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