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