1 .\" $OpenBSD: ohash_init.3,v 1.2 2014/05/13 14:01:41 jmc Exp $
2 .\" Copyright (c) 1999 Marc Espie <espie@openbsd.org>
4 .\" Permission to use, copy, modify, and distribute this software for any
5 .\" purpose with or without fee is hereby granted, provided that the above
6 .\" copyright notice and this permission notice appear in all copies.
8 .\" THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
9 .\" WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10 .\" MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
11 .\" ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12 .\" WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
13 .\" ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
14 .\" OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
24 .Nm ohash_lookup_interval ,
25 .Nm ohash_lookup_memory ,
32 .Nd light-weight open hashing
38 .Fn ohash_init "struct ohash *h" "unsigned int size" "struct ohash_info *info"
40 .Fn ohash_delete "struct ohash *h"
42 .Fn ohash_lookup_interval "struct ohash *h" "const char *start" "const char *end" "uint32_t hv"
44 .Fn ohash_lookup_memory "struct ohash *h" "const char *k" "size_t s" "uint32_t hv"
46 .Fn ohash_find "struct ohash *h" "unsigned int i"
48 .Fn ohash_remove "struct ohash *h" "unsigned int i"
50 .Fn ohash_insert "struct ohash *h" "unsigned int i" "void *p"
52 .Fn ohash_first "struct ohash *h" "unsigned int *i"
54 .Fn ohash_next "struct ohash *h" "unsigned int *i"
56 .Fn ohash_entries "struct ohash *h"
58 These functions have been designed as a fast, extensible alternative to
59 the usual hash table functions.
60 They provide storage and retrieval of records indexed by keys,
61 where a key is a contiguous sequence of bytes at a fixed position in
63 Keys can either be NUL-terminated strings or fixed-size memory areas.
64 All functions take a pointer to an ohash structure as the
67 Storage for this structure should be provided by user code.
70 initializes the table to store roughly 2 to the power
75 .Fa struct ohash_info .
76 .Bd -literal -offset indent
79 void *data; /* user data */
80 void *(*calloc)(size_t, size_t, void *);
81 void (*free)(void *, void *);
82 void *(*alloc)(size_t, void *);
88 field holds the position of the key in each record;
93 fields are pointers to
97 functions, used for managing the table internal storage;
100 field is only used by the utility function
101 .Xr ohash_create_entry 3 .
103 Each of these functions are called similarly to their standard counterpart,
106 parameter corresponding to the content of the field
108 which can be used to communicate specific information to the functions.
111 stores a copy of those fields internally, so
113 can be reclaimed after initialization.
116 frees storage internal to
118 Elements themselves should be freed by the user first, using for instance
123 .Fn ohash_lookup_interval
125 .Fn ohash_lookup_memory
126 are the basic look-up element functions.
127 The hashing function result is provided by the user as
138 This slot is only valid up to the next call to
143 .Fn ohash_lookup_interval
144 handles string-like keys.
145 .Fn ohash_lookup_interval
146 assumes the key is the interval between
151 though the actual elements stored in the table should only contain
154 .Fn ohash_lookup_memory
155 assumes the key is the memory area starting at
159 All bytes are significant in key comparison.
162 retrieves an element from a slot
169 if the slot is empty.
172 inserts a new element
178 must be empty and element
180 must have a key corresponding to the
185 removes the element at slot
187 It returns the removed element, for user code to dispose of, or
189 if the slot was empty.
194 can be used to access all elements in an ohash table, like this:
195 .Bd -literal -offset indent
196 for (n = ohash_first(h, &i); n != NULL; n = ohash_next(h, &i))
197 do_something_with(n);
201 points to an auxiliary unsigned integer used to record the current position
203 Those functions are safe to use even while entries are added to/removed
204 from the table, but in such a case they don't guarantee that new entries
206 As a special case, they can safely be used to free elements in the table.
209 returns the number of elements in the hash table.
217 may call the user-supplied memory functions:
218 .Bd -literal -offset indent
219 p = (*info->calloc)(n, sizeof_record, info->data);
220 /* copy data from old to p */
221 (*info->free)(old, info->data);
224 It is the responsibility of the user memory allocation code to verify
225 that those calls did not fail.
227 If memory allocation fails,
229 returns a useless hash table.
233 still perform the requested operation, but the returned table should be
234 considered read-only.
235 It can still be accessed by
241 to dump relevant information to disk before aborting.
243 The open hashing functions are not thread-safe by design.
244 In particular, in a threaded environment, there is no guarantee that a
246 will not move between a
255 Multi-threaded applications should explicitly protect ohash table access.
261 .%B The Art of Computer Programming
267 Those functions are completely non-standard and should be avoided in
270 Those functions were designed and written for
273 by Marc Espie in 1999.