home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / misc / volume1 / 8712 / 8 < prev    next >
Encoding:
Text File  |  1990-07-13  |  11.2 KB  |  460 lines
  1. Path: uunet!husc6!think!ames!necntc!ncoast!allbery
  2. From: drw@culdev1.UUCP (Dale Worley)
  3. Newsgroups: comp.sources.misc
  4. Subject: Prettyprint a du listing
  5. Message-ID: <6803@ncoast.UUCP>
  6. Date: 17 Dec 87 02:33:54 GMT
  7. Sender: allbery@ncoast.UUCP
  8. Organization: Cullinet Software, Westwood, MA, USA
  9. Lines: 447
  10. Approved: allbery@ncoast.UUCP
  11. X-Archive: comp.sources.misc/8712/8
  12.  
  13. I've always wanted to get a du listing that shows how the space is
  14. being used graphically.  I finally wrote a program to digest a du
  15. listing and print out a tree, where each directory occupies lines
  16. proportionally to how much space the files in it consume.
  17.  
  18. To run it, type "du | dugraph" or some such.  The listing for each
  19. directory starts with a blank space showing space occupied by files
  20. directly in that directory, then the subtrees for each subdirectory
  21. (in descending order of size).  If the subdirectories at the bottom
  22. get so small that they occupy less than 1 line each, they are all
  23. merged into an entry "(etc.)".
  24.  
  25. The entire listing always occupies 60 lines (the value of 'length').
  26. This program has tab-width = 5.
  27. --------------------------dugraph.c---------------------------------
  28. /* program to make a pretty graph out of a du report */
  29.  
  30. #include <stdio.h>
  31. #include <string.h>
  32.  
  33. /* number of lines the listing should occupy */
  34. int    length = 60;
  35. /* message for suppressed directories */
  36. #define    SUPPRESSED    "(etc.)"
  37.  
  38. /* format of a tree node */
  39. struct node {
  40.             struct node    *lson;    /* left son */
  41.             struct node    *rbrother;/* right brother */
  42.             unsigned long    size;    /* size of directory in kbytes */
  43.             int            loc;        /* location we will print it at */
  44.             int            print_col;/* column to print name in */
  45.             int            print_limit;
  46.                                 /* location we can't print on or
  47.                                  * after */
  48.             int            last;    /* are we last son of our father? */
  49.             char            name[1];    /* name */
  50.           };
  51.  
  52. /* root of the tree */
  53. struct node    *root = NULL;
  54. /* total size of things listed */
  55. unsigned long    total_size;
  56. /* current line number we are on (0-origin) */
  57. int            current_line = 0;
  58. /* list of where to put bars */
  59. int            bar_list[50];
  60. /* number of bars in the list */
  61. int            bar_count = 0;
  62.  
  63. /* declare functions */
  64. void            read_input();
  65. struct node    *insert_in_tree();
  66. void            dfs();
  67. void            dfs1();
  68. void            missing_sizes();
  69. void            sort();
  70. void            calc_loc();
  71. void            blank();
  72. void            mark_last();
  73. void            calc_pc();
  74. void            output();
  75. void            position();
  76.  
  77. main()
  78.     {
  79.     struct node    *t;    /* scratch */
  80.  
  81.     /* read the input and form a tree */
  82.     read_input();
  83.     root->size = 0;
  84.     /* put sizes on entries that have none */
  85.     dfs(NULL, missing_sizes);
  86.     /* sort each directory */
  87.     dfs(sort, NULL);
  88.     /* calculate the total size */
  89.     total_size = 0;
  90.     for (t = root->lson; t != NULL; t = t->rbrother)
  91.         total_size += t->size;
  92.     /* calculate the location of each directory */
  93.     /* blank out subdirectories that get scrunched together at the bottom */
  94.     root->print_limit = length;
  95.     dfs(calc_loc, blank);
  96.     /* print out the tree */
  97.     for (t = root->lson; t != NULL; t = t->rbrother)
  98.         {
  99.         /* mark the last son of each directory */
  100.         /* figure out the print columns */
  101.         t->print_col = 0;
  102.         dfs1(calc_pc, mark_last, t);
  103.         dfs1(output, NULL, t);
  104.         }
  105.     /* put blank space at end */
  106.     position(length);
  107.     }
  108.  
  109. /* read input and form a tree */
  110. void read_input()
  111.     {
  112.     unsigned long    size;        /* size read from input */
  113.     char            name[100];    /* directory name read from input */
  114.  
  115.     /* make the dummy node at the top of the tree */
  116.     root = (struct node *)malloc(sizeof (struct node));
  117.     root->name[0] = '\0';
  118.     root->lson = NULL;
  119.     /* read the next line of input */
  120.     while (fscanf(stdin, "%lu %s\n", &size, name) != EOF)
  121.         {
  122.         /* insert (or find) the directory in the tree and save its size */
  123.         insert_in_tree(name)->size = size;
  124.         }
  125.     }
  126.  
  127. /* insert (or find) a directory in the tree */
  128. struct node *insert_in_tree(name)
  129.     char    *name;        /* name of the directory */
  130.     {
  131.     struct node    *t;    /* pointer for searching down through tree */
  132.     char            *np;    /* points to next part of directory name to be
  133.                      * examined */
  134.     struct node    *t1;    /* scratch pointer */
  135.     char            *np1;/* scratch pointer */
  136.  
  137.     /* read through the name, one directory-part at a time, and hunt
  138.      * down the tree, constructing nodes as needed */
  139.     for (t = root, np = name; np != NULL; np = np1)
  140.         {
  141.         /* extract the next directory-part */
  142.         if ((np1 = strchr(np, '/')) != NULL)
  143.             {
  144.             /* we found a slash, replace it with a null, and position
  145.              * np1 to point to the remainder of the name */
  146.             *np1++ = '\0';
  147.             }
  148.         /* else */
  149.             /* we found no shash, so we are at the end of the name
  150.              * np1 has been set to NULL for us by strchr */
  151.         /* search the sons of this node for a node with the proper name */
  152.         for (t1 = t->lson; t1 != NULL && strcmp(t1->name, np) != 0;
  153.                 t1 = t1->rbrother)
  154.             ;
  155.         /* did we find one? */
  156.         if (t1 != NULL)
  157.             /* yes, go to it */
  158.             t = t1;
  159.         else
  160.             {
  161.             /* no, make one */
  162.             t1 = (struct node *)malloc(sizeof(struct node) + strlen(np));
  163.             strcpy(t1->name, np);
  164.             t1->lson = NULL;
  165.             t1->rbrother = NULL;
  166.             t1->size = 0;
  167.             /* insert it in tree */
  168.             t1->rbrother = t->lson;
  169.             t->lson = t1;
  170.             t = t1;
  171.             }
  172.         }
  173.     return t;
  174.     }
  175.  
  176. /* depth-first-search routine */
  177. void dfs(pre_routine, post_routine)
  178.     void    (*pre_routine)();    /* routine to execute before scanning
  179.                          * descendants */
  180.     void    (*post_routine)();    /* routine to execute after scanning
  181.                          * descendants */
  182.     {
  183.     dfs1(pre_routine, post_routine, root);
  184.     }
  185.  
  186. /* depth-first-search service routine */
  187. void dfs1(pre_routine, post_routine, t)
  188.     void    (*pre_routine)();    /* routine to execute before scanning
  189.                          * descendants */
  190.     void    (*post_routine)();    /* routine to execute after scanning
  191.                          * descendants */
  192.     struct node *t;        /* node to operate on */
  193.     {
  194.     struct node *t1;        /* scratch pointer */
  195.  
  196.     /* if it exists, execute the pre-routine */
  197.     if (pre_routine != NULL)
  198.         pre_routine(t);
  199.     /* call self on sons of this node */
  200.     for (t1 = t->lson; t1 != NULL; t1 = t1->rbrother)
  201.         dfs1(pre_routine, post_routine, t1);
  202.     /* if it exists, execute the post-routine */
  203.     if (post_routine != NULL)
  204.         post_routine(t);
  205.     }
  206.  
  207. /* add missing sizes */
  208. void missing_sizes(t)
  209.     struct node    *t;
  210.     {
  211.     struct node    *t1;        /* scratch pointer */
  212.     unsigned long    s;        /* scratch */
  213.  
  214.     if (t->size == 0)
  215.         {
  216.         /* size is missing, we have to calcuate it */
  217.         s = 0;
  218.         for (t1 = t->lson; t1 != NULL; t1 = t1->rbrother)
  219.             s += t1->size;
  220.         t->size = s;
  221.         }
  222.     }
  223.  
  224. /* sort the directories under a directory */
  225. void sort(t)
  226.     struct node    *t;
  227.     {
  228.     struct node    *p1, *p2, *p3, *pp;        /* scratch pointers */
  229.     int            nodes, n;                /* scratch */
  230.  
  231.     /* count the number of nodes */
  232.     nodes = 0;
  233.     for (p1 = t->lson; p1 != NULL; p1 = p1->rbrother)
  234.         nodes++;
  235.     /* just a simple and inefficient bubble sort */
  236.     for (n = 1; n < nodes; n++)
  237.         for (p1 = NULL, p2 = t->lson, p3 = p2->rbrother; p3 != NULL;
  238.                 p1 = p2, p2 = p3, p3 = p3->rbrother)
  239.             {
  240.             if (p2->size < p3->size)
  241.                 {
  242.                 /* exchange the nodes p2 and p3 */
  243.                 pp = p3->rbrother;
  244.                 p3->rbrother = p2;
  245.                 p2->rbrother = pp;
  246.                 if (p1 != NULL)
  247.                     p1->rbrother = p3;
  248.                 else
  249.                     t->lson = p3;
  250.                 /* exchange the values of p2 and p3 */
  251.                 pp = p2;
  252.                 p2 = p3;
  253.                 p3 = pp;
  254.                 }
  255.             }
  256.     }
  257.  
  258. /* calculate the print location */
  259. void calc_loc(t)
  260.     struct node    *t;
  261.     {
  262.     unsigned long    cs;        /* scratch */
  263.     struct node    *t1, *t2;    /* scratch pointers */
  264.     int            print_limit;
  265.                         /* location next directory after t will
  266.                          * be printed */
  267.  
  268.     if (t == root)
  269.         cs = 0;
  270.     else
  271.         {
  272.         /* figure out how much is in the directory itself */
  273.         for (t1 = t->lson, cs = 0; t1 != NULL; t1 = t1->rbrother)
  274.             {
  275.             cs += t1->size;
  276.             }
  277.         /* cs is the size accounted for by subdirectories */
  278.         cs = t->size - cs;
  279.         }
  280.     /* cs is the size of the files in the directory itself */
  281.     /* convert cs to lines */
  282.     cs = cs*length/total_size + t->loc;
  283.     /* calculate where next directory after t will be */
  284.     print_limit = t->print_limit;
  285.     /* assign locations */
  286.     for (t1 = t->lson, t2 = NULL; t1 != NULL; t2 = t1, t1 = t1->rbrother)
  287.         {
  288.         /* make sure we don't run into next directory */
  289.         if (cs >= print_limit)
  290.             {
  291.             cs = print_limit-1;
  292.             }
  293.         t1->loc = cs;
  294.         if (t2 != NULL)
  295.             t2->print_limit = cs;
  296.         cs += t1->size*length/total_size;
  297.         }
  298.     if (t2 != NULL)
  299.         t2->print_limit = print_limit;
  300.     }
  301.  
  302. /* figure out which directories to blank out */
  303. void blank(t)
  304.     struct node    *t;
  305.     {
  306.     struct node    *t1, *t2, *t3;        /* loop pointers */
  307.  
  308.     /* return if there aren't at least two sons */
  309.     if (t->lson == NULL || t->lson->rbrother == NULL)
  310.         return;
  311.     for (t1 = NULL, t2 = t->lson, t3 = t2->rbrother; t3 != NULL;
  312.             t1 = t2, t2 = t3, t3 = t3->rbrother)
  313.         if (t2->loc == t3->loc)
  314.             {
  315.             /* replace t1 and succeeding nodes with "(etc.)" */
  316.             t3 = (struct node *)malloc(sizeof (struct node) +
  317.                 sizeof (SUPPRESSED) - 1);
  318.             strcpy(t3->name, SUPPRESSED);
  319.             t3->lson = t3->rbrother = NULL;
  320.             t3->loc = t2->loc;
  321.             if (t1 == NULL)
  322.                 t->lson = t3;
  323.             else
  324.                 t1->rbrother = t3;
  325.             }
  326.     }
  327.  
  328. /* mark the last son of each directory */
  329. void mark_last(t)
  330.     struct node    *t;
  331.     {
  332.     struct node    *t1, *t2;    /* scratch pointers */
  333.     t->last = 0;
  334.     for (t1 = t->lson, t2 = NULL; t1 != NULL; t2 = t1, t1 = t1->rbrother)
  335.         ;
  336.     if (t2 != NULL)
  337.         t2->last = 1;
  338.     }
  339.  
  340. /* calculate the print columns */
  341. void calc_pc(t)
  342.     struct node    *t;
  343.     {
  344.     struct node    *t1;        /* scratch pointer */
  345.     int            c;        /* column suns will be printed in */
  346.  
  347.     c = t->print_col + strlen(t->name) + 5;
  348.     for (t1 = t->lson; t1 != NULL; t1 = t1->rbrother)    
  349.         t1->print_col = c;
  350.     }
  351.  
  352. /* write the output */
  353. void output(t)
  354.     struct node    *t;
  355.     {
  356.     position(t->loc);
  357.     printf("--%s%s", t->name, (t->lson != NULL ? "--+" : ""));
  358.     /* remove the bar for our father if we are the last son */
  359.     if (t->last)
  360.         bar_count--;
  361.     /* add the location of the bar to the bar list if we have a son */
  362.     if (t->lson != NULL)
  363.         {
  364.         bar_list[bar_count] = t->print_col + strlen(t->name) + 5 - 1;
  365.         bar_count++;
  366.         }
  367.     }
  368.  
  369. /* position to a specific line */
  370. void position(line)
  371.     int    line;        /* line number */
  372.     {
  373.     int    i;            /* counts through the bar list */
  374.     int    j;            /* current column number */
  375.  
  376.     /* for every line we need to go down */
  377.     for (; current_line < line; current_line++)
  378.         {
  379.         putchar('\n');
  380.         /* print the bars for this line */
  381.         j = 0;
  382.         for (i = 0; i < bar_count; i++)
  383.             {
  384.             for (; j < bar_list[i]; j++)
  385.                 putchar(' ');
  386.             if (current_line == line-1 && i == bar_count-1)
  387.                 putchar('+');
  388.             else
  389.                 putchar('|');
  390.             j++;
  391.             }
  392.         }
  393.     }
  394. -----------------------------------example-----------------------------------
  395. --.--+
  396.      |
  397.      |
  398.      |
  399.      |
  400.      |
  401.      |
  402.      |
  403.      +--scpp--+--ftps--+
  404.      |        |        +--scpp--+--temp
  405.      |        +--error
  406.      |        |
  407.      |        +--shar--+
  408.      |                 |
  409.      |                 +--temp
  410.      +--uemacs--+--uemacs3.9
  411.      |
  412.      |
  413.      |
  414.      |
  415.      |
  416.      |
  417.      +--patch--+--dist
  418.      |         |
  419.      |         |
  420.      |         +--build
  421.      |
  422.      |
  423.      |
  424.      +--sccs--+--all
  425.      |        |
  426.      |        |
  427.      |        |
  428.      |        +--(etc.)
  429.      +--yacctest
  430.      |
  431.      |
  432.      |
  433.      +--yacc
  434.      |
  435.      |
  436.      |
  437.      +--rnsend--+--dist1
  438.      |          +--dist3
  439.      |          +--dist2
  440.      +--bin--+
  441.      |       +--source
  442.      +--sources
  443.      |
  444.      +--kwfrob
  445.      +--rsts.tape
  446.      +--rnews
  447.      +--ftp-server
  448.      +--(etc.)
  449.  
  450.  
  451.  
  452.  
  453.  
  454.  
  455. ------------------------------end of example------------------------------
  456. -- 
  457. Dale Worley    Cullinet Software      ARPA: culdev1!drw@eddie.mit.edu
  458. UUCP: ...!seismo!harvard!mit-eddie!culdev1!drw
  459. Nothing shocks me -- I'm a scientist.
  460.