← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to storage/myisam/rt_mbr.c

  • Committer: Monty Taylor
  • Date: 2008-10-16 06:32:30 UTC
  • mto: (511.1.5 codestyle)
  • mto: This revision was merged to the branch mainline in revision 521.
  • Revision ID: monty@inaugust.com-20081016063230-4brxsra0qsmsg84q
Added -Wunused-macros.

Show diffs side-by-side

added added

removed removed

Lines of Context:
storage/myisam/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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  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 = min(amin, bmin); \
329
 
  amax = 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 = min(amin, bmin); \
342
 
  amax = 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 = max(amin, bmin); \
421
 
  amax = 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 = max(amin, bmin); \
435
 
  amax = 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)max(amax, bmax) - (double)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)max(amax, bmax) - (double)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)max(amax, bmax) - (double)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)max(amax, bmax) - (double)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*/