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, 61 insertions, 25 deletions

diff --git a/heap/hp_write.c b/heap/hp_write.c
index 806f40e5be5..801505216bd 100644
--- a/heap/hp_write.c
+++ b/heap/hp_write.c
@@ -27,12 +27,12 @@
 #define HIGHUSED 8
 
 static byte *next_free_record_pos(HP_SHARE *info);
-static HASH_INFO *_hp_find_free_hash(HP_SHARE *info, HP_BLOCK *block,
+static HASH_INFO *hp_find_free_hash(HP_SHARE *info, HP_BLOCK *block,
 				     ulong records);
 
 int heap_write(HP_INFO *info, const byte *record)
 {
-  uint key;
+  HP_KEYDEF *keydef, *end;
   byte *pos;
   HP_SHARE *share=info->s;
   DBUG_ENTER("heap_write");
@@ -47,9 +47,10 @@ int heap_write(HP_INFO *info, const byte *record)
     DBUG_RETURN(my_errno);
   share->changed=1;
 
-  for (key=0 ; key < share->keys ; key++)
+  for (keydef = share->keydef, end = keydef + share->keys; keydef < end;
+       keydef++)
   {
-    if (_hp_write_key(share,share->keydef+key,record,pos))
+    if ((*keydef->write_key)(info, keydef, record, pos))
       goto err;
   }
 
@@ -62,13 +63,19 @@ int heap_write(HP_INFO *info, const byte *record)
   info->update|=HA_STATE_AKTIV;
   DBUG_RETURN(0);
 err:
-  DBUG_PRINT("info",("Duplicate key: %d",key));
-  info->errkey= key;
-  do
+  DBUG_PRINT("info",("Duplicate key: %d", keydef - share->keydef));
+  info->errkey= keydef - share->keydef;
+  if (keydef->algorithm == HA_KEY_ALG_BTREE)
   {
-    if (_hp_delete_key(info,share->keydef+key,record,pos,0))
+    /* we don't need to delete non-inserted key from rb-tree */
+    keydef--;
+  }
+  while (keydef >= share->keydef)
+  {
+    if ((*keydef->delete_key)(info, keydef, record, pos, 0))
       break;
-  } while (key-- > 0);
+    keydef--;
+  } 
 
   share->deleted++;
   *((byte**) pos)=share->del_link;
@@ -77,6 +84,35 @@ err:
   DBUG_RETURN(my_errno);
 } /* heap_write */
 
+/* 
+  Write a key to rb_tree-index 
+*/
+
+int hp_rb_write_key(HP_INFO *info, HP_KEYDEF *keyinfo, const byte *record, 
+                  byte *recpos)
+{
+  heap_rb_param custom_arg;
+
+  info->last_pos = NULL; /* For heap_rnext/heap_rprev */
+  hp_rb_make_key(keyinfo, info->recbuf, record, recpos);
+  custom_arg.keyseg = keyinfo->seg;
+  custom_arg.key_length = keyinfo->length;
+  if ((keyinfo->flag & HA_NOSAME) &&
+      (!(keyinfo->flag & HA_NULL_PART_KEY) ||
+       !hp_if_null_in_key(keyinfo, record)))
+  {
+    custom_arg.search_flag = SEARCH_FIND | SEARCH_SAME;
+    if (tree_search_key(&keyinfo->rb_tree, info->recbuf, info->parents, 
+	&info->last_pos, 0, &custom_arg))
+    {
+      my_errno = HA_ERR_FOUND_DUPP_KEY;
+      return 1;
+    }
+  }
+  custom_arg.search_flag = SEARCH_SAME;
+  return tree_insert(&keyinfo->rb_tree, (void*)info->recbuf, keyinfo->length + 
+                     sizeof(byte*), &custom_arg) ? 0 : 1;
+}
 
 	/* Find where to place new record */
 
@@ -102,7 +138,7 @@ static byte *next_free_record_pos(HP_SHARE *info)
       my_errno=HA_ERR_RECORD_FILE_FULL;
       DBUG_RETURN(NULL);
     }
-    if (_hp_get_new_block(&info->block,&length))
+    if (hp_get_new_block(&info->block,&length))
       DBUG_RETURN(NULL);
     info->data_length+=length;
   }
@@ -113,12 +149,12 @@ static byte *next_free_record_pos(HP_SHARE *info)
 	      block_pos*info->block.recbuffer);
 }
 
-
 	/* Write a hash-key to the hash-index */
 
-int _hp_write_key(register HP_SHARE *info, HP_KEYDEF *keyinfo,
+int hp_write_key(HP_INFO *info, HP_KEYDEF *keyinfo,
 		  const byte *record, byte *recpos)
 {
+  HP_SHARE *share = info->s;
   int flag;
   ulong halfbuff,hashnr,first_index;
   byte *ptr_to_rec,*ptr_to_rec2;
@@ -129,18 +165,18 @@ int _hp_write_key(register HP_SHARE *info, HP_KEYDEF *keyinfo,
   LINT_INIT(ptr_to_rec); LINT_INIT(ptr_to_rec2);
 
   flag=0;
-  if (!(empty= _hp_find_free_hash(info,&keyinfo->block,info->records)))
+  if (!(empty= hp_find_free_hash(share,&keyinfo->block,share->records)))
     DBUG_RETURN(-1);				/* No more memory */
-  halfbuff= (long) info->blength >> 1;
-  pos=	 hp_find_hash(&keyinfo->block,(first_index=info->records-halfbuff));
+  halfbuff= (long) share->blength >> 1;
+  pos= hp_find_hash(&keyinfo->block,(first_index=share->records-halfbuff));
 
   if (pos != empty)				/* If some records */
   {
     do
     {
-      hashnr=_hp_rec_hashnr(keyinfo,pos->ptr_to_rec);
+      hashnr = hp_rec_hashnr(keyinfo, pos->ptr_to_rec);
       if (flag == 0)				/* First loop; Check if ok */
-	if (_hp_mask(hashnr,info->blength,info->records) != first_index)
+	if (hp_mask(hashnr, share->blength, share->records) != first_index)
 	  break;
       if (!(hashnr & halfbuff))
       {						/* Key will not move */
@@ -212,8 +248,8 @@ int _hp_write_key(register HP_SHARE *info, HP_KEYDEF *keyinfo,
   }
   /* Check if we are at the empty position */
 
-  pos=hp_find_hash(&keyinfo->block,_hp_mask(_hp_rec_hashnr(keyinfo,record),
-					    info->blength,info->records+1));
+  pos=hp_find_hash(&keyinfo->block, hp_mask(hp_rec_hashnr(keyinfo, record),
+					 share->blength, share->records + 1));
   if (pos == empty)
   {
     pos->ptr_to_rec=recpos;
@@ -224,8 +260,8 @@ int _hp_write_key(register HP_SHARE *info, HP_KEYDEF *keyinfo,
     /* Check if more records in same hash-nr family */
     empty[0]=pos[0];
     gpos=hp_find_hash(&keyinfo->block,
-		      _hp_mask(_hp_rec_hashnr(keyinfo,pos->ptr_to_rec),
-			       info->blength,info->records+1));
+		      hp_mask(hp_rec_hashnr(keyinfo, pos->ptr_to_rec),
+			      share->blength, share->records + 1));
     if (pos == gpos)
     {
       pos->ptr_to_rec=recpos;
@@ -235,7 +271,7 @@ int _hp_write_key(register HP_SHARE *info, HP_KEYDEF *keyinfo,
     {
       pos->ptr_to_rec=recpos;
       pos->next_key=0;
-      _hp_movelink(pos,gpos,empty);
+      hp_movelink(pos, gpos, empty);
     }
 
     /* Check if duplicated keys */
@@ -246,7 +282,7 @@ int _hp_write_key(register HP_SHARE *info, HP_KEYDEF *keyinfo,
       pos=empty;
       do
       {
-	if (! _hp_rec_key_cmp(keyinfo,record,pos->ptr_to_rec))
+	if (! hp_rec_key_cmp(keyinfo, record, pos->ptr_to_rec))
 	{
 	  DBUG_RETURN(my_errno=HA_ERR_FOUND_DUPP_KEY);
 	}
@@ -258,7 +294,7 @@ int _hp_write_key(register HP_SHARE *info, HP_KEYDEF *keyinfo,
 
 	/* Returns ptr to block, and allocates block if neaded */
 
-static HASH_INFO *_hp_find_free_hash(HP_SHARE *info,
+static HASH_INFO *hp_find_free_hash(HP_SHARE *info,
 				     HP_BLOCK *block, ulong records)
 {
   uint block_pos;
@@ -268,7 +304,7 @@ static HASH_INFO *_hp_find_free_hash(HP_SHARE *info,
     return hp_find_hash(block,records);
   if (!(block_pos=(records % block->records_in_block)))
   {
-    if (_hp_get_new_block(block,&length))
+    if (hp_get_new_block(block,&length))
       return(NULL);
     info->index_length+=length;
   }