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