summaryrefslogtreecommitdiff
path: root/misc
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 /misc
parent76b87c039ba8d20add4f52ba43f3471fd92e210b (diff)
downloadglibc-d951286f645cc1d6f719c0c715620fc395c049d4.tar.gz
* 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.
Diffstat (limited to 'misc')
-rw-r--r--misc/search.h21
-rw-r--r--misc/tsearch.c35
2 files changed, 53 insertions, 3 deletions
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)