release/src/router/mysql/storage/myisam/mi_delete.c

   1 /*
   2    Copyright (c) 2000-2008 MySQL AB, 2008, 2009 Sun Microsystems, Inc.
   3    Use is subject to license terms.
   4
   5    This program is free software; you can redistribute it and/or modify
   6    it under the terms of the GNU General Public License as published by
   7    the Free Software Foundation; version 2 of the License.
   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., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301  USA
  17 */
  18
  19 /* Remove a row from a MyISAM table */
  20
  21 #include "fulltext.h"
  22 #include "rt_index.h"
  23
  24 static int d_search(MI_INFO *info,MI_KEYDEF *keyinfo,uint comp_flag,
  25                     uchar *key,uint key_length,my_off_t page,uchar *anc_buff);
  26 static int del(MI_INFO *info,MI_KEYDEF *keyinfo,uchar *key,uchar *anc_buff,
  27                my_off_t leaf_page,uchar *leaf_buff,uchar *keypos,
  28                my_off_t next_block,uchar *ret_key);
  29 static int underflow(MI_INFO *info,MI_KEYDEF *keyinfo,uchar *anc_buff,
  30                      my_off_t leaf_page,uchar *leaf_buff,uchar *keypos);
  31 static uint remove_key(MI_KEYDEF *keyinfo,uint nod_flag,uchar *keypos,
  32                        uchar *lastkey,uchar *page_end,
  33                        my_off_t *next_block);
  34 static int _mi_ck_real_delete(register MI_INFO *info,MI_KEYDEF *keyinfo,
  35                               uchar *key, uint key_length, my_off_t *root);
  36
  37
  38 int mi_delete(MI_INFO *info,const uchar *record)
  39 {
  40   uint i;
  41   uchar *old_key;
  42   int save_errno;
  43   char lastpos[8];
  44
  45   MYISAM_SHARE *share=info->s;
  46   DBUG_ENTER("mi_delete");
  47
  48         /* Test if record is in datafile */
  49
  50   DBUG_EXECUTE_IF("myisam_pretend_crashed_table_on_usage",
  51                   mi_print_error(info->s, HA_ERR_CRASHED);
  52                   DBUG_RETURN(my_errno= HA_ERR_CRASHED););
  53   DBUG_EXECUTE_IF("my_error_test_undefined_error",
  54                   mi_print_error(info->s, INT_MAX);
  55                   DBUG_RETURN(my_errno= INT_MAX););
  56   if (!(info->update & HA_STATE_AKTIV))
  57   {
  58     DBUG_RETURN(my_errno=HA_ERR_KEY_NOT_FOUND); /* No database read */
  59   }
  60   if (share->options & HA_OPTION_READ_ONLY_DATA)
  61   {
  62     DBUG_RETURN(my_errno=EACCES);
  63   }
  64   if (_mi_readinfo(info,F_WRLCK,1))
  65     DBUG_RETURN(my_errno);
  66   if (info->s->calc_checksum)
  67     info->checksum=(*info->s->calc_checksum)(info,record);
  68   if ((*share->compare_record)(info,record))
  69     goto err;                           /* Error on read-check */
  70
  71   if (_mi_mark_file_changed(info))
  72     goto err;
  73
  74         /* Remove all keys from the .ISAM file */
  75
  76   old_key=info->lastkey2;
  77   for (i=0 ; i < share->base.keys ; i++ )
  78   {
  79     if (mi_is_key_active(info->s->state.key_map, i))
  80     {
  81       info->s->keyinfo[i].version++;
  82       if (info->s->keyinfo[i].flag & HA_FULLTEXT )
  83       {
  84         if (_mi_ft_del(info,i, old_key,record,info->lastpos))
  85           goto err;
  86       }
  87       else
  88       {
  89         if (info->s->keyinfo[i].ck_delete(info,i,old_key,
  90                 _mi_make_key(info,i,old_key,record,info->lastpos)))
  91           goto err;
  92       }
  93       /* The above changed info->lastkey2. Inform mi_rnext_same(). */
  94       info->update&= ~HA_STATE_RNEXT_SAME;
  95     }
  96   }
  97
  98   if ((*share->delete_record)(info))
  99     goto err;                           /* Remove record from database */
 100   info->state->checksum-=info->checksum;
 101
 102   info->update= HA_STATE_CHANGED+HA_STATE_DELETED+HA_STATE_ROW_CHANGED;
 103   info->state->records--;
 104
 105   mi_sizestore(lastpos,info->lastpos);
 106   myisam_log_command(MI_LOG_DELETE,info,(uchar*) lastpos,sizeof(lastpos),0);
 107   VOID(_mi_writeinfo(info,WRITEINFO_UPDATE_KEYFILE));
 108   allow_break();                        /* Allow SIGHUP & SIGINT */
 109   if (info->invalidator != 0)
 110   {
 111     DBUG_PRINT("info", ("invalidator... '%s' (delete)", info->filename));
 112     (*info->invalidator)(info->filename);
 113     info->invalidator=0;
 114   }
 115   DBUG_RETURN(0);
 116
 117 err:
 118   save_errno=my_errno;
 119   mi_sizestore(lastpos,info->lastpos);
 120   myisam_log_command(MI_LOG_DELETE,info,(uchar*) lastpos, sizeof(lastpos),0);
 121   if (save_errno != HA_ERR_RECORD_CHANGED)
 122   {
 123     mi_print_error(info->s, HA_ERR_CRASHED);
 124     mi_mark_crashed(info);              /* mark table crashed */
 125   }
 126   VOID(_mi_writeinfo(info,WRITEINFO_UPDATE_KEYFILE));
 127   info->update|=HA_STATE_WRITTEN;       /* Buffer changed */
 128   allow_break();                        /* Allow SIGHUP & SIGINT */
 129   my_errno=save_errno;
 130   if (save_errno == HA_ERR_KEY_NOT_FOUND)
 131   {
 132     mi_print_error(info->s, HA_ERR_CRASHED);
 133     my_errno=HA_ERR_CRASHED;
 134   }
 135
 136   DBUG_RETURN(my_errno);
 137 } /* mi_delete */
 138
 139
 140         /* Remove a key from the btree index */
 141
 142 int _mi_ck_delete(register MI_INFO *info, uint keynr, uchar *key,
 143                   uint key_length)
 144 {
 145   return _mi_ck_real_delete(info, info->s->keyinfo+keynr, key, key_length,
 146                             &info->s->state.key_root[keynr]);
 147 } /* _mi_ck_delete */
 148
 149
 150 static int _mi_ck_real_delete(register MI_INFO *info, MI_KEYDEF *keyinfo,
 151                               uchar *key, uint key_length, my_off_t *root)
 152 {
 153   int error;
 154   uint nod_flag;
 155   my_off_t old_root;
 156   uchar *root_buff;
 157   DBUG_ENTER("_mi_ck_real_delete");
 158
 159   if ((old_root=*root) == HA_OFFSET_ERROR)
 160   {
 161     mi_print_error(info->s, HA_ERR_CRASHED);
 162     DBUG_RETURN(my_errno=HA_ERR_CRASHED);
 163   }
 164   if (!(root_buff= (uchar*) my_alloca((uint) keyinfo->block_length+
 165                                       MI_MAX_KEY_BUFF*2)))
 166   {
 167     DBUG_PRINT("error",("Couldn't allocate memory"));
 168     DBUG_RETURN(my_errno=ENOMEM);
 169   }
 170   DBUG_PRINT("info",("root_page: %ld", (long) old_root));
 171   if (!_mi_fetch_keypage(info,keyinfo,old_root,DFLT_INIT_HITS,root_buff,0))
 172   {
 173     error= -1;
 174     goto err;
 175   }
 176   if ((error=d_search(info,keyinfo,
 177                       (keyinfo->flag & HA_FULLTEXT ? SEARCH_FIND | SEARCH_UPDATE
 178                                                    : SEARCH_SAME),
 179                        key,key_length,old_root,root_buff)) >0)
 180   {
 181     if (error == 2)
 182     {
 183       DBUG_PRINT("test",("Enlarging of root when deleting"));
 184       error=_mi_enlarge_root(info,keyinfo,key,root);
 185     }
 186     else /* error == 1 */
 187     {
 188       if (mi_getint(root_buff) <= (nod_flag=mi_test_if_nod(root_buff))+3)
 189       {
 190         error=0;
 191         if (nod_flag)
 192           *root=_mi_kpos(nod_flag,root_buff+2+nod_flag);
 193         else
 194           *root=HA_OFFSET_ERROR;
 195         if (_mi_dispose(info,keyinfo,old_root,DFLT_INIT_HITS))
 196           error= -1;
 197       }
 198       else
 199         error=_mi_write_keypage(info,keyinfo,old_root,
 200                                 DFLT_INIT_HITS,root_buff);
 201     }
 202   }
 203 err:
 204   my_afree((uchar*) root_buff);
 205   DBUG_PRINT("exit",("Return: %d",error));
 206   DBUG_RETURN(error);
 207 } /* _mi_ck_real_delete */
 208
 209
 210         /*
 211         ** Remove key below key root
 212         ** Return values:
 213         ** 1 if there are less buffers;  In this case anc_buff is not saved
 214         ** 2 if there are more buffers
 215         ** -1 on errors
 216         */
 217
 218 static int d_search(register MI_INFO *info, register MI_KEYDEF *keyinfo,
 219                     uint comp_flag, uchar *key, uint key_length,
 220                     my_off_t page, uchar *anc_buff)
 221 {
 222   int flag,ret_value,save_flag;
 223   uint length,nod_flag,search_key_length;
 224   my_bool last_key;
 225   uchar *leaf_buff,*keypos;
 226   my_off_t UNINIT_VAR(leaf_page),next_block;
 227   uchar lastkey[MI_MAX_KEY_BUFF];
 228   DBUG_ENTER("d_search");
 229   DBUG_DUMP("page",(uchar*) anc_buff,mi_getint(anc_buff));
 230
 231   search_key_length= (comp_flag & SEARCH_FIND) ? key_length : USE_WHOLE_KEY;
 232   flag=(*keyinfo->bin_search)(info,keyinfo,anc_buff,key, search_key_length,
 233                               comp_flag, &keypos, lastkey, &last_key);
 234   if (flag == MI_FOUND_WRONG_KEY)
 235   {
 236     DBUG_PRINT("error",("Found wrong key"));
 237     DBUG_RETURN(-1);
 238   }
 239   nod_flag=mi_test_if_nod(anc_buff);
 240
 241   if (!flag && keyinfo->flag & HA_FULLTEXT)
 242   {
 243     uint off;
 244     int  subkeys;
 245
 246     get_key_full_length_rdonly(off, lastkey);
 247     subkeys=ft_sintXkorr(lastkey+off);
 248     DBUG_ASSERT(info->ft1_to_ft2==0 || subkeys >=0);
 249     comp_flag=SEARCH_SAME;
 250     if (subkeys >= 0)
 251     {
 252       /* normal word, one-level tree structure */
 253       if (info->ft1_to_ft2)
 254       {
 255         /* we're in ft1->ft2 conversion mode. Saving key data */
 256         if (insert_dynamic(info->ft1_to_ft2, (lastkey+off)))
 257         {
 258           DBUG_PRINT("error",("Out of memory"));
 259           DBUG_RETURN(-1);
 260         }
 261       }
 262       else
 263       {
 264         /* we need exact match only if not in ft1->ft2 conversion mode */
 265         flag=(*keyinfo->bin_search)(info,keyinfo,anc_buff,key,USE_WHOLE_KEY,
 266                                     comp_flag, &keypos, lastkey, &last_key);
 267       }
 268       /* fall through to normal delete */
 269     }
 270     else
 271     {
 272       /* popular word. two-level tree. going down */
 273       uint tmp_key_length;
 274       my_off_t root;
 275       uchar *kpos=keypos;
 276
 277       if (!(tmp_key_length=(*keyinfo->get_key)(keyinfo,nod_flag,&kpos,lastkey)))
 278       {
 279         mi_print_error(info->s, HA_ERR_CRASHED);
 280         my_errno= HA_ERR_CRASHED;
 281         DBUG_RETURN(-1);
 282       }
 283       root=_mi_dpos(info,nod_flag,kpos);
 284       if (subkeys == -1)
 285       {
 286         /* the last entry in sub-tree */
 287         if (_mi_dispose(info, keyinfo, root,DFLT_INIT_HITS))
 288           DBUG_RETURN(-1);
 289         /* fall through to normal delete */
 290       }
 291       else
 292       {
 293         keyinfo=&info->s->ft2_keyinfo;
 294         kpos-=keyinfo->keylength+nod_flag; /* we'll modify key entry 'in vivo' */
 295         get_key_full_length_rdonly(off, key);
 296         key+=off;
 297         ret_value=_mi_ck_real_delete(info, &info->s->ft2_keyinfo,
 298             key, HA_FT_WLEN, &root);
 299         _mi_dpointer(info, kpos+HA_FT_WLEN, root);
 300         subkeys++;
 301         ft_intXstore(kpos, subkeys);
 302         if (!ret_value)
 303           ret_value=_mi_write_keypage(info,keyinfo,page,
 304                                       DFLT_INIT_HITS,anc_buff);
 305         DBUG_PRINT("exit",("Return: %d",ret_value));
 306         DBUG_RETURN(ret_value);
 307       }
 308     }
 309   }
 310   leaf_buff=0;
 311   LINT_INIT(leaf_page);
 312   if (nod_flag)
 313   {
 314     leaf_page=_mi_kpos(nod_flag,keypos);
 315     if (!(leaf_buff= (uchar*) my_alloca((uint) keyinfo->block_length+
 316                                         MI_MAX_KEY_BUFF*2)))
 317     {
 318       DBUG_PRINT("error",("Couldn't allocate memory"));
 319       my_errno=ENOMEM;
 320       DBUG_PRINT("exit",("Return: %d",-1));
 321       DBUG_RETURN(-1);
 322     }
 323     if (!_mi_fetch_keypage(info,keyinfo,leaf_page,DFLT_INIT_HITS,leaf_buff,0))
 324       goto err;
 325   }
 326
 327   if (flag != 0)
 328   {
 329     if (!nod_flag)
 330     {
 331       DBUG_PRINT("error",("Didn't find key"));
 332       mi_print_error(info->s, HA_ERR_CRASHED);
 333       my_errno=HA_ERR_CRASHED;          /* This should newer happend */
 334       goto err;
 335     }
 336     save_flag=0;
 337     ret_value=d_search(info,keyinfo,comp_flag,key,key_length,
 338                        leaf_page,leaf_buff);
 339   }
 340   else
 341   {                                             /* Found key */
 342     uint tmp;
 343     length=mi_getint(anc_buff);
 344     if (!(tmp= remove_key(keyinfo,nod_flag,keypos,lastkey,anc_buff+length,
 345                           &next_block)))
 346       goto err;
 347
 348     length-= tmp;
 349
 350     mi_putint(anc_buff,length,nod_flag);
 351     if (!nod_flag)
 352     {                                           /* On leaf page */
 353       if (_mi_write_keypage(info,keyinfo,page,DFLT_INIT_HITS,anc_buff))
 354       {
 355         DBUG_PRINT("exit",("Return: %d",-1));
 356         DBUG_RETURN(-1);
 357       }
 358       /* Page will be update later if we return 1 */
 359       DBUG_RETURN(test(length <= (info->quick_mode ? MI_MIN_KEYBLOCK_LENGTH :
 360                                   (uint) keyinfo->underflow_block_length)));
 361     }
 362     save_flag=1;
 363     ret_value=del(info,keyinfo,key,anc_buff,leaf_page,leaf_buff,keypos,
 364                   next_block,lastkey);
 365   }
 366   if (ret_value >0)
 367   {
 368     save_flag=1;
 369     if (ret_value == 1)
 370       ret_value= underflow(info,keyinfo,anc_buff,leaf_page,leaf_buff,keypos);
 371     else
 372     {                           /* This happens only with packed keys */
 373       DBUG_PRINT("test",("Enlarging of key when deleting"));
 374       if (!_mi_get_last_key(info,keyinfo,anc_buff,lastkey,keypos,&length))
 375       {
 376         goto err;
 377       }
 378       ret_value=_mi_insert(info,keyinfo,key,anc_buff,keypos,lastkey,
 379                            (uchar*) 0,(uchar*) 0,(my_off_t) 0,(my_bool) 0);
 380     }
 381   }
 382   if (ret_value == 0 && mi_getint(anc_buff) > keyinfo->block_length)
 383   {
 384     save_flag=1;
 385     ret_value=_mi_split_page(info,keyinfo,key,anc_buff,lastkey,0) | 2;
 386   }
 387   if (save_flag && ret_value != 1)
 388     ret_value|=_mi_write_keypage(info,keyinfo,page,DFLT_INIT_HITS,anc_buff);
 389   else
 390   {
 391     DBUG_DUMP("page",(uchar*) anc_buff,mi_getint(anc_buff));
 392   }
 393   my_afree((uchar*) leaf_buff);
 394   DBUG_PRINT("exit",("Return: %d",ret_value));
 395   DBUG_RETURN(ret_value);
 396
 397 err:
 398   my_afree((uchar*) leaf_buff);
 399   DBUG_PRINT("exit",("Error: %d",my_errno));
 400   DBUG_RETURN (-1);
 401 } /* d_search */
 402
 403
 404         /* Remove a key that has a page-reference */
 405
 406 static int del(register MI_INFO *info, register MI_KEYDEF *keyinfo, uchar *key,
 407                uchar *anc_buff, my_off_t leaf_page, uchar *leaf_buff,
 408                uchar *keypos,           /* Pos to where deleted key was */
 409                my_off_t next_block,
 410                uchar *ret_key)          /* key before keypos in anc_buff */
 411 {
 412   int ret_value,length;
 413   uint a_length,nod_flag,tmp;
 414   my_off_t next_page;
 415   uchar keybuff[MI_MAX_KEY_BUFF],*endpos,*next_buff,*key_start, *prev_key;
 416   MYISAM_SHARE *share=info->s;
 417   MI_KEY_PARAM s_temp;
 418   DBUG_ENTER("del");
 419   DBUG_PRINT("enter",("leaf_page: %ld  keypos: 0x%lx", (long) leaf_page,
 420                       (ulong) keypos));
 421   DBUG_DUMP("leaf_buff",(uchar*) leaf_buff,mi_getint(leaf_buff));
 422
 423   endpos=leaf_buff+mi_getint(leaf_buff);
 424   if (!(key_start=_mi_get_last_key(info,keyinfo,leaf_buff,keybuff,endpos,
 425                                    &tmp)))
 426     DBUG_RETURN(-1);
 427
 428   if ((nod_flag=mi_test_if_nod(leaf_buff)))
 429   {
 430     next_page= _mi_kpos(nod_flag,endpos);
 431     if (!(next_buff= (uchar*) my_alloca((uint) keyinfo->block_length+
 432                                         MI_MAX_KEY_BUFF*2)))
 433       DBUG_RETURN(-1);
 434     if (!_mi_fetch_keypage(info,keyinfo,next_page,DFLT_INIT_HITS,next_buff,0))
 435       ret_value= -1;
 436     else
 437     {
 438       DBUG_DUMP("next_page",(uchar*) next_buff,mi_getint(next_buff));
 439       if ((ret_value=del(info,keyinfo,key,anc_buff,next_page,next_buff,
 440                          keypos,next_block,ret_key)) >0)
 441       {
 442         endpos=leaf_buff+mi_getint(leaf_buff);
 443         if (ret_value == 1)
 444         {
 445           ret_value=underflow(info,keyinfo,leaf_buff,next_page,
 446                               next_buff,endpos);
 447           if (ret_value == 0 && mi_getint(leaf_buff) > keyinfo->block_length)
 448           {
 449             ret_value=_mi_split_page(info,keyinfo,key,leaf_buff,ret_key,0) | 2;
 450           }
 451         }
 452         else
 453         {
 454           DBUG_PRINT("test",("Inserting of key when deleting"));
 455           if (!_mi_get_last_key(info,keyinfo,leaf_buff,keybuff,endpos,
 456                                 &tmp))
 457             goto err;
 458           ret_value=_mi_insert(info,keyinfo,key,leaf_buff,endpos,keybuff,
 459                                (uchar*) 0,(uchar*) 0,(my_off_t) 0,0);
 460         }
 461       }
 462       if (_mi_write_keypage(info,keyinfo,leaf_page,DFLT_INIT_HITS,leaf_buff))
 463         goto err;
 464     }
 465     my_afree((uchar*) next_buff);
 466     DBUG_RETURN(ret_value);
 467   }
 468
 469         /* Remove last key from leaf page */
 470
 471   mi_putint(leaf_buff,key_start-leaf_buff,nod_flag);
 472   if (_mi_write_keypage(info,keyinfo,leaf_page,DFLT_INIT_HITS,leaf_buff))
 473     goto err;
 474
 475         /* Place last key in ancestor page on deleted key position */
 476
 477   a_length=mi_getint(anc_buff);
 478   endpos=anc_buff+a_length;
 479   if (keypos != anc_buff+2+share->base.key_reflength &&
 480       !_mi_get_last_key(info,keyinfo,anc_buff,ret_key,keypos,&tmp))
 481     goto err;
 482   prev_key=(keypos == anc_buff+2+share->base.key_reflength ?
 483             0 : ret_key);
 484   length=(*keyinfo->pack_key)(keyinfo,share->base.key_reflength,
 485                               keypos == endpos ? (uchar*) 0 : keypos,
 486                               prev_key, prev_key,
 487                               keybuff,&s_temp);
 488   if (length > 0)
 489     bmove_upp((uchar*) endpos+length,(uchar*) endpos,(uint) (endpos-keypos));
 490   else
 491     bmove(keypos,keypos-length, (int) (endpos-keypos)+length);
 492   (*keyinfo->store_key)(keyinfo,keypos,&s_temp);
 493   /* Save pointer to next leaf */
 494   if (!(*keyinfo->get_key)(keyinfo,share->base.key_reflength,&keypos,ret_key))
 495     goto err;
 496   _mi_kpointer(info,keypos - share->base.key_reflength,next_block);
 497   mi_putint(anc_buff,a_length+length,share->base.key_reflength);
 498
 499   DBUG_RETURN( mi_getint(leaf_buff) <=
 500                (info->quick_mode ? MI_MIN_KEYBLOCK_LENGTH :
 501                 (uint) keyinfo->underflow_block_length));
 502 err:
 503   DBUG_RETURN(-1);
 504 } /* del */
 505
 506
 507         /* Balances adjacent pages if underflow occours */
 508
 509 static int underflow(register MI_INFO *info, register MI_KEYDEF *keyinfo,
 510                      uchar *anc_buff,
 511                      my_off_t leaf_page,/* Ancestor page and underflow page */
 512                      uchar *leaf_buff,
 513                      uchar *keypos)     /* Position to pos after key */
 514 {
 515   int t_length;
 516   uint length,anc_length,buff_length,leaf_length,p_length,s_length,nod_flag,
 517        key_reflength,key_length;
 518   my_off_t next_page;
 519   uchar anc_key[MI_MAX_KEY_BUFF],leaf_key[MI_MAX_KEY_BUFF],
 520         *buff,*endpos,*next_keypos,*anc_pos,*half_pos,*temp_pos,*prev_key,
 521         *after_key;
 522   MI_KEY_PARAM s_temp;
 523   MYISAM_SHARE *share=info->s;
 524   DBUG_ENTER("underflow");
 525   DBUG_PRINT("enter",("leaf_page: %ld  keypos: 0x%lx",(long) leaf_page,
 526                       (ulong) keypos));
 527   DBUG_DUMP("anc_buff",(uchar*) anc_buff,mi_getint(anc_buff));
 528   DBUG_DUMP("leaf_buff",(uchar*) leaf_buff,mi_getint(leaf_buff));
 529
 530   buff=info->buff;
 531   info->buff_used=1;
 532   next_keypos=keypos;
 533   nod_flag=mi_test_if_nod(leaf_buff);
 534   p_length=nod_flag+2;
 535   anc_length=mi_getint(anc_buff);
 536   leaf_length=mi_getint(leaf_buff);
 537   key_reflength=share->base.key_reflength;
 538   if (info->s->keyinfo+info->lastinx == keyinfo)
 539     info->page_changed=1;
 540
 541   if ((keypos < anc_buff+anc_length && (info->state->records & 1)) ||
 542       keypos == anc_buff+2+key_reflength)
 543   {                                     /* Use page right of anc-page */
 544     DBUG_PRINT("test",("use right page"));
 545
 546     if (keyinfo->flag & HA_BINARY_PACK_KEY)
 547     {
 548       if (!(next_keypos=_mi_get_key(info, keyinfo,
 549                                     anc_buff, buff, keypos, &length)))
 550         goto err;
 551     }
 552     else
 553     {
 554       /* Got to end of found key */
 555       buff[0]=buff[1]=0;        /* Avoid length error check if packed key */
 556       if (!(*keyinfo->get_key)(keyinfo,key_reflength,&next_keypos,
 557                                buff))
 558       goto err;
 559     }
 560     next_page= _mi_kpos(key_reflength,next_keypos);
 561     if (!_mi_fetch_keypage(info,keyinfo,next_page,DFLT_INIT_HITS,buff,0))
 562       goto err;
 563     buff_length=mi_getint(buff);
 564     DBUG_DUMP("next",(uchar*) buff,buff_length);
 565
 566     /* find keys to make a big key-page */
 567     bmove((uchar*) next_keypos-key_reflength,(uchar*) buff+2,
 568           key_reflength);
 569     if (!_mi_get_last_key(info,keyinfo,anc_buff,anc_key,next_keypos,&length)
 570         || !_mi_get_last_key(info,keyinfo,leaf_buff,leaf_key,
 571                              leaf_buff+leaf_length,&length))
 572       goto err;
 573
 574     /* merge pages and put parting key from anc_buff between */
 575     prev_key=(leaf_length == p_length ? (uchar*) 0 : leaf_key);
 576     t_length=(*keyinfo->pack_key)(keyinfo,nod_flag,buff+p_length,
 577                                   prev_key, prev_key,
 578                                   anc_key, &s_temp);
 579     length=buff_length-p_length;
 580     endpos=buff+length+leaf_length+t_length;
 581     /* buff will always be larger than before !*/
 582     bmove_upp((uchar*) endpos, (uchar*) buff+buff_length,length);
 583     memcpy((uchar*) buff, (uchar*) leaf_buff,(size_t) leaf_length);
 584     (*keyinfo->store_key)(keyinfo,buff+leaf_length,&s_temp);
 585     buff_length=(uint) (endpos-buff);
 586     mi_putint(buff,buff_length,nod_flag);
 587
 588     /* remove key from anc_buff */
 589
 590     if (!(s_length=remove_key(keyinfo,key_reflength,keypos,anc_key,
 591                               anc_buff+anc_length,(my_off_t *) 0)))
 592       goto err;
 593
 594     anc_length-=s_length;
 595     mi_putint(anc_buff,anc_length,key_reflength);
 596
 597     if (buff_length <= keyinfo->block_length)
 598     {                                           /* Keys in one page */
 599       memcpy((uchar*) leaf_buff,(uchar*) buff,(size_t) buff_length);
 600       if (_mi_dispose(info,keyinfo,next_page,DFLT_INIT_HITS))
 601        goto err;
 602     }
 603     else
 604     {                                           /* Page is full */
 605       endpos=anc_buff+anc_length;
 606       DBUG_PRINT("test",("anc_buff: 0x%lx  endpos: 0x%lx",
 607                          (long) anc_buff, (long) endpos));
 608       if (keypos != anc_buff+2+key_reflength &&
 609           !_mi_get_last_key(info,keyinfo,anc_buff,anc_key,keypos,&length))
 610         goto err;
 611       if (!(half_pos=_mi_find_half_pos(nod_flag, keyinfo, buff, leaf_key,
 612                                        &key_length, &after_key)))
 613         goto err;
 614       length=(uint) (half_pos-buff);
 615       memcpy((uchar*) leaf_buff,(uchar*) buff,(size_t) length);
 616       mi_putint(leaf_buff,length,nod_flag);
 617
 618       /* Correct new keypointer to leaf_page */
 619       half_pos=after_key;
 620       _mi_kpointer(info,leaf_key+key_length,next_page);
 621       /* Save key in anc_buff */
 622       prev_key=(keypos == anc_buff+2+key_reflength ? (uchar*) 0 : anc_key),
 623       t_length=(*keyinfo->pack_key)(keyinfo,key_reflength,
 624                                     (keypos == endpos ? (uchar*) 0 :
 625                                      keypos),
 626                                     prev_key, prev_key,
 627                                     leaf_key, &s_temp);
 628       if (t_length >= 0)
 629         bmove_upp((uchar*) endpos+t_length,(uchar*) endpos,
 630                   (uint) (endpos-keypos));
 631       else
 632         bmove(keypos,keypos-t_length,(uint) (endpos-keypos)+t_length);
 633       (*keyinfo->store_key)(keyinfo,keypos,&s_temp);
 634       mi_putint(anc_buff,(anc_length+=t_length),key_reflength);
 635
 636         /* Store key first in new page */
 637       if (nod_flag)
 638         bmove((uchar*) buff+2,(uchar*) half_pos-nod_flag,(size_t) nod_flag);
 639       if (!(*keyinfo->get_key)(keyinfo,nod_flag,&half_pos,leaf_key))
 640         goto err;
 641       t_length=(int) (*keyinfo->pack_key)(keyinfo, nod_flag, (uchar*) 0,
 642                                           (uchar*) 0, (uchar *) 0,
 643                                           leaf_key, &s_temp);
 644       /* t_length will always be > 0 for a new page !*/
 645       length=(uint) ((buff+mi_getint(buff))-half_pos);
 646       bmove((uchar*) buff+p_length+t_length,(uchar*) half_pos,(size_t) length);
 647       (*keyinfo->store_key)(keyinfo,buff+p_length,&s_temp);
 648       mi_putint(buff,length+t_length+p_length,nod_flag);
 649
 650       if (_mi_write_keypage(info,keyinfo,next_page,DFLT_INIT_HITS,buff))
 651         goto err;
 652     }
 653     if (_mi_write_keypage(info,keyinfo,leaf_page,DFLT_INIT_HITS,leaf_buff))
 654       goto err;
 655     DBUG_RETURN(anc_length <= ((info->quick_mode ? MI_MIN_BLOCK_LENGTH :
 656                                 (uint) keyinfo->underflow_block_length)));
 657   }
 658
 659   DBUG_PRINT("test",("use left page"));
 660
 661   keypos=_mi_get_last_key(info,keyinfo,anc_buff,anc_key,keypos,&length);
 662   if (!keypos)
 663     goto err;
 664   next_page= _mi_kpos(key_reflength,keypos);
 665   if (!_mi_fetch_keypage(info,keyinfo,next_page,DFLT_INIT_HITS,buff,0))
 666       goto err;
 667   buff_length=mi_getint(buff);
 668   endpos=buff+buff_length;
 669   DBUG_DUMP("prev",(uchar*) buff,buff_length);
 670
 671   /* find keys to make a big key-page */
 672   bmove((uchar*) next_keypos - key_reflength,(uchar*) leaf_buff+2,
 673         key_reflength);
 674   next_keypos=keypos;
 675   if (!(*keyinfo->get_key)(keyinfo,key_reflength,&next_keypos,
 676                            anc_key))
 677     goto err;
 678   if (!_mi_get_last_key(info,keyinfo,buff,leaf_key,endpos,&length))
 679     goto err;
 680
 681   /* merge pages and put parting key from anc_buff between */
 682   prev_key=(leaf_length == p_length ? (uchar*) 0 : leaf_key);
 683   t_length=(*keyinfo->pack_key)(keyinfo,nod_flag,
 684                                 (leaf_length == p_length ?
 685                                  (uchar*) 0 : leaf_buff+p_length),
 686                                 prev_key, prev_key,
 687                                 anc_key, &s_temp);
 688   if (t_length >= 0)
 689     bmove((uchar*) endpos+t_length,(uchar*) leaf_buff+p_length,
 690             (size_t) (leaf_length-p_length));
 691   else                                          /* We gained space */
 692     bmove((uchar*) endpos,(uchar*) leaf_buff+((int) p_length-t_length),
 693           (size_t) (leaf_length-p_length+t_length));
 694
 695   (*keyinfo->store_key)(keyinfo,endpos,&s_temp);
 696   buff_length=buff_length+leaf_length-p_length+t_length;
 697   mi_putint(buff,buff_length,nod_flag);
 698
 699   /* remove key from anc_buff */
 700   if (!(s_length= remove_key(keyinfo,key_reflength,keypos,anc_key,
 701                              anc_buff+anc_length,(my_off_t *) 0)))
 702     goto err;
 703
 704   anc_length-=s_length;
 705   mi_putint(anc_buff,anc_length,key_reflength);
 706
 707   if (buff_length <= keyinfo->block_length)
 708   {                                             /* Keys in one page */
 709     if (_mi_dispose(info,keyinfo,leaf_page,DFLT_INIT_HITS))
 710       goto err;
 711   }
 712   else
 713   {                                             /* Page is full */
 714     if (keypos == anc_buff+2+key_reflength)
 715       anc_pos=0;                                /* First key */
 716     else if (!_mi_get_last_key(info,keyinfo,anc_buff,anc_pos=anc_key,keypos,
 717                                &length))
 718       goto err;
 719     endpos=_mi_find_half_pos(nod_flag,keyinfo,buff,leaf_key,
 720                              &key_length, &half_pos);
 721     if (!endpos)
 722       goto err;
 723     _mi_kpointer(info,leaf_key+key_length,leaf_page);
 724     /* Save key in anc_buff */
 725     DBUG_DUMP("anc_buff",(uchar*) anc_buff,anc_length);
 726     DBUG_DUMP("key_to_anc",(uchar*) leaf_key,key_length);
 727
 728     temp_pos=anc_buff+anc_length;
 729     t_length=(*keyinfo->pack_key)(keyinfo,key_reflength,
 730                                   keypos == temp_pos ? (uchar*) 0
 731                                   : keypos,
 732                                   anc_pos, anc_pos,
 733                                   leaf_key,&s_temp);
 734     if (t_length > 0)
 735       bmove_upp((uchar*) temp_pos+t_length,(uchar*) temp_pos,
 736                 (uint) (temp_pos-keypos));
 737     else
 738       bmove(keypos,keypos-t_length,(uint) (temp_pos-keypos)+t_length);
 739     (*keyinfo->store_key)(keyinfo,keypos,&s_temp);
 740     mi_putint(anc_buff,(anc_length+=t_length),key_reflength);
 741
 742     /* Store first key on new page */
 743     if (nod_flag)
 744       bmove((uchar*) leaf_buff+2,(uchar*) half_pos-nod_flag,(size_t) nod_flag);
 745     if (!(length=(*keyinfo->get_key)(keyinfo,nod_flag,&half_pos,leaf_key)))
 746       goto err;
 747     DBUG_DUMP("key_to_leaf",(uchar*) leaf_key,length);
 748     t_length=(*keyinfo->pack_key)(keyinfo,nod_flag, (uchar*) 0,
 749                                   (uchar*) 0, (uchar*) 0, leaf_key, &s_temp);
 750     length=(uint) ((buff+buff_length)-half_pos);
 751     DBUG_PRINT("info",("t_length: %d  length: %d",t_length,(int) length));
 752     bmove((uchar*) leaf_buff+p_length+t_length,(uchar*) half_pos,
 753           (size_t) length);
 754     (*keyinfo->store_key)(keyinfo,leaf_buff+p_length,&s_temp);
 755     mi_putint(leaf_buff,length+t_length+p_length,nod_flag);
 756     if (_mi_write_keypage(info,keyinfo,leaf_page,DFLT_INIT_HITS,leaf_buff))
 757       goto err;
 758     mi_putint(buff,endpos-buff,nod_flag);
 759   }
 760   if (_mi_write_keypage(info,keyinfo,next_page,DFLT_INIT_HITS,buff))
 761     goto err;
 762   DBUG_RETURN(anc_length <= (uint) keyinfo->block_length/2);
 763
 764 err:
 765   DBUG_RETURN(-1);
 766 } /* underflow */
 767
 768
 769         /*
 770           remove a key from packed buffert
 771           The current code doesn't handle the case that the next key may be
 772           packed better against the previous key if there is a case difference
 773           returns how many chars was removed or 0 on error
 774         */
 775
 776 static uint remove_key(MI_KEYDEF *keyinfo, uint nod_flag,
 777                        uchar *keypos,   /* Where key starts */
 778                        uchar *lastkey,  /* key to be removed */
 779                        uchar *page_end, /* End of page */
 780                        my_off_t *next_block)    /* ptr to next block */
 781 {
 782   int s_length;
 783   uchar *start;
 784   DBUG_ENTER("remove_key");
 785   DBUG_PRINT("enter",("keypos: 0x%lx  page_end: 0x%lx",(long) keypos, (long) page_end));
 786
 787   start=keypos;
 788   if (!(keyinfo->flag &
 789         (HA_PACK_KEY | HA_SPACE_PACK_USED | HA_VAR_LENGTH_KEY |
 790          HA_BINARY_PACK_KEY)))
 791   {
 792     s_length=(int) (keyinfo->keylength+nod_flag);
 793     if (next_block && nod_flag)
 794       *next_block= _mi_kpos(nod_flag,keypos+s_length);
 795   }
 796   else
 797   {                                      /* Let keypos point at next key */
 798     /* Calculate length of key */
 799     if (!(*keyinfo->get_key)(keyinfo,nod_flag,&keypos,lastkey))
 800       DBUG_RETURN(0);                           /* Error */
 801
 802     if (next_block && nod_flag)
 803       *next_block= _mi_kpos(nod_flag,keypos);
 804     s_length=(int) (keypos-start);
 805     if (keypos != page_end)
 806     {
 807       if (keyinfo->flag & HA_BINARY_PACK_KEY)
 808       {
 809         uchar *old_key=start;
 810         uint next_length,prev_length,prev_pack_length;
 811         get_key_length(next_length,keypos);
 812         get_key_pack_length(prev_length,prev_pack_length,old_key);
 813         if (next_length > prev_length)
 814         {
 815           /* We have to copy data from the current key to the next key */
 816           bmove_upp(keypos, (lastkey+next_length),
 817                     (next_length-prev_length));
 818           keypos-=(next_length-prev_length)+prev_pack_length;
 819           store_key_length(keypos,prev_length);
 820           s_length=(int) (keypos-start);
 821         }
 822       }
 823       else
 824       {
 825         /* Check if a variable length first key part */
 826         if ((keyinfo->seg->flag & HA_PACK_KEY) && *keypos & 128)
 827         {
 828           /* Next key is packed against the current one */
 829           uint next_length,prev_length,prev_pack_length,lastkey_length,
 830             rest_length;
 831           if (keyinfo->seg[0].length >= 127)
 832           {
 833             if (!(prev_length=mi_uint2korr(start) & 32767))
 834               goto end;
 835             next_length=mi_uint2korr(keypos) & 32767;
 836             keypos+=2;
 837             prev_pack_length=2;
 838           }
 839           else
 840           {
 841             if (!(prev_length= *start & 127))
 842               goto end;                         /* Same key as previous*/
 843             next_length= *keypos & 127;
 844             keypos++;
 845             prev_pack_length=1;
 846           }
 847           if (!(*start & 128))
 848             prev_length=0;                      /* prev key not packed */
 849           if (keyinfo->seg[0].flag & HA_NULL_PART)
 850             lastkey++;                          /* Skip null marker */
 851           get_key_length(lastkey_length,lastkey);
 852           if (!next_length)                     /* Same key after */
 853           {
 854             next_length=lastkey_length;
 855             rest_length=0;
 856           }
 857           else
 858             get_key_length(rest_length,keypos);
 859
 860           if (next_length >= prev_length)
 861           {             /* Key after is based on deleted key */
 862             uint pack_length,tmp;
 863             bmove_upp(keypos, (lastkey+next_length),
 864                       tmp=(next_length-prev_length));
 865             rest_length+=tmp;
 866             pack_length= prev_length ? get_pack_length(rest_length): 0;
 867             keypos-=tmp+pack_length+prev_pack_length;
 868             s_length=(int) (keypos-start);
 869             if (prev_length)                    /* Pack against prev key */
 870             {
 871               *keypos++= start[0];
 872               if (prev_pack_length == 2)
 873                 *keypos++= start[1];
 874               store_key_length(keypos,rest_length);
 875             }
 876             else
 877             {
 878               /* Next key is not packed anymore */
 879               if (keyinfo->seg[0].flag & HA_NULL_PART)
 880               {
 881                 rest_length++;                  /* Mark not null */
 882               }
 883               if (prev_pack_length == 2)
 884               {
 885                 mi_int2store(keypos,rest_length);
 886               }
 887               else
 888                 *keypos= rest_length;
 889             }
 890           }
 891         }
 892       }
 893     }
 894   }
 895   end:
 896   bmove((uchar*) start,(uchar*) start+s_length,
 897         (uint) (page_end-start-s_length));
 898   DBUG_RETURN((uint) s_length);
 899 } /* remove_key */