.
[glibc/history.git] / io / fts.c
blob8e628b481d9ba07d5abd7cc76023a63be5212b6b
1 /*-
2 * Copyright (c) 1990, 1993, 1994
3 * The Regents of the University of California. All rights reserved.
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 * 4. Neither the name of the University nor the names of its contributors
14 * may be used to endorse or promote products derived from this software
15 * without specific prior written permission.
17 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
18 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
20 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
21 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
22 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
23 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
24 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
25 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
26 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
27 * SUCH DAMAGE.
30 #if defined(LIBC_SCCS) && !defined(lint)
31 static char sccsid[] = "@(#)fts.c 8.6 (Berkeley) 8/14/94";
32 #endif /* LIBC_SCCS and not lint */
34 #include <sys/param.h>
35 #include <include/sys/stat.h>
36 #include <fcntl.h>
37 #include <dirent.h>
38 #include <errno.h>
39 #include <fts.h>
40 #include <stdlib.h>
41 #include <string.h>
42 #include <unistd.h>
45 /* Largest alignment size needed, minus one.
46 Usually long double is the worst case. */
47 #ifndef ALIGNBYTES
48 #define ALIGNBYTES (__alignof__ (long double) - 1)
49 #endif
50 /* Align P to that size. */
51 #ifndef ALIGN
52 #define ALIGN(p) (((unsigned long int) (p) + ALIGNBYTES) & ~ALIGNBYTES)
53 #endif
56 static FTSENT *fts_alloc (FTS *, const char *, size_t) internal_function;
57 static FTSENT *fts_build (FTS *, int) internal_function;
58 static void fts_lfree (FTSENT *) internal_function;
59 static void fts_load (FTS *, FTSENT *) internal_function;
60 static size_t fts_maxarglen (char * const *) internal_function;
61 static void fts_padjust (FTS *, FTSENT *) internal_function;
62 static int fts_palloc (FTS *, size_t) internal_function;
63 static FTSENT *fts_sort (FTS *, FTSENT *, int) internal_function;
64 static u_short fts_stat (FTS *, FTSENT *, int) internal_function;
65 static int fts_safe_changedir (FTS *, FTSENT *, int, const char *)
66 internal_function;
68 #ifndef MAX
69 #define MAX(a, b) ({ __typeof__ (a) _a = (a); \
70 __typeof__ (b) _b = (b); \
71 _a > _b ? _a : _b; })
72 #endif
74 #define ISDOT(a) (a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2])))
76 #define CLR(opt) (sp->fts_options &= ~(opt))
77 #define ISSET(opt) (sp->fts_options & (opt))
78 #define SET(opt) (sp->fts_options |= (opt))
80 #define FCHDIR(sp, fd) (!ISSET(FTS_NOCHDIR) && __fchdir(fd))
82 /* fts_build flags */
83 #define BCHILD 1 /* fts_children */
84 #define BNAMES 2 /* fts_children, names only */
85 #define BREAD 3 /* fts_read */
87 FTS *
88 fts_open(argv, options, compar)
89 char * const *argv;
90 register int options;
91 int (*compar) (const FTSENT **, const FTSENT **);
93 register FTS *sp;
94 register FTSENT *p, *root;
95 register int nitems;
96 FTSENT *parent = NULL;
97 FTSENT *tmp;
99 /* Options check. */
100 if (options & ~FTS_OPTIONMASK) {
101 __set_errno (EINVAL);
102 return (NULL);
105 /* Allocate/initialize the stream */
106 if ((sp = malloc((u_int)sizeof(FTS))) == NULL)
107 return (NULL);
108 memset(sp, 0, sizeof(FTS));
109 sp->fts_compar = (int (*) (const void *, const void *)) compar;
110 sp->fts_options = options;
112 /* Logical walks turn on NOCHDIR; symbolic links are too hard. */
113 if (ISSET(FTS_LOGICAL))
114 SET(FTS_NOCHDIR);
117 * Start out with 1K of path space, and enough, in any case,
118 * to hold the user's paths.
120 #ifndef MAXPATHLEN
121 #define MAXPATHLEN 1024
122 #endif
123 size_t maxarglen = fts_maxarglen(argv);
124 if (fts_palloc(sp, MAX(maxarglen, MAXPATHLEN)))
125 goto mem1;
127 /* Allocate/initialize root's parent. */
128 if (*argv != NULL) {
129 if ((parent = fts_alloc(sp, "", 0)) == NULL)
130 goto mem2;
131 parent->fts_level = FTS_ROOTPARENTLEVEL;
134 /* Allocate/initialize root(s). */
135 for (root = NULL, nitems = 0; *argv != NULL; ++argv, ++nitems) {
136 /* Don't allow zero-length paths. */
137 size_t len = strlen(*argv);
138 if (len == 0) {
139 __set_errno (ENOENT);
140 goto mem3;
143 p = fts_alloc(sp, *argv, len);
144 p->fts_level = FTS_ROOTLEVEL;
145 p->fts_parent = parent;
146 p->fts_accpath = p->fts_name;
147 p->fts_info = fts_stat(sp, p, ISSET(FTS_COMFOLLOW));
149 /* Command-line "." and ".." are real directories. */
150 if (p->fts_info == FTS_DOT)
151 p->fts_info = FTS_D;
154 * If comparison routine supplied, traverse in sorted
155 * order; otherwise traverse in the order specified.
157 if (compar) {
158 p->fts_link = root;
159 root = p;
160 } else {
161 p->fts_link = NULL;
162 if (root == NULL)
163 tmp = root = p;
164 else {
165 tmp->fts_link = p;
166 tmp = p;
170 if (compar && nitems > 1)
171 root = fts_sort(sp, root, nitems);
174 * Allocate a dummy pointer and make fts_read think that we've just
175 * finished the node before the root(s); set p->fts_info to FTS_INIT
176 * so that everything about the "current" node is ignored.
178 if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL)
179 goto mem3;
180 sp->fts_cur->fts_link = root;
181 sp->fts_cur->fts_info = FTS_INIT;
184 * If using chdir(2), grab a file descriptor pointing to dot to ensure
185 * that we can get back here; this could be avoided for some paths,
186 * but almost certainly not worth the effort. Slashes, symbolic links,
187 * and ".." are all fairly nasty problems. Note, if we can't get the
188 * descriptor we run anyway, just more slowly.
190 if (!ISSET(FTS_NOCHDIR)
191 && (sp->fts_rfd = __open(".", O_RDONLY, 0)) < 0)
192 SET(FTS_NOCHDIR);
194 return (sp);
196 mem3: fts_lfree(root);
197 free(parent);
198 mem2: free(sp->fts_path);
199 mem1: free(sp);
200 return (NULL);
203 static void
204 internal_function
205 fts_load(sp, p)
206 FTS *sp;
207 register FTSENT *p;
209 register int len;
210 register char *cp;
213 * Load the stream structure for the next traversal. Since we don't
214 * actually enter the directory until after the preorder visit, set
215 * the fts_accpath field specially so the chdir gets done to the right
216 * place and the user can access the first node. From fts_open it's
217 * known that the path will fit.
219 len = p->fts_pathlen = p->fts_namelen;
220 memmove(sp->fts_path, p->fts_name, len + 1);
221 if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) {
222 len = strlen(++cp);
223 memmove(p->fts_name, cp, len + 1);
224 p->fts_namelen = len;
226 p->fts_accpath = p->fts_path = sp->fts_path;
227 sp->fts_dev = p->fts_dev;
231 fts_close(sp)
232 FTS *sp;
234 register FTSENT *freep, *p;
235 int saved_errno;
238 * This still works if we haven't read anything -- the dummy structure
239 * points to the root list, so we step through to the end of the root
240 * list which has a valid parent pointer.
242 if (sp->fts_cur) {
243 for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {
244 freep = p;
245 p = p->fts_link != NULL ? p->fts_link : p->fts_parent;
246 free(freep);
248 free(p);
251 /* Free up child linked list, sort array, path buffer. */
252 if (sp->fts_child)
253 fts_lfree(sp->fts_child);
254 free(sp->fts_array);
255 free(sp->fts_path);
257 /* Return to original directory, save errno if necessary. */
258 if (!ISSET(FTS_NOCHDIR)) {
259 saved_errno = __fchdir(sp->fts_rfd) ? errno : 0;
260 (void)__close(sp->fts_rfd);
262 /* Set errno and return. */
263 if (saved_errno != 0) {
264 /* Free up the stream pointer. */
265 free(sp);
266 __set_errno (saved_errno);
267 return (-1);
271 /* Free up the stream pointer. */
272 free(sp);
273 return (0);
277 * Special case of "/" at the end of the path so that slashes aren't
278 * appended which would cause paths to be written as "....//foo".
280 #define NAPPEND(p) \
281 (p->fts_path[p->fts_pathlen - 1] == '/' \
282 ? p->fts_pathlen - 1 : p->fts_pathlen)
284 FTSENT *
285 fts_read(sp)
286 register FTS *sp;
288 register FTSENT *p, *tmp;
289 register int instr;
290 register char *t;
291 int saved_errno;
293 /* If finished or unrecoverable error, return NULL. */
294 if (sp->fts_cur == NULL || ISSET(FTS_STOP))
295 return (NULL);
297 /* Set current node pointer. */
298 p = sp->fts_cur;
300 /* Save and zero out user instructions. */
301 instr = p->fts_instr;
302 p->fts_instr = FTS_NOINSTR;
304 /* Any type of file may be re-visited; re-stat and re-turn. */
305 if (instr == FTS_AGAIN) {
306 p->fts_info = fts_stat(sp, p, 0);
307 return (p);
311 * Following a symlink -- SLNONE test allows application to see
312 * SLNONE and recover. If indirecting through a symlink, have
313 * keep a pointer to current location. If unable to get that
314 * pointer, follow fails.
316 if (instr == FTS_FOLLOW &&
317 (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) {
318 p->fts_info = fts_stat(sp, p, 1);
319 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
320 if ((p->fts_symfd = __open(".", O_RDONLY, 0)) < 0) {
321 p->fts_errno = errno;
322 p->fts_info = FTS_ERR;
323 } else
324 p->fts_flags |= FTS_SYMFOLLOW;
326 return (p);
329 /* Directory in pre-order. */
330 if (p->fts_info == FTS_D) {
331 /* If skipped or crossed mount point, do post-order visit. */
332 if (instr == FTS_SKIP ||
333 (ISSET(FTS_XDEV) && p->fts_dev != sp->fts_dev)) {
334 if (p->fts_flags & FTS_SYMFOLLOW)
335 (void)__close(p->fts_symfd);
336 if (sp->fts_child) {
337 fts_lfree(sp->fts_child);
338 sp->fts_child = NULL;
340 p->fts_info = FTS_DP;
341 return (p);
344 /* Rebuild if only read the names and now traversing. */
345 if (sp->fts_child != NULL && ISSET(FTS_NAMEONLY)) {
346 CLR(FTS_NAMEONLY);
347 fts_lfree(sp->fts_child);
348 sp->fts_child = NULL;
352 * Cd to the subdirectory.
354 * If have already read and now fail to chdir, whack the list
355 * to make the names come out right, and set the parent errno
356 * so the application will eventually get an error condition.
357 * Set the FTS_DONTCHDIR flag so that when we logically change
358 * directories back to the parent we don't do a chdir.
360 * If haven't read do so. If the read fails, fts_build sets
361 * FTS_STOP or the fts_info field of the node.
363 if (sp->fts_child != NULL) {
364 if (fts_safe_changedir(sp, p, -1, p->fts_accpath)) {
365 p->fts_errno = errno;
366 p->fts_flags |= FTS_DONTCHDIR;
367 for (p = sp->fts_child; p != NULL;
368 p = p->fts_link)
369 p->fts_accpath =
370 p->fts_parent->fts_accpath;
372 } else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) {
373 if (ISSET(FTS_STOP))
374 return (NULL);
375 return (p);
377 p = sp->fts_child;
378 sp->fts_child = NULL;
379 sp->fts_cur = p;
380 goto name;
383 /* Move to the next node on this level. */
384 next: tmp = p;
385 if ((p = p->fts_link) != NULL) {
386 sp->fts_cur = p;
387 free(tmp);
390 * If reached the top, return to the original directory (or
391 * the root of the tree), and load the paths for the next root.
393 if (p->fts_level == FTS_ROOTLEVEL) {
394 if (FCHDIR(sp, sp->fts_rfd)) {
395 SET(FTS_STOP);
396 return (NULL);
398 fts_load(sp, p);
399 return p;
403 * User may have called fts_set on the node. If skipped,
404 * ignore. If followed, get a file descriptor so we can
405 * get back if necessary.
407 if (p->fts_instr == FTS_SKIP)
408 goto next;
409 if (p->fts_instr == FTS_FOLLOW) {
410 p->fts_info = fts_stat(sp, p, 1);
411 if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
412 if ((p->fts_symfd =
413 __open(".", O_RDONLY, 0)) < 0) {
414 p->fts_errno = errno;
415 p->fts_info = FTS_ERR;
416 } else
417 p->fts_flags |= FTS_SYMFOLLOW;
419 p->fts_instr = FTS_NOINSTR;
422 name: t = sp->fts_path + NAPPEND(p->fts_parent);
423 *t++ = '/';
424 memmove(t, p->fts_name, p->fts_namelen + 1);
425 return p;
428 /* Move up to the parent node. */
429 p = tmp->fts_parent;
430 sp->fts_cur = p;
431 free(tmp);
433 if (p->fts_level == FTS_ROOTPARENTLEVEL) {
435 * Done; free everything up and set errno to 0 so the user
436 * can distinguish between error and EOF.
438 free(p);
439 __set_errno (0);
440 return (sp->fts_cur = NULL);
443 /* NUL terminate the pathname. */
444 sp->fts_path[p->fts_pathlen] = '\0';
447 * Return to the parent directory. If at a root node or came through
448 * a symlink, go back through the file descriptor. Otherwise, cd up
449 * one directory.
451 if (p->fts_level == FTS_ROOTLEVEL) {
452 if (FCHDIR(sp, sp->fts_rfd)) {
453 SET(FTS_STOP);
454 return (NULL);
456 } else if (p->fts_flags & FTS_SYMFOLLOW) {
457 if (FCHDIR(sp, p->fts_symfd)) {
458 saved_errno = errno;
459 (void)__close(p->fts_symfd);
460 __set_errno (saved_errno);
461 SET(FTS_STOP);
462 return (NULL);
464 (void)__close(p->fts_symfd);
465 } else if (!(p->fts_flags & FTS_DONTCHDIR) &&
466 fts_safe_changedir(sp, p->fts_parent, -1, "..")) {
467 SET(FTS_STOP);
468 return (NULL);
470 p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;
471 return p;
475 * Fts_set takes the stream as an argument although it's not used in this
476 * implementation; it would be necessary if anyone wanted to add global
477 * semantics to fts using fts_set. An error return is allowed for similar
478 * reasons.
480 /* ARGSUSED */
482 fts_set(sp, p, instr)
483 FTS *sp;
484 FTSENT *p;
485 int instr;
487 if (instr != 0 && instr != FTS_AGAIN && instr != FTS_FOLLOW &&
488 instr != FTS_NOINSTR && instr != FTS_SKIP) {
489 __set_errno (EINVAL);
490 return (1);
492 p->fts_instr = instr;
493 return (0);
496 FTSENT *
497 fts_children(sp, instr)
498 register FTS *sp;
499 int instr;
501 register FTSENT *p;
502 int fd;
504 if (instr != 0 && instr != FTS_NAMEONLY) {
505 __set_errno (EINVAL);
506 return (NULL);
509 /* Set current node pointer. */
510 p = sp->fts_cur;
513 * Errno set to 0 so user can distinguish empty directory from
514 * an error.
516 __set_errno (0);
518 /* Fatal errors stop here. */
519 if (ISSET(FTS_STOP))
520 return (NULL);
522 /* Return logical hierarchy of user's arguments. */
523 if (p->fts_info == FTS_INIT)
524 return (p->fts_link);
527 * If not a directory being visited in pre-order, stop here. Could
528 * allow FTS_DNR, assuming the user has fixed the problem, but the
529 * same effect is available with FTS_AGAIN.
531 if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */)
532 return (NULL);
534 /* Free up any previous child list. */
535 if (sp->fts_child != NULL)
536 fts_lfree(sp->fts_child);
538 if (instr == FTS_NAMEONLY) {
539 SET(FTS_NAMEONLY);
540 instr = BNAMES;
541 } else
542 instr = BCHILD;
545 * If using chdir on a relative path and called BEFORE fts_read does
546 * its chdir to the root of a traversal, we can lose -- we need to
547 * chdir into the subdirectory, and we don't know where the current
548 * directory is, so we can't get back so that the upcoming chdir by
549 * fts_read will work.
551 if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' ||
552 ISSET(FTS_NOCHDIR))
553 return (sp->fts_child = fts_build(sp, instr));
555 if ((fd = __open(".", O_RDONLY, 0)) < 0)
556 return (NULL);
557 sp->fts_child = fts_build(sp, instr);
558 if (__fchdir(fd))
559 return (NULL);
560 (void)__close(fd);
561 return (sp->fts_child);
565 * This is the tricky part -- do not casually change *anything* in here. The
566 * idea is to build the linked list of entries that are used by fts_children
567 * and fts_read. There are lots of special cases.
569 * The real slowdown in walking the tree is the stat calls. If FTS_NOSTAT is
570 * set and it's a physical walk (so that symbolic links can't be directories),
571 * we can do things quickly. First, if it's a 4.4BSD file system, the type
572 * of the file is in the directory entry. Otherwise, we assume that the number
573 * of subdirectories in a node is equal to the number of links to the parent.
574 * The former skips all stat calls. The latter skips stat calls in any leaf
575 * directories and for any files after the subdirectories in the directory have
576 * been found, cutting the stat calls by about 2/3.
578 static FTSENT *
579 internal_function
580 fts_build(sp, type)
581 register FTS *sp;
582 int type;
584 register struct dirent *dp;
585 register FTSENT *p, *head;
586 register int nitems;
587 FTSENT *cur, *tail;
588 DIR *dirp;
589 void *oldaddr;
590 int cderrno, descend, len, level, nlinks, saved_errno,
591 nostat, doadjust;
592 size_t maxlen;
593 char *cp;
595 /* Set current node pointer. */
596 cur = sp->fts_cur;
599 * Open the directory for reading. If this fails, we're done.
600 * If being called from fts_read, set the fts_info field.
602 #if defined FTS_WHITEOUT && 0
603 if (ISSET(FTS_WHITEOUT))
604 oflag = DTF_NODUP|DTF_REWIND;
605 else
606 oflag = DTF_HIDEW|DTF_NODUP|DTF_REWIND;
607 #else
608 # define __opendir2(path, flag) __opendir(path)
609 #endif
610 if ((dirp = __opendir2(cur->fts_accpath, oflag)) == NULL) {
611 if (type == BREAD) {
612 cur->fts_info = FTS_DNR;
613 cur->fts_errno = errno;
615 return (NULL);
619 * Nlinks is the number of possible entries of type directory in the
620 * directory if we're cheating on stat calls, 0 if we're not doing
621 * any stat calls at all, -1 if we're doing stats on everything.
623 if (type == BNAMES) {
624 nlinks = 0;
625 /* Be quiet about nostat, GCC. */
626 nostat = 0;
627 } else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) {
628 nlinks = cur->fts_nlink - (ISSET(FTS_SEEDOT) ? 0 : 2);
629 nostat = 1;
630 } else {
631 nlinks = -1;
632 nostat = 0;
635 #ifdef notdef
636 (void)printf("nlinks == %d (cur: %d)\n", nlinks, cur->fts_nlink);
637 (void)printf("NOSTAT %d PHYSICAL %d SEEDOT %d\n",
638 ISSET(FTS_NOSTAT), ISSET(FTS_PHYSICAL), ISSET(FTS_SEEDOT));
639 #endif
641 * If we're going to need to stat anything or we want to descend
642 * and stay in the directory, chdir. If this fails we keep going,
643 * but set a flag so we don't chdir after the post-order visit.
644 * We won't be able to stat anything, but we can still return the
645 * names themselves. Note, that since fts_read won't be able to
646 * chdir into the directory, it will have to return different path
647 * names than before, i.e. "a/b" instead of "b". Since the node
648 * has already been visited in pre-order, have to wait until the
649 * post-order visit to return the error. There is a special case
650 * here, if there was nothing to stat then it's not an error to
651 * not be able to stat. This is all fairly nasty. If a program
652 * needed sorted entries or stat information, they had better be
653 * checking FTS_NS on the returned nodes.
655 cderrno = 0;
656 if (nlinks || type == BREAD) {
657 if (fts_safe_changedir(sp, cur, dirfd(dirp), NULL)) {
658 if (nlinks && type == BREAD)
659 cur->fts_errno = errno;
660 cur->fts_flags |= FTS_DONTCHDIR;
661 descend = 0;
662 cderrno = errno;
663 (void)__closedir(dirp);
664 dirp = NULL;
665 } else
666 descend = 1;
667 } else
668 descend = 0;
671 * Figure out the max file name length that can be stored in the
672 * current path -- the inner loop allocates more path as necessary.
673 * We really wouldn't have to do the maxlen calculations here, we
674 * could do them in fts_read before returning the path, but it's a
675 * lot easier here since the length is part of the dirent structure.
677 * If not changing directories set a pointer so that can just append
678 * each new name into the path.
680 len = NAPPEND(cur);
681 if (ISSET(FTS_NOCHDIR)) {
682 cp = sp->fts_path + len;
683 *cp++ = '/';
684 } else {
685 /* GCC, you're too verbose. */
686 cp = NULL;
688 len++;
689 maxlen = sp->fts_pathlen - len;
691 level = cur->fts_level + 1;
693 /* Read the directory, attaching each entry to the `link' pointer. */
694 doadjust = 0;
695 for (head = tail = NULL, nitems = 0; dirp && (dp = __readdir(dirp));) {
696 if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))
697 continue;
699 if ((p = fts_alloc(sp, dp->d_name, _D_EXACT_NAMLEN (dp))) == NULL)
700 goto mem1;
701 if (_D_EXACT_NAMLEN (dp) >= maxlen) {/* include space for NUL */
702 oldaddr = sp->fts_path;
703 if (fts_palloc(sp, _D_EXACT_NAMLEN (dp) + len + 1)) {
705 * No more memory for path or structures. Save
706 * errno, free up the current structure and the
707 * structures already allocated.
709 mem1: saved_errno = errno;
710 free(p);
711 fts_lfree(head);
712 (void)__closedir(dirp);
713 cur->fts_info = FTS_ERR;
714 SET(FTS_STOP);
715 __set_errno (saved_errno);
716 return (NULL);
718 /* Did realloc() change the pointer? */
719 if (oldaddr != sp->fts_path) {
720 doadjust = 1;
721 if (ISSET(FTS_NOCHDIR))
722 cp = sp->fts_path + len;
724 maxlen = sp->fts_pathlen - len;
727 if (len + _D_EXACT_NAMLEN (dp) >= USHRT_MAX) {
729 * In an FTSENT, fts_pathlen is a u_short so it is
730 * possible to wraparound here. If we do, free up
731 * the current structure and the structures already
732 * allocated, then error out with ENAMETOOLONG.
734 free(p);
735 fts_lfree(head);
736 (void)__closedir(dirp);
737 cur->fts_info = FTS_ERR;
738 SET(FTS_STOP);
739 __set_errno (ENAMETOOLONG);
740 return (NULL);
742 p->fts_level = level;
743 p->fts_parent = sp->fts_cur;
744 p->fts_pathlen = len + _D_EXACT_NAMLEN (dp);
746 #if defined FTS_WHITEOUT && 0
747 if (dp->d_type == DT_WHT)
748 p->fts_flags |= FTS_ISW;
749 #endif
751 #if 0
752 /* Unreachable code. cderrno is only ever set to a nonnull
753 value if dirp is closed at the same time. But then we
754 cannot enter this loop. */
755 if (cderrno) {
756 if (nlinks) {
757 p->fts_info = FTS_NS;
758 p->fts_errno = cderrno;
759 } else
760 p->fts_info = FTS_NSOK;
761 p->fts_accpath = cur->fts_accpath;
762 } else
763 #endif
764 if (nlinks == 0
765 #if defined DT_DIR && defined _DIRENT_HAVE_D_TYPE
766 || (nostat &&
767 dp->d_type != DT_DIR && dp->d_type != DT_UNKNOWN)
768 #endif
770 p->fts_accpath =
771 ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name;
772 p->fts_info = FTS_NSOK;
773 } else {
774 /* Build a file name for fts_stat to stat. */
775 if (ISSET(FTS_NOCHDIR)) {
776 p->fts_accpath = p->fts_path;
777 memmove(cp, p->fts_name, p->fts_namelen + 1);
778 } else
779 p->fts_accpath = p->fts_name;
780 /* Stat it. */
781 p->fts_info = fts_stat(sp, p, 0);
783 /* Decrement link count if applicable. */
784 if (nlinks > 0 && (p->fts_info == FTS_D ||
785 p->fts_info == FTS_DC || p->fts_info == FTS_DOT))
786 --nlinks;
789 /* We walk in directory order so "ls -f" doesn't get upset. */
790 p->fts_link = NULL;
791 if (head == NULL)
792 head = tail = p;
793 else {
794 tail->fts_link = p;
795 tail = p;
797 ++nitems;
799 if (dirp)
800 (void)__closedir(dirp);
803 * If realloc() changed the address of the path, adjust the
804 * addresses for the rest of the tree and the dir list.
806 if (doadjust)
807 fts_padjust(sp, head);
810 * If not changing directories, reset the path back to original
811 * state.
813 if (ISSET(FTS_NOCHDIR)) {
814 if (len == sp->fts_pathlen || nitems == 0)
815 --cp;
816 *cp = '\0';
820 * If descended after called from fts_children or after called from
821 * fts_read and nothing found, get back. At the root level we use
822 * the saved fd; if one of fts_open()'s arguments is a relative path
823 * to an empty directory, we wind up here with no other way back. If
824 * can't get back, we're done.
826 if (descend && (type == BCHILD || !nitems) &&
827 (cur->fts_level == FTS_ROOTLEVEL ?
828 FCHDIR(sp, sp->fts_rfd) :
829 fts_safe_changedir(sp, cur->fts_parent, -1, ".."))) {
830 cur->fts_info = FTS_ERR;
831 SET(FTS_STOP);
832 fts_lfree(head);
833 return (NULL);
836 /* If didn't find anything, return NULL. */
837 if (!nitems) {
838 if (type == BREAD)
839 cur->fts_info = FTS_DP;
840 fts_lfree(head);
841 return (NULL);
844 /* Sort the entries. */
845 if (sp->fts_compar && nitems > 1)
846 head = fts_sort(sp, head, nitems);
847 return (head);
850 static u_short
851 internal_function
852 fts_stat(sp, p, follow)
853 FTS *sp;
854 register FTSENT *p;
855 int follow;
857 register FTSENT *t;
858 register dev_t dev;
859 register ino_t ino;
860 struct stat *sbp, sb;
861 int saved_errno;
863 /* If user needs stat info, stat buffer already allocated. */
864 sbp = ISSET(FTS_NOSTAT) ? &sb : p->fts_statp;
866 #if defined FTS_WHITEOUT && 0
867 /* check for whiteout */
868 if (p->fts_flags & FTS_ISW) {
869 if (sbp != &sb) {
870 memset(sbp, '\0', sizeof (*sbp));
871 sbp->st_mode = S_IFWHT;
873 return (FTS_W);
875 #endif
878 * If doing a logical walk, or application requested FTS_FOLLOW, do
879 * a stat(2). If that fails, check for a non-existent symlink. If
880 * fail, set the errno from the stat call.
882 if (ISSET(FTS_LOGICAL) || follow) {
883 if (stat(p->fts_accpath, sbp)) {
884 saved_errno = errno;
885 if (!lstat(p->fts_accpath, sbp)) {
886 __set_errno (0);
887 return (FTS_SLNONE);
889 p->fts_errno = saved_errno;
890 goto err;
892 } else if (lstat(p->fts_accpath, sbp)) {
893 p->fts_errno = errno;
894 err: memset(sbp, 0, sizeof(struct stat));
895 return (FTS_NS);
898 if (S_ISDIR(sbp->st_mode)) {
900 * Set the device/inode. Used to find cycles and check for
901 * crossing mount points. Also remember the link count, used
902 * in fts_build to limit the number of stat calls. It is
903 * understood that these fields are only referenced if fts_info
904 * is set to FTS_D.
906 dev = p->fts_dev = sbp->st_dev;
907 ino = p->fts_ino = sbp->st_ino;
908 p->fts_nlink = sbp->st_nlink;
910 if (ISDOT(p->fts_name))
911 return (FTS_DOT);
914 * Cycle detection is done by brute force when the directory
915 * is first encountered. If the tree gets deep enough or the
916 * number of symbolic links to directories is high enough,
917 * something faster might be worthwhile.
919 for (t = p->fts_parent;
920 t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
921 if (ino == t->fts_ino && dev == t->fts_dev) {
922 p->fts_cycle = t;
923 return (FTS_DC);
925 return (FTS_D);
927 if (S_ISLNK(sbp->st_mode))
928 return (FTS_SL);
929 if (S_ISREG(sbp->st_mode))
930 return (FTS_F);
931 return (FTS_DEFAULT);
934 static FTSENT *
935 internal_function
936 fts_sort(sp, head, nitems)
937 FTS *sp;
938 FTSENT *head;
939 register int nitems;
941 register FTSENT **ap, *p;
944 * Construct an array of pointers to the structures and call qsort(3).
945 * Reassemble the array in the order returned by qsort. If unable to
946 * sort for memory reasons, return the directory entries in their
947 * current order. Allocate enough space for the current needs plus
948 * 40 so don't realloc one entry at a time.
950 if (nitems > sp->fts_nitems) {
951 struct _ftsent **a;
953 sp->fts_nitems = nitems + 40;
954 if ((a = realloc(sp->fts_array,
955 (size_t)(sp->fts_nitems * sizeof(FTSENT *)))) == NULL) {
956 free(sp->fts_array);
957 sp->fts_array = NULL;
958 sp->fts_nitems = 0;
959 return (head);
961 sp->fts_array = a;
963 for (ap = sp->fts_array, p = head; p; p = p->fts_link)
964 *ap++ = p;
965 qsort((void *)sp->fts_array, nitems, sizeof(FTSENT *), sp->fts_compar);
966 for (head = *(ap = sp->fts_array); --nitems; ++ap)
967 ap[0]->fts_link = ap[1];
968 ap[0]->fts_link = NULL;
969 return (head);
972 static FTSENT *
973 internal_function
974 fts_alloc(sp, name, namelen)
975 FTS *sp;
976 const char *name;
977 size_t namelen;
979 register FTSENT *p;
980 size_t len;
983 * The file name is a variable length array and no stat structure is
984 * necessary if the user has set the nostat bit. Allocate the FTSENT
985 * structure, the file name and the stat structure in one chunk, but
986 * be careful that the stat structure is reasonably aligned. Since the
987 * fts_name field is declared to be of size 1, the fts_name pointer is
988 * namelen + 2 before the first possible address of the stat structure.
990 len = sizeof(FTSENT) + namelen;
991 if (!ISSET(FTS_NOSTAT))
992 len += sizeof(struct stat) + ALIGNBYTES;
993 if ((p = malloc(len)) == NULL)
994 return (NULL);
996 /* Copy the name and guarantee NUL termination. */
997 memmove(p->fts_name, name, namelen);
998 p->fts_name[namelen] = '\0';
1000 if (!ISSET(FTS_NOSTAT))
1001 p->fts_statp = (struct stat *)ALIGN(p->fts_name + namelen + 2);
1002 p->fts_namelen = namelen;
1003 p->fts_path = sp->fts_path;
1004 p->fts_errno = 0;
1005 p->fts_flags = 0;
1006 p->fts_instr = FTS_NOINSTR;
1007 p->fts_number = 0;
1008 p->fts_pointer = NULL;
1009 return (p);
1012 static void
1013 internal_function
1014 fts_lfree(head)
1015 register FTSENT *head;
1017 register FTSENT *p;
1019 /* Free a linked list of structures. */
1020 while ((p = head)) {
1021 head = head->fts_link;
1022 free(p);
1027 * Allow essentially unlimited paths; find, rm, ls should all work on any tree.
1028 * Most systems will allow creation of paths much longer than MAXPATHLEN, even
1029 * though the kernel won't resolve them. Add the size (not just what's needed)
1030 * plus 256 bytes so don't realloc the path 2 bytes at a time.
1032 static int
1033 internal_function
1034 fts_palloc(sp, more)
1035 FTS *sp;
1036 size_t more;
1038 char *p;
1040 sp->fts_pathlen += more + 256;
1042 * Check for possible wraparound. In an FTS, fts_pathlen is
1043 * a signed int but in an FTSENT it is an unsigned short.
1044 * We limit fts_pathlen to USHRT_MAX to be safe in both cases.
1046 if (sp->fts_pathlen < 0 || sp->fts_pathlen >= USHRT_MAX) {
1047 free(sp->fts_path);
1048 sp->fts_path = NULL;
1049 __set_errno (ENAMETOOLONG);
1050 return (1);
1052 p = realloc(sp->fts_path, sp->fts_pathlen);
1053 if (p == NULL) {
1054 free(sp->fts_path);
1055 sp->fts_path = NULL;
1056 return 1;
1058 sp->fts_path = p;
1059 return 0;
1063 * When the path is realloc'd, have to fix all of the pointers in structures
1064 * already returned.
1066 static void
1067 internal_function
1068 fts_padjust(sp, head)
1069 FTS *sp;
1070 FTSENT *head;
1072 FTSENT *p;
1073 char *addr = sp->fts_path;
1075 #define ADJUST(p) do { \
1076 if ((p)->fts_accpath != (p)->fts_name) { \
1077 (p)->fts_accpath = \
1078 (char *)addr + ((p)->fts_accpath - (p)->fts_path); \
1080 (p)->fts_path = addr; \
1081 } while (0)
1082 /* Adjust the current set of children. */
1083 for (p = sp->fts_child; p; p = p->fts_link)
1084 ADJUST(p);
1086 /* Adjust the rest of the tree, including the current level. */
1087 for (p = head; p->fts_level >= FTS_ROOTLEVEL;) {
1088 ADJUST(p);
1089 p = p->fts_link ? p->fts_link : p->fts_parent;
1093 static size_t
1094 internal_function
1095 fts_maxarglen(argv)
1096 char * const *argv;
1098 size_t len, max;
1100 for (max = 0; *argv; ++argv)
1101 if ((len = strlen(*argv)) > max)
1102 max = len;
1103 return (max + 1);
1107 * Change to dir specified by fd or p->fts_accpath without getting
1108 * tricked by someone changing the world out from underneath us.
1109 * Assumes p->fts_dev and p->fts_ino are filled in.
1111 static int
1112 internal_function
1113 fts_safe_changedir(sp, p, fd, path)
1114 FTS *sp;
1115 FTSENT *p;
1116 int fd;
1117 const char *path;
1119 int ret, oerrno, newfd;
1120 struct stat64 sb;
1122 newfd = fd;
1123 if (ISSET(FTS_NOCHDIR))
1124 return (0);
1125 if (fd < 0 && (newfd = __open(path, O_RDONLY, 0)) < 0)
1126 return (-1);
1127 if (__fxstat64(_STAT_VER, newfd, &sb)) {
1128 ret = -1;
1129 goto bail;
1131 if (p->fts_dev != sb.st_dev || p->fts_ino != sb.st_ino) {
1132 __set_errno (ENOENT); /* disinformation */
1133 ret = -1;
1134 goto bail;
1136 ret = __fchdir(newfd);
1137 bail:
1138 oerrno = errno;
1139 if (fd < 0)
1140 (void)__close(newfd);
1141 __set_errno (oerrno);
1142 return (ret);