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