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 "%Z%%M% %I% %E% SMI" 28 29 /* 30 * Routines for manipulating hash tables 31 */ 32 33 #include <stdio.h> 34 #include <stdlib.h> 35 #include <strings.h> 36 #include <sys/types.h> 37 #include <sys/sysmacros.h> 38 39 #include "hash.h" 40 #include "memory.h" 41 #include "list.h" 42 43 struct hash { 44 int h_nbuckets; 45 list_t **h_buckets; 46 47 int (*h_hashfn)(int, void *); 48 int (*h_cmp)(void *, void *); 49 }; 50 51 struct hash_data { 52 hash_t *hd_hash; 53 int (*hd_fun)(void *, void *); 54 void *hd_key; 55 void *hd_private; 56 57 void *hd_ret; 58 }; 59 60 static int 61 hash_def_hash(int nbuckets, void *arg) 62 { 63 uintptr_t data = (uintptr_t) arg; 64 return (data % nbuckets); 65 } 66 67 static int 68 hash_def_cmp(void *d1, void *d2) 69 { 70 return (d1 != d2); 71 } 72 73 74 int 75 hash_name(int nbuckets, const char *name) 76 { 77 const char *c; 78 ulong_t g; 79 int h = 0; 80 81 for (c = name; *c; c++) { 82 h = (h << 4) + *c; 83 if ((g = (h & 0xf0000000)) != 0) { 84 h ^= (g >> 24); 85 h ^= g; 86 } 87 } 88 89 return (h % nbuckets); 90 } 91 92 hash_t * 93 hash_new(int nbuckets, int (*hashfn)(int, void *), int (*cmp)(void *, void *)) 94 { 95 hash_t *hash; 96 97 hash = xmalloc(sizeof (hash_t)); 98 hash->h_buckets = xcalloc(sizeof (list_t *) * nbuckets); 99 hash->h_nbuckets = nbuckets; 100 hash->h_hashfn = hashfn ? hashfn : hash_def_hash; 101 hash->h_cmp = cmp ? cmp : hash_def_cmp; 102 103 return (hash); 104 } 105 106 void 107 hash_add(hash_t *hash, void *key) 108 { 109 int bucket = hash->h_hashfn(hash->h_nbuckets, key); 110 111 list_add(&hash->h_buckets[bucket], key); 112 } 113 114 static int 115 hash_add_cb(void *node, void *private) 116 { 117 hash_add((hash_t *)private, node); 118 return (0); 119 } 120 121 void 122 hash_merge(hash_t *to, hash_t *from) 123 { 124 (void) hash_iter(from, hash_add_cb, to); 125 } 126 127 static int 128 hash_remove_cb(void *key1, void *key2, void *arg) 129 { 130 hash_t *hash = arg; 131 return (hash->h_cmp(key1, key2)); 132 } 133 134 void 135 hash_remove(hash_t *hash, void *key) 136 { 137 int bucket = hash->h_hashfn(hash->h_nbuckets, key); 138 139 (void) list_remove(&hash->h_buckets[bucket], key, 140 hash_remove_cb, hash); 141 } 142 143 int 144 hash_match(hash_t *hash, void *key, int (*fun)(void *, void *), 145 void *private) 146 { 147 int bucket = hash->h_hashfn(hash->h_nbuckets, key); 148 149 return (list_iter(hash->h_buckets[bucket], fun, private) < 0); 150 } 151 152 static int 153 hash_find_list_cb(void *node, void *arg) 154 { 155 struct hash_data *hd = arg; 156 int cbrc; 157 int rc = 0; 158 159 if (hd->hd_hash->h_cmp(hd->hd_key, node) == 0) { 160 if ((cbrc = hd->hd_fun(node, hd->hd_private)) < 0) 161 return (cbrc); 162 rc += cbrc; 163 } 164 165 return (rc); 166 } 167 168 int 169 hash_find_iter(hash_t *hash, void *key, int (*fun)(void *, void *), 170 void *private) 171 { 172 int bucket = hash->h_hashfn(hash->h_nbuckets, key); 173 struct hash_data hd; 174 175 hd.hd_hash = hash; 176 hd.hd_fun = fun; 177 hd.hd_key = key; 178 hd.hd_private = private; 179 180 return (list_iter(hash->h_buckets[bucket], hash_find_list_cb, 181 &hd)); 182 } 183 184 /* stop on first match */ 185 static int 186 hash_find_first_cb(void *node, void *arg) 187 { 188 struct hash_data *hd = arg; 189 if (hd->hd_hash->h_cmp(hd->hd_key, node) == 0) { 190 hd->hd_ret = node; 191 return (-1); 192 } 193 194 return (0); 195 } 196 197 int 198 hash_find(hash_t *hash, void *key, void **value) 199 { 200 int ret; 201 struct hash_data hd; 202 203 hd.hd_hash = hash; 204 hd.hd_fun = hash_find_first_cb; 205 hd.hd_key = key; 206 207 ret = hash_match(hash, key, hash_find_first_cb, &hd); 208 if (ret && value) 209 *value = hd.hd_ret; 210 211 return (ret); 212 } 213 214 int 215 hash_iter(hash_t *hash, int (*fun)(void *, void *), void *private) 216 { 217 int cumrc = 0; 218 int cbrc; 219 int i; 220 221 for (i = 0; i < hash->h_nbuckets; i++) { 222 if (hash->h_buckets[i] != NULL) { 223 if ((cbrc = list_iter(hash->h_buckets[i], fun, 224 private)) < 0) 225 return (cbrc); 226 cumrc += cbrc; 227 } 228 } 229 230 return (cumrc); 231 } 232 233 int 234 hash_count(hash_t *hash) 235 { 236 int num, i; 237 238 for (num = 0, i = 0; i < hash->h_nbuckets; i++) 239 num += list_count(hash->h_buckets[i]); 240 241 return (num); 242 } 243 244 void 245 hash_free(hash_t *hash, void (*datafree)(void *, void *), void *private) 246 { 247 int i; 248 249 if (hash == NULL) 250 return; 251 252 for (i = 0; i < hash->h_nbuckets; i++) 253 list_free(hash->h_buckets[i], datafree, private); 254 free(hash->h_buckets); 255 free(hash); 256 } 257 258 void 259 hash_stats(hash_t *hash, int verbose) 260 { 261 int min = list_count(hash->h_buckets[0]); 262 int minidx = 0; 263 int max = min; 264 int maxidx = 0; 265 int tot = min; 266 int count; 267 int i; 268 269 if (min && verbose) 270 printf("%3d: %d\n", 0, min); 271 for (i = 1; i < hash->h_nbuckets; i++) { 272 count = list_count(hash->h_buckets[i]); 273 if (min > count) { 274 min = count; 275 minidx = i; 276 } 277 if (max < count) { 278 max = count; 279 maxidx = i; 280 } 281 if (count && verbose) 282 printf("%3d: %d\n", i, count); 283 tot += count; 284 } 285 286 printf("Hash statistics:\n"); 287 printf(" Buckets: %d\n", hash->h_nbuckets); 288 printf(" Items : %d\n", tot); 289 printf(" Min/Max: %d in #%d, %d in #%d\n", min, minidx, max, maxidx); 290 printf(" Average: %5.2f\n", (float)tot / (float)hash->h_nbuckets); 291 } 292