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.27 (Berkeley) 01/17/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, 0); 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. 254 */ 255 if (instr == FTS_FOLLOW && 256 (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) { 257 p->fts_info = fts_stat(sp, p, 1); 258 return (p); 259 } 260 261 /* Directory in pre-order. */ 262 if (p->fts_info == FTS_D) { 263 /* If skipped or crossed mount point, do post-order visit. */ 264 if (instr == FTS_SKIP || 265 ISSET(FTS_XDEV) && p->fts_dev != sp->fts_dev) { 266 if (sp->fts_child) { 267 fts_lfree(sp->fts_child); 268 sp->fts_child = NULL; 269 } 270 p->fts_info = FTS_DP; 271 return (p); 272 } 273 274 /* 275 * Cd to the subdirectory, reading it if haven't already. If 276 * the read fails for any reason, or the directory is empty, 277 * the fts_info field of the current node is set by fts_build. 278 * If have already read and now fail to chdir, whack the list 279 * to make the names come out right, and set the parent state 280 * so the application will eventually get an error condition. 281 * If haven't read and fail to chdir, check to see if we're 282 * at the root node -- if so, we have to get back or the root 283 * node may be inaccessible. 284 */ 285 if (sp->fts_child) { 286 if (CHDIR(sp, p->fts_accpath)) { 287 p->fts_parent->fts_errno = errno; 288 for (p = sp->fts_child; p; p = p->fts_link) 289 p->fts_accpath = 290 p->fts_parent->fts_accpath; 291 } 292 } else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) { 293 if ISSET(FTS_STOP) 294 return (NULL); 295 if (p->fts_level == FTS_ROOTLEVEL && 296 FCHDIR(sp, sp->fts_rfd)) { 297 SET(FTS_STOP); 298 return (NULL); 299 } 300 return (p); 301 } 302 p = sp->fts_child; 303 sp->fts_child = NULL; 304 goto name; 305 } 306 307 /* Move to next node on this level. */ 308 next: tmp = p; 309 if (p = p->fts_link) { 310 free(tmp); 311 312 /* If reached the top, load the paths for the next root. */ 313 if (p->fts_level == FTS_ROOTLEVEL) { 314 fts_load(sp, p); 315 return (sp->fts_cur = p); 316 } 317 318 /* User may have called fts_set on the node. */ 319 if (p->fts_instr == FTS_SKIP) 320 goto next; 321 if (p->fts_instr == FTS_FOLLOW) { 322 p->fts_info = fts_stat(sp, p, 1); 323 p->fts_instr = FTS_NOINSTR; 324 } 325 326 name: t = sp->fts_path + NAPPEND(p->fts_parent); 327 *t++ = '/'; 328 bcopy(p->fts_name, t, p->fts_namelen + 1); 329 return (sp->fts_cur = p); 330 } 331 332 /* Move up to the parent node. */ 333 p = tmp->fts_parent; 334 free(tmp); 335 336 if (p->fts_level == FTS_ROOTPARENTLEVEL) { 337 /* 338 * Done; free everything up and set errno to 0 so the user 339 * can distinguish between error and EOF. 340 */ 341 free(p); 342 errno = 0; 343 return (sp->fts_cur = NULL); 344 } 345 346 sp->fts_path[p->fts_pathlen] = '\0'; 347 348 /* 349 * Cd back up to the parent directory. If at a root node, have to cd 350 * back to the original place, otherwise may not be able to access the 351 * original node on post-order. 352 */ 353 if (p->fts_level == FTS_ROOTLEVEL) { 354 if (FCHDIR(sp, sp->fts_rfd)) { 355 SET(FTS_STOP); 356 return (NULL); 357 } 358 } 359 else if (CHDIR(sp, "..")) { 360 SET(FTS_STOP); 361 return (NULL); 362 } 363 364 /* 365 * If had a chdir error when trying to get into the directory, set the 366 * info field to reflect this, and restore errno. The error indicator 367 * has to be reset to 0 so that if the user does an FTS_AGAIN, it all 368 * works. 369 */ 370 if (p->fts_errno) { 371 errno = p->fts_errno; 372 p->fts_errno = 0; 373 p->fts_info = FTS_ERR; 374 } else 375 p->fts_info = FTS_DP; 376 return (sp->fts_cur = p); 377 } 378 379 /* 380 * Fts_set takes the stream as an argument although it's not used in this 381 * implementation; it would be necessary if anyone wanted to add global 382 * semantics to fts using fts_set. An error return is allowed for similar 383 * reasons. 384 */ 385 /* ARGSUSED */ 386 int 387 fts_set(sp, p, instr) 388 FTS *sp; 389 FTSENT *p; 390 int instr; 391 { 392 p->fts_instr = instr; 393 return (0); 394 } 395 396 FTSENT * 397 fts_children(sp) 398 register FTS *sp; 399 { 400 register FTSENT *p; 401 int fd; 402 403 /* Set current node pointer. */ 404 p = sp->fts_cur; 405 406 /* 407 * Errno set to 0 so user can distinguish empty directory from 408 * an error. 409 */ 410 errno = 0; 411 412 /* Fatal errors stop here. */ 413 if (ISSET(FTS_STOP)) 414 return (NULL); 415 416 /* Return logical hierarchy of user's arguments. */ 417 if (p->fts_info == FTS_INIT) 418 return (p->fts_link); 419 420 /* If not a directory being visited in pre-order, stop here. */ 421 if (p->fts_info != FTS_D && p->fts_info != FTS_DNR) 422 return (NULL); 423 424 /* Free up any previous child list. */ 425 if (sp->fts_child) 426 fts_lfree(sp->fts_child); 427 428 /* 429 * If using chdir on a relative path and called BEFORE fts_read does 430 * its chdir to the root of a traversal, we can lose -- we need to 431 * chdir into the subdirectory, and we don't know where the current 432 * directory is, so we can't get back so that the upcoming chdir by 433 * fts_read will work. 434 */ 435 if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' || 436 ISSET(FTS_NOCHDIR)) 437 return (sp->fts_child = fts_build(sp, BCHILD)); 438 439 if ((fd = open(".", O_RDONLY, 0)) < 0) 440 return (NULL); 441 sp->fts_child = fts_build(sp, BCHILD); 442 if (fchdir(fd)) 443 return (NULL); 444 (void)close(fd); 445 return (sp->fts_child); 446 } 447 448 /* 449 * This is the tricky part -- do not casually change *anything* in here. The 450 * idea is to build the linked list of entries that are used by fts_children 451 * and fts_read. There are lots of special cases. 452 * 453 * The real slowdown in walking the tree is the stat calls. If FTS_NOSTAT is 454 * set and it's a physical walk (so that symbolic links can't be directories), 455 * we assume that the number of subdirectories in a node is equal to the number 456 * of links to the parent. This allows stat calls to be skipped in any leaf 457 * directories and for any nodes after the directories in the parent node have 458 * been found. This empirically cuts the stat calls by about 2/3. 459 */ 460 static FTSENT * 461 fts_build(sp, type) 462 register FTS *sp; 463 int type; 464 { 465 register struct dirent *dp; 466 register FTSENT *p, *head; 467 register int nitems; 468 FTSENT *cur; 469 DIR *dirp; 470 void *adjaddr; 471 int cderr, descend, len, level, maxlen, nlinks, saved_errno; 472 char *cp; 473 474 /* Set current node pointer. */ 475 cur = sp->fts_cur; 476 477 /* 478 * Open the directory for reading. If this fails, we're done. 479 * If being called from fts_read, set the fts_info field. 480 */ 481 if ((dirp = opendir(cur->fts_accpath)) == NULL) { 482 if (type == BREAD) { 483 cur->fts_info = FTS_DNR; 484 cur->fts_errno = errno; 485 } 486 return (NULL); 487 } 488 489 /* 490 * Nlinks is the number of possible entries of type directory in the 491 * directory if we're cheating on stat calls, 0 if we're not doing 492 * any stat calls at all, -1 if we're doing stats on everything. 493 */ 494 nlinks = 495 ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL) ? 496 cur->fts_nlink - (ISSET(FTS_SEEDOT) ? 0 : 2) : -1; 497 498 /* 499 * If we're going to need to stat anything or we want to descend 500 * and stay in the directory, chdir. If this fails we keep going. 501 * We won't be able to stat anything, but we can still return the 502 * names themselves. Note, that since fts_read won't be able to 503 * chdir into the directory, it will have to return different path 504 * names than before, i.e. "a/b" instead of "b". Since the node 505 * has already been visited in pre-order, have to wait until the 506 * post-order visit to return the error. This is all fairly nasty. 507 * If a program needed sorted entries or stat information, they had 508 * better be checking FTS_NS on the returned nodes. 509 */ 510 if (nlinks || type == BREAD) 511 if (FCHDIR(sp, dirfd(dirp))) { 512 if (type == BREAD) 513 cur->fts_errno = errno; 514 descend = nlinks = 0; 515 cderr = 1; 516 } else { 517 descend = 1; 518 cderr = 0; 519 } 520 else 521 descend = 0; 522 523 /* 524 * Figure out the max file name length that can be stored in the 525 * current path -- the inner loop allocates more path as necessary. 526 * We really wouldn't have to do the maxlen calculations here, we 527 * could do them in fts_read before returning the path, but it's a 528 * lot easier here since the length is part of the dirent structure. 529 * 530 * If not changing directories set a pointer so that can just append 531 * each new name into the path. 532 */ 533 maxlen = sp->fts_pathlen - cur->fts_pathlen - 1; 534 len = NAPPEND(cur); 535 if (ISSET(FTS_NOCHDIR)) { 536 cp = sp->fts_path + len; 537 *cp++ = '/'; 538 } 539 540 level = cur->fts_level + 1; 541 542 /* Read the directory, attaching each entry to the `link' pointer. */ 543 adjaddr = NULL; 544 for (head = NULL, nitems = 0; dp = readdir(dirp);) { 545 if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name)) 546 continue; 547 548 if ((p = fts_alloc(sp, dp->d_name, (int)dp->d_namlen)) == NULL) 549 goto mem1; 550 if (dp->d_namlen > maxlen) { 551 if (fts_palloc(sp, (int)dp->d_namlen)) { 552 /* 553 * No more memory for path or structures. Save 554 * errno, free up the current structure and the 555 * structures already allocated. 556 */ 557 mem1: saved_errno = errno; 558 if (p) 559 free(p); 560 fts_lfree(head); 561 (void)closedir(dirp); 562 errno = saved_errno; 563 cur->fts_info = FTS_ERR; 564 SET(FTS_STOP); 565 return (NULL); 566 } 567 adjaddr = sp->fts_path; 568 maxlen = sp->fts_pathlen - sp->fts_cur->fts_pathlen - 1; 569 } 570 571 p->fts_pathlen = len + dp->d_namlen + 1; 572 p->fts_parent = sp->fts_cur; 573 p->fts_level = level; 574 575 if (nlinks) { 576 /* Build a file name for fts_stat to stat. */ 577 if (ISSET(FTS_NOCHDIR)) { 578 p->fts_accpath = p->fts_path; 579 bcopy(p->fts_name, cp, p->fts_namelen + 1); 580 } else 581 p->fts_accpath = p->fts_name; 582 p->fts_info = fts_stat(sp, p, 0); 583 if (nlinks > 0 && (p->fts_info == FTS_D || 584 p->fts_info == FTS_DC || p->fts_info == FTS_DOT)) 585 --nlinks; 586 } else if (cderr) { 587 p->fts_info = ISSET(FTS_NOSTAT) ? FTS_NSOK : FTS_NS; 588 p->fts_accpath = cur->fts_accpath; 589 } else { 590 p->fts_accpath = 591 ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name; 592 p->fts_info = FTS_NSOK; 593 } 594 595 p->fts_link = head; 596 head = p; 597 ++nitems; 598 } 599 (void)closedir(dirp); 600 601 /* 602 * If had to realloc the path, adjust the addresses for the rest 603 * of the tree. 604 */ 605 if (adjaddr) 606 fts_padjust(sp, adjaddr); 607 608 /* 609 * If not changing directories, reset the path back to original 610 * state. 611 */ 612 if (ISSET(FTS_NOCHDIR)) { 613 if (cp - 1 > sp->fts_path) 614 --cp; 615 *cp = '\0'; 616 } 617 618 /* 619 * If descended after called from fts_children or called from 620 * fts_read and didn't find anything, get back. If can't get 621 * back, done. 622 */ 623 if (descend && (!nitems || type == BCHILD) && CHDIR(sp, "..")) { 624 cur->fts_info = FTS_ERR; 625 SET(FTS_STOP); 626 return (NULL); 627 } 628 629 /* If didn't find anything, just do the post-order visit */ 630 if (!nitems) { 631 if (type == BREAD) 632 cur->fts_info = FTS_DP; 633 return (NULL); 634 } 635 636 /* Sort the entries. */ 637 if (sp->fts_compar && nitems > 1) 638 head = fts_sort(sp, head, nitems); 639 return (head); 640 } 641 642 static u_short 643 fts_stat(sp, p, follow) 644 FTS *sp; 645 register FTSENT *p; 646 int follow; 647 { 648 register FTSENT *t; 649 register dev_t dev; 650 register ino_t ino; 651 struct stat *sbp, sb; 652 int saved_errno; 653 654 /* If user needs stat info, stat buffer already allocated. */ 655 sbp = ISSET(FTS_NOSTAT) ? &sb : p->fts_statp; 656 657 /* 658 * If doing a logical walk, or application requested FTS_FOLLOW, do 659 * a stat(2). If that fails, check for a non-existent symlink. If 660 * fail, set the errno from the stat call. 661 */ 662 if (ISSET(FTS_LOGICAL) || follow) { 663 if (stat(p->fts_accpath, sbp)) { 664 saved_errno = errno; 665 if (!lstat(p->fts_accpath, sbp)) { 666 errno = 0; 667 return (FTS_SLNONE); 668 } 669 p->fts_errno = saved_errno; 670 goto err; 671 } 672 } else if (lstat(p->fts_accpath, sbp)) { 673 p->fts_errno = errno; 674 err: bzero(sbp, sizeof(struct stat)); 675 return (FTS_NS); 676 } 677 678 if (S_ISDIR(sbp->st_mode)) { 679 if (ISDOT(p->fts_name)) 680 return (FTS_DOT); 681 /* 682 * Set the device/inode. Used to find cycles and check for 683 * crossing mount points. Also remember the link count, used 684 * in fts_build to limit the number of stat calls. It is 685 * understood that these fields are only referenced if fts_info 686 * is set to FTS_D. 687 */ 688 dev = p->fts_dev = sbp->st_dev; 689 ino = p->fts_ino = sbp->st_ino; 690 p->fts_nlink = sbp->st_nlink; 691 692 /* 693 * Cycle detection is done by brute force when the directory 694 * is first encountered. If the tree gets deep enough or the 695 * number of symbolic links to directories is high enough, 696 * something faster might be worthwhile. 697 */ 698 for (t = p->fts_parent; 699 t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent) 700 if (ino == t->fts_ino && dev == t->fts_dev) { 701 p->fts_cycle = t; 702 return (FTS_DC); 703 } 704 return (FTS_D); 705 } 706 if (S_ISLNK(sbp->st_mode)) 707 return (FTS_SL); 708 if (S_ISREG(sbp->st_mode)) 709 return (FTS_F); 710 return (FTS_DEFAULT); 711 } 712 713 static FTSENT * 714 fts_sort(sp, head, nitems) 715 FTS *sp; 716 FTSENT *head; 717 register int nitems; 718 { 719 register FTSENT **ap, *p; 720 721 /* 722 * Construct an array of pointers to the structures and call qsort(3). 723 * Reassemble the array in the order returned by qsort. If unable to 724 * sort for memory reasons, return the directory entries in their 725 * current order. Allocate enough space for the current needs plus 726 * 40 so don't realloc one entry at a time. 727 */ 728 if (nitems > sp->fts_nitems) { 729 sp->fts_nitems = nitems + 40; 730 if ((sp->fts_array = realloc(sp->fts_array, 731 (size_t)(sp->fts_nitems * sizeof(FTSENT *)))) == NULL) { 732 sp->fts_nitems = 0; 733 return (head); 734 } 735 } 736 for (ap = sp->fts_array, p = head; p; p = p->fts_link) 737 *ap++ = p; 738 qsort((void *)sp->fts_array, nitems, sizeof(FTSENT *), sp->fts_compar); 739 for (head = *(ap = sp->fts_array); --nitems; ++ap) 740 ap[0]->fts_link = ap[1]; 741 ap[0]->fts_link = NULL; 742 return (head); 743 } 744 745 static FTSENT * 746 fts_alloc(sp, name, len) 747 FTS *sp; 748 char *name; 749 register int len; 750 { 751 register FTSENT *p; 752 int needstat; 753 754 /* 755 * Variable sized structures. The stat structure isn't necessary 756 * if the user doesn't need it, and the name is variable length. 757 * Allocate enough extra space after the structure to store them. 758 */ 759 needstat = ISSET(FTS_NOSTAT) ? 0 : sizeof(struct stat); 760 if ((p = malloc((size_t)(sizeof(FTSENT) + len + 1 + needstat))) == NULL) 761 return (NULL); 762 bcopy(name, p->fts_name, len + 1); 763 if (needstat) 764 p->fts_statp = (struct stat *)(p->fts_name + len + 1); 765 p->fts_namelen = len; 766 p->fts_path = sp->fts_path; 767 p->fts_instr = FTS_NOINSTR; 768 p->fts_errno = 0; 769 p->fts_number = 0; 770 #ifdef NOT_NECESSARY 771 p->fts_pointer = NULL; 772 #endif 773 return (p); 774 } 775 776 static void 777 fts_lfree(head) 778 register FTSENT *head; 779 { 780 register FTSENT *p; 781 782 /* Free a linked list of structures. */ 783 while (p = head) { 784 head = head->fts_link; 785 free(p); 786 } 787 } 788 789 /* 790 * Allow essentially unlimited paths; find, rm, ls should all work on any tree. 791 * Most systems will allow creation of paths much longer than MAXPATHLEN, even 792 * though the kernel won't resolve them. Add the size (not just what's needed) 793 * plus 256 bytes so don't realloc the path 2 bytes at a time. 794 */ 795 static int 796 fts_palloc(sp, more) 797 FTS *sp; 798 int more; 799 { 800 801 sp->fts_pathlen += more + 256; 802 sp->fts_path = realloc(sp->fts_path, (size_t)sp->fts_pathlen); 803 return (sp->fts_path == NULL); 804 } 805 806 /* 807 * When the path is realloc'd, have to fix all of the pointers in structures 808 * already returned. 809 */ 810 static void 811 fts_padjust(sp, addr) 812 FTS *sp; 813 void *addr; 814 { 815 FTSENT *p; 816 817 #define ADJUST(p) { \ 818 (p)->fts_accpath = addr + ((p)->fts_accpath - (p)->fts_path); \ 819 (p)->fts_path = addr; \ 820 } 821 /* Adjust the current set of children. */ 822 for (p = sp->fts_child; p; p = p->fts_link) 823 ADJUST(p); 824 825 /* Adjust the rest of the tree. */ 826 for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) { 827 ADJUST(p); 828 p = p->fts_link ? p->fts_link : p->fts_parent; 829 } 830 } 831