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., 51 Franklin Street, Fifth Floor, Boston, MA 02111-1301 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
96int maria_rtree_key_cmp(HA_KEYSEG *keyseg, const uchar *b, const uchar *a,
97 uint key_length, uint32 nextflag)
98{
99 for (; (int) key_length > 0; keyseg += 2 )
100 {
101 uint32 keyseg_length;
102 switch ((enum ha_base_keytype) keyseg->type) {
103 case HA_KEYTYPE_INT8:
104 RT_CMP_KORR(int8, mi_sint1korr, 1, nextflag);
105 break;
106 case HA_KEYTYPE_BINARY:
107 RT_CMP_KORR(uint8, mi_uint1korr, 1, nextflag);
108 break;
109 case HA_KEYTYPE_SHORT_INT:
110 RT_CMP_KORR(int16, mi_sint2korr, 2, nextflag);
111 break;
112 case HA_KEYTYPE_USHORT_INT:
113 RT_CMP_KORR(uint16, mi_uint2korr, 2, nextflag);
114 break;
115 case HA_KEYTYPE_INT24:
116 RT_CMP_KORR(int32, mi_sint3korr, 3, nextflag);
117 break;
118 case HA_KEYTYPE_UINT24:
119 RT_CMP_KORR(uint32, mi_uint3korr, 3, nextflag);
120 break;
121 case HA_KEYTYPE_LONG_INT:
122 RT_CMP_KORR(int32, mi_sint4korr, 4, nextflag);
123 break;
124 case HA_KEYTYPE_ULONG_INT:
125 RT_CMP_KORR(uint32, mi_uint4korr, 4, nextflag);
126 break;
127#ifdef HAVE_LONG_LONG
128 case HA_KEYTYPE_LONGLONG:
129 RT_CMP_KORR(longlong, mi_sint8korr, 8, nextflag)
130 break;
131 case HA_KEYTYPE_ULONGLONG:
132 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 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
153end:
154 if (nextflag & MBR_DATA)
155 {
156 const 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*/
185double maria_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#ifdef HAVE_LONG_LONG
217 case HA_KEYTYPE_LONGLONG:
218 RT_VOL_KORR(longlong, mi_sint8korr, 8, (double));
219 break;
220 case HA_KEYTYPE_ULONGLONG:
221 RT_VOL_KORR(longlong, mi_sint8korr, 8, ulonglong2double);
222 break;
223#endif
224 case HA_KEYTYPE_FLOAT:
225 RT_VOL_GET(float, mi_float4get, 4, (double));
226 break;
227 case HA_KEYTYPE_DOUBLE:
228 RT_VOL_GET(double, mi_float8get, 8, (double));
229 break;
230 case HA_KEYTYPE_END:
231 key_length= 0;
232 break;
233 default:
234 return -1;
235 }
236 keyseg_length= keyseg->length * 2;
237 key_length-= keyseg_length;
238 a+= keyseg_length;
239 }
240 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
267int maria_rtree_d_mbr(const HA_KEYSEG *keyseg, const uchar *a,
268 uint key_length, double *res)
269{
270 for (; (int)key_length > 0; keyseg += 2)
271 {
272 uint32 keyseg_length;
273 switch ((enum ha_base_keytype) keyseg->type) {
274 case HA_KEYTYPE_INT8:
275 RT_D_MBR_KORR(int8, mi_sint1korr, 1, (double));
276 break;
277 case HA_KEYTYPE_BINARY:
278 RT_D_MBR_KORR(uint8, mi_uint1korr, 1, (double));
279 break;
280 case HA_KEYTYPE_SHORT_INT:
281 RT_D_MBR_KORR(int16, mi_sint2korr, 2, (double));
282 break;
283 case HA_KEYTYPE_USHORT_INT:
284 RT_D_MBR_KORR(uint16, mi_uint2korr, 2, (double));
285 break;
286 case HA_KEYTYPE_INT24:
287 RT_D_MBR_KORR(int32, mi_sint3korr, 3, (double));
288 break;
289 case HA_KEYTYPE_UINT24:
290 RT_D_MBR_KORR(uint32, mi_uint3korr, 3, (double));
291 break;
292 case HA_KEYTYPE_LONG_INT:
293 RT_D_MBR_KORR(int32, mi_sint4korr, 4, (double));
294 break;
295 case HA_KEYTYPE_ULONG_INT:
296 RT_D_MBR_KORR(uint32, mi_uint4korr, 4, (double));
297 break;
298#ifdef HAVE_LONG_LONG
299 case HA_KEYTYPE_LONGLONG:
300 RT_D_MBR_KORR(longlong, mi_sint8korr, 8, (double));
301 break;
302 case HA_KEYTYPE_ULONGLONG:
303 RT_D_MBR_KORR(longlong, mi_sint8korr, 8, ulonglong2double);
304 break;
305#endif
306 case HA_KEYTYPE_FLOAT:
307 RT_D_MBR_GET(float, mi_float4get, 4, (double));
308 break;
309 case HA_KEYTYPE_DOUBLE:
310 RT_D_MBR_GET(double, mi_float8get, 8, (double));
311 break;
312 case HA_KEYTYPE_END:
313 key_length= 0;
314 break;
315 default:
316 return 1;
317 }
318 keyseg_length= keyseg->length * 2;
319 key_length-= keyseg_length;
320 a+= keyseg_length;
321 }
322 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= MY_MIN(amin, bmin); \
333 amax= MY_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= MY_MIN(amin, bmin); \
346 amax= MY_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
357int maria_rtree_combine_rect(const HA_KEYSEG *keyseg, const uchar* a,
358 const uchar* b, uchar* c,
359 uint key_length)
360{
361 for ( ; (int) key_length > 0 ; keyseg += 2)
362 {
363 uint32 keyseg_length;
364 switch ((enum ha_base_keytype) keyseg->type) {
365 case HA_KEYTYPE_INT8:
366 RT_COMB_KORR(int8, mi_sint1korr, mi_int1store, 1);
367 break;
368 case HA_KEYTYPE_BINARY:
369 RT_COMB_KORR(uint8, mi_uint1korr, mi_int1store, 1);
370 break;
371 case HA_KEYTYPE_SHORT_INT:
372 RT_COMB_KORR(int16, mi_sint2korr, mi_int2store, 2);
373 break;
374 case HA_KEYTYPE_USHORT_INT:
375 RT_COMB_KORR(uint16, mi_uint2korr, mi_int2store, 2);
376 break;
377 case HA_KEYTYPE_INT24:
378 RT_COMB_KORR(int32, mi_sint3korr, mi_int3store, 3);
379 break;
380 case HA_KEYTYPE_UINT24:
381 RT_COMB_KORR(uint32, mi_uint3korr, mi_int3store, 3);
382 break;
383 case HA_KEYTYPE_LONG_INT:
384 RT_COMB_KORR(int32, mi_sint4korr, mi_int4store, 4);
385 break;
386 case HA_KEYTYPE_ULONG_INT:
387 RT_COMB_KORR(uint32, mi_uint4korr, mi_int4store, 4);
388 break;
389#ifdef HAVE_LONG_LONG
390 case HA_KEYTYPE_LONGLONG:
391 RT_COMB_KORR(longlong, mi_sint8korr, mi_int8store, 8);
392 break;
393 case HA_KEYTYPE_ULONGLONG:
394 RT_COMB_KORR(ulonglong, mi_uint8korr, mi_int8store, 8);
395 break;
396#endif
397 case HA_KEYTYPE_FLOAT:
398 RT_COMB_GET(float, mi_float4get, mi_float4store, 4);
399 break;
400 case HA_KEYTYPE_DOUBLE:
401 RT_COMB_GET(double, mi_float8get, mi_float8store, 8);
402 break;
403 case HA_KEYTYPE_END:
404 return 0;
405 default:
406 return 1;
407 }
408 keyseg_length= keyseg->length * 2;
409 key_length-= keyseg_length;
410 a+= keyseg_length;
411 b+= keyseg_length;
412 c+= keyseg_length;
413 }
414 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= MY_MAX(amin, bmin); \
426 amax= MY_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= MY_MAX(amin, bmin); \
440 amax= MY_MIN(amax, bmax); \
441 if (amin >= amax) \
442 return 0; \
443 res *= amax - amin; \
444}
445
446/*
447Calculates overlapping area of two MBRs a & b
448*/
449double maria_rtree_overlapping_area(HA_KEYSEG *keyseg, uchar* a, uchar* b,
450 uint key_length)
451{
452 double res= 1;
453 for (; (int) key_length > 0 ; keyseg += 2)
454 {
455 uint32 keyseg_length;
456 switch ((enum ha_base_keytype) keyseg->type) {
457 case HA_KEYTYPE_INT8:
458 RT_OVL_AREA_KORR(int8, mi_sint1korr, 1);
459 break;
460 case HA_KEYTYPE_BINARY:
461 RT_OVL_AREA_KORR(uint8, mi_uint1korr, 1);
462 break;
463 case HA_KEYTYPE_SHORT_INT:
464 RT_OVL_AREA_KORR(int16, mi_sint2korr, 2);
465 break;
466 case HA_KEYTYPE_USHORT_INT:
467 RT_OVL_AREA_KORR(uint16, mi_uint2korr, 2);
468 break;
469 case HA_KEYTYPE_INT24:
470 RT_OVL_AREA_KORR(int32, mi_sint3korr, 3);
471 break;
472 case HA_KEYTYPE_UINT24:
473 RT_OVL_AREA_KORR(uint32, mi_uint3korr, 3);
474 break;
475 case HA_KEYTYPE_LONG_INT:
476 RT_OVL_AREA_KORR(int32, mi_sint4korr, 4);
477 break;
478 case HA_KEYTYPE_ULONG_INT:
479 RT_OVL_AREA_KORR(uint32, mi_uint4korr, 4);
480 break;
481#ifdef HAVE_LONG_LONG
482 case HA_KEYTYPE_LONGLONG:
483 RT_OVL_AREA_KORR(longlong, mi_sint8korr, 8);
484 break;
485 case HA_KEYTYPE_ULONGLONG:
486 RT_OVL_AREA_KORR(longlong, mi_sint8korr, 8);
487 break;
488#endif
489 case HA_KEYTYPE_FLOAT:
490 RT_OVL_AREA_GET(float, mi_float4get, 4);
491 break;
492 case HA_KEYTYPE_DOUBLE:
493 RT_OVL_AREA_GET(double, mi_float8get, 8);
494 break;
495 case HA_KEYTYPE_END:
496 return res;
497 default:
498 return -1;
499 }
500 keyseg_length= keyseg->length * 2;
501 key_length-= keyseg_length;
502 a+= keyseg_length;
503 b+= keyseg_length;
504 }
505 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)MY_MAX(amax, bmax) - (double)MY_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)MY_MAX(amax, bmax) - (double)MY_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
538double maria_rtree_area_increase(const HA_KEYSEG *keyseg, const uchar *a,
539 const uchar *b,
540 uint key_length, double *ab_area)
541{
542 double a_area= 1.0;
543 double loc_ab_area= 1.0;
544
545 *ab_area= 1.0;
546 for (; (int)key_length > 0; keyseg += 2)
547 {
548 uint32 keyseg_length;
549
550 if (keyseg->null_bit) /* Handle NULL part */
551 return -1;
552
553 switch ((enum ha_base_keytype) keyseg->type) {
554 case HA_KEYTYPE_INT8:
555 RT_AREA_INC_KORR(int8, mi_sint1korr, 1);
556 break;
557 case HA_KEYTYPE_BINARY:
558 RT_AREA_INC_KORR(uint8, mi_uint1korr, 1);
559 break;
560 case HA_KEYTYPE_SHORT_INT:
561 RT_AREA_INC_KORR(int16, mi_sint2korr, 2);
562 break;
563 case HA_KEYTYPE_USHORT_INT:
564 RT_AREA_INC_KORR(uint16, mi_uint2korr, 2);
565 break;
566 case HA_KEYTYPE_INT24:
567 RT_AREA_INC_KORR(int32, mi_sint3korr, 3);
568 break;
569 case HA_KEYTYPE_UINT24:
570 RT_AREA_INC_KORR(int32, mi_uint3korr, 3);
571 break;
572 case HA_KEYTYPE_LONG_INT:
573 RT_AREA_INC_KORR(int32, mi_sint4korr, 4);
574 break;
575 case HA_KEYTYPE_ULONG_INT:
576 RT_AREA_INC_KORR(uint32, mi_uint4korr, 4);
577 break;
578#ifdef HAVE_LONG_LONG
579 case HA_KEYTYPE_LONGLONG:
580 RT_AREA_INC_KORR(longlong, mi_sint8korr, 8);
581 break;
582 case HA_KEYTYPE_ULONGLONG:
583 RT_AREA_INC_KORR(longlong, mi_sint8korr, 8);
584 break;
585#endif
586 case HA_KEYTYPE_FLOAT:
587 RT_AREA_INC_GET(float, mi_float4get, 4);
588 break;
589 case HA_KEYTYPE_DOUBLE:
590 RT_AREA_INC_GET(double, mi_float8get, 8);
591 break;
592 case HA_KEYTYPE_END:
593 goto safe_end;
594 default:
595 return -1;
596 }
597 keyseg_length= keyseg->length * 2;
598 key_length-= keyseg_length;
599 a+= keyseg_length;
600 b+= keyseg_length;
601 }
602safe_end:
603 *ab_area= loc_ab_area;
604 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)MY_MAX(amax, bmax) - (double)MY_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)MY_MAX(amax, bmax) - (double)MY_MIN(amin, bmin)); \
627}
628
629/*
630Calculates MBR_PERIMETER(a+b) - MBR_PERIMETER(a)
631*/
632double maria_rtree_perimeter_increase(HA_KEYSEG *keyseg, uchar* a, uchar* b,
633 uint key_length, double *ab_perim)
634{
635 double a_perim= 0.0;
636
637 *ab_perim= 0.0;
638 for (; (int)key_length > 0; keyseg += 2)
639 {
640 uint32 keyseg_length;
641
642 if (keyseg->null_bit) /* Handle NULL part */
643 return -1;
644
645 switch ((enum ha_base_keytype) keyseg->type) {
646 case HA_KEYTYPE_INT8:
647 RT_PERIM_INC_KORR(int8, mi_sint1korr, 1);
648 break;
649 case HA_KEYTYPE_BINARY:
650 RT_PERIM_INC_KORR(uint8, mi_uint1korr, 1);
651 break;
652 case HA_KEYTYPE_SHORT_INT:
653 RT_PERIM_INC_KORR(int16, mi_sint2korr, 2);
654 break;
655 case HA_KEYTYPE_USHORT_INT:
656 RT_PERIM_INC_KORR(uint16, mi_uint2korr, 2);
657 break;
658 case HA_KEYTYPE_INT24:
659 RT_PERIM_INC_KORR(int32, mi_sint3korr, 3);
660 break;
661 case HA_KEYTYPE_UINT24:
662 RT_PERIM_INC_KORR(int32, mi_uint3korr, 3);
663 break;
664 case HA_KEYTYPE_LONG_INT:
665 RT_PERIM_INC_KORR(int32, mi_sint4korr, 4);
666 break;
667 case HA_KEYTYPE_ULONG_INT:
668 RT_PERIM_INC_KORR(uint32, mi_uint4korr, 4);
669 break;
670#ifdef HAVE_LONG_LONG
671 case HA_KEYTYPE_LONGLONG:
672 RT_PERIM_INC_KORR(longlong, mi_sint8korr, 8);
673 break;
674 case HA_KEYTYPE_ULONGLONG:
675 RT_PERIM_INC_KORR(longlong, mi_sint8korr, 8);
676 break;
677#endif
678 case HA_KEYTYPE_FLOAT:
679 RT_PERIM_INC_GET(float, mi_float4get, 4);
680 break;
681 case HA_KEYTYPE_DOUBLE:
682 RT_PERIM_INC_GET(double, mi_float8get, 8);
683 break;
684 case HA_KEYTYPE_END:
685 return *ab_perim - a_perim;
686 default:
687 return -1;
688 }
689 keyseg_length= keyseg->length * 2;
690 key_length-= keyseg_length;
691 a+= keyseg_length;
692 b+= keyseg_length;
693 }
694 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*/
746int maria_rtree_page_mbr(const HA_KEYSEG *keyseg,
747 MARIA_PAGE *page,
748 uchar *to, uint key_length)
749{
750 MARIA_HA *info= page->info;
751 MARIA_SHARE *share= info->s;
752 uint inc= 0;
753 uint k_len= key_length;
754 uint nod_flag= page->node;
755 const uchar *k;
756 const uchar *last= rt_PAGE_END(page);
757
758 for (; (int)key_length > 0; keyseg += 2)
759 {
760 key_length -= keyseg->length * 2;
761
762 /* Handle NULL part */
763 if (keyseg->null_bit)
764 {
765 return 1;
766 }
767
768 k= rt_PAGE_FIRST_KEY(share, page->buff, nod_flag);
769
770 switch ((enum ha_base_keytype) keyseg->type) {
771 case HA_KEYTYPE_INT8:
772 RT_PAGE_MBR_KORR(share, int8, mi_sint1korr, mi_int1store, 1, to);
773 break;
774 case HA_KEYTYPE_BINARY:
775 RT_PAGE_MBR_KORR(share, uint8, mi_uint1korr, mi_int1store, 1, to);
776 break;
777 case HA_KEYTYPE_SHORT_INT:
778 RT_PAGE_MBR_KORR(share, int16, mi_sint2korr, mi_int2store, 2, to);
779 break;
780 case HA_KEYTYPE_USHORT_INT:
781 RT_PAGE_MBR_KORR(share, uint16, mi_uint2korr, mi_int2store, 2, to);
782 break;
783 case HA_KEYTYPE_INT24:
784 RT_PAGE_MBR_KORR(share, int32, mi_sint3korr, mi_int3store, 3, to);
785 break;
786 case HA_KEYTYPE_UINT24:
787 RT_PAGE_MBR_KORR(share, uint32, mi_uint3korr, mi_int3store, 3, to);
788 break;
789 case HA_KEYTYPE_LONG_INT:
790 RT_PAGE_MBR_KORR(share, int32, mi_sint4korr, mi_int4store, 4, to);
791 break;
792 case HA_KEYTYPE_ULONG_INT:
793 RT_PAGE_MBR_KORR(share, uint32, mi_uint4korr, mi_int4store, 4, to);
794 break;
795#ifdef HAVE_LONG_LONG
796 case HA_KEYTYPE_LONGLONG:
797 RT_PAGE_MBR_KORR(share, longlong, mi_sint8korr, mi_int8store, 8, to);
798 break;
799 case HA_KEYTYPE_ULONGLONG:
800 RT_PAGE_MBR_KORR(share, ulonglong, mi_uint8korr, mi_int8store, 8, to);
801 break;
802#endif
803 case HA_KEYTYPE_FLOAT:
804 RT_PAGE_MBR_GET(share, float, mi_float4get, mi_float4store, 4, to);
805 break;
806 case HA_KEYTYPE_DOUBLE:
807 RT_PAGE_MBR_GET(share, double, mi_float8get, mi_float8store, 8, to);
808 break;
809 case HA_KEYTYPE_END:
810 return 0;
811 default:
812 return 1;
813 }
814 }
815 return 0;
816}
817
818#endif /*HAVE_RTREE_KEYS*/
819