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
23struct 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
38struct 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 */
62bool 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 */
70int hash_table_state_required_bytes(size_t size, size_t *required_bytes);
71
72#endif /* AWS_COMMON_PRIVATE_HASH_TABLE_IMPL_H */
73