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, 67 insertions, 36 deletions

diff --git a/sql/ha_heap.cc b/sql/ha_heap.cc
index 5f482bca1e8..8a4758aa558 100644
--- a/sql/ha_heap.cc
+++ b/sql/ha_heap.cc
@@ -36,42 +36,59 @@ int ha_heap::open(const char *name, int mode, uint test_if_locked)
   uint key,parts,mem_per_row=0;
   ulong max_rows;
   HP_KEYDEF *keydef;
-  HP_KEYSEG *seg;
+  MI_KEYSEG *seg;
 
   for (key=parts=0 ; key < table->keys ; key++)
+  {
     parts+=table->key_info[key].key_parts;
+    if (table->key_info[key].algorithm == HA_KEY_ALG_BTREE)
+    {
+      parts++; /* additional HA_KEYTYPE_END keyseg */
+    }
+  }
 
   if (!(keydef=(HP_KEYDEF*) my_malloc(table->keys*sizeof(HP_KEYDEF)+
-				      parts*sizeof(HP_KEYSEG),MYF(MY_WME))))
+				      parts*sizeof(MI_KEYSEG),MYF(MY_WME))))
     return my_errno;
-  seg=my_reinterpret_cast(HP_KEYSEG*) (keydef+table->keys);
+  seg=my_reinterpret_cast(MI_KEYSEG*) (keydef+table->keys);
   for (key=0 ; key < table->keys ; key++)
   {
     KEY *pos=table->key_info+key;
     KEY_PART_INFO *key_part=     pos->key_part;
     KEY_PART_INFO *key_part_end= key_part+pos->key_parts;
 
-    mem_per_row += (pos->key_length + (sizeof(char*) * 2));
+    mem_per_row+= (pos->key_length + (sizeof(char*) * 2));
 
-    keydef[key].keysegs=(uint) pos->key_parts;
-    keydef[key].flag = (pos->flags & (HA_NOSAME | HA_NULL_ARE_EQUAL));
-    keydef[key].seg=seg;
+    keydef[key].keysegs=   (uint) pos->key_parts;
+    keydef[key].flag=      (pos->flags & (HA_NOSAME | HA_NULL_ARE_EQUAL));
+    keydef[key].seg=       seg;
+    keydef[key].algorithm= pos->algorithm == HA_KEY_ALG_UNDEF ? 
+					HA_KEY_ALG_HASH : pos->algorithm;
 
     for (; key_part != key_part_end ; key_part++, seg++)
     {
-      uint flag=key_part->key_type;
-      Field *field=key_part->field;
-      if (!f_is_packed(flag) &&
-	  f_packtype(flag) == (int) FIELD_TYPE_DECIMAL &&
-	  !(flag & FIELDFLAG_BINARY))
-	seg->type= (int) HA_KEYTYPE_TEXT;
+      uint flag= key_part->key_type;
+      Field *field= key_part->field;
+      if (pos->algorithm == HA_KEY_ALG_BTREE)
+      {
+	seg->type= field->key_type();
+      }
       else
-	seg->type= (int) HA_KEYTYPE_BINARY;
-      seg->start=(uint) key_part->offset;
-      seg->length=(uint) key_part->length;
+      {
+	if (!f_is_packed(flag) &&
+	    f_packtype(flag) == (int) FIELD_TYPE_DECIMAL &&
+	    !(flag & FIELDFLAG_BINARY))
+	  seg->type= (int) HA_KEYTYPE_TEXT;
+	else
+	  seg->type= (int) HA_KEYTYPE_BINARY;
+      }
+      seg->start=   (uint) key_part->offset;
+      seg->length=  (uint) key_part->length;
+      seg->flag =   0;
+      seg->charset= default_charset_info;
       if (field->null_ptr)
       {
-	seg->null_bit=field->null_bit;
+	seg->null_bit= field->null_bit;
 	seg->null_pos= (uint) (field->null_ptr-
 			       (uchar*) table->record[0]);
       }
@@ -81,6 +98,16 @@ int ha_heap::open(const char *name, int mode, uint test_if_locked)
 	seg->null_pos=0;
       }
     }
+    if (pos->algorithm == HA_KEY_ALG_BTREE)
+    {
+      /* additional HA_KEYTYPE_END keyseg */
+      keydef[key].keysegs++;
+      seg->type=     HA_KEYTYPE_END;
+      seg->length=   sizeof(byte*);
+      seg->flag=     0;
+      seg->null_bit= 0;
+      seg++;
+    }
   }
   mem_per_row += MY_ALIGN(table->reclength+1, sizeof(char*));
   max_rows = (ulong) (max_heap_table_size / mem_per_row);
@@ -124,25 +151,21 @@ int ha_heap::delete_row(const byte * buf)
   return heap_delete(file,buf);
 }
 
-int ha_heap::index_read(byte * buf, const byte * key,
-			uint key_len __attribute__((unused)),
-			enum ha_rkey_function find_flag
-			__attribute__((unused)))
+int ha_heap::index_read(byte * buf, const byte * key, uint key_len,
+			enum ha_rkey_function find_flag)
 {
-  statistic_increment(ha_read_key_count,&LOCK_status);
-  int error=heap_rkey(file,buf,active_index, key);
-  table->status=error ? STATUS_NOT_FOUND: 0;
+  statistic_increment(ha_read_key_count, &LOCK_status);
+  int error = heap_rkey(file,buf,active_index, key, key_len, find_flag);
+  table->status = error ? STATUS_NOT_FOUND : 0;
   return error;
 }
 
 int ha_heap::index_read_idx(byte * buf, uint index, const byte * key,
-			    uint key_len __attribute__((unused)),
-			    enum ha_rkey_function find_flag
-			    __attribute__((unused)))
+			    uint key_len, enum ha_rkey_function find_flag)
 {
-  statistic_increment(ha_read_key_count,&LOCK_status);
-  int error=heap_rkey(file, buf, index, key);
-  table->status=error ? STATUS_NOT_FOUND: 0;
+  statistic_increment(ha_read_key_count, &LOCK_status);
+  int error = heap_rkey(file, buf, index, key, key_len, find_flag);
+  table->status = error ? STATUS_NOT_FOUND : 0;
   return error;
 }
 
@@ -279,12 +302,20 @@ ha_rows ha_heap::records_in_range(int inx,
 				  enum ha_rkey_function end_search_flag)
 {
   KEY *pos=table->key_info+inx;
-  if (start_key_len != end_key_len ||
-      start_key_len != pos->key_length ||
-      start_search_flag != HA_READ_KEY_EXACT ||
-      end_search_flag != HA_READ_AFTER_KEY)
-    return HA_POS_ERROR;			// Can't only use exact keys
-  return 10;					// Good guess
+  if (pos->algorithm == HA_KEY_ALG_BTREE)
+  {
+    return hp_rb_records_in_range(file, inx, start_key, start_key_len,
+             start_search_flag, end_key, end_key_len, end_search_flag);
+  }
+  else
+  {
+    if (start_key_len != end_key_len ||
+        start_key_len != pos->key_length ||
+        start_search_flag != HA_READ_KEY_EXACT ||
+        end_search_flag != HA_READ_AFTER_KEY)
+      return HA_POS_ERROR;			// Can't only use exact keys
+    return 10;					// Good guess
+  }
 }