← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to plugin/heap/hp_hash.cc

  • Committer: Brian Aker
  • Date: 2009-10-12 06:15:02 UTC
  • mfrom: (1165.1.178 static-functions)
  • Revision ID: brian@gaz-20091012061502-cds4m0cya7ow8sj7
Merge Stewart

Show diffs side-by-side

added added

removed removed

Lines of Context:
plugin/heap/hp_hash.cc
21
21
#include <drizzled/util/test.h>
22
22
 
23
23
#include <string.h>
 
24
static uint32_t hp_hashnr(register HP_KEYDEF *keydef, register const unsigned char *key);
 
25
static int hp_key_cmp(HP_KEYDEF *keydef, const unsigned char *rec, const unsigned char *key);
24
26
 
25
27
/*
26
28
  Find out how many rows there is in the given range
227
229
  return;
228
230
}
229
231
 
230
 
#ifndef NEW_HASH_FUNCTION
231
 
 
232
232
        /* Calc hashvalue for a key */
233
233
 
234
 
uint32_t hp_hashnr(register HP_KEYDEF *keydef, register const unsigned char *key)
 
234
static uint32_t hp_hashnr(register HP_KEYDEF *keydef, register const unsigned char *key)
235
235
{
236
236
  /*register*/
237
237
  uint32_t nr=1, nr2=4;
351
351
  return(nr);
352
352
}
353
353
 
354
 
#else
355
 
 
356
 
/*
357
 
 * Fowler/Noll/Vo hash
358
 
 *
359
 
 * The basis of the hash algorithm was taken from an idea sent by email to the
360
 
 * IEEE Posix P1003.2 mailing list from Phong Vo (kpv@research.att.com) and
361
 
 * Glenn Fowler (gsf@research.att.com).  Landon Curt Noll (chongo@toad.com)
362
 
 * later improved on their algorithm.
363
 
 *
364
 
 * The magic is in the interesting relationship between the special prime
365
 
 * 16777619 (2^24 + 403) and 2^32 and 2^8.
366
 
 *
367
 
 * This hash produces the fewest collisions of any function that we've seen so
368
 
 * far, and works well on both numbers and strings.
369
 
 */
370
 
 
371
 
uint32_t hp_hashnr(register HP_KEYDEF *keydef, register const unsigned char *key)
372
 
{
373
 
  /*
374
 
    Note, if a key consists of a combination of numeric and
375
 
    a text columns, it most likely won't work well.
376
 
    Making text columns work with NEW_HASH_FUNCTION
377
 
    needs also changes in strings/ctype-xxx.c.
378
 
  */
379
 
  uint32_t nr= 1, nr2= 4;
380
 
  HA_KEYSEG *seg,*endseg;
381
 
 
382
 
  for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
383
 
  {
384
 
    unsigned char *pos=(unsigned char*) key;
385
 
    key+=seg->length;
386
 
    if (seg->null_bit)
387
 
    {
388
 
      key++;
389
 
      if (*pos)
390
 
      {
391
 
        nr^= (nr << 1) | 1;
392
 
        /* Add key pack length (2) to key for VARCHAR segments */
393
 
        if (seg->type == HA_KEYTYPE_VARTEXT1)
394
 
          key+= 2;
395
 
        continue;
396
 
      }
397
 
      pos++;
398
 
    }
399
 
    if (seg->type == HA_KEYTYPE_TEXT)
400
 
    {
401
 
      seg->charset->coll->hash_sort(seg->charset, pos, ((unsigned char*)key)-pos,
402
 
                                    &nr, &nr2);
403
 
    }
404
 
    else if (seg->type == HA_KEYTYPE_VARTEXT1)  /* Any VARCHAR segments */
405
 
    {
406
 
      uint32_t pack_length= 2;                      /* Key packing is constant */
407
 
      uint32_t length= uint2korr(pos);
408
 
      seg->charset->coll->hash_sort(seg->charset, pos+pack_length, length,
409
 
                                    &nr, &nr2);
410
 
      key+= pack_length;
411
 
    }
412
 
    else
413
 
    {
414
 
      for ( ; pos < (unsigned char*) key ; pos++)
415
 
      {
416
 
        nr *=16777619;
417
 
        nr ^=(uint) *pos;
418
 
      }
419
 
    }
420
 
  }
421
 
  return(nr);
422
 
}
423
 
 
424
 
        /* Calc hashvalue for a key in a record */
425
 
 
426
 
uint32_t hp_rec_hashnr(register HP_KEYDEF *keydef, register const unsigned char *rec)
427
 
{
428
 
  uint32_t nr= 1, nr2= 4;
429
 
  HA_KEYSEG *seg,*endseg;
430
 
 
431
 
  for (seg=keydef->seg,endseg=seg+keydef->keysegs ; seg < endseg ; seg++)
432
 
  {
433
 
    unsigned char *pos=(unsigned char*) rec+seg->start;
434
 
    if (seg->null_bit)
435
 
    {
436
 
      if (rec[seg->null_pos] & seg->null_bit)
437
 
      {
438
 
        nr^= (nr << 1) | 1;
439
 
        continue;
440
 
      }
441
 
    }
442
 
    if (seg->type == HA_KEYTYPE_TEXT)
443
 
    {
444
 
      uint32_t char_length= seg->length; /* TODO: fix to use my_charpos() */
445
 
      seg->charset->coll->hash_sort(seg->charset, pos, char_length,
446
 
                                    &nr, &nr2);
447
 
    }
448
 
    else if (seg->type == HA_KEYTYPE_VARTEXT1)  /* Any VARCHAR segments */
449
 
    {
450
 
      uint32_t pack_length= seg->bit_start;
451
 
      uint32_t length= (pack_length == 1 ? (uint) *(unsigned char*) pos : uint2korr(pos));
452
 
      seg->charset->coll->hash_sort(seg->charset, pos+pack_length,
453
 
                                    length, &nr, &nr2);
454
 
    }
455
 
    else
456
 
    {
457
 
      unsigned char *end= pos+seg->length;
458
 
      for ( ; pos < end ; pos++)
459
 
      {
460
 
        nr *=16777619;
461
 
        nr ^=(uint) *pos;
462
 
      }
463
 
    }
464
 
  }
465
 
  return(nr);
466
 
}
467
 
 
468
 
#endif
469
 
 
470
 
 
471
354
/*
472
355
  Compare keys for two records. Returns 0 if they are identical
473
356
 
575
458
 
576
459
        /* Compare a key in a record to a whole key */
577
460
 
578
 
int hp_key_cmp(HP_KEYDEF *keydef, const unsigned char *rec, const unsigned char *key)
 
461
static int hp_key_cmp(HP_KEYDEF *keydef, const unsigned char *rec, const unsigned char *key)
579
462
{
580
463
  HA_KEYSEG *seg,*endseg;
581
464