11 static int delta(struct node *n) {
12 return (n->left ? n->left->height:0) - (n->right ? n->right->height:0);
15 static void updateheight(struct node *n) {
17 if (n->left && n->left->height > n->height)
18 n->height = n->left->height;
19 if (n->right && n->right->height > n->height)
20 n->height = n->right->height;
24 static struct node *rotl(struct node *n) {
25 struct node *r = n->right;
33 static struct node *rotr(struct node *n) {
34 struct node *l = n->left;
42 static struct node *balance(struct node *n) {
46 if (delta(n->right) > 0)
47 n->right = rotr(n->right);
50 if (delta(n->left) < 0)
51 n->left = rotl(n->left);
58 static struct node *find(struct node *n, const void *k,
59 int (*cmp)(const void *, const void *))
69 return find(n->left, k, cmp);
71 return find(n->right, k, cmp);
74 static struct node *insert(struct node **n, const void *k,
75 int (*cmp)(const void *, const void *), int *new)
81 *n = r = malloc(sizeof **n);
84 r->left = r->right = 0;
94 r = insert(&r->left, k, cmp, new);
96 r = insert(&r->right, k, cmp, new);
102 static struct node *movr(struct node *n, struct node *r) {
105 n->right = movr(n->right, r);
109 static struct node *remove(struct node **n, const void *k,
110 int (*cmp)(const void *, const void *), struct node *parent)
116 c = cmp(k, (*n)->key);
119 *n = movr(r->left, r->right);
124 parent = remove(&(*n)->left, k, cmp, *n);
126 parent = remove(&(*n)->right, k, cmp, *n);
132 void *tdelete(const void *restrict key, void **restrict rootp,
133 int(*compar)(const void *, const void *))
135 /* last argument is arbitrary non-null pointer
136 which is returned when the root node is deleted */
137 return remove((void*)rootp, key, compar, *rootp);
140 void *tfind(const void *key, void *const *rootp,
141 int(*compar)(const void *, const void *))
143 return find(*rootp, key, compar);
146 void *tsearch(const void *key, void **rootp,
147 int (*compar)(const void *, const void *))
150 return insert((void*)rootp, key, compar, &new);
153 static void walk(const struct node *r, void (*action)(const void *, VISIT, int), int d)
157 if (r->left == 0 && r->right == 0)
160 action(r, preorder, d);
161 walk(r->left, action, d+1);
162 action(r, postorder, d);
163 walk(r->right, action, d+1);
164 action(r, endorder, d);
168 void twalk(const void *root, void (*action)(const void *, VISIT, int))
170 walk(root, action, 0);