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]
22 * Copyright 2007 Sun Microsystems, Inc. All rights reserved.
23 * Use is subject to license terms.
26 #ifndef _SMBSRV_HASH_TABLE_H
27 #define _SMBSRV_HASH_TABLE_H
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.
36 * +------+ +-------+ +----+ +----+
37 * |handle|---> |index 0|--->|item|--->|item|--->
38 * | ... | +-------+ +----+ +----+
39 * | ... | |index 1|--->
40 * +------+ +-------+ +----+ +----+ +----+
41 * |index 2|--->|item|--->|item|--->|item|--->
42 * +-------+ +----+ +----+ +----+
52 #include <sys/types.h>
59 * This is the hash multiplier value.
61 #define HASH_MESH_VALUE 77
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.
71 * The item bit flags are:
73 * HTIF_DELETE: Specifies that an item is marked for deletion (see
74 * ht_mark_delete and ht_clean_table).
76 #define HTIF_MARKED_DELETED 0x01
77 #define HT_DELETE HTIF_MARKED_DELETED
79 typedef struct ht_item
{
80 struct ht_item
*hi_next
;
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
92 typedef struct ht_table_entry
{
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.
102 * The handle bit flags are:
104 * HTHF_FIXED_KEY: Specifies that keys are fixed length and should
105 * not be assumed to be null terminated.
107 #define HTHF_FIXED_KEY 0x01
109 typedef struct ht_handle
{
110 HT_TABLE_ENTRY
*ht_table
;
112 size_t ht_table_size
;
113 size_t ht_table_mask
;
115 size_t ht_total_items
; /* show total number of available items */
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
);
123 * Typedefs for the optional user-installable functions.
125 typedef void (*HT_CALLBACK
)(HT_ITEM
*item
);
128 * Compare function cast to make all compare
129 * functions look like strncmp.
131 typedef int (*HT_CMP
)(const char *, const char *, size_t);
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.
141 typedef struct ht_iterator
{
142 HT_HANDLE
*hti_handle
;
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.
152 extern HT_HANDLE
*ht_create_table(size_t table_size
, size_t key_size
,
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
);
159 * Public API to add, remove, replace or find specific items
162 extern HT_ITEM
*ht_add_item(HT_HANDLE
*handle
, const char *key
,
164 extern HT_ITEM
*ht_replace_item(HT_HANDLE
*handle
, const char *key
,
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
);
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.
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
);
190 #endif /* _SMBSRV_HASH_TABLE_H */