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