diff options
Diffstat (limited to 'misc')
| -rw-r--r-- | misc/search.h | 21 | ||||
| -rw-r--r-- | misc/tsearch.c | 35 |
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) |