Merging

8 files changed, 405 insertions, 280 deletions

diff --git a/myisam/rt_index.c b/myisam/rt_index.c
index 6a2606a1f8e..4fffd848624 100644
--- a/myisam/rt_index.c
+++ b/myisam/rt_index.c
@@ -24,6 +24,8 @@
 #include "rt_mbr.h"
 
 #define REINSERT_BUFFER_INC 10
+#define PICK_BY_AREA
+/*#define PICK_BY_PERIMETER*/
 
 typedef struct st_page_level
 {
@@ -439,6 +441,84 @@ int rtree_get_next(MI_INFO *info, uint keynr, uint key_length)
 
 
 /*
+  Choose non-leaf better key for insertion
+*/
+
+#ifdef PICK_BY_PERIMETER
+static uchar *rtree_pick_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 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 = 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 *rtree_pick_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);
+
+  LINT_INIT(best_area);
+  LINT_INIT(best_key);
+
+  for (; k < last; k = rt_PAGE_NEXT_KEY(k, key_length, nod_flag))
+  {
+    if ((increase = rtree_area_increase(keyinfo->seg, k, key, 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;
+}
+
+#endif /*PICK_BY_AREA*/
+
+/*
   Go down and insert key into tree
 
   RETURN
@@ -469,7 +549,7 @@ static int rtree_insert_req(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *key,
   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 = rtree_choose_key(info, keyinfo, key, key_length, page_buf, 
+    if ((k = rtree_pick_key(info, keyinfo, key, key_length, page_buf, 
                              nod_flag)) == NULL)
       goto err1;
     switch ((res = rtree_insert_req(info, keyinfo, key, key_length, 
@@ -579,7 +659,7 @@ static int rtree_insert_level(MI_INFO *info, uint keynr, uchar *key,
 
       mi_putint(new_root_buf, 2, nod_flag);
       if ((new_root = _mi_new(info, keyinfo, DFLT_INIT_HITS)) ==
-                                                             HA_OFFSET_ERROR)
+	  HA_OFFSET_ERROR)
         goto err1;
 
       new_key = new_root_buf + keyinfo->block_length + nod_flag;
diff --git a/myisam/rt_index.h b/myisam/rt_index.h
index 1a24c403043..d3fcd934719 100644
--- a/myisam/rt_index.h
+++ b/myisam/rt_index.h
@@ -25,7 +25,7 @@
               (nod_flag ? nod_flag : info->s->base.rec_reflength))
 #define rt_PAGE_END(page) (page + mi_getint(page))
 
-#define rt_PAGE_MIN_SIZE(block_length) ((uint)(block_length) / 2)
+#define rt_PAGE_MIN_SIZE(block_length) ((uint)(block_length) / 3)
 
 int rtree_insert(MI_INFO *info, uint keynr, uchar *key, uint key_length);
 int rtree_delete(MI_INFO *info, uint keynr, uchar *key, uint key_length);
diff --git a/myisam/rt_key.c b/myisam/rt_key.c
index e05bb744cc1..e2a402fbefd 100644
--- a/myisam/rt_key.c
+++ b/myisam/rt_key.c
@@ -36,7 +36,8 @@ int rtree_add_key(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *key,
   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)  
+  if (page_size + key_length + info->s->base.rec_reflength <=
+      keyinfo->block_length)
   {
     /* split won't be necessary */
     if (nod_flag)
@@ -96,47 +97,4 @@ int rtree_set_key_mbr(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *key,
   return rtree_page_mbr(info, keyinfo->seg, info->buff, key, key_length);
 }
 
-
-/*
-  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);
-
-  LINT_INIT(best_area);
-  LINT_INIT(best_key);
-
-  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;
-}
-
 #endif /*HAVE_RTREE_KEYS*/
diff --git a/myisam/rt_key.h b/myisam/rt_key.h
index 92e10d04783..df4f8aa03a2 100644
--- a/myisam/rt_key.h
+++ b/myisam/rt_key.h
@@ -28,7 +28,6 @@ int rtree_delete_key(MI_INFO *info, uchar *page, uchar *key,
                     uint key_length, uint nod_flag);
 int rtree_set_key_mbr(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *key, 
                     uint key_length, my_off_t child_page);
-uchar *rtree_choose_key(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *key, 
-                       uint key_length, uchar *page_buf, uint nod_flag);
+
 #endif /*HAVE_RTREE_KEYS*/
 #endif /* _rt_key_h */
diff --git a/myisam/rt_mbr.c b/myisam/rt_mbr.c
index c7864228e08..09ec3f5e50a 100644
--- a/myisam/rt_mbr.c
+++ b/myisam/rt_mbr.c
@@ -26,7 +26,7 @@
 #define CONTAIN_CMP(amin, amax, bmin, bmax) ((bmin > amin)  || (bmax <  amax))
 #define WITHIN_CMP(amin, amax, bmin, bmax) ((amin > bmin)  || (amax <  bmax))
 #define DISJOINT_CMP(amin, amax, bmin, bmax) ((amin <= bmax) && (bmin <= amax))
-#define EQUAL_CMP(amix, amax, bmin, bmax) ((amix != bmin) || (amax != bmax))
+#define EQUAL_CMP(amin, amax, bmin, bmax) ((amin != bmin) || (amax != bmax))
 
 #define FCMP(A, B) ((int)(A) - (int)(B))
 #define p_inc(A, B, X)  {A += X; B += X;}
@@ -63,12 +63,9 @@
   type amin, amax, bmin, bmax; \
   amin = korr_func(a); \
   bmin = korr_func(b); \
-  p_inc(a, b, len); \
-  amax = korr_func(a); \
-  bmax = korr_func(b); \
+  amax = korr_func(a+len); \
+  bmax = korr_func(b+len); \
   RT_CMP(nextflag); \
-  p_inc(a, b, len); \
-  break; \
 }
 
 #define RT_CMP_GET(type, get_func, len, nextflag) \
@@ -76,12 +73,9 @@
   type amin, amax, bmin, bmax; \
   get_func(amin, a); \
   get_func(bmin, b); \
-  p_inc(a, b, len); \
-  get_func(amax, a); \
-  get_func(bmax, b); \
+  get_func(amax, a+len); \
+  get_func(bmax, b+len); \
   RT_CMP(nextflag); \
-  p_inc(a, b, len); \
-  break; \
 }
 
 /*
@@ -100,54 +94,54 @@ int rtree_key_cmp(HA_KEYSEG *keyseg, uchar *b, uchar *a, uint key_length,
 {
   for (; (int) key_length > 0; keyseg += 2 )
   {
-    key_length -= keyseg->length * 2;
-
     switch ((enum ha_base_keytype) keyseg->type) {
-    case HA_KEYTYPE_TEXT:
+    case HA_KEYTYPE_INT8:
+      RT_CMP_KORR(int8, mi_sint1korr, 1, nextflag);
+      break;
     case HA_KEYTYPE_BINARY:
-    case HA_KEYTYPE_VARTEXT:
-    case HA_KEYTYPE_VARBINARY:
-    case HA_KEYTYPE_NUM:
-    default:
-      return 1;
+      RT_CMP_KORR(uint8, mi_uint1korr, 1, nextflag);
       break;
-    case HA_KEYTYPE_INT8:
-      {
-        int amin,amax,bmin,bmax;
-        amin = (int)*((signed char *)a);
-        bmin = (int)*((signed char *)b);
-        p_inc(a, b, 1);
-        amax = (int)*((signed char *)a);
-        bmax = (int)*((signed char *)b);
-        RT_CMP(nextflag);
-        p_inc(a, b, 1);
-        break;
-      }
     case HA_KEYTYPE_SHORT_INT:
       RT_CMP_KORR(int16, mi_sint2korr, 2, nextflag);
+      break;
     case HA_KEYTYPE_USHORT_INT:
       RT_CMP_KORR(uint16, mi_uint2korr, 2, nextflag);
+      break;
     case HA_KEYTYPE_INT24:
       RT_CMP_KORR(int32, mi_sint3korr, 3, nextflag);
+      break;
     case HA_KEYTYPE_UINT24:
       RT_CMP_KORR(uint32, mi_uint3korr, 3, nextflag);
+      break;
     case HA_KEYTYPE_LONG_INT:
       RT_CMP_KORR(int32, mi_sint4korr, 4, nextflag);
+      break;
     case HA_KEYTYPE_ULONG_INT:
       RT_CMP_KORR(uint32, mi_uint4korr, 4, nextflag);
+      break;
 #ifdef HAVE_LONG_LONG
     case HA_KEYTYPE_LONGLONG:
       RT_CMP_KORR(longlong, mi_sint8korr, 8, nextflag)
+      break;
     case HA_KEYTYPE_ULONGLONG:
       RT_CMP_KORR(ulonglong, mi_uint8korr, 8, nextflag)
+      break;
 #endif
     case HA_KEYTYPE_FLOAT:
       RT_CMP_GET(float, mi_float4get, 4, nextflag);
+      break;
     case HA_KEYTYPE_DOUBLE:
       RT_CMP_GET(double, mi_float8get, 8, nextflag);
+      break;
     case HA_KEYTYPE_END:
       goto end;
+    default:
+      return 1;
     }
+    uint32 keyseg_length= keyseg->length * 2;
+    key_length-= keyseg_length;
+    a+= keyseg_length;
+    b+= keyseg_length;
   }
 
 end:
@@ -167,22 +161,16 @@ end:
 { \
   type amin, amax; \
   amin = korr_func(a); \
-  a += len; \
-  amax = korr_func(a); \
-  a += len; \
+  amax = korr_func(a+len); \
   res *= (cast(amax) - cast(amin)); \
-  break; \
 }
 
 #define RT_VOL_GET(type, get_func, len, cast) \
 { \
   type amin, amax; \
   get_func(amin, a); \
-  a += len; \
-  get_func(amax, a); \
-  a += len; \
+  get_func(amax, a+len); \
   res *= (cast(amax) - cast(amin)); \
-  break; \
 }
 
 /*
@@ -193,53 +181,54 @@ double rtree_rect_volume(HA_KEYSEG *keyseg, uchar *a, uint key_length)
   double res = 1;
   for (; (int)key_length > 0; keyseg += 2)
   {
-    key_length -= keyseg->length * 2;
-    
     switch ((enum ha_base_keytype) keyseg->type) {
-    case HA_KEYTYPE_TEXT:
+    case HA_KEYTYPE_INT8:
+      RT_VOL_KORR(int8, mi_sint1korr, 1, (double));
+      break;
     case HA_KEYTYPE_BINARY:
-    case HA_KEYTYPE_VARTEXT:
-    case HA_KEYTYPE_VARBINARY:
-    case HA_KEYTYPE_NUM:
-    default:
-      return 1;
+      RT_VOL_KORR(uint8, mi_uint1korr, 1, (double));
       break;
-    case HA_KEYTYPE_INT8:
-      {
-        int amin, amax;
-        amin = (int)*((signed char *)a);
-        a += 1;
-        amax = (int)*((signed char *)a);
-        a += 1;
-        res *= ((double)amax - (double)amin);
-        break;
-      }
     case HA_KEYTYPE_SHORT_INT:
       RT_VOL_KORR(int16, mi_sint2korr, 2, (double));
+      break;
     case HA_KEYTYPE_USHORT_INT:
       RT_VOL_KORR(uint16, mi_uint2korr, 2, (double));
+      break;
     case HA_KEYTYPE_INT24:
       RT_VOL_KORR(int32, mi_sint3korr, 3, (double));
+      break;
     case HA_KEYTYPE_UINT24:
       RT_VOL_KORR(uint32, mi_uint3korr, 3, (double));
+      break;
     case HA_KEYTYPE_LONG_INT:
       RT_VOL_KORR(int32, mi_sint4korr, 4, (double));
+      break;
     case HA_KEYTYPE_ULONG_INT:
       RT_VOL_KORR(uint32, mi_uint4korr, 4, (double));
+      break;
 #ifdef HAVE_LONG_LONG
     case HA_KEYTYPE_LONGLONG:
       RT_VOL_KORR(longlong, mi_sint8korr, 8, (double));
+      break;
     case HA_KEYTYPE_ULONGLONG:
       RT_VOL_KORR(longlong, mi_sint8korr, 8, ulonglong2double);
+      break;
 #endif
     case HA_KEYTYPE_FLOAT:
       RT_VOL_GET(float, mi_float4get, 4, (double));
+      break;
     case HA_KEYTYPE_DOUBLE:
       RT_VOL_GET(double, mi_float8get, 8, (double));
+      break;
     case HA_KEYTYPE_END:
       key_length = 0;
       break;
+    default:
+      return -1;
     }
+    uint32 keyseg_length= keyseg->length * 2;
+    key_length-= keyseg_length;
+    a+= keyseg_length;
   }
   return res;
 }
@@ -248,24 +237,18 @@ double rtree_rect_volume(HA_KEYSEG *keyseg, uchar *a, uint key_length)
 { \
   type amin, amax; \
   amin = korr_func(a); \
-  a += len; \
-  amax = korr_func(a); \
-  a += len; \
+  amax = korr_func(a+len); \
   *res++ = cast(amin); \
   *res++ = cast(amax); \
-  break; \
 }
 
 #define RT_D_MBR_GET(type, get_func, len, cast) \
 { \
   type amin, amax; \
   get_func(amin, a); \
-  a += len; \
-  get_func(amax, a); \
-  a += len; \
+  get_func(amax, a+len); \
   *res++ = cast(amin); \
   *res++ = cast(amax); \
-  break; \
 }
 
 /*
@@ -275,54 +258,54 @@ int rtree_d_mbr(HA_KEYSEG *keyseg, uchar *a, uint key_length, double *res)
 {
   for (; (int)key_length > 0; keyseg += 2)
   {
-    key_length -= keyseg->length * 2;
-    
     switch ((enum ha_base_keytype) keyseg->type) {
-    case HA_KEYTYPE_TEXT:
+    case HA_KEYTYPE_INT8:
+      RT_D_MBR_KORR(int8, mi_sint1korr, 1, (double));
+      break;
     case HA_KEYTYPE_BINARY:
-    case HA_KEYTYPE_VARTEXT:
-    case HA_KEYTYPE_VARBINARY:
-    case HA_KEYTYPE_NUM:
-    default:
-      return 1;
+      RT_D_MBR_KORR(uint8, mi_uint1korr, 1, (double));
       break;
-    case HA_KEYTYPE_INT8:
-      {
-        int amin, amax;
-        amin = (int)*((signed char *)a);
-        a += 1;
-        amax = (int)*((signed char *)a);
-        a += 1;
-        *res++ = (double)amin;
-        *res++ = (double)amax;
-        break;
-      }
     case HA_KEYTYPE_SHORT_INT:
       RT_D_MBR_KORR(int16, mi_sint2korr, 2, (double));
+      break;
     case HA_KEYTYPE_USHORT_INT:
       RT_D_MBR_KORR(uint16, mi_uint2korr, 2, (double));
+      break;
     case HA_KEYTYPE_INT24:
       RT_D_MBR_KORR(int32, mi_sint3korr, 3, (double));
+      break;
     case HA_KEYTYPE_UINT24:
       RT_D_MBR_KORR(uint32, mi_uint3korr, 3, (double));
+      break;
     case HA_KEYTYPE_LONG_INT:
       RT_D_MBR_KORR(int32, mi_sint4korr, 4, (double));
+      break;
     case HA_KEYTYPE_ULONG_INT:
       RT_D_MBR_KORR(uint32, mi_uint4korr, 4, (double));
+      break;
 #ifdef HAVE_LONG_LONG
     case HA_KEYTYPE_LONGLONG:
       RT_D_MBR_KORR(longlong, mi_sint8korr, 8, (double));
+      break;
     case HA_KEYTYPE_ULONGLONG:
       RT_D_MBR_KORR(longlong, mi_sint8korr, 8, ulonglong2double);
+      break;
 #endif
     case HA_KEYTYPE_FLOAT:
       RT_D_MBR_GET(float, mi_float4get, 4, (double));
+      break;
     case HA_KEYTYPE_DOUBLE:
       RT_D_MBR_GET(double, mi_float8get, 8, (double));
+      break;
     case HA_KEYTYPE_END:
       key_length = 0;
       break;
+    default:
+      return 1;
     }
+    uint32 keyseg_length= keyseg->length * 2;
+    key_length-= keyseg_length;
+    a+= keyseg_length;
   }
   return 0;
 }
@@ -332,17 +315,12 @@ int rtree_d_mbr(HA_KEYSEG *keyseg, uchar *a, uint key_length, double *res)
   type amin, amax, bmin, bmax; \
   amin = korr_func(a); \
   bmin = korr_func(b); \
-  p_inc(a, b, len); \
-  amax = korr_func(a); \
-  bmax = korr_func(b); \
-  p_inc(a, b, len); \
+  amax = korr_func(a+len); \
+  bmax = korr_func(b+len); \
   amin = min(amin, bmin); \
   amax = max(amax, bmax); \
   store_func(c, amin); \
-  c += len; \
-  store_func(c, amax); \
-  c += len; \
-  break; \
+  store_func(c+len, amax); \
 }
 
 #define RT_COMB_GET(type, get_func, store_func, len) \
@@ -350,17 +328,12 @@ int rtree_d_mbr(HA_KEYSEG *keyseg, uchar *a, uint key_length, double *res)
   type amin, amax, bmin, bmax; \
   get_func(amin, a); \
   get_func(bmin, b); \
-  p_inc(a, b, len); \
-  get_func(amax, a); \
-  get_func(bmax, b); \
-  p_inc(a, b, len); \
+  get_func(amax, a+len); \
+  get_func(bmax, b+len); \
   amin = min(amin, bmin); \
   amax = max(amax, bmax); \
   store_func(c, amin); \
-  c += len; \
-  store_func(c, amax); \
-  c += len; \
-  break; \
+  store_func(c+len, amax); \
 }
 
 /*
@@ -372,62 +345,57 @@ int rtree_d_mbr(HA_KEYSEG *keyseg, uchar *a, uint key_length, double *res)
 int rtree_combine_rect(HA_KEYSEG *keyseg, uchar* a, uchar* b, uchar* c, 
 		       uint key_length)
 {
-
   for ( ; (int) key_length > 0 ; keyseg += 2)
   {
-    key_length -= keyseg->length * 2;
-    
     switch ((enum ha_base_keytype) keyseg->type) {
-    case HA_KEYTYPE_TEXT:
+    case HA_KEYTYPE_INT8:
+      RT_COMB_KORR(int8, mi_sint1korr, mi_int1store, 1);
+      break;
     case HA_KEYTYPE_BINARY:
-    case HA_KEYTYPE_VARTEXT:
-    case HA_KEYTYPE_VARBINARY:
-    case HA_KEYTYPE_NUM:
-    default:
-      return 1;
+      RT_COMB_KORR(uint8, mi_uint1korr, mi_int1store, 1);
       break;
-    case HA_KEYTYPE_INT8:
-      {
-        int amin, amax, bmin, bmax;
-        amin = (int)*((signed char *)a);
-        bmin = (int)*((signed char *)b);
-        p_inc(a, b, 1);
-        amax = (int)*((signed char *)a);
-        bmax = (int)*((signed char *)b);
-        p_inc(a, b, 1);
-        amin = min(amin, bmin);
-        amax = max(amax, bmax);
-        *((signed char*)c) = amin;
-        c += 1;
-        *((signed char*)c) = amax;
-        c += 1;
-        break;
-      }
     case HA_KEYTYPE_SHORT_INT:
       RT_COMB_KORR(int16, mi_sint2korr, mi_int2store, 2);
+      break;
     case HA_KEYTYPE_USHORT_INT:
       RT_COMB_KORR(uint16, mi_uint2korr, mi_int2store, 2);
+      break;
     case HA_KEYTYPE_INT24:
       RT_COMB_KORR(int32, mi_sint3korr, mi_int3store, 3);
+      break;
     case HA_KEYTYPE_UINT24:
       RT_COMB_KORR(uint32, mi_uint3korr, mi_int3store, 3);
+      break;
     case HA_KEYTYPE_LONG_INT:
       RT_COMB_KORR(int32, mi_sint4korr, mi_int4store, 4);
+      break;
     case HA_KEYTYPE_ULONG_INT:
       RT_COMB_KORR(uint32, mi_uint4korr, mi_int4store, 4);
+      break;
 #ifdef HAVE_LONG_LONG
     case HA_KEYTYPE_LONGLONG:
       RT_COMB_KORR(longlong, mi_sint8korr, mi_int8store, 8);
+      break;
     case HA_KEYTYPE_ULONGLONG:
       RT_COMB_KORR(ulonglong, mi_uint8korr, mi_int8store, 8);
+      break;
 #endif
     case HA_KEYTYPE_FLOAT:
       RT_COMB_GET(float, mi_float4get, mi_float4store, 4);
+      break;
     case HA_KEYTYPE_DOUBLE:
       RT_COMB_GET(double, mi_float8get, mi_float8store, 8);
+      break;
     case HA_KEYTYPE_END:
       return 0;
+    default:
+      return 1;
     }
+    uint32 keyseg_length= keyseg->length * 2;
+    key_length-= keyseg_length;
+    a+= keyseg_length;
+    b+= keyseg_length;
+    c+= keyseg_length;
   }
   return 0;
 }
@@ -437,16 +405,13 @@ int rtree_combine_rect(HA_KEYSEG *keyseg, uchar* a, uchar* b, uchar* c,
   type amin, amax, bmin, bmax; \
   amin = korr_func(a); \
   bmin = korr_func(b); \
-  p_inc(a, b, len); \
-  amax = korr_func(a); \
-  bmax = korr_func(b); \
-  p_inc(a, b, len); \
+  amax = korr_func(a+len); \
+  bmax = korr_func(b+len); \
   amin = max(amin, bmin); \
   amax = min(amax, bmax); \
   if (amin >= amax) \
     return 0; \
   res *= amax - amin; \
-  break; \
 }
 
 #define RT_OVL_AREA_GET(type, get_func, len) \
@@ -454,16 +419,13 @@ int rtree_combine_rect(HA_KEYSEG *keyseg, uchar* a, uchar* b, uchar* c,
   type amin, amax, bmin, bmax; \
   get_func(amin, a); \
   get_func(bmin, b); \
-  p_inc(a, b, len); \
-  get_func(amax, a); \
-  get_func(bmax, b); \
-  p_inc(a, b, len); \
+  get_func(amax, a+len); \
+  get_func(bmax, b+len); \
   amin = max(amin, bmin); \
   amax = min(amax, bmax); \
   if (amin >= amax)  \
     return 0; \
   res *= amax - amin; \
-  break; \
 }
 
 /*
@@ -475,58 +437,54 @@ double rtree_overlapping_area(HA_KEYSEG *keyseg, uchar* a, uchar* b,
   double res = 1;
   for (; (int) key_length > 0 ; keyseg += 2)
   {
-    key_length -= keyseg->length * 2;
-    
     switch ((enum ha_base_keytype) keyseg->type) {
-    case HA_KEYTYPE_TEXT:
+    case HA_KEYTYPE_INT8:
+      RT_OVL_AREA_KORR(int8, mi_sint1korr, 1);
+      break;
     case HA_KEYTYPE_BINARY:
-    case HA_KEYTYPE_VARTEXT:
-    case HA_KEYTYPE_VARBINARY:
-    case HA_KEYTYPE_NUM:
-    default:
-      return -1;
+      RT_OVL_AREA_KORR(uint8, mi_uint1korr, 1);
       break;
-    case HA_KEYTYPE_INT8:
-      {
-        int amin, amax, bmin, bmax;
-        amin = (int)*((signed char *)a);
-        bmin = (int)*((signed char *)b);
-        p_inc(a, b, 1);
-        amax = (int)*((signed char *)a);
-        bmax = (int)*((signed char *)b);
-        p_inc(a, b, 1);
-        amin = max(amin, bmin);
-        amax = min(amax, bmax);
-        if (amin >= amax) 
-          return 0;
-        res *= amax - amin;
-        break;
-      }
     case HA_KEYTYPE_SHORT_INT:
       RT_OVL_AREA_KORR(int16, mi_sint2korr, 2);
+      break;
     case HA_KEYTYPE_USHORT_INT:
       RT_OVL_AREA_KORR(uint16, mi_uint2korr, 2);
+      break;
     case HA_KEYTYPE_INT24:
       RT_OVL_AREA_KORR(int32, mi_sint3korr, 3);
+      break;
     case HA_KEYTYPE_UINT24:
       RT_OVL_AREA_KORR(uint32, mi_uint3korr, 3);
+      break;
     case HA_KEYTYPE_LONG_INT:
       RT_OVL_AREA_KORR(int32, mi_sint4korr, 4);
+      break;
     case HA_KEYTYPE_ULONG_INT:
       RT_OVL_AREA_KORR(uint32, mi_uint4korr, 4);
+      break;
 #ifdef HAVE_LONG_LONG
     case HA_KEYTYPE_LONGLONG:
       RT_OVL_AREA_KORR(longlong, mi_sint8korr, 8);
+      break;
     case HA_KEYTYPE_ULONGLONG:
       RT_OVL_AREA_KORR(longlong, mi_sint8korr, 8);
+      break;
 #endif
     case HA_KEYTYPE_FLOAT:
       RT_OVL_AREA_GET(float, mi_float4get, 4);
+      break;
     case HA_KEYTYPE_DOUBLE:
       RT_OVL_AREA_GET(double, mi_float8get, 8);
+      break;
     case HA_KEYTYPE_END:
       return res;
+    default:
+      return -1;
     }
+    uint32 keyseg_length= keyseg->length * 2;
+    key_length-= keyseg_length;
+    a+= keyseg_length;
+    b+= keyseg_length;
   }
   return res;
 }
@@ -536,13 +494,10 @@ double rtree_overlapping_area(HA_KEYSEG *keyseg, uchar* a, uchar* b,
    type amin, amax, bmin, bmax; \
    amin = korr_func(a); \
    bmin = korr_func(b); \
-   p_inc(a, b, len); \
-   amax = korr_func(a); \
-   bmax = korr_func(b); \
-   p_inc(a, b, len); \
+   amax = korr_func(a+len); \
+   bmax = korr_func(b+len); \
    a_area *= (((double)amax) - ((double)amin)); \
    *ab_area *= ((double)max(amax, bmax) - (double)min(amin, bmin)); \
-   break; \
 }
 
 #define RT_AREA_INC_GET(type, get_func, len)\
@@ -550,13 +505,10 @@ double rtree_overlapping_area(HA_KEYSEG *keyseg, uchar* a, uchar* b,
    type amin, amax, bmin, bmax; \
    get_func(amin, a); \
    get_func(bmin, b); \
-   p_inc(a, b, len); \
-   get_func(amax, a); \
-   get_func(bmax, b); \
-   p_inc(a, b, len); \
+   get_func(amax, a+len); \
+   get_func(bmax, b+len); \
    a_area *= (((double)amax) - ((double)amin)); \
    *ab_area *= ((double)max(amax, bmax) - (double)min(amin, bmin)); \
-   break; \
 }
 
 /*
@@ -565,13 +517,11 @@ Calculates MBR_AREA(a+b) - MBR_AREA(a)
 double rtree_area_increase(HA_KEYSEG *keyseg, uchar* a, uchar* b, 
                           uint key_length, double *ab_area)
 {
-  double a_area = 1;
+  double a_area= 1.0;
   
-  *ab_area = 1;
+  *ab_area= 1.0;
   for (; (int)key_length > 0; keyseg += 2)
   {
-    key_length -= keyseg->length * 2;
-    
     /* Handle NULL part */
     if (keyseg->null_bit)
     {
@@ -579,56 +529,149 @@ double rtree_area_increase(HA_KEYSEG *keyseg, uchar* a, uchar* b,
     }
 
     switch ((enum ha_base_keytype) keyseg->type) {
-    case HA_KEYTYPE_TEXT:
+    case HA_KEYTYPE_INT8:
+      RT_AREA_INC_KORR(int8, mi_sint1korr, 1);
+      break;
     case HA_KEYTYPE_BINARY:
-    case HA_KEYTYPE_VARTEXT:
-    case HA_KEYTYPE_VARBINARY:
-    case HA_KEYTYPE_NUM:
-    default:
-      return 1;
+      RT_AREA_INC_KORR(uint8, mi_uint1korr, 1);
       break;
-    case HA_KEYTYPE_INT8:
-      {
-        int amin, amax, bmin, bmax;
-        amin = (int)*((signed char *)a);
-        bmin = (int)*((signed char *)b);
-        p_inc(a, b, 1);
-        amax = (int)*((signed char *)a);
-        bmax = (int)*((signed char *)b);
-        p_inc(a, b, 1);
-        a_area *= (((double)amax) - ((double)amin));
-        *ab_area *= ((double)max(amax, bmax) - (double)min(amin, bmin));
-        break;
-      }
     case HA_KEYTYPE_SHORT_INT:
       RT_AREA_INC_KORR(int16, mi_sint2korr, 2);
+      break;
     case HA_KEYTYPE_USHORT_INT:
       RT_AREA_INC_KORR(uint16, mi_uint2korr, 2);
+      break;
     case HA_KEYTYPE_INT24:
       RT_AREA_INC_KORR(int32, mi_sint3korr, 3);
+      break;
     case HA_KEYTYPE_UINT24:
       RT_AREA_INC_KORR(int32, mi_uint3korr, 3);
+      break;
     case HA_KEYTYPE_LONG_INT:
       RT_AREA_INC_KORR(int32, mi_sint4korr, 4);
+      break;
     case HA_KEYTYPE_ULONG_INT:
       RT_AREA_INC_KORR(uint32, mi_uint4korr, 4);
+      break;
 #ifdef HAVE_LONG_LONG
     case HA_KEYTYPE_LONGLONG:
       RT_AREA_INC_KORR(longlong, mi_sint8korr, 8);
+      break;
     case HA_KEYTYPE_ULONGLONG:
       RT_AREA_INC_KORR(longlong, mi_sint8korr, 8);
+      break;
 #endif
     case HA_KEYTYPE_FLOAT:
       RT_AREA_INC_GET(float, mi_float4get, 4);
+      break;
     case HA_KEYTYPE_DOUBLE:
       RT_AREA_INC_GET(double, mi_float8get, 8);
+      break;
     case HA_KEYTYPE_END:
       return *ab_area - a_area;
+    default:
+      return -1;
     }
+    uint32 keyseg_length= keyseg->length * 2;
+    key_length-= keyseg_length;
+    a+= keyseg_length;
+    b+= keyseg_length;
   }
   return *ab_area - a_area;
 }
 
+#define RT_PERIM_INC_KORR(type, korr_func, len) \
+{ \
+   type amin, amax, bmin, bmax; \
+   amin = korr_func(a); \
+   bmin = korr_func(b); \
+   amax = korr_func(a+len); \
+   bmax = korr_func(b+len); \
+   a_perim+= (((double)amax) - ((double)amin)); \
+   *ab_perim+= ((double)max(amax, bmax) - (double)min(amin, bmin)); \
+}
+
+#define RT_PERIM_INC_GET(type, get_func, len)\
+{\
+   type amin, amax, bmin, bmax; \
+   get_func(amin, a); \
+   get_func(bmin, b); \
+   get_func(amax, a+len); \
+   get_func(bmax, b+len); \
+   a_perim+= (((double)amax) - ((double)amin)); \
+   *ab_perim+= ((double)max(amax, bmax) - (double)min(amin, bmin)); \
+}
+
+/*
+Calculates MBR_PERIMETER(a+b) - MBR_PERIMETER(a)
+*/
+double rtree_perimeter_increase(HA_KEYSEG *keyseg, uchar* a, uchar* b, 
+				uint key_length, double *ab_perim)
+{
+  double a_perim = 0.0;
+  
+  *ab_perim= 0.0;
+  for (; (int)key_length > 0; keyseg += 2)
+  {
+    /* Handle NULL part */
+    if (keyseg->null_bit)
+    {
+      return -1;
+    }
+
+    switch ((enum ha_base_keytype) keyseg->type) {
+    case HA_KEYTYPE_INT8:
+      RT_PERIM_INC_KORR(int8, mi_sint1korr, 1);
+      break;
+    case HA_KEYTYPE_BINARY:
+      RT_PERIM_INC_KORR(uint8, mi_uint1korr, 1);
+      break;
+    case HA_KEYTYPE_SHORT_INT:
+      RT_PERIM_INC_KORR(int16, mi_sint2korr, 2);
+      break;
+    case HA_KEYTYPE_USHORT_INT:
+      RT_PERIM_INC_KORR(uint16, mi_uint2korr, 2);
+      break;
+    case HA_KEYTYPE_INT24:
+      RT_PERIM_INC_KORR(int32, mi_sint3korr, 3);
+      break;
+    case HA_KEYTYPE_UINT24:
+      RT_PERIM_INC_KORR(int32, mi_uint3korr, 3);
+      break;
+    case HA_KEYTYPE_LONG_INT:
+      RT_PERIM_INC_KORR(int32, mi_sint4korr, 4);
+      break;
+    case HA_KEYTYPE_ULONG_INT:
+      RT_PERIM_INC_KORR(uint32, mi_uint4korr, 4);
+      break;
+#ifdef HAVE_LONG_LONG
+    case HA_KEYTYPE_LONGLONG:
+      RT_PERIM_INC_KORR(longlong, mi_sint8korr, 8);
+      break;
+    case HA_KEYTYPE_ULONGLONG:
+      RT_PERIM_INC_KORR(longlong, mi_sint8korr, 8);
+      break;
+#endif
+    case HA_KEYTYPE_FLOAT:
+      RT_PERIM_INC_GET(float, mi_float4get, 4);
+      break;
+    case HA_KEYTYPE_DOUBLE:
+      RT_PERIM_INC_GET(double, mi_float8get, 8);
+      break;
+    case HA_KEYTYPE_END:
+      return *ab_perim - a_perim;
+    default:
+      return -1;
+    }
+    uint32 keyseg_length= keyseg->length * 2;
+    key_length-= keyseg_length;
+    a+= keyseg_length;
+    b+= keyseg_length;
+  }
+  return *ab_perim - a_perim;
+}
+
+
 #define RT_PAGE_MBR_KORR(type, korr_func, store_func, len) \
 { \
   type amin, amax, bmin, bmax; \
@@ -649,7 +692,6 @@ double rtree_area_increase(HA_KEYSEG *keyseg, uchar* a, uchar* b,
   store_func(c, amax); \
   c += len; \
   inc += 2 * len; \
-  break; \
 }
 
 #define RT_PAGE_MBR_GET(type, get_func, store_func, len) \
@@ -672,7 +714,6 @@ double rtree_area_increase(HA_KEYSEG *keyseg, uchar* a, uchar* b,
   store_func(c, amax); \
   c += len; \
   inc += 2 * len; \
-  break; \
 }
 
 /*
@@ -700,61 +741,48 @@ int rtree_page_mbr(MI_INFO *info, HA_KEYSEG *keyseg, uchar *page_buf,
     k = rt_PAGE_FIRST_KEY(page_buf, nod_flag);
 
     switch ((enum ha_base_keytype) keyseg->type) {
-    case HA_KEYTYPE_TEXT:
+    case HA_KEYTYPE_INT8:
+      RT_PAGE_MBR_KORR(int8, mi_sint1korr, mi_int1store, 1);
+      break;
     case HA_KEYTYPE_BINARY:
-    case HA_KEYTYPE_VARTEXT:
-    case HA_KEYTYPE_VARBINARY:
-    case HA_KEYTYPE_NUM:
-    default:
-      return 1;
+      RT_PAGE_MBR_KORR(uint8, mi_uint1korr, mi_int1store, 1);
       break;
-    case HA_KEYTYPE_INT8:
-      {
-        int amin, amax, bmin, bmax;
-        amin = (int)*((signed char *)(k + inc));
-        amax = (int)*((signed char *)(k + inc + 1));
-        k = rt_PAGE_NEXT_KEY(k, k_len, nod_flag);
-        for (; k < last; k = rt_PAGE_NEXT_KEY(k, k_len, nod_flag))
-        {
-          bmin = (int)*((signed char *)(k + inc));
-          bmax = (int)*((signed char *)(k + inc + 1));
-
-          if (amin > bmin)
-            amin = bmin;
-          if (amax < bmax)
-            amax = bmax;
-        }
-        *((signed char*)c) = amin;
-        c += 1;
-        *((signed char*)c) = amax;
-        c += 1;
-        inc += 1 * 2;
-        break;
-      }
     case HA_KEYTYPE_SHORT_INT:
       RT_PAGE_MBR_KORR(int16, mi_sint2korr, mi_int2store, 2);
+      break;
     case HA_KEYTYPE_USHORT_INT:
       RT_PAGE_MBR_KORR(uint16, mi_uint2korr, mi_int2store, 2);
+      break;
     case HA_KEYTYPE_INT24:
       RT_PAGE_MBR_KORR(int32, mi_sint3korr, mi_int3store, 3);
+      break;
     case HA_KEYTYPE_UINT24:
       RT_PAGE_MBR_KORR(uint32, mi_uint3korr, mi_int3store, 3);
+      break;
     case HA_KEYTYPE_LONG_INT:
       RT_PAGE_MBR_KORR(int32, mi_sint4korr, mi_int4store, 4);
+      break;
     case HA_KEYTYPE_ULONG_INT:
       RT_PAGE_MBR_KORR(uint32, mi_uint4korr, mi_int4store, 4);
+      break;
 #ifdef HAVE_LONG_LONG
     case HA_KEYTYPE_LONGLONG:
       RT_PAGE_MBR_KORR(longlong, mi_sint8korr, mi_int8store, 8);
+      break;
     case HA_KEYTYPE_ULONGLONG:
       RT_PAGE_MBR_KORR(ulonglong, mi_uint8korr, mi_int8store, 8);
+      break;
 #endif
     case HA_KEYTYPE_FLOAT:
       RT_PAGE_MBR_GET(float, mi_float4get, mi_float4store, 4);
+      break;
     case HA_KEYTYPE_DOUBLE:
       RT_PAGE_MBR_GET(double, mi_float8get, mi_float8store, 8);
+      break;
     case HA_KEYTYPE_END:
       return 0;
+    default:
+      return 1;
     }
   }
   return 0;
diff --git a/myisam/rt_mbr.h b/myisam/rt_mbr.h
index 1367163da79..2153faad2b4 100644
--- a/myisam/rt_mbr.h
+++ b/myisam/rt_mbr.h
@@ -30,6 +30,8 @@ double rtree_overlapping_area(HA_KEYSEG *keyseg, uchar *a, uchar *b,
                               uint key_length);
 double rtree_area_increase(HA_KEYSEG *keyseg, uchar *a, uchar *b, 
                            uint key_length, double *ab_area);
+double rtree_perimeter_increase(HA_KEYSEG *keyseg, uchar* a, uchar* b, 
+				uint key_length, double *ab_perim);
 int rtree_page_mbr(MI_INFO *info, HA_KEYSEG *keyseg, uchar *page_buf, 
                    uchar* c, uint key_length);
 #endif /*HAVE_RTREE_KEYS*/
diff --git a/myisam/rt_split.c b/myisam/rt_split.c
index ccc4c0733f4..005e86805bb 100644
--- a/myisam/rt_split.c
+++ b/myisam/rt_split.c
@@ -267,12 +267,12 @@ int rtree_split_page(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *page, uchar *key,
 
   n_dim = keyinfo->keysegs / 2;
   
-  if (!my_multi_malloc(MYF(0),
-		       &coord_buf, n_dim * 2 * sizeof(double) * (max_keys + 1 + 4),
-		       &task, sizeof(SplitStruct) * (max_keys + 1),
-		       NullS))
+  if (!(coord_buf= my_alloca(n_dim * 2 * sizeof(double) * (max_keys + 1 + 4) +
+			     sizeof(SplitStruct) * (max_keys + 1))))
     return -1;
 
+  task= (SplitStruct *)(coord_buf + n_dim * 2 * (max_keys + 1 + 4));
+
   next_coord = coord_buf;
  
   stop = task + max_keys;
@@ -345,7 +345,7 @@ int rtree_split_page(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *page, uchar *key,
   my_afree((byte*)new_page);
 
 split_err:
-  my_free((gptr) coord_buf, MYF(0));
+  my_afree((byte*) coord_buf);
   return err_code;
 }
 
diff --git a/myisam/rt_test.c b/myisam/rt_test.c
index 5bf390cd0d8..5e883e223b3 100644
--- a/myisam/rt_test.c
+++ b/myisam/rt_test.c
@@ -34,6 +34,51 @@ static void create_record1(char *record,uint rownr);
 static void print_record(char * record,my_off_t offs,const char * tail);
 static  int run_test(const char *filename);
 
+static double rt_data[]=
+{
+  /*1*/  0,10,0,10,
+  /*2*/  5,15,0,10,
+  /*3*/  0,10,5,15,
+  /*4*/  10,20,10,20,
+  /*5*/  0,10,0,10,
+  /*6*/  5,15,0,10,
+  /*7*/  0,10,5,15,
+  /*8*/  10,20,10,20,
+  /*9*/  0,10,0,10,
+  /*10*/  5,15,0,10,
+  /*11*/  0,10,5,15,
+  /*12*/  10,20,10,20,
+  /*13*/  0,10,0,10,
+  /*14*/  5,15,0,10,
+  /*15*/  0,10,5,15,
+  /*16*/  10,20,10,20,
+  /*17*/  5,15,0,10,
+  /*18*/  0,10,5,15,
+  /*19*/  10,20,10,20,
+  /*20*/  0,10,0,10,
+
+  /*1*/  100,110,0,10,
+  /*2*/  105,115,0,10,
+  /*3*/  100,110,5,15,
+  /*4*/  110,120,10,20,
+  /*5*/  100,110,0,10,
+  /*6*/  105,115,0,10,
+  /*7*/  100,110,5,15,
+  /*8*/  110,120,10,20,
+  /*9*/  100,110,0,10,
+  /*10*/  105,115,0,10,
+  /*11*/  100,110,5,15,
+  /*12*/  110,120,10,20,
+  /*13*/  100,110,0,10,
+  /*14*/  105,115,0,10,
+  /*15*/  100,110,5,15,
+  /*16*/  110,120,10,20,
+  /*17*/  105,115,0,10,
+  /*18*/  100,110,5,15,
+  /*19*/  110,120,10,20,
+  /*20*/  100,110,0,10,
+  -1
+};
 
 int main(int argc __attribute__((unused)),char *argv[] __attribute__((unused)))
 {
@@ -58,7 +103,7 @@ static int run_test(const char *filename)
   int key_type=HA_KEYTYPE_DOUBLE;
   int key_length=8;
   int null_fields=0;
-  int nrecords=300;
+  int nrecords=sizeof(rt_data)/(sizeof(double)*4);/* 3000;*/
   int rec_length=0;
   int uniques=0;
   int i;
@@ -381,7 +426,7 @@ static void create_record1(char *record,uint rownr)
 }
 
 
-static void create_record(char *record,uint rownr)
+static void create_record0(char *record,uint rownr)
 {
    int i;
    char * pos;
@@ -402,6 +447,19 @@ static void create_record(char *record,uint rownr)
    }
 }
 
+static void create_record(char *record,uint rownr)
+{
+   int i;
+   char *pos;
+   double *data= rt_data+rownr*4;
+   record[0]=0x01; /* DEL marker */
+   for ( pos=record+1, i=0; i<ndims*2; i++)
+   {
+      float8store(pos,data[i]);
+      pos+=8;
+   }
+}
+
 #else
 int main(int argc __attribute__((unused)),char *argv[] __attribute__((unused)))
 {