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