home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / misc / volume39 / enh-du2 / part02 / dusort.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-08-21  |  7.5 KB  |  352 lines
  1. /* @(#) dusort.c 1.7 93/08/18 00:09:05
  2.  *
  3.  * disk usage sorter
  4.  *
  5.  * Copyright 1990-1992, Unicom Systems Development.  All rights reserved.
  6.  * See accompanying README file for terms of distribution and use.
  7.  *
  8.  * Edit at tabstops=4.
  9.  *
  10.  * This filter reads the output from "du", builds a tree representing
  11.  * the directories scanned, sorts the nodes in descending order, and
  12.  * traverses the tree, thus yielding a printout of disk usage sorted
  13.  * within directories.
  14.  */
  15.  
  16. #include "config.h"
  17. #include <stdio.h>
  18. #include <stdlib.h>
  19. #include <ctype.h>
  20. #include <string.h>
  21.  
  22. #define USAGE        "usage: %s [-t threshold] [file]\n"
  23. #define INDENT        4
  24. #define LISTINCR    16
  25. #define TRUE        1
  26. #define FALSE        0
  27.  
  28. /*
  29.  * The disk usage information is loaded into a tree structure.  Each node
  30.  * of the tree is a (struct duentry), and corresponds to one component
  31.  * in a pathname.  If the node represents a directory, its contents (both
  32.  * files and subdirectories) will be stored in the "child[]" list.  The
  33.  * disk usage at this entry will be saved into "size", or set to -1 if
  34.  * no disk usage info exists at this entry.  Only those entries with a
  35.  * nonnegative "size" value will be printed in the final report.
  36.  */
  37. struct duentry {
  38.     char *name;                /* pathname component at this node            */
  39.     long size;                /* usage size info, or -1 if not available    */
  40.     struct duentry **child;    /* directory contents                        */
  41.     int ch_alloc;            /* allocated size of "child" array            */
  42.     int ch_size;            /* number of elements used in "child" array    */
  43.     short leading_slash;    /* is there a "/" before the name component    */
  44. };
  45.  
  46. /*
  47.  * Only save off entries whose disk usage exceeds this threshold.
  48.  */
  49. long Threshold;
  50.  
  51.  
  52. struct duentry *make_entry();    /* allocate a node to be placed in the tree    */
  53. struct duentry *find_entry();    /* search directory for an entry            */
  54. struct duentry *attach_entry();    /* add entry as child to current directory    */
  55. void sort_tree();                /* sort tree in descending order            */
  56. void print_tree();                /* pre-order traversal of the tree            */
  57. char *xstrdup();
  58. PTRTYPE *xmalloc();
  59. PTRTYPE *xrealloc();
  60.  
  61.  
  62. main(argc, argv)
  63. int argc;
  64. char *argv[];
  65. {
  66.     char buf[1024], *fname, *last_field, *bufp, *s;
  67.     int lineno, leading_slash, i;
  68.     long size;
  69.     struct duentry *du_root, *p, *p1;
  70.     extern int optind;
  71.     extern char *optarg;
  72.  
  73.     /*
  74.      * Initialize.
  75.      */
  76.     Threshold = 0L;
  77.     du_root = make_entry("", FALSE);
  78.  
  79.     /*
  80.      * Crack command line.
  81.      */
  82.     while ((i = getopt(argc, argv, "t:")) != EOF) {
  83.         switch (i) {
  84.         case 't':
  85.             if ((Threshold=atol(optarg)) <= 0L && strcmp(optarg, "0") != 0) {
  86.                 fprintf(stderr, "%s: bad threshold value \"%s\"\n",
  87.                     argv[0], optarg);
  88.                 exit(1);
  89.             }
  90.             break;
  91.         default:
  92.             fprintf(stderr, USAGE, argv[0]);
  93.             exit(1);
  94.         }
  95.     }
  96.  
  97.     /*
  98.      * Figure out where input is coming from.
  99.      */
  100.     switch (argc-optind) {
  101.     case 1:
  102.         fname = argv[optind];
  103.         if (freopen(fname, "r", stdin) == NULL) {
  104.             perror(fname);
  105.             exit(1);
  106.         }
  107.         break;
  108.     case 0:
  109.         /* read from stdin */
  110.         fname = "<stdin>";
  111.         break;
  112.     default:
  113.         fprintf(stderr, USAGE, argv[0]);
  114.         exit(1);
  115.     }
  116.  
  117.     /*
  118.      * Read in the input data.  It is expected to be in a format:
  119.      *
  120.      *        size   ....   pathname
  121.      */
  122.     lineno = 0;
  123.     while (++lineno, fgets(buf, sizeof(buf), stdin) != NULL) {
  124.  
  125.         /*
  126.          * Break the line up into fields.  Save the first field as the size.
  127.          */
  128.         s = NULL;
  129.         bufp = buf;
  130.         i = 0;
  131.         while (last_field = s, (s = strtok(bufp, " \t\n")) != NULL) {
  132.             bufp = NULL;
  133.             if (i++ == 0)
  134.                 size = atol(s);
  135.         }
  136.         if (i < 2) {
  137.             fprintf(stderr, "%s(%d): line ignored\n", fname, lineno);
  138.             continue;
  139.         }
  140.  
  141.         /*
  142.          * Ignore this entry if it is smaller than what we want.
  143.          */
  144.         if (size < Threshold)
  145.             continue;
  146.  
  147.         /*
  148.          * Break the pathname into components, and descend down
  149.          * into the tree, creating nodes as required.
  150.          */
  151.         leading_slash = (*last_field == '/');
  152.         p = du_root;
  153.         while ((s = strtok(last_field, "/")) != NULL) {
  154.             if ((p1 = find_entry(p, s)) == NULL)
  155.                 p1 = attach_entry(p, make_entry(s, leading_slash));
  156.             last_field = NULL;
  157.             leading_slash = TRUE;
  158.             p = p1;
  159.         }
  160.  
  161.         /*
  162.          * Save disk usage for this entry in last component of the path.
  163.          */
  164.         p->size = size;
  165.  
  166.     }
  167.  
  168.     /*
  169.      * Sort and traverse the tree.
  170.      */
  171.     sort_tree(du_root);
  172.     buf[0] = '\0';
  173.     print_tree(du_root, buf, buf, 0);
  174.  
  175.     exit(0);
  176.     /*NOTREACHED*/
  177. }
  178.  
  179.  
  180. /*
  181.  * Allocate a new node for the tree.
  182.  */
  183. struct duentry *make_entry(name, leading_slash)
  184. register char *name;
  185. int leading_slash;
  186. {
  187.     register struct duentry *p;
  188.     p = (struct duentry *) xmalloc(sizeof(struct duentry));
  189.     p->name = xstrdup(name);
  190.     p->size = -1L;
  191.     p->child = (struct duentry **) NULL;
  192.     p->ch_alloc = 0;
  193.     p->ch_size = 0;
  194.     p->leading_slash = (short) leading_slash;
  195.     return p;
  196. }
  197.  
  198.  
  199. /*
  200.  * Search a directory entry for a member entry and return a pointer to
  201.  * the located entry.  If not found, add this member to the directory.
  202.  */
  203. struct duentry *find_entry(p, name)
  204. register struct duentry *p;
  205. register char *name;
  206. {
  207.     register int i;
  208.  
  209.     for (i = 0 ; i < p->ch_size ; ++i) {
  210.         if (strcmp(name, p->child[i]->name) == 0)
  211.             return p->child[i];
  212.     }
  213.     return (struct duentry *) NULL;
  214. }
  215.  
  216.  
  217. /*
  218.  * Add a new child at the current node.
  219.  */
  220. struct duentry *attach_entry(p, pchild)
  221. register struct duentry *p, *pchild;
  222. {
  223.     if (p->ch_size >= p->ch_alloc) {
  224.         p->ch_alloc += LISTINCR;
  225.         p->child = (struct duentry **) xrealloc((PTRTYPE *)p->child,
  226.             p->ch_alloc*sizeof(struct duentry *));
  227.     }
  228.     p->child[p->ch_size++] = pchild;
  229.     return pchild;
  230. }
  231.  
  232.  
  233. /*
  234.  * Recursively sort the tree so that the nodes in "child[]" are in
  235.  * descending order by disk usage.  This is done as a selection sort.
  236.  */
  237. void sort_tree(p)
  238. struct duentry *p;
  239. {
  240.     int i, j, m;
  241.     long msize;
  242.     struct duentry *t;
  243.  
  244.     /*
  245.      * Selection sort.
  246.      */
  247.     for (i = 0 ; i < p->ch_size ; ++i) {
  248.         /*
  249.          * INVARIANT: child[0:i-1] is sorted in descending order.
  250.          * child[x] > child[y] for all x < y && x < i.
  251.          */
  252.         m = i;
  253.         msize = p->child[i]->size;
  254.         for (j = i+1 ; j < p->ch_size ; ++j) {
  255.             /*
  256.              * INVARIANT: child[m] is the maximum in the range child[i:j-1]
  257.              */
  258.             if (p->child[j]->size > msize) {
  259.                 m = j;
  260.                 msize = p->child[j]->size;
  261.             }
  262.         }
  263.         /*
  264.          * RESULT: child[m] is the maximum in the range [i:ch_size-1]
  265.          */
  266.         if (m != i) {
  267.             t = p->child[m];
  268.             p->child[m] = p->child[i];
  269.             p->child[i] = t;
  270.         }
  271.         /*
  272.          * RESULT: child[0:i] is sorted,
  273.          * child[x] > child[y] for all x < y && x < i+1.
  274.          */
  275.         sort_tree(p->child[i]);
  276.     }
  277. }
  278.  
  279.  
  280. /*
  281.  * Perform a preorder traversal of the tree to get a sorted report.
  282.  */
  283. void print_tree(p, buf, bufend, lvl)
  284. struct duentry *p;
  285. char *buf, *bufend;
  286. int lvl;
  287. {
  288.     int i;
  289.     char *s;
  290.  
  291.     /*
  292.      * Append this entry to the pathname.
  293.      */
  294.     if (p->leading_slash)
  295.         *bufend++ = '/';
  296.     for (s = p->name ; *s != '\0' ; )
  297.         *bufend++ = *s++;
  298.     *bufend = '\0';
  299.  
  300.     /*
  301.      * If there is a size at this entry then display it.
  302.      */
  303.     if (p->size >= 0) {
  304.         printf("%ld\t%*s%s\n", p->size, INDENT*lvl, "",
  305.             (buf[0] == '\0' ? "/" : buf));
  306.         ++lvl;
  307.     }
  308.  
  309.     /*
  310.      * Recurse into the children of this entry.
  311.      */
  312.     for (i = 0 ; i < p->ch_size ; ++i)
  313.         print_tree(p->child[i], buf, bufend, lvl);
  314. }
  315.  
  316.  
  317. static char malloc_error[] = "error - out of memory [malloc failed]\n";
  318.  
  319. char *xstrdup(s)
  320. register char *s;
  321. {
  322.     register char *s1;
  323.     if ((s1 = (char *) malloc((unsigned)strlen(s)+1)) == NULL) {
  324.         fputs(malloc_error, stderr);
  325.         exit(1);
  326.     }
  327.     return strcpy(s1, s);
  328. }
  329.  
  330. PTRTYPE *xmalloc(n)
  331. register unsigned n;
  332. {
  333.     register PTRTYPE *s;
  334.     if ((s = malloc(n)) == NULL) {
  335.         fputs(malloc_error, stderr);
  336.         exit(1);
  337.     }
  338.     return s;
  339. }
  340.  
  341. PTRTYPE *xrealloc(s, n)
  342. register PTRTYPE *s;
  343. register unsigned n;
  344. {
  345.     if ((s = (s == NULL ? malloc(n) : realloc(s, n))) == NULL) {
  346.         fputs(malloc_error, stderr);
  347.         exit(1);
  348.     }
  349.     return s;
  350. }
  351.  
  352.