Drizzled Public API Documentation

mi_delete.cc
1 /* Copyright (C) 2000-2006 MySQL AB
2 
3  This program is free software; you can redistribute it and/or modify
4  it under the terms of the GNU General Public License as published by
5  the Free Software Foundation; version 2 of the License.
6 
7  This program is distributed in the hope that it will be useful,
8  but WITHOUT ANY WARRANTY; without even the implied warranty of
9  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10  GNU General Public License for more details.
11 
12  You should have received a copy of the GNU General Public License
13  along with this program; if not, write to the Free Software
14  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
15 
16 /* Remove a row from a MyISAM table */
17 
18 #include "myisam_priv.h"
19 #include <drizzled/internal/m_string.h>
20 #include <drizzled/util/test.h>
21 
22 using namespace drizzled;
23 
24 static int d_search(MI_INFO *info,MI_KEYDEF *keyinfo,uint32_t comp_flag,
25  unsigned char *key,uint32_t key_length,internal::my_off_t page,unsigned char *anc_buff);
26 static int del(MI_INFO *info,MI_KEYDEF *keyinfo,unsigned char *key,unsigned char *anc_buff,
27  internal::my_off_t leaf_page,unsigned char *leaf_buff,unsigned char *keypos,
28  internal::my_off_t next_block,unsigned char *ret_key);
29 static int underflow(MI_INFO *info,MI_KEYDEF *keyinfo,unsigned char *anc_buff,
30  internal::my_off_t leaf_page,unsigned char *leaf_buff,unsigned char *keypos);
31 static uint32_t remove_key(MI_KEYDEF *keyinfo,uint32_t nod_flag,unsigned char *keypos,
32  unsigned char *lastkey,unsigned char *page_end,
33  internal::my_off_t *next_block);
34 static int _mi_ck_real_delete(register MI_INFO *info,MI_KEYDEF *keyinfo,
35  unsigned char *key, uint32_t key_length, internal::my_off_t *root);
36 
37 
38 int mi_delete(MI_INFO *info,const unsigned char *record)
39 {
40  uint32_t i;
41  unsigned char *old_key;
42  int save_errno;
43  char lastpos[8];
44 
45  MYISAM_SHARE *share=info->s;
46 
47  /* Test if record is in datafile */
48  if (!(info->update & HA_STATE_AKTIV))
49  {
50  return(errno=HA_ERR_KEY_NOT_FOUND); /* No database read */
51  }
52  if (share->options & HA_OPTION_READ_ONLY_DATA)
53  {
54  return(errno=EACCES);
55  }
56  if (_mi_readinfo(info,F_WRLCK,1))
57  return(errno);
58  if (info->s->calc_checksum)
59  info->checksum=(*info->s->calc_checksum)(info,record);
60  if ((*share->compare_record)(info,record))
61  goto err; /* Error on read-check */
62 
63  if (_mi_mark_file_changed(info))
64  goto err;
65 
66  /* Remove all keys from the .ISAM file */
67 
68  old_key=info->lastkey2;
69  for (i=0 ; i < share->base.keys ; i++ )
70  {
71  if (mi_is_key_active(info->s->state.key_map, i))
72  {
73  info->s->keyinfo[i].version++;
74  {
75  if (info->s->keyinfo[i].ck_delete(info,i,old_key,
76  _mi_make_key(info,i,old_key,record,info->lastpos)))
77  goto err;
78  }
79  /* The above changed info->lastkey2. Inform mi_rnext_same(). */
80  info->update&= ~HA_STATE_RNEXT_SAME;
81  }
82  }
83 
84  if ((*share->delete_record)(info))
85  goto err; /* Remove record from database */
86  info->state->checksum-=info->checksum;
87 
88  info->update= HA_STATE_CHANGED+HA_STATE_DELETED+HA_STATE_ROW_CHANGED;
89  info->state->records--;
90 
91  mi_sizestore(lastpos,info->lastpos);
92  _mi_writeinfo(info,WRITEINFO_UPDATE_KEYFILE);
93  return(0);
94 
95 err:
96  save_errno=errno;
97  mi_sizestore(lastpos,info->lastpos);
98  if (save_errno != HA_ERR_RECORD_CHANGED)
99  {
100  mi_print_error(info->s, HA_ERR_CRASHED);
101  mi_mark_crashed(info); /* mark table crashed */
102  }
103  _mi_writeinfo(info,WRITEINFO_UPDATE_KEYFILE);
104  info->update|=HA_STATE_WRITTEN; /* Buffer changed */
105  errno=save_errno;
106  if (save_errno == HA_ERR_KEY_NOT_FOUND)
107  {
108  mi_print_error(info->s, HA_ERR_CRASHED);
109  errno=HA_ERR_CRASHED;
110  }
111 
112  return(errno);
113 } /* mi_delete */
114 
115 
116  /* Remove a key from the btree index */
117 
118 int _mi_ck_delete(register MI_INFO *info, uint32_t keynr, unsigned char *key,
119  uint32_t key_length)
120 {
121  return _mi_ck_real_delete(info, info->s->keyinfo+keynr, key, key_length,
122  &info->s->state.key_root[keynr]);
123 } /* _mi_ck_delete */
124 
125 
126 static int _mi_ck_real_delete(register MI_INFO *info, MI_KEYDEF *keyinfo,
127  unsigned char *key, uint32_t key_length, internal::my_off_t *root)
128 {
129  int error;
130  uint32_t nod_flag;
131  internal::my_off_t old_root;
132  unsigned char *root_buff;
133 
134  if ((old_root=*root) == HA_OFFSET_ERROR)
135  {
136  mi_print_error(info->s, HA_ERR_CRASHED);
137  return(errno=HA_ERR_CRASHED);
138  }
139  if (!(root_buff= (unsigned char*) malloc(keyinfo->block_length+
140  MI_MAX_KEY_BUFF*2)))
141  {
142  return(errno=ENOMEM);
143  }
144  if (!_mi_fetch_keypage(info,keyinfo,old_root,DFLT_INIT_HITS,root_buff,0))
145  {
146  error= -1;
147  goto err;
148  }
149  if ((error=d_search(info,keyinfo, (SEARCH_SAME), key,key_length,old_root,root_buff)) > 0)
150  {
151  if (error == 2)
152  {
153  error=_mi_enlarge_root(info,keyinfo,key,root);
154  }
155  else /* error == 1 */
156  {
157  if (mi_getint(root_buff) <= (nod_flag=mi_test_if_nod(root_buff))+3)
158  {
159  error=0;
160  if (nod_flag)
161  *root=_mi_kpos(nod_flag,root_buff+2+nod_flag);
162  else
163  *root=HA_OFFSET_ERROR;
164  if (_mi_dispose(info,keyinfo,old_root,DFLT_INIT_HITS))
165  error= -1;
166  }
167  else
168  error=_mi_write_keypage(info,keyinfo,old_root,
169  DFLT_INIT_HITS,root_buff);
170  }
171  }
172 err:
173  free(root_buff);
174  return(error);
175 } /* _mi_ck_real_delete */
176 
177 
178  /*
179  ** Remove key below key root
180  ** Return values:
181  ** 1 if there are less buffers; In this case anc_buff is not saved
182  ** 2 if there are more buffers
183  ** -1 on errors
184  */
185 
186 static int d_search(register MI_INFO *info, register MI_KEYDEF *keyinfo,
187  uint32_t comp_flag, unsigned char *key, uint32_t key_length,
188  internal::my_off_t page, unsigned char *anc_buff)
189 {
190  int flag,ret_value,save_flag;
191  uint32_t length,nod_flag,search_key_length;
192  bool last_key;
193  unsigned char *leaf_buff,*keypos;
194  internal::my_off_t leaf_page= 0, next_block;
195  unsigned char lastkey[MI_MAX_KEY_BUFF];
196 
197  search_key_length= (comp_flag & SEARCH_FIND) ? key_length : USE_WHOLE_KEY;
198  flag=(*keyinfo->bin_search)(info,keyinfo,anc_buff,key, search_key_length,
199  comp_flag, &keypos, lastkey, &last_key);
200  if (flag == MI_FOUND_WRONG_KEY)
201  {
202  return(-1);
203  }
204  nod_flag=mi_test_if_nod(anc_buff);
205 
206  leaf_buff= 0;
207  if (nod_flag)
208  {
209  leaf_page=_mi_kpos(nod_flag,keypos);
210  if (!(leaf_buff= (unsigned char*) malloc(keyinfo->block_length+
211  MI_MAX_KEY_BUFF*2)))
212  {
213  errno=ENOMEM;
214  return(-1);
215  }
216  if (!_mi_fetch_keypage(info,keyinfo,leaf_page,DFLT_INIT_HITS,leaf_buff,0))
217  goto err;
218  }
219 
220  if (flag != 0)
221  {
222  if (!nod_flag)
223  {
224  mi_print_error(info->s, HA_ERR_CRASHED);
225  errno=HA_ERR_CRASHED; /* This should newer happend */
226  goto err;
227  }
228  save_flag=0;
229  ret_value=d_search(info,keyinfo,comp_flag,key,key_length,
230  leaf_page,leaf_buff);
231  }
232  else
233  { /* Found key */
234  uint32_t tmp;
235  length=mi_getint(anc_buff);
236  if (!(tmp= remove_key(keyinfo,nod_flag,keypos,lastkey,anc_buff+length,
237  &next_block)))
238  goto err;
239 
240  length-= tmp;
241 
242  mi_putint(anc_buff,length,nod_flag);
243  if (!nod_flag)
244  { /* On leaf page */
245  if (_mi_write_keypage(info,keyinfo,page,DFLT_INIT_HITS,anc_buff))
246  {
247  return(-1);
248  }
249  /* Page will be update later if we return 1 */
250  return(test(length <= (info->quick_mode ? MI_MIN_KEYBLOCK_LENGTH :
251  (uint) keyinfo->underflow_block_length)));
252  }
253  save_flag=1;
254  ret_value=del(info,keyinfo,key,anc_buff,leaf_page,leaf_buff,keypos,
255  next_block,lastkey);
256  }
257  if (ret_value >0)
258  {
259  save_flag=1;
260  if (ret_value == 1)
261  ret_value= underflow(info,keyinfo,anc_buff,leaf_page,leaf_buff,keypos);
262  else
263  { /* This happens only with packed keys */
264  if (!_mi_get_last_key(info,keyinfo,anc_buff,lastkey,keypos,&length))
265  {
266  goto err;
267  }
268  ret_value=_mi_insert(info,keyinfo,key,anc_buff,keypos,lastkey,
269  (unsigned char*) 0,(unsigned char*) 0,(internal::my_off_t) 0,(bool) 0);
270  }
271  }
272  if (ret_value == 0 && mi_getint(anc_buff) > keyinfo->block_length)
273  {
274  save_flag=1;
275  ret_value=_mi_split_page(info,keyinfo,key,anc_buff,lastkey,0) | 2;
276  }
277  if (save_flag && ret_value != 1)
278  ret_value|=_mi_write_keypage(info,keyinfo,page,DFLT_INIT_HITS,anc_buff);
279  free(leaf_buff);
280  return(ret_value);
281 
282 err:
283  free(leaf_buff);
284  return (-1);
285 } /* d_search */
286 
287 
288  /* Remove a key that has a page-reference */
289 
290 static int del(register MI_INFO *info, register MI_KEYDEF *keyinfo, unsigned char *key,
291  unsigned char *anc_buff, internal::my_off_t leaf_page, unsigned char *leaf_buff,
292  unsigned char *keypos, /* Pos to where deleted key was */
293  internal::my_off_t next_block,
294  unsigned char *ret_key) /* key before keypos in anc_buff */
295 {
296  int ret_value,length;
297  uint32_t a_length,nod_flag,tmp;
298  internal::my_off_t next_page;
299  unsigned char keybuff[MI_MAX_KEY_BUFF],*endpos,*next_buff,*key_start, *prev_key;
300  MYISAM_SHARE *share=info->s;
301  MI_KEY_PARAM s_temp;
302 
303  endpos=leaf_buff+mi_getint(leaf_buff);
304  if (!(key_start=_mi_get_last_key(info,keyinfo,leaf_buff,keybuff,endpos,
305  &tmp)))
306  return(-1);
307 
308  if ((nod_flag=mi_test_if_nod(leaf_buff)))
309  {
310  next_page= _mi_kpos(nod_flag,endpos);
311  if (!(next_buff= (unsigned char*) malloc(keyinfo->block_length+
312  MI_MAX_KEY_BUFF*2)))
313  return(-1);
314  if (!_mi_fetch_keypage(info,keyinfo,next_page,DFLT_INIT_HITS,next_buff,0))
315  ret_value= -1;
316  else
317  {
318  if ((ret_value=del(info,keyinfo,key,anc_buff,next_page,next_buff,
319  keypos,next_block,ret_key)) >0)
320  {
321  endpos=leaf_buff+mi_getint(leaf_buff);
322  if (ret_value == 1)
323  {
324  ret_value=underflow(info,keyinfo,leaf_buff,next_page,
325  next_buff,endpos);
326  if (ret_value == 0 && mi_getint(leaf_buff) > keyinfo->block_length)
327  {
328  ret_value=_mi_split_page(info,keyinfo,key,leaf_buff,ret_key,0) | 2;
329  }
330  }
331  else
332  {
333  if (!_mi_get_last_key(info,keyinfo,leaf_buff,keybuff,endpos,
334  &tmp))
335  goto err;
336  ret_value=_mi_insert(info,keyinfo,key,leaf_buff,endpos,keybuff,
337  (unsigned char*) 0,(unsigned char*) 0,(internal::my_off_t) 0,0);
338  }
339  }
340  if (_mi_write_keypage(info,keyinfo,leaf_page,DFLT_INIT_HITS,leaf_buff))
341  goto err;
342  }
343  free(next_buff);
344  return(ret_value);
345  }
346 
347  /* Remove last key from leaf page */
348 
349  mi_putint(leaf_buff,key_start-leaf_buff,nod_flag);
350  if (_mi_write_keypage(info,keyinfo,leaf_page,DFLT_INIT_HITS,leaf_buff))
351  goto err;
352 
353  /* Place last key in ancestor page on deleted key position */
354 
355  a_length=mi_getint(anc_buff);
356  endpos=anc_buff+a_length;
357  if (keypos != anc_buff+2+share->base.key_reflength &&
358  !_mi_get_last_key(info,keyinfo,anc_buff,ret_key,keypos,&tmp))
359  goto err;
360  prev_key=(keypos == anc_buff+2+share->base.key_reflength ?
361  0 : ret_key);
362  length=(*keyinfo->pack_key)(keyinfo,share->base.key_reflength,
363  keypos == endpos ? (unsigned char*) 0 : keypos,
364  prev_key, prev_key,
365  keybuff,&s_temp);
366  if (length > 0)
367  internal::bmove_upp((unsigned char*) endpos+length,(unsigned char*) endpos,(uint) (endpos-keypos));
368  else
369  memmove(keypos,keypos-length, (int) (endpos-keypos)+length);
370  (*keyinfo->store_key)(keyinfo,keypos,&s_temp);
371  /* Save pointer to next leaf */
372  if (!(*keyinfo->get_key)(keyinfo,share->base.key_reflength,&keypos,ret_key))
373  goto err;
374  _mi_kpointer(info,keypos - share->base.key_reflength,next_block);
375  mi_putint(anc_buff,a_length+length,share->base.key_reflength);
376 
377  return( mi_getint(leaf_buff) <=
378  (info->quick_mode ? MI_MIN_KEYBLOCK_LENGTH :
379  (uint) keyinfo->underflow_block_length));
380 err:
381  return(-1);
382 } /* del */
383 
384 
385  /* Balances adjacent pages if underflow occours */
386 
387 static int underflow(register MI_INFO *info, register MI_KEYDEF *keyinfo,
388  unsigned char *anc_buff,
389  internal::my_off_t leaf_page,/* Ancestor page and underflow page */
390  unsigned char *leaf_buff,
391  unsigned char *keypos) /* Position to pos after key */
392 {
393  int t_length;
394  uint32_t length,anc_length,buff_length,leaf_length,p_length,s_length,nod_flag,
395  key_reflength,key_length;
396  internal::my_off_t next_page;
397  unsigned char anc_key[MI_MAX_KEY_BUFF],leaf_key[MI_MAX_KEY_BUFF],
398  *buff,*endpos,*next_keypos,*anc_pos,*half_pos,*temp_pos,*prev_key,
399  *after_key;
400  MI_KEY_PARAM s_temp;
401  MYISAM_SHARE *share=info->s;
402 
403  buff=info->buff;
404  info->buff_used=1;
405  next_keypos=keypos;
406  nod_flag=mi_test_if_nod(leaf_buff);
407  p_length=nod_flag+2;
408  anc_length=mi_getint(anc_buff);
409  leaf_length=mi_getint(leaf_buff);
410  key_reflength=share->base.key_reflength;
411  if (info->s->keyinfo+info->lastinx == keyinfo)
412  info->page_changed=1;
413 
414  if ((keypos < anc_buff+anc_length && (info->state->records & 1)) ||
415  keypos == anc_buff+2+key_reflength)
416  { /* Use page right of anc-page */
417  if (keyinfo->flag & HA_BINARY_PACK_KEY)
418  {
419  if (!(next_keypos=_mi_get_key(info, keyinfo,
420  anc_buff, buff, keypos, &length)))
421  goto err;
422  }
423  else
424  {
425  /* Got to end of found key */
426  buff[0]=buff[1]=0; /* Avoid length error check if packed key */
427  if (!(*keyinfo->get_key)(keyinfo,key_reflength,&next_keypos,
428  buff))
429  goto err;
430  }
431  next_page= _mi_kpos(key_reflength,next_keypos);
432  if (!_mi_fetch_keypage(info,keyinfo,next_page,DFLT_INIT_HITS,buff,0))
433  goto err;
434  buff_length=mi_getint(buff);
435 
436  /* find keys to make a big key-page */
437  memmove(next_keypos - key_reflength, buff + 2, key_reflength);
438  if (!_mi_get_last_key(info,keyinfo,anc_buff,anc_key,next_keypos,&length)
439  || !_mi_get_last_key(info,keyinfo,leaf_buff,leaf_key,
440  leaf_buff+leaf_length,&length))
441  goto err;
442 
443  /* merge pages and put parting key from anc_buff between */
444  prev_key=(leaf_length == p_length ? (unsigned char*) 0 : leaf_key);
445  t_length=(*keyinfo->pack_key)(keyinfo,nod_flag,buff+p_length,
446  prev_key, prev_key,
447  anc_key, &s_temp);
448  length=buff_length-p_length;
449  endpos=buff+length+leaf_length+t_length;
450  /* buff will always be larger than before !*/
451  internal::bmove_upp((unsigned char*) endpos, (unsigned char*) buff+buff_length,length);
452  memcpy(buff, leaf_buff, leaf_length);
453  (*keyinfo->store_key)(keyinfo,buff+leaf_length,&s_temp);
454  buff_length=(uint) (endpos-buff);
455  mi_putint(buff,buff_length,nod_flag);
456 
457  /* remove key from anc_buff */
458 
459  if (!(s_length=remove_key(keyinfo,key_reflength,keypos,anc_key,
460  anc_buff+anc_length,(internal::my_off_t *) 0)))
461  goto err;
462 
463  anc_length-=s_length;
464  mi_putint(anc_buff,anc_length,key_reflength);
465 
466  if (buff_length <= keyinfo->block_length)
467  { /* Keys in one page */
468  memcpy(leaf_buff, buff, buff_length);
469  if (_mi_dispose(info,keyinfo,next_page,DFLT_INIT_HITS))
470  goto err;
471  }
472  else
473  { /* Page is full */
474  endpos=anc_buff+anc_length;
475  if (keypos != anc_buff+2+key_reflength &&
476  !_mi_get_last_key(info,keyinfo,anc_buff,anc_key,keypos,&length))
477  goto err;
478  if (!(half_pos=_mi_find_half_pos(nod_flag, keyinfo, buff, leaf_key,
479  &key_length, &after_key)))
480  goto err;
481  length=(uint) (half_pos-buff);
482  memcpy(leaf_buff, buff, length);
483  mi_putint(leaf_buff,length,nod_flag);
484 
485  /* Correct new keypointer to leaf_page */
486  half_pos=after_key;
487  _mi_kpointer(info,leaf_key+key_length,next_page);
488  /* Save key in anc_buff */
489  prev_key=(keypos == anc_buff+2+key_reflength ? (unsigned char*) 0 : anc_key),
490  t_length=(*keyinfo->pack_key)(keyinfo,key_reflength,
491  (keypos == endpos ? (unsigned char*) 0 :
492  keypos),
493  prev_key, prev_key,
494  leaf_key, &s_temp);
495  if (t_length >= 0)
496  internal::bmove_upp((unsigned char*) endpos+t_length,(unsigned char*) endpos,
497  (uint) (endpos-keypos));
498  else
499  memmove(keypos,keypos-t_length,(uint) (endpos-keypos)+t_length);
500  (*keyinfo->store_key)(keyinfo,keypos,&s_temp);
501  mi_putint(anc_buff,(anc_length+=t_length),key_reflength);
502 
503  /* Store key first in new page */
504  if (nod_flag)
505  memmove(buff + 2, half_pos - nod_flag, nod_flag);
506  if (!(*keyinfo->get_key)(keyinfo,nod_flag,&half_pos,leaf_key))
507  goto err;
508  t_length=(int) (*keyinfo->pack_key)(keyinfo, nod_flag, (unsigned char*) 0,
509  (unsigned char*) 0, (unsigned char *) 0,
510  leaf_key, &s_temp);
511  /* t_length will always be > 0 for a new page !*/
512  length=(uint) ((buff+mi_getint(buff))-half_pos);
513  memmove(buff + p_length + t_length, half_pos, length);
514  (*keyinfo->store_key)(keyinfo,buff+p_length,&s_temp);
515  mi_putint(buff,length+t_length+p_length,nod_flag);
516 
517  if (_mi_write_keypage(info,keyinfo,next_page,DFLT_INIT_HITS,buff))
518  goto err;
519  }
520  if (_mi_write_keypage(info,keyinfo,leaf_page,DFLT_INIT_HITS,leaf_buff))
521  goto err;
522  return(anc_length <= ((info->quick_mode ? MI_MIN_BLOCK_LENGTH :
523  (uint) keyinfo->underflow_block_length)));
524  }
525 
526  keypos=_mi_get_last_key(info,keyinfo,anc_buff,anc_key,keypos,&length);
527  if (!keypos)
528  goto err;
529  next_page= _mi_kpos(key_reflength,keypos);
530  if (!_mi_fetch_keypage(info,keyinfo,next_page,DFLT_INIT_HITS,buff,0))
531  goto err;
532  buff_length=mi_getint(buff);
533  endpos=buff+buff_length;
534 
535  /* find keys to make a big key-page */
536  memmove(next_keypos - key_reflength, leaf_buff+2, key_reflength);
537  next_keypos=keypos;
538  if (!(*keyinfo->get_key)(keyinfo,key_reflength,&next_keypos,
539  anc_key))
540  goto err;
541  if (!_mi_get_last_key(info,keyinfo,buff,leaf_key,endpos,&length))
542  goto err;
543 
544  /* merge pages and put parting key from anc_buff between */
545  prev_key=(leaf_length == p_length ? (unsigned char*) 0 : leaf_key);
546  t_length=(*keyinfo->pack_key)(keyinfo,nod_flag,
547  (leaf_length == p_length ?
548  (unsigned char*) 0 : leaf_buff+p_length),
549  prev_key, prev_key,
550  anc_key, &s_temp);
551  if (t_length >= 0)
552  memmove(endpos+t_length,leaf_buff+p_length, leaf_length-p_length);
553  else /* We gained space */
554  memmove(endpos, leaf_buff+((int) p_length-t_length),
555  leaf_length - p_length + t_length);
556 
557  (*keyinfo->store_key)(keyinfo,endpos,&s_temp);
558  buff_length=buff_length+leaf_length-p_length+t_length;
559  mi_putint(buff,buff_length,nod_flag);
560 
561  /* remove key from anc_buff */
562  if (!(s_length= remove_key(keyinfo,key_reflength,keypos,anc_key,
563  anc_buff+anc_length,(internal::my_off_t *) 0)))
564  goto err;
565 
566  anc_length-=s_length;
567  mi_putint(anc_buff,anc_length,key_reflength);
568 
569  if (buff_length <= keyinfo->block_length)
570  { /* Keys in one page */
571  if (_mi_dispose(info,keyinfo,leaf_page,DFLT_INIT_HITS))
572  goto err;
573  }
574  else
575  { /* Page is full */
576  if (keypos == anc_buff+2+key_reflength)
577  anc_pos=0; /* First key */
578  else if (!_mi_get_last_key(info,keyinfo,anc_buff,anc_pos=anc_key,keypos,
579  &length))
580  goto err;
581  endpos=_mi_find_half_pos(nod_flag,keyinfo,buff,leaf_key,
582  &key_length, &half_pos);
583  if (!endpos)
584  goto err;
585  _mi_kpointer(info,leaf_key+key_length,leaf_page);
586  /* Save key in anc_buff */
587 
588  temp_pos=anc_buff+anc_length;
589  t_length=(*keyinfo->pack_key)(keyinfo,key_reflength,
590  keypos == temp_pos ? (unsigned char*) 0
591  : keypos,
592  anc_pos, anc_pos,
593  leaf_key,&s_temp);
594  if (t_length > 0)
595  internal::bmove_upp((unsigned char*) temp_pos+t_length,(unsigned char*) temp_pos,
596  (uint) (temp_pos-keypos));
597  else
598  memmove(keypos,keypos-t_length,(uint) (temp_pos-keypos)+t_length);
599  (*keyinfo->store_key)(keyinfo,keypos,&s_temp);
600  mi_putint(anc_buff,(anc_length+=t_length),key_reflength);
601 
602  /* Store first key on new page */
603  if (nod_flag)
604  memmove(leaf_buff+2, half_pos - nod_flag, nod_flag);
605  if (!(length=(*keyinfo->get_key)(keyinfo,nod_flag,&half_pos,leaf_key)))
606  goto err;
607  t_length=(*keyinfo->pack_key)(keyinfo,nod_flag, (unsigned char*) 0,
608  (unsigned char*) 0, (unsigned char*) 0, leaf_key, &s_temp);
609  length=(uint) ((buff+buff_length)-half_pos);
610  memmove(leaf_buff + p_length + t_length, half_pos, length);
611  (*keyinfo->store_key)(keyinfo,leaf_buff+p_length,&s_temp);
612  mi_putint(leaf_buff,length+t_length+p_length,nod_flag);
613  if (_mi_write_keypage(info,keyinfo,leaf_page,DFLT_INIT_HITS,leaf_buff))
614  goto err;
615  mi_putint(buff,endpos-buff,nod_flag);
616  }
617  if (_mi_write_keypage(info,keyinfo,next_page,DFLT_INIT_HITS,buff))
618  goto err;
619  return(anc_length <= (uint) keyinfo->block_length/2);
620 
621 err:
622  return(-1);
623 } /* underflow */
624 
625 
626  /*
627  remove a key from packed buffert
628  The current code doesn't handle the case that the next key may be
629  packed better against the previous key if there is a case difference
630  returns how many chars was removed or 0 on error
631  */
632 
633 static uint32_t remove_key(MI_KEYDEF *keyinfo, uint32_t nod_flag,
634  unsigned char *keypos, /* Where key starts */
635  unsigned char *lastkey, /* key to be removed */
636  unsigned char *page_end, /* End of page */
637  internal::my_off_t *next_block) /* ptr to next block */
638 {
639  int s_length;
640  unsigned char *start;
641 
642  start=keypos;
643  if (!(keyinfo->flag &
644  (HA_PACK_KEY | HA_SPACE_PACK_USED | HA_VAR_LENGTH_KEY |
645  HA_BINARY_PACK_KEY)))
646  {
647  s_length=(int) (keyinfo->keylength+nod_flag);
648  if (next_block && nod_flag)
649  *next_block= _mi_kpos(nod_flag,keypos+s_length);
650  }
651  else
652  { /* Let keypos point at next key */
653  /* Calculate length of key */
654  if (!(*keyinfo->get_key)(keyinfo,nod_flag,&keypos,lastkey))
655  return(0); /* Error */
656 
657  if (next_block && nod_flag)
658  *next_block= _mi_kpos(nod_flag,keypos);
659  s_length=(int) (keypos-start);
660  if (keypos != page_end)
661  {
662  if (keyinfo->flag & HA_BINARY_PACK_KEY)
663  {
664  unsigned char *old_key=start;
665  uint32_t next_length,prev_length,prev_pack_length;
666  get_key_length(next_length,keypos);
667  get_key_pack_length(prev_length,prev_pack_length,old_key);
668  if (next_length > prev_length)
669  {
670  /* We have to copy data from the current key to the next key */
671  internal::bmove_upp(keypos, (lastkey+next_length),
672  (next_length-prev_length));
673  keypos-=(next_length-prev_length)+prev_pack_length;
674  store_key_length(keypos,prev_length);
675  s_length=(int) (keypos-start);
676  }
677  }
678  else
679  {
680  /* Check if a variable length first key part */
681  if ((keyinfo->seg->flag & HA_PACK_KEY) && *keypos & 128)
682  {
683  /* Next key is packed against the current one */
684  uint32_t next_length,prev_length,prev_pack_length,lastkey_length,
685  rest_length;
686  if (keyinfo->seg[0].length >= 127)
687  {
688  if (!(prev_length=mi_uint2korr(start) & 32767))
689  goto end;
690  next_length=mi_uint2korr(keypos) & 32767;
691  keypos+=2;
692  prev_pack_length=2;
693  }
694  else
695  {
696  if (!(prev_length= *start & 127))
697  goto end; /* Same key as previous*/
698  next_length= *keypos & 127;
699  keypos++;
700  prev_pack_length=1;
701  }
702  if (!(*start & 128))
703  prev_length=0; /* prev key not packed */
704  if (keyinfo->seg[0].flag & HA_NULL_PART)
705  lastkey++; /* Skip null marker */
706  get_key_length(lastkey_length,lastkey);
707  if (!next_length) /* Same key after */
708  {
709  next_length=lastkey_length;
710  rest_length=0;
711  }
712  else
713  get_key_length(rest_length,keypos);
714 
715  if (next_length >= prev_length)
716  { /* Key after is based on deleted key */
717  uint32_t pack_length,tmp;
718  internal::bmove_upp(keypos, (lastkey+next_length),
719  tmp=(next_length-prev_length));
720  rest_length+=tmp;
721  pack_length= prev_length ? get_pack_length(rest_length): 0;
722  keypos-=tmp+pack_length+prev_pack_length;
723  s_length=(int) (keypos-start);
724  if (prev_length) /* Pack against prev key */
725  {
726  *keypos++= start[0];
727  if (prev_pack_length == 2)
728  *keypos++= start[1];
729  store_key_length(keypos,rest_length);
730  }
731  else
732  {
733  /* Next key is not packed anymore */
734  if (keyinfo->seg[0].flag & HA_NULL_PART)
735  {
736  rest_length++; /* Mark not null */
737  }
738  if (prev_pack_length == 2)
739  {
740  mi_int2store(keypos,rest_length);
741  }
742  else
743  *keypos= rest_length;
744  }
745  }
746  }
747  }
748  }
749  }
750 end:
751  assert(page_end-start >= s_length);
752  memmove(start, start + s_length, page_end-start-s_length);
753  return s_length;
754 } /* remove_key */