]>
Commit | Line | Data |
---|---|---|
74235cc9 UM |
1 | =pod |
2 | ||
3 | =head1 NAME | |
4 | ||
5317b6ee | 5 | LHASH, LHASH_OF, DEFINE_LHASH_OF_EX, DEFINE_LHASH_OF, |
739a1eb1 RS |
6 | OPENSSL_LH_COMPFUNC, OPENSSL_LH_HASHFUNC, OPENSSL_LH_DOALL_FUNC, |
7 | LHASH_DOALL_ARG_FN_TYPE, | |
91da5e77 | 8 | IMPLEMENT_LHASH_HASH_FN, IMPLEMENT_LHASH_COMP_FN, |
1bdbdaff | 9 | lh_TYPE_new, lh_TYPE_free, lh_TYPE_flush, |
739a1eb1 | 10 | lh_TYPE_insert, lh_TYPE_delete, lh_TYPE_retrieve, |
7e1d7fea MC |
11 | lh_TYPE_doall, lh_TYPE_doall_arg, lh_TYPE_error, |
12 | OPENSSL_LH_new, OPENSSL_LH_free, OPENSSL_LH_flush, | |
13 | OPENSSL_LH_insert, OPENSSL_LH_delete, OPENSSL_LH_retrieve, | |
14 | OPENSSL_LH_doall, OPENSSL_LH_doall_arg, OPENSSL_LH_error | |
15 | - dynamic hash table | |
74235cc9 UM |
16 | |
17 | =head1 SYNOPSIS | |
18 | ||
bb82531f | 19 | =for openssl generic |
b97fdb57 | 20 | |
74235cc9 UM |
21 | #include <openssl/lhash.h> |
22 | ||
5317b6ee HL |
23 | LHASH_OF(TYPE) |
24 | ||
25 | DEFINE_LHASH_OF_EX(TYPE); | |
74235cc9 | 26 | |
7e1d7fea | 27 | LHASH_OF(TYPE) *lh_TYPE_new(OPENSSL_LH_HASHFUNC hash, OPENSSL_LH_COMPFUNC compare); |
86a92bcb | 28 | void lh_TYPE_free(LHASH_OF(TYPE) *table); |
1bdbdaff | 29 | void lh_TYPE_flush(LHASH_OF(TYPE) *table); |
74235cc9 | 30 | |
86a92bcb ER |
31 | TYPE *lh_TYPE_insert(LHASH_OF(TYPE) *table, TYPE *data); |
32 | TYPE *lh_TYPE_delete(LHASH_OF(TYPE) *table, TYPE *data); | |
33 | TYPE *lh_retrieve(LHASH_OF(TYPE) *table, TYPE *data); | |
74235cc9 | 34 | |
86a92bcb | 35 | void lh_TYPE_doall(LHASH_OF(TYPE) *table, OPENSSL_LH_DOALL_FUNC func); |
739a1eb1 | 36 | void lh_TYPE_doall_arg(LHASH_OF(TYPE) *table, OPENSSL_LH_DOALL_FUNCARG func, |
d1f8b74c | 37 | TYPE *arg); |
3c1d6bbc | 38 | |
739a1eb1 | 39 | int lh_TYPE_error(LHASH_OF(TYPE) *table); |
74235cc9 | 40 | |
739a1eb1 RS |
41 | typedef int (*OPENSSL_LH_COMPFUNC)(const void *, const void *); |
42 | typedef unsigned long (*OPENSSL_LH_HASHFUNC)(const void *); | |
43 | typedef void (*OPENSSL_LH_DOALL_FUNC)(const void *); | |
ab5db007 | 44 | typedef void (*LHASH_DOALL_ARG_FN_TYPE)(const void *, const void *); |
73377727 | 45 | |
7e1d7fea MC |
46 | OPENSSL_LHASH *OPENSSL_LH_new(OPENSSL_LH_HASHFUNC h, OPENSSL_LH_COMPFUNC c); |
47 | void OPENSSL_LH_free(OPENSSL_LHASH *lh); | |
48 | void OPENSSL_LH_flush(OPENSSL_LHASH *lh); | |
49 | ||
50 | void *OPENSSL_LH_insert(OPENSSL_LHASH *lh, void *data); | |
51 | void *OPENSSL_LH_delete(OPENSSL_LHASH *lh, const void *data); | |
52 | void *OPENSSL_LH_retrieve(OPENSSL_LHASH *lh, const void *data); | |
53 | ||
54 | void OPENSSL_LH_doall(OPENSSL_LHASH *lh, OPENSSL_LH_DOALL_FUNC func); | |
55 | void OPENSSL_LH_doall_arg(OPENSSL_LHASH *lh, OPENSSL_LH_DOALL_FUNCARG func, void *arg); | |
56 | ||
57 | int OPENSSL_LH_error(OPENSSL_LHASH *lh); | |
58 | ||
5317b6ee HL |
59 | The following macro is deprecated: |
60 | ||
61 | DEFINE_LHASH_OF(TYPE); | |
62 | ||
74235cc9 UM |
63 | =head1 DESCRIPTION |
64 | ||
3c1d6bbc BL |
65 | This library implements type-checked dynamic hash tables. The hash |
66 | table entries can be arbitrary structures. Usually they consist of key | |
bbecf04e | 67 | and value fields. In the description here, B<I<TYPE>> is used a placeholder |
739a1eb1 | 68 | for any of the OpenSSL datatypes, such as I<SSL_SESSION>. |
3c1d6bbc | 69 | |
5317b6ee HL |
70 | To define a new type-checked dynamic hash table, use B<DEFINE_LHASH_OF_EX>(). |
71 | B<DEFINE_LHASH_OF>() was previously used for this purpose, but is now | |
72 | deprecated. The B<DEFINE_LHASH_OF_EX>() macro provides all functionality of | |
73 | B<DEFINE_LHASH_OF>() except for certain deprecated statistics functions (see | |
74 | OPENSSL_LH_stats(3)). | |
75 | ||
bbecf04e | 76 | B<lh_I<TYPE>_new>() creates a new B<LHASH_OF>(B<I<TYPE>>) structure to store |
91da5e77 | 77 | arbitrary data entries, and specifies the 'hash' and 'compare' |
bbecf04e | 78 | callbacks to be used in organising the table's entries. The I<hash> |
3c1d6bbc BL |
79 | callback takes a pointer to a table entry as its argument and returns |
80 | an unsigned long hash value for its key field. The hash value is | |
81 | normally truncated to a power of 2, so make sure that your hash | |
bbecf04e | 82 | function returns well mixed low order bits. The I<compare> callback |
3c1d6bbc | 83 | takes two arguments (pointers to two hash table entries), and returns |
9c0586d5 | 84 | 0 if their keys are equal, nonzero otherwise. |
91da5e77 RS |
85 | |
86 | If your hash table | |
bbecf04e RL |
87 | will contain items of some particular type and the I<hash> and |
88 | I<compare> callbacks hash/compare these types, then the | |
91da5e77 | 89 | B<IMPLEMENT_LHASH_HASH_FN> and B<IMPLEMENT_LHASH_COMP_FN> macros can be |
3c1d6bbc | 90 | used to create callback wrappers of the prototypes required by |
bbecf04e | 91 | B<lh_I<TYPE>_new>() as shown in this example: |
91da5e77 RS |
92 | |
93 | /* | |
94 | * Implement the hash and compare functions; "stuff" can be any word. | |
95 | */ | |
96 | static unsigned long stuff_hash(const TYPE *a) | |
97 | { | |
98 | ... | |
99 | } | |
100 | static int stuff_cmp(const TYPE *a, const TYPE *b) | |
101 | { | |
102 | ... | |
73377727 | 103 | } |
74235cc9 | 104 | |
91da5e77 RS |
105 | /* |
106 | * Implement the wrapper functions. | |
107 | */ | |
108 | static IMPLEMENT_LHASH_HASH_FN(stuff, TYPE) | |
109 | static IMPLEMENT_LHASH_COMP_FN(stuff, TYPE) | |
110 | ||
111 | If the type is going to be used in several places, the following macros | |
112 | can be used in a common header file to declare the function wrappers: | |
113 | ||
114 | DECLARE_LHASH_HASH_FN(stuff, TYPE) | |
115 | DECLARE_LHASH_COMP_FN(stuff, TYPE) | |
116 | ||
bbecf04e | 117 | Then a hash table of B<I<TYPE>> objects can be created using this: |
91da5e77 RS |
118 | |
119 | LHASH_OF(TYPE) *htable; | |
120 | ||
bbecf04e | 121 | htable = B<lh_I<TYPE>_new>(LHASH_HASH_FN(stuff), LHASH_COMP_FN(stuff)); |
91da5e77 | 122 | |
bbecf04e RL |
123 | B<lh_I<TYPE>_free>() frees the B<LHASH_OF>(B<I<TYPE>>) structure |
124 | I<table>. Allocated hash table entries will not be freed; consider | |
125 | using B<lh_I<TYPE>_doall>() to deallocate any remaining entries in the | |
3c1d6bbc | 126 | hash table (see below). |
74235cc9 | 127 | |
bbecf04e | 128 | B<lh_I<TYPE>_flush>() empties the B<LHASH_OF>(B<I<TYPE>>) structure I<table>. New |
1bdbdaff | 129 | entries can be added to the flushed table. Allocated hash table entries |
bbecf04e | 130 | will not be freed; consider using B<lh_I<TYPE>_doall>() to deallocate any |
1bdbdaff P |
131 | remaining entries in the hash table (see below). |
132 | ||
bbecf04e RL |
133 | B<lh_I<TYPE>_insert>() inserts the structure pointed to by I<data> into |
134 | I<table>. If there already is an entry with the same key, the old | |
135 | value is replaced. Note that B<lh_I<TYPE>_insert>() stores pointers, the | |
3c1d6bbc | 136 | data are not copied. |
74235cc9 | 137 | |
bbecf04e | 138 | B<lh_I<TYPE>_delete>() deletes an entry from I<table>. |
74235cc9 | 139 | |
bbecf04e | 140 | B<lh_I<TYPE>_retrieve>() looks up an entry in I<table>. Normally, I<data> |
3c1d6bbc | 141 | is a structure with the key field(s) set; the function will return a |
74235cc9 UM |
142 | pointer to a fully populated structure. |
143 | ||
bbecf04e RL |
144 | B<lh_I<TYPE>_doall>() will, for every entry in the hash table, call |
145 | I<func> with the data item as its parameter. | |
91da5e77 | 146 | For example: |
ab5db007 GT |
147 | |
148 | /* Cleans up resources belonging to 'a' (this is implemented elsewhere) */ | |
91da5e77 RS |
149 | void TYPE_cleanup_doall(TYPE *a); |
150 | ||
151 | /* Implement a prototype-compatible wrapper for "TYPE_cleanup" */ | |
152 | IMPLEMENT_LHASH_DOALL_FN(TYPE_cleanup, TYPE) | |
153 | ||
154 | /* Call "TYPE_cleanup" against all items in a hash table. */ | |
155 | lh_TYPE_doall(hashtable, LHASH_DOALL_FN(TYPE_cleanup)); | |
156 | ||
ab5db007 | 157 | /* Then the hash table itself can be deallocated */ |
91da5e77 | 158 | lh_TYPE_free(hashtable); |
ab5db007 GT |
159 | |
160 | When doing this, be careful if you delete entries from the hash table | |
161 | in your callbacks: the table may decrease in size, moving the item | |
162 | that you are currently on down lower in the hash table - this could | |
163 | cause some entries to be skipped during the iteration. The second | |
164 | best solution to this problem is to set hash-E<gt>down_load=0 before | |
165 | you start (which will stop the hash table ever decreasing in size). | |
166 | The best solution is probably to avoid deleting items from the hash | |
167 | table inside a "doall" callback! | |
168 | ||
bbecf04e RL |
169 | B<lh_I<TYPE>_doall_arg>() is the same as B<lh_I<TYPE>_doall>() except that |
170 | I<func> will be called with I<arg> as the second argument and I<func> | |
171 | should be of type B<LHASH_DOALL_ARG_FN>(B<I<TYPE>>) (a callback prototype | |
3c1d6bbc BL |
172 | that is passed both the table entry and an extra argument). As with |
173 | lh_doall(), you can instead choose to declare your callback with a | |
174 | prototype matching the types you are dealing with and use the | |
175 | declare/implement macros to create compatible wrappers that cast | |
176 | variables before calling your type-specific callbacks. An example of | |
177 | this is demonstrated here (printing all hash table entries to a BIO | |
178 | that is provided by the caller): | |
ab5db007 GT |
179 | |
180 | /* Prints item 'a' to 'output_bio' (this is implemented elsewhere) */ | |
91da5e77 RS |
181 | void TYPE_print_doall_arg(const TYPE *a, BIO *output_bio); |
182 | ||
183 | /* Implement a prototype-compatible wrapper for "TYPE_print" */ | |
184 | static IMPLEMENT_LHASH_DOALL_ARG_FN(TYPE, const TYPE, BIO) | |
185 | ||
ab5db007 | 186 | /* Print out the entire hashtable to a particular BIO */ |
91da5e77 RS |
187 | lh_TYPE_doall_arg(hashtable, LHASH_DOALL_ARG_FN(TYPE_print), BIO, |
188 | logging_bio); | |
1bc74519 | 189 | |
739a1eb1 | 190 | |
bbecf04e | 191 | B<lh_I<TYPE>_error>() can be used to determine if an error occurred in the last |
739a1eb1 | 192 | operation. |
74235cc9 | 193 | |
7e1d7fea MC |
194 | OPENSSL_LH_new() is the same as the B<lh_I<TYPE>_new>() except that it is not |
195 | type specific. So instead of returning an B<LHASH_OF(I<TYPE>)> value it returns | |
196 | a B<void *>. In the same way the functions OPENSSL_LH_free(), | |
197 | OPENSSL_LH_flush(), OPENSSL_LH_insert(), OPENSSL_LH_delete(), | |
198 | OPENSSL_LH_retrieve(), OPENSSL_LH_doall(), OPENSSL_LH_doall_arg(), and | |
199 | OPENSSL_LH_error() are equivalent to the similarly named B<lh_I<TYPE>> functions | |
200 | except that they return or use a B<void *> where the equivalent B<lh_I<TYPE>> | |
201 | function returns or uses a B<I<TYPE> *> or B<LHASH_OF(I<TYPE>) *>. B<lh_I<TYPE>> | |
202 | functions are implemented as type checked wrappers around the B<OPENSSL_LH> | |
203 | functions. Most applications should not call the B<OPENSSL_LH> functions | |
204 | directly. | |
205 | ||
74235cc9 UM |
206 | =head1 RETURN VALUES |
207 | ||
7e1d7fea MC |
208 | B<lh_I<TYPE>_new>() and OPENSSL_LH_new() return NULL on error, otherwise a |
209 | pointer to the new B<LHASH> structure. | |
74235cc9 | 210 | |
7e1d7fea MC |
211 | When a hash table entry is replaced, B<lh_I<TYPE>_insert>() or |
212 | OPENSSL_LH_insert() return the value being replaced. NULL is returned on normal | |
213 | operation and on error. | |
74235cc9 | 214 | |
7e1d7fea MC |
215 | B<lh_I<TYPE>_delete>() and OPENSSL_LH_delete() return the entry being deleted. |
216 | NULL is returned if there is no such value in the hash table. | |
74235cc9 | 217 | |
7e1d7fea MC |
218 | B<lh_I<TYPE>_retrieve>() and OPENSSL_LH_retrieve() return the hash table entry |
219 | if it has been found, NULL otherwise. | |
74235cc9 | 220 | |
7e1d7fea MC |
221 | B<lh_I<TYPE>_error>() and OPENSSL_LH_error() return 1 if an error occurred in |
222 | the last operation, 0 otherwise. It's meaningful only after non-retrieve | |
223 | operations. | |
74235cc9 | 224 | |
7e1d7fea MC |
225 | B<lh_I<TYPE>_free>(), OPENSSL_LH_free(), B<lh_I<TYPE>_flush>(), |
226 | OPENSSL_LH_flush(), B<lh_I<TYPE>_doall>() OPENSSL_LH_doall(), | |
227 | B<lh_I<TYPE>_doall_arg>() and OPENSSL_LH_doall_arg() return no values. | |
74235cc9 | 228 | |
ab5db007 GT |
229 | =head1 NOTE |
230 | ||
d1f8b74c | 231 | The LHASH code is not thread safe. All updating operations, as well as |
7e1d7fea MC |
232 | B<lh_I<TYPE>_error>() or OPENSSL_LH_error() calls must be performed under |
233 | a write lock. All retrieve operations should be performed under a read lock, | |
234 | I<unless> accurate usage statistics are desired. In which case, a write lock | |
235 | should be used for retrieve operations as well. For output of the usage | |
236 | statistics, using the functions from L<OPENSSL_LH_stats(3)>, a read lock | |
237 | suffices. | |
2e8b5d75 | 238 | |
ab5db007 GT |
239 | The LHASH code regards table entries as constant data. As such, it |
240 | internally represents lh_insert()'d items with a "const void *" | |
241 | pointer type. This is why callbacks such as those used by lh_doall() | |
242 | and lh_doall_arg() declare their prototypes with "const", even for the | |
243 | parameters that pass back the table items' data pointers - for | |
244 | consistency, user-provided data is "const" at all times as far as the | |
245 | LHASH code is concerned. However, as callers are themselves providing | |
246 | these pointers, they can choose whether they too should be treating | |
247 | all such parameters as constant. | |
248 | ||
249 | As an example, a hash table may be maintained by code that, for | |
250 | reasons of encapsulation, has only "const" access to the data being | |
8c1cbc72 | 251 | indexed in the hash table (i.e. it is returned as "const" from |
ab5db007 GT |
252 | elsewhere in their code) - in this case the LHASH prototypes are |
253 | appropriate as-is. Conversely, if the caller is responsible for the | |
254 | life-time of the data in question, then they may well wish to make | |
255 | modifications to table item passed back in the lh_doall() or | |
91da5e77 | 256 | lh_doall_arg() callbacks (see the "TYPE_cleanup" example above). If |
ab5db007 GT |
257 | so, the caller can either cast the "const" away (if they're providing |
258 | the raw callbacks themselves) or use the macros to declare/implement | |
259 | the wrapper functions without "const" types. | |
260 | ||
261 | Callers that only have "const" access to data they're indexing in a | |
262 | table, yet declare callbacks without constant types (or cast the | |
263 | "const" away themselves), are therefore creating their own risks/bugs | |
264 | without being encouraged to do so by the API. On a related note, | |
265 | those auditing code should pay special attention to any instances of | |
266 | DECLARE/IMPLEMENT_LHASH_DOALL_[ARG_]_FN macros that provide types | |
267 | without any "const" qualifiers. | |
268 | ||
74235cc9 UM |
269 | =head1 BUGS |
270 | ||
7e1d7fea MC |
271 | B<lh_I<TYPE>_insert>() and OPENSSL_LH_insert() return NULL both for success |
272 | and error. | |
74235cc9 | 273 | |
74235cc9 UM |
274 | =head1 SEE ALSO |
275 | ||
b97fdb57 | 276 | L<OPENSSL_LH_stats(3)> |
74235cc9 | 277 | |
05ea606a RS |
278 | =head1 HISTORY |
279 | ||
280 | In OpenSSL 1.0.0, the lhash interface was revamped for better | |
281 | type checking. | |
e2f92610 | 282 | |
5317b6ee HL |
283 | In OpenSSL 3.1, B<DEFINE_LHASH_OF_EX>() was introduced and B<DEFINE_LHASH_OF>() |
284 | was deprecated. | |
285 | ||
e2f92610 RS |
286 | =head1 COPYRIGHT |
287 | ||
8020d79b | 288 | Copyright 2000-2021 The OpenSSL Project Authors. All Rights Reserved. |
e2f92610 | 289 | |
4746f25a | 290 | Licensed under the Apache License 2.0 (the "License"). You may not use |
e2f92610 RS |
291 | this file except in compliance with the License. You can obtain a copy |
292 | in the file LICENSE in the source distribution or at | |
293 | L<https://www.openssl.org/source/license.html>. | |
294 | ||
295 | =cut |