LTP GCOV extension - code coverage report
Current view: directory - storage/maria - ma_search.c
Test: mtr_and_unit.info
Date: 2009-03-05 Instrumented lines: 958
Code covered: 80.7 % Executed lines: 773

       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          279350 : {
      29          279350 :   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          279350 :   if (info->lastinx != inx)             /* Index changed */
      35                 :   {
      36             486 :     info->lastinx = inx;
      37             486 :     info->page_changed=1;
      38             486 :     info->update= ((info->update & (HA_STATE_CHANGED | HA_STATE_ROW_CHANGED)) |
      39                 :                    HA_STATE_NEXT_FOUND | HA_STATE_PREV_FOUND);
      40                 :   }
      41          279350 :   if (info->opt_flag & WRITE_CACHE_USED && flush_io_cache(&info->rec_cache))
      42               0 :     return(-1);
      43          279350 :   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          362154 : {
      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          362154 :   MARIA_KEYDEF *keyinfo= key->keyinfo;
      68                 :   MARIA_PAGE page;
      69          362154 :   DBUG_ENTER("_ma_search");
      70          362154 :   DBUG_PRINT("enter",("pos: %lu  nextflag: %u  lastpos: %lu",
      71                 :                       (ulong) pos, nextflag, (ulong) info->cur_row.lastpos));
      72          362154 :   DBUG_EXECUTE("key", _ma_print_key(DBUG_FILE, key););
      73                 : 
      74          362154 :   if (pos == HA_OFFSET_ERROR)
      75                 :   {
      76            4920 :     my_errno=HA_ERR_KEY_NOT_FOUND;                      /* Didn't find key */
      77            4920 :     info->cur_row.lastpos= HA_OFFSET_ERROR;
      78            4920 :     if (!(nextflag & (SEARCH_SMALLER | SEARCH_BIGGER | SEARCH_LAST)))
      79            3952 :       DBUG_RETURN(-1);                          /* Not found ; return error */
      80             968 :     DBUG_RETURN(1);                             /* Search at upper levels */
      81                 :   }
      82                 : 
      83          357234 :   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          357234 :     goto err;
      88          357234 :   DBUG_DUMP("page", page.buff, page.size);
      89                 : 
      90          357234 :   flag= (*keyinfo->bin_search)(key, &page, nextflag, &keypos, lastkey,
      91                 :                                &last_key_not_used);
      92          357234 :   if (flag == MARIA_FOUND_WRONG_KEY)
      93               0 :     DBUG_RETURN(-1);
      94          357234 :   page_flag=   page.flag;
      95          357234 :   used_length= page.size;
      96          357234 :   nod_flag=    page.node;
      97          357234 :   maxpos=      page.buff + used_length -1;
      98                 : 
      99          357234 :   if (flag)
     100                 :   {
     101          128196 :     if ((error= _ma_search(info, key, nextflag,
     102                 :                           _ma_kpos(nod_flag,keypos))) <= 0)
     103          126830 :       DBUG_RETURN(error);
     104                 : 
     105            1366 :     if (flag >0)
     106                 :     {
     107             844 :       if (nextflag & (SEARCH_SMALLER | SEARCH_LAST) &&
     108                 :           keypos == page.buff + info->s->keypage_header + nod_flag)
     109             361 :         DBUG_RETURN(1);                                 /* Bigger than key */
     110                 :     }
     111             522 :     else if (nextflag & SEARCH_BIGGER && keypos >= maxpos)
     112             376 :       DBUG_RETURN(1);                                   /* Smaller than key */
     113                 :   }
     114                 :   else
     115                 :   {
     116                 :     /* Found matching key */
     117          229038 :     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             167 :       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              97 :         DBUG_RETURN(error);
     126              70 :       info->last_keypage= HA_OFFSET_ERROR;              /* Buffer not in mem */
     127                 :     }
     128                 :   }
     129          229570 :   if (pos != info->last_keypage)
     130                 :   {
     131             256 :     uchar *old_buff= page.buff;
     132             256 :     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             256 :       goto err;
     137                 :     /* Restore position if page buffer moved */
     138             256 :     keypos= page.buff + (keypos - old_buff);
     139             256 :     maxpos= page.buff + (maxpos - old_buff);
     140                 :   }
     141                 : 
     142          229570 :   info->last_key.keyinfo= keyinfo;
     143          229570 :   if ((nextflag & (SEARCH_SMALLER | SEARCH_LAST)) && flag != 0)
     144                 :   {
     145                 :     uint not_used[2];
     146             276 :     if (_ma_get_prev_key(&info->last_key, &page, keypos))
     147             276 :       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             276 :     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          229294 :     info->last_key.data= lastkey;
     166                 :     /* Get key value (if not packed key) and position after key */
     167          229294 :     if (!(*keyinfo->get_key)(&info->last_key, page_flag, nod_flag, &keypos))
     168          229294 :       goto err;
     169          229294 :     memcpy(info->lastkey_buff, lastkey,
     170                 :            info->last_key.data_length + info->last_key.ref_length);
     171          229294 :     info->last_key.data= info->lastkey_buff;
     172                 :   }
     173          229570 :   info->cur_row.lastpos= _ma_row_pos_from_key(&info->last_key);
     174          229570 :   info->cur_row.trid=    _ma_trid_from_key(&info->last_key);
     175                 :   /* Save position for a possible read next / previous */
     176          229570 :   info->int_keypos= info->keyread_buff + (keypos - page.buff);
     177          229570 :   info->int_maxpos= info->keyread_buff + (maxpos - page.buff);
     178          229570 :   info->int_nod_flag=nod_flag;
     179          229570 :   info->int_keytree_version=keyinfo->version;
     180          229570 :   info->last_search_keypage=info->last_keypage;
     181          229570 :   info->page_changed=0;
     182                 :   /* Set marker that buffer was used (Marker for mi_search_next()) */
     183          229570 :   info->keyread_buff_used= (info->keyread_buff != page.buff);
     184                 : 
     185          229570 :   DBUG_PRINT("exit",("found key at %lu",(ulong) info->cur_row.lastpos));
     186          229570 :   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         2756438 : {
     221                 :   int flag;
     222                 :   uint page_flag;
     223                 :   uint start, mid, end, save_end, totlength, nod_flag;
     224                 :   uint not_used[2];
     225         2756438 :   MARIA_KEYDEF *keyinfo= key->keyinfo;
     226         2756438 :   MARIA_SHARE *share=  keyinfo->share;
     227                 :   uchar *page;
     228         2756438 :   DBUG_ENTER("_ma_bin_search");
     229                 : 
     230         2756438 :   LINT_INIT(flag);
     231                 : 
     232         2756438 :   page_flag= ma_page->flag;
     233         2756438 :   if (page_flag & KEYPAGE_FLAG_HAS_TRANSID)
     234                 :   {
     235                 :     /* Keys have varying length, can't use binary search */
     236          568994 :     DBUG_RETURN(_ma_seq_search(key, ma_page, comp_flag, ret_pos, buff,
     237                 :                                last_key));
     238                 :   }
     239                 : 
     240         2187444 :   nod_flag=    ma_page->node;
     241         2187444 :   totlength= keyinfo->keylength + nod_flag;
     242         2187444 :   DBUG_ASSERT(ma_page->size >= share->keypage_header + nod_flag + totlength);
     243                 : 
     244         2187444 :   start=0;
     245         2187444 :   mid=1;
     246         2187444 :   save_end= end= ((ma_page->size - nod_flag - share->keypage_header) /
     247                 :                   totlength-1);
     248         2187444 :   DBUG_PRINT("test",("page_length: %u  end: %u", ma_page->size, end));
     249         2187444 :   page= ma_page->buff + share->keypage_header + nod_flag;
     250                 : 
     251        16532860 :   while (start != end)
     252                 :   {
     253        12157972 :     mid= (start+end)/2;
     254        12157972 :     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         6266676 :       end=mid;
     259                 :     else
     260         5891296 :       start=mid+1;
     261                 :   }
     262         2187444 :   if (mid != start)
     263         1457084 :     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         2187444 :   if (flag < 0)
     267          255741 :     start++;                    /* point at next, bigger key */
     268         2187444 :   *ret_pos= (page + (uint) start * totlength);
     269         2187444 :   *last_key= end == save_end;
     270         2187444 :   DBUG_PRINT("exit",("flag: %d  keypos: %d",flag,start));
     271         2187444 :   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          959565 : {
     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          959565 :   MARIA_KEYDEF *keyinfo= key->keyinfo;
     313          959565 :   MARIA_SHARE *share= keyinfo->share;
     314                 :   MARIA_KEY tmp_key;
     315          959565 :   DBUG_ENTER("_ma_seq_search");
     316                 : 
     317          959565 :   LINT_INIT(flag);
     318          959565 :   LINT_INIT(length);
     319                 : 
     320          959565 :   page_flag= ma_page->flag;
     321          959565 :   nod_flag=  ma_page->node;
     322          959565 :   page=      ma_page->buff;
     323          959565 :   end= page + ma_page->size;
     324          959565 :   page+= share->keypage_header + nod_flag;
     325          959565 :   *ret_pos= page;
     326          959565 :   t_buff[0]=0;                                  /* Avoid bugs */
     327                 : 
     328          959565 :   tmp_key.data= t_buff;
     329          959565 :   tmp_key.keyinfo= keyinfo;
     330       216882427 :   while (page < end)
     331                 :   {
     332       215852866 :     length=(*keyinfo->get_key)(&tmp_key, page_flag, nod_flag, &page);
     333       215852866 :     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       215852866 :     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       214963297 :       break;
     347       214963297 :     DBUG_PRINT("loop_extra",("page: 0x%lx  key: '%s'  flag: %d",
     348                 :                              (long) page, t_buff, flag));
     349       214963297 :     memcpy(buff,t_buff,length);
     350       214963297 :     *ret_pos=page;
     351                 :   }
     352          959565 :   if (flag == 0)
     353          382057 :     memcpy(buff,t_buff,length);                 /* Result is first key */
     354          959565 :   *last_key= page == end;
     355          959565 :   DBUG_PRINT("exit",("flag: %d  ret_pos: 0x%lx", flag, (long) *ret_pos));
     356          959565 :   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         1528645 : {
     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         1528645 :   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         1528645 :   uchar tt_buff[MARIA_MAX_KEY_BUFF+2], *t_buff=tt_buff+2;
     386                 :   uchar  *saved_to;
     387                 :   const uchar *kseg;
     388         1528645 :   uint  saved_length=0, saved_prefix_len=0;
     389                 :   uint  length_pack;
     390         1528645 :   MARIA_KEYDEF *keyinfo= key->keyinfo;
     391         1528645 :   MARIA_SHARE *share= keyinfo->share;
     392         1528645 :   uchar *sort_order= keyinfo->seg->charset->sort_order;
     393         1528645 :   DBUG_ENTER("_ma_prefix_search");
     394                 : 
     395         1528645 :   LINT_INIT(length);
     396         1528645 :   LINT_INIT(prefix_len);
     397         1528645 :   LINT_INIT(seg_len_pack);
     398         1528645 :   LINT_INIT(saved_from);
     399         1528645 :   LINT_INIT(saved_to);
     400         1528645 :   LINT_INIT(saved_vseg);
     401                 : 
     402         1528645 :   t_buff[0]=0;                                  /* Avoid bugs */
     403         1528645 :   page_flag=   ma_page->flag;
     404         1528645 :   nod_flag=    ma_page->node;
     405         1528645 :   page_flag&= KEYPAGE_FLAG_HAS_TRANSID;         /* For faster test in loop */
     406         1528645 :   page= ma_page->buff;
     407         1528645 :   end= page + ma_page->size;
     408         1528645 :   page+= share->keypage_header + nod_flag;
     409         1528645 :   *ret_pos= page;
     410         1528645 :   kseg= key->data;
     411                 : 
     412         1528645 :   get_key_pack_length(kseg_len, length_pack, kseg);
     413         1528645 :   key_len_skip=length_pack+kseg_len;
     414         1528645 :   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         1528645 :   cmplen= ((key_len_left>=0) ? kseg_len :
     417                 :            (key->data_length + key->ref_length - length_pack));
     418         1528645 :   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         1528645 :   matched=0;  /* how many char's from prefix were alredy matched */
     434         1528645 :   len=0;      /* length of previous key unpacked */
     435                 : 
     436       325883231 :   while (page < end)
     437                 :   {
     438       324175748 :     uint packed= *page & 128;
     439                 :     uint key_flag;
     440                 : 
     441       324175748 :     vseg= page;
     442       324175748 :     if (keyinfo->seg->length >= 127)
     443                 :     {
     444            5370 :       suffix_len=mi_uint2korr(vseg) & 32767;
     445            5370 :       vseg+=2;
     446                 :     }
     447                 :     else
     448       324170378 :       suffix_len= *vseg++ & 127;
     449                 : 
     450       324175748 :     if (packed)
     451                 :     {
     452       307413010 :       if (suffix_len == 0)
     453                 :       {
     454                 :         /* == 0x80 or 0x8000, same key, prefix length == old key length. */
     455       214358091 :         prefix_len=len;
     456                 :       }
     457                 :       else
     458                 :       {
     459                 :         /* > 0x80 or 0x8000, this is prefix lgt, packed suffix lgt follows. */
     460        93054919 :         prefix_len=suffix_len;
     461        93054919 :         get_key_length(suffix_len,vseg);
     462                 :       }
     463                 :     }
     464                 :     else
     465                 :     {
     466                 :       /* Not packed. No prefix used from last key. */
     467        16762738 :       prefix_len=0;
     468                 :     }
     469                 : 
     470       324175748 :     len=prefix_len+suffix_len;
     471       324175748 :     seg_len_pack=get_pack_length(len);
     472       324175748 :     t_buff=tt_buff+3-seg_len_pack;
     473       324175748 :     store_key_length(t_buff,len);
     474                 : 
     475       324175748 :     if (prefix_len > saved_prefix_len)
     476        63852140 :       memcpy(t_buff+seg_len_pack+saved_prefix_len,saved_vseg,
     477                 :              prefix_len-saved_prefix_len);
     478       324175748 :     saved_vseg=vseg;
     479       324175748 :     saved_prefix_len=prefix_len;
     480                 : 
     481       324175748 :     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       324175748 :       uchar *from= vseg+suffix_len;
     486                 :       HA_KEYSEG *keyseg;
     487                 : 
     488       324175748 :       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       324175748 :       from+= keyseg->length;
     505       324175748 :       key_flag=0;
     506                 : 
     507       324175748 :       if (page_flag && key_has_transid(from-1))
     508                 :       {
     509        56828925 :         from+= transid_packed_length(from);
     510        56828925 :         key_flag= SEARCH_PAGE_KEY_HAS_TRANSID;
     511                 :       }
     512       324175748 :       page= from + nod_flag;
     513       324175748 :       length= (uint) (from-vseg);
     514                 :     }
     515                 : 
     516       324175748 :     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       324175748 :     if (matched >= prefix_len)
     527                 :     {
     528                 :       /* We have to compare. But we can still skip part of the key */
     529                 :       uint  left;
     530        41385532 :       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        41385532 :       left= ((len <= cmplen) ? suffix_len :
     537                 :              ((prefix_len < cmplen) ? cmplen - prefix_len : 0));
     538                 : 
     539        41385532 :       matched=prefix_len+left;
     540                 : 
     541        41385532 :       if (sort_order)
     542                 :       {
     543        55140642 :         for (my_flag=0;left;left--)
     544        22585855 :           if ((my_flag= (int) sort_order[*vseg++] - (int) sort_order[*k++]))
     545        13755110 :             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        41385532 :       if (my_flag>0)      /* mismatch */
     555        40570621 :         break;
     556        40570621 :       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        32554787 :         if (len < cmplen)
     569                 :         {
     570        13451627 :           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        13451627 :             const uchar *k_end= k+ (cmplen - len);
     578        13451627 :             for ( ; k < k_end && *k == ' '; k++) ;
     579        13451627 :             if (k == k_end)
     580        13451627 :               goto cmp_rest;            /* should never happen */
     581        13451627 :             if ((uchar) *k < (uchar) ' ')
     582                 :             {
     583               0 :               my_flag= 1;               /* Compared string is smaller */
     584               0 :               break;
     585                 :             }
     586        13451627 :             my_flag= -1;                /* Continue searching */
     587                 :           }
     588                 :         }
     589        19103160 :         else if (len > cmplen)
     590                 :         {
     591                 :           uchar *vseg_end;
     592           16885 :           if ((nextflag & SEARCH_PREFIX) && key_len_left == 0)
     593           16885 :             goto fix_flag;
     594                 : 
     595                 :           /* We have to compare k and vseg as if they were space extended */
     596           16885 :           for (vseg_end= vseg + (len-cmplen) ;
     597           84335 :                vseg < vseg_end && *vseg == (uchar) ' ';
     598           50565 :                vseg++, matched++) ;
     599           16885 :           DBUG_ASSERT(vseg < vseg_end);
     600                 : 
     601           16885 :           if ((uchar) *vseg > (uchar) ' ')
     602                 :           {
     603           16885 :             my_flag= 1;                 /* Compared string is smaller */
     604           16885 :             break;
     605                 :           }
     606               0 :           my_flag= -1;                  /* Continue searching */
     607                 :         }
     608                 :         else
     609                 :         {
     610        19086275 :       cmp_rest:
     611        19086275 :           if (key_len_left>0)
     612                 :           {
     613                 :             uint not_used[2];
     614        19028611 :             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           57664 :         fix_flag:
     626           57664 :             DBUG_ASSERT(flag <= 0);
     627           57664 :             if (nextflag & (SEARCH_NO_FIND | SEARCH_LAST))
     628            5606 :               flag=(nextflag & (SEARCH_BIGGER | SEARCH_LAST)) ? -1 : 1;
     629           57664 :             if (flag>=0)
     630        40035725 :               break;
     631                 :           }
     632                 :         }
     633                 :       }
     634        40035725 :       matched-=left;
     635                 :     }
     636                 :     /* else (matched < prefix_len) ---> do nothing. */
     637                 : 
     638       322825941 :     memcpy(buff,t_buff,saved_length=seg_len_pack+prefix_len);
     639       322825941 :     saved_to= buff+saved_length;
     640       322825941 :     saved_from= saved_vseg;
     641       322825941 :     saved_length=length;
     642       322825941 :     *ret_pos=page;
     643                 :   }
     644         1528645 :   if (my_flag)
     645          995925 :     flag=(keyinfo->seg->flag & HA_REVERSE_SORT) ? -my_flag : my_flag;
     646         1528645 :   if (flag == 0)
     647                 :   {
     648          477058 :     memcpy(buff,t_buff,saved_length=seg_len_pack+prefix_len);
     649          477058 :     saved_to= buff+saved_length;
     650          477058 :     saved_from= saved_vseg;
     651          477058 :     saved_length=length;
     652                 :   }
     653         1528645 :   if (saved_length)
     654         1356821 :     memcpy(saved_to, saved_from, saved_length);
     655                 : 
     656         1528645 :   *last_key= page == end;
     657                 : 
     658         1528645 :   DBUG_PRINT("exit",("flag: %d  ret_pos: 0x%lx", flag, (long) *ret_pos));
     659         1528645 :   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         3124347 : {
     667         3124347 :   after_key-=nod_flag;
     668         3124347 :   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         1198534 :     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           95703 :     return ((my_off_t) mi_uint4korr(after_key))*maria_block_size;
     686                 :   case 3:
     687          488461 :     return ((my_off_t) mi_uint3korr(after_key))*maria_block_size;
     688                 :   case 2:
     689            2545 :     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         1339104 :     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            9924 : {
     703            9924 :   pos/=maria_block_size;
     704            9924 :   switch (info->s->base.key_reflength) {
     705                 : #if SIZEOF_OFF_T > 4
     706               0 :   case 7: mi_int7store(buff,pos); break;
     707            7211 :   case 6: mi_int6store(buff,pos); break;
     708             207 :   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             487 :   case 4: mi_int4store(buff,pos); break;
     718            1930 :   case 3: mi_int3store(buff,pos); break;
     719              89 :   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          713410 : {
     730                 :   my_off_t pos;
     731          713410 :   const uchar *after_key= key->data + key->data_length;
     732          713410 :   MARIA_SHARE *share= key->keyinfo->share;
     733          713410 :   switch (share->rec_reflength) {
     734                 : #if SIZEOF_OFF_T > 4
     735               0 :   case 8:  pos= (my_off_t) mi_uint8korr(after_key);  break;
     736             131 :   case 7:  pos= (my_off_t) mi_uint7korr(after_key);  break;
     737             524 :   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          698801 :   case 4:  pos= (my_off_t) mi_uint4korr(after_key);  break;
     746             129 :   case 3:  pos= (my_off_t) mi_uint3korr(after_key);  break;
     747           13825 :   case 2:  pos= (my_off_t) mi_uint2korr(after_key);  break;
     748                 :   default:
     749               0 :     pos=0L;                                     /* Shut compiler up */
     750                 :   }
     751          713410 :   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          536588 : {
     766          536588 :   if (!(key->flag & (SEARCH_PAGE_KEY_HAS_TRANSID |
     767                 :                      SEARCH_USER_KEY_HAS_TRANSID)))
     768          461038 :     return 0;
     769           75550 :   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           18331 : {
     779                 :   my_off_t pos;
     780           18331 :   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           17836 :     pos= (my_off_t) mi_uint4korr(ptr);
     812           17836 :     if (pos == (my_off_t) (uint32) ~0L)
     813              42 :       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             495 :     pos= (my_off_t) mi_uint2korr(ptr);
     822             495 :     if (pos == (my_off_t) (1 << 16) -1)
     823               3 :       return HA_OFFSET_ERROR;
     824                 :     break;
     825               0 :   default: abort();                             /* Impossible */
     826                 :   }
     827           18286 :   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         2735548 : {
     835         2735548 :   if (pos != HA_OFFSET_ERROR)
     836         2735519 :     pos= (*share->recpos_to_keypos)(share, pos);
     837                 : 
     838         2735578 :   switch (share->rec_reflength) {
     839                 : #if SIZEOF_OFF_T > 4
     840               0 :   case 8: mi_int8store(buff,pos); break;
     841             640 :   case 7: mi_int7store(buff,pos); break;
     842            2560 :   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         2705863 :   case 4: mi_int4store(buff,pos); break;
     855             330 :   case 3: mi_int3store(buff,pos); break;
     856           26214 :   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          135274 : {
     864          135274 :   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          436289 : {
     870          436289 :   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          611520 : {
     876          611520 :   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          461269 : {
     883                 :   /* We need one bit to store if there is transid's after position */
     884          461269 :   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         1822913 : {
     891         1822913 :   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        75946133 : {
     912        75946133 :   register MARIA_KEYDEF *keyinfo= key->keyinfo;
     913        75946133 :   size_t key_length= keyinfo->keylength;
     914                 : 
     915        75946133 :   key->ref_length=  keyinfo->share->rec_reflength;
     916        75946133 :   key->data_length= key_length - key->ref_length;
     917        75946133 :   key->flag= 0;
     918        75946133 :   if (page_flag & KEYPAGE_FLAG_HAS_TRANSID)
     919                 :   {
     920        75699440 :     uchar *end= *page + keyinfo->keylength;
     921        75699440 :     if (key_has_transid(end-1))
     922                 :     {
     923        42025557 :       uint trans_length= transid_packed_length(end);
     924        42025557 :       key->ref_length+= trans_length;
     925        42025557 :       key_length+= trans_length;
     926        42025557 :       key->flag= SEARCH_PAGE_KEY_HAS_TRANSID;
     927                 :     }
     928                 :   }
     929        75946133 :   key_length+= nod_flag;
     930        75946133 :   memcpy(key->data, *page, key_length);
     931        75946133 :   *page+= key_length;
     932        75946133 :   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           65230 : {
     950           65230 :   page+= key->keyinfo->keylength;
     951           65230 :   if ((page_flag & KEYPAGE_FLAG_HAS_TRANSID) && key_has_transid(page-1))
     952           55474 :     page+= transid_packed_length(page);
     953           65230 :   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        58483483 : {
     974                 :   reg1 HA_KEYSEG *keyseg;
     975        58483483 :   uchar *page= *page_pos;
     976                 :   uint length;
     977        58483483 :   uchar *key= int_key->data;
     978        58483483 :   MARIA_KEYDEF *keyinfo= int_key->keyinfo;
     979                 : 
     980       116966966 :   for (keyseg=keyinfo->seg ; keyseg->type ;keyseg++)
     981                 :   {
     982        58483483 :     if (keyseg->flag & HA_PACK_KEY)
     983                 :     {
     984                 :       /* key with length, packed to previous key */
     985        58303053 :       uchar *start= key;
     986        58303053 :       uint packed= *page & 128,tot_length,rest_length;
     987        58303053 :       if (keyseg->length >= 127)
     988                 :       {
     989            7105 :         length=mi_uint2korr(page) & 32767;
     990            7105 :         page+=2;
     991                 :       }
     992                 :       else
     993        58295948 :         length= *page++ & 127;
     994                 : 
     995        58303053 :       if (packed)
     996                 :       {
     997        58106800 :         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        58106800 :         if (length == 0)                        /* Same key */
    1004                 :         {
    1005        38978870 :           if (keyseg->flag & HA_NULL_PART)
    1006               0 :             *key++=1;                           /* Can't be NULL */
    1007        38978870 :           get_key_length(length,key);
    1008        38978870 :           key+= length;                         /* Same diff_key as prev */
    1009        38978870 :           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        19127930 :         if (keyseg->flag & HA_NULL_PART)
    1022                 :         {
    1023            6420 :           key++;                                /* Skip null marker*/
    1024            6420 :           start++;
    1025                 :         }
    1026                 : 
    1027        19127930 :         get_key_length(rest_length,page);
    1028        19127930 :         tot_length=rest_length+length;
    1029                 : 
    1030                 :         /* If the stored length has changed, we must move the key */
    1031        19127930 :         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        19127930 :         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        19127930 :           store_key_length_inc(key,tot_length);
    1048        19127930 :           key+=length;
    1049                 :         }
    1050        19127930 :         memcpy(key,page,rest_length);
    1051        19127930 :         page+=rest_length;
    1052        19127930 :         key+=rest_length;
    1053        19127930 :         continue;
    1054                 :       }
    1055                 :       else
    1056                 :       {
    1057                 :         /* Key that is not packed against previous key */
    1058          196253 :         if (keyseg->flag & HA_NULL_PART)
    1059                 :         {
    1060            3450 :           if (!length--)                        /* Null part */
    1061                 :           {
    1062             795 :             *key++=0;
    1063             795 :             continue;
    1064                 :           }
    1065            2655 :           *key++=1;                             /* Not null */
    1066                 :         }
    1067                 :       }
    1068          195458 :       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          195458 :       store_key_length_inc(key,length);
    1078                 :     }
    1079                 :     else
    1080                 :     {
    1081          180430 :       if (keyseg->flag & HA_NULL_PART)
    1082                 :       {
    1083          160772 :         if (!(*key++ = *page++))
    1084          163771 :           continue;
    1085                 :       }
    1086          163771 :       if (keyseg->flag &
    1087                 :           (HA_VAR_LENGTH_PART | HA_BLOB_PART | HA_SPACE_PACK))
    1088                 :       {
    1089          106341 :         uchar *tmp=page;
    1090          106341 :         get_key_length(length,tmp);
    1091          106341 :         length+=(uint) (tmp-page);
    1092                 :       }
    1093                 :       else
    1094           57430 :         length=keyseg->length;
    1095                 :     }
    1096          359229 :     memcpy(key, page,(size_t) length);
    1097          359229 :     key+=length;
    1098          359229 :     page+=length;
    1099                 :   }
    1100                 : 
    1101        58483483 :   int_key->data_length= (key - int_key->data);
    1102        58483483 :   int_key->flag= 0;
    1103        58483483 :   length= keyseg->length;
    1104        58483483 :   if (page_flag & KEYPAGE_FLAG_HAS_TRANSID)
    1105                 :   {
    1106        11437379 :     uchar *end= page + length;
    1107        11437379 :     if (key_has_transid(end-1))
    1108                 :     {
    1109        11408693 :       length+= transid_packed_length(end);
    1110        11408693 :       int_key->flag= SEARCH_PAGE_KEY_HAS_TRANSID;
    1111                 :     }
    1112                 :   }
    1113        58483483 :   int_key->ref_length= length;
    1114        58483483 :   length+= nod_flag;
    1115        58483483 :   bmove(key, page, length);
    1116        58483483 :   *page_pos= page+length;
    1117                 : 
    1118        58483483 :   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          346630 : {
    1139                 :   reg1 HA_KEYSEG *keyseg;
    1140          693260 :   for (keyseg= key->keyinfo->seg ; keyseg->type ; keyseg++)
    1141                 :   {
    1142          346630 :     if (keyseg->flag & HA_PACK_KEY)
    1143                 :     {
    1144                 :       /* key with length, packed to previous key */
    1145          345766 :       uint packed= *page & 128, length;
    1146          345766 :       if (keyseg->length >= 127)
    1147                 :       {
    1148               0 :         length= mi_uint2korr(page) & 32767;
    1149               0 :         page+= 2;
    1150                 :       }
    1151                 :       else
    1152          345766 :         length= *page++ & 127;
    1153                 : 
    1154          345766 :       if (packed)
    1155                 :       {
    1156          338364 :         if (length == 0)                        /* Same key */
    1157          128132 :           continue;
    1158          128132 :         get_key_length(length,page);
    1159          128132 :         page+= length;
    1160          128132 :         continue;
    1161                 :       }
    1162            7402 :       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            7402 :       page+= length;
    1171                 :     }
    1172                 :     else
    1173                 :     {
    1174             864 :       if (keyseg->flag & HA_NULL_PART)
    1175             864 :         if (!*page++)
    1176             800 :           continue;
    1177             800 :       if (keyseg->flag & (HA_SPACE_PACK | HA_BLOB_PART | HA_VAR_LENGTH_PART))
    1178                 :       {
    1179                 :         uint length;
    1180             400 :         get_key_length(length,page);
    1181             400 :         page+=length;
    1182                 :       }
    1183                 :       else
    1184             400 :         page+= keyseg->length;
    1185                 :     }
    1186                 :   }
    1187          346630 :   page+= keyseg->length;
    1188          346630 :   if ((page_flag & KEYPAGE_FLAG_HAS_TRANSID) && key_has_transid(page-1))
    1189           64055 :     page+= transid_packed_length(page);
    1190          346630 :   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       149246721 : {
    1199                 :   reg1 HA_KEYSEG *keyseg;
    1200                 :   uchar *page, *page_end, *from, *from_end, *key;
    1201                 :   uint length,tmp;
    1202       149246721 :   MARIA_KEYDEF *keyinfo= int_key->keyinfo;
    1203       149246721 :   DBUG_ENTER("_ma_get_binary_pack_key");
    1204                 : 
    1205       149246721 :   page= *page_pos;
    1206       149246721 :   page_end=page + MARIA_MAX_KEY_BUFF + 1;
    1207       149246721 :   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       149246721 :   get_key_length(length,page);
    1225       149246721 :   if (length)
    1226                 :   {
    1227       148053293 :     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       148053293 :     from= key;
    1239       148053293 :     from_end= key + length;
    1240                 :   }
    1241                 :   else
    1242                 :   {
    1243                 :     /* Key is not packed against prev key, take all from page buffer. */
    1244         1193428 :     from= page;
    1245         1193428 :     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       298493442 :   for (keyseg=keyinfo->seg ; keyseg->type ;keyseg++)
    1256                 :   {
    1257       149246721 :     if (keyseg->flag & HA_NULL_PART)
    1258                 :     {
    1259                 :       /* If prefix is used up, switch to rest. */
    1260           12240 :       if (from == from_end)
    1261                 :       {
    1262               0 :         from=page;
    1263               0 :         from_end=page_end;
    1264                 :       }
    1265           12240 :       if (!(*key++ = *from++))
    1266       149245391 :         continue;                               /* Null part */
    1267                 :     }
    1268       149245391 :     if (keyseg->flag & (HA_VAR_LENGTH_PART | HA_BLOB_PART | HA_SPACE_PACK))
    1269                 :     {
    1270                 :       /* If prefix is used up, switch to rest. */
    1271        19357952 :       if (from == from_end) { from=page;  from_end=page_end; }
    1272                 :       /* Get length of dynamic length key part */
    1273        19357952 :       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       129887439 :       length=keyseg->length;
    1285                 : 
    1286       149245391 :     if ((tmp=(uint) (from_end-from)) <= length)
    1287                 :     {
    1288        18654173 :       key+=tmp;                                 /* Use old key */
    1289        18654173 :       length-=tmp;
    1290        18654173 :       from=page; from_end=page_end;
    1291                 :     }
    1292       149245391 :     DBUG_ASSERT((int) length >= 0);
    1293       149245391 :     DBUG_PRINT("info",("key: 0x%lx  from: 0x%lx  length: %u",
    1294                 :                        (long) key, (long) from, length));
    1295       149245391 :     memmove(key, from, (size_t) length);
    1296       149245391 :     key+=length;
    1297       149245391 :     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       149246721 :   int_key->data_length= (key - int_key->data);
    1305       149246721 :   int_key->ref_length= length= keyseg->length;
    1306       149246721 :   int_key->flag= 0;
    1307       149246721 :   if ((tmp=(uint) (from_end-from)) <= length)
    1308                 :   {
    1309                 :     /* Skip over the last common part of the data */
    1310       129399120 :     key+= tmp;
    1311       129399120 :     length-= tmp;
    1312       129399120 :     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        19847601 :     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       149246721 :   if (page_flag & KEYPAGE_FLAG_HAS_TRANSID)
    1331                 :   {
    1332        26106509 :     uchar *end= from + length;
    1333        26106509 :     if (key_has_transid(end-1))
    1334                 :     {
    1335        26106509 :       uint trans_length= transid_packed_length(end);
    1336        26106509 :       length+= trans_length;
    1337        26106509 :       int_key->ref_length+= trans_length;
    1338        26106509 :       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       149246721 :   memcpy(key, from, length + nod_flag);
    1344       149246721 :   *page_pos= from + length + nod_flag;
    1345                 :   
    1346       149246721 :   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          207165 : {
    1372          207165 :   if (!_ma_get_binary_pack_key(key, page_flag, nod_flag, &page))
    1373               0 :     return 0;
    1374          207165 :   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              63 : {
    1386                 :   uint page_flag, nod_flag;
    1387              63 :   MARIA_KEYDEF *keyinfo= key->keyinfo;
    1388                 :   uchar *page;
    1389              63 :   DBUG_ENTER("_ma_get_key");
    1390                 : 
    1391              63 :   page=       ma_page->buff;
    1392              63 :   page_flag=  ma_page->flag;
    1393              63 :   nod_flag=   ma_page->node;
    1394                 : 
    1395              63 :   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              63 :     page+= keyinfo->share->keypage_header + nod_flag;
    1407              63 :     key->data[0]= 0;                            /* safety */
    1408             333 :     while (page <= keypos)
    1409                 :     {
    1410             207 :       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              63 :   DBUG_PRINT("exit",("page: 0x%lx  length: %u", (long) page,
    1419                 :                      key->data_length + key->ref_length));
    1420              63 :   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             276 : {
    1435                 :   uint page_flag, nod_flag;
    1436             276 :   MARIA_KEYDEF *keyinfo= key->keyinfo;
    1437             276 :   DBUG_ENTER("_ma_get_prev_key");
    1438                 : 
    1439             276 :   page_flag= ma_page->flag;
    1440             276 :   nod_flag=  ma_page->node;
    1441                 : 
    1442             276 :   if (! (keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)) &&
    1443                 :       ! (page_flag & KEYPAGE_FLAG_HAS_TRANSID))
    1444                 :   {
    1445              99 :     bmove(key->data, keypos - keyinfo->keylength - nod_flag,
    1446                 :           keyinfo->keylength);
    1447              99 :     key->ref_length= keyinfo->share->rec_reflength;
    1448              99 :     key->data_length= keyinfo->keylength - key->ref_length;
    1449              99 :     key->flag= 0;
    1450              99 :     DBUG_RETURN(0);
    1451                 :   }
    1452                 :   else
    1453                 :   {
    1454                 :     uchar *page;
    1455                 : 
    1456             177 :     page= ma_page->buff + keyinfo->share->keypage_header + nod_flag;
    1457             177 :     key->data[0]= 0;                            /* safety */
    1458             177 :     DBUG_ASSERT(page != keypos);
    1459           67225 :     while (page < keypos)
    1460                 :     {
    1461           67048 :       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             177 :   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          216192 : {
    1485                 :   uint page_flag,nod_flag;
    1486                 :   uchar *lastpos, *page;
    1487          216192 :   MARIA_KEYDEF *keyinfo= key->keyinfo;
    1488          216192 :   DBUG_ENTER("_ma_get_last_key");
    1489          216192 :   DBUG_PRINT("enter",("page: 0x%lx  endpos: 0x%lx", (long) ma_page->buff,
    1490                 :                       (long) endpos));
    1491                 : 
    1492          216192 :   page_flag= ma_page->flag;
    1493          216192 :   nod_flag=  ma_page->node;
    1494          216192 :   page= ma_page->buff + keyinfo->share->keypage_header + nod_flag;
    1495                 : 
    1496          216192 :   if (! (keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)) &&
    1497                 :       ! (page_flag & KEYPAGE_FLAG_HAS_TRANSID))
    1498                 :   {
    1499           62076 :     lastpos= endpos-keyinfo->keylength-nod_flag;
    1500           62076 :     key->ref_length= keyinfo->share->rec_reflength;
    1501           62076 :     key->data_length= keyinfo->keylength - key->ref_length;
    1502           62076 :     key->flag= 0;
    1503           62076 :     if (lastpos >= page)
    1504           62076 :       bmove(key->data, lastpos, keyinfo->keylength + nod_flag);
    1505                 :   }
    1506                 :   else
    1507                 :   {
    1508          154116 :     lastpos= page;
    1509          154116 :     key->data[0]=0;                             /* safety */
    1510        66312255 :     while (page < endpos)
    1511                 :     {
    1512        66004023 :       lastpos= page;
    1513        66004023 :       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          216192 :   DBUG_PRINT("exit",("lastpos: 0x%lx  length: %u", (ulong) lastpos,
    1524                 :                      key->data_length + key->ref_length));
    1525          216192 :   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          675474 : {
    1549                 :   reg1 HA_KEYSEG *keyseg;
    1550                 :   const uchar *start;
    1551                 : 
    1552          675474 :   if (! (keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)))
    1553           46425 :     return (keyinfo->keylength);
    1554                 : 
    1555          629049 :   start= key;
    1556         1258098 :   for (keyseg=keyinfo->seg ; keyseg->type ; keyseg++)
    1557                 :   {
    1558          629049 :     if (keyseg->flag & HA_NULL_PART)
    1559             575 :       if (!*key++)
    1560          629014 :         continue;
    1561          629014 :     if (keyseg->flag & (HA_SPACE_PACK | HA_BLOB_PART | HA_VAR_LENGTH_PART))
    1562                 :     {
    1563                 :       uint length;
    1564          497803 :       get_key_length(length,key);
    1565          497803 :       key+=length;
    1566                 :     }
    1567                 :     else
    1568          131211 :       key+= keyseg->length;
    1569                 :   }
    1570          629049 :   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           57962 : {
    1585                 :   reg1 HA_KEYSEG *keyseg;
    1586           57962 :   const uchar *start= key;
    1587                 : 
    1588          115924 :   for (keyseg=keyinfo->seg ; keyseg != end ; keyseg++)
    1589                 :   {
    1590           57962 :     if (keyseg->flag & HA_NULL_PART)
    1591            1857 :       if (!*key++)
    1592           57820 :         continue;
    1593           57820 :     if (keyseg->flag & (HA_SPACE_PACK | HA_BLOB_PART | HA_VAR_LENGTH_PART))
    1594                 :     {
    1595                 :       uint length;
    1596           56315 :       get_key_length(length,key);
    1597           56315 :       key+=length;
    1598                 :     }
    1599                 :     else
    1600            1505 :       key+= keyseg->length;
    1601                 :   }
    1602           57962 :   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          201212 : {
    1616                 :   int error;
    1617                 :   uchar lastkey[MARIA_MAX_KEY_BUFF];
    1618          201212 :   MARIA_KEYDEF *keyinfo= key->keyinfo;
    1619                 :   MARIA_KEY tmp_key;
    1620                 :   MARIA_PAGE page;
    1621          201212 :   DBUG_ENTER("_ma_search_next");
    1622          201212 :   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          201212 :   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          201212 :   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             318 :     DBUG_RETURN(_ma_search(info, key, nextflag | SEARCH_SAVE_BUFF,
    1641                 :                            pos));
    1642                 : 
    1643          200894 :   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          200894 :     _ma_page_setup(&page, info, keyinfo, 0, info->keyread_buff);
    1656                 :   }
    1657                 : 
    1658          200894 :   tmp_key.data=   lastkey;
    1659          200894 :   info->last_key.keyinfo= tmp_key.keyinfo= keyinfo;
    1660                 : 
    1661          200894 :   if (nextflag & SEARCH_BIGGER)                                 /* Next key */
    1662                 :   {
    1663          100473 :     if (page.node)
    1664                 :     {
    1665              40 :       my_off_t tmp_pos= _ma_kpos(page.node, info->int_keypos);
    1666                 : 
    1667              40 :       if ((error= _ma_search(info, key, nextflag | SEARCH_SAVE_BUFF,
    1668                 :                              tmp_pos)) <=0)
    1669              40 :         DBUG_RETURN(error);
    1670                 :     }
    1671          100433 :     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          100433 :     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          100421 :     info->int_keypos= _ma_get_last_key(&tmp_key, &page, info->int_keypos);
    1683          100421 :     if (!info->int_keypos)
    1684               0 :       DBUG_RETURN(-1);
    1685          100421 :     if (info->int_keypos == info->keyread_buff + info->s->keypage_header)
    1686                 :     {
    1687                 :       /* Previous key was first key, read key before this one */
    1688             255 :       DBUG_RETURN(_ma_search(info, key, nextflag | SEARCH_SAVE_BUFF,
    1689                 :                              pos));
    1690                 :     }
    1691          100166 :     if (page.node &&
    1692                 :         (error= _ma_search(info, key, nextflag | SEARCH_SAVE_BUFF,
    1693                 :                            _ma_kpos(page.node,info->int_keypos))) <= 0)
    1694              93 :       DBUG_RETURN(error);
    1695                 : 
    1696                 :     /* QQ: We should be able to optimize away the following call */
    1697          100073 :     if (! _ma_get_last_key(&info->last_key, &page, info->int_keypos))
    1698               0 :       DBUG_RETURN(-1);
    1699                 :   }
    1700          200506 :   info->cur_row.lastpos= _ma_row_pos_from_key(&info->last_key);
    1701          200506 :   info->cur_row.trid=    _ma_trid_from_key(&info->last_key);
    1702          200506 :   DBUG_PRINT("exit",("found key at %lu",(ulong) info->cur_row.lastpos));
    1703          200506 :   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             810 : {
    1717                 :   uchar *first_pos;
    1718                 :   MARIA_PAGE page;
    1719             810 :   MARIA_SHARE *share= info->s;
    1720             810 :   DBUG_ENTER("_ma_search_first");
    1721                 : 
    1722             810 :   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            1354 :     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            1354 :     first_pos= page.buff + share->keypage_header + page.node;
    1739            1354 :   } while ((pos= _ma_kpos(page.node, first_pos)) != HA_OFFSET_ERROR);
    1740                 : 
    1741             810 :   info->last_key.keyinfo= keyinfo;
    1742                 : 
    1743             810 :   if (!(*keyinfo->get_key)(&info->last_key, page.flag, page.node, &first_pos))
    1744               0 :     DBUG_RETURN(-1);                            /* Crashed */
    1745                 : 
    1746             810 :   info->int_keypos=   first_pos;
    1747             810 :   info->int_maxpos=   (page.buff + page.size -1);
    1748             810 :   info->int_nod_flag= page.node;
    1749             810 :   info->int_keytree_version= keyinfo->version;
    1750             810 :   info->last_search_keypage= info->last_keypage;
    1751             810 :   info->page_changed=info->keyread_buff_used=0;
    1752             810 :   info->cur_row.lastpos= _ma_row_pos_from_key(&info->last_key);
    1753             810 :   info->cur_row.trid=    _ma_trid_from_key(&info->last_key);
    1754                 : 
    1755             810 :   DBUG_PRINT("exit",("found key at %lu", (ulong) info->cur_row.lastpos));
    1756             810 :   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             739 : {
    1770                 :   uchar *end_of_page;
    1771                 :   MARIA_PAGE page;
    1772             739 :   DBUG_ENTER("_ma_search_last");
    1773                 : 
    1774             739 :   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            1230 :     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            1230 :     end_of_page= page.buff + page.size;
    1791            1230 :   } while ((pos= _ma_kpos(page.node, end_of_page)) != HA_OFFSET_ERROR);
    1792                 : 
    1793             739 :   info->last_key.keyinfo= keyinfo;
    1794                 : 
    1795             739 :   if (!_ma_get_last_key(&info->last_key, &page, end_of_page))
    1796               0 :     DBUG_RETURN(-1);
    1797             739 :   info->cur_row.lastpos= _ma_row_pos_from_key(&info->last_key);
    1798             739 :   info->cur_row.trid=    _ma_trid_from_key(&info->last_key);
    1799             739 :   info->int_keypos=      info->int_maxpos= end_of_page;
    1800             739 :   info->int_nod_flag=    page.node;
    1801             739 :   info->int_keytree_version= keyinfo->version;
    1802             739 :   info->last_search_keypage= info->last_keypage;
    1803             739 :   info->page_changed=info->keyread_buff_used=0;
    1804                 : 
    1805             739 :   DBUG_PRINT("exit",("found key at %lu",(ulong) info->cur_row.lastpos));
    1806             739 :   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          841088 : {
    1833          841088 :   s_temp->key= key->data;
    1834          841088 :   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            6948 : {
    1847            6948 :   s_temp->key= key->data;
    1848            6948 :   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          474161 : {
    1881                 :   reg1 HA_KEYSEG *keyseg;
    1882                 :   int length;
    1883          474161 :   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          474161 :   MARIA_KEYDEF *keyinfo= int_key->keyinfo;
    1889                 : 
    1890          474161 :   key= int_key->data;
    1891          474161 :   length_pack=s_temp->ref_length=s_temp->n_ref_length=s_temp->n_length=0;
    1892          474161 :   same_length=0; keyseg=keyinfo->seg;
    1893          474161 :   key_length= int_key->data_length + int_key->ref_length + nod_flag;
    1894                 : 
    1895          474161 :   sort_order=0;
    1896          474161 :   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          474161 :   if (keyseg->length >= 127)
    1905                 :   {
    1906             520 :     diff_flag=2;
    1907             520 :     pack_marker=32768;
    1908                 :   }
    1909                 :   else
    1910                 :   {
    1911          473641 :     diff_flag= 1;
    1912          473641 :     pack_marker=128;
    1913                 :   }
    1914          474161 :   s_temp->pack_marker=pack_marker;
    1915                 : 
    1916                 :   /* Handle the case that the first part have NULL values */
    1917          474161 :   if (keyseg->flag & HA_NULL_PART)
    1918                 :   {
    1919             405 :     if (!*key++)
    1920                 :     {
    1921              30 :       s_temp->key= key;
    1922              30 :       s_temp->key_length= 0;
    1923              30 :       s_temp->totlength= key_length-1+diff_flag;
    1924              30 :       s_temp->next_key_pos= 0;                   /* No next key */
    1925              30 :       return (s_temp->move_length= s_temp->totlength);
    1926                 :     }
    1927             375 :     s_temp->store_not_null=1;
    1928             375 :     key_length--;                               /* We don't store NULL */
    1929             375 :     if (prev_key && !*prev_key++)
    1930               0 :       org_key=prev_key=0;                       /* Can't pack against prev */
    1931             375 :     else if (org_key)
    1932             240 :       org_key++;                                /* Skip NULL */
    1933                 :   }
    1934                 :   else
    1935          473756 :     s_temp->store_not_null=0;
    1936          474131 :   s_temp->prev_key= org_key;
    1937                 : 
    1938                 :   /* The key part will start with a packed length */
    1939                 : 
    1940          474131 :   get_key_pack_length(new_key_length,length_pack,key);
    1941          474131 :   end= key_end= key+ new_key_length;
    1942          474131 :   start= key;
    1943                 : 
    1944                 :   /* Calc how many characters are identical between this and the prev. key */
    1945          474131 :   if (prev_key)
    1946                 :   {
    1947          469866 :     get_key_length(org_key_length,prev_key);
    1948          469866 :     s_temp->prev_key=prev_key;          /* Pointer at data */
    1949                 :     /* Don't use key-pack if length == 0 */
    1950          807380 :     if (new_key_length && new_key_length == org_key_length)
    1951          337514 :       same_length=1;
    1952          132352 :     else if (new_key_length > org_key_length)
    1953           60746 :       end= key + org_key_length;
    1954                 : 
    1955          469866 :     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         2981231 :       while (key < end && *key == *prev_key)
    1966                 :       {
    1967         2511365 :         key++; prev_key++;
    1968                 :       }
    1969                 :     }
    1970                 :   }
    1971                 : 
    1972          474131 :   s_temp->key=key;
    1973          474131 :   s_temp->key_length= (uint) (key_end-key);
    1974                 : 
    1975          474131 :   if (same_length && key == key_end)
    1976                 :   {
    1977                 :     /* identical variable length key */
    1978          262624 :     s_temp->ref_length= pack_marker;
    1979          262624 :     length=(int) key_length-(int) (key_end-start)-length_pack;
    1980          262624 :     length+= diff_flag;
    1981          262624 :     if (next_key)
    1982                 :     {                                           /* Can't combine with next */
    1983          225536 :       s_temp->n_length= *next_key;              /* Needed by _ma_store_key */
    1984          225536 :       next_key=0;
    1985                 :     }
    1986                 :   }
    1987                 :   else
    1988                 :   {
    1989          211507 :     if (start != key)
    1990                 :     {                                           /* Starts as prev key */
    1991          195208 :       ref_length= (uint) (key-start);
    1992          195208 :       s_temp->ref_length= ref_length + pack_marker;
    1993          195208 :       length= (int) (key_length - ref_length);
    1994                 : 
    1995          195208 :       length-= length_pack;
    1996          195208 :       length+= diff_flag;
    1997          195208 :       length+= ((new_key_length-ref_length) >= 255) ? 3 : 1;/* Rest_of_key */
    1998                 :     }
    1999                 :     else
    2000                 :     {
    2001           16299 :       s_temp->key_length+=s_temp->store_not_null;       /* If null */
    2002           16299 :       length= key_length - length_pack+ diff_flag;
    2003                 :     }
    2004                 :   }
    2005          474131 :   s_temp->totlength=(uint) length;
    2006          474131 :   s_temp->prev_length=0;
    2007          474131 :   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          474131 :   if ((s_temp->next_key_pos=next_key))
    2012                 :   {
    2013                 :     uint packed,n_length;
    2014                 : 
    2015          166820 :     packed = *next_key & 128;
    2016          166820 :     if (diff_flag == 2)
    2017                 :     {
    2018             375 :       n_length= mi_uint2korr(next_key) & 32767; /* Length of next key */
    2019             375 :       next_key+=2;
    2020                 :     }
    2021                 :     else
    2022          166445 :       n_length= *next_key++ & 127;
    2023          166820 :     if (!packed)
    2024           13198 :       n_length-= s_temp->store_not_null;
    2025                 : 
    2026          166820 :     if (n_length || packed)             /* Don't pack 0 length keys */
    2027                 :     {
    2028          166116 :       uint next_length_pack, new_ref_length=s_temp->ref_length;
    2029                 : 
    2030          166116 :       if (packed)
    2031                 :       {
    2032                 :         /* If first key and next key is packed (only on delete) */
    2033          153622 :         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          153622 :         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          153622 :         ref_length=n_length;
    2084                 :         /* Get information about not packed key suffix */
    2085          153622 :         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          153622 :         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          153622 :         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           12494 :         ref_length=0;
    2112           12494 :         next_length_pack=0;
    2113                 :      }
    2114          166116 :       DBUG_PRINT("test",("length: %d  next_key: 0x%lx", length,
    2115                 :                          (long) next_key));
    2116                 : 
    2117                 :       {
    2118                 :         uint tmp_length;
    2119          166116 :         key=(start+=ref_length);
    2120          166116 :         if (key+n_length < key_end)             /* Normalize length based */
    2121           48924 :           key_end= key+n_length;
    2122          166116 :         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          320503 :           while (key < key_end && *key == *next_key)
    2133                 :           {
    2134          154387 :             key++; next_key++;
    2135                 :           }
    2136                 :         }
    2137          166116 :         if (!(tmp_length=(uint) (key-start)))
    2138                 :         {                                       /* Key can't be re-packed */
    2139          104261 :           s_temp->next_key_pos=0;
    2140          104261 :           return (s_temp->move_length= length);
    2141                 :         }
    2142           61855 :         ref_length+=tmp_length;
    2143           61855 :         n_length-=tmp_length;
    2144           61855 :         length-=tmp_length+next_length_pack;    /* We gained these chars */
    2145                 :       }
    2146           77510 :       if (n_length == 0 && ref_length == new_key_length)
    2147                 :       {
    2148           15655 :         s_temp->n_ref_length=pack_marker;       /* Same as prev key */
    2149                 :       }
    2150                 :       else
    2151                 :       {
    2152           46200 :         s_temp->n_ref_length=ref_length | pack_marker;
    2153           46200 :         length+= get_pack_length(n_length);
    2154           46200 :         s_temp->n_length=n_length;
    2155                 :       }
    2156                 :     }
    2157                 :   }
    2158          369870 :   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          163537 : {
    2170                 :   uint length,key_length,ref_length;
    2171          163537 :   const uchar *key= int_key->data;
    2172                 : 
    2173          163537 :   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          163537 :   s_temp->key=key;
    2179          163537 :   s_temp->prev_key=org_key;
    2180          163537 :   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          162280 :     end=key+key_length;
    2189          162280 :     for ( ; *key == *prev_key && key < end; key++,prev_key++) ;
    2190          162280 :     s_temp->ref_length= ref_length=(uint) (key-s_temp->key);
    2191          162280 :     length=key_length - ref_length + get_pack_length(ref_length);
    2192                 :   }
    2193                 :   else
    2194                 :   {
    2195                 :     /* No previous key */
    2196            1257 :     s_temp->ref_length=ref_length=0;
    2197            1257 :     length=key_length+1;
    2198                 :   }
    2199          163537 :   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          137667 :     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          137667 :     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          137667 :     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             475 :       s_temp->n_ref_length= ref_length;
    2222             475 :       s_temp->prev_length=  next_length-ref_length;
    2223             475 :       s_temp->prev_key+=    ref_length;
    2224             475 :       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          137192 :     key= s_temp->key+next_length;
    2230          137192 :     s_temp->prev_length= 0;
    2231          290608 :     while (*key++ == *next_key++) ;
    2232          137192 :     if ((ref_length= (uint) (key - s_temp->key)-1) == next_length)
    2233                 :     {
    2234          130738 :       s_temp->next_key_pos=0;
    2235          130738 :       return (s_temp->move_length= length);  /* Can't pack next key */
    2236                 :     }
    2237            6454 :     s_temp->n_ref_length=ref_length;
    2238            6454 :     return s_temp->move_length= (int) (length-(ref_length - next_length) -
    2239                 :                                        next_length_pack +
    2240                 :                                        get_pack_length(ref_length));
    2241                 :   }
    2242           25870 :   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          848036 : {
    2256          848036 :   memcpy(key_pos, s_temp->key,(size_t) s_temp->move_length);
    2257          848036 :   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          474161 : {
    2272                 :   uint length;
    2273          474161 :   uchar *org_key_pos= key_pos;
    2274                 : 
    2275          474161 :   if (s_temp->ref_length)
    2276                 :   {
    2277                 :     /* Packed against previous key */
    2278          457832 :     store_pack_length(s_temp->pack_marker == 128,key_pos,s_temp->ref_length);
    2279                 :     /* If not same key after */
    2280          457832 :     if (s_temp->ref_length != s_temp->pack_marker)
    2281          195208 :       store_key_length_inc(key_pos,s_temp->key_length);
    2282                 :   }
    2283                 :   else
    2284                 :   {
    2285                 :     /* Not packed against previous key */
    2286           16329 :     store_pack_length(s_temp->pack_marker == 128,key_pos,s_temp->key_length);
    2287                 :   }
    2288          474161 :   bmove(key_pos, s_temp->key,
    2289                 :         (length= s_temp->totlength - (uint) (key_pos-org_key_pos)));
    2290                 : 
    2291          474161 :   key_pos+= length;
    2292                 : 
    2293          474161 :   if (!s_temp->next_key_pos)                    /* No following key */
    2294           62559 :     goto end;
    2295                 : 
    2296           62559 :   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           62559 :   else if (s_temp->n_ref_length)
    2315                 :   {
    2316           61855 :     store_pack_length(s_temp->pack_marker == 128,key_pos,s_temp->n_ref_length);
    2317           61855 :     if (s_temp->n_ref_length != s_temp->pack_marker)
    2318                 :     {
    2319                 :       /* Not identical key */
    2320           46200 :       store_key_length_inc(key_pos,s_temp->n_length);
    2321                 :     }
    2322                 :   }
    2323                 :   else
    2324                 :   {
    2325             704 :     s_temp->n_length+= s_temp->store_not_null;
    2326             704 :     store_pack_length(s_temp->pack_marker == 128,key_pos,s_temp->n_length);
    2327                 :   }
    2328                 : 
    2329          474161 : end:
    2330          474161 :   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          163537 : {
    2340          163537 :   uchar *org_key_pos= key_pos;
    2341          163537 :   size_t length= s_temp->totlength - s_temp->ref_length;
    2342                 : 
    2343          163537 :   store_key_length_inc(key_pos,s_temp->ref_length);
    2344          163537 :   memcpy(key_pos, s_temp->key+s_temp->ref_length, length);
    2345          163537 :   key_pos+= length;
    2346                 : 
    2347          163537 :   if (s_temp->next_key_pos)
    2348                 :   {
    2349            6929 :     store_key_length_inc(key_pos,s_temp->n_ref_length);
    2350            6929 :     if (s_temp->prev_length)                    /* If we must extend key */
    2351                 :     {
    2352             475 :       memcpy(key_pos,s_temp->prev_key,s_temp->prev_length);
    2353             475 :       key_pos+= s_temp->prev_length;
    2354                 :     }
    2355                 :   }
    2356          163537 :   s_temp->changed_length= (uint) (key_pos - org_key_pos);
    2357                 : }

Generated by: LTP GCOV extension version 1.4