Back to index

glibc  2.9
fts.c
Go to the documentation of this file.
00001 /*-
00002  * Copyright (c) 1990, 1993, 1994
00003  *     The Regents of the University of California.  All rights reserved.
00004  *
00005  * Redistribution and use in source and binary forms, with or without
00006  * modification, are permitted provided that the following conditions
00007  * are met:
00008  * 1. Redistributions of source code must retain the above copyright
00009  *    notice, this list of conditions and the following disclaimer.
00010  * 2. Redistributions in binary form must reproduce the above copyright
00011  *    notice, this list of conditions and the following disclaimer in the
00012  *    documentation and/or other materials provided with the distribution.
00013  * 4. Neither the name of the University nor the names of its contributors
00014  *    may be used to endorse or promote products derived from this software
00015  *    without specific prior written permission.
00016  *
00017  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
00018  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00019  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
00020  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
00021  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
00022  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
00023  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
00024  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
00025  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
00026  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
00027  * SUCH DAMAGE.
00028  */
00029 
00030 #if defined(LIBC_SCCS) && !defined(lint)
00031 static char sccsid[] = "@(#)fts.c  8.6 (Berkeley) 8/14/94";
00032 #endif /* LIBC_SCCS and not lint */
00033 
00034 #include <sys/param.h>
00035 #include <include/sys/stat.h>
00036 #include <fcntl.h>
00037 #include <dirent.h>
00038 #include <errno.h>
00039 #include <fts.h>
00040 #include <stdlib.h>
00041 #include <string.h>
00042 #include <unistd.h>
00043 
00044 
00045 /* Largest alignment size needed, minus one.
00046    Usually long double is the worst case.  */
00047 #ifndef ALIGNBYTES
00048 #define ALIGNBYTES   (__alignof__ (long double) - 1)
00049 #endif
00050 /* Align P to that size.  */
00051 #ifndef ALIGN
00052 #define       ALIGN(p)      (((unsigned long int) (p) + ALIGNBYTES) & ~ALIGNBYTES)
00053 #endif
00054 
00055 
00056 static FTSENT *fts_alloc (FTS *, const char *, size_t) internal_function;
00057 static FTSENT *fts_build (FTS *, int) internal_function;
00058 static void    fts_lfree (FTSENT *) internal_function;
00059 static void    fts_load (FTS *, FTSENT *) internal_function;
00060 static size_t  fts_maxarglen (char * const *) internal_function;
00061 static void    fts_padjust (FTS *, FTSENT *) internal_function;
00062 static int     fts_palloc (FTS *, size_t) internal_function;
00063 static FTSENT *fts_sort (FTS *, FTSENT *, int) internal_function;
00064 static u_short        fts_stat (FTS *, FTSENT *, int) internal_function;
00065 static int      fts_safe_changedir (FTS *, FTSENT *, int, const char *)
00066      internal_function;
00067 
00068 #ifndef MAX
00069 #define MAX(a, b)    ({ __typeof__ (a) _a = (a); \
00070                         __typeof__ (b) _b = (b); \
00071                         _a > _b ? _a : _b; })
00072 #endif
00073 
00074 #define       ISDOT(a)      (a[0] == '.' && (!a[1] || (a[1] == '.' && !a[2])))
00075 
00076 #define CLR(opt)     (sp->fts_options &= ~(opt))
00077 #define       ISSET(opt)    (sp->fts_options & (opt))
00078 #define       SET(opt)      (sp->fts_options |= (opt))
00079 
00080 #define       FCHDIR(sp, fd)       (!ISSET(FTS_NOCHDIR) && __fchdir(fd))
00081 
00082 /* fts_build flags */
00083 #define       BCHILD        1             /* fts_children */
00084 #define       BNAMES        2             /* fts_children, names only */
00085 #define       BREAD         3             /* fts_read */
00086 
00087 FTS *
00088 fts_open(argv, options, compar)
00089        char * const *argv;
00090        register int options;
00091        int (*compar) (const FTSENT **, const FTSENT **);
00092 {
00093        register FTS *sp;
00094        register FTSENT *p, *root;
00095        register int nitems;
00096        FTSENT *parent = NULL;
00097        FTSENT *tmp;
00098 
00099        /* Options check. */
00100        if (options & ~FTS_OPTIONMASK) {
00101               __set_errno (EINVAL);
00102               return (NULL);
00103        }
00104 
00105        /* Allocate/initialize the stream */
00106        if ((sp = malloc((u_int)sizeof(FTS))) == NULL)
00107               return (NULL);
00108        memset(sp, 0, sizeof(FTS));
00109        sp->fts_compar = (int (*) (const void *, const void *)) compar;
00110        sp->fts_options = options;
00111 
00112        /* Logical walks turn on NOCHDIR; symbolic links are too hard. */
00113        if (ISSET(FTS_LOGICAL))
00114               SET(FTS_NOCHDIR);
00115 
00116        /*
00117         * Start out with 1K of path space, and enough, in any case,
00118         * to hold the user's paths.
00119         */
00120 #ifndef MAXPATHLEN
00121 #define MAXPATHLEN 1024
00122 #endif
00123        size_t maxarglen = fts_maxarglen(argv);
00124        if (fts_palloc(sp, MAX(maxarglen, MAXPATHLEN)))
00125               goto mem1;
00126 
00127        /* Allocate/initialize root's parent. */
00128        if (*argv != NULL) {
00129               if ((parent = fts_alloc(sp, "", 0)) == NULL)
00130                      goto mem2;
00131               parent->fts_level = FTS_ROOTPARENTLEVEL;
00132          }
00133 
00134        /* Allocate/initialize root(s). */
00135        for (root = NULL, nitems = 0; *argv != NULL; ++argv, ++nitems) {
00136               /* Don't allow zero-length paths. */
00137               size_t len = strlen(*argv);
00138               if (len == 0) {
00139                      __set_errno (ENOENT);
00140                      goto mem3;
00141               }
00142 
00143               p = fts_alloc(sp, *argv, len);
00144               p->fts_level = FTS_ROOTLEVEL;
00145               p->fts_parent = parent;
00146               p->fts_accpath = p->fts_name;
00147               p->fts_info = fts_stat(sp, p, ISSET(FTS_COMFOLLOW));
00148 
00149               /* Command-line "." and ".." are real directories. */
00150               if (p->fts_info == FTS_DOT)
00151                      p->fts_info = FTS_D;
00152 
00153               /*
00154                * If comparison routine supplied, traverse in sorted
00155                * order; otherwise traverse in the order specified.
00156                */
00157               if (compar) {
00158                      p->fts_link = root;
00159                      root = p;
00160               } else {
00161                      p->fts_link = NULL;
00162                      if (root == NULL)
00163                             tmp = root = p;
00164                      else {
00165                             tmp->fts_link = p;
00166                             tmp = p;
00167                      }
00168               }
00169        }
00170        if (compar && nitems > 1)
00171               root = fts_sort(sp, root, nitems);
00172 
00173        /*
00174         * Allocate a dummy pointer and make fts_read think that we've just
00175         * finished the node before the root(s); set p->fts_info to FTS_INIT
00176         * so that everything about the "current" node is ignored.
00177         */
00178        if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL)
00179               goto mem3;
00180        sp->fts_cur->fts_link = root;
00181        sp->fts_cur->fts_info = FTS_INIT;
00182 
00183        /*
00184         * If using chdir(2), grab a file descriptor pointing to dot to ensure
00185         * that we can get back here; this could be avoided for some paths,
00186         * but almost certainly not worth the effort.  Slashes, symbolic links,
00187         * and ".." are all fairly nasty problems.  Note, if we can't get the
00188         * descriptor we run anyway, just more slowly.
00189         */
00190        if (!ISSET(FTS_NOCHDIR)
00191            && (sp->fts_rfd = __open(".", O_RDONLY, 0)) < 0)
00192               SET(FTS_NOCHDIR);
00193 
00194        return (sp);
00195 
00196 mem3:  fts_lfree(root);
00197        free(parent);
00198 mem2:  free(sp->fts_path);
00199 mem1:  free(sp);
00200        return (NULL);
00201 }
00202 
00203 static void
00204 internal_function
00205 fts_load(sp, p)
00206        FTS *sp;
00207        register FTSENT *p;
00208 {
00209        register int len;
00210        register char *cp;
00211 
00212        /*
00213         * Load the stream structure for the next traversal.  Since we don't
00214         * actually enter the directory until after the preorder visit, set
00215         * the fts_accpath field specially so the chdir gets done to the right
00216         * place and the user can access the first node.  From fts_open it's
00217         * known that the path will fit.
00218         */
00219        len = p->fts_pathlen = p->fts_namelen;
00220        memmove(sp->fts_path, p->fts_name, len + 1);
00221        if ((cp = strrchr(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) {
00222               len = strlen(++cp);
00223               memmove(p->fts_name, cp, len + 1);
00224               p->fts_namelen = len;
00225        }
00226        p->fts_accpath = p->fts_path = sp->fts_path;
00227        sp->fts_dev = p->fts_dev;
00228 }
00229 
00230 int
00231 fts_close(sp)
00232        FTS *sp;
00233 {
00234        register FTSENT *freep, *p;
00235        int saved_errno;
00236 
00237        /*
00238         * This still works if we haven't read anything -- the dummy structure
00239         * points to the root list, so we step through to the end of the root
00240         * list which has a valid parent pointer.
00241         */
00242        if (sp->fts_cur) {
00243               for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {
00244                      freep = p;
00245                      p = p->fts_link != NULL ? p->fts_link : p->fts_parent;
00246                      free(freep);
00247               }
00248               free(p);
00249        }
00250 
00251        /* Free up child linked list, sort array, path buffer. */
00252        if (sp->fts_child)
00253               fts_lfree(sp->fts_child);
00254        free(sp->fts_array);
00255        free(sp->fts_path);
00256 
00257        /* Return to original directory, save errno if necessary. */
00258        if (!ISSET(FTS_NOCHDIR)) {
00259               saved_errno = __fchdir(sp->fts_rfd) ? errno : 0;
00260               (void)__close(sp->fts_rfd);
00261 
00262               /* Set errno and return. */
00263               if (saved_errno != 0) {
00264                      /* Free up the stream pointer. */
00265                      free(sp);
00266                      __set_errno (saved_errno);
00267                      return (-1);
00268               }
00269        }
00270 
00271        /* Free up the stream pointer. */
00272        free(sp);
00273        return (0);
00274 }
00275 
00276 /*
00277  * Special case of "/" at the end of the path so that slashes aren't
00278  * appended which would cause paths to be written as "....//foo".
00279  */
00280 #define       NAPPEND(p)                                              \
00281        (p->fts_path[p->fts_pathlen - 1] == '/'                        \
00282            ? p->fts_pathlen - 1 : p->fts_pathlen)
00283 
00284 FTSENT *
00285 fts_read(sp)
00286        register FTS *sp;
00287 {
00288        register FTSENT *p, *tmp;
00289        register int instr;
00290        register char *t;
00291        int saved_errno;
00292 
00293        /* If finished or unrecoverable error, return NULL. */
00294        if (sp->fts_cur == NULL || ISSET(FTS_STOP))
00295               return (NULL);
00296 
00297        /* Set current node pointer. */
00298        p = sp->fts_cur;
00299 
00300        /* Save and zero out user instructions. */
00301        instr = p->fts_instr;
00302        p->fts_instr = FTS_NOINSTR;
00303 
00304        /* Any type of file may be re-visited; re-stat and re-turn. */
00305        if (instr == FTS_AGAIN) {
00306               p->fts_info = fts_stat(sp, p, 0);
00307               return (p);
00308        }
00309 
00310        /*
00311         * Following a symlink -- SLNONE test allows application to see
00312         * SLNONE and recover.  If indirecting through a symlink, have
00313         * keep a pointer to current location.  If unable to get that
00314         * pointer, follow fails.
00315         */
00316        if (instr == FTS_FOLLOW &&
00317            (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) {
00318               p->fts_info = fts_stat(sp, p, 1);
00319               if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
00320                      if ((p->fts_symfd = __open(".", O_RDONLY, 0)) < 0) {
00321                             p->fts_errno = errno;
00322                             p->fts_info = FTS_ERR;
00323                      } else
00324                             p->fts_flags |= FTS_SYMFOLLOW;
00325               }
00326               return (p);
00327        }
00328 
00329        /* Directory in pre-order. */
00330        if (p->fts_info == FTS_D) {
00331               /* If skipped or crossed mount point, do post-order visit. */
00332               if (instr == FTS_SKIP ||
00333                   (ISSET(FTS_XDEV) && p->fts_dev != sp->fts_dev)) {
00334                      if (p->fts_flags & FTS_SYMFOLLOW)
00335                             (void)__close(p->fts_symfd);
00336                      if (sp->fts_child) {
00337                             fts_lfree(sp->fts_child);
00338                             sp->fts_child = NULL;
00339                      }
00340                      p->fts_info = FTS_DP;
00341                      return (p);
00342               }
00343 
00344               /* Rebuild if only read the names and now traversing. */
00345               if (sp->fts_child != NULL && ISSET(FTS_NAMEONLY)) {
00346                      CLR(FTS_NAMEONLY);
00347                      fts_lfree(sp->fts_child);
00348                      sp->fts_child = NULL;
00349               }
00350 
00351               /*
00352                * Cd to the subdirectory.
00353                *
00354                * If have already read and now fail to chdir, whack the list
00355                * to make the names come out right, and set the parent errno
00356                * so the application will eventually get an error condition.
00357                * Set the FTS_DONTCHDIR flag so that when we logically change
00358                * directories back to the parent we don't do a chdir.
00359                *
00360                * If haven't read do so.  If the read fails, fts_build sets
00361                * FTS_STOP or the fts_info field of the node.
00362                */
00363               if (sp->fts_child != NULL) {
00364                      if (fts_safe_changedir(sp, p, -1, p->fts_accpath)) {
00365                             p->fts_errno = errno;
00366                             p->fts_flags |= FTS_DONTCHDIR;
00367                             for (p = sp->fts_child; p != NULL;
00368                                  p = p->fts_link)
00369                                    p->fts_accpath =
00370                                        p->fts_parent->fts_accpath;
00371                      }
00372               } else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) {
00373                      if (ISSET(FTS_STOP))
00374                             return (NULL);
00375                      return (p);
00376               }
00377               p = sp->fts_child;
00378               sp->fts_child = NULL;
00379               sp->fts_cur = p;
00380               goto name;
00381        }
00382 
00383        /* Move to the next node on this level. */
00384 next:  tmp = p;
00385        if ((p = p->fts_link) != NULL) {
00386               sp->fts_cur = p;
00387               free(tmp);
00388 
00389               /*
00390                * If reached the top, return to the original directory (or
00391                * the root of the tree), and load the paths for the next root.
00392                */
00393               if (p->fts_level == FTS_ROOTLEVEL) {
00394                      if (FCHDIR(sp, sp->fts_rfd)) {
00395                             SET(FTS_STOP);
00396                             return (NULL);
00397                      }
00398                      fts_load(sp, p);
00399                      return p;
00400               }
00401 
00402               /*
00403                * User may have called fts_set on the node.  If skipped,
00404                * ignore.  If followed, get a file descriptor so we can
00405                * get back if necessary.
00406                */
00407               if (p->fts_instr == FTS_SKIP)
00408                      goto next;
00409               if (p->fts_instr == FTS_FOLLOW) {
00410                      p->fts_info = fts_stat(sp, p, 1);
00411                      if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR)) {
00412                             if ((p->fts_symfd =
00413                                 __open(".", O_RDONLY, 0)) < 0) {
00414                                    p->fts_errno = errno;
00415                                    p->fts_info = FTS_ERR;
00416                             } else
00417                                    p->fts_flags |= FTS_SYMFOLLOW;
00418                      }
00419                      p->fts_instr = FTS_NOINSTR;
00420               }
00421 
00422 name:         t = sp->fts_path + NAPPEND(p->fts_parent);
00423               *t++ = '/';
00424               memmove(t, p->fts_name, p->fts_namelen + 1);
00425               return p;
00426        }
00427 
00428        /* Move up to the parent node. */
00429        p = tmp->fts_parent;
00430        sp->fts_cur = p;
00431        free(tmp);
00432 
00433        if (p->fts_level == FTS_ROOTPARENTLEVEL) {
00434               /*
00435                * Done; free everything up and set errno to 0 so the user
00436                * can distinguish between error and EOF.
00437                */
00438               free(p);
00439               __set_errno (0);
00440               return (sp->fts_cur = NULL);
00441        }
00442 
00443        /* NUL terminate the pathname. */
00444        sp->fts_path[p->fts_pathlen] = '\0';
00445 
00446        /*
00447         * Return to the parent directory.  If at a root node or came through
00448         * a symlink, go back through the file descriptor.  Otherwise, cd up
00449         * one directory.
00450         */
00451        if (p->fts_level == FTS_ROOTLEVEL) {
00452               if (FCHDIR(sp, sp->fts_rfd)) {
00453                      SET(FTS_STOP);
00454                      return (NULL);
00455               }
00456        } else if (p->fts_flags & FTS_SYMFOLLOW) {
00457               if (FCHDIR(sp, p->fts_symfd)) {
00458                      saved_errno = errno;
00459                      (void)__close(p->fts_symfd);
00460                      __set_errno (saved_errno);
00461                      SET(FTS_STOP);
00462                      return (NULL);
00463               }
00464               (void)__close(p->fts_symfd);
00465        } else if (!(p->fts_flags & FTS_DONTCHDIR) &&
00466                  fts_safe_changedir(sp, p->fts_parent, -1, "..")) {
00467               SET(FTS_STOP);
00468               return (NULL);
00469        }
00470        p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;
00471        return p;
00472 }
00473 
00474 /*
00475  * Fts_set takes the stream as an argument although it's not used in this
00476  * implementation; it would be necessary if anyone wanted to add global
00477  * semantics to fts using fts_set.  An error return is allowed for similar
00478  * reasons.
00479  */
00480 /* ARGSUSED */
00481 int
00482 fts_set(sp, p, instr)
00483        FTS *sp;
00484        FTSENT *p;
00485        int instr;
00486 {
00487        if (instr != 0 && instr != FTS_AGAIN && instr != FTS_FOLLOW &&
00488            instr != FTS_NOINSTR && instr != FTS_SKIP) {
00489               __set_errno (EINVAL);
00490               return (1);
00491        }
00492        p->fts_instr = instr;
00493        return (0);
00494 }
00495 
00496 FTSENT *
00497 fts_children(sp, instr)
00498        register FTS *sp;
00499        int instr;
00500 {
00501        register FTSENT *p;
00502        int fd;
00503 
00504        if (instr != 0 && instr != FTS_NAMEONLY) {
00505               __set_errno (EINVAL);
00506               return (NULL);
00507        }
00508 
00509        /* Set current node pointer. */
00510        p = sp->fts_cur;
00511 
00512        /*
00513         * Errno set to 0 so user can distinguish empty directory from
00514         * an error.
00515         */
00516        __set_errno (0);
00517 
00518        /* Fatal errors stop here. */
00519        if (ISSET(FTS_STOP))
00520               return (NULL);
00521 
00522        /* Return logical hierarchy of user's arguments. */
00523        if (p->fts_info == FTS_INIT)
00524               return (p->fts_link);
00525 
00526        /*
00527         * If not a directory being visited in pre-order, stop here.  Could
00528         * allow FTS_DNR, assuming the user has fixed the problem, but the
00529         * same effect is available with FTS_AGAIN.
00530         */
00531        if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */)
00532               return (NULL);
00533 
00534        /* Free up any previous child list. */
00535        if (sp->fts_child != NULL)
00536               fts_lfree(sp->fts_child);
00537 
00538        if (instr == FTS_NAMEONLY) {
00539               SET(FTS_NAMEONLY);
00540               instr = BNAMES;
00541        } else
00542               instr = BCHILD;
00543 
00544        /*
00545         * If using chdir on a relative path and called BEFORE fts_read does
00546         * its chdir to the root of a traversal, we can lose -- we need to
00547         * chdir into the subdirectory, and we don't know where the current
00548         * directory is, so we can't get back so that the upcoming chdir by
00549         * fts_read will work.
00550         */
00551        if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' ||
00552            ISSET(FTS_NOCHDIR))
00553               return (sp->fts_child = fts_build(sp, instr));
00554 
00555        if ((fd = __open(".", O_RDONLY, 0)) < 0)
00556               return (NULL);
00557        sp->fts_child = fts_build(sp, instr);
00558        if (__fchdir(fd))
00559               return (NULL);
00560        (void)__close(fd);
00561        return (sp->fts_child);
00562 }
00563 
00564 /*
00565  * This is the tricky part -- do not casually change *anything* in here.  The
00566  * idea is to build the linked list of entries that are used by fts_children
00567  * and fts_read.  There are lots of special cases.
00568  *
00569  * The real slowdown in walking the tree is the stat calls.  If FTS_NOSTAT is
00570  * set and it's a physical walk (so that symbolic links can't be directories),
00571  * we can do things quickly.  First, if it's a 4.4BSD file system, the type
00572  * of the file is in the directory entry.  Otherwise, we assume that the number
00573  * of subdirectories in a node is equal to the number of links to the parent.
00574  * The former skips all stat calls.  The latter skips stat calls in any leaf
00575  * directories and for any files after the subdirectories in the directory have
00576  * been found, cutting the stat calls by about 2/3.
00577  */
00578 static FTSENT *
00579 internal_function
00580 fts_build(sp, type)
00581        register FTS *sp;
00582        int type;
00583 {
00584        register struct dirent *dp;
00585        register FTSENT *p, *head;
00586        register int nitems;
00587        FTSENT *cur, *tail;
00588        DIR *dirp;
00589        void *oldaddr;
00590        int cderrno, descend, len, level, nlinks, saved_errno,
00591            nostat, doadjust;
00592        size_t maxlen;
00593        char *cp;
00594 
00595        /* Set current node pointer. */
00596        cur = sp->fts_cur;
00597 
00598        /*
00599         * Open the directory for reading.  If this fails, we're done.
00600         * If being called from fts_read, set the fts_info field.
00601         */
00602 #if defined FTS_WHITEOUT && 0
00603        if (ISSET(FTS_WHITEOUT))
00604               oflag = DTF_NODUP|DTF_REWIND;
00605        else
00606               oflag = DTF_HIDEW|DTF_NODUP|DTF_REWIND;
00607 #else
00608 # define __opendir2(path, flag) __opendir(path)
00609 #endif
00610        if ((dirp = __opendir2(cur->fts_accpath, oflag)) == NULL) {
00611               if (type == BREAD) {
00612                      cur->fts_info = FTS_DNR;
00613                      cur->fts_errno = errno;
00614               }
00615               return (NULL);
00616        }
00617 
00618        /*
00619         * Nlinks is the number of possible entries of type directory in the
00620         * directory if we're cheating on stat calls, 0 if we're not doing
00621         * any stat calls at all, -1 if we're doing stats on everything.
00622         */
00623        if (type == BNAMES) {
00624               nlinks = 0;
00625               /* Be quiet about nostat, GCC. */
00626               nostat = 0;
00627        } else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL)) {
00628               nlinks = cur->fts_nlink - (ISSET(FTS_SEEDOT) ? 0 : 2);
00629               nostat = 1;
00630        } else {
00631               nlinks = -1;
00632               nostat = 0;
00633        }
00634 
00635 #ifdef notdef
00636        (void)printf("nlinks == %d (cur: %d)\n", nlinks, cur->fts_nlink);
00637        (void)printf("NOSTAT %d PHYSICAL %d SEEDOT %d\n",
00638            ISSET(FTS_NOSTAT), ISSET(FTS_PHYSICAL), ISSET(FTS_SEEDOT));
00639 #endif
00640        /*
00641         * If we're going to need to stat anything or we want to descend
00642         * and stay in the directory, chdir.  If this fails we keep going,
00643         * but set a flag so we don't chdir after the post-order visit.
00644         * We won't be able to stat anything, but we can still return the
00645         * names themselves.  Note, that since fts_read won't be able to
00646         * chdir into the directory, it will have to return different path
00647         * names than before, i.e. "a/b" instead of "b".  Since the node
00648         * has already been visited in pre-order, have to wait until the
00649         * post-order visit to return the error.  There is a special case
00650         * here, if there was nothing to stat then it's not an error to
00651         * not be able to stat.  This is all fairly nasty.  If a program
00652         * needed sorted entries or stat information, they had better be
00653         * checking FTS_NS on the returned nodes.
00654         */
00655        cderrno = 0;
00656        if (nlinks || type == BREAD) {
00657               if (fts_safe_changedir(sp, cur, dirfd(dirp), NULL)) {
00658                      if (nlinks && type == BREAD)
00659                             cur->fts_errno = errno;
00660                      cur->fts_flags |= FTS_DONTCHDIR;
00661                      descend = 0;
00662                      cderrno = errno;
00663                      (void)__closedir(dirp);
00664                      dirp = NULL;
00665               } else
00666                      descend = 1;
00667        } else
00668               descend = 0;
00669 
00670        /*
00671         * Figure out the max file name length that can be stored in the
00672         * current path -- the inner loop allocates more path as necessary.
00673         * We really wouldn't have to do the maxlen calculations here, we
00674         * could do them in fts_read before returning the path, but it's a
00675         * lot easier here since the length is part of the dirent structure.
00676         *
00677         * If not changing directories set a pointer so that can just append
00678         * each new name into the path.
00679         */
00680        len = NAPPEND(cur);
00681        if (ISSET(FTS_NOCHDIR)) {
00682               cp = sp->fts_path + len;
00683               *cp++ = '/';
00684        } else {
00685               /* GCC, you're too verbose. */
00686               cp = NULL;
00687        }
00688        len++;
00689        maxlen = sp->fts_pathlen - len;
00690 
00691        level = cur->fts_level + 1;
00692 
00693        /* Read the directory, attaching each entry to the `link' pointer. */
00694        doadjust = 0;
00695        for (head = tail = NULL, nitems = 0; dirp && (dp = __readdir(dirp));) {
00696               if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))
00697                      continue;
00698 
00699               if ((p = fts_alloc(sp, dp->d_name, _D_EXACT_NAMLEN (dp))) == NULL)
00700                      goto mem1;
00701               if (_D_EXACT_NAMLEN (dp) >= maxlen) {/* include space for NUL */
00702                      oldaddr = sp->fts_path;
00703                      if (fts_palloc(sp, _D_EXACT_NAMLEN (dp) + len + 1)) {
00704                             /*
00705                              * No more memory for path or structures.  Save
00706                              * errno, free up the current structure and the
00707                              * structures already allocated.
00708                              */
00709 mem1:                       saved_errno = errno;
00710                             free(p);
00711                             fts_lfree(head);
00712                             (void)__closedir(dirp);
00713                             cur->fts_info = FTS_ERR;
00714                             SET(FTS_STOP);
00715                             __set_errno (saved_errno);
00716                             return (NULL);
00717                      }
00718                      /* Did realloc() change the pointer? */
00719                      if (oldaddr != sp->fts_path) {
00720                             doadjust = 1;
00721                             if (ISSET(FTS_NOCHDIR))
00722                                    cp = sp->fts_path + len;
00723                      }
00724                      maxlen = sp->fts_pathlen - len;
00725               }
00726 
00727               if (len + _D_EXACT_NAMLEN (dp) >= USHRT_MAX) {
00728                      /*
00729                       * In an FTSENT, fts_pathlen is a u_short so it is
00730                       * possible to wraparound here.  If we do, free up
00731                       * the current structure and the structures already
00732                       * allocated, then error out with ENAMETOOLONG.
00733                       */
00734                      free(p);
00735                      fts_lfree(head);
00736                      (void)__closedir(dirp);
00737                      cur->fts_info = FTS_ERR;
00738                      SET(FTS_STOP);
00739                      __set_errno (ENAMETOOLONG);
00740                      return (NULL);
00741               }
00742               p->fts_level = level;
00743               p->fts_parent = sp->fts_cur;
00744               p->fts_pathlen = len + _D_EXACT_NAMLEN (dp);
00745 
00746 #if defined FTS_WHITEOUT && 0
00747               if (dp->d_type == DT_WHT)
00748                      p->fts_flags |= FTS_ISW;
00749 #endif
00750 
00751 #if 0
00752               /* Unreachable code.  cderrno is only ever set to a nonnull
00753                  value if dirp is closed at the same time.  But then we
00754                  cannot enter this loop.  */
00755               if (cderrno) {
00756                      if (nlinks) {
00757                             p->fts_info = FTS_NS;
00758                             p->fts_errno = cderrno;
00759                      } else
00760                             p->fts_info = FTS_NSOK;
00761                      p->fts_accpath = cur->fts_accpath;
00762               } else
00763 #endif
00764               if (nlinks == 0
00765 #if defined DT_DIR && defined _DIRENT_HAVE_D_TYPE
00766                         || (nostat &&
00767                             dp->d_type != DT_DIR && dp->d_type != DT_UNKNOWN)
00768 #endif
00769                   ) {
00770                      p->fts_accpath =
00771                          ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name;
00772                      p->fts_info = FTS_NSOK;
00773               } else {
00774                      /* Build a file name for fts_stat to stat. */
00775                      if (ISSET(FTS_NOCHDIR)) {
00776                             p->fts_accpath = p->fts_path;
00777                             memmove(cp, p->fts_name, p->fts_namelen + 1);
00778                      } else
00779                             p->fts_accpath = p->fts_name;
00780                      /* Stat it. */
00781                      p->fts_info = fts_stat(sp, p, 0);
00782 
00783                      /* Decrement link count if applicable. */
00784                      if (nlinks > 0 && (p->fts_info == FTS_D ||
00785                          p->fts_info == FTS_DC || p->fts_info == FTS_DOT))
00786                             --nlinks;
00787               }
00788 
00789               /* We walk in directory order so "ls -f" doesn't get upset. */
00790               p->fts_link = NULL;
00791               if (head == NULL)
00792                      head = tail = p;
00793               else {
00794                      tail->fts_link = p;
00795                      tail = p;
00796               }
00797               ++nitems;
00798        }
00799        if (dirp)
00800               (void)__closedir(dirp);
00801 
00802        /*
00803         * If realloc() changed the address of the path, adjust the
00804         * addresses for the rest of the tree and the dir list.
00805         */
00806        if (doadjust)
00807               fts_padjust(sp, head);
00808 
00809        /*
00810         * If not changing directories, reset the path back to original
00811         * state.
00812         */
00813        if (ISSET(FTS_NOCHDIR)) {
00814               if (len == sp->fts_pathlen || nitems == 0)
00815                      --cp;
00816               *cp = '\0';
00817        }
00818 
00819        /*
00820         * If descended after called from fts_children or after called from
00821         * fts_read and nothing found, get back.  At the root level we use
00822         * the saved fd; if one of fts_open()'s arguments is a relative path
00823         * to an empty directory, we wind up here with no other way back.  If
00824         * can't get back, we're done.
00825         */
00826        if (descend && (type == BCHILD || !nitems) &&
00827            (cur->fts_level == FTS_ROOTLEVEL ?
00828             FCHDIR(sp, sp->fts_rfd) :
00829             fts_safe_changedir(sp, cur->fts_parent, -1, ".."))) {
00830               cur->fts_info = FTS_ERR;
00831               SET(FTS_STOP);
00832               fts_lfree(head);
00833               return (NULL);
00834        }
00835 
00836        /* If didn't find anything, return NULL. */
00837        if (!nitems) {
00838               if (type == BREAD)
00839                      cur->fts_info = FTS_DP;
00840               fts_lfree(head);
00841               return (NULL);
00842        }
00843 
00844        /* Sort the entries. */
00845        if (sp->fts_compar && nitems > 1)
00846               head = fts_sort(sp, head, nitems);
00847        return (head);
00848 }
00849 
00850 static u_short
00851 internal_function
00852 fts_stat(sp, p, follow)
00853        FTS *sp;
00854        register FTSENT *p;
00855        int follow;
00856 {
00857        register FTSENT *t;
00858        register dev_t dev;
00859        register ino_t ino;
00860        struct stat *sbp, sb;
00861        int saved_errno;
00862 
00863        /* If user needs stat info, stat buffer already allocated. */
00864        sbp = ISSET(FTS_NOSTAT) ? &sb : p->fts_statp;
00865 
00866 #if defined FTS_WHITEOUT && 0
00867        /* check for whiteout */
00868        if (p->fts_flags & FTS_ISW) {
00869               if (sbp != &sb) {
00870                      memset(sbp, '\0', sizeof (*sbp));
00871                      sbp->st_mode = S_IFWHT;
00872               }
00873               return (FTS_W);
00874        }
00875 #endif
00876 
00877        /*
00878         * If doing a logical walk, or application requested FTS_FOLLOW, do
00879         * a stat(2).  If that fails, check for a non-existent symlink.  If
00880         * fail, set the errno from the stat call.
00881         */
00882        if (ISSET(FTS_LOGICAL) || follow) {
00883               if (stat(p->fts_accpath, sbp)) {
00884                      saved_errno = errno;
00885                      if (!lstat(p->fts_accpath, sbp)) {
00886                             __set_errno (0);
00887                             return (FTS_SLNONE);
00888                      }
00889                      p->fts_errno = saved_errno;
00890                      goto err;
00891               }
00892        } else if (lstat(p->fts_accpath, sbp)) {
00893               p->fts_errno = errno;
00894 err:          memset(sbp, 0, sizeof(struct stat));
00895               return (FTS_NS);
00896        }
00897 
00898        if (S_ISDIR(sbp->st_mode)) {
00899               /*
00900                * Set the device/inode.  Used to find cycles and check for
00901                * crossing mount points.  Also remember the link count, used
00902                * in fts_build to limit the number of stat calls.  It is
00903                * understood that these fields are only referenced if fts_info
00904                * is set to FTS_D.
00905                */
00906               dev = p->fts_dev = sbp->st_dev;
00907               ino = p->fts_ino = sbp->st_ino;
00908               p->fts_nlink = sbp->st_nlink;
00909 
00910               if (ISDOT(p->fts_name))
00911                      return (FTS_DOT);
00912 
00913               /*
00914                * Cycle detection is done by brute force when the directory
00915                * is first encountered.  If the tree gets deep enough or the
00916                * number of symbolic links to directories is high enough,
00917                * something faster might be worthwhile.
00918                */
00919               for (t = p->fts_parent;
00920                   t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
00921                      if (ino == t->fts_ino && dev == t->fts_dev) {
00922                             p->fts_cycle = t;
00923                             return (FTS_DC);
00924                      }
00925               return (FTS_D);
00926        }
00927        if (S_ISLNK(sbp->st_mode))
00928               return (FTS_SL);
00929        if (S_ISREG(sbp->st_mode))
00930               return (FTS_F);
00931        return (FTS_DEFAULT);
00932 }
00933 
00934 static FTSENT *
00935 internal_function
00936 fts_sort(sp, head, nitems)
00937        FTS *sp;
00938        FTSENT *head;
00939        register int nitems;
00940 {
00941        register FTSENT **ap, *p;
00942 
00943        /*
00944         * Construct an array of pointers to the structures and call qsort(3).
00945         * Reassemble the array in the order returned by qsort.  If unable to
00946         * sort for memory reasons, return the directory entries in their
00947         * current order.  Allocate enough space for the current needs plus
00948         * 40 so don't realloc one entry at a time.
00949         */
00950        if (nitems > sp->fts_nitems) {
00951               struct _ftsent **a;
00952 
00953               sp->fts_nitems = nitems + 40;
00954               if ((a = realloc(sp->fts_array,
00955                   (size_t)(sp->fts_nitems * sizeof(FTSENT *)))) == NULL) {
00956                      free(sp->fts_array);
00957                      sp->fts_array = NULL;
00958                      sp->fts_nitems = 0;
00959                      return (head);
00960               }
00961               sp->fts_array = a;
00962        }
00963        for (ap = sp->fts_array, p = head; p; p = p->fts_link)
00964               *ap++ = p;
00965        qsort((void *)sp->fts_array, nitems, sizeof(FTSENT *), sp->fts_compar);
00966        for (head = *(ap = sp->fts_array); --nitems; ++ap)
00967               ap[0]->fts_link = ap[1];
00968        ap[0]->fts_link = NULL;
00969        return (head);
00970 }
00971 
00972 static FTSENT *
00973 internal_function
00974 fts_alloc(sp, name, namelen)
00975        FTS *sp;
00976        const char *name;
00977        size_t namelen;
00978 {
00979        register FTSENT *p;
00980        size_t len;
00981 
00982        /*
00983         * The file name is a variable length array and no stat structure is
00984         * necessary if the user has set the nostat bit.  Allocate the FTSENT
00985         * structure, the file name and the stat structure in one chunk, but
00986         * be careful that the stat structure is reasonably aligned.  Since the
00987         * fts_name field is declared to be of size 1, the fts_name pointer is
00988         * namelen + 2 before the first possible address of the stat structure.
00989         */
00990        len = sizeof(FTSENT) + namelen;
00991        if (!ISSET(FTS_NOSTAT))
00992               len += sizeof(struct stat) + ALIGNBYTES;
00993        if ((p = malloc(len)) == NULL)
00994               return (NULL);
00995 
00996        /* Copy the name and guarantee NUL termination. */
00997        memmove(p->fts_name, name, namelen);
00998        p->fts_name[namelen] = '\0';
00999 
01000        if (!ISSET(FTS_NOSTAT))
01001               p->fts_statp = (struct stat *)ALIGN(p->fts_name + namelen + 2);
01002        p->fts_namelen = namelen;
01003        p->fts_path = sp->fts_path;
01004        p->fts_errno = 0;
01005        p->fts_flags = 0;
01006        p->fts_instr = FTS_NOINSTR;
01007        p->fts_number = 0;
01008        p->fts_pointer = NULL;
01009        return (p);
01010 }
01011 
01012 static void
01013 internal_function
01014 fts_lfree(head)
01015        register FTSENT *head;
01016 {
01017        register FTSENT *p;
01018 
01019        /* Free a linked list of structures. */
01020        while ((p = head)) {
01021               head = head->fts_link;
01022               free(p);
01023        }
01024 }
01025 
01026 /*
01027  * Allow essentially unlimited paths; find, rm, ls should all work on any tree.
01028  * Most systems will allow creation of paths much longer than MAXPATHLEN, even
01029  * though the kernel won't resolve them.  Add the size (not just what's needed)
01030  * plus 256 bytes so don't realloc the path 2 bytes at a time.
01031  */
01032 static int
01033 internal_function
01034 fts_palloc(sp, more)
01035        FTS *sp;
01036        size_t more;
01037 {
01038        char *p;
01039 
01040        sp->fts_pathlen += more + 256;
01041        /*
01042         * Check for possible wraparound.  In an FTS, fts_pathlen is
01043         * a signed int but in an FTSENT it is an unsigned short.
01044         * We limit fts_pathlen to USHRT_MAX to be safe in both cases.
01045         */
01046        if (sp->fts_pathlen < 0 || sp->fts_pathlen >= USHRT_MAX) {
01047               free(sp->fts_path);
01048               sp->fts_path = NULL;
01049               __set_errno (ENAMETOOLONG);
01050               return (1);
01051        }
01052        p = realloc(sp->fts_path, sp->fts_pathlen);
01053        if (p == NULL) {
01054               free(sp->fts_path);
01055               sp->fts_path = NULL;
01056               return 1;
01057        }
01058        sp->fts_path = p;
01059        return 0;
01060 }
01061 
01062 /*
01063  * When the path is realloc'd, have to fix all of the pointers in structures
01064  * already returned.
01065  */
01066 static void
01067 internal_function
01068 fts_padjust(sp, head)
01069        FTS *sp;
01070        FTSENT *head;
01071 {
01072        FTSENT *p;
01073        char *addr = sp->fts_path;
01074 
01075 #define       ADJUST(p) do {                                                 \
01076        if ((p)->fts_accpath != (p)->fts_name) {                \
01077               (p)->fts_accpath =                               \
01078                   (char *)addr + ((p)->fts_accpath - (p)->fts_path);  \
01079        }                                                       \
01080        (p)->fts_path = addr;                                          \
01081 } while (0)
01082        /* Adjust the current set of children. */
01083        for (p = sp->fts_child; p; p = p->fts_link)
01084               ADJUST(p);
01085 
01086        /* Adjust the rest of the tree, including the current level. */
01087        for (p = head; p->fts_level >= FTS_ROOTLEVEL;) {
01088               ADJUST(p);
01089               p = p->fts_link ? p->fts_link : p->fts_parent;
01090        }
01091 }
01092 
01093 static size_t
01094 internal_function
01095 fts_maxarglen(argv)
01096        char * const *argv;
01097 {
01098        size_t len, max;
01099 
01100        for (max = 0; *argv; ++argv)
01101               if ((len = strlen(*argv)) > max)
01102                      max = len;
01103        return (max + 1);
01104 }
01105 
01106 /*
01107  * Change to dir specified by fd or p->fts_accpath without getting
01108  * tricked by someone changing the world out from underneath us.
01109  * Assumes p->fts_dev and p->fts_ino are filled in.
01110  */
01111 static int
01112 internal_function
01113 fts_safe_changedir(sp, p, fd, path)
01114        FTS *sp;
01115        FTSENT *p;
01116        int fd;
01117        const char *path;
01118 {
01119        int ret, oerrno, newfd;
01120        struct stat64 sb;
01121 
01122        newfd = fd;
01123        if (ISSET(FTS_NOCHDIR))
01124               return (0);
01125        if (fd < 0 && (newfd = __open(path, O_RDONLY, 0)) < 0)
01126               return (-1);
01127        if (__fxstat64(_STAT_VER, newfd, &sb)) {
01128               ret = -1;
01129               goto bail;
01130        }
01131        if (p->fts_dev != sb.st_dev || p->fts_ino != sb.st_ino) {
01132               __set_errno (ENOENT);              /* disinformation */
01133               ret = -1;
01134               goto bail;
01135        }
01136        ret = __fchdir(newfd);
01137 bail:
01138        oerrno = errno;
01139        if (fd < 0)
01140               (void)__close(newfd);
01141        __set_errno (oerrno);
01142        return (ret);
01143 }