jcs.org
jcs's openbsd hax
openbsd
1.\" $OpenBSD: ohash_init.3,v 1.5 2025/06/13 18:34:00 schwarze Exp $
2.\" Copyright (c) 1999 Marc Espie <espie@openbsd.org>
3.\"
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.
7.\"
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.
15.\"
16.Dd $Mdocdate: June 13 2025 $
17.Dt OHASH_INIT 3
18.Os
19.Sh NAME
20.Nm ohash_init ,
21.Nm ohash_delete ,
22.Nm ohash_lookup_interval ,
23.Nm ohash_lookup_memory ,
24.Nm ohash_find ,
25.Nm ohash_remove ,
26.Nm ohash_insert ,
27.Nm ohash_first ,
28.Nm ohash_next ,
29.Nm ohash_entries
30.Nd light-weight open hashing
31.Sh SYNOPSIS
32.Lb libutil
33.In stdint.h
34.In stddef.h
35.In ohash.h
36.Ft void
37.Fn ohash_init "struct ohash *h" "unsigned int size" "struct ohash_info *info"
38.Ft void
39.Fn ohash_delete "struct ohash *h"
40.Ft unsigned int
41.Fn ohash_lookup_interval "struct ohash *h" "const char *start" "const char *end" "uint32_t hv"
42.Ft unsigned int
43.Fn ohash_lookup_memory "struct ohash *h" "const char *k" "size_t s" "uint32_t hv"
44.Ft void *
45.Fn ohash_find "struct ohash *h" "unsigned int i"
46.Ft void *
47.Fn ohash_remove "struct ohash *h" "unsigned int i"
48.Ft void *
49.Fn ohash_insert "struct ohash *h" "unsigned int i" "void *p"
50.Ft void *
51.Fn ohash_first "struct ohash *h" "unsigned int *i"
52.Ft void *
53.Fn ohash_next "struct ohash *h" "unsigned int *i"
54.Ft unsigned int
55.Fn ohash_entries "struct ohash *h"
56.Sh DESCRIPTION
57These functions have been designed as a fast, extensible alternative to
58the usual hash table functions.
59They provide storage and retrieval of records indexed by keys,
60where a key is a contiguous sequence of bytes at a fixed position in
61each record.
62Keys can either be NUL-terminated strings or fixed-size memory areas.
63All functions take a pointer to an ohash structure as the
64.Fa h
65function argument.
66Storage for this structure should be provided by user code.
67.Pp
68.Fn ohash_init
69initializes the table to store roughly 2 to the power
70.Fa size
71elements.
72.Fa info
73is a pointer to a
74.Fa struct ohash_info .
75.Bd -literal -offset indent
76struct ohash_info {
77 ptrdiff_t key_offset;
78 void *data; /* user data */
79 void *(*calloc)(size_t, size_t, void *);
80 void (*free)(void *, void *);
81 void *(*alloc)(size_t, void *);
82};
83.Ed
84.Pp
85The
86.Va offset
87field holds the position of the key in each record;
88the
89.Va calloc
90and
91.Va free
92fields are pointers to
93.Xr calloc 3
94and
95.Xr free 3 Ns -like
96functions, used for managing the table internal storage;
97the
98.Va alloc
99field is only used by the utility function
100.Xr ohash_create_entry 3 .
101.Pp
102Each of these functions are called similarly to their standard counterpart,
103but with an extra
104.Fa "void *"
105parameter corresponding to the content of the field
106.Fa data ,
107which can be used to communicate specific information to the functions.
108.Pp
109.Fn ohash_init
110stores a copy of those fields internally, so
111.Fa info
112can be reclaimed after initialization.
113.Pp
114.Fn ohash_delete
115frees storage internal to
116.Fa h .
117Elements themselves should be freed by the user first, using for instance
118.Fn ohash_first
119and
120.Fn ohash_next .
121.Pp
122.Fn ohash_lookup_interval
123and
124.Fn ohash_lookup_memory
125are the basic look-up element functions.
126The hashing function result is provided by the user as
127.Fa hv .
128These return a
129.Qq slot
130in the ohash table
131.Fa h ,
132to be used with
133.Fn ohash_find ,
134.Fn ohash_insert ,
135or
136.Fn ohash_remove .
137This slot is only valid up to the next call to
138.Fn ohash_insert
139or
140.Fn ohash_remove .
141.Pp
142.Fn ohash_lookup_interval
143handles string-like keys.
144.Fn ohash_lookup_interval
145assumes the key is the interval between
146.Fa start
147and
148.Fa end ,
149exclusive,
150though the actual elements stored in the table should only contain
151NUL-terminated keys.
152.Pp
153.Fn ohash_lookup_memory
154assumes the key is the memory area starting at
155.Fa k
156of size
157.Fa s .
158All bytes are significant in key comparison.
159.Pp
160.Fn ohash_find
161retrieves an element from a slot
162.Fa i
163returned by the
164.Fn ohash_lookup*
165functions.
166It returns
167.Dv NULL
168if the slot is empty.
169.Pp
170.Fn ohash_insert
171inserts a new element
172.Fa p
173at slot
174.Fa i .
175Slot
176.Fa i
177must be empty and element
178.Fa p
179must have a key corresponding to the
180.Fn ohash_lookup*
181call.
182.Pp
183.Fn ohash_remove
184removes the element at slot
185.Fa i .
186It returns the removed element, for user code to dispose of, or
187.Dv NULL
188if the slot was empty.
189.Pp
190.Fn ohash_first
191and
192.Fn ohash_next
193can be used to access all elements in an ohash table, like this:
194.Bd -literal -offset indent
195for (n = ohash_first(h, &i); n != NULL; n = ohash_next(h, &i))
196 do_something_with(n);
197.Ed
198.Pp
199.Fa i
200points to an auxiliary unsigned integer used to record the current position
201in the ohash table.
202Those functions are safe to use even while entries are added to/removed
203from the table, but in such a case they don't guarantee that new entries
204will be returned.
205As a special case, they can safely be used to free elements in the table.
206.Pp
207.Fn ohash_entries
208returns the number of elements in the hash table.
209.Sh STORAGE HANDLING
210Only
211.Fn ohash_init ,
212.Fn ohash_insert ,
213.Fn ohash_remove
214and
215.Fn ohash_delete
216may call the user-supplied memory functions:
217.Bd -literal -offset indent
218p = (*info->calloc)(n, sizeof_record, info->data);
219/* copy data from old to p */
220(*info->free)(old, info->data);
221.Ed
222.Pp
223It is the responsibility of the user memory allocation code to verify
224that those calls did not fail.
225.Pp
226If memory allocation fails,
227.Fn ohash_init
228returns a useless hash table.
229.Fn ohash_insert
230and
231.Fn ohash_remove
232still perform the requested operation, but the returned table should be
233considered read-only.
234It can still be accessed by
235.Fn ohash_lookup* ,
236.Fn ohash_find ,
237.Fn ohash_first
238and
239.Fn ohash_next
240to dump relevant information to disk before aborting.
241.Sh THREAD SAFETY
242The open hashing functions are not thread-safe by design.
243In particular, in a threaded environment, there is no guarantee that a
244.Qq slot
245will not move between a
246.Fn ohash_lookup*
247and a
248.Fn ohash_find ,
249.Fn ohash_insert
250or
251.Fn ohash_remove
252call.
253.Pp
254Multi-threaded applications should explicitly protect ohash table access.
255.Sh SEE ALSO
256.Xr hcreate 3 ,
257.Xr ohash_interval 3
258.Rs
259.%A Donald E. Knuth
260.%B The Art of Computer Programming
261.%V Vol. 3
262.%P pp. 506\(en550
263.%D 1973
264.Re
265.Sh STANDARDS
266Those functions are completely non-standard and should be avoided in
267portable programs.
268.Sh HISTORY
269Those functions were designed and written for
270.Ox
271.Xr make 1
272by Marc Espie in 1999.