X-Git-Url: http://erislabs.net/gitweb/?a=blobdiff_plain;f=lib%2Ffts.c;h=d4f7db21cb7a051582869e1c638bf52dad98d4ae;hb=671c9011cb6944a63f0d15f60252c31bf0ee8e9b;hp=fa4d7576fd1e6ee9530d9dba81d79e6c1d6bc801;hpb=a98bbee4c1388c33841d11b4bdc5d0a600a9deda;p=gnulib.git
diff --git a/lib/fts.c b/lib/fts.c
index fa4d7576f..d4f7db21c 100644
--- a/lib/fts.c
+++ b/lib/fts.c
@@ -1,11 +1,11 @@
/* Traverse a file hierarchy.
- Copyright (C) 2004, 2005, 2006 Free Software Foundation, Inc.
+ Copyright (C) 2004, 2005, 2006, 2007, 2008 Free Software Foundation, Inc.
- This program is free software; you can redistribute it and/or modify
+ 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
- the Free Software Foundation; either version 2, or (at your option)
- any later version.
+ the Free Software Foundation; either version 3 of the License, or
+ (at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
@@ -13,8 +13,7 @@
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
- along with this program; if not, write to the Free Software Foundation,
- Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
+ along with this program. If not, see . */
/*-
* Copyright (c) 1990, 1993, 1994
@@ -92,6 +91,29 @@ static char sccsid[] = "@(#)fts.c 8.6 (Berkeley) 8/14/94";
# define DT_MUST_BE(d, t) false
#endif
+enum
+{
+ NOT_AN_INODE_NUMBER = 0
+};
+
+#ifdef D_INO_IN_DIRENT
+# define D_INO(dp) (dp)->d_ino
+#else
+/* Some systems don't have inodes, so fake them to avoid lots of ifdefs. */
+# define D_INO(dp) NOT_AN_INODE_NUMBER
+#endif
+
+/* If there are more than this many entries in a directory,
+ and the conditions mentioned below are satisfied, then sort
+ the entries on inode number before any further processing. */
+#ifndef FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD
+# define FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD 10000
+#endif
+enum
+{
+ _FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD = FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD
+};
+
enum Fts_stat
{
FTS_NO_STAT_REQUIRED = 1,
@@ -121,7 +143,7 @@ enum Fts_stat
#endif
#ifndef __attribute__
-# if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 8) || __STRICT_ANSI__
+# if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 8)
# define __attribute__(x) /* empty */
# endif
#endif
@@ -138,6 +160,18 @@ enum Fts_stat
# define HAVE_OPENAT_SUPPORT 0
#endif
+#ifdef NDEBUG
+# define fts_assert(expr) ((void) 0)
+#else
+# define fts_assert(expr) \
+ do \
+ { \
+ if (!(expr)) \
+ abort (); \
+ } \
+ while (false)
+#endif
+
static FTSENT *fts_alloc (FTS *, const char *, size_t) internal_function;
static FTSENT *fts_build (FTS *, int) internal_function;
static void fts_lfree (FTSENT *) internal_function;
@@ -150,13 +184,13 @@ 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
+#if GNULIB_FTS
+# include "fts-cycle.c"
+#else
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 "fts-cycle.c"
#endif
#ifndef MAX
@@ -236,8 +270,7 @@ fd_ring_clear (I_ring *fd_ring)
static void
fts_set_stat_required (FTSENT *p, bool required)
{
- if (p->fts_info != FTS_NSOK)
- abort ();
+ fts_assert (p->fts_info == FTS_NSOK);
p->fts_statp->st_size = (required
? FTS_STAT_REQUIRED
: FTS_NO_STAT_REQUIRED);
@@ -274,8 +307,7 @@ internal_function
cwd_advance_fd (FTS *sp, int fd, bool chdir_down_one)
{
int old = sp->fts_cwd_fd;
- if (old == fd && old != AT_FDCWD)
- abort ();
+ fts_assert (old != fd || old == AT_FDCWD);
if (chdir_down_one)
{
@@ -675,7 +707,7 @@ fts_read (register FTS *sp)
/* If fts_build's call to fts_safe_changedir failed
because it was not able to fchdir into a
subdirectory, tell the caller. */
- if (p->fts_errno)
+ if (p->fts_errno && p->fts_info != FTS_DNR)
p->fts_info = FTS_ERR;
LEAVE_DIR (sp, p, "2");
return (p);
@@ -688,6 +720,7 @@ fts_read (register FTS *sp)
/* Move to the next node on this level. */
next: tmp = p;
if ((p = p->fts_link) != NULL) {
+ sp->fts_cur = p;
free(tmp);
/*
@@ -698,7 +731,6 @@ next: tmp = p;
if (p->fts_level == FTS_ROOTLEVEL) {
if (RESTORE_INITIAL_CWD(sp)) {
SET(FTS_STOP);
- sp->fts_cur = p;
return (NULL);
}
fts_load(sp, p);
@@ -728,22 +760,15 @@ 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_NSOK)
{
- enum Fts_stat need_stat = p->fts_statp->st_size;
- switch (need_stat)
- {
- case FTS_STAT_REQUIRED:
- p->fts_info = fts_stat(sp, p, false);
- break;
- case FTS_NO_STAT_REQUIRED:
- break;
- default:
- abort ();
- }
+ if (p->fts_statp->st_size == FTS_STAT_REQUIRED)
+ p->fts_info = fts_stat(sp, p, false);
+ else
+ fts_assert (p->fts_statp->st_size == FTS_NO_STAT_REQUIRED);
}
- sp->fts_cur = p;
if (p->fts_info == FTS_D)
{
/* Now that P->fts_statp is guaranteed to be valid,
@@ -763,6 +788,7 @@ check_for_dir:
/* Move up to the parent node. */
p = tmp->fts_parent;
+ sp->fts_cur = p;
free(tmp);
if (p->fts_level == FTS_ROOTPARENTLEVEL) {
@@ -775,8 +801,7 @@ check_for_dir:
return (sp->fts_cur = NULL);
}
- if (p->fts_info == FTS_NSOK)
- abort ();
+ fts_assert (p->fts_info != FTS_NSOK);
/* NUL terminate the file name. */
sp->fts_path[p->fts_pathlen] = '\0';
@@ -809,7 +834,6 @@ check_for_dir:
p->fts_info = p->fts_errno ? FTS_ERR : FTS_DP;
if (p->fts_errno == 0)
LEAVE_DIR (sp, p, "3");
- sp->fts_cur = p;
return ISSET(FTS_STOP) ? NULL : p;
}
@@ -910,6 +934,63 @@ fts_children (register FTS *sp, int instr)
return (sp->fts_child);
}
+#if defined __linux__ \
+ && HAVE_SYS_VFS_H && HAVE_FSTATFS && HAVE_STRUCT_STATFS_F_TYPE
+
+#include
+
+/* Linux-specific constants from coreutils' src/fs.h */
+# define S_MAGIC_TMPFS 0x1021994
+# define S_MAGIC_NFS 0x6969
+
+/* Return false if it is easy to determine the file system type of
+ the directory on which DIR_FD is open, and sorting dirents on
+ inode numbers is known not to improve traversal performance with
+ that type of file system. Otherwise, return true. */
+static bool
+dirent_inode_sort_may_be_useful (int dir_fd)
+{
+ /* Skip the sort only if we can determine efficiently
+ that skipping it is the right thing to do.
+ The cost of performing an unnecessary sort is negligible,
+ while the cost of *not* performing it can be O(N^2) with
+ a very large constant. */
+ struct statfs fs_buf;
+
+ /* If fstatfs fails, assume sorting would be useful. */
+ if (fstatfs (dir_fd, &fs_buf) != 0)
+ return true;
+
+ /* FIXME: what about when f_type is not an integral type?
+ deal with that if/when it's encountered. */
+ switch (fs_buf.f_type)
+ {
+ case S_MAGIC_TMPFS:
+ case S_MAGIC_NFS:
+ /* On a file system of any of these types, sorting
+ is unnecessary, and hence wasteful. */
+ return false;
+
+ default:
+ return true;
+ }
+}
+#else
+static bool dirent_inode_sort_may_be_useful (int dir_fd) { return true; }
+#endif
+
+/* A comparison function to sort on increasing inode number.
+ For some file system types, sorting either way makes a huge
+ performance difference for a directory with very many entries,
+ but sorting on increasing values is slightly better than sorting
+ on decreasing values. The difference is in the 5% range. */
+static int
+fts_compare_ino (struct _ftsent const **a, struct _ftsent const **b)
+{
+ return (a[0]->fts_statp->st_ino < b[0]->fts_statp->st_ino ? -1
+ : b[0]->fts_statp->st_ino < a[0]->fts_statp->st_ino ? 1 : 0);
+}
+
/*
* This is the tricky part -- do not casually change *anything* in here. The
* idea is to build the linked list of entries that are used by fts_children
@@ -1089,7 +1170,7 @@ mem1: saved_errno = errno;
new_len = len + _D_EXACT_NAMLEN (dp);
if (new_len < len) {
/*
- * In the unlikely even that we would end up
+ * In the unlikely event that we would end up
* with a file name longer than SIZE_MAX, free up
* the current structure and the structures already
* allocated, then error out with ENAMETOOLONG.
@@ -1110,6 +1191,9 @@ mem1: saved_errno = errno;
if (dp->d_type == DT_WHT)
p->fts_flags |= FTS_ISW;
#endif
+ /* Store dirent.d_ino, in case we need to sort
+ entries before processing them. */
+ p->fts_statp->st_ino = D_INO (dp);
/* Build a file name for fts_stat to stat. */
if (ISSET(FTS_NOCHDIR)) {
@@ -1205,6 +1289,19 @@ mem1: saved_errno = errno;
return (NULL);
}
+ /* If there are many entries, no sorting function has been specified,
+ and this file system is of a type that may be slow with a large
+ number of entries, then sort the directory entries on increasing
+ inode numbers. */
+ if (nitems > _FTS_INODE_SORT_DIR_ENTRIES_THRESHOLD
+ && !sp->fts_compar
+ && ISSET (FTS_CWDFD)
+ && dirent_inode_sort_may_be_useful (sp->fts_cwd_fd)) {
+ sp->fts_compar = fts_compare_ino;
+ head = fts_sort (sp, head, nitems);
+ sp->fts_compar = NULL;
+ }
+
/* Sort the entries. */
if (sp->fts_compar && nitems > 1)
head = fts_sort(sp, head, nitems);
@@ -1345,7 +1442,7 @@ fd_ring_check (FTS const *sp)
error (0, errno, "parent: %s", c2);
free (cwd);
free (c2);
- abort ();
+ fts_assert (0);
}
close (cwd_fd);
cwd_fd = parent_fd;
@@ -1403,7 +1500,7 @@ err: memset(sbp, 0, sizeof(struct stat));
return (p->fts_level == FTS_ROOTLEVEL ? FTS_D : FTS_DOT);
}
-#if _LGPL_PACKAGE
+#if !GNULIB_FTS
{
/*
* Cycle detection is done by brute force when the directory
@@ -1474,7 +1571,7 @@ fts_sort (FTS *sp, FTSENT *head, register size_t nitems)
* 40 so don't realloc one entry at a time.
*/
if (nitems > sp->fts_nitems) {
- struct _ftsent **a;
+ FTSENT **a;
sp->fts_nitems = nitems + 40;
if (SIZE_MAX / sizeof *a < sp->fts_nitems