开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数据库系统 > MySQL数据库 > 查看源码
rt_mbr.c
资源名称：mysql-4.1.16-win-src.zip　[点击查看]
上传用户：romrleung
上传日期：2022-05-23
资源大小：18897k
文件大小：21k
源码类别：

MySQL数据库

开发平台：

Visual C++

rt_mbr.c：源码内容
  1. /* Copyright (C) 2000 MySQL AB & Ramil Kalimullin & MySQL Finland AB 
  2.    & TCX DataKonsult AB
  3.    
  4.    This program is free software; you can redistribute it and/or modify
  5.    it under the terms of the GNU General Public License as published by
  6.    the Free Software Foundation; either version 2 of the License, or
  7.    (at your option) any later version.
  8.    
  9.    This program is distributed in the hope that it will be useful,
  10.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12.    GNU General Public License for more details.
  13.    
  14.    You should have received a copy of the GNU General Public License
  15.    along with this program; if not, write to the Free Software
  16.    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
  18. #include "myisamdef.h"
  20. #ifdef HAVE_RTREE_KEYS
  22. #include "rt_index.h"
  23. #include "rt_mbr.h"
  25. #define INTERSECT_CMP(amin, amax, bmin, bmax) ((amin >  bmax) || (bmin >  amax))
  26. #define CONTAIN_CMP(amin, amax, bmin, bmax) ((bmin > amin)  || (bmax <  amax))
  27. #define WITHIN_CMP(amin, amax, bmin, bmax) ((amin > bmin)  || (amax <  bmax))
  28. #define DISJOINT_CMP(amin, amax, bmin, bmax) ((amin <= bmax) && (bmin <= amax))
  29. #define EQUAL_CMP(amin, amax, bmin, bmax) ((amin != bmin) || (amax != bmax))
  31. #define FCMP(A, B) ((int)(A) - (int)(B))
  32. #define p_inc(A, B, X)  {A += X; B += X;}
  34. #define RT_CMP(nextflag) 
  35.   if (nextflag & MBR_INTERSECT) 
  36.   { 
  37.     if (INTERSECT_CMP(amin, amax, bmin, bmax)) 
  38.       return 1; 
  39.   } 
  40.   else if (nextflag & MBR_CONTAIN) 
  41.   { 
  42.     if (CONTAIN_CMP(amin, amax, bmin, bmax)) 
  43.       return 1; 
  44.   } 
  45.   else if (nextflag & MBR_WITHIN) 
  46.   { 
  47.     if (WITHIN_CMP(amin, amax, bmin, bmax)) 
  48.       return 1; 
  49.   } 
  50.   else if (nextflag & MBR_EQUAL)  
  51.   { 
  52.     if (EQUAL_CMP(amin, amax, bmin, bmax)) 
  53.       return 1; 
  54.   } 
  55.   else /* if (nextflag & MBR_DISJOINT) */ 
  56.   { 
  57.     if (DISJOINT_CMP(amin, amax, bmin, bmax)) 
  58.       return 1; 
  59.   }
  61. #define RT_CMP_KORR(type, korr_func, len, nextflag) 
  62. { 
  63.   type amin, amax, bmin, bmax; 
  64.   amin = korr_func(a); 
  65.   bmin = korr_func(b); 
  66.   amax = korr_func(a+len); 
  67.   bmax = korr_func(b+len); 
  68.   RT_CMP(nextflag); 
  69. }
  71. #define RT_CMP_GET(type, get_func, len, nextflag) 
  72. { 
  73.   type amin, amax, bmin, bmax; 
  74.   get_func(amin, a); 
  75.   get_func(bmin, b); 
  76.   get_func(amax, a+len); 
  77.   get_func(bmax, b+len); 
  78.   RT_CMP(nextflag); 
  79. }
  81. /*
  82.  Compares two keys a and b depending on nextflag
  83.  nextflag can contain these flags:
  84.    MBR_INTERSECT(a,b)  a overlaps b
  85.    MBR_CONTAIN(a,b)    a contains b
  86.    MBR_DISJOINT(a,b)   a disjoint b
  87.    MBR_WITHIN(a,b)     a within   b
  88.    MBR_EQUAL(a,b)      All coordinates of MBRs are equal
  89.    MBR_DATA(a,b)       Data reference is the same
  90.  Returns 0 on success.
  91. */
  92. int rtree_key_cmp(HA_KEYSEG *keyseg, uchar *b, uchar *a, uint key_length, 
  93.                   uint nextflag)
  94. {
  95.   for (; (int) key_length > 0; keyseg += 2 )
  96.   {
  97.     uint32 keyseg_length;
  98.     switch ((enum ha_base_keytype) keyseg->type) {
  99.     case HA_KEYTYPE_INT8:
  100.       RT_CMP_KORR(int8, mi_sint1korr, 1, nextflag);
  101.       break;
  102.     case HA_KEYTYPE_BINARY:
  103.       RT_CMP_KORR(uint8, mi_uint1korr, 1, nextflag);
  104.       break;
  105.     case HA_KEYTYPE_SHORT_INT:
  106.       RT_CMP_KORR(int16, mi_sint2korr, 2, nextflag);
  107.       break;
  108.     case HA_KEYTYPE_USHORT_INT:
  109.       RT_CMP_KORR(uint16, mi_uint2korr, 2, nextflag);
  110.       break;
  111.     case HA_KEYTYPE_INT24:
  112.       RT_CMP_KORR(int32, mi_sint3korr, 3, nextflag);
  113.       break;
  114.     case HA_KEYTYPE_UINT24:
  115.       RT_CMP_KORR(uint32, mi_uint3korr, 3, nextflag);
  116.       break;
  117.     case HA_KEYTYPE_LONG_INT:
  118.       RT_CMP_KORR(int32, mi_sint4korr, 4, nextflag);
  119.       break;
  120.     case HA_KEYTYPE_ULONG_INT:
  121.       RT_CMP_KORR(uint32, mi_uint4korr, 4, nextflag);
  122.       break;
  123. #ifdef HAVE_LONG_LONG
  124.     case HA_KEYTYPE_LONGLONG:
  125.       RT_CMP_KORR(longlong, mi_sint8korr, 8, nextflag)
  126.       break;
  127.     case HA_KEYTYPE_ULONGLONG:
  128.       RT_CMP_KORR(ulonglong, mi_uint8korr, 8, nextflag)
  129.       break;
  130. #endif
  131.     case HA_KEYTYPE_FLOAT:
  132.       /* The following should be safe, even if we compare doubles */
  133.       RT_CMP_GET(float, mi_float4get, 4, nextflag);
  134.       break;
  135.     case HA_KEYTYPE_DOUBLE:
  136.       RT_CMP_GET(double, mi_float8get, 8, nextflag);
  137.       break;
  138.     case HA_KEYTYPE_END:
  139.       goto end;
  140.     default:
  141.       return 1;
  142.     }
  143.     keyseg_length= keyseg->length * 2;
  144.     key_length-= keyseg_length;
  145.     a+= keyseg_length;
  146.     b+= keyseg_length;
  147.   }
  149. end:
  150.   if (nextflag & MBR_DATA)
  151.   {
  152.     uchar *end = a + keyseg->length;
  153.     do
  154.     {
  155.       if (*a++ != *b++)
  156.         return FCMP(a[-1], b[-1]);
  157.     } while (a != end);
  158.   }
  159.   return 0;
  160. }
  162. #define RT_VOL_KORR(type, korr_func, len, cast) 
  163. { 
  164.   type amin, amax; 
  165.   amin = korr_func(a); 
  166.   amax = korr_func(a+len); 
  167.   res *= (cast(amax) - cast(amin)); 
  168. }
  170. #define RT_VOL_GET(type, get_func, len, cast) 
  171. { 
  172.   type amin, amax; 
  173.   get_func(amin, a); 
  174.   get_func(amax, a+len); 
  175.   res *= (cast(amax) - cast(amin)); 
  176. }
  178. /*
  179.  Calculates rectangle volume
  180. */
  181. double rtree_rect_volume(HA_KEYSEG *keyseg, uchar *a, uint key_length)
  182. {
  183.   double res = 1;
  184.   for (; (int)key_length > 0; keyseg += 2)
  185.   {
  186.     uint32 keyseg_length;
  187.     switch ((enum ha_base_keytype) keyseg->type) {
  188.     case HA_KEYTYPE_INT8:
  189.       RT_VOL_KORR(int8, mi_sint1korr, 1, (double));
  190.       break;
  191.     case HA_KEYTYPE_BINARY:
  192.       RT_VOL_KORR(uint8, mi_uint1korr, 1, (double));
  193.       break;
  194.     case HA_KEYTYPE_SHORT_INT:
  195.       RT_VOL_KORR(int16, mi_sint2korr, 2, (double));
  196.       break;
  197.     case HA_KEYTYPE_USHORT_INT:
  198.       RT_VOL_KORR(uint16, mi_uint2korr, 2, (double));
  199.       break;
  200.     case HA_KEYTYPE_INT24:
  201.       RT_VOL_KORR(int32, mi_sint3korr, 3, (double));
  202.       break;
  203.     case HA_KEYTYPE_UINT24:
  204.       RT_VOL_KORR(uint32, mi_uint3korr, 3, (double));
  205.       break;
  206.     case HA_KEYTYPE_LONG_INT:
  207.       RT_VOL_KORR(int32, mi_sint4korr, 4, (double));
  208.       break;
  209.     case HA_KEYTYPE_ULONG_INT:
  210.       RT_VOL_KORR(uint32, mi_uint4korr, 4, (double));
  211.       break;
  212. #ifdef HAVE_LONG_LONG
  213.     case HA_KEYTYPE_LONGLONG:
  214.       RT_VOL_KORR(longlong, mi_sint8korr, 8, (double));
  215.       break;
  216.     case HA_KEYTYPE_ULONGLONG:
  217.       RT_VOL_KORR(longlong, mi_sint8korr, 8, ulonglong2double);
  218.       break;
  219. #endif
  220.     case HA_KEYTYPE_FLOAT:
  221.       RT_VOL_GET(float, mi_float4get, 4, (double));
  222.       break;
  223.     case HA_KEYTYPE_DOUBLE:
  224.       RT_VOL_GET(double, mi_float8get, 8, (double));
  225.       break;
  226.     case HA_KEYTYPE_END:
  227.       key_length = 0;
  228.       break;
  229.     default:
  230.       return -1;
  231.     }
  232.     keyseg_length= keyseg->length * 2;
  233.     key_length-= keyseg_length;
  234.     a+= keyseg_length;
  235.   }
  236.   return res;
  237. }
  239. #define RT_D_MBR_KORR(type, korr_func, len, cast) 
  240. { 
  241.   type amin, amax; 
  242.   amin = korr_func(a); 
  243.   amax = korr_func(a+len); 
  244.   *res++ = cast(amin); 
  245.   *res++ = cast(amax); 
  246. }
  248. #define RT_D_MBR_GET(type, get_func, len, cast) 
  249. { 
  250.   type amin, amax; 
  251.   get_func(amin, a); 
  252.   get_func(amax, a+len); 
  253.   *res++ = cast(amin); 
  254.   *res++ = cast(amax); 
  255. }
  258. /*
  259.   Creates an MBR as an array of doubles.
  260. */
  262. int rtree_d_mbr(HA_KEYSEG *keyseg, uchar *a, uint key_length, double *res)
  263. {
  264.   for (; (int)key_length > 0; keyseg += 2)
  265.   {
  266.     uint32 keyseg_length;
  267.     switch ((enum ha_base_keytype) keyseg->type) {
  268.     case HA_KEYTYPE_INT8:
  269.       RT_D_MBR_KORR(int8, mi_sint1korr, 1, (double));
  270.       break;
  271.     case HA_KEYTYPE_BINARY:
  272.       RT_D_MBR_KORR(uint8, mi_uint1korr, 1, (double));
  273.       break;
  274.     case HA_KEYTYPE_SHORT_INT:
  275.       RT_D_MBR_KORR(int16, mi_sint2korr, 2, (double));
  276.       break;
  277.     case HA_KEYTYPE_USHORT_INT:
  278.       RT_D_MBR_KORR(uint16, mi_uint2korr, 2, (double));
  279.       break;
  280.     case HA_KEYTYPE_INT24:
  281.       RT_D_MBR_KORR(int32, mi_sint3korr, 3, (double));
  282.       break;
  283.     case HA_KEYTYPE_UINT24:
  284.       RT_D_MBR_KORR(uint32, mi_uint3korr, 3, (double));
  285.       break;
  286.     case HA_KEYTYPE_LONG_INT:
  287.       RT_D_MBR_KORR(int32, mi_sint4korr, 4, (double));
  288.       break;
  289.     case HA_KEYTYPE_ULONG_INT:
  290.       RT_D_MBR_KORR(uint32, mi_uint4korr, 4, (double));
  291.       break;
  292. #ifdef HAVE_LONG_LONG
  293.     case HA_KEYTYPE_LONGLONG:
  294.       RT_D_MBR_KORR(longlong, mi_sint8korr, 8, (double));
  295.       break;
  296.     case HA_KEYTYPE_ULONGLONG:
  297.       RT_D_MBR_KORR(longlong, mi_sint8korr, 8, ulonglong2double);
  298.       break;
  299. #endif
  300.     case HA_KEYTYPE_FLOAT:
  301.       RT_D_MBR_GET(float, mi_float4get, 4, (double));
  302.       break;
  303.     case HA_KEYTYPE_DOUBLE:
  304.       RT_D_MBR_GET(double, mi_float8get, 8, (double));
  305.       break;
  306.     case HA_KEYTYPE_END:
  307.       key_length = 0;
  308.       break;
  309.     default:
  310.       return 1;
  311.     }
  312.     keyseg_length= keyseg->length * 2;
  313.     key_length-= keyseg_length;
  314.     a+= keyseg_length;
  315.   }
  316.   return 0;
  317. }
  319. #define RT_COMB_KORR(type, korr_func, store_func, len) 
  320. { 
  321.   type amin, amax, bmin, bmax; 
  322.   amin = korr_func(a); 
  323.   bmin = korr_func(b); 
  324.   amax = korr_func(a+len); 
  325.   bmax = korr_func(b+len); 
  326.   amin = min(amin, bmin); 
  327.   amax = max(amax, bmax); 
  328.   store_func(c, amin); 
  329.   store_func(c+len, amax); 
  330. }
  332. #define RT_COMB_GET(type, get_func, store_func, len) 
  333. { 
  334.   type amin, amax, bmin, bmax; 
  335.   get_func(amin, a); 
  336.   get_func(bmin, b); 
  337.   get_func(amax, a+len); 
  338.   get_func(bmax, b+len); 
  339.   amin = min(amin, bmin); 
  340.   amax = max(amax, bmax); 
  341.   store_func(c, amin); 
  342.   store_func(c+len, amax); 
  343. }
  345. /*
  346.   Creates common minimal bounding rectungle
  347.   for two input rectagnles a and b
  348.   Result is written to c
  349. */
  351. int rtree_combine_rect(HA_KEYSEG *keyseg, uchar* a, uchar* b, uchar* c, 
  352.        uint key_length)
  353. {
  354.   for ( ; (int) key_length > 0 ; keyseg += 2)
  355.   {
  356.     uint32 keyseg_length;
  357.     switch ((enum ha_base_keytype) keyseg->type) {
  358.     case HA_KEYTYPE_INT8:
  359.       RT_COMB_KORR(int8, mi_sint1korr, mi_int1store, 1);
  360.       break;
  361.     case HA_KEYTYPE_BINARY:
  362.       RT_COMB_KORR(uint8, mi_uint1korr, mi_int1store, 1);
  363.       break;
  364.     case HA_KEYTYPE_SHORT_INT:
  365.       RT_COMB_KORR(int16, mi_sint2korr, mi_int2store, 2);
  366.       break;
  367.     case HA_KEYTYPE_USHORT_INT:
  368.       RT_COMB_KORR(uint16, mi_uint2korr, mi_int2store, 2);
  369.       break;
  370.     case HA_KEYTYPE_INT24:
  371.       RT_COMB_KORR(int32, mi_sint3korr, mi_int3store, 3);
  372.       break;
  373.     case HA_KEYTYPE_UINT24:
  374.       RT_COMB_KORR(uint32, mi_uint3korr, mi_int3store, 3);
  375.       break;
  376.     case HA_KEYTYPE_LONG_INT:
  377.       RT_COMB_KORR(int32, mi_sint4korr, mi_int4store, 4);
  378.       break;
  379.     case HA_KEYTYPE_ULONG_INT:
  380.       RT_COMB_KORR(uint32, mi_uint4korr, mi_int4store, 4);
  381.       break;
  382. #ifdef HAVE_LONG_LONG
  383.     case HA_KEYTYPE_LONGLONG:
  384.       RT_COMB_KORR(longlong, mi_sint8korr, mi_int8store, 8);
  385.       break;
  386.     case HA_KEYTYPE_ULONGLONG:
  387.       RT_COMB_KORR(ulonglong, mi_uint8korr, mi_int8store, 8);
  388.       break;
  389. #endif
  390.     case HA_KEYTYPE_FLOAT:
  391.       RT_COMB_GET(float, mi_float4get, mi_float4store, 4);
  392.       break;
  393.     case HA_KEYTYPE_DOUBLE:
  394.       RT_COMB_GET(double, mi_float8get, mi_float8store, 8);
  395.       break;
  396.     case HA_KEYTYPE_END:
  397.       return 0;
  398.     default:
  399.       return 1;
  400.     }
  401.     keyseg_length= keyseg->length * 2;
  402.     key_length-= keyseg_length;
  403.     a+= keyseg_length;
  404.     b+= keyseg_length;
  405.     c+= keyseg_length;
  406.   }
  407.   return 0;
  408. }
  411. #define RT_OVL_AREA_KORR(type, korr_func, len) 
  412. { 
  413.   type amin, amax, bmin, bmax; 
  414.   amin = korr_func(a); 
  415.   bmin = korr_func(b); 
  416.   amax = korr_func(a+len); 
  417.   bmax = korr_func(b+len); 
  418.   amin = max(amin, bmin); 
  419.   amax = min(amax, bmax); 
  420.   if (amin >= amax) 
  421.     return 0; 
  422.   res *= amax - amin; 
  423. }
  425. #define RT_OVL_AREA_GET(type, get_func, len) 
  426. { 
  427.   type amin, amax, bmin, bmax; 
  428.   get_func(amin, a); 
  429.   get_func(bmin, b); 
  430.   get_func(amax, a+len); 
  431.   get_func(bmax, b+len); 
  432.   amin = max(amin, bmin); 
  433.   amax = min(amax, bmax); 
  434.   if (amin >= amax)  
  435.     return 0; 
  436.   res *= amax - amin; 
  437. }
  439. /*
  440. Calculates overlapping area of two MBRs a & b
  441. */
  442. double rtree_overlapping_area(HA_KEYSEG *keyseg, uchar* a, uchar* b, 
  443.                              uint key_length)
  444. {
  445.   double res = 1;
  446.   for (; (int) key_length > 0 ; keyseg += 2)
  447.   {
  448.     uint32 keyseg_length;
  449.     switch ((enum ha_base_keytype) keyseg->type) {
  450.     case HA_KEYTYPE_INT8:
  451.       RT_OVL_AREA_KORR(int8, mi_sint1korr, 1);
  452.       break;
  453.     case HA_KEYTYPE_BINARY:
  454.       RT_OVL_AREA_KORR(uint8, mi_uint1korr, 1);
  455.       break;
  456.     case HA_KEYTYPE_SHORT_INT:
  457.       RT_OVL_AREA_KORR(int16, mi_sint2korr, 2);
  458.       break;
  459.     case HA_KEYTYPE_USHORT_INT:
  460.       RT_OVL_AREA_KORR(uint16, mi_uint2korr, 2);
  461.       break;
  462.     case HA_KEYTYPE_INT24:
  463.       RT_OVL_AREA_KORR(int32, mi_sint3korr, 3);
  464.       break;
  465.     case HA_KEYTYPE_UINT24:
  466.       RT_OVL_AREA_KORR(uint32, mi_uint3korr, 3);
  467.       break;
  468.     case HA_KEYTYPE_LONG_INT:
  469.       RT_OVL_AREA_KORR(int32, mi_sint4korr, 4);
  470.       break;
  471.     case HA_KEYTYPE_ULONG_INT:
  472.       RT_OVL_AREA_KORR(uint32, mi_uint4korr, 4);
  473.       break;
  474. #ifdef HAVE_LONG_LONG
  475.     case HA_KEYTYPE_LONGLONG:
  476.       RT_OVL_AREA_KORR(longlong, mi_sint8korr, 8);
  477.       break;
  478.     case HA_KEYTYPE_ULONGLONG:
  479.       RT_OVL_AREA_KORR(longlong, mi_sint8korr, 8);
  480.       break;
  481. #endif
  482.     case HA_KEYTYPE_FLOAT:
  483.       RT_OVL_AREA_GET(float, mi_float4get, 4);
  484.       break;
  485.     case HA_KEYTYPE_DOUBLE:
  486.       RT_OVL_AREA_GET(double, mi_float8get, 8);
  487.       break;
  488.     case HA_KEYTYPE_END:
  489.       return res;
  490.     default:
  491.       return -1;
  492.     }
  493.     keyseg_length= keyseg->length * 2;
  494.     key_length-= keyseg_length;
  495.     a+= keyseg_length;
  496.     b+= keyseg_length;
  497.   }
  498.   return res;
  499. }
  501. #define RT_AREA_INC_KORR(type, korr_func, len) 
  502. { 
  503.    type amin, amax, bmin, bmax; 
  504.    amin = korr_func(a); 
  505.    bmin = korr_func(b); 
  506.    amax = korr_func(a+len); 
  507.    bmax = korr_func(b+len); 
  508.    a_area *= (((double)amax) - ((double)amin)); 
  509.    loc_ab_area *= ((double)max(amax, bmax) - (double)min(amin, bmin)); 
  510. }
  512. #define RT_AREA_INC_GET(type, get_func, len)
  513. {
  514.    type amin, amax, bmin, bmax; 
  515.    get_func(amin, a); 
  516.    get_func(bmin, b); 
  517.    get_func(amax, a+len); 
  518.    get_func(bmax, b+len); 
  519.    a_area *= (((double)amax) - ((double)amin)); 
  520.    loc_ab_area *= ((double)max(amax, bmax) - (double)min(amin, bmin)); 
  521. }
  523. /*
  524. Calculates MBR_AREA(a+b) - MBR_AREA(a)
  525. */
  526. double rtree_area_increase(HA_KEYSEG *keyseg, uchar* a, uchar* b, 
  527.                           uint key_length, double *ab_area)
  528. {
  529.   double a_area= 1.0;
  530.   double loc_ab_area= 1.0;
  531.   
  532.   *ab_area= 1.0;
  533.   for (; (int)key_length > 0; keyseg += 2)
  534.   {
  535.     uint32 keyseg_length;
  537.     if (keyseg->null_bit)                       /* Handle NULL part */
  538.       return -1;
  540.     switch ((enum ha_base_keytype) keyseg->type) {
  541.     case HA_KEYTYPE_INT8:
  542.       RT_AREA_INC_KORR(int8, mi_sint1korr, 1);
  543.       break;
  544.     case HA_KEYTYPE_BINARY:
  545.       RT_AREA_INC_KORR(uint8, mi_uint1korr, 1);
  546.       break;
  547.     case HA_KEYTYPE_SHORT_INT:
  548.       RT_AREA_INC_KORR(int16, mi_sint2korr, 2);
  549.       break;
  550.     case HA_KEYTYPE_USHORT_INT:
  551.       RT_AREA_INC_KORR(uint16, mi_uint2korr, 2);
  552.       break;
  553.     case HA_KEYTYPE_INT24:
  554.       RT_AREA_INC_KORR(int32, mi_sint3korr, 3);
  555.       break;
  556.     case HA_KEYTYPE_UINT24:
  557.       RT_AREA_INC_KORR(int32, mi_uint3korr, 3);
  558.       break;
  559.     case HA_KEYTYPE_LONG_INT:
  560.       RT_AREA_INC_KORR(int32, mi_sint4korr, 4);
  561.       break;
  562.     case HA_KEYTYPE_ULONG_INT:
  563.       RT_AREA_INC_KORR(uint32, mi_uint4korr, 4);
  564.       break;
  565. #ifdef HAVE_LONG_LONG
  566.     case HA_KEYTYPE_LONGLONG:
  567.       RT_AREA_INC_KORR(longlong, mi_sint8korr, 8);
  568.       break;
  569.     case HA_KEYTYPE_ULONGLONG:
  570.       RT_AREA_INC_KORR(longlong, mi_sint8korr, 8);
  571.       break;
  572. #endif
  573.     case HA_KEYTYPE_FLOAT:
  574.       RT_AREA_INC_GET(float, mi_float4get, 4);
  575.       break;
  576.     case HA_KEYTYPE_DOUBLE:
  577.       RT_AREA_INC_GET(double, mi_float8get, 8);
  578.       break;
  579.     case HA_KEYTYPE_END:
  580.       goto safe_end;
  581.     default:
  582.       return -1;
  583.     }
  584.     keyseg_length= keyseg->length * 2;
  585.     key_length-= keyseg_length;
  586.     a+= keyseg_length;
  587.     b+= keyseg_length;
  588.   }
  589. safe_end:
  590.   *ab_area= loc_ab_area;
  591.   return loc_ab_area - a_area;
  592. }
  594. #define RT_PERIM_INC_KORR(type, korr_func, len) 
  595. { 
  596.    type amin, amax, bmin, bmax; 
  597.    amin = korr_func(a); 
  598.    bmin = korr_func(b); 
  599.    amax = korr_func(a+len); 
  600.    bmax = korr_func(b+len); 
  601.    a_perim+= (((double)amax) - ((double)amin)); 
  602.    *ab_perim+= ((double)max(amax, bmax) - (double)min(amin, bmin)); 
  603. }
  605. #define RT_PERIM_INC_GET(type, get_func, len)
  606. {
  607.    type amin, amax, bmin, bmax; 
  608.    get_func(amin, a); 
  609.    get_func(bmin, b); 
  610.    get_func(amax, a+len); 
  611.    get_func(bmax, b+len); 
  612.    a_perim+= (((double)amax) - ((double)amin)); 
  613.    *ab_perim+= ((double)max(amax, bmax) - (double)min(amin, bmin)); 
  614. }
  616. /*
  617. Calculates MBR_PERIMETER(a+b) - MBR_PERIMETER(a)
  618. */
  619. double rtree_perimeter_increase(HA_KEYSEG *keyseg, uchar* a, uchar* b, 
  620. uint key_length, double *ab_perim)
  621. {
  622.   double a_perim = 0.0;
  623.   
  624.   *ab_perim= 0.0;
  625.   for (; (int)key_length > 0; keyseg += 2)
  626.   {
  627.     uint32 keyseg_length;
  629.     if (keyseg->null_bit)                       /* Handle NULL part */
  630.       return -1;
  632.     switch ((enum ha_base_keytype) keyseg->type) {
  633.     case HA_KEYTYPE_INT8:
  634.       RT_PERIM_INC_KORR(int8, mi_sint1korr, 1);
  635.       break;
  636.     case HA_KEYTYPE_BINARY:
  637.       RT_PERIM_INC_KORR(uint8, mi_uint1korr, 1);
  638.       break;
  639.     case HA_KEYTYPE_SHORT_INT:
  640.       RT_PERIM_INC_KORR(int16, mi_sint2korr, 2);
  641.       break;
  642.     case HA_KEYTYPE_USHORT_INT:
  643.       RT_PERIM_INC_KORR(uint16, mi_uint2korr, 2);
  644.       break;
  645.     case HA_KEYTYPE_INT24:
  646.       RT_PERIM_INC_KORR(int32, mi_sint3korr, 3);
  647.       break;
  648.     case HA_KEYTYPE_UINT24:
  649.       RT_PERIM_INC_KORR(int32, mi_uint3korr, 3);
  650.       break;
  651.     case HA_KEYTYPE_LONG_INT:
  652.       RT_PERIM_INC_KORR(int32, mi_sint4korr, 4);
  653.       break;
  654.     case HA_KEYTYPE_ULONG_INT:
  655.       RT_PERIM_INC_KORR(uint32, mi_uint4korr, 4);
  656.       break;
  657. #ifdef HAVE_LONG_LONG
  658.     case HA_KEYTYPE_LONGLONG:
  659.       RT_PERIM_INC_KORR(longlong, mi_sint8korr, 8);
  660.       break;
  661.     case HA_KEYTYPE_ULONGLONG:
  662.       RT_PERIM_INC_KORR(longlong, mi_sint8korr, 8);
  663.       break;
  664. #endif
  665.     case HA_KEYTYPE_FLOAT:
  666.       RT_PERIM_INC_GET(float, mi_float4get, 4);
  667.       break;
  668.     case HA_KEYTYPE_DOUBLE:
  669.       RT_PERIM_INC_GET(double, mi_float8get, 8);
  670.       break;
  671.     case HA_KEYTYPE_END:
  672.       return *ab_perim - a_perim;
  673.     default:
  674.       return -1;
  675.     }
  676.     keyseg_length= keyseg->length * 2;
  677.     key_length-= keyseg_length;
  678.     a+= keyseg_length;
  679.     b+= keyseg_length;
  680.   }
  681.   return *ab_perim - a_perim;
  682. }
  685. #define RT_PAGE_MBR_KORR(type, korr_func, store_func, len) 
  686. { 
  687.   type amin, amax, bmin, bmax; 
  688.   amin = korr_func(k + inc); 
  689.   amax = korr_func(k + inc + len); 
  690.   k = rt_PAGE_NEXT_KEY(k, k_len, nod_flag); 
  691.   for (; k < last; k = rt_PAGE_NEXT_KEY(k, k_len, nod_flag)) 
  692. { 
  693.     bmin = korr_func(k + inc); 
  694.     bmax = korr_func(k + inc + len); 
  695.     if (amin > bmin) 
  696.       amin = bmin; 
  697.     if (amax < bmax) 
  698.       amax = bmax; 
  699. } 
  700.   store_func(c, amin); 
  701.   c += len; 
  702.   store_func(c, amax); 
  703.   c += len; 
  704.   inc += 2 * len; 
  705. }
  707. #define RT_PAGE_MBR_GET(type, get_func, store_func, len) 
  708. { 
  709.   type amin, amax, bmin, bmax; 
  710.   get_func(amin, k + inc); 
  711.   get_func(amax, k + inc + len); 
  712.   k = rt_PAGE_NEXT_KEY(k, k_len, nod_flag); 
  713.   for (; k < last; k = rt_PAGE_NEXT_KEY(k, k_len, nod_flag)) 
  714. { 
  715.     get_func(bmin, k + inc); 
  716.     get_func(bmax, k + inc + len); 
  717.     if (amin > bmin) 
  718.       amin = bmin; 
  719.     if (amax < bmax) 
  720.       amax = bmax; 
  721. } 
  722.   store_func(c, amin); 
  723.   c += len; 
  724.   store_func(c, amax); 
  725.   c += len; 
  726.   inc += 2 * len; 
  727. }
  729. /*
  730. Calculates key page total MBR = MBR(key1) + MBR(key2) + ...
  731. */
  732. int rtree_page_mbr(MI_INFO *info, HA_KEYSEG *keyseg, uchar *page_buf,
  733.                   uchar *c, uint key_length)
  734. {
  735.   uint inc = 0;
  736.   uint k_len = key_length;
  737.   uint nod_flag = mi_test_if_nod(page_buf);
  738.   uchar *k;
  739.   uchar *last = rt_PAGE_END(page_buf);
  741.   for (; (int)key_length > 0; keyseg += 2)
  742.   {
  743.     key_length -= keyseg->length * 2;
  744.     
  745.     /* Handle NULL part */
  746.     if (keyseg->null_bit)
  747.     {
  748.       return 1;
  749.     }
  751.     k = rt_PAGE_FIRST_KEY(page_buf, nod_flag);
  753.     switch ((enum ha_base_keytype) keyseg->type) {
  754.     case HA_KEYTYPE_INT8:
  755.       RT_PAGE_MBR_KORR(int8, mi_sint1korr, mi_int1store, 1);
  756.       break;
  757.     case HA_KEYTYPE_BINARY:
  758.       RT_PAGE_MBR_KORR(uint8, mi_uint1korr, mi_int1store, 1);
  759.       break;
  760.     case HA_KEYTYPE_SHORT_INT:
  761.       RT_PAGE_MBR_KORR(int16, mi_sint2korr, mi_int2store, 2);
  762.       break;
  763.     case HA_KEYTYPE_USHORT_INT:
  764.       RT_PAGE_MBR_KORR(uint16, mi_uint2korr, mi_int2store, 2);
  765.       break;
  766.     case HA_KEYTYPE_INT24:
  767.       RT_PAGE_MBR_KORR(int32, mi_sint3korr, mi_int3store, 3);
  768.       break;
  769.     case HA_KEYTYPE_UINT24:
  770.       RT_PAGE_MBR_KORR(uint32, mi_uint3korr, mi_int3store, 3);
  771.       break;
  772.     case HA_KEYTYPE_LONG_INT:
  773.       RT_PAGE_MBR_KORR(int32, mi_sint4korr, mi_int4store, 4);
  774.       break;
  775.     case HA_KEYTYPE_ULONG_INT:
  776.       RT_PAGE_MBR_KORR(uint32, mi_uint4korr, mi_int4store, 4);
  777.       break;
  778. #ifdef HAVE_LONG_LONG
  779.     case HA_KEYTYPE_LONGLONG:
  780.       RT_PAGE_MBR_KORR(longlong, mi_sint8korr, mi_int8store, 8);
  781.       break;
  782.     case HA_KEYTYPE_ULONGLONG:
  783.       RT_PAGE_MBR_KORR(ulonglong, mi_uint8korr, mi_int8store, 8);
  784.       break;
  785. #endif
  786.     case HA_KEYTYPE_FLOAT:
  787.       RT_PAGE_MBR_GET(float, mi_float4get, mi_float4store, 4);
  788.       break;
  789.     case HA_KEYTYPE_DOUBLE:
  790.       RT_PAGE_MBR_GET(double, mi_float8get, mi_float8store, 8);
  791.       break;
  792.     case HA_KEYTYPE_END:
  793.       return 0;
  794.     default:
  795.       return 1;
  796.     }
  797.   }
  798.   return 0;
  799. }
  801. #endif /*HAVE_RTREE_KEYS*/