BSD 4_3_Net_2 release

[unix-history] / usr / src / lib / libc / gen / fts.c

diff --git a/usr/src/lib/libc/gen/fts.c b/usr/src/lib/libc/gen/fts.c
index 296d5d1..e2958d3 100644 (file)
--- 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.
  *
  * 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)
  */
 
 #if defined(LIBC_SCCS) && !defined(lint)

-static char sccsid[] = "@(#)fts.c      5.3 (Berkeley) %G%";
+static char sccsid[] = "@(#)fts.c      5.19 (Berkeley) 5/9/91";

 #endif /* LIBC_SCCS and not lint */
 
 #endif /* LIBC_SCCS and not lint */
 

+#include <sys/cdefs.h>

 #include <sys/param.h>
 #include <sys/stat.h>
 #include <sys/param.h>
 #include <sys/stat.h>

+#include <fcntl.h>

 #include <dirent.h>
 #include <errno.h>
 #include <dirent.h>
 #include <errno.h>

-#include <fts.h>
-#include <strings.h>
-
-extern int errno;
+#include "fts.h"
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>

 
 

-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 *
 
 FTS *

-ftsopen(argv, options, compar)
-       char *argv[];
+fts_open(argv, options, compar)
+       char * const *argv;

        register int options;
        int (*compar)();
 {
        register int options;
        int (*compar)();
 {


@@ -58,602 +71,717 @@ ftsopen(argv, options, compar)
        register FTSENT *p, *root;
        register int nitems, maxlen;
        FTSENT *parent, *tmp;
        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));
                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;
                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);
 
 
        return(sp);
 

+mem3:  free(sp->fts_cur);

 mem2:  fts_lfree(root);
 mem2:  fts_lfree(root);

-       (void)free((char *)parent);
-mem1:  (void)free((char *)sp);
+       free(parent);
+mem1:  free(sp);

        return(NULL);
 }
 
        return(NULL);
 }
 

-static
-fts_load(p)
+static void
+fts_load(sp, p)
+       FTS *sp;

        register FTSENT *p;
 {
        register int len;
        register char *cp;
 
        /*
        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.
         */
         * 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);
                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;
 
        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);
 }
 
                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 *
 FTSENT *

-ftsread(sp)
+fts_read(sp)

        register FTS *sp;
 {
        register FTS *sp;
 {

-       register FTSENT *p;
+       register FTSENT *p, *tmp;

        register int instr;
        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);
 
                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) {
        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);
        }
 
        /*
                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);
+               }
+               p = sp->fts_child;
+               sp->fts_child = NULL;
+               goto name;
+       }
+
+       /* 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;

                }
                }

-               return(sp->cur = p);
+
+name:          t = sp->fts_path + NAPPEND(p->fts_parent);
+               *t++ = '/';
+               bcopy(p->fts_name, t, p->fts_namelen + 1);
+               return(sp->fts_cur = p);

        }
 
        }
 

-       /* go to parent */
-       p = sp->cur->parent;
-       (void)free((char *)sp->cur);
-       if (p->level == ROOTPARENTLEVEL) {
+       /* 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.
                 */
                 * can distinguish between error and EOF.
                 */

-               (void)free((char *)p);
+               free(p);

                errno = 0;
                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
        } 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
  * 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 */
  */
 /* ARGSUSED */

-ftsset(sp, p, instr)
+fts_set(sp, p, instr)

        FTS *sp;
        FTSENT *p;
        int instr;
 {
        FTS *sp;
        FTSENT *p;
        int instr;
 {

-       p->instr = instr;
+       p->fts_instr = instr;

        return(0);
 }
 
 FTSENT *
        return(0);
 }
 
 FTSENT *

-ftschildren(sp)
+fts_children(sp)

        register FTS *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;
         */
        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);
+
+       /* 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);
                return(NULL);

-       if (sp->child)
-               fts_lfree(sp->child);
-       return(sp->child = fts_build(sp, 0));
+       (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 *
 #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;
        register FTS *sp;

-       int set_node;
+       int type;

 {
        register struct dirent *dp;
        register FTSENT *p, *head;
        register int nitems;
 {
        register struct dirent *dp;
        register FTSENT *p, *head;
        register int nitems;

+       FTSENT *cur;

        DIR *dirp;
        DIR *dirp;

-       int descend, len, level, maxlen, nlinks, saved_errno;
+       int cderr, descend, len, level, maxlen, nlinks, saved_errno;

        char *cp;
 
        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);
        }
 
        /*
                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;
+       nlinks =
+           ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL) ?
+           cur->fts_statb.st_nlink - (ISSET(FTS_SEEDOT) ? 0 : 2) : -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 (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;
 
                descend = 0;
 

-       /* get max file name length that can be stored in current path */
-       maxlen = sp->pathlen - p->pathlen - 1;
-
-       cp = sp->path + (len = NAPPEND(p));
-       *cp++ = '/';
+       /*
+        * 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 = p->level + 1;
+       level = cur->fts_level + 1;

 
 

-       /* read the directory, attching each new entry to the `link' pointer */
+       /* Read the directory, attaching each entry to the `link' pointer. */

        for (head = NULL, nitems = 0; dp = readdir(dirp);) {
        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;
 
                        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;
                        goto mem1;

-               }

                if (dp->d_namlen > maxlen) {
                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;
                                errno = saved_errno;

+                               cur->fts_info = FTS_ERR;
+                               SET(FTS_STOP);

                                return(NULL);
                        }
                                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) {
 
                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;
                                --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);
 
                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);
        }
 
                return(NULL);
        }
 

+       /* If we didn't find anything, just do the post-order visit */

        if (!nitems) {
        if (!nitems) {

-               if (set_node)
-                       p->info = FTS_DP;
-               *--cp = '\0';
+               if (type == BREAD)
+                       cur->fts_info = FTS_DP;

                return(NULL);
        }
 
                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);
 }
 
        return(head);
 }
 

-static short
-fts_stat(p, symflag)
+static u_short
+fts_stat(sp, p, follow)
+       FTS *sp;

        register FTSENT *p;
        register FTSENT *p;

-       int symflag;
+       int follow;

 {
 {

+       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:
-               return(FTS_D);
-       case S_IFLNK:
-               return(FTS_SL);
-       case S_IFREG:
-               return(FTS_F);
+       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);
+               }
+       } else if (lstat(p->fts_accpath, &p->fts_statb)) {
+               bzero(&p->fts_statb, sizeof(struct stat));
+               return(FTS_NS);

        }
        }

-       return(FTS_DEFAULT);
-}
-
-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) \
 }
 
 #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 *
 
 static FTSENT *

-fts_sort(head, nitems)
+fts_sort(sp, head, nitems)
+       FTS *sp;

        FTSENT *head;
        register int nitems;
 {
        register FTSENT **ap, *p;
 
        /*
        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.
         */
         * 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);
                }
        }
                        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;
                *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 *
        return(head);
 }
 
 static FTSENT *

-fts_alloc(name, len)
+fts_alloc(sp, name, len)
+       FTS *sp;

        char *name;
        register int len;
 {
        register FTSENT *p;
 
        /*
        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);
                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);
 }
 
        return(p);
 }
 

-static
+static void

 fts_lfree(head)
        register FTSENT *head;
 {
        register FTSENT *p;
 
 fts_lfree(head)
        register FTSENT *head;
 {
        register FTSENT *p;
 

+       /* Free a linked list of structures. */

        while (p = head) {
        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;
 {
        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));

 }
 }