1 /* 2 * Copyright (c) 1989 The Regents of the University of California. 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms are permitted 6 * provided that the above copyright notice and this paragraph are 7 * duplicated in all such forms and that any documentation, 8 * advertising materials, and other materials related to such 9 * distribution and use acknowledge that the software was developed 10 * by the University of California, Berkeley. The name of the 11 * University may not be used to endorse or promote products derived 12 * from this software without specific prior written permission. 13 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR 14 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED 15 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. 16 */ 17 18 #if defined(LIBC_SCCS) && !defined(lint) 19 static char sccsid[] = "@(#)fts.c 5.3 (Berkeley) 04/16/90"; 20 #endif /* LIBC_SCCS and not lint */ 21 22 #include <sys/param.h> 23 #include <sys/stat.h> 24 #include <dirent.h> 25 #include <errno.h> 26 #include <fts.h> 27 #include <strings.h> 28 29 extern int errno; 30 31 FTSENT *fts_alloc(), *fts_build(), *fts_cycle(), *fts_sort(), *fts_root(); 32 short fts_stat(); 33 char *malloc(), *realloc(); 34 35 /* 36 * Special case a root of "/" so that slashes aren't appended causing 37 * paths to be written as "//foo". 38 */ 39 #define NAPPEND(p) \ 40 (p->level == ROOTLEVEL && p->pathlen == 1 && \ 41 p->path[0] == '/' ? 0 : p->pathlen) 42 43 #define CHDIR(sp, path) (!(sp->options & FTS_NOCHDIR) && chdir(path)) 44 #define FCHDIR(sp, fd) (!(sp->options & FTS_NOCHDIR) && fchdir(fd)) 45 46 #define ROOTLEVEL 0 47 #define ROOTPARENTLEVEL -1 48 49 static FTS *stream; /* current stream pointer */ 50 51 FTS * 52 ftsopen(argv, options, compar) 53 char *argv[]; 54 register int options; 55 int (*compar)(); 56 { 57 register FTS *sp; 58 register FTSENT *p, *root; 59 register int nitems, maxlen; 60 FTSENT *parent, *tmp; 61 char wd[MAXPATHLEN], *getwd(), *strdup(); 62 63 /* allocate/initialize the stream */ 64 if (!(stream = sp = (FTS *)malloc((u_int)sizeof(FTS)))) 65 return(NULL); 66 bzero(sp, sizeof(FTS)); 67 sp->compar = compar; 68 sp->options = options; 69 70 /* allocate/initialize root's parent */ 71 if (!(parent = fts_alloc("", 0))) 72 goto mem1; 73 parent->level = ROOTPARENTLEVEL; 74 75 /* allocate/initialize root(s) */ 76 if (options & FTS_MULTIPLE) { 77 maxlen = -1; 78 for (root = NULL, nitems = 0; *argv; ++argv, ++nitems) { 79 if (!(p = fts_root(*argv))) 80 goto mem2; 81 if (maxlen < p->namelen) 82 maxlen = p->namelen; 83 /* 84 * if comparison routine supplied, traverse in sorted 85 * order; otherwise traverse in the order specified. 86 */ 87 if (compar) { 88 p->link = root; 89 root = p; 90 p->accpath = p->name; 91 p->info = fts_stat(p, 0); 92 } else { 93 p->link = NULL; 94 if (!root) 95 tmp = root = p; 96 else { 97 tmp->link = p; 98 tmp = p; 99 } 100 } 101 p->level = ROOTLEVEL; 102 p->parent = parent; 103 } 104 if (compar && nitems > 1) 105 root = fts_sort(root, nitems); 106 } else { 107 if (!(root = fts_root((char *)argv))) 108 goto mem2; 109 maxlen = root->namelen; 110 root->link = NULL; 111 root->level = ROOTLEVEL; 112 root->parent = parent; 113 } 114 115 /* start out with at least 1K+ of path space */ 116 if (!fts_path(MAX(maxlen, MAXPATHLEN))) 117 goto mem2; 118 119 /* 120 * some minor trickiness. Set the pointers so that ftsread thinks 121 * we've just finished the node before the root(s); set p->info to 122 * FTS_NS so that everything about the "current" node is ignored. 123 * Rather than allocate a dummy node use the root's parent's link 124 * pointer. This is handled specially in ftsclose() as well. 125 */ 126 sp->cur = parent; 127 parent->link = root; 128 parent->info = FTS_NS; 129 130 /* 131 * if using chdir(2), do a getwd() to insure that we can get back 132 * here; this could be avoided for some paths, but probably not 133 * worth the effort. Slashes, symbolic links, and ".." are all 134 * fairly nasty problems. Note, if we can't get the current 135 * working directory we run anyway, just more slowly. 136 */ 137 if (!(options & FTS_NOCHDIR) && (!getwd(wd) || !(sp->wd = strdup(wd)))) 138 sp->options |= FTS_NOCHDIR; 139 140 return(sp); 141 142 mem2: fts_lfree(root); 143 (void)free((char *)parent); 144 mem1: (void)free((char *)sp); 145 return(NULL); 146 } 147 148 static 149 fts_load(p) 150 register FTSENT *p; 151 { 152 register int len; 153 register char *cp; 154 155 /* 156 * load the stream structure for the next traversal; set the 157 * accpath field specially so the chdir gets done to the right 158 * place and the user can access the first node. 159 */ 160 len = p->pathlen = p->namelen; 161 bcopy(p->name, stream->path, len + 1); 162 if ((cp = rindex(p->name, '/')) && (cp != p->name || cp[1])) { 163 len = strlen(++cp); 164 bcopy(cp, p->name, len + 1); 165 p->namelen = len; 166 } 167 p->accpath = p->path = stream->path; 168 } 169 170 ftsclose(sp) 171 FTS *sp; 172 { 173 register FTSENT *freep, *p; 174 int saved_errno; 175 176 if (sp->cur) 177 /* check for never having read anything */ 178 if (sp->cur->level == ROOTPARENTLEVEL) 179 fts_lfree(sp->cur); 180 else { 181 for (p = sp->cur; p->level > ROOTPARENTLEVEL;) { 182 freep = p; 183 p = p->link ? p->link : p->parent; 184 (void)free((char *)freep); 185 } 186 (void)free((char *)p); 187 } 188 189 /* free up child linked list, sort array, path buffer */ 190 if (sp->child) 191 fts_lfree(sp->child); 192 if (sp->array) 193 (void)free((char *)sp->array); 194 (void)free((char *)sp->path); 195 196 /* 197 * return to original directory, save errno if necessary; 198 * free up the directory buffer 199 */ 200 if (!(sp->options & FTS_NOCHDIR)) { 201 saved_errno = chdir(sp->wd) ? errno : 0; 202 (void)free(sp->wd); 203 } 204 205 /* free up the stream pointer */ 206 (void)free((char *)sp); 207 208 /* set errno and return */ 209 if (!(sp->options & FTS_NOCHDIR) && saved_errno) { 210 errno = saved_errno; 211 return(-1); 212 } 213 return(0); 214 } 215 216 FTSENT * 217 ftsread(sp) 218 register FTS *sp; 219 { 220 register FTSENT *p; 221 register int instr; 222 static int cd; 223 FTSENT *tmp; 224 char *cp; 225 226 /* if finished or unrecoverable error, return NULL */ 227 if (!sp->cur || sp->options & FTS__STOP) 228 return(NULL); 229 230 /* set global stream pointer, and current node pointer */ 231 stream = sp; 232 p = sp->cur; 233 234 /* save and zero out user instructions */ 235 instr = p->instr; 236 p->instr = 0; 237 238 /* if used link pointer for cycle detection, restore it */ 239 if (sp->savelink) { 240 p->link = sp->savelink; 241 sp->savelink = NULL; 242 } 243 244 /* any type of file may be re-visited; re-stat and return */ 245 if (instr == FTS_AGAIN) { 246 p->info = fts_stat(p, 0); 247 return(p); 248 } 249 250 if (p->info == FTS_D) 251 if (instr == FTS_SKIP) { 252 if (sp->child) { 253 fts_lfree(sp->child); 254 sp->child = NULL; 255 } 256 } else { 257 if (!sp->child && (!(sp->child = fts_build(sp, 1)))) 258 return(p); 259 p = sp->child; 260 sp->child = NULL; 261 return(sp->cur = p); 262 } 263 else if (p->info == FTS_SL && instr == FTS_FOLLOW) { 264 p->info = fts_stat(p, 1); 265 return(p); 266 } 267 268 /* 269 * user may have called ftsset on pointer returned by 270 * ftschildren; handle it here. 271 */ 272 for (p = p->link; p;) { 273 instr = p->instr; 274 if (instr == FTS_FOLLOW) { 275 p->info = fts_stat(p, 1); 276 p->instr = 0; 277 break; 278 } 279 if (instr == FTS_SKIP) { 280 tmp = p; 281 p = p->link; 282 (void)free((char *)tmp); 283 continue; 284 } 285 p->instr = 0; 286 break; 287 } 288 289 /* go to next node on this level */ 290 if (p) { 291 /* 292 * if root level node, set up paths and return. If not the 293 * first time, and it's not an absolute pathname, get back 294 * to wherever we started from. 295 */ 296 if (p->level == ROOTLEVEL) { 297 fts_load(p); 298 if (cd) { 299 (void)free((char *)sp->cur); 300 if (p->path[0] != '/' && CHDIR(sp, sp->wd)) { 301 /* return target path for error msg */ 302 p->path = sp->wd; 303 p->info = FTS_ERR; 304 sp->options |= FTS__STOP; 305 return(sp->cur = p); 306 } 307 } else 308 cd = 1; 309 p->info = fts_stat(p, 0); 310 } else { 311 (void)free((char *)sp->cur); 312 cp = sp->path + NAPPEND(p->parent); 313 *cp++ = '/'; 314 bcopy(p->name, cp, p->namelen + 1); 315 if (p->info == FTS_D && (tmp = fts_cycle(p))) { 316 sp->savelink = p->link; 317 p->link = tmp; 318 } 319 } 320 return(sp->cur = p); 321 } 322 323 /* go to parent */ 324 p = sp->cur->parent; 325 (void)free((char *)sp->cur); 326 if (p->level == ROOTPARENTLEVEL) { 327 /* 328 * done; free everything up and set errno to 0 so the user 329 * can distinguish between error and EOF. 330 */ 331 (void)free((char *)p); 332 errno = 0; 333 return(sp->cur = NULL); 334 } 335 336 sp->path[p->pathlen] = '\0'; 337 if (CHDIR(sp, "..")) { 338 sp->options |= FTS__STOP; 339 p->info = FTS_ERR; 340 } else 341 p->info = FTS_DP; 342 return(sp->cur = p); 343 } 344 345 /* 346 * ftsset takes the stream as an argument although it's not used in this 347 * implementation; it would be necessary if anyone wanted to add global 348 * semantics to fts using ftsset. A possible error return is allowed for 349 * similar reasons. 350 */ 351 /* ARGSUSED */ 352 ftsset(sp, p, instr) 353 FTS *sp; 354 FTSENT *p; 355 int instr; 356 { 357 p->instr = instr; 358 return(0); 359 } 360 361 FTSENT * 362 ftschildren(sp) 363 register FTS *sp; 364 { 365 /* 366 * set errno to 0 so that user can tell the difference between an 367 * error and a directory without entries. 368 */ 369 errno = 0; 370 if (sp->cur->info != FTS_D || sp->options & FTS__STOP) 371 return(NULL); 372 if (sp->child) 373 fts_lfree(sp->child); 374 return(sp->child = fts_build(sp, 0)); 375 } 376 377 #define ISDOT(a) (a[0] == '.' && (!a[1] || a[1] == '.' && !a[2])) 378 379 static FTSENT * 380 fts_build(sp, set_node) 381 register FTS *sp; 382 int set_node; 383 { 384 register struct dirent *dp; 385 register FTSENT *p, *head; 386 register int nitems; 387 DIR *dirp; 388 int descend, len, level, maxlen, nlinks, saved_errno; 389 char *cp; 390 391 p = sp->cur; 392 if (!(dirp = opendir(p->accpath))) { 393 if (set_node) { 394 errno = 0; 395 p->info = FTS_DNR; 396 } 397 return(NULL); 398 } 399 400 /* 401 * the real slowdown in walking the tree is the stat calls. If 402 * FTS_NOSTAT is set and it's a physical walk (so that symbolic 403 * links can't be directories), fts assumes that the number of 404 * subdirectories in a node is equal to the number of links to 405 * the parent. This allows stat calls to be skipped in any leaf 406 * directories and for any nodes after the directories in the 407 * parent node have been found. This empirically cuts the stat 408 * calls by about 2/3. 409 */ 410 nlinks = sp->options & FTS_NOSTAT && sp->options & FTS_PHYSICAL ? 411 p->statb.st_nlink - (sp->options & FTS_SEEDOT ? 0 : 2) : -1; 412 413 if (nlinks || set_node) { 414 if (FCHDIR(sp, dirfd(dirp))) { 415 if (set_node) { 416 errno = 0; 417 p->info = FTS_DNX; 418 } 419 return(NULL); 420 } 421 descend = 1; 422 } else 423 descend = 0; 424 425 /* get max file name length that can be stored in current path */ 426 maxlen = sp->pathlen - p->pathlen - 1; 427 428 cp = sp->path + (len = NAPPEND(p)); 429 *cp++ = '/'; 430 431 level = p->level + 1; 432 433 /* read the directory, attching each new entry to the `link' pointer */ 434 for (head = NULL, nitems = 0; dp = readdir(dirp);) { 435 if (ISDOT(dp->d_name) && !(sp->options & FTS_SEEDOT)) 436 continue; 437 438 if (!(p = fts_alloc(dp->d_name, dp->d_namlen))) { 439 saved_errno = errno; 440 goto mem1; 441 } 442 if (dp->d_namlen > maxlen) { 443 if (!fts_path((int)dp->d_namlen)) { 444 /* quit: this stream no longer has a path */ 445 sp->options |= FTS__STOP; 446 saved_errno = errno; 447 (void)free((char *)p); 448 mem1: fts_lfree(head); 449 if (set_node) 450 p->info = FTS_ERR; 451 if (descend && CHDIR(sp, "..")) { 452 saved_errno = errno; 453 sp->options |= FTS__STOP; 454 } 455 errno = saved_errno; 456 return(NULL); 457 } 458 maxlen = sp->pathlen - sp->cur->pathlen - 1; 459 } 460 461 p->pathlen = len + dp->d_namlen + 1; 462 p->accpath = sp->options & FTS_NOCHDIR ? p->path : p->name; 463 464 p->parent = sp->cur; 465 p->level = level; 466 467 if (nlinks) { 468 /* make sure fts_stat has a filename to stat */ 469 if (sp->options & FTS_NOCHDIR) 470 bcopy(p->name, cp, p->namelen + 1); 471 p->info = fts_stat(p, 0); 472 if (nlinks > 0 && (p->info == FTS_D || 473 p->info == FTS_DNR || p->info == FTS_DNX)) 474 --nlinks; 475 } else 476 p->info = FTS_NS; 477 478 p->link = head; 479 head = p; 480 ++nitems; 481 } 482 (void)closedir(dirp); 483 484 if (descend && (!nitems || !set_node) && CHDIR(sp, "..")) { 485 sp->options |= FTS__STOP; 486 p->info = FTS_ERR; 487 *--cp = '\0'; 488 return(NULL); 489 } 490 491 if (!nitems) { 492 if (set_node) 493 p->info = FTS_DP; 494 *--cp = '\0'; 495 return(NULL); 496 } 497 498 if (sp->compar && nitems > 1) 499 head = fts_sort(head, nitems); 500 501 if (set_node) 502 bcopy(head->name, cp, head->namelen + 1); 503 else 504 *--cp = '\0'; 505 return(head); 506 } 507 508 static short 509 fts_stat(p, symflag) 510 register FTSENT *p; 511 int symflag; 512 { 513 /* 514 * detection of symbolic links w/o targets. If FTS_FOLLOW is set, 515 * the symlink structure is overwritten with the stat structure of 516 * the target. 517 */ 518 if (stream->options & FTS_LOGICAL || symflag) { 519 if (stat(p->accpath, &p->statb)) 520 return(symflag || !lstat(p->accpath, &p->statb) ? 521 FTS_SLNONE : FTS_ERR); 522 } else if (lstat(p->accpath, &p->statb)) 523 return(FTS_ERR); 524 525 switch(p->statb.st_mode&S_IFMT) { 526 case S_IFDIR: 527 return(FTS_D); 528 case S_IFLNK: 529 return(FTS_SL); 530 case S_IFREG: 531 return(FTS_F); 532 } 533 return(FTS_DEFAULT); 534 } 535 536 static FTSENT * 537 fts_cycle(p) 538 register FTSENT *p; 539 { 540 register dev_t dev; 541 register ino_t ino; 542 543 /* 544 * cycle detection is brute force; if the tree gets deep enough or 545 * the number of symbolic links to directories is really high 546 * something faster might be worthwhile. 547 */ 548 dev = p->statb.st_dev; 549 ino = p->statb.st_ino; 550 for (p = p->parent; p->level > ROOTLEVEL; p = p->parent) 551 if (ino == p->statb.st_ino && dev == p->statb.st_dev) 552 return(p); 553 return(NULL); 554 } 555 556 #define R(type, nelem, ptr) \ 557 (type *)realloc((char *)ptr, (u_int)((nelem) * sizeof(type))) 558 559 static FTSENT * 560 fts_sort(head, nitems) 561 FTSENT *head; 562 register int nitems; 563 { 564 register FTSENT **ap, *p; 565 566 /* 567 * construct an array of pointers to the structures and call qsort(3). 568 * Reassemble the array in the order returned by qsort. If unable to 569 * sort for memory reasons, return the directory entries in their 570 * current order. Allocate enough space for the current needs plus 571 * 40 so we don't realloc one entry at a time. 572 */ 573 if (nitems > stream->nitems) { 574 stream->nitems = nitems + 40; 575 if (!(stream->array = 576 R(FTSENT *, stream->nitems, stream->array))) { 577 stream->nitems = 0; 578 return(head); 579 } 580 } 581 for (ap = stream->array, p = head; p; p = p->link) 582 *ap++ = p; 583 qsort((char *)stream->array, nitems, sizeof(FTSENT *), stream->compar); 584 for (head = *(ap = stream->array); --nitems; ++ap) 585 ap[0]->link = ap[1]; 586 ap[0]->link = NULL; 587 return(head); 588 } 589 590 static FTSENT * 591 fts_alloc(name, len) 592 char *name; 593 register int len; 594 { 595 register FTSENT *p; 596 597 /* 598 * variable sized structures; the name is the last element so 599 * allocate enough extra space after the structure to hold it. 600 */ 601 if (!(p = (FTSENT *)malloc((u_int)(sizeof(FTSENT) + len)))) 602 return(NULL); 603 bcopy(name, p->name, len + 1); 604 p->namelen = len; 605 p->path = stream->path; 606 p->instr = 0; 607 p->local.number = 0; 608 p->local.pointer = NULL; 609 return(p); 610 } 611 612 static 613 fts_lfree(head) 614 register FTSENT *head; 615 { 616 register FTSENT *p; 617 618 while (p = head) { 619 head = head->link; 620 (void)free((char *)p); 621 } 622 } 623 624 /* 625 * allow essentially unlimited paths; certain programs (find, remove, ls) 626 * need to work on any tree. Most systems will allow creation of paths 627 * much longer than MAXPATHLEN, even though the kernel won't resolve them. 628 * Add an extra 128 bytes to the requested size so that we don't realloc 629 * the path 2 bytes at a time. 630 */ 631 static 632 fts_path(size) 633 int size; 634 { 635 stream->pathlen += size + 128; 636 return((int)(stream->path = R(char, stream->pathlen, stream->path))); 637 } 638 639 static FTSENT * 640 fts_root(name) 641 register char *name; 642 { 643 register char *cp; 644 645 /* 646 * rip trailing slashes; it's somewhat unclear in POSIX 1003.1 what 647 * /a/b/ really is, they don't talk about what a null path component 648 * resolves to. This hopefully does what the user intended. Don't 649 * allow null pathnames. 650 */ 651 for (cp = name; *cp; ++cp); 652 if (cp == name) { 653 errno = ENOENT; 654 return(NULL); 655 } 656 while (--cp > name && *cp == '/'); 657 *++cp = '\0'; 658 return(fts_alloc(name, cp - name)); 659 } 660