Return to ftw.c CVS log

Up to [Research Unix] / researchv10no / cmd / odist / opkg

Annotation of researchv10no/cmd/odist/opkg/ftw.c, revision 1.1

1.1     ! root        1: /*
        !             2:  *     ftw - file tree walk
        !             3:  *
        !             4:  *     int ftw (path, fn, depth)  char *path; int (*fn)(); int depth;
        !             5:  *
        !             6:  *     Given a path name, ftw starts from the file given by that path
        !             7:  *     name and visits each file and directory in the tree beneath
        !             8:  *     that file.  If a single file has multiple links within the
        !             9:  *     structure, it will be visited once for each such link.
        !            10:  *     For each object visited, fn is called with four arguments.
        !            11:  *     The fourth can often be ignored; it is a pointer, say S,
        !            12:  *     declared "struct FTW *S", discussed in more detail below.
        !            13:  *     The first contains the path name of the object, the second
        !            14:  *     contains a pointer to a stat buffer which will usually hold
        !            15:  *     appropriate information for the object and the third contains
        !            16:  *     an integer value giving additional information about the
        !            17:  *     object, as follows:
        !            18:  *
        !            19:  *             FTW_F   The object is a file for which stat was
        !            20:  *                     successful.  It does not guarantee that the
        !            21:  *                     file can actually be read.
        !            22:  *
        !            23:  *             FTW_D   The object is a directory for which stat and
        !            24:  *                     open for read were both successful.  This is
        !            25:  *                     a preorder visit -- objects in the directory
        !            26:  *                     are yet to be visited.
        !            27:  *
        !            28:  *             FTW_DNR The object is a directory for which stat
        !            29:  *                     succeeded, but which cannot be read.  Because
        !            30:  *                     the directory cannot be read, fn will not be
        !            31:  *                     called for any descendants of this directory.
        !            32:  *
        !            33:  *             FTW_DP  The object is a directory for which stat and
        !            34:  *                     open for read were both successful.  This is
        !            35:  *                     a postorder visit -- everything in the directory
        !            36:  *                     has already been visited.
        !            37:  *
        !            38:  *             FTW_NS  Lstat failed on the object.  If errno is EACCES,
        !            39:  *                     then the failure stems from lack of
        !            40:  *                     appropriate permission.  This indication will
        !            41:  *                     be given, for example, for each file in a directory
        !            42:  *                     with read but no execute permission.  Whenever
        !            43:  *                     stat fails, it is not possible to determine
        !            44:  *                     whether this object is a file or a directory.
        !            45:  *                     The stat buffer passed to fn will contain garbage.
        !            46:  *
        !            47:  *             FTW_SL  The object is a symbolic link.  Set S->quit
        !            48:  *                     (a component of the structure pointed to by
        !            49:  *                     the fourth parameter to fn) to FTW_FOLLOW to
        !            50:  *                     have the link followed and the object to which
        !            51:  *                     it points visited.
        !            52:  *
        !            53:  *             FTW_NSL Lstat succeeded, but stat failed on the object.
        !            54:  *                     This is only possible when following a symbolic
        !            55:  *                     link.
        !            56:  *
        !            57:  *     Among the components of the structure to which the fourth
        !            58:  *     parameter, S, to fn points is S->quit.  If the caller sets
        !            59:  *     S->quit to FTW_SKR, then no more files in the current directory
        !            60:  *     will be visited.  (The current directory is the one containing
        !            61:  *     the object being visited.)  If the third parameter to fn is
        !            62:  *     FTW_D and the caller sets S->quit to FTW_SKD, then this directory
        !            63:  *     (the one named in the first parameter to fn) will be skipped.
        !            64:  *
        !            65:  *     Other components pointed to by the fourth parameter S are
        !            66:  *     the current recursion level S->level (top level = 0) and
        !            67:  *     the offset S->base in the pathname of the current object
        !            68:  *     (the first parameter to fn) of the object's base name.
        !            69:  *     By expanding the definition of struct FTW given below and
        !            70:  *     including the files included below, one can arrange for
        !            71:  *     S to point to a larger structure, components of which can
        !            72:  *     be initialized (for example) on calls to fn with third
        !            73:  *     parameter FTW_D.
        !            74:  *
        !            75:  *     If fn returns nonzero, ftw stops and returns the same value
        !            76:  *     to its caller.  Ftw only initiates a nonzero return if malloc
        !            77:  *     fails; in this case ftw sets errno to ENOMEM and returns -1.
        !            78:  *
        !            79:  *     The third argument to ftw does not limit the depth to which
        !            80:  *     ftw will go.  Rather, it limits the depth to which ftw will
        !            81:  *     go before it starts recycling file descriptors.  In general,
        !            82:  *     it is necessary to use a file descriptor for each level of the
        !            83:  *     tree, but they can be recycled for deep trees by saving the position,
        !            84:  *     closing, re-opening, and seeking.  It is possible to start
        !            85:  *     recycling file descriptors by sensing when we have run out, but
        !            86:  *     in general this will not be terribly useful if fn expects to be
        !            87:  *     able to open files.  We could also figure out how many file descriptors
        !            88:  *     are available and guarantee a certain number to fn, but we would not
        !            89:  *     know how many to guarantee, and we do not want to impose the extra
        !            90:  *     overhead on a caller who knows how many are available without
        !            91:  *     having to figure it out.
        !            92:  *
        !            93:  *     It is possible for ftw to die with a memory fault in the event
        !            94:  *     of a file system so deeply nested that the stack overflows.
        !            95:  */
        !            96: 
        !            97: #include <sys/types.h>
        !            98: #include <dirent.h>
        !            99: #include <sys/stat.h>
        !           100: #include "ftw.h"
        !           101: /*
        !           102:  * Struct FTW (whose definition starts at the end of ftw.h) must
        !           103:  * must include at least the integers quit, base, and level.
        !           104:  */
        !           105: 
        !           106: #define FTW_PATHLEN0 1000
        !           107: #define FTW_PATHINC 1000
        !           108: 
        !           109: #ifndef S_ISLNK
        !           110: #define lstat stat
        !           111: #endif
        !           112: 
        !           113: #ifndef ENOMEM
        !           114: #include <errno.h>
        !           115: #endif
        !           116: 
        !           117:        extern int errno;
        !           118: 
        !           119: /*
        !           120:  *  Each generation of ftw1 (the real ftw) allocates one copy, R, of the
        !           121:  *  following structure; it passes a pointer to this structure when it
        !           122:  *  recursively invokes itself.  These structures are chained together,
        !           123:  *  so that if it becomes necessary to recycle file descriptors, then
        !           124:  *  the oldest descriptor (the one at the shallowest depth still open)
        !           125:  *  can be recycled.
        !           126:  */
        !           127: 
        !           128:        struct FTW_rec {
        !           129:                struct FTW_rec *prev;
        !           130:                long here;      /* seek to here when reopening at this level */
        !           131:                DIR *fd;        /* file descriptor at this level */
        !           132:                };
        !           133: 
        !           134: /*
        !           135:  *  One instance, T, of the following structure is allocated by ftw; a
        !           136:  *  pointer to it is passed to all generations of ftw1 (the real ftw).
        !           137:  *  T could often be a global variable, but this way the parameter fn
        !           138:  *  can invoke ftw for an independent tree walk.
        !           139:  *  Component T->path points to storage for the object path-names;
        !           140:  *  this storage may be relocated by realloc if T->path needs to be
        !           141:  *  more than T->pathlast characters long.
        !           142:  *  T->path[T->pathnext] is the next free character in the pathnames.
        !           143:  *  T->depth = parameter depth to ftw.  T->lastout is the deepest level at
        !           144:  *  which a file descriptor has been recycled.
        !           145:  */
        !           146: 
        !           147:        struct FTW_top {
        !           148:                int (*fn)();
        !           149:                char *path;
        !           150:                unsigned pathlast, pathnext;
        !           151:                int lastout;
        !           152:                int depth;
        !           153:                };
        !           154: 
        !           155: static ftw_1_();
        !           156: 
        !           157: int
        !           158: ftw (path, fn, depth)
        !           159:        char *path;
        !           160:        int (*fn)();
        !           161:        int depth;
        !           162: {
        !           163:        struct FTW_top T;
        !           164:        struct FTW_rec R;
        !           165:        struct FTW S;
        !           166:        int rc;
        !           167:        char *malloc(), *strcpy();
        !           168: 
        !           169:        T.depth = depth;
        !           170:        T.lastout = -1;
        !           171:        T.fn = fn;
        !           172:        S.quit = 0;
        !           173:        S.level = -1;
        !           174: 
        !           175:        /* initialize S.base, T.pathnext... */
        !           176:                {
        !           177:                register char c, *p, *q;
        !           178:                for (p = q = path; c = *p; p++) if (c == '/') q = p + 1;
        !           179:                S.base = q - path;
        !           180:                T.pathnext = p - path;
        !           181:                }
        !           182: 
        !           183:        T.pathlast = T.pathnext + FTW_PATHLEN0;
        !           184:        T.path = malloc(T.pathlast);
        !           185:        if (!T.path) { errno = ENOMEM; return -1; }
        !           186:        strcpy(T.path, path);
        !           187:        rc = ftw_1_(&R, &T, 0, &S);
        !           188:        free(T.path);
        !           189:        return rc;
        !           190: }
        !           191: 
        !           192: int
        !           193: static
        !           194: ftw_1_ (R, T, level, S1)
        !           195:        register struct FTW_rec *R;
        !           196:        register struct FTW_top *T;
        !           197:        int level;
        !           198:        struct FTW *S1;
        !           199: {
        !           200:        int rc, n;
        !           201:        DIR *fd;
        !           202:        struct dirent *dirp;
        !           203:        char *component, *path;
        !           204:        struct stat sb;
        !           205:        struct FTW_rec mr;
        !           206:        unsigned nextsave;
        !           207:        struct FTW S;
        !           208:        char *realloc();
        !           209:        long lseek();
        !           210: 
        !           211:        mr.prev = R;
        !           212:        path = T->path;
        !           213:        S.level = level;
        !           214:        S.quit = 0;
        !           215:        S.base = S1->base;
        !           216: 
        !           217:        /* Try to get file status.  If unsuccessful, errno will say why. */
        !           218:        if (lstat(path, &sb) < 0) {
        !           219:                rc = (*T->fn) (path, &sb, FTW_NS, &S);
        !           220:                S1->quit = S.quit;
        !           221:                return rc;
        !           222:                };
        !           223: 
        !           224:        /*
        !           225:         *      The stat succeeded, so we know the object exists.
        !           226:         *      If not a directory, call the user function and return.
        !           227:         */
        !           228: #ifdef S_ISLNK
        !           229:        if (S_ISLNK(sb.st_mode )) {
        !           230:                rc = (*T->fn) (path, &sb, FTW_SL, &S);
        !           231:                S1->quit = S.quit;
        !           232:                if (rc || S.quit == FTW_SKR) return rc;
        !           233:                if (S.quit != FTW_FOLLOW) return 0;
        !           234:                S1->quit = S.quit = 0;
        !           235:                if (stat(path, &sb) < 0) {
        !           236:                        rc = (*T->fn) (path, &sb, FTW_NSL, &S);
        !           237:                        S1->quit = S.quit;
        !           238:                        return rc;
        !           239:                        };
        !           240:                }
        !           241: #endif
        !           242:                
        !           243:        if (!S_ISDIR(sb.st_mode)) {
        !           244:                rc = (*T->fn) (path, &sb, FTW_F, &S);
        !           245:                S1->quit = S.quit;
        !           246:                return rc;
        !           247:                }
        !           248: 
        !           249:        /*
        !           250:         *      The object was a directory.
        !           251:         *
        !           252:         *      Open a file to read the directory
        !           253:         */
        !           254:        mr.fd = fd = opendir(path);
        !           255: 
        !           256:        /*
        !           257:         *      Call the user function, telling it whether
        !           258:         *      the directory can be read.  If it can't be read
        !           259:         *      call the user function or indicate an error,
        !           260:         *      depending on the reason it couldn't be read.
        !           261:         */
        !           262:        if (!fd) {
        !           263:                rc = (*T->fn) (path, &sb, FTW_DNR, &S);
        !           264:                S1->quit = S.quit;
        !           265:                return rc;
        !           266:                }
        !           267: 
        !           268:        /* We could read the directory.  Call user function. */
        !           269:        rc = (*T->fn) (path, &sb, FTW_D, &S);
        !           270:        if (rc != 0)
        !           271:                goto rtrn;
        !           272:        if (S.quit == FTW_SKD) goto rtrn;
        !           273:        if (S.quit == FTW_SKR) {S1->quit = FTW_SKR; goto rtrn;}
        !           274: 
        !           275:        /* Make sure path is big enough to hold generated pathnames. */
        !           276: 
        !           277:        n = nextsave = T->pathnext;
        !           278:        if (n + MAXNAMLEN + 1 >= T->pathlast) {
        !           279:                T->pathlast += FTW_PATHINC;
        !           280:                path = T->path = realloc(T->path, T->pathlast);
        !           281:                if (!path) {
        !           282:                        errno = ENOMEM;
        !           283:                        rc = -1;
        !           284:                        goto rtrn;
        !           285:                        }
        !           286:                }
        !           287:        
        !           288:        /* Create a prefix to which we will append component names */
        !           289: 
        !           290:        if (n > 0 && path[n-1] != '/') path[n++] = '/';
        !           291:        component = path + n;
        !           292: 
        !           293:        /*
        !           294:         *      Read the directory one component at a time.
        !           295:         *      We must ignore "." and "..", but other than that,
        !           296:         *      just create a path name and call self to check it out.
        !           297:         */
        !           298:        while (dirp = readdir(fd)) {
        !           299:                if (dirp->d_ino != 0
        !           300:                    && strcmp (dirp->d_name, ".") != 0
        !           301:                    && strcmp (dirp->d_name, "..") != 0) {
        !           302:                        int i;
        !           303:                        struct FTW_rec *pr;
        !           304: 
        !           305:                        /* Append the component name to the working path */
        !           306:                        strcpy(component, dirp->d_name);
        !           307:                        T->pathnext = n + strlen(dirp->d_name);
        !           308: 
        !           309:                        /*
        !           310:                         *      If we are about to exceed our depth,
        !           311:                         *      remember where we are and close the file.
        !           312:                         */
        !           313:                        if (level - T->lastout >= T->depth) {
        !           314:                                pr = &mr;
        !           315:                                i = T->lastout++;
        !           316:                                while (++i < level) pr = pr->prev;
        !           317:                                pr->here = telldir(pr->fd);
        !           318:                                closedir(pr->fd);
        !           319:                        }
        !           320: 
        !           321:                        /*
        !           322:                         *      Do a recursive call to process the file.
        !           323:                         */
        !           324:                        S.quit = 0;
        !           325:                        S.base = n;
        !           326:                        rc = ftw_1_(&mr, T, level+1, &S);
        !           327:                        if (rc != 0 || S.quit == FTW_SKR) {
        !           328:                                if (level > T->lastout) closedir(fd);
        !           329:                                T->pathnext = nextsave;
        !           330:                                return rc;
        !           331:                        }
        !           332: 
        !           333:                        /*
        !           334:                         *      If we closed the file, try to reopen it.
        !           335:                         */
        !           336:                        if (level <= T->lastout) {
        !           337:                                char c = path[nextsave];
        !           338:                                path[nextsave] = 0;
        !           339:                                T->lastout = level - 1;
        !           340:                                mr.fd = fd = opendir(path);
        !           341:                                if (!fd) {
        !           342:                                        rc = (*T->fn) (path, &sb, FTW_DNR, &S);
        !           343:                                        S1->quit = S.quit;
        !           344:                                        T->pathnext = nextsave;
        !           345:                                        return rc;
        !           346:                                        }
        !           347:                                path[nextsave] = c;
        !           348:                                seekdir(fd, mr.here);
        !           349:                                }
        !           350:                        }
        !           351:                }
        !           352:        T->pathnext = nextsave;
        !           353:        path[nextsave] = 0;
        !           354: 
        !           355:        /*
        !           356:         *      We got out of the subdirectory loop.  Call the user
        !           357:         *      function again at the end and clean up.
        !           358:         */
        !           359: 
        !           360:        rc = (*T->fn) (path, &sb, FTW_DP, &S);
        !           361:        S1->quit = S.quit;
        !           362: rtrn:
        !           363:        closedir(fd);
        !           364:        return rc;
        !           365: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.