1 /* Traverse a file hierarchy.
3 Copyright (C) 2004, 2005, 2006 Free Software Foundation, Inc.
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 2, or (at your option)
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with this program; if not, write to the Free Software Foundation,
17 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
20 * Copyright (c) 1990, 1993, 1994
21 * The Regents of the University of California. All rights reserved.
23 * Redistribution and use in source and binary forms, with or without
24 * modification, are permitted provided that the following conditions
26 * 1. Redistributions of source code must retain the above copyright
27 * notice, this list of conditions and the following disclaimer.
28 * 2. Redistributions in binary form must reproduce the above copyright
29 * notice, this list of conditions and the following disclaimer in the
30 * documentation and/or other materials provided with the distribution.
31 * 4. Neither the name of the University nor the names of its contributors
32 * may be used to endorse or promote products derived from this software
33 * without specific prior written permission.
35 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
36 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
37 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
38 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
39 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
40 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
41 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
42 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
43 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
44 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
52 #if defined(LIBC_SCCS) && !defined(lint)
53 static char sccsid[] = "@(#)fts.c 8.6 (Berkeley) 8/14/94";
54 #endif /* LIBC_SCCS and not lint */
58 #if HAVE_SYS_PARAM_H || defined _LIBC
59 # include <sys/param.h>
62 # include <include/sys/stat.h>
64 # include <sys/stat.h>
80 # define NAMLEN(dirent) _D_EXACT_NAMLEN (dirent)
84 # define NAMLEN(dirent) strlen ((dirent)->d_name)
86 # define dirent direct
87 # define NAMLEN(dirent) (dirent)->d_namlen
89 # include <sys/ndir.h>
102 # define close __close
104 # define closedir __closedir
106 # define fchdir __fchdir
110 # define opendir __opendir
112 # define readdir __readdir
114 # undef internal_function
115 # define internal_function /* empty */
119 # define __set_errno(Val) errno = (Val)
122 #ifndef __attribute__
123 # if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 8) || __STRICT_ANSI__
124 # define __attribute__(x) /* empty */
128 #ifndef ATTRIBUTE_UNUSED
129 # define ATTRIBUTE_UNUSED __attribute__ ((__unused__))
133 static FTSENT *fts_alloc (FTS *, const char *, size_t) internal_function;
134 static FTSENT *fts_build (FTS *, int) internal_function;
135 static void fts_lfree (FTSENT *) internal_function;
136 static void fts_load (FTS *, FTSENT *) internal_function;
137 static size_t fts_maxarglen (char * const *) internal_function;
138 static void fts_padjust (FTS *, FTSENT *) internal_function;
139 static bool fts_palloc (FTS *, size_t) internal_function;
140 static FTSENT *fts_sort (FTS *, FTSENT *, size_t) internal_function;
141 static unsigned short int fts_stat (FTS *, FTSENT *, bool) internal_function;
142 static int fts_safe_changedir (FTS *, FTSENT *, int, const char *)
146 static bool enter_dir (FTS *fts, FTSENT *ent) { return true; }
147 static void leave_dir (FTS *fts, FTSENT *ent) {}
148 static bool setup_dir (FTS *fts) { return true; }
149 static void free_dir (FTS *fts) {}
151 # include "fcntl--.h"
152 # include "fts-cycle.c"
156 # define MAX(a,b) ((a) > (b) ? (a) : (b))
160 # define SIZE_MAX ((size_t) -1)
164 # define O_DIRECTORY 0
167 #define ISDOT(a) (a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2])))
169 #define CLR(opt) (sp->fts_options &= ~(opt))
170 #define ISSET(opt) (sp->fts_options & (opt))
171 #define SET(opt) (sp->fts_options |= (opt))
173 #define FCHDIR(sp, fd) (!ISSET(FTS_NOCHDIR) && fchdir(fd))
175 /* fts_build flags */
176 #define BCHILD 1 /* fts_children */
177 #define BNAMES 2 /* fts_children, names only */
178 #define BREAD 3 /* fts_read */
181 # include <inttypes.h>
184 bool fts_debug = false;
185 # define Dprintf(x) do { if (fts_debug) printf x; } while (0)
190 #define LEAVE_DIR(Fts, Ent, Tag) \
193 Dprintf ((" %s-leaving: %s\n", Tag, (Ent)->fts_path)); \
194 leave_dir (Fts, Ent); \
198 /* Open the directory DIR if possible, and return a file
199 descriptor. Return -1 and set errno on failure. It doesn't matter
200 whether the file descriptor has read or write access. */
204 diropen (char const *dir)
206 return open (dir, O_RDONLY | O_DIRECTORY | O_NOCTTY | O_NONBLOCK);
210 fts_open (char * const *argv,
211 register int options,
212 int (*compar) (FTSENT const **, FTSENT const **))
215 register FTSENT *p, *root;
216 register size_t nitems;
217 FTSENT *parent, *tmp = NULL; /* pacify gcc */
221 if (options & ~FTS_OPTIONMASK) {
222 __set_errno (EINVAL);
226 /* Allocate/initialize the stream */
227 if ((sp = malloc(sizeof(FTS))) == NULL)
229 memset(sp, 0, sizeof(FTS));
230 sp->fts_compar = compar;
231 sp->fts_options = options;
233 /* Logical walks turn on NOCHDIR; symbolic links are too hard. */
234 if (ISSET(FTS_LOGICAL))
238 * Start out with 1K of file name space, and enough, in any case,
239 * to hold the user's file names.
242 # define MAXPATHLEN 1024
245 size_t maxarglen = fts_maxarglen(argv);
246 if (! fts_palloc(sp, MAX(maxarglen, MAXPATHLEN)))
250 /* Allocate/initialize root's parent. */
251 if ((parent = fts_alloc(sp, "", 0)) == NULL)
253 parent->fts_level = FTS_ROOTPARENTLEVEL;
255 /* Allocate/initialize root(s). */
256 for (root = NULL, nitems = 0; *argv != NULL; ++argv, ++nitems) {
257 /* Don't allow zero-length file names. */
258 if ((len = strlen(*argv)) == 0) {
259 __set_errno (ENOENT);
263 if ((p = fts_alloc(sp, *argv, len)) == NULL)
265 p->fts_level = FTS_ROOTLEVEL;
266 p->fts_parent = parent;
267 p->fts_accpath = p->fts_name;
268 p->fts_info = fts_stat(sp, p, ISSET(FTS_COMFOLLOW) != 0);
270 /* Command-line "." and ".." are real directories. */
271 if (p->fts_info == FTS_DOT)
275 * If comparison routine supplied, traverse in sorted
276 * order; otherwise traverse in the order specified.
291 if (compar && nitems > 1)
292 root = fts_sort(sp, root, nitems);
295 * Allocate a dummy pointer and make fts_read think that we've just
296 * finished the node before the root(s); set p->fts_info to FTS_INIT
297 * so that everything about the "current" node is ignored.
299 if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL)
301 sp->fts_cur->fts_link = root;
302 sp->fts_cur->fts_info = FTS_INIT;
303 if (! setup_dir (sp))
307 * If using chdir(2), grab a file descriptor pointing to dot to ensure
308 * that we can get back here; this could be avoided for some file names,
309 * but almost certainly not worth the effort. Slashes, symbolic links,
310 * and ".." are all fairly nasty problems. Note, if we can't get the
311 * descriptor we run anyway, just more slowly.
313 if (!ISSET(FTS_NOCHDIR)
314 && (sp->fts_rfd = diropen (".")) < 0)
319 mem3: fts_lfree(root);
321 mem2: free(sp->fts_path);
328 fts_load (FTS *sp, register FTSENT *p)
334 * Load the stream structure for the next traversal. Since we don't
335 * actually enter the directory until after the preorder visit, set
336 * the fts_accpath field specially so the chdir gets done to the right
337 * place and the user can access the first node. From fts_open it's
338 * known that the file name will fit.
340 len = p->fts_pathlen = p->fts_namelen;
341 memmove(sp->fts_path, p->fts_name, len + 1);
342 if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) {
344 memmove(p->fts_name, cp, len + 1);
345 p->fts_namelen = len;
347 p->fts_accpath = p->fts_path = sp->fts_path;
348 sp->fts_dev = p->fts_statp->st_dev;
354 register FTSENT *freep, *p;
358 * This still works if we haven't read anything -- the dummy structure
359 * points to the root list, so we step through to the end of the root
360 * list which has a valid parent pointer.
363 for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {
365 p = p->fts_link != NULL ? p->fts_link : p->fts_parent;
371 /* Free up child linked list, sort array, file name buffer. */
373 fts_lfree(sp->fts_child);
378 /* Return to original directory, save errno if necessary. */
379 if (!ISSET(FTS_NOCHDIR)) {
380 if (fchdir(sp->fts_rfd))
382 (void)close(sp->fts_rfd);
387 /* Free up the stream pointer. */
390 /* Set errno and return. */
392 __set_errno (saved_errno);
400 * Special case of "/" at the end of the file name so that slashes aren't
401 * appended which would cause file names to be written as "....//foo".
404 (p->fts_path[p->fts_pathlen - 1] == '/' \
405 ? p->fts_pathlen - 1 : p->fts_pathlen)
408 fts_read (register FTS *sp)
410 register FTSENT *p, *tmp;
411 register unsigned short int instr;
415 /* If finished or unrecoverable error, return NULL. */
416 if (sp->fts_cur == NULL || ISSET(FTS_STOP))
419 /* Set current node pointer. */
422 /* Save and zero out user instructions. */
423 instr = p->fts_instr;
424 p->fts_instr = FTS_NOINSTR;
426 /* Any type of file may be re-visited; re-stat and re-turn. */
427 if (instr == FTS_AGAIN) {
428 p->fts_info = fts_stat(sp, p, false);
431 Dprintf (("fts_read: p=%s\n",
432 p->fts_info == FTS_INIT ? "" : p->fts_path));
435 * Following a symlink -- SLNONE test allows application to see
436 * SLNONE and recover. If indirecting through a symlink, have
437 * keep a pointer to current location. If unable to get that
438 * pointer, follow fails.
440 if (instr == FTS_FOLLOW &&
441 (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) {
442 p->fts_info = fts_stat(sp, p, true);
443 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
444 if ((p->fts_symfd = diropen (".")) < 0) {
445 p->fts_errno = errno;
446 p->fts_info = FTS_ERR;
448 p->fts_flags |= FTS_SYMFOLLOW;
453 /* Directory in pre-order. */
454 if (p->fts_info == FTS_D) {
455 /* If skipped or crossed mount point, do post-order visit. */
456 if (instr == FTS_SKIP ||
457 (ISSET(FTS_XDEV) && p->fts_statp->st_dev != sp->fts_dev)) {
458 if (p->fts_flags & FTS_SYMFOLLOW)
459 (void)close(p->fts_symfd);
461 fts_lfree(sp->fts_child);
462 sp->fts_child = NULL;
464 p->fts_info = FTS_DP;
465 LEAVE_DIR (sp, p, "1");
469 /* Rebuild if only read the names and now traversing. */
470 if (sp->fts_child != NULL && ISSET(FTS_NAMEONLY)) {
472 fts_lfree(sp->fts_child);
473 sp->fts_child = NULL;
477 * Cd to the subdirectory.
479 * If have already read and now fail to chdir, whack the list
480 * to make the names come out right, and set the parent errno
481 * so the application will eventually get an error condition.
482 * Set the FTS_DONTCHDIR flag so that when we logically change
483 * directories back to the parent we don't do a chdir.
485 * If haven't read do so. If the read fails, fts_build sets
486 * FTS_STOP or the fts_info field of the node.
488 if (sp->fts_child != NULL) {
489 if (fts_safe_changedir(sp, p, -1, p->fts_accpath)) {
490 p->fts_errno = errno;
491 p->fts_flags |= FTS_DONTCHDIR;
492 for (p = sp->fts_child; p != NULL;
495 p->fts_parent->fts_accpath;
497 } else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) {
500 /* If fts_build's call to fts_safe_changedir failed
501 because it was not able to fchdir into a
502 subdirectory, tell the caller. */
504 p->fts_info = FTS_ERR;
505 /* FIXME: see if this should be in an else block */
506 LEAVE_DIR (sp, p, "2");
510 sp->fts_child = NULL;
514 /* Move to the next node on this level. */
516 if ((p = p->fts_link) != NULL) {
520 * If reached the top, return to the original directory (or
521 * the root of the tree), and load the file names for the next
524 if (p->fts_level == FTS_ROOTLEVEL) {
525 if (FCHDIR(sp, sp->fts_rfd)) {
535 * User may have called fts_set on the node. If skipped,
536 * ignore. If followed, get a file descriptor so we can
537 * get back if necessary.
539 if (p->fts_instr == FTS_SKIP)
541 if (p->fts_instr == FTS_FOLLOW) {
542 p->fts_info = fts_stat(sp, p, true);
543 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
544 if ((p->fts_symfd = diropen (".")) < 0) {
545 p->fts_errno = errno;
546 p->fts_info = FTS_ERR;
548 p->fts_flags |= FTS_SYMFOLLOW;
550 p->fts_instr = FTS_NOINSTR;
553 name: t = sp->fts_path + NAPPEND(p->fts_parent);
555 memmove(t, p->fts_name, p->fts_namelen + 1);
558 if (p->fts_info == FTS_D)
560 Dprintf ((" %s-entering: %s\n", sp, p->fts_path));
561 if (! enter_dir (sp, p))
563 __set_errno (ENOMEM);
570 /* Move up to the parent node. */
574 if (p->fts_level == FTS_ROOTPARENTLEVEL) {
576 * Done; free everything up and set errno to 0 so the user
577 * can distinguish between error and EOF.
581 return (sp->fts_cur = NULL);
584 /* NUL terminate the file name. */
585 sp->fts_path[p->fts_pathlen] = '\0';
588 * Return to the parent directory. If at a root node or came through
589 * a symlink, go back through the file descriptor. Otherwise, cd up
592 if (p->fts_level == FTS_ROOTLEVEL) {
593 if (FCHDIR(sp, sp->fts_rfd)) {
594 p->fts_errno = errno;
597 } else if (p->fts_flags & FTS_SYMFOLLOW) {
598 if (FCHDIR(sp, p->fts_symfd)) {
600 (void)close(p->fts_symfd);
601 __set_errno (saved_errno);
602 p->fts_errno = errno;
605 (void)close(p->fts_symfd);
606 } else if (!(p->fts_flags & FTS_DONTCHDIR) &&
607 fts_safe_changedir(sp, p->fts_parent, -1, "..")) {
608 p->fts_errno = errno;
611 p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;
612 if (p->fts_errno == 0)
613 LEAVE_DIR (sp, p, "3");
615 return ISSET(FTS_STOP) ? NULL : p;
619 * Fts_set takes the stream as an argument although it's not used in this
620 * implementation; it would be necessary if anyone wanted to add global
621 * semantics to fts using fts_set. An error return is allowed for similar
626 fts_set(FTS *sp ATTRIBUTE_UNUSED, FTSENT *p, int instr)
628 if (instr != 0 && instr != FTS_AGAIN && instr != FTS_FOLLOW &&
629 instr != FTS_NOINSTR && instr != FTS_SKIP) {
630 __set_errno (EINVAL);
633 p->fts_instr = instr;
638 fts_children (register FTS *sp, int instr)
643 if (instr != 0 && instr != FTS_NAMEONLY) {
644 __set_errno (EINVAL);
648 /* Set current node pointer. */
652 * Errno set to 0 so user can distinguish empty directory from
657 /* Fatal errors stop here. */
661 /* Return logical hierarchy of user's arguments. */
662 if (p->fts_info == FTS_INIT)
663 return (p->fts_link);
666 * If not a directory being visited in pre-order, stop here. Could
667 * allow FTS_DNR, assuming the user has fixed the problem, but the
668 * same effect is available with FTS_AGAIN.
670 if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */)
673 /* Free up any previous child list. */
674 if (sp->fts_child != NULL)
675 fts_lfree(sp->fts_child);
677 if (instr == FTS_NAMEONLY) {
684 * If using chdir on a relative file name and called BEFORE fts_read
685 * does its chdir to the root of a traversal, we can lose -- we need to
686 * chdir into the subdirectory, and we don't know where the current
687 * directory is, so we can't get back so that the upcoming chdir by
688 * fts_read will work.
690 if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' ||
692 return (sp->fts_child = fts_build(sp, instr));
694 if ((fd = diropen (".")) < 0)
695 return (sp->fts_child = NULL);
696 sp->fts_child = fts_build(sp, instr);
698 int saved_errno = errno;
700 __set_errno (saved_errno);
704 return (sp->fts_child);
708 * This is the tricky part -- do not casually change *anything* in here. The
709 * idea is to build the linked list of entries that are used by fts_children
710 * and fts_read. There are lots of special cases.
712 * The real slowdown in walking the tree is the stat calls. If FTS_NOSTAT is
713 * set and it's a physical walk (so that symbolic links can't be directories),
714 * we can do things quickly. First, if it's a 4.4BSD file system, the type
715 * of the file is in the directory entry. Otherwise, we assume that the number
716 * of subdirectories in a node is equal to the number of links to the parent.
717 * The former skips all stat calls. The latter skips stat calls in any leaf
718 * directories and for any files after the subdirectories in the directory have
719 * been found, cutting the stat calls by about 2/3.
723 fts_build (register FTS *sp, int type)
725 register struct dirent *dp;
726 register FTSENT *p, *head;
727 register size_t nitems;
738 size_t len, maxlen, new_len;
741 /* Set current node pointer. */
745 * Open the directory for reading. If this fails, we're done.
746 * If being called from fts_read, set the fts_info field.
748 #if defined FTS_WHITEOUT && 0
749 if (ISSET(FTS_WHITEOUT))
750 oflag = DTF_NODUP|DTF_REWIND;
752 oflag = DTF_HIDEW|DTF_NODUP|DTF_REWIND;
754 # define __opendir2(file, flag) opendir(file)
756 if ((dirp = __opendir2(cur->fts_accpath, oflag)) == NULL) {
758 cur->fts_info = FTS_DNR;
759 cur->fts_errno = errno;
765 * Nlinks is the number of possible entries of type directory in the
766 * directory if we're cheating on stat calls, 0 if we're not doing
767 * any stat calls at all, (nlink_t) -1 if we're statting everything.
769 if (type == BNAMES) {
771 /* Be quiet about nostat, GCC. */
773 } else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) {
774 nlinks = (cur->fts_statp->st_nlink
775 - (ISSET(FTS_SEEDOT) ? 0 : 2));
783 * If we're going to need to stat anything or we want to descend
784 * and stay in the directory, chdir. If this fails we keep going,
785 * but set a flag so we don't chdir after the post-order visit.
786 * We won't be able to stat anything, but we can still return the
787 * names themselves. Note, that since fts_read won't be able to
788 * chdir into the directory, it will have to return different file
789 * names than before, i.e. "a/b" instead of "b". Since the node
790 * has already been visited in pre-order, have to wait until the
791 * post-order visit to return the error. There is a special case
792 * here, if there was nothing to stat then it's not an error to
793 * not be able to stat. This is all fairly nasty. If a program
794 * needed sorted entries or stat information, they had better be
795 * checking FTS_NS on the returned nodes.
798 if (nlinks || type == BREAD) {
799 if (fts_safe_changedir(sp, cur, dirfd(dirp), NULL)) {
800 if (nlinks && type == BREAD)
801 cur->fts_errno = errno;
802 cur->fts_flags |= FTS_DONTCHDIR;
813 * Figure out the max file name length that can be stored in the
814 * current buffer -- the inner loop allocates more space as necessary.
815 * We really wouldn't have to do the maxlen calculations here, we
816 * could do them in fts_read before returning the name, but it's a
817 * lot easier here since the length is part of the dirent structure.
819 * If not changing directories set a pointer so that can just append
820 * each new component into the file name.
823 if (ISSET(FTS_NOCHDIR)) {
824 cp = sp->fts_path + len;
827 /* GCC, you're too verbose. */
831 maxlen = sp->fts_pathlen - len;
833 level = cur->fts_level + 1;
835 /* Read the directory, attaching each entry to the `link' pointer. */
837 for (head = tail = NULL, nitems = 0; dirp && (dp = readdir(dirp));) {
838 if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))
841 if ((p = fts_alloc(sp, dp->d_name, NAMLEN (dp))) == NULL)
843 if (NAMLEN (dp) >= maxlen) {/* include space for NUL */
844 oldaddr = sp->fts_path;
845 if (! fts_palloc(sp, NAMLEN (dp) + len + 1)) {
847 * No more memory. Save
848 * errno, free up the current structure and the
849 * structures already allocated.
851 mem1: saved_errno = errno;
856 cur->fts_info = FTS_ERR;
858 __set_errno (saved_errno);
861 /* Did realloc() change the pointer? */
862 if (oldaddr != sp->fts_path) {
864 if (ISSET(FTS_NOCHDIR))
865 cp = sp->fts_path + len;
867 maxlen = sp->fts_pathlen - len;
870 new_len = len + NAMLEN (dp);
873 * In the unlikely even that we would end up
874 * with a file name longer than SIZE_MAX, free up
875 * the current structure and the structures already
876 * allocated, then error out with ENAMETOOLONG.
881 cur->fts_info = FTS_ERR;
883 __set_errno (ENAMETOOLONG);
886 p->fts_level = level;
887 p->fts_parent = sp->fts_cur;
888 p->fts_pathlen = new_len;
890 #if defined FTS_WHITEOUT && 0
891 if (dp->d_type == DT_WHT)
892 p->fts_flags |= FTS_ISW;
897 p->fts_info = FTS_NS;
898 p->fts_errno = cderrno;
900 p->fts_info = FTS_NSOK;
901 p->fts_accpath = cur->fts_accpath;
902 } else if (nlinks == 0
903 #if HAVE_STRUCT_DIRENT_D_TYPE
905 dp->d_type != DT_DIR && dp->d_type != DT_UNKNOWN)
909 ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name;
910 p->fts_info = FTS_NSOK;
912 /* Build a file name for fts_stat to stat. */
913 if (ISSET(FTS_NOCHDIR)) {
914 p->fts_accpath = p->fts_path;
915 memmove(cp, p->fts_name, p->fts_namelen + 1);
917 p->fts_accpath = p->fts_name;
919 p->fts_info = fts_stat(sp, p, false);
921 /* Decrement link count if applicable. */
922 if (nlinks > 0 && (p->fts_info == FTS_D ||
923 p->fts_info == FTS_DC || p->fts_info == FTS_DOT))
927 /* We walk in directory order so "ls -f" doesn't get upset. */
941 * If realloc() changed the address of the file name, adjust the
942 * addresses for the rest of the tree and the dir list.
945 fts_padjust(sp, head);
948 * If not changing directories, reset the file name back to original
951 if (ISSET(FTS_NOCHDIR)) {
952 if (len == sp->fts_pathlen || nitems == 0)
958 * If descended after called from fts_children or after called from
959 * fts_read and nothing found, get back. At the root level we use
960 * the saved fd; if one of fts_open()'s arguments is a relative name
961 * to an empty directory, we wind up here with no other way back. If
962 * can't get back, we're done.
964 if (descend && (type == BCHILD || !nitems) &&
965 (cur->fts_level == FTS_ROOTLEVEL ?
966 FCHDIR(sp, sp->fts_rfd) :
967 fts_safe_changedir(sp, cur->fts_parent, -1, ".."))) {
968 cur->fts_info = FTS_ERR;
973 /* If didn't find anything, return NULL. */
976 cur->fts_info = FTS_DP;
980 /* Sort the entries. */
981 if (sp->fts_compar && nitems > 1)
982 head = fts_sort(sp, head, nitems);
988 /* Walk ->fts_parent links starting at E_CURR, until the root of the
989 current hierarchy. There should be a directory with dev/inode
990 matching those of AD. If not, print a lot of diagnostics. */
992 find_matching_ancestor (FTSENT const *e_curr, struct Active_dir const *ad)
995 for (ent = e_curr; ent->fts_level >= FTS_ROOTLEVEL; ent = ent->fts_parent)
997 if (ad->ino == ent->fts_statp->st_ino
998 && ad->dev == ent->fts_statp->st_dev)
1001 printf ("ERROR: tree dir, %s, not active\n", ad->fts_ent->fts_accpath);
1002 printf ("active dirs:\n");
1004 ent->fts_level >= FTS_ROOTLEVEL; ent = ent->fts_parent)
1005 printf (" %s(%"PRIuMAX"/%"PRIuMAX") to %s(%"PRIuMAX"/%"PRIuMAX")...\n",
1006 ad->fts_ent->fts_accpath,
1007 (uintmax_t) ad->dev,
1008 (uintmax_t) ad->ino,
1010 (uintmax_t) ent->fts_statp->st_dev,
1011 (uintmax_t) ent->fts_statp->st_ino);
1015 fts_cross_check (FTS const *sp)
1017 FTSENT const *ent = sp->fts_cur;
1019 if ( ! ISSET (FTS_TIGHT_CYCLE_CHECK))
1022 Dprintf (("fts-cross-check cur=%s\n", ent->fts_path));
1023 /* Make sure every parent dir is in the tree. */
1024 for (t = ent->fts_parent; t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
1026 struct Active_dir ad;
1027 ad.ino = t->fts_statp->st_ino;
1028 ad.dev = t->fts_statp->st_dev;
1029 if ( ! hash_lookup (sp->fts_cycle.ht, &ad))
1030 printf ("ERROR: active dir, %s, not in tree\n", t->fts_path);
1033 /* Make sure every dir in the tree is an active dir.
1034 But ENT is not necessarily a directory. If so, just skip this part. */
1035 if (ent->fts_parent->fts_level >= FTS_ROOTLEVEL
1036 && (ent->fts_info == FTS_DP
1037 || ent->fts_info == FTS_D))
1039 struct Active_dir *ad;
1040 for (ad = hash_get_first (sp->fts_cycle.ht); ad != NULL;
1041 ad = hash_get_next (sp->fts_cycle.ht, ad))
1043 find_matching_ancestor (ent, ad);
1049 static unsigned short int
1051 fts_stat(FTS *sp, register FTSENT *p, bool follow)
1053 struct stat *sbp = p->fts_statp;
1056 #if defined FTS_WHITEOUT && 0
1057 /* check for whiteout */
1058 if (p->fts_flags & FTS_ISW) {
1059 memset(sbp, '\0', sizeof (*sbp));
1060 sbp->st_mode = S_IFWHT;
1066 * If doing a logical walk, or application requested FTS_FOLLOW, do
1067 * a stat(2). If that fails, check for a non-existent symlink. If
1068 * fail, set the errno from the stat call.
1070 if (ISSET(FTS_LOGICAL) || follow) {
1071 if (stat(p->fts_accpath, sbp)) {
1072 saved_errno = errno;
1074 && lstat(p->fts_accpath, sbp) == 0) {
1076 return (FTS_SLNONE);
1078 p->fts_errno = saved_errno;
1081 } else if (lstat(p->fts_accpath, sbp)) {
1082 p->fts_errno = errno;
1083 err: memset(sbp, 0, sizeof(struct stat));
1087 if (S_ISDIR(sbp->st_mode)) {
1088 if (ISDOT(p->fts_name))
1094 * Cycle detection is done by brute force when the directory
1095 * is first encountered. If the tree gets deep enough or the
1096 * number of symbolic links to directories is high enough,
1097 * something faster might be worthwhile.
1101 for (t = p->fts_parent;
1102 t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
1103 if (sbp->st_ino == t->fts_statp->st_ino
1104 && sbp->st_dev == t->fts_statp->st_dev)
1114 if (S_ISLNK(sbp->st_mode))
1116 if (S_ISREG(sbp->st_mode))
1118 return (FTS_DEFAULT);
1122 fts_compar (void const *a, void const *b)
1124 /* Convert A and B to the correct types, to pacify the compiler, and
1125 for portability to bizarre hosts where "void const *" and "FTSENT
1126 const **" differ in runtime representation. The comparison
1127 function cannot modify *a and *b, but there is no compile-time
1129 FTSENT const **pa = (FTSENT const **) a;
1130 FTSENT const **pb = (FTSENT const **) b;
1131 return pa[0]->fts_fts->fts_compar (pa, pb);
1136 fts_sort (FTS *sp, FTSENT *head, register size_t nitems)
1138 register FTSENT **ap, *p;
1140 /* On most modern hosts, void * and FTSENT ** have the same
1141 run-time representation, and one can convert sp->fts_compar to
1142 the type qsort expects without problem. Use the heuristic that
1143 this is OK if the two pointer types are the same size, and if
1144 converting FTSENT ** to long int is the same as converting
1145 FTSENT ** to void * and then to long int. This heuristic isn't
1146 valid in general but we don't know of any counterexamples. */
1148 int (*compare) (void const *, void const *) =
1149 ((sizeof &dummy == sizeof (void *)
1150 && (long int) &dummy == (long int) (void *) &dummy)
1151 ? (int (*) (void const *, void const *)) sp->fts_compar
1155 * Construct an array of pointers to the structures and call qsort(3).
1156 * Reassemble the array in the order returned by qsort. If unable to
1157 * sort for memory reasons, return the directory entries in their
1158 * current order. Allocate enough space for the current needs plus
1159 * 40 so don't realloc one entry at a time.
1161 if (nitems > sp->fts_nitems) {
1164 sp->fts_nitems = nitems + 40;
1165 if (SIZE_MAX / sizeof *a < sp->fts_nitems
1166 || ! (a = realloc (sp->fts_array,
1167 sp->fts_nitems * sizeof *a))) {
1168 free(sp->fts_array);
1169 sp->fts_array = NULL;
1175 for (ap = sp->fts_array, p = head; p; p = p->fts_link)
1177 qsort((void *)sp->fts_array, nitems, sizeof(FTSENT *), compare);
1178 for (head = *(ap = sp->fts_array); --nitems; ++ap)
1179 ap[0]->fts_link = ap[1];
1180 ap[0]->fts_link = NULL;
1186 fts_alloc (FTS *sp, const char *name, register size_t namelen)
1192 * The file name is a variable length array. Allocate the FTSENT
1193 * structure and the file name in one chunk.
1195 len = sizeof(FTSENT) + namelen;
1196 if ((p = malloc(len)) == NULL)
1199 /* Copy the name and guarantee NUL termination. */
1200 memmove(p->fts_name, name, namelen);
1201 p->fts_name[namelen] = '\0';
1203 p->fts_namelen = namelen;
1205 p->fts_path = sp->fts_path;
1208 p->fts_instr = FTS_NOINSTR;
1210 p->fts_pointer = NULL;
1216 fts_lfree (register FTSENT *head)
1220 /* Free a linked list of structures. */
1221 while ((p = head)) {
1222 head = head->fts_link;
1228 * Allow essentially unlimited file name lengths; find, rm, ls should
1229 * all work on any tree. Most systems will allow creation of file
1230 * names much longer than MAXPATHLEN, even though the kernel won't
1231 * resolve them. Add the size (not just what's needed) plus 256 bytes
1232 * so don't realloc the file name 2 bytes at a time.
1236 fts_palloc (FTS *sp, size_t more)
1239 size_t new_len = sp->fts_pathlen + more + 256;
1242 * See if fts_pathlen would overflow.
1244 if (new_len < sp->fts_pathlen) {
1247 sp->fts_path = NULL;
1249 sp->fts_path = NULL;
1250 __set_errno (ENAMETOOLONG);
1253 sp->fts_pathlen = new_len;
1254 p = realloc(sp->fts_path, sp->fts_pathlen);
1257 sp->fts_path = NULL;
1265 * When the file name is realloc'd, have to fix all of the pointers in
1266 * structures already returned.
1270 fts_padjust (FTS *sp, FTSENT *head)
1273 char *addr = sp->fts_path;
1275 #define ADJUST(p) do { \
1276 if ((p)->fts_accpath != (p)->fts_name) { \
1277 (p)->fts_accpath = \
1278 (char *)addr + ((p)->fts_accpath - (p)->fts_path); \
1280 (p)->fts_path = addr; \
1282 /* Adjust the current set of children. */
1283 for (p = sp->fts_child; p; p = p->fts_link)
1286 /* Adjust the rest of the tree, including the current level. */
1287 for (p = head; p->fts_level >= FTS_ROOTLEVEL;) {
1289 p = p->fts_link ? p->fts_link : p->fts_parent;
1295 fts_maxarglen (char * const *argv)
1299 for (max = 0; *argv; ++argv)
1300 if ((len = strlen(*argv)) > max)
1306 * Change to dir specified by fd or file name without getting
1307 * tricked by someone changing the world out from underneath us.
1308 * Assumes p->fts_statp->st_dev and p->fts_statp->st_ino are filled in.
1312 fts_safe_changedir (FTS *sp, FTSENT *p, int fd, char const *dir)
1314 int ret, oerrno, newfd;
1318 if (ISSET(FTS_NOCHDIR))
1320 if (fd < 0 && (newfd = diropen (dir)) < 0)
1322 if (fstat(newfd, &sb)) {
1326 if (p->fts_statp->st_dev != sb.st_dev
1327 || p->fts_statp->st_ino != sb.st_ino) {
1328 __set_errno (ENOENT); /* disinformation */
1332 ret = fchdir(newfd);
1337 __set_errno (oerrno);