cddl/contrib/opensolaris/tools/ctf/cvt/hash.c

   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 }