| 1 |
#include <stdlib.h> |
| 2 |
#include <search.h> |
| 3 |
#include "tsearch.h" |
| 4 |
|
| 5 |
void *tdelete(const void *restrict key, void **restrict rootp, |
| 6 |
int(*cmp)(const void *, const void *)) |
| 7 |
{ |
| 8 |
if (!rootp) |
| 9 |
return 0; |
| 10 |
|
| 11 |
void **a[MAXH+1]; |
| 12 |
struct node *n = *rootp; |
| 13 |
struct node *parent; |
| 14 |
struct node *child; |
| 15 |
int i=0; |
| 16 |
/* *a[0] is an arbitrary non-null pointer that is returned when |
| 17 |
the root node is deleted. */ |
| 18 |
a[i++] = rootp; |
| 19 |
a[i++] = rootp; |
| 20 |
for (;;) { |
| 21 |
if (!n) |
| 22 |
return 0; |
| 23 |
int c = cmp(key, n->key); |
| 24 |
if (!c) |
| 25 |
break; |
| 26 |
a[i++] = &n->a[c>0]; |
| 27 |
n = n->a[c>0]; |
| 28 |
} |
| 29 |
parent = *a[i-2]; |
| 30 |
if (n->a[0]) { |
| 31 |
/* free the preceding node instead of the deleted one. */ |
| 32 |
struct node *deleted = n; |
| 33 |
a[i++] = &n->a[0]; |
| 34 |
n = n->a[0]; |
| 35 |
while (n->a[1]) { |
| 36 |
a[i++] = &n->a[1]; |
| 37 |
n = n->a[1]; |
| 38 |
} |
| 39 |
deleted->key = n->key; |
| 40 |
child = n->a[0]; |
| 41 |
} else { |
| 42 |
child = n->a[1]; |
| 43 |
} |
| 44 |
/* freed node has at most one child, move it up and rebalance. */ |
| 45 |
free(n); |
| 46 |
*a[--i] = child; |
| 47 |
while (--i && __tsearch_balance(a[i])); |
| 48 |
return parent; |
| 49 |
} |