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) | |
0e31e24a | 9 | static char sccsid[] = "@(#)fts.c 5.10 (Berkeley) %G%"; |
6f8dfca7 KB |
10 | #endif /* LIBC_SCCS and not lint */ |
11 | ||
12 | #include <sys/param.h> | |
13 | #include <sys/stat.h> | |
c8f49d0a | 14 | #include <fcntl.h> |
6f8dfca7 KB |
15 | #include <dirent.h> |
16 | #include <errno.h> | |
17 | #include <fts.h> | |
df589a0d | 18 | #include <string.h> |
ccfce475 | 19 | #include <stdlib.h> |
6f8dfca7 | 20 | |
6f8dfca7 KB |
21 | FTSENT *fts_alloc(), *fts_build(), *fts_cycle(), *fts_sort(), *fts_root(); |
22 | short fts_stat(); | |
6f8dfca7 KB |
23 | |
24 | /* | |
25 | * Special case a root of "/" so that slashes aren't appended causing | |
26 | * paths to be written as "//foo". | |
27 | */ | |
28 | #define NAPPEND(p) \ | |
df589a0d KB |
29 | (p->fts_level == ROOTLEVEL && p->fts_pathlen == 1 && \ |
30 | p->fts_path[0] == '/' ? 0 : p->fts_pathlen) | |
6f8dfca7 | 31 | |
df589a0d KB |
32 | #define CHDIR(sp, path) (!(sp->fts_options & FTS_NOCHDIR) && chdir(path)) |
33 | #define FCHDIR(sp, fd) (!(sp->fts_options & FTS_NOCHDIR) && fchdir(fd)) | |
6f8dfca7 KB |
34 | |
35 | #define ROOTLEVEL 0 | |
36 | #define ROOTPARENTLEVEL -1 | |
37 | ||
c8f49d0a KB |
38 | /* fts_build flags */ |
39 | #define BCHILD 1 /* from ftschildren */ | |
40 | #define BREAD 2 /* from ftsread */ | |
41 | ||
6f8dfca7 KB |
42 | static FTS *stream; /* current stream pointer */ |
43 | ||
44 | FTS * | |
45 | ftsopen(argv, options, compar) | |
46 | char *argv[]; | |
47 | register int options; | |
48 | int (*compar)(); | |
49 | { | |
50 | register FTS *sp; | |
51 | register FTSENT *p, *root; | |
52 | register int nitems, maxlen; | |
53 | FTSENT *parent, *tmp; | |
c8f49d0a | 54 | char *fts_path(); |
6f8dfca7 KB |
55 | |
56 | /* allocate/initialize the stream */ | |
57 | if (!(stream = sp = (FTS *)malloc((u_int)sizeof(FTS)))) | |
58 | return(NULL); | |
59 | bzero(sp, sizeof(FTS)); | |
df589a0d | 60 | sp->fts_compar = compar; |
c8f49d0a KB |
61 | |
62 | /* | |
63 | * logical walks turn on NOCHDIR; symbolic links are just too | |
64 | * hard to deal with. | |
65 | */ | |
df589a0d | 66 | sp->fts_options = options; |
c8f49d0a KB |
67 | if (options & FTS_LOGICAL) |
68 | sp->fts_options |= FTS_NOCHDIR; | |
6f8dfca7 KB |
69 | |
70 | /* allocate/initialize root's parent */ | |
71 | if (!(parent = fts_alloc("", 0))) | |
72 | goto mem1; | |
df589a0d | 73 | parent->fts_level = ROOTPARENTLEVEL; |
6f8dfca7 KB |
74 | |
75 | /* allocate/initialize root(s) */ | |
9a0aa1ee KB |
76 | maxlen = -1; |
77 | for (root = NULL, nitems = 0; *argv; ++argv, ++nitems) { | |
78 | if (!(p = fts_root(*argv))) | |
79 | goto mem2; | |
80 | if (maxlen < p->fts_namelen) | |
81 | maxlen = p->fts_namelen; | |
82 | /* | |
83 | * if comparison routine supplied, traverse in sorted | |
84 | * order; otherwise traverse in the order specified. | |
85 | */ | |
86 | if (compar) { | |
87 | p->fts_link = root; | |
88 | root = p; | |
89 | p->fts_accpath = p->fts_name; | |
0e31e24a KB |
90 | if (!(options & FTS_NOSTAT)) |
91 | p->fts_info = fts_stat(p, 0); | |
9a0aa1ee KB |
92 | } else { |
93 | p->fts_link = NULL; | |
94 | if (!root) | |
95 | tmp = root = p; | |
96 | else { | |
97 | tmp->fts_link = p; | |
98 | tmp = p; | |
6f8dfca7 | 99 | } |
6f8dfca7 | 100 | } |
9a0aa1ee KB |
101 | p->fts_level = ROOTLEVEL; |
102 | p->fts_parent = parent; | |
6f8dfca7 | 103 | } |
9a0aa1ee KB |
104 | if (compar && nitems > 1) |
105 | root = fts_sort(root, nitems); | |
6f8dfca7 | 106 | |
6f8dfca7 | 107 | /* |
ccfce475 KB |
108 | * allocate a dummy pointer and make ftsread think that we've just |
109 | * finished the node before the root(s); set p->fts_info to FTS_NS | |
110 | * so that everything about the "current" node is ignored. | |
6f8dfca7 | 111 | */ |
ccfce475 KB |
112 | if (!(sp->fts_cur = fts_alloc("", 0))) |
113 | goto mem2; | |
114 | sp->fts_cur->fts_link = root; | |
115 | sp->fts_cur->fts_info = FTS_NS; | |
116 | ||
117 | /* start out with at least 1K+ of path space */ | |
118 | if (!fts_path(MAX(maxlen, MAXPATHLEN))) | |
119 | goto mem3; | |
6f8dfca7 KB |
120 | |
121 | /* | |
c8f49d0a KB |
122 | * if using chdir(2), grab a file descriptor pointing to dot to insure |
123 | * that we can get back here; this could be avoided for some paths, | |
124 | * but almost certainly not worth the effort. Slashes, symbolic links, | |
125 | * and ".." are all fairly nasty problems. Note, if we can't get the | |
126 | * descriptor we run anyway, just more slowly. | |
6f8dfca7 | 127 | */ |
df589a0d | 128 | if (!(options & FTS_NOCHDIR) && |
c8f49d0a | 129 | (sp->fts_sd = open(".", O_RDONLY, 0)) < 0) |
df589a0d | 130 | sp->fts_options |= FTS_NOCHDIR; |
6f8dfca7 KB |
131 | |
132 | return(sp); | |
133 | ||
c8f49d0a | 134 | mem3: (void)free((void *)sp->fts_cur); |
6f8dfca7 | 135 | mem2: fts_lfree(root); |
c8f49d0a KB |
136 | (void)free((void *)parent); |
137 | mem1: (void)free((void *)sp); | |
6f8dfca7 KB |
138 | return(NULL); |
139 | } | |
140 | ||
141 | static | |
142 | fts_load(p) | |
143 | register FTSENT *p; | |
144 | { | |
145 | register int len; | |
146 | register char *cp; | |
147 | ||
148 | /* | |
149 | * load the stream structure for the next traversal; set the | |
150 | * accpath field specially so the chdir gets done to the right | |
151 | * place and the user can access the first node. | |
152 | */ | |
df589a0d KB |
153 | len = p->fts_pathlen = p->fts_namelen; |
154 | bcopy(p->fts_name, stream->fts_path, len + 1); | |
155 | if ((cp = rindex(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) { | |
6f8dfca7 | 156 | len = strlen(++cp); |
df589a0d KB |
157 | bcopy(cp, p->fts_name, len + 1); |
158 | p->fts_namelen = len; | |
6f8dfca7 | 159 | } |
df589a0d | 160 | p->fts_accpath = p->fts_path = stream->fts_path; |
6f8dfca7 KB |
161 | } |
162 | ||
163 | ftsclose(sp) | |
164 | FTS *sp; | |
165 | { | |
166 | register FTSENT *freep, *p; | |
167 | int saved_errno; | |
168 | ||
ccfce475 KB |
169 | if (sp->fts_cur) { |
170 | /* | |
171 | * this still works if we haven't read anything -- the dummy | |
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 | */ | |
175 | for (p = sp->fts_cur; p->fts_level > ROOTPARENTLEVEL;) { | |
176 | freep = p; | |
177 | p = p->fts_link ? p->fts_link : p->fts_parent; | |
c8f49d0a | 178 | (void)free((void *)freep); |
6f8dfca7 | 179 | } |
c8f49d0a | 180 | (void)free((void *)p); |
ccfce475 | 181 | } |
6f8dfca7 KB |
182 | |
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) | |
c8f49d0a | 187 | (void)free((void *)sp->fts_array); |
df589a0d | 188 | (void)free((char *)sp->fts_path); |
6f8dfca7 KB |
189 | |
190 | /* | |
191 | * return to original directory, save errno if necessary; | |
192 | * free up the directory buffer | |
193 | */ | |
df589a0d | 194 | if (!(sp->fts_options & FTS_NOCHDIR)) { |
c8f49d0a KB |
195 | saved_errno = fchdir(sp->fts_sd) ? errno : 0; |
196 | (void)close(sp->fts_sd); | |
6f8dfca7 KB |
197 | } |
198 | ||
199 | /* free up the stream pointer */ | |
c8f49d0a | 200 | (void)free((void *)sp); |
6f8dfca7 KB |
201 | |
202 | /* set errno and return */ | |
df589a0d | 203 | if (!(sp->fts_options & FTS_NOCHDIR) && saved_errno) { |
6f8dfca7 KB |
204 | errno = saved_errno; |
205 | return(-1); | |
206 | } | |
207 | return(0); | |
208 | } | |
209 | ||
210 | FTSENT * | |
211 | ftsread(sp) | |
212 | register FTS *sp; | |
213 | { | |
c8f49d0a | 214 | register FTSENT *p, *tmp; |
6f8dfca7 | 215 | register int instr; |
c8f49d0a | 216 | register char *cp; |
6f8dfca7 | 217 | static int cd; |
6f8dfca7 KB |
218 | |
219 | /* if finished or unrecoverable error, return NULL */ | |
df589a0d | 220 | if (!sp->fts_cur || sp->fts_options & FTS__STOP) |
6f8dfca7 KB |
221 | return(NULL); |
222 | ||
223 | /* set global stream pointer, and current node pointer */ | |
224 | stream = sp; | |
df589a0d | 225 | p = sp->fts_cur; |
6f8dfca7 KB |
226 | |
227 | /* save and zero out user instructions */ | |
df589a0d KB |
228 | instr = p->fts_instr; |
229 | p->fts_instr = 0; | |
6f8dfca7 KB |
230 | |
231 | /* if used link pointer for cycle detection, restore it */ | |
df589a0d KB |
232 | if (sp->fts_savelink) { |
233 | p->fts_link = sp->fts_savelink; | |
234 | sp->fts_savelink = NULL; | |
6f8dfca7 KB |
235 | } |
236 | ||
237 | /* any type of file may be re-visited; re-stat and return */ | |
238 | if (instr == FTS_AGAIN) { | |
df589a0d | 239 | p->fts_info = fts_stat(p, 0); |
6f8dfca7 KB |
240 | return(p); |
241 | } | |
242 | ||
c8f49d0a KB |
243 | /* following a symbolic link */ |
244 | if (p->fts_info == FTS_SL && instr == FTS_FOLLOW) { | |
245 | p->fts_info = fts_stat(p, 1); | |
246 | return(p); | |
247 | } | |
248 | ||
249 | /* directory in pre-order */ | |
250 | if (p->fts_info == FTS_D) { | |
e8fecd88 | 251 | /* if skipped or crossed mount point, do post-order visit */ |
97bb157b KB |
252 | if (instr == FTS_SKIP || sp->fts_options & FTS_XDEV && |
253 | p->fts_statb.st_dev != sp->sdev) { | |
df589a0d KB |
254 | if (sp->fts_child) { |
255 | fts_lfree(sp->fts_child); | |
256 | sp->fts_child = NULL; | |
6f8dfca7 | 257 | } |
e8fecd88 KB |
258 | p->fts_info = FTS_DP; |
259 | return(p); | |
c8f49d0a KB |
260 | } |
261 | ||
262 | /* read the directory if necessary, and return first entry */ | |
263 | if (sp->fts_child) | |
264 | if (CHDIR(sp, p->fts_accpath)) { | |
265 | fts_lfree(sp->fts_child); | |
266 | p->fts_info = FTS_DNX; | |
267 | } else { | |
268 | p = sp->fts_child; | |
269 | cp = sp->fts_path + NAPPEND(p->fts_parent); | |
270 | *cp++ = '/'; | |
271 | bcopy(p->fts_name, cp, p->fts_namelen + 1); | |
272 | } | |
273 | else { | |
274 | if (!(sp->fts_child = fts_build(sp, BREAD))) | |
6f8dfca7 | 275 | return(p); |
df589a0d | 276 | p = sp->fts_child; |
6f8dfca7 | 277 | } |
c8f49d0a KB |
278 | sp->fts_child = NULL; |
279 | return(sp->fts_cur = p); | |
6f8dfca7 KB |
280 | } |
281 | ||
c8f49d0a KB |
282 | /* move to next node on this level */ |
283 | next: tmp = p; | |
284 | if (p = p->fts_link) { | |
6f8dfca7 KB |
285 | /* |
286 | * if root level node, set up paths and return. If not the | |
287 | * first time, and it's not an absolute pathname, get back | |
c8f49d0a | 288 | * to starting directory. |
6f8dfca7 | 289 | */ |
df589a0d | 290 | if (p->fts_level == ROOTLEVEL) { |
6f8dfca7 | 291 | fts_load(p); |
c8f49d0a | 292 | (void)free((void *)tmp); |
ccfce475 | 293 | if (cd && |
c8f49d0a KB |
294 | p->fts_path[0] != '/' && FCHDIR(sp, sp->fts_sd)) { |
295 | /* should never happen... */ | |
296 | p->fts_path = "starting directory"; | |
ccfce475 KB |
297 | p->fts_info = FTS_ERR; |
298 | sp->fts_options |= FTS__STOP; | |
299 | return(sp->fts_cur = p); | |
c8f49d0a | 300 | } |
ccfce475 | 301 | cd = 1; |
df589a0d | 302 | p->fts_info = fts_stat(p, 0); |
97bb157b | 303 | sp->sdev = p->fts_statb.st_dev; |
6f8dfca7 | 304 | } else { |
c8f49d0a KB |
305 | (void)free((void *)tmp); |
306 | ||
307 | /* user may have called ftsset on node */ | |
308 | if (p->fts_instr == FTS_SKIP) | |
309 | goto next; | |
310 | if (p->fts_instr == FTS_FOLLOW) { | |
311 | p->fts_info = fts_stat(p, 1); | |
312 | p->fts_instr = 0; | |
313 | } | |
314 | ||
315 | /* fill in the paths */ | |
df589a0d | 316 | cp = sp->fts_path + NAPPEND(p->fts_parent); |
6f8dfca7 | 317 | *cp++ = '/'; |
df589a0d | 318 | bcopy(p->fts_name, cp, p->fts_namelen + 1); |
c8f49d0a KB |
319 | |
320 | /* check for directory cycles */ | |
df589a0d KB |
321 | if (p->fts_info == FTS_D && (tmp = fts_cycle(p))) { |
322 | sp->fts_savelink = p->fts_link; | |
323 | p->fts_link = tmp; | |
c8f49d0a | 324 | p->fts_info = FTS_DC; |
6f8dfca7 KB |
325 | } |
326 | } | |
df589a0d | 327 | return(sp->fts_cur = p); |
6f8dfca7 KB |
328 | } |
329 | ||
c8f49d0a KB |
330 | /* move to parent */ |
331 | p = tmp->fts_parent; | |
332 | (void)free((void *)tmp); | |
333 | ||
df589a0d | 334 | if (p->fts_level == ROOTPARENTLEVEL) { |
6f8dfca7 KB |
335 | /* |
336 | * done; free everything up and set errno to 0 so the user | |
337 | * can distinguish between error and EOF. | |
338 | */ | |
c8f49d0a | 339 | (void)free((void *)p); |
6f8dfca7 | 340 | errno = 0; |
df589a0d | 341 | return(sp->fts_cur = NULL); |
6f8dfca7 KB |
342 | } |
343 | ||
df589a0d | 344 | sp->fts_path[p->fts_pathlen] = '\0'; |
6f8dfca7 | 345 | if (CHDIR(sp, "..")) { |
df589a0d KB |
346 | sp->fts_options |= FTS__STOP; |
347 | p->fts_info = FTS_ERR; | |
6f8dfca7 | 348 | } else |
df589a0d KB |
349 | p->fts_info = FTS_DP; |
350 | return(sp->fts_cur = p); | |
6f8dfca7 KB |
351 | } |
352 | ||
353 | /* | |
354 | * ftsset takes the stream as an argument although it's not used in this | |
355 | * implementation; it would be necessary if anyone wanted to add global | |
356 | * semantics to fts using ftsset. A possible error return is allowed for | |
357 | * similar reasons. | |
358 | */ | |
359 | /* ARGSUSED */ | |
360 | ftsset(sp, p, instr) | |
361 | FTS *sp; | |
362 | FTSENT *p; | |
363 | int instr; | |
364 | { | |
df589a0d | 365 | p->fts_instr = instr; |
6f8dfca7 KB |
366 | return(0); |
367 | } | |
368 | ||
369 | FTSENT * | |
370 | ftschildren(sp) | |
371 | register FTS *sp; | |
372 | { | |
c8f49d0a KB |
373 | register FTSENT *p; |
374 | int fd; | |
375 | ||
6f8dfca7 KB |
376 | /* |
377 | * set errno to 0 so that user can tell the difference between an | |
378 | * error and a directory without entries. | |
379 | */ | |
380 | errno = 0; | |
c8f49d0a KB |
381 | p = sp->fts_cur; |
382 | if (p->fts_info != FTS_D || sp->fts_options & FTS__STOP) | |
6f8dfca7 | 383 | return(NULL); |
df589a0d KB |
384 | if (sp->fts_child) |
385 | fts_lfree(sp->fts_child); | |
c8f49d0a KB |
386 | |
387 | /* | |
388 | * if using chdir on a relative path and called BEFORE ftsread on the | |
389 | * root of a traversal, we can lose because we need to chdir into the | |
390 | * subdirectory, and we don't know where the current directory is to | |
391 | * get back so that the upcoming chdir by ftsread will work. | |
392 | */ | |
393 | if (p->fts_level != ROOTLEVEL || p->fts_accpath[0] == '/' || | |
394 | sp->fts_options & FTS_NOCHDIR) | |
395 | return(sp->fts_child = fts_build(sp, BCHILD)); | |
396 | ||
397 | if ((fd = open(".", O_RDONLY, 0)) < 0) | |
398 | return(NULL); | |
399 | sp->fts_child = fts_build(sp, BCHILD); | |
400 | if (fchdir(fd)) | |
401 | return(NULL); | |
402 | (void)close(fd); | |
403 | return(sp->fts_child); | |
6f8dfca7 KB |
404 | } |
405 | ||
406 | #define ISDOT(a) (a[0] == '.' && (!a[1] || a[1] == '.' && !a[2])) | |
407 | ||
c8f49d0a KB |
408 | FTSENT * |
409 | fts_build(sp, type) | |
6f8dfca7 | 410 | register FTS *sp; |
c8f49d0a | 411 | int type; |
6f8dfca7 KB |
412 | { |
413 | register struct dirent *dp; | |
414 | register FTSENT *p, *head; | |
415 | register int nitems; | |
416 | DIR *dirp; | |
1730d75f | 417 | int descend, len, level, maxlen, nlinks, saved_errno; |
6f8dfca7 KB |
418 | char *cp; |
419 | ||
df589a0d KB |
420 | p = sp->fts_cur; |
421 | if (!(dirp = opendir(p->fts_accpath))) { | |
c8f49d0a | 422 | if (type == BREAD) { |
6f8dfca7 | 423 | errno = 0; |
df589a0d | 424 | p->fts_info = FTS_DNR; |
6f8dfca7 KB |
425 | } |
426 | return(NULL); | |
427 | } | |
6f8dfca7 KB |
428 | |
429 | /* | |
430 | * the real slowdown in walking the tree is the stat calls. If | |
431 | * FTS_NOSTAT is set and it's a physical walk (so that symbolic | |
432 | * links can't be directories), fts assumes that the number of | |
433 | * subdirectories in a node is equal to the number of links to | |
434 | * the parent. This allows stat calls to be skipped in any leaf | |
435 | * directories and for any nodes after the directories in the | |
436 | * parent node have been found. This empirically cuts the stat | |
437 | * calls by about 2/3. | |
438 | */ | |
df589a0d KB |
439 | nlinks = |
440 | sp->fts_options & FTS_NOSTAT && sp->fts_options & FTS_PHYSICAL ? | |
441 | p->fts_statb.st_nlink - (sp->fts_options & FTS_SEEDOT ? 0 : 2) : -1; | |
6f8dfca7 | 442 | |
c8f49d0a KB |
443 | /* if told to descend or found links and not told not to descend. */ |
444 | if (nlinks || type == BREAD) { | |
1730d75f | 445 | if (FCHDIR(sp, dirfd(dirp))) { |
c8f49d0a | 446 | if (type == BREAD) { |
1730d75f | 447 | errno = 0; |
df589a0d | 448 | p->fts_info = FTS_DNX; |
1730d75f | 449 | } |
c8f49d0a | 450 | (void)closedir(dirp); |
1730d75f KB |
451 | return(NULL); |
452 | } | |
453 | descend = 1; | |
454 | } else | |
455 | descend = 0; | |
456 | ||
9b63b883 | 457 | /* get max file name length that can be stored in current path */ |
df589a0d | 458 | maxlen = sp->fts_pathlen - p->fts_pathlen - 1; |
9b63b883 | 459 | |
df589a0d | 460 | cp = sp->fts_path + (len = NAPPEND(p)); |
9b63b883 KB |
461 | *cp++ = '/'; |
462 | ||
df589a0d | 463 | level = p->fts_level + 1; |
9b63b883 | 464 | |
6f8dfca7 KB |
465 | /* read the directory, attching each new entry to the `link' pointer */ |
466 | for (head = NULL, nitems = 0; dp = readdir(dirp);) { | |
df589a0d | 467 | if (ISDOT(dp->d_name) && !(sp->fts_options & FTS_SEEDOT)) |
6f8dfca7 KB |
468 | continue; |
469 | ||
470 | if (!(p = fts_alloc(dp->d_name, dp->d_namlen))) { | |
471 | saved_errno = errno; | |
472 | goto mem1; | |
473 | } | |
474 | if (dp->d_namlen > maxlen) { | |
475 | if (!fts_path((int)dp->d_namlen)) { | |
476 | /* quit: this stream no longer has a path */ | |
df589a0d | 477 | sp->fts_options |= FTS__STOP; |
6f8dfca7 | 478 | saved_errno = errno; |
c8f49d0a | 479 | (void)free((void *)p); |
6f8dfca7 | 480 | mem1: fts_lfree(head); |
c8f49d0a | 481 | if (type == BREAD) |
df589a0d | 482 | p->fts_info = FTS_ERR; |
1730d75f | 483 | if (descend && CHDIR(sp, "..")) { |
6f8dfca7 | 484 | saved_errno = errno; |
df589a0d | 485 | sp->fts_options |= FTS__STOP; |
6f8dfca7 KB |
486 | } |
487 | errno = saved_errno; | |
c8f49d0a | 488 | (void)closedir(dirp); |
6f8dfca7 KB |
489 | return(NULL); |
490 | } | |
df589a0d | 491 | maxlen = sp->fts_pathlen - sp->fts_cur->fts_pathlen - 1; |
6f8dfca7 KB |
492 | } |
493 | ||
df589a0d KB |
494 | p->fts_pathlen = len + dp->d_namlen + 1; |
495 | p->fts_accpath = | |
496 | sp->fts_options & FTS_NOCHDIR ? p->fts_path : p->fts_name; | |
6f8dfca7 | 497 | |
df589a0d KB |
498 | p->fts_parent = sp->fts_cur; |
499 | p->fts_level = level; | |
6f8dfca7 KB |
500 | |
501 | if (nlinks) { | |
502 | /* make sure fts_stat has a filename to stat */ | |
df589a0d KB |
503 | if (sp->fts_options & FTS_NOCHDIR) |
504 | bcopy(p->fts_name, cp, p->fts_namelen + 1); | |
505 | p->fts_info = fts_stat(p, 0); | |
506 | if (nlinks > 0 && (p->fts_info == FTS_D || | |
507 | p->fts_info == FTS_DNR || p->fts_info == FTS_DNX)) | |
6f8dfca7 KB |
508 | --nlinks; |
509 | } else | |
df589a0d | 510 | p->fts_info = FTS_NS; |
6f8dfca7 | 511 | |
df589a0d | 512 | p->fts_link = head; |
6f8dfca7 KB |
513 | head = p; |
514 | ++nitems; | |
515 | } | |
516 | (void)closedir(dirp); | |
517 | ||
c8f49d0a KB |
518 | /* reset the path */ |
519 | if (cp - 1 > sp->fts_path) | |
520 | --cp; | |
521 | *cp = '\0'; | |
522 | ||
523 | /* | |
524 | * if descended: if were called from ftsread and didn't find anything, | |
525 | * or were called from ftschildren, get back. | |
526 | */ | |
527 | if (descend && (!nitems || type == BCHILD) && CHDIR(sp, "..")) { | |
df589a0d KB |
528 | sp->fts_options |= FTS__STOP; |
529 | p->fts_info = FTS_ERR; | |
1730d75f KB |
530 | return(NULL); |
531 | } | |
532 | ||
6f8dfca7 | 533 | if (!nitems) { |
c8f49d0a | 534 | if (type == BREAD) |
df589a0d | 535 | p->fts_info = FTS_DP; |
6f8dfca7 KB |
536 | return(NULL); |
537 | } | |
538 | ||
df589a0d | 539 | if (sp->fts_compar && nitems > 1) |
6f8dfca7 KB |
540 | head = fts_sort(head, nitems); |
541 | ||
c8f49d0a KB |
542 | if (type == BREAD) { |
543 | *cp = '/'; | |
544 | bcopy(head->fts_name, cp + 1, head->fts_namelen + 1); | |
545 | } | |
6f8dfca7 KB |
546 | return(head); |
547 | } | |
548 | ||
549 | static short | |
550 | fts_stat(p, symflag) | |
551 | register FTSENT *p; | |
552 | int symflag; | |
553 | { | |
6f8dfca7 KB |
554 | /* |
555 | * detection of symbolic links w/o targets. If FTS_FOLLOW is set, | |
556 | * the symlink structure is overwritten with the stat structure of | |
557 | * the target. | |
558 | */ | |
df589a0d KB |
559 | if (stream->fts_options & FTS_LOGICAL || symflag) { |
560 | if (stat(p->fts_accpath, &p->fts_statb)) | |
561 | return(symflag || !lstat(p->fts_accpath, | |
562 | &p->fts_statb) ? FTS_SLNONE : FTS_ERR); | |
563 | } else if (lstat(p->fts_accpath, &p->fts_statb)) | |
6f8dfca7 KB |
564 | return(FTS_ERR); |
565 | ||
df589a0d | 566 | switch(p->fts_statb.st_mode&S_IFMT) { |
6f8dfca7 | 567 | case S_IFDIR: |
6f8dfca7 KB |
568 | return(FTS_D); |
569 | case S_IFLNK: | |
570 | return(FTS_SL); | |
571 | case S_IFREG: | |
572 | return(FTS_F); | |
6f8dfca7 | 573 | } |
9b63b883 | 574 | return(FTS_DEFAULT); |
6f8dfca7 KB |
575 | } |
576 | ||
577 | static FTSENT * | |
578 | fts_cycle(p) | |
579 | register FTSENT *p; | |
580 | { | |
581 | register dev_t dev; | |
582 | register ino_t ino; | |
583 | ||
584 | /* | |
585 | * cycle detection is brute force; if the tree gets deep enough or | |
586 | * the number of symbolic links to directories is really high | |
587 | * something faster might be worthwhile. | |
588 | */ | |
df589a0d KB |
589 | dev = p->fts_statb.st_dev; |
590 | ino = p->fts_statb.st_ino; | |
591 | for (p = p->fts_parent; p->fts_level > ROOTLEVEL; p = p->fts_parent) | |
592 | if (ino == p->fts_statb.st_ino && dev == p->fts_statb.st_dev) | |
6f8dfca7 KB |
593 | return(p); |
594 | return(NULL); | |
595 | } | |
596 | ||
597 | #define R(type, nelem, ptr) \ | |
c8f49d0a | 598 | (type *)realloc((void *)ptr, (u_int)((nelem) * sizeof(type))) |
6f8dfca7 KB |
599 | |
600 | static FTSENT * | |
601 | fts_sort(head, nitems) | |
602 | FTSENT *head; | |
603 | register int nitems; | |
604 | { | |
605 | register FTSENT **ap, *p; | |
606 | ||
607 | /* | |
608 | * construct an array of pointers to the structures and call qsort(3). | |
609 | * Reassemble the array in the order returned by qsort. If unable to | |
610 | * sort for memory reasons, return the directory entries in their | |
611 | * current order. Allocate enough space for the current needs plus | |
612 | * 40 so we don't realloc one entry at a time. | |
613 | */ | |
df589a0d KB |
614 | if (nitems > stream->fts_nitems) { |
615 | stream->fts_nitems = nitems + 40; | |
616 | if (!(stream->fts_array = | |
617 | R(FTSENT *, stream->fts_nitems, stream->fts_array))) { | |
618 | stream->fts_nitems = 0; | |
6f8dfca7 KB |
619 | return(head); |
620 | } | |
621 | } | |
df589a0d | 622 | for (ap = stream->fts_array, p = head; p; p = p->fts_link) |
6f8dfca7 | 623 | *ap++ = p; |
c8f49d0a | 624 | qsort((void *)stream->fts_array, nitems, sizeof(FTSENT *), |
df589a0d KB |
625 | stream->fts_compar); |
626 | for (head = *(ap = stream->fts_array); --nitems; ++ap) | |
627 | ap[0]->fts_link = ap[1]; | |
628 | ap[0]->fts_link = NULL; | |
6f8dfca7 KB |
629 | return(head); |
630 | } | |
631 | ||
632 | static FTSENT * | |
633 | fts_alloc(name, len) | |
634 | char *name; | |
635 | register int len; | |
636 | { | |
637 | register FTSENT *p; | |
638 | ||
639 | /* | |
640 | * variable sized structures; the name is the last element so | |
641 | * allocate enough extra space after the structure to hold it. | |
642 | */ | |
c8f49d0a | 643 | if (!(p = (FTSENT *)malloc((size_t)(sizeof(FTSENT) + len)))) |
6f8dfca7 | 644 | return(NULL); |
df589a0d KB |
645 | bcopy(name, p->fts_name, len + 1); |
646 | p->fts_namelen = len; | |
647 | p->fts_path = stream->fts_path; | |
648 | p->fts_instr = 0; | |
649 | p->fts_local.number = 0; | |
650 | p->fts_local.pointer = NULL; | |
6f8dfca7 KB |
651 | return(p); |
652 | } | |
653 | ||
654 | static | |
655 | fts_lfree(head) | |
656 | register FTSENT *head; | |
657 | { | |
658 | register FTSENT *p; | |
659 | ||
660 | while (p = head) { | |
df589a0d | 661 | head = head->fts_link; |
c8f49d0a | 662 | (void)free((void *)p); |
6f8dfca7 KB |
663 | } |
664 | } | |
665 | ||
666 | /* | |
667 | * allow essentially unlimited paths; certain programs (find, remove, ls) | |
668 | * need to work on any tree. Most systems will allow creation of paths | |
669 | * much longer than MAXPATHLEN, even though the kernel won't resolve them. | |
670 | * Add an extra 128 bytes to the requested size so that we don't realloc | |
671 | * the path 2 bytes at a time. | |
672 | */ | |
c8f49d0a | 673 | static char * |
6f8dfca7 KB |
674 | fts_path(size) |
675 | int size; | |
676 | { | |
df589a0d | 677 | stream->fts_pathlen += size + 128; |
c8f49d0a KB |
678 | return(stream->fts_path = |
679 | R(char, stream->fts_pathlen, stream->fts_path)); | |
6f8dfca7 KB |
680 | } |
681 | ||
682 | static FTSENT * | |
683 | fts_root(name) | |
684 | register char *name; | |
685 | { | |
686 | register char *cp; | |
687 | ||
688 | /* | |
689 | * rip trailing slashes; it's somewhat unclear in POSIX 1003.1 what | |
690 | * /a/b/ really is, they don't talk about what a null path component | |
691 | * resolves to. This hopefully does what the user intended. Don't | |
692 | * allow null pathnames. | |
693 | */ | |
694 | for (cp = name; *cp; ++cp); | |
695 | if (cp == name) { | |
696 | errno = ENOENT; | |
697 | return(NULL); | |
698 | } | |
699 | while (--cp > name && *cp == '/'); | |
700 | *++cp = '\0'; | |
701 | return(fts_alloc(name, cp - name)); | |
702 | } |