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