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