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

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

1 files changed, 2395 insertions, 0 deletions

diff --git a/storage/maria/ma_search.c b/storage/maria/ma_search.c
new file mode 100644
index 00000000..e6f8b6bc
--- /dev/null
+++ b/storage/maria/ma_search.c
@@ -0,0 +1,2395 @@
+/* Copyright (C) 2006 MySQL AB & MySQL Finland AB & TCX DataKonsult AB
+
+   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 Street, Fifth Floor, Boston, MA 02110-1335 USA */
+
+/* key handling functions */
+
+#include "ma_fulltext.h"
+#include "m_ctype.h"
+
+static int _ma_search_no_save(register MARIA_HA *info, MARIA_KEY *key,
+                              uint32 nextflag, register my_off_t pos,
+                              MARIA_PINNED_PAGE **res_page_link,
+                              uchar **res_page_buff);
+static my_bool _ma_get_prev_key(MARIA_KEY *key, MARIA_PAGE *ma_page,
+                                uchar *keypos);
+
+
+/* Check that new index is ok */
+
+int _ma_check_index(MARIA_HA *info, int inx)
+{
+  if (inx < 0 || ! maria_is_key_active(info->s->state.key_map, inx))
+  {
+    my_errno=HA_ERR_WRONG_INDEX;
+    return -1;
+  }
+  if (info->lastinx != inx)             /* Index changed */
+  {
+    info->lastinx = inx;
+    info->last_key.keyinfo= info->s->keyinfo + inx;
+    info->last_key.flag= 0;
+    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))
+  {
+    if (unlikely(!my_errno))
+      my_errno= HA_ERR_INTERNAL_ERROR;          /* Impossible */
+    return(-1);
+  }
+  if (unlikely(maria_is_crashed(info)))
+  {
+    my_errno= HA_ERR_CRASHED;
+    return(-1);
+  }
+
+  return(inx);
+} /* _ma_check_index */
+
+
+/**
+   @breif Search after row by a key
+
+   @note
+     Position to row is stored in info->lastpos
+
+   @return
+   @retval  0   ok (key found)
+   @retval -1   Not found
+   @retval  1   If one should continue search on higher level
+*/
+
+int _ma_search(register MARIA_HA *info, MARIA_KEY *key, uint32 nextflag,
+               my_off_t pos)
+{
+  int error;
+  MARIA_PINNED_PAGE *page_link;
+  uchar *page_buff;
+
+  info->page_changed= 1;                        /* If page not saved */
+  if (!(error= _ma_search_no_save(info, key, nextflag, pos, &page_link,
+                                  &page_buff)))
+  {
+    if (nextflag & SEARCH_SAVE_BUFF)
+    {
+      memcpy(info->keyread_buff, page_buff, info->s->block_size);
+
+      /* Save position for a possible read next / previous */
+      info->int_keypos= info->keyread_buff + info->keypos_offset;
+      info->int_maxpos= info->keyread_buff + info->maxpos_offset;
+      info->int_keytree_version= key->keyinfo->version;
+      info->last_search_keypage= info->last_keypage;
+      info->page_changed= 0;
+      info->keyread_buff_used= 0;
+    }
+  }
+  _ma_unpin_all_pages(info, LSN_IMPOSSIBLE);
+  return (error);
+}
+
+/**
+   @breif Search after row by a key
+
+   ret_page_link	Will contain pointer to page where we found key
+
+   @note
+     Position to row is stored in info->lastpos
+     Last used key is stored in info->last_key
+
+   @return
+   @retval  0   ok (key found)
+   @retval -1   Not found
+   @retval  1   If one should continue search on higher level
+*/
+
+static int _ma_search_no_save(register MARIA_HA *info, MARIA_KEY *key,
+                              uint32 nextflag, register my_off_t pos,
+                              MARIA_PINNED_PAGE **res_page_link,
+                              uchar **res_page_buff)
+{
+  my_bool last_key_not_used, buff_alloced;
+  int error,flag;
+  uint page_flag, nod_flag, used_length;
+  uchar *keypos,*maxpos;
+  uchar *lastkey;
+  MARIA_KEYDEF *keyinfo= key->keyinfo;
+  MARIA_PAGE page;
+  MARIA_PINNED_PAGE *page_link;
+  DBUG_ENTER("_ma_search");
+  DBUG_PRINT("enter",("page: %lu  nextflag: %u  lastpos: %lu",
+                      (ulong) (pos / info->s->block_size),
+                      nextflag, (ulong) info->cur_row.lastpos));
+  DBUG_EXECUTE("key", _ma_print_key(DBUG_FILE, key););
+  DBUG_ASSERT(info->last_key.keyinfo == key->keyinfo);
+
+  if (pos == HA_OFFSET_ERROR)
+  {
+    my_errno=HA_ERR_KEY_NOT_FOUND;                      /* Didn't find key */
+    info->cur_row.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 */
+  }
+
+  alloc_on_stack(*info->stack_end_ptr, lastkey, buff_alloced,
+                 keyinfo->max_store_length);
+  if (!lastkey)
+    DBUG_RETURN(1);
+
+  if (_ma_fetch_keypage(&page, info, keyinfo, pos,
+                        PAGECACHE_LOCK_READ, DFLT_INIT_HITS, 0, 0))
+    goto err;
+  page_link= dynamic_element(&info->pinned_pages,
+                             info->pinned_pages.elements-1,
+                             MARIA_PINNED_PAGE*);
+  DBUG_DUMP("page", page.buff, page.size);
+
+  flag= (*keyinfo->bin_search)(key, &page, nextflag, &keypos, lastkey,
+                               &last_key_not_used);
+  if (flag == MARIA_FOUND_WRONG_KEY)
+  {
+    _ma_print_error(info, HA_ERR_CRASHED, 0);
+    my_errno= HA_ERR_CRASHED;
+    goto err;
+  }
+  page_flag=   page.flag;
+  used_length= page.size;
+  nod_flag=    page.node;
+  maxpos=      page.buff + used_length -1;
+
+  if (flag)
+  {
+    if ((error= _ma_search_no_save(info, key, nextflag,
+                                   _ma_kpos(nod_flag,keypos),
+                                   res_page_link, res_page_buff)) <= 0)
+      goto ret_error;
+
+    error= 1;                                    /* Default return value */
+    if (flag >0)
+    {
+      if (nextflag & (SEARCH_SMALLER | SEARCH_LAST) &&
+          keypos == page.buff + info->s->keypage_header + nod_flag)
+        goto ret_error;                         /* Bigger than key */
+    }
+    else if (nextflag & SEARCH_BIGGER && keypos >= maxpos)
+      goto ret_error;                           /* Smaller than key */
+  }
+  else
+  {
+    /* Found matching key */
+    if ((nextflag & SEARCH_FIND) && nod_flag &&
+	((keyinfo->flag & (HA_NOSAME | HA_NULL_PART)) != HA_NOSAME ||
+	 (key->flag & SEARCH_PART_KEY) || info->s->base.born_transactional))
+    {
+      if ((error= _ma_search_no_save(info, key, (nextflag | SEARCH_FIND) &
+                                     ~(SEARCH_BIGGER | SEARCH_SMALLER |
+                                       SEARCH_LAST),
+                                     _ma_kpos(nod_flag,keypos),
+                                     res_page_link, res_page_buff)) >= 0 ||
+          my_errno != HA_ERR_KEY_NOT_FOUND)
+        goto ret_error;
+    }
+  }
+
+  if ((nextflag & (SEARCH_SMALLER | SEARCH_LAST)) && flag != 0)
+  {
+    uint not_used[2];
+    if (_ma_get_prev_key(&info->last_key, &page, keypos))
+      goto err;
+    /*
+      We have to use key->flag >> 1 here to transform
+      SEARCH_PAGE_KEY_HAS_TRANSID to SEARCH_USER_KEY_HAS_TRANSID
+    */
+    if (!(nextflag & SEARCH_SMALLER) &&
+        ha_key_cmp(keyinfo->seg, info->last_key.data, key->data,
+                   key->data_length + key->ref_length,
+                   SEARCH_FIND | (key->flag >> 1) | info->last_key.flag,
+                   not_used))
+    {
+      my_errno=HA_ERR_KEY_NOT_FOUND;                    /* Didn't find key */
+      goto err;
+    }
+  }
+  else
+  {
+    /* Set info->last_key to temporarily point to last key value */
+    info->last_key.data= lastkey;
+    /* Get key value (if not packed key) and position after key */
+    if (!(*keyinfo->get_key)(&info->last_key, page_flag, nod_flag, &keypos))
+      goto err;
+    memcpy(info->lastkey_buff, lastkey,
+           info->last_key.data_length + info->last_key.ref_length);
+    info->last_key.data= info->lastkey_buff;
+  }
+  info->cur_row.lastpos= _ma_row_pos_from_key(&info->last_key);
+  info->cur_row.trid=    _ma_trid_from_key(&info->last_key);
+
+  /* Store offset to key */
+  info->keypos_offset= (uint) (keypos - page.buff);
+  info->maxpos_offset= (uint) (maxpos - page.buff);
+  info->int_nod_flag= nod_flag;
+  info->last_keypage= pos;
+  *res_page_link= page_link;
+  *res_page_buff= page.buff;
+  
+  stack_alloc_free(lastkey, buff_alloced);
+  DBUG_PRINT("exit",("found key at %lu",(ulong) info->cur_row.lastpos));
+  DBUG_RETURN(0);
+
+err:
+  DBUG_PRINT("exit",("Error: %d",my_errno));
+  info->cur_row.lastpos= HA_OFFSET_ERROR;
+  info->page_changed=1;
+  error= -1;
+
+ret_error:
+  stack_alloc_free(lastkey, buff_alloced);
+  DBUG_RETURN(error);
+}
+
+
+/*
+  Search after key in page-block
+
+  @fn    _ma_bin_search
+  @param key		Search after this key
+  @param page		Start of data page
+  @param comp_flag	How key should be compared
+  @param ret_pos
+  @param buff		Buffer for holding a key (not used here)
+  @param last_key
+
+  @note
+   If keys are packed, then smaller or identical key is stored in buff
+
+  @return
+  @retval <0, 0 , >0 depending on if if found is smaller, equal or bigger than
+          'key'
+  @retval ret_pos   Points to where the identical or bigger key starts
+  @retval last_key  Set to 1 if key is the last key in the page.
+*/
+
+int _ma_bin_search(const MARIA_KEY *key, const MARIA_PAGE *ma_page,
+                   uint32 comp_flag, uchar **ret_pos,
+                   uchar *buff __attribute__((unused)), my_bool *last_key)
+{
+  int UNINIT_VAR(flag);
+  uint page_flag;
+  uint start, mid, end, save_end, totlength, nod_flag;
+  uint not_used[2];
+  MARIA_KEYDEF *keyinfo= key->keyinfo;
+  MARIA_SHARE *share=  keyinfo->share;
+  uchar *page;
+  DBUG_ENTER("_ma_bin_search");
+
+  page_flag= ma_page->flag;
+  if (page_flag & KEYPAGE_FLAG_HAS_TRANSID)
+  {
+    /* Keys have varying length, can't use binary search */
+    DBUG_RETURN(_ma_seq_search(key, ma_page, comp_flag, ret_pos, buff,
+                               last_key));
+  }
+
+  nod_flag=    ma_page->node;
+  totlength= keyinfo->keylength + nod_flag;
+  DBUG_ASSERT(ma_page->size >= share->keypage_header + nod_flag + totlength);
+
+  start=0;
+  mid=1;
+  save_end= end= ((ma_page->size - nod_flag - share->keypage_header) /
+                  totlength-1);
+  DBUG_PRINT("test",("page_length: %u  end: %u", ma_page->size, end));
+  page= ma_page->buff + share->keypage_header + nod_flag;
+
+  while (start != end)
+  {
+    mid= (start+end)/2;
+    if ((flag=ha_key_cmp(keyinfo->seg, page + (uint) mid * totlength,
+                         key->data, key->data_length + key->ref_length,
+                         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->data, key->data_length + key->ref_length, 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);
+} /* _ma_bin_search */
+
+
+/**
+   Locate a packed key in a key page.
+
+   @fn    _ma_seq_search()
+   @param key                       Search key.
+   @param page                      Key page (beginning).
+   @param comp_flag                 Search flags like SEARCH_SAME etc.
+   @param ret_pos
+   @param buff                      Buffer for holding temp keys
+   @param last_key
+
+   @description
+   Used instead of _ma_bin_search() when key is packed.
+   Puts smaller or identical key in buff.
+   Key is searched sequentially.
+
+   @todo
+   Don't copy key to buffer if we are not using key with prefix packing
+
+   @return
+   @retval > 0         Key in 'buff' is smaller than search key.
+   @retval 0           Key in 'buff' is identical to search key.
+   @retval < 0         Not found.
+
+   @retval ret_pos   Points to where the identical or bigger key starts
+   @retval last_key  Set to 1 if key is the last key in the page
+   @retval buff      Copy of previous or identical unpacked key
+*/
+
+int _ma_seq_search(const MARIA_KEY *key, const MARIA_PAGE *ma_page,
+                   uint32 comp_flag, uchar **ret_pos,
+                   uchar *buff, my_bool *last_key)
+{
+  int UNINIT_VAR(flag);
+  uint page_flag, nod_flag, UNINIT_VAR(length), not_used[2];
+  uchar t_buff[MARIA_MAX_KEY_BUFF], *end;
+  uchar *page;
+  MARIA_KEYDEF *keyinfo= key->keyinfo;
+  MARIA_SHARE *share= keyinfo->share;
+  MARIA_KEY tmp_key;
+  DBUG_ENTER("_ma_seq_search");
+
+  page_flag= ma_page->flag;
+  nod_flag=  ma_page->node;
+  page=      ma_page->buff;
+  end= page + ma_page->size;
+  page+= share->keypage_header + nod_flag;
+  *ret_pos= page;
+  t_buff[0]=0;                                  /* Avoid bugs */
+
+  tmp_key.data= t_buff;
+  tmp_key.keyinfo= keyinfo;
+  while (page < end)
+  {
+    length=(*keyinfo->get_key)(&tmp_key, page_flag, nod_flag, &page);
+    if (length == 0 || page > end)
+    {
+      _ma_set_fatal_error_with_share(share, HA_ERR_CRASHED);
+      DBUG_PRINT("error",
+                 ("Found wrong key:  length: %u  page: %p  end: %p",
+                  length, page, end));
+      DBUG_RETURN(MARIA_FOUND_WRONG_KEY);
+    }
+    if ((flag= ha_key_cmp(keyinfo->seg, t_buff, key->data,
+                          key->data_length + key->ref_length,
+                          comp_flag | tmp_key.flag,
+                          not_used)) >= 0)
+      break;
+    DBUG_PRINT("loop_extra",("page:%p  key: '%s'  flag: %d",
+                             page, t_buff, flag));
+    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);
+} /* _ma_seq_search */
+
+
+/**
+   Search for key on key page with string prefix compression
+
+   @notes
+   This is an optimized function compared to calling _ma_get_pack_key()
+   for each key in the buffer
+
+   Same interface as for _ma_seq_search()
+*/
+
+int _ma_prefix_search(const MARIA_KEY *key, const MARIA_PAGE *ma_page,
+                      uint32 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 page_flag, UNINIT_VAR(prefix_len),suffix_len;
+  int key_len_skip, UNINIT_VAR(seg_len_pack), key_len_left;
+  uchar *end, *vseg, *UNINIT_VAR(saved_vseg), *UNINIT_VAR(saved_from);
+  uchar *page;
+  uchar tt_buff[MARIA_MAX_KEY_BUFF+2], *t_buff=tt_buff+2;
+  uchar  *UNINIT_VAR(saved_to);
+  const uchar *kseg;
+  uint  saved_length=0, saved_prefix_len=0;
+  uint  length_pack;
+  MARIA_KEYDEF *keyinfo= key->keyinfo;
+  MARIA_SHARE *share= keyinfo->share;
+  const uchar *sort_order= keyinfo->seg->charset->sort_order;
+  const int reverse = keyinfo->seg->flag & HA_REVERSE_SORT;
+  DBUG_ENTER("_ma_prefix_search");
+
+  t_buff[0]=0;                                  /* Avoid bugs */
+  page_flag=   ma_page->flag;
+  nod_flag=    ma_page->node;
+  page_flag&= KEYPAGE_FLAG_HAS_TRANSID;         /* For faster test in loop */
+  page= ma_page->buff;
+  end= page + ma_page->size;
+  page+= share->keypage_header + nod_flag;
+  *ret_pos= page;
+  kseg= key->data;
+
+  get_key_pack_length(kseg_len, length_pack, kseg);
+  key_len_skip=length_pack+kseg_len;
+  key_len_left=(int) (key->data_length + key->ref_length) - (int) key_len_skip;
+  /* If key_len is 0, then length_pack is 1, then key_len_left is -1. */
+  cmplen= ((key_len_left>=0) ? kseg_len :
+           (key->data_length + key->ref_length - 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 uchar 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;
+    uint key_flag;
+
+    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));
+    {
+      /* Calculate length of one key */
+      uchar *from= vseg+suffix_len;
+      HA_KEYSEG *keyseg;
+
+      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))
+        {
+          uint key_part_length;
+          get_key_length(key_part_length,from);
+          from+= key_part_length;
+        }
+        else
+          from+= keyseg->length;
+      }
+      from+= keyseg->length;
+      key_flag=0;
+
+      if (page_flag && key_has_transid(from-1))
+      {
+        from+= transid_packed_length(from);
+        key_flag= SEARCH_PAGE_KEY_HAS_TRANSID;
+      }
+      page= from + nod_flag;
+      length= (uint) (from-vseg);
+    }
+
+    if (page > end)
+    {
+      _ma_set_fatal_error_with_share(share, HA_ERR_CRASHED);
+      DBUG_PRINT("error",
+                 ("Found wrong key:  length: %u  page: %p  end: %p",
+                  length, page, end));
+      DBUG_RETURN(MARIA_FOUND_WRONG_KEY);
+    }
+
+    if (matched >= prefix_len)
+    {
+      /* We have to compare. But we can still skip part of the key */
+      uint  left;
+      const 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 */
+	    const 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 | key_flag,
+                                   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);
+} /* _ma_prefix_search */
+
+
+/* Get pos to a key_block */
+
+my_off_t _ma_kpos(uint nod_flag, const uchar *after_key)
+{
+  after_key-=nod_flag;
+  switch (nod_flag) {
+#if SIZEOF_OFF_T > 4
+  case 7:
+    return mi_uint7korr(after_key)*maria_block_size;
+  case 6:
+    return mi_uint6korr(after_key)*maria_block_size;
+  case 5:
+    return mi_uint5korr(after_key)*maria_block_size;
+#else
+  case 7:
+    after_key++;
+  case 6:
+    after_key++;
+  case 5:
+    after_key++;
+#endif
+  case 4:
+    return ((my_off_t) mi_uint4korr(after_key))*maria_block_size;
+  case 3:
+    return ((my_off_t) mi_uint3korr(after_key))*maria_block_size;
+  case 2:
+    return (my_off_t) (mi_uint2korr(after_key)*maria_block_size);
+  case 1:
+    return (uint) (*after_key)*maria_block_size;
+  case 0:                                       /* At leaf page */
+  default:                                      /* Impossible */
+    return(HA_OFFSET_ERROR);
+  }
+} /* _kpos */
+
+
+/* Save pos to a key_block */
+
+void _ma_kpointer(register MARIA_HA *info, register uchar *buff, my_off_t pos)
+{
+  pos/=maria_block_size;
+  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 */
+  }
+} /* _ma_kpointer */
+
+
+/* Calc pos to a data-record from a key */
+
+MARIA_RECORD_POS _ma_row_pos_from_key(const MARIA_KEY *key)
+{
+  my_off_t pos;
+  const uchar *after_key= key->data + key->data_length;
+  MARIA_SHARE *share= key->keyinfo->share;
+  switch (share->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;
+  case 0:                                       /* NO_RECORD */
+  default:
+    pos=0L;                                     /* Shut compiler up */
+  }
+  return (*share->keypos_to_recpos)(share, pos);
+}
+
+
+/**
+   Get trid from a key
+
+   @param key	Maria key read from a page
+
+   @retval 0    If key doesn't have a trid
+   @retval trid
+*/
+
+TrID _ma_trid_from_key(const MARIA_KEY *key)
+{
+  if (!(key->flag & (SEARCH_PAGE_KEY_HAS_TRANSID |
+                     SEARCH_USER_KEY_HAS_TRANSID)))
+    return 0;
+  return transid_get_packed(key->keyinfo->share,
+                            key->data + key->data_length +
+                            key->keyinfo->share->rec_reflength);
+}
+
+
+/* Calc position from a record pointer ( in delete link chain ) */
+
+MARIA_RECORD_POS _ma_rec_pos(MARIA_SHARE *share, uchar *ptr)
+{
+  my_off_t pos;
+  switch (share->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+= (share->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 (*share->keypos_to_recpos)(share, pos);
+}
+
+
+/* save position to record */
+
+void _ma_dpointer(MARIA_SHARE *share, uchar *buff, my_off_t pos)
+{
+  if (pos != HA_OFFSET_ERROR)
+    pos= (*share->recpos_to_keypos)(share, pos);
+
+  switch (share->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;
+  case 0: break;                                /* For NO_RECORD */
+  default: abort();                             /* Impossible */
+  }
+} /* _ma_dpointer */
+
+
+my_off_t _ma_static_keypos_to_recpos(MARIA_SHARE *share, my_off_t pos)
+{
+  return pos * share->base.pack_reclength;
+}
+
+
+my_off_t _ma_static_recpos_to_keypos(MARIA_SHARE *share, my_off_t pos)
+{
+  return pos / share->base.pack_reclength;
+}
+
+my_off_t _ma_transparent_recpos(MARIA_SHARE *share __attribute__((unused)),
+                                my_off_t pos)
+{
+  return pos;
+}
+
+my_off_t _ma_transaction_keypos_to_recpos(MARIA_SHARE *share
+                                          __attribute__((unused)),
+                                          my_off_t pos)
+{
+  /* We need one bit to store if there is transid's after position */
+  return pos >> 1;
+}
+
+my_off_t _ma_transaction_recpos_to_keypos(MARIA_SHARE *share
+                                          __attribute__((unused)),
+                                          my_off_t pos)
+{
+  return pos << 1;
+}
+
+/*
+  @brief Get key from key-block
+
+  @param key         Should contain previous key. Will contain new key
+  @param page_flag   Flag on page block
+  @param nod_flag    Is set to nod length if we on nod
+  @param page        Points at previous key; Its advanced to point at next key
+
+  @notes
+    Same as _ma_get_key but used with fixed length keys
+
+  @return
+  @retval key_length + length of data pointer (without nod length)
+ */
+
+uint _ma_get_static_key(MARIA_KEY *key, uint page_flag, uint nod_flag,
+                        register uchar **page)
+{
+  register MARIA_KEYDEF *keyinfo= key->keyinfo;
+  uint key_length= keyinfo->keylength;
+
+  key->ref_length=  keyinfo->share->rec_reflength;
+  key->data_length= key_length - key->ref_length;
+  key->flag= 0;
+  if (page_flag & KEYPAGE_FLAG_HAS_TRANSID)
+  {
+    uchar *end= *page + keyinfo->keylength;
+    if (key_has_transid(end-1))
+    {
+      uint trans_length= transid_packed_length(end);
+      key->ref_length+= trans_length;
+      key_length+= trans_length;
+      key->flag= SEARCH_PAGE_KEY_HAS_TRANSID;
+    }
+  }
+  key_length+= nod_flag;
+  memcpy(key->data, *page, key_length);
+  *page+= key_length;
+  return key_length - nod_flag;
+} /* _ma_get_static_key */
+
+
+/**
+   Skip over static length key from key-block
+
+  @fn _ma_skip_static_key()
+  @param key       Keyinfo and buffer that can be used
+  @param nod_flag  If nod: Length of node pointer, else zero.
+  @param key       Points at key
+
+  @retval pointer to next key
+*/
+
+uchar *_ma_skip_static_key(MARIA_KEY *key, uint page_flag,
+                           uint nod_flag, uchar *page)
+{
+  page+= key->keyinfo->keylength;
+  if ((page_flag & KEYPAGE_FLAG_HAS_TRANSID) && key_has_transid(page-1))
+    page+= transid_packed_length(page);
+  return page+ nod_flag;
+}
+
+
+/*
+  get key which is packed against previous key or key with a NULL column.
+
+  SYNOPSIS
+    _ma_get_pack_key()
+    @param int_key   Should contain previous key. Will contain new key
+    @param page_flag page_flag from page
+    @param nod_flag  If nod: Length of node pointer, else zero.
+    @param page_pos  Points at previous key; Its advanced to point at next key
+
+    @return
+    @retval key_length + length of data pointer
+*/
+
+uint _ma_get_pack_key(MARIA_KEY *int_key, uint page_flag,
+                      uint nod_flag, uchar **page_pos)
+{
+  reg1 HA_KEYSEG *keyseg;
+  uchar *page= *page_pos;
+  uint length;
+  uchar *key= int_key->data;
+  MARIA_KEYDEF *keyinfo= int_key->keyinfo;
+
+  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)
+	{
+          _ma_set_fatal_error_with_share(keyinfo->share, 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);
+            _ma_set_fatal_error_with_share(keyinfo->share, 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
+      {
+        /* Key that is not packed against previous key */
+        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);
+        _ma_set_fatal_error_with_share(keyinfo->share, 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(key, page,(size_t) length);
+    key+=length;
+    page+=length;
+  }
+
+  int_key->data_length= (uint)(key - int_key->data);
+  int_key->flag= 0;
+  length= keyseg->length;
+  if (page_flag & KEYPAGE_FLAG_HAS_TRANSID)
+  {
+    uchar *end= page + length;
+    if (key_has_transid(end-1))
+    {
+      length+= transid_packed_length(end);
+      int_key->flag= SEARCH_PAGE_KEY_HAS_TRANSID;
+    }
+  }
+  int_key->ref_length= length;
+  length+= nod_flag;
+  bmove(key, page, length);
+  *page_pos= page+length;
+
+  return (int_key->data_length + int_key->ref_length);
+} /* _ma_get_pack_key */
+
+
+/**
+  skip key which is packed against previous key or key with a NULL column.
+
+  @fn _ma_skip_pack_key()
+  @param key       Keyinfo and buffer that can be used
+  @param nod_flag  If nod: Length of node pointer, else zero.
+  @param key       Points at key
+
+  @note
+  This is in principle a simpler version of _ma_get_pack_key()
+
+  @retval pointer to next key
+*/
+
+uchar *_ma_skip_pack_key(MARIA_KEY *key, uint page_flag,
+                         uint nod_flag, uchar *page)
+{
+  reg1 HA_KEYSEG *keyseg;
+  for (keyseg= key->keyinfo->seg ; keyseg->type ; keyseg++)
+  {
+    if (keyseg->flag & HA_PACK_KEY)
+    {
+      /* key with length, packed to previous key */
+      uint packed= *page & 128, length;
+      if (keyseg->length >= 127)
+      {
+        length= mi_uint2korr(page) & 32767;
+        page+= 2;
+      }
+      else
+        length= *page++ & 127;
+
+      if (packed)
+      {
+	if (length == 0)			/* Same key */
+	  continue;
+	get_key_length(length,page);
+	page+= length;
+	continue;
+      }
+      if ((keyseg->flag & HA_NULL_PART) && length)
+      {
+        /*
+          Keys that can have null use length+1 as the length for date as the
+          number 0 is reserved for keys that have a NULL value
+        */
+        length--;
+      }
+      page+= length;
+    }
+    else
+    {
+      if (keyseg->flag & HA_NULL_PART)
+        if (!*page++)
+          continue;
+      if (keyseg->flag & (HA_SPACE_PACK | HA_BLOB_PART | HA_VAR_LENGTH_PART))
+      {
+        uint length;
+        get_key_length(length,page);
+        page+=length;
+      }
+      else
+        page+= keyseg->length;
+    }
+  }
+  page+= keyseg->length;
+  if ((page_flag & KEYPAGE_FLAG_HAS_TRANSID) && key_has_transid(page-1))
+    page+= transid_packed_length(page);
+  return page + nod_flag;
+}
+
+
+/* Read key that is packed relatively to previous */
+
+uint _ma_get_binary_pack_key(MARIA_KEY *int_key, uint page_flag, uint nod_flag,
+                             register uchar **page_pos)
+{
+  reg1 HA_KEYSEG *keyseg;
+  uchar *page, *page_end, *from, *from_end, *key;
+  uint length,tmp;
+  MARIA_KEYDEF *keyinfo= int_key->keyinfo;
+  DBUG_ENTER("_ma_get_binary_pack_key");
+
+  page= *page_pos;
+  page_end=page + MARIA_MAX_KEY_BUFF + 1;
+  key= int_key->data;
+
+  /*
+    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);
+      _ma_set_fatal_error_with_share(keyinfo->share, HA_ERR_CRASHED);
+      DBUG_RETURN(0);                                 /* 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= (uint) (uchar) (*key++ = *from++)) == 255)
+      {
+        /* If prefix is used up, switch to rest. */
+        if (from == from_end) { from=page;  from_end=page_end; }
+        length= ((uint) (uchar) ((*key++ = *from++))) << 8;
+        /* If prefix is used up, switch to rest. */
+        if (from == from_end) { from=page;  from_end=page_end; }
+        length+= (uint) (uchar) ((*key++ = *from++));
+      }
+    }
+    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_ASSERT((int) length >= 0);
+    DBUG_PRINT("info",("key: %p  from: %p  length: %u",
+		       key, from, length));
+    memmove(key, 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.
+  */
+  int_key->data_length= (uint)(key - int_key->data);
+  int_key->ref_length= length= keyseg->length;
+  int_key->flag= 0;
+  if ((tmp=(uint) (from_end-from)) <= length)
+  {
+    /* Skip over the last common part of the data */
+    key+= tmp;
+    length-= tmp;
+    from= page;
+  }
+  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 MARIA_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"));
+      _ma_set_fatal_error_with_share(keyinfo->share, HA_ERR_CRASHED);
+      DBUG_RETURN(0);                                 /* Error */
+    }
+  }
+  if (page_flag & KEYPAGE_FLAG_HAS_TRANSID)
+  {
+    uchar *end= from + length;
+    if (key_has_transid(end-1))
+    {
+      uint trans_length= transid_packed_length(end);
+      length+= trans_length;
+      int_key->ref_length+= trans_length;
+      int_key->flag= SEARCH_PAGE_KEY_HAS_TRANSID;
+    }
+  }
+
+  /* Copy rest of data ptr and, if appropriate, trans_id and node_ptr */
+  memcpy(key, from, length + nod_flag);
+  *page_pos= from + length + nod_flag;
+  
+#ifdef USEFUL_FOR_DEBUGGING
+  DBUG_DUMP("key", int_key->data,
+            (uint) (int_key->data_length + int_key->ref_length));
+#endif
+  DBUG_RETURN(int_key->data_length + int_key->ref_length);
+}
+
+/**
+  skip key which is ptefix packed against previous key
+
+  @fn _ma_skip_binary_key()
+  @param key       Keyinfo and buffer that can be used
+  @param nod_flag  If nod: Length of node pointer, else zero.
+  @param key       Points at key
+
+  @note
+  We have to copy the key as otherwise we don't know how much left
+  data there is of the key.
+
+  @todo
+  Implement more efficient version of this. We can ignore to copy any rest
+  key parts that are not null or not packed. We also don't have to copy
+  rowid or transid.
+
+  @retval pointer to next key
+*/
+
+uchar *_ma_skip_binary_pack_key(MARIA_KEY *key, uint page_flag,
+                                uint nod_flag, uchar *page)
+{
+  if (!_ma_get_binary_pack_key(key, page_flag, nod_flag, &page))
+    return 0;
+  return page;
+}
+
+
+/**
+  @brief Get key at position without knowledge of previous key
+
+  @return pointer to next key
+*/
+
+uchar *_ma_get_key(MARIA_KEY *key, MARIA_PAGE *ma_page, uchar *keypos)
+{
+  uint page_flag, nod_flag;
+  MARIA_KEYDEF *keyinfo= key->keyinfo;
+  uchar *page;
+  DBUG_ENTER("_ma_get_key");
+
+  page=       ma_page->buff;
+  page_flag=  ma_page->flag;
+  nod_flag=   ma_page->node;
+
+  if (! (keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)) &&
+      ! (page_flag & KEYPAGE_FLAG_HAS_TRANSID))
+  {
+    bmove(key->data, keypos, keyinfo->keylength+nod_flag);
+    key->ref_length= keyinfo->share->rec_reflength;
+    key->data_length= keyinfo->keylength - key->ref_length;
+    key->flag= 0;
+    DBUG_RETURN(keypos+keyinfo->keylength+nod_flag);
+  }
+  else
+  {
+    page+= keyinfo->share->keypage_header + nod_flag;
+    key->data[0]= 0;                            /* safety */
+    while (page <= keypos)
+    {
+      if (!(*keyinfo->get_key)(key, page_flag, nod_flag, &page))
+      {
+        _ma_set_fatal_error_with_share(keyinfo->share, HA_ERR_CRASHED);
+        DBUG_RETURN(0);
+      }
+    }
+  }
+  DBUG_PRINT("exit",("page: %p  length: %u", page,
+                     key->data_length + key->ref_length));
+  DBUG_RETURN(page);
+} /* _ma_get_key */
+
+
+/*
+  @brief Get key at position without knowledge of previous key
+
+  @return
+  @retval 0  ok
+  @retval 1  error
+*/
+
+static my_bool _ma_get_prev_key(MARIA_KEY *key, MARIA_PAGE *ma_page,
+                                uchar *keypos)
+{
+  uint page_flag, nod_flag;
+  MARIA_KEYDEF *keyinfo= key->keyinfo;
+  DBUG_ENTER("_ma_get_prev_key");
+
+  page_flag= ma_page->flag;
+  nod_flag=  ma_page->node;
+
+  if (! (keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)) &&
+      ! (page_flag & KEYPAGE_FLAG_HAS_TRANSID))
+  {
+    bmove(key->data, keypos - keyinfo->keylength - nod_flag,
+          keyinfo->keylength);
+    key->ref_length= keyinfo->share->rec_reflength;
+    key->data_length= keyinfo->keylength - key->ref_length;
+    key->flag= 0;
+    DBUG_RETURN(0);
+  }
+  else
+  {
+    uchar *page;
+
+    page= ma_page->buff + keyinfo->share->keypage_header + nod_flag;
+    key->data[0]= 0;                            /* safety */
+    DBUG_ASSERT(page != keypos);
+    while (page < keypos)
+    {
+      if (! (*keyinfo->get_key)(key, page_flag, nod_flag, &page))
+      {
+        _ma_set_fatal_error_with_share(keyinfo->share, HA_ERR_CRASHED);
+        DBUG_RETURN(1);
+      }
+    }
+  }
+  DBUG_RETURN(0);
+} /* _ma_get_prev_key */
+
+
+/*
+  @brief Get last key from key-page before 'endpos'
+
+  @note
+  endpos may be either end of buffer or start of a key
+
+  @return
+  @retval pointer to where key starts
+*/
+
+uchar *_ma_get_last_key(MARIA_KEY *key, MARIA_PAGE *ma_page, uchar *endpos)
+{
+  uint page_flag,nod_flag;
+  uchar *lastpos, *page;
+  MARIA_KEYDEF *keyinfo= key->keyinfo;
+  DBUG_ENTER("_ma_get_last_key");
+  DBUG_PRINT("enter",("page: %p  endpos: %p", ma_page->buff,
+                      endpos));
+
+  page_flag= ma_page->flag;
+  nod_flag=  ma_page->node;
+  page= ma_page->buff + keyinfo->share->keypage_header + nod_flag;
+
+  if (! (keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)) &&
+      ! (page_flag & KEYPAGE_FLAG_HAS_TRANSID))
+  {
+    lastpos= endpos-keyinfo->keylength-nod_flag;
+    key->ref_length= keyinfo->share->rec_reflength;
+    key->data_length= keyinfo->keylength - key->ref_length;
+    key->flag= 0;
+    if (lastpos >= page)
+      bmove(key->data, lastpos, keyinfo->keylength + nod_flag);
+  }
+  else
+  {
+    lastpos= page;
+    key->data[0]=0;                             /* safety */
+    while (page < endpos)
+    {
+      lastpos= page;
+      if (!(*keyinfo->get_key)(key, page_flag, nod_flag, &page))
+      {
+        DBUG_PRINT("error",("Couldn't find last key:  page: %p",
+                            page));
+        _ma_set_fatal_error_with_share(keyinfo->share, HA_ERR_CRASHED);
+        DBUG_RETURN(0);
+      }
+    }
+  }
+  DBUG_PRINT("exit",("lastpos: %p  length: %u", lastpos,
+                     key->data_length + key->ref_length));
+  DBUG_RETURN(lastpos);
+} /* _ma_get_last_key */
+
+
+/**
+   Calculate length of unpacked key
+
+   @param info	       Maria handler
+   @param keyinfo      key handler
+   @param key	       data for key
+
+   @notes
+     This function is very seldom used.  It's mainly used for debugging
+     or when calculating a key length from a stored key in batch insert.
+
+     This function does *NOT* calculate length of transid size!
+     This function can't be used against a prefix packed key on a page
+
+   @return
+   @retval total length for key
+*/
+
+uint _ma_keylength(MARIA_KEYDEF *keyinfo, const uchar *key)
+{
+  reg1 HA_KEYSEG *keyseg;
+  const 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);
+} /* _ma_keylength */
+
+
+/*
+  Calculate length of part key.
+
+  Used in maria_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 _ma_keylength_part(MARIA_KEYDEF *keyinfo, register const uchar *key,
+			HA_KEYSEG *end)
+{
+  reg1 HA_KEYSEG *keyseg;
+  const 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);
+}
+
+
+/*
+  Find next/previous record with same key
+
+  WARNING
+    This can't be used when database is touched after last read
+*/
+
+int _ma_search_next(register MARIA_HA *info, MARIA_KEY *key,
+                    uint32 nextflag, my_off_t pos)
+{
+  int error;
+  uchar lastkey[MARIA_MAX_KEY_BUFF];
+  MARIA_KEYDEF *keyinfo= key->keyinfo;
+  MARIA_KEY tmp_key;
+  MARIA_PAGE page;
+  DBUG_ENTER("_ma_search_next");
+  DBUG_PRINT("enter",("nextflag: %u  lastpos: %lu  int_keypos:%p  page_changed %d  keyread_buff_used: %d",
+                      nextflag, (ulong) info->cur_row.lastpos,
+                      info->int_keypos,
+                      info->page_changed, info->keyread_buff_used));
+  DBUG_EXECUTE("key", _ma_print_key(DBUG_FILE, key););
+
+  /*
+    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->keyread_buff_used)))
+    DBUG_RETURN(_ma_search(info, key, nextflag | SEARCH_SAVE_BUFF,
+                           pos));
+
+  if (info->keyread_buff_used)
+  {
+    if (_ma_fetch_keypage(&page, info, keyinfo, info->last_search_keypage,
+                          PAGECACHE_LOCK_LEFT_UNLOCKED,
+                          DFLT_INIT_HITS, info->keyread_buff, 0))
+      DBUG_RETURN(-1);
+    info->keyread_buff_used=0;
+  }
+  else
+  {
+    /* Last used buffer is in info->keyread_buff */
+    /* Todo:  Add info->keyread_page to keep track of this */
+    _ma_page_setup(&page, info, keyinfo, 0, info->keyread_buff);
+  }
+
+  tmp_key.data=   lastkey;
+  tmp_key.keyinfo= keyinfo;
+
+  if (nextflag & SEARCH_BIGGER)                                 /* Next key */
+  {
+    if (page.node)
+    {
+      my_off_t tmp_pos= _ma_kpos(page.node, info->int_keypos);
+
+      if ((error= _ma_search(info, key, nextflag | SEARCH_SAVE_BUFF,
+                             tmp_pos)) <=0)
+        DBUG_RETURN(error);
+    }
+    if (keyinfo->flag & (HA_PACK_KEY | HA_BINARY_PACK_KEY) &&
+        info->last_key.data != key->data)
+      memcpy(info->last_key.data, key->data,
+             key->data_length + key->ref_length);
+    if (!(*keyinfo->get_key)(&info->last_key, page.flag, page.node,
+                             &info->int_keypos))
+      DBUG_RETURN(-1);
+  }
+  else                                                  /* Previous key */
+  {
+    /* Find start of previous key */
+    info->int_keypos= _ma_get_last_key(&tmp_key, &page, info->int_keypos);
+    if (!info->int_keypos)
+      DBUG_RETURN(-1);
+    if (info->int_keypos == info->keyread_buff + info->s->keypage_header)
+    {
+      /* Previous key was first key, read key before this one */
+      DBUG_RETURN(_ma_search(info, key, nextflag | SEARCH_SAVE_BUFF,
+                             pos));
+    }
+    if (page.node &&
+        (error= _ma_search(info, key, nextflag | SEARCH_SAVE_BUFF,
+                           _ma_kpos(page.node,info->int_keypos))) <= 0)
+      DBUG_RETURN(error);
+
+    /* QQ: We should be able to optimize away the following call */
+    if (! _ma_get_last_key(&info->last_key, &page, info->int_keypos))
+      DBUG_RETURN(-1);
+  }
+  info->cur_row.lastpos= _ma_row_pos_from_key(&info->last_key);
+  info->cur_row.trid=    _ma_trid_from_key(&info->last_key);
+  DBUG_PRINT("exit",("found key at %lu",(ulong) info->cur_row.lastpos));
+  DBUG_RETURN(0);
+} /* _ma_search_next */
+
+
+/**
+  Search after position for the first row in an index
+
+  @return
+  Found row is stored in info->cur_row.lastpos
+*/
+
+int _ma_search_first(MARIA_HA *info, MARIA_KEYDEF *keyinfo,
+                     my_off_t pos)
+{
+  uchar *first_pos;
+  MARIA_PAGE page;
+  MARIA_SHARE *share= info->s;
+  DBUG_ENTER("_ma_search_first");
+
+  if (pos == HA_OFFSET_ERROR)
+  {
+    my_errno=HA_ERR_KEY_NOT_FOUND;
+    info->cur_row.lastpos= HA_OFFSET_ERROR;
+    DBUG_RETURN(-1);
+  }
+
+  do
+  {
+    if (_ma_fetch_keypage(&page, info, keyinfo, pos,
+                          PAGECACHE_LOCK_LEFT_UNLOCKED,
+                          DFLT_INIT_HITS, info->keyread_buff, 0))
+    {
+      info->cur_row.lastpos= HA_OFFSET_ERROR;
+      DBUG_RETURN(-1);
+    }
+    first_pos= page.buff + share->keypage_header + page.node;
+  } while ((pos= _ma_kpos(page.node, first_pos)) != HA_OFFSET_ERROR);
+
+  if (!(*keyinfo->get_key)(&info->last_key, page.flag, page.node, &first_pos))
+    DBUG_RETURN(-1);                            /* Crashed */
+
+  info->int_keypos=   first_pos;
+  info->int_maxpos=   (page.buff + page.size -1);
+  info->int_nod_flag= page.node;
+  info->int_keytree_version= keyinfo->version;
+  info->last_search_keypage= info->last_keypage;
+  info->page_changed=info->keyread_buff_used=0;
+  info->cur_row.lastpos= _ma_row_pos_from_key(&info->last_key);
+  info->cur_row.trid=    _ma_trid_from_key(&info->last_key);
+
+  DBUG_PRINT("exit",("found key at %lu", (ulong) info->cur_row.lastpos));
+  DBUG_RETURN(0);
+} /* _ma_search_first */
+
+
+/**
+   Search after position for the last row in an index
+
+  @return
+  Found row is stored in info->cur_row.lastpos
+*/
+
+int _ma_search_last(MARIA_HA *info, MARIA_KEYDEF *keyinfo,
+                    my_off_t pos)
+{
+  uchar *end_of_page;
+  MARIA_PAGE page;
+  DBUG_ENTER("_ma_search_last");
+
+  if (pos == HA_OFFSET_ERROR)
+  {
+    my_errno=HA_ERR_KEY_NOT_FOUND;                      /* Didn't find key */
+    info->cur_row.lastpos= HA_OFFSET_ERROR;
+    DBUG_RETURN(-1);
+  }
+
+  do
+  {
+    if (_ma_fetch_keypage(&page, info, keyinfo, pos,
+                          PAGECACHE_LOCK_LEFT_UNLOCKED,
+                          DFLT_INIT_HITS, info->keyread_buff, 0))
+    {
+      info->cur_row.lastpos= HA_OFFSET_ERROR;
+      DBUG_RETURN(-1);
+    }
+    end_of_page= page.buff + page.size;
+  } while ((pos= _ma_kpos(page.node, end_of_page)) != HA_OFFSET_ERROR);
+
+  if (!_ma_get_last_key(&info->last_key, &page, end_of_page))
+    DBUG_RETURN(-1);
+  info->cur_row.lastpos= _ma_row_pos_from_key(&info->last_key);
+  info->cur_row.trid=    _ma_trid_from_key(&info->last_key);
+  info->int_keypos=      info->int_maxpos= end_of_page;
+  info->int_nod_flag=    page.node;
+  info->int_keytree_version= keyinfo->version;
+  info->last_search_keypage= info->last_keypage;
+  info->page_changed=info->keyread_buff_used=0;
+
+  DBUG_PRINT("exit",("found key at %lu",(ulong) info->cur_row.lastpos));
+  DBUG_RETURN(0);
+} /* _ma_search_last */
+
+
+
+/****************************************************************************
+**
+** Functions to store and pack a key in a page
+**
+** maria_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
+_ma_calc_static_key_length(const MARIA_KEY *key, uint nod_flag,
+                           uchar *next_pos  __attribute__((unused)),
+                           uchar *org_key  __attribute__((unused)),
+                           uchar *prev_key __attribute__((unused)),
+                           MARIA_KEY_PARAM *s_temp)
+{
+  s_temp->key= key->data;
+  return (int) (s_temp->move_length= key->data_length + key->ref_length +
+                nod_flag);
+}
+
+/* Variable length key */
+
+int
+_ma_calc_var_key_length(const MARIA_KEY *key, uint nod_flag,
+                        uchar *next_pos  __attribute__((unused)),
+                        uchar *org_key  __attribute__((unused)),
+                        uchar *prev_key __attribute__((unused)),
+                        MARIA_KEY_PARAM *s_temp)
+{
+  s_temp->key= key->data;
+  return (int) (s_temp->move_length= key->data_length + key->ref_length +
+                nod_flag);
+}
+
+/**
+   @brief Calc length needed to store prefixed compressed keys
+
+  @info
+    Variable length first segment which is prefix compressed
+    (maria_chk reports 'packed + stripped')
+
+    Keys are compressed the following way:
+
+    If the max length of first key segment <= 127 bytes the prefix is
+    1 uchar 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
+    [data_length]  data bytes ('length' bytes)
+    next-key-seg   Next key segments
+
+    If the first segment can have NULL:
+       If key was packed
+         data_length is length of rest of key
+       If key was not packed
+         The data_length is 0 for NULLS and 1+data_length for not null columns
+*/
+
+int
+_ma_calc_var_pack_key_length(const MARIA_KEY *int_key, uint nod_flag,
+                             uchar *next_key, uchar *org_key, uchar *prev_key,
+                             MARIA_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;
+  const uchar *key, *start, *end, *key_end;
+  const uchar *sort_order;
+  my_bool same_length;
+  MARIA_KEYDEF *keyinfo= int_key->keyinfo;
+
+  key= int_key->data;
+  length_pack=s_temp->ref_length=s_temp->n_ref_length=s_temp->n_length=0;
+  same_length=0; keyseg=keyinfo->seg;
+  key_length= int_key->data_length + int_key->ref_length + 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->move_length= 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 _ma_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 (s_temp->move_length= (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 s_temp->move_length= ((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 s_temp->move_length= ((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 (s_temp->move_length= 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 (s_temp->move_length= length);
+}
+
+
+/* Length of key which is prefix compressed */
+
+int _ma_calc_bin_pack_key_length(const MARIA_KEY *int_key,
+                                 uint nod_flag,
+                                 uchar *next_key,
+                                 uchar *org_key, uchar *prev_key,
+                                 MARIA_KEY_PARAM *s_temp)
+{
+  uint length,key_length,ref_length;
+  const uchar *key= int_key->data;
+
+  s_temp->totlength= key_length= (int_key->data_length + int_key->ref_length+
+                                  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 maria_chk, we
+      have to guard against the case where keys may be identical
+    */
+    const 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)
+    {
+      const 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 s_temp->move_length= ((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 (s_temp->move_length= length);  /* Can't pack next key */
+    }
+    s_temp->n_ref_length=ref_length;
+    return s_temp->move_length= (int) (length-(ref_length - next_length) -
+                                       next_length_pack +
+                                       get_pack_length(ref_length));
+  }
+  return (s_temp->move_length= (int) length);
+}
+
+
+/*
+** store a key packed with _ma_calc_xxx_key_length in page-buffert
+*/
+
+/* store key without compression */
+
+void _ma_store_static_key(MARIA_KEYDEF *keyinfo __attribute__((unused)),
+                          register uchar *key_pos,
+                          register MARIA_KEY_PARAM *s_temp)
+{
+  memcpy(key_pos, s_temp->key,(size_t) s_temp->move_length);
+  s_temp->changed_length= s_temp->move_length;
+}
+
+
+/* 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 _ma_store_var_pack_key(MARIA_KEYDEF *keyinfo  __attribute__((unused)),
+                            register uchar *key_pos,
+                            register MARIA_KEY_PARAM *s_temp)
+{
+  uint length;
+  uchar *org_key_pos= 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(key_pos, s_temp->key,
+        (length= s_temp->totlength - (uint) (key_pos-org_key_pos)));
+
+  key_pos+= length;
+
+  if (!s_temp->next_key_pos)                    /* No following key */
+    goto end;
+
+  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);
+    key_pos+= 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)
+    {
+      /* Not identical key */
+      store_key_length_inc(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);
+  }
+
+end:
+  s_temp->changed_length= (uint) (key_pos - org_key_pos);
+}
+
+
+/* variable length key with prefix compression */
+
+void _ma_store_bin_pack_key(MARIA_KEYDEF *keyinfo  __attribute__((unused)),
+                            register uchar *key_pos,
+                            register MARIA_KEY_PARAM *s_temp)
+{
+  uchar *org_key_pos= key_pos;
+  size_t length= s_temp->totlength - s_temp->ref_length;
+
+  store_key_length_inc(key_pos,s_temp->ref_length);
+  memcpy(key_pos, s_temp->key+s_temp->ref_length, length);
+  key_pos+= length;
+
+  if (s_temp->next_key_pos)
+  {
+    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);
+      key_pos+= s_temp->prev_length;
+    }
+  }
+  s_temp->changed_length= (uint) (key_pos - org_key_pos);
+}