1 /*- 2 * Copyright (c) 1990 The Regents of the University of California. 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 3. All advertising materials mentioning features or use of this software 14 * must display the following acknowledgement: 15 * This product includes software developed by the University of 16 * California, Berkeley and its contributors. 17 * 4. Neither the name of the University nor the names of its contributors 18 * may be used to endorse or promote products derived from this software 19 * without specific prior written permission. 20 * 21 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 22 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 24 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 25 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 31 * SUCH DAMAGE. 32 */ 33 34 #if defined(LIBC_SCCS) && !defined(lint) 35 static char sccsid[] = "@(#)fts.c 5.19 (Berkeley) 5/9/91"; 36 #endif /* LIBC_SCCS and not lint */ 37 38 #include <sys/cdefs.h> 39 #include <sys/param.h> 40 #include <sys/stat.h> 41 #include <fcntl.h> 42 #include <dirent.h> 43 #include <errno.h> 44 #include "fts.h" 45 #include <stdlib.h> 46 #include <string.h> 47 #include <unistd.h> 48 49 static FTSENT *fts_alloc(), *fts_build(), *fts_sort(); 50 static void fts_load(), fts_lfree(); 51 static u_short fts_stat(); 52 static char *fts_path(); 53 54 #define ISSET(opt) (sp->fts_options & opt) 55 #define SET(opt) (sp->fts_options |= opt) 56 57 #define CHDIR(sp, path) (!ISSET(FTS_NOCHDIR) && chdir(path)) 58 #define FCHDIR(sp, fd) (!ISSET(FTS_NOCHDIR) && fchdir(fd)) 59 60 /* fts_build flags */ 61 #define BCHILD 1 /* from fts_children */ 62 #define BREAD 2 /* from fts_read */ 63 64 FTS * 65 fts_open(argv, options, compar) 66 char * const *argv; 67 register int options; 68 int (*compar)(); 69 { 70 register FTS *sp; 71 register FTSENT *p, *root; 72 register int nitems, maxlen; 73 FTSENT *parent, *tmp; 74 int len; 75 76 /* Allocate/initialize the stream */ 77 if (!(sp = (FTS *)malloc((u_int)sizeof(FTS)))) 78 return(NULL); 79 bzero(sp, sizeof(FTS)); 80 sp->fts_compar = compar; 81 sp->fts_options = options; 82 83 /* Logical walks turn on NOCHDIR; symbolic links are too hard. */ 84 if (ISSET(FTS_LOGICAL)) 85 SET(FTS_NOCHDIR); 86 87 /* Allocate/initialize root's parent. */ 88 if (!(parent = fts_alloc(sp, "", 0))) 89 goto mem1; 90 parent->fts_level = FTS_ROOTPARENTLEVEL; 91 92 /* Allocate/initialize root(s). */ 93 maxlen = -1; 94 for (root = NULL, nitems = 0; *argv; ++argv, ++nitems) { 95 if (!(len = strlen(*argv))) { 96 errno = ENOENT; 97 goto mem2; 98 } 99 if (maxlen < len) 100 maxlen = len; 101 p = fts_alloc(sp, *argv, len); 102 p->fts_level = FTS_ROOTLEVEL; 103 p->fts_parent = parent; 104 /* 105 * If comparison routine supplied, traverse in sorted 106 * order; otherwise traverse in the order specified. 107 */ 108 if (compar) { 109 p->fts_link = root; 110 root = p; 111 p->fts_accpath = p->fts_name; 112 if (!(options & FTS_NOSTAT)) 113 p->fts_info = fts_stat(sp, p, 0); 114 } else { 115 p->fts_link = NULL; 116 if (!root) 117 tmp = root = p; 118 else { 119 tmp->fts_link = p; 120 tmp = p; 121 } 122 } 123 } 124 if (compar && nitems > 1) 125 root = fts_sort(sp, root, nitems); 126 127 /* 128 * Allocate a dummy pointer and make fts_read think that we've just 129 * finished the node before the root(s); set p->fts_info to FTS_NS 130 * so that everything about the "current" node is ignored. 131 */ 132 if (!(sp->fts_cur = fts_alloc(sp, "", 0))) 133 goto mem2; 134 sp->fts_cur->fts_link = root; 135 sp->fts_cur->fts_info = FTS_NS; 136 137 /* Start out with at least 1K+ of path space. */ 138 if (!fts_path(sp, MAX(maxlen, MAXPATHLEN))) 139 goto mem3; 140 141 /* 142 * If using chdir(2), grab a file descriptor pointing to dot to insure 143 * that we can get back here; this could be avoided for some paths, 144 * but almost certainly not worth the effort. Slashes, symbolic links, 145 * and ".." are all fairly nasty problems. Note, if we can't get the 146 * descriptor we run anyway, just more slowly. 147 */ 148 if (!ISSET(FTS_NOCHDIR) && (sp->fts_rfd = open(".", O_RDONLY, 0)) < 0) 149 SET(FTS_NOCHDIR); 150 151 return(sp); 152 153 mem3: free(sp->fts_cur); 154 mem2: fts_lfree(root); 155 free(parent); 156 mem1: free(sp); 157 return(NULL); 158 } 159 160 static void 161 fts_load(sp, p) 162 FTS *sp; 163 register FTSENT *p; 164 { 165 register int len; 166 register char *cp; 167 168 /* 169 * Load the stream structure for the next traversal. Since we don't 170 * actually enter the directory until after the preorder visit, set 171 * the fts_accpath field specially so the chdir gets done to the right 172 * place and the user can access the first node. 173 */ 174 len = p->fts_pathlen = p->fts_namelen; 175 bcopy(p->fts_name, sp->fts_path, len + 1); 176 if ((cp = rindex(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) { 177 len = strlen(++cp); 178 bcopy(cp, p->fts_name, len + 1); 179 p->fts_namelen = len; 180 } 181 p->fts_accpath = p->fts_path = sp->fts_path; 182 183 p->fts_info = fts_stat(sp, p, 0); 184 sp->rdev = p->fts_statb.st_dev; 185 } 186 187 fts_close(sp) 188 FTS *sp; 189 { 190 register FTSENT *freep, *p; 191 int saved_errno; 192 193 if (sp->fts_cur) { 194 /* 195 * This still works if we haven't read anything -- the dummy 196 * structure points to the root list, so we step through to 197 * the end of the root list which has a valid parent pointer. 198 */ 199 for (p = sp->fts_cur; p->fts_level > FTS_ROOTPARENTLEVEL;) { 200 freep = p; 201 p = p->fts_link ? p->fts_link : p->fts_parent; 202 free(freep); 203 } 204 free(p); 205 } 206 207 /* Free up child linked list, sort array, path buffer. */ 208 if (sp->fts_child) 209 fts_lfree(sp->fts_child); 210 if (sp->fts_array) 211 free(sp->fts_array); 212 free(sp->fts_path); 213 214 /* Return to original directory, save errno if necessary. */ 215 if (!ISSET(FTS_NOCHDIR)) { 216 saved_errno = fchdir(sp->fts_rfd) ? errno : 0; 217 (void)close(sp->fts_rfd); 218 } 219 220 /* Free up the stream pointer. */ 221 free(sp); 222 223 /* Set errno and return. */ 224 if (!ISSET(FTS_NOCHDIR) && saved_errno) { 225 errno = saved_errno; 226 return(-1); 227 } 228 return(0); 229 } 230 231 /* 232 * Special case a root of "/" so that slashes aren't appended causing 233 * paths to be written as "//foo". 234 */ 235 #define NAPPEND(p) \ 236 (p->fts_level == FTS_ROOTLEVEL && p->fts_pathlen == 1 && \ 237 p->fts_path[0] == '/' ? 0 : p->fts_pathlen) 238 239 FTSENT * 240 fts_read(sp) 241 register FTS *sp; 242 { 243 register FTSENT *p, *tmp; 244 register int instr; 245 register char *t; 246 247 /* If finished or unrecoverable error, return NULL. */ 248 if (!sp->fts_cur || ISSET(FTS_STOP)) 249 return(NULL); 250 251 /* Set current node pointer. */ 252 p = sp->fts_cur; 253 254 /* Save and zero out user instructions. */ 255 instr = p->fts_instr; 256 p->fts_instr = FTS_NOINSTR; 257 258 /* If used fts_link pointer for cycle detection, restore it. */ 259 if (sp->fts_savelink) { 260 p->fts_link = sp->fts_savelink; 261 sp->fts_savelink = NULL; 262 } 263 264 /* Any type of file may be re-visited; re-stat and re-turn. */ 265 if (instr == FTS_AGAIN) { 266 p->fts_info = fts_stat(sp, p, 0); 267 return(p); 268 } 269 270 /* 271 * Following a symlink -- SLNONE test allows application to see 272 * SLNONE and recover. 273 */ 274 if (instr == FTS_FOLLOW && 275 (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) { 276 p->fts_info = fts_stat(sp, p, 1); 277 return(p); 278 } 279 280 /* Directory in pre-order. */ 281 if (p->fts_info == FTS_D) { 282 /* If skipped or crossed mount point, do post-order visit. */ 283 if (instr == FTS_SKIP || 284 ISSET(FTS_XDEV) && p->fts_statb.st_dev != sp->rdev) { 285 if (sp->fts_child) { 286 fts_lfree(sp->fts_child); 287 sp->fts_child = NULL; 288 } 289 p->fts_info = FTS_DP; 290 return(p); 291 } 292 293 /* 294 * Cd to the subdirectory, reading it if haven't already. If 295 * the read fails for any reason, or the directory is empty, 296 * the fts_info field of the current node is set by fts_build. 297 * If have already read and now fail to chdir, whack the list 298 * to make the names come out right, and set the parent state 299 * so the application will eventually get an error condition. 300 * If haven't read and fail to chdir, check to see if we're 301 * at the root node -- if so, we have to get back or the root 302 * node may be inaccessible. 303 */ 304 if (sp->fts_child) { 305 if (CHDIR(sp, p->fts_accpath)) { 306 p->fts_parent->fts_cderr = errno; 307 for (p = sp->fts_child; p; p = p->fts_link) 308 p->fts_accpath = 309 p->fts_parent->fts_accpath; 310 } 311 } else if (!(sp->fts_child = fts_build(sp, BREAD))) { 312 if ISSET(FTS_STOP) 313 return(NULL); 314 if (p->fts_level == FTS_ROOTLEVEL && 315 FCHDIR(sp, sp->fts_rfd)) { 316 SET(FTS_STOP); 317 return(NULL); 318 } 319 return(p); 320 } 321 p = sp->fts_child; 322 sp->fts_child = NULL; 323 goto name; 324 } 325 326 /* Move to next node on this level. */ 327 next: tmp = p; 328 if (p = p->fts_link) { 329 free(tmp); 330 331 /* If reached the top, load the paths for the next root. */ 332 if (p->fts_level == FTS_ROOTLEVEL) { 333 fts_load(sp, p); 334 return(sp->fts_cur = p); 335 } 336 337 /* User may have called fts_set on the node. */ 338 if (p->fts_instr == FTS_SKIP) 339 goto next; 340 if (p->fts_instr == FTS_FOLLOW) { 341 p->fts_info = fts_stat(sp, p, 1); 342 p->fts_instr = FTS_NOINSTR; 343 } 344 345 name: t = sp->fts_path + NAPPEND(p->fts_parent); 346 *t++ = '/'; 347 bcopy(p->fts_name, t, p->fts_namelen + 1); 348 return(sp->fts_cur = p); 349 } 350 351 /* Move up to the parent node. */ 352 p = tmp->fts_parent; 353 free(tmp); 354 355 if (p->fts_level == FTS_ROOTPARENTLEVEL) { 356 /* 357 * Done; free everything up and set errno to 0 so the user 358 * can distinguish between error and EOF. 359 */ 360 free(p); 361 errno = 0; 362 return(sp->fts_cur = NULL); 363 } 364 365 sp->fts_path[p->fts_pathlen] = '\0'; 366 367 /* 368 * Cd back up to the parent directory. If at a root node, have to cd 369 * back to the original place, otherwise may not be able to access the 370 * original node on post-order. 371 */ 372 if (p->fts_level == FTS_ROOTLEVEL) { 373 if (FCHDIR(sp, sp->fts_rfd)) { 374 SET(FTS_STOP); 375 return(NULL); 376 } 377 } 378 else if (CHDIR(sp, "..")) { 379 SET(FTS_STOP); 380 return(NULL); 381 } 382 383 /* 384 * If had a chdir error when trying to get into the directory, set the 385 * info field to reflect this, and restore errno. The error indicator 386 * has to be reset to 0 so that if the user does an FTS_AGAIN, it all 387 * works. 388 */ 389 if (p->fts_cderr) { 390 errno = p->fts_cderr; 391 p->fts_cderr = 0; 392 p->fts_info = FTS_ERR; 393 } else 394 p->fts_info = FTS_DP; 395 return(sp->fts_cur = p); 396 } 397 398 /* 399 * Fts_set takes the stream as an argument although it's not used in this 400 * implementation; it would be necessary if anyone wanted to add global 401 * semantics to fts using fts_set. An error return is allowed for similar 402 * reasons. 403 */ 404 /* ARGSUSED */ 405 fts_set(sp, p, instr) 406 FTS *sp; 407 FTSENT *p; 408 int instr; 409 { 410 p->fts_instr = instr; 411 return(0); 412 } 413 414 FTSENT * 415 fts_children(sp) 416 register FTS *sp; 417 { 418 register FTSENT *p; 419 int fd; 420 421 /* Set current node pointer. */ 422 p = sp->fts_cur; 423 424 /* 425 * Set errno to 0 so that user can tell the difference between an 426 * error and a directory without entries. If not a directory being 427 * visited in *pre-order*, or we've already had fatal errors, return 428 * immediately. 429 */ 430 errno = 0; 431 if (ISSET(FTS_STOP) || p->fts_info != FTS_D && p->fts_info != FTS_DNR) 432 return(NULL); 433 434 /* Free up any previous child list. */ 435 if (sp->fts_child) 436 fts_lfree(sp->fts_child); 437 438 /* 439 * If using chdir on a relative path and called BEFORE fts_read does 440 * its chdir to the root of a traversal, we can lose -- we need to 441 * chdir into the subdirectory, and we don't know where the current 442 * directory is, so we can't get back so that the upcoming chdir by 443 * fts_read will work. 444 */ 445 if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' || 446 ISSET(FTS_NOCHDIR)) 447 return(sp->fts_child = fts_build(sp, BCHILD)); 448 449 if ((fd = open(".", O_RDONLY, 0)) < 0) 450 return(NULL); 451 sp->fts_child = fts_build(sp, BCHILD); 452 if (fchdir(fd)) 453 return(NULL); 454 (void)close(fd); 455 return(sp->fts_child); 456 } 457 458 /* 459 * This is the tricky part -- do not casually change *anything* in here. The 460 * idea is to build the linked list of entries that are used by fts_children 461 * and fts_read. There are lots of special cases. 462 * 463 * The real slowdown in walking the tree is the stat calls. If FTS_NOSTAT is 464 * set and it's a physical walk (so that symbolic links can't be directories), 465 * we assume that the number of subdirectories in a node is equal to the number 466 * of links to the parent. This allows stat calls to be skipped in any leaf 467 * directories and for any nodes after the directories in the parent node have 468 * been found. This empirically cuts the stat calls by about 2/3. 469 */ 470 #define ISDOT(a) (a[0] == '.' && (!a[1] || a[1] == '.' && !a[2])) 471 472 static FTSENT * 473 fts_build(sp, type) 474 register FTS *sp; 475 int type; 476 { 477 register struct dirent *dp; 478 register FTSENT *p, *head; 479 register int nitems; 480 FTSENT *cur; 481 DIR *dirp; 482 int cderr, descend, len, level, maxlen, nlinks, saved_errno; 483 char *cp; 484 485 /* Set current node pointer. */ 486 cur = sp->fts_cur; 487 488 /* 489 * Open the directory for reading. If this fails, we're done. 490 * If being called from fts_read, set the fts_info field. 491 */ 492 if (!(dirp = opendir(cur->fts_accpath))) { 493 if (type == BREAD) 494 cur->fts_info = FTS_DNR; 495 return(NULL); 496 } 497 498 /* 499 * Nlinks is the number of possible entries of type directory in the 500 * directory if we're cheating on stat calls, 0 if we're not doing 501 * any stat calls at all, -1 if we're doing stats on everything. 502 */ 503 nlinks = 504 ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL) ? 505 cur->fts_statb.st_nlink - (ISSET(FTS_SEEDOT) ? 0 : 2) : -1; 506 507 /* 508 * If we're going to need to stat anything or we want to descend 509 * and stay in the directory, chdir. If this fails we keep going. 510 * We won't be able to stat anything, but we can still return the 511 * names themselves. Note, that since fts_read won't be able to 512 * chdir into the directory, it will have to return different path 513 * names than before, i.e. "a/b" instead of "b". Since the node 514 * has already been visited in pre-order, have to wait until the 515 * post-order visit to return the error. This is all fairly nasty. 516 * If a program needed sorted entries or stat information, they had 517 * better be checking FTS_NS on the returned nodes. 518 */ 519 if (nlinks || type == BREAD) 520 if (FCHDIR(sp, dirfd(dirp))) { 521 if (type == BREAD) 522 cur->fts_cderr = errno; 523 descend = nlinks = 0; 524 cderr = 1; 525 } else { 526 descend = 1; 527 cderr = 0; 528 } 529 else 530 descend = 0; 531 532 /* 533 * Figure out the max file name length that can be stored in the 534 * current path -- the inner loop allocates more path as necessary. 535 * We really wouldn't have to do the maxlen calculations here, we 536 * could do them in fts_read before returning the path, but it's a 537 * lot easier here since the length is part of the dirent structure. 538 * 539 * If not changing directories set a pointer so that we can just 540 * append each new name into the path. 541 */ 542 maxlen = sp->fts_pathlen - cur->fts_pathlen - 1; 543 len = NAPPEND(cur); 544 if (ISSET(FTS_NOCHDIR)) { 545 cp = sp->fts_path + len; 546 *cp++ = '/'; 547 } 548 549 level = cur->fts_level + 1; 550 551 /* Read the directory, attaching each entry to the `link' pointer. */ 552 for (head = NULL, nitems = 0; dp = readdir(dirp);) { 553 if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name)) 554 continue; 555 556 if (!(p = fts_alloc(sp, dp->d_name, (int)dp->d_namlen))) 557 goto mem1; 558 if (dp->d_namlen > maxlen) { 559 if (!fts_path(sp, (int)dp->d_namlen)) { 560 /* 561 * No more memory for path or structures. Save 562 * errno, free up the current structure and the 563 * structures already allocated. 564 */ 565 mem1: saved_errno = errno; 566 if (p) 567 free(p); 568 fts_lfree(head); 569 (void)closedir(dirp); 570 errno = saved_errno; 571 cur->fts_info = FTS_ERR; 572 SET(FTS_STOP); 573 return(NULL); 574 } 575 maxlen = sp->fts_pathlen - sp->fts_cur->fts_pathlen - 1; 576 } 577 578 p->fts_pathlen = len + dp->d_namlen + 1; 579 p->fts_parent = sp->fts_cur; 580 p->fts_level = level; 581 582 if (nlinks) { 583 /* Build a file name for fts_stat to stat. */ 584 if (ISSET(FTS_NOCHDIR)) { 585 p->fts_accpath = p->fts_path; 586 bcopy(p->fts_name, cp, p->fts_namelen + 1); 587 } else 588 p->fts_accpath = p->fts_name; 589 p->fts_info = fts_stat(sp, p, 0); 590 if (nlinks > 0 && p->fts_info == FTS_D) 591 --nlinks; 592 } else if (cderr) { 593 p->fts_info = ISSET(FTS_NOSTAT) ? FTS_NSOK : FTS_NS; 594 p->fts_accpath = cur->fts_accpath; 595 } else { 596 p->fts_accpath = 597 ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name; 598 p->fts_info = FTS_NSOK; 599 } 600 601 p->fts_link = head; 602 head = p; 603 ++nitems; 604 } 605 (void)closedir(dirp); 606 607 /* 608 * If not changing directories, reset the path back to original 609 * state. 610 */ 611 if (ISSET(FTS_NOCHDIR)) { 612 if (cp - 1 > sp->fts_path) 613 --cp; 614 *cp = '\0'; 615 } 616 617 /* 618 * If descended after called from fts_children or called from 619 * fts_read and didn't find anything, get back. If can't get 620 * back, we're done. 621 */ 622 if (descend && (!nitems || type == BCHILD) && CHDIR(sp, "..")) { 623 cur->fts_info = FTS_ERR; 624 SET(FTS_STOP); 625 return(NULL); 626 } 627 628 /* If we didn't find anything, just do the post-order visit */ 629 if (!nitems) { 630 if (type == BREAD) 631 cur->fts_info = FTS_DP; 632 return(NULL); 633 } 634 635 /* Sort the entries. */ 636 if (sp->fts_compar && nitems > 1) 637 head = fts_sort(sp, head, nitems); 638 return(head); 639 } 640 641 static u_short 642 fts_stat(sp, p, follow) 643 FTS *sp; 644 register FTSENT *p; 645 int follow; 646 { 647 int saved_errno; 648 649 /* 650 * If doing a logical walk, or application requested FTS_FOLLOW, do 651 * a stat(2). If that fails, check for a non-existent symlink. If 652 * fail, return the errno from the stat call. 653 */ 654 if (ISSET(FTS_LOGICAL) || follow) { 655 if (stat(p->fts_accpath, &p->fts_statb)) { 656 saved_errno = errno; 657 if (!lstat(p->fts_accpath, &p->fts_statb)) { 658 errno = 0; 659 return(FTS_SLNONE); 660 } 661 errno = saved_errno; 662 bzero(&p->fts_statb, sizeof(struct stat)); 663 return(FTS_NS); 664 } 665 } else if (lstat(p->fts_accpath, &p->fts_statb)) { 666 bzero(&p->fts_statb, sizeof(struct stat)); 667 return(FTS_NS); 668 } 669 670 /* 671 * Cycle detection is done as soon as we find a directory. Detection 672 * is by brute force; if the tree gets deep enough or the number of 673 * symbolic links to directories high enough something faster might 674 * be worthwhile. 675 */ 676 if (S_ISDIR(p->fts_statb.st_mode)) { 677 register FTSENT *t; 678 register dev_t dev; 679 register ino_t ino; 680 681 dev = p->fts_statb.st_dev; 682 ino = p->fts_statb.st_ino; 683 for (t = p->fts_parent; t->fts_level > FTS_ROOTLEVEL; 684 t = t->fts_parent) 685 if (ino == t->fts_statb.st_ino && 686 dev == t->fts_statb.st_dev) { 687 sp->fts_savelink = p->fts_link; 688 p->fts_link = t; 689 return(FTS_DC); 690 } 691 return(FTS_D); 692 } 693 if (S_ISLNK(p->fts_statb.st_mode)) 694 return(FTS_SL); 695 if (S_ISREG(p->fts_statb.st_mode)) 696 return(FTS_F); 697 return(FTS_DEFAULT); 698 } 699 700 #define R(type, nelem, ptr) \ 701 (type *)realloc((void *)ptr, (u_int)((nelem) * sizeof(type))) 702 703 static FTSENT * 704 fts_sort(sp, head, nitems) 705 FTS *sp; 706 FTSENT *head; 707 register int nitems; 708 { 709 register FTSENT **ap, *p; 710 711 /* 712 * Construct an array of pointers to the structures and call qsort(3). 713 * Reassemble the array in the order returned by qsort. If unable to 714 * sort for memory reasons, return the directory entries in their 715 * current order. Allocate enough space for the current needs plus 716 * 40 so we don't realloc one entry at a time. 717 */ 718 if (nitems > sp->fts_nitems) { 719 sp->fts_nitems = nitems + 40; 720 if (!(sp->fts_array = 721 R(FTSENT *, sp->fts_nitems, sp->fts_array))) { 722 sp->fts_nitems = 0; 723 return(head); 724 } 725 } 726 for (ap = sp->fts_array, p = head; p; p = p->fts_link) 727 *ap++ = p; 728 qsort((void *)sp->fts_array, nitems, sizeof(FTSENT *), sp->fts_compar); 729 for (head = *(ap = sp->fts_array); --nitems; ++ap) 730 ap[0]->fts_link = ap[1]; 731 ap[0]->fts_link = NULL; 732 return(head); 733 } 734 735 static FTSENT * 736 fts_alloc(sp, name, len) 737 FTS *sp; 738 char *name; 739 register int len; 740 { 741 register FTSENT *p; 742 743 /* 744 * Variable sized structures; the name is the last element so 745 * we allocate enough extra space after the structure to store 746 * it. 747 */ 748 if (!(p = (FTSENT *)malloc((size_t)(sizeof(FTSENT) + len)))) 749 return(NULL); 750 bcopy(name, p->fts_name, len + 1); 751 p->fts_namelen = len; 752 p->fts_path = sp->fts_path; 753 p->fts_instr = FTS_NOINSTR; 754 p->fts_cderr = 0; 755 p->fts_number = 0; 756 p->fts_pointer = NULL; 757 return(p); 758 } 759 760 static void 761 fts_lfree(head) 762 register FTSENT *head; 763 { 764 register FTSENT *p; 765 766 /* Free a linked list of structures. */ 767 while (p = head) { 768 head = head->fts_link; 769 free(p); 770 } 771 } 772 773 /* 774 * Allow essentially unlimited paths; certain programs (find, rm, ls) need to 775 * work on any tree. Most systems will allow creation of paths much longer 776 * than MAXPATHLEN, even though the kernel won't resolve them. Add an extra 777 * 128 bytes to the requested size so that we don't realloc the path 2 bytes 778 * at a time. 779 */ 780 static char * 781 fts_path(sp, size) 782 FTS *sp; 783 int size; 784 { 785 sp->fts_pathlen += size + 128; 786 return(sp->fts_path = R(char, sp->fts_pathlen, sp->fts_path)); 787 } 788