1 | #ifndef AWS_COMMON_PRIVATE_HASH_TABLE_IMPL_H |
2 | #define AWS_COMMON_PRIVATE_HASH_TABLE_IMPL_H |
3 | |
4 | /* |
5 | * Copyright 2010-2019 Amazon.com, Inc. or its affiliates. All Rights Reserved. |
6 | * |
7 | * Licensed under the Apache License, Version 2.0 (the "License"). |
8 | * You may not use this file except in compliance with the License. |
9 | * A copy of the License is located at |
10 | * |
11 | * http://aws.amazon.com/apache2.0 |
12 | * |
13 | * or in the "license" file accompanying this file. This file is distributed |
14 | * on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either |
15 | * express or implied. See the License for the specific language governing |
16 | * permissions and limitations under the License. |
17 | */ |
18 | |
19 | #include <aws/common/common.h> |
20 | #include <aws/common/hash_table.h> |
21 | #include <aws/common/math.h> |
22 | |
23 | struct hash_table_entry { |
24 | struct aws_hash_element element; |
25 | uint64_t hash_code; /* hash code (0 signals empty) */ |
26 | }; |
27 | |
28 | /* Using a flexible array member is the C99 compliant way to have the hash_table_entries |
29 | * immediatly follow the struct. |
30 | * |
31 | * MSVC doesn't know this for some reason so we need to use a pragma to make |
32 | * it happy. |
33 | */ |
34 | #ifdef _MSC_VER |
35 | # pragma warning(push) |
36 | # pragma warning(disable : 4200) |
37 | #endif |
38 | struct hash_table_state { |
39 | aws_hash_fn *hash_fn; |
40 | aws_hash_callback_eq_fn *equals_fn; |
41 | aws_hash_callback_destroy_fn *destroy_key_fn; |
42 | aws_hash_callback_destroy_fn *destroy_value_fn; |
43 | struct aws_allocator *alloc; |
44 | |
45 | size_t size, entry_count; |
46 | size_t max_load; |
47 | /* We AND a hash value with mask to get the slot index */ |
48 | size_t mask; |
49 | double max_load_factor; |
50 | /* actually variable length */ |
51 | struct hash_table_entry slots[]; |
52 | }; |
53 | #ifdef _MSC_VER |
54 | # pragma warning(pop) |
55 | #endif |
56 | |
57 | /** |
58 | * Best-effort check of hash_table_state data-structure invariants |
59 | * Some invariants, such as that the number of entries is actually the |
60 | * same as the entry_count field, would require a loop to check |
61 | */ |
62 | bool hash_table_state_is_valid(const struct hash_table_state *map); |
63 | |
64 | /** |
65 | * Determine the total number of bytes needed for a hash-table with |
66 | * "size" slots. If the result would overflow a size_t, return |
67 | * AWS_OP_ERR; otherwise, return AWS_OP_SUCCESS with the result in |
68 | * "required_bytes". |
69 | */ |
70 | int hash_table_state_required_bytes(size_t size, size_t *required_bytes); |
71 | |
72 | #endif /* AWS_COMMON_PRIVATE_HASH_TABLE_IMPL_H */ |
73 | |