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
244 size_t maxarglen = fts_maxarglen(argv);
245 if (! fts_palloc(sp, MAX(maxarglen, MAXPATHLEN)))
248 /* Allocate/initialize root's parent. */
249 if ((parent = fts_alloc(sp, "", 0)) == NULL)
251 parent->fts_level = FTS_ROOTPARENTLEVEL;
253 /* Allocate/initialize root(s). */
254 for (root = NULL, nitems = 0; *argv != NULL; ++argv, ++nitems) {
255 /* Don't allow zero-length file names. */
256 if ((len = strlen(*argv)) == 0) {
257 __set_errno (ENOENT);
261 if ((p = fts_alloc(sp, *argv, len)) == NULL)
263 p->fts_level = FTS_ROOTLEVEL;
264 p->fts_parent = parent;
265 p->fts_accpath = p->fts_name;
266 p->fts_info = fts_stat(sp, p, ISSET(FTS_COMFOLLOW) != 0);
268 /* Command-line "." and ".." are real directories. */
269 if (p->fts_info == FTS_DOT)
273 * If comparison routine supplied, traverse in sorted
274 * order; otherwise traverse in the order specified.
289 if (compar && nitems > 1)
290 root = fts_sort(sp, root, nitems);
293 * Allocate a dummy pointer and make fts_read think that we've just
294 * finished the node before the root(s); set p->fts_info to FTS_INIT
295 * so that everything about the "current" node is ignored.
297 if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL)
299 sp->fts_cur->fts_link = root;
300 sp->fts_cur->fts_info = FTS_INIT;
301 if (! setup_dir (sp))
305 * If using chdir(2), grab a file descriptor pointing to dot to ensure
306 * that we can get back here; this could be avoided for some file names,
307 * but almost certainly not worth the effort. Slashes, symbolic links,
308 * and ".." are all fairly nasty problems. Note, if we can't get the
309 * descriptor we run anyway, just more slowly.
311 if (!ISSET(FTS_NOCHDIR)
312 && (sp->fts_rfd = diropen (".")) < 0)
317 mem3: fts_lfree(root);
319 mem2: free(sp->fts_path);
326 fts_load (FTS *sp, register FTSENT *p)
332 * Load the stream structure for the next traversal. Since we don't
333 * actually enter the directory until after the preorder visit, set
334 * the fts_accpath field specially so the chdir gets done to the right
335 * place and the user can access the first node. From fts_open it's
336 * known that the file name will fit.
338 len = p->fts_pathlen = p->fts_namelen;
339 memmove(sp->fts_path, p->fts_name, len + 1);
340 if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) {
342 memmove(p->fts_name, cp, len + 1);
343 p->fts_namelen = len;
345 p->fts_accpath = p->fts_path = sp->fts_path;
346 sp->fts_dev = p->fts_statp->st_dev;
352 register FTSENT *freep, *p;
356 * This still works if we haven't read anything -- the dummy structure
357 * points to the root list, so we step through to the end of the root
358 * list which has a valid parent pointer.
361 for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {
363 p = p->fts_link != NULL ? p->fts_link : p->fts_parent;
369 /* Free up child linked list, sort array, file name buffer. */
371 fts_lfree(sp->fts_child);
376 /* Return to original directory, save errno if necessary. */
377 if (!ISSET(FTS_NOCHDIR)) {
378 if (fchdir(sp->fts_rfd))
380 (void)close(sp->fts_rfd);
385 /* Free up the stream pointer. */
388 /* Set errno and return. */
390 __set_errno (saved_errno);
398 * Special case of "/" at the end of the file name so that slashes aren't
399 * appended which would cause file names to be written as "....//foo".
402 (p->fts_path[p->fts_pathlen - 1] == '/' \
403 ? p->fts_pathlen - 1 : p->fts_pathlen)
406 fts_read (register FTS *sp)
408 register FTSENT *p, *tmp;
409 register unsigned short int instr;
413 /* If finished or unrecoverable error, return NULL. */
414 if (sp->fts_cur == NULL || ISSET(FTS_STOP))
417 /* Set current node pointer. */
420 /* Save and zero out user instructions. */
421 instr = p->fts_instr;
422 p->fts_instr = FTS_NOINSTR;
424 /* Any type of file may be re-visited; re-stat and re-turn. */
425 if (instr == FTS_AGAIN) {
426 p->fts_info = fts_stat(sp, p, false);
429 Dprintf (("fts_read: p=%s\n",
430 p->fts_info == FTS_INIT ? "" : p->fts_path));
433 * Following a symlink -- SLNONE test allows application to see
434 * SLNONE and recover. If indirecting through a symlink, have
435 * keep a pointer to current location. If unable to get that
436 * pointer, follow fails.
438 if (instr == FTS_FOLLOW &&
439 (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) {
440 p->fts_info = fts_stat(sp, p, true);
441 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
442 if ((p->fts_symfd = diropen (".")) < 0) {
443 p->fts_errno = errno;
444 p->fts_info = FTS_ERR;
446 p->fts_flags |= FTS_SYMFOLLOW;
451 /* Directory in pre-order. */
452 if (p->fts_info == FTS_D) {
453 /* If skipped or crossed mount point, do post-order visit. */
454 if (instr == FTS_SKIP ||
455 (ISSET(FTS_XDEV) && p->fts_statp->st_dev != sp->fts_dev)) {
456 if (p->fts_flags & FTS_SYMFOLLOW)
457 (void)close(p->fts_symfd);
459 fts_lfree(sp->fts_child);
460 sp->fts_child = NULL;
462 p->fts_info = FTS_DP;
463 LEAVE_DIR (sp, p, "1");
467 /* Rebuild if only read the names and now traversing. */
468 if (sp->fts_child != NULL && ISSET(FTS_NAMEONLY)) {
470 fts_lfree(sp->fts_child);
471 sp->fts_child = NULL;
475 * Cd to the subdirectory.
477 * If have already read and now fail to chdir, whack the list
478 * to make the names come out right, and set the parent errno
479 * so the application will eventually get an error condition.
480 * Set the FTS_DONTCHDIR flag so that when we logically change
481 * directories back to the parent we don't do a chdir.
483 * If haven't read do so. If the read fails, fts_build sets
484 * FTS_STOP or the fts_info field of the node.
486 if (sp->fts_child != NULL) {
487 if (fts_safe_changedir(sp, p, -1, p->fts_accpath)) {
488 p->fts_errno = errno;
489 p->fts_flags |= FTS_DONTCHDIR;
490 for (p = sp->fts_child; p != NULL;
493 p->fts_parent->fts_accpath;
495 } else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) {
498 /* If fts_build's call to fts_safe_changedir failed
499 because it was not able to fchdir into a
500 subdirectory, tell the caller. */
502 p->fts_info = FTS_ERR;
503 /* FIXME: see if this should be in an else block */
504 LEAVE_DIR (sp, p, "2");
508 sp->fts_child = NULL;
512 /* Move to the next node on this level. */
514 if ((p = p->fts_link) != NULL) {
518 * If reached the top, return to the original directory (or
519 * the root of the tree), and load the file names for the next
522 if (p->fts_level == FTS_ROOTLEVEL) {
523 if (FCHDIR(sp, sp->fts_rfd)) {
532 * User may have called fts_set on the node. If skipped,
533 * ignore. If followed, get a file descriptor so we can
534 * get back if necessary.
536 if (p->fts_instr == FTS_SKIP)
538 if (p->fts_instr == FTS_FOLLOW) {
539 p->fts_info = fts_stat(sp, p, true);
540 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
541 if ((p->fts_symfd = diropen (".")) < 0) {
542 p->fts_errno = errno;
543 p->fts_info = FTS_ERR;
545 p->fts_flags |= FTS_SYMFOLLOW;
547 p->fts_instr = FTS_NOINSTR;
550 name: t = sp->fts_path + NAPPEND(p->fts_parent);
552 memmove(t, p->fts_name, p->fts_namelen + 1);
555 if (p->fts_info == FTS_D)
557 Dprintf ((" %s-entering: %s\n", sp, p->fts_path));
558 if (! enter_dir (sp, p))
560 __set_errno (ENOMEM);
567 /* Move up to the parent node. */
571 if (p->fts_level == FTS_ROOTPARENTLEVEL) {
573 * Done; free everything up and set errno to 0 so the user
574 * can distinguish between error and EOF.
578 return (sp->fts_cur = NULL);
581 /* NUL terminate the file name. */
582 sp->fts_path[p->fts_pathlen] = '\0';
585 * Return to the parent directory. If at a root node or came through
586 * a symlink, go back through the file descriptor. Otherwise, cd up
589 if (p->fts_level == FTS_ROOTLEVEL) {
590 if (FCHDIR(sp, sp->fts_rfd)) {
591 p->fts_errno = errno;
594 } else if (p->fts_flags & FTS_SYMFOLLOW) {
595 if (FCHDIR(sp, p->fts_symfd)) {
597 (void)close(p->fts_symfd);
598 __set_errno (saved_errno);
599 p->fts_errno = errno;
602 (void)close(p->fts_symfd);
603 } else if (!(p->fts_flags & FTS_DONTCHDIR) &&
604 fts_safe_changedir(sp, p->fts_parent, -1, "..")) {
605 p->fts_errno = errno;
608 p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;
609 if (p->fts_errno == 0)
610 LEAVE_DIR (sp, p, "3");
612 return ISSET(FTS_STOP) ? NULL : p;
616 * Fts_set takes the stream as an argument although it's not used in this
617 * implementation; it would be necessary if anyone wanted to add global
618 * semantics to fts using fts_set. An error return is allowed for similar
623 fts_set(FTS *sp ATTRIBUTE_UNUSED, FTSENT *p, int instr)
625 if (instr != 0 && instr != FTS_AGAIN && instr != FTS_FOLLOW &&
626 instr != FTS_NOINSTR && instr != FTS_SKIP) {
627 __set_errno (EINVAL);
630 p->fts_instr = instr;
635 fts_children (register FTS *sp, int instr)
640 if (instr != 0 && instr != FTS_NAMEONLY) {
641 __set_errno (EINVAL);
645 /* Set current node pointer. */
649 * Errno set to 0 so user can distinguish empty directory from
654 /* Fatal errors stop here. */
658 /* Return logical hierarchy of user's arguments. */
659 if (p->fts_info == FTS_INIT)
660 return (p->fts_link);
663 * If not a directory being visited in pre-order, stop here. Could
664 * allow FTS_DNR, assuming the user has fixed the problem, but the
665 * same effect is available with FTS_AGAIN.
667 if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */)
670 /* Free up any previous child list. */
671 if (sp->fts_child != NULL)
672 fts_lfree(sp->fts_child);
674 if (instr == FTS_NAMEONLY) {
681 * If using chdir on a relative file name and called BEFORE fts_read
682 * does its chdir to the root of a traversal, we can lose -- we need to
683 * chdir into the subdirectory, and we don't know where the current
684 * directory is, so we can't get back so that the upcoming chdir by
685 * fts_read will work.
687 if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' ||
689 return (sp->fts_child = fts_build(sp, instr));
691 if ((fd = diropen (".")) < 0)
692 return (sp->fts_child = NULL);
693 sp->fts_child = fts_build(sp, instr);
699 return (sp->fts_child);
703 * This is the tricky part -- do not casually change *anything* in here. The
704 * idea is to build the linked list of entries that are used by fts_children
705 * and fts_read. There are lots of special cases.
707 * The real slowdown in walking the tree is the stat calls. If FTS_NOSTAT is
708 * set and it's a physical walk (so that symbolic links can't be directories),
709 * we can do things quickly. First, if it's a 4.4BSD file system, the type
710 * of the file is in the directory entry. Otherwise, we assume that the number
711 * of subdirectories in a node is equal to the number of links to the parent.
712 * The former skips all stat calls. The latter skips stat calls in any leaf
713 * directories and for any files after the subdirectories in the directory have
714 * been found, cutting the stat calls by about 2/3.
718 fts_build (register FTS *sp, int type)
720 register struct dirent *dp;
721 register FTSENT *p, *head;
722 register size_t nitems;
733 size_t len, maxlen, new_len;
736 /* Set current node pointer. */
740 * Open the directory for reading. If this fails, we're done.
741 * If being called from fts_read, set the fts_info field.
743 #if defined FTS_WHITEOUT && 0
744 if (ISSET(FTS_WHITEOUT))
745 oflag = DTF_NODUP|DTF_REWIND;
747 oflag = DTF_HIDEW|DTF_NODUP|DTF_REWIND;
749 # define __opendir2(file, flag) opendir(file)
751 if ((dirp = __opendir2(cur->fts_accpath, oflag)) == NULL) {
753 cur->fts_info = FTS_DNR;
754 cur->fts_errno = errno;
760 * Nlinks is the number of possible entries of type directory in the
761 * directory if we're cheating on stat calls, 0 if we're not doing
762 * any stat calls at all, (nlink_t) -1 if we're statting everything.
764 if (type == BNAMES) {
766 /* Be quiet about nostat, GCC. */
768 } else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) {
769 nlinks = (cur->fts_statp->st_nlink
770 - (ISSET(FTS_SEEDOT) ? 0 : 2));
778 * If we're going to need to stat anything or we want to descend
779 * and stay in the directory, chdir. If this fails we keep going,
780 * but set a flag so we don't chdir after the post-order visit.
781 * We won't be able to stat anything, but we can still return the
782 * names themselves. Note, that since fts_read won't be able to
783 * chdir into the directory, it will have to return different file
784 * names than before, i.e. "a/b" instead of "b". Since the node
785 * has already been visited in pre-order, have to wait until the
786 * post-order visit to return the error. There is a special case
787 * here, if there was nothing to stat then it's not an error to
788 * not be able to stat. This is all fairly nasty. If a program
789 * needed sorted entries or stat information, they had better be
790 * checking FTS_NS on the returned nodes.
793 if (nlinks || type == BREAD) {
794 if (fts_safe_changedir(sp, cur, dirfd(dirp), NULL)) {
795 if (nlinks && type == BREAD)
796 cur->fts_errno = errno;
797 cur->fts_flags |= FTS_DONTCHDIR;
808 * Figure out the max file name length that can be stored in the
809 * current buffer -- the inner loop allocates more space as necessary.
810 * We really wouldn't have to do the maxlen calculations here, we
811 * could do them in fts_read before returning the name, but it's a
812 * lot easier here since the length is part of the dirent structure.
814 * If not changing directories set a pointer so that can just append
815 * each new component into the file name.
818 if (ISSET(FTS_NOCHDIR)) {
819 cp = sp->fts_path + len;
822 /* GCC, you're too verbose. */
826 maxlen = sp->fts_pathlen - len;
828 level = cur->fts_level + 1;
830 /* Read the directory, attaching each entry to the `link' pointer. */
832 for (head = tail = NULL, nitems = 0; dirp && (dp = readdir(dirp));) {
833 if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))
836 if ((p = fts_alloc(sp, dp->d_name, NAMLEN (dp))) == NULL)
838 if (NAMLEN (dp) >= maxlen) {/* include space for NUL */
839 oldaddr = sp->fts_path;
840 if (! fts_palloc(sp, NAMLEN (dp) + len + 1)) {
842 * No more memory. Save
843 * errno, free up the current structure and the
844 * structures already allocated.
846 mem1: saved_errno = errno;
851 cur->fts_info = FTS_ERR;
853 __set_errno (saved_errno);
856 /* Did realloc() change the pointer? */
857 if (oldaddr != sp->fts_path) {
859 if (ISSET(FTS_NOCHDIR))
860 cp = sp->fts_path + len;
862 maxlen = sp->fts_pathlen - len;
865 new_len = len + NAMLEN (dp);
868 * In the unlikely even that we would end up
869 * with a file name longer than SIZE_MAX, free up
870 * the current structure and the structures already
871 * allocated, then error out with ENAMETOOLONG.
876 cur->fts_info = FTS_ERR;
878 __set_errno (ENAMETOOLONG);
881 p->fts_level = level;
882 p->fts_parent = sp->fts_cur;
883 p->fts_pathlen = new_len;
885 #if defined FTS_WHITEOUT && 0
886 if (dp->d_type == DT_WHT)
887 p->fts_flags |= FTS_ISW;
892 p->fts_info = FTS_NS;
893 p->fts_errno = cderrno;
895 p->fts_info = FTS_NSOK;
896 p->fts_accpath = cur->fts_accpath;
897 } else if (nlinks == 0
898 #if HAVE_STRUCT_DIRENT_D_TYPE
900 dp->d_type != DT_DIR && dp->d_type != DT_UNKNOWN)
904 ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name;
905 p->fts_info = FTS_NSOK;
907 /* Build a file name for fts_stat to stat. */
908 if (ISSET(FTS_NOCHDIR)) {
909 p->fts_accpath = p->fts_path;
910 memmove(cp, p->fts_name, p->fts_namelen + 1);
912 p->fts_accpath = p->fts_name;
914 p->fts_info = fts_stat(sp, p, false);
916 /* Decrement link count if applicable. */
917 if (nlinks > 0 && (p->fts_info == FTS_D ||
918 p->fts_info == FTS_DC || p->fts_info == FTS_DOT))
922 /* We walk in directory order so "ls -f" doesn't get upset. */
936 * If realloc() changed the address of the file name, adjust the
937 * addresses for the rest of the tree and the dir list.
940 fts_padjust(sp, head);
943 * If not changing directories, reset the file name back to original
946 if (ISSET(FTS_NOCHDIR)) {
947 if (len == sp->fts_pathlen || nitems == 0)
953 * If descended after called from fts_children or after called from
954 * fts_read and nothing found, get back. At the root level we use
955 * the saved fd; if one of fts_open()'s arguments is a relative name
956 * to an empty directory, we wind up here with no other way back. If
957 * can't get back, we're done.
959 if (descend && (type == BCHILD || !nitems) &&
960 (cur->fts_level == FTS_ROOTLEVEL ?
961 FCHDIR(sp, sp->fts_rfd) :
962 fts_safe_changedir(sp, cur->fts_parent, -1, ".."))) {
963 cur->fts_info = FTS_ERR;
968 /* If didn't find anything, return NULL. */
971 cur->fts_info = FTS_DP;
975 /* Sort the entries. */
976 if (sp->fts_compar && nitems > 1)
977 head = fts_sort(sp, head, nitems);
983 /* Walk ->fts_parent links starting at E_CURR, until the root of the
984 current hierarchy. There should be a directory with dev/inode
985 matching those of AD. If not, print a lot of diagnostics. */
987 find_matching_ancestor (FTSENT const *e_curr, struct Active_dir const *ad)
990 for (ent = e_curr; ent->fts_level >= FTS_ROOTLEVEL; ent = ent->fts_parent)
992 if (ad->ino == ent->fts_statp->st_ino
993 && ad->dev == ent->fts_statp->st_dev)
996 printf ("ERROR: tree dir, %s, not active\n", ad->fts_ent->fts_accpath);
997 printf ("active dirs:\n");
999 ent->fts_level >= FTS_ROOTLEVEL; ent = ent->fts_parent)
1000 printf (" %s(%"PRIuMAX"/%"PRIuMAX") to %s(%"PRIuMAX"/%"PRIuMAX")...\n",
1001 ad->fts_ent->fts_accpath,
1002 (uintmax_t) ad->dev,
1003 (uintmax_t) ad->ino,
1005 (uintmax_t) ent->fts_statp->st_dev,
1006 (uintmax_t) ent->fts_statp->st_ino);
1010 fts_cross_check (FTS const *sp)
1012 FTSENT const *ent = sp->fts_cur;
1014 if ( ! ISSET (FTS_TIGHT_CYCLE_CHECK))
1017 Dprintf (("fts-cross-check cur=%s\n", ent->fts_path));
1018 /* Make sure every parent dir is in the tree. */
1019 for (t = ent->fts_parent; t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
1021 struct Active_dir ad;
1022 ad.ino = t->fts_statp->st_ino;
1023 ad.dev = t->fts_statp->st_dev;
1024 if ( ! hash_lookup (sp->fts_cycle.ht, &ad))
1025 printf ("ERROR: active dir, %s, not in tree\n", t->fts_path);
1028 /* Make sure every dir in the tree is an active dir.
1029 But ENT is not necessarily a directory. If so, just skip this part. */
1030 if (ent->fts_parent->fts_level >= FTS_ROOTLEVEL
1031 && (ent->fts_info == FTS_DP
1032 || ent->fts_info == FTS_D))
1034 struct Active_dir *ad;
1035 for (ad = hash_get_first (sp->fts_cycle.ht); ad != NULL;
1036 ad = hash_get_next (sp->fts_cycle.ht, ad))
1038 find_matching_ancestor (ent, ad);
1044 static unsigned short int
1046 fts_stat(FTS *sp, register FTSENT *p, bool follow)
1048 struct stat *sbp = p->fts_statp;
1051 #if defined FTS_WHITEOUT && 0
1052 /* check for whiteout */
1053 if (p->fts_flags & FTS_ISW) {
1054 memset(sbp, '\0', sizeof (*sbp));
1055 sbp->st_mode = S_IFWHT;
1061 * If doing a logical walk, or application requested FTS_FOLLOW, do
1062 * a stat(2). If that fails, check for a non-existent symlink. If
1063 * fail, set the errno from the stat call.
1065 if (ISSET(FTS_LOGICAL) || follow) {
1066 if (stat(p->fts_accpath, sbp)) {
1067 saved_errno = errno;
1068 if (!lstat(p->fts_accpath, sbp)) {
1070 return (FTS_SLNONE);
1072 p->fts_errno = saved_errno;
1075 } else if (lstat(p->fts_accpath, sbp)) {
1076 p->fts_errno = errno;
1077 err: memset(sbp, 0, sizeof(struct stat));
1081 if (S_ISDIR(sbp->st_mode)) {
1082 if (ISDOT(p->fts_name))
1088 * Cycle detection is done by brute force when the directory
1089 * is first encountered. If the tree gets deep enough or the
1090 * number of symbolic links to directories is high enough,
1091 * something faster might be worthwhile.
1095 for (t = p->fts_parent;
1096 t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
1097 if (sbp->st_ino == t->fts_statp->st_ino
1098 && sbp->st_dev == t->fts_statp->st_dev)
1108 if (S_ISLNK(sbp->st_mode))
1110 if (S_ISREG(sbp->st_mode))
1112 return (FTS_DEFAULT);
1116 fts_compar (void const *a, void const *b)
1118 /* Convert A and B to the correct types, to pacify the compiler, and
1119 for portability to bizarre hosts where "void const *" and "FTSENT
1120 const **" differ in runtime representation. The comparison
1121 function cannot modify *a and *b, but there is no compile-time
1123 FTSENT const **pa = (FTSENT const **) a;
1124 FTSENT const **pb = (FTSENT const **) b;
1125 return pa[0]->fts_fts->fts_compar (pa, pb);
1130 fts_sort (FTS *sp, FTSENT *head, register size_t nitems)
1132 register FTSENT **ap, *p;
1134 /* On most modern hosts, void * and FTSENT ** have the same
1135 run-time representation, and one can convert sp->fts_compar to
1136 the type qsort expects without problem. Use the heuristic that
1137 this is OK if the two pointer types are the same size, and if
1138 converting FTSENT ** to long int is the same as converting
1139 FTSENT ** to void * and then to long int. This heuristic isn't
1140 valid in general but we don't know of any counterexamples. */
1142 int (*compare) (void const *, void const *) =
1143 ((sizeof &dummy == sizeof (void *)
1144 && (long int) &dummy == (long int) (void *) &dummy)
1145 ? (int (*) (void const *, void const *)) sp->fts_compar
1149 * Construct an array of pointers to the structures and call qsort(3).
1150 * Reassemble the array in the order returned by qsort. If unable to
1151 * sort for memory reasons, return the directory entries in their
1152 * current order. Allocate enough space for the current needs plus
1153 * 40 so don't realloc one entry at a time.
1155 if (nitems > sp->fts_nitems) {
1158 sp->fts_nitems = nitems + 40;
1159 if (SIZE_MAX / sizeof *a < sp->fts_nitems
1160 || ! (a = realloc (sp->fts_array,
1161 sp->fts_nitems * sizeof *a))) {
1162 free(sp->fts_array);
1163 sp->fts_array = NULL;
1169 for (ap = sp->fts_array, p = head; p; p = p->fts_link)
1171 qsort((void *)sp->fts_array, nitems, sizeof(FTSENT *), compare);
1172 for (head = *(ap = sp->fts_array); --nitems; ++ap)
1173 ap[0]->fts_link = ap[1];
1174 ap[0]->fts_link = NULL;
1180 fts_alloc (FTS *sp, const char *name, register size_t namelen)
1186 * The file name is a variable length array. Allocate the FTSENT
1187 * structure and the file name in one chunk.
1189 len = sizeof(FTSENT) + namelen;
1190 if ((p = malloc(len)) == NULL)
1193 /* Copy the name and guarantee NUL termination. */
1194 memmove(p->fts_name, name, namelen);
1195 p->fts_name[namelen] = '\0';
1197 p->fts_namelen = namelen;
1199 p->fts_path = sp->fts_path;
1202 p->fts_instr = FTS_NOINSTR;
1204 p->fts_pointer = NULL;
1210 fts_lfree (register FTSENT *head)
1214 /* Free a linked list of structures. */
1215 while ((p = head)) {
1216 head = head->fts_link;
1222 * Allow essentially unlimited file name lengths; find, rm, ls should
1223 * all work on any tree. Most systems will allow creation of file
1224 * names much longer than MAXPATHLEN, even though the kernel won't
1225 * resolve them. Add the size (not just what's needed) plus 256 bytes
1226 * so don't realloc the file name 2 bytes at a time.
1230 fts_palloc (FTS *sp, size_t more)
1233 size_t new_len = sp->fts_pathlen + more + 256;
1236 * See if fts_pathlen would overflow.
1238 if (new_len < sp->fts_pathlen) {
1241 sp->fts_path = NULL;
1243 sp->fts_path = NULL;
1244 __set_errno (ENAMETOOLONG);
1247 sp->fts_pathlen = new_len;
1248 p = realloc(sp->fts_path, sp->fts_pathlen);
1251 sp->fts_path = NULL;
1259 * When the file name is realloc'd, have to fix all of the pointers in
1260 * structures already returned.
1264 fts_padjust (FTS *sp, FTSENT *head)
1267 char *addr = sp->fts_path;
1269 #define ADJUST(p) do { \
1270 if ((p)->fts_accpath != (p)->fts_name) { \
1271 (p)->fts_accpath = \
1272 (char *)addr + ((p)->fts_accpath - (p)->fts_path); \
1274 (p)->fts_path = addr; \
1276 /* Adjust the current set of children. */
1277 for (p = sp->fts_child; p; p = p->fts_link)
1280 /* Adjust the rest of the tree, including the current level. */
1281 for (p = head; p->fts_level >= FTS_ROOTLEVEL;) {
1283 p = p->fts_link ? p->fts_link : p->fts_parent;
1289 fts_maxarglen (char * const *argv)
1293 for (max = 0; *argv; ++argv)
1294 if ((len = strlen(*argv)) > max)
1300 * Change to dir specified by fd or file name without getting
1301 * tricked by someone changing the world out from underneath us.
1302 * Assumes p->fts_statp->st_dev and p->fts_statp->st_ino are filled in.
1306 fts_safe_changedir (FTS *sp, FTSENT *p, int fd, char const *dir)
1308 int ret, oerrno, newfd;
1312 if (ISSET(FTS_NOCHDIR))
1314 if (fd < 0 && (newfd = diropen (dir)) < 0)
1316 if (fstat(newfd, &sb)) {
1320 if (p->fts_statp->st_dev != sb.st_dev
1321 || p->fts_statp->st_ino != sb.st_ino) {
1322 __set_errno (ENOENT); /* disinformation */
1326 ret = fchdir(newfd);
1331 __set_errno (oerrno);