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> 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: May 31 2007 $ 17.Dt OPEN_HASH 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.Fd #include <stdint.h> 33.Fd #include <stddef.h> 34.Fd #include <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 72holds the position of the key in each record, and two pointers to 73.Xr calloc 3 74and 75.Xr free 3 Ns -like 76functions, to use for managing the table internal storage. 77.Pp 78.Fn ohash_delete 79frees storage internal to 80.Fa h . 81Elements themselves should be freed by the user first, using for instance 82.Fn ohash_first 83and 84.Fn ohash_next . 85.Pp 86.Fn ohash_lookup_interval 87and 88.Fn ohash_lookup_memory 89are the basic look-up element functions. 90The hashing function result is provided by the user as 91.Fa hv . 92These return a 93.Qq slot 94in the ohash table 95.Fa h , 96to be used with 97.Fn ohash_find , 98.Fn ohash_insert , 99or 100.Fn ohash_remove . 101This slot is only valid up to the next call to 102.Fn ohash_insert 103or 104.Fn ohash_remove . 105.Pp 106.Fn ohash_lookup_interval 107handles string-like keys. 108.Fn ohash_lookup_interval 109assumes the key is the interval between 110.Fa start 111and 112.Fa end , 113exclusive, 114though the actual elements stored in the table should only contain 115NUL-terminated keys. 116.Pp 117.Fn ohash_lookup_memory 118assumes the key is the memory area starting at 119.Fa k 120of size 121.Fa s . 122All bytes are significant in key comparison. 123.Pp 124.Fn ohash_find 125retrieves an element from a slot 126.Fa i 127returned by the 128.Fn ohash_lookup* 129functions. 130It returns 131.Dv NULL 132if the slot is empty. 133.Pp 134.Fn ohash_insert 135inserts a new element 136.Fa p 137at slot 138.Fa i . 139Slot 140.Fa i 141must be empty and element 142.Fa p 143must have a key corresponding to the 144.Fn ohash_lookup* 145call. 146.Pp 147.Fn ohash_remove 148removes the element at slot 149.Fa i . 150It returns the removed element, for user code to dispose of, or 151.Dv NULL 152if the slot was empty. 153.Pp 154.Fn ohash_first 155and 156.Fn ohash_next 157can be used to access all elements in an ohash table, like this: 158.Bd -literal -offset indent 159for (n = ohash_first(h, &i); n != NULL; n = ohash_next(h, &i)) 160 do_something_with(n); 161.Ed 162.Pp 163.Fa i 164points to an auxiliary unsigned integer used to record the current position 165in the ohash table. 166Those functions are safe to use even while entries are added to/removed 167from the table, but in such a case they don't guarantee that new entries 168will be returned. 169As a special case, they can safely be used to free elements in the table. 170.Pp 171.Fn ohash_entries 172returns the number of elements in the hash table. 173.Sh STORAGE HANDLING 174Only 175.Fn ohash_init , 176.Fn ohash_insert , 177.Fn ohash_remove 178and 179.Fn ohash_delete 180may call the user-supplied memory functions. 181It is the responsibility of the user memory allocation code to verify 182that those calls did not fail. 183.Pp 184If memory allocation fails, 185.Fn ohash_init 186returns a useless hash table. 187.Fn ohash_insert 188and 189.Fn ohash_remove 190still perform the requested operation, but the returned table should be 191considered read-only. 192It can still be accessed by 193.Fn ohash_lookup* , 194.Fn ohash_find , 195.Fn ohash_first 196and 197.Fn ohash_next 198to dump relevant information to disk before aborting. 199.Sh THREAD SAFETY 200The open hashing functions are not thread-safe by design. 201In particular, in a threaded environment, there is no guarantee that a 202.Qq slot 203will not move between a 204.Fn ohash_lookup* 205and a 206.Fn ohash_find , 207.Fn ohash_insert 208or 209.Fn ohash_remove 210call. 211.Pp 212Multi-threaded applications should explicitly protect ohash table access. 213.Sh SEE ALSO 214.Xr ohash_interval 3 215.Rs 216.%A Donald E. Knuth 217.%B The Art of Computer Programming 218.%V Vol. 3 219.%P pp 506-550 220.%D 1973 221.Re 222.Sh STANDARDS 223Those functions are completely non-standard and should be avoided in 224portable programs. 225.Sh HISTORY 226Those functions were designed and written for 227.Ox 228.Xr make 1 229by Marc Espie in 1999. 230