mi_search.c 58.1 KB
Newer Older
unknown's avatar
unknown committed
1
/* Copyright (C) 2000-2006 MySQL AB
unknown's avatar
unknown committed
2

unknown's avatar
unknown committed
3 4
   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
unknown's avatar
unknown committed
5
   the Free Software Foundation; version 2 of the License.
unknown's avatar
unknown committed
6

unknown's avatar
unknown committed
7 8 9 10
   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.
unknown's avatar
unknown committed
11

unknown's avatar
unknown committed
12 13 14 15 16 17 18 19 20 21
   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,
22 23
                                uchar *key, uchar *keypos,
                                uint *return_key_length);
unknown's avatar
unknown committed
24

25
        /* Check index */
unknown's avatar
unknown committed
26 27 28

int _mi_check_index(MI_INFO *info, int inx)
{
29
  if (inx == -1)                        /* Use last index */
unknown's avatar
unknown committed
30
    inx=info->lastinx;
31
  if (inx < 0 || ! mi_is_key_active(info->s->state.key_map, inx))
unknown's avatar
unknown committed
32 33 34 35
  {
    my_errno=HA_ERR_WRONG_INDEX;
    return -1;
  }
36
  if (info->lastinx != inx)             /* Index changed */
unknown's avatar
unknown committed
37 38 39 40
  {
    info->lastinx = inx;
    info->page_changed=1;
    info->update= ((info->update & (HA_STATE_CHANGED | HA_STATE_ROW_CHANGED)) |
41
                   HA_STATE_NEXT_FOUND | HA_STATE_PREV_FOUND);
unknown's avatar
unknown committed
42 43 44 45 46 47 48
  }
  if (info->opt_flag & WRITE_CACHE_USED && flush_io_cache(&info->rec_cache))
    return(-1);
  return(inx);
} /* mi_check_index */


49 50 51 52 53 54
        /*
        ** 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
        */
unknown's avatar
unknown committed
55 56

int _mi_search(register MI_INFO *info, register MI_KEYDEF *keyinfo,
57
               uchar *key, uint key_len, uint nextflag, register my_off_t pos)
unknown's avatar
unknown committed
58 59 60 61 62 63 64
{
  my_bool last_key;
  int error,flag;
  uint nod_flag;
  uchar *keypos,*maxpos;
  uchar lastkey[MI_MAX_KEY_BUFF],*buff;
  DBUG_ENTER("_mi_search");
65 66
  DBUG_PRINT("enter",("pos: %lu  nextflag: %u  lastpos: %lu",
                      (ulong) pos, nextflag, (ulong) info->lastpos));
unknown's avatar
unknown committed
67 68 69 70
  DBUG_EXECUTE("key",_mi_print_key(DBUG_FILE,keyinfo->seg,key,key_len););

  if (pos == HA_OFFSET_ERROR)
  {
71
    my_errno=HA_ERR_KEY_NOT_FOUND;                      /* Didn't find key */
unknown's avatar
unknown committed
72 73
    info->lastpos= HA_OFFSET_ERROR;
    if (!(nextflag & (SEARCH_SMALLER | SEARCH_BIGGER | SEARCH_LAST)))
74 75
      DBUG_RETURN(-1);                          /* Not found ; return error */
    DBUG_RETURN(1);                             /* Search at upper levels */
unknown's avatar
unknown committed
76 77
  }

78
  if (!(buff=_mi_fetch_keypage(info,keyinfo,pos,DFLT_INIT_HITS,info->buff,
79
                               test(!(nextflag & SEARCH_SAVE_BUFF)))))
unknown's avatar
unknown committed
80 81 82 83
    goto err;
  DBUG_DUMP("page",(byte*) buff,mi_getint(buff));

  flag=(*keyinfo->bin_search)(info,keyinfo,buff,key,key_len,nextflag,
84
                              &keypos,lastkey, &last_key);
unknown's avatar
unknown committed
85 86 87 88 89 90 91 92
  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,
93
                          _mi_kpos(nod_flag,keypos))) <= 0)
unknown's avatar
unknown committed
94 95 96 97 98
      DBUG_RETURN(error);

    if (flag >0)
    {
      if (nextflag & (SEARCH_SMALLER | SEARCH_LAST) &&
99 100
          keypos == buff+2+nod_flag)
        DBUG_RETURN(1);                                 /* Bigger than key */
unknown's avatar
unknown committed
101 102
    }
    else if (nextflag & SEARCH_BIGGER && keypos >= maxpos)
103
      DBUG_RETURN(1);                                   /* Smaller than key */
unknown's avatar
unknown committed
104 105 106
  }
  else
  {
unknown's avatar
unknown committed
107 108 109
    if ((nextflag & SEARCH_FIND) && nod_flag &&
	((keyinfo->flag & (HA_NOSAME | HA_NULL_PART)) != HA_NOSAME ||
	 key_len != USE_WHOLE_KEY))
unknown's avatar
unknown committed
110 111
    {
      if ((error=_mi_search(info,keyinfo,key,key_len,SEARCH_FIND,
112 113 114
                            _mi_kpos(nod_flag,keypos))) >= 0 ||
          my_errno != HA_ERR_KEY_NOT_FOUND)
        DBUG_RETURN(error);
unknown's avatar
unknown committed
115
      info->last_keypage= HA_OFFSET_ERROR;              /* Buffer not in mem */
unknown's avatar
unknown committed
116 117 118 119 120
    }
  }
  if (pos != info->last_keypage)
  {
    uchar *old_buff=buff;
121
    if (!(buff=_mi_fetch_keypage(info,keyinfo,pos,DFLT_INIT_HITS,info->buff,
122
                                 test(!(nextflag & SEARCH_SAVE_BUFF)))))
unknown's avatar
unknown committed
123 124 125 126 127 128 129
      goto err;
    keypos=buff+(keypos-old_buff);
    maxpos=buff+(maxpos-old_buff);
  }

  if ((nextflag & (SEARCH_SMALLER | SEARCH_LAST)) && flag != 0)
  {
130
    uint not_used[2];
unknown's avatar
unknown committed
131
    if (_mi_get_prev_key(info,keyinfo, buff, info->lastkey, keypos,
132
                         &info->lastkey_length))
unknown's avatar
unknown committed
133
      goto err;
134
    if (!(nextflag & SEARCH_SMALLER) &&
unknown's avatar
unknown committed
135
        ha_key_cmp(keyinfo->seg, info->lastkey, key, key_len, SEARCH_FIND,
136
                   not_used))
unknown's avatar
unknown committed
137
    {
138
      my_errno=HA_ERR_KEY_NOT_FOUND;                    /* Didn't find key */
unknown's avatar
unknown committed
139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156
      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;
157
  info->buff_used= (info->buff != buff);        /* If we have to reread buff */
unknown's avatar
unknown committed
158

159
  DBUG_PRINT("exit",("found key at %lu",(ulong) info->lastpos));
unknown's avatar
unknown committed
160
  DBUG_RETURN(0);
unknown's avatar
unknown committed
161

unknown's avatar
unknown committed
162 163 164 165 166 167 168 169
err:
  DBUG_PRINT("exit",("Error: %d",my_errno));
  info->lastpos= HA_OFFSET_ERROR;
  info->page_changed=1;
  DBUG_RETURN (-1);
} /* _mi_search */


170 171 172 173
        /* 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 */
unknown's avatar
unknown committed
174 175

int _mi_bin_search(MI_INFO *info, register MI_KEYDEF *keyinfo, uchar *page,
176 177
                   uchar *key, uint key_len, uint comp_flag, uchar **ret_pos,
                   uchar *buff __attribute__((unused)), my_bool *last_key)
unknown's avatar
unknown committed
178 179 180
{
  reg4 int start,mid,end,save_end;
  int flag;
181
  uint totlength,nod_flag,not_used[2];
unknown's avatar
unknown committed
182 183 184 185 186 187 188 189 190 191 192 193
  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;
unknown's avatar
unknown committed
194
    if ((flag=ha_key_cmp(keyinfo->seg,page+(uint) mid*totlength,key,key_len,
195
                         comp_flag, not_used))
196
        >= 0)
unknown's avatar
unknown committed
197 198 199 200 201
      end=mid;
    else
      start=mid+1;
  }
  if (mid != start)
unknown's avatar
unknown committed
202
    flag=ha_key_cmp(keyinfo->seg,page+(uint) start*totlength,key,key_len,
203
                     comp_flag, not_used);
unknown's avatar
unknown committed
204
  if (flag < 0)
205
    start++;                    /* point at next, bigger key */
unknown's avatar
unknown committed
206 207 208 209 210 211 212
  *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 */


213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237
/*
  Locate a packed key in a key page.

  SYNOPSIS
    _mi_seq_search()
    info                        Open table information.
    keyinfo                     Key definition information.
    page                        Key page (beginning).
    key                         Search key.
    key_len                     Length to use from search key or USE_WHOLE_KEY
    comp_flag                   Search flags like SEARCH_SAME etc.
    ret_pos             RETURN  Position in key page behind this key.
    buff                RETURN  Copy of previous or identical unpacked key.
    last_key            RETURN  If key is last in page.

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

  RETURN
    > 0         Key in 'buff' is smaller than search key.
    0           Key in 'buff' is identical to search key.
    < 0         Not found.
*/
unknown's avatar
unknown committed
238 239

int _mi_seq_search(MI_INFO *info, register MI_KEYDEF *keyinfo, uchar *page,
240 241
                   uchar *key, uint key_len, uint comp_flag, uchar **ret_pos,
                   uchar *buff, my_bool *last_key)
unknown's avatar
unknown committed
242 243
{
  int flag;
244
  uint nod_flag,length,not_used[2];
unknown's avatar
unknown committed
245 246 247 248 249 250 251 252
  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;
253
  t_buff[0]=0;                                  /* Avoid bugs */
unknown's avatar
unknown committed
254 255 256 257 258
  while (page < end)
  {
    length=(*keyinfo->get_key)(keyinfo,nod_flag,&page,t_buff);
    if (length == 0 || page > end)
    {
unknown's avatar
unknown committed
259
      mi_print_error(info->s, HA_ERR_CRASHED);
unknown's avatar
unknown committed
260
      my_errno=HA_ERR_CRASHED;
unknown's avatar
unknown committed
261 262
      DBUG_PRINT("error",("Found wrong key:  length: %u  page: %lx  end: %lx",
                          length, (long) page, (long) end));
unknown's avatar
unknown committed
263 264
      DBUG_RETURN(MI_FOUND_WRONG_KEY);
    }
unknown's avatar
unknown committed
265
    if ((flag=ha_key_cmp(keyinfo->seg,t_buff,key,key_len,comp_flag,
266
                         not_used)) >= 0)
unknown's avatar
unknown committed
267 268
      break;
#ifdef EXTRA_DEBUG
unknown's avatar
unknown committed
269 270
    DBUG_PRINT("loop",("page: %lx  key: '%s'  flag: %d", (long) page, t_buff,
                       flag));
unknown's avatar
unknown committed
271 272 273 274 275
#endif
    memcpy(buff,t_buff,length);
    *ret_pos=page;
  }
  if (flag == 0)
276
    memcpy(buff,t_buff,length);                 /* Result is first key */
unknown's avatar
unknown committed
277
  *last_key= page == end;
unknown's avatar
unknown committed
278
  DBUG_PRINT("exit",("flag: %d  ret_pos: %lx", flag, (long) *ret_pos));
unknown's avatar
unknown committed
279 280 281
  DBUG_RETURN(flag);
} /* _mi_seq_search */

unknown's avatar
unknown committed
282

283 284 285 286
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)
{
287 288 289
  /*
    my_flag is raw comparison result to be changed according to
    SEARCH_NO_FIND,SEARCH_LAST and HA_REVERSE_SORT flags.
unknown's avatar
unknown committed
290
    flag is the value returned by ha_key_cmp and as treated as final
291
  */
292
  int flag=0, my_flag=-1;
unknown's avatar
unknown committed
293
  uint nod_flag, length, len, matched, cmplen, kseg_len;
294
  uint prefix_len,suffix_len;
unknown's avatar
unknown committed
295
  int key_len_skip, seg_len_pack, key_len_left;
296 297 298 299
  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;
300 301
  uint  saved_length=0, saved_prefix_len=0;
  uint  length_pack;
302 303
  DBUG_ENTER("_mi_prefix_search");

unknown's avatar
unknown committed
304 305 306 307 308 309 310
  LINT_INIT(length);
  LINT_INIT(prefix_len);
  LINT_INIT(seg_len_pack);
  LINT_INIT(saved_from);
  LINT_INIT(saved_to);
  LINT_INIT(saved_vseg);

311 312 313 314 315 316 317
  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;

318 319 320
  get_key_pack_length(kseg_len,length_pack,kseg);
  key_len_skip=length_pack+kseg_len;
  key_len_left=(int) key_len- (int) key_len_skip;
321
  /* If key_len is 0, then lenght_pack is 1, then key_len_left is -1. */
322 323
  cmplen=(key_len_left>=0) ? kseg_len : key_len-length_pack;
  DBUG_PRINT("info",("key: '%.*s'",kseg_len,kseg));
324

325 326
  /*
    Keys are compressed the following way:
327

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

331 332 333 334 335
    (prefix) length  The high bit is set if this is a prefix for the prev key.
    [suffix length]  Packed length of suffix if the previous was a prefix.
    (suffix) data    Key data bytes (past the common prefix or whole segment).
    [next-key-seg]   Next key segments (([packed length], data), ...)
    pointer          Reference to the data file (last_keyseg->length).
336
  */
337 338 339 340 341 342 343

  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;
unknown's avatar
unknown committed
344

345 346 347 348 349 350 351 352 353 354 355
    vseg=page;
    if (keyinfo->seg->length >= 127)
    {
      suffix_len=mi_uint2korr(vseg) & 32767;
      vseg+=2;
    }
    else
      suffix_len= *vseg++ & 127;

    if (packed)
    {
356 357 358
      if (suffix_len == 0)
      {
        /* == 0x80 or 0x8000, same key, prefix length == old key length. */
359
        prefix_len=len;
360
      }
361 362
      else
      {
363
        /* > 0x80 or 0x8000, this is prefix lgt, packed suffix lgt follows. */
unknown's avatar
unknown committed
364
        prefix_len=suffix_len;
365 366 367 368
        get_key_length(suffix_len,vseg);
      }
    }
    else
369 370
    {
      /* Not packed. No prefix used from last key. */
371
      prefix_len=0;
372
    }
373 374 375 376 377

    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);
unknown's avatar
unknown committed
378

379 380 381 382 383 384
    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;

385 386
    DBUG_PRINT("loop",("page: '%.*s%.*s'",prefix_len,t_buff+seg_len_pack,
		       suffix_len,vseg));
387 388
    {
      uchar *from=vseg+suffix_len;
unknown's avatar
unknown committed
389
      HA_KEYSEG *keyseg;
390 391 392 393
      uint l;

      for (keyseg=keyinfo->seg+1 ; keyseg->type ; keyseg++ )
      {
unknown's avatar
unknown committed
394

395 396 397 398 399
        if (keyseg->flag & HA_NULL_PART)
        {
          if (!(*from++))
            continue;
        }
400
        if (keyseg->flag & (HA_VAR_LENGTH_PART | HA_BLOB_PART | HA_SPACE_PACK))
401 402 403 404 405 406 407 408 409 410 411 412 413 414 415
        {
          get_key_length(l,from);
        }
        else
          l=keyseg->length;

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

    if (page > end)
    {
unknown's avatar
unknown committed
416
      mi_print_error(info->s, HA_ERR_CRASHED);
417
      my_errno=HA_ERR_CRASHED;
unknown's avatar
unknown committed
418 419
      DBUG_PRINT("error",("Found wrong key:  length: %u  page: %lx  end: %lx",
                          length, (long) page, (long) end));
420 421 422 423 424 425 426 427 428
      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;

429 430 431 432 433 434
      /*
        If prefix_len > cmplen then we are in the end-space comparison
        phase. Do not try to acces the key any more ==> left= 0.
      */
      left= ((len <= cmplen) ? suffix_len :
             ((prefix_len < cmplen) ? cmplen - prefix_len : 0));
435 436 437

      matched=prefix_len+left;

438 439 440 441 442 443 444 445 446 447 448 449
      if (sort_order)
      {
        for (my_flag=0;left;left--)
          if ((my_flag= (int) sort_order[*vseg++] - (int) sort_order[*k++]))
            break;
      }
      else
      {
        for (my_flag=0;left;left--)
          if ((my_flag= (int) *vseg++ - (int) *k++))
            break;
      }
450 451 452

      if (my_flag>0)      /* mismatch */
        break;
453 454 455
      if (my_flag==0) /* match */
      {
	/*
456 457 458 459 460 461 462 463 464 465
        **  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)
        {
466
	  if ((keyinfo->seg->type != HA_KEYTYPE_TEXT &&
467 468
	       keyinfo->seg->type != HA_KEYTYPE_VARTEXT1 &&
               keyinfo->seg->type != HA_KEYTYPE_VARTEXT2))
469 470 471
	    my_flag= -1;
	  else
	  {
472
	    /* We have to compare k and vseg as if they were space extended */
473 474 475
	    uchar *k_end= k+ (cmplen - len);
	    for ( ; k < k_end && *k == ' '; k++) ;
	    if (k == k_end)
476 477 478 479 480 481 482 483
	      goto cmp_rest;		/* should never happen */
	    if (*k < (uchar) ' ')
	    {
	      my_flag= 1;		/* Compared string is smaller */
	      break;
	    }
	    my_flag= -1;		/* Continue searching */
	  }
484 485 486
        }
        else if (len > cmplen)
        {
487
	  uchar *vseg_end;
488 489 490
	  if ((nextflag & SEARCH_PREFIX) && key_len_left == 0)
	    goto fix_flag;

491
	  /* We have to compare k and vseg as if they were space extended */
492 493
	  for (vseg_end= vseg + (len-cmplen) ;
	       vseg < vseg_end && *vseg == (uchar) ' ';
494
	       vseg++, matched++) ;
495
	  DBUG_ASSERT(vseg < vseg_end);
496 497 498 499 500 501 502

	  if (*vseg > (uchar) ' ')
	  {
	    my_flag= 1;			/* Compared string is smaller */
	    break;
	  }
	  my_flag= -1;			/* Continue searching */
503 504
        }
        else
505 506 507 508
	{
      cmp_rest:
	  if (key_len_left>0)
	  {
509
	    uint not_used[2];
510
	    if ((flag = ha_key_cmp(keyinfo->seg+1,vseg,
511
				   k, key_len_left, nextflag, not_used)) >= 0)
512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527
	      break;
	  }
	  else
	  {
	    /*
	      at this line flag==-1 if the following lines were already
	      visited and 0 otherwise,  i.e. flag <=0 here always !!!
	    */
	fix_flag:
	    DBUG_ASSERT(flag <= 0);
	    if (nextflag & (SEARCH_NO_FIND | SEARCH_LAST))
	      flag=(nextflag & (SEARCH_BIGGER | SEARCH_LAST)) ? -1 : 1;
	    if (flag>=0)
	      break;
	  }
	}
528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551
      }
      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;
unknown's avatar
unknown committed
552

unknown's avatar
unknown committed
553
  DBUG_PRINT("exit",("flag: %d  ret_pos: %lx", flag, (long) *ret_pos));
554 555 556 557 558
  DBUG_RETURN(flag);
} /* _mi_prefix_search */


        /* Get pos to a key_block */
unknown's avatar
unknown committed
559 560 561 562 563 564 565

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:
unknown's avatar
unknown committed
566
    return mi_uint7korr(after_key)*MI_MIN_KEY_BLOCK_LENGTH;
unknown's avatar
unknown committed
567
  case 6:
unknown's avatar
unknown committed
568
    return mi_uint6korr(after_key)*MI_MIN_KEY_BLOCK_LENGTH;
unknown's avatar
unknown committed
569
  case 5:
unknown's avatar
unknown committed
570
    return mi_uint5korr(after_key)*MI_MIN_KEY_BLOCK_LENGTH;
unknown's avatar
unknown committed
571 572 573 574 575 576 577 578 579
#else
  case 7:
    after_key++;
  case 6:
    after_key++;
  case 5:
    after_key++;
#endif
  case 4:
unknown's avatar
unknown committed
580
    return ((my_off_t) mi_uint4korr(after_key))*MI_MIN_KEY_BLOCK_LENGTH;
unknown's avatar
unknown committed
581
  case 3:
unknown's avatar
unknown committed
582
    return ((my_off_t) mi_uint3korr(after_key))*MI_MIN_KEY_BLOCK_LENGTH;
unknown's avatar
unknown committed
583
  case 2:
unknown's avatar
unknown committed
584
    return (my_off_t) (mi_uint2korr(after_key)*MI_MIN_KEY_BLOCK_LENGTH);
unknown's avatar
unknown committed
585
  case 1:
unknown's avatar
unknown committed
586
    return (uint) (*after_key)*MI_MIN_KEY_BLOCK_LENGTH;
587 588
  case 0:                                       /* At leaf page */
  default:                                      /* Impossible */
unknown's avatar
unknown committed
589 590 591 592 593
    return(HA_OFFSET_ERROR);
  }
} /* _kpos */


594
        /* Save pos to a key_block */
unknown's avatar
unknown committed
595 596 597

void _mi_kpointer(register MI_INFO *info, register uchar *buff, my_off_t pos)
{
unknown's avatar
unknown committed
598
  pos/=MI_MIN_KEY_BLOCK_LENGTH;
unknown's avatar
unknown committed
599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615
  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;
616
  default: abort();                             /* impossible */
unknown's avatar
unknown committed
617 618 619 620
  }
} /* _mi_kpointer */


621
        /* Calc pos to a data-record from a key */
unknown's avatar
unknown committed
622 623 624 625 626 627 628 629


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
630
  case 8:  pos= (my_off_t) mi_uint8korr(after_key);  break;
unknown's avatar
unknown committed
631 632 633 634 635
  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;
636 637 638
  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;
unknown's avatar
unknown committed
639 640 641 642 643
#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:
644
    pos=0L;                                     /* Shut compiler up */
unknown's avatar
unknown committed
645 646
  }
  return (info->s->options &
647 648
          (HA_OPTION_PACK_RECORD | HA_OPTION_COMPRESS_RECORD)) ? pos :
            pos*info->s->base.pack_reclength;
unknown's avatar
unknown committed
649 650 651 652 653 654 655 656 657 658 659 660 661
}


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

my_off_t _mi_rec_pos(MYISAM_SHARE *s, uchar *ptr)
{
  my_off_t pos;
  switch (s->rec_reflength) {
#if SIZEOF_OFF_T > 4
  case 8:
    pos= (my_off_t) mi_uint8korr(ptr);
    if (pos == HA_OFFSET_ERROR)
662
      return HA_OFFSET_ERROR;                   /* end of list */
unknown's avatar
unknown committed
663 664 665 666
    break;
  case 7:
    pos= (my_off_t) mi_uint7korr(ptr);
    if (pos == (((my_off_t) 1) << 56) -1)
667
      return HA_OFFSET_ERROR;                   /* end of list */
unknown's avatar
unknown committed
668 669 670 671
    break;
  case 6:
    pos= (my_off_t) mi_uint6korr(ptr);
    if (pos == (((my_off_t) 1) << 48) -1)
672
      return HA_OFFSET_ERROR;                   /* end of list */
unknown's avatar
unknown committed
673 674 675 676
    break;
  case 5:
    pos= (my_off_t) mi_uint5korr(ptr);
    if (pos == (((my_off_t) 1) << 40) -1)
677
      return HA_OFFSET_ERROR;                   /* end of list */
unknown's avatar
unknown committed
678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701
    break;
#else
  case 8:
  case 7:
  case 6:
  case 5:
    ptr+= (s->rec_reflength-4);
    /* fall through */
#endif
  case 4:
    pos= (my_off_t) mi_uint4korr(ptr);
    if (pos == (my_off_t) (uint32) ~0L)
      return  HA_OFFSET_ERROR;
    break;
  case 3:
    pos= (my_off_t) mi_uint3korr(ptr);
    if (pos == (my_off_t) (1 << 24) -1)
      return HA_OFFSET_ERROR;
    break;
  case 2:
    pos= (my_off_t) mi_uint2korr(ptr);
    if (pos == (my_off_t) (1 << 16) -1)
      return HA_OFFSET_ERROR;
    break;
702
  default: abort();                             /* Impossible */
unknown's avatar
unknown committed
703 704
  }
  return ((s->options &
705 706
          (HA_OPTION_PACK_RECORD | HA_OPTION_COMPRESS_RECORD)) ? pos :
          pos*s->base.pack_reclength);
unknown's avatar
unknown committed
707 708 709
}


710
        /* save position to record */
unknown's avatar
unknown committed
711 712 713 714

void _mi_dpointer(MI_INFO *info, uchar *buff, my_off_t pos)
{
  if (!(info->s->options &
715
        (HA_OPTION_PACK_RECORD | HA_OPTION_COMPRESS_RECORD)) &&
unknown's avatar
unknown committed
716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737
      pos != HA_OFFSET_ERROR)
    pos/=info->s->base.pack_reclength;

  switch (info->s->rec_reflength) {
#if SIZEOF_OFF_T > 4
  case 8: mi_int8store(buff,pos); break;
  case 7: mi_int7store(buff,pos); break;
  case 6: mi_int6store(buff,pos); break;
  case 5: mi_int5store(buff,pos); break;
#else
  case 8: *buff++=0;
    /* fall trough */
  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;
738
  default: abort();                             /* Impossible */
unknown's avatar
unknown committed
739 740 741 742
  }
} /* _mi_dpointer */


743 744 745 746 747
        /* Get key from key-block */
        /* page points at previous key; its advanced to point at next key */
        /* key should contain previous key */
        /* Returns length of found key + pointers */
        /* nod_flag is a flag if we are on nod */
unknown's avatar
unknown committed
748

749
        /* same as _mi_get_key but used with fixed length keys */
unknown's avatar
unknown committed
750 751

uint _mi_get_static_key(register MI_KEYDEF *keyinfo, uint nod_flag,
752
                       register uchar **page, register uchar *key)
unknown's avatar
unknown committed
753 754
{
  memcpy((byte*) key,(byte*) *page,
755
         (size_t) (keyinfo->keylength+nod_flag));
unknown's avatar
unknown committed
756 757 758 759 760
  *page+=keyinfo->keylength+nod_flag;
  return(keyinfo->keylength);
} /* _mi_get_static_key */


761 762 763 764 765 766 767 768 769 770 771 772 773
/*
  get key witch is packed against previous key or key with a NULL column.

  SYNOPSIS
    _mi_get_pack_key()
    keyinfo                     key definition information.
    nod_flag                    If nod: Length of node pointer, else zero.
    page_pos            RETURN  position in key page behind this key.
    key                 IN/OUT  in: prev key, out: unpacked key.

  RETURN
    key_length + length of data pointer
*/
unknown's avatar
unknown committed
774 775

uint _mi_get_pack_key(register MI_KEYDEF *keyinfo, uint nod_flag,
776
                      register uchar **page_pos, register uchar *key)
unknown's avatar
unknown committed
777
{
unknown's avatar
unknown committed
778
  reg1 HA_KEYSEG *keyseg;
unknown's avatar
unknown committed
779 780 781 782 783 784 785 786 787 788 789 790 791
  uchar *start_key,*page=*page_pos;
  uint length;

  start_key=key;
  for (keyseg=keyinfo->seg ; keyseg->type ;keyseg++)
  {
    if (keyseg->flag & HA_PACK_KEY)
    {
      /* key with length, packed to previous key */
      uchar *start=key;
      uint packed= *page & 128,tot_length,rest_length;
      if (keyseg->length >= 127)
      {
792 793
        length=mi_uint2korr(page) & 32767;
        page+=2;
unknown's avatar
unknown committed
794 795
      }
      else
796
        length= *page++ & 127;
unknown's avatar
unknown committed
797 798 799 800 801

      if (packed)
      {
	if (length > (uint) keyseg->length)
	{
unknown's avatar
unknown committed
802
          mi_print_error(keyinfo->share, HA_ERR_CRASHED);
unknown's avatar
unknown committed
803 804 805 806 807 808 809 810 811 812 813
	  my_errno=HA_ERR_CRASHED;
	  return 0;				/* Error */
	}
	if (length == 0)			/* Same key */
	{
	  if (keyseg->flag & HA_NULL_PART)
	    *key++=1;				/* Can't be NULL */
	  get_key_length(length,key);
	  key+= length;				/* Same diff_key as prev */
	  if (length > keyseg->length)
	  {
814
	    DBUG_PRINT("error",
unknown's avatar
unknown committed
815 816
                       ("Found too long null packed key: %u of %u at %lx",
                        length, keyseg->length, (long) *page_pos));
unknown's avatar
unknown committed
817
	    DBUG_DUMP("key",(char*) *page_pos,16);
unknown's avatar
unknown committed
818
            mi_print_error(keyinfo->share, HA_ERR_CRASHED);
unknown's avatar
unknown committed
819 820 821 822 823 824
	    my_errno=HA_ERR_CRASHED;
	    return 0;
	  }
	  continue;
	}
	if (keyseg->flag & HA_NULL_PART)
825
	{
826
	  key++;				/* Skip null marker*/
827 828
	  start++;
	}
unknown's avatar
unknown committed
829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853

	get_key_length(rest_length,page);
	tot_length=rest_length+length;

	/* If the stored length has changed, we must move the key */
	if (tot_length >= 255 && *start != 255)
	{
	  /* length prefix changed from a length of one to a length of 3 */
	  bmove_upp((char*) key+length+3,(char*) key+length+1,length);
	  *key=255;
	  mi_int2store(key+1,tot_length);
	  key+=3+length;
	}
	else if (tot_length < 255 && *start == 255)
	{
	  bmove(key+1,key+3,length);
	  *key=tot_length;
	  key+=1+length;
	}
	else
	{
	  store_key_length_inc(key,tot_length);
	  key+=length;
	}
	memcpy(key,page,rest_length);
unknown's avatar
unknown committed
854 855 856
	page+=rest_length;
	key+=rest_length;
	continue;
unknown's avatar
unknown committed
857 858 859
      }
      else
      {
860 861 862 863 864 865 866 867 868
        if (keyseg->flag & HA_NULL_PART)
        {
          if (!length--)                        /* Null part */
          {
            *key++=0;
            continue;
          }
          *key++=1;                             /* Not null */
        }
unknown's avatar
unknown committed
869 870 871
      }
      if (length > (uint) keyseg->length)
      {
unknown's avatar
unknown committed
872 873
        DBUG_PRINT("error",("Found too long packed key: %u of %u at %lx",
                            length, keyseg->length, (long) *page_pos));
874
        DBUG_DUMP("key",(char*) *page_pos,16);
unknown's avatar
unknown committed
875
        mi_print_error(keyinfo->share, HA_ERR_CRASHED);
876 877
        my_errno=HA_ERR_CRASHED;
        return 0;                               /* Error */
unknown's avatar
unknown committed
878 879 880 881 882 883 884
      }
      store_key_length_inc(key,length);
    }
    else
    {
      if (keyseg->flag & HA_NULL_PART)
      {
885 886
        if (!(*key++ = *page++))
          continue;
unknown's avatar
unknown committed
887 888
      }
      if (keyseg->flag &
889
          (HA_VAR_LENGTH_PART | HA_BLOB_PART | HA_SPACE_PACK))
unknown's avatar
unknown committed
890
      {
891 892 893
        uchar *tmp=page;
        get_key_length(length,tmp);
        length+=(uint) (tmp-page);
unknown's avatar
unknown committed
894 895
      }
      else
896
        length=keyseg->length;
unknown's avatar
unknown committed
897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912
    }
    memcpy((byte*) key,(byte*) page,(size_t) length);
    key+=length;
    page+=length;
  }
  length=keyseg->length+nod_flag;
  bmove((byte*) key,(byte*) page,length);
  *page_pos= page+length;
  return ((uint) (key-start_key)+keyseg->length);
} /* _mi_get_pack_key */



/* key that is packed relatively to previous */

uint _mi_get_binary_pack_key(register MI_KEYDEF *keyinfo, uint nod_flag,
913
                             register uchar **page_pos, register uchar *key)
unknown's avatar
unknown committed
914
{
unknown's avatar
unknown committed
915
  reg1 HA_KEYSEG *keyseg;
unknown's avatar
unknown committed
916
  uchar *start_key,*page,*page_end,*from,*from_end;
unknown's avatar
unknown committed
917
  uint length,tmp;
918
  DBUG_ENTER("_mi_get_binary_pack_key");
unknown's avatar
unknown committed
919

unknown's avatar
unknown committed
920
  page= *page_pos;
unknown's avatar
unknown committed
921 922 923
  page_end=page+MI_MAX_KEY_BUFF+1;
  start_key=key;

924 925 926
  /*
    Keys are compressed the following way:

927
    prefix length    Packed length of prefix common with prev key (1 or 3 bytes)
928 929 930
    for each key segment:
      [is null]        Null indicator if can be null (1 byte, zero means null)
      [length]         Packed length if varlength (1 or 3 bytes)
931
      key segment      'length' bytes of key segment value
932
    pointer          Reference to the data file (last_keyseg->length).
933 934 935 936

    get_key_length() is a macro. It gets the prefix length from 'page'
    and puts it into 'length'. It increments 'page' by 1 or 3, depending
    on the packed length of the prefix length.
937
  */
unknown's avatar
unknown committed
938 939 940 941 942
  get_key_length(length,page);
  if (length)
  {
    if (length > keyinfo->maxlength)
    {
unknown's avatar
unknown committed
943 944
      DBUG_PRINT("error",("Found too long binary packed key: %u of %u at %lx",
                          length, keyinfo->maxlength, (long) *page_pos));
unknown's avatar
unknown committed
945
      DBUG_DUMP("key",(char*) *page_pos,16);
unknown's avatar
unknown committed
946
      mi_print_error(keyinfo->share, HA_ERR_CRASHED);
unknown's avatar
unknown committed
947
      my_errno=HA_ERR_CRASHED;
948
      DBUG_RETURN(0);                                 /* Wrong key */
unknown's avatar
unknown committed
949
    }
950 951 952
    /* Key is packed against prev key, take prefix from prev key. */
    from= key;
    from_end= key + length;
unknown's avatar
unknown committed
953 954 955
  }
  else
  {
956 957 958
    /* Key is not packed against prev key, take all from page buffer. */
    from= page;
    from_end= page_end;
unknown's avatar
unknown committed
959 960 961
  }

  /*
962 963 964 965 966
    The trouble is that key can be split in two parts:
      The first part (prefix) is in from .. from_end - 1.
      The second part starts at page.
    The split can be at every byte position. So we need to check for
    the end of the first part before using every byte.
unknown's avatar
unknown committed
967 968 969 970 971
  */
  for (keyseg=keyinfo->seg ; keyseg->type ;keyseg++)
  {
    if (keyseg->flag & HA_NULL_PART)
    {
972
      /* If prefix is used up, switch to rest. */
unknown's avatar
unknown committed
973 974
      if (from == from_end) { from=page;  from_end=page_end; }
      if (!(*key++ = *from++))
975
        continue;                               /* Null part */
unknown's avatar
unknown committed
976
    }
977
    if (keyseg->flag & (HA_VAR_LENGTH_PART | HA_BLOB_PART | HA_SPACE_PACK))
unknown's avatar
unknown committed
978
    {
979
      /* If prefix is used up, switch to rest. */
unknown's avatar
unknown committed
980
      if (from == from_end) { from=page;  from_end=page_end; }
981
      /* Get length of dynamic length key part */
unknown's avatar
unknown committed
982 983
      if ((length= (*key++ = *from++)) == 255)
      {
984
        /* If prefix is used up, switch to rest. */
985 986
        if (from == from_end) { from=page;  from_end=page_end; }
        length= (uint) ((*key++ = *from++)) << 8;
987
        /* If prefix is used up, switch to rest. */
988 989
        if (from == from_end) { from=page;  from_end=page_end; }
        length+= (uint) ((*key++ = *from++));
unknown's avatar
unknown committed
990 991 992 993 994 995 996
      }
    }
    else
      length=keyseg->length;

    if ((tmp=(uint) (from_end-from)) <= length)
    {
997
      key+=tmp;                                 /* Use old key */
unknown's avatar
unknown committed
998 999 1000
      length-=tmp;
      from=page; from_end=page_end;
    }
unknown's avatar
unknown committed
1001 1002
    DBUG_PRINT("info",("key: %lx  from: %lx  length: %u",
		       (long) key, (long) from, length));
unknown's avatar
unknown committed
1003
    memmove((byte*) key, (byte*) from, (size_t) length);
unknown's avatar
unknown committed
1004 1005 1006
    key+=length;
    from+=length;
  }
1007 1008 1009 1010 1011
  /*
    Last segment (type == 0) contains length of data pointer.
    If we have mixed key blocks with data pointer and key block pointer,
    we have to copy both.
  */
unknown's avatar
unknown committed
1012 1013 1014
  length=keyseg->length+nod_flag;
  if ((tmp=(uint) (from_end-from)) <= length)
  {
1015
    /* Remaining length is less or equal max possible length. */
1016
    memcpy(key+tmp,page,length-tmp);            /* Get last part of key */
unknown's avatar
unknown committed
1017 1018 1019 1020
    *page_pos= page+length-tmp;
  }
  else
  {
1021 1022 1023 1024 1025 1026
    /*
      Remaining length is greater than max possible length.
      This can happen only if we switched to the new key bytes already.
      'page_end' is calculated with MI_MAX_KEY_BUFF. So it can be far
      behind the real end of the key.
    */
unknown's avatar
unknown committed
1027 1028 1029
    if (from_end != page_end)
    {
      DBUG_PRINT("error",("Error when unpacking key"));
unknown's avatar
unknown committed
1030
      mi_print_error(keyinfo->share, HA_ERR_CRASHED);
unknown's avatar
unknown committed
1031
      my_errno=HA_ERR_CRASHED;
1032
      DBUG_RETURN(0);                                 /* Error */
unknown's avatar
unknown committed
1033
    }
1034
    /* Copy data pointer and, if appropriate, key block pointer. */
unknown's avatar
unknown committed
1035 1036 1037
    memcpy((byte*) key,(byte*) from,(size_t) length);
    *page_pos= from+length;
  }
1038
  DBUG_RETURN((uint) (key-start_key)+keyseg->length);
unknown's avatar
unknown committed
1039 1040 1041
}


1042 1043
        /* Get key at position without knowledge of previous key */
        /* Returns pointer to next key */
unknown's avatar
unknown committed
1044 1045

uchar *_mi_get_key(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *page,
1046
                   uchar *key, uchar *keypos, uint *return_key_length)
unknown's avatar
unknown committed
1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059
{
  uint nod_flag;
  DBUG_ENTER("_mi_get_key");

  nod_flag=mi_test_if_nod(page);
  if (! (keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)))
  {
    bmove((byte*) key,(byte*) keypos,keyinfo->keylength+nod_flag);
    DBUG_RETURN(keypos+keyinfo->keylength+nod_flag);
  }
  else
  {
    page+=2+nod_flag;
1060
    key[0]=0;                                   /* safety */
unknown's avatar
unknown committed
1061 1062 1063 1064 1065
    while (page <= keypos)
    {
      *return_key_length=(*keyinfo->get_key)(keyinfo,nod_flag,&page,key);
      if (*return_key_length == 0)
      {
unknown's avatar
unknown committed
1066
        mi_print_error(info->s, HA_ERR_CRASHED);
1067 1068
        my_errno=HA_ERR_CRASHED;
        DBUG_RETURN(0);
unknown's avatar
unknown committed
1069 1070 1071
      }
    }
  }
unknown's avatar
unknown committed
1072 1073
  DBUG_PRINT("exit",("page: %lx  length: %u", (long) page,
                     *return_key_length));
unknown's avatar
unknown committed
1074 1075 1076 1077
  DBUG_RETURN(page);
} /* _mi_get_key */


1078 1079
        /* Get key at position without knowledge of previous key */
        /* Returns 0 if ok */
unknown's avatar
unknown committed
1080 1081

static my_bool _mi_get_prev_key(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *page,
1082 1083
                                uchar *key, uchar *keypos,
                                uint *return_key_length)
unknown's avatar
unknown committed
1084 1085 1086 1087 1088 1089 1090 1091 1092
{
  uint nod_flag;
  DBUG_ENTER("_mi_get_prev_key");

  nod_flag=mi_test_if_nod(page);
  if (! (keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)))
  {
    *return_key_length=keyinfo->keylength;
    bmove((byte*) key,(byte*) keypos- *return_key_length-nod_flag,
1093
          *return_key_length);
unknown's avatar
unknown committed
1094 1095 1096 1097 1098
    DBUG_RETURN(0);
  }
  else
  {
    page+=2+nod_flag;
1099
    key[0]=0;                                   /* safety */
unknown's avatar
unknown committed
1100 1101 1102 1103 1104
    while (page < keypos)
    {
      *return_key_length=(*keyinfo->get_key)(keyinfo,nod_flag,&page,key);
      if (*return_key_length == 0)
      {
unknown's avatar
unknown committed
1105
        mi_print_error(info->s, HA_ERR_CRASHED);
1106 1107
        my_errno=HA_ERR_CRASHED;
        DBUG_RETURN(1);
unknown's avatar
unknown committed
1108 1109 1110 1111 1112 1113 1114 1115
      }
    }
  }
  DBUG_RETURN(0);
} /* _mi_get_key */



1116 1117
        /* Get last key from key-page */
        /* Return pointer to where key starts */
unknown's avatar
unknown committed
1118 1119

uchar *_mi_get_last_key(MI_INFO *info, MI_KEYDEF *keyinfo, uchar *page,
1120
                        uchar *lastkey, uchar *endpos, uint *return_key_length)
unknown's avatar
unknown committed
1121 1122 1123 1124
{
  uint nod_flag;
  uchar *lastpos;
  DBUG_ENTER("_mi_get_last_key");
unknown's avatar
unknown committed
1125
  DBUG_PRINT("enter",("page: %lx  endpos: %lx", (long) page, (long) endpos));
unknown's avatar
unknown committed
1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144

  nod_flag=mi_test_if_nod(page);
  if (! (keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)))
  {
    lastpos=endpos-keyinfo->keylength-nod_flag;
    *return_key_length=keyinfo->keylength;
    if (lastpos > page)
      bmove((byte*) lastkey,(byte*) lastpos,keyinfo->keylength+nod_flag);
  }
  else
  {
    lastpos=(page+=2+nod_flag);
    lastkey[0]=0;
    while (page < endpos)
    {
      lastpos=page;
      *return_key_length=(*keyinfo->get_key)(keyinfo,nod_flag,&page,lastkey);
      if (*return_key_length == 0)
      {
unknown's avatar
unknown committed
1145 1146
        DBUG_PRINT("error",("Couldn't find last key:  page: %lx",
                            (long) page));
unknown's avatar
unknown committed
1147
        mi_print_error(info->s, HA_ERR_CRASHED);
1148 1149
        my_errno=HA_ERR_CRASHED;
        DBUG_RETURN(0);
unknown's avatar
unknown committed
1150 1151 1152
      }
    }
  }
unknown's avatar
unknown committed
1153 1154
  DBUG_PRINT("exit",("lastpos: %lx  length: %u", (long) lastpos,
                     *return_key_length));
unknown's avatar
unknown committed
1155 1156 1157 1158
  DBUG_RETURN(lastpos);
} /* _mi_get_last_key */


1159
        /* Calculate length of key */
unknown's avatar
unknown committed
1160 1161 1162

uint _mi_keylength(MI_KEYDEF *keyinfo, register uchar *key)
{
unknown's avatar
unknown committed
1163
  reg1 HA_KEYSEG *keyseg;
unknown's avatar
unknown committed
1164 1165 1166 1167 1168 1169 1170 1171 1172 1173
  uchar *start;

  if (! (keyinfo->flag & (HA_VAR_LENGTH_KEY | HA_BINARY_PACK_KEY)))
    return (keyinfo->keylength);

  start=key;
  for (keyseg=keyinfo->seg ; keyseg->type ; keyseg++)
  {
    if (keyseg->flag & HA_NULL_PART)
      if (!*key++)
1174
        continue;
1175
    if (keyseg->flag & (HA_SPACE_PACK | HA_BLOB_PART | HA_VAR_LENGTH_PART))
unknown's avatar
unknown committed
1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187
    {
      uint length;
      get_key_length(length,key);
      key+=length;
    }
    else
      key+= keyseg->length;
  }
  return((uint) (key-start)+keyseg->length);
} /* _mi_keylength */


1188 1189 1190 1191 1192 1193 1194 1195 1196
/*
  Calculate length of part key.

  Used in mi_rkey() to find the key found for the key-part that was used.
  This is needed in case of multi-byte character sets where we may search
  after '0xDF' but find 'ss'
*/

uint _mi_keylength_part(MI_KEYDEF *keyinfo, register uchar *key,
unknown's avatar
unknown committed
1197
			HA_KEYSEG *end)
1198
{
unknown's avatar
unknown committed
1199
  reg1 HA_KEYSEG *keyseg;
1200 1201 1202 1203 1204 1205 1206
  uchar *start= key;

  for (keyseg=keyinfo->seg ; keyseg != end ; keyseg++)
  {
    if (keyseg->flag & HA_NULL_PART)
      if (!*key++)
        continue;
1207
    if (keyseg->flag & (HA_SPACE_PACK | HA_BLOB_PART | HA_VAR_LENGTH_PART))
1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218
    {
      uint length;
      get_key_length(length,key);
      key+=length;
    }
    else
      key+= keyseg->length;
  }
  return (uint) (key-start);
}

1219
        /* Move a key */
unknown's avatar
unknown committed
1220 1221 1222 1223 1224

uchar *_mi_move_key(MI_KEYDEF *keyinfo, uchar *to, uchar *from)
{
  reg1 uint length;
  memcpy((byte*) to, (byte*) from,
1225
         (size_t) (length=_mi_keylength(keyinfo,from)));
unknown's avatar
unknown committed
1226 1227 1228
  return to+length;
}

1229 1230
        /* Find next/previous record with same key */
        /* This can't be used when database is touched after last read */
unknown's avatar
unknown committed
1231 1232

int _mi_search_next(register MI_INFO *info, register MI_KEYDEF *keyinfo,
1233
                    uchar *key, uint key_length, uint nextflag, my_off_t pos)
unknown's avatar
unknown committed
1234 1235 1236 1237 1238
{
  int error;
  uint nod_flag;
  uchar lastkey[MI_MAX_KEY_BUFF];
  DBUG_ENTER("_mi_search_next");
1239 1240 1241
  DBUG_PRINT("enter",("nextflag: %u  lastpos: %lu  int_keypos: %lu",
                      nextflag, (ulong) info->lastpos,
                      (ulong) info->int_keypos));
unknown's avatar
unknown committed
1242 1243 1244
  DBUG_EXECUTE("key",_mi_print_key(DBUG_FILE,keyinfo->seg,key,key_length););

  /* Force full read if we are at last key or if we are not on a leaf
1245 1246 1247 1248 1249
     and the key tree has changed since we used it last time
     Note that even if the key tree has changed since last read, we can use
     the last read data from the leaf if we haven't used the buffer for
     something else.
  */
unknown's avatar
unknown committed
1250 1251 1252 1253 1254

  if (((nextflag & SEARCH_BIGGER) && info->int_keypos >= info->int_maxpos) ||
      info->page_changed ||
      (info->int_keytree_version != keyinfo->version &&
       (info->int_nod_flag || info->buff_used)))
unknown's avatar
unknown committed
1255
    DBUG_RETURN(_mi_search(info,keyinfo,key, USE_WHOLE_KEY,
1256
                           nextflag | SEARCH_SAVE_BUFF, pos));
unknown's avatar
unknown committed
1257 1258 1259 1260

  if (info->buff_used)
  {
    if (!_mi_fetch_keypage(info,keyinfo,info->last_search_keypage,
1261
                           DFLT_INIT_HITS,info->buff,0))
unknown's avatar
unknown committed
1262 1263 1264 1265 1266 1267 1268
      DBUG_RETURN(-1);
    info->buff_used=0;
  }

  /* Last used buffer is in info->buff */
  nod_flag=mi_test_if_nod(info->buff);

1269
  if (nextflag & SEARCH_BIGGER)                                 /* Next key */
unknown's avatar
unknown committed
1270 1271 1272 1273
  {
    my_off_t tmp_pos=_mi_kpos(nod_flag,info->int_keypos);
    if (tmp_pos != HA_OFFSET_ERROR)
    {
unknown's avatar
unknown committed
1274
      if ((error=_mi_search(info,keyinfo,key, USE_WHOLE_KEY,
1275 1276
                            nextflag | SEARCH_SAVE_BUFF, tmp_pos)) <=0)
        DBUG_RETURN(error);
unknown's avatar
unknown committed
1277
    }
unknown's avatar
unknown committed
1278
    memcpy(lastkey,key,key_length);
unknown's avatar
unknown committed
1279
    if (!(info->lastkey_length=(*keyinfo->get_key)(keyinfo,nod_flag,
1280
                                                   &info->int_keypos,lastkey)))
unknown's avatar
unknown committed
1281 1282
      DBUG_RETURN(-1);
  }
1283
  else                                                  /* Previous key */
unknown's avatar
unknown committed
1284 1285 1286 1287
  {
    uint length;
    /* Find start of previous key */
    info->int_keypos=_mi_get_last_key(info,keyinfo,info->buff,lastkey,
1288
                                      info->int_keypos, &length);
unknown's avatar
unknown committed
1289 1290 1291
    if (!info->int_keypos)
      DBUG_RETURN(-1);
    if (info->int_keypos == info->buff+2)
unknown's avatar
unknown committed
1292
      DBUG_RETURN(_mi_search(info,keyinfo,key, USE_WHOLE_KEY,
1293
                             nextflag | SEARCH_SAVE_BUFF, pos));
unknown's avatar
unknown committed
1294 1295
    if ((error=_mi_search(info,keyinfo,key, USE_WHOLE_KEY,
			  nextflag | SEARCH_SAVE_BUFF,
1296
                          _mi_kpos(nod_flag,info->int_keypos))) <= 0)
unknown's avatar
unknown committed
1297 1298
      DBUG_RETURN(error);

unknown's avatar
unknown committed
1299
    /* QQ: We should be able to optimize away the following call */
unknown's avatar
unknown committed
1300
    if (! _mi_get_last_key(info,keyinfo,info->buff,lastkey,
1301
                           info->int_keypos,&info->lastkey_length))
unknown's avatar
unknown committed
1302 1303 1304 1305
      DBUG_RETURN(-1);
  }
  memcpy(info->lastkey,lastkey,info->lastkey_length);
  info->lastpos=_mi_dpos(info,0,info->lastkey+info->lastkey_length);
1306
  DBUG_PRINT("exit",("found key at %lu",(ulong) info->lastpos));
unknown's avatar
unknown committed
1307 1308 1309 1310
  DBUG_RETURN(0);
} /* _mi_search_next */


1311 1312
        /* Search after position for the first row in an index */
        /* This is stored in info->lastpos */
unknown's avatar
unknown committed
1313 1314

int _mi_search_first(register MI_INFO *info, register MI_KEYDEF *keyinfo,
1315
                     register my_off_t pos)
unknown's avatar
unknown committed
1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329
{
  uint nod_flag;
  uchar *page;
  DBUG_ENTER("_mi_search_first");

  if (pos == HA_OFFSET_ERROR)
  {
    my_errno=HA_ERR_KEY_NOT_FOUND;
    info->lastpos= HA_OFFSET_ERROR;
    DBUG_RETURN(-1);
  }

  do
  {
1330
    if (!_mi_fetch_keypage(info,keyinfo,pos,DFLT_INIT_HITS,info->buff,0))
unknown's avatar
unknown committed
1331 1332 1333 1334 1335 1336 1337 1338
    {
      info->lastpos= HA_OFFSET_ERROR;
      DBUG_RETURN(-1);
    }
    nod_flag=mi_test_if_nod(info->buff);
    page=info->buff+2+nod_flag;
  } while ((pos=_mi_kpos(nod_flag,page)) != HA_OFFSET_ERROR);

1339
  if (!(info->lastkey_length=(*keyinfo->get_key)(keyinfo,nod_flag,&page,
unknown's avatar
unknown committed
1340 1341 1342
                                                 info->lastkey)))
    DBUG_RETURN(-1);                            /* Crashed */

unknown's avatar
unknown committed
1343 1344 1345 1346 1347 1348 1349
  info->int_keypos=page; info->int_maxpos=info->buff+mi_getint(info->buff)-1;
  info->int_nod_flag=nod_flag;
  info->int_keytree_version=keyinfo->version;
  info->last_search_keypage=info->last_keypage;
  info->page_changed=info->buff_used=0;
  info->lastpos=_mi_dpos(info,0,info->lastkey+info->lastkey_length);

1350
  DBUG_PRINT("exit",("found key at %lu", (ulong) info->lastpos));
unknown's avatar
unknown committed
1351 1352 1353 1354
  DBUG_RETURN(0);
} /* _mi_search_first */


1355 1356
        /* Search after position for the last row in an index */
        /* This is stored in info->lastpos */
unknown's avatar
unknown committed
1357 1358

int _mi_search_last(register MI_INFO *info, register MI_KEYDEF *keyinfo,
1359
                    register my_off_t pos)
unknown's avatar
unknown committed
1360 1361 1362 1363 1364 1365 1366
{
  uint nod_flag;
  uchar *buff,*page;
  DBUG_ENTER("_mi_search_last");

  if (pos == HA_OFFSET_ERROR)
  {
1367
    my_errno=HA_ERR_KEY_NOT_FOUND;                      /* Didn't find key */
unknown's avatar
unknown committed
1368 1369 1370 1371 1372 1373 1374
    info->lastpos= HA_OFFSET_ERROR;
    DBUG_RETURN(-1);
  }

  buff=info->buff;
  do
  {
1375
    if (!_mi_fetch_keypage(info,keyinfo,pos,DFLT_INIT_HITS,buff,0))
unknown's avatar
unknown committed
1376 1377 1378 1379 1380 1381 1382 1383 1384
    {
      info->lastpos= HA_OFFSET_ERROR;
      DBUG_RETURN(-1);
    }
    page= buff+mi_getint(buff);
    nod_flag=mi_test_if_nod(buff);
  } while ((pos=_mi_kpos(nod_flag,page)) != HA_OFFSET_ERROR);

  if (!_mi_get_last_key(info,keyinfo,buff,info->lastkey,page,
1385
                        &info->lastkey_length))
unknown's avatar
unknown committed
1386 1387 1388 1389 1390 1391 1392 1393
    DBUG_RETURN(-1);
  info->lastpos=_mi_dpos(info,0,info->lastkey+info->lastkey_length);
  info->int_keypos=info->int_maxpos=page;
  info->int_nod_flag=nod_flag;
  info->int_keytree_version=keyinfo->version;
  info->last_search_keypage=info->last_keypage;
  info->page_changed=info->buff_used=0;

1394
  DBUG_PRINT("exit",("found key at %lu",(ulong) info->lastpos));
unknown's avatar
unknown committed
1395 1396 1397 1398 1399 1400 1401 1402 1403 1404
  DBUG_RETURN(0);
} /* _mi_search_last */



/****************************************************************************
**
** Functions to store and pack a key in a page
**
** mi_calc_xx_key_length takes the following arguments:
1405 1406 1407 1408 1409 1410
**  nod_flag    If nod: Length of nod-pointer
**  next_key    Position to pos after the new key in buffer
**  org_key     Key that was before the next key in buffer
**  prev_key    Last key before current key
**  key         Key that will be stored
**  s_temp      Information how next key will be packed
unknown's avatar
unknown committed
1411 1412 1413 1414 1415 1416
****************************************************************************/

/* Static length key */

int
_mi_calc_static_key_length(MI_KEYDEF *keyinfo,uint nod_flag,
1417 1418 1419 1420
                           uchar *next_pos  __attribute__((unused)),
                           uchar *org_key  __attribute__((unused)),
                           uchar *prev_key __attribute__((unused)),
                           uchar *key, MI_KEY_PARAM *s_temp)
unknown's avatar
unknown committed
1421 1422 1423 1424 1425 1426 1427 1428 1429
{
  s_temp->key=key;
  return (int) (s_temp->totlength=keyinfo->keylength+nod_flag);
}

/* Variable length key */

int
_mi_calc_var_key_length(MI_KEYDEF *keyinfo,uint nod_flag,
1430 1431 1432 1433
                        uchar *next_pos  __attribute__((unused)),
                        uchar *org_key  __attribute__((unused)),
                        uchar *prev_key __attribute__((unused)),
                        uchar *key, MI_KEY_PARAM *s_temp)
unknown's avatar
unknown committed
1434 1435 1436 1437 1438 1439 1440 1441 1442 1443 1444
{
  s_temp->key=key;
  return (int) (s_temp->totlength=_mi_keylength(keyinfo,key)+nod_flag);
}

/*
  length of key with a variable length first segment which is prefix
  compressed (myisamchk reports 'packed + stripped')

  Keys are compressed the following way:

1445
  If the max length of first key segment <= 127 bytes the prefix is
1446
  1 byte else it's 2 byte
unknown's avatar
unknown committed
1447

1448
  prefix byte(s) The high bit is set if this is a prefix for the prev key
1449
  length         Packed length if the previous was a prefix byte
1450
  [length]       data bytes ('length' bytes)
1451
  next-key-seg   Next key segments
unknown's avatar
unknown committed
1452 1453 1454 1455 1456 1457 1458 1459

  If the first segment can have NULL:
  The length is 0 for NULLS and 1+length for not null columns.

*/

int
_mi_calc_var_pack_key_length(MI_KEYDEF *keyinfo,uint nod_flag,uchar *next_key,
1460 1461
                             uchar *org_key, uchar *prev_key, uchar *key,
                             MI_KEY_PARAM *s_temp)
unknown's avatar
unknown committed
1462
{
unknown's avatar
unknown committed
1463
  reg1 HA_KEYSEG *keyseg;
unknown's avatar
unknown committed
1464 1465 1466 1467 1468 1469 1470 1471 1472 1473 1474 1475 1476
  int length;
  uint key_length,ref_length,org_key_length=0,
       length_pack,new_key_length,diff_flag,pack_marker;
  uchar *start,*end,*key_end,*sort_order;
  bool same_length;

  length_pack=s_temp->ref_length=s_temp->n_ref_length=s_temp->n_length=0;
  same_length=0; keyseg=keyinfo->seg;
  key_length=_mi_keylength(keyinfo,key)+nod_flag;

  sort_order=0;
  if ((keyinfo->flag & HA_FULLTEXT) &&
      ((keyseg->type == HA_KEYTYPE_TEXT) ||
1477 1478
       (keyseg->type == HA_KEYTYPE_VARTEXT1) ||
       (keyseg->type == HA_KEYTYPE_VARTEXT2)) &&
1479
      !use_strnxfrm(keyseg->charset))
unknown's avatar
unknown committed
1480 1481 1482 1483 1484 1485 1486 1487 1488 1489 1490 1491 1492 1493 1494 1495 1496 1497 1498 1499 1500
    sort_order=keyseg->charset->sort_order;

  /* diff flag contains how many bytes is needed to pack key */
  if (keyseg->length >= 127)
  {
    diff_flag=2;
    pack_marker=32768;
  }
  else
  {
    diff_flag= 1;
    pack_marker=128;
  }
  s_temp->pack_marker=pack_marker;

  /* Handle the case that the first part have NULL values */
  if (keyseg->flag & HA_NULL_PART)
  {
    if (!*key++)
    {
      s_temp->key=key;
1501
      s_temp->key_length= 0;
unknown's avatar
unknown committed
1502
      s_temp->totlength=key_length-1+diff_flag;
1503
      s_temp->next_key_pos=0;                   /* No next key */
unknown's avatar
unknown committed
1504 1505 1506
      return (s_temp->totlength);
    }
    s_temp->store_not_null=1;
1507
    key_length--;                               /* We don't store NULL */
unknown's avatar
unknown committed
1508
    if (prev_key && !*prev_key++)
1509
      org_key=prev_key=0;                       /* Can't pack against prev */
unknown's avatar
unknown committed
1510
    else if (org_key)
1511
      org_key++;                                /* Skip NULL */
unknown's avatar
unknown committed
1512 1513 1514 1515 1516 1517 1518 1519 1520 1521 1522 1523 1524 1525 1526
  }
  else
    s_temp->store_not_null=0;
  s_temp->prev_key=org_key;

  /* The key part will start with a packed length */

  get_key_pack_length(new_key_length,length_pack,key);
  end=key_end= key+ new_key_length;
  start=key;

  /* Calc how many characters are identical between this and the prev. key */
  if (prev_key)
  {
    get_key_length(org_key_length,prev_key);
1527
    s_temp->prev_key=prev_key;          /* Pointer at data */
unknown's avatar
unknown committed
1528 1529 1530 1531
    /* Don't use key-pack if length == 0 */
    if (new_key_length && new_key_length == org_key_length)
      same_length=1;
    else if (new_key_length > org_key_length)
1532
      end=key + org_key_length;
unknown's avatar
unknown committed
1533

1534
    if (sort_order)                             /* SerG */
unknown's avatar
unknown committed
1535 1536 1537 1538 1539 1540 1541 1542 1543 1544
    {
      while (key < end && sort_order[*key] == sort_order[*prev_key])
      {
        key++; prev_key++;
      }
    }
    else
    {
      while (key < end && *key == *prev_key)
      {
1545
        key++; prev_key++;
unknown's avatar
unknown committed
1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556 1557 1558 1559
      }
    }
  }

  s_temp->key=key;
  s_temp->key_length= (uint) (key_end-key);

  if (same_length && key == key_end)
  {
    /* identical variable length key */
    s_temp->ref_length= pack_marker;
    length=(int) key_length-(int) (key_end-start)-length_pack;
    length+= diff_flag;
    if (next_key)
1560 1561
    {                                           /* Can't combine with next */
      s_temp->n_length= *next_key;              /* Needed by _mi_store_key */
unknown's avatar
unknown committed
1562 1563 1564 1565 1566 1567
      next_key=0;
    }
  }
  else
  {
    if (start != key)
1568
    {                                           /* Starts as prev key */
unknown's avatar
unknown committed
1569 1570 1571 1572 1573 1574 1575 1576 1577 1578
      ref_length= (uint) (key-start);
      s_temp->ref_length= ref_length + pack_marker;
      length= (int) (key_length - ref_length);

      length-= length_pack;
      length+= diff_flag;
      length+= ((new_key_length-ref_length) >= 255) ? 3 : 1;/* Rest_of_key */
    }
    else
    {
1579
      s_temp->key_length+=s_temp->store_not_null;       /* If null */
unknown's avatar
unknown committed
1580 1581 1582 1583 1584
      length= key_length - length_pack+ diff_flag;
    }
  }
  s_temp->totlength=(uint) length;
  s_temp->prev_length=0;
1585 1586
  DBUG_PRINT("test",("tot_length: %u  length: %d  uniq_key_length: %u",
                     key_length, length, s_temp->key_length));
unknown's avatar
unknown committed
1587

1588
        /* If something after that hasn't length=0, test if we can combine */
unknown's avatar
unknown committed
1589 1590 1591 1592 1593 1594 1595 1596 1597 1598 1599 1600 1601 1602 1603
  if ((s_temp->next_key_pos=next_key))
  {
    uint packed,n_length;

    packed = *next_key & 128;
    if (diff_flag == 2)
    {
      n_length= mi_uint2korr(next_key) & 32767; /* Length of next key */
      next_key+=2;
    }
    else
      n_length= *next_key++ & 127;
    if (!packed)
      n_length-= s_temp->store_not_null;

1604
    if (n_length || packed)             /* Don't pack 0 length keys */
unknown's avatar
unknown committed
1605 1606 1607 1608 1609
    {
      uint next_length_pack, new_ref_length=s_temp->ref_length;

      if (packed)
      {
1610 1611 1612 1613 1614 1615 1616 1617 1618 1619 1620 1621 1622 1623 1624 1625 1626 1627 1628 1629 1630 1631 1632 1633 1634 1635 1636 1637 1638 1639 1640 1641 1642 1643
        /* If first key and next key is packed (only on delete) */
        if (!prev_key && org_key)
        {
          get_key_length(org_key_length,org_key);
          key=start;
          if (sort_order)                       /* SerG */
          {
            while (key < end && sort_order[*key] == sort_order[*org_key])
            {
              key++; org_key++;
            }
          }
          else
          {
            while (key < end && *key == *org_key)
            {
              key++; org_key++;
            }
          }
          if ((new_ref_length= (uint) (key - start)))
            new_ref_length+=pack_marker;
        }

        if (!n_length)
        {
          /*
            We put a different key between two identical variable length keys
            Extend next key to have same prefix as this key
          */
          if (new_ref_length)                   /* prefix of previus key */
          {                                     /* make next key longer */
            s_temp->part_of_prev_key= new_ref_length;
            s_temp->prev_length=          org_key_length -
              (new_ref_length-pack_marker);
1644 1645
            s_temp->n_ref_length= s_temp->part_of_prev_key;
            s_temp->n_length= s_temp->prev_length;
1646 1647 1648 1649 1650 1651 1652 1653 1654 1655 1656 1657 1658 1659 1660
            n_length=             get_pack_length(s_temp->prev_length);
            s_temp->prev_key+=    (new_ref_length - pack_marker);
            length+=              s_temp->prev_length + n_length;
          }
          else
          {                                     /* Can't use prev key */
            s_temp->part_of_prev_key=0;
            s_temp->prev_length= org_key_length;
            s_temp->n_ref_length=s_temp->n_length=  org_key_length;
            length+=           org_key_length;
          }
          return (int) length;
        }

        ref_length=n_length;
1661
        /* Get information about not packed key suffix */
1662 1663 1664 1665 1666 1667 1668 1669 1670 1671 1672 1673 1674 1675 1676 1677 1678 1679
        get_key_pack_length(n_length,next_length_pack,next_key);

        /* Test if new keys has fewer characters that match the previous key */
        if (!new_ref_length)
        {                                       /* Can't use prev key */
          s_temp->part_of_prev_key=     0;
          s_temp->prev_length=          ref_length;
          s_temp->n_ref_length= s_temp->n_length= n_length+ref_length;
          return (int) length+ref_length-next_length_pack;
        }
        if (ref_length+pack_marker > new_ref_length)
        {
          uint new_pack_length=new_ref_length-pack_marker;
          /* We must copy characters from the original key to the next key */
          s_temp->part_of_prev_key= new_ref_length;
          s_temp->prev_length=      ref_length - new_pack_length;
          s_temp->n_ref_length=s_temp->n_length=n_length + s_temp->prev_length;
          s_temp->prev_key+=        new_pack_length;
1680
          length-= (next_length_pack - get_pack_length(s_temp->n_length));
1681 1682
          return (int) length + s_temp->prev_length;
        }
unknown's avatar
unknown committed
1683 1684 1685
      }
      else
      {
1686 1687 1688
        /* Next key wasn't a prefix of previous key */
        ref_length=0;
        next_length_pack=0;
1689
      }
unknown's avatar
unknown committed
1690 1691
      DBUG_PRINT("test",("length: %d  next_key: %lx", length,
                         (long) next_key));
unknown's avatar
unknown committed
1692 1693

      {
1694 1695 1696 1697 1698 1699
        uint tmp_length;
        key=(start+=ref_length);
        if (key+n_length < key_end)             /* Normalize length based */
          key_end=key+n_length;
        if (sort_order)                         /* SerG */
        {
unknown's avatar
unknown committed
1700
          while (key < key_end && sort_order[*key] ==
1701 1702 1703 1704 1705 1706 1707 1708 1709 1710 1711 1712 1713 1714 1715 1716 1717 1718 1719 1720
                 sort_order[*next_key])
          {
            key++; next_key++;
          }
        }
        else
        {
          while (key < key_end && *key == *next_key)
          {
            key++; next_key++;
          }
        }
        if (!(tmp_length=(uint) (key-start)))
        {                                       /* Key can't be re-packed */
          s_temp->next_key_pos=0;
          return length;
        }
        ref_length+=tmp_length;
        n_length-=tmp_length;
        length-=tmp_length+next_length_pack;    /* We gained these chars */
unknown's avatar
unknown committed
1721
      }
1722
      if (n_length == 0 && ref_length == new_key_length)
unknown's avatar
unknown committed
1723
      {
1724
        s_temp->n_ref_length=pack_marker;       /* Same as prev key */
unknown's avatar
unknown committed
1725 1726 1727
      }
      else
      {
1728 1729 1730
        s_temp->n_ref_length=ref_length | pack_marker;
        length+= get_pack_length(n_length);
        s_temp->n_length=n_length;
unknown's avatar
unknown committed
1731 1732 1733 1734 1735 1736 1737 1738 1739 1740 1741
      }
    }
  }
  return length;
}


/* Length of key which is prefix compressed */

int
_mi_calc_bin_pack_key_length(MI_KEYDEF *keyinfo,uint nod_flag,uchar *next_key,
1742 1743
                             uchar *org_key, uchar *prev_key, uchar *key,
                             MI_KEY_PARAM *s_temp)
unknown's avatar
unknown committed
1744 1745 1746 1747
{
  uint length,key_length,ref_length;

  s_temp->totlength=key_length=_mi_keylength(keyinfo,key)+nod_flag;
unknown's avatar
unknown committed
1748 1749 1750
#ifdef HAVE_purify
  s_temp->n_length= s_temp->n_ref_length=0;	/* For valgrind */
#endif
unknown's avatar
unknown committed
1751 1752
  s_temp->key=key;
  s_temp->prev_key=org_key;
1753
  if (prev_key)                                 /* If not first key in block */
unknown's avatar
unknown committed
1754 1755 1756 1757 1758 1759 1760 1761 1762 1763 1764 1765 1766 1767 1768 1769 1770 1771
  {
    /* pack key against previous key */
    /*
      As keys may be identical when running a sort in myisamchk, we
      have to guard against the case where keys may be identical
    */
    uchar *end;
    end=key+key_length;
    for ( ; *key == *prev_key && key < end; key++,prev_key++) ;
    s_temp->ref_length= ref_length=(uint) (key-s_temp->key);
    length=key_length - ref_length + get_pack_length(ref_length);
  }
  else
  {
    /* No previous key */
    s_temp->ref_length=ref_length=0;
    length=key_length+1;
  }
1772
  if ((s_temp->next_key_pos=next_key))          /* If another key after */
unknown's avatar
unknown committed
1773 1774 1775 1776 1777 1778 1779 1780 1781 1782
  {
    /* pack key against next key */
    uint next_length,next_length_pack;
    get_key_pack_length(next_length,next_length_pack,next_key);

    /* If first key and next key is packed (only on delete) */
    if (!prev_key && org_key && next_length)
    {
      uchar *end;
      for (key= s_temp->key, end=key+next_length ;
1783 1784
           *key == *org_key && key < end;
           key++,org_key++) ;
unknown's avatar
unknown committed
1785 1786 1787 1788 1789 1790
      ref_length= (uint) (key - s_temp->key);
    }

    if (next_length > ref_length)
    {
      /* We put a key with different case between two keys with the same prefix
1791 1792
         Extend next key to have same prefix as
         this key */
unknown's avatar
unknown committed
1793 1794 1795 1796
      s_temp->n_ref_length= ref_length;
      s_temp->prev_length=  next_length-ref_length;
      s_temp->prev_key+=    ref_length;
      return (int) (length+ s_temp->prev_length - next_length_pack +
1797
                    get_pack_length(ref_length));
unknown's avatar
unknown committed
1798 1799 1800 1801 1802 1803 1804
    }
    /* Check how many characters are identical to next key */
    key= s_temp->key+next_length;
    while (*key++ == *next_key++) ;
    if ((ref_length= (uint) (key - s_temp->key)-1) == next_length)
    {
      s_temp->next_key_pos=0;
1805
      return length;                            /* can't pack next key */
unknown's avatar
unknown committed
1806 1807 1808 1809
    }
    s_temp->prev_length=0;
    s_temp->n_ref_length=ref_length;
    return (int) (length-(ref_length - next_length) - next_length_pack +
1810
                  get_pack_length(ref_length));
unknown's avatar
unknown committed
1811 1812 1813 1814 1815 1816 1817 1818 1819 1820 1821 1822
  }
  return (int) length;
}


/*
** store a key packed with _mi_calc_xxx_key_length in page-buffert
*/

/* store key without compression */

void _mi_store_static_key(MI_KEYDEF *keyinfo __attribute__((unused)),
1823 1824
                          register uchar *key_pos,
                          register MI_KEY_PARAM *s_temp)
unknown's avatar
unknown committed
1825 1826 1827 1828 1829 1830 1831 1832 1833 1834 1835 1836 1837
{
  memcpy((byte*) key_pos,(byte*) s_temp->key,(size_t) s_temp->totlength);
}


/* store variable length key with prefix compression */

#define store_pack_length(test,pos,length) { \
  if (test) { *((pos)++) = (uchar) (length); } else \
  { *((pos)++) = (uchar) ((length) >> 8); *((pos)++) = (uchar) (length);  } }


void _mi_store_var_pack_key(MI_KEYDEF *keyinfo  __attribute__((unused)),
1838 1839
                            register uchar *key_pos,
                            register MI_KEY_PARAM *s_temp)
unknown's avatar
unknown committed
1840 1841 1842 1843 1844 1845 1846 1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 1857 1858 1859
{
  uint length;
  uchar *start;

  start=key_pos;

  if (s_temp->ref_length)
  {
    /* Packed against previous key */
    store_pack_length(s_temp->pack_marker == 128,key_pos,s_temp->ref_length);
    /* If not same key after */
    if (s_temp->ref_length != s_temp->pack_marker)
      store_key_length_inc(key_pos,s_temp->key_length);
  }
  else
  {
    /* Not packed against previous key */
    store_pack_length(s_temp->pack_marker == 128,key_pos,s_temp->key_length);
  }
  bmove((byte*) key_pos,(byte*) s_temp->key,
1860
        (length=s_temp->totlength-(uint) (key_pos-start)));
unknown's avatar
unknown committed
1861

1862
  if (!s_temp->next_key_pos)                    /* No following key */
unknown's avatar
unknown committed
1863 1864 1865 1866 1867 1868 1869 1870 1871
    return;
  key_pos+=length;

  if (s_temp->prev_length)
  {
    /* Extend next key because new key didn't have same prefix as prev key */
    if (s_temp->part_of_prev_key)
    {
      store_pack_length(s_temp->pack_marker == 128,key_pos,
1872
                        s_temp->part_of_prev_key);
unknown's avatar
unknown committed
1873 1874 1875 1876 1877 1878
      store_key_length_inc(key_pos,s_temp->n_length);
    }
    else
    {
      s_temp->n_length+= s_temp->store_not_null;
      store_pack_length(s_temp->pack_marker == 128,key_pos,
1879
                        s_temp->n_length);
unknown's avatar
unknown committed
1880 1881 1882 1883 1884 1885 1886
    }
    memcpy(key_pos, s_temp->prev_key, s_temp->prev_length);
  }
  else if (s_temp->n_ref_length)
  {
    store_pack_length(s_temp->pack_marker == 128,key_pos,s_temp->n_ref_length);
    if (s_temp->n_ref_length == s_temp->pack_marker)
1887
      return;                                   /* Identical key */
unknown's avatar
unknown committed
1888 1889 1890 1891 1892 1893 1894 1895 1896 1897 1898 1899 1900
    store_key_length(key_pos,s_temp->n_length);
  }
  else
  {
    s_temp->n_length+= s_temp->store_not_null;
    store_pack_length(s_temp->pack_marker == 128,key_pos,s_temp->n_length);
  }
}


/* variable length key with prefix compression */

void _mi_store_bin_pack_key(MI_KEYDEF *keyinfo  __attribute__((unused)),
1901 1902
                            register uchar *key_pos,
                            register MI_KEY_PARAM *s_temp)
unknown's avatar
unknown committed
1903 1904 1905
{
  store_key_length_inc(key_pos,s_temp->ref_length);
  memcpy((char*) key_pos,(char*) s_temp->key+s_temp->ref_length,
1906
          (size_t) s_temp->totlength-s_temp->ref_length);
unknown's avatar
unknown committed
1907 1908 1909 1910 1911

  if (s_temp->next_key_pos)
  {
    key_pos+=(uint) (s_temp->totlength-s_temp->ref_length);
    store_key_length_inc(key_pos,s_temp->n_ref_length);
1912
    if (s_temp->prev_length)                    /* If we must extend key */
unknown's avatar
unknown committed
1913 1914 1915 1916 1917
    {
      memcpy(key_pos,s_temp->prev_key,s_temp->prev_length);
    }
  }
}