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, 11 deletions

diff --git a/include/heap.h b/include/heap.h
index 02b04e2b3ec..ebcad285f55 100644
--- a/include/heap.h
+++ b/include/heap.h
@@ -14,7 +14,7 @@
    along with this program; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
 
-/* This file should be included when using heap_database_funktions */
+/* This file should be included when using heap_database_functions */
 /* Author: Michael Widenius */
 
 #ifndef _heap_h
@@ -31,6 +31,9 @@ extern "C" {
 #include <thr_lock.h>
 #endif
 
+#include "my_handler.h"
+#include "my_tree.h"
+
 	/* defines used by heap-funktions */
 
 #define HP_MAX_LEVELS	4		/* 128^5 records is enough */
@@ -73,22 +76,22 @@ typedef struct st_heap_block		/* The data is saved in blocks */
   ulong last_allocated;			/* Blocks allocated, used by keys */
 } HP_BLOCK;
 
-typedef struct st_hp_keyseg		/* Key-portion */
-{
-  uint start;				/* Start of key in record (from 0) */
-  uint length;				/* Keylength */
-  uint type;
-  uint null_bit;			/* bit set in row+null_pos */
-  uint null_pos;
-} HP_KEYSEG;
+struct st_heap_info;			/* For referense */
 
 typedef struct st_hp_keydef		/* Key definition with open */
 {
   uint flag;				/* HA_NOSAME | HA_NULL_PART_KEY */
   uint keysegs;				/* Number of key-segment */
   uint length;				/* Length of key (automatic) */
-  HP_KEYSEG *seg;
+  uint8 algorithm;			/* HASH / BTREE */
+  uint ref_offs;			/* Data reference offset */
+  MI_KEYSEG *seg;
   HP_BLOCK block;			/* Where keys are saved */
+  TREE rb_tree;
+  int (*write_key)(struct st_heap_info *info, struct st_hp_keydef *keyinfo,
+		   const byte *record, byte *recpos);
+  int (*delete_key)(struct st_heap_info *info, struct st_hp_keydef *keyinfo, 
+  		   const byte *record, byte *recpos, int flag);
 } HP_KEYDEF;
 
 typedef struct st_heap_share
@@ -126,6 +129,11 @@ typedef struct st_heap_info
   int  mode;				/* Mode of file (READONLY..) */
   uint opt_flag,update;
   byte *lastkey;			/* Last used key with rkey */
+  byte *recbuf;                         /* Record buffer for rb-tree keys */
+  enum ha_rkey_function last_find_flag;
+  TREE_ELEMENT *parents[MAX_TREE_HIGHT+1];
+  TREE_ELEMENT **last_pos;
+  uint lastkey_len;
 #ifdef THREAD
   THR_LOCK_DATA lock;
 #endif
@@ -156,7 +164,14 @@ extern int heap_rprev(HP_INFO *info,byte *record);
 extern int heap_rfirst(HP_INFO *info,byte *record);
 extern int heap_rlast(HP_INFO *info,byte *record);
 extern void heap_clear(HP_INFO *info);
-extern int heap_rkey(HP_INFO *info,byte *record,int inx,const byte *key);
+
+ha_rows hp_rb_records_in_range(HP_INFO *info, int inx, const byte *start_key,
+			       uint start_key_len,
+			       enum ha_rkey_function start_search_flag,
+			       const byte *end_key, uint end_key_len,
+			       enum ha_rkey_function end_search_flag);
+int heap_rkey(HP_INFO *info, byte *record, int inx, const byte *key, 
+              uint key_len, enum ha_rkey_function find_flag);
 extern gptr heap_find(HP_INFO *info,int inx,const byte *key);
 extern int heap_check_heap(HP_INFO *info, my_bool print_status);
 extern byte *heap_position(HP_INFO *info);