rt_index.c 29.7 KB
Newer Older
1
/* Copyright (C) 2002-2006 MySQL AB & Ramil Kalimullin
2 3 4
   
   This program is free software; you can redistribute it and/or modify
   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 8 9 10 11 12 13 14 15 16 17
   
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.
   
   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */

#include "myisamdef.h"

18 19
#ifdef HAVE_RTREE_KEYS

20 21 22 23 24
#include "rt_index.h"
#include "rt_key.h"
#include "rt_mbr.h"

#define REINSERT_BUFFER_INC 10
25 26
#define PICK_BY_AREA
/*#define PICK_BY_PERIMETER*/
27 28 29 30 31 32 33 34 35 36 37 38 39 40

typedef struct st_page_level
{
  uint level;
  my_off_t offs;
} stPageLevel;

typedef struct st_page_list
{   
  ulong n_pages;
  ulong m_pages;
  stPageLevel *pages;
} stPageList;

41

42
/* 
43 44 45 46 47 48 49 50 51
   Find next key in r-tree according to search_flag recursively

   NOTES
     Used in rtree_find_first() and rtree_find_next()

   RETURN
     -1	 Error
     0   Found
     1   Not found 
52
*/
53 54 55

static int rtree_find_req(MI_INFO *info, MI_KEYDEF *keyinfo, uint search_flag,
			  uint nod_cmp_flag, my_off_t page, int level)
56 57 58 59 60 61 62
{
  uchar *k;
  uchar *last;
  uint nod_flag;
  int res;
  uchar *page_buf;
  int k_len;
63
  uint *saved_key = (uint*) (info->rtree_recursion_state) + level;
64 65 66 67 68 69
  
  if (!(page_buf = (uchar*)my_alloca((uint)keyinfo->block_length)))
  {
    my_errno = HA_ERR_OUT_OF_MEM;
    return -1;
  }
70
  if (!_mi_fetch_keypage(info, keyinfo, page, DFLT_INIT_HITS, page_buf, 0))
71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90
    goto err1;
  nod_flag = mi_test_if_nod(page_buf);

  k_len = keyinfo->keylength - info->s->base.rec_reflength;
  
  if(info->rtree_recursion_depth >= level)
  {
    k = page_buf + *saved_key;
  }
  else
  {
    k = rt_PAGE_FIRST_KEY(page_buf, nod_flag);
  }
  last = rt_PAGE_END(page_buf);

  for (; k < last; k = rt_PAGE_NEXT_KEY(k, k_len, nod_flag))
  {
    if (nod_flag) 
    { 
      /* this is an internal node in the tree */
91
      if (!(res = rtree_key_cmp(keyinfo->seg, info->first_mbr_key, k, 
92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111
                            info->last_rkey_length, nod_cmp_flag)))
      {
        switch ((res = rtree_find_req(info, keyinfo, search_flag, nod_cmp_flag,
                                      _mi_kpos(nod_flag, k), level + 1)))
        {
          case 0: /* found - exit from recursion */
            *saved_key = k - page_buf;
            goto ok;
          case 1: /* not found - continue searching */
            info->rtree_recursion_depth = level;
            break;
          default: /* error */
          case -1:
            goto err1;
        }
      }
    }
    else 
    { 
      /* this is a leaf */
112
      if (!rtree_key_cmp(keyinfo->seg, info->first_mbr_key, k, 
113 114 115 116 117
                         info->last_rkey_length, search_flag))
      {
        uchar *after_key = rt_PAGE_NEXT_KEY(k, k_len, nod_flag);
        info->lastpos = _mi_dpos(info, 0, after_key);
        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 123

        if (after_key < last)
        {
124 125 126
          info->int_keypos = info->buff;
          info->int_maxpos = info->buff + (last - after_key);
          memcpy(info->buff, after_key, last - after_key);
127 128
          info->buff_used = 0;
        }
129 130 131 132
        else
        {
	  info->buff_used = 1;
        }
133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152

        res = 0;
        goto ok;
      }
    }
  }
  info->lastpos = HA_OFFSET_ERROR;
  my_errno = HA_ERR_KEY_NOT_FOUND;
  res = 1;

ok:
  my_afree((byte*)page_buf);
  return res;

err1:
  my_afree((byte*)page_buf);
  info->lastpos = HA_OFFSET_ERROR;
  return -1;
}

153

154
/*
155 156 157 158 159 160 161 162 163 164 165 166 167 168
  Find first key in r-tree according to search_flag condition

  SYNOPSIS
   rtree_find_first()
   info			Handler to MyISAM file
   uint keynr		Key number to use
   key			Key to search for
   key_length		Length of 'key' 
   search_flag		Bitmap of flags how to do the search

  RETURN
    -1  Error
    0   Found
    1   Not found
169
*/
170

171 172 173 174 175 176 177 178
int rtree_find_first(MI_INFO *info, uint keynr, uchar *key, uint key_length, 
                    uint search_flag)
{
  my_off_t root;
  uint nod_cmp_flag;
  MI_KEYDEF *keyinfo = info->s->keyinfo + keynr;

  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 186
  /*
    Save searched key, include data pointer.
    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 191 192 193 194 195 196 197 198 199
  info->last_rkey_length = key_length;

  info->rtree_recursion_depth = -1;
  info->buff_used = 1;
  
  nod_cmp_flag = ((search_flag & (MBR_EQUAL | MBR_WITHIN)) ? 
        MBR_WITHIN : MBR_INTERSECT);
  return rtree_find_req(info, keyinfo, search_flag, nod_cmp_flag, root, 0);
}

200

201
/* 
202 203
   Find next key in r-tree according to search_flag condition

204 205 206 207 208 209
  SYNOPSIS
   rtree_find_next()
   info			Handler to MyISAM file
   uint keynr		Key number to use
   search_flag		Bitmap of flags how to do the search

210 211 212 213
   RETURN
     -1  Error
     0   Found
     1   Not found
214
*/
215

216 217 218 219 220 221
int rtree_find_next(MI_INFO *info, uint keynr, uint search_flag)
{
  my_off_t root;
  uint nod_cmp_flag;
  MI_KEYDEF *keyinfo = info->s->keyinfo + keynr;

ram@mysql.r18.ru's avatar
ram@mysql.r18.ru committed
222 223 224
  if (info->update & HA_STATE_DELETED)
    return rtree_find_first(info, keynr, info->lastkey, info->lastkey_length,
			    search_flag);
225

226 227
  if (!info->buff_used)
  {
228
    uchar *key= info->int_keypos;
229 230 231

    while (key < info->int_maxpos)
    {
232
      if (!rtree_key_cmp(keyinfo->seg, info->first_mbr_key, key, 
233 234
                         info->last_rkey_length, search_flag))
      {
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 245
        return 0;
      }
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 256 257 258 259
  
  nod_cmp_flag = ((search_flag & (MBR_EQUAL | MBR_WITHIN)) ? 
        MBR_WITHIN : MBR_INTERSECT);
  return rtree_find_req(info, keyinfo, search_flag, nod_cmp_flag, root, 0);
}

260

261
/*
262 263 264 265 266 267 268 269 270
  Get next key in r-tree recursively

  NOTES
    Used in rtree_get_first() and rtree_get_next()

  RETURN
    -1  Error
    0   Found
    1   Not found
271
*/
272

273 274 275 276 277 278 279 280 281
static int rtree_get_req(MI_INFO *info, MI_KEYDEF *keyinfo, uint key_length, 
                         my_off_t page, int level)
{
  uchar *k;
  uchar *last;
  uint nod_flag;
  int res;
  uchar *page_buf;
  uint k_len;
282
  uint *saved_key = (uint*) (info->rtree_recursion_state) + level;
283 284 285
  
  if (!(page_buf = (uchar*)my_alloca((uint)keyinfo->block_length)))
    return -1;
286
  if (!_mi_fetch_keypage(info, keyinfo, page, DFLT_INIT_HITS, page_buf, 0))
287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332
    goto err1;
  nod_flag = mi_test_if_nod(page_buf);

  k_len = keyinfo->keylength - info->s->base.rec_reflength;

  if(info->rtree_recursion_depth >= level)
  {
    k = page_buf + *saved_key;
    if (!nod_flag)
    {
      /* Only leaf pages contain data references. */
      /* Need to check next key with data reference. */
      k = rt_PAGE_NEXT_KEY(k, k_len, nod_flag);
    }
  }
  else
  {
    k = rt_PAGE_FIRST_KEY(page_buf, nod_flag);
  }
  last = rt_PAGE_END(page_buf);

  for (; k < last; k = rt_PAGE_NEXT_KEY(k, k_len, nod_flag))
  {
    if (nod_flag) 
    { 
      /* this is an internal node in the tree */
      switch ((res = rtree_get_req(info, keyinfo, key_length, 
                                  _mi_kpos(nod_flag, k), level + 1)))
      {
        case 0: /* found - exit from recursion */
          *saved_key = k - page_buf;
          goto ok;
        case 1: /* not found - continue searching */
          info->rtree_recursion_depth = level;
          break;
        default:
        case -1: /* error */
          goto err1;
      }
    }
    else 
    { 
      /* this is a leaf */
      uchar *after_key = rt_PAGE_NEXT_KEY(k, k_len, nod_flag);
      info->lastpos = _mi_dpos(info, 0, after_key);
      info->lastkey_length = k_len + info->s->base.rec_reflength;
333
      memcpy(info->lastkey, k, info->lastkey_length);
334 335 336 337 338 339 340 341 342 343 344

      info->rtree_recursion_depth = level;
      *saved_key = k - page_buf;

      if (after_key < last)
      {
        info->int_keypos = (uchar*)saved_key;
        memcpy(info->buff, page_buf, keyinfo->block_length);
        info->int_maxpos = rt_PAGE_END(info->buff);
        info->buff_used = 0;
      }
345 346 347 348
      else
      {
	info->buff_used = 1;
      }
349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367

      res = 0;
      goto ok;
    }
  }
  info->lastpos = HA_OFFSET_ERROR;
  my_errno = HA_ERR_KEY_NOT_FOUND;
  res = 1;

ok:
  my_afree((byte*)page_buf);
  return res;

err1:
  my_afree((byte*)page_buf);
  info->lastpos = HA_OFFSET_ERROR;
  return -1;
}

368

369
/*
370 371 372 373 374 375
  Get first key in r-tree

  RETURN
    -1	Error
    0	Found
    1	Not found
376
*/
377

378 379 380 381 382 383
int rtree_get_first(MI_INFO *info, uint keynr, uint key_length)
{
  my_off_t root;
  MI_KEYDEF *keyinfo = info->s->keyinfo + keynr;

  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 390 391 392 393 394

  info->rtree_recursion_depth = -1;
  info->buff_used = 1;
  
  return rtree_get_req(info, &keyinfo[keynr], key_length, root, 0);
}

395 396 397 398 399 400 401 402

/* 
  Get next key in r-tree

  RETURN
    -1	Error
    0	Found
    1	Not found
403
*/
404

405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433
int rtree_get_next(MI_INFO *info, uint keynr, uint key_length)
{
  my_off_t root;
  MI_KEYDEF *keyinfo = info->s->keyinfo + keynr;

  if (!info->buff_used)
  {
    uint k_len = keyinfo->keylength - info->s->base.rec_reflength;
    /* rt_PAGE_NEXT_KEY(info->int_keypos) */
    uchar *key = info->buff + *(int*)info->int_keypos + k_len + 
                 info->s->base.rec_reflength;
    /* rt_PAGE_NEXT_KEY(key) */
    uchar *after_key = key + k_len + info->s->base.rec_reflength; 

    info->lastpos = _mi_dpos(info, 0, after_key);
    info->lastkey_length = k_len + info->s->base.rec_reflength;
    memcpy(info->lastkey, key, k_len + info->s->base.rec_reflength);

    *(int*)info->int_keypos = key - info->buff;
    if (after_key >= info->int_maxpos)
    {
      info->buff_used = 1;
    }

    return 0;
  }
  else
  {
    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 440 441 442
  
    return rtree_get_req(info, &keyinfo[keynr], key_length, root, 0);
  }
}

443

444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467
/*
  Choose non-leaf better key for insertion
*/

#ifdef PICK_BY_PERIMETER
static uchar *rtree_pick_key(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *key, 
			     uint key_length, uchar *page_buf, uint nod_flag)
{
  double increase;
  double best_incr = DBL_MAX;
  double perimeter;
  double best_perimeter;
  uchar *best_key;
  uchar *k = rt_PAGE_FIRST_KEY(page_buf, nod_flag);
  uchar *last = rt_PAGE_END(page_buf);

  LINT_INIT(best_perimeter);
  LINT_INIT(best_key);

  for (; k < last; k = rt_PAGE_NEXT_KEY(k, key_length, nod_flag))
  {
    if ((increase = rtree_perimeter_increase(keyinfo->seg, k, key, key_length,
					     &perimeter)) == -1)
      return NULL;
468 469
    if ((increase < best_incr)||
	(increase == best_incr && perimeter < best_perimeter))
470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497
    {
      best_key = k;
      best_perimeter= perimeter;
      best_incr = increase;
    }
  }
  return best_key;
}

#endif /*PICK_BY_PERIMETER*/

#ifdef PICK_BY_AREA
static uchar *rtree_pick_key(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *key, 
			     uint key_length, uchar *page_buf, uint nod_flag)
{
  double increase;
  double best_incr = DBL_MAX;
  double area;
  double best_area;
  uchar *best_key;
  uchar *k = rt_PAGE_FIRST_KEY(page_buf, nod_flag);
  uchar *last = rt_PAGE_END(page_buf);

  LINT_INIT(best_area);
  LINT_INIT(best_key);

  for (; k < last; k = rt_PAGE_NEXT_KEY(k, key_length, nod_flag))
  {
498
    /* The following is safe as -1.0 is an exact number */
499
    if ((increase = rtree_area_increase(keyinfo->seg, k, key, key_length, 
500
                                        &area)) == -1.0)
501
      return NULL;
502
    /* The following should be safe, even if we compare doubles */
503 504 505 506 507 508 509 510
    if (increase < best_incr)
    {
      best_key = k;
      best_area = area;
      best_incr = increase;
    }
    else
    {
511
      /* The following should be safe, even if we compare doubles */
512 513 514 515 516 517 518 519 520 521 522 523 524
      if ((increase == best_incr) && (area < best_area))
      {
        best_key = k;
        best_area = area;
        best_incr = increase;
      }
    }
  }
  return best_key;
}

#endif /*PICK_BY_AREA*/

525
/*
526 527 528 529 530 531
  Go down and insert key into tree

  RETURN
    -1	Error
    0	Child was not split
    1	Child was split
532
*/
533

534 535 536 537 538 539 540 541
static int rtree_insert_req(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *key, 
                            uint key_length, my_off_t page, my_off_t *new_page, 
                            int ins_level, int level)
{
  uchar *k;
  uint nod_flag;
  uchar *page_buf;
  int res;
542
  DBUG_ENTER("rtree_insert_req");
543 544 545 546 547

  if (!(page_buf = (uchar*)my_alloca((uint)keyinfo->block_length + 
                                     MI_MAX_KEY_BUFF)))
  {
    my_errno = HA_ERR_OUT_OF_MEM;
548
    DBUG_RETURN(-1); /* purecov: inspected */
549
  }
550
  if (!_mi_fetch_keypage(info, keyinfo, page, DFLT_INIT_HITS, page_buf, 0))
551 552
    goto err1;
  nod_flag = mi_test_if_nod(page_buf);
553 554
  DBUG_PRINT("rtree", ("page: %lu  level: %d  ins_level: %d  nod_flag: %u",
                       (ulong) page, level, ins_level, nod_flag));
555 556 557 558

  if ((ins_level == -1 && nod_flag) ||       /* key: go down to leaf */
      (ins_level > -1 && ins_level > level)) /* branch: go down to ins_level */
  { 
559
    if ((k = rtree_pick_key(info, keyinfo, key, key_length, page_buf, 
560 561 562 563 564 565 566 567
                             nod_flag)) == NULL)
      goto err1;
    switch ((res = rtree_insert_req(info, keyinfo, key, key_length, 
                     _mi_kpos(nod_flag, k), new_page, ins_level, level + 1)))
    {
      case 0: /* child was not split */
      {
        rtree_combine_rect(keyinfo->seg, k, key, k, key_length);
568
        if (_mi_write_keypage(info, keyinfo, page, DFLT_INIT_HITS, page_buf))
569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584
          goto err1;
        goto ok;
      }
      case 1: /* child was split */
      {
        uchar *new_key = page_buf + keyinfo->block_length + nod_flag;
        /* set proper MBR for key */
        if (rtree_set_key_mbr(info, keyinfo, k, key_length, 
                            _mi_kpos(nod_flag, k)))
          goto err1;
        /* add new key for new page */
        _mi_kpointer(info, new_key - nod_flag, *new_page);
        if (rtree_set_key_mbr(info, keyinfo, new_key, key_length, *new_page))
          goto err1;
        res = rtree_add_key(info, keyinfo, new_key, key_length, 
                           page_buf, new_page);
585
        if (_mi_write_keypage(info, keyinfo, page, DFLT_INIT_HITS, page_buf))
586 587 588 589 590 591 592 593 594 595 596 597 598
          goto err1;
        goto ok;
      }
      default:
      case -1: /* error */
      {
        goto err1;
      }
    }
  }
  else
  { 
    res = rtree_add_key(info, keyinfo, key, key_length, page_buf, new_page);
599
    if (_mi_write_keypage(info, keyinfo, page, DFLT_INIT_HITS, page_buf))
600 601 602 603 604 605
      goto err1;
    goto ok;
  }

ok:
  my_afree((byte*)page_buf);
606
  DBUG_RETURN(res);
607 608 609

err1:
  my_afree((byte*)page_buf);
610
  DBUG_RETURN(-1); /* purecov: inspected */
611 612
}

613

614
/*
615 616 617 618 619 620
  Insert key into the tree

  RETURN
    -1	Error
    0	Root was not split
    1	Root was split
621
*/
622

623 624 625 626 627 628 629
static int rtree_insert_level(MI_INFO *info, uint keynr, uchar *key, 
                             uint key_length, int ins_level)
{
  my_off_t old_root;
  MI_KEYDEF *keyinfo = info->s->keyinfo + keynr;
  int res;
  my_off_t new_page;
630 631
  DBUG_ENTER("rtree_insert_level");

632 633 634 635
  if ((old_root = info->s->state.key_root[keynr]) == HA_OFFSET_ERROR)
  {
    int res;

636
    if ((old_root = _mi_new(info, keyinfo, DFLT_INIT_HITS)) == HA_OFFSET_ERROR)
637
      DBUG_RETURN(-1);
638 639 640
    info->buff_used = 1;
    mi_putint(info->buff, 2, 0);
    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
  }

bar@bar.mysql.r18.ru's avatar
bar@bar.mysql.r18.ru committed
647
  switch ((res = rtree_insert_req(info, keyinfo, key, key_length, 
648 649 650 651 652 653 654 655 656 657 658 659 660
                                  old_root, &new_page, ins_level, 0)))
  {
    case 0: /* root was not split */
    {
      break;
    }
    case 1: /* root was split, grow a new root */
    { 
      uchar *new_root_buf;
      my_off_t new_root;
      uchar *new_key;
      uint nod_flag = info->s->base.key_reflength;

661
      DBUG_PRINT("rtree", ("root was split, grow a new root"));
662 663 664 665
      if (!(new_root_buf = (uchar*)my_alloca((uint)keyinfo->block_length + 
                                             MI_MAX_KEY_BUFF)))
      {
        my_errno = HA_ERR_OUT_OF_MEM;
666
        DBUG_RETURN(-1); /* purecov: inspected */
667 668 669
      }

      mi_putint(new_root_buf, 2, nod_flag);
670
      if ((new_root = _mi_new(info, keyinfo, DFLT_INIT_HITS)) ==
671
	  HA_OFFSET_ERROR)
672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687
        goto err1;

      new_key = new_root_buf + keyinfo->block_length + nod_flag;

      _mi_kpointer(info, new_key - nod_flag, old_root);
      if (rtree_set_key_mbr(info, keyinfo, new_key, key_length, old_root))
        goto err1;
      if (rtree_add_key(info, keyinfo, new_key, key_length, new_root_buf, NULL) 
          == -1)
        goto err1;
      _mi_kpointer(info, new_key - nod_flag, new_page);
      if (rtree_set_key_mbr(info, keyinfo, new_key, key_length, new_page))
        goto err1;
      if (rtree_add_key(info, keyinfo, new_key, key_length, new_root_buf, NULL) 
          == -1)
        goto err1;
688 689
      if (_mi_write_keypage(info, keyinfo, new_root,
                            DFLT_INIT_HITS, new_root_buf))
690 691
        goto err1;
      info->s->state.key_root[keynr] = new_root;
692 693
      DBUG_PRINT("rtree", ("new root page: %lu  level: %d  nod_flag: %u",
                           (ulong) new_root, 0, mi_test_if_nod(new_root_buf)));
694 695 696 697 698

      my_afree((byte*)new_root_buf);
      break;
err1:
      my_afree((byte*)new_root_buf);
699
      DBUG_RETURN(-1); /* purecov: inspected */
700 701 702 703 704 705 706
    }
    default:
    case -1: /* error */
    {
      break;
    }
  }
707
  DBUG_RETURN(res);
708 709
}

710

711
/*
712 713 714 715 716
  Insert key into the tree - interface function

  RETURN
    -1	Error
    0	OK
717
*/
718

719 720
int rtree_insert(MI_INFO *info, uint keynr, uchar *key, uint key_length)
{
721 722 723 724
  DBUG_ENTER("rtree_insert");
  DBUG_RETURN((!key_length ||
               (rtree_insert_level(info, keynr, key, key_length, -1) == -1)) ?
              -1 : 0);
725 726
}

727

728
/* 
729 730 731 732 733
  Fill reinsert page buffer 

  RETURN
    -1	Error
    0	OK
734
*/
735

736 737 738
static int rtree_fill_reinsert_list(stPageList *ReinsertList, my_off_t page, 
                                    int level)
{
739 740
  DBUG_ENTER("rtree_fill_reinsert_list");
  DBUG_PRINT("rtree", ("page: %lu  level: %d", (ulong) page, level));
741 742 743 744 745 746 747 748 749 750 751
  if (ReinsertList->n_pages == ReinsertList->m_pages)
  {
    ReinsertList->m_pages += REINSERT_BUFFER_INC;
    if (!(ReinsertList->pages = (stPageLevel*)my_realloc((gptr)ReinsertList->pages, 
      ReinsertList->m_pages * sizeof(stPageLevel), MYF(MY_ALLOW_ZERO_PTR))))
      goto err1;
  }
  /* save page to ReinsertList */
  ReinsertList->pages[ReinsertList->n_pages].offs = page;
  ReinsertList->pages[ReinsertList->n_pages].level = level;
  ReinsertList->n_pages++;
752
  DBUG_RETURN(0);
753 754

err1:
755
  DBUG_RETURN(-1); /* purecov: inspected */
756 757
}

758

759
/*
760 761 762 763 764 765 766
  Go down and delete key from the tree

  RETURN
    -1	Error
    0	Deleted
    1	Not found
    2	Empty leaf
767
*/
768

769 770 771 772 773 774 775 776 777 778
static int rtree_delete_req(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *key, 
                           uint key_length, my_off_t page, uint *page_size, 
                           stPageList *ReinsertList, int level)
{
  uchar *k;
  uchar *last;
  ulong i;
  uint nod_flag;
  uchar *page_buf;
  int res;
779
  DBUG_ENTER("rtree_delete_req");
780 781 782 783

  if (!(page_buf = (uchar*)my_alloca((uint)keyinfo->block_length)))
  {
    my_errno = HA_ERR_OUT_OF_MEM;
784
    DBUG_RETURN(-1); /* purecov: inspected */
785
  }
786
  if (!_mi_fetch_keypage(info, keyinfo, page, DFLT_INIT_HITS, page_buf, 0))
787 788
    goto err1;
  nod_flag = mi_test_if_nod(page_buf);
789 790
  DBUG_PRINT("rtree", ("page: %lu  level: %d  nod_flag: %u",
                       (ulong) page, level, nod_flag));
791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810

  k = rt_PAGE_FIRST_KEY(page_buf, nod_flag);
  last = rt_PAGE_END(page_buf);

  for (i = 0; k < last; k = rt_PAGE_NEXT_KEY(k, key_length, nod_flag), ++i)
  {
    if (nod_flag)
    { 
      /* not leaf */
      if (!rtree_key_cmp(keyinfo->seg, key, k, key_length, MBR_WITHIN))
      {
        switch ((res = rtree_delete_req(info, keyinfo, key, key_length, 
                  _mi_kpos(nod_flag, k), page_size, ReinsertList, level + 1)))
        {
          case 0: /* deleted */
          { 
            /* test page filling */
            if (*page_size + key_length >= rt_PAGE_MIN_SIZE(keyinfo->block_length)) 
            { 
              /* OK */
811
              /* Calculate a new key value (MBR) for the shrinked block. */
812 813 814
              if (rtree_set_key_mbr(info, keyinfo, k, key_length, 
                                  _mi_kpos(nod_flag, k)))
                goto err1;
815 816
              if (_mi_write_keypage(info, keyinfo, page,
                                    DFLT_INIT_HITS, page_buf))
817 818 819 820
                goto err1;
            }
            else
            { 
821 822 823 824 825 826
              /*
                Too small: delete key & add it descendant to reinsert list.
                Store position and level of the block so that it can be
                accessed later for inserting the remaining keys.
              */
              DBUG_PRINT("rtree", ("too small. move block to reinsert list"));
827 828 829
              if (rtree_fill_reinsert_list(ReinsertList, _mi_kpos(nod_flag, k),
                                           level + 1))
                goto err1;
830 831 832 833 834 835 836 837
              /*
                Delete the key that references the block. This makes the
                block disappear from the index. Hence we need to insert
                its remaining keys later. Note: if the block is a branch
                block, we do not only remove this block, but the whole
                subtree. So we need to re-insert its keys on the same
                level later to reintegrate the subtrees.
              */
838
              rtree_delete_key(info, page_buf, k, key_length, nod_flag);
839 840
              if (_mi_write_keypage(info, keyinfo, page,
                                    DFLT_INIT_HITS, page_buf))
841 842 843 844 845 846 847 848 849 850 851 852 853
                goto err1;
              *page_size = mi_getint(page_buf);
            }
            
            goto ok;
          }
          case 1: /* not found - continue searching */
          {
            break;
          }
          case 2: /* vacuous case: last key in the leaf */
          {
            rtree_delete_key(info, page_buf, k, key_length, nod_flag);
854 855
            if (_mi_write_keypage(info, keyinfo, page,
                                  DFLT_INIT_HITS, page_buf))
856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879
              goto err1;
            *page_size = mi_getint(page_buf);
            res = 0;
            goto ok;
          }
          default: /* error */
          case -1:
          {
            goto err1;
          }
        }
      }
    }
    else  
    {
      /* leaf */
      if (!rtree_key_cmp(keyinfo->seg, key, k, key_length, MBR_EQUAL | MBR_DATA))
      {
        rtree_delete_key(info, page_buf, k, key_length, nod_flag);
        *page_size = mi_getint(page_buf);
        if (*page_size == 2) 
        {
          /* last key in the leaf */
          res = 2;
880
          if (_mi_dispose(info, keyinfo, page, DFLT_INIT_HITS))
881 882 883 884 885
            goto err1;
        }
        else
        {
          res = 0;
886
          if (_mi_write_keypage(info, keyinfo, page, DFLT_INIT_HITS, page_buf))
887 888 889 890 891 892 893 894 895 896
            goto err1;
        }
        goto ok;
      }
    }
  }
  res = 1;

ok:
  my_afree((byte*)page_buf);
897
  DBUG_RETURN(res);
898 899 900

err1:
  my_afree((byte*)page_buf);
901
  DBUG_RETURN(-1); /* purecov: inspected */
902 903
}

904

905
/*
906 907 908 909 910
  Delete key - interface function

  RETURN
    -1	Error
    0	Deleted
911
*/
912

913 914 915 916 917 918
int rtree_delete(MI_INFO *info, uint keynr, uchar *key, uint key_length)
{
  uint page_size;
  stPageList ReinsertList;
  my_off_t old_root;
  MI_KEYDEF *keyinfo = info->s->keyinfo + keynr;
919
  DBUG_ENTER("rtree_delete");
920 921 922

  if ((old_root = info->s->state.key_root[keynr]) == HA_OFFSET_ERROR)
  {
923
    my_errno= HA_ERR_END_OF_FILE;
924
    DBUG_RETURN(-1); /* purecov: inspected */
925
  }
926 927
  DBUG_PRINT("rtree", ("starting deletion at root page: %lu",
                       (ulong) old_root));
928 929 930 931 932 933 934 935

  ReinsertList.pages = NULL;
  ReinsertList.n_pages = 0;
  ReinsertList.m_pages = 0;
  
  switch (rtree_delete_req(info, keyinfo, key, key_length, old_root, 
                                 &page_size, &ReinsertList, 0))
  {
936
    case 2: /* empty */
937 938
    {
      info->s->state.key_root[keynr] = HA_OFFSET_ERROR;
939
      DBUG_RETURN(0);
940
    }
941
    case 0: /* deleted */
942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957
    {
      uint nod_flag;
      ulong i;
      for (i = 0; i < ReinsertList.n_pages; ++i)
      {
        uchar *page_buf;
        uint nod_flag;
        uchar *k;
        uchar *last;

        if (!(page_buf = (uchar*)my_alloca((uint)keyinfo->block_length)))
        {
          my_errno = HA_ERR_OUT_OF_MEM;
          goto err1;
        }
        if (!_mi_fetch_keypage(info, keyinfo, ReinsertList.pages[i].offs, 
958
                               DFLT_INIT_HITS, page_buf, 0))
959 960
          goto err1;
        nod_flag = mi_test_if_nod(page_buf);
961 962 963 964 965
        DBUG_PRINT("rtree", ("reinserting keys from "
                             "page: %lu  level: %d  nod_flag: %u",
                             (ulong) ReinsertList.pages[i].offs,
                             ReinsertList.pages[i].level, nod_flag));

966 967 968 969
        k = rt_PAGE_FIRST_KEY(page_buf, nod_flag);
        last = rt_PAGE_END(page_buf);
        for (; k < last; k = rt_PAGE_NEXT_KEY(k, key_length, nod_flag))
        {
970 971 972
          int res;
          if ((res= rtree_insert_level(info, keynr, k, key_length,
                                       ReinsertList.pages[i].level)) == -1)
973 974 975 976
          {
            my_afree((byte*)page_buf);
            goto err1;
          }
977 978
          if (res)
          {
979
            ulong j;
980 981 982 983 984 985 986 987 988
            DBUG_PRINT("rtree", ("root has been split, adjust levels"));
            for (j= i; j < ReinsertList.n_pages; j++)
            {
              ReinsertList.pages[j].level++;
              DBUG_PRINT("rtree", ("keys from page: %lu  now level: %d",
                                   (ulong) ReinsertList.pages[i].offs,
                                   ReinsertList.pages[i].level));
            }
          }
989 990
        }
        my_afree((byte*)page_buf);
991 992
        if (_mi_dispose(info, keyinfo, ReinsertList.pages[i].offs,
            DFLT_INIT_HITS))
993 994 995
          goto err1;
      }
      if (ReinsertList.pages)
ram@mysql.r18.ru's avatar
ram@mysql.r18.ru committed
996
        my_free((byte*) ReinsertList.pages, MYF(0));
997 998 999 1000

      /* check for redundant root (not leaf, 1 child) and eliminate */
      if ((old_root = info->s->state.key_root[keynr]) == HA_OFFSET_ERROR)
        goto err1;
1001
      if (!_mi_fetch_keypage(info, keyinfo, old_root, DFLT_INIT_HITS,
1002
                             info->buff, 0))
1003 1004 1005
        goto err1;
      nod_flag = mi_test_if_nod(info->buff);
      page_size = mi_getint(info->buff);
1006
      if (nod_flag && (page_size == 2 + key_length + nod_flag))
1007
      {
1008
        my_off_t new_root = _mi_kpos(nod_flag,
1009
                                     rt_PAGE_FIRST_KEY(info->buff, nod_flag));
1010
        if (_mi_dispose(info, keyinfo, old_root, DFLT_INIT_HITS))
1011 1012 1013
          goto err1;
        info->s->state.key_root[keynr] = new_root;
      }
ram@mysql.r18.ru's avatar
ram@mysql.r18.ru committed
1014
      info->update= HA_STATE_DELETED;
1015
      DBUG_RETURN(0);
1016 1017

err1:
1018
      DBUG_RETURN(-1); /* purecov: inspected */
1019 1020 1021 1022
    }
    case 1: /* not found */
    {
      my_errno = HA_ERR_KEY_NOT_FOUND;
1023
      DBUG_RETURN(-1); /* purecov: inspected */
1024 1025 1026 1027
    }
    default:
    case -1: /* error */
    {
1028
      DBUG_RETURN(-1); /* purecov: inspected */
1029 1030 1031 1032
    }
  }
}

1033

1034
/* 
1035 1036 1037 1038
  Estimate number of suitable keys in the tree 

  RETURN
    estimated value
1039
*/
1040

1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061
ha_rows rtree_estimate(MI_INFO *info, uint keynr, uchar *key, 
                       uint key_length, uint flag)
{
  MI_KEYDEF *keyinfo = info->s->keyinfo + keynr;
  my_off_t root;
  uint i = 0;
  uchar *k;
  uchar *last;
  uint nod_flag;
  uchar *page_buf;
  uint k_len;
  double area = 0;
  ha_rows res = 0;

  if (flag & MBR_DISJOINT)
    return info->state->records;

  if ((root = info->s->state.key_root[keynr]) == HA_OFFSET_ERROR)
    return HA_POS_ERROR;
  if (!(page_buf = (uchar*)my_alloca((uint)keyinfo->block_length)))
    return HA_POS_ERROR;
1062
  if (!_mi_fetch_keypage(info, keyinfo, root, DFLT_INIT_HITS, page_buf, 0))
1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076
    goto err1;
  nod_flag = mi_test_if_nod(page_buf);

  k_len = keyinfo->keylength - info->s->base.rec_reflength;

  k = rt_PAGE_FIRST_KEY(page_buf, nod_flag);
  last = rt_PAGE_END(page_buf);

  for (; k < last; k = rt_PAGE_NEXT_KEY(k, k_len, nod_flag), ++i)
  {
    if (nod_flag)
    {
      double k_area = rtree_rect_volume(keyinfo->seg, k, key_length);

1077
      /* The following should be safe, even if we compare doubles */
1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117
      if (k_area == 0)
      {
        if (flag & (MBR_CONTAIN | MBR_INTERSECT))
        {
          area += 1;
        }
        else if (flag & (MBR_WITHIN | MBR_EQUAL))
        {
          if (!rtree_key_cmp(keyinfo->seg, key, k, key_length, MBR_WITHIN))
            area += 1;
        }
        else
          goto err1;
      }
      else
      {
        if (flag & (MBR_CONTAIN | MBR_INTERSECT))
        {
          area += rtree_overlapping_area(keyinfo->seg, key, k, key_length) / 
                  k_area;
        }
        else if (flag & (MBR_WITHIN | MBR_EQUAL))
        {
          if (!rtree_key_cmp(keyinfo->seg, key, k, key_length, MBR_WITHIN))
            area += rtree_rect_volume(keyinfo->seg, key, key_length) /
                    k_area;
        }
        else
          goto err1;
      }
    }
    else
    {
      if (!rtree_key_cmp(keyinfo->seg, key, k, key_length, flag))
        ++res;
    }
  }
  if (nod_flag)
  {
    if (i)
ram@mysql.r18.ru's avatar
ram@mysql.r18.ru committed
1118
      res = (ha_rows) (area / i * info->state->records);
1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129
    else 
      res = HA_POS_ERROR;
  }

  my_afree((byte*)page_buf);
  return res;

err1:
  my_afree((byte*)page_buf);
  return HA_POS_ERROR;
}
1130 1131 1132

#endif /*HAVE_RTREE_KEYS*/