release/src/router/mysql/storage/myisam/rt_mbr.c

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