X-Git-Url: https://git.subgeniuskitty.com/unix-history/.git/blobdiff_plain/1730d75fcbca9197539eb71576f0322a3cdc7c75..af359dea2e5ab3e937b62107ecd6a51d78189ed7:/usr/src/lib/libc/gen/fts.c?ds=inline diff --git a/usr/src/lib/libc/gen/fts.c b/usr/src/lib/libc/gen/fts.c index d4ed277c96..e2958d3cb4 100644 --- a/usr/src/lib/libc/gen/fts.c +++ b/usr/src/lib/libc/gen/fts.c @@ -1,56 +1,69 @@ -/* - * Copyright (c) 1989 The Regents of the University of California. +/*- + * Copyright (c) 1990 The Regents of the University of California. * All rights reserved. * - * Redistribution and use in source and binary forms are permitted - * provided that the above copyright notice and this paragraph are - * duplicated in all such forms and that any documentation, - * advertising materials, and other materials related to such - * distribution and use acknowledge that the software was developed - * by the University of California, Berkeley. The name of the - * University may not be used to endorse or promote products derived - * from this software without specific prior written permission. - * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR - * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED - * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * This product includes software developed by the University of + * California, Berkeley and its contributors. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. */ #if defined(LIBC_SCCS) && !defined(lint) -static char sccsid[] = "@(#)fts.c 5.2 (Berkeley) %G%"; +static char sccsid[] = "@(#)fts.c 5.19 (Berkeley) 5/9/91"; #endif /* LIBC_SCCS and not lint */ +#include #include #include +#include #include #include -#include -#include - -extern int errno; +#include "fts.h" +#include +#include +#include -FTSENT *fts_alloc(), *fts_build(), *fts_cycle(), *fts_sort(), *fts_root(); -short fts_stat(); -char *malloc(), *realloc(); - -/* - * Special case a root of "/" so that slashes aren't appended causing - * paths to be written as "//foo". - */ -#define NAPPEND(p) \ - (p->level == ROOTLEVEL && p->pathlen == 1 && \ - p->path[0] == '/' ? 0 : p->pathlen) +static FTSENT *fts_alloc(), *fts_build(), *fts_sort(); +static void fts_load(), fts_lfree(); +static u_short fts_stat(); +static char *fts_path(); -#define CHDIR(sp, path) (!(sp->options & FTS_NOCHDIR) && chdir(path)) -#define FCHDIR(sp, fd) (!(sp->options & FTS_NOCHDIR) && fchdir(fd)) +#define ISSET(opt) (sp->fts_options & opt) +#define SET(opt) (sp->fts_options |= opt) -#define ROOTLEVEL 0 -#define ROOTPARENTLEVEL -1 +#define CHDIR(sp, path) (!ISSET(FTS_NOCHDIR) && chdir(path)) +#define FCHDIR(sp, fd) (!ISSET(FTS_NOCHDIR) && fchdir(fd)) -static FTS *stream; /* current stream pointer */ +/* fts_build flags */ +#define BCHILD 1 /* from fts_children */ +#define BREAD 2 /* from fts_read */ FTS * -ftsopen(argv, options, compar) - char *argv[]; +fts_open(argv, options, compar) + char * const *argv; register int options; int (*compar)(); { @@ -58,629 +71,717 @@ ftsopen(argv, options, compar) register FTSENT *p, *root; register int nitems, maxlen; FTSENT *parent, *tmp; - char wd[MAXPATHLEN], *getwd(), *strdup(); + int len; - /* allocate/initialize the stream */ - if (!(stream = sp = (FTS *)malloc((u_int)sizeof(FTS)))) + /* Allocate/initialize the stream */ + if (!(sp = (FTS *)malloc((u_int)sizeof(FTS)))) return(NULL); bzero(sp, sizeof(FTS)); - sp->compar = compar; - sp->options = options; + sp->fts_compar = compar; + sp->fts_options = options; + + /* Logical walks turn on NOCHDIR; symbolic links are too hard. */ + if (ISSET(FTS_LOGICAL)) + SET(FTS_NOCHDIR); - /* allocate/initialize root's parent */ - if (!(parent = fts_alloc("", 0))) + /* Allocate/initialize root's parent. */ + if (!(parent = fts_alloc(sp, "", 0))) goto mem1; - parent->level = ROOTPARENTLEVEL; - - /* allocate/initialize root(s) */ - if (options & FTS_MULTIPLE) { - maxlen = -1; - for (root = NULL, nitems = 0; *argv; ++argv, ++nitems) { - if (!(p = fts_root(*argv))) - goto mem2; - if (maxlen < p->namelen) - maxlen = p->namelen; - /* - * if comparison routine supplied, traverse in sorted - * order; otherwise traverse in the order specified. - */ - if (compar) { - p->link = root; - root = p; - p->accpath = p->name; - p->info = fts_stat(p, 0); - } else { - p->link = NULL; - if (!root) - tmp = root = p; - else { - tmp->link = p; - tmp = p; - } + parent->fts_level = FTS_ROOTPARENTLEVEL; + + /* Allocate/initialize root(s). */ + maxlen = -1; + for (root = NULL, nitems = 0; *argv; ++argv, ++nitems) { + if (!(len = strlen(*argv))) { + errno = ENOENT; + goto mem2; + } + if (maxlen < len) + maxlen = len; + p = fts_alloc(sp, *argv, len); + p->fts_level = FTS_ROOTLEVEL; + p->fts_parent = parent; + /* + * If comparison routine supplied, traverse in sorted + * order; otherwise traverse in the order specified. + */ + if (compar) { + p->fts_link = root; + root = p; + p->fts_accpath = p->fts_name; + if (!(options & FTS_NOSTAT)) + p->fts_info = fts_stat(sp, p, 0); + } else { + p->fts_link = NULL; + if (!root) + tmp = root = p; + else { + tmp->fts_link = p; + tmp = p; } - p->level = ROOTLEVEL; - p->parent = parent; } - if (compar && nitems > 1) - root = fts_sort(root, nitems); - } else { - if (!(root = fts_root((char *)argv))) - goto mem2; - maxlen = root->namelen; - root->link = NULL; - root->level = ROOTLEVEL; - root->parent = parent; } - - /* start out with at least 1K+ of path space */ - if (!fts_path(MAX(maxlen, MAXPATHLEN))) - goto mem2; + if (compar && nitems > 1) + root = fts_sort(sp, root, nitems); /* - * some minor trickiness. Set the pointers so that ftsread thinks - * we've just finished the node before the root(s); set p->info to - * FTS_NS so that everything about the "current" node is ignored. - * Rather than allocate a dummy node use the root's parent's link - * pointer. This is handled specially in ftsclose() as well. + * Allocate a dummy pointer and make fts_read think that we've just + * finished the node before the root(s); set p->fts_info to FTS_NS + * so that everything about the "current" node is ignored. */ - sp->cur = parent; - parent->link = root; - parent->info = FTS_NS; + if (!(sp->fts_cur = fts_alloc(sp, "", 0))) + goto mem2; + sp->fts_cur->fts_link = root; + sp->fts_cur->fts_info = FTS_NS; + + /* Start out with at least 1K+ of path space. */ + if (!fts_path(sp, MAX(maxlen, MAXPATHLEN))) + goto mem3; /* - * if using chdir(2), do a getwd() to insure that we can get back - * here; this could be avoided for some paths, but probably not - * worth the effort. Slashes, symbolic links, and ".." are all - * fairly nasty problems. Note, if we can't get the current - * working directory we run anyway, just more slowly. + * If using chdir(2), grab a file descriptor pointing to dot to insure + * that we can get back here; this could be avoided for some paths, + * but almost certainly not worth the effort. Slashes, symbolic links, + * and ".." are all fairly nasty problems. Note, if we can't get the + * descriptor we run anyway, just more slowly. */ - if (!(options & FTS_NOCHDIR) && (!getwd(wd) || !(sp->wd = strdup(wd)))) - sp->options |= FTS_NOCHDIR; + if (!ISSET(FTS_NOCHDIR) && (sp->fts_rfd = open(".", O_RDONLY, 0)) < 0) + SET(FTS_NOCHDIR); return(sp); +mem3: free(sp->fts_cur); mem2: fts_lfree(root); - (void)free((char *)parent); -mem1: (void)free((char *)sp); + free(parent); +mem1: free(sp); return(NULL); } -static -fts_load(p) +static void +fts_load(sp, p) + FTS *sp; register FTSENT *p; { register int len; register char *cp; /* - * load the stream structure for the next traversal; set the - * accpath field specially so the chdir gets done to the right + * Load the stream structure for the next traversal. Since we don't + * actually enter the directory until after the preorder visit, set + * the fts_accpath field specially so the chdir gets done to the right * place and the user can access the first node. */ - len = p->pathlen = p->namelen; - bcopy(p->name, stream->path, len + 1); - if ((cp = rindex(p->name, '/')) && (cp != p->name || cp[1])) { + len = p->fts_pathlen = p->fts_namelen; + bcopy(p->fts_name, sp->fts_path, len + 1); + if ((cp = rindex(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) { len = strlen(++cp); - bcopy(cp, p->name, len + 1); - p->namelen = len; + bcopy(cp, p->fts_name, len + 1); + p->fts_namelen = len; } - p->accpath = p->path = stream->path; + p->fts_accpath = p->fts_path = sp->fts_path; + + p->fts_info = fts_stat(sp, p, 0); + sp->rdev = p->fts_statb.st_dev; } -ftsclose(sp) +fts_close(sp) FTS *sp; { register FTSENT *freep, *p; int saved_errno; - if (sp->cur) - /* check for never having read anything */ - if (sp->cur->level == ROOTPARENTLEVEL) - fts_lfree(sp->cur); - else { - for (p = sp->cur; p->level > ROOTPARENTLEVEL;) { - freep = p; - p = p->link ? p->link : p->parent; - (void)free((char *)freep); - } - (void)free((char *)p); + if (sp->fts_cur) { + /* + * This still works if we haven't read anything -- the dummy + * structure points to the root list, so we step through to + * the end of the root list which has a valid parent pointer. + */ + for (p = sp->fts_cur; p->fts_level > FTS_ROOTPARENTLEVEL;) { + freep = p; + p = p->fts_link ? p->fts_link : p->fts_parent; + free(freep); } + free(p); + } - /* free up child linked list, sort array, path buffer */ - if (sp->child) - fts_lfree(sp->child); - if (sp->array) - (void)free((char *)sp->array); - (void)free((char *)sp->path); - - /* - * return to original directory, save errno if necessary; - * free up the directory buffer - */ - if (!(sp->options & FTS_NOCHDIR)) { - saved_errno = chdir(sp->wd) ? errno : 0; - (void)free(sp->wd); + /* Free up child linked list, sort array, path buffer. */ + if (sp->fts_child) + fts_lfree(sp->fts_child); + if (sp->fts_array) + free(sp->fts_array); + free(sp->fts_path); + + /* Return to original directory, save errno if necessary. */ + if (!ISSET(FTS_NOCHDIR)) { + saved_errno = fchdir(sp->fts_rfd) ? errno : 0; + (void)close(sp->fts_rfd); } - /* free up the stream pointer */ - (void)free((char *)sp); + /* Free up the stream pointer. */ + free(sp); - /* set errno and return */ - if (!(sp->options & FTS_NOCHDIR) && saved_errno) { + /* Set errno and return. */ + if (!ISSET(FTS_NOCHDIR) && saved_errno) { errno = saved_errno; return(-1); } return(0); } +/* + * Special case a root of "/" so that slashes aren't appended causing + * paths to be written as "//foo". + */ +#define NAPPEND(p) \ + (p->fts_level == FTS_ROOTLEVEL && p->fts_pathlen == 1 && \ + p->fts_path[0] == '/' ? 0 : p->fts_pathlen) + FTSENT * -ftsread(sp) +fts_read(sp) register FTS *sp; { - register FTSENT *p; + register FTSENT *p, *tmp; register int instr; - static int cd; - FTSENT *tmp; - char *cp; + register char *t; - /* if finished or unrecoverable error, return NULL */ - if (!sp->cur || sp->options & FTS__STOP) + /* If finished or unrecoverable error, return NULL. */ + if (!sp->fts_cur || ISSET(FTS_STOP)) return(NULL); - /* set global stream pointer, and current node pointer */ - stream = sp; - p = sp->cur; + /* Set current node pointer. */ + p = sp->fts_cur; - /* save and zero out user instructions */ - instr = p->instr; - p->instr = 0; + /* Save and zero out user instructions. */ + instr = p->fts_instr; + p->fts_instr = FTS_NOINSTR; - /* if used link pointer for cycle detection, restore it */ - if (sp->savelink) { - p->link = sp->savelink; - sp->savelink = NULL; + /* If used fts_link pointer for cycle detection, restore it. */ + if (sp->fts_savelink) { + p->fts_link = sp->fts_savelink; + sp->fts_savelink = NULL; } - /* any type of file may be re-visited; re-stat and return */ + /* Any type of file may be re-visited; re-stat and re-turn. */ if (instr == FTS_AGAIN) { - p->info = fts_stat(p, 0); - return(p); - } - - if (p->info == FTS_D) - if (instr == FTS_SKIP) { - if (sp->child) { - fts_lfree(sp->child); - sp->child = NULL; - } - } else { - if (!sp->child && (!(sp->child = fts_build(sp, 1)))) - return(p); - p = sp->child; - sp->child = NULL; - return(sp->cur = p); - } - else if (p->info == FTS_SL && instr == FTS_FOLLOW) { - p->info = fts_stat(p, 1); + p->fts_info = fts_stat(sp, p, 0); return(p); } /* - * user may have called ftsset on pointer returned by - * ftschildren; handle it here. + * Following a symlink -- SLNONE test allows application to see + * SLNONE and recover. */ - for (p = p->link; p;) { - instr = p->instr; - if (instr == FTS_FOLLOW) { - p->info = fts_stat(p, 1); - p->instr = 0; - break; - } - if (instr == FTS_SKIP) { - tmp = p; - p = p->link; - (void)free((char *)tmp); - continue; - } - p->instr = 0; - break; + if (instr == FTS_FOLLOW && + (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) { + p->fts_info = fts_stat(sp, p, 1); + return(p); } - /* go to next node on this level */ - if (p) { + /* Directory in pre-order. */ + if (p->fts_info == FTS_D) { + /* If skipped or crossed mount point, do post-order visit. */ + if (instr == FTS_SKIP || + ISSET(FTS_XDEV) && p->fts_statb.st_dev != sp->rdev) { + if (sp->fts_child) { + fts_lfree(sp->fts_child); + sp->fts_child = NULL; + } + p->fts_info = FTS_DP; + return(p); + } + /* - * if root level node, set up paths and return. If not the - * first time, and it's not an absolute pathname, get back - * to wherever we started from. + * Cd to the subdirectory, reading it if haven't already. If + * the read fails for any reason, or the directory is empty, + * the fts_info field of the current node is set by fts_build. + * If have already read and now fail to chdir, whack the list + * to make the names come out right, and set the parent state + * so the application will eventually get an error condition. + * If haven't read and fail to chdir, check to see if we're + * at the root node -- if so, we have to get back or the root + * node may be inaccessible. */ - if (p->level == ROOTLEVEL) { - fts_load(p); - if (cd) { - (void)free((char *)sp->cur); - if (p->path[0] != '/' && CHDIR(sp, sp->wd)) { - /* return target path for error msg */ - p->path = sp->wd; - p->info = FTS_ERR; - sp->options |= FTS__STOP; - return(sp->cur = p); - } - } else - cd = 1; - p->info = fts_stat(p, 0); - } else { - (void)free((char *)sp->cur); - cp = sp->path + NAPPEND(p->parent); - *cp++ = '/'; - bcopy(p->name, cp, p->namelen + 1); - if (p->info == FTS_D && (tmp = fts_cycle(p))) { - sp->savelink = p->link; - p->link = tmp; + if (sp->fts_child) { + if (CHDIR(sp, p->fts_accpath)) { + p->fts_parent->fts_cderr = errno; + for (p = sp->fts_child; p; p = p->fts_link) + p->fts_accpath = + p->fts_parent->fts_accpath; + } + } else if (!(sp->fts_child = fts_build(sp, BREAD))) { + if ISSET(FTS_STOP) + return(NULL); + if (p->fts_level == FTS_ROOTLEVEL && + FCHDIR(sp, sp->fts_rfd)) { + SET(FTS_STOP); + return(NULL); } + return(p); } - return(sp->cur = p); + p = sp->fts_child; + sp->fts_child = NULL; + goto name; } - /* go to parent */ - p = sp->cur->parent; - (void)free((char *)sp->cur); - if (p->level == ROOTPARENTLEVEL) { + /* Move to next node on this level. */ +next: tmp = p; + if (p = p->fts_link) { + free(tmp); + + /* If reached the top, load the paths for the next root. */ + if (p->fts_level == FTS_ROOTLEVEL) { + fts_load(sp, p); + return(sp->fts_cur = p); + } + + /* User may have called fts_set on the node. */ + if (p->fts_instr == FTS_SKIP) + goto next; + if (p->fts_instr == FTS_FOLLOW) { + p->fts_info = fts_stat(sp, p, 1); + p->fts_instr = FTS_NOINSTR; + } + +name: t = sp->fts_path + NAPPEND(p->fts_parent); + *t++ = '/'; + bcopy(p->fts_name, t, p->fts_namelen + 1); + return(sp->fts_cur = p); + } + + /* Move up to the parent node. */ + p = tmp->fts_parent; + free(tmp); + + if (p->fts_level == FTS_ROOTPARENTLEVEL) { /* - * done; free everything up and set errno to 0 so the user + * Done; free everything up and set errno to 0 so the user * can distinguish between error and EOF. */ - (void)free((char *)p); + free(p); errno = 0; - return(sp->cur = NULL); + return(sp->fts_cur = NULL); } - sp->path[p->pathlen] = '\0'; - if (CHDIR(sp, "..")) { - sp->options |= FTS__STOP; - p->info = FTS_ERR; + sp->fts_path[p->fts_pathlen] = '\0'; + + /* + * Cd back up to the parent directory. If at a root node, have to cd + * back to the original place, otherwise may not be able to access the + * original node on post-order. + */ + if (p->fts_level == FTS_ROOTLEVEL) { + if (FCHDIR(sp, sp->fts_rfd)) { + SET(FTS_STOP); + return(NULL); + } + } + else if (CHDIR(sp, "..")) { + SET(FTS_STOP); + return(NULL); + } + + /* + * If had a chdir error when trying to get into the directory, set the + * info field to reflect this, and restore errno. The error indicator + * has to be reset to 0 so that if the user does an FTS_AGAIN, it all + * works. + */ + if (p->fts_cderr) { + errno = p->fts_cderr; + p->fts_cderr = 0; + p->fts_info = FTS_ERR; } else - p->info = FTS_DP; - return(sp->cur = p); + p->fts_info = FTS_DP; + return(sp->fts_cur = p); } /* - * ftsset takes the stream as an argument although it's not used in this + * Fts_set takes the stream as an argument although it's not used in this * implementation; it would be necessary if anyone wanted to add global - * semantics to fts using ftsset. A possible error return is allowed for - * similar reasons. + * semantics to fts using fts_set. An error return is allowed for similar + * reasons. */ /* ARGSUSED */ -ftsset(sp, p, instr) +fts_set(sp, p, instr) FTS *sp; FTSENT *p; int instr; { - p->instr = instr; + p->fts_instr = instr; return(0); } FTSENT * -ftschildren(sp) +fts_children(sp) register FTS *sp; { + register FTSENT *p; + int fd; + + /* Set current node pointer. */ + p = sp->fts_cur; + /* - * set errno to 0 so that user can tell the difference between an - * error and a directory without entries. + * Set errno to 0 so that user can tell the difference between an + * error and a directory without entries. If not a directory being + * visited in *pre-order*, or we've already had fatal errors, return + * immediately. */ errno = 0; - if (sp->cur->info != FTS_D || sp->options & FTS__STOP) + if (ISSET(FTS_STOP) || p->fts_info != FTS_D && p->fts_info != FTS_DNR) return(NULL); - if (sp->child) - fts_lfree(sp->child); - return(sp->child = fts_build(sp, 0)); + + /* Free up any previous child list. */ + if (sp->fts_child) + fts_lfree(sp->fts_child); + + /* + * If using chdir on a relative path and called BEFORE fts_read does + * its chdir to the root of a traversal, we can lose -- we need to + * chdir into the subdirectory, and we don't know where the current + * directory is, so we can't get back so that the upcoming chdir by + * fts_read will work. + */ + if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' || + ISSET(FTS_NOCHDIR)) + return(sp->fts_child = fts_build(sp, BCHILD)); + + if ((fd = open(".", O_RDONLY, 0)) < 0) + return(NULL); + sp->fts_child = fts_build(sp, BCHILD); + if (fchdir(fd)) + return(NULL); + (void)close(fd); + return(sp->fts_child); } +/* + * This is the tricky part -- do not casually change *anything* in here. The + * idea is to build the linked list of entries that are used by fts_children + * and fts_read. There are lots of special cases. + * + * The real slowdown in walking the tree is the stat calls. If FTS_NOSTAT is + * set and it's a physical walk (so that symbolic links can't be directories), + * we assume that the number of subdirectories in a node is equal to the number + * of links to the parent. This allows stat calls to be skipped in any leaf + * directories and for any nodes after the directories in the parent node have + * been found. This empirically cuts the stat calls by about 2/3. + */ #define ISDOT(a) (a[0] == '.' && (!a[1] || a[1] == '.' && !a[2])) static FTSENT * -fts_build(sp, set_node) +fts_build(sp, type) register FTS *sp; - int set_node; + int type; { register struct dirent *dp; register FTSENT *p, *head; register int nitems; + FTSENT *cur; DIR *dirp; - int descend, len, level, maxlen, nlinks, saved_errno; + int cderr, descend, len, level, maxlen, nlinks, saved_errno; char *cp; - p = sp->cur; - if (!(dirp = opendir(p->accpath))) { - if (set_node) { - errno = 0; - p->info = FTS_DNR; - } + /* Set current node pointer. */ + cur = sp->fts_cur; + + /* + * Open the directory for reading. If this fails, we're done. + * If being called from fts_read, set the fts_info field. + */ + if (!(dirp = opendir(cur->fts_accpath))) { + if (type == BREAD) + cur->fts_info = FTS_DNR; return(NULL); } /* - * the real slowdown in walking the tree is the stat calls. If - * FTS_NOSTAT is set and it's a physical walk (so that symbolic - * links can't be directories), fts assumes that the number of - * subdirectories in a node is equal to the number of links to - * the parent. This allows stat calls to be skipped in any leaf - * directories and for any nodes after the directories in the - * parent node have been found. This empirically cuts the stat - * calls by about 2/3. + * Nlinks is the number of possible entries of type directory in the + * directory if we're cheating on stat calls, 0 if we're not doing + * any stat calls at all, -1 if we're doing stats on everything. */ - nlinks = sp->options & FTS_NOSTAT && sp->options & FTS_PHYSICAL ? - p->statb.st_nlink - (sp->options & FTS_SEEDOT ? 0 : 2) : -1; - - /* get max file name length that can be stored in current path */ - maxlen = sp->pathlen - p->pathlen - 1; + nlinks = + ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL) ? + cur->fts_statb.st_nlink - (ISSET(FTS_SEEDOT) ? 0 : 2) : -1; - cp = sp->path + (len = NAPPEND(p)); - *cp++ = '/'; - - level = p->level + 1; - - if (nlinks || set_node) { + /* + * If we're going to need to stat anything or we want to descend + * and stay in the directory, chdir. If this fails we keep going. + * We won't be able to stat anything, but we can still return the + * names themselves. Note, that since fts_read won't be able to + * chdir into the directory, it will have to return different path + * names than before, i.e. "a/b" instead of "b". Since the node + * has already been visited in pre-order, have to wait until the + * post-order visit to return the error. This is all fairly nasty. + * If a program needed sorted entries or stat information, they had + * better be checking FTS_NS on the returned nodes. + */ + if (nlinks || type == BREAD) if (FCHDIR(sp, dirfd(dirp))) { - if (set_node) { - errno = 0; - p->info = FTS_DNX; - } - return(NULL); + if (type == BREAD) + cur->fts_cderr = errno; + descend = nlinks = 0; + cderr = 1; + } else { + descend = 1; + cderr = 0; } - descend = 1; - } else + else descend = 0; - /* read the directory, attching each new entry to the `link' pointer */ + /* + * Figure out the max file name length that can be stored in the + * current path -- the inner loop allocates more path as necessary. + * We really wouldn't have to do the maxlen calculations here, we + * could do them in fts_read before returning the path, but it's a + * lot easier here since the length is part of the dirent structure. + * + * If not changing directories set a pointer so that we can just + * append each new name into the path. + */ + maxlen = sp->fts_pathlen - cur->fts_pathlen - 1; + len = NAPPEND(cur); + if (ISSET(FTS_NOCHDIR)) { + cp = sp->fts_path + len; + *cp++ = '/'; + } + + level = cur->fts_level + 1; + + /* Read the directory, attaching each entry to the `link' pointer. */ for (head = NULL, nitems = 0; dp = readdir(dirp);) { - if (ISDOT(dp->d_name) && !(sp->options & FTS_SEEDOT)) + if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name)) continue; - if (!(p = fts_alloc(dp->d_name, dp->d_namlen))) { - saved_errno = errno; + if (!(p = fts_alloc(sp, dp->d_name, (int)dp->d_namlen))) goto mem1; - } if (dp->d_namlen > maxlen) { - if (!fts_path((int)dp->d_namlen)) { - /* quit: this stream no longer has a path */ - sp->options |= FTS__STOP; - saved_errno = errno; - (void)free((char *)p); -mem1: fts_lfree(head); - if (set_node) - p->info = FTS_ERR; - if (descend && CHDIR(sp, "..")) { - saved_errno = errno; - sp->options |= FTS__STOP; - } + if (!fts_path(sp, (int)dp->d_namlen)) { + /* + * No more memory for path or structures. Save + * errno, free up the current structure and the + * structures already allocated. + */ +mem1: saved_errno = errno; + if (p) + free(p); + fts_lfree(head); + (void)closedir(dirp); errno = saved_errno; + cur->fts_info = FTS_ERR; + SET(FTS_STOP); return(NULL); } - maxlen = sp->pathlen - sp->cur->pathlen - 1; + maxlen = sp->fts_pathlen - sp->fts_cur->fts_pathlen - 1; } - p->pathlen = len + dp->d_namlen + 1; - p->accpath = sp->options & FTS_NOCHDIR ? p->path : p->name; - - p->parent = sp->cur; - p->level = level; + p->fts_pathlen = len + dp->d_namlen + 1; + p->fts_parent = sp->fts_cur; + p->fts_level = level; if (nlinks) { - /* make sure fts_stat has a filename to stat */ - if (sp->options & FTS_NOCHDIR) - bcopy(p->name, cp, p->namelen + 1); - p->info = fts_stat(p, 0); - if (nlinks > 0 && (p->info == FTS_D || - p->info == FTS_DNR || p->info == FTS_DNX)) + /* Build a file name for fts_stat to stat. */ + if (ISSET(FTS_NOCHDIR)) { + p->fts_accpath = p->fts_path; + bcopy(p->fts_name, cp, p->fts_namelen + 1); + } else + p->fts_accpath = p->fts_name; + p->fts_info = fts_stat(sp, p, 0); + if (nlinks > 0 && p->fts_info == FTS_D) --nlinks; - } else - p->info = FTS_NS; + } else if (cderr) { + p->fts_info = ISSET(FTS_NOSTAT) ? FTS_NSOK : FTS_NS; + p->fts_accpath = cur->fts_accpath; + } else { + p->fts_accpath = + ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name; + p->fts_info = FTS_NSOK; + } - p->link = head; + p->fts_link = head; head = p; ++nitems; } (void)closedir(dirp); - if (descend && (!nitems || !set_node) && CHDIR(sp, "..")) { - sp->options |= FTS__STOP; - p->info = FTS_ERR; - *--cp = '\0'; + /* + * If not changing directories, reset the path back to original + * state. + */ + if (ISSET(FTS_NOCHDIR)) { + if (cp - 1 > sp->fts_path) + --cp; + *cp = '\0'; + } + + /* + * If descended after called from fts_children or called from + * fts_read and didn't find anything, get back. If can't get + * back, we're done. + */ + if (descend && (!nitems || type == BCHILD) && CHDIR(sp, "..")) { + cur->fts_info = FTS_ERR; + SET(FTS_STOP); return(NULL); } + /* If we didn't find anything, just do the post-order visit */ if (!nitems) { - if (set_node) - p->info = FTS_DP; - *--cp = '\0'; + if (type == BREAD) + cur->fts_info = FTS_DP; return(NULL); } - if (sp->compar && nitems > 1) - head = fts_sort(head, nitems); - - if (set_node) - bcopy(head->name, cp, head->namelen + 1); - else - *--cp = '\0'; + /* Sort the entries. */ + if (sp->fts_compar && nitems > 1) + head = fts_sort(sp, head, nitems); return(head); } -static short -fts_stat(p, symflag) +static u_short +fts_stat(sp, p, follow) + FTS *sp; register FTSENT *p; - int symflag; + int follow; { - register int ngroups, *gp; - int gidset[NGROUPS]; + int saved_errno; /* - * detection of symbolic links w/o targets. If FTS_FOLLOW is set, - * the symlink structure is overwritten with the stat structure of - * the target. + * If doing a logical walk, or application requested FTS_FOLLOW, do + * a stat(2). If that fails, check for a non-existent symlink. If + * fail, return the errno from the stat call. */ - if (stream->options & FTS_LOGICAL || symflag) { - if (stat(p->accpath, &p->statb)) - return(symflag || !lstat(p->accpath, &p->statb) ? - FTS_SLNONE : FTS_ERR); - } else if (lstat(p->accpath, &p->statb)) - return(FTS_ERR); - - switch(p->statb.st_mode&S_IFMT) { - case S_IFDIR: - /* get new uid/groups each time, they may have changed */ - if (getuid() == p->statb.st_uid) { - if (!(p->statb.st_mode&S_IRUSR)) - return(FTS_DNR); - if (!(p->statb.st_mode&S_IXUSR)) - return(FTS_DNX); - return(FTS_D); + if (ISSET(FTS_LOGICAL) || follow) { + if (stat(p->fts_accpath, &p->fts_statb)) { + saved_errno = errno; + if (!lstat(p->fts_accpath, &p->fts_statb)) { + errno = 0; + return(FTS_SLNONE); + } + errno = saved_errno; + bzero(&p->fts_statb, sizeof(struct stat)); + return(FTS_NS); } - if ((ngroups = getgroups(NGROUPS, gidset)) == -1) - return(FTS_ERR); - for (gp = gidset; ngroups--;) - if (*gp++ == p->statb.st_gid) { - if (!(p->statb.st_mode&S_IRGRP)) - return(FTS_DNR); - if (!(p->statb.st_mode&S_IXGRP)) - return(FTS_DNX); - return(FTS_D); - } - if (!(p->statb.st_mode&S_IROTH)) - return(FTS_DNR); - if (!(p->statb.st_mode&S_IXOTH)) - return(FTS_DNX); - return(FTS_D); - case S_IFLNK: - return(FTS_SL); - case S_IFREG: - return(FTS_F); - default: - return(FTS_DEFAULT); + } else if (lstat(p->fts_accpath, &p->fts_statb)) { + bzero(&p->fts_statb, sizeof(struct stat)); + return(FTS_NS); } - /* NOTREACHED */ -} - -static FTSENT * -fts_cycle(p) - register FTSENT *p; -{ - register dev_t dev; - register ino_t ino; /* - * cycle detection is brute force; if the tree gets deep enough or - * the number of symbolic links to directories is really high - * something faster might be worthwhile. + * Cycle detection is done as soon as we find a directory. Detection + * is by brute force; if the tree gets deep enough or the number of + * symbolic links to directories high enough something faster might + * be worthwhile. */ - dev = p->statb.st_dev; - ino = p->statb.st_ino; - for (p = p->parent; p->level > ROOTLEVEL; p = p->parent) - if (ino == p->statb.st_ino && dev == p->statb.st_dev) - return(p); - return(NULL); + if (S_ISDIR(p->fts_statb.st_mode)) { + register FTSENT *t; + register dev_t dev; + register ino_t ino; + + dev = p->fts_statb.st_dev; + ino = p->fts_statb.st_ino; + for (t = p->fts_parent; t->fts_level > FTS_ROOTLEVEL; + t = t->fts_parent) + if (ino == t->fts_statb.st_ino && + dev == t->fts_statb.st_dev) { + sp->fts_savelink = p->fts_link; + p->fts_link = t; + return(FTS_DC); + } + return(FTS_D); + } + if (S_ISLNK(p->fts_statb.st_mode)) + return(FTS_SL); + if (S_ISREG(p->fts_statb.st_mode)) + return(FTS_F); + return(FTS_DEFAULT); } #define R(type, nelem, ptr) \ - (type *)realloc((char *)ptr, (u_int)((nelem) * sizeof(type))) + (type *)realloc((void *)ptr, (u_int)((nelem) * sizeof(type))) static FTSENT * -fts_sort(head, nitems) +fts_sort(sp, head, nitems) + FTS *sp; FTSENT *head; register int nitems; { register FTSENT **ap, *p; /* - * construct an array of pointers to the structures and call qsort(3). + * Construct an array of pointers to the structures and call qsort(3). * Reassemble the array in the order returned by qsort. If unable to * sort for memory reasons, return the directory entries in their * current order. Allocate enough space for the current needs plus * 40 so we don't realloc one entry at a time. */ - if (nitems > stream->nitems) { - stream->nitems = nitems + 40; - if (!(stream->array = - R(FTSENT *, stream->nitems, stream->array))) { - stream->nitems = 0; + if (nitems > sp->fts_nitems) { + sp->fts_nitems = nitems + 40; + if (!(sp->fts_array = + R(FTSENT *, sp->fts_nitems, sp->fts_array))) { + sp->fts_nitems = 0; return(head); } } - for (ap = stream->array, p = head; p; p = p->link) + for (ap = sp->fts_array, p = head; p; p = p->fts_link) *ap++ = p; - qsort((char *)stream->array, nitems, sizeof(FTSENT *), stream->compar); - for (head = *(ap = stream->array); --nitems; ++ap) - ap[0]->link = ap[1]; - ap[0]->link = NULL; + qsort((void *)sp->fts_array, nitems, sizeof(FTSENT *), sp->fts_compar); + for (head = *(ap = sp->fts_array); --nitems; ++ap) + ap[0]->fts_link = ap[1]; + ap[0]->fts_link = NULL; return(head); } static FTSENT * -fts_alloc(name, len) +fts_alloc(sp, name, len) + FTS *sp; char *name; register int len; { register FTSENT *p; /* - * variable sized structures; the name is the last element so - * allocate enough extra space after the structure to hold it. + * Variable sized structures; the name is the last element so + * we allocate enough extra space after the structure to store + * it. */ - if (!(p = (FTSENT *)malloc((u_int)(sizeof(FTSENT) + len)))) + if (!(p = (FTSENT *)malloc((size_t)(sizeof(FTSENT) + len)))) return(NULL); - bcopy(name, p->name, len + 1); - p->namelen = len; - p->path = stream->path; - p->instr = 0; - p->local.number = 0; - p->local.pointer = NULL; + bcopy(name, p->fts_name, len + 1); + p->fts_namelen = len; + p->fts_path = sp->fts_path; + p->fts_instr = FTS_NOINSTR; + p->fts_cderr = 0; + p->fts_number = 0; + p->fts_pointer = NULL; return(p); } -static +static void fts_lfree(head) register FTSENT *head; { register FTSENT *p; + /* Free a linked list of structures. */ while (p = head) { - head = head->link; - (void)free((char *)p); + head = head->fts_link; + free(p); } } /* - * allow essentially unlimited paths; certain programs (find, remove, ls) - * need to work on any tree. Most systems will allow creation of paths - * much longer than MAXPATHLEN, even though the kernel won't resolve them. - * Add an extra 128 bytes to the requested size so that we don't realloc - * the path 2 bytes at a time. + * Allow essentially unlimited paths; certain programs (find, rm, ls) need to + * work on any tree. Most systems will allow creation of paths much longer + * than MAXPATHLEN, even though the kernel won't resolve them. Add an extra + * 128 bytes to the requested size so that we don't realloc the path 2 bytes + * at a time. */ -static -fts_path(size) +static char * +fts_path(sp, size) + FTS *sp; int size; { - stream->pathlen += size + 128; - return((int)(stream->path = R(char, stream->pathlen, stream->path))); -} - -static FTSENT * -fts_root(name) - register char *name; -{ - register char *cp; - - /* - * rip trailing slashes; it's somewhat unclear in POSIX 1003.1 what - * /a/b/ really is, they don't talk about what a null path component - * resolves to. This hopefully does what the user intended. Don't - * allow null pathnames. - */ - for (cp = name; *cp; ++cp); - if (cp == name) { - errno = ENOENT; - return(NULL); - } - while (--cp > name && *cp == '/'); - *++cp = '\0'; - return(fts_alloc(name, cp - name)); + sp->fts_pathlen += size + 128; + return(sp->fts_path = R(char, sp->fts_pathlen, sp->fts_path)); }