1 /*
2 * X D U . C
3 *
4 * Display the output of "du" in an X window.
5 *
6 * Phillip C. Dykstra
7 * <phil@arl.mil>
8 * 4 Sep 1991.
9 *
10 * Copyright (c) Phillip C. Dykstra 1991, 1993, 1994
11 * The X Consortium, and any party obtaining a copy of these files from
12 * the X Consortium, directly or indirectly, is granted, free of charge, a
13 * full and unrestricted irrevocable, world-wide, paid up, royalty-free,
14 * nonexclusive right and license to deal in this software and
15 * documentation files (the "Software"), including without limitation the
16 * rights to use, copy, modify, merge, publish, distribute, sublicense,
17 * and/or sell copies of the Software, and to permit persons who receive
18 * copies from any such party to do so. This license includes without
19 * limitation a license to do the foregoing actions under any patents of
20 * the party supplying this software to the X Consortium.
21 */
22 #include <stdio.h>
23 #include <string.h>
24 #include <stdlib.h>
25 #include <unistd.h>
26 #include <ctype.h>
27 #include "version.h"
28
29
30 #define MAXDEPTH 80 /* max elements in a path */
31 #define MAXNAME 1024 /* max pathname element length */
32 #define MAXPATH 4096 /* max total pathname length */
33 #define NCOLS 5 /* default number of columns in display */
34
35 /* What we IMPORT from xwin.c */
36 extern int xsetup(), xmainloop(), xdrawrect(), xrepaint();
37
38 /* What we EXPORT to xwin.c */
39 extern int press(), reset(), repaint(), setorder(), reorder();
40 extern nodeinfo(), helpinfo();
41 int ncols = NCOLS;
42
43 /* internal routines */
44 char *strdup();
45 void addtree();
46 void parse_file();
47 void parse_entry();
48 void dumptree();
49 void clearrects();
50 void sorttree();
51
52 /* order to sort paths by */
53 #define ORD_FIRST 1
54 #define ORD_LAST 2
55 #define ORD_ALPHA 3
56 #define ORD_SIZE 4
57 #define ORD_RALPHA 5
58 #define ORD_RSIZE 6
59 #define ORD_DEFAULT ORD_FIRST
60 int order = ORD_DEFAULT;
61
62 /*
63 * Rectangle Structure
64 * Stores window coordinates of a displayed rectangle
65 * so that we can "find" it again on key presses.
66 */
67 struct rect {
68 int left;
69 int top;
70 int width;
71 int height;
72 };
73
74 /*
75 * Node Structure
76 * Each node in the path tree is linked in with one of these.
77 */
78 struct node {
79 char *name;
80 long size; /* from here down in the tree */
81 long num; /* entry number - for resorting */
82 struct rect rect; /* last drawn screen rectangle */
83 struct node *peer; /* siblings */
84 struct node *child; /* list of children if !NULL */
85 struct node *parent; /* backpointer to parent */
86 } top;
87 struct node *topp = ⊤
88 #define NODE_NULL ((struct node *)0)
89 long nnodes = 0;
90
91 /*
92 * create a new node with the given name and size info
93 */
94 struct node *
makenode(name,size)95 makenode(name,size)
96 char *name;
97 int size;
98 {
99 struct node *np;
100
101 np = (struct node *)calloc(1,sizeof(struct node));
102 np->name = strdup(name);
103 np->size = size;
104 np->num = nnodes;
105 nnodes++;
106
107 return np;
108 }
109
110 /*
111 * Return the node (if any) which has a draw rectangle containing
112 * the given x,y point.
113 */
114 struct node *
findnode(treep,x,y)115 findnode(treep, x, y)
116 struct node *treep;
117 int x, y;
118 {
119 struct node *np;
120 struct node *np2;
121
122 if (treep == NODE_NULL)
123 return NODE_NULL;
124
125 if (x >= treep->rect.left && x < treep->rect.left+treep->rect.width
126 && y >= treep->rect.top && y < treep->rect.top+treep->rect.height) {
127 /*printf("found %s\n", treep->name);*/
128 return treep; /* found */
129 }
130
131 /* for each child */
132 for (np = treep->child; np != NULL; np = np->peer) {
133 if ((np2 = findnode(np,x,y)) != NODE_NULL)
134 return np2;
135 }
136 return NODE_NULL;
137 }
138
139 /*
140 * return a count of the number of children of a given node
141 */
142 int
numchildren(nodep)143 numchildren(nodep)
144 struct node *nodep;
145 {
146 int n;
147
148 if (nodep == NODE_NULL)
149 return 0;
150
151 n = 0;
152 for (nodep = nodep->child; nodep != NODE_NULL; nodep=nodep->peer)
153 n++;
154
155 return n;
156 }
157
158 /*
159 * fix_tree - This function repairs the tree when certain nodes haven't
160 * had their sizes initialized. [DPT911113]
161 * * * * This function is recursive * * *
162 */
163 long
fix_tree(top)164 fix_tree(top)
165 struct node *top;
166 {
167 struct node *nd;
168
169 if (top == NODE_NULL) /* recursion end conditions */
170 return 0;
171 if (top->size >= 0) /* also halt recursion on valid size */
172 return top->size; /* (remember: sizes init. to -1) */
173
174 top->size = 0;
175 for (nd = top->child; nd != NODE_NULL; nd = nd->peer)
176 top->size += fix_tree(nd);
177
178 return top->size;
179 }
180
181 static char usage[] = "\
182 Usage: xdu [-options ...] filename\n\
183 or xdu [-options ...] < du.out\n\
184 \n\
185 Graphically displays the output of du in an X window\n\
186 options include:\n\
187 -s Don't display size information\n\
188 +s Display size information (default)\n\
189 -n Sort in numerical order (largest first)\n\
190 -rn Sort in reverse numerical order\n\
191 -a Sort in alphabetical order\n\
192 -ra Sort in reverse alphabetical order\n\
193 -c num Set number of columns to num\n\
194 Toolkit options: -fg, -bg, -rv, -display, -geometry, etc.\n\
195 ";
196
main(argc,argv)197 main(argc,argv)
198 int argc;
199 char **argv;
200 {
201 top.name = strdup("[root]");
202 top.size = -1;
203
204 xsetup(&argc,argv);
205 if (argc == 1) {
206 if (isatty(fileno(stdin))) {
207 fprintf(stderr, usage);
208 exit(1);
209 } else {
210 parse_file("-");
211 }
212 } else if (argc == 2 && strcmp(argv[1],"-help") != 0) {
213 parse_file(argv[1]);
214 } else {
215 fprintf(stderr, usage);
216 exit(1);
217 }
218 top.size = fix_tree(&top);
219
220 /*dumptree(&top,0);*/
221 if (order != ORD_DEFAULT)
222 sorttree(&top, order);
223
224 topp = ⊤
225 /* don't display root if only one child */
226 if (numchildren(topp) == 1)
227 topp = topp->child;
228
229 xmainloop();
230 exit(0);
231 }
232
233 void
parse_file(filename)234 parse_file(filename)
235 char *filename;
236 {
237 char buf[4096];
238 char name[4096];
239 int size;
240 FILE *fp;
241 char *p, *n;
242
243 if (strcmp(filename, "-") == 0) {
244 fp = stdin;
245 } else {
246 if ((fp = fopen(filename, "r")) == 0) {
247 fprintf(stderr, "xdu: can't open \"%s\"\n", filename);
248 exit(1);
249 }
250 }
251
252 while (fgets(buf,sizeof(buf),fp) != NULL) {
253 p = buf;
254 while (*p && isspace(*p)) p++;
255 size = atoi(p);
256 while (*p && !isspace(*p)) p++;
257 while (*p && isspace(*p)) p++;
258 n = name;
259 while (*p && *p != '\n' && *p != '\r')
260 *n++ = *p++;
261 *n++ = '\0';
262 /*printf("%d %s\n", size, name);*/
263 parse_entry(name,size);
264 }
265
266 fclose(fp);
267 }
268
269 /* bust up a path string and link it into the tree */
270 void
parse_entry(name,size)271 parse_entry(name,size)
272 char *name;
273 int size;
274 {
275 char *path[MAXDEPTH]; /* break up path into this list */
276 char buf[MAXNAME]; /* temp space for path element name */
277 int arg, indx;
278 int length; /* nelson@reed.edu - trailing / fix */
279
280 if (*name == '/')
281 name++; /* skip leading / */
282
283 length = strlen(name);
284 if ((length > 0) && (name[length-1] == '/')) {
285 /* strip off trailing / (e.g. GNU du) */
286 name[--length] = 0;
287 }
288
289 arg = 0; indx = 0;
290 bzero(path,sizeof(path));
291 bzero(buf,sizeof(buf));
292 while (*name != NULL) {
293 if (*name == '/') {
294 buf[indx] = 0;
295 path[arg++] = strdup(buf);
296 indx = 0;
297 if (arg >= MAXDEPTH)
298 break;
299 } else {
300 buf[indx++] = *name;
301 if (indx >= MAXNAME)
302 break;
303 }
304 name++;
305 }
306 if (length) {
307 buf[indx] = 0;
308 path[arg++] = strdup(buf);
309 }
310 path[arg] = NULL;
311
312 addtree(&top,path,size);
313 }
314
315 /*
316 * Determine where n1 should go compared to n2
317 * based on the current sorting order.
318 * Return -1 if is should be before.
319 * 0 if it is a toss up.
320 * 1 if it should go after.
321 */
322 int
compare(n1,n2,order)323 compare(n1,n2,order)
324 struct node *n1, *n2;
325 int order;
326 {
327 int ret;
328
329 switch (order) {
330 case ORD_SIZE:
331 ret = n2->size - n1->size;
332 if (ret == 0)
333 return strcmp(n1->name,n2->name);
334 else
335 return ret;
336 break;
337 case ORD_RSIZE:
338 ret = n1->size - n2->size;
339 if (ret == 0)
340 return strcmp(n1->name,n2->name);
341 else
342 return ret;
343 break;
344 case ORD_ALPHA:
345 return strcmp(n1->name,n2->name);
346 break;
347 case ORD_RALPHA:
348 return strcmp(n2->name,n1->name);
349 break;
350 case ORD_FIRST:
351 /*return -1;*/
352 return (n1->num - n2->num);
353 break;
354 case ORD_LAST:
355 /*return 1;*/
356 return (n2->num - n1->num);
357 break;
358 }
359
360 /* shouldn't get here */
361 fprintf(stderr,"xdu: bad insertion order\n");
362 return 0;
363 }
364
365 void
insertchild(nodep,childp,order)366 insertchild(nodep,childp,order)
367 struct node *nodep; /* parent */
368 struct node *childp; /* child to be added */
369 int order; /* FIRST, LAST, ALPHA, SIZE */
370 {
371 struct node *np, *np1;
372
373 if (nodep == NODE_NULL || childp == NODE_NULL)
374 return;
375 if (childp->peer != NODE_NULL) {
376 fprintf(stderr, "xdu: can't insert child with peers\n");
377 return;
378 }
379
380 childp->parent = nodep;
381 if (nodep->child == NODE_NULL) {
382 /* no children, order doesn't matter */
383 nodep->child = childp;
384 return;
385 }
386 /* nodep has at least one child already */
387 if (compare(childp,nodep->child,order) < 0) {
388 /* new first child */
389 childp->peer = nodep->child;
390 nodep->child = childp;
391 return;
392 }
393 np1 = nodep->child;
394 for (np = np1->peer; np != NODE_NULL; np = np->peer) {
395 if (compare(childp,np,order) < 0) {
396 /* insert between np1 and np */
397 childp->peer = np;
398 np1->peer = childp;
399 return;
400 }
401 np1 = np;
402 }
403 /* at end, link new child on */
404 np1->peer = childp;
405 }
406
407 /* add path as a child of top - recursively */
408 void
addtree(top,path,size)409 addtree(top, path, size)
410 struct node *top;
411 char *path[];
412 int size;
413 {
414 struct node *np;
415
416 /*printf("addtree(\"%s\",\"%s\",%d)\n", top->name, path[0], size);*/
417
418 if (path[0] == NULL) {
419 /* end of the chain, save size */
420 top->size = size;
421 return;
422 }
423
424 /* check all children for a match */
425 for (np = top->child; np != NULL; np = np->peer) {
426 if (strcmp(path[0],np->name) == 0) {
427 /* recurse */
428 addtree(np,&path[1],size);
429 return;
430 }
431 }
432 /* no child matched, add a new child */
433 np = makenode(path[0],-1);
434 insertchild(top,np,order);
435
436 if (path[1] == NULL) {
437 /* end of the chain, save size */
438 np->size = size;
439 return;
440 }
441 /* recurse */
442 addtree(np,&path[1],size);
443 return;
444 }
445
446 /* debug tree print */
447 void
dumptree(np,level)448 dumptree(np,level)
449 struct node *np;
450 int level;
451 {
452 int i;
453 struct node *subnp;
454
455 for (i = 0; i < level; i++)
456 printf(" ");
457
458 printf("%s %d\n", np->name, np->size);
459 for (subnp = np->child; subnp != NULL; subnp = subnp->peer) {
460 dumptree(subnp,level+1);
461 }
462 }
463
464 void
sorttree(np,order)465 sorttree(np, order)
466 struct node *np;
467 int order;
468 {
469 struct node *subnp;
470 struct node *np0, *np1, *np2, *np3;
471
472 /* sort the trees of each of this nodes children */
473 for (subnp = np->child; subnp != NODE_NULL; subnp = subnp->peer) {
474 sorttree(subnp, order);
475 }
476 /* then put the given nodes children in order */
477 np0 = np; /* np0 points to node before np1 */
478 for (np1 = np->child; np1 != NODE_NULL; np1 = np1->peer) {
479 np2 = np1; /* np2 points to node before np3 */
480 for (np3 = np1->peer; np3 != NODE_NULL; np3 = np3->peer) {
481 if (compare(np3,np1,order) < 0) {
482 /* swap links */
483 if (np0 == np)
484 np0->child = np3;
485 else
486 np0->peer = np3;
487 np2->peer = np3->peer;
488 np3->peer = np1;
489
490 /* adjust pointers */
491 np1 = np3;
492 np3 = np2;
493 }
494 np2 = np3;
495 }
496 np0 = np1;
497 }
498 }
499
500 /*
501 * Draws a node in the given rectangle, and all of its children
502 * to the "right" of the given rectangle.
503 */
504 drawnode(nodep, rect)
505 struct node *nodep; /* node whose children we should draw */
506 struct rect rect; /* rectangle to draw all children in */
507 {
508 struct rect subrect;
509
510 /*printf("Drawing \"%s\" %d\n", nodep->name, nodep->size);*/
511
512 xdrawrect(nodep->name, nodep->size,
513 rect.left,rect.top,rect.width,rect.height);
514
515 /* save current screen rectangle for lookups */
516 nodep->rect.left = rect.left;
517 nodep->rect.top = rect.top;
518 nodep->rect.width = rect.width;
519 nodep->rect.height = rect.height;
520
521 /* draw children in subrectangle */
522 subrect.left = rect.left+rect.width;
523 subrect.top = rect.top;
524 subrect.width = rect.width;
525 subrect.height = rect.height;
526 drawchildren(nodep, subrect);
527 }
528
529 /*
530 * Draws all children of a node within the given rectangle.
531 * Recurses on children.
532 */
533 drawchildren(nodep, rect)
534 struct node *nodep; /* node whose children we should draw */
535 struct rect rect; /* rectangle to draw all children in */
536 {
537 int totalsize;
538 int totalheight;
539 struct node *np;
540 double fractsize;
541 int height;
542 int top;
543
544 /*printf("Drawing children of \"%s\", %d\n", nodep->name, nodep->size);*/
545 /*printf("In [%d,%d,%d,%d]\n", rect.left,rect.top,rect.width,rect.height);*/
546
547 top = rect.top;
548 totalheight = rect.height;
549 totalsize = nodep->size;
550 if (totalsize == 0) {
551 /* total the sizes of the children */
552 totalsize = 0;
553 for (np = nodep->child; np != NULL; np = np->peer)
554 totalsize += np->size;
555 nodep->size = totalsize;
556 }
557
558 /* for each child */
559 for (np = nodep->child; np != NULL; np = np->peer) {
560 fractsize = np->size / (double)totalsize;
561 height = fractsize * totalheight + 0.5;
562 if (height > 1) {
563 struct rect subrect;
564 /*printf("%s, drawrect[%d,%d,%d,%d]\n", np->name,
565 rect.left,top,rect.width,height);*/
566 xdrawrect(np->name, np->size,
567 rect.left,top,rect.width,height);
568
569 /* save current screen rectangle for lookups */
570 np->rect.left = rect.left;
571 np->rect.top = top;
572 np->rect.width = rect.width;
573 np->rect.height = height;
574
575 /* draw children in subrectangle */
576 subrect.left = rect.left+rect.width;
577 subrect.top = top;
578 subrect.width = rect.width;
579 subrect.height = height;
580 drawchildren(np, subrect);
581
582 top += height;
583 }
584 }
585 }
586
587 /*
588 * clear the rectangle information of a given node
589 * and all of its decendents
590 */
591 void
clearrects(nodep)592 clearrects(nodep)
593 struct node *nodep;
594 {
595 struct node *np;
596
597 if (nodep == NODE_NULL)
598 return;
599
600 nodep->rect.left = 0;
601 nodep->rect.top = 0;
602 nodep->rect.width = 0;
603 nodep->rect.height = 0;
604
605 /* for each child */
606 for (np = nodep->child; np != NULL; np = np->peer) {
607 clearrects(np);
608 }
609 }
610
pwd()611 pwd()
612 {
613 struct node *np;
614 struct node *stack[MAXDEPTH];
615 int num = 0;
616 struct node *rootp;
617 char path[MAXPATH];
618
619 rootp = ⊤
620 if (numchildren(rootp) == 1)
621 rootp = rootp->child;
622
623 np = topp;
624 while (np != NODE_NULL) {
625 stack[num++] = np;
626 if (np == rootp)
627 break;
628 np = np->parent;
629 }
630
631 path[0] = '\0';
632 while (--num >= 0) {
633 strcat(path,stack[num]->name);
634 if (num != 0)
635 strcat(path,"/");
636 }
637 printf("%s %d (%.2f%%)\n", path, topp->size,
638 100.0*topp->size/rootp->size);
639 }
640 /*
641 char *
642 strdup(s)
643 char *s;
644 {
645 int n;
646 char *cp;
647
648 n = strlen(s);
649 cp = malloc(n+1);
650 strcpy(cp,s);
651
652 return cp;
653 }
654 */
655 /**************** External Entry Points ****************/
656
657 int
press(x,y)658 press(x,y)
659 int x, y;
660 {
661 struct node *np;
662
663 /*printf("press(%d,%d)...\n",x,y);*/
664 np = findnode(&top,x,y);
665 /*printf("Found \"%s\"\n", np?np->name:"(null)");*/
666 if (np == topp) {
667 /* already top, go up if possible */
668 if (np->parent != &top || numchildren(&top) != 1)
669 np = np->parent;
670 /*printf("Already top, parent = \"%s\"\n", np?np->name:"(null)");*/
671 }
672 if (np != NODE_NULL) {
673 topp = np;
674 xrepaint();
675 }
676 }
677
678 int
reset()679 reset()
680 {
681 topp = ⊤
682 if (numchildren(topp) == 1)
683 topp = topp->child;
684 xrepaint();
685 }
686
687 int
repaint(width,height)688 repaint(width,height)
689 int width, height;
690 {
691 struct rect rect;
692
693 /* define a rectangle to draw into */
694 rect.top = 0;
695 rect.left = 0;
696 rect.width = width/ncols;
697 rect.height = height;
698
699 clearrects(&top); /* clear current rectangle info */
700 drawnode(topp,rect); /* draw tree into given rectangle */
701 #if 0
702 pwd(); /* display current path */
703 #endif
704 }
705
706 int
setorder(op)707 setorder(op)
708 char *op;
709 {
710 if (strcmp(op, "size") == 0) {
711 order = ORD_SIZE;
712 } else if (strcmp(op, "rsize") == 0) {
713 order = ORD_RSIZE;
714 } else if (strcmp(op, "alpha") == 0) {
715 order = ORD_ALPHA;
716 } else if (strcmp(op, "ralpha") == 0) {
717 order = ORD_RALPHA;
718 } else if (strcmp(op, "first") == 0) {
719 order = ORD_FIRST;
720 } else if (strcmp(op, "last") == 0) {
721 order = ORD_LAST;
722 } else if (strcmp(op, "reverse") == 0) {
723 switch (order) {
724 case ORD_ALPHA:
725 order = ORD_RALPHA;
726 break;
727 case ORD_RALPHA:
728 order = ORD_ALPHA;
729 break;
730 case ORD_SIZE:
731 order = ORD_RSIZE;
732 break;
733 case ORD_RSIZE:
734 order = ORD_SIZE;
735 break;
736 case ORD_FIRST:
737 order = ORD_LAST;
738 break;
739 case ORD_LAST:
740 order = ORD_FIRST;
741 break;
742 }
743 } else {
744 fprintf(stderr, "xdu: bad order \"%s\"\n", op);
745 }
746 }
747
748 int
reorder(op)749 reorder(op)
750 char *op; /* order name */
751 {
752 setorder(op);
753 sorttree(topp, order);
754 xrepaint();
755 }
756
757 int
nodeinfo()758 nodeinfo()
759 {
760 struct node *np;
761
762 /* display current root path */
763 pwd();
764
765 /* display each child of this node */
766 for (np = topp->child; np != NULL; np = np->peer) {
767 printf("%-8d %s\n", np->size, np->name);
768 }
769 }
770
771 int
helpinfo()772 helpinfo()
773 {
774 fprintf(stdout, "\n\
775 XDU Version %s - Keyboard Commands\n\
776 a sort alphabetically\n\
777 n sort numerically (largest first)\n\
778 f sort first-in-first-out\n\
779 l sort last-in-first-out\n\
780 r reverse sort\n\
781 / goto the root\n\
782 q quit (also Escape)\n\
783 i info to standard out\n\
784 0-9 set number of columns (0=10)\n\
785 ", XDU_VERSION);
786 }
787