From d951286f645cc1d6f719c0c715620fc395c049d4 Mon Sep 17 00:00:00 2001 From: Ulrich Drepper Date: Fri, 30 May 1997 01:37:13 +0000 Subject: Update. * io/Makefile (test-srcs): Add ftwtest. (distribute): Add ftwtest-sh. (tests): Call ftwtest-sh for this goal. * io/ftwtest-sh: New file. Sets up test environment, calls test program and compares the result. * io/ftwtest.c: Test program for ftw. * misc/search.h: Add comments. Declare tdestroy. * misc/tsearch.c (tdestroy): New function. --- .cvsignore | 1 + ChangeLog | 9 +++ io/Makefile | 6 ++ io/ftw.c | 187 ++++++++++++++++++++++++++++++++++++++++----------------- io/ftw.h | 4 +- io/ftwtest-sh | 84 ++++++++++++++++++++++++++ io/ftwtest.c | 71 ++++++++++++++++++++++ misc/search.h | 21 ++++++- misc/tsearch.c | 35 ++++++++++- 9 files changed, 359 insertions(+), 59 deletions(-) create mode 100644 io/ftwtest-sh create mode 100644 io/ftwtest.c diff --git a/.cvsignore b/.cvsignore index 1378938989..e724ae9d55 100644 --- a/.cvsignore +++ b/.cvsignore @@ -14,6 +14,7 @@ gpl2lgpl.sed distinfo distinfo +test-include analysis docs diff --git a/ChangeLog b/ChangeLog index 5c3cf9de8a..199ee31f9a 100644 --- a/ChangeLog +++ b/ChangeLog @@ -2,6 +2,15 @@ * io/ftw.c: Complete rewrite. Add implementation of `nftw'. * io/ftw.h: Update for new implementation and XPG4.2. + * io/Makefile (test-srcs): Add ftwtest. + (distribute): Add ftwtest-sh. + (tests): Call ftwtest-sh for this goal. + * io/ftwtest-sh: New file. Sets up test environment, calls test + program and compares the result. + * io/ftwtest.c: Test program for ftw. + + * misc/search.h: Add comments. Declare tdestroy. + * misc/tsearch.c (tdestroy): New function. * login/Makefile: Update for UTMP daemon implementation. diff --git a/io/Makefile b/io/Makefile index f1efd21e87..d199f9110b 100644 --- a/io/Makefile +++ b/io/Makefile @@ -51,9 +51,15 @@ routines := \ static-only-routines = stat fstat lstat mknod others := pwd +test-srcs := ftwtest tests := test-utime +distribute := ftwtest-sh + include ../Rules CFLAGS-fts.c = -Wno-uninitialized CFLAGS-ftw.c = -Wno-uninitialized + +tests: $(objpfx)ftwtest + $(SHELL) -e ftwtest-sh $(common-objpfx) $< diff --git a/io/ftw.c b/io/ftw.c index e20ad231d3..7367f9733e 100644 --- a/io/ftw.c +++ b/io/ftw.c @@ -38,24 +38,44 @@ struct dir_data char *content; }; +struct known_object +{ + dev_t dev; + ino_t ino; +}; + struct ftw_data { + /* Array with pointers to open directory streams. */ struct dir_data **dirstreams; size_t actdir; size_t maxdir; + /* Buffer containing name of currently processed object. */ char *dirbuf; size_t dirbufsize; + + /* Passed as fourth argument to `nftw' callback. The `base' member + tracks the content of the `dirbuf'. */ struct FTW ftw; + /* Flags passed to `nftw' function. 0 for `ftw'. */ int flags; + /* Conversion array for flag values. It is the identity mapping for + `nftw' calls, otherwise it maps the values to those know by + `ftw'. */ int *cvt_arr; - __nftw_func_t func; - struct stat st; + /* Callback function. We always use the `nftw' form. */ + __nftw_func_t func; + /* Device of starting point. Needed for FTW_MOUNT. */ dev_t dev; + + /* Data structure for keeping fingerprints of already processed + object. This is needed when not using FTW_PHYS. */ + void *known_objects; }; @@ -74,7 +94,36 @@ static int ftw_arr[] = /* Forward declarations of local functions. */ -static int ftw_dir (struct ftw_data *data); +static int ftw_dir (struct ftw_data *data, struct stat *st); + + +static int +object_compare (const void *p1, const void *p2) +{ + /* We don't need a sophisticated and useful comparison. We are only + interested in equality. */ + return memcmp (p1, p2, sizeof (struct known_object)); +} + + +static inline int +add_object (struct ftw_data *data, struct stat *st) +{ + struct known_object *newp = malloc (sizeof (struct known_object)); + if (newp == NULL) + return -1; + newp->dev = st->st_dev; + newp->ino = st->st_ino; + return __tsearch (newp, &data->known_objects, object_compare) ? 0 : -1; +} + + +static inline int +find_object (struct ftw_data *data, struct stat *st) +{ + struct known_object obj = { dev: st->st_dev, ino: st->st_ino }; + return __tfind (&obj, &data->known_objects, object_compare) != NULL; +} static inline int @@ -170,6 +219,7 @@ static inline int process_entry (struct ftw_data *data, struct dir_data *dir, const char *name, size_t namlen) { + struct stat st; int result = 0; int flag; @@ -193,65 +243,72 @@ process_entry (struct ftw_data *data, struct dir_data *dir, const char *name, memcpy (data->dirbuf + data->ftw.base, name, namlen); data->dirbuf[data->ftw.base + namlen] = '\0'; - if (((data->flags & FTW_PHYS) ? lstat : stat) (data->dirbuf, &data->st) < 0) + if (((data->flags & FTW_PHYS) ? lstat : stat) (data->dirbuf, &st) < 0) { if (errno != EACCES && errno != ENOENT) result = -1; else if (!(data->flags & FTW_PHYS) - && lstat (data->dirbuf, &data->st) == 0 - && S_ISLNK (data->st.st_mode)) + && lstat (data->dirbuf, &st) == 0 + && S_ISLNK (st.st_mode)) flag = FTW_SLN; else flag = FTW_NS; } else { - if (S_ISDIR (data->st.st_mode)) + if (S_ISDIR (st.st_mode)) flag = FTW_D; - else if (S_ISLNK (data->st.st_mode)) + else if (S_ISLNK (st.st_mode)) flag = FTW_SL; else flag = FTW_F; } if (result == 0 - && (!(data->flags & FTW_MOUNT) || data->st.st_dev == data->dev)) + && (!(data->flags & FTW_MOUNT) || flag == FTW_NS + || st.st_dev == data->dev)) { - if (flag == FTW_D) + if ((data->flags & FTW_PHYS) || flag == FTW_NS + || (!find_object (data, &st) + /* Remember the object. */ + && (result = add_object (data, &st)) == 0)) { - result = ftw_dir (data); - - if (result == 0 && (data->flags & FTW_CHDIR)) + if (flag == FTW_D) { - /* Change back to current directory. */ - int done = 0; - if (dir->stream != NULL) - if (fchdir (dirfd (dir->stream)) == 0) - done = 1; + result = ftw_dir (data, &st); - if (!done) + if (result == 0 && (data->flags & FTW_CHDIR)) { - if (data->ftw.base == 1) - { - if (chdir ("/") < 0) - result = -1; - } - else - { - /* Please note that we overwrite a slash. */ - data->dirbuf[data->ftw.base - 1] = '\0'; + /* Change back to current directory. */ + int done = 0; + if (dir->stream != NULL) + if (fchdir (dirfd (dir->stream)) == 0) + done = 1; - if (chdir (data->dirbuf) < 0) - result = -1; + if (!done) + { + if (data->ftw.base == 1) + { + if (chdir ("/") < 0) + result = -1; + } else - data->dirbuf[data->ftw.base - 1] = '/'; + { + /* Please note that we overwrite a slash. */ + data->dirbuf[data->ftw.base - 1] = '\0'; + + if (chdir (data->dirbuf) < 0) + result = -1; + + data->dirbuf[data->ftw.base - 1] = '/'; + } } } } + else + result = (*data->func) (data->dirbuf, &st, data->cvt_arr[flag], + &data->ftw); } - else - result = (*data->func) (data->dirbuf, &data->st, data->cvt_arr[flag], - &data->ftw); } return result; @@ -259,28 +316,34 @@ process_entry (struct ftw_data *data, struct dir_data *dir, const char *name, static int -ftw_dir (struct ftw_data *data) +ftw_dir (struct ftw_data *data, struct stat *st) { struct dir_data dir; struct dirent *d; int previous_base = data->ftw.base; - int result = 0; + int result; char *startp; + /* Open the stream for this directory. This might require that + another stream has to be closed. */ + result = open_dir_stream (data, &dir); + if (result != 0) + { + if (errno == EACCES) + /* We cannot read the directory. Signal this with a special flag. */ + result = (*data->func) (data->dirbuf, st, FTW_DNR, &data->ftw); + + return result; + } + /* First, report the directory (if not depth-first). */ if (!(data->flags & FTW_DEPTH)) { - result = (*data->func) (data->dirbuf, &data->st, FTW_D, &data->ftw); + result = (*data->func) (data->dirbuf, st, FTW_D, &data->ftw); if (result != 0) return result; } - /* Open the stream for this directory. This might require that - another stream has to be closed. */ - result = open_dir_stream (data, &dir); - if (result != 0) - return result; - /* If necessary, change to this directory. */ if (data->flags & FTW_CHDIR) { @@ -361,12 +424,13 @@ ftw_dir (struct ftw_data *data) } /* Prepare the return, revert the `struct FTW' information. */ + data->dirbuf[data->ftw.base - 1] = '\0'; --data->ftw.level; data->ftw.base = previous_base; /* Finally, if we process depth-first report the directory. */ if (result == 0 && (data->flags & FTW_DEPTH)) - result = (*data->func) (data->dirbuf, &data->st, FTW_DP, &data->ftw); + result = (*data->func) (data->dirbuf, st, FTW_DP, &data->ftw); return result; } @@ -377,9 +441,10 @@ ftw_startup (const char *dir, int is_nftw, void *func, int descriptors, int flags) { struct ftw_data data; + struct stat st; int result = 0; int save_err; - char *cwd; + char *cwd = NULL; char *cp; /* First make sure the parameters are reasonable. */ @@ -399,7 +464,7 @@ ftw_startup (const char *dir, int is_nftw, void *func, int descriptors, data.dirbuf = (char *) malloc (data.dirbufsize); if (data.dirbuf == NULL) return -1; - cp = stpcpy (data.dirbuf, dir); + cp = __stpcpy (data.dirbuf, dir); /* Strip trailing slashes. */ while (cp > data.dirbuf + 1 && cp[-1] == '/') --cp; @@ -426,6 +491,9 @@ ftw_startup (const char *dir, int is_nftw, void *func, int descriptors, to reduce the value range before calling a `ftw' callback. */ data.cvt_arr = is_nftw ? nftw_arr : ftw_arr; + /* No object known so far. */ + data.known_objects = NULL; + /* Now go to the directory containing the initial file/directory. */ if ((flags & FTW_CHDIR) && data.ftw.base > 0) { @@ -453,14 +521,14 @@ ftw_startup (const char *dir, int is_nftw, void *func, int descriptors, /* Get stat info for start directory. */ if (result == 0) - if (((flags & FTW_PHYS) ? lstat : stat) (data.dirbuf, &data.st) < 0) + if (((flags & FTW_PHYS) ? lstat : stat) (data.dirbuf, &st) < 0) { if (errno == EACCES) - result = (*data.func) (data.dirbuf, &data.st, FTW_NS, &data.ftw); + result = (*data.func) (data.dirbuf, &st, FTW_NS, &data.ftw); else if (!(flags & FTW_PHYS) && errno == ENOENT - && lstat (dir, &data.st) == 0 && S_ISLNK (data.st.st_mode)) - result = (*data.func) (data.dirbuf, &data.st, data.cvt_arr[FTW_SLN], + && lstat (dir, &st) == 0 && S_ISLNK (st.st_mode)) + result = (*data.func) (data.dirbuf, &st, data.cvt_arr[FTW_SLN], &data.ftw); else /* No need to call the callback since we cannot say anything @@ -469,16 +537,24 @@ ftw_startup (const char *dir, int is_nftw, void *func, int descriptors, } else { - if (S_ISDIR (data.st.st_mode)) + if (S_ISDIR (st.st_mode)) { - data.dev = data.st.st_dev; - result = ftw_dir (&data); + /* Remember the device of the initial directory in case + FTW_MOUNT is given. */ + data.dev = st.st_dev; + + /* We know this directory now. */ + if (!(flags & FTW_PHYS)) + result = add_object (&data, &st); + + if (result == 0) + result = ftw_dir (&data, &st); } else { - int flag = S_ISLNK (data.st.st_mode) ? FTW_SL : FTW_F; + int flag = S_ISLNK (st.st_mode) ? FTW_SL : FTW_F; - result = (*data.func) (data.dirbuf, &data.st, data.cvt_arr[flag], + result = (*data.func) (data.dirbuf, &st, data.cvt_arr[flag], &data.ftw); } } @@ -494,6 +570,7 @@ ftw_startup (const char *dir, int is_nftw, void *func, int descriptors, /* Free all memory. */ save_err = errno; + __tdestroy (data.known_objects, free); free (data.dirbuf); __set_errno (save_err); diff --git a/io/ftw.h b/io/ftw.h index 70fb9e22fd..d283e6937e 100644 --- a/io/ftw.h +++ b/io/ftw.h @@ -44,11 +44,13 @@ enum FTW_NS, /* Unstatable file. */ #define FTW_NS FTW_NS -#ifdef __USE_XOPEN_EXTENDED +#if defined __USE_BSD || defined __USE_XOPEN_EXTENDED FTW_SL, /* Symbolic link. */ # define FTW_SL FTW_SL +#endif +#ifdef __USE_XOPEN_EXTENDED /* These flags are only passed from the `nftw' function. */ FTW_DP, /* Directory, all subdirs have been visited. */ # define FTW_DP FTW_DP diff --git a/io/ftwtest-sh b/io/ftwtest-sh new file mode 100644 index 0000000000..1c7c3984d8 --- /dev/null +++ b/io/ftwtest-sh @@ -0,0 +1,84 @@ +#! /bin/sh + +# The common objpfx, used to find libraries and the dynamic loader. +objpfx=$1 + +# We expect one parameter which is the test program. This must understand +# a number options: +# --phys use the FTW_PHYS flag +# --chdir use the FTW_CHDIR and print the current directory in the +# callback +# --depth use the FTW_DEPTH flag +testprogram=$2 + + +# First create our scenario: +tmp=${TMPDIR:-/tmp} +tmpdir=$tmp/ftwtest.d + +trap 'rm -fr $tmpdir $testout' 1 2 3 15 + +if test -d $tmpdir; then + chmod -R a+x $tmpdir + rm -fr $tmpdir +fi +mkdir $tmpdir +mkdir $tmpdir/foo +mkdir $tmpdir/bar +echo > $tmpdir/baz +mkdir $tmpdir/foo/lvl1 +echo > $tmpdir/foo/lvl1/file@1 +mkdir $tmpdir/foo/lvl1/lvl2 +echo > $tmpdir/foo/lvl1/lvl2/file@2 +mkdir $tmpdir/foo/lvl1/lvl2/lvl3 +echo > $tmpdir/foo/lvl1/lvl2/lvl3/file@3 +ln -s $tmpdir $tmpdir/foo/lvl1/lvl2/lvl3/link@3 +ln -s $tmpdir/foo/lvl1/lvl2 $tmpdir/foo/lvl1/lvl2/link@2 +ln -s $tmpdir/foo/lvl1/lvl2/lvl3/lvl4 $tmpdir/foo/lvl1/link@1 +echo > $tmpdir/bar/xo +chmod a-x,a+r $tmpdir/bar + +testout=${TMPDIR:-/tmp}/ftwtest.out +LD_LIBRARY_PATH=$objpfx $objpfx/elf/ld.so $testprogram $tmpdir | + sort > $testout + +cat < $testout + +cat < +#include +#include +#include +#include +#include +#include + + +int do_depth; +int do_chdir; +int do_phys; + +struct option options[] = +{ + { "depth", no_argument, &do_depth, 1 }, + { "chdir", no_argument, &do_chdir, 1 }, + { "phys", no_argument, &do_phys, 1 }, + { NULL, 0, NULL, 0 } +}; + +const char *flag2name[] = +{ + [FTW_F] = "FTW_F", + [FTW_D] = "FTW_D", + [FTW_DNR] = "FTW_DNR", + [FTW_NS] = "FTW_NS", + [FTW_SL] = "FTW_SL", + [FTW_DP] = "FTW_DP", + [FTW_SLN] = "FTW_SLN" +}; + + +int +cb (const char *name, const struct stat *st, int flag, struct FTW *f) +{ + printf ("base = \"%.*s\", file = \"%s\", flag = %s", + f->base, name, name + f->base, flag2name[flag]); + if (do_chdir) + { + char *cwd = getcwd (NULL, 0); + printf (", cwd = %s", cwd); + free (cwd); + } + puts (""); + return 0; +} + +int +main (int argc, char *argv[]) +{ + int opt; + int r; + int flag = 0; + mtrace (); + + while ((opt = getopt_long_only (argc, argv, "", options, NULL)) != -1) + ; + + if (do_chdir) + flag |= FTW_CHDIR; + if (do_depth) + flag |= FTW_DEPTH; + if (do_phys) + flag |= FTW_PHYS; + + r = nftw (optind < argc ? argv[optind] : ".", cb, 3, flag); + if (r) + perror ("nftw"); + return r; +} diff --git a/misc/search.h b/misc/search.h index 8ce33515d9..ff0672d39d 100644 --- a/misc/search.h +++ b/misc/search.h @@ -106,16 +106,21 @@ typedef enum } VISIT; +/* Search for an entry matching the given KEY in the tree pointed to + by *ROOTP and insert a new element if not found. */ extern void *tsearch __P ((__const void * __key, void **__rootp, __compar_fn_t compar)); extern void *__tsearch __P ((__const void * __key, void **__rootp, __compar_fn_t compar)); -extern void *tfind __P ((__const void * __key, __const void ** __rootp, +/* Search for an entry matching the given KEY in the tree pointed to + by *ROOTP. If no matching entry is available return NULL. */ +extern void *tfind __P ((__const void * __key, void *__const * __rootp, __compar_fn_t compar)); -extern void *__tfind __P ((__const void * __key, __const void ** __rootp, +extern void *__tfind __P ((__const void * __key, void *__const * __rootp, __compar_fn_t compar)); +/* Remove the element matching KEY from the tree pointed to by *ROOTP. */ extern void *tdelete __P ((__const void * __key, void ** __rootp, __compar_fn_t compar)); extern void *__tdelete __P ((__const void * __key, void ** __rootp, @@ -128,10 +133,22 @@ typedef void (*__action_fn_t) __P ((__const void *__nodep, int __level)); #endif +/* Walk through the whole tree and call the ACTION callback for every node + or leaf. */ extern void twalk __P ((__const void * __root, __action_fn_t action)); extern void __twalk __P ((__const void * __root, __action_fn_t action)); +#ifdef __USE_GNU +/* Callback type for function to free a tree node. If the keys are atomic + data this function should do nothing. */ +typedef void (*__free_fn_t) __P ((void *__nodep)); + +/* Destroy the whole tree, call FREEFCT for each node or leaf. */ +extern void __tdestroy __P ((void *__root, __free_fn_t freefct)); +extern void tdestroy __P ((void *__root, __free_fn_t freefct)); +#endif + /* Perform linear search for KEY by comparing by COMPAR in an array [BASE,BASE+NMEMB*SIZE). */ diff --git a/misc/tsearch.c b/misc/tsearch.c index 466536bf34..c06930d509 100644 --- a/misc/tsearch.c +++ b/misc/tsearch.c @@ -300,7 +300,7 @@ weak_alias (__tsearch, tsearch) void * __tfind (key, vrootp, compar) const void *key; - const void **vrootp; + void *const *vrootp; __compar_fn_t compar; { node *rootp = (node *) vrootp; @@ -625,3 +625,36 @@ __twalk (const void *vroot, __action_fn_t action) trecurse (root, action, 0); } weak_alias (__twalk, twalk) + + + +/* The standardized functions miss an important functionality: the + tree cannot be removed easily. We provide a function to do this. */ +static void +tdestroy_recurse (node root, __free_fn_t freefct) +{ + if (root->left == NULL && root->right == NULL) + (*freefct) (root->key); + else + { + if (root->left != NULL) + tdestroy_recurse (root->left, freefct); + if (root->right != NULL) + tdestroy_recurse (root->right, freefct); + (*freefct) (root->key); + } + /* Free the node itself. */ + free (root); +} + +void +__tdestroy (void *vroot, __free_fn_t freefct) +{ + node root = (node) vroot; + + CHECK_TREE (root); + + if (root != NULL) + tdestroy_recurse (root, freefct); +} +weak_alias (__tdestroy, tdestroy) -- cgit v1.2.3