Home | History | Annotate | Download | only in smbsrv
      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 #ifndef _SMBSRV_HASH_TABLE_H
     27 #define	_SMBSRV_HASH_TABLE_H
     28 
     29 #pragma ident	"@(#)hash_table.h	1.1	07/10/25 SMI"
     30 
     31 /*
     32  *
     33  * Interface definition for the hash table library. The hash table is a
     34  * user-specified array of pointers to items. Hash collisions are handled
     35  * using linked lists from the table entries. A handle is associated with
     36  * each table, which is used to maintain the hash table.
     37  *
     38  * +------+     +-------+    +----+    +----+
     39  * |handle|---> |index 0|--->|item|--->|item|--->
     40  * | ...  |     +-------+    +----+    +----+
     41  * | ...  |     |index 1|--->
     42  * +------+     +-------+    +----+    +----+    +----+
     43  *              |index 2|--->|item|--->|item|--->|item|--->
     44  *              +-------+    +----+    +----+    +----+
     45  *              | ...   |--->
     46  *              +-------+
     47  *              | ...   |--->
     48  *              +-------+
     49  *              |index n|--->
     50  *              +-------+
     51  *
     52  */
     53 
     54 #include <sys/types.h>
     55 
     56 #ifdef __cplusplus
     57 extern "C" {
     58 #endif
     59 
     60 /*
     61  * This is the hash multiplier value.
     62  */
     63 #define	HASH_MESH_VALUE		77
     64 
     65 /*
     66  * Each entry (item) in the hash table has a linked-list pointer, a key,
     67  * a pointer to some user defined data (which may be null) and some flags.
     68  * The key is a user provided key and is used to position the item within
     69  * the table. The linked-list is used to store items whose hash values
     70  * collide. The data pointer is never dereferenced in the hash code so
     71  * it may be a null pointer.
     72  *
     73  * The item bit flags are:
     74  *
     75  * HTIF_DELETE:    Specifies that an item is marked for deletion (see
     76  *               ht_mark_delete and ht_clean_table).
     77  */
     78 #define	HTIF_MARKED_DELETED	0x01
     79 #define	HT_DELETE		HTIF_MARKED_DELETED
     80 
     81 typedef struct ht_item {
     82 	struct ht_item *hi_next;
     83 	char *hi_key;
     84 	void *hi_data;
     85 	size_t hi_flags;
     86 } HT_ITEM;
     87 
     88 /*
     89  * HT_TABLE_ENTRY is an opaque structure (to the public) used to maintain
     90  * a pointer to the hash table and the number of items in the table entry.
     91  * This number shows number of both available items and those are marked
     92  * as deleted.
     93  */
     94 typedef struct ht_table_entry {
     95 	HT_ITEM *he_head;
     96 	size_t he_count;
     97 } HT_TABLE_ENTRY;
     98 
     99 /*
    100  * The HT_HANDLE is an opaque handle that associates each request with
    101  * a hash table. A handle is generated when a hash table is created and
    102  * it is used to maintain all global data associated with the table.
    103  *
    104  * The handle bit flags are:
    105  *
    106  * HTHF_FIXED_KEY:    Specifies that keys are fixed length and should
    107  *                    not be assumed to be null terminated.
    108  */
    109 #define	HTHF_FIXED_KEY		0x01
    110 
    111 typedef struct ht_handle {
    112 	HT_TABLE_ENTRY *ht_table;
    113 	size_t ht_sequence;
    114 	size_t ht_table_size;
    115 	size_t ht_table_mask;
    116 	size_t ht_key_size;
    117 	size_t ht_total_items;	/* show total number of available items */
    118 	size_t ht_flags;
    119 	size_t (*ht_hash)(struct ht_handle *handle, const char *key);
    120 	void (*ht_callback)(HT_ITEM *item);
    121 	int (*ht_cmp)(const char *key1, const char *key2, size_t n);
    122 } HT_HANDLE;
    123 
    124 /*
    125  * Typedefs for the optional user-installable functions.
    126  */
    127 typedef void (*HT_CALLBACK)(HT_ITEM *item);
    128 
    129 /*
    130  * Compare function cast to make all compare
    131  * functions look like strncmp.
    132  */
    133 typedef	int (*HT_CMP)(const char *, const char *, size_t);
    134 
    135 /*
    136  * Iterator used with ht_findfirst and ht_findnext to walk through
    137  * all the items in a hash table. The iterator should be treated as
    138  * an opaque handle. The sequence number in the iterator is used
    139  * to maintain consistency with the table on which the iteration
    140  * is being performed. If the table sequence number changes, the
    141  * iterator becomes invalid.
    142  */
    143 typedef struct ht_iterator {
    144 	HT_HANDLE *hti_handle;
    145 	HT_ITEM *hti_item;
    146 	size_t hti_index;
    147 	size_t hti_sequence;
    148 } HT_ITERATOR;
    149 
    150 /*
    151  * Public API to create and destroy hash tables, to change the hash
    152  * function and to find out how many items are in a hash table.
    153  */
    154 extern HT_HANDLE *ht_create_table(size_t table_size, size_t key_size,
    155     size_t flags);
    156 extern void ht_destroy_table(HT_HANDLE *handle);
    157 extern void ht_set_cmpfn(HT_HANDLE *handle, HT_CMP cmpfn);
    158 extern size_t ht_get_total_items(HT_HANDLE *handle);
    159 
    160 /*
    161  * Public API to add, remove, replace or find specific items
    162  * in a hash table.
    163  */
    164 extern HT_ITEM *ht_add_item(HT_HANDLE *handle, const char *key,
    165     const void *data);
    166 extern HT_ITEM *ht_replace_item(HT_HANDLE *handle, const char *key,
    167     const void *data);
    168 extern void *ht_remove_item(HT_HANDLE *handle, const char *key);
    169 extern HT_ITEM *ht_find_item(HT_HANDLE *handle, const char *key);
    170 
    171 /*
    172  * Public API to iterate over a hash table. A mechanism is provided to
    173  * mark items for deletion while searching the table so that the table
    174  * is not modified during the search. When the search is complete, all
    175  * of the marked items can be deleted by calling ht_clean_table. If
    176  * the item data has been dynamically allocated, a callback can be
    177  * registered to free the memory. The callback will be invoked with a
    178  * pointer to each item as it is removed from the hash table.
    179  */
    180 extern HT_ITEM *ht_findfirst(HT_HANDLE *handle, HT_ITERATOR *iterator);
    181 extern HT_ITEM *ht_findnext(HT_ITERATOR *iterator);
    182 extern void ht_mark_delete(HT_HANDLE *handle, HT_ITEM *item);
    183 extern void ht_clear_delete(HT_HANDLE *handle, HT_ITEM *item);
    184 extern size_t ht_clean_table(HT_HANDLE *handle);
    185 extern HT_CALLBACK ht_register_callback(HT_HANDLE *handle,
    186     HT_CALLBACK callback);
    187 
    188 #ifdef __cplusplus
    189 }
    190 #endif
    191 
    192 #endif /* _SMBSRV_HASH_TABLE_H */
    193