RB-Tree indexes support in HEAP tables

Renamed _hp_func  ->  hp_func
mi_key_cmp moved to /mysys/my_handler.c
New tests for HEAP tables

1 files changed, 178 insertions, 11 deletions

diff --git a/mysys/tree.c b/mysys/tree.c
index 2ac2c88fd66..632660344b5 100644
--- a/mysys/tree.c
+++ b/mysys/tree.c
@@ -42,6 +42,7 @@
 #include "mysys_priv.h"
 #include <m_string.h>
 #include <my_tree.h>
+#include "my_base.h"
 
 #define BLACK		1
 #define RED		0
@@ -167,7 +168,8 @@ static void delete_tree_element(TREE *tree, TREE_ELEMENT *element)
 	     parent[0] = & parent[-1][0]->right */
 
 
-TREE_ELEMENT *tree_insert(TREE *tree, void *key, uint key_size)
+TREE_ELEMENT *tree_insert(TREE *tree, void *key, uint key_size, 
+                          void* custom_arg)
 {
   int cmp;
   TREE_ELEMENT *element,***parent;
@@ -177,8 +179,8 @@ TREE_ELEMENT *tree_insert(TREE *tree, void *key, uint key_size)
   for (;;)
   {
     if (element == &tree->null_element ||
-	(cmp=(*tree->compare)(tree->custom_arg,
-			      ELEMENT_KEY(tree,element),key)) == 0)
+	(cmp = (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element),
+                                key)) == 0)
       break;
     if (cmp < 0)
     {
@@ -198,7 +200,7 @@ TREE_ELEMENT *tree_insert(TREE *tree, void *key, uint key_size)
                            && tree->allocated > tree->memory_limit)
     {
       reset_tree(tree);
-      return tree_insert(tree, key, key_size);
+      return tree_insert(tree, key, key_size, custom_arg);
     }
 
     key_size+=tree->size_of_element;
@@ -234,8 +236,7 @@ TREE_ELEMENT *tree_insert(TREE *tree, void *key, uint key_size)
   return element;
 }
 
-
-int tree_delete(TREE *tree, void *key)
+int tree_delete(TREE *tree, void *key, void *custom_arg)
 {
   int cmp,remove_colour;
   TREE_ELEMENT *element,***parent, ***org_parent, *nod;
@@ -248,8 +249,8 @@ int tree_delete(TREE *tree, void *key)
   {
     if (element == &tree->null_element)
       return 1;				/* Was not in tree */
-    if ((cmp=(*tree->compare)(tree->custom_arg,
-			      ELEMENT_KEY(tree,element),key)) == 0)
+    if ((cmp = (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element),
+                                key)) == 0)
       break;
     if (cmp < 0)
     {
@@ -296,7 +297,7 @@ int tree_delete(TREE *tree, void *key)
 }
 
 
-void *tree_search(TREE *tree, void *key)
+void *tree_search(TREE *tree, void *key, void *custom_arg)
 {
   int cmp;
   TREE_ELEMENT *element=tree->root;
@@ -305,8 +306,8 @@ void *tree_search(TREE *tree, void *key)
   {
     if (element == &tree->null_element)
       return (void*) 0;
-    if ((cmp=(*tree->compare)(tree->custom_arg,
-			      ELEMENT_KEY(tree,element),key)) == 0)
+    if ((cmp = (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element),
+                                key)) == 0)
       return ELEMENT_KEY(tree,element);
     if (cmp < 0)
       element=element->right;
@@ -315,6 +316,172 @@ void *tree_search(TREE *tree, void *key)
   }
 }
 
+void *tree_search_key(TREE *tree, const void *key, 
+                      TREE_ELEMENT **parents, TREE_ELEMENT ***last_pos,
+                      enum ha_rkey_function flag, void *custom_arg)
+{
+  int cmp;
+  TREE_ELEMENT *element = tree->root;
+  TREE_ELEMENT **last_left_step_parent = NULL;
+  TREE_ELEMENT **last_equal_element = NULL;
+
+/* 
+  TODO: handle HA_READ_KEY_OR_PREV, HA_READ_BEFORE_KEY, HA_READ_PREFIX, 
+  HA_READ_PREFIX_LAST flags if needed.
+*/
+
+  *parents = &tree->null_element;
+  while (element != &tree->null_element)
+  {
+    *++parents = element;
+    if ((cmp = (*tree->compare)(custom_arg, ELEMENT_KEY(tree, element), 
+                                key)) == 0)
+    {
+      switch (flag) {
+      case HA_READ_KEY_EXACT:
+      case HA_READ_KEY_OR_NEXT:
+        last_equal_element = parents;
+        cmp = 1;
+        break;
+      case HA_READ_AFTER_KEY:
+        cmp = -1;
+        break;
+      default:
+        return NULL;
+      }
+    }
+    if (cmp < 0) /* element < key */
+    {
+      element = element->right;
+    }
+    else
+    {
+      last_left_step_parent = parents;
+      element = element->left;
+    }
+  }
+  switch (flag) {
+  case HA_READ_KEY_EXACT:
+    *last_pos = last_equal_element;
+    break;
+  case HA_READ_KEY_OR_NEXT:
+    *last_pos = last_equal_element ? last_equal_element : last_left_step_parent;
+    break;
+  case HA_READ_AFTER_KEY:
+    *last_pos = last_left_step_parent;
+    break;
+  default:
+    return NULL;
+  }
+  return *last_pos ? ELEMENT_KEY(tree, **last_pos) : NULL;
+}
+
+/* 
+  Search first (the most left) or last (the most right) tree element 
+*/
+void *tree_search_edge(TREE *tree, TREE_ELEMENT **parents, 
+                        TREE_ELEMENT ***last_pos, int child_offs)
+{
+  TREE_ELEMENT *element = tree->root;
+  
+  *parents = &tree->null_element;
+  while (element != &tree->null_element)
+  {
+    *++parents = element;
+    element = ELEMENT_CHILD(element, child_offs);
+  }
+  *last_pos = parents;
+  return **last_pos != &tree->null_element ? 
+    ELEMENT_KEY(tree, **last_pos) : NULL;
+}
+
+void *tree_search_next(TREE *tree, TREE_ELEMENT ***last_pos, int l_offs, 
+                       int r_offs)
+{
+  TREE_ELEMENT *x = **last_pos;
+  
+  if (ELEMENT_CHILD(x, r_offs) != &tree->null_element)
+  {
+    x = ELEMENT_CHILD(x, r_offs);
+    *++*last_pos = x;
+    while (ELEMENT_CHILD(x, l_offs) != &tree->null_element)
+    {
+      x = ELEMENT_CHILD(x, l_offs);
+      *++*last_pos = x;
+    }
+    return ELEMENT_KEY(tree, x);
+  }
+  else
+  {
+    TREE_ELEMENT *y = *--*last_pos;
+    while (y != &tree->null_element && x == ELEMENT_CHILD(y, r_offs))
+    {
+      x = y;
+      y = *--*last_pos;
+    }
+    return y == &tree->null_element ? NULL : ELEMENT_KEY(tree, y);
+  }
+}
+
+/*
+  Expected that tree is fully balanced
+  (each path from root to leaf has the same length)
+*/
+uint tree_record_pos(TREE *tree, const void *key, 
+                     enum ha_rkey_function flag, void *custom_arg)
+{
+  int cmp;
+  TREE_ELEMENT *element = tree->root;
+  uint left = 1;
+  uint right = tree->elements_in_tree;
+  uint last_left_step_pos = tree->elements_in_tree;
+  uint last_right_step_pos = 1;
+  uint last_equal_pos = HA_POS_ERROR;
+
+  while (element != &tree->null_element)
+  {
+    if ((cmp = (*tree->compare)(custom_arg, ELEMENT_KEY(tree, element), 
+                                key)) == 0)
+    {
+      switch (flag) {
+      case HA_READ_KEY_EXACT:
+        last_equal_pos = (left + right) >> 1;
+        cmp = 1;
+        break;
+      case HA_READ_BEFORE_KEY:
+        cmp = 1;
+        break;
+      case HA_READ_AFTER_KEY:
+        cmp = -1;
+        break;
+      default:
+        return HA_POS_ERROR;
+      }
+    }
+    if (cmp < 0) /* element < key */
+    {
+      last_right_step_pos = (left + right) >> 1;
+      element = element->right;
+      left = last_right_step_pos;
+    }
+    else
+    {
+      last_left_step_pos = (left + right) >> 1;
+      element = element->left;
+      right = last_left_step_pos;
+    }
+  }
+  switch (flag) {
+  case HA_READ_KEY_EXACT:
+    return last_equal_pos;
+  case HA_READ_BEFORE_KEY:
+    return last_right_step_pos;
+  case HA_READ_AFTER_KEY:
+    return last_left_step_pos;
+  default:
+    return HA_POS_ERROR;
+  }
+}
 
 int tree_walk(TREE *tree, tree_walk_action action, void *argument, TREE_WALK visit)
 {