Adding upstream version 1:10.11.6.upstream/1%10.11.6upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 1918 insertions, 0 deletions

diff --git a/storage/myisam/mi_search.c b/storage/myisam/mi_search.c
new file mode 100644
index 00000000..dbad6aa7
--- /dev/null
+++ b/storage/myisam/mi_search.c
@@ -0,0 +1,1918 @@
+/*
+   Copyright (c) 2000, 2010, Oracle and/or its affiliates
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; version 2 of the License.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1335  USA */
+
+/* key handling functions */
+
+#include "fulltext.h"
+#include "m_ctype.h"
+
+static my_bool _mi_get_prev_key(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *page,
+                                uchar *key, uchar *keypos,
+                                uint *return_key_length);
+
+        /* Check index */
+
+int _mi_check_index(MI_INFO *info, int inx)
+{
+  if (inx == -1)                        /* Use last index */
+    inx=info->lastinx;
+  if (inx < 0)
+  {
+    my_errno= HA_ERR_WRONG_INDEX;
+    return -1;
+  }
+  if (!mi_is_key_active(info->s->state.key_map, inx))
+  {
+    my_errno= info->s->state.state.records ? HA_ERR_WRONG_INDEX :
+                                             HA_ERR_END_OF_FILE;
+    return -1;
+  }
+  if (info->lastinx != inx)             /* Index changed */
+  {
+    info->lastinx = inx;
+    info->page_changed=1;
+    info->update= ((info->update & (HA_STATE_CHANGED | HA_STATE_ROW_CHANGED)) |
+                   HA_STATE_NEXT_FOUND | HA_STATE_PREV_FOUND);
+  }
+  if (info->opt_flag & WRITE_CACHE_USED && flush_io_cache(&info->rec_cache))
+    return(-1);
+  return(inx);
+} /* mi_check_index */
+
+
+        /*
+        ** Search after row by a key
+        ** Position to row is stored in info->lastpos
+        ** Return: -1 if not found
+        **          1 if one should continue search on higher level
+        */
+
+int _mi_search(register MI_INFO *info, register MI_KEYDEF *keyinfo,
+               uchar *key, uint key_len, uint nextflag, register my_off_t pos)
+{
+  my_bool last_key;
+  int error,flag;
+  uint nod_flag;
+  uchar *keypos,*maxpos;
+  uchar lastkey[HA_MAX_KEY_BUFF],*buff;
+  DBUG_ENTER("_mi_search");
+  DBUG_PRINT("enter",("pos: %lu  nextflag: %u  lastpos: %lu",
+                      (ulong) pos, nextflag, (ulong) info->lastpos));
+  DBUG_EXECUTE("key",_mi_print_key(DBUG_FILE,keyinfo->seg,key,key_len););
+
+  if (pos == HA_OFFSET_ERROR)
+  {
+    my_errno=HA_ERR_KEY_NOT_FOUND;                      /* Didn't find key */
+    info->lastpos= HA_OFFSET_ERROR;
+    if (!(nextflag & (SEARCH_SMALLER | SEARCH_BIGGER | SEARCH_LAST)))
+      DBUG_RETURN(-1);                          /* Not found ; return error */
+    DBUG_RETURN(1);                             /* Search at upper levels */
+  }
+
+  if (!(buff=_mi_fetch_keypage(info,keyinfo,pos,DFLT_INIT_HITS,info->buff,
+                               MY_TEST(!(nextflag & SEARCH_SAVE_BUFF)))))
+    goto err;
+  DBUG_DUMP("page", buff, mi_getint(buff));
+
+  flag=(*keyinfo->bin_search)(info,keyinfo,buff,key,key_len,nextflag,
+                              &keypos,lastkey, &last_key);
+  if (flag == MI_FOUND_WRONG_KEY)
+  {
+    my_errno= HA_ERR_CRASHED;
+    goto err;
+  }
+  nod_flag=mi_test_if_nod(buff);
+  maxpos=buff+mi_getint(buff)-1;
+
+  if (flag)
+  {
+    if ((error=_mi_search(info,keyinfo,key,key_len,nextflag,
+                          _mi_kpos(nod_flag,keypos))) <= 0)
+      DBUG_RETURN(error);
+
+    if (flag >0)
+    {
+      if (nextflag & (SEARCH_SMALLER | SEARCH_LAST) &&
+          keypos == buff+2+nod_flag)
+        DBUG_RETURN(1);                                 /* Bigger than key */
+    }
+    else if (nextflag & SEARCH_BIGGER && keypos >= maxpos)
+      DBUG_RETURN(1);                                   /* Smaller than key */
+  }
+  else
+  {
+    if ((nextflag & SEARCH_FIND) && nod_flag &&
+	((keyinfo->flag & (HA_NOSAME | HA_NULL_PART)) != HA_NOSAME ||
+	 key_len != USE_WHOLE_KEY))
+    {
+      if ((error=_mi_search(info,keyinfo,key,key_len,SEARCH_FIND,
+                            _mi_kpos(nod_flag,keypos))) >= 0 ||
+          my_errno != HA_ERR_KEY_NOT_FOUND)
+        DBUG_RETURN(error);
+      info->last_keypage= HA_OFFSET_ERROR;              /* Buffer not in mem */
+    }
+  }
+  if (pos != info->last_keypage)
+  {
+    uchar *old_buff=buff;
+    if (!(buff=_mi_fetch_keypage(info,keyinfo,pos,DFLT_INIT_HITS,info->buff,
+                                 MY_TEST(!(nextflag & SEARCH_SAVE_BUFF)))))
+      goto err;
+    keypos=buff+(keypos-old_buff);
+    maxpos=buff+(maxpos-old_buff);
+  }
+
+  if ((nextflag & (SEARCH_SMALLER | SEARCH_LAST)) && flag != 0)
+  {
+    uint not_used[2];
+    if (_mi_get_prev_key(info,keyinfo, buff, info->lastkey, keypos,
+                         &info->lastkey_length))
+      goto err;
+    if (!(nextflag & SEARCH_SMALLER) &&
+        ha_key_cmp(keyinfo->seg, info->lastkey, key, key_len, SEARCH_FIND,
+                   not_used))
+    {
+      my_errno=HA_ERR_KEY_NOT_FOUND;                    /* Didn't find key */
+      goto err;
+    }
+  }
+  else
+  {
+    info->lastkey_length=(*keyinfo->get_key)(keyinfo,nod_flag,&keypos,lastkey);
+    if (!info->lastkey_length)
+      goto err;
+    memcpy(info->lastkey,lastkey,info->lastkey_length);
+  }
+  info->lastpos=_mi_dpos(info,0,info->lastkey+info->lastkey_length);
+  /* Save position for a possible read next / previous */
+  info->int_keypos=info->buff+ (keypos-buff);
+  info->int_maxpos=info->buff+ (maxpos-buff);
+  info->int_nod_flag=nod_flag;
+  info->int_keytree_version=keyinfo->version;
+  info->last_search_keypage=info->last_keypage;
+  info->page_changed=0;
+  info->buff_used= (info->buff != buff);        /* If we have to reread buff */
+
+  DBUG_PRINT("exit",("found key at %lu",(ulong) info->lastpos));
+  DBUG_RETURN(0);
+
+err:
+  DBUG_PRINT("exit",("Error: %d",my_errno));
+  info->lastpos= HA_OFFSET_ERROR;
+  info->page_changed=1;
+  DBUG_RETURN (-1);
+} /* _mi_search */
+
+
+        /* Search after key in page-block */
+        /* If packed key puts smaller or identical key in buff */
+        /* ret_pos point to where find or bigger key starts */
+        /* ARGSUSED */
+
+int _mi_bin_search(MI_INFO *info, register MI_KEYDEF *keyinfo, uchar *page,
+                   uchar *key, uint key_len, uint comp_flag, uchar **ret_pos,
+                   uchar *buff __attribute__((unused)), my_bool *last_key)
+{
+  reg4 int start,mid,end,save_end;
+  int UNINIT_VAR(flag);
+  uint totlength,nod_flag,not_used[2];
+  DBUG_ENTER("_mi_bin_search");
+
+  totlength=keyinfo->keylength+(nod_flag=mi_test_if_nod(page));
+  start=0; mid=1;
+  save_end=end=(int) ((mi_getint(page)-2-nod_flag)/totlength-1);
+  DBUG_PRINT("test",("mi_getint: %d  end: %d",mi_getint(page),end));
+  page+=2+nod_flag;
+
+  while (start != end)
+  {
+    mid= (start+end)/2;
+    if ((flag=ha_key_cmp(keyinfo->seg,page+(uint) mid*totlength,key,key_len,
+                         comp_flag, not_used))
+        >= 0)
+      end=mid;
+    else
+      start=mid+1;
+  }
+  if (mid != start)
+    flag=ha_key_cmp(keyinfo->seg,page+(uint) start*totlength,key,key_len,
+                     comp_flag, not_used);
+  if (flag < 0)
+    start++;                    /* point at next, bigger key */
+  *ret_pos=page+(uint) start*totlength;
+  *last_key= end == save_end;
+  DBUG_PRINT("exit",("flag: %d  keypos: %d",flag,start));
+  DBUG_RETURN(flag);
+} /* _mi_bin_search */
+
+
+/*
+  Locate a packed key in a key page.
+
+  SYNOPSIS
+    _mi_seq_search()
+    info                        Open table information.
+    keyinfo                     Key definition information.
+    page                        Key page (beginning).
+    key                         Search key.
+    key_len                     Length to use from search key or USE_WHOLE_KEY
+    comp_flag                   Search flags like SEARCH_SAME etc.
+    ret_pos             RETURN  Position in key page behind this key.
+    buff                RETURN  Copy of previous or identical unpacked key.
+    last_key            RETURN  If key is last in page.
+
+  DESCRIPTION
+    Used instead of _mi_bin_search() when key is packed.
+    Puts smaller or identical key in buff.
+    Key is searched sequentially.
+
+  RETURN
+    > 0         Key in 'buff' is smaller than search key.
+    0           Key in 'buff' is identical to search key.
+    < 0         Not found.
+*/
+
+int _mi_seq_search(MI_INFO *info, register MI_KEYDEF *keyinfo, uchar *page,
+                   uchar *key, uint key_len, uint comp_flag, uchar **ret_pos,
+                   uchar *buff, my_bool *last_key)
+{
+  int UNINIT_VAR(flag);
+  uint nod_flag,UNINIT_VAR(length),not_used[2];
+  uchar t_buff[HA_MAX_KEY_BUFF],*end;
+  DBUG_ENTER("_mi_seq_search");
+
+  end= page+mi_getint(page);
+  nod_flag=mi_test_if_nod(page);
+  page+=2+nod_flag;
+  *ret_pos=page;
+  t_buff[0]=0;                                  /* Avoid bugs */
+  while (page < end)
+  {
+    length=(*keyinfo->get_key)(keyinfo,nod_flag,&page,t_buff);
+    if (length == 0 || page > end)
+    {
+      mi_print_error(info->s, HA_ERR_CRASHED);
+      my_errno=HA_ERR_CRASHED;
+      DBUG_PRINT("error",
+                 ("Found wrong key:  length: %u  page: %p  end: %p",
+                  length, page, end));
+      DBUG_RETURN(MI_FOUND_WRONG_KEY);
+    }
+    if ((flag=ha_key_cmp(keyinfo->seg,t_buff,key,key_len,comp_flag,
+                         not_used)) >= 0)
+      break;
+#ifdef EXTRA_DEBUG
+    DBUG_PRINT("loop",("page: 0x%lx  key: '%s'  flag: %d", (long) page, t_buff,
+                       flag));
+#endif
+    memcpy(buff,t_buff,length);
+    *ret_pos=page;
+  }
+  if (flag == 0)
+    memcpy(buff,t_buff,length);                 /* Result is first key */
+  *last_key= page == end;
+  DBUG_PRINT("exit",("flag: %d  ret_pos: %p", flag, *ret_pos));
+  DBUG_RETURN(flag);
+} /* _mi_seq_search */
+
+
+int _mi_prefix_search(MI_INFO *info, register MI_KEYDEF *keyinfo, uchar *page,
+                      uchar *key, uint key_len, uint nextflag, uchar **ret_pos,
+                      uchar *buff, my_bool *last_key)
+{
+  /*
+    my_flag is raw comparison result to be changed according to
+    SEARCH_NO_FIND,SEARCH_LAST and HA_REVERSE_SORT flags.
+    flag is the value returned by ha_key_cmp and as treated as final
+  */
+  int flag=0, my_flag=-1;
+  uint nod_flag, UNINIT_VAR(length), len, matched, cmplen, kseg_len;
+  uint UNINIT_VAR(prefix_len), suffix_len;
+  int key_len_skip, UNINIT_VAR(seg_len_pack), key_len_left;
+  uchar *end, *kseg, *vseg;
+  const uchar *sort_order= keyinfo->seg->charset->sort_order;
+  uchar tt_buff[HA_MAX_KEY_BUFF+2], *t_buff=tt_buff+2;
+  uchar *UNINIT_VAR(saved_from), *UNINIT_VAR(saved_to);
+  uchar *UNINIT_VAR(saved_vseg);
+  uint  saved_length=0, saved_prefix_len=0;
+  uint  length_pack;
+  const int reverse = keyinfo->seg->flag & HA_REVERSE_SORT;
+  DBUG_ENTER("_mi_prefix_search");
+
+  t_buff[0]=0;                                  /* Avoid bugs */
+  end= page+mi_getint(page);
+  nod_flag=mi_test_if_nod(page);
+  page+=2+nod_flag;
+  *ret_pos=page;
+  kseg=key;
+
+  get_key_pack_length(kseg_len,length_pack,kseg);
+  key_len_skip=length_pack+kseg_len;
+  key_len_left=(int) key_len- (int) key_len_skip;
+  /* If key_len is 0, then lenght_pack is 1, then key_len_left is -1. */
+  cmplen=(key_len_left>=0) ? kseg_len : key_len-length_pack;
+  DBUG_PRINT("info",("key: '%.*s'",kseg_len,kseg));
+
+  /*
+    Keys are compressed the following way:
+
+    If the max length of first key segment <= 127 bytes the prefix is
+    1 byte else it's 2 byte
+
+    (prefix) length  The high bit is set if this is a prefix for the prev key.
+    [suffix length]  Packed length of suffix if the previous was a prefix.
+    (suffix) data    Key data bytes (past the common prefix or whole segment).
+    [next-key-seg]   Next key segments (([packed length], data), ...)
+    pointer          Reference to the data file (last_keyseg->length).
+  */
+
+  matched=0;  /* how many char's from prefix were alredy matched */
+  len=0;      /* length of previous key unpacked */
+
+  while (page < end)
+  {
+    uint packed= *page & 128;
+
+    vseg=page;
+    if (keyinfo->seg->length >= 127)
+    {
+      suffix_len=mi_uint2korr(vseg) & 32767;
+      vseg+=2;
+    }
+    else
+      suffix_len= *vseg++ & 127;
+
+    if (packed)
+    {
+      if (suffix_len == 0)
+      {
+        /* == 0x80 or 0x8000, same key, prefix length == old key length. */
+        prefix_len=len;
+      }
+      else
+      {
+        /* > 0x80 or 0x8000, this is prefix lgt, packed suffix lgt follows. */
+        prefix_len=suffix_len;
+        get_key_length(suffix_len,vseg);
+      }
+    }
+    else
+    {
+      /* Not packed. No prefix used from last key. */
+      prefix_len=0;
+    }
+
+    len=prefix_len+suffix_len;
+    seg_len_pack=get_pack_length(len);
+    t_buff=tt_buff+3-seg_len_pack;
+    store_key_length(t_buff,len);
+
+    if (prefix_len > saved_prefix_len)
+      memcpy(t_buff+seg_len_pack+saved_prefix_len,saved_vseg,
+             prefix_len-saved_prefix_len);
+    saved_vseg=vseg;
+    saved_prefix_len=prefix_len;
+
+    DBUG_PRINT("loop",("page: '%.*s%.*s'",prefix_len,t_buff+seg_len_pack,
+		       suffix_len,vseg));
+    {
+      uchar *from=vseg+suffix_len;
+      HA_KEYSEG *keyseg;
+      uint l;
+
+      for (keyseg=keyinfo->seg+1 ; keyseg->type ; keyseg++ )
+      {
+
+        if (keyseg->flag & HA_NULL_PART)
+        {
+          if (!(*from++))
+            continue;
+        }
+        if (keyseg->flag & (HA_VAR_LENGTH_PART | HA_BLOB_PART | HA_SPACE_PACK))
+        {
+          get_key_length(l,from);
+        }
+        else
+          l=keyseg->length;
+
+        from+=l;
+      }
+      from+=keyseg->length;
+      page=from+nod_flag;
+      length= (uint) (from - vseg);
+    }
+
+    if (page > end)
+    {
+      mi_print_error(info->s, HA_ERR_CRASHED);
+      my_errno=HA_ERR_CRASHED;
+      DBUG_PRINT("error",
+                 ("Found wrong key:  length: %u  page: %p  end: %p",
+                  length, page, end));
+      DBUG_RETURN(MI_FOUND_WRONG_KEY);
+    }
+
+    if (matched >= prefix_len)
+    {
+      /* We have to compare. But we can still skip part of the key */
+      uint  left;
+      uchar *k=kseg+prefix_len;
+
+      /*
+        If prefix_len > cmplen then we are in the end-space comparison
+        phase. Do not try to access the key any more ==> left= 0.
+      */
+      left= ((len <= cmplen) ? suffix_len :
+             ((prefix_len < cmplen) ? cmplen - prefix_len : 0));
+
+      matched=prefix_len+left;
+
+      if (sort_order)
+      {
+        for (my_flag=0;left;left--)
+          if ((my_flag= (int) sort_order[*vseg++] - (int) sort_order[*k++]))
+            break;
+      }
+      else
+      {
+        for (my_flag=0;left;left--)
+          if ((my_flag= (int) *vseg++ - (int) *k++))
+            break;
+      }
+
+      if (my_flag==0) /* match */
+      {
+	/*
+        **  len cmplen seg_left_len more_segs
+        **     <                               matched=len; continue search
+        **     >      =                        prefix ? found : (matched=len; continue search)
+        **     >      <                 -      ok, found
+        **     =      <                 -      ok, found
+        **     =      =                 -      ok, found
+        **     =      =                 +      next seg
+        */
+        if (len < cmplen)
+        {
+	  if ((keyinfo->seg->type != HA_KEYTYPE_TEXT &&
+	       keyinfo->seg->type != HA_KEYTYPE_VARTEXT1 &&
+               keyinfo->seg->type != HA_KEYTYPE_VARTEXT2))
+	    my_flag= -1;
+	  else
+	  {
+	    /* We have to compare k and vseg as if they were space extended */
+	    uchar *k_end= k+ (cmplen - len);
+	    for ( ; k < k_end && *k == ' '; k++) ;
+	    if (k == k_end)
+	      goto cmp_rest;		/* should never happen */
+	    my_flag= (uchar)' ' - *k;
+	  }
+        }
+        else if (len > cmplen)
+        {
+	  uchar *vseg_end;
+	  if ((nextflag & SEARCH_PREFIX) && key_len_left == 0)
+	    goto fix_flag;
+
+	  /* We have to compare k and vseg as if they were space extended */
+	  for (vseg_end= vseg + (len-cmplen) ;
+	       vseg < vseg_end && *vseg == (uchar) ' ';
+	       vseg++, matched++) ;
+	  DBUG_ASSERT(vseg < vseg_end);
+
+          my_flag= *vseg - (uchar)' ';
+        }
+        else
+	{
+      cmp_rest:
+	  if (key_len_left>0)
+	  {
+	    uint not_used[2];
+	    if ((flag = ha_key_cmp(keyinfo->seg+1,vseg,
+				   k, key_len_left, nextflag, not_used)) >= 0)
+	      break;
+	  }
+	  else
+	  {
+	    /*
+	      at this line flag==-1 if the following lines were already
+	      visited and 0 otherwise,  i.e. flag <=0 here always !!!
+	    */
+	fix_flag:
+	    DBUG_ASSERT(flag <= 0);
+	    if (nextflag & (SEARCH_NO_FIND | SEARCH_LAST))
+	      flag=(nextflag & (SEARCH_BIGGER | SEARCH_LAST)) ? -1 : 1;
+	    if (flag>=0)
+	      break;
+	  }
+	}
+      }
+      if ((reverse ? -my_flag : my_flag) > 0)      /* mismatch */
+        break;
+      matched-=left;
+    }
+    /* else (matched < prefix_len) ---> do nothing. */
+
+    memcpy(buff,t_buff,saved_length=seg_len_pack+prefix_len);
+    saved_to=buff+saved_length;
+    saved_from=saved_vseg;
+    saved_length=length;
+    *ret_pos=page;
+  }
+  if (my_flag)
+    flag= reverse ? -my_flag : my_flag;
+  if (flag == 0)
+  {
+    memcpy(buff,t_buff,saved_length=seg_len_pack+prefix_len);
+    saved_to=buff+saved_length;
+    saved_from=saved_vseg;
+    saved_length=length;
+  }
+  if (saved_length)
+    memcpy(saved_to,saved_from,saved_length);
+
+  *last_key= page == end;
+
+  DBUG_PRINT("exit",("flag: %d  ret_pos: %p", flag, *ret_pos));
+  DBUG_RETURN(flag);
+} /* _mi_prefix_search */
+
+
+        /* Get pos to a key_block */
+
+my_off_t _mi_kpos(uint nod_flag, uchar *after_key)
+{
+  after_key-=nod_flag;
+  switch (nod_flag) {
+#if SIZEOF_OFF_T > 4
+  case 7:
+    return mi_uint7korr(after_key)*MI_MIN_KEY_BLOCK_LENGTH;
+  case 6:
+    return mi_uint6korr(after_key)*MI_MIN_KEY_BLOCK_LENGTH;
+  case 5:
+    return mi_uint5korr(after_key)*MI_MIN_KEY_BLOCK_LENGTH;
+#else
+  case 7:
+    after_key++;
+  case 6:
+    after_key++;
+  case 5:
+    after_key++;
+#endif
+  case 4:
+    return ((my_off_t) mi_uint4korr(after_key))*MI_MIN_KEY_BLOCK_LENGTH;
+  case 3:
+    return ((my_off_t) mi_uint3korr(after_key))*MI_MIN_KEY_BLOCK_LENGTH;
+  case 2:
+    return (my_off_t) (mi_uint2korr(after_key)*MI_MIN_KEY_BLOCK_LENGTH);
+  case 1:
+    return (uint) (*after_key)*MI_MIN_KEY_BLOCK_LENGTH;
+  case 0:                                       /* At leaf page */
+  default:                                      /* Impossible */
+    return(HA_OFFSET_ERROR);
+  }
+} /* _kpos */
+
+
+        /* Save pos to a key_block */
+
+void _mi_kpointer(register MI_INFO *info, register uchar *buff, my_off_t pos)
+{
+  pos/=MI_MIN_KEY_BLOCK_LENGTH;
+  switch (info->s->base.key_reflength) {
+#if SIZEOF_OFF_T > 4
+  case 7: mi_int7store(buff,pos); break;
+  case 6: mi_int6store(buff,pos); break;
+  case 5: mi_int5store(buff,pos); break;
+#else
+  case 7: *buff++=0;
+    /* fall through */
+  case 6: *buff++=0;
+    /* fall through */
+  case 5: *buff++=0;
+    /* fall through */
+#endif
+  case 4: mi_int4store(buff,pos); break;
+  case 3: mi_int3store(buff,pos); break;
+  case 2: mi_int2store(buff,(uint) pos); break;
+  case 1: buff[0]= (uchar) pos; break;
+  default: abort();                             /* impossible */
+  }
+} /* _mi_kpointer */
+
+
+        /* Calc pos to a data-record from a key */
+
+
+my_off_t _mi_dpos(MI_INFO *info, uint nod_flag, uchar *after_key)
+{
+  my_off_t pos;
+  after_key-=(nod_flag + info->s->rec_reflength);
+  switch (info->s->rec_reflength) {
+#if SIZEOF_OFF_T > 4
+  case 8:  pos= (my_off_t) mi_uint8korr(after_key);  break;
+  case 7:  pos= (my_off_t) mi_uint7korr(after_key);  break;
+  case 6:  pos= (my_off_t) mi_uint6korr(after_key);  break;
+  case 5:  pos= (my_off_t) mi_uint5korr(after_key);  break;
+#else
+  case 8:  pos= (my_off_t) mi_uint4korr(after_key+4);   break;
+  case 7:  pos= (my_off_t) mi_uint4korr(after_key+3);   break;
+  case 6:  pos= (my_off_t) mi_uint4korr(after_key+2);   break;
+  case 5:  pos= (my_off_t) mi_uint4korr(after_key+1);   break;
+#endif
+  case 4:  pos= (my_off_t) mi_uint4korr(after_key);  break;
+  case 3:  pos= (my_off_t) mi_uint3korr(after_key);  break;
+  case 2:  pos= (my_off_t) mi_uint2korr(after_key);  break;
+  default:
+    pos=0L;                                     /* Shut compiler up */
+  }
+  return (info->s->options &
+          (HA_OPTION_PACK_RECORD | HA_OPTION_COMPRESS_RECORD)) ? pos :
+            pos*info->s->base.pack_reclength;
+}
+
+
+/* Calc position from a record pointer ( in delete link chain ) */
+
+my_off_t _mi_rec_pos(MYISAM_SHARE *s, uchar *ptr)
+{
+  my_off_t pos;
+  switch (s->rec_reflength) {
+#if SIZEOF_OFF_T > 4
+  case 8:
+    pos= (my_off_t) mi_uint8korr(ptr);
+    if (pos == HA_OFFSET_ERROR)
+      return HA_OFFSET_ERROR;                   /* end of list */
+    break;
+  case 7:
+    pos= (my_off_t) mi_uint7korr(ptr);
+    if (pos == (((my_off_t) 1) << 56) -1)
+      return HA_OFFSET_ERROR;                   /* end of list */
+    break;
+  case 6:
+    pos= (my_off_t) mi_uint6korr(ptr);
+    if (pos == (((my_off_t) 1) << 48) -1)
+      return HA_OFFSET_ERROR;                   /* end of list */
+    break;
+  case 5:
+    pos= (my_off_t) mi_uint5korr(ptr);
+    if (pos == (((my_off_t) 1) << 40) -1)
+      return HA_OFFSET_ERROR;                   /* end of list */
+    break;
+#else
+  case 8:
+  case 7:
+  case 6:
+  case 5:
+    ptr+= (s->rec_reflength-4);
+    /* fall through */
+#endif
+  case 4:
+    pos= (my_off_t) mi_uint4korr(ptr);
+    if (pos == (my_off_t) (uint32) ~0L)
+      return  HA_OFFSET_ERROR;
+    break;
+  case 3:
+    pos= (my_off_t) mi_uint3korr(ptr);
+    if (pos == (my_off_t) (1 << 24) -1)
+      return HA_OFFSET_ERROR;
+    break;
+  case 2:
+    pos= (my_off_t) mi_uint2korr(ptr);
+    if (pos == (my_off_t) (1 << 16) -1)
+      return HA_OFFSET_ERROR;
+    break;
+  default: abort();                             /* Impossible */
+  }
+  return ((s->options &
+          (HA_OPTION_PACK_RECORD | HA_OPTION_COMPRESS_RECORD)) ? pos :
+          pos*s->base.pack_reclength);
+}
+
+
+        /* save position to record */
+
+void _mi_dpointer(MI_INFO *info, uchar *buff, my_off_t pos)
+{
+  if (!(info->s->options &
+        (HA_OPTION_PACK_RECORD | HA_OPTION_COMPRESS_RECORD)) &&
+      pos != HA_OFFSET_ERROR)
+    pos/=info->s->base.pack_reclength;
+
+  switch (info->s->rec_reflength) {
+#if SIZEOF_OFF_T > 4
+  case 8: mi_int8store(buff,pos); break;
+  case 7: mi_int7store(buff,pos); break;
+  case 6: mi_int6store(buff,pos); break;
+  case 5: mi_int5store(buff,pos); break;
+#else
+  case 8: *buff++=0;
+    /* fall through */
+  case 7: *buff++=0;
+    /* fall through */
+  case 6: *buff++=0;
+    /* fall through */
+  case 5: *buff++=0;
+    /* fall through */
+#endif
+  case 4: mi_int4store(buff,pos); break;
+  case 3: mi_int3store(buff,pos); break;
+  case 2: mi_int2store(buff,(uint) pos); break;
+  default: abort();                             /* Impossible */
+  }
+} /* _mi_dpointer */
+
+
+        /* Get key from key-block */
+        /* page points at previous key; its advanced to point at next key */
+        /* key should contain previous key */
+        /* Returns length of found key + pointers */
+        /* nod_flag is a flag if we are on nod */
+
+        /* same as _mi_get_key but used with fixed length keys */
+
+uint _mi_get_static_key(register MI_KEYDEF *keyinfo, uint nod_flag,
+                       register uchar **page, register uchar *key)
+{
+  memcpy((uchar*) key,(uchar*) *page,
+         (size_t) (keyinfo->keylength+nod_flag));
+  *page+=keyinfo->keylength+nod_flag;
+  return(keyinfo->keylength);
+} /* _mi_get_static_key */
+
+
+/*
+  get key witch is packed against previous key or key with a NULL column.
+
+  SYNOPSIS
+    _mi_get_pack_key()
+    keyinfo                     key definition information.
+    nod_flag                    If nod: Length of node pointer, else zero.
+    page_pos            RETURN  position in key page behind this key.
+    key                 IN/OUT  in: prev key, out: unpacked key.
+
+  RETURN
+    key_length + length of data pointer
+*/
+
+uint _mi_get_pack_key(register MI_KEYDEF *keyinfo, uint nod_flag,
+                      register uchar **page_pos, register uchar *key)
+{
+  reg1 HA_KEYSEG *keyseg;
+  uchar *start_key,*page=*page_pos;
+  uint length;
+
+  start_key=key;
+  for (keyseg=keyinfo->seg ; keyseg->type ;keyseg++)
+  {
+    if (keyseg->flag & HA_PACK_KEY)
+    {
+      /* key with length, packed to previous key */
+      uchar *start=key;
+      uint packed= *page & 128,tot_length,rest_length;
+      if (keyseg->length >= 127)
+      {
+        length=mi_uint2korr(page) & 32767;
+        page+=2;
+      }
+      else
+        length= *page++ & 127;
+
+      if (packed)
+      {
+	if (length > (uint) keyseg->length)
+	{
+          mi_print_error(keyinfo->share, HA_ERR_CRASHED);
+	  my_errno=HA_ERR_CRASHED;
+	  return 0;				/* Error */
+	}
+	if (length == 0)			/* Same key */
+	{
+	  if (keyseg->flag & HA_NULL_PART)
+	    *key++=1;				/* Can't be NULL */
+	  get_key_length(length,key);
+	  key+= length;				/* Same diff_key as prev */
+	  if (length > keyseg->length)
+	  {
+	    DBUG_PRINT("error",
+                       ("Found too long null packed key: %u of %u at %p",
+                        length, keyseg->length, *page_pos));
+	    DBUG_DUMP("key", *page_pos, 16);
+            mi_print_error(keyinfo->share, HA_ERR_CRASHED);
+	    my_errno=HA_ERR_CRASHED;
+	    return 0;
+	  }
+	  continue;
+	}
+	if (keyseg->flag & HA_NULL_PART)
+	{
+	  key++;				/* Skip null marker*/
+	  start++;
+	}
+
+	get_key_length(rest_length,page);
+	tot_length=rest_length+length;
+
+	/* If the stored length has changed, we must move the key */
+	if (tot_length >= 255 && *start != 255)
+	{
+	  /* length prefix changed from a length of one to a length of 3 */
+	  bmove_upp(key+length+3, key+length+1, length);
+	  *key=255;
+	  mi_int2store(key+1,tot_length);
+	  key+=3+length;
+	}
+	else if (tot_length < 255 && *start == 255)
+	{
+	  bmove(key+1,key+3,length);
+	  *key=tot_length;
+	  key+=1+length;
+	}
+	else
+	{
+	  store_key_length_inc(key,tot_length);
+	  key+=length;
+	}
+	memcpy(key,page,rest_length);
+	page+=rest_length;
+	key+=rest_length;
+	continue;
+      }
+      else
+      {
+        if (keyseg->flag & HA_NULL_PART)
+        {
+          if (!length--)                        /* Null part */
+          {
+            *key++=0;
+            continue;
+          }
+          *key++=1;                             /* Not null */
+        }
+      }
+      if (length > (uint) keyseg->length)
+      {
+        DBUG_PRINT("error",("Found too long packed key: %u of %u at %p",
+                            length, keyseg->length, *page_pos));
+        DBUG_DUMP("key", *page_pos, 16);
+        mi_print_error(keyinfo->share, HA_ERR_CRASHED);
+        my_errno=HA_ERR_CRASHED;
+        return 0;                               /* Error */
+      }
+      store_key_length_inc(key,length);
+    }
+    else
+    {
+      if (keyseg->flag & HA_NULL_PART)
+      {
+        if (!(*key++ = *page++))
+          continue;
+      }
+      if (keyseg->flag &
+          (HA_VAR_LENGTH_PART | HA_BLOB_PART | HA_SPACE_PACK))
+      {
+        uchar *tmp=page;
+        get_key_length(length,tmp);
+        length+=(uint) (tmp-page);
+      }
+      else
+        length=keyseg->length;
+    }
+    memcpy((uchar*) key,(uchar*) page,(size_t) length);
+    key+=length;
+    page+=length;
+  }
+  length=keyseg->length+nod_flag;
+  bmove((uchar*) key,(uchar*) page,length);
+  *page_pos= page+length;
+  return ((uint) (key-start_key)+keyseg->length);
+} /* _mi_get_pack_key */
+
+
+
+/* key that is packed relatively to previous */
+
+uint _mi_get_binary_pack_key(register MI_KEYDEF *keyinfo, uint nod_flag,
+                             register uchar **page_pos, register uchar *key)
+{
+  reg1 HA_KEYSEG *keyseg;
+  uchar *start_key,*page,*page_end,*from,*from_end;
+  uint length,tmp;
+  DBUG_ENTER("_mi_get_binary_pack_key");
+
+  page= *page_pos;
+  page_end=page+HA_MAX_KEY_BUFF+1;
+  start_key=key;
+
+  /*
+    Keys are compressed the following way:
+
+    prefix length    Packed length of prefix common with prev key (1 or 3 bytes)
+    for each key segment:
+      [is null]        Null indicator if can be null (1 byte, zero means null)
+      [length]         Packed length if varlength (1 or 3 bytes)
+      key segment      'length' bytes of key segment value
+    pointer          Reference to the data file (last_keyseg->length).
+
+    get_key_length() is a macro. It gets the prefix length from 'page'
+    and puts it into 'length'. It increments 'page' by 1 or 3, depending
+    on the packed length of the prefix length.
+  */
+  get_key_length(length,page);
+  if (length)
+  {
+    if (length > keyinfo->maxlength)
+    {
+      DBUG_PRINT("error",
+                 ("Found too long binary packed key: %u of %u at %p",
+                  length, keyinfo->maxlength, *page_pos));
+      DBUG_DUMP("key", *page_pos, 16);
+      goto crashed;                                  /* Wrong key */
+    }
+    /* Key is packed against prev key, take prefix from prev key. */
+    from= key;
+    from_end= key + length;
+  }
+  else
+  {
+    /* Key is not packed against prev key, take all from page buffer. */
+    from= page;
+    from_end= page_end;
+  }
+
+  /*
+    The trouble is that key can be split in two parts:
+      The first part (prefix) is in from .. from_end - 1.
+      The second part starts at page.
+    The split can be at every byte position. So we need to check for
+    the end of the first part before using every byte.
+  */
+  for (keyseg=keyinfo->seg ; keyseg->type ;keyseg++)
+  {
+    if (keyseg->flag & HA_NULL_PART)
+    {
+      /* If prefix is used up, switch to rest. */
+      if (from == from_end) { from=page;  from_end=page_end; }
+      if (!(*key++ = *from++))
+        continue;                               /* Null part */
+    }
+    if (keyseg->flag & (HA_VAR_LENGTH_PART | HA_BLOB_PART | HA_SPACE_PACK))
+    {
+      /* If prefix is used up, switch to rest. */
+      if (from == from_end) { from=page;  from_end=page_end; }
+      /* Get length of dynamic length key part */
+      if ((length= (*key++ = *from++)) == 255)
+      {
+        /* If prefix is used up, switch to rest. */
+        if (from == from_end) { from=page;  from_end=page_end; }
+        length= (uint) ((*key++ = *from++)) << 8;
+        /* If prefix is used up, switch to rest. */
+        if (from == from_end) { from=page;  from_end=page_end; }
+        length+= (uint) ((*key++ = *from++));
+      }
+      if (length > keyseg->length)
+        goto crashed;
+    }
+    else
+      length=keyseg->length;
+
+    if ((tmp=(uint) (from_end-from)) <= length)
+    {
+      key+=tmp;                                 /* Use old key */
+      length-=tmp;
+      from=page; from_end=page_end;
+    }
+    DBUG_PRINT("info",("key: %p  from: %p  length: %u",
+		       key, from, length));
+    memmove((uchar*) key, (uchar*) from, (size_t) length);
+    key+=length;
+    from+=length;
+  }
+  /*
+    Last segment (type == 0) contains length of data pointer.
+    If we have mixed key blocks with data pointer and key block pointer,
+    we have to copy both.
+  */
+  length=keyseg->length+nod_flag;
+  if ((tmp=(uint) (from_end-from)) <= length)
+  {
+    /* Remaining length is less or equal max possible length. */
+    memcpy(key+tmp,page,length-tmp);            /* Get last part of key */
+    *page_pos= page+length-tmp;
+  }
+  else
+  {
+    /*
+      Remaining length is greater than max possible length.
+      This can happen only if we switched to the new key bytes already.
+      'page_end' is calculated with MI_MAX_KEY_BUFF. So it can be far
+      behind the real end of the key.
+    */
+    if (from_end != page_end)
+    {
+      DBUG_PRINT("error",("Error when unpacking key"));
+      goto crashed;                                 /* Error */
+    }
+    /* Copy data pointer and, if appropriate, key block pointer. */
+    memcpy((uchar*) key,(uchar*) from,(size_t) length);
+    *page_pos= from+length;
+  }
+  DBUG_RETURN((uint) (key-start_key)+keyseg->length);
+
+  crashed:
+    mi_print_error(keyinfo->share, HA_ERR_CRASHED);
+    my_errno= HA_ERR_CRASHED;
+    DBUG_RETURN(0);
+}
+
+
+        /* Get key at position without knowledge of previous key */
+        /* Returns pointer to next key */
+
+uchar *_mi_get_key(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *page,
+                   uchar *key, uchar *keypos, uint *return_key_length)
+{
+  uint nod_flag;
+  DBUG_ENTER("_mi_get_key");
+
+  nod_flag=mi_test_if_nod(page);
+  if (! (keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)))
+  {
+    bmove((uchar*) key,(uchar*) keypos,keyinfo->keylength+nod_flag);
+    DBUG_RETURN(keypos+keyinfo->keylength+nod_flag);
+  }
+  else
+  {
+    page+=2+nod_flag;
+    key[0]=0;                                   /* safety */
+    while (page <= keypos)
+    {
+      *return_key_length=(*keyinfo->get_key)(keyinfo,nod_flag,&page,key);
+      if (*return_key_length == 0)
+      {
+        mi_print_error(info->s, HA_ERR_CRASHED);
+        my_errno=HA_ERR_CRASHED;
+        DBUG_RETURN(0);
+      }
+    }
+  }
+  DBUG_PRINT("exit",("page: %p  length: %u", page,
+                     *return_key_length));
+  DBUG_RETURN(page);
+} /* _mi_get_key */
+
+
+        /* Get key at position without knowledge of previous key */
+        /* Returns 0 if ok */
+
+static my_bool _mi_get_prev_key(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *page,
+                                uchar *key, uchar *keypos,
+                                uint *return_key_length)
+{
+  uint nod_flag;
+  DBUG_ENTER("_mi_get_prev_key");
+
+  nod_flag=mi_test_if_nod(page);
+  if (! (keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)))
+  {
+    *return_key_length=keyinfo->keylength;
+    bmove((uchar*) key,(uchar*) keypos- *return_key_length-nod_flag,
+          *return_key_length);
+    DBUG_RETURN(0);
+  }
+  else
+  {
+    page+=2+nod_flag;
+    key[0]=0;                                   /* safety */
+    while (page < keypos)
+    {
+      *return_key_length=(*keyinfo->get_key)(keyinfo,nod_flag,&page,key);
+      if (*return_key_length == 0)
+      {
+        mi_print_error(info->s, HA_ERR_CRASHED);
+        my_errno=HA_ERR_CRASHED;
+        DBUG_RETURN(1);
+      }
+    }
+  }
+  DBUG_RETURN(0);
+} /* _mi_get_key */
+
+
+
+        /* Get last key from key-page */
+        /* Return pointer to where key starts */
+
+uchar *_mi_get_last_key(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *page,
+                        uchar *lastkey, uchar *endpos, uint *return_key_length)
+{
+  uint nod_flag;
+  uchar *lastpos;
+  DBUG_ENTER("_mi_get_last_key");
+  DBUG_PRINT("enter",("page:%p  endpos: %p", page,
+                      endpos));
+
+  nod_flag=mi_test_if_nod(page);
+  if (! (keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)))
+  {
+    lastpos=endpos-keyinfo->keylength-nod_flag;
+    *return_key_length=keyinfo->keylength;
+    if (lastpos > page)
+      bmove((uchar*) lastkey,(uchar*) lastpos,keyinfo->keylength+nod_flag);
+  }
+  else
+  {
+    lastpos=(page+=2+nod_flag);
+    lastkey[0]=0;
+    while (page < endpos)
+    {
+      lastpos=page;
+      *return_key_length=(*keyinfo->get_key)(keyinfo,nod_flag,&page,lastkey);
+      if (*return_key_length == 0)
+      {
+        DBUG_PRINT("error",("Couldn't find last key:  page: %p",
+                            page));
+        mi_print_error(info->s, HA_ERR_CRASHED);
+        my_errno=HA_ERR_CRASHED;
+        DBUG_RETURN(0);
+      }
+    }
+  }
+  DBUG_PRINT("exit",("lastpos: %p  length: %u", lastpos,
+                     *return_key_length));
+  DBUG_RETURN(lastpos);
+} /* _mi_get_last_key */
+
+
+        /* Calculate length of key */
+
+uint _mi_keylength(MI_KEYDEF *keyinfo, register uchar *key)
+{
+  reg1 HA_KEYSEG *keyseg;
+  uchar *start;
+
+  if (! (keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)))
+    return (keyinfo->keylength);
+
+  start=key;
+  for (keyseg=keyinfo->seg ; keyseg->type ; keyseg++)
+  {
+    if (keyseg->flag & HA_NULL_PART)
+      if (!*key++)
+        continue;
+    if (keyseg->flag & (HA_SPACE_PACK | HA_BLOB_PART | HA_VAR_LENGTH_PART))
+    {
+      uint length;
+      get_key_length(length,key);
+      key+=length;
+    }
+    else
+      key+= keyseg->length;
+  }
+  return((uint) (key-start)+keyseg->length);
+} /* _mi_keylength */
+
+
+/*
+  Calculate length of part key.
+
+  Used in mi_rkey() to find the key found for the key-part that was used.
+  This is needed in case of multi-byte character sets where we may search
+  after '0xDF' but find 'ss'
+*/
+
+uint _mi_keylength_part(MI_KEYDEF *keyinfo, register uchar *key,
+			HA_KEYSEG *end)
+{
+  reg1 HA_KEYSEG *keyseg;
+  uchar *start= key;
+
+  for (keyseg=keyinfo->seg ; keyseg != end ; keyseg++)
+  {
+    if (keyseg->flag & HA_NULL_PART)
+      if (!*key++)
+        continue;
+    if (keyseg->flag & (HA_SPACE_PACK | HA_BLOB_PART | HA_VAR_LENGTH_PART))
+    {
+      uint length;
+      get_key_length(length,key);
+      key+=length;
+    }
+    else
+      key+= keyseg->length;
+  }
+  return (uint) (key-start);
+}
+
+        /* Move a key */
+
+uchar *_mi_move_key(MI_KEYDEF *keyinfo, uchar *to, uchar *from)
+{
+  reg1 uint length;
+  memcpy((uchar*) to, (uchar*) from,
+         (size_t) (length=_mi_keylength(keyinfo,from)));
+  return to+length;
+}
+
+        /* Find next/previous record with same key */
+        /* This can't be used when database is touched after last read */
+
+int _mi_search_next(register MI_INFO *info, register MI_KEYDEF *keyinfo,
+                    uchar *key, uint key_length, uint nextflag, my_off_t pos)
+{
+  int error;
+  uint nod_flag;
+  uchar lastkey[HA_MAX_KEY_BUFF];
+  DBUG_ENTER("_mi_search_next");
+  DBUG_PRINT("enter",("nextflag: %u  lastpos: %llu  int_keypos: %p",
+                      nextflag, info->lastpos,
+                      info->int_keypos));
+  DBUG_EXECUTE("key",_mi_print_key(DBUG_FILE,keyinfo->seg,key,key_length););
+
+  /* Force full read if we are at last key or if we are not on a leaf
+     and the key tree has changed since we used it last time
+     Note that even if the key tree has changed since last read, we can use
+     the last read data from the leaf if we haven't used the buffer for
+     something else.
+  */
+
+  if (((nextflag & SEARCH_BIGGER) && info->int_keypos >= info->int_maxpos) ||
+      info->page_changed ||
+      (info->int_keytree_version != keyinfo->version &&
+       (info->int_nod_flag || info->buff_used)))
+    DBUG_RETURN(_mi_search(info,keyinfo,key, USE_WHOLE_KEY,
+                           nextflag | SEARCH_SAVE_BUFF, pos));
+
+  if (info->buff_used)
+  {
+    if (!_mi_fetch_keypage(info,keyinfo,info->last_search_keypage,
+                           DFLT_INIT_HITS,info->buff,0))
+      DBUG_RETURN(-1);
+    info->buff_used=0;
+  }
+
+  /* Last used buffer is in info->buff */
+  nod_flag=mi_test_if_nod(info->buff);
+
+  if (nextflag & SEARCH_BIGGER)                                 /* Next key */
+  {
+    my_off_t tmp_pos=_mi_kpos(nod_flag,info->int_keypos);
+    if (tmp_pos != HA_OFFSET_ERROR)
+    {
+      if ((error=_mi_search(info,keyinfo,key, USE_WHOLE_KEY,
+                            nextflag | SEARCH_SAVE_BUFF, tmp_pos)) <=0)
+        DBUG_RETURN(error);
+    }
+    memcpy(lastkey,key,key_length);
+    if (!(info->lastkey_length=(*keyinfo->get_key)(keyinfo,nod_flag,
+                                                   &info->int_keypos,lastkey)))
+      DBUG_RETURN(-1);
+  }
+  else                                                  /* Previous key */
+  {
+    uint length;
+    /* Find start of previous key */
+    info->int_keypos=_mi_get_last_key(info,keyinfo,info->buff,lastkey,
+                                      info->int_keypos, &length);
+    if (!info->int_keypos)
+      DBUG_RETURN(-1);
+    if (info->int_keypos == info->buff+2)
+      DBUG_RETURN(_mi_search(info,keyinfo,key, USE_WHOLE_KEY,
+                             nextflag | SEARCH_SAVE_BUFF, pos));
+    if ((error=_mi_search(info,keyinfo,key, USE_WHOLE_KEY,
+			  nextflag | SEARCH_SAVE_BUFF,
+                          _mi_kpos(nod_flag,info->int_keypos))) <= 0)
+      DBUG_RETURN(error);
+
+    /* QQ: We should be able to optimize away the following call */
+    if (! _mi_get_last_key(info,keyinfo,info->buff,lastkey,
+                           info->int_keypos,&info->lastkey_length))
+      DBUG_RETURN(-1);
+  }
+  memcpy(info->lastkey,lastkey,info->lastkey_length);
+  info->lastpos=_mi_dpos(info,0,info->lastkey+info->lastkey_length);
+  DBUG_PRINT("exit",("found key at %lu",(ulong) info->lastpos));
+  DBUG_RETURN(0);
+} /* _mi_search_next */
+
+
+        /* Search after position for the first row in an index */
+        /* This is stored in info->lastpos */
+
+int _mi_search_first(register MI_INFO *info, register MI_KEYDEF *keyinfo,
+                     register my_off_t pos)
+{
+  uint nod_flag;
+  uchar *page;
+  DBUG_ENTER("_mi_search_first");
+
+  if (pos == HA_OFFSET_ERROR)
+  {
+    my_errno=HA_ERR_KEY_NOT_FOUND;
+    info->lastpos= HA_OFFSET_ERROR;
+    DBUG_RETURN(-1);
+  }
+
+  do
+  {
+    if (!_mi_fetch_keypage(info,keyinfo,pos,DFLT_INIT_HITS,info->buff,0))
+    {
+      info->lastpos= HA_OFFSET_ERROR;
+      DBUG_RETURN(-1);
+    }
+    nod_flag=mi_test_if_nod(info->buff);
+    page=info->buff+2+nod_flag;
+  } while ((pos=_mi_kpos(nod_flag,page)) != HA_OFFSET_ERROR);
+
+  if (!(info->lastkey_length=(*keyinfo->get_key)(keyinfo,nod_flag,&page,
+                                                 info->lastkey)))
+    DBUG_RETURN(-1);                            /* Crashed */
+
+  info->int_keypos=page; info->int_maxpos=info->buff+mi_getint(info->buff)-1;
+  info->int_nod_flag=nod_flag;
+  info->int_keytree_version=keyinfo->version;
+  info->last_search_keypage=info->last_keypage;
+  info->page_changed=info->buff_used=0;
+  info->lastpos=_mi_dpos(info,0,info->lastkey+info->lastkey_length);
+
+  DBUG_PRINT("exit",("found key at %lu", (ulong) info->lastpos));
+  DBUG_RETURN(0);
+} /* _mi_search_first */
+
+
+        /* Search after position for the last row in an index */
+        /* This is stored in info->lastpos */
+
+int _mi_search_last(register MI_INFO *info, register MI_KEYDEF *keyinfo,
+                    register my_off_t pos)
+{
+  uint nod_flag;
+  uchar *buff,*page;
+  DBUG_ENTER("_mi_search_last");
+
+  if (pos == HA_OFFSET_ERROR)
+  {
+    my_errno=HA_ERR_KEY_NOT_FOUND;                      /* Didn't find key */
+    info->lastpos= HA_OFFSET_ERROR;
+    DBUG_RETURN(-1);
+  }
+
+  buff=info->buff;
+  do
+  {
+    if (!_mi_fetch_keypage(info,keyinfo,pos,DFLT_INIT_HITS,buff,0))
+    {
+      info->lastpos= HA_OFFSET_ERROR;
+      DBUG_RETURN(-1);
+    }
+    page= buff+mi_getint(buff);
+    nod_flag=mi_test_if_nod(buff);
+  } while ((pos=_mi_kpos(nod_flag,page)) != HA_OFFSET_ERROR);
+
+  if (!_mi_get_last_key(info,keyinfo,buff,info->lastkey,page,
+                        &info->lastkey_length))
+    DBUG_RETURN(-1);
+  info->lastpos=_mi_dpos(info,0,info->lastkey+info->lastkey_length);
+  info->int_keypos=info->int_maxpos=page;
+  info->int_nod_flag=nod_flag;
+  info->int_keytree_version=keyinfo->version;
+  info->last_search_keypage=info->last_keypage;
+  info->page_changed=info->buff_used=0;
+
+  DBUG_PRINT("exit",("found key at %lu",(ulong) info->lastpos));
+  DBUG_RETURN(0);
+} /* _mi_search_last */
+
+
+
+/****************************************************************************
+**
+** Functions to store and pack a key in a page
+**
+** mi_calc_xx_key_length takes the following arguments:
+**  nod_flag    If nod: Length of nod-pointer
+**  next_key    Position to pos after the new key in buffer
+**  org_key     Key that was before the next key in buffer
+**  prev_key    Last key before current key
+**  key         Key that will be stored
+**  s_temp      Information how next key will be packed
+****************************************************************************/
+
+/* Static length key */
+
+int
+_mi_calc_static_key_length(MI_KEYDEF *keyinfo,uint nod_flag,
+                           uchar *next_pos  __attribute__((unused)),
+                           uchar *org_key  __attribute__((unused)),
+                           uchar *prev_key __attribute__((unused)),
+                           uchar *key, MI_KEY_PARAM *s_temp)
+{
+  s_temp->key=key;
+  return (int) (s_temp->totlength=keyinfo->keylength+nod_flag);
+}
+
+/* Variable length key */
+
+int
+_mi_calc_var_key_length(MI_KEYDEF *keyinfo,uint nod_flag,
+                        uchar *next_pos  __attribute__((unused)),
+                        uchar *org_key  __attribute__((unused)),
+                        uchar *prev_key __attribute__((unused)),
+                        uchar *key, MI_KEY_PARAM *s_temp)
+{
+  s_temp->key=key;
+  return (int) (s_temp->totlength=_mi_keylength(keyinfo,key)+nod_flag);
+}
+
+/*
+  length of key with a variable length first segment which is prefix
+  compressed (myisamchk reports 'packed + stripped')
+
+  Keys are compressed the following way:
+
+  If the max length of first key segment <= 127 bytes the prefix is
+  1 byte else it's 2 byte
+
+  prefix byte(s) The high bit is set if this is a prefix for the prev key
+  length         Packed length if the previous was a prefix byte
+  [length]       data bytes ('length' bytes)
+  next-key-seg   Next key segments
+
+  If the first segment can have NULL:
+  The length is 0 for NULLS and 1+length for not null columns.
+
+*/
+
+int
+_mi_calc_var_pack_key_length(MI_KEYDEF *keyinfo,uint nod_flag,uchar *next_key,
+                             uchar *org_key, uchar *prev_key, uchar *key,
+                             MI_KEY_PARAM *s_temp)
+{
+  reg1 HA_KEYSEG *keyseg;
+  int length;
+  uint key_length,ref_length,org_key_length=0,
+       length_pack,new_key_length,diff_flag,pack_marker;
+  uchar *start,*end,*key_end;
+  const uchar *sort_order;
+  my_bool same_length;
+
+  length_pack=s_temp->ref_length=s_temp->n_ref_length=s_temp->n_length=0;
+  same_length=0; keyseg=keyinfo->seg;
+  key_length=_mi_keylength(keyinfo,key)+nod_flag;
+
+  sort_order=0;
+  if ((keyinfo->flag & HA_FULLTEXT) &&
+      ((keyseg->type == HA_KEYTYPE_TEXT) ||
+       (keyseg->type == HA_KEYTYPE_VARTEXT1) ||
+       (keyseg->type == HA_KEYTYPE_VARTEXT2)) &&
+      !use_strnxfrm(keyseg->charset))
+    sort_order=keyseg->charset->sort_order;
+
+  /* diff flag contains how many bytes is needed to pack key */
+  if (keyseg->length >= 127)
+  {
+    diff_flag=2;
+    pack_marker=32768;
+  }
+  else
+  {
+    diff_flag= 1;
+    pack_marker=128;
+  }
+  s_temp->pack_marker=pack_marker;
+
+  /* Handle the case that the first part have NULL values */
+  if (keyseg->flag & HA_NULL_PART)
+  {
+    if (!*key++)
+    {
+      s_temp->key=key;
+      s_temp->key_length= 0;
+      s_temp->totlength=key_length-1+diff_flag;
+      s_temp->next_key_pos=0;                   /* No next key */
+      return (s_temp->totlength);
+    }
+    s_temp->store_not_null=1;
+    key_length--;                               /* We don't store NULL */
+    if (prev_key && !*prev_key++)
+      org_key=prev_key=0;                       /* Can't pack against prev */
+    else if (org_key)
+      org_key++;                                /* Skip NULL */
+  }
+  else
+    s_temp->store_not_null=0;
+  s_temp->prev_key=org_key;
+
+  /* The key part will start with a packed length */
+
+  get_key_pack_length(new_key_length,length_pack,key);
+  end=key_end= key+ new_key_length;
+  start=key;
+
+  /* Calc how many characters are identical between this and the prev. key */
+  if (prev_key)
+  {
+    get_key_length(org_key_length,prev_key);
+    s_temp->prev_key=prev_key;          /* Pointer at data */
+    /* Don't use key-pack if length == 0 */
+    if (new_key_length && new_key_length == org_key_length)
+      same_length=1;
+    else if (new_key_length > org_key_length)
+      end=key + org_key_length;
+
+    if (sort_order)                             /* SerG */
+    {
+      while (key < end && sort_order[*key] == sort_order[*prev_key])
+      {
+        key++; prev_key++;
+      }
+    }
+    else
+    {
+      while (key < end && *key == *prev_key)
+      {
+        key++; prev_key++;
+      }
+    }
+  }
+
+  s_temp->key=key;
+  s_temp->key_length= (uint) (key_end-key);
+
+  if (same_length && key == key_end)
+  {
+    /* identical variable length key */
+    s_temp->ref_length= pack_marker;
+    length=(int) key_length-(int) (key_end-start)-length_pack;
+    length+= diff_flag;
+    if (next_key)
+    {                                           /* Can't combine with next */
+      s_temp->n_length= *next_key;              /* Needed by _mi_store_key */
+      next_key=0;
+    }
+  }
+  else
+  {
+    if (start != key)
+    {                                           /* Starts as prev key */
+      ref_length= (uint) (key-start);
+      s_temp->ref_length= ref_length + pack_marker;
+      length= (int) (key_length - ref_length);
+
+      length-= length_pack;
+      length+= diff_flag;
+      length+= ((new_key_length-ref_length) >= 255) ? 3 : 1;/* Rest_of_key */
+    }
+    else
+    {
+      s_temp->key_length+=s_temp->store_not_null;       /* If null */
+      length= key_length - length_pack+ diff_flag;
+    }
+  }
+  s_temp->totlength=(uint) length;
+  s_temp->prev_length=0;
+  DBUG_PRINT("test",("tot_length: %u  length: %d  uniq_key_length: %u",
+                     key_length, length, s_temp->key_length));
+
+        /* If something after that hasn't length=0, test if we can combine */
+  if ((s_temp->next_key_pos=next_key))
+  {
+    uint packed,n_length;
+
+    packed = *next_key & 128;
+    if (diff_flag == 2)
+    {
+      n_length= mi_uint2korr(next_key) & 32767; /* Length of next key */
+      next_key+=2;
+    }
+    else
+      n_length= *next_key++ & 127;
+    if (!packed && n_length)
+      n_length-= s_temp->store_not_null;
+
+    if (n_length || packed)             /* Don't pack 0 length keys */
+    {
+      uint next_length_pack, new_ref_length=s_temp->ref_length;
+
+      if (packed)
+      {
+        /* If first key and next key is packed (only on delete) */
+        if (!prev_key && org_key)
+        {
+          get_key_length(org_key_length,org_key);
+          key=start;
+          if (sort_order)                       /* SerG */
+          {
+            while (key < end && sort_order[*key] == sort_order[*org_key])
+            {
+              key++; org_key++;
+            }
+          }
+          else
+          {
+            while (key < end && *key == *org_key)
+            {
+              key++; org_key++;
+            }
+          }
+          if ((new_ref_length= (uint) (key - start)))
+            new_ref_length+=pack_marker;
+        }
+
+        if (!n_length)
+        {
+          /*
+            We put a different key between two identical variable length keys
+            Extend next key to have same prefix as this key
+          */
+          if (new_ref_length)                   /* prefix of previus key */
+          {                                     /* make next key longer */
+            s_temp->part_of_prev_key= new_ref_length;
+            s_temp->prev_length=          org_key_length -
+              (new_ref_length-pack_marker);
+            s_temp->n_ref_length= s_temp->part_of_prev_key;
+            s_temp->n_length= s_temp->prev_length;
+            n_length=             get_pack_length(s_temp->prev_length);
+            s_temp->prev_key+=    (new_ref_length - pack_marker);
+            length+=              s_temp->prev_length + n_length;
+          }
+          else
+          {                                     /* Can't use prev key */
+            s_temp->part_of_prev_key=0;
+            s_temp->prev_length= org_key_length;
+            s_temp->n_ref_length=s_temp->n_length=  org_key_length;
+            length+=           org_key_length;
+          }
+          return (int) length;
+        }
+
+        ref_length=n_length;
+        /* Get information about not packed key suffix */
+        get_key_pack_length(n_length,next_length_pack,next_key);
+
+        /* Test if new keys has fewer characters that match the previous key */
+        if (!new_ref_length)
+        {                                       /* Can't use prev key */
+          s_temp->part_of_prev_key=     0;
+          s_temp->prev_length=          ref_length;
+          s_temp->n_ref_length= s_temp->n_length= n_length+ref_length;
+          return (int) length+ref_length-next_length_pack;
+        }
+        if (ref_length+pack_marker > new_ref_length)
+        {
+          uint new_pack_length=new_ref_length-pack_marker;
+          /* We must copy characters from the original key to the next key */
+          s_temp->part_of_prev_key= new_ref_length;
+          s_temp->prev_length=      ref_length - new_pack_length;
+          s_temp->n_ref_length=s_temp->n_length=n_length + s_temp->prev_length;
+          s_temp->prev_key+=        new_pack_length;
+          length-= (next_length_pack - get_pack_length(s_temp->n_length));
+          return (int) length + s_temp->prev_length;
+        }
+      }
+      else
+      {
+        /* Next key wasn't a prefix of previous key */
+        ref_length=0;
+        next_length_pack=0;
+      }
+      DBUG_PRINT("test",("length: %d  next_key: %p", length,
+                         next_key));
+
+      {
+        uint tmp_length;
+        key=(start+=ref_length);
+        if (key+n_length < key_end)             /* Normalize length based */
+          key_end=key+n_length;
+        if (sort_order)                         /* SerG */
+        {
+          while (key < key_end && sort_order[*key] ==
+                 sort_order[*next_key])
+          {
+            key++; next_key++;
+          }
+        }
+        else
+        {
+          while (key < key_end && *key == *next_key)
+          {
+            key++; next_key++;
+          }
+        }
+        if (!(tmp_length=(uint) (key-start)))
+        {                                       /* Key can't be re-packed */
+          s_temp->next_key_pos=0;
+          return length;
+        }
+        ref_length+=tmp_length;
+        n_length-=tmp_length;
+        length-=tmp_length+next_length_pack;    /* We gained these chars */
+      }
+      if (n_length == 0 && ref_length == new_key_length)
+      {
+        s_temp->n_ref_length=pack_marker;       /* Same as prev key */
+      }
+      else
+      {
+        s_temp->n_ref_length=ref_length | pack_marker;
+        length+= get_pack_length(n_length);
+        s_temp->n_length=n_length;
+      }
+    }
+  }
+  return length;
+}
+
+
+/* Length of key which is prefix compressed */
+
+int
+_mi_calc_bin_pack_key_length(MI_KEYDEF *keyinfo,uint nod_flag,uchar *next_key,
+                             uchar *org_key, uchar *prev_key, uchar *key,
+                             MI_KEY_PARAM *s_temp)
+{
+  uint length,key_length,ref_length;
+
+  s_temp->totlength=key_length=_mi_keylength(keyinfo,key)+nod_flag;
+#ifdef HAVE_valgrind
+  s_temp->n_length= s_temp->n_ref_length=0;	/* For valgrind */
+#endif
+  s_temp->key=key;
+  s_temp->prev_key=org_key;
+  if (prev_key)                                 /* If not first key in block */
+  {
+    /* pack key against previous key */
+    /*
+      As keys may be identical when running a sort in myisamchk, we
+      have to guard against the case where keys may be identical
+    */
+    uchar *end;
+    end=key+key_length;
+    for ( ; *key == *prev_key && key < end; key++,prev_key++) ;
+    s_temp->ref_length= ref_length=(uint) (key-s_temp->key);
+    length=key_length - ref_length + get_pack_length(ref_length);
+  }
+  else
+  {
+    /* No previous key */
+    s_temp->ref_length=ref_length=0;
+    length=key_length+1;
+  }
+  if ((s_temp->next_key_pos=next_key))          /* If another key after */
+  {
+    /* pack key against next key */
+    uint next_length,next_length_pack;
+    get_key_pack_length(next_length,next_length_pack,next_key);
+
+    /* If first key and next key is packed (only on delete) */
+    if (!prev_key && org_key && next_length)
+    {
+      uchar *end;
+      for (key= s_temp->key, end=key+next_length ;
+           *key == *org_key && key < end;
+           key++,org_key++) ;
+      ref_length= (uint) (key - s_temp->key);
+    }
+
+    if (next_length > ref_length)
+    {
+      /* We put a key with different case between two keys with the same prefix
+         Extend next key to have same prefix as
+         this key */
+      s_temp->n_ref_length= ref_length;
+      s_temp->prev_length=  next_length-ref_length;
+      s_temp->prev_key+=    ref_length;
+      return (int) (length+ s_temp->prev_length - next_length_pack +
+                    get_pack_length(ref_length));
+    }
+    /* Check how many characters are identical to next key */
+    key= s_temp->key+next_length;
+    s_temp->prev_length= 0;
+    while (*key++ == *next_key++) ;
+    if ((ref_length= (uint) (key - s_temp->key)-1) == next_length)
+    {
+      s_temp->next_key_pos=0;
+      return length;                            /* can't pack next key */
+    }
+    s_temp->n_ref_length=ref_length;
+    return (int) (length-(ref_length - next_length) - next_length_pack +
+                  get_pack_length(ref_length));
+  }
+  return (int) length;
+}
+
+
+/*
+** store a key packed with _mi_calc_xxx_key_length in page-buffert
+*/
+
+/* store key without compression */
+
+void _mi_store_static_key(MI_KEYDEF *keyinfo __attribute__((unused)),
+                          register uchar *key_pos,
+                          register MI_KEY_PARAM *s_temp)
+{
+  memcpy((uchar*) key_pos,(uchar*) s_temp->key,(size_t) s_temp->totlength);
+}
+
+
+/* store variable length key with prefix compression */
+
+#define store_pack_length(test,pos,length) { \
+  if (test) { *((pos)++) = (uchar) (length); } else \
+  { *((pos)++) = (uchar) ((length) >> 8); *((pos)++) = (uchar) (length);  } }
+
+
+void _mi_store_var_pack_key(MI_KEYDEF *keyinfo  __attribute__((unused)),
+                            register uchar *key_pos,
+                            register MI_KEY_PARAM *s_temp)
+{
+  uint length;
+  uchar *start;
+
+  start=key_pos;
+
+  if (s_temp->ref_length)
+  {
+    /* Packed against previous key */
+    store_pack_length(s_temp->pack_marker == 128,key_pos,s_temp->ref_length);
+    /* If not same key after */
+    if (s_temp->ref_length != s_temp->pack_marker)
+      store_key_length_inc(key_pos,s_temp->key_length);
+  }
+  else
+  {
+    /* Not packed against previous key */
+    store_pack_length(s_temp->pack_marker == 128,key_pos,s_temp->key_length);
+  }
+  bmove((uchar*) key_pos,(uchar*) s_temp->key,
+        (length=s_temp->totlength-(uint) (key_pos-start)));
+
+  if (!s_temp->next_key_pos)                    /* No following key */
+    return;
+  key_pos+=length;
+
+  if (s_temp->prev_length)
+  {
+    /* Extend next key because new key didn't have same prefix as prev key */
+    if (s_temp->part_of_prev_key)
+    {
+      store_pack_length(s_temp->pack_marker == 128,key_pos,
+                        s_temp->part_of_prev_key);
+      store_key_length_inc(key_pos,s_temp->n_length);
+    }
+    else
+    {
+      s_temp->n_length+= s_temp->store_not_null;
+      store_pack_length(s_temp->pack_marker == 128,key_pos,
+                        s_temp->n_length);
+    }
+    memcpy(key_pos, s_temp->prev_key, s_temp->prev_length);
+  }
+  else if (s_temp->n_ref_length)
+  {
+    store_pack_length(s_temp->pack_marker == 128,key_pos,s_temp->n_ref_length);
+    if (s_temp->n_ref_length == s_temp->pack_marker)
+      return;                                   /* Identical key */
+    store_key_length(key_pos,s_temp->n_length);
+  }
+  else if (s_temp->n_length)
+  {
+    s_temp->n_length+= s_temp->store_not_null;
+    store_pack_length(s_temp->pack_marker == 128,key_pos,s_temp->n_length);
+  }
+}
+
+
+/* variable length key with prefix compression */
+
+void _mi_store_bin_pack_key(MI_KEYDEF *keyinfo  __attribute__((unused)),
+                            register uchar *key_pos,
+                            register MI_KEY_PARAM *s_temp)
+{
+  store_key_length_inc(key_pos,s_temp->ref_length);
+  memcpy((char*) key_pos,(char*) s_temp->key+s_temp->ref_length,
+          (size_t) s_temp->totlength-s_temp->ref_length);
+
+  if (s_temp->next_key_pos)
+  {
+    key_pos+=(uint) (s_temp->totlength-s_temp->ref_length);
+    store_key_length_inc(key_pos,s_temp->n_ref_length);
+    if (s_temp->prev_length)                    /* If we must extend key */
+    {
+      memcpy(key_pos,s_temp->prev_key,s_temp->prev_length);
+    }
+  }
+}