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

Generated on Sun Oct 26 13:02:03 2003 for rpm by doxygen1.2.18