← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to storage/myisam/rt_index.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_index.c
 
1
/* Copyright (C) 2002-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_key.h"
 
22
#include "rt_mbr.h"
 
23
 
 
24
#define REINSERT_BUFFER_INC 10
 
25
#define PICK_BY_AREA
 
26
/*#define PICK_BY_PERIMETER*/
 
27
 
 
28
typedef struct st_page_level
 
29
{
 
30
  uint level;
 
31
  my_off_t offs;
 
32
} stPageLevel;
 
33
 
 
34
typedef struct st_page_list
 
35
{   
 
36
  ulong n_pages;
 
37
  ulong m_pages;
 
38
  stPageLevel *pages;
 
39
} stPageList;
 
40
 
 
41
 
 
42
/* 
 
43
   Find next key in r-tree according to search_flag recursively
 
44
 
 
45
   NOTES
 
46
     Used in rtree_find_first() and rtree_find_next()
 
47
 
 
48
   RETURN
 
49
     -1  Error
 
50
     0   Found
 
51
     1   Not found 
 
52
*/
 
53
 
 
54
static int rtree_find_req(MI_INFO *info, MI_KEYDEF *keyinfo, uint search_flag,
 
55
                          uint nod_cmp_flag, my_off_t page, int level)
 
56
{
 
57
  uchar *k;
 
58
  uchar *last;
 
59
  uint nod_flag;
 
60
  int res;
 
61
  uchar *page_buf;
 
62
  int k_len;
 
63
  uint *saved_key = (uint*) (info->rtree_recursion_state) + level;
 
64
  
 
65
  if (!(page_buf = (uchar*)my_alloca((uint)keyinfo->block_length)))
 
66
  {
 
67
    my_errno = HA_ERR_OUT_OF_MEM;
 
68
    return -1;
 
69
  }
 
70
  if (!_mi_fetch_keypage(info, keyinfo, page, DFLT_INIT_HITS, page_buf, 0))
 
71
    goto err1;
 
72
  nod_flag = mi_test_if_nod(page_buf);
 
73
 
 
74
  k_len = keyinfo->keylength - info->s->base.rec_reflength;
 
75
  
 
76
  if(info->rtree_recursion_depth >= level)
 
77
  {
 
78
    k = page_buf + *saved_key;
 
79
  }
 
80
  else
 
81
  {
 
82
    k = rt_PAGE_FIRST_KEY(page_buf, nod_flag);
 
83
  }
 
84
  last = rt_PAGE_END(page_buf);
 
85
 
 
86
  for (; k < last; k = rt_PAGE_NEXT_KEY(k, k_len, nod_flag))
 
87
  {
 
88
    if (nod_flag) 
 
89
    { 
 
90
      /* this is an internal node in the tree */
 
91
      if (!(res = rtree_key_cmp(keyinfo->seg, info->first_mbr_key, k, 
 
92
                            info->last_rkey_length, nod_cmp_flag)))
 
93
      {
 
94
        switch ((res = rtree_find_req(info, keyinfo, search_flag, nod_cmp_flag,
 
95
                                      _mi_kpos(nod_flag, k), level + 1)))
 
96
        {
 
97
          case 0: /* found - exit from recursion */
 
98
            *saved_key = k - page_buf;
 
99
            goto ok;
 
100
          case 1: /* not found - continue searching */
 
101
            info->rtree_recursion_depth = level;
 
102
            break;
 
103
          default: /* error */
 
104
          case -1:
 
105
            goto err1;
 
106
        }
 
107
      }
 
108
    }
 
109
    else 
 
110
    { 
 
111
      /* this is a leaf */
 
112
      if (!rtree_key_cmp(keyinfo->seg, info->first_mbr_key, k, 
 
113
                         info->last_rkey_length, search_flag))
 
114
      {
 
115
        uchar *after_key = rt_PAGE_NEXT_KEY(k, k_len, nod_flag);
 
116
        info->lastpos = _mi_dpos(info, 0, after_key);
 
117
        info->lastkey_length = k_len + info->s->base.rec_reflength;
 
118
        memcpy(info->lastkey, k, info->lastkey_length);
 
119
        info->rtree_recursion_depth = level;
 
120
        *saved_key = last - page_buf;
 
121
 
 
122
        if (after_key < last)
 
123
        {
 
124
          info->int_keypos = info->buff;
 
125
          info->int_maxpos = info->buff + (last - after_key);
 
126
          memcpy(info->buff, after_key, last - after_key);
 
127
          info->buff_used = 0;
 
128
        }
 
129
        else
 
130
        {
 
131
          info->buff_used = 1;
 
132
        }
 
133
 
 
134
        res = 0;
 
135
        goto ok;
 
136
      }
 
137
    }
 
138
  }
 
139
  info->lastpos = HA_OFFSET_ERROR;
 
140
  my_errno = HA_ERR_KEY_NOT_FOUND;
 
141
  res = 1;
 
142
 
 
143
ok:
 
144
  my_afree((uchar*)page_buf);
 
145
  return res;
 
146
 
 
147
err1:
 
148
  my_afree((uchar*)page_buf);
 
149
  info->lastpos = HA_OFFSET_ERROR;
 
150
  return -1;
 
151
}
 
152
 
 
153
 
 
154
/*
 
155
  Find first key in r-tree according to search_flag condition
 
156
 
 
157
  SYNOPSIS
 
158
   rtree_find_first()
 
159
   info                 Handler to MyISAM file
 
160
   uint keynr           Key number to use
 
161
   key                  Key to search for
 
162
   key_length           Length of 'key' 
 
163
   search_flag          Bitmap of flags how to do the search
 
164
 
 
165
  RETURN
 
166
    -1  Error
 
167
    0   Found
 
168
    1   Not found
 
169
*/
 
170
 
 
171
int rtree_find_first(MI_INFO *info, uint keynr, uchar *key, uint key_length, 
 
172
                    uint search_flag)
 
173
{
 
174
  my_off_t root;
 
175
  uint nod_cmp_flag;
 
176
  MI_KEYDEF *keyinfo = info->s->keyinfo + keynr;
 
177
 
 
178
  if ((root = info->s->state.key_root[keynr]) == HA_OFFSET_ERROR)
 
179
  {
 
180
    my_errno= HA_ERR_END_OF_FILE;
 
181
    return -1;
 
182
  }
 
183
 
 
184
  /*
 
185
    Save searched key, include data pointer.
 
186
    The data pointer is required if the search_flag contains MBR_DATA.
 
187
    (minimum bounding rectangle)
 
188
  */
 
189
  memcpy(info->first_mbr_key, key, keyinfo->keylength);
 
190
  info->last_rkey_length = key_length;
 
191
 
 
192
  info->rtree_recursion_depth = -1;
 
193
  info->buff_used = 1;
 
194
  
 
195
  nod_cmp_flag = ((search_flag & (MBR_EQUAL | MBR_WITHIN)) ? 
 
196
        MBR_WITHIN : MBR_INTERSECT);
 
197
  return rtree_find_req(info, keyinfo, search_flag, nod_cmp_flag, root, 0);
 
198
}
 
199
 
 
200
 
 
201
/* 
 
202
   Find next key in r-tree according to search_flag condition
 
203
 
 
204
  SYNOPSIS
 
205
   rtree_find_next()
 
206
   info                 Handler to MyISAM file
 
207
   uint keynr           Key number to use
 
208
   search_flag          Bitmap of flags how to do the search
 
209
 
 
210
   RETURN
 
211
     -1  Error
 
212
     0   Found
 
213
     1   Not found
 
214
*/
 
215
 
 
216
int rtree_find_next(MI_INFO *info, uint keynr, uint search_flag)
 
217
{
 
218
  my_off_t root;
 
219
  uint nod_cmp_flag;
 
220
  MI_KEYDEF *keyinfo = info->s->keyinfo + keynr;
 
221
 
 
222
  if (info->update & HA_STATE_DELETED)
 
223
    return rtree_find_first(info, keynr, info->lastkey, info->lastkey_length,
 
224
                            search_flag);
 
225
 
 
226
  if (!info->buff_used)
 
227
  {
 
228
    uchar *key= info->int_keypos;
 
229
 
 
230
    while (key < info->int_maxpos)
 
231
    {
 
232
      if (!rtree_key_cmp(keyinfo->seg, info->first_mbr_key, key, 
 
233
                         info->last_rkey_length, search_flag))
 
234
      {
 
235
        uchar *after_key = key + keyinfo->keylength;
 
236
 
 
237
        info->lastpos= _mi_dpos(info, 0, after_key);
 
238
        memcpy(info->lastkey, key, info->lastkey_length);
 
239
 
 
240
        if (after_key < info->int_maxpos)
 
241
          info->int_keypos= after_key;
 
242
        else
 
243
          info->buff_used= 1;
 
244
        return 0;
 
245
      }
 
246
      key+= keyinfo->keylength;
 
247
    }
 
248
  }
 
249
  if ((root = info->s->state.key_root[keynr]) == HA_OFFSET_ERROR)
 
250
  {
 
251
    my_errno= HA_ERR_END_OF_FILE;
 
252
    return -1;
 
253
  }
 
254
  
 
255
  nod_cmp_flag = ((search_flag & (MBR_EQUAL | MBR_WITHIN)) ? 
 
256
        MBR_WITHIN : MBR_INTERSECT);
 
257
  return rtree_find_req(info, keyinfo, search_flag, nod_cmp_flag, root, 0);
 
258
}
 
259
 
 
260
 
 
261
/*
 
262
  Get next key in r-tree recursively
 
263
 
 
264
  NOTES
 
265
    Used in rtree_get_first() and rtree_get_next()
 
266
 
 
267
  RETURN
 
268
    -1  Error
 
269
    0   Found
 
270
    1   Not found
 
271
*/
 
272
 
 
273
static int rtree_get_req(MI_INFO *info, MI_KEYDEF *keyinfo, uint key_length, 
 
274
                         my_off_t page, int level)
 
275
{
 
276
  uchar *k;
 
277
  uchar *last;
 
278
  uint nod_flag;
 
279
  int res;
 
280
  uchar *page_buf;
 
281
  uint k_len;
 
282
  uint *saved_key = (uint*) (info->rtree_recursion_state) + level;
 
283
  
 
284
  if (!(page_buf = (uchar*)my_alloca((uint)keyinfo->block_length)))
 
285
    return -1;
 
286
  if (!_mi_fetch_keypage(info, keyinfo, page, DFLT_INIT_HITS, page_buf, 0))
 
287
    goto err1;
 
288
  nod_flag = mi_test_if_nod(page_buf);
 
289
 
 
290
  k_len = keyinfo->keylength - info->s->base.rec_reflength;
 
291
 
 
292
  if(info->rtree_recursion_depth >= level)
 
293
  {
 
294
    k = page_buf + *saved_key;
 
295
    if (!nod_flag)
 
296
    {
 
297
      /* Only leaf pages contain data references. */
 
298
      /* Need to check next key with data reference. */
 
299
      k = rt_PAGE_NEXT_KEY(k, k_len, nod_flag);
 
300
    }
 
301
  }
 
302
  else
 
303
  {
 
304
    k = rt_PAGE_FIRST_KEY(page_buf, nod_flag);
 
305
  }
 
306
  last = rt_PAGE_END(page_buf);
 
307
 
 
308
  for (; k < last; k = rt_PAGE_NEXT_KEY(k, k_len, nod_flag))
 
309
  {
 
310
    if (nod_flag) 
 
311
    { 
 
312
      /* this is an internal node in the tree */
 
313
      switch ((res = rtree_get_req(info, keyinfo, key_length, 
 
314
                                  _mi_kpos(nod_flag, k), level + 1)))
 
315
      {
 
316
        case 0: /* found - exit from recursion */
 
317
          *saved_key = k - page_buf;
 
318
          goto ok;
 
319
        case 1: /* not found - continue searching */
 
320
          info->rtree_recursion_depth = level;
 
321
          break;
 
322
        default:
 
323
        case -1: /* error */
 
324
          goto err1;
 
325
      }
 
326
    }
 
327
    else 
 
328
    { 
 
329
      /* this is a leaf */
 
330
      uchar *after_key = rt_PAGE_NEXT_KEY(k, k_len, nod_flag);
 
331
      info->lastpos = _mi_dpos(info, 0, after_key);
 
332
      info->lastkey_length = k_len + info->s->base.rec_reflength;
 
333
      memcpy(info->lastkey, k, info->lastkey_length);
 
334
 
 
335
      info->rtree_recursion_depth = level;
 
336
      *saved_key = k - page_buf;
 
337
 
 
338
      if (after_key < last)
 
339
      {
 
340
        info->int_keypos = (uchar*)saved_key;
 
341
        memcpy(info->buff, page_buf, keyinfo->block_length);
 
342
        info->int_maxpos = rt_PAGE_END(info->buff);
 
343
        info->buff_used = 0;
 
344
      }
 
345
      else
 
346
      {
 
347
        info->buff_used = 1;
 
348
      }
 
349
 
 
350
      res = 0;
 
351
      goto ok;
 
352
    }
 
353
  }
 
354
  info->lastpos = HA_OFFSET_ERROR;
 
355
  my_errno = HA_ERR_KEY_NOT_FOUND;
 
356
  res = 1;
 
357
 
 
358
ok:
 
359
  my_afree((uchar*)page_buf);
 
360
  return res;
 
361
 
 
362
err1:
 
363
  my_afree((uchar*)page_buf);
 
364
  info->lastpos = HA_OFFSET_ERROR;
 
365
  return -1;
 
366
}
 
367
 
 
368
 
 
369
/*
 
370
  Get first key in r-tree
 
371
 
 
372
  RETURN
 
373
    -1  Error
 
374
    0   Found
 
375
    1   Not found
 
376
*/
 
377
 
 
378
int rtree_get_first(MI_INFO *info, uint keynr, uint key_length)
 
379
{
 
380
  my_off_t root;
 
381
  MI_KEYDEF *keyinfo = info->s->keyinfo + keynr;
 
382
 
 
383
  if ((root = info->s->state.key_root[keynr]) == HA_OFFSET_ERROR)
 
384
  {
 
385
    my_errno= HA_ERR_END_OF_FILE;
 
386
    return -1;
 
387
  }
 
388
 
 
389
  info->rtree_recursion_depth = -1;
 
390
  info->buff_used = 1;
 
391
  
 
392
  return rtree_get_req(info, &keyinfo[keynr], key_length, root, 0);
 
393
}
 
394
 
 
395
 
 
396
/* 
 
397
  Get next key in r-tree
 
398
 
 
399
  RETURN
 
400
    -1  Error
 
401
    0   Found
 
402
    1   Not found
 
403
*/
 
404
 
 
405
int rtree_get_next(MI_INFO *info, uint keynr, uint key_length)
 
406
{
 
407
  my_off_t root;
 
408
  MI_KEYDEF *keyinfo = info->s->keyinfo + keynr;
 
409
 
 
410
  if (!info->buff_used)
 
411
  {
 
412
    uint k_len = keyinfo->keylength - info->s->base.rec_reflength;
 
413
    /* rt_PAGE_NEXT_KEY(info->int_keypos) */
 
414
    uchar *key = info->buff + *(int*)info->int_keypos + k_len + 
 
415
                 info->s->base.rec_reflength;
 
416
    /* rt_PAGE_NEXT_KEY(key) */
 
417
    uchar *after_key = key + k_len + info->s->base.rec_reflength; 
 
418
 
 
419
    info->lastpos = _mi_dpos(info, 0, after_key);
 
420
    info->lastkey_length = k_len + info->s->base.rec_reflength;
 
421
    memcpy(info->lastkey, key, k_len + info->s->base.rec_reflength);
 
422
 
 
423
    *(int*)info->int_keypos = key - info->buff;
 
424
    if (after_key >= info->int_maxpos)
 
425
    {
 
426
      info->buff_used = 1;
 
427
    }
 
428
 
 
429
    return 0;
 
430
  }
 
431
  else
 
432
  {
 
433
    if ((root = info->s->state.key_root[keynr]) == HA_OFFSET_ERROR)
 
434
    {
 
435
      my_errno= HA_ERR_END_OF_FILE;
 
436
      return -1;
 
437
    }
 
438
  
 
439
    return rtree_get_req(info, &keyinfo[keynr], key_length, root, 0);
 
440
  }
 
441
}
 
442
 
 
443
 
 
444
/*
 
445
  Choose non-leaf better key for insertion
 
446
*/
 
447
 
 
448
#ifdef PICK_BY_PERIMETER
 
449
static uchar *rtree_pick_key(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *key, 
 
450
                             uint key_length, uchar *page_buf, uint nod_flag)
 
451
{
 
452
  double increase;
 
453
  double best_incr = DBL_MAX;
 
454
  double perimeter;
 
455
  double best_perimeter;
 
456
  uchar *best_key;
 
457
  uchar *k = rt_PAGE_FIRST_KEY(page_buf, nod_flag);
 
458
  uchar *last = rt_PAGE_END(page_buf);
 
459
 
 
460
  LINT_INIT(best_perimeter);
 
461
  LINT_INIT(best_key);
 
462
 
 
463
  for (; k < last; k = rt_PAGE_NEXT_KEY(k, key_length, nod_flag))
 
464
  {
 
465
    if ((increase = rtree_perimeter_increase(keyinfo->seg, k, key, key_length,
 
466
                                             &perimeter)) == -1)
 
467
      return NULL;
 
468
    if ((increase < best_incr)||
 
469
        (increase == best_incr && perimeter < best_perimeter))
 
470
    {
 
471
      best_key = k;
 
472
      best_perimeter= perimeter;
 
473
      best_incr = increase;
 
474
    }
 
475
  }
 
476
  return best_key;
 
477
}
 
478
 
 
479
#endif /*PICK_BY_PERIMETER*/
 
480
 
 
481
#ifdef PICK_BY_AREA
 
482
static uchar *rtree_pick_key(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *key, 
 
483
                             uint key_length, uchar *page_buf, uint nod_flag)
 
484
{
 
485
  double increase;
 
486
  double best_incr;
 
487
  double area;
 
488
  double best_area;
 
489
  uchar *best_key= NULL;
 
490
  uchar *k = rt_PAGE_FIRST_KEY(page_buf, nod_flag);
 
491
  uchar *last = rt_PAGE_END(page_buf);
 
492
 
 
493
  LINT_INIT(best_area);
 
494
  LINT_INIT(best_key);
 
495
  LINT_INIT(best_incr);
 
496
 
 
497
  for (; k < last; k = rt_PAGE_NEXT_KEY(k, key_length, nod_flag))
 
498
  {
 
499
    /* The following is safe as -1.0 is an exact number */
 
500
    if ((increase = rtree_area_increase(keyinfo->seg, k, key, key_length, 
 
501
                                        &area)) == -1.0)
 
502
      return NULL;
 
503
    /* The following should be safe, even if we compare doubles */
 
504
    if (!best_key || increase < best_incr ||
 
505
        ((increase == best_incr) && (area < best_area)))
 
506
    {
 
507
      best_key = k;
 
508
      best_area = area;
 
509
      best_incr = increase;
 
510
    }
 
511
  }
 
512
  return best_key;
 
513
}
 
514
 
 
515
#endif /*PICK_BY_AREA*/
 
516
 
 
517
/*
 
518
  Go down and insert key into tree
 
519
 
 
520
  RETURN
 
521
    -1  Error
 
522
    0   Child was not split
 
523
    1   Child was split
 
524
*/
 
525
 
 
526
static int rtree_insert_req(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *key, 
 
527
                            uint key_length, my_off_t page, my_off_t *new_page, 
 
528
                            int ins_level, int level)
 
529
{
 
530
  uchar *k;
 
531
  uint nod_flag;
 
532
  uchar *page_buf;
 
533
  int res;
 
534
  DBUG_ENTER("rtree_insert_req");
 
535
 
 
536
  if (!(page_buf = (uchar*)my_alloca((uint)keyinfo->block_length + 
 
537
                                     MI_MAX_KEY_BUFF)))
 
538
  {
 
539
    my_errno = HA_ERR_OUT_OF_MEM;
 
540
    DBUG_RETURN(-1); /* purecov: inspected */
 
541
  }
 
542
  if (!_mi_fetch_keypage(info, keyinfo, page, DFLT_INIT_HITS, page_buf, 0))
 
543
    goto err1;
 
544
  nod_flag = mi_test_if_nod(page_buf);
 
545
  DBUG_PRINT("rtree", ("page: %lu  level: %d  ins_level: %d  nod_flag: %u",
 
546
                       (ulong) page, level, ins_level, nod_flag));
 
547
 
 
548
  if ((ins_level == -1 && nod_flag) ||       /* key: go down to leaf */
 
549
      (ins_level > -1 && ins_level > level)) /* branch: go down to ins_level */
 
550
  { 
 
551
    if ((k = rtree_pick_key(info, keyinfo, key, key_length, page_buf, 
 
552
                             nod_flag)) == NULL)
 
553
      goto err1;
 
554
    switch ((res = rtree_insert_req(info, keyinfo, key, key_length, 
 
555
                     _mi_kpos(nod_flag, k), new_page, ins_level, level + 1)))
 
556
    {
 
557
      case 0: /* child was not split */
 
558
      {
 
559
        rtree_combine_rect(keyinfo->seg, k, key, k, key_length);
 
560
        if (_mi_write_keypage(info, keyinfo, page, DFLT_INIT_HITS, page_buf))
 
561
          goto err1;
 
562
        goto ok;
 
563
      }
 
564
      case 1: /* child was split */
 
565
      {
 
566
        uchar *new_key = page_buf + keyinfo->block_length + nod_flag;
 
567
        /* set proper MBR for key */
 
568
        if (rtree_set_key_mbr(info, keyinfo, k, key_length, 
 
569
                            _mi_kpos(nod_flag, k)))
 
570
          goto err1;
 
571
        /* add new key for new page */
 
572
        _mi_kpointer(info, new_key - nod_flag, *new_page);
 
573
        if (rtree_set_key_mbr(info, keyinfo, new_key, key_length, *new_page))
 
574
          goto err1;
 
575
        res = rtree_add_key(info, keyinfo, new_key, key_length, 
 
576
                           page_buf, new_page);
 
577
        if (_mi_write_keypage(info, keyinfo, page, DFLT_INIT_HITS, page_buf))
 
578
          goto err1;
 
579
        goto ok;
 
580
      }
 
581
      default:
 
582
      case -1: /* error */
 
583
      {
 
584
        goto err1;
 
585
      }
 
586
    }
 
587
  }
 
588
  else
 
589
  { 
 
590
    res = rtree_add_key(info, keyinfo, key, key_length, page_buf, new_page);
 
591
    if (_mi_write_keypage(info, keyinfo, page, DFLT_INIT_HITS, page_buf))
 
592
      goto err1;
 
593
    goto ok;
 
594
  }
 
595
 
 
596
ok:
 
597
  my_afree((uchar*)page_buf);
 
598
  DBUG_RETURN(res);
 
599
 
 
600
err1:
 
601
  my_afree((uchar*)page_buf);
 
602
  DBUG_RETURN(-1); /* purecov: inspected */
 
603
}
 
604
 
 
605
 
 
606
/*
 
607
  Insert key into the tree
 
608
 
 
609
  RETURN
 
610
    -1  Error
 
611
    0   Root was not split
 
612
    1   Root was split
 
613
*/
 
614
 
 
615
static int rtree_insert_level(MI_INFO *info, uint keynr, uchar *key, 
 
616
                             uint key_length, int ins_level)
 
617
{
 
618
  my_off_t old_root;
 
619
  MI_KEYDEF *keyinfo = info->s->keyinfo + keynr;
 
620
  int res;
 
621
  my_off_t new_page;
 
622
  DBUG_ENTER("rtree_insert_level");
 
623
 
 
624
  if ((old_root = info->s->state.key_root[keynr]) == HA_OFFSET_ERROR)
 
625
  {
 
626
    if ((old_root = _mi_new(info, keyinfo, DFLT_INIT_HITS)) == HA_OFFSET_ERROR)
 
627
      DBUG_RETURN(-1);
 
628
    info->buff_used = 1;
 
629
    mi_putint(info->buff, 2, 0);
 
630
    res = rtree_add_key(info, keyinfo, key, key_length, info->buff, NULL);
 
631
    if (_mi_write_keypage(info, keyinfo, old_root, DFLT_INIT_HITS, info->buff))
 
632
      DBUG_RETURN(1);
 
633
    info->s->state.key_root[keynr] = old_root;
 
634
    DBUG_RETURN(res);
 
635
  }
 
636
 
 
637
  switch ((res = rtree_insert_req(info, keyinfo, key, key_length, 
 
638
                                  old_root, &new_page, ins_level, 0)))
 
639
  {
 
640
    case 0: /* root was not split */
 
641
    {
 
642
      break;
 
643
    }
 
644
    case 1: /* root was split, grow a new root */
 
645
    { 
 
646
      uchar *new_root_buf;
 
647
      my_off_t new_root;
 
648
      uchar *new_key;
 
649
      uint nod_flag = info->s->base.key_reflength;
 
650
 
 
651
      DBUG_PRINT("rtree", ("root was split, grow a new root"));
 
652
      if (!(new_root_buf = (uchar*)my_alloca((uint)keyinfo->block_length + 
 
653
                                             MI_MAX_KEY_BUFF)))
 
654
      {
 
655
        my_errno = HA_ERR_OUT_OF_MEM;
 
656
        DBUG_RETURN(-1); /* purecov: inspected */
 
657
      }
 
658
 
 
659
      mi_putint(new_root_buf, 2, nod_flag);
 
660
      if ((new_root = _mi_new(info, keyinfo, DFLT_INIT_HITS)) ==
 
661
          HA_OFFSET_ERROR)
 
662
        goto err1;
 
663
 
 
664
      new_key = new_root_buf + keyinfo->block_length + nod_flag;
 
665
 
 
666
      _mi_kpointer(info, new_key - nod_flag, old_root);
 
667
      if (rtree_set_key_mbr(info, keyinfo, new_key, key_length, old_root))
 
668
        goto err1;
 
669
      if (rtree_add_key(info, keyinfo, new_key, key_length, new_root_buf, NULL) 
 
670
          == -1)
 
671
        goto err1;
 
672
      _mi_kpointer(info, new_key - nod_flag, new_page);
 
673
      if (rtree_set_key_mbr(info, keyinfo, new_key, key_length, new_page))
 
674
        goto err1;
 
675
      if (rtree_add_key(info, keyinfo, new_key, key_length, new_root_buf, NULL) 
 
676
          == -1)
 
677
        goto err1;
 
678
      if (_mi_write_keypage(info, keyinfo, new_root,
 
679
                            DFLT_INIT_HITS, new_root_buf))
 
680
        goto err1;
 
681
      info->s->state.key_root[keynr] = new_root;
 
682
      DBUG_PRINT("rtree", ("new root page: %lu  level: %d  nod_flag: %u",
 
683
                           (ulong) new_root, 0, mi_test_if_nod(new_root_buf)));
 
684
 
 
685
      my_afree((uchar*)new_root_buf);
 
686
      break;
 
687
err1:
 
688
      my_afree((uchar*)new_root_buf);
 
689
      DBUG_RETURN(-1); /* purecov: inspected */
 
690
    }
 
691
    default:
 
692
    case -1: /* error */
 
693
    {
 
694
      break;
 
695
    }
 
696
  }
 
697
  DBUG_RETURN(res);
 
698
}
 
699
 
 
700
 
 
701
/*
 
702
  Insert key into the tree - interface function
 
703
 
 
704
  RETURN
 
705
    -1  Error
 
706
    0   OK
 
707
*/
 
708
 
 
709
int rtree_insert(MI_INFO *info, uint keynr, uchar *key, uint key_length)
 
710
{
 
711
  DBUG_ENTER("rtree_insert");
 
712
  DBUG_RETURN((!key_length ||
 
713
               (rtree_insert_level(info, keynr, key, key_length, -1) == -1)) ?
 
714
              -1 : 0);
 
715
}
 
716
 
 
717
 
 
718
/* 
 
719
  Fill reinsert page buffer 
 
720
 
 
721
  RETURN
 
722
    -1  Error
 
723
    0   OK
 
724
*/
 
725
 
 
726
static int rtree_fill_reinsert_list(stPageList *ReinsertList, my_off_t page, 
 
727
                                    int level)
 
728
{
 
729
  DBUG_ENTER("rtree_fill_reinsert_list");
 
730
  DBUG_PRINT("rtree", ("page: %lu  level: %d", (ulong) page, level));
 
731
  if (ReinsertList->n_pages == ReinsertList->m_pages)
 
732
  {
 
733
    ReinsertList->m_pages += REINSERT_BUFFER_INC;
 
734
    if (!(ReinsertList->pages = (stPageLevel*)my_realloc((uchar*)ReinsertList->pages, 
 
735
      ReinsertList->m_pages * sizeof(stPageLevel), MYF(MY_ALLOW_ZERO_PTR))))
 
736
      goto err1;
 
737
  }
 
738
  /* save page to ReinsertList */
 
739
  ReinsertList->pages[ReinsertList->n_pages].offs = page;
 
740
  ReinsertList->pages[ReinsertList->n_pages].level = level;
 
741
  ReinsertList->n_pages++;
 
742
  DBUG_RETURN(0);
 
743
 
 
744
err1:
 
745
  DBUG_RETURN(-1); /* purecov: inspected */
 
746
}
 
747
 
 
748
 
 
749
/*
 
750
  Go down and delete key from the tree
 
751
 
 
752
  RETURN
 
753
    -1  Error
 
754
    0   Deleted
 
755
    1   Not found
 
756
    2   Empty leaf
 
757
*/
 
758
 
 
759
static int rtree_delete_req(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *key, 
 
760
                           uint key_length, my_off_t page, uint *page_size, 
 
761
                           stPageList *ReinsertList, int level)
 
762
{
 
763
  uchar *k;
 
764
  uchar *last;
 
765
  ulong i;
 
766
  uint nod_flag;
 
767
  uchar *page_buf;
 
768
  int res;
 
769
  DBUG_ENTER("rtree_delete_req");
 
770
 
 
771
  if (!(page_buf = (uchar*)my_alloca((uint)keyinfo->block_length)))
 
772
  {
 
773
    my_errno = HA_ERR_OUT_OF_MEM;
 
774
    DBUG_RETURN(-1); /* purecov: inspected */
 
775
  }
 
776
  if (!_mi_fetch_keypage(info, keyinfo, page, DFLT_INIT_HITS, page_buf, 0))
 
777
    goto err1;
 
778
  nod_flag = mi_test_if_nod(page_buf);
 
779
  DBUG_PRINT("rtree", ("page: %lu  level: %d  nod_flag: %u",
 
780
                       (ulong) page, level, nod_flag));
 
781
 
 
782
  k = rt_PAGE_FIRST_KEY(page_buf, nod_flag);
 
783
  last = rt_PAGE_END(page_buf);
 
784
 
 
785
  for (i = 0; k < last; k = rt_PAGE_NEXT_KEY(k, key_length, nod_flag), ++i)
 
786
  {
 
787
    if (nod_flag)
 
788
    { 
 
789
      /* not leaf */
 
790
      if (!rtree_key_cmp(keyinfo->seg, key, k, key_length, MBR_WITHIN))
 
791
      {
 
792
        switch ((res = rtree_delete_req(info, keyinfo, key, key_length, 
 
793
                  _mi_kpos(nod_flag, k), page_size, ReinsertList, level + 1)))
 
794
        {
 
795
          case 0: /* deleted */
 
796
          { 
 
797
            /* test page filling */
 
798
            if (*page_size + key_length >= rt_PAGE_MIN_SIZE(keyinfo->block_length)) 
 
799
            { 
 
800
              /* OK */
 
801
              /* Calculate a new key value (MBR) for the shrinked block. */
 
802
              if (rtree_set_key_mbr(info, keyinfo, k, key_length, 
 
803
                                  _mi_kpos(nod_flag, k)))
 
804
                goto err1;
 
805
              if (_mi_write_keypage(info, keyinfo, page,
 
806
                                    DFLT_INIT_HITS, page_buf))
 
807
                goto err1;
 
808
            }
 
809
            else
 
810
            { 
 
811
              /*
 
812
                Too small: delete key & add it descendant to reinsert list.
 
813
                Store position and level of the block so that it can be
 
814
                accessed later for inserting the remaining keys.
 
815
              */
 
816
              DBUG_PRINT("rtree", ("too small. move block to reinsert list"));
 
817
              if (rtree_fill_reinsert_list(ReinsertList, _mi_kpos(nod_flag, k),
 
818
                                           level + 1))
 
819
                goto err1;
 
820
              /*
 
821
                Delete the key that references the block. This makes the
 
822
                block disappear from the index. Hence we need to insert
 
823
                its remaining keys later. Note: if the block is a branch
 
824
                block, we do not only remove this block, but the whole
 
825
                subtree. So we need to re-insert its keys on the same
 
826
                level later to reintegrate the subtrees.
 
827
              */
 
828
              rtree_delete_key(info, page_buf, k, key_length, nod_flag);
 
829
              if (_mi_write_keypage(info, keyinfo, page,
 
830
                                    DFLT_INIT_HITS, page_buf))
 
831
                goto err1;
 
832
              *page_size = mi_getint(page_buf);
 
833
            }
 
834
            
 
835
            goto ok;
 
836
          }
 
837
          case 1: /* not found - continue searching */
 
838
          {
 
839
            break;
 
840
          }
 
841
          case 2: /* vacuous case: last key in the leaf */
 
842
          {
 
843
            rtree_delete_key(info, page_buf, k, key_length, nod_flag);
 
844
            if (_mi_write_keypage(info, keyinfo, page,
 
845
                                  DFLT_INIT_HITS, page_buf))
 
846
              goto err1;
 
847
            *page_size = mi_getint(page_buf);
 
848
            res = 0;
 
849
            goto ok;
 
850
          }
 
851
          default: /* error */
 
852
          case -1:
 
853
          {
 
854
            goto err1;
 
855
          }
 
856
        }
 
857
      }
 
858
    }
 
859
    else  
 
860
    {
 
861
      /* leaf */
 
862
      if (!rtree_key_cmp(keyinfo->seg, key, k, key_length, MBR_EQUAL | MBR_DATA))
 
863
      {
 
864
        rtree_delete_key(info, page_buf, k, key_length, nod_flag);
 
865
        *page_size = mi_getint(page_buf);
 
866
        if (*page_size == 2) 
 
867
        {
 
868
          /* last key in the leaf */
 
869
          res = 2;
 
870
          if (_mi_dispose(info, keyinfo, page, DFLT_INIT_HITS))
 
871
            goto err1;
 
872
        }
 
873
        else
 
874
        {
 
875
          res = 0;
 
876
          if (_mi_write_keypage(info, keyinfo, page, DFLT_INIT_HITS, page_buf))
 
877
            goto err1;
 
878
        }
 
879
        goto ok;
 
880
      }
 
881
    }
 
882
  }
 
883
  res = 1;
 
884
 
 
885
ok:
 
886
  my_afree((uchar*)page_buf);
 
887
  DBUG_RETURN(res);
 
888
 
 
889
err1:
 
890
  my_afree((uchar*)page_buf);
 
891
  DBUG_RETURN(-1); /* purecov: inspected */
 
892
}
 
893
 
 
894
 
 
895
/*
 
896
  Delete key - interface function
 
897
 
 
898
  RETURN
 
899
    -1  Error
 
900
    0   Deleted
 
901
*/
 
902
 
 
903
int rtree_delete(MI_INFO *info, uint keynr, uchar *key, uint key_length)
 
904
{
 
905
  uint page_size;
 
906
  stPageList ReinsertList;
 
907
  my_off_t old_root;
 
908
  MI_KEYDEF *keyinfo = info->s->keyinfo + keynr;
 
909
  DBUG_ENTER("rtree_delete");
 
910
 
 
911
  if ((old_root = info->s->state.key_root[keynr]) == HA_OFFSET_ERROR)
 
912
  {
 
913
    my_errno= HA_ERR_END_OF_FILE;
 
914
    DBUG_RETURN(-1); /* purecov: inspected */
 
915
  }
 
916
  DBUG_PRINT("rtree", ("starting deletion at root page: %lu",
 
917
                       (ulong) old_root));
 
918
 
 
919
  ReinsertList.pages = NULL;
 
920
  ReinsertList.n_pages = 0;
 
921
  ReinsertList.m_pages = 0;
 
922
  
 
923
  switch (rtree_delete_req(info, keyinfo, key, key_length, old_root, 
 
924
                                 &page_size, &ReinsertList, 0))
 
925
  {
 
926
    case 2: /* empty */
 
927
    {
 
928
      info->s->state.key_root[keynr] = HA_OFFSET_ERROR;
 
929
      DBUG_RETURN(0);
 
930
    }
 
931
    case 0: /* deleted */
 
932
    {
 
933
      uint nod_flag;
 
934
      ulong i;
 
935
      for (i = 0; i < ReinsertList.n_pages; ++i)
 
936
      {
 
937
        uchar *page_buf;
 
938
        uchar *k;
 
939
        uchar *last;
 
940
 
 
941
        if (!(page_buf = (uchar*)my_alloca((uint)keyinfo->block_length)))
 
942
        {
 
943
          my_errno = HA_ERR_OUT_OF_MEM;
 
944
          goto err1;
 
945
        }
 
946
        if (!_mi_fetch_keypage(info, keyinfo, ReinsertList.pages[i].offs, 
 
947
                               DFLT_INIT_HITS, page_buf, 0))
 
948
          goto err1;
 
949
        nod_flag = mi_test_if_nod(page_buf);
 
950
        DBUG_PRINT("rtree", ("reinserting keys from "
 
951
                             "page: %lu  level: %d  nod_flag: %u",
 
952
                             (ulong) ReinsertList.pages[i].offs,
 
953
                             ReinsertList.pages[i].level, nod_flag));
 
954
 
 
955
        k = rt_PAGE_FIRST_KEY(page_buf, nod_flag);
 
956
        last = rt_PAGE_END(page_buf);
 
957
        for (; k < last; k = rt_PAGE_NEXT_KEY(k, key_length, nod_flag))
 
958
        {
 
959
          int res;
 
960
          if ((res= rtree_insert_level(info, keynr, k, key_length,
 
961
                                       ReinsertList.pages[i].level)) == -1)
 
962
          {
 
963
            my_afree((uchar*)page_buf);
 
964
            goto err1;
 
965
          }
 
966
          if (res)
 
967
          {
 
968
            ulong j;
 
969
            DBUG_PRINT("rtree", ("root has been split, adjust levels"));
 
970
            for (j= i; j < ReinsertList.n_pages; j++)
 
971
            {
 
972
              ReinsertList.pages[j].level++;
 
973
              DBUG_PRINT("rtree", ("keys from page: %lu  now level: %d",
 
974
                                   (ulong) ReinsertList.pages[i].offs,
 
975
                                   ReinsertList.pages[i].level));
 
976
            }
 
977
          }
 
978
        }
 
979
        my_afree((uchar*)page_buf);
 
980
        if (_mi_dispose(info, keyinfo, ReinsertList.pages[i].offs,
 
981
            DFLT_INIT_HITS))
 
982
          goto err1;
 
983
      }
 
984
      if (ReinsertList.pages)
 
985
        my_free((uchar*) ReinsertList.pages, MYF(0));
 
986
 
 
987
      /* check for redundant root (not leaf, 1 child) and eliminate */
 
988
      if ((old_root = info->s->state.key_root[keynr]) == HA_OFFSET_ERROR)
 
989
        goto err1;
 
990
      if (!_mi_fetch_keypage(info, keyinfo, old_root, DFLT_INIT_HITS,
 
991
                             info->buff, 0))
 
992
        goto err1;
 
993
      nod_flag = mi_test_if_nod(info->buff);
 
994
      page_size = mi_getint(info->buff);
 
995
      if (nod_flag && (page_size == 2 + key_length + nod_flag))
 
996
      {
 
997
        my_off_t new_root = _mi_kpos(nod_flag,
 
998
                                     rt_PAGE_FIRST_KEY(info->buff, nod_flag));
 
999
        if (_mi_dispose(info, keyinfo, old_root, DFLT_INIT_HITS))
 
1000
          goto err1;
 
1001
        info->s->state.key_root[keynr] = new_root;
 
1002
      }
 
1003
      info->update= HA_STATE_DELETED;
 
1004
      DBUG_RETURN(0);
 
1005
 
 
1006
err1:
 
1007
      DBUG_RETURN(-1); /* purecov: inspected */
 
1008
    }
 
1009
    case 1: /* not found */
 
1010
    {
 
1011
      my_errno = HA_ERR_KEY_NOT_FOUND;
 
1012
      DBUG_RETURN(-1); /* purecov: inspected */
 
1013
    }
 
1014
    default:
 
1015
    case -1: /* error */
 
1016
    {
 
1017
      DBUG_RETURN(-1); /* purecov: inspected */
 
1018
    }
 
1019
  }
 
1020
}
 
1021
 
 
1022
 
 
1023
/* 
 
1024
  Estimate number of suitable keys in the tree 
 
1025
 
 
1026
  RETURN
 
1027
    estimated value
 
1028
*/
 
1029
 
 
1030
ha_rows rtree_estimate(MI_INFO *info, uint keynr, uchar *key, 
 
1031
                       uint key_length, uint flag)
 
1032
{
 
1033
  MI_KEYDEF *keyinfo = info->s->keyinfo + keynr;
 
1034
  my_off_t root;
 
1035
  uint i = 0;
 
1036
  uchar *k;
 
1037
  uchar *last;
 
1038
  uint nod_flag;
 
1039
  uchar *page_buf;
 
1040
  uint k_len;
 
1041
  double area = 0;
 
1042
  ha_rows res = 0;
 
1043
 
 
1044
  if (flag & MBR_DISJOINT)
 
1045
    return info->state->records;
 
1046
 
 
1047
  if ((root = info->s->state.key_root[keynr]) == HA_OFFSET_ERROR)
 
1048
    return HA_POS_ERROR;
 
1049
  if (!(page_buf = (uchar*)my_alloca((uint)keyinfo->block_length)))
 
1050
    return HA_POS_ERROR;
 
1051
  if (!_mi_fetch_keypage(info, keyinfo, root, DFLT_INIT_HITS, page_buf, 0))
 
1052
    goto err1;
 
1053
  nod_flag = mi_test_if_nod(page_buf);
 
1054
 
 
1055
  k_len = keyinfo->keylength - info->s->base.rec_reflength;
 
1056
 
 
1057
  k = rt_PAGE_FIRST_KEY(page_buf, nod_flag);
 
1058
  last = rt_PAGE_END(page_buf);
 
1059
 
 
1060
  for (; k < last; k = rt_PAGE_NEXT_KEY(k, k_len, nod_flag), ++i)
 
1061
  {
 
1062
    if (nod_flag)
 
1063
    {
 
1064
      double k_area = rtree_rect_volume(keyinfo->seg, k, key_length);
 
1065
 
 
1066
      /* The following should be safe, even if we compare doubles */
 
1067
      if (k_area == 0)
 
1068
      {
 
1069
        if (flag & (MBR_CONTAIN | MBR_INTERSECT))
 
1070
        {
 
1071
          area += 1;
 
1072
        }
 
1073
        else if (flag & (MBR_WITHIN | MBR_EQUAL))
 
1074
        {
 
1075
          if (!rtree_key_cmp(keyinfo->seg, key, k, key_length, MBR_WITHIN))
 
1076
            area += 1;
 
1077
        }
 
1078
        else
 
1079
          goto err1;
 
1080
      }
 
1081
      else
 
1082
      {
 
1083
        if (flag & (MBR_CONTAIN | MBR_INTERSECT))
 
1084
        {
 
1085
          area += rtree_overlapping_area(keyinfo->seg, key, k, key_length) / 
 
1086
                  k_area;
 
1087
        }
 
1088
        else if (flag & (MBR_WITHIN | MBR_EQUAL))
 
1089
        {
 
1090
          if (!rtree_key_cmp(keyinfo->seg, key, k, key_length, MBR_WITHIN))
 
1091
            area += rtree_rect_volume(keyinfo->seg, key, key_length) /
 
1092
                    k_area;
 
1093
        }
 
1094
        else
 
1095
          goto err1;
 
1096
      }
 
1097
    }
 
1098
    else
 
1099
    {
 
1100
      if (!rtree_key_cmp(keyinfo->seg, key, k, key_length, flag))
 
1101
        ++res;
 
1102
    }
 
1103
  }
 
1104
  if (nod_flag)
 
1105
  {
 
1106
    if (i)
 
1107
      res = (ha_rows) (area / i * info->state->records);
 
1108
    else 
 
1109
      res = HA_POS_ERROR;
 
1110
  }
 
1111
 
 
1112
  my_afree((uchar*)page_buf);
 
1113
  return res;
 
1114
 
 
1115
err1:
 
1116
  my_afree((uchar*)page_buf);
 
1117
  return HA_POS_ERROR;
 
1118
}
 
1119
 
 
1120
#endif /*HAVE_RTREE_KEYS*/
 
1121