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>
78 #if HAVE_DIRENT_H || _LIBC
80 # ifdef _D_EXACT_NAMLEN
81 # define NAMLEN(dirent) _D_EXACT_NAMLEN (dirent)
83 # define NAMLEN(dirent) strlen ((dirent)->d_name)
86 # define dirent direct
87 # define NAMLEN(dirent) (dirent)->d_namlen
93 # define close __close
95 # define closedir __closedir
97 # define fchdir __fchdir
101 # define opendir __opendir
103 # define readdir __readdir
105 # undef internal_function
106 # define internal_function /* empty */
110 # define __set_errno(Val) errno = (Val)
113 #ifndef __attribute__
114 # if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 8) || __STRICT_ANSI__
115 # define __attribute__(x) /* empty */
119 #ifndef ATTRIBUTE_UNUSED
120 # define ATTRIBUTE_UNUSED __attribute__ ((__unused__))
124 static FTSENT *fts_alloc (FTS *, const char *, size_t) internal_function;
125 static FTSENT *fts_build (FTS *, int) internal_function;
126 static void fts_lfree (FTSENT *) internal_function;
127 static void fts_load (FTS *, FTSENT *) internal_function;
128 static size_t fts_maxarglen (char * const *) internal_function;
129 static void fts_padjust (FTS *, FTSENT *) internal_function;
130 static bool fts_palloc (FTS *, size_t) internal_function;
131 static FTSENT *fts_sort (FTS *, FTSENT *, size_t) internal_function;
132 static unsigned short int fts_stat (FTS *, FTSENT *, bool) internal_function;
133 static int fts_safe_changedir (FTS *, FTSENT *, int, const char *)
137 static bool enter_dir (FTS *fts, FTSENT *ent) { return true; }
138 static void leave_dir (FTS *fts, FTSENT *ent) {}
139 static bool setup_dir (FTS *fts) { return true; }
140 static void free_dir (FTS *fts) {}
142 # include "fcntl--.h"
143 # include "fts-cycle.c"
147 # define MAX(a,b) ((a) > (b) ? (a) : (b))
151 # define SIZE_MAX ((size_t) -1)
155 # define O_DIRECTORY 0
158 #define ISDOT(a) (a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2])))
160 #define CLR(opt) (sp->fts_options &= ~(opt))
161 #define ISSET(opt) (sp->fts_options & (opt))
162 #define SET(opt) (sp->fts_options |= (opt))
164 #define FCHDIR(sp, fd) (!ISSET(FTS_NOCHDIR) && fchdir(fd))
166 /* fts_build flags */
167 #define BCHILD 1 /* fts_children */
168 #define BNAMES 2 /* fts_children, names only */
169 #define BREAD 3 /* fts_read */
172 # include <inttypes.h>
175 bool fts_debug = false;
176 # define Dprintf(x) do { if (fts_debug) printf x; } while (0)
181 #define LEAVE_DIR(Fts, Ent, Tag) \
184 Dprintf ((" %s-leaving: %s\n", Tag, (Ent)->fts_path)); \
185 leave_dir (Fts, Ent); \
189 /* Open the directory DIR if possible, and return a file
190 descriptor. Return -1 and set errno on failure. It doesn't matter
191 whether the file descriptor has read or write access. */
195 diropen (char const *dir)
197 return open (dir, O_RDONLY | O_DIRECTORY | O_NOCTTY | O_NONBLOCK);
201 fts_open (char * const *argv,
202 register int options,
203 int (*compar) (FTSENT const **, FTSENT const **))
206 register FTSENT *p, *root;
207 register size_t nitems;
208 FTSENT *parent, *tmp = NULL; /* pacify gcc */
212 if (options & ~FTS_OPTIONMASK) {
213 __set_errno (EINVAL);
217 /* Allocate/initialize the stream */
218 if ((sp = malloc(sizeof(FTS))) == NULL)
220 memset(sp, 0, sizeof(FTS));
221 sp->fts_compar = compar;
222 sp->fts_options = options;
224 /* Logical walks turn on NOCHDIR; symbolic links are too hard. */
225 if (ISSET(FTS_LOGICAL))
229 * Start out with 1K of file name space, and enough, in any case,
230 * to hold the user's file names.
233 # define MAXPATHLEN 1024
236 size_t maxarglen = fts_maxarglen(argv);
237 if (! fts_palloc(sp, MAX(maxarglen, MAXPATHLEN)))
241 /* Allocate/initialize root's parent. */
242 if ((parent = fts_alloc(sp, "", 0)) == NULL)
244 parent->fts_level = FTS_ROOTPARENTLEVEL;
246 /* Allocate/initialize root(s). */
247 for (root = NULL, nitems = 0; *argv != NULL; ++argv, ++nitems) {
248 /* Don't allow zero-length file names. */
249 if ((len = strlen(*argv)) == 0) {
250 __set_errno (ENOENT);
254 if ((p = fts_alloc(sp, *argv, len)) == NULL)
256 p->fts_level = FTS_ROOTLEVEL;
257 p->fts_parent = parent;
258 p->fts_accpath = p->fts_name;
259 p->fts_info = fts_stat(sp, p, ISSET(FTS_COMFOLLOW) != 0);
261 /* Command-line "." and ".." are real directories. */
262 if (p->fts_info == FTS_DOT)
266 * If comparison routine supplied, traverse in sorted
267 * order; otherwise traverse in the order specified.
282 if (compar && nitems > 1)
283 root = fts_sort(sp, root, nitems);
286 * Allocate a dummy pointer and make fts_read think that we've just
287 * finished the node before the root(s); set p->fts_info to FTS_INIT
288 * so that everything about the "current" node is ignored.
290 if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL)
292 sp->fts_cur->fts_link = root;
293 sp->fts_cur->fts_info = FTS_INIT;
294 if (! setup_dir (sp))
298 * If using chdir(2), grab a file descriptor pointing to dot to ensure
299 * that we can get back here; this could be avoided for some file names,
300 * but almost certainly not worth the effort. Slashes, symbolic links,
301 * and ".." are all fairly nasty problems. Note, if we can't get the
302 * descriptor we run anyway, just more slowly.
304 if (!ISSET(FTS_NOCHDIR)
305 && (sp->fts_rfd = diropen (".")) < 0)
310 mem3: fts_lfree(root);
312 mem2: free(sp->fts_path);
319 fts_load (FTS *sp, register FTSENT *p)
325 * Load the stream structure for the next traversal. Since we don't
326 * actually enter the directory until after the preorder visit, set
327 * the fts_accpath field specially so the chdir gets done to the right
328 * place and the user can access the first node. From fts_open it's
329 * known that the file name will fit.
331 len = p->fts_pathlen = p->fts_namelen;
332 memmove(sp->fts_path, p->fts_name, len + 1);
333 if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) {
335 memmove(p->fts_name, cp, len + 1);
336 p->fts_namelen = len;
338 p->fts_accpath = p->fts_path = sp->fts_path;
339 sp->fts_dev = p->fts_statp->st_dev;
345 register FTSENT *freep, *p;
349 * This still works if we haven't read anything -- the dummy structure
350 * points to the root list, so we step through to the end of the root
351 * list which has a valid parent pointer.
354 for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {
356 p = p->fts_link != NULL ? p->fts_link : p->fts_parent;
362 /* Free up child linked list, sort array, file name buffer. */
364 fts_lfree(sp->fts_child);
369 /* Return to original directory, save errno if necessary. */
370 if (!ISSET(FTS_NOCHDIR)) {
371 if (fchdir(sp->fts_rfd))
373 (void)close(sp->fts_rfd);
378 /* Free up the stream pointer. */
381 /* Set errno and return. */
383 __set_errno (saved_errno);
391 * Special case of "/" at the end of the file name so that slashes aren't
392 * appended which would cause file names to be written as "....//foo".
395 (p->fts_path[p->fts_pathlen - 1] == '/' \
396 ? p->fts_pathlen - 1 : p->fts_pathlen)
399 fts_read (register FTS *sp)
401 register FTSENT *p, *tmp;
402 register unsigned short int instr;
406 /* If finished or unrecoverable error, return NULL. */
407 if (sp->fts_cur == NULL || ISSET(FTS_STOP))
410 /* Set current node pointer. */
413 /* Save and zero out user instructions. */
414 instr = p->fts_instr;
415 p->fts_instr = FTS_NOINSTR;
417 /* Any type of file may be re-visited; re-stat and re-turn. */
418 if (instr == FTS_AGAIN) {
419 p->fts_info = fts_stat(sp, p, false);
422 Dprintf (("fts_read: p=%s\n",
423 p->fts_info == FTS_INIT ? "" : p->fts_path));
426 * Following a symlink -- SLNONE test allows application to see
427 * SLNONE and recover. If indirecting through a symlink, have
428 * keep a pointer to current location. If unable to get that
429 * pointer, follow fails.
431 if (instr == FTS_FOLLOW &&
432 (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) {
433 p->fts_info = fts_stat(sp, p, true);
434 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
435 if ((p->fts_symfd = diropen (".")) < 0) {
436 p->fts_errno = errno;
437 p->fts_info = FTS_ERR;
439 p->fts_flags |= FTS_SYMFOLLOW;
444 /* Directory in pre-order. */
445 if (p->fts_info == FTS_D) {
446 /* If skipped or crossed mount point, do post-order visit. */
447 if (instr == FTS_SKIP ||
448 (ISSET(FTS_XDEV) && p->fts_statp->st_dev != sp->fts_dev)) {
449 if (p->fts_flags & FTS_SYMFOLLOW)
450 (void)close(p->fts_symfd);
452 fts_lfree(sp->fts_child);
453 sp->fts_child = NULL;
455 p->fts_info = FTS_DP;
456 LEAVE_DIR (sp, p, "1");
460 /* Rebuild if only read the names and now traversing. */
461 if (sp->fts_child != NULL && ISSET(FTS_NAMEONLY)) {
463 fts_lfree(sp->fts_child);
464 sp->fts_child = NULL;
468 * Cd to the subdirectory.
470 * If have already read and now fail to chdir, whack the list
471 * to make the names come out right, and set the parent errno
472 * so the application will eventually get an error condition.
473 * Set the FTS_DONTCHDIR flag so that when we logically change
474 * directories back to the parent we don't do a chdir.
476 * If haven't read do so. If the read fails, fts_build sets
477 * FTS_STOP or the fts_info field of the node.
479 if (sp->fts_child != NULL) {
480 if (fts_safe_changedir(sp, p, -1, p->fts_accpath)) {
481 p->fts_errno = errno;
482 p->fts_flags |= FTS_DONTCHDIR;
483 for (p = sp->fts_child; p != NULL;
486 p->fts_parent->fts_accpath;
488 } else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) {
491 /* If fts_build's call to fts_safe_changedir failed
492 because it was not able to fchdir into a
493 subdirectory, tell the caller. */
495 p->fts_info = FTS_ERR;
496 /* FIXME: see if this should be in an else block */
497 LEAVE_DIR (sp, p, "2");
501 sp->fts_child = NULL;
505 /* Move to the next node on this level. */
507 if ((p = p->fts_link) != NULL) {
511 * If reached the top, return to the original directory (or
512 * the root of the tree), and load the file names for the next
515 if (p->fts_level == FTS_ROOTLEVEL) {
516 if (FCHDIR(sp, sp->fts_rfd)) {
526 * User may have called fts_set on the node. If skipped,
527 * ignore. If followed, get a file descriptor so we can
528 * get back if necessary.
530 if (p->fts_instr == FTS_SKIP)
532 if (p->fts_instr == FTS_FOLLOW) {
533 p->fts_info = fts_stat(sp, p, true);
534 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
535 if ((p->fts_symfd = diropen (".")) < 0) {
536 p->fts_errno = errno;
537 p->fts_info = FTS_ERR;
539 p->fts_flags |= FTS_SYMFOLLOW;
541 p->fts_instr = FTS_NOINSTR;
544 name: t = sp->fts_path + NAPPEND(p->fts_parent);
546 memmove(t, p->fts_name, p->fts_namelen + 1);
549 if (p->fts_info == FTS_D)
551 Dprintf ((" %s-entering: %s\n", sp, p->fts_path));
552 if (! enter_dir (sp, p))
554 __set_errno (ENOMEM);
561 /* Move up to the parent node. */
565 if (p->fts_level == FTS_ROOTPARENTLEVEL) {
567 * Done; free everything up and set errno to 0 so the user
568 * can distinguish between error and EOF.
572 return (sp->fts_cur = NULL);
575 /* NUL terminate the file name. */
576 sp->fts_path[p->fts_pathlen] = '\0';
579 * Return to the parent directory. If at a root node or came through
580 * a symlink, go back through the file descriptor. Otherwise, cd up
583 if (p->fts_level == FTS_ROOTLEVEL) {
584 if (FCHDIR(sp, sp->fts_rfd)) {
585 p->fts_errno = errno;
588 } else if (p->fts_flags & FTS_SYMFOLLOW) {
589 if (FCHDIR(sp, p->fts_symfd)) {
591 (void)close(p->fts_symfd);
592 __set_errno (saved_errno);
593 p->fts_errno = errno;
596 (void)close(p->fts_symfd);
597 } else if (!(p->fts_flags & FTS_DONTCHDIR) &&
598 fts_safe_changedir(sp, p->fts_parent, -1, "..")) {
599 p->fts_errno = errno;
602 p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;
603 if (p->fts_errno == 0)
604 LEAVE_DIR (sp, p, "3");
606 return ISSET(FTS_STOP) ? NULL : p;
610 * Fts_set takes the stream as an argument although it's not used in this
611 * implementation; it would be necessary if anyone wanted to add global
612 * semantics to fts using fts_set. An error return is allowed for similar
617 fts_set(FTS *sp ATTRIBUTE_UNUSED, FTSENT *p, int instr)
619 if (instr != 0 && instr != FTS_AGAIN && instr != FTS_FOLLOW &&
620 instr != FTS_NOINSTR && instr != FTS_SKIP) {
621 __set_errno (EINVAL);
624 p->fts_instr = instr;
629 fts_children (register FTS *sp, int instr)
634 if (instr != 0 && instr != FTS_NAMEONLY) {
635 __set_errno (EINVAL);
639 /* Set current node pointer. */
643 * Errno set to 0 so user can distinguish empty directory from
648 /* Fatal errors stop here. */
652 /* Return logical hierarchy of user's arguments. */
653 if (p->fts_info == FTS_INIT)
654 return (p->fts_link);
657 * If not a directory being visited in pre-order, stop here. Could
658 * allow FTS_DNR, assuming the user has fixed the problem, but the
659 * same effect is available with FTS_AGAIN.
661 if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */)
664 /* Free up any previous child list. */
665 if (sp->fts_child != NULL)
666 fts_lfree(sp->fts_child);
668 if (instr == FTS_NAMEONLY) {
675 * If using chdir on a relative file name and called BEFORE fts_read
676 * does its chdir to the root of a traversal, we can lose -- we need to
677 * chdir into the subdirectory, and we don't know where the current
678 * directory is, so we can't get back so that the upcoming chdir by
679 * fts_read will work.
681 if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' ||
683 return (sp->fts_child = fts_build(sp, instr));
685 if ((fd = diropen (".")) < 0)
686 return (sp->fts_child = NULL);
687 sp->fts_child = fts_build(sp, instr);
689 int saved_errno = errno;
691 __set_errno (saved_errno);
695 return (sp->fts_child);
699 * This is the tricky part -- do not casually change *anything* in here. The
700 * idea is to build the linked list of entries that are used by fts_children
701 * and fts_read. There are lots of special cases.
703 * The real slowdown in walking the tree is the stat calls. If FTS_NOSTAT is
704 * set and it's a physical walk (so that symbolic links can't be directories),
705 * we can do things quickly. First, if it's a 4.4BSD file system, the type
706 * of the file is in the directory entry. Otherwise, we assume that the number
707 * of subdirectories in a node is equal to the number of links to the parent.
708 * The former skips all stat calls. The latter skips stat calls in any leaf
709 * directories and for any files after the subdirectories in the directory have
710 * been found, cutting the stat calls by about 2/3.
714 fts_build (register FTS *sp, int type)
716 register struct dirent *dp;
717 register FTSENT *p, *head;
718 register size_t nitems;
729 size_t len, maxlen, new_len;
732 /* Set current node pointer. */
736 * Open the directory for reading. If this fails, we're done.
737 * If being called from fts_read, set the fts_info field.
739 #if defined FTS_WHITEOUT && 0
740 if (ISSET(FTS_WHITEOUT))
741 oflag = DTF_NODUP|DTF_REWIND;
743 oflag = DTF_HIDEW|DTF_NODUP|DTF_REWIND;
745 # define __opendir2(file, flag) opendir(file)
747 if ((dirp = __opendir2(cur->fts_accpath, oflag)) == NULL) {
749 cur->fts_info = FTS_DNR;
750 cur->fts_errno = errno;
756 * Nlinks is the number of possible entries of type directory in the
757 * directory if we're cheating on stat calls, 0 if we're not doing
758 * any stat calls at all, (nlink_t) -1 if we're statting everything.
760 if (type == BNAMES) {
762 /* Be quiet about nostat, GCC. */
764 } else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) {
765 nlinks = (cur->fts_statp->st_nlink
766 - (ISSET(FTS_SEEDOT) ? 0 : 2));
774 * If we're going to need to stat anything or we want to descend
775 * and stay in the directory, chdir. If this fails we keep going,
776 * but set a flag so we don't chdir after the post-order visit.
777 * We won't be able to stat anything, but we can still return the
778 * names themselves. Note, that since fts_read won't be able to
779 * chdir into the directory, it will have to return different file
780 * names than before, i.e. "a/b" instead of "b". Since the node
781 * has already been visited in pre-order, have to wait until the
782 * post-order visit to return the error. There is a special case
783 * here, if there was nothing to stat then it's not an error to
784 * not be able to stat. This is all fairly nasty. If a program
785 * needed sorted entries or stat information, they had better be
786 * checking FTS_NS on the returned nodes.
789 if (nlinks || type == BREAD) {
790 if (fts_safe_changedir(sp, cur, dirfd(dirp), NULL)) {
791 if (nlinks && type == BREAD)
792 cur->fts_errno = errno;
793 cur->fts_flags |= FTS_DONTCHDIR;
804 * Figure out the max file name length that can be stored in the
805 * current buffer -- the inner loop allocates more space as necessary.
806 * We really wouldn't have to do the maxlen calculations here, we
807 * could do them in fts_read before returning the name, but it's a
808 * lot easier here since the length is part of the dirent structure.
810 * If not changing directories set a pointer so that can just append
811 * each new component into the file name.
814 if (ISSET(FTS_NOCHDIR)) {
815 cp = sp->fts_path + len;
818 /* GCC, you're too verbose. */
822 maxlen = sp->fts_pathlen - len;
824 level = cur->fts_level + 1;
826 /* Read the directory, attaching each entry to the `link' pointer. */
828 for (head = tail = NULL, nitems = 0; dirp && (dp = readdir(dirp));) {
829 if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))
832 if ((p = fts_alloc(sp, dp->d_name, NAMLEN (dp))) == NULL)
834 if (NAMLEN (dp) >= maxlen) {/* include space for NUL */
835 oldaddr = sp->fts_path;
836 if (! fts_palloc(sp, NAMLEN (dp) + len + 1)) {
838 * No more memory. Save
839 * errno, free up the current structure and the
840 * structures already allocated.
842 mem1: saved_errno = errno;
847 cur->fts_info = FTS_ERR;
849 __set_errno (saved_errno);
852 /* Did realloc() change the pointer? */
853 if (oldaddr != sp->fts_path) {
855 if (ISSET(FTS_NOCHDIR))
856 cp = sp->fts_path + len;
858 maxlen = sp->fts_pathlen - len;
861 new_len = len + NAMLEN (dp);
864 * In the unlikely even that we would end up
865 * with a file name longer than SIZE_MAX, free up
866 * the current structure and the structures already
867 * allocated, then error out with ENAMETOOLONG.
872 cur->fts_info = FTS_ERR;
874 __set_errno (ENAMETOOLONG);
877 p->fts_level = level;
878 p->fts_parent = sp->fts_cur;
879 p->fts_pathlen = new_len;
881 #if defined FTS_WHITEOUT && 0
882 if (dp->d_type == DT_WHT)
883 p->fts_flags |= FTS_ISW;
888 p->fts_info = FTS_NS;
889 p->fts_errno = cderrno;
891 p->fts_info = FTS_NSOK;
892 p->fts_accpath = cur->fts_accpath;
893 } else if (nlinks == 0
894 #if HAVE_STRUCT_DIRENT_D_TYPE
896 dp->d_type != DT_DIR && dp->d_type != DT_UNKNOWN)
900 ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name;
901 p->fts_info = FTS_NSOK;
903 /* Build a file name for fts_stat to stat. */
904 if (ISSET(FTS_NOCHDIR)) {
905 p->fts_accpath = p->fts_path;
906 memmove(cp, p->fts_name, p->fts_namelen + 1);
908 p->fts_accpath = p->fts_name;
910 p->fts_info = fts_stat(sp, p, false);
912 /* Decrement link count if applicable. */
913 if (nlinks > 0 && (p->fts_info == FTS_D ||
914 p->fts_info == FTS_DC || p->fts_info == FTS_DOT))
918 /* We walk in directory order so "ls -f" doesn't get upset. */
932 * If realloc() changed the address of the file name, adjust the
933 * addresses for the rest of the tree and the dir list.
936 fts_padjust(sp, head);
939 * If not changing directories, reset the file name back to original
942 if (ISSET(FTS_NOCHDIR)) {
943 if (len == sp->fts_pathlen || nitems == 0)
949 * If descended after called from fts_children or after called from
950 * fts_read and nothing found, get back. At the root level we use
951 * the saved fd; if one of fts_open()'s arguments is a relative name
952 * to an empty directory, we wind up here with no other way back. If
953 * can't get back, we're done.
955 if (descend && (type == BCHILD || !nitems) &&
956 (cur->fts_level == FTS_ROOTLEVEL ?
957 FCHDIR(sp, sp->fts_rfd) :
958 fts_safe_changedir(sp, cur->fts_parent, -1, ".."))) {
959 cur->fts_info = FTS_ERR;
964 /* If didn't find anything, return NULL. */
967 cur->fts_info = FTS_DP;
971 /* Sort the entries. */
972 if (sp->fts_compar && nitems > 1)
973 head = fts_sort(sp, head, nitems);
979 /* Walk ->fts_parent links starting at E_CURR, until the root of the
980 current hierarchy. There should be a directory with dev/inode
981 matching those of AD. If not, print a lot of diagnostics. */
983 find_matching_ancestor (FTSENT const *e_curr, struct Active_dir const *ad)
986 for (ent = e_curr; ent->fts_level >= FTS_ROOTLEVEL; ent = ent->fts_parent)
988 if (ad->ino == ent->fts_statp->st_ino
989 && ad->dev == ent->fts_statp->st_dev)
992 printf ("ERROR: tree dir, %s, not active\n", ad->fts_ent->fts_accpath);
993 printf ("active dirs:\n");
995 ent->fts_level >= FTS_ROOTLEVEL; ent = ent->fts_parent)
996 printf (" %s(%"PRIuMAX"/%"PRIuMAX") to %s(%"PRIuMAX"/%"PRIuMAX")...\n",
997 ad->fts_ent->fts_accpath,
1001 (uintmax_t) ent->fts_statp->st_dev,
1002 (uintmax_t) ent->fts_statp->st_ino);
1006 fts_cross_check (FTS const *sp)
1008 FTSENT const *ent = sp->fts_cur;
1010 if ( ! ISSET (FTS_TIGHT_CYCLE_CHECK))
1013 Dprintf (("fts-cross-check cur=%s\n", ent->fts_path));
1014 /* Make sure every parent dir is in the tree. */
1015 for (t = ent->fts_parent; t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
1017 struct Active_dir ad;
1018 ad.ino = t->fts_statp->st_ino;
1019 ad.dev = t->fts_statp->st_dev;
1020 if ( ! hash_lookup (sp->fts_cycle.ht, &ad))
1021 printf ("ERROR: active dir, %s, not in tree\n", t->fts_path);
1024 /* Make sure every dir in the tree is an active dir.
1025 But ENT is not necessarily a directory. If so, just skip this part. */
1026 if (ent->fts_parent->fts_level >= FTS_ROOTLEVEL
1027 && (ent->fts_info == FTS_DP
1028 || ent->fts_info == FTS_D))
1030 struct Active_dir *ad;
1031 for (ad = hash_get_first (sp->fts_cycle.ht); ad != NULL;
1032 ad = hash_get_next (sp->fts_cycle.ht, ad))
1034 find_matching_ancestor (ent, ad);
1040 static unsigned short int
1042 fts_stat(FTS *sp, register FTSENT *p, bool follow)
1044 struct stat *sbp = p->fts_statp;
1047 #if defined FTS_WHITEOUT && 0
1048 /* check for whiteout */
1049 if (p->fts_flags & FTS_ISW) {
1050 memset(sbp, '\0', sizeof (*sbp));
1051 sbp->st_mode = S_IFWHT;
1057 * If doing a logical walk, or application requested FTS_FOLLOW, do
1058 * a stat(2). If that fails, check for a non-existent symlink. If
1059 * fail, set the errno from the stat call.
1061 if (ISSET(FTS_LOGICAL) || follow) {
1062 if (stat(p->fts_accpath, sbp)) {
1063 saved_errno = errno;
1065 && lstat(p->fts_accpath, sbp) == 0) {
1067 return (FTS_SLNONE);
1069 p->fts_errno = saved_errno;
1072 } else if (lstat(p->fts_accpath, sbp)) {
1073 p->fts_errno = errno;
1074 err: memset(sbp, 0, sizeof(struct stat));
1078 if (S_ISDIR(sbp->st_mode)) {
1079 if (ISDOT(p->fts_name))
1085 * Cycle detection is done by brute force when the directory
1086 * is first encountered. If the tree gets deep enough or the
1087 * number of symbolic links to directories is high enough,
1088 * something faster might be worthwhile.
1092 for (t = p->fts_parent;
1093 t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
1094 if (sbp->st_ino == t->fts_statp->st_ino
1095 && sbp->st_dev == t->fts_statp->st_dev)
1105 if (S_ISLNK(sbp->st_mode))
1107 if (S_ISREG(sbp->st_mode))
1109 return (FTS_DEFAULT);
1113 fts_compar (void const *a, void const *b)
1115 /* Convert A and B to the correct types, to pacify the compiler, and
1116 for portability to bizarre hosts where "void const *" and "FTSENT
1117 const **" differ in runtime representation. The comparison
1118 function cannot modify *a and *b, but there is no compile-time
1120 FTSENT const **pa = (FTSENT const **) a;
1121 FTSENT const **pb = (FTSENT const **) b;
1122 return pa[0]->fts_fts->fts_compar (pa, pb);
1127 fts_sort (FTS *sp, FTSENT *head, register size_t nitems)
1129 register FTSENT **ap, *p;
1131 /* On most modern hosts, void * and FTSENT ** have the same
1132 run-time representation, and one can convert sp->fts_compar to
1133 the type qsort expects without problem. Use the heuristic that
1134 this is OK if the two pointer types are the same size, and if
1135 converting FTSENT ** to long int is the same as converting
1136 FTSENT ** to void * and then to long int. This heuristic isn't
1137 valid in general but we don't know of any counterexamples. */
1139 int (*compare) (void const *, void const *) =
1140 ((sizeof &dummy == sizeof (void *)
1141 && (long int) &dummy == (long int) (void *) &dummy)
1142 ? (int (*) (void const *, void const *)) sp->fts_compar
1146 * Construct an array of pointers to the structures and call qsort(3).
1147 * Reassemble the array in the order returned by qsort. If unable to
1148 * sort for memory reasons, return the directory entries in their
1149 * current order. Allocate enough space for the current needs plus
1150 * 40 so don't realloc one entry at a time.
1152 if (nitems > sp->fts_nitems) {
1155 sp->fts_nitems = nitems + 40;
1156 if (SIZE_MAX / sizeof *a < sp->fts_nitems
1157 || ! (a = realloc (sp->fts_array,
1158 sp->fts_nitems * sizeof *a))) {
1159 free(sp->fts_array);
1160 sp->fts_array = NULL;
1166 for (ap = sp->fts_array, p = head; p; p = p->fts_link)
1168 qsort((void *)sp->fts_array, nitems, sizeof(FTSENT *), compare);
1169 for (head = *(ap = sp->fts_array); --nitems; ++ap)
1170 ap[0]->fts_link = ap[1];
1171 ap[0]->fts_link = NULL;
1177 fts_alloc (FTS *sp, const char *name, register size_t namelen)
1183 * The file name is a variable length array. Allocate the FTSENT
1184 * structure and the file name in one chunk.
1186 len = sizeof(FTSENT) + namelen;
1187 if ((p = malloc(len)) == NULL)
1190 /* Copy the name and guarantee NUL termination. */
1191 memmove(p->fts_name, name, namelen);
1192 p->fts_name[namelen] = '\0';
1194 p->fts_namelen = namelen;
1196 p->fts_path = sp->fts_path;
1199 p->fts_instr = FTS_NOINSTR;
1201 p->fts_pointer = NULL;
1207 fts_lfree (register FTSENT *head)
1211 /* Free a linked list of structures. */
1212 while ((p = head)) {
1213 head = head->fts_link;
1219 * Allow essentially unlimited file name lengths; find, rm, ls should
1220 * all work on any tree. Most systems will allow creation of file
1221 * names much longer than MAXPATHLEN, even though the kernel won't
1222 * resolve them. Add the size (not just what's needed) plus 256 bytes
1223 * so don't realloc the file name 2 bytes at a time.
1227 fts_palloc (FTS *sp, size_t more)
1230 size_t new_len = sp->fts_pathlen + more + 256;
1233 * See if fts_pathlen would overflow.
1235 if (new_len < sp->fts_pathlen) {
1238 sp->fts_path = NULL;
1240 sp->fts_path = NULL;
1241 __set_errno (ENAMETOOLONG);
1244 sp->fts_pathlen = new_len;
1245 p = realloc(sp->fts_path, sp->fts_pathlen);
1248 sp->fts_path = NULL;
1256 * When the file name is realloc'd, have to fix all of the pointers in
1257 * structures already returned.
1261 fts_padjust (FTS *sp, FTSENT *head)
1264 char *addr = sp->fts_path;
1266 #define ADJUST(p) do { \
1267 if ((p)->fts_accpath != (p)->fts_name) { \
1268 (p)->fts_accpath = \
1269 (char *)addr + ((p)->fts_accpath - (p)->fts_path); \
1271 (p)->fts_path = addr; \
1273 /* Adjust the current set of children. */
1274 for (p = sp->fts_child; p; p = p->fts_link)
1277 /* Adjust the rest of the tree, including the current level. */
1278 for (p = head; p->fts_level >= FTS_ROOTLEVEL;) {
1280 p = p->fts_link ? p->fts_link : p->fts_parent;
1286 fts_maxarglen (char * const *argv)
1290 for (max = 0; *argv; ++argv)
1291 if ((len = strlen(*argv)) > max)
1297 * Change to dir specified by fd or file name without getting
1298 * tricked by someone changing the world out from underneath us.
1299 * Assumes p->fts_statp->st_dev and p->fts_statp->st_ino are filled in.
1303 fts_safe_changedir (FTS *sp, FTSENT *p, int fd, char const *dir)
1305 int ret, oerrno, newfd;
1309 if (ISSET(FTS_NOCHDIR))
1311 if (fd < 0 && (newfd = diropen (dir)) < 0)
1313 if (fstat(newfd, &sb)) {
1317 if (p->fts_statp->st_dev != sb.st_dev
1318 || p->fts_statp->st_ino != sb.st_ino) {
1319 __set_errno (ENOENT); /* disinformation */
1323 ret = fchdir(newfd);
1328 __set_errno (oerrno);