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