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