18 #include "myisam_priv.h"
19 #include <drizzled/charset.h>
20 #include <drizzled/internal/m_string.h>
21 #include <drizzled/util/test.h>
23 using namespace drizzled;
25 static bool _mi_get_prev_key(
MI_INFO *info,
MI_KEYDEF *keyinfo,
unsigned char *page,
26 unsigned char *key,
unsigned char *keypos,
27 uint32_t *return_key_length);
31 int _mi_check_index(
MI_INFO *info,
int inx)
35 if (inx < 0 || ! mi_is_key_active(info->s->state.key_map, inx))
37 errno=HA_ERR_WRONG_INDEX;
40 if (info->lastinx != inx)
44 info->update= ((info->update & (HA_STATE_CHANGED | HA_STATE_ROW_CHANGED)) |
45 HA_STATE_NEXT_FOUND | HA_STATE_PREV_FOUND);
47 if (info->opt_flag & WRITE_CACHE_USED && info->rec_cache.flush())
61 unsigned char *key, uint32_t key_len, uint32_t nextflag,
register internal::my_off_t pos)
66 unsigned char *keypos,*maxpos;
67 unsigned char lastkey[MI_MAX_KEY_BUFF],*buff;
69 if (pos == HA_OFFSET_ERROR)
71 errno=HA_ERR_KEY_NOT_FOUND;
72 info->lastpos= HA_OFFSET_ERROR;
73 if (!(nextflag & (SEARCH_SMALLER | SEARCH_BIGGER | SEARCH_LAST)))
78 if (!(buff=_mi_fetch_keypage(info,keyinfo,pos,DFLT_INIT_HITS,info->buff,
79 test(!(nextflag & SEARCH_SAVE_BUFF)))))
82 flag=(*keyinfo->bin_search)(info,keyinfo,buff,key,key_len,nextflag,
83 &keypos,lastkey, &last_key);
84 if (flag == MI_FOUND_WRONG_KEY)
86 nod_flag=mi_test_if_nod(buff);
87 maxpos=buff+mi_getint(buff)-1;
91 if ((error=_mi_search(info,keyinfo,key,key_len,nextflag,
92 _mi_kpos(nod_flag,keypos))) <= 0)
97 if (nextflag & (SEARCH_SMALLER | SEARCH_LAST) &&
98 keypos == buff+2+nod_flag)
101 else if (nextflag & SEARCH_BIGGER && keypos >= maxpos)
106 if ((nextflag & SEARCH_FIND) && nod_flag &&
107 ((keyinfo->flag & (HA_NOSAME | HA_NULL_PART)) != HA_NOSAME ||
108 key_len != USE_WHOLE_KEY))
110 if ((error=_mi_search(info,keyinfo,key,key_len,SEARCH_FIND,
111 _mi_kpos(nod_flag,keypos))) >= 0 ||
112 errno != HA_ERR_KEY_NOT_FOUND)
114 info->last_keypage= HA_OFFSET_ERROR;
117 if (pos != info->last_keypage)
119 unsigned char *old_buff=buff;
120 if (!(buff=_mi_fetch_keypage(info,keyinfo,pos,DFLT_INIT_HITS,info->buff,
121 test(!(nextflag & SEARCH_SAVE_BUFF)))))
123 keypos=buff+(keypos-old_buff);
124 maxpos=buff+(maxpos-old_buff);
127 if ((nextflag & (SEARCH_SMALLER | SEARCH_LAST)) && flag != 0)
129 uint32_t not_used[2];
130 if (_mi_get_prev_key(info,keyinfo, buff, info->lastkey, keypos,
131 &info->lastkey_length))
133 if (!(nextflag & SEARCH_SMALLER) &&
134 ha_key_cmp(keyinfo->seg, info->lastkey, key, key_len, SEARCH_FIND,
137 errno=HA_ERR_KEY_NOT_FOUND;
143 info->lastkey_length=(*keyinfo->get_key)(keyinfo,nod_flag,&keypos,lastkey);
144 if (!info->lastkey_length)
146 memcpy(info->lastkey,lastkey,info->lastkey_length);
148 info->lastpos=_mi_dpos(info,0,info->lastkey+info->lastkey_length);
150 info->int_keypos=info->buff+ (keypos-buff);
151 info->int_maxpos=info->buff+ (maxpos-buff);
152 info->int_nod_flag=nod_flag;
153 info->int_keytree_version=keyinfo->version;
154 info->last_search_keypage=info->last_keypage;
155 info->page_changed=0;
156 info->buff_used= (info->buff != buff);
161 info->lastpos= HA_OFFSET_ERROR;
162 info->page_changed=1;
172 int _mi_bin_search(
MI_INFO *info,
register MI_KEYDEF *keyinfo,
unsigned char *page,
173 unsigned char *key, uint32_t key_len, uint32_t comp_flag,
unsigned char **ret_pos,
174 unsigned char *buff,
bool *last_key)
177 register int start,mid,end,save_end;
179 uint32_t totlength,nod_flag,not_used[2];
181 totlength=keyinfo->keylength+(nod_flag=mi_test_if_nod(page));
183 save_end=end=(int) ((mi_getint(page)-2-nod_flag)/totlength-1);
189 if ((flag=ha_key_cmp(keyinfo->seg,page+(uint) mid*totlength,key,key_len,
190 comp_flag, not_used))
197 flag=ha_key_cmp(keyinfo->seg,page+(uint) start*totlength,key,key_len,
198 comp_flag, not_used);
201 *ret_pos=page+(uint) start*totlength;
202 *last_key= end == save_end;
233 int _mi_seq_search(
MI_INFO *info,
register MI_KEYDEF *keyinfo,
unsigned char *page,
234 unsigned char *key, uint32_t key_len, uint32_t comp_flag,
unsigned char **ret_pos,
235 unsigned char *buff,
bool *last_key)
238 uint32_t nod_flag,length=0,not_used[2];
239 unsigned char t_buff[MI_MAX_KEY_BUFF],*end;
241 end= page+mi_getint(page);
242 nod_flag=mi_test_if_nod(page);
248 length=(*keyinfo->get_key)(keyinfo,nod_flag,&page,t_buff);
249 if (length == 0 || page > end)
251 mi_print_error(info->s, HA_ERR_CRASHED);
252 errno=HA_ERR_CRASHED;
253 return(MI_FOUND_WRONG_KEY);
255 if ((flag=ha_key_cmp(keyinfo->seg,t_buff,key,key_len,comp_flag,
258 memcpy(buff,t_buff,length);
262 memcpy(buff,t_buff,length);
263 *last_key= page == end;
268 int _mi_prefix_search(
MI_INFO *info,
register MI_KEYDEF *keyinfo,
unsigned char *page,
269 unsigned char *key, uint32_t key_len, uint32_t nextflag,
unsigned char **ret_pos,
270 unsigned char *buff,
bool *last_key)
277 int flag=0, my_flag=-1;
278 uint32_t nod_flag, length=0, len, matched, cmplen, kseg_len;
279 uint32_t prefix_len=0,suffix_len;
280 int key_len_skip, seg_len_pack=0, key_len_left;
281 unsigned char *end, *kseg, *vseg;
282 unsigned char *sort_order=keyinfo->seg->charset->sort_order;
283 unsigned char tt_buff[MI_MAX_KEY_BUFF+2], *t_buff=tt_buff+2;
284 unsigned char *saved_from=NULL, *saved_to=NULL, *saved_vseg=NULL;
285 uint32_t saved_length=0, saved_prefix_len=0;
286 uint32_t length_pack;
290 end= page+mi_getint(page);
291 nod_flag=mi_test_if_nod(page);
296 get_key_pack_length(kseg_len,length_pack,kseg);
297 key_len_skip=length_pack+kseg_len;
298 key_len_left=(int) key_len- (
int) key_len_skip;
300 cmplen=(key_len_left>=0) ? kseg_len : key_len-length_pack;
320 uint32_t packed= *page & 128;
323 if (keyinfo->seg->length >= 127)
325 suffix_len=mi_uint2korr(vseg) & 32767;
329 suffix_len= *vseg++ & 127;
341 prefix_len=suffix_len;
342 get_key_length(suffix_len,vseg);
351 len=prefix_len+suffix_len;
352 seg_len_pack=get_pack_length(len);
353 t_buff=tt_buff+3-seg_len_pack;
354 store_key_length(t_buff,len);
356 if (prefix_len > saved_prefix_len)
357 memcpy(t_buff+seg_len_pack+saved_prefix_len,saved_vseg,
358 prefix_len-saved_prefix_len);
360 saved_prefix_len=prefix_len;
363 unsigned char *from=vseg+suffix_len;
367 for (keyseg=keyinfo->seg+1 ; keyseg->type ; keyseg++ )
370 if (keyseg->flag & HA_NULL_PART)
375 if (keyseg->flag & (HA_VAR_LENGTH_PART | HA_BLOB_PART | HA_SPACE_PACK))
377 get_key_length(l,from);
384 from+=keyseg->length;
391 mi_print_error(info->s, HA_ERR_CRASHED);
392 errno=HA_ERR_CRASHED;
393 return(MI_FOUND_WRONG_KEY);
396 if (matched >= prefix_len)
400 unsigned char *k=kseg+prefix_len;
406 left= ((len <= cmplen) ? suffix_len :
407 ((prefix_len < cmplen) ? cmplen - prefix_len : 0));
409 matched=prefix_len+left;
413 for (my_flag=0;left;left--)
414 if ((my_flag= (
int) sort_order[*vseg++] - (int) sort_order[*k++]))
419 for (my_flag=0;left;left--)
420 if ((my_flag= (
int) *vseg++ - (int) *k++))
439 if ((keyinfo->seg->type != HA_KEYTYPE_TEXT &&
440 keyinfo->seg->type != HA_KEYTYPE_VARTEXT1 &&
441 keyinfo->seg->type != HA_KEYTYPE_VARTEXT2))
446 unsigned char *k_end= k+ (cmplen - len);
447 for ( ; k < k_end && *k ==
' '; k++) ;
450 if (*k < (
unsigned char)
' ')
458 else if (len > cmplen)
460 unsigned char *vseg_end;
461 if ((nextflag & SEARCH_PREFIX) && key_len_left == 0)
465 for (vseg_end= vseg + (len-cmplen) ;
466 vseg < vseg_end && *vseg == (
unsigned char)
' ';
468 assert(vseg < vseg_end);
470 if (*vseg > (
unsigned char)
' ')
482 uint32_t not_used[2];
483 if ((flag = ha_key_cmp(keyinfo->seg+1,vseg,
484 k, key_len_left, nextflag, not_used)) >= 0)
495 if (nextflag & (SEARCH_NO_FIND | SEARCH_LAST))
496 flag=(nextflag & (SEARCH_BIGGER | SEARCH_LAST)) ? -1 : 1;
506 memcpy(buff,t_buff,saved_length=seg_len_pack+prefix_len);
507 saved_to=buff+saved_length;
508 saved_from=saved_vseg;
513 flag=(keyinfo->seg->flag & HA_REVERSE_SORT) ? -my_flag : my_flag;
516 memcpy(buff,t_buff,saved_length=seg_len_pack+prefix_len);
517 saved_to=buff+saved_length;
518 saved_from=saved_vseg;
522 memcpy(saved_to,saved_from,saved_length);
524 *last_key= page == end;
532 internal::my_off_t _mi_kpos(uint32_t nod_flag,
unsigned char *after_key)
538 return mi_uint7korr(after_key)*MI_MIN_KEY_BLOCK_LENGTH;
540 return mi_uint6korr(after_key)*MI_MIN_KEY_BLOCK_LENGTH;
542 return mi_uint5korr(after_key)*MI_MIN_KEY_BLOCK_LENGTH;
552 return ((internal::my_off_t) mi_uint4korr(after_key))*MI_MIN_KEY_BLOCK_LENGTH;
554 return ((internal::my_off_t) mi_uint3korr(after_key))*MI_MIN_KEY_BLOCK_LENGTH;
556 return (internal::my_off_t) (mi_uint2korr(after_key)*MI_MIN_KEY_BLOCK_LENGTH);
558 return (uint) (*after_key)*MI_MIN_KEY_BLOCK_LENGTH;
561 return(HA_OFFSET_ERROR);
568 void _mi_kpointer(
register MI_INFO *info,
register unsigned char *buff, internal::my_off_t pos)
570 pos/=MI_MIN_KEY_BLOCK_LENGTH;
571 switch (info->s->base.key_reflength) {
573 case 7: mi_int7store(buff,pos);
break;
574 case 6: mi_int6store(buff,pos);
break;
575 case 5: mi_int5store(buff,pos);
break;
584 case 4: mi_int4store(buff,pos);
break;
585 case 3: mi_int3store(buff,pos);
break;
586 case 2: mi_int2store(buff,(uint) pos);
break;
587 case 1: buff[0]= (
unsigned char) pos;
break;
596 internal::my_off_t _mi_dpos(
MI_INFO *info, uint32_t nod_flag,
unsigned char *after_key)
598 internal::my_off_t pos;
599 after_key-=(nod_flag + info->s->rec_reflength);
600 switch (info->s->rec_reflength) {
602 case 8: pos= (internal::my_off_t) mi_uint8korr(after_key);
break;
603 case 7: pos= (internal::my_off_t) mi_uint7korr(after_key);
break;
604 case 6: pos= (internal::my_off_t) mi_uint6korr(after_key);
break;
605 case 5: pos= (internal::my_off_t) mi_uint5korr(after_key);
break;
607 case 8: pos= (internal::my_off_t) mi_uint4korr(after_key+4);
break;
608 case 7: pos= (internal::my_off_t) mi_uint4korr(after_key+3);
break;
609 case 6: pos= (internal::my_off_t) mi_uint4korr(after_key+2);
break;
610 case 5: pos= (internal::my_off_t) mi_uint4korr(after_key+1);
break;
612 case 4: pos= (internal::my_off_t) mi_uint4korr(after_key);
break;
613 case 3: pos= (internal::my_off_t) mi_uint3korr(after_key);
break;
614 case 2: pos= (internal::my_off_t) mi_uint2korr(after_key);
break;
618 return (info->s->options &
619 (HA_OPTION_PACK_RECORD | HA_OPTION_COMPRESS_RECORD)) ? pos :
620 pos*info->s->base.pack_reclength;
626 internal::my_off_t _mi_rec_pos(
MYISAM_SHARE *s,
unsigned char *ptr)
628 internal::my_off_t pos;
629 switch (s->rec_reflength) {
632 pos= (internal::my_off_t) mi_uint8korr(ptr);
633 if (pos == HA_OFFSET_ERROR)
634 return HA_OFFSET_ERROR;
637 pos= (internal::my_off_t) mi_uint7korr(ptr);
638 if (pos == (((internal::my_off_t) 1) << 56) -1)
639 return HA_OFFSET_ERROR;
642 pos= (internal::my_off_t) mi_uint6korr(ptr);
643 if (pos == (((internal::my_off_t) 1) << 48) -1)
644 return HA_OFFSET_ERROR;
647 pos= (internal::my_off_t) mi_uint5korr(ptr);
648 if (pos == (((internal::my_off_t) 1) << 40) -1)
649 return HA_OFFSET_ERROR;
656 ptr+= (s->rec_reflength-4);
660 pos= (internal::my_off_t) mi_uint4korr(ptr);
661 if (pos == (internal::my_off_t) UINT32_MAX)
662 return HA_OFFSET_ERROR;
665 pos= (internal::my_off_t) mi_uint3korr(ptr);
666 if (pos == (internal::my_off_t) (1 << 24) -1)
667 return HA_OFFSET_ERROR;
670 pos= (internal::my_off_t) mi_uint2korr(ptr);
671 if (pos == (internal::my_off_t) (1 << 16) -1)
672 return HA_OFFSET_ERROR;
676 return ((s->options &
677 (HA_OPTION_PACK_RECORD | HA_OPTION_COMPRESS_RECORD)) ? pos :
678 pos*s->base.pack_reclength);
684 void _mi_dpointer(
MI_INFO *info,
unsigned char *buff, internal::my_off_t pos)
686 if (!(info->s->options &
687 (HA_OPTION_PACK_RECORD | HA_OPTION_COMPRESS_RECORD)) &&
688 pos != HA_OFFSET_ERROR)
689 pos/=info->s->base.pack_reclength;
691 switch (info->s->rec_reflength) {
693 case 8: mi_int8store(buff,pos);
break;
694 case 7: mi_int7store(buff,pos);
break;
695 case 6: mi_int6store(buff,pos);
break;
696 case 5: mi_int5store(buff,pos);
break;
707 case 4: mi_int4store(buff,pos);
break;
708 case 3: mi_int3store(buff,pos);
break;
709 case 2: mi_int2store(buff,(uint) pos);
break;
723 uint32_t _mi_get_static_key(
register MI_KEYDEF *keyinfo, uint32_t nod_flag,
724 register unsigned char **page,
register unsigned char *key)
726 memcpy(key, *page, keyinfo->keylength+nod_flag);
727 *page+=keyinfo->keylength+nod_flag;
728 return(keyinfo->keylength);
746 uint32_t _mi_get_pack_key(
register MI_KEYDEF *keyinfo, uint32_t nod_flag,
747 register unsigned char **page_pos,
register unsigned char *key)
750 unsigned char *start_key,*page=*page_pos;
754 for (keyseg=keyinfo->seg ; keyseg->type ;keyseg++)
756 if (keyseg->flag & HA_PACK_KEY)
759 unsigned char *start=key;
760 uint32_t packed= *page & 128,tot_length,rest_length;
761 if (keyseg->length >= 127)
763 length=mi_uint2korr(page) & 32767;
767 length= *page++ & 127;
771 if (length > (uint) keyseg->length)
773 mi_print_error(keyinfo->share, HA_ERR_CRASHED);
774 errno=HA_ERR_CRASHED;
779 if (keyseg->flag & HA_NULL_PART)
781 get_key_length(length,key);
783 if (length > keyseg->length)
785 mi_print_error(keyinfo->share, HA_ERR_CRASHED);
786 errno=HA_ERR_CRASHED;
791 if (keyseg->flag & HA_NULL_PART)
797 get_key_length(rest_length,page);
798 tot_length=rest_length+length;
801 if (tot_length >= 255 && *start != 255)
804 internal::bmove_upp(key+length+3, key+length+1, length);
806 mi_int2store(key+1,tot_length);
809 else if (tot_length < 255 && *start == 255)
811 memmove(key+1,key+3,length);
817 store_key_length_inc(key,tot_length);
820 memcpy(key,page,rest_length);
827 if (keyseg->flag & HA_NULL_PART)
837 if (length > (uint) keyseg->length)
839 mi_print_error(keyinfo->share, HA_ERR_CRASHED);
840 errno=HA_ERR_CRASHED;
843 store_key_length_inc(key,length);
847 if (keyseg->flag & HA_NULL_PART)
849 if (!(*key++ = *page++))
853 (HA_VAR_LENGTH_PART | HA_BLOB_PART | HA_SPACE_PACK))
855 unsigned char *tmp=page;
856 get_key_length(length,tmp);
857 length+=(uint) (tmp-page);
860 length=keyseg->length;
862 memcpy(key, page, length);
866 length=keyseg->length+nod_flag;
867 memmove(key,page,length);
868 *page_pos= page+length;
869 return ((uint) (key-start_key)+keyseg->length);
876 uint32_t _mi_get_binary_pack_key(
register MI_KEYDEF *keyinfo, uint32_t nod_flag,
877 register unsigned char **page_pos,
register unsigned char *key)
880 unsigned char *start_key,*page,*page_end,*from,*from_end;
884 page_end=page+MI_MAX_KEY_BUFF+1;
901 get_key_length(length,page);
904 if (length > keyinfo->maxlength)
906 mi_print_error(keyinfo->share, HA_ERR_CRASHED);
907 errno=HA_ERR_CRASHED;
912 from_end= key + length;
928 for (keyseg=keyinfo->seg ; keyseg->type ;keyseg++)
930 if (keyseg->flag & HA_NULL_PART)
933 if (from == from_end) { from=page; from_end=page_end; }
934 if (!(*key++ = *from++))
937 if (keyseg->flag & (HA_VAR_LENGTH_PART | HA_BLOB_PART | HA_SPACE_PACK))
940 if (from == from_end) { from=page; from_end=page_end; }
942 if ((length= (*key++ = *from++)) == 255)
945 if (from == from_end) { from=page; from_end=page_end; }
946 length= (uint) ((*key++ = *from++)) << 8;
948 if (from == from_end) { from=page; from_end=page_end; }
949 length+= (uint) ((*key++ = *from++));
953 length=keyseg->length;
955 if ((tmp=(uint) (from_end-from)) <= length)
959 from=page; from_end=page_end;
961 memmove(key, from, length);
970 length=keyseg->length+nod_flag;
971 if ((tmp=(uint) (from_end-from)) <= length)
974 memcpy(key+tmp,page,length-tmp);
975 *page_pos= page+length-tmp;
985 if (from_end != page_end)
987 mi_print_error(keyinfo->share, HA_ERR_CRASHED);
988 errno=HA_ERR_CRASHED;
992 memcpy(key, from, length);
993 *page_pos= from+length;
995 return((uint) (key-start_key)+keyseg->length);
1002 unsigned char *_mi_get_key(
MI_INFO *info,
MI_KEYDEF *keyinfo,
unsigned char *page,
1003 unsigned char *key,
unsigned char *keypos, uint32_t *return_key_length)
1007 nod_flag=mi_test_if_nod(page);
1008 if (! (keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)))
1010 memmove(key,keypos,keyinfo->keylength+nod_flag);
1011 return(keypos+keyinfo->keylength+nod_flag);
1017 while (page <= keypos)
1019 *return_key_length=(*keyinfo->get_key)(keyinfo,nod_flag,&page,key);
1020 if (*return_key_length == 0)
1022 mi_print_error(info->s, HA_ERR_CRASHED);
1023 errno=HA_ERR_CRASHED;
1035 static bool _mi_get_prev_key(
MI_INFO *info,
MI_KEYDEF *keyinfo,
unsigned char *page,
1036 unsigned char *key,
unsigned char *keypos,
1037 uint32_t *return_key_length)
1041 nod_flag=mi_test_if_nod(page);
1042 if (! (keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)))
1044 *return_key_length=keyinfo->keylength;
1045 memmove(key, keypos - *return_key_length-nod_flag, *return_key_length);
1052 while (page < keypos)
1054 *return_key_length=(*keyinfo->get_key)(keyinfo,nod_flag,&page,key);
1055 if (*return_key_length == 0)
1057 mi_print_error(info->s, HA_ERR_CRASHED);
1058 errno=HA_ERR_CRASHED;
1071 unsigned char *_mi_get_last_key(
MI_INFO *info,
MI_KEYDEF *keyinfo,
unsigned char *page,
1072 unsigned char *lastkey,
unsigned char *endpos, uint32_t *return_key_length)
1075 unsigned char *lastpos;
1077 nod_flag=mi_test_if_nod(page);
1078 if (! (keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)))
1080 lastpos=endpos-keyinfo->keylength-nod_flag;
1081 *return_key_length=keyinfo->keylength;
1083 memmove(lastkey,lastpos,keyinfo->keylength+nod_flag);
1087 lastpos=(page+=2+nod_flag);
1089 while (page < endpos)
1092 *return_key_length=(*keyinfo->get_key)(keyinfo,nod_flag,&page,lastkey);
1093 if (*return_key_length == 0)
1095 mi_print_error(info->s, HA_ERR_CRASHED);
1096 errno=HA_ERR_CRASHED;
1107 uint32_t _mi_keylength(
MI_KEYDEF *keyinfo,
register unsigned char *key)
1110 unsigned char *start;
1112 if (! (keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)))
1113 return (keyinfo->keylength);
1116 for (keyseg=keyinfo->seg ; keyseg->type ; keyseg++)
1118 if (keyseg->flag & HA_NULL_PART)
1121 if (keyseg->flag & (HA_SPACE_PACK | HA_BLOB_PART | HA_VAR_LENGTH_PART))
1124 get_key_length(length,key);
1128 key+= keyseg->length;
1130 return((uint) (key-start)+keyseg->length);
1142 uint32_t _mi_keylength_part(
MI_KEYDEF *keyinfo,
register unsigned char *key,
1146 unsigned char *start= key;
1148 for (keyseg=keyinfo->seg ; keyseg != end ; keyseg++)
1150 if (keyseg->flag & HA_NULL_PART)
1153 if (keyseg->flag & (HA_SPACE_PACK | HA_BLOB_PART | HA_VAR_LENGTH_PART))
1156 get_key_length(length,key);
1160 key+= keyseg->length;
1162 return (uint) (key-start);
1167 unsigned char *_mi_move_key(
MI_KEYDEF *keyinfo,
unsigned char *to,
unsigned char *from)
1169 register uint32_t length;
1170 length= _mi_keylength(keyinfo, from);
1171 memcpy(to, from, length);
1179 unsigned char *key, uint32_t key_length, uint32_t nextflag, internal::my_off_t pos)
1183 unsigned char lastkey[MI_MAX_KEY_BUFF];
1192 if (((nextflag & SEARCH_BIGGER) && info->int_keypos >= info->int_maxpos) ||
1193 info->page_changed ||
1194 (info->int_keytree_version != keyinfo->version &&
1195 (info->int_nod_flag || info->buff_used)))
1196 return(_mi_search(info,keyinfo,key, USE_WHOLE_KEY,
1197 nextflag | SEARCH_SAVE_BUFF, pos));
1199 if (info->buff_used)
1201 if (!_mi_fetch_keypage(info,keyinfo,info->last_search_keypage,
1202 DFLT_INIT_HITS,info->buff,0))
1208 nod_flag=mi_test_if_nod(info->buff);
1210 if (nextflag & SEARCH_BIGGER)
1212 internal::my_off_t tmp_pos=_mi_kpos(nod_flag,info->int_keypos);
1213 if (tmp_pos != HA_OFFSET_ERROR)
1215 if ((error=_mi_search(info,keyinfo,key, USE_WHOLE_KEY,
1216 nextflag | SEARCH_SAVE_BUFF, tmp_pos)) <=0)
1219 memcpy(lastkey,key,key_length);
1220 if (!(info->lastkey_length=(*keyinfo->get_key)(keyinfo,nod_flag,
1221 &info->int_keypos,lastkey)))
1228 info->int_keypos=_mi_get_last_key(info,keyinfo,info->buff,lastkey,
1229 info->int_keypos, &length);
1230 if (!info->int_keypos)
1232 if (info->int_keypos == info->buff+2)
1233 return(_mi_search(info,keyinfo,key, USE_WHOLE_KEY,
1234 nextflag | SEARCH_SAVE_BUFF, pos));
1235 if ((error=_mi_search(info,keyinfo,key, USE_WHOLE_KEY,
1236 nextflag | SEARCH_SAVE_BUFF,
1237 _mi_kpos(nod_flag,info->int_keypos))) <= 0)
1241 if (! _mi_get_last_key(info,keyinfo,info->buff,lastkey,
1242 info->int_keypos,&info->lastkey_length))
1245 memcpy(info->lastkey,lastkey,info->lastkey_length);
1246 info->lastpos=_mi_dpos(info,0,info->lastkey+info->lastkey_length);
1255 register internal::my_off_t pos)
1258 unsigned char *page;
1260 if (pos == HA_OFFSET_ERROR)
1262 errno=HA_ERR_KEY_NOT_FOUND;
1263 info->lastpos= HA_OFFSET_ERROR;
1269 if (!_mi_fetch_keypage(info,keyinfo,pos,DFLT_INIT_HITS,info->buff,0))
1271 info->lastpos= HA_OFFSET_ERROR;
1274 nod_flag=mi_test_if_nod(info->buff);
1275 page=info->buff+2+nod_flag;
1276 }
while ((pos=_mi_kpos(nod_flag,page)) != HA_OFFSET_ERROR);
1278 if (!(info->lastkey_length=(*keyinfo->get_key)(keyinfo,nod_flag,&page,
1282 info->int_keypos=page; info->int_maxpos=info->buff+mi_getint(info->buff)-1;
1283 info->int_nod_flag=nod_flag;
1284 info->int_keytree_version=keyinfo->version;
1285 info->last_search_keypage=info->last_keypage;
1286 info->page_changed=info->buff_used=0;
1287 info->lastpos=_mi_dpos(info,0,info->lastkey+info->lastkey_length);
1297 register internal::my_off_t pos)
1300 unsigned char *buff,*page;
1302 if (pos == HA_OFFSET_ERROR)
1304 errno=HA_ERR_KEY_NOT_FOUND;
1305 info->lastpos= HA_OFFSET_ERROR;
1312 if (!_mi_fetch_keypage(info,keyinfo,pos,DFLT_INIT_HITS,buff,0))
1314 info->lastpos= HA_OFFSET_ERROR;
1317 page= buff+mi_getint(buff);
1318 nod_flag=mi_test_if_nod(buff);
1319 }
while ((pos=_mi_kpos(nod_flag,page)) != HA_OFFSET_ERROR);
1321 if (!_mi_get_last_key(info,keyinfo,buff,info->lastkey,page,
1322 &info->lastkey_length))
1324 info->lastpos=_mi_dpos(info,0,info->lastkey+info->lastkey_length);
1325 info->int_keypos=info->int_maxpos=page;
1326 info->int_nod_flag=nod_flag;
1327 info->int_keytree_version=keyinfo->version;
1328 info->last_search_keypage=info->last_keypage;
1329 info->page_changed=info->buff_used=0;
1352 _mi_calc_static_key_length(
MI_KEYDEF *keyinfo,uint32_t nod_flag,
1353 unsigned char *next_pos,
1354 unsigned char *org_key,
1355 unsigned char *prev_key,
1362 return (
int) (s_temp->totlength=keyinfo->keylength+nod_flag);
1368 _mi_calc_var_key_length(
MI_KEYDEF *keyinfo,uint32_t nod_flag,
1369 unsigned char *next_pos,
1370 unsigned char *org_key,
1371 unsigned char *prev_key,
1378 return (
int) (s_temp->totlength=_mi_keylength(keyinfo,key)+nod_flag);
1401 _mi_calc_var_pack_key_length(
MI_KEYDEF *keyinfo,uint32_t nod_flag,
1402 unsigned char *next_key,
1403 unsigned char *org_key,
1404 unsigned char *prev_key,
1410 uint32_t key_length,ref_length,org_key_length=0,
1411 length_pack,new_key_length,diff_flag,pack_marker;
1412 unsigned char *start,*end,*key_end,*sort_order;
1415 length_pack=s_temp->ref_length=s_temp->n_ref_length=s_temp->n_length=0;
1416 same_length=0; keyseg=keyinfo->seg;
1417 key_length=_mi_keylength(keyinfo,key)+nod_flag;
1422 if (keyseg->length >= 127)
1432 s_temp->pack_marker=pack_marker;
1435 if (keyseg->flag & HA_NULL_PART)
1440 s_temp->key_length= 0;
1441 s_temp->totlength=key_length-1+diff_flag;
1442 s_temp->next_key_pos=0;
1443 return (s_temp->totlength);
1445 s_temp->store_not_null=1;
1447 if (prev_key && !*prev_key++)
1453 s_temp->store_not_null=0;
1454 s_temp->prev_key=org_key;
1458 get_key_pack_length(new_key_length,length_pack,key);
1459 end=key_end= key+ new_key_length;
1465 get_key_length(org_key_length,prev_key);
1466 s_temp->prev_key=prev_key;
1468 if (new_key_length && new_key_length == org_key_length)
1470 else if (new_key_length > org_key_length)
1471 end=key + org_key_length;
1475 while (key < end && sort_order[*key] == sort_order[*prev_key])
1482 while (key < end && *key == *prev_key)
1490 s_temp->key_length= (uint) (key_end-key);
1492 if (same_length && key == key_end)
1495 s_temp->ref_length= pack_marker;
1496 length=(int) key_length-(
int) (key_end-start)-length_pack;
1500 s_temp->n_length= *next_key;
1508 ref_length= (uint) (key-start);
1509 s_temp->ref_length= ref_length + pack_marker;
1510 length= (int) (key_length - ref_length);
1512 length-= length_pack;
1514 length+= ((new_key_length-ref_length) >= 255) ? 3 : 1;
1518 s_temp->key_length+=s_temp->store_not_null;
1519 length= key_length - length_pack+ diff_flag;
1522 s_temp->totlength=(uint) length;
1523 s_temp->prev_length=0;
1526 if ((s_temp->next_key_pos=next_key))
1528 uint32_t packed,n_length;
1530 packed = *next_key & 128;
1533 n_length= mi_uint2korr(next_key) & 32767;
1537 n_length= *next_key++ & 127;
1539 n_length-= s_temp->store_not_null;
1541 if (n_length || packed)
1543 uint32_t next_length_pack, new_ref_length=s_temp->ref_length;
1548 if (!prev_key && org_key)
1550 get_key_length(org_key_length,org_key);
1554 while (key < end && sort_order[*key] == sort_order[*org_key])
1561 while (key < end && *key == *org_key)
1566 if ((new_ref_length= (uint) (key - start)))
1567 new_ref_length+=pack_marker;
1578 s_temp->part_of_prev_key= new_ref_length;
1579 s_temp->prev_length= org_key_length -
1580 (new_ref_length-pack_marker);
1581 s_temp->n_ref_length= s_temp->part_of_prev_key;
1582 s_temp->n_length= s_temp->prev_length;
1583 n_length= get_pack_length(s_temp->prev_length);
1584 s_temp->prev_key+= (new_ref_length - pack_marker);
1585 length+= s_temp->prev_length + n_length;
1589 s_temp->part_of_prev_key=0;
1590 s_temp->prev_length= org_key_length;
1591 s_temp->n_ref_length=s_temp->n_length= org_key_length;
1592 length+= org_key_length;
1594 return (
int) length;
1597 ref_length=n_length;
1599 get_key_pack_length(n_length,next_length_pack,next_key);
1602 if (!new_ref_length)
1604 s_temp->part_of_prev_key= 0;
1605 s_temp->prev_length= ref_length;
1606 s_temp->n_ref_length= s_temp->n_length= n_length+ref_length;
1607 return (
int) length+ref_length-next_length_pack;
1609 if (ref_length+pack_marker > new_ref_length)
1611 uint32_t new_pack_length=new_ref_length-pack_marker;
1613 s_temp->part_of_prev_key= new_ref_length;
1614 s_temp->prev_length= ref_length - new_pack_length;
1615 s_temp->n_ref_length=s_temp->n_length=n_length + s_temp->prev_length;
1616 s_temp->prev_key+= new_pack_length;
1617 length-= (next_length_pack - get_pack_length(s_temp->n_length));
1618 return (
int) length + s_temp->prev_length;
1629 uint32_t tmp_length;
1630 key=(start+=ref_length);
1631 if (key+n_length < key_end)
1632 key_end=key+n_length;
1635 while (key < key_end && sort_order[*key] ==
1636 sort_order[*next_key])
1643 while (key < key_end && *key == *next_key)
1648 if (!(tmp_length=(uint) (key-start)))
1650 s_temp->next_key_pos=0;
1653 ref_length+=tmp_length;
1654 n_length-=tmp_length;
1655 length-=tmp_length+next_length_pack;
1657 if (n_length == 0 && ref_length == new_key_length)
1659 s_temp->n_ref_length=pack_marker;
1663 s_temp->n_ref_length=ref_length | pack_marker;
1664 length+= get_pack_length(n_length);
1665 s_temp->n_length=n_length;
1676 _mi_calc_bin_pack_key_length(
MI_KEYDEF *keyinfo,uint32_t nod_flag,
unsigned char *next_key,
1677 unsigned char *org_key,
unsigned char *prev_key,
unsigned char *key,
1680 uint32_t length,key_length,ref_length;
1682 s_temp->totlength=key_length=_mi_keylength(keyinfo,key)+nod_flag;
1683 #ifdef HAVE_VALGRIND
1684 s_temp->n_length= s_temp->n_ref_length=0;
1687 s_temp->prev_key=org_key;
1697 for ( ; *key == *prev_key && key < end; key++,prev_key++) ;
1698 s_temp->ref_length= ref_length=(uint) (key-s_temp->key);
1699 length=key_length - ref_length + get_pack_length(ref_length);
1704 s_temp->ref_length=ref_length=0;
1705 length=key_length+1;
1707 if ((s_temp->next_key_pos=next_key))
1710 uint32_t next_length,next_length_pack;
1711 get_key_pack_length(next_length,next_length_pack,next_key);
1714 if (!prev_key && org_key && next_length)
1717 for (key= s_temp->key, end=key+next_length ;
1718 *key == *org_key && key < end;
1720 ref_length= (uint) (key - s_temp->key);
1723 if (next_length > ref_length)
1728 s_temp->n_ref_length= ref_length;
1729 s_temp->prev_length= next_length-ref_length;
1730 s_temp->prev_key+= ref_length;
1731 return (
int) (length+ s_temp->prev_length - next_length_pack +
1732 get_pack_length(ref_length));
1735 key= s_temp->key+next_length;
1736 while (*key++ == *next_key++) ;
1737 if ((ref_length= (uint) (key - s_temp->key)-1) == next_length)
1739 s_temp->next_key_pos=0;
1742 s_temp->prev_length=0;
1743 s_temp->n_ref_length=ref_length;
1744 return (
int) (length-(ref_length - next_length) - next_length_pack +
1745 get_pack_length(ref_length));
1747 return (
int) length;
1757 void _mi_store_static_key(
MI_KEYDEF *keyinfo,
1758 register unsigned char *key_pos,
1762 memcpy(key_pos, s_temp->key, s_temp->totlength);
1768 #define store_pack_length(test,pos,length) { \
1769 if (test) { *((pos)++) = (unsigned char) (length); } else \
1770 { *((pos)++) = (unsigned char) ((length) >> 8); *((pos)++) = (unsigned char) (length); } }
1773 void _mi_store_var_pack_key(
MI_KEYDEF *keyinfo,
1774 register unsigned char *key_pos,
1779 unsigned char *start;
1783 if (s_temp->ref_length)
1786 store_pack_length(s_temp->pack_marker == 128,key_pos,s_temp->ref_length);
1788 if (s_temp->ref_length != s_temp->pack_marker)
1789 store_key_length_inc(key_pos,s_temp->key_length);
1794 store_pack_length(s_temp->pack_marker == 128,key_pos,s_temp->key_length);
1796 assert(key_pos >= start);
1797 length= s_temp->totlength - (key_pos - start);
1798 memmove(key_pos, s_temp->key, length);
1800 if (!s_temp->next_key_pos)
1804 if (s_temp->prev_length)
1807 if (s_temp->part_of_prev_key)
1809 store_pack_length(s_temp->pack_marker == 128,key_pos,
1810 s_temp->part_of_prev_key);
1811 store_key_length_inc(key_pos,s_temp->n_length);
1815 s_temp->n_length+= s_temp->store_not_null;
1816 store_pack_length(s_temp->pack_marker == 128,key_pos,
1819 memcpy(key_pos, s_temp->prev_key, s_temp->prev_length);
1821 else if (s_temp->n_ref_length)
1823 store_pack_length(s_temp->pack_marker == 128,key_pos,s_temp->n_ref_length);
1824 if (s_temp->n_ref_length == s_temp->pack_marker)
1826 store_key_length(key_pos,s_temp->n_length);
1830 s_temp->n_length+= s_temp->store_not_null;
1831 store_pack_length(s_temp->pack_marker == 128,key_pos,s_temp->n_length);
1838 void _mi_store_bin_pack_key(
MI_KEYDEF *keyinfo,
1839 register unsigned char *key_pos,
1843 assert(s_temp->totlength >= s_temp->ref_length);
1844 store_key_length_inc(key_pos,s_temp->ref_length);
1845 memcpy(key_pos,s_temp->key+s_temp->ref_length,
1846 s_temp->totlength - s_temp->ref_length);
1848 if (s_temp->next_key_pos)
1850 key_pos+=(uint) (s_temp->totlength-s_temp->ref_length);
1851 store_key_length_inc(key_pos,s_temp->n_ref_length);
1852 if (s_temp->prev_length)
1854 memcpy(key_pos,s_temp->prev_key,s_temp->prev_length);