<commit_before>/* Copyright (C) 2000 MySQL AB & MySQL Finland AB & TCX DataKonsult AB

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */

/* key handling functions */

#include "fulltext.h"
#include "m_ctype.h"

static my_bool _mi_get_prev_key(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *page,
                                uchar *key, uchar *keypos,
                                uint *return_key_length);

        /* Check index */

int _mi_check_index(MI_INFO *info, int inx)
{
  if (inx == -1)                        /* Use last index */
    inx=info->lastinx;
  if (inx < 0 || ! (((ulonglong) 1 << inx) & info->s->state.key_map))
  {
    my_errno=HA_ERR_WRONG_INDEX;
    return -1;
  }
  if (info->lastinx != inx)             /* Index changed */
  {
    info->lastinx = inx;
    info->page_changed=1;
    info->update= ((info->update & (HA_STATE_CHANGED | HA_STATE_ROW_CHANGED)) |
                   HA_STATE_NEXT_FOUND | HA_STATE_PREV_FOUND);
  }
  if (info->opt_flag & WRITE_CACHE_USED && flush_io_cache(&info->rec_cache))
    return(-1);
  return(inx);
} /* mi_check_index */


        /*
        ** Search after row by a key
        ** Position to row is stored in info->lastpos
        ** Return: -1 if not found
        **          1 if one should continue search on higher level
        */

int _mi_search(register MI_INFO *info, register MI_KEYDEF *keyinfo,
               uchar *key, uint key_len, uint nextflag, register my_off_t pos)
{
  my_bool last_key;
  int error,flag;
  uint nod_flag;
  uchar *keypos,*maxpos;
  uchar lastkey[MI_MAX_KEY_BUFF],*buff;
  DBUG_ENTER("_mi_search");
  DBUG_PRINT("enter",("pos: %ld  nextflag: %d  lastpos: %ld",
                      pos,nextflag,info->lastpos));
  DBUG_EXECUTE("key",_mi_print_key(DBUG_FILE,keyinfo->seg,key,key_len););

  if (pos == HA_OFFSET_ERROR)
  {
    my_errno=HA_ERR_KEY_NOT_FOUND;                      /* Didn't find key */
    info->lastpos= HA_OFFSET_ERROR;
    if (!(nextflag & (SEARCH_SMALLER | SEARCH_BIGGER | SEARCH_LAST)))
      DBUG_RETURN(-1);                          /* Not found ; return error */
    DBUG_RETURN(1);                             /* Search at upper levels */
  }

  if (!(buff=_mi_fetch_keypage(info,keyinfo,pos,info->buff,
                               test(!(nextflag & SEARCH_SAVE_BUFF)))))
    goto err;
  DBUG_DUMP("page",(byte*) buff,mi_getint(buff));

  flag=(*keyinfo->bin_search)(info,keyinfo,buff,key,key_len,nextflag,
                              &keypos,lastkey, &last_key);
  if (flag == MI_FOUND_WRONG_KEY)
    DBUG_RETURN(-1);
  nod_flag=mi_test_if_nod(buff);
  maxpos=buff+mi_getint(buff)-1;

  if (flag)
  {
    if ((error=_mi_search(info,keyinfo,key,key_len,nextflag,
                          _mi_kpos(nod_flag,keypos))) <= 0)
      DBUG_RETURN(error);

    if (flag >0)
    {
      if (nextflag & (SEARCH_SMALLER | SEARCH_LAST) &&
          keypos == buff+2+nod_flag)
        DBUG_RETURN(1);                                 /* Bigger than key */
    }
    else if (nextflag & SEARCH_BIGGER && keypos >= maxpos)
      DBUG_RETURN(1);                                   /* Smaller than key */
  }
  else
  {
    if ((nextflag & SEARCH_FIND) && nod_flag &&
	((keyinfo->flag & (HA_NOSAME | HA_NULL_PART)) != HA_NOSAME ||
	 key_len != USE_WHOLE_KEY))
    {
      if ((error=_mi_search(info,keyinfo,key,key_len,SEARCH_FIND,
                            _mi_kpos(nod_flag,keypos))) >= 0 ||
          my_errno != HA_ERR_KEY_NOT_FOUND)
        DBUG_RETURN(error);
      info->last_keypage= HA_OFFSET_ERROR;              /* Buffer not in mem */
    }
  }
  if (pos != info->last_keypage)
  {
    uchar *old_buff=buff;
    if (!(buff=_mi_fetch_keypage(info,keyinfo,pos,info->buff,
                                 test(!(nextflag & SEARCH_SAVE_BUFF)))))
      goto err;
    keypos=buff+(keypos-old_buff);
    maxpos=buff+(maxpos-old_buff);
  }

  if ((nextflag & (SEARCH_SMALLER | SEARCH_LAST)) && flag != 0)
  {
    uint not_used;
    if (_mi_get_prev_key(info,keyinfo, buff, info->lastkey, keypos,
                         &info->lastkey_length))
      goto err;
    if ((nextflag & SEARCH_LAST) &&
        _mi_key_cmp(keyinfo->seg, info->lastkey, key, key_len, SEARCH_FIND,
                    &not_used))
    {
      my_errno=HA_ERR_KEY_NOT_FOUND;                    /* Didn't find key */
      goto err;
    }
  }
  else
  {
    info->lastkey_length=(*keyinfo->get_key)(keyinfo,nod_flag,&keypos,lastkey);
    if (!info->lastkey_length)
      goto err;
    memcpy(info->lastkey,lastkey,info->lastkey_length);
  }
  info->lastpos=_mi_dpos(info,0,info->lastkey+info->lastkey_length);
  /* Save position for a possible read next / previous */
  info->int_keypos=info->buff+ (keypos-buff);
  info->int_maxpos=info->buff+ (maxpos-buff);
  info->int_nod_flag=nod_flag;
  info->int_keytree_version=keyinfo->version;
  info->last_search_keypage=info->last_keypage;
  info->page_changed=0;
  info->buff_used= (info->buff != buff);        /* If we have to reread buff */

  DBUG_PRINT("exit",("found key at %lu",(ulong) info->lastpos));
  DBUG_RETURN(0);
err:
  DBUG_PRINT("exit",("Error: %d",my_errno));
  info->lastpos= HA_OFFSET_ERROR;
  info->page_changed=1;
  DBUG_RETURN (-1);
} /* _mi_search */


        /* Search after key in page-block */
        /* If packed key puts smaller or identical key in buff */
        /* ret_pos point to where find or bigger key starts */
        /* ARGSUSED */

int _mi_bin_search(MI_INFO *info, register MI_KEYDEF *keyinfo, uchar *page,
                   uchar *key, uint key_len, uint comp_flag, uchar **ret_pos,
                   uchar *buff __attribute__((unused)), my_bool *last_key)
{
  reg4 int start,mid,end,save_end;
  int flag;
  uint totlength,nod_flag,not_used;
  DBUG_ENTER("_mi_bin_search");

  LINT_INIT(flag);
  totlength=keyinfo->keylength+(nod_flag=mi_test_if_nod(page));
  start=0; mid=1;
  save_end=end=(int) ((mi_getint(page)-2-nod_flag)/totlength-1);
  DBUG_PRINT("test",("mi_getint: %d  end: %d",mi_getint(page),end));
  page+=2+nod_flag;

  while (start != end)
  {
    mid= (start+end)/2;
    if ((flag=_mi_key_cmp(keyinfo->seg,page+(uint) mid*totlength,key,key_len,
                          comp_flag,&not_used))
        >= 0)
      end=mid;
    else
      start=mid+1;
  }
  if (mid != start)
    flag=_mi_key_cmp(keyinfo->seg,page+(uint) start*totlength,key,key_len,
                     comp_flag,&not_used);
  if (flag < 0)
    start++;                    /* point at next, bigger key */
  *ret_pos=page+(uint) start*totlength;
  *last_key= end == save_end;
  DBUG_PRINT("exit",("flag: %d  keypos: %d",flag,start));
  DBUG_RETURN(flag);
} /* _mi_bin_search */


        /* Used instead of _mi_bin_search() when key is packed */
        /* Puts smaller or identical key in buff */
        /* Key is searched sequentially */

int _mi_seq_search(MI_INFO *info, register MI_KEYDEF *keyinfo, uchar *page,
                   uchar *key, uint key_len, uint comp_flag, uchar **ret_pos,
                   uchar *buff, my_bool *last_key)
{
  int flag;
  uint nod_flag,length,not_used;
  uchar t_buff[MI_MAX_KEY_BUFF],*end;
  DBUG_ENTER("_mi_seq_search");

  LINT_INIT(flag); LINT_INIT(length);
  end= page+mi_getint(page);
  nod_flag=mi_test_if_nod(page);
  page+=2+nod_flag;
  *ret_pos=page;
  t_buff[0]=0;                                  /* Avoid bugs */
  while (page < end)
  {
    length=(*keyinfo->get_key)(keyinfo,nod_flag,&page,t_buff);
    if (length == 0 || page > end)
    {
      my_errno=HA_ERR_CRASHED;
      DBUG_PRINT("error",("Found wrong key:  length: %d  page: %lx  end: %lx",
                          length,page,end));
      DBUG_RETURN(MI_FOUND_WRONG_KEY);
    }
    if ((flag=_mi_key_cmp(keyinfo->seg,t_buff,key,key_len,comp_flag,
                          &not_used)) >= 0)
      break;
#ifdef EXTRA_DEBUG
    DBUG_PRINT("loop",("page: %lx  key: '%s'  flag: %d",page,t_buff,flag));
#endif
    memcpy(buff,t_buff,length);
    *ret_pos=page;
  }
  if (flag == 0)
    memcpy(buff,t_buff,length);                 /* Result is first key */
  *last_key= page == end;
  DBUG_PRINT("exit",("flag: %d  ret_pos: %lx",flag,*ret_pos));
  DBUG_RETURN(flag);
} /* _mi_seq_search */


int _mi_prefix_search(MI_INFO *info, register MI_KEYDEF *keyinfo, uchar *page,
                      uchar *key, uint key_len, uint nextflag, uchar **ret_pos,
                      uchar *buff, my_bool *last_key)
{
  /*
    my_flag is raw comparison result to be changed according to
    SEARCH_NO_FIND,SEARCH_LAST and HA_REVERSE_SORT flags.
    flag is the value returned by _mi_key_cmp and as treated as final
  */
  int flag=0, my_flag=-1;
  uint nod_flag, length, len, matched, cmplen, kseg_len;
  uint prefix_len,suffix_len;
  int key_len_skip, seg_len_pack, key_len_left;
  uchar *end, *kseg, *vseg;
  uchar *sort_order=keyinfo->seg->charset->sort_order;
  uchar tt_buff[MI_MAX_KEY_BUFF+2], *t_buff=tt_buff+2;
  uchar *saved_from, *saved_to, *saved_vseg;
  uint   saved_length=0, saved_prefix_len=0;
  DBUG_ENTER("_mi_prefix_search");

  LINT_INIT(length);
  LINT_INIT(prefix_len);
  LINT_INIT(seg_len_pack);
  LINT_INIT(saved_from);
  LINT_INIT(saved_to);
  LINT_INIT(saved_vseg);

  t_buff[0]=0;                                  /* Avoid bugs */
  end= page+mi_getint(page);
  nod_flag=mi_test_if_nod(page);
  page+=2+nod_flag;
  *ret_pos=page;
  kseg=key;
  {
    uint lenght_pack;
    get_key_pack_length(kseg_len,lenght_pack,kseg);
    key_len_skip=lenght_pack+kseg_len;
    key_len_left=(int) key_len- (int) key_len_skip;
    cmplen=(key_len_left>=0) ? kseg_len : key_len-lenght_pack;
    DBUG_PRINT("info",("key: '%.*s'",kseg_len,kseg));
  }

/*
  Keys are compressed the following way:

  If the max length of first key segment <= 127 characters the prefix is
  1 byte else it's 2 byte

  prefix         The high bit is set if this is a prefix for the prev key
  length         Packed length if the previous was a prefix byte
  [length]       Length character of data
  next-key-seg   Next key segments
*/

  matched=0;  /* how many char's from prefix were alredy matched */
  len=0;      /* length of previous key unpacked */

  while (page < end)
  {
    uint packed= *page & 128;

    vseg=page;
    if (keyinfo->seg->length >= 127)
    {
      suffix_len=mi_uint2korr(vseg) & 32767;
      vseg+=2;
    }
    else
      suffix_len= *vseg++ & 127;

    if (packed)
    {
      if (suffix_len == 0)                      /* Same key */
        prefix_len=len;
      else
      {
        prefix_len=suffix_len;
        get_key_length(suffix_len,vseg);
      }
    }
    else
      prefix_len=0;

    len=prefix_len+suffix_len;
    seg_len_pack=get_pack_length(len);
    t_buff=tt_buff+3-seg_len_pack;
    store_key_length(t_buff,len);

    if (prefix_len > saved_prefix_len)
      memcpy(t_buff+seg_len_pack+saved_prefix_len,saved_vseg,
             prefix_len-saved_prefix_len);
    saved_vseg=vseg;
    saved_prefix_len=prefix_len;

    DBUG_PRINT("loop",("page: '%.*s%.*s'",prefix_len,t_buff+seg_len_pack,suffix_len,vseg));
    {
      uchar *from=vseg+suffix_len;
      MI_KEYSEG *keyseg;
      uint l;

      for (keyseg=keyinfo->seg+1 ; keyseg->type ; keyseg++ )
      {

        if (keyseg->flag & HA_NULL_PART)
        {
          if (!(*from++))
            continue;
        }
        if (keyseg->flag & (HA_VAR_LENGTH | HA_BLOB_PART | HA_SPACE_PACK))
        {
          get_key_length(l,from);
        }
        else
          l=keyseg->length;

        from+=l;
      }
      from+=keyseg->length;
      page=from+nod_flag;
      length=from-vseg;
    }

    if (page > end)
    {
      my_errno=HA_ERR_CRASHED;
      DBUG_PRINT("error",("Found wrong key:  length: %d  page: %lx  end: %lx",
                          length,page,end));
      DBUG_RETURN(MI_FOUND_WRONG_KEY);
    }

    if (matched >= prefix_len)
    {
      /* We have to compare. But we can still skip part of the key */
      uint  left;
      uchar *k=kseg+prefix_len;

      left=(len>cmplen) ? cmplen-prefix_len : suffix_len;

      matched=prefix_len+left;

      for(my_flag=0;left;left--)
        if ((my_flag= (int) sort_order[*vseg++] - (int) sort_order[*k++]))
          break;

      if (my_flag>0)      /* mismatch */
        break;
      else if (my_flag==0) /* match */
      { /*
        **  len cmplen seg_left_len more_segs
        **     <                               matched=len; continue search
        **     >      =                        prefix ? found : (matched=len; continue search)
        **     >      <                 -      ok, found
        **     =      <                 -      ok, found
        **     =      =                 -      ok, found
        **     =      =                 +      next seg
        */
        if (len < cmplen)
        {
          my_flag= -1;
        }
        else if (len > cmplen)
        {
          if ((my_flag= (!(nextflag & SEARCH_PREFIX) || key_len_left>0)))
            break;
          goto fix_flag;
        }
        else if (key_len_left>0)
        {
          uint not_used;
          if ((flag = _mi_key_cmp(keyinfo->seg+1,vseg,
                                  k,key_len_left,nextflag,&not_used)) >= 0)
            break;
        }
        else
        {
          /* at this line flag==-1 if the following lines were already
             visited and 0 otherwise,  i.e. flag <=0 here always !!! */
  fix_flag:
          if (nextflag & (SEARCH_NO_FIND | SEARCH_LAST))
            flag=(nextflag & (SEARCH_BIGGER | SEARCH_LAST)) ? -1 : 1;
          if (flag>=0) break;
        }
      }
      matched-=left;
    }
    /* else (matched < prefix_len) ---> do nothing. */

    memcpy(buff,t_buff,saved_length=seg_len_pack+prefix_len);
    saved_to=buff+saved_length;
    saved_from=saved_vseg;
    saved_length=length;
    *ret_pos=page;
  }
  if (my_flag)
    flag=(keyinfo->seg->flag & HA_REVERSE_SORT) ? -my_flag : my_flag;
  if (flag == 0)
  {
    memcpy(buff,t_buff,saved_length=seg_len_pack+prefix_len);
    saved_to=buff+saved_length;
    saved_from=saved_vseg;
    saved_length=length;
  }
  if (saved_length)
    memcpy(saved_to,saved_from,saved_length);

  *last_key= page == end;

  DBUG_PRINT("exit",("flag: %d  ret_pos: %lx",flag,*ret_pos));
  DBUG_RETURN(flag);
} /* _mi_prefix_search */


        /* Get pos to a key_block */

my_off_t _mi_kpos(uint nod_flag, uchar *after_key)
{
  after_key-=nod_flag;
  switch (nod_flag) {
#if SIZEOF_OFF_T > 4
  case 7:
    return mi_uint7korr(after_key)*MI_MIN_KEY_BLOCK_LENGTH;
  case 6:
    return mi_uint6korr(after_key)*MI_MIN_KEY_BLOCK_LENGTH;
  case 5:
    return mi_uint5korr(after_key)*MI_MIN_KEY_BLOCK_LENGTH;
#else
  case 7:
    after_key++;
  case 6:
    after_key++;
  case 5:
    after_key++;
#endif
  case 4:
    return ((my_off_t) mi_uint4korr(after_key))*MI_MIN_KEY_BLOCK_LENGTH;
  case 3:
    return ((my_off_t) mi_uint3korr(after_key))*MI_MIN_KEY_BLOCK_LENGTH;
  case 2:
    return (my_off_t) (mi_uint2korr(after_key)*MI_MIN_KEY_BLOCK_LENGTH);
  case 1:
    return (uint) (*after_key)*MI_MIN_KEY_BLOCK_LENGTH;
  case 0:                                       /* At leaf page */
  default:                                      /* Impossible */
    return(HA_OFFSET_ERROR);
  }
} /* _kpos */


        /* Save pos to a key_block */

void _mi_kpointer(register MI_INFO *info, register uchar *buff, my_off_t pos)
{
  pos/=MI_MIN_KEY_BLOCK_LENGTH;
  switch (info->s->base.key_reflength) {
#if SIZEOF_OFF_T > 4
  case 7: mi_int7store(buff,pos); break;
  case 6: mi_int6store(buff,pos); break;
  case 5: mi_int5store(buff,pos); break;
#else
  case 7: *buff++=0;
    /* fall trough */
  case 6: *buff++=0;
    /* fall trough */
  case 5: *buff++=0;
    /* fall trough */
#endif
  case 4: mi_int4store(buff,pos); break;
  case 3: mi_int3store(buff,pos); break;
  case 2: mi_int2store(buff,(uint) pos); break;
  case 1: buff[0]= (uchar) pos; break;
  default: abort();                             /* impossible */
  }
} /* _mi_kpointer */


        /* Calc pos to a data-record from a key */


my_off_t _mi_dpos(MI_INFO *info, uint nod_flag, uchar *after_key)
{
  my_off_t pos;
  after_key-=(nod_flag + info->s->rec_reflength);
  switch (info->s->rec_reflength) {
#if SIZEOF_OFF_T > 4
  case 8:  pos= (my_off_t) mi_uint5korr(after_key);  break;
  case 7:  pos= (my_off_t) mi_uint7korr(after_key);  break;
  case 6:  pos= (my_off_t) mi_uint6korr(after_key);  break;
  case 5:  pos= (my_off_t) mi_uint5korr(after_key);  break;
#else
  case 8:  pos= (my_off_t) mi_uint4korr(after_key+4);   break;
  case 7:  pos= (my_off_t) mi_uint4korr(after_key+3);   break;
  case 6:  pos= (my_off_t) mi_uint4korr(after_key+2);   break;
  case 5:  pos= (my_off_t) mi_uint4korr(after_key+1);   break;
#endif
  case 4:  pos= (my_off_t) mi_uint4korr(after_key);  break;
  case 3:  pos= (my_off_t) mi_uint3korr(after_key);  break;
  case 2:  pos= (my_off_t) mi_uint2korr(after_key);  break;
  default:
    pos=0L;                                     /* Shut compiler up */
  }
  return (info->s->options &
          (HA_OPTION_PACK_RECORD | HA_OPTION_COMPRESS_RECORD)) ? pos :
            pos*info->s->base.pack_reclength;
}


/* Calc position from a record pointer ( in delete link chain ) */

my_off_t _mi_rec_pos(MYISAM_SHARE *s, uchar *ptr)
{<commit_msg>Fixed a probable typo. Unfortunately we will not be able to test this ;-)<commit_after>/* Copyright (C) 2000 MySQL AB & MySQL Finland AB & TCX DataKonsult AB

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2 of the License, or
   (at your option) any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */

/* key handling functions */

#include "fulltext.h"
#include "m_ctype.h"

static my_bool _mi_get_prev_key(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *page,
                                uchar *key, uchar *keypos,
                                uint *return_key_length);

        /* Check index */

int _mi_check_index(MI_INFO *info, int inx)
{
  if (inx == -1)                        /* Use last index */
    inx=info->lastinx;
  if (inx < 0 || ! (((ulonglong) 1 << inx) & info->s->state.key_map))
  {
    my_errno=HA_ERR_WRONG_INDEX;
    return -1;
  }
  if (info->lastinx != inx)             /* Index changed */
  {
    info->lastinx = inx;
    info->page_changed=1;
    info->update= ((info->update & (HA_STATE_CHANGED | HA_STATE_ROW_CHANGED)) |
                   HA_STATE_NEXT_FOUND | HA_STATE_PREV_FOUND);
  }
  if (info->opt_flag & WRITE_CACHE_USED && flush_io_cache(&info->rec_cache))
    return(-1);
  return(inx);
} /* mi_check_index */


        /*
        ** Search after row by a key
        ** Position to row is stored in info->lastpos
        ** Return: -1 if not found
        **          1 if one should continue search on higher level
        */

int _mi_search(register MI_INFO *info, register MI_KEYDEF *keyinfo,
               uchar *key, uint key_len, uint nextflag, register my_off_t pos)
{
  my_bool last_key;
  int error,flag;
  uint nod_flag;
  uchar *keypos,*maxpos;
  uchar lastkey[MI_MAX_KEY_BUFF],*buff;
  DBUG_ENTER("_mi_search");
  DBUG_PRINT("enter",("pos: %ld  nextflag: %d  lastpos: %ld",
                      pos,nextflag,info->lastpos));
  DBUG_EXECUTE("key",_mi_print_key(DBUG_FILE,keyinfo->seg,key,key_len););

  if (pos == HA_OFFSET_ERROR)
  {
    my_errno=HA_ERR_KEY_NOT_FOUND;                      /* Didn't find key */
    info->lastpos= HA_OFFSET_ERROR;
    if (!(nextflag & (SEARCH_SMALLER | SEARCH_BIGGER | SEARCH_LAST)))
      DBUG_RETURN(-1);                          /* Not found ; return error */
    DBUG_RETURN(1);                             /* Search at upper levels */
  }

  if (!(buff=_mi_fetch_keypage(info,keyinfo,pos,info->buff,
                               test(!(nextflag & SEARCH_SAVE_BUFF)))))
    goto err;
  DBUG_DUMP("page",(byte*) buff,mi_getint(buff));

  flag=(*keyinfo->bin_search)(info,keyinfo,buff,key,key_len,nextflag,
                              &keypos,lastkey, &last_key);
  if (flag == MI_FOUND_WRONG_KEY)
    DBUG_RETURN(-1);
  nod_flag=mi_test_if_nod(buff);
  maxpos=buff+mi_getint(buff)-1;

  if (flag)
  {
    if ((error=_mi_search(info,keyinfo,key,key_len,nextflag,
                          _mi_kpos(nod_flag,keypos))) <= 0)
      DBUG_RETURN(error);

    if (flag >0)
    {
      if (nextflag & (SEARCH_SMALLER | SEARCH_LAST) &&
          keypos == buff+2+nod_flag)
        DBUG_RETURN(1);                                 /* Bigger than key */
    }
    else if (nextflag & SEARCH_BIGGER && keypos >= maxpos)
      DBUG_RETURN(1);                                   /* Smaller than key */
  }
  else
  {
    if ((nextflag & SEARCH_FIND) && nod_flag &&
	((keyinfo->flag & (HA_NOSAME | HA_NULL_PART)) != HA_NOSAME ||
	 key_len != USE_WHOLE_KEY))
    {
      if ((error=_mi_search(info,keyinfo,key,key_len,SEARCH_FIND,
                            _mi_kpos(nod_flag,keypos))) >= 0 ||
          my_errno != HA_ERR_KEY_NOT_FOUND)
        DBUG_RETURN(error);
      info->last_keypage= HA_OFFSET_ERROR;              /* Buffer not in mem */
    }
  }
  if (pos != info->last_keypage)
  {
    uchar *old_buff=buff;
    if (!(buff=_mi_fetch_keypage(info,keyinfo,pos,info->buff,
                                 test(!(nextflag & SEARCH_SAVE_BUFF)))))
      goto err;
    keypos=buff+(keypos-old_buff);
    maxpos=buff+(maxpos-old_buff);
  }

  if ((nextflag & (SEARCH_SMALLER | SEARCH_LAST)) && flag != 0)
  {
    uint not_used;
    if (_mi_get_prev_key(info,keyinfo, buff, info->lastkey, keypos,
                         &info->lastkey_length))
      goto err;
    if ((nextflag & SEARCH_LAST) &&
        _mi_key_cmp(keyinfo->seg, info->lastkey, key, key_len, SEARCH_FIND,
                    &not_used))
    {
      my_errno=HA_ERR_KEY_NOT_FOUND;                    /* Didn't find key */
      goto err;
    }
  }
  else
  {
    info->lastkey_length=(*keyinfo->get_key)(keyinfo,nod_flag,&keypos,lastkey);
    if (!info->lastkey_length)
      goto err;
    memcpy(info->lastkey,lastkey,info->lastkey_length);
  }
  info->lastpos=_mi_dpos(info,0,info->lastkey+info->lastkey_length);
  /* Save position for a possible read next / previous */
  info->int_keypos=info->buff+ (keypos-buff);
  info->int_maxpos=info->buff+ (maxpos-buff);
  info->int_nod_flag=nod_flag;
  info->int_keytree_version=keyinfo->version;
  info->last_search_keypage=info->last_keypage;
  info->page_changed=0;
  info->buff_used= (info->buff != buff);        /* If we have to reread buff */

  DBUG_PRINT("exit",("found key at %lu",(ulong) info->lastpos));
  DBUG_RETURN(0);
err:
  DBUG_PRINT("exit",("Error: %d",my_errno));
  info->lastpos= HA_OFFSET_ERROR;
  info->page_changed=1;
  DBUG_RETURN (-1);
} /* _mi_search */


        /* Search after key in page-block */
        /* If packed key puts smaller or identical key in buff */
        /* ret_pos point to where find or bigger key starts */
        /* ARGSUSED */

int _mi_bin_search(MI_INFO *info, register MI_KEYDEF *keyinfo, uchar *page,
                   uchar *key, uint key_len, uint comp_flag, uchar **ret_pos,
                   uchar *buff __attribute__((unused)), my_bool *last_key)
{
  reg4 int start,mid,end,save_end;
  int flag;
  uint totlength,nod_flag,not_used;
  DBUG_ENTER("_mi_bin_search");

  LINT_INIT(flag);
  totlength=keyinfo->keylength+(nod_flag=mi_test_if_nod(page));
  start=0; mid=1;
  save_end=end=(int) ((mi_getint(page)-2-nod_flag)/totlength-1);
  DBUG_PRINT("test",("mi_getint: %d  end: %d",mi_getint(page),end));
  page+=2+nod_flag;

  while (start != end)
  {
    mid= (start+end)/2;
    if ((flag=_mi_key_cmp(keyinfo->seg,page+(uint) mid*totlength,key,key_len,
                          comp_flag,&not_used))
        >= 0)
      end=mid;
    else
      start=mid+1;
  }
  if (mid != start)
    flag=_mi_key_cmp(keyinfo->seg,page+(uint) start*totlength,key,key_len,
                     comp_flag,&not_used);
  if (flag < 0)
    start++;                    /* point at next, bigger key */
  *ret_pos=page+(uint) start*totlength;
  *last_key= end == save_end;
  DBUG_PRINT("exit",("flag: %d  keypos: %d",flag,start));
  DBUG_RETURN(flag);
} /* _mi_bin_search */


        /* Used instead of _mi_bin_search() when key is packed */
        /* Puts smaller or identical key in buff */
        /* Key is searched sequentially */

int _mi_seq_search(MI_INFO *info, register MI_KEYDEF *keyinfo, uchar *page,
                   uchar *key, uint key_len, uint comp_flag, uchar **ret_pos,
                   uchar *buff, my_bool *last_key)
{
  int flag;
  uint nod_flag,length,not_used;
  uchar t_buff[MI_MAX_KEY_BUFF],*end;
  DBUG_ENTER("_mi_seq_search");

  LINT_INIT(flag); LINT_INIT(length);
  end= page+mi_getint(page);
  nod_flag=mi_test_if_nod(page);
  page+=2+nod_flag;
  *ret_pos=page;
  t_buff[0]=0;                                  /* Avoid bugs */
  while (page < end)
  {
    length=(*keyinfo->get_key)(keyinfo,nod_flag,&page,t_buff);
    if (length == 0 || page > end)
    {
      my_errno=HA_ERR_CRASHED;
      DBUG_PRINT("error",("Found wrong key:  length: %d  page: %lx  end: %lx",
                          length,page,end));
      DBUG_RETURN(MI_FOUND_WRONG_KEY);
    }
    if ((flag=_mi_key_cmp(keyinfo->seg,t_buff,key,key_len,comp_flag,
                          &not_used)) >= 0)
      break;
#ifdef EXTRA_DEBUG
    DBUG_PRINT("loop",("page: %lx  key: '%s'  flag: %d",page,t_buff,flag));
#endif
    memcpy(buff,t_buff,length);
    *ret_pos=page;
  }
  if (flag == 0)
    memcpy(buff,t_buff,length);                 /* Result is first key */
  *last_key= page == end;
  DBUG_PRINT("exit",("flag: %d  ret_pos: %lx",flag,*ret_pos));
  DBUG_RETURN(flag);
} /* _mi_seq_search */


int _mi_prefix_search(MI_INFO *info, register MI_KEYDEF *keyinfo, uchar *page,
                      uchar *key, uint key_len, uint nextflag, uchar **ret_pos,
                      uchar *buff, my_bool *last_key)
{
  /*
    my_flag is raw comparison result to be changed according to
    SEARCH_NO_FIND,SEARCH_LAST and HA_REVERSE_SORT flags.
    flag is the value returned by _mi_key_cmp and as treated as final
  */
  int flag=0, my_flag=-1;
  uint nod_flag, length, len, matched, cmplen, kseg_len;
  uint prefix_len,suffix_len;
  int key_len_skip, seg_len_pack, key_len_left;
  uchar *end, *kseg, *vseg;
  uchar *sort_order=keyinfo->seg->charset->sort_order;
  uchar tt_buff[MI_MAX_KEY_BUFF+2], *t_buff=tt_buff+2;
  uchar *saved_from, *saved_to, *saved_vseg;
  uint   saved_length=0, saved_prefix_len=0;
  DBUG_ENTER("_mi_prefix_search");

  LINT_INIT(length);
  LINT_INIT(prefix_len);
  LINT_INIT(seg_len_pack);
  LINT_INIT(saved_from);
  LINT_INIT(saved_to);
  LINT_INIT(saved_vseg);

  t_buff[0]=0;                                  /* Avoid bugs */
  end= page+mi_getint(page);
  nod_flag=mi_test_if_nod(page);
  page+=2+nod_flag;
  *ret_pos=page;
  kseg=key;
  {
    uint lenght_pack;
    get_key_pack_length(kseg_len,lenght_pack,kseg);
    key_len_skip=lenght_pack+kseg_len;
    key_len_left=(int) key_len- (int) key_len_skip;
    cmplen=(key_len_left>=0) ? kseg_len : key_len-lenght_pack;
    DBUG_PRINT("info",("key: '%.*s'",kseg_len,kseg));
  }

/*
  Keys are compressed the following way:

  If the max length of first key segment <= 127 characters the prefix is
  1 byte else it's 2 byte

  prefix         The high bit is set if this is a prefix for the prev key
  length         Packed length if the previous was a prefix byte
  [length]       Length character of data
  next-key-seg   Next key segments
*/

  matched=0;  /* how many char's from prefix were alredy matched */
  len=0;      /* length of previous key unpacked */

  while (page < end)
  {
    uint packed= *page & 128;

    vseg=page;
    if (keyinfo->seg->length >= 127)
    {
      suffix_len=mi_uint2korr(vseg) & 32767;
      vseg+=2;
    }
    else
      suffix_len= *vseg++ & 127;

    if (packed)
    {
      if (suffix_len == 0)                      /* Same key */
        prefix_len=len;
      else
      {
        prefix_len=suffix_len;
        get_key_length(suffix_len,vseg);
      }
    }
    else
      prefix_len=0;

    len=prefix_len+suffix_len;
    seg_len_pack=get_pack_length(len);
    t_buff=tt_buff+3-seg_len_pack;
    store_key_length(t_buff,len);

    if (prefix_len > saved_prefix_len)
      memcpy(t_buff+seg_len_pack+saved_prefix_len,saved_vseg,
             prefix_len-saved_prefix_len);
    saved_vseg=vseg;
    saved_prefix_len=prefix_len;

    DBUG_PRINT("loop",("page: '%.*s%.*s'",prefix_len,t_buff+seg_len_pack,suffix_len,vseg));
    {
      uchar *from=vseg+suffix_len;
      MI_KEYSEG *keyseg;
      uint l;

      for (keyseg=keyinfo->seg+1 ; keyseg->type ; keyseg++ )
      {

        if (keyseg->flag & HA_NULL_PART)
        {
          if (!(*from++))
            continue;
        }
        if (keyseg->flag & (HA_VAR_LENGTH | HA_BLOB_PART | HA_SPACE_PACK))
        {
          get_key_length(l,from);
        }
        else
          l=keyseg->length;

        from+=l;
      }
      from+=keyseg->length;
      page=from+nod_flag;
      length=from-vseg;
    }

    if (page > end)
    {
      my_errno=HA_ERR_CRASHED;
      DBUG_PRINT("error",("Found wrong key:  length: %d  page: %lx  end: %lx",
                          length,page,end));
      DBUG_RETURN(MI_FOUND_WRONG_KEY);
    }

    if (matched >= prefix_len)
    {
      /* We have to compare. But we can still skip part of the key */
      uint  left;
      uchar *k=kseg+prefix_len;

      left=(len>cmplen) ? cmplen-prefix_len : suffix_len;

      matched=prefix_len+left;

      for(my_flag=0;left;left--)
        if ((my_flag= (int) sort_order[*vseg++] - (int) sort_order[*k++]))
          break;

      if (my_flag>0)      /* mismatch */
        break;
      else if (my_flag==0) /* match */
      { /*
        **  len cmplen seg_left_len more_segs
        **     <                               matched=len; continue search
        **     >      =                        prefix ? found : (matched=len; continue search)
        **     >      <                 -      ok, found
        **     =      <                 -      ok, found
        **     =      =                 -      ok, found
        **     =      =                 +      next seg
        */
        if (len < cmplen)
        {
          my_flag= -1;
        }
        else if (len > cmplen)
        {
          if ((my_flag= (!(nextflag & SEARCH_PREFIX) || key_len_left>0)))
            break;
          goto fix_flag;
        }
        else if (key_len_left>0)
        {
          uint not_used;
          if ((flag = _mi_key_cmp(keyinfo->seg+1,vseg,
                                  k,key_len_left,nextflag,&not_used)) >= 0)
            break;
        }
        else
        {
          /* at this line flag==-1 if the following lines were already
             visited and 0 otherwise,  i.e. flag <=0 here always !!! */
  fix_flag:
          if (nextflag & (SEARCH_NO_FIND | SEARCH_LAST))
            flag=(nextflag & (SEARCH_BIGGER | SEARCH_LAST)) ? -1 : 1;
          if (flag>=0) break;
        }
      }
      matched-=left;
    }
    /* else (matched < prefix_len) ---> do nothing. */

    memcpy(buff,t_buff,saved_length=seg_len_pack+prefix_len);
    saved_to=buff+saved_length;
    saved_from=saved_vseg;
    saved_length=length;
    *ret_pos=page;
  }
  if (my_flag)
    flag=(keyinfo->seg->flag & HA_REVERSE_SORT) ? -my_flag : my_flag;
  if (flag == 0)
  {
    memcpy(buff,t_buff,saved_length=seg_len_pack+prefix_len);
    saved_to=buff+saved_length;
    saved_from=saved_vseg;
    saved_length=length;
  }
  if (saved_length)
    memcpy(saved_to,saved_from,saved_length);

  *last_key= page == end;

  DBUG_PRINT("exit",("flag: %d  ret_pos: %lx",flag,*ret_pos));
  DBUG_RETURN(flag);
} /* _mi_prefix_search */


        /* Get pos to a key_block */

my_off_t _mi_kpos(uint nod_flag, uchar *after_key)
{
  after_key-=nod_flag;
  switch (nod_flag) {
#if SIZEOF_OFF_T > 4
  case 7:
    return mi_uint7korr(after_key)*MI_MIN_KEY_BLOCK_LENGTH;
  case 6:
    return mi_uint6korr(after_key)*MI_MIN_KEY_BLOCK_LENGTH;
  case 5:
    return mi_uint5korr(after_key)*MI_MIN_KEY_BLOCK_LENGTH;
#else
  case 7:
    after_key++;
  case 6:
    after_key++;
  case 5:
    after_key++;
#endif
  case 4:
    return ((my_off_t) mi_uint4korr(after_key))*MI_MIN_KEY_BLOCK_LENGTH;
  case 3:
    return ((my_off_t) mi_uint3korr(after_key))*MI_MIN_KEY_BLOCK_LENGTH;
  case 2:
    return (my_off_t) (mi_uint2korr(after_key)*MI_MIN_KEY_BLOCK_LENGTH);
  case 1:
    return (uint) (*after_key)*MI_MIN_KEY_BLOCK_LENGTH;
  case 0:                                       /* At leaf page */
  default:                                      /* Impossible */
    return(HA_OFFSET_ERROR);
  }
} /* _kpos */


        /* Save pos to a key_block */

void _mi_kpointer(register MI_INFO *info, register uchar *buff, my_off_t pos)
{
  pos/=MI_MIN_KEY_BLOCK_LENGTH;
  switch (info->s->base.key_reflength) {
#if SIZEOF_OFF_T > 4
  case 7: mi_int7store(buff,pos); break;
  case 6: mi_int6store(buff,pos); break;
  case 5: mi_int5store(buff,pos); break;
#else
  case 7: *buff++=0;
    /* fall trough */
  case 6: *buff++=0;
    /* fall trough */
  case 5: *buff++=0;
    /* fall trough */
#endif
  case 4: mi_int4store(buff,pos); break;
  case 3: mi_int3store(buff,pos); break;
  case 2: mi_int2store(buff,(uint) pos); break;
  case 1: buff[0]= (uchar) pos; break;
  default: abort();                             /* impossible */
  }
} /* _mi_kpointer */


        /* Calc pos to a data-record from a key */


my_off_t _mi_dpos(MI_INFO *info, uint nod_flag, uchar *after_key)
{
  my_off_t pos;
  after_key-=(nod_flag + info->s->rec_reflength);
  switch (info->s->rec_reflength) {
#if SIZEOF_OFF_T > 4
  case 8:  pos= (my_off_t) mi_uint8korr(after_key);  break;
  case 7:  pos= (my_off_t) mi_uint7korr(after_key);  break;
  case 6:  pos= (my_off_t) mi_uint6korr(after_key);  break;
  case 5:  pos= (my_off_t) mi_uint5korr(after_key);  break;
#else
  case 8:  pos= (my_off_t) mi_uint4korr(after_key+4);   break;
  case 7:  pos= (my_off_t) mi_uint4korr(after_key+3);   break;
  case 6:  pos= (my_off_t) mi_uint4korr(after_key+2);   break;
  case 5:  pos= (my_off_t) mi_uint4korr(after_key+1);   break;
#endif
  case 4:  pos= (my_off_t) mi_uint4korr(after_key);  break;
  case 3:  pos= (my_off_t) mi_uint3korr(after_key);  break;
  case 2:  pos= (my_off_t) mi_uint2korr(after_key);  break;
  default:
    pos=0L;                                     /* Shut compiler up */
  }
  return (info->s->options &
          (HA_OPTION_PACK_RECORD | HA_OPTION_COMPRESS_RECORD)) ? pos :
            pos*info->s->base.pack_reclength;
}


/* Calc position from a record pointer ( in delete link chain ) */

my_off_t _mi_rec_pos(MYISAM_SHARE *s, uchar *ptr)
{
{'fraction_non_alphanumeric': 0.12699386503067484, 'fraction_numerical': 0.00992749581706637, 'mean_word_length': 2.483003108003108, 'pattern_counts': {'":': 0, '<': 31, '<?xml version=': 0, '>': 203, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 50, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6494758', 'n_tokens_mistral': 13319, 'n_tokens_neox': 12896, 'n_words': 2687}