1115013Smarcel/* 2160157Smarcel * CDDL HEADER START 3121642Smarcel * 4121642Smarcel * The contents of this file are subject to the terms of the 5121642Smarcel * Common Development and Distribution License, Version 1.0 only 6121642Smarcel * (the "License"). You may not use this file except in compliance 7121642Smarcel * with the License. 8121642Smarcel * 9121642Smarcel * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 10121642Smarcel * or http://www.opensolaris.org/os/licensing. 11115013Smarcel * See the License for the specific language governing permissions 12121642Smarcel * and limitations under the License. 13121642Smarcel * 14121642Smarcel * When distributing Covered Code, include this CDDL HEADER in each 15121642Smarcel * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 16121642Smarcel * If applicable, add the following below this CDDL HEADER, with the 17121642Smarcel * fields enclosed by brackets "[]" replaced with your own identifying 18121642Smarcel * information: Portions Copyright [yyyy] [name of copyright owner] 19121642Smarcel * 20121642Smarcel * CDDL HEADER END 21121642Smarcel */ 22121642Smarcel/* 23121642Smarcel * Copyright 2004 Sun Microsystems, Inc. All rights reserved. 24121642Smarcel * Use is subject to license terms. 25115013Smarcel */ 26115013Smarcel 27115013Smarcel#pragma ident "%Z%%M% %I% %E% SMI" 28115013Smarcel 29115013Smarcel/* 30115013Smarcel * Routines for manipulating hash tables 31115013Smarcel */ 32115013Smarcel 33115013Smarcel#include <stdio.h> 34120925Smarcel#include <stdlib.h> 35115013Smarcel#include <strings.h> 36160163Smarcel#include <sys/types.h> 37160163Smarcel#include <sys/sysmacros.h> 38160163Smarcel 39160163Smarcel#include "hash.h" 40115013Smarcel#include "memory.h" 41115013Smarcel#include "list.h" 42160163Smarcel 43160163Smarcelstruct hash { 44160163Smarcel int h_nbuckets; 45160163Smarcel list_t **h_buckets; 46115013Smarcel 47115013Smarcel int (*h_hashfn)(int, void *); 48115013Smarcel int (*h_cmp)(void *, void *); 49115013Smarcel}; 50115013Smarcel 51115013Smarcelstruct hash_data { 52115013Smarcel hash_t *hd_hash; 53115013Smarcel int (*hd_fun)(void *, void *); 54115013Smarcel void *hd_key; 55115013Smarcel void *hd_private; 56115013Smarcel 57115013Smarcel void *hd_ret; 58115013Smarcel}; 59115013Smarcel 60115013Smarcelstatic int 61160157Smarcelhash_def_hash(int nbuckets, void *arg) 62115013Smarcel{ 63160157Smarcel uintptr_t data = (uintptr_t) arg; 64160157Smarcel return (data % nbuckets); 65160157Smarcel} 66160157Smarcel 67115013Smarcelstatic int 68115013Smarcelhash_def_cmp(void *d1, void *d2) 69160157Smarcel{ 70115013Smarcel return (d1 != d2); 71115013Smarcel} 72115013Smarcel 73160157Smarcel 74115013Smarcelint 75115013Smarcelhash_name(int nbuckets, const char *name) 76115013Smarcel{ 77160157Smarcel const char *c; 78115013Smarcel ulong_t g; 79115013Smarcel int h = 0; 80115013Smarcel 81160157Smarcel for (c = name; *c; c++) { 82115013Smarcel h = (h << 4) + *c; 83115013Smarcel if ((g = (h & 0xf0000000)) != 0) { 84115013Smarcel h ^= (g >> 24); 85160157Smarcel h ^= g; 86115013Smarcel } 87115013Smarcel } 88115013Smarcel 89115013Smarcel return (h % nbuckets); 90160157Smarcel} 91115013Smarcel 92115013Smarcelhash_t * 93115013Smarcelhash_new(int nbuckets, int (*hashfn)(int, void *), int (*cmp)(void *, void *)) 94160157Smarcel{ 95115013Smarcel hash_t *hash; 96115013Smarcel 97115013Smarcel hash = xmalloc(sizeof (hash_t)); 98160157Smarcel hash->h_buckets = xcalloc(sizeof (list_t *) * nbuckets); 99115013Smarcel hash->h_nbuckets = nbuckets; 100115013Smarcel hash->h_hashfn = hashfn ? hashfn : hash_def_hash; 101115013Smarcel hash->h_cmp = cmp ? cmp : hash_def_cmp; 102160157Smarcel 103115013Smarcel return (hash); 104115013Smarcel} 105115013Smarcel 106160157Smarcelvoid 107115013Smarcelhash_add(hash_t *hash, void *key) 108115013Smarcel{ 109115013Smarcel int bucket = hash->h_hashfn(hash->h_nbuckets, key); 110115013Smarcel 111160157Smarcel list_add(&hash->h_buckets[bucket], key); 112115013Smarcel} 113115013Smarcel 114115013Smarcelstatic int 115160157Smarcelhash_add_cb(void *node, void *private) 116115013Smarcel{ 117115013Smarcel hash_add((hash_t *)private, node); 118115013Smarcel return (0); 119115013Smarcel} 120160157Smarcel 121115013Smarcelvoid 122115013Smarcelhash_merge(hash_t *to, hash_t *from) 123115013Smarcel{ 124115013Smarcel (void) hash_iter(from, hash_add_cb, to); 125160157Smarcel} 126115013Smarcel 127115013Smarcelstatic int 128115013Smarcelhash_remove_cb(void *key1, void *key2, void *arg) 129115013Smarcel{ 130160157Smarcel hash_t *hash = arg; 131115013Smarcel return (hash->h_cmp(key1, key2)); 132115013Smarcel} 133115013Smarcel 134115013Smarcelvoid 135160157Smarcelhash_remove(hash_t *hash, void *key) 136115013Smarcel{ 137115013Smarcel int bucket = hash->h_hashfn(hash->h_nbuckets, key); 138115013Smarcel 139115013Smarcel (void) list_remove(&hash->h_buckets[bucket], key, 140160157Smarcel hash_remove_cb, hash); 141115013Smarcel} 142115013Smarcel 143115013Smarcelint 144115013Smarcelhash_match(hash_t *hash, void *key, int (*fun)(void *, void *), 145160157Smarcel void *private) 146115013Smarcel{ 147115013Smarcel int bucket = hash->h_hashfn(hash->h_nbuckets, key); 148115013Smarcel 149115013Smarcel return (list_iter(hash->h_buckets[bucket], fun, private) < 0); 150160157Smarcel} 151115013Smarcel 152115013Smarcelstatic int 153115013Smarcelhash_find_list_cb(void *node, void *arg) 154115013Smarcel{ 155160157Smarcel struct hash_data *hd = arg; 156115013Smarcel int cbrc; 157115013Smarcel int rc = 0; 158115013Smarcel 159115013Smarcel if (hd->hd_hash->h_cmp(hd->hd_key, node) == 0) { 160160157Smarcel if ((cbrc = hd->hd_fun(node, hd->hd_private)) < 0) 161115013Smarcel return (cbrc); 162115013Smarcel rc += cbrc; 163115013Smarcel } 164115013Smarcel 165160157Smarcel return (rc); 166115013Smarcel} 167115013Smarcel 168115013Smarcelint 169160157Smarcelhash_find_iter(hash_t *hash, void *key, int (*fun)(void *, void *), 170115013Smarcel void *private) 171115013Smarcel{ 172115013Smarcel int bucket = hash->h_hashfn(hash->h_nbuckets, key); 173115013Smarcel struct hash_data hd; 174160157Smarcel 175115013Smarcel hd.hd_hash = hash; 176115013Smarcel hd.hd_fun = fun; 177115013Smarcel hd.hd_key = key; 178160157Smarcel hd.hd_private = private; 179115013Smarcel 180115013Smarcel return (list_iter(hash->h_buckets[bucket], hash_find_list_cb, 181115013Smarcel &hd)); 182115013Smarcel} 183160157Smarcel 184115013Smarcel/* stop on first match */ 185115013Smarcelstatic int 186115013Smarcelhash_find_first_cb(void *node, void *arg) 187115013Smarcel{ 188160157Smarcel struct hash_data *hd = arg; 189115013Smarcel if (hd->hd_hash->h_cmp(hd->hd_key, node) == 0) { 190115013Smarcel hd->hd_ret = node; 191115013Smarcel return (-1); 192160157Smarcel } 193160157Smarcel 194160157Smarcel return (0); 195160157Smarcel} 196115013Smarcel 197115013Smarcelint 198160157Smarcelhash_find(hash_t *hash, void *key, void **value) 199160157Smarcel{ 200160157Smarcel int ret; 201115013Smarcel struct hash_data hd; 202115013Smarcel 203115013Smarcel hd.hd_hash = hash; 204115013Smarcel hd.hd_fun = hash_find_first_cb; 205115013Smarcel hd.hd_key = key; 206115013Smarcel 207115013Smarcel ret = hash_match(hash, key, hash_find_first_cb, &hd); 208115013Smarcel if (ret && value) 209160157Smarcel *value = hd.hd_ret; 210115013Smarcel 211115013Smarcel return (ret); 212115013Smarcel} 213115013Smarcel 214115013Smarcelint 215115013Smarcelhash_iter(hash_t *hash, int (*fun)(void *, void *), void *private) 216115013Smarcel{ 217160157Smarcel int cumrc = 0; 218115013Smarcel int cbrc; 219115013Smarcel int i; 220115013Smarcel 221115013Smarcel for (i = 0; i < hash->h_nbuckets; i++) { 222115013Smarcel if (hash->h_buckets[i] != NULL) { 223115013Smarcel if ((cbrc = list_iter(hash->h_buckets[i], fun, 224115013Smarcel private)) < 0) 225115013Smarcel return (cbrc); 226160157Smarcel cumrc += cbrc; 227115013Smarcel } 228115013Smarcel } 229115013Smarcel 230115013Smarcel return (cumrc); 231115013Smarcel} 232115013Smarcel 233115013Smarcelint 234115013Smarcelhash_count(hash_t *hash) 235160157Smarcel{ 236115013Smarcel int num, i; 237115013Smarcel 238115013Smarcel for (num = 0, i = 0; i < hash->h_nbuckets; i++) 239115013Smarcel num += list_count(hash->h_buckets[i]); 240115013Smarcel 241115013Smarcel return (num); 242115013Smarcel} 243115013Smarcel 244160157Smarcelvoid 245115013Smarcelhash_free(hash_t *hash, void (*datafree)(void *, void *), void *private) 246115013Smarcel{ 247115013Smarcel int i; 248115013Smarcel 249115013Smarcel if (hash == NULL) 250115013Smarcel return; 251115013Smarcel 252115013Smarcel for (i = 0; i < hash->h_nbuckets; i++) 253115013Smarcel list_free(hash->h_buckets[i], datafree, private); 254115013Smarcel free(hash->h_buckets); 255160157Smarcel free(hash); 256115013Smarcel} 257115013Smarcel 258115013Smarcelvoid 259160157Smarcelhash_stats(hash_t *hash, int verbose) 260115013Smarcel{ 261115013Smarcel int min = list_count(hash->h_buckets[0]); 262115013Smarcel int minidx = 0; 263115013Smarcel int max = min; 264160157Smarcel int maxidx = 0; 265115013Smarcel int tot = min; 266115013Smarcel int count; 267115013Smarcel int i; 268115013Smarcel 269115013Smarcel if (min && verbose) 270115013Smarcel printf("%3d: %d\n", 0, min); 271160157Smarcel for (i = 1; i < hash->h_nbuckets; i++) { 272115013Smarcel count = list_count(hash->h_buckets[i]); 273115013Smarcel if (min > count) { 274115013Smarcel min = count; 275115013Smarcel minidx = i; 276115013Smarcel } 277115013Smarcel if (max < count) { 278115013Smarcel max = count; 279160157Smarcel maxidx = i; 280115013Smarcel } 281115013Smarcel if (count && verbose) 282115013Smarcel printf("%3d: %d\n", i, count); 283115013Smarcel tot += count; 284115013Smarcel } 285115013Smarcel 286160157Smarcel printf("Hash statistics:\n"); 287115013Smarcel printf(" Buckets: %d\n", hash->h_nbuckets); 288115013Smarcel printf(" Items : %d\n", tot); 289115013Smarcel printf(" Min/Max: %d in #%d, %d in #%d\n", min, minidx, max, maxidx); 290115013Smarcel printf(" Average: %5.2f\n", (float)tot / (float)hash->h_nbuckets); 291115013Smarcel} 292115013Smarcel