dmake: do not set MAKEFLAGS=k
[unleashed/tickless.git] / usr / src / lib / smbsrv / libsmb / common / smb_ht.c
blobd167931539cfe37153f5bff228eb111d4a1f3c90
1 /*
2 * CDDL HEADER START
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.
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.
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]
19 * CDDL HEADER END
22 * Copyright 2007 Sun Microsystems, Inc. All rights reserved.
23 * Use is subject to license terms.
26 #pragma ident "%Z%%M% %I% %E% SMI"
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.
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 * +-------+
50 #include <stdlib.h>
51 #include <strings.h>
52 #include <smbsrv/hash_table.h>
54 static size_t ht_default_hash(HT_HANDLE *handle, const char *key);
57 * ht_is_power2
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.
63 * Returns 1 if value given is power of two, otherwise returns 0.
65 static size_t
66 ht_is_power2(size_t value)
68 return (((value & (value - 1)) == 0)? 1 : 0);
73 * ht_create_table
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).
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.
85 * On success a pointer to an opaque handle is returned. Otherwise a
86 * null pointer is returned.
88 HT_HANDLE *
89 ht_create_table(size_t table_size, size_t key_size, size_t flags)
91 HT_HANDLE *ht;
92 size_t msize;
93 size_t i;
95 if ((table_size == 0) || (key_size == 0))
96 return (NULL);
98 if (ht_is_power2(table_size) == 0)
99 return (NULL);
101 msize = sizeof (HT_HANDLE) + (sizeof (HT_TABLE_ENTRY) * table_size);
103 if ((ht = (HT_HANDLE *)malloc(msize)) == 0)
104 return (NULL);
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;
119 for (i = 0; i < table_size; i++)
120 bzero(&ht->ht_table[i], sizeof (HT_TABLE_ENTRY));
122 return (ht);
127 * ht_destroy_table
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.
132 void
133 ht_destroy_table(HT_HANDLE *handle)
135 HT_ITEM *item;
136 HT_ITERATOR iterator;
138 if (handle == 0)
139 return;
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);
146 free(handle);
151 * ht_get_total_items
153 * Return the total number of items in the table. Returns -1 if the
154 * handle is invalid.
156 size_t
157 ht_get_total_items(HT_HANDLE *handle)
159 if (handle == 0)
160 return ((size_t)-1);
162 return (handle->ht_total_items);
167 * ht_default_hash
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.
174 * Returns the table index location for the item.
176 static size_t
177 ht_default_hash(HT_HANDLE *handle, const char *key)
179 unsigned int hash_ndx = 0;
180 size_t rval;
182 if ((handle->ht_flags & HTHF_FIXED_KEY) == 0) {
183 while (*key) {
184 hash_ndx += *key;
185 ++key;
187 } else {
188 int key_len = handle->ht_key_size;
190 while (key_len--) {
191 hash_ndx += *key;
192 ++key;
196 rval = (hash_ndx * HASH_MESH_VALUE) & handle->ht_table_mask;
197 return (rval);
202 * ht_set_cmpfn
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.
208 void
209 ht_set_cmpfn(HT_HANDLE *handle, HT_CMP cmpfn)
211 if (handle)
212 handle->ht_cmp = cmpfn;
216 * ht_add_item
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.
224 * The table sequence number may be modified here.
226 * If the item is successfully inserted, a pointer to the item object
227 * is returned. Otherwise a null pointer is returned.
229 HT_ITEM *
230 ht_add_item(HT_HANDLE *handle, const char *key, const void *data)
232 size_t h_index, key_len;
233 size_t msize;
234 HT_ITEM *item;
236 if (handle == 0 || key == 0)
237 return (NULL);
239 if (handle->ht_flags & HTHF_FIXED_KEY) {
240 key_len = handle->ht_key_size;
241 } else {
242 key_len = strlen(key);
244 if (key_len > handle->ht_key_size)
245 return (NULL);
247 /* Include the null terminator */
248 ++key_len;
251 msize = key_len + sizeof (HT_ITEM);
253 if ((item = malloc(msize)) == 0)
254 return (NULL);
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;
261 h_index = handle->ht_hash(handle, key);
264 * Add to the front of the list.
266 item->hi_next = handle->ht_table[h_index].he_head;
267 handle->ht_table[h_index].he_head = item;
269 handle->ht_table[h_index].he_count++;
270 handle->ht_total_items++;
271 handle->ht_sequence++;
273 return (item);
278 * ht_replace_item
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.
284 * The table sequence number may be modified here.
286 HT_ITEM *
287 ht_replace_item(HT_HANDLE *handle, const char *key, const void *data)
289 (void) ht_remove_item(handle, key);
291 return (ht_add_item(handle, key, data));
296 * ht_remove_item
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.
305 * The table sequence number may be modified here.
307 void *
308 ht_remove_item(HT_HANDLE *handle, const char *key)
310 size_t h_index;
311 HT_ITEM *cur, *prev;
312 int key_len;
313 void *data = 0;
315 if (handle == 0 || key == 0)
316 return (NULL);
318 if ((handle->ht_flags & HTHF_FIXED_KEY) == 0)
319 key_len = strlen(key) + 1;
320 else
321 key_len = handle->ht_key_size;
323 h_index = handle->ht_hash(handle, key);
325 cur = handle->ht_table[h_index].he_head;
326 prev = 0;
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;
338 if (handle->ht_callback)
339 handle->ht_callback(cur);
340 else
341 data = cur->hi_data;
344 * Since the key and the item were allocated as
345 * a single chunk, we only need one free here.
347 free(cur);
349 handle->ht_table[h_index].he_count--;
350 handle->ht_total_items--;
351 handle->ht_sequence++;
352 break;
355 prev = cur;
356 cur = cur->hi_next;
359 return (data);
363 * ht_find_item
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.
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.
371 HT_ITEM *
372 ht_find_item(HT_HANDLE *handle, const char *key)
374 size_t h_index;
375 HT_ITEM *cur;
376 int key_len;
378 if (handle == 0 || key == 0)
379 return (NULL);
381 if ((handle->ht_flags & HTHF_FIXED_KEY) == 0)
382 key_len = strlen(key) + 1;
383 else
384 key_len = handle->ht_key_size;
386 h_index = handle->ht_hash(handle, key);
387 cur = handle->ht_table[h_index].he_head;
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);
394 cur = cur->hi_next;
397 return (NULL);
402 * ht_register_callback
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.
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.
412 HT_CALLBACK
413 ht_register_callback(HT_HANDLE *handle, HT_CALLBACK callback)
415 HT_CALLBACK old_callback;
417 if (handle == 0)
418 return (NULL);
420 old_callback = handle->ht_callback;
421 handle->ht_callback = callback;
423 return (old_callback);
428 * ht_clean_table
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.
435 * The table sequence number may be modified here.
437 * Returns 0 if the handle is valid; otherwise returns -1.
439 size_t
440 ht_clean_table(HT_HANDLE *handle)
442 size_t i;
443 HT_ITEM *cur, *prev;
445 if (handle == 0)
446 return ((size_t)-1);
448 for (i = 0; i < handle->ht_table_size; i++) {
449 cur = handle->ht_table[i].he_head;
450 prev = 0;
452 while (cur) {
453 if (cur->hi_flags & HTIF_MARKED_DELETED) {
455 * We have a marked item: remove it.
457 if (prev == 0)
458 handle->ht_table[i].he_head =
459 cur->hi_next;
460 else
461 prev->hi_next = cur->hi_next;
463 if (handle->ht_callback)
464 handle->ht_callback(cur);
467 * Since the key and the item were allocated as
468 * a single chunk, we only need one free here.
470 free(cur);
472 handle->ht_table[i].he_count--;
473 handle->ht_sequence++;
475 if (prev == 0)
476 cur = handle->ht_table[i].he_head;
477 else
478 cur = prev->hi_next;
479 continue;
482 prev = cur;
483 cur = cur->hi_next;
487 return (0);
492 * ht_mark_delete
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.
498 void
499 ht_mark_delete(HT_HANDLE *handle, HT_ITEM *item)
501 if (handle && item) {
502 item->hi_flags |= HTIF_MARKED_DELETED;
503 handle->ht_total_items--;
508 * ht_clear_delete
510 * This function clear an item from marked for deletion list.
512 void
513 ht_clear_delete(HT_HANDLE *handle, HT_ITEM *item)
515 if (handle && item) {
516 item->hi_flags &= ~HTIF_MARKED_DELETED;
517 handle->ht_total_items++;
522 * ht_bucket_search
524 * Returns first item which is not marked as deleted
525 * in the specified bucket by 'head'
527 static HT_ITEM *
528 ht_bucket_search(HT_ITEM *head)
530 HT_ITEM *item = head;
531 while ((item != 0) && (item->hi_flags & HTIF_MARKED_DELETED))
532 item = item->hi_next;
534 return (item);
538 * ht_findfirst
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.
547 HT_ITEM *
548 ht_findfirst(HT_HANDLE *handle, HT_ITERATOR *iterator)
550 HT_ITEM *item;
551 size_t h_index;
553 if (handle == 0 || iterator == 0 || handle->ht_total_items == 0)
554 return (NULL);
556 (void) memset(iterator, 0, sizeof (HT_ITERATOR));
557 iterator->hti_handle = handle;
558 iterator->hti_sequence = handle->ht_sequence;
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);
569 return (NULL);
573 * ht_findnext
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:
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
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.
587 HT_ITEM *
588 ht_findnext(HT_ITERATOR *iterator)
590 HT_HANDLE *handle;
591 HT_ITEM *item;
592 size_t total;
593 size_t index;
595 if (iterator == 0 || iterator->hti_handle == 0 ||
596 iterator->hti_sequence == 0) {
597 /* Invalid iterator */
598 return (NULL);
601 handle = iterator->hti_handle;
603 if (iterator->hti_item == 0 ||
604 iterator->hti_sequence != handle->ht_sequence) {
606 * No more items or the table has changed
607 * since the last call.
609 return (NULL);
613 * Check for another item in the current bucket.
615 item = ht_bucket_search(iterator->hti_item->hi_next);
616 if (item != 0) {
617 iterator->hti_item = item;
618 return (item);
622 * Nothing else in the current bucket. Look for another
623 * bucket with something in it and return the head item.
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);
635 iterator->hti_index = 0;
636 iterator->hti_item = 0;
637 iterator->hti_sequence = 0;
638 return (NULL);