30  * Routines for manipulating hash tables
39 #include "hash.h"
43 struct hash {  struct
95 	hash_t *hash;  in hash_new()  local
97 	hash = xmalloc(sizeof (hash_t));  in hash_new()
98 	hash->h_buckets = xcalloc(sizeof (list_t *) * nbuckets);  in hash_new()
99 	hash->h_nbuckets = nbuckets;  in hash_new()
100 	hash->h_hashfn = hashfn ? hashfn : hash_def_hash;  in hash_new()
101 	hash->h_cmp = cmp ? cmp : hash_def_cmp;  in hash_new()
103 	return (hash);  in hash_new()
107 hash_add(hash_t *hash, void *key)  in hash_add()  argument
109 	int bucket = hash->h_hashfn(hash->h_nbuckets, key);  in hash_add()
111 	list_add(&hash->h_buckets[bucket], key);  in hash_add()
130 	hash_t *hash = arg;  in hash_remove_cb()  local
131 	return (hash->h_cmp(key1, key2));  in hash_remove_cb()
135 hash_remove(hash_t *hash, void *key)  in hash_remove()  argument
137 	int bucket = hash->h_hashfn(hash->h_nbuckets, key);  in hash_remove()
139 	(void) list_remove(&hash->h_buckets[bucket], key,  in hash_remove()
140 	    hash_remove_cb, hash);  in hash_remove()
144 hash_match(hash_t *hash, void *key, int (*fun)(void *, void *),  in hash_match()  argument
147 	int bucket = hash->h_hashfn(hash->h_nbuckets, key);  in hash_match()
149 	return (list_iter(hash->h_buckets[bucket], fun, private) < 0);  in hash_match()
169 hash_find_iter(hash_t *hash, void *key, int (*fun)(void *, void *),  in hash_find_iter()  argument
172 	int bucket = hash->h_hashfn(hash->h_nbuckets, key);  in hash_find_iter()
175 	hd.hd_hash = hash;  in hash_find_iter()
180 	return (list_iter(hash->h_buckets[bucket], hash_find_list_cb,  in hash_find_iter()
198 hash_find(hash_t *hash, void *key, void **value)  in hash_find()  argument
203 	hd.hd_hash = hash;  in hash_find()
207 	ret = hash_match(hash, key, hash_find_first_cb, &hd);  in hash_find()
215 hash_iter(hash_t *hash, int (*fun)(void *, void *), void *private)  in hash_iter()  argument
221 	for (i = 0; i < hash->h_nbuckets; i++) {  in hash_iter()
222 		if (hash->h_buckets[i] != NULL) {  in hash_iter()
223 			if ((cbrc = list_iter(hash->h_buckets[i], fun,  in hash_iter()
234 hash_count(hash_t *hash)  in hash_count()  argument
238 	for (num = 0, i = 0; i < hash->h_nbuckets; i++)  in hash_count()
239 		num += list_count(hash->h_buckets[i]);  in hash_count()
245 hash_free(hash_t *hash, void (*datafree)(void *, void *), void *private)  in hash_free()  argument
249 	if (hash == NULL)  in hash_free()
252 	for (i = 0; i < hash->h_nbuckets; i++)  in hash_free()
253 		list_free(hash->h_buckets[i], datafree, private);  in hash_free()
254 	free(hash->h_buckets);  in hash_free()
255 	free(hash);  in hash_free()
259 hash_stats(hash_t *hash, int verbose)  in hash_stats()  argument
261 	int min = list_count(hash->h_buckets[0]);  in hash_stats()
271 	for (i = 1; i < hash->h_nbuckets; i++) {  in hash_stats()
272 		count = list_count(hash->h_buckets[i]);  in hash_stats()
286 	printf("Hash statistics:\n");  in hash_stats()
287 	printf(" Buckets: %d\n", hash->h_nbuckets);  in hash_stats()
290 	printf(" Average: %5.2f\n", (float)tot / (float)hash->h_nbuckets);  in hash_stats()