summaryrefslogtreecommitdiff
path: root/src/libdatastruct/avlnode_delete.c
blob: 8e57bf81c488bd928f29ba1e0fcb4eabfcd61de5 (plain)
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 ;
}