Adding upstream version 1:10.11.6.upstream/1%10.11.6upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

33 files changed, 5689 insertions, 0 deletions

diff --git a/storage/heap/CMakeLists.txt b/storage/heap/CMakeLists.txt
new file mode 100644
index 00000000..a26124d0
--- /dev/null
+++ b/storage/heap/CMakeLists.txt
@@ -0,0 +1,35 @@
+# Copyright (c) 2006, 2010, Oracle and/or its affiliates. All rights reserved.
+# 
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; version 2 of the License.
+# 
+# This program 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 General Public License for more details.
+# 
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software
+# Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1335 USA
+
+SET(HEAP_SOURCES  _check.c _rectest.c hp_block.c hp_clear.c hp_close.c hp_create.c
+				ha_heap.cc
+				hp_delete.c hp_extra.c hp_hash.c hp_info.c hp_open.c hp_panic.c
+				hp_rename.c hp_rfirst.c hp_rkey.c hp_rlast.c hp_rnext.c hp_rprev.c
+				hp_rrnd.c hp_rsame.c hp_scan.c hp_static.c hp_update.c hp_write.c)
+
+MYSQL_ADD_PLUGIN(heap ${HEAP_SOURCES} STORAGE_ENGINE MANDATORY RECOMPILE_FOR_EMBEDDED)
+
+IF(CMAKE_SYSTEM_NAME MATCHES AIX AND CMAKE_BUILD_TYPE STREQUAL "DEBUG")
+  # Workaround linker bug on AIX
+  SET(CMAKE_EXE_LINKER_FLAGS "${CMAKE_EXE_LINKER_FLAGS} -Wl,-berok")
+ENDIF()
+
+IF(WITH_UNIT_TESTS)
+  ADD_EXECUTABLE(hp_test1 hp_test1.c)
+  TARGET_LINK_LIBRARIES(hp_test1 heap mysys dbug strings)
+
+  ADD_EXECUTABLE(hp_test2 hp_test2.c)
+  TARGET_LINK_LIBRARIES(hp_test2 heap mysys dbug strings)
+ENDIF()
\ No newline at end of file
diff --git a/storage/heap/ChangeLog b/storage/heap/ChangeLog
new file mode 100644
index 00000000..b6bd0e43
--- /dev/null
+++ b/storage/heap/ChangeLog
@@ -0,0 +1,8 @@
+Sun Sep  6 10:56:59 1992  Michael Widenius  (monty@bitch)
+
+	* Added functions for first,next,last,prev and clear of database-heap
+	* Added optional index to rsame for compatibility.
+
+Fri Aug 14 14:34:35 1992  Michael Widenius  (monty@bitch)
+
+	* changed file parameter to HP_INFO *
diff --git a/storage/heap/_check.c b/storage/heap/_check.c
new file mode 100644
index 00000000..1a640fa1
--- /dev/null
+++ b/storage/heap/_check.c
@@ -0,0 +1,206 @@
+/* Copyright (c) 2000, 2002-2007 MySQL AB
+   Use is subject to license terms
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; version 2 of the License.
+
+   This program 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 General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1335  USA */
+
+/* Check that heap-structure is ok */
+
+#include "heapdef.h"
+
+static int check_one_key(HP_KEYDEF *, uint, ulong, ulong, my_bool);
+static int check_one_rb_key(const HP_INFO *, uint, ulong, my_bool);
+
+
+/*
+  Check if keys and rows are ok in a heap table
+
+  SYNOPSIS
+    heap_check_heap()
+    info		Table handler
+    print_status	Prints some extra status
+
+  NOTES
+    Doesn't change the state of the table handler
+
+  RETURN VALUES
+    0	ok
+    1 error
+*/
+
+int heap_check_heap(const HP_INFO *info, my_bool print_status)
+{
+  int error;
+  uint key;
+  ulong records=0, deleted=0, pos, next_block;
+  HP_SHARE *share=info->s;
+  uchar *current_ptr= info->current_ptr;
+  DBUG_ENTER("heap_check_heap");
+
+  for (error=key= 0 ; key < share->keys ; key++)
+  {
+    if (share->keydef[key].algorithm == HA_KEY_ALG_BTREE)
+      error|= check_one_rb_key(info, key, share->records, print_status);
+    else
+      error|= check_one_key(share->keydef + key, key, share->records,
+			    share->blength, print_status);
+  }
+  /*
+    This is basicly the same code as in hp_scan, but we repeat it here to
+    get shorter DBUG log file.
+  */
+  for (pos=next_block= 0 ; ; pos++)
+  {
+    if (pos < next_block)
+    {
+      current_ptr+= share->block.recbuffer;
+    }
+    else
+    {
+      next_block+= share->block.records_in_block;
+      if (next_block >= share->records+share->deleted)
+      {
+	next_block= share->records+share->deleted;
+	if (pos >= next_block)
+	  break;				/* End of file */
+      }
+    }
+    current_ptr= hp_find_block(&share->block, pos);
+
+    if (!current_ptr[share->visible])
+      deleted++;
+    else
+      records++;
+  }
+
+  if (records != share->records || deleted != share->deleted)
+  {
+    DBUG_PRINT("error",("Found rows: %lu (%lu)  deleted %lu (%lu)",
+			records, (ulong) share->records,
+                        deleted, (ulong) share->deleted));
+    error= 1;
+  }
+  DBUG_RETURN(error);
+}
+
+
+static int check_one_key(HP_KEYDEF *keydef, uint keynr, ulong records,
+			 ulong blength, my_bool print_status)
+{
+  int error;
+  ulong i,found,max_links,seek,links;
+  ulong rec_link;				/* Only used with debugging */
+  ulong hash_buckets_found;
+  HASH_INFO *hash_info;
+
+  error=0;
+  hash_buckets_found= 0;
+  for (i=found=max_links=seek=0 ; i < records ; i++)
+  {
+    hash_info=hp_find_hash(&keydef->block,i);
+    if (hash_info->hash_of_key != hp_rec_hashnr(keydef, hash_info->ptr_to_rec))
+    {
+      DBUG_PRINT("error",
+                 ("Found row with wrong hash_of_key at position %lu", i));
+      error= 1;
+    }
+    if (hp_mask(hash_info->hash_of_key, blength, records) == i)
+    {
+      found++;
+      seek++;
+      links=1;
+      while ((hash_info=hash_info->next_key) && found < records + 1)
+      {
+	seek+= ++links;
+	if ((rec_link= hp_mask(hash_info->hash_of_key, blength, records)) != i)
+	{
+	  DBUG_PRINT("error",
+                     ("Record in wrong link: Link %lu  Record: %p  Record-link %lu",
+                      i, hash_info->ptr_to_rec, rec_link));
+	  error=1;
+	}
+	else
+	  found++;
+      }
+      if (links > max_links) max_links=links;
+      hash_buckets_found++;
+    }
+  }
+  if (found != records)
+  {
+    DBUG_PRINT("error",("Found %ld of %ld records", found, records));
+    error=1;
+  }
+  if (keydef->hash_buckets != hash_buckets_found)
+  {
+    DBUG_PRINT("error",("Found %ld buckets, stats shows %ld buckets",
+                        hash_buckets_found, (long) keydef->hash_buckets));
+    error=1;
+  }
+  DBUG_PRINT("info",
+	     ("key: %u  records: %ld  seeks: %lu  max links: %lu  "
+              "hitrate: %.2f  buckets: %lu",
+	      keynr, records,seek,max_links,
+	      (float) seek / (float) (records ? records : 1), 
+              hash_buckets_found));
+  if (print_status)
+    printf("Key: %u  records: %ld  seeks: %lu  max links: %lu  "
+           "hitrate: %.2f  buckets: %lu\n",
+	   keynr, records, seek, max_links,
+	   (float) seek / (float) (records ? records : 1), 
+           hash_buckets_found);
+  return error;
+}
+
+static int check_one_rb_key(const HP_INFO *info, uint keynr, ulong records,
+			    my_bool print_status)
+{
+  HP_KEYDEF *keydef= info->s->keydef + keynr;
+  int error= 0;
+  ulong found= 0;
+  uchar *key, *recpos;
+  uint key_length;
+  uint not_used[2];
+  TREE_ELEMENT **last_pos;
+  TREE_ELEMENT *parents[MAX_TREE_HEIGHT+1];
+  
+  if ((key= tree_search_edge(&keydef->rb_tree, parents,
+			     &last_pos, offsetof(TREE_ELEMENT, left))))
+  {
+    do
+    {
+      memcpy(&recpos, key + (*keydef->get_key_length)(keydef,key), sizeof(uchar*));
+      key_length= hp_rb_make_key(keydef, info->recbuf, recpos, 0);
+      if (ha_key_cmp(keydef->seg, (uchar*) info->recbuf, (uchar*) key,
+		     key_length, SEARCH_FIND | SEARCH_SAME, not_used))
+      {
+	error= 1;
+	DBUG_PRINT("error",("Record in wrong link:  key: %u  Record: %p\n", 
+			    keynr, recpos));
+      }
+      else
+	found++;
+      key= tree_search_next(&keydef->rb_tree, &last_pos,
+			    offsetof(TREE_ELEMENT, left), 
+			    offsetof(TREE_ELEMENT, right));
+    } while (key);
+  }
+  if (found != records)
+  {
+    DBUG_PRINT("error",("Found %lu of %lu records", found, records));
+    error= 1;
+  }
+  if (print_status)
+    printf("Key: %d  records: %ld\n", keynr, records);
+  return error;
+}
diff --git a/storage/heap/_rectest.c b/storage/heap/_rectest.c
new file mode 100644
index 00000000..f611ad55
--- /dev/null
+++ b/storage/heap/_rectest.c
@@ -0,0 +1,31 @@
+/* Copyright (c) 2000-2002, 2005-2007 MySQL AB
+   Use is subject to license terms
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; version 2 of the License.
+
+   This program 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 General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1335  USA */
+
+/* Test if a record has changed since last read */
+/* In heap this is only used when debugging */
+
+#include "heapdef.h"
+
+int hp_rectest(register HP_INFO *info, register const uchar *old)
+{
+  DBUG_ENTER("hp_rectest");
+
+  if (memcmp(info->current_ptr,old,(size_t) info->s->reclength))
+  {
+    DBUG_RETURN((my_errno=HA_ERR_RECORD_CHANGED)); /* Record have changed */
+  }
+  DBUG_RETURN(0);
+} /* _heap_rectest */
diff --git a/storage/heap/ha_heap.cc b/storage/heap/ha_heap.cc
new file mode 100644
index 00000000..5f7f0c1e
--- /dev/null
+++ b/storage/heap/ha_heap.cc
@@ -0,0 +1,850 @@
+/*
+   Copyright (c) 2000, 2011, Oracle and/or its affiliates
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; version 2 of the License.
+
+   This program 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 General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1335  USA */
+
+
+#ifdef USE_PRAGMA_IMPLEMENTATION
+#pragma implementation				// gcc: Class implementation
+#endif
+
+#define MYSQL_SERVER 1
+#include "heapdef.h"
+#include "sql_priv.h"
+#include "sql_plugin.h"
+#include "ha_heap.h"
+#include "sql_base.h"
+
+static handler *heap_create_handler(handlerton *, TABLE_SHARE *, MEM_ROOT *);
+static int heap_prepare_hp_create_info(TABLE *, bool, HP_CREATE_INFO *);
+
+
+static int heap_panic(handlerton *hton, ha_panic_function flag)
+{
+  return hp_panic(flag);
+}
+
+
+static int heap_drop_table(handlerton *hton, const char *path)
+{
+  int error= heap_delete_table(path);
+  return error == ENOENT ? -1 : error;
+}
+
+int heap_init(void *p)
+{
+  handlerton *heap_hton;
+
+  init_heap_psi_keys();
+
+  heap_hton= (handlerton *)p;
+  heap_hton->db_type=    DB_TYPE_HEAP;
+  heap_hton->create=     heap_create_handler;
+  heap_hton->panic=      heap_panic;
+  heap_hton->drop_table= heap_drop_table;
+  heap_hton->flags=      HTON_CAN_RECREATE;
+
+  return 0;
+}
+
+static handler *heap_create_handler(handlerton *hton,
+                                    TABLE_SHARE *table, 
+                                    MEM_ROOT *mem_root)
+{
+  return new (mem_root) ha_heap(hton, table);
+}
+
+
+/*****************************************************************************
+** HEAP tables
+*****************************************************************************/
+
+ha_heap::ha_heap(handlerton *hton, TABLE_SHARE *table_arg)
+  :handler(hton, table_arg), file(0), records_changed(0), key_stat_version(0), 
+  internal_table(0)
+{}
+
+/*
+  Hash index statistics is updated (copied from HP_KEYDEF::hash_buckets to 
+  rec_per_key) after 1/HEAP_STATS_UPDATE_THRESHOLD fraction of table records 
+  have been inserted/updated/deleted. delete_all_rows() and table flush cause 
+  immediate update.
+
+  NOTE
+   hash index statistics must be updated when number of table records changes
+   from 0 to non-zero value and vice versa. Otherwise records_in_range may 
+   erroneously return 0 and 'range' may miss records.
+*/
+#define HEAP_STATS_UPDATE_THRESHOLD 10
+
+int ha_heap::open(const char *name, int mode, uint test_if_locked)
+{
+  internal_table= MY_TEST(test_if_locked & HA_OPEN_INTERNAL_TABLE);
+  if (internal_table || (!(file= heap_open(name, mode)) && my_errno == ENOENT))
+  {
+    HP_CREATE_INFO create_info;
+    my_bool created_new_share;
+    int rc;
+    file= 0;
+    if (heap_prepare_hp_create_info(table, internal_table, &create_info))
+      goto end;
+    create_info.pin_share= TRUE;
+
+    rc= heap_create(name, &create_info, &internal_share, &created_new_share);
+    my_free(create_info.keydef);
+    if (rc)
+      goto end;
+
+    implicit_emptied= MY_TEST(created_new_share);
+    if (internal_table)
+      file= heap_open_from_share(internal_share, mode);
+    else
+      file= heap_open_from_share_and_register(internal_share, mode);
+
+    if (!file)
+    {
+      heap_release_share(internal_share, internal_table);
+      goto end;
+    }
+  }
+
+  ref_length= sizeof(HEAP_PTR);
+  /* Initialize variables for the opened table */
+  set_keys_for_scanning();
+  /*
+    We cannot run update_key_stats() here because we do not have a
+    lock on the table. The 'records' count might just be changed
+    temporarily at this moment and we might get wrong statistics (Bug
+    #10178). Instead we request for update. This will be done in
+    ha_heap::info(), which is always called before key statistics are
+    used.
+    */
+  key_stat_version= file->s->key_stat_version-1;
+end:
+  return (file ? 0 : 1);
+}
+
+int ha_heap::close(void)
+{
+  return internal_table ? hp_close(file) : heap_close(file);
+}
+
+
+/*
+  Create a copy of this table
+
+  DESCRIPTION
+    Do same as default implementation but use file->s->name instead of 
+    table->s->path. This is needed by Windows where the clone() call sees
+    '/'-delimited path in table->s->path, while ha_heap::open() was called 
+    with '\'-delimited path.
+*/
+
+handler *ha_heap::clone(const char *name, MEM_ROOT *mem_root)
+{
+  handler *new_handler= get_new_handler(table->s, mem_root, ht);
+  if (new_handler && !new_handler->ha_open(table, file->s->name, table->db_stat,
+                                           HA_OPEN_IGNORE_IF_LOCKED))
+    return new_handler;
+  return NULL;  /* purecov: inspected */
+}
+
+
+/*
+  Compute which keys to use for scanning
+
+  SYNOPSIS
+    set_keys_for_scanning()
+    no parameter
+
+  DESCRIPTION
+    Set the bitmap btree_keys, which is used when the upper layers ask
+    which keys to use for scanning. For each btree index the
+    corresponding bit is set.
+
+  RETURN
+    void
+*/
+
+void ha_heap::set_keys_for_scanning(void)
+{
+  btree_keys.clear_all();
+  for (uint i= 0 ; i < table->s->keys ; i++)
+  {
+    if (table->key_info[i].algorithm == HA_KEY_ALG_BTREE)
+      btree_keys.set_bit(i);
+  }
+}
+
+
+int ha_heap::can_continue_handler_scan()
+{
+  int error= 0;
+  if ((file->key_version != file->s->key_version && inited == INDEX) ||
+      (file->file_version != file->s->file_version && inited == RND))
+  {
+    /* Data changed, not safe to do index or rnd scan */
+    error= HA_ERR_RECORD_CHANGED;
+  }
+  return error;
+}
+
+
+void ha_heap::update_key_stats()
+{
+  for (uint i= 0; i < table->s->keys; i++)
+  {
+    KEY *key=table->key_info+i;
+    if (!key->rec_per_key)
+      continue;
+    if (key->algorithm != HA_KEY_ALG_BTREE)
+    {
+      if (key->flags & HA_NOSAME)
+        key->rec_per_key[key->user_defined_key_parts-1]= 1;
+      else
+      {
+        ha_rows hash_buckets= file->s->keydef[i].hash_buckets;
+        ulong no_records= hash_buckets ? (ulong)(file->s->records/hash_buckets) : 2;
+        if (no_records < 2)
+          no_records= 2;
+        key->rec_per_key[key->user_defined_key_parts-1]= no_records;
+      }
+    }
+  }
+  records_changed= 0;
+  /* At the end of update_key_stats() we can proudly claim they are OK. */
+  key_stat_version= file->s->key_stat_version;
+}
+
+
+int ha_heap::write_row(const uchar * buf)
+{
+  int res;
+  if (table->next_number_field && buf == table->record[0])
+  {
+    if ((res= update_auto_increment()))
+      return res;
+  }
+  res= heap_write(file,buf);
+  if (!res && (++records_changed*HEAP_STATS_UPDATE_THRESHOLD > 
+               file->s->records))
+  {
+    /*
+       We can perform this safely since only one writer at the time is
+       allowed on the table.
+    */
+    records_changed= 0;
+    file->s->key_stat_version++;
+  }
+  return res;
+}
+
+int ha_heap::update_row(const uchar * old_data, const uchar * new_data)
+{
+  int res;
+  res= heap_update(file,old_data,new_data);
+  if (!res && ++records_changed*HEAP_STATS_UPDATE_THRESHOLD > 
+              file->s->records)
+  {
+    /*
+       We can perform this safely since only one writer at the time is
+       allowed on the table.
+    */
+    records_changed= 0;
+    file->s->key_stat_version++;
+  }
+  return res;
+}
+
+int ha_heap::delete_row(const uchar * buf)
+{
+  int res;
+  res= heap_delete(file,buf);
+  if (!res && table->s->tmp_table == NO_TMP_TABLE && 
+      ++records_changed*HEAP_STATS_UPDATE_THRESHOLD > file->s->records)
+  {
+    /*
+       We can perform this safely since only one writer at the time is
+       allowed on the table.
+    */
+    records_changed= 0;
+    file->s->key_stat_version++;
+  }
+  return res;
+}
+
+int ha_heap::index_read_map(uchar *buf, const uchar *key,
+                            key_part_map keypart_map,
+                            enum ha_rkey_function find_flag)
+{
+  DBUG_ASSERT(inited==INDEX);
+  int error = heap_rkey(file,buf,active_index, key, keypart_map, find_flag);
+  return error;
+}
+
+int ha_heap::index_read_last_map(uchar *buf, const uchar *key,
+                                 key_part_map keypart_map)
+{
+  DBUG_ASSERT(inited==INDEX);
+  int error= heap_rkey(file, buf, active_index, key, keypart_map,
+		       HA_READ_PREFIX_LAST);
+  return error;
+}
+
+int ha_heap::index_read_idx_map(uchar *buf, uint index, const uchar *key,
+                                key_part_map keypart_map,
+                                enum ha_rkey_function find_flag)
+{
+  int error = heap_rkey(file, buf, index, key, keypart_map, find_flag);
+  return error;
+}
+
+int ha_heap::index_next(uchar * buf)
+{
+  DBUG_ASSERT(inited==INDEX);
+  int error=heap_rnext(file,buf);
+  return error;
+}
+
+int ha_heap::index_prev(uchar * buf)
+{
+  DBUG_ASSERT(inited==INDEX);
+  int error=heap_rprev(file,buf);
+  return error;
+}
+
+int ha_heap::index_first(uchar * buf)
+{
+  DBUG_ASSERT(inited==INDEX);
+  int error=heap_rfirst(file, buf, active_index);
+  return error;
+}
+
+int ha_heap::index_last(uchar * buf)
+{
+  DBUG_ASSERT(inited==INDEX);
+  int error=heap_rlast(file, buf, active_index);
+  return error;
+}
+
+int ha_heap::rnd_init(bool scan)
+{
+  return scan ? heap_scan_init(file) : 0;
+}
+
+int ha_heap::rnd_next(uchar *buf)
+{
+  int error=heap_scan(file, buf);
+  return error;
+}
+
+int ha_heap::rnd_pos(uchar * buf, uchar *pos)
+{
+  int error;
+  HEAP_PTR heap_position;
+  memcpy(&heap_position, pos, sizeof(HEAP_PTR));
+  error=heap_rrnd(file, buf, heap_position);
+  return error;
+}
+
+void ha_heap::position(const uchar *record)
+{
+  *(HEAP_PTR*) ref= heap_position(file);	// Ref is aligned
+}
+
+int ha_heap::info(uint flag)
+{
+  HEAPINFO hp_info;
+
+  (void) heap_info(file,&hp_info,flag);
+
+  errkey=                     hp_info.errkey;
+  stats.records=              hp_info.records;
+  stats.deleted=              hp_info.deleted;
+  stats.mean_rec_length=      hp_info.reclength;
+  stats.data_file_length=     hp_info.data_length;
+  stats.index_file_length=    hp_info.index_length;
+  stats.max_data_file_length= hp_info.max_records * hp_info.reclength;
+  stats.delete_length=        hp_info.deleted * hp_info.reclength;
+  stats.create_time=          (ulong) hp_info.create_time;
+  if (flag & HA_STATUS_AUTO)
+    stats.auto_increment_value= hp_info.auto_increment;
+  /*
+    If info() is called for the first time after open(), we will still
+    have to update the key statistics. Hoping that a table lock is now
+    in place.
+  */
+  if (key_stat_version != file->s->key_stat_version)
+    update_key_stats();
+  return 0;
+}
+
+
+int ha_heap::extra(enum ha_extra_function operation)
+{
+  return heap_extra(file,operation);
+}
+
+
+int ha_heap::reset()
+{
+  return heap_reset(file);
+}
+
+
+int ha_heap::delete_all_rows()
+{
+  heap_clear(file);
+  if (table->s->tmp_table == NO_TMP_TABLE)
+  {
+    /*
+       We can perform this safely since only one writer at the time is
+       allowed on the table.
+    */
+    file->s->key_stat_version++;
+  }
+  return 0;
+}
+
+
+int ha_heap::reset_auto_increment(ulonglong value)
+{
+  file->s->auto_increment= value;
+  return 0;
+}
+
+
+int ha_heap::external_lock(THD *thd, int lock_type)
+{
+#if !defined(DBUG_OFF) && defined(EXTRA_DEBUG)
+  if (lock_type == F_UNLCK && file->s->changed && heap_check_heap(file, 0))
+    return HA_ERR_CRASHED;
+#endif
+  return 0;					// No external locking
+}
+
+
+/*
+  Disable indexes.
+
+  SYNOPSIS
+    disable_indexes()
+    mode        mode of operation:
+                HA_KEY_SWITCH_NONUNIQ      disable all non-unique keys
+                HA_KEY_SWITCH_ALL          disable all keys
+                HA_KEY_SWITCH_NONUNIQ_SAVE dis. non-uni. and make persistent
+                HA_KEY_SWITCH_ALL_SAVE     dis. all keys and make persistent
+
+  DESCRIPTION
+    Disable indexes and clear keys to use for scanning.
+
+  IMPLEMENTATION
+    HA_KEY_SWITCH_NONUNIQ       is not implemented.
+    HA_KEY_SWITCH_NONUNIQ_SAVE  is not implemented with HEAP.
+    HA_KEY_SWITCH_ALL_SAVE      is not implemented with HEAP.
+
+  RETURN
+    0  ok
+    HA_ERR_WRONG_COMMAND  mode not implemented.
+*/
+
+int ha_heap::disable_indexes(uint mode)
+{
+  int error;
+
+  if (mode == HA_KEY_SWITCH_ALL)
+  {
+    if (!(error= heap_disable_indexes(file)))
+      set_keys_for_scanning();
+  }
+  else
+  {
+    /* mode not implemented */
+    error= HA_ERR_WRONG_COMMAND;
+  }
+  return error;
+}
+
+
+/*
+  Enable indexes.
+
+  SYNOPSIS
+    enable_indexes()
+    mode        mode of operation:
+                HA_KEY_SWITCH_NONUNIQ      enable all non-unique keys
+                HA_KEY_SWITCH_ALL          enable all keys
+                HA_KEY_SWITCH_NONUNIQ_SAVE en. non-uni. and make persistent
+                HA_KEY_SWITCH_ALL_SAVE     en. all keys and make persistent
+
+  DESCRIPTION
+    Enable indexes and set keys to use for scanning.
+    The indexes might have been disabled by disable_index() before.
+    The function works only if both data and indexes are empty,
+    since the heap storage engine cannot repair the indexes.
+    To be sure, call handler::delete_all_rows() before.
+
+  IMPLEMENTATION
+    HA_KEY_SWITCH_NONUNIQ       is not implemented.
+    HA_KEY_SWITCH_NONUNIQ_SAVE  is not implemented with HEAP.
+    HA_KEY_SWITCH_ALL_SAVE      is not implemented with HEAP.
+
+  RETURN
+    0  ok
+    HA_ERR_CRASHED  data or index is non-empty. Delete all rows and retry.
+    HA_ERR_WRONG_COMMAND  mode not implemented.
+*/
+
+int ha_heap::enable_indexes(uint mode)
+{
+  int error;
+
+  if (mode == HA_KEY_SWITCH_ALL)
+  {
+    if (!(error= heap_enable_indexes(file)))
+      set_keys_for_scanning();
+  }
+  else
+  {
+    /* mode not implemented */
+    error= HA_ERR_WRONG_COMMAND;
+  }
+  return error;
+}
+
+
+/*
+  Test if indexes are disabled.
+
+  SYNOPSIS
+    indexes_are_disabled()
+    no parameters
+
+  RETURN
+    0  indexes are not disabled
+    1  all indexes are disabled
+   [2  non-unique indexes are disabled - NOT YET IMPLEMENTED]
+*/
+
+int ha_heap::indexes_are_disabled(void)
+{
+  return heap_indexes_are_disabled(file);
+}
+
+THR_LOCK_DATA **ha_heap::store_lock(THD *thd,
+				    THR_LOCK_DATA **to,
+				    enum thr_lock_type lock_type)
+{
+  if (lock_type != TL_IGNORE && file->lock.type == TL_UNLOCK)
+    file->lock.type=lock_type;
+  *to++= &file->lock;
+  return to;
+}
+
+/*
+  We have to ignore ENOENT entries as the HEAP table is created on open and
+  not when doing a CREATE on the table.
+*/
+
+int ha_heap::delete_table(const char *name)
+{
+  return heap_drop_table(0, name);
+}
+
+
+void ha_heap::drop_table(const char *name)
+{
+  file->s->delete_on_close= 1;
+  ha_close();
+}
+
+
+int ha_heap::rename_table(const char * from, const char * to)
+{
+  return heap_rename(from,to);
+}
+
+
+ha_rows ha_heap::records_in_range(uint inx, const key_range *min_key,
+                                  const key_range *max_key, page_range *pages)
+{
+  KEY *key=table->key_info+inx;
+  if (key->algorithm == HA_KEY_ALG_BTREE)
+    return hp_rb_records_in_range(file, inx, min_key, max_key);
+
+  if (!min_key || !max_key ||
+      min_key->length != max_key->length ||
+      min_key->length != key->key_length ||
+      min_key->flag != HA_READ_KEY_EXACT ||
+      max_key->flag != HA_READ_AFTER_KEY)
+    return HA_POS_ERROR;			// Can only use exact keys
+
+  if (stats.records <= 1)
+    return stats.records;
+
+  /* Assert that info() did run. We need current statistics here. */
+  DBUG_ASSERT(key_stat_version == file->s->key_stat_version);
+  return key->rec_per_key[key->user_defined_key_parts-1];
+}
+
+
+static int heap_prepare_hp_create_info(TABLE *table_arg, bool internal_table,
+                                       HP_CREATE_INFO *hp_create_info)
+{
+  TABLE_SHARE *share= table_arg->s;
+  uint key, parts, mem_per_row= 0, keys= share->keys;
+  uint auto_key= 0, auto_key_type= 0;
+  ha_rows max_rows;
+  HP_KEYDEF *keydef;
+  HA_KEYSEG *seg;
+  bool found_real_auto_increment= 0;
+
+  bzero(hp_create_info, sizeof(*hp_create_info));
+
+  for (key= parts= 0; key < keys; key++)
+    parts+= table_arg->key_info[key].user_defined_key_parts;
+
+  if (!my_multi_malloc(hp_key_memory_HP_KEYDEF,
+                       MYF(MY_WME | MY_THREAD_SPECIFIC),
+                       &keydef, keys * sizeof(HP_KEYDEF),
+                       &seg, parts * sizeof(HA_KEYSEG),
+                       NULL))
+    return my_errno;
+  for (key= 0; key < keys; key++)
+  {
+    KEY *pos= table_arg->key_info+key;
+    KEY_PART_INFO *key_part=     pos->key_part;
+    KEY_PART_INFO *key_part_end= key_part + pos->user_defined_key_parts;
+
+    keydef[key].keysegs=   (uint) pos->user_defined_key_parts;
+    keydef[key].flag=      (pos->flags & (HA_NOSAME | HA_NULL_ARE_EQUAL));
+    keydef[key].seg=       seg;
+
+    switch (pos->algorithm) {
+    case HA_KEY_ALG_UNDEF:
+    case HA_KEY_ALG_HASH:
+      keydef[key].algorithm= HA_KEY_ALG_HASH;
+      mem_per_row+= sizeof(char*) * 2; // = sizeof(HASH_INFO)
+      break;
+    case HA_KEY_ALG_BTREE:
+      keydef[key].algorithm= HA_KEY_ALG_BTREE;
+      mem_per_row+=sizeof(TREE_ELEMENT)+pos->key_length+sizeof(char*);
+      break;
+    default:
+      DBUG_ASSERT(0); // cannot happen
+    }
+
+    for (; key_part != key_part_end; key_part++, seg++)
+    {
+      Field *field= key_part->field;
+
+      if (pos->algorithm == HA_KEY_ALG_BTREE)
+	seg->type= field->key_type();
+      else
+      {
+        if ((seg->type = field->key_type()) != (int) HA_KEYTYPE_TEXT &&
+            seg->type != HA_KEYTYPE_VARTEXT1 &&
+            seg->type != HA_KEYTYPE_VARTEXT2 &&
+            seg->type != HA_KEYTYPE_VARBINARY1 &&
+            seg->type != HA_KEYTYPE_VARBINARY2 &&
+            seg->type != HA_KEYTYPE_BIT)
+          seg->type= HA_KEYTYPE_BINARY;
+      }
+      seg->start=   (uint) key_part->offset;
+      seg->length=  (uint) key_part->length;
+      seg->flag=    key_part->key_part_flag;
+
+      if (field->flags & (ENUM_FLAG | SET_FLAG))
+        seg->charset= &my_charset_bin;
+      else
+        seg->charset= field->charset_for_protocol();
+      if (field->null_ptr)
+      {
+	seg->null_bit= field->null_bit;
+	seg->null_pos= (uint) (field->null_ptr - (uchar*) table_arg->record[0]);
+      }
+      else
+      {
+	seg->null_bit= 0;
+	seg->null_pos= 0;
+      }
+      if (field->flags & AUTO_INCREMENT_FLAG &&
+          table_arg->found_next_number_field &&
+          key == share->next_number_index)
+      {
+        /*
+          Store key number and type for found auto_increment key
+          We have to store type as seg->type can differ from it
+        */
+        auto_key= key+ 1;
+	auto_key_type= field->key_type();
+      }
+      if (seg->type == HA_KEYTYPE_BIT)
+      {
+        seg->bit_length= ((Field_bit *) field)->bit_len;
+        seg->bit_start= ((Field_bit *) field)->bit_ofs;
+        seg->bit_pos= (uint) (((Field_bit *) field)->bit_ptr -
+                                          (uchar*) table_arg->record[0]);
+      }
+      else
+      {
+        seg->bit_length= seg->bit_start= 0;
+        seg->bit_pos= 0;
+      }
+    }
+  }
+  mem_per_row+= MY_ALIGN(MY_MAX(share->reclength, sizeof(char*)) + 1, sizeof(char*));
+  if (table_arg->found_next_number_field)
+  {
+    keydef[share->next_number_index].flag|= HA_AUTO_KEY;
+    found_real_auto_increment= share->next_number_key_offset == 0;
+  }
+  hp_create_info->auto_key= auto_key;
+  hp_create_info->auto_key_type= auto_key_type;
+  hp_create_info->max_table_size=current_thd->variables.max_heap_table_size;
+  hp_create_info->with_auto_increment= found_real_auto_increment;
+  hp_create_info->internal_table= internal_table;
+
+  max_rows= (ha_rows) (hp_create_info->max_table_size / mem_per_row);
+  if (share->max_rows && share->max_rows < max_rows)
+    max_rows= share->max_rows;
+
+  hp_create_info->max_records= (ulong) MY_MIN(max_rows, ULONG_MAX);
+  hp_create_info->min_records= (ulong) MY_MIN(share->min_rows, ULONG_MAX);
+  hp_create_info->keys= share->keys;
+  hp_create_info->reclength= share->reclength;
+  hp_create_info->keydef= keydef;
+  return 0;
+}
+
+
+int ha_heap::create(const char *name, TABLE *table_arg,
+		    HA_CREATE_INFO *create_info)
+{
+  int error;
+  my_bool created;
+  HP_CREATE_INFO hp_create_info;
+
+  error= heap_prepare_hp_create_info(table_arg, internal_table,
+                                     &hp_create_info);
+  if (error)
+    return error;
+  hp_create_info.auto_increment= (create_info->auto_increment_value ?
+				  create_info->auto_increment_value - 1 : 0);
+  error= heap_create(name, &hp_create_info, &internal_share, &created);
+  my_free(hp_create_info.keydef);
+  DBUG_ASSERT(file == 0);
+  return (error);
+}
+
+
+void ha_heap::update_create_info(HA_CREATE_INFO *create_info)
+{
+  table->file->info(HA_STATUS_AUTO);
+  if (!(create_info->used_fields & HA_CREATE_USED_AUTO))
+    create_info->auto_increment_value= stats.auto_increment_value;
+}
+
+void ha_heap::get_auto_increment(ulonglong offset, ulonglong increment,
+                                 ulonglong nb_desired_values,
+                                 ulonglong *first_value,
+                                 ulonglong *nb_reserved_values)
+{
+  ha_heap::info(HA_STATUS_AUTO);
+  *first_value= stats.auto_increment_value;
+  /* such table has only table-level locking so reserves up to +inf */
+  *nb_reserved_values= ULONGLONG_MAX;
+}
+
+
+bool ha_heap::check_if_incompatible_data(HA_CREATE_INFO *info,
+					 uint table_changes)
+{
+  /* Check that auto_increment value was not changed */
+  if ((info->used_fields & HA_CREATE_USED_AUTO &&
+       info->auto_increment_value != 0) ||
+      table_changes == IS_EQUAL_NO ||
+      table_changes & IS_EQUAL_PACK_LENGTH) // Not implemented yet
+    return COMPATIBLE_DATA_NO;
+  return COMPATIBLE_DATA_YES;
+}
+
+
+/**
+  Find record by unique index (used in temporary tables with the index)
+
+  @param record          (IN|OUT) the record to find
+  @param unique_idx      (IN) number of index (for this engine)
+
+  @note It is like hp_search but uses function for raw where hp_search
+        uses functions for index.
+
+  @retval  0 OK
+  @retval  1 Not found
+  @retval -1 Error
+*/
+
+int ha_heap::find_unique_row(uchar *record, uint unique_idx)
+{
+  DBUG_ENTER("ha_heap::find_unique_row");
+  HP_SHARE *share= file->s;
+  DBUG_ASSERT(inited==NONE);
+  HP_KEYDEF *keyinfo= share->keydef + unique_idx;
+  DBUG_ASSERT(keyinfo->algorithm == HA_KEY_ALG_HASH);
+  DBUG_ASSERT(keyinfo->flag & HA_NOSAME);
+  if (!share->records)
+    DBUG_RETURN(1); // not found
+  HASH_INFO *pos= hp_find_hash(&keyinfo->block,
+                               hp_mask(hp_rec_hashnr(keyinfo, record),
+                                       share->blength, share->records));
+  do
+  {
+    if (!hp_rec_key_cmp(keyinfo, pos->ptr_to_rec, record))
+    {
+      file->current_hash_ptr= pos;
+      file->current_ptr= pos->ptr_to_rec;
+      file->update = HA_STATE_AKTIV;
+      /*
+        We compare it only by record in the index, so better to read all
+        records.
+      */
+      memcpy(record, file->current_ptr, (size_t) share->reclength);
+
+      DBUG_RETURN(0); // found and position set
+    }
+  }
+  while ((pos= pos->next_key));
+  DBUG_RETURN(1); // not found
+}
+
+struct st_mysql_storage_engine heap_storage_engine=
+{ MYSQL_HANDLERTON_INTERFACE_VERSION };
+
+maria_declare_plugin(heap)
+{
+  MYSQL_STORAGE_ENGINE_PLUGIN,
+  &heap_storage_engine,
+  "MEMORY",
+  "MySQL AB",
+  "Hash based, stored in memory, useful for temporary tables",
+  PLUGIN_LICENSE_GPL,
+  heap_init,
+  NULL,
+  0x0100, /* 1.0 */
+  NULL,                       /* status variables                */
+  NULL,                       /* system variables                */
+  "1.0",                      /* string version */
+  MariaDB_PLUGIN_MATURITY_STABLE /* maturity */
+}
+maria_declare_plugin_end;
diff --git a/storage/heap/ha_heap.h b/storage/heap/ha_heap.h
new file mode 100644
index 00000000..18e0d1a9
--- /dev/null
+++ b/storage/heap/ha_heap.h
@@ -0,0 +1,125 @@
+/*
+   Copyright (c) 2000, 2011, Oracle and/or its affiliates
+   Copyright (c) 2009, 2011, Monty Program Ab
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; version 2 of the License.
+
+   This program 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 General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1335  USA */
+
+
+#ifdef USE_PRAGMA_INTERFACE
+#pragma interface			/* gcc class implementation */
+#endif
+
+/* class for the the heap handler */
+
+#include <heap.h>
+#include "sql_class.h"                          /* THD */
+
+class ha_heap final : public handler
+{
+  HP_INFO *file;
+  HP_SHARE *internal_share;
+  key_map btree_keys;
+  /* number of records changed since last statistics update */
+  ulong   records_changed;
+  uint    key_stat_version;
+  my_bool internal_table;
+public:
+  ha_heap(handlerton *hton, TABLE_SHARE *table);
+  ~ha_heap() = default;
+  handler *clone(const char *name, MEM_ROOT *mem_root);
+  const char *index_type(uint inx)
+  {
+    return ((table_share->key_info[inx].algorithm == HA_KEY_ALG_BTREE) ?
+            "BTREE" : "HASH");
+  }
+  /* Rows also use a fixed-size format */
+  enum row_type get_row_type() const { return ROW_TYPE_FIXED; }
+  ulonglong table_flags() const
+  {
+    return (HA_FAST_KEY_READ | HA_NO_BLOBS | HA_NULL_IN_KEY |
+            HA_BINLOG_ROW_CAPABLE | HA_BINLOG_STMT_CAPABLE |
+            HA_CAN_SQL_HANDLER | HA_CAN_ONLINE_BACKUPS |
+            HA_REC_NOT_IN_SEQ | HA_CAN_INSERT_DELAYED | HA_NO_TRANSACTIONS |
+            HA_HAS_RECORDS | HA_STATS_RECORDS_IS_EXACT | HA_CAN_HASH_KEYS);
+  }
+  ulong index_flags(uint inx, uint part, bool all_parts) const
+  {
+    return ((table_share->key_info[inx].algorithm == HA_KEY_ALG_BTREE) ?
+            HA_READ_NEXT | HA_READ_PREV | HA_READ_ORDER | HA_READ_RANGE :
+            HA_ONLY_WHOLE_INDEX | HA_KEY_SCAN_NOT_ROR);
+  }
+  const key_map *keys_to_use_for_scanning() { return &btree_keys; }
+  uint max_supported_keys()          const { return MAX_KEY; }
+  uint max_supported_key_part_length() const { return MAX_KEY_LENGTH; }
+  double scan_time()
+  { return (double) (stats.records+stats.deleted) / 20.0+10; }
+  double read_time(uint index, uint ranges, ha_rows rows)
+  { return (double) (rows +1)/ 20.0; }
+  double keyread_time(uint index, uint ranges, ha_rows rows)
+  { return (double) (rows + ranges) / 20.0 ; }
+  double avg_io_cost()
+  { return 0.05; }                              /* 1/20 */
+  int open(const char *name, int mode, uint test_if_locked);
+  int close(void);
+  void set_keys_for_scanning(void);
+  int write_row(const uchar * buf);
+  int update_row(const uchar * old_data, const uchar * new_data);
+  int delete_row(const uchar * buf);
+  virtual void get_auto_increment(ulonglong offset, ulonglong increment,
+                                  ulonglong nb_desired_values,
+                                  ulonglong *first_value,
+                                  ulonglong *nb_reserved_values);
+  int index_read_map(uchar * buf, const uchar * key, key_part_map keypart_map,
+                     enum ha_rkey_function find_flag);
+  int index_read_last_map(uchar *buf, const uchar *key, key_part_map keypart_map);
+  int index_read_idx_map(uchar * buf, uint index, const uchar * key,
+                         key_part_map keypart_map,
+                         enum ha_rkey_function find_flag);
+  int index_next(uchar * buf);
+  int index_prev(uchar * buf);
+  int index_first(uchar * buf);
+  int index_last(uchar * buf);
+  int rnd_init(bool scan);
+  int rnd_next(uchar *buf);
+  int rnd_pos(uchar * buf, uchar *pos);
+  void position(const uchar *record);
+  int can_continue_handler_scan();
+  int info(uint);
+  int extra(enum ha_extra_function operation);
+  int reset();
+  int external_lock(THD *thd, int lock_type);
+  int delete_all_rows(void);
+  int reset_auto_increment(ulonglong value);
+  int disable_indexes(uint mode);
+  int enable_indexes(uint mode);
+  int indexes_are_disabled(void);
+  ha_rows records_in_range(uint inx, const key_range *start_key,
+                           const key_range *end_key, page_range *pages);
+  int delete_table(const char *from);
+  void drop_table(const char *name);
+  int rename_table(const char * from, const char * to);
+  int create(const char *name, TABLE *form, HA_CREATE_INFO *create_info);
+  void update_create_info(HA_CREATE_INFO *create_info);
+
+  THR_LOCK_DATA **store_lock(THD *thd, THR_LOCK_DATA **to,
+			     enum thr_lock_type lock_type);
+  int cmp_ref(const uchar *ref1, const uchar *ref2)
+  {
+    return memcmp(ref1, ref2, sizeof(HEAP_PTR));
+  }
+  bool check_if_incompatible_data(HA_CREATE_INFO *info, uint table_changes);
+  int find_unique_row(uchar *record, uint unique_idx);
+private:
+  void update_key_stats();
+};
diff --git a/storage/heap/heapdef.h b/storage/heap/heapdef.h
new file mode 100644
index 00000000..ffd5382b
--- /dev/null
+++ b/storage/heap/heapdef.h
@@ -0,0 +1,136 @@
+/* Copyright (c) 2000, 2011, Oracle and/or its affiliates. All rights reserved.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; version 2 of the License.
+
+   This program 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 General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1335  USA */
+
+/* This file is included in all heap-files */
+
+#include <my_global.h>
+#include <my_base.h>
+C_MODE_START
+#include <my_pthread.h>
+#include "heap.h"			/* Structs & some defines */
+#include "my_tree.h"
+
+/*
+  When allocating keys /rows in the internal block structure, do it
+  within the following boundaries.
+
+  The challenge is to find the balance between allocate as few blocks
+  as possible and keep memory consumption down.
+*/
+
+#define HP_MIN_RECORDS_IN_BLOCK 16
+#define HP_MAX_RECORDS_IN_BLOCK 8192
+
+	/* Some extern variables */
+
+extern LIST *heap_open_list,*heap_share_list;
+
+#define test_active(info) \
+if (!(info->update & HA_STATE_AKTIV))\
+{ my_errno=HA_ERR_NO_ACTIVE_RECORD; DBUG_RETURN(-1); }
+#define hp_find_hash(A,B) ((HASH_INFO*) hp_find_block((A),(B)))
+
+	/* Find pos for record and update it in info->current_ptr */
+#define hp_find_record(info,pos) (info)->current_ptr= hp_find_block(&(info)->s->block,pos)
+
+typedef struct st_hp_hash_info
+{
+  struct st_hp_hash_info *next_key;
+  uchar *ptr_to_rec;
+  ulong hash_of_key;
+} HASH_INFO;
+
+typedef struct {
+  HA_KEYSEG *keyseg;
+  uint key_length;
+  uint search_flag;
+} heap_rb_param;
+      
+	/* Prototypes for intern functions */
+
+extern HP_SHARE *hp_find_named_heap(const char *name);
+extern int hp_rectest(HP_INFO *info,const uchar *old);
+extern uchar *hp_find_block(HP_BLOCK *info,ulong pos);
+extern int hp_get_new_block(HP_SHARE *info, HP_BLOCK *block,
+                            size_t* alloc_length);
+extern void hp_free(HP_SHARE *info);
+extern uchar *hp_free_level(HP_BLOCK *block,uint level,HP_PTRS *pos,
+			   uchar *last_pos);
+extern int hp_write_key(HP_INFO *info, HP_KEYDEF *keyinfo,
+			const uchar *record, uchar *recpos);
+extern int hp_rb_write_key(HP_INFO *info, HP_KEYDEF *keyinfo, 
+			   const uchar *record, uchar *recpos);
+extern int hp_rb_delete_key(HP_INFO *info,HP_KEYDEF *keyinfo,
+			    const uchar *record,uchar *recpos,int flag);
+extern int hp_delete_key(HP_INFO *info,HP_KEYDEF *keyinfo,
+			 const uchar *record,uchar *recpos,int flag);
+extern HASH_INFO *_heap_find_hash(HP_BLOCK *block,ulong pos);
+extern uchar *hp_search(HP_INFO *info,HP_KEYDEF *keyinfo,const uchar *key,
+		       uint nextflag);
+extern uchar *hp_search_next(HP_INFO *info, HP_KEYDEF *keyinfo,
+			    const uchar *key, HASH_INFO *pos);
+extern ulong hp_rec_hashnr(HP_KEYDEF *keyinfo,const uchar *rec);
+extern void hp_movelink(HASH_INFO *pos,HASH_INFO *next_link,
+			 HASH_INFO *newlink);
+extern int hp_rec_key_cmp(HP_KEYDEF *keydef,const uchar *rec1,
+			  const uchar *rec2);
+extern int hp_key_cmp(HP_KEYDEF *keydef,const uchar *rec,
+		      const uchar *key);
+extern void hp_make_key(HP_KEYDEF *keydef,uchar *key,const uchar *rec);
+extern uint hp_rb_make_key(HP_KEYDEF *keydef, uchar *key,
+			   const uchar *rec, uchar *recpos);
+extern uint hp_rb_key_length(HP_KEYDEF *keydef, const uchar *key);
+extern uint hp_rb_null_key_length(HP_KEYDEF *keydef, const uchar *key);
+extern uint hp_rb_var_key_length(HP_KEYDEF *keydef, const uchar *key);
+extern my_bool hp_if_null_in_key(HP_KEYDEF *keyinfo, const uchar *record);
+extern int hp_close(HP_INFO *info);
+extern void hp_clear(HP_SHARE *info);
+extern void hp_clear_keys(HP_SHARE *info);
+extern uint hp_rb_pack_key(HP_KEYDEF *keydef, uchar *key, const uchar *old,
+                           key_part_map keypart_map);
+
+extern mysql_mutex_t THR_LOCK_heap;
+
+extern PSI_memory_key hp_key_memory_HP_SHARE;
+extern PSI_memory_key hp_key_memory_HP_INFO;
+extern PSI_memory_key hp_key_memory_HP_PTRS;
+extern PSI_memory_key hp_key_memory_HP_KEYDEF;
+
+#ifdef HAVE_PSI_INTERFACE
+void init_heap_psi_keys();
+#else
+#define init_heap_psi_keys() do { } while(0)
+#endif /* HAVE_PSI_INTERFACE */
+
+C_MODE_END
+
+/*
+  Calculate position number for hash value.
+  SYNOPSIS
+    hp_mask()
+      hashnr     Hash value
+      buffmax    Value such that
+                 2^(n-1) < maxlength <= 2^n = buffmax
+      maxlength
+
+  RETURN
+    Array index, in [0..maxlength)
+*/
+
+static inline ulong hp_mask(ulong hashnr, ulong buffmax, ulong maxlength)
+{
+  if ((hashnr & (buffmax-1)) < maxlength) return (hashnr & (buffmax-1));
+  return (hashnr & ((buffmax >> 1) -1));
+}
diff --git a/storage/heap/hp_block.c b/storage/heap/hp_block.c
new file mode 100644
index 00000000..324efc8b
--- /dev/null
+++ b/storage/heap/hp_block.c
@@ -0,0 +1,155 @@
+/* Copyright (c) 2000, 2014, Oracle and/or its affiliates. All rights reserved.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; version 2 of the License.
+
+   This program 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 General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1335  USA */
+
+/* functions on blocks; Keys and records are saved in blocks */
+
+#include "heapdef.h"
+
+/*
+  Find record according to record-position.
+      
+  The record is located by factoring position number pos into (p_0, p_1, ...) 
+  such that
+     pos = SUM_i(block->level_info[i].records_under_level * p_i)
+  {p_0, p_1, ...} serve as indexes to descend the blocks tree.
+*/
+
+uchar *hp_find_block(HP_BLOCK *block, ulong pos)
+{
+  reg1 int i;
+  reg3 HP_PTRS *ptr; /* block base ptr */
+
+  for (i=block->levels-1, ptr=block->root ; i > 0 ; i--)
+  {
+    ptr=(HP_PTRS*)ptr->blocks[pos/block->level_info[i].records_under_level];
+    pos%=block->level_info[i].records_under_level;
+  }
+  return (uchar*) ptr+ pos*block->recbuffer;
+}
+
+
+/*
+  Get one new block-of-records. Alloc ptr to block if needed
+
+  SYNOPSIS
+    hp_get_new_block()
+      info	        heap handle
+      block             HP_BLOCK tree-like block
+      alloc_length OUT  Amount of memory allocated from the heap
+      
+  Interrupts are stopped to allow ha_panic in interrupts 
+  RETURN
+    0  OK
+    1  Out of memory
+*/
+
+int hp_get_new_block(HP_SHARE *info, HP_BLOCK *block, size_t *alloc_length)
+{
+  reg1 uint i,j;
+  HP_PTRS *root;
+
+  for (i=0 ; i < block->levels ; i++)
+    if (block->level_info[i].free_ptrs_in_block)
+      break;
+
+  /*
+    Allocate space for leaf block (data) plus space for upper level blocks
+    up to first level that has a free slot to put the pointer.
+    If this is a new level, we have to allocate pointers to all future
+    lower levels.
+
+    For example, for level 0, we allocate data for X rows.
+    When level 0 is full, we allocate data for HP_PTRS_IN_NOD + X rows.
+    Next time we allocate data for X rows.
+    When level 1 is full, we allocate data for HP_PTRS_IN_NOD at level 2 and 1
+    + X rows at level 0.
+   */
+  *alloc_length= (sizeof(HP_PTRS) * ((i == block->levels) ? i : i - 1) +
+                  (ulonglong)block->records_in_block * block->recbuffer);
+  if (!(root=(HP_PTRS*) my_malloc(hp_key_memory_HP_PTRS, *alloc_length,
+                                  MYF(MY_WME |
+                                      (info->internal ?
+                                       MY_THREAD_SPECIFIC : 0)))))
+    return 1;
+
+  if (i == 0)
+  {
+    block->levels=1;
+    block->root=block->level_info[0].last_blocks=root;
+  }
+  else
+  {
+    if ((uint) i == block->levels)
+    {
+      /* Adding a new level on top of the existing ones. */
+      block->levels=i+1;
+      /*
+        Use first allocated HP_PTRS as a top-level block. Put the current
+        block tree into the first slot of a new top-level block.
+      */
+      block->level_info[i].free_ptrs_in_block=HP_PTRS_IN_NOD-1;
+      ((HP_PTRS**) root)[0]= block->root;
+      block->root=block->level_info[i].last_blocks= root++;
+    }
+    /* Occupy the free slot we've found at level i */
+    block->level_info[i].last_blocks->
+      blocks[HP_PTRS_IN_NOD - block->level_info[i].free_ptrs_in_block--]=
+	(uchar*) root;
+    
+    /* Add a block subtree with each node having one left-most child */
+    for (j=i-1 ; j >0 ; j--)
+    {
+      block->level_info[j].last_blocks= root++;
+      block->level_info[j].last_blocks->blocks[0]=(uchar*) root;
+      block->level_info[j].free_ptrs_in_block=HP_PTRS_IN_NOD-1;
+    }
+    
+    /* 
+      root now points to last (block->records_in_block* block->recbuffer)
+      allocated bytes. Use it as a leaf block.
+    */
+    block->level_info[0].last_blocks= root;
+  }
+  return 0;
+}
+
+
+	/* free all blocks under level */
+
+uchar *hp_free_level(HP_BLOCK *block, uint level, HP_PTRS *pos, uchar *last_pos)
+{
+  int i,max_pos;
+  uchar *next_ptr;
+
+  if (level == 1)
+    next_ptr=(uchar*) pos+block->recbuffer;
+  else
+  {
+    max_pos= (block->level_info[level-1].last_blocks == pos) ?
+      HP_PTRS_IN_NOD - block->level_info[level-1].free_ptrs_in_block :
+    HP_PTRS_IN_NOD;
+
+    next_ptr=(uchar*) (pos+1);
+    for (i=0 ; i < max_pos ; i++)
+      next_ptr=hp_free_level(block,level-1,
+			      (HP_PTRS*) pos->blocks[i],next_ptr);
+  }
+  if ((uchar*) pos != last_pos)
+  {
+    my_free(pos);
+    return last_pos;
+  }
+  return next_ptr;			/* next memory position */
+}
diff --git a/storage/heap/hp_clear.c b/storage/heap/hp_clear.c
new file mode 100644
index 00000000..b0b26324
--- /dev/null
+++ b/storage/heap/hp_clear.c
@@ -0,0 +1,197 @@
+/* Copyright (c) 2000-2002, 2004-2007 MySQL AB, 2009 Sun Microsystems, Inc.
+   Use is subject to license terms.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; version 2 of the License.
+
+   This program 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 General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1335  USA */
+
+/*
+  remove all records from database
+  Identical as hp_create() and hp_open() but used HP_SHARE* instead of name and
+  database remains open.
+*/
+
+#include "heapdef.h"
+
+void heap_clear(HP_INFO *info)
+{
+  hp_clear(info->s);
+}
+
+void hp_clear(HP_SHARE *info)
+{
+  DBUG_ENTER("hp_clear");
+
+  if (info->block.levels)
+    (void) hp_free_level(&info->block,info->block.levels,info->block.root,
+			(uchar*) 0);
+  info->block.levels=0;
+  hp_clear_keys(info);
+  info->records= info->deleted= 0;
+  info->data_length= 0;
+  info->blength=1;
+  info->changed=0;
+  info->del_link=0;
+  info->key_version++;
+  info->file_version++;
+  DBUG_VOID_RETURN;
+}
+
+
+/*
+  Clear all keys.
+
+  SYNOPSIS
+    heap_clear_keys()
+    info      A pointer to the heap storage engine HP_INFO struct.
+
+  DESCRIPTION
+    Delete all trees of all indexes and leave them empty.
+
+  RETURN
+    void
+*/
+
+void heap_clear_keys(HP_INFO *info)
+{
+  hp_clear(info->s);
+}
+
+
+/*
+  Clear all keys.
+
+  SYNOPSIS
+    hp_clear_keys()
+    info      A pointer to the heap storage engine HP_SHARE struct.
+
+  DESCRIPTION
+    Delete all trees of all indexes and leave them empty.
+
+  RETURN
+    void
+*/
+
+void hp_clear_keys(HP_SHARE *info)
+{
+  uint key;
+  DBUG_ENTER("hp_clear_keys");
+
+  for (key=0 ; key < info->keys ; key++)
+  {
+    HP_KEYDEF *keyinfo = info->keydef + key;
+    if (keyinfo->algorithm == HA_KEY_ALG_BTREE)
+    {
+      delete_tree(&keyinfo->rb_tree, 0);
+    }
+    else
+    {
+      HP_BLOCK *block= &keyinfo->block;
+      if (block->levels)
+        (void) hp_free_level(block,block->levels,block->root,(uchar*) 0);
+      block->levels=0;
+      block->last_allocated=0;
+      keyinfo->hash_buckets= 0;
+    }
+  }
+  info->index_length=0;
+  DBUG_VOID_RETURN;
+}
+
+
+/*
+  Disable all indexes.
+
+  SYNOPSIS
+    heap_disable_indexes()
+    info      A pointer to the heap storage engine HP_INFO struct.
+
+  DESCRIPTION
+    Disable and clear (remove contents of) all indexes.
+
+  RETURN
+    0  ok
+*/
+
+int heap_disable_indexes(HP_INFO *info)
+{
+  HP_SHARE *share= info->s;
+
+  if (share->keys)
+  {
+    hp_clear_keys(share);
+    share->currently_disabled_keys= share->keys;
+    share->keys= 0;
+  }
+  return 0;
+}
+
+
+/*
+  Enable all indexes
+
+  SYNOPSIS
+    heap_enable_indexes()
+    info      A pointer to the heap storage engine HP_INFO struct.
+
+  DESCRIPTION
+    Enable all indexes. The indexes might have been disabled
+    by heap_disable_index() before.
+    The function works only if both data and indexes are empty,
+    since the heap storage engine cannot repair the indexes.
+    To be sure, call handler::delete_all_rows() before.
+
+  RETURN
+    0  ok
+    HA_ERR_CRASHED data or index is non-empty.
+*/
+
+int heap_enable_indexes(HP_INFO *info)
+{
+  int error= 0;
+  HP_SHARE *share= info->s;
+
+  if (share->data_length || share->index_length)
+    error= HA_ERR_CRASHED;
+  else
+    if (share->currently_disabled_keys)
+    {
+      share->keys= share->currently_disabled_keys;
+      share->currently_disabled_keys= 0;
+    }
+  return error;
+}
+
+
+/*
+  Test if indexes are disabled.
+
+  SYNOPSIS
+    heap_indexes_are_disabled()
+    info      A pointer to the heap storage engine HP_INFO struct.
+
+  DESCRIPTION
+    Test if indexes are disabled.
+
+  RETURN
+    0  indexes are not disabled
+    1  all indexes are disabled
+   [2  non-unique indexes are disabled - NOT YET IMPLEMENTED]
+*/
+
+int heap_indexes_are_disabled(HP_INFO *info)
+{
+  HP_SHARE *share= info->s;
+
+  return (! share->keys && share->currently_disabled_keys);
+}
+
diff --git a/storage/heap/hp_close.c b/storage/heap/hp_close.c
new file mode 100644
index 00000000..82d61863
--- /dev/null
+++ b/storage/heap/hp_close.c
@@ -0,0 +1,45 @@
+/* Copyright (c) 2000, 2010, Oracle and/or its affiliates. All rights reserved.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; version 2 of the License.
+
+   This program 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 General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1335  USA */
+
+/* close a heap-database */
+
+#include "heapdef.h"
+
+	/* Close a database open by hp_open() */
+	/* Data is normally not deallocated */
+
+int heap_close(HP_INFO *info)
+{
+  int tmp;
+  DBUG_ENTER("heap_close");
+  mysql_mutex_lock(&THR_LOCK_heap);
+  tmp= hp_close(info);
+  mysql_mutex_unlock(&THR_LOCK_heap);
+  DBUG_RETURN(tmp);
+}
+
+
+int hp_close(register HP_INFO *info)
+{
+  int error=0;
+  DBUG_ENTER("hp_close");
+  info->s->changed=0;
+  if (info->open_list.data)
+    heap_open_list=list_delete(heap_open_list,&info->open_list);
+  if (!--info->s->open_count && info->s->delete_on_close)
+    hp_free(info->s);				/* Table was deleted */
+  my_free(info);
+  DBUG_RETURN(error);
+}
diff --git a/storage/heap/hp_create.c b/storage/heap/hp_create.c
new file mode 100644
index 00000000..935c6f8d
--- /dev/null
+++ b/storage/heap/hp_create.c
@@ -0,0 +1,368 @@
+/* Copyright (c) 2000, 2018, Oracle and/or its affiliates.
+   Copyright (c) 2010, 2020, MariaDB Corporation.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; version 2 of the License.
+
+   This program 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 General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1335  USA */
+
+#include "heapdef.h"
+
+static int keys_compare(heap_rb_param *param, uchar *key1, uchar *key2);
+static void init_block(HP_BLOCK *block,uint reclength,ulong min_records,
+		       ulong max_records);
+
+/* Create a heap table */
+
+int heap_create(const char *name, HP_CREATE_INFO *create_info,
+                HP_SHARE **res, my_bool *created_new_share)
+{
+  uint i, j, key_segs, max_length, length;
+  HP_SHARE *share= 0;
+  HA_KEYSEG *keyseg;
+  HP_KEYDEF *keydef= create_info->keydef;
+  uint reclength= create_info->reclength;
+  uint keys= create_info->keys;
+  ulong min_records= create_info->min_records;
+  ulong max_records= create_info->max_records;
+  uint visible_offset;
+  DBUG_ENTER("heap_create");
+
+  if (!create_info->internal_table)
+  {
+    mysql_mutex_lock(&THR_LOCK_heap);
+    share= hp_find_named_heap(name);
+    if (share && share->open_count == 0)
+    {
+      hp_free(share);
+      share= 0;
+    }
+  }  
+  else
+  {
+    DBUG_PRINT("info", ("Creating internal (no named) temporary table"));
+  }
+  *created_new_share= (share == NULL);
+
+  if (!share)
+  {
+    HP_KEYDEF *keyinfo;
+    DBUG_PRINT("info",("Initializing new table"));
+    
+    /*
+      We have to store sometimes uchar* del_link in records,
+      so the visible_offset must be least at sizeof(uchar*)
+    */
+    visible_offset= MY_MAX(reclength, sizeof (char*));
+    
+    for (i= key_segs= max_length= 0, keyinfo= keydef; i < keys; i++, keyinfo++)
+    {
+      bzero((char*) &keyinfo->block,sizeof(keyinfo->block));
+      bzero((char*) &keyinfo->rb_tree ,sizeof(keyinfo->rb_tree));
+      for (j= length= 0; j < keyinfo->keysegs; j++)
+      {
+	length+= keyinfo->seg[j].length;
+	if (keyinfo->seg[j].null_bit)
+	{
+	  length++;
+	  if (!(keyinfo->flag & HA_NULL_ARE_EQUAL))
+	    keyinfo->flag|= HA_NULL_PART_KEY;
+	  if (keyinfo->algorithm == HA_KEY_ALG_BTREE)
+	    keyinfo->rb_tree.size_of_element++;
+	}
+	switch (keyinfo->seg[j].type) {
+	case HA_KEYTYPE_SHORT_INT:
+	case HA_KEYTYPE_LONG_INT:
+	case HA_KEYTYPE_FLOAT:
+	case HA_KEYTYPE_DOUBLE:
+	case HA_KEYTYPE_USHORT_INT:
+	case HA_KEYTYPE_ULONG_INT:
+	case HA_KEYTYPE_LONGLONG:
+	case HA_KEYTYPE_ULONGLONG:
+	case HA_KEYTYPE_INT24:
+	case HA_KEYTYPE_UINT24:
+	case HA_KEYTYPE_INT8:
+	  keyinfo->seg[j].flag|= HA_SWAP_KEY;
+          break;
+        case HA_KEYTYPE_VARBINARY1:
+          /* Case-insensitiveness is handled in hash_sort */
+          keyinfo->seg[j].type= HA_KEYTYPE_VARTEXT1;
+          /* fall through */
+        case HA_KEYTYPE_VARTEXT1:
+          keyinfo->flag|= HA_VAR_LENGTH_KEY;
+          /*
+            For BTREE algorithm, key length, greater than or equal
+            to 255, is packed on 3 bytes.
+          */
+          if (keyinfo->algorithm == HA_KEY_ALG_BTREE)
+            length+= size_to_store_key_length(keyinfo->seg[j].length);
+          else
+            length+= 2;
+          /* Save number of bytes used to store length */
+          keyinfo->seg[j].bit_start= 1;
+          break;
+        case HA_KEYTYPE_VARBINARY2:
+          /* Case-insensitiveness is handled in hash_sort */
+          /* fall_through */
+        case HA_KEYTYPE_VARTEXT2:
+          keyinfo->flag|= HA_VAR_LENGTH_KEY;
+          /*
+            For BTREE algorithm, key length, greater than or equal
+            to 255, is packed on 3 bytes.
+          */
+          if (keyinfo->algorithm == HA_KEY_ALG_BTREE)
+            length+= size_to_store_key_length(keyinfo->seg[j].length);
+          else
+            length+= 2;
+          /* Save number of bytes used to store length */
+          keyinfo->seg[j].bit_start= 2;
+          /*
+            Make future comparison simpler by only having to check for
+            one type
+          */
+          keyinfo->seg[j].type= HA_KEYTYPE_VARTEXT1;
+          break;
+        case HA_KEYTYPE_BIT:
+          /*
+            The odd bits which stored separately (if they are present
+            (bit_pos, bit_length)) are already present in seg[j].length as
+            additional byte.
+            See field.h, function key_length()
+          */
+          break;
+	default:
+	  break;
+	}
+      }
+      keyinfo->length= length;
+      length+= keyinfo->rb_tree.size_of_element + 
+	       ((keyinfo->algorithm == HA_KEY_ALG_BTREE) ? sizeof(uchar*) : 0);
+      if (length > max_length)
+	max_length= length;
+      key_segs+= keyinfo->keysegs;
+      if (keyinfo->algorithm == HA_KEY_ALG_BTREE)
+      {
+        key_segs++; /* additional HA_KEYTYPE_END segment */
+        if (keyinfo->flag & HA_VAR_LENGTH_KEY)
+          keyinfo->get_key_length= hp_rb_var_key_length;
+        else if (keyinfo->flag & HA_NULL_PART_KEY)
+          keyinfo->get_key_length= hp_rb_null_key_length;
+        else
+          keyinfo->get_key_length= hp_rb_key_length;
+      }
+    }
+    if (!(share= (HP_SHARE*) my_malloc(hp_key_memory_HP_SHARE,
+                                       sizeof(HP_SHARE)+
+				       keys*sizeof(HP_KEYDEF)+
+				       key_segs*sizeof(HA_KEYSEG),
+				       MYF(MY_ZEROFILL |
+                                           (create_info->internal_table ?
+                                            MY_THREAD_SPECIFIC : 0)))))
+      goto err;
+    share->keydef= (HP_KEYDEF*) (share + 1);
+    share->key_stat_version= 1;
+    keyseg= (HA_KEYSEG*) (share->keydef + keys);
+    init_block(&share->block, visible_offset + 1, min_records, max_records);
+	/* Fix keys */
+    memcpy(share->keydef, keydef, (size_t) (sizeof(keydef[0]) * keys));
+    for (i= 0, keyinfo= share->keydef; i < keys; i++, keyinfo++)
+    {
+      keyinfo->seg= keyseg;
+      memcpy(keyseg, keydef[i].seg,
+	     (size_t) (sizeof(keyseg[0]) * keydef[i].keysegs));
+      keyseg+= keydef[i].keysegs;
+
+      if (keydef[i].algorithm == HA_KEY_ALG_BTREE)
+      {
+	/* additional HA_KEYTYPE_END keyseg */
+	keyseg->type=     HA_KEYTYPE_END;
+	keyseg->length=   sizeof(uchar*);
+	keyseg->flag=     0;
+	keyseg->null_bit= 0;
+	keyseg++;
+
+	init_tree(&keyinfo->rb_tree, 0, 0, sizeof(uchar*),
+		  (qsort_cmp2)keys_compare, NULL, NULL,
+                  MYF((create_info->internal_table ? MY_THREAD_SPECIFIC : 0) |
+                      MY_TREE_WITH_DELETE));
+	keyinfo->delete_key= hp_rb_delete_key;
+	keyinfo->write_key= hp_rb_write_key;
+      }
+      else
+      {
+	init_block(&keyinfo->block, sizeof(HASH_INFO), min_records,
+		   max_records);
+	keyinfo->delete_key= hp_delete_key;
+	keyinfo->write_key= hp_write_key;
+        keyinfo->hash_buckets= 0;
+      }
+      if ((keyinfo->flag & HA_AUTO_KEY) && create_info->with_auto_increment)
+        share->auto_key= i + 1;
+    }
+    share->min_records= min_records;
+    share->max_records= max_records;
+    share->max_table_size= create_info->max_table_size;
+    share->data_length= share->index_length= 0;
+    share->reclength= reclength;
+    share->visible= visible_offset;
+    share->blength= 1;
+    share->keys= keys;
+    share->max_key_length= max_length;
+    share->changed= 0;
+    share->auto_key= create_info->auto_key;
+    share->auto_key_type= create_info->auto_key_type;
+    share->auto_increment= create_info->auto_increment;
+    share->create_time= (long) time((time_t*) 0);
+    share->internal= create_info->internal_table;
+    /* Must be allocated separately for rename to work */
+    if (!(share->name= my_strdup(hp_key_memory_HP_SHARE, name, MYF(0))))
+    {
+      my_free(share);
+      goto err;
+    }
+
+    if (!create_info->internal_table)
+    {
+      thr_lock_init(&share->lock);
+      share->open_list.data= (void*) share;
+      heap_share_list= list_add(heap_share_list,&share->open_list);
+    }
+    else
+      share->delete_on_close= 1;
+  }
+  if (!create_info->internal_table)
+  {
+    if (create_info->pin_share)
+      ++share->open_count;
+    mysql_mutex_unlock(&THR_LOCK_heap);
+  }
+
+  *res= share;
+  DBUG_RETURN(0);
+
+err:
+  if (!create_info->internal_table)
+    mysql_mutex_unlock(&THR_LOCK_heap);
+  DBUG_RETURN(1);
+} /* heap_create */
+
+
+static int keys_compare(heap_rb_param *param, uchar *key1, uchar *key2)
+{
+  uint not_used[2];
+  return ha_key_cmp(param->keyseg, key1, key2, param->key_length, 
+		    param->search_flag, not_used);
+}
+
+static void init_block(HP_BLOCK *block, uint reclength, ulong min_records,
+		       ulong max_records)
+{
+  ulong i,recbuffer,records_in_block;
+
+  /*
+    If not min_records and max_records are given, optimize for 1000 rows
+  */
+  if (!min_records)
+    min_records= MY_MIN(1000, max_records);
+  if (!max_records)
+    max_records= MY_MAX(min_records, 1000);
+
+  /*
+    We don't want too few records_in_block as otherwise the overhead of
+    of the HP_PTRS block will be too notable
+  */
+  records_in_block= MY_MAX(1000, min_records);
+  records_in_block= MY_MIN(records_in_block, max_records);
+  /* If big max_records is given, allocate bigger blocks */
+  records_in_block= MY_MAX(records_in_block, max_records / 10);
+  /* We don't want too few blocks per row either */
+  if (records_in_block < 10)
+    records_in_block= 10;
+
+  recbuffer= (uint) (reclength + sizeof(uchar**) - 1) & ~(sizeof(uchar**) - 1);
+  /*
+    Don't allocate more than my_default_record_cache_size per level.
+    The + 1 is there to ensure that we get at least 1 row per level (for
+    the exceptional case of very long rows)
+  */
+  if ((ulonglong) records_in_block*recbuffer >
+      (my_default_record_cache_size-sizeof(HP_PTRS)*HP_MAX_LEVELS))
+    records_in_block= (my_default_record_cache_size - sizeof(HP_PTRS) *
+                       HP_MAX_LEVELS) / recbuffer + 1;
+  block->records_in_block= records_in_block;
+  block->recbuffer= recbuffer;
+  block->last_allocated= 0L;
+
+  for (i= 0; i <= HP_MAX_LEVELS; i++)
+    block->level_info[i].records_under_level=
+      (!i ? 1 : i == 1 ? records_in_block :
+       HP_PTRS_IN_NOD * block->level_info[i - 1].records_under_level);
+}
+
+
+static inline void heap_try_free(HP_SHARE *share)
+{
+  DBUG_ENTER("heap_try_free");
+  if (share->open_count == 0)
+    hp_free(share);
+  else
+  {
+    DBUG_PRINT("info", ("Table is still in use. Will be freed on close"));
+    share->delete_on_close= 1;
+  }
+  DBUG_VOID_RETURN;
+}
+
+
+int heap_delete_table(const char *name)
+{
+  int result;
+  reg1 HP_SHARE *share;
+  DBUG_ENTER("heap_delete_table");
+
+  mysql_mutex_lock(&THR_LOCK_heap);
+  if ((share= hp_find_named_heap(name)))
+  {
+    heap_try_free(share);
+    result= 0;
+  }
+  else
+  {
+    result= my_errno=ENOENT;
+    DBUG_PRINT("error", ("Could not find table '%s'", name));
+  }
+  mysql_mutex_unlock(&THR_LOCK_heap);
+  DBUG_RETURN(result);
+}
+
+
+void heap_drop_table(HP_INFO *info)
+{
+  DBUG_ENTER("heap_drop_table");
+  mysql_mutex_lock(&THR_LOCK_heap);
+  heap_try_free(info->s);
+  mysql_mutex_unlock(&THR_LOCK_heap);
+  DBUG_VOID_RETURN;
+}
+
+
+void hp_free(HP_SHARE *share)
+{
+  if (!share->internal)
+  {
+    heap_share_list= list_delete(heap_share_list, &share->open_list);
+    thr_lock_delete(&share->lock);
+  }
+  hp_clear(share);			/* Remove blocks from memory */
+  my_free(share->name);
+  my_free(share);
+  return;
+}
diff --git a/storage/heap/hp_delete.c b/storage/heap/hp_delete.c
new file mode 100644
index 00000000..9579fb51
--- /dev/null
+++ b/storage/heap/hp_delete.c
@@ -0,0 +1,232 @@
+/* Copyright (c) 2000, 2012, Oracle and/or its affiliates. All rights reserved.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; version 2 of the License.
+
+   This program 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 General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1335  USA */
+
+/* remove current record in heap-database */
+
+#include "heapdef.h"
+
+int heap_delete(HP_INFO *info, const uchar *record)
+{
+  uchar *pos;
+  HP_SHARE *share=info->s;
+  HP_KEYDEF *keydef, *end, *p_lastinx;
+  DBUG_ENTER("heap_delete");
+  DBUG_PRINT("enter",("info: %p  record: %p", info, record));
+
+  test_active(info);
+
+  if (info->opt_flag & READ_CHECK_USED && hp_rectest(info,record))
+    DBUG_RETURN(my_errno);			/* Record changed */
+  share->changed=1;
+
+  if ( --(share->records) < share->blength >> 1) share->blength>>=1;
+  pos=info->current_ptr;
+
+  p_lastinx = share->keydef + info->lastinx;
+  for (keydef = share->keydef, end = keydef + share->keys; keydef < end; 
+       keydef++)
+  {
+    if ((*keydef->delete_key)(info, keydef, record, pos, keydef == p_lastinx))
+      goto err;
+  }
+
+  info->update=HA_STATE_DELETED;
+  *((uchar**) pos)=share->del_link;
+  share->del_link=pos;
+  pos[share->visible]=0;		/* Record deleted */
+  share->deleted++;
+  share->key_version++;
+#if !defined(DBUG_OFF) && defined(EXTRA_HEAP_DEBUG)
+  DBUG_EXECUTE("check_heap",heap_check_heap(info, 0););
+#endif
+
+  DBUG_RETURN(0);
+err:
+  if (++(share->records) == share->blength)
+    share->blength+= share->blength;
+  DBUG_RETURN(my_errno);
+}
+
+
+/*
+  Remove one key from rb-tree
+*/
+
+int hp_rb_delete_key(HP_INFO *info, register HP_KEYDEF *keyinfo,
+		   const uchar *record, uchar *recpos, int flag)
+{
+  heap_rb_param custom_arg;
+  size_t old_allocated;
+  int res;
+
+  if (flag) 
+    info->last_pos= NULL; /* For heap_rnext/heap_rprev */
+
+  custom_arg.keyseg= keyinfo->seg;
+  custom_arg.key_length= hp_rb_make_key(keyinfo, info->recbuf, record, recpos);
+  custom_arg.search_flag= SEARCH_SAME;
+  old_allocated= keyinfo->rb_tree.allocated;
+  res= tree_delete(&keyinfo->rb_tree, info->recbuf, custom_arg.key_length,
+                   &custom_arg);
+  info->s->index_length-= (old_allocated - keyinfo->rb_tree.allocated);
+  return res;
+}
+
+
+/*
+  Remove one key from hash-table
+
+  SYNPOSIS
+    hp_delete_key()
+    info		Hash handler
+    keyinfo		key definition of key that we want to delete
+    record		row data to be deleted
+    recpos		Pointer to heap record in memory
+    flag		Is set if we want's to correct info->current_ptr
+
+  RETURN
+    0      Ok
+    other  Error code
+*/
+
+int hp_delete_key(HP_INFO *info, register HP_KEYDEF *keyinfo,
+		  const uchar *record, uchar *recpos, int flag)
+{
+  ulong blength, pos2, pos_hashnr, lastpos_hashnr, key_pos;
+  HASH_INFO *lastpos,*gpos,*pos,*pos3,*empty,*last_ptr;
+  HP_SHARE *share=info->s;
+  DBUG_ENTER("hp_delete_key");
+
+  blength=share->blength;
+  if (share->records+1 == blength)
+    blength+= blength;
+  lastpos=hp_find_hash(&keyinfo->block,share->records);
+  last_ptr=0;
+
+  /* Search after record with key */
+  key_pos= hp_mask(hp_rec_hashnr(keyinfo, record), blength, share->records + 1);
+  pos= hp_find_hash(&keyinfo->block, key_pos);
+
+  gpos = pos3 = 0;
+
+  while (pos->ptr_to_rec != recpos)
+  {
+    if (flag && !hp_rec_key_cmp(keyinfo, record, pos->ptr_to_rec))
+      last_ptr=pos;				/* Previous same key */
+    gpos=pos;
+    if (!(pos=pos->next_key))
+    {
+      DBUG_RETURN(my_errno=HA_ERR_CRASHED);	/* This shouldn't happend */
+    }
+  }
+
+  /* Remove link to record */
+
+  if (flag)
+  {
+    /* Save for heap_rnext/heap_rprev */
+    info->current_hash_ptr=last_ptr;
+    info->current_ptr = last_ptr ? last_ptr->ptr_to_rec : 0;
+    DBUG_PRINT("info",("Corrected current_ptr to point at: %p",
+		       info->current_ptr));
+  }
+  empty=pos;
+  if (gpos)
+    gpos->next_key=pos->next_key;	/* unlink current ptr */
+  else if (pos->next_key)
+  {
+    empty=pos->next_key;
+    pos->ptr_to_rec=  empty->ptr_to_rec;
+    pos->next_key=    empty->next_key;
+    pos->hash_of_key= empty->hash_of_key;
+  }
+  else
+    keyinfo->hash_buckets--;
+
+  if (empty == lastpos)			/* deleted last hash key */
+    DBUG_RETURN (0);
+
+  /* Move the last key (lastpos) */
+  lastpos_hashnr= lastpos->hash_of_key;
+  /* pos is where lastpos should be */
+  pos=hp_find_hash(&keyinfo->block, hp_mask(lastpos_hashnr, share->blength,
+					    share->records));
+  if (pos == empty)			/* Move to empty position. */
+  {
+    empty[0]=lastpos[0];
+    DBUG_RETURN(0);
+  }
+  pos_hashnr= pos->hash_of_key;
+  /* pos3 is where the pos should be */
+  pos3= hp_find_hash(&keyinfo->block,
+		     hp_mask(pos_hashnr, share->blength, share->records));
+  if (pos != pos3)
+  {					/* pos is on wrong posit */
+    empty[0]=pos[0];			/* Save it here */
+    pos[0]=lastpos[0];			/* This shold be here */
+    hp_movelink(pos, pos3, empty);	/* Fix link to pos */
+    DBUG_RETURN(0);
+  }
+  pos2= hp_mask(lastpos_hashnr, blength, share->records + 1);
+  if (pos2 == hp_mask(pos_hashnr, blength, share->records + 1))
+  {
+    /* lastpos and the row in the main bucket entry (pos) has the same hash */ 
+    if (pos2 != share->records)
+    {
+      /*
+        The bucket entry was not deleted. Copy lastpos over the
+        deleted entry and update previous link to point to it.
+      */
+      empty[0]= lastpos[0];
+      hp_movelink(lastpos, pos, empty);
+      if (last_ptr == lastpos)
+      {
+        /*
+          We moved the row that info->current_hash_ptr points to.
+          Update info->current_hash_ptr to point to the new position.
+        */
+        info->current_hash_ptr= empty;
+      }
+      DBUG_RETURN(0);
+    }
+    /*
+      Shrinking the hash table deleted the main bucket entry for this hash.
+      In this case the last entry was the first key in the key chain.
+      We move things around so that we keep the original key order to ensure
+      that heap_rnext() works.
+      
+      - Move the row at the main bucket entry to the empty spot.
+      - Move the last entry first in the new chain.
+      - Link in the first element of the hash.
+    */
+    empty[0]= pos[0];
+    pos[0]= lastpos[0];
+    hp_movelink(pos, pos, empty);
+
+    /* Update current_hash_ptr if the entry moved */
+    if (last_ptr == lastpos)
+      info->current_hash_ptr= pos;
+    else if (last_ptr == pos)
+      info->current_hash_ptr= empty;
+    DBUG_RETURN(0);
+  }
+
+  pos3= 0;				/* Different positions merge */
+  keyinfo->hash_buckets--;
+  empty[0]=lastpos[0];
+  hp_movelink(pos3, empty, pos->next_key);
+  pos->next_key=empty;
+  DBUG_RETURN(0);
+}
diff --git a/storage/heap/hp_extra.c b/storage/heap/hp_extra.c
new file mode 100644
index 00000000..3c554fe9
--- /dev/null
+++ b/storage/heap/hp_extra.c
@@ -0,0 +1,87 @@
+/* Copyright (c) 2000, 2004-2006 MySQL AB
+   Use is subject to license terms
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; version 2 of the License.
+
+   This program 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 General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1335  USA */
+
+/* Extra functions we want to do with a database */
+/* - Set flags for quicker databasehandler */
+/* - Set databasehandler to normal */
+/* - Reset recordpointers as after open database */
+
+#include "heapdef.h"
+
+static void heap_extra_keyflag(register HP_INFO *info,
+                               enum ha_extra_function function);
+
+
+	/* set extra flags for database */
+
+int heap_extra(register HP_INFO *info, enum ha_extra_function function)
+{
+  DBUG_ENTER("heap_extra");
+
+  switch (function) {
+  case HA_EXTRA_RESET_STATE:
+    heap_reset(info);
+    /* fall through */
+  case HA_EXTRA_NO_READCHECK:
+    info->opt_flag&= ~READ_CHECK_USED;	/* No readcheck */
+    break;
+  case HA_EXTRA_READCHECK:
+    info->opt_flag|= READ_CHECK_USED;
+    break;
+  case HA_EXTRA_CHANGE_KEY_TO_UNIQUE:
+  case HA_EXTRA_CHANGE_KEY_TO_DUP:
+    heap_extra_keyflag(info, function);
+    break;
+  default:
+    break;
+  }
+  DBUG_RETURN(0);
+} /* heap_extra */
+
+
+int heap_reset(HP_INFO *info)
+{
+  info->lastinx= -1;
+  info->current_record= (ulong) ~0L;
+  info->current_hash_ptr=0;
+  info->update=0;
+  info->next_block=0;
+  return 0;
+}
+
+
+/*
+    Start/Stop Inserting Duplicates Into a Table, WL#1648.
+ */
+static void heap_extra_keyflag(register HP_INFO *info,
+                               enum ha_extra_function function)
+{
+  uint  idx;
+
+  for (idx= 0; idx< info->s->keys; idx++)
+  {
+    switch (function) {
+    case HA_EXTRA_CHANGE_KEY_TO_UNIQUE:
+      info->s->keydef[idx].flag|= HA_NOSAME;
+      break;
+    case HA_EXTRA_CHANGE_KEY_TO_DUP:
+      info->s->keydef[idx].flag&= ~(HA_NOSAME);
+      break;
+    default:
+      break;
+    }
+  }
+}
diff --git a/storage/heap/hp_hash.c b/storage/heap/hp_hash.c
new file mode 100644
index 00000000..a0139151
--- /dev/null
+++ b/storage/heap/hp_hash.c
@@ -0,0 +1,920 @@
+/*
+   Copyright (c) 2000, 2010, Oracle and/or its affiliates
+   Copyright (c) 2020, MariaDB Corporation.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; version 2 of the License.
+
+   This program 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 General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1335  USA */
+
+/* The hash functions used for saveing keys */
+
+#include "heapdef.h"
+#include <m_ctype.h>
+
+
+static inline size_t
+hp_charpos(CHARSET_INFO *cs, const uchar *b, const uchar *e, size_t num)
+{
+  return my_ci_charpos(cs, (const char*) b, (const char *) e, num);
+}
+
+
+static ulong hp_hashnr(HP_KEYDEF *keydef, const uchar *key);
+/*
+  Find out how many rows there is in the given range
+
+  SYNOPSIS
+    hp_rb_records_in_range()
+    info		HEAP handler
+    inx			Index to use
+    min_key		Min key. Is = 0 if no min range
+    max_key		Max key. Is = 0 if no max range
+
+  NOTES
+    min_key.flag can have one of the following values:
+      HA_READ_KEY_EXACT		Include the key in the range
+      HA_READ_AFTER_KEY		Don't include key in range
+
+    max_key.flag can have one of the following values:
+      HA_READ_BEFORE_KEY	Don't include key in range
+      HA_READ_AFTER_KEY		Include all 'end_key' values in the range
+
+  RETURN
+   HA_POS_ERROR		Something is wrong with the index tree.
+   0			There is no matching keys in the given range
+   number > 0		There is approximately 'number' matching rows in
+			the range.
+*/
+
+ha_rows hp_rb_records_in_range(HP_INFO *info, int inx,
+                               const key_range *min_key,
+                               const key_range *max_key)
+{
+  ha_rows start_pos, end_pos;
+  HP_KEYDEF *keyinfo= info->s->keydef + inx;
+  TREE *rb_tree = &keyinfo->rb_tree;
+  heap_rb_param custom_arg;
+  DBUG_ENTER("hp_rb_records_in_range");
+
+  info->lastinx= inx;
+  custom_arg.keyseg= keyinfo->seg;
+  custom_arg.search_flag= SEARCH_FIND | SEARCH_SAME;
+  if (min_key)
+  {
+    custom_arg.key_length= hp_rb_pack_key(keyinfo, (uchar*) info->recbuf,
+					  (uchar*) min_key->key,
+					  min_key->keypart_map);
+    start_pos= tree_record_pos(rb_tree, info->recbuf, min_key->flag,
+			       &custom_arg);
+  }
+  else
+  {
+    start_pos= 0;
+  }
+
+  if (max_key)
+  {
+    custom_arg.key_length= hp_rb_pack_key(keyinfo, (uchar*) info->recbuf,
+					  (uchar*) max_key->key,
+                                          max_key->keypart_map);
+    end_pos= tree_record_pos(rb_tree, info->recbuf, max_key->flag,
+			     &custom_arg);
+  }
+  else
+  {
+    end_pos= rb_tree->elements_in_tree + (ha_rows)1;
+  }
+
+  DBUG_PRINT("info",("start_pos: %lu  end_pos: %lu", (ulong) start_pos,
+		     (ulong) end_pos));
+  if (start_pos == HA_POS_ERROR || end_pos == HA_POS_ERROR)
+    DBUG_RETURN(HA_POS_ERROR);
+  DBUG_RETURN(end_pos < start_pos ? (ha_rows) 0 :
+	      (end_pos == start_pos ? (ha_rows) 1 : end_pos - start_pos));
+}
+
+
+	/* Search after a record based on a key */
+	/* Sets info->current_ptr to found record */
+	/* next_flag:  Search=0, next=1, prev =2, same =3 */
+
+uchar *hp_search(HP_INFO *info, HP_KEYDEF *keyinfo, const uchar *key,
+                uint nextflag)
+{
+  reg1 HASH_INFO *pos,*prev_ptr;
+  uint old_nextflag;
+  HP_SHARE *share=info->s;
+  DBUG_ENTER("hp_search");
+  old_nextflag=nextflag;
+  prev_ptr=0;
+
+  if (share->records)
+  {
+    ulong search_pos=
+      hp_mask(hp_hashnr(keyinfo, key), share->blength, share->records);
+    pos=hp_find_hash(&keyinfo->block, search_pos);
+    if (search_pos !=
+        hp_mask(pos->hash_of_key, share->blength, share->records))
+      goto not_found;                           /* Wrong link */
+    do
+    {
+      if (!hp_key_cmp(keyinfo, pos->ptr_to_rec, key))
+      {
+	switch (nextflag) {
+	case 0:					/* Search after key */
+	  DBUG_PRINT("exit", ("found key at %p", pos->ptr_to_rec));
+	  info->current_hash_ptr=pos;
+	  DBUG_RETURN(info->current_ptr= pos->ptr_to_rec);
+	case 1:					/* Search next */
+	  if (pos->ptr_to_rec == info->current_ptr)
+	    nextflag=0;
+	  break;
+	case 2:					/* Search previous */
+	  if (pos->ptr_to_rec == info->current_ptr)
+	  {
+	    my_errno=HA_ERR_KEY_NOT_FOUND;	/* If gpos == 0 */
+	    info->current_hash_ptr=prev_ptr;
+	    DBUG_RETURN(info->current_ptr=prev_ptr ? prev_ptr->ptr_to_rec : 0);
+	  }
+	  prev_ptr=pos;				/* Prev. record found */
+	  break;
+	case 3:					/* Search same */
+	  if (pos->ptr_to_rec == info->current_ptr)
+	  {
+	    info->current_hash_ptr=pos;
+	    DBUG_RETURN(info->current_ptr);
+	  }
+	}
+      }
+    }
+    while ((pos=pos->next_key));
+  }
+
+not_found:
+  my_errno=HA_ERR_KEY_NOT_FOUND;
+  if (nextflag == 2 && ! info->current_ptr)
+  {
+    /* Do a previous from end */
+    info->current_hash_ptr=prev_ptr;
+    DBUG_RETURN(info->current_ptr=prev_ptr ? prev_ptr->ptr_to_rec : 0);
+  }
+
+  if (old_nextflag && nextflag)
+    my_errno=HA_ERR_RECORD_CHANGED;		/* Didn't find old record */
+  DBUG_PRINT("exit",("Error: %d",my_errno));
+  info->current_hash_ptr=0;  
+  DBUG_RETURN((info->current_ptr= 0));
+}
+
+
+/*
+  Search next after last read;  Assumes that the table hasn't changed
+  since last read !
+*/
+
+uchar *hp_search_next(HP_INFO *info, HP_KEYDEF *keyinfo, const uchar *key,
+		      HASH_INFO *pos)
+{
+  DBUG_ENTER("hp_search_next");
+
+  while ((pos= pos->next_key))
+  {
+    if (! hp_key_cmp(keyinfo, pos->ptr_to_rec, key))
+    {
+      info->current_hash_ptr=pos;
+      DBUG_RETURN (info->current_ptr= pos->ptr_to_rec);
+    }
+  }
+  my_errno=HA_ERR_KEY_NOT_FOUND;
+  DBUG_PRINT("exit",("Error: %d",my_errno));
+  info->current_hash_ptr=0;
+  DBUG_RETURN ((info->current_ptr= 0));
+}
+
+
+/*
+  Change
+    next_link -> ... -> X -> pos
+  to
+    next_link -> ... -> X -> newlink
+*/
+
+void hp_movelink(HASH_INFO *pos, HASH_INFO *next_link, HASH_INFO *newlink)
+{
+  HASH_INFO *old_link;
+  do
+  {
+    old_link=next_link;
+  }
+  while ((next_link=next_link->next_key) != pos);
+  old_link->next_key=newlink;
+  return;
+}
+
+	/* Calc hashvalue for a key */
+
+static ulong hp_hashnr(HP_KEYDEF *keydef, const uchar *key)
+{
+  /*register*/ 
+  ulong nr=1, nr2=4;
+  HA_KEYSEG *seg,*endseg;
+
+  for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
+  {
+    uchar *pos=(uchar*) key;
+    key+=seg->length;
+    if (seg->null_bit)
+    {
+      key++;					/* Skip null byte */
+      if (*pos)					/* Found null */
+      {
+	nr^= (nr << 1) | 1;
+	/* Add key pack length (2) to key for VARCHAR segments */
+        if (seg->type == HA_KEYTYPE_VARTEXT1)
+          key+= 2;
+	continue;
+      }
+      pos++;
+    }
+    if (seg->type == HA_KEYTYPE_TEXT)
+    {
+       CHARSET_INFO *cs= seg->charset;
+       size_t length= seg->length;
+       if (cs->mbmaxlen > 1)
+       {
+         size_t char_length;
+         char_length= hp_charpos(cs, pos, pos + length, length/cs->mbmaxlen);
+         set_if_smaller(length, char_length);
+       }
+       my_ci_hash_sort(cs, pos, length, &nr, &nr2);
+    }
+    else if (seg->type == HA_KEYTYPE_VARTEXT1)  /* Any VARCHAR segments */
+    {
+       CHARSET_INFO *cs= seg->charset;
+       size_t pack_length= 2;                     /* Key packing is constant */
+       size_t length= uint2korr(pos);
+       if (cs->mbmaxlen > 1)
+       {
+         size_t char_length;
+         char_length= hp_charpos(cs, pos +pack_length,
+                                 pos +pack_length + length,
+                                 seg->length/cs->mbmaxlen);
+         set_if_smaller(length, char_length);
+       }
+       my_ci_hash_sort(cs, pos+pack_length, length, &nr, &nr2);
+       key+= pack_length;
+    }
+    else
+    {
+      for (; pos < (uchar*) key ; pos++)
+      {
+	nr^=(ulong) ((((uint) nr & 63)+nr2)*((uint) *pos)) + (nr << 8);
+	nr2+=3;
+      }
+    }
+  }
+#ifdef ONLY_FOR_HASH_DEBUGGING
+  DBUG_PRINT("exit", ("hash: 0x%lx", nr));
+#endif
+  return((ulong) nr);
+}
+
+	/* Calc hashvalue for a key in a record */
+
+ulong hp_rec_hashnr(register HP_KEYDEF *keydef, register const uchar *rec)
+{
+  ulong nr=1, nr2=4;
+  HA_KEYSEG *seg,*endseg;
+
+  for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
+  {
+    uchar *pos=(uchar*) rec+seg->start,*end=pos+seg->length;
+    if (seg->null_bit)
+    {
+      if (rec[seg->null_pos] & seg->null_bit)
+      {
+	nr^= (nr << 1) | 1;
+	continue;
+      }
+    }
+    if (seg->type == HA_KEYTYPE_TEXT)
+    {
+      CHARSET_INFO *cs= seg->charset;
+      size_t char_length= seg->length;
+      if (cs->mbmaxlen > 1)
+      {
+        char_length= hp_charpos(cs, pos, pos + char_length,
+                                char_length / cs->mbmaxlen);
+        set_if_smaller(char_length, seg->length); /* QQ: ok to remove? */
+      }
+      my_ci_hash_sort(cs, pos, char_length, &nr, &nr2);
+    }
+    else if (seg->type == HA_KEYTYPE_VARTEXT1)  /* Any VARCHAR segments */
+    {
+      CHARSET_INFO *cs= seg->charset;
+      size_t pack_length= seg->bit_start;
+      size_t length= (pack_length == 1 ? (size_t) *(uchar*) pos : uint2korr(pos));
+      if (cs->mbmaxlen > 1)
+      {
+        size_t char_length;
+        char_length= hp_charpos(cs, pos + pack_length,
+                                pos + pack_length + length,
+                                seg->length/cs->mbmaxlen);
+        set_if_smaller(length, char_length);
+      }
+      else
+        set_if_smaller(length, seg->length);
+      my_ci_hash_sort(cs, pos+pack_length, length, &nr, &nr2);
+    }
+    else
+    {
+      if (seg->type == HA_KEYTYPE_BIT && seg->bit_length)
+      {
+        uchar bits= get_rec_bits(rec + seg->bit_pos,
+                                 seg->bit_start, seg->bit_length);
+	nr^=(ulong) ((((uint) nr & 63)+nr2)*((uint) bits))+ (nr << 8);
+	nr2+=3;
+        end--;
+      }
+
+      for (; pos < end ; pos++)
+      {
+	nr^=(ulong) ((((uint) nr & 63)+nr2)*((uint) *pos))+ (nr << 8);
+	nr2+=3;
+      }
+    }
+  }
+#ifdef ONLY_FOR_HASH_DEBUGGING
+  DBUG_PRINT("exit", ("hash: 0x%lx", nr));
+#endif
+  return(nr);
+}
+
+
+/*
+  Compare keys for two records. Returns 0 if they are identical
+
+  SYNOPSIS
+    hp_rec_key_cmp()
+    keydef		Key definition
+    rec1		Record to compare
+    rec2		Other record to compare
+
+  NOTES
+    diff_if_only_endspace_difference is used to allow us to insert
+    'a' and 'a ' when there is an an unique key.
+
+  RETURN
+    0		Key is identical
+    <> 0 	Key differes
+*/
+
+int hp_rec_key_cmp(HP_KEYDEF *keydef, const uchar *rec1, const uchar *rec2)
+{
+  HA_KEYSEG *seg,*endseg;
+
+  for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
+  {
+    if (seg->null_bit)
+    {
+      if ((rec1[seg->null_pos] & seg->null_bit) !=
+	  (rec2[seg->null_pos] & seg->null_bit))
+	return 1;
+      if (rec1[seg->null_pos] & seg->null_bit)
+	continue;
+    }
+    if (seg->type == HA_KEYTYPE_TEXT)
+    {
+      CHARSET_INFO *cs= seg->charset;
+      size_t char_length1;
+      size_t char_length2;
+      uchar *pos1= (uchar*)rec1 + seg->start;
+      uchar *pos2= (uchar*)rec2 + seg->start;
+      if (cs->mbmaxlen > 1)
+      {
+        size_t char_length= seg->length / cs->mbmaxlen;
+        char_length1= hp_charpos(cs, pos1, pos1 + seg->length, char_length);
+        set_if_smaller(char_length1, seg->length);
+        char_length2= hp_charpos(cs, pos2, pos2 + seg->length, char_length);
+        set_if_smaller(char_length2, seg->length);
+      }
+      else
+      {
+        char_length1= char_length2= seg->length;
+      }
+      if (my_ci_strnncollsp(seg->charset,
+                            pos1, char_length1,
+                            pos2, char_length2))
+	return 1;
+    }
+    else if (seg->type == HA_KEYTYPE_VARTEXT1)  /* Any VARCHAR segments */
+    {
+      uchar *pos1= (uchar*) rec1 + seg->start;
+      uchar *pos2= (uchar*) rec2 + seg->start;
+      size_t char_length1, char_length2;
+      size_t pack_length= seg->bit_start;
+      CHARSET_INFO *cs= seg->charset;
+      if (pack_length == 1)
+      {
+        char_length1= (size_t) *(uchar*) pos1++;
+        char_length2= (size_t) *(uchar*) pos2++;
+      }
+      else
+      {
+        char_length1= uint2korr(pos1);
+        char_length2= uint2korr(pos2);
+        pos1+= 2;
+        pos2+= 2;
+      }
+      if (cs->mbmaxlen > 1)
+      {
+        size_t safe_length1= char_length1;
+        size_t safe_length2= char_length2;
+        size_t char_length= seg->length / cs->mbmaxlen;
+        char_length1= hp_charpos(cs, pos1, pos1 + char_length1, char_length);
+        set_if_smaller(char_length1, safe_length1);
+        char_length2= hp_charpos(cs, pos2, pos2 + char_length2, char_length);
+        set_if_smaller(char_length2, safe_length2);
+      }
+      else
+      {
+        set_if_smaller(char_length1, seg->length);
+        set_if_smaller(char_length2, seg->length);
+      }
+
+      if (my_ci_strnncollsp(seg->charset,
+                            pos1, char_length1,
+                            pos2, char_length2))
+	return 1;
+    }
+    else
+    {
+      uint dec= 0;
+      if (seg->type == HA_KEYTYPE_BIT && seg->bit_length)
+      {
+        uchar bits1= get_rec_bits(rec1 + seg->bit_pos,
+                                  seg->bit_start, seg->bit_length);
+        uchar bits2= get_rec_bits(rec2 + seg->bit_pos,
+                                  seg->bit_start, seg->bit_length);
+        if (bits1 != bits2)
+          return 1;
+        dec= 1;
+      }
+      if (bcmp(rec1 + seg->start, rec2 + seg->start, seg->length - dec))
+	return 1;
+    }
+  }
+  return 0;
+}
+
+	/* Compare a key in a record to a whole key */
+
+int hp_key_cmp(HP_KEYDEF *keydef, const uchar *rec, const uchar *key)
+{
+  HA_KEYSEG *seg,*endseg;
+
+  for (seg=keydef->seg,endseg=seg+keydef->keysegs ;
+       seg < endseg ;
+       key+= (seg++)->length)
+  {
+    if (seg->null_bit)
+    {
+      int found_null= MY_TEST(rec[seg->null_pos] & seg->null_bit);
+      if (found_null != (int) *key++)
+	return 1;
+      if (found_null)
+      {
+        /* Add key pack length (2) to key for VARCHAR segments */
+        if (seg->type == HA_KEYTYPE_VARTEXT1)
+          key+= 2;
+	continue;
+      }
+    }
+    if (seg->type == HA_KEYTYPE_TEXT)
+    {
+      CHARSET_INFO *cs= seg->charset;
+      size_t char_length_key;
+      size_t char_length_rec;
+      uchar *pos= (uchar*) rec + seg->start;
+      if (cs->mbmaxlen > 1)
+      {
+        size_t char_length= seg->length / cs->mbmaxlen;
+        char_length_key= hp_charpos(cs, key, key + seg->length, char_length);
+        set_if_smaller(char_length_key, seg->length);
+        char_length_rec= hp_charpos(cs, pos, pos + seg->length, char_length);
+        set_if_smaller(char_length_rec, seg->length);
+      }
+      else
+      {
+        char_length_key= seg->length;
+        char_length_rec= seg->length;
+      }
+      
+      if (my_ci_strnncollsp(seg->charset,
+                            pos, char_length_rec,
+                            key, char_length_key))
+	return 1;
+    }
+    else if (seg->type == HA_KEYTYPE_VARTEXT1)  /* Any VARCHAR segments */
+    {
+      uchar *pos= (uchar*) rec + seg->start;
+      CHARSET_INFO *cs= seg->charset;
+      size_t pack_length= seg->bit_start;
+      size_t char_length_rec= (pack_length == 1 ? (size_t) *(uchar*) pos :
+                             uint2korr(pos));
+      /* Key segments are always packed with 2 bytes */
+      size_t char_length_key= uint2korr(key);
+      pos+= pack_length;
+      key+= 2;                                  /* skip key pack length */
+      if (cs->mbmaxlen > 1)
+      {
+        size_t char_length1, char_length2;
+        char_length1= char_length2= seg->length / cs->mbmaxlen; 
+        char_length1= hp_charpos(cs, key, key + char_length_key, char_length1);
+        set_if_smaller(char_length_key, char_length1);
+        char_length2= hp_charpos(cs, pos, pos + char_length_rec, char_length2);
+        set_if_smaller(char_length_rec, char_length2);
+      }
+      else
+        set_if_smaller(char_length_rec, seg->length);
+
+      if (my_ci_strnncollsp(seg->charset,
+                            pos, char_length_rec,
+                            key, char_length_key))
+	return 1;
+    }
+    else
+    {
+      uint dec= 0;
+      if (seg->type == HA_KEYTYPE_BIT && seg->bit_length)
+      {
+        uchar bits= get_rec_bits(rec + seg->bit_pos,
+                                 seg->bit_start, seg->bit_length);
+        if (bits != (*key))
+          return 1;
+        dec= 1;
+        key++;
+      }
+
+      if (bcmp(rec + seg->start, key, seg->length - dec))
+	return 1;
+    }
+  }
+  return 0;
+}
+
+
+	/* Copy a key from a record to a keybuffer */
+
+void hp_make_key(HP_KEYDEF *keydef, uchar *key, const uchar *rec)
+{
+  HA_KEYSEG *seg,*endseg;
+
+  for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
+  {
+    CHARSET_INFO *cs= seg->charset;
+    size_t char_length= seg->length;
+    uchar *pos= (uchar*) rec + seg->start;
+    if (seg->null_bit)
+      *key++= MY_TEST(rec[seg->null_pos] & seg->null_bit);
+    if (cs->mbmaxlen > 1)
+    {
+      char_length= hp_charpos(cs, pos, pos + seg->length,
+                              char_length / cs->mbmaxlen);
+      set_if_smaller(char_length, seg->length); /* QQ: ok to remove? */
+    }
+    if (seg->type == HA_KEYTYPE_VARTEXT1)
+      char_length+= seg->bit_start;             /* Copy also length */
+    else if (seg->type == HA_KEYTYPE_BIT && seg->bit_length)
+    {
+      *key++= get_rec_bits(rec + seg->bit_pos,
+                           seg->bit_start, seg->bit_length);
+      char_length--;
+    }
+    memcpy(key,rec+seg->start,(size_t) char_length);
+    key+= char_length;
+  }
+}
+
+#define FIX_LENGTH(cs, pos, length, char_length)                        \
+  do {                                                                  \
+    if (length > char_length)                                           \
+      char_length= hp_charpos(cs, pos, pos+length, char_length);        \
+    set_if_smaller(char_length,length);                                 \
+  } while(0)
+
+
+uint hp_rb_make_key(HP_KEYDEF *keydef, uchar *key, 
+		    const uchar *rec, uchar *recpos)
+{
+  uchar *start_key= key;
+  HA_KEYSEG *seg, *endseg;
+
+  for (seg= keydef->seg, endseg= seg + keydef->keysegs; seg < endseg; seg++)
+  {
+    size_t char_length;
+    if (seg->null_bit)
+    {
+      if (!(*key++= 1 - MY_TEST(rec[seg->null_pos] & seg->null_bit)))
+        continue;
+    }
+    if (seg->flag & HA_SWAP_KEY)
+    {
+      uint length= seg->length;
+      uchar *pos= (uchar*) rec + seg->start;
+      DBUG_ASSERT(seg->type != HA_KEYTYPE_BIT);
+
+      if (seg->type == HA_KEYTYPE_FLOAT)
+      {
+	float nr;
+	float4get(nr, pos);
+	if (isnan(nr))
+	{
+	  /* Replace NAN with zero */
+ 	  bzero(key, length);
+	  key+= length;
+	  continue;
+	}
+      }
+      else if (seg->type == HA_KEYTYPE_DOUBLE)
+      {
+	double nr;
+	float8get(nr, pos);
+	if (isnan(nr))
+	{
+ 	  bzero(key, length);
+	  key+= length;
+	  continue;
+	}
+      }
+      pos+= length;
+      while (length--)
+      {
+	*key++= *--pos;
+      }
+      continue;
+    }
+
+    if (seg->flag & HA_VAR_LENGTH_PART)
+    {
+      uchar *pos=      (uchar*) rec + seg->start;
+      size_t length=     seg->length;
+      size_t pack_length= seg->bit_start;
+      size_t tmp_length= (pack_length == 1 ? (uint) *(uchar*) pos :
+                        uint2korr(pos));
+      CHARSET_INFO *cs= seg->charset;
+      char_length= length/cs->mbmaxlen;
+
+      pos+= pack_length;			/* Skip VARCHAR length */
+      set_if_smaller(length,tmp_length);
+      FIX_LENGTH(cs, pos, length, char_length);
+      store_key_length_inc(key,char_length);
+      memcpy((uchar*) key,(uchar*) pos,(size_t) char_length);
+      key+= char_length;
+      continue;
+    }
+
+    char_length= seg->length;
+    if (seg->charset->mbmaxlen > 1)
+    {
+      char_length= hp_charpos(seg->charset, 
+                              rec + seg->start, rec + seg->start + char_length,
+                              char_length / seg->charset->mbmaxlen);
+      set_if_smaller(char_length, seg->length); /* QQ: ok to remove? */
+      if (char_length < seg->length)
+        my_ci_fill(seg->charset, (char*) key + char_length,
+                                 seg->length - char_length, ' ');
+    }
+    if (seg->type == HA_KEYTYPE_BIT && seg->bit_length)
+    {
+      *key++= get_rec_bits(rec + seg->bit_pos,
+                           seg->bit_start, seg->bit_length);
+      char_length--;
+    }
+    memcpy(key, rec + seg->start, (size_t) char_length);
+    key+= seg->length;
+  }
+  memcpy(key, &recpos, sizeof(uchar*));
+  return (uint) (key - start_key);
+}
+
+
+uint hp_rb_pack_key(HP_KEYDEF *keydef, uchar *key, const uchar *old,
+                    key_part_map keypart_map)
+{
+  HA_KEYSEG *seg, *endseg;
+  uchar *start_key= key;
+
+  for (seg= keydef->seg, endseg= seg + keydef->keysegs;
+       seg < endseg && keypart_map; old+= seg->length, seg++)
+  {
+    size_t char_length;
+    keypart_map>>= 1;
+    if (seg->null_bit)
+    {
+      /* Convert NULL from MySQL representation into HEAP's. */
+      if (!(*key++= (char) 1 - *old++))
+      {
+	/* Add key pack length (2) to key for VARCHAR segments */
+        if (seg->type == HA_KEYTYPE_VARTEXT1)
+          old+= 2;
+        continue;
+      }
+    }
+    if (seg->flag & HA_SWAP_KEY)
+    {
+      uint length= seg->length;
+      uchar *pos= (uchar*) old + length;
+      
+      while (length--)
+      {
+	*key++= *--pos;
+      }
+      continue;
+    }
+    if (seg->flag & (HA_VAR_LENGTH_PART | HA_BLOB_PART))
+    {
+      /* Length of key-part used with heap_rkey() always 2 */
+      size_t tmp_length=uint2korr(old);
+      size_t length= seg->length;
+      CHARSET_INFO *cs= seg->charset;
+      char_length= length/cs->mbmaxlen;
+
+      old+= 2;
+      set_if_smaller(length,tmp_length);	/* Safety */
+      FIX_LENGTH(cs, old, length, char_length);
+      store_key_length_inc(key,char_length);
+      memcpy((uchar*) key, old,(size_t) char_length);
+      key+= char_length;
+      continue;
+    }
+    char_length= seg->length;
+    if (seg->charset->mbmaxlen > 1)
+    {
+      char_length= hp_charpos(seg->charset, old, old+char_length,
+                              char_length / seg->charset->mbmaxlen);
+      set_if_smaller(char_length, seg->length); /* QQ: ok to remove? */
+      if (char_length < seg->length)
+        my_ci_fill(seg->charset, (char*) key + char_length,
+                                 seg->length - char_length, ' ');
+    }
+    memcpy(key, old, (size_t) char_length);
+    key+= seg->length;
+  }
+  return (uint) (key - start_key);
+}
+
+
+uint hp_rb_key_length(HP_KEYDEF *keydef, 
+		      const uchar *key __attribute__((unused)))
+{
+  return keydef->length;
+}
+
+
+uint hp_rb_null_key_length(HP_KEYDEF *keydef, const uchar *key)
+{
+  const uchar *start_key= key;
+  HA_KEYSEG *seg, *endseg;
+  
+  for (seg= keydef->seg, endseg= seg + keydef->keysegs; seg < endseg; seg++)
+  {
+    if (seg->null_bit && !*key++)
+      continue;
+    key+= seg->length;
+  }
+  return (uint) (key - start_key);
+}
+                  
+
+uint hp_rb_var_key_length(HP_KEYDEF *keydef, const uchar *key)
+{
+  const uchar *start_key= key;
+  HA_KEYSEG *seg, *endseg;
+  
+  for (seg= keydef->seg, endseg= seg + keydef->keysegs; seg < endseg; seg++)
+  {
+    uint length= seg->length;
+    if (seg->null_bit && !*key++)
+      continue;
+    if (seg->flag & (HA_VAR_LENGTH_PART | HA_BLOB_PART))
+    {
+      get_key_length(length, key);
+    }
+    key+= length;
+  }
+  return (uint) (key - start_key);
+}
+
+
+/*
+  Test if any of the key parts are NULL.
+  Return:
+    1 if any of the key parts was NULL
+    0 otherwise
+*/
+
+my_bool hp_if_null_in_key(HP_KEYDEF *keydef, const uchar *record)
+{
+  HA_KEYSEG *seg,*endseg;
+  for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
+  {
+    if (seg->null_bit && (record[seg->null_pos] & seg->null_bit))
+      return 1;
+  }
+  return 0;
+}
+
+
+/*
+  Update auto_increment info
+
+  SYNOPSIS
+    update_auto_increment()
+    info			MyISAM handler
+    record			Row to update
+
+  IMPLEMENTATION
+    Only replace the auto_increment value if it is higher than the previous
+    one. For signed columns we don't update the auto increment value if it's
+    less than zero.
+*/
+
+void heap_update_auto_increment(HP_INFO *info, const uchar *record)
+{
+  ulonglong value= 0;			/* Store unsigned values here */
+  longlong s_value= 0;			/* Store signed values here */
+
+  HA_KEYSEG *keyseg= info->s->keydef[info->s->auto_key - 1].seg;
+  const uchar *key=  (uchar*) record + keyseg->start;
+
+  switch (info->s->auto_key_type) {
+  case HA_KEYTYPE_INT8:
+    s_value= (longlong) *(const signed char*) key;
+    break;
+  case HA_KEYTYPE_BINARY:
+    value=(ulonglong)  *(uchar*) key;
+    break;
+  case HA_KEYTYPE_SHORT_INT:
+    s_value= (longlong) sint2korr(key);
+    break;
+  case HA_KEYTYPE_USHORT_INT:
+    value=(ulonglong) uint2korr(key);
+    break;
+  case HA_KEYTYPE_LONG_INT:
+    s_value= (longlong) sint4korr(key);
+    break;
+  case HA_KEYTYPE_ULONG_INT:
+    value=(ulonglong) uint4korr(key);
+    break;
+  case HA_KEYTYPE_INT24:
+    s_value= (longlong) sint3korr(key);
+    break;
+  case HA_KEYTYPE_UINT24:
+    value=(ulonglong) uint3korr(key);
+    break;
+  case HA_KEYTYPE_FLOAT:                        /* This shouldn't be used */
+  {
+    float f_1;
+    float4get(f_1,key);
+    /* Ignore negative values */
+    value = (f_1 < (float) 0.0) ? 0 : (ulonglong) f_1;
+    break;
+  }
+  case HA_KEYTYPE_DOUBLE:                       /* This shouldn't be used */
+  {
+    double f_1;
+    float8get(f_1,key);
+    /* Ignore negative values */
+    value = (f_1 < 0.0) ? 0 : (ulonglong) f_1;
+    break;
+  }
+  case HA_KEYTYPE_LONGLONG:
+    s_value= sint8korr(key);
+    break;
+  case HA_KEYTYPE_ULONGLONG:
+    value= uint8korr(key);
+    break;
+  default:
+    DBUG_ASSERT(0);
+    value=0;                                    /* Error */
+    break;
+  }
+
+  /*
+    The following code works becasue if s_value < 0 then value is 0
+    and if s_value == 0 then value will contain either s_value or the
+    correct value.
+  */
+  set_if_bigger(info->s->auto_increment,
+                (s_value > 0) ? (ulonglong) s_value : value);
+}
diff --git a/storage/heap/hp_info.c b/storage/heap/hp_info.c
new file mode 100644
index 00000000..41596d86
--- /dev/null
+++ b/storage/heap/hp_info.c
@@ -0,0 +1,45 @@
+/* Copyright (c) 2000, 2011, Oracle and/or its affiliates. All rights reserved.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; version 2 of the License.
+
+   This program 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 General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1335  USA */
+
+/* Returns info about database status */
+
+#include "heapdef.h"
+
+
+uchar *heap_position(HP_INFO *info)
+{
+  return ((info->update & HA_STATE_AKTIV) ? info->current_ptr :
+	  (HEAP_PTR) 0);
+}
+
+
+/* Note that heap_info does NOT return information about the
+   current position anymore;  Use heap_position instead */
+
+int heap_info(reg1 HP_INFO *info,reg2 HEAPINFO *x, int flag )
+{
+  DBUG_ENTER("heap_info");
+  x->records         = info->s->records;
+  x->deleted         = info->s->deleted;
+  x->reclength       = info->s->reclength;
+  x->data_length     = info->s->data_length;
+  x->index_length    = info->s->index_length;
+  x->max_records     = info->s->max_records;
+  x->errkey          = info->errkey;
+  x->create_time     = info->s->create_time;
+  if (flag & HA_STATUS_AUTO)
+    x->auto_increment= info->s->auto_increment + 1;
+  DBUG_RETURN(0);
+} /* heap_info */
diff --git a/storage/heap/hp_open.c b/storage/heap/hp_open.c
new file mode 100644
index 00000000..272c4a3a
--- /dev/null
+++ b/storage/heap/hp_open.c
@@ -0,0 +1,152 @@
+/* Copyright (c) 2000, 2011, Oracle and/or its affiliates. All rights reserved.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; version 2 of the License.
+
+   This program 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 General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1335  USA */
+
+/* open a heap-database */
+
+#include "heapdef.h"
+#include "my_sys.h"
+
+/*
+  Open heap table based on HP_SHARE structure
+  
+  NOTE
+    This doesn't register the table in the open table list.
+*/
+
+HP_INFO *heap_open_from_share(HP_SHARE *share, int mode)
+{
+  HP_INFO *info;
+  DBUG_ENTER("heap_open_from_share");
+
+  if (!(info= (HP_INFO*) my_malloc(hp_key_memory_HP_INFO,
+                                   sizeof(HP_INFO) + 2 * share->max_key_length,
+                                   MYF(MY_ZEROFILL +
+                                       (share->internal ?
+                                        MY_THREAD_SPECIFIC : 0)))))
+  {
+    DBUG_RETURN(0);
+  }
+  share->open_count++; 
+  thr_lock_data_init(&share->lock,&info->lock,NULL);
+  info->s= share;
+  info->lastkey= (uchar*) (info + 1);
+  info->recbuf= (uchar*) (info->lastkey + share->max_key_length);
+  info->mode= mode;
+  info->current_record= (ulong) ~0L;		/* No current record */
+  info->lastinx= info->errkey= -1;
+#ifndef DBUG_OFF
+  info->opt_flag= READ_CHECK_USED;		/* Check when changing */
+#endif
+  DBUG_PRINT("exit",("heap: %p  reclength: %d  records_in_block: %lu",
+		     info, share->reclength,
+                     share->block.records_in_block));
+  DBUG_RETURN(info);
+}
+
+
+/*
+  Open heap table based on HP_SHARE structure and register it
+*/
+
+HP_INFO *heap_open_from_share_and_register(HP_SHARE *share, int mode)
+{
+  HP_INFO *info;
+  DBUG_ENTER("heap_open_from_share_and_register");
+
+  mysql_mutex_lock(&THR_LOCK_heap);
+  if ((info= heap_open_from_share(share, mode)))
+  {
+    info->open_list.data= (void*) info;
+    heap_open_list= list_add(heap_open_list,&info->open_list);
+    /* Unpin the share, it is now pinned by the file. */
+    share->open_count--;
+  }
+  mysql_mutex_unlock(&THR_LOCK_heap);
+  DBUG_RETURN(info);
+}
+
+
+/**
+  Dereference a HEAP share and free it if it's not referenced.
+  We don't check open_count for internal tables since they
+  are always thread-local, i.e. referenced by a single thread.
+*/
+void heap_release_share(HP_SHARE *share, my_bool internal_table)
+{
+  /* Couldn't open table; Remove the newly created table */
+  if (internal_table)
+    hp_free(share);
+  else
+  {
+    mysql_mutex_lock(&THR_LOCK_heap);
+    if (--share->open_count == 0)
+      hp_free(share);
+    mysql_mutex_unlock(&THR_LOCK_heap);
+  }
+}
+
+/*
+  Open heap table based on name
+
+  NOTE
+    This register the table in the open table list. so that it can be
+    found by future heap_open() calls.
+*/
+
+HP_INFO *heap_open(const char *name, int mode)
+{
+  HP_INFO *info;
+  HP_SHARE *share;
+  DBUG_ENTER("heap_open");
+
+  mysql_mutex_lock(&THR_LOCK_heap);
+  if (!(share= hp_find_named_heap(name)))
+  {
+    my_errno= ENOENT;
+    mysql_mutex_unlock(&THR_LOCK_heap);
+    DBUG_RETURN(0);
+  }
+  if ((info= heap_open_from_share(share, mode)))
+  {
+    info->open_list.data= (void*) info;
+    heap_open_list= list_add(heap_open_list,&info->open_list);
+  }
+  mysql_mutex_unlock(&THR_LOCK_heap);
+  DBUG_RETURN(info);
+}
+
+
+/* map name to a heap-nr. If name isn't found return 0 */
+
+HP_SHARE *hp_find_named_heap(const char *name)
+{
+  LIST *pos;
+  HP_SHARE *info;
+  DBUG_ENTER("heap_find");
+  DBUG_PRINT("enter",("name: %s",name));
+
+  for (pos= heap_share_list; pos; pos= pos->next)
+  {
+    info= (HP_SHARE*) pos->data;
+    if (!strcmp(name, info->name))
+    {
+      DBUG_PRINT("exit", ("Old heap_database: %p", info));
+      DBUG_RETURN(info);
+    }
+  }
+  DBUG_RETURN((HP_SHARE *) 0);
+}
+
+
diff --git a/storage/heap/hp_panic.c b/storage/heap/hp_panic.c
new file mode 100644
index 00000000..6872f04a
--- /dev/null
+++ b/storage/heap/hp_panic.c
@@ -0,0 +1,57 @@
+/* Copyright (c) 2000, 2002, 2005, 2006 MySQL AB, 2009 Sun Microsystems, Inc.
+   Use is subject to license terms.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; version 2 of the License.
+
+   This program 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 General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1335  USA */
+
+#include "heapdef.h"
+
+	/* if flag == HA_PANIC_CLOSE then all files are removed for more
+	   memory */
+
+int hp_panic(enum ha_panic_function flag)
+{
+  LIST *element,*next_open;
+  DBUG_ENTER("hp_panic");
+
+  mysql_mutex_lock(&THR_LOCK_heap);
+  for (element=heap_open_list ; element ; element=next_open)
+  {
+    HP_INFO *info=(HP_INFO*) element->data;
+    next_open=element->next;	/* Save if close */
+    switch (flag) {
+    case HA_PANIC_CLOSE:
+      hp_close(info);
+      break;
+    default:
+      break;
+    }
+  }
+  for (element=heap_share_list ; element ; element=next_open)
+  {
+    HP_SHARE *share=(HP_SHARE*) element->data;
+    next_open=element->next;	/* Save if close */
+    switch (flag) {
+    case HA_PANIC_CLOSE:
+    {
+      if (!share->open_count)
+	hp_free(share);
+      break;
+    }
+    default:
+      break;
+    }
+  }
+  mysql_mutex_unlock(&THR_LOCK_heap);
+  DBUG_RETURN(0);
+} /* hp_panic */
diff --git a/storage/heap/hp_rename.c b/storage/heap/hp_rename.c
new file mode 100644
index 00000000..7343644b
--- /dev/null
+++ b/storage/heap/hp_rename.c
@@ -0,0 +1,42 @@
+/* Copyright (c) 2000, 2010, Oracle and/or its affiliates. All rights reserved.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; version 2 of the License.
+
+   This program 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 General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1335  USA */
+
+/*
+  Rename a table
+*/
+
+#include "heapdef.h"
+
+int heap_rename(const char *old_name, const char *new_name)
+{
+  reg1 HP_SHARE *info;
+  char *name_buff;
+  DBUG_ENTER("heap_rename");
+
+  mysql_mutex_lock(&THR_LOCK_heap);
+  if ((info = hp_find_named_heap(old_name)))
+  {
+    if (!(name_buff=(char*) my_strdup(hp_key_memory_HP_SHARE,
+                                      new_name, MYF(MY_WME))))
+    {
+      mysql_mutex_unlock(&THR_LOCK_heap);
+      DBUG_RETURN(my_errno);
+    }
+    my_free(info->name);
+    info->name=name_buff;
+  }
+  mysql_mutex_unlock(&THR_LOCK_heap);
+  DBUG_RETURN(0);
+}
diff --git a/storage/heap/hp_rfirst.c b/storage/heap/hp_rfirst.c
new file mode 100644
index 00000000..60596a2c
--- /dev/null
+++ b/storage/heap/hp_rfirst.c
@@ -0,0 +1,68 @@
+/* Copyright (c) 2000-2002, 2004-2007 MySQL AB
+   Use is subject to license terms
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; version 2 of the License.
+
+   This program 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 General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1335  USA */
+
+#include "heapdef.h"
+
+/* Read first record with the current key */
+
+int heap_rfirst(HP_INFO *info, uchar *record, int inx)
+{
+  HP_SHARE *share = info->s;
+  HP_KEYDEF *keyinfo = share->keydef + inx;
+  
+  DBUG_ENTER("heap_rfirst");
+  info->lastinx= inx;
+  info->key_version= info->s->key_version;
+
+  if (keyinfo->algorithm == HA_KEY_ALG_BTREE)
+  {
+    uchar *pos;
+
+    if ((pos = tree_search_edge(&keyinfo->rb_tree, info->parents,
+                                &info->last_pos, offsetof(TREE_ELEMENT, left))))
+    {
+      memcpy(&pos, pos + (*keyinfo->get_key_length)(keyinfo, pos), 
+	     sizeof(uchar*));
+      info->current_ptr = pos;
+      memcpy(record, pos, (size_t)share->reclength);
+      /*
+        If we're performing index_first on a table that was taken from
+        table cache, info->lastkey_len is initialized to previous query.
+        Thus we set info->lastkey_len to proper value for subsequent
+        heap_rnext() calls.
+        This is needed for DELETE queries only, otherwise this variable is
+        not used.
+        Note that the same workaround may be needed for heap_rlast(), but
+        for now heap_rlast() is never used for DELETE queries.
+      */
+      info->lastkey_len= 0;
+      info->update = HA_STATE_AKTIV;
+    }
+    else
+    {
+      info->update= HA_STATE_NO_KEY;
+      my_errno = HA_ERR_END_OF_FILE;
+      DBUG_RETURN(my_errno);
+    }
+    DBUG_RETURN(0);
+  }
+  else
+  {
+    /* We can't scan a non existing key value with hash index */
+    my_errno= HA_ERR_WRONG_COMMAND;
+    DBUG_RETURN(my_errno);
+  }
+}
diff --git a/storage/heap/hp_rkey.c b/storage/heap/hp_rkey.c
new file mode 100644
index 00000000..2d9fae4c
--- /dev/null
+++ b/storage/heap/hp_rkey.c
@@ -0,0 +1,82 @@
+/* Copyright (c) 2000, 2002-2007 MySQL AB, 2009 Sun Microsystems, Inc.
+   Use is subject to license terms.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; version 2 of the License.
+
+   This program 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 General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1335  USA */
+
+#include "heapdef.h"
+
+int heap_rkey(HP_INFO *info, uchar *record, int inx, const uchar *key, 
+              key_part_map keypart_map, enum ha_rkey_function find_flag)
+{
+  uchar *pos;
+  HP_SHARE *share= info->s;
+  HP_KEYDEF *keyinfo= share->keydef + inx;
+  DBUG_ENTER("heap_rkey");
+  DBUG_PRINT("enter",("info: %p  inx: %d", info, inx));
+
+  if ((uint) inx >= share->keys)
+  {
+    DBUG_RETURN(my_errno= HA_ERR_WRONG_INDEX);
+  }
+  info->lastinx= inx;
+  info->current_record= (ulong) ~0L;		/* For heap_rrnd() */
+  info->key_version= info->s->key_version;
+
+  if (keyinfo->algorithm == HA_KEY_ALG_BTREE)
+  {
+    heap_rb_param custom_arg;
+
+    custom_arg.keyseg= info->s->keydef[inx].seg;
+    custom_arg.key_length= info->lastkey_len= 
+      hp_rb_pack_key(keyinfo, (uchar*) info->lastkey,
+		     (uchar*) key, keypart_map);
+    custom_arg.search_flag= SEARCH_FIND | SEARCH_SAME;
+    /* for next rkey() after deletion */
+    if (find_flag == HA_READ_AFTER_KEY)
+      info->last_find_flag= HA_READ_KEY_OR_NEXT;
+    else if (find_flag == HA_READ_BEFORE_KEY)
+      info->last_find_flag= HA_READ_KEY_OR_PREV;
+    else
+      info->last_find_flag= find_flag;
+    if (!(pos= tree_search_key(&keyinfo->rb_tree, info->lastkey, info->parents,
+			       &info->last_pos, find_flag, &custom_arg)))
+    {
+      info->update= HA_STATE_NO_KEY;
+      DBUG_RETURN(my_errno= HA_ERR_KEY_NOT_FOUND);
+    }
+    memcpy(&pos, pos + (*keyinfo->get_key_length)(keyinfo, pos), sizeof(uchar*));
+    info->current_ptr= pos;
+  }
+  else
+  {
+    if (!(pos= hp_search(info, share->keydef + inx, key, 0)))
+    {
+      info->update= HA_STATE_NO_KEY;
+      DBUG_RETURN(my_errno);
+    }
+    if ((keyinfo->flag & (HA_NOSAME | HA_NULL_PART_KEY)) != HA_NOSAME)
+      memcpy(info->lastkey, key, (size_t) keyinfo->length);
+  }
+  memcpy(record, pos, (size_t) share->reclength);
+  info->update= HA_STATE_AKTIV;
+  DBUG_RETURN(0);
+}
+
+
+	/* Quick find of record */
+
+uchar* heap_find(HP_INFO *info, int inx, const uchar *key)
+{
+  return hp_search(info, info->s->keydef + inx, key, 0);
+}
diff --git a/storage/heap/hp_rlast.c b/storage/heap/hp_rlast.c
new file mode 100644
index 00000000..ed9c3499
--- /dev/null
+++ b/storage/heap/hp_rlast.c
@@ -0,0 +1,56 @@
+/* Copyright (c) 2000-2002, 2005-2007 MySQL AB
+   Use is subject to license terms
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; version 2 of the License.
+
+   This program 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 General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1335  USA */
+
+#include "heapdef.h"
+
+	/* Read first record with the current key */
+
+
+int heap_rlast(HP_INFO *info, uchar *record, int inx)
+{
+  HP_SHARE *share=    info->s;
+  HP_KEYDEF *keyinfo= share->keydef + inx;
+
+  DBUG_ENTER("heap_rlast");
+  info->lastinx= inx;
+  info->key_version= info->s->key_version;
+  if (keyinfo->algorithm == HA_KEY_ALG_BTREE)
+  {
+    uchar *pos;
+
+    if ((pos = tree_search_edge(&keyinfo->rb_tree, info->parents,
+                                &info->last_pos, offsetof(TREE_ELEMENT, right))))
+    {
+      memcpy(&pos, pos + (*keyinfo->get_key_length)(keyinfo, pos), 
+	     sizeof(uchar*));
+      info->current_ptr = pos;
+      memcpy(record, pos, (size_t)share->reclength);
+      info->update = HA_STATE_AKTIV;
+    }
+    else
+    {
+      my_errno = HA_ERR_END_OF_FILE;
+      DBUG_RETURN(my_errno);
+    }
+    DBUG_RETURN(0);
+  }
+  else
+  {
+    /* We can't scan a non existing key value with hash index */
+    my_errno= HA_ERR_WRONG_COMMAND;
+    DBUG_RETURN(my_errno);
+  }
+}
diff --git a/storage/heap/hp_rnext.c b/storage/heap/hp_rnext.c
new file mode 100644
index 00000000..f227ce4d
--- /dev/null
+++ b/storage/heap/hp_rnext.c
@@ -0,0 +1,130 @@
+/* Copyright (c) 2000, 2002, 2005-2007 MySQL AB
+   Use is subject to license terms
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; version 2 of the License.
+
+   This program 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 General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1335  USA */
+
+#include "heapdef.h"
+
+/* Read next record with the same key */
+
+int heap_rnext(HP_INFO *info, uchar *record)
+{
+  uchar *pos;
+  HP_SHARE *share=info->s;
+  HP_KEYDEF *keyinfo;
+  DBUG_ENTER("heap_rnext");
+  
+  if (info->lastinx < 0)
+    DBUG_RETURN(my_errno=HA_ERR_WRONG_INDEX);
+
+  keyinfo = share->keydef + info->lastinx;
+  if (keyinfo->algorithm == HA_KEY_ALG_BTREE)
+  {
+    heap_rb_param custom_arg;
+
+    /* If no active record and last was not deleted */
+    if (!(info->update & (HA_STATE_AKTIV | HA_STATE_NO_KEY |
+                          HA_STATE_DELETED)))
+    {
+      if (info->update & HA_STATE_NEXT_FOUND)
+        pos= 0;                            /* Can't search after last row */
+      else
+      {
+        /* Last was 'prev' before first record; search after first record */
+        pos= tree_search_edge(&keyinfo->rb_tree, info->parents,
+                              &info->last_pos, offsetof(TREE_ELEMENT, left));
+      }
+    }
+    else if (info->last_pos)
+    {
+      /*
+        We enter this branch for non-DELETE queries after heap_rkey()
+        or heap_rfirst(). As last key position (info->last_pos) is available,
+        we only need to climb the tree using tree_search_next().
+      */
+      pos = tree_search_next(&keyinfo->rb_tree, &info->last_pos,
+                             offsetof(TREE_ELEMENT, left),
+                             offsetof(TREE_ELEMENT, right));
+    }
+    else if (!info->lastkey_len)
+    {
+      /*
+        We enter this branch only for DELETE queries after heap_rfirst(). E.g.
+        DELETE FROM t1 WHERE a<10. As last key position is not available
+        (last key is removed by heap_delete()), we must restart search as it
+        is done in heap_rfirst().
+
+        It should be safe to handle this situation without this branch. That is
+        branch below should find smallest element in a tree as lastkey_len is
+        zero. tree_search_edge() is a kind of optimisation here as it should be
+        faster than tree_search_key().
+      */
+      pos= tree_search_edge(&keyinfo->rb_tree, info->parents,
+                            &info->last_pos, offsetof(TREE_ELEMENT, left));
+    }
+    else
+    {
+      /*
+        We enter this branch only for DELETE queries after heap_rkey(). E.g.
+        DELETE FROM t1 WHERE a=10. As last key position is not available
+        (last key is removed by heap_delete()), we must restart search as it
+        is done in heap_rkey().
+      */
+      custom_arg.keyseg = keyinfo->seg;
+      custom_arg.key_length = info->lastkey_len;
+      custom_arg.search_flag = SEARCH_SAME | SEARCH_FIND;
+      info->last_find_flag= HA_READ_KEY_OR_NEXT;
+      pos = tree_search_key(&keyinfo->rb_tree, info->lastkey, info->parents, 
+                           &info->last_pos, info->last_find_flag, &custom_arg);
+    }
+    if (pos)
+    {
+      memcpy(&pos, pos + (*keyinfo->get_key_length)(keyinfo, pos), 
+	     sizeof(uchar*));
+      info->current_ptr = pos;
+    }
+    else
+    {
+      my_errno = HA_ERR_KEY_NOT_FOUND;
+    }
+  }
+  else
+  {
+    if (info->current_hash_ptr)
+      pos= hp_search_next(info, keyinfo, info->lastkey,
+			   info->current_hash_ptr);
+    else
+    {
+      if (!info->current_ptr && (info->update & HA_STATE_NEXT_FOUND))
+      {
+	pos=0;					/* Read next after last */
+	my_errno=HA_ERR_KEY_NOT_FOUND;
+      }
+      else if (!info->current_ptr)		/* Deleted or first call */
+	pos= hp_search(info, keyinfo, info->lastkey, 0);
+      else
+	pos= hp_search(info, keyinfo, info->lastkey, 1);
+    }
+  }
+  if (!pos)
+  {
+    info->update=HA_STATE_NEXT_FOUND;		/* For heap_rprev */
+    if (my_errno == HA_ERR_KEY_NOT_FOUND)
+      my_errno=HA_ERR_END_OF_FILE;
+    DBUG_RETURN(my_errno);
+  }
+  memcpy(record,pos,(size_t) share->reclength);
+  info->update=HA_STATE_AKTIV | HA_STATE_NEXT_FOUND;
+  DBUG_RETURN(0);
+}
diff --git a/storage/heap/hp_rprev.c b/storage/heap/hp_rprev.c
new file mode 100644
index 00000000..1d9420ba
--- /dev/null
+++ b/storage/heap/hp_rprev.c
@@ -0,0 +1,98 @@
+/* Copyright (c) 2000-2002, 2005-2007 MySQL AB
+   Use is subject to license terms
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; version 2 of the License.
+
+   This program 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 General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1335  USA */
+
+#include "heapdef.h"
+
+	/* Read prev record for key */
+
+
+int heap_rprev(HP_INFO *info, uchar *record)
+{
+  uchar *pos;
+  HP_SHARE *share=info->s;
+  HP_KEYDEF *keyinfo;
+  DBUG_ENTER("heap_rprev");
+
+  if (info->lastinx < 0)
+    DBUG_RETURN(my_errno=HA_ERR_WRONG_INDEX);
+  keyinfo = share->keydef + info->lastinx;
+  if (keyinfo->algorithm == HA_KEY_ALG_BTREE)
+  {
+    heap_rb_param custom_arg;
+
+    /* If no active record and last was not deleted */
+    if (!(info->update & (HA_STATE_AKTIV | HA_STATE_NO_KEY |
+                          HA_STATE_DELETED)))
+    {
+      if (info->update & HA_STATE_PREV_FOUND)
+        pos= 0;                            /* Can't search before first row */
+      else
+      {
+        /* Last was 'next' after last record; search after last record */
+        pos= tree_search_edge(&keyinfo->rb_tree, info->parents,
+                              &info->last_pos, offsetof(TREE_ELEMENT, right));
+      }
+    }
+    else if (info->last_pos)
+      pos = tree_search_next(&keyinfo->rb_tree, &info->last_pos,
+                             offsetof(TREE_ELEMENT, right),
+                             offsetof(TREE_ELEMENT, left));
+    else
+    {
+      custom_arg.keyseg = keyinfo->seg;
+      custom_arg.key_length = keyinfo->length;
+      custom_arg.search_flag = SEARCH_SAME;
+      info->last_find_flag= HA_READ_KEY_OR_PREV;
+      pos = tree_search_key(&keyinfo->rb_tree, info->lastkey, info->parents, 
+                           &info->last_pos, info->last_find_flag, &custom_arg);
+    }
+    if (pos)
+    {
+      memcpy(&pos, pos + (*keyinfo->get_key_length)(keyinfo, pos),
+	     sizeof(uchar*));
+      info->current_ptr = pos;
+    }
+    else
+    {
+      my_errno = HA_ERR_KEY_NOT_FOUND;
+    }
+  }
+  else
+  {
+    if (info->current_ptr || (info->update & HA_STATE_NEXT_FOUND))
+    {
+      if ((info->update & HA_STATE_DELETED))
+        pos= hp_search(info, share->keydef + info->lastinx, info->lastkey, 3);
+      else
+        pos= hp_search(info, share->keydef + info->lastinx, info->lastkey, 2);
+    }
+    else
+    {
+      pos=0;					/* Read next after last */
+      my_errno=HA_ERR_KEY_NOT_FOUND;
+    }
+  }
+  if (!pos)
+  {
+    info->update=HA_STATE_PREV_FOUND;		/* For heap_rprev */
+    if (my_errno == HA_ERR_KEY_NOT_FOUND)
+      my_errno=HA_ERR_END_OF_FILE;
+    DBUG_RETURN(my_errno);
+  }
+  memcpy(record,pos,(size_t) share->reclength);
+  info->update=HA_STATE_AKTIV | HA_STATE_PREV_FOUND;
+  DBUG_RETURN(0);
+}
diff --git a/storage/heap/hp_rrnd.c b/storage/heap/hp_rrnd.c
new file mode 100644
index 00000000..3947946c
--- /dev/null
+++ b/storage/heap/hp_rrnd.c
@@ -0,0 +1,50 @@
+/* Copyright (c) 2000-2002, 2004-2007 MySQL AB
+   Use is subject to license terms
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; version 2 of the License.
+
+   This program 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 General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1335  USA */
+
+/* Read a record from a random position */
+
+#include "heapdef.h"
+
+/*
+	   Returns one of following values:
+	   0 = Ok.
+	   HA_ERR_RECORD_DELETED = Record is deleted.
+	   HA_ERR_END_OF_FILE = EOF.
+*/
+
+int heap_rrnd(register HP_INFO *info, uchar *record, uchar *pos)
+{
+  HP_SHARE *share=info->s;
+  DBUG_ENTER("heap_rrnd");
+  DBUG_PRINT("enter",("info: %p  pos: %p", info, pos));
+
+  info->lastinx= -1;
+  if (!(info->current_ptr= pos))
+  {
+    info->update= 0;
+    DBUG_RETURN(my_errno= HA_ERR_END_OF_FILE);
+  }
+  if (!info->current_ptr[share->visible])
+  {
+    info->update= HA_STATE_PREV_FOUND | HA_STATE_NEXT_FOUND;
+    DBUG_RETURN(my_errno=HA_ERR_RECORD_DELETED);
+  }
+  info->update=HA_STATE_PREV_FOUND | HA_STATE_NEXT_FOUND | HA_STATE_AKTIV;
+  memcpy(record,info->current_ptr,(size_t) share->reclength);
+  DBUG_PRINT("exit", ("found record at %p", info->current_ptr));
+  info->current_hash_ptr=0;			/* Can't use rnext */
+  DBUG_RETURN(0);
+} /* heap_rrnd */
diff --git a/storage/heap/hp_rsame.c b/storage/heap/hp_rsame.c
new file mode 100644
index 00000000..8bba4cd2
--- /dev/null
+++ b/storage/heap/hp_rsame.c
@@ -0,0 +1,57 @@
+/* Copyright (c) 2000-2002, 2005-2007 MySQL AB
+   Use is subject to license terms
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; version 2 of the License.
+
+   This program 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 General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1335  USA */
+
+/* re-read current record */
+
+#include "heapdef.h"
+
+	/* If inx != -1 the new record is read according to index
+	   (for next/prev). Record must in this case point to last record
+	   Returncodes:
+	   0 = Ok.
+	   HA_ERR_RECORD_DELETED = Record was removed
+	   HA_ERR_KEY_NOT_FOUND = Record not found with key
+	*/
+
+int heap_rsame(register HP_INFO *info, uchar *record, int inx)
+{
+  HP_SHARE *share=info->s;
+  DBUG_ENTER("heap_rsame");
+
+  test_active(info);
+  if (info->current_ptr[share->visible])
+  {
+    if (inx < -1 || inx >= (int) share->keys)
+    {
+      DBUG_RETURN(my_errno=HA_ERR_WRONG_INDEX);
+    }
+    else if (inx != -1)
+    {
+      info->lastinx=inx;
+      hp_make_key(share->keydef + inx, info->lastkey, record);
+      if (!hp_search(info, share->keydef + inx, info->lastkey, 3))
+      {
+	info->update= 0;
+	DBUG_RETURN(my_errno);
+      }
+    }
+    memcpy(record,info->current_ptr,(size_t) share->reclength);
+    DBUG_RETURN(0);
+  }
+  info->update=0;
+
+  DBUG_RETURN(my_errno=HA_ERR_RECORD_DELETED);
+}
diff --git a/storage/heap/hp_scan.c b/storage/heap/hp_scan.c
new file mode 100644
index 00000000..f07efe6c
--- /dev/null
+++ b/storage/heap/hp_scan.c
@@ -0,0 +1,77 @@
+/* Copyright (c) 2000-2002, 2005-2007 MySQL AB
+   Use is subject to license terms
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; version 2 of the License.
+
+   This program 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 General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1335  USA */
+
+/* Scan through all rows */
+
+#include "heapdef.h"
+
+/*
+	   Returns one of following values:
+	   0 = Ok.
+	   HA_ERR_RECORD_DELETED = Record is deleted.
+	   HA_ERR_END_OF_FILE = EOF.
+*/
+
+int heap_scan_init(register HP_INFO *info)
+{
+  DBUG_ENTER("heap_scan_init");
+  info->lastinx= -1;
+  info->current_record= (ulong) ~0L;		/* No current record */
+  info->update=0;
+  info->next_block=0;
+  info->key_version= info->s->key_version;
+  info->file_version= info->s->file_version;
+  DBUG_RETURN(0);
+}
+
+int heap_scan(register HP_INFO *info, uchar *record)
+{
+  HP_SHARE *share=info->s;
+  ulong pos;
+  DBUG_ENTER("heap_scan");
+
+  pos= ++info->current_record;
+  if (pos < info->next_block)
+  {
+    info->current_ptr+=share->block.recbuffer;
+  }
+  else
+  {
+    /* increase next_block to the next records_in_block boundary */
+    ulong rem= info->next_block % share->block.records_in_block;
+    info->next_block+=share->block.records_in_block - rem;
+    if (info->next_block >= share->records+share->deleted)
+    {
+      info->next_block= share->records+share->deleted;
+      if (pos >= info->next_block)
+      {
+	info->update= 0;
+	DBUG_RETURN(my_errno= HA_ERR_END_OF_FILE);
+      }
+    }
+    hp_find_record(info, pos);
+  }
+  if (!info->current_ptr[share->visible])
+  {
+    DBUG_PRINT("warning",("Found deleted record"));
+    info->update= HA_STATE_PREV_FOUND | HA_STATE_NEXT_FOUND;
+    DBUG_RETURN(my_errno=HA_ERR_RECORD_DELETED);
+  }
+  info->update= HA_STATE_PREV_FOUND | HA_STATE_NEXT_FOUND | HA_STATE_AKTIV;
+  memcpy(record,info->current_ptr,(size_t) share->reclength);
+  info->current_hash_ptr=0;			/* Can't use read_next */
+  DBUG_RETURN(0);
+} /* heap_scan */
diff --git a/storage/heap/hp_static.c b/storage/heap/hp_static.c
new file mode 100644
index 00000000..9a4410ee
--- /dev/null
+++ b/storage/heap/hp_static.c
@@ -0,0 +1,55 @@
+/* Copyright (c) 2000, 2011, Oracle and/or its affiliates. All rights reserved.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; version 2 of the License.
+
+   This program 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 General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1335  USA */
+
+/*
+  Static variables for heap library. All definied here for easy making of
+  a shared library
+*/
+
+#ifndef MY_GLOBAL_INCLUDED
+#include "heapdef.h"
+#endif
+
+LIST *heap_open_list=0,*heap_share_list=0;
+
+PSI_memory_key hp_key_memory_HP_SHARE;
+PSI_memory_key hp_key_memory_HP_INFO;
+PSI_memory_key hp_key_memory_HP_PTRS;
+PSI_memory_key hp_key_memory_HP_KEYDEF;
+
+#ifdef HAVE_PSI_INTERFACE
+
+static PSI_memory_info all_heap_memory[]=
+{
+  { & hp_key_memory_HP_SHARE, "HP_SHARE", 0},
+  { & hp_key_memory_HP_INFO, "HP_INFO", 0},
+  { & hp_key_memory_HP_PTRS, "HP_PTRS", 0},
+  { & hp_key_memory_HP_KEYDEF, "HP_KEYDEF", 0}
+};
+
+void init_heap_psi_keys()
+{
+  const char* category= "memory";
+  int count;
+
+  if (PSI_server == NULL)
+    return;
+
+  count= array_elements(all_heap_memory);
+  mysql_memory_register(category, all_heap_memory, count);
+}
+#endif /* HAVE_PSI_INTERFACE */
+
+
diff --git a/storage/heap/hp_test1.c b/storage/heap/hp_test1.c
new file mode 100644
index 00000000..03054843
--- /dev/null
+++ b/storage/heap/hp_test1.c
@@ -0,0 +1,172 @@
+/* Copyright (c) 2000, 2010, Oracle and/or its affiliates. All rights reserved.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; version 2 of the License.
+
+   This program 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 General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1335  USA */
+
+/* Test av heap-database */
+/* Programmet skapar en heap-databas. Till denna skrivs ett antal poster.
+   Databasen st{ngs. D{refter |ppnas den p} nytt och en del av posterna
+   raderas.
+*/
+
+#include <my_global.h>
+#include <my_sys.h>
+#include <m_string.h>
+#include "heap.h"
+
+static int get_options(int argc, char *argv[]);
+
+static int flag=0,verbose=0,remove_ant=0,flags[50];
+
+int main(int argc, char **argv)
+{
+  int i,j,error;
+  HP_INFO *file;
+  uchar record[128],key[32];
+  const char *filename;
+  HP_KEYDEF keyinfo[10];
+  HA_KEYSEG keyseg[4];
+  HP_CREATE_INFO hp_create_info;
+  HP_SHARE *tmp_share;
+  my_bool unused;
+  MY_INIT(argv[0]);
+
+  filename= "test1";
+  get_options(argc,argv);
+
+  bzero(&hp_create_info, sizeof(hp_create_info));
+  hp_create_info.max_table_size= 1024L*1024L;
+  hp_create_info.keys= 1;
+  hp_create_info.keydef= keyinfo;
+  hp_create_info.reclength= 30;
+  hp_create_info.max_records= (ulong) flag*100000L;
+  hp_create_info.min_records= 10UL;
+
+  keyinfo[0].keysegs=1;
+  keyinfo[0].seg=keyseg;
+  keyinfo[0].algorithm= HA_KEY_ALG_HASH;
+  keyinfo[0].seg[0].type=HA_KEYTYPE_BINARY;
+  keyinfo[0].seg[0].start=1;
+  keyinfo[0].seg[0].length=6;
+  keyinfo[0].seg[0].charset= &my_charset_latin1;
+  keyinfo[0].seg[0].null_bit= 0;
+  keyinfo[0].flag = HA_NOSAME;
+
+  bzero((uchar*) flags,sizeof(flags));
+
+  printf("- Creating heap-file\n");
+  if (heap_create(filename, &hp_create_info, &tmp_share, &unused) ||
+      !(file= heap_open(filename, 2)))
+    goto err;
+  printf("- Writing records:s\n");
+  strmov((char*) record,"          ..... key           ");
+
+  for (i=49 ; i>=1 ; i-=2 )
+  {
+    j=i%25 +1;
+    sprintf((char*) key,"%6d",j);
+    bmove(record+1,key,6);
+    error=heap_write(file,record);
+    if (heap_check_heap(file,0))
+    {
+      puts("Heap keys crashed");
+      goto err;
+    }
+    flags[j]=1;
+    if (verbose || error) printf("J= %2d  heap_write: %d  my_errno: %d\n",
+       j,error,my_errno);
+  }
+  if (heap_close(file))
+    goto err;
+  printf("- Reopening file\n");
+  if (!(file=heap_open(filename, 2)))
+    goto err;
+
+  printf("- Removing records\n");
+  for (i=1 ; i<=10 ; i++)
+  {
+    if (i == remove_ant) { (void) heap_close(file); return (0) ; }
+    sprintf((char*) key,"%6d",(j=(int) ((rand() & 32767)/32767.*25)));
+    if ((error = heap_rkey(file,record,0,key,6,HA_READ_KEY_EXACT)))
+    {
+      if (verbose || (flags[j] == 1 ||
+		      (error && my_errno != HA_ERR_KEY_NOT_FOUND)))
+	printf("key: %s  rkey:   %3d  my_errno: %3d\n",(char*) key,error,my_errno);
+    }
+    else
+    {
+      error=heap_delete(file,record);
+      if (error || verbose)
+	printf("key: %s  delete: %d  my_errno: %d\n",(char*) key,error,my_errno);
+      flags[j]=0;
+    }
+    if (heap_check_heap(file,0))
+    {
+      puts("Heap keys crashed");
+      goto err;
+    }
+  }
+
+  printf("- Reading records with key\n");
+  for (i=1 ; i<=25 ; i++)
+  {
+    sprintf((char*) key,"%6d",i);
+    bmove(record+1,key,6);
+    my_errno=0;
+    error=heap_rkey(file,record,0,key,6,HA_READ_KEY_EXACT);
+    if (verbose ||
+	(error == 0 && flags[i] != 1) ||
+	(error && (flags[i] != 0 || my_errno != HA_ERR_KEY_NOT_FOUND)))
+    {
+      printf("key: %s  rkey: %3d  my_errno: %3d  record: %s\n",
+             (char*) key,error,my_errno,record+1);
+    }
+  }
+
+  if (heap_close(file) || hp_panic(HA_PANIC_CLOSE))
+    goto err;
+  my_end(MY_GIVE_INFO);
+  return(0);
+err:
+  printf("got error: %d when using heap-database\n",my_errno);
+  return(1);
+} /* main */
+
+
+/* Read options */
+
+static int get_options(int argc, char **argv)
+{
+  char *pos;
+
+  while (--argc >0 && *(pos = *(++argv)) == '-' ) {
+    switch(*++pos) {
+    case 'B':				/* Big file */
+      flag=1;
+      break;
+    case 'v':				/* verbose */
+      verbose=1;
+      break;
+    case 'm':
+      remove_ant=atoi(++pos);
+      break;
+    case 'V':
+      printf("hp_test1    Ver 3.0 \n");
+      exit(0);
+    case '#':
+      DBUG_PUSH (++pos);
+      break;
+    }
+  }
+  return 0;
+} /* get options */
diff --git a/storage/heap/hp_test2.c b/storage/heap/hp_test2.c
new file mode 100644
index 00000000..27d15077
--- /dev/null
+++ b/storage/heap/hp_test2.c
@@ -0,0 +1,643 @@
+/* Copyright (c) 2000, 2011, Oracle and/or its affiliates.
+   Copyright (c) 2010, 2011, Monty Program Ab
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; version 2 of the License.
+
+   This program 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 General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1335  USA */
+
+/* Test av isam-databas: stor test */
+
+#include "heapdef.h"		/* Because of hp_find_block */
+#include <signal.h>
+
+#define MAX_RECORDS 100000
+#define MAX_KEYS 4
+
+static int get_options(int argc, char *argv[]);
+static int rnd(int max_value);
+static sig_handler endprog(int sig_number);
+
+static uint flag=0,verbose=0,testflag=0,recant=10000,silent=0;
+static uint keys=MAX_KEYS;
+static uint16 key1[1001];
+static my_bool key3[MAX_RECORDS];
+static int reclength=39;
+
+
+static int calc_check(uchar *buf,uint length);
+static void make_record(uchar *record, uint n1, uint n2, uint n3,
+			const char *mark, uint count);
+
+/* Main program */
+
+int main(int argc, char *argv[])
+{
+  register uint i,j;
+  uint ant,n1,n2,n3;
+  uint write_count,update,opt_delete,check2,dupp_keys,found_key;
+  int error;
+  ulong pos;
+  unsigned long key_check;
+  uchar record[128],record2[128],record3[128],key[10];
+  const char *filename,*filename2;
+  HP_INFO *file,*file2;
+  HP_SHARE *tmp_share;
+  HP_KEYDEF keyinfo[MAX_KEYS];
+  HA_KEYSEG keyseg[MAX_KEYS*5];
+  HEAP_PTR UNINIT_VAR(position);
+  HP_CREATE_INFO hp_create_info;
+  CHARSET_INFO *cs= &my_charset_latin1;
+  my_bool unused;
+  MY_INIT(argv[0]);		/* init my_sys library & pthreads */
+
+  filename= "test2";
+  filename2= "test2_2";
+  file=file2=0;
+  get_options(argc,argv);
+
+  bzero(&hp_create_info, sizeof(hp_create_info));
+  hp_create_info.max_table_size= 2*1024L*1024L;
+  hp_create_info.keys= keys;
+  hp_create_info.keydef= keyinfo;
+  hp_create_info.reclength= reclength;
+  hp_create_info.max_records= (ulong) flag*100000L;
+  hp_create_info.min_records= (ulong) recant/2;
+
+  write_count=update=opt_delete=0;
+  key_check=0;
+
+  keyinfo[0].seg=keyseg;
+  keyinfo[0].keysegs=1;
+  keyinfo[0].flag= 0;
+  keyinfo[0].algorithm= HA_KEY_ALG_HASH;
+  keyinfo[0].seg[0].type=HA_KEYTYPE_BINARY;
+  keyinfo[0].seg[0].start=0;
+  keyinfo[0].seg[0].length=6;
+  keyinfo[0].seg[0].null_bit=0;
+  keyinfo[0].seg[0].charset=cs;
+  keyinfo[1].seg=keyseg+1;
+  keyinfo[1].keysegs=2;
+  keyinfo[1].flag=0;
+  keyinfo[1].algorithm= HA_KEY_ALG_HASH;
+  keyinfo[1].seg[0].type=HA_KEYTYPE_BINARY;
+  keyinfo[1].seg[0].start=7;
+  keyinfo[1].seg[0].length=6;
+  keyinfo[1].seg[0].null_bit=0;
+  keyinfo[1].seg[0].charset=cs;
+  keyinfo[1].seg[1].type=HA_KEYTYPE_TEXT;
+  keyinfo[1].seg[1].start=0;			/* key in two parts */
+  keyinfo[1].seg[1].length=6;
+  keyinfo[1].seg[1].null_bit=0;
+  keyinfo[1].seg[1].charset=cs;
+  keyinfo[2].seg=keyseg+3;
+  keyinfo[2].keysegs=1;
+  keyinfo[2].flag=HA_NOSAME;
+  keyinfo[2].algorithm= HA_KEY_ALG_HASH;
+  keyinfo[2].seg[0].type=HA_KEYTYPE_BINARY;
+  keyinfo[2].seg[0].start=12;
+  keyinfo[2].seg[0].length=8;
+  keyinfo[2].seg[0].null_bit=0;
+  keyinfo[2].seg[0].charset=cs;
+  keyinfo[3].seg=keyseg+4;
+  keyinfo[3].keysegs=1;
+  keyinfo[3].flag=HA_NOSAME;
+  keyinfo[3].algorithm= HA_KEY_ALG_HASH;
+  keyinfo[3].seg[0].type=HA_KEYTYPE_BINARY;
+  keyinfo[3].seg[0].start=37;
+  keyinfo[3].seg[0].length=1;
+  keyinfo[3].seg[0].null_bit=1;
+  keyinfo[3].seg[0].null_pos=38;
+  keyinfo[3].seg[0].charset=cs;
+
+  bzero((char*) key1,sizeof(key1));
+  bzero((char*) key3,sizeof(key3));
+
+  printf("- Creating heap-file\n");
+  if (heap_create(filename, &hp_create_info, &tmp_share, &unused) ||
+      !(file= heap_open(filename, 2)))
+    goto err;
+  signal(SIGINT,endprog);
+
+  printf("- Writing records:s\n");
+  strmov((char*) record,"          ..... key");
+
+  for (i=0 ; i < recant ; i++)
+  {
+    n1=rnd(1000); n2=rnd(100); n3=rnd(MY_MIN(recant*5,MAX_RECORDS));
+    make_record(record,n1,n2,n3,"Pos",write_count);
+
+    if (heap_write(file,record))
+    {
+      if (my_errno != HA_ERR_FOUND_DUPP_KEY || key3[n3] == 0)
+      {
+	printf("Error: %d in write at record: %d\n",my_errno,i);
+	goto err;
+      }
+      if (verbose) printf("   Double key: %d\n",n3);
+    }
+    else
+    {
+      if (key3[n3] == 1)
+      {
+	printf("Error: Didn't get error when writing second key: '%8d'\n",n3);
+	goto err;
+      }
+      write_count++; key1[n1]++; key3[n3]=1;
+      key_check+=n1;
+    }
+    if (testflag == 1 && heap_check_heap(file,0))
+    {
+      puts("Heap keys crashed");
+      goto err;
+    }
+  }
+  if (testflag == 1)
+    goto end;
+  if (heap_check_heap(file,0))
+  {
+    puts("Heap keys crashed");
+    goto err;
+  }
+
+  printf("- Delete\n");
+  for (i=0 ; i < write_count/10 ; i++)
+  {
+    for (j=rnd(1000)+1 ; j>0 && key1[j] == 0 ; j--) ;
+    if (j != 0)
+    {
+      sprintf((char*) key,"%6d",j);
+      if (heap_rkey(file,record,0,key,6, HA_READ_KEY_EXACT))
+      {
+	printf("can't find key1: \"%s\"\n",(char*) key);
+	goto err;
+      }
+      if (heap_delete(file,record))
+      {
+	printf("error: %d; can't delete record: \"%s\"\n", my_errno,(char*) record);
+	goto err;
+      }
+      opt_delete++;
+      key1[atoi((char*) record+keyinfo[0].seg[0].start)]--;
+      key3[atoi((char*) record+keyinfo[2].seg[0].start)]=0;
+      key_check-=atoi((char*) record);
+      if (testflag == 2 && heap_check_heap(file,0))
+      {
+	puts("Heap keys crashed");
+	goto err;
+      }
+    }
+    else
+      puts("Warning: Skipping delete test because no dupplicate keys");
+  }
+  if (testflag==2) goto end;
+  if (heap_check_heap(file,0))
+  {
+    puts("Heap keys crashed");
+    goto err;
+  }
+
+  printf("- Update\n");
+  for (i=0 ; i < write_count/10 ; i++)
+  {
+    n1=rnd(1000); n2=rnd(100); n3=rnd(MY_MIN(recant*2,MAX_RECORDS));
+    make_record(record2, n1, n2, n3, "XXX", update);
+    if (rnd(2) == 1)
+    {
+      if (heap_scan_init(file))
+	goto err;
+      j=rnd(write_count-opt_delete);
+      while ((error=heap_scan(file,record) == HA_ERR_RECORD_DELETED) ||
+	     (!error && j))
+      {
+	if (!error)
+	  j--;
+      }
+      if (error)
+	goto err;
+    }
+    else
+    {
+      for (j=rnd(1000)+1 ; j>0 && key1[j] == 0 ; j--) ;
+      if (!key1[j])
+	continue;
+      sprintf((char*) key,"%6d",j);
+      if (heap_rkey(file,record,0,key,6, HA_READ_KEY_EXACT))
+      {
+	printf("can't find key1: \"%s\"\n",(char*) key);
+	goto err;
+      }
+    }
+    if (heap_update(file,record,record2))
+    {
+      if (my_errno != HA_ERR_FOUND_DUPP_KEY || key3[n3] == 0)
+      {
+	printf("error: %d; can't update:\nFrom: \"%s\"\nTo:   \"%s\"\n",
+	       my_errno,(char*) record, (char*) record2);
+	goto err;
+      }
+      if (verbose)
+	printf("Double key when tried to update:\nFrom: \"%s\"\nTo:   \"%s\"\n",
+               (char*) record, (char*) record2);
+    }
+    else
+    {
+      key1[atoi((char*) record+keyinfo[0].seg[0].start)]--;
+      key3[atoi((char*) record+keyinfo[2].seg[0].start)]=0;
+      key1[n1]++; key3[n3]=1;
+      update++;
+      key_check=key_check-atoi((char*) record)+n1;
+    }
+    if (testflag == 3 && heap_check_heap(file,0))
+    {
+      puts("Heap keys crashed");
+      goto err;
+    }
+  }
+  if (testflag == 3) goto end;
+  if (heap_check_heap(file,0))
+  {
+    puts("Heap keys crashed");
+    goto err;
+  }
+
+  for (i=999, dupp_keys=found_key=0 ; i>0 ; i--)
+  {
+    if (key1[i] > dupp_keys) { dupp_keys=key1[i]; found_key=i; }
+    sprintf((char*) key,"%6d",found_key);
+  }
+
+  if (dupp_keys > 3)
+  {
+    if (!silent)
+      printf("- Read first key - next - delete - next -> last\n");
+    DBUG_PRINT("progpos",("first - next - delete - next -> last"));
+
+    if (heap_rkey(file,record,0,key,6, HA_READ_KEY_EXACT))
+      goto err;
+    if (heap_rnext(file,record3)) goto err;
+    if (heap_delete(file,record3)) goto err;
+    key_check-=atoi((char*) record3);
+    key1[atoi((char*) record+keyinfo[0].seg[0].start)]--;
+    key3[atoi((char*) record+keyinfo[2].seg[0].start)]=0;
+    opt_delete++;
+    ant=2;
+    while ((error=heap_rnext(file,record3)) == 0 ||
+	   error == HA_ERR_RECORD_DELETED)
+      if (! error)
+	ant++;
+    if (ant != dupp_keys)
+    {
+      printf("next: I can only find: %d records of %d\n",
+	     ant,dupp_keys);
+      goto end;
+    }
+    dupp_keys--;
+    if (heap_check_heap(file,0))
+    {
+      puts("Heap keys crashed");
+      goto err;
+    }
+
+    if (!silent)
+      printf("- Read last key - delete - prev - prev - opt_delete - prev -> first\n");
+
+    if (heap_rprev(file,record))
+      goto err;
+    if (heap_delete(file,record3)) goto err;
+    key_check-=atoi((char*) record3);
+    key1[atoi((char*) record+keyinfo[0].seg[0].start)]--;
+    key3[atoi((char*) record+keyinfo[2].seg[0].start)]=0;
+    opt_delete++;
+    if (heap_rprev(file,record3) || heap_rprev(file,record3))
+      goto err;
+    if (heap_delete(file,record3)) goto err;
+    key_check-=atoi((char*) record3);
+    key1[atoi((char*) record+keyinfo[0].seg[0].start)]--;
+    key3[atoi((char*) record+keyinfo[2].seg[0].start)]=0;
+    opt_delete++;
+    ant=3;
+    while ((error=heap_rprev(file,record3)) == 0 ||
+	   error == HA_ERR_RECORD_DELETED)
+    {
+      if (! error)
+	ant++;
+    }
+    if (ant != dupp_keys)
+    {
+      printf("next: I can only find: %d records of %d\n",
+	     ant,dupp_keys);
+      goto end;
+    }
+    dupp_keys-=2;
+    if (heap_check_heap(file,0))
+    {
+      puts("Heap keys crashed");
+      goto err;
+    }
+  }
+  else
+    puts("Warning: Not enough duplicated keys:  Skipping delete key check");
+
+  if (!silent)
+    printf("- Read (first) - next - delete - next -> last\n");
+  DBUG_PRINT("progpos",("first - next - delete - next -> last"));
+
+  if (heap_scan_init(file))
+    goto err;
+  while ((error=heap_scan(file,record3) == HA_ERR_RECORD_DELETED)) ;
+  if (error)
+    goto err;
+  if (heap_delete(file,record3)) goto err;
+  key_check-=atoi((char*) record3);
+  opt_delete++;
+  key1[atoi((char*) record+keyinfo[0].seg[0].start)]--;
+  key3[atoi((char*) record+keyinfo[2].seg[0].start)]=0;
+  ant=0;
+  while ((error=heap_scan(file,record3)) == 0 ||
+	 error == HA_ERR_RECORD_DELETED)
+    if (! error)
+      ant++;
+  if (ant != write_count-opt_delete)
+  {
+    printf("next: Found: %d records of %d\n",ant,write_count-opt_delete);
+    goto end;
+  }
+  if (heap_check_heap(file,0))
+  {
+    puts("Heap keys crashed");
+    goto err;
+  }
+
+  puts("- Test if: Read rrnd - same - rkey - same");
+  DBUG_PRINT("progpos",("Read rrnd - same"));
+  pos=rnd(write_count-opt_delete-5)+5;
+  heap_scan_init(file);
+  i=5;
+  while ((error=heap_scan(file,record)) == HA_ERR_RECORD_DELETED ||
+	 (error == 0 && pos))
+  {
+    if (!error)
+      pos--;
+    if (i-- == 0)
+    {
+      bmove(record3,record,reclength);
+      position=heap_position(file);
+    }
+  }
+  if (error)
+    goto err;
+  bmove(record2,record,reclength);
+  if (heap_rsame(file,record,-1) || heap_rsame(file,record2,2))
+    goto err;
+  if (memcmp(record2,record,reclength))
+  {
+    puts("heap_rsame didn't find right record");
+    goto end;
+  }
+
+  puts("- Test of read through position");
+  if (heap_rrnd(file,record,position))
+    goto err;
+  if (memcmp(record3,record,reclength))
+  {
+    puts("heap_frnd didn't find right record");
+    goto end;
+  }
+
+  printf("- heap_info\n");
+  {
+    HEAPINFO info;
+    heap_info(file,&info,0);
+    /* We have to test with opt_delete +1 as this may be the case if the last
+       inserted row was a duplicate key */
+    if (info.records != write_count-opt_delete ||
+	(info.deleted != opt_delete && info.deleted != opt_delete+1))
+    {
+      puts("Wrong info from heap_info");
+      printf("Got: records: %ld(%d)  deleted: %ld(%d)\n",
+	     info.records,write_count-opt_delete,info.deleted,opt_delete);
+    }
+  }
+
+  printf("- Read through all records with scan\n");
+  if (heap_reset(file) || heap_extra(file,HA_EXTRA_CACHE))
+  {
+    puts("got error from heap_extra");
+    goto end;
+  }
+  ant=check2=0;
+  heap_scan_init(file);
+  while ((error=heap_scan(file,record)) != HA_ERR_END_OF_FILE &&
+	 ant < write_count + 10)
+  {
+    if (!error)
+    {
+      ant++;
+      check2+=calc_check(record,reclength);
+    }
+  }
+  if (ant != write_count-opt_delete)
+  {
+    printf("scan: I can only find: %d records of %d\n", ant,
+	   write_count-opt_delete);
+    goto end;
+  }
+
+  if (heap_extra(file,HA_EXTRA_NO_CACHE))
+  {
+    puts("got error from heap_extra(HA_EXTRA_NO_CACHE)");
+    goto end;
+  }
+
+  for (i=999, dupp_keys=found_key=0 ; i>0 ; i--)
+  {
+    if (key1[i] > dupp_keys) { dupp_keys=key1[i]; found_key=i; }
+    sprintf((char*) key,"%6d",found_key);
+  }
+  printf("- Read through all keys with first-next-last-prev\n");
+  ant=0;
+  for (error=heap_rkey(file,record,0,key,6, HA_READ_KEY_EXACT);
+      ! error ;
+       error=heap_rnext(file,record))
+    ant++;
+  if (ant != dupp_keys)
+  {
+    printf("first-next: I can only find: %d records of %d\n", ant,
+	   dupp_keys);
+    goto end;
+  }
+
+  ant=0;
+  for (error=heap_rprev(file,record) ;
+      ! error ;
+      error=heap_rprev(file,record))
+  {
+    ant++;
+    check2+=calc_check(record,reclength);
+  }
+  if (ant != dupp_keys)
+  {
+    printf("last-prev: I can only find: %d records of %d\n", ant,
+	   dupp_keys);
+    goto end;
+  }
+
+  if (testflag == 4) goto end;
+
+  printf("- Reading through all rows through keys\n");
+  if (!(file2=heap_open(filename, 2)))
+    goto err;
+  if (heap_scan_init(file))
+    goto err;
+  while ((error=heap_scan(file,record)) != HA_ERR_END_OF_FILE)
+  {
+    if (error == 0)
+    {
+      if (heap_rkey(file2,record2,2,record+keyinfo[2].seg[0].start,8,
+		    HA_READ_KEY_EXACT))
+      {
+	printf("can't find key3: \"%.8s\"\n",
+	       record+keyinfo[2].seg[0].start);
+	goto err;
+      }
+    }
+  }
+  heap_close(file2);
+
+  printf("- Creating output heap-file 2\n");
+  hp_create_info.keys= 1;
+  hp_create_info.max_records= 0;
+  hp_create_info.min_records= 0;
+  if (heap_create(filename2, &hp_create_info, &tmp_share, &unused) ||
+      !(file2= heap_open_from_share_and_register(tmp_share, 2)))
+    goto err;
+
+  printf("- Copying and removing records\n");
+  if (heap_scan_init(file))
+    goto err;
+  while ((error=heap_scan(file,record)) != HA_ERR_END_OF_FILE)
+  {
+    if (error == 0)
+    {
+      if (heap_write(file2,record))
+	goto err;
+      key_check-=atoi((char*) record);
+      write_count++;
+      if (heap_delete(file,record))
+	goto err;
+      opt_delete++;
+    }
+    pos++;
+  }
+  printf("- Checking heap tables\n");
+  if (heap_check_heap(file,1) || heap_check_heap(file2,1))
+  {
+    puts("Heap keys crashed");
+    goto err;
+  }
+
+  if (my_errno != HA_ERR_END_OF_FILE)
+    printf("error: %d from heap_rrnd\n",my_errno);
+  if (key_check)
+    printf("error: Some read got wrong: check is %ld\n",(long) key_check);
+
+end:
+  printf("\nFollowing test have been made:\n");
+  printf("Write records: %d\nUpdate records: %d\nDelete records: %d\n", write_count,update,opt_delete);
+  heap_clear(file);
+  if (heap_close(file) || (file2 && heap_close(file2)))
+    goto err;
+  heap_delete_table(filename2);
+  hp_panic(HA_PANIC_CLOSE);
+  my_end(MY_GIVE_INFO);
+  return(0);
+err:
+  printf("Got error: %d when using heap-database\n",my_errno);
+  (void) heap_close(file);
+  return(1);
+} /* main */
+
+
+	/* Read options */
+
+static int get_options(int argc,char *argv[])
+{
+  char *pos,*progname;
+
+  progname= argv[0];
+
+  while (--argc >0 && *(pos = *(++argv)) == '-' ) {
+    switch(*++pos) {
+    case 'B':				/* Big file */
+      flag=1;
+      break;
+    case 'v':				/* verbose */
+      verbose=1;
+      break;
+    case 'm':				/* records */
+      recant=atoi(++pos);
+      break;
+    case 's':
+      silent=1;
+      break;
+    case 't':
+      testflag=atoi(++pos);		/* testmod */
+      break;
+    case 'V':
+    case 'I':
+    case '?':
+      printf("%s  Ver 1.2 for %s at %s\n",progname,SYSTEM_TYPE,MACHINE_TYPE);
+      puts("TCX Datakonsult AB, by Monty, for your professional use\n");
+      printf("Usage: %s [-?ABIKLsWv] [-m#] [-t#]\n",progname);
+      exit(0);
+    case '#':
+      DBUG_PUSH (++pos);
+      break;
+    }
+  }
+  return 0;
+} /* get options */
+
+	/* Generate a random value in intervall 0 <=x <= n */
+
+static int rnd(int max_value)
+{
+  return (int) ((rand() & 32767)/32767.0*max_value);
+} /* rnd */
+
+
+static sig_handler endprog(int sig_number __attribute__((unused)))
+{
+  {
+    hp_panic(HA_PANIC_CLOSE);
+    my_end(1);
+    exit(1);
+  }
+}
+
+static int calc_check(uchar *buf, uint length)
+{
+  int check=0;
+  while (length--)
+    check+= (int) (uchar) *(buf++);
+  return check;
+}
+
+static void make_record(uchar *record, uint n1, uint n2, uint n3,
+			const char *mark, uint count)
+{
+  bfill(record,reclength,' ');
+  sprintf((char*) record,"%6d:%4d:%8d:%3.3s: %4d",
+	  n1,n2,n3,mark,count);
+  record[37]='A';				/* Store A in null key */
+  record[38]=1;					/* set as null */
+}
diff --git a/storage/heap/hp_update.c b/storage/heap/hp_update.c
new file mode 100644
index 00000000..da83a9c7
--- /dev/null
+++ b/storage/heap/hp_update.c
@@ -0,0 +1,91 @@
+/* Copyright (c) 2000-2002, 2004-2008 MySQL AB
+   Use is subject to license terms
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; version 2 of the License.
+
+   This program 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 General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1335  USA */
+
+/* Update current record in heap-database */
+
+#include "heapdef.h"
+
+int heap_update(HP_INFO *info, const uchar *old, const uchar *heap_new)
+{
+  HP_KEYDEF *keydef, *end, *p_lastinx;
+  uchar *pos;
+  my_bool auto_key_changed= 0, key_changed= 0;
+  HP_SHARE *share= info->s;
+  DBUG_ENTER("heap_update");
+
+  test_active(info);
+  pos=info->current_ptr;
+
+  if (info->opt_flag & READ_CHECK_USED && hp_rectest(info,old))
+    DBUG_RETURN(my_errno);				/* Record changed */
+  if (--(share->records) < share->blength >> 1) share->blength>>= 1;
+  share->changed=1;
+
+  p_lastinx= share->keydef + info->lastinx;
+  for (keydef= share->keydef, end= keydef + share->keys; keydef < end; keydef++)
+  {
+    if (hp_rec_key_cmp(keydef, old, heap_new))
+    {
+      if ((*keydef->delete_key)(info, keydef, old, pos, keydef == p_lastinx) ||
+          (*keydef->write_key)(info, keydef, heap_new, pos))
+        goto err;
+      if (share->auto_key == (uint) (keydef - share->keydef + 1))
+        auto_key_changed= 1;
+    }
+  }
+
+  memcpy(pos,heap_new,(size_t) share->reclength);
+  if (++(share->records) == share->blength) share->blength+= share->blength;
+
+#if !defined(DBUG_OFF) && defined(EXTRA_HEAP_DEBUG)
+  DBUG_EXECUTE("check_heap",heap_check_heap(info, 0););
+#endif
+  if (auto_key_changed)
+    heap_update_auto_increment(info, heap_new);
+  if (key_changed)
+    share->key_version++;
+  DBUG_RETURN(0);
+
+ err:
+  if (my_errno == HA_ERR_FOUND_DUPP_KEY)
+  {
+    info->errkey = (int) (keydef - share->keydef);
+    if (keydef->algorithm == HA_KEY_ALG_BTREE)
+    {
+      /* we don't need to delete non-inserted key from rb-tree */
+      if ((*keydef->write_key)(info, keydef, old, pos))
+      {
+        if (++(share->records) == share->blength)
+	  share->blength+= share->blength;
+        DBUG_RETURN(my_errno);
+      }
+      keydef--;
+    }
+    while (keydef >= share->keydef)
+    {
+      if (hp_rec_key_cmp(keydef, old, heap_new))
+      {
+	if ((*keydef->delete_key)(info, keydef, heap_new, pos, 0) ||
+	    (*keydef->write_key)(info, keydef, old, pos))
+	  break;
+      }
+      keydef--;
+    }
+  }
+  if (++(share->records) == share->blength)
+    share->blength+= share->blength;
+  DBUG_RETURN(my_errno);
+} /* heap_update */
diff --git a/storage/heap/hp_write.c b/storage/heap/hp_write.c
new file mode 100644
index 00000000..5469784c
--- /dev/null
+++ b/storage/heap/hp_write.c
@@ -0,0 +1,416 @@
+/* Copyright (c) 2000-2002, 2004-2007 MySQL AB, 2009 Sun Microsystems, Inc.
+   Use is subject to license terms.
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; version 2 of the License.
+
+   This program 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 General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1335  USA */
+
+/* Write a record to heap-databas */
+
+#include "heapdef.h"
+#ifdef _WIN32
+#include <fcntl.h>
+#endif
+
+#define LOWFIND 1
+#define LOWUSED 2
+#define HIGHFIND 4
+#define HIGHUSED 8
+
+static uchar *next_free_record_pos(HP_SHARE *info);
+static HASH_INFO *hp_find_free_hash(HP_SHARE *info, HP_BLOCK *block,
+				     ulong records);
+
+int heap_write(HP_INFO *info, const uchar *record)
+{
+  HP_KEYDEF *keydef, *end;
+  uchar *pos;
+  HP_SHARE *share=info->s;
+  DBUG_ENTER("heap_write");
+#ifndef DBUG_OFF
+  if (info->mode & O_RDONLY)
+  {
+    DBUG_RETURN(my_errno=EACCES);
+  }
+#endif
+  if (!(pos=next_free_record_pos(share)))
+    DBUG_RETURN(my_errno);
+  share->changed=1;
+
+  for (keydef = share->keydef, end = keydef + share->keys; keydef < end;
+       keydef++)
+  {
+    if ((*keydef->write_key)(info, keydef, record, pos))
+      goto err;
+  }
+
+  memcpy(pos,record,(size_t) share->reclength);
+  pos[share->visible]= 1;                     /* Mark record as not deleted */
+  if (++share->records == share->blength)
+    share->blength+= share->blength;
+  info->s->key_version++;
+  info->update|=HA_STATE_AKTIV;
+#if !defined(DBUG_OFF) && defined(EXTRA_HEAP_DEBUG)
+  DBUG_EXECUTE("check_heap",heap_check_heap(info, 0););
+#endif
+  if (share->auto_key)
+    heap_update_auto_increment(info, record);
+  DBUG_RETURN(0);
+
+err:
+  if (my_errno == HA_ERR_FOUND_DUPP_KEY)
+    DBUG_PRINT("info",("Duplicate key: %d", (int) (keydef - share->keydef)));
+  info->errkey= (int) (keydef - share->keydef);
+  /*
+    We don't need to delete non-inserted key from rb-tree.  Also, if
+    we got ENOMEM, the key wasn't inserted, so don't try to delete it
+    either.  Otherwise for HASH index on HA_ERR_FOUND_DUPP_KEY the key
+    was inserted and we have to delete it.
+  */
+  if (keydef->algorithm == HA_KEY_ALG_BTREE || my_errno == ENOMEM)
+  {
+    keydef--;
+  }
+  while (keydef >= share->keydef)
+  {
+    if ((*keydef->delete_key)(info, keydef, record, pos, 0))
+      break;
+    keydef--;
+  } 
+
+  share->deleted++;
+  *((uchar**) pos)=share->del_link;
+  share->del_link=pos;
+  pos[share->visible]= 0;                                 /* Record deleted */
+
+  DBUG_RETURN(my_errno);
+} /* heap_write */
+
+/* 
+  Write a key to rb_tree-index 
+*/
+
+int hp_rb_write_key(HP_INFO *info, HP_KEYDEF *keyinfo, const uchar *record, 
+		    uchar *recpos)
+{
+  heap_rb_param custom_arg;
+  size_t old_allocated;
+
+  custom_arg.keyseg= keyinfo->seg;
+  custom_arg.key_length= hp_rb_make_key(keyinfo, info->recbuf, record, recpos);
+  if (keyinfo->flag & HA_NOSAME)
+  {
+    custom_arg.search_flag= SEARCH_FIND | SEARCH_UPDATE | SEARCH_INSERT;
+    keyinfo->rb_tree.flag= TREE_NO_DUPS;
+  }
+  else
+  {
+    custom_arg.search_flag= SEARCH_SAME;
+    keyinfo->rb_tree.flag= 0;
+  }
+  old_allocated= keyinfo->rb_tree.allocated;
+  if (!tree_insert(&keyinfo->rb_tree, (void*)info->recbuf,
+		   custom_arg.key_length, &custom_arg))
+  {
+    my_errno= HA_ERR_FOUND_DUPP_KEY;
+    return 1;
+  }
+  info->s->index_length+= (keyinfo->rb_tree.allocated-old_allocated);
+  return 0;
+}
+
+	/* Find where to place new record */
+
+static uchar *next_free_record_pos(HP_SHARE *info)
+{
+  int block_pos;
+  uchar *pos;
+  size_t length;
+  DBUG_ENTER("next_free_record_pos");
+
+  if (info->del_link)
+  {
+    pos=info->del_link;
+    info->del_link= *((uchar**) pos);
+    info->deleted--;
+    DBUG_PRINT("exit",("Used old position: %p", pos));
+    DBUG_RETURN(pos);
+  }
+  if ((info->records > info->max_records && info->max_records) ||
+      (info->data_length + info->index_length >= info->max_table_size))
+  {
+    DBUG_PRINT("error",
+                ("record file full. records: %lu  max_records: %lu  "
+                "data_length: %llu  index_length: %llu  "
+                "max_table_size: %llu",
+                info->records, info->max_records,
+                info->data_length, info->index_length,
+                info->max_table_size));
+    my_errno=HA_ERR_RECORD_FILE_FULL;
+    DBUG_RETURN(NULL);
+  }
+  if (!(block_pos=(info->records % info->block.records_in_block)))
+  {
+    if (hp_get_new_block(info, &info->block,&length))
+      DBUG_RETURN(NULL);
+    info->data_length+=length;
+  }
+  DBUG_PRINT("exit",("Used new position: %p",
+		     ((uchar*) info->block.level_info[0].last_blocks+
+                      block_pos * info->block.recbuffer)));
+  DBUG_RETURN((uchar*) info->block.level_info[0].last_blocks+
+	      block_pos*info->block.recbuffer);
+}
+
+
+/*
+  Write a hash-key to the hash-index
+  SYNOPSIS
+    info     Heap table info
+    keyinfo  Key info
+    record   Table record to added
+    recpos   Memory buffer where the table record will be stored if added 
+             successfully
+  NOTE
+    Hash index uses HP_BLOCK structure as a 'growable array' of HASH_INFO 
+    structs. Array size == number of entries in hash index.
+    hp_mask(hp_rec_hashnr()) maps hash entries values to hash array positions.
+    If there are several hash entries with the same hash array position P,
+    they are connected in a linked list via HASH_INFO::next_key. The first 
+    list element is located at position P, next elements are located at 
+    positions for which there is no record that should be located at that
+    position. The order of elements in the list is arbitrary.
+
+  RETURN
+    0  - OK
+    -1 - Out of memory
+    HA_ERR_FOUND_DUPP_KEY - Duplicate record on unique key. The record was 
+    still added and the caller must call hp_delete_key for it.
+*/
+
+int hp_write_key(HP_INFO *info, HP_KEYDEF *keyinfo,
+		 const uchar *record, uchar *recpos)
+{
+  HP_SHARE *share = info->s;
+  int flag;
+  ulong halfbuff,hashnr,first_index;
+  ulong UNINIT_VAR(hash_of_key), UNINIT_VAR(hash_of_key2);
+  uchar *UNINIT_VAR(ptr_to_rec),*UNINIT_VAR(ptr_to_rec2);
+  HASH_INFO *empty,*UNINIT_VAR(gpos),*UNINIT_VAR(gpos2),*pos;
+  DBUG_ENTER("hp_write_key");
+
+  flag=0;
+  if (!(empty= hp_find_free_hash(share,&keyinfo->block,share->records)))
+    DBUG_RETURN(-1);				/* No more memory */
+  halfbuff= (long) share->blength >> 1;
+  pos= hp_find_hash(&keyinfo->block,(first_index=share->records-halfbuff));
+  
+  /*
+    We're about to add one more hash array position, with hash_mask=#records.
+    The number of hash positions will change and some entries might need to 
+    be relocated to the newly added position. Those entries are currently 
+    members of the list that starts at #first_index position (this is 
+    guaranteed by properties of hp_mask(hp_rec_hashnr(X)) mapping function)
+    At #first_index position currently there may be either:
+    a) An entry with hashnr != first_index. We don't need to move it.
+    or
+    b) A list of items with hash_mask=first_index. The list contains entries
+       of 2 types:
+       1) entries that should be relocated to the list that starts at new 
+          position we're adding ('uppper' list)
+       2) entries that should be left in the list starting at #first_index 
+          position ('lower' list)
+  */
+  if (pos != empty)				/* If some records */
+  {
+    do
+    {
+      hashnr = pos->hash_of_key;
+      if (flag == 0)
+      {
+        /* 
+          First loop, bail out if we're dealing with case a) from above 
+          comment
+        */
+	if (hp_mask(hashnr, share->blength, share->records) != first_index)
+	  break;
+      }
+      /*
+        flag & LOWFIND - found a record that should be put into lower position
+        flag & LOWUSED - lower position occupied by the record
+        Same for HIGHFIND and HIGHUSED and 'upper' position
+
+        gpos  - ptr to last element in lower position's list
+        gpos2 - ptr to last element in upper position's list
+
+        ptr_to_rec - ptr to last entry that should go into lower list.
+        ptr_to_rec2 - same for upper list.
+      */
+      if (!(hashnr & halfbuff))
+      {						
+        /* Key should be put into 'lower' list */
+	if (!(flag & LOWFIND))
+	{
+          /* key is the first element to go into lower position */
+	  if (flag & HIGHFIND)
+	  {
+	    flag=LOWFIND | HIGHFIND;
+	    /* key shall be moved to the current empty position */
+	    gpos=empty;
+	    empty=pos;				/* This place is now free */
+	  }
+	  else
+	  {
+            /*
+              We can only get here at first iteration: key is at 'lower' 
+              position pos and should be left here.
+            */
+	    flag=LOWFIND | LOWUSED;
+	    gpos=pos;
+	  }
+	}
+	else
+        {
+          /* Already have another key for lower position */
+	  if (!(flag & LOWUSED))
+	  {
+	    /* Change link of previous lower-list key */
+	    gpos->ptr_to_rec=  ptr_to_rec;
+	    gpos->next_key=    pos;
+            gpos->hash_of_key= hash_of_key;
+	    flag= (flag & HIGHFIND) | (LOWFIND | LOWUSED);
+	  }
+	  gpos=pos;
+	}
+        ptr_to_rec=  pos->ptr_to_rec;
+        hash_of_key= pos->hash_of_key;
+      }
+      else
+      {
+        /* key will be put into 'higher' list */
+	if (!(flag & HIGHFIND))
+	{
+	  flag= (flag & LOWFIND) | HIGHFIND;
+	  /* key shall be moved to the last (empty) position */
+	  gpos2= empty;
+          empty= pos;
+	}
+	else
+	{
+	  if (!(flag & HIGHUSED))
+	  {
+	    /* Change link of previous upper-list key and save */
+	    gpos2->ptr_to_rec=  ptr_to_rec2;
+	    gpos2->next_key=    pos;
+            gpos2->hash_of_key= hash_of_key2;
+	    flag= (flag & LOWFIND) | (HIGHFIND | HIGHUSED);
+	  }
+	  gpos2=pos;
+	}
+        ptr_to_rec2=  pos->ptr_to_rec;
+        hash_of_key2= pos->hash_of_key;
+      }
+    }
+    while ((pos=pos->next_key));
+    
+    if ((flag & (LOWFIND | HIGHFIND)) == (LOWFIND | HIGHFIND))
+    {
+      /*
+        If both 'higher' and 'lower' list have at least one element, now
+        there are two hash buckets instead of one.
+      */
+      keyinfo->hash_buckets++;
+    }
+
+    if ((flag & (LOWFIND | LOWUSED)) == LOWFIND)
+    {
+      gpos->ptr_to_rec=  ptr_to_rec;
+      gpos->hash_of_key= hash_of_key;
+      gpos->next_key=    0;
+    }
+    if ((flag & (HIGHFIND | HIGHUSED)) == HIGHFIND)
+    {
+      gpos2->ptr_to_rec=  ptr_to_rec2;
+      gpos2->hash_of_key= hash_of_key2;
+      gpos2->next_key=    0;
+    }
+  }
+  /* Check if we are at the empty position */
+
+  hash_of_key= hp_rec_hashnr(keyinfo, record);
+  pos=hp_find_hash(&keyinfo->block,
+                   hp_mask(hash_of_key, share->blength, share->records + 1));
+  if (pos == empty)
+  {
+    pos->ptr_to_rec=  recpos;
+    pos->hash_of_key= hash_of_key;
+    pos->next_key=    0;
+    keyinfo->hash_buckets++;
+  }
+  else
+  {
+    /* Check if more records in same hash-nr family */
+    empty[0]=pos[0];
+    gpos=hp_find_hash(&keyinfo->block,
+		      hp_mask(pos->hash_of_key,
+			      share->blength, share->records + 1));
+
+    pos->ptr_to_rec=  recpos;
+    pos->hash_of_key= hash_of_key;
+    if (pos == gpos)
+      pos->next_key=empty;
+    else
+    {
+      keyinfo->hash_buckets++;
+      pos->next_key= 0;
+      hp_movelink(pos, gpos, empty);
+    }
+
+    /* Check if duplicated keys */
+    if ((keyinfo->flag & HA_NOSAME) && pos == gpos &&
+	(!(keyinfo->flag & HA_NULL_PART_KEY) ||
+	 !hp_if_null_in_key(keyinfo, record)))
+    {
+      pos=empty;
+      do
+      {
+	if (pos->hash_of_key == hash_of_key &&
+            ! hp_rec_key_cmp(keyinfo, record, pos->ptr_to_rec))
+	{
+	  DBUG_RETURN(my_errno=HA_ERR_FOUND_DUPP_KEY);
+	}
+      } while ((pos=pos->next_key));
+    }
+  }
+  DBUG_RETURN(0);
+}
+
+	/* Returns ptr to block, and allocates block if neaded */
+
+static HASH_INFO *hp_find_free_hash(HP_SHARE *info,
+				     HP_BLOCK *block, ulong records)
+{
+  ulong block_pos;
+  size_t length;
+
+  if (records < block->last_allocated)
+    return hp_find_hash(block,records);
+  if (!(block_pos=(records % block->records_in_block)))
+  {
+    if (hp_get_new_block(info, block, &length))
+      return(NULL);
+    info->index_length+=length;
+  }
+  block->last_allocated=records+1;
+  return((HASH_INFO*) ((uchar*) block->level_info[0].last_blocks+
+		       block_pos*block->recbuffer));
+}
diff --git a/storage/heap/mysql-test/mtr2/README b/storage/heap/mysql-test/mtr2/README
new file mode 100644
index 00000000..5b2453d0
--- /dev/null
+++ b/storage/heap/mysql-test/mtr2/README
@@ -0,0 +1,2 @@
+These tests don't have anything to do with the engine itself,
+but they test how mysql-test handles overlays
diff --git a/storage/heap/mysql-test/mtr2/my.cnf b/storage/heap/mysql-test/mtr2/my.cnf
new file mode 100644
index 00000000..772daa0f
--- /dev/null
+++ b/storage/heap/mysql-test/mtr2/my.cnf
@@ -0,0 +1 @@
+!include include/default_my.cnf