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