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