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