tree

commit 5f67edad2ec70060fffbc3b6a23f8b7e7abbae38
parent a97217b6f99c2488f6e8863f190d63e45a93a85e
Author: Remy Noulin <loader2x@gmail.com>
Date:   Sun, 30 Dec 2018 12:53:02 +0100

store nodes in dVector for better performance

wavl.h | 54 ++++++++++++++++++++++++++++++++++++++----------------
1 file changed, 38 insertions(+), 16 deletions(-)

Diffstat:
M
wavl.h
 | 
54
++++++++++++++++++++++++++++++++++++++----------------

1 file changed, 38 insertions(+), 16 deletions(-)
diff --git a/wavl.h b/wavl.h
@@ -4,6 +4,9 @@
 
 /**
  *
+ * allocating node in dVector is slightly faster (in the order of 10% when the memory is not already map in the process)
+ * than the version allocating nodes with malloc. (826ms vs 870ms for 10M elements)
+ *
  * TODO add leftMost, rightMost pointer in tree
  *
  * void printTree(typeName##Nodet *X) {
@@ -81,8 +84,8 @@
   scope void init##suffix(typeName##t *tree) {\
     wavlInit(tree, nullKeyV, nullValueV);\
   }\
-  internal typeName##Nodet* newNode##suffix(keyType k, typeName##Nodet *parent) {\
-    ret wavlNewNode(k, parent);\
+  internal typeName##Nodet* newNode##suffix(typeName##t *tree, keyType k, typeName##Nodet *parent) {\
+    ret wavlNewNode(tree, k, parent);\
   }\
   internal int nodeHeight##suffix(typeName##Nodet *node) {\
     if (!node) {\
@@ -93,15 +96,15 @@
   scope int height##suffix(typeName##t *tree) {\
     ret nodeHeight##suffix(tree->root) - 1;\
   }\
-  internal void freeNodes##suffix(typeName##Nodet *node) {\
+  internal void freeNodes##suffix(typeName##t *tree, typeName##Nodet *node) {\
     if (!node) ret;\
-    freeNodes##suffix(node->left);\
-    freeNodes##suffix(node->right);\
+    freeNodes##suffix(tree, node->left);\
+    freeNodes##suffix(tree, node->right);\
     FREEFUNC(&node->key, &node->value);\
-    free(node);\
+    dVectorAppend(&tree->freeNodeList, node->index);\
   }\
   scope void empty##suffix(typeName##t *tree) {\
-    freeNodes##suffix(tree->root);\
+    freeNodes##suffix(tree, tree->root);\
     tree->modCount++;\
     tree->count      = 0;\
     tree->root       = NULL;\
@@ -112,7 +115,8 @@
   }\
   scope void free##suffix(typeName##t *tree) {\
     empty##suffix(tree);\
-    /* TODO free internal buffers */\
+    dVectorFree(&tree->treeNodes);\
+    dVectorFree(&tree->freeNodeList);\
   }\
   /** insert new (key,value), fail when the key already exists */\
   scope bool add##suffix(typeName##t *tree, keyType key, valueType value) {\
@@ -245,7 +249,7 @@
     if (!O) {\
       /* tree is empty, new node is root */\
       *isnew = true;\
-      tree->root  = newNode##suffix(key, NULL);\
+      tree->root  = newNode##suffix(tree, key, NULL);\
       tree->count = 1;\
       tree->modCount++;\
       ret tree->root;\
@@ -275,7 +279,7 @@
     } while(O);\
     \
     *isnew = true;\
-    var e = newNode##suffix(key, P);\
+    var e = newNode##suffix(tree, key, P);\
     /*logI("New %p", e);*/\
     if (cmp < 0) {\
       P->left = e;\
@@ -466,7 +470,7 @@
       if (!node->parent) {\
         tree->root = replacement;\
         FREEFUNC(&node->key, &node->value);\
-        free(node);\
+        dVectorAppend(&tree->freeNodeList, node->index);\
         ret;\
       }\
       elif (node == node->parent->left) {\
@@ -481,13 +485,13 @@
       /* Null out links so they are OK to use by fixAfterDeletion. */\
       node->left = node->right = node->parent = NULL;\
       FREEFUNC(&node->key, &node->value);\
-      free(node);\
+      dVectorAppend(&tree->freeNodeList, node->index);\
       balanceAfterDeleteWAVL##suffix(tree, replacement->parent, sibling, replacement->rank);\
     }\
     elif (!node->parent) {\
       /* return if we are the only node. */\
       FREEFUNC(&node->key, &node->value);\
-      free(node);\
+      dVectorAppend(&tree->freeNodeList, node->index);\
       tree->root = NULL;\
       ret;\
     }\
@@ -507,7 +511,7 @@
       node->parent = NULL;\
       int8_t rk = --node->rank;\
       FREEFUNC(&node->key, &node->value);\
-      free(node);\
+      dVectorAppend(&tree->freeNodeList, node->index);\
       balanceAfterDeleteWAVL##suffix(tree, fixPoint, sibling, rk);\
     }\
   }\
@@ -557,9 +561,12 @@
     typeName  *right;\
     typeName  *parent;\
     i8        rank;\
+    u32       index; /* node index in treeNodes vector */\
   }
 
 #define wavlTreeT(typeName, nodeType, keyType, valueType)\
+  dVectorT(UNIQVAR(treeNodest), nodeType);\
+  dVectorT(UNIQVAR(freeNodest), u32);\
   typ struct {\
     size_t             count;     /* number of entries in the tree */\
     size_t             modCount;  /* number of structural modifications to the tree */\
@@ -572,6 +579,8 @@
     nodeType           *next;\
     nodeType           *lastReturned;\
     /* end private iterator */\
+    UNIQVAR(treeNodest) treeNodes;\
+    UNIQVAR(freeNodest) freeNodeList;\
   } typeName
 
 #define wavlInit(t, nullKeyV, nullValueV) do {\
@@ -585,10 +594,23 @@
   t->expectedModCount = -1;\
   t->next             = NULL;\
   t->lastReturned     = NULL;\
+  dVectorInit(&t->treeNodes);\
+  dVectorInit(&t->freeNodeList);\
   } while(0)
 
-#define wavlNewNode(k, parent) ({\
-  typeof(parent) r = malloc(sizeof(*parent));\
+#define wavlNewNode(t, k, parent) ({\
+  typeof(t->root) r = NULL;\
+  if (dVectorIsEmpty(&t->freeNodeList)) {\
+    dVectorPush(&t->treeNodes);\
+    r        = dVectorLastPtr(&t->treeNodes);\
+    r->index = dVectorLastIndex(&t->treeNodes);\
+  }\
+  else {\
+   var UNIQVAR(idx) = dVectorLast(&t->freeNodeList);\
+   dVectorDelLast(&t->freeNodeList);\
+   r                = dVectorPtr(&t->treeNodes, UNIQVAR(idx));\
+   r->index         = UNIQVAR(idx);\
+  }\
   if (r) {\
     r->key           = k;\
     r->left          = NULL;\