X-Git-Url: http://erislabs.net/gitweb/?a=blobdiff_plain;f=lib%2Ffts.c;h=8666cff871ce1e185b4e5eeaad8e1a48b178f3cf;hb=f84215faa43d2933011459dd42ba518df63e34c4;hp=11ec512938cfb68820f7c890975a3131cb7f4bda;hpb=c0b6cbd43c59550c565712d0ba6a3fe827d63f4d;p=gnulib.git diff --git a/lib/fts.c b/lib/fts.c index 11ec51293..8666cff87 100644 --- a/lib/fts.c +++ b/lib/fts.c @@ -1,6 +1,6 @@ /* Traverse a file hierarchy. - Copyright (C) 2004, 2005 Free Software Foundation, Inc. + Copyright (C) 2004, 2005, 2006 Free Software Foundation, Inc. This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by @@ -53,6 +53,8 @@ static char sccsid[] = "@(#)fts.c 8.6 (Berkeley) 8/14/94"; #endif /* LIBC_SCCS and not lint */ +#include "fts_.h" + #if HAVE_SYS_PARAM_H || defined _LIBC # include #endif @@ -64,28 +66,13 @@ static char sccsid[] = "@(#)fts.c 8.6 (Berkeley) 8/14/94"; #include #include #include "dirfd.h" -#include "fts_.h" -#include "intprops.h" -#include "unistd-safer.h" +#include #include #include #include -#if HAVE_INTTYPES_H -# include -#endif -#if HAVE_STDINT_H -# include -#endif -#if ULONG_MAX < ULLONG_MAX -# define LONGEST_MODIFIER "ll" -#else -# define LONGEST_MODIFIER "l" -#endif -#if PRI_MACROS_BROKEN -# undef PRIuMAX -#endif -#ifndef PRIuMAX -# define PRIuMAX LONGEST_MODIFIER "u" + +#if ! _LIBC +# include "lstat.h" #endif #if defined _LIBC @@ -128,15 +115,6 @@ static char sccsid[] = "@(#)fts.c 8.6 (Berkeley) 8/14/94"; # define internal_function /* empty */ #endif -/* Arrange to make lstat calls go through the wrapper function - on systems with an lstat function that does not dereference symlinks - that are specified with a trailing slash. */ -#if ! _LIBC && ! LSTAT_FOLLOWS_SLASHED_SYMLINK -int rpl_lstat (const char *, struct stat *); -# undef lstat -# define lstat(Name, Stat_buf) rpl_lstat(Name, Stat_buf) -#endif - #ifndef __set_errno # define __set_errno(Val) errno = (Val) #endif @@ -164,6 +142,16 @@ static unsigned short int fts_stat (FTS *, FTSENT *, bool) internal_function; static int fts_safe_changedir (FTS *, FTSENT *, int, const char *) internal_function; +#if _LGPL_PACKAGE +static bool enter_dir (FTS *fts, FTSENT *ent) { return true; } +static void leave_dir (FTS *fts, FTSENT *ent) {} +static bool setup_dir (FTS *fts) { return true; } +static void free_dir (FTS *fts) {} +#else +# include "fcntl--.h" +# include "fts-cycle.c" +#endif + #ifndef MAX # define MAX(a,b) ((a) > (b) ? (a) : (b)) #endif @@ -189,124 +177,23 @@ static int fts_safe_changedir (FTS *, FTSENT *, int, const char *) #define BNAMES 2 /* fts_children, names only */ #define BREAD 3 /* fts_read */ -#define HT_INITIAL_SIZE 31 - #if FTS_DEBUG -bool fts_debug = false; +# include +# include # include +bool fts_debug = false; # define Dprintf(x) do { if (fts_debug) printf x; } while (0) #else # define Dprintf(x) #endif -#define ENTER_DIR(Fts, Ent, Tag) \ - do { \ - Dprintf ((" %s-entering: %s\n", Tag, (Ent)->fts_path)); \ - enter_dir (sp, p); \ - } while (0) - #define LEAVE_DIR(Fts, Ent, Tag) \ - do { \ + do \ + { \ Dprintf ((" %s-leaving: %s\n", Tag, (Ent)->fts_path)); \ - leave_dir (sp, p); \ - } while (0) - -/* Use these each of these to map a device/inode pair to an FTSENT. */ -struct Active_dir -{ - dev_t dev; - ino_t ino; - FTSENT *fts_ent; -}; - -static bool -AD_compare (void const *x, void const *y) -{ - struct Active_dir const *ax = x; - struct Active_dir const *ay = y; - return ax->ino == ay->ino - && ax->dev == ay->dev; -} - -static size_t -AD_hash (void const *x, size_t table_size) -{ - struct Active_dir const *ax = x; - return (uintmax_t) ax->ino % table_size; -} - -static void -enter_dir (FTS *fts, FTSENT *ent) -{ - if (fts->active_dir_ht) - { - struct stat const *st = ent->fts_statp; - struct Active_dir *ad = malloc (sizeof (struct Active_dir)); - struct Active_dir *ad_from_table; - - if (ad == NULL) - goto give_up; - - ad->dev = st->st_dev; - ad->ino = st->st_ino; - ad->fts_ent = ent; - - /* See if we've already encountered this directory. - This can happen when following symlinks as well as - with a corrupted directory hierarchy. */ - ad_from_table = hash_insert (fts->active_dir_ht, ad); - - if (ad_from_table == NULL) - { - give_up: - /* Insertion failed due to lack of memory. Free the hash - table and turn off this sort of cycle detection. */ - hash_free (fts->active_dir_ht); - fts->active_dir_ht = NULL; - return; - } - - if (ad_from_table != ad) - { - /* There was an entry with matching dev/inode already in the table. - Record the fact that we've found a cycle. */ - ent->fts_cycle = ad_from_table->fts_ent; - ent->fts_info = FTS_DC; - - /* ad was not inserted, so free it. */ - free (ad); - } - } - else if (fts->cycle_state) - { - if (cycle_check (fts->cycle_state, ent->fts_statp)) - { - /* FIXME: setting fts_cycle like this isn't proper. - To do what the documentation requires, we'd have to - go around the cycle again and find the right entry. - But no callers in coreutils use the fts_cycle member. */ - ent->fts_cycle = ent; - ent->fts_info = FTS_DC; - } - } -} - -static void -leave_dir (FTS *fts, FTSENT *ent) -{ - if (fts->active_dir_ht) - { - struct stat const *st = ent->fts_statp; - struct Active_dir obj; - void *found; - obj.dev = st->st_dev; - obj.ino = st->st_ino; - found = hash_delete (fts->active_dir_ht, &obj); - if (!found) - abort (); - free (found); - } -} + leave_dir (Fts, Ent); \ + } \ + while (false) /* Open the directory DIR if possible, and return a file descriptor. Return -1 and set errno on failure. It doesn't matter @@ -316,10 +203,7 @@ static int internal_function diropen (char const *dir) { - int fd = open (dir, O_RDONLY | O_DIRECTORY); - if (fd < 0) - fd = open (dir, O_WRONLY | O_DIRECTORY); - return fd; + return open (dir, O_RDONLY | O_DIRECTORY | O_NOCTTY | O_NONBLOCK); } FTS * @@ -351,14 +235,17 @@ fts_open (char * const *argv, SET(FTS_NOCHDIR); /* - * Start out with 1K of path space, and enough, in any case, - * to hold the user's paths. + * Start out with 1K of file name space, and enough, in any case, + * to hold the user's file names. */ #ifndef MAXPATHLEN # define MAXPATHLEN 1024 #endif - if (! fts_palloc(sp, MAX(fts_maxarglen(argv), MAXPATHLEN))) - goto mem1; + { + size_t maxarglen = fts_maxarglen(argv); + if (! fts_palloc(sp, MAX(maxarglen, MAXPATHLEN))) + goto mem1; + } /* Allocate/initialize root's parent. */ if ((parent = fts_alloc(sp, "", 0)) == NULL) @@ -367,7 +254,7 @@ fts_open (char * const *argv, /* Allocate/initialize root(s). */ for (root = NULL, nitems = 0; *argv != NULL; ++argv, ++nitems) { - /* Don't allow zero-length paths. */ + /* Don't allow zero-length file names. */ if ((len = strlen(*argv)) == 0) { __set_errno (ENOENT); goto mem3; @@ -413,28 +300,12 @@ fts_open (char * const *argv, goto mem3; sp->fts_cur->fts_link = root; sp->fts_cur->fts_info = FTS_INIT; - - if (ISSET (FTS_TIGHT_CYCLE_CHECK)) - { - sp->active_dir_ht = hash_initialize (HT_INITIAL_SIZE, - NULL, AD_hash, - AD_compare, free); - if (sp->active_dir_ht == NULL) - goto mem3; - sp->cycle_state = malloc (sizeof *sp->cycle_state); - } - else - { - sp->cycle_state = malloc (sizeof *sp->cycle_state); - if (sp->cycle_state == NULL) - goto mem3; - cycle_check_init (sp->cycle_state); - sp->active_dir_ht = NULL; - } + if (! setup_dir (sp)) + goto mem3; /* * If using chdir(2), grab a file descriptor pointing to dot to ensure - * that we can get back here; this could be avoided for some paths, + * that we can get back here; this could be avoided for some file names, * but almost certainly not worth the effort. Slashes, symbolic links, * and ".." are all fairly nasty problems. Note, if we can't get the * descriptor we run anyway, just more slowly. @@ -464,7 +335,7 @@ fts_load (FTS *sp, register FTSENT *p) * actually enter the directory until after the preorder visit, set * the fts_accpath field specially so the chdir gets done to the right * place and the user can access the first node. From fts_open it's - * known that the path will fit. + * known that the file name will fit. */ len = p->fts_pathlen = p->fts_namelen; memmove(sp->fts_path, p->fts_name, len + 1); @@ -497,7 +368,7 @@ fts_close (FTS *sp) free(p); } - /* Free up child linked list, sort array, path buffer. */ + /* Free up child linked list, sort array, file name buffer. */ if (sp->fts_child) fts_lfree(sp->fts_child); if (sp->fts_array) @@ -511,11 +382,7 @@ fts_close (FTS *sp) (void)close(sp->fts_rfd); } - /* Free any memory used for cycle detection. */ - if (sp->active_dir_ht) - hash_free (sp->active_dir_ht); - if (sp->cycle_state) - free (sp->cycle_state); + free_dir (sp); /* Free up the stream pointer. */ free(sp); @@ -530,8 +397,8 @@ fts_close (FTS *sp) } /* - * Special case of "/" at the end of the path so that slashes aren't - * appended which would cause paths to be written as "....//foo". + * Special case of "/" at the end of the file name so that slashes aren't + * appended which would cause file names to be written as "....//foo". */ #define NAPPEND(p) \ (p->fts_path[p->fts_pathlen - 1] == '/' \ @@ -580,9 +447,7 @@ fts_read (register FTS *sp) } else p->fts_flags |= FTS_SYMFOLLOW; } - if (p->fts_info == FTS_D) - ENTER_DIR (sp, p, "7"); - return (p); + goto check_for_dir; } /* Directory in pre-order. */ @@ -653,17 +518,17 @@ next: tmp = p; /* * If reached the top, return to the original directory (or - * the root of the tree), and load the paths for the next root. + * the root of the tree), and load the file names for the next + * root. */ if (p->fts_level == FTS_ROOTLEVEL) { if (FCHDIR(sp, sp->fts_rfd)) { SET(FTS_STOP); + sp->fts_cur = p; return (NULL); } fts_load(sp, p); - if (p->fts_info == FTS_D) - ENTER_DIR (sp, p, "8"); - return (sp->fts_cur = p); + goto check_for_dir; } /* @@ -688,9 +553,18 @@ next: tmp = p; name: t = sp->fts_path + NAPPEND(p->fts_parent); *t++ = '/'; memmove(t, p->fts_name, p->fts_namelen + 1); +check_for_dir: + sp->fts_cur = p; if (p->fts_info == FTS_D) - ENTER_DIR (sp, p, "9"); - return (sp->fts_cur = p); + { + Dprintf ((" %s-entering: %s\n", sp, p->fts_path)); + if (! enter_dir (sp, p)) + { + __set_errno (ENOMEM); + return NULL; + } + } + return p; } /* Move up to the parent node. */ @@ -707,7 +581,7 @@ name: t = sp->fts_path + NAPPEND(p->fts_parent); return (sp->fts_cur = NULL); } - /* NUL terminate the pathname. */ + /* NUL terminate the file name. */ sp->fts_path[p->fts_pathlen] = '\0'; /* @@ -807,8 +681,8 @@ fts_children (register FTS *sp, int instr) instr = BCHILD; /* - * If using chdir on a relative path and called BEFORE fts_read does - * its chdir to the root of a traversal, we can lose -- we need to + * If using chdir on a relative file name and called BEFORE fts_read + * does its chdir to the root of a traversal, we can lose -- we need to * chdir into the subdirectory, and we don't know where the current * directory is, so we can't get back so that the upcoming chdir by * fts_read will work. @@ -821,7 +695,9 @@ fts_children (register FTS *sp, int instr) return (sp->fts_child = NULL); sp->fts_child = fts_build(sp, instr); if (fchdir(fd)) { + int saved_errno = errno; (void)close(fd); + __set_errno (saved_errno); return (NULL); } (void)close(fd); @@ -875,7 +751,7 @@ fts_build (register FTS *sp, int type) else oflag = DTF_HIDEW|DTF_NODUP|DTF_REWIND; #else -# define __opendir2(path, flag) opendir(path) +# define __opendir2(file, flag) opendir(file) #endif if ((dirp = __opendir2(cur->fts_accpath, oflag)) == NULL) { if (type == BREAD) { @@ -909,7 +785,7 @@ fts_build (register FTS *sp, int type) * but set a flag so we don't chdir after the post-order visit. * We won't be able to stat anything, but we can still return the * names themselves. Note, that since fts_read won't be able to - * chdir into the directory, it will have to return different path + * chdir into the directory, it will have to return different file * names than before, i.e. "a/b" instead of "b". Since the node * has already been visited in pre-order, have to wait until the * post-order visit to return the error. There is a special case @@ -926,7 +802,7 @@ fts_build (register FTS *sp, int type) cur->fts_flags |= FTS_DONTCHDIR; descend = false; cderrno = errno; - (void)closedir(dirp); + closedir(dirp); dirp = NULL; } else descend = true; @@ -935,13 +811,13 @@ fts_build (register FTS *sp, int type) /* * Figure out the max file name length that can be stored in the - * current path -- the inner loop allocates more path as necessary. + * current buffer -- the inner loop allocates more space as necessary. * We really wouldn't have to do the maxlen calculations here, we - * could do them in fts_read before returning the path, but it's a + * could do them in fts_read before returning the name, but it's a * lot easier here since the length is part of the dirent structure. * * If not changing directories set a pointer so that can just append - * each new name into the path. + * each new component into the file name. */ len = NAPPEND(cur); if (ISSET(FTS_NOCHDIR)) { @@ -968,7 +844,7 @@ fts_build (register FTS *sp, int type) oldaddr = sp->fts_path; if (! fts_palloc(sp, NAMLEN (dp) + len + 1)) { /* - * No more memory for path or structures. Save + * No more memory. Save * errno, free up the current structure and the * structures already allocated. */ @@ -976,7 +852,7 @@ mem1: saved_errno = errno; if (p) free(p); fts_lfree(head); - (void)closedir(dirp); + closedir(dirp); cur->fts_info = FTS_ERR; SET(FTS_STOP); __set_errno (saved_errno); @@ -995,13 +871,13 @@ mem1: saved_errno = errno; if (new_len < len) { /* * In the unlikely even that we would end up - * with a path longer than SIZE_MAX, free up + * with a file name longer than SIZE_MAX, free up * the current structure and the structures already * allocated, then error out with ENAMETOOLONG. */ free(p); fts_lfree(head); - (void)closedir(dirp); + closedir(dirp); cur->fts_info = FTS_ERR; SET(FTS_STOP); __set_errno (ENAMETOOLONG); @@ -1043,11 +919,9 @@ mem1: saved_errno = errno; p->fts_info = fts_stat(sp, p, false); /* Decrement link count if applicable. */ - if (nlinks > 0 - && (TYPE_SIGNED (nlink_t) || nostat) - && (p->fts_info == FTS_D || + if (nlinks > 0 && (p->fts_info == FTS_D || p->fts_info == FTS_DC || p->fts_info == FTS_DOT)) - --nlinks; + nlinks -= nostat; } /* We walk in directory order so "ls -f" doesn't get upset. */ @@ -1061,17 +935,17 @@ mem1: saved_errno = errno; ++nitems; } if (dirp) - (void)closedir(dirp); + closedir(dirp); /* - * If realloc() changed the address of the path, adjust the + * If realloc() changed the address of the file name, adjust the * addresses for the rest of the tree and the dir list. */ if (doadjust) fts_padjust(sp, head); /* - * If not changing directories, reset the path back to original + * If not changing directories, reset the file name back to original * state. */ if (ISSET(FTS_NOCHDIR)) { @@ -1083,7 +957,7 @@ mem1: saved_errno = errno; /* * If descended after called from fts_children or after called from * fts_read and nothing found, get back. At the root level we use - * the saved fd; if one of fts_open()'s arguments is a relative path + * the saved fd; if one of fts_open()'s arguments is a relative name * to an empty directory, we wind up here with no other way back. If * can't get back, we're done. */ @@ -1152,7 +1026,7 @@ fts_cross_check (FTS const *sp) struct Active_dir ad; ad.ino = t->fts_statp->st_ino; ad.dev = t->fts_statp->st_dev; - if ( ! hash_lookup (sp->active_dir_ht, &ad)) + if ( ! hash_lookup (sp->fts_cycle.ht, &ad)) printf ("ERROR: active dir, %s, not in tree\n", t->fts_path); } @@ -1163,8 +1037,8 @@ fts_cross_check (FTS const *sp) || ent->fts_info == FTS_D)) { struct Active_dir *ad; - for (ad = hash_get_first (sp->active_dir_ht); ad != NULL; - ad = hash_get_next (sp->active_dir_ht, ad)) + for (ad = hash_get_first (sp->fts_cycle.ht); ad != NULL; + ad = hash_get_next (sp->fts_cycle.ht, ad)) { find_matching_ancestor (ent, ad); } @@ -1196,7 +1070,8 @@ fts_stat(FTS *sp, register FTSENT *p, bool follow) if (ISSET(FTS_LOGICAL) || follow) { if (stat(p->fts_accpath, sbp)) { saved_errno = errno; - if (!lstat(p->fts_accpath, sbp)) { + if (errno == ENOENT + && lstat(p->fts_accpath, sbp) == 0) { __set_errno (0); return (FTS_SLNONE); } @@ -1212,6 +1087,28 @@ err: memset(sbp, 0, sizeof(struct stat)); if (S_ISDIR(sbp->st_mode)) { if (ISDOT(p->fts_name)) return (FTS_DOT); + +#if _LGPL_PACKAGE + { + /* + * Cycle detection is done by brute force when the directory + * is first encountered. If the tree gets deep enough or the + * number of symbolic links to directories is high enough, + * something faster might be worthwhile. + */ + FTSENT *t; + + for (t = p->fts_parent; + t->fts_level >= FTS_ROOTLEVEL; t = t->fts_parent) + if (sbp->st_ino == t->fts_statp->st_ino + && sbp->st_dev == t->fts_statp->st_dev) + { + p->fts_cycle = t; + return (FTS_DC); + } + } +#endif + return (FTS_D); } if (S_ISLNK(sbp->st_mode)) @@ -1328,10 +1225,11 @@ fts_lfree (register FTSENT *head) } /* - * Allow essentially unlimited paths; find, rm, ls should all work on any tree. - * Most systems will allow creation of paths much longer than MAXPATHLEN, even - * though the kernel won't resolve them. Add the size (not just what's needed) - * plus 256 bytes so don't realloc the path 2 bytes at a time. + * Allow essentially unlimited file name lengths; find, rm, ls should + * all work on any tree. Most systems will allow creation of file + * names much longer than MAXPATHLEN, even though the kernel won't + * resolve them. Add the size (not just what's needed) plus 256 bytes + * so don't realloc the file name 2 bytes at a time. */ static bool internal_function @@ -1364,8 +1262,8 @@ fts_palloc (FTS *sp, size_t more) } /* - * When the path is realloc'd, have to fix all of the pointers in structures - * already returned. + * When the file name is realloc'd, have to fix all of the pointers in + * structures already returned. */ static void internal_function @@ -1405,13 +1303,13 @@ fts_maxarglen (char * const *argv) } /* - * Change to dir specified by fd or path without getting + * Change to dir specified by fd or file name without getting * tricked by someone changing the world out from underneath us. * Assumes p->fts_statp->st_dev and p->fts_statp->st_ino are filled in. */ static int internal_function -fts_safe_changedir (FTS *sp, FTSENT *p, int fd, char const *path) +fts_safe_changedir (FTS *sp, FTSENT *p, int fd, char const *dir) { int ret, oerrno, newfd; struct stat sb; @@ -1419,7 +1317,7 @@ fts_safe_changedir (FTS *sp, FTSENT *p, int fd, char const *path) newfd = fd; if (ISSET(FTS_NOCHDIR)) return (0); - if (fd < 0 && (newfd = fd_safer (diropen (path))) < 0) + if (fd < 0 && (newfd = diropen (dir)) < 0) return (-1); if (fstat(newfd, &sb)) { ret = -1;