2 \label{group__dbprim__hash}\index{Hash tables@{Hash tables}}
3 Operations for hash tables.
7 \#define {\bf HASH\_\-FLAG\_\-AUTOGROW}
8 \begin{CompactList}\small\item\em Flag permitting a hash table to automatically grow.\item\end{CompactList}\item
9 \#define {\bf HASH\_\-FLAG\_\-AUTOSHRINK}
10 \begin{CompactList}\small\item\em Flag permitting a hash table to automatically shrink.\item\end{CompactList}\item
11 \#define {\bf HASH\_\-TABLE\_\-INIT}(flags, func, comp, resize, extra)
12 \begin{CompactList}\small\item\em Hash table static initializer.\item\end{CompactList}\item
13 \#define {\bf ht\_\-verify}(table)
14 \begin{CompactList}\small\item\em Hash table verification macro.\item\end{CompactList}\item
15 \#define {\bf ht\_\-flags}(table)
16 \begin{CompactList}\small\item\em Hash table flags.\item\end{CompactList}\item
17 \#define {\bf ht\_\-frozen}(table)
18 \begin{CompactList}\small\item\em Determine if a hash table is frozen.\item\end{CompactList}\item
19 \#define {\bf ht\_\-modulus}(table)
20 \begin{CompactList}\small\item\em Hash table modulus.\item\end{CompactList}\item
21 \#define {\bf ht\_\-count}(table)
22 \begin{CompactList}\small\item\em Hash table count.\item\end{CompactList}\item
23 \#define {\bf ht\_\-func}(table)
24 \begin{CompactList}\small\item\em Hash table hash function.\item\end{CompactList}\item
25 \#define {\bf ht\_\-comp}(table)
26 \begin{CompactList}\small\item\em Hash table comparison function.\item\end{CompactList}\item
27 \#define {\bf ht\_\-rsize}(table)
28 \begin{CompactList}\small\item\em Hash table resize callback function.\item\end{CompactList}\item
29 \#define {\bf ht\_\-extra}(table)
30 \begin{CompactList}\small\item\em Extra pointer data in a hash table.\item\end{CompactList}\item
31 \#define {\bf ht\_\-size}(table)
32 \begin{CompactList}\small\item\em Hash table memory size.\item\end{CompactList}\item
33 \#define {\bf HASH\_\-ENTRY\_\-INIT}(value)
34 \begin{CompactList}\small\item\em Hash table entry static initializer.\item\end{CompactList}\item
35 \#define {\bf he\_\-verify}(entry)
36 \begin{CompactList}\small\item\em Hash table entry verification macro.\item\end{CompactList}\item
37 \#define {\bf he\_\-link}(entry)
38 \begin{CompactList}\small\item\em Hash table entry linked list element.\item\end{CompactList}\item
39 \#define {\bf he\_\-flags}(entry)
40 \begin{CompactList}\small\item\em Hash table entry flags.\item\end{CompactList}\item
41 \#define {\bf he\_\-table}(entry)
42 \begin{CompactList}\small\item\em Hash table entry table pointer.\item\end{CompactList}\item
43 \#define {\bf he\_\-hash}(entry)
44 \begin{CompactList}\small\item\em Hash table entry hash value.\item\end{CompactList}\item
45 \#define {\bf he\_\-key}(entry)
46 \begin{CompactList}\small\item\em Hash table entry key pointer.\item\end{CompactList}\item
47 \#define {\bf he\_\-value}(entry)
48 \begin{CompactList}\small\item\em Hash table entry value pointer.\item\end{CompactList}\item
49 \#define {\bf st\_\-rsize}(table)
50 \begin{CompactList}\small\item\em Sparse matrix table resize callback function.\item\end{CompactList}\end{CompactItemize}
51 \subsection*{Typedefs}
52 \begin{CompactItemize}
54 typedef struct \_\-hash\_\-table\_\-s {\bf hash\_\-table\_\-t}
55 \begin{CompactList}\small\item\em Hash table.\item\end{CompactList}\item
56 typedef struct \_\-hash\_\-entry\_\-s {\bf hash\_\-entry\_\-t}
57 \begin{CompactList}\small\item\em Hash table entry.\item\end{CompactList}\item
58 typedef unsigned long ($\ast$ {\bf hash\_\-iter\_\-t} )({\bf hash\_\-table\_\-t} $\ast$, {\bf hash\_\-entry\_\-t} $\ast$, void $\ast$)
59 \begin{CompactList}\small\item\em Hash table iteration callback.\item\end{CompactList}\item
60 typedef unsigned long ($\ast$ {\bf hash\_\-func\_\-t} )({\bf hash\_\-table\_\-t} $\ast$, {\bf db\_\-key\_\-t} $\ast$)
61 \begin{CompactList}\small\item\em Hash function callback.\item\end{CompactList}\item
62 typedef unsigned long ($\ast$ {\bf hash\_\-comp\_\-t} )({\bf hash\_\-table\_\-t} $\ast$, {\bf db\_\-key\_\-t} $\ast$, {\bf db\_\-key\_\-t} $\ast$)
63 \begin{CompactList}\small\item\em Hash table comparison callback.\item\end{CompactList}\item
64 typedef unsigned long ($\ast$ {\bf hash\_\-resize\_\-t} )({\bf hash\_\-table\_\-t} $\ast$, unsigned long)
65 \begin{CompactList}\small\item\em Hash table resize callback.\item\end{CompactList}\end{CompactItemize}
66 \subsection*{Functions}
67 \begin{CompactItemize}
69 unsigned long {\bf ht\_\-init} ({\bf hash\_\-table\_\-t} $\ast$table, unsigned long flags, {\bf hash\_\-func\_\-t} func, {\bf hash\_\-comp\_\-t} comp, {\bf hash\_\-resize\_\-t} resize, void $\ast$extra, unsigned long init\_\-mod)
70 \begin{CompactList}\small\item\em Dynamically initialize a hash table.\item\end{CompactList}\item
71 unsigned long {\bf ht\_\-add} ({\bf hash\_\-table\_\-t} $\ast$table, {\bf hash\_\-entry\_\-t} $\ast$entry, {\bf db\_\-key\_\-t} $\ast$key)
72 \begin{CompactList}\small\item\em Add an entry to a hash table.\item\end{CompactList}\item
73 unsigned long {\bf ht\_\-move} ({\bf hash\_\-table\_\-t} $\ast$table, {\bf hash\_\-entry\_\-t} $\ast$entry, {\bf db\_\-key\_\-t} $\ast$key)
74 \begin{CompactList}\small\item\em Move an entry in the hash table.\item\end{CompactList}\item
75 unsigned long {\bf ht\_\-remove} ({\bf hash\_\-table\_\-t} $\ast$table, {\bf hash\_\-entry\_\-t} $\ast$entry)
76 \begin{CompactList}\small\item\em Remove an element from a hash table.\item\end{CompactList}\item
77 unsigned long {\bf ht\_\-find} ({\bf hash\_\-table\_\-t} $\ast$table, {\bf hash\_\-entry\_\-t} $\ast$$\ast$entry\_\-p, {\bf db\_\-key\_\-t} $\ast$key)
78 \begin{CompactList}\small\item\em Find an entry in a hash table.\item\end{CompactList}\item
79 unsigned long {\bf ht\_\-iter} ({\bf hash\_\-table\_\-t} $\ast$table, {\bf hash\_\-iter\_\-t} iter\_\-func, void $\ast$extra)
80 \begin{CompactList}\small\item\em Iterate over each entry in a hash table.\item\end{CompactList}\item
81 unsigned long {\bf ht\_\-flush} ({\bf hash\_\-table\_\-t} $\ast$table, {\bf hash\_\-iter\_\-t} flush\_\-func, void $\ast$extra)
82 \begin{CompactList}\small\item\em Flush a hash table.\item\end{CompactList}\item
83 unsigned long {\bf ht\_\-resize} ({\bf hash\_\-table\_\-t} $\ast$table, unsigned long new\_\-size)
84 \begin{CompactList}\small\item\em Resize a hash table.\item\end{CompactList}\item
85 unsigned long {\bf ht\_\-free} ({\bf hash\_\-table\_\-t} $\ast$table)
86 \begin{CompactList}\small\item\em Free memory used by an empty hash table.\item\end{CompactList}\item
87 unsigned long {\bf he\_\-init} ({\bf hash\_\-entry\_\-t} $\ast$entry, void $\ast$value)
88 \begin{CompactList}\small\item\em Dynamically initialize a hash table entry.\item\end{CompactList}\end{CompactItemize}
91 \subsection{Detailed Description}
92 Hash tables are a basic data structure used in building databases. Hash tables provide a means of storing data such that an arbitrary entry may be looked up efficiently. This library implements a hash table that may optionally grow and shrink to provide maximum efficiency. The implementation is with two kinds of caller-allocated structures--a {\bf hash\_\-table\_\-t} {\rm (p.\,\pageref{group__dbprim__hash_a0})} structure that describes the table and a {\bf hash\_\-entry\_\-t} {\rm (p.\,\pageref{group__dbprim__hash_a1})} structure for each entry in the table. The library allocates a bucket array which must be released with the {\bf ht\_\-free}() {\rm (p.\,\pageref{group__dbprim__hash_a14})} function when the hash table has been emptied. Additionally, the hash table may be manually resized with the {\bf ht\_\-resize}() {\rm (p.\,\pageref{group__dbprim__hash_a13})} function.
94 Entries may be added to and removed from the table using the {\bf ht\_\-add}() {\rm (p.\,\pageref{group__dbprim__hash_a7})} and {\bf ht\_\-remove}() {\rm (p.\,\pageref{group__dbprim__hash_a9})} functions. Additionally, the key on a given entry may be changed using the {\bf ht\_\-move}() {\rm (p.\,\pageref{group__dbprim__hash_a8})} function. Of course, any given entry may be looked up using the {\bf ht\_\-find}() {\rm (p.\,\pageref{group__dbprim__hash_a10})} function, and {\bf ht\_\-iter}() {\rm (p.\,\pageref{group__dbprim__hash_a11})} will execute a user-defined function for each entry in the hash table (in an unspecified order). The {\bf ht\_\-flush}() {\rm (p.\,\pageref{group__dbprim__hash_a12})} function will remove all entries from the hash table, optionally executing a user-specified clean-up function.
96 \subsection{Define Documentation}
97 \index{dbprim_hash@{dbprim\_\-hash}!HASH_ENTRY_INIT@{HASH\_\-ENTRY\_\-INIT}}
98 \index{HASH_ENTRY_INIT@{HASH\_\-ENTRY\_\-INIT}!dbprim_hash@{dbprim\_\-hash}}
99 \subsubsection{\setlength{\rightskip}{0pt plus 5cm}\#define HASH\_\-ENTRY\_\-INIT(value)}\label{group__dbprim__hash_a29}
104 This macro statically initializes a {\bf hash\_\-entry\_\-t} {\rm (p.\,\pageref{group__dbprim__hash_a1})}.\begin{Desc}
105 \item[{\bf Parameters: }]\par
108 {\em value}]A pointer to {\tt void} representing the object associated with the entry. \end{description}
110 \index{dbprim_hash@{dbprim\_\-hash}!HASH_FLAG_AUTOGROW@{HASH\_\-FLAG\_\-AUTOGROW}}
111 \index{HASH_FLAG_AUTOGROW@{HASH\_\-FLAG\_\-AUTOGROW}!dbprim_hash@{dbprim\_\-hash}}
112 \subsubsection{\setlength{\rightskip}{0pt plus 5cm}\#define HASH\_\-FLAG\_\-AUTOGROW}\label{group__dbprim__hash_a16}
117 If passed in to {\bf HASH\_\-TABLE\_\-INIT}() {\rm (p.\,\pageref{group__dbprim__hash_a18})} or {\bf ht\_\-init}() {\rm (p.\,\pageref{group__dbprim__hash_a6})}, allows the hash table to grow automatically. \index{dbprim_hash@{dbprim\_\-hash}!HASH_FLAG_AUTOSHRINK@{HASH\_\-FLAG\_\-AUTOSHRINK}}
118 \index{HASH_FLAG_AUTOSHRINK@{HASH\_\-FLAG\_\-AUTOSHRINK}!dbprim_hash@{dbprim\_\-hash}}
119 \subsubsection{\setlength{\rightskip}{0pt plus 5cm}\#define HASH\_\-FLAG\_\-AUTOSHRINK}\label{group__dbprim__hash_a17}
124 If passed in to {\bf HASH\_\-TABLE\_\-INIT}() {\rm (p.\,\pageref{group__dbprim__hash_a18})} or {\bf ht\_\-init}() {\rm (p.\,\pageref{group__dbprim__hash_a6})}, allows the hash table to shrink automatically. \index{dbprim_hash@{dbprim\_\-hash}!HASH_TABLE_INIT@{HASH\_\-TABLE\_\-INIT}}
125 \index{HASH_TABLE_INIT@{HASH\_\-TABLE\_\-INIT}!dbprim_hash@{dbprim\_\-hash}}
126 \subsubsection{\setlength{\rightskip}{0pt plus 5cm}\#define HASH\_\-TABLE\_\-INIT(flags, func, comp, resize, extra)}\label{group__dbprim__hash_a18}
131 This macro statically initializes a {\bf hash\_\-table\_\-t} {\rm (p.\,\pageref{group__dbprim__hash_a0})}.\begin{Desc}
132 \item[{\bf Parameters: }]\par
135 {\em flags}]A bit-wise OR of {\bf HASH\_\-FLAG\_\-AUTOGROW} {\rm (p.\,\pageref{group__dbprim__hash_a16})} and {\bf HASH\_\-FLAG\_\-AUTOSHRINK} {\rm (p.\,\pageref{group__dbprim__hash_a17})}. If neither behavior is desired, use 0. \item[
136 {\em func}]A {\bf hash\_\-func\_\-t} {\rm (p.\,\pageref{group__dbprim__hash_a3})} function pointer for a hash function. \item[
137 {\em comp}]A {\bf hash\_\-comp\_\-t} {\rm (p.\,\pageref{group__dbprim__hash_a4})} function pointer for a comparison function. \item[
138 {\em resize}]A {\bf hash\_\-resize\_\-t} {\rm (p.\,\pageref{group__dbprim__hash_a5})} function pointer for determining whether resizing is permitted and/or for notification of the resize. \item[
139 {\em extra}]Extra pointer data that should be associated with the hash table. \end{description}
141 \index{dbprim_hash@{dbprim\_\-hash}!he_flags@{he\_\-flags}}
142 \index{he_flags@{he\_\-flags}!dbprim_hash@{dbprim\_\-hash}}
143 \subsubsection{\setlength{\rightskip}{0pt plus 5cm}\#define he\_\-flags(entry)}\label{group__dbprim__hash_a32}
148 This macro retrieves a set of user-defined flags associated with the entry. It may be used as an lvalue to set those flags.\begin{Desc}
149 \item[{\bf Parameters: }]\par
152 {\em entry}]A pointer to a {\bf hash\_\-entry\_\-t} {\rm (p.\,\pageref{group__dbprim__hash_a1})}.
157 \item[{\bf Returns: }]\par
158 An {\tt unsigned long} containing the flags associated with the entry. \end{Desc}
159 \index{dbprim_hash@{dbprim\_\-hash}!he_hash@{he\_\-hash}}
160 \index{he_hash@{he\_\-hash}!dbprim_hash@{dbprim\_\-hash}}
161 \subsubsection{\setlength{\rightskip}{0pt plus 5cm}\#define he\_\-hash(entry)}\label{group__dbprim__hash_a34}
166 This macro retrieves the hash value of the given hash entry. If the hash table has been resized, this value may not be the same as a previous value.\begin{Desc}
167 \item[{\bf Parameters: }]\par
170 {\em entry}]A pointer to a {\bf hash\_\-entry\_\-t} {\rm (p.\,\pageref{group__dbprim__hash_a1})}.
175 \item[{\bf Returns: }]\par
176 An {\tt unsigned long} containing the hash code for the entry. \end{Desc}
177 \index{dbprim_hash@{dbprim\_\-hash}!he_key@{he\_\-key}}
178 \index{he_key@{he\_\-key}!dbprim_hash@{dbprim\_\-hash}}
179 \subsubsection{\setlength{\rightskip}{0pt plus 5cm}\#define he\_\-key(entry)}\label{group__dbprim__hash_a35}
184 This macro retrieves the key associated with the hash table entry.\begin{Desc}
185 \item[{\bf Parameters: }]\par
188 {\em entry}]A pointer to a {\bf hash\_\-entry\_\-t} {\rm (p.\,\pageref{group__dbprim__hash_a1})}.
193 \item[{\bf Returns: }]\par
194 A pointer to a {\bf db\_\-key\_\-t} {\rm (p.\,\pageref{group__dbprim__key_a0})}. \end{Desc}
195 \index{dbprim_hash@{dbprim\_\-hash}!he_link@{he\_\-link}}
196 \index{he_link@{he\_\-link}!dbprim_hash@{dbprim\_\-hash}}
197 \subsubsection{\setlength{\rightskip}{0pt plus 5cm}\#define he\_\-link(entry)}\label{group__dbprim__hash_a31}
202 This macro provides access to the linked list element buried in the hash table entry. It should $\ast$not$\ast$ be used on entries currently in a hash table. The purpose of this macro is to allow an object containing a hash table entry to be placed upon a free list.\begin{Desc}
203 \item[{\bf Parameters: }]\par
206 {\em entry}]A pointer to a {\bf hash\_\-entry\_\-t} {\rm (p.\,\pageref{group__dbprim__hash_a1})}.
211 \item[{\bf Returns: }]\par
212 A pointer to a {\bf link\_\-elem\_\-t} {\rm (p.\,\pageref{group__dbprim__link_a1})}. \end{Desc}
213 \index{dbprim_hash@{dbprim\_\-hash}!he_table@{he\_\-table}}
214 \index{he_table@{he\_\-table}!dbprim_hash@{dbprim\_\-hash}}
215 \subsubsection{\setlength{\rightskip}{0pt plus 5cm}\#define he\_\-table(entry)}\label{group__dbprim__hash_a33}
220 This macro retrieves a pointer to the hash table the entry is in.\begin{Desc}
221 \item[{\bf Parameters: }]\par
224 {\em entry}]A pointer to a {\bf hash\_\-entry\_\-t} {\rm (p.\,\pageref{group__dbprim__hash_a1})}.
229 \item[{\bf Returns: }]\par
230 A pointer to a {\bf hash\_\-table\_\-t} {\rm (p.\,\pageref{group__dbprim__hash_a0})}. \end{Desc}
231 \index{dbprim_hash@{dbprim\_\-hash}!he_value@{he\_\-value}}
232 \index{he_value@{he\_\-value}!dbprim_hash@{dbprim\_\-hash}}
233 \subsubsection{\setlength{\rightskip}{0pt plus 5cm}\#define he\_\-value(entry)}\label{group__dbprim__hash_a36}
238 This macro retrieves the value associated with the hash table entry. It may be treated as an lvalue to change that value. Care should be taken when using this option.\begin{Desc}
239 \item[{\bf Parameters: }]\par
242 {\em entry}]A pointer to a {\bf hash\_\-entry\_\-t} {\rm (p.\,\pageref{group__dbprim__hash_a1})}.
247 \item[{\bf Returns: }]\par
248 A pointer to {\tt void} representing the value associated with this entry. \end{Desc}
249 \index{dbprim_hash@{dbprim\_\-hash}!he_verify@{he\_\-verify}}
250 \index{he_verify@{he\_\-verify}!dbprim_hash@{dbprim\_\-hash}}
251 \subsubsection{\setlength{\rightskip}{0pt plus 5cm}\#define he\_\-verify(entry)}\label{group__dbprim__hash_a30}
256 This macro verifies that a given pointer actually does point to a hash table entry.\begin{Desc}
257 \item[{\bf Parameters: }]\par
260 {\em entry}]A pointer to a {\bf hash\_\-entry\_\-t} {\rm (p.\,\pageref{group__dbprim__hash_a1})}.
265 \item[{\bf Returns: }]\par
266 Boolean true if {\tt entry} is a valid hash table entry or false otherwise. \end{Desc}
267 \index{dbprim_hash@{dbprim\_\-hash}!ht_comp@{ht\_\-comp}}
268 \index{ht_comp@{ht\_\-comp}!dbprim_hash@{dbprim\_\-hash}}
269 \subsubsection{\setlength{\rightskip}{0pt plus 5cm}\#define ht\_\-comp(table)}\label{group__dbprim__hash_a25}
274 This macro retrieves the comparison function pointer.\begin{Desc}
275 \item[{\bf Parameters: }]\par
278 {\em table}]A pointer to a {\bf hash\_\-table\_\-t} {\rm (p.\,\pageref{group__dbprim__hash_a0})}.
283 \item[{\bf Returns: }]\par
284 A {\bf hash\_\-comp\_\-t} {\rm (p.\,\pageref{group__dbprim__hash_a4})}. \end{Desc}
285 \index{dbprim_hash@{dbprim\_\-hash}!ht_count@{ht\_\-count}}
286 \index{ht_count@{ht\_\-count}!dbprim_hash@{dbprim\_\-hash}}
287 \subsubsection{\setlength{\rightskip}{0pt plus 5cm}\#define ht\_\-count(table)}\label{group__dbprim__hash_a23}
292 This macro retrieves the total number of items actually in the hash table.\begin{Desc}
293 \item[{\bf Parameters: }]\par
296 {\em table}]A pointer to a {\bf hash\_\-table\_\-t} {\rm (p.\,\pageref{group__dbprim__hash_a0})}.
301 \item[{\bf Returns: }]\par
302 An {\tt unsigned long} containing a count of the number of items in the hash table. \end{Desc}
303 \index{dbprim_hash@{dbprim\_\-hash}!ht_extra@{ht\_\-extra}}
304 \index{ht_extra@{ht\_\-extra}!dbprim_hash@{dbprim\_\-hash}}
305 \subsubsection{\setlength{\rightskip}{0pt plus 5cm}\#define ht\_\-extra(table)}\label{group__dbprim__hash_a27}
310 This macro retrieves the extra pointer data associated with a particular hash table.\begin{Desc}
311 \item[{\bf Parameters: }]\par
314 {\em table}]A pointer to a {\bf hash\_\-table\_\-t} {\rm (p.\,\pageref{group__dbprim__hash_a0})}.
319 \item[{\bf Returns: }]\par
320 A pointer to {\tt void}. \end{Desc}
321 \index{dbprim_hash@{dbprim\_\-hash}!ht_flags@{ht\_\-flags}}
322 \index{ht_flags@{ht\_\-flags}!dbprim_hash@{dbprim\_\-hash}}
323 \subsubsection{\setlength{\rightskip}{0pt plus 5cm}\#define ht\_\-flags(table)}\label{group__dbprim__hash_a20}
328 This macro retrieves the flags associated with the hash table. Only {\bf HASH\_\-FLAG\_\-AUTOGROW} {\rm (p.\,\pageref{group__dbprim__hash_a16})} and {\bf HASH\_\-FLAG\_\-AUTOSHRINK} {\rm (p.\,\pageref{group__dbprim__hash_a17})} have any meaning to the application; all other bits are reserved for use in the library. This macro may be used as an lvalue, but care must be taken to avoid modifying the library-specific bits.\begin{Desc}
329 \item[{\bf Parameters: }]\par
332 {\em table}]A pointer to a {\bf hash\_\-table\_\-t} {\rm (p.\,\pageref{group__dbprim__hash_a0})}.
337 \item[{\bf Returns: }]\par
338 An {\tt unsigned long} containing the flags for the hash table. \end{Desc}
339 \index{dbprim_hash@{dbprim\_\-hash}!ht_frozen@{ht\_\-frozen}}
340 \index{ht_frozen@{ht\_\-frozen}!dbprim_hash@{dbprim\_\-hash}}
341 \subsubsection{\setlength{\rightskip}{0pt plus 5cm}\#define ht\_\-frozen(table)}\label{group__dbprim__hash_a21}
346 This macro returns a non-zero value if the table is currently frozen. The hash table may be frozen if there is an iteration in progress.\begin{Desc}
347 \item[{\bf Parameters: }]\par
350 {\em table}]A pointer to a {\bf hash\_\-table\_\-t} {\rm (p.\,\pageref{group__dbprim__hash_a0})}.
355 \item[{\bf Returns: }]\par
356 A zero value if the table is not frozen or a non-zero value if the table is frozen. \end{Desc}
357 \index{dbprim_hash@{dbprim\_\-hash}!ht_func@{ht\_\-func}}
358 \index{ht_func@{ht\_\-func}!dbprim_hash@{dbprim\_\-hash}}
359 \subsubsection{\setlength{\rightskip}{0pt plus 5cm}\#define ht\_\-func(table)}\label{group__dbprim__hash_a24}
364 This macro retrieves the hash function pointer.\begin{Desc}
365 \item[{\bf Parameters: }]\par
368 {\em table}]A pointer to a {\bf hash\_\-table\_\-t} {\rm (p.\,\pageref{group__dbprim__hash_a0})}.
373 \item[{\bf Returns: }]\par
374 A {\bf hash\_\-func\_\-t} {\rm (p.\,\pageref{group__dbprim__hash_a3})}. \end{Desc}
375 \index{dbprim_hash@{dbprim\_\-hash}!ht_modulus@{ht\_\-modulus}}
376 \index{ht_modulus@{ht\_\-modulus}!dbprim_hash@{dbprim\_\-hash}}
377 \subsubsection{\setlength{\rightskip}{0pt plus 5cm}\#define ht\_\-modulus(table)}\label{group__dbprim__hash_a22}
382 This macro retrieves the number of buckets allocated for the hash table. An application may wish to save this value between invocations to avoid the overhead of growing the table while filling it with data.\begin{Desc}
383 \item[{\bf Parameters: }]\par
386 {\em table}]A pointer to a {\bf hash\_\-table\_\-t} {\rm (p.\,\pageref{group__dbprim__hash_a0})}.
391 \item[{\bf Returns: }]\par
392 An {\tt unsigned long} containing the number of buckets allocated for the hash table. \end{Desc}
393 \index{dbprim_hash@{dbprim\_\-hash}!ht_rsize@{ht\_\-rsize}}
394 \index{ht_rsize@{ht\_\-rsize}!dbprim_hash@{dbprim\_\-hash}}
395 \subsubsection{\setlength{\rightskip}{0pt plus 5cm}\#define ht\_\-rsize(table)}\label{group__dbprim__hash_a26}
400 This macro retrieves the resize callback function pointer.\begin{Desc}
401 \item[{\bf Parameters: }]\par
404 {\em table}]A pointer to a {\bf hash\_\-table\_\-t} {\rm (p.\,\pageref{group__dbprim__hash_a0})}.
409 \item[{\bf Returns: }]\par
410 A {\bf hash\_\-resize\_\-t} {\rm (p.\,\pageref{group__dbprim__hash_a5})}. \end{Desc}
411 \index{dbprim_hash@{dbprim\_\-hash}!ht_size@{ht\_\-size}}
412 \index{ht_size@{ht\_\-size}!dbprim_hash@{dbprim\_\-hash}}
413 \subsubsection{\setlength{\rightskip}{0pt plus 5cm}\#define ht\_\-size(table)}\label{group__dbprim__hash_a28}
418 This macro returns the physical size of the bucket array allocated by the library for this hash table.\begin{Desc}
419 \item[{\bf Parameters: }]\par
422 {\em table}]A pointer to a {\bf hash\_\-table\_\-t} {\rm (p.\,\pageref{group__dbprim__hash_a0})}.
427 \item[{\bf Returns: }]\par
428 A {\tt size\_\-t}. \end{Desc}
429 \index{dbprim_hash@{dbprim\_\-hash}!ht_verify@{ht\_\-verify}}
430 \index{ht_verify@{ht\_\-verify}!dbprim_hash@{dbprim\_\-hash}}
431 \subsubsection{\setlength{\rightskip}{0pt plus 5cm}\#define ht\_\-verify(table)}\label{group__dbprim__hash_a19}
436 This macro verifies that a given pointer actually does point to a hash table.\begin{Desc}
437 \item[{\bf Parameters: }]\par
440 {\em table}]A pointer to a {\bf hash\_\-table\_\-t} {\rm (p.\,\pageref{group__dbprim__hash_a0})}.
445 \item[{\bf Returns: }]\par
446 Boolean true if {\tt table} is a valid hash table or false otherwise. \end{Desc}
447 \index{dbprim_hash@{dbprim\_\-hash}!st_rsize@{st\_\-rsize}}
448 \index{st_rsize@{st\_\-rsize}!dbprim_hash@{dbprim\_\-hash}}
449 \subsubsection{\setlength{\rightskip}{0pt plus 5cm}\#define st\_\-rsize(table)}\label{group__dbprim__hash_a37}
454 This macro retrieves the resize callback function pointer.\begin{Desc}
455 \item[{\bf Parameters: }]\par
458 {\em table}]A pointer to a {\bf smat\_\-table\_\-t} {\rm (p.\,\pageref{group__dbprim__smat_a0})}.
463 \item[{\bf Returns: }]\par
464 A {\bf smat\_\-resize\_\-t} {\rm (p.\,\pageref{group__dbprim__smat_a3})}. \end{Desc}
467 \subsection{Typedef Documentation}
468 \index{dbprim_hash@{dbprim\_\-hash}!hash_comp_t@{hash\_\-comp\_\-t}}
469 \index{hash_comp_t@{hash\_\-comp\_\-t}!dbprim_hash@{dbprim\_\-hash}}
470 \subsubsection{\setlength{\rightskip}{0pt plus 5cm}typedef unsigned long($\ast$ hash\_\-comp\_\-t)({\bf hash\_\-table\_\-t} $\ast$, {\bf db\_\-key\_\-t} $\ast$, {\bf db\_\-key\_\-t} $\ast$)}\label{group__dbprim__hash_a4}
475 This function pointer references a callback used to compare entries in a hash table. It should return 0 for identical entries and non-zero otherwise. No assumptions should be made about the order in which the two keys are passed to this function. \index{dbprim_hash@{dbprim\_\-hash}!hash_entry_t@{hash\_\-entry\_\-t}}
476 \index{hash_entry_t@{hash\_\-entry\_\-t}!dbprim_hash@{dbprim\_\-hash}}
477 \subsubsection{\setlength{\rightskip}{0pt plus 5cm}typedef struct \_\-hash\_\-entry\_\-s hash\_\-entry\_\-t}\label{group__dbprim__hash_a1}
482 This structure represents a single entry of a hash table. \index{dbprim_hash@{dbprim\_\-hash}!hash_func_t@{hash\_\-func\_\-t}}
483 \index{hash_func_t@{hash\_\-func\_\-t}!dbprim_hash@{dbprim\_\-hash}}
484 \subsubsection{\setlength{\rightskip}{0pt plus 5cm}typedef unsigned long($\ast$ hash\_\-func\_\-t)({\bf hash\_\-table\_\-t} $\ast$, {\bf db\_\-key\_\-t} $\ast$)}\label{group__dbprim__hash_a3}
489 This function is associated with a hash table, and is responsible for generating a hash value. The full 32-bit range of an {\tt unsigned long} should be used--do $\ast$not$\ast$ reduce the hash value by the modulus of the hash table. \index{dbprim_hash@{dbprim\_\-hash}!hash_iter_t@{hash\_\-iter\_\-t}}
490 \index{hash_iter_t@{hash\_\-iter\_\-t}!dbprim_hash@{dbprim\_\-hash}}
491 \subsubsection{\setlength{\rightskip}{0pt plus 5cm}typedef unsigned long($\ast$ hash\_\-iter\_\-t)({\bf hash\_\-table\_\-t} $\ast$, {\bf hash\_\-entry\_\-t} $\ast$, void $\ast$)}\label{group__dbprim__hash_a2}
496 This function pointer references a callback used by {\bf ht\_\-iter}() {\rm (p.\,\pageref{group__dbprim__hash_a11})} and {\bf ht\_\-flush}() {\rm (p.\,\pageref{group__dbprim__hash_a12})}. It should return 0 for success. A non-zero return value will terminate the operation and will become the return value of the {\bf ht\_\-iter}() {\rm (p.\,\pageref{group__dbprim__hash_a11})} or {\bf ht\_\-flush}() {\rm (p.\,\pageref{group__dbprim__hash_a12})} call. \index{dbprim_hash@{dbprim\_\-hash}!hash_resize_t@{hash\_\-resize\_\-t}}
497 \index{hash_resize_t@{hash\_\-resize\_\-t}!dbprim_hash@{dbprim\_\-hash}}
498 \subsubsection{\setlength{\rightskip}{0pt plus 5cm}typedef unsigned long($\ast$ hash\_\-resize\_\-t)({\bf hash\_\-table\_\-t} $\ast$, unsigned long)}\label{group__dbprim__hash_a5}
503 This function pointer references a callback that will be called with both the old and new hash table sizes whenever a hash table is resized. It should return non-zero only when the resize should be inhibited. \index{dbprim_hash@{dbprim\_\-hash}!hash_table_t@{hash\_\-table\_\-t}}
504 \index{hash_table_t@{hash\_\-table\_\-t}!dbprim_hash@{dbprim\_\-hash}}
505 \subsubsection{\setlength{\rightskip}{0pt plus 5cm}typedef struct \_\-hash\_\-table\_\-s hash\_\-table\_\-t}\label{group__dbprim__hash_a0}
510 This structure is the basis of all hash tables maintained by this library.
512 \subsection{Function Documentation}
513 \index{dbprim_hash@{dbprim\_\-hash}!he_init@{he\_\-init}}
514 \index{he_init@{he\_\-init}!dbprim_hash@{dbprim\_\-hash}}
515 \subsubsection{\setlength{\rightskip}{0pt plus 5cm}unsigned long he\_\-init ({\bf hash\_\-entry\_\-t} $\ast$ {\em entry}, void $\ast$ {\em value})}\label{group__dbprim__hash_a15}
520 This function dynamically initializes a hash table entry.\begin{Desc}
521 \item[{\bf Parameters: }]\par
524 {\em entry}]A pointer to a {\bf hash\_\-entry\_\-t} {\rm (p.\,\pageref{group__dbprim__hash_a1})} to be initialized. \item[
525 {\em value}]A pointer to {\tt void} which will be the value of the hash table entry.\end{description}
528 \item[{\bf Return values: }]\par
531 {\em DB\_\-ERR\_\-BADARGS}]A {\tt NULL} pointer was passed for {\tt entry}. \end{description}
533 \index{dbprim_hash@{dbprim\_\-hash}!ht_add@{ht\_\-add}}
534 \index{ht_add@{ht\_\-add}!dbprim_hash@{dbprim\_\-hash}}
535 \subsubsection{\setlength{\rightskip}{0pt plus 5cm}unsigned long ht\_\-add ({\bf hash\_\-table\_\-t} $\ast$ {\em table}, {\bf hash\_\-entry\_\-t} $\ast$ {\em entry}, {\bf db\_\-key\_\-t} $\ast$ {\em key})}\label{group__dbprim__hash_a7}
540 This function adds an entry to a hash table.\begin{Desc}
541 \item[{\bf Parameters: }]\par
544 {\em table}]A pointer to a {\bf hash\_\-table\_\-t} {\rm (p.\,\pageref{group__dbprim__hash_a0})}. \item[
545 {\em entry}]A pointer to a {\bf hash\_\-entry\_\-t} {\rm (p.\,\pageref{group__dbprim__hash_a1})} to be added to the table. \item[
546 {\em key}]A pointer to a {\bf db\_\-key\_\-t} {\rm (p.\,\pageref{group__dbprim__key_a0})} containing the key for the entry.\end{description}
549 \item[{\bf Return values: }]\par
552 {\em DB\_\-ERR\_\-BADARGS}]An invalid argument was given. \item[
553 {\em DB\_\-ERR\_\-BUSY}]The entry is already in a table. \item[
554 {\em DB\_\-ERR\_\-FROZEN}]The table is currently frozen. \item[
555 {\em DB\_\-ERR\_\-NOTABLE}]The bucket table has not been allocated and automatic growth is not enabled. \item[
556 {\em DB\_\-ERR\_\-DUPLICATE}]The entry is a duplicate of an existing entry. \item[
557 {\em DB\_\-ERR\_\-UNRECOVERABLE}]An unrecoverable error occurred while resizing the table. \end{description}
559 \index{dbprim_hash@{dbprim\_\-hash}!ht_find@{ht\_\-find}}
560 \index{ht_find@{ht\_\-find}!dbprim_hash@{dbprim\_\-hash}}
561 \subsubsection{\setlength{\rightskip}{0pt plus 5cm}unsigned long ht\_\-find ({\bf hash\_\-table\_\-t} $\ast$ {\em table}, {\bf hash\_\-entry\_\-t} $\ast$$\ast$ {\em entry\_\-p}, {\bf db\_\-key\_\-t} $\ast$ {\em key})}\label{group__dbprim__hash_a10}
566 This function looks up an entry matching the given {\tt key}.\begin{Desc}
567 \item[{\bf Parameters: }]\par
570 {\em table}]A pointer to a {\bf hash\_\-table\_\-t} {\rm (p.\,\pageref{group__dbprim__hash_a0})}. \item[
571 {\em entry\_\-p}]A pointer to a pointer to a {\bf hash\_\-entry\_\-t} {\rm (p.\,\pageref{group__dbprim__hash_a1})}. This is a result parameter. If {\tt NULL} is passed, the lookup will be performed and an appropriate error code returned. \item[
572 {\em key}]A pointer to a {\bf db\_\-key\_\-t} {\rm (p.\,\pageref{group__dbprim__key_a0})} describing the item to find.\end{description}
575 \item[{\bf Return values: }]\par
578 {\em DB\_\-ERR\_\-BADARGS}]An argument was invalid. \item[
579 {\em DB\_\-ERR\_\-NOENTRY}]No matching entry was found. \end{description}
581 \index{dbprim_hash@{dbprim\_\-hash}!ht_flush@{ht\_\-flush}}
582 \index{ht_flush@{ht\_\-flush}!dbprim_hash@{dbprim\_\-hash}}
583 \subsubsection{\setlength{\rightskip}{0pt plus 5cm}unsigned long ht\_\-flush ({\bf hash\_\-table\_\-t} $\ast$ {\em table}, {\bf hash\_\-iter\_\-t} {\em flush\_\-func}, void $\ast$ {\em extra})}\label{group__dbprim__hash_a12}
588 This function flushes a hash table--that is, it removes each entry from the table. If a {\tt flush\_\-func} is specified, it will be called on the entry after it has been removed from the table, and may safely call {\tt free()}.\begin{Desc}
589 \item[{\bf Parameters: }]\par
592 {\em table}]A pointer to a {\bf hash\_\-table\_\-t} {\rm (p.\,\pageref{group__dbprim__hash_a0})}. \item[
593 {\em flush\_\-func}]A pointer to a callback function used to perform user-specified actions on an entry after removing it from the table. May be {\tt NULL}. See the documentation for {\bf hash\_\-iter\_\-t} {\rm (p.\,\pageref{group__dbprim__hash_a2})} for more information. \item[
594 {\em extra}]A {\tt void} pointer that will be passed to {\tt flush\_\-func}.\end{description}
597 \item[{\bf Return values: }]\par
600 {\em DB\_\-ERR\_\-BADARGS}]An argument was invalid. \item[
601 {\em DB\_\-ERR\_\-FROZEN}]The hash table is frozen. \end{description}
603 \index{dbprim_hash@{dbprim\_\-hash}!ht_free@{ht\_\-free}}
604 \index{ht_free@{ht\_\-free}!dbprim_hash@{dbprim\_\-hash}}
605 \subsubsection{\setlength{\rightskip}{0pt plus 5cm}unsigned long ht\_\-free ({\bf hash\_\-table\_\-t} $\ast$ {\em table})}\label{group__dbprim__hash_a14}
610 This function releases the memory used by the bucket table in an empty hash table.\begin{Desc}
611 \item[{\bf Parameters: }]\par
614 {\em table}]A pointer to a {\bf hash\_\-table\_\-t} {\rm (p.\,\pageref{group__dbprim__hash_a0})}.\end{description}
617 \item[{\bf Return values: }]\par
620 {\em DB\_\-ERR\_\-BADARGS}]An invalid argument was given. \item[
621 {\em DB\_\-ERR\_\-FROZEN}]The table is frozen. \item[
622 {\em DB\_\-ERR\_\-NOTEMPTY}]The table is not empty. \end{description}
624 \index{dbprim_hash@{dbprim\_\-hash}!ht_init@{ht\_\-init}}
625 \index{ht_init@{ht\_\-init}!dbprim_hash@{dbprim\_\-hash}}
626 \subsubsection{\setlength{\rightskip}{0pt plus 5cm}unsigned long ht\_\-init ({\bf hash\_\-table\_\-t} $\ast$ {\em table}, unsigned long {\em flags}, {\bf hash\_\-func\_\-t} {\em func}, {\bf hash\_\-comp\_\-t} {\em comp}, {\bf hash\_\-resize\_\-t} {\em resize}, void $\ast$ {\em extra}, unsigned long {\em init\_\-mod})}\label{group__dbprim__hash_a6}
631 This function dynamically initializes a hash table.\begin{Desc}
632 \item[{\bf Parameters: }]\par
635 {\em table}]A pointer to a {\bf hash\_\-table\_\-t} {\rm (p.\,\pageref{group__dbprim__hash_a0})} to be initialized. \item[
636 {\em flags}]A bit-wise OR of {\bf HASH\_\-FLAG\_\-AUTOGROW} {\rm (p.\,\pageref{group__dbprim__hash_a16})} and {\bf HASH\_\-FLAG\_\-AUTOSHRINK} {\rm (p.\,\pageref{group__dbprim__hash_a17})}. If neither behavior is desired, use 0. \item[
637 {\em func}]A {\bf hash\_\-func\_\-t} {\rm (p.\,\pageref{group__dbprim__hash_a3})} function pointer for a hash function. \item[
638 {\em comp}]A {\bf hash\_\-comp\_\-t} {\rm (p.\,\pageref{group__dbprim__hash_a4})} function pointer for a comparison function. \item[
639 {\em resize}]A {\bf hash\_\-resize\_\-t} {\rm (p.\,\pageref{group__dbprim__hash_a5})} function pointer for determining whether resizing is permitted and/or for notification of the resize. \item[
640 {\em extra}]Extra pointer data that should be associated with the hash table. \item[
641 {\em init\_\-mod}]An initial modulus for the table. This will presumably be extracted by {\bf ht\_\-modulus}() {\rm (p.\,\pageref{group__dbprim__hash_a22})} in a previous invocation of the application. A 0 value is valid.\end{description}
644 \item[{\bf Return values: }]\par
647 {\em DB\_\-ERR\_\-BADARGS}]An invalid argument was given. \item[
648 {\em ENOMEM}]Unable to allocate memory. \end{description}
650 \index{dbprim_hash@{dbprim\_\-hash}!ht_iter@{ht\_\-iter}}
651 \index{ht_iter@{ht\_\-iter}!dbprim_hash@{dbprim\_\-hash}}
652 \subsubsection{\setlength{\rightskip}{0pt plus 5cm}unsigned long ht\_\-iter ({\bf hash\_\-table\_\-t} $\ast$ {\em table}, {\bf hash\_\-iter\_\-t} {\em iter\_\-func}, void $\ast$ {\em extra})}\label{group__dbprim__hash_a11}
657 This function iterates over every entry in a hash table (in an unspecified order), executing the given {\tt iter\_\-func} on each entry.\begin{Desc}
658 \item[{\bf Parameters: }]\par
661 {\em table}]A pointer to a {\bf hash\_\-table\_\-t} {\rm (p.\,\pageref{group__dbprim__hash_a0})}. \item[
662 {\em iter\_\-func}]A pointer to a callback function used to perform user-specified actions on an entry in a hash table. {\tt NULL} is an invalid value. See the documentation for {\bf hash\_\-iter\_\-t} {\rm (p.\,\pageref{group__dbprim__hash_a2})} for more information. \item[
663 {\em extra}]A {\tt void} pointer that will be passed to {\tt iter\_\-func}.\end{description}
666 \item[{\bf Return values: }]\par
669 {\em DB\_\-ERR\_\-BADARGS}]An argument was invalid. \item[
670 {\em DB\_\-ERR\_\-FROZEN}]The hash table is frozen. \end{description}
672 \index{dbprim_hash@{dbprim\_\-hash}!ht_move@{ht\_\-move}}
673 \index{ht_move@{ht\_\-move}!dbprim_hash@{dbprim\_\-hash}}
674 \subsubsection{\setlength{\rightskip}{0pt plus 5cm}unsigned long ht\_\-move ({\bf hash\_\-table\_\-t} $\ast$ {\em table}, {\bf hash\_\-entry\_\-t} $\ast$ {\em entry}, {\bf db\_\-key\_\-t} $\ast$ {\em key})}\label{group__dbprim__hash_a8}
679 This function moves an existing entry in the hash table to correspond to the new key.\begin{Desc}
680 \item[{\bf Parameters: }]\par
683 {\em table}]A pointer to a {\bf hash\_\-table\_\-t} {\rm (p.\,\pageref{group__dbprim__hash_a0})}. \item[
684 {\em entry}]A pointer to a {\bf hash\_\-entry\_\-t} {\rm (p.\,\pageref{group__dbprim__hash_a1})} to be moved. It must already be in the hash table. \item[
685 {\em key}]A pointer to a {\bf db\_\-key\_\-t} {\rm (p.\,\pageref{group__dbprim__key_a0})} describing the new key for the entry.\end{description}
688 \item[{\bf Return values: }]\par
691 {\em DB\_\-ERR\_\-BADARGS}]An invalid argument was given. \item[
692 {\em DB\_\-ERR\_\-UNUSED}]Entry is not in a hash table. \item[
693 {\em DB\_\-ERR\_\-WRONGTABLE}]Entry is not in this hash table. \item[
694 {\em DB\_\-ERR\_\-FROZEN}]Hash table is frozen. \item[
695 {\em DB\_\-ERR\_\-DUPLICATE}]New key is a duplicate of an existing key. \item[
696 {\em DB\_\-ERR\_\-READDFAILED}]Unable to re-add entry to table. \end{description}
698 \index{dbprim_hash@{dbprim\_\-hash}!ht_remove@{ht\_\-remove}}
699 \index{ht_remove@{ht\_\-remove}!dbprim_hash@{dbprim\_\-hash}}
700 \subsubsection{\setlength{\rightskip}{0pt plus 5cm}unsigned long ht\_\-remove ({\bf hash\_\-table\_\-t} $\ast$ {\em table}, {\bf hash\_\-entry\_\-t} $\ast$ {\em entry})}\label{group__dbprim__hash_a9}
705 This function removes the given element from the specified hash table.\begin{Desc}
706 \item[{\bf Parameters: }]\par
709 {\em table}]A pointer to a {\bf hash\_\-table\_\-t} {\rm (p.\,\pageref{group__dbprim__hash_a0})}. \item[
710 {\em entry}]A pointer to a {\bf hash\_\-entry\_\-t} {\rm (p.\,\pageref{group__dbprim__hash_a1})} to be removed from the table.\end{description}
713 \item[{\bf Return values: }]\par
716 {\em DB\_\-ERR\_\-BADARGS}]An invalid argument was given. \item[
717 {\em DB\_\-ERR\_\-UNUSED}]Entry is not in a hash table. \item[
718 {\em DB\_\-ERR\_\-WRONGTABLE}]Entry is not in this hash table. \item[
719 {\em DB\_\-ERR\_\-FROZEN}]Hash table is frozen. \item[
720 {\em DB\_\-ERR\_\-UNRECOVERABLE}]An unrecoverable error occurred while resizing the table. \end{description}
722 \index{dbprim_hash@{dbprim\_\-hash}!ht_resize@{ht\_\-resize}}
723 \index{ht_resize@{ht\_\-resize}!dbprim_hash@{dbprim\_\-hash}}
724 \subsubsection{\setlength{\rightskip}{0pt plus 5cm}unsigned long ht\_\-resize ({\bf hash\_\-table\_\-t} $\ast$ {\em table}, unsigned long {\em new\_\-size})}\label{group__dbprim__hash_a13}
729 This function resizes a hash table to the given {\tt new\_\-size}. If {\tt new\_\-size} is 0, then an appropriate new size based on the current number of items in the hash table will be selected.\begin{Desc}
730 \item[{\bf Parameters: }]\par
733 {\em table}]A pointer to a {\bf hash\_\-table\_\-t} {\rm (p.\,\pageref{group__dbprim__hash_a0})}. \item[
734 {\em new\_\-size}]A new size value for the table.\end{description}
737 \item[{\bf Return values: }]\par
740 {\em DB\_\-ERR\_\-BADARGS}]An argument was invalid. \item[
741 {\em DB\_\-ERR\_\-FROZEN}]The table is currently frozen. \item[
742 {\em DB\_\-ERR\_\-UNRECOVERABLE}]A catastrophic error was encountered. The table is now unusable. \item[
743 {\em ENOMEM}]No memory could be allocated for the new bucket table. \end{description}