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