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