Subject: Re: Tree command - Display Structure of Directory Hierarchy
From: "Ehud Karni" <[email-masked]>
To: "Dave Korn" <[email-masked]>
Cc: [email-masked], [email-masked], "Charles Wilson" <[email-masked]>
Date: Wed, 30 Sep 2009 14:22:22 +0200
List-Id: <cygwin.cygwin.com>

On Tue, 29 Sep 2009 21:52:02 Dave Korn wrote:
>
>   That is precisely why I asked for the source, and precisely the advantage of
> open source over proprietary closed sources :-)

I attach a source code for my own (simplified version) treed program
(do your own compilation, my gcc command is in the source).
This program is not related to the previous attached binary of `tree'.

This program is released under the GPL, so you can do any modification
to it. If you do, please post your changes (and the reason behind it).

Ehud.

--
 Ehud Karni           Tel: +972-3-7966-561  /"\
 Mivtach - Simon      Fax: +972-3-7976-561  \ /  ASCII Ribbon Campaign
 Insurance agencies   (USA) voice mail and   X   Against   HTML   Mail
 http://www.mvs.co.il  FAX:  1-815-5509341  / \
 GnuPG: 98EA398D <http://www.keyserver.net/>    Better Safe Than Sorry
/* TREED: list all directories from given node
    Copyright (C) 1994-2009 Ehud karni <[email-masked]>

       Compile command: gcc treed.c -O2 -o treed -static -Wall

    command call:  treed [-<number>] [-n] [-s] [-x] [dir]
       -<number> = max depth of branching
       -s        = follow symbolic links
       -x        = cross mount point
       -n        = print net size (bytes not including unused block parts)
       -m        = print size in Megabytes (1024*1024) instead of Kilobytes (1024)

       RCS: $Id: treed.c,v 1.112 2009/01/15 17:02:19 ehud Exp ehud $

       $Log: treed.c,v $
       Revision 1.112  2009/01/15 17:02:19  ehud
       Add -m switch for printing sizes in Megabytes

       Revision 1.111  2006/05/21 16:10:37  ehud
       Added net size option: -n. Added struct blksiz (blocks & char size)
       used instead of blocks.  Changed total_dir () to struct blksiz,

       Revision 1.110  2005/04/18 10:52:54  ehud
       Remove kvv, kvh, kvnx - use kvchars instead, set it according to
       terminal type - NPC? (pc graphics) characters or textual (any other).

       Revision 1.109  2003/05/15 12:02:31  ehud
       Use 64 bit file ops (LFS) - just added defines.
       Change size (750 ents) and fix check for directory "realoc".

       Revision 1.108  2001/07/04 11:17:38  ehud
       Change the allocation of the directories list

       Revision 1.107  2001/06/05 16:17:14  ehud
       Delete inode hashing altogether

       Revision 1.106  2001/06/05 12:44:35  ehud
       Adjustments for W32, changes in ino hash schem (no good).

       Revision 1.105  1997/01/14 16:23:01  ehud
       Changes to ttywrt_, detecting q on page wait

       Revision 1.104  1996/04/15  11:51:05  ehud
       Changes for SGI compatibilty

       Revision 1.103  1994/11/30  14:17:46  ehud
       Fix bug (different devices) and deal with mount crossing

       Revision 1.100  1994/11/08  11:01:42  ehud
       Initial version control use

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 3 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You can find a copy of the GNU General Public License and some
    more information at:  http://www.gnu.org/copyleft/gpl.html

                                                           Ehud  Karni */

#define DEBUG  0                       /* debug prints ON / OFF */

#define _FILE_OFFSET_BITS 64           /* use 64 bit file length */
#define _LARGEFILE64_SOURCE 1          /* LFS support needed */

#ifdef __MSDOS__
#define  __DOS_W32__   1               /* dos (DJGPP) or W32 (mingw) */
#endif /* __MSDOS__ */
#ifdef __MINGW__
#define  __DOS_W32__   1               /* dos (DJGPP) or W32 (mingw) */
#endif /* __MINGW__ */

#include <string.h>                            /* standard string library */
#include <stdio.h>                             /* standard I/O library */
#include <stdlib.h>                            /* standard library */
#include <sys/types.h>                         /* UNIX sys types */
#include <signal.h>                            /* standard signal library */
#include <time.h>                              /* date/time structers */
#include <dirent.h>                            /* directory entry */
#include <sys/stat.h>                          /* File status entry */

#ifndef __DOS_W32__                            /* include for REAL unix only */
#include <unistd.h>                            /* UNIX non standard library */

#define RE_ALOC(pntr,count)                    /* reallocate table (pntr) to count entries */ \
   { register void *tmpp ;                     /* tmp pointer */                   \
       while ( ( ( tmpp = realloc ( pntr, count * sizeof ( pntr[0] ) ) ) == NULL ) \
               && ( count != 0 ) )                                                 \
       {                                                                           \
           fprintf ( stderr, "Can not allocate %d entries, waiting.\n", count ) ;  \
           sleep (1) ;                                                             \
       }                                                                           \
       pntr = tmpp ;                                                               \
   }

#define flstat lstat                           /* file status function name (UNIX) - no symbolic */

#else  /* __DOS_W32__ */
#define flstat  stat                           /* file status function name (PC) */
#endif /* not __DOS_W32__ */

static const char *RCS_WHAT = "<@(#) $Id: treed.c,v 1.112 2009/01/15 17:02:19 ehud Exp ehud $  >" ;

char pline [ 500 ] ;                           /* line to be printed */

unsigned int switches = 0 ;                    /* switches int */
#define  SYMBOLIC_BIT 0x01                     /* follow symbolic link bit */
#define  X_MOUNT_BIT  0x02                     /* cross mount point bit */
#define  NETO_BIT     0x04                     /* Display size in bytes */
#define  MEGA_BIT     0x08                     /* Display size in megabytes */
#define  SYMBOLIC     ( switches & SYMBOLIC_BIT )  /* symbolic ON */
#define  X_MOUNT      ( switches & X_MOUNT_BIT )   /* cross mount ON */
#define  NETO         ( switches & NETO_BIT )      /* Bytes neto ON */
#define  MEGA_BYTES   ( switches & MEGA_BIT )      /* Mega bytes ON */

int max_lvl = 0x7FFF ;                         /* max branching level */
int b_lvl = -1 ;                               /* current branching level */

char *blnk = "      " ;                        /* blank spaces between branches */

char *kvchars [ 9 ] = {                        /* dumb terminal characters */
           "! |"   , "! |"    , "!"  ,         /* vertical line * 3 */
           "! +- " , "! \\- " , "!"  ,         /* horizontal line (0, 1, 2) */
           " |"    , "  "     , " |" } ;       /* next vertical line * 3 */

DIR *hdir ;                                    /* handle for open directory */
struct dirent *dent ;                          /* directory entry pointer */
struct stat Fstat ;                            /* file status entry */

struct blksiz                                  /* structure to be used with total_dir */
   {
       long long blocks ;                      /* size in dev size blocks - must use 64 bits */
       long long charsz ;                      /* Net size in characters */
   } ;

/* = = = = = = = = = = = = = =   my  functions   = = = = = = = = = = = = = = = = = = = = = */

void draw_dir ( char *dirn, char *prfx , int tprfx ) ; /* draw tree for 1 directory */
int  params ( int argc, char *argv[] ) ;               /* check command line params */
int pntstrcmp ( char **e1, char **e2 ) ;               /* strcmp of *e1 and *e2 */
#ifdef __DOS_W32__                                     /* use this for MINGW only */
unsigned long make_ino ( char *dirn, int b_lvl ) ;     /* make hash ino from name & branch level */
#endif /* not __DOS_W32__ */
struct blksiz total_dir ( char *dirn ) ;               /* total blocks in dir (recursive) */
void wrt_prfx ( char *prfx , int tprfx ) ;             /* write prefix to terminal */
void wrt_term ( char *txt ) ;                          /* write 1 line to terminal and check input */
/* = = = = = = = = = = = = = =   my  functions   = = = = = = = = = = = = = = = = = = = = = */

int main ( int argc, char *argv[] )
{
int i ;
char *dir1 ;

   i = params ( argc, argv ) ;                 /* check params */

   if ( i < argc )
       dir1 = argv [ i ] ;                     /* given input dir */
   else
       dir1 = "." ;                            /* not given, use . */

#ifndef __DOS_W32__                            /* include for REAL unix only */
   setuid ( 0 ) ;                              /* Make it run with root id (may fail) */
#endif /* not __DOS_W32__ */

   if ( chdir ( dir1 ) != 0 )
   {
       fprintf (stderr, "\n can not change to dir %s, Aborted ! \n" , dir1 ) ;
       exit ( 2 ) ;
   }

   wrt_term ( "0 treed of " ) ;                /* header part 1 */
   getcwd ( pline + 1 , sizeof ( pline ) ) ;   /* header dir name */
   pline [ 0 ] = '!' ;
   wrt_term ( pline ) ;                        /* write it */

   draw_dir ( "." , "  " , 2 ) ;               /* draw dir tree */

   wrt_term ( "0\n" ) ;                        /* double space at the end */
   return  ( 0 ) ;                             /* end of program */
}
/*============================================================================*/

void draw_dir ( char *dirn, char *prfx , int tprfx )
{                                   /* draw full directory tree (recursive) */
#ifndef  __CYGWIN__                            /* real UNIX / Linux */
#define S2K  >> 1                              /* block size is 512 on real UNIX */
#else
#define S2K                                    /* block size on Cygwin = 1KB (no need to do / 2) */
#endif

#define ADD_dirn 750                           /* Add pointers number (1K blocks) */
#define ADD_name 16320                         /* Add memory size (16K blocks) */
char  **sv_dirs = NULL ;                       /* pointers to saved directory names */
char  *sv_name = NULL ;                        /* saved directory names (strings) */
unsigned int aloc_dirn = 0 ;                   /* no. of dir names allocated */
unsigned int no_dirn = 0 ;                     /* no. of dir names used */
unsigned int aloc_name = 0 ;                   /* size of dir names allocated */
unsigned int used_name = 0 ;                   /* size of dir names used */

#define old_dir_SIZE 500                       /* length of saved current directory */
char  old_dir [ old_dir_SIZE ] ;               /* saved current directory */
char  nprfx [ 300 ] ;                          /* new prefix */
struct blksiz sz = { 0 , 0 } ;                 /* blocks , net size in chars */
int  nofls = -2 ;                              /* no. of files in dir (ignore . & .. ) */

char  *pnt ;                                   /* tmp pointer */
int  i ;                                       /* tmp index */

   b_lvl++ ;                                   /* current branch level */

   if ( getcwd ( old_dir , old_dir_SIZE ) == NULL )
   {
       wrt_prfx ( prfx , tprfx ) ;
       wrt_term ( "! parent directory name too long, not entered" ) ;
       return ;
   }

   if ( chdir ( dirn ) != 0 )
   {
       fprintf ( stderr , "DIR  Parent=|%s|, Sub=|%s|\n" , old_dir , dirn ) ;
       wrt_prfx ( prfx , tprfx ) ;
       wrt_term ( "! change to directory " ) ;
       sprintf ( pline, "!%s  error " , dirn ) ;
       wrt_term ( pline ) ;
       return ;
   }

   sz = total_dir ( NULL ) ;                   /* total files length in dir & subs */

   hdir = opendir ( "." ) ;                    /* open directory requests */

   if ( hdir == NULL )
   {
       fprintf ( stderr , "\ndraw-dir **** opendir . (%s) failed *****", dirn ) ;
       perror ( " opendir failed " ) ;
       exit (3) ;
   }

   while ( ( dent = readdir ( hdir ) ) != NULL )   /* next entry */
   {
       pnt = dent->d_name ;                    /* file name pointer */

       if ( flstat ( pnt , & Fstat ) == 0 )    /* file status entry (no symbolic !) */
       {
           nofls ++ ;                          /* no. of files in dir */

#ifndef __DOS_W32__                                        /* include for REAL unix only */
           if ( ( ( Fstat.st_mode & S_IFMT ) == S_IFLNK )  /* symbolic link */
                   && ( SYMBOLIC ) )                       /* follow symbolic links ON */
               stat ( pnt , & Fstat ) ;                    /* file status entry (follow symbolic) */
#endif /* not __DOS_W32__ */
           if ( ( ( Fstat.st_mode & S_IFMT ) == S_IFDIR )  /* directory  AND */
                   && ( ( Fstat.st_ino != 2 ) ||           /* not mount point ? */
                        ( X_MOUNT ) )                      /* or cross mount points ? */
                   && ( strcmp ( pnt , "." ) != 0 )        /* ignore . and .. */
                   && ( strcmp ( pnt , ".." ) != 0 ) )     /* ignore . and .. */
               {
               int dirlen = strlen ( pnt ) + 1;            /* temp: length of dirname (+ Zbyte) */
#if DEBUG
                   fprintf ( stderr , "Read dir is |%s|, len=%d   aloc=%d no_dir=%d" ,
                             pnt , dirlen , aloc_dirn , no_dirn ) ;
#endif /* not DEBUG */

                   if ( aloc_dirn <= no_dirn )             /* no more room for name pointers ? */
                   {
                       aloc_dirn += ADD_dirn ;             /* work in 1K blocks */
                       RE_ALOC ( sv_dirs , aloc_dirn ) ;   /* allocate more entries */
#if DEBUG
                       fprintf ( stderr , "sv_dirs re_alloc'ed, aloc_dirn=%d\n" , aloc_dirn ) ;
#endif /* not DEBUG */
                   }
                   while ( aloc_name <= ( used_name + dirlen ) )   /* no more room for names ? */
                   {
                   char *name_bfr = sv_name ;
#if DEBUG
                       fprintf ( stderr , "\nBefore sv_name re_alloc'ed, pntr=%ld, aloc_name=%d\n" ,
                                 (long) sv_name , aloc_name ) ;
#endif /* not DEBUG */
                       aloc_name += ADD_name ;             /* work in 4K blocks */
                       RE_ALOC ( sv_name , aloc_name ) ;   /* allocate another block */
#if DEBUG
                       fprintf ( stderr , "After  sv_name re_alloc'ed, pntr=%ld, aloc_name=%d\n" ,
                                 (long) sv_name , aloc_name ) ;
#endif /* not DEBUG */
                       if ( name_bfr != sv_name )          /* names moved ? */
                       {                                   /* yes, must adjust pointers */
#if DEBUG
                           fprintf ( stderr , "Adjust sv_dirs pointers by %d\n" , sv_name - name_bfr ) ;
#endif /* not DEBUG */
                           for ( i = 0 ; i < no_dirn ; i++ )
                               sv_dirs [ i ] += sv_name - name_bfr ;   /* adjust dir name pointer */
                       }
                   }

                   sv_dirs [ no_dirn ] = sv_name + used_name ; /* dirname saved pointer */
                   strcpy ( sv_name + used_name , pnt ) ;      /* add to saved dir table */
#if DEBUG
                   fprintf ( stderr , "   sv_dir[]=|%s|\n" , sv_dirs [ no_dirn ] ) ;
#endif /* not DEBUG */
                   no_dirn ++ ;                            /* no. of dir names in table */
#if DEBUG
                   fprintf ( stderr , "no_dirn=%d, sv_name=|%s| sv_dirs[0]=|%s|\n" ,
                             no_dirn , sv_name , sv_dirs [0] ) ;
#endif /* not DEBUG */
                   used_name += dirlen ;                   /* no. of chars used in names */
               }
       }
   }

   closedir ( hdir ) ;                         /* close this directory */

   if ( tprfx == 2 )                           /* top top dir ? */
       dirn = old_dir ;                        /* change to full name */

   wrt_prfx ( prfx , tprfx ) ;
   if ( NETO )                                 /* display neto size (bytes) ? */
       sprintf ( pline, "!%s (%d files, %lld)",
                 dirn , nofls , sz.charsz ) ;
   else
   if ( MEGA_BYTES )                           /* display size in Mega bytes ? */
       sprintf ( pline, "!%s (%d files, %ld MB)",
                 dirn , nofls , ( ( (sz.blocks >> 10) + 1) S2K ) ) ;
   else
       sprintf ( pline, "!%s (%d files, %ld KB)",
                 dirn , nofls , ( (sz.blocks + 1) S2K ) ) ;
   wrt_term ( pline ) ;                        /* write this line */

   if ( ( no_dirn > 0 ) &&                     /* no. of directories in this dir */
        ( b_lvl < max_lvl ) )                  /* branching < maximum */
   {
       qsort ( sv_dirs , no_dirn , sizeof (char *) , (void *) pntstrcmp ) ;
                                               /* sort by name */
       if ( tprfx == 2 )
           strcpy ( nprfx, blnk ) ;            /* root of treed */
       else
           sprintf ( nprfx , "%s%s%s" , prfx , kvchars [ tprfx + 6 ] , blnk ) ;/* new prfx */

       i = 0 ;
       no_dirn -- ;                            /* 1 less for last */
       while ( i < no_dirn )
       {
#if DEBUG
           fprintf ( stderr , "Call draw-dir. index=%d, name=|%s|\n" , i , sv_dirs [ i ] ) ;
#endif /* not DEBUG */
           draw_dir ( sv_dirs [ i++ ] , nprfx , 0 ) ;  /* not last sub directory */
       }

       draw_dir ( sv_dirs [ i ] , nprfx , 1 ) ;/* last subdirectory */
   }

   free ( sv_dirs ) ;                          /* free saved */
   free ( sv_name ) ;                          /* dir names */
   b_lvl -- ;                                  /* current branch level */

   if ( chdir ( old_dir ) != 0 )
   {
       wrt_term ( "-  cannot change back to parent error !" ) ;
       exit ( 3 ) ;
   }
}
/*============================================================================*/

int pntstrcmp ( char **e1, char **e2 )         /* strcmp of *e1 and *e2 */
{
   return ( strcmp ( *e1 , *e2 ) ) ;           /* dereference 1 level */
}
/*============================================================================*/

int params ( int argc, char *argv[] )          /* check command line params */
{                                              /* return 1st not known (0 for ?) */
int i = 1 ;                                    /* temp index */
char *ptr ;

   while ( i < argc )
   {
       ptr = argv [ i ] ;

       if ( *ptr++ != '-' )                    /* check if parameter (-x) */
           return ( i ) ;                      /* no, assume file name */

       switch( *ptr | ( 'A' ^ 'a' ) )          /* check all lower case */
       {

               case '0' :                      /* max branching lvl */
               case '1' :
               case '2' :
               case '3' :
               case '4' :
               case '5' :
               case '6' :
               case '7' :
               case '8' :
               case '9' :
                       max_lvl = atoi ( ptr ) ;/* convert to number */
                       break ;

               case 'm' :
                       switches |= MEGA_BIT ;  /* Show size in Megabytes */
                       break ;

               case 'n' :
                       switches |= NETO_BIT ;  /* Show size in bytes neto */
                       break ;

               case 's' :
                       switches |= SYMBOLIC_BIT ;  /* no symbolic link bit */
                       break ;

               case 'x' :
                       switches |= X_MOUNT_BIT ;   /* cross mount points */
                       break ;

               default:
                       return ( i ) ;

       }
       i++ ;                                   /* next input */

   }
   return ( i ) ;                              /* use standard input (no files) */
}
/*============================================================================*/

struct blksiz total_dir ( char *dirn )         /* total files length in dir (recursive) */
{                                              /* if dirn is NULL, compute for current directory */
DIR *tdir ;                                    /* handle for open directory */
struct dirent *tent ;                          /* directory entry pointer */
struct blksiz sz = { 0 , 0 } ;                 /* blocks , net size in chars */
char  *pnt ;                                   /* tmp pointer */

   if ( dirn != NULL )
   {
       if ( chdir ( dirn ) != 0 )
           return ( sz ) ;                     /* 0 blocks, no error */
       b_lvl++ ;                               /* current branch level */
   }

   tdir = opendir ( "." ) ;                    /* open directory requests */
   if ( tdir == NULL )
   {
       fprintf ( stderr , "\ntotal-dir **** opendir . (%s) failed *****", dirn ) ;
       perror ( " opendir failed " ) ;
       exit (3) ;
   }

   while ( ( tent = readdir ( tdir ) ) != NULL )       /* next entry */
   {
       pnt = tent->d_name ;                            /* file name pointer */
       if ( flstat ( pnt , & Fstat ) == 0 )            /* file status entry (no symbolic !) */
       {
           if ( Fstat.st_ino == 2 )                    /* mount point ? */
           {
               if ( ! X_MOUNT )                        /* do not cross mount points ? */
                   pnt = ".." ;                        /* ignore this directory ! (do not cross) */
           }

           if ( ( Fstat.st_mode & S_IFMT ) == S_IFDIR )/* directory */
           {
               Fstat.st_nlink = 1 ;                    /* for size computation */
               if ( ( strcmp ( pnt , "." ) == 0 ) ||   /* ignore . and .. */
                       ( strcmp ( pnt , ".." ) == 0 ) )
                   continue ;                          /* no further action */
#ifndef __DOS_W32__                                    /* include for REAL unix only */
           Fstat.st_size = 0 ;                         /* ignore directory size for net size */
#endif /* not __DOS_W32__ */
           }

#ifndef __DOS_W32__                                    /* include for REAL unix only */
           sz.blocks += Fstat.st_blocks / Fstat.st_nlink ; /* add blocks */
           sz.charsz += Fstat.st_size / Fstat.st_nlink ;   /* add characters */
#else  /* __DOS_W32__ */
           sz.blocks += ( ( Fstat.st_size + 511 ) / 512 ) ;/* size in K bytes */
           sz.charsz += Fstat.st_size ;                /* add blocks */
#endif /* not __DOS_W32__ */

           if ( ( Fstat.st_mode & S_IFMT ) == S_IFDIR )/* directory */
           {
           struct blksiz ts ;                          /* temp: blocks , net size in chars */
                   ts = total_dir ( pnt ) ;            /* total files length in subdir */
                   sz.blocks += ts.blocks ;            /* add total blocks */
                   sz.charsz += ts.charsz ;            /* add net size in chars */
           }
       }
   }

   closedir ( tdir ) ;                         /* close this directory */

   if ( dirn != NULL )
   {
       if ( chdir ( ".." ) != 0 )
       {
           wrt_term ( "-     cannot change back to parent (..) error ! " ) ;
           exit ( 3 ) ;
       }
       b_lvl-- ;                               /* current branch level */
   }
   else
       dirn = "Root" ;

   return ( sz ) ;                             /* blocks & charsz */
}
/*============================================================================*/

void wrt_prfx ( char *prfx , int tprfx )       /* write prefix to terminal */
{
   wrt_term ( prfx ) ;
   wrt_term ( kvchars [ tprfx ] ) ;

   wrt_term ( prfx ) ;
   wrt_term ( kvchars [ tprfx + 3 ] ) ;
}
/*============================================================================*/

void wrt_term ( char *txt )                    /* write 1 line and check input */
{
   switch ( *txt )
   {
       case '!':                               /* ! - continue from last */
               break ;

       case '+':                               /* + - same as last line */
               putchar ( '\r' ) ;              /* Carriage Return */
               break ;

       case '-':                               /* - - triple space */
               putchar ( '\n' ) ;              /* 1 New Line */
       case '0':                               /* 0 - double space */
               putchar ( '\n' ) ;              /* 1 New Line */
       default :                               /* space/any single space */
               putchar ( '\n' ) ;              /* 1 New Line */
   }
   fputs ( txt + 1 , stdout ) ;                /* write rest of line */

   return ;
}
/*==========================================================================*/

--
Problem reports:       http://cygwin.com/problems.html
FAQ:                   http://cygwin.com/faq/
Documentation:         http://cygwin.com/docs.html
Unsubscribe info:      http://cygwin.com/ml/#unsubscribe-simple