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