1 /* Traverse a file hierarchy.
3 Copyright (C) 2004, 2005 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 size_t fts_pathlen; /* sizeof(path) */
77 size_t fts_nitems; /* elements in the sort array */
78 int (*fts_compar) (struct _ftsent const **, struct _ftsent const **);
81 # define FTS_COMFOLLOW 0x0001 /* follow command line symlinks */
82 # define FTS_LOGICAL 0x0002 /* logical walk */
83 # define FTS_NOCHDIR 0x0004 /* don't change directories */
84 # define FTS_NOSTAT 0x0008 /* don't get stat info */
85 # define FTS_PHYSICAL 0x0010 /* physical walk */
86 # define FTS_SEEDOT 0x0020 /* return dot and dot-dot */
87 # define FTS_XDEV 0x0040 /* don't cross devices */
88 # define FTS_WHITEOUT 0x0080 /* return whiteout information */
90 /* There are two ways to detect cycles.
91 The lazy way (which works only with FTS_PHYSICAL),
92 with which one may process a directory that is a
93 part of the cycle several times before detecting the cycle.
94 The `tight' way, whereby fts uses more memory (proportional
95 to number of `active' directories, aka distance from root
96 of current tree to current directory -- see active_dir_ht)
97 to detect any cycle right away. For example, du must use
98 this option to avoid counting disk space in a cycle multiple
99 times, but chown -R need not.
100 The default is to use the constant-memory lazy way, when possible
103 However, with FTS_LOGICAL (when following symlinks, e.g., chown -L)
104 using lazy cycle detection is inadequate. For example, traversing
105 a directory containing a symbolic link to a peer directory, it is
106 possible to encounter the same directory twice even though there
111 So, when FTS_LOGICAL is selected, we have to use a different
112 mode of cycle detection: FTS_TIGHT_CYCLE_CHECK. */
113 # define FTS_TIGHT_CYCLE_CHECK 0x0100
115 # define FTS_OPTIONMASK 0x01ff /* valid user option mask */
117 # define FTS_NAMEONLY 0x1000 /* (private) child names only */
118 # define FTS_STOP 0x2000 /* (private) unrecoverable error */
119 int fts_options; /* fts_open options, global flags */
123 /* This data structure is used if FTS_TIGHT_CYCLE_CHECK is
124 specified. It records the directories between a starting
125 point and the current directory. I.e., a directory is
126 recorded here IFF we have visited it once, but we have not
127 yet completed processing of all its entries. Every time we
128 visit a new directory, we add that directory to this set.
129 When we finish with a directory (usually by visiting it a
130 second time), we remove it from this set. Each entry in
131 this data structure is a device/inode pair. This data
132 structure is used to detect directory cycles efficiently and
133 promptly even when the depth of a hierarchy is in the tens
135 struct hash_table *ht;
137 /* This data structure uses lazy checking, as done by rm via
138 cycle-check.c. It's the default, but it's not appropriate
139 for programs like du. */
140 struct cycle_check_state *state;
145 typedef struct _ftsent {
146 struct _ftsent *fts_cycle; /* cycle node */
147 struct _ftsent *fts_parent; /* parent directory */
148 struct _ftsent *fts_link; /* next file in directory */
149 long fts_number; /* local numeric value */
150 void *fts_pointer; /* local address value */
151 char *fts_accpath; /* access file name */
152 char *fts_path; /* root name; == fts_fts->fts_path */
153 int fts_errno; /* errno for this node */
154 int fts_symfd; /* fd for symlink */
155 size_t fts_pathlen; /* strlen(fts_path) */
157 FTS *fts_fts; /* the file hierarchy itself */
159 # define FTS_ROOTPARENTLEVEL (-1)
160 # define FTS_ROOTLEVEL 0
161 ptrdiff_t fts_level; /* depth (-1 to N) */
163 size_t fts_namelen; /* strlen(fts_name) */
165 # define FTS_D 1 /* preorder directory */
166 # define FTS_DC 2 /* directory that causes cycles */
167 # define FTS_DEFAULT 3 /* none of the above */
168 # define FTS_DNR 4 /* unreadable directory */
169 # define FTS_DOT 5 /* dot or dot-dot */
170 # define FTS_DP 6 /* postorder directory */
171 # define FTS_ERR 7 /* error; errno is set */
172 # define FTS_F 8 /* regular file */
173 # define FTS_INIT 9 /* initialized only */
174 # define FTS_NS 10 /* stat(2) failed */
175 # define FTS_NSOK 11 /* no stat(2) requested */
176 # define FTS_SL 12 /* symbolic link */
177 # define FTS_SLNONE 13 /* symbolic link without target */
178 # define FTS_W 14 /* whiteout object */
179 unsigned short int fts_info; /* user flags for FTSENT structure */
181 # define FTS_DONTCHDIR 0x01 /* don't chdir .. to the parent */
182 # define FTS_SYMFOLLOW 0x02 /* followed a symlink to get here */
183 unsigned short int fts_flags; /* private flags for FTSENT structure */
185 # define FTS_AGAIN 1 /* read node again */
186 # define FTS_FOLLOW 2 /* follow symbolic link */
187 # define FTS_NOINSTR 3 /* no instructions */
188 # define FTS_SKIP 4 /* discard node */
189 unsigned short int fts_instr; /* fts_set() instructions */
191 struct stat fts_statp[1]; /* stat(2) information */
192 char fts_name[1]; /* file name */
196 FTSENT *fts_children (FTS *, int) __THROW;
197 int fts_close (FTS *) __THROW;
198 FTS *fts_open (char * const *, int,
199 int (*)(const FTSENT **, const FTSENT **)) __THROW;
200 FTSENT *fts_read (FTS *) __THROW;
201 int fts_set (FTS *, FTSENT *, int) __THROW;