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


heap/_check.c:
  RB-tree index
  Renamed _hp_func -> hp_func
heap/_rectest.c:
  RB-tree index
  Renamed _hp_func -> hp_func
heap/heapdef.h:
  RB-tree index
  Renamed _hp_func -> hp_func
heap/hp_block.c:
  RB-tree index
  Renamed _hp_func -> hp_func
heap/hp_clear.c:
  RB-tree index
  Renamed _hp_func -> hp_func
heap/hp_close.c:
  RB-tree index
  Renamed _hp_func -> hp_func
heap/hp_create.c:
  RB-tree index
  Renamed _hp_func -> hp_func
heap/hp_delete.c:
  RB-tree index
  Renamed _hp_func -> hp_func
heap/hp_hash.c:
  RB-tree index
  Renamed _hp_func -> hp_func
heap/hp_open.c:
  RB-tree index
  Renamed _hp_func -> hp_func
heap/hp_panic.c:
  RB-tree index
  Renamed _hp_func -> hp_func
heap/hp_rename.c:
  RB-tree index
  Renamed _hp_func -> hp_func
heap/hp_rfirst.c:
  RB-tree index
  Renamed _hp_func -> hp_func
heap/hp_rkey.c:
  RB-tree index
  Renamed _hp_func -> hp_func
heap/hp_rlast.c:
  RB-tree index
  Renamed _hp_func -> hp_func
heap/hp_rnext.c:
  RB-tree index
  Renamed _hp_func -> hp_func
heap/hp_rprev.c:
  RB-tree index
  Renamed _hp_func -> hp_func
heap/hp_rrnd.c:
  RB-tree index
  Renamed _hp_func -> hp_func
heap/hp_rsame.c:
  RB-tree index
  Renamed _hp_func -> hp_func
heap/hp_scan.c:
  RB-tree index
  Renamed _hp_func -> hp_func
heap/hp_test1.c:
  RB-tree index
  Renamed _hp_func -> hp_func
heap/hp_test2.c:
  RB-tree index
  Renamed _hp_func -> hp_func
heap/hp_update.c:
  RB-tree index
  Renamed _hp_func -> hp_func
heap/hp_write.c:
  RB-tree index
  Renamed _hp_func -> hp_func
include/Makefile.am:
  New include
include/heap.h:
  RB-Tree index
include/my_tree.h:
  new search functions
  new custom_arg argument
include/myisam.h:
  Removed MI_KEYSEG
isam/isamlog.c:
  Add custom_arg
isam/pack_isam.c:
  Add custom_arg
myisam/ft_nlq_search.c:
  Add custom_arg
myisam/ft_parser.c:
  Add custom_arg
myisam/ft_stopwords.c:
  Add custom_arg
myisam/mi_search.c:
  Remove mi_key_cmp
myisam/mi_write.c:
  Add custom_arg
myisam/myisamdef.h:
  Remove mi_key_cmp
myisam/myisamlog.c:
  Add custom_arg
myisam/myisampack.c:
  Add custom_arg
mysys/Makefile.am:
  New file my_handler.c
mysys/tree.c:
  custom_arg
  new search functions
sql/ha_heap.cc:
  RBTree
sql/ha_myisam.cc:
  RBTree
sql/item_sum.cc:
  custom_arg
sql/sql_analyse.cc:
  custom_arg
sql/sql_class.h:
  custom_arg
sql/sql_table.cc:
  Remove duplicate code
sql/sql_yacc.yy:
  UNDEF by default
sql/table.cc:
  Remove dirty hack

1 files changed, 41 insertions, 11 deletions

diff --git a/heap/hp_rnext.c b/heap/hp_rnext.c
index af08a0e68a2..12ce354335d 100644
--- a/heap/hp_rnext.c
+++ b/heap/hp_rnext.c
@@ -22,27 +22,57 @@ int heap_rnext(HP_INFO *info, byte *record)
 {
   byte *pos;
   HP_SHARE *share=info->s;
+  HP_KEYDEF *keyinfo;
   DBUG_ENTER("heap_rnext");
   
   if (info->lastinx < 0)
     DBUG_RETURN(my_errno=HA_ERR_WRONG_INDEX);
 
-  if (info->current_hash_ptr)
-    pos= _hp_search_next(info,share->keydef+info->lastinx, info->lastkey,
-			 info->current_hash_ptr);
-  else
+  keyinfo = share->keydef + info->lastinx;
+  if (keyinfo->algorithm == HA_KEY_ALG_BTREE)
   {
-    if (!info->current_ptr && (info->update & HA_STATE_NEXT_FOUND))
+    heap_rb_param custom_arg;
+
+    if (info->last_pos)
+      pos = tree_search_next(&keyinfo->rb_tree, &info->last_pos,
+                             offsetof(TREE_ELEMENT, left),
+                             offsetof(TREE_ELEMENT, right));
+    else
+    {
+      custom_arg.keyseg = keyinfo->seg;
+      custom_arg.key_length = info->lastkey_len;
+      custom_arg.search_flag = SEARCH_SAME | SEARCH_FIND;
+      pos = tree_search_key(&keyinfo->rb_tree, info->lastkey, info->parents, 
+                           &info->last_pos, info->last_find_flag, &custom_arg);
+    }
+    if (pos)
+    {
+      memcpy(&pos, pos + keyinfo->ref_offs, sizeof(byte*));
+      info->current_ptr = pos;
+    }
+    else
     {
-      pos=0;					/* Read next after last */
-      my_errno=HA_ERR_KEY_NOT_FOUND;
+      my_errno = HA_ERR_KEY_NOT_FOUND;
     }
-    else if (!info->current_ptr)		/* Deleted or first call */
-      pos= _hp_search(info,share->keydef+info->lastinx, info->lastkey, 0);
+  }
+  else
+  {
+    if (info->current_hash_ptr)
+      pos= hp_search_next(info, keyinfo, info->lastkey,
+			   info->current_hash_ptr);
     else
-      pos= _hp_search(info,share->keydef+info->lastinx, info->lastkey, 1);
+    {
+      if (!info->current_ptr && (info->update & HA_STATE_NEXT_FOUND))
+      {
+	pos=0;					/* Read next after last */
+	my_errno=HA_ERR_KEY_NOT_FOUND;
+      }
+      else if (!info->current_ptr)		/* Deleted or first call */
+	pos= hp_search(info, keyinfo, info->lastkey, 0);
+      else
+	pos= hp_search(info, keyinfo, info->lastkey, 1);
+    }
   }
-
   if (!pos)
   {
     info->update=HA_STATE_NEXT_FOUND;		/* For heap_rprev */