Drizzled Public API Documentation

mi_delete.cc
00001 /* Copyright (C) 2000-2006 MySQL AB
00002 
00003    This program is free software; you can redistribute it and/or modify
00004    it under the terms of the GNU General Public License as published by
00005    the Free Software Foundation; version 2 of the License.
00006 
00007    This program is distributed in the hope that it will be useful,
00008    but WITHOUT ANY WARRANTY; without even the implied warranty of
00009    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00010    GNU General Public License for more details.
00011 
00012    You should have received a copy of the GNU General Public License
00013    along with this program; if not, write to the Free Software
00014    Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA */
00015 
00016 /* Remove a row from a MyISAM table */
00017 
00018 #include "myisam_priv.h"
00019 #include <drizzled/internal/m_string.h>
00020 #include <drizzled/util/test.h>
00021 
00022 using namespace drizzled;
00023 
00024 static int d_search(MI_INFO *info,MI_KEYDEF *keyinfo,uint32_t comp_flag,
00025                     unsigned char *key,uint32_t key_length,internal::my_off_t page,unsigned char *anc_buff);
00026 static int del(MI_INFO *info,MI_KEYDEF *keyinfo,unsigned char *key,unsigned char *anc_buff,
00027          internal::my_off_t leaf_page,unsigned char *leaf_buff,unsigned char *keypos,
00028          internal::my_off_t next_block,unsigned char *ret_key);
00029 static int underflow(MI_INFO *info,MI_KEYDEF *keyinfo,unsigned char *anc_buff,
00030          internal::my_off_t leaf_page,unsigned char *leaf_buff,unsigned char *keypos);
00031 static uint32_t remove_key(MI_KEYDEF *keyinfo,uint32_t nod_flag,unsigned char *keypos,
00032            unsigned char *lastkey,unsigned char *page_end,
00033            internal::my_off_t *next_block);
00034 static int _mi_ck_real_delete(register MI_INFO *info,MI_KEYDEF *keyinfo,
00035             unsigned char *key, uint32_t key_length, internal::my_off_t *root);
00036 
00037 
00038 int mi_delete(MI_INFO *info,const unsigned char *record)
00039 {
00040   uint32_t i;
00041   unsigned char *old_key;
00042   int save_errno;
00043   char lastpos[8];
00044 
00045   MYISAM_SHARE *share=info->s;
00046 
00047   /* Test if record is in datafile */
00048   if (!(info->update & HA_STATE_AKTIV))
00049   {
00050     return(errno=HA_ERR_KEY_NOT_FOUND); /* No database read */
00051   }
00052   if (share->options & HA_OPTION_READ_ONLY_DATA)
00053   {
00054     return(errno=EACCES);
00055   }
00056   if (_mi_readinfo(info,F_WRLCK,1))
00057     return(errno);
00058   if (info->s->calc_checksum)
00059     info->checksum=(*info->s->calc_checksum)(info,record);
00060   if ((*share->compare_record)(info,record))
00061     goto err;       /* Error on read-check */
00062 
00063   if (_mi_mark_file_changed(info))
00064     goto err;
00065 
00066   /* Remove all keys from the .ISAM file */
00067 
00068   old_key=info->lastkey2;
00069   for (i=0 ; i < share->base.keys ; i++ )
00070   {
00071     if (mi_is_key_active(info->s->state.key_map, i))
00072     {
00073       info->s->keyinfo[i].version++;
00074       {
00075         if (info->s->keyinfo[i].ck_delete(info,i,old_key,
00076                 _mi_make_key(info,i,old_key,record,info->lastpos)))
00077           goto err;
00078       }
00079       /* The above changed info->lastkey2. Inform mi_rnext_same(). */
00080       info->update&= ~HA_STATE_RNEXT_SAME;
00081     }
00082   }
00083 
00084   if ((*share->delete_record)(info))
00085     goto err;       /* Remove record from database */
00086   info->state->checksum-=info->checksum;
00087 
00088   info->update= HA_STATE_CHANGED+HA_STATE_DELETED+HA_STATE_ROW_CHANGED;
00089   info->state->records--;
00090 
00091   mi_sizestore(lastpos,info->lastpos);
00092   _mi_writeinfo(info,WRITEINFO_UPDATE_KEYFILE);
00093   return(0);
00094 
00095 err:
00096   save_errno=errno;
00097   mi_sizestore(lastpos,info->lastpos);
00098   if (save_errno != HA_ERR_RECORD_CHANGED)
00099   {
00100     mi_print_error(info->s, HA_ERR_CRASHED);
00101     mi_mark_crashed(info);    /* mark table crashed */
00102   }
00103   _mi_writeinfo(info,WRITEINFO_UPDATE_KEYFILE);
00104   info->update|=HA_STATE_WRITTEN; /* Buffer changed */
00105   errno=save_errno;
00106   if (save_errno == HA_ERR_KEY_NOT_FOUND)
00107   {
00108     mi_print_error(info->s, HA_ERR_CRASHED);
00109     errno=HA_ERR_CRASHED;
00110   }
00111 
00112   return(errno);
00113 } /* mi_delete */
00114 
00115 
00116   /* Remove a key from the btree index */
00117 
00118 int _mi_ck_delete(register MI_INFO *info, uint32_t keynr, unsigned char *key,
00119       uint32_t key_length)
00120 {
00121   return _mi_ck_real_delete(info, info->s->keyinfo+keynr, key, key_length,
00122                             &info->s->state.key_root[keynr]);
00123 } /* _mi_ck_delete */
00124 
00125 
00126 static int _mi_ck_real_delete(register MI_INFO *info, MI_KEYDEF *keyinfo,
00127             unsigned char *key, uint32_t key_length, internal::my_off_t *root)
00128 {
00129   int error;
00130   uint32_t nod_flag;
00131   internal::my_off_t old_root;
00132   unsigned char *root_buff;
00133 
00134   if ((old_root=*root) == HA_OFFSET_ERROR)
00135   {
00136     mi_print_error(info->s, HA_ERR_CRASHED);
00137     return(errno=HA_ERR_CRASHED);
00138   }
00139   if (!(root_buff= (unsigned char*) malloc(keyinfo->block_length+
00140               MI_MAX_KEY_BUFF*2)))
00141   {
00142     return(errno=ENOMEM);
00143   }
00144   if (!_mi_fetch_keypage(info,keyinfo,old_root,DFLT_INIT_HITS,root_buff,0))
00145   {
00146     error= -1;
00147     goto err;
00148   }
00149   if ((error=d_search(info,keyinfo, (SEARCH_SAME), key,key_length,old_root,root_buff)) > 0)
00150   {
00151     if (error == 2)
00152     {
00153       error=_mi_enlarge_root(info,keyinfo,key,root);
00154     }
00155     else /* error == 1 */
00156     {
00157       if (mi_getint(root_buff) <= (nod_flag=mi_test_if_nod(root_buff))+3)
00158       {
00159   error=0;
00160   if (nod_flag)
00161     *root=_mi_kpos(nod_flag,root_buff+2+nod_flag);
00162   else
00163     *root=HA_OFFSET_ERROR;
00164   if (_mi_dispose(info,keyinfo,old_root,DFLT_INIT_HITS))
00165     error= -1;
00166       }
00167       else
00168   error=_mi_write_keypage(info,keyinfo,old_root,
00169                                 DFLT_INIT_HITS,root_buff);
00170     }
00171   }
00172 err:
00173   free(root_buff);
00174   return(error);
00175 } /* _mi_ck_real_delete */
00176 
00177 
00178   /*
00179   ** Remove key below key root
00180   ** Return values:
00181   ** 1 if there are less buffers;  In this case anc_buff is not saved
00182   ** 2 if there are more buffers
00183   ** -1 on errors
00184   */
00185 
00186 static int d_search(register MI_INFO *info, register MI_KEYDEF *keyinfo,
00187                     uint32_t comp_flag, unsigned char *key, uint32_t key_length,
00188                     internal::my_off_t page, unsigned char *anc_buff)
00189 {
00190   int flag,ret_value,save_flag;
00191   uint32_t length,nod_flag,search_key_length;
00192   bool last_key;
00193   unsigned char *leaf_buff,*keypos;
00194   internal::my_off_t leaf_page= 0, next_block;
00195   unsigned char lastkey[MI_MAX_KEY_BUFF];
00196 
00197   search_key_length= (comp_flag & SEARCH_FIND) ? key_length : USE_WHOLE_KEY;
00198   flag=(*keyinfo->bin_search)(info,keyinfo,anc_buff,key, search_key_length,
00199                               comp_flag, &keypos, lastkey, &last_key);
00200   if (flag == MI_FOUND_WRONG_KEY)
00201   {
00202     return(-1);
00203   }
00204   nod_flag=mi_test_if_nod(anc_buff);
00205 
00206   leaf_buff= 0;
00207   if (nod_flag)
00208   {
00209     leaf_page=_mi_kpos(nod_flag,keypos);
00210     if (!(leaf_buff= (unsigned char*) malloc(keyinfo->block_length+
00211           MI_MAX_KEY_BUFF*2)))
00212     {
00213       errno=ENOMEM;
00214       return(-1);
00215     }
00216     if (!_mi_fetch_keypage(info,keyinfo,leaf_page,DFLT_INIT_HITS,leaf_buff,0))
00217       goto err;
00218   }
00219 
00220   if (flag != 0)
00221   {
00222     if (!nod_flag)
00223     {
00224       mi_print_error(info->s, HA_ERR_CRASHED);
00225       errno=HA_ERR_CRASHED;   /* This should newer happend */
00226       goto err;
00227     }
00228     save_flag=0;
00229     ret_value=d_search(info,keyinfo,comp_flag,key,key_length,
00230                        leaf_page,leaf_buff);
00231   }
00232   else
00233   {           /* Found key */
00234     uint32_t tmp;
00235     length=mi_getint(anc_buff);
00236     if (!(tmp= remove_key(keyinfo,nod_flag,keypos,lastkey,anc_buff+length,
00237                           &next_block)))
00238       goto err;
00239 
00240     length-= tmp;
00241 
00242     mi_putint(anc_buff,length,nod_flag);
00243     if (!nod_flag)
00244     {           /* On leaf page */
00245       if (_mi_write_keypage(info,keyinfo,page,DFLT_INIT_HITS,anc_buff))
00246       {
00247   return(-1);
00248       }
00249       /* Page will be update later if we return 1 */
00250       return(test(length <= (info->quick_mode ? MI_MIN_KEYBLOCK_LENGTH :
00251           (uint) keyinfo->underflow_block_length)));
00252     }
00253     save_flag=1;
00254     ret_value=del(info,keyinfo,key,anc_buff,leaf_page,leaf_buff,keypos,
00255       next_block,lastkey);
00256   }
00257   if (ret_value >0)
00258   {
00259     save_flag=1;
00260     if (ret_value == 1)
00261       ret_value= underflow(info,keyinfo,anc_buff,leaf_page,leaf_buff,keypos);
00262     else
00263     {       /* This happens only with packed keys */
00264       if (!_mi_get_last_key(info,keyinfo,anc_buff,lastkey,keypos,&length))
00265       {
00266   goto err;
00267       }
00268       ret_value=_mi_insert(info,keyinfo,key,anc_buff,keypos,lastkey,
00269          (unsigned char*) 0,(unsigned char*) 0,(internal::my_off_t) 0,(bool) 0);
00270     }
00271   }
00272   if (ret_value == 0 && mi_getint(anc_buff) > keyinfo->block_length)
00273   {
00274     save_flag=1;
00275     ret_value=_mi_split_page(info,keyinfo,key,anc_buff,lastkey,0) | 2;
00276   }
00277   if (save_flag && ret_value != 1)
00278     ret_value|=_mi_write_keypage(info,keyinfo,page,DFLT_INIT_HITS,anc_buff);
00279   free(leaf_buff);
00280   return(ret_value);
00281 
00282 err:
00283   free(leaf_buff);
00284   return (-1);
00285 } /* d_search */
00286 
00287 
00288   /* Remove a key that has a page-reference */
00289 
00290 static int del(register MI_INFO *info, register MI_KEYDEF *keyinfo, unsigned char *key,
00291          unsigned char *anc_buff, internal::my_off_t leaf_page, unsigned char *leaf_buff,
00292          unsigned char *keypos,   /* Pos to where deleted key was */
00293          internal::my_off_t next_block,
00294          unsigned char *ret_key)    /* key before keypos in anc_buff */
00295 {
00296   int ret_value,length;
00297   uint32_t a_length,nod_flag,tmp;
00298   internal::my_off_t next_page;
00299   unsigned char keybuff[MI_MAX_KEY_BUFF],*endpos,*next_buff,*key_start, *prev_key;
00300   MYISAM_SHARE *share=info->s;
00301   MI_KEY_PARAM s_temp;
00302 
00303   endpos=leaf_buff+mi_getint(leaf_buff);
00304   if (!(key_start=_mi_get_last_key(info,keyinfo,leaf_buff,keybuff,endpos,
00305            &tmp)))
00306     return(-1);
00307 
00308   if ((nod_flag=mi_test_if_nod(leaf_buff)))
00309   {
00310     next_page= _mi_kpos(nod_flag,endpos);
00311     if (!(next_buff= (unsigned char*) malloc(keyinfo->block_length+
00312           MI_MAX_KEY_BUFF*2)))
00313       return(-1);
00314     if (!_mi_fetch_keypage(info,keyinfo,next_page,DFLT_INIT_HITS,next_buff,0))
00315       ret_value= -1;
00316     else
00317     {
00318       if ((ret_value=del(info,keyinfo,key,anc_buff,next_page,next_buff,
00319        keypos,next_block,ret_key)) >0)
00320       {
00321   endpos=leaf_buff+mi_getint(leaf_buff);
00322   if (ret_value == 1)
00323   {
00324     ret_value=underflow(info,keyinfo,leaf_buff,next_page,
00325             next_buff,endpos);
00326     if (ret_value == 0 && mi_getint(leaf_buff) > keyinfo->block_length)
00327     {
00328       ret_value=_mi_split_page(info,keyinfo,key,leaf_buff,ret_key,0) | 2;
00329     }
00330   }
00331   else
00332   {
00333     if (!_mi_get_last_key(info,keyinfo,leaf_buff,keybuff,endpos,
00334         &tmp))
00335       goto err;
00336     ret_value=_mi_insert(info,keyinfo,key,leaf_buff,endpos,keybuff,
00337              (unsigned char*) 0,(unsigned char*) 0,(internal::my_off_t) 0,0);
00338   }
00339       }
00340       if (_mi_write_keypage(info,keyinfo,leaf_page,DFLT_INIT_HITS,leaf_buff))
00341   goto err;
00342     }
00343     free(next_buff);
00344     return(ret_value);
00345   }
00346 
00347   /* Remove last key from leaf page */
00348 
00349   mi_putint(leaf_buff,key_start-leaf_buff,nod_flag);
00350   if (_mi_write_keypage(info,keyinfo,leaf_page,DFLT_INIT_HITS,leaf_buff))
00351     goto err;
00352 
00353   /* Place last key in ancestor page on deleted key position */
00354 
00355   a_length=mi_getint(anc_buff);
00356   endpos=anc_buff+a_length;
00357   if (keypos != anc_buff+2+share->base.key_reflength &&
00358       !_mi_get_last_key(info,keyinfo,anc_buff,ret_key,keypos,&tmp))
00359     goto err;
00360   prev_key=(keypos == anc_buff+2+share->base.key_reflength ?
00361       0 : ret_key);
00362   length=(*keyinfo->pack_key)(keyinfo,share->base.key_reflength,
00363             keypos == endpos ? (unsigned char*) 0 : keypos,
00364             prev_key, prev_key,
00365             keybuff,&s_temp);
00366   if (length > 0)
00367     internal::bmove_upp((unsigned char*) endpos+length,(unsigned char*) endpos,(uint) (endpos-keypos));
00368   else
00369     memmove(keypos,keypos-length, (int) (endpos-keypos)+length);
00370   (*keyinfo->store_key)(keyinfo,keypos,&s_temp);
00371   /* Save pointer to next leaf */
00372   if (!(*keyinfo->get_key)(keyinfo,share->base.key_reflength,&keypos,ret_key))
00373     goto err;
00374   _mi_kpointer(info,keypos - share->base.key_reflength,next_block);
00375   mi_putint(anc_buff,a_length+length,share->base.key_reflength);
00376 
00377   return( mi_getint(leaf_buff) <=
00378          (info->quick_mode ? MI_MIN_KEYBLOCK_LENGTH :
00379     (uint) keyinfo->underflow_block_length));
00380 err:
00381   return(-1);
00382 } /* del */
00383 
00384 
00385   /* Balances adjacent pages if underflow occours */
00386 
00387 static int underflow(register MI_INFO *info, register MI_KEYDEF *keyinfo,
00388          unsigned char *anc_buff,
00389          internal::my_off_t leaf_page,/* Ancestor page and underflow page */
00390          unsigned char *leaf_buff,
00391          unsigned char *keypos) /* Position to pos after key */
00392 {
00393   int t_length;
00394   uint32_t length,anc_length,buff_length,leaf_length,p_length,s_length,nod_flag,
00395        key_reflength,key_length;
00396   internal::my_off_t next_page;
00397   unsigned char anc_key[MI_MAX_KEY_BUFF],leaf_key[MI_MAX_KEY_BUFF],
00398         *buff,*endpos,*next_keypos,*anc_pos,*half_pos,*temp_pos,*prev_key,
00399         *after_key;
00400   MI_KEY_PARAM s_temp;
00401   MYISAM_SHARE *share=info->s;
00402 
00403   buff=info->buff;
00404   info->buff_used=1;
00405   next_keypos=keypos;
00406   nod_flag=mi_test_if_nod(leaf_buff);
00407   p_length=nod_flag+2;
00408   anc_length=mi_getint(anc_buff);
00409   leaf_length=mi_getint(leaf_buff);
00410   key_reflength=share->base.key_reflength;
00411   if (info->s->keyinfo+info->lastinx == keyinfo)
00412     info->page_changed=1;
00413 
00414   if ((keypos < anc_buff+anc_length && (info->state->records & 1)) ||
00415       keypos == anc_buff+2+key_reflength)
00416   {         /* Use page right of anc-page */
00417     if (keyinfo->flag & HA_BINARY_PACK_KEY)
00418     {
00419       if (!(next_keypos=_mi_get_key(info, keyinfo,
00420             anc_buff, buff, keypos, &length)))
00421   goto err;
00422     }
00423     else
00424     {
00425       /* Got to end of found key */
00426       buff[0]=buff[1]=0;  /* Avoid length error check if packed key */
00427       if (!(*keyinfo->get_key)(keyinfo,key_reflength,&next_keypos,
00428              buff))
00429       goto err;
00430     }
00431     next_page= _mi_kpos(key_reflength,next_keypos);
00432     if (!_mi_fetch_keypage(info,keyinfo,next_page,DFLT_INIT_HITS,buff,0))
00433       goto err;
00434     buff_length=mi_getint(buff);
00435 
00436     /* find keys to make a big key-page */
00437     memmove(next_keypos - key_reflength, buff + 2, key_reflength);
00438     if (!_mi_get_last_key(info,keyinfo,anc_buff,anc_key,next_keypos,&length)
00439   || !_mi_get_last_key(info,keyinfo,leaf_buff,leaf_key,
00440            leaf_buff+leaf_length,&length))
00441       goto err;
00442 
00443     /* merge pages and put parting key from anc_buff between */
00444     prev_key=(leaf_length == p_length ? (unsigned char*) 0 : leaf_key);
00445     t_length=(*keyinfo->pack_key)(keyinfo,nod_flag,buff+p_length,
00446           prev_key, prev_key,
00447           anc_key, &s_temp);
00448     length=buff_length-p_length;
00449     endpos=buff+length+leaf_length+t_length;
00450     /* buff will always be larger than before !*/
00451     internal::bmove_upp((unsigned char*) endpos, (unsigned char*) buff+buff_length,length);
00452     memcpy(buff, leaf_buff, leaf_length);
00453     (*keyinfo->store_key)(keyinfo,buff+leaf_length,&s_temp);
00454     buff_length=(uint) (endpos-buff);
00455     mi_putint(buff,buff_length,nod_flag);
00456 
00457     /* remove key from anc_buff */
00458 
00459     if (!(s_length=remove_key(keyinfo,key_reflength,keypos,anc_key,
00460                               anc_buff+anc_length,(internal::my_off_t *) 0)))
00461       goto err;
00462 
00463     anc_length-=s_length;
00464     mi_putint(anc_buff,anc_length,key_reflength);
00465 
00466     if (buff_length <= keyinfo->block_length)
00467     {           /* Keys in one page */
00468       memcpy(leaf_buff, buff, buff_length);
00469       if (_mi_dispose(info,keyinfo,next_page,DFLT_INIT_HITS))
00470        goto err;
00471     }
00472     else
00473     {           /* Page is full */
00474       endpos=anc_buff+anc_length;
00475       if (keypos != anc_buff+2+key_reflength &&
00476     !_mi_get_last_key(info,keyinfo,anc_buff,anc_key,keypos,&length))
00477   goto err;
00478       if (!(half_pos=_mi_find_half_pos(nod_flag, keyinfo, buff, leaf_key,
00479                &key_length, &after_key)))
00480   goto err;
00481       length=(uint) (half_pos-buff);
00482       memcpy(leaf_buff, buff, length);
00483       mi_putint(leaf_buff,length,nod_flag);
00484 
00485       /* Correct new keypointer to leaf_page */
00486       half_pos=after_key;
00487       _mi_kpointer(info,leaf_key+key_length,next_page);
00488       /* Save key in anc_buff */
00489       prev_key=(keypos == anc_buff+2+key_reflength ? (unsigned char*) 0 : anc_key),
00490       t_length=(*keyinfo->pack_key)(keyinfo,key_reflength,
00491             (keypos == endpos ? (unsigned char*) 0 :
00492              keypos),
00493             prev_key, prev_key,
00494             leaf_key, &s_temp);
00495       if (t_length >= 0)
00496   internal::bmove_upp((unsigned char*) endpos+t_length,(unsigned char*) endpos,
00497       (uint) (endpos-keypos));
00498       else
00499   memmove(keypos,keypos-t_length,(uint) (endpos-keypos)+t_length);
00500       (*keyinfo->store_key)(keyinfo,keypos,&s_temp);
00501       mi_putint(anc_buff,(anc_length+=t_length),key_reflength);
00502 
00503   /* Store key first in new page */
00504       if (nod_flag)
00505   memmove(buff + 2, half_pos - nod_flag, nod_flag);
00506       if (!(*keyinfo->get_key)(keyinfo,nod_flag,&half_pos,leaf_key))
00507   goto err;
00508       t_length=(int) (*keyinfo->pack_key)(keyinfo, nod_flag, (unsigned char*) 0,
00509             (unsigned char*) 0, (unsigned char *) 0,
00510             leaf_key, &s_temp);
00511       /* t_length will always be > 0 for a new page !*/
00512       length=(uint) ((buff+mi_getint(buff))-half_pos);
00513       memmove(buff + p_length + t_length, half_pos, length);
00514       (*keyinfo->store_key)(keyinfo,buff+p_length,&s_temp);
00515       mi_putint(buff,length+t_length+p_length,nod_flag);
00516 
00517       if (_mi_write_keypage(info,keyinfo,next_page,DFLT_INIT_HITS,buff))
00518   goto err;
00519     }
00520     if (_mi_write_keypage(info,keyinfo,leaf_page,DFLT_INIT_HITS,leaf_buff))
00521       goto err;
00522     return(anc_length <= ((info->quick_mode ? MI_MIN_BLOCK_LENGTH :
00523         (uint) keyinfo->underflow_block_length)));
00524   }
00525 
00526   keypos=_mi_get_last_key(info,keyinfo,anc_buff,anc_key,keypos,&length);
00527   if (!keypos)
00528     goto err;
00529   next_page= _mi_kpos(key_reflength,keypos);
00530   if (!_mi_fetch_keypage(info,keyinfo,next_page,DFLT_INIT_HITS,buff,0))
00531       goto err;
00532   buff_length=mi_getint(buff);
00533   endpos=buff+buff_length;
00534 
00535   /* find keys to make a big key-page */
00536   memmove(next_keypos - key_reflength, leaf_buff+2, key_reflength);
00537   next_keypos=keypos;
00538   if (!(*keyinfo->get_key)(keyinfo,key_reflength,&next_keypos,
00539          anc_key))
00540     goto err;
00541   if (!_mi_get_last_key(info,keyinfo,buff,leaf_key,endpos,&length))
00542     goto err;
00543 
00544   /* merge pages and put parting key from anc_buff between */
00545   prev_key=(leaf_length == p_length ? (unsigned char*) 0 : leaf_key);
00546   t_length=(*keyinfo->pack_key)(keyinfo,nod_flag,
00547         (leaf_length == p_length ?
00548                                  (unsigned char*) 0 : leaf_buff+p_length),
00549         prev_key, prev_key,
00550         anc_key, &s_temp);
00551   if (t_length >= 0)
00552     memmove(endpos+t_length,leaf_buff+p_length, leaf_length-p_length);
00553   else            /* We gained space */
00554     memmove(endpos, leaf_buff+((int) p_length-t_length),
00555             leaf_length - p_length + t_length);
00556 
00557   (*keyinfo->store_key)(keyinfo,endpos,&s_temp);
00558   buff_length=buff_length+leaf_length-p_length+t_length;
00559   mi_putint(buff,buff_length,nod_flag);
00560 
00561   /* remove key from anc_buff */
00562   if (!(s_length= remove_key(keyinfo,key_reflength,keypos,anc_key,
00563                              anc_buff+anc_length,(internal::my_off_t *) 0)))
00564     goto err;
00565 
00566   anc_length-=s_length;
00567   mi_putint(anc_buff,anc_length,key_reflength);
00568 
00569   if (buff_length <= keyinfo->block_length)
00570   {           /* Keys in one page */
00571     if (_mi_dispose(info,keyinfo,leaf_page,DFLT_INIT_HITS))
00572       goto err;
00573   }
00574   else
00575   {           /* Page is full */
00576     if (keypos == anc_buff+2+key_reflength)
00577       anc_pos=0;        /* First key */
00578     else if (!_mi_get_last_key(info,keyinfo,anc_buff,anc_pos=anc_key,keypos,
00579              &length))
00580       goto err;
00581     endpos=_mi_find_half_pos(nod_flag,keyinfo,buff,leaf_key,
00582            &key_length, &half_pos);
00583     if (!endpos)
00584       goto err;
00585     _mi_kpointer(info,leaf_key+key_length,leaf_page);
00586     /* Save key in anc_buff */
00587 
00588     temp_pos=anc_buff+anc_length;
00589     t_length=(*keyinfo->pack_key)(keyinfo,key_reflength,
00590           keypos == temp_pos ? (unsigned char*) 0
00591           : keypos,
00592           anc_pos, anc_pos,
00593           leaf_key,&s_temp);
00594     if (t_length > 0)
00595       internal::bmove_upp((unsigned char*) temp_pos+t_length,(unsigned char*) temp_pos,
00596     (uint) (temp_pos-keypos));
00597     else
00598       memmove(keypos,keypos-t_length,(uint) (temp_pos-keypos)+t_length);
00599     (*keyinfo->store_key)(keyinfo,keypos,&s_temp);
00600     mi_putint(anc_buff,(anc_length+=t_length),key_reflength);
00601 
00602     /* Store first key on new page */
00603     if (nod_flag)
00604       memmove(leaf_buff+2, half_pos - nod_flag, nod_flag);
00605     if (!(length=(*keyinfo->get_key)(keyinfo,nod_flag,&half_pos,leaf_key)))
00606       goto err;
00607     t_length=(*keyinfo->pack_key)(keyinfo,nod_flag, (unsigned char*) 0,
00608           (unsigned char*) 0, (unsigned char*) 0, leaf_key, &s_temp);
00609     length=(uint) ((buff+buff_length)-half_pos);
00610     memmove(leaf_buff + p_length + t_length, half_pos, length);
00611     (*keyinfo->store_key)(keyinfo,leaf_buff+p_length,&s_temp);
00612     mi_putint(leaf_buff,length+t_length+p_length,nod_flag);
00613     if (_mi_write_keypage(info,keyinfo,leaf_page,DFLT_INIT_HITS,leaf_buff))
00614       goto err;
00615     mi_putint(buff,endpos-buff,nod_flag);
00616   }
00617   if (_mi_write_keypage(info,keyinfo,next_page,DFLT_INIT_HITS,buff))
00618     goto err;
00619   return(anc_length <= (uint) keyinfo->block_length/2);
00620 
00621 err:
00622   return(-1);
00623 } /* underflow */
00624 
00625 
00626   /*
00627     remove a key from packed buffert
00628     The current code doesn't handle the case that the next key may be
00629     packed better against the previous key if there is a case difference
00630     returns how many chars was removed or 0 on error
00631   */
00632 
00633 static uint32_t remove_key(MI_KEYDEF *keyinfo, uint32_t nod_flag,
00634            unsigned char *keypos, /* Where key starts */
00635            unsigned char *lastkey,  /* key to be removed */
00636            unsigned char *page_end, /* End of page */
00637            internal::my_off_t *next_block)  /* ptr to next block */
00638 {
00639   int s_length;
00640   unsigned char *start;
00641 
00642   start=keypos;
00643   if (!(keyinfo->flag &
00644   (HA_PACK_KEY | HA_SPACE_PACK_USED | HA_VAR_LENGTH_KEY |
00645    HA_BINARY_PACK_KEY)))
00646   {
00647     s_length=(int) (keyinfo->keylength+nod_flag);
00648     if (next_block && nod_flag)
00649       *next_block= _mi_kpos(nod_flag,keypos+s_length);
00650   }
00651   else
00652   {          /* Let keypos point at next key */
00653     /* Calculate length of key */
00654     if (!(*keyinfo->get_key)(keyinfo,nod_flag,&keypos,lastkey))
00655       return(0);        /* Error */
00656 
00657     if (next_block && nod_flag)
00658       *next_block= _mi_kpos(nod_flag,keypos);
00659     s_length=(int) (keypos-start);
00660     if (keypos != page_end)
00661     {
00662       if (keyinfo->flag & HA_BINARY_PACK_KEY)
00663       {
00664   unsigned char *old_key=start;
00665   uint32_t next_length,prev_length,prev_pack_length;
00666   get_key_length(next_length,keypos);
00667   get_key_pack_length(prev_length,prev_pack_length,old_key);
00668   if (next_length > prev_length)
00669   {
00670     /* We have to copy data from the current key to the next key */
00671     internal::bmove_upp(keypos, (lastkey+next_length),
00672         (next_length-prev_length));
00673     keypos-=(next_length-prev_length)+prev_pack_length;
00674     store_key_length(keypos,prev_length);
00675     s_length=(int) (keypos-start);
00676   }
00677       }
00678       else
00679       {
00680   /* Check if a variable length first key part */
00681   if ((keyinfo->seg->flag & HA_PACK_KEY) && *keypos & 128)
00682   {
00683     /* Next key is packed against the current one */
00684     uint32_t next_length,prev_length,prev_pack_length,lastkey_length,
00685       rest_length;
00686     if (keyinfo->seg[0].length >= 127)
00687     {
00688       if (!(prev_length=mi_uint2korr(start) & 32767))
00689         goto end;
00690       next_length=mi_uint2korr(keypos) & 32767;
00691       keypos+=2;
00692       prev_pack_length=2;
00693     }
00694     else
00695     {
00696       if (!(prev_length= *start & 127))
00697         goto end;       /* Same key as previous*/
00698       next_length= *keypos & 127;
00699       keypos++;
00700       prev_pack_length=1;
00701     }
00702     if (!(*start & 128))
00703       prev_length=0;      /* prev key not packed */
00704     if (keyinfo->seg[0].flag & HA_NULL_PART)
00705       lastkey++;        /* Skip null marker */
00706     get_key_length(lastkey_length,lastkey);
00707     if (!next_length)     /* Same key after */
00708     {
00709       next_length=lastkey_length;
00710       rest_length=0;
00711     }
00712     else
00713       get_key_length(rest_length,keypos);
00714 
00715     if (next_length >= prev_length)
00716     {   /* Key after is based on deleted key */
00717       uint32_t pack_length,tmp;
00718       internal::bmove_upp(keypos, (lastkey+next_length),
00719                     tmp=(next_length-prev_length));
00720       rest_length+=tmp;
00721       pack_length= prev_length ? get_pack_length(rest_length): 0;
00722       keypos-=tmp+pack_length+prev_pack_length;
00723       s_length=(int) (keypos-start);
00724       if (prev_length)      /* Pack against prev key */
00725       {
00726         *keypos++= start[0];
00727         if (prev_pack_length == 2)
00728     *keypos++= start[1];
00729         store_key_length(keypos,rest_length);
00730       }
00731       else
00732       {
00733         /* Next key is not packed anymore */
00734         if (keyinfo->seg[0].flag & HA_NULL_PART)
00735         {
00736     rest_length++;      /* Mark not null */
00737         }
00738         if (prev_pack_length == 2)
00739         {
00740     mi_int2store(keypos,rest_length);
00741         }
00742         else
00743     *keypos= rest_length;
00744       }
00745     }
00746   }
00747       }
00748     }
00749   }
00750 end:
00751   assert(page_end-start >= s_length);
00752   memmove(start, start + s_length, page_end-start-s_length);
00753   return s_length;
00754 } /* remove_key */