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