home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / bsd_srcs / lib / libc / gen / fts.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-12-04  |  25.3 KB  |  950 lines
  1. /*-
  2.  * Copyright (c) 1990 The Regents of the University of California.
  3.  * All rights reserved.
  4.  *
  5.  * Redistribution and use in source and binary forms, with or without
  6.  * modification, are permitted provided that the following conditions
  7.  * are met:
  8.  * 1. Redistributions of source code must retain the above copyright
  9.  *    notice, this list of conditions and the following disclaimer.
  10.  * 2. Redistributions in binary form must reproduce the above copyright
  11.  *    notice, this list of conditions and the following disclaimer in the
  12.  *    documentation and/or other materials provided with the distribution.
  13.  * 3. All advertising materials mentioning features or use of this software
  14.  *    must display the following acknowledgement:
  15.  *    This product includes software developed by the University of
  16.  *    California, Berkeley and its contributors.
  17.  * 4. Neither the name of the University nor the names of its contributors
  18.  *    may be used to endorse or promote products derived from this software
  19.  *    without specific prior written permission.
  20.  *
  21.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  22.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  23.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  24.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  25.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  26.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  27.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  28.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  29.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  30.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  31.  * SUCH DAMAGE.
  32.  */
  33.  
  34. #if defined(LIBC_SCCS) && !defined(lint)
  35. static char sccsid[] = "@(#)fts.c    5.40 (Berkeley) 7/23/92";
  36. #endif /* LIBC_SCCS and not lint */
  37.  
  38. #include <sys/param.h>
  39. #include <sys/stat.h>
  40. #include <fcntl.h>
  41. #include <dirent.h>
  42. #include <errno.h>
  43. #include <fts.h>
  44. #include <stdlib.h>
  45. #include <string.h>
  46. #include <unistd.h>
  47.  
  48. static FTSENT    *fts_alloc __P((FTS *, char *, int));
  49. static FTSENT    *fts_build __P((FTS *, int));
  50. static void     fts_lfree __P((FTSENT *));
  51. static void     fts_load __P((FTS *, FTSENT *));
  52. static size_t     fts_maxarglen __P((char * const *));
  53. static void     fts_padjust __P((FTS *, void *));
  54. static int     fts_palloc __P((FTS *, size_t));
  55. static FTSENT    *fts_sort __P((FTS *, FTSENT *, int));
  56. static u_short     fts_stat __P((FTS *, FTSENT *, int));
  57.  
  58. #define    ISDOT(a)    (a[0] == '.' && (!a[1] || a[1] == '.' && !a[2]))
  59.  
  60. #define    ISSET(opt)    (sp->fts_options & opt)
  61. #define    SET(opt)    (sp->fts_options |= opt)
  62.  
  63. #define    CHDIR(sp, path)    (!ISSET(FTS_NOCHDIR) && chdir(path))
  64. #define    FCHDIR(sp, fd)    (!ISSET(FTS_NOCHDIR) && fchdir(fd))
  65.  
  66. /* fts_build flags */
  67. #define    BCHILD        1        /* fts_children */
  68. #define    BNAMES        2        /* fts_children, names only */
  69. #define    BREAD        3        /* fts_read */
  70.  
  71. FTS *
  72. fts_open(argv, options, compar)
  73.     char * const *argv;
  74.     register int options;
  75.     int (*compar)();
  76. {
  77.     register FTS *sp;
  78.     register FTSENT *p, *root;
  79.     register int nitems;
  80.     FTSENT *parent, *tmp;
  81.     int len;
  82.  
  83.     /* Options check. */
  84.     if (options & ~FTS_OPTIONMASK) {
  85.         errno = EINVAL;
  86.         return (NULL);
  87.     }
  88.  
  89.     /* Allocate/initialize the stream */
  90.     if ((sp = malloc((u_int)sizeof(FTS))) == NULL)
  91.         return (NULL);
  92.     bzero(sp, sizeof(FTS));
  93.     sp->fts_compar = compar;
  94.     sp->fts_options = options;
  95.  
  96.     /* Logical walks turn on NOCHDIR; symbolic links are too hard. */
  97.     if (ISSET(FTS_LOGICAL))
  98.         SET(FTS_NOCHDIR);
  99.  
  100.     /*
  101.      * Start out with 1K of path space, and enough, in any case,
  102.      * to hold the user's paths.
  103.      */
  104.     if (fts_palloc(sp, MAX(fts_maxarglen(argv), MAXPATHLEN)))
  105.         goto mem1;
  106.  
  107.     /* Allocate/initialize root's parent. */
  108.     if ((parent = fts_alloc(sp, "", 0)) == NULL)
  109.         goto mem2;
  110.     parent->fts_level = FTS_ROOTPARENTLEVEL;
  111.  
  112.     /* Allocate/initialize root(s). */
  113.     for (root = NULL, nitems = 0; *argv; ++argv, ++nitems) {
  114.         /* Don't allow zero-length paths. */
  115.         if ((len = strlen(*argv)) == 0) {
  116.             errno = ENOENT;
  117.             goto mem3;
  118.         }
  119.  
  120.         p = fts_alloc(sp, *argv, len);
  121.         p->fts_level = FTS_ROOTLEVEL;
  122.         p->fts_parent = parent;
  123.         p->fts_accpath = p->fts_name;
  124.         p->fts_info = fts_stat(sp, p, ISSET(FTS_COMFOLLOW));
  125.  
  126.         /* Command-line "." and ".." are real directories. */
  127.         if (p->fts_info == FTS_DOT)
  128.             p->fts_info = FTS_D;
  129.  
  130.         /*
  131.          * If comparison routine supplied, traverse in sorted
  132.          * order; otherwise traverse in the order specified.
  133.          */
  134.         if (compar) {
  135.             p->fts_link = root;
  136.             root = p;
  137.         } else {
  138.             p->fts_link = NULL;
  139.             if (root == NULL)
  140.                 tmp = root = p;
  141.             else {
  142.                 tmp->fts_link = p;
  143.                 tmp = p;
  144.             }
  145.         }
  146.     }
  147.     if (compar && nitems > 1)
  148.         root = fts_sort(sp, root, nitems);
  149.  
  150.     /*
  151.      * Allocate a dummy pointer and make fts_read think that we've just
  152.      * finished the node before the root(s); set p->fts_info to FTS_INIT
  153.      * so that everything about the "current" node is ignored.
  154.      */
  155.     if ((sp->fts_cur = fts_alloc(sp, "", 0)) == NULL)
  156.         goto mem3;
  157.     sp->fts_cur->fts_link = root;
  158.     sp->fts_cur->fts_info = FTS_INIT;
  159.  
  160.     /*
  161.      * If using chdir(2), grab a file descriptor pointing to dot to insure
  162.      * that we can get back here; this could be avoided for some paths,
  163.      * but almost certainly not worth the effort.  Slashes, symbolic links,
  164.      * and ".." are all fairly nasty problems.  Note, if we can't get the
  165.      * descriptor we run anyway, just more slowly.
  166.      */
  167.     if (!ISSET(FTS_NOCHDIR) && (sp->fts_rfd = open(".", O_RDONLY, 0)) < 0)
  168.         SET(FTS_NOCHDIR);
  169.  
  170.     return (sp);
  171.  
  172. mem3:    fts_lfree(root);
  173.     free(parent);
  174. mem2:    free(sp->fts_path);
  175. mem1:    free(sp);
  176.     return (NULL);
  177. }
  178.  
  179. static void
  180. fts_load(sp, p)
  181.     FTS *sp;
  182.     register FTSENT *p;
  183. {
  184.     register int len;
  185.     register char *cp;
  186.  
  187.     /*
  188.      * Load the stream structure for the next traversal.  Since we don't
  189.      * actually enter the directory until after the preorder visit, set
  190.      * the fts_accpath field specially so the chdir gets done to the right
  191.      * place and the user can access the first node.  From fts_open it's
  192.      * known that the path will fit.
  193.      */
  194.     len = p->fts_pathlen = p->fts_namelen;
  195.     bcopy(p->fts_name, sp->fts_path, len + 1);
  196.     if ((cp = rindex(p->fts_name, '/')) && (cp != p->fts_name || cp[1])) {
  197.         len = strlen(++cp);
  198.         bcopy(cp, p->fts_name, len + 1);
  199.         p->fts_namelen = len;
  200.     }
  201.     p->fts_accpath = p->fts_path = sp->fts_path;
  202.     sp->fts_dev = p->fts_dev;
  203. }
  204.  
  205. int
  206. fts_close(sp)
  207.     FTS *sp;
  208. {
  209.     register FTSENT *freep, *p;
  210.     int saved_errno;
  211.  
  212.     /*
  213.      * This still works if we haven't read anything -- the dummy structure
  214.      * points to the root list, so we step through to the end of the root
  215.      * list which has a valid parent pointer.
  216.      */
  217.     if (sp->fts_cur) {
  218.         for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {
  219.             freep = p;
  220.             p = p->fts_link ? p->fts_link : p->fts_parent;
  221.             free(freep);
  222.         }
  223.         free(p);
  224.     }
  225.  
  226.     /* Free up child linked list, sort array, path buffer. */
  227.     if (sp->fts_child)
  228.         fts_lfree(sp->fts_child);
  229.     if (sp->fts_array)
  230.         free(sp->fts_array);
  231.     free(sp->fts_path);
  232.  
  233.     /* Return to original directory, save errno if necessary. */
  234.     if (!ISSET(FTS_NOCHDIR)) {
  235.         saved_errno = fchdir(sp->fts_rfd) ? errno : 0;
  236.         (void)close(sp->fts_rfd);
  237.     }
  238.  
  239.     /* Free up the stream pointer. */
  240.     free(sp);
  241.  
  242.     /* Set errno and return. */
  243.     if (!ISSET(FTS_NOCHDIR) && saved_errno) {
  244.         errno = saved_errno;
  245.         return (-1);
  246.     }
  247.     return (0);
  248. }
  249.  
  250. /*
  251.  * Special case a root of "/" so that slashes aren't appended which would
  252.  * cause paths to be written as "//foo".
  253.  */
  254. #define    NAPPEND(p)                            \
  255.     (p->fts_level == FTS_ROOTLEVEL && p->fts_pathlen == 1 &&    \
  256.         p->fts_path[0] == '/' ? 0 : p->fts_pathlen)
  257.  
  258. FTSENT *
  259. fts_read(sp)
  260.     register FTS *sp;
  261. {
  262.     register FTSENT *p, *tmp;
  263.     register int instr;
  264.     register char *t;
  265.     int saved_errno;
  266.  
  267.     /* If finished or unrecoverable error, return NULL. */
  268.     if (sp->fts_cur == NULL || ISSET(FTS_STOP))
  269.         return (NULL);
  270.  
  271.     /* Set current node pointer. */
  272.     p = sp->fts_cur;
  273.  
  274.     /* Save and zero out user instructions. */
  275.     instr = p->fts_instr;
  276.     p->fts_instr = FTS_NOINSTR;
  277.  
  278.     /* Any type of file may be re-visited; re-stat and re-turn. */
  279.     if (instr == FTS_AGAIN) {
  280.         p->fts_info = fts_stat(sp, p, 0);
  281.         return (p);
  282.     }
  283.  
  284.     /*
  285.      * Following a symlink -- SLNONE test allows application to see
  286.      * SLNONE and recover.  If indirecting through a symlink, have
  287.      * keep a pointer to current location.  If unable to get that
  288.      * pointer, follow fails.
  289.      */
  290.     if (instr == FTS_FOLLOW &&
  291.         (p->fts_info == FTS_SL || p->fts_info == FTS_SLNONE)) {
  292.         p->fts_info = fts_stat(sp, p, 1);
  293.         if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR))
  294.             if ((p->fts_symfd = open(".", O_RDONLY, 0)) < 0) {
  295.                 p->fts_errno = errno;
  296.                 p->fts_info = FTS_ERR;
  297.             } else
  298.                 p->fts_flags |= FTS_SYMFOLLOW;
  299.         return (p);
  300.     }
  301.  
  302.     /* Directory in pre-order. */
  303.     if (p->fts_info == FTS_D) {
  304.         /* If skipped or crossed mount point, do post-order visit. */
  305.         if (instr == FTS_SKIP ||
  306.             ISSET(FTS_XDEV) && p->fts_dev != sp->fts_dev) {
  307.             if (p->fts_flags & FTS_SYMFOLLOW)
  308.                 (void)close(p->fts_symfd);
  309.             if (sp->fts_child) {
  310.                 fts_lfree(sp->fts_child);
  311.                 sp->fts_child = NULL;
  312.             }
  313.             p->fts_info = FTS_DP;
  314.             return (p);
  315.         } 
  316.  
  317.         /* Rebuild if only read the names and now traversing. */
  318.         if (sp->fts_child && sp->fts_options & FTS_NAMEONLY) {
  319.             sp->fts_options &= ~FTS_NAMEONLY;
  320.             fts_lfree(sp->fts_child);
  321.             sp->fts_child = NULL;
  322.         }
  323.  
  324.         /*
  325.          * Cd to the subdirectory.
  326.          *
  327.          * If have already read and now fail to chdir, whack the list
  328.          * to make the names come out right, and set the parent errno
  329.          * so the application will eventually get an error condition.
  330.          * Set the FTS_DONTCHDIR flag so that when we logically change
  331.          * directories back to the parent we don't do a chdir.
  332.          *
  333.          * If haven't read do so.  If the read fails, fts_build sets
  334.          * FTS_STOP or the fts_info field of the node.
  335.          */
  336.         if (sp->fts_child) {
  337.             if (CHDIR(sp, p->fts_accpath)) {
  338.                 p->fts_errno = errno;
  339.                 p->fts_flags |= FTS_DONTCHDIR;
  340.                 for (p = sp->fts_child; p; p = p->fts_link)
  341.                     p->fts_accpath =
  342.                         p->fts_parent->fts_accpath;
  343.             }
  344.         } else if ((sp->fts_child = fts_build(sp, BREAD)) == NULL) {
  345.             if (ISSET(FTS_STOP))
  346.                 return (NULL);
  347.             return (p);
  348.         }
  349.         p = sp->fts_child;
  350.         sp->fts_child = NULL;
  351.         goto name;
  352.     }
  353.  
  354.     /* Move to the next node on this level. */
  355. next:    tmp = p;
  356.     if (p = p->fts_link) {
  357.         free(tmp);
  358.  
  359.         /* If reached the top, load the paths for the next root. */
  360.         if (p->fts_level == FTS_ROOTLEVEL) {
  361.             fts_load(sp, p);
  362.             return (sp->fts_cur = p);
  363.         }
  364.  
  365.         /*
  366.          * User may have called fts_set on the node.  If skipped,
  367.          * ignore.  If followed, get a file descriptor so we can
  368.          * get back if necessary.
  369.          */
  370.         if (p->fts_instr == FTS_SKIP)
  371.             goto next;
  372.         if (p->fts_instr == FTS_FOLLOW) {
  373.             p->fts_info = fts_stat(sp, p, 1);
  374.             if (p->fts_info == FTS_D && !ISSET(FTS_NOCHDIR))
  375.                 if ((p->fts_symfd =
  376.                     open(".", O_RDONLY, 0)) < 0) {
  377.                     p->fts_errno = errno;
  378.                     p->fts_info = FTS_ERR;
  379.                 } else
  380.                     p->fts_flags |= FTS_SYMFOLLOW;
  381.             p->fts_instr = FTS_NOINSTR;
  382.         }
  383.  
  384. name:        t = sp->fts_path + NAPPEND(p->fts_parent);
  385.         *t++ = '/';
  386.         bcopy(p->fts_name, t, p->fts_namelen + 1);
  387.         return (sp->fts_cur = p);
  388.     }
  389.  
  390.     /* Move up to the parent node. */
  391.     p = tmp->fts_parent;
  392.     free(tmp);
  393.  
  394.     if (p->fts_level == FTS_ROOTPARENTLEVEL) {
  395.         /*
  396.          * Done; free everything up and set errno to 0 so the user
  397.          * can distinguish between error and EOF.
  398.          */
  399.         free(p);
  400.         errno = 0;
  401.         return (sp->fts_cur = NULL);
  402.     }
  403.  
  404.     /* Nul terminate the pathname. */
  405.     sp->fts_path[p->fts_pathlen] = '\0';
  406.  
  407.     /*
  408.      * Return to the parent directory.  If at a root node or came through
  409.      * a symlink, go back through the file descriptor.  Otherwise, cd up
  410.      * one directory.
  411.      */
  412.     if (p->fts_level == FTS_ROOTLEVEL) {
  413.         if (!ISSET(FTS_NOCHDIR) && FCHDIR(sp, sp->fts_rfd)) {
  414.             SET(FTS_STOP);
  415.             return (NULL);
  416.         }
  417.     } else if (p->fts_flags & FTS_SYMFOLLOW) {
  418.         if (FCHDIR(sp, p->fts_symfd)) {
  419.             saved_errno = errno;
  420.             (void)close(p->fts_symfd);
  421.             errno = saved_errno;
  422.             SET(FTS_STOP);
  423.             return (NULL);
  424.         }
  425.         (void)close(p->fts_symfd);
  426.     } else if (!(p->fts_flags & FTS_DONTCHDIR)) {
  427.         if (CHDIR(sp, "..")) {
  428.             SET(FTS_STOP);
  429.             return (NULL);
  430.         }
  431.     }
  432.     p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;
  433.     return (sp->fts_cur = p);
  434. }
  435.  
  436. /*
  437.  * Fts_set takes the stream as an argument although it's not used in this
  438.  * implementation; it would be necessary if anyone wanted to add global
  439.  * semantics to fts using fts_set.  An error return is allowed for similar
  440.  * reasons.
  441.  */
  442. /* ARGSUSED */
  443. int
  444. fts_set(sp, p, instr)
  445.     FTS *sp;
  446.     FTSENT *p;
  447.     int instr;
  448. {
  449.     if (instr && instr != FTS_AGAIN && instr != FTS_FOLLOW &&
  450.         instr != FTS_NOINSTR && instr != FTS_SKIP) {
  451.         errno = EINVAL;
  452.         return (1);
  453.     }
  454.     p->fts_instr = instr;
  455.     return (0);
  456. }
  457.  
  458. FTSENT *
  459. fts_children(sp, instr)
  460.     register FTS *sp;
  461.     int instr;
  462. {
  463.     register FTSENT *p;
  464.     int fd;
  465.  
  466.     if (instr && instr != FTS_NAMEONLY) {
  467.         errno = EINVAL;
  468.         return (NULL);
  469.     }
  470.  
  471.     /* Set current node pointer. */
  472.     p = sp->fts_cur;
  473.  
  474.     /*
  475.      * Errno set to 0 so user can distinguish empty directory from
  476.      * an error.
  477.      */
  478.     errno = 0;
  479.  
  480.     /* Fatal errors stop here. */
  481.     if (ISSET(FTS_STOP))
  482.         return (NULL);
  483.  
  484.     /* Return logical hierarchy of user's arguments. */
  485.     if (p->fts_info == FTS_INIT)
  486.         return (p->fts_link);
  487.  
  488.     /*
  489.      * If not a directory being visited in pre-order, stop here.  Could
  490.      * allow FTS_DNR, assuming the user has fixed the problem, but the
  491.      * same effect is available with FTS_AGAIN.
  492.      */
  493.     if (p->fts_info != FTS_D /* && p->fts_info != FTS_DNR */)
  494.         return (NULL);
  495.  
  496.     /* Free up any previous child list. */
  497.     if (sp->fts_child)
  498.         fts_lfree(sp->fts_child);
  499.  
  500.     if (instr == FTS_NAMEONLY) {
  501.         sp->fts_options |= FTS_NAMEONLY;
  502.         instr = BNAMES;
  503.     } else 
  504.         instr = BCHILD;
  505.  
  506.     /*
  507.      * If using chdir on a relative path and called BEFORE fts_read does
  508.      * its chdir to the root of a traversal, we can lose -- we need to
  509.      * chdir into the subdirectory, and we don't know where the current
  510.      * directory is, so we can't get back so that the upcoming chdir by
  511.      * fts_read will work.
  512.      */
  513.     if (p->fts_level != FTS_ROOTLEVEL || p->fts_accpath[0] == '/' ||
  514.         ISSET(FTS_NOCHDIR))
  515.         return (sp->fts_child = fts_build(sp, instr));
  516.  
  517.     if ((fd = open(".", O_RDONLY, 0)) < 0)
  518.         return (NULL);
  519.     sp->fts_child = fts_build(sp, instr);
  520.     if (fchdir(fd))
  521.         return (NULL);
  522.     (void)close(fd);
  523.     return (sp->fts_child);
  524. }
  525.  
  526. /*
  527.  * This is the tricky part -- do not casually change *anything* in here.  The
  528.  * idea is to build the linked list of entries that are used by fts_children
  529.  * and fts_read.  There are lots of special cases.
  530.  *
  531.  * The real slowdown in walking the tree is the stat calls.  If FTS_NOSTAT is
  532.  * set and it's a physical walk (so that symbolic links can't be directories),
  533.  * we assume that the number of subdirectories in a node is equal to the number
  534.  * of links to the parent.  This allows stat calls to be skipped in any leaf
  535.  * directories and for any nodes after the directories in the parent node have
  536.  * been found.  This empirically cuts the stat calls by about 2/3.
  537.  */
  538. static FTSENT *
  539. fts_build(sp, type)
  540.     register FTS *sp;
  541.     int type;
  542. {
  543.     register struct dirent *dp;
  544.     register FTSENT *p, *head;
  545.     register int nitems;
  546.     FTSENT *cur, *tail;
  547.     DIR *dirp;
  548.     void *adjaddr;
  549.     int cderrno, descend, len, level, maxlen, nlinks, saved_errno;
  550.     char *cp;
  551.  
  552.     /* Set current node pointer. */
  553.     cur = sp->fts_cur;
  554.  
  555.     /*
  556.      * Open the directory for reading.  If this fails, we're done.
  557.      * If being called from fts_read, set the fts_info field.
  558.      */
  559.     if ((dirp = opendir(cur->fts_accpath)) == NULL) {
  560.         if (type == BREAD) {
  561.             cur->fts_info = FTS_DNR;
  562.             cur->fts_errno = errno;
  563.         }
  564.         return (NULL);
  565.     }
  566.  
  567.     /*
  568.      * Nlinks is the number of possible entries of type directory in the
  569.      * directory if we're cheating on stat calls, 0 if we're not doing
  570.      * any stat calls at all, -1 if we're doing stats on everything.
  571.      */
  572.     if (type == BNAMES)
  573.         nlinks = 0;
  574.     else if (ISSET(FTS_NOSTAT) && ISSET(FTS_PHYSICAL))
  575.         nlinks = cur->fts_nlink - (ISSET(FTS_SEEDOT) ? 0 : 2);
  576.     else
  577.         nlinks = -1;
  578.  
  579. #ifdef notdef
  580.     (void)printf("nlinks == %d (cur: %d)\n", nlinks, cur->fts_nlink);
  581.     (void)printf("NOSTAT %d PHYSICAL %d SEEDOT %d\n",
  582.         ISSET(FTS_NOSTAT), ISSET(FTS_PHYSICAL), ISSET(FTS_SEEDOT));
  583. #endif
  584.     /*
  585.      * If we're going to need to stat anything or we want to descend
  586.      * and stay in the directory, chdir.  If this fails we keep going,
  587.      * but set a flag so we don't chdir after the post-order visit.
  588.      * We won't be able to stat anything, but we can still return the
  589.      * names themselves.  Note, that since fts_read won't be able to
  590.      * chdir into the directory, it will have to return different path
  591.      * names than before, i.e. "a/b" instead of "b".  Since the node
  592.      * has already been visited in pre-order, have to wait until the
  593.      * post-order visit to return the error.  There is a special case
  594.      * here, if there was nothing to stat then it's not an error to
  595.      * not be able to stat.  This is all fairly nasty.  If a program
  596.      * needed sorted entries or stat information, they had better be
  597.      * checking FTS_NS on the returned nodes.
  598.      */
  599.     if (nlinks || type == BREAD)
  600.         if (FCHDIR(sp, dirfd(dirp))) {
  601.             if (nlinks && type == BREAD)
  602.                 cur->fts_errno = errno;
  603.             cur->fts_flags |= FTS_DONTCHDIR;
  604.             descend = 0;
  605.             cderrno = errno;
  606.         } else {
  607.             descend = 1;
  608.             cderrno = 0;
  609.         }
  610.     else
  611.         descend = 0;
  612.  
  613.     /*
  614.      * Figure out the max file name length that can be stored in the
  615.      * current path -- the inner loop allocates more path as necessary.
  616.      * We really wouldn't have to do the maxlen calculations here, we
  617.      * could do them in fts_read before returning the path, but it's a
  618.      * lot easier here since the length is part of the dirent structure.
  619.      *
  620.      * If not changing directories set a pointer so that can just append
  621.      * each new name into the path.
  622.      */
  623.     maxlen = sp->fts_pathlen - cur->fts_pathlen - 1;
  624.     len = NAPPEND(cur);
  625.     if (ISSET(FTS_NOCHDIR)) {
  626.         cp = sp->fts_path + len;
  627.         *cp++ = '/';
  628.     }
  629.  
  630.     level = cur->fts_level + 1;
  631.  
  632.     /* Read the directory, attaching each entry to the `link' pointer. */
  633.     adjaddr = NULL;
  634.     for (head = tail = NULL, nitems = 0; dp = readdir(dirp);) {
  635.         if (!ISSET(FTS_SEEDOT) && ISDOT(dp->d_name))
  636.             continue;
  637.  
  638.         if ((p = fts_alloc(sp, dp->d_name, (int)dp->d_namlen)) == NULL)
  639.             goto mem1;
  640.         if (dp->d_namlen > maxlen) {
  641.             if (fts_palloc(sp, (size_t)dp->d_namlen)) {
  642.                 /*
  643.                  * No more memory for path or structures.  Save
  644.                  * errno, free up the current structure and the
  645.                  * structures already allocated.
  646.                  */
  647. mem1:                saved_errno = errno;
  648.                 if (p)
  649.                     free(p);
  650.                 fts_lfree(head);
  651.                 (void)closedir(dirp);
  652.                 errno = saved_errno;
  653.                 cur->fts_info = FTS_ERR;
  654.                 SET(FTS_STOP);
  655.                 return (NULL);
  656.             }
  657.             adjaddr = sp->fts_path;
  658.             maxlen = sp->fts_pathlen - sp->fts_cur->fts_pathlen - 1;
  659.         }
  660.  
  661.         p->fts_pathlen = len + dp->d_namlen + 1;
  662.         p->fts_parent = sp->fts_cur;
  663.         p->fts_level = level;
  664.  
  665.         if (cderrno) {
  666.             if (nlinks) {
  667.                 p->fts_info = FTS_NS;
  668.                 p->fts_errno = cderrno;
  669.             } else
  670.                 p->fts_info = FTS_NSOK;
  671.             p->fts_accpath = cur->fts_accpath;
  672.         } else if (nlinks) {
  673.             /* Build a file name for fts_stat to stat. */
  674.             if (ISSET(FTS_NOCHDIR)) {
  675.                 p->fts_accpath = p->fts_path;
  676.                 bcopy(p->fts_name, cp, p->fts_namelen + 1);
  677.             } else
  678.                 p->fts_accpath = p->fts_name;
  679.             p->fts_info = fts_stat(sp, p, 0);
  680.             if (nlinks > 0 && (p->fts_info == FTS_D ||
  681.                 p->fts_info == FTS_DC || p->fts_info == FTS_DOT))
  682.                 --nlinks;
  683.         } else {
  684.             p->fts_accpath =
  685.                 ISSET(FTS_NOCHDIR) ? p->fts_path : p->fts_name;
  686.             p->fts_info = FTS_NSOK;
  687.         }
  688.  
  689.         /* We walk in directory order so "ls -f" doesn't get upset. */
  690.         p->fts_link = NULL;
  691.         if (head == NULL)
  692.             head = tail = p;
  693.         else {
  694.             tail->fts_link = p;
  695.             tail = p;
  696.         }
  697.         ++nitems;
  698.     }
  699.     (void)closedir(dirp);
  700.  
  701.     /*
  702.      * If had to realloc the path, adjust the addresses for the rest
  703.      * of the tree.
  704.      */
  705.     if (adjaddr)
  706.         fts_padjust(sp, adjaddr);
  707.  
  708.     /*
  709.      * If not changing directories, reset the path back to original
  710.      * state.
  711.      */
  712.     if (ISSET(FTS_NOCHDIR)) {
  713.         if (cp - 1 > sp->fts_path)
  714.             --cp;
  715.         *cp = '\0';
  716.     }
  717.  
  718.     /*
  719.      * If descended after called from fts_children or called from
  720.      * fts_read and didn't find anything, get back.  If can't get
  721.      * back, done.
  722.      */
  723.     if (descend && (!nitems || type == BCHILD) && CHDIR(sp, "..")) {
  724.         cur->fts_info = FTS_ERR;
  725.         SET(FTS_STOP);
  726.         return (NULL);
  727.     }
  728.  
  729.     /* If didn't find anything, return NULL. */
  730.     if (!nitems) {
  731.         if (type == BREAD)
  732.             cur->fts_info = FTS_DP;
  733.         return (NULL);
  734.     }
  735.  
  736.     /* Sort the entries. */
  737.     if (sp->fts_compar && nitems > 1)
  738.         head = fts_sort(sp, head, nitems);
  739.     return (head);
  740. }
  741.  
  742. static u_short
  743. fts_stat(sp, p, follow)
  744.     FTS *sp;
  745.     register FTSENT *p;
  746.     int follow;
  747. {
  748.     register FTSENT *t;
  749.     register dev_t dev;
  750.     register ino_t ino;
  751.     struct stat *sbp, sb;
  752.     int saved_errno;
  753.  
  754.     /* If user needs stat info, stat buffer already allocated. */
  755.     sbp = ISSET(FTS_NOSTAT) ? &sb : p->fts_statp;
  756.     
  757.     /*
  758.      * If doing a logical walk, or application requested FTS_FOLLOW, do
  759.      * a stat(2).  If that fails, check for a non-existent symlink.  If
  760.      * fail, set the errno from the stat call.
  761.      */
  762.     if (ISSET(FTS_LOGICAL) || follow) {
  763.         if (stat(p->fts_accpath, sbp)) {
  764.             saved_errno = errno;
  765.             if (!lstat(p->fts_accpath, sbp)) {
  766.                 errno = 0;
  767.                 return (FTS_SLNONE);
  768.             } 
  769.             p->fts_errno = saved_errno;
  770.             goto err;
  771.         }
  772.     } else if (lstat(p->fts_accpath, sbp)) {
  773.         p->fts_errno = errno;
  774. err:        bzero(sbp, sizeof(struct stat));
  775.         return (FTS_NS);
  776.     }
  777.  
  778.     if (S_ISDIR(sbp->st_mode)) {
  779.         /*
  780.          * Set the device/inode.  Used to find cycles and check for
  781.          * crossing mount points.  Also remember the link count, used
  782.          * in fts_build to limit the number of stat calls.  It is
  783.          * understood that these fields are only referenced if fts_info
  784.          * is set to FTS_D.
  785.          */
  786.         dev = p->fts_dev = sbp->st_dev;
  787.         ino = p->fts_ino = sbp->st_ino;
  788.         p->fts_nlink = sbp->st_nlink;
  789.  
  790.         if (ISDOT(p->fts_name))
  791.             return (FTS_DOT);
  792.  
  793.         /*
  794.          * Cycle detection is done by brute force when the directory
  795.          * is first encountered.  If the tree gets deep enough or the
  796.          * number of symbolic links to directories is high enough,
  797.          * something faster might be worthwhile.
  798.          */
  799.         for (t = p->fts_parent;
  800.             t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent)
  801.             if (ino == t->fts_ino && dev == t->fts_dev) {
  802.                 p->fts_cycle = t;
  803.                 return (FTS_DC);
  804.             }
  805.         return (FTS_D);
  806.     }
  807.     if (S_ISLNK(sbp->st_mode))
  808.         return (FTS_SL);
  809.     if (S_ISREG(sbp->st_mode))
  810.         return (FTS_F);
  811.     return (FTS_DEFAULT);
  812. }
  813.  
  814. static FTSENT *
  815. fts_sort(sp, head, nitems)
  816.     FTS *sp;
  817.     FTSENT *head;
  818.     register int nitems;
  819. {
  820.     register FTSENT **ap, *p;
  821.  
  822.     /*
  823.      * Construct an array of pointers to the structures and call qsort(3).
  824.      * Reassemble the array in the order returned by qsort.  If unable to
  825.      * sort for memory reasons, return the directory entries in their
  826.      * current order.  Allocate enough space for the current needs plus
  827.      * 40 so don't realloc one entry at a time.
  828.      */
  829.     if (nitems > sp->fts_nitems) {
  830.         sp->fts_nitems = nitems + 40;
  831.         if ((sp->fts_array = realloc(sp->fts_array,
  832.             (size_t)(sp->fts_nitems * sizeof(FTSENT *)))) == NULL) {
  833.             sp->fts_nitems = 0;
  834.             return (head);
  835.         }
  836.     }
  837.     for (ap = sp->fts_array, p = head; p; p = p->fts_link)
  838.         *ap++ = p;
  839.     qsort((void *)sp->fts_array, nitems, sizeof(FTSENT *), sp->fts_compar);
  840.     for (head = *(ap = sp->fts_array); --nitems; ++ap)
  841.         ap[0]->fts_link = ap[1];
  842.     ap[0]->fts_link = NULL;
  843.     return (head);
  844. }
  845.  
  846. static FTSENT *
  847. fts_alloc(sp, name, namelen)
  848.     FTS *sp;
  849.     char *name;
  850.     register int namelen;
  851. {
  852.     register FTSENT *p;
  853.     size_t len;
  854.  
  855.     /*
  856.      * The file name is a variable length array and no stat structure is
  857.      * necessary if the user has set the nostat bit.  Allocate the FTSENT
  858.      * structure, the file name and the stat structure in one chunk, but
  859.      * be careful that the stat structure is reasonably aligned.  Since the
  860.      * fts_name field is declared to be of size 1, the fts_name pointer is
  861.      * namelen + 2 before the first possible address of the stat structure.
  862.      */
  863.     len = sizeof(FTSENT) + namelen;
  864.     if (!ISSET(FTS_NOSTAT))
  865.         len += sizeof(struct stat) + ALIGNBYTES;
  866.     if ((p = malloc(len)) == NULL)
  867.         return (NULL);
  868.  
  869.     /* Copy the name plus the trailing NULL. */
  870.     bcopy(name, p->fts_name, namelen + 1);
  871.  
  872.     if (!ISSET(FTS_NOSTAT))
  873.         p->fts_statp = (struct stat *)ALIGN(p->fts_name + namelen + 2);
  874.     p->fts_namelen = namelen;
  875.     p->fts_path = sp->fts_path;
  876.     p->fts_errno = 0;
  877.     p->fts_flags = 0;
  878.     p->fts_instr = FTS_NOINSTR;
  879.     p->fts_number = 0;
  880.     p->fts_pointer = NULL;
  881.     return (p);
  882. }
  883.  
  884. static void
  885. fts_lfree(head)
  886.     register FTSENT *head;
  887. {
  888.     register FTSENT *p;
  889.  
  890.     /* Free a linked list of structures. */
  891.     while (p = head) {
  892.         head = head->fts_link;
  893.         free(p);
  894.     }
  895. }
  896.  
  897. /*
  898.  * Allow essentially unlimited paths; find, rm, ls should all work on any tree.
  899.  * Most systems will allow creation of paths much longer than MAXPATHLEN, even
  900.  * though the kernel won't resolve them.  Add the size (not just what's needed)
  901.  * plus 256 bytes so don't realloc the path 2 bytes at a time. 
  902.  */
  903. static int
  904. fts_palloc(sp, more)
  905.     FTS *sp;
  906.     size_t more;
  907. {
  908.     sp->fts_pathlen += more + 256;
  909.     sp->fts_path = realloc(sp->fts_path, (size_t)sp->fts_pathlen);
  910.     return (sp->fts_path == NULL);
  911. }
  912.  
  913. /*
  914.  * When the path is realloc'd, have to fix all of the pointers in structures
  915.  * already returned.
  916.  */
  917. static void
  918. fts_padjust(sp, addr)
  919.     FTS *sp;
  920.     void *addr;
  921. {
  922.     FTSENT *p;
  923.  
  924. #define    ADJUST(p) {                            \
  925.     (p)->fts_accpath = addr + ((p)->fts_accpath - (p)->fts_path);    \
  926.     (p)->fts_path = addr;                        \
  927. }
  928.     /* Adjust the current set of children. */
  929.     for (p = sp->fts_child; p; p = p->fts_link)
  930.         ADJUST(p);
  931.  
  932.     /* Adjust the rest of the tree. */
  933.     for (p = sp->fts_cur; p->fts_level >= FTS_ROOTLEVEL;) {
  934.         ADJUST(p);
  935.         p = p->fts_link ? p->fts_link : p->fts_parent;
  936.     }
  937. }
  938.  
  939. static size_t
  940. fts_maxarglen(argv)
  941.     char * const *argv;
  942. {
  943.     size_t len, max;
  944.  
  945.     for (max = 0; *argv; ++argv)
  946.         if ((len = strlen(*argv)) > max)
  947.             max = len;
  948.     return (max);
  949. }
  950.