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