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, 26 insertions, 14 deletions

diff --git a/heap/hp_update.c b/heap/hp_update.c
index 8cf3e4d4b8d..dd47e04ebc2 100644
--- a/heap/hp_update.c
+++ b/heap/hp_update.c
@@ -20,7 +20,7 @@
 
 int heap_update(HP_INFO *info, const byte *old, const byte *heap_new)
 {
-  uint key;
+  HP_KEYDEF *keydef, *end, *p_lastinx;
   byte *pos;
   HP_SHARE *share=info->s;
   DBUG_ENTER("heap_update");
@@ -28,19 +28,20 @@ int heap_update(HP_INFO *info, const byte *old, const byte *heap_new)
   test_active(info);
   pos=info->current_ptr;
 
-  if (info->opt_flag & READ_CHECK_USED && _hp_rectest(info,old))
+  if (info->opt_flag & READ_CHECK_USED && hp_rectest(info,old))
     DBUG_RETURN(my_errno);				/* Record changed */
   if (--(share->records) < share->blength >> 1) share->blength>>= 1;
   share->changed=1;
 
-  for (key=0 ; key < share->keys ; key++)
+  p_lastinx = share->keydef + info->lastinx;
+  for (keydef = share->keydef, end = keydef + share->keys; keydef < end; 
+       keydef++)
   {
-    if (_hp_rec_key_cmp(share->keydef+key,old,heap_new))
+    if (hp_rec_key_cmp(keydef, old, heap_new))
     {
-      if (_hp_delete_key(info,share->keydef+key,old,pos,key ==
-			 (uint) info->lastinx) ||
-	  _hp_write_key(share,share->keydef+key,heap_new,pos))
-	goto err;
+      if ((*keydef->delete_key)(info, keydef, old, pos, keydef == p_lastinx) ||
+          (*keydef->write_key)(info, keydef, heap_new, pos))
+        goto err;
     }
   }
 
@@ -51,16 +52,27 @@ int heap_update(HP_INFO *info, const byte *old, const byte *heap_new)
  err:
   if (my_errno == HA_ERR_FOUND_DUPP_KEY)
   {
-    info->errkey=key;
-    do
+    info->errkey = keydef - share->keydef;
+    if (keydef->algorithm == HA_KEY_ALG_BTREE)
     {
-      if (_hp_rec_key_cmp(share->keydef+key,old,heap_new))
+      /* we don't need to delete non-inserted key from rb-tree */
+      if ((*keydef->write_key)(info, keydef, old, pos))
       {
-	if (_hp_delete_key(info,share->keydef+key,heap_new,pos,0) ||
-	    _hp_write_key(share,share->keydef+key,old,pos))
+        if (++(share->records) == share->blength) share->blength+= share->blength;
+        DBUG_RETURN(my_errno);
+      }
+      keydef--;
+    }
+    while (keydef >= share->keydef)
+    {
+      if (hp_rec_key_cmp(keydef, old, heap_new))
+      {
+	if ((*keydef->delete_key)(info, keydef, heap_new, pos, 0) ||
+	    (*keydef->write_key)(info, keydef, old, pos))
 	  break;
       }
-    } while (key-- > 0);
+      keydef--;
+    }
   }
   if (++(share->records) == share->blength) share->blength+= share->blength;
   DBUG_RETURN(my_errno);