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