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	"%Z%%M%	%I%	%E% 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
57extern "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
81typedef 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 */
94typedef 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
111typedef 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 */
127typedef void (*HT_CALLBACK)(HT_ITEM *item);
128
129/*
130 * Compare function cast to make all compare
131 * functions look like strncmp.
132 */
133typedef	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 */
143typedef 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 */
154extern HT_HANDLE *ht_create_table(size_t table_size, size_t key_size,
155    size_t flags);
156extern void ht_destroy_table(HT_HANDLE *handle);
157extern void ht_set_cmpfn(HT_HANDLE *handle, HT_CMP cmpfn);
158extern 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 */
164extern HT_ITEM *ht_add_item(HT_HANDLE *handle, const char *key,
165    const void *data);
166extern HT_ITEM *ht_replace_item(HT_HANDLE *handle, const char *key,
167    const void *data);
168extern void *ht_remove_item(HT_HANDLE *handle, const char *key);
169extern 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 */
180extern HT_ITEM *ht_findfirst(HT_HANDLE *handle, HT_ITERATOR *iterator);
181extern HT_ITEM *ht_findnext(HT_ITERATOR *iterator);
182extern void ht_mark_delete(HT_HANDLE *handle, HT_ITEM *item);
183extern void ht_clear_delete(HT_HANDLE *handle, HT_ITEM *item);
184extern size_t ht_clean_table(HT_HANDLE *handle);
185extern 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