1 .\" $OpenBSD: ohash_init.3,v 1.14 2007/05/31 19:19:30 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.
16 .\" $FreeBSD: src/usr.bin/m4/lib/ohash_init.3,v 1.3 2012/11/17 01:54:24 svnexp Exp $
18 .Dd $Mdocdate: May 31 2007 $
24 .Nm ohash_lookup_interval ,
25 .Nm ohash_lookup_memory ,
32 .Nd light-weight open hashing
34 .Fd #include <stdint.h>
35 .Fd #include <stddef.h>
36 .Fd #include <ohash.h>
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
74 holds the position of the key in each record, and two pointers to
78 functions, to use for managing the table internal storage.
81 frees storage internal to
83 Elements themselves should be freed by the user first, using for instance
88 .Fn ohash_lookup_interval
90 .Fn ohash_lookup_memory
91 are the basic look-up element functions.
92 The hashing function result is provided by the user as
103 This slot is only valid up to the next call to
108 .Fn ohash_lookup_interval
109 handles string-like keys.
110 .Fn ohash_lookup_interval
111 assumes the key is the interval between
116 though the actual elements stored in the table should only contain
119 .Fn ohash_lookup_memory
120 assumes the key is the memory area starting at
124 All bytes are significant in key comparison.
127 retrieves an element from a slot
134 if the slot is empty.
137 inserts a new element
143 must be empty and element
145 must have a key corresponding to the
150 removes the element at slot
152 It returns the removed element, for user code to dispose of, or
154 if the slot was empty.
159 can be used to access all elements in an ohash table, like this:
160 .Bd -literal -offset indent
161 for (n = ohash_first(h, &i); n != NULL; n = ohash_next(h, &i))
162 do_something_with(n);
166 points to an auxiliary unsigned integer used to record the current position
168 Those functions are safe to use even while entries are added to/removed
169 from the table, but in such a case they do not guarantee that new entries
171 As a special case, they can safely be used to free elements in the table.
174 returns the number of elements in the hash table.
182 may call the user-supplied memory functions.
183 It is the responsibility of the user memory allocation code to verify
184 that those calls did not fail.
186 If memory allocation fails,
188 returns a useless hash table.
192 still perform the requested operation, but the returned table should be
193 considered read-only.
194 It can still be accessed by
200 to dump relevant information to disk before aborting.
202 The open hashing functions are not thread-safe by design.
203 In particular, in a threaded environment, there is no guarantee that a
205 will not move between a
214 Multi-threaded applications should explicitly protect ohash table access.
219 .%B The Art of Computer Programming
225 Those functions are completely non-standard and should be avoided in
228 Those functions were designed and written for
231 by Marc Espie in 1999.