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