LTP GCOV extension - code coverage report
Current view: directory - storage/maria - ma_search.c
Test: maria-mtr.html
Date: 2009-03-04 Instrumented lines: 958
Code covered: 0.0 % Executed lines: 0

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

Generated by: LTP GCOV extension version 1.4