Drizzled Public API Documentation

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 
23 using namespace drizzled;
24 
25 static bool _mi_get_prev_key(MI_INFO *info, MI_KEYDEF *keyinfo, unsigned char *page,
26  unsigned char *key, unsigned char *keypos,
27  uint32_t *return_key_length);
28 
29  /* Check index */
30 
31 int _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 
60 int _mi_search(register MI_INFO *info, register MI_KEYDEF *keyinfo,
61  unsigned char *key, uint32_t key_len, uint32_t nextflag, register internal::my_off_t pos)
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 
160 err:
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 
172 int _mi_bin_search(MI_INFO *info, register MI_KEYDEF *keyinfo, unsigned char *page,
173  unsigned char *key, uint32_t key_len, uint32_t comp_flag, unsigned char **ret_pos,
174  unsigned char *buff, bool *last_key)
175 {
176  (void)buff;
177  register 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 
233 int _mi_seq_search(MI_INFO *info, register MI_KEYDEF *keyinfo, unsigned char *page,
234  unsigned char *key, uint32_t key_len, uint32_t comp_flag, unsigned char **ret_pos,
235  unsigned char *buff, bool *last_key)
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 
268 int _mi_prefix_search(MI_INFO *info, register MI_KEYDEF *keyinfo, unsigned char *page,
269  unsigned char *key, uint32_t key_len, uint32_t nextflag, unsigned char **ret_pos,
270  unsigned char *buff, bool *last_key)
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 
532 internal::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 
568 void _mi_kpointer(register MI_INFO *info, register 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 
596 internal::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 
626 internal::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 
684 void _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 
723 uint32_t _mi_get_static_key(register MI_KEYDEF *keyinfo, uint32_t nod_flag,
724  register unsigned char **page, register 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 
746 uint32_t _mi_get_pack_key(register MI_KEYDEF *keyinfo, uint32_t nod_flag,
747  register unsigned char **page_pos, register unsigned char *key)
748 {
749  register 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 
876 uint32_t _mi_get_binary_pack_key(register MI_KEYDEF *keyinfo, uint32_t nod_flag,
877  register unsigned char **page_pos, register unsigned char *key)
878 {
879  register 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 
1002 unsigned char *_mi_get_key(MI_INFO *info, MI_KEYDEF *keyinfo, unsigned char *page,
1003  unsigned char *key, unsigned char *keypos, uint32_t *return_key_length)
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 
1035 static bool _mi_get_prev_key(MI_INFO *info, MI_KEYDEF *keyinfo, unsigned char *page,
1036  unsigned char *key, unsigned char *keypos,
1037  uint32_t *return_key_length)
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 
1071 unsigned char *_mi_get_last_key(MI_INFO *info, MI_KEYDEF *keyinfo, unsigned char *page,
1072  unsigned char *lastkey, unsigned char *endpos, uint32_t *return_key_length)
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 
1107 uint32_t _mi_keylength(MI_KEYDEF *keyinfo, register unsigned char *key)
1108 {
1109  register 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 
1142 uint32_t _mi_keylength_part(MI_KEYDEF *keyinfo, register unsigned char *key,
1143  HA_KEYSEG *end)
1144 {
1145  register 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 
1167 unsigned char *_mi_move_key(MI_KEYDEF *keyinfo, unsigned char *to, unsigned char *from)
1168 {
1169  register 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 
1178 int _mi_search_next(register MI_INFO *info, register MI_KEYDEF *keyinfo,
1179  unsigned char *key, uint32_t key_length, uint32_t nextflag, internal::my_off_t pos)
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 
1254 int _mi_search_first(register MI_INFO *info, register MI_KEYDEF *keyinfo,
1255  register 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 
1296 int _mi_search_last(register MI_INFO *info, register MI_KEYDEF *keyinfo,
1297  register 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 
1351 int
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 
1367 int
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 
1400 int
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  register 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 
1675 int
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 
1757 void _mi_store_static_key(MI_KEYDEF *keyinfo,
1758  register unsigned char *key_pos,
1759  register 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 
1773 void _mi_store_var_pack_key(MI_KEYDEF *keyinfo,
1774  register unsigned char *key_pos,
1775  register 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 
1838 void _mi_store_bin_pack_key(MI_KEYDEF *keyinfo,
1839  register unsigned char *key_pos,
1840  register 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.