1 /* ISC license. */
2
3 #include <skalibs/avlnode.h>
4 #include "avlnode-internal.h"
5
avlnode_delete(avlnode * s,uint32_t max,uint32_t * root,void const * k,dtokfunc_t_ref dtok,cmpfunc_t_ref f,void * p)6 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)
7 {
8 uint32_t stack[AVLNODE_MAXDEPTH] ;
9 int spin[AVLNODE_MAXDEPTH] ;
10 unsigned int sp = 0 ;
11 uint32_t r = *root ;
12 uint32_t itodel ;
13
14 for (; r < max ; sp++)
15 {
16 int c = (*f)(k, (*dtok)(s[r].data, p), p) ;
17 if (!c) break ;
18 spin[sp] = avlnode_ufroms(c) ;
19 stack[sp] = r ;
20 r = s[r].child[spin[sp]] ;
21 }
22 if (r >= max) return max ;
23 itodel = r ;
24
25 if ((s[r].child[0] < max) || (s[r].child[1] < max))
26 {
27 int subspin = s[r].child[1] < max ;
28 stack[sp] = r ;
29 spin[sp++] = subspin ;
30 r = s[r].child[subspin] ;
31 for (; r < max ; sp++)
32 {
33 stack[sp] = r ;
34 spin[sp] = !subspin ;
35 r = s[r].child[!subspin] ;
36 }
37 r = stack[--sp] ;
38 s[itodel].data = s[r].data ;
39 itodel = s[r].child[subspin] ;
40 if (itodel < max)
41 {
42 s[r].data = s[itodel].data ;
43 stack[sp] = r ;
44 spin[sp++] = subspin ;
45 }
46 else itodel = r ;
47 }
48
49 r = max ;
50 while (sp--)
51 {
52 s[stack[sp]].child[spin[sp]] = r ;
53 r = stack[sp] ;
54 if (!s[r].balance) goto easyfix ;
55 else if (spin[sp] == avlnode_ufroms(s[r].balance)) s[r].balance = 0 ;
56 else if (!s[s[r].child[!spin[sp]]].balance) goto hardfix ;
57 else r = avlnode_rotate_maydouble(s, max, r, spin[sp], spin[sp] == avlnode_ufroms(s[s[r].child[!spin[sp]]].balance)) ;
58 }
59 *root = r ;
60 return itodel ;
61
62 easyfix:
63 s[r].balance = -avlnode_sfromu(spin[sp]) ;
64 return itodel ;
65
66 hardfix:
67 r = avlnode_rotate(s, max, r, spin[sp]) ;
68 if (!sp--) *root = r ;
69 else s[stack[sp]].child[spin[sp]] = r ;
70 return itodel ;
71 }
72