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*/
|