#include <stdlib.h>
#include <search.h>
+/*
+avl tree implementation using recursive functions
+the height of an n node tree is less than 1.44*log2(n+2)-1
+(so the max recursion depth in case of a tree with 2^32 nodes is 45)
+*/
+
struct node {
const void *key;
struct node *left;
void *tdelete(const void *restrict key, void **restrict rootp,
int(*compar)(const void *, const void *))
{
+ struct node *n = *rootp;
+ struct node *ret;
/* last argument is arbitrary non-null pointer
which is returned when the root node is deleted */
- return remove((void*)rootp, key, compar, *rootp);
+ ret = remove(&n, key, compar, n);
+ *rootp = n;
+ return ret;
}
void *tfind(const void *key, void *const *rootp,
int (*compar)(const void *, const void *))
{
int new = 0;
- return insert((void*)rootp, key, compar, &new);
+ struct node *n = *rootp;
+ struct node *ret;
+ ret = insert(&n, key, compar, &new);
+ *rootp = n;
+ return ret;
}
static void walk(const struct node *r, void (*action)(const void *, VISIT, int), int d)