From 3534b428629be185e096be99e3bd5fdfe32d5544 Mon Sep 17 00:00:00 2001
From: Laurent Bercot <ska-skaware@skarnet.org>
Date: Thu, 18 Sep 2014 18:55:44 +0000
Subject: initial commit with rc for skalibs-2.0.0.0

---
 src/libdatastruct/avlnode_insertnode.c | 42 ++++++++++++++++++++++++++++++++++
 1 file changed, 42 insertions(+)
 create mode 100644 src/libdatastruct/avlnode_insertnode.c

(limited to 'src/libdatastruct/avlnode_insertnode.c')

diff --git a/src/libdatastruct/avlnode_insertnode.c b/src/libdatastruct/avlnode_insertnode.c
new file mode 100644
index 0000000..c69b34e
--- /dev/null
+++ b/src/libdatastruct/avlnode_insertnode.c
@@ -0,0 +1,42 @@
+/* ISC license. */
+
+#include <skalibs/functypes.h>
+#include <skalibs/avlnode.h>
+#include "avlnode-internal.h"
+
+unsigned int avlnode_insertnode (avlnode_ref s, unsigned int max, unsigned int r, unsigned int i, dtokfunc_t_ref dtok, cmpfunc_t_ref f, void *p)
+{
+  unsigned int stack[AVLNODE_MAXDEPTH] ;
+  int spin[AVLNODE_MAXDEPTH] ;
+  unsigned int sp = 0 ;
+  
+  {
+    register void const *k = (*dtok)(s[i].data, p) ;
+    for (; r < max ; sp++)
+    {
+      spin[sp] = avlnode_ufroms((*f)(k, (*dtok)(s[r].data, p), p)) ;
+      stack[sp] = r ;
+      r = s[r].child[spin[sp]] ;
+    }
+  }
+  r = i ;
+  while (sp--)
+  {
+    s[stack[sp]].child[spin[sp]] = r ;
+    r = stack[sp] ;
+    if (s[r].balance) goto lastfix ;
+    s[r].balance = avlnode_sfromu(spin[sp]) ;
+  }
+  return r ;
+
+ lastfix:
+  if (avlnode_ufroms(s[r].balance) != spin[sp])
+  {
+    s[r].balance = 0 ;
+    return stack[0] ;
+  }
+  r = avlnode_rotate_maydouble(s, max, r, !spin[sp], spin[sp] != spin[sp+1]) ;
+  if (!sp--) return r ;
+  s[stack[sp]].child[spin[sp]] = r ;
+  return stack[0] ;
+}
-- 
cgit v1.3.1