usr/src/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)();
  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 }