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.30 (Berkeley) 02/04/92"; 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 <stdlib.h> 19 #include <string.h> 20 #include <unistd.h> 21 22 static FTSENT *fts_alloc __P((FTS *, char *, int)); 23 static FTSENT *fts_build __P((FTS *, int)); 24 static void fts_lfree __P((FTSENT *)); 25 static void fts_load __P((FTS *, FTSENT *)); 26 static void fts_padjust __P((FTS *, void *)); 27 static int fts_palloc __P((FTS *, int)); 28 static FTSENT *fts_sort __P((FTS *, FTSENT *, int)); 29 static u_short fts_stat __P((FTS *, FTSENT *, int)); 30 31 #define ISDOT(a) (a[0] == '.' && (!a[1] || a[1] == '.' && !a[2])) 32 33 #define ISSET(opt) (sp->fts_options & opt) 34 #define SET(opt) (sp->fts_options |= opt) 35 36 #define CHDIR(sp, path) (!ISSET(FTS_NOCHDIR) && chdir(path)) 37 #define FCHDIR(sp, fd) (!ISSET(FTS_NOCHDIR) && fchdir(fd)) 38 39 /* fts_build flags */ 40 #define BCHILD 1 /* from fts_children */ 41 #define BREAD 2 /* from fts_read */ 42 43 FTS * 44 fts_open(argv, options, compar) 45 char * const *argv; 46 register int options; 47 int (*compar)(); 48 { 49 register FTS *sp; 50 register FTSENT *p, *root; 51 register int nitems, maxlen; 52 FTSENT *parent, *tmp; 53 int len; 54 55 /* Allocate/initialize the stream */ 56 if ((sp = malloc((u_int)sizeof(FTS))) == NULL) 57 return (NULL); 58 bzero(sp, sizeof(FTS)); 59 sp->fts_compar = compar; 60 sp->fts_options = options; 61 62 /* Logical walks turn on NOCHDIR; symbolic links are too hard. */ 63 if (ISSET(FTS_LOGICAL)) 64 SET(FTS_NOCHDIR); 65 66 /* Allocate/initialize root's parent. */ 67 if ((parent = fts_alloc(sp, "", 0)) == NULL) 68 goto mem1; 69 parent->fts_level = FTS_ROOTPARENTLEVEL; 70 71 /* Allocate/initialize root(s). */ 72 for (root = NULL, maxlen = nitems = 0; *argv; ++argv, ++nitems) { 73 /* Don't allow zero-length paths. */ 74 if ((len = strlen(*argv)) == 0) { 75 errno = ENOENT; 76 goto mem2; 77 } 78 if (maxlen < len) 79 maxlen = len; 80 81 p = fts_alloc(sp, *argv, len); 82 p->fts_level = FTS_ROOTLEVEL; 83 p->fts_parent = parent; 84 p->fts_accpath = p->fts_name; 85 p->fts_info = fts_stat(sp, p, ISSET(FTS_COMFOLLOW)); 86 87 /* Command-line "." and ".." are real directories. */ 88 if (p->fts_info == FTS_DOT) 89 p->fts_info = FTS_D; 90 91 /* 92 * If comparison routine supplied, traverse in sorted 93 * order; otherwise traverse in the order specified. 94 */ 95 if (compar) { 96 p->fts_link = root; 97 root = p; 98 } else { 99 p->fts_link = NULL; 100 if (root == NULL) 101 tmp = root = p; 102 else { 103 tmp->fts_link = p; 104 tmp = p; 105 } 106 } 107 } 108 if (compar && nitems > 1) 109 root = fts_sort(sp, root, nitems); 110 111 /* 112 * Allocate a dummy pointer and make fts_read think that we've just 113 * finished the node before the root(s); set p->fts_info to FTS_INIT 114 * so that everything about the "current" node is ignored. 115 */ 116 if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL) 117 goto mem2; 118 sp->fts_cur->fts_link = root; 119 sp->fts_cur->fts_info = FTS_INIT; 120 121 /* 122 * Start out with more than 1K of path space, and enough, in any 123 * case, to hold the user's paths. 124 */ 125 if (fts_palloc(sp, MAX(maxlen, MAXPATHLEN))) 126 goto mem3; 127 128 /* 129 * If using chdir(2), grab a file descriptor pointing to dot to insure 130 * that we can get back here; this could be avoided for some paths, 131 * but almost certainly not worth the effort. Slashes, symbolic links, 132 * and ".." are all fairly nasty problems. Note, if we can't get the 133 * descriptor we run anyway, just more slowly. 134 */ 135 if (!ISSET(FTS_NOCHDIR) && (sp->fts_rfd = open(".", O_RDONLY, 0)) < 0) 136 SET(FTS_NOCHDIR); 137 138 return (sp); 139 140 mem3: free(sp->fts_cur); 141 mem2: fts_lfree(root); 142 free(parent); 143 mem1: free(sp); 144 return (NULL); 145 } 146 147 static void 148 fts_load(sp, p) 149 FTS *sp; 150 register FTSENT *p; 151 { 152 register int len; 153 register char *cp; 154 155 /* 156 * Load the stream structure for the next traversal. Since we don't 157 * actually enter the directory until after the preorder visit, set 158 * the fts_accpath field specially so the chdir gets done to the right 159 * place and the user can access the first node. From fts_open it's 160 * known that the path will fit. 161 */ 162 len = p->fts_pathlen = p->fts_namelen; 163 bcopy(p->fts_name, sp->fts_path, len + 1); 164 if ((cp = rindex(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) { 165 len = strlen(++cp); 166 bcopy(cp, p->fts_name, len + 1); 167 p->fts_namelen = len; 168 } 169 p->fts_accpath = p->fts_path = sp->fts_path; 170 sp->fts_dev = p->fts_dev; 171 } 172 173 int 174 fts_close(sp) 175 FTS *sp; 176 { 177 register FTSENT *freep, *p; 178 int saved_errno; 179 180 /* 181 * This still works if we haven't read anything -- the dummy structure 182 * points to the root list, so we step through to the end of the root 183 * list which has a valid parent pointer. 184 */ 185 if (sp->fts_cur) { 186 for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) { 187 freep = p; 188 p = p->fts_link ? p->fts_link : p->fts_parent; 189 free(freep); 190 } 191 free(p); 192 } 193 194 /* Free up child linked list, sort array, path buffer. */ 195 if (sp->fts_child) 196 fts_lfree(sp->fts_child); 197 if (sp->fts_array) 198 free(sp->fts_array); 199 free(sp->fts_path); 200 201 /* Return to original directory, save errno if necessary. */ 202 if (!ISSET(FTS_NOCHDIR)) { 203 saved_errno = fchdir(sp->fts_rfd) ? errno : 0; 204 (void)close(sp->fts_rfd); 205 } 206 207 /* Free up the stream pointer. */ 208 free(sp); 209 210 /* Set errno and return. */ 211 if (!ISSET(FTS_NOCHDIR) && saved_errno) { 212 errno = saved_errno; 213 return (-1); 214 } 215 return (0); 216 } 217 218 /* 219 * Special case a root of "/" so that slashes aren't appended which would 220 * cause paths to be written as "//foo". 221 */ 222 #define NAPPEND(p) \ 223 (p->fts_level == FTS_ROOTLEVEL && p->fts_pathlen == 1 && \ 224 p->fts_path[0] == '/' ? 0 : p->fts_pathlen) 225 226 FTSENT * 227 fts_read(sp) 228 register FTS *sp; 229 { 230 register FTSENT *p, *tmp; 231 register int instr; 232 register char *t; 233 234 /* If finished or unrecoverable error, return NULL. */ 235 if (sp->fts_cur == NULL || ISSET(FTS_STOP)) 236 return (NULL); 237 238 /* Set current node pointer. */ 239 p = sp->fts_cur; 240 241 /* Save and zero out user instructions. */ 242 instr = p->fts_instr; 243 p->fts_instr = FTS_NOINSTR; 244 245 /* Any type of file may be re-visited; re-stat and re-turn. */ 246 if (instr == FTS_AGAIN) { 247 p->fts_info = fts_stat(sp, p, 0); 248 return (p); 249 } 250 251 /* 252 * Following a symlink -- SLNONE test allows application to see 253 * SLNONE and recover. If indirecting through a symlink, have 254 * keep a pointer to current location. If unable to get that 255 * pointer, follow fails. 256 */ 257 if (instr == FTS_FOLLOW && 258 (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) { 259 p->fts_info = fts_stat(sp, p, 1); 260 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) 261 if ((p->fts_symfd = open(".", O_RDONLY, 0)) < 0) { 262 p->fts_errno = errno; 263 p->fts_info = FTS_ERR; 264 } else 265 p->fts_flags |= FTS_SYMFOLLOW; 266 return (p); 267 } 268 269 /* Directory in pre-order. */ 270 if (p->fts_info == FTS_D) { 271 /* If skipped or crossed mount point, do post-order visit. */ 272 if (instr == FTS_SKIP || 273 ISSET(FTS_XDEV) && p->fts_dev != sp->fts_dev) { 274 if (p->fts_flags & FTS_SYMFOLLOW) 275 (void)close(p->fts_symfd); 276 if (sp->fts_child) { 277 fts_lfree(sp->fts_child); 278 sp->fts_child = NULL; 279 } 280 p->fts_info = FTS_DP; 281 return (p); 282 } 283 284 /* 285 * Cd to the subdirectory, reading it if haven't already. If 286 * the read fails for any reason, or the directory is empty, 287 * the fts_info field of the current node is set by fts_build. 288 * If have already read and now fail to chdir, whack the list 289 * to make the names come out right, and set the parent state 290 * so the application will eventually get an error condition. 291 * If haven't read and fail to chdir, check to see if we're 292 * at the root node -- if so, we have to get back or the root 293 * node may be inaccessible. 294 */ 295 if (sp->fts_child) { 296 if (CHDIR(sp, p->fts_accpath)) { 297 p->fts_errno = errno; 298 p->fts_flags |= FTS_DONTCHDIR; 299 for (p = sp->fts_child; p; p = p->fts_link) 300 p->fts_accpath = 301 p->fts_parent->fts_accpath; 302 } 303 } else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) { 304 p->fts_flags |= FTS_DONTCHDIR; 305 if (ISSET(FTS_STOP)) 306 return (NULL); 307 if (p->fts_level == FTS_ROOTLEVEL && 308 FCHDIR(sp, sp->fts_rfd)) { 309 (void)close(sp->fts_rfd); 310 SET(FTS_STOP); 311 return (NULL); 312 } 313 (void)close(sp->fts_rfd); 314 return (p); 315 } 316 p = sp->fts_child; 317 sp->fts_child = NULL; 318 goto name; 319 } 320 321 /* Move to the next node on this level. */ 322 next: tmp = p; 323 if (p = p->fts_link) { 324 free(tmp); 325 326 /* If reached the top, load the paths for the next root. */ 327 if (p->fts_level == FTS_ROOTLEVEL) { 328 fts_load(sp, p); 329 return (sp->fts_cur = p); 330 } 331 332 /* 333 * User may have called fts_set on the node. If skipped, 334 * ignore. If followed, get a file descriptor so we can 335 * get back if necessary. 336 */ 337 if (p->fts_instr == FTS_SKIP) 338 goto next; 339 if (p->fts_instr == FTS_FOLLOW) { 340 p->fts_info = fts_stat(sp, p, 1); 341 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) 342 if ((p->fts_symfd = 343 open(".", O_RDONLY, 0)) < 0) { 344 p->fts_errno = errno; 345 p->fts_info = FTS_ERR; 346 } else 347 p->fts_flags |= FTS_SYMFOLLOW; 348 p->fts_instr = FTS_NOINSTR; 349 } 350 351 name: t = sp->fts_path + NAPPEND(p->fts_parent); 352 *t++ = '/'; 353 bcopy(p->fts_name, t, p->fts_namelen + 1); 354 return (sp->fts_cur = p); 355 } 356 357 /* Move up to the parent node. */ 358 p = tmp->fts_parent; 359 free(tmp); 360 361 if (p->fts_level == FTS_ROOTPARENTLEVEL) { 362 /* 363 * Done; free everything up and set errno to 0 so the user 364 * can distinguish between error and EOF. 365 */ 366 free(p); 367 errno = 0; 368 return (sp->fts_cur = NULL); 369 } 370 371 sp->fts_path[p->fts_pathlen] = '\0'; 372 373 /* 374 * Change to starting directory. If at a root node or came through a 375 * symlink, go back through the file descriptor. Otherwise, just cd 376 * up one directory. 377 */ 378 if (p->fts_level == FTS_ROOTLEVEL) { 379 if (FCHDIR(sp, sp->fts_rfd)) { 380 (void)close(sp->fts_rfd); 381 SET(FTS_STOP); 382 return (NULL); 383 } 384 (void)close(sp->fts_rfd); 385 } else if (p->fts_flags & FTS_SYMFOLLOW) { 386 if (FCHDIR(sp, p->fts_symfd)) { 387 (void)close(p->fts_symfd); 388 SET(FTS_STOP); 389 return (NULL); 390 } 391 (void)close(p->fts_symfd); 392 } else if (!(p->fts_flags & FTS_DONTCHDIR)) { 393 if (CHDIR(sp, "..")) { 394 SET(FTS_STOP); 395 return (NULL); 396 } 397 } 398 p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP; 399 return (sp->fts_cur = p); 400 } 401 402 /* 403 * Fts_set takes the stream as an argument although it's not used in this 404 * implementation; it would be necessary if anyone wanted to add global 405 * semantics to fts using fts_set. An error return is allowed for similar 406 * reasons. 407 */ 408 /* ARGSUSED */ 409 int 410 fts_set(sp, p, instr) 411 FTS *sp; 412 FTSENT *p; 413 int instr; 414 { 415 p->fts_instr = instr; 416 return (0); 417 } 418 419 FTSENT * 420 fts_children(sp) 421 register FTS *sp; 422 { 423 register FTSENT *p; 424 int fd; 425 426 /* Set current node pointer. */ 427 p = sp->fts_cur; 428 429 /* 430 * Errno set to 0 so user can distinguish empty directory from 431 * an error. 432 */ 433 errno = 0; 434 435 /* Fatal errors stop here. */ 436 if (ISSET(FTS_STOP)) 437 return (NULL); 438 439 /* Return logical hierarchy of user's arguments. */ 440 if (p->fts_info == FTS_INIT) 441 return (p->fts_link); 442 443 /* 444 * If not a directory being visited in pre-order, stop here. Could 445 * allow FTS_DNR, assuming the user has fixed the problem, but the 446 * same effect is available with FTS_AGAIN. 447 */ 448 if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */) 449 return (NULL); 450 451 /* Free up any previous child list. */ 452 if (sp->fts_child) 453 fts_lfree(sp->fts_child); 454 455 /* 456 * If using chdir on a relative path and called BEFORE fts_read does 457 * its chdir to the root of a traversal, we can lose -- we need to 458 * chdir into the subdirectory, and we don't know where the current 459 * directory is, so we can't get back so that the upcoming chdir by 460 * fts_read will work. 461 */ 462 if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' || 463 ISSET(FTS_NOCHDIR)) 464 return (sp->fts_child = fts_build(sp, BCHILD)); 465 466 if ((fd = open(".", O_RDONLY, 0)) < 0) 467 return (NULL); 468 sp->fts_child = fts_build(sp, BCHILD); 469 if (fchdir(fd)) 470 return (NULL); 471 (void)close(fd); 472 return (sp->fts_child); 473 } 474 475 /* 476 * This is the tricky part -- do not casually change *anything* in here. The 477 * idea is to build the linked list of entries that are used by fts_children 478 * and fts_read. There are lots of special cases. 479 * 480 * The real slowdown in walking the tree is the stat calls. If FTS_NOSTAT is 481 * set and it's a physical walk (so that symbolic links can't be directories), 482 * we assume that the number of subdirectories in a node is equal to the number 483 * of links to the parent. This allows stat calls to be skipped in any leaf 484 * directories and for any nodes after the directories in the parent node have 485 * been found. This empirically cuts the stat calls by about 2/3. 486 */ 487 static FTSENT * 488 fts_build(sp, type) 489 register FTS *sp; 490 int type; 491 { 492 register struct dirent *dp; 493 register FTSENT *p, *head; 494 register int nitems; 495 FTSENT *cur, *tail; 496 DIR *dirp; 497 void *adjaddr; 498 int cderrno, descend, len, level, maxlen, nlinks, saved_errno; 499 char *cp; 500 501 /* Set current node pointer. */ 502 cur = sp->fts_cur; 503 504 /* 505 * Open the directory for reading. If this fails, we're done. 506 * If being called from fts_read, set the fts_info field. 507 */ 508 if ((dirp = opendir(cur->fts_accpath)) == NULL) { 509 if (type == BREAD) { 510 cur->fts_info = FTS_DNR; 511 cur->fts_errno = errno; 512 } 513 return (NULL); 514 } 515 516 /* 517 * Nlinks is the number of possible entries of type directory in the 518 * directory if we're cheating on stat calls, 0 if we're not doing 519 * any stat calls at all, -1 if we're doing stats on everything. 520 */ 521 nlinks = ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL) ? 522 cur->fts_nlink - (ISSET(FTS_SEEDOT) ? 0 : 2) : -1; 523 524 #ifdef notdef 525 (void)printf("nlinks == %d (cur: %d)\n", nlinks, cur->fts_nlink); 526 (void)printf("NOSTAT %d PHYSICAL %d SEEDOT %d\n", 527 ISSET(FTS_NOSTAT), ISSET(FTS_PHYSICAL), ISSET(FTS_SEEDOT)); 528 #endif 529 /* 530 * If we're going to need to stat anything or we want to descend 531 * and stay in the directory, chdir. If this fails we keep going. 532 * We won't be able to stat anything, but we can still return the 533 * names themselves. Note, that since fts_read won't be able to 534 * chdir into the directory, it will have to return different path 535 * names than before, i.e. "a/b" instead of "b". Since the node 536 * has already been visited in pre-order, have to wait until the 537 * post-order visit to return the error. There is a special case 538 * here, if there was nothing to stat then it's not an error to 539 * not be able to stat. This is all fairly nasty. If a program 540 * needed sorted entries or stat information, they had better be 541 * checking FTS_NS on the returned nodes. 542 */ 543 if (nlinks || type == BREAD) 544 if (FCHDIR(sp, dirfd(dirp))) { 545 if (nlinks && type == BREAD) 546 cur->fts_errno = errno; 547 descend = 0; 548 cderrno = errno; 549 } else { 550 descend = 1; 551 cderrno = 0; 552 } 553 else 554 descend = 0; 555 556 /* 557 * Figure out the max file name length that can be stored in the 558 * current path -- the inner loop allocates more path as necessary. 559 * We really wouldn't have to do the maxlen calculations here, we 560 * could do them in fts_read before returning the path, but it's a 561 * lot easier here since the length is part of the dirent structure. 562 * 563 * If not changing directories set a pointer so that can just append 564 * each new name into the path. 565 */ 566 maxlen = sp->fts_pathlen - cur->fts_pathlen - 1; 567 len = NAPPEND(cur); 568 if (ISSET(FTS_NOCHDIR)) { 569 cp = sp->fts_path + len; 570 *cp++ = '/'; 571 } 572 573 level = cur->fts_level + 1; 574 575 /* Read the directory, attaching each entry to the `link' pointer. */ 576 adjaddr = NULL; 577 for (head = tail = NULL, nitems = 0; dp = readdir(dirp);) { 578 if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name)) 579 continue; 580 581 if ((p = fts_alloc(sp, dp->d_name, (int)dp->d_namlen)) == NULL) 582 goto mem1; 583 if (dp->d_namlen > maxlen) { 584 if (fts_palloc(sp, (int)dp->d_namlen)) { 585 /* 586 * No more memory for path or structures. Save 587 * errno, free up the current structure and the 588 * structures already allocated. 589 */ 590 mem1: saved_errno = errno; 591 if (p) 592 free(p); 593 fts_lfree(head); 594 (void)closedir(dirp); 595 errno = saved_errno; 596 cur->fts_info = FTS_ERR; 597 SET(FTS_STOP); 598 return (NULL); 599 } 600 adjaddr = sp->fts_path; 601 maxlen = sp->fts_pathlen - sp->fts_cur->fts_pathlen - 1; 602 } 603 604 p->fts_pathlen = len + dp->d_namlen + 1; 605 p->fts_parent = sp->fts_cur; 606 p->fts_level = level; 607 608 if (cderrno) { 609 if (nlinks) { 610 p->fts_info = FTS_NS; 611 p->fts_errno = cderrno; 612 } else 613 p->fts_info = FTS_NSOK; 614 p->fts_accpath = cur->fts_accpath; 615 } else if (nlinks) { 616 /* Build a file name for fts_stat to stat. */ 617 if (ISSET(FTS_NOCHDIR)) { 618 p->fts_accpath = p->fts_path; 619 bcopy(p->fts_name, cp, p->fts_namelen + 1); 620 } else 621 p->fts_accpath = p->fts_name; 622 p->fts_info = fts_stat(sp, p, 0); 623 if (nlinks > 0 && (p->fts_info == FTS_D || 624 p->fts_info == FTS_DC || p->fts_info == FTS_DOT)) 625 --nlinks; 626 } else { 627 p->fts_accpath = 628 ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name; 629 p->fts_info = FTS_NSOK; 630 } 631 632 /* We walk in directory order so "ls -f" doesn't get upset. */ 633 p->fts_link = NULL; 634 if (head == NULL) 635 head = tail = p; 636 else { 637 tail->fts_link = p; 638 tail = p; 639 } 640 ++nitems; 641 } 642 (void)closedir(dirp); 643 644 /* 645 * If had to realloc the path, adjust the addresses for the rest 646 * of the tree. 647 */ 648 if (adjaddr) 649 fts_padjust(sp, adjaddr); 650 651 /* 652 * If not changing directories, reset the path back to original 653 * state. 654 */ 655 if (ISSET(FTS_NOCHDIR)) { 656 if (cp - 1 > sp->fts_path) 657 --cp; 658 *cp = '\0'; 659 } 660 661 /* 662 * If descended after called from fts_children or called from 663 * fts_read and didn't find anything, get back. If can't get 664 * back, done. 665 */ 666 if (descend && (!nitems || type == BCHILD) && CHDIR(sp, "..")) { 667 cur->fts_info = FTS_ERR; 668 SET(FTS_STOP); 669 return (NULL); 670 } 671 672 /* If didn't find anything, just do the post-order visit */ 673 if (!nitems) { 674 if (type == BREAD) 675 cur->fts_info = FTS_DP; 676 return (NULL); 677 } 678 679 /* Sort the entries. */ 680 if (sp->fts_compar && nitems > 1) 681 head = fts_sort(sp, head, nitems); 682 return (head); 683 } 684 685 static u_short 686 fts_stat(sp, p, follow) 687 FTS *sp; 688 register FTSENT *p; 689 int follow; 690 { 691 register FTSENT *t; 692 register dev_t dev; 693 register ino_t ino; 694 struct stat *sbp, sb; 695 int saved_errno; 696 697 /* If user needs stat info, stat buffer already allocated. */ 698 sbp = ISSET(FTS_NOSTAT) ? &sb : p->fts_statp; 699 700 /* 701 * If doing a logical walk, or application requested FTS_FOLLOW, do 702 * a stat(2). If that fails, check for a non-existent symlink. If 703 * fail, set the errno from the stat call. 704 */ 705 if (ISSET(FTS_LOGICAL) || follow) { 706 if (stat(p->fts_accpath, sbp)) { 707 saved_errno = errno; 708 if (!lstat(p->fts_accpath, sbp)) { 709 errno = 0; 710 return (FTS_SLNONE); 711 } 712 p->fts_errno = saved_errno; 713 goto err; 714 } 715 } else if (lstat(p->fts_accpath, sbp)) { 716 p->fts_errno = errno; 717 err: bzero(sbp, sizeof(struct stat)); 718 return (FTS_NS); 719 } 720 721 if (S_ISDIR(sbp->st_mode)) { 722 /* 723 * Set the device/inode. Used to find cycles and check for 724 * crossing mount points. Also remember the link count, used 725 * in fts_build to limit the number of stat calls. It is 726 * understood that these fields are only referenced if fts_info 727 * is set to FTS_D. 728 */ 729 dev = p->fts_dev = sbp->st_dev; 730 ino = p->fts_ino = sbp->st_ino; 731 p->fts_nlink = sbp->st_nlink; 732 733 if (ISDOT(p->fts_name)) 734 return (FTS_DOT); 735 736 /* 737 * Cycle detection is done by brute force when the directory 738 * is first encountered. If the tree gets deep enough or the 739 * number of symbolic links to directories is high enough, 740 * something faster might be worthwhile. 741 */ 742 for (t = p->fts_parent; 743 t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent) 744 if (ino == t->fts_ino && dev == t->fts_dev) { 745 p->fts_cycle = t; 746 return (FTS_DC); 747 } 748 return (FTS_D); 749 } 750 if (S_ISLNK(sbp->st_mode)) 751 return (FTS_SL); 752 if (S_ISREG(sbp->st_mode)) 753 return (FTS_F); 754 return (FTS_DEFAULT); 755 } 756 757 static FTSENT * 758 fts_sort(sp, head, nitems) 759 FTS *sp; 760 FTSENT *head; 761 register int nitems; 762 { 763 register FTSENT **ap, *p; 764 765 /* 766 * Construct an array of pointers to the structures and call qsort(3). 767 * Reassemble the array in the order returned by qsort. If unable to 768 * sort for memory reasons, return the directory entries in their 769 * current order. Allocate enough space for the current needs plus 770 * 40 so don't realloc one entry at a time. 771 */ 772 if (nitems > sp->fts_nitems) { 773 sp->fts_nitems = nitems + 40; 774 if ((sp->fts_array = realloc(sp->fts_array, 775 (size_t)(sp->fts_nitems * sizeof(FTSENT *)))) == NULL) { 776 sp->fts_nitems = 0; 777 return (head); 778 } 779 } 780 for (ap = sp->fts_array, p = head; p; p = p->fts_link) 781 *ap++ = p; 782 qsort((void *)sp->fts_array, nitems, sizeof(FTSENT *), sp->fts_compar); 783 for (head = *(ap = sp->fts_array); --nitems; ++ap) 784 ap[0]->fts_link = ap[1]; 785 ap[0]->fts_link = NULL; 786 return (head); 787 } 788 789 static FTSENT * 790 fts_alloc(sp, name, len) 791 FTS *sp; 792 char *name; 793 register int len; 794 { 795 register FTSENT *p; 796 int needstat; 797 798 /* 799 * Variable sized structures. The stat structure isn't necessary 800 * if the user doesn't need it, and the name is variable length. 801 * Allocate enough extra space after the structure to store them. 802 */ 803 needstat = ISSET(FTS_NOSTAT) ? 0 : sizeof(struct stat); 804 if ((p = malloc((size_t)(sizeof(FTSENT) + len + 1 + needstat))) == NULL) 805 return (NULL); 806 bcopy(name, p->fts_name, len + 1); 807 if (needstat) 808 p->fts_statp = (struct stat *)(p->fts_name + len + 1); 809 p->fts_namelen = len; 810 p->fts_path = sp->fts_path; 811 p->fts_errno = 0; 812 p->fts_flags = 0; 813 p->fts_instr = FTS_NOINSTR; 814 p->fts_number = 0; 815 #ifdef NOT_NECESSARY 816 p->fts_pointer = NULL; 817 #endif 818 return (p); 819 } 820 821 static void 822 fts_lfree(head) 823 register FTSENT *head; 824 { 825 register FTSENT *p; 826 827 /* Free a linked list of structures. */ 828 while (p = head) { 829 head = head->fts_link; 830 free(p); 831 } 832 } 833 834 /* 835 * Allow essentially unlimited paths; find, rm, ls should all work on any tree. 836 * Most systems will allow creation of paths much longer than MAXPATHLEN, even 837 * though the kernel won't resolve them. Add the size (not just what's needed) 838 * plus 256 bytes so don't realloc the path 2 bytes at a time. 839 */ 840 static int 841 fts_palloc(sp, more) 842 FTS *sp; 843 int more; 844 { 845 846 sp->fts_pathlen += more + 256; 847 sp->fts_path = realloc(sp->fts_path, (size_t)sp->fts_pathlen); 848 return (sp->fts_path == NULL); 849 } 850 851 /* 852 * When the path is realloc'd, have to fix all of the pointers in structures 853 * already returned. 854 */ 855 static void 856 fts_padjust(sp, addr) 857 FTS *sp; 858 void *addr; 859 { 860 FTSENT *p; 861 862 #define ADJUST(p) { \ 863 (p)->fts_accpath = addr + ((p)->fts_accpath - (p)->fts_path); \ 864 (p)->fts_path = addr; \ 865 } 866 /* Adjust the current set of children. */ 867 for (p = sp->fts_child; p; p = p->fts_link) 868 ADJUST(p); 869 870 /* Adjust the rest of the tree. */ 871 for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) { 872 ADJUST(p); 873 p = p->fts_link ? p->fts_link : p->fts_parent; 874 } 875 } 876