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 ccd1181..e2958d3 100644 (file)
--- a/usr/src/lib/libc/gen/fts.c
+++ b/usr/src/lib/libc/gen/fts.c
@@ -2,33 +2,54 @@
  * Copyright (c) 1990 The Regents of the University of California.
  * All rights reserved.
  *
  * Copyright (c) 1990 The Regents of the University of California.
  * All rights reserved.
  *

- * %sccs.include.redist.c%
+ * 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.11 (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 <fcntl.h>
 #include <dirent.h>
 #include <errno.h>
 #include <sys/param.h>
 #include <sys/stat.h>
 #include <fcntl.h>
 #include <dirent.h>
 #include <errno.h>

-#include <fts.h>
-#include <string.h>
+#include "fts.h"

 #include <stdlib.h>
 #include <stdlib.h>

+#include <string.h>
+#include <unistd.h>

 
 

-FTSENT *fts_alloc(), *fts_build(), *fts_cycle(), *fts_root(), *fts_sort();
-void fts_lfree(), fts_load();
-u_short fts_stat();
-
-/*
- * Special case a root of "/" so that slashes aren't appended causing
- * paths to be written as "//foo".
- */
-#define        NAPPEND(p) \
-       (p->fts_level == ROOTLEVEL && p->fts_pathlen == 1 && \
-           p->fts_path[0] == '/' ? 0 : p->fts_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        ISSET(opt)      (sp->fts_options & opt)
 #define        SET(opt)        (sp->fts_options |= opt)
 
 #define        ISSET(opt)      (sp->fts_options & opt)
 #define        SET(opt)        (sp->fts_options |= opt)


@@ -40,13 +61,9 @@ u_short fts_stat();
 #define        BCHILD          1               /* from fts_children */
 #define        BREAD           2               /* from fts_read */
 
 #define        BCHILD          1               /* from fts_children */
 #define        BREAD           2               /* from fts_read */
 

-/* fts_level values */
-#define        ROOTLEVEL       0
-#define        ROOTPARENTLEVEL -1
-

 FTS *
 fts_open(argv, options, compar)
 FTS *
 fts_open(argv, options, compar)

-       char *argv[];
+       char * const *argv;

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


@@ -54,7 +71,7 @@ fts_open(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 *fts_path();
+       int len;

 
        /* Allocate/initialize the stream */
        if (!(sp = (FTS *)malloc((u_int)sizeof(FTS))))
 
        /* Allocate/initialize the stream */
        if (!(sp = (FTS *)malloc((u_int)sizeof(FTS))))


@@ -70,15 +87,20 @@ fts_open(argv, options, compar)
        /* Allocate/initialize root's parent. */
        if (!(parent = fts_alloc(sp, "", 0)))
                goto mem1;
        /* Allocate/initialize root's parent. */
        if (!(parent = fts_alloc(sp, "", 0)))
                goto mem1;

-       parent->fts_level = ROOTPARENTLEVEL;
+       parent->fts_level = FTS_ROOTPARENTLEVEL;

 
        /* Allocate/initialize root(s). */
        maxlen = -1;
        for (root = NULL, nitems = 0; *argv; ++argv, ++nitems) {
 
        /* Allocate/initialize root(s). */
        maxlen = -1;
        for (root = NULL, nitems = 0; *argv; ++argv, ++nitems) {

-               if (!(p = fts_root(sp, *argv)))
+               if (!(len = strlen(*argv))) {
+                       errno = ENOENT;

                        goto mem2;
                        goto mem2;

-               if (maxlen < p->fts_namelen)
-                       maxlen = p->fts_namelen;
+               }
+               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 comparison routine supplied, traverse in sorted
                 * order; otherwise traverse in the order specified.


@@ -98,8 +120,6 @@ fts_open(argv, options, compar)
                                tmp = p;
                        }
                }
                                tmp = p;
                        }
                }

-               p->fts_level = ROOTLEVEL;
-               p->fts_parent = parent;

        }
        if (compar && nitems > 1)
                root = fts_sort(sp, root, nitems);
        }
        if (compar && nitems > 1)
                root = fts_sort(sp, root, nitems);


@@ -125,15 +145,15 @@ fts_open(argv, options, compar)
         * and ".." are all fairly nasty problems.  Note, if we can't get the
         * descriptor we run anyway, just more slowly.
         */
         * and ".." are all fairly nasty problems.  Note, if we can't get the
         * descriptor we run anyway, just more slowly.
         */

-       if (!ISSET(FTS_NOCHDIR) && (sp->fts_sd = open(".", O_RDONLY, 0)) < 0)
+       if (!ISSET(FTS_NOCHDIR) && (sp->fts_rfd = open(".", O_RDONLY, 0)) < 0)

                SET(FTS_NOCHDIR);
 
        return(sp);
 
                SET(FTS_NOCHDIR);
 
        return(sp);
 

-mem3:  free((void *)sp->fts_cur);
+mem3:  free(sp->fts_cur);

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

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

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


@@ -146,9 +166,10 @@ fts_load(sp, p)
        register char *cp;
 
        /*
        register char *cp;
 
        /*

-        * Load the stream structure for the next traversal; set the
-        * fts_accpath field specially so the chdir gets done to the
-        * right place and the user can access the first node.
+        * 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->fts_pathlen = p->fts_namelen;
        bcopy(p->fts_name, sp->fts_path, len + 1);
         */
        len = p->fts_pathlen = p->fts_namelen;
        bcopy(p->fts_name, sp->fts_path, len + 1);


@@ -158,6 +179,9 @@ fts_load(sp, p)
                p->fts_namelen = len;
        }
        p->fts_accpath = p->fts_path = sp->fts_path;
                p->fts_namelen = len;
        }
        p->fts_accpath = p->fts_path = sp->fts_path;

+
+       p->fts_info = fts_stat(sp, p, 0);
+       sp->rdev = p->fts_statb.st_dev;

 }
 
 fts_close(sp)
 }
 
 fts_close(sp)


@@ -172,32 +196,29 @@ fts_close(sp)
                 * structure points to the root list, so we step through to
                 * the end of the root list which has a valid parent pointer.
                 */
                 * 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 > ROOTPARENTLEVEL;) {
+               for (p = sp->fts_cur; p->fts_level > FTS_ROOTPARENTLEVEL;) {

                        freep = p;
                        p = p->fts_link ? p->fts_link : p->fts_parent;
                        freep = p;
                        p = p->fts_link ? p->fts_link : p->fts_parent;

-                       free((void *)freep);
+                       free(freep);

                }
                }

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

        }
 
        /* Free up child linked list, sort array, path buffer. */
        if (sp->fts_child)
                fts_lfree(sp->fts_child);
        if (sp->fts_array)
        }
 
        /* Free up child linked list, sort array, path buffer. */
        if (sp->fts_child)
                fts_lfree(sp->fts_child);
        if (sp->fts_array)

-               free((void *)sp->fts_array);
-       free((char *)sp->fts_path);
+               free(sp->fts_array);
+       free(sp->fts_path);

 
 

-       /*
-        * Return to original directory, save errno if necessary; free up
-        * the directory buffer.
-        */
+       /* Return to original directory, save errno if necessary. */

        if (!ISSET(FTS_NOCHDIR)) {
        if (!ISSET(FTS_NOCHDIR)) {

-               saved_errno = fchdir(sp->fts_sd) ? errno : 0;
-               (void)close(sp->fts_sd);
+               saved_errno = fchdir(sp->fts_rfd) ? errno : 0;
+               (void)close(sp->fts_rfd);

        }
 
        /* Free up the stream pointer. */
        }
 
        /* Free up the stream pointer. */

-       free((void *)sp);
+       free(sp);

 
        /* Set errno and return. */
        if (!ISSET(FTS_NOCHDIR) && saved_errno) {
 
        /* Set errno and return. */
        if (!ISSET(FTS_NOCHDIR) && saved_errno) {


@@ -207,17 +228,24 @@ fts_close(sp)
        return(0);
 }
 
        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 *
 fts_read(sp)
        register FTS *sp;
 {
        register FTSENT *p, *tmp;
        register int instr;
 FTSENT *
 fts_read(sp)
        register FTS *sp;
 {
        register FTSENT *p, *tmp;
        register int instr;

-       register char *cp;
-       static int cd;
+       register char *t;

 
        /* If finished or unrecoverable error, return NULL. */
 
        /* If finished or unrecoverable error, return NULL. */

-       if (!sp->fts_cur || ISSET(FTS__STOP))
+       if (!sp->fts_cur || ISSET(FTS_STOP))

                return(NULL);
 
        /* Set current node pointer. */
                return(NULL);
 
        /* Set current node pointer. */


@@ -225,7 +253,7 @@ fts_read(sp)
 
        /* Save and zero out user instructions. */
        instr = p->fts_instr;
 
        /* Save and zero out user instructions. */
        instr = p->fts_instr;

-       p->fts_instr = FTS__NOINSTR;
+       p->fts_instr = FTS_NOINSTR;

 
        /* If used fts_link pointer for cycle detection, restore it. */
        if (sp->fts_savelink) {
 
        /* If used fts_link pointer for cycle detection, restore it. */
        if (sp->fts_savelink) {


@@ -233,14 +261,18 @@ fts_read(sp)
                sp->fts_savelink = NULL;
        }
 
                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->fts_info = fts_stat(sp, p, 0);
                return(p);
        }
 
        if (instr == FTS_AGAIN) {
                p->fts_info = fts_stat(sp, p, 0);
                return(p);
        }
 

-       /* Following a symbolic link. */
-       if (p->fts_info == FTS_SL && instr == FTS_FOLLOW) {
+       /*
+        * Following a symlink -- SLNONE test allows application to see
+        * SLNONE and recover.
+        */
+       if (instr == FTS_FOLLOW &&
+           (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) {

                p->fts_info = fts_stat(sp, p, 1);
                return(p);
        }
                p->fts_info = fts_stat(sp, p, 1);
                return(p);
        }


@@ -248,8 +280,8 @@ fts_read(sp)
        /* Directory in pre-order. */
        if (p->fts_info == FTS_D) {
                /* If skipped or crossed mount point, do post-order visit. */
        /* 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->sdev) {
+               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;
                        if (sp->fts_child) {
                                fts_lfree(sp->fts_child);
                                sp->fts_child = NULL;


@@ -258,91 +290,105 @@ fts_read(sp)
                        return(p);
                } 
 
                        return(p);
                } 
 

-               /* Read the directory if necessary, and return first entry. */
-               if (sp->fts_child) 
+               /*
+                * 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 (sp->fts_child) {

                        if (CHDIR(sp, p->fts_accpath)) {
                        if (CHDIR(sp, p->fts_accpath)) {

-                               fts_lfree(sp->fts_child);
-                               p->fts_info = FTS_DNX;
-                       } else {
-                               p = sp->fts_child;
-                               cp = sp->fts_path + NAPPEND(p->fts_parent);
-                               *cp++ = '/';
-                               bcopy(p->fts_name, cp, p->fts_namelen + 1);
+                               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)))
-                               return(p);
-                       p = sp->fts_child;
+               } 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;
                sp->fts_child = NULL;

-               return(sp->fts_cur = p);
+               goto name;

        }
 
        /* Move to next node on this level. */
 next:  tmp = p;
        if (p = p->fts_link) {
        }
 
        /* Move to next node on this level. */
 next:  tmp = p;
        if (p = p->fts_link) {

-               /*
-                * If root level node, set up paths and return.  If not the
-                * first time, and it's not an absolute pathname, get back
-                * to starting directory.  If that fails, we're dead.
-                */
-               if (p->fts_level == ROOTLEVEL) {
-                       fts_load(sp, p);
-                       free((void *)tmp);
-                       if (cd &&
-                           p->fts_path[0] != '/' && FCHDIR(sp, sp->fts_sd)) {
-                               /* Can't get back to start; we're dead. */
-                               p->fts_path = "starting directory";
-                               p->fts_info = FTS_ERR;
-                               SET(FTS__STOP);
-                               return(sp->fts_cur = p);
-                       } 
-                       cd = 1;
-                       p->fts_info = fts_stat(sp, p, 0);
-                       sp->sdev = p->fts_statb.st_dev;
-               } else {
-                       free((void *)tmp);
-
-                       /* User may have called fts_set on 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;
-                       }
+               free(tmp);

 
 

-                       /* Fill in the paths. */
-                       cp = sp->fts_path + NAPPEND(p->fts_parent);
-                       *cp++ = '/';
-                       bcopy(p->fts_name, cp, p->fts_namelen + 1);
+               /* 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);
+               }

 
 

-                       /* Check for directory cycles. */
-                       if (p->fts_info == FTS_D && (tmp = fts_cycle(p))) {
-                               sp->fts_savelink = p->fts_link;
-                               p->fts_link = tmp;
-                               p->fts_info = FTS_DC;
-                       }
+               /* 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);
        }
 
                return(sp->fts_cur = p);
        }
 

-       /* Move to parent. */
+       /* Move up to the parent node. */

        p = tmp->fts_parent;
        p = tmp->fts_parent;

-       free((void *)tmp);
+       free(tmp);

 
 

-       if (p->fts_level == ROOTPARENTLEVEL) {
+       if (p->fts_level == FTS_ROOTPARENTLEVEL) {

                /*
                 * Done; free everything up and set errno to 0 so the user
                 * can distinguish between error and EOF.
                 */
                /*
                 * Done; free everything up and set errno to 0 so the user
                 * can distinguish between error and EOF.
                 */

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

                errno = 0;
                return(sp->fts_cur = NULL);
        }
 
        sp->fts_path[p->fts_pathlen] = '\0';
                errno = 0;
                return(sp->fts_cur = NULL);
        }
 
        sp->fts_path[p->fts_pathlen] = '\0';

-       if (CHDIR(sp, "..")) {
-               SET(FTS__STOP);
+
+       /*
+        * 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->fts_info = FTS_DP;
                p->fts_info = FTS_ERR;
        } else
                p->fts_info = FTS_DP;


@@ -350,7 +396,7 @@ next:       tmp = p;
 }
 
 /*
 }
 
 /*

- * fts_set 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 fts_set.  An error return is allowed for similar
  * reasons.
  * implementation; it would be necessary if anyone wanted to add global
  * semantics to fts using fts_set.  An error return is allowed for similar
  * reasons.


@@ -377,12 +423,12 @@ fts_children(sp)
 
        /*
         * Set errno to 0 so that user can tell the difference between an
 
        /*
         * Set errno to 0 so that user can tell the difference between an

-        * error and a directory without entries.
+        * 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 (ISSET(FTS__STOP) ||
-           p->fts_info != FTS_D && p->fts_info != FTS_DNX &&
-           p->fts_info != FTS_DNR)
+       if (ISSET(FTS_STOP) || p->fts_info != FTS_D && p->fts_info != FTS_DNR)

                return(NULL);
 
        /* Free up any previous child list. */
                return(NULL);
 
        /* Free up any previous child list. */


@@ -391,12 +437,12 @@ fts_children(sp)
 
        /*
         * If using chdir on a relative path and called BEFORE fts_read does
 
        /*
         * If using chdir on a relative path and called BEFORE fts_read does

-        * its chdir to the root of a traversal, we can lose because we need
-        * to chdir into the subdirectory, and we don't know where the current
-        * directory is to get back so that the upcoming chdir by fts_read
-        * will work.
+        * 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 != ROOTLEVEL || p->fts_accpath[0] == '/' ||
+       if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' ||

            ISSET(FTS_NOCHDIR))
                return(sp->fts_child = fts_build(sp, BCHILD));
 
            ISSET(FTS_NOCHDIR))
                return(sp->fts_child = fts_build(sp, BCHILD));
 


@@ -409,9 +455,21 @@ fts_children(sp)
        return(sp->fts_child);
 }
 
        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]))
 
 #define        ISDOT(a)        (a[0] == '.' && (!a[1] || a[1] == '.' && !a[2]))
 

-FTSENT *
+static FTSENT *

 fts_build(sp, type)
        register FTS *sp;
        int type;
 fts_build(sp, type)
        register FTS *sp;
        int type;


@@ -419,114 +477,126 @@ fts_build(sp, 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;
 
        /* Set current node pointer. */
        char *cp;
 
        /* Set current node pointer. */

-       p = sp->fts_cur;
+       cur = sp->fts_cur;

 
 

-       if (!(dirp = opendir(p->fts_accpath))) {
-               if (type == BREAD) {
-                       p->fts_info = FTS_DNR;
-                       errno = 0;
-               }
+       /*
+        * 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 =
            ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL) ?
         */
        nlinks =
            ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL) ?

-           p->fts_statb.st_nlink - (ISSET(FTS_SEEDOT) ? 0 : 2) : -1;
+           cur->fts_statb.st_nlink - (ISSET(FTS_SEEDOT) ? 0 : 2) : -1;

 
 

-       /* If told to descend or found links and not told not to descend. */
-       descend = 0;
+       /*
+        * 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 (nlinks || type == BREAD)

-               if (!FCHDIR(sp, dirfd(dirp))) 
+               if (FCHDIR(sp, dirfd(dirp))) {
+                       if (type == BREAD)
+                               cur->fts_cderr = errno;
+                       descend = nlinks = 0;
+                       cderr = 1;
+               } else {

                        descend = 1;
                        descend = 1;

-               /*
-                * Return all the information possible; fts_read doing a
-                * relative walk of the tree will have to descend, so it
-                * can't succeed.  Fts_children or absolute walks of the
-                * tree can succeed, but no stat information will be available.
-                */
-               else {
-                       if (type == BREAD) {
-                               (void)closedir(dirp);
-                               p->fts_info = FTS_DNX;
-                               errno = 0;
-                               return(NULL);
-                       }
-                       nlinks = 0;
+                       cderr = 0;

                }
                }

+       else
+               descend = 0;

 
 

-       /* Get max file name length that can be stored in current path. */
-       maxlen = sp->fts_pathlen - p->fts_pathlen - 1;
-
-       cp = sp->fts_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->fts_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) && !ISSET(FTS_SEEDOT))
+               if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))

                        continue;
 
                        continue;
 

-               if (!(p = fts_alloc(sp, dp->d_name, (int)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 (!fts_path(sp, (int)dp->d_namlen)) {
                if (dp->d_namlen > maxlen) {
                        if (!fts_path(sp, (int)dp->d_namlen)) {

-                               /* Quit: this stream no longer has a path. */
-                               SET(FTS__STOP);
-                               saved_errno = errno;
-                               free((void *)p);
-mem1:                          fts_lfree(head);
-                               if (type == BREAD)
-                                       p->fts_info = FTS_ERR;
-                               if (descend && CHDIR(sp, "..")) {
-                                       /*
-                                        * chdir error is more interesting
-                                        * than memory error, since it stops
-                                        * everything.
-                                        */
-                                       saved_errno = errno;
-                                       SET(FTS__STOP);
-                               }
-                               errno = saved_errno;
+                               /*
+                                * 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);
                                (void)closedir(dirp);

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

                                return(NULL);
                        }
                        maxlen = sp->fts_pathlen - sp->fts_cur->fts_pathlen - 1;
                }
 
                p->fts_pathlen = len + dp->d_namlen + 1;
                                return(NULL);
                        }
                        maxlen = sp->fts_pathlen - sp->fts_cur->fts_pathlen - 1;
                }
 
                p->fts_pathlen = len + dp->d_namlen + 1;

-               p->fts_accpath = ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name;
-

                p->fts_parent = sp->fts_cur;
                p->fts_level = level;
 
                if (nlinks) {
                p->fts_parent = sp->fts_cur;
                p->fts_level = level;
 
                if (nlinks) {

-                       /* Make sure fts_stat has a filename to stat. */
-                       if (ISSET(FTS_NOCHDIR))
+                       /* 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);
                                bcopy(p->fts_name, cp, p->fts_namelen + 1);

+                       } else
+                               p->fts_accpath = p->fts_name;

                        p->fts_info = fts_stat(sp, p, 0);
                        p->fts_info = fts_stat(sp, p, 0);

-                       if (nlinks > 0 && (p->fts_info == FTS_D ||
-                           p->fts_info == FTS_DNR || p->fts_info == FTS_DNX))
+                       if (nlinks > 0 && p->fts_info == FTS_D)

                                --nlinks;
                                --nlinks;

-               } else
-                       p->fts_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->fts_link = head;
                head = p;
 
                p->fts_link = head;
                head = p;


@@ -534,34 +604,37 @@ mem1:                             fts_lfree(head);
        }
        (void)closedir(dirp);
 
        }
        (void)closedir(dirp);
 

-       /* Reset the path. */
-       if (cp - 1 > sp->fts_path)
-               --cp;
-       *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: if were called from fts_read and didn't find anything,
-        * or were called from fts_children, get back.
+        * 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, "..")) {
         */
        if (descend && (!nitems || type == BCHILD) && CHDIR(sp, "..")) {

-               SET(FTS__STOP);
-               p->fts_info = FTS_ERR;
+               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 (type == BREAD)
        if (!nitems) {
                if (type == BREAD)

-                       p->fts_info = FTS_DP;
+                       cur->fts_info = FTS_DP;

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

+       /* Sort the entries. */

        if (sp->fts_compar && nitems > 1)
                head = fts_sort(sp, head, nitems);
        if (sp->fts_compar && nitems > 1)
                head = fts_sort(sp, head, nitems);

-
-       if (type == BREAD) {
-               *cp = '/';
-               bcopy(head->fts_name, cp + 1, head->fts_namelen + 1);
-       }

        return(head);
 }
 
        return(head);
 }
 


@@ -571,31 +644,52 @@ fts_stat(sp, p, follow)
        register FTSENT *p;
        int follow;
 {
        register FTSENT *p;
        int follow;
 {

+       int saved_errno;
+

        /*
         * If doing a logical walk, or application requested FTS_FOLLOW, do
        /*
         * If doing a logical walk, or application requested FTS_FOLLOW, do

-        * a stat(2).  If that fails, either fail or do an lstat(2) for a
-        * non-existent symlink.  (The check has to be done, or we wouldn't
-        * detect a symlink being deleted.)
-        *
-        * Don't leave errno set for FTS_NS cases.              XXX
+        * a stat(2).  If that fails, check for a non-existent symlink.  If
+        * fail, return the errno from the stat call.

         */
        if (ISSET(FTS_LOGICAL) || follow) {
                if (stat(p->fts_accpath, &p->fts_statb)) {
         */
        if (ISSET(FTS_LOGICAL) || follow) {
                if (stat(p->fts_accpath, &p->fts_statb)) {

-                       errno = 0;
-                       if (follow && !lstat(p->fts_accpath, &p->fts_statb))
-                               return(FTS_SLNONE);
-                       else {
+                       saved_errno = errno;
+                       if (!lstat(p->fts_accpath, &p->fts_statb)) {

                                errno = 0;
                                errno = 0;

-                               return(FTS_NS);
-                       }
+                               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)) {
                }
        } else if (lstat(p->fts_accpath, &p->fts_statb)) {

-               errno = 0;
+               bzero(&p->fts_statb, sizeof(struct stat));

                return(FTS_NS);
        }
 
                return(FTS_NS);
        }
 

-       if (S_ISDIR(p->fts_statb.st_mode))
+       /*
+        * 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.
+        */
+       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);
                return(FTS_D);

+       }

        if (S_ISLNK(p->fts_statb.st_mode))
                return(FTS_SL);
        if (S_ISREG(p->fts_statb.st_mode))
        if (S_ISLNK(p->fts_statb.st_mode))
                return(FTS_SL);
        if (S_ISREG(p->fts_statb.st_mode))


@@ -603,26 +697,6 @@ fts_stat(sp, p, follow)
        return(FTS_DEFAULT);
 }
 
        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.
-        */
-       dev = p->fts_statb.st_dev;
-       ino = p->fts_statb.st_ino;
-       for (p = p->fts_parent; p->fts_level > ROOTLEVEL; p = p->fts_parent)
-               if (ino == p->fts_statb.st_ino && dev == p->fts_statb.st_dev)
-                       return(p);
-       return(NULL);
-}
-

 #define        R(type, nelem, ptr) \
        (type *)realloc((void *)ptr, (u_int)((nelem) * sizeof(type)))
 
 #define        R(type, nelem, ptr) \
        (type *)realloc((void *)ptr, (u_int)((nelem) * sizeof(type)))
 


@@ -668,14 +742,16 @@ fts_alloc(sp, name, len)
 
        /*
         * Variable sized structures; the name is the last element so
 
        /*
         * Variable sized structures; the name is the last element so

-        * allocate enough extra space after the structure to hold it.
+        * we allocate enough extra space after the structure to store
+        * it.

         */
        if (!(p = (FTSENT *)malloc((size_t)(sizeof(FTSENT) + len))))
                return(NULL);
        bcopy(name, p->fts_name, len + 1);
        p->fts_namelen = len;
        p->fts_path = sp->fts_path;
         */
        if (!(p = (FTSENT *)malloc((size_t)(sizeof(FTSENT) + len))))
                return(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_instr = FTS_NOINSTR;
+       p->fts_cderr = 0;

        p->fts_number = 0;
        p->fts_pointer = NULL;
        return(p);
        p->fts_number = 0;
        p->fts_pointer = NULL;
        return(p);


@@ -690,7 +766,7 @@ fts_lfree(head)
        /* Free a linked list of structures. */
        while (p = head) {
                head = head->fts_link;
        /* Free a linked list of structures. */
        while (p = head) {
                head = head->fts_link;

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

        }
 }
 
        }
 }
 


@@ -707,27 +783,5 @@ fts_path(sp, size)
        int size;
 {
        sp->fts_pathlen += size + 128;
        int size;
 {
        sp->fts_pathlen += size + 128;

-       return(sp->fts_path = R(char, sp->fts_pathlen, sp->fts_path)); }
-
-static FTSENT *
-fts_root(sp, name)
-       FTS *sp;
-       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(sp, name, cp - name));
+       return(sp->fts_path = R(char, sp->fts_pathlen, sp->fts_path));

 }
 }