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