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) 1989, 1993
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
47 * @(#)fts.h 8.3 (Berkeley) 8/14/94
54 # include <features.h>
55 # define _LGPL_PACKAGE 1
60 # define __BEGIN_DECLS
66 # include <sys/types.h>
67 # include <sys/stat.h>
70 struct _ftsent *fts_cur; /* current node */
71 struct _ftsent *fts_child; /* linked list of children */
72 struct _ftsent **fts_array; /* sort array */
73 dev_t fts_dev; /* starting device # */
74 char *fts_path; /* file name for this descent */
75 int fts_rfd; /* fd for root */
76 int fts_cwd_fd; /* the file descriptor on which the
77 virtual cwd is open, or AT_FDCWD */
78 size_t fts_pathlen; /* sizeof(path) */
79 size_t fts_nitems; /* elements in the sort array */
80 int (*fts_compar) (struct _ftsent const **, struct _ftsent const **);
83 # define FTS_COMFOLLOW 0x0001 /* follow command line symlinks */
84 # define FTS_LOGICAL 0x0002 /* logical walk */
85 # define FTS_NOCHDIR 0x0004 /* don't change directories */
86 # define FTS_NOSTAT 0x0008 /* don't get stat info */
87 # define FTS_PHYSICAL 0x0010 /* physical walk */
88 # define FTS_SEEDOT 0x0020 /* return dot and dot-dot */
89 # define FTS_XDEV 0x0040 /* don't cross devices */
90 # define FTS_WHITEOUT 0x0080 /* return whiteout information */
92 /* There are two ways to detect cycles.
93 The lazy way (which works only with FTS_PHYSICAL),
94 with which one may process a directory that is a
95 part of the cycle several times before detecting the cycle.
96 The `tight' way, whereby fts uses more memory (proportional
97 to number of `active' directories, aka distance from root
98 of current tree to current directory -- see active_dir_ht)
99 to detect any cycle right away. For example, du must use
100 this option to avoid counting disk space in a cycle multiple
101 times, but chown -R need not.
102 The default is to use the constant-memory lazy way, when possible
105 However, with FTS_LOGICAL (when following symlinks, e.g., chown -L)
106 using lazy cycle detection is inadequate. For example, traversing
107 a directory containing a symbolic link to a peer directory, it is
108 possible to encounter the same directory twice even though there
113 So, when FTS_LOGICAL is selected, we have to use a different
114 mode of cycle detection: FTS_TIGHT_CYCLE_CHECK. */
115 # define FTS_TIGHT_CYCLE_CHECK 0x0100
117 /* Use this flag to enable semantics with which the parent
118 application may be made both more efficient and more robust.
119 Whereas the default is to visit each directory in a recursive
120 traversal (via chdir), using this flag makes it so the initial
121 working directory is never changed. Instead, these functions
122 perform the traversal via a virtual working directory, maintained
123 through the file descriptor member, fts_cwd_fd. */
124 # define FTS_CWDFD 0x0200
126 # define FTS_OPTIONMASK 0x03ff /* valid user option mask */
128 # define FTS_NAMEONLY 0x1000 /* (private) child names only */
129 # define FTS_STOP 0x2000 /* (private) unrecoverable error */
130 int fts_options; /* fts_open options, global flags */
134 /* This data structure is used if FTS_TIGHT_CYCLE_CHECK is
135 specified. It records the directories between a starting
136 point and the current directory. I.e., a directory is
137 recorded here IFF we have visited it once, but we have not
138 yet completed processing of all its entries. Every time we
139 visit a new directory, we add that directory to this set.
140 When we finish with a directory (usually by visiting it a
141 second time), we remove it from this set. Each entry in
142 this data structure is a device/inode pair. This data
143 structure is used to detect directory cycles efficiently and
144 promptly even when the depth of a hierarchy is in the tens
146 struct hash_table *ht;
148 /* FIXME: rename these two members to have the fts_ prefix */
149 /* This data structure uses a lazy cycle-detection algorithm,
150 as done by rm via cycle-check.c. It's the default,
151 but it's not appropriate for programs like du. */
152 struct cycle_check_state *state;
157 typedef struct _ftsent {
158 struct _ftsent *fts_cycle; /* cycle node */
159 struct _ftsent *fts_parent; /* parent directory */
160 struct _ftsent *fts_link; /* next file in directory */
161 long fts_number; /* local numeric value */
162 void *fts_pointer; /* local address value */
163 char *fts_accpath; /* access file name */
164 char *fts_path; /* root name; == fts_fts->fts_path */
165 int fts_errno; /* errno for this node */
166 int fts_symfd; /* fd for symlink */
167 size_t fts_pathlen; /* strlen(fts_path) */
169 FTS *fts_fts; /* the file hierarchy itself */
171 # define FTS_ROOTPARENTLEVEL (-1)
172 # define FTS_ROOTLEVEL 0
173 ptrdiff_t fts_level; /* depth (-1 to N) */
175 size_t fts_namelen; /* strlen(fts_name) */
177 # define FTS_D 1 /* preorder directory */
178 # define FTS_DC 2 /* directory that causes cycles */
179 # define FTS_DEFAULT 3 /* none of the above */
180 # define FTS_DNR 4 /* unreadable directory */
181 # define FTS_DOT 5 /* dot or dot-dot */
182 # define FTS_DP 6 /* postorder directory */
183 # define FTS_ERR 7 /* error; errno is set */
184 # define FTS_F 8 /* regular file */
185 # define FTS_INIT 9 /* initialized only */
186 # define FTS_NS 10 /* stat(2) failed */
187 # define FTS_NSOK 11 /* no stat(2) requested */
188 # define FTS_SL 12 /* symbolic link */
189 # define FTS_SLNONE 13 /* symbolic link without target */
190 # define FTS_W 14 /* whiteout object */
191 unsigned short int fts_info; /* user flags for FTSENT structure */
193 # define FTS_DONTCHDIR 0x01 /* don't chdir .. to the parent */
194 # define FTS_SYMFOLLOW 0x02 /* followed a symlink to get here */
195 unsigned short int fts_flags; /* private flags for FTSENT structure */
197 # define FTS_AGAIN 1 /* read node again */
198 # define FTS_FOLLOW 2 /* follow symbolic link */
199 # define FTS_NOINSTR 3 /* no instructions */
200 # define FTS_SKIP 4 /* discard node */
201 unsigned short int fts_instr; /* fts_set() instructions */
203 struct stat fts_statp[1]; /* stat(2) information */
204 char fts_name[1]; /* file name */
208 FTSENT *fts_children (FTS *, int) __THROW;
209 int fts_close (FTS *) __THROW;
210 FTS *fts_open (char * const *, int,
211 int (*)(const FTSENT **, const FTSENT **)) __THROW;
212 FTSENT *fts_read (FTS *) __THROW;
213 int fts_set (FTS *, FTSENT *, int) __THROW;