xref: /titanic_41/usr/src/lib/libipmi/common/ipmi_hash.c (revision 2eeaed14a5e2ed9bd811643ad5bffc3510ca0310)
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
ipmi_hash_double(ulong_t size)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
ipmi_hash_half(ulong_t size)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 *
ipmi_hash_create(ipmi_handle_t * hp,size_t linkoffs,const void * (* convert)(const void * elem),ulong_t (* compute)(const void * key),int (* compare)(const void * lkey,const void * rkey))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
ipmi_hash_destroy(ipmi_hash_t * ihp)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
ipmi_hash_strhash(const void * key)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
ipmi_hash_strcmp(const void * lhs,const void * rhs)143 ipmi_hash_strcmp(const void *lhs, const void *rhs)
144 {
145 	return (strcmp(lhs, rhs));
146 }
147 
148 ulong_t
ipmi_hash_ptrhash(const void * key)149 ipmi_hash_ptrhash(const void *key)
150 {
151 	return (*((const uintptr_t *)key) >> 4);
152 }
153 
154 int
ipmi_hash_ptrcmp(const void * lhs,const void * rhs)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
ipmi_hash_compute(ipmi_hash_t * ihp,const void * elem)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
ipmi_hash_resize(ipmi_hash_t * ihp,ulong_t nsize)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 *
ipmi_hash_lookup(ipmi_hash_t * ihp,const void * search)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 *
ipmi_hash_first(ipmi_hash_t * ihp)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 *
ipmi_hash_next(ipmi_hash_t * ihp,void * elem)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
ipmi_hash_insert(ipmi_hash_t * ihp,void * elem)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
ipmi_hash_remove(ipmi_hash_t * ihp,void * elem)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
ipmi_hash_count(ipmi_hash_t * ihp)295 ipmi_hash_count(ipmi_hash_t *ihp)
296 {
297 	return (ihp->ih_nelements);
298 }
299