1\def\covernote{Copyright 1987 Norman Ramsey -- Princeton University} 2 3\def\vbar{\.{|}} 4@*Directory Trees. 5Our object is to print out a directory hierarchy in some pleasant way. 6The program takes output from {\tt find * -type d -print \vbar\ sort} 7@^system dependencies@> 8and produces a nicer-looking listing. 9More precisely, our input, which is the output of {\tt find} followed 10by {\tt sort}, is a list of fully qualified directory names (parent 11and child separated by slashes |'/'|); everything has already been 12sorted nicely into lexicographic order. 13 14The {\tt treeprint} routine takes one option, |"-p"|, which tells it 15to use the printer's line-drawing set, rather than the terminal's. 16 17@c 18@<Global definitions@>@; 19@<Global include files@>@; 20@<Global declarations@>@; 21 22@# 23main(argc, argv) 24 int argc; 25 char **argv; 26{ 27@<|main| variable declarations@>; 28@<Search for options and set special characters on |"-p"|@>; 29@<Read output from find and enter into tree@>; 30@<Write tree on standard output@>@; 31exit(0); 32} 33 34@ 35We make all the siblings of a directory a linked list off of its left child, 36and the offspring a linked list off the right side. 37Data are just directory names. 38@d sibling left 39@d child right 40 41@<Global decl...@>= 42typedef struct tnode { 43 struct tnode *left, *right; 44 char *data; 45} TNODE; 46@ @<|main| variable...@>= 47struct tnode *root=NULL; 48 49 50 51@*Input. 52Reading the tree is simple---we read one line at a time, and call on the 53recursive |add_tree| procedure. 54 55@c 56read_tree (fp, rootptr) 57 FILE *fp; 58 struct tnode **rootptr; 59{ 60 char buf[255], *p; 61 62 while ((fgets(buf, 255, fp))!=NULL) { 63 @<If |buf| contains a newline, make it end there@>; 64 add_tree(rootptr, buf); 65 } 66 } 67@ @<Global include...@>= 68#include <stdio.h> 69 70@ Depending what system you're on, you may or may not get a newline in |buf|. 71@<If |buf| contains a newline...@>= 72 p=buf; while (*p!='\0'&&*p!='\n') p++; 73@^system dependencies@> 74 *p='\0'; 75 76@ 77To add a string, we split off the first part of the name and insert it into 78the sibling list. We then do the rest of the string as a child of the new node. 79 80@c 81add_tree(rootptr, p) 82 struct tnode **rootptr; 83 char *p; 84{ 85 char *s; 86 int slashed; 87 88 if (*p=='\0') return; 89 90@<Break up the string so |p| is the first word, 91 |s| points at null-begun remainder, 92 and |slashed| tells whether |*s=='/'| on entry@>; 93 94 if (*rootptr==NULL) { 95@<Allocate new node to hold string of size |strlen(p)|@>; 96 strcpy((*rootptr)->data,p); 97 } 98 if (strcmp((*rootptr)->data,p)==0) { 99 if (slashed) ++s; 100 add_tree(&((*rootptr)->child),s); 101 } 102 else { 103 if (slashed) *s='/'; 104 add_tree(&((*rootptr)->sibling),p); 105 } 106 } 107 108@ We perform some nonsense to cut off the string |p| so that |p| just 109holds the first word of a multiword name. Variable |s| points at what 110was either the end of |p| or a slash delimiting names. In either case 111|*s| is made |'\0'|. Later, depending on whether we want to pass the 112whole string or the last piece, we will restore the slash or advance 113|s| one character to the right. 114 115@<Break up...@>= 116 for (s=p;*s!='\0'&&*s!='/';) s++; 117 if (*s=='/') { 118 slashed=1; 119 *s='\0'; 120 } else slashed=0; 121 122@ Node allocation is perfectly standard \dots 123@<Allocate new node...@>= 124 *rootptr=(struct tnode *) malloc (sizeof(struct tnode)); 125 (*rootptr)->left = (*rootptr)->right = NULL; 126 (*rootptr)->data = malloc (strlen(p)+1); 127 128@ 129@<Global decl...@>= char *malloc(); 130 131@ In this simple implementation, we just read from standard input. 132@<Read...@>= read_tree(stdin,&root); 133 134@*Output. 135We begin by defining some lines, tees, and corners. 136The |s| stands for screen and the |p| for printer. 137You will have to change this for your line-drawing set. 138@^system dependencies@> 139 140@<Global definitions@>= 141#define svert '|' 142#define shoriz '-' 143#define scross '+' 144#define scorner '\\' /* lower left corner */ 145 146#define pvert '|' 147#define phoriz '-' 148#define pcross '+' 149#define pcorner '\\' /* lower left corner */ 150 151@ The default is to use the terminal's line drawing set. 152@<Global declarations@>= 153char vert=svert; 154char horiz=shoriz; 155char cross=scross; 156char corner=scorner; 157 158@ With option |"-p"| use the printer character set. 159@<Search for options...@>= 160while (--argc>0) { 161 if (**++argv=='-') { 162 switch (*++(*argv)) { 163 case 'p': 164 vert=pvert; 165 horiz=phoriz; 166 cross=pcross; 167 corner=pcorner; 168 break; 169 default: 170 fprintf(stderr,"treeprint: bad option -%c\n",**argv); 171 break; 172 } 173 } 174} 175 176@ We play games with a character stack to figure out when to put in vertical 177bars. 178A vertical bar connects every sibling with its successor, but the last sibling 179in a list is followed by blanks, not by vertical bars. The state of 180bar-ness or space-ness for each preceding sibling is recorded in the 181|indent_string| variable, one character (bar or blank) per sibling. 182 183@<Global decl...@>= 184char indent_string[100]=""; 185 186@ Children get printed 187before siblings. 188We don't bother trying to bring children up to the same line as their parents, 189because the \UNIX/ filenames are so long. 190 191We define a predicate telling us when a sibling is the last in a series. 192@d is_last(S) (S->sibling==NULL) 193 194@c 195print_node(fp, indent_string, node) 196 FILE *fp; 197 char *indent_string; 198 struct tnode *node; 199{ 200 char string[255]; 201 int i; 202 char *p, *is; 203 204 if (node==NULL) { 205 } 206 else { 207 *string='\0'; 208 for (i=strlen(indent_string); i>0; i--) 209 strcat(string,@, " | "); 210 strcat(string,@t\ \ @> " +--"); 211@<Replace chars in |string| with chars from 212 line-drawing set and from |indent_string|@>; 213 fprintf(fp,"%s%s\n",string,node->data); 214 215@# 216 /* Add vertical bar or space for this sibling (claim |*is=='\0'|) */ 217 *is++ = (is_last(node) ? ' ' : vert); 218 *is='\0'; 219 220 print_node(fp, indent_string, node->child); /* extended |indent_string| */ 221 *--is='\0'; 222 print_node(fp, indent_string, node->sibling); /* original |indent_string| */ 223 } 224 225} 226@ For simplicity, we originally wrote connecting lines with |'|'|, |'+'|, and 227|'-'|. 228Now we replace those characters with appropriate characters from the 229line-drawing set. 230We take the early vertical bars and replace them with characters from 231|indent_string|, and we replace the other characters appropriately. 232We are sure to put a |corner|, not a |cross|, on the last sibling in 233a group. 234@<Replace chars...@>= 235 is=indent_string; 236 for (p=string; *p!='\0'; p++) switch(*p) { 237 case '|': *p=*is++; break; 238 case '+': *p=(is_last(node) ? corner : cross); break; 239 case '-': *p=horiz; break; 240 default: break; 241 } 242 243 244@ For this simple implementation, we just write on standard output. 245 246@<Write...@>= print_node(stdout, indent_string, root); 247 248@*Index. 249