1*da6c28aaSamw /*
2*da6c28aaSamw  * CDDL HEADER START
3*da6c28aaSamw  *
4*da6c28aaSamw  * The contents of this file are subject to the terms of the
5*da6c28aaSamw  * Common Development and Distribution License (the "License").
6*da6c28aaSamw  * You may not use this file except in compliance with the License.
7*da6c28aaSamw  *
8*da6c28aaSamw  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9*da6c28aaSamw  * or http://www.opensolaris.org/os/licensing.
10*da6c28aaSamw  * See the License for the specific language governing permissions
11*da6c28aaSamw  * and limitations under the License.
12*da6c28aaSamw  *
13*da6c28aaSamw  * When distributing Covered Code, include this CDDL HEADER in each
14*da6c28aaSamw  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15*da6c28aaSamw  * If applicable, add the following below this CDDL HEADER, with the
16*da6c28aaSamw  * fields enclosed by brackets "[]" replaced with your own identifying
17*da6c28aaSamw  * information: Portions Copyright [yyyy] [name of copyright owner]
18*da6c28aaSamw  *
19*da6c28aaSamw  * CDDL HEADER END
20*da6c28aaSamw  */
21*da6c28aaSamw /*
22*da6c28aaSamw  * Copyright 2007 Sun Microsystems, Inc.  All rights reserved.
23*da6c28aaSamw  * Use is subject to license terms.
24*da6c28aaSamw  */
25*da6c28aaSamw 
26*da6c28aaSamw /*
27*da6c28aaSamw  * Generic hash table library. The hash table is an array of pointers
28*da6c28aaSamw  * to items. Hash collisions are handled using linked lists from the
29*da6c28aaSamw  * table entries. A handle is associated with each table, which is used
30*da6c28aaSamw  * to maintain the hash table.
31*da6c28aaSamw  *
32*da6c28aaSamw  * +------+     +-------+    +----+    +----+
33*da6c28aaSamw  * |handle|---> |index 0|--->|item|--->|item|--->
34*da6c28aaSamw  * | ...  |     +-------+    +----+    +----+
35*da6c28aaSamw  * | ...  |     |index 1|--->
36*da6c28aaSamw  * +------+     +-------+    +----+    +----+    +----+
37*da6c28aaSamw  *              |index 2|--->|item|--->|item|--->|item|--->
38*da6c28aaSamw  *              +-------+    +----+    +----+    +----+
39*da6c28aaSamw  *              | ...   |--->
40*da6c28aaSamw  *              +-------+
41*da6c28aaSamw  *              | ...   |--->
42*da6c28aaSamw  *              +-------+
43*da6c28aaSamw  *              |index n|--->
44*da6c28aaSamw  *              +-------+
45*da6c28aaSamw  *
46*da6c28aaSamw  */
47*da6c28aaSamw 
48*da6c28aaSamw #include <stdlib.h>
49*da6c28aaSamw #include <strings.h>
50*da6c28aaSamw #include <smbsrv/hash_table.h>
51*da6c28aaSamw 
52*da6c28aaSamw static size_t ht_default_hash(HT_HANDLE *handle, const char *key);
53*da6c28aaSamw 
54*da6c28aaSamw /*
55*da6c28aaSamw  * ht_is_power2
56*da6c28aaSamw  *
57*da6c28aaSamw  * Inline function to determine if a value is a power of two. This
58*da6c28aaSamw  * function is used by the library to validate the table size when
59*da6c28aaSamw  * a new table is created.
60*da6c28aaSamw  *
61*da6c28aaSamw  * Returns 1 if value given is power of two, otherwise returns 0.
62*da6c28aaSamw  */
63*da6c28aaSamw static size_t
ht_is_power2(size_t value)64*da6c28aaSamw ht_is_power2(size_t value)
65*da6c28aaSamw {
66*da6c28aaSamw 	return (((value & (value - 1)) == 0)? 1 : 0);
67*da6c28aaSamw }
68*da6c28aaSamw 
69*da6c28aaSamw 
70*da6c28aaSamw /*
71*da6c28aaSamw  * ht_create_table
72*da6c28aaSamw  *
73*da6c28aaSamw  * Create a hash table. The table size must be a positive integer and
74*da6c28aaSamw  * must be a power of two. The key size must be a positive integer.
75*da6c28aaSamw  * For null terminated keys, the key size does not need to include the
76*da6c28aaSamw  * null terminating character. The type of key is indicated by the
77*da6c28aaSamw  * flags (see hash_table.h).
78*da6c28aaSamw  *
79*da6c28aaSamw  * The handle and the table are are malloc'd using a single call, to
80*da6c28aaSamw  * avoid two allocations. The table is located immediately after the
81*da6c28aaSamw  * handle.
82*da6c28aaSamw  *
83*da6c28aaSamw  * On success a pointer to an opaque handle is returned. Otherwise a
84*da6c28aaSamw  * null pointer is returned.
85*da6c28aaSamw  */
86*da6c28aaSamw HT_HANDLE *
ht_create_table(size_t table_size,size_t key_size,size_t flags)87*da6c28aaSamw ht_create_table(size_t table_size, size_t key_size, size_t flags)
88*da6c28aaSamw {
89*da6c28aaSamw 	HT_HANDLE *ht;
90*da6c28aaSamw 	size_t msize;
91*da6c28aaSamw 	size_t i;
92*da6c28aaSamw 
93*da6c28aaSamw 	if ((table_size == 0) || (key_size == 0))
94*da6c28aaSamw 		return (NULL);
95*da6c28aaSamw 
96*da6c28aaSamw 	if (ht_is_power2(table_size) == 0)
97*da6c28aaSamw 		return (NULL);
98*da6c28aaSamw 
99*da6c28aaSamw 	msize = sizeof (HT_HANDLE) + (sizeof (HT_TABLE_ENTRY) * table_size);
100*da6c28aaSamw 
101*da6c28aaSamw 	if ((ht = (HT_HANDLE *)malloc(msize)) == 0)
102*da6c28aaSamw 		return (NULL);
103*da6c28aaSamw 
104*da6c28aaSamw 	/*LINTED E_BAD_PTR_CAST_ALIGN*/
105*da6c28aaSamw 	ht->ht_table = (HT_TABLE_ENTRY *)((char *)ht + sizeof (HT_HANDLE));
106*da6c28aaSamw 	ht->ht_table_size = table_size;
107*da6c28aaSamw 	ht->ht_table_mask = table_size - 1;
108*da6c28aaSamw 	ht->ht_key_size = key_size;
109*da6c28aaSamw 	ht->ht_total_items = 0;
110*da6c28aaSamw 	ht->ht_flags = flags;
111*da6c28aaSamw 	ht->ht_hash = ht_default_hash;
112*da6c28aaSamw 	ht->ht_callback = 0;
113*da6c28aaSamw 	ht->ht_sequence = random();
114*da6c28aaSamw 	ht->ht_cmp = ((flags & HTHF_FIXED_KEY) == 0)
115*da6c28aaSamw 	    ? (HT_CMP)strncmp : (HT_CMP)memcmp;
116*da6c28aaSamw 
117*da6c28aaSamw 	for (i = 0; i < table_size; i++)
118*da6c28aaSamw 		bzero(&ht->ht_table[i], sizeof (HT_TABLE_ENTRY));
119*da6c28aaSamw 
120*da6c28aaSamw 	return (ht);
121*da6c28aaSamw }
122*da6c28aaSamw 
123*da6c28aaSamw 
124*da6c28aaSamw /*
125*da6c28aaSamw  * ht_destroy_table
126*da6c28aaSamw  *
127*da6c28aaSamw  * Destroy a hash table. All entries in the table are removed, which
128*da6c28aaSamw  * may invoke the callback if it's installed, and the memory is freed.
129*da6c28aaSamw  */
130*da6c28aaSamw void
ht_destroy_table(HT_HANDLE * handle)131*da6c28aaSamw ht_destroy_table(HT_HANDLE *handle)
132*da6c28aaSamw {
133*da6c28aaSamw 	HT_ITEM *item;
134*da6c28aaSamw 	HT_ITERATOR iterator;
135*da6c28aaSamw 
136*da6c28aaSamw 	if (handle == 0)
137*da6c28aaSamw 		return;
138*da6c28aaSamw 
139*da6c28aaSamw 	/* To remove marked entries */
140*da6c28aaSamw 	(void) ht_clean_table(handle);
141*da6c28aaSamw 	while ((item = ht_findfirst(handle, &iterator)) != 0)
142*da6c28aaSamw 		(void) ht_remove_item(handle, item->hi_key);
143*da6c28aaSamw 
144*da6c28aaSamw 	free(handle);
145*da6c28aaSamw }
146*da6c28aaSamw 
147*da6c28aaSamw 
148*da6c28aaSamw /*
149*da6c28aaSamw  * ht_get_total_items
150*da6c28aaSamw  *
151*da6c28aaSamw  * Return the total number of items in the table. Returns -1 if the
152*da6c28aaSamw  * handle is invalid.
153*da6c28aaSamw  */
154*da6c28aaSamw size_t
ht_get_total_items(HT_HANDLE * handle)155*da6c28aaSamw ht_get_total_items(HT_HANDLE *handle)
156*da6c28aaSamw {
157*da6c28aaSamw 	if (handle == 0)
158*da6c28aaSamw 		return ((size_t)-1);
159*da6c28aaSamw 
160*da6c28aaSamw 	return (handle->ht_total_items);
161*da6c28aaSamw }
162*da6c28aaSamw 
163*da6c28aaSamw 
164*da6c28aaSamw /*
165*da6c28aaSamw  * ht_default_hash
166*da6c28aaSamw  *
167*da6c28aaSamw  * Default hash function to compute the table index (hash value) based
168*da6c28aaSamw  * on the specified key. This will identify the location for the
169*da6c28aaSamw  * corresponding item in the hash table. The handle and key pointers
170*da6c28aaSamw  * should be validated before this function is called.
171*da6c28aaSamw  *
172*da6c28aaSamw  * Returns the table index location for the item.
173*da6c28aaSamw  */
174*da6c28aaSamw static size_t
ht_default_hash(HT_HANDLE * handle,const char * key)175*da6c28aaSamw ht_default_hash(HT_HANDLE *handle, const char *key)
176*da6c28aaSamw {
177*da6c28aaSamw 	unsigned int hash_ndx = 0;
178*da6c28aaSamw 	size_t rval;
179*da6c28aaSamw 
180*da6c28aaSamw 	if ((handle->ht_flags & HTHF_FIXED_KEY) == 0) {
181*da6c28aaSamw 		while (*key) {
182*da6c28aaSamw 			hash_ndx += *key;
183*da6c28aaSamw 			++key;
184*da6c28aaSamw 		}
185*da6c28aaSamw 	} else {
186*da6c28aaSamw 		int key_len = handle->ht_key_size;
187*da6c28aaSamw 
188*da6c28aaSamw 		while (key_len--) {
189*da6c28aaSamw 			hash_ndx += *key;
190*da6c28aaSamw 			++key;
191*da6c28aaSamw 		}
192*da6c28aaSamw 	}
193*da6c28aaSamw 
194*da6c28aaSamw 	rval = (hash_ndx * HASH_MESH_VALUE) & handle->ht_table_mask;
195*da6c28aaSamw 	return (rval);
196*da6c28aaSamw }
197*da6c28aaSamw 
198*da6c28aaSamw 
199*da6c28aaSamw /*
200*da6c28aaSamw  * ht_set_cmpfn
201*da6c28aaSamw  *
202*da6c28aaSamw  * Replace the current compare function. As the this is function
203*da6c28aaSamw  * for comparing items' key, it should not be called while there are
204*da6c28aaSamw  * items in the table.
205*da6c28aaSamw  */
206*da6c28aaSamw void
ht_set_cmpfn(HT_HANDLE * handle,HT_CMP cmpfn)207*da6c28aaSamw ht_set_cmpfn(HT_HANDLE *handle, HT_CMP cmpfn)
208*da6c28aaSamw {
209*da6c28aaSamw 	if (handle)
210*da6c28aaSamw 		handle->ht_cmp = cmpfn;
211*da6c28aaSamw }
212*da6c28aaSamw 
213*da6c28aaSamw /*
214*da6c28aaSamw  * ht_add_item
215*da6c28aaSamw  *
216*da6c28aaSamw  * Adds an item to a hash table. The hash table is identified by the
217*da6c28aaSamw  * handle and the key is used to generate a hashed index. The data
218*da6c28aaSamw  * item can be null; it is never dereferenced. We don't check for
219*da6c28aaSamw  * duplicates. If duplicate keys are added to the table, the last
220*da6c28aaSamw  * item added will be to the front of the duplicate list.
221*da6c28aaSamw  *
222*da6c28aaSamw  * The table sequence number may be modified here.
223*da6c28aaSamw  *
224*da6c28aaSamw  * If the item is successfully inserted, a pointer to the item object
225*da6c28aaSamw  * is returned. Otherwise a null pointer is returned.
226*da6c28aaSamw  */
227*da6c28aaSamw HT_ITEM *
ht_add_item(HT_HANDLE * handle,const char * key,const void * data)228*da6c28aaSamw ht_add_item(HT_HANDLE *handle, const char *key, const void *data)
229*da6c28aaSamw {
230*da6c28aaSamw 	size_t h_index, key_len;
231*da6c28aaSamw 	size_t msize;
232*da6c28aaSamw 	HT_ITEM *item;
233*da6c28aaSamw 
234*da6c28aaSamw 	if (handle == 0 || key == 0)
235*da6c28aaSamw 		return (NULL);
236*da6c28aaSamw 
237*da6c28aaSamw 	if (handle->ht_flags & HTHF_FIXED_KEY) {
238*da6c28aaSamw 		key_len = handle->ht_key_size;
239*da6c28aaSamw 	} else {
240*da6c28aaSamw 		key_len = strlen(key);
241*da6c28aaSamw 
242*da6c28aaSamw 		if (key_len > handle->ht_key_size)
243*da6c28aaSamw 			return (NULL);
244*da6c28aaSamw 
245*da6c28aaSamw 		/* Include the null terminator */
246*da6c28aaSamw 		++key_len;
247*da6c28aaSamw 	}
248*da6c28aaSamw 
249*da6c28aaSamw 	msize = key_len + sizeof (HT_ITEM);
250*da6c28aaSamw 
251*da6c28aaSamw 	if ((item = malloc(msize)) == 0)
252*da6c28aaSamw 		return (NULL);
253*da6c28aaSamw 
254*da6c28aaSamw 	item->hi_key = (char *)item + sizeof (HT_ITEM);
255*da6c28aaSamw 	(void) memcpy(item->hi_key, key, key_len);
256*da6c28aaSamw 	item->hi_data = (void *)data;
257*da6c28aaSamw 	item->hi_flags = 0;
258*da6c28aaSamw 
259*da6c28aaSamw 	h_index = handle->ht_hash(handle, key);
260*da6c28aaSamw 
261*da6c28aaSamw 	/*
262*da6c28aaSamw 	 * Add to the front of the list.
263*da6c28aaSamw 	 */
264*da6c28aaSamw 	item->hi_next = handle->ht_table[h_index].he_head;
265*da6c28aaSamw 	handle->ht_table[h_index].he_head = item;
266*da6c28aaSamw 
267*da6c28aaSamw 	handle->ht_table[h_index].he_count++;
268*da6c28aaSamw 	handle->ht_total_items++;
269*da6c28aaSamw 	handle->ht_sequence++;
270*da6c28aaSamw 
271*da6c28aaSamw 	return (item);
272*da6c28aaSamw }
273*da6c28aaSamw 
274*da6c28aaSamw 
275*da6c28aaSamw /*
276*da6c28aaSamw  * ht_replace_item
277*da6c28aaSamw  *
278*da6c28aaSamw  * Replace an item in a hash table. The item associated with key is removed
279*da6c28aaSamw  * using ht_remove_item and a new item is added using ht_add_item. We rely
280*da6c28aaSamw  * on parameter validation in ht_remove_item and ht_add_item.
281*da6c28aaSamw  *
282*da6c28aaSamw  * The table sequence number may be modified here.
283*da6c28aaSamw  */
284*da6c28aaSamw HT_ITEM *
ht_replace_item(HT_HANDLE * handle,const char * key,const void * data)285*da6c28aaSamw ht_replace_item(HT_HANDLE *handle, const char *key, const void *data)
286*da6c28aaSamw {
287*da6c28aaSamw 	(void) ht_remove_item(handle, key);
288*da6c28aaSamw 
289*da6c28aaSamw 	return (ht_add_item(handle, key, data));
290*da6c28aaSamw }
291*da6c28aaSamw 
292*da6c28aaSamw 
293*da6c28aaSamw /*
294*da6c28aaSamw  * ht_remove_item
295*da6c28aaSamw  *
296*da6c28aaSamw  * Remove an item from a hash table. If there are duplicate keys, then the
297*da6c28aaSamw  * first key found will be deleted. Note that the data pointer is never
298*da6c28aaSamw  * dereferenced.  If a callback is installed, it will be invoked and the
299*da6c28aaSamw  * return value will be null. Otherwise, the data pointer supplied by the
300*da6c28aaSamw  * application will be returned. If there is an error, a null pointer will
301*da6c28aaSamw  * be returned.
302*da6c28aaSamw  *
303*da6c28aaSamw  * The table sequence number may be modified here.
304*da6c28aaSamw  */
305*da6c28aaSamw void *
ht_remove_item(HT_HANDLE * handle,const char * key)306*da6c28aaSamw ht_remove_item(HT_HANDLE *handle, const char *key)
307*da6c28aaSamw {
308*da6c28aaSamw 	size_t h_index;
309*da6c28aaSamw 	HT_ITEM *cur, *prev;
310*da6c28aaSamw 	int key_len;
311*da6c28aaSamw 	void *data = 0;
312*da6c28aaSamw 
313*da6c28aaSamw 	if (handle == 0 || key == 0)
314*da6c28aaSamw 		return (NULL);
315*da6c28aaSamw 
316*da6c28aaSamw 	if ((handle->ht_flags & HTHF_FIXED_KEY) == 0)
317*da6c28aaSamw 		key_len = strlen(key) + 1;
318*da6c28aaSamw 	else
319*da6c28aaSamw 		key_len = handle->ht_key_size;
320*da6c28aaSamw 
321*da6c28aaSamw 	h_index = handle->ht_hash(handle, key);
322*da6c28aaSamw 
323*da6c28aaSamw 	cur = handle->ht_table[h_index].he_head;
324*da6c28aaSamw 	prev = 0;
325*da6c28aaSamw 
326*da6c28aaSamw 	while (cur) {
327*da6c28aaSamw 		if (!(cur->hi_flags & HTIF_MARKED_DELETED) &&
328*da6c28aaSamw 		    (handle->ht_cmp(cur->hi_key, key, key_len) == 0)) {
329*da6c28aaSamw 			/* found key */
330*da6c28aaSamw 			if (prev == 0)
331*da6c28aaSamw 				handle->ht_table[h_index].he_head =
332*da6c28aaSamw 				    cur->hi_next;
333*da6c28aaSamw 			else
334*da6c28aaSamw 				prev->hi_next = cur->hi_next;
335*da6c28aaSamw 
336*da6c28aaSamw 			if (handle->ht_callback)
337*da6c28aaSamw 				handle->ht_callback(cur);
338*da6c28aaSamw 			else
339*da6c28aaSamw 				data = cur->hi_data;
340*da6c28aaSamw 
341*da6c28aaSamw 			/*
342*da6c28aaSamw 			 * Since the key and the item were allocated as
343*da6c28aaSamw 			 * a single chunk, we only need one free here.
344*da6c28aaSamw 			 */
345*da6c28aaSamw 			free(cur);
346*da6c28aaSamw 
347*da6c28aaSamw 			handle->ht_table[h_index].he_count--;
348*da6c28aaSamw 			handle->ht_total_items--;
349*da6c28aaSamw 			handle->ht_sequence++;
350*da6c28aaSamw 			break;
351*da6c28aaSamw 		}
352*da6c28aaSamw 
353*da6c28aaSamw 		prev = cur;
354*da6c28aaSamw 		cur = cur->hi_next;
355*da6c28aaSamw 	}
356*da6c28aaSamw 
357*da6c28aaSamw 	return (data);
358*da6c28aaSamw }
359*da6c28aaSamw 
360*da6c28aaSamw /*
361*da6c28aaSamw  * ht_find_item
362*da6c28aaSamw  *
363*da6c28aaSamw  * Find an item in a hash table. If there are duplicate keys then the
364*da6c28aaSamw  * first item found (which will be the last one added) will be returned.
365*da6c28aaSamw  *
366*da6c28aaSamw  * Returns a pointer to an item. Otherwise returns a null pointer to
367*da6c28aaSamw  * indicate an error or that the key didn't match anything in the table.
368*da6c28aaSamw  */
369*da6c28aaSamw HT_ITEM *
ht_find_item(HT_HANDLE * handle,const char * key)370*da6c28aaSamw ht_find_item(HT_HANDLE *handle, const char *key)
371*da6c28aaSamw {
372*da6c28aaSamw 	size_t h_index;
373*da6c28aaSamw 	HT_ITEM *cur;
374*da6c28aaSamw 	int key_len;
375*da6c28aaSamw 
376*da6c28aaSamw 	if (handle == 0 || key == 0)
377*da6c28aaSamw 		return (NULL);
378*da6c28aaSamw 
379*da6c28aaSamw 	if ((handle->ht_flags & HTHF_FIXED_KEY) == 0)
380*da6c28aaSamw 		key_len = strlen(key) + 1;
381*da6c28aaSamw 	else
382*da6c28aaSamw 		key_len = handle->ht_key_size;
383*da6c28aaSamw 
384*da6c28aaSamw 	h_index = handle->ht_hash(handle, key);
385*da6c28aaSamw 	cur = handle->ht_table[h_index].he_head;
386*da6c28aaSamw 
387*da6c28aaSamw 	while (cur) {
388*da6c28aaSamw 		if (!(cur->hi_flags & HTIF_MARKED_DELETED) &&
389*da6c28aaSamw 		    (handle->ht_cmp(cur->hi_key, key, key_len) == 0))
390*da6c28aaSamw 			return (cur);
391*da6c28aaSamw 
392*da6c28aaSamw 		cur = cur->hi_next;
393*da6c28aaSamw 	}
394*da6c28aaSamw 
395*da6c28aaSamw 	return (NULL);
396*da6c28aaSamw }
397*da6c28aaSamw 
398*da6c28aaSamw 
399*da6c28aaSamw /*
400*da6c28aaSamw  * ht_register_callback
401*da6c28aaSamw  *
402*da6c28aaSamw  * Register an application callback function that can be used to process
403*da6c28aaSamw  * an item when it is removed from the table, i.e. free any memory
404*da6c28aaSamw  * allocated for that data item.
405*da6c28aaSamw  *
406*da6c28aaSamw  * The previous callback function pointer, which may be null, before
407*da6c28aaSamw  * registering the new one. This provides the caller with the option to
408*da6c28aaSamw  * restore a previous callback as required.
409*da6c28aaSamw  */
410*da6c28aaSamw HT_CALLBACK
ht_register_callback(HT_HANDLE * handle,HT_CALLBACK callback)411*da6c28aaSamw ht_register_callback(HT_HANDLE *handle, HT_CALLBACK callback)
412*da6c28aaSamw {
413*da6c28aaSamw 	HT_CALLBACK old_callback;
414*da6c28aaSamw 
415*da6c28aaSamw 	if (handle == 0)
416*da6c28aaSamw 		return (NULL);
417*da6c28aaSamw 
418*da6c28aaSamw 	old_callback = handle->ht_callback;
419*da6c28aaSamw 	handle->ht_callback = callback;
420*da6c28aaSamw 
421*da6c28aaSamw 	return (old_callback);
422*da6c28aaSamw }
423*da6c28aaSamw 
424*da6c28aaSamw 
425*da6c28aaSamw /*
426*da6c28aaSamw  * ht_clean_table
427*da6c28aaSamw  *
428*da6c28aaSamw  * This function removes all the items that are marked for deletion. Note
429*da6c28aaSamw  * that this will invoke the callback, if one has been installed. If this
430*da6c28aaSamw  * call is used, the callback mechanism is the only way for an application
431*da6c28aaSamw  * to free the item data if it was dynamically allocated.
432*da6c28aaSamw  *
433*da6c28aaSamw  * The table sequence number may be modified here.
434*da6c28aaSamw  *
435*da6c28aaSamw  * Returns 0 if the handle is valid; otherwise returns -1.
436*da6c28aaSamw  */
437*da6c28aaSamw size_t
ht_clean_table(HT_HANDLE * handle)438*da6c28aaSamw ht_clean_table(HT_HANDLE *handle)
439*da6c28aaSamw {
440*da6c28aaSamw 	size_t i;
441*da6c28aaSamw 	HT_ITEM *cur, *prev;
442*da6c28aaSamw 
443*da6c28aaSamw 	if (handle == 0)
444*da6c28aaSamw 		return ((size_t)-1);
445*da6c28aaSamw 
446*da6c28aaSamw 	for (i = 0; i < handle->ht_table_size; i++) {
447*da6c28aaSamw 		cur = handle->ht_table[i].he_head;
448*da6c28aaSamw 		prev = 0;
449*da6c28aaSamw 
450*da6c28aaSamw 		while (cur) {
451*da6c28aaSamw 			if (cur->hi_flags & HTIF_MARKED_DELETED) {
452*da6c28aaSamw 				/*
453*da6c28aaSamw 				 * We have a marked item: remove it.
454*da6c28aaSamw 				 */
455*da6c28aaSamw 				if (prev == 0)
456*da6c28aaSamw 					handle->ht_table[i].he_head =
457*da6c28aaSamw 					    cur->hi_next;
458*da6c28aaSamw 				else
459*da6c28aaSamw 					prev->hi_next = cur->hi_next;
460*da6c28aaSamw 
461*da6c28aaSamw 				if (handle->ht_callback)
462*da6c28aaSamw 					handle->ht_callback(cur);
463*da6c28aaSamw 
464*da6c28aaSamw 				/*
465*da6c28aaSamw 				 * Since the key and the item were allocated as
466*da6c28aaSamw 				 * a single chunk, we only need one free here.
467*da6c28aaSamw 				 */
468*da6c28aaSamw 				free(cur);
469*da6c28aaSamw 
470*da6c28aaSamw 				handle->ht_table[i].he_count--;
471*da6c28aaSamw 				handle->ht_sequence++;
472*da6c28aaSamw 
473*da6c28aaSamw 				if (prev == 0)
474*da6c28aaSamw 					cur = handle->ht_table[i].he_head;
475*da6c28aaSamw 				else
476*da6c28aaSamw 					cur = prev->hi_next;
477*da6c28aaSamw 				continue;
478*da6c28aaSamw 			}
479*da6c28aaSamw 
480*da6c28aaSamw 			prev = cur;
481*da6c28aaSamw 			cur = cur->hi_next;
482*da6c28aaSamw 		}
483*da6c28aaSamw 	}
484*da6c28aaSamw 
485*da6c28aaSamw 	return (0);
486*da6c28aaSamw }
487*da6c28aaSamw 
488*da6c28aaSamw 
489*da6c28aaSamw /*
490*da6c28aaSamw  * ht_mark_delete
491*da6c28aaSamw  *
492*da6c28aaSamw  * This function marks an item for deletion, which may be useful when
493*da6c28aaSamw  * using findfirst/findnext to avoid modifying the table during the
494*da6c28aaSamw  * table scan. Marked items can be removed later using ht_clean_table.
495*da6c28aaSamw  */
496*da6c28aaSamw void
ht_mark_delete(HT_HANDLE * handle,HT_ITEM * item)497*da6c28aaSamw ht_mark_delete(HT_HANDLE *handle, HT_ITEM *item)
498*da6c28aaSamw {
499*da6c28aaSamw 	if (handle && item) {
500*da6c28aaSamw 		item->hi_flags |= HTIF_MARKED_DELETED;
501*da6c28aaSamw 		handle->ht_total_items--;
502*da6c28aaSamw 	}
503*da6c28aaSamw }
504*da6c28aaSamw 
505*da6c28aaSamw /*
506*da6c28aaSamw  * ht_clear_delete
507*da6c28aaSamw  *
508*da6c28aaSamw  * This function clear an item from marked for deletion list.
509*da6c28aaSamw  */
510*da6c28aaSamw void
ht_clear_delete(HT_HANDLE * handle,HT_ITEM * item)511*da6c28aaSamw ht_clear_delete(HT_HANDLE *handle, HT_ITEM *item)
512*da6c28aaSamw {
513*da6c28aaSamw 	if (handle && item) {
514*da6c28aaSamw 		item->hi_flags &= ~HTIF_MARKED_DELETED;
515*da6c28aaSamw 		handle->ht_total_items++;
516*da6c28aaSamw 	}
517*da6c28aaSamw }
518*da6c28aaSamw 
519*da6c28aaSamw /*
520*da6c28aaSamw  * ht_bucket_search
521*da6c28aaSamw  *
522*da6c28aaSamw  * Returns first item which is not marked as deleted
523*da6c28aaSamw  * in the specified bucket by 'head'
524*da6c28aaSamw  */
525*da6c28aaSamw static HT_ITEM *
ht_bucket_search(HT_ITEM * head)526*da6c28aaSamw ht_bucket_search(HT_ITEM *head)
527*da6c28aaSamw {
528*da6c28aaSamw 	HT_ITEM *item = head;
529*da6c28aaSamw 	while ((item != 0) && (item->hi_flags & HTIF_MARKED_DELETED))
530*da6c28aaSamw 		item = item->hi_next;
531*da6c28aaSamw 
532*da6c28aaSamw 	return (item);
533*da6c28aaSamw }
534*da6c28aaSamw 
535*da6c28aaSamw /*
536*da6c28aaSamw  * ht_findfirst
537*da6c28aaSamw  *
538*da6c28aaSamw  * This function is used to begin an iteration through the hash table.
539*da6c28aaSamw  * The iterator is initialized and the first item in the table (as
540*da6c28aaSamw  * determined by the hash algorithm) is returned. The current sequence
541*da6c28aaSamw  * number is stored in the iterator to determine whether or not the
542*da6c28aaSamw  * the table has changed between calls. If the table is empty, a null
543*da6c28aaSamw  * pointer is returned.
544*da6c28aaSamw  */
545*da6c28aaSamw HT_ITEM *
ht_findfirst(HT_HANDLE * handle,HT_ITERATOR * iterator)546*da6c28aaSamw ht_findfirst(HT_HANDLE *handle, HT_ITERATOR *iterator)
547*da6c28aaSamw {
548*da6c28aaSamw 	HT_ITEM *item;
549*da6c28aaSamw 	size_t h_index;
550*da6c28aaSamw 
551*da6c28aaSamw 	if (handle == 0 || iterator == 0 || handle->ht_total_items == 0)
552*da6c28aaSamw 		return (NULL);
553*da6c28aaSamw 
554*da6c28aaSamw 	(void) memset(iterator, 0, sizeof (HT_ITERATOR));
555*da6c28aaSamw 	iterator->hti_handle = handle;
556*da6c28aaSamw 	iterator->hti_sequence = handle->ht_sequence;
557*da6c28aaSamw 
558*da6c28aaSamw 	for (h_index = 0; h_index < handle->ht_table_size; ++h_index) {
559*da6c28aaSamw 		item = ht_bucket_search(handle->ht_table[h_index].he_head);
560*da6c28aaSamw 		if (item != 0) {
561*da6c28aaSamw 			iterator->hti_index = h_index;
562*da6c28aaSamw 			iterator->hti_item = item;
563*da6c28aaSamw 			return (item);
564*da6c28aaSamw 		}
565*da6c28aaSamw 	}
566*da6c28aaSamw 
567*da6c28aaSamw 	return (NULL);
568*da6c28aaSamw }
569*da6c28aaSamw 
570*da6c28aaSamw /*
571*da6c28aaSamw  * ht_findnext
572*da6c28aaSamw  *
573*da6c28aaSamw  * Find the next item in the table for the given iterator. Iterators must
574*da6c28aaSamw  * be initialized by ht_findfirst, which will also return the first item
575*da6c28aaSamw  * in the table. If an item is available, a pointer to it is returned.
576*da6c28aaSamw  * Otherwise a null pointer is returned. A null pointer may indicate:
577*da6c28aaSamw  *
578*da6c28aaSamw  *	- an invalid iterator (i.e. ht_findfirst has not been called)
579*da6c28aaSamw  *	- the table has changed since the previous findfirst/findnext
580*da6c28aaSamw  *	- the entire table has been traversed
581*da6c28aaSamw  *
582*da6c28aaSamw  * The caller can use ht_get_total_items to determine whether or not all
583*da6c28aaSamw  * of the items in the table have been visited.
584*da6c28aaSamw  */
585*da6c28aaSamw HT_ITEM *
ht_findnext(HT_ITERATOR * iterator)586*da6c28aaSamw ht_findnext(HT_ITERATOR *iterator)
587*da6c28aaSamw {
588*da6c28aaSamw 	HT_HANDLE *handle;
589*da6c28aaSamw 	HT_ITEM *item;
590*da6c28aaSamw 	size_t total;
591*da6c28aaSamw 	size_t index;
592*da6c28aaSamw 
593*da6c28aaSamw 	if (iterator == 0 || iterator->hti_handle == 0 ||
594*da6c28aaSamw 	    iterator->hti_sequence == 0) {
595*da6c28aaSamw 		/* Invalid iterator */
596*da6c28aaSamw 		return (NULL);
597*da6c28aaSamw 	}
598*da6c28aaSamw 
599*da6c28aaSamw 	handle = iterator->hti_handle;
600*da6c28aaSamw 
601*da6c28aaSamw 	if (iterator->hti_item == 0 ||
602*da6c28aaSamw 	    iterator->hti_sequence != handle->ht_sequence) {
603*da6c28aaSamw 		/*
604*da6c28aaSamw 		 * No more items or the table has changed
605*da6c28aaSamw 		 * since the last call.
606*da6c28aaSamw 		 */
607*da6c28aaSamw 		return (NULL);
608*da6c28aaSamw 	}
609*da6c28aaSamw 
610*da6c28aaSamw 	/*
611*da6c28aaSamw 	 * Check for another item in the current bucket.
612*da6c28aaSamw 	 */
613*da6c28aaSamw 	item = ht_bucket_search(iterator->hti_item->hi_next);
614*da6c28aaSamw 	if (item != 0) {
615*da6c28aaSamw 		iterator->hti_item = item;
616*da6c28aaSamw 		return (item);
617*da6c28aaSamw 	}
618*da6c28aaSamw 
619*da6c28aaSamw 	/*
620*da6c28aaSamw 	 * Nothing else in the current bucket. Look for another
621*da6c28aaSamw 	 * bucket with something in it and return the head item.
622*da6c28aaSamw 	 */
623*da6c28aaSamw 	total = handle->ht_table_size;
624*da6c28aaSamw 	for (index = iterator->hti_index + 1; index < total; ++index) {
625*da6c28aaSamw 		item = ht_bucket_search(handle->ht_table[index].he_head);
626*da6c28aaSamw 		if (item != 0) {
627*da6c28aaSamw 			iterator->hti_index = index;
628*da6c28aaSamw 			iterator->hti_item = item;
629*da6c28aaSamw 			return (item);
630*da6c28aaSamw 		}
631*da6c28aaSamw 	}
632*da6c28aaSamw 
633*da6c28aaSamw 	iterator->hti_index = 0;
634*da6c28aaSamw 	iterator->hti_item = 0;
635*da6c28aaSamw 	iterator->hti_sequence = 0;
636*da6c28aaSamw 	return (NULL);
637*da6c28aaSamw }
638