← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to storage/myisam/rt_mbr.c

  • Committer: brian
  • Date: 2008-06-25 05:29:13 UTC
  • Revision ID: brian@localhost.localdomain-20080625052913-6upwo0jsrl4lnapl
clean slate

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