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