1178481Sjb/* 2178481Sjb * CDDL HEADER START 3178481Sjb * 4178481Sjb * The contents of this file are subject to the terms of the 5178481Sjb * Common Development and Distribution License, Version 1.0 only 6178481Sjb * (the "License"). You may not use this file except in compliance 7178481Sjb * with the License. 8178481Sjb * 9178481Sjb * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 10178481Sjb * or http://www.opensolaris.org/os/licensing. 11178481Sjb * See the License for the specific language governing permissions 12178481Sjb * and limitations under the License. 13178481Sjb * 14178481Sjb * When distributing Covered Code, include this CDDL HEADER in each 15178481Sjb * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 16178481Sjb * If applicable, add the following below this CDDL HEADER, with the 17178481Sjb * fields enclosed by brackets "[]" replaced with your own identifying 18178481Sjb * information: Portions Copyright [yyyy] [name of copyright owner] 19178481Sjb * 20178481Sjb * CDDL HEADER END 21178481Sjb */ 22178481Sjb/* 23178481Sjb * Copyright 2004 Sun Microsystems, Inc. All rights reserved. 24178481Sjb * Use is subject to license terms. 25178481Sjb */ 26178481Sjb 27178481Sjb#pragma ident "%Z%%M% %I% %E% SMI" 28178481Sjb 29178481Sjb/* 30178481Sjb * Routines for manipulating hash tables 31178481Sjb */ 32178481Sjb 33178481Sjb#include <stdio.h> 34178481Sjb#include <stdlib.h> 35178481Sjb#include <strings.h> 36178481Sjb#include <sys/types.h> 37178481Sjb#include <sys/sysmacros.h> 38178481Sjb 39178481Sjb#include "hash.h" 40178481Sjb#include "memory.h" 41178481Sjb#include "list.h" 42178481Sjb 43178481Sjbstruct hash { 44178481Sjb int h_nbuckets; 45178481Sjb list_t **h_buckets; 46178481Sjb 47178481Sjb int (*h_hashfn)(int, void *); 48178481Sjb int (*h_cmp)(void *, void *); 49178481Sjb}; 50178481Sjb 51178481Sjbstruct hash_data { 52178481Sjb hash_t *hd_hash; 53178546Sjb int (*hd_fun)(void *, void *); 54178481Sjb void *hd_key; 55178481Sjb void *hd_private; 56178481Sjb 57178481Sjb void *hd_ret; 58178481Sjb}; 59178481Sjb 60178481Sjbstatic int 61178546Sjbhash_def_hash(int nbuckets, void *arg) 62178481Sjb{ 63178546Sjb uintptr_t data = (uintptr_t) arg; 64178481Sjb return (data % nbuckets); 65178481Sjb} 66178481Sjb 67178481Sjbstatic int 68178546Sjbhash_def_cmp(void *d1, void *d2) 69178481Sjb{ 70178481Sjb return (d1 != d2); 71178481Sjb} 72178481Sjb 73178481Sjb 74178481Sjbint 75178481Sjbhash_name(int nbuckets, const char *name) 76178481Sjb{ 77178481Sjb const char *c; 78178481Sjb ulong_t g; 79178481Sjb int h = 0; 80178481Sjb 81178481Sjb for (c = name; *c; c++) { 82178481Sjb h = (h << 4) + *c; 83178481Sjb if ((g = (h & 0xf0000000)) != 0) { 84178481Sjb h ^= (g >> 24); 85178481Sjb h ^= g; 86178481Sjb } 87178481Sjb } 88178481Sjb 89178481Sjb return (h % nbuckets); 90178481Sjb} 91178481Sjb 92178481Sjbhash_t * 93178481Sjbhash_new(int nbuckets, int (*hashfn)(int, void *), int (*cmp)(void *, void *)) 94178481Sjb{ 95178481Sjb hash_t *hash; 96178481Sjb 97178481Sjb hash = xmalloc(sizeof (hash_t)); 98178481Sjb hash->h_buckets = xcalloc(sizeof (list_t *) * nbuckets); 99178481Sjb hash->h_nbuckets = nbuckets; 100178546Sjb hash->h_hashfn = hashfn ? hashfn : hash_def_hash; 101178546Sjb hash->h_cmp = cmp ? cmp : hash_def_cmp; 102178481Sjb 103178481Sjb return (hash); 104178481Sjb} 105178481Sjb 106178481Sjbvoid 107178481Sjbhash_add(hash_t *hash, void *key) 108178481Sjb{ 109178481Sjb int bucket = hash->h_hashfn(hash->h_nbuckets, key); 110178481Sjb 111178481Sjb list_add(&hash->h_buckets[bucket], key); 112178481Sjb} 113178481Sjb 114178481Sjbstatic int 115178481Sjbhash_add_cb(void *node, void *private) 116178481Sjb{ 117178481Sjb hash_add((hash_t *)private, node); 118178481Sjb return (0); 119178481Sjb} 120178481Sjb 121178481Sjbvoid 122178481Sjbhash_merge(hash_t *to, hash_t *from) 123178481Sjb{ 124178481Sjb (void) hash_iter(from, hash_add_cb, to); 125178481Sjb} 126178481Sjb 127178481Sjbstatic int 128178546Sjbhash_remove_cb(void *key1, void *key2, void *arg) 129178481Sjb{ 130178546Sjb hash_t *hash = arg; 131178481Sjb return (hash->h_cmp(key1, key2)); 132178481Sjb} 133178481Sjb 134178481Sjbvoid 135178481Sjbhash_remove(hash_t *hash, void *key) 136178481Sjb{ 137178481Sjb int bucket = hash->h_hashfn(hash->h_nbuckets, key); 138178481Sjb 139178481Sjb (void) list_remove(&hash->h_buckets[bucket], key, 140178546Sjb hash_remove_cb, hash); 141178481Sjb} 142178481Sjb 143178481Sjbint 144178481Sjbhash_match(hash_t *hash, void *key, int (*fun)(void *, void *), 145178481Sjb void *private) 146178481Sjb{ 147178481Sjb int bucket = hash->h_hashfn(hash->h_nbuckets, key); 148178481Sjb 149178481Sjb return (list_iter(hash->h_buckets[bucket], fun, private) < 0); 150178481Sjb} 151178481Sjb 152178481Sjbstatic int 153178546Sjbhash_find_list_cb(void *node, void *arg) 154178481Sjb{ 155178546Sjb struct hash_data *hd = arg; 156178481Sjb int cbrc; 157178481Sjb int rc = 0; 158178481Sjb 159178481Sjb if (hd->hd_hash->h_cmp(hd->hd_key, node) == 0) { 160178481Sjb if ((cbrc = hd->hd_fun(node, hd->hd_private)) < 0) 161178481Sjb return (cbrc); 162178481Sjb rc += cbrc; 163178481Sjb } 164178481Sjb 165178481Sjb return (rc); 166178481Sjb} 167178481Sjb 168178481Sjbint 169178481Sjbhash_find_iter(hash_t *hash, void *key, int (*fun)(void *, void *), 170178481Sjb void *private) 171178481Sjb{ 172178481Sjb int bucket = hash->h_hashfn(hash->h_nbuckets, key); 173178481Sjb struct hash_data hd; 174178481Sjb 175178481Sjb hd.hd_hash = hash; 176178481Sjb hd.hd_fun = fun; 177178481Sjb hd.hd_key = key; 178178481Sjb hd.hd_private = private; 179178481Sjb 180178546Sjb return (list_iter(hash->h_buckets[bucket], hash_find_list_cb, 181178481Sjb &hd)); 182178481Sjb} 183178481Sjb 184178481Sjb/* stop on first match */ 185178481Sjbstatic int 186178546Sjbhash_find_first_cb(void *node, void *arg) 187178481Sjb{ 188178546Sjb struct hash_data *hd = arg; 189178481Sjb if (hd->hd_hash->h_cmp(hd->hd_key, node) == 0) { 190178481Sjb hd->hd_ret = node; 191178481Sjb return (-1); 192178481Sjb } 193178481Sjb 194178481Sjb return (0); 195178481Sjb} 196178481Sjb 197178481Sjbint 198178481Sjbhash_find(hash_t *hash, void *key, void **value) 199178481Sjb{ 200178481Sjb int ret; 201178481Sjb struct hash_data hd; 202178481Sjb 203178481Sjb hd.hd_hash = hash; 204178481Sjb hd.hd_fun = hash_find_first_cb; 205178481Sjb hd.hd_key = key; 206178481Sjb 207178546Sjb ret = hash_match(hash, key, hash_find_first_cb, &hd); 208178481Sjb if (ret && value) 209178481Sjb *value = hd.hd_ret; 210178481Sjb 211178481Sjb return (ret); 212178481Sjb} 213178481Sjb 214178481Sjbint 215178481Sjbhash_iter(hash_t *hash, int (*fun)(void *, void *), void *private) 216178481Sjb{ 217178481Sjb int cumrc = 0; 218178481Sjb int cbrc; 219178481Sjb int i; 220178481Sjb 221178481Sjb for (i = 0; i < hash->h_nbuckets; i++) { 222178481Sjb if (hash->h_buckets[i] != NULL) { 223178481Sjb if ((cbrc = list_iter(hash->h_buckets[i], fun, 224178481Sjb private)) < 0) 225178481Sjb return (cbrc); 226178481Sjb cumrc += cbrc; 227178481Sjb } 228178481Sjb } 229178481Sjb 230178481Sjb return (cumrc); 231178481Sjb} 232178481Sjb 233178481Sjbint 234178481Sjbhash_count(hash_t *hash) 235178481Sjb{ 236178481Sjb int num, i; 237178481Sjb 238178481Sjb for (num = 0, i = 0; i < hash->h_nbuckets; i++) 239178481Sjb num += list_count(hash->h_buckets[i]); 240178481Sjb 241178481Sjb return (num); 242178481Sjb} 243178481Sjb 244178481Sjbvoid 245178481Sjbhash_free(hash_t *hash, void (*datafree)(void *, void *), void *private) 246178481Sjb{ 247178481Sjb int i; 248178481Sjb 249178481Sjb if (hash == NULL) 250178481Sjb return; 251178481Sjb 252178481Sjb for (i = 0; i < hash->h_nbuckets; i++) 253178481Sjb list_free(hash->h_buckets[i], datafree, private); 254178481Sjb free(hash->h_buckets); 255178481Sjb free(hash); 256178481Sjb} 257178481Sjb 258178481Sjbvoid 259178481Sjbhash_stats(hash_t *hash, int verbose) 260178481Sjb{ 261178481Sjb int min = list_count(hash->h_buckets[0]); 262178481Sjb int minidx = 0; 263178481Sjb int max = min; 264178481Sjb int maxidx = 0; 265178481Sjb int tot = min; 266178481Sjb int count; 267178481Sjb int i; 268178481Sjb 269178481Sjb if (min && verbose) 270178481Sjb printf("%3d: %d\n", 0, min); 271178481Sjb for (i = 1; i < hash->h_nbuckets; i++) { 272178481Sjb count = list_count(hash->h_buckets[i]); 273178481Sjb if (min > count) { 274178481Sjb min = count; 275178481Sjb minidx = i; 276178481Sjb } 277178481Sjb if (max < count) { 278178481Sjb max = count; 279178481Sjb maxidx = i; 280178481Sjb } 281178481Sjb if (count && verbose) 282178481Sjb printf("%3d: %d\n", i, count); 283178481Sjb tot += count; 284178481Sjb } 285178481Sjb 286178481Sjb printf("Hash statistics:\n"); 287178481Sjb printf(" Buckets: %d\n", hash->h_nbuckets); 288178481Sjb printf(" Items : %d\n", tot); 289178481Sjb printf(" Min/Max: %d in #%d, %d in #%d\n", min, minidx, max, maxidx); 290178481Sjb printf(" Average: %5.2f\n", (float)tot / (float)hash->h_nbuckets); 291178481Sjb} 292