about summary refs log tree commit diff
path: root/misc
diff options
context:
space:
mode:
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)