1 /* Traverse a file hierarchy.
3 Copyright (C) 2004, 2005 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 int fd = open (dir, O_RDONLY | O_DIRECTORY);
208 fd = open (dir, O_WRONLY | O_DIRECTORY);
213 fts_open (char * const *argv,
214 register int options,
215 int (*compar) (FTSENT const **, FTSENT const **))
218 register FTSENT *p, *root;
219 register size_t nitems;
220 FTSENT *parent, *tmp = NULL; /* pacify gcc */
224 if (options & ~FTS_OPTIONMASK) {
225 __set_errno (EINVAL);
229 /* Allocate/initialize the stream */
230 if ((sp = malloc(sizeof(FTS))) == NULL)
232 memset(sp, 0, sizeof(FTS));
233 sp->fts_compar = compar;
234 sp->fts_options = options;
236 /* Logical walks turn on NOCHDIR; symbolic links are too hard. */
237 if (ISSET(FTS_LOGICAL))
241 * Start out with 1K of file name space, and enough, in any case,
242 * to hold the user's file names.
245 # define MAXPATHLEN 1024
247 if (! fts_palloc(sp, MAX(fts_maxarglen(argv), 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)) {
534 * User may have called fts_set on the node. If skipped,
535 * ignore. If followed, get a file descriptor so we can
536 * get back if necessary.
538 if (p->fts_instr == FTS_SKIP)
540 if (p->fts_instr == FTS_FOLLOW) {
541 p->fts_info = fts_stat(sp, p, true);
542 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
543 if ((p->fts_symfd = diropen (".")) < 0) {
544 p->fts_errno = errno;
545 p->fts_info = FTS_ERR;
547 p->fts_flags |= FTS_SYMFOLLOW;
549 p->fts_instr = FTS_NOINSTR;
552 name: t = sp->fts_path + NAPPEND(p->fts_parent);
554 memmove(t, p->fts_name, p->fts_namelen + 1);
557 if (p->fts_info == FTS_D)
559 Dprintf ((" %s-entering: %s\n", sp, p->fts_path));
560 if (! enter_dir (sp, p))
562 __set_errno (ENOMEM);
569 /* Move up to the parent node. */
573 if (p->fts_level == FTS_ROOTPARENTLEVEL) {
575 * Done; free everything up and set errno to 0 so the user
576 * can distinguish between error and EOF.
580 return (sp->fts_cur = NULL);
583 /* NUL terminate the file name. */
584 sp->fts_path[p->fts_pathlen] = '\0';
587 * Return to the parent directory. If at a root node or came through
588 * a symlink, go back through the file descriptor. Otherwise, cd up
591 if (p->fts_level == FTS_ROOTLEVEL) {
592 if (FCHDIR(sp, sp->fts_rfd)) {
593 p->fts_errno = errno;
596 } else if (p->fts_flags & FTS_SYMFOLLOW) {
597 if (FCHDIR(sp, p->fts_symfd)) {
599 (void)close(p->fts_symfd);
600 __set_errno (saved_errno);
601 p->fts_errno = errno;
604 (void)close(p->fts_symfd);
605 } else if (!(p->fts_flags & FTS_DONTCHDIR) &&
606 fts_safe_changedir(sp, p->fts_parent, -1, "..")) {
607 p->fts_errno = errno;
610 p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;
611 if (p->fts_errno == 0)
612 LEAVE_DIR (sp, p, "3");
614 return ISSET(FTS_STOP) ? NULL : p;
618 * Fts_set takes the stream as an argument although it's not used in this
619 * implementation; it would be necessary if anyone wanted to add global
620 * semantics to fts using fts_set. An error return is allowed for similar
625 fts_set(FTS *sp ATTRIBUTE_UNUSED, FTSENT *p, int instr)
627 if (instr != 0 && instr != FTS_AGAIN && instr != FTS_FOLLOW &&
628 instr != FTS_NOINSTR && instr != FTS_SKIP) {
629 __set_errno (EINVAL);
632 p->fts_instr = instr;
637 fts_children (register FTS *sp, int instr)
642 if (instr != 0 && instr != FTS_NAMEONLY) {
643 __set_errno (EINVAL);
647 /* Set current node pointer. */
651 * Errno set to 0 so user can distinguish empty directory from
656 /* Fatal errors stop here. */
660 /* Return logical hierarchy of user's arguments. */
661 if (p->fts_info == FTS_INIT)
662 return (p->fts_link);
665 * If not a directory being visited in pre-order, stop here. Could
666 * allow FTS_DNR, assuming the user has fixed the problem, but the
667 * same effect is available with FTS_AGAIN.
669 if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */)
672 /* Free up any previous child list. */
673 if (sp->fts_child != NULL)
674 fts_lfree(sp->fts_child);
676 if (instr == FTS_NAMEONLY) {
683 * If using chdir on a relative file name and called BEFORE fts_read
684 * does its chdir to the root of a traversal, we can lose -- we need to
685 * chdir into the subdirectory, and we don't know where the current
686 * directory is, so we can't get back so that the upcoming chdir by
687 * fts_read will work.
689 if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' ||
691 return (sp->fts_child = fts_build(sp, instr));
693 if ((fd = diropen (".")) < 0)
694 return (sp->fts_child = NULL);
695 sp->fts_child = fts_build(sp, instr);
701 return (sp->fts_child);
705 * This is the tricky part -- do not casually change *anything* in here. The
706 * idea is to build the linked list of entries that are used by fts_children
707 * and fts_read. There are lots of special cases.
709 * The real slowdown in walking the tree is the stat calls. If FTS_NOSTAT is
710 * set and it's a physical walk (so that symbolic links can't be directories),
711 * we can do things quickly. First, if it's a 4.4BSD file system, the type
712 * of the file is in the directory entry. Otherwise, we assume that the number
713 * of subdirectories in a node is equal to the number of links to the parent.
714 * The former skips all stat calls. The latter skips stat calls in any leaf
715 * directories and for any files after the subdirectories in the directory have
716 * been found, cutting the stat calls by about 2/3.
720 fts_build (register FTS *sp, int type)
722 register struct dirent *dp;
723 register FTSENT *p, *head;
724 register size_t nitems;
735 size_t len, maxlen, new_len;
738 /* Set current node pointer. */
742 * Open the directory for reading. If this fails, we're done.
743 * If being called from fts_read, set the fts_info field.
745 #if defined FTS_WHITEOUT && 0
746 if (ISSET(FTS_WHITEOUT))
747 oflag = DTF_NODUP|DTF_REWIND;
749 oflag = DTF_HIDEW|DTF_NODUP|DTF_REWIND;
751 # define __opendir2(file, flag) opendir(file)
753 if ((dirp = __opendir2(cur->fts_accpath, oflag)) == NULL) {
755 cur->fts_info = FTS_DNR;
756 cur->fts_errno = errno;
762 * Nlinks is the number of possible entries of type directory in the
763 * directory if we're cheating on stat calls, 0 if we're not doing
764 * any stat calls at all, (nlink_t) -1 if we're statting everything.
766 if (type == BNAMES) {
768 /* Be quiet about nostat, GCC. */
770 } else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) {
771 nlinks = (cur->fts_statp->st_nlink
772 - (ISSET(FTS_SEEDOT) ? 0 : 2));
780 * If we're going to need to stat anything or we want to descend
781 * and stay in the directory, chdir. If this fails we keep going,
782 * but set a flag so we don't chdir after the post-order visit.
783 * We won't be able to stat anything, but we can still return the
784 * names themselves. Note, that since fts_read won't be able to
785 * chdir into the directory, it will have to return different file
786 * names than before, i.e. "a/b" instead of "b". Since the node
787 * has already been visited in pre-order, have to wait until the
788 * post-order visit to return the error. There is a special case
789 * here, if there was nothing to stat then it's not an error to
790 * not be able to stat. This is all fairly nasty. If a program
791 * needed sorted entries or stat information, they had better be
792 * checking FTS_NS on the returned nodes.
795 if (nlinks || type == BREAD) {
796 if (fts_safe_changedir(sp, cur, dirfd(dirp), NULL)) {
797 if (nlinks && type == BREAD)
798 cur->fts_errno = errno;
799 cur->fts_flags |= FTS_DONTCHDIR;
810 * Figure out the max file name length that can be stored in the
811 * current buffer -- the inner loop allocates more space as necessary.
812 * We really wouldn't have to do the maxlen calculations here, we
813 * could do them in fts_read before returning the name, but it's a
814 * lot easier here since the length is part of the dirent structure.
816 * If not changing directories set a pointer so that can just append
817 * each new component into the file name.
820 if (ISSET(FTS_NOCHDIR)) {
821 cp = sp->fts_path + len;
824 /* GCC, you're too verbose. */
828 maxlen = sp->fts_pathlen - len;
830 level = cur->fts_level + 1;
832 /* Read the directory, attaching each entry to the `link' pointer. */
834 for (head = tail = NULL, nitems = 0; dirp && (dp = readdir(dirp));) {
835 if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))
838 if ((p = fts_alloc(sp, dp->d_name, NAMLEN (dp))) == NULL)
840 if (NAMLEN (dp) >= maxlen) {/* include space for NUL */
841 oldaddr = sp->fts_path;
842 if (! fts_palloc(sp, NAMLEN (dp) + len + 1)) {
844 * No more memory. Save
845 * errno, free up the current structure and the
846 * structures already allocated.
848 mem1: saved_errno = errno;
853 cur->fts_info = FTS_ERR;
855 __set_errno (saved_errno);
858 /* Did realloc() change the pointer? */
859 if (oldaddr != sp->fts_path) {
861 if (ISSET(FTS_NOCHDIR))
862 cp = sp->fts_path + len;
864 maxlen = sp->fts_pathlen - len;
867 new_len = len + NAMLEN (dp);
870 * In the unlikely even that we would end up
871 * with a file name longer than SIZE_MAX, free up
872 * the current structure and the structures already
873 * allocated, then error out with ENAMETOOLONG.
878 cur->fts_info = FTS_ERR;
880 __set_errno (ENAMETOOLONG);
883 p->fts_level = level;
884 p->fts_parent = sp->fts_cur;
885 p->fts_pathlen = new_len;
887 #if defined FTS_WHITEOUT && 0
888 if (dp->d_type == DT_WHT)
889 p->fts_flags |= FTS_ISW;
894 p->fts_info = FTS_NS;
895 p->fts_errno = cderrno;
897 p->fts_info = FTS_NSOK;
898 p->fts_accpath = cur->fts_accpath;
899 } else if (nlinks == 0
900 #if HAVE_STRUCT_DIRENT_D_TYPE
902 dp->d_type != DT_DIR && dp->d_type != DT_UNKNOWN)
906 ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name;
907 p->fts_info = FTS_NSOK;
909 /* Build a file name for fts_stat to stat. */
910 if (ISSET(FTS_NOCHDIR)) {
911 p->fts_accpath = p->fts_path;
912 memmove(cp, p->fts_name, p->fts_namelen + 1);
914 p->fts_accpath = p->fts_name;
916 p->fts_info = fts_stat(sp, p, false);
918 /* Decrement link count if applicable. */
919 if (nlinks > 0 && (p->fts_info == FTS_D ||
920 p->fts_info == FTS_DC || p->fts_info == FTS_DOT))
924 /* We walk in directory order so "ls -f" doesn't get upset. */
938 * If realloc() changed the address of the file name, adjust the
939 * addresses for the rest of the tree and the dir list.
942 fts_padjust(sp, head);
945 * If not changing directories, reset the file name back to original
948 if (ISSET(FTS_NOCHDIR)) {
949 if (len == sp->fts_pathlen || nitems == 0)
955 * If descended after called from fts_children or after called from
956 * fts_read and nothing found, get back. At the root level we use
957 * the saved fd; if one of fts_open()'s arguments is a relative name
958 * to an empty directory, we wind up here with no other way back. If
959 * can't get back, we're done.
961 if (descend && (type == BCHILD || !nitems) &&
962 (cur->fts_level == FTS_ROOTLEVEL ?
963 FCHDIR(sp, sp->fts_rfd) :
964 fts_safe_changedir(sp, cur->fts_parent, -1, ".."))) {
965 cur->fts_info = FTS_ERR;
970 /* If didn't find anything, return NULL. */
973 cur->fts_info = FTS_DP;
977 /* Sort the entries. */
978 if (sp->fts_compar && nitems > 1)
979 head = fts_sort(sp, head, nitems);
985 /* Walk ->fts_parent links starting at E_CURR, until the root of the
986 current hierarchy. There should be a directory with dev/inode
987 matching those of AD. If not, print a lot of diagnostics. */
989 find_matching_ancestor (FTSENT const *e_curr, struct Active_dir const *ad)
992 for (ent = e_curr; ent->fts_level >= FTS_ROOTLEVEL; ent = ent->fts_parent)
994 if (ad->ino == ent->fts_statp->st_ino
995 && ad->dev == ent->fts_statp->st_dev)
998 printf ("ERROR: tree dir, %s, not active\n", ad->fts_ent->fts_accpath);
999 printf ("active dirs:\n");
1001 ent->fts_level >= FTS_ROOTLEVEL; ent = ent->fts_parent)
1002 printf (" %s(%"PRIuMAX"/%"PRIuMAX") to %s(%"PRIuMAX"/%"PRIuMAX")...\n",
1003 ad->fts_ent->fts_accpath,
1004 (uintmax_t) ad->dev,
1005 (uintmax_t) ad->ino,
1007 (uintmax_t) ent->fts_statp->st_dev,
1008 (uintmax_t) ent->fts_statp->st_ino);
1012 fts_cross_check (FTS const *sp)
1014 FTSENT const *ent = sp->fts_cur;
1016 if ( ! ISSET (FTS_TIGHT_CYCLE_CHECK))
1019 Dprintf (("fts-cross-check cur=%s\n", ent->fts_path));
1020 /* Make sure every parent dir is in the tree. */
1021 for (t = ent->fts_parent; t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
1023 struct Active_dir ad;
1024 ad.ino = t->fts_statp->st_ino;
1025 ad.dev = t->fts_statp->st_dev;
1026 if ( ! hash_lookup (sp->fts_cycle.ht, &ad))
1027 printf ("ERROR: active dir, %s, not in tree\n", t->fts_path);
1030 /* Make sure every dir in the tree is an active dir.
1031 But ENT is not necessarily a directory. If so, just skip this part. */
1032 if (ent->fts_parent->fts_level >= FTS_ROOTLEVEL
1033 && (ent->fts_info == FTS_DP
1034 || ent->fts_info == FTS_D))
1036 struct Active_dir *ad;
1037 for (ad = hash_get_first (sp->fts_cycle.ht); ad != NULL;
1038 ad = hash_get_next (sp->fts_cycle.ht, ad))
1040 find_matching_ancestor (ent, ad);
1046 static unsigned short int
1048 fts_stat(FTS *sp, register FTSENT *p, bool follow)
1050 struct stat *sbp = p->fts_statp;
1053 #if defined FTS_WHITEOUT && 0
1054 /* check for whiteout */
1055 if (p->fts_flags & FTS_ISW) {
1056 memset(sbp, '\0', sizeof (*sbp));
1057 sbp->st_mode = S_IFWHT;
1063 * If doing a logical walk, or application requested FTS_FOLLOW, do
1064 * a stat(2). If that fails, check for a non-existent symlink. If
1065 * fail, set the errno from the stat call.
1067 if (ISSET(FTS_LOGICAL) || follow) {
1068 if (stat(p->fts_accpath, sbp)) {
1069 saved_errno = errno;
1070 if (!lstat(p->fts_accpath, sbp)) {
1072 return (FTS_SLNONE);
1074 p->fts_errno = saved_errno;
1077 } else if (lstat(p->fts_accpath, sbp)) {
1078 p->fts_errno = errno;
1079 err: memset(sbp, 0, sizeof(struct stat));
1083 if (S_ISDIR(sbp->st_mode)) {
1084 if (ISDOT(p->fts_name))
1090 * Cycle detection is done by brute force when the directory
1091 * is first encountered. If the tree gets deep enough or the
1092 * number of symbolic links to directories is high enough,
1093 * something faster might be worthwhile.
1097 for (t = p->fts_parent;
1098 t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
1099 if (sbp->st_ino == t->fts_statp->st_ino
1100 && sbp->st_dev == t->fts_statp->st_dev)
1110 if (S_ISLNK(sbp->st_mode))
1112 if (S_ISREG(sbp->st_mode))
1114 return (FTS_DEFAULT);
1118 fts_compar (void const *a, void const *b)
1120 /* Convert A and B to the correct types, to pacify the compiler, and
1121 for portability to bizarre hosts where "void const *" and "FTSENT
1122 const **" differ in runtime representation. The comparison
1123 function cannot modify *a and *b, but there is no compile-time
1125 FTSENT const **pa = (FTSENT const **) a;
1126 FTSENT const **pb = (FTSENT const **) b;
1127 return pa[0]->fts_fts->fts_compar (pa, pb);
1132 fts_sort (FTS *sp, FTSENT *head, register size_t nitems)
1134 register FTSENT **ap, *p;
1136 /* On most modern hosts, void * and FTSENT ** have the same
1137 run-time representation, and one can convert sp->fts_compar to
1138 the type qsort expects without problem. Use the heuristic that
1139 this is OK if the two pointer types are the same size, and if
1140 converting FTSENT ** to long int is the same as converting
1141 FTSENT ** to void * and then to long int. This heuristic isn't
1142 valid in general but we don't know of any counterexamples. */
1144 int (*compare) (void const *, void const *) =
1145 ((sizeof &dummy == sizeof (void *)
1146 && (long int) &dummy == (long int) (void *) &dummy)
1147 ? (int (*) (void const *, void const *)) sp->fts_compar
1151 * Construct an array of pointers to the structures and call qsort(3).
1152 * Reassemble the array in the order returned by qsort. If unable to
1153 * sort for memory reasons, return the directory entries in their
1154 * current order. Allocate enough space for the current needs plus
1155 * 40 so don't realloc one entry at a time.
1157 if (nitems > sp->fts_nitems) {
1160 sp->fts_nitems = nitems + 40;
1161 if (SIZE_MAX / sizeof *a < sp->fts_nitems
1162 || ! (a = realloc (sp->fts_array,
1163 sp->fts_nitems * sizeof *a))) {
1164 free(sp->fts_array);
1165 sp->fts_array = NULL;
1171 for (ap = sp->fts_array, p = head; p; p = p->fts_link)
1173 qsort((void *)sp->fts_array, nitems, sizeof(FTSENT *), compare);
1174 for (head = *(ap = sp->fts_array); --nitems; ++ap)
1175 ap[0]->fts_link = ap[1];
1176 ap[0]->fts_link = NULL;
1182 fts_alloc (FTS *sp, const char *name, register size_t namelen)
1188 * The file name is a variable length array. Allocate the FTSENT
1189 * structure and the file name in one chunk.
1191 len = sizeof(FTSENT) + namelen;
1192 if ((p = malloc(len)) == NULL)
1195 /* Copy the name and guarantee NUL termination. */
1196 memmove(p->fts_name, name, namelen);
1197 p->fts_name[namelen] = '\0';
1199 p->fts_namelen = namelen;
1201 p->fts_path = sp->fts_path;
1204 p->fts_instr = FTS_NOINSTR;
1206 p->fts_pointer = NULL;
1212 fts_lfree (register FTSENT *head)
1216 /* Free a linked list of structures. */
1217 while ((p = head)) {
1218 head = head->fts_link;
1224 * Allow essentially unlimited file name lengths; find, rm, ls should
1225 * all work on any tree. Most systems will allow creation of file
1226 * names much longer than MAXPATHLEN, even though the kernel won't
1227 * resolve them. Add the size (not just what's needed) plus 256 bytes
1228 * so don't realloc the file name 2 bytes at a time.
1232 fts_palloc (FTS *sp, size_t more)
1235 size_t new_len = sp->fts_pathlen + more + 256;
1238 * See if fts_pathlen would overflow.
1240 if (new_len < sp->fts_pathlen) {
1243 sp->fts_path = NULL;
1245 sp->fts_path = NULL;
1246 __set_errno (ENAMETOOLONG);
1249 sp->fts_pathlen = new_len;
1250 p = realloc(sp->fts_path, sp->fts_pathlen);
1253 sp->fts_path = NULL;
1261 * When the file name is realloc'd, have to fix all of the pointers in
1262 * structures already returned.
1266 fts_padjust (FTS *sp, FTSENT *head)
1269 char *addr = sp->fts_path;
1271 #define ADJUST(p) do { \
1272 if ((p)->fts_accpath != (p)->fts_name) { \
1273 (p)->fts_accpath = \
1274 (char *)addr + ((p)->fts_accpath - (p)->fts_path); \
1276 (p)->fts_path = addr; \
1278 /* Adjust the current set of children. */
1279 for (p = sp->fts_child; p; p = p->fts_link)
1282 /* Adjust the rest of the tree, including the current level. */
1283 for (p = head; p->fts_level >= FTS_ROOTLEVEL;) {
1285 p = p->fts_link ? p->fts_link : p->fts_parent;
1291 fts_maxarglen (char * const *argv)
1295 for (max = 0; *argv; ++argv)
1296 if ((len = strlen(*argv)) > max)
1302 * Change to dir specified by fd or file name without getting
1303 * tricked by someone changing the world out from underneath us.
1304 * Assumes p->fts_statp->st_dev and p->fts_statp->st_ino are filled in.
1308 fts_safe_changedir (FTS *sp, FTSENT *p, int fd, char const *dir)
1310 int ret, oerrno, newfd;
1314 if (ISSET(FTS_NOCHDIR))
1316 if (fd < 0 && (newfd = diropen (dir)) < 0)
1318 if (fstat(newfd, &sb)) {
1322 if (p->fts_statp->st_dev != sb.st_dev
1323 || p->fts_statp->st_ino != sb.st_ino) {
1324 __set_errno (ENOENT); /* disinformation */
1328 ret = fchdir(newfd);
1333 __set_errno (oerrno);