Libc-1082.20.4.tar.gz

[apple/libc.git] / gen / fts.c

diff --git a/gen/fts.c b/gen/fts.c
index b8630c87f0c520d88f812a3c293e783059b2b33d..1bd602528ee165082458f862afce037e831a61f7 100644 (file)
--- a/gen/fts.c
+++ b/gen/fts.c
@@ -1,5 +1,5 @@
 /*
 /*

- * Copyright (c) 1999 Apple Computer, Inc. All rights reserved.
+ * Copyright (c) 1999, 2000, 2003, 2005, 2008, 2012 Apple Inc. All rights reserved.

  *
  * @APPLE_LICENSE_HEADER_START@
  * 
  *
  * @APPLE_LICENSE_HEADER_START@
  * 


@@ -64,6 +64,9 @@
 #include <stdlib.h>
 #include <string.h>
 #include <unistd.h>
 #include <stdlib.h>
 #include <string.h>
 #include <unistd.h>

+#ifdef __BLOCKS__
+#include <Block.h>
+#endif /* __BLOCKS__ */

 
 static FTSENT  *fts_alloc(FTS *, char *, int);
 static FTSENT  *fts_build(FTS *, int);
 
 static FTSENT  *fts_alloc(FTS *, char *, int);
 static FTSENT  *fts_build(FTS *, int);


@@ -88,31 +91,54 @@ static u_short       fts_stat(FTS *, FTSENT *, int);
 #define        BNAMES          2               /* fts_children, names only */
 #define        BREAD           3               /* fts_read */
 
 #define        BNAMES          2               /* fts_children, names only */
 #define        BREAD           3               /* fts_read */
 

-FTS *
-fts_open(argv, options, compar)
+/* 5653270
+ * For directories containing > 64k subdirectories (or HFS+ with > 64k files
+ * and subdirectories), struct stat's st_nlink (16 bits) will overflow.  This
+ * causes the case with FTS_NOSTAT and FTS_PHYSICAL set to prematurely stop
+ * recursing into subdirectories, because of an optimization that expects
+ * st_nlink to be the number of subdirectories (once that number has been
+ * encountered, no further calls to stat should be needed).
+ *
+ * However, on Mac OS X, another optimization largely nullifies the st_nlink
+ * optimization.  struct dirent contains d_type, which can distinguish
+ * directories from files without initially calling stat. So stat is only
+ * called on known directories, rather than on other files.  With this
+ * optimization, the difference in also using the st_nlink optimization is
+ * pretty minimal (tests show an improvement of a percent or two, probably
+ * due to additional if statement clauses that need to be evaluated). 
+ *
+ * So removing the st_nlink optimization code will fix the > 64k subdirectories
+ * problem.  And if we replace the multiple if clause logic with a single
+ * switch statement, we can recover the minimal performance lose.  We can
+ * go even further and for the case of FTS_NOSTAT and FTS_LOGICAL set, we
+ * can use d_type to also distinguish symbolic links, and so we only need to
+ * call stat on directories and symlinks, not on all files.  This provides
+ * a significant performance boost in that special case.
+ */
+/*
+ * The following macros defines values of the dostat variable, which is or-ed
+ * with the value of d_type, and the result used in a switch statement to
+ * determine whether to call stat or not.  (We order the macros to minimize
+ * the size of any jump table that the compiler may generate.)
+ */
+#define        F_SHIFT         4               /* shift to leave space for d_type */
+#define F_NOSTAT       (0 << F_SHIFT)  /* don't do any stat's */
+#define F_STATDIRSYM   (1 << F_SHIFT)  /* only stat directories and symlinks (and unknowns) */
+#define F_ALWAYSSTAT   (2 << F_SHIFT)  /* always stat */
+#define F_STATDIR      (3 << F_SHIFT)  /* only stat directories (and unknowns) */
+#define F_D_TYPE       (4 << F_SHIFT)  /* only stat directories but use d_type */
+#define F_D_TYPESYM    (5 << F_SHIFT)  /* only stat directories and symlinks but use d_type */
+
+static FTS *
+__fts_open(argv, sp)

        char * const *argv;
        char * const *argv;

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

        register FTS *sp;
        register FTS *sp;

+{

        register FTSENT *p, *root;
        register int nitems;
        register FTSENT *p, *root;
        register int nitems;

-       FTSENT *parent, *tmp;
+       FTSENT *parent, *tmp = NULL;

        int len;
 
        int len;
 

-       /* Options check. */
-       if (options & ~FTS_OPTIONMASK) {
-               errno = EINVAL;
-               return (NULL);
-       }
-
-       /* Allocate/initialize the stream */
-       if ((sp = malloc((u_int)sizeof(FTS))) == NULL)
-               return (NULL);
-       memset(sp, 0, sizeof(FTS));
-       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);
        /* Logical walks turn on NOCHDIR; symbolic links are too hard. */
        if (ISSET(FTS_LOGICAL))
                SET(FTS_NOCHDIR);


@@ -151,7 +177,7 @@ fts_open(argv, options, compar)
                 * 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.
                 */

-               if (compar) {
+               if (sp->fts_compar) {

                        p->fts_link = root;
                        root = p;
                } else {
                        p->fts_link = root;
                        root = p;
                } else {


@@ -164,7 +190,7 @@ fts_open(argv, options, compar)
                        }
                }
        }
                        }
                }
        }

-       if (compar && nitems > 1)
+       if (sp->fts_compar && nitems > 1)

                root = fts_sort(sp, root, nitems);
 
        /*
                root = fts_sort(sp, root, nitems);
 
        /*


@@ -196,6 +222,58 @@ mem1:      free(sp);
        return (NULL);
 }
 
        return (NULL);
 }
 

+FTS *
+fts_open(argv, options, compar)
+       char * const *argv;
+       int options;
+       int (*compar)();
+{
+       register FTS *sp;
+
+       /* Options check. */
+       if (options & ~FTS_OPTIONMASK) {
+               errno = EINVAL;
+               return (NULL);
+       }
+       if (options & FTS_NOSTAT_TYPE) options |= FTS_NOSTAT;
+
+       /* Allocate/initialize the stream */
+       if ((sp = malloc((u_int)sizeof(FTS))) == NULL)
+               return (NULL);
+       memset(sp, 0, sizeof(FTS));
+       sp->fts_compar = compar;
+       sp->fts_options = options;
+
+       return __fts_open(argv, sp);
+}
+
+#ifdef __BLOCKS__
+FTS *
+fts_open_b(argv, options, compar)
+       char * const *argv;
+       int options;
+       int (^compar)(const FTSENT **, const FTSENT **);
+{
+       register FTS *sp;
+
+       /* Options check. */
+       if (options & ~FTS_OPTIONMASK) {
+               errno = EINVAL;
+               return (NULL);
+       }
+       if (options & FTS_NOSTAT_TYPE) options |= FTS_NOSTAT;
+
+       /* Allocate/initialize the stream */
+       if ((sp = malloc((u_int)sizeof(FTS))) == NULL)
+               return (NULL);
+       memset(sp, 0, sizeof(FTS));
+       sp->fts_compar_b = (int (^)())Block_copy(compar);
+       sp->fts_options = options | FTS_BLOCK_COMPAR;
+
+       return __fts_open(argv, sp);
+}
+#endif /* __BLOCKS__ */
+

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


@@ -258,6 +336,12 @@ fts_close(sp)
             (void)close(sp->fts_rfd);
        }
 
             (void)close(sp->fts_rfd);
        }
 

+#ifdef __BLOCKS__
+       /* Free up any block pointer. */
+       if (ISSET(FTS_BLOCK_COMPAR) && sp->fts_compar_b != NULL)
+               Block_release(sp->fts_compar_b);
+#endif /* __BLOCKS__ */
+

        /* Free up the stream pointer. */
        free(sp);
 
        /* Free up the stream pointer. */
        free(sp);
 


@@ -312,12 +396,14 @@ fts_read(sp)
        if (instr == FTS_FOLLOW &&
            (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) {
                p->fts_info = fts_stat(sp, p, 1);
        if (instr == FTS_FOLLOW &&
            (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) {
                p->fts_info = fts_stat(sp, p, 1);

-               if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR))
+               if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {

                        if ((p->fts_symfd = open(".", O_RDONLY, 0)) < 0) {
                                p->fts_errno = errno;
                                p->fts_info = FTS_ERR;
                        if ((p->fts_symfd = open(".", O_RDONLY, 0)) < 0) {
                                p->fts_errno = errno;
                                p->fts_info = FTS_ERR;

-                       } else
+                       } else {

                                p->fts_flags |= FTS_SYMFOLLOW;
                                p->fts_flags |= FTS_SYMFOLLOW;

+                       }
+               }

                return (p);
        }
 
                return (p);
        }
 


@@ -325,7 +411,7 @@ fts_read(sp)
        if (p->fts_info == FTS_D) {
                /* If skipped or crossed mount point, do post-order visit. */
                if (instr == FTS_SKIP ||
        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_dev != sp->fts_dev) {
+                   (ISSET(FTS_XDEV) && p->fts_dev != sp->fts_dev)) {

                        if (p->fts_flags & FTS_SYMFOLLOW)
                                (void)close(p->fts_symfd);
                        if (sp->fts_child) {
                        if (p->fts_flags & FTS_SYMFOLLOW)
                                (void)close(p->fts_symfd);
                        if (sp->fts_child) {


@@ -334,7 +420,7 @@ fts_read(sp)
                        }
                        p->fts_info = FTS_DP;
                        return (p);
                        }
                        p->fts_info = FTS_DP;
                        return (p);

-               } 
+               }

 
                /* Rebuild if only read the names and now traversing. */
                if (sp->fts_child && sp->fts_options & FTS_NAMEONLY) {
 
                /* Rebuild if only read the names and now traversing. */
                if (sp->fts_child && sp->fts_options & FTS_NAMEONLY) {


@@ -375,9 +461,7 @@ fts_read(sp)
 
        /* Move to the next node on this level. */
 next:  tmp = p;
 
        /* Move to the next node on this level. */
 next:  tmp = p;

-       if (p = p->fts_link) {
-               free(tmp);
-
+       if ((p = p->fts_link)) {

                /*
                 * If reached the top, return to the original directory, and
                 * load the paths for the next root.
                /*
                 * If reached the top, return to the original directory, and
                 * load the paths for the next root.


@@ -388,6 +472,7 @@ next:       tmp = p;
                                return (NULL);
                        }
                        fts_load(sp, p);
                                return (NULL);
                        }
                        fts_load(sp, p);

+                       free(tmp);

                        return (sp->fts_cur = p);
                }
 
                        return (sp->fts_cur = p);
                }
 


@@ -396,20 +481,25 @@ next:     tmp = p;
                 * ignore.  If followed, get a file descriptor so we can
                 * get back if necessary.
                 */
                 * ignore.  If followed, get a file descriptor so we can
                 * get back if necessary.
                 */

-               if (p->fts_instr == FTS_SKIP)
+               if (p->fts_instr == FTS_SKIP) {
+                       free(tmp);

                        goto next;
                        goto next;

+               }

                if (p->fts_instr == FTS_FOLLOW) {
                        p->fts_info = fts_stat(sp, p, 1);
                if (p->fts_instr == FTS_FOLLOW) {
                        p->fts_info = fts_stat(sp, p, 1);

-                       if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR))
+                       if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {

                                if ((p->fts_symfd =
                                    open(".", O_RDONLY, 0)) < 0) {
                                        p->fts_errno = errno;
                                        p->fts_info = FTS_ERR;
                                if ((p->fts_symfd =
                                    open(".", O_RDONLY, 0)) < 0) {
                                        p->fts_errno = errno;
                                        p->fts_info = FTS_ERR;

-                               } else
+                               } else {

                                        p->fts_flags |= FTS_SYMFOLLOW;
                                        p->fts_flags |= FTS_SYMFOLLOW;

+                               }
+                       }

                        p->fts_instr = FTS_NOINSTR;
                }
 
                        p->fts_instr = FTS_NOINSTR;
                }
 

+               free(tmp);

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


@@ -418,13 +508,13 @@ name:             t = sp->fts_path + NAPPEND(p->fts_parent);
 
        /* Move up to the parent node. */
        p = tmp->fts_parent;
 
        /* 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
                 * can distinguish between error and EOF.
                 */
 
        if (p->fts_level == FTS_ROOTPARENTLEVEL) {
                /*
                 * Done; free everything up and set errno to 0 so the user
                 * can distinguish between error and EOF.
                 */

+               free(tmp);

                free(p);
                errno = 0;
                return (sp->fts_cur = NULL);
                free(p);
                errno = 0;
                return (sp->fts_cur = NULL);


@@ -458,6 +548,7 @@ name:               t = sp->fts_path + NAPPEND(p->fts_parent);
                        return (NULL);
                }
        }
                        return (NULL);
                }
        }

+       free(tmp);

        p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;
        return (sp->fts_cur = p);
 }
        p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;
        return (sp->fts_cur = p);
 }


@@ -558,13 +649,9 @@ fts_children(sp, instr)
  * and fts_read.  There are lots of special cases.
  *
  * The real slowdown in walking the tree is the stat calls.  If FTS_NOSTAT is
  * 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 can do things quickly.  First, if it's a 4.4BSD file system, the type
- * of the file is in the directory entry.  Otherwise, we assume that the number
- * of subdirectories in a node is equal to the number of links to the parent.
- * The former skips all stat calls.  The latter skips stat calls in any leaf
- * directories and for any files after the subdirectories in the directory have
- * been found, cutting the stat calls by about 2/3.
+ * set, we can use d_type to determine if the entry is a directory (or for
+ * logical walks, a directory or symlink) and not call stat for other file
+ * types.  This cuts the number of stat calls significantly.

  */
 static FTSENT *
 fts_build(sp, type)
  */
 static FTSENT *
 fts_build(sp, type)


@@ -577,8 +664,8 @@ fts_build(sp, type)
        FTSENT *cur, *tail;
        DIR *dirp;
        void *adjaddr;
        FTSENT *cur, *tail;
        DIR *dirp;
        void *adjaddr;

-       int cderrno, descend, len, level, maxlen, nlinks, oflag, saved_errno;
-       char *cp;
+       int cderrno, descend, len, level, maxlen, dostat, oflag, saved_errno;
+       char *cp = NULL;

 
        /* Set current node pointer. */
        cur = sp->fts_cur;
 
        /* Set current node pointer. */
        cur = sp->fts_cur;


@@ -603,20 +690,17 @@ fts_build(sp, type)
                return (NULL);
        }
 
                return (NULL);
        }
 

-       /*
-        * 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.
-        */

        if (type == BNAMES)
        if (type == BNAMES)

-               nlinks = 0;
-       else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL))
-               nlinks = cur->fts_nlink - (ISSET(FTS_SEEDOT) ? 0 : 2);
+               dostat = F_NOSTAT;
+       else if (ISSET(FTS_NOSTAT_TYPE))
+               dostat = ISSET(FTS_PHYSICAL) ? F_D_TYPE : F_D_TYPESYM;
+       else if (ISSET(FTS_NOSTAT))
+               dostat = ISSET(FTS_PHYSICAL) ? F_STATDIR : F_STATDIRSYM;

        else
        else

-               nlinks = -1;
+               dostat = F_ALWAYSSTAT;

 
 #ifdef notdef
 
 #ifdef notdef

-       (void)printf("nlinks == %d (cur: %d)\n", nlinks, cur->fts_nlink);
+       (void)printf("dostat == %d\n", dostat);

        (void)printf("NOSTAT %d PHYSICAL %d SEEDOT %d\n",
            ISSET(FTS_NOSTAT), ISSET(FTS_PHYSICAL), ISSET(FTS_SEEDOT));
 #endif
        (void)printf("NOSTAT %d PHYSICAL %d SEEDOT %d\n",
            ISSET(FTS_NOSTAT), ISSET(FTS_PHYSICAL), ISSET(FTS_SEEDOT));
 #endif


@@ -636,9 +720,9 @@ fts_build(sp, type)
         * checking FTS_NS on the returned nodes.
         */
        cderrno = 0;
         * checking FTS_NS on the returned nodes.
         */
        cderrno = 0;

-       if (nlinks || type == BREAD)
+       if (dostat || type == BREAD)

                if (FCHDIR(sp, dirfd(dirp))) {
                if (FCHDIR(sp, dirfd(dirp))) {

-                       if (nlinks && type == BREAD)
+                       if (dostat && type == BREAD)

                                cur->fts_errno = errno;
                        cur->fts_flags |= FTS_DONTCHDIR;
                        descend = 0;
                                cur->fts_errno = errno;
                        cur->fts_flags |= FTS_DONTCHDIR;
                        descend = 0;


@@ -658,24 +742,25 @@ fts_build(sp, type)
         * If not changing directories set a pointer so that can just append
         * each new name into the path.
         */
         * If not changing directories set a pointer so that 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++ = '/';
        }
        len = NAPPEND(cur);
        if (ISSET(FTS_NOCHDIR)) {
                cp = sp->fts_path + len;
                *cp++ = '/';
        }

+       len++;
+       maxlen = sp->fts_pathlen - len;

 
        level = cur->fts_level + 1;
 
        /* Read the directory, attaching each entry to the `link' pointer. */
        adjaddr = NULL;
 
        level = cur->fts_level + 1;
 
        /* Read the directory, attaching each entry to the `link' pointer. */
        adjaddr = NULL;

-       for (head = tail = NULL, nitems = 0; dp = readdir(dirp);) {
+       for (head = tail = NULL, nitems = 0; (dp = readdir(dirp)) ; ) {

                if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))
                        continue;
 
                if ((p = fts_alloc(sp, dp->d_name, (int)dp->d_namlen)) == NULL)
                        goto mem1;
                if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))
                        continue;
 
                if ((p = fts_alloc(sp, dp->d_name, (int)dp->d_namlen)) == NULL)
                        goto mem1;

-               if (dp->d_namlen > maxlen) {
+               if (dp->d_namlen >= maxlen) {   /* include space for NUL */

                        if (fts_palloc(sp, (size_t)dp->d_namlen)) {
                                /*
                                 * No more memory for path or structures.  Save
                        if (fts_palloc(sp, (size_t)dp->d_namlen)) {
                                /*
                                 * No more memory for path or structures.  Save


@@ -687,18 +772,18 @@ mem1:                             saved_errno = errno;
                                        free(p);
                                fts_lfree(head);
                                (void)closedir(dirp);
                                        free(p);
                                fts_lfree(head);
                                (void)closedir(dirp);

-                               errno = saved_errno;

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

+                               errno = saved_errno;

                                return (NULL);
                        }
                        adjaddr = sp->fts_path;
                        maxlen = sp->fts_pathlen - sp->fts_cur->fts_pathlen - 1;
                }
 
                                return (NULL);
                        }
                        adjaddr = sp->fts_path;
                        maxlen = sp->fts_pathlen - sp->fts_cur->fts_pathlen - 1;
                }
 

-               p->fts_pathlen = len + dp->d_namlen + 1;
-               p->fts_parent = sp->fts_cur;

                p->fts_level = level;
                p->fts_level = level;

+               p->fts_parent = sp->fts_cur;
+               p->fts_pathlen = len + dp->d_namlen;

 
 #ifdef FTS_WHITEOUT
                if (dp->d_type == DT_WHT)
 
 #ifdef FTS_WHITEOUT
                if (dp->d_type == DT_WHT)


@@ -706,35 +791,76 @@ mem1:                             saved_errno = errno;
 #endif
 
                if (cderrno) {
 #endif
 
                if (cderrno) {

-                       if (nlinks) {
+                       if (dostat) {

                                p->fts_info = FTS_NS;
                                p->fts_errno = cderrno;
                        } else
                                p->fts_info = FTS_NSOK;
                        p->fts_accpath = cur->fts_accpath;
                                p->fts_info = FTS_NS;
                                p->fts_errno = cderrno;
                        } else
                                p->fts_info = FTS_NSOK;
                        p->fts_accpath = cur->fts_accpath;

-               } else if (nlinks == 0
-#ifdef DT_DIR
-                   || nlinks > 0 && 
-                   dp->d_type != DT_DIR && dp->d_type != DT_UNKNOWN
-#endif
-                   ) {
-                       p->fts_accpath =
-                           ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name;
-                       p->fts_info = FTS_NSOK;

                } else {
                } else {

-                       /* Build a file name for fts_stat to stat. */
-                       if (ISSET(FTS_NOCHDIR)) {
-                               p->fts_accpath = p->fts_path;
-                               memmove(cp, p->fts_name, p->fts_namelen + 1);
-                       } else
-                               p->fts_accpath = p->fts_name;
-                       /* Stat it. */
-                       p->fts_info = fts_stat(sp, p, 0);
-
-                       /* Decrement link count if applicable. */
-                       if (nlinks > 0 && (p->fts_info == FTS_D ||
-                           p->fts_info == FTS_DC || p->fts_info == FTS_DOT))
-                               --nlinks;
+                       /*
+                        * We need to know all file types values that d_type may
+                        * be set to.  So if that changes, the following needs
+                        * to be modified appropriately.
+                        */
+                       switch(dostat | dp->d_type) {
+                       case (F_STATDIR | DT_UNKNOWN):
+                       case (F_STATDIR | DT_DIR):
+                       case (F_STATDIRSYM | DT_UNKNOWN):
+                       case (F_STATDIRSYM | DT_DIR):
+                       case (F_STATDIRSYM | DT_LNK):
+                       case (F_ALWAYSSTAT | DT_UNKNOWN):
+                       case (F_ALWAYSSTAT | DT_FIFO):
+                       case (F_ALWAYSSTAT | DT_CHR):
+                       case (F_ALWAYSSTAT | DT_DIR):
+                       case (F_ALWAYSSTAT | DT_BLK):
+                       case (F_ALWAYSSTAT | DT_REG):
+                       case (F_ALWAYSSTAT | DT_LNK):
+                       case (F_ALWAYSSTAT | DT_SOCK):
+                       case (F_ALWAYSSTAT | DT_WHT):
+                       case (F_D_TYPE | DT_UNKNOWN):
+                       case (F_D_TYPE | DT_DIR):
+                       case (F_D_TYPESYM | DT_UNKNOWN):
+                       case (F_D_TYPESYM | DT_DIR):
+                       case (F_D_TYPESYM | DT_LNK):
+                               /* Build a file name for fts_stat to stat. */
+                               if (ISSET(FTS_NOCHDIR)) {
+                                       p->fts_accpath = p->fts_path;
+                                       memmove(cp, p->fts_name, p->fts_namelen + 1);
+                               } else
+                                       p->fts_accpath = p->fts_name;
+                               /* Stat it. */
+                               p->fts_info = fts_stat(sp, p, 0);
+                               break;
+                       case (F_D_TYPE | DT_FIFO):
+                       case (F_D_TYPE | DT_CHR):
+                       case (F_D_TYPE | DT_BLK):
+                       case (F_D_TYPE | DT_SOCK):
+                       case (F_D_TYPESYM | DT_FIFO):
+                       case (F_D_TYPESYM | DT_CHR):
+                       case (F_D_TYPESYM | DT_BLK):
+                       case (F_D_TYPESYM | DT_SOCK):
+                               p->fts_info = FTS_DEFAULT;
+                               goto common_no_stat;
+                       case (F_D_TYPE | DT_REG):
+                       case (F_D_TYPESYM | DT_REG):
+                               p->fts_info = FTS_F;
+                               goto common_no_stat;
+                       case (F_D_TYPE | DT_LNK):
+                               p->fts_info = FTS_SL;
+                               goto common_no_stat;
+                       case (F_D_TYPE | DT_WHT):
+                       case (F_D_TYPESYM | DT_WHT):
+                               p->fts_info = FTS_W;
+                               goto common_no_stat;
+                       default:
+                               /* No stat necessary */
+                               p->fts_info = FTS_NSOK;
+common_no_stat:
+                               p->fts_accpath =
+                                   ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name;
+                               break;
+                       }

                }
 
                /* We walk in directory order so "ls -f" doesn't get upset. */
                }
 
                /* We walk in directory order so "ls -f" doesn't get upset. */


@@ -914,7 +1040,12 @@ fts_sort(sp, head, nitems)
        }
        for (ap = sp->fts_array, p = head; p; p = p->fts_link)
                *ap++ = p;
        }
        for (ap = sp->fts_array, p = head; p; p = p->fts_link)
                *ap++ = p;

-       qsort((void *)sp->fts_array, nitems, sizeof(FTSENT *), sp->fts_compar);
+#ifdef __BLOCKS__
+       if (ISSET(FTS_BLOCK_COMPAR))
+               qsort_b((void *)sp->fts_array, nitems, sizeof(FTSENT *), (int (^)(const void *, const void *))sp->fts_compar_b);
+       else
+#endif /* __BLOCKS__ */
+               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;
        for (head = *(ap = sp->fts_array); --nitems; ++ap)
                ap[0]->fts_link = ap[1];
        ap[0]->fts_link = NULL;


@@ -966,7 +1097,7 @@ fts_lfree(head)
        register FTSENT *p;
 
        /* Free a linked list of structures. */
        register FTSENT *p;
 
        /* Free a linked list of structures. */

-       while (p = head) {
+       while ((p = head)) {

                head = head->fts_link;
                free(p);
        }
                head = head->fts_link;
                free(p);
        }


@@ -976,7 +1107,7 @@ fts_lfree(head)
  * Allow essentially unlimited paths; find, rm, ls should all work on any tree.
  * Most systems will allow creation of paths much longer than MAXPATHLEN, even
  * though the kernel won't resolve them.  Add the size (not just what's needed)
  * Allow essentially unlimited paths; find, rm, ls should all work on any tree.
  * Most systems will allow creation of paths much longer than MAXPATHLEN, even
  * though the kernel won't resolve them.  Add the size (not just what's needed)

- * plus 256 bytes so don't realloc the path 2 bytes at a time. 
+ * plus 256 bytes so don't realloc the path 2 bytes at a time.

  */
 static int
 fts_palloc(sp, more)
  */
 static int
 fts_palloc(sp, more)


@@ -993,17 +1124,17 @@ fts_palloc(sp, more)
  * already returned.
  */
 static void
  * already returned.
  */
 static void

-fts_padjust(sp, addr)
-       FTS *sp;
-       void *addr;
+fts_padjust(FTS *sp, void *addr)

 {
        FTSENT *p;
 
 {
        FTSENT *p;
 

-#define        ADJUST(p) {                                                     \
-       (p)->fts_accpath =                                              \
-           (char *)addr + ((p)->fts_accpath - (p)->fts_path);          \
+#define        ADJUST(p) do {                                                  \
+       if ((p)->fts_accpath != (p)->fts_name) {                        \
+               (p)->fts_accpath =                                      \
+                   (char *)addr + ((p)->fts_accpath - (p)->fts_path);  \
+       }                                                               \

        (p)->fts_path = addr;                                           \
        (p)->fts_path = addr;                                           \

-}
+} while (0)

        /* Adjust the current set of children. */
        for (p = sp->fts_child; p; p = p->fts_link)
                ADJUST(p);
        /* Adjust the current set of children. */
        for (p = sp->fts_child; p; p = p->fts_link)
                ADJUST(p);


@@ -1024,5 +1155,5 @@ fts_maxarglen(argv)
        for (max = 0; *argv; ++argv)
                if ((len = strlen(*argv)) > max)
                        max = len;
        for (max = 0; *argv; ++argv)
                if ((len = strlen(*argv)) > max)
                        max = len;

-       return (max);
+       return (max + 1);

 }
 }