hp_hash.c 27.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
   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 */

/* The hash functions used for saveing keys */

#include "heapdef.h"
#include <m_ctype.h>

21 22 23 24 25 26 27 28 29


/*
  Find out how many rows there is in the given range

  SYNOPSIS
    hp_rb_records_in_range()
    info		HEAP handler
    inx			Index to use
unknown's avatar
unknown committed
30 31
    min_key		Min key. Is = 0 if no min range
    max_key		Max key. Is = 0 if no max range
32 33

  NOTES
unknown's avatar
unknown committed
34
    min_key.flag can have one of the following values:
35 36 37
      HA_READ_KEY_EXACT		Include the key in the range
      HA_READ_AFTER_KEY		Don't include key in range

unknown's avatar
unknown committed
38
    max_key.flag can have one of the following values:  
39 40 41 42 43 44 45 46 47 48
      HA_READ_BEFORE_KEY	Don't include key in range
      HA_READ_AFTER_KEY		Include all 'end_key' values in the range

  RETURN
   HA_POS_ERROR		Something is wrong with the index tree.
   0			There is no matching keys in the given range
   number > 0		There is approximately 'number' matching rows in
			the range.
*/

unknown's avatar
unknown committed
49 50
ha_rows hp_rb_records_in_range(HP_INFO *info, int inx,  key_range *min_key,
                               key_range *max_key)
51 52
{
  ha_rows start_pos, end_pos;
unknown's avatar
unknown committed
53 54
  HP_KEYDEF *keyinfo= info->s->keydef + inx;
  TREE *rb_tree = &keyinfo->rb_tree;
55
  heap_rb_param custom_arg;
56
  DBUG_ENTER("hp_rb_records_in_range");
57

unknown's avatar
unknown committed
58 59 60
  info->lastinx= inx;
  custom_arg.keyseg= keyinfo->seg;
  custom_arg.search_flag= SEARCH_FIND | SEARCH_SAME;
unknown's avatar
unknown committed
61
  if (min_key)
62
  {
unknown's avatar
unknown committed
63
    custom_arg.key_length= hp_rb_pack_key(keyinfo, (uchar*) info->recbuf,
unknown's avatar
unknown committed
64 65 66
					  (uchar*) min_key->key,
					  min_key->length);
    start_pos= tree_record_pos(rb_tree, info->recbuf, min_key->flag,
unknown's avatar
unknown committed
67
			       &custom_arg);
68 69 70 71 72 73
  }
  else
  {
    start_pos= 0;
  }
  
unknown's avatar
unknown committed
74
  if (max_key)
75
  {
unknown's avatar
unknown committed
76
    custom_arg.key_length= hp_rb_pack_key(keyinfo, (uchar*) info->recbuf,
unknown's avatar
unknown committed
77 78 79
					  (uchar*) max_key->key,
                                          max_key->length);
    end_pos= tree_record_pos(rb_tree, info->recbuf, max_key->flag,
unknown's avatar
unknown committed
80
			     &custom_arg);
81 82 83 84 85 86
  }
  else
  {
    end_pos= rb_tree->elements_in_tree + (ha_rows)1;
  }

87 88
  DBUG_PRINT("info",("start_pos: %lu  end_pos: %lu", (ulong) start_pos,
		     (ulong) end_pos));
89
  if (start_pos == HA_POS_ERROR || end_pos == HA_POS_ERROR)
90 91 92
    DBUG_RETURN(HA_POS_ERROR);
  DBUG_RETURN(end_pos < start_pos ? (ha_rows) 0 :
	      (end_pos == start_pos ? (ha_rows) 1 : end_pos - start_pos));
93 94
}

unknown's avatar
unknown committed
95

unknown's avatar
unknown committed
96 97 98 99
	/* Search after a record based on a key */
	/* Sets info->current_ptr to found record */
	/* next_flag:  Search=0, next=1, prev =2, same =3 */

100
byte *hp_search(HP_INFO *info, HP_KEYDEF *keyinfo, const byte *key,
unknown's avatar
unknown committed
101
                uint nextflag)
unknown's avatar
unknown committed
102 103 104 105 106
{
  reg1 HASH_INFO *pos,*prev_ptr;
  int flag;
  uint old_nextflag;
  HP_SHARE *share=info->s;
107
  DBUG_ENTER("hp_search");
unknown's avatar
unknown committed
108 109 110 111 112 113
  old_nextflag=nextflag;
  flag=1;
  prev_ptr=0;

  if (share->records)
  {
114 115
    pos=hp_find_hash(&keyinfo->block, hp_mask(hp_hashnr(keyinfo, key),
					      share->blength, share->records));
unknown's avatar
unknown committed
116 117
    do
    {
118
      if (!hp_key_cmp(keyinfo, pos->ptr_to_rec, key))
unknown's avatar
unknown committed
119 120 121
      {
	switch (nextflag) {
	case 0:					/* Search after key */
unknown's avatar
unknown committed
122
	  DBUG_PRINT("exit", ("found key at 0x%lx", (long) pos->ptr_to_rec));
unknown's avatar
unknown committed
123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149
	  info->current_hash_ptr=pos;
	  DBUG_RETURN(info->current_ptr= pos->ptr_to_rec);
	case 1:					/* Search next */
	  if (pos->ptr_to_rec == info->current_ptr)
	    nextflag=0;
	  break;
	case 2:					/* Search previous */
	  if (pos->ptr_to_rec == info->current_ptr)
	  {
	    my_errno=HA_ERR_KEY_NOT_FOUND;	/* If gpos == 0 */
	    info->current_hash_ptr=prev_ptr;
	    DBUG_RETURN(info->current_ptr=prev_ptr ? prev_ptr->ptr_to_rec : 0);
	  }
	  prev_ptr=pos;				/* Prev. record found */
	  break;
	case 3:					/* Search same */
	  if (pos->ptr_to_rec == info->current_ptr)
	  {
	    info->current_hash_ptr=pos;
	    DBUG_RETURN(info->current_ptr);
	  }
	}
      }
      if (flag)
      {
	flag=0;					/* Reset flag */
	if (hp_find_hash(&keyinfo->block,
150 151
			 hp_mask(hp_rec_hashnr(keyinfo, pos->ptr_to_rec),
				  share->blength, share->records)) != pos)
unknown's avatar
unknown committed
152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177
	  break;				/* Wrong link */
      }
    }
    while ((pos=pos->next_key));
  }
  my_errno=HA_ERR_KEY_NOT_FOUND;
  if (nextflag == 2 && ! info->current_ptr)
  {
    /* Do a previous from end */
    info->current_hash_ptr=prev_ptr;
    DBUG_RETURN(info->current_ptr=prev_ptr ? prev_ptr->ptr_to_rec : 0);
  }

  if (old_nextflag && nextflag)
    my_errno=HA_ERR_RECORD_CHANGED;		/* Didn't find old record */
  DBUG_PRINT("exit",("Error: %d",my_errno));
  info->current_hash_ptr=0;  
  DBUG_RETURN((info->current_ptr= 0));
}


/*
  Search next after last read;  Assumes that the table hasn't changed
  since last read !
*/

178
byte *hp_search_next(HP_INFO *info, HP_KEYDEF *keyinfo, const byte *key,
unknown's avatar
unknown committed
179 180
		      HASH_INFO *pos)
{
181
  DBUG_ENTER("hp_search_next");
unknown's avatar
unknown committed
182 183 184

  while ((pos= pos->next_key))
  {
185
    if (! hp_key_cmp(keyinfo, pos->ptr_to_rec, key))
unknown's avatar
unknown committed
186 187 188 189 190 191 192 193 194 195 196 197
    {
      info->current_hash_ptr=pos;
      DBUG_RETURN (info->current_ptr= pos->ptr_to_rec);
    }
  }
  my_errno=HA_ERR_KEY_NOT_FOUND;
  DBUG_PRINT("exit",("Error: %d",my_errno));
  info->current_hash_ptr=0;
  DBUG_RETURN ((info->current_ptr= 0));
}


198 199 200 201 202 203 204 205 206 207 208 209
/*
  Calculate position number for hash value.
  SYNOPSIS
    hp_mask()
      hashnr     Hash value
      buffmax    Value such that
                 2^(n-1) < maxlength <= 2^n = buffmax
      maxlength  
  
  RETURN
    Array index, in [0..maxlength)
*/
unknown's avatar
unknown committed
210

211
ulong hp_mask(ulong hashnr, ulong buffmax, ulong maxlength)
unknown's avatar
unknown committed
212 213 214 215 216 217
{
  if ((hashnr & (buffmax-1)) < maxlength) return (hashnr & (buffmax-1));
  return (hashnr & ((buffmax >> 1) -1));
}


218 219 220 221 222 223
/*
  Change
    next_link -> ... -> X -> pos
  to
    next_link -> ... -> X -> newlink
*/
unknown's avatar
unknown committed
224

225
void hp_movelink(HASH_INFO *pos, HASH_INFO *next_link, HASH_INFO *newlink)
unknown's avatar
unknown committed
226 227 228 229 230 231 232 233 234 235 236
{
  HASH_INFO *old_link;
  do
  {
    old_link=next_link;
  }
  while ((next_link=next_link->next_key) != pos);
  old_link->next_key=newlink;
  return;
}

unknown's avatar
unknown committed
237
#ifndef NEW_HASH_FUNCTION
unknown's avatar
unknown committed
238 239 240

	/* Calc hashvalue for a key */

241
ulong hp_hashnr(register HP_KEYDEF *keydef, register const byte *key)
unknown's avatar
unknown committed
242
{
243 244
  /*register*/ 
  ulong nr=1, nr2=4;
unknown's avatar
unknown committed
245
  HA_KEYSEG *seg,*endseg;
unknown's avatar
unknown committed
246 247 248

  for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
  {
unknown's avatar
unknown committed
249 250
    uchar *pos=(uchar*) key;
    key+=seg->length;
251 252
    if (seg->null_bit)
    {
253
      key++;					/* Skip null byte */
254 255 256
      if (*pos)					/* Found null */
      {
	nr^= (nr << 1) | 1;
257 258 259
	/* Add key pack length (2) to key for VARCHAR segments */
        if (seg->type == HA_KEYTYPE_VARTEXT1)
          key+= 2;
260 261 262 263
	continue;
      }
      pos++;
    }
unknown's avatar
unknown committed
264 265
    if (seg->type == HA_KEYTYPE_TEXT)
    {
unknown's avatar
unknown committed
266
       CHARSET_INFO *cs= seg->charset;
267
       uint length= seg->length;
unknown's avatar
unknown committed
268
       if (cs->mbmaxlen > 1)
unknown's avatar
unknown committed
269
       {
270
         uint char_length;
unknown's avatar
unknown committed
271
         char_length= my_charpos(cs, pos, pos + length, length/cs->mbmaxlen);
272
         set_if_smaller(length, char_length);
unknown's avatar
unknown committed
273
       }
274 275
       cs->coll->hash_sort(cs, pos, length, &nr, &nr2);
    }
276
    else if (seg->type == HA_KEYTYPE_VARTEXT1)  /* Any VARCHAR segments */
277 278
    {
       CHARSET_INFO *cs= seg->charset;
279
       uint pack_length= 2;                     /* Key packing is constant */
280 281 282 283
       uint length= uint2korr(pos);
       if (cs->mbmaxlen > 1)
       {
         uint char_length;
284 285
         char_length= my_charpos(cs, pos +pack_length,
                                 pos +pack_length + length,
286 287 288
                                 seg->length/cs->mbmaxlen);
         set_if_smaller(length, char_length);
       }
289 290
       cs->coll->hash_sort(cs, pos+pack_length, length, &nr, &nr2);
       key+= pack_length;
unknown's avatar
unknown committed
291 292 293
    }
    else
    {
unknown's avatar
unknown committed
294
      for (; pos < (uchar*) key ; pos++)
unknown's avatar
unknown committed
295
      {
296
	nr^=(ulong) ((((uint) nr & 63)+nr2)*((uint) *pos)) + (nr << 8);
unknown's avatar
unknown committed
297 298 299 300
	nr2+=3;
      }
    }
  }
301
  DBUG_PRINT("exit", ("hash: 0x%lx", nr));
unknown's avatar
unknown committed
302 303 304 305 306
  return((ulong) nr);
}

	/* Calc hashvalue for a key in a record */

307
ulong hp_rec_hashnr(register HP_KEYDEF *keydef, register const byte *rec)
unknown's avatar
unknown committed
308
{
309
  ulong nr=1, nr2=4;
unknown's avatar
unknown committed
310
  HA_KEYSEG *seg,*endseg;
unknown's avatar
unknown committed
311 312 313

  for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
  {
unknown's avatar
unknown committed
314
    uchar *pos=(uchar*) rec+seg->start,*end=pos+seg->length;
315 316 317 318 319 320 321 322
    if (seg->null_bit)
    {
      if (rec[seg->null_pos] & seg->null_bit)
      {
	nr^= (nr << 1) | 1;
	continue;
      }
    }
unknown's avatar
unknown committed
323 324
    if (seg->type == HA_KEYTYPE_TEXT)
    {
unknown's avatar
unknown committed
325
      CHARSET_INFO *cs= seg->charset;
unknown's avatar
unknown committed
326 327
      uint char_length= seg->length;
      if (cs->mbmaxlen > 1)
unknown's avatar
unknown committed
328
      {
unknown's avatar
unknown committed
329 330 331
        char_length= my_charpos(cs, pos, pos + char_length,
                                char_length / cs->mbmaxlen);
        set_if_smaller(char_length, seg->length); /* QQ: ok to remove? */
unknown's avatar
unknown committed
332 333
      }
      cs->coll->hash_sort(cs, pos, char_length, &nr, &nr2);
unknown's avatar
unknown committed
334
    }
335
    else if (seg->type == HA_KEYTYPE_VARTEXT1)  /* Any VARCHAR segments */
336 337
    {
      CHARSET_INFO *cs= seg->charset;
338 339
      uint pack_length= seg->bit_start;
      uint length= (pack_length == 1 ? (uint) *(uchar*) pos : uint2korr(pos));
340 341 342
      if (cs->mbmaxlen > 1)
      {
        uint char_length;
343 344
        char_length= my_charpos(cs, pos + pack_length,
                                pos + pack_length + length,
345 346 347
                                seg->length/cs->mbmaxlen);
        set_if_smaller(length, char_length);
      }
348
      cs->coll->hash_sort(cs, pos+pack_length, length, &nr, &nr2);
349
    }
unknown's avatar
unknown committed
350 351
    else
    {
unknown's avatar
unknown committed
352
      for (; pos < end ; pos++)
unknown's avatar
unknown committed
353 354 355 356 357 358
      {
	nr^=(ulong) ((((uint) nr & 63)+nr2)*((uint) *pos))+ (nr << 8);
	nr2+=3;
      }
    }
  }
359 360
  DBUG_PRINT("exit", ("hash: 0x%lx", nr));
  return(nr);
unknown's avatar
unknown committed
361 362
}

unknown's avatar
unknown committed
363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379
#else

/*
 * Fowler/Noll/Vo hash
 *
 * The basis of the hash algorithm was taken from an idea sent by email to the
 * IEEE Posix P1003.2 mailing list from Phong Vo (kpv@research.att.com) and
 * Glenn Fowler (gsf@research.att.com).  Landon Curt Noll (chongo@toad.com)
 * later improved on their algorithm.
 *
 * The magic is in the interesting relationship between the special prime
 * 16777619 (2^24 + 403) and 2^32 and 2^8.
 *
 * This hash produces the fewest collisions of any function that we've seen so
 * far, and works well on both numbers and strings.
 */

380
ulong hp_hashnr(register HP_KEYDEF *keydef, register const byte *key)
unknown's avatar
unknown committed
381
{
382 383 384 385 386 387 388
  /*
    Note, if a key consists of a combination of numeric and
    a text columns, it most likely won't work well.
    Making text columns work with NEW_HASH_FUNCTION
    needs also changes in strings/ctype-xxx.c.
  */
  ulong nr= 1, nr2= 4;
unknown's avatar
unknown committed
389
  HA_KEYSEG *seg,*endseg;
unknown's avatar
unknown committed
390 391 392 393 394

  for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
  {
    uchar *pos=(uchar*) key;
    key+=seg->length;
395 396 397 398 399 400
    if (seg->null_bit)
    {
      key++;
      if (*pos)
      {
	nr^= (nr << 1) | 1;
401 402 403
	/* Add key pack length (2) to key for VARCHAR segments */
        if (seg->type == HA_KEYTYPE_VARTEXT1)
          key+= 2;
404 405 406 407
	continue;
      }
      pos++;
    }
unknown's avatar
unknown committed
408 409
    if (seg->type == HA_KEYTYPE_TEXT)
    {
410 411
      seg->charset->coll->hash_sort(seg->charset, pos, ((uchar*)key)-pos,
                                    &nr, &nr2);
unknown's avatar
unknown committed
412
    }
413
    else if (seg->type == HA_KEYTYPE_VARTEXT1)  /* Any VARCHAR segments */
414
    {
415
      uint pack_length= 2;                      /* Key packing is constant */
416
      uint length= uint2korr(pos);
417 418
      seg->charset->coll->hash_sort(seg->charset, pos+pack_length, length,
                                    &nr, &nr2);
419
      key+= pack_length;
420
    }
unknown's avatar
unknown committed
421 422 423 424 425 426 427 428 429
    else
    {
      for ( ; pos < (uchar*) key ; pos++)
      {
	nr *=16777619; 
	nr ^=(uint) *pos;
      }
    }
  }
430 431
  DBUG_PRINT("exit", ("hash: 0x%lx", nr));
  return(nr);
unknown's avatar
unknown committed
432 433 434 435
}

	/* Calc hashvalue for a key in a record */

436
ulong hp_rec_hashnr(register HP_KEYDEF *keydef, register const byte *rec)
unknown's avatar
unknown committed
437
{
438
  ulong nr= 1, nr2= 4;
unknown's avatar
unknown committed
439
  HA_KEYSEG *seg,*endseg;
unknown's avatar
unknown committed
440 441 442

  for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
  {
443
    uchar *pos=(uchar*) rec+seg->start;
444 445 446 447 448 449 450 451
    if (seg->null_bit)
    {
      if (rec[seg->null_pos] & seg->null_bit)
      {
	nr^= (nr << 1) | 1;
	continue;
      }
    }
unknown's avatar
unknown committed
452 453
    if (seg->type == HA_KEYTYPE_TEXT)
    {
454 455 456
      uint char_length= seg->length; /* TODO: fix to use my_charpos() */
      seg->charset->coll->hash_sort(seg->charset, pos, char_length,
                                    &nr, &nr2);
unknown's avatar
unknown committed
457
    }
458
    else if (seg->type == HA_KEYTYPE_VARTEXT1)  /* Any VARCHAR segments */
459
    {
460 461
      uint pack_length= seg->bit_start;
      uint length= (pack_length == 1 ? (uint) *(uchar*) pos : uint2korr(pos));
462 463
      seg->charset->coll->hash_sort(seg->charset, pos+pack_length,
                                    length, &nr, &nr2);
464
    }
unknown's avatar
unknown committed
465 466
    else
    {
467
      uchar *end= pos+seg->length;
unknown's avatar
unknown committed
468 469 470 471 472 473 474
      for ( ; pos < end ; pos++)
      {
	nr *=16777619; 
	nr ^=(uint) *pos;
      }
    }
  }
475 476
  DBUG_PRINT("exit", ("hash: 0x%lx", nr));
  return(nr);
unknown's avatar
unknown committed
477 478 479 480 481
}

#endif


482 483
/*
  Compare keys for two records. Returns 0 if they are identical
unknown's avatar
unknown committed
484

485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503
  SYNOPSIS
    hp_rec_key_cmp()
    keydef		Key definition
    rec1		Record to compare
    rec2		Other record to compare
    diff_if_only_endspace_difference
			Different number of end space is significant    

  NOTES
    diff_if_only_endspace_difference is used to allow us to insert
    'a' and 'a ' when there is an an unique key.

  RETURN
    0		Key is identical
    <> 0 	Key differes
*/

int hp_rec_key_cmp(HP_KEYDEF *keydef, const byte *rec1, const byte *rec2,
                   my_bool diff_if_only_endspace_difference)
unknown's avatar
unknown committed
504
{
unknown's avatar
unknown committed
505
  HA_KEYSEG *seg,*endseg;
unknown's avatar
unknown committed
506 507 508

  for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
  {
509 510 511 512 513 514 515 516
    if (seg->null_bit)
    {
      if ((rec1[seg->null_pos] & seg->null_bit) !=
	  (rec2[seg->null_pos] & seg->null_bit))
	return 1;
      if (rec1[seg->null_pos] & seg->null_bit)
	continue;
    }
517 518
    if (seg->type == HA_KEYTYPE_TEXT)
    {
unknown's avatar
unknown committed
519 520 521 522 523
      CHARSET_INFO *cs= seg->charset;
      uint char_length1;
      uint char_length2;
      uchar *pos1= (uchar*)rec1 + seg->start;
      uchar *pos2= (uchar*)rec2 + seg->start;
unknown's avatar
unknown committed
524
      if (cs->mbmaxlen > 1)
unknown's avatar
unknown committed
525
      {
unknown's avatar
unknown committed
526
        uint char_length= seg->length / cs->mbmaxlen;
unknown's avatar
unknown committed
527
        char_length1= my_charpos(cs, pos1, pos1 + seg->length, char_length);
528
        set_if_smaller(char_length1, seg->length);
unknown's avatar
unknown committed
529
        char_length2= my_charpos(cs, pos2, pos2 + seg->length, char_length);
530
        set_if_smaller(char_length2, seg->length);
unknown's avatar
unknown committed
531 532 533 534 535
      }
      else
      {
        char_length1= char_length2= seg->length;
      }
unknown's avatar
Fix:  
unknown committed
536
      if (seg->charset->coll->strnncollsp(seg->charset,
unknown's avatar
unknown committed
537
      					  pos1,char_length1,
538 539 540
					  pos2,char_length2, 0))
	return 1;
    }
541
    else if (seg->type == HA_KEYTYPE_VARTEXT1)  /* Any VARCHAR segments */
542
    {
543 544 545 546
      uchar *pos1= (uchar*) rec1 + seg->start;
      uchar *pos2= (uchar*) rec2 + seg->start;
      uint char_length1, char_length2;
      uint pack_length= seg->bit_start;
547
      CHARSET_INFO *cs= seg->charset;
548 549 550 551 552 553 554 555 556 557 558 559
      if (pack_length == 1)
      {
        char_length1= (uint) *(uchar*) pos1++;
        char_length2= (uint) *(uchar*) pos2++;
      }
      else
      {
        char_length1= uint2korr(pos1);
        char_length2= uint2korr(pos2);
        pos1+= 2;
        pos2+= 2;
      }
560 561
      if (cs->mbmaxlen > 1)
      {
unknown's avatar
unknown committed
562 563
        uint safe_length1= char_length1;
        uint safe_length2= char_length2;
564
        uint char_length= seg->length / cs->mbmaxlen;
unknown's avatar
unknown committed
565 566 567 568
        char_length1= my_charpos(cs, pos1, pos1 + char_length1, char_length);
        set_if_smaller(char_length1, safe_length1);
        char_length2= my_charpos(cs, pos2, pos2 + char_length2, char_length);
        set_if_smaller(char_length2, safe_length2);
569 570 571
      }

      if (cs->coll->strnncollsp(seg->charset,
572 573
                                pos1, char_length1,
                                pos2, char_length2,
574 575
                                seg->flag & HA_END_SPACE_ARE_EQUAL ?
                                0 : diff_if_only_endspace_difference))
unknown's avatar
unknown committed
576
	return 1;
577 578 579
    }
    else
    {
unknown's avatar
unknown committed
580 581 582 583 584 585 586
      if (bcmp(rec1+seg->start,rec2+seg->start,seg->length))
	return 1;
    }
  }
  return 0;
}

587
	/* Compare a key in a record to a whole key */
unknown's avatar
unknown committed
588

589
int hp_key_cmp(HP_KEYDEF *keydef, const byte *rec, const byte *key)
unknown's avatar
unknown committed
590
{
unknown's avatar
unknown committed
591
  HA_KEYSEG *seg,*endseg;
unknown's avatar
unknown committed
592

593 594 595
  for (seg=keydef->seg,endseg=seg+keydef->keysegs ;
       seg < endseg ;
       key+= (seg++)->length)
unknown's avatar
unknown committed
596
  {
597 598 599 600 601 602
    if (seg->null_bit)
    {
      int found_null=test(rec[seg->null_pos] & seg->null_bit);
      if (found_null != (int) *key++)
	return 1;
      if (found_null)
603 604 605 606
      {
        /* Add key pack length (2) to key for VARCHAR segments */
        if (seg->type == HA_KEYTYPE_VARTEXT1)
          key+= 2;
607
	continue;
608
      }
609
    }
unknown's avatar
unknown committed
610 611
    if (seg->type == HA_KEYTYPE_TEXT)
    {
unknown's avatar
unknown committed
612 613 614 615
      CHARSET_INFO *cs= seg->charset;
      uint char_length_key;
      uint char_length_rec;
      uchar *pos= (uchar*) rec + seg->start;
unknown's avatar
unknown committed
616
      if (cs->mbmaxlen > 1)
unknown's avatar
unknown committed
617
      {
unknown's avatar
unknown committed
618
        uint char_length= seg->length / cs->mbmaxlen;
unknown's avatar
unknown committed
619 620 621 622 623 624 625 626 627 628 629
        char_length_key= my_charpos(cs, key, key + seg->length, char_length);
        set_if_smaller(char_length_key, seg->length);
        char_length_rec= my_charpos(cs, pos, pos + seg->length, char_length);
        set_if_smaller(char_length_rec, seg->length);
      }
      else
      {
        char_length_key= seg->length;
        char_length_rec= seg->length;
      }
      
unknown's avatar
Fix:  
unknown committed
630
      if (seg->charset->coll->strnncollsp(seg->charset,
unknown's avatar
unknown committed
631
					  (uchar*) pos, char_length_rec,
632 633 634
					  (uchar*) key, char_length_key, 0))
	return 1;
    }
635
    else if (seg->type == HA_KEYTYPE_VARTEXT1)  /* Any VARCHAR segments */
636 637 638
    {
      uchar *pos= (uchar*) rec + seg->start;
      CHARSET_INFO *cs= seg->charset;
639 640 641 642
      uint pack_length= seg->bit_start;
      uint char_length_rec= (pack_length == 1 ? (uint) *(uchar*) pos :
                             uint2korr(pos));
      /* Key segments are always packed with 2 bytes */
643
      uint char_length_key= uint2korr(key);
644 645
      pos+= pack_length;
      key+= 2;                                  /* skip key pack length */
646 647
      if (cs->mbmaxlen > 1)
      {
648 649 650 651 652 653
        uint char_length1, char_length2;
        char_length1= char_length2= seg->length / cs->mbmaxlen; 
        char_length1= my_charpos(cs, key, key + char_length_key, char_length1);
        set_if_smaller(char_length_key, char_length1);
        char_length2= my_charpos(cs, pos, pos + char_length_rec, char_length2);
        set_if_smaller(char_length_rec, char_length2);
654 655 656
      }

      if (cs->coll->strnncollsp(seg->charset,
657 658
                                (uchar*) pos, char_length_rec,
                                (uchar*) key, char_length_key, 0))
unknown's avatar
unknown committed
659 660 661 662 663 664 665 666 667 668 669 670 671 672
	return 1;
    }
    else
    {
      if (bcmp(rec+seg->start,key,seg->length))
	return 1;
    }
  }
  return 0;
}


	/* Copy a key from a record to a keybuffer */

673
void hp_make_key(HP_KEYDEF *keydef, byte *key, const byte *rec)
unknown's avatar
unknown committed
674
{
unknown's avatar
unknown committed
675
  HA_KEYSEG *seg,*endseg;
unknown's avatar
unknown committed
676 677 678

  for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
  {
unknown's avatar
unknown committed
679
    CHARSET_INFO *cs= seg->charset;
unknown's avatar
unknown committed
680
    uint char_length= seg->length;
unknown's avatar
unknown committed
681
    uchar *pos= (uchar*) rec + seg->start;
682 683
    if (seg->null_bit)
      *key++= test(rec[seg->null_pos] & seg->null_bit);
unknown's avatar
unknown committed
684
    if (cs->mbmaxlen > 1)
unknown's avatar
unknown committed
685
    {
unknown's avatar
unknown committed
686 687 688
      char_length= my_charpos(cs, pos, pos + seg->length,
                              char_length / cs->mbmaxlen);
      set_if_smaller(char_length, seg->length); /* QQ: ok to remove? */
unknown's avatar
unknown committed
689
    }
690 691
    if (seg->type == HA_KEYTYPE_VARTEXT1)
      char_length+= seg->bit_start;             /* Copy also length */
unknown's avatar
unknown committed
692 693
    memcpy(key,rec+seg->start,(size_t) char_length);
    key+= char_length;
unknown's avatar
unknown committed
694 695
  }
}
696

697 698 699 700 701 702 703
#define FIX_LENGTH(cs, pos, length, char_length)                        \
  do {                                                                  \
    if (length > char_length)                                           \
      char_length= my_charpos(cs, pos, pos+length, char_length);        \
    set_if_smaller(char_length,length);                                 \
  } while(0)

unknown's avatar
unknown committed
704

705
uint hp_rb_make_key(HP_KEYDEF *keydef, byte *key, 
706 707
		    const byte *rec, byte *recpos)
{
708
  byte *start_key= key;
unknown's avatar
unknown committed
709
  HA_KEYSEG *seg, *endseg;
710

711
  for (seg= keydef->seg, endseg= seg + keydef->keysegs; seg < endseg; seg++)
712
  {
unknown's avatar
unknown committed
713
    uint char_length;
714
    if (seg->null_bit)
715 716 717 718
    {
      if (!(*key++= 1 - test(rec[seg->null_pos] & seg->null_bit)))
        continue;
    }
719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755
    if (seg->flag & HA_SWAP_KEY)
    {
      uint length= seg->length;
      byte *pos= (byte*) rec + seg->start;
      
#ifdef HAVE_ISNAN
      if (seg->type == HA_KEYTYPE_FLOAT)
      {
	float nr;
	float4get(nr, pos);
	if (isnan(nr))
	{
	  /* Replace NAN with zero */
 	  bzero(key, length);
	  key+= length;
	  continue;
	}
      }
      else if (seg->type == HA_KEYTYPE_DOUBLE)
      {
	double nr;
	float8get(nr, pos);
	if (isnan(nr))
	{
 	  bzero(key, length);
	  key+= length;
	  continue;
	}
      }
#endif
      pos+= length;
      while (length--)
      {
	*key++= *--pos;
      }
      continue;
    }
756 757 758 759 760

    if (seg->flag & HA_VAR_LENGTH_PART)
    {
      uchar *pos=      (uchar*) rec + seg->start;
      uint length=     seg->length;
761 762 763
      uint pack_length= seg->bit_start;
      uint tmp_length= (pack_length == 1 ? (uint) *(uchar*) pos :
                        uint2korr(pos));
764 765 766
      CHARSET_INFO *cs= seg->charset;
      char_length= length/cs->mbmaxlen;

767
      pos+= pack_length;			/* Skip VARCHAR length */
768 769 770 771 772 773 774 775
      set_if_smaller(length,tmp_length);
      FIX_LENGTH(cs, pos, length, char_length);
      store_key_length_inc(key,char_length);
      memcpy((byte*) key,(byte*) pos,(size_t) char_length);
      key+= char_length;
      continue;
    }

unknown's avatar
unknown committed
776 777
    char_length= seg->length;
    if (seg->charset->mbmaxlen > 1)
unknown's avatar
unknown committed
778 779
    {
      char_length= my_charpos(seg->charset, 
unknown's avatar
unknown committed
780 781 782
                              rec + seg->start, rec + seg->start + char_length,
                              char_length / seg->charset->mbmaxlen);
      set_if_smaller(char_length, seg->length); /* QQ: ok to remove? */
unknown's avatar
unknown committed
783
      if (char_length < seg->length)
784
        seg->charset->cset->fill(seg->charset, (char*) key + char_length, 
unknown's avatar
unknown committed
785 786 787
                                 seg->length - char_length, ' ');
    }
    memcpy(key, rec + seg->start, (size_t) char_length);
788 789 790
    key+= seg->length;
  }
  memcpy(key, &recpos, sizeof(byte*));
791
  return (uint) (key - start_key);
792
}
793

unknown's avatar
unknown committed
794 795 796

uint hp_rb_pack_key(HP_KEYDEF *keydef, uchar *key, const uchar *old,
                    uint k_len)
797
{
unknown's avatar
unknown committed
798
  HA_KEYSEG *seg, *endseg;
799 800
  uchar *start_key= key;
  
unknown's avatar
unknown committed
801 802
  for (seg= keydef->seg, endseg= seg + keydef->keysegs;
       seg < endseg && (int) k_len > 0; old+= seg->length, seg++)
803
  {
unknown's avatar
unknown committed
804
    uint char_length;
805
    if (seg->null_bit)
806
    {
unknown's avatar
unknown committed
807
      k_len--;
808
      if (!(*key++= (char) 1 - *old++))
unknown's avatar
unknown committed
809 810
      {
        k_len-= seg->length;
811
        continue;
unknown's avatar
unknown committed
812
      }
813
    }
814 815 816 817 818 819 820 821 822 823 824 825
    if (seg->flag & HA_SWAP_KEY)
    {
      uint length= seg->length;
      byte *pos= (byte*) old + length;
      
      k_len-= length;
      while (length--)
      {
	*key++= *--pos;
      }
      continue;
    }
826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842
    if (seg->flag & (HA_VAR_LENGTH_PART | HA_BLOB_PART))
    {
      /* Length of key-part used with heap_rkey() always 2 */
      uint tmp_length=uint2korr(old);
      uint length= seg->length;
      CHARSET_INFO *cs= seg->charset;
      char_length= length/cs->mbmaxlen;

      k_len-= 2+length;
      old+= 2;
      set_if_smaller(length,tmp_length);	/* Safety */
      FIX_LENGTH(cs, old, length, char_length);
      store_key_length_inc(key,char_length);
      memcpy((byte*) key, old,(size_t) char_length);
      key+= char_length;
      continue;
    }
unknown's avatar
unknown committed
843 844
    char_length= seg->length;
    if (seg->charset->mbmaxlen > 1)
unknown's avatar
unknown committed
845
    {
unknown's avatar
unknown committed
846 847 848
      char_length= my_charpos(seg->charset, old, old+char_length,
                              char_length / seg->charset->mbmaxlen);
      set_if_smaller(char_length, seg->length); /* QQ: ok to remove? */
unknown's avatar
unknown committed
849
      if (char_length < seg->length)
850
        seg->charset->cset->fill(seg->charset, (char*) key + char_length, 
unknown's avatar
unknown committed
851 852 853
                                 seg->length - char_length, ' ');
    }
    memcpy(key, old, (size_t) char_length);
854
    key+= seg->length;
unknown's avatar
unknown committed
855
    k_len-= seg->length;
856
  }
857
  return (uint) (key - start_key);
858
}
859

unknown's avatar
unknown committed
860

unknown's avatar
unknown committed
861 862 863 864 865 866
uint hp_rb_key_length(HP_KEYDEF *keydef, 
		      const byte *key __attribute__((unused)))
{
  return keydef->length;
}

unknown's avatar
unknown committed
867

unknown's avatar
unknown committed
868
uint hp_rb_null_key_length(HP_KEYDEF *keydef, const byte *key)
869 870 871 872
{
  const byte *start_key= key;
  HA_KEYSEG *seg, *endseg;
  
unknown's avatar
unknown committed
873
  for (seg= keydef->seg, endseg= seg + keydef->keysegs; seg < endseg; seg++)
874
  {
unknown's avatar
unknown committed
875 876 877
    if (seg->null_bit && !*key++)
      continue;
    key+= seg->length;
878
  }
879
  return (uint) (key - start_key);
880
}
881
                  
882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898

uint hp_rb_var_key_length(HP_KEYDEF *keydef, const byte *key)
{
  const byte *start_key= key;
  HA_KEYSEG *seg, *endseg;
  
  for (seg= keydef->seg, endseg= seg + keydef->keysegs; seg < endseg; seg++)
  {
    uint length= seg->length;
    if (seg->null_bit && !*key++)
      continue;
    if (seg->flag & (HA_VAR_LENGTH_PART | HA_BLOB_PART))
    {
      get_key_length(length, key);
    }
    key+= length;
  }
899
  return (uint) (key - start_key);
900 901 902
}


903 904 905 906 907 908 909 910 911
/*
  Test if any of the key parts are NULL.
  Return:
    1 if any of the key parts was NULL
    0 otherwise
*/

my_bool hp_if_null_in_key(HP_KEYDEF *keydef, const byte *record)
{
unknown's avatar
unknown committed
912
  HA_KEYSEG *seg,*endseg;
913 914 915 916 917 918 919
  for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
  {
    if (seg->null_bit && (record[seg->null_pos] & seg->null_bit))
      return 1;
  }
  return 0;
}
unknown's avatar
unknown committed
920

921 922 923 924 925 926 927 928 929 930 931 932 933 934 935

/*
  Update auto_increment info

  SYNOPSIS
    update_auto_increment()
    info			MyISAM handler
    record			Row to update

  IMPLEMENTATION
    Only replace the auto_increment value if it is higher than the previous
    one. For signed columns we don't update the auto increment value if it's
    less than zero.
*/

unknown's avatar
unknown committed
936 937
void heap_update_auto_increment(HP_INFO *info, const byte *record)
{
938 939 940
  ulonglong value= 0;			/* Store unsigned values here */
  longlong s_value= 0;			/* Store signed values here */

unknown's avatar
unknown committed
941 942 943 944 945
  HA_KEYSEG *keyseg= info->s->keydef[info->s->auto_key - 1].seg;
  const uchar *key=  (uchar*) record + keyseg->start;

  switch (info->s->auto_key_type) {
  case HA_KEYTYPE_INT8:
946 947
    s_value= (longlong) *(char*)key;
    break;
unknown's avatar
unknown committed
948
  case HA_KEYTYPE_BINARY:
949
    value=(ulonglong)  *(uchar*) key;
unknown's avatar
unknown committed
950 951
    break;
  case HA_KEYTYPE_SHORT_INT:
952 953
    s_value= (longlong) sint2korr(key);
    break;
unknown's avatar
unknown committed
954
  case HA_KEYTYPE_USHORT_INT:
955
    value=(ulonglong) uint2korr(key);
unknown's avatar
unknown committed
956 957
    break;
  case HA_KEYTYPE_LONG_INT:
958 959
    s_value= (longlong) sint4korr(key);
    break;
unknown's avatar
unknown committed
960
  case HA_KEYTYPE_ULONG_INT:
961
    value=(ulonglong) uint4korr(key);
unknown's avatar
unknown committed
962 963
    break;
  case HA_KEYTYPE_INT24:
964 965
    s_value= (longlong) sint3korr(key);
    break;
unknown's avatar
unknown committed
966
  case HA_KEYTYPE_UINT24:
967
    value=(ulonglong) uint3korr(key);
unknown's avatar
unknown committed
968
    break;
969
  case HA_KEYTYPE_FLOAT:                        /* This shouldn't be used */
unknown's avatar
unknown committed
970 971
  {
    float f_1;
972 973 974
    float4get(f_1,key);
    /* Ignore negative values */
    value = (f_1 < (float) 0.0) ? 0 : (ulonglong) f_1;
unknown's avatar
unknown committed
975 976
    break;
  }
977
  case HA_KEYTYPE_DOUBLE:                       /* This shouldn't be used */
unknown's avatar
unknown committed
978 979
  {
    double f_1;
980 981 982
    float8get(f_1,key);
    /* Ignore negative values */
    value = (f_1 < 0.0) ? 0 : (ulonglong) f_1;
unknown's avatar
unknown committed
983 984 985
    break;
  }
  case HA_KEYTYPE_LONGLONG:
986 987
    s_value= sint8korr(key);
    break;
unknown's avatar
unknown committed
988 989 990 991
  case HA_KEYTYPE_ULONGLONG:
    value= uint8korr(key);
    break;
  default:
992 993
    DBUG_ASSERT(0);
    value=0;                                    /* Error */
unknown's avatar
unknown committed
994 995
    break;
  }
996 997 998 999 1000 1001 1002 1003

  /*
    The following code works becasue if s_value < 0 then value is 0
    and if s_value == 0 then value will contain either s_value or the
    correct value.
  */
  set_if_bigger(info->s->auto_increment,
                (s_value > 0) ? (ulonglong) s_value : value);
unknown's avatar
unknown committed
1004
}