aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorUlrich Drepper <drepper@redhat.com>1997-05-30 01:37:13 +0000
committerUlrich Drepper <drepper@redhat.com>1997-05-30 01:37:13 +0000
commitd951286f645cc1d6f719c0c715620fc395c049d4 (patch)
treeff756b3d8cb561d733337cf27bca2e26358852ba
parent76b87c039ba8d20add4f52ba43f3471fd92e210b (diff)
downloadglibc-d951286f645cc1d6f719c0c715620fc395c049d4.zip
glibc-d951286f645cc1d6f719c0c715620fc395c049d4.tar.gz
glibc-d951286f645cc1d6f719c0c715620fc395c049d4.tar.bz2
* 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.
-rw-r--r--.cvsignore1
-rw-r--r--ChangeLog9
-rw-r--r--io/Makefile6
-rw-r--r--io/ftw.c187
-rw-r--r--io/ftw.h4
-rw-r--r--io/ftwtest-sh84
-rw-r--r--io/ftwtest.c71
-rw-r--r--misc/search.h21
-rw-r--r--misc/tsearch.c35
9 files changed, 359 insertions, 59 deletions
diff --git a/.cvsignore b/.cvsignore
index 1378938..e724ae9 100644
--- a/.cvsignore
+++ b/.cvsignore
@@ -14,6 +14,7 @@ gpl2lgpl.sed
distinfo
distinfo
+test-include
analysis
docs
diff --git a/ChangeLog b/ChangeLog
index 5c3cf9d..199ee31 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 f1efd21..d199f91 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 e20ad23..7367f97 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 70fb9e2..d283e69 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 0000000..1c7c398
--- /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 <<EOF | cmp $testout - || exit 1
+base = "$tmp/", file = "ftwtest.d", flag = FTW_D
+base = "$tmp/ftwtest.d/", file = "bar", flag = FTW_D
+base = "$tmp/ftwtest.d/", file = "baz", flag = FTW_F
+base = "$tmp/ftwtest.d/", file = "foo", flag = FTW_D
+base = "$tmp/ftwtest.d/bar/", file = "xo", flag = FTW_NS
+base = "$tmp/ftwtest.d/foo/", file = "lvl1", flag = FTW_D
+base = "$tmp/ftwtest.d/foo/lvl1/", file = "file@1", flag = FTW_F
+base = "$tmp/ftwtest.d/foo/lvl1/", file = "link@1", flag = FTW_SLN
+base = "$tmp/ftwtest.d/foo/lvl1/", file = "lvl2", flag = FTW_D
+base = "$tmp/ftwtest.d/foo/lvl1/lvl2/", file = "file@2", flag = FTW_F
+base = "$tmp/ftwtest.d/foo/lvl1/lvl2/", file = "lvl3", flag = FTW_D
+base = "$tmp/ftwtest.d/foo/lvl1/lvl2/lvl3/", file = "file@3", flag = FTW_F
+EOF
+rm $testout
+
+testout=${TMPDIR:-/tmp}/ftwtest.out
+LD_LIBRARY_PATH=$objpfx $objpfx/elf/ld.so $testprogram --depth $tmpdir |
+ sort > $testout
+
+cat <<EOF | cmp $testout - || exit 1
+base = "/tmp/", file = "ftwtest.d", flag = FTW_DP
+base = "/tmp/ftwtest.d/", file = "bar", flag = FTW_DP
+base = "/tmp/ftwtest.d/", file = "baz", flag = FTW_F
+base = "/tmp/ftwtest.d/", file = "foo", flag = FTW_DP
+base = "/tmp/ftwtest.d/bar/", file = "xo", flag = FTW_NS
+base = "/tmp/ftwtest.d/foo/", file = "lvl1", flag = FTW_DP
+base = "/tmp/ftwtest.d/foo/lvl1/", file = "file@1", flag = FTW_F
+base = "/tmp/ftwtest.d/foo/lvl1/", file = "link@1", flag = FTW_SLN
+base = "/tmp/ftwtest.d/foo/lvl1/", file = "lvl2", flag = FTW_DP
+base = "/tmp/ftwtest.d/foo/lvl1/lvl2/", file = "file@2", flag = FTW_F
+base = "/tmp/ftwtest.d/foo/lvl1/lvl2/", file = "lvl3", flag = FTW_DP
+base = "/tmp/ftwtest.d/foo/lvl1/lvl2/lvl3/", file = "file@3", flag = FTW_F
+EOF
+rm $testout
+
+chmod -R a+x $tmpdir
+rm -fr $tmpdir
+
+exit 0 \ No newline at end of file
diff --git a/io/ftwtest.c b/io/ftwtest.c
new file mode 100644
index 0000000..6daa7e9
--- /dev/null
+++ b/io/ftwtest.c
@@ -0,0 +1,71 @@
+#include <ftw.h>
+#include <getopt.h>
+#include <mcheck.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <unistd.h>
+#include <sys/stat.h>
+
+
+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 8ce3351..ff0672d 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 466536b..c06930d 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)