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 
54 static 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  */
65 static size_t
ht_is_power2(size_t value)66 ht_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  */
88 HT_HANDLE *
ht_create_table(size_t table_size,size_t key_size,size_t flags)89 ht_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  */
132 void
ht_destroy_table(HT_HANDLE * handle)133 ht_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  */
156 size_t
ht_get_total_items(HT_HANDLE * handle)157 ht_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  */
176 static size_t
ht_default_hash(HT_HANDLE * handle,const char * key)177 ht_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  */
208 void
ht_set_cmpfn(HT_HANDLE * handle,HT_CMP cmpfn)209 ht_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  */
229 HT_ITEM *
ht_add_item(HT_HANDLE * handle,const char * key,const void * data)230 ht_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  */
286 HT_ITEM *
ht_replace_item(HT_HANDLE * handle,const char * key,const void * data)287 ht_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  */
307 void *
ht_remove_item(HT_HANDLE * handle,const char * key)308 ht_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  */
371 HT_ITEM *
ht_find_item(HT_HANDLE * handle,const char * key)372 ht_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  */
412 HT_CALLBACK
ht_register_callback(HT_HANDLE * handle,HT_CALLBACK callback)413 ht_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  */
439 size_t
ht_clean_table(HT_HANDLE * handle)440 ht_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  */
498 void
ht_mark_delete(HT_HANDLE * handle,HT_ITEM * item)499 ht_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  */
512 void
ht_clear_delete(HT_HANDLE * handle,HT_ITEM * item)513 ht_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  */
527 static HT_ITEM *
ht_bucket_search(HT_ITEM * head)528 ht_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  */
547 HT_ITEM *
ht_findfirst(HT_HANDLE * handle,HT_ITERATOR * iterator)548 ht_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  */
587 HT_ITEM *
ht_findnext(HT_ITERATOR * iterator)588 ht_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