LTP GCOV extension - code coverage report
Current view: directory - storage/maria - ma_rt_mbr.c
Test: maria-unit-test.html
Date: 2009-03-04 Instrumented lines: 284
Code covered: 0.0 % Executed lines: 0

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

Generated by: LTP GCOV extension version 1.4