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