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