drizzle
C++ MySQL-protocol-compatible database server
Loading...
Searching...
No Matches
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
22using namespace drizzled;
23
24static 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);
26static 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);
29static 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);
31static 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);
34static int _mi_ck_real_delete(MI_INFO *info,MI_KEYDEF *keyinfo,
35 unsigned char *key, uint32_t key_length, internal::my_off_t *root);
36
37
38int 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
95err:
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
118int _mi_ck_delete(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
126static int _mi_ck_real_delete(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 }
172err:
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
186static int d_search(MI_INFO *info, 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
282err:
283 free(leaf_buff);
284 return (-1);
285} /* d_search */
286
287
288 /* Remove a key that has a page-reference */
289
290static int del(MI_INFO *info, 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));
380err:
381 return(-1);
382} /* del */
383
384
385 /* Balances adjacent pages if underflow occours */
386
387static int underflow(MI_INFO *info, 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
621err:
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
633static 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 }
750end:
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 */
TODO: Rename this file - func.h is stupid.