usr/src/lib/libipmi/common/ipmi_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 (the "License").
   6  * You may not use this file except in compliance with the License.
   7  *
   8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
   9  * or http://www.opensolaris.org/os/licensing.
  10  * See the License for the specific language governing permissions
  11  * and limitations under the License.
  12  *
  13  * When distributing Covered Code, include this CDDL HEADER in each
  14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
  15  * If applicable, add the following below this CDDL HEADER, with the
  16  * fields enclosed by brackets "[]" replaced with your own identifying
  17  * information: Portions Copyright [yyyy] [name of copyright owner]
  18  *
  19  * CDDL HEADER END
  20  */
  21 /*
  22  * Copyright 2008 Sun Microsystems, Inc.  All rights reserved.
  23  * Use is subject to license terms.
  24  */
  25
  26 #pragma ident   "%Z%%M% %I%     %E% SMI"
  27
  28 #include <strings.h>
  29
  30 #include <assert.h>
  31 #include <ipmi_impl.h>
  32 #include <string.h>
  33 #include <strings.h>
  34
  35 /*
  36  * The (prime) number 137 happens to have the nice property that -- when
  37  * multiplied by two and added to 33 -- one gets a pretty long series of
  38  * primes:
  39  *
  40  *   307, 647, 1327, 2687, 5407, 10847, 21727, 43487
  41  *
  42  * And beyond 43487, the numbers in the series have few factors or are prime.
  43  * That is, one can have a prime number and roughly double it to get another
  44  * prime number -- but the series starts at 137.  A size of 137 buckets doesn't
  45  * particularly accommodate small hash tables, but we note that 13 also yields
  46  * a reasonable sequence when doubling it and adding 5:
  47  *
  48  *   13, 31, 67, 139, 283, 571
  49  *
  50  * So we start with this second sequence, crossing over to the first when
  51  * the size is greater than 137.  (And when reducing the size of the hash
  52  * table, we cross back when the size gets below 67.)
  53  */
  54 #define IPMI_HASHCROSSOVER      137
  55 #define IPMI_HASHCROSSUNDER     67
  56 #define IPMI_HASHMINSIZE                13
  57
  58 static ulong_t
  59 ipmi_hash_double(ulong_t size)
  60 {
  61         ulong_t nsize;
  62
  63         if (size < IPMI_HASHCROSSOVER) {
  64                 nsize = (size * 2) + 5;
  65                 return (nsize < IPMI_HASHCROSSOVER ? nsize :
  66                     IPMI_HASHCROSSOVER);
  67         }
  68
  69         return ((size * 2) + 33);
  70 }
  71
  72 static ulong_t
  73 ipmi_hash_half(ulong_t size)
  74 {
  75         ulong_t nsize;
  76
  77         if (size > IPMI_HASHCROSSUNDER) {
  78                 nsize = (size - 33) / 2;
  79                 return (nsize > IPMI_HASHCROSSUNDER ? nsize :
  80                     IPMI_HASHCROSSUNDER);
  81         }
  82
  83         nsize = (size - 5) / 2;
  84
  85         return (nsize > IPMI_HASHMINSIZE ? nsize : IPMI_HASHMINSIZE);
  86 }
  87
  88 ipmi_hash_t *
  89 ipmi_hash_create(ipmi_handle_t *hp, size_t linkoffs,
  90     const void *(*convert)(const void *elem),
  91     ulong_t (*compute)(const void *key),
  92     int (*compare)(const void *lkey, const void *rkey))
  93 {
  94         ipmi_hash_t *ihp;
  95
  96         if ((ihp = ipmi_zalloc(hp, sizeof (ipmi_hash_t))) == NULL)
  97                 return (NULL);
  98
  99         ihp->ih_handle = hp;
 100         ihp->ih_nbuckets = IPMI_HASHMINSIZE;
 101         ihp->ih_linkoffs = linkoffs;
 102         ihp->ih_convert = convert;
 103         ihp->ih_compute = compute;
 104         ihp->ih_compare = compare;
 105
 106         if ((ihp->ih_buckets = ipmi_zalloc(hp,
 107             ihp->ih_nbuckets * sizeof (void *))) == NULL) {
 108                 ipmi_free(hp, ihp);
 109                 return (NULL);
 110         }
 111
 112         return (ihp);
 113 }
 114
 115 void
 116 ipmi_hash_destroy(ipmi_hash_t *ihp)
 117 {
 118         if (ihp != NULL) {
 119                 ipmi_free(ihp->ih_handle, ihp->ih_buckets);
 120                 ipmi_free(ihp->ih_handle, ihp);
 121         }
 122 }
 123
 124 ulong_t
 125 ipmi_hash_strhash(const void *key)
 126 {
 127         ulong_t g, h = 0;
 128         const char *p;
 129
 130         for (p = key; *p != '\0'; p++) {
 131                 h = (h << 4) + *p;
 132
 133                 if ((g = (h & 0xf0000000)) != 0) {
 134                         h ^= (g >> 24);
 135                         h ^= g;
 136                 }
 137         }
 138
 139         return (h);
 140 }
 141
 142 int
 143 ipmi_hash_strcmp(const void *lhs, const void *rhs)
 144 {
 145         return (strcmp(lhs, rhs));
 146 }
 147
 148 ulong_t
 149 ipmi_hash_ptrhash(const void *key)
 150 {
 151         return (*((const uintptr_t *)key) >> 4);
 152 }
 153
 154 int
 155 ipmi_hash_ptrcmp(const void *lhs, const void *rhs)
 156 {
 157         const uintptr_t *l = lhs, *r = rhs;
 158
 159         return (*l == *r ? 0 : -1);
 160 }
 161
 162
 163 static ulong_t
 164 ipmi_hash_compute(ipmi_hash_t *ihp, const void *elem)
 165 {
 166         return (ihp->ih_compute(ihp->ih_convert(elem)) % ihp->ih_nbuckets);
 167 }
 168
 169 static void
 170 ipmi_hash_resize(ipmi_hash_t *ihp, ulong_t nsize)
 171 {
 172         size_t osize = ihp->ih_nbuckets;
 173         ipmi_handle_t *hp = ihp->ih_handle;
 174         ipmi_hash_link_t *link, **nbuckets;
 175         ulong_t idx, nidx;
 176
 177         assert(nsize >= IPMI_HASHMINSIZE);
 178
 179         if (nsize == osize)
 180                 return;
 181
 182         if ((nbuckets = ipmi_zalloc(hp, nsize * sizeof (void *))) == NULL) {
 183                 /*
 184                  * This routine can't fail, so we just eat the failure here.
 185                  * The consequences of this failing are only for performance;
 186                  * correctness is not affected by our inability to resize
 187                  * the hash table.
 188                  */
 189                 return;
 190         }
 191
 192         ihp->ih_nbuckets = nsize;
 193
 194         for (idx = 0; idx < osize; idx++) {
 195                 while ((link = ihp->ih_buckets[idx]) != NULL) {
 196                         void *elem;
 197
 198                         /*
 199                          * For every hash element, we need to remove it from
 200                          * this bucket, and rehash it given the new bucket
 201                          * size.
 202                          */
 203                         ihp->ih_buckets[idx] = link->ihl_next;
 204                         elem = (void *)((uintptr_t)link - ihp->ih_linkoffs);
 205                         nidx = ipmi_hash_compute(ihp, elem);
 206
 207                         link->ihl_next = nbuckets[nidx];
 208                         nbuckets[nidx] = link;
 209                 }
 210         }
 211
 212         ipmi_free(hp, ihp->ih_buckets);
 213         ihp->ih_buckets = nbuckets;
 214 }
 215
 216 void *
 217 ipmi_hash_lookup(ipmi_hash_t *ihp, const void *search)
 218 {
 219         ulong_t idx = ihp->ih_compute(search) % ihp->ih_nbuckets;
 220         ipmi_hash_link_t *hl;
 221
 222         for (hl = ihp->ih_buckets[idx]; hl != NULL; hl = hl->ihl_next) {
 223                 void *elem = (void *)((uintptr_t)hl - ihp->ih_linkoffs);
 224
 225                 if (ihp->ih_compare(ihp->ih_convert(elem), search) == 0)
 226                         return (elem);
 227         }
 228
 229         return (NULL);
 230 }
 231
 232 void *
 233 ipmi_hash_first(ipmi_hash_t *ihp)
 234 {
 235         void *link = ipmi_list_next(&(ihp)->ih_list);
 236
 237         if (link == NULL)
 238                 return (NULL);
 239
 240         return ((void *)((uintptr_t)link - ihp->ih_linkoffs));
 241 }
 242
 243 void *
 244 ipmi_hash_next(ipmi_hash_t *ihp, void *elem)
 245 {
 246         void *link = ipmi_list_next((uintptr_t)elem + ihp->ih_linkoffs);
 247
 248         if (link == NULL)
 249                 return (NULL);
 250
 251         return ((void *)((uintptr_t)link - ihp->ih_linkoffs));
 252 }
 253
 254 void
 255 ipmi_hash_insert(ipmi_hash_t *ihp, void *elem)
 256 {
 257         ipmi_hash_link_t *link = (void *)((uintptr_t)elem + ihp->ih_linkoffs);
 258         ulong_t idx = ipmi_hash_compute(ihp, elem);
 259
 260         assert(ipmi_hash_lookup(ihp, ihp->ih_convert(elem)) == NULL);
 261
 262         link->ihl_next = ihp->ih_buckets[idx];
 263         ihp->ih_buckets[idx] = link;
 264
 265         ipmi_list_append(&ihp->ih_list, link);
 266
 267         if (++ihp->ih_nelements > ihp->ih_nbuckets / 2)
 268                 ipmi_hash_resize(ihp, ipmi_hash_double(ihp->ih_nbuckets));
 269 }
 270
 271 void
 272 ipmi_hash_remove(ipmi_hash_t *ihp, void *elem)
 273 {
 274         ulong_t idx = ipmi_hash_compute(ihp, elem);
 275         ipmi_hash_link_t *link = (void *)((uintptr_t)elem + ihp->ih_linkoffs);
 276         ipmi_hash_link_t **hlp = &ihp->ih_buckets[idx];
 277
 278         for (; *hlp != NULL; hlp = &(*hlp)->ihl_next) {
 279                 if (*hlp == link)
 280                         break;
 281         }
 282
 283         assert(*hlp != NULL);
 284         *hlp = (*hlp)->ihl_next;
 285
 286         ipmi_list_delete(&ihp->ih_list, link);
 287
 288         assert(ihp->ih_nelements > 0);
 289
 290         if (--ihp->ih_nelements < ihp->ih_nbuckets / 4)
 291                 ipmi_hash_resize(ihp, ipmi_hash_half(ihp->ih_nbuckets));
 292 }
 293
 294 size_t
 295 ipmi_hash_count(ipmi_hash_t *ihp)
 296 {
 297         return (ihp->ih_nelements);
 298 }