lib/libopenbsd/ohash_init.3

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