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