1/*
2 Copyright (c) 2000, 2010, Oracle and/or its affiliates
3
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; version 2 of the License.
7
8 This program is distributed in the hope that it will be useful,
9 but WITHOUT ANY WARRANTY; without even the implied warranty of
10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 GNU General Public License for more details.
12
13 You should have received a copy of the GNU General Public License
14 along with this program; if not, write to the Free Software
15 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
16
17/* key handling functions */
18
19#include "fulltext.h"
20#include "m_ctype.h"
21
22static my_bool _mi_get_prev_key(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *page,
23 uchar *key, uchar *keypos,
24 uint *return_key_length);
25
26 /* Check index */
27
28int _mi_check_index(MI_INFO *info, int inx)
29{
30 if (inx == -1) /* Use last index */
31 inx=info->lastinx;
32 if (inx < 0)
33 {
34 my_errno= HA_ERR_WRONG_INDEX;
35 return -1;
36 }
37 if (!mi_is_key_active(info->s->state.key_map, inx))
38 {
39 my_errno= info->s->state.state.records ? HA_ERR_WRONG_INDEX :
40 HA_ERR_END_OF_FILE;
41 return -1;
42 }
43 if (info->lastinx != inx) /* Index changed */
44 {
45 info->lastinx = inx;
46 info->page_changed=1;
47 info->update= ((info->update & (HA_STATE_CHANGED | HA_STATE_ROW_CHANGED)) |
48 HA_STATE_NEXT_FOUND | HA_STATE_PREV_FOUND);
49 }
50 if (info->opt_flag & WRITE_CACHE_USED && flush_io_cache(&info->rec_cache))
51 return(-1);
52 return(inx);
53} /* mi_check_index */
54
55
56 /*
57 ** Search after row by a key
58 ** Position to row is stored in info->lastpos
59 ** Return: -1 if not found
60 ** 1 if one should continue search on higher level
61 */
62
63int _mi_search(register MI_INFO *info, register MI_KEYDEF *keyinfo,
64 uchar *key, uint key_len, uint nextflag, register my_off_t pos)
65{
66 my_bool last_key;
67 int error,flag;
68 uint nod_flag;
69 uchar *keypos,*maxpos;
70 uchar lastkey[HA_MAX_KEY_BUFF],*buff;
71 DBUG_ENTER("_mi_search");
72 DBUG_PRINT("enter",("pos: %lu nextflag: %u lastpos: %lu",
73 (ulong) pos, nextflag, (ulong) info->lastpos));
74 DBUG_EXECUTE("key",_mi_print_key(DBUG_FILE,keyinfo->seg,key,key_len););
75
76 if (pos == HA_OFFSET_ERROR)
77 {
78 my_errno=HA_ERR_KEY_NOT_FOUND; /* Didn't find key */
79 info->lastpos= HA_OFFSET_ERROR;
80 if (!(nextflag & (SEARCH_SMALLER | SEARCH_BIGGER | SEARCH_LAST)))
81 DBUG_RETURN(-1); /* Not found ; return error */
82 DBUG_RETURN(1); /* Search at upper levels */
83 }
84
85 if (!(buff=_mi_fetch_keypage(info,keyinfo,pos,DFLT_INIT_HITS,info->buff,
86 MY_TEST(!(nextflag & SEARCH_SAVE_BUFF)))))
87 goto err;
88 DBUG_DUMP("page", buff, mi_getint(buff));
89
90 flag=(*keyinfo->bin_search)(info,keyinfo,buff,key,key_len,nextflag,
91 &keypos,lastkey, &last_key);
92 if (flag == MI_FOUND_WRONG_KEY)
93 {
94 my_errno= HA_ERR_CRASHED;
95 goto err;
96 }
97 nod_flag=mi_test_if_nod(buff);
98 maxpos=buff+mi_getint(buff)-1;
99
100 if (flag)
101 {
102 if ((error=_mi_search(info,keyinfo,key,key_len,nextflag,
103 _mi_kpos(nod_flag,keypos))) <= 0)
104 DBUG_RETURN(error);
105
106 if (flag >0)
107 {
108 if (nextflag & (SEARCH_SMALLER | SEARCH_LAST) &&
109 keypos == buff+2+nod_flag)
110 DBUG_RETURN(1); /* Bigger than key */
111 }
112 else if (nextflag & SEARCH_BIGGER && keypos >= maxpos)
113 DBUG_RETURN(1); /* Smaller than key */
114 }
115 else
116 {
117 if ((nextflag & SEARCH_FIND) && nod_flag &&
118 ((keyinfo->flag & (HA_NOSAME | HA_NULL_PART)) != HA_NOSAME ||
119 key_len != USE_WHOLE_KEY))
120 {
121 if ((error=_mi_search(info,keyinfo,key,key_len,SEARCH_FIND,
122 _mi_kpos(nod_flag,keypos))) >= 0 ||
123 my_errno != HA_ERR_KEY_NOT_FOUND)
124 DBUG_RETURN(error);
125 info->last_keypage= HA_OFFSET_ERROR; /* Buffer not in mem */
126 }
127 }
128 if (pos != info->last_keypage)
129 {
130 uchar *old_buff=buff;
131 if (!(buff=_mi_fetch_keypage(info,keyinfo,pos,DFLT_INIT_HITS,info->buff,
132 MY_TEST(!(nextflag & SEARCH_SAVE_BUFF)))))
133 goto err;
134 keypos=buff+(keypos-old_buff);
135 maxpos=buff+(maxpos-old_buff);
136 }
137
138 if ((nextflag & (SEARCH_SMALLER | SEARCH_LAST)) && flag != 0)
139 {
140 uint not_used[2];
141 if (_mi_get_prev_key(info,keyinfo, buff, info->lastkey, keypos,
142 &info->lastkey_length))
143 goto err;
144 if (!(nextflag & SEARCH_SMALLER) &&
145 ha_key_cmp(keyinfo->seg, info->lastkey, key, key_len, SEARCH_FIND,
146 not_used))
147 {
148 my_errno=HA_ERR_KEY_NOT_FOUND; /* Didn't find key */
149 goto err;
150 }
151 }
152 else
153 {
154 info->lastkey_length=(*keyinfo->get_key)(keyinfo,nod_flag,&keypos,lastkey);
155 if (!info->lastkey_length)
156 goto err;
157 memcpy(info->lastkey,lastkey,info->lastkey_length);
158 }
159 info->lastpos=_mi_dpos(info,0,info->lastkey+info->lastkey_length);
160 /* Save position for a possible read next / previous */
161 info->int_keypos=info->buff+ (keypos-buff);
162 info->int_maxpos=info->buff+ (maxpos-buff);
163 info->int_nod_flag=nod_flag;
164 info->int_keytree_version=keyinfo->version;
165 info->last_search_keypage=info->last_keypage;
166 info->page_changed=0;
167 info->buff_used= (info->buff != buff); /* If we have to reread buff */
168
169 DBUG_PRINT("exit",("found key at %lu",(ulong) info->lastpos));
170 DBUG_RETURN(0);
171
172err:
173 DBUG_PRINT("exit",("Error: %d",my_errno));
174 info->lastpos= HA_OFFSET_ERROR;
175 info->page_changed=1;
176 DBUG_RETURN (-1);
177} /* _mi_search */
178
179
180 /* Search after key in page-block */
181 /* If packed key puts smaller or identical key in buff */
182 /* ret_pos point to where find or bigger key starts */
183 /* ARGSUSED */
184
185int _mi_bin_search(MI_INFO *info, register MI_KEYDEF *keyinfo, uchar *page,
186 uchar *key, uint key_len, uint comp_flag, uchar **ret_pos,
187 uchar *buff __attribute__((unused)), my_bool *last_key)
188{
189 reg4 int start,mid,end,save_end;
190 int UNINIT_VAR(flag);
191 uint totlength,nod_flag,not_used[2];
192 DBUG_ENTER("_mi_bin_search");
193
194 totlength=keyinfo->keylength+(nod_flag=mi_test_if_nod(page));
195 start=0; mid=1;
196 save_end=end=(int) ((mi_getint(page)-2-nod_flag)/totlength-1);
197 DBUG_PRINT("test",("mi_getint: %d end: %d",mi_getint(page),end));
198 page+=2+nod_flag;
199
200 while (start != end)
201 {
202 mid= (start+end)/2;
203 if ((flag=ha_key_cmp(keyinfo->seg,page+(uint) mid*totlength,key,key_len,
204 comp_flag, not_used))
205 >= 0)
206 end=mid;
207 else
208 start=mid+1;
209 }
210 if (mid != start)
211 flag=ha_key_cmp(keyinfo->seg,page+(uint) start*totlength,key,key_len,
212 comp_flag, not_used);
213 if (flag < 0)
214 start++; /* point at next, bigger key */
215 *ret_pos=page+(uint) start*totlength;
216 *last_key= end == save_end;
217 DBUG_PRINT("exit",("flag: %d keypos: %d",flag,start));
218 DBUG_RETURN(flag);
219} /* _mi_bin_search */
220
221
222/*
223 Locate a packed key in a key page.
224
225 SYNOPSIS
226 _mi_seq_search()
227 info Open table information.
228 keyinfo Key definition information.
229 page Key page (beginning).
230 key Search key.
231 key_len Length to use from search key or USE_WHOLE_KEY
232 comp_flag Search flags like SEARCH_SAME etc.
233 ret_pos RETURN Position in key page behind this key.
234 buff RETURN Copy of previous or identical unpacked key.
235 last_key RETURN If key is last in page.
236
237 DESCRIPTION
238 Used instead of _mi_bin_search() when key is packed.
239 Puts smaller or identical key in buff.
240 Key is searched sequentially.
241
242 RETURN
243 > 0 Key in 'buff' is smaller than search key.
244 0 Key in 'buff' is identical to search key.
245 < 0 Not found.
246*/
247
248int _mi_seq_search(MI_INFO *info, register MI_KEYDEF *keyinfo, uchar *page,
249 uchar *key, uint key_len, uint comp_flag, uchar **ret_pos,
250 uchar *buff, my_bool *last_key)
251{
252 int UNINIT_VAR(flag);
253 uint nod_flag,UNINIT_VAR(length),not_used[2];
254 uchar t_buff[HA_MAX_KEY_BUFF],*end;
255 DBUG_ENTER("_mi_seq_search");
256
257 end= page+mi_getint(page);
258 nod_flag=mi_test_if_nod(page);
259 page+=2+nod_flag;
260 *ret_pos=page;
261 t_buff[0]=0; /* Avoid bugs */
262 while (page < end)
263 {
264 length=(*keyinfo->get_key)(keyinfo,nod_flag,&page,t_buff);
265 if (length == 0 || page > end)
266 {
267 mi_print_error(info->s, HA_ERR_CRASHED);
268 my_errno=HA_ERR_CRASHED;
269 DBUG_PRINT("error",
270 ("Found wrong key: length: %u page: %p end: %p",
271 length, page, end));
272 DBUG_RETURN(MI_FOUND_WRONG_KEY);
273 }
274 if ((flag=ha_key_cmp(keyinfo->seg,t_buff,key,key_len,comp_flag,
275 not_used)) >= 0)
276 break;
277#ifdef EXTRA_DEBUG
278 DBUG_PRINT("loop",("page: 0x%lx key: '%s' flag: %d", (long) page, t_buff,
279 flag));
280#endif
281 memcpy(buff,t_buff,length);
282 *ret_pos=page;
283 }
284 if (flag == 0)
285 memcpy(buff,t_buff,length); /* Result is first key */
286 *last_key= page == end;
287 DBUG_PRINT("exit",("flag: %d ret_pos: %p", flag, *ret_pos));
288 DBUG_RETURN(flag);
289} /* _mi_seq_search */
290
291
292int _mi_prefix_search(MI_INFO *info, register MI_KEYDEF *keyinfo, uchar *page,
293 uchar *key, uint key_len, uint nextflag, uchar **ret_pos,
294 uchar *buff, my_bool *last_key)
295{
296 /*
297 my_flag is raw comparison result to be changed according to
298 SEARCH_NO_FIND,SEARCH_LAST and HA_REVERSE_SORT flags.
299 flag is the value returned by ha_key_cmp and as treated as final
300 */
301 int flag=0, my_flag=-1;
302 uint nod_flag, UNINIT_VAR(length), len, matched, cmplen, kseg_len;
303 uint UNINIT_VAR(prefix_len), suffix_len;
304 int key_len_skip, UNINIT_VAR(seg_len_pack), key_len_left;
305 uchar *end, *kseg, *vseg;
306 const uchar *sort_order= keyinfo->seg->charset->sort_order;
307 uchar tt_buff[HA_MAX_KEY_BUFF+2], *t_buff=tt_buff+2;
308 uchar *UNINIT_VAR(saved_from), *UNINIT_VAR(saved_to);
309 uchar *UNINIT_VAR(saved_vseg);
310 uint saved_length=0, saved_prefix_len=0;
311 uint length_pack;
312 DBUG_ENTER("_mi_prefix_search");
313
314 t_buff[0]=0; /* Avoid bugs */
315 end= page+mi_getint(page);
316 nod_flag=mi_test_if_nod(page);
317 page+=2+nod_flag;
318 *ret_pos=page;
319 kseg=key;
320
321 get_key_pack_length(kseg_len,length_pack,kseg);
322 key_len_skip=length_pack+kseg_len;
323 key_len_left=(int) key_len- (int) key_len_skip;
324 /* If key_len is 0, then lenght_pack is 1, then key_len_left is -1. */
325 cmplen=(key_len_left>=0) ? kseg_len : key_len-length_pack;
326 DBUG_PRINT("info",("key: '%.*s'",kseg_len,kseg));
327
328 /*
329 Keys are compressed the following way:
330
331 If the max length of first key segment <= 127 bytes the prefix is
332 1 byte else it's 2 byte
333
334 (prefix) length The high bit is set if this is a prefix for the prev key.
335 [suffix length] Packed length of suffix if the previous was a prefix.
336 (suffix) data Key data bytes (past the common prefix or whole segment).
337 [next-key-seg] Next key segments (([packed length], data), ...)
338 pointer Reference to the data file (last_keyseg->length).
339 */
340
341 matched=0; /* how many char's from prefix were alredy matched */
342 len=0; /* length of previous key unpacked */
343
344 while (page < end)
345 {
346 uint packed= *page & 128;
347
348 vseg=page;
349 if (keyinfo->seg->length >= 127)
350 {
351 suffix_len=mi_uint2korr(vseg) & 32767;
352 vseg+=2;
353 }
354 else
355 suffix_len= *vseg++ & 127;
356
357 if (packed)
358 {
359 if (suffix_len == 0)
360 {
361 /* == 0x80 or 0x8000, same key, prefix length == old key length. */
362 prefix_len=len;
363 }
364 else
365 {
366 /* > 0x80 or 0x8000, this is prefix lgt, packed suffix lgt follows. */
367 prefix_len=suffix_len;
368 get_key_length(suffix_len,vseg);
369 }
370 }
371 else
372 {
373 /* Not packed. No prefix used from last key. */
374 prefix_len=0;
375 }
376
377 len=prefix_len+suffix_len;
378 seg_len_pack=get_pack_length(len);
379 t_buff=tt_buff+3-seg_len_pack;
380 store_key_length(t_buff,len);
381
382 if (prefix_len > saved_prefix_len)
383 memcpy(t_buff+seg_len_pack+saved_prefix_len,saved_vseg,
384 prefix_len-saved_prefix_len);
385 saved_vseg=vseg;
386 saved_prefix_len=prefix_len;
387
388 DBUG_PRINT("loop",("page: '%.*s%.*s'",prefix_len,t_buff+seg_len_pack,
389 suffix_len,vseg));
390 {
391 uchar *from=vseg+suffix_len;
392 HA_KEYSEG *keyseg;
393 uint l;
394
395 for (keyseg=keyinfo->seg+1 ; keyseg->type ; keyseg++ )
396 {
397
398 if (keyseg->flag & HA_NULL_PART)
399 {
400 if (!(*from++))
401 continue;
402 }
403 if (keyseg->flag & (HA_VAR_LENGTH_PART | HA_BLOB_PART | HA_SPACE_PACK))
404 {
405 get_key_length(l,from);
406 }
407 else
408 l=keyseg->length;
409
410 from+=l;
411 }
412 from+=keyseg->length;
413 page=from+nod_flag;
414 length= (uint) (from - vseg);
415 }
416
417 if (page > end)
418 {
419 mi_print_error(info->s, HA_ERR_CRASHED);
420 my_errno=HA_ERR_CRASHED;
421 DBUG_PRINT("error",
422 ("Found wrong key: length: %u page: %p end: %p",
423 length, page, end));
424 DBUG_RETURN(MI_FOUND_WRONG_KEY);
425 }
426
427 if (matched >= prefix_len)
428 {
429 /* We have to compare. But we can still skip part of the key */
430 uint left;
431 uchar *k=kseg+prefix_len;
432
433 /*
434 If prefix_len > cmplen then we are in the end-space comparison
435 phase. Do not try to acces the key any more ==> left= 0.
436 */
437 left= ((len <= cmplen) ? suffix_len :
438 ((prefix_len < cmplen) ? cmplen - prefix_len : 0));
439
440 matched=prefix_len+left;
441
442 if (sort_order)
443 {
444 for (my_flag=0;left;left--)
445 if ((my_flag= (int) sort_order[*vseg++] - (int) sort_order[*k++]))
446 break;
447 }
448 else
449 {
450 for (my_flag=0;left;left--)
451 if ((my_flag= (int) *vseg++ - (int) *k++))
452 break;
453 }
454
455 if (my_flag>0) /* mismatch */
456 break;
457 if (my_flag==0) /* match */
458 {
459 /*
460 ** len cmplen seg_left_len more_segs
461 ** < matched=len; continue search
462 ** > = prefix ? found : (matched=len; continue search)
463 ** > < - ok, found
464 ** = < - ok, found
465 ** = = - ok, found
466 ** = = + next seg
467 */
468 if (len < cmplen)
469 {
470 if ((keyinfo->seg->type != HA_KEYTYPE_TEXT &&
471 keyinfo->seg->type != HA_KEYTYPE_VARTEXT1 &&
472 keyinfo->seg->type != HA_KEYTYPE_VARTEXT2))
473 my_flag= -1;
474 else
475 {
476 /* We have to compare k and vseg as if they were space extended */
477 uchar *k_end= k+ (cmplen - len);
478 for ( ; k < k_end && *k == ' '; k++) ;
479 if (k == k_end)
480 goto cmp_rest; /* should never happen */
481 if (*k < (uchar) ' ')
482 {
483 my_flag= 1; /* Compared string is smaller */
484 break;
485 }
486 my_flag= -1; /* Continue searching */
487 }
488 }
489 else if (len > cmplen)
490 {
491 uchar *vseg_end;
492 if ((nextflag & SEARCH_PREFIX) && key_len_left == 0)
493 goto fix_flag;
494
495 /* We have to compare k and vseg as if they were space extended */
496 for (vseg_end= vseg + (len-cmplen) ;
497 vseg < vseg_end && *vseg == (uchar) ' ';
498 vseg++, matched++) ;
499 DBUG_ASSERT(vseg < vseg_end);
500
501 if (*vseg > (uchar) ' ')
502 {
503 my_flag= 1; /* Compared string is smaller */
504 break;
505 }
506 my_flag= -1; /* Continue searching */
507 }
508 else
509 {
510 cmp_rest:
511 if (key_len_left>0)
512 {
513 uint not_used[2];
514 if ((flag = ha_key_cmp(keyinfo->seg+1,vseg,
515 k, key_len_left, nextflag, not_used)) >= 0)
516 break;
517 }
518 else
519 {
520 /*
521 at this line flag==-1 if the following lines were already
522 visited and 0 otherwise, i.e. flag <=0 here always !!!
523 */
524 fix_flag:
525 DBUG_ASSERT(flag <= 0);
526 if (nextflag & (SEARCH_NO_FIND | SEARCH_LAST))
527 flag=(nextflag & (SEARCH_BIGGER | SEARCH_LAST)) ? -1 : 1;
528 if (flag>=0)
529 break;
530 }
531 }
532 }
533 matched-=left;
534 }
535 /* else (matched < prefix_len) ---> do nothing. */
536
537 memcpy(buff,t_buff,saved_length=seg_len_pack+prefix_len);
538 saved_to=buff+saved_length;
539 saved_from=saved_vseg;
540 saved_length=length;
541 *ret_pos=page;
542 }
543 if (my_flag)
544 flag=(keyinfo->seg->flag & HA_REVERSE_SORT) ? -my_flag : my_flag;
545 if (flag == 0)
546 {
547 memcpy(buff,t_buff,saved_length=seg_len_pack+prefix_len);
548 saved_to=buff+saved_length;
549 saved_from=saved_vseg;
550 saved_length=length;
551 }
552 if (saved_length)
553 memcpy(saved_to,saved_from,saved_length);
554
555 *last_key= page == end;
556
557 DBUG_PRINT("exit",("flag: %d ret_pos: %p", flag, *ret_pos));
558 DBUG_RETURN(flag);
559} /* _mi_prefix_search */
560
561
562 /* Get pos to a key_block */
563
564my_off_t _mi_kpos(uint nod_flag, uchar *after_key)
565{
566 after_key-=nod_flag;
567 switch (nod_flag) {
568#if SIZEOF_OFF_T > 4
569 case 7:
570 return mi_uint7korr(after_key)*MI_MIN_KEY_BLOCK_LENGTH;
571 case 6:
572 return mi_uint6korr(after_key)*MI_MIN_KEY_BLOCK_LENGTH;
573 case 5:
574 return mi_uint5korr(after_key)*MI_MIN_KEY_BLOCK_LENGTH;
575#else
576 case 7:
577 after_key++;
578 case 6:
579 after_key++;
580 case 5:
581 after_key++;
582#endif
583 case 4:
584 return ((my_off_t) mi_uint4korr(after_key))*MI_MIN_KEY_BLOCK_LENGTH;
585 case 3:
586 return ((my_off_t) mi_uint3korr(after_key))*MI_MIN_KEY_BLOCK_LENGTH;
587 case 2:
588 return (my_off_t) (mi_uint2korr(after_key)*MI_MIN_KEY_BLOCK_LENGTH);
589 case 1:
590 return (uint) (*after_key)*MI_MIN_KEY_BLOCK_LENGTH;
591 case 0: /* At leaf page */
592 default: /* Impossible */
593 return(HA_OFFSET_ERROR);
594 }
595} /* _kpos */
596
597
598 /* Save pos to a key_block */
599
600void _mi_kpointer(register MI_INFO *info, register uchar *buff, my_off_t pos)
601{
602 pos/=MI_MIN_KEY_BLOCK_LENGTH;
603 switch (info->s->base.key_reflength) {
604#if SIZEOF_OFF_T > 4
605 case 7: mi_int7store(buff,pos); break;
606 case 6: mi_int6store(buff,pos); break;
607 case 5: mi_int5store(buff,pos); break;
608#else
609 case 7: *buff++=0;
610 /* fall through */
611 case 6: *buff++=0;
612 /* fall through */
613 case 5: *buff++=0;
614 /* fall through */
615#endif
616 case 4: mi_int4store(buff,pos); break;
617 case 3: mi_int3store(buff,pos); break;
618 case 2: mi_int2store(buff,(uint) pos); break;
619 case 1: buff[0]= (uchar) pos; break;
620 default: abort(); /* impossible */
621 }
622} /* _mi_kpointer */
623
624
625 /* Calc pos to a data-record from a key */
626
627
628my_off_t _mi_dpos(MI_INFO *info, uint nod_flag, uchar *after_key)
629{
630 my_off_t pos;
631 after_key-=(nod_flag + info->s->rec_reflength);
632 switch (info->s->rec_reflength) {
633#if SIZEOF_OFF_T > 4
634 case 8: pos= (my_off_t) mi_uint8korr(after_key); break;
635 case 7: pos= (my_off_t) mi_uint7korr(after_key); break;
636 case 6: pos= (my_off_t) mi_uint6korr(after_key); break;
637 case 5: pos= (my_off_t) mi_uint5korr(after_key); break;
638#else
639 case 8: pos= (my_off_t) mi_uint4korr(after_key+4); break;
640 case 7: pos= (my_off_t) mi_uint4korr(after_key+3); break;
641 case 6: pos= (my_off_t) mi_uint4korr(after_key+2); break;
642 case 5: pos= (my_off_t) mi_uint4korr(after_key+1); break;
643#endif
644 case 4: pos= (my_off_t) mi_uint4korr(after_key); break;
645 case 3: pos= (my_off_t) mi_uint3korr(after_key); break;
646 case 2: pos= (my_off_t) mi_uint2korr(after_key); break;
647 default:
648 pos=0L; /* Shut compiler up */
649 }
650 return (info->s->options &
651 (HA_OPTION_PACK_RECORD | HA_OPTION_COMPRESS_RECORD)) ? pos :
652 pos*info->s->base.pack_reclength;
653}
654
655
656/* Calc position from a record pointer ( in delete link chain ) */
657
658my_off_t _mi_rec_pos(MYISAM_SHARE *s, uchar *ptr)
659{
660 my_off_t pos;
661 switch (s->rec_reflength) {
662#if SIZEOF_OFF_T > 4
663 case 8:
664 pos= (my_off_t) mi_uint8korr(ptr);
665 if (pos == HA_OFFSET_ERROR)
666 return HA_OFFSET_ERROR; /* end of list */
667 break;
668 case 7:
669 pos= (my_off_t) mi_uint7korr(ptr);
670 if (pos == (((my_off_t) 1) << 56) -1)
671 return HA_OFFSET_ERROR; /* end of list */
672 break;
673 case 6:
674 pos= (my_off_t) mi_uint6korr(ptr);
675 if (pos == (((my_off_t) 1) << 48) -1)
676 return HA_OFFSET_ERROR; /* end of list */
677 break;
678 case 5:
679 pos= (my_off_t) mi_uint5korr(ptr);
680 if (pos == (((my_off_t) 1) << 40) -1)
681 return HA_OFFSET_ERROR; /* end of list */
682 break;
683#else
684 case 8:
685 case 7:
686 case 6:
687 case 5:
688 ptr+= (s->rec_reflength-4);
689 /* fall through */
690#endif
691 case 4:
692 pos= (my_off_t) mi_uint4korr(ptr);
693 if (pos == (my_off_t) (uint32) ~0L)
694 return HA_OFFSET_ERROR;
695 break;
696 case 3:
697 pos= (my_off_t) mi_uint3korr(ptr);
698 if (pos == (my_off_t) (1 << 24) -1)
699 return HA_OFFSET_ERROR;
700 break;
701 case 2:
702 pos= (my_off_t) mi_uint2korr(ptr);
703 if (pos == (my_off_t) (1 << 16) -1)
704 return HA_OFFSET_ERROR;
705 break;
706 default: abort(); /* Impossible */
707 }
708 return ((s->options &
709 (HA_OPTION_PACK_RECORD | HA_OPTION_COMPRESS_RECORD)) ? pos :
710 pos*s->base.pack_reclength);
711}
712
713
714 /* save position to record */
715
716void _mi_dpointer(MI_INFO *info, uchar *buff, my_off_t pos)
717{
718 if (!(info->s->options &
719 (HA_OPTION_PACK_RECORD | HA_OPTION_COMPRESS_RECORD)) &&
720 pos != HA_OFFSET_ERROR)
721 pos/=info->s->base.pack_reclength;
722
723 switch (info->s->rec_reflength) {
724#if SIZEOF_OFF_T > 4
725 case 8: mi_int8store(buff,pos); break;
726 case 7: mi_int7store(buff,pos); break;
727 case 6: mi_int6store(buff,pos); break;
728 case 5: mi_int5store(buff,pos); break;
729#else
730 case 8: *buff++=0;
731 /* fall through */
732 case 7: *buff++=0;
733 /* fall through */
734 case 6: *buff++=0;
735 /* fall through */
736 case 5: *buff++=0;
737 /* fall through */
738#endif
739 case 4: mi_int4store(buff,pos); break;
740 case 3: mi_int3store(buff,pos); break;
741 case 2: mi_int2store(buff,(uint) pos); break;
742 default: abort(); /* Impossible */
743 }
744} /* _mi_dpointer */
745
746
747 /* Get key from key-block */
748 /* page points at previous key; its advanced to point at next key */
749 /* key should contain previous key */
750 /* Returns length of found key + pointers */
751 /* nod_flag is a flag if we are on nod */
752
753 /* same as _mi_get_key but used with fixed length keys */
754
755uint _mi_get_static_key(register MI_KEYDEF *keyinfo, uint nod_flag,
756 register uchar **page, register uchar *key)
757{
758 memcpy((uchar*) key,(uchar*) *page,
759 (size_t) (keyinfo->keylength+nod_flag));
760 *page+=keyinfo->keylength+nod_flag;
761 return(keyinfo->keylength);
762} /* _mi_get_static_key */
763
764
765/*
766 get key witch is packed against previous key or key with a NULL column.
767
768 SYNOPSIS
769 _mi_get_pack_key()
770 keyinfo key definition information.
771 nod_flag If nod: Length of node pointer, else zero.
772 page_pos RETURN position in key page behind this key.
773 key IN/OUT in: prev key, out: unpacked key.
774
775 RETURN
776 key_length + length of data pointer
777*/
778
779uint _mi_get_pack_key(register MI_KEYDEF *keyinfo, uint nod_flag,
780 register uchar **page_pos, register uchar *key)
781{
782 reg1 HA_KEYSEG *keyseg;
783 uchar *start_key,*page=*page_pos;
784 uint length;
785
786 start_key=key;
787 for (keyseg=keyinfo->seg ; keyseg->type ;keyseg++)
788 {
789 if (keyseg->flag & HA_PACK_KEY)
790 {
791 /* key with length, packed to previous key */
792 uchar *start=key;
793 uint packed= *page & 128,tot_length,rest_length;
794 if (keyseg->length >= 127)
795 {
796 length=mi_uint2korr(page) & 32767;
797 page+=2;
798 }
799 else
800 length= *page++ & 127;
801
802 if (packed)
803 {
804 if (length > (uint) keyseg->length)
805 {
806 mi_print_error(keyinfo->share, HA_ERR_CRASHED);
807 my_errno=HA_ERR_CRASHED;
808 return 0; /* Error */
809 }
810 if (length == 0) /* Same key */
811 {
812 if (keyseg->flag & HA_NULL_PART)
813 *key++=1; /* Can't be NULL */
814 get_key_length(length,key);
815 key+= length; /* Same diff_key as prev */
816 if (length > keyseg->length)
817 {
818 DBUG_PRINT("error",
819 ("Found too long null packed key: %u of %u at %p",
820 length, keyseg->length, *page_pos));
821 DBUG_DUMP("key", *page_pos, 16);
822 mi_print_error(keyinfo->share, HA_ERR_CRASHED);
823 my_errno=HA_ERR_CRASHED;
824 return 0;
825 }
826 continue;
827 }
828 if (keyseg->flag & HA_NULL_PART)
829 {
830 key++; /* Skip null marker*/
831 start++;
832 }
833
834 get_key_length(rest_length,page);
835 tot_length=rest_length+length;
836
837 /* If the stored length has changed, we must move the key */
838 if (tot_length >= 255 && *start != 255)
839 {
840 /* length prefix changed from a length of one to a length of 3 */
841 bmove_upp(key+length+3, key+length+1, length);
842 *key=255;
843 mi_int2store(key+1,tot_length);
844 key+=3+length;
845 }
846 else if (tot_length < 255 && *start == 255)
847 {
848 bmove(key+1,key+3,length);
849 *key=tot_length;
850 key+=1+length;
851 }
852 else
853 {
854 store_key_length_inc(key,tot_length);
855 key+=length;
856 }
857 memcpy(key,page,rest_length);
858 page+=rest_length;
859 key+=rest_length;
860 continue;
861 }
862 else
863 {
864 if (keyseg->flag & HA_NULL_PART)
865 {
866 if (!length--) /* Null part */
867 {
868 *key++=0;
869 continue;
870 }
871 *key++=1; /* Not null */
872 }
873 }
874 if (length > (uint) keyseg->length)
875 {
876 DBUG_PRINT("error",("Found too long packed key: %u of %u at %p",
877 length, keyseg->length, *page_pos));
878 DBUG_DUMP("key", *page_pos, 16);
879 mi_print_error(keyinfo->share, HA_ERR_CRASHED);
880 my_errno=HA_ERR_CRASHED;
881 return 0; /* Error */
882 }
883 store_key_length_inc(key,length);
884 }
885 else
886 {
887 if (keyseg->flag & HA_NULL_PART)
888 {
889 if (!(*key++ = *page++))
890 continue;
891 }
892 if (keyseg->flag &
893 (HA_VAR_LENGTH_PART | HA_BLOB_PART | HA_SPACE_PACK))
894 {
895 uchar *tmp=page;
896 get_key_length(length,tmp);
897 length+=(uint) (tmp-page);
898 }
899 else
900 length=keyseg->length;
901 }
902 memcpy((uchar*) key,(uchar*) page,(size_t) length);
903 key+=length;
904 page+=length;
905 }
906 length=keyseg->length+nod_flag;
907 bmove((uchar*) key,(uchar*) page,length);
908 *page_pos= page+length;
909 return ((uint) (key-start_key)+keyseg->length);
910} /* _mi_get_pack_key */
911
912
913
914/* key that is packed relatively to previous */
915
916uint _mi_get_binary_pack_key(register MI_KEYDEF *keyinfo, uint nod_flag,
917 register uchar **page_pos, register uchar *key)
918{
919 reg1 HA_KEYSEG *keyseg;
920 uchar *start_key,*page,*page_end,*from,*from_end;
921 uint length,tmp;
922 DBUG_ENTER("_mi_get_binary_pack_key");
923
924 page= *page_pos;
925 page_end=page+HA_MAX_KEY_BUFF+1;
926 start_key=key;
927
928 /*
929 Keys are compressed the following way:
930
931 prefix length Packed length of prefix common with prev key (1 or 3 bytes)
932 for each key segment:
933 [is null] Null indicator if can be null (1 byte, zero means null)
934 [length] Packed length if varlength (1 or 3 bytes)
935 key segment 'length' bytes of key segment value
936 pointer Reference to the data file (last_keyseg->length).
937
938 get_key_length() is a macro. It gets the prefix length from 'page'
939 and puts it into 'length'. It increments 'page' by 1 or 3, depending
940 on the packed length of the prefix length.
941 */
942 get_key_length(length,page);
943 if (length)
944 {
945 if (length > keyinfo->maxlength)
946 {
947 DBUG_PRINT("error",
948 ("Found too long binary packed key: %u of %u at %p",
949 length, keyinfo->maxlength, *page_pos));
950 DBUG_DUMP("key", *page_pos, 16);
951 goto crashed; /* Wrong key */
952 }
953 /* Key is packed against prev key, take prefix from prev key. */
954 from= key;
955 from_end= key + length;
956 }
957 else
958 {
959 /* Key is not packed against prev key, take all from page buffer. */
960 from= page;
961 from_end= page_end;
962 }
963
964 /*
965 The trouble is that key can be split in two parts:
966 The first part (prefix) is in from .. from_end - 1.
967 The second part starts at page.
968 The split can be at every byte position. So we need to check for
969 the end of the first part before using every byte.
970 */
971 for (keyseg=keyinfo->seg ; keyseg->type ;keyseg++)
972 {
973 if (keyseg->flag & HA_NULL_PART)
974 {
975 /* If prefix is used up, switch to rest. */
976 if (from == from_end) { from=page; from_end=page_end; }
977 if (!(*key++ = *from++))
978 continue; /* Null part */
979 }
980 if (keyseg->flag & (HA_VAR_LENGTH_PART | HA_BLOB_PART | HA_SPACE_PACK))
981 {
982 /* If prefix is used up, switch to rest. */
983 if (from == from_end) { from=page; from_end=page_end; }
984 /* Get length of dynamic length key part */
985 if ((length= (*key++ = *from++)) == 255)
986 {
987 /* If prefix is used up, switch to rest. */
988 if (from == from_end) { from=page; from_end=page_end; }
989 length= (uint) ((*key++ = *from++)) << 8;
990 /* If prefix is used up, switch to rest. */
991 if (from == from_end) { from=page; from_end=page_end; }
992 length+= (uint) ((*key++ = *from++));
993 }
994 if (length > keyseg->length)
995 goto crashed;
996 }
997 else
998 length=keyseg->length;
999
1000 if ((tmp=(uint) (from_end-from)) <= length)
1001 {
1002 key+=tmp; /* Use old key */
1003 length-=tmp;
1004 from=page; from_end=page_end;
1005 }
1006 DBUG_PRINT("info",("key: %p from: %p length: %u",
1007 key, from, length));
1008 memmove((uchar*) key, (uchar*) from, (size_t) length);
1009 key+=length;
1010 from+=length;
1011 }
1012 /*
1013 Last segment (type == 0) contains length of data pointer.
1014 If we have mixed key blocks with data pointer and key block pointer,
1015 we have to copy both.
1016 */
1017 length=keyseg->length+nod_flag;
1018 if ((tmp=(uint) (from_end-from)) <= length)
1019 {
1020 /* Remaining length is less or equal max possible length. */
1021 memcpy(key+tmp,page,length-tmp); /* Get last part of key */
1022 *page_pos= page+length-tmp;
1023 }
1024 else
1025 {
1026 /*
1027 Remaining length is greater than max possible length.
1028 This can happen only if we switched to the new key bytes already.
1029 'page_end' is calculated with MI_MAX_KEY_BUFF. So it can be far
1030 behind the real end of the key.
1031 */
1032 if (from_end != page_end)
1033 {
1034 DBUG_PRINT("error",("Error when unpacking key"));
1035 goto crashed; /* Error */
1036 }
1037 /* Copy data pointer and, if appropriate, key block pointer. */
1038 memcpy((uchar*) key,(uchar*) from,(size_t) length);
1039 *page_pos= from+length;
1040 }
1041 DBUG_RETURN((uint) (key-start_key)+keyseg->length);
1042
1043 crashed:
1044 mi_print_error(keyinfo->share, HA_ERR_CRASHED);
1045 my_errno= HA_ERR_CRASHED;
1046 DBUG_RETURN(0);
1047}
1048
1049
1050 /* Get key at position without knowledge of previous key */
1051 /* Returns pointer to next key */
1052
1053uchar *_mi_get_key(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *page,
1054 uchar *key, uchar *keypos, uint *return_key_length)
1055{
1056 uint nod_flag;
1057 DBUG_ENTER("_mi_get_key");
1058
1059 nod_flag=mi_test_if_nod(page);
1060 if (! (keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)))
1061 {
1062 bmove((uchar*) key,(uchar*) keypos,keyinfo->keylength+nod_flag);
1063 DBUG_RETURN(keypos+keyinfo->keylength+nod_flag);
1064 }
1065 else
1066 {
1067 page+=2+nod_flag;
1068 key[0]=0; /* safety */
1069 while (page <= keypos)
1070 {
1071 *return_key_length=(*keyinfo->get_key)(keyinfo,nod_flag,&page,key);
1072 if (*return_key_length == 0)
1073 {
1074 mi_print_error(info->s, HA_ERR_CRASHED);
1075 my_errno=HA_ERR_CRASHED;
1076 DBUG_RETURN(0);
1077 }
1078 }
1079 }
1080 DBUG_PRINT("exit",("page: %p length: %u", page,
1081 *return_key_length));
1082 DBUG_RETURN(page);
1083} /* _mi_get_key */
1084
1085
1086 /* Get key at position without knowledge of previous key */
1087 /* Returns 0 if ok */
1088
1089static my_bool _mi_get_prev_key(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *page,
1090 uchar *key, uchar *keypos,
1091 uint *return_key_length)
1092{
1093 uint nod_flag;
1094 DBUG_ENTER("_mi_get_prev_key");
1095
1096 nod_flag=mi_test_if_nod(page);
1097 if (! (keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)))
1098 {
1099 *return_key_length=keyinfo->keylength;
1100 bmove((uchar*) key,(uchar*) keypos- *return_key_length-nod_flag,
1101 *return_key_length);
1102 DBUG_RETURN(0);
1103 }
1104 else
1105 {
1106 page+=2+nod_flag;
1107 key[0]=0; /* safety */
1108 while (page < keypos)
1109 {
1110 *return_key_length=(*keyinfo->get_key)(keyinfo,nod_flag,&page,key);
1111 if (*return_key_length == 0)
1112 {
1113 mi_print_error(info->s, HA_ERR_CRASHED);
1114 my_errno=HA_ERR_CRASHED;
1115 DBUG_RETURN(1);
1116 }
1117 }
1118 }
1119 DBUG_RETURN(0);
1120} /* _mi_get_key */
1121
1122
1123
1124 /* Get last key from key-page */
1125 /* Return pointer to where key starts */
1126
1127uchar *_mi_get_last_key(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *page,
1128 uchar *lastkey, uchar *endpos, uint *return_key_length)
1129{
1130 uint nod_flag;
1131 uchar *lastpos;
1132 DBUG_ENTER("_mi_get_last_key");
1133 DBUG_PRINT("enter",("page:%p endpos: %p", page,
1134 endpos));
1135
1136 nod_flag=mi_test_if_nod(page);
1137 if (! (keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)))
1138 {
1139 lastpos=endpos-keyinfo->keylength-nod_flag;
1140 *return_key_length=keyinfo->keylength;
1141 if (lastpos > page)
1142 bmove((uchar*) lastkey,(uchar*) lastpos,keyinfo->keylength+nod_flag);
1143 }
1144 else
1145 {
1146 lastpos=(page+=2+nod_flag);
1147 lastkey[0]=0;
1148 while (page < endpos)
1149 {
1150 lastpos=page;
1151 *return_key_length=(*keyinfo->get_key)(keyinfo,nod_flag,&page,lastkey);
1152 if (*return_key_length == 0)
1153 {
1154 DBUG_PRINT("error",("Couldn't find last key: page: %p",
1155 page));
1156 mi_print_error(info->s, HA_ERR_CRASHED);
1157 my_errno=HA_ERR_CRASHED;
1158 DBUG_RETURN(0);
1159 }
1160 }
1161 }
1162 DBUG_PRINT("exit",("lastpos: %p length: %u", lastpos,
1163 *return_key_length));
1164 DBUG_RETURN(lastpos);
1165} /* _mi_get_last_key */
1166
1167
1168 /* Calculate length of key */
1169
1170uint _mi_keylength(MI_KEYDEF *keyinfo, register uchar *key)
1171{
1172 reg1 HA_KEYSEG *keyseg;
1173 uchar *start;
1174
1175 if (! (keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)))
1176 return (keyinfo->keylength);
1177
1178 start=key;
1179 for (keyseg=keyinfo->seg ; keyseg->type ; keyseg++)
1180 {
1181 if (keyseg->flag & HA_NULL_PART)
1182 if (!*key++)
1183 continue;
1184 if (keyseg->flag & (HA_SPACE_PACK | HA_BLOB_PART | HA_VAR_LENGTH_PART))
1185 {
1186 uint length;
1187 get_key_length(length,key);
1188 key+=length;
1189 }
1190 else
1191 key+= keyseg->length;
1192 }
1193 return((uint) (key-start)+keyseg->length);
1194} /* _mi_keylength */
1195
1196
1197/*
1198 Calculate length of part key.
1199
1200 Used in mi_rkey() to find the key found for the key-part that was used.
1201 This is needed in case of multi-byte character sets where we may search
1202 after '0xDF' but find 'ss'
1203*/
1204
1205uint _mi_keylength_part(MI_KEYDEF *keyinfo, register uchar *key,
1206 HA_KEYSEG *end)
1207{
1208 reg1 HA_KEYSEG *keyseg;
1209 uchar *start= key;
1210
1211 for (keyseg=keyinfo->seg ; keyseg != end ; keyseg++)
1212 {
1213 if (keyseg->flag & HA_NULL_PART)
1214 if (!*key++)
1215 continue;
1216 if (keyseg->flag & (HA_SPACE_PACK | HA_BLOB_PART | HA_VAR_LENGTH_PART))
1217 {
1218 uint length;
1219 get_key_length(length,key);
1220 key+=length;
1221 }
1222 else
1223 key+= keyseg->length;
1224 }
1225 return (uint) (key-start);
1226}
1227
1228 /* Move a key */
1229
1230uchar *_mi_move_key(MI_KEYDEF *keyinfo, uchar *to, uchar *from)
1231{
1232 reg1 uint length;
1233 memcpy((uchar*) to, (uchar*) from,
1234 (size_t) (length=_mi_keylength(keyinfo,from)));
1235 return to+length;
1236}
1237
1238 /* Find next/previous record with same key */
1239 /* This can't be used when database is touched after last read */
1240
1241int _mi_search_next(register MI_INFO *info, register MI_KEYDEF *keyinfo,
1242 uchar *key, uint key_length, uint nextflag, my_off_t pos)
1243{
1244 int error;
1245 uint nod_flag;
1246 uchar lastkey[HA_MAX_KEY_BUFF];
1247 DBUG_ENTER("_mi_search_next");
1248 DBUG_PRINT("enter",("nextflag: %u lastpos: %llu int_keypos: %p",
1249 nextflag, info->lastpos,
1250 info->int_keypos));
1251 DBUG_EXECUTE("key",_mi_print_key(DBUG_FILE,keyinfo->seg,key,key_length););
1252
1253 /* Force full read if we are at last key or if we are not on a leaf
1254 and the key tree has changed since we used it last time
1255 Note that even if the key tree has changed since last read, we can use
1256 the last read data from the leaf if we haven't used the buffer for
1257 something else.
1258 */
1259
1260 if (((nextflag & SEARCH_BIGGER) && info->int_keypos >= info->int_maxpos) ||
1261 info->page_changed ||
1262 (info->int_keytree_version != keyinfo->version &&
1263 (info->int_nod_flag || info->buff_used)))
1264 DBUG_RETURN(_mi_search(info,keyinfo,key, USE_WHOLE_KEY,
1265 nextflag | SEARCH_SAVE_BUFF, pos));
1266
1267 if (info->buff_used)
1268 {
1269 if (!_mi_fetch_keypage(info,keyinfo,info->last_search_keypage,
1270 DFLT_INIT_HITS,info->buff,0))
1271 DBUG_RETURN(-1);
1272 info->buff_used=0;
1273 }
1274
1275 /* Last used buffer is in info->buff */
1276 nod_flag=mi_test_if_nod(info->buff);
1277
1278 if (nextflag & SEARCH_BIGGER) /* Next key */
1279 {
1280 my_off_t tmp_pos=_mi_kpos(nod_flag,info->int_keypos);
1281 if (tmp_pos != HA_OFFSET_ERROR)
1282 {
1283 if ((error=_mi_search(info,keyinfo,key, USE_WHOLE_KEY,
1284 nextflag | SEARCH_SAVE_BUFF, tmp_pos)) <=0)
1285 DBUG_RETURN(error);
1286 }
1287 memcpy(lastkey,key,key_length);
1288 if (!(info->lastkey_length=(*keyinfo->get_key)(keyinfo,nod_flag,
1289 &info->int_keypos,lastkey)))
1290 DBUG_RETURN(-1);
1291 }
1292 else /* Previous key */
1293 {
1294 uint length;
1295 /* Find start of previous key */
1296 info->int_keypos=_mi_get_last_key(info,keyinfo,info->buff,lastkey,
1297 info->int_keypos, &length);
1298 if (!info->int_keypos)
1299 DBUG_RETURN(-1);
1300 if (info->int_keypos == info->buff+2)
1301 DBUG_RETURN(_mi_search(info,keyinfo,key, USE_WHOLE_KEY,
1302 nextflag | SEARCH_SAVE_BUFF, pos));
1303 if ((error=_mi_search(info,keyinfo,key, USE_WHOLE_KEY,
1304 nextflag | SEARCH_SAVE_BUFF,
1305 _mi_kpos(nod_flag,info->int_keypos))) <= 0)
1306 DBUG_RETURN(error);
1307
1308 /* QQ: We should be able to optimize away the following call */
1309 if (! _mi_get_last_key(info,keyinfo,info->buff,lastkey,
1310 info->int_keypos,&info->lastkey_length))
1311 DBUG_RETURN(-1);
1312 }
1313 memcpy(info->lastkey,lastkey,info->lastkey_length);
1314 info->lastpos=_mi_dpos(info,0,info->lastkey+info->lastkey_length);
1315 DBUG_PRINT("exit",("found key at %lu",(ulong) info->lastpos));
1316 DBUG_RETURN(0);
1317} /* _mi_search_next */
1318
1319
1320 /* Search after position for the first row in an index */
1321 /* This is stored in info->lastpos */
1322
1323int _mi_search_first(register MI_INFO *info, register MI_KEYDEF *keyinfo,
1324 register my_off_t pos)
1325{
1326 uint nod_flag;
1327 uchar *page;
1328 DBUG_ENTER("_mi_search_first");
1329
1330 if (pos == HA_OFFSET_ERROR)
1331 {
1332 my_errno=HA_ERR_KEY_NOT_FOUND;
1333 info->lastpos= HA_OFFSET_ERROR;
1334 DBUG_RETURN(-1);
1335 }
1336
1337 do
1338 {
1339 if (!_mi_fetch_keypage(info,keyinfo,pos,DFLT_INIT_HITS,info->buff,0))
1340 {
1341 info->lastpos= HA_OFFSET_ERROR;
1342 DBUG_RETURN(-1);
1343 }
1344 nod_flag=mi_test_if_nod(info->buff);
1345 page=info->buff+2+nod_flag;
1346 } while ((pos=_mi_kpos(nod_flag,page)) != HA_OFFSET_ERROR);
1347
1348 if (!(info->lastkey_length=(*keyinfo->get_key)(keyinfo,nod_flag,&page,
1349 info->lastkey)))
1350 DBUG_RETURN(-1); /* Crashed */
1351
1352 info->int_keypos=page; info->int_maxpos=info->buff+mi_getint(info->buff)-1;
1353 info->int_nod_flag=nod_flag;
1354 info->int_keytree_version=keyinfo->version;
1355 info->last_search_keypage=info->last_keypage;
1356 info->page_changed=info->buff_used=0;
1357 info->lastpos=_mi_dpos(info,0,info->lastkey+info->lastkey_length);
1358
1359 DBUG_PRINT("exit",("found key at %lu", (ulong) info->lastpos));
1360 DBUG_RETURN(0);
1361} /* _mi_search_first */
1362
1363
1364 /* Search after position for the last row in an index */
1365 /* This is stored in info->lastpos */
1366
1367int _mi_search_last(register MI_INFO *info, register MI_KEYDEF *keyinfo,
1368 register my_off_t pos)
1369{
1370 uint nod_flag;
1371 uchar *buff,*page;
1372 DBUG_ENTER("_mi_search_last");
1373
1374 if (pos == HA_OFFSET_ERROR)
1375 {
1376 my_errno=HA_ERR_KEY_NOT_FOUND; /* Didn't find key */
1377 info->lastpos= HA_OFFSET_ERROR;
1378 DBUG_RETURN(-1);
1379 }
1380
1381 buff=info->buff;
1382 do
1383 {
1384 if (!_mi_fetch_keypage(info,keyinfo,pos,DFLT_INIT_HITS,buff,0))
1385 {
1386 info->lastpos= HA_OFFSET_ERROR;
1387 DBUG_RETURN(-1);
1388 }
1389 page= buff+mi_getint(buff);
1390 nod_flag=mi_test_if_nod(buff);
1391 } while ((pos=_mi_kpos(nod_flag,page)) != HA_OFFSET_ERROR);
1392
1393 if (!_mi_get_last_key(info,keyinfo,buff,info->lastkey,page,
1394 &info->lastkey_length))
1395 DBUG_RETURN(-1);
1396 info->lastpos=_mi_dpos(info,0,info->lastkey+info->lastkey_length);
1397 info->int_keypos=info->int_maxpos=page;
1398 info->int_nod_flag=nod_flag;
1399 info->int_keytree_version=keyinfo->version;
1400 info->last_search_keypage=info->last_keypage;
1401 info->page_changed=info->buff_used=0;
1402
1403 DBUG_PRINT("exit",("found key at %lu",(ulong) info->lastpos));
1404 DBUG_RETURN(0);
1405} /* _mi_search_last */
1406
1407
1408
1409/****************************************************************************
1410**
1411** Functions to store and pack a key in a page
1412**
1413** mi_calc_xx_key_length takes the following arguments:
1414** nod_flag If nod: Length of nod-pointer
1415** next_key Position to pos after the new key in buffer
1416** org_key Key that was before the next key in buffer
1417** prev_key Last key before current key
1418** key Key that will be stored
1419** s_temp Information how next key will be packed
1420****************************************************************************/
1421
1422/* Static length key */
1423
1424int
1425_mi_calc_static_key_length(MI_KEYDEF *keyinfo,uint nod_flag,
1426 uchar *next_pos __attribute__((unused)),
1427 uchar *org_key __attribute__((unused)),
1428 uchar *prev_key __attribute__((unused)),
1429 uchar *key, MI_KEY_PARAM *s_temp)
1430{
1431 s_temp->key=key;
1432 return (int) (s_temp->totlength=keyinfo->keylength+nod_flag);
1433}
1434
1435/* Variable length key */
1436
1437int
1438_mi_calc_var_key_length(MI_KEYDEF *keyinfo,uint nod_flag,
1439 uchar *next_pos __attribute__((unused)),
1440 uchar *org_key __attribute__((unused)),
1441 uchar *prev_key __attribute__((unused)),
1442 uchar *key, MI_KEY_PARAM *s_temp)
1443{
1444 s_temp->key=key;
1445 return (int) (s_temp->totlength=_mi_keylength(keyinfo,key)+nod_flag);
1446}
1447
1448/*
1449 length of key with a variable length first segment which is prefix
1450 compressed (myisamchk reports 'packed + stripped')
1451
1452 Keys are compressed the following way:
1453
1454 If the max length of first key segment <= 127 bytes the prefix is
1455 1 byte else it's 2 byte
1456
1457 prefix byte(s) The high bit is set if this is a prefix for the prev key
1458 length Packed length if the previous was a prefix byte
1459 [length] data bytes ('length' bytes)
1460 next-key-seg Next key segments
1461
1462 If the first segment can have NULL:
1463 The length is 0 for NULLS and 1+length for not null columns.
1464
1465*/
1466
1467int
1468_mi_calc_var_pack_key_length(MI_KEYDEF *keyinfo,uint nod_flag,uchar *next_key,
1469 uchar *org_key, uchar *prev_key, uchar *key,
1470 MI_KEY_PARAM *s_temp)
1471{
1472 reg1 HA_KEYSEG *keyseg;
1473 int length;
1474 uint key_length,ref_length,org_key_length=0,
1475 length_pack,new_key_length,diff_flag,pack_marker;
1476 uchar *start,*end,*key_end;
1477 const uchar *sort_order;
1478 my_bool same_length;
1479
1480 length_pack=s_temp->ref_length=s_temp->n_ref_length=s_temp->n_length=0;
1481 same_length=0; keyseg=keyinfo->seg;
1482 key_length=_mi_keylength(keyinfo,key)+nod_flag;
1483
1484 sort_order=0;
1485 if ((keyinfo->flag & HA_FULLTEXT) &&
1486 ((keyseg->type == HA_KEYTYPE_TEXT) ||
1487 (keyseg->type == HA_KEYTYPE_VARTEXT1) ||
1488 (keyseg->type == HA_KEYTYPE_VARTEXT2)) &&
1489 !use_strnxfrm(keyseg->charset))
1490 sort_order=keyseg->charset->sort_order;
1491
1492 /* diff flag contains how many bytes is needed to pack key */
1493 if (keyseg->length >= 127)
1494 {
1495 diff_flag=2;
1496 pack_marker=32768;
1497 }
1498 else
1499 {
1500 diff_flag= 1;
1501 pack_marker=128;
1502 }
1503 s_temp->pack_marker=pack_marker;
1504
1505 /* Handle the case that the first part have NULL values */
1506 if (keyseg->flag & HA_NULL_PART)
1507 {
1508 if (!*key++)
1509 {
1510 s_temp->key=key;
1511 s_temp->key_length= 0;
1512 s_temp->totlength=key_length-1+diff_flag;
1513 s_temp->next_key_pos=0; /* No next key */
1514 return (s_temp->totlength);
1515 }
1516 s_temp->store_not_null=1;
1517 key_length--; /* We don't store NULL */
1518 if (prev_key && !*prev_key++)
1519 org_key=prev_key=0; /* Can't pack against prev */
1520 else if (org_key)
1521 org_key++; /* Skip NULL */
1522 }
1523 else
1524 s_temp->store_not_null=0;
1525 s_temp->prev_key=org_key;
1526
1527 /* The key part will start with a packed length */
1528
1529 get_key_pack_length(new_key_length,length_pack,key);
1530 end=key_end= key+ new_key_length;
1531 start=key;
1532
1533 /* Calc how many characters are identical between this and the prev. key */
1534 if (prev_key)
1535 {
1536 get_key_length(org_key_length,prev_key);
1537 s_temp->prev_key=prev_key; /* Pointer at data */
1538 /* Don't use key-pack if length == 0 */
1539 if (new_key_length && new_key_length == org_key_length)
1540 same_length=1;
1541 else if (new_key_length > org_key_length)
1542 end=key + org_key_length;
1543
1544 if (sort_order) /* SerG */
1545 {
1546 while (key < end && sort_order[*key] == sort_order[*prev_key])
1547 {
1548 key++; prev_key++;
1549 }
1550 }
1551 else
1552 {
1553 while (key < end && *key == *prev_key)
1554 {
1555 key++; prev_key++;
1556 }
1557 }
1558 }
1559
1560 s_temp->key=key;
1561 s_temp->key_length= (uint) (key_end-key);
1562
1563 if (same_length && key == key_end)
1564 {
1565 /* identical variable length key */
1566 s_temp->ref_length= pack_marker;
1567 length=(int) key_length-(int) (key_end-start)-length_pack;
1568 length+= diff_flag;
1569 if (next_key)
1570 { /* Can't combine with next */
1571 s_temp->n_length= *next_key; /* Needed by _mi_store_key */
1572 next_key=0;
1573 }
1574 }
1575 else
1576 {
1577 if (start != key)
1578 { /* Starts as prev key */
1579 ref_length= (uint) (key-start);
1580 s_temp->ref_length= ref_length + pack_marker;
1581 length= (int) (key_length - ref_length);
1582
1583 length-= length_pack;
1584 length+= diff_flag;
1585 length+= ((new_key_length-ref_length) >= 255) ? 3 : 1;/* Rest_of_key */
1586 }
1587 else
1588 {
1589 s_temp->key_length+=s_temp->store_not_null; /* If null */
1590 length= key_length - length_pack+ diff_flag;
1591 }
1592 }
1593 s_temp->totlength=(uint) length;
1594 s_temp->prev_length=0;
1595 DBUG_PRINT("test",("tot_length: %u length: %d uniq_key_length: %u",
1596 key_length, length, s_temp->key_length));
1597
1598 /* If something after that hasn't length=0, test if we can combine */
1599 if ((s_temp->next_key_pos=next_key))
1600 {
1601 uint packed,n_length;
1602
1603 packed = *next_key & 128;
1604 if (diff_flag == 2)
1605 {
1606 n_length= mi_uint2korr(next_key) & 32767; /* Length of next key */
1607 next_key+=2;
1608 }
1609 else
1610 n_length= *next_key++ & 127;
1611 if (!packed)
1612 n_length-= s_temp->store_not_null;
1613
1614 if (n_length || packed) /* Don't pack 0 length keys */
1615 {
1616 uint next_length_pack, new_ref_length=s_temp->ref_length;
1617
1618 if (packed)
1619 {
1620 /* If first key and next key is packed (only on delete) */
1621 if (!prev_key && org_key)
1622 {
1623 get_key_length(org_key_length,org_key);
1624 key=start;
1625 if (sort_order) /* SerG */
1626 {
1627 while (key < end && sort_order[*key] == sort_order[*org_key])
1628 {
1629 key++; org_key++;
1630 }
1631 }
1632 else
1633 {
1634 while (key < end && *key == *org_key)
1635 {
1636 key++; org_key++;
1637 }
1638 }
1639 if ((new_ref_length= (uint) (key - start)))
1640 new_ref_length+=pack_marker;
1641 }
1642
1643 if (!n_length)
1644 {
1645 /*
1646 We put a different key between two identical variable length keys
1647 Extend next key to have same prefix as this key
1648 */
1649 if (new_ref_length) /* prefix of previus key */
1650 { /* make next key longer */
1651 s_temp->part_of_prev_key= new_ref_length;
1652 s_temp->prev_length= org_key_length -
1653 (new_ref_length-pack_marker);
1654 s_temp->n_ref_length= s_temp->part_of_prev_key;
1655 s_temp->n_length= s_temp->prev_length;
1656 n_length= get_pack_length(s_temp->prev_length);
1657 s_temp->prev_key+= (new_ref_length - pack_marker);
1658 length+= s_temp->prev_length + n_length;
1659 }
1660 else
1661 { /* Can't use prev key */
1662 s_temp->part_of_prev_key=0;
1663 s_temp->prev_length= org_key_length;
1664 s_temp->n_ref_length=s_temp->n_length= org_key_length;
1665 length+= org_key_length;
1666 }
1667 return (int) length;
1668 }
1669
1670 ref_length=n_length;
1671 /* Get information about not packed key suffix */
1672 get_key_pack_length(n_length,next_length_pack,next_key);
1673
1674 /* Test if new keys has fewer characters that match the previous key */
1675 if (!new_ref_length)
1676 { /* Can't use prev key */
1677 s_temp->part_of_prev_key= 0;
1678 s_temp->prev_length= ref_length;
1679 s_temp->n_ref_length= s_temp->n_length= n_length+ref_length;
1680 return (int) length+ref_length-next_length_pack;
1681 }
1682 if (ref_length+pack_marker > new_ref_length)
1683 {
1684 uint new_pack_length=new_ref_length-pack_marker;
1685 /* We must copy characters from the original key to the next key */
1686 s_temp->part_of_prev_key= new_ref_length;
1687 s_temp->prev_length= ref_length - new_pack_length;
1688 s_temp->n_ref_length=s_temp->n_length=n_length + s_temp->prev_length;
1689 s_temp->prev_key+= new_pack_length;
1690 length-= (next_length_pack - get_pack_length(s_temp->n_length));
1691 return (int) length + s_temp->prev_length;
1692 }
1693 }
1694 else
1695 {
1696 /* Next key wasn't a prefix of previous key */
1697 ref_length=0;
1698 next_length_pack=0;
1699 }
1700 DBUG_PRINT("test",("length: %d next_key: %p", length,
1701 next_key));
1702
1703 {
1704 uint tmp_length;
1705 key=(start+=ref_length);
1706 if (key+n_length < key_end) /* Normalize length based */
1707 key_end=key+n_length;
1708 if (sort_order) /* SerG */
1709 {
1710 while (key < key_end && sort_order[*key] ==
1711 sort_order[*next_key])
1712 {
1713 key++; next_key++;
1714 }
1715 }
1716 else
1717 {
1718 while (key < key_end && *key == *next_key)
1719 {
1720 key++; next_key++;
1721 }
1722 }
1723 if (!(tmp_length=(uint) (key-start)))
1724 { /* Key can't be re-packed */
1725 s_temp->next_key_pos=0;
1726 return length;
1727 }
1728 ref_length+=tmp_length;
1729 n_length-=tmp_length;
1730 length-=tmp_length+next_length_pack; /* We gained these chars */
1731 }
1732 if (n_length == 0 && ref_length == new_key_length)
1733 {
1734 s_temp->n_ref_length=pack_marker; /* Same as prev key */
1735 }
1736 else
1737 {
1738 s_temp->n_ref_length=ref_length | pack_marker;
1739 length+= get_pack_length(n_length);
1740 s_temp->n_length=n_length;
1741 }
1742 }
1743 }
1744 return length;
1745}
1746
1747
1748/* Length of key which is prefix compressed */
1749
1750int
1751_mi_calc_bin_pack_key_length(MI_KEYDEF *keyinfo,uint nod_flag,uchar *next_key,
1752 uchar *org_key, uchar *prev_key, uchar *key,
1753 MI_KEY_PARAM *s_temp)
1754{
1755 uint length,key_length,ref_length;
1756
1757 s_temp->totlength=key_length=_mi_keylength(keyinfo,key)+nod_flag;
1758#ifdef HAVE_valgrind
1759 s_temp->n_length= s_temp->n_ref_length=0; /* For valgrind */
1760#endif
1761 s_temp->key=key;
1762 s_temp->prev_key=org_key;
1763 if (prev_key) /* If not first key in block */
1764 {
1765 /* pack key against previous key */
1766 /*
1767 As keys may be identical when running a sort in myisamchk, we
1768 have to guard against the case where keys may be identical
1769 */
1770 uchar *end;
1771 end=key+key_length;
1772 for ( ; *key == *prev_key && key < end; key++,prev_key++) ;
1773 s_temp->ref_length= ref_length=(uint) (key-s_temp->key);
1774 length=key_length - ref_length + get_pack_length(ref_length);
1775 }
1776 else
1777 {
1778 /* No previous key */
1779 s_temp->ref_length=ref_length=0;
1780 length=key_length+1;
1781 }
1782 if ((s_temp->next_key_pos=next_key)) /* If another key after */
1783 {
1784 /* pack key against next key */
1785 uint next_length,next_length_pack;
1786 get_key_pack_length(next_length,next_length_pack,next_key);
1787
1788 /* If first key and next key is packed (only on delete) */
1789 if (!prev_key && org_key && next_length)
1790 {
1791 uchar *end;
1792 for (key= s_temp->key, end=key+next_length ;
1793 *key == *org_key && key < end;
1794 key++,org_key++) ;
1795 ref_length= (uint) (key - s_temp->key);
1796 }
1797
1798 if (next_length > ref_length)
1799 {
1800 /* We put a key with different case between two keys with the same prefix
1801 Extend next key to have same prefix as
1802 this key */
1803 s_temp->n_ref_length= ref_length;
1804 s_temp->prev_length= next_length-ref_length;
1805 s_temp->prev_key+= ref_length;
1806 return (int) (length+ s_temp->prev_length - next_length_pack +
1807 get_pack_length(ref_length));
1808 }
1809 /* Check how many characters are identical to next key */
1810 key= s_temp->key+next_length;
1811 s_temp->prev_length= 0;
1812 while (*key++ == *next_key++) ;
1813 if ((ref_length= (uint) (key - s_temp->key)-1) == next_length)
1814 {
1815 s_temp->next_key_pos=0;
1816 return length; /* can't pack next key */
1817 }
1818 s_temp->n_ref_length=ref_length;
1819 return (int) (length-(ref_length - next_length) - next_length_pack +
1820 get_pack_length(ref_length));
1821 }
1822 return (int) length;
1823}
1824
1825
1826/*
1827** store a key packed with _mi_calc_xxx_key_length in page-buffert
1828*/
1829
1830/* store key without compression */
1831
1832void _mi_store_static_key(MI_KEYDEF *keyinfo __attribute__((unused)),
1833 register uchar *key_pos,
1834 register MI_KEY_PARAM *s_temp)
1835{
1836 memcpy((uchar*) key_pos,(uchar*) s_temp->key,(size_t) s_temp->totlength);
1837}
1838
1839
1840/* store variable length key with prefix compression */
1841
1842#define store_pack_length(test,pos,length) { \
1843 if (test) { *((pos)++) = (uchar) (length); } else \
1844 { *((pos)++) = (uchar) ((length) >> 8); *((pos)++) = (uchar) (length); } }
1845
1846
1847void _mi_store_var_pack_key(MI_KEYDEF *keyinfo __attribute__((unused)),
1848 register uchar *key_pos,
1849 register MI_KEY_PARAM *s_temp)
1850{
1851 uint length;
1852 uchar *start;
1853
1854 start=key_pos;
1855
1856 if (s_temp->ref_length)
1857 {
1858 /* Packed against previous key */
1859 store_pack_length(s_temp->pack_marker == 128,key_pos,s_temp->ref_length);
1860 /* If not same key after */
1861 if (s_temp->ref_length != s_temp->pack_marker)
1862 store_key_length_inc(key_pos,s_temp->key_length);
1863 }
1864 else
1865 {
1866 /* Not packed against previous key */
1867 store_pack_length(s_temp->pack_marker == 128,key_pos,s_temp->key_length);
1868 }
1869 bmove((uchar*) key_pos,(uchar*) s_temp->key,
1870 (length=s_temp->totlength-(uint) (key_pos-start)));
1871
1872 if (!s_temp->next_key_pos) /* No following key */
1873 return;
1874 key_pos+=length;
1875
1876 if (s_temp->prev_length)
1877 {
1878 /* Extend next key because new key didn't have same prefix as prev key */
1879 if (s_temp->part_of_prev_key)
1880 {
1881 store_pack_length(s_temp->pack_marker == 128,key_pos,
1882 s_temp->part_of_prev_key);
1883 store_key_length_inc(key_pos,s_temp->n_length);
1884 }
1885 else
1886 {
1887 s_temp->n_length+= s_temp->store_not_null;
1888 store_pack_length(s_temp->pack_marker == 128,key_pos,
1889 s_temp->n_length);
1890 }
1891 memcpy(key_pos, s_temp->prev_key, s_temp->prev_length);
1892 }
1893 else if (s_temp->n_ref_length)
1894 {
1895 store_pack_length(s_temp->pack_marker == 128,key_pos,s_temp->n_ref_length);
1896 if (s_temp->n_ref_length == s_temp->pack_marker)
1897 return; /* Identical key */
1898 store_key_length(key_pos,s_temp->n_length);
1899 }
1900 else
1901 {
1902 s_temp->n_length+= s_temp->store_not_null;
1903 store_pack_length(s_temp->pack_marker == 128,key_pos,s_temp->n_length);
1904 }
1905}
1906
1907
1908/* variable length key with prefix compression */
1909
1910void _mi_store_bin_pack_key(MI_KEYDEF *keyinfo __attribute__((unused)),
1911 register uchar *key_pos,
1912 register MI_KEY_PARAM *s_temp)
1913{
1914 store_key_length_inc(key_pos,s_temp->ref_length);
1915 memcpy((char*) key_pos,(char*) s_temp->key+s_temp->ref_length,
1916 (size_t) s_temp->totlength-s_temp->ref_length);
1917
1918 if (s_temp->next_key_pos)
1919 {
1920 key_pos+=(uint) (s_temp->totlength-s_temp->ref_length);
1921 store_key_length_inc(key_pos,s_temp->n_ref_length);
1922 if (s_temp->prev_length) /* If we must extend key */
1923 {
1924 memcpy(key_pos,s_temp->prev_key,s_temp->prev_length);
1925 }
1926 }
1927}
1928