LTP GCOV extension - code coverage report
Current view: directory - storage/maria - ma_rt_index.c
Test: maria-unit-test.html
Date: 2009-03-04 Instrumented lines: 505
Code covered: 0.0 % Executed lines: 0

       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*/

Generated by: LTP GCOV extension version 1.4