1 : /* Copyright (C) 2006 MySQL AB & Ramil Kalimullin & MySQL Finland AB
2 : & TCX DataKonsult AB
3 :
4 : This program is free software; you can redistribute it and/or modify
5 : it under the terms of the GNU General Public License as published by
6 : the Free Software Foundation; version 2 of the License.
7 :
8 : This program is distributed in the hope that it will be useful,
9 : but WITHOUT ANY WARRANTY; without even the implied warranty of
10 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 : GNU General Public License for more details.
12 :
13 : You should have received a copy of the GNU General Public License
14 : along with this program; if not, write to the Free Software
15 : Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
16 :
17 : #include "maria_def.h"
18 : #include "trnman.h"
19 : #include "ma_key_recover.h"
20 :
21 : #ifdef HAVE_RTREE_KEYS
22 :
23 : #include "ma_rt_index.h"
24 : #include "ma_rt_key.h"
25 : #include "ma_rt_mbr.h"
26 :
27 : #define REINSERT_BUFFER_INC 10
28 : #define PICK_BY_AREA
29 : /*#define PICK_BY_PERIMETER*/
30 :
31 : typedef struct st_page_level
32 : {
33 : uint level;
34 : my_off_t offs;
35 : } stPageLevel;
36 :
37 : typedef struct st_page_list
38 : {
39 : uint n_pages;
40 : uint m_pages;
41 : stPageLevel *pages;
42 : } stPageList;
43 :
44 :
45 : /*
46 : Find next key in r-tree according to search_flag recursively
47 :
48 : NOTES
49 : Used in maria_rtree_find_first() and maria_rtree_find_next()
50 :
51 : RETURN
52 : -1 Error
53 : 0 Found
54 : 1 Not found
55 : */
56 :
57 : static int maria_rtree_find_req(MARIA_HA *info, MARIA_KEYDEF *keyinfo,
58 : uint32 search_flag,
59 : uint nod_cmp_flag, my_off_t page_pos,
60 : int level)
61 0 : {
62 0 : MARIA_SHARE *share= info->s;
63 : uint nod_flag;
64 : int res;
65 : uchar *page_buf, *k, *last;
66 : int key_data_length;
67 0 : uint *saved_key= (uint*) (info->maria_rtree_recursion_state) + level;
68 : MARIA_PAGE page;
69 :
70 0 : if (!(page_buf= (uchar*) my_alloca((uint) keyinfo->block_length)))
71 : {
72 0 : my_errno= HA_ERR_OUT_OF_MEM;
73 0 : return -1;
74 : }
75 0 : if (_ma_fetch_keypage(&page, info, keyinfo, page_pos,
76 : PAGECACHE_LOCK_LEFT_UNLOCKED,
77 : DFLT_INIT_HITS, page_buf, 0))
78 0 : goto err;
79 0 : nod_flag= page.node;
80 :
81 0 : key_data_length= keyinfo->keylength - share->base.rec_reflength;
82 :
83 0 : if (info->maria_rtree_recursion_depth >= level)
84 : {
85 0 : k= page_buf + *saved_key;
86 : }
87 : else
88 : {
89 0 : k= rt_PAGE_FIRST_KEY(share, page_buf, nod_flag);
90 : }
91 0 : last= rt_PAGE_END(&page);
92 :
93 0 : for (; k < last; k= rt_PAGE_NEXT_KEY(share, k, key_data_length, nod_flag))
94 : {
95 0 : if (nod_flag)
96 : {
97 : /* this is an internal node in the tree */
98 0 : if (!(res= maria_rtree_key_cmp(keyinfo->seg,
99 : info->first_mbr_key, k,
100 : info->last_rkey_length, nod_cmp_flag)))
101 : {
102 : switch ((res= maria_rtree_find_req(info, keyinfo, search_flag,
103 : nod_cmp_flag,
104 : _ma_kpos(nod_flag, k),
105 0 : level + 1)))
106 : {
107 : case 0: /* found - exit from recursion */
108 0 : *saved_key= k - page_buf;
109 0 : goto ok;
110 : case 1: /* not found - continue searching */
111 0 : info->maria_rtree_recursion_depth= level;
112 0 : break;
113 : default: /* error */
114 : case -1:
115 : goto err;
116 : }
117 : }
118 : }
119 : else
120 : {
121 : /* this is a leaf */
122 0 : if (!maria_rtree_key_cmp(keyinfo->seg, info->first_mbr_key,
123 : k, info->last_rkey_length, search_flag))
124 : {
125 0 : uchar *after_key= rt_PAGE_NEXT_KEY(share, k, key_data_length, 0);
126 : MARIA_KEY tmp_key;
127 :
128 : /*
129 : We don't need to set all MARIA_KEY elements here as
130 : _ma_row_pos_from_key() only uses a few of them.
131 : */
132 0 : tmp_key.keyinfo= keyinfo;
133 0 : tmp_key.data= k;
134 0 : tmp_key.data_length= key_data_length;
135 :
136 0 : info->cur_row.lastpos= _ma_row_pos_from_key(&tmp_key);
137 0 : info->last_key.keyinfo= keyinfo;
138 0 : info->last_key.data_length= key_data_length;
139 0 : info->last_key.ref_length= share->base.rec_reflength;
140 0 : info->last_key.flag= 0;
141 0 : memcpy(info->last_key.data, k,
142 : info->last_key.data_length + info->last_key.ref_length);
143 0 : info->maria_rtree_recursion_depth= level;
144 0 : *saved_key= last - page_buf;
145 :
146 0 : if (after_key < last)
147 : {
148 0 : uchar *keyread_buff= info->keyread_buff;
149 0 : info->int_keypos= keyread_buff;
150 0 : info->int_maxpos= keyread_buff + (last - after_key);
151 0 : memcpy(keyread_buff, after_key, last - after_key);
152 0 : info->keyread_buff_used= 0;
153 : }
154 : else
155 : {
156 0 : info->keyread_buff_used= 1;
157 : }
158 :
159 0 : res= 0;
160 0 : goto ok;
161 : }
162 : }
163 : }
164 0 : info->cur_row.lastpos= HA_OFFSET_ERROR;
165 0 : my_errno= HA_ERR_KEY_NOT_FOUND;
166 0 : res= 1;
167 :
168 0 : ok:
169 : my_afree(page_buf);
170 0 : return res;
171 :
172 0 : err:
173 : my_afree(page_buf);
174 0 : info->cur_row.lastpos= HA_OFFSET_ERROR;
175 0 : return -1;
176 : }
177 :
178 :
179 : /*
180 : Find first key in r-tree according to search_flag condition
181 :
182 : SYNOPSIS
183 : maria_rtree_find_first()
184 : info Handler to MARIA file
185 : key Key to search for
186 : search_flag Bitmap of flags how to do the search
187 :
188 : RETURN
189 : -1 Error
190 : 0 Found
191 : 1 Not found
192 : */
193 :
194 : int maria_rtree_find_first(MARIA_HA *info, MARIA_KEY *key, uint32 search_flag)
195 0 : {
196 : my_off_t root;
197 : uint nod_cmp_flag;
198 0 : MARIA_KEYDEF *keyinfo= key->keyinfo;
199 :
200 0 : if ((root= info->s->state.key_root[keyinfo->key_nr]) == HA_OFFSET_ERROR)
201 : {
202 0 : my_errno= HA_ERR_END_OF_FILE;
203 0 : return -1;
204 : }
205 :
206 : /*
207 : Save searched key, include data pointer.
208 : The data pointer is required if the search_flag contains MBR_DATA.
209 : (minimum bounding rectangle)
210 : */
211 0 : memcpy(info->first_mbr_key, key->data, key->data_length + key->ref_length);
212 0 : info->last_rkey_length= key->data_length;
213 :
214 0 : info->maria_rtree_recursion_depth= -1;
215 0 : info->keyread_buff_used= 1;
216 :
217 0 : nod_cmp_flag= ((search_flag & (MBR_EQUAL | MBR_WITHIN)) ?
218 : MBR_WITHIN : MBR_INTERSECT);
219 0 : return maria_rtree_find_req(info, keyinfo, search_flag, nod_cmp_flag, root,
220 : 0);
221 : }
222 :
223 :
224 : /*
225 : Find next key in r-tree according to search_flag condition
226 :
227 : SYNOPSIS
228 : maria_rtree_find_next()
229 : info Handler to MARIA file
230 : uint keynr Key number to use
231 : search_flag Bitmap of flags how to do the search
232 :
233 : RETURN
234 : -1 Error
235 : 0 Found
236 : 1 Not found
237 : */
238 :
239 : int maria_rtree_find_next(MARIA_HA *info, uint keynr, uint32 search_flag)
240 0 : {
241 : my_off_t root;
242 : uint32 nod_cmp_flag;
243 0 : MARIA_KEYDEF *keyinfo= info->s->keyinfo + keynr;
244 0 : DBUG_ASSERT(info->last_key.keyinfo == keyinfo);
245 :
246 0 : if (info->update & HA_STATE_DELETED)
247 0 : return maria_rtree_find_first(info, &info->last_key, search_flag);
248 :
249 0 : if (!info->keyread_buff_used)
250 : {
251 0 : uchar *key= info->int_keypos;
252 :
253 0 : while (key < info->int_maxpos)
254 : {
255 0 : if (!maria_rtree_key_cmp(keyinfo->seg,
256 : info->first_mbr_key, key,
257 : info->last_rkey_length, search_flag))
258 : {
259 0 : uchar *after_key= key + keyinfo->keylength;
260 : MARIA_KEY tmp_key;
261 :
262 : /*
263 : We don't need to set all MARIA_KEY elements here as
264 : _ma_row_pos_from_key only uses a few of them.
265 : */
266 0 : tmp_key.keyinfo= keyinfo;
267 0 : tmp_key.data= key;
268 0 : tmp_key.data_length= keyinfo->keylength - info->s->base.rec_reflength;
269 :
270 0 : info->cur_row.lastpos= _ma_row_pos_from_key(&tmp_key);
271 0 : memcpy(info->last_key.data, key, info->last_key.data_length);
272 :
273 0 : if (after_key < info->int_maxpos)
274 0 : info->int_keypos= after_key;
275 : else
276 0 : info->keyread_buff_used= 1;
277 0 : return 0;
278 : }
279 0 : key+= keyinfo->keylength;
280 : }
281 : }
282 0 : if ((root= info->s->state.key_root[keynr]) == HA_OFFSET_ERROR)
283 : {
284 0 : my_errno= HA_ERR_END_OF_FILE;
285 0 : return -1;
286 : }
287 :
288 0 : nod_cmp_flag= (((search_flag & (MBR_EQUAL | MBR_WITHIN)) ?
289 : MBR_WITHIN : MBR_INTERSECT));
290 0 : return maria_rtree_find_req(info, keyinfo, search_flag, nod_cmp_flag, root,
291 : 0);
292 : }
293 :
294 :
295 : /*
296 : Get next key in r-tree recursively
297 :
298 : NOTES
299 : Used in maria_rtree_get_first() and maria_rtree_get_next()
300 :
301 : RETURN
302 : -1 Error
303 : 0 Found
304 : 1 Not found
305 : */
306 :
307 : static int maria_rtree_get_req(MARIA_HA *info, MARIA_KEYDEF *keyinfo,
308 : uint key_length, my_off_t page_pos, int level)
309 0 : {
310 0 : MARIA_SHARE *share= info->s;
311 : uchar *page_buf, *last, *k;
312 : uint nod_flag, key_data_length;
313 : int res;
314 0 : uint *saved_key= (uint*) (info->maria_rtree_recursion_state) + level;
315 : MARIA_PAGE page;
316 :
317 0 : if (!(page_buf= (uchar*) my_alloca((uint) keyinfo->block_length)))
318 0 : return -1;
319 0 : if (_ma_fetch_keypage(&page, info, keyinfo, page_pos,
320 : PAGECACHE_LOCK_LEFT_UNLOCKED,
321 : DFLT_INIT_HITS, page_buf, 0))
322 0 : goto err;
323 0 : nod_flag= page.node;
324 :
325 0 : key_data_length= keyinfo->keylength - share->base.rec_reflength;
326 :
327 0 : if (info->maria_rtree_recursion_depth >= level)
328 : {
329 0 : k= page.buff + *saved_key;
330 0 : if (!nod_flag)
331 : {
332 : /* Only leaf pages contain data references. */
333 : /* Need to check next key with data reference. */
334 0 : k= rt_PAGE_NEXT_KEY(share, k, key_data_length, nod_flag);
335 : }
336 : }
337 : else
338 : {
339 0 : k= rt_PAGE_FIRST_KEY(share, page.buff, nod_flag);
340 : }
341 0 : last= rt_PAGE_END(&page);
342 :
343 0 : for (; k < last; k= rt_PAGE_NEXT_KEY(share, k, key_data_length, nod_flag))
344 : {
345 0 : if (nod_flag)
346 : {
347 : /* this is an internal node in the tree */
348 : switch ((res= maria_rtree_get_req(info, keyinfo, key_length,
349 0 : _ma_kpos(nod_flag, k), level + 1)))
350 : {
351 : case 0: /* found - exit from recursion */
352 0 : *saved_key= k - page.buff;
353 0 : goto ok;
354 : case 1: /* not found - continue searching */
355 0 : info->maria_rtree_recursion_depth= level;
356 : break;
357 : default:
358 : case -1: /* error */
359 : goto err;
360 : }
361 : }
362 : else
363 : {
364 : /* this is a leaf */
365 0 : uchar *after_key= rt_PAGE_NEXT_KEY(share, k, key_data_length, 0);
366 : MARIA_KEY tmp_key;
367 :
368 : /*
369 : We don't need to set all MARIA_KEY elements here as
370 : _ma_row_pos_from_key() only uses a few of them.
371 : */
372 0 : tmp_key.keyinfo= keyinfo;
373 0 : tmp_key.data= k;
374 0 : tmp_key.data_length= key_data_length;
375 :
376 0 : info->cur_row.lastpos= _ma_row_pos_from_key(&tmp_key);
377 0 : info->last_key.data_length= key_data_length;
378 0 : info->last_key.ref_length= share->base.rec_reflength;
379 :
380 0 : memcpy(info->last_key.data, k,
381 : info->last_key.data_length + info->last_key.ref_length);
382 :
383 0 : info->maria_rtree_recursion_depth= level;
384 0 : *saved_key= k - page.buff;
385 :
386 0 : if (after_key < last)
387 : {
388 0 : uchar *keyread_buff= info->keyread_buff;
389 0 : info->last_rtree_keypos= saved_key;
390 0 : memcpy(keyread_buff, page.buff, page.size);
391 0 : info->int_maxpos= keyread_buff + page.size;
392 0 : info->keyread_buff_used= 0;
393 : }
394 : else
395 : {
396 0 : info->keyread_buff_used= 1;
397 : }
398 :
399 0 : res= 0;
400 0 : goto ok;
401 : }
402 : }
403 0 : info->cur_row.lastpos= HA_OFFSET_ERROR;
404 0 : my_errno= HA_ERR_KEY_NOT_FOUND;
405 0 : res= 1;
406 :
407 0 : ok:
408 : my_afree(page_buf);
409 0 : return res;
410 :
411 0 : err:
412 : my_afree(page_buf);
413 0 : info->cur_row.lastpos= HA_OFFSET_ERROR;
414 0 : return -1;
415 : }
416 :
417 :
418 : /*
419 : Get first key in r-tree
420 :
421 : RETURN
422 : -1 Error
423 : 0 Found
424 : 1 Not found
425 : */
426 :
427 : int maria_rtree_get_first(MARIA_HA *info, uint keynr, uint key_length)
428 0 : {
429 : my_off_t root;
430 0 : MARIA_KEYDEF *keyinfo= info->s->keyinfo + keynr;
431 :
432 0 : if ((root= info->s->state.key_root[keynr]) == HA_OFFSET_ERROR)
433 : {
434 0 : my_errno= HA_ERR_END_OF_FILE;
435 0 : return -1;
436 : }
437 :
438 0 : info->maria_rtree_recursion_depth= -1;
439 0 : info->keyread_buff_used= 1;
440 :
441 0 : return maria_rtree_get_req(info, keyinfo, key_length, root, 0);
442 : }
443 :
444 :
445 : /*
446 : Get next key in r-tree
447 :
448 : RETURN
449 : -1 Error
450 : 0 Found
451 : 1 Not found
452 : */
453 :
454 : int maria_rtree_get_next(MARIA_HA *info, uint keynr, uint key_length)
455 0 : {
456 : my_off_t root;
457 0 : MARIA_KEYDEF *keyinfo= info->s->keyinfo + keynr;
458 0 : uchar *keyread_buff= info->keyread_buff;
459 :
460 0 : if (!info->keyread_buff_used)
461 : {
462 0 : uint key_data_length= keyinfo->keylength - info->s->base.rec_reflength;
463 : /* rt_PAGE_NEXT_KEY(*info->last_rtree_keypos) */
464 0 : uchar *key= keyread_buff + *info->last_rtree_keypos + keyinfo->keylength;
465 : /* rt_PAGE_NEXT_KEY(key) */
466 0 : uchar *after_key= key + keyinfo->keylength;
467 : MARIA_KEY tmp_key;
468 :
469 0 : tmp_key.keyinfo= keyinfo;
470 0 : tmp_key.data= key;
471 0 : tmp_key.data_length= key_data_length;
472 0 : tmp_key.ref_length= info->s->base.rec_reflength;
473 0 : tmp_key.flag= 0;
474 :
475 0 : info->cur_row.lastpos= _ma_row_pos_from_key(&tmp_key);
476 0 : _ma_copy_key(&info->last_key, &tmp_key);
477 :
478 0 : *info->last_rtree_keypos= (uint) (key - keyread_buff);
479 0 : if (after_key >= info->int_maxpos)
480 : {
481 0 : info->keyread_buff_used= 1;
482 : }
483 :
484 0 : return 0;
485 : }
486 : else
487 : {
488 0 : if ((root= info->s->state.key_root[keynr]) == HA_OFFSET_ERROR)
489 : {
490 0 : my_errno= HA_ERR_END_OF_FILE;
491 0 : return -1;
492 : }
493 :
494 0 : return maria_rtree_get_req(info, &keyinfo[keynr], key_length, root, 0);
495 : }
496 : }
497 :
498 :
499 : /*
500 : Choose non-leaf better key for insertion
501 :
502 : Returns a pointer inside the page_buf buffer.
503 : */
504 : #ifdef PICK_BY_PERIMETER
505 : static const uchar *maria_rtree_pick_key(const MARIA_KEY *key,
506 : const MARIA_PAGE *page)
507 : {
508 : double increase;
509 : double best_incr;
510 : double perimeter;
511 : double best_perimeter;
512 : uchar *best_key= NULL;
513 : const MARIA_HA *info= page->info;
514 :
515 : uchar *k= rt_PAGE_FIRST_KEY(info->s, page->buf, page->node);
516 : uchar *last= rt_PAGE_END(info, page);
517 :
518 : LINT_INIT(best_perimeter);
519 : LINT_INIT(best_key);
520 : LINT_INIT(best_incr);
521 :
522 : for (; k < last; k= rt_PAGE_NEXT_KEY(k, key->data_length, nod_flag))
523 : {
524 : if ((increase= maria_rtree_perimeter_increase(keyinfo->seg, k, key,
525 : &perimeter)) == -1)
526 : return NULL;
527 : if ((increase < best_incr)||
528 : (increase == best_incr && perimeter < best_perimeter))
529 : {
530 : best_key= k;
531 : best_perimeter= perimeter;
532 : best_incr= increase;
533 : }
534 : }
535 : return best_key;
536 : }
537 :
538 : #endif /*PICK_BY_PERIMETER*/
539 :
540 : #ifdef PICK_BY_AREA
541 : static const uchar *maria_rtree_pick_key(const MARIA_KEY *key,
542 : const MARIA_PAGE *page)
543 0 : {
544 0 : const MARIA_HA *info= page->info;
545 0 : MARIA_SHARE *share= info->s;
546 : double increase;
547 0 : double best_incr= DBL_MAX;
548 : double area;
549 : double best_area;
550 0 : const uchar *best_key= NULL;
551 0 : const uchar *k= rt_PAGE_FIRST_KEY(share, page->buff, page->node);
552 0 : const uchar *last= rt_PAGE_END(page);
553 :
554 0 : LINT_INIT(best_area);
555 :
556 0 : for (; k < last;
557 0 : k= rt_PAGE_NEXT_KEY(share, k, key->data_length, page->node))
558 : {
559 : /* The following is safe as -1.0 is an exact number */
560 0 : if ((increase= maria_rtree_area_increase(key->keyinfo->seg, k, key->data,
561 : key->data_length +
562 : key->ref_length,
563 : &area)) == -1.0)
564 0 : return NULL;
565 : /* The following should be safe, even if we compare doubles */
566 0 : if (!best_key || increase < best_incr ||
567 : ((increase == best_incr) && (area < best_area)))
568 : {
569 0 : best_key= k;
570 0 : best_area= area;
571 0 : best_incr= increase;
572 : }
573 : }
574 0 : return best_key;
575 : }
576 :
577 : #endif /*PICK_BY_AREA*/
578 :
579 : /*
580 : Go down and insert key into tree
581 :
582 : RETURN
583 : -1 Error
584 : 0 Child was not split
585 : 1 Child was split
586 : */
587 :
588 : static int maria_rtree_insert_req(MARIA_HA *info, MARIA_KEY *key,
589 : my_off_t page_pos, my_off_t *new_page,
590 : int ins_level, int level)
591 0 : {
592 : uint nod_flag;
593 0 : uint key_length= key->data_length;
594 : int res;
595 : uchar *page_buf, *k;
596 0 : MARIA_SHARE *share= info->s;
597 0 : MARIA_KEYDEF *keyinfo= key->keyinfo;
598 : MARIA_PAGE page;
599 0 : DBUG_ENTER("maria_rtree_insert_req");
600 :
601 0 : if (!(page_buf= (uchar*) my_alloca((uint) keyinfo->block_length +
602 : MARIA_MAX_KEY_BUFF)))
603 : {
604 0 : my_errno= HA_ERR_OUT_OF_MEM;
605 0 : DBUG_RETURN(-1); /* purecov: inspected */
606 : }
607 0 : if (_ma_fetch_keypage(&page, info, keyinfo, page_pos, PAGECACHE_LOCK_WRITE,
608 : DFLT_INIT_HITS, page_buf, 0))
609 0 : goto err;
610 0 : nod_flag= page.node;
611 0 : DBUG_PRINT("rtree", ("page: %lu level: %d ins_level: %d nod_flag: %u",
612 : (ulong) page.pos, level, ins_level, nod_flag));
613 :
614 0 : if ((ins_level == -1 && nod_flag) || /* key: go down to leaf */
615 : (ins_level > -1 && ins_level > level)) /* branch: go down to ins_level */
616 : {
617 0 : if (!(k= (uchar *)maria_rtree_pick_key(key, &page)))
618 0 : goto err;
619 : /* k is now a pointer inside the page_buf buffer */
620 : switch ((res= maria_rtree_insert_req(info, key,
621 : _ma_kpos(nod_flag, k), new_page,
622 0 : ins_level, level + 1)))
623 : {
624 : case 0: /* child was not split, most common case */
625 : {
626 0 : maria_rtree_combine_rect(keyinfo->seg, k, key->data, k, key_length);
627 0 : if (share->now_transactional &&
628 : _ma_log_change(&page, k, key_length))
629 0 : goto err;
630 0 : page_mark_changed(info, &page);
631 0 : if (_ma_write_keypage(&page, PAGECACHE_LOCK_LEFT_WRITELOCKED,
632 : DFLT_INIT_HITS))
633 : goto err;
634 : goto ok;
635 : }
636 : case 1: /* child was split */
637 : {
638 : /* Set new_key to point to a free buffer area */
639 0 : uchar *new_key_buff= page_buf + keyinfo->block_length + nod_flag;
640 : MARIA_KEY new_key;
641 : MARIA_KEY k_key;
642 :
643 0 : DBUG_ASSERT(nod_flag);
644 0 : k_key.keyinfo= new_key.keyinfo= keyinfo;
645 0 : new_key.data= new_key_buff;
646 0 : k_key.data= k;
647 0 : k_key.data_length= new_key.data_length= key->data_length;
648 0 : k_key.ref_length= new_key.ref_length= key->ref_length;
649 0 : k_key.flag= new_key.flag= 0; /* Safety */
650 :
651 : /* set proper MBR for key */
652 0 : if (maria_rtree_set_key_mbr(info, &k_key, _ma_kpos(nod_flag, k)))
653 0 : goto err;
654 0 : if (share->now_transactional &&
655 : _ma_log_change(&page, k, key_length))
656 0 : goto err;
657 : /* add new key for new page */
658 0 : _ma_kpointer(info, new_key_buff - nod_flag, *new_page);
659 0 : if (maria_rtree_set_key_mbr(info, &new_key, *new_page))
660 0 : goto err;
661 0 : res= maria_rtree_add_key(&new_key, &page, new_page);
662 0 : page_mark_changed(info, &page);
663 0 : if (_ma_write_keypage(&page, PAGECACHE_LOCK_LEFT_WRITELOCKED,
664 : DFLT_INIT_HITS))
665 : goto err;
666 : goto ok;
667 : }
668 : default:
669 : case -1: /* error */
670 : {
671 : goto err;
672 : }
673 : }
674 : }
675 : else
676 : {
677 0 : res= maria_rtree_add_key(key, &page, new_page);
678 0 : page_mark_changed(info, &page);
679 0 : if (_ma_write_keypage(&page, PAGECACHE_LOCK_LEFT_WRITELOCKED,
680 : DFLT_INIT_HITS))
681 0 : goto err;
682 : }
683 :
684 0 : ok:
685 : my_afree(page_buf);
686 0 : DBUG_RETURN(res);
687 :
688 0 : err:
689 0 : res= -1; /* purecov: inspected */
690 0 : goto ok; /* purecov: inspected */
691 : }
692 :
693 :
694 : /**
695 : Insert key into the tree
696 :
697 : @param info table
698 : @param key KEY to insert
699 : @param ins_level at which level key insertion should start
700 : @param root put new key_root there
701 :
702 : @return Operation result
703 : @retval -1 Error
704 : @retval 0 Root was not split
705 : @retval 1 Root was split
706 : */
707 :
708 : int maria_rtree_insert_level(MARIA_HA *info, MARIA_KEY *key, int ins_level,
709 : my_off_t *root)
710 0 : {
711 : my_off_t old_root;
712 0 : MARIA_SHARE *share= info->s;
713 0 : MARIA_KEYDEF *keyinfo= key->keyinfo;
714 : int res;
715 : my_off_t new_page;
716 : enum pagecache_page_lock write_lock;
717 0 : DBUG_ENTER("maria_rtree_insert_level");
718 :
719 0 : if ((old_root= share->state.key_root[keyinfo->key_nr]) == HA_OFFSET_ERROR)
720 : {
721 : MARIA_PINNED_PAGE tmp_page_link, *page_link;
722 : MARIA_PAGE page;
723 :
724 0 : page_link= &tmp_page_link;
725 0 : if ((old_root= _ma_new(info, DFLT_INIT_HITS, &page_link)) ==
726 : HA_OFFSET_ERROR)
727 0 : DBUG_RETURN(-1);
728 0 : write_lock= page_link->write_lock;
729 0 : info->keyread_buff_used= 1;
730 0 : bzero(info->buff, share->block_size);
731 0 : _ma_store_keynr(share, info->buff, keyinfo->key_nr);
732 0 : _ma_store_page_used(share, info->buff, share->keypage_header);
733 0 : _ma_page_setup(&page, info, keyinfo, old_root, info->buff);
734 :
735 0 : if (share->now_transactional && _ma_log_new(&page, 1))
736 0 : DBUG_RETURN(1);
737 :
738 0 : res= maria_rtree_add_key(key, &page, NULL);
739 0 : if (_ma_write_keypage(&page, write_lock, DFLT_INIT_HITS))
740 0 : DBUG_RETURN(1);
741 0 : *root= old_root;
742 0 : DBUG_RETURN(res);
743 : }
744 :
745 : switch ((res= maria_rtree_insert_req(info, key, old_root, &new_page,
746 0 : ins_level, 0)))
747 : {
748 : case 0: /* root was not split */
749 : {
750 : break;
751 : }
752 : case 1: /* root was split, grow a new root; very rare */
753 : {
754 : uchar *new_root_buf, *new_key_buff;
755 : my_off_t new_root;
756 0 : uint nod_flag= share->base.key_reflength;
757 : MARIA_PINNED_PAGE tmp_page_link, *page_link;
758 : MARIA_KEY new_key;
759 : MARIA_PAGE page;
760 0 : page_link= &tmp_page_link;
761 :
762 0 : DBUG_PRINT("rtree", ("root was split, grow a new root"));
763 0 : if (!(new_root_buf= (uchar*) my_alloca((uint) keyinfo->block_length +
764 : MARIA_MAX_KEY_BUFF)))
765 : {
766 0 : my_errno= HA_ERR_OUT_OF_MEM;
767 0 : DBUG_RETURN(-1); /* purecov: inspected */
768 : }
769 :
770 0 : bzero(new_root_buf, share->block_size);
771 0 : _ma_store_keypage_flag(share, new_root_buf, KEYPAGE_FLAG_ISNOD);
772 0 : _ma_store_keynr(share, new_root_buf, keyinfo->key_nr);
773 0 : _ma_store_page_used(share, new_root_buf, share->keypage_header);
774 0 : if ((new_root= _ma_new(info, DFLT_INIT_HITS, &page_link)) ==
775 : HA_OFFSET_ERROR)
776 0 : goto err;
777 0 : write_lock= page_link->write_lock;
778 :
779 0 : _ma_page_setup(&page, info, keyinfo, new_root, new_root_buf);
780 :
781 0 : if (share->now_transactional && _ma_log_new(&page, 1))
782 0 : goto err;
783 :
784 : /* Point to some free space */
785 0 : new_key_buff= new_root_buf + keyinfo->block_length + nod_flag;
786 0 : new_key.keyinfo= keyinfo;
787 0 : new_key.data= new_key_buff;
788 0 : new_key.data_length= key->data_length;
789 0 : new_key.ref_length= key->ref_length;
790 0 : new_key.flag= 0;
791 :
792 0 : _ma_kpointer(info, new_key_buff - nod_flag, old_root);
793 0 : if (maria_rtree_set_key_mbr(info, &new_key, old_root))
794 0 : goto err;
795 0 : if (maria_rtree_add_key(&new_key, &page, NULL)
796 : == -1)
797 0 : goto err;
798 0 : _ma_kpointer(info, new_key_buff - nod_flag, new_page);
799 0 : if (maria_rtree_set_key_mbr(info, &new_key, new_page))
800 0 : goto err;
801 0 : if (maria_rtree_add_key(&new_key, &page, NULL)
802 : == -1)
803 0 : goto err;
804 0 : if (_ma_write_keypage(&page, write_lock, DFLT_INIT_HITS))
805 0 : goto err;
806 0 : *root= new_root;
807 0 : DBUG_PRINT("rtree", ("new root page: %lu level: %d nod_flag: %u",
808 : (ulong) new_root, 0, page.node));
809 :
810 : my_afree(new_root_buf);
811 0 : break;
812 0 : err:
813 : my_afree(new_root_buf);
814 0 : DBUG_RETURN(-1); /* purecov: inspected */
815 : }
816 : default:
817 : case -1: /* error */
818 : {
819 0 : DBUG_ASSERT(0);
820 : break;
821 : }
822 : }
823 0 : DBUG_RETURN(res);
824 : }
825 :
826 :
827 : /*
828 : Insert key into the tree - interface function
829 :
830 : RETURN
831 : 1 Error
832 : 0 OK
833 : */
834 :
835 : my_bool maria_rtree_insert(MARIA_HA *info, MARIA_KEY *key)
836 0 : {
837 : int res;
838 0 : MARIA_SHARE *share= info->s;
839 : my_off_t *root, new_root;
840 0 : LSN lsn= LSN_IMPOSSIBLE;
841 0 : DBUG_ENTER("maria_rtree_insert");
842 :
843 0 : if (!key)
844 0 : DBUG_RETURN(1); /* _ma_sp_make_key failed */
845 :
846 0 : root= &share->state.key_root[key->keyinfo->key_nr];
847 0 : new_root= *root;
848 :
849 0 : if ((res= (maria_rtree_insert_level(info, key, -1, &new_root) == -1)))
850 0 : goto err;
851 0 : if (share->now_transactional)
852 0 : res= _ma_write_undo_key_insert(info, key, root, new_root, &lsn);
853 : else
854 : {
855 0 : *root= new_root;
856 0 : _ma_fast_unlock_key_del(info);
857 : }
858 0 : _ma_unpin_all_pages_and_finalize_row(info, lsn);
859 0 : err:
860 0 : DBUG_RETURN(res != 0);
861 : }
862 :
863 :
864 : /*
865 : Fill reinsert page buffer
866 :
867 : RETURN
868 : 1 Error
869 : 0 OK
870 : */
871 :
872 : static my_bool maria_rtree_fill_reinsert_list(stPageList *ReinsertList,
873 : my_off_t page, int level)
874 0 : {
875 0 : DBUG_ENTER("maria_rtree_fill_reinsert_list");
876 0 : DBUG_PRINT("rtree", ("page: %lu level: %d", (ulong) page, level));
877 0 : if (ReinsertList->n_pages == ReinsertList->m_pages)
878 : {
879 0 : ReinsertList->m_pages += REINSERT_BUFFER_INC;
880 0 : if (!(ReinsertList->pages= (stPageLevel*)my_realloc((uchar*)ReinsertList->pages,
881 : ReinsertList->m_pages * sizeof(stPageLevel), MYF(MY_ALLOW_ZERO_PTR))))
882 0 : goto err;
883 : }
884 : /* save page to ReinsertList */
885 0 : ReinsertList->pages[ReinsertList->n_pages].offs= page;
886 0 : ReinsertList->pages[ReinsertList->n_pages].level= level;
887 0 : ReinsertList->n_pages++;
888 0 : DBUG_RETURN(0);
889 :
890 0 : err:
891 0 : DBUG_RETURN(1); /* purecov: inspected */
892 : }
893 :
894 :
895 : /*
896 : Go down and delete key from the tree
897 :
898 : RETURN
899 : -1 Error
900 : 0 Deleted
901 : 1 Not found
902 : 2 Empty leaf
903 : */
904 :
905 : static int maria_rtree_delete_req(MARIA_HA *info, const MARIA_KEY *key,
906 : my_off_t page_pos, uint *page_size,
907 : stPageList *ReinsertList, int level)
908 0 : {
909 : ulong i;
910 : uint nod_flag;
911 : int res;
912 : uchar *page_buf, *last, *k;
913 0 : MARIA_SHARE *share= info->s;
914 0 : MARIA_KEYDEF *keyinfo= key->keyinfo;
915 : MARIA_PAGE page;
916 0 : DBUG_ENTER("maria_rtree_delete_req");
917 :
918 0 : if (!(page_buf= (uchar*) my_alloca((uint) keyinfo->block_length)))
919 : {
920 0 : my_errno= HA_ERR_OUT_OF_MEM;
921 0 : DBUG_RETURN(-1); /* purecov: inspected */
922 : }
923 0 : if (_ma_fetch_keypage(&page, info, keyinfo, page_pos, PAGECACHE_LOCK_WRITE,
924 : DFLT_INIT_HITS, page_buf, 0))
925 0 : goto err;
926 0 : nod_flag= page.node;
927 0 : DBUG_PRINT("rtree", ("page: %lu level: %d nod_flag: %u",
928 : (ulong) page_pos, level, nod_flag));
929 :
930 0 : k= rt_PAGE_FIRST_KEY(share, page_buf, nod_flag);
931 0 : last= rt_PAGE_END(&page);
932 :
933 0 : for (i= 0;
934 0 : k < last;
935 0 : k= rt_PAGE_NEXT_KEY(share, k, key->data_length, nod_flag), i++)
936 : {
937 0 : if (nod_flag)
938 : {
939 : /* not leaf */
940 0 : if (!maria_rtree_key_cmp(keyinfo->seg, key->data, k, key->data_length,
941 : MBR_WITHIN))
942 : {
943 : switch ((res= maria_rtree_delete_req(info, key,
944 : _ma_kpos(nod_flag, k),
945 : page_size, ReinsertList,
946 0 : level + 1)))
947 : {
948 : case 0: /* deleted */
949 : {
950 : /* test page filling */
951 0 : if (*page_size + key->data_length >=
952 : rt_PAGE_MIN_SIZE(keyinfo->block_length))
953 : {
954 : /* OK */
955 : /* Calculate a new key value (MBR) for the shrinked block. */
956 : MARIA_KEY tmp_key;
957 0 : tmp_key.keyinfo= keyinfo;
958 0 : tmp_key.data= k;
959 0 : tmp_key.data_length= key->data_length;
960 0 : tmp_key.ref_length= key->ref_length;
961 0 : tmp_key.flag= 0; /* Safety */
962 :
963 0 : if (maria_rtree_set_key_mbr(info, &tmp_key,
964 : _ma_kpos(nod_flag, k)))
965 0 : goto err;
966 0 : if (share->now_transactional &&
967 : _ma_log_change(&page, k, key->data_length))
968 0 : goto err;
969 0 : page_mark_changed(info, &page)
970 0 : if (_ma_write_keypage(&page,
971 : PAGECACHE_LOCK_LEFT_WRITELOCKED,
972 : DFLT_INIT_HITS))
973 : goto err;
974 : }
975 : else
976 : {
977 : /*
978 : Too small: delete key & add it descendant to reinsert list.
979 : Store position and level of the block so that it can be
980 : accessed later for inserting the remaining keys.
981 : */
982 0 : DBUG_PRINT("rtree", ("too small. move block to reinsert list"));
983 0 : if (maria_rtree_fill_reinsert_list(ReinsertList,
984 : _ma_kpos(nod_flag, k),
985 : level + 1))
986 0 : goto err;
987 : /*
988 : Delete the key that references the block. This makes the
989 : block disappear from the index. Hence we need to insert
990 : its remaining keys later. Note: if the block is a branch
991 : block, we do not only remove this block, but the whole
992 : subtree. So we need to re-insert its keys on the same
993 : level later to reintegrate the subtrees.
994 : */
995 0 : if (maria_rtree_delete_key(&page, k, key->data_length))
996 0 : goto err;
997 0 : page_mark_changed(info, &page);
998 0 : if (_ma_write_keypage(&page, PAGECACHE_LOCK_LEFT_WRITELOCKED,
999 : DFLT_INIT_HITS))
1000 0 : goto err;
1001 0 : *page_size= page.size;
1002 : }
1003 :
1004 : goto ok;
1005 : }
1006 : case 1: /* not found - continue searching */
1007 : {
1008 : break;
1009 : }
1010 : case 2: /* vacuous case: last key in the leaf */
1011 : {
1012 0 : if (maria_rtree_delete_key(&page, k, key->data_length))
1013 0 : goto err;
1014 0 : page_mark_changed(info, &page);
1015 0 : if (_ma_write_keypage(&page, PAGECACHE_LOCK_LEFT_WRITELOCKED,
1016 : DFLT_INIT_HITS))
1017 0 : goto err;
1018 0 : *page_size= page.size;
1019 0 : res= 0;
1020 0 : goto ok;
1021 : }
1022 : default: /* error */
1023 : case -1:
1024 : {
1025 : goto err;
1026 : }
1027 : }
1028 : }
1029 : }
1030 : else
1031 : {
1032 : /* leaf */
1033 0 : if (!maria_rtree_key_cmp(keyinfo->seg, key->data, k, key->data_length,
1034 : MBR_EQUAL | MBR_DATA))
1035 : {
1036 0 : page_mark_changed(info, &page);
1037 0 : if (maria_rtree_delete_key(&page, k, key->data_length))
1038 0 : goto err;
1039 0 : *page_size= page.size;
1040 0 : if (*page_size == info->s->keypage_header)
1041 : {
1042 : /* last key in the leaf */
1043 0 : res= 2;
1044 0 : if (_ma_dispose(info, page.pos, 0))
1045 : goto err;
1046 : }
1047 : else
1048 : {
1049 0 : res= 0;
1050 0 : if (_ma_write_keypage(&page, PAGECACHE_LOCK_LEFT_WRITELOCKED,
1051 : DFLT_INIT_HITS))
1052 : goto err;
1053 : }
1054 : goto ok;
1055 : }
1056 : }
1057 : }
1058 0 : res= 1;
1059 :
1060 0 : ok:
1061 : my_afree(page_buf);
1062 0 : DBUG_RETURN(res);
1063 :
1064 0 : err:
1065 : my_afree(page_buf);
1066 0 : DBUG_RETURN(-1); /* purecov: inspected */
1067 : }
1068 :
1069 :
1070 : /*
1071 : Delete key - interface function
1072 :
1073 : RETURN
1074 : 1 Error
1075 : 0 Deleted
1076 : */
1077 :
1078 : my_bool maria_rtree_delete(MARIA_HA *info, MARIA_KEY *key)
1079 0 : {
1080 0 : MARIA_SHARE *share= info->s;
1081 0 : my_off_t new_root= share->state.key_root[key->keyinfo->key_nr];
1082 : int res;
1083 0 : LSN lsn= LSN_IMPOSSIBLE;
1084 0 : DBUG_ENTER("maria_rtree_delete");
1085 :
1086 0 : if ((res= maria_rtree_real_delete(info, key, &new_root)))
1087 0 : goto err;
1088 :
1089 0 : if (share->now_transactional)
1090 0 : res= _ma_write_undo_key_delete(info, key, new_root, &lsn);
1091 : else
1092 0 : share->state.key_root[key->keyinfo->key_nr]= new_root;
1093 :
1094 0 : err:
1095 0 : _ma_fast_unlock_key_del(info);
1096 0 : _ma_unpin_all_pages_and_finalize_row(info, lsn);
1097 0 : DBUG_RETURN(res != 0);
1098 : }
1099 :
1100 :
1101 : my_bool maria_rtree_real_delete(MARIA_HA *info, MARIA_KEY *key,
1102 : my_off_t *root)
1103 0 : {
1104 : uint page_size;
1105 : stPageList ReinsertList;
1106 : my_off_t old_root;
1107 0 : MARIA_SHARE *share= info->s;
1108 0 : MARIA_KEYDEF *keyinfo= key->keyinfo;
1109 0 : uint key_data_length= key->data_length;
1110 0 : DBUG_ENTER("maria_rtree_real_delete");
1111 :
1112 0 : if ((old_root= share->state.key_root[keyinfo->key_nr]) ==
1113 : HA_OFFSET_ERROR)
1114 : {
1115 0 : my_errno= HA_ERR_END_OF_FILE;
1116 0 : DBUG_RETURN(1); /* purecov: inspected */
1117 : }
1118 0 : DBUG_PRINT("rtree", ("starting deletion at root page: %lu",
1119 : (ulong) old_root));
1120 :
1121 0 : ReinsertList.pages= NULL;
1122 0 : ReinsertList.n_pages= 0;
1123 0 : ReinsertList.m_pages= 0;
1124 :
1125 : switch (maria_rtree_delete_req(info, key, old_root, &page_size,
1126 0 : &ReinsertList, 0)) {
1127 : case 2: /* empty */
1128 : {
1129 0 : *root= HA_OFFSET_ERROR;
1130 0 : break;
1131 : }
1132 : case 0: /* deleted */
1133 : {
1134 : uint nod_flag;
1135 : ulong i;
1136 : MARIA_KEY tmp_key;
1137 0 : tmp_key.keyinfo= key->keyinfo;
1138 0 : tmp_key.data_length= key->data_length;
1139 0 : tmp_key.ref_length= key->ref_length;
1140 0 : tmp_key.flag= 0; /* Safety */
1141 : uchar *page_buf;
1142 : MARIA_PAGE page;
1143 :
1144 0 : if (ReinsertList.n_pages)
1145 : {
1146 0 : if (!(page_buf= (uchar*) my_alloca((uint) keyinfo->block_length)))
1147 : {
1148 0 : my_errno= HA_ERR_OUT_OF_MEM;
1149 0 : goto err;
1150 : }
1151 :
1152 0 : for (i= 0; i < ReinsertList.n_pages; ++i)
1153 : {
1154 : uchar *k, *last;
1155 0 : if (_ma_fetch_keypage(&page, info, keyinfo, ReinsertList.pages[i].offs,
1156 : PAGECACHE_LOCK_WRITE,
1157 : DFLT_INIT_HITS, page_buf, 0))
1158 0 : goto err;
1159 0 : nod_flag= page.node;
1160 0 : DBUG_PRINT("rtree", ("reinserting keys from "
1161 : "page: %lu level: %d nod_flag: %u",
1162 : (ulong) ReinsertList.pages[i].offs,
1163 : ReinsertList.pages[i].level, nod_flag));
1164 :
1165 0 : k= rt_PAGE_FIRST_KEY(share, page.buff, nod_flag);
1166 0 : last= rt_PAGE_END(&page);
1167 0 : for (; k < last; k= rt_PAGE_NEXT_KEY(share, k, key_data_length,
1168 : nod_flag))
1169 : {
1170 : int res;
1171 0 : tmp_key.data= k;
1172 0 : if ((res= maria_rtree_insert_level(info, &tmp_key,
1173 : ReinsertList.pages[i].level,
1174 : root)) == -1)
1175 : {
1176 : my_afree(page_buf);
1177 0 : goto err;
1178 : }
1179 0 : if (res)
1180 : {
1181 : uint j;
1182 0 : DBUG_PRINT("rtree", ("root has been split, adjust levels"));
1183 0 : for (j= i; j < ReinsertList.n_pages; j++)
1184 : {
1185 0 : ReinsertList.pages[j].level++;
1186 0 : DBUG_PRINT("rtree", ("keys from page: %lu now level: %d",
1187 : (ulong) ReinsertList.pages[i].offs,
1188 : ReinsertList.pages[i].level));
1189 : }
1190 : }
1191 : }
1192 0 : page_mark_changed(info, &page);
1193 0 : if (_ma_dispose(info, page.pos, 0))
1194 : {
1195 : my_afree(page_buf);
1196 0 : goto err;
1197 : }
1198 : }
1199 : my_afree(page_buf);
1200 0 : my_free(ReinsertList.pages, MYF(0));
1201 : }
1202 :
1203 : /* check for redundant root (not leaf, 1 child) and eliminate */
1204 0 : if ((old_root= *root) == HA_OFFSET_ERROR)
1205 0 : goto err;
1206 0 : if (_ma_fetch_keypage(&page, info, keyinfo, old_root,
1207 : PAGECACHE_LOCK_WRITE,
1208 : DFLT_INIT_HITS, info->buff, 0))
1209 0 : goto err;
1210 0 : nod_flag= page.node;
1211 0 : if (nod_flag && (page.size == share->keypage_header + key_data_length +
1212 : nod_flag))
1213 : {
1214 0 : *root= _ma_kpos(nod_flag,
1215 : rt_PAGE_FIRST_KEY(share, info->buff, nod_flag));
1216 0 : page_mark_changed(info, &page);
1217 0 : if (_ma_dispose(info, page.pos, 0))
1218 0 : goto err;
1219 : }
1220 0 : info->update= HA_STATE_DELETED;
1221 0 : break;
1222 : }
1223 : case 1: /* not found */
1224 : {
1225 0 : my_errno= HA_ERR_KEY_NOT_FOUND;
1226 0 : goto err;
1227 : }
1228 : case -1: /* error */
1229 : default:
1230 : goto err; /* purecov: inspected */
1231 : }
1232 0 : DBUG_RETURN(0);
1233 :
1234 0 : err:
1235 0 : DBUG_RETURN(1);
1236 : }
1237 :
1238 :
1239 : /*
1240 : Estimate number of suitable keys in the tree
1241 :
1242 : RETURN
1243 : estimated value
1244 : */
1245 :
1246 : ha_rows maria_rtree_estimate(MARIA_HA *info, MARIA_KEY *key, uint32 flag)
1247 0 : {
1248 : my_off_t root;
1249 0 : uint i= 0;
1250 : uint nod_flag, key_data_length;
1251 : uchar *page_buf, *k, *last;
1252 0 : double area= 0;
1253 0 : ha_rows res= 0;
1254 0 : MARIA_SHARE *share= info->s;
1255 0 : MARIA_KEYDEF *keyinfo= key->keyinfo;
1256 : MARIA_PAGE page;
1257 :
1258 0 : if (flag & MBR_DISJOINT)
1259 0 : return info->state->records;
1260 :
1261 0 : if ((root= share->state.key_root[key->keyinfo->key_nr]) == HA_OFFSET_ERROR)
1262 0 : return HA_POS_ERROR;
1263 0 : if (!(page_buf= (uchar*) my_alloca((uint) keyinfo->block_length)))
1264 0 : return HA_POS_ERROR;
1265 0 : if (_ma_fetch_keypage(&page, info, keyinfo, root,
1266 : PAGECACHE_LOCK_LEFT_UNLOCKED, DFLT_INIT_HITS, page_buf,
1267 : 0))
1268 0 : goto err;
1269 0 : nod_flag= page.node;
1270 :
1271 0 : key_data_length= key->data_length;
1272 :
1273 0 : k= rt_PAGE_FIRST_KEY(share, page.buff, nod_flag);
1274 0 : last= rt_PAGE_END(&page);
1275 :
1276 0 : for (; k < last;
1277 0 : k= rt_PAGE_NEXT_KEY(share, k, key_data_length, nod_flag), i++)
1278 : {
1279 0 : if (nod_flag)
1280 : {
1281 0 : double k_area= maria_rtree_rect_volume(keyinfo->seg, k, key_data_length);
1282 :
1283 : /* The following should be safe, even if we compare doubles */
1284 0 : if (k_area == 0)
1285 : {
1286 0 : if (flag & (MBR_CONTAIN | MBR_INTERSECT))
1287 : {
1288 0 : area+= 1;
1289 : }
1290 0 : else if (flag & (MBR_WITHIN | MBR_EQUAL))
1291 : {
1292 0 : if (!maria_rtree_key_cmp(keyinfo->seg, key->data, k, key_data_length,
1293 : MBR_WITHIN))
1294 0 : area+= 1;
1295 : }
1296 : else
1297 0 : goto err;
1298 : }
1299 : else
1300 : {
1301 0 : if (flag & (MBR_CONTAIN | MBR_INTERSECT))
1302 : {
1303 0 : area+= maria_rtree_overlapping_area(keyinfo->seg, key->data, k,
1304 : key_data_length) / k_area;
1305 : }
1306 0 : else if (flag & (MBR_WITHIN | MBR_EQUAL))
1307 : {
1308 0 : if (!maria_rtree_key_cmp(keyinfo->seg, key->data, k, key_data_length,
1309 : MBR_WITHIN))
1310 0 : area+= (maria_rtree_rect_volume(keyinfo->seg, key->data,
1311 : key_data_length) / k_area);
1312 : }
1313 : else
1314 0 : goto err;
1315 : }
1316 : }
1317 : else
1318 : {
1319 0 : if (!maria_rtree_key_cmp(keyinfo->seg, key->data, k, key_data_length,
1320 : flag))
1321 0 : ++res;
1322 : }
1323 : }
1324 0 : if (nod_flag)
1325 : {
1326 0 : if (i)
1327 0 : res= (ha_rows) (area / i * info->state->records);
1328 : else
1329 0 : res= HA_POS_ERROR;
1330 : }
1331 :
1332 : my_afree(page_buf);
1333 0 : return res;
1334 :
1335 0 : err:
1336 : my_afree(page_buf);
1337 0 : return HA_POS_ERROR;
1338 : }
1339 :
1340 : #endif /*HAVE_RTREE_KEYS*/
|