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