1 /* ISC license. */
2
3 #include <skalibs/avlnode.h>
4 #include "avlnode-internal.h"
5
avlnode_insertnode(avlnode * s,uint32_t max,uint32_t r,uint32_t i,dtokfunc_t_ref dtok,cmpfunc_t_ref f,void * p)6 uint32_t avlnode_insertnode (avlnode *s, uint32_t max, uint32_t r, uint32_t i, 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
12 {
13 void const *k = (*dtok)(s[i].data, p) ;
14 for (; r < max ; sp++)
15 {
16 spin[sp] = avlnode_ufroms((*f)(k, (*dtok)(s[r].data, p), p)) ;
17 stack[sp] = r ;
18 r = s[r].child[spin[sp]] ;
19 }
20 }
21 r = i ;
22 while (sp--)
23 {
24 s[stack[sp]].child[spin[sp]] = r ;
25 r = stack[sp] ;
26 if (s[r].balance) goto lastfix ;
27 s[r].balance = avlnode_sfromu(spin[sp]) ;
28 }
29 return r ;
30
31 lastfix:
32 if (avlnode_ufroms(s[r].balance) != spin[sp])
33 {
34 s[r].balance = 0 ;
35 return stack[0] ;
36 }
37 r = avlnode_rotate_maydouble(s, max, r, !spin[sp], spin[sp] != spin[sp+1]) ;
38 if (!sp--) return r ;
39 s[stack[sp]].child[spin[sp]] = r ;
40 return stack[0] ;
41 }
42