Commit | Line | Data |
---|---|---|
df589a0d KB |
1 | /*- |
2 | * Copyright (c) 1990 The Regents of the University of California. | |
6f8dfca7 KB |
3 | * All rights reserved. |
4 | * | |
df589a0d | 5 | * %sccs.include.redist.c% |
6f8dfca7 KB |
6 | */ |
7 | ||
8 | #if defined(LIBC_SCCS) && !defined(lint) | |
0a60cc84 | 9 | static char sccsid[] = "@(#)fts.c 5.18 (Berkeley) %G%"; |
6f8dfca7 KB |
10 | #endif /* LIBC_SCCS and not lint */ |
11 | ||
10f860f8 | 12 | #include <sys/cdefs.h> |
6f8dfca7 KB |
13 | #include <sys/param.h> |
14 | #include <sys/stat.h> | |
c8f49d0a | 15 | #include <fcntl.h> |
6f8dfca7 KB |
16 | #include <dirent.h> |
17 | #include <errno.h> | |
10f860f8 | 18 | #include "fts.h" |
ccfce475 | 19 | #include <stdlib.h> |
10f860f8 | 20 | #include <string.h> |
2c9e6184 | 21 | #include <unistd.h> |
6f8dfca7 | 22 | |
10f860f8 | 23 | static FTSENT *fts_alloc(), *fts_build(), *fts_sort(); |
0a60cc84 | 24 | static void fts_load(), fts_lfree(); |
2c9e6184 KB |
25 | static u_short fts_stat(); |
26 | static char *fts_path(); | |
6f8dfca7 | 27 | |
9f27273b KB |
28 | #define ISSET(opt) (sp->fts_options & opt) |
29 | #define SET(opt) (sp->fts_options |= opt) | |
6f8dfca7 | 30 | |
9f27273b KB |
31 | #define CHDIR(sp, path) (!ISSET(FTS_NOCHDIR) && chdir(path)) |
32 | #define FCHDIR(sp, fd) (!ISSET(FTS_NOCHDIR) && fchdir(fd)) | |
6f8dfca7 | 33 | |
c8f49d0a | 34 | /* fts_build flags */ |
9f27273b KB |
35 | #define BCHILD 1 /* from fts_children */ |
36 | #define BREAD 2 /* from fts_read */ | |
c8f49d0a | 37 | |
6f8dfca7 | 38 | FTS * |
9f27273b | 39 | fts_open(argv, options, compar) |
2c9e6184 | 40 | char * const *argv; |
6f8dfca7 | 41 | register int options; |
10f860f8 | 42 | int (*compar)(); |
6f8dfca7 KB |
43 | { |
44 | register FTS *sp; | |
45 | register FTSENT *p, *root; | |
46 | register int nitems, maxlen; | |
47 | FTSENT *parent, *tmp; | |
10f860f8 | 48 | int len; |
6f8dfca7 | 49 | |
9f27273b KB |
50 | /* Allocate/initialize the stream */ |
51 | if (!(sp = (FTS *)malloc((u_int)sizeof(FTS)))) | |
6f8dfca7 KB |
52 | return(NULL); |
53 | bzero(sp, sizeof(FTS)); | |
df589a0d KB |
54 | sp->fts_compar = compar; |
55 | sp->fts_options = options; | |
6f8dfca7 | 56 | |
9f27273b KB |
57 | /* Logical walks turn on NOCHDIR; symbolic links are too hard. */ |
58 | if (ISSET(FTS_LOGICAL)) | |
59 | SET(FTS_NOCHDIR); | |
60 | ||
61 | /* Allocate/initialize root's parent. */ | |
62 | if (!(parent = fts_alloc(sp, "", 0))) | |
6f8dfca7 | 63 | goto mem1; |
6cfdcbf9 | 64 | parent->fts_level = FTS_ROOTPARENTLEVEL; |
6f8dfca7 | 65 | |
9f27273b | 66 | /* Allocate/initialize root(s). */ |
9a0aa1ee KB |
67 | maxlen = -1; |
68 | for (root = NULL, nitems = 0; *argv; ++argv, ++nitems) { | |
10f860f8 KB |
69 | if (!(len = strlen(*argv))) { |
70 | errno = ENOENT; | |
9a0aa1ee | 71 | goto mem2; |
10f860f8 KB |
72 | } |
73 | if (maxlen < len) | |
74 | maxlen = len; | |
75 | p = fts_alloc(sp, *argv, len); | |
9a0aa1ee | 76 | /* |
9f27273b | 77 | * If comparison routine supplied, traverse in sorted |
9a0aa1ee KB |
78 | * order; otherwise traverse in the order specified. |
79 | */ | |
80 | if (compar) { | |
81 | p->fts_link = root; | |
82 | root = p; | |
83 | p->fts_accpath = p->fts_name; | |
0e31e24a | 84 | if (!(options & FTS_NOSTAT)) |
9f27273b | 85 | p->fts_info = fts_stat(sp, p, 0); |
9a0aa1ee KB |
86 | } else { |
87 | p->fts_link = NULL; | |
88 | if (!root) | |
89 | tmp = root = p; | |
90 | else { | |
91 | tmp->fts_link = p; | |
92 | tmp = p; | |
6f8dfca7 | 93 | } |
6f8dfca7 | 94 | } |
6cfdcbf9 | 95 | p->fts_level = FTS_ROOTLEVEL; |
9a0aa1ee | 96 | p->fts_parent = parent; |
6f8dfca7 | 97 | } |
9a0aa1ee | 98 | if (compar && nitems > 1) |
9f27273b | 99 | root = fts_sort(sp, root, nitems); |
6f8dfca7 | 100 | |
6f8dfca7 | 101 | /* |
9f27273b | 102 | * Allocate a dummy pointer and make fts_read think that we've just |
ccfce475 KB |
103 | * finished the node before the root(s); set p->fts_info to FTS_NS |
104 | * so that everything about the "current" node is ignored. | |
6f8dfca7 | 105 | */ |
9f27273b | 106 | if (!(sp->fts_cur = fts_alloc(sp, "", 0))) |
ccfce475 KB |
107 | goto mem2; |
108 | sp->fts_cur->fts_link = root; | |
109 | sp->fts_cur->fts_info = FTS_NS; | |
110 | ||
9f27273b KB |
111 | /* Start out with at least 1K+ of path space. */ |
112 | if (!fts_path(sp, MAX(maxlen, MAXPATHLEN))) | |
ccfce475 | 113 | goto mem3; |
6f8dfca7 KB |
114 | |
115 | /* | |
9f27273b | 116 | * If using chdir(2), grab a file descriptor pointing to dot to insure |
c8f49d0a KB |
117 | * that we can get back here; this could be avoided for some paths, |
118 | * but almost certainly not worth the effort. Slashes, symbolic links, | |
119 | * and ".." are all fairly nasty problems. Note, if we can't get the | |
120 | * descriptor we run anyway, just more slowly. | |
6f8dfca7 | 121 | */ |
10f860f8 | 122 | if (!ISSET(FTS_NOCHDIR) && (sp->fts_rfd = open(".", O_RDONLY, 0)) < 0) |
9f27273b | 123 | SET(FTS_NOCHDIR); |
6f8dfca7 KB |
124 | |
125 | return(sp); | |
126 | ||
10f860f8 | 127 | mem3: free(sp->fts_cur); |
6f8dfca7 | 128 | mem2: fts_lfree(root); |
10f860f8 KB |
129 | free(parent); |
130 | mem1: free(sp); | |
6f8dfca7 KB |
131 | return(NULL); |
132 | } | |
133 | ||
0a60cc84 | 134 | static void |
9f27273b KB |
135 | fts_load(sp, p) |
136 | FTS *sp; | |
6f8dfca7 KB |
137 | register FTSENT *p; |
138 | { | |
139 | register int len; | |
140 | register char *cp; | |
141 | ||
142 | /* | |
0548d806 KB |
143 | * Load the stream structure for the next traversal. Since we don't |
144 | * actually enter the directory until after the preorder visit, set | |
145 | * the fts_accpath field specially so the chdir gets done to the right | |
146 | * place and the user can access the first node. | |
6f8dfca7 | 147 | */ |
df589a0d | 148 | len = p->fts_pathlen = p->fts_namelen; |
9f27273b | 149 | bcopy(p->fts_name, sp->fts_path, len + 1); |
df589a0d | 150 | if ((cp = rindex(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) { |
6f8dfca7 | 151 | len = strlen(++cp); |
df589a0d KB |
152 | bcopy(cp, p->fts_name, len + 1); |
153 | p->fts_namelen = len; | |
6f8dfca7 | 154 | } |
9f27273b | 155 | p->fts_accpath = p->fts_path = sp->fts_path; |
10f860f8 | 156 | |
6cfdcbf9 | 157 | p->fts_info = fts_stat(sp, p, 0); |
5ee6b6f8 | 158 | sp->rdev = p->fts_statb.st_dev; |
6f8dfca7 KB |
159 | } |
160 | ||
9f27273b | 161 | fts_close(sp) |
6f8dfca7 KB |
162 | FTS *sp; |
163 | { | |
164 | register FTSENT *freep, *p; | |
165 | int saved_errno; | |
166 | ||
ccfce475 KB |
167 | if (sp->fts_cur) { |
168 | /* | |
9f27273b | 169 | * This still works if we haven't read anything -- the dummy |
ccfce475 KB |
170 | * structure points to the root list, so we step through to |
171 | * the end of the root list which has a valid parent pointer. | |
172 | */ | |
6cfdcbf9 | 173 | for (p = sp->fts_cur; p->fts_level > FTS_ROOTPARENTLEVEL;) { |
ccfce475 KB |
174 | freep = p; |
175 | p = p->fts_link ? p->fts_link : p->fts_parent; | |
10f860f8 | 176 | free(freep); |
6f8dfca7 | 177 | } |
10f860f8 | 178 | free(p); |
ccfce475 | 179 | } |
6f8dfca7 | 180 | |
9f27273b | 181 | /* Free up child linked list, sort array, path buffer. */ |
df589a0d KB |
182 | if (sp->fts_child) |
183 | fts_lfree(sp->fts_child); | |
184 | if (sp->fts_array) | |
10f860f8 KB |
185 | free(sp->fts_array); |
186 | free(sp->fts_path); | |
6f8dfca7 | 187 | |
10f860f8 | 188 | /* Return to original directory, save errno if necessary. */ |
9f27273b | 189 | if (!ISSET(FTS_NOCHDIR)) { |
10f860f8 KB |
190 | saved_errno = fchdir(sp->fts_rfd) ? errno : 0; |
191 | (void)close(sp->fts_rfd); | |
6f8dfca7 KB |
192 | } |
193 | ||
9f27273b | 194 | /* Free up the stream pointer. */ |
10f860f8 | 195 | free(sp); |
6f8dfca7 | 196 | |
9f27273b KB |
197 | /* Set errno and return. */ |
198 | if (!ISSET(FTS_NOCHDIR) && saved_errno) { | |
6f8dfca7 KB |
199 | errno = saved_errno; |
200 | return(-1); | |
201 | } | |
202 | return(0); | |
203 | } | |
204 | ||
10f860f8 KB |
205 | /* |
206 | * Special case a root of "/" so that slashes aren't appended causing | |
207 | * paths to be written as "//foo". | |
208 | */ | |
209 | #define NAPPEND(p) \ | |
6cfdcbf9 | 210 | (p->fts_level == FTS_ROOTLEVEL && p->fts_pathlen == 1 && \ |
10f860f8 KB |
211 | p->fts_path[0] == '/' ? 0 : p->fts_pathlen) |
212 | ||
6f8dfca7 | 213 | FTSENT * |
9f27273b | 214 | fts_read(sp) |
6f8dfca7 KB |
215 | register FTS *sp; |
216 | { | |
c8f49d0a | 217 | register FTSENT *p, *tmp; |
6f8dfca7 | 218 | register int instr; |
10f860f8 | 219 | register char *t; |
6f8dfca7 | 220 | |
9f27273b | 221 | /* If finished or unrecoverable error, return NULL. */ |
10f860f8 | 222 | if (!sp->fts_cur || ISSET(FTS_STOP)) |
6f8dfca7 KB |
223 | return(NULL); |
224 | ||
9f27273b | 225 | /* Set current node pointer. */ |
df589a0d | 226 | p = sp->fts_cur; |
6f8dfca7 | 227 | |
9f27273b | 228 | /* Save and zero out user instructions. */ |
df589a0d | 229 | instr = p->fts_instr; |
10f860f8 | 230 | p->fts_instr = FTS_NOINSTR; |
6f8dfca7 | 231 | |
9f27273b | 232 | /* If used fts_link pointer for cycle detection, restore it. */ |
df589a0d KB |
233 | if (sp->fts_savelink) { |
234 | p->fts_link = sp->fts_savelink; | |
235 | sp->fts_savelink = NULL; | |
6f8dfca7 KB |
236 | } |
237 | ||
10f860f8 | 238 | /* Any type of file may be re-visited; re-stat and re-turn. */ |
6f8dfca7 | 239 | if (instr == FTS_AGAIN) { |
9f27273b | 240 | p->fts_info = fts_stat(sp, p, 0); |
6f8dfca7 KB |
241 | return(p); |
242 | } | |
243 | ||
10f860f8 KB |
244 | /* |
245 | * Following a symlink -- SLNONE test allows application to see | |
246 | * SLNONE and recover. | |
247 | */ | |
248 | if (instr == FTS_FOLLOW && | |
249 | (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) { | |
9f27273b | 250 | p->fts_info = fts_stat(sp, p, 1); |
c8f49d0a KB |
251 | return(p); |
252 | } | |
253 | ||
9f27273b | 254 | /* Directory in pre-order. */ |
c8f49d0a | 255 | if (p->fts_info == FTS_D) { |
9f27273b | 256 | /* If skipped or crossed mount point, do post-order visit. */ |
10f860f8 KB |
257 | if (instr == FTS_SKIP || |
258 | ISSET(FTS_XDEV) && p->fts_statb.st_dev != sp->rdev) { | |
df589a0d KB |
259 | if (sp->fts_child) { |
260 | fts_lfree(sp->fts_child); | |
261 | sp->fts_child = NULL; | |
6f8dfca7 | 262 | } |
e8fecd88 KB |
263 | p->fts_info = FTS_DP; |
264 | return(p); | |
c8f49d0a KB |
265 | } |
266 | ||
10f860f8 KB |
267 | /* |
268 | * Cd to the subdirectory, reading it if haven't already. If | |
269 | * the read fails for any reason, or the directory is empty, | |
270 | * the fts_info field of the current node is set by fts_build. | |
0548d806 KB |
271 | * If have already read and now fail to chdir, whack the list |
272 | * to make the names come out right, and set the parent state | |
273 | * so the application will eventually get an error condition. | |
274 | * If haven't read and fail to chdir, check to see if we're | |
275 | * at the root node -- if so, we have to get back or the root | |
276 | * node may be inaccessible. | |
10f860f8 KB |
277 | */ |
278 | if (sp->fts_child) { | |
c8f49d0a | 279 | if (CHDIR(sp, p->fts_accpath)) { |
10f860f8 KB |
280 | p->fts_parent->fts_cderr = errno; |
281 | for (p = sp->fts_child; p; p = p->fts_link) | |
282 | p->fts_accpath = | |
283 | p->fts_parent->fts_accpath; | |
c8f49d0a | 284 | } |
0548d806 KB |
285 | } else if (!(sp->fts_child = fts_build(sp, BREAD))) { |
286 | if ISSET(FTS_STOP) | |
287 | return(NULL); | |
288 | if (p->fts_level == FTS_ROOTLEVEL && | |
289 | FCHDIR(sp, sp->fts_rfd)) { | |
290 | SET(FTS_STOP); | |
291 | return(NULL); | |
292 | } | |
293 | return(p); | |
294 | } | |
10f860f8 | 295 | p = sp->fts_child; |
c8f49d0a | 296 | sp->fts_child = NULL; |
10f860f8 | 297 | goto name; |
6f8dfca7 KB |
298 | } |
299 | ||
9f27273b | 300 | /* Move to next node on this level. */ |
c8f49d0a KB |
301 | next: tmp = p; |
302 | if (p = p->fts_link) { | |
10f860f8 KB |
303 | free(tmp); |
304 | ||
305 | /* If reached the top, load the paths for the next root. */ | |
6cfdcbf9 | 306 | if (p->fts_level == FTS_ROOTLEVEL) { |
0a60cc84 | 307 | fts_load(sp, p); |
10f860f8 KB |
308 | return(sp->fts_cur = p); |
309 | } | |
c8f49d0a | 310 | |
10f860f8 KB |
311 | /* User may have called fts_set on the node. */ |
312 | if (p->fts_instr == FTS_SKIP) | |
313 | goto next; | |
314 | if (p->fts_instr == FTS_FOLLOW) { | |
315 | p->fts_info = fts_stat(sp, p, 1); | |
316 | p->fts_instr = FTS_NOINSTR; | |
6f8dfca7 | 317 | } |
10f860f8 KB |
318 | |
319 | name: t = sp->fts_path + NAPPEND(p->fts_parent); | |
320 | *t++ = '/'; | |
321 | bcopy(p->fts_name, t, p->fts_namelen + 1); | |
df589a0d | 322 | return(sp->fts_cur = p); |
6f8dfca7 KB |
323 | } |
324 | ||
0548d806 | 325 | /* Move up to the parent node. */ |
c8f49d0a | 326 | p = tmp->fts_parent; |
10f860f8 | 327 | free(tmp); |
c8f49d0a | 328 | |
6cfdcbf9 | 329 | if (p->fts_level == FTS_ROOTPARENTLEVEL) { |
6f8dfca7 | 330 | /* |
9f27273b | 331 | * Done; free everything up and set errno to 0 so the user |
6f8dfca7 KB |
332 | * can distinguish between error and EOF. |
333 | */ | |
10f860f8 | 334 | free(p); |
6f8dfca7 | 335 | errno = 0; |
df589a0d | 336 | return(sp->fts_cur = NULL); |
6f8dfca7 KB |
337 | } |
338 | ||
df589a0d | 339 | sp->fts_path[p->fts_pathlen] = '\0'; |
10f860f8 KB |
340 | |
341 | /* | |
0548d806 KB |
342 | * Cd back up to the parent directory. If at a root node, have to cd |
343 | * back to the original place, otherwise may not be able to access the | |
344 | * original node on post-order. | |
345 | */ | |
346 | if (p->fts_level == FTS_ROOTLEVEL) { | |
347 | if (FCHDIR(sp, sp->fts_rfd)) { | |
348 | SET(FTS_STOP); | |
349 | return(NULL); | |
350 | } | |
351 | } | |
352 | else if (CHDIR(sp, "..")) { | |
353 | SET(FTS_STOP); | |
354 | return(NULL); | |
355 | } | |
356 | ||
357 | /* | |
358 | * If had a chdir error when trying to get into the directory, set the | |
359 | * info field to reflect this, and restore errno. The error indicator | |
360 | * has to be reset to 0 so that if the user does an FTS_AGAIN, it all | |
361 | * works. | |
10f860f8 KB |
362 | */ |
363 | if (p->fts_cderr) { | |
364 | errno = p->fts_cderr; | |
365 | p->fts_cderr = 0; | |
df589a0d | 366 | p->fts_info = FTS_ERR; |
0548d806 | 367 | } else |
df589a0d KB |
368 | p->fts_info = FTS_DP; |
369 | return(sp->fts_cur = p); | |
6f8dfca7 KB |
370 | } |
371 | ||
372 | /* | |
0548d806 | 373 | * Fts_set takes the stream as an argument although it's not used in this |
6f8dfca7 | 374 | * implementation; it would be necessary if anyone wanted to add global |
9f27273b KB |
375 | * semantics to fts using fts_set. An error return is allowed for similar |
376 | * reasons. | |
6f8dfca7 KB |
377 | */ |
378 | /* ARGSUSED */ | |
9f27273b | 379 | fts_set(sp, p, instr) |
6f8dfca7 KB |
380 | FTS *sp; |
381 | FTSENT *p; | |
382 | int instr; | |
383 | { | |
df589a0d | 384 | p->fts_instr = instr; |
6f8dfca7 KB |
385 | return(0); |
386 | } | |
387 | ||
388 | FTSENT * | |
9f27273b | 389 | fts_children(sp) |
6f8dfca7 KB |
390 | register FTS *sp; |
391 | { | |
c8f49d0a KB |
392 | register FTSENT *p; |
393 | int fd; | |
394 | ||
9f27273b KB |
395 | /* Set current node pointer. */ |
396 | p = sp->fts_cur; | |
397 | ||
6f8dfca7 | 398 | /* |
9f27273b | 399 | * Set errno to 0 so that user can tell the difference between an |
10f860f8 KB |
400 | * error and a directory without entries. If not a directory being |
401 | * visited in *pre-order*, or we've already had fatal errors, return | |
402 | * immediately. | |
6f8dfca7 KB |
403 | */ |
404 | errno = 0; | |
10f860f8 | 405 | if (ISSET(FTS_STOP) || p->fts_info != FTS_D && p->fts_info != FTS_DNR) |
6f8dfca7 | 406 | return(NULL); |
9f27273b KB |
407 | |
408 | /* Free up any previous child list. */ | |
df589a0d KB |
409 | if (sp->fts_child) |
410 | fts_lfree(sp->fts_child); | |
c8f49d0a KB |
411 | |
412 | /* | |
9f27273b | 413 | * If using chdir on a relative path and called BEFORE fts_read does |
10f860f8 KB |
414 | * its chdir to the root of a traversal, we can lose -- we need to |
415 | * chdir into the subdirectory, and we don't know where the current | |
416 | * directory is, so we can't get back so that the upcoming chdir by | |
417 | * fts_read will work. | |
c8f49d0a | 418 | */ |
6cfdcbf9 | 419 | if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' || |
9f27273b | 420 | ISSET(FTS_NOCHDIR)) |
c8f49d0a KB |
421 | return(sp->fts_child = fts_build(sp, BCHILD)); |
422 | ||
423 | if ((fd = open(".", O_RDONLY, 0)) < 0) | |
424 | return(NULL); | |
425 | sp->fts_child = fts_build(sp, BCHILD); | |
426 | if (fchdir(fd)) | |
427 | return(NULL); | |
428 | (void)close(fd); | |
429 | return(sp->fts_child); | |
6f8dfca7 KB |
430 | } |
431 | ||
10f860f8 KB |
432 | /* |
433 | * This is the tricky part -- do not casually change *anything* in here. The | |
434 | * idea is to build the linked list of entries that are used by fts_children | |
435 | * and fts_read. There are lots of special cases. | |
436 | * | |
437 | * The real slowdown in walking the tree is the stat calls. If FTS_NOSTAT is | |
438 | * set and it's a physical walk (so that symbolic links can't be directories), | |
439 | * we assume that the number of subdirectories in a node is equal to the number | |
440 | * of links to the parent. This allows stat calls to be skipped in any leaf | |
441 | * directories and for any nodes after the directories in the parent node have | |
442 | * been found. This empirically cuts the stat calls by about 2/3. | |
443 | */ | |
6f8dfca7 KB |
444 | #define ISDOT(a) (a[0] == '.' && (!a[1] || a[1] == '.' && !a[2])) |
445 | ||
2c9e6184 | 446 | static FTSENT * |
c8f49d0a | 447 | fts_build(sp, type) |
6f8dfca7 | 448 | register FTS *sp; |
c8f49d0a | 449 | int type; |
6f8dfca7 KB |
450 | { |
451 | register struct dirent *dp; | |
452 | register FTSENT *p, *head; | |
453 | register int nitems; | |
10f860f8 | 454 | FTSENT *cur; |
6f8dfca7 | 455 | DIR *dirp; |
10f860f8 | 456 | int cderr, descend, len, level, maxlen, nlinks, saved_errno; |
6f8dfca7 KB |
457 | char *cp; |
458 | ||
9f27273b | 459 | /* Set current node pointer. */ |
10f860f8 | 460 | cur = sp->fts_cur; |
9f27273b | 461 | |
10f860f8 KB |
462 | /* |
463 | * Open the directory for reading. If this fails, we're done. | |
464 | * If being called from fts_read, set the fts_info field. | |
465 | */ | |
466 | if (!(dirp = opendir(cur->fts_accpath))) { | |
467 | if (type == BREAD) | |
468 | cur->fts_info = FTS_DNR; | |
6f8dfca7 KB |
469 | return(NULL); |
470 | } | |
6f8dfca7 KB |
471 | |
472 | /* | |
10f860f8 KB |
473 | * Nlinks is the number of possible entries of type directory in the |
474 | * directory if we're cheating on stat calls, 0 if we're not doing | |
475 | * any stat calls at all, -1 if we're doing stats on everything. | |
6f8dfca7 | 476 | */ |
df589a0d | 477 | nlinks = |
9f27273b | 478 | ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL) ? |
10f860f8 | 479 | cur->fts_statb.st_nlink - (ISSET(FTS_SEEDOT) ? 0 : 2) : -1; |
9f27273b | 480 | |
10f860f8 KB |
481 | /* |
482 | * If we're going to need to stat anything or we want to descend | |
483 | * and stay in the directory, chdir. If this fails we keep going. | |
484 | * We won't be able to stat anything, but we can still return the | |
485 | * names themselves. Note, that since fts_read won't be able to | |
486 | * chdir into the directory, it will have to return different path | |
487 | * names than before, i.e. "a/b" instead of "b". Since the node | |
488 | * has already been visited in pre-order, have to wait until the | |
489 | * post-order visit to return the error. This is all fairly nasty. | |
490 | * If a program needed sorted entries or stat information, they had | |
491 | * better be checking FTS_NS on the returned nodes. | |
492 | */ | |
9f27273b | 493 | if (nlinks || type == BREAD) |
10f860f8 KB |
494 | if (FCHDIR(sp, dirfd(dirp))) { |
495 | if (type == BREAD) | |
496 | cur->fts_cderr = errno; | |
497 | descend = nlinks = 0; | |
498 | cderr = 1; | |
499 | } else { | |
9f27273b | 500 | descend = 1; |
10f860f8 | 501 | cderr = 0; |
1730d75f | 502 | } |
10f860f8 KB |
503 | else |
504 | descend = 0; | |
1730d75f | 505 | |
10f860f8 KB |
506 | /* |
507 | * Figure out the max file name length that can be stored in the | |
508 | * current path -- the inner loop allocates more path as necessary. | |
509 | * We really wouldn't have to do the maxlen calculations here, we | |
510 | * could do them in fts_read before returning the path, but it's a | |
511 | * lot easier here since the length is part of the dirent structure. | |
512 | * | |
513 | * If not changing directories set a pointer so that we can just | |
514 | * append each new name into the path. | |
515 | */ | |
516 | maxlen = sp->fts_pathlen - cur->fts_pathlen - 1; | |
517 | len = NAPPEND(cur); | |
518 | if (ISSET(FTS_NOCHDIR)) { | |
519 | cp = sp->fts_path + len; | |
520 | *cp++ = '/'; | |
521 | } | |
9b63b883 | 522 | |
10f860f8 | 523 | level = cur->fts_level + 1; |
9b63b883 | 524 | |
10f860f8 | 525 | /* Read the directory, attaching each entry to the `link' pointer. */ |
6f8dfca7 | 526 | for (head = NULL, nitems = 0; dp = readdir(dirp);) { |
10f860f8 | 527 | if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name)) |
6f8dfca7 KB |
528 | continue; |
529 | ||
10f860f8 | 530 | if (!(p = fts_alloc(sp, dp->d_name, (int)dp->d_namlen))) |
6f8dfca7 | 531 | goto mem1; |
6f8dfca7 | 532 | if (dp->d_namlen > maxlen) { |
9f27273b | 533 | if (!fts_path(sp, (int)dp->d_namlen)) { |
10f860f8 KB |
534 | /* |
535 | * No more memory for path or structures. Save | |
536 | * errno, free up the current structure and the | |
537 | * structures already allocated. | |
538 | */ | |
539 | mem1: saved_errno = errno; | |
540 | if (p) | |
541 | free(p); | |
542 | fts_lfree(head); | |
c8f49d0a | 543 | (void)closedir(dirp); |
10f860f8 KB |
544 | errno = saved_errno; |
545 | cur->fts_info = FTS_ERR; | |
546 | SET(FTS_STOP); | |
6f8dfca7 KB |
547 | return(NULL); |
548 | } | |
df589a0d | 549 | maxlen = sp->fts_pathlen - sp->fts_cur->fts_pathlen - 1; |
6f8dfca7 KB |
550 | } |
551 | ||
df589a0d | 552 | p->fts_pathlen = len + dp->d_namlen + 1; |
df589a0d KB |
553 | p->fts_parent = sp->fts_cur; |
554 | p->fts_level = level; | |
6f8dfca7 KB |
555 | |
556 | if (nlinks) { | |
10f860f8 KB |
557 | /* Build a file name for fts_stat to stat. */ |
558 | if (ISSET(FTS_NOCHDIR)) { | |
559 | p->fts_accpath = p->fts_path; | |
df589a0d | 560 | bcopy(p->fts_name, cp, p->fts_namelen + 1); |
10f860f8 KB |
561 | } else |
562 | p->fts_accpath = p->fts_name; | |
9f27273b | 563 | p->fts_info = fts_stat(sp, p, 0); |
10f860f8 | 564 | if (nlinks > 0 && p->fts_info == FTS_D) |
6f8dfca7 | 565 | --nlinks; |
10f860f8 KB |
566 | } else if (cderr) { |
567 | p->fts_info = ISSET(FTS_NOSTAT) ? FTS_NSOK : FTS_NS; | |
568 | p->fts_accpath = cur->fts_accpath; | |
569 | } else { | |
570 | p->fts_accpath = | |
571 | ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name; | |
572 | p->fts_info = FTS_NSOK; | |
573 | } | |
6f8dfca7 | 574 | |
df589a0d | 575 | p->fts_link = head; |
6f8dfca7 KB |
576 | head = p; |
577 | ++nitems; | |
578 | } | |
579 | (void)closedir(dirp); | |
580 | ||
10f860f8 KB |
581 | /* |
582 | * If not changing directories, reset the path back to original | |
583 | * state. | |
584 | */ | |
585 | if (ISSET(FTS_NOCHDIR)) { | |
586 | if (cp - 1 > sp->fts_path) | |
587 | --cp; | |
588 | *cp = '\0'; | |
589 | } | |
c8f49d0a KB |
590 | |
591 | /* | |
10f860f8 KB |
592 | * If descended after called from fts_children or called from |
593 | * fts_read and didn't find anything, get back. If can't get | |
594 | * back, we're done. | |
c8f49d0a KB |
595 | */ |
596 | if (descend && (!nitems || type == BCHILD) && CHDIR(sp, "..")) { | |
10f860f8 KB |
597 | cur->fts_info = FTS_ERR; |
598 | SET(FTS_STOP); | |
1730d75f KB |
599 | return(NULL); |
600 | } | |
601 | ||
10f860f8 | 602 | /* If we didn't find anything, just do the post-order visit */ |
6f8dfca7 | 603 | if (!nitems) { |
c8f49d0a | 604 | if (type == BREAD) |
10f860f8 | 605 | cur->fts_info = FTS_DP; |
6f8dfca7 KB |
606 | return(NULL); |
607 | } | |
608 | ||
10f860f8 | 609 | /* Sort the entries. */ |
df589a0d | 610 | if (sp->fts_compar && nitems > 1) |
9f27273b | 611 | head = fts_sort(sp, head, nitems); |
6f8dfca7 KB |
612 | return(head); |
613 | } | |
614 | ||
9f27273b KB |
615 | static u_short |
616 | fts_stat(sp, p, follow) | |
617 | FTS *sp; | |
6f8dfca7 | 618 | register FTSENT *p; |
9f27273b | 619 | int follow; |
6f8dfca7 | 620 | { |
10f860f8 KB |
621 | int saved_errno; |
622 | ||
6f8dfca7 | 623 | /* |
9f27273b | 624 | * If doing a logical walk, or application requested FTS_FOLLOW, do |
10f860f8 KB |
625 | * a stat(2). If that fails, check for a non-existent symlink. If |
626 | * fail, return the errno from the stat call. | |
6f8dfca7 | 627 | */ |
9f27273b KB |
628 | if (ISSET(FTS_LOGICAL) || follow) { |
629 | if (stat(p->fts_accpath, &p->fts_statb)) { | |
10f860f8 KB |
630 | saved_errno = errno; |
631 | if (!lstat(p->fts_accpath, &p->fts_statb)) { | |
9f27273b | 632 | errno = 0; |
10f860f8 KB |
633 | return(FTS_SLNONE); |
634 | } | |
635 | errno = saved_errno; | |
636 | bzero(&p->fts_statb, sizeof(struct stat)); | |
637 | return(FTS_NS); | |
9f27273b KB |
638 | } |
639 | } else if (lstat(p->fts_accpath, &p->fts_statb)) { | |
10f860f8 | 640 | bzero(&p->fts_statb, sizeof(struct stat)); |
9f27273b KB |
641 | return(FTS_NS); |
642 | } | |
643 | ||
10f860f8 KB |
644 | /* |
645 | * Cycle detection is done as soon as we find a directory. Detection | |
646 | * is by brute force; if the tree gets deep enough or the number of | |
647 | * symbolic links to directories high enough something faster might | |
648 | * be worthwhile. | |
649 | */ | |
650 | if (S_ISDIR(p->fts_statb.st_mode)) { | |
651 | register FTSENT *t; | |
652 | register dev_t dev; | |
653 | register ino_t ino; | |
654 | ||
655 | dev = p->fts_statb.st_dev; | |
656 | ino = p->fts_statb.st_ino; | |
6cfdcbf9 | 657 | for (t = p->fts_parent; t->fts_level > FTS_ROOTLEVEL; |
10f860f8 KB |
658 | t = t->fts_parent) |
659 | if (ino == t->fts_statb.st_ino && | |
660 | dev == t->fts_statb.st_dev) { | |
661 | sp->fts_savelink = p->fts_link; | |
662 | p->fts_link = t; | |
663 | return(FTS_DC); | |
664 | } | |
6f8dfca7 | 665 | return(FTS_D); |
10f860f8 | 666 | } |
9f27273b | 667 | if (S_ISLNK(p->fts_statb.st_mode)) |
6f8dfca7 | 668 | return(FTS_SL); |
9f27273b | 669 | if (S_ISREG(p->fts_statb.st_mode)) |
6f8dfca7 | 670 | return(FTS_F); |
9b63b883 | 671 | return(FTS_DEFAULT); |
6f8dfca7 KB |
672 | } |
673 | ||
6f8dfca7 | 674 | #define R(type, nelem, ptr) \ |
c8f49d0a | 675 | (type *)realloc((void *)ptr, (u_int)((nelem) * sizeof(type))) |
6f8dfca7 KB |
676 | |
677 | static FTSENT * | |
9f27273b KB |
678 | fts_sort(sp, head, nitems) |
679 | FTS *sp; | |
6f8dfca7 KB |
680 | FTSENT *head; |
681 | register int nitems; | |
682 | { | |
683 | register FTSENT **ap, *p; | |
684 | ||
685 | /* | |
9f27273b | 686 | * Construct an array of pointers to the structures and call qsort(3). |
6f8dfca7 KB |
687 | * Reassemble the array in the order returned by qsort. If unable to |
688 | * sort for memory reasons, return the directory entries in their | |
689 | * current order. Allocate enough space for the current needs plus | |
690 | * 40 so we don't realloc one entry at a time. | |
691 | */ | |
9f27273b KB |
692 | if (nitems > sp->fts_nitems) { |
693 | sp->fts_nitems = nitems + 40; | |
694 | if (!(sp->fts_array = | |
695 | R(FTSENT *, sp->fts_nitems, sp->fts_array))) { | |
696 | sp->fts_nitems = 0; | |
6f8dfca7 KB |
697 | return(head); |
698 | } | |
699 | } | |
9f27273b | 700 | for (ap = sp->fts_array, p = head; p; p = p->fts_link) |
6f8dfca7 | 701 | *ap++ = p; |
9f27273b KB |
702 | qsort((void *)sp->fts_array, nitems, sizeof(FTSENT *), sp->fts_compar); |
703 | for (head = *(ap = sp->fts_array); --nitems; ++ap) | |
df589a0d KB |
704 | ap[0]->fts_link = ap[1]; |
705 | ap[0]->fts_link = NULL; | |
6f8dfca7 KB |
706 | return(head); |
707 | } | |
708 | ||
709 | static FTSENT * | |
9f27273b KB |
710 | fts_alloc(sp, name, len) |
711 | FTS *sp; | |
6f8dfca7 KB |
712 | char *name; |
713 | register int len; | |
714 | { | |
715 | register FTSENT *p; | |
716 | ||
717 | /* | |
9f27273b | 718 | * Variable sized structures; the name is the last element so |
10f860f8 KB |
719 | * we allocate enough extra space after the structure to store |
720 | * it. | |
6f8dfca7 | 721 | */ |
c8f49d0a | 722 | if (!(p = (FTSENT *)malloc((size_t)(sizeof(FTSENT) + len)))) |
6f8dfca7 | 723 | return(NULL); |
df589a0d KB |
724 | bcopy(name, p->fts_name, len + 1); |
725 | p->fts_namelen = len; | |
9f27273b | 726 | p->fts_path = sp->fts_path; |
10f860f8 KB |
727 | p->fts_instr = FTS_NOINSTR; |
728 | p->fts_cderr = 0; | |
9f27273b KB |
729 | p->fts_number = 0; |
730 | p->fts_pointer = NULL; | |
6f8dfca7 KB |
731 | return(p); |
732 | } | |
733 | ||
9f27273b | 734 | static void |
6f8dfca7 KB |
735 | fts_lfree(head) |
736 | register FTSENT *head; | |
737 | { | |
738 | register FTSENT *p; | |
739 | ||
9f27273b | 740 | /* Free a linked list of structures. */ |
6f8dfca7 | 741 | while (p = head) { |
df589a0d | 742 | head = head->fts_link; |
10f860f8 | 743 | free(p); |
6f8dfca7 KB |
744 | } |
745 | } | |
746 | ||
747 | /* | |
9f27273b KB |
748 | * Allow essentially unlimited paths; certain programs (find, rm, ls) need to |
749 | * work on any tree. Most systems will allow creation of paths much longer | |
750 | * than MAXPATHLEN, even though the kernel won't resolve them. Add an extra | |
751 | * 128 bytes to the requested size so that we don't realloc the path 2 bytes | |
752 | * at a time. | |
6f8dfca7 | 753 | */ |
c8f49d0a | 754 | static char * |
9f27273b KB |
755 | fts_path(sp, size) |
756 | FTS *sp; | |
6f8dfca7 KB |
757 | int size; |
758 | { | |
9f27273b | 759 | sp->fts_pathlen += size + 128; |
2c9e6184 KB |
760 | return(sp->fts_path = R(char, sp->fts_pathlen, sp->fts_path)); |
761 | } |