1*0Sstevel@tonic-gate /*
2*0Sstevel@tonic-gate * Copyright (c) 1993-2001 by Sun Microsystems, Inc.
3*0Sstevel@tonic-gate * All rights reserved.
4*0Sstevel@tonic-gate */
5*0Sstevel@tonic-gate
6*0Sstevel@tonic-gate #pragma ident "%Z%%M% %I% %E% SMI"
7*0Sstevel@tonic-gate
8*0Sstevel@tonic-gate /*
9*0Sstevel@tonic-gate * Copyright 1988, 1991 by Carnegie Mellon University
10*0Sstevel@tonic-gate *
11*0Sstevel@tonic-gate * All Rights Reserved
12*0Sstevel@tonic-gate *
13*0Sstevel@tonic-gate * Permission to use, copy, modify, and distribute this software and its
14*0Sstevel@tonic-gate * documentation for any purpose and without fee is hereby granted, provided
15*0Sstevel@tonic-gate * that the above copyright notice appear in all copies and that both that
16*0Sstevel@tonic-gate * copyright notice and this permission notice appear in supporting
17*0Sstevel@tonic-gate * documentation, and that the name of Carnegie Mellon University not be used
18*0Sstevel@tonic-gate * in advertising or publicity pertaining to distribution of the software
19*0Sstevel@tonic-gate * without specific, written prior permission.
20*0Sstevel@tonic-gate *
21*0Sstevel@tonic-gate * CARNEGIE MELLON UNIVERSITY DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS
22*0Sstevel@tonic-gate * SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS.
23*0Sstevel@tonic-gate * IN NO EVENT SHALL CMU BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
24*0Sstevel@tonic-gate * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR
25*0Sstevel@tonic-gate * PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS
26*0Sstevel@tonic-gate * ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF
27*0Sstevel@tonic-gate * THIS SOFTWARE.
28*0Sstevel@tonic-gate */
29*0Sstevel@tonic-gate
30*0Sstevel@tonic-gate /*
31*0Sstevel@tonic-gate * Generalized hash table ADT
32*0Sstevel@tonic-gate *
33*0Sstevel@tonic-gate * Provides multiple, dynamically-allocated, variable-sized hash tables on
34*0Sstevel@tonic-gate * various data and keys.
35*0Sstevel@tonic-gate *
36*0Sstevel@tonic-gate * This package attempts to follow some of the coding conventions suggested
37*0Sstevel@tonic-gate * by Bob Sidebotham and the AFS Clean Code Committee of the
38*0Sstevel@tonic-gate * Information Technology Center at Carnegie Mellon.
39*0Sstevel@tonic-gate *
40*0Sstevel@tonic-gate * Additions for per bucket locking, and configurable dynamic free of
41*0Sstevel@tonic-gate * unused entries.
42*0Sstevel@tonic-gate */
43*0Sstevel@tonic-gate
44*0Sstevel@tonic-gate #include <stdlib.h>
45*0Sstevel@tonic-gate #include <string.h>
46*0Sstevel@tonic-gate #include <sys/types.h>
47*0Sstevel@tonic-gate #include <sys/param.h>
48*0Sstevel@tonic-gate #include <sys/sysmacros.h>
49*0Sstevel@tonic-gate #include <stdarg.h>
50*0Sstevel@tonic-gate #include <stddef.h>
51*0Sstevel@tonic-gate #include <assert.h>
52*0Sstevel@tonic-gate #include <synch.h>
53*0Sstevel@tonic-gate #include "dhcpd.h"
54*0Sstevel@tonic-gate #include "hash.h"
55*0Sstevel@tonic-gate
56*0Sstevel@tonic-gate /*
57*0Sstevel@tonic-gate * Hash table size calculation routine.
58*0Sstevel@tonic-gate *
59*0Sstevel@tonic-gate * Estimate the size of a hash table based on the expected number of
60*0Sstevel@tonic-gate * entries, up to a maximum of HASHTABLESIZE.
61*0Sstevel@tonic-gate */
62*0Sstevel@tonic-gate static unsigned
hashi_Hsize(unsigned hint)63*0Sstevel@tonic-gate hashi_Hsize(unsigned hint)
64*0Sstevel@tonic-gate {
65*0Sstevel@tonic-gate unsigned f;
66*0Sstevel@tonic-gate
67*0Sstevel@tonic-gate if (hint == 0) /* Default size. */
68*0Sstevel@tonic-gate hint = HASHTABLESIZE;
69*0Sstevel@tonic-gate else if (hint < 16) /* Minimal size. */
70*0Sstevel@tonic-gate hint = 16;
71*0Sstevel@tonic-gate
72*0Sstevel@tonic-gate hint /= 4;
73*0Sstevel@tonic-gate for (f = 2; f * f <= hint; f++) { /* Find next largest prime. */
74*0Sstevel@tonic-gate if (hint % f == 0) {
75*0Sstevel@tonic-gate f = 1;
76*0Sstevel@tonic-gate hint++;
77*0Sstevel@tonic-gate }
78*0Sstevel@tonic-gate }
79*0Sstevel@tonic-gate return (MIN(HASHTABLESIZE, hint));
80*0Sstevel@tonic-gate }
81*0Sstevel@tonic-gate
82*0Sstevel@tonic-gate /*
83*0Sstevel@tonic-gate * Frees an entire linked list of bucket members (used in the
84*0Sstevel@tonic-gate * open hashing scheme). Does nothing if the passed pointer is NULL.
85*0Sstevel@tonic-gate *
86*0Sstevel@tonic-gate * Returns B_FALSE and members which could not be freed in bucketptr, when
87*0Sstevel@tonic-gate * force variable is set to B_FALSE, and free_data routine indicates
88*0Sstevel@tonic-gate * free did not occur.
89*0Sstevel@tonic-gate */
90*0Sstevel@tonic-gate static boolean_t
hashi_FreeMember(hash_member ** bucketptr,boolean_t (* free_data)(),boolean_t force)91*0Sstevel@tonic-gate hashi_FreeMember(hash_member **bucketptr, boolean_t (*free_data)(),
92*0Sstevel@tonic-gate boolean_t force)
93*0Sstevel@tonic-gate {
94*0Sstevel@tonic-gate hash_member *prev, *next, *unfree = NULL;
95*0Sstevel@tonic-gate boolean_t ret = B_TRUE;
96*0Sstevel@tonic-gate
97*0Sstevel@tonic-gate if (bucketptr) {
98*0Sstevel@tonic-gate for (prev = *bucketptr; prev; prev = next) {
99*0Sstevel@tonic-gate next = prev->next;
100*0Sstevel@tonic-gate prev->next = NULL;
101*0Sstevel@tonic-gate if (free_data != NULL) {
102*0Sstevel@tonic-gate if ((*free_data)(prev->data, force) ==
103*0Sstevel@tonic-gate B_FALSE) {
104*0Sstevel@tonic-gate ret = B_FALSE;
105*0Sstevel@tonic-gate prev->next = unfree;
106*0Sstevel@tonic-gate unfree = prev;
107*0Sstevel@tonic-gate } else {
108*0Sstevel@tonic-gate free(prev);
109*0Sstevel@tonic-gate }
110*0Sstevel@tonic-gate } else
111*0Sstevel@tonic-gate free(prev);
112*0Sstevel@tonic-gate }
113*0Sstevel@tonic-gate *bucketptr = unfree;
114*0Sstevel@tonic-gate }
115*0Sstevel@tonic-gate return (ret);
116*0Sstevel@tonic-gate }
117*0Sstevel@tonic-gate
118*0Sstevel@tonic-gate /*
119*0Sstevel@tonic-gate * Dynamic free initialization.
120*0Sstevel@tonic-gate */
121*0Sstevel@tonic-gate static void
hashi_Dinit(hash_tbl * hashtable,hash_member * memberptr)122*0Sstevel@tonic-gate hashi_Dinit(hash_tbl *hashtable, hash_member *memberptr)
123*0Sstevel@tonic-gate {
124*0Sstevel@tonic-gate (void) mutex_init(&memberptr->h_mtx, USYNC_THREAD, NULL);
125*0Sstevel@tonic-gate memberptr->h_time = time(NULL) + hashtable->dfree_time;
126*0Sstevel@tonic-gate memberptr->h_count = 1;
127*0Sstevel@tonic-gate }
128*0Sstevel@tonic-gate
129*0Sstevel@tonic-gate /*
130*0Sstevel@tonic-gate * Dynamic free reference count increment.
131*0Sstevel@tonic-gate */
132*0Sstevel@tonic-gate static void
hashi_Dhold(hash_member * memberptr)133*0Sstevel@tonic-gate hashi_Dhold(hash_member *memberptr)
134*0Sstevel@tonic-gate {
135*0Sstevel@tonic-gate (void) mutex_lock(&memberptr->h_mtx);
136*0Sstevel@tonic-gate memberptr->h_count++;
137*0Sstevel@tonic-gate (void) mutex_unlock(&memberptr->h_mtx);
138*0Sstevel@tonic-gate }
139*0Sstevel@tonic-gate
140*0Sstevel@tonic-gate /*
141*0Sstevel@tonic-gate * Dynamic free expired data. Return NULL if memberptr is successfully
142*0Sstevel@tonic-gate * dynamically freed, otherwise return memberptr.
143*0Sstevel@tonic-gate */
144*0Sstevel@tonic-gate static hash_member *
hashi_Dfree(hash_member * memberptr,boolean_t (* free_data)())145*0Sstevel@tonic-gate hashi_Dfree(hash_member *memberptr, boolean_t (*free_data)())
146*0Sstevel@tonic-gate {
147*0Sstevel@tonic-gate hash_member *next;
148*0Sstevel@tonic-gate
149*0Sstevel@tonic-gate next = memberptr->next;
150*0Sstevel@tonic-gate memberptr->next = NULL;
151*0Sstevel@tonic-gate if (hashi_FreeMember(&memberptr, free_data, B_FALSE) == B_TRUE)
152*0Sstevel@tonic-gate memberptr = NULL;
153*0Sstevel@tonic-gate else
154*0Sstevel@tonic-gate memberptr->next = next;
155*0Sstevel@tonic-gate return (memberptr);
156*0Sstevel@tonic-gate }
157*0Sstevel@tonic-gate
158*0Sstevel@tonic-gate /*
159*0Sstevel@tonic-gate * Hash table initialization routine.
160*0Sstevel@tonic-gate *
161*0Sstevel@tonic-gate * This routine creates and intializes a hash table of size "tablesize"
162*0Sstevel@tonic-gate * entries. Successful calls return a pointer to the hash table (which must
163*0Sstevel@tonic-gate * be passed to other hash routines to identify the hash table). Failed
164*0Sstevel@tonic-gate * calls return NULL.
165*0Sstevel@tonic-gate */
166*0Sstevel@tonic-gate hash_tbl *
hash_Init(unsigned tablesize,boolean_t (* dfree_data)(),time_t dtime,boolean_t lck)167*0Sstevel@tonic-gate hash_Init(unsigned tablesize, boolean_t (*dfree_data)(), time_t dtime,
168*0Sstevel@tonic-gate boolean_t lck)
169*0Sstevel@tonic-gate {
170*0Sstevel@tonic-gate hash_tbl *hashtblptr;
171*0Sstevel@tonic-gate unsigned totalsize;
172*0Sstevel@tonic-gate unsigned i;
173*0Sstevel@tonic-gate
174*0Sstevel@tonic-gate tablesize = hashi_Hsize(tablesize);
175*0Sstevel@tonic-gate
176*0Sstevel@tonic-gate totalsize = sizeof (hash_tbl) + (sizeof (hash_bucket) *
177*0Sstevel@tonic-gate (tablesize - 1));
178*0Sstevel@tonic-gate
179*0Sstevel@tonic-gate hashtblptr = (hash_tbl *)smalloc(totalsize);
180*0Sstevel@tonic-gate
181*0Sstevel@tonic-gate hashtblptr->size = tablesize; /* Success! */
182*0Sstevel@tonic-gate hashtblptr->bucketnum = 0;
183*0Sstevel@tonic-gate hashtblptr->dfree_data = dfree_data;
184*0Sstevel@tonic-gate hashtblptr->dfree_lck = lck;
185*0Sstevel@tonic-gate hashtblptr->dfree_time = dtime;
186*0Sstevel@tonic-gate hashtblptr->table = &hashtblptr->data[0];
187*0Sstevel@tonic-gate for (i = 0; i < tablesize; i++) {
188*0Sstevel@tonic-gate hashtblptr->table[i].table = hashtblptr;
189*0Sstevel@tonic-gate if (lck == B_TRUE) {
190*0Sstevel@tonic-gate (void) rwlock_init(&(hashtblptr->table[i].rwlock),
191*0Sstevel@tonic-gate USYNC_THREAD, NULL);
192*0Sstevel@tonic-gate }
193*0Sstevel@tonic-gate }
194*0Sstevel@tonic-gate
195*0Sstevel@tonic-gate return (hashtblptr); /* NULL if failure */
196*0Sstevel@tonic-gate }
197*0Sstevel@tonic-gate
198*0Sstevel@tonic-gate /*
199*0Sstevel@tonic-gate * Generic hash function to calculate a hash code from the given string.
200*0Sstevel@tonic-gate *
201*0Sstevel@tonic-gate * For each byte of the string, this function left-shifts the value in an
202*0Sstevel@tonic-gate * accumulator and then adds the byte into the accumulator. The contents of
203*0Sstevel@tonic-gate * the accumulator is returned after the entire string has been processed.
204*0Sstevel@tonic-gate * It is assumed that this result will be used as the "hashcode" parameter in
205*0Sstevel@tonic-gate * calls to other functions in this package. These functions automatically
206*0Sstevel@tonic-gate * adjust the hashcode for the size of each hashtable.
207*0Sstevel@tonic-gate *
208*0Sstevel@tonic-gate * This algorithm probably works best when the hash table size is a prime
209*0Sstevel@tonic-gate * number.
210*0Sstevel@tonic-gate *
211*0Sstevel@tonic-gate * Hopefully, this function is better than the previous one which returned
212*0Sstevel@tonic-gate * the sum of the squares of all the bytes. I'm still open to other
213*0Sstevel@tonic-gate * suggestions for a default hash function. The programmer is more than
214*0Sstevel@tonic-gate * welcome to supply his/her own hash function as that is one of the design
215*0Sstevel@tonic-gate * features of this package.
216*0Sstevel@tonic-gate */
217*0Sstevel@tonic-gate static unsigned
hashi_HashFunction(unsigned char * string,unsigned len)218*0Sstevel@tonic-gate hashi_HashFunction(unsigned char *string, unsigned len)
219*0Sstevel@tonic-gate {
220*0Sstevel@tonic-gate unsigned accum;
221*0Sstevel@tonic-gate
222*0Sstevel@tonic-gate /*
223*0Sstevel@tonic-gate * Special case: allow hash_Delete() to iterate over buckets.
224*0Sstevel@tonic-gate */
225*0Sstevel@tonic-gate if (string == NULL)
226*0Sstevel@tonic-gate return (len);
227*0Sstevel@tonic-gate
228*0Sstevel@tonic-gate for (accum = 0; len != 0; len--) {
229*0Sstevel@tonic-gate accum <<= 1;
230*0Sstevel@tonic-gate accum += (unsigned)(*string++ & 0xFF);
231*0Sstevel@tonic-gate }
232*0Sstevel@tonic-gate return (accum);
233*0Sstevel@tonic-gate }
234*0Sstevel@tonic-gate
235*0Sstevel@tonic-gate /*
236*0Sstevel@tonic-gate * This routine re-initializes the hash table. It frees all the allocated
237*0Sstevel@tonic-gate * memory and resets all bucket pointers to NULL. For the macro hash
238*0Sstevel@tonic-gate * table, the table will be reused. Other tables (with bucket locks)
239*0Sstevel@tonic-gate * will be destroyed.
240*0Sstevel@tonic-gate */
241*0Sstevel@tonic-gate void
hash_Reset(hash_tbl * hashtable,boolean_t (* free_data)())242*0Sstevel@tonic-gate hash_Reset(hash_tbl *hashtable, boolean_t (*free_data)())
243*0Sstevel@tonic-gate {
244*0Sstevel@tonic-gate hash_bucket *bucketptr;
245*0Sstevel@tonic-gate unsigned i;
246*0Sstevel@tonic-gate
247*0Sstevel@tonic-gate bucketptr = &((hashtable->table)[0]);
248*0Sstevel@tonic-gate for (i = 0; i < hashtable->size; i++) {
249*0Sstevel@tonic-gate if (hashtable->dfree_lck == B_TRUE)
250*0Sstevel@tonic-gate (void) rw_wrlock(&bucketptr->rwlock);
251*0Sstevel@tonic-gate /*
252*0Sstevel@tonic-gate * Unequivocally free member, using the force parameter.
253*0Sstevel@tonic-gate */
254*0Sstevel@tonic-gate (void) hashi_FreeMember(&bucketptr->next, free_data, B_TRUE);
255*0Sstevel@tonic-gate bucketptr->next = NULL;
256*0Sstevel@tonic-gate if (hashtable->dfree_lck == B_TRUE) {
257*0Sstevel@tonic-gate (void) rw_unlock(&bucketptr->rwlock);
258*0Sstevel@tonic-gate (void) rwlock_destroy(&(bucketptr->rwlock));
259*0Sstevel@tonic-gate }
260*0Sstevel@tonic-gate bucketptr++;
261*0Sstevel@tonic-gate }
262*0Sstevel@tonic-gate hashtable->bucketnum = 0;
263*0Sstevel@tonic-gate }
264*0Sstevel@tonic-gate
265*0Sstevel@tonic-gate /*
266*0Sstevel@tonic-gate * Returns B_TRUE if at least one entry for the given key exists; B_FALSE
267*0Sstevel@tonic-gate * otherwise. Dynamically free expired data as searched.
268*0Sstevel@tonic-gate */
269*0Sstevel@tonic-gate static int
hashi_Exists(hash_bucket * bucketptr,int (* compare)(),hash_datum * key,boolean_t (* free_data)(),hash_member ** prev)270*0Sstevel@tonic-gate hashi_Exists(hash_bucket *bucketptr, int (*compare)(), hash_datum *key,
271*0Sstevel@tonic-gate boolean_t (*free_data)(), hash_member **prev)
272*0Sstevel@tonic-gate {
273*0Sstevel@tonic-gate hash_member *prevptr = (hash_member *)bucketptr;
274*0Sstevel@tonic-gate hash_member *memberptr = bucketptr->next;
275*0Sstevel@tonic-gate hash_tbl *hashtable = bucketptr->table;
276*0Sstevel@tonic-gate hash_member *next;
277*0Sstevel@tonic-gate boolean_t ret = B_FALSE;
278*0Sstevel@tonic-gate time_t now = time(NULL);
279*0Sstevel@tonic-gate
280*0Sstevel@tonic-gate while (memberptr != NULL) {
281*0Sstevel@tonic-gate /*
282*0Sstevel@tonic-gate * Dynamically free expired data.
283*0Sstevel@tonic-gate */
284*0Sstevel@tonic-gate if (free_data != NULL && hashtable->dfree_data != NULL &&
285*0Sstevel@tonic-gate memberptr->h_time < now) {
286*0Sstevel@tonic-gate next = memberptr->next;
287*0Sstevel@tonic-gate if ((memberptr = hashi_Dfree(memberptr, free_data)) ==
288*0Sstevel@tonic-gate NULL) {
289*0Sstevel@tonic-gate prevptr->next = memberptr = next;
290*0Sstevel@tonic-gate continue;
291*0Sstevel@tonic-gate }
292*0Sstevel@tonic-gate }
293*0Sstevel@tonic-gate
294*0Sstevel@tonic-gate /*
295*0Sstevel@tonic-gate * Entry exists, or we are randomly selecting any
296*0Sstevel@tonic-gate * element (compare function is NULL).
297*0Sstevel@tonic-gate */
298*0Sstevel@tonic-gate if (compare == NULL || (*compare)(key, memberptr->data)) {
299*0Sstevel@tonic-gate ret = B_TRUE;
300*0Sstevel@tonic-gate break;
301*0Sstevel@tonic-gate } else
302*0Sstevel@tonic-gate prevptr = memberptr;
303*0Sstevel@tonic-gate memberptr = memberptr->next;
304*0Sstevel@tonic-gate }
305*0Sstevel@tonic-gate
306*0Sstevel@tonic-gate if (prev != NULL)
307*0Sstevel@tonic-gate *prev = prevptr;
308*0Sstevel@tonic-gate return (ret);
309*0Sstevel@tonic-gate }
310*0Sstevel@tonic-gate
311*0Sstevel@tonic-gate /*
312*0Sstevel@tonic-gate * Returns number of Dynamically freed expired entries.
313*0Sstevel@tonic-gate */
314*0Sstevel@tonic-gate static int
hashi_Expire(hash_bucket * bucketptr,boolean_t (* free_data)())315*0Sstevel@tonic-gate hashi_Expire(hash_bucket *bucketptr, boolean_t (*free_data)())
316*0Sstevel@tonic-gate {
317*0Sstevel@tonic-gate hash_member *prevptr = (hash_member *)bucketptr;
318*0Sstevel@tonic-gate hash_member *memberptr = bucketptr->next;
319*0Sstevel@tonic-gate hash_tbl *hashtable = bucketptr->table;
320*0Sstevel@tonic-gate hash_member *next;
321*0Sstevel@tonic-gate int rcount = 0;
322*0Sstevel@tonic-gate time_t now = time(NULL);
323*0Sstevel@tonic-gate
324*0Sstevel@tonic-gate while (memberptr) {
325*0Sstevel@tonic-gate /*
326*0Sstevel@tonic-gate * Dynamically free expired data.
327*0Sstevel@tonic-gate */
328*0Sstevel@tonic-gate if (free_data != NULL && hashtable->dfree_data != NULL &&
329*0Sstevel@tonic-gate memberptr->h_time < now) {
330*0Sstevel@tonic-gate next = memberptr->next;
331*0Sstevel@tonic-gate if ((memberptr = hashi_Dfree(memberptr, free_data)) ==
332*0Sstevel@tonic-gate NULL) {
333*0Sstevel@tonic-gate rcount++;
334*0Sstevel@tonic-gate prevptr->next = memberptr = next;
335*0Sstevel@tonic-gate continue;
336*0Sstevel@tonic-gate }
337*0Sstevel@tonic-gate }
338*0Sstevel@tonic-gate prevptr = memberptr;
339*0Sstevel@tonic-gate memberptr = memberptr->next;
340*0Sstevel@tonic-gate }
341*0Sstevel@tonic-gate return (rcount);
342*0Sstevel@tonic-gate }
343*0Sstevel@tonic-gate
344*0Sstevel@tonic-gate /*
345*0Sstevel@tonic-gate * Insert the data item "element" into the hash table using "hashcode"
346*0Sstevel@tonic-gate * to determine the bucket number, and "compare" and "key" to determine
347*0Sstevel@tonic-gate * its uniqueness.
348*0Sstevel@tonic-gate *
349*0Sstevel@tonic-gate * If the insertion is successful the element is returned. If a matching entry
350*0Sstevel@tonic-gate * already exists in the given bucket of the hash table, then NULL is returned,
351*0Sstevel@tonic-gate * signifying that the entry is already in the table. This happens when some
352*0Sstevel@tonic-gate * other thread has already inserted the entry.
353*0Sstevel@tonic-gate */
354*0Sstevel@tonic-gate void *
hash_Insert(hash_tbl * hashtable,void * hashdata,unsigned hashlen,int (* compare)(),hash_datum * key,hash_datum * element)355*0Sstevel@tonic-gate hash_Insert(hash_tbl *hashtable, void *hashdata, unsigned hashlen,
356*0Sstevel@tonic-gate int (*compare)(), hash_datum *key, hash_datum *element)
357*0Sstevel@tonic-gate {
358*0Sstevel@tonic-gate hash_member *temp = NULL;
359*0Sstevel@tonic-gate hash_bucket *bucketptr;
360*0Sstevel@tonic-gate hash_member *prev = NULL;
361*0Sstevel@tonic-gate unsigned hashcode = hashi_HashFunction(hashdata, hashlen);
362*0Sstevel@tonic-gate
363*0Sstevel@tonic-gate bucketptr = &((hashtable->table)[hashcode % hashtable->size]);
364*0Sstevel@tonic-gate if (hashtable->dfree_lck)
365*0Sstevel@tonic-gate (void) rw_wrlock(&bucketptr->rwlock);
366*0Sstevel@tonic-gate
367*0Sstevel@tonic-gate if (hashi_Exists(bucketptr, compare, key, hashtable->dfree_data,
368*0Sstevel@tonic-gate &prev)) {
369*0Sstevel@tonic-gate /* Some other thread got there first, so just return */
370*0Sstevel@tonic-gate if (hashtable->dfree_lck)
371*0Sstevel@tonic-gate (void) rw_unlock(&bucketptr->rwlock);
372*0Sstevel@tonic-gate return (NULL);
373*0Sstevel@tonic-gate }
374*0Sstevel@tonic-gate
375*0Sstevel@tonic-gate temp = (hash_member *)smalloc(sizeof (hash_member));
376*0Sstevel@tonic-gate
377*0Sstevel@tonic-gate prev->next = temp;
378*0Sstevel@tonic-gate temp->data = element;
379*0Sstevel@tonic-gate temp->next = NULL;
380*0Sstevel@tonic-gate
381*0Sstevel@tonic-gate /*
382*0Sstevel@tonic-gate * Dynamic free initialization.
383*0Sstevel@tonic-gate */
384*0Sstevel@tonic-gate if (hashtable->dfree_data != NULL)
385*0Sstevel@tonic-gate hashi_Dinit(hashtable, temp);
386*0Sstevel@tonic-gate
387*0Sstevel@tonic-gate if (hashtable->dfree_lck)
388*0Sstevel@tonic-gate (void) rw_unlock(&bucketptr->rwlock);
389*0Sstevel@tonic-gate
390*0Sstevel@tonic-gate return ((void *)temp);
391*0Sstevel@tonic-gate }
392*0Sstevel@tonic-gate
393*0Sstevel@tonic-gate /*
394*0Sstevel@tonic-gate * Release the reference count on an item. Performance: if item is to be
395*0Sstevel@tonic-gate * deleted, mark for future dynamic free.
396*0Sstevel@tonic-gate */
397*0Sstevel@tonic-gate void
hash_Rele(void * hashp,boolean_t delete)398*0Sstevel@tonic-gate hash_Rele(void *hashp, boolean_t delete)
399*0Sstevel@tonic-gate {
400*0Sstevel@tonic-gate hash_member *memberptr = (hash_member *)hashp;
401*0Sstevel@tonic-gate
402*0Sstevel@tonic-gate (void) mutex_lock(&memberptr->h_mtx);
403*0Sstevel@tonic-gate memberptr->h_count--;
404*0Sstevel@tonic-gate assert(memberptr->h_count >= 0);
405*0Sstevel@tonic-gate if (delete == B_TRUE)
406*0Sstevel@tonic-gate memberptr->h_time = 0;
407*0Sstevel@tonic-gate (void) mutex_unlock(&memberptr->h_mtx);
408*0Sstevel@tonic-gate }
409*0Sstevel@tonic-gate
410*0Sstevel@tonic-gate /*
411*0Sstevel@tonic-gate * Report the reference count on an item.
412*0Sstevel@tonic-gate */
413*0Sstevel@tonic-gate int
hash_Refcount(void * hashp)414*0Sstevel@tonic-gate hash_Refcount(void *hashp)
415*0Sstevel@tonic-gate {
416*0Sstevel@tonic-gate hash_member *memberptr = (hash_member *)hashp;
417*0Sstevel@tonic-gate int ret;
418*0Sstevel@tonic-gate
419*0Sstevel@tonic-gate (void) mutex_lock(&memberptr->h_mtx);
420*0Sstevel@tonic-gate ret = memberptr->h_count;
421*0Sstevel@tonic-gate (void) mutex_unlock(&memberptr->h_mtx);
422*0Sstevel@tonic-gate return (ret);
423*0Sstevel@tonic-gate }
424*0Sstevel@tonic-gate
425*0Sstevel@tonic-gate /*
426*0Sstevel@tonic-gate * Report the dynamic free time on an item.
427*0Sstevel@tonic-gate */
428*0Sstevel@tonic-gate int
hash_Htime(void * hashp)429*0Sstevel@tonic-gate hash_Htime(void *hashp)
430*0Sstevel@tonic-gate {
431*0Sstevel@tonic-gate hash_member *memberptr = (hash_member *)hashp;
432*0Sstevel@tonic-gate int ret;
433*0Sstevel@tonic-gate
434*0Sstevel@tonic-gate (void) mutex_lock(&memberptr->h_mtx);
435*0Sstevel@tonic-gate ret = memberptr->h_time;
436*0Sstevel@tonic-gate (void) mutex_unlock(&memberptr->h_mtx);
437*0Sstevel@tonic-gate return (ret);
438*0Sstevel@tonic-gate }
439*0Sstevel@tonic-gate
440*0Sstevel@tonic-gate /*
441*0Sstevel@tonic-gate * Increase the dynamic free time on an item.
442*0Sstevel@tonic-gate */
443*0Sstevel@tonic-gate void
hash_Age(void * hashp)444*0Sstevel@tonic-gate hash_Age(void *hashp)
445*0Sstevel@tonic-gate {
446*0Sstevel@tonic-gate hash_member *memberptr = (hash_member *)hashp;
447*0Sstevel@tonic-gate
448*0Sstevel@tonic-gate (void) mutex_lock(&memberptr->h_mtx);
449*0Sstevel@tonic-gate memberptr->h_time++;
450*0Sstevel@tonic-gate (void) mutex_unlock(&memberptr->h_mtx);
451*0Sstevel@tonic-gate }
452*0Sstevel@tonic-gate
453*0Sstevel@tonic-gate /*
454*0Sstevel@tonic-gate * Set the dynamic free time on an item.
455*0Sstevel@tonic-gate */
456*0Sstevel@tonic-gate void
hash_Dtime(void * hashp,time_t tm)457*0Sstevel@tonic-gate hash_Dtime(void *hashp, time_t tm)
458*0Sstevel@tonic-gate {
459*0Sstevel@tonic-gate hash_member *memberptr = (hash_member *)hashp;
460*0Sstevel@tonic-gate
461*0Sstevel@tonic-gate (void) mutex_lock(&memberptr->h_mtx);
462*0Sstevel@tonic-gate memberptr->h_time = tm;
463*0Sstevel@tonic-gate (void) mutex_unlock(&memberptr->h_mtx);
464*0Sstevel@tonic-gate }
465*0Sstevel@tonic-gate
466*0Sstevel@tonic-gate /*
467*0Sstevel@tonic-gate * Delete a data item from the hash table using "hashcode"
468*0Sstevel@tonic-gate * to determine the bucket number, and "compare" and "key" to determine
469*0Sstevel@tonic-gate * its uniqueness.
470*0Sstevel@tonic-gate *
471*0Sstevel@tonic-gate * If the deletion is successful 0 is returned. If a matching entry
472*0Sstevel@tonic-gate * does not exist in the given bucket of the hash table, or some other error
473*0Sstevel@tonic-gate * occurs, -1 is returned and the insertion is not done.
474*0Sstevel@tonic-gate */
475*0Sstevel@tonic-gate boolean_t
hash_Delete(hash_tbl * hashtable,void * hashdata,unsigned hashlen,int (* compare)(),hash_datum * key,boolean_t (* free_data)())476*0Sstevel@tonic-gate hash_Delete(hash_tbl *hashtable, void *hashdata, unsigned hashlen,
477*0Sstevel@tonic-gate int (*compare)(), hash_datum *key, boolean_t (*free_data)())
478*0Sstevel@tonic-gate {
479*0Sstevel@tonic-gate hash_member *prev = NULL;
480*0Sstevel@tonic-gate hash_member *temp;
481*0Sstevel@tonic-gate hash_bucket *bucketptr;
482*0Sstevel@tonic-gate unsigned hashcode = hashi_HashFunction(hashdata, hashlen);
483*0Sstevel@tonic-gate
484*0Sstevel@tonic-gate bucketptr = &((hashtable->table)[hashcode % hashtable->size]);
485*0Sstevel@tonic-gate if (hashtable->dfree_lck == B_TRUE)
486*0Sstevel@tonic-gate (void) rw_wrlock(&bucketptr->rwlock);
487*0Sstevel@tonic-gate
488*0Sstevel@tonic-gate if (hashi_Exists(bucketptr, compare, key, free_data, &prev) ==
489*0Sstevel@tonic-gate B_FALSE || prev == NULL) {
490*0Sstevel@tonic-gate if (hashtable->dfree_lck == B_TRUE)
491*0Sstevel@tonic-gate (void) rw_unlock(&bucketptr->rwlock);
492*0Sstevel@tonic-gate return (B_FALSE); /* Entry does not exist */
493*0Sstevel@tonic-gate }
494*0Sstevel@tonic-gate
495*0Sstevel@tonic-gate temp = prev->next;
496*0Sstevel@tonic-gate if (temp) {
497*0Sstevel@tonic-gate prev->next = temp->next;
498*0Sstevel@tonic-gate temp->next = NULL;
499*0Sstevel@tonic-gate (void) hashi_FreeMember(&temp, free_data, B_TRUE);
500*0Sstevel@tonic-gate } else
501*0Sstevel@tonic-gate prev->next = NULL;
502*0Sstevel@tonic-gate if (hashtable->dfree_lck == B_TRUE)
503*0Sstevel@tonic-gate (void) rw_unlock(&bucketptr->rwlock);
504*0Sstevel@tonic-gate return (B_TRUE);
505*0Sstevel@tonic-gate }
506*0Sstevel@tonic-gate
507*0Sstevel@tonic-gate /*
508*0Sstevel@tonic-gate * Locate and return the data entry associated with the given key.
509*0Sstevel@tonic-gate *
510*0Sstevel@tonic-gate * If the data entry is found, a pointer to it is returned. Otherwise,
511*0Sstevel@tonic-gate * NULL is returned.
512*0Sstevel@tonic-gate */
513*0Sstevel@tonic-gate hash_datum *
hash_Lookup(hash_tbl * hashtable,void * hashdata,unsigned hashlen,int (* compare)(),hash_datum * key,boolean_t hold)514*0Sstevel@tonic-gate hash_Lookup(hash_tbl *hashtable, void *hashdata, unsigned hashlen,
515*0Sstevel@tonic-gate int (*compare)(), hash_datum *key, boolean_t hold)
516*0Sstevel@tonic-gate {
517*0Sstevel@tonic-gate hash_datum *ret = NULL;
518*0Sstevel@tonic-gate hash_bucket *bucketptr;
519*0Sstevel@tonic-gate hash_member *prev = NULL;
520*0Sstevel@tonic-gate unsigned hashcode = hashi_HashFunction(hashdata, hashlen);
521*0Sstevel@tonic-gate
522*0Sstevel@tonic-gate bucketptr = &((hashtable->table)[hashcode % hashtable->size]);
523*0Sstevel@tonic-gate if (hashtable->dfree_lck == B_TRUE)
524*0Sstevel@tonic-gate (void) rw_wrlock(&bucketptr->rwlock);
525*0Sstevel@tonic-gate
526*0Sstevel@tonic-gate if (hashi_Exists(bucketptr, compare, key, hashtable->dfree_data,
527*0Sstevel@tonic-gate &prev) == B_TRUE) {
528*0Sstevel@tonic-gate /*
529*0Sstevel@tonic-gate * Dynamic free increment reference.
530*0Sstevel@tonic-gate */
531*0Sstevel@tonic-gate if (hold)
532*0Sstevel@tonic-gate hashi_Dhold(prev->next);
533*0Sstevel@tonic-gate ret = prev->next->data;
534*0Sstevel@tonic-gate
535*0Sstevel@tonic-gate }
536*0Sstevel@tonic-gate if (hashtable->dfree_lck == B_TRUE)
537*0Sstevel@tonic-gate (void) rw_unlock(&bucketptr->rwlock);
538*0Sstevel@tonic-gate return (ret);
539*0Sstevel@tonic-gate }
540*0Sstevel@tonic-gate
541*0Sstevel@tonic-gate /*
542*0Sstevel@tonic-gate * Reap expired data items, or a random data item from the hash table.
543*0Sstevel@tonic-gate */
544*0Sstevel@tonic-gate void
hash_Reap(hash_tbl * hashtable,boolean_t (* free_data)())545*0Sstevel@tonic-gate hash_Reap(hash_tbl *hashtable, boolean_t (*free_data)())
546*0Sstevel@tonic-gate {
547*0Sstevel@tonic-gate hash_bucket *bucketptr;
548*0Sstevel@tonic-gate int rcount;
549*0Sstevel@tonic-gate unsigned i;
550*0Sstevel@tonic-gate
551*0Sstevel@tonic-gate bucketptr = &((hashtable->table)[0]);
552*0Sstevel@tonic-gate rcount = 0;
553*0Sstevel@tonic-gate
554*0Sstevel@tonic-gate /*
555*0Sstevel@tonic-gate * Walk the buckets, reaping expired clients.
556*0Sstevel@tonic-gate */
557*0Sstevel@tonic-gate for (i = 0; i < hashtable->size; i++) {
558*0Sstevel@tonic-gate if (hashtable->dfree_lck == B_TRUE)
559*0Sstevel@tonic-gate (void) rw_wrlock(&bucketptr->rwlock);
560*0Sstevel@tonic-gate rcount += hashi_Expire(bucketptr, hashtable->dfree_data);
561*0Sstevel@tonic-gate if (hashtable->dfree_lck == B_TRUE)
562*0Sstevel@tonic-gate (void) rw_unlock(&bucketptr->rwlock);
563*0Sstevel@tonic-gate bucketptr++;
564*0Sstevel@tonic-gate }
565*0Sstevel@tonic-gate
566*0Sstevel@tonic-gate /*
567*0Sstevel@tonic-gate * Nothing to be reaped, delete a random element. Note that
568*0Sstevel@tonic-gate * the unhash_data routine will wait for current references
569*0Sstevel@tonic-gate * before deletion.
570*0Sstevel@tonic-gate */
571*0Sstevel@tonic-gate if (rcount == 0) {
572*0Sstevel@tonic-gate for (i = 0; i < hashtable->size; i++) {
573*0Sstevel@tonic-gate if (hash_Delete(hashtable, NULL, i, NULL, NULL,
574*0Sstevel@tonic-gate free_data) == B_TRUE) {
575*0Sstevel@tonic-gate break;
576*0Sstevel@tonic-gate }
577*0Sstevel@tonic-gate }
578*0Sstevel@tonic-gate }
579*0Sstevel@tonic-gate }
580