1/* File tree traversal functions declarations.
2 Copyright (C) 1994-2026 Free Software Foundation, Inc.
3 This file is part of the GNU C Library.
4
5 The GNU C Library is free software; you can redistribute it and/or
6 modify it under the terms of the GNU Lesser General Public
7 License as published by the Free Software Foundation; either
8 version 2.1 of the License, or (at your option) any later version.
9
10 The GNU C Library 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 GNU
13 Lesser General Public License for more details.
14
15 You should have received a copy of the GNU Lesser General Public
16 License along with the GNU C Library; if not, see
17 <https://www.gnu.org/licenses/>. */
18
19/*
20 * Copyright (c) 1989, 1993
21 * The Regents of the University of California. All rights reserved.
22 *
23 * Redistribution and use in source and binary forms, with or without
24 * modification, are permitted provided that the following conditions
25 * are met:
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.
34 *
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
45 * SUCH DAMAGE.
46 *
47 * @(#)fts.h 8.3 (Berkeley) 8/14/94
48 */
49
50#ifndef _FTS_H
51#define _FTS_H 1
52
53#include <features.h>
54#include <sys/types.h>
55#include <sys/stat.h>
56#include <dirent.h>
57#include <stdbool.h>
58
59enum { __I_RING_SIZE = 4 };
60
61/* When ir_empty is true, the ring is empty.
62 Otherwise, ir_data[B..F] are defined, where B..F is the contiguous
63 range of indices, modulo I_RING_SIZE, from back to front, inclusive.
64 Undefined elements of ir_data are always set to ir_default_val.
65 Popping from an empty ring aborts.
66 Pushing onto a full ring returns the displaced value.
67 An empty ring has F==B and ir_empty == true.
68 A ring with one entry still has F==B, but now ir_empty == false. */
69struct __I_ring
70{
71 int ir_data[__I_RING_SIZE];
72 int ir_default_val;
73 unsigned int ir_front;
74 unsigned int ir_back;
75 bool ir_empty;
76};
77typedef struct __I_ring __I_ring;
78
79typedef struct {
80 struct _ftsent *fts_cur; /* current node */
81 struct _ftsent *fts_child; /* linked list of children */
82 struct _ftsent **fts_array; /* sort array */
83 dev_t fts_dev; /* starting device # */
84 char *fts_path; /* path for this descent */
85 int fts_rfd; /* fd for root */
86 int fts_pathlen; /* sizeof(path) */
87 int fts_nitems; /* elements in the sort array */
88 int (*fts_compar) (const void *, const void *); /* compare fn */
89
90#define FTS_COMFOLLOW 0x0001 /* follow command line symlinks */
91#define FTS_LOGICAL 0x0002 /* logical walk */
92#define FTS_NOCHDIR 0x0004 /* don't change directories */
93#define FTS_NOSTAT 0x0008 /* don't get stat info */
94#define FTS_PHYSICAL 0x0010 /* physical walk */
95#define FTS_SEEDOT 0x0020 /* return dot and dot-dot */
96#define FTS_XDEV 0x0040 /* don't cross devices */
97#define FTS_WHITEOUT 0x0080 /* return whiteout information */
98
99 /* There are two ways to detect cycles.
100 The lazy way (which works only with FTS_PHYSICAL),
101 with which one may process a directory that is a
102 part of the cycle several times before detecting the cycle.
103 The "tight" way, whereby fts uses more memory (proportional
104 to number of "active" directories, aka distance from root
105 of current tree to current directory -- see active_dir_ht)
106 to detect any cycle right away. For example, du must use
107 this option to avoid counting disk space in a cycle multiple
108 times, but chown -R need not.
109 The default is to use the constant-memory lazy way, when possible
110 (see below).
111
112 However, with FTS_LOGICAL (when following symlinks, e.g., chown -L)
113 using lazy cycle detection is inadequate. For example, traversing
114 a directory containing a symbolic link to a peer directory, it is
115 possible to encounter the same directory twice even though there
116 is no cycle:
117 dir
118 ...
119 slink -> dir
120 So, when FTS_LOGICAL is selected, we have to use a different
121 mode of cycle detection: FTS_TIGHT_CYCLE_CHECK. */
122#define FTS_TIGHT_CYCLE_CHECK 0x0400
123
124 /* Use this flag to enable semantics with which the parent
125 application may be made both more efficient and more robust.
126 Whereas the default is to visit each directory in a recursive
127 traversal (via chdir), using this flag makes it so the initial
128 working directory is never changed. Instead, these functions
129 perform the traversal via a virtual working directory, maintained
130 through the file descriptor member, fts_cwd_fd. */
131# define FTS_CWDFD 0x0800
132
133 /* Historically, for each directory that fts initially encounters, it would
134 open it, read all entries, and stat each entry, storing the results, and
135 then it would process the first entry. But that behavior is bad for
136 locality of reference, and also causes trouble with inode-simulating
137 file systems like FAT, CIFS, FUSE-based ones, etc., when entries from
138 their name/inode cache are flushed too early.
139 Use this flag to make fts_open and fts_read defer the stat/lstat/fststat
140 of each entry until it is actually processed. However, note that if you
141 use this option and also specify a comparison function, that function may
142 not examine any data via fts_statp. However, when fts_statp->st_mode is
143 nonzero, the S_IFMT type bits are valid, with mapped dirent.d_type data.
144 Of course, that happens only on file systems that provide useful
145 dirent.d_type data. */
146#define FTS_DEFER_STAT 0x1000
147
148 /* Use this flag to disable stripping of trailing slashes
149 from input path names during fts_open initialization. */
150#define FTS_VERBATIM 0x2000
151
152#define FTS_MOUNT 0x4000 /* skip other devices */
153#define FTS_OPTIONMASK 0x7fff /* valid user option mask */
154
155#define FTS_NAMEONLY 0x0100 /* (private) child names only */
156#define FTS_STOP 0x0200 /* (private) unrecoverable error */
157
158 int fts_options; /* fts_open options, global flags */
159
160 int fts_cwd_fd; /* the file descriptor on which the
161 virtual cwd is open, or AT_FDCWD */
162
163 /* Map a directory's device number to a boolean. The boolean is
164 true if for that file system (type determined by a single fstatfs
165 call per FS) st_nlink can be used to calculate the number of
166 sub-directory entries in a directory.
167 Using this table is an optimization that permits us to look up
168 file system type on a per-inode basis at the minimal cost of
169 calling fstatfs only once per traversed device. */
170 struct hash_table *fts_leaf_optimization_works_ht;
171
172 union {
173 /* This data structure is used if FTS_TIGHT_CYCLE_CHECK is
174 specified. It records the directories between a starting
175 point and the current directory. I.e., a directory is
176 recorded here IFF we have visited it once, but we have not
177 yet completed processing of all its entries. Every time we
178 visit a new directory, we add that directory to this set.
179 When we finish with a directory (usually by visiting it a
180 second time), we remove it from this set. Each entry in
181 this data structure is a device/inode pair. This data
182 structure is used to detect directory cycles efficiently and
183 promptly even when the depth of a hierarchy is in the tens
184 of thousands. */
185 struct hash_table *ht;
186
187 /* FIXME: rename these two members to have the fts_ prefix */
188 /* This data structure uses a lazy cycle-detection algorithm,
189 as done by rm via cycle-check.c. It's the default,
190 but it's not appropriate for programs like du. */
191 struct cycle_check_state *state;
192 } fts_cycle;
193
194 /* A stack of the file descriptors corresponding to the
195 most-recently traversed parent directories.
196 Currently used only in FTS_CWDFD mode. */
197 __I_ring fts_fd_ring;
198} FTS;
199
200#ifdef __USE_LARGEFILE64
201typedef struct {
202 struct _ftsent64 *fts_cur; /* current node */
203 struct _ftsent64 *fts_child; /* linked list of children */
204 struct _ftsent64 **fts_array; /* sort array */
205 dev_t fts_dev; /* starting device # */
206 char *fts_path; /* path for this descent */
207 int fts_rfd; /* fd for root */
208 int fts_pathlen; /* sizeof(path) */
209 int fts_nitems; /* elements in the sort array */
210 int (*fts_compar) (const void *, const void *); /* compare fn */
211 int fts_options; /* fts_open options, global flags */
212 int fts_cwd_fd;
213 struct hash_table *fts_leaf_optimization_works_ht;
214 union {
215 struct hash_table *ht;
216 struct cycle_check_state *state;
217 } fts_cycle;
218 __I_ring fts_fd_ring;
219} FTS64;
220#endif
221
222typedef struct _ftsent {
223 struct _ftsent *fts_cycle; /* cycle node */
224 struct _ftsent *fts_parent; /* parent directory */
225 struct _ftsent *fts_link; /* next file in directory */
226 long fts_number; /* local numeric value */
227 void *fts_pointer; /* local address value */
228 char *fts_accpath; /* access path */
229 char *fts_path; /* root path */
230 int fts_errno; /* errno for this node */
231 int fts_symfd; /* fd for symlink */
232 unsigned short fts_pathlen; /* strlen(fts_path) */
233 unsigned short fts_namelen; /* strlen(fts_name) */
234
235 ino_t fts_ino; /* inode */
236 dev_t fts_dev; /* device */
237 nlink_t fts_nlink; /* link count */
238
239#define FTS_ROOTPARENTLEVEL -1
240#define FTS_ROOTLEVEL 0
241 short fts_level; /* depth (-1 to N) */
242
243#define FTS_D 1 /* preorder directory */
244#define FTS_DC 2 /* directory that causes cycles */
245#define FTS_DEFAULT 3 /* none of the above */
246#define FTS_DNR 4 /* unreadable directory */
247#define FTS_DOT 5 /* dot or dot-dot */
248#define FTS_DP 6 /* postorder directory */
249#define FTS_ERR 7 /* error; errno is set */
250#define FTS_F 8 /* regular file */
251#define FTS_INIT 9 /* initialized only */
252#define FTS_NS 10 /* stat(2) failed */
253#define FTS_NSOK 11 /* no stat(2) requested */
254#define FTS_SL 12 /* symbolic link */
255#define FTS_SLNONE 13 /* symbolic link without target */
256#define FTS_W 14 /* whiteout object */
257 unsigned short fts_info; /* user flags for FTSENT structure */
258
259#define FTS_DONTCHDIR 0x01 /* don't chdir .. to the parent */
260#define FTS_SYMFOLLOW 0x02 /* followed a symlink to get here */
261 unsigned short fts_flags; /* private flags for FTSENT structure */
262
263#define FTS_AGAIN 1 /* read node again */
264#define FTS_FOLLOW 2 /* follow symbolic link */
265#define FTS_NOINSTR 3 /* no instructions */
266#define FTS_SKIP 4 /* discard node */
267 unsigned short fts_instr; /* fts_set() instructions */
268
269 struct stat *fts_statp; /* stat(2) information */
270 char fts_name[1]; /* file name */
271} FTSENT;
272
273#ifdef __USE_LARGEFILE64
274// zig patch: 64bits variants appeared starting from glibc 2.23
275# if (__GLIBC__ == 2 && __GLIBC_MINOR__ >= 23) || __GLIBC__ > 2
276typedef struct _ftsent64 {
277 struct _ftsent64 *fts_cycle; /* cycle node */
278 struct _ftsent64 *fts_parent; /* parent directory */
279 struct _ftsent64 *fts_link; /* next file in directory */
280 long fts_number; /* local numeric value */
281 void *fts_pointer; /* local address value */
282 char *fts_accpath; /* access path */
283 char *fts_path; /* root path */
284 int fts_errno; /* errno for this node */
285 int fts_symfd; /* fd for symlink */
286 unsigned short fts_pathlen; /* strlen(fts_path) */
287 unsigned short fts_namelen; /* strlen(fts_name) */
288
289 ino64_t fts_ino; /* inode */
290 dev_t fts_dev; /* device */
291 nlink_t fts_nlink; /* link count */
292
293 short fts_level; /* depth (-1 to N) */
294
295 unsigned short fts_info; /* user flags for FTSENT structure */
296
297 unsigned short fts_flags; /* private flags for FTSENT structure */
298
299 unsigned short fts_instr; /* fts_set() instructions */
300
301 struct stat64 *fts_statp; /* stat(2) information */
302 char fts_name[1]; /* file name */
303} FTSENT64;
304# endif
305#endif
306
307__BEGIN_DECLS
308
309// zig patch: 64bits variants appeared starting from glibc 2.23
310// before that version, we can't declare nor redirect to them
311#if (__GLIBC__ == 2 && __GLIBC_MINOR__ >= 23) || __GLIBC__ > 2
312
313#ifndef __USE_FILE_OFFSET64
314FTSENT *fts_children (FTS *, int);
315int fts_close (FTS *);
316FTS *fts_open (char * const *, int,
317 int (*)(const FTSENT **, const FTSENT **));
318FTSENT *fts_read (FTS *);
319int fts_set (FTS *, FTSENT *, int) __THROW;
320#else
321# ifdef __REDIRECT
322# ifndef __USE_TIME64_REDIRECTS
323FTSENT *__REDIRECT (fts_children, (FTS *, int), fts64_children);
324int __REDIRECT (fts_close, (FTS *), fts64_close);
325FTS *__REDIRECT (fts_open, (char * const *, int,
326 int (*)(const FTSENT **, const FTSENT **)),
327 fts64_open);
328FTSENT *__REDIRECT (fts_read, (FTS *), fts64_read);
329int __REDIRECT_NTH (fts_set, (FTS *, FTSENT *, int), fts64_set);
330# else
331FTSENT *__REDIRECT (fts_children, (FTS *, int), __fts64_children_time64);
332int __REDIRECT (fts_close, (FTS *), __fts64_close_time64);
333FTS *__REDIRECT (fts_open, (char * const *, int,
334 int (*)(const FTSENT **, const FTSENT **)),
335 __fts64_open_time64);
336FTSENT *__REDIRECT (fts_read, (FTS *), __fts64_read_time64);
337int __REDIRECT_NTH (fts_set, (FTS *, FTSENT *, int),
338 __fts64_set_time64);
339# endif
340# else
341# ifndef __USE_TIME64_REDIRECTS
342# define fts_children fts64_children
343# define fts_close fts64_close
344# define fts_open fts64_open
345# define fts_read fts64_read
346# define fts_set fts64_set
347# else
348# endif
349# endif
350#endif
351#else /* (__GLIBC__ == 2 && __GLIBC_MINOR__ >= 23) || __GLIBC__ > 2 */
352FTSENT *fts_children (FTS *, int);
353int fts_close (FTS *);
354FTS *fts_open (char * const *, int,
355 int (*)(const FTSENT **, const FTSENT **));
356FTSENT *fts_read (FTS *);
357int fts_set (FTS *, FTSENT *, int) __THROW;
358#endif
359
360// zig patch: 64bits time variants appeared starting from glibc 2.34
361// before that version, there is nothing to declare
362#if (__GLIBC__ == 2 && __GLIBC_MINOR__ >= 34) || __GLIBC__ > 2
363
364#ifdef __USE_LARGEFILE64
365# ifndef __USE_TIME64_REDIRECTS
366FTSENT64 *fts64_children (FTS64 *, int);
367int fts64_close (FTS64 *);
368FTS64 *fts64_open (char * const *, int,
369 int (*)(const FTSENT64 **, const FTSENT64 **));
370FTSENT64 *fts64_read (FTS64 *);
371int fts64_set (FTS64 *, FTSENT64 *, int) __THROW;
372# else
373# ifdef __REDIRECT
374FTSENT *__REDIRECT (fts64_children, (FTS64 *, int), __fts64_children_time64);
375int __REDIRECT (fts64_close, (FTS64 *), __fts64_close_time64);
376FTS *__REDIRECT (fts64_open, (char * const *, int,
377 int (*)(const FTSENT64 **, const FTSENT64 **)),
378 __fts64_open_time64);
379FTSENT *__REDIRECT (fts64_read, (FTS64 *), __fts64_read_time64);
380int __REDIRECT_NTH (fts64_set, (FTS64 *, FTSENT64 *, int),
381 __fts64_set_time64);
382# else
383# define fts_children __fts64_children_time64
384# define fts_close __fts64_close_time64
385# define fts_open __fts64_open_time64
386# define fts_read __fts64_read_time64
387# define fts_set __fts64_set_time64
388# endif
389# endif
390#endif
391
392#endif /* (__GLIBC__ == 2 && __GLIBC_MINOR__ >= 34) || __GLIBC__ > 2 */
393__END_DECLS
394
395#endif /* fts.h */