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