1/* Copyright (C) 2006 MySQL AB & MySQL Finland AB & TCX DataKonsult 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 Street, Fifth Floor, Boston, MA 02111-1301 USA */
15
16/* key handling functions */
17
18#include "ma_fulltext.h"
19#include "m_ctype.h"
20
21static int _ma_search_no_save(register MARIA_HA *info, MARIA_KEY *key,
22 uint32 nextflag, register my_off_t pos,
23 MARIA_PINNED_PAGE **res_page_link,
24 uchar **res_page_buff);
25static my_bool _ma_get_prev_key(MARIA_KEY *key, MARIA_PAGE *ma_page,
26 uchar *keypos);
27
28
29/* Check that new index is ok */
30
31int _ma_check_index(MARIA_HA *info, int inx)
32{
33 if (inx < 0 || ! maria_is_key_active(info->s->state.key_map, inx))
34 {
35 my_errno=HA_ERR_WRONG_INDEX;
36 return -1;
37 }
38 if (info->lastinx != inx) /* Index changed */
39 {
40 info->lastinx = inx;
41 info->last_key.keyinfo= info->s->keyinfo + inx;
42 info->last_key.flag= 0;
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) && flush_io_cache(&info->rec_cache))
48 {
49 if (unlikely(!my_errno))
50 my_errno= HA_ERR_INTERNAL_ERROR; /* Impossible */
51 return(-1);
52 }
53 return(inx);
54} /* _ma_check_index */
55
56
57/**
58 @breif Search after row by a key
59
60 @note
61 Position to row is stored in info->lastpos
62
63 @return
64 @retval 0 ok (key found)
65 @retval -1 Not found
66 @retval 1 If one should continue search on higher level
67*/
68
69int _ma_search(register MARIA_HA *info, MARIA_KEY *key, uint32 nextflag,
70 my_off_t pos)
71{
72 int error;
73 MARIA_PINNED_PAGE *page_link;
74 uchar *page_buff;
75
76 info->page_changed= 1; /* If page not saved */
77 if (!(error= _ma_search_no_save(info, key, nextflag, pos, &page_link,
78 &page_buff)))
79 {
80 if (nextflag & SEARCH_SAVE_BUFF)
81 {
82 memcpy(info->keyread_buff, page_buff, info->s->block_size);
83
84 /* Save position for a possible read next / previous */
85 info->int_keypos= info->keyread_buff + info->keypos_offset;
86 info->int_maxpos= info->keyread_buff + info->maxpos_offset;
87 info->int_keytree_version= key->keyinfo->version;
88 info->last_search_keypage= info->last_keypage;
89 info->page_changed= 0;
90 info->keyread_buff_used= 0;
91 }
92 }
93 _ma_unpin_all_pages(info, LSN_IMPOSSIBLE);
94 return (error);
95}
96
97/**
98 @breif Search after row by a key
99
100 ret_page_link Will contain pointer to page where we found key
101
102 @note
103 Position to row is stored in info->lastpos
104 Last used key is stored in info->last_key
105
106 @return
107 @retval 0 ok (key found)
108 @retval -1 Not found
109 @retval 1 If one should continue search on higher level
110*/
111
112static int _ma_search_no_save(register MARIA_HA *info, MARIA_KEY *key,
113 uint32 nextflag, register my_off_t pos,
114 MARIA_PINNED_PAGE **res_page_link,
115 uchar **res_page_buff)
116{
117 my_bool last_key_not_used;
118 int error,flag;
119 uint page_flag, nod_flag, used_length;
120 uchar *keypos,*maxpos;
121 uchar lastkey[MARIA_MAX_KEY_BUFF];
122 MARIA_KEYDEF *keyinfo= key->keyinfo;
123 MARIA_PAGE page;
124 MARIA_PINNED_PAGE *page_link;
125 DBUG_ENTER("_ma_search");
126 DBUG_PRINT("enter",("page: %lu nextflag: %u lastpos: %lu",
127 (ulong) (pos / info->s->block_size),
128 nextflag, (ulong) info->cur_row.lastpos));
129 DBUG_EXECUTE("key", _ma_print_key(DBUG_FILE, key););
130 DBUG_ASSERT(info->last_key.keyinfo == key->keyinfo);
131
132 if (pos == HA_OFFSET_ERROR)
133 {
134 my_errno=HA_ERR_KEY_NOT_FOUND; /* Didn't find key */
135 info->cur_row.lastpos= HA_OFFSET_ERROR;
136 if (!(nextflag & (SEARCH_SMALLER | SEARCH_BIGGER | SEARCH_LAST)))
137 DBUG_RETURN(-1); /* Not found ; return error */
138 DBUG_RETURN(1); /* Search at upper levels */
139 }
140
141 if (_ma_fetch_keypage(&page, info, keyinfo, pos,
142 PAGECACHE_LOCK_READ, DFLT_INIT_HITS, 0, 0))
143 goto err;
144 page_link= dynamic_element(&info->pinned_pages,
145 info->pinned_pages.elements-1,
146 MARIA_PINNED_PAGE*);
147 DBUG_DUMP("page", page.buff, page.size);
148
149 flag= (*keyinfo->bin_search)(key, &page, nextflag, &keypos, lastkey,
150 &last_key_not_used);
151 if (flag == MARIA_FOUND_WRONG_KEY)
152 {
153 maria_print_error(info->s, HA_ERR_CRASHED);
154 my_errno= HA_ERR_CRASHED;
155 goto err;
156 }
157 page_flag= page.flag;
158 used_length= page.size;
159 nod_flag= page.node;
160 maxpos= page.buff + used_length -1;
161
162 if (flag)
163 {
164 if ((error= _ma_search_no_save(info, key, nextflag,
165 _ma_kpos(nod_flag,keypos),
166 res_page_link, res_page_buff)) <= 0)
167 DBUG_RETURN(error);
168
169 if (flag >0)
170 {
171 if (nextflag & (SEARCH_SMALLER | SEARCH_LAST) &&
172 keypos == page.buff + info->s->keypage_header + nod_flag)
173 DBUG_RETURN(1); /* Bigger than key */
174 }
175 else if (nextflag & SEARCH_BIGGER && keypos >= maxpos)
176 DBUG_RETURN(1); /* Smaller than key */
177 }
178 else
179 {
180 /* Found matching key */
181 if ((nextflag & SEARCH_FIND) && nod_flag &&
182 ((keyinfo->flag & (HA_NOSAME | HA_NULL_PART)) != HA_NOSAME ||
183 (key->flag & SEARCH_PART_KEY) || info->s->base.born_transactional))
184 {
185 if ((error= _ma_search_no_save(info, key, (nextflag | SEARCH_FIND) &
186 ~(SEARCH_BIGGER | SEARCH_SMALLER |
187 SEARCH_LAST),
188 _ma_kpos(nod_flag,keypos),
189 res_page_link, res_page_buff)) >= 0 ||
190 my_errno != HA_ERR_KEY_NOT_FOUND)
191 DBUG_RETURN(error);
192 }
193 }
194
195 if ((nextflag & (SEARCH_SMALLER | SEARCH_LAST)) && flag != 0)
196 {
197 uint not_used[2];
198 if (_ma_get_prev_key(&info->last_key, &page, keypos))
199 goto err;
200 /*
201 We have to use key->flag >> 1 here to transform
202 SEARCH_PAGE_KEY_HAS_TRANSID to SEARCH_USER_KEY_HAS_TRANSID
203 */
204 if (!(nextflag & SEARCH_SMALLER) &&
205 ha_key_cmp(keyinfo->seg, info->last_key.data, key->data,
206 key->data_length + key->ref_length,
207 SEARCH_FIND | (key->flag >> 1) | info->last_key.flag,
208 not_used))
209 {
210 my_errno=HA_ERR_KEY_NOT_FOUND; /* Didn't find key */
211 goto err;
212 }
213 }
214 else
215 {
216 /* Set info->last_key to temporarily point to last key value */
217 info->last_key.data= lastkey;
218 /* Get key value (if not packed key) and position after key */
219 if (!(*keyinfo->get_key)(&info->last_key, page_flag, nod_flag, &keypos))
220 goto err;
221 memcpy(info->lastkey_buff, lastkey,
222 info->last_key.data_length + info->last_key.ref_length);
223 info->last_key.data= info->lastkey_buff;
224 }
225 info->cur_row.lastpos= _ma_row_pos_from_key(&info->last_key);
226 info->cur_row.trid= _ma_trid_from_key(&info->last_key);
227
228 /* Store offset to key */
229 info->keypos_offset= (uint) (keypos - page.buff);
230 info->maxpos_offset= (uint) (maxpos - page.buff);
231 info->int_nod_flag= nod_flag;
232 info->last_keypage= pos;
233 *res_page_link= page_link;
234 *res_page_buff= page.buff;
235
236 DBUG_PRINT("exit",("found key at %lu",(ulong) info->cur_row.lastpos));
237 DBUG_RETURN(0);
238
239err:
240 DBUG_PRINT("exit",("Error: %d",my_errno));
241 info->cur_row.lastpos= HA_OFFSET_ERROR;
242 info->page_changed=1;
243 DBUG_RETURN (-1);
244}
245
246
247/*
248 Search after key in page-block
249
250 @fn _ma_bin_search
251 @param key Search after this key
252 @param page Start of data page
253 @param comp_flag How key should be compared
254 @param ret_pos
255 @param buff Buffer for holding a key (not used here)
256 @param last_key
257
258 @note
259 If keys are packed, then smaller or identical key is stored in buff
260
261 @return
262 @retval <0, 0 , >0 depending on if if found is smaller, equal or bigger than
263 'key'
264 @retval ret_pos Points to where the identical or bigger key starts
265 @retval last_key Set to 1 if key is the last key in the page.
266*/
267
268int _ma_bin_search(const MARIA_KEY *key, const MARIA_PAGE *ma_page,
269 uint32 comp_flag, uchar **ret_pos,
270 uchar *buff __attribute__((unused)), my_bool *last_key)
271{
272 int UNINIT_VAR(flag);
273 uint page_flag;
274 uint start, mid, end, save_end, totlength, nod_flag;
275 uint not_used[2];
276 MARIA_KEYDEF *keyinfo= key->keyinfo;
277 MARIA_SHARE *share= keyinfo->share;
278 uchar *page;
279 DBUG_ENTER("_ma_bin_search");
280
281 page_flag= ma_page->flag;
282 if (page_flag & KEYPAGE_FLAG_HAS_TRANSID)
283 {
284 /* Keys have varying length, can't use binary search */
285 DBUG_RETURN(_ma_seq_search(key, ma_page, comp_flag, ret_pos, buff,
286 last_key));
287 }
288
289 nod_flag= ma_page->node;
290 totlength= keyinfo->keylength + nod_flag;
291 DBUG_ASSERT(ma_page->size >= share->keypage_header + nod_flag + totlength);
292
293 start=0;
294 mid=1;
295 save_end= end= ((ma_page->size - nod_flag - share->keypage_header) /
296 totlength-1);
297 DBUG_PRINT("test",("page_length: %u end: %u", ma_page->size, end));
298 page= ma_page->buff + share->keypage_header + nod_flag;
299
300 while (start != end)
301 {
302 mid= (start+end)/2;
303 if ((flag=ha_key_cmp(keyinfo->seg, page + (uint) mid * totlength,
304 key->data, key->data_length + key->ref_length,
305 comp_flag, not_used))
306 >= 0)
307 end=mid;
308 else
309 start=mid+1;
310 }
311 if (mid != start)
312 flag=ha_key_cmp(keyinfo->seg, page + (uint) start * totlength,
313 key->data, key->data_length + key->ref_length, comp_flag,
314 not_used);
315 if (flag < 0)
316 start++; /* point at next, bigger key */
317 *ret_pos= (page + (uint) start * totlength);
318 *last_key= end == save_end;
319 DBUG_PRINT("exit",("flag: %d keypos: %d",flag,start));
320 DBUG_RETURN(flag);
321} /* _ma_bin_search */
322
323
324/**
325 Locate a packed key in a key page.
326
327 @fn _ma_seq_search()
328 @param key Search key.
329 @param page Key page (beginning).
330 @param comp_flag Search flags like SEARCH_SAME etc.
331 @param ret_pos
332 @param buff Buffer for holding temp keys
333 @param last_key
334
335 @description
336 Used instead of _ma_bin_search() when key is packed.
337 Puts smaller or identical key in buff.
338 Key is searched sequentially.
339
340 @todo
341 Don't copy key to buffer if we are not using key with prefix packing
342
343 @return
344 @retval > 0 Key in 'buff' is smaller than search key.
345 @retval 0 Key in 'buff' is identical to search key.
346 @retval < 0 Not found.
347
348 @retval ret_pos Points to where the identical or bigger key starts
349 @retval last_key Set to 1 if key is the last key in the page
350 @retval buff Copy of previous or identical unpacked key
351*/
352
353int _ma_seq_search(const MARIA_KEY *key, const MARIA_PAGE *ma_page,
354 uint32 comp_flag, uchar **ret_pos,
355 uchar *buff, my_bool *last_key)
356{
357 int UNINIT_VAR(flag);
358 uint page_flag, nod_flag, UNINIT_VAR(length), not_used[2];
359 uchar t_buff[MARIA_MAX_KEY_BUFF], *end;
360 uchar *page;
361 MARIA_KEYDEF *keyinfo= key->keyinfo;
362 MARIA_SHARE *share= keyinfo->share;
363 MARIA_KEY tmp_key;
364 DBUG_ENTER("_ma_seq_search");
365
366 page_flag= ma_page->flag;
367 nod_flag= ma_page->node;
368 page= ma_page->buff;
369 end= page + ma_page->size;
370 page+= share->keypage_header + nod_flag;
371 *ret_pos= page;
372 t_buff[0]=0; /* Avoid bugs */
373
374 tmp_key.data= t_buff;
375 tmp_key.keyinfo= keyinfo;
376 while (page < end)
377 {
378 length=(*keyinfo->get_key)(&tmp_key, page_flag, nod_flag, &page);
379 if (length == 0 || page > end)
380 {
381 _ma_set_fatal_error(share, HA_ERR_CRASHED);
382 DBUG_PRINT("error",
383 ("Found wrong key: length: %u page: %p end: %p",
384 length, page, end));
385 DBUG_RETURN(MARIA_FOUND_WRONG_KEY);
386 }
387 if ((flag= ha_key_cmp(keyinfo->seg, t_buff, key->data,
388 key->data_length + key->ref_length,
389 comp_flag | tmp_key.flag,
390 not_used)) >= 0)
391 break;
392 DBUG_PRINT("loop_extra",("page:%p key: '%s' flag: %d",
393 page, t_buff, flag));
394 memcpy(buff,t_buff,length);
395 *ret_pos=page;
396 }
397 if (flag == 0)
398 memcpy(buff,t_buff,length); /* Result is first key */
399 *last_key= page == end;
400 DBUG_PRINT("exit",("flag: %d ret_pos: %p", flag, *ret_pos));
401 DBUG_RETURN(flag);
402} /* _ma_seq_search */
403
404
405/**
406 Search for key on key page with string prefix compression
407
408 @notes
409 This is an optimized function compared to calling _ma_get_pack_key()
410 for each key in the buffer
411
412 Same interface as for _ma_seq_search()
413*/
414
415int _ma_prefix_search(const MARIA_KEY *key, const MARIA_PAGE *ma_page,
416 uint32 nextflag, uchar **ret_pos, uchar *buff,
417 my_bool *last_key)
418{
419 /*
420 my_flag is raw comparison result to be changed according to
421 SEARCH_NO_FIND,SEARCH_LAST and HA_REVERSE_SORT flags.
422 flag is the value returned by ha_key_cmp and as treated as final
423 */
424 int flag=0, my_flag=-1;
425 uint nod_flag, UNINIT_VAR(length), len, matched, cmplen, kseg_len;
426 uint page_flag, UNINIT_VAR(prefix_len),suffix_len;
427 int key_len_skip, UNINIT_VAR(seg_len_pack), key_len_left;
428 uchar *end, *vseg, *UNINIT_VAR(saved_vseg), *UNINIT_VAR(saved_from);
429 uchar *page;
430 uchar tt_buff[MARIA_MAX_KEY_BUFF+2], *t_buff=tt_buff+2;
431 uchar *UNINIT_VAR(saved_to);
432 const uchar *kseg;
433 uint saved_length=0, saved_prefix_len=0;
434 uint length_pack;
435 MARIA_KEYDEF *keyinfo= key->keyinfo;
436 MARIA_SHARE *share= keyinfo->share;
437 const uchar *sort_order= keyinfo->seg->charset->sort_order;
438 DBUG_ENTER("_ma_prefix_search");
439
440 t_buff[0]=0; /* Avoid bugs */
441 page_flag= ma_page->flag;
442 nod_flag= ma_page->node;
443 page_flag&= KEYPAGE_FLAG_HAS_TRANSID; /* For faster test in loop */
444 page= ma_page->buff;
445 end= page + ma_page->size;
446 page+= share->keypage_header + nod_flag;
447 *ret_pos= page;
448 kseg= key->data;
449
450 get_key_pack_length(kseg_len, length_pack, kseg);
451 key_len_skip=length_pack+kseg_len;
452 key_len_left=(int) (key->data_length + key->ref_length) - (int) key_len_skip;
453 /* If key_len is 0, then length_pack is 1, then key_len_left is -1. */
454 cmplen= ((key_len_left>=0) ? kseg_len :
455 (key->data_length + key->ref_length - length_pack));
456 DBUG_PRINT("info",("key: '%.*s'",kseg_len,kseg));
457
458 /*
459 Keys are compressed the following way:
460
461 If the max length of first key segment <= 127 bytes the prefix is
462 1 uchar else it's 2 byte
463
464 (prefix) length The high bit is set if this is a prefix for the prev key.
465 [suffix length] Packed length of suffix if the previous was a prefix.
466 (suffix) data Key data bytes (past the common prefix or whole segment).
467 [next-key-seg] Next key segments (([packed length], data), ...)
468 pointer Reference to the data file (last_keyseg->length).
469 */
470
471 matched=0; /* how many char's from prefix were alredy matched */
472 len=0; /* length of previous key unpacked */
473
474 while (page < end)
475 {
476 uint packed= *page & 128;
477 uint key_flag;
478
479 vseg= page;
480 if (keyinfo->seg->length >= 127)
481 {
482 suffix_len=mi_uint2korr(vseg) & 32767;
483 vseg+=2;
484 }
485 else
486 suffix_len= *vseg++ & 127;
487
488 if (packed)
489 {
490 if (suffix_len == 0)
491 {
492 /* == 0x80 or 0x8000, same key, prefix length == old key length. */
493 prefix_len=len;
494 }
495 else
496 {
497 /* > 0x80 or 0x8000, this is prefix lgt, packed suffix lgt follows. */
498 prefix_len=suffix_len;
499 get_key_length(suffix_len,vseg);
500 }
501 }
502 else
503 {
504 /* Not packed. No prefix used from last key. */
505 prefix_len=0;
506 }
507
508 len=prefix_len+suffix_len;
509 seg_len_pack=get_pack_length(len);
510 t_buff=tt_buff+3-seg_len_pack;
511 store_key_length(t_buff,len);
512
513 if (prefix_len > saved_prefix_len)
514 memcpy(t_buff+seg_len_pack+saved_prefix_len,saved_vseg,
515 prefix_len-saved_prefix_len);
516 saved_vseg=vseg;
517 saved_prefix_len=prefix_len;
518
519 DBUG_PRINT("loop",("page: '%.*s%.*s'",prefix_len,t_buff+seg_len_pack,
520 suffix_len,vseg));
521 {
522 /* Calculate length of one key */
523 uchar *from= vseg+suffix_len;
524 HA_KEYSEG *keyseg;
525
526 for (keyseg=keyinfo->seg+1 ; keyseg->type ; keyseg++ )
527 {
528 if (keyseg->flag & HA_NULL_PART)
529 {
530 if (!(*from++))
531 continue;
532 }
533 if (keyseg->flag & (HA_VAR_LENGTH_PART | HA_BLOB_PART | HA_SPACE_PACK))
534 {
535 uint key_part_length;
536 get_key_length(key_part_length,from);
537 from+= key_part_length;
538 }
539 else
540 from+= keyseg->length;
541 }
542 from+= keyseg->length;
543 key_flag=0;
544
545 if (page_flag && key_has_transid(from-1))
546 {
547 from+= transid_packed_length(from);
548 key_flag= SEARCH_PAGE_KEY_HAS_TRANSID;
549 }
550 page= from + nod_flag;
551 length= (uint) (from-vseg);
552 }
553
554 if (page > end)
555 {
556 _ma_set_fatal_error(share, HA_ERR_CRASHED);
557 DBUG_PRINT("error",
558 ("Found wrong key: length: %u page: %p end: %p",
559 length, page, end));
560 DBUG_RETURN(MARIA_FOUND_WRONG_KEY);
561 }
562
563 if (matched >= prefix_len)
564 {
565 /* We have to compare. But we can still skip part of the key */
566 uint left;
567 const uchar *k= kseg+prefix_len;
568
569 /*
570 If prefix_len > cmplen then we are in the end-space comparison
571 phase. Do not try to acces the key any more ==> left= 0.
572 */
573 left= ((len <= cmplen) ? suffix_len :
574 ((prefix_len < cmplen) ? cmplen - prefix_len : 0));
575
576 matched=prefix_len+left;
577
578 if (sort_order)
579 {
580 for (my_flag=0;left;left--)
581 if ((my_flag= (int) sort_order[*vseg++] - (int) sort_order[*k++]))
582 break;
583 }
584 else
585 {
586 for (my_flag=0;left;left--)
587 if ((my_flag= (int) *vseg++ - (int) *k++))
588 break;
589 }
590
591 if (my_flag>0) /* mismatch */
592 break;
593 if (my_flag==0) /* match */
594 {
595 /*
596 ** len cmplen seg_left_len more_segs
597 ** < matched=len; continue search
598 ** > = prefix ? found : (matched=len;
599 * continue search)
600 ** > < - ok, found
601 ** = < - ok, found
602 ** = = - ok, found
603 ** = = + next seg
604 */
605 if (len < cmplen)
606 {
607 if ((keyinfo->seg->type != HA_KEYTYPE_TEXT &&
608 keyinfo->seg->type != HA_KEYTYPE_VARTEXT1 &&
609 keyinfo->seg->type != HA_KEYTYPE_VARTEXT2))
610 my_flag= -1;
611 else
612 {
613 /* We have to compare k and vseg as if they were space extended */
614 const uchar *k_end= k+ (cmplen - len);
615 for ( ; k < k_end && *k == ' '; k++) ;
616 if (k == k_end)
617 goto cmp_rest; /* should never happen */
618 if ((uchar) *k < (uchar) ' ')
619 {
620 my_flag= 1; /* Compared string is smaller */
621 break;
622 }
623 my_flag= -1; /* Continue searching */
624 }
625 }
626 else if (len > cmplen)
627 {
628 uchar *vseg_end;
629 if ((nextflag & SEARCH_PREFIX) && key_len_left == 0)
630 goto fix_flag;
631
632 /* We have to compare k and vseg as if they were space extended */
633 for (vseg_end= vseg + (len-cmplen) ;
634 vseg < vseg_end && *vseg == (uchar) ' ';
635 vseg++, matched++) ;
636 DBUG_ASSERT(vseg < vseg_end);
637
638 if ((uchar) *vseg > (uchar) ' ')
639 {
640 my_flag= 1; /* Compared string is smaller */
641 break;
642 }
643 my_flag= -1; /* Continue searching */
644 }
645 else
646 {
647 cmp_rest:
648 if (key_len_left>0)
649 {
650 uint not_used[2];
651 if ((flag = ha_key_cmp(keyinfo->seg+1,vseg,
652 k, key_len_left, nextflag | key_flag,
653 not_used)) >= 0)
654 break;
655 }
656 else
657 {
658 /*
659 at this line flag==-1 if the following lines were already
660 visited and 0 otherwise, i.e. flag <=0 here always !!!
661 */
662 fix_flag:
663 DBUG_ASSERT(flag <= 0);
664 if (nextflag & (SEARCH_NO_FIND | SEARCH_LAST))
665 flag=(nextflag & (SEARCH_BIGGER | SEARCH_LAST)) ? -1 : 1;
666 if (flag>=0)
667 break;
668 }
669 }
670 }
671 matched-=left;
672 }
673 /* else (matched < prefix_len) ---> do nothing. */
674
675 memcpy(buff,t_buff,saved_length=seg_len_pack+prefix_len);
676 saved_to= buff+saved_length;
677 saved_from= saved_vseg;
678 saved_length=length;
679 *ret_pos=page;
680 }
681 if (my_flag)
682 flag=(keyinfo->seg->flag & HA_REVERSE_SORT) ? -my_flag : my_flag;
683 if (flag == 0)
684 {
685 memcpy(buff,t_buff,saved_length=seg_len_pack+prefix_len);
686 saved_to= buff+saved_length;
687 saved_from= saved_vseg;
688 saved_length=length;
689 }
690 if (saved_length)
691 memcpy(saved_to, saved_from, saved_length);
692
693 *last_key= page == end;
694
695 DBUG_PRINT("exit",("flag: %d ret_pos: %p", flag, *ret_pos));
696 DBUG_RETURN(flag);
697} /* _ma_prefix_search */
698
699
700/* Get pos to a key_block */
701
702my_off_t _ma_kpos(uint nod_flag, const uchar *after_key)
703{
704 after_key-=nod_flag;
705 switch (nod_flag) {
706#if SIZEOF_OFF_T > 4
707 case 7:
708 return mi_uint7korr(after_key)*maria_block_size;
709 case 6:
710 return mi_uint6korr(after_key)*maria_block_size;
711 case 5:
712 return mi_uint5korr(after_key)*maria_block_size;
713#else
714 case 7:
715 after_key++;
716 case 6:
717 after_key++;
718 case 5:
719 after_key++;
720#endif
721 case 4:
722 return ((my_off_t) mi_uint4korr(after_key))*maria_block_size;
723 case 3:
724 return ((my_off_t) mi_uint3korr(after_key))*maria_block_size;
725 case 2:
726 return (my_off_t) (mi_uint2korr(after_key)*maria_block_size);
727 case 1:
728 return (uint) (*after_key)*maria_block_size;
729 case 0: /* At leaf page */
730 default: /* Impossible */
731 return(HA_OFFSET_ERROR);
732 }
733} /* _kpos */
734
735
736/* Save pos to a key_block */
737
738void _ma_kpointer(register MARIA_HA *info, register uchar *buff, my_off_t pos)
739{
740 pos/=maria_block_size;
741 switch (info->s->base.key_reflength) {
742#if SIZEOF_OFF_T > 4
743 case 7: mi_int7store(buff,pos); break;
744 case 6: mi_int6store(buff,pos); break;
745 case 5: mi_int5store(buff,pos); break;
746#else
747 case 7: *buff++=0;
748 /* fall through */
749 case 6: *buff++=0;
750 /* fall through */
751 case 5: *buff++=0;
752 /* fall through */
753#endif
754 case 4: mi_int4store(buff,pos); break;
755 case 3: mi_int3store(buff,pos); break;
756 case 2: mi_int2store(buff,(uint) pos); break;
757 case 1: buff[0]= (uchar) pos; break;
758 default: abort(); /* impossible */
759 }
760} /* _ma_kpointer */
761
762
763/* Calc pos to a data-record from a key */
764
765MARIA_RECORD_POS _ma_row_pos_from_key(const MARIA_KEY *key)
766{
767 my_off_t pos;
768 const uchar *after_key= key->data + key->data_length;
769 MARIA_SHARE *share= key->keyinfo->share;
770 switch (share->rec_reflength) {
771#if SIZEOF_OFF_T > 4
772 case 8: pos= (my_off_t) mi_uint8korr(after_key); break;
773 case 7: pos= (my_off_t) mi_uint7korr(after_key); break;
774 case 6: pos= (my_off_t) mi_uint6korr(after_key); break;
775 case 5: pos= (my_off_t) mi_uint5korr(after_key); break;
776#else
777 case 8: pos= (my_off_t) mi_uint4korr(after_key+4); break;
778 case 7: pos= (my_off_t) mi_uint4korr(after_key+3); break;
779 case 6: pos= (my_off_t) mi_uint4korr(after_key+2); break;
780 case 5: pos= (my_off_t) mi_uint4korr(after_key+1); break;
781#endif
782 case 4: pos= (my_off_t) mi_uint4korr(after_key); break;
783 case 3: pos= (my_off_t) mi_uint3korr(after_key); break;
784 case 2: pos= (my_off_t) mi_uint2korr(after_key); break;
785 case 0: /* NO_RECORD */
786 default:
787 pos=0L; /* Shut compiler up */
788 }
789 return (*share->keypos_to_recpos)(share, pos);
790}
791
792
793/**
794 Get trid from a key
795
796 @param key Maria key read from a page
797
798 @retval 0 If key doesn't have a trid
799 @retval trid
800*/
801
802TrID _ma_trid_from_key(const MARIA_KEY *key)
803{
804 if (!(key->flag & (SEARCH_PAGE_KEY_HAS_TRANSID |
805 SEARCH_USER_KEY_HAS_TRANSID)))
806 return 0;
807 return transid_get_packed(key->keyinfo->share,
808 key->data + key->data_length +
809 key->keyinfo->share->rec_reflength);
810}
811
812
813/* Calc position from a record pointer ( in delete link chain ) */
814
815MARIA_RECORD_POS _ma_rec_pos(MARIA_SHARE *share, uchar *ptr)
816{
817 my_off_t pos;
818 switch (share->rec_reflength) {
819#if SIZEOF_OFF_T > 4
820 case 8:
821 pos= (my_off_t) mi_uint8korr(ptr);
822 if (pos == HA_OFFSET_ERROR)
823 return HA_OFFSET_ERROR; /* end of list */
824 break;
825 case 7:
826 pos= (my_off_t) mi_uint7korr(ptr);
827 if (pos == (((my_off_t) 1) << 56) -1)
828 return HA_OFFSET_ERROR; /* end of list */
829 break;
830 case 6:
831 pos= (my_off_t) mi_uint6korr(ptr);
832 if (pos == (((my_off_t) 1) << 48) -1)
833 return HA_OFFSET_ERROR; /* end of list */
834 break;
835 case 5:
836 pos= (my_off_t) mi_uint5korr(ptr);
837 if (pos == (((my_off_t) 1) << 40) -1)
838 return HA_OFFSET_ERROR; /* end of list */
839 break;
840#else
841 case 8:
842 case 7:
843 case 6:
844 case 5:
845 ptr+= (share->rec_reflength-4);
846 /* fall through */
847#endif
848 case 4:
849 pos= (my_off_t) mi_uint4korr(ptr);
850 if (pos == (my_off_t) (uint32) ~0L)
851 return HA_OFFSET_ERROR;
852 break;
853 case 3:
854 pos= (my_off_t) mi_uint3korr(ptr);
855 if (pos == (my_off_t) (1 << 24) -1)
856 return HA_OFFSET_ERROR;
857 break;
858 case 2:
859 pos= (my_off_t) mi_uint2korr(ptr);
860 if (pos == (my_off_t) (1 << 16) -1)
861 return HA_OFFSET_ERROR;
862 break;
863 default: abort(); /* Impossible */
864 }
865 return (*share->keypos_to_recpos)(share, pos);
866}
867
868
869/* save position to record */
870
871void _ma_dpointer(MARIA_SHARE *share, uchar *buff, my_off_t pos)
872{
873 if (pos != HA_OFFSET_ERROR)
874 pos= (*share->recpos_to_keypos)(share, pos);
875
876 switch (share->rec_reflength) {
877#if SIZEOF_OFF_T > 4
878 case 8: mi_int8store(buff,pos); break;
879 case 7: mi_int7store(buff,pos); break;
880 case 6: mi_int6store(buff,pos); break;
881 case 5: mi_int5store(buff,pos); break;
882#else
883 case 8: *buff++=0;
884 /* fall through */
885 case 7: *buff++=0;
886 /* fall through */
887 case 6: *buff++=0;
888 /* fall through */
889 case 5: *buff++=0;
890 /* fall through */
891#endif
892 case 4: mi_int4store(buff,pos); break;
893 case 3: mi_int3store(buff,pos); break;
894 case 2: mi_int2store(buff,(uint) pos); break;
895 case 0: break; /* For NO_RECORD */
896 default: abort(); /* Impossible */
897 }
898} /* _ma_dpointer */
899
900
901my_off_t _ma_static_keypos_to_recpos(MARIA_SHARE *share, my_off_t pos)
902{
903 return pos * share->base.pack_reclength;
904}
905
906
907my_off_t _ma_static_recpos_to_keypos(MARIA_SHARE *share, my_off_t pos)
908{
909 return pos / share->base.pack_reclength;
910}
911
912my_off_t _ma_transparent_recpos(MARIA_SHARE *share __attribute__((unused)),
913 my_off_t pos)
914{
915 return pos;
916}
917
918my_off_t _ma_transaction_keypos_to_recpos(MARIA_SHARE *share
919 __attribute__((unused)),
920 my_off_t pos)
921{
922 /* We need one bit to store if there is transid's after position */
923 return pos >> 1;
924}
925
926my_off_t _ma_transaction_recpos_to_keypos(MARIA_SHARE *share
927 __attribute__((unused)),
928 my_off_t pos)
929{
930 return pos << 1;
931}
932
933/*
934 @brief Get key from key-block
935
936 @param key Should contain previous key. Will contain new key
937 @param page_flag Flag on page block
938 @param nod_flag Is set to nod length if we on nod
939 @param page Points at previous key; Its advanced to point at next key
940
941 @notes
942 Same as _ma_get_key but used with fixed length keys
943
944 @return
945 @retval key_length + length of data pointer (without nod length)
946 */
947
948uint _ma_get_static_key(MARIA_KEY *key, uint page_flag, uint nod_flag,
949 register uchar **page)
950{
951 register MARIA_KEYDEF *keyinfo= key->keyinfo;
952 uint key_length= keyinfo->keylength;
953
954 key->ref_length= keyinfo->share->rec_reflength;
955 key->data_length= key_length - key->ref_length;
956 key->flag= 0;
957 if (page_flag & KEYPAGE_FLAG_HAS_TRANSID)
958 {
959 uchar *end= *page + keyinfo->keylength;
960 if (key_has_transid(end-1))
961 {
962 uint trans_length= transid_packed_length(end);
963 key->ref_length+= trans_length;
964 key_length+= trans_length;
965 key->flag= SEARCH_PAGE_KEY_HAS_TRANSID;
966 }
967 }
968 key_length+= nod_flag;
969 memcpy(key->data, *page, key_length);
970 *page+= key_length;
971 return key_length - nod_flag;
972} /* _ma_get_static_key */
973
974
975/**
976 Skip over static length key from key-block
977
978 @fn _ma_skip_static_key()
979 @param key Keyinfo and buffer that can be used
980 @param nod_flag If nod: Length of node pointer, else zero.
981 @param key Points at key
982
983 @retval pointer to next key
984*/
985
986uchar *_ma_skip_static_key(MARIA_KEY *key, uint page_flag,
987 uint nod_flag, uchar *page)
988{
989 page+= key->keyinfo->keylength;
990 if ((page_flag & KEYPAGE_FLAG_HAS_TRANSID) && key_has_transid(page-1))
991 page+= transid_packed_length(page);
992 return page+ nod_flag;
993}
994
995
996/*
997 get key which is packed against previous key or key with a NULL column.
998
999 SYNOPSIS
1000 _ma_get_pack_key()
1001 @param int_key Should contain previous key. Will contain new key
1002 @param page_flag page_flag from page
1003 @param nod_flag If nod: Length of node pointer, else zero.
1004 @param page_pos Points at previous key; Its advanced to point at next key
1005
1006 @return
1007 @retval key_length + length of data pointer
1008*/
1009
1010uint _ma_get_pack_key(MARIA_KEY *int_key, uint page_flag,
1011 uint nod_flag, uchar **page_pos)
1012{
1013 reg1 HA_KEYSEG *keyseg;
1014 uchar *page= *page_pos;
1015 uint length;
1016 uchar *key= int_key->data;
1017 MARIA_KEYDEF *keyinfo= int_key->keyinfo;
1018
1019 for (keyseg=keyinfo->seg ; keyseg->type ;keyseg++)
1020 {
1021 if (keyseg->flag & HA_PACK_KEY)
1022 {
1023 /* key with length, packed to previous key */
1024 uchar *start= key;
1025 uint packed= *page & 128,tot_length,rest_length;
1026 if (keyseg->length >= 127)
1027 {
1028 length=mi_uint2korr(page) & 32767;
1029 page+=2;
1030 }
1031 else
1032 length= *page++ & 127;
1033
1034 if (packed)
1035 {
1036 if (length > (uint) keyseg->length)
1037 {
1038 _ma_set_fatal_error(keyinfo->share, HA_ERR_CRASHED);
1039 return 0; /* Error */
1040 }
1041 if (length == 0) /* Same key */
1042 {
1043 if (keyseg->flag & HA_NULL_PART)
1044 *key++=1; /* Can't be NULL */
1045 get_key_length(length,key);
1046 key+= length; /* Same diff_key as prev */
1047 if (length > keyseg->length)
1048 {
1049 DBUG_PRINT("error",
1050 ("Found too long null packed key: %u of %u at %p",
1051 length, keyseg->length, *page_pos));
1052 DBUG_DUMP("key", *page_pos, 16);
1053 _ma_set_fatal_error(keyinfo->share, HA_ERR_CRASHED);
1054 return 0;
1055 }
1056 continue;
1057 }
1058 if (keyseg->flag & HA_NULL_PART)
1059 {
1060 key++; /* Skip null marker*/
1061 start++;
1062 }
1063
1064 get_key_length(rest_length,page);
1065 tot_length=rest_length+length;
1066
1067 /* If the stored length has changed, we must move the key */
1068 if (tot_length >= 255 && *start != 255)
1069 {
1070 /* length prefix changed from a length of one to a length of 3 */
1071 bmove_upp(key+length+3, key+length+1, length);
1072 *key=255;
1073 mi_int2store(key+1,tot_length);
1074 key+=3+length;
1075 }
1076 else if (tot_length < 255 && *start == 255)
1077 {
1078 bmove(key+1,key+3,length);
1079 *key=tot_length;
1080 key+=1+length;
1081 }
1082 else
1083 {
1084 store_key_length_inc(key,tot_length);
1085 key+=length;
1086 }
1087 memcpy(key,page,rest_length);
1088 page+=rest_length;
1089 key+=rest_length;
1090 continue;
1091 }
1092 else
1093 {
1094 /* Key that is not packed against previous key */
1095 if (keyseg->flag & HA_NULL_PART)
1096 {
1097 if (!length--) /* Null part */
1098 {
1099 *key++=0;
1100 continue;
1101 }
1102 *key++=1; /* Not null */
1103 }
1104 }
1105 if (length > (uint) keyseg->length)
1106 {
1107 DBUG_PRINT("error",("Found too long packed key: %u of %u at %p",
1108 length, keyseg->length, *page_pos));
1109 DBUG_DUMP("key", *page_pos, 16);
1110 _ma_set_fatal_error(keyinfo->share, HA_ERR_CRASHED);
1111 return 0; /* Error */
1112 }
1113 store_key_length_inc(key,length);
1114 }
1115 else
1116 {
1117 if (keyseg->flag & HA_NULL_PART)
1118 {
1119 if (!(*key++ = *page++))
1120 continue;
1121 }
1122 if (keyseg->flag &
1123 (HA_VAR_LENGTH_PART | HA_BLOB_PART | HA_SPACE_PACK))
1124 {
1125 uchar *tmp=page;
1126 get_key_length(length,tmp);
1127 length+=(uint) (tmp-page);
1128 }
1129 else
1130 length=keyseg->length;
1131 }
1132 memcpy(key, page,(size_t) length);
1133 key+=length;
1134 page+=length;
1135 }
1136
1137 int_key->data_length= (uint)(key - int_key->data);
1138 int_key->flag= 0;
1139 length= keyseg->length;
1140 if (page_flag & KEYPAGE_FLAG_HAS_TRANSID)
1141 {
1142 uchar *end= page + length;
1143 if (key_has_transid(end-1))
1144 {
1145 length+= transid_packed_length(end);
1146 int_key->flag= SEARCH_PAGE_KEY_HAS_TRANSID;
1147 }
1148 }
1149 int_key->ref_length= length;
1150 length+= nod_flag;
1151 bmove(key, page, length);
1152 *page_pos= page+length;
1153
1154 return (int_key->data_length + int_key->ref_length);
1155} /* _ma_get_pack_key */
1156
1157
1158/**
1159 skip key which is packed against previous key or key with a NULL column.
1160
1161 @fn _ma_skip_pack_key()
1162 @param key Keyinfo and buffer that can be used
1163 @param nod_flag If nod: Length of node pointer, else zero.
1164 @param key Points at key
1165
1166 @note
1167 This is in principle a simpler version of _ma_get_pack_key()
1168
1169 @retval pointer to next key
1170*/
1171
1172uchar *_ma_skip_pack_key(MARIA_KEY *key, uint page_flag,
1173 uint nod_flag, uchar *page)
1174{
1175 reg1 HA_KEYSEG *keyseg;
1176 for (keyseg= key->keyinfo->seg ; keyseg->type ; keyseg++)
1177 {
1178 if (keyseg->flag & HA_PACK_KEY)
1179 {
1180 /* key with length, packed to previous key */
1181 uint packed= *page & 128, length;
1182 if (keyseg->length >= 127)
1183 {
1184 length= mi_uint2korr(page) & 32767;
1185 page+= 2;
1186 }
1187 else
1188 length= *page++ & 127;
1189
1190 if (packed)
1191 {
1192 if (length == 0) /* Same key */
1193 continue;
1194 get_key_length(length,page);
1195 page+= length;
1196 continue;
1197 }
1198 if ((keyseg->flag & HA_NULL_PART) && length)
1199 {
1200 /*
1201 Keys that can have null use length+1 as the length for date as the
1202 number 0 is reserved for keys that have a NULL value
1203 */
1204 length--;
1205 }
1206 page+= length;
1207 }
1208 else
1209 {
1210 if (keyseg->flag & HA_NULL_PART)
1211 if (!*page++)
1212 continue;
1213 if (keyseg->flag & (HA_SPACE_PACK | HA_BLOB_PART | HA_VAR_LENGTH_PART))
1214 {
1215 uint length;
1216 get_key_length(length,page);
1217 page+=length;
1218 }
1219 else
1220 page+= keyseg->length;
1221 }
1222 }
1223 page+= keyseg->length;
1224 if ((page_flag & KEYPAGE_FLAG_HAS_TRANSID) && key_has_transid(page-1))
1225 page+= transid_packed_length(page);
1226 return page + nod_flag;
1227}
1228
1229
1230/* Read key that is packed relatively to previous */
1231
1232uint _ma_get_binary_pack_key(MARIA_KEY *int_key, uint page_flag, uint nod_flag,
1233 register uchar **page_pos)
1234{
1235 reg1 HA_KEYSEG *keyseg;
1236 uchar *page, *page_end, *from, *from_end, *key;
1237 uint length,tmp;
1238 MARIA_KEYDEF *keyinfo= int_key->keyinfo;
1239 DBUG_ENTER("_ma_get_binary_pack_key");
1240
1241 page= *page_pos;
1242 page_end=page + MARIA_MAX_KEY_BUFF + 1;
1243 key= int_key->data;
1244
1245 /*
1246 Keys are compressed the following way:
1247
1248 prefix length Packed length of prefix common with prev key.
1249 (1 or 3 bytes)
1250 for each key segment:
1251 [is null] Null indicator if can be null (1 byte, zero means null)
1252 [length] Packed length if varlength (1 or 3 bytes)
1253 key segment 'length' bytes of key segment value
1254 pointer Reference to the data file (last_keyseg->length).
1255
1256 get_key_length() is a macro. It gets the prefix length from 'page'
1257 and puts it into 'length'. It increments 'page' by 1 or 3, depending
1258 on the packed length of the prefix length.
1259 */
1260 get_key_length(length,page);
1261 if (length)
1262 {
1263 if (length > keyinfo->maxlength)
1264 {
1265 DBUG_PRINT("error",
1266 ("Found too long binary packed key: %u of %u at %p",
1267 length, keyinfo->maxlength, *page_pos));
1268 DBUG_DUMP("key", *page_pos, 16);
1269 _ma_set_fatal_error(keyinfo->share, HA_ERR_CRASHED);
1270 DBUG_RETURN(0); /* Wrong key */
1271 }
1272 /* Key is packed against prev key, take prefix from prev key. */
1273 from= key;
1274 from_end= key + length;
1275 }
1276 else
1277 {
1278 /* Key is not packed against prev key, take all from page buffer. */
1279 from= page;
1280 from_end= page_end;
1281 }
1282
1283 /*
1284 The trouble is that key can be split in two parts:
1285 The first part (prefix) is in from .. from_end - 1.
1286 The second part starts at page.
1287 The split can be at every byte position. So we need to check for
1288 the end of the first part before using every byte.
1289 */
1290 for (keyseg=keyinfo->seg ; keyseg->type ;keyseg++)
1291 {
1292 if (keyseg->flag & HA_NULL_PART)
1293 {
1294 /* If prefix is used up, switch to rest. */
1295 if (from == from_end)
1296 {
1297 from=page;
1298 from_end=page_end;
1299 }
1300 if (!(*key++ = *from++))
1301 continue; /* Null part */
1302 }
1303 if (keyseg->flag & (HA_VAR_LENGTH_PART | HA_BLOB_PART | HA_SPACE_PACK))
1304 {
1305 /* If prefix is used up, switch to rest. */
1306 if (from == from_end) { from=page; from_end=page_end; }
1307 /* Get length of dynamic length key part */
1308 if ((length= (uint) (uchar) (*key++ = *from++)) == 255)
1309 {
1310 /* If prefix is used up, switch to rest. */
1311 if (from == from_end) { from=page; from_end=page_end; }
1312 length= ((uint) (uchar) ((*key++ = *from++))) << 8;
1313 /* If prefix is used up, switch to rest. */
1314 if (from == from_end) { from=page; from_end=page_end; }
1315 length+= (uint) (uchar) ((*key++ = *from++));
1316 }
1317 }
1318 else
1319 length=keyseg->length;
1320
1321 if ((tmp=(uint) (from_end-from)) <= length)
1322 {
1323 key+=tmp; /* Use old key */
1324 length-=tmp;
1325 from=page; from_end=page_end;
1326 }
1327 DBUG_ASSERT((int) length >= 0);
1328 DBUG_PRINT("info",("key: %p from: %p length: %u",
1329 key, from, length));
1330 memmove(key, from, (size_t) length);
1331 key+=length;
1332 from+=length;
1333 }
1334 /*
1335 Last segment (type == 0) contains length of data pointer.
1336 If we have mixed key blocks with data pointer and key block pointer,
1337 we have to copy both.
1338 */
1339 int_key->data_length= (uint)(key - int_key->data);
1340 int_key->ref_length= length= keyseg->length;
1341 int_key->flag= 0;
1342 if ((tmp=(uint) (from_end-from)) <= length)
1343 {
1344 /* Skip over the last common part of the data */
1345 key+= tmp;
1346 length-= tmp;
1347 from= page;
1348 }
1349 else
1350 {
1351 /*
1352 Remaining length is greater than max possible length.
1353 This can happen only if we switched to the new key bytes already.
1354 'page_end' is calculated with MARIA_MAX_KEY_BUFF. So it can be far
1355 behind the real end of the key.
1356 */
1357 if (from_end != page_end)
1358 {
1359 DBUG_PRINT("error",("Error when unpacking key"));
1360 _ma_set_fatal_error(keyinfo->share, HA_ERR_CRASHED);
1361 DBUG_RETURN(0); /* Error */
1362 }
1363 }
1364 if (page_flag & KEYPAGE_FLAG_HAS_TRANSID)
1365 {
1366 uchar *end= from + length;
1367 if (key_has_transid(end-1))
1368 {
1369 uint trans_length= transid_packed_length(end);
1370 length+= trans_length;
1371 int_key->ref_length+= trans_length;
1372 int_key->flag= SEARCH_PAGE_KEY_HAS_TRANSID;
1373 }
1374 }
1375
1376 /* Copy rest of data ptr and, if appropriate, trans_id and node_ptr */
1377 memcpy(key, from, length + nod_flag);
1378 *page_pos= from + length + nod_flag;
1379
1380#ifdef USEFUL_FOR_DEBUGGING
1381 DBUG_DUMP("key", int_key->data,
1382 (uint) (int_key->data_length + int_key->ref_length));
1383#endif
1384 DBUG_RETURN(int_key->data_length + int_key->ref_length);
1385}
1386
1387/**
1388 skip key which is ptefix packed against previous key
1389
1390 @fn _ma_skip_binary_key()
1391 @param key Keyinfo and buffer that can be used
1392 @param nod_flag If nod: Length of node pointer, else zero.
1393 @param key Points at key
1394
1395 @note
1396 We have to copy the key as otherwise we don't know how much left
1397 data there is of the key.
1398
1399 @todo
1400 Implement more efficient version of this. We can ignore to copy any rest
1401 key parts that are not null or not packed. We also don't have to copy
1402 rowid or transid.
1403
1404 @retval pointer to next key
1405*/
1406
1407uchar *_ma_skip_binary_pack_key(MARIA_KEY *key, uint page_flag,
1408 uint nod_flag, uchar *page)
1409{
1410 if (!_ma_get_binary_pack_key(key, page_flag, nod_flag, &page))
1411 return 0;
1412 return page;
1413}
1414
1415
1416/**
1417 @brief Get key at position without knowledge of previous key
1418
1419 @return pointer to next key
1420*/
1421
1422uchar *_ma_get_key(MARIA_KEY *key, MARIA_PAGE *ma_page, uchar *keypos)
1423{
1424 uint page_flag, nod_flag;
1425 MARIA_KEYDEF *keyinfo= key->keyinfo;
1426 uchar *page;
1427 DBUG_ENTER("_ma_get_key");
1428
1429 page= ma_page->buff;
1430 page_flag= ma_page->flag;
1431 nod_flag= ma_page->node;
1432
1433 if (! (keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)) &&
1434 ! (page_flag & KEYPAGE_FLAG_HAS_TRANSID))
1435 {
1436 bmove(key->data, keypos, keyinfo->keylength+nod_flag);
1437 key->ref_length= keyinfo->share->rec_reflength;
1438 key->data_length= keyinfo->keylength - key->ref_length;
1439 key->flag= 0;
1440 DBUG_RETURN(keypos+keyinfo->keylength+nod_flag);
1441 }
1442 else
1443 {
1444 page+= keyinfo->share->keypage_header + nod_flag;
1445 key->data[0]= 0; /* safety */
1446 while (page <= keypos)
1447 {
1448 if (!(*keyinfo->get_key)(key, page_flag, nod_flag, &page))
1449 {
1450 _ma_set_fatal_error(keyinfo->share, HA_ERR_CRASHED);
1451 DBUG_RETURN(0);
1452 }
1453 }
1454 }
1455 DBUG_PRINT("exit",("page: %p length: %u", page,
1456 key->data_length + key->ref_length));
1457 DBUG_RETURN(page);
1458} /* _ma_get_key */
1459
1460
1461/*
1462 @brief Get key at position without knowledge of previous key
1463
1464 @return
1465 @retval 0 ok
1466 @retval 1 error
1467*/
1468
1469static my_bool _ma_get_prev_key(MARIA_KEY *key, MARIA_PAGE *ma_page,
1470 uchar *keypos)
1471{
1472 uint page_flag, nod_flag;
1473 MARIA_KEYDEF *keyinfo= key->keyinfo;
1474 DBUG_ENTER("_ma_get_prev_key");
1475
1476 page_flag= ma_page->flag;
1477 nod_flag= ma_page->node;
1478
1479 if (! (keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)) &&
1480 ! (page_flag & KEYPAGE_FLAG_HAS_TRANSID))
1481 {
1482 bmove(key->data, keypos - keyinfo->keylength - nod_flag,
1483 keyinfo->keylength);
1484 key->ref_length= keyinfo->share->rec_reflength;
1485 key->data_length= keyinfo->keylength - key->ref_length;
1486 key->flag= 0;
1487 DBUG_RETURN(0);
1488 }
1489 else
1490 {
1491 uchar *page;
1492
1493 page= ma_page->buff + keyinfo->share->keypage_header + nod_flag;
1494 key->data[0]= 0; /* safety */
1495 DBUG_ASSERT(page != keypos);
1496 while (page < keypos)
1497 {
1498 if (! (*keyinfo->get_key)(key, page_flag, nod_flag, &page))
1499 {
1500 _ma_set_fatal_error(keyinfo->share, HA_ERR_CRASHED);
1501 DBUG_RETURN(1);
1502 }
1503 }
1504 }
1505 DBUG_RETURN(0);
1506} /* _ma_get_prev_key */
1507
1508
1509/*
1510 @brief Get last key from key-page before 'endpos'
1511
1512 @note
1513 endpos may be either end of buffer or start of a key
1514
1515 @return
1516 @retval pointer to where key starts
1517*/
1518
1519uchar *_ma_get_last_key(MARIA_KEY *key, MARIA_PAGE *ma_page, uchar *endpos)
1520{
1521 uint page_flag,nod_flag;
1522 uchar *lastpos, *page;
1523 MARIA_KEYDEF *keyinfo= key->keyinfo;
1524 DBUG_ENTER("_ma_get_last_key");
1525 DBUG_PRINT("enter",("page: %p endpos: %p", ma_page->buff,
1526 endpos));
1527
1528 page_flag= ma_page->flag;
1529 nod_flag= ma_page->node;
1530 page= ma_page->buff + keyinfo->share->keypage_header + nod_flag;
1531
1532 if (! (keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)) &&
1533 ! (page_flag & KEYPAGE_FLAG_HAS_TRANSID))
1534 {
1535 lastpos= endpos-keyinfo->keylength-nod_flag;
1536 key->ref_length= keyinfo->share->rec_reflength;
1537 key->data_length= keyinfo->keylength - key->ref_length;
1538 key->flag= 0;
1539 if (lastpos >= page)
1540 bmove(key->data, lastpos, keyinfo->keylength + nod_flag);
1541 }
1542 else
1543 {
1544 lastpos= page;
1545 key->data[0]=0; /* safety */
1546 while (page < endpos)
1547 {
1548 lastpos= page;
1549 if (!(*keyinfo->get_key)(key, page_flag, nod_flag, &page))
1550 {
1551 DBUG_PRINT("error",("Couldn't find last key: page: %p",
1552 page));
1553 _ma_set_fatal_error(keyinfo->share, HA_ERR_CRASHED);
1554 DBUG_RETURN(0);
1555 }
1556 }
1557 }
1558 DBUG_PRINT("exit",("lastpos: %p length: %u", lastpos,
1559 key->data_length + key->ref_length));
1560 DBUG_RETURN(lastpos);
1561} /* _ma_get_last_key */
1562
1563
1564/**
1565 Calculate length of unpacked key
1566
1567 @param info Maria handler
1568 @param keyinfo key handler
1569 @param key data for key
1570
1571 @notes
1572 This function is very seldom used. It's mainly used for debugging
1573 or when calculating a key length from a stored key in batch insert.
1574
1575 This function does *NOT* calculate length of transid size!
1576 This function can't be used against a prefix packed key on a page
1577
1578 @return
1579 @retval total length for key
1580*/
1581
1582uint _ma_keylength(MARIA_KEYDEF *keyinfo, const uchar *key)
1583{
1584 reg1 HA_KEYSEG *keyseg;
1585 const uchar *start;
1586
1587 if (! (keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)))
1588 return (keyinfo->keylength);
1589
1590 start= key;
1591 for (keyseg=keyinfo->seg ; keyseg->type ; keyseg++)
1592 {
1593 if (keyseg->flag & HA_NULL_PART)
1594 if (!*key++)
1595 continue;
1596 if (keyseg->flag & (HA_SPACE_PACK | HA_BLOB_PART | HA_VAR_LENGTH_PART))
1597 {
1598 uint length;
1599 get_key_length(length,key);
1600 key+=length;
1601 }
1602 else
1603 key+= keyseg->length;
1604 }
1605 return((uint) (key-start)+keyseg->length);
1606} /* _ma_keylength */
1607
1608
1609/*
1610 Calculate length of part key.
1611
1612 Used in maria_rkey() to find the key found for the key-part that was used.
1613 This is needed in case of multi-byte character sets where we may search
1614 after '0xDF' but find 'ss'
1615*/
1616
1617uint _ma_keylength_part(MARIA_KEYDEF *keyinfo, register const uchar *key,
1618 HA_KEYSEG *end)
1619{
1620 reg1 HA_KEYSEG *keyseg;
1621 const uchar *start= key;
1622
1623 for (keyseg=keyinfo->seg ; keyseg != end ; keyseg++)
1624 {
1625 if (keyseg->flag & HA_NULL_PART)
1626 if (!*key++)
1627 continue;
1628 if (keyseg->flag & (HA_SPACE_PACK | HA_BLOB_PART | HA_VAR_LENGTH_PART))
1629 {
1630 uint length;
1631 get_key_length(length,key);
1632 key+=length;
1633 }
1634 else
1635 key+= keyseg->length;
1636 }
1637 return (uint) (key-start);
1638}
1639
1640
1641/*
1642 Find next/previous record with same key
1643
1644 WARNING
1645 This can't be used when database is touched after last read
1646*/
1647
1648int _ma_search_next(register MARIA_HA *info, MARIA_KEY *key,
1649 uint32 nextflag, my_off_t pos)
1650{
1651 int error;
1652 uchar lastkey[MARIA_MAX_KEY_BUFF];
1653 MARIA_KEYDEF *keyinfo= key->keyinfo;
1654 MARIA_KEY tmp_key;
1655 MARIA_PAGE page;
1656 DBUG_ENTER("_ma_search_next");
1657 DBUG_PRINT("enter",("nextflag: %u lastpos: %lu int_keypos:%p page_changed %d keyread_buff_used: %d",
1658 nextflag, (ulong) info->cur_row.lastpos,
1659 info->int_keypos,
1660 info->page_changed, info->keyread_buff_used));
1661 DBUG_EXECUTE("key", _ma_print_key(DBUG_FILE, key););
1662
1663 /*
1664 Force full read if we are at last key or if we are not on a leaf
1665 and the key tree has changed since we used it last time
1666 Note that even if the key tree has changed since last read, we can use
1667 the last read data from the leaf if we haven't used the buffer for
1668 something else.
1669 */
1670
1671 if (((nextflag & SEARCH_BIGGER) && info->int_keypos >= info->int_maxpos) ||
1672 info->page_changed ||
1673 (info->int_keytree_version != keyinfo->version &&
1674 (info->int_nod_flag || info->keyread_buff_used)))
1675 DBUG_RETURN(_ma_search(info, key, nextflag | SEARCH_SAVE_BUFF,
1676 pos));
1677
1678 if (info->keyread_buff_used)
1679 {
1680 if (_ma_fetch_keypage(&page, info, keyinfo, info->last_search_keypage,
1681 PAGECACHE_LOCK_LEFT_UNLOCKED,
1682 DFLT_INIT_HITS, info->keyread_buff, 0))
1683 DBUG_RETURN(-1);
1684 info->keyread_buff_used=0;
1685 }
1686 else
1687 {
1688 /* Last used buffer is in info->keyread_buff */
1689 /* Todo: Add info->keyread_page to keep track of this */
1690 _ma_page_setup(&page, info, keyinfo, 0, info->keyread_buff);
1691 }
1692
1693 tmp_key.data= lastkey;
1694 tmp_key.keyinfo= keyinfo;
1695
1696 if (nextflag & SEARCH_BIGGER) /* Next key */
1697 {
1698 if (page.node)
1699 {
1700 my_off_t tmp_pos= _ma_kpos(page.node, info->int_keypos);
1701
1702 if ((error= _ma_search(info, key, nextflag | SEARCH_SAVE_BUFF,
1703 tmp_pos)) <=0)
1704 DBUG_RETURN(error);
1705 }
1706 if (keyinfo->flag & (HA_PACK_KEY | HA_BINARY_PACK_KEY) &&
1707 info->last_key.data != key->data)
1708 memcpy(info->last_key.data, key->data,
1709 key->data_length + key->ref_length);
1710 if (!(*keyinfo->get_key)(&info->last_key, page.flag, page.node,
1711 &info->int_keypos))
1712 DBUG_RETURN(-1);
1713 }
1714 else /* Previous key */
1715 {
1716 /* Find start of previous key */
1717 info->int_keypos= _ma_get_last_key(&tmp_key, &page, info->int_keypos);
1718 if (!info->int_keypos)
1719 DBUG_RETURN(-1);
1720 if (info->int_keypos == info->keyread_buff + info->s->keypage_header)
1721 {
1722 /* Previous key was first key, read key before this one */
1723 DBUG_RETURN(_ma_search(info, key, nextflag | SEARCH_SAVE_BUFF,
1724 pos));
1725 }
1726 if (page.node &&
1727 (error= _ma_search(info, key, nextflag | SEARCH_SAVE_BUFF,
1728 _ma_kpos(page.node,info->int_keypos))) <= 0)
1729 DBUG_RETURN(error);
1730
1731 /* QQ: We should be able to optimize away the following call */
1732 if (! _ma_get_last_key(&info->last_key, &page, info->int_keypos))
1733 DBUG_RETURN(-1);
1734 }
1735 info->cur_row.lastpos= _ma_row_pos_from_key(&info->last_key);
1736 info->cur_row.trid= _ma_trid_from_key(&info->last_key);
1737 DBUG_PRINT("exit",("found key at %lu",(ulong) info->cur_row.lastpos));
1738 DBUG_RETURN(0);
1739} /* _ma_search_next */
1740
1741
1742/**
1743 Search after position for the first row in an index
1744
1745 @return
1746 Found row is stored in info->cur_row.lastpos
1747*/
1748
1749int _ma_search_first(MARIA_HA *info, MARIA_KEYDEF *keyinfo,
1750 my_off_t pos)
1751{
1752 uchar *first_pos;
1753 MARIA_PAGE page;
1754 MARIA_SHARE *share= info->s;
1755 DBUG_ENTER("_ma_search_first");
1756
1757 if (pos == HA_OFFSET_ERROR)
1758 {
1759 my_errno=HA_ERR_KEY_NOT_FOUND;
1760 info->cur_row.lastpos= HA_OFFSET_ERROR;
1761 DBUG_RETURN(-1);
1762 }
1763
1764 do
1765 {
1766 if (_ma_fetch_keypage(&page, info, keyinfo, pos,
1767 PAGECACHE_LOCK_LEFT_UNLOCKED,
1768 DFLT_INIT_HITS, info->keyread_buff, 0))
1769 {
1770 info->cur_row.lastpos= HA_OFFSET_ERROR;
1771 DBUG_RETURN(-1);
1772 }
1773 first_pos= page.buff + share->keypage_header + page.node;
1774 } while ((pos= _ma_kpos(page.node, first_pos)) != HA_OFFSET_ERROR);
1775
1776 if (!(*keyinfo->get_key)(&info->last_key, page.flag, page.node, &first_pos))
1777 DBUG_RETURN(-1); /* Crashed */
1778
1779 info->int_keypos= first_pos;
1780 info->int_maxpos= (page.buff + page.size -1);
1781 info->int_nod_flag= page.node;
1782 info->int_keytree_version= keyinfo->version;
1783 info->last_search_keypage= info->last_keypage;
1784 info->page_changed=info->keyread_buff_used=0;
1785 info->cur_row.lastpos= _ma_row_pos_from_key(&info->last_key);
1786 info->cur_row.trid= _ma_trid_from_key(&info->last_key);
1787
1788 DBUG_PRINT("exit",("found key at %lu", (ulong) info->cur_row.lastpos));
1789 DBUG_RETURN(0);
1790} /* _ma_search_first */
1791
1792
1793/**
1794 Search after position for the last row in an index
1795
1796 @return
1797 Found row is stored in info->cur_row.lastpos
1798*/
1799
1800int _ma_search_last(MARIA_HA *info, MARIA_KEYDEF *keyinfo,
1801 my_off_t pos)
1802{
1803 uchar *end_of_page;
1804 MARIA_PAGE page;
1805 DBUG_ENTER("_ma_search_last");
1806
1807 if (pos == HA_OFFSET_ERROR)
1808 {
1809 my_errno=HA_ERR_KEY_NOT_FOUND; /* Didn't find key */
1810 info->cur_row.lastpos= HA_OFFSET_ERROR;
1811 DBUG_RETURN(-1);
1812 }
1813
1814 do
1815 {
1816 if (_ma_fetch_keypage(&page, info, keyinfo, pos,
1817 PAGECACHE_LOCK_LEFT_UNLOCKED,
1818 DFLT_INIT_HITS, info->keyread_buff, 0))
1819 {
1820 info->cur_row.lastpos= HA_OFFSET_ERROR;
1821 DBUG_RETURN(-1);
1822 }
1823 end_of_page= page.buff + page.size;
1824 } while ((pos= _ma_kpos(page.node, end_of_page)) != HA_OFFSET_ERROR);
1825
1826 if (!_ma_get_last_key(&info->last_key, &page, end_of_page))
1827 DBUG_RETURN(-1);
1828 info->cur_row.lastpos= _ma_row_pos_from_key(&info->last_key);
1829 info->cur_row.trid= _ma_trid_from_key(&info->last_key);
1830 info->int_keypos= info->int_maxpos= end_of_page;
1831 info->int_nod_flag= page.node;
1832 info->int_keytree_version= keyinfo->version;
1833 info->last_search_keypage= info->last_keypage;
1834 info->page_changed=info->keyread_buff_used=0;
1835
1836 DBUG_PRINT("exit",("found key at %lu",(ulong) info->cur_row.lastpos));
1837 DBUG_RETURN(0);
1838} /* _ma_search_last */
1839
1840
1841
1842/****************************************************************************
1843**
1844** Functions to store and pack a key in a page
1845**
1846** maria_calc_xx_key_length takes the following arguments:
1847** nod_flag If nod: Length of nod-pointer
1848** next_key Position to pos after the new key in buffer
1849** org_key Key that was before the next key in buffer
1850** prev_key Last key before current key
1851** key Key that will be stored
1852** s_temp Information how next key will be packed
1853****************************************************************************/
1854
1855/* Static length key */
1856
1857int
1858_ma_calc_static_key_length(const MARIA_KEY *key, uint nod_flag,
1859 uchar *next_pos __attribute__((unused)),
1860 uchar *org_key __attribute__((unused)),
1861 uchar *prev_key __attribute__((unused)),
1862 MARIA_KEY_PARAM *s_temp)
1863{
1864 s_temp->key= key->data;
1865 return (int) (s_temp->move_length= key->data_length + key->ref_length +
1866 nod_flag);
1867}
1868
1869/* Variable length key */
1870
1871int
1872_ma_calc_var_key_length(const MARIA_KEY *key, uint nod_flag,
1873 uchar *next_pos __attribute__((unused)),
1874 uchar *org_key __attribute__((unused)),
1875 uchar *prev_key __attribute__((unused)),
1876 MARIA_KEY_PARAM *s_temp)
1877{
1878 s_temp->key= key->data;
1879 return (int) (s_temp->move_length= key->data_length + key->ref_length +
1880 nod_flag);
1881}
1882
1883/**
1884 @brief Calc length needed to store prefixed compressed keys
1885
1886 @info
1887 Variable length first segment which is prefix compressed
1888 (maria_chk reports 'packed + stripped')
1889
1890 Keys are compressed the following way:
1891
1892 If the max length of first key segment <= 127 bytes the prefix is
1893 1 uchar else it's 2 byte
1894
1895 prefix byte(s) The high bit is set if this is a prefix for the prev key
1896 length Packed length if the previous was a prefix byte
1897 [data_length] data bytes ('length' bytes)
1898 next-key-seg Next key segments
1899
1900 If the first segment can have NULL:
1901 If key was packed
1902 data_length is length of rest of key
1903 If key was not packed
1904 The data_length is 0 for NULLS and 1+data_length for not null columns
1905*/
1906
1907int
1908_ma_calc_var_pack_key_length(const MARIA_KEY *int_key, uint nod_flag,
1909 uchar *next_key, uchar *org_key, uchar *prev_key,
1910 MARIA_KEY_PARAM *s_temp)
1911{
1912 reg1 HA_KEYSEG *keyseg;
1913 int length;
1914 uint key_length,ref_length,org_key_length=0,
1915 length_pack,new_key_length,diff_flag,pack_marker;
1916 const uchar *key, *start, *end, *key_end;
1917 const uchar *sort_order;
1918 my_bool same_length;
1919 MARIA_KEYDEF *keyinfo= int_key->keyinfo;
1920
1921 key= int_key->data;
1922 length_pack=s_temp->ref_length=s_temp->n_ref_length=s_temp->n_length=0;
1923 same_length=0; keyseg=keyinfo->seg;
1924 key_length= int_key->data_length + int_key->ref_length + nod_flag;
1925
1926 sort_order=0;
1927 if ((keyinfo->flag & HA_FULLTEXT) &&
1928 ((keyseg->type == HA_KEYTYPE_TEXT) ||
1929 (keyseg->type == HA_KEYTYPE_VARTEXT1) ||
1930 (keyseg->type == HA_KEYTYPE_VARTEXT2)) &&
1931 !use_strnxfrm(keyseg->charset))
1932 sort_order= keyseg->charset->sort_order;
1933
1934 /* diff flag contains how many bytes is needed to pack key */
1935 if (keyseg->length >= 127)
1936 {
1937 diff_flag=2;
1938 pack_marker=32768;
1939 }
1940 else
1941 {
1942 diff_flag= 1;
1943 pack_marker=128;
1944 }
1945 s_temp->pack_marker=pack_marker;
1946
1947 /* Handle the case that the first part have NULL values */
1948 if (keyseg->flag & HA_NULL_PART)
1949 {
1950 if (!*key++)
1951 {
1952 s_temp->key= key;
1953 s_temp->key_length= 0;
1954 s_temp->totlength= key_length-1+diff_flag;
1955 s_temp->next_key_pos= 0; /* No next key */
1956 return (s_temp->move_length= s_temp->totlength);
1957 }
1958 s_temp->store_not_null=1;
1959 key_length--; /* We don't store NULL */
1960 if (prev_key && !*prev_key++)
1961 org_key=prev_key=0; /* Can't pack against prev */
1962 else if (org_key)
1963 org_key++; /* Skip NULL */
1964 }
1965 else
1966 s_temp->store_not_null=0;
1967 s_temp->prev_key= org_key;
1968
1969 /* The key part will start with a packed length */
1970
1971 get_key_pack_length(new_key_length,length_pack,key);
1972 end= key_end= key+ new_key_length;
1973 start= key;
1974
1975 /* Calc how many characters are identical between this and the prev. key */
1976 if (prev_key)
1977 {
1978 get_key_length(org_key_length,prev_key);
1979 s_temp->prev_key=prev_key; /* Pointer at data */
1980 /* Don't use key-pack if length == 0 */
1981 if (new_key_length && new_key_length == org_key_length)
1982 same_length=1;
1983 else if (new_key_length > org_key_length)
1984 end= key + org_key_length;
1985
1986 if (sort_order) /* SerG */
1987 {
1988 while (key < end &&
1989 sort_order[*key] == sort_order[*prev_key])
1990 {
1991 key++; prev_key++;
1992 }
1993 }
1994 else
1995 {
1996 while (key < end && *key == *prev_key)
1997 {
1998 key++; prev_key++;
1999 }
2000 }
2001 }
2002
2003 s_temp->key=key;
2004 s_temp->key_length= (uint) (key_end-key);
2005
2006 if (same_length && key == key_end)
2007 {
2008 /* identical variable length key */
2009 s_temp->ref_length= pack_marker;
2010 length=(int) key_length-(int) (key_end-start)-length_pack;
2011 length+= diff_flag;
2012 if (next_key)
2013 { /* Can't combine with next */
2014 s_temp->n_length= *next_key; /* Needed by _ma_store_key */
2015 next_key=0;
2016 }
2017 }
2018 else
2019 {
2020 if (start != key)
2021 { /* Starts as prev key */
2022 ref_length= (uint) (key-start);
2023 s_temp->ref_length= ref_length + pack_marker;
2024 length= (int) (key_length - ref_length);
2025
2026 length-= length_pack;
2027 length+= diff_flag;
2028 length+= ((new_key_length-ref_length) >= 255) ? 3 : 1;/* Rest_of_key */
2029 }
2030 else
2031 {
2032 s_temp->key_length+=s_temp->store_not_null; /* If null */
2033 length= key_length - length_pack+ diff_flag;
2034 }
2035 }
2036 s_temp->totlength=(uint) length;
2037 s_temp->prev_length=0;
2038 DBUG_PRINT("test",("tot_length: %u length: %d uniq_key_length: %u",
2039 key_length, length, s_temp->key_length));
2040
2041 /* If something after that hasn't length=0, test if we can combine */
2042 if ((s_temp->next_key_pos=next_key))
2043 {
2044 uint packed,n_length;
2045
2046 packed = *next_key & 128;
2047 if (diff_flag == 2)
2048 {
2049 n_length= mi_uint2korr(next_key) & 32767; /* Length of next key */
2050 next_key+=2;
2051 }
2052 else
2053 n_length= *next_key++ & 127;
2054 if (!packed)
2055 n_length-= s_temp->store_not_null;
2056
2057 if (n_length || packed) /* Don't pack 0 length keys */
2058 {
2059 uint next_length_pack, new_ref_length=s_temp->ref_length;
2060
2061 if (packed)
2062 {
2063 /* If first key and next key is packed (only on delete) */
2064 if (!prev_key && org_key)
2065 {
2066 get_key_length(org_key_length,org_key);
2067 key=start;
2068 if (sort_order) /* SerG */
2069 {
2070 while (key < end &&
2071 sort_order[*key] == sort_order[*org_key])
2072 {
2073 key++; org_key++;
2074 }
2075 }
2076 else
2077 {
2078 while (key < end && *key == *org_key)
2079 {
2080 key++; org_key++;
2081 }
2082 }
2083 if ((new_ref_length= (uint) (key - start)))
2084 new_ref_length+=pack_marker;
2085 }
2086
2087 if (!n_length)
2088 {
2089 /*
2090 We put a different key between two identical variable length keys
2091 Extend next key to have same prefix as this key
2092 */
2093 if (new_ref_length) /* prefix of previus key */
2094 { /* make next key longer */
2095 s_temp->part_of_prev_key= new_ref_length;
2096 s_temp->prev_length= org_key_length -
2097 (new_ref_length-pack_marker);
2098 s_temp->n_ref_length= s_temp->part_of_prev_key;
2099 s_temp->n_length= s_temp->prev_length;
2100 n_length= get_pack_length(s_temp->prev_length);
2101 s_temp->prev_key+= (new_ref_length - pack_marker);
2102 length+= s_temp->prev_length + n_length;
2103 }
2104 else
2105 { /* Can't use prev key */
2106 s_temp->part_of_prev_key=0;
2107 s_temp->prev_length= org_key_length;
2108 s_temp->n_ref_length=s_temp->n_length= org_key_length;
2109 length+= org_key_length;
2110 }
2111 return (s_temp->move_length= (int) length);
2112 }
2113
2114 ref_length=n_length;
2115 /* Get information about not packed key suffix */
2116 get_key_pack_length(n_length,next_length_pack,next_key);
2117
2118 /* Test if new keys has fewer characters that match the previous key */
2119 if (!new_ref_length)
2120 { /* Can't use prev key */
2121 s_temp->part_of_prev_key= 0;
2122 s_temp->prev_length= ref_length;
2123 s_temp->n_ref_length= s_temp->n_length= n_length+ref_length;
2124 return s_temp->move_length= ((int) length+ref_length-
2125 next_length_pack);
2126 }
2127 if (ref_length+pack_marker > new_ref_length)
2128 {
2129 uint new_pack_length=new_ref_length-pack_marker;
2130 /* We must copy characters from the original key to the next key */
2131 s_temp->part_of_prev_key= new_ref_length;
2132 s_temp->prev_length= ref_length - new_pack_length;
2133 s_temp->n_ref_length=s_temp->n_length=n_length + s_temp->prev_length;
2134 s_temp->prev_key+= new_pack_length;
2135 length-= (next_length_pack - get_pack_length(s_temp->n_length));
2136 return s_temp->move_length= ((int) length + s_temp->prev_length);
2137 }
2138 }
2139 else
2140 {
2141 /* Next key wasn't a prefix of previous key */
2142 ref_length=0;
2143 next_length_pack=0;
2144 }
2145 DBUG_PRINT("test",("length: %d next_key: %p", length,
2146 next_key));
2147
2148 {
2149 uint tmp_length;
2150 key=(start+=ref_length);
2151 if (key+n_length < key_end) /* Normalize length based */
2152 key_end= key+n_length;
2153 if (sort_order) /* SerG */
2154 {
2155 while (key < key_end &&
2156 sort_order[*key] == sort_order[*next_key])
2157 {
2158 key++; next_key++;
2159 }
2160 }
2161 else
2162 {
2163 while (key < key_end && *key == *next_key)
2164 {
2165 key++; next_key++;
2166 }
2167 }
2168 if (!(tmp_length=(uint) (key-start)))
2169 { /* Key can't be re-packed */
2170 s_temp->next_key_pos=0;
2171 return (s_temp->move_length= length);
2172 }
2173 ref_length+=tmp_length;
2174 n_length-=tmp_length;
2175 length-=tmp_length+next_length_pack; /* We gained these chars */
2176 }
2177 if (n_length == 0 && ref_length == new_key_length)
2178 {
2179 s_temp->n_ref_length=pack_marker; /* Same as prev key */
2180 }
2181 else
2182 {
2183 s_temp->n_ref_length=ref_length | pack_marker;
2184 length+= get_pack_length(n_length);
2185 s_temp->n_length=n_length;
2186 }
2187 }
2188 }
2189 return (s_temp->move_length= length);
2190}
2191
2192
2193/* Length of key which is prefix compressed */
2194
2195int _ma_calc_bin_pack_key_length(const MARIA_KEY *int_key,
2196 uint nod_flag,
2197 uchar *next_key,
2198 uchar *org_key, uchar *prev_key,
2199 MARIA_KEY_PARAM *s_temp)
2200{
2201 uint length,key_length,ref_length;
2202 const uchar *key= int_key->data;
2203
2204 s_temp->totlength= key_length= (int_key->data_length + int_key->ref_length+
2205 nod_flag);
2206#ifdef HAVE_valgrind
2207 s_temp->n_length= s_temp->n_ref_length=0; /* For valgrind */
2208#endif
2209 s_temp->key=key;
2210 s_temp->prev_key=org_key;
2211 if (prev_key) /* If not first key in block */
2212 {
2213 /* pack key against previous key */
2214 /*
2215 As keys may be identical when running a sort in maria_chk, we
2216 have to guard against the case where keys may be identical
2217 */
2218 const uchar *end;
2219 end=key+key_length;
2220 for ( ; *key == *prev_key && key < end; key++,prev_key++) ;
2221 s_temp->ref_length= ref_length=(uint) (key-s_temp->key);
2222 length=key_length - ref_length + get_pack_length(ref_length);
2223 }
2224 else
2225 {
2226 /* No previous key */
2227 s_temp->ref_length=ref_length=0;
2228 length=key_length+1;
2229 }
2230 if ((s_temp->next_key_pos=next_key)) /* If another key after */
2231 {
2232 /* pack key against next key */
2233 uint next_length,next_length_pack;
2234 get_key_pack_length(next_length,next_length_pack,next_key);
2235
2236 /* If first key and next key is packed (only on delete) */
2237 if (!prev_key && org_key && next_length)
2238 {
2239 const uchar *end;
2240 for (key= s_temp->key, end=key+next_length ;
2241 *key == *org_key && key < end;
2242 key++,org_key++) ;
2243 ref_length= (uint) (key - s_temp->key);
2244 }
2245
2246 if (next_length > ref_length)
2247 {
2248 /*
2249 We put a key with different case between two keys with the same prefix
2250 Extend next key to have same prefix as this key
2251 */
2252 s_temp->n_ref_length= ref_length;
2253 s_temp->prev_length= next_length-ref_length;
2254 s_temp->prev_key+= ref_length;
2255 return s_temp->move_length= ((int) (length+ s_temp->prev_length -
2256 next_length_pack +
2257 get_pack_length(ref_length)));
2258 }
2259 /* Check how many characters are identical to next key */
2260 key= s_temp->key+next_length;
2261 s_temp->prev_length= 0;
2262 while (*key++ == *next_key++) ;
2263 if ((ref_length= (uint) (key - s_temp->key)-1) == next_length)
2264 {
2265 s_temp->next_key_pos=0;
2266 return (s_temp->move_length= length); /* Can't pack next key */
2267 }
2268 s_temp->n_ref_length=ref_length;
2269 return s_temp->move_length= (int) (length-(ref_length - next_length) -
2270 next_length_pack +
2271 get_pack_length(ref_length));
2272 }
2273 return (s_temp->move_length= (int) length);
2274}
2275
2276
2277/*
2278** store a key packed with _ma_calc_xxx_key_length in page-buffert
2279*/
2280
2281/* store key without compression */
2282
2283void _ma_store_static_key(MARIA_KEYDEF *keyinfo __attribute__((unused)),
2284 register uchar *key_pos,
2285 register MARIA_KEY_PARAM *s_temp)
2286{
2287 memcpy(key_pos, s_temp->key,(size_t) s_temp->move_length);
2288 s_temp->changed_length= s_temp->move_length;
2289}
2290
2291
2292/* store variable length key with prefix compression */
2293
2294#define store_pack_length(test,pos,length) { \
2295 if (test) { *((pos)++) = (uchar) (length); } else \
2296 { *((pos)++) = (uchar) ((length) >> 8); *((pos)++) = (uchar) (length); } }
2297
2298
2299void _ma_store_var_pack_key(MARIA_KEYDEF *keyinfo __attribute__((unused)),
2300 register uchar *key_pos,
2301 register MARIA_KEY_PARAM *s_temp)
2302{
2303 uint length;
2304 uchar *org_key_pos= key_pos;
2305
2306 if (s_temp->ref_length)
2307 {
2308 /* Packed against previous key */
2309 store_pack_length(s_temp->pack_marker == 128,key_pos,s_temp->ref_length);
2310 /* If not same key after */
2311 if (s_temp->ref_length != s_temp->pack_marker)
2312 store_key_length_inc(key_pos,s_temp->key_length);
2313 }
2314 else
2315 {
2316 /* Not packed against previous key */
2317 store_pack_length(s_temp->pack_marker == 128,key_pos,s_temp->key_length);
2318 }
2319 bmove(key_pos, s_temp->key,
2320 (length= s_temp->totlength - (uint) (key_pos-org_key_pos)));
2321
2322 key_pos+= length;
2323
2324 if (!s_temp->next_key_pos) /* No following key */
2325 goto end;
2326
2327 if (s_temp->prev_length)
2328 {
2329 /* Extend next key because new key didn't have same prefix as prev key */
2330 if (s_temp->part_of_prev_key)
2331 {
2332 store_pack_length(s_temp->pack_marker == 128,key_pos,
2333 s_temp->part_of_prev_key);
2334 store_key_length_inc(key_pos,s_temp->n_length);
2335 }
2336 else
2337 {
2338 s_temp->n_length+= s_temp->store_not_null;
2339 store_pack_length(s_temp->pack_marker == 128,key_pos,
2340 s_temp->n_length);
2341 }
2342 memcpy(key_pos, s_temp->prev_key, s_temp->prev_length);
2343 key_pos+= s_temp->prev_length;
2344 }
2345 else if (s_temp->n_ref_length)
2346 {
2347 store_pack_length(s_temp->pack_marker == 128,key_pos,s_temp->n_ref_length);
2348 if (s_temp->n_ref_length != s_temp->pack_marker)
2349 {
2350 /* Not identical key */
2351 store_key_length_inc(key_pos,s_temp->n_length);
2352 }
2353 }
2354 else
2355 {
2356 s_temp->n_length+= s_temp->store_not_null;
2357 store_pack_length(s_temp->pack_marker == 128,key_pos,s_temp->n_length);
2358 }
2359
2360end:
2361 s_temp->changed_length= (uint) (key_pos - org_key_pos);
2362}
2363
2364
2365/* variable length key with prefix compression */
2366
2367void _ma_store_bin_pack_key(MARIA_KEYDEF *keyinfo __attribute__((unused)),
2368 register uchar *key_pos,
2369 register MARIA_KEY_PARAM *s_temp)
2370{
2371 uchar *org_key_pos= key_pos;
2372 size_t length= s_temp->totlength - s_temp->ref_length;
2373
2374 store_key_length_inc(key_pos,s_temp->ref_length);
2375 memcpy(key_pos, s_temp->key+s_temp->ref_length, length);
2376 key_pos+= length;
2377
2378 if (s_temp->next_key_pos)
2379 {
2380 store_key_length_inc(key_pos,s_temp->n_ref_length);
2381 if (s_temp->prev_length) /* If we must extend key */
2382 {
2383 memcpy(key_pos,s_temp->prev_key,s_temp->prev_length);
2384 key_pos+= s_temp->prev_length;
2385 }
2386 }
2387 s_temp->changed_length= (uint) (key_pos - org_key_pos);
2388}
2389