skalibs

Mirror/fork of https://skarnet.org/software/skalibs/
git clone https://ccx.te2000.cz/git/skalibs
Log | Files | Refs | README | LICENSE

avlnode_insertnode.c (998B)

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