← Back to branch summary

~mordred/libmemcached/pandora-build

« back to all changes in this revision

Viewing changes to libmemcached/hsieh_hash.c

  • Committer: Brian Aker
  • Date: 2010-01-21 02:51:52 UTC
  • Revision ID: brian@gaz-20100121025152-0twtkpef3yev2u8u
Cleanup dead files in libmemcached.

Show diffs side-by-side

added added

removed removed

Lines of Context:
libmemcached/hsieh_hash.c
1
 
/* By Paul Hsieh (C) 2004, 2005.  Covered under the Paul Hsieh
2
 
 * derivative license. 
3
 
 * See: http://www.azillionmonkeys.com/qed/weblicense.html for license
4
 
 * details.
5
 
 * http://www.azillionmonkeys.com/qed/hash.html
6
 
*/
7
 
 
8
 
#include "common.h"
9
 
 
10
 
#undef get16bits
11
 
#if (defined(__GNUC__) && defined(__i386__))
12
 
#define get16bits(d) (*((const uint16_t *) (d)))
13
 
#endif
14
 
 
15
 
#if !defined (get16bits)
16
 
#define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8)\
17
 
                      +(uint32_t)(((const uint8_t *)(d))[0]) )
18
 
#endif
19
 
 
20
 
uint32_t hsieh_hash(const char *key, size_t key_length)
21
 
{
22
 
  uint32_t hash = 0, tmp;
23
 
  int rem;
24
 
 
25
 
  if (key_length <= 0 || key == NULL)
26
 
    return 0;
27
 
 
28
 
  rem = key_length & 3;
29
 
  key_length >>= 2;
30
 
 
31
 
  /* Main loop */
32
 
  for (;key_length > 0; key_length--)
33
 
  {
34
 
    hash  += get16bits (key);
35
 
    tmp    = (get16bits (key+2) << 11) ^ hash;
36
 
    hash   = (hash << 16) ^ tmp;
37
 
    key  += 2*sizeof (uint16_t);
38
 
    hash  += hash >> 11;
39
 
  }
40
 
 
41
 
  /* Handle end cases */
42
 
  switch (rem)
43
 
  {
44
 
  case 3: hash += get16bits (key);
45
 
          hash ^= hash << 16;
46
 
          hash ^= key[sizeof (uint16_t)] << 18;
47
 
          hash += hash >> 11;
48
 
          break;
49
 
  case 2: hash += get16bits (key);
50
 
          hash ^= hash << 11;
51
 
          hash += hash >> 17;
52
 
          break;
53
 
  case 1: hash += *key;
54
 
          hash ^= hash << 10;
55
 
          hash += hash >> 1;
56
 
  }
57
 
 
58
 
  /* Force "avalanching" of final 127 bits */
59
 
  hash ^= hash << 3;
60
 
  hash += hash >> 5;
61
 
  hash ^= hash << 4;
62
 
  hash += hash >> 17;
63
 
  hash ^= hash << 25;
64
 
  hash += hash >> 6;
65
 
 
66
 
  return hash;
67
 
}
68