usr.bin/m4/lib/ohash_init.3

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