rt_index.c
上传用户:romrleung
上传日期:2022-05-23
资源大小:18897k
文件大小:27k
源码类别:

MySQL数据库

开发平台:

Visual C++

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