/* TREED: list all directories from given node
    Copyright (C) 1994-2009 Ehud karni <ehud@unix.mvs.co.il>

       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 ;
}
/*==========================================================================*/