1/*-
2 * Copyright (c) 1990, 1993, 1994
3 * The Regents of the University of California. All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 * 3. All advertising materials mentioning features or use of this software
14 * must display the following acknowledgement:
15 * This product includes software developed by the University of
16 * California, Berkeley and its contributors.
17 * 4. Neither the name of the University nor the names of its contributors
18 * may be used to endorse or promote products derived from this software
19 * without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
22 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
25 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
31 * SUCH DAMAGE.
32 */
33
34#if defined(LIBC_SCCS) && !defined(lint)
35static char sccsid[] = "@(#)fts.c 8.4 (Berkeley) 4/16/94";
36#endif /* LIBC_SCCS and not lint */
37
38#include <sys/param.h>
39#include <sys/stat.h>
40
41#include <dirent.h>
42#include <errno.h>
43#include <fcntl.h>
44#include <fts.h>
45#include <stdlib.h>
46#include <string.h>
47#include <unistd.h>
48
49static FTSENT *fts_alloc __P((FTS *, char *, int));
50static FTSENT *fts_build __P((FTS *, int));
51static void fts_lfree __P((FTSENT *));
52static void fts_load __P((FTS *, FTSENT *));
53static size_t fts_maxarglen __P((char * const *));
54static void fts_padjust __P((FTS *, void *));
55static int fts_palloc __P((FTS *, size_t));
56static FTSENT *fts_sort __P((FTS *, FTSENT *, int));
57static u_short fts_stat __P((FTS *, FTSENT *, int));
58
| 1/*-
2 * Copyright (c) 1990, 1993, 1994
3 * The Regents of the University of California. All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 * 3. All advertising materials mentioning features or use of this software
14 * must display the following acknowledgement:
15 * This product includes software developed by the University of
16 * California, Berkeley and its contributors.
17 * 4. Neither the name of the University nor the names of its contributors
18 * may be used to endorse or promote products derived from this software
19 * without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
22 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
25 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
31 * SUCH DAMAGE.
32 */
33
34#if defined(LIBC_SCCS) && !defined(lint)
35static char sccsid[] = "@(#)fts.c 8.4 (Berkeley) 4/16/94";
36#endif /* LIBC_SCCS and not lint */
37
38#include <sys/param.h>
39#include <sys/stat.h>
40
41#include <dirent.h>
42#include <errno.h>
43#include <fcntl.h>
44#include <fts.h>
45#include <stdlib.h>
46#include <string.h>
47#include <unistd.h>
48
49static FTSENT *fts_alloc __P((FTS *, char *, int));
50static FTSENT *fts_build __P((FTS *, int));
51static void fts_lfree __P((FTSENT *));
52static void fts_load __P((FTS *, FTSENT *));
53static size_t fts_maxarglen __P((char * const *));
54static void fts_padjust __P((FTS *, void *));
55static int fts_palloc __P((FTS *, size_t));
56static FTSENT *fts_sort __P((FTS *, FTSENT *, int));
57static u_short fts_stat __P((FTS *, FTSENT *, int));
58
|
59#define ISDOT(a) (a[0] == '.' && (!a[1] || a[1] == '.' && !a[2]))
| 59#define ISDOT(a) (a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2])) )
|
60
61#define ISSET(opt) (sp->fts_options & opt)
62#define SET(opt) (sp->fts_options |= opt)
63
64#define CHDIR(sp, path) (!ISSET(FTS_NOCHDIR) && chdir(path))
65#define FCHDIR(sp, fd) (!ISSET(FTS_NOCHDIR) && fchdir(fd))
66
67/* fts_build flags */
68#define BCHILD 1 /* fts_children */
69#define BNAMES 2 /* fts_children, names only */
70#define BREAD 3 /* fts_read */
71
72FTS *
73fts_open(argv, options, compar)
74 char * const *argv;
75 register int options;
76 int (*compar)();
77{
78 register FTS *sp;
79 register FTSENT *p, *root;
80 register int nitems;
81 FTSENT *parent, *tmp;
82 int len;
83
84 /* Options check. */
85 if (options & ~FTS_OPTIONMASK) {
86 errno = EINVAL;
87 return (NULL);
88 }
89
90 /* Allocate/initialize the stream */
91 if ((sp = malloc((u_int)sizeof(FTS))) == NULL)
92 return (NULL);
93 memset(sp, 0, sizeof(FTS));
94 sp->fts_compar = compar;
95 sp->fts_options = options;
96
97 /* Logical walks turn on NOCHDIR; symbolic links are too hard. */
98 if (ISSET(FTS_LOGICAL))
99 SET(FTS_NOCHDIR);
100
101 /*
102 * Start out with 1K of path space, and enough, in any case,
103 * to hold the user's paths.
104 */
105 if (fts_palloc(sp, MAX(fts_maxarglen(argv), MAXPATHLEN)))
106 goto mem1;
107
108 /* Allocate/initialize root's parent. */
109 if ((parent = fts_alloc(sp, "", 0)) == NULL)
110 goto mem2;
111 parent->fts_level = FTS_ROOTPARENTLEVEL;
112
113 /* Allocate/initialize root(s). */
114 for (root = NULL, nitems = 0; *argv; ++argv, ++nitems) {
115 /* Don't allow zero-length paths. */
116 if ((len = strlen(*argv)) == 0) {
117 errno = ENOENT;
118 goto mem3;
119 }
120
121 p = fts_alloc(sp, *argv, len);
122 p->fts_level = FTS_ROOTLEVEL;
123 p->fts_parent = parent;
124 p->fts_accpath = p->fts_name;
125 p->fts_info = fts_stat(sp, p, ISSET(FTS_COMFOLLOW));
126
127 /* Command-line "." and ".." are real directories. */
128 if (p->fts_info == FTS_DOT)
129 p->fts_info = FTS_D;
130
131 /*
132 * If comparison routine supplied, traverse in sorted
133 * order; otherwise traverse in the order specified.
134 */
135 if (compar) {
136 p->fts_link = root;
137 root = p;
138 } else {
139 p->fts_link = NULL;
140 if (root == NULL)
141 tmp = root = p;
142 else {
143 tmp->fts_link = p;
144 tmp = p;
145 }
146 }
147 }
148 if (compar && nitems > 1)
149 root = fts_sort(sp, root, nitems);
150
151 /*
152 * Allocate a dummy pointer and make fts_read think that we've just
153 * finished the node before the root(s); set p->fts_info to FTS_INIT
154 * so that everything about the "current" node is ignored.
155 */
156 if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL)
157 goto mem3;
158 sp->fts_cur->fts_link = root;
159 sp->fts_cur->fts_info = FTS_INIT;
160
161 /*
162 * If using chdir(2), grab a file descriptor pointing to dot to insure
163 * that we can get back here; this could be avoided for some paths,
164 * but almost certainly not worth the effort. Slashes, symbolic links,
165 * and ".." are all fairly nasty problems. Note, if we can't get the
166 * descriptor we run anyway, just more slowly.
167 */
168 if (!ISSET(FTS_NOCHDIR) && (sp->fts_rfd = open(".", O_RDONLY, 0)) < 0)
169 SET(FTS_NOCHDIR);
170
171 return (sp);
172
173mem3: fts_lfree(root);
174 free(parent);
175mem2: free(sp->fts_path);
176mem1: free(sp);
177 return (NULL);
178}
179
180static void
181fts_load(sp, p)
182 FTS *sp;
183 register FTSENT *p;
184{
185 register int len;
186 register char *cp;
187
188 /*
189 * Load the stream structure for the next traversal. Since we don't
190 * actually enter the directory until after the preorder visit, set
191 * the fts_accpath field specially so the chdir gets done to the right
192 * place and the user can access the first node. From fts_open it's
193 * known that the path will fit.
194 */
195 len = p->fts_pathlen = p->fts_namelen;
196 memmove(sp->fts_path, p->fts_name, len + 1);
197 if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) {
198 len = strlen(++cp);
199 memmove(p->fts_name, cp, len + 1);
200 p->fts_namelen = len;
201 }
202 p->fts_accpath = p->fts_path = sp->fts_path;
203 sp->fts_dev = p->fts_dev;
204}
205
206int
207fts_close(sp)
208 FTS *sp;
209{
210 register FTSENT *freep, *p;
211 int saved_errno;
212
213 /*
214 * This still works if we haven't read anything -- the dummy structure
215 * points to the root list, so we step through to the end of the root
216 * list which has a valid parent pointer.
217 */
218 if (sp->fts_cur) {
219 for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {
220 freep = p;
221 p = p->fts_link ? p->fts_link : p->fts_parent;
222 free(freep);
223 }
224 free(p);
225 }
226
227 /* Free up child linked list, sort array, path buffer. */
228 if (sp->fts_child)
229 fts_lfree(sp->fts_child);
230 if (sp->fts_array)
231 free(sp->fts_array);
232 free(sp->fts_path);
233
234 /* Return to original directory, save errno if necessary. */
235 if (!ISSET(FTS_NOCHDIR)) {
236 saved_errno = fchdir(sp->fts_rfd) ? errno : 0;
237 (void)close(sp->fts_rfd);
238 }
239
240 /* Free up the stream pointer. */
241 free(sp);
242
243 /* Set errno and return. */
244 if (!ISSET(FTS_NOCHDIR) && saved_errno) {
245 errno = saved_errno;
246 return (-1);
247 }
248 return (0);
249}
250
251/*
252 * Special case a root of "/" so that slashes aren't appended which would
253 * cause paths to be written as "//foo".
254 */
255#define NAPPEND(p) \
256 (p->fts_level == FTS_ROOTLEVEL && p->fts_pathlen == 1 && \
257 p->fts_path[0] == '/' ? 0 : p->fts_pathlen)
258
259FTSENT *
260fts_read(sp)
261 register FTS *sp;
262{
263 register FTSENT *p, *tmp;
264 register int instr;
265 register char *t;
266 int saved_errno;
267
268 /* If finished or unrecoverable error, return NULL. */
269 if (sp->fts_cur == NULL || ISSET(FTS_STOP))
270 return (NULL);
271
272 /* Set current node pointer. */
273 p = sp->fts_cur;
274
275 /* Save and zero out user instructions. */
276 instr = p->fts_instr;
277 p->fts_instr = FTS_NOINSTR;
278
279 /* Any type of file may be re-visited; re-stat and re-turn. */
280 if (instr == FTS_AGAIN) {
281 p->fts_info = fts_stat(sp, p, 0);
282 return (p);
283 }
284
285 /*
286 * Following a symlink -- SLNONE test allows application to see
287 * SLNONE and recover. If indirecting through a symlink, have
288 * keep a pointer to current location. If unable to get that
289 * pointer, follow fails.
290 */
291 if (instr == FTS_FOLLOW &&
292 (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) {
293 p->fts_info = fts_stat(sp, p, 1);
294 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR))
295 if ((p->fts_symfd = open(".", O_RDONLY, 0)) < 0) {
296 p->fts_errno = errno;
297 p->fts_info = FTS_ERR;
298 } else
299 p->fts_flags |= FTS_SYMFOLLOW;
300 return (p);
301 }
302
303 /* Directory in pre-order. */
304 if (p->fts_info == FTS_D) {
305 /* If skipped or crossed mount point, do post-order visit. */
306 if (instr == FTS_SKIP ||
| 60
61#define ISSET(opt) (sp->fts_options & opt)
62#define SET(opt) (sp->fts_options |= opt)
63
64#define CHDIR(sp, path) (!ISSET(FTS_NOCHDIR) && chdir(path))
65#define FCHDIR(sp, fd) (!ISSET(FTS_NOCHDIR) && fchdir(fd))
66
67/* fts_build flags */
68#define BCHILD 1 /* fts_children */
69#define BNAMES 2 /* fts_children, names only */
70#define BREAD 3 /* fts_read */
71
72FTS *
73fts_open(argv, options, compar)
74 char * const *argv;
75 register int options;
76 int (*compar)();
77{
78 register FTS *sp;
79 register FTSENT *p, *root;
80 register int nitems;
81 FTSENT *parent, *tmp;
82 int len;
83
84 /* Options check. */
85 if (options & ~FTS_OPTIONMASK) {
86 errno = EINVAL;
87 return (NULL);
88 }
89
90 /* Allocate/initialize the stream */
91 if ((sp = malloc((u_int)sizeof(FTS))) == NULL)
92 return (NULL);
93 memset(sp, 0, sizeof(FTS));
94 sp->fts_compar = compar;
95 sp->fts_options = options;
96
97 /* Logical walks turn on NOCHDIR; symbolic links are too hard. */
98 if (ISSET(FTS_LOGICAL))
99 SET(FTS_NOCHDIR);
100
101 /*
102 * Start out with 1K of path space, and enough, in any case,
103 * to hold the user's paths.
104 */
105 if (fts_palloc(sp, MAX(fts_maxarglen(argv), MAXPATHLEN)))
106 goto mem1;
107
108 /* Allocate/initialize root's parent. */
109 if ((parent = fts_alloc(sp, "", 0)) == NULL)
110 goto mem2;
111 parent->fts_level = FTS_ROOTPARENTLEVEL;
112
113 /* Allocate/initialize root(s). */
114 for (root = NULL, nitems = 0; *argv; ++argv, ++nitems) {
115 /* Don't allow zero-length paths. */
116 if ((len = strlen(*argv)) == 0) {
117 errno = ENOENT;
118 goto mem3;
119 }
120
121 p = fts_alloc(sp, *argv, len);
122 p->fts_level = FTS_ROOTLEVEL;
123 p->fts_parent = parent;
124 p->fts_accpath = p->fts_name;
125 p->fts_info = fts_stat(sp, p, ISSET(FTS_COMFOLLOW));
126
127 /* Command-line "." and ".." are real directories. */
128 if (p->fts_info == FTS_DOT)
129 p->fts_info = FTS_D;
130
131 /*
132 * If comparison routine supplied, traverse in sorted
133 * order; otherwise traverse in the order specified.
134 */
135 if (compar) {
136 p->fts_link = root;
137 root = p;
138 } else {
139 p->fts_link = NULL;
140 if (root == NULL)
141 tmp = root = p;
142 else {
143 tmp->fts_link = p;
144 tmp = p;
145 }
146 }
147 }
148 if (compar && nitems > 1)
149 root = fts_sort(sp, root, nitems);
150
151 /*
152 * Allocate a dummy pointer and make fts_read think that we've just
153 * finished the node before the root(s); set p->fts_info to FTS_INIT
154 * so that everything about the "current" node is ignored.
155 */
156 if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL)
157 goto mem3;
158 sp->fts_cur->fts_link = root;
159 sp->fts_cur->fts_info = FTS_INIT;
160
161 /*
162 * If using chdir(2), grab a file descriptor pointing to dot to insure
163 * that we can get back here; this could be avoided for some paths,
164 * but almost certainly not worth the effort. Slashes, symbolic links,
165 * and ".." are all fairly nasty problems. Note, if we can't get the
166 * descriptor we run anyway, just more slowly.
167 */
168 if (!ISSET(FTS_NOCHDIR) && (sp->fts_rfd = open(".", O_RDONLY, 0)) < 0)
169 SET(FTS_NOCHDIR);
170
171 return (sp);
172
173mem3: fts_lfree(root);
174 free(parent);
175mem2: free(sp->fts_path);
176mem1: free(sp);
177 return (NULL);
178}
179
180static void
181fts_load(sp, p)
182 FTS *sp;
183 register FTSENT *p;
184{
185 register int len;
186 register char *cp;
187
188 /*
189 * Load the stream structure for the next traversal. Since we don't
190 * actually enter the directory until after the preorder visit, set
191 * the fts_accpath field specially so the chdir gets done to the right
192 * place and the user can access the first node. From fts_open it's
193 * known that the path will fit.
194 */
195 len = p->fts_pathlen = p->fts_namelen;
196 memmove(sp->fts_path, p->fts_name, len + 1);
197 if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) {
198 len = strlen(++cp);
199 memmove(p->fts_name, cp, len + 1);
200 p->fts_namelen = len;
201 }
202 p->fts_accpath = p->fts_path = sp->fts_path;
203 sp->fts_dev = p->fts_dev;
204}
205
206int
207fts_close(sp)
208 FTS *sp;
209{
210 register FTSENT *freep, *p;
211 int saved_errno;
212
213 /*
214 * This still works if we haven't read anything -- the dummy structure
215 * points to the root list, so we step through to the end of the root
216 * list which has a valid parent pointer.
217 */
218 if (sp->fts_cur) {
219 for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {
220 freep = p;
221 p = p->fts_link ? p->fts_link : p->fts_parent;
222 free(freep);
223 }
224 free(p);
225 }
226
227 /* Free up child linked list, sort array, path buffer. */
228 if (sp->fts_child)
229 fts_lfree(sp->fts_child);
230 if (sp->fts_array)
231 free(sp->fts_array);
232 free(sp->fts_path);
233
234 /* Return to original directory, save errno if necessary. */
235 if (!ISSET(FTS_NOCHDIR)) {
236 saved_errno = fchdir(sp->fts_rfd) ? errno : 0;
237 (void)close(sp->fts_rfd);
238 }
239
240 /* Free up the stream pointer. */
241 free(sp);
242
243 /* Set errno and return. */
244 if (!ISSET(FTS_NOCHDIR) && saved_errno) {
245 errno = saved_errno;
246 return (-1);
247 }
248 return (0);
249}
250
251/*
252 * Special case a root of "/" so that slashes aren't appended which would
253 * cause paths to be written as "//foo".
254 */
255#define NAPPEND(p) \
256 (p->fts_level == FTS_ROOTLEVEL && p->fts_pathlen == 1 && \
257 p->fts_path[0] == '/' ? 0 : p->fts_pathlen)
258
259FTSENT *
260fts_read(sp)
261 register FTS *sp;
262{
263 register FTSENT *p, *tmp;
264 register int instr;
265 register char *t;
266 int saved_errno;
267
268 /* If finished or unrecoverable error, return NULL. */
269 if (sp->fts_cur == NULL || ISSET(FTS_STOP))
270 return (NULL);
271
272 /* Set current node pointer. */
273 p = sp->fts_cur;
274
275 /* Save and zero out user instructions. */
276 instr = p->fts_instr;
277 p->fts_instr = FTS_NOINSTR;
278
279 /* Any type of file may be re-visited; re-stat and re-turn. */
280 if (instr == FTS_AGAIN) {
281 p->fts_info = fts_stat(sp, p, 0);
282 return (p);
283 }
284
285 /*
286 * Following a symlink -- SLNONE test allows application to see
287 * SLNONE and recover. If indirecting through a symlink, have
288 * keep a pointer to current location. If unable to get that
289 * pointer, follow fails.
290 */
291 if (instr == FTS_FOLLOW &&
292 (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) {
293 p->fts_info = fts_stat(sp, p, 1);
294 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR))
295 if ((p->fts_symfd = open(".", O_RDONLY, 0)) < 0) {
296 p->fts_errno = errno;
297 p->fts_info = FTS_ERR;
298 } else
299 p->fts_flags |= FTS_SYMFOLLOW;
300 return (p);
301 }
302
303 /* Directory in pre-order. */
304 if (p->fts_info == FTS_D) {
305 /* If skipped or crossed mount point, do post-order visit. */
306 if (instr == FTS_SKIP ||
|
307 ISSET(FTS_XDEV) && p->fts_dev != sp->fts_dev) {
| 307 (ISSET(FTS_XDEV) && p->fts_dev != sp->fts_dev) ) {
|
308 if (p->fts_flags & FTS_SYMFOLLOW)
309 (void)close(p->fts_symfd);
310 if (sp->fts_child) {
311 fts_lfree(sp->fts_child);
312 sp->fts_child = NULL;
313 }
314 p->fts_info = FTS_DP;
315 return (p);
316 }
317
318 /* Rebuild if only read the names and now traversing. */
319 if (sp->fts_child && sp->fts_options & FTS_NAMEONLY) {
320 sp->fts_options &= ~FTS_NAMEONLY;
321 fts_lfree(sp->fts_child);
322 sp->fts_child = NULL;
323 }
324
325 /*
326 * Cd to the subdirectory.
327 *
328 * If have already read and now fail to chdir, whack the list
329 * to make the names come out right, and set the parent errno
330 * so the application will eventually get an error condition.
331 * Set the FTS_DONTCHDIR flag so that when we logically change
332 * directories back to the parent we don't do a chdir.
333 *
334 * If haven't read do so. If the read fails, fts_build sets
335 * FTS_STOP or the fts_info field of the node.
336 */
337 if (sp->fts_child) {
338 if (CHDIR(sp, p->fts_accpath)) {
339 p->fts_errno = errno;
340 p->fts_flags |= FTS_DONTCHDIR;
341 for (p = sp->fts_child; p; p = p->fts_link)
342 p->fts_accpath =
343 p->fts_parent->fts_accpath;
344 }
345 } else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) {
346 if (ISSET(FTS_STOP))
347 return (NULL);
348 return (p);
349 }
350 p = sp->fts_child;
351 sp->fts_child = NULL;
352 goto name;
353 }
354
355 /* Move to the next node on this level. */
356next: tmp = p;
| 308 if (p->fts_flags & FTS_SYMFOLLOW)
309 (void)close(p->fts_symfd);
310 if (sp->fts_child) {
311 fts_lfree(sp->fts_child);
312 sp->fts_child = NULL;
313 }
314 p->fts_info = FTS_DP;
315 return (p);
316 }
317
318 /* Rebuild if only read the names and now traversing. */
319 if (sp->fts_child && sp->fts_options & FTS_NAMEONLY) {
320 sp->fts_options &= ~FTS_NAMEONLY;
321 fts_lfree(sp->fts_child);
322 sp->fts_child = NULL;
323 }
324
325 /*
326 * Cd to the subdirectory.
327 *
328 * If have already read and now fail to chdir, whack the list
329 * to make the names come out right, and set the parent errno
330 * so the application will eventually get an error condition.
331 * Set the FTS_DONTCHDIR flag so that when we logically change
332 * directories back to the parent we don't do a chdir.
333 *
334 * If haven't read do so. If the read fails, fts_build sets
335 * FTS_STOP or the fts_info field of the node.
336 */
337 if (sp->fts_child) {
338 if (CHDIR(sp, p->fts_accpath)) {
339 p->fts_errno = errno;
340 p->fts_flags |= FTS_DONTCHDIR;
341 for (p = sp->fts_child; p; p = p->fts_link)
342 p->fts_accpath =
343 p->fts_parent->fts_accpath;
344 }
345 } else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) {
346 if (ISSET(FTS_STOP))
347 return (NULL);
348 return (p);
349 }
350 p = sp->fts_child;
351 sp->fts_child = NULL;
352 goto name;
353 }
354
355 /* Move to the next node on this level. */
356next: tmp = p;
|
357 if (p = p->fts_link) {
| 357 if ( (p = p->fts_link) ) {
|
358 free(tmp);
359
360 /*
361 * If reached the top, return to the original directory, and
362 * load the paths for the next root.
363 */
364 if (p->fts_level == FTS_ROOTLEVEL) {
365 if (!ISSET(FTS_NOCHDIR) && FCHDIR(sp, sp->fts_rfd)) {
366 SET(FTS_STOP);
367 return (NULL);
368 }
369 fts_load(sp, p);
370 return (sp->fts_cur = p);
371 }
372
373 /*
374 * User may have called fts_set on the node. If skipped,
375 * ignore. If followed, get a file descriptor so we can
376 * get back if necessary.
377 */
378 if (p->fts_instr == FTS_SKIP)
379 goto next;
380 if (p->fts_instr == FTS_FOLLOW) {
381 p->fts_info = fts_stat(sp, p, 1);
382 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR))
383 if ((p->fts_symfd =
384 open(".", O_RDONLY, 0)) < 0) {
385 p->fts_errno = errno;
386 p->fts_info = FTS_ERR;
387 } else
388 p->fts_flags |= FTS_SYMFOLLOW;
389 p->fts_instr = FTS_NOINSTR;
390 }
391
392name: t = sp->fts_path + NAPPEND(p->fts_parent);
393 *t++ = '/';
394 memmove(t, p->fts_name, p->fts_namelen + 1);
395 return (sp->fts_cur = p);
396 }
397
398 /* Move up to the parent node. */
399 p = tmp->fts_parent;
400 free(tmp);
401
402 if (p->fts_level == FTS_ROOTPARENTLEVEL) {
403 /*
404 * Done; free everything up and set errno to 0 so the user
405 * can distinguish between error and EOF.
406 */
407 free(p);
408 errno = 0;
409 return (sp->fts_cur = NULL);
410 }
411
412 /* Nul terminate the pathname. */
413 sp->fts_path[p->fts_pathlen] = '\0';
414
415 /*
416 * Return to the parent directory. If at a root node or came through
417 * a symlink, go back through the file descriptor. Otherwise, cd up
418 * one directory.
419 */
420 if (p->fts_level == FTS_ROOTLEVEL) {
421 if (!ISSET(FTS_NOCHDIR) && FCHDIR(sp, sp->fts_rfd)) {
422 SET(FTS_STOP);
423 return (NULL);
424 }
425 } else if (p->fts_flags & FTS_SYMFOLLOW) {
426 if (FCHDIR(sp, p->fts_symfd)) {
427 saved_errno = errno;
428 (void)close(p->fts_symfd);
429 errno = saved_errno;
430 SET(FTS_STOP);
431 return (NULL);
432 }
433 (void)close(p->fts_symfd);
434 } else if (!(p->fts_flags & FTS_DONTCHDIR)) {
435 if (CHDIR(sp, "..")) {
436 SET(FTS_STOP);
437 return (NULL);
438 }
439 }
440 p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;
441 return (sp->fts_cur = p);
442}
443
444/*
445 * Fts_set takes the stream as an argument although it's not used in this
446 * implementation; it would be necessary if anyone wanted to add global
447 * semantics to fts using fts_set. An error return is allowed for similar
448 * reasons.
449 */
450/* ARGSUSED */
451int
452fts_set(sp, p, instr)
453 FTS *sp;
454 FTSENT *p;
455 int instr;
456{
457 if (instr && instr != FTS_AGAIN && instr != FTS_FOLLOW &&
458 instr != FTS_NOINSTR && instr != FTS_SKIP) {
459 errno = EINVAL;
460 return (1);
461 }
462 p->fts_instr = instr;
463 return (0);
464}
465
466FTSENT *
467fts_children(sp, instr)
468 register FTS *sp;
469 int instr;
470{
471 register FTSENT *p;
472 int fd;
473
474 if (instr && instr != FTS_NAMEONLY) {
475 errno = EINVAL;
476 return (NULL);
477 }
478
479 /* Set current node pointer. */
480 p = sp->fts_cur;
481
482 /*
483 * Errno set to 0 so user can distinguish empty directory from
484 * an error.
485 */
486 errno = 0;
487
488 /* Fatal errors stop here. */
489 if (ISSET(FTS_STOP))
490 return (NULL);
491
492 /* Return logical hierarchy of user's arguments. */
493 if (p->fts_info == FTS_INIT)
494 return (p->fts_link);
495
496 /*
497 * If not a directory being visited in pre-order, stop here. Could
498 * allow FTS_DNR, assuming the user has fixed the problem, but the
499 * same effect is available with FTS_AGAIN.
500 */
501 if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */)
502 return (NULL);
503
504 /* Free up any previous child list. */
505 if (sp->fts_child)
506 fts_lfree(sp->fts_child);
507
508 if (instr == FTS_NAMEONLY) {
509 sp->fts_options |= FTS_NAMEONLY;
510 instr = BNAMES;
511 } else
512 instr = BCHILD;
513
514 /*
515 * If using chdir on a relative path and called BEFORE fts_read does
516 * its chdir to the root of a traversal, we can lose -- we need to
517 * chdir into the subdirectory, and we don't know where the current
518 * directory is, so we can't get back so that the upcoming chdir by
519 * fts_read will work.
520 */
521 if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' ||
522 ISSET(FTS_NOCHDIR))
523 return (sp->fts_child = fts_build(sp, instr));
524
525 if ((fd = open(".", O_RDONLY, 0)) < 0)
526 return (NULL);
527 sp->fts_child = fts_build(sp, instr);
528 if (fchdir(fd))
529 return (NULL);
530 (void)close(fd);
531 return (sp->fts_child);
532}
533
534/*
535 * This is the tricky part -- do not casually change *anything* in here. The
536 * idea is to build the linked list of entries that are used by fts_children
537 * and fts_read. There are lots of special cases.
538 *
539 * The real slowdown in walking the tree is the stat calls. If FTS_NOSTAT is
540 * set and it's a physical walk (so that symbolic links can't be directories),
541 * we can do things quickly. First, if it's a 4.4BSD file system, the type
542 * of the file is in the directory entry. Otherwise, we assume that the number
543 * of subdirectories in a node is equal to the number of links to the parent.
544 * The former skips all stat calls. The latter skips stat calls in any leaf
545 * directories and for any files after the subdirectories in the directory have
546 * been found, cutting the stat calls by about 2/3.
547 */
548static FTSENT *
549fts_build(sp, type)
550 register FTS *sp;
551 int type;
552{
553 register struct dirent *dp;
554 register FTSENT *p, *head;
555 register int nitems;
556 FTSENT *cur, *tail;
557 DIR *dirp;
558 void *adjaddr;
559 int cderrno, descend, len, level, maxlen, nlinks, saved_errno;
560 char *cp;
561
562 /* Set current node pointer. */
563 cur = sp->fts_cur;
564
565 /*
566 * Open the directory for reading. If this fails, we're done.
567 * If being called from fts_read, set the fts_info field.
568 */
569 if ((dirp = opendir(cur->fts_accpath)) == NULL) {
570 if (type == BREAD) {
571 cur->fts_info = FTS_DNR;
572 cur->fts_errno = errno;
573 }
574 return (NULL);
575 }
576
577 /*
578 * Nlinks is the number of possible entries of type directory in the
579 * directory if we're cheating on stat calls, 0 if we're not doing
580 * any stat calls at all, -1 if we're doing stats on everything.
581 */
582 if (type == BNAMES)
583 nlinks = 0;
584 else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL))
585 nlinks = cur->fts_nlink - (ISSET(FTS_SEEDOT) ? 0 : 2);
586 else
587 nlinks = -1;
588
589#ifdef notdef
590 (void)printf("nlinks == %d (cur: %d)\n", nlinks, cur->fts_nlink);
591 (void)printf("NOSTAT %d PHYSICAL %d SEEDOT %d\n",
592 ISSET(FTS_NOSTAT), ISSET(FTS_PHYSICAL), ISSET(FTS_SEEDOT));
593#endif
594 /*
595 * If we're going to need to stat anything or we want to descend
596 * and stay in the directory, chdir. If this fails we keep going,
597 * but set a flag so we don't chdir after the post-order visit.
598 * We won't be able to stat anything, but we can still return the
599 * names themselves. Note, that since fts_read won't be able to
600 * chdir into the directory, it will have to return different path
601 * names than before, i.e. "a/b" instead of "b". Since the node
602 * has already been visited in pre-order, have to wait until the
603 * post-order visit to return the error. There is a special case
604 * here, if there was nothing to stat then it's not an error to
605 * not be able to stat. This is all fairly nasty. If a program
606 * needed sorted entries or stat information, they had better be
607 * checking FTS_NS on the returned nodes.
608 */
609 cderrno = 0;
610 if (nlinks || type == BREAD)
611 if (FCHDIR(sp, dirfd(dirp))) {
612 if (nlinks && type == BREAD)
613 cur->fts_errno = errno;
614 cur->fts_flags |= FTS_DONTCHDIR;
615 descend = 0;
616 cderrno = errno;
617 } else
618 descend = 1;
619 else
620 descend = 0;
621
622 /*
623 * Figure out the max file name length that can be stored in the
624 * current path -- the inner loop allocates more path as necessary.
625 * We really wouldn't have to do the maxlen calculations here, we
626 * could do them in fts_read before returning the path, but it's a
627 * lot easier here since the length is part of the dirent structure.
628 *
629 * If not changing directories set a pointer so that can just append
630 * each new name into the path.
631 */
632 maxlen = sp->fts_pathlen - cur->fts_pathlen - 1;
633 len = NAPPEND(cur);
634 if (ISSET(FTS_NOCHDIR)) {
635 cp = sp->fts_path + len;
636 *cp++ = '/';
637 }
638
639 level = cur->fts_level + 1;
640
641 /* Read the directory, attaching each entry to the `link' pointer. */
642 adjaddr = NULL;
| 358 free(tmp);
359
360 /*
361 * If reached the top, return to the original directory, and
362 * load the paths for the next root.
363 */
364 if (p->fts_level == FTS_ROOTLEVEL) {
365 if (!ISSET(FTS_NOCHDIR) && FCHDIR(sp, sp->fts_rfd)) {
366 SET(FTS_STOP);
367 return (NULL);
368 }
369 fts_load(sp, p);
370 return (sp->fts_cur = p);
371 }
372
373 /*
374 * User may have called fts_set on the node. If skipped,
375 * ignore. If followed, get a file descriptor so we can
376 * get back if necessary.
377 */
378 if (p->fts_instr == FTS_SKIP)
379 goto next;
380 if (p->fts_instr == FTS_FOLLOW) {
381 p->fts_info = fts_stat(sp, p, 1);
382 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR))
383 if ((p->fts_symfd =
384 open(".", O_RDONLY, 0)) < 0) {
385 p->fts_errno = errno;
386 p->fts_info = FTS_ERR;
387 } else
388 p->fts_flags |= FTS_SYMFOLLOW;
389 p->fts_instr = FTS_NOINSTR;
390 }
391
392name: t = sp->fts_path + NAPPEND(p->fts_parent);
393 *t++ = '/';
394 memmove(t, p->fts_name, p->fts_namelen + 1);
395 return (sp->fts_cur = p);
396 }
397
398 /* Move up to the parent node. */
399 p = tmp->fts_parent;
400 free(tmp);
401
402 if (p->fts_level == FTS_ROOTPARENTLEVEL) {
403 /*
404 * Done; free everything up and set errno to 0 so the user
405 * can distinguish between error and EOF.
406 */
407 free(p);
408 errno = 0;
409 return (sp->fts_cur = NULL);
410 }
411
412 /* Nul terminate the pathname. */
413 sp->fts_path[p->fts_pathlen] = '\0';
414
415 /*
416 * Return to the parent directory. If at a root node or came through
417 * a symlink, go back through the file descriptor. Otherwise, cd up
418 * one directory.
419 */
420 if (p->fts_level == FTS_ROOTLEVEL) {
421 if (!ISSET(FTS_NOCHDIR) && FCHDIR(sp, sp->fts_rfd)) {
422 SET(FTS_STOP);
423 return (NULL);
424 }
425 } else if (p->fts_flags & FTS_SYMFOLLOW) {
426 if (FCHDIR(sp, p->fts_symfd)) {
427 saved_errno = errno;
428 (void)close(p->fts_symfd);
429 errno = saved_errno;
430 SET(FTS_STOP);
431 return (NULL);
432 }
433 (void)close(p->fts_symfd);
434 } else if (!(p->fts_flags & FTS_DONTCHDIR)) {
435 if (CHDIR(sp, "..")) {
436 SET(FTS_STOP);
437 return (NULL);
438 }
439 }
440 p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;
441 return (sp->fts_cur = p);
442}
443
444/*
445 * Fts_set takes the stream as an argument although it's not used in this
446 * implementation; it would be necessary if anyone wanted to add global
447 * semantics to fts using fts_set. An error return is allowed for similar
448 * reasons.
449 */
450/* ARGSUSED */
451int
452fts_set(sp, p, instr)
453 FTS *sp;
454 FTSENT *p;
455 int instr;
456{
457 if (instr && instr != FTS_AGAIN && instr != FTS_FOLLOW &&
458 instr != FTS_NOINSTR && instr != FTS_SKIP) {
459 errno = EINVAL;
460 return (1);
461 }
462 p->fts_instr = instr;
463 return (0);
464}
465
466FTSENT *
467fts_children(sp, instr)
468 register FTS *sp;
469 int instr;
470{
471 register FTSENT *p;
472 int fd;
473
474 if (instr && instr != FTS_NAMEONLY) {
475 errno = EINVAL;
476 return (NULL);
477 }
478
479 /* Set current node pointer. */
480 p = sp->fts_cur;
481
482 /*
483 * Errno set to 0 so user can distinguish empty directory from
484 * an error.
485 */
486 errno = 0;
487
488 /* Fatal errors stop here. */
489 if (ISSET(FTS_STOP))
490 return (NULL);
491
492 /* Return logical hierarchy of user's arguments. */
493 if (p->fts_info == FTS_INIT)
494 return (p->fts_link);
495
496 /*
497 * If not a directory being visited in pre-order, stop here. Could
498 * allow FTS_DNR, assuming the user has fixed the problem, but the
499 * same effect is available with FTS_AGAIN.
500 */
501 if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */)
502 return (NULL);
503
504 /* Free up any previous child list. */
505 if (sp->fts_child)
506 fts_lfree(sp->fts_child);
507
508 if (instr == FTS_NAMEONLY) {
509 sp->fts_options |= FTS_NAMEONLY;
510 instr = BNAMES;
511 } else
512 instr = BCHILD;
513
514 /*
515 * If using chdir on a relative path and called BEFORE fts_read does
516 * its chdir to the root of a traversal, we can lose -- we need to
517 * chdir into the subdirectory, and we don't know where the current
518 * directory is, so we can't get back so that the upcoming chdir by
519 * fts_read will work.
520 */
521 if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' ||
522 ISSET(FTS_NOCHDIR))
523 return (sp->fts_child = fts_build(sp, instr));
524
525 if ((fd = open(".", O_RDONLY, 0)) < 0)
526 return (NULL);
527 sp->fts_child = fts_build(sp, instr);
528 if (fchdir(fd))
529 return (NULL);
530 (void)close(fd);
531 return (sp->fts_child);
532}
533
534/*
535 * This is the tricky part -- do not casually change *anything* in here. The
536 * idea is to build the linked list of entries that are used by fts_children
537 * and fts_read. There are lots of special cases.
538 *
539 * The real slowdown in walking the tree is the stat calls. If FTS_NOSTAT is
540 * set and it's a physical walk (so that symbolic links can't be directories),
541 * we can do things quickly. First, if it's a 4.4BSD file system, the type
542 * of the file is in the directory entry. Otherwise, we assume that the number
543 * of subdirectories in a node is equal to the number of links to the parent.
544 * The former skips all stat calls. The latter skips stat calls in any leaf
545 * directories and for any files after the subdirectories in the directory have
546 * been found, cutting the stat calls by about 2/3.
547 */
548static FTSENT *
549fts_build(sp, type)
550 register FTS *sp;
551 int type;
552{
553 register struct dirent *dp;
554 register FTSENT *p, *head;
555 register int nitems;
556 FTSENT *cur, *tail;
557 DIR *dirp;
558 void *adjaddr;
559 int cderrno, descend, len, level, maxlen, nlinks, saved_errno;
560 char *cp;
561
562 /* Set current node pointer. */
563 cur = sp->fts_cur;
564
565 /*
566 * Open the directory for reading. If this fails, we're done.
567 * If being called from fts_read, set the fts_info field.
568 */
569 if ((dirp = opendir(cur->fts_accpath)) == NULL) {
570 if (type == BREAD) {
571 cur->fts_info = FTS_DNR;
572 cur->fts_errno = errno;
573 }
574 return (NULL);
575 }
576
577 /*
578 * Nlinks is the number of possible entries of type directory in the
579 * directory if we're cheating on stat calls, 0 if we're not doing
580 * any stat calls at all, -1 if we're doing stats on everything.
581 */
582 if (type == BNAMES)
583 nlinks = 0;
584 else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL))
585 nlinks = cur->fts_nlink - (ISSET(FTS_SEEDOT) ? 0 : 2);
586 else
587 nlinks = -1;
588
589#ifdef notdef
590 (void)printf("nlinks == %d (cur: %d)\n", nlinks, cur->fts_nlink);
591 (void)printf("NOSTAT %d PHYSICAL %d SEEDOT %d\n",
592 ISSET(FTS_NOSTAT), ISSET(FTS_PHYSICAL), ISSET(FTS_SEEDOT));
593#endif
594 /*
595 * If we're going to need to stat anything or we want to descend
596 * and stay in the directory, chdir. If this fails we keep going,
597 * but set a flag so we don't chdir after the post-order visit.
598 * We won't be able to stat anything, but we can still return the
599 * names themselves. Note, that since fts_read won't be able to
600 * chdir into the directory, it will have to return different path
601 * names than before, i.e. "a/b" instead of "b". Since the node
602 * has already been visited in pre-order, have to wait until the
603 * post-order visit to return the error. There is a special case
604 * here, if there was nothing to stat then it's not an error to
605 * not be able to stat. This is all fairly nasty. If a program
606 * needed sorted entries or stat information, they had better be
607 * checking FTS_NS on the returned nodes.
608 */
609 cderrno = 0;
610 if (nlinks || type == BREAD)
611 if (FCHDIR(sp, dirfd(dirp))) {
612 if (nlinks && type == BREAD)
613 cur->fts_errno = errno;
614 cur->fts_flags |= FTS_DONTCHDIR;
615 descend = 0;
616 cderrno = errno;
617 } else
618 descend = 1;
619 else
620 descend = 0;
621
622 /*
623 * Figure out the max file name length that can be stored in the
624 * current path -- the inner loop allocates more path as necessary.
625 * We really wouldn't have to do the maxlen calculations here, we
626 * could do them in fts_read before returning the path, but it's a
627 * lot easier here since the length is part of the dirent structure.
628 *
629 * If not changing directories set a pointer so that can just append
630 * each new name into the path.
631 */
632 maxlen = sp->fts_pathlen - cur->fts_pathlen - 1;
633 len = NAPPEND(cur);
634 if (ISSET(FTS_NOCHDIR)) {
635 cp = sp->fts_path + len;
636 *cp++ = '/';
637 }
638
639 level = cur->fts_level + 1;
640
641 /* Read the directory, attaching each entry to the `link' pointer. */
642 adjaddr = NULL;
|
643 for (head = tail = NULL, nitems = 0; dp = readdir(dirp);) {
| 643 for (head = tail = NULL, nitems = 0; (dp = readdir(dirp)); ) {
|
644 if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))
645 continue;
646
647 if ((p = fts_alloc(sp, dp->d_name, (int)dp->d_namlen)) == NULL)
648 goto mem1;
649 if (dp->d_namlen > maxlen) {
650 if (fts_palloc(sp, (size_t)dp->d_namlen)) {
651 /*
652 * No more memory for path or structures. Save
653 * errno, free up the current structure and the
654 * structures already allocated.
655 */
656mem1: saved_errno = errno;
657 if (p)
658 free(p);
659 fts_lfree(head);
660 (void)closedir(dirp);
661 errno = saved_errno;
662 cur->fts_info = FTS_ERR;
663 SET(FTS_STOP);
664 return (NULL);
665 }
666 adjaddr = sp->fts_path;
667 maxlen = sp->fts_pathlen - sp->fts_cur->fts_pathlen - 1;
668 }
669
670 p->fts_pathlen = len + dp->d_namlen + 1;
671 p->fts_parent = sp->fts_cur;
672 p->fts_level = level;
673
674 if (cderrno) {
675 if (nlinks) {
676 p->fts_info = FTS_NS;
677 p->fts_errno = cderrno;
678 } else
679 p->fts_info = FTS_NSOK;
680 p->fts_accpath = cur->fts_accpath;
681 } else if (nlinks == 0
682#ifdef DT_DIR
| 644 if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))
645 continue;
646
647 if ((p = fts_alloc(sp, dp->d_name, (int)dp->d_namlen)) == NULL)
648 goto mem1;
649 if (dp->d_namlen > maxlen) {
650 if (fts_palloc(sp, (size_t)dp->d_namlen)) {
651 /*
652 * No more memory for path or structures. Save
653 * errno, free up the current structure and the
654 * structures already allocated.
655 */
656mem1: saved_errno = errno;
657 if (p)
658 free(p);
659 fts_lfree(head);
660 (void)closedir(dirp);
661 errno = saved_errno;
662 cur->fts_info = FTS_ERR;
663 SET(FTS_STOP);
664 return (NULL);
665 }
666 adjaddr = sp->fts_path;
667 maxlen = sp->fts_pathlen - sp->fts_cur->fts_pathlen - 1;
668 }
669
670 p->fts_pathlen = len + dp->d_namlen + 1;
671 p->fts_parent = sp->fts_cur;
672 p->fts_level = level;
673
674 if (cderrno) {
675 if (nlinks) {
676 p->fts_info = FTS_NS;
677 p->fts_errno = cderrno;
678 } else
679 p->fts_info = FTS_NSOK;
680 p->fts_accpath = cur->fts_accpath;
681 } else if (nlinks == 0
682#ifdef DT_DIR
|
683 || nlinks > 0 &&
684 dp->d_type != DT_DIR && dp->d_type != DT_UNKNOWN
| 683 || (nlinks > 0 &&
684 dp->d_type != DT_DIR && dp->d_type != DT_UNKNOWN)
|
685#endif
686 ) {
687 p->fts_accpath =
688 ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name;
689 p->fts_info = FTS_NSOK;
690 } else {
691 /* Build a file name for fts_stat to stat. */
692 if (ISSET(FTS_NOCHDIR)) {
693 p->fts_accpath = p->fts_path;
694 memmove(cp, p->fts_name, p->fts_namelen + 1);
695 } else
696 p->fts_accpath = p->fts_name;
697 /* Stat it. */
698 p->fts_info = fts_stat(sp, p, 0);
699
700 /* Decrement link count if applicable. */
701 if (nlinks > 0 && (p->fts_info == FTS_D ||
702 p->fts_info == FTS_DC || p->fts_info == FTS_DOT))
703 --nlinks;
704 }
705
706 /* We walk in directory order so "ls -f" doesn't get upset. */
707 p->fts_link = NULL;
708 if (head == NULL)
709 head = tail = p;
710 else {
711 tail->fts_link = p;
712 tail = p;
713 }
714 ++nitems;
715 }
716 (void)closedir(dirp);
717
718 /*
719 * If had to realloc the path, adjust the addresses for the rest
720 * of the tree.
721 */
722 if (adjaddr)
723 fts_padjust(sp, adjaddr);
724
725 /*
726 * If not changing directories, reset the path back to original
727 * state.
728 */
729 if (ISSET(FTS_NOCHDIR)) {
730 if (cp - 1 > sp->fts_path)
731 --cp;
732 *cp = '\0';
733 }
734
735 /*
736 * If descended after called from fts_children or after called from
737 * fts_read and nothing found, get back. At the root level we use
738 * the saved fd; if one of fts_open()'s arguments is a relative path
739 * to an empty directory, we wind up here with no other way back. If
740 * can't get back, we're done.
741 */
742 if (descend && (type == BCHILD || !nitems) &&
743 (cur->fts_level == FTS_ROOTLEVEL ?
744 FCHDIR(sp, sp->fts_rfd) : CHDIR(sp, ".."))) {
745 cur->fts_info = FTS_ERR;
746 SET(FTS_STOP);
747 return (NULL);
748 }
749
750 /* If didn't find anything, return NULL. */
751 if (!nitems) {
752 if (type == BREAD)
753 cur->fts_info = FTS_DP;
754 return (NULL);
755 }
756
757 /* Sort the entries. */
758 if (sp->fts_compar && nitems > 1)
759 head = fts_sort(sp, head, nitems);
760 return (head);
761}
762
763static u_short
764fts_stat(sp, p, follow)
765 FTS *sp;
766 register FTSENT *p;
767 int follow;
768{
769 register FTSENT *t;
770 register dev_t dev;
771 register ino_t ino;
772 struct stat *sbp, sb;
773 int saved_errno;
774
775 /* If user needs stat info, stat buffer already allocated. */
776 sbp = ISSET(FTS_NOSTAT) ? &sb : p->fts_statp;
777
778 /*
779 * If doing a logical walk, or application requested FTS_FOLLOW, do
780 * a stat(2). If that fails, check for a non-existent symlink. If
781 * fail, set the errno from the stat call.
782 */
783 if (ISSET(FTS_LOGICAL) || follow) {
784 if (stat(p->fts_accpath, sbp)) {
785 saved_errno = errno;
786 if (!lstat(p->fts_accpath, sbp)) {
787 errno = 0;
788 return (FTS_SLNONE);
789 }
790 p->fts_errno = saved_errno;
791 goto err;
792 }
793 } else if (lstat(p->fts_accpath, sbp)) {
794 p->fts_errno = errno;
795err: memset(sbp, 0, sizeof(struct stat));
796 return (FTS_NS);
797 }
798
799 if (S_ISDIR(sbp->st_mode)) {
800 /*
801 * Set the device/inode. Used to find cycles and check for
802 * crossing mount points. Also remember the link count, used
803 * in fts_build to limit the number of stat calls. It is
804 * understood that these fields are only referenced if fts_info
805 * is set to FTS_D.
806 */
807 dev = p->fts_dev = sbp->st_dev;
808 ino = p->fts_ino = sbp->st_ino;
809 p->fts_nlink = sbp->st_nlink;
810
811 if (ISDOT(p->fts_name))
812 return (FTS_DOT);
813
814 /*
815 * Cycle detection is done by brute force when the directory
816 * is first encountered. If the tree gets deep enough or the
817 * number of symbolic links to directories is high enough,
818 * something faster might be worthwhile.
819 */
820 for (t = p->fts_parent;
821 t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
822 if (ino == t->fts_ino && dev == t->fts_dev) {
823 p->fts_cycle = t;
824 return (FTS_DC);
825 }
826 return (FTS_D);
827 }
828 if (S_ISLNK(sbp->st_mode))
829 return (FTS_SL);
830 if (S_ISREG(sbp->st_mode))
831 return (FTS_F);
832 return (FTS_DEFAULT);
833}
834
835static FTSENT *
836fts_sort(sp, head, nitems)
837 FTS *sp;
838 FTSENT *head;
839 register int nitems;
840{
841 register FTSENT **ap, *p;
842
843 /*
844 * Construct an array of pointers to the structures and call qsort(3).
845 * Reassemble the array in the order returned by qsort. If unable to
846 * sort for memory reasons, return the directory entries in their
847 * current order. Allocate enough space for the current needs plus
848 * 40 so don't realloc one entry at a time.
849 */
850 if (nitems > sp->fts_nitems) {
851 sp->fts_nitems = nitems + 40;
852 if ((sp->fts_array = realloc(sp->fts_array,
853 (size_t)(sp->fts_nitems * sizeof(FTSENT *)))) == NULL) {
854 sp->fts_nitems = 0;
855 return (head);
856 }
857 }
858 for (ap = sp->fts_array, p = head; p; p = p->fts_link)
859 *ap++ = p;
860 qsort((void *)sp->fts_array, nitems, sizeof(FTSENT *), sp->fts_compar);
861 for (head = *(ap = sp->fts_array); --nitems; ++ap)
862 ap[0]->fts_link = ap[1];
863 ap[0]->fts_link = NULL;
864 return (head);
865}
866
867static FTSENT *
868fts_alloc(sp, name, namelen)
869 FTS *sp;
870 char *name;
871 register int namelen;
872{
873 register FTSENT *p;
874 size_t len;
875
876 /*
877 * The file name is a variable length array and no stat structure is
878 * necessary if the user has set the nostat bit. Allocate the FTSENT
879 * structure, the file name and the stat structure in one chunk, but
880 * be careful that the stat structure is reasonably aligned. Since the
881 * fts_name field is declared to be of size 1, the fts_name pointer is
882 * namelen + 2 before the first possible address of the stat structure.
883 */
884 len = sizeof(FTSENT) + namelen;
885 if (!ISSET(FTS_NOSTAT))
886 len += sizeof(struct stat) + ALIGNBYTES;
887 if ((p = malloc(len)) == NULL)
888 return (NULL);
889
890 /* Copy the name plus the trailing NULL. */
891 memmove(p->fts_name, name, namelen + 1);
892
893 if (!ISSET(FTS_NOSTAT))
894 p->fts_statp = (struct stat *)ALIGN(p->fts_name + namelen + 2);
895 p->fts_namelen = namelen;
896 p->fts_path = sp->fts_path;
897 p->fts_errno = 0;
898 p->fts_flags = 0;
899 p->fts_instr = FTS_NOINSTR;
900 p->fts_number = 0;
901 p->fts_pointer = NULL;
902 return (p);
903}
904
905static void
906fts_lfree(head)
907 register FTSENT *head;
908{
909 register FTSENT *p;
910
911 /* Free a linked list of structures. */
| 685#endif
686 ) {
687 p->fts_accpath =
688 ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name;
689 p->fts_info = FTS_NSOK;
690 } else {
691 /* Build a file name for fts_stat to stat. */
692 if (ISSET(FTS_NOCHDIR)) {
693 p->fts_accpath = p->fts_path;
694 memmove(cp, p->fts_name, p->fts_namelen + 1);
695 } else
696 p->fts_accpath = p->fts_name;
697 /* Stat it. */
698 p->fts_info = fts_stat(sp, p, 0);
699
700 /* Decrement link count if applicable. */
701 if (nlinks > 0 && (p->fts_info == FTS_D ||
702 p->fts_info == FTS_DC || p->fts_info == FTS_DOT))
703 --nlinks;
704 }
705
706 /* We walk in directory order so "ls -f" doesn't get upset. */
707 p->fts_link = NULL;
708 if (head == NULL)
709 head = tail = p;
710 else {
711 tail->fts_link = p;
712 tail = p;
713 }
714 ++nitems;
715 }
716 (void)closedir(dirp);
717
718 /*
719 * If had to realloc the path, adjust the addresses for the rest
720 * of the tree.
721 */
722 if (adjaddr)
723 fts_padjust(sp, adjaddr);
724
725 /*
726 * If not changing directories, reset the path back to original
727 * state.
728 */
729 if (ISSET(FTS_NOCHDIR)) {
730 if (cp - 1 > sp->fts_path)
731 --cp;
732 *cp = '\0';
733 }
734
735 /*
736 * If descended after called from fts_children or after called from
737 * fts_read and nothing found, get back. At the root level we use
738 * the saved fd; if one of fts_open()'s arguments is a relative path
739 * to an empty directory, we wind up here with no other way back. If
740 * can't get back, we're done.
741 */
742 if (descend && (type == BCHILD || !nitems) &&
743 (cur->fts_level == FTS_ROOTLEVEL ?
744 FCHDIR(sp, sp->fts_rfd) : CHDIR(sp, ".."))) {
745 cur->fts_info = FTS_ERR;
746 SET(FTS_STOP);
747 return (NULL);
748 }
749
750 /* If didn't find anything, return NULL. */
751 if (!nitems) {
752 if (type == BREAD)
753 cur->fts_info = FTS_DP;
754 return (NULL);
755 }
756
757 /* Sort the entries. */
758 if (sp->fts_compar && nitems > 1)
759 head = fts_sort(sp, head, nitems);
760 return (head);
761}
762
763static u_short
764fts_stat(sp, p, follow)
765 FTS *sp;
766 register FTSENT *p;
767 int follow;
768{
769 register FTSENT *t;
770 register dev_t dev;
771 register ino_t ino;
772 struct stat *sbp, sb;
773 int saved_errno;
774
775 /* If user needs stat info, stat buffer already allocated. */
776 sbp = ISSET(FTS_NOSTAT) ? &sb : p->fts_statp;
777
778 /*
779 * If doing a logical walk, or application requested FTS_FOLLOW, do
780 * a stat(2). If that fails, check for a non-existent symlink. If
781 * fail, set the errno from the stat call.
782 */
783 if (ISSET(FTS_LOGICAL) || follow) {
784 if (stat(p->fts_accpath, sbp)) {
785 saved_errno = errno;
786 if (!lstat(p->fts_accpath, sbp)) {
787 errno = 0;
788 return (FTS_SLNONE);
789 }
790 p->fts_errno = saved_errno;
791 goto err;
792 }
793 } else if (lstat(p->fts_accpath, sbp)) {
794 p->fts_errno = errno;
795err: memset(sbp, 0, sizeof(struct stat));
796 return (FTS_NS);
797 }
798
799 if (S_ISDIR(sbp->st_mode)) {
800 /*
801 * Set the device/inode. Used to find cycles and check for
802 * crossing mount points. Also remember the link count, used
803 * in fts_build to limit the number of stat calls. It is
804 * understood that these fields are only referenced if fts_info
805 * is set to FTS_D.
806 */
807 dev = p->fts_dev = sbp->st_dev;
808 ino = p->fts_ino = sbp->st_ino;
809 p->fts_nlink = sbp->st_nlink;
810
811 if (ISDOT(p->fts_name))
812 return (FTS_DOT);
813
814 /*
815 * Cycle detection is done by brute force when the directory
816 * is first encountered. If the tree gets deep enough or the
817 * number of symbolic links to directories is high enough,
818 * something faster might be worthwhile.
819 */
820 for (t = p->fts_parent;
821 t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
822 if (ino == t->fts_ino && dev == t->fts_dev) {
823 p->fts_cycle = t;
824 return (FTS_DC);
825 }
826 return (FTS_D);
827 }
828 if (S_ISLNK(sbp->st_mode))
829 return (FTS_SL);
830 if (S_ISREG(sbp->st_mode))
831 return (FTS_F);
832 return (FTS_DEFAULT);
833}
834
835static FTSENT *
836fts_sort(sp, head, nitems)
837 FTS *sp;
838 FTSENT *head;
839 register int nitems;
840{
841 register FTSENT **ap, *p;
842
843 /*
844 * Construct an array of pointers to the structures and call qsort(3).
845 * Reassemble the array in the order returned by qsort. If unable to
846 * sort for memory reasons, return the directory entries in their
847 * current order. Allocate enough space for the current needs plus
848 * 40 so don't realloc one entry at a time.
849 */
850 if (nitems > sp->fts_nitems) {
851 sp->fts_nitems = nitems + 40;
852 if ((sp->fts_array = realloc(sp->fts_array,
853 (size_t)(sp->fts_nitems * sizeof(FTSENT *)))) == NULL) {
854 sp->fts_nitems = 0;
855 return (head);
856 }
857 }
858 for (ap = sp->fts_array, p = head; p; p = p->fts_link)
859 *ap++ = p;
860 qsort((void *)sp->fts_array, nitems, sizeof(FTSENT *), sp->fts_compar);
861 for (head = *(ap = sp->fts_array); --nitems; ++ap)
862 ap[0]->fts_link = ap[1];
863 ap[0]->fts_link = NULL;
864 return (head);
865}
866
867static FTSENT *
868fts_alloc(sp, name, namelen)
869 FTS *sp;
870 char *name;
871 register int namelen;
872{
873 register FTSENT *p;
874 size_t len;
875
876 /*
877 * The file name is a variable length array and no stat structure is
878 * necessary if the user has set the nostat bit. Allocate the FTSENT
879 * structure, the file name and the stat structure in one chunk, but
880 * be careful that the stat structure is reasonably aligned. Since the
881 * fts_name field is declared to be of size 1, the fts_name pointer is
882 * namelen + 2 before the first possible address of the stat structure.
883 */
884 len = sizeof(FTSENT) + namelen;
885 if (!ISSET(FTS_NOSTAT))
886 len += sizeof(struct stat) + ALIGNBYTES;
887 if ((p = malloc(len)) == NULL)
888 return (NULL);
889
890 /* Copy the name plus the trailing NULL. */
891 memmove(p->fts_name, name, namelen + 1);
892
893 if (!ISSET(FTS_NOSTAT))
894 p->fts_statp = (struct stat *)ALIGN(p->fts_name + namelen + 2);
895 p->fts_namelen = namelen;
896 p->fts_path = sp->fts_path;
897 p->fts_errno = 0;
898 p->fts_flags = 0;
899 p->fts_instr = FTS_NOINSTR;
900 p->fts_number = 0;
901 p->fts_pointer = NULL;
902 return (p);
903}
904
905static void
906fts_lfree(head)
907 register FTSENT *head;
908{
909 register FTSENT *p;
910
911 /* Free a linked list of structures. */
|
912 while (p = head) {
| 912 while ( (p = head) ) {
|
913 head = head->fts_link;
914 free(p);
915 }
916}
917
918/*
919 * Allow essentially unlimited paths; find, rm, ls should all work on any tree.
920 * Most systems will allow creation of paths much longer than MAXPATHLEN, even
921 * though the kernel won't resolve them. Add the size (not just what's needed)
922 * plus 256 bytes so don't realloc the path 2 bytes at a time.
923 */
924static int
925fts_palloc(sp, more)
926 FTS *sp;
927 size_t more;
928{
929 sp->fts_pathlen += more + 256;
930 sp->fts_path = realloc(sp->fts_path, (size_t)sp->fts_pathlen);
931 return (sp->fts_path == NULL);
932}
933
934/*
935 * When the path is realloc'd, have to fix all of the pointers in structures
936 * already returned.
937 */
938static void
939fts_padjust(sp, addr)
940 FTS *sp;
941 void *addr;
942{
943 FTSENT *p;
944
945#define ADJUST(p) { \
946 (p)->fts_accpath = \
947 (char *)addr + ((p)->fts_accpath - (p)->fts_path); \
948 (p)->fts_path = addr; \
949}
950 /* Adjust the current set of children. */
951 for (p = sp->fts_child; p; p = p->fts_link)
952 ADJUST(p);
953
954 /* Adjust the rest of the tree. */
955 for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {
956 ADJUST(p);
957 p = p->fts_link ? p->fts_link : p->fts_parent;
958 }
959}
960
961static size_t
962fts_maxarglen(argv)
963 char * const *argv;
964{
965 size_t len, max;
966
967 for (max = 0; *argv; ++argv)
968 if ((len = strlen(*argv)) > max)
969 max = len;
970 return (max);
971}
| 913 head = head->fts_link;
914 free(p);
915 }
916}
917
918/*
919 * Allow essentially unlimited paths; find, rm, ls should all work on any tree.
920 * Most systems will allow creation of paths much longer than MAXPATHLEN, even
921 * though the kernel won't resolve them. Add the size (not just what's needed)
922 * plus 256 bytes so don't realloc the path 2 bytes at a time.
923 */
924static int
925fts_palloc(sp, more)
926 FTS *sp;
927 size_t more;
928{
929 sp->fts_pathlen += more + 256;
930 sp->fts_path = realloc(sp->fts_path, (size_t)sp->fts_pathlen);
931 return (sp->fts_path == NULL);
932}
933
934/*
935 * When the path is realloc'd, have to fix all of the pointers in structures
936 * already returned.
937 */
938static void
939fts_padjust(sp, addr)
940 FTS *sp;
941 void *addr;
942{
943 FTSENT *p;
944
945#define ADJUST(p) { \
946 (p)->fts_accpath = \
947 (char *)addr + ((p)->fts_accpath - (p)->fts_path); \
948 (p)->fts_path = addr; \
949}
950 /* Adjust the current set of children. */
951 for (p = sp->fts_child; p; p = p->fts_link)
952 ADJUST(p);
953
954 /* Adjust the rest of the tree. */
955 for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {
956 ADJUST(p);
957 p = p->fts_link ? p->fts_link : p->fts_parent;
958 }
959}
960
961static size_t
962fts_maxarglen(argv)
963 char * const *argv;
964{
965 size_t len, max;
966
967 for (max = 0; *argv; ++argv)
968 if ((len = strlen(*argv)) > max)
969 max = len;
970 return (max);
971}
|