1 /*-
2 * Copyright (c) 1990, 1993, 1994
3 * The Regents of the University of California. All rights reserved.
4 *
5 * %sccs.include.redist.c%
6 */
7
8 #if defined(LIBC_SCCS) && !defined(lint)
9 static char sccsid[] = "@(#)fts.c 8.6 (Berkeley) 08/14/94";
10 #endif /* LIBC_SCCS and not lint */
11
12 #include <sys/param.h>
13 #include <sys/stat.h>
14
15 #include <dirent.h>
16 #include <errno.h>
17 #include <fcntl.h>
18 #include <fts.h>
19 #include <stdlib.h>
20 #include <string.h>
21 #include <unistd.h>
22
23 static FTSENT *fts_alloc __P((FTS *, char *, int));
24 static FTSENT *fts_build __P((FTS *, int));
25 static void fts_lfree __P((FTSENT *));
26 static void fts_load __P((FTS *, FTSENT *));
27 static size_t fts_maxarglen __P((char * const *));
28 static void fts_padjust __P((FTS *, void *));
29 static int fts_palloc __P((FTS *, size_t));
30 static FTSENT *fts_sort __P((FTS *, FTSENT *, int));
31 static u_short fts_stat __P((FTS *, FTSENT *, int));
32
33 #define ISDOT(a) (a[0] == '.' && (!a[1] || a[1] == '.' && !a[2]))
34
35 #define ISSET(opt) (sp->fts_options & opt)
36 #define SET(opt) (sp->fts_options |= opt)
37
38 #define CHDIR(sp, path) (!ISSET(FTS_NOCHDIR) && chdir(path))
39 #define FCHDIR(sp, fd) (!ISSET(FTS_NOCHDIR) && fchdir(fd))
40
41 /* fts_build flags */
42 #define BCHILD 1 /* fts_children */
43 #define BNAMES 2 /* fts_children, names only */
44 #define BREAD 3 /* fts_read */
45
46 FTS *
fts_open(argv,options,compar)47 fts_open(argv, options, compar)
48 char * const *argv;
49 register int options;
50 int (*compar)();
51 {
52 register FTS *sp;
53 register FTSENT *p, *root;
54 register int nitems;
55 FTSENT *parent, *tmp;
56 int len;
57
58 /* Options check. */
59 if (options & ~FTS_OPTIONMASK) {
60 errno = EINVAL;
61 return (NULL);
62 }
63
64 /* Allocate/initialize the stream */
65 if ((sp = malloc((u_int)sizeof(FTS))) == NULL)
66 return (NULL);
67 memset(sp, 0, sizeof(FTS));
68 sp->fts_compar = compar;
69 sp->fts_options = options;
70
71 /* Logical walks turn on NOCHDIR; symbolic links are too hard. */
72 if (ISSET(FTS_LOGICAL))
73 SET(FTS_NOCHDIR);
74
75 /*
76 * Start out with 1K of path space, and enough, in any case,
77 * to hold the user's paths.
78 */
79 if (fts_palloc(sp, MAX(fts_maxarglen(argv), MAXPATHLEN)))
80 goto mem1;
81
82 /* Allocate/initialize root's parent. */
83 if ((parent = fts_alloc(sp, "", 0)) == NULL)
84 goto mem2;
85 parent->fts_level = FTS_ROOTPARENTLEVEL;
86
87 /* Allocate/initialize root(s). */
88 for (root = NULL, nitems = 0; *argv; ++argv, ++nitems) {
89 /* Don't allow zero-length paths. */
90 if ((len = strlen(*argv)) == 0) {
91 errno = ENOENT;
92 goto mem3;
93 }
94
95 p = fts_alloc(sp, *argv, len);
96 p->fts_level = FTS_ROOTLEVEL;
97 p->fts_parent = parent;
98 p->fts_accpath = p->fts_name;
99 p->fts_info = fts_stat(sp, p, ISSET(FTS_COMFOLLOW));
100
101 /* Command-line "." and ".." are real directories. */
102 if (p->fts_info == FTS_DOT)
103 p->fts_info = FTS_D;
104
105 /*
106 * If comparison routine supplied, traverse in sorted
107 * order; otherwise traverse in the order specified.
108 */
109 if (compar) {
110 p->fts_link = root;
111 root = p;
112 } else {
113 p->fts_link = NULL;
114 if (root == NULL)
115 tmp = root = p;
116 else {
117 tmp->fts_link = p;
118 tmp = p;
119 }
120 }
121 }
122 if (compar && nitems > 1)
123 root = fts_sort(sp, root, nitems);
124
125 /*
126 * Allocate a dummy pointer and make fts_read think that we've just
127 * finished the node before the root(s); set p->fts_info to FTS_INIT
128 * so that everything about the "current" node is ignored.
129 */
130 if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL)
131 goto mem3;
132 sp->fts_cur->fts_link = root;
133 sp->fts_cur->fts_info = FTS_INIT;
134
135 /*
136 * If using chdir(2), grab a file descriptor pointing to dot to insure
137 * that we can get back here; this could be avoided for some paths,
138 * but almost certainly not worth the effort. Slashes, symbolic links,
139 * and ".." are all fairly nasty problems. Note, if we can't get the
140 * descriptor we run anyway, just more slowly.
141 */
142 if (!ISSET(FTS_NOCHDIR) && (sp->fts_rfd = open(".", O_RDONLY, 0)) < 0)
143 SET(FTS_NOCHDIR);
144
145 return (sp);
146
147 mem3: fts_lfree(root);
148 free(parent);
149 mem2: free(sp->fts_path);
150 mem1: free(sp);
151 return (NULL);
152 }
153
154 static void
fts_load(sp,p)155 fts_load(sp, p)
156 FTS *sp;
157 register FTSENT *p;
158 {
159 register int len;
160 register char *cp;
161
162 /*
163 * Load the stream structure for the next traversal. Since we don't
164 * actually enter the directory until after the preorder visit, set
165 * the fts_accpath field specially so the chdir gets done to the right
166 * place and the user can access the first node. From fts_open it's
167 * known that the path will fit.
168 */
169 len = p->fts_pathlen = p->fts_namelen;
170 memmove(sp->fts_path, p->fts_name, len + 1);
171 if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) {
172 len = strlen(++cp);
173 memmove(p->fts_name, cp, len + 1);
174 p->fts_namelen = len;
175 }
176 p->fts_accpath = p->fts_path = sp->fts_path;
177 sp->fts_dev = p->fts_dev;
178 }
179
180 int
fts_close(sp)181 fts_close(sp)
182 FTS *sp;
183 {
184 register FTSENT *freep, *p;
185 int saved_errno;
186
187 /*
188 * This still works if we haven't read anything -- the dummy structure
189 * points to the root list, so we step through to the end of the root
190 * list which has a valid parent pointer.
191 */
192 if (sp->fts_cur) {
193 for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {
194 freep = p;
195 p = p->fts_link ? p->fts_link : p->fts_parent;
196 free(freep);
197 }
198 free(p);
199 }
200
201 /* Free up child linked list, sort array, path buffer. */
202 if (sp->fts_child)
203 fts_lfree(sp->fts_child);
204 if (sp->fts_array)
205 free(sp->fts_array);
206 free(sp->fts_path);
207
208 /* Return to original directory, save errno if necessary. */
209 if (!ISSET(FTS_NOCHDIR)) {
210 saved_errno = fchdir(sp->fts_rfd) ? errno : 0;
211 (void)close(sp->fts_rfd);
212 }
213
214 /* Free up the stream pointer. */
215 free(sp);
216
217 /* Set errno and return. */
218 if (!ISSET(FTS_NOCHDIR) && saved_errno) {
219 errno = saved_errno;
220 return (-1);
221 }
222 return (0);
223 }
224
225 /*
226 * Special case a root of "/" so that slashes aren't appended which would
227 * cause paths to be written as "//foo".
228 */
229 #define NAPPEND(p) \
230 (p->fts_level == FTS_ROOTLEVEL && p->fts_pathlen == 1 && \
231 p->fts_path[0] == '/' ? 0 : p->fts_pathlen)
232
233 FTSENT *
fts_read(sp)234 fts_read(sp)
235 register FTS *sp;
236 {
237 register FTSENT *p, *tmp;
238 register int instr;
239 register char *t;
240 int saved_errno;
241
242 /* If finished or unrecoverable error, return NULL. */
243 if (sp->fts_cur == NULL || ISSET(FTS_STOP))
244 return (NULL);
245
246 /* Set current node pointer. */
247 p = sp->fts_cur;
248
249 /* Save and zero out user instructions. */
250 instr = p->fts_instr;
251 p->fts_instr = FTS_NOINSTR;
252
253 /* Any type of file may be re-visited; re-stat and re-turn. */
254 if (instr == FTS_AGAIN) {
255 p->fts_info = fts_stat(sp, p, 0);
256 return (p);
257 }
258
259 /*
260 * Following a symlink -- SLNONE test allows application to see
261 * SLNONE and recover. If indirecting through a symlink, have
262 * keep a pointer to current location. If unable to get that
263 * pointer, follow fails.
264 */
265 if (instr == FTS_FOLLOW &&
266 (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) {
267 p->fts_info = fts_stat(sp, p, 1);
268 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR))
269 if ((p->fts_symfd = open(".", O_RDONLY, 0)) < 0) {
270 p->fts_errno = errno;
271 p->fts_info = FTS_ERR;
272 } else
273 p->fts_flags |= FTS_SYMFOLLOW;
274 return (p);
275 }
276
277 /* Directory in pre-order. */
278 if (p->fts_info == FTS_D) {
279 /* If skipped or crossed mount point, do post-order visit. */
280 if (instr == FTS_SKIP ||
281 ISSET(FTS_XDEV) && p->fts_dev != sp->fts_dev) {
282 if (p->fts_flags & FTS_SYMFOLLOW)
283 (void)close(p->fts_symfd);
284 if (sp->fts_child) {
285 fts_lfree(sp->fts_child);
286 sp->fts_child = NULL;
287 }
288 p->fts_info = FTS_DP;
289 return (p);
290 }
291
292 /* Rebuild if only read the names and now traversing. */
293 if (sp->fts_child && sp->fts_options & FTS_NAMEONLY) {
294 sp->fts_options &= ~FTS_NAMEONLY;
295 fts_lfree(sp->fts_child);
296 sp->fts_child = NULL;
297 }
298
299 /*
300 * Cd to the subdirectory.
301 *
302 * If have already read and now fail to chdir, whack the list
303 * to make the names come out right, and set the parent errno
304 * so the application will eventually get an error condition.
305 * Set the FTS_DONTCHDIR flag so that when we logically change
306 * directories back to the parent we don't do a chdir.
307 *
308 * If haven't read do so. If the read fails, fts_build sets
309 * FTS_STOP or the fts_info field of the node.
310 */
311 if (sp->fts_child) {
312 if (CHDIR(sp, p->fts_accpath)) {
313 p->fts_errno = errno;
314 p->fts_flags |= FTS_DONTCHDIR;
315 for (p = sp->fts_child; p; p = p->fts_link)
316 p->fts_accpath =
317 p->fts_parent->fts_accpath;
318 }
319 } else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) {
320 if (ISSET(FTS_STOP))
321 return (NULL);
322 return (p);
323 }
324 p = sp->fts_child;
325 sp->fts_child = NULL;
326 goto name;
327 }
328
329 /* Move to the next node on this level. */
330 next: tmp = p;
331 if (p = p->fts_link) {
332 free(tmp);
333
334 /*
335 * If reached the top, return to the original directory, and
336 * load the paths for the next root.
337 */
338 if (p->fts_level == FTS_ROOTLEVEL) {
339 if (!ISSET(FTS_NOCHDIR) && FCHDIR(sp, sp->fts_rfd)) {
340 SET(FTS_STOP);
341 return (NULL);
342 }
343 fts_load(sp, p);
344 return (sp->fts_cur = p);
345 }
346
347 /*
348 * User may have called fts_set on the node. If skipped,
349 * ignore. If followed, get a file descriptor so we can
350 * get back if necessary.
351 */
352 if (p->fts_instr == FTS_SKIP)
353 goto next;
354 if (p->fts_instr == FTS_FOLLOW) {
355 p->fts_info = fts_stat(sp, p, 1);
356 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR))
357 if ((p->fts_symfd =
358 open(".", O_RDONLY, 0)) < 0) {
359 p->fts_errno = errno;
360 p->fts_info = FTS_ERR;
361 } else
362 p->fts_flags |= FTS_SYMFOLLOW;
363 p->fts_instr = FTS_NOINSTR;
364 }
365
366 name: t = sp->fts_path + NAPPEND(p->fts_parent);
367 *t++ = '/';
368 memmove(t, p->fts_name, p->fts_namelen + 1);
369 return (sp->fts_cur = p);
370 }
371
372 /* Move up to the parent node. */
373 p = tmp->fts_parent;
374 free(tmp);
375
376 if (p->fts_level == FTS_ROOTPARENTLEVEL) {
377 /*
378 * Done; free everything up and set errno to 0 so the user
379 * can distinguish between error and EOF.
380 */
381 free(p);
382 errno = 0;
383 return (sp->fts_cur = NULL);
384 }
385
386 /* Nul terminate the pathname. */
387 sp->fts_path[p->fts_pathlen] = '\0';
388
389 /*
390 * Return to the parent directory. If at a root node or came through
391 * a symlink, go back through the file descriptor. Otherwise, cd up
392 * one directory.
393 */
394 if (p->fts_level == FTS_ROOTLEVEL) {
395 if (!ISSET(FTS_NOCHDIR) && FCHDIR(sp, sp->fts_rfd)) {
396 SET(FTS_STOP);
397 return (NULL);
398 }
399 } else if (p->fts_flags & FTS_SYMFOLLOW) {
400 if (FCHDIR(sp, p->fts_symfd)) {
401 saved_errno = errno;
402 (void)close(p->fts_symfd);
403 errno = saved_errno;
404 SET(FTS_STOP);
405 return (NULL);
406 }
407 (void)close(p->fts_symfd);
408 } else if (!(p->fts_flags & FTS_DONTCHDIR)) {
409 if (CHDIR(sp, "..")) {
410 SET(FTS_STOP);
411 return (NULL);
412 }
413 }
414 p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;
415 return (sp->fts_cur = p);
416 }
417
418 /*
419 * Fts_set takes the stream as an argument although it's not used in this
420 * implementation; it would be necessary if anyone wanted to add global
421 * semantics to fts using fts_set. An error return is allowed for similar
422 * reasons.
423 */
424 /* ARGSUSED */
425 int
fts_set(sp,p,instr)426 fts_set(sp, p, instr)
427 FTS *sp;
428 FTSENT *p;
429 int instr;
430 {
431 if (instr && instr != FTS_AGAIN && instr != FTS_FOLLOW &&
432 instr != FTS_NOINSTR && instr != FTS_SKIP) {
433 errno = EINVAL;
434 return (1);
435 }
436 p->fts_instr = instr;
437 return (0);
438 }
439
440 FTSENT *
fts_children(sp,instr)441 fts_children(sp, instr)
442 register FTS *sp;
443 int instr;
444 {
445 register FTSENT *p;
446 int fd;
447
448 if (instr && instr != FTS_NAMEONLY) {
449 errno = EINVAL;
450 return (NULL);
451 }
452
453 /* Set current node pointer. */
454 p = sp->fts_cur;
455
456 /*
457 * Errno set to 0 so user can distinguish empty directory from
458 * an error.
459 */
460 errno = 0;
461
462 /* Fatal errors stop here. */
463 if (ISSET(FTS_STOP))
464 return (NULL);
465
466 /* Return logical hierarchy of user's arguments. */
467 if (p->fts_info == FTS_INIT)
468 return (p->fts_link);
469
470 /*
471 * If not a directory being visited in pre-order, stop here. Could
472 * allow FTS_DNR, assuming the user has fixed the problem, but the
473 * same effect is available with FTS_AGAIN.
474 */
475 if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */)
476 return (NULL);
477
478 /* Free up any previous child list. */
479 if (sp->fts_child)
480 fts_lfree(sp->fts_child);
481
482 if (instr == FTS_NAMEONLY) {
483 sp->fts_options |= FTS_NAMEONLY;
484 instr = BNAMES;
485 } else
486 instr = BCHILD;
487
488 /*
489 * If using chdir on a relative path and called BEFORE fts_read does
490 * its chdir to the root of a traversal, we can lose -- we need to
491 * chdir into the subdirectory, and we don't know where the current
492 * directory is, so we can't get back so that the upcoming chdir by
493 * fts_read will work.
494 */
495 if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' ||
496 ISSET(FTS_NOCHDIR))
497 return (sp->fts_child = fts_build(sp, instr));
498
499 if ((fd = open(".", O_RDONLY, 0)) < 0)
500 return (NULL);
501 sp->fts_child = fts_build(sp, instr);
502 if (fchdir(fd))
503 return (NULL);
504 (void)close(fd);
505 return (sp->fts_child);
506 }
507
508 /*
509 * This is the tricky part -- do not casually change *anything* in here. The
510 * idea is to build the linked list of entries that are used by fts_children
511 * and fts_read. There are lots of special cases.
512 *
513 * The real slowdown in walking the tree is the stat calls. If FTS_NOSTAT is
514 * set and it's a physical walk (so that symbolic links can't be directories),
515 * we can do things quickly. First, if it's a 4.4BSD file system, the type
516 * of the file is in the directory entry. Otherwise, we assume that the number
517 * of subdirectories in a node is equal to the number of links to the parent.
518 * The former skips all stat calls. The latter skips stat calls in any leaf
519 * directories and for any files after the subdirectories in the directory have
520 * been found, cutting the stat calls by about 2/3.
521 */
522 static FTSENT *
fts_build(sp,type)523 fts_build(sp, type)
524 register FTS *sp;
525 int type;
526 {
527 register struct dirent *dp;
528 register FTSENT *p, *head;
529 register int nitems;
530 FTSENT *cur, *tail;
531 DIR *dirp;
532 void *adjaddr;
533 int cderrno, descend, len, level, maxlen, nlinks, oflag, saved_errno;
534 char *cp;
535
536 /* Set current node pointer. */
537 cur = sp->fts_cur;
538
539 /*
540 * Open the directory for reading. If this fails, we're done.
541 * If being called from fts_read, set the fts_info field.
542 */
543 #ifdef FTS_WHITEOUT
544 if (ISSET(FTS_WHITEOUT))
545 oflag = DTF_NODUP|DTF_REWIND;
546 else
547 oflag = DTF_HIDEW|DTF_NODUP|DTF_REWIND;
548 #else
549 #define __opendir2(path, flag) opendir(path)
550 #endif
551 if ((dirp = __opendir2(cur->fts_accpath, oflag)) == NULL) {
552 if (type == BREAD) {
553 cur->fts_info = FTS_DNR;
554 cur->fts_errno = errno;
555 }
556 return (NULL);
557 }
558
559 /*
560 * Nlinks is the number of possible entries of type directory in the
561 * directory if we're cheating on stat calls, 0 if we're not doing
562 * any stat calls at all, -1 if we're doing stats on everything.
563 */
564 if (type == BNAMES)
565 nlinks = 0;
566 else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL))
567 nlinks = cur->fts_nlink - (ISSET(FTS_SEEDOT) ? 0 : 2);
568 else
569 nlinks = -1;
570
571 #ifdef notdef
572 (void)printf("nlinks == %d (cur: %d)\n", nlinks, cur->fts_nlink);
573 (void)printf("NOSTAT %d PHYSICAL %d SEEDOT %d\n",
574 ISSET(FTS_NOSTAT), ISSET(FTS_PHYSICAL), ISSET(FTS_SEEDOT));
575 #endif
576 /*
577 * If we're going to need to stat anything or we want to descend
578 * and stay in the directory, chdir. If this fails we keep going,
579 * but set a flag so we don't chdir after the post-order visit.
580 * We won't be able to stat anything, but we can still return the
581 * names themselves. Note, that since fts_read won't be able to
582 * chdir into the directory, it will have to return different path
583 * names than before, i.e. "a/b" instead of "b". Since the node
584 * has already been visited in pre-order, have to wait until the
585 * post-order visit to return the error. There is a special case
586 * here, if there was nothing to stat then it's not an error to
587 * not be able to stat. This is all fairly nasty. If a program
588 * needed sorted entries or stat information, they had better be
589 * checking FTS_NS on the returned nodes.
590 */
591 cderrno = 0;
592 if (nlinks || type == BREAD)
593 if (FCHDIR(sp, dirfd(dirp))) {
594 if (nlinks && type == BREAD)
595 cur->fts_errno = errno;
596 cur->fts_flags |= FTS_DONTCHDIR;
597 descend = 0;
598 cderrno = errno;
599 } else
600 descend = 1;
601 else
602 descend = 0;
603
604 /*
605 * Figure out the max file name length that can be stored in the
606 * current path -- the inner loop allocates more path as necessary.
607 * We really wouldn't have to do the maxlen calculations here, we
608 * could do them in fts_read before returning the path, but it's a
609 * lot easier here since the length is part of the dirent structure.
610 *
611 * If not changing directories set a pointer so that can just append
612 * each new name into the path.
613 */
614 maxlen = sp->fts_pathlen - cur->fts_pathlen - 1;
615 len = NAPPEND(cur);
616 if (ISSET(FTS_NOCHDIR)) {
617 cp = sp->fts_path + len;
618 *cp++ = '/';
619 }
620
621 level = cur->fts_level + 1;
622
623 /* Read the directory, attaching each entry to the `link' pointer. */
624 adjaddr = NULL;
625 for (head = tail = NULL, nitems = 0; dp = readdir(dirp);) {
626 if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))
627 continue;
628
629 if ((p = fts_alloc(sp, dp->d_name, (int)dp->d_namlen)) == NULL)
630 goto mem1;
631 if (dp->d_namlen > maxlen) {
632 if (fts_palloc(sp, (size_t)dp->d_namlen)) {
633 /*
634 * No more memory for path or structures. Save
635 * errno, free up the current structure and the
636 * structures already allocated.
637 */
638 mem1: saved_errno = errno;
639 if (p)
640 free(p);
641 fts_lfree(head);
642 (void)closedir(dirp);
643 errno = saved_errno;
644 cur->fts_info = FTS_ERR;
645 SET(FTS_STOP);
646 return (NULL);
647 }
648 adjaddr = sp->fts_path;
649 maxlen = sp->fts_pathlen - sp->fts_cur->fts_pathlen - 1;
650 }
651
652 p->fts_pathlen = len + dp->d_namlen + 1;
653 p->fts_parent = sp->fts_cur;
654 p->fts_level = level;
655
656 #ifdef FTS_WHITEOUT
657 if (dp->d_type == DT_WHT)
658 p->fts_flags |= FTS_ISW;
659 #endif
660
661 if (cderrno) {
662 if (nlinks) {
663 p->fts_info = FTS_NS;
664 p->fts_errno = cderrno;
665 } else
666 p->fts_info = FTS_NSOK;
667 p->fts_accpath = cur->fts_accpath;
668 } else if (nlinks == 0
669 #ifdef DT_DIR
670 || nlinks > 0 &&
671 dp->d_type != DT_DIR && dp->d_type != DT_UNKNOWN
672 #endif
673 ) {
674 p->fts_accpath =
675 ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name;
676 p->fts_info = FTS_NSOK;
677 } else {
678 /* Build a file name for fts_stat to stat. */
679 if (ISSET(FTS_NOCHDIR)) {
680 p->fts_accpath = p->fts_path;
681 memmove(cp, p->fts_name, p->fts_namelen + 1);
682 } else
683 p->fts_accpath = p->fts_name;
684 /* Stat it. */
685 p->fts_info = fts_stat(sp, p, 0);
686
687 /* Decrement link count if applicable. */
688 if (nlinks > 0 && (p->fts_info == FTS_D ||
689 p->fts_info == FTS_DC || p->fts_info == FTS_DOT))
690 --nlinks;
691 }
692
693 /* We walk in directory order so "ls -f" doesn't get upset. */
694 p->fts_link = NULL;
695 if (head == NULL)
696 head = tail = p;
697 else {
698 tail->fts_link = p;
699 tail = p;
700 }
701 ++nitems;
702 }
703 (void)closedir(dirp);
704
705 /*
706 * If had to realloc the path, adjust the addresses for the rest
707 * of the tree.
708 */
709 if (adjaddr)
710 fts_padjust(sp, adjaddr);
711
712 /*
713 * If not changing directories, reset the path back to original
714 * state.
715 */
716 if (ISSET(FTS_NOCHDIR)) {
717 if (cp - 1 > sp->fts_path)
718 --cp;
719 *cp = '\0';
720 }
721
722 /*
723 * If descended after called from fts_children or after called from
724 * fts_read and nothing found, get back. At the root level we use
725 * the saved fd; if one of fts_open()'s arguments is a relative path
726 * to an empty directory, we wind up here with no other way back. If
727 * can't get back, we're done.
728 */
729 if (descend && (type == BCHILD || !nitems) &&
730 (cur->fts_level == FTS_ROOTLEVEL ?
731 FCHDIR(sp, sp->fts_rfd) : CHDIR(sp, ".."))) {
732 cur->fts_info = FTS_ERR;
733 SET(FTS_STOP);
734 return (NULL);
735 }
736
737 /* If didn't find anything, return NULL. */
738 if (!nitems) {
739 if (type == BREAD)
740 cur->fts_info = FTS_DP;
741 return (NULL);
742 }
743
744 /* Sort the entries. */
745 if (sp->fts_compar && nitems > 1)
746 head = fts_sort(sp, head, nitems);
747 return (head);
748 }
749
750 static u_short
fts_stat(sp,p,follow)751 fts_stat(sp, p, follow)
752 FTS *sp;
753 register FTSENT *p;
754 int follow;
755 {
756 register FTSENT *t;
757 register dev_t dev;
758 register ino_t ino;
759 struct stat *sbp, sb;
760 int saved_errno;
761
762 /* If user needs stat info, stat buffer already allocated. */
763 sbp = ISSET(FTS_NOSTAT) ? &sb : p->fts_statp;
764
765 #ifdef FTS_WHITEOUT
766 /* check for whiteout */
767 if (p->fts_flags & FTS_ISW) {
768 if (sbp != &sb) {
769 memset(sbp, '\0', sizeof (*sbp));
770 sbp->st_mode = S_IFWHT;
771 }
772 return (FTS_W);
773 }
774 #endif
775
776 /*
777 * If doing a logical walk, or application requested FTS_FOLLOW, do
778 * a stat(2). If that fails, check for a non-existent symlink. If
779 * fail, set the errno from the stat call.
780 */
781 if (ISSET(FTS_LOGICAL) || follow) {
782 if (stat(p->fts_accpath, sbp)) {
783 saved_errno = errno;
784 if (!lstat(p->fts_accpath, sbp)) {
785 errno = 0;
786 return (FTS_SLNONE);
787 }
788 p->fts_errno = saved_errno;
789 goto err;
790 }
791 } else if (lstat(p->fts_accpath, sbp)) {
792 p->fts_errno = errno;
793 err: memset(sbp, 0, sizeof(struct stat));
794 return (FTS_NS);
795 }
796
797 if (S_ISDIR(sbp->st_mode)) {
798 /*
799 * Set the device/inode. Used to find cycles and check for
800 * crossing mount points. Also remember the link count, used
801 * in fts_build to limit the number of stat calls. It is
802 * understood that these fields are only referenced if fts_info
803 * is set to FTS_D.
804 */
805 dev = p->fts_dev = sbp->st_dev;
806 ino = p->fts_ino = sbp->st_ino;
807 p->fts_nlink = sbp->st_nlink;
808
809 if (ISDOT(p->fts_name))
810 return (FTS_DOT);
811
812 /*
813 * Cycle detection is done by brute force when the directory
814 * is first encountered. If the tree gets deep enough or the
815 * number of symbolic links to directories is high enough,
816 * something faster might be worthwhile.
817 */
818 for (t = p->fts_parent;
819 t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
820 if (ino == t->fts_ino && dev == t->fts_dev) {
821 p->fts_cycle = t;
822 return (FTS_DC);
823 }
824 return (FTS_D);
825 }
826 if (S_ISLNK(sbp->st_mode))
827 return (FTS_SL);
828 if (S_ISREG(sbp->st_mode))
829 return (FTS_F);
830 return (FTS_DEFAULT);
831 }
832
833 static FTSENT *
fts_sort(sp,head,nitems)834 fts_sort(sp, head, nitems)
835 FTS *sp;
836 FTSENT *head;
837 register int nitems;
838 {
839 register FTSENT **ap, *p;
840
841 /*
842 * Construct an array of pointers to the structures and call qsort(3).
843 * Reassemble the array in the order returned by qsort. If unable to
844 * sort for memory reasons, return the directory entries in their
845 * current order. Allocate enough space for the current needs plus
846 * 40 so don't realloc one entry at a time.
847 */
848 if (nitems > sp->fts_nitems) {
849 sp->fts_nitems = nitems + 40;
850 if ((sp->fts_array = realloc(sp->fts_array,
851 (size_t)(sp->fts_nitems * sizeof(FTSENT *)))) == NULL) {
852 sp->fts_nitems = 0;
853 return (head);
854 }
855 }
856 for (ap = sp->fts_array, p = head; p; p = p->fts_link)
857 *ap++ = p;
858 qsort((void *)sp->fts_array, nitems, sizeof(FTSENT *), sp->fts_compar);
859 for (head = *(ap = sp->fts_array); --nitems; ++ap)
860 ap[0]->fts_link = ap[1];
861 ap[0]->fts_link = NULL;
862 return (head);
863 }
864
865 static FTSENT *
fts_alloc(sp,name,namelen)866 fts_alloc(sp, name, namelen)
867 FTS *sp;
868 char *name;
869 register int namelen;
870 {
871 register FTSENT *p;
872 size_t len;
873
874 /*
875 * The file name is a variable length array and no stat structure is
876 * necessary if the user has set the nostat bit. Allocate the FTSENT
877 * structure, the file name and the stat structure in one chunk, but
878 * be careful that the stat structure is reasonably aligned. Since the
879 * fts_name field is declared to be of size 1, the fts_name pointer is
880 * namelen + 2 before the first possible address of the stat structure.
881 */
882 len = sizeof(FTSENT) + namelen;
883 if (!ISSET(FTS_NOSTAT))
884 len += sizeof(struct stat) + ALIGNBYTES;
885 if ((p = malloc(len)) == NULL)
886 return (NULL);
887
888 /* Copy the name plus the trailing NULL. */
889 memmove(p->fts_name, name, namelen + 1);
890
891 if (!ISSET(FTS_NOSTAT))
892 p->fts_statp = (struct stat *)ALIGN(p->fts_name + namelen + 2);
893 p->fts_namelen = namelen;
894 p->fts_path = sp->fts_path;
895 p->fts_errno = 0;
896 p->fts_flags = 0;
897 p->fts_instr = FTS_NOINSTR;
898 p->fts_number = 0;
899 p->fts_pointer = NULL;
900 return (p);
901 }
902
903 static void
fts_lfree(head)904 fts_lfree(head)
905 register FTSENT *head;
906 {
907 register FTSENT *p;
908
909 /* Free a linked list of structures. */
910 while (p = head) {
911 head = head->fts_link;
912 free(p);
913 }
914 }
915
916 /*
917 * Allow essentially unlimited paths; find, rm, ls should all work on any tree.
918 * Most systems will allow creation of paths much longer than MAXPATHLEN, even
919 * though the kernel won't resolve them. Add the size (not just what's needed)
920 * plus 256 bytes so don't realloc the path 2 bytes at a time.
921 */
922 static int
fts_palloc(sp,more)923 fts_palloc(sp, more)
924 FTS *sp;
925 size_t more;
926 {
927 sp->fts_pathlen += more + 256;
928 sp->fts_path = realloc(sp->fts_path, (size_t)sp->fts_pathlen);
929 return (sp->fts_path == NULL);
930 }
931
932 /*
933 * When the path is realloc'd, have to fix all of the pointers in structures
934 * already returned.
935 */
936 static void
fts_padjust(sp,addr)937 fts_padjust(sp, addr)
938 FTS *sp;
939 void *addr;
940 {
941 FTSENT *p;
942
943 #define ADJUST(p) { \
944 (p)->fts_accpath = \
945 (char *)addr + ((p)->fts_accpath - (p)->fts_path); \
946 (p)->fts_path = addr; \
947 }
948 /* Adjust the current set of children. */
949 for (p = sp->fts_child; p; p = p->fts_link)
950 ADJUST(p);
951
952 /* Adjust the rest of the tree. */
953 for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {
954 ADJUST(p);
955 p = p->fts_link ? p->fts_link : p->fts_parent;
956 }
957 }
958
959 static size_t
fts_maxarglen(argv)960 fts_maxarglen(argv)
961 char * const *argv;
962 {
963 size_t len, max;
964
965 for (max = 0; *argv; ++argv)
966 if ((len = strlen(*argv)) > max)
967 max = len;
968 return (max);
969 }
970