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