rpm 5.3.7

rpmio/fts.c

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