diff options
author | Brad Fitzpatrick <brad@danga.com> | 2006-09-04 04:08:03 +0000 |
---|---|---|
committer | Brad Fitzpatrick <brad@danga.com> | 2006-09-04 04:08:03 +0000 |
commit | 86969ea43d6718411cc3653faeb0c49090a1c4cf (patch) | |
tree | ddb9da202b62f152141ff060900b69052572109e /assoc.c | |
parent | 85688dac534a831db220485a5691e380f54ce2f5 (diff) | |
download | memcached-86969ea43d6718411cc3653faeb0c49090a1c4cf.tar.gz |
restore blank lines I over-zealously destroyed earlier.
git-svn-id: http://code.sixapart.com/svn/memcached/trunk/server@335 b0b603af-a30f-0410-a34e-baf09ae79d0b
Diffstat (limited to 'assoc.c')
-rw-r--r-- | assoc.c | 23 |
1 files changed, 23 insertions, 0 deletions
@@ -27,13 +27,18 @@ #include <errno.h> #include <event.h> #include <assert.h> + #include "memcached.h" + typedef unsigned long int ub4; /* unsigned 4-byte quantities */ typedef unsigned char ub1; /* unsigned 1-byte quantities */ + /* hard-code one million buckets, for now (2**20 == 4MB hash) */ #define HASHPOWER 20 + #define hashsize(n) ((ub4)1<<(n)) #define hashmask(n) (hashsize(n)-1) + #define mix(a,b,c) \ { \ a -= b; a -= c; a ^= (c>>13); \ @@ -46,6 +51,7 @@ typedef unsigned char ub1; /* unsigned 1-byte quantities */ b -= c; b -= a; b ^= (a<<10); \ c -= a; c -= b; c ^= (b>>15); \ } + /* -------------------------------------------------------------------- hash() -- hash a variable-length key into a 32-bit value @@ -55,30 +61,37 @@ hash() -- hash a variable-length key into a 32-bit value Returns a 32-bit value. Every bit of the key affects every bit of the return value. Every 1-bit and 2-bit delta achieves avalanche. About 6*len+35 instructions. + The best hash table sizes are powers of 2. There is no need to do mod a prime (mod is sooo slow!). If you need less than 32 bits, use a bitmask. For example, if you need only 10 bits, do h = (h & hashmask(10)); In which case, the hash table should have hashsize(10) elements. + If you are hashing n strings (ub1 **)k, do it like this: for (i=0, h=0; i<n; ++i) h = hash( k[i], len[i], h); + By Bob Jenkins, 1996. bob_jenkins@burtleburtle.net. You may use this code any way you wish, private, educational, or commercial. It's free. + See http://burtleburtle.net/bob/hash/evahash.html Use for hash table lookup, or anything where one collision in 2^^32 is acceptable. Do NOT use for cryptographic purposes. -------------------------------------------------------------------- */ + ub4 hash( k, length, initval) register ub1 *k; /* the key */ register ub4 length; /* the length of the key */ register ub4 initval; /* the previous hash, or an arbitrary value */ { register ub4 a,b,c,len; + /* Set up the internal state */ len = length; a = b = 0x9e3779b9; /* the golden ratio; an arbitrary value */ c = initval; /* the previous hash value */ + /*---------------------------------------- handle most of the key */ while (len >= 12) { @@ -88,6 +101,7 @@ ub4 hash( k, length, initval) mix(a,b,c); k += 12; len -= 12; } + /*------------------------------------- handle the last 11 bytes */ c += length; switch(len) /* all the case statements fall through */ @@ -110,7 +124,9 @@ ub4 hash( k, length, initval) /*-------------------------------------------- report the result */ return c; } + static item** hashtable = 0; + void assoc_init(void) { unsigned int hash_size = hashsize(HASHPOWER) * sizeof(void*); hashtable = malloc(hash_size); @@ -120,9 +136,11 @@ void assoc_init(void) { } memset(hashtable, 0, hash_size); } + item *assoc_find(char *key) { ub4 hv = hash(key, strlen(key), 0) & hashmask(HASHPOWER); item *it = hashtable[hv]; + while (it) { if (strcmp(key, ITEM_key(it)) == 0) return it; @@ -130,16 +148,20 @@ item *assoc_find(char *key) { } return 0; } + /* returns the address of the item pointer before the key. if *item == 0, the item wasn't found */ + static item** _hashitem_before (char *key) { ub4 hv = hash(key, strlen(key), 0) & hashmask(HASHPOWER); item **pos = &hashtable[hv]; + while (*pos && strcmp(key, ITEM_key(*pos))) { pos = &(*pos)->h_next; } return pos; } + /* Note: this isn't an assoc_update. The key must not already exist to call this */ int assoc_insert(char *key, item *it) { ub4 hv = hash(key, strlen(key), 0) & hashmask(HASHPOWER); @@ -147,6 +169,7 @@ int assoc_insert(char *key, item *it) { hashtable[hv] = it; return 1; } + void assoc_delete(char *key) { item **before = _hashitem_before(key); if (*before) { |