This ChangeSet adds RTREE support into myisam library.

RTREEs will be used for GIS extension in MySQL


myisam/.cvsignore:
  Added sp_test and rt_test
myisam/Makefile.am:
  Added RTREE files
myisam/mi_create.c:
  Added RTREE/SPATIAL initialization
myisam/mi_delete.c:
  Switched to use virual function, instead of mi_ck_delete() direct call
myisam/mi_key.c:
  Added sp_make_key() call in the case of SPATIAL index type
myisam/mi_open.c:
  Added some new initialization actions which depend on key_alg being used: RTREE or BTREE
myisam/mi_range.c:
  Rtree estimation
myisam/mi_rkey.c:
  rtree
myisam/mi_rnext.c:
  rtree
myisam/mi_rnext_same.c:
  rtree
myisam/mi_static.c:
  New search flags for bounding rectungles
myisam/mi_test1.c:
  one now should always specify key_alg during keyinfo initializing: BTREE or RTREE
myisam/mi_test2.c:
  Added key_alg initializing
myisam/mi_test3.c:
  Added key_alg initialization
myisam/mi_update.c:
  Switched to virtual functions, instead of mi_ck_delete/mi_ck_write direct call
myisam/mi_write.c:
  Virtual function instead of mi_ck_write() direct call
myisam/myisamdef.h:
  Rtree additions

1 files changed, 154 insertions, 0 deletions

diff --git a/myisam/rt_key.c b/myisam/rt_key.c
new file mode 100644
index 00000000000..c08e918c6db
--- /dev/null
+++ b/myisam/rt_key.c
@@ -0,0 +1,154 @@
+/* Copyright (C) 2000 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 "myisamdef.h"
+
+#include "rt_index.h"
+#include "rt_key.h"
+#include "rt_mbr.h"
+
+/*
+Add key to the page
+Result values:
+-1 - error
+ 0 - not split
+ 1 - split
+*/
+int rtree_add_key(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *key, 
+                 uint key_length, uchar *page_buf, my_off_t *new_page)
+{
+  uint page_size = mi_getint(page_buf);
+  uint nod_flag = mi_test_if_nod(page_buf);
+
+  if (page_size + key_length + nod_flag <= keyinfo->block_length)  
+  {
+    /* split won't be necessary */
+    if (nod_flag)
+    {
+      /* save key */
+      memcpy(rt_PAGE_END(page_buf), key - nod_flag, key_length + nod_flag); 
+      page_size += key_length + nod_flag;
+    }
+    else
+    {
+      /* save key */
+      memcpy(rt_PAGE_END(page_buf), key, key_length + 
+                                         info->s->base.rec_reflength);
+      page_size += key_length + info->s->base.rec_reflength;
+    }
+    mi_putint(page_buf, page_size, nod_flag);
+    return 0;
+  }
+  else
+  { 
+    if (rtree_split_page(info, keyinfo, page_buf, key, key_length, new_page))
+      return -1;
+    else 
+      return 1;
+  }
+}
+
+/*
+Delete key from the page
+*/
+int rtree_delete_key(MI_INFO *info, uchar *page_buf, uchar *key, 
+                    uint key_length, uint nod_flag)
+{
+  uint16 page_size = mi_getint(page_buf);
+  uchar *key_start;
+
+  if (nod_flag)
+  {
+    key_start = key - nod_flag;
+  }
+  else
+  {
+    key_start = key;
+    key_length += info->s->base.rec_reflength;
+  }
+  memmove(key_start, key + key_length, page_size - key_length - 
+                                       (key - page_buf));
+  page_size -= key_length + nod_flag;
+
+  mi_putint(page_buf, page_size, nod_flag);
+
+  return 0;
+}
+
+/*
+Calculate and store key MBR
+*/
+int rtree_set_key_mbr(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *key, 
+                    uint key_length, my_off_t child_page)
+{
+  uchar *k;
+  uchar *last;
+  uint nod_flag;
+
+  if (!_mi_fetch_keypage(info, keyinfo, child_page, info->buff, 0))
+    goto err1;
+  nod_flag = mi_test_if_nod(info->buff);
+
+  k = rt_PAGE_FIRST_KEY(info->buff, nod_flag);
+  last = rt_PAGE_END(info->buff);
+
+  rtree_page_mbr(info, keyinfo->seg, info->buff, key, key_length);
+
+  return 0;
+
+err1:
+  return -1;
+}
+
+/*
+Choose non-leaf better key for insertion
+*/
+uchar *rtree_choose_key(MI_INFO *info, MI_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);
+
+  for (; k < last; k = rt_PAGE_NEXT_KEY(k, key_length, nod_flag))
+  {
+    if ((increase = rtree_area_increase(keyinfo->seg, key, k, key_length, 
+                                        &area)) == -1)
+      return NULL;
+    if (increase < best_incr)
+    {
+      best_key = k;
+      best_area = area;
+      best_incr = increase;
+    }
+    else
+    {
+      if ((increase == best_incr) && (area < best_area))
+      {
+        best_key = k;
+        best_area = area;
+        best_incr = increase;
+      }
+    }
+  }
+  return best_key;
+}