1/* 2 * CDDL HEADER START 3 * 4 * The contents of this file are subject to the terms of the 5 * Common Development and Distribution License, Version 1.0 only 6 * (the "License"). You may not use this file except in compliance 7 * with the License. 8 * 9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 10 * or http://www.opensolaris.org/os/licensing. 11 * See the License for the specific language governing permissions 12 * and limitations under the License. 13 * 14 * When distributing Covered Code, include this CDDL HEADER in each 15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 16 * If applicable, add the following below this CDDL HEADER, with the 17 * fields enclosed by brackets "[]" replaced with your own identifying 18 * information: Portions Copyright [yyyy] [name of copyright owner] 19 * 20 * CDDL HEADER END 21 */ 22/* 23 * Copyright 2004 Sun Microsystems, Inc. All rights reserved. 24 * Use is subject to license terms. 25 */ 26 27#pragma ident "@(#)hash.c 1.5 05/06/08 SMI" 28 29/* 30 * Routines for manipulating hash tables 31 */ 32 33#if !defined(__APPLE__) 34#include <stdio.h> 35#include <stdlib.h> 36#include <strings.h> 37#include <sys/types.h> 38#include <sys/sysmacros.h> 39 40#include "hash.h" 41#include "memory.h" 42#include "list.h" 43 44#else 45#include <stdio.h> 46#include <stdlib.h> 47#include <strings.h> 48#include <sys/types.h> 49// #include <sys/sysmacros.h> 50 51#include "darwin_shim.h" 52#include "hash.h" 53#include "memory.h" 54#include "list.h" 55 56#endif /* __APPLE__ */ 57 58struct hash { 59 int h_nbuckets; 60 list_t **h_buckets; 61 62 int (*h_hashfn)(int, void *); 63 int (*h_cmp)(void *, void *); 64}; 65 66struct hash_data { 67 hash_t *hd_hash; 68 int (*hd_fun)(); 69 void *hd_key; 70 void *hd_private; 71 72 void *hd_ret; 73}; 74 75static int 76hash_def_hash(int nbuckets, uintptr_t data) 77{ 78 return (data % nbuckets); 79} 80 81static int 82hash_def_cmp(uintptr_t d1, uintptr_t d2) 83{ 84 return (d1 != d2); 85} 86 87 88int 89hash_name(int nbuckets, const char *name) 90{ 91 const char *c; 92 ulong_t g; 93 int h = 0; 94 95 for (c = name; *c; c++) { 96 h = (h << 4) + *c; 97 if ((g = (h & 0xf0000000)) != 0) { 98 h ^= (g >> 24); 99 h ^= g; 100 } 101 } 102 103 return (h % nbuckets); 104} 105 106hash_t * 107hash_new(int nbuckets, int (*hashfn)(int, void *), int (*cmp)(void *, void *)) 108{ 109 hash_t *hash; 110 111 hash = xmalloc(sizeof (hash_t)); 112 hash->h_buckets = xcalloc(sizeof (list_t *) * nbuckets); 113 hash->h_nbuckets = nbuckets; 114 hash->h_hashfn = hashfn ? hashfn : (int (*)())hash_def_hash; 115 hash->h_cmp = cmp ? cmp : (int (*)())hash_def_cmp; 116 117 return (hash); 118} 119 120void 121hash_add(hash_t *hash, void *key) 122{ 123 int bucket = hash->h_hashfn(hash->h_nbuckets, key); 124 125 list_add(&hash->h_buckets[bucket], key); 126} 127 128static int 129hash_add_cb(void *node, void *private) 130{ 131 hash_add((hash_t *)private, node); 132 return (0); 133} 134 135void 136hash_merge(hash_t *to, hash_t *from) 137{ 138 (void) hash_iter(from, hash_add_cb, to); 139} 140 141static int 142hash_remove_cb(void *key1, void *key2, hash_t *hash) 143{ 144 return (hash->h_cmp(key1, key2)); 145} 146 147void 148hash_remove(hash_t *hash, void *key) 149{ 150 int bucket = hash->h_hashfn(hash->h_nbuckets, key); 151 152 (void) list_remove(&hash->h_buckets[bucket], key, 153 (int (*)())hash_remove_cb, hash); 154} 155 156int 157hash_match(hash_t *hash, void *key, int (*fun)(void *, void *), 158 void *private) 159{ 160 int bucket = hash->h_hashfn(hash->h_nbuckets, key); 161 162 return (list_iter(hash->h_buckets[bucket], fun, private) < 0); 163} 164 165static int 166hash_find_list_cb(void *node, struct hash_data *hd) 167{ 168 int cbrc; 169 int rc = 0; 170 171 if (hd->hd_hash->h_cmp(hd->hd_key, node) == 0) { 172 if ((cbrc = hd->hd_fun(node, hd->hd_private)) < 0) 173 return (cbrc); 174 rc += cbrc; 175 } 176 177 return (rc); 178} 179 180int 181hash_find_iter(hash_t *hash, void *key, int (*fun)(void *, void *), 182 void *private) 183{ 184 int bucket = hash->h_hashfn(hash->h_nbuckets, key); 185 struct hash_data hd; 186 187 hd.hd_hash = hash; 188 hd.hd_fun = fun; 189 hd.hd_key = key; 190 hd.hd_private = private; 191 192 return (list_iter(hash->h_buckets[bucket], (int (*)())hash_find_list_cb, 193 &hd)); 194} 195 196/* stop on first match */ 197static int 198hash_find_first_cb(void *node, struct hash_data *hd) 199{ 200 if (hd->hd_hash->h_cmp(hd->hd_key, node) == 0) { 201 hd->hd_ret = node; 202 return (-1); 203 } 204 205 return (0); 206} 207 208int 209hash_find(hash_t *hash, void *key, void **value) 210{ 211 int ret; 212 struct hash_data hd; 213 214 hd.hd_hash = hash; 215 hd.hd_fun = hash_find_first_cb; 216 hd.hd_key = key; 217 218 ret = hash_match(hash, key, (int (*)())hash_find_first_cb, &hd); 219 if (ret && value) 220 *value = hd.hd_ret; 221 222 return (ret); 223} 224 225int 226hash_iter(hash_t *hash, int (*fun)(void *, void *), void *private) 227{ 228 int cumrc = 0; 229 int cbrc; 230 int i; 231 232 for (i = 0; i < hash->h_nbuckets; i++) { 233 if (hash->h_buckets[i] != NULL) { 234 if ((cbrc = list_iter(hash->h_buckets[i], fun, 235 private)) < 0) 236 return (cbrc); 237 cumrc += cbrc; 238 } 239 } 240 241 return (cumrc); 242} 243 244int 245hash_count(hash_t *hash) 246{ 247 int num, i; 248 249 for (num = 0, i = 0; i < hash->h_nbuckets; i++) 250 num += list_count(hash->h_buckets[i]); 251 252 return (num); 253} 254 255void 256hash_free(hash_t *hash, void (*datafree)(void *, void *), void *private) 257{ 258 int i; 259 260 if (hash == NULL) 261 return; 262 263 for (i = 0; i < hash->h_nbuckets; i++) 264 list_free(hash->h_buckets[i], datafree, private); 265 free(hash->h_buckets); 266 free(hash); 267} 268 269void 270hash_stats(hash_t *hash, int verbose) 271{ 272 int min = list_count(hash->h_buckets[0]); 273 int minidx = 0; 274 int max = min; 275 int maxidx = 0; 276 int tot = min; 277 int count; 278 int i; 279 280 if (min && verbose) 281 printf("%3d: %d\n", 0, min); 282 for (i = 1; i < hash->h_nbuckets; i++) { 283 count = list_count(hash->h_buckets[i]); 284 if (min > count) { 285 min = count; 286 minidx = i; 287 } 288 if (max < count) { 289 max = count; 290 maxidx = i; 291 } 292 if (count && verbose) 293 printf("%3d: %d\n", i, count); 294 tot += count; 295 } 296 297 printf("Hash statistics:\n"); 298 printf(" Buckets: %d\n", hash->h_nbuckets); 299 printf(" Items : %d\n", tot); 300 printf(" Min/Max: %d in #%d, %d in #%d\n", min, minidx, max, maxidx); 301 printf(" Average: %5.2f\n", (float)tot / (float)hash->h_nbuckets); 302} 303