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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
|
/* ISC license. */
#include <skalibs/avlnode.h>
#include "avlnode-internal.h"
uint32_t avlnode_delete (avlnode *s, uint32_t max, uint32_t *root, void const *k, dtokfunc_t_ref dtok, cmpfunc_t_ref f, void *p)
{
uint32_t stack[AVLNODE_MAXDEPTH] ;
int spin[AVLNODE_MAXDEPTH] ;
unsigned int sp = 0 ;
uint32_t r = *root ;
uint32_t itodel ;
for (; r < max ; sp++)
{
int c = (*f)(k, (*dtok)(s[r].data, p), p) ;
if (!c) break ;
spin[sp] = avlnode_ufroms(c) ;
stack[sp] = r ;
r = s[r].child[spin[sp]] ;
}
if (r >= max) return max ;
itodel = r ;
if ((s[r].child[0] < max) || (s[r].child[1] < max))
{
int subspin = s[r].child[1] < max ;
stack[sp] = r ;
spin[sp++] = subspin ;
r = s[r].child[subspin] ;
for (; r < max ; sp++)
{
stack[sp] = r ;
spin[sp] = !subspin ;
r = s[r].child[!subspin] ;
}
r = stack[--sp] ;
s[itodel].data = s[r].data ;
itodel = s[r].child[subspin] ;
if (itodel < max)
{
s[r].data = s[itodel].data ;
stack[sp] = r ;
spin[sp++] = subspin ;
}
else itodel = r ;
}
r = max ;
while (sp--)
{
s[stack[sp]].child[spin[sp]] = r ;
r = stack[sp] ;
if (!s[r].balance) goto easyfix ;
else if (spin[sp] == avlnode_ufroms(s[r].balance)) s[r].balance = 0 ;
else if (!s[s[r].child[!spin[sp]]].balance) goto hardfix ;
else r = avlnode_rotate_maydouble(s, max, r, spin[sp], spin[sp] == avlnode_ufroms(s[s[r].child[!spin[sp]]].balance)) ;
}
*root = r ;
return itodel ;
easyfix:
s[r].balance = -avlnode_sfromu(spin[sp]) ;
return itodel ;
hardfix:
r = avlnode_rotate(s, max, r, spin[sp]) ;
if (!sp--) *root = r ;
else s[stack[sp]].child[spin[sp]] = r ;
return itodel ;
}
|
