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

5 files changed, 106 insertions, 29 deletions

diff --git a/include/Makefile.am b/include/Makefile.am
index b943e8d76e6..8cf9c7c5a78 100644
--- a/include/Makefile.am
+++ b/include/Makefile.am
@@ -29,7 +29,7 @@ noinst_HEADERS =	config-win.h \
 			my_nosys.h my_alarm.h queues.h \
 			my_tree.h hash.h thr_alarm.h thr_lock.h \
 			getopt.h my_getopt.h t_ctype.h violite.h md5.h \
-			mysql_version.h.in
+			my_handler.h mysql_version.h.in
 
 # mysql_version.h are generated
 SUPERCLEANFILES =	mysql_version.h my_config.h
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);
diff --git a/include/my_handler.h b/include/my_handler.h
new file mode 100644
index 00000000000..ddbb33cd93f
--- /dev/null
+++ b/include/my_handler.h
@@ -0,0 +1,63 @@
+/* Copyright (C) 2000 MySQL AB & MySQL Finland AB & TCX DataKonsult AB
+   
+   This library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Library General Public
+   License as published by the Free Software Foundation; either
+   version 2 of the License, or (at your option) any later version.
+   
+   This library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Library General Public License for more details.
+   
+   You should have received a copy of the GNU Library General Public
+   License along with this library; if not, write to the Free
+   Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
+   MA 02111-1307, USA */
+
+#ifndef _my_handler_h
+#define _my_handler_h
+
+#include "my_global.h"
+#include "my_base.h"
+#include "m_ctype.h"
+#include "myisampack.h"
+
+typedef struct st_MI_KEYSEG		/* Key-portion */
+{
+  uint8  type;				/* Type of key (for sort) */
+  uint8  language;
+  uint8  null_bit;			/* bitmask to test for NULL */
+  uint8  bit_start,bit_end;		/* if bit field */
+  uint16 flag;
+  uint16 length;			/* Keylength */
+  uint32 start;				/* Start of key in record */
+  uint32 null_pos;			/* position to NULL indicator */
+  CHARSET_INFO *charset;
+} MI_KEYSEG;
+
+#define get_key_length(length,key) \
+{ if ((uchar) *(key) != 255) \
+    length= (uint) (uchar) *((key)++); \
+  else \
+  { length=mi_uint2korr((key)+1); (key)+=3; } \
+}
+
+#define get_key_pack_length(length,length_pack,key) \
+{ if ((uchar) *(key) != 255) \
+  { length= (uint) (uchar) *((key)++); length_pack=1; }\
+  else \
+  { length=mi_uint2korr((key)+1); (key)+=3; length_pack=3; } \
+}
+
+extern int _mi_compare_text(CHARSET_INFO *, uchar *, uint, uchar *, uint ,
+			    my_bool);
+extern int _mi_key_cmp(register MI_KEYSEG *keyseg, register uchar *a,
+		       register uchar *b, uint key_length, uint nextflag,
+		       uint *diff_pos);
+
+extern int hp_rb_key_cmp(register MI_KEYSEG *keyseg, register uchar *a,
+			 register uchar *b, uint key_length, uint nextflag,
+			 uint *diff_pos);
+
+#endif /* _my_handler_h */
diff --git a/include/my_tree.h b/include/my_tree.h
index 8b326a19518..265bf69b1e7 100644
--- a/include/my_tree.h
+++ b/include/my_tree.h
@@ -48,6 +48,8 @@ typedef struct st_tree_element {
 } TREE_ELEMENT;
 #endif /* MSDOS */
 
+#define ELEMENT_CHILD(element, offs) (*(TREE_ELEMENT**)((char*)element + offs))
+
 typedef struct st_tree {
   TREE_ELEMENT *root,null_element;
   TREE_ELEMENT **parents[MAX_TREE_HIGHT];
@@ -70,12 +72,22 @@ void reset_tree(TREE*);
 #define is_tree_inited(tree) ((tree)->root != 0)
 
 	/* Functions on leafs */
-TREE_ELEMENT *tree_insert(TREE *tree,void *key,uint key_size);
-void *tree_search(TREE *tree,void *key);
+TREE_ELEMENT *tree_insert(TREE *tree,void *key, uint key_size, 
+                          void *custom_arg);
+void *tree_search(TREE *tree, void *key, void *custom_arg);
 int tree_walk(TREE *tree,tree_walk_action action,
 	      void *argument, TREE_WALK visit);
-int tree_delete(TREE *tree,void *key);
+int tree_delete(TREE *tree, void *key, void *custom_arg);
 
+void *tree_search_key(TREE *tree, const void *key, 
+                      TREE_ELEMENT **parents, TREE_ELEMENT ***last_pos,
+                      enum ha_rkey_function flag, void *custom_arg);
+void *tree_search_edge(TREE *tree, TREE_ELEMENT **parents, 
+                        TREE_ELEMENT ***last_pos, int child_offs);
+void *tree_search_next(TREE *tree, TREE_ELEMENT ***last_pos, int l_offs, 
+                       int r_offs);
+uint tree_record_pos(TREE *tree, const void *key, 
+                     enum ha_rkey_function search_flag, void *custom_arg);
 #ifdef	__cplusplus
 }
 #endif
diff --git a/include/myisam.h b/include/myisam.h
index ecf34a7e156..bf714dfef8a 100644
--- a/include/myisam.h
+++ b/include/myisam.h
@@ -28,6 +28,7 @@ extern "C" {
 #ifndef _m_ctype_h
 #include <m_ctype.h>
 #endif
+#include "my_handler.h"
 
 	/* defines used by myisam-funktions */
 
@@ -105,20 +106,6 @@ typedef struct st_mi_create_info
 struct st_myisam_info;			/* For referense */
 typedef struct st_myisam_info MI_INFO;
 
-typedef struct st_mi_keyseg		/* Key-portion */
-{
-  uint8  type;				/* Type of key (for sort) */
-  uint8  language;
-  uint8  null_bit;			/* bitmask to test for NULL */
-  uint8  bit_start,bit_end;		/* if bit field */
-  uint16 flag;
-  uint16 length;			/* Keylength */
-  uint32 start;				/* Start of key in record */
-  uint32 null_pos;			/* position to NULL indicator */
-  CHARSET_INFO *charset;
-} MI_KEYSEG;
-
-
 struct st_mi_s_param;
 
 typedef struct st_mi_keydef		/* Key definition with open & info */