1
/* Copyright (C) 2006 MySQL AB & MySQL Finland AB & TCX DataKonsult 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 "ma_fulltext.h"
21
static my_bool _ma_get_prev_key(MARIA_KEY *key, uchar *page, uchar *keypos);
24
/* Check that new index is ok */
26
int _ma_check_index(MARIA_HA *info, int inx)
28
if (inx < 0 || ! maria_is_key_active(info->s->state.key_map, inx))
30
my_errno=HA_ERR_WRONG_INDEX;
33
if (info->lastinx != inx) /* Index changed */
37
info->update= ((info->update & (HA_STATE_CHANGED | HA_STATE_ROW_CHANGED)) |
38
HA_STATE_NEXT_FOUND | HA_STATE_PREV_FOUND);
40
if (info->opt_flag & WRITE_CACHE_USED && flush_io_cache(&info->rec_cache))
43
} /* _ma_check_index */
47
@breif Search after row by a key
50
Position to row is stored in info->lastpos
53
@retval 0 ok (key found)
55
@retval 1 If one should continue search on higher level
58
int _ma_search(register MARIA_HA *info, MARIA_KEY *key, uint32 nextflag,
59
register my_off_t pos)
61
my_bool last_key_not_used;
63
uint page_flag, nod_flag, used_length;
64
uchar *keypos,*maxpos;
65
uchar lastkey[MARIA_MAX_KEY_BUFF],*buff;
66
MARIA_KEYDEF *keyinfo= key->keyinfo;
67
DBUG_ENTER("_ma_search");
68
DBUG_PRINT("enter",("pos: %lu nextflag: %u lastpos: %lu",
69
(ulong) pos, nextflag, (ulong) info->cur_row.lastpos));
70
DBUG_EXECUTE("key", _ma_print_key(DBUG_FILE, key););
72
if (pos == HA_OFFSET_ERROR)
74
my_errno=HA_ERR_KEY_NOT_FOUND; /* Didn't find key */
75
info->cur_row.lastpos= HA_OFFSET_ERROR;
76
if (!(nextflag & (SEARCH_SMALLER | SEARCH_BIGGER | SEARCH_LAST)))
77
DBUG_RETURN(-1); /* Not found ; return error */
78
DBUG_RETURN(1); /* Search at upper levels */
81
if (!(buff= _ma_fetch_keypage(info, keyinfo, pos,
82
PAGECACHE_LOCK_LEFT_UNLOCKED,
83
DFLT_INIT_HITS, info->keyread_buff,
84
test(!(nextflag & SEARCH_SAVE_BUFF)), 0)))
86
DBUG_DUMP("page", buff, _ma_get_page_used(info->s, buff));
88
flag= (*keyinfo->bin_search)(key, buff, nextflag, &keypos, lastkey,
90
if (flag == MARIA_FOUND_WRONG_KEY)
92
page_flag= _ma_get_keypage_flag(info->s, buff);
93
_ma_get_used_and_nod_with_flag(info->s, page_flag, buff, used_length,
95
maxpos= buff + used_length -1;
99
if ((error= _ma_search(info, key, nextflag,
100
_ma_kpos(nod_flag,keypos))) <= 0)
105
if (nextflag & (SEARCH_SMALLER | SEARCH_LAST) &&
106
keypos == buff + info->s->keypage_header + nod_flag)
107
DBUG_RETURN(1); /* Bigger than key */
109
else if (nextflag & SEARCH_BIGGER && keypos >= maxpos)
110
DBUG_RETURN(1); /* Smaller than key */
114
/* Found matching key */
115
if ((nextflag & SEARCH_FIND) && nod_flag &&
116
((keyinfo->flag & (HA_NOSAME | HA_NULL_PART)) != HA_NOSAME ||
117
(key->flag & SEARCH_PART_KEY) || info->s->base.born_transactional))
119
if ((error= _ma_search(info, key, nextflag,
120
_ma_kpos(nod_flag,keypos))) >= 0 ||
121
my_errno != HA_ERR_KEY_NOT_FOUND)
123
info->last_keypage= HA_OFFSET_ERROR; /* Buffer not in mem */
126
if (pos != info->last_keypage)
128
uchar *old_buff=buff;
129
if (!(buff= _ma_fetch_keypage(info,keyinfo, pos,
130
PAGECACHE_LOCK_LEFT_UNLOCKED,DFLT_INIT_HITS,
132
test(!(nextflag & SEARCH_SAVE_BUFF)), 0)))
134
keypos=buff+(keypos-old_buff);
135
maxpos=buff+(maxpos-old_buff);
138
info->last_key.keyinfo= keyinfo;
139
if ((nextflag & (SEARCH_SMALLER | SEARCH_LAST)) && flag != 0)
142
if (_ma_get_prev_key(&info->last_key, buff, keypos))
145
We have to use key->flag >> 1 here to transform
146
SEARCH_PAGE_KEY_HAS_TRANSID to SEARCH_USER_KEY_HAS_TRANSID
148
if (!(nextflag & SEARCH_SMALLER) &&
149
ha_key_cmp(keyinfo->seg, info->last_key.data, key->data,
150
key->data_length + key->ref_length,
151
SEARCH_FIND | (key->flag >> 1) | info->last_key.flag,
154
my_errno=HA_ERR_KEY_NOT_FOUND; /* Didn't find key */
160
/* Set info->last_key to temporarily point to last key value */
161
info->last_key.data= lastkey;
162
/* Get key value (if not packed key) and position after key */
163
if (!(*keyinfo->get_key)(&info->last_key, page_flag, nod_flag, &keypos))
165
memcpy(info->lastkey_buff, lastkey,
166
info->last_key.data_length + info->last_key.ref_length);
167
info->last_key.data= info->lastkey_buff;
169
info->cur_row.lastpos= _ma_row_pos_from_key(&info->last_key);
170
info->cur_row.trid= _ma_trid_from_key(&info->last_key);
171
/* Save position for a possible read next / previous */
172
info->int_keypos= info->keyread_buff+ (keypos-buff);
173
info->int_maxpos= info->keyread_buff+ (maxpos-buff);
174
info->int_nod_flag=nod_flag;
175
info->int_keytree_version=keyinfo->version;
176
info->last_search_keypage=info->last_keypage;
177
info->page_changed=0;
178
/* Set marker that buffer was used (Marker for mi_search_next()) */
179
info->keyread_buff_used= (info->keyread_buff != buff);
181
DBUG_PRINT("exit",("found key at %lu",(ulong) info->cur_row.lastpos));
185
DBUG_PRINT("exit",("Error: %d",my_errno));
186
info->cur_row.lastpos= HA_OFFSET_ERROR;
187
info->page_changed=1;
193
Search after key in page-block
196
@param key Search after this key
197
@param page Start of data page
198
@param comp_flag How key should be compared
200
@param buff Buffer for holding a key (not used here)
204
If keys are packed, then smaller or identical key is stored in buff
207
@retval <0, 0 , >0 depending on if if found is smaller, equal or bigger than
209
@retval ret_pos Points to where the identical or bigger key starts
210
@retval last_key Set to 1 if key is the last key in the page.
213
int _ma_bin_search(const MARIA_KEY *key, uchar *page,
214
uint32 comp_flag, uchar **ret_pos,
215
uchar *buff __attribute__((unused)), my_bool *last_key)
219
uint start, mid, end, save_end, totlength, nod_flag, used_length;
221
MARIA_KEYDEF *keyinfo= key->keyinfo;
222
MARIA_SHARE *share= keyinfo->share;
223
DBUG_ENTER("_ma_bin_search");
227
page_flag= _ma_get_keypage_flag(share, page);
228
if (page_flag & KEYPAGE_FLAG_HAS_TRANSID)
230
/* Keys have varying length, can't use binary search */
231
DBUG_RETURN(_ma_seq_search(key, page, comp_flag, ret_pos, buff, last_key));
234
_ma_get_used_and_nod_with_flag(share, page_flag, page, used_length,
236
totlength= keyinfo->keylength + nod_flag;
237
DBUG_ASSERT(used_length >= share->keypage_header + nod_flag + totlength);
241
save_end= end= ((used_length - nod_flag - share->keypage_header) /
243
DBUG_PRINT("test",("page_length: %u end: %u", used_length, end));
244
page+= share->keypage_header + nod_flag;
249
if ((flag=ha_key_cmp(keyinfo->seg, page + (uint) mid * totlength,
250
key->data, key->data_length + key->ref_length,
251
comp_flag, not_used))
258
flag=ha_key_cmp(keyinfo->seg, page + (uint) start * totlength,
259
key->data, key->data_length + key->ref_length, comp_flag,
262
start++; /* point at next, bigger key */
263
*ret_pos= (page + (uint) start * totlength);
264
*last_key= end == save_end;
265
DBUG_PRINT("exit",("flag: %d keypos: %d",flag,start));
267
} /* _ma_bin_search */
271
Locate a packed key in a key page.
274
@param key Search key.
275
@param page Key page (beginning).
276
@param comp_flag Search flags like SEARCH_SAME etc.
278
@param buff Buffer for holding temp keys
282
Used instead of _ma_bin_search() when key is packed.
283
Puts smaller or identical key in buff.
284
Key is searched sequentially.
287
Don't copy key to buffer if we are not using key with prefix packing
290
@retval > 0 Key in 'buff' is smaller than search key.
291
@retval 0 Key in 'buff' is identical to search key.
292
@retval < 0 Not found.
294
@retval ret_pos Points to where the identical or bigger key starts
295
@retval last_key Set to 1 if key is the last key in the page
296
@retval buff Copy of previous or identical unpacked key
299
int _ma_seq_search(const MARIA_KEY *key, uchar *page,
300
uint32 comp_flag, uchar **ret_pos,
301
uchar *buff, my_bool *last_key)
304
uint page_flag, nod_flag, length, used_length, not_used[2];
305
uchar t_buff[MARIA_MAX_KEY_BUFF], *end;
306
MARIA_KEYDEF *keyinfo= key->keyinfo;
307
MARIA_SHARE *share= keyinfo->share;
309
DBUG_ENTER("_ma_seq_search");
314
page_flag= _ma_get_keypage_flag(share, page);
315
_ma_get_used_and_nod_with_flag(share, page_flag, page, used_length,
317
end= page + used_length;
318
page+= share->keypage_header + nod_flag;
319
*ret_pos= (uchar*) page;
320
t_buff[0]=0; /* Avoid bugs */
322
tmp_key.data= t_buff;
323
tmp_key.keyinfo= keyinfo;
326
length=(*keyinfo->get_key)(&tmp_key, page_flag, nod_flag, &page);
327
if (length == 0 || page > end)
329
maria_print_error(share, HA_ERR_CRASHED);
330
my_errno=HA_ERR_CRASHED;
332
("Found wrong key: length: %u page: 0x%lx end: 0x%lx",
333
length, (long) page, (long) end));
334
DBUG_RETURN(MARIA_FOUND_WRONG_KEY);
336
if ((flag= ha_key_cmp(keyinfo->seg, t_buff, key->data,
337
key->data_length + key->ref_length,
338
comp_flag | tmp_key.flag,
342
DBUG_PRINT("loop",("page: 0x%lx key: '%s' flag: %d", (long) page, t_buff,
345
memcpy(buff,t_buff,length);
349
memcpy(buff,t_buff,length); /* Result is first key */
350
*last_key= page == end;
351
DBUG_PRINT("exit",("flag: %d ret_pos: 0x%lx", flag, (long) *ret_pos));
353
} /* _ma_seq_search */
357
Search for key on key page with string prefix compression
360
This is an optimized function compared to calling _ma_get_pack_key()
361
for each key in the buffer
363
Same interface as for _ma_seq_search()
366
int _ma_prefix_search(const MARIA_KEY *key, uchar *page,
367
uint32 nextflag, uchar **ret_pos, uchar *buff,
371
my_flag is raw comparison result to be changed according to
372
SEARCH_NO_FIND,SEARCH_LAST and HA_REVERSE_SORT flags.
373
flag is the value returned by ha_key_cmp and as treated as final
375
int flag=0, my_flag=-1;
376
uint nod_flag, used_length, length, len, matched, cmplen, kseg_len;
377
uint page_flag, prefix_len,suffix_len;
378
int key_len_skip, seg_len_pack, key_len_left;
380
uchar *vseg, *saved_vseg, *saved_from;
381
uchar tt_buff[MARIA_MAX_KEY_BUFF+2], *t_buff=tt_buff+2;
384
uint saved_length=0, saved_prefix_len=0;
386
MARIA_KEYDEF *keyinfo= key->keyinfo;
387
MARIA_SHARE *share= keyinfo->share;
388
uchar *sort_order= keyinfo->seg->charset->sort_order;
389
DBUG_ENTER("_ma_prefix_search");
392
LINT_INIT(prefix_len);
393
LINT_INIT(seg_len_pack);
394
LINT_INIT(saved_from);
396
LINT_INIT(saved_vseg);
398
t_buff[0]=0; /* Avoid bugs */
399
page_flag= _ma_get_keypage_flag(share, page);
400
_ma_get_used_and_nod_with_flag(share, page_flag, page, used_length,
402
page_flag&= KEYPAGE_FLAG_HAS_TRANSID; /* For faster test in loop */
403
end= page + used_length;
404
page+= share->keypage_header + nod_flag;
408
get_key_pack_length(kseg_len, length_pack, kseg);
409
key_len_skip=length_pack+kseg_len;
410
key_len_left=(int) (key->data_length + key->ref_length) - (int) key_len_skip;
411
/* If key_len is 0, then length_pack is 1, then key_len_left is -1. */
412
cmplen= ((key_len_left>=0) ? kseg_len :
413
(key->data_length + key->ref_length - length_pack));
414
DBUG_PRINT("info",("key: '%.*s'",kseg_len,kseg));
417
Keys are compressed the following way:
419
If the max length of first key segment <= 127 bytes the prefix is
420
1 uchar else it's 2 byte
422
(prefix) length The high bit is set if this is a prefix for the prev key.
423
[suffix length] Packed length of suffix if the previous was a prefix.
424
(suffix) data Key data bytes (past the common prefix or whole segment).
425
[next-key-seg] Next key segments (([packed length], data), ...)
426
pointer Reference to the data file (last_keyseg->length).
429
matched=0; /* how many char's from prefix were alredy matched */
430
len=0; /* length of previous key unpacked */
434
uint packed= *page & 128;
438
if (keyinfo->seg->length >= 127)
440
suffix_len=mi_uint2korr(vseg) & 32767;
444
suffix_len= *vseg++ & 127;
450
/* == 0x80 or 0x8000, same key, prefix length == old key length. */
455
/* > 0x80 or 0x8000, this is prefix lgt, packed suffix lgt follows. */
456
prefix_len=suffix_len;
457
get_key_length(suffix_len,vseg);
462
/* Not packed. No prefix used from last key. */
466
len=prefix_len+suffix_len;
467
seg_len_pack=get_pack_length(len);
468
t_buff=tt_buff+3-seg_len_pack;
469
store_key_length(t_buff,len);
471
if (prefix_len > saved_prefix_len)
472
memcpy(t_buff+seg_len_pack+saved_prefix_len,saved_vseg,
473
prefix_len-saved_prefix_len);
475
saved_prefix_len=prefix_len;
477
DBUG_PRINT("loop",("page: '%.*s%.*s'",prefix_len,t_buff+seg_len_pack,
480
/* Calculate length of one key */
481
uchar *from= vseg+suffix_len;
484
for (keyseg=keyinfo->seg+1 ; keyseg->type ; keyseg++ )
486
if (keyseg->flag & HA_NULL_PART)
491
if (keyseg->flag & (HA_VAR_LENGTH_PART | HA_BLOB_PART | HA_SPACE_PACK))
493
uint key_part_length;
494
get_key_length(key_part_length,from);
495
from+= key_part_length;
498
from+= keyseg->length;
500
from+= keyseg->length;
503
if (page_flag && key_has_transid(from-1))
505
from+= transid_packed_length(from);
506
key_flag= SEARCH_PAGE_KEY_HAS_TRANSID;
508
page= (uchar*) from+nod_flag;
509
length= (uint) (from-vseg);
514
maria_print_error(share, HA_ERR_CRASHED);
515
my_errno=HA_ERR_CRASHED;
517
("Found wrong key: length: %u page: 0x%lx end: %lx",
518
length, (long) page, (long) end));
519
DBUG_RETURN(MARIA_FOUND_WRONG_KEY);
522
if (matched >= prefix_len)
524
/* We have to compare. But we can still skip part of the key */
526
const uchar *k= kseg+prefix_len;
529
If prefix_len > cmplen then we are in the end-space comparison
530
phase. Do not try to acces the key any more ==> left= 0.
532
left= ((len <= cmplen) ? suffix_len :
533
((prefix_len < cmplen) ? cmplen - prefix_len : 0));
535
matched=prefix_len+left;
539
for (my_flag=0;left;left--)
540
if ((my_flag= (int) sort_order[*vseg++] - (int) sort_order[*k++]))
545
for (my_flag=0;left;left--)
546
if ((my_flag= (int) *vseg++ - (int) *k++))
550
if (my_flag>0) /* mismatch */
552
if (my_flag==0) /* match */
555
** len cmplen seg_left_len more_segs
556
** < matched=len; continue search
557
** > = prefix ? found : (matched=len;
566
if ((keyinfo->seg->type != HA_KEYTYPE_TEXT &&
567
keyinfo->seg->type != HA_KEYTYPE_VARTEXT1 &&
568
keyinfo->seg->type != HA_KEYTYPE_VARTEXT2))
572
/* We have to compare k and vseg as if they were space extended */
573
const uchar *k_end= k+ (cmplen - len);
574
for ( ; k < k_end && *k == ' '; k++) ;
576
goto cmp_rest; /* should never happen */
577
if ((uchar) *k < (uchar) ' ')
579
my_flag= 1; /* Compared string is smaller */
582
my_flag= -1; /* Continue searching */
585
else if (len > cmplen)
588
if ((nextflag & SEARCH_PREFIX) && key_len_left == 0)
591
/* We have to compare k and vseg as if they were space extended */
592
for (vseg_end= vseg + (len-cmplen) ;
593
vseg < vseg_end && *vseg == (uchar) ' ';
595
DBUG_ASSERT(vseg < vseg_end);
597
if ((uchar) *vseg > (uchar) ' ')
599
my_flag= 1; /* Compared string is smaller */
602
my_flag= -1; /* Continue searching */
610
if ((flag = ha_key_cmp(keyinfo->seg+1,vseg,
611
k, key_len_left, nextflag | key_flag,
618
at this line flag==-1 if the following lines were already
619
visited and 0 otherwise, i.e. flag <=0 here always !!!
622
DBUG_ASSERT(flag <= 0);
623
if (nextflag & (SEARCH_NO_FIND | SEARCH_LAST))
624
flag=(nextflag & (SEARCH_BIGGER | SEARCH_LAST)) ? -1 : 1;
632
/* else (matched < prefix_len) ---> do nothing. */
634
memcpy(buff,t_buff,saved_length=seg_len_pack+prefix_len);
635
saved_to= buff+saved_length;
636
saved_from= saved_vseg;
641
flag=(keyinfo->seg->flag & HA_REVERSE_SORT) ? -my_flag : my_flag;
644
memcpy(buff,t_buff,saved_length=seg_len_pack+prefix_len);
645
saved_to= buff+saved_length;
646
saved_from= saved_vseg;
650
memcpy(saved_to, (uchar*) saved_from, saved_length);
652
*last_key= page == end;
654
DBUG_PRINT("exit",("flag: %d ret_pos: 0x%lx", flag, (long) *ret_pos));
656
} /* _ma_prefix_search */
659
/* Get pos to a key_block */
661
my_off_t _ma_kpos(uint nod_flag, const uchar *after_key)
667
return mi_uint7korr(after_key)*maria_block_size;
669
return mi_uint6korr(after_key)*maria_block_size;
671
return mi_uint5korr(after_key)*maria_block_size;
681
return ((my_off_t) mi_uint4korr(after_key))*maria_block_size;
683
return ((my_off_t) mi_uint3korr(after_key))*maria_block_size;
685
return (my_off_t) (mi_uint2korr(after_key)*maria_block_size);
687
return (uint) (*after_key)*maria_block_size;
688
case 0: /* At leaf page */
689
default: /* Impossible */
690
return(HA_OFFSET_ERROR);
695
/* Save pos to a key_block */
697
void _ma_kpointer(register MARIA_HA *info, register uchar *buff, my_off_t pos)
699
pos/=maria_block_size;
700
switch (info->s->base.key_reflength) {
702
case 7: mi_int7store(buff,pos); break;
703
case 6: mi_int6store(buff,pos); break;
704
case 5: mi_int5store(buff,pos); break;
713
case 4: mi_int4store(buff,pos); break;
714
case 3: mi_int3store(buff,pos); break;
715
case 2: mi_int2store(buff,(uint) pos); break;
716
case 1: buff[0]= (uchar) pos; break;
717
default: abort(); /* impossible */
722
/* Calc pos to a data-record from a key */
724
MARIA_RECORD_POS _ma_row_pos_from_key(const MARIA_KEY *key)
727
const uchar *after_key= key->data + key->data_length;
728
MARIA_SHARE *share= key->keyinfo->share;
729
switch (share->rec_reflength) {
731
case 8: pos= (my_off_t) mi_uint8korr(after_key); break;
732
case 7: pos= (my_off_t) mi_uint7korr(after_key); break;
733
case 6: pos= (my_off_t) mi_uint6korr(after_key); break;
734
case 5: pos= (my_off_t) mi_uint5korr(after_key); break;
736
case 8: pos= (my_off_t) mi_uint4korr(after_key+4); break;
737
case 7: pos= (my_off_t) mi_uint4korr(after_key+3); break;
738
case 6: pos= (my_off_t) mi_uint4korr(after_key+2); break;
739
case 5: pos= (my_off_t) mi_uint4korr(after_key+1); break;
741
case 4: pos= (my_off_t) mi_uint4korr(after_key); break;
742
case 3: pos= (my_off_t) mi_uint3korr(after_key); break;
743
case 2: pos= (my_off_t) mi_uint2korr(after_key); break;
745
pos=0L; /* Shut compiler up */
747
return (*share->keypos_to_recpos)(share, pos);
754
@param key Maria key read from a page
756
@retval 0 If key doesn't have a trid
760
TrID _ma_trid_from_key(const MARIA_KEY *key)
762
if (!(key->flag & (SEARCH_PAGE_KEY_HAS_TRANSID |
763
SEARCH_USER_KEY_HAS_TRANSID)))
765
return transid_get_packed(key->keyinfo->share,
766
key->data + key->data_length +
767
key->keyinfo->share->rec_reflength);
771
/* Calc position from a record pointer ( in delete link chain ) */
773
MARIA_RECORD_POS _ma_rec_pos(MARIA_SHARE *share, uchar *ptr)
776
switch (share->rec_reflength) {
779
pos= (my_off_t) mi_uint8korr(ptr);
780
if (pos == HA_OFFSET_ERROR)
781
return HA_OFFSET_ERROR; /* end of list */
784
pos= (my_off_t) mi_uint7korr(ptr);
785
if (pos == (((my_off_t) 1) << 56) -1)
786
return HA_OFFSET_ERROR; /* end of list */
789
pos= (my_off_t) mi_uint6korr(ptr);
790
if (pos == (((my_off_t) 1) << 48) -1)
791
return HA_OFFSET_ERROR; /* end of list */
794
pos= (my_off_t) mi_uint5korr(ptr);
795
if (pos == (((my_off_t) 1) << 40) -1)
796
return HA_OFFSET_ERROR; /* end of list */
803
ptr+= (share->rec_reflength-4);
807
pos= (my_off_t) mi_uint4korr(ptr);
808
if (pos == (my_off_t) (uint32) ~0L)
809
return HA_OFFSET_ERROR;
812
pos= (my_off_t) mi_uint3korr(ptr);
813
if (pos == (my_off_t) (1 << 24) -1)
814
return HA_OFFSET_ERROR;
817
pos= (my_off_t) mi_uint2korr(ptr);
818
if (pos == (my_off_t) (1 << 16) -1)
819
return HA_OFFSET_ERROR;
821
default: abort(); /* Impossible */
823
return (*share->keypos_to_recpos)(share, pos);
827
/* save position to record */
829
void _ma_dpointer(MARIA_SHARE *share, uchar *buff, my_off_t pos)
831
if (pos != HA_OFFSET_ERROR)
832
pos= (*share->recpos_to_keypos)(share, pos);
834
switch (share->rec_reflength) {
836
case 8: mi_int8store(buff,pos); break;
837
case 7: mi_int7store(buff,pos); break;
838
case 6: mi_int6store(buff,pos); break;
839
case 5: mi_int5store(buff,pos); break;
850
case 4: mi_int4store(buff,pos); break;
851
case 3: mi_int3store(buff,pos); break;
852
case 2: mi_int2store(buff,(uint) pos); break;
853
default: abort(); /* Impossible */
858
my_off_t _ma_static_keypos_to_recpos(MARIA_SHARE *share, my_off_t pos)
860
return pos * share->base.pack_reclength;
864
my_off_t _ma_static_recpos_to_keypos(MARIA_SHARE *share, my_off_t pos)
866
return pos / share->base.pack_reclength;
869
my_off_t _ma_transparent_recpos(MARIA_SHARE *share __attribute__((unused)),
875
my_off_t _ma_transaction_keypos_to_recpos(MARIA_SHARE *share
876
__attribute__((unused)),
879
/* We need one bit to store if there is transid's after position */
883
my_off_t _ma_transaction_recpos_to_keypos(MARIA_SHARE *share
884
__attribute__((unused)),
891
@brief Get key from key-block
893
@param key Should contain previous key. Will contain new key
894
@param page_flag Flag on page block
895
@param nod_flag Is set to nod length if we on nod
896
@param page Points at previous key; Its advanced to point at next key
899
Same as _ma_get_key but used with fixed length keys
902
@retval key_length + length of data pointer (without nod length)
905
uint _ma_get_static_key(MARIA_KEY *key, uint page_flag, uint nod_flag,
906
register uchar **page)
908
register MARIA_KEYDEF *keyinfo= key->keyinfo;
909
size_t key_length= keyinfo->keylength;
911
key->ref_length= keyinfo->share->rec_reflength;
912
key->data_length= key_length - key->ref_length;
914
if (page_flag & KEYPAGE_FLAG_HAS_TRANSID)
916
uchar *end= *page + keyinfo->keylength;
917
if (key_has_transid(end-1))
919
uint trans_length= transid_packed_length(end);
920
key->ref_length+= trans_length;
921
key_length+= trans_length;
922
key->flag= SEARCH_PAGE_KEY_HAS_TRANSID;
925
key_length+= nod_flag;
926
memcpy(key->data, *page, key_length);
928
return key_length - nod_flag;
929
} /* _ma_get_static_key */
933
Skip over static length key from key-block
935
@fn _ma_skip_pack_key()
936
@param key Keyinfo and buffer that can be used
937
@param nod_flag If nod: Length of node pointer, else zero.
938
@param key Points at key
940
@retval pointer to next key
943
uchar *_ma_skip_static_key(MARIA_KEY *key, uint page_flag,
944
uint nod_flag, uchar *page)
946
page+= key->keyinfo->keylength;
947
if ((page_flag & KEYPAGE_FLAG_HAS_TRANSID) && key_has_transid(page-1))
948
page+= transid_packed_length(page);
949
return page+ nod_flag;
954
get key which is packed against previous key or key with a NULL column.
958
@param int_key Should contain previous key. Will contain new key
959
@param page_flag page_flag from page
960
@param nod_flag If nod: Length of node pointer, else zero.
961
@param page_pos Points at previous key; Its advanced to point at next key
964
@retval key_length + length of data pointer
967
uint _ma_get_pack_key(MARIA_KEY *int_key, uint page_flag,
968
uint nod_flag, uchar **page_pos)
970
reg1 HA_KEYSEG *keyseg;
971
uchar *page= *page_pos;
973
uchar *key= int_key->data;
974
MARIA_KEYDEF *keyinfo= int_key->keyinfo;
976
for (keyseg=keyinfo->seg ; keyseg->type ;keyseg++)
978
if (keyseg->flag & HA_PACK_KEY)
980
/* key with length, packed to previous key */
982
uint packed= *page & 128,tot_length,rest_length;
983
if (keyseg->length >= 127)
985
length=mi_uint2korr(page) & 32767;
989
length= *page++ & 127;
993
if (length > (uint) keyseg->length)
995
maria_print_error(keyinfo->share, HA_ERR_CRASHED);
996
my_errno=HA_ERR_CRASHED;
997
return 0; /* Error */
999
if (length == 0) /* Same key */
1001
if (keyseg->flag & HA_NULL_PART)
1002
*key++=1; /* Can't be NULL */
1003
get_key_length(length,key);
1004
key+= length; /* Same diff_key as prev */
1005
if (length > keyseg->length)
1008
("Found too long null packed key: %u of %u at 0x%lx",
1009
length, keyseg->length, (long) *page_pos));
1010
DBUG_DUMP("key", *page_pos, 16);
1011
maria_print_error(keyinfo->share, HA_ERR_CRASHED);
1012
my_errno=HA_ERR_CRASHED;
1017
if (keyseg->flag & HA_NULL_PART)
1019
key++; /* Skip null marker*/
1023
get_key_length(rest_length,page);
1024
tot_length=rest_length+length;
1026
/* If the stored length has changed, we must move the key */
1027
if (tot_length >= 255 && *start != 255)
1029
/* length prefix changed from a length of one to a length of 3 */
1030
bmove_upp(key+length+3, key+length+1, length);
1032
mi_int2store(key+1,tot_length);
1035
else if (tot_length < 255 && *start == 255)
1037
bmove(key+1,key+3,length);
1043
store_key_length_inc(key,tot_length);
1046
memcpy(key,page,rest_length);
1053
if (keyseg->flag & HA_NULL_PART)
1055
if (!length--) /* Null part */
1060
*key++=1; /* Not null */
1063
if (length > (uint) keyseg->length)
1065
DBUG_PRINT("error",("Found too long packed key: %u of %u at 0x%lx",
1066
length, keyseg->length, (long) *page_pos));
1067
DBUG_DUMP("key", *page_pos, 16);
1068
maria_print_error(keyinfo->share, HA_ERR_CRASHED);
1069
my_errno=HA_ERR_CRASHED;
1070
return 0; /* Error */
1072
store_key_length_inc(key,length);
1076
if (keyseg->flag & HA_NULL_PART)
1078
if (!(*key++ = *page++))
1082
(HA_VAR_LENGTH_PART | HA_BLOB_PART | HA_SPACE_PACK))
1085
get_key_length(length,tmp);
1086
length+=(uint) (tmp-page);
1089
length=keyseg->length;
1091
memcpy((uchar*) key,(uchar*) page,(size_t) length);
1096
int_key->data_length= (key - int_key->data);
1098
length= keyseg->length;
1099
if (page_flag & KEYPAGE_FLAG_HAS_TRANSID)
1101
uchar *end= page + length;
1102
if (key_has_transid(end-1))
1104
length+= transid_packed_length(end);
1105
int_key->flag= SEARCH_PAGE_KEY_HAS_TRANSID;
1108
int_key->ref_length= length;
1110
bmove(key, page, length);
1111
*page_pos= page+length;
1113
return (int_key->data_length + int_key->ref_length);
1114
} /* _ma_get_pack_key */
1118
skip key which is packed against previous key or key with a NULL column.
1120
@fn _ma_skip_pack_key()
1121
@param key Keyinfo and buffer that can be used
1122
@param nod_flag If nod: Length of node pointer, else zero.
1123
@param key Points at key
1125
@retval pointer to next key
1128
uchar *_ma_skip_pack_key(MARIA_KEY *key, uint page_flag,
1129
uint nod_flag, uchar *page)
1131
reg1 HA_KEYSEG *keyseg;
1132
for (keyseg= key->keyinfo->seg ; keyseg->type ; keyseg++)
1134
if (keyseg->flag & HA_PACK_KEY)
1136
/* key with length, packed to previous key */
1137
uint packed= *page & 128, length;
1138
if (keyseg->length >= 127)
1140
length= mi_uint2korr(page) & 32767;
1144
length= *page++ & 127;
1148
if (length == 0) /* Same key */
1150
get_key_length(length,page);
1158
if (keyseg->flag & HA_NULL_PART)
1161
if (keyseg->flag & (HA_SPACE_PACK | HA_BLOB_PART | HA_VAR_LENGTH_PART))
1164
get_key_length(length,page);
1168
page+= keyseg->length;
1171
page+= keyseg->length;
1172
if ((page_flag & KEYPAGE_FLAG_HAS_TRANSID) && key_has_transid(page-1))
1173
page+= transid_packed_length(page);
1174
return page + nod_flag;
1178
/* Read key that is packed relatively to previous */
1180
uint _ma_get_binary_pack_key(MARIA_KEY *int_key, uint page_flag, uint nod_flag,
1181
register uchar **page_pos)
1183
reg1 HA_KEYSEG *keyseg;
1184
uchar *page, *page_end, *from, *from_end, *key;
1186
MARIA_KEYDEF *keyinfo= int_key->keyinfo;
1187
DBUG_ENTER("_ma_get_binary_pack_key");
1190
page_end=page + MARIA_MAX_KEY_BUFF + 1;
1194
Keys are compressed the following way:
1196
prefix length Packed length of prefix common with prev key.
1198
for each key segment:
1199
[is null] Null indicator if can be null (1 byte, zero means null)
1200
[length] Packed length if varlength (1 or 3 bytes)
1201
key segment 'length' bytes of key segment value
1202
pointer Reference to the data file (last_keyseg->length).
1204
get_key_length() is a macro. It gets the prefix length from 'page'
1205
and puts it into 'length'. It increments 'page' by 1 or 3, depending
1206
on the packed length of the prefix length.
1208
get_key_length(length,page);
1211
if (length > keyinfo->maxlength)
1214
("Found too long binary packed key: %u of %u at 0x%lx",
1215
length, keyinfo->maxlength, (long) *page_pos));
1216
DBUG_DUMP("key", *page_pos, 16);
1217
maria_print_error(keyinfo->share, HA_ERR_CRASHED);
1218
my_errno=HA_ERR_CRASHED;
1219
DBUG_RETURN(0); /* Wrong key */
1221
/* Key is packed against prev key, take prefix from prev key. */
1223
from_end= key + length;
1227
/* Key is not packed against prev key, take all from page buffer. */
1233
The trouble is that key can be split in two parts:
1234
The first part (prefix) is in from .. from_end - 1.
1235
The second part starts at page.
1236
The split can be at every byte position. So we need to check for
1237
the end of the first part before using every byte.
1239
for (keyseg=keyinfo->seg ; keyseg->type ;keyseg++)
1241
if (keyseg->flag & HA_NULL_PART)
1243
/* If prefix is used up, switch to rest. */
1244
if (from == from_end)
1249
if (!(*key++ = *from++))
1250
continue; /* Null part */
1252
if (keyseg->flag & (HA_VAR_LENGTH_PART | HA_BLOB_PART | HA_SPACE_PACK))
1254
/* If prefix is used up, switch to rest. */
1255
if (from == from_end) { from=page; from_end=page_end; }
1256
/* Get length of dynamic length key part */
1257
if ((length= (uint) (uchar) (*key++ = *from++)) == 255)
1259
/* If prefix is used up, switch to rest. */
1260
if (from == from_end) { from=page; from_end=page_end; }
1261
length= ((uint) (uchar) ((*key++ = *from++))) << 8;
1262
/* If prefix is used up, switch to rest. */
1263
if (from == from_end) { from=page; from_end=page_end; }
1264
length+= (uint) (uchar) ((*key++ = *from++));
1268
length=keyseg->length;
1270
if ((tmp=(uint) (from_end-from)) <= length)
1272
key+=tmp; /* Use old key */
1274
from=page; from_end=page_end;
1276
DBUG_ASSERT((int) length >= 0);
1277
DBUG_PRINT("info",("key: 0x%lx from: 0x%lx length: %u",
1278
(long) key, (long) from, length));
1279
memmove((uchar*) key, (uchar*) from, (size_t) length);
1284
Last segment (type == 0) contains length of data pointer.
1285
If we have mixed key blocks with data pointer and key block pointer,
1286
we have to copy both.
1288
int_key->data_length= (key - int_key->data);
1289
int_key->ref_length= length= keyseg->length;
1291
if ((tmp=(uint) (from_end-from)) <= length)
1293
/* Skip over the last common part of the data */
1301
Remaining length is greater than max possible length.
1302
This can happen only if we switched to the new key bytes already.
1303
'page_end' is calculated with MARIA_MAX_KEY_BUFF. So it can be far
1304
behind the real end of the key.
1306
if (from_end != page_end)
1308
DBUG_PRINT("error",("Error when unpacking key"));
1309
maria_print_error(keyinfo->share, HA_ERR_CRASHED);
1310
my_errno=HA_ERR_CRASHED;
1311
DBUG_RETURN(0); /* Error */
1314
if (page_flag & KEYPAGE_FLAG_HAS_TRANSID)
1316
uchar *end= from + length;
1317
if (key_has_transid(end-1))
1319
uint trans_length= transid_packed_length(end);
1320
length+= trans_length;
1321
int_key->ref_length+= trans_length;
1322
int_key->flag= SEARCH_PAGE_KEY_HAS_TRANSID;
1326
/* Copy rest of data ptr and, if appropriate, trans_id and node_ptr */
1327
memcpy(key, from, length);
1328
*page_pos= from + length + nod_flag;
1330
DBUG_RETURN(int_key->data_length + int_key->ref_length);
1334
skip key which is ptefix packed against previous key
1336
@fn _ma_skip_binary_key()
1337
@param key Keyinfo and buffer that can be used
1338
@param nod_flag If nod: Length of node pointer, else zero.
1339
@param key Points at key
1342
We have to copy the key as otherwise we don't know how much left
1343
data there is of the key.
1346
Implement more efficient version of this. We can ignore to copy any rest
1347
key parts that are not null or not packed. We also don't have to copy
1350
@retval pointer to next key
1353
uchar *_ma_skip_binary_pack_key(MARIA_KEY *key, uint page_flag,
1354
uint nod_flag, uchar *page)
1356
if (!_ma_get_binary_pack_key(key, page_flag, nod_flag, &page))
1363
@brief Get key at position without knowledge of previous key
1365
@return pointer to next key
1368
uchar *_ma_get_key(MARIA_KEY *key, uchar *page, uchar *keypos)
1370
uint page_flag, nod_flag;
1371
MARIA_KEYDEF *keyinfo= key->keyinfo;
1372
DBUG_ENTER("_ma_get_key");
1374
page_flag= _ma_get_keypage_flag(keyinfo->share, page);
1375
nod_flag= _ma_test_if_nod(keyinfo->share, page);
1377
if (! (keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)) &&
1378
! (page_flag & KEYPAGE_FLAG_HAS_TRANSID))
1380
bmove(key->data, keypos, keyinfo->keylength+nod_flag);
1381
key->ref_length= keyinfo->share->rec_reflength;
1382
key->data_length= keyinfo->keylength - key->ref_length;
1384
DBUG_RETURN(keypos+keyinfo->keylength+nod_flag);
1388
page+= keyinfo->share->keypage_header + nod_flag;
1389
key->data[0]= 0; /* safety */
1390
while (page <= keypos)
1392
if (!(*keyinfo->get_key)(key, page_flag, nod_flag, &page))
1394
maria_print_error(keyinfo->share, HA_ERR_CRASHED);
1395
my_errno=HA_ERR_CRASHED;
1400
DBUG_PRINT("exit",("page: 0x%lx length: %u", (long) page,
1401
key->data_length + key->ref_length));
1407
@brief Get key at position without knowledge of previous key
1414
static my_bool _ma_get_prev_key(MARIA_KEY *key, uchar *page, uchar *keypos)
1416
uint page_flag, nod_flag;
1417
MARIA_KEYDEF *keyinfo= key->keyinfo;
1418
DBUG_ENTER("_ma_get_prev_key");
1420
page_flag= _ma_get_keypage_flag(keyinfo->share, page);
1421
nod_flag= _ma_test_if_nod(keyinfo->share, page);
1423
if (! (keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)) &&
1424
! (page_flag & KEYPAGE_FLAG_HAS_TRANSID))
1426
bmove(key->data, keypos - keyinfo->keylength - nod_flag,
1427
keyinfo->keylength);
1428
key->ref_length= keyinfo->share->rec_reflength;
1429
key->data_length= keyinfo->keylength - key->ref_length;
1435
page+= keyinfo->share->keypage_header + nod_flag;
1436
key->data[0]= 0; /* safety */
1437
DBUG_ASSERT(page != keypos);
1438
while (page < keypos)
1440
if (! (*keyinfo->get_key)(key, page_flag, nod_flag, &page))
1442
maria_print_error(keyinfo->share, HA_ERR_CRASHED);
1443
my_errno=HA_ERR_CRASHED;
1449
} /* _ma_get_prev_key */
1453
@brief Get last key from key-page before 'endpos'
1456
endpos may be either end of buffer or start of a key
1459
@retval pointer to where key starts
1462
uchar *_ma_get_last_key(MARIA_KEY *key, uchar *page, uchar *endpos)
1464
uint page_flag,nod_flag;
1466
MARIA_KEYDEF *keyinfo= key->keyinfo;
1467
DBUG_ENTER("_ma_get_last_key");
1468
DBUG_PRINT("enter",("page: 0x%lx endpos: 0x%lx", (long) page,
1471
page_flag= _ma_get_keypage_flag(keyinfo->share, page);
1472
nod_flag= _ma_test_if_nod(keyinfo->share, page);
1473
if (! (keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)) &&
1474
! (page_flag & KEYPAGE_FLAG_HAS_TRANSID))
1476
lastpos= endpos-keyinfo->keylength-nod_flag;
1477
key->ref_length= keyinfo->share->rec_reflength;
1478
key->data_length= keyinfo->keylength - key->ref_length;
1481
bmove(key->data, lastpos, keyinfo->keylength + nod_flag);
1485
page+= keyinfo->share->keypage_header + nod_flag;
1487
key->data[0]=0; /* safety */
1488
while (page < endpos)
1491
if (!(*keyinfo->get_key)(key, page_flag, nod_flag, &page))
1493
DBUG_PRINT("error",("Couldn't find last key: page: 0x%lx",
1495
maria_print_error(keyinfo->share, HA_ERR_CRASHED);
1496
my_errno=HA_ERR_CRASHED;
1501
DBUG_PRINT("exit",("lastpos: 0x%lx length: %u", (ulong) lastpos,
1502
key->data_length + key->ref_length));
1503
DBUG_RETURN(lastpos);
1504
} /* _ma_get_last_key */
1508
Calculate length of unpacked key
1510
@param info Maria handler
1511
@param keyinfo key handler
1512
@param key data for key
1515
This function is very seldom used. It's mainly used for debugging
1516
or when calculating a key length from a stored key in batch insert.
1518
This function does *NOT* calculate length of transid size!
1519
This function can't be used against a prefix packed key on a page
1522
@retval total length for key
1525
uint _ma_keylength(MARIA_KEYDEF *keyinfo, const uchar *key)
1527
reg1 HA_KEYSEG *keyseg;
1530
if (! (keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)))
1531
return (keyinfo->keylength);
1534
for (keyseg=keyinfo->seg ; keyseg->type ; keyseg++)
1536
if (keyseg->flag & HA_NULL_PART)
1539
if (keyseg->flag & (HA_SPACE_PACK | HA_BLOB_PART | HA_VAR_LENGTH_PART))
1542
get_key_length(length,key);
1546
key+= keyseg->length;
1548
return((uint) (key-start)+keyseg->length);
1549
} /* _ma_keylength */
1553
Calculate length of part key.
1555
Used in maria_rkey() to find the key found for the key-part that was used.
1556
This is needed in case of multi-byte character sets where we may search
1557
after '0xDF' but find 'ss'
1560
uint _ma_keylength_part(MARIA_KEYDEF *keyinfo, register const uchar *key,
1563
reg1 HA_KEYSEG *keyseg;
1564
const uchar *start= key;
1566
for (keyseg=keyinfo->seg ; keyseg != end ; keyseg++)
1568
if (keyseg->flag & HA_NULL_PART)
1571
if (keyseg->flag & (HA_SPACE_PACK | HA_BLOB_PART | HA_VAR_LENGTH_PART))
1574
get_key_length(length,key);
1578
key+= keyseg->length;
1580
return (uint) (key-start);
1585
Find next/previous record with same key
1588
This can't be used when database is touched after last read
1591
int _ma_search_next(register MARIA_HA *info, MARIA_KEY *key,
1592
uint32 nextflag, my_off_t pos)
1595
uint page_flag,nod_flag;
1596
uchar lastkey[MARIA_MAX_KEY_BUFF];
1597
MARIA_KEYDEF *keyinfo= key->keyinfo;
1599
DBUG_ENTER("_ma_search_next");
1600
DBUG_PRINT("enter",("nextflag: %u lastpos: %lu int_keypos: 0x%lx page_changed %d keyread_buff_used: %d",
1601
nextflag, (ulong) info->cur_row.lastpos,
1602
(ulong) info->int_keypos,
1603
info->page_changed, info->keyread_buff_used));
1604
DBUG_EXECUTE("key", _ma_print_key(DBUG_FILE, key););
1607
Force full read if we are at last key or if we are not on a leaf
1608
and the key tree has changed since we used it last time
1609
Note that even if the key tree has changed since last read, we can use
1610
the last read data from the leaf if we haven't used the buffer for
1614
if (((nextflag & SEARCH_BIGGER) && info->int_keypos >= info->int_maxpos) ||
1615
info->page_changed ||
1616
(info->int_keytree_version != keyinfo->version &&
1617
(info->int_nod_flag || info->keyread_buff_used)))
1618
DBUG_RETURN(_ma_search(info, key, nextflag | SEARCH_SAVE_BUFF,
1621
if (info->keyread_buff_used)
1623
if (!_ma_fetch_keypage(info, keyinfo, info->last_search_keypage,
1624
PAGECACHE_LOCK_LEFT_UNLOCKED,
1625
DFLT_INIT_HITS, info->keyread_buff, 0, 0))
1627
info->keyread_buff_used=0;
1630
/* Last used buffer is in info->keyread_buff */
1631
page_flag= _ma_get_keypage_flag(keyinfo->share, info->keyread_buff);
1632
nod_flag= _ma_test_if_nod(keyinfo->share, info->keyread_buff);
1634
tmp_key.data= lastkey;
1635
info->last_key.keyinfo= tmp_key.keyinfo= keyinfo;
1637
if (nextflag & SEARCH_BIGGER) /* Next key */
1641
my_off_t tmp_pos= _ma_kpos(nod_flag,info->int_keypos);
1643
if ((error= _ma_search(info, key, nextflag | SEARCH_SAVE_BUFF,
1647
if (keyinfo->flag & (HA_PACK_KEY | HA_BINARY_PACK_KEY) &&
1648
info->last_key.data != key->data)
1649
memcpy(info->last_key.data, key->data,
1650
key->data_length + key->ref_length);
1651
if (!(*keyinfo->get_key)(&info->last_key, page_flag, nod_flag,
1655
else /* Previous key */
1657
/* Find start of previous key */
1658
info->int_keypos= _ma_get_last_key(&tmp_key, info->keyread_buff,
1660
if (!info->int_keypos)
1662
if (info->int_keypos == info->keyread_buff + info->s->keypage_header)
1664
/* Previous key was first key, read key before this one */
1665
DBUG_RETURN(_ma_search(info, key, nextflag | SEARCH_SAVE_BUFF,
1669
(error= _ma_search(info, key, nextflag | SEARCH_SAVE_BUFF,
1670
_ma_kpos(nod_flag,info->int_keypos))) <= 0)
1673
/* QQ: We should be able to optimize away the following call */
1674
if (! _ma_get_last_key(&info->last_key, info->keyread_buff,
1678
info->cur_row.lastpos= _ma_row_pos_from_key(&info->last_key);
1679
info->cur_row.trid= _ma_trid_from_key(&info->last_key);
1680
DBUG_PRINT("exit",("found key at %lu",(ulong) info->cur_row.lastpos));
1682
} /* _ma_search_next */
1686
Search after position for the first row in an index
1689
Found row is stored in info->cur_row.lastpos
1692
int _ma_search_first(register MARIA_HA *info, register MARIA_KEYDEF *keyinfo,
1693
register my_off_t pos)
1695
uint page_flag, nod_flag;
1697
MARIA_SHARE *share= info->s;
1698
DBUG_ENTER("_ma_search_first");
1700
if (pos == HA_OFFSET_ERROR)
1702
my_errno=HA_ERR_KEY_NOT_FOUND;
1703
info->cur_row.lastpos= HA_OFFSET_ERROR;
1709
if (!_ma_fetch_keypage(info, keyinfo, pos, PAGECACHE_LOCK_LEFT_UNLOCKED,
1710
DFLT_INIT_HITS, info->keyread_buff, 0, 0))
1712
info->cur_row.lastpos= HA_OFFSET_ERROR;
1715
page_flag= _ma_get_keypage_flag(share, info->keyread_buff);
1716
nod_flag= _ma_test_if_nod(share, info->keyread_buff);
1717
page= info->keyread_buff + share->keypage_header + nod_flag;
1718
} while ((pos= _ma_kpos(nod_flag,page)) != HA_OFFSET_ERROR);
1720
info->last_key.keyinfo= keyinfo;
1722
if (!(*keyinfo->get_key)(&info->last_key, page_flag, nod_flag, &page))
1723
DBUG_RETURN(-1); /* Crashed */
1725
info->int_keypos=page;
1726
info->int_maxpos= (info->keyread_buff +
1727
_ma_get_page_used(share, info->keyread_buff)-1);
1728
info->int_nod_flag=nod_flag;
1729
info->int_keytree_version=keyinfo->version;
1730
info->last_search_keypage=info->last_keypage;
1731
info->page_changed=info->keyread_buff_used=0;
1732
info->cur_row.lastpos= _ma_row_pos_from_key(&info->last_key);
1733
info->cur_row.trid= _ma_trid_from_key(&info->last_key);
1735
DBUG_PRINT("exit",("found key at %lu", (ulong) info->cur_row.lastpos));
1737
} /* _ma_search_first */
1741
Search after position for the last row in an index
1744
Found row is stored in info->cur_row.lastpos
1747
int _ma_search_last(register MARIA_HA *info, register MARIA_KEYDEF *keyinfo,
1748
register my_off_t pos)
1750
uint page_flag, nod_flag;
1751
uchar *buff,*end_of_page;
1752
DBUG_ENTER("_ma_search_last");
1754
if (pos == HA_OFFSET_ERROR)
1756
my_errno=HA_ERR_KEY_NOT_FOUND; /* Didn't find key */
1757
info->cur_row.lastpos= HA_OFFSET_ERROR;
1761
buff=info->keyread_buff;
1765
if (!_ma_fetch_keypage(info, keyinfo, pos, PAGECACHE_LOCK_LEFT_UNLOCKED,
1766
DFLT_INIT_HITS, buff, 0, 0))
1768
info->cur_row.lastpos= HA_OFFSET_ERROR;
1771
page_flag= _ma_get_keypage_flag(info->s, info->keyread_buff);
1772
_ma_get_used_and_nod_with_flag(info->s, page_flag, buff, used_length,
1774
end_of_page= buff + used_length;
1775
} while ((pos= _ma_kpos(nod_flag, end_of_page)) != HA_OFFSET_ERROR);
1777
info->last_key.keyinfo= keyinfo;
1779
if (!_ma_get_last_key(&info->last_key, buff, end_of_page))
1781
info->cur_row.lastpos= _ma_row_pos_from_key(&info->last_key);
1782
info->cur_row.trid= _ma_trid_from_key(&info->last_key);
1783
info->int_keypos= info->int_maxpos= end_of_page;
1784
info->int_nod_flag=nod_flag;
1785
info->int_keytree_version=keyinfo->version;
1786
info->last_search_keypage=info->last_keypage;
1787
info->page_changed=info->keyread_buff_used=0;
1789
DBUG_PRINT("exit",("found key at %lu",(ulong) info->cur_row.lastpos));
1791
} /* _ma_search_last */
1795
/****************************************************************************
1797
** Functions to store and pack a key in a page
1799
** maria_calc_xx_key_length takes the following arguments:
1800
** nod_flag If nod: Length of nod-pointer
1801
** next_key Position to pos after the new key in buffer
1802
** org_key Key that was before the next key in buffer
1803
** prev_key Last key before current key
1804
** key Key that will be stored
1805
** s_temp Information how next key will be packed
1806
****************************************************************************/
1808
/* Static length key */
1811
_ma_calc_static_key_length(const MARIA_KEY *key, uint nod_flag,
1812
uchar *next_pos __attribute__((unused)),
1813
uchar *org_key __attribute__((unused)),
1814
uchar *prev_key __attribute__((unused)),
1815
MARIA_KEY_PARAM *s_temp)
1817
s_temp->key= key->data;
1818
return (int) (s_temp->move_length= key->data_length + key->ref_length +
1822
/* Variable length key */
1825
_ma_calc_var_key_length(const MARIA_KEY *key, uint nod_flag,
1826
uchar *next_pos __attribute__((unused)),
1827
uchar *org_key __attribute__((unused)),
1828
uchar *prev_key __attribute__((unused)),
1829
MARIA_KEY_PARAM *s_temp)
1831
s_temp->key= key->data;
1832
return (int) (s_temp->move_length= key->data_length + key->ref_length +
1837
@brief Calc length needed to store prefixed compressed keys
1840
Variable length first segment which is prefix compressed
1841
(maria_chk reports 'packed + stripped')
1843
Keys are compressed the following way:
1845
If the max length of first key segment <= 127 bytes the prefix is
1846
1 uchar else it's 2 byte
1848
prefix byte(s) The high bit is set if this is a prefix for the prev key
1849
length Packed length if the previous was a prefix byte
1850
[length] data bytes ('length' bytes)
1851
next-key-seg Next key segments
1853
If the first segment can have NULL:
1854
The length is 0 for NULLS and 1+length for not null columns.
1858
_ma_calc_var_pack_key_length(const MARIA_KEY *int_key, uint nod_flag,
1859
uchar *next_key, uchar *org_key, uchar *prev_key,
1860
MARIA_KEY_PARAM *s_temp)
1862
reg1 HA_KEYSEG *keyseg;
1864
uint key_length,ref_length,org_key_length=0,
1865
length_pack,new_key_length,diff_flag,pack_marker;
1866
const uchar *key, *start, *end, *key_end;
1868
my_bool same_length;
1869
MARIA_KEYDEF *keyinfo= int_key->keyinfo;
1872
length_pack=s_temp->ref_length=s_temp->n_ref_length=s_temp->n_length=0;
1873
same_length=0; keyseg=keyinfo->seg;
1874
key_length= int_key->data_length + int_key->ref_length + nod_flag;
1877
if ((keyinfo->flag & HA_FULLTEXT) &&
1878
((keyseg->type == HA_KEYTYPE_TEXT) ||
1879
(keyseg->type == HA_KEYTYPE_VARTEXT1) ||
1880
(keyseg->type == HA_KEYTYPE_VARTEXT2)) &&
1881
!use_strnxfrm(keyseg->charset))
1882
sort_order= keyseg->charset->sort_order;
1884
/* diff flag contains how many bytes is needed to pack key */
1885
if (keyseg->length >= 127)
1895
s_temp->pack_marker=pack_marker;
1897
/* Handle the case that the first part have NULL values */
1898
if (keyseg->flag & HA_NULL_PART)
1903
s_temp->key_length= 0;
1904
s_temp->totlength= key_length-1+diff_flag;
1905
s_temp->next_key_pos= 0; /* No next key */
1906
return (s_temp->move_length= s_temp->totlength);
1908
s_temp->store_not_null=1;
1909
key_length--; /* We don't store NULL */
1910
if (prev_key && !*prev_key++)
1911
org_key=prev_key=0; /* Can't pack against prev */
1913
org_key++; /* Skip NULL */
1916
s_temp->store_not_null=0;
1917
s_temp->prev_key= org_key;
1919
/* The key part will start with a packed length */
1921
get_key_pack_length(new_key_length,length_pack,key);
1922
end= key_end= key+ new_key_length;
1925
/* Calc how many characters are identical between this and the prev. key */
1928
get_key_length(org_key_length,prev_key);
1929
s_temp->prev_key=prev_key; /* Pointer at data */
1930
/* Don't use key-pack if length == 0 */
1931
if (new_key_length && new_key_length == org_key_length)
1933
else if (new_key_length > org_key_length)
1934
end= key + org_key_length;
1936
if (sort_order) /* SerG */
1939
sort_order[*key] == sort_order[*prev_key])
1946
while (key < end && *key == *prev_key)
1954
s_temp->key_length= (uint) (key_end-key);
1956
if (same_length && key == key_end)
1958
/* identical variable length key */
1959
s_temp->ref_length= pack_marker;
1960
length=(int) key_length-(int) (key_end-start)-length_pack;
1963
{ /* Can't combine with next */
1964
s_temp->n_length= *next_key; /* Needed by _ma_store_key */
1971
{ /* Starts as prev key */
1972
ref_length= (uint) (key-start);
1973
s_temp->ref_length= ref_length + pack_marker;
1974
length= (int) (key_length - ref_length);
1976
length-= length_pack;
1978
length+= ((new_key_length-ref_length) >= 255) ? 3 : 1;/* Rest_of_key */
1982
s_temp->key_length+=s_temp->store_not_null; /* If null */
1983
length= key_length - length_pack+ diff_flag;
1986
s_temp->totlength=(uint) length;
1987
s_temp->prev_length=0;
1988
DBUG_PRINT("test",("tot_length: %u length: %d uniq_key_length: %u",
1989
key_length, length, s_temp->key_length));
1991
/* If something after that hasn't length=0, test if we can combine */
1992
if ((s_temp->next_key_pos=next_key))
1994
uint packed,n_length;
1996
packed = *next_key & 128;
1999
n_length= mi_uint2korr(next_key) & 32767; /* Length of next key */
2003
n_length= *next_key++ & 127;
2005
n_length-= s_temp->store_not_null;
2007
if (n_length || packed) /* Don't pack 0 length keys */
2009
uint next_length_pack, new_ref_length=s_temp->ref_length;
2013
/* If first key and next key is packed (only on delete) */
2014
if (!prev_key && org_key)
2016
get_key_length(org_key_length,org_key);
2018
if (sort_order) /* SerG */
2021
sort_order[*key] == sort_order[*org_key])
2028
while (key < end && *key == *org_key)
2033
if ((new_ref_length= (uint) (key - start)))
2034
new_ref_length+=pack_marker;
2040
We put a different key between two identical variable length keys
2041
Extend next key to have same prefix as this key
2043
if (new_ref_length) /* prefix of previus key */
2044
{ /* make next key longer */
2045
s_temp->part_of_prev_key= new_ref_length;
2046
s_temp->prev_length= org_key_length -
2047
(new_ref_length-pack_marker);
2048
s_temp->n_ref_length= s_temp->part_of_prev_key;
2049
s_temp->n_length= s_temp->prev_length;
2050
n_length= get_pack_length(s_temp->prev_length);
2051
s_temp->prev_key+= (new_ref_length - pack_marker);
2052
length+= s_temp->prev_length + n_length;
2055
{ /* Can't use prev key */
2056
s_temp->part_of_prev_key=0;
2057
s_temp->prev_length= org_key_length;
2058
s_temp->n_ref_length=s_temp->n_length= org_key_length;
2059
length+= org_key_length;
2061
return (s_temp->move_length= (int) length);
2064
ref_length=n_length;
2065
/* Get information about not packed key suffix */
2066
get_key_pack_length(n_length,next_length_pack,next_key);
2068
/* Test if new keys has fewer characters that match the previous key */
2069
if (!new_ref_length)
2070
{ /* Can't use prev key */
2071
s_temp->part_of_prev_key= 0;
2072
s_temp->prev_length= ref_length;
2073
s_temp->n_ref_length= s_temp->n_length= n_length+ref_length;
2074
return s_temp->move_length= ((int) length+ref_length-
2077
if (ref_length+pack_marker > new_ref_length)
2079
uint new_pack_length=new_ref_length-pack_marker;
2080
/* We must copy characters from the original key to the next key */
2081
s_temp->part_of_prev_key= new_ref_length;
2082
s_temp->prev_length= ref_length - new_pack_length;
2083
s_temp->n_ref_length=s_temp->n_length=n_length + s_temp->prev_length;
2084
s_temp->prev_key+= new_pack_length;
2085
length-= (next_length_pack - get_pack_length(s_temp->n_length));
2086
return s_temp->move_length= ((int) length + s_temp->prev_length);
2091
/* Next key wasn't a prefix of previous key */
2095
DBUG_PRINT("test",("length: %d next_key: 0x%lx", length,
2100
key=(start+=ref_length);
2101
if (key+n_length < key_end) /* Normalize length based */
2102
key_end= key+n_length;
2103
if (sort_order) /* SerG */
2105
while (key < key_end &&
2106
sort_order[*key] == sort_order[*next_key])
2113
while (key < key_end && *key == *next_key)
2118
if (!(tmp_length=(uint) (key-start)))
2119
{ /* Key can't be re-packed */
2120
s_temp->next_key_pos=0;
2121
return (s_temp->move_length= length);
2123
ref_length+=tmp_length;
2124
n_length-=tmp_length;
2125
length-=tmp_length+next_length_pack; /* We gained these chars */
2127
if (n_length == 0 && ref_length == new_key_length)
2129
s_temp->n_ref_length=pack_marker; /* Same as prev key */
2133
s_temp->n_ref_length=ref_length | pack_marker;
2134
length+= get_pack_length(n_length);
2135
s_temp->n_length=n_length;
2139
return (s_temp->move_length= length);
2143
/* Length of key which is prefix compressed */
2145
int _ma_calc_bin_pack_key_length(const MARIA_KEY *int_key,
2148
uchar *org_key, uchar *prev_key,
2149
MARIA_KEY_PARAM *s_temp)
2151
uint length,key_length,ref_length;
2152
const uchar *key= int_key->data;
2154
s_temp->totlength= key_length= (int_key->data_length + int_key->ref_length+
2157
s_temp->n_length= s_temp->n_ref_length=0; /* For valgrind */
2160
s_temp->prev_key=org_key;
2161
if (prev_key) /* If not first key in block */
2163
/* pack key against previous key */
2165
As keys may be identical when running a sort in maria_chk, we
2166
have to guard against the case where keys may be identical
2170
for ( ; *key == *prev_key && key < end; key++,prev_key++) ;
2171
s_temp->ref_length= ref_length=(uint) (key-s_temp->key);
2172
length=key_length - ref_length + get_pack_length(ref_length);
2176
/* No previous key */
2177
s_temp->ref_length=ref_length=0;
2178
length=key_length+1;
2180
if ((s_temp->next_key_pos=next_key)) /* If another key after */
2182
/* pack key against next key */
2183
uint next_length,next_length_pack;
2184
get_key_pack_length(next_length,next_length_pack,next_key);
2186
/* If first key and next key is packed (only on delete) */
2187
if (!prev_key && org_key && next_length)
2190
for (key= s_temp->key, end=key+next_length ;
2191
*key == *org_key && key < end;
2193
ref_length= (uint) (key - s_temp->key);
2196
if (next_length > ref_length)
2198
/* We put a key with different case between two keys with the same prefix
2199
Extend next key to have same prefix as
2201
s_temp->n_ref_length= ref_length;
2202
s_temp->prev_length= next_length-ref_length;
2203
s_temp->prev_key+= ref_length;
2204
return s_temp->move_length= ((int) (length+ s_temp->prev_length -
2206
get_pack_length(ref_length)));
2208
/* Check how many characters are identical to next key */
2209
key= s_temp->key+next_length;
2210
while (*key++ == *next_key++) ;
2211
if ((ref_length= (uint) (key - s_temp->key)-1) == next_length)
2213
s_temp->next_key_pos=0;
2214
return (s_temp->move_length= length); /* Can't pack next key */
2216
s_temp->prev_length=0;
2217
s_temp->n_ref_length=ref_length;
2218
return s_temp->move_length= (int) (length-(ref_length - next_length) -
2220
get_pack_length(ref_length));
2222
return (s_temp->move_length= (int) length);
2227
** store a key packed with _ma_calc_xxx_key_length in page-buffert
2230
/* store key without compression */
2232
void _ma_store_static_key(MARIA_KEYDEF *keyinfo __attribute__((unused)),
2233
register uchar *key_pos,
2234
register MARIA_KEY_PARAM *s_temp)
2236
memcpy(key_pos, s_temp->key,(size_t) s_temp->move_length);
2237
s_temp->changed_length= s_temp->move_length;
2241
/* store variable length key with prefix compression */
2243
#define store_pack_length(test,pos,length) { \
2244
if (test) { *((pos)++) = (uchar) (length); } else \
2245
{ *((pos)++) = (uchar) ((length) >> 8); *((pos)++) = (uchar) (length); } }
2248
void _ma_store_var_pack_key(MARIA_KEYDEF *keyinfo __attribute__((unused)),
2249
register uchar *key_pos,
2250
register MARIA_KEY_PARAM *s_temp)
2253
uchar *org_key_pos= key_pos;
2255
if (s_temp->ref_length)
2257
/* Packed against previous key */
2258
store_pack_length(s_temp->pack_marker == 128,key_pos,s_temp->ref_length);
2259
/* If not same key after */
2260
if (s_temp->ref_length != s_temp->pack_marker)
2261
store_key_length_inc(key_pos,s_temp->key_length);
2265
/* Not packed against previous key */
2266
store_pack_length(s_temp->pack_marker == 128,key_pos,s_temp->key_length);
2268
bmove(key_pos, s_temp->key,
2269
(length= s_temp->totlength - (uint) (key_pos-org_key_pos)));
2273
if (!s_temp->next_key_pos) /* No following key */
2276
if (s_temp->prev_length)
2278
/* Extend next key because new key didn't have same prefix as prev key */
2279
if (s_temp->part_of_prev_key)
2281
store_pack_length(s_temp->pack_marker == 128,key_pos,
2282
s_temp->part_of_prev_key);
2283
store_key_length_inc(key_pos,s_temp->n_length);
2287
s_temp->n_length+= s_temp->store_not_null;
2288
store_pack_length(s_temp->pack_marker == 128,key_pos,
2291
memcpy(key_pos, s_temp->prev_key, s_temp->prev_length);
2292
key_pos+= s_temp->prev_length;
2294
else if (s_temp->n_ref_length)
2296
store_pack_length(s_temp->pack_marker == 128,key_pos,s_temp->n_ref_length);
2297
if (s_temp->n_ref_length != s_temp->pack_marker)
2299
/* Not identical key */
2300
store_key_length_inc(key_pos,s_temp->n_length);
2305
s_temp->n_length+= s_temp->store_not_null;
2306
store_pack_length(s_temp->pack_marker == 128,key_pos,s_temp->n_length);
2310
s_temp->changed_length= (uint) (key_pos - org_key_pos);
2314
/* variable length key with prefix compression */
2316
void _ma_store_bin_pack_key(MARIA_KEYDEF *keyinfo __attribute__((unused)),
2317
register uchar *key_pos,
2318
register MARIA_KEY_PARAM *s_temp)
2320
uchar *org_key_pos= key_pos;
2321
size_t length= s_temp->totlength - s_temp->ref_length;
2323
store_key_length_inc(key_pos,s_temp->ref_length);
2324
memcpy(key_pos, s_temp->key+s_temp->ref_length, length);
2327
if (s_temp->next_key_pos)
2329
store_key_length_inc(key_pos,s_temp->n_ref_length);
2330
if (s_temp->prev_length) /* If we must extend key */
2332
memcpy(key_pos,s_temp->prev_key,s_temp->prev_length);
2333
key_pos+= s_temp->prev_length;
2336
s_temp->changed_length= (uint) (key_pos - org_key_pos);
added
removed
storage/maria/ma_search.c
