Main Page | Modules | Data Structures | File List | Data Fields | Globals | Related Pages

rpmio/fts.c

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

Generated on Tue Dec 21 14:22:42 2004 for rpm by doxygen 1.3.5