1 /* Traverse a file hierarchy.
3 Copyright (C) 2004, 2005, 2006, 2007, 2008 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 3 of the License, or
8 (at your option) any later version.
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, see <http://www.gnu.org/licenses/>. */
19 * Copyright (c) 1990, 1993, 1994
20 * The Regents of the University of California. All rights reserved.
22 * Redistribution and use in source and binary forms, with or without
23 * modification, are permitted provided that the following conditions
25 * 1. Redistributions of source code must retain the above copyright
26 * notice, this list of conditions and the following disclaimer.
27 * 2. Redistributions in binary form must reproduce the above copyright
28 * notice, this list of conditions and the following disclaimer in the
29 * documentation and/or other materials provided with the distribution.
30 * 4. Neither the name of the University nor the names of its contributors
31 * may be used to endorse or promote products derived from this software
32 * without specific prior written permission.
34 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
35 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
36 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
37 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
38 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
39 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
40 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
41 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
42 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
43 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
49 #if defined(LIBC_SCCS) && !defined(lint)
50 static char sccsid[] = "@(#)fts.c 8.6 (Berkeley) 8/14/94";
51 #endif /* LIBC_SCCS and not lint */
55 #if HAVE_SYS_PARAM_H || defined _LIBC
56 # include <sys/param.h>
59 # include <include/sys/stat.h>
61 # include <sys/stat.h>
73 # include "unistd--.h"
74 # include "same-inode.h"
78 #ifndef _D_EXACT_NAMLEN
79 # define _D_EXACT_NAMLEN(dirent) strlen ((dirent)->d_name)
82 #if HAVE_STRUCT_DIRENT_D_TYPE
83 /* True if the type of the directory entry D is known. */
84 # define DT_IS_KNOWN(d) ((d)->d_type != DT_UNKNOWN)
85 /* True if the type of the directory entry D must be T. */
86 # define DT_MUST_BE(d, t) ((d)->d_type == (t))
87 # define D_TYPE(d) ((d)->d_type)
89 # define DT_IS_KNOWN(d) false
90 # define DT_MUST_BE(d, t) false
91 # define D_TYPE(d) DT_UNKNOWN
96 /* Any nonzero values will do here, so long as they're distinct.
97 Undef any existing macros out of the way. */
123 NOT_AN_INODE_NUMBER = 0
126 #ifdef D_INO_IN_DIRENT
127 # define D_INO(dp) (dp)->d_ino
129 /* Some systems don't have inodes, so fake them to avoid lots of ifdefs. */
130 # define D_INO(dp) NOT_AN_INODE_NUMBER
133 /* If there are more than this many entries in a directory,
134 and the conditions mentioned below are satisfied, then sort
135 the entries on inode number before any further processing. */
136 #ifndef FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD
137 # define FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD 10000
141 _FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD = FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD
146 FTS_NO_STAT_REQUIRED = 1,
147 FTS_STAT_REQUIRED = 2
152 # define close __close
154 # define closedir __closedir
156 # define fchdir __fchdir
160 # define opendir __opendir
162 # define readdir __readdir
164 # undef internal_function
165 # define internal_function /* empty */
169 # define __set_errno(Val) errno = (Val)
172 #ifndef __attribute__
173 # if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 8)
174 # define __attribute__(x) /* empty */
178 #ifndef ATTRIBUTE_UNUSED
179 # define ATTRIBUTE_UNUSED __attribute__ ((__unused__))
182 /* If this host provides the openat function, then we can avoid
183 attempting to open "." in some initialization code below. */
185 # define HAVE_OPENAT_SUPPORT 1
187 # define HAVE_OPENAT_SUPPORT 0
191 # define fts_assert(expr) ((void) 0)
193 # define fts_assert(expr) \
202 static FTSENT *fts_alloc (FTS *, const char *, size_t) internal_function;
203 static FTSENT *fts_build (FTS *, int) internal_function;
204 static void fts_lfree (FTSENT *) internal_function;
205 static void fts_load (FTS *, FTSENT *) internal_function;
206 static size_t fts_maxarglen (char * const *) internal_function;
207 static void fts_padjust (FTS *, FTSENT *) internal_function;
208 static bool fts_palloc (FTS *, size_t) internal_function;
209 static FTSENT *fts_sort (FTS *, FTSENT *, size_t) internal_function;
210 static unsigned short int fts_stat (FTS *, FTSENT *, bool) internal_function;
211 static int fts_safe_changedir (FTS *, FTSENT *, int, const char *)
215 # include "fts-cycle.c"
217 static bool enter_dir (FTS *fts, FTSENT *ent) { return true; }
218 static void leave_dir (FTS *fts, FTSENT *ent) {}
219 static bool setup_dir (FTS *fts) { return true; }
220 static void free_dir (FTS *fts) {}
224 # define MAX(a,b) ((a) > (b) ? (a) : (b))
228 # define SIZE_MAX ((size_t) -1)
232 # define O_DIRECTORY 0
235 #define ISDOT(a) (a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2])))
236 #define STREQ(a, b) (strcmp ((a), (b)) == 0)
238 #define CLR(opt) (sp->fts_options &= ~(opt))
239 #define ISSET(opt) (sp->fts_options & (opt))
240 #define SET(opt) (sp->fts_options |= (opt))
242 /* FIXME: make this a function */
243 #define RESTORE_INITIAL_CWD(sp) \
244 (fd_ring_clear (&((sp)->fts_fd_ring)), \
245 FCHDIR ((sp), (ISSET (FTS_CWDFD) ? AT_FDCWD : (sp)->fts_rfd)))
247 /* FIXME: FTS_NOCHDIR is now misnamed.
248 Call it FTS_USE_FULL_RELATIVE_FILE_NAMES instead. */
249 #define FCHDIR(sp, fd) \
250 (!ISSET(FTS_NOCHDIR) && (ISSET(FTS_CWDFD) \
251 ? (cwd_advance_fd ((sp), (fd), true), 0) \
255 /* fts_build flags */
256 /* FIXME: make this an enum */
257 #define BCHILD 1 /* fts_children */
258 #define BNAMES 2 /* fts_children, names only */
259 #define BREAD 3 /* fts_read */
262 # include <inttypes.h>
265 # include "getcwdat.h"
266 bool fts_debug = false;
267 # define Dprintf(x) do { if (fts_debug) printf x; } while (false)
270 # define fd_ring_check(x)
271 # define fd_ring_print(a, b, c)
274 #define LEAVE_DIR(Fts, Ent, Tag) \
277 Dprintf ((" %s-leaving: %s\n", Tag, (Ent)->fts_path)); \
278 leave_dir (Fts, Ent); \
279 fd_ring_check (Fts); \
284 fd_ring_clear (I_ring *fd_ring)
286 while ( ! i_ring_empty (fd_ring))
288 int fd = i_ring_pop (fd_ring);
294 /* Overload the fts_statp->st_size member (otherwise unused, when
295 fts_info is FTS_NSOK) to indicate whether fts_read should stat
296 this entry or not. */
298 fts_set_stat_required (FTSENT *p, bool required)
300 fts_assert (p->fts_info == FTS_NSOK);
301 p->fts_statp->st_size = (required
303 : FTS_NO_STAT_REQUIRED);
306 /* file-descriptor-relative opendir. */
307 /* FIXME: if others need this function, move it into lib/openat.c */
310 opendirat (int fd, char const *dir)
312 int new_fd = openat (fd, dir, O_RDONLY);
317 dirp = fdopendir (new_fd);
320 int saved_errno = errno;
327 /* Virtual fchdir. Advance SP's working directory file descriptor,
328 SP->fts_cwd_fd, to FD, and push the previous value onto the fd_ring.
329 CHDIR_DOWN_ONE is true if FD corresponds to an entry in the directory
330 open on sp->fts_cwd_fd; i.e., to move the working directory one level
334 cwd_advance_fd (FTS *sp, int fd, bool chdir_down_one)
336 int old = sp->fts_cwd_fd;
337 fts_assert (old != fd || old == AT_FDCWD);
341 /* Push "old" onto the ring.
342 If the displaced file descriptor is non-negative, close it. */
343 int prev_fd_in_slot = i_ring_push (&sp->fts_fd_ring, old);
344 fd_ring_print (sp, stderr, "post-push");
345 if (0 <= prev_fd_in_slot)
346 close (prev_fd_in_slot); /* ignore any close failure */
348 else if ( ! ISSET (FTS_NOCHDIR))
351 close (old); /* ignore any close failure */
357 /* Open the directory DIR if possible, and return a file
358 descriptor. Return -1 and set errno on failure. It doesn't matter
359 whether the file descriptor has read or write access. */
363 diropen (FTS const *sp, char const *dir)
365 int open_flags = (O_RDONLY | O_DIRECTORY | O_NOCTTY | O_NONBLOCK
366 | (ISSET (FTS_PHYSICAL) ? O_NOFOLLOW : 0));
368 return (ISSET (FTS_CWDFD)
369 ? openat (sp->fts_cwd_fd, dir, open_flags)
370 : open (dir, open_flags));
374 fts_open (char * const *argv,
375 register int options,
376 int (*compar) (FTSENT const **, FTSENT const **))
379 register FTSENT *p, *root;
380 register size_t nitems;
381 FTSENT *parent = NULL;
382 FTSENT *tmp = NULL; /* pacify gcc */
387 if (options & ~FTS_OPTIONMASK) {
388 __set_errno (EINVAL);
391 if ((options & FTS_NOCHDIR) && (options & FTS_CWDFD)) {
392 __set_errno (EINVAL);
395 if ( ! (options & (FTS_LOGICAL | FTS_PHYSICAL))) {
396 __set_errno (EINVAL);
400 /* Allocate/initialize the stream */
401 if ((sp = malloc(sizeof(FTS))) == NULL)
403 memset(sp, 0, sizeof(FTS));
404 sp->fts_compar = compar;
405 sp->fts_options = options;
407 /* Logical walks turn on NOCHDIR; symbolic links are too hard. */
408 if (ISSET(FTS_LOGICAL)) {
413 /* Initialize fts_cwd_fd. */
414 sp->fts_cwd_fd = AT_FDCWD;
415 if ( ISSET(FTS_CWDFD) && ! HAVE_OPENAT_SUPPORT)
417 /* While it isn't technically necessary to open "." this
418 early, doing it here saves us the trouble of ensuring
419 later (where it'd be messier) that "." can in fact
420 be opened. If not, revert to FTS_NOCHDIR mode. */
421 int fd = open (".", O_RDONLY);
424 /* Even if `.' is unreadable, don't revert to FTS_NOCHDIR mode
425 on systems like Linux+PROC_FS, where our openat emulation
426 is good enough. Note: on a system that emulates
427 openat via /proc, this technique can still fail, but
428 only in extreme conditions, e.g., when the working
429 directory cannot be saved (i.e. save_cwd fails) --
430 and that happens on Linux only when "." is unreadable
431 and the CWD would be longer than PATH_MAX.
432 FIXME: once Linux kernel openat support is well established,
433 replace the above open call and this entire if/else block
434 with the body of the if-block below. */
435 if ( openat_needs_fchdir ())
448 * Start out with 1K of file name space, and enough, in any case,
449 * to hold the user's file names.
452 # define MAXPATHLEN 1024
455 size_t maxarglen = fts_maxarglen(argv);
456 if (! fts_palloc(sp, MAX(maxarglen, MAXPATHLEN)))
460 /* Allocate/initialize root's parent. */
462 if ((parent = fts_alloc(sp, "", 0)) == NULL)
464 parent->fts_level = FTS_ROOTPARENTLEVEL;
467 /* The classic fts implementation would call fts_stat with
468 a new entry for each iteration of the loop below.
469 If the comparison function is not specified or if the
470 FTS_DEFER_STAT option is in effect, don't stat any entry
471 in this loop. This is an attempt to minimize the interval
472 between the initial stat/lstat/fstatat and the point at which
473 a directory argument is first opened. This matters for any
474 directory command line argument that resides on a file system
475 without genuine i-nodes. If you specify FTS_DEFER_STAT along
476 with a comparison function, that function must not access any
477 data via the fts_statp pointer. */
478 defer_stat = (compar == NULL || ISSET(FTS_DEFER_STAT));
480 /* Allocate/initialize root(s). */
481 for (root = NULL, nitems = 0; *argv != NULL; ++argv, ++nitems) {
482 /* Don't allow zero-length file names. */
483 if ((len = strlen(*argv)) == 0) {
484 __set_errno (ENOENT);
488 if ((p = fts_alloc(sp, *argv, len)) == NULL)
490 p->fts_level = FTS_ROOTLEVEL;
491 p->fts_parent = parent;
492 p->fts_accpath = p->fts_name;
493 /* Even when defer_stat is true, be sure to stat the first
494 command line argument, since fts_read (at least with
495 FTS_XDEV) requires that. */
496 if (defer_stat && root != NULL) {
497 p->fts_info = FTS_NSOK;
498 fts_set_stat_required(p, true);
500 p->fts_info = fts_stat(sp, p, false);
504 * If comparison routine supplied, traverse in sorted
505 * order; otherwise traverse in the order specified.
520 if (compar && nitems > 1)
521 root = fts_sort(sp, root, nitems);
524 * Allocate a dummy pointer and make fts_read think that we've just
525 * finished the node before the root(s); set p->fts_info to FTS_INIT
526 * so that everything about the "current" node is ignored.
528 if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL)
530 sp->fts_cur->fts_link = root;
531 sp->fts_cur->fts_info = FTS_INIT;
532 if (! setup_dir (sp))
536 * If using chdir(2), grab a file descriptor pointing to dot to ensure
537 * that we can get back here; this could be avoided for some file names,
538 * but almost certainly not worth the effort. Slashes, symbolic links,
539 * and ".." are all fairly nasty problems. Note, if we can't get the
540 * descriptor we run anyway, just more slowly.
542 if (!ISSET(FTS_NOCHDIR) && !ISSET(FTS_CWDFD)
543 && (sp->fts_rfd = diropen (sp, ".")) < 0)
546 i_ring_init (&sp->fts_fd_ring, -1);
549 mem3: fts_lfree(root);
551 mem2: free(sp->fts_path);
558 fts_load (FTS *sp, register FTSENT *p)
564 * Load the stream structure for the next traversal. Since we don't
565 * actually enter the directory until after the preorder visit, set
566 * the fts_accpath field specially so the chdir gets done to the right
567 * place and the user can access the first node. From fts_open it's
568 * known that the file name will fit.
570 len = p->fts_pathlen = p->fts_namelen;
571 memmove(sp->fts_path, p->fts_name, len + 1);
572 if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) {
574 memmove(p->fts_name, cp, len + 1);
575 p->fts_namelen = len;
577 p->fts_accpath = p->fts_path = sp->fts_path;
583 register FTSENT *freep, *p;
587 * This still works if we haven't read anything -- the dummy structure
588 * points to the root list, so we step through to the end of the root
589 * list which has a valid parent pointer.
592 for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {
594 p = p->fts_link != NULL ? p->fts_link : p->fts_parent;
600 /* Free up child linked list, sort array, file name buffer. */
602 fts_lfree(sp->fts_child);
606 if (ISSET(FTS_CWDFD))
608 if (0 <= sp->fts_cwd_fd)
609 close (sp->fts_cwd_fd);
611 else if (!ISSET(FTS_NOCHDIR))
613 /* Return to original directory, save errno if necessary. */
614 if (fchdir(sp->fts_rfd))
619 fd_ring_clear (&sp->fts_fd_ring);
622 /* Free up the stream pointer. */
625 /* Set errno and return. */
627 __set_errno (saved_errno);
635 * Special case of "/" at the end of the file name so that slashes aren't
636 * appended which would cause file names to be written as "....//foo".
639 (p->fts_path[p->fts_pathlen - 1] == '/' \
640 ? p->fts_pathlen - 1 : p->fts_pathlen)
643 fts_read (register FTS *sp)
645 register FTSENT *p, *tmp;
646 register unsigned short int instr;
649 /* If finished or unrecoverable error, return NULL. */
650 if (sp->fts_cur == NULL || ISSET(FTS_STOP))
653 /* Set current node pointer. */
656 /* Save and zero out user instructions. */
657 instr = p->fts_instr;
658 p->fts_instr = FTS_NOINSTR;
660 /* Any type of file may be re-visited; re-stat and re-turn. */
661 if (instr == FTS_AGAIN) {
662 p->fts_info = fts_stat(sp, p, false);
665 Dprintf (("fts_read: p=%s\n",
666 p->fts_info == FTS_INIT ? "" : p->fts_path));
669 * Following a symlink -- SLNONE test allows application to see
670 * SLNONE and recover. If indirecting through a symlink, have
671 * keep a pointer to current location. If unable to get that
672 * pointer, follow fails.
674 if (instr == FTS_FOLLOW &&
675 (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) {
676 p->fts_info = fts_stat(sp, p, true);
677 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
678 if ((p->fts_symfd = diropen (sp, ".")) < 0) {
679 p->fts_errno = errno;
680 p->fts_info = FTS_ERR;
682 p->fts_flags |= FTS_SYMFOLLOW;
687 /* Directory in pre-order. */
688 if (p->fts_info == FTS_D) {
689 /* If skipped or crossed mount point, do post-order visit. */
690 if (instr == FTS_SKIP ||
691 (ISSET(FTS_XDEV) && p->fts_statp->st_dev != sp->fts_dev)) {
692 if (p->fts_flags & FTS_SYMFOLLOW)
693 (void)close(p->fts_symfd);
695 fts_lfree(sp->fts_child);
696 sp->fts_child = NULL;
698 p->fts_info = FTS_DP;
699 LEAVE_DIR (sp, p, "1");
703 /* Rebuild if only read the names and now traversing. */
704 if (sp->fts_child != NULL && ISSET(FTS_NAMEONLY)) {
706 fts_lfree(sp->fts_child);
707 sp->fts_child = NULL;
711 * Cd to the subdirectory.
713 * If have already read and now fail to chdir, whack the list
714 * to make the names come out right, and set the parent errno
715 * so the application will eventually get an error condition.
716 * Set the FTS_DONTCHDIR flag so that when we logically change
717 * directories back to the parent we don't do a chdir.
719 * If haven't read do so. If the read fails, fts_build sets
720 * FTS_STOP or the fts_info field of the node.
722 if (sp->fts_child != NULL) {
723 if (fts_safe_changedir(sp, p, -1, p->fts_accpath)) {
724 p->fts_errno = errno;
725 p->fts_flags |= FTS_DONTCHDIR;
726 for (p = sp->fts_child; p != NULL;
729 p->fts_parent->fts_accpath;
731 } else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) {
734 /* If fts_build's call to fts_safe_changedir failed
735 because it was not able to fchdir into a
736 subdirectory, tell the caller. */
737 if (p->fts_errno && p->fts_info != FTS_DNR)
738 p->fts_info = FTS_ERR;
739 LEAVE_DIR (sp, p, "2");
743 sp->fts_child = NULL;
747 /* Move to the next node on this level. */
749 if ((p = p->fts_link) != NULL) {
754 * If reached the top, return to the original directory (or
755 * the root of the tree), and load the file names for the next
758 if (p->fts_level == FTS_ROOTLEVEL) {
759 if (RESTORE_INITIAL_CWD(sp)) {
768 * User may have called fts_set on the node. If skipped,
769 * ignore. If followed, get a file descriptor so we can
770 * get back if necessary.
772 if (p->fts_instr == FTS_SKIP)
774 if (p->fts_instr == FTS_FOLLOW) {
775 p->fts_info = fts_stat(sp, p, true);
776 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
777 if ((p->fts_symfd = diropen (sp, ".")) < 0) {
778 p->fts_errno = errno;
779 p->fts_info = FTS_ERR;
781 p->fts_flags |= FTS_SYMFOLLOW;
783 p->fts_instr = FTS_NOINSTR;
786 name: t = sp->fts_path + NAPPEND(p->fts_parent);
788 memmove(t, p->fts_name, p->fts_namelen + 1);
791 if (p->fts_info == FTS_NSOK)
793 if (p->fts_statp->st_size == FTS_STAT_REQUIRED)
794 p->fts_info = fts_stat(sp, p, false);
796 fts_assert (p->fts_statp->st_size == FTS_NO_STAT_REQUIRED);
799 if (p->fts_info == FTS_D)
801 /* Now that P->fts_statp is guaranteed to be valid,
802 if this is a command-line directory, record its
803 device number, to be used for FTS_XDEV. */
804 if (p->fts_level == FTS_ROOTLEVEL)
805 sp->fts_dev = p->fts_statp->st_dev;
806 Dprintf ((" entering: %s\n", p->fts_path));
807 if (! enter_dir (sp, p))
809 __set_errno (ENOMEM);
816 /* Move up to the parent node. */
821 if (p->fts_level == FTS_ROOTPARENTLEVEL) {
823 * Done; free everything up and set errno to 0 so the user
824 * can distinguish between error and EOF.
828 return (sp->fts_cur = NULL);
831 fts_assert (p->fts_info != FTS_NSOK);
833 /* NUL terminate the file name. */
834 sp->fts_path[p->fts_pathlen] = '\0';
837 * Return to the parent directory. If at a root node, restore
838 * the initial working directory. If we came through a symlink,
839 * go back through the file descriptor. Otherwise, move up
840 * one level, via "..".
842 if (p->fts_level == FTS_ROOTLEVEL) {
843 if (RESTORE_INITIAL_CWD(sp)) {
844 p->fts_errno = errno;
847 } else if (p->fts_flags & FTS_SYMFOLLOW) {
848 if (FCHDIR(sp, p->fts_symfd)) {
849 int saved_errno = errno;
850 (void)close(p->fts_symfd);
851 __set_errno (saved_errno);
852 p->fts_errno = errno;
855 (void)close(p->fts_symfd);
856 } else if (!(p->fts_flags & FTS_DONTCHDIR) &&
857 fts_safe_changedir(sp, p->fts_parent, -1, "..")) {
858 p->fts_errno = errno;
861 p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;
862 if (p->fts_errno == 0)
863 LEAVE_DIR (sp, p, "3");
864 return ISSET(FTS_STOP) ? NULL : p;
868 * Fts_set takes the stream as an argument although it's not used in this
869 * implementation; it would be necessary if anyone wanted to add global
870 * semantics to fts using fts_set. An error return is allowed for similar
875 fts_set(FTS *sp ATTRIBUTE_UNUSED, FTSENT *p, int instr)
877 if (instr != 0 && instr != FTS_AGAIN && instr != FTS_FOLLOW &&
878 instr != FTS_NOINSTR && instr != FTS_SKIP) {
879 __set_errno (EINVAL);
882 p->fts_instr = instr;
887 fts_children (register FTS *sp, int instr)
892 if (instr != 0 && instr != FTS_NAMEONLY) {
893 __set_errno (EINVAL);
897 /* Set current node pointer. */
901 * Errno set to 0 so user can distinguish empty directory from
906 /* Fatal errors stop here. */
910 /* Return logical hierarchy of user's arguments. */
911 if (p->fts_info == FTS_INIT)
912 return (p->fts_link);
915 * If not a directory being visited in pre-order, stop here. Could
916 * allow FTS_DNR, assuming the user has fixed the problem, but the
917 * same effect is available with FTS_AGAIN.
919 if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */)
922 /* Free up any previous child list. */
923 if (sp->fts_child != NULL)
924 fts_lfree(sp->fts_child);
926 if (instr == FTS_NAMEONLY) {
933 * If using chdir on a relative file name and called BEFORE fts_read
934 * does its chdir to the root of a traversal, we can lose -- we need to
935 * chdir into the subdirectory, and we don't know where the current
936 * directory is, so we can't get back so that the upcoming chdir by
937 * fts_read will work.
939 if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' ||
941 return (sp->fts_child = fts_build(sp, instr));
943 if ((fd = diropen (sp, ".")) < 0)
944 return (sp->fts_child = NULL);
945 sp->fts_child = fts_build(sp, instr);
946 if (ISSET(FTS_CWDFD))
948 cwd_advance_fd (sp, fd, true);
954 int saved_errno = errno;
956 __set_errno (saved_errno);
961 return (sp->fts_child);
964 #if defined __linux__ \
965 && HAVE_SYS_VFS_H && HAVE_FSTATFS && HAVE_STRUCT_STATFS_F_TYPE
969 /* Linux-specific constants from coreutils' src/fs.h */
970 # define S_MAGIC_TMPFS 0x1021994
971 # define S_MAGIC_NFS 0x6969
973 /* Return false if it is easy to determine the file system type of
974 the directory on which DIR_FD is open, and sorting dirents on
975 inode numbers is known not to improve traversal performance with
976 that type of file system. Otherwise, return true. */
978 dirent_inode_sort_may_be_useful (int dir_fd)
980 /* Skip the sort only if we can determine efficiently
981 that skipping it is the right thing to do.
982 The cost of performing an unnecessary sort is negligible,
983 while the cost of *not* performing it can be O(N^2) with
984 a very large constant. */
985 struct statfs fs_buf;
987 /* If fstatfs fails, assume sorting would be useful. */
988 if (fstatfs (dir_fd, &fs_buf) != 0)
991 /* FIXME: what about when f_type is not an integral type?
992 deal with that if/when it's encountered. */
993 switch (fs_buf.f_type)
997 /* On a file system of any of these types, sorting
998 is unnecessary, and hence wasteful. */
1006 static bool dirent_inode_sort_may_be_useful (int dir_fd) { return true; }
1009 /* A comparison function to sort on increasing inode number.
1010 For some file system types, sorting either way makes a huge
1011 performance difference for a directory with very many entries,
1012 but sorting on increasing values is slightly better than sorting
1013 on decreasing values. The difference is in the 5% range. */
1015 fts_compare_ino (struct _ftsent const **a, struct _ftsent const **b)
1017 return (a[0]->fts_statp->st_ino < b[0]->fts_statp->st_ino ? -1
1018 : b[0]->fts_statp->st_ino < a[0]->fts_statp->st_ino ? 1 : 0);
1021 /* Map the dirent.d_type value, DTYPE, to the corresponding stat.st_mode
1022 S_IF* bit and set ST.st_mode, thus clearing all other bits in that field. */
1024 set_stat_type (struct stat *st, unsigned int dtype)
1057 * This is the tricky part -- do not casually change *anything* in here. The
1058 * idea is to build the linked list of entries that are used by fts_children
1059 * and fts_read. There are lots of special cases.
1061 * The real slowdown in walking the tree is the stat calls. If FTS_NOSTAT is
1062 * set and it's a physical walk (so that symbolic links can't be directories),
1063 * we can do things quickly. First, if it's a 4.4BSD file system, the type
1064 * of the file is in the directory entry. Otherwise, we assume that the number
1065 * of subdirectories in a node is equal to the number of links to the parent.
1066 * The former skips all stat calls. The latter skips stat calls in any leaf
1067 * directories and for any files after the subdirectories in the directory have
1068 * been found, cutting the stat calls by about 2/3.
1072 fts_build (register FTS *sp, int type)
1074 register struct dirent *dp;
1075 register FTSENT *p, *head;
1076 register size_t nitems;
1086 size_t len, maxlen, new_len;
1089 /* Set current node pointer. */
1093 * Open the directory for reading. If this fails, we're done.
1094 * If being called from fts_read, set the fts_info field.
1096 #if defined FTS_WHITEOUT && 0
1097 if (ISSET(FTS_WHITEOUT))
1098 oflag = DTF_NODUP|DTF_REWIND;
1100 oflag = DTF_HIDEW|DTF_NODUP|DTF_REWIND;
1102 # define __opendir2(file, flag) \
1103 ( ! ISSET(FTS_NOCHDIR) && ISSET(FTS_CWDFD) \
1104 ? opendirat(sp->fts_cwd_fd, file) \
1107 if ((dirp = __opendir2(cur->fts_accpath, oflag)) == NULL) {
1108 if (type == BREAD) {
1109 cur->fts_info = FTS_DNR;
1110 cur->fts_errno = errno;
1114 /* Rather than calling fts_stat for each and every entry encountered
1115 in the readdir loop (below), stat each directory only right after
1117 if (cur->fts_info == FTS_NSOK)
1118 cur->fts_info = fts_stat(sp, cur, false);
1121 * Nlinks is the number of possible entries of type directory in the
1122 * directory if we're cheating on stat calls, 0 if we're not doing
1123 * any stat calls at all, (nlink_t) -1 if we're statting everything.
1125 if (type == BNAMES) {
1127 /* Be quiet about nostat, GCC. */
1129 } else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) {
1130 nlinks = (cur->fts_statp->st_nlink
1131 - (ISSET(FTS_SEEDOT) ? 0 : 2));
1139 * If we're going to need to stat anything or we want to descend
1140 * and stay in the directory, chdir. If this fails we keep going,
1141 * but set a flag so we don't chdir after the post-order visit.
1142 * We won't be able to stat anything, but we can still return the
1143 * names themselves. Note, that since fts_read won't be able to
1144 * chdir into the directory, it will have to return different file
1145 * names than before, i.e. "a/b" instead of "b". Since the node
1146 * has already been visited in pre-order, have to wait until the
1147 * post-order visit to return the error. There is a special case
1148 * here, if there was nothing to stat then it's not an error to
1149 * not be able to stat. This is all fairly nasty. If a program
1150 * needed sorted entries or stat information, they had better be
1151 * checking FTS_NS on the returned nodes.
1153 if (nlinks || type == BREAD) {
1154 int dir_fd = dirfd(dirp);
1155 if (ISSET(FTS_CWDFD) && 0 <= dir_fd)
1156 dir_fd = dup (dir_fd);
1157 if (dir_fd < 0 || fts_safe_changedir(sp, cur, dir_fd, NULL)) {
1158 if (nlinks && type == BREAD)
1159 cur->fts_errno = errno;
1160 cur->fts_flags |= FTS_DONTCHDIR;
1163 if (ISSET(FTS_CWDFD) && 0 <= dir_fd)
1172 * Figure out the max file name length that can be stored in the
1173 * current buffer -- the inner loop allocates more space as necessary.
1174 * We really wouldn't have to do the maxlen calculations here, we
1175 * could do them in fts_read before returning the name, but it's a
1176 * lot easier here since the length is part of the dirent structure.
1178 * If not changing directories set a pointer so that can just append
1179 * each new component into the file name.
1182 if (ISSET(FTS_NOCHDIR)) {
1183 cp = sp->fts_path + len;
1186 /* GCC, you're too verbose. */
1190 maxlen = sp->fts_pathlen - len;
1192 level = cur->fts_level + 1;
1194 /* Read the directory, attaching each entry to the `link' pointer. */
1196 for (head = tail = NULL, nitems = 0; dirp && (dp = readdir(dirp));) {
1199 if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))
1202 if ((p = fts_alloc (sp, dp->d_name,
1203 _D_EXACT_NAMLEN (dp))) == NULL)
1205 if (_D_EXACT_NAMLEN (dp) >= maxlen) {
1206 /* include space for NUL */
1207 oldaddr = sp->fts_path;
1208 if (! fts_palloc(sp, _D_EXACT_NAMLEN (dp) + len + 1)) {
1210 * No more memory. Save
1211 * errno, free up the current structure and the
1212 * structures already allocated.
1214 mem1: saved_errno = errno;
1218 cur->fts_info = FTS_ERR;
1220 __set_errno (saved_errno);
1223 /* Did realloc() change the pointer? */
1224 if (oldaddr != sp->fts_path) {
1226 if (ISSET(FTS_NOCHDIR))
1227 cp = sp->fts_path + len;
1229 maxlen = sp->fts_pathlen - len;
1232 new_len = len + _D_EXACT_NAMLEN (dp);
1233 if (new_len < len) {
1235 * In the unlikely event that we would end up
1236 * with a file name longer than SIZE_MAX, free up
1237 * the current structure and the structures already
1238 * allocated, then error out with ENAMETOOLONG.
1243 cur->fts_info = FTS_ERR;
1245 __set_errno (ENAMETOOLONG);
1248 p->fts_level = level;
1249 p->fts_parent = sp->fts_cur;
1250 p->fts_pathlen = new_len;
1252 #if defined FTS_WHITEOUT && 0
1253 if (dp->d_type == DT_WHT)
1254 p->fts_flags |= FTS_ISW;
1256 /* Store dirent.d_ino, in case we need to sort
1257 entries before processing them. */
1258 p->fts_statp->st_ino = D_INO (dp);
1260 /* Build a file name for fts_stat to stat. */
1261 if (ISSET(FTS_NOCHDIR)) {
1262 p->fts_accpath = p->fts_path;
1263 memmove(cp, p->fts_name, p->fts_namelen + 1);
1265 p->fts_accpath = p->fts_name;
1267 if (sp->fts_compar == NULL || ISSET(FTS_DEFER_STAT)) {
1268 /* Record what fts_read will have to do with this
1269 entry. In many cases, it will simply fts_stat it,
1270 but we can take advantage of any d_type information
1271 to optimize away the unnecessary stat calls. I.e.,
1272 if FTS_NOSTAT is in effect and we're not following
1273 symlinks (FTS_PHYSICAL) and d_type indicates this
1274 is *not* a directory, then we won't have to stat it
1275 at all. If it *is* a directory, then (currently)
1276 we stat it regardless, in order to get device and
1277 inode numbers. Some day we might optimize that
1278 away, too, for directories where d_ino is known to
1280 bool skip_stat = (ISSET(FTS_PHYSICAL)
1281 && ISSET(FTS_NOSTAT)
1283 && ! DT_MUST_BE(dp, DT_DIR));
1284 p->fts_info = FTS_NSOK;
1285 /* Propagate dirent.d_type information back
1286 to caller, when possible. */
1287 set_stat_type (p->fts_statp, D_TYPE (dp));
1288 fts_set_stat_required(p, !skip_stat);
1289 is_dir = (ISSET(FTS_PHYSICAL) && ISSET(FTS_NOSTAT)
1290 && DT_MUST_BE(dp, DT_DIR));
1292 p->fts_info = fts_stat(sp, p, false);
1293 is_dir = (p->fts_info == FTS_D
1294 || p->fts_info == FTS_DC
1295 || p->fts_info == FTS_DOT);
1298 /* Decrement link count if applicable. */
1299 if (nlinks > 0 && is_dir)
1302 /* We walk in directory order so "ls -f" doesn't get upset. */
1316 * If realloc() changed the address of the file name, adjust the
1317 * addresses for the rest of the tree and the dir list.
1320 fts_padjust(sp, head);
1323 * If not changing directories, reset the file name back to original
1326 if (ISSET(FTS_NOCHDIR)) {
1327 if (len == sp->fts_pathlen || nitems == 0)
1333 * If descended after called from fts_children or after called from
1334 * fts_read and nothing found, get back. At the root level we use
1335 * the saved fd; if one of fts_open()'s arguments is a relative name
1336 * to an empty directory, we wind up here with no other way back. If
1337 * can't get back, we're done.
1339 if (descend && (type == BCHILD || !nitems) &&
1340 (cur->fts_level == FTS_ROOTLEVEL
1341 ? RESTORE_INITIAL_CWD(sp)
1342 : fts_safe_changedir(sp, cur->fts_parent, -1, ".."))) {
1343 cur->fts_info = FTS_ERR;
1349 /* If didn't find anything, return NULL. */
1352 cur->fts_info = FTS_DP;
1357 /* If there are many entries, no sorting function has been specified,
1358 and this file system is of a type that may be slow with a large
1359 number of entries, then sort the directory entries on increasing
1361 if (nitems > _FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD
1363 && ISSET (FTS_CWDFD)
1364 && dirent_inode_sort_may_be_useful (sp->fts_cwd_fd)) {
1365 sp->fts_compar = fts_compare_ino;
1366 head = fts_sort (sp, head, nitems);
1367 sp->fts_compar = NULL;
1370 /* Sort the entries. */
1371 if (sp->fts_compar && nitems > 1)
1372 head = fts_sort(sp, head, nitems);
1378 /* Walk ->fts_parent links starting at E_CURR, until the root of the
1379 current hierarchy. There should be a directory with dev/inode
1380 matching those of AD. If not, print a lot of diagnostics. */
1382 find_matching_ancestor (FTSENT const *e_curr, struct Active_dir const *ad)
1385 for (ent = e_curr; ent->fts_level >= FTS_ROOTLEVEL; ent = ent->fts_parent)
1387 if (ad->ino == ent->fts_statp->st_ino
1388 && ad->dev == ent->fts_statp->st_dev)
1391 printf ("ERROR: tree dir, %s, not active\n", ad->fts_ent->fts_accpath);
1392 printf ("active dirs:\n");
1394 ent->fts_level >= FTS_ROOTLEVEL; ent = ent->fts_parent)
1395 printf (" %s(%"PRIuMAX"/%"PRIuMAX") to %s(%"PRIuMAX"/%"PRIuMAX")...\n",
1396 ad->fts_ent->fts_accpath,
1397 (uintmax_t) ad->dev,
1398 (uintmax_t) ad->ino,
1400 (uintmax_t) ent->fts_statp->st_dev,
1401 (uintmax_t) ent->fts_statp->st_ino);
1405 fts_cross_check (FTS const *sp)
1407 FTSENT const *ent = sp->fts_cur;
1409 if ( ! ISSET (FTS_TIGHT_CYCLE_CHECK))
1412 Dprintf (("fts-cross-check cur=%s\n", ent->fts_path));
1413 /* Make sure every parent dir is in the tree. */
1414 for (t = ent->fts_parent; t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
1416 struct Active_dir ad;
1417 ad.ino = t->fts_statp->st_ino;
1418 ad.dev = t->fts_statp->st_dev;
1419 if ( ! hash_lookup (sp->fts_cycle.ht, &ad))
1420 printf ("ERROR: active dir, %s, not in tree\n", t->fts_path);
1423 /* Make sure every dir in the tree is an active dir.
1424 But ENT is not necessarily a directory. If so, just skip this part. */
1425 if (ent->fts_parent->fts_level >= FTS_ROOTLEVEL
1426 && (ent->fts_info == FTS_DP
1427 || ent->fts_info == FTS_D))
1429 struct Active_dir *ad;
1430 for (ad = hash_get_first (sp->fts_cycle.ht); ad != NULL;
1431 ad = hash_get_next (sp->fts_cycle.ht, ad))
1433 find_matching_ancestor (ent, ad);
1439 same_fd (int fd1, int fd2)
1441 struct stat sb1, sb2;
1442 return (fstat (fd1, &sb1) == 0
1443 && fstat (fd2, &sb2) == 0
1444 && SAME_INODE (sb1, sb2));
1448 fd_ring_print (FTS const *sp, FILE *stream, char const *msg)
1450 I_ring const *fd_ring = &sp->fts_fd_ring;
1451 unsigned int i = fd_ring->fts_front;
1452 char *cwd = getcwdat (sp->fts_cwd_fd, NULL, 0);
1453 fprintf (stream, "=== %s ========== %s\n", msg, cwd);
1455 if (i_ring_empty (fd_ring))
1460 int fd = fd_ring->fts_fd_ring[i];
1462 fprintf (stream, "%d: %d:\n", i, fd);
1465 char *wd = getcwdat (fd, NULL, 0);
1466 fprintf (stream, "%d: %d: %s\n", i, fd, wd);
1469 if (i == fd_ring->fts_back)
1471 i = (i + I_RING_SIZE - 1) % I_RING_SIZE;
1475 /* Ensure that each file descriptor on the fd_ring matches a
1476 parent, grandparent, etc. of the current working directory. */
1478 fd_ring_check (FTS const *sp)
1483 /* Make a writable copy. */
1484 I_ring fd_w = sp->fts_fd_ring;
1486 int cwd_fd = sp->fts_cwd_fd;
1487 cwd_fd = dup (cwd_fd);
1488 char *dot = getcwdat (cwd_fd, NULL, 0);
1489 error (0, 0, "===== check ===== cwd: %s", dot);
1491 while ( ! i_ring_empty (&fd_w))
1493 int fd = i_ring_pop (&fd_w);
1496 int parent_fd = openat (cwd_fd, "..", O_RDONLY);
1502 if (!same_fd (fd, parent_fd))
1504 char *cwd = getcwdat (fd, NULL, 0);
1505 error (0, errno, "ring : %s", cwd);
1506 char *c2 = getcwdat (parent_fd, NULL, 0);
1507 error (0, errno, "parent: %s", c2);
1520 static unsigned short int
1522 fts_stat(FTS *sp, register FTSENT *p, bool follow)
1524 struct stat *sbp = p->fts_statp;
1527 if (p->fts_level == FTS_ROOTLEVEL && ISSET(FTS_COMFOLLOW))
1530 #if defined FTS_WHITEOUT && 0
1531 /* check for whiteout */
1532 if (p->fts_flags & FTS_ISW) {
1533 memset(sbp, '\0', sizeof (*sbp));
1534 sbp->st_mode = S_IFWHT;
1540 * If doing a logical walk, or application requested FTS_FOLLOW, do
1541 * a stat(2). If that fails, check for a non-existent symlink. If
1542 * fail, set the errno from the stat call.
1544 if (ISSET(FTS_LOGICAL) || follow) {
1545 if (stat(p->fts_accpath, sbp)) {
1546 saved_errno = errno;
1548 && lstat(p->fts_accpath, sbp) == 0) {
1550 return (FTS_SLNONE);
1552 p->fts_errno = saved_errno;
1555 } else if (fstatat(sp->fts_cwd_fd, p->fts_accpath, sbp,
1556 AT_SYMLINK_NOFOLLOW)) {
1557 p->fts_errno = errno;
1558 err: memset(sbp, 0, sizeof(struct stat));
1562 if (S_ISDIR(sbp->st_mode)) {
1563 if (ISDOT(p->fts_name)) {
1564 /* Command-line "." and ".." are real directories. */
1565 return (p->fts_level == FTS_ROOTLEVEL ? FTS_D : FTS_DOT);
1571 * Cycle detection is done by brute force when the directory
1572 * is first encountered. If the tree gets deep enough or the
1573 * number of symbolic links to directories is high enough,
1574 * something faster might be worthwhile.
1578 for (t = p->fts_parent;
1579 t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
1580 if (sbp->st_ino == t->fts_statp->st_ino
1581 && sbp->st_dev == t->fts_statp->st_dev)
1591 if (S_ISLNK(sbp->st_mode))
1593 if (S_ISREG(sbp->st_mode))
1595 return (FTS_DEFAULT);
1599 fts_compar (void const *a, void const *b)
1601 /* Convert A and B to the correct types, to pacify the compiler, and
1602 for portability to bizarre hosts where "void const *" and "FTSENT
1603 const **" differ in runtime representation. The comparison
1604 function cannot modify *a and *b, but there is no compile-time
1606 FTSENT const **pa = (FTSENT const **) a;
1607 FTSENT const **pb = (FTSENT const **) b;
1608 return pa[0]->fts_fts->fts_compar (pa, pb);
1613 fts_sort (FTS *sp, FTSENT *head, register size_t nitems)
1615 register FTSENT **ap, *p;
1617 /* On most modern hosts, void * and FTSENT ** have the same
1618 run-time representation, and one can convert sp->fts_compar to
1619 the type qsort expects without problem. Use the heuristic that
1620 this is OK if the two pointer types are the same size, and if
1621 converting FTSENT ** to long int is the same as converting
1622 FTSENT ** to void * and then to long int. This heuristic isn't
1623 valid in general but we don't know of any counterexamples. */
1625 int (*compare) (void const *, void const *) =
1626 ((sizeof &dummy == sizeof (void *)
1627 && (long int) &dummy == (long int) (void *) &dummy)
1628 ? (int (*) (void const *, void const *)) sp->fts_compar
1632 * Construct an array of pointers to the structures and call qsort(3).
1633 * Reassemble the array in the order returned by qsort. If unable to
1634 * sort for memory reasons, return the directory entries in their
1635 * current order. Allocate enough space for the current needs plus
1636 * 40 so don't realloc one entry at a time.
1638 if (nitems > sp->fts_nitems) {
1641 sp->fts_nitems = nitems + 40;
1642 if (SIZE_MAX / sizeof *a < sp->fts_nitems
1643 || ! (a = realloc (sp->fts_array,
1644 sp->fts_nitems * sizeof *a))) {
1645 free(sp->fts_array);
1646 sp->fts_array = NULL;
1652 for (ap = sp->fts_array, p = head; p; p = p->fts_link)
1654 qsort((void *)sp->fts_array, nitems, sizeof(FTSENT *), compare);
1655 for (head = *(ap = sp->fts_array); --nitems; ++ap)
1656 ap[0]->fts_link = ap[1];
1657 ap[0]->fts_link = NULL;
1663 fts_alloc (FTS *sp, const char *name, register size_t namelen)
1669 * The file name is a variable length array. Allocate the FTSENT
1670 * structure and the file name in one chunk.
1672 len = sizeof(FTSENT) + namelen;
1673 if ((p = malloc(len)) == NULL)
1676 /* Copy the name and guarantee NUL termination. */
1677 memmove(p->fts_name, name, namelen);
1678 p->fts_name[namelen] = '\0';
1680 p->fts_namelen = namelen;
1682 p->fts_path = sp->fts_path;
1685 p->fts_instr = FTS_NOINSTR;
1687 p->fts_pointer = NULL;
1693 fts_lfree (register FTSENT *head)
1697 /* Free a linked list of structures. */
1698 while ((p = head)) {
1699 head = head->fts_link;
1705 * Allow essentially unlimited file name lengths; find, rm, ls should
1706 * all work on any tree. Most systems will allow creation of file
1707 * names much longer than MAXPATHLEN, even though the kernel won't
1708 * resolve them. Add the size (not just what's needed) plus 256 bytes
1709 * so don't realloc the file name 2 bytes at a time.
1713 fts_palloc (FTS *sp, size_t more)
1716 size_t new_len = sp->fts_pathlen + more + 256;
1719 * See if fts_pathlen would overflow.
1721 if (new_len < sp->fts_pathlen) {
1723 sp->fts_path = NULL;
1724 __set_errno (ENAMETOOLONG);
1727 sp->fts_pathlen = new_len;
1728 p = realloc(sp->fts_path, sp->fts_pathlen);
1731 sp->fts_path = NULL;
1739 * When the file name is realloc'd, have to fix all of the pointers in
1740 * structures already returned.
1744 fts_padjust (FTS *sp, FTSENT *head)
1747 char *addr = sp->fts_path;
1749 #define ADJUST(p) do { \
1750 if ((p)->fts_accpath != (p)->fts_name) { \
1751 (p)->fts_accpath = \
1752 (char *)addr + ((p)->fts_accpath - (p)->fts_path); \
1754 (p)->fts_path = addr; \
1756 /* Adjust the current set of children. */
1757 for (p = sp->fts_child; p; p = p->fts_link)
1760 /* Adjust the rest of the tree, including the current level. */
1761 for (p = head; p->fts_level >= FTS_ROOTLEVEL;) {
1763 p = p->fts_link ? p->fts_link : p->fts_parent;
1769 fts_maxarglen (char * const *argv)
1773 for (max = 0; *argv; ++argv)
1774 if ((len = strlen(*argv)) > max)
1780 * Change to dir specified by fd or file name without getting
1781 * tricked by someone changing the world out from underneath us.
1782 * Assumes p->fts_statp->st_dev and p->fts_statp->st_ino are filled in.
1783 * If FD is non-negative, expect it to be used after this function returns,
1784 * and to be closed eventually. So don't pass e.g., `dirfd(dirp)' and then
1785 * do closedir(dirp), because that would invalidate the saved FD.
1786 * Upon failure, close FD immediately and return nonzero.
1790 fts_safe_changedir (FTS *sp, FTSENT *p, int fd, char const *dir)
1793 bool is_dotdot = dir && STREQ (dir, "..");
1796 /* This clause handles the unusual case in which FTS_NOCHDIR
1797 is specified, along with FTS_CWDFD. In that case, there is
1798 no need to change even the virtual cwd file descriptor.
1799 However, if FD is non-negative, we do close it here. */
1800 if (ISSET (FTS_NOCHDIR))
1802 if (ISSET (FTS_CWDFD) && 0 <= fd)
1807 if (fd < 0 && is_dotdot && ISSET (FTS_CWDFD))
1809 /* When possible, skip the diropen and subsequent fstat+dev/ino
1810 comparison. I.e., when changing to parent directory
1811 (chdir ("..")), use a file descriptor from the ring and
1812 save the overhead of diropen+fstat, as well as avoiding
1813 failure when we lack "x" access to the virtual cwd. */
1814 if ( ! i_ring_empty (&sp->fts_fd_ring))
1817 fd_ring_print (sp, stderr, "pre-pop");
1818 parent_fd = i_ring_pop (&sp->fts_fd_ring);
1829 if (fd < 0 && (newfd = diropen (sp, dir)) < 0)
1832 /* The following dev/inode check is necessary if we're doing a
1833 `logical' traversal (through symlinks, a la chown -L), if the
1834 system lacks O_NOFOLLOW support, or if we're changing to ".."
1835 (but not via a popped file descriptor). When changing to the
1836 name "..", O_NOFOLLOW can't help. In general, when the target is
1837 not "..", diropen's use of O_NOFOLLOW ensures we don't mistakenly
1838 follow a symlink, so we can avoid the expense of this fstat. */
1839 if (ISSET(FTS_LOGICAL) || ! HAVE_WORKING_O_NOFOLLOW
1840 || (dir && STREQ (dir, "..")))
1843 if (fstat(newfd, &sb))
1848 if (p->fts_statp->st_dev != sb.st_dev
1849 || p->fts_statp->st_ino != sb.st_ino)
1851 __set_errno (ENOENT); /* disinformation */
1857 if (ISSET(FTS_CWDFD))
1859 cwd_advance_fd (sp, newfd, ! is_dotdot);
1863 ret = fchdir(newfd);
1869 __set_errno (oerrno);