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, 15 insertions, 3 deletions

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