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