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>
79 #ifndef _D_EXACT_NAMLEN
80 # define _D_EXACT_NAMLEN(dirent) strlen ((dirent)->d_name)
85 # define close __close
87 # define closedir __closedir
89 # define fchdir __fchdir
93 # define opendir __opendir
95 # define readdir __readdir
97 # undef internal_function
98 # define internal_function /* empty */
102 # define __set_errno(Val) errno = (Val)
105 #ifndef __attribute__
106 # if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 8) || __STRICT_ANSI__
107 # define __attribute__(x) /* empty */
111 #ifndef ATTRIBUTE_UNUSED
112 # define ATTRIBUTE_UNUSED __attribute__ ((__unused__))
116 static FTSENT *fts_alloc (FTS *, const char *, size_t) internal_function;
117 static FTSENT *fts_build (FTS *, int) internal_function;
118 static void fts_lfree (FTSENT *) internal_function;
119 static void fts_load (FTS *, FTSENT *) internal_function;
120 static size_t fts_maxarglen (char * const *) internal_function;
121 static void fts_padjust (FTS *, FTSENT *) internal_function;
122 static bool fts_palloc (FTS *, size_t) internal_function;
123 static FTSENT *fts_sort (FTS *, FTSENT *, size_t) internal_function;
124 static unsigned short int fts_stat (FTS *, FTSENT *, bool) internal_function;
125 static int fts_safe_changedir (FTS *, FTSENT *, int, const char *)
129 static bool enter_dir (FTS *fts, FTSENT *ent) { return true; }
130 static void leave_dir (FTS *fts, FTSENT *ent) {}
131 static bool setup_dir (FTS *fts) { return true; }
132 static void free_dir (FTS *fts) {}
134 # include "fcntl--.h"
135 # include "fts-cycle.c"
139 # define MAX(a,b) ((a) > (b) ? (a) : (b))
143 # define SIZE_MAX ((size_t) -1)
147 # define O_DIRECTORY 0
150 #define ISDOT(a) (a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2])))
152 #define CLR(opt) (sp->fts_options &= ~(opt))
153 #define ISSET(opt) (sp->fts_options & (opt))
154 #define SET(opt) (sp->fts_options |= (opt))
156 #define FCHDIR(sp, fd) (!ISSET(FTS_NOCHDIR) && fchdir(fd))
158 /* fts_build flags */
159 #define BCHILD 1 /* fts_children */
160 #define BNAMES 2 /* fts_children, names only */
161 #define BREAD 3 /* fts_read */
164 # include <inttypes.h>
167 bool fts_debug = false;
168 # define Dprintf(x) do { if (fts_debug) printf x; } while (0)
173 #define LEAVE_DIR(Fts, Ent, Tag) \
176 Dprintf ((" %s-leaving: %s\n", Tag, (Ent)->fts_path)); \
177 leave_dir (Fts, Ent); \
181 /* Open the directory DIR if possible, and return a file
182 descriptor. Return -1 and set errno on failure. It doesn't matter
183 whether the file descriptor has read or write access. */
187 diropen (char const *dir)
189 return open (dir, O_RDONLY | O_DIRECTORY | O_NOCTTY | O_NONBLOCK);
193 fts_open (char * const *argv,
194 register int options,
195 int (*compar) (FTSENT const **, FTSENT const **))
198 register FTSENT *p, *root;
199 register size_t nitems;
200 FTSENT *parent, *tmp = NULL; /* pacify gcc */
204 if (options & ~FTS_OPTIONMASK) {
205 __set_errno (EINVAL);
209 /* Allocate/initialize the stream */
210 if ((sp = malloc(sizeof(FTS))) == NULL)
212 memset(sp, 0, sizeof(FTS));
213 sp->fts_compar = compar;
214 sp->fts_options = options;
216 /* Logical walks turn on NOCHDIR; symbolic links are too hard. */
217 if (ISSET(FTS_LOGICAL))
221 * Start out with 1K of file name space, and enough, in any case,
222 * to hold the user's file names.
225 # define MAXPATHLEN 1024
228 size_t maxarglen = fts_maxarglen(argv);
229 if (! fts_palloc(sp, MAX(maxarglen, MAXPATHLEN)))
233 /* Allocate/initialize root's parent. */
234 if ((parent = fts_alloc(sp, "", 0)) == NULL)
236 parent->fts_level = FTS_ROOTPARENTLEVEL;
238 /* Allocate/initialize root(s). */
239 for (root = NULL, nitems = 0; *argv != NULL; ++argv, ++nitems) {
240 /* Don't allow zero-length file names. */
241 if ((len = strlen(*argv)) == 0) {
242 __set_errno (ENOENT);
246 if ((p = fts_alloc(sp, *argv, len)) == NULL)
248 p->fts_level = FTS_ROOTLEVEL;
249 p->fts_parent = parent;
250 p->fts_accpath = p->fts_name;
251 p->fts_info = fts_stat(sp, p, ISSET(FTS_COMFOLLOW) != 0);
253 /* Command-line "." and ".." are real directories. */
254 if (p->fts_info == FTS_DOT)
258 * If comparison routine supplied, traverse in sorted
259 * order; otherwise traverse in the order specified.
274 if (compar && nitems > 1)
275 root = fts_sort(sp, root, nitems);
278 * Allocate a dummy pointer and make fts_read think that we've just
279 * finished the node before the root(s); set p->fts_info to FTS_INIT
280 * so that everything about the "current" node is ignored.
282 if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL)
284 sp->fts_cur->fts_link = root;
285 sp->fts_cur->fts_info = FTS_INIT;
286 if (! setup_dir (sp))
290 * If using chdir(2), grab a file descriptor pointing to dot to ensure
291 * that we can get back here; this could be avoided for some file names,
292 * but almost certainly not worth the effort. Slashes, symbolic links,
293 * and ".." are all fairly nasty problems. Note, if we can't get the
294 * descriptor we run anyway, just more slowly.
296 if (!ISSET(FTS_NOCHDIR)
297 && (sp->fts_rfd = diropen (".")) < 0)
302 mem3: fts_lfree(root);
304 mem2: free(sp->fts_path);
311 fts_load (FTS *sp, register FTSENT *p)
317 * Load the stream structure for the next traversal. Since we don't
318 * actually enter the directory until after the preorder visit, set
319 * the fts_accpath field specially so the chdir gets done to the right
320 * place and the user can access the first node. From fts_open it's
321 * known that the file name will fit.
323 len = p->fts_pathlen = p->fts_namelen;
324 memmove(sp->fts_path, p->fts_name, len + 1);
325 if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) {
327 memmove(p->fts_name, cp, len + 1);
328 p->fts_namelen = len;
330 p->fts_accpath = p->fts_path = sp->fts_path;
331 sp->fts_dev = p->fts_statp->st_dev;
337 register FTSENT *freep, *p;
341 * This still works if we haven't read anything -- the dummy structure
342 * points to the root list, so we step through to the end of the root
343 * list which has a valid parent pointer.
346 for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {
348 p = p->fts_link != NULL ? p->fts_link : p->fts_parent;
354 /* Free up child linked list, sort array, file name buffer. */
356 fts_lfree(sp->fts_child);
361 /* Return to original directory, save errno if necessary. */
362 if (!ISSET(FTS_NOCHDIR)) {
363 if (fchdir(sp->fts_rfd))
365 (void)close(sp->fts_rfd);
370 /* Free up the stream pointer. */
373 /* Set errno and return. */
375 __set_errno (saved_errno);
383 * Special case of "/" at the end of the file name so that slashes aren't
384 * appended which would cause file names to be written as "....//foo".
387 (p->fts_path[p->fts_pathlen - 1] == '/' \
388 ? p->fts_pathlen - 1 : p->fts_pathlen)
391 fts_read (register FTS *sp)
393 register FTSENT *p, *tmp;
394 register unsigned short int instr;
398 /* If finished or unrecoverable error, return NULL. */
399 if (sp->fts_cur == NULL || ISSET(FTS_STOP))
402 /* Set current node pointer. */
405 /* Save and zero out user instructions. */
406 instr = p->fts_instr;
407 p->fts_instr = FTS_NOINSTR;
409 /* Any type of file may be re-visited; re-stat and re-turn. */
410 if (instr == FTS_AGAIN) {
411 p->fts_info = fts_stat(sp, p, false);
414 Dprintf (("fts_read: p=%s\n",
415 p->fts_info == FTS_INIT ? "" : p->fts_path));
418 * Following a symlink -- SLNONE test allows application to see
419 * SLNONE and recover. If indirecting through a symlink, have
420 * keep a pointer to current location. If unable to get that
421 * pointer, follow fails.
423 if (instr == FTS_FOLLOW &&
424 (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) {
425 p->fts_info = fts_stat(sp, p, true);
426 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
427 if ((p->fts_symfd = diropen (".")) < 0) {
428 p->fts_errno = errno;
429 p->fts_info = FTS_ERR;
431 p->fts_flags |= FTS_SYMFOLLOW;
436 /* Directory in pre-order. */
437 if (p->fts_info == FTS_D) {
438 /* If skipped or crossed mount point, do post-order visit. */
439 if (instr == FTS_SKIP ||
440 (ISSET(FTS_XDEV) && p->fts_statp->st_dev != sp->fts_dev)) {
441 if (p->fts_flags & FTS_SYMFOLLOW)
442 (void)close(p->fts_symfd);
444 fts_lfree(sp->fts_child);
445 sp->fts_child = NULL;
447 p->fts_info = FTS_DP;
448 LEAVE_DIR (sp, p, "1");
452 /* Rebuild if only read the names and now traversing. */
453 if (sp->fts_child != NULL && ISSET(FTS_NAMEONLY)) {
455 fts_lfree(sp->fts_child);
456 sp->fts_child = NULL;
460 * Cd to the subdirectory.
462 * If have already read and now fail to chdir, whack the list
463 * to make the names come out right, and set the parent errno
464 * so the application will eventually get an error condition.
465 * Set the FTS_DONTCHDIR flag so that when we logically change
466 * directories back to the parent we don't do a chdir.
468 * If haven't read do so. If the read fails, fts_build sets
469 * FTS_STOP or the fts_info field of the node.
471 if (sp->fts_child != NULL) {
472 if (fts_safe_changedir(sp, p, -1, p->fts_accpath)) {
473 p->fts_errno = errno;
474 p->fts_flags |= FTS_DONTCHDIR;
475 for (p = sp->fts_child; p != NULL;
478 p->fts_parent->fts_accpath;
480 } else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) {
483 /* If fts_build's call to fts_safe_changedir failed
484 because it was not able to fchdir into a
485 subdirectory, tell the caller. */
487 p->fts_info = FTS_ERR;
488 /* FIXME: see if this should be in an else block */
489 LEAVE_DIR (sp, p, "2");
493 sp->fts_child = NULL;
497 /* Move to the next node on this level. */
499 if ((p = p->fts_link) != NULL) {
503 * If reached the top, return to the original directory (or
504 * the root of the tree), and load the file names for the next
507 if (p->fts_level == FTS_ROOTLEVEL) {
508 if (FCHDIR(sp, sp->fts_rfd)) {
518 * User may have called fts_set on the node. If skipped,
519 * ignore. If followed, get a file descriptor so we can
520 * get back if necessary.
522 if (p->fts_instr == FTS_SKIP)
524 if (p->fts_instr == FTS_FOLLOW) {
525 p->fts_info = fts_stat(sp, p, true);
526 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
527 if ((p->fts_symfd = diropen (".")) < 0) {
528 p->fts_errno = errno;
529 p->fts_info = FTS_ERR;
531 p->fts_flags |= FTS_SYMFOLLOW;
533 p->fts_instr = FTS_NOINSTR;
536 name: t = sp->fts_path + NAPPEND(p->fts_parent);
538 memmove(t, p->fts_name, p->fts_namelen + 1);
541 if (p->fts_info == FTS_D)
543 Dprintf ((" %s-entering: %s\n", sp, p->fts_path));
544 if (! enter_dir (sp, p))
546 __set_errno (ENOMEM);
553 /* Move up to the parent node. */
557 if (p->fts_level == FTS_ROOTPARENTLEVEL) {
559 * Done; free everything up and set errno to 0 so the user
560 * can distinguish between error and EOF.
564 return (sp->fts_cur = NULL);
567 /* NUL terminate the file name. */
568 sp->fts_path[p->fts_pathlen] = '\0';
571 * Return to the parent directory. If at a root node or came through
572 * a symlink, go back through the file descriptor. Otherwise, cd up
575 if (p->fts_level == FTS_ROOTLEVEL) {
576 if (FCHDIR(sp, sp->fts_rfd)) {
577 p->fts_errno = errno;
580 } else if (p->fts_flags & FTS_SYMFOLLOW) {
581 if (FCHDIR(sp, p->fts_symfd)) {
583 (void)close(p->fts_symfd);
584 __set_errno (saved_errno);
585 p->fts_errno = errno;
588 (void)close(p->fts_symfd);
589 } else if (!(p->fts_flags & FTS_DONTCHDIR) &&
590 fts_safe_changedir(sp, p->fts_parent, -1, "..")) {
591 p->fts_errno = errno;
594 p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;
595 if (p->fts_errno == 0)
596 LEAVE_DIR (sp, p, "3");
598 return ISSET(FTS_STOP) ? NULL : p;
602 * Fts_set takes the stream as an argument although it's not used in this
603 * implementation; it would be necessary if anyone wanted to add global
604 * semantics to fts using fts_set. An error return is allowed for similar
609 fts_set(FTS *sp ATTRIBUTE_UNUSED, FTSENT *p, int instr)
611 if (instr != 0 && instr != FTS_AGAIN && instr != FTS_FOLLOW &&
612 instr != FTS_NOINSTR && instr != FTS_SKIP) {
613 __set_errno (EINVAL);
616 p->fts_instr = instr;
621 fts_children (register FTS *sp, int instr)
626 if (instr != 0 && instr != FTS_NAMEONLY) {
627 __set_errno (EINVAL);
631 /* Set current node pointer. */
635 * Errno set to 0 so user can distinguish empty directory from
640 /* Fatal errors stop here. */
644 /* Return logical hierarchy of user's arguments. */
645 if (p->fts_info == FTS_INIT)
646 return (p->fts_link);
649 * If not a directory being visited in pre-order, stop here. Could
650 * allow FTS_DNR, assuming the user has fixed the problem, but the
651 * same effect is available with FTS_AGAIN.
653 if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */)
656 /* Free up any previous child list. */
657 if (sp->fts_child != NULL)
658 fts_lfree(sp->fts_child);
660 if (instr == FTS_NAMEONLY) {
667 * If using chdir on a relative file name and called BEFORE fts_read
668 * does its chdir to the root of a traversal, we can lose -- we need to
669 * chdir into the subdirectory, and we don't know where the current
670 * directory is, so we can't get back so that the upcoming chdir by
671 * fts_read will work.
673 if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' ||
675 return (sp->fts_child = fts_build(sp, instr));
677 if ((fd = diropen (".")) < 0)
678 return (sp->fts_child = NULL);
679 sp->fts_child = fts_build(sp, instr);
681 int saved_errno = errno;
683 __set_errno (saved_errno);
687 return (sp->fts_child);
691 * This is the tricky part -- do not casually change *anything* in here. The
692 * idea is to build the linked list of entries that are used by fts_children
693 * and fts_read. There are lots of special cases.
695 * The real slowdown in walking the tree is the stat calls. If FTS_NOSTAT is
696 * set and it's a physical walk (so that symbolic links can't be directories),
697 * we can do things quickly. First, if it's a 4.4BSD file system, the type
698 * of the file is in the directory entry. Otherwise, we assume that the number
699 * of subdirectories in a node is equal to the number of links to the parent.
700 * The former skips all stat calls. The latter skips stat calls in any leaf
701 * directories and for any files after the subdirectories in the directory have
702 * been found, cutting the stat calls by about 2/3.
706 fts_build (register FTS *sp, int type)
708 register struct dirent *dp;
709 register FTSENT *p, *head;
710 register size_t nitems;
721 size_t len, maxlen, new_len;
724 /* Set current node pointer. */
728 * Open the directory for reading. If this fails, we're done.
729 * If being called from fts_read, set the fts_info field.
731 #if defined FTS_WHITEOUT && 0
732 if (ISSET(FTS_WHITEOUT))
733 oflag = DTF_NODUP|DTF_REWIND;
735 oflag = DTF_HIDEW|DTF_NODUP|DTF_REWIND;
737 # define __opendir2(file, flag) opendir(file)
739 if ((dirp = __opendir2(cur->fts_accpath, oflag)) == NULL) {
741 cur->fts_info = FTS_DNR;
742 cur->fts_errno = errno;
748 * Nlinks is the number of possible entries of type directory in the
749 * directory if we're cheating on stat calls, 0 if we're not doing
750 * any stat calls at all, (nlink_t) -1 if we're statting everything.
752 if (type == BNAMES) {
754 /* Be quiet about nostat, GCC. */
756 } else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) {
757 nlinks = (cur->fts_statp->st_nlink
758 - (ISSET(FTS_SEEDOT) ? 0 : 2));
766 * If we're going to need to stat anything or we want to descend
767 * and stay in the directory, chdir. If this fails we keep going,
768 * but set a flag so we don't chdir after the post-order visit.
769 * We won't be able to stat anything, but we can still return the
770 * names themselves. Note, that since fts_read won't be able to
771 * chdir into the directory, it will have to return different file
772 * names than before, i.e. "a/b" instead of "b". Since the node
773 * has already been visited in pre-order, have to wait until the
774 * post-order visit to return the error. There is a special case
775 * here, if there was nothing to stat then it's not an error to
776 * not be able to stat. This is all fairly nasty. If a program
777 * needed sorted entries or stat information, they had better be
778 * checking FTS_NS on the returned nodes.
781 if (nlinks || type == BREAD) {
782 if (fts_safe_changedir(sp, cur, dirfd(dirp), NULL)) {
783 if (nlinks && type == BREAD)
784 cur->fts_errno = errno;
785 cur->fts_flags |= FTS_DONTCHDIR;
796 * Figure out the max file name length that can be stored in the
797 * current buffer -- the inner loop allocates more space as necessary.
798 * We really wouldn't have to do the maxlen calculations here, we
799 * could do them in fts_read before returning the name, but it's a
800 * lot easier here since the length is part of the dirent structure.
802 * If not changing directories set a pointer so that can just append
803 * each new component into the file name.
806 if (ISSET(FTS_NOCHDIR)) {
807 cp = sp->fts_path + len;
810 /* GCC, you're too verbose. */
814 maxlen = sp->fts_pathlen - len;
816 level = cur->fts_level + 1;
818 /* Read the directory, attaching each entry to the `link' pointer. */
820 for (head = tail = NULL, nitems = 0; dirp && (dp = readdir(dirp));) {
821 if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))
824 if ((p = fts_alloc (sp, dp->d_name,
825 _D_EXACT_NAMLEN (dp))) == NULL)
827 if (_D_EXACT_NAMLEN (dp) >= maxlen) {
828 /* include space for NUL */
829 oldaddr = sp->fts_path;
830 if (! fts_palloc(sp, _D_EXACT_NAMLEN (dp) + len + 1)) {
832 * No more memory. Save
833 * errno, free up the current structure and the
834 * structures already allocated.
836 mem1: saved_errno = errno;
841 cur->fts_info = FTS_ERR;
843 __set_errno (saved_errno);
846 /* Did realloc() change the pointer? */
847 if (oldaddr != sp->fts_path) {
849 if (ISSET(FTS_NOCHDIR))
850 cp = sp->fts_path + len;
852 maxlen = sp->fts_pathlen - len;
855 new_len = len + _D_EXACT_NAMLEN (dp);
858 * In the unlikely even that we would end up
859 * with a file name longer than SIZE_MAX, free up
860 * the current structure and the structures already
861 * allocated, then error out with ENAMETOOLONG.
866 cur->fts_info = FTS_ERR;
868 __set_errno (ENAMETOOLONG);
871 p->fts_level = level;
872 p->fts_parent = sp->fts_cur;
873 p->fts_pathlen = new_len;
875 #if defined FTS_WHITEOUT && 0
876 if (dp->d_type == DT_WHT)
877 p->fts_flags |= FTS_ISW;
882 p->fts_info = FTS_NS;
883 p->fts_errno = cderrno;
885 p->fts_info = FTS_NSOK;
886 p->fts_accpath = cur->fts_accpath;
887 } else if (nlinks == 0
888 #if HAVE_STRUCT_DIRENT_D_TYPE
890 dp->d_type != DT_DIR && dp->d_type != DT_UNKNOWN)
894 ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name;
895 p->fts_info = FTS_NSOK;
897 /* Build a file name for fts_stat to stat. */
898 if (ISSET(FTS_NOCHDIR)) {
899 p->fts_accpath = p->fts_path;
900 memmove(cp, p->fts_name, p->fts_namelen + 1);
902 p->fts_accpath = p->fts_name;
904 p->fts_info = fts_stat(sp, p, false);
906 /* Decrement link count if applicable. */
907 if (nlinks > 0 && (p->fts_info == FTS_D ||
908 p->fts_info == FTS_DC || p->fts_info == FTS_DOT))
912 /* We walk in directory order so "ls -f" doesn't get upset. */
926 * If realloc() changed the address of the file name, adjust the
927 * addresses for the rest of the tree and the dir list.
930 fts_padjust(sp, head);
933 * If not changing directories, reset the file name back to original
936 if (ISSET(FTS_NOCHDIR)) {
937 if (len == sp->fts_pathlen || nitems == 0)
943 * If descended after called from fts_children or after called from
944 * fts_read and nothing found, get back. At the root level we use
945 * the saved fd; if one of fts_open()'s arguments is a relative name
946 * to an empty directory, we wind up here with no other way back. If
947 * can't get back, we're done.
949 if (descend && (type == BCHILD || !nitems) &&
950 (cur->fts_level == FTS_ROOTLEVEL ?
951 FCHDIR(sp, sp->fts_rfd) :
952 fts_safe_changedir(sp, cur->fts_parent, -1, ".."))) {
953 cur->fts_info = FTS_ERR;
958 /* If didn't find anything, return NULL. */
961 cur->fts_info = FTS_DP;
965 /* Sort the entries. */
966 if (sp->fts_compar && nitems > 1)
967 head = fts_sort(sp, head, nitems);
973 /* Walk ->fts_parent links starting at E_CURR, until the root of the
974 current hierarchy. There should be a directory with dev/inode
975 matching those of AD. If not, print a lot of diagnostics. */
977 find_matching_ancestor (FTSENT const *e_curr, struct Active_dir const *ad)
980 for (ent = e_curr; ent->fts_level >= FTS_ROOTLEVEL; ent = ent->fts_parent)
982 if (ad->ino == ent->fts_statp->st_ino
983 && ad->dev == ent->fts_statp->st_dev)
986 printf ("ERROR: tree dir, %s, not active\n", ad->fts_ent->fts_accpath);
987 printf ("active dirs:\n");
989 ent->fts_level >= FTS_ROOTLEVEL; ent = ent->fts_parent)
990 printf (" %s(%"PRIuMAX"/%"PRIuMAX") to %s(%"PRIuMAX"/%"PRIuMAX")...\n",
991 ad->fts_ent->fts_accpath,
995 (uintmax_t) ent->fts_statp->st_dev,
996 (uintmax_t) ent->fts_statp->st_ino);
1000 fts_cross_check (FTS const *sp)
1002 FTSENT const *ent = sp->fts_cur;
1004 if ( ! ISSET (FTS_TIGHT_CYCLE_CHECK))
1007 Dprintf (("fts-cross-check cur=%s\n", ent->fts_path));
1008 /* Make sure every parent dir is in the tree. */
1009 for (t = ent->fts_parent; t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
1011 struct Active_dir ad;
1012 ad.ino = t->fts_statp->st_ino;
1013 ad.dev = t->fts_statp->st_dev;
1014 if ( ! hash_lookup (sp->fts_cycle.ht, &ad))
1015 printf ("ERROR: active dir, %s, not in tree\n", t->fts_path);
1018 /* Make sure every dir in the tree is an active dir.
1019 But ENT is not necessarily a directory. If so, just skip this part. */
1020 if (ent->fts_parent->fts_level >= FTS_ROOTLEVEL
1021 && (ent->fts_info == FTS_DP
1022 || ent->fts_info == FTS_D))
1024 struct Active_dir *ad;
1025 for (ad = hash_get_first (sp->fts_cycle.ht); ad != NULL;
1026 ad = hash_get_next (sp->fts_cycle.ht, ad))
1028 find_matching_ancestor (ent, ad);
1034 static unsigned short int
1036 fts_stat(FTS *sp, register FTSENT *p, bool follow)
1038 struct stat *sbp = p->fts_statp;
1041 #if defined FTS_WHITEOUT && 0
1042 /* check for whiteout */
1043 if (p->fts_flags & FTS_ISW) {
1044 memset(sbp, '\0', sizeof (*sbp));
1045 sbp->st_mode = S_IFWHT;
1051 * If doing a logical walk, or application requested FTS_FOLLOW, do
1052 * a stat(2). If that fails, check for a non-existent symlink. If
1053 * fail, set the errno from the stat call.
1055 if (ISSET(FTS_LOGICAL) || follow) {
1056 if (stat(p->fts_accpath, sbp)) {
1057 saved_errno = errno;
1059 && lstat(p->fts_accpath, sbp) == 0) {
1061 return (FTS_SLNONE);
1063 p->fts_errno = saved_errno;
1066 } else if (lstat(p->fts_accpath, sbp)) {
1067 p->fts_errno = errno;
1068 err: memset(sbp, 0, sizeof(struct stat));
1072 if (S_ISDIR(sbp->st_mode)) {
1073 if (ISDOT(p->fts_name))
1079 * Cycle detection is done by brute force when the directory
1080 * is first encountered. If the tree gets deep enough or the
1081 * number of symbolic links to directories is high enough,
1082 * something faster might be worthwhile.
1086 for (t = p->fts_parent;
1087 t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
1088 if (sbp->st_ino == t->fts_statp->st_ino
1089 && sbp->st_dev == t->fts_statp->st_dev)
1099 if (S_ISLNK(sbp->st_mode))
1101 if (S_ISREG(sbp->st_mode))
1103 return (FTS_DEFAULT);
1107 fts_compar (void const *a, void const *b)
1109 /* Convert A and B to the correct types, to pacify the compiler, and
1110 for portability to bizarre hosts where "void const *" and "FTSENT
1111 const **" differ in runtime representation. The comparison
1112 function cannot modify *a and *b, but there is no compile-time
1114 FTSENT const **pa = (FTSENT const **) a;
1115 FTSENT const **pb = (FTSENT const **) b;
1116 return pa[0]->fts_fts->fts_compar (pa, pb);
1121 fts_sort (FTS *sp, FTSENT *head, register size_t nitems)
1123 register FTSENT **ap, *p;
1125 /* On most modern hosts, void * and FTSENT ** have the same
1126 run-time representation, and one can convert sp->fts_compar to
1127 the type qsort expects without problem. Use the heuristic that
1128 this is OK if the two pointer types are the same size, and if
1129 converting FTSENT ** to long int is the same as converting
1130 FTSENT ** to void * and then to long int. This heuristic isn't
1131 valid in general but we don't know of any counterexamples. */
1133 int (*compare) (void const *, void const *) =
1134 ((sizeof &dummy == sizeof (void *)
1135 && (long int) &dummy == (long int) (void *) &dummy)
1136 ? (int (*) (void const *, void const *)) sp->fts_compar
1140 * Construct an array of pointers to the structures and call qsort(3).
1141 * Reassemble the array in the order returned by qsort. If unable to
1142 * sort for memory reasons, return the directory entries in their
1143 * current order. Allocate enough space for the current needs plus
1144 * 40 so don't realloc one entry at a time.
1146 if (nitems > sp->fts_nitems) {
1149 sp->fts_nitems = nitems + 40;
1150 if (SIZE_MAX / sizeof *a < sp->fts_nitems
1151 || ! (a = realloc (sp->fts_array,
1152 sp->fts_nitems * sizeof *a))) {
1153 free(sp->fts_array);
1154 sp->fts_array = NULL;
1160 for (ap = sp->fts_array, p = head; p; p = p->fts_link)
1162 qsort((void *)sp->fts_array, nitems, sizeof(FTSENT *), compare);
1163 for (head = *(ap = sp->fts_array); --nitems; ++ap)
1164 ap[0]->fts_link = ap[1];
1165 ap[0]->fts_link = NULL;
1171 fts_alloc (FTS *sp, const char *name, register size_t namelen)
1177 * The file name is a variable length array. Allocate the FTSENT
1178 * structure and the file name in one chunk.
1180 len = sizeof(FTSENT) + namelen;
1181 if ((p = malloc(len)) == NULL)
1184 /* Copy the name and guarantee NUL termination. */
1185 memmove(p->fts_name, name, namelen);
1186 p->fts_name[namelen] = '\0';
1188 p->fts_namelen = namelen;
1190 p->fts_path = sp->fts_path;
1193 p->fts_instr = FTS_NOINSTR;
1195 p->fts_pointer = NULL;
1201 fts_lfree (register FTSENT *head)
1205 /* Free a linked list of structures. */
1206 while ((p = head)) {
1207 head = head->fts_link;
1213 * Allow essentially unlimited file name lengths; find, rm, ls should
1214 * all work on any tree. Most systems will allow creation of file
1215 * names much longer than MAXPATHLEN, even though the kernel won't
1216 * resolve them. Add the size (not just what's needed) plus 256 bytes
1217 * so don't realloc the file name 2 bytes at a time.
1221 fts_palloc (FTS *sp, size_t more)
1224 size_t new_len = sp->fts_pathlen + more + 256;
1227 * See if fts_pathlen would overflow.
1229 if (new_len < sp->fts_pathlen) {
1232 sp->fts_path = NULL;
1234 sp->fts_path = NULL;
1235 __set_errno (ENAMETOOLONG);
1238 sp->fts_pathlen = new_len;
1239 p = realloc(sp->fts_path, sp->fts_pathlen);
1242 sp->fts_path = NULL;
1250 * When the file name is realloc'd, have to fix all of the pointers in
1251 * structures already returned.
1255 fts_padjust (FTS *sp, FTSENT *head)
1258 char *addr = sp->fts_path;
1260 #define ADJUST(p) do { \
1261 if ((p)->fts_accpath != (p)->fts_name) { \
1262 (p)->fts_accpath = \
1263 (char *)addr + ((p)->fts_accpath - (p)->fts_path); \
1265 (p)->fts_path = addr; \
1267 /* Adjust the current set of children. */
1268 for (p = sp->fts_child; p; p = p->fts_link)
1271 /* Adjust the rest of the tree, including the current level. */
1272 for (p = head; p->fts_level >= FTS_ROOTLEVEL;) {
1274 p = p->fts_link ? p->fts_link : p->fts_parent;
1280 fts_maxarglen (char * const *argv)
1284 for (max = 0; *argv; ++argv)
1285 if ((len = strlen(*argv)) > max)
1291 * Change to dir specified by fd or file name without getting
1292 * tricked by someone changing the world out from underneath us.
1293 * Assumes p->fts_statp->st_dev and p->fts_statp->st_ino are filled in.
1297 fts_safe_changedir (FTS *sp, FTSENT *p, int fd, char const *dir)
1299 int ret, oerrno, newfd;
1303 if (ISSET(FTS_NOCHDIR))
1305 if (fd < 0 && (newfd = diropen (dir)) < 0)
1307 if (fstat(newfd, &sb)) {
1311 if (p->fts_statp->st_dev != sb.st_dev
1312 || p->fts_statp->st_ino != sb.st_ino) {
1313 __set_errno (ENOENT); /* disinformation */
1317 ret = fchdir(newfd);
1322 __set_errno (oerrno);