1
/* Copyright (C) 2000-2006 MySQL AB
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.
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.
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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
16
/* key handling functions */
18
#include "myisam_priv.h"
19
#include "drizzled/charset_info.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)
33
if (inx == -1) /* Use last index */
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) /* Index changed */
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 && flush_io_cache(&info->rec_cache))
50
} /* mi_check_index */
54
** Search after row by a key
55
** Position to row is stored in info->lastpos
56
** Return: -1 if not found
57
** 1 if one should continue search on higher level
60
int _mi_search(register MI_INFO *info, register MI_KEYDEF *keyinfo,
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; /* Didn't find key */
72
info->lastpos= HA_OFFSET_ERROR;
73
if (!(nextflag & (SEARCH_SMALLER | SEARCH_BIGGER | SEARCH_LAST)))
74
return(-1); /* Not found ; return error */
75
return(1); /* Search at upper levels */
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)
99
return(1); /* Bigger than key */
101
else if (nextflag & SEARCH_BIGGER && keypos >= maxpos)
102
return(1); /* Smaller than key */
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; /* Buffer not in mem */
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; /* Didn't find key */
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);
149
/* Save position for a possible read next / previous */
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); /* If we have to reread buff */
161
info->lastpos= HA_OFFSET_ERROR;
162
info->page_changed=1;
167
/* Search after key in page-block */
168
/* If packed key puts smaller or identical key in buff */
169
/* ret_pos point to where find or bigger key starts */
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);
200
start++; /* point at next, bigger key */
201
*ret_pos=page+(uint) start*totlength;
202
*last_key= end == save_end;
204
} /* _mi_bin_search */
208
Locate a packed key in a key page.
212
info Open table information.
213
keyinfo Key definition information.
214
page Key page (beginning).
216
key_len Length to use from search key or USE_WHOLE_KEY
217
comp_flag Search flags like SEARCH_SAME etc.
218
ret_pos RETURN Position in key page behind this key.
219
buff RETURN Copy of previous or identical unpacked key.
220
last_key RETURN If key is last in page.
223
Used instead of _mi_bin_search() when key is packed.
224
Puts smaller or identical key in buff.
225
Key is searched sequentially.
228
> 0 Key in 'buff' is smaller than search key.
229
0 Key in 'buff' is identical to search key.
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);
245
t_buff[0]=0; /* Avoid bugs */
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); /* Result is first key */
263
*last_key= page == end;
265
} /* _mi_seq_search */
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)
273
my_flag is raw comparison result to be changed according to
274
SEARCH_NO_FIND,SEARCH_LAST and HA_REVERSE_SORT flags.
275
flag is the value returned by ha_key_cmp and as treated as final
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;
289
t_buff[0]=0; /* Avoid bugs */
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;
299
/* If key_len is 0, then lenght_pack is 1, then key_len_left is -1. */
300
cmplen=(key_len_left>=0) ? kseg_len : key_len-length_pack;
303
Keys are compressed the following way:
305
If the max length of first key segment <= 127 bytes the prefix is
306
1 byte else it's 2 byte
308
(prefix) length The high bit is set if this is a prefix for the prev key.
309
[suffix length] Packed length of suffix if the previous was a prefix.
310
(suffix) data Key data bytes (past the common prefix or whole segment).
311
[next-key-seg] Next key segments (([packed length], data), ...)
312
pointer Reference to the data file (last_keyseg->length).
315
matched=0; /* how many char's from prefix were alredy matched */
316
len=0; /* length of previous key unpacked */
320
uint32_t packed= *page & 128;
323
if (keyinfo->seg->length >= 127)
325
suffix_len=mi_uint2korr(vseg) & 32767;
329
suffix_len= *vseg++ & 127;
335
/* == 0x80 or 0x8000, same key, prefix length == old key length. */
340
/* > 0x80 or 0x8000, this is prefix lgt, packed suffix lgt follows. */
341
prefix_len=suffix_len;
342
get_key_length(suffix_len,vseg);
347
/* Not packed. No prefix used from last key. */
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)
398
/* We have to compare. But we can still skip part of the key */
400
unsigned char *k=kseg+prefix_len;
403
If prefix_len > cmplen then we are in the end-space comparison
404
phase. Do not try to acces the key any more ==> left= 0.
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++))
424
if (my_flag>0) /* mismatch */
426
if (my_flag==0) /* match */
429
** len cmplen seg_left_len more_segs
430
** < matched=len; continue search
431
** > = prefix ? found : (matched=len; continue search)
439
if ((keyinfo->seg->type != HA_KEYTYPE_TEXT &&
440
keyinfo->seg->type != HA_KEYTYPE_VARTEXT1 &&
441
keyinfo->seg->type != HA_KEYTYPE_VARTEXT2))
445
/* We have to compare k and vseg as if they were space extended */
446
unsigned char *k_end= k+ (cmplen - len);
447
for ( ; k < k_end && *k == ' '; k++) ;
449
goto cmp_rest; /* should never happen */
450
if (*k < (unsigned char) ' ')
452
my_flag= 1; /* Compared string is smaller */
455
my_flag= -1; /* Continue searching */
458
else if (len > cmplen)
460
unsigned char *vseg_end;
461
if ((nextflag & SEARCH_PREFIX) && key_len_left == 0)
464
/* We have to compare k and vseg as if they were space extended */
465
for (vseg_end= vseg + (len-cmplen) ;
466
vseg < vseg_end && *vseg == (unsigned char) ' ';
468
assert(vseg < vseg_end);
470
if (*vseg > (unsigned char) ' ')
472
my_flag= 1; /* Compared string is smaller */
475
my_flag= -1; /* Continue searching */
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)
490
at this line flag==-1 if the following lines were already
491
visited and 0 otherwise, i.e. flag <=0 here always !!!
495
if (nextflag & (SEARCH_NO_FIND | SEARCH_LAST))
496
flag=(nextflag & (SEARCH_BIGGER | SEARCH_LAST)) ? -1 : 1;
504
/* else (matched < prefix_len) ---> do nothing. */
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;
527
} /* _mi_prefix_search */
530
/* Get pos to a key_block */
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;
559
case 0: /* At leaf page */
560
default: /* Impossible */
561
return(HA_OFFSET_ERROR);
566
/* Save pos to a key_block */
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;
588
default: abort(); /* impossible */
593
/* Calc pos to a data-record from a key */
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;
616
pos=0L; /* Shut compiler up */
618
return (info->s->options &
619
(HA_OPTION_PACK_RECORD | HA_OPTION_COMPRESS_RECORD)) ? pos :
620
pos*info->s->base.pack_reclength;
624
/* Calc position from a record pointer ( in delete link chain ) */
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; /* end of list */
637
pos= (internal::my_off_t) mi_uint7korr(ptr);
638
if (pos == (((internal::my_off_t) 1) << 56) -1)
639
return HA_OFFSET_ERROR; /* end of list */
642
pos= (internal::my_off_t) mi_uint6korr(ptr);
643
if (pos == (((internal::my_off_t) 1) << 48) -1)
644
return HA_OFFSET_ERROR; /* end of list */
647
pos= (internal::my_off_t) mi_uint5korr(ptr);
648
if (pos == (((internal::my_off_t) 1) << 40) -1)
649
return HA_OFFSET_ERROR; /* end of list */
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;
674
default: abort(); /* Impossible */
676
return ((s->options &
677
(HA_OPTION_PACK_RECORD | HA_OPTION_COMPRESS_RECORD)) ? pos :
678
pos*s->base.pack_reclength);
682
/* save position to record */
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;
710
default: abort(); /* Impossible */
715
/* Get key from key-block */
716
/* page points at previous key; its advanced to point at next key */
717
/* key should contain previous key */
718
/* Returns length of found key + pointers */
719
/* nod_flag is a flag if we are on nod */
721
/* same as _mi_get_key but used with fixed length keys */
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);
729
} /* _mi_get_static_key */
733
get key witch is packed against previous key or key with a NULL column.
737
keyinfo key definition information.
738
nod_flag If nod: Length of node pointer, else zero.
739
page_pos RETURN position in key page behind this key.
740
key IN/OUT in: prev key, out: unpacked key.
743
key_length + length of data pointer
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)
749
register HA_KEYSEG *keyseg;
750
unsigned char *start_key,*page=*page_pos;
754
for (keyseg=keyinfo->seg ; keyseg->type ;keyseg++)
756
if (keyseg->flag & HA_PACK_KEY)
758
/* key with length, packed to previous 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;
775
return 0; /* Error */
777
if (length == 0) /* Same key */
779
if (keyseg->flag & HA_NULL_PART)
780
*key++=1; /* Can't be NULL */
781
get_key_length(length,key);
782
key+= length; /* Same diff_key as prev */
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)
793
key++; /* Skip null marker*/
797
get_key_length(rest_length,page);
798
tot_length=rest_length+length;
800
/* If the stored length has changed, we must move the key */
801
if (tot_length >= 255 && *start != 255)
803
/* length prefix changed from a length of one to a length of 3 */
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)
829
if (!length--) /* Null part */
834
*key++=1; /* Not null */
837
if (length > (uint) keyseg->length)
839
mi_print_error(keyinfo->share, HA_ERR_CRASHED);
840
errno=HA_ERR_CRASHED;
841
return 0; /* Error */
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);
870
} /* _mi_get_pack_key */
874
/* key that is packed relatively to previous */
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)
879
register HA_KEYSEG *keyseg;
880
unsigned char *start_key,*page,*page_end,*from,*from_end;
884
page_end=page+MI_MAX_KEY_BUFF+1;
888
Keys are compressed the following way:
890
prefix length Packed length of prefix common with prev key (1 or 3 bytes)
891
for each key segment:
892
[is null] Null indicator if can be null (1 byte, zero means null)
893
[length] Packed length if varlength (1 or 3 bytes)
894
key segment 'length' bytes of key segment value
895
pointer Reference to the data file (last_keyseg->length).
897
get_key_length() is a macro. It gets the prefix length from 'page'
898
and puts it into 'length'. It increments 'page' by 1 or 3, depending
899
on the packed length of the prefix length.
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;
908
return(0); /* Wrong key */
910
/* Key is packed against prev key, take prefix from prev key. */
912
from_end= key + length;
916
/* Key is not packed against prev key, take all from page buffer. */
922
The trouble is that key can be split in two parts:
923
The first part (prefix) is in from .. from_end - 1.
924
The second part starts at page.
925
The split can be at every byte position. So we need to check for
926
the end of the first part before using every byte.
928
for (keyseg=keyinfo->seg ; keyseg->type ;keyseg++)
930
if (keyseg->flag & HA_NULL_PART)
932
/* If prefix is used up, switch to rest. */
933
if (from == from_end) { from=page; from_end=page_end; }
934
if (!(*key++ = *from++))
935
continue; /* Null part */
937
if (keyseg->flag & (HA_VAR_LENGTH_PART | HA_BLOB_PART | HA_SPACE_PACK))
939
/* If prefix is used up, switch to rest. */
940
if (from == from_end) { from=page; from_end=page_end; }
941
/* Get length of dynamic length key part */
942
if ((length= (*key++ = *from++)) == 255)
944
/* If prefix is used up, switch to rest. */
945
if (from == from_end) { from=page; from_end=page_end; }
946
length= (uint) ((*key++ = *from++)) << 8;
947
/* If prefix is used up, switch to rest. */
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)
957
key+=tmp; /* Use old key */
959
from=page; from_end=page_end;
961
memmove(key, from, length);
966
Last segment (type == 0) contains length of data pointer.
967
If we have mixed key blocks with data pointer and key block pointer,
968
we have to copy both.
970
length=keyseg->length+nod_flag;
971
if ((tmp=(uint) (from_end-from)) <= length)
973
/* Remaining length is less or equal max possible length. */
974
memcpy(key+tmp,page,length-tmp); /* Get last part of key */
975
*page_pos= page+length-tmp;
980
Remaining length is greater than max possible length.
981
This can happen only if we switched to the new key bytes already.
982
'page_end' is calculated with MI_MAX_KEY_BUFF. So it can be far
983
behind the real end of the key.
985
if (from_end != page_end)
987
mi_print_error(keyinfo->share, HA_ERR_CRASHED);
988
errno=HA_ERR_CRASHED;
989
return(0); /* Error */
991
/* Copy data pointer and, if appropriate, key block pointer. */
992
memcpy(key, from, length);
993
*page_pos= from+length;
995
return((uint) (key-start_key)+keyseg->length);
999
/* Get key at position without knowledge of previous key */
1000
/* Returns pointer to next key */
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);
1016
key[0]=0; /* safety */
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;
1032
/* Get key at position without knowledge of previous key */
1033
/* Returns 0 if ok */
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);
1051
key[0]=0; /* safety */
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;
1068
/* Get last key from key-page */
1069
/* Return pointer to where key starts */
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;
1102
} /* _mi_get_last_key */
1105
/* Calculate length of key */
1107
uint32_t _mi_keylength(MI_KEYDEF *keyinfo, register unsigned char *key)
1109
register HA_KEYSEG *keyseg;
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);
1131
} /* _mi_keylength */
1135
Calculate length of part key.
1137
Used in mi_rkey() to find the key found for the key-part that was used.
1138
This is needed in case of multi-byte character sets where we may search
1139
after '0xDF' but find 'ss'
1142
uint32_t _mi_keylength_part(MI_KEYDEF *keyinfo, register unsigned char *key,
1145
register HA_KEYSEG *keyseg;
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);
1175
/* Find next/previous record with same key */
1176
/* This can't be used when database is touched after last read */
1178
int _mi_search_next(register MI_INFO *info, register MI_KEYDEF *keyinfo,
1179
unsigned char *key, uint32_t key_length, uint32_t nextflag, internal::my_off_t pos)
1183
unsigned char lastkey[MI_MAX_KEY_BUFF];
1185
/* Force full read if we are at last key or if we are not on a leaf
1186
and the key tree has changed since we used it last time
1187
Note that even if the key tree has changed since last read, we can use
1188
the last read data from the leaf if we haven't used the buffer for
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))
1207
/* Last used buffer is in info->buff */
1208
nod_flag=mi_test_if_nod(info->buff);
1210
if (nextflag & SEARCH_BIGGER) /* Next key */
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)))
1224
else /* Previous key */
1227
/* Find start of previous key */
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)
1240
/* QQ: We should be able to optimize away the following call */
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);
1248
} /* _mi_search_next */
1251
/* Search after position for the first row in an index */
1252
/* This is stored in info->lastpos */
1254
int _mi_search_first(register MI_INFO *info, register MI_KEYDEF *keyinfo,
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,
1280
return(-1); /* Crashed */
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);
1290
} /* _mi_search_first */
1293
/* Search after position for the last row in an index */
1294
/* This is stored in info->lastpos */
1296
int _mi_search_last(register MI_INFO *info, register MI_KEYDEF *keyinfo,
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; /* Didn't find key */
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;
1332
} /* _mi_search_last */
1336
/****************************************************************************
1338
** Functions to store and pack a key in a page
1340
** mi_calc_xx_key_length takes the following arguments:
1341
** nod_flag If nod: Length of nod-pointer
1342
** next_key Position to pos after the new key in buffer
1343
** org_key Key that was before the next key in buffer
1344
** prev_key Last key before current key
1345
** key Key that will be stored
1346
** s_temp Information how next key will be packed
1347
****************************************************************************/
1349
/* Static length key */
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,
1356
unsigned char *key, MI_KEY_PARAM *s_temp)
1362
return (int) (s_temp->totlength=keyinfo->keylength+nod_flag);
1365
/* Variable length key */
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,
1372
unsigned char *key, MI_KEY_PARAM *s_temp)
1378
return (int) (s_temp->totlength=_mi_keylength(keyinfo,key)+nod_flag);
1382
length of key with a variable length first segment which is prefix
1383
compressed (myisamchk reports 'packed + stripped')
1385
Keys are compressed the following way:
1387
If the max length of first key segment <= 127 bytes the prefix is
1388
1 byte else it's 2 byte
1390
prefix byte(s) The high bit is set if this is a prefix for the prev key
1391
length Packed length if the previous was a prefix byte
1392
[length] data bytes ('length' bytes)
1393
next-key-seg Next key segments
1395
If the first segment can have NULL:
1396
The length is 0 for NULLS and 1+length for not null columns.
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,
1406
MI_KEY_PARAM *s_temp)
1408
register HA_KEYSEG *keyseg;
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;
1421
/* diff flag contains how many bytes is needed to pack key */
1422
if (keyseg->length >= 127)
1432
s_temp->pack_marker=pack_marker;
1434
/* Handle the case that the first part have NULL values */
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; /* No next key */
1443
return (s_temp->totlength);
1445
s_temp->store_not_null=1;
1446
key_length--; /* We don't store NULL */
1447
if (prev_key && !*prev_key++)
1448
org_key=prev_key=0; /* Can't pack against prev */
1450
org_key++; /* Skip NULL */
1453
s_temp->store_not_null=0;
1454
s_temp->prev_key=org_key;
1456
/* The key part will start with a packed length */
1458
get_key_pack_length(new_key_length,length_pack,key);
1459
end=key_end= key+ new_key_length;
1462
/* Calc how many characters are identical between this and the prev. key */
1465
get_key_length(org_key_length,prev_key);
1466
s_temp->prev_key=prev_key; /* Pointer at data */
1467
/* Don't use key-pack if length == 0 */
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;
1473
if (sort_order) /* SerG */
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)
1494
/* identical variable length key */
1495
s_temp->ref_length= pack_marker;
1496
length=(int) key_length-(int) (key_end-start)-length_pack;
1499
{ /* Can't combine with next */
1500
s_temp->n_length= *next_key; /* Needed by _mi_store_key */
1507
{ /* Starts as prev 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;/* Rest_of_key */
1518
s_temp->key_length+=s_temp->store_not_null; /* If null */
1519
length= key_length - length_pack+ diff_flag;
1522
s_temp->totlength=(uint) length;
1523
s_temp->prev_length=0;
1525
/* If something after that hasn't length=0, test if we can combine */
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; /* Length of next key */
1537
n_length= *next_key++ & 127;
1539
n_length-= s_temp->store_not_null;
1541
if (n_length || packed) /* Don't pack 0 length keys */
1543
uint32_t next_length_pack, new_ref_length=s_temp->ref_length;
1547
/* If first key and next key is packed (only on delete) */
1548
if (!prev_key && org_key)
1550
get_key_length(org_key_length,org_key);
1552
if (sort_order) /* SerG */
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;
1573
We put a different key between two identical variable length keys
1574
Extend next key to have same prefix as this key
1576
if (new_ref_length) /* prefix of previus key */
1577
{ /* make next key longer */
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;
1588
{ /* Can't use prev key */
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;
1598
/* Get information about not packed key suffix */
1599
get_key_pack_length(n_length,next_length_pack,next_key);
1601
/* Test if new keys has fewer characters that match the previous key */
1602
if (!new_ref_length)
1603
{ /* Can't use prev key */
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;
1612
/* We must copy characters from the original key to the next key */
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;
1623
/* Next key wasn't a prefix of previous key */
1629
uint32_t tmp_length;
1630
key=(start+=ref_length);
1631
if (key+n_length < key_end) /* Normalize length based */
1632
key_end=key+n_length;
1633
if (sort_order) /* SerG */
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)))
1649
{ /* Key can't be re-packed */
1650
s_temp->next_key_pos=0;
1653
ref_length+=tmp_length;
1654
n_length-=tmp_length;
1655
length-=tmp_length+next_length_pack; /* We gained these chars */
1657
if (n_length == 0 && ref_length == new_key_length)
1659
s_temp->n_ref_length=pack_marker; /* Same as prev key */
1663
s_temp->n_ref_length=ref_length | pack_marker;
1664
length+= get_pack_length(n_length);
1665
s_temp->n_length=n_length;
1673
/* Length of key which is prefix compressed */
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,
1678
MI_KEY_PARAM *s_temp)
1680
uint32_t length,key_length,ref_length;
1682
s_temp->totlength=key_length=_mi_keylength(keyinfo,key)+nod_flag;
1684
s_temp->n_length= s_temp->n_ref_length=0; /* For valgrind */
1687
s_temp->prev_key=org_key;
1688
if (prev_key) /* If not first key in block */
1690
/* pack key against previous key */
1692
As keys may be identical when running a sort in myisamchk, we
1693
have to guard against the case where keys may be identical
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);
1703
/* No previous key */
1704
s_temp->ref_length=ref_length=0;
1705
length=key_length+1;
1707
if ((s_temp->next_key_pos=next_key)) /* If another key after */
1709
/* pack key against next key */
1710
uint32_t next_length,next_length_pack;
1711
get_key_pack_length(next_length,next_length_pack,next_key);
1713
/* If first key and next key is packed (only on delete) */
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)
1725
/* We put a key with different case between two keys with the same prefix
1726
Extend next key to have same prefix as
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));
1734
/* Check how many characters are identical to next key */
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;
1740
return length; /* can't pack next key */
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;
1752
** store a key packed with _mi_calc_xxx_key_length in page-buffert
1755
/* store key without compression */
1757
void _mi_store_static_key(MI_KEYDEF *keyinfo,
1758
register unsigned char *key_pos,
1759
register MI_KEY_PARAM *s_temp)
1762
memcpy(key_pos, s_temp->key, s_temp->totlength);
1766
/* store variable length key with prefix compression */
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,
1775
register MI_KEY_PARAM *s_temp)
1779
unsigned char *start;
1783
if (s_temp->ref_length)
1785
/* Packed against previous key */
1786
store_pack_length(s_temp->pack_marker == 128,key_pos,s_temp->ref_length);
1787
/* If not same key after */
1788
if (s_temp->ref_length != s_temp->pack_marker)
1789
store_key_length_inc(key_pos,s_temp->key_length);
1793
/* Not packed against previous key */
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) /* No following key */
1804
if (s_temp->prev_length)
1806
/* Extend next key because new key didn't have same prefix as prev key */
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)
1825
return; /* Identical key */
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);
1836
/* variable length key with prefix compression */
1838
void _mi_store_bin_pack_key(MI_KEYDEF *keyinfo,
1839
register unsigned char *key_pos,
1840
register MI_KEY_PARAM *s_temp)
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) /* If we must extend key */
1854
memcpy(key_pos,s_temp->prev_key,s_temp->prev_length);
added
removed
plugin/myisam/mi_search.cc
