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 } 299