fts.c revision 1.14
1/* $NetBSD: fts.c,v 1.14 1997/07/13 18:59:02 christos Exp $ */ 2 3/*- 4 * Copyright (c) 1990, 1993, 1994 5 * The Regents of the University of California. All rights reserved. 6 * 7 * Redistribution and use in source and binary forms, with or without 8 * modification, are permitted provided that the following conditions 9 * are met: 10 * 1. Redistributions of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 2. Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 3. All advertising materials mentioning features or use of this software 16 * must display the following acknowledgement: 17 * This product includes software developed by the University of 18 * California, Berkeley and its contributors. 19 * 4. Neither the name of the University nor the names of its contributors 20 * may be used to endorse or promote products derived from this software 21 * without specific prior written permission. 22 * 23 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 24 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 25 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 26 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 27 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 28 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 29 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 30 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 31 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 32 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 33 * SUCH DAMAGE. 34 */ 35 36#include <sys/cdefs.h> 37#if defined(LIBC_SCCS) && !defined(lint) 38#if 0 39static char sccsid[] = "@(#)fts.c 8.4 (Berkeley) 4/16/94"; 40#else 41__RCSID("$NetBSD: fts.c,v 1.14 1997/07/13 18:59:02 christos Exp $"); 42#endif 43#endif /* LIBC_SCCS and not lint */ 44 45#include <sys/param.h> 46#include <sys/stat.h> 47 48#include <dirent.h> 49#include <errno.h> 50#include <fcntl.h> 51#include <fts.h> 52#include <stdlib.h> 53#include <string.h> 54#include <unistd.h> 55 56static FTSENT *fts_alloc __P((FTS *, char *, int)); 57static FTSENT *fts_build __P((FTS *, int)); 58static void fts_lfree __P((FTSENT *)); 59static void fts_load __P((FTS *, FTSENT *)); 60static size_t fts_maxarglen __P((char * const *)); 61static void fts_padjust __P((FTS *, void *)); 62static int fts_palloc __P((FTS *, size_t)); 63static FTSENT *fts_sort __P((FTS *, FTSENT *, int)); 64static u_short fts_stat __P((FTS *, FTSENT *, int)); 65 66#define ISDOT(a) (a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2]))) 67 68#define CLR(opt) (sp->fts_options &= ~(opt)) 69#define ISSET(opt) (sp->fts_options & (opt)) 70#define SET(opt) (sp->fts_options |= (opt)) 71 72#define CHDIR(sp, path) (!ISSET(FTS_NOCHDIR) && chdir(path)) 73#define FCHDIR(sp, fd) (!ISSET(FTS_NOCHDIR) && fchdir(fd)) 74 75/* fts_build flags */ 76#define BCHILD 1 /* fts_children */ 77#define BNAMES 2 /* fts_children, names only */ 78#define BREAD 3 /* fts_read */ 79 80FTS * 81fts_open(argv, options, compar) 82 char * const *argv; 83 register int options; 84 int (*compar) __P((const FTSENT **, const FTSENT **)); 85{ 86 register FTS *sp; 87 register FTSENT *p, *root; 88 register int nitems; 89 FTSENT *parent, *tmp = NULL; /* pacify gcc */ 90 int len; 91 92 /* Options check. */ 93 if (options & ~FTS_OPTIONMASK) { 94 errno = EINVAL; 95 return (NULL); 96 } 97 98 /* Allocate/initialize the stream */ 99 if ((sp = malloc((u_int)sizeof(FTS))) == NULL) 100 return (NULL); 101 memset(sp, 0, sizeof(FTS)); 102 sp->fts_compar = compar; 103 sp->fts_options = options; 104 105 /* Logical walks turn on NOCHDIR; symbolic links are too hard. */ 106 if (ISSET(FTS_LOGICAL)) 107 SET(FTS_NOCHDIR); 108 109 /* 110 * Start out with 1K of path space, and enough, in any case, 111 * to hold the user's paths. 112 */ 113 if (fts_palloc(sp, MAX(fts_maxarglen(argv), MAXPATHLEN))) 114 goto mem1; 115 116 /* Allocate/initialize root's parent. */ 117 if ((parent = fts_alloc(sp, "", 0)) == NULL) 118 goto mem2; 119 parent->fts_level = FTS_ROOTPARENTLEVEL; 120 121 /* Allocate/initialize root(s). */ 122 for (root = NULL, nitems = 0; *argv; ++argv, ++nitems) { 123 /* Don't allow zero-length paths. */ 124 if ((len = strlen(*argv)) == 0) { 125 errno = ENOENT; 126 goto mem3; 127 } 128 129 p = fts_alloc(sp, *argv, len); 130 p->fts_level = FTS_ROOTLEVEL; 131 p->fts_parent = parent; 132 p->fts_accpath = p->fts_name; 133 p->fts_info = fts_stat(sp, p, ISSET(FTS_COMFOLLOW)); 134 135 /* Command-line "." and ".." are real directories. */ 136 if (p->fts_info == FTS_DOT) 137 p->fts_info = FTS_D; 138 139 /* 140 * If comparison routine supplied, traverse in sorted 141 * order; otherwise traverse in the order specified. 142 */ 143 if (compar) { 144 p->fts_link = root; 145 root = p; 146 } else { 147 p->fts_link = NULL; 148 if (root == NULL) 149 tmp = root = p; 150 else { 151 tmp->fts_link = p; 152 tmp = p; 153 } 154 } 155 } 156 if (compar && nitems > 1) 157 root = fts_sort(sp, root, nitems); 158 159 /* 160 * Allocate a dummy pointer and make fts_read think that we've just 161 * finished the node before the root(s); set p->fts_info to FTS_INIT 162 * so that everything about the "current" node is ignored. 163 */ 164 if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL) 165 goto mem3; 166 sp->fts_cur->fts_link = root; 167 sp->fts_cur->fts_info = FTS_INIT; 168 169 /* 170 * If using chdir(2), grab a file descriptor pointing to dot to insure 171 * that we can get back here; this could be avoided for some paths, 172 * but almost certainly not worth the effort. Slashes, symbolic links, 173 * and ".." are all fairly nasty problems. Note, if we can't get the 174 * descriptor we run anyway, just more slowly. 175 */ 176 if (!ISSET(FTS_NOCHDIR) && (sp->fts_rfd = open(".", O_RDONLY, 0)) < 0) 177 SET(FTS_NOCHDIR); 178 179 return (sp); 180 181mem3: fts_lfree(root); 182 free(parent); 183mem2: free(sp->fts_path); 184mem1: free(sp); 185 return (NULL); 186} 187 188static void 189fts_load(sp, p) 190 FTS *sp; 191 register FTSENT *p; 192{ 193 register int len; 194 register char *cp; 195 196 /* 197 * Load the stream structure for the next traversal. Since we don't 198 * actually enter the directory until after the preorder visit, set 199 * the fts_accpath field specially so the chdir gets done to the right 200 * place and the user can access the first node. From fts_open it's 201 * known that the path will fit. 202 */ 203 len = p->fts_pathlen = p->fts_namelen; 204 memmove(sp->fts_path, p->fts_name, len + 1); 205 if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) { 206 len = strlen(++cp); 207 memmove(p->fts_name, cp, len + 1); 208 p->fts_namelen = len; 209 } 210 p->fts_accpath = p->fts_path = sp->fts_path; 211 sp->fts_dev = p->fts_dev; 212} 213 214int 215fts_close(sp) 216 FTS *sp; 217{ 218 register FTSENT *freep, *p; 219 int saved_errno = 0; /* pacify gcc */ 220 221 /* 222 * This still works if we haven't read anything -- the dummy structure 223 * points to the root list, so we step through to the end of the root 224 * list which has a valid parent pointer. 225 */ 226 if (sp->fts_cur) { 227 for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) { 228 freep = p; 229 p = p->fts_link ? p->fts_link : p->fts_parent; 230 free(freep); 231 } 232 free(p); 233 } 234 235 /* Free up child linked list, sort array, path buffer. */ 236 if (sp->fts_child) 237 fts_lfree(sp->fts_child); 238 if (sp->fts_array) 239 free(sp->fts_array); 240 free(sp->fts_path); 241 242 /* Return to original directory, save errno if necessary. */ 243 if (!ISSET(FTS_NOCHDIR)) { 244 saved_errno = fchdir(sp->fts_rfd) ? errno : 0; 245 (void)close(sp->fts_rfd); 246 } 247 248 /* Free up the stream pointer. */ 249 free(sp); 250 251 /* Set errno and return. */ 252 if (!ISSET(FTS_NOCHDIR) && saved_errno) { 253 errno = saved_errno; 254 return (-1); 255 } 256 return (0); 257} 258 259/* 260 * Special case of "/" at the end of the path so that slashes 261 * aren't appended which would cause paths to be written as "....//foo". 262 */ 263#define NAPPEND(p) \ 264 (p->fts_path[p->fts_pathlen-1] == '/' \ 265 ? p->fts_pathlen-1 : p->fts_pathlen) 266 267FTSENT * 268fts_read(sp) 269 register FTS *sp; 270{ 271 register FTSENT *p, *tmp; 272 register int instr; 273 register char *t; 274 int saved_errno; 275 276 /* If finished or unrecoverable error, return NULL. */ 277 if (sp->fts_cur == NULL || ISSET(FTS_STOP)) 278 return (NULL); 279 280 /* Set current node pointer. */ 281 p = sp->fts_cur; 282 283 /* Save and zero out user instructions. */ 284 instr = p->fts_instr; 285 p->fts_instr = FTS_NOINSTR; 286 287 /* Any type of file may be re-visited; re-stat and re-turn. */ 288 if (instr == FTS_AGAIN) { 289 p->fts_info = fts_stat(sp, p, 0); 290 return (p); 291 } 292 293 /* 294 * Following a symlink -- SLNONE test allows application to see 295 * SLNONE and recover. If indirecting through a symlink, have 296 * keep a pointer to current location. If unable to get that 297 * pointer, follow fails. 298 */ 299 if (instr == FTS_FOLLOW && 300 (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) { 301 p->fts_info = fts_stat(sp, p, 1); 302 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) 303 if ((p->fts_symfd = open(".", O_RDONLY, 0)) < 0) { 304 p->fts_errno = errno; 305 p->fts_info = FTS_ERR; 306 } else 307 p->fts_flags |= FTS_SYMFOLLOW; 308 return (p); 309 } 310 311 /* Directory in pre-order. */ 312 if (p->fts_info == FTS_D) { 313 /* If skipped or crossed mount point, do post-order visit. */ 314 if (instr == FTS_SKIP || 315 (ISSET(FTS_XDEV) && p->fts_dev != sp->fts_dev)) { 316 if (p->fts_flags & FTS_SYMFOLLOW) 317 (void)close(p->fts_symfd); 318 if (sp->fts_child) { 319 fts_lfree(sp->fts_child); 320 sp->fts_child = NULL; 321 } 322 p->fts_info = FTS_DP; 323 return (p); 324 } 325 326 /* Rebuild if only read the names and now traversing. */ 327 if (sp->fts_child && ISSET(FTS_NAMEONLY)) { 328 CLR(FTS_NAMEONLY); 329 fts_lfree(sp->fts_child); 330 sp->fts_child = NULL; 331 } 332 333 /* 334 * Cd to the subdirectory. 335 * 336 * If have already read and now fail to chdir, whack the list 337 * to make the names come out right, and set the parent errno 338 * so the application will eventually get an error condition. 339 * Set the FTS_DONTCHDIR flag so that when we logically change 340 * directories back to the parent we don't do a chdir. 341 * 342 * If haven't read do so. If the read fails, fts_build sets 343 * FTS_STOP or the fts_info field of the node. 344 */ 345 if (sp->fts_child) { 346 if (CHDIR(sp, p->fts_accpath)) { 347 p->fts_errno = errno; 348 p->fts_flags |= FTS_DONTCHDIR; 349 for (p = sp->fts_child; p; p = p->fts_link) 350 p->fts_accpath = 351 p->fts_parent->fts_accpath; 352 } 353 } else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) { 354 if (ISSET(FTS_STOP)) 355 return (NULL); 356 return (p); 357 } 358 p = sp->fts_child; 359 sp->fts_child = NULL; 360 goto name; 361 } 362 363 /* Move to the next node on this level. */ 364next: tmp = p; 365 if ((p = p->fts_link) != NULL) { 366 free(tmp); 367 368 /* 369 * If reached the top, return to the original directory, and 370 * load the paths for the next root. 371 */ 372 if (p->fts_level == FTS_ROOTLEVEL) { 373 if (!ISSET(FTS_NOCHDIR) && FCHDIR(sp, sp->fts_rfd)) { 374 SET(FTS_STOP); 375 return (NULL); 376 } 377 fts_load(sp, p); 378 return (sp->fts_cur = p); 379 } 380 381 /* 382 * User may have called fts_set on the node. If skipped, 383 * ignore. If followed, get a file descriptor so we can 384 * get back if necessary. 385 */ 386 if (p->fts_instr == FTS_SKIP) 387 goto next; 388 if (p->fts_instr == FTS_FOLLOW) { 389 p->fts_info = fts_stat(sp, p, 1); 390 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) 391 if ((p->fts_symfd = 392 open(".", O_RDONLY, 0)) < 0) { 393 p->fts_errno = errno; 394 p->fts_info = FTS_ERR; 395 } else 396 p->fts_flags |= FTS_SYMFOLLOW; 397 p->fts_instr = FTS_NOINSTR; 398 } 399 400name: t = sp->fts_path + NAPPEND(p->fts_parent); 401 *t++ = '/'; 402 memmove(t, p->fts_name, p->fts_namelen + 1); 403 return (sp->fts_cur = p); 404 } 405 406 /* Move up to the parent node. */ 407 p = tmp->fts_parent; 408 free(tmp); 409 410 if (p->fts_level == FTS_ROOTPARENTLEVEL) { 411 /* 412 * Done; free everything up and set errno to 0 so the user 413 * can distinguish between error and EOF. 414 */ 415 free(p); 416 errno = 0; 417 return (sp->fts_cur = NULL); 418 } 419 420 /* Nul terminate the pathname. */ 421 sp->fts_path[p->fts_pathlen] = '\0'; 422 423 /* 424 * Return to the parent directory. If at a root node or came through 425 * a symlink, go back through the file descriptor. Otherwise, cd up 426 * one directory. 427 */ 428 if (p->fts_level == FTS_ROOTLEVEL) { 429 if (!ISSET(FTS_NOCHDIR) && FCHDIR(sp, sp->fts_rfd)) { 430 SET(FTS_STOP); 431 return (NULL); 432 } 433 } else if (p->fts_flags & FTS_SYMFOLLOW) { 434 if (FCHDIR(sp, p->fts_symfd)) { 435 saved_errno = errno; 436 (void)close(p->fts_symfd); 437 errno = saved_errno; 438 SET(FTS_STOP); 439 return (NULL); 440 } 441 (void)close(p->fts_symfd); 442 } else if (!(p->fts_flags & FTS_DONTCHDIR)) { 443 if (CHDIR(sp, "..")) { 444 SET(FTS_STOP); 445 return (NULL); 446 } 447 } 448 p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP; 449 return (sp->fts_cur = p); 450} 451 452/* 453 * Fts_set takes the stream as an argument although it's not used in this 454 * implementation; it would be necessary if anyone wanted to add global 455 * semantics to fts using fts_set. An error return is allowed for similar 456 * reasons. 457 */ 458/* ARGSUSED */ 459int 460fts_set(sp, p, instr) 461 FTS *sp; 462 FTSENT *p; 463 int instr; 464{ 465 if (instr && instr != FTS_AGAIN && instr != FTS_FOLLOW && 466 instr != FTS_NOINSTR && instr != FTS_SKIP) { 467 errno = EINVAL; 468 return (1); 469 } 470 p->fts_instr = instr; 471 return (0); 472} 473 474FTSENT * 475fts_children(sp, instr) 476 register FTS *sp; 477 int instr; 478{ 479 register FTSENT *p; 480 int fd; 481 482 if (instr && instr != FTS_NAMEONLY) { 483 errno = EINVAL; 484 return (NULL); 485 } 486 487 /* Set current node pointer. */ 488 p = sp->fts_cur; 489 490 /* 491 * Errno set to 0 so user can distinguish empty directory from 492 * an error. 493 */ 494 errno = 0; 495 496 /* Fatal errors stop here. */ 497 if (ISSET(FTS_STOP)) 498 return (NULL); 499 500 /* Return logical hierarchy of user's arguments. */ 501 if (p->fts_info == FTS_INIT) 502 return (p->fts_link); 503 504 /* 505 * If not a directory being visited in pre-order, stop here. Could 506 * allow FTS_DNR, assuming the user has fixed the problem, but the 507 * same effect is available with FTS_AGAIN. 508 */ 509 if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */) 510 return (NULL); 511 512 /* Free up any previous child list. */ 513 if (sp->fts_child) 514 fts_lfree(sp->fts_child); 515 516 if (instr == FTS_NAMEONLY) { 517 SET(FTS_NAMEONLY); 518 instr = BNAMES; 519 } else 520 instr = BCHILD; 521 522 /* 523 * If using chdir on a relative path and called BEFORE fts_read does 524 * its chdir to the root of a traversal, we can lose -- we need to 525 * chdir into the subdirectory, and we don't know where the current 526 * directory is, so we can't get back so that the upcoming chdir by 527 * fts_read will work. 528 */ 529 if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' || 530 ISSET(FTS_NOCHDIR)) 531 return (sp->fts_child = fts_build(sp, instr)); 532 533 if ((fd = open(".", O_RDONLY, 0)) < 0) 534 return (NULL); 535 sp->fts_child = fts_build(sp, instr); 536 if (fchdir(fd)) 537 return (NULL); 538 (void)close(fd); 539 return (sp->fts_child); 540} 541 542/* 543 * This is the tricky part -- do not casually change *anything* in here. The 544 * idea is to build the linked list of entries that are used by fts_children 545 * and fts_read. There are lots of special cases. 546 * 547 * The real slowdown in walking the tree is the stat calls. If FTS_NOSTAT is 548 * set and it's a physical walk (so that symbolic links can't be directories), 549 * we can do things quickly. First, if it's a 4.4BSD file system, the type 550 * of the file is in the directory entry. Otherwise, we assume that the number 551 * of subdirectories in a node is equal to the number of links to the parent. 552 * The former skips all stat calls. The latter skips stat calls in any leaf 553 * directories and for any files after the subdirectories in the directory have 554 * been found, cutting the stat calls by about 2/3. 555 */ 556static FTSENT * 557fts_build(sp, type) 558 register FTS *sp; 559 int type; 560{ 561 register struct dirent *dp; 562 register FTSENT *p, *head; 563 register int nitems; 564 FTSENT *cur, *tail; 565 DIR *dirp; 566 void *adjaddr; 567 int cderrno, descend, len, level, maxlen, nlinks, oflag, saved_errno, 568 nostat = 0; 569 char *cp = NULL; /* pacify gcc */ 570 571 /* Set current node pointer. */ 572 cur = sp->fts_cur; 573 574 /* 575 * Open the directory for reading. If this fails, we're done. 576 * If being called from fts_read, set the fts_info field. 577 */ 578#ifdef FTS_WHITEOUT 579 if (ISSET(FTS_WHITEOUT)) 580 oflag = DTF_NODUP|DTF_REWIND; 581 else 582 oflag = DTF_HIDEW|DTF_NODUP|DTF_REWIND; 583#else 584#define __opendir2(path, flag) opendir(path) 585#endif 586 if ((dirp = __opendir2(cur->fts_accpath, oflag)) == NULL) { 587 if (type == BREAD) { 588 cur->fts_info = FTS_DNR; 589 cur->fts_errno = errno; 590 } 591 return (NULL); 592 } 593 594 /* 595 * Nlinks is the number of possible entries of type directory in the 596 * directory if we're cheating on stat calls, 0 if we're not doing 597 * any stat calls at all, -1 if we're doing stats on everything. 598 */ 599 if (type == BNAMES) 600 nlinks = 0; 601 else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) { 602 nlinks = cur->fts_nlink - (ISSET(FTS_SEEDOT) ? 0 : 2); 603 nostat = 1; 604 } else { 605 nlinks = -1; 606 nostat = 0; 607 } 608 609#ifdef notdef 610 (void)printf("nlinks == %d (cur: %d)\n", nlinks, cur->fts_nlink); 611 (void)printf("NOSTAT %d PHYSICAL %d SEEDOT %d\n", 612 ISSET(FTS_NOSTAT), ISSET(FTS_PHYSICAL), ISSET(FTS_SEEDOT)); 613#endif 614 /* 615 * If we're going to need to stat anything or we want to descend 616 * and stay in the directory, chdir. If this fails we keep going, 617 * but set a flag so we don't chdir after the post-order visit. 618 * We won't be able to stat anything, but we can still return the 619 * names themselves. Note, that since fts_read won't be able to 620 * chdir into the directory, it will have to return different path 621 * names than before, i.e. "a/b" instead of "b". Since the node 622 * has already been visited in pre-order, have to wait until the 623 * post-order visit to return the error. There is a special case 624 * here, if there was nothing to stat then it's not an error to 625 * not be able to stat. This is all fairly nasty. If a program 626 * needed sorted entries or stat information, they had better be 627 * checking FTS_NS on the returned nodes. 628 */ 629 cderrno = 0; 630 if (nlinks || type == BREAD) 631 if (FCHDIR(sp, dirfd(dirp))) { 632 if (nlinks && type == BREAD) 633 cur->fts_errno = errno; 634 cur->fts_flags |= FTS_DONTCHDIR; 635 descend = 0; 636 cderrno = errno; 637 } else 638 descend = 1; 639 else 640 descend = 0; 641 642 /* 643 * Figure out the max file name length that can be stored in the 644 * current path -- the inner loop allocates more path as necessary. 645 * We really wouldn't have to do the maxlen calculations here, we 646 * could do them in fts_read before returning the path, but it's a 647 * lot easier here since the length is part of the dirent structure. 648 * 649 * If not changing directories set a pointer so that can just append 650 * each new name into the path. 651 */ 652 maxlen = sp->fts_pathlen - cur->fts_pathlen - 1; 653 len = NAPPEND(cur); 654 if (ISSET(FTS_NOCHDIR)) { 655 cp = sp->fts_path + len; 656 *cp++ = '/'; 657 } 658 659 level = cur->fts_level + 1; 660 661 /* Read the directory, attaching each entry to the `link' pointer. */ 662 adjaddr = NULL; 663 for (head = tail = NULL, nitems = 0; (dp = readdir(dirp)) != NULL;) { 664 if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name)) 665 continue; 666 667 if ((p = fts_alloc(sp, dp->d_name, (int)dp->d_namlen)) == NULL) 668 goto mem1; 669 if (dp->d_namlen > maxlen) { 670 if (fts_palloc(sp, (size_t)dp->d_namlen)) { 671 /* 672 * No more memory for path or structures. Save 673 * errno, free up the current structure and the 674 * structures already allocated. 675 */ 676mem1: saved_errno = errno; 677 if (p) 678 free(p); 679 fts_lfree(head); 680 (void)closedir(dirp); 681 errno = saved_errno; 682 cur->fts_info = FTS_ERR; 683 SET(FTS_STOP); 684 return (NULL); 685 } 686 adjaddr = sp->fts_path; 687 maxlen = sp->fts_pathlen - sp->fts_cur->fts_pathlen - 1; 688 } 689 690 p->fts_pathlen = len + dp->d_namlen + 1; 691 p->fts_parent = sp->fts_cur; 692 p->fts_level = level; 693 694#ifdef FTS_WHITEOUT 695 if (dp->d_type == DT_WHT) 696 p->fts_flags |= FTS_ISW; 697#endif 698 699 if (cderrno) { 700 if (nlinks) { 701 p->fts_info = FTS_NS; 702 p->fts_errno = cderrno; 703 } else 704 p->fts_info = FTS_NSOK; 705 p->fts_accpath = cur->fts_accpath; 706 } else if (nlinks == 0 707#ifdef DT_DIR 708 || (nostat && 709 dp->d_type != DT_DIR && dp->d_type != DT_UNKNOWN) 710#endif 711 ) { 712 p->fts_accpath = 713 ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name; 714 p->fts_info = FTS_NSOK; 715 } else { 716 /* Build a file name for fts_stat to stat. */ 717 if (ISSET(FTS_NOCHDIR)) { 718 p->fts_accpath = p->fts_path; 719 memmove(cp, p->fts_name, p->fts_namelen + 1); 720 } else 721 p->fts_accpath = p->fts_name; 722 /* Stat it. */ 723 p->fts_info = fts_stat(sp, p, 0); 724 725 /* Decrement link count if applicable. */ 726 if (nlinks > 0 && (p->fts_info == FTS_D || 727 p->fts_info == FTS_DC || p->fts_info == FTS_DOT)) 728 --nlinks; 729 } 730 731 /* We walk in directory order so "ls -f" doesn't get upset. */ 732 p->fts_link = NULL; 733 if (head == NULL) 734 head = tail = p; 735 else { 736 tail->fts_link = p; 737 tail = p; 738 } 739 ++nitems; 740 } 741 (void)closedir(dirp); 742 743 /* 744 * If had to realloc the path, adjust the addresses for the rest 745 * of the tree. 746 */ 747 if (adjaddr) 748 fts_padjust(sp, adjaddr); 749 750 /* 751 * If not changing directories, reset the path back to original 752 * state. 753 */ 754 if (ISSET(FTS_NOCHDIR)) { 755 if (cp - 1 > sp->fts_path) 756 --cp; 757 *cp = '\0'; 758 } 759 760 /* 761 * If descended after called from fts_children or after called from 762 * fts_read and nothing found, get back. At the root level we use 763 * the saved fd; if one of fts_open()'s arguments is a relative path 764 * to an empty directory, we wind up here with no other way back. If 765 * can't get back, we're done. 766 */ 767 if (descend && (type == BCHILD || !nitems) && 768 (cur->fts_level == FTS_ROOTLEVEL ? 769 FCHDIR(sp, sp->fts_rfd) : CHDIR(sp, ".."))) { 770 cur->fts_info = FTS_ERR; 771 SET(FTS_STOP); 772 return (NULL); 773 } 774 775 /* If didn't find anything, return NULL. */ 776 if (!nitems) { 777 if (type == BREAD) 778 cur->fts_info = FTS_DP; 779 return (NULL); 780 } 781 782 /* Sort the entries. */ 783 if (sp->fts_compar && nitems > 1) 784 head = fts_sort(sp, head, nitems); 785 return (head); 786} 787 788static u_short 789fts_stat(sp, p, follow) 790 FTS *sp; 791 register FTSENT *p; 792 int follow; 793{ 794 register FTSENT *t; 795 register dev_t dev; 796 register ino_t ino; 797 struct stat *sbp, sb; 798 int saved_errno; 799 800 /* If user needs stat info, stat buffer already allocated. */ 801 sbp = ISSET(FTS_NOSTAT) ? &sb : p->fts_statp; 802 803#ifdef FTS_WHITEOUT 804 /* check for whiteout */ 805 if (p->fts_flags & FTS_ISW) { 806 if (sbp != &sb) { 807 memset(sbp, '\0', sizeof (*sbp)); 808 sbp->st_mode = S_IFWHT; 809 } 810 return (FTS_W); 811 } 812#endif 813 814 /* 815 * If doing a logical walk, or application requested FTS_FOLLOW, do 816 * a stat(2). If that fails, check for a non-existent symlink. If 817 * fail, set the errno from the stat call. 818 */ 819 if (ISSET(FTS_LOGICAL) || follow) { 820 if (stat(p->fts_accpath, sbp)) { 821 saved_errno = errno; 822 if (!lstat(p->fts_accpath, sbp)) { 823 errno = 0; 824 return (FTS_SLNONE); 825 } 826 p->fts_errno = saved_errno; 827 goto err; 828 } 829 } else if (lstat(p->fts_accpath, sbp)) { 830 p->fts_errno = errno; 831err: memset(sbp, 0, sizeof(struct stat)); 832 return (FTS_NS); 833 } 834 835 if (S_ISDIR(sbp->st_mode)) { 836 /* 837 * Set the device/inode. Used to find cycles and check for 838 * crossing mount points. Also remember the link count, used 839 * in fts_build to limit the number of stat calls. It is 840 * understood that these fields are only referenced if fts_info 841 * is set to FTS_D. 842 */ 843 dev = p->fts_dev = sbp->st_dev; 844 ino = p->fts_ino = sbp->st_ino; 845 p->fts_nlink = sbp->st_nlink; 846 847 if (ISDOT(p->fts_name)) 848 return (FTS_DOT); 849 850 /* 851 * Cycle detection is done by brute force when the directory 852 * is first encountered. If the tree gets deep enough or the 853 * number of symbolic links to directories is high enough, 854 * something faster might be worthwhile. 855 */ 856 for (t = p->fts_parent; 857 t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent) 858 if (ino == t->fts_ino && dev == t->fts_dev) { 859 p->fts_cycle = t; 860 return (FTS_DC); 861 } 862 return (FTS_D); 863 } 864 if (S_ISLNK(sbp->st_mode)) 865 return (FTS_SL); 866 if (S_ISREG(sbp->st_mode)) 867 return (FTS_F); 868 return (FTS_DEFAULT); 869} 870 871static FTSENT * 872fts_sort(sp, head, nitems) 873 FTS *sp; 874 FTSENT *head; 875 register int nitems; 876{ 877 register FTSENT **ap, *p; 878 879 /* 880 * Construct an array of pointers to the structures and call qsort(3). 881 * Reassemble the array in the order returned by qsort. If unable to 882 * sort for memory reasons, return the directory entries in their 883 * current order. Allocate enough space for the current needs plus 884 * 40 so don't realloc one entry at a time. 885 */ 886 if (nitems > sp->fts_nitems) { 887 sp->fts_nitems = nitems + 40; 888 if ((sp->fts_array = realloc(sp->fts_array, 889 (size_t)(sp->fts_nitems * sizeof(FTSENT *)))) == NULL) { 890 sp->fts_nitems = 0; 891 return (head); 892 } 893 } 894 for (ap = sp->fts_array, p = head; p; p = p->fts_link) 895 *ap++ = p; 896 qsort((void *)sp->fts_array, nitems, sizeof(FTSENT *), sp->fts_compar); 897 for (head = *(ap = sp->fts_array); --nitems; ++ap) 898 ap[0]->fts_link = ap[1]; 899 ap[0]->fts_link = NULL; 900 return (head); 901} 902 903static FTSENT * 904fts_alloc(sp, name, namelen) 905 FTS *sp; 906 char *name; 907 register int namelen; 908{ 909 register FTSENT *p; 910 size_t len; 911 912 /* 913 * The file name is a variable length array and no stat structure is 914 * necessary if the user has set the nostat bit. Allocate the FTSENT 915 * structure, the file name and the stat structure in one chunk, but 916 * be careful that the stat structure is reasonably aligned. Since the 917 * fts_name field is declared to be of size 1, the fts_name pointer is 918 * namelen + 2 before the first possible address of the stat structure. 919 */ 920 len = sizeof(FTSENT) + namelen; 921 if (!ISSET(FTS_NOSTAT)) 922 len += sizeof(struct stat) + ALIGNBYTES; 923 if ((p = malloc(len)) == NULL) 924 return (NULL); 925 926 /* Copy the name plus the trailing NULL. */ 927 memmove(p->fts_name, name, namelen + 1); 928 929 if (!ISSET(FTS_NOSTAT)) 930 p->fts_statp = (struct stat *)ALIGN(p->fts_name + namelen + 2); 931 p->fts_namelen = namelen; 932 p->fts_path = sp->fts_path; 933 p->fts_errno = 0; 934 p->fts_flags = 0; 935 p->fts_instr = FTS_NOINSTR; 936 p->fts_number = 0; 937 p->fts_pointer = NULL; 938 return (p); 939} 940 941static void 942fts_lfree(head) 943 register FTSENT *head; 944{ 945 register FTSENT *p; 946 947 /* Free a linked list of structures. */ 948 while ((p = head) != NULL) { 949 head = head->fts_link; 950 free(p); 951 } 952} 953 954/* 955 * Allow essentially unlimited paths; find, rm, ls should all work on any tree. 956 * Most systems will allow creation of paths much longer than MAXPATHLEN, even 957 * though the kernel won't resolve them. Add the size (not just what's needed) 958 * plus 256 bytes so don't realloc the path 2 bytes at a time. 959 */ 960static int 961fts_palloc(sp, more) 962 FTS *sp; 963 size_t more; 964{ 965 sp->fts_pathlen += more + 256; 966 sp->fts_path = realloc(sp->fts_path, (size_t)sp->fts_pathlen); 967 return (sp->fts_path == NULL); 968} 969 970/* 971 * When the path is realloc'd, have to fix all of the pointers in structures 972 * already returned. 973 */ 974static void 975fts_padjust(sp, addr) 976 FTS *sp; 977 void *addr; 978{ 979 FTSENT *p; 980 981#define ADJUST(p) { \ 982 (p)->fts_accpath = \ 983 (char *)addr + ((p)->fts_accpath - (p)->fts_path); \ 984 (p)->fts_path = addr; \ 985} 986 /* Adjust the current set of children. */ 987 for (p = sp->fts_child; p; p = p->fts_link) 988 ADJUST(p); 989 990 /* Adjust the rest of the tree. */ 991 for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) { 992 ADJUST(p); 993 p = p->fts_link ? p->fts_link : p->fts_parent; 994 } 995} 996 997static size_t 998fts_maxarglen(argv) 999 char * const *argv; 1000{ 1001 size_t len, max; 1002 1003 for (max = 0; *argv; ++argv) 1004 if ((len = strlen(*argv)) > max) 1005 max = len; 1006 return (max); 1007} 1008