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