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