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