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