Added storage/maria (based on MyISAM). WL#3245

Moved things into ft_global.h, my_handler.h and myisamchk.h to allow MyISAM and Maria to share code and defines
Rename of not properly renamed functions in MyISAM and my_handler.c
Renamed some MI_ defines to HA_ to allow MyISAM and Maria to share
Added maria variables to mysqld.cc and set_var.cc
Fixed compiler warnings



BitKeeper/etc/ignore:
  added storage/maria/*.MAI
BUILD/SETUP.sh:
  Compile maria by default
BitKeeper/triggers/post-commit:
  No public maria emails.
  Mark changesets emails with 'maria'
configure.in:
  Add maria
include/ft_global.h:
  Move defines needed by maria and MyISAM here
include/keycache.h:
  Add support for default key_cache if cache not found
include/my_base.h:
  Add invalidator_by_filename
include/my_handler.h:
  Remove duplicate header files
  Add defines that are typical for handlers (MyISAM and Maria)
include/myisam.h:
  Move things to my_handler.h to allow Maria and MyISAM to share things
  (Some things needed to be shared to allow sharing of HA_CHECK structure)
libmysqld/Makefile.am:
  Added ha_maria.cc
mysys/mf_keycaches.c:
  Added default value for multi_key_cache_search
mysys/my_handler.c:
  mi_compare_text -> ha_compare_text
  Removed compiler warnings
sql/ha_myisam.cc:
  MI_CHECK -> HA_CHECK
  MI_MAX_KEY_LENGTH -> HA_MAX_KEY_LENGTH
sql/ha_myisam.h:
  MI_CHECK -> HA_CHECK
  MI_MAX_KEY_LENGTH -> HA_MAX_KEY_LENGTH
sql/ha_myisammrg.h:
  MI_CHECK -> HA_CHECK
  MI_MAX_KEY_LENGTH -> HA_MAX_KEY_LENGTH
sql/handler.h:
  Added MARIA
  Added inclusion of my_handler.h
sql/item_func.h:
  Remove duplicate include
sql/mysql_priv.h:
  Added maria variables
sql/mysqld.cc:
  Added maria
sql/set_var.cc:
  Added maria status variables
sql/set_var.h:
  Added maria
sql/sql_class.h:
  Added maria status variables
sql/sql_sort.h:
  Remove duplicate BUFFPEK struct
storage/Makefile.am:
  Added maria
storage/csv/ha_tina.cc:
  Removed compiler warning
storage/myisam/Makefile.am:
  Added ft_myisam.c
storage/myisam/ft_boolean_search.c:
  mi_compare_text -> ha_compare_text
  MI_MAX_KEY_BUFF -> HA_MAX_KEY_BUFF
  Remove compiler warnings
storage/myisam/ft_nlq_search.c:
  mi_compare_text -> ha_compare_text
storage/myisam/ft_parser.c:
  mi_compare_text -> ha_compare_text
storage/myisam/ft_static.c:
  Move ft_init_search() to ft_myisam.c to make ft_static.c independent of MyISAM
storage/myisam/ft_stopwords.c:
  mi_compare_text -> ha_compare_text
storage/myisam/ft_update.c:
  mi_compare_text -> ha_compare_text
storage/myisam/fulltext.h:
  Move things to ft_global.h to allow to share more things between MyISAM and Maria
storage/myisam/mi_check.c:
  MI_CHECK -> HA_CHECK
storage/myisam/mi_create.c:
  MI_MAX_POSSIBLE_KEY ->   HA_MAX_POSSIBLE_KEY
  MI_MAX_KEY_BLOCK_SIZE -> HA_MAX_KEY_BLOCK_SIZE
  MI_MAX_KEY_SEG ->  HA_MAX_KEY_SEG
  MI_MAX_KEY_BUFF -> HA_MAX_KEY_BUFF
storage/myisam/mi_delete.c:
  MI_MAX_KEY_BUFF -> HA_MAX_KEY_BUFF
storage/myisam/mi_delete_all.c:
  Remove not used variable
storage/myisam/mi_dynrec.c:
  _my_calc_total_blob_length -> _mi_calc_total_blob_length
storage/myisam/mi_key.c:
  _my_store_blob_length -> _mi_store_blob_length
storage/myisam/mi_log.c:
  _my_calc_total_blob_length -> _mi_calc_total_blob_length
storage/myisam/mi_open.c:
  MI_MAX_POSSIBLE_KEY -> HA_MAX_POSSIBLE_KEY
  MI_MAX_KEY_SEG ->      HA_MAX_KEY_SEG
  MI_MAX_KEY_BUFF ->     HA_MAX_KEY_BUFF
  my_n_base_info_read -> mi_n_base_info_read
storage/myisam/mi_packrec.c:
  Made read_pack_length static
  _my_store_blob_length -> _mi_store_blob_length
  Remove not used variable
storage/myisam/mi_range.c:
  MI_MAX_KEY_BUFF -> HA_MAX_KEY_BUFF
storage/myisam/mi_search.c:
  MI_MAX_KEY_BUFF -> HA_MAX_KEY_BUFF
storage/myisam/mi_test1.c:
  MI_MAX_KEY_LENGTH -> HA_MAX_KEY_LENGTH
storage/myisam/mi_test2.c:
  Fixed compiler warning
storage/myisam/mi_unique.c:
  Fixed compiler warning
  mi_compare_text -> ha_compare_text
storage/myisam/mi_update.c:
  MI_MAX_KEY_BUFF -> HA_MAX_KEY_BUFF
storage/myisam/mi_write.c:
  Rename of defines and functions
storage/myisam/myisamchk.c:
  Rename of defines and functions
storage/myisam/myisamdef.h:
  Remove tabs
  Indentation fixes (Large changes as I did run indent-ex on the file)
  Move some things to myisamchk.h
  Added missing functions that gave compiler warnings
storage/myisam/myisamlog.c:
  Rename of defines and functions
storage/myisam/myisampack.c:
  Remove compiler warning
storage/myisam/rt_index.c:
  Rename of defines and functions
storage/myisam/sort.c:
  Rename of defines, functions and structures
config/ac-macros/ha_maria.m4:
  New BitKeeper file ``config/ac-macros/ha_maria.m4''
include/maria.h:
  New BitKeeper file ``include/maria.h''
include/myisamchk.h:
  New BitKeeper file ``include/myisamchk.h''
libmysqld/ha_maria.cc:
  New BitKeeper file ``libmysqld/ha_maria.cc''
mysql-test/include/have_maria.inc:
  New BitKeeper file ``mysql-test/include/have_maria.inc''
mysql-test/r/have_maria.require:
  New BitKeeper file ``mysql-test/r/have_maria.require''
mysql-test/r/maria.result:
  New BitKeeper file ``mysql-test/r/maria.result''
mysql-test/r/ps_maria.result:
  New BitKeeper file ``mysql-test/r/ps_maria.result''
mysql-test/t/maria.test:
  New BitKeeper file ``mysql-test/t/maria.test''
mysql-test/t/ps_maria.test:
  New BitKeeper file ``mysql-test/t/ps_maria.test''
sql/ha_maria.cc:
  New BitKeeper file ``sql/ha_maria.cc''
sql/ha_maria.h:
  New BitKeeper file ``sql/ha_maria.h''
storage/maria/Makefile.am:
  New BitKeeper file ``storage/maria/Makefile.am''
storage/maria/cmakelists.txt:
  New BitKeeper file ``storage/maria/cmakelists.txt''
storage/maria/ft_maria.c:
  New BitKeeper file ``storage/maria/ft_maria.c''
storage/maria/ma_cache.c:
  New BitKeeper file ``storage/maria/ma_cache.c''
storage/maria/ma_changed.c:
  New BitKeeper file ``storage/maria/ma_changed.c''
storage/maria/ma_check.c:
  New BitKeeper file ``storage/maria/ma_check.c''
storage/maria/ma_checksum.c:
  New BitKeeper file ``storage/maria/ma_checksum.c''
storage/maria/ma_close.c:
  New BitKeeper file ``storage/maria/ma_close.c''
storage/maria/ma_create.c:
  New BitKeeper file ``storage/maria/ma_create.c''
storage/maria/ma_dbug.c:
  New BitKeeper file ``storage/maria/ma_dbug.c''
storage/maria/ma_delete.c:
  New BitKeeper file ``storage/maria/ma_delete.c''
storage/maria/ma_delete_all.c:
  New BitKeeper file ``storage/maria/ma_delete_all.c''
storage/maria/ma_delete_table.c:
  New BitKeeper file ``storage/maria/ma_delete_table.c''
storage/maria/ma_dynrec.c:
  New BitKeeper file ``storage/maria/ma_dynrec.c''
storage/maria/ma_extra.c:
  New BitKeeper file ``storage/maria/ma_extra.c''
storage/maria/ma_ft_boolean_search.c:
  New BitKeeper file ``storage/maria/ma_ft_boolean_search.c''
storage/maria/ma_ft_eval.c:
  New BitKeeper file ``storage/maria/ma_ft_eval.c''
storage/maria/ma_ft_eval.h:
  New BitKeeper file ``storage/maria/ma_ft_eval.h''
storage/maria/ma_ft_nlq_search.c:
  New BitKeeper file ``storage/maria/ma_ft_nlq_search.c''
storage/maria/ma_ft_parser.c:
  New BitKeeper file ``storage/maria/ma_ft_parser.c''
storage/maria/ma_ft_stem.c:
  New BitKeeper file ``storage/maria/ma_ft_stem.c''
storage/maria/ma_ft_test1.c:
  New BitKeeper file ``storage/maria/ma_ft_test1.c''
storage/maria/ma_ft_test1.h:
  New BitKeeper file ``storage/maria/ma_ft_test1.h''
storage/maria/ma_ft_update.c:
  New BitKeeper file ``storage/maria/ma_ft_update.c''
storage/maria/ma_ftdefs.h:
  New BitKeeper file ``storage/maria/ma_ftdefs.h''
storage/maria/ma_fulltext.h:
  New BitKeeper file ``storage/maria/ma_fulltext.h''
storage/maria/ma_info.c:
  New BitKeeper file ``storage/maria/ma_info.c''
storage/maria/ma_init.c:
  New BitKeeper file ``storage/maria/ma_init.c''
storage/maria/ma_key.c:
  New BitKeeper file ``storage/maria/ma_key.c''
storage/maria/ma_keycache.c:
  New BitKeeper file ``storage/maria/ma_keycache.c''
storage/maria/ma_locking.c:
  New BitKeeper file ``storage/maria/ma_locking.c''
storage/maria/ma_log.c:
  New BitKeeper file ``storage/maria/ma_log.c''
storage/maria/ma_open.c:
  New BitKeeper file ``storage/maria/ma_open.c''
storage/maria/ma_packrec.c:
  New BitKeeper file ``storage/maria/ma_packrec.c''
storage/maria/ma_page.c:
  New BitKeeper file ``storage/maria/ma_page.c''
storage/maria/ma_panic.c:
  New BitKeeper file ``storage/maria/ma_panic.c''
storage/maria/ma_preload.c:
  New BitKeeper file ``storage/maria/ma_preload.c''
storage/maria/ma_range.c:
  New BitKeeper file ``storage/maria/ma_range.c''
storage/maria/ma_rename.c:
  New BitKeeper file ``storage/maria/ma_rename.c''
storage/maria/ma_rfirst.c:
  New BitKeeper file ``storage/maria/ma_rfirst.c''
storage/maria/ma_rkey.c:
  New BitKeeper file ``storage/maria/ma_rkey.c''
storage/maria/ma_rlast.c:
  New BitKeeper file ``storage/maria/ma_rlast.c''
storage/maria/ma_rnext.c:
  New BitKeeper file ``storage/maria/ma_rnext.c''
storage/maria/ma_rnext_same.c:
  New BitKeeper file ``storage/maria/ma_rnext_same.c''
storage/maria/ma_rprev.c:
  New BitKeeper file ``storage/maria/ma_rprev.c''
storage/maria/ma_rrnd.c:
  New BitKeeper file ``storage/maria/ma_rrnd.c''
storage/maria/ma_rsame.c:
  New BitKeeper file ``storage/maria/ma_rsame.c''
storage/maria/ma_rsamepos.c:
  New BitKeeper file ``storage/maria/ma_rsamepos.c''
storage/maria/ma_rt_index.c:
  New BitKeeper file ``storage/maria/ma_rt_index.c''
storage/maria/ma_rt_index.h:
  New BitKeeper file ``storage/maria/ma_rt_index.h''
storage/maria/ma_rt_key.c:
  New BitKeeper file ``storage/maria/ma_rt_key.c''
storage/maria/ma_rt_key.h:
  New BitKeeper file ``storage/maria/ma_rt_key.h''
storage/maria/ma_rt_mbr.c:
  New BitKeeper file ``storage/maria/ma_rt_mbr.c''
storage/maria/ma_rt_mbr.h:
  New BitKeeper file ``storage/maria/ma_rt_mbr.h''
storage/maria/ma_rt_split.c:
  New BitKeeper file ``storage/maria/ma_rt_split.c''
storage/maria/ma_rt_test.c:
  New BitKeeper file ``storage/maria/ma_rt_test.c''
storage/maria/ma_scan.c:
  New BitKeeper file ``storage/maria/ma_scan.c''
storage/maria/ma_search.c:
  New BitKeeper file ``storage/maria/ma_search.c''
storage/maria/ma_sort.c:
  New BitKeeper file ``storage/maria/ma_sort.c''
storage/maria/ma_sp_defs.h:
  New BitKeeper file ``storage/maria/ma_sp_defs.h''
storage/maria/ma_sp_key.c:
  New BitKeeper file ``storage/maria/ma_sp_key.c''
storage/maria/ma_sp_test.c:
  New BitKeeper file ``storage/maria/ma_sp_test.c''
storage/maria/ma_static.c:
  New BitKeeper file ``storage/maria/ma_static.c''
storage/maria/ma_statrec.c:
  New BitKeeper file ``storage/maria/ma_statrec.c''
storage/maria/ma_test1.c:
  New BitKeeper file ``storage/maria/ma_test1.c''
storage/maria/ma_test2.c:
  New BitKeeper file ``storage/maria/ma_test2.c''
storage/maria/ma_test3.c:
  New BitKeeper file ``storage/maria/ma_test3.c''
storage/maria/ma_test_all.sh:
  New BitKeeper file ``storage/maria/ma_test_all.sh''
storage/maria/ma_unique.c:
  New BitKeeper file ``storage/maria/ma_unique.c''
storage/maria/ma_update.c:
  New BitKeeper file ``storage/maria/ma_update.c''
storage/maria/ma_write.c:
  New BitKeeper file ``storage/maria/ma_write.c''
storage/maria/maria_chk.c:
  New BitKeeper file ``storage/maria/maria_chk.c''
storage/maria/maria_def.h:
  New BitKeeper file ``storage/maria/maria_def.h''
storage/maria/maria_ftdump.c:
  New BitKeeper file ``storage/maria/maria_ftdump.c''
storage/maria/maria_log.c:
  New BitKeeper file ``storage/maria/maria_log.c''
storage/maria/maria_pack.c:
  New BitKeeper file ``storage/maria/maria_pack.c''
storage/maria/maria_rename.sh:
  New BitKeeper file ``storage/maria/maria_rename.sh''
storage/maria/test_pack:
  New BitKeeper file ``storage/maria/test_pack''
storage/myisam/ft_myisam.c:
  New BitKeeper file ``storage/myisam/ft_myisam.c''

1 files changed, 1081 insertions, 0 deletions

diff --git a/storage/maria/ma_rt_index.c b/storage/maria/ma_rt_index.c
new file mode 100644
index 00000000000..ff10ae72027
--- /dev/null
+++ b/storage/maria/ma_rt_index.c
@@ -0,0 +1,1081 @@
+/* Copyright (C) 2006 MySQL AB & Ramil Kalimullin & MySQL Finland AB
+   & TCX DataKonsult 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; either version 2 of the License, or
+   (at your option) any later version.
+
+   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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
+
+#include "maria_def.h"
+
+#ifdef HAVE_RTREE_KEYS
+
+#include "ma_rt_index.h"
+#include "ma_rt_key.h"
+#include "ma_rt_mbr.h"
+
+#define REINSERT_BUFFER_INC 10
+#define PICK_BY_AREA
+/*#define PICK_BY_PERIMETER*/
+
+typedef struct st_page_level
+{
+  uint level;
+  my_off_t offs;
+} stPageLevel;
+
+typedef struct st_page_list
+{
+  ulong n_pages;
+  ulong m_pages;
+  stPageLevel *pages;
+} stPageList;
+
+
+/*
+   Find next key in r-tree according to search_flag recursively
+
+   NOTES
+     Used in maria_rtree_find_first() and maria_rtree_find_next()
+
+   RETURN
+     -1	 Error
+     0   Found
+     1   Not found
+*/
+
+static int maria_rtree_find_req(MARIA_HA *info, MARIA_KEYDEF *keyinfo, uint search_flag,
+			  uint nod_cmp_flag, my_off_t page, int level)
+{
+  uchar *k;
+  uchar *last;
+  uint nod_flag;
+  int res;
+  uchar *page_buf;
+  int k_len;
+  uint *saved_key = (uint*) (info->maria_rtree_recursion_state) + level;
+
+  if (!(page_buf = (uchar*)my_alloca((uint)keyinfo->block_length)))
+  {
+    my_errno = HA_ERR_OUT_OF_MEM;
+    return -1;
+  }
+  if (!_ma_fetch_keypage(info, keyinfo, page, DFLT_INIT_HITS, page_buf, 0))
+    goto err1;
+  nod_flag = _ma_test_if_nod(page_buf);
+
+  k_len = keyinfo->keylength - info->s->base.rec_reflength;
+
+  if(info->maria_rtree_recursion_depth >= level)
+  {
+    k = page_buf + *saved_key;
+  }
+  else
+  {
+    k = rt_PAGE_FIRST_KEY(page_buf, nod_flag);
+  }
+  last = rt_PAGE_END(page_buf);
+
+  for (; k < last; k = rt_PAGE_NEXT_KEY(k, k_len, nod_flag))
+  {
+    if (nod_flag)
+    {
+      /* this is an internal node in the tree */
+      if (!(res = maria_rtree_key_cmp(keyinfo->seg, info->first_mbr_key, k,
+                            info->last_rkey_length, nod_cmp_flag)))
+      {
+        switch ((res = maria_rtree_find_req(info, keyinfo, search_flag, nod_cmp_flag,
+                                      _ma_kpos(nod_flag, k), level + 1)))
+        {
+          case 0: /* found - exit from recursion */
+            *saved_key = k - page_buf;
+            goto ok;
+          case 1: /* not found - continue searching */
+            info->maria_rtree_recursion_depth = level;
+            break;
+          default: /* error */
+          case -1:
+            goto err1;
+        }
+      }
+    }
+    else
+    {
+      /* this is a leaf */
+      if (!maria_rtree_key_cmp(keyinfo->seg, info->first_mbr_key, k,
+                         info->last_rkey_length, search_flag))
+      {
+        uchar *after_key = rt_PAGE_NEXT_KEY(k, k_len, nod_flag);
+        info->lastpos = _ma_dpos(info, 0, after_key);
+        info->lastkey_length = k_len + info->s->base.rec_reflength;
+        memcpy(info->lastkey, k, info->lastkey_length);
+        info->maria_rtree_recursion_depth = level;
+        *saved_key = last - page_buf;
+
+        if (after_key < last)
+        {
+          info->int_keypos = info->buff;
+          info->int_maxpos = info->buff + (last - after_key);
+          memcpy(info->buff, after_key, last - after_key);
+          info->buff_used = 0;
+        }
+        else
+        {
+	  info->buff_used = 1;
+        }
+
+        res = 0;
+        goto ok;
+      }
+    }
+  }
+  info->lastpos = HA_OFFSET_ERROR;
+  my_errno = HA_ERR_KEY_NOT_FOUND;
+  res = 1;
+
+ok:
+  my_afree((byte*)page_buf);
+  return res;
+
+err1:
+  my_afree((byte*)page_buf);
+  info->lastpos = HA_OFFSET_ERROR;
+  return -1;
+}
+
+
+/*
+  Find first key in r-tree according to search_flag condition
+
+  SYNOPSIS
+   maria_rtree_find_first()
+   info			Handler to MARIA file
+   uint keynr		Key number to use
+   key			Key to search for
+   key_length		Length of 'key'
+   search_flag		Bitmap of flags how to do the search
+
+  RETURN
+    -1  Error
+    0   Found
+    1   Not found
+*/
+
+int maria_rtree_find_first(MARIA_HA *info, uint keynr, uchar *key, uint key_length,
+                    uint search_flag)
+{
+  my_off_t root;
+  uint nod_cmp_flag;
+  MARIA_KEYDEF *keyinfo = info->s->keyinfo + keynr;
+
+  if ((root = info->s->state.key_root[keynr]) == HA_OFFSET_ERROR)
+  {
+    my_errno= HA_ERR_END_OF_FILE;
+    return -1;
+  }
+
+  /* Save searched key */
+  memcpy(info->first_mbr_key, key, keyinfo->keylength -
+	 info->s->base.rec_reflength);
+  info->last_rkey_length = key_length;
+
+  info->maria_rtree_recursion_depth = -1;
+  info->buff_used = 1;
+
+  nod_cmp_flag = ((search_flag & (MBR_EQUAL | MBR_WITHIN)) ?
+        MBR_WITHIN : MBR_INTERSECT);
+  return maria_rtree_find_req(info, keyinfo, search_flag, nod_cmp_flag, root, 0);
+}
+
+
+/*
+   Find next key in r-tree according to search_flag condition
+
+  SYNOPSIS
+   maria_rtree_find_next()
+   info			Handler to MARIA file
+   uint keynr		Key number to use
+   search_flag		Bitmap of flags how to do the search
+
+   RETURN
+     -1  Error
+     0   Found
+     1   Not found
+*/
+
+int maria_rtree_find_next(MARIA_HA *info, uint keynr, uint search_flag)
+{
+  my_off_t root;
+  uint nod_cmp_flag;
+  MARIA_KEYDEF *keyinfo = info->s->keyinfo + keynr;
+
+  if (info->update & HA_STATE_DELETED)
+    return maria_rtree_find_first(info, keynr, info->lastkey, info->lastkey_length,
+			    search_flag);
+
+  if (!info->buff_used)
+  {
+    uchar *key= info->int_keypos;
+
+    while (key < info->int_maxpos)
+    {
+      if (!maria_rtree_key_cmp(keyinfo->seg, info->first_mbr_key, key,
+                         info->last_rkey_length, search_flag))
+      {
+        uchar *after_key = key + keyinfo->keylength;
+
+        info->lastpos= _ma_dpos(info, 0, after_key);
+        memcpy(info->lastkey, key, info->lastkey_length);
+
+        if (after_key < info->int_maxpos)
+	  info->int_keypos= after_key;
+        else
+	  info->buff_used= 1;
+        return 0;
+      }
+      key+= keyinfo->keylength;
+    }
+  }
+  if ((root = info->s->state.key_root[keynr]) == HA_OFFSET_ERROR)
+  {
+    my_errno= HA_ERR_END_OF_FILE;
+    return -1;
+  }
+
+  nod_cmp_flag = ((search_flag & (MBR_EQUAL | MBR_WITHIN)) ?
+        MBR_WITHIN : MBR_INTERSECT);
+  return maria_rtree_find_req(info, keyinfo, search_flag, nod_cmp_flag, root, 0);
+}
+
+
+/*
+  Get next key in r-tree recursively
+
+  NOTES
+    Used in maria_rtree_get_first() and maria_rtree_get_next()
+
+  RETURN
+    -1  Error
+    0   Found
+    1   Not found
+*/
+
+static int maria_rtree_get_req(MARIA_HA *info, MARIA_KEYDEF *keyinfo, uint key_length,
+                         my_off_t page, int level)
+{
+  uchar *k;
+  uchar *last;
+  uint nod_flag;
+  int res;
+  uchar *page_buf;
+  uint k_len;
+  uint *saved_key = (uint*) (info->maria_rtree_recursion_state) + level;
+
+  if (!(page_buf = (uchar*)my_alloca((uint)keyinfo->block_length)))
+    return -1;
+  if (!_ma_fetch_keypage(info, keyinfo, page, DFLT_INIT_HITS, page_buf, 0))
+    goto err1;
+  nod_flag = _ma_test_if_nod(page_buf);
+
+  k_len = keyinfo->keylength - info->s->base.rec_reflength;
+
+  if(info->maria_rtree_recursion_depth >= level)
+  {
+    k = page_buf + *saved_key;
+    if (!nod_flag)
+    {
+      /* Only leaf pages contain data references. */
+      /* Need to check next key with data reference. */
+      k = rt_PAGE_NEXT_KEY(k, k_len, nod_flag);
+    }
+  }
+  else
+  {
+    k = rt_PAGE_FIRST_KEY(page_buf, nod_flag);
+  }
+  last = rt_PAGE_END(page_buf);
+
+  for (; k < last; k = rt_PAGE_NEXT_KEY(k, k_len, nod_flag))
+  {
+    if (nod_flag)
+    {
+      /* this is an internal node in the tree */
+      switch ((res = maria_rtree_get_req(info, keyinfo, key_length,
+                                  _ma_kpos(nod_flag, k), level + 1)))
+      {
+        case 0: /* found - exit from recursion */
+          *saved_key = k - page_buf;
+          goto ok;
+        case 1: /* not found - continue searching */
+          info->maria_rtree_recursion_depth = level;
+          break;
+        default:
+        case -1: /* error */
+          goto err1;
+      }
+    }
+    else
+    {
+      /* this is a leaf */
+      uchar *after_key = rt_PAGE_NEXT_KEY(k, k_len, nod_flag);
+      info->lastpos = _ma_dpos(info, 0, after_key);
+      info->lastkey_length = k_len + info->s->base.rec_reflength;
+      memcpy(info->lastkey, k, info->lastkey_length);
+
+      info->maria_rtree_recursion_depth = level;
+      *saved_key = k - page_buf;
+
+      if (after_key < last)
+      {
+        info->int_keypos = (uchar*)saved_key;
+        memcpy(info->buff, page_buf, keyinfo->block_length);
+        info->int_maxpos = rt_PAGE_END(info->buff);
+        info->buff_used = 0;
+      }
+      else
+      {
+	info->buff_used = 1;
+      }
+
+      res = 0;
+      goto ok;
+    }
+  }
+  info->lastpos = HA_OFFSET_ERROR;
+  my_errno = HA_ERR_KEY_NOT_FOUND;
+  res = 1;
+
+ok:
+  my_afree((byte*)page_buf);
+  return res;
+
+err1:
+  my_afree((byte*)page_buf);
+  info->lastpos = HA_OFFSET_ERROR;
+  return -1;
+}
+
+
+/*
+  Get first key in r-tree
+
+  RETURN
+    -1	Error
+    0	Found
+    1	Not found
+*/
+
+int maria_rtree_get_first(MARIA_HA *info, uint keynr, uint key_length)
+{
+  my_off_t root;
+  MARIA_KEYDEF *keyinfo = info->s->keyinfo + keynr;
+
+  if ((root = info->s->state.key_root[keynr]) == HA_OFFSET_ERROR)
+  {
+    my_errno= HA_ERR_END_OF_FILE;
+    return -1;
+  }
+
+  info->maria_rtree_recursion_depth = -1;
+  info->buff_used = 1;
+
+  return maria_rtree_get_req(info, &keyinfo[keynr], key_length, root, 0);
+}
+
+
+/*
+  Get next key in r-tree
+
+  RETURN
+    -1	Error
+    0	Found
+    1	Not found
+*/
+
+int maria_rtree_get_next(MARIA_HA *info, uint keynr, uint key_length)
+{
+  my_off_t root;
+  MARIA_KEYDEF *keyinfo = info->s->keyinfo + keynr;
+
+  if (!info->buff_used)
+  {
+    uint k_len = keyinfo->keylength - info->s->base.rec_reflength;
+    /* rt_PAGE_NEXT_KEY(info->int_keypos) */
+    uchar *key = info->buff + *(int*)info->int_keypos + k_len +
+                 info->s->base.rec_reflength;
+    /* rt_PAGE_NEXT_KEY(key) */
+    uchar *after_key = key + k_len + info->s->base.rec_reflength;
+
+    info->lastpos = _ma_dpos(info, 0, after_key);
+    info->lastkey_length = k_len + info->s->base.rec_reflength;
+    memcpy(info->lastkey, key, k_len + info->s->base.rec_reflength);
+
+    *(int*)info->int_keypos = key - info->buff;
+    if (after_key >= info->int_maxpos)
+    {
+      info->buff_used = 1;
+    }
+
+    return 0;
+  }
+  else
+  {
+    if ((root = info->s->state.key_root[keynr]) == HA_OFFSET_ERROR)
+    {
+      my_errno= HA_ERR_END_OF_FILE;
+      return -1;
+    }
+
+    return maria_rtree_get_req(info, &keyinfo[keynr], key_length, root, 0);
+  }
+}
+
+
+/*
+  Choose non-leaf better key for insertion
+*/
+
+#ifdef PICK_BY_PERIMETER
+static uchar *maria_rtree_pick_key(MARIA_HA *info, MARIA_KEYDEF *keyinfo, uchar *key,
+			     uint key_length, uchar *page_buf, uint nod_flag)
+{
+  double increase;
+  double best_incr = DBL_MAX;
+  double perimeter;
+  double best_perimeter;
+  uchar *best_key;
+  uchar *k = rt_PAGE_FIRST_KEY(page_buf, nod_flag);
+  uchar *last = rt_PAGE_END(page_buf);
+
+  LINT_INIT(best_perimeter);
+  LINT_INIT(best_key);
+
+  for (; k < last; k = rt_PAGE_NEXT_KEY(k, key_length, nod_flag))
+  {
+    if ((increase = maria_rtree_perimeter_increase(keyinfo->seg, k, key, key_length,
+					     &perimeter)) == -1)
+      return NULL;
+    if ((increase < best_incr)||
+	(increase == best_incr && perimeter < best_perimeter))
+    {
+      best_key = k;
+      best_perimeter= perimeter;
+      best_incr = increase;
+    }
+  }
+  return best_key;
+}
+
+#endif /*PICK_BY_PERIMETER*/
+
+#ifdef PICK_BY_AREA
+static uchar *maria_rtree_pick_key(MARIA_HA *info, MARIA_KEYDEF *keyinfo, uchar *key,
+			     uint key_length, uchar *page_buf, uint nod_flag)
+{
+  double increase;
+  double best_incr = DBL_MAX;
+  double area;
+  double best_area;
+  uchar *best_key;
+  uchar *k = rt_PAGE_FIRST_KEY(page_buf, nod_flag);
+  uchar *last = rt_PAGE_END(page_buf);
+
+  LINT_INIT(best_area);
+  LINT_INIT(best_key);
+
+  for (; k < last; k = rt_PAGE_NEXT_KEY(k, key_length, nod_flag))
+  {
+    /* The following is safe as -1.0 is an exact number */
+    if ((increase = maria_rtree_area_increase(keyinfo->seg, k, key, key_length,
+                                        &area)) == -1.0)
+      return NULL;
+    /* The following should be safe, even if we compare doubles */
+    if (increase < best_incr)
+    {
+      best_key = k;
+      best_area = area;
+      best_incr = increase;
+    }
+    else
+    {
+      /* The following should be safe, even if we compare doubles */
+      if ((increase == best_incr) && (area < best_area))
+      {
+        best_key = k;
+        best_area = area;
+        best_incr = increase;
+      }
+    }
+  }
+  return best_key;
+}
+
+#endif /*PICK_BY_AREA*/
+
+/*
+  Go down and insert key into tree
+
+  RETURN
+    -1	Error
+    0	Child was not split
+    1	Child was split
+*/
+
+static int maria_rtree_insert_req(MARIA_HA *info, MARIA_KEYDEF *keyinfo, uchar *key,
+                            uint key_length, my_off_t page, my_off_t *new_page,
+                            int ins_level, int level)
+{
+  uchar *k;
+  uint nod_flag;
+  uchar *page_buf;
+  int res;
+
+  if (!(page_buf = (uchar*)my_alloca((uint)keyinfo->block_length +
+                                     HA_MAX_KEY_BUFF)))
+  {
+    my_errno = HA_ERR_OUT_OF_MEM;
+    return -1;
+  }
+  if (!_ma_fetch_keypage(info, keyinfo, page, DFLT_INIT_HITS, page_buf, 0))
+    goto err1;
+  nod_flag = _ma_test_if_nod(page_buf);
+
+  if ((ins_level == -1 && nod_flag) ||       /* key: go down to leaf */
+      (ins_level > -1 && ins_level > level)) /* branch: go down to ins_level */
+  {
+    if ((k = maria_rtree_pick_key(info, keyinfo, key, key_length, page_buf,
+                             nod_flag)) == NULL)
+      goto err1;
+    switch ((res = maria_rtree_insert_req(info, keyinfo, key, key_length,
+                     _ma_kpos(nod_flag, k), new_page, ins_level, level + 1)))
+    {
+      case 0: /* child was not split */
+      {
+        maria_rtree_combine_rect(keyinfo->seg, k, key, k, key_length);
+        if (_ma_write_keypage(info, keyinfo, page, DFLT_INIT_HITS, page_buf))
+          goto err1;
+        goto ok;
+      }
+      case 1: /* child was split */
+      {
+        uchar *new_key = page_buf + keyinfo->block_length + nod_flag;
+        /* set proper MBR for key */
+        if (maria_rtree_set_key_mbr(info, keyinfo, k, key_length,
+                            _ma_kpos(nod_flag, k)))
+          goto err1;
+        /* add new key for new page */
+        _ma_kpointer(info, new_key - nod_flag, *new_page);
+        if (maria_rtree_set_key_mbr(info, keyinfo, new_key, key_length, *new_page))
+          goto err1;
+        res = maria_rtree_add_key(info, keyinfo, new_key, key_length,
+                           page_buf, new_page);
+        if (_ma_write_keypage(info, keyinfo, page, DFLT_INIT_HITS, page_buf))
+          goto err1;
+        goto ok;
+      }
+      default:
+      case -1: /* error */
+      {
+        goto err1;
+      }
+    }
+  }
+  else
+  {
+    res = maria_rtree_add_key(info, keyinfo, key, key_length, page_buf, new_page);
+    if (_ma_write_keypage(info, keyinfo, page, DFLT_INIT_HITS, page_buf))
+      goto err1;
+    goto ok;
+  }
+
+ok:
+  my_afree((byte*)page_buf);
+  return res;
+
+err1:
+  my_afree((byte*)page_buf);
+  return -1;
+}
+
+
+/*
+  Insert key into the tree
+
+  RETURN
+    -1	Error
+    0	Root was not split
+    1	Root was split
+*/
+
+static int maria_rtree_insert_level(MARIA_HA *info, uint keynr, uchar *key,
+                             uint key_length, int ins_level)
+{
+  my_off_t old_root;
+  MARIA_KEYDEF *keyinfo = info->s->keyinfo + keynr;
+  int res;
+  my_off_t new_page;
+
+  if ((old_root = info->s->state.key_root[keynr]) == HA_OFFSET_ERROR)
+  {
+    int res;
+
+    if ((old_root = _ma_new(info, keyinfo, DFLT_INIT_HITS)) == HA_OFFSET_ERROR)
+      return -1;
+    info->buff_used = 1;
+    maria_putint(info->buff, 2, 0);
+    res = maria_rtree_add_key(info, keyinfo, key, key_length, info->buff, NULL);
+    if (_ma_write_keypage(info, keyinfo, old_root, DFLT_INIT_HITS, info->buff))
+      return 1;
+    info->s->state.key_root[keynr] = old_root;
+    return res;
+  }
+
+  switch ((res = maria_rtree_insert_req(info, keyinfo, key, key_length,
+                                  old_root, &new_page, ins_level, 0)))
+  {
+    case 0: /* root was not split */
+    {
+      break;
+    }
+    case 1: /* root was split, grow a new root */
+    {
+      uchar *new_root_buf;
+      my_off_t new_root;
+      uchar *new_key;
+      uint nod_flag = info->s->base.key_reflength;
+
+      if (!(new_root_buf = (uchar*)my_alloca((uint)keyinfo->block_length +
+                                             HA_MAX_KEY_BUFF)))
+      {
+        my_errno = HA_ERR_OUT_OF_MEM;
+        return -1;
+      }
+
+      maria_putint(new_root_buf, 2, nod_flag);
+      if ((new_root = _ma_new(info, keyinfo, DFLT_INIT_HITS)) ==
+	  HA_OFFSET_ERROR)
+        goto err1;
+
+      new_key = new_root_buf + keyinfo->block_length + nod_flag;
+
+      _ma_kpointer(info, new_key - nod_flag, old_root);
+      if (maria_rtree_set_key_mbr(info, keyinfo, new_key, key_length, old_root))
+        goto err1;
+      if (maria_rtree_add_key(info, keyinfo, new_key, key_length, new_root_buf, NULL)
+          == -1)
+        goto err1;
+      _ma_kpointer(info, new_key - nod_flag, new_page);
+      if (maria_rtree_set_key_mbr(info, keyinfo, new_key, key_length, new_page))
+        goto err1;
+      if (maria_rtree_add_key(info, keyinfo, new_key, key_length, new_root_buf, NULL)
+          == -1)
+        goto err1;
+      if (_ma_write_keypage(info, keyinfo, new_root,
+                            DFLT_INIT_HITS, new_root_buf))
+        goto err1;
+      info->s->state.key_root[keynr] = new_root;
+
+      my_afree((byte*)new_root_buf);
+      break;
+err1:
+      my_afree((byte*)new_root_buf);
+      return -1;
+    }
+    default:
+    case -1: /* error */
+    {
+      break;
+    }
+  }
+  return res;
+}
+
+
+/*
+  Insert key into the tree - interface function
+
+  RETURN
+    -1	Error
+    0	OK
+*/
+
+int maria_rtree_insert(MARIA_HA *info, uint keynr, uchar *key, uint key_length)
+{
+  return (!key_length ||
+	  (maria_rtree_insert_level(info, keynr, key, key_length, -1) == -1)) ? -1 : 0;
+}
+
+
+/*
+  Fill reinsert page buffer
+
+  RETURN
+    -1	Error
+    0	OK
+*/
+
+static int maria_rtree_fill_reinsert_list(stPageList *ReinsertList, my_off_t page,
+                                    int level)
+{
+  if (ReinsertList->n_pages == ReinsertList->m_pages)
+  {
+    ReinsertList->m_pages += REINSERT_BUFFER_INC;
+    if (!(ReinsertList->pages = (stPageLevel*)my_realloc((gptr)ReinsertList->pages,
+      ReinsertList->m_pages * sizeof(stPageLevel), MYF(MY_ALLOW_ZERO_PTR))))
+      goto err1;
+  }
+  /* save page to ReinsertList */
+  ReinsertList->pages[ReinsertList->n_pages].offs = page;
+  ReinsertList->pages[ReinsertList->n_pages].level = level;
+  ReinsertList->n_pages++;
+  return 0;
+
+err1:
+  return -1;
+}
+
+
+/*
+  Go down and delete key from the tree
+
+  RETURN
+    -1	Error
+    0	Deleted
+    1	Not found
+    2	Empty leaf
+*/
+
+static int maria_rtree_delete_req(MARIA_HA *info, MARIA_KEYDEF *keyinfo, uchar *key,
+                           uint key_length, my_off_t page, uint *page_size,
+                           stPageList *ReinsertList, int level)
+{
+  uchar *k;
+  uchar *last;
+  ulong i;
+  uint nod_flag;
+  uchar *page_buf;
+  int res;
+
+  if (!(page_buf = (uchar*)my_alloca((uint)keyinfo->block_length)))
+  {
+    my_errno = HA_ERR_OUT_OF_MEM;
+    return -1;
+  }
+  if (!_ma_fetch_keypage(info, keyinfo, page, DFLT_INIT_HITS, page_buf, 0))
+    goto err1;
+  nod_flag = _ma_test_if_nod(page_buf);
+
+  k = rt_PAGE_FIRST_KEY(page_buf, nod_flag);
+  last = rt_PAGE_END(page_buf);
+
+  for (i = 0; k < last; k = rt_PAGE_NEXT_KEY(k, key_length, nod_flag), ++i)
+  {
+    if (nod_flag)
+    {
+      /* not leaf */
+      if (!maria_rtree_key_cmp(keyinfo->seg, key, k, key_length, MBR_WITHIN))
+      {
+        switch ((res = maria_rtree_delete_req(info, keyinfo, key, key_length,
+                  _ma_kpos(nod_flag, k), page_size, ReinsertList, level + 1)))
+        {
+          case 0: /* deleted */
+          {
+            /* test page filling */
+            if (*page_size + key_length >= rt_PAGE_MIN_SIZE(keyinfo->block_length))
+            {
+              /* OK */
+              if (maria_rtree_set_key_mbr(info, keyinfo, k, key_length,
+                                  _ma_kpos(nod_flag, k)))
+                goto err1;
+              if (_ma_write_keypage(info, keyinfo, page,
+                                    DFLT_INIT_HITS, page_buf))
+                goto err1;
+            }
+            else
+            {
+              /* too small: delete key & add it descendant to reinsert list */
+              if (maria_rtree_fill_reinsert_list(ReinsertList, _ma_kpos(nod_flag, k),
+                                           level + 1))
+                goto err1;
+              maria_rtree_delete_key(info, page_buf, k, key_length, nod_flag);
+              if (_ma_write_keypage(info, keyinfo, page,
+                                    DFLT_INIT_HITS, page_buf))
+                goto err1;
+              *page_size = maria_getint(page_buf);
+            }
+
+            goto ok;
+          }
+          case 1: /* not found - continue searching */
+          {
+            break;
+          }
+          case 2: /* vacuous case: last key in the leaf */
+          {
+            maria_rtree_delete_key(info, page_buf, k, key_length, nod_flag);
+            if (_ma_write_keypage(info, keyinfo, page,
+                                  DFLT_INIT_HITS, page_buf))
+              goto err1;
+            *page_size = maria_getint(page_buf);
+            res = 0;
+            goto ok;
+          }
+          default: /* error */
+          case -1:
+          {
+            goto err1;
+          }
+        }
+      }
+    }
+    else
+    {
+      /* leaf */
+      if (!maria_rtree_key_cmp(keyinfo->seg, key, k, key_length, MBR_EQUAL | MBR_DATA))
+      {
+        maria_rtree_delete_key(info, page_buf, k, key_length, nod_flag);
+        *page_size = maria_getint(page_buf);
+        if (*page_size == 2)
+        {
+          /* last key in the leaf */
+          res = 2;
+          if (_ma_dispose(info, keyinfo, page, DFLT_INIT_HITS))
+            goto err1;
+        }
+        else
+        {
+          res = 0;
+          if (_ma_write_keypage(info, keyinfo, page, DFLT_INIT_HITS, page_buf))
+            goto err1;
+        }
+        goto ok;
+      }
+    }
+  }
+  res = 1;
+
+ok:
+  my_afree((byte*)page_buf);
+  return res;
+
+err1:
+  my_afree((byte*)page_buf);
+  return -1;
+}
+
+
+/*
+  Delete key - interface function
+
+  RETURN
+    -1	Error
+    0	Deleted
+*/
+
+int maria_rtree_delete(MARIA_HA *info, uint keynr, uchar *key, uint key_length)
+{
+  uint page_size;
+  stPageList ReinsertList;
+  my_off_t old_root;
+  MARIA_KEYDEF *keyinfo = info->s->keyinfo + keynr;
+
+  if ((old_root = info->s->state.key_root[keynr]) == HA_OFFSET_ERROR)
+  {
+    my_errno= HA_ERR_END_OF_FILE;
+    return -1;
+  }
+
+  ReinsertList.pages = NULL;
+  ReinsertList.n_pages = 0;
+  ReinsertList.m_pages = 0;
+
+  switch (maria_rtree_delete_req(info, keyinfo, key, key_length, old_root,
+                                 &page_size, &ReinsertList, 0))
+  {
+    case 2:
+    {
+      info->s->state.key_root[keynr] = HA_OFFSET_ERROR;
+      return 0;
+    }
+    case 0:
+    {
+      uint nod_flag;
+      ulong i;
+      for (i = 0; i < ReinsertList.n_pages; ++i)
+      {
+        uchar *page_buf;
+        uint nod_flag;
+        uchar *k;
+        uchar *last;
+
+        if (!(page_buf = (uchar*)my_alloca((uint)keyinfo->block_length)))
+        {
+          my_errno = HA_ERR_OUT_OF_MEM;
+          goto err1;
+        }
+        if (!_ma_fetch_keypage(info, keyinfo, ReinsertList.pages[i].offs,
+                               DFLT_INIT_HITS, page_buf, 0))
+          goto err1;
+        nod_flag = _ma_test_if_nod(page_buf);
+        k = rt_PAGE_FIRST_KEY(page_buf, nod_flag);
+        last = rt_PAGE_END(page_buf);
+        for (; k < last; k = rt_PAGE_NEXT_KEY(k, key_length, nod_flag))
+        {
+          if (maria_rtree_insert_level(info, keynr, k, key_length,
+                                 ReinsertList.pages[i].level) == -1)
+          {
+            my_afree((byte*)page_buf);
+            goto err1;
+          }
+        }
+        my_afree((byte*)page_buf);
+        if (_ma_dispose(info, keyinfo, ReinsertList.pages[i].offs,
+            DFLT_INIT_HITS))
+          goto err1;
+      }
+      if (ReinsertList.pages)
+        my_free((byte*) ReinsertList.pages, MYF(0));
+
+      /* check for redundant root (not leaf, 1 child) and eliminate */
+      if ((old_root = info->s->state.key_root[keynr]) == HA_OFFSET_ERROR)
+        goto err1;
+      if (!_ma_fetch_keypage(info, keyinfo, old_root, DFLT_INIT_HITS,
+                             info->buff, 0))
+        goto err1;
+      nod_flag = _ma_test_if_nod(info->buff);
+      page_size = maria_getint(info->buff);
+      if (nod_flag && (page_size == 2 + key_length + nod_flag))
+      {
+        my_off_t new_root = _ma_kpos(nod_flag,
+                                     rt_PAGE_FIRST_KEY(info->buff, nod_flag));
+        if (_ma_dispose(info, keyinfo, old_root, DFLT_INIT_HITS))
+          goto err1;
+        info->s->state.key_root[keynr] = new_root;
+      }
+      info->update= HA_STATE_DELETED;
+      return 0;
+
+err1:
+      return -1;
+    }
+    case 1: /* not found */
+    {
+      my_errno = HA_ERR_KEY_NOT_FOUND;
+      return -1;
+    }
+    default:
+    case -1: /* error */
+    {
+      return -1;
+    }
+  }
+}
+
+
+/*
+  Estimate number of suitable keys in the tree
+
+  RETURN
+    estimated value
+*/
+
+ha_rows maria_rtree_estimate(MARIA_HA *info, uint keynr, uchar *key,
+                       uint key_length, uint flag)
+{
+  MARIA_KEYDEF *keyinfo = info->s->keyinfo + keynr;
+  my_off_t root;
+  uint i = 0;
+  uchar *k;
+  uchar *last;
+  uint nod_flag;
+  uchar *page_buf;
+  uint k_len;
+  double area = 0;
+  ha_rows res = 0;
+
+  if (flag & MBR_DISJOINT)
+    return info->state->records;
+
+  if ((root = info->s->state.key_root[keynr]) == HA_OFFSET_ERROR)
+    return HA_POS_ERROR;
+  if (!(page_buf = (uchar*)my_alloca((uint)keyinfo->block_length)))
+    return HA_POS_ERROR;
+  if (!_ma_fetch_keypage(info, keyinfo, root, DFLT_INIT_HITS, page_buf, 0))
+    goto err1;
+  nod_flag = _ma_test_if_nod(page_buf);
+
+  k_len = keyinfo->keylength - info->s->base.rec_reflength;
+
+  k = rt_PAGE_FIRST_KEY(page_buf, nod_flag);
+  last = rt_PAGE_END(page_buf);
+
+  for (; k < last; k = rt_PAGE_NEXT_KEY(k, k_len, nod_flag), ++i)
+  {
+    if (nod_flag)
+    {
+      double k_area = maria_rtree_rect_volume(keyinfo->seg, k, key_length);
+
+      /* The following should be safe, even if we compare doubles */
+      if (k_area == 0)
+      {
+        if (flag & (MBR_CONTAIN | MBR_INTERSECT))
+        {
+          area += 1;
+        }
+        else if (flag & (MBR_WITHIN | MBR_EQUAL))
+        {
+          if (!maria_rtree_key_cmp(keyinfo->seg, key, k, key_length, MBR_WITHIN))
+            area += 1;
+        }
+        else
+          goto err1;
+      }
+      else
+      {
+        if (flag & (MBR_CONTAIN | MBR_INTERSECT))
+        {
+          area += maria_rtree_overlapping_area(keyinfo->seg, key, k, key_length) /
+                  k_area;
+        }
+        else if (flag & (MBR_WITHIN | MBR_EQUAL))
+        {
+          if (!maria_rtree_key_cmp(keyinfo->seg, key, k, key_length, MBR_WITHIN))
+            area += maria_rtree_rect_volume(keyinfo->seg, key, key_length) /
+                    k_area;
+        }
+        else
+          goto err1;
+      }
+    }
+    else
+    {
+      if (!maria_rtree_key_cmp(keyinfo->seg, key, k, key_length, flag))
+        ++res;
+    }
+  }
+  if (nod_flag)
+  {
+    if (i)
+      res = (ha_rows) (area / i * info->state->records);
+    else
+      res = HA_POS_ERROR;
+  }
+
+  my_afree((byte*)page_buf);
+  return res;
+
+err1:
+  my_afree((byte*)page_buf);
+  return HA_POS_ERROR;
+}
+
+#endif /*HAVE_RTREE_KEYS*/