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