Lines Matching full:hash
25 #include <shared/hash.h>
39 struct hash {
47 struct hash *hash_new(unsigned int n_buckets,
50 struct hash *hash;
53 hash = calloc(1, sizeof(struct hash) +
55 if (hash == NULL)
57 hash->n_buckets = n_buckets;
58 hash->free_value = free_value;
59 hash->step = n_buckets / 32;
60 if (hash->step == 0)
61 hash->step = 4;
62 else if (hash->step > 64)
63 hash->step = 64;
64 return hash;
67 void hash_free(struct hash *hash)
71 if (hash == NULL)
74 bucket = hash->buckets;
75 bucket_end = bucket + hash->n_buckets;
77 if (hash->free_value) {
82 hash->free_value((void *)entry->value);
86 free(hash);
91 /* Paul Hsieh (http://www.azillionmonkeys.com/qed/hash.html)
95 unsigned int tmp, hash = len, rem = len & 3;
101 hash += get_unaligned((uint16_t *) key);
102 tmp = (get_unaligned((uint16_t *)(key + 2)) << 11) ^ hash;
103 hash = (hash << 16) ^ tmp;
105 hash += hash >> 11;
111 hash += get_unaligned((uint16_t *) key);
112 hash ^= hash << 16;
113 hash ^= key[2] << 18;
114 hash += hash >> 11;
118 hash += get_unaligned((uint16_t *) key);
119 hash ^= hash << 11;
120 hash += hash >> 17;
124 hash += *key;
125 hash ^= hash << 10;
126 hash += hash >> 1;
130 hash ^= hash << 3;
131 hash += hash >> 5;
132 hash ^= hash << 4;
133 hash += hash >> 17;
134 hash ^= hash << 25;
135 hash += hash >> 6;
137 return hash;
141 * add or replace key in hash map.
144 * make sure they are live while pair exists in hash!
146 int hash_add(struct hash *hash, const char *key, const void *value)
150 unsigned int pos = hashval & (hash->n_buckets - 1);
151 struct hash_bucket *bucket = hash->buckets + pos;
155 unsigned new_total = bucket->total + hash->step;
169 if (hash->free_value)
170 hash->free_value((void *)entry->value);
184 hash->count++;
189 int hash_add_unique(struct hash *hash, const char *key, const void *value)
193 unsigned int pos = hashval & (hash->n_buckets - 1);
194 struct hash_bucket *bucket = hash->buckets + pos;
198 unsigned new_total = bucket->total + hash->step;
223 hash->count++;
234 void *hash_find(const struct hash *hash, const char *key)
238 unsigned int pos = hashval & (hash->n_buckets - 1);
239 const struct hash_bucket *bucket = hash->buckets + pos;
252 int hash_del(struct hash *hash, const char *key)
256 unsigned int pos = hashval & (hash->n_buckets - 1);
258 struct hash_bucket *bucket = hash->buckets + pos;
270 if (hash->free_value)
271 hash->free_value((void *)entry->value);
278 hash->count--;
280 steps_used = bucket->used / hash->step;
281 steps_total = bucket->total / hash->step;
284 hash->step * sizeof(struct hash_entry);
288 bucket->total = (steps_used + 1) * hash->step;
295 unsigned int hash_get_count(const struct hash *hash)
297 return hash->count;
300 void hash_iter_init(const struct hash *hash, struct hash_iter *iter)
302 iter->hash = hash;
310 const struct hash_bucket *b = iter->hash->buckets + iter->bucket;
318 for (iter->bucket++; iter->bucket < iter->hash->n_buckets;
320 b = iter->hash->buckets + iter->bucket;
326 if (iter->bucket >= iter->hash->n_buckets)
