16
16
/* key handling functions */
18
18
#include "myisamdef.h"
19
#include <mystrings/m_ctype.h>
21
static bool _mi_get_prev_key(MI_INFO *info, MI_KEYDEF *keyinfo, unsigned char *page,
22
unsigned char *key, unsigned char *keypos,
23
uint32_t *return_key_length);
21
static my_bool _mi_get_prev_key(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *page,
22
uchar *key, uchar *keypos,
23
uint *return_key_length);
56
56
int _mi_search(register MI_INFO *info, register MI_KEYDEF *keyinfo,
57
unsigned char *key, uint32_t key_len, uint32_t nextflag, register my_off_t pos)
57
uchar *key, uint key_len, uint nextflag, register my_off_t pos)
62
unsigned char *keypos,*maxpos;
63
unsigned char lastkey[MI_MAX_KEY_BUFF],*buff;
62
uchar *keypos,*maxpos;
63
uchar lastkey[MI_MAX_KEY_BUFF],*buff;
64
DBUG_ENTER("_mi_search");
65
DBUG_PRINT("enter",("pos: %lu nextflag: %u lastpos: %lu",
66
(ulong) pos, nextflag, (ulong) info->lastpos));
67
DBUG_EXECUTE("key",_mi_print_key(DBUG_FILE,keyinfo->seg,key,key_len););
65
69
if (pos == HA_OFFSET_ERROR)
67
71
my_errno=HA_ERR_KEY_NOT_FOUND; /* Didn't find key */
68
72
info->lastpos= HA_OFFSET_ERROR;
69
73
if (!(nextflag & (SEARCH_SMALLER | SEARCH_BIGGER | SEARCH_LAST)))
70
return(-1); /* Not found ; return error */
71
return(1); /* Search at upper levels */
74
DBUG_RETURN(-1); /* Not found ; return error */
75
DBUG_RETURN(1); /* Search at upper levels */
74
78
if (!(buff=_mi_fetch_keypage(info,keyinfo,pos,DFLT_INIT_HITS,info->buff,
75
79
test(!(nextflag & SEARCH_SAVE_BUFF)))))
81
DBUG_DUMP("page",(uchar*) buff,mi_getint(buff));
78
83
flag=(*keyinfo->bin_search)(info,keyinfo,buff,key,key_len,nextflag,
79
84
&keypos,lastkey, &last_key);
80
85
if (flag == MI_FOUND_WRONG_KEY)
82
87
nod_flag=mi_test_if_nod(buff);
83
88
maxpos=buff+mi_getint(buff)-1;
87
92
if ((error=_mi_search(info,keyinfo,key,key_len,nextflag,
88
93
_mi_kpos(nod_flag,keypos))) <= 0)
93
98
if (nextflag & (SEARCH_SMALLER | SEARCH_LAST) &&
94
99
keypos == buff+2+nod_flag)
95
return(1); /* Bigger than key */
100
DBUG_RETURN(1); /* Bigger than key */
97
102
else if (nextflag & SEARCH_BIGGER && keypos >= maxpos)
98
return(1); /* Smaller than key */
103
DBUG_RETURN(1); /* Smaller than key */
106
111
if ((error=_mi_search(info,keyinfo,key,key_len,SEARCH_FIND,
107
112
_mi_kpos(nod_flag,keypos))) >= 0 ||
108
113
my_errno != HA_ERR_KEY_NOT_FOUND)
110
115
info->last_keypage= HA_OFFSET_ERROR; /* Buffer not in mem */
113
118
if (pos != info->last_keypage)
115
unsigned char *old_buff=buff;
120
uchar *old_buff=buff;
116
121
if (!(buff=_mi_fetch_keypage(info,keyinfo,pos,DFLT_INIT_HITS,info->buff,
117
122
test(!(nextflag & SEARCH_SAVE_BUFF)))))
151
156
info->page_changed=0;
152
157
info->buff_used= (info->buff != buff); /* If we have to reread buff */
159
DBUG_PRINT("exit",("found key at %lu",(ulong) info->lastpos));
163
DBUG_PRINT("exit",("Error: %d",my_errno));
157
164
info->lastpos= HA_OFFSET_ERROR;
158
165
info->page_changed=1;
160
167
} /* _mi_search */
165
172
/* ret_pos point to where find or bigger key starts */
168
int _mi_bin_search(MI_INFO *info, register MI_KEYDEF *keyinfo, unsigned char *page,
169
unsigned char *key, uint32_t key_len, uint32_t comp_flag, unsigned char **ret_pos,
170
unsigned char *buff __attribute__((unused)), bool *last_key)
175
int _mi_bin_search(MI_INFO *info, register MI_KEYDEF *keyinfo, uchar *page,
176
uchar *key, uint key_len, uint comp_flag, uchar **ret_pos,
177
uchar *buff __attribute__((unused)), my_bool *last_key)
172
179
register int start,mid,end,save_end;
174
uint32_t totlength,nod_flag,not_used[2];
181
uint totlength,nod_flag,not_used[2];
182
DBUG_ENTER("_mi_bin_search");
176
184
totlength=keyinfo->keylength+(nod_flag=mi_test_if_nod(page));
178
186
save_end=end=(int) ((mi_getint(page)-2-nod_flag)/totlength-1);
187
DBUG_PRINT("test",("mi_getint: %d end: %d",mi_getint(page),end));
179
188
page+=2+nod_flag;
181
190
while (start != end)
195
204
start++; /* point at next, bigger key */
196
205
*ret_pos=page+(uint) start*totlength;
197
206
*last_key= end == save_end;
207
DBUG_PRINT("exit",("flag: %d keypos: %d",flag,start));
199
209
} /* _mi_bin_search */
228
int _mi_seq_search(MI_INFO *info, register MI_KEYDEF *keyinfo, unsigned char *page,
229
unsigned char *key, uint32_t key_len, uint32_t comp_flag, unsigned char **ret_pos,
230
unsigned char *buff, bool *last_key)
238
int _mi_seq_search(MI_INFO *info, register MI_KEYDEF *keyinfo, uchar *page,
239
uchar *key, uint key_len, uint comp_flag, uchar **ret_pos,
240
uchar *buff, my_bool *last_key)
233
uint32_t nod_flag,length=0,not_used[2];
234
unsigned char t_buff[MI_MAX_KEY_BUFF],*end;
243
uint nod_flag,length=0,not_used[2];
244
uchar t_buff[MI_MAX_KEY_BUFF],*end;
245
DBUG_ENTER("_mi_seq_search");
236
247
end= page+mi_getint(page);
237
248
nod_flag=mi_test_if_nod(page);
246
257
mi_print_error(info->s, HA_ERR_CRASHED);
247
258
my_errno=HA_ERR_CRASHED;
248
return(MI_FOUND_WRONG_KEY);
260
("Found wrong key: length: %u page: 0x%lx end: 0x%lx",
261
length, (long) page, (long) end));
262
DBUG_RETURN(MI_FOUND_WRONG_KEY);
250
264
if ((flag=ha_key_cmp(keyinfo->seg,t_buff,key,key_len,comp_flag,
268
DBUG_PRINT("loop",("page: 0x%lx key: '%s' flag: %d", (long) page, t_buff,
253
271
memcpy(buff,t_buff,length);
257
275
memcpy(buff,t_buff,length); /* Result is first key */
258
276
*last_key= page == end;
277
DBUG_PRINT("exit",("flag: %d ret_pos: 0x%lx", flag, (long) *ret_pos));
260
279
} /* _mi_seq_search */
263
int _mi_prefix_search(MI_INFO *info, register MI_KEYDEF *keyinfo, unsigned char *page,
264
unsigned char *key, uint32_t key_len, uint32_t nextflag, unsigned char **ret_pos,
265
unsigned char *buff, bool *last_key)
282
int _mi_prefix_search(MI_INFO *info, register MI_KEYDEF *keyinfo, uchar *page,
283
uchar *key, uint key_len, uint nextflag, uchar **ret_pos,
284
uchar *buff, my_bool *last_key)
268
287
my_flag is raw comparison result to be changed according to
270
289
flag is the value returned by ha_key_cmp and as treated as final
272
291
int flag=0, my_flag=-1;
273
uint32_t nod_flag, length=0, len, matched, cmplen, kseg_len;
274
uint32_t prefix_len=0,suffix_len;
275
int key_len_skip, seg_len_pack=0, key_len_left;
276
unsigned char *end, *kseg, *vseg;
277
unsigned char *sort_order=keyinfo->seg->charset->sort_order;
278
unsigned char tt_buff[MI_MAX_KEY_BUFF+2], *t_buff=tt_buff+2;
279
unsigned char *saved_from=NULL, *saved_to=NULL, *saved_vseg=NULL;
280
uint32_t saved_length=0, saved_prefix_len=0;
281
uint32_t length_pack;
292
uint nod_flag, length=0, len, matched, cmplen, kseg_len;
293
uint prefix_len,suffix_len;
294
int key_len_skip, seg_len_pack, key_len_left;
295
uchar *end, *kseg, *vseg;
296
uchar *sort_order=keyinfo->seg->charset->sort_order;
297
uchar tt_buff[MI_MAX_KEY_BUFF+2], *t_buff=tt_buff+2;
298
uchar *saved_from=NULL, *saved_to=NULL, *saved_vseg=NULL;
299
uint saved_length=0, saved_prefix_len=0;
301
DBUG_ENTER("_mi_prefix_search");
284
303
t_buff[0]=0; /* Avoid bugs */
285
304
end= page+mi_getint(page);
293
312
key_len_left=(int) key_len- (int) key_len_skip;
294
313
/* If key_len is 0, then lenght_pack is 1, then key_len_left is -1. */
295
314
cmplen=(key_len_left>=0) ? kseg_len : key_len-length_pack;
315
DBUG_PRINT("info",("key: '%.*s'",kseg_len,kseg));
298
318
Keys are compressed the following way:
355
375
saved_prefix_len=prefix_len;
377
DBUG_PRINT("loop",("page: '%.*s%.*s'",prefix_len,t_buff+seg_len_pack,
358
unsigned char *from=vseg+suffix_len;
380
uchar *from=vseg+suffix_len;
359
381
HA_KEYSEG *keyseg;
362
384
for (keyseg=keyinfo->seg+1 ; keyseg->type ; keyseg++ )
386
408
mi_print_error(info->s, HA_ERR_CRASHED);
387
409
my_errno=HA_ERR_CRASHED;
388
return(MI_FOUND_WRONG_KEY);
411
("Found wrong key: length: %u page: 0x%lx end: %lx",
412
length, (long) page, (long) end));
413
DBUG_RETURN(MI_FOUND_WRONG_KEY);
391
416
if (matched >= prefix_len)
393
418
/* We have to compare. But we can still skip part of the key */
395
unsigned char *k=kseg+prefix_len;
420
uchar *k=kseg+prefix_len;
398
423
If prefix_len > cmplen then we are in the end-space comparison
440
465
/* We have to compare k and vseg as if they were space extended */
441
unsigned char *k_end= k+ (cmplen - len);
466
uchar *k_end= k+ (cmplen - len);
442
467
for ( ; k < k_end && *k == ' '; k++) ;
444
469
goto cmp_rest; /* should never happen */
445
if (*k < (unsigned char) ' ')
470
if (*k < (uchar) ' ')
447
472
my_flag= 1; /* Compared string is smaller */
453
478
else if (len > cmplen)
455
unsigned char *vseg_end;
456
481
if ((nextflag & SEARCH_PREFIX) && key_len_left == 0)
459
484
/* We have to compare k and vseg as if they were space extended */
460
485
for (vseg_end= vseg + (len-cmplen) ;
461
vseg < vseg_end && *vseg == (unsigned char) ' ';
486
vseg < vseg_end && *vseg == (uchar) ' ';
462
487
vseg++, matched++) ;
463
assert(vseg < vseg_end);
488
DBUG_ASSERT(vseg < vseg_end);
465
if (*vseg > (unsigned char) ' ')
490
if (*vseg > (uchar) ' ')
467
492
my_flag= 1; /* Compared string is smaller */
519
544
*last_key= page == end;
546
DBUG_PRINT("exit",("flag: %d ret_pos: 0x%lx", flag, (long) *ret_pos));
522
548
} /* _mi_prefix_search */
525
551
/* Get pos to a key_block */
527
my_off_t _mi_kpos(uint32_t nod_flag, unsigned char *after_key)
553
my_off_t _mi_kpos(uint nod_flag, uchar *after_key)
529
555
after_key-=nod_flag;
530
556
switch (nod_flag) {
561
587
/* Save pos to a key_block */
563
void _mi_kpointer(register MI_INFO *info, register unsigned char *buff, my_off_t pos)
589
void _mi_kpointer(register MI_INFO *info, register uchar *buff, my_off_t pos)
565
591
pos/=MI_MIN_KEY_BLOCK_LENGTH;
566
592
switch (info->s->base.key_reflength) {
579
605
case 4: mi_int4store(buff,pos); break;
580
606
case 3: mi_int3store(buff,pos); break;
581
607
case 2: mi_int2store(buff,(uint) pos); break;
582
case 1: buff[0]= (unsigned char) pos; break;
608
case 1: buff[0]= (uchar) pos; break;
583
609
default: abort(); /* impossible */
585
611
} /* _mi_kpointer */
588
614
/* Calc pos to a data-record from a key */
591
my_off_t _mi_dpos(MI_INFO *info, uint32_t nod_flag, unsigned char *after_key)
617
my_off_t _mi_dpos(MI_INFO *info, uint nod_flag, uchar *after_key)
594
620
after_key-=(nod_flag + info->s->rec_reflength);
619
645
/* Calc position from a record pointer ( in delete link chain ) */
621
my_off_t _mi_rec_pos(MYISAM_SHARE *s, unsigned char *ptr)
647
my_off_t _mi_rec_pos(MYISAM_SHARE *s, uchar *ptr)
624
650
switch (s->rec_reflength) {
677
703
/* save position to record */
679
void _mi_dpointer(MI_INFO *info, unsigned char *buff, my_off_t pos)
705
void _mi_dpointer(MI_INFO *info, uchar *buff, my_off_t pos)
681
707
if (!(info->s->options &
682
708
(HA_OPTION_PACK_RECORD | HA_OPTION_COMPRESS_RECORD)) &&
716
742
/* same as _mi_get_key but used with fixed length keys */
718
uint32_t _mi_get_static_key(register MI_KEYDEF *keyinfo, uint32_t nod_flag,
719
register unsigned char **page, register unsigned char *key)
744
uint _mi_get_static_key(register MI_KEYDEF *keyinfo, uint nod_flag,
745
register uchar **page, register uchar *key)
721
memcpy(key, *page, keyinfo->keylength+nod_flag);
747
memcpy((uchar*) key,(uchar*) *page,
748
(size_t) (keyinfo->keylength+nod_flag));
722
749
*page+=keyinfo->keylength+nod_flag;
723
750
return(keyinfo->keylength);
724
751
} /* _mi_get_static_key */
738
765
key_length + length of data pointer
741
uint32_t _mi_get_pack_key(register MI_KEYDEF *keyinfo, uint32_t nod_flag,
742
register unsigned char **page_pos, register unsigned char *key)
768
uint _mi_get_pack_key(register MI_KEYDEF *keyinfo, uint nod_flag,
769
register uchar **page_pos, register uchar *key)
744
771
register HA_KEYSEG *keyseg;
745
unsigned char *start_key,*page=*page_pos;
772
uchar *start_key,*page=*page_pos;
749
776
for (keyseg=keyinfo->seg ; keyseg->type ;keyseg++)
751
778
if (keyseg->flag & HA_PACK_KEY)
753
780
/* key with length, packed to previous key */
754
unsigned char *start=key;
755
uint32_t packed= *page & 128,tot_length,rest_length;
782
uint packed= *page & 128,tot_length,rest_length;
756
783
if (keyseg->length >= 127)
758
785
length=mi_uint2korr(page) & 32767;
777
804
key+= length; /* Same diff_key as prev */
778
805
if (length > keyseg->length)
808
("Found too long null packed key: %u of %u at 0x%lx",
809
length, keyseg->length, (long) *page_pos));
810
DBUG_DUMP("key",(uchar*) *page_pos,16);
780
811
mi_print_error(keyinfo->share, HA_ERR_CRASHED);
781
812
my_errno=HA_ERR_CRASHED;
832
863
if (length > (uint) keyseg->length)
865
DBUG_PRINT("error",("Found too long packed key: %u of %u at 0x%lx",
866
length, keyseg->length, (long) *page_pos));
867
DBUG_DUMP("key",(uchar*) *page_pos,16);
834
868
mi_print_error(keyinfo->share, HA_ERR_CRASHED);
835
869
my_errno=HA_ERR_CRASHED;
836
870
return 0; /* Error */
847
881
if (keyseg->flag &
848
882
(HA_VAR_LENGTH_PART | HA_BLOB_PART | HA_SPACE_PACK))
850
unsigned char *tmp=page;
851
885
get_key_length(length,tmp);
852
886
length+=(uint) (tmp-page);
855
889
length=keyseg->length;
857
memcpy(key, page, length);
891
memcpy((uchar*) key,(uchar*) page,(size_t) length);
861
895
length=keyseg->length+nod_flag;
862
memcpy(key,page,length);
896
bmove((uchar*) key,(uchar*) page,length);
863
897
*page_pos= page+length;
864
898
return ((uint) (key-start_key)+keyseg->length);
865
899
} /* _mi_get_pack_key */
869
903
/* key that is packed relatively to previous */
871
uint32_t _mi_get_binary_pack_key(register MI_KEYDEF *keyinfo, uint32_t nod_flag,
872
register unsigned char **page_pos, register unsigned char *key)
905
uint _mi_get_binary_pack_key(register MI_KEYDEF *keyinfo, uint nod_flag,
906
register uchar **page_pos, register uchar *key)
874
908
register HA_KEYSEG *keyseg;
875
unsigned char *start_key,*page,*page_end,*from,*from_end;
909
uchar *start_key,*page,*page_end,*from,*from_end;
911
DBUG_ENTER("_mi_get_binary_pack_key");
879
914
page_end=page+MI_MAX_KEY_BUFF+1;
899
934
if (length > keyinfo->maxlength)
937
("Found too long binary packed key: %u of %u at 0x%lx",
938
length, keyinfo->maxlength, (long) *page_pos));
939
DBUG_DUMP("key",(uchar*) *page_pos,16);
901
940
mi_print_error(keyinfo->share, HA_ERR_CRASHED);
902
941
my_errno=HA_ERR_CRASHED;
903
return(0); /* Wrong key */
942
DBUG_RETURN(0); /* Wrong key */
905
944
/* Key is packed against prev key, take prefix from prev key. */
954
993
from=page; from_end=page_end;
956
memmove(key, from, length);
995
DBUG_PRINT("info",("key: 0x%lx from: 0x%lx length: %u",
996
(long) key, (long) from, length));
997
memmove((uchar*) key, (uchar*) from, (size_t) length);
980
1021
if (from_end != page_end)
1023
DBUG_PRINT("error",("Error when unpacking key"));
982
1024
mi_print_error(keyinfo->share, HA_ERR_CRASHED);
983
1025
my_errno=HA_ERR_CRASHED;
984
return(0); /* Error */
1026
DBUG_RETURN(0); /* Error */
986
1028
/* Copy data pointer and, if appropriate, key block pointer. */
987
memcpy(key, from, length);
1029
memcpy((uchar*) key,(uchar*) from,(size_t) length);
988
1030
*page_pos= from+length;
990
return((uint) (key-start_key)+keyseg->length);
1032
DBUG_RETURN((uint) (key-start_key)+keyseg->length);
994
1036
/* Get key at position without knowledge of previous key */
995
1037
/* Returns pointer to next key */
997
unsigned char *_mi_get_key(MI_INFO *info, MI_KEYDEF *keyinfo, unsigned char *page,
998
unsigned char *key, unsigned char *keypos, uint32_t *return_key_length)
1039
uchar *_mi_get_key(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *page,
1040
uchar *key, uchar *keypos, uint *return_key_length)
1043
DBUG_ENTER("_mi_get_key");
1002
1045
nod_flag=mi_test_if_nod(page);
1003
1046
if (! (keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)))
1005
memcpy(key,keypos,keyinfo->keylength+nod_flag);
1006
return(keypos+keyinfo->keylength+nod_flag);
1048
bmove((uchar*) key,(uchar*) keypos,keyinfo->keylength+nod_flag);
1049
DBUG_RETURN(keypos+keyinfo->keylength+nod_flag);
1017
1060
mi_print_error(info->s, HA_ERR_CRASHED);
1018
1061
my_errno=HA_ERR_CRASHED;
1066
DBUG_PRINT("exit",("page: 0x%lx length: %u", (long) page,
1067
*return_key_length));
1024
1069
} /* _mi_get_key */
1027
1072
/* Get key at position without knowledge of previous key */
1028
1073
/* Returns 0 if ok */
1030
static bool _mi_get_prev_key(MI_INFO *info, MI_KEYDEF *keyinfo, unsigned char *page,
1031
unsigned char *key, unsigned char *keypos,
1032
uint32_t *return_key_length)
1075
static my_bool _mi_get_prev_key(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *page,
1076
uchar *key, uchar *keypos,
1077
uint *return_key_length)
1080
DBUG_ENTER("_mi_get_prev_key");
1036
1082
nod_flag=mi_test_if_nod(page);
1037
1083
if (! (keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)))
1039
1085
*return_key_length=keyinfo->keylength;
1040
memcpy(key, keypos - *return_key_length-nod_flag, *return_key_length);
1086
bmove((uchar*) key,(uchar*) keypos- *return_key_length-nod_flag,
1087
*return_key_length);
1063
1110
/* Get last key from key-page */
1064
1111
/* Return pointer to where key starts */
1066
unsigned char *_mi_get_last_key(MI_INFO *info, MI_KEYDEF *keyinfo, unsigned char *page,
1067
unsigned char *lastkey, unsigned char *endpos, uint32_t *return_key_length)
1113
uchar *_mi_get_last_key(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *page,
1114
uchar *lastkey, uchar *endpos, uint *return_key_length)
1070
unsigned char *lastpos;
1118
DBUG_ENTER("_mi_get_last_key");
1119
DBUG_PRINT("enter",("page: 0x%lx endpos: 0x%lx", (long) page,
1072
1122
nod_flag=mi_test_if_nod(page);
1073
1123
if (! (keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)))
1075
1125
lastpos=endpos-keyinfo->keylength-nod_flag;
1076
1126
*return_key_length=keyinfo->keylength;
1077
1127
if (lastpos > page)
1078
memcpy(lastkey,lastpos,keyinfo->keylength+nod_flag);
1128
bmove((uchar*) lastkey,(uchar*) lastpos,keyinfo->keylength+nod_flag);
1087
1137
*return_key_length=(*keyinfo->get_key)(keyinfo,nod_flag,&page,lastkey);
1088
1138
if (*return_key_length == 0)
1140
DBUG_PRINT("error",("Couldn't find last key: page: 0x%lx",
1090
1142
mi_print_error(info->s, HA_ERR_CRASHED);
1091
1143
my_errno=HA_ERR_CRASHED;
1148
DBUG_PRINT("exit",("lastpos: 0x%lx length: %u", (long) lastpos,
1149
*return_key_length));
1150
DBUG_RETURN(lastpos);
1097
1151
} /* _mi_get_last_key */
1100
1154
/* Calculate length of key */
1102
uint32_t _mi_keylength(MI_KEYDEF *keyinfo, register unsigned char *key)
1156
uint _mi_keylength(MI_KEYDEF *keyinfo, register uchar *key)
1104
1158
register HA_KEYSEG *keyseg;
1105
unsigned char *start;
1107
1161
if (! (keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)))
1108
1162
return (keyinfo->keylength);
1134
1188
after '0xDF' but find 'ss'
1137
uint32_t _mi_keylength_part(MI_KEYDEF *keyinfo, register unsigned char *key,
1191
uint _mi_keylength_part(MI_KEYDEF *keyinfo, register uchar *key,
1138
1192
HA_KEYSEG *end)
1140
1194
register HA_KEYSEG *keyseg;
1141
unsigned char *start= key;
1143
1197
for (keyseg=keyinfo->seg ; keyseg != end ; keyseg++)
1160
1214
/* Move a key */
1162
unsigned char *_mi_move_key(MI_KEYDEF *keyinfo, unsigned char *to, unsigned char *from)
1216
uchar *_mi_move_key(MI_KEYDEF *keyinfo, uchar *to, uchar *from)
1164
register uint32_t length;
1165
length= _mi_keylength(keyinfo, from);
1166
memcpy(to, from, length);
1218
register uint length;
1219
memcpy((uchar*) to, (uchar*) from,
1220
(size_t) (length=_mi_keylength(keyinfo,from)));
1167
1221
return to+length;
1171
1225
/* This can't be used when database is touched after last read */
1173
1227
int _mi_search_next(register MI_INFO *info, register MI_KEYDEF *keyinfo,
1174
unsigned char *key, uint32_t key_length, uint32_t nextflag, my_off_t pos)
1228
uchar *key, uint key_length, uint nextflag, my_off_t pos)
1178
unsigned char lastkey[MI_MAX_KEY_BUFF];
1232
uchar lastkey[MI_MAX_KEY_BUFF];
1233
DBUG_ENTER("_mi_search_next");
1234
DBUG_PRINT("enter",("nextflag: %u lastpos: %lu int_keypos: %lu",
1235
nextflag, (ulong) info->lastpos,
1236
(ulong) info->int_keypos));
1237
DBUG_EXECUTE("key",_mi_print_key(DBUG_FILE,keyinfo->seg,key,key_length););
1180
1239
/* Force full read if we are at last key or if we are not on a leaf
1181
1240
and the key tree has changed since we used it last time
1188
1247
info->page_changed ||
1189
1248
(info->int_keytree_version != keyinfo->version &&
1190
1249
(info->int_nod_flag || info->buff_used)))
1191
return(_mi_search(info,keyinfo,key, USE_WHOLE_KEY,
1250
DBUG_RETURN(_mi_search(info,keyinfo,key, USE_WHOLE_KEY,
1192
1251
nextflag | SEARCH_SAVE_BUFF, pos));
1194
1253
if (info->buff_used)
1196
1255
if (!_mi_fetch_keypage(info,keyinfo,info->last_search_keypage,
1197
1256
DFLT_INIT_HITS,info->buff,0))
1199
1258
info->buff_used=0;
1210
1269
if ((error=_mi_search(info,keyinfo,key, USE_WHOLE_KEY,
1211
1270
nextflag | SEARCH_SAVE_BUFF, tmp_pos)) <=0)
1214
1273
memcpy(lastkey,key,key_length);
1215
1274
if (!(info->lastkey_length=(*keyinfo->get_key)(keyinfo,nod_flag,
1216
1275
&info->int_keypos,lastkey)))
1219
1278
else /* Previous key */
1222
1281
/* Find start of previous key */
1223
1282
info->int_keypos=_mi_get_last_key(info,keyinfo,info->buff,lastkey,
1224
1283
info->int_keypos, &length);
1225
1284
if (!info->int_keypos)
1227
1286
if (info->int_keypos == info->buff+2)
1228
return(_mi_search(info,keyinfo,key, USE_WHOLE_KEY,
1287
DBUG_RETURN(_mi_search(info,keyinfo,key, USE_WHOLE_KEY,
1229
1288
nextflag | SEARCH_SAVE_BUFF, pos));
1230
1289
if ((error=_mi_search(info,keyinfo,key, USE_WHOLE_KEY,
1231
1290
nextflag | SEARCH_SAVE_BUFF,
1232
1291
_mi_kpos(nod_flag,info->int_keypos))) <= 0)
1235
1294
/* QQ: We should be able to optimize away the following call */
1236
1295
if (! _mi_get_last_key(info,keyinfo,info->buff,lastkey,
1237
1296
info->int_keypos,&info->lastkey_length))
1240
1299
memcpy(info->lastkey,lastkey,info->lastkey_length);
1241
1300
info->lastpos=_mi_dpos(info,0,info->lastkey+info->lastkey_length);
1301
DBUG_PRINT("exit",("found key at %lu",(ulong) info->lastpos));
1243
1303
} /* _mi_search_next */
1249
1309
int _mi_search_first(register MI_INFO *info, register MI_KEYDEF *keyinfo,
1250
1310
register my_off_t pos)
1253
unsigned char *page;
1314
DBUG_ENTER("_mi_search_first");
1255
1316
if (pos == HA_OFFSET_ERROR)
1257
1318
my_errno=HA_ERR_KEY_NOT_FOUND;
1258
1319
info->lastpos= HA_OFFSET_ERROR;
1264
1325
if (!_mi_fetch_keypage(info,keyinfo,pos,DFLT_INIT_HITS,info->buff,0))
1266
1327
info->lastpos= HA_OFFSET_ERROR;
1269
1330
nod_flag=mi_test_if_nod(info->buff);
1270
1331
page=info->buff+2+nod_flag;
1273
1334
if (!(info->lastkey_length=(*keyinfo->get_key)(keyinfo,nod_flag,&page,
1274
1335
info->lastkey)))
1275
return(-1); /* Crashed */
1336
DBUG_RETURN(-1); /* Crashed */
1277
1338
info->int_keypos=page; info->int_maxpos=info->buff+mi_getint(info->buff)-1;
1278
1339
info->int_nod_flag=nod_flag;
1281
1342
info->page_changed=info->buff_used=0;
1282
1343
info->lastpos=_mi_dpos(info,0,info->lastkey+info->lastkey_length);
1345
DBUG_PRINT("exit",("found key at %lu", (ulong) info->lastpos));
1285
1347
} /* _mi_search_first */
1291
1353
int _mi_search_last(register MI_INFO *info, register MI_KEYDEF *keyinfo,
1292
1354
register my_off_t pos)
1295
unsigned char *buff,*page;
1358
DBUG_ENTER("_mi_search_last");
1297
1360
if (pos == HA_OFFSET_ERROR)
1299
1362
my_errno=HA_ERR_KEY_NOT_FOUND; /* Didn't find key */
1300
1363
info->lastpos= HA_OFFSET_ERROR;
1304
1367
buff=info->buff;
1307
1370
if (!_mi_fetch_keypage(info,keyinfo,pos,DFLT_INIT_HITS,buff,0))
1309
1372
info->lastpos= HA_OFFSET_ERROR;
1312
1375
page= buff+mi_getint(buff);
1313
1376
nod_flag=mi_test_if_nod(buff);
1316
1379
if (!_mi_get_last_key(info,keyinfo,buff,info->lastkey,page,
1317
1380
&info->lastkey_length))
1319
1382
info->lastpos=_mi_dpos(info,0,info->lastkey+info->lastkey_length);
1320
1383
info->int_keypos=info->int_maxpos=page;
1321
1384
info->int_nod_flag=nod_flag;
1344
1408
/* Static length key */
1347
_mi_calc_static_key_length(MI_KEYDEF *keyinfo,uint32_t nod_flag,
1348
unsigned char *next_pos __attribute__((unused)),
1349
unsigned char *org_key __attribute__((unused)),
1350
unsigned char *prev_key __attribute__((unused)),
1351
unsigned char *key, MI_KEY_PARAM *s_temp)
1411
_mi_calc_static_key_length(MI_KEYDEF *keyinfo,uint nod_flag,
1412
uchar *next_pos __attribute__((unused)),
1413
uchar *org_key __attribute__((unused)),
1414
uchar *prev_key __attribute__((unused)),
1415
uchar *key, MI_KEY_PARAM *s_temp)
1353
1417
s_temp->key=key;
1354
1418
return (int) (s_temp->totlength=keyinfo->keylength+nod_flag);
1357
1421
/* Variable length key */
1360
_mi_calc_var_key_length(MI_KEYDEF *keyinfo,uint32_t nod_flag,
1361
unsigned char *next_pos __attribute__((unused)),
1362
unsigned char *org_key __attribute__((unused)),
1363
unsigned char *prev_key __attribute__((unused)),
1364
unsigned char *key, MI_KEY_PARAM *s_temp)
1424
_mi_calc_var_key_length(MI_KEYDEF *keyinfo,uint nod_flag,
1425
uchar *next_pos __attribute__((unused)),
1426
uchar *org_key __attribute__((unused)),
1427
uchar *prev_key __attribute__((unused)),
1428
uchar *key, MI_KEY_PARAM *s_temp)
1366
1430
s_temp->key=key;
1367
1431
return (int) (s_temp->totlength=_mi_keylength(keyinfo,key)+nod_flag);
1390
_mi_calc_var_pack_key_length(MI_KEYDEF *keyinfo,uint32_t nod_flag,unsigned char *next_key,
1391
unsigned char *org_key, unsigned char *prev_key, unsigned char *key,
1454
_mi_calc_var_pack_key_length(MI_KEYDEF *keyinfo,uint nod_flag,uchar *next_key,
1455
uchar *org_key, uchar *prev_key, uchar *key,
1392
1456
MI_KEY_PARAM *s_temp)
1394
1458
register HA_KEYSEG *keyseg;
1396
uint32_t key_length,ref_length,org_key_length=0,
1460
uint key_length,ref_length,org_key_length=0,
1397
1461
length_pack,new_key_length,diff_flag,pack_marker;
1398
unsigned char *start,*end,*key_end,*sort_order;
1462
uchar *start,*end,*key_end,*sort_order;
1463
my_bool same_length;
1401
1465
length_pack=s_temp->ref_length=s_temp->n_ref_length=s_temp->n_length=0;
1402
1466
same_length=0; keyseg=keyinfo->seg;
1508
1572
s_temp->totlength=(uint) length;
1509
1573
s_temp->prev_length=0;
1574
DBUG_PRINT("test",("tot_length: %u length: %d uniq_key_length: %u",
1575
key_length, length, s_temp->key_length));
1511
1577
/* If something after that hasn't length=0, test if we can combine */
1512
1578
if ((s_temp->next_key_pos=next_key))
1514
uint32_t packed,n_length;
1580
uint packed,n_length;
1516
1582
packed = *next_key & 128;
1517
1583
if (diff_flag == 2)
1595
1661
if (ref_length+pack_marker > new_ref_length)
1597
uint32_t new_pack_length=new_ref_length-pack_marker;
1663
uint new_pack_length=new_ref_length-pack_marker;
1598
1664
/* We must copy characters from the original key to the next key */
1599
1665
s_temp->part_of_prev_key= new_ref_length;
1600
1666
s_temp->prev_length= ref_length - new_pack_length;
1659
1727
/* Length of key which is prefix compressed */
1662
_mi_calc_bin_pack_key_length(MI_KEYDEF *keyinfo,uint32_t nod_flag,unsigned char *next_key,
1663
unsigned char *org_key, unsigned char *prev_key, unsigned char *key,
1730
_mi_calc_bin_pack_key_length(MI_KEYDEF *keyinfo,uint nod_flag,uchar *next_key,
1731
uchar *org_key, uchar *prev_key, uchar *key,
1664
1732
MI_KEY_PARAM *s_temp)
1666
uint32_t length,key_length,ref_length;
1734
uint length,key_length,ref_length;
1668
1736
s_temp->totlength=key_length=_mi_keylength(keyinfo,key)+nod_flag;
1669
1737
#ifdef HAVE_purify
1678
1746
As keys may be identical when running a sort in myisamchk, we
1679
1747
have to guard against the case where keys may be identical
1682
1750
end=key+key_length;
1683
1751
for ( ; *key == *prev_key && key < end; key++,prev_key++) ;
1684
1752
s_temp->ref_length= ref_length=(uint) (key-s_temp->key);
1693
1761
if ((s_temp->next_key_pos=next_key)) /* If another key after */
1695
1763
/* pack key against next key */
1696
uint32_t next_length,next_length_pack;
1764
uint next_length,next_length_pack;
1697
1765
get_key_pack_length(next_length,next_length_pack,next_key);
1699
1767
/* If first key and next key is packed (only on delete) */
1700
1768
if (!prev_key && org_key && next_length)
1703
1771
for (key= s_temp->key, end=key+next_length ;
1704
1772
*key == *org_key && key < end;
1705
1773
key++,org_key++) ;
1741
1809
/* store key without compression */
1743
1811
void _mi_store_static_key(MI_KEYDEF *keyinfo __attribute__((unused)),
1744
register unsigned char *key_pos,
1812
register uchar *key_pos,
1745
1813
register MI_KEY_PARAM *s_temp)
1747
memcpy(key_pos, s_temp->key, s_temp->totlength);
1815
memcpy((uchar*) key_pos,(uchar*) s_temp->key,(size_t) s_temp->totlength);
1751
1819
/* store variable length key with prefix compression */
1753
1821
#define store_pack_length(test,pos,length) { \
1754
if (test) { *((pos)++) = (unsigned char) (length); } else \
1755
{ *((pos)++) = (unsigned char) ((length) >> 8); *((pos)++) = (unsigned char) (length); } }
1822
if (test) { *((pos)++) = (uchar) (length); } else \
1823
{ *((pos)++) = (uchar) ((length) >> 8); *((pos)++) = (uchar) (length); } }
1758
1826
void _mi_store_var_pack_key(MI_KEYDEF *keyinfo __attribute__((unused)),
1759
register unsigned char *key_pos,
1827
register uchar *key_pos,
1760
1828
register MI_KEY_PARAM *s_temp)
1763
unsigned char *start;
1777
1845
/* Not packed against previous key */
1778
1846
store_pack_length(s_temp->pack_marker == 128,key_pos,s_temp->key_length);
1780
assert(key_pos >= start);
1781
length= s_temp->totlength - (key_pos - start);
1782
memcpy(key_pos, s_temp->key, length);
1848
bmove((uchar*) key_pos,(uchar*) s_temp->key,
1849
(length=s_temp->totlength-(uint) (key_pos-start)));
1784
1851
if (!s_temp->next_key_pos) /* No following key */
1820
1887
/* variable length key with prefix compression */
1822
1889
void _mi_store_bin_pack_key(MI_KEYDEF *keyinfo __attribute__((unused)),
1823
register unsigned char *key_pos,
1890
register uchar *key_pos,
1824
1891
register MI_KEY_PARAM *s_temp)
1826
assert(s_temp->totlength >= s_temp->ref_length);
1827
1893
store_key_length_inc(key_pos,s_temp->ref_length);
1828
memcpy(key_pos,s_temp->key+s_temp->ref_length,
1829
s_temp->totlength - s_temp->ref_length);
1894
memcpy((char*) key_pos,(char*) s_temp->key+s_temp->ref_length,
1895
(size_t) s_temp->totlength-s_temp->ref_length);
1831
1897
if (s_temp->next_key_pos)
added
removed
storage/myisam/mi_search.c
