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