Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Newer
Older
100644 187 lines (161 sloc) 5.823 kb
825db0f @bradfitz stop using Judy for string mappings and use a hash table instead, which
bradfitz authored
1 /* -*- Mode: C; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2 /*
3 * Hash table
4 *
5 * The hash function used here is by Bob Jenkins, 1996:
6 * <http://burtleburtle.net/bob/hash/doobs.html>
93c6642 @bradfitz whitespace changes only
bradfitz authored
7 * "By Bob Jenkins, 1996. bob_jenkins@burtleburtle.net.
825db0f @bradfitz stop using Judy for string mappings and use a hash table instead, which
bradfitz authored
8 * You may use this code any way you wish, private, educational,
9 * or commercial. It's free."
10 *
11 * The rest of the file is licensed under the BSD license. See LICENSE.
12 *
13 * $Id$
14 */
15
16 #include <sys/types.h>
17 #include <sys/stat.h>
18 #include <sys/time.h>
19 #include <sys/socket.h>
20 #include <sys/signal.h>
21 #include <sys/resource.h>
22 #include <fcntl.h>
23 #include <stdlib.h>
24 #include <stdio.h>
25 #include <string.h>
26 #include <unistd.h>
27 #include <netinet/in.h>
28 #include <errno.h>
29 #include <event.h>
18a72ad @bradfitz version 1.1.6
bradfitz authored
30 #include <assert.h>
825db0f @bradfitz stop using Judy for string mappings and use a hash table instead, which
bradfitz authored
31
32 #include "memcached.h"
33
34 typedef unsigned long int ub4; /* unsigned 4-byte quantities */
35 typedef unsigned char ub1; /* unsigned 1-byte quantities */
36
37 /* hard-code one million buckets, for now (2**20 == 4MB hash) */
38 #define HASHPOWER 20
39
40 #define hashsize(n) ((ub4)1<<(n))
41 #define hashmask(n) (hashsize(n)-1)
42
43 #define mix(a,b,c) \
44 { \
45 a -= b; a -= c; a ^= (c>>13); \
46 b -= c; b -= a; b ^= (a<<8); \
47 c -= a; c -= b; c ^= (b>>13); \
48 a -= b; a -= c; a ^= (c>>12); \
49 b -= c; b -= a; b ^= (a<<16); \
50 c -= a; c -= b; c ^= (b>>5); \
51 a -= b; a -= c; a ^= (c>>3); \
52 b -= c; b -= a; b ^= (a<<10); \
53 c -= a; c -= b; c ^= (b>>15); \
54 }
55
56 /*
57 --------------------------------------------------------------------
58 hash() -- hash a variable-length key into a 32-bit value
59 k : the key (the unaligned variable-length array of bytes)
60 len : the length of the key, counting by bytes
61 initval : can be any 4-byte value
62 Returns a 32-bit value. Every bit of the key affects every bit of
63 the return value. Every 1-bit and 2-bit delta achieves avalanche.
64 About 6*len+35 instructions.
65
66 The best hash table sizes are powers of 2. There is no need to do
67 mod a prime (mod is sooo slow!). If you need less than 32 bits,
68 use a bitmask. For example, if you need only 10 bits, do
69 h = (h & hashmask(10));
70 In which case, the hash table should have hashsize(10) elements.
71
72 If you are hashing n strings (ub1 **)k, do it like this:
73 for (i=0, h=0; i<n; ++i) h = hash( k[i], len[i], h);
74
75 By Bob Jenkins, 1996. bob_jenkins@burtleburtle.net. You may use this
76 code any way you wish, private, educational, or commercial. It's free.
77
78 See http://burtleburtle.net/bob/hash/evahash.html
79 Use for hash table lookup, or anything where one collision in 2^^32 is
80 acceptable. Do NOT use for cryptographic purposes.
81 --------------------------------------------------------------------
82 */
83
84 ub4 hash( k, length, initval)
85 register ub1 *k; /* the key */
86 register ub4 length; /* the length of the key */
87 register ub4 initval; /* the previous hash, or an arbitrary value */
88 {
89 register ub4 a,b,c,len;
90
91 /* Set up the internal state */
92 len = length;
93 a = b = 0x9e3779b9; /* the golden ratio; an arbitrary value */
94 c = initval; /* the previous hash value */
95
96 /*---------------------------------------- handle most of the key */
97 while (len >= 12)
98 {
99 a += (k[0] +((ub4)k[1]<<8) +((ub4)k[2]<<16) +((ub4)k[3]<<24));
100 b += (k[4] +((ub4)k[5]<<8) +((ub4)k[6]<<16) +((ub4)k[7]<<24));
101 c += (k[8] +((ub4)k[9]<<8) +((ub4)k[10]<<16)+((ub4)k[11]<<24));
102 mix(a,b,c);
103 k += 12; len -= 12;
104 }
105
106 /*------------------------------------- handle the last 11 bytes */
107 c += length;
108 switch(len) /* all the case statements fall through */
109 {
110 case 11: c+=((ub4)k[10]<<24);
111 case 10: c+=((ub4)k[9]<<16);
112 case 9 : c+=((ub4)k[8]<<8);
113 /* the first byte of c is reserved for the length */
114 case 8 : b+=((ub4)k[7]<<24);
115 case 7 : b+=((ub4)k[6]<<16);
116 case 6 : b+=((ub4)k[5]<<8);
117 case 5 : b+=k[4];
118 case 4 : a+=((ub4)k[3]<<24);
119 case 3 : a+=((ub4)k[2]<<16);
120 case 2 : a+=((ub4)k[1]<<8);
121 case 1 : a+=k[0];
122 /* case 0: nothing left to add */
123 }
124 mix(a,b,c);
125 /*-------------------------------------------- report the result */
126 return c;
127 }
128
f6d334e @bradfitz 2003-06-10
bradfitz authored
129 static item** hashtable = 0;
825db0f @bradfitz stop using Judy for string mappings and use a hash table instead, which
bradfitz authored
130
131 void assoc_init(void) {
132 unsigned int hash_size = hashsize(HASHPOWER) * sizeof(void*);
133 hashtable = malloc(hash_size);
134 if (! hashtable) {
135 fprintf(stderr, "Failed to init hashtable.\n");
136 exit(1);
137 }
138 memset(hashtable, 0, hash_size);
139 }
140
141 item *assoc_find(char *key) {
142 ub4 hv = hash(key, strlen(key), 0) & hashmask(HASHPOWER);
f6d334e @bradfitz 2003-06-10
bradfitz authored
143 item *it = hashtable[hv];
825db0f @bradfitz stop using Judy for string mappings and use a hash table instead, which
bradfitz authored
144
f6d334e @bradfitz 2003-06-10
bradfitz authored
145 while (it) {
146 if (strcmp(key, ITEM_key(it)) == 0)
825db0f @bradfitz stop using Judy for string mappings and use a hash table instead, which
bradfitz authored
147 return it;
f6d334e @bradfitz 2003-06-10
bradfitz authored
148 it = it->h_next;
825db0f @bradfitz stop using Judy for string mappings and use a hash table instead, which
bradfitz authored
149 }
150 return 0;
151 }
152
7917af4 @bradfitz misc fixes as suggested by avva. lot of comment updates, mostly.
bradfitz authored
153 /* returns the address of the item pointer before the key. if *item == 0,
154 the item wasn't found */
825db0f @bradfitz stop using Judy for string mappings and use a hash table instead, which
bradfitz authored
155
f6d334e @bradfitz 2003-06-10
bradfitz authored
156 static item** _hashitem_before (char *key) {
825db0f @bradfitz stop using Judy for string mappings and use a hash table instead, which
bradfitz authored
157 ub4 hv = hash(key, strlen(key), 0) & hashmask(HASHPOWER);
f6d334e @bradfitz 2003-06-10
bradfitz authored
158 item **pos = &hashtable[hv];
825db0f @bradfitz stop using Judy for string mappings and use a hash table instead, which
bradfitz authored
159
f6d334e @bradfitz 2003-06-10
bradfitz authored
160 while (*pos && strcmp(key, ITEM_key(*pos))) {
161 pos = &(*pos)->h_next;
825db0f @bradfitz stop using Judy for string mappings and use a hash table instead, which
bradfitz authored
162 }
163 return pos;
164 }
165
7917af4 @bradfitz misc fixes as suggested by avva. lot of comment updates, mostly.
bradfitz authored
166 /* Note: this isn't an assoc_update. The key must not already exist to call this */
825db0f @bradfitz stop using Judy for string mappings and use a hash table instead, which
bradfitz authored
167 int assoc_insert(char *key, item *it) {
7917af4 @bradfitz misc fixes as suggested by avva. lot of comment updates, mostly.
bradfitz authored
168 ub4 hv = hash(key, strlen(key), 0) & hashmask(HASHPOWER);
169 it->h_next = hashtable[hv];
170 hashtable[hv] = it;
f6d334e @bradfitz 2003-06-10
bradfitz authored
171 return 1;
825db0f @bradfitz stop using Judy for string mappings and use a hash table instead, which
bradfitz authored
172 }
173
174 void assoc_delete(char *key) {
f6d334e @bradfitz 2003-06-10
bradfitz authored
175 item **before = _hashitem_before(key);
825db0f @bradfitz stop using Judy for string mappings and use a hash table instead, which
bradfitz authored
176 if (*before) {
f6d334e @bradfitz 2003-06-10
bradfitz authored
177 item *nxt = (*before)->h_next;
178 (*before)->h_next = 0; /* probably pointless, but whatever. */
179 *before = nxt;
180 return;
825db0f @bradfitz stop using Judy for string mappings and use a hash table instead, which
bradfitz authored
181 }
7917af4 @bradfitz misc fixes as suggested by avva. lot of comment updates, mostly.
bradfitz authored
182 /* Note: we never actually get here. the callers don't delete things
c08383a @bradfitz more debug asserts
bradfitz authored
183 they can't find. */
184 assert(*before != 0);
825db0f @bradfitz stop using Judy for string mappings and use a hash table instead, which
bradfitz authored
185 }
186
Something went wrong with that request. Please try again.