aboutsummaryrefslogtreecommitdiff
path: root/orig/lib/ohash_init.3
blob: 683256312b9daee2a9030dc3ac664eb5f4844b68 (plain)
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
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
.\"	$OpenBSD: ohash_init.3,v 1.2 2014/05/13 14:01:41 jmc Exp $
.\" Copyright (c) 1999 Marc Espie <espie@openbsd.org>
.\"
.\" Permission to use, copy, modify, and distribute this software for any
.\" purpose with or without fee is hereby granted, provided that the above
.\" copyright notice and this permission notice appear in all copies.
.\"
.\" THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
.\" WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
.\" MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
.\" ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
.\" WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
.\" ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
.\" OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
.\"
.Dd $Mdocdate: May 13 2014 $
.Dt OHASH_INIT 3
.Os
.Sh NAME
.Nm ohash_init ,
.Nm ohash_delete ,
.Nm ohash_lookup_interval ,
.Nm ohash_lookup_memory ,
.Nm ohash_find ,
.Nm ohash_remove ,
.Nm ohash_insert ,
.Nm ohash_first ,
.Nm ohash_next ,
.Nm ohash_entries
.Nd light-weight open hashing
.Sh SYNOPSIS
.In stdint.h
.In stddef.h
.In ohash.h
.Ft void
.Fn ohash_init "struct ohash *h" "unsigned int size" "struct ohash_info *info"
.Ft void
.Fn ohash_delete "struct ohash *h"
.Ft "unsigned int"
.Fn ohash_lookup_interval "struct ohash *h" "const char *start" "const char *end" "uint32_t hv"
.Ft "unsigned int"
.Fn ohash_lookup_memory "struct ohash *h" "const char *k" "size_t s" "uint32_t hv"
.Ft void *
.Fn ohash_find "struct ohash *h" "unsigned int i"
.Ft void *
.Fn ohash_remove "struct ohash *h" "unsigned int i"
.Ft void *
.Fn ohash_insert "struct ohash *h" "unsigned int i" "void *p"
.Ft void *
.Fn ohash_first "struct ohash *h" "unsigned int *i"
.Ft void *
.Fn ohash_next "struct ohash *h" "unsigned int *i"
.Ft "unsigned int"
.Fn ohash_entries "struct ohash *h"
.Sh DESCRIPTION
These functions have been designed as a fast, extensible alternative to
the usual hash table functions.
They provide storage and retrieval of records indexed by keys,
where a key is a contiguous sequence of bytes at a fixed position in
each record.
Keys can either be NUL-terminated strings or fixed-size memory areas.
All functions take a pointer to an ohash structure as the
.Fa h
function argument.
Storage for this structure should be provided by user code.
.Pp
.Fn ohash_init
initializes the table to store roughly 2 to the power
.Fa size
elements.
.Fa info
is a pointer to a
.Fa struct ohash_info .
.Bd -literal -offset indent
struct ohash_info {
	ptrdiff_t key_offset;
	void *data;	/* user data */
	void *(*calloc)(size_t, size_t, void *);
	void (*free)(void *, void *);
	void *(*alloc)(size_t, void *);
};
.Ed
.Pp
The
.Va offset
field holds the position of the key in each record;
the
.Va calloc
and
.Va free
fields are pointers to
.Xr calloc 3
and
.Xr free 3 Ns -like
functions, used for managing the table internal storage;
the
.Va alloc
field is only used by the utility function
.Xr ohash_create_entry 3 .
.Pp
Each of these functions are called similarly to their standard counterpart,
but with an extra
.Ft void *
parameter corresponding to the content of the field
.Fa data ,
which can be used to communicate specific information to the functions.
.Pp
.Fn ohash_init
stores a copy of those fields internally, so
.Fa info
can be reclaimed after initialization.
.Pp
.Fn ohash_delete
frees storage internal to
.Fa h .
Elements themselves should be freed by the user first, using for instance
.Fn ohash_first
and
.Fn ohash_next .
.Pp
.Fn ohash_lookup_interval
and
.Fn ohash_lookup_memory
are the basic look-up element functions.
The hashing function result is provided by the user as
.Fa hv .
These return a
.Qq slot
in the ohash table
.Fa h ,
to be used with
.Fn ohash_find ,
.Fn ohash_insert ,
or
.Fn ohash_remove .
This slot is only valid up to the next call to
.Fn ohash_insert
or
.Fn ohash_remove .
.Pp
.Fn ohash_lookup_interval
handles string-like keys.
.Fn ohash_lookup_interval
assumes the key is the interval between
.Fa start
and
.Fa end ,
exclusive,
though the actual elements stored in the table should only contain
NUL-terminated keys.
.Pp
.Fn ohash_lookup_memory
assumes the key is the memory area starting at
.Fa k
of size
.Fa s .
All bytes are significant in key comparison.
.Pp
.Fn ohash_find
retrieves an element from a slot
.Fa i
returned by the
.Fn ohash_lookup*
functions.
It returns
.Dv NULL
if the slot is empty.
.Pp
.Fn ohash_insert
inserts a new element
.Fa p
at slot
.Fa i .
Slot
.Fa i
must be empty and element
.Fa p
must have a key corresponding to the
.Fn ohash_lookup*
call.
.Pp
.Fn ohash_remove
removes the element at slot
.Fa i .
It returns the removed element, for user code to dispose of, or
.Dv NULL
if the slot was empty.
.Pp
.Fn ohash_first
and
.Fn ohash_next
can be used to access all elements in an ohash table, like this:
.Bd -literal -offset indent
for (n = ohash_first(h, &i); n != NULL; n = ohash_next(h, &i))
	do_something_with(n);
.Ed
.Pp
.Fa i
points to an auxiliary unsigned integer used to record the current position
in the ohash table.
Those functions are safe to use even while entries are added to/removed
from the table, but in such a case they don't guarantee that new entries
will be returned.
As a special case, they can safely be used to free elements in the table.
.Pp
.Fn ohash_entries
returns the number of elements in the hash table.
.Sh STORAGE HANDLING
Only
.Fn ohash_init ,
.Fn ohash_insert ,
.Fn ohash_remove
and
.Fn ohash_delete
may call the user-supplied memory functions:
.Bd -literal -offset indent
p = (*info->calloc)(n, sizeof_record, info->data);
/* copy data from old to p */
(*info->free)(old, info->data);
.Ed
.Pp
It is the responsibility of the user memory allocation code to verify
that those calls did not fail.
.Pp
If memory allocation fails,
.Fn ohash_init
returns a useless hash table.
.Fn ohash_insert
and
.Fn ohash_remove
still perform the requested operation, but the returned table should be
considered read-only.
It can still be accessed by
.Fn ohash_lookup* ,
.Fn ohash_find ,
.Fn ohash_first
and
.Fn ohash_next
to dump relevant information to disk before aborting.
.Sh THREAD SAFETY
The open hashing functions are not thread-safe by design.
In particular, in a threaded environment, there is no guarantee that a
.Qq slot
will not move between a
.Fn ohash_lookup*
and a
.Fn ohash_find ,
.Fn ohash_insert
or
.Fn ohash_remove
call.
.Pp
Multi-threaded applications should explicitly protect ohash table access.
.Sh SEE ALSO
.Xr hcreate 3 ,
.Xr ohash_interval 3
.Rs
.%A Donald E. Knuth
.%B The Art of Computer Programming
.%V Vol. 3
.%P pp 506-550
.%D 1973
.Re
.Sh STANDARDS
Those functions are completely non-standard and should be avoided in
portable programs.
.Sh HISTORY
Those functions were designed and written for
.Ox
.Xr make 1
by Marc Espie in 1999.