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, 140 insertions, 0 deletions

diff --git a/mysql-test/t/heap_btree.test b/mysql-test/t/heap_btree.test
new file mode 100644
index 00000000000..28fc209525b
--- /dev/null
+++ b/mysql-test/t/heap_btree.test
@@ -0,0 +1,140 @@
+#
+# Test of heap tables.
+#
+
+drop table if exists t1;
+create table t1 (a int not null,b int not null, primary key using BTREE (a)) type=heap comment="testing heaps" avg_row_length=100 min_rows=1 max_rows=100;
+insert into t1 values(1,1),(2,2),(3,3),(4,4);
+delete from t1 where a=1 or a=0;
+#show table status like "t1";
+show keys from t1;
+select * from t1;
+select * from t1 where a=4;
+update t1 set b=5 where a=4;
+update t1 set b=b+1 where a>=3;
+replace t1 values (3,3);
+select * from t1;
+alter table t1 add c int not null, add key using BTREE (c,a);
+drop table t1;
+
+create table t1 (a int not null,b int not null, primary key using BTREE (a)) type=heap comment="testing heaps";
+insert into t1 values(1,1),(2,2),(3,3),(4,4);
+delete from t1 where a > 0;
+select * from t1;
+drop table t1;
+
+create table t1 (a int not null,b int not null, primary key using BTREE (a)) type=heap comment="testing heaps";
+insert into t1 values(1,1),(2,2),(3,3),(4,4);
+alter table t1 modify a int not null auto_increment, type=myisam, comment="new myisam table";
+#show table status like "t1";
+select * from t1;
+drop table t1;
+
+create table t1 (a int not null) type=heap;
+insert into t1 values (869751),(736494),(226312),(802616);
+select * from t1 where a > 736494;
+alter table t1 add unique uniq_id using BTREE (a);
+select * from t1 where a > 736494;
+select * from t1 where a = 736494;
+select * from t1 where a=869751 or a=736494;
+select * from t1 where a in (869751,736494,226312,802616);
+alter table t1 type=myisam;
+explain select * from t1 where a in (869751,736494,226312,802616);
+drop table t1;
+
+create table t1 (x int not null, y int not null, key x  using BTREE (x), unique y  using BTREE (y))
+type=heap;
+insert into t1 values (1,1),(2,2),(1,3),(2,4),(2,5),(2,6);
+select * from t1 where x=1;
+select * from t1,t1 as t2 where t1.x=t2.y;
+explain select * from t1,t1 as t2 where t1.x=t2.y;
+drop table t1;
+
+create table t1 (a int) type=heap;
+insert into t1 values(1);
+select max(a) from t1;
+drop table t1;
+
+CREATE TABLE t1 ( a int not null default 0, b int not null default 0,  key  using BTREE (a),  key  using BTREE (b)  ) TYPE=HEAP;
+insert into t1 values(1,1),(1,2),(2,3),(1,3),(1,4),(1,5),(1,6);
+select * from t1 where a=1; 
+insert into t1 values(1,1),(1,2),(2,3),(1,3),(1,4),(1,5),(1,6);
+select * from t1 where a=1;
+drop table t1;
+
+create table t1 (id int unsigned not null, primary key  using BTREE (id)) type=HEAP;
+insert into t1 values(1);
+select max(id) from t1; 
+insert into t1 values(2);
+select max(id) from t1; 
+replace into t1 values(1);
+drop table t1;
+
+create table t1 (n int) type=heap;
+drop table t1;
+
+create table t1 (n int) type=heap;
+drop table if exists t1;
+
+# Test of non unique index
+
+CREATE table t1(f1 int not null,f2 char(20) not 
+null,index(f2)) type=heap;
+INSERT into t1 set f1=12,f2="bill";
+INSERT into t1 set f1=13,f2="bill";
+INSERT into t1 set f1=14,f2="bill";
+INSERT into t1 set f1=15,f2="bill";
+INSERT into t1 set f1=16,f2="ted";
+INSERT into t1 set f1=12,f2="ted";
+INSERT into t1 set f1=12,f2="ted";
+INSERT into t1 set f1=12,f2="ted";
+INSERT into t1 set f1=12,f2="ted";
+delete from t1 where f2="bill";
+select * from t1;
+drop table t1;
+
+#
+# Test when using part key searches
+#
+
+create table t1 (btn char(10) not null, key using BTREE (btn)) type=heap;
+insert into t1 values ("hello"),("hello"),("hello"),("hello"),("hello"),("a"),("b"),("c"),("d"),("e"),("f"),("g"),("h"),("i");
+explain select * from t1 where btn like "q%";
+select * from t1 where btn like "q%";
+alter table t1 add column new_col char(1) not null, add key using BTREE (btn,new_col), drop key btn;
+update t1 set new_col=btn;
+explain select * from t1 where btn="a";
+explain select * from t1 where btn="a" and new_col="a";
+drop table t1;
+
+#
+# Test of NULL keys
+#
+
+CREATE TABLE t1 (
+  a int default NULL,
+  b int default NULL,
+  KEY a using BTREE (a),
+  UNIQUE b using BTREE (b)
+) type=heap;
+INSERT INTO t1 VALUES (NULL,99),(99,NULL),(1,1),(2,2),(1,3);
+SELECT * FROM t1 WHERE a=NULL;
+explain SELECT * FROM t1 WHERE a IS NULL;
+SELECT * FROM t1 WHERE a<=>NULL;
+SELECT * FROM t1 WHERE b=NULL;
+explain SELECT * FROM t1 WHERE b IS NULL;
+SELECT * FROM t1 WHERE b<=>NULL;
+
+--error 1062
+INSERT INTO t1 VALUES (1,3);
+DROP TABLE t1;
+
+#
+# Test when deleting all rows
+#
+
+CREATE TABLE t1 (a int not null, primary key using BTREE (a)) type=heap;
+INSERT into t1 values (1),(2),(3),(4),(5),(6),(7),(8),(9),(10),(11);
+DELETE from t1 where a < 100;
+SELECT * from t1;
+DROP TABLE t1;