skalibs

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

avlnode_delete.c (1776B)

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