Line data Source code
1 : #ifndef AWS_COMMON_HASH_TABLE_H
2 : #define AWS_COMMON_HASH_TABLE_H
3 :
4 : /**
5 : * Copyright Amazon.com, Inc. or its affiliates. All Rights Reserved.
6 : * SPDX-License-Identifier: Apache-2.0.
7 : */
8 :
9 : #include <aws/common/common.h>
10 :
11 : #include <stddef.h>
12 :
13 0 : #define AWS_COMMON_HASH_TABLE_ITER_CONTINUE (1 << 0)
14 0 : #define AWS_COMMON_HASH_TABLE_ITER_DELETE (1 << 1)
15 :
16 : /**
17 : * Hash table data structure. This module provides an automatically resizing
18 : * hash table implementation for general purpose use. The hash table stores a
19 : * mapping between void * keys and values; it is expected that in most cases,
20 : * these will point to a structure elsewhere in the heap, instead of inlining a
21 : * key or value into the hash table element itself.
22 : *
23 : * Currently, this hash table implements a variant of robin hood hashing, but
24 : * we do not guarantee that this won't change in the future.
25 : *
26 : * Associated with each hash function are four callbacks:
27 : *
28 : * hash_fn - A hash function from the keys to a uint64_t. It is critical that
29 : * the hash function for a key does not change while the key is in the hash
30 : * table; violating this results in undefined behavior. Collisions are
31 : * tolerated, though naturally with reduced performance.
32 : *
33 : * equals_fn - An equality comparison function. This function must be
34 : * reflexive and consistent with hash_fn.
35 : *
36 : * destroy_key_fn, destroy_value_fn - Optional callbacks invoked when the
37 : * table is cleared or cleaned up and at the caller's option when an element
38 : * is removed from the table. Either or both may be set to NULL, which
39 : * has the same effect as a no-op destroy function.
40 : *
41 : * This datastructure can be safely moved between threads, subject to the
42 : * requirements of the underlying allocator. It is also safe to invoke
43 : * non-mutating operations on the hash table from multiple threads. A suitable
44 : * memory barrier must be used when transitioning from single-threaded mutating
45 : * usage to multithreaded usage.
46 : */
47 : struct hash_table_state; /* Opaque pointer */
48 : struct aws_hash_table {
49 : struct hash_table_state *p_impl;
50 : };
51 :
52 : /**
53 : * Represents an element in the hash table. Various operations on the hash
54 : * table may provide pointers to elements stored within the hash table;
55 : * generally, calling code may alter value, but must not alter key (or any
56 : * information used to compute key's hash code).
57 : *
58 : * Pointers to elements within the hash are invalidated whenever an operation
59 : * which may change the number of elements in the hash is invoked (i.e. put,
60 : * delete, clear, and clean_up), regardless of whether the number of elements
61 : * actually changes.
62 : */
63 : struct aws_hash_element {
64 : const void *key;
65 : void *value;
66 : };
67 :
68 : enum aws_hash_iter_status {
69 : AWS_HASH_ITER_STATUS_DONE,
70 : AWS_HASH_ITER_STATUS_DELETE_CALLED,
71 : AWS_HASH_ITER_STATUS_READY_FOR_USE,
72 : };
73 :
74 : struct aws_hash_iter {
75 : const struct aws_hash_table *map;
76 : struct aws_hash_element element;
77 : size_t slot;
78 : size_t limit;
79 : enum aws_hash_iter_status status;
80 : /*
81 : * Reserving extra fields for binary compatibility with future expansion of
82 : * iterator in case hash table implementation changes.
83 : */
84 : int unused_0;
85 : void *unused_1;
86 : void *unused_2;
87 : };
88 :
89 : /**
90 : * Prototype for a key hashing function pointer.
91 : */
92 : typedef uint64_t(aws_hash_fn)(const void *key);
93 :
94 : /**
95 : * Prototype for a hash table equality check function pointer.
96 : *
97 : * This type is usually used for a function that compares two hash table
98 : * keys, but note that the same type is used for a function that compares
99 : * two hash table values in aws_hash_table_eq.
100 : *
101 : * Equality functions used in a hash table must be reflexive (i.e., a == b if
102 : * and only if b == a), and must be consistent with the hash function in use.
103 : */
104 : typedef bool(aws_hash_callback_eq_fn)(const void *a, const void *b);
105 :
106 : /**
107 : * Prototype for a hash table key or value destructor function pointer.
108 : *
109 : * This function is used to destroy elements in the hash table when the
110 : * table is cleared or cleaned up.
111 : *
112 : * Note that functions which remove individual elements from the hash
113 : * table provide options of whether or not to invoke the destructors
114 : * on the key and value of a removed element.
115 : */
116 : typedef void(aws_hash_callback_destroy_fn)(void *key_or_value);
117 :
118 : AWS_EXTERN_C_BEGIN
119 :
120 : /**
121 : * Initializes a hash map with initial capacity for 'size' elements
122 : * without resizing. Uses hash_fn to compute the hash of each element.
123 : * equals_fn to compute equality of two keys. Whenever an element is
124 : * removed without being returned, destroy_key_fn is run on the pointer
125 : * to the key and destroy_value_fn is run on the pointer to the value.
126 : * Either or both may be NULL if a callback is not desired in this case.
127 : */
128 : AWS_COMMON_API
129 : int aws_hash_table_init(
130 : struct aws_hash_table *map,
131 : struct aws_allocator *alloc,
132 : size_t size,
133 : aws_hash_fn *hash_fn,
134 : aws_hash_callback_eq_fn *equals_fn,
135 : aws_hash_callback_destroy_fn *destroy_key_fn,
136 : aws_hash_callback_destroy_fn *destroy_value_fn);
137 :
138 : /**
139 : * Deletes every element from map and frees all associated memory.
140 : * destroy_fn will be called for each element. aws_hash_table_init
141 : * must be called before reusing the hash table.
142 : *
143 : * This method is idempotent.
144 : */
145 : AWS_COMMON_API
146 : void aws_hash_table_clean_up(struct aws_hash_table *map);
147 :
148 : /**
149 : * Safely swaps two hash tables. Note that we swap the entirety of the hash
150 : * table, including which allocator is associated.
151 : *
152 : * Neither hash table is required to be initialized; if one or both is
153 : * uninitialized, then the uninitialized state is also swapped.
154 : */
155 : AWS_COMMON_API
156 : void aws_hash_table_swap(struct aws_hash_table *AWS_RESTRICT a, struct aws_hash_table *AWS_RESTRICT b);
157 :
158 : /**
159 : * Moves the hash table in 'from' to 'to'. After this move, 'from' will
160 : * be identical to the state of the original 'to' hash table, and 'to'
161 : * will be in the same state as if it had been passed to aws_hash_table_clean_up
162 : * (that is, it will have no memory allocated, and it will be safe to
163 : * either discard it or call aws_hash_table_clean_up again).
164 : *
165 : * Note that 'to' will not be cleaned up. You should make sure that 'to'
166 : * is either uninitialized or cleaned up before moving a hashtable into
167 : * it.
168 : */
169 : AWS_COMMON_API
170 : void aws_hash_table_move(struct aws_hash_table *AWS_RESTRICT to, struct aws_hash_table *AWS_RESTRICT from);
171 :
172 : /**
173 : * Returns the current number of entries in the table.
174 : */
175 : AWS_COMMON_API
176 : size_t aws_hash_table_get_entry_count(const struct aws_hash_table *map);
177 :
178 : /**
179 : * Returns an iterator to be used for iterating through a hash table.
180 : * Iterator will already point to the first element of the table it finds,
181 : * which can be accessed as iter.element.
182 : *
183 : * This function cannot fail, but if there are no elements in the table,
184 : * the returned iterator will return true for aws_hash_iter_done(&iter).
185 : */
186 : AWS_COMMON_API
187 : struct aws_hash_iter aws_hash_iter_begin(const struct aws_hash_table *map);
188 :
189 : /**
190 : * Returns true if iterator is done iterating through table, false otherwise.
191 : * If this is true, the iterator will not include an element of the table.
192 : */
193 : AWS_COMMON_API
194 : bool aws_hash_iter_done(const struct aws_hash_iter *iter);
195 :
196 : /**
197 : * Updates iterator so that it points to next element of hash table.
198 : *
199 : * This and the two previous functions are designed to be used together with
200 : * the following idiom:
201 : *
202 : * for (struct aws_hash_iter iter = aws_hash_iter_begin(&map);
203 : * !aws_hash_iter_done(&iter); aws_hash_iter_next(&iter)) {
204 : * const key_type key = *(const key_type *)iter.element.key;
205 : * value_type value = *(value_type *)iter.element.value;
206 : * // etc.
207 : * }
208 : *
209 : * Note that calling this on an iter which is "done" is idempotent:
210 : * i.e. it will return another iter which is "done".
211 : */
212 : AWS_COMMON_API
213 : void aws_hash_iter_next(struct aws_hash_iter *iter);
214 :
215 : /**
216 : * Deletes the element currently pointed-to by the hash iterator.
217 : * After calling this method, the element member of the iterator
218 : * should not be accessed until the next call to aws_hash_iter_next.
219 : *
220 : * @param destroy_contents If true, the destructors for the key and value
221 : * will be called.
222 : */
223 : AWS_COMMON_API
224 : void aws_hash_iter_delete(struct aws_hash_iter *iter, bool destroy_contents);
225 :
226 : /**
227 : * Attempts to locate an element at key. If the element is found, a
228 : * pointer to the value is placed in *p_elem; if it is not found,
229 : * *pElem is set to NULL. Either way, AWS_OP_SUCCESS is returned.
230 : *
231 : * This method does not change the state of the hash table. Therefore, it
232 : * is safe to call _find from multiple threads on the same hash table,
233 : * provided no mutating operations happen in parallel.
234 : *
235 : * Calling code may update the value in the hash table by modifying **pElem
236 : * after a successful find. However, this pointer is not guaranteed to
237 : * remain usable after a subsequent call to _put, _delete, _clear, or
238 : * _clean_up.
239 : */
240 :
241 : AWS_COMMON_API
242 : int aws_hash_table_find(const struct aws_hash_table *map, const void *key, struct aws_hash_element **p_elem);
243 :
244 : /**
245 : * Attempts to locate an element at key. If no such element was found,
246 : * creates a new element, with value initialized to NULL. In either case, a
247 : * pointer to the element is placed in *p_elem.
248 : *
249 : * If was_created is non-NULL, *was_created is set to 0 if an existing
250 : * element was found, or 1 is a new element was created.
251 : *
252 : * Returns AWS_OP_SUCCESS if an item was found or created.
253 : * Raises AWS_ERROR_OOM if hash table expansion was required and memory
254 : * allocation failed.
255 : */
256 : AWS_COMMON_API
257 : int aws_hash_table_create(
258 : struct aws_hash_table *map,
259 : const void *key,
260 : struct aws_hash_element **p_elem,
261 : int *was_created);
262 :
263 : /**
264 : * Inserts a new element at key, with the given value. If another element
265 : * exists at that key, the old element will be overwritten; both old key and
266 : * value objects will be destroyed.
267 : *
268 : * If was_created is non-NULL, *was_created is set to 0 if an existing
269 : * element was found, or 1 is a new element was created.
270 : *
271 : * Returns AWS_OP_SUCCESS if an item was found or created.
272 : * Raises AWS_ERROR_OOM if hash table expansion was required and memory
273 : */
274 : AWS_COMMON_API
275 : int aws_hash_table_put(struct aws_hash_table *map, const void *key, void *value, int *was_created);
276 :
277 : /**
278 : * Removes element at key. Always returns AWS_OP_SUCCESS.
279 : *
280 : * If pValue is non-NULL, the existing value (if any) is moved into
281 : * (*value) before removing from the table, and destroy_fn is _not_
282 : * invoked. If pValue is NULL, then (if the element existed) destroy_fn
283 : * will be invoked on the element being removed.
284 : *
285 : * If was_present is non-NULL, it is set to 0 if the element was
286 : * not present, or 1 if it was present (and is now removed).
287 : */
288 : AWS_COMMON_API
289 : int aws_hash_table_remove(
290 : struct aws_hash_table *map,
291 : const void *key,
292 : struct aws_hash_element *p_value,
293 : int *was_present);
294 :
295 : /**
296 : * Removes element already known (typically by find()).
297 : *
298 : * p_value should point to a valid element returned by create() or find().
299 : *
300 : * NOTE: DO NOT call this method from inside of a aws_hash_table_foreach callback, return
301 : * AWS_COMMON_HASH_TABLE_ITER_DELETE instead.
302 : */
303 : AWS_COMMON_API
304 : int aws_hash_table_remove_element(struct aws_hash_table *map, struct aws_hash_element *p_value);
305 :
306 : /**
307 : * Iterates through every element in the map and invokes the callback on
308 : * that item. Iteration is performed in an arbitrary, implementation-defined
309 : * order, and is not guaranteed to be consistent across invocations.
310 : *
311 : * The callback may change the value associated with the key by overwriting
312 : * the value pointed-to by value. In this case, the on_element_removed
313 : * callback will not be invoked, unless the callback invokes
314 : * AWS_COMMON_HASH_TABLE_ITER_DELETE (in which case the on_element_removed
315 : * is given the updated value).
316 : *
317 : * The callback must return a bitmask of zero or more of the following values
318 : * ORed together:
319 : *
320 : * # AWS_COMMON_HASH_TABLE_ITER_CONTINUE - Continues iteration to the next
321 : * element (if not set, iteration stops)
322 : * # AWS_COMMON_HASH_TABLE_ITER_DELETE - Deletes the current value and
323 : * continues iteration. destroy_fn will NOT be invoked.
324 : *
325 : * Invoking any method which may change the contents of the hashtable
326 : * during iteration results in undefined behavior. However, you may safely
327 : * invoke non-mutating operations during an iteration.
328 : *
329 : * This operation is mutating only if AWS_COMMON_HASH_TABLE_ITER_DELETE
330 : * is returned at some point during iteration. Otherwise, it is non-mutating
331 : * and is safe to invoke in parallel with other non-mutating operations.
332 : */
333 :
334 : AWS_COMMON_API
335 : int aws_hash_table_foreach(
336 : struct aws_hash_table *map,
337 : int (*callback)(void *context, struct aws_hash_element *p_element),
338 : void *context);
339 :
340 : /**
341 : * Compares two hash tables for equality. Both hash tables must have equivalent
342 : * key comparators; values will be compared using the comparator passed into this
343 : * function. The key hash function does not need to be equivalent between the
344 : * two hash tables.
345 : */
346 : AWS_COMMON_API
347 : bool aws_hash_table_eq(
348 : const struct aws_hash_table *a,
349 : const struct aws_hash_table *b,
350 : aws_hash_callback_eq_fn *value_eq);
351 :
352 : /**
353 : * Removes every element from the hash map. destroy_fn will be called for
354 : * each element.
355 : */
356 : AWS_COMMON_API
357 : void aws_hash_table_clear(struct aws_hash_table *map);
358 :
359 : /**
360 : * Convenience hash function for NULL-terminated C-strings
361 : */
362 : AWS_COMMON_API
363 : uint64_t aws_hash_c_string(const void *item);
364 :
365 : /**
366 : * Convenience hash function for struct aws_strings.
367 : * Hash is same as used on the string bytes by aws_hash_c_string.
368 : */
369 : AWS_COMMON_API
370 : uint64_t aws_hash_string(const void *item);
371 :
372 : /**
373 : * Convenience hash function for struct aws_byte_cursor.
374 : * Hash is same as used on the string bytes by aws_hash_c_string.
375 : */
376 : AWS_COMMON_API
377 : uint64_t aws_hash_byte_cursor_ptr(const void *item);
378 :
379 : /**
380 : * Convenience hash function which hashes the pointer value directly,
381 : * without dereferencing. This can be used in cases where pointer identity
382 : * is desired, or where a uintptr_t is encoded into a const void *.
383 : */
384 : AWS_COMMON_API
385 : uint64_t aws_hash_ptr(const void *item);
386 :
387 : AWS_COMMON_API
388 : uint64_t aws_hash_combine(uint64_t item1, uint64_t item2);
389 :
390 : /**
391 : * Convenience eq callback for NULL-terminated C-strings
392 : */
393 : AWS_COMMON_API
394 : bool aws_hash_callback_c_str_eq(const void *a, const void *b);
395 :
396 : /**
397 : * Convenience eq callback for AWS strings
398 : */
399 : AWS_COMMON_API
400 : bool aws_hash_callback_string_eq(const void *a, const void *b);
401 :
402 : /**
403 : * Convenience destroy callback for AWS strings
404 : */
405 : AWS_COMMON_API
406 : void aws_hash_callback_string_destroy(void *a);
407 :
408 : /**
409 : * Equality function which compares pointer equality.
410 : */
411 : AWS_COMMON_API
412 : bool aws_ptr_eq(const void *a, const void *b);
413 :
414 : /**
415 : * Best-effort check of hash_table_state data-structure invariants
416 : */
417 : AWS_COMMON_API
418 : bool aws_hash_table_is_valid(const struct aws_hash_table *map);
419 :
420 : /**
421 : * Given a pointer to a hash_iter, checks that it is well-formed, with all data-structure invariants.
422 : */
423 : AWS_COMMON_API
424 : bool aws_hash_iter_is_valid(const struct aws_hash_iter *iter);
425 :
426 : AWS_EXTERN_C_END
427 :
428 : #endif /* AWS_COMMON_HASH_TABLE_H */
|
