18 #include "myisam_priv.h"
20 #include <drizzled/internal/m_string.h>
21 #include <drizzled/util/test.h>
22 #include <drizzled/tree.h>
24 using namespace drizzled;
26 #define MAX_POINTER_LENGTH 8
31 uint32_t comp_flag,
unsigned char *key,
32 uint32_t key_length, internal::my_off_t pos,
unsigned char *father_buff,
33 unsigned char *father_keypos, internal::my_off_t father_page,
35 static int _mi_balance_page(
MI_INFO *info,
MI_KEYDEF *keyinfo,
unsigned char *key,
36 unsigned char *curr_buff,
unsigned char *father_buff,
37 unsigned char *father_keypos,internal::my_off_t father_page);
38 static unsigned char *_mi_find_last_pos(
MI_KEYDEF *keyinfo,
unsigned char *page,
39 unsigned char *key, uint32_t *return_key_length,
40 unsigned char **after_key);
41 int _mi_ck_write_tree(
register MI_INFO *info, uint32_t keynr,
unsigned char *key,
43 int _mi_ck_write_btree(
register MI_INFO *info, uint32_t keynr,
unsigned char *key,
48 int mi_write(
MI_INFO *info,
unsigned char *record)
53 internal::my_off_t filepos;
55 bool lock_tree= share->concurrent_insert;
57 if (share->options & HA_OPTION_READ_ONLY_DATA)
61 if (_mi_readinfo(info,F_WRLCK,1))
63 filepos= ((share->state.dellink != HA_OFFSET_ERROR &&
64 !info->append_insert_at_end) ?
65 share->state.dellink :
66 info->state->data_file_length);
68 if (share->base.reloc == (ha_rows) 1 &&
69 share->base.records == (ha_rows) 1 &&
70 info->state->records == (ha_rows) 1)
72 errno=HA_ERR_RECORD_FILE_FULL;
75 if (info->state->key_file_length >= share->base.margin_key_file_length)
77 errno=HA_ERR_INDEX_FILE_FULL;
80 if (_mi_mark_file_changed(info))
84 for (i=0 ; i < share->state.header.uniques ; i++)
86 if (mi_check_unique(info,share->uniqueinfo+i,record,
87 mi_unique_hash(share->uniqueinfo+i,record),
95 for (i=0 ; i < share->base.keys ; i++)
97 if (mi_is_key_active(share->state.key_map, i))
99 bool local_lock_tree= (lock_tree &&
100 !(info->bulk_insert &&
101 info->bulk_insert[i].is_inited()));
104 share->keyinfo[i].version++;
107 if (share->keyinfo[i].ck_insert(info,i,buff,
108 _mi_make_key(info,i,buff,record,filepos)))
115 info->update&= ~HA_STATE_RNEXT_SAME;
118 if (share->calc_checksum)
119 info->checksum=(*share->calc_checksum)(info,record);
120 if (!(info->opt_flag & OPT_NO_ROWS))
122 if ((*share->write_record)(info,record))
124 info->state->checksum+=info->checksum;
126 if (share->base.auto_key)
127 set_if_bigger(info->s->state.auto_increment,
128 retrieve_auto_increment(info, record));
129 info->update= (HA_STATE_CHANGED | HA_STATE_AKTIV | HA_STATE_WRITTEN |
130 HA_STATE_ROW_CHANGED);
131 info->state->records++;
132 info->lastpos=filepos;
133 _mi_writeinfo(info, WRITEINFO_UPDATE_KEYFILE);
143 if (share->is_log_table)
150 if (errno == HA_ERR_FOUND_DUPP_KEY || errno == HA_ERR_RECORD_FILE_FULL ||
151 errno == HA_ERR_NULL_IN_SPATIAL || errno == HA_ERR_OUT_OF_MEM)
153 if (info->bulk_insert)
156 for (j=0 ; j < share->base.keys ; j++)
157 mi_flush_bulk_insert(info, j);
159 info->errkey= (int) i;
162 if (mi_is_key_active(share->state.key_map, i))
165 uint32_t key_length=_mi_make_key(info,i,buff,record,filepos);
166 if (_mi_ck_delete(info,i,buff,key_length))
176 mi_print_error(info->s, HA_ERR_CRASHED);
177 mi_mark_crashed(info);
179 info->update= (HA_STATE_CHANGED | HA_STATE_WRITTEN | HA_STATE_ROW_CHANGED);
183 _mi_writeinfo(info,WRITEINFO_UPDATE_KEYFILE);
184 return(errno=save_errno);
190 int _mi_ck_write(
MI_INFO *info, uint32_t keynr,
unsigned char *key, uint32_t key_length)
192 if (info->bulk_insert && info->bulk_insert[keynr].is_inited())
194 return(_mi_ck_write_tree(info, keynr, key, key_length));
198 return(_mi_ck_write_btree(info, keynr, key, key_length));
207 int _mi_ck_write_btree(
register MI_INFO *info, uint32_t keynr,
unsigned char *key,
212 MI_KEYDEF *keyinfo=info->s->keyinfo+keynr;
213 internal::my_off_t *root=&info->s->state.key_root[keynr];
215 if (keyinfo->flag & HA_SORT_ALLOWS_SAME)
216 comp_flag=SEARCH_BIGGER;
217 else if (keyinfo->flag & (HA_NOSAME))
219 comp_flag=SEARCH_FIND | SEARCH_UPDATE;
220 if (keyinfo->flag & HA_NULL_ARE_EQUAL)
221 comp_flag|= SEARCH_NULL_ARE_EQUAL;
224 comp_flag=SEARCH_SAME;
226 error=_mi_ck_real_write_btree(info, keyinfo, key, key_length,
232 unsigned char *key, uint32_t key_length, internal::my_off_t *root, uint32_t comp_flag)
236 if (*root == HA_OFFSET_ERROR ||
237 (error=w_search(info, keyinfo, comp_flag, key, key_length,
238 *root, (
unsigned char *) 0, (
unsigned char*) 0,
239 (internal::my_off_t) 0, 1)) > 0)
240 error=_mi_enlarge_root(info,keyinfo,key,root);
248 internal::my_off_t *root)
250 uint32_t t_length,nod_flag;
254 nod_flag= (*root != HA_OFFSET_ERROR) ? share->base.key_reflength : 0;
255 _mi_kpointer(info,info->buff+2,*root);
256 t_length=(*keyinfo->pack_key)(keyinfo,nod_flag,(
unsigned char*) 0,
257 (
unsigned char*) 0, (
unsigned char*) 0, key,&s_temp);
258 mi_putint(info->buff,t_length+2+nod_flag,nod_flag);
259 (*keyinfo->store_key)(keyinfo,info->buff+2+nod_flag,&s_temp);
260 info->buff_used=info->page_changed=1;
261 if ((*root= _mi_new(info,keyinfo,DFLT_INIT_HITS)) == HA_OFFSET_ERROR ||
262 _mi_write_keypage(info,keyinfo,*root,DFLT_INIT_HITS,info->buff))
276 uint32_t comp_flag,
unsigned char *key, uint32_t key_length, internal::my_off_t page,
277 unsigned char *father_buff,
unsigned char *father_keypos,
278 internal::my_off_t father_page,
bool insert_last)
281 uint32_t nod_flag, search_key_length;
282 unsigned char *temp_buff,*keypos;
283 unsigned char keybuff[MI_MAX_KEY_BUFF];
285 internal::my_off_t next_page, dupp_key_pos;
287 search_key_length= (comp_flag & SEARCH_FIND) ? key_length : USE_WHOLE_KEY;
288 if (!(temp_buff= (
unsigned char*) malloc(keyinfo->block_length+
291 if (!_mi_fetch_keypage(info,keyinfo,page,DFLT_INIT_HITS,temp_buff,0))
294 flag=(*keyinfo->bin_search)(info,keyinfo,temp_buff,key,search_key_length,
295 comp_flag, &keypos, keybuff, &was_last_key);
296 nod_flag=mi_test_if_nod(temp_buff);
299 uint32_t tmp_key_length;
301 tmp_key_length=(*keyinfo->get_key)(keyinfo,nod_flag,&keypos,keybuff);
303 dupp_key_pos=_mi_dpos(info,0,keybuff+tmp_key_length);
305 dupp_key_pos= HA_OFFSET_ERROR;
308 info->dupp_key_pos= dupp_key_pos;
310 errno=HA_ERR_FOUND_DUPP_KEY;
314 if (flag == MI_FOUND_WRONG_KEY)
318 next_page=_mi_kpos(nod_flag,keypos);
319 if (next_page == HA_OFFSET_ERROR ||
320 (error=w_search(info, keyinfo, comp_flag, key, key_length, next_page,
321 temp_buff, keypos, page, insert_last)) >0)
323 error=_mi_insert(info,keyinfo,key,temp_buff,keypos,keybuff,father_buff,
324 father_keypos,father_page, insert_last);
325 if (_mi_write_keypage(info,keyinfo,page,DFLT_INIT_HITS,temp_buff))
362 unsigned char *key,
unsigned char *anc_buff,
unsigned char *key_pos,
unsigned char *key_buff,
363 unsigned char *father_buff,
unsigned char *father_key_pos, internal::my_off_t father_page,
366 uint32_t a_length,nod_flag;
368 unsigned char *endpos, *prev_key;
371 nod_flag=mi_test_if_nod(anc_buff);
372 a_length=mi_getint(anc_buff);
373 endpos= anc_buff+ a_length;
374 prev_key=(key_pos == anc_buff+2+nod_flag ? (
unsigned char*) 0 : key_buff);
375 t_length=(*keyinfo->pack_key)(keyinfo,nod_flag,
376 (key_pos == endpos ? (
unsigned char*) 0 : key_pos),
382 if (t_length >= keyinfo->maxlength*2+MAX_POINTER_LENGTH)
384 mi_print_error(info->s, HA_ERR_CRASHED);
385 errno=HA_ERR_CRASHED;
388 internal::bmove_upp((
unsigned char*) endpos+t_length,(
unsigned char*) endpos,(uint) (endpos-key_pos));
392 if (-t_length >= keyinfo->maxlength*2+MAX_POINTER_LENGTH)
394 mi_print_error(info->s, HA_ERR_CRASHED);
395 errno=HA_ERR_CRASHED;
398 memmove(key_pos, key_pos - t_length, endpos - key_pos + t_length);
400 (*keyinfo->store_key)(keyinfo,key_pos,&s_temp);
402 mi_putint(anc_buff,a_length,nod_flag);
403 if (a_length <= keyinfo->block_length)
410 if (!(keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)) &&
411 father_buff && !insert_last)
412 return(_mi_balance_page(info,keyinfo,key,anc_buff,father_buff,
413 father_key_pos,father_page));
414 return(_mi_split_page(info,keyinfo,key,anc_buff,key_buff, insert_last));
421 unsigned char *key,
unsigned char *buff,
unsigned char *key_buff,
422 bool insert_last_key)
424 uint32_t length,a_length,key_ref_length,t_length,nod_flag,key_length;
425 unsigned char *key_pos,*pos, *after_key= NULL;
426 internal::my_off_t new_pos;
429 if (info->s->keyinfo+info->lastinx == keyinfo)
430 info->page_changed=1;
432 nod_flag=mi_test_if_nod(buff);
433 key_ref_length=2+nod_flag;
435 key_pos=_mi_find_last_pos(keyinfo,buff,key_buff, &key_length, &after_key);
437 key_pos=_mi_find_half_pos(nod_flag,keyinfo,buff,key_buff, &key_length,
442 length=(uint) (key_pos-buff);
443 a_length=mi_getint(buff);
444 mi_putint(buff,length,nod_flag);
449 pos=key_pos-nod_flag;
450 memcpy(info->buff + 2, pos, nod_flag);
454 if ((new_pos=_mi_new(info,keyinfo,DFLT_INIT_HITS)) == HA_OFFSET_ERROR)
456 _mi_kpointer(info,_mi_move_key(keyinfo,key,key_buff),new_pos);
459 if (!(*keyinfo->get_key)(keyinfo,nod_flag,&key_pos,key_buff))
462 t_length=(*keyinfo->pack_key)(keyinfo,nod_flag,(
unsigned char *) 0,
463 (
unsigned char*) 0, (
unsigned char*) 0,
465 length=(uint) ((buff+a_length)-key_pos);
466 memcpy(info->buff+key_ref_length+t_length, key_pos, length);
467 (*keyinfo->store_key)(keyinfo,info->buff+key_ref_length,&s_temp);
468 mi_putint(info->buff,length+t_length+key_ref_length,nod_flag);
470 if (_mi_write_keypage(info,keyinfo,new_pos,DFLT_INIT_HITS,info->buff))
484 unsigned char *_mi_find_half_pos(uint32_t nod_flag,
MI_KEYDEF *keyinfo,
unsigned char *page,
485 unsigned char *key, uint32_t *return_key_length,
486 unsigned char **after_key)
488 uint32_t keys,length,key_ref_length;
489 unsigned char *end,*lastpos;
491 key_ref_length=2+nod_flag;
492 length=mi_getint(page)-key_ref_length;
493 page+=key_ref_length;
494 if (!(keyinfo->flag &
495 (HA_PACK_KEY | HA_SPACE_PACK_USED | HA_VAR_LENGTH_KEY |
496 HA_BINARY_PACK_KEY)))
498 key_ref_length=keyinfo->keylength+nod_flag;
499 keys=length/(key_ref_length*2);
500 *return_key_length=keyinfo->keylength;
501 end=page+keys*key_ref_length;
502 *after_key=end+key_ref_length;
503 memcpy(key,end,key_ref_length);
507 end=page+length/2-key_ref_length;
512 if (!(length=(*keyinfo->get_key)(keyinfo,nod_flag,&page,key)))
514 }
while (page < end);
515 *return_key_length=length;
527 static unsigned char *_mi_find_last_pos(
MI_KEYDEF *keyinfo,
unsigned char *page,
528 unsigned char *key, uint32_t *return_key_length,
529 unsigned char **after_key)
533 uint32_t last_length= 0;
534 uint32_t key_ref_length;
535 unsigned char *end, *lastpos, *prevpos= NULL;
536 unsigned char key_buff[MI_MAX_KEY_BUFF];
539 length=mi_getint(page)-key_ref_length;
540 page+=key_ref_length;
541 if (!(keyinfo->flag &
542 (HA_PACK_KEY | HA_SPACE_PACK_USED | HA_VAR_LENGTH_KEY |
543 HA_BINARY_PACK_KEY)))
545 keys=length/keyinfo->keylength-2;
546 *return_key_length=length=keyinfo->keylength;
547 end=page+keys*length;
548 *after_key=end+length;
549 memcpy(key,end,length);
553 end= page + length - key_ref_length;
559 prevpos=lastpos; lastpos=page;
561 memcpy(key, key_buff, length);
562 if (!(length=(*keyinfo->get_key)(keyinfo,0,&page,key_buff)))
564 mi_print_error(keyinfo->share, HA_ERR_CRASHED);
565 errno=HA_ERR_CRASHED;
569 *return_key_length=last_length;
579 unsigned char *key,
unsigned char *curr_buff,
unsigned char *father_buff,
580 unsigned char *father_key_pos, internal::my_off_t father_page)
583 uint32_t k_length,father_length,father_keylength,nod_flag,curr_keylength,
584 right_length,left_length,new_right_length,new_left_length,extra_length,
586 unsigned char *pos,*buff,*extra_buff;
587 internal::my_off_t next_page,new_pos;
588 unsigned char tmp_part_key[MI_MAX_KEY_BUFF];
590 k_length=keyinfo->keylength;
591 father_length=mi_getint(father_buff);
592 father_keylength=k_length+info->s->base.key_reflength;
593 nod_flag=mi_test_if_nod(curr_buff);
594 curr_keylength=k_length+nod_flag;
595 info->page_changed=1;
597 if ((father_key_pos != father_buff+father_length &&
598 (info->state->records & 1)) ||
599 father_key_pos == father_buff+2+info->s->base.key_reflength)
602 next_page= _mi_kpos(info->s->base.key_reflength,
603 father_key_pos+father_keylength);
609 father_key_pos-=father_keylength;
610 next_page= _mi_kpos(info->s->base.key_reflength,father_key_pos);
612 buff=curr_buff; curr_buff=info->buff;
615 if (!_mi_fetch_keypage(info,keyinfo,next_page,DFLT_INIT_HITS,info->buff,0))
620 left_length=mi_getint(curr_buff);
621 right_length=mi_getint(buff);
622 keys=(left_length+right_length-4-nod_flag*2)/curr_keylength;
624 if ((right ? right_length : left_length) + curr_keylength <=
625 keyinfo->block_length)
627 new_left_length=2+nod_flag+(keys/2)*curr_keylength;
628 new_right_length=2+nod_flag+((keys+1)/2)*curr_keylength;
629 mi_putint(curr_buff,new_left_length,nod_flag);
630 mi_putint(buff,new_right_length,nod_flag);
632 if (left_length < new_left_length)
634 pos=curr_buff+left_length;
635 memcpy(pos, father_key_pos, k_length);
636 length= new_left_length - left_length - k_length;
637 memcpy(pos+k_length, buff+2, length);
639 memcpy(father_key_pos, pos, k_length);
640 memmove(buff+2, pos+k_length, new_right_length);
645 internal::bmove_upp((
unsigned char*) buff+new_right_length,(
unsigned char*) buff+right_length,
647 length=new_right_length-right_length-k_length;
648 memcpy(buff+2+length,father_key_pos, k_length);
649 pos=curr_buff+new_left_length;
650 memcpy(father_key_pos, pos, k_length);
651 memcpy(buff+2, pos+k_length, length);
654 if (_mi_write_keypage(info,keyinfo,next_page,DFLT_INIT_HITS,info->buff) ||
655 _mi_write_keypage(info,keyinfo,father_page,DFLT_INIT_HITS,father_buff))
662 extra_buff=info->buff+info->s->base.max_key_block_length;
663 new_left_length=new_right_length=2+nod_flag+(keys+1)/3*curr_keylength;
665 new_left_length-=curr_keylength;
666 extra_length=nod_flag+left_length+right_length-
667 new_left_length-new_right_length-curr_keylength;
668 mi_putint(curr_buff,new_left_length,nod_flag);
669 mi_putint(buff,new_right_length,nod_flag);
670 mi_putint(extra_buff,extra_length+2,nod_flag);
673 pos=buff+right_length-extra_length;
674 memcpy(extra_buff+2, pos, extra_length);
676 memcpy(tmp_part_key, pos-k_length,k_length);
678 internal::bmove_upp((
unsigned char*) buff+new_right_length,(
unsigned char*) pos-k_length,
679 right_length-extra_length-k_length-2);
681 pos= curr_buff+new_left_length;
682 length= left_length - new_left_length - k_length;
683 memcpy(buff+2, pos+k_length, length);
685 memcpy(buff+2+length, father_key_pos, k_length);
688 memcpy((right ? key : father_key_pos), pos, k_length);
689 memcpy((right ? father_key_pos : key), tmp_part_key, k_length);
691 if ((new_pos=_mi_new(info,keyinfo,DFLT_INIT_HITS)) == HA_OFFSET_ERROR)
693 _mi_kpointer(info,key+k_length,new_pos);
694 if (_mi_write_keypage(info,keyinfo,(right ? new_pos : next_page),
695 DFLT_INIT_HITS,info->buff) ||
696 _mi_write_keypage(info,keyinfo,(right ? next_page : new_pos),
697 DFLT_INIT_HITS,extra_buff))
715 int _mi_ck_write_tree(
register MI_INFO *info, uint32_t keynr,
unsigned char *key,
720 error= info->bulk_insert[keynr].tree_insert(key,
721 key_length + info->s->rec_reflength,
722 info->bulk_insert[keynr].getCustomArg()) ? 0 : HA_ERR_OUT_OF_MEM ;
730 static int keys_compare(
bulk_insert_param *param,
unsigned char *key1,
unsigned char *key2)
732 uint32_t not_used[2];
733 return ha_key_cmp(param->info->s->keyinfo[param->keynr].seg,
734 key1, key2, USE_WHOLE_KEY, SEARCH_SAME,
739 static int keys_free(
unsigned char *key, TREE_FREE mode,
bulk_insert_param *param)
745 unsigned char lastkey[MI_MAX_KEY_BUFF];
751 if (param->info->s->concurrent_insert)
753 param->info->s->keyinfo[param->keynr].version++;
757 keyinfo=param->info->s->keyinfo+param->keynr;
758 keylen=_mi_keylength(keyinfo, key);
759 memcpy(lastkey, key, keylen);
760 return _mi_ck_write_btree(param->info,param->keynr,lastkey,
761 keylen - param->info->s->rec_reflength);
769 int mi_init_bulk_insert(
MI_INFO *info, uint32_t cache_size, ha_rows rows)
774 uint32_t i, num_keys, total_keylength;
777 assert(!info->bulk_insert &&
778 (!rows || rows >= MI_MIN_ROWS_TO_USE_BULK_INSERT));
780 mi_clear_all_keys_active(key_map);
781 for (i=total_keylength=num_keys=0 ; i < share->base.keys ; i++)
783 if (! (key[i].flag & HA_NOSAME) && (share->base.auto_key != i + 1) &&
784 mi_is_key_active(share->state.key_map, i))
787 mi_set_key_active(key_map, i);
788 total_keylength+=key[i].maxlength+TREE_ELEMENT_EXTRA_SIZE;
793 num_keys * MI_MIN_SIZE_BULK_INSERT_TREE > cache_size)
796 if (rows && rows*total_keylength < cache_size)
797 cache_size= (uint32_t)rows;
799 cache_size/=total_keylength*16;
801 info->bulk_insert=(
Tree *) malloc((
sizeof(
Tree)*share->base.keys+
804 if (!info->bulk_insert)
805 return(HA_ERR_OUT_OF_MEM);
808 for (i=0 ; i < share->base.keys ; i++)
810 if (mi_is_key_active(key_map, i))
815 info->bulk_insert[i].
init_tree(cache_size * key[i].maxlength,
816 cache_size * key[i].maxlength, 0,
817 (qsort_cmp2)keys_compare,
false,
818 (tree_element_free) keys_free, (
void *)params++);
821 info->bulk_insert[i].setRoot(0);
827 void mi_flush_bulk_insert(
MI_INFO *info, uint32_t inx)
829 if (info->bulk_insert)
831 if (info->bulk_insert[inx].is_inited())
832 info->bulk_insert[inx].reset_tree();
836 void mi_end_bulk_insert(
MI_INFO *info)
838 if (info->bulk_insert)
841 for (i=0 ; i < info->s->base.keys ; i++)
843 if (info->bulk_insert[i].is_inited())
845 info->bulk_insert[i].delete_tree();
848 free((
void *)info->bulk_insert);
void init_tree(size_t default_alloc_size, uint32_t memory_limit, uint32_t size, qsort_cmp2 compare, bool with_delete, tree_element_free free_element, void *custom_arg)