1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
|
/* MIT License
*
* Copyright (c) 2023 Brad House
*
* Permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and associated documentation files (the "Software"), to deal
* in the Software without restriction, including without limitation the rights
* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the Software is
* furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice (including the next
* paragraph) shall be included in all copies or substantial portions of the
* Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
* SOFTWARE.
*
* SPDX-License-Identifier: MIT
*/
#ifndef __ARES__HTABLE_H
#define __ARES__HTABLE_H
/*! \addtogroup ares__htable Base HashTable Data Structure
*
* This is a basic hashtable data structure that is meant to be wrapped
* by a higher level implementation. This data structure is designed to
* be callback-based in order to facilitate wrapping without needing to
* worry about any underlying complexities of the hashtable implementation.
*
* This implementation supports automatic growing by powers of 2 when reaching
* 75% capacity. A rehash will be performed on the expanded bucket list.
*
* Average time complexity:
* - Insert: O(1)
* - Search: O(1)
* - Delete: O(1)
*
* @{
*/
struct ares__htable;
/*! Opaque data type for generic hash table implementation */
typedef struct ares__htable ares__htable_t;
/*! Callback for generating a hash of the key.
*
* \param[in] key pointer to key to be hashed
* \param[in] seed randomly generated seed used by hash function.
* value is specific to the hashtable instance
* but otherwise will not change between calls.
* \return hash
*/
typedef unsigned int (*ares__htable_hashfunc_t)(const void *key,
unsigned int seed);
/*! Callback to free the bucket
*
* \param[in] bucket user provided bucket
*/
typedef void (*ares__htable_bucket_free_t)(void *bucket);
/*! Callback to extract the key from the user-provided bucket
*
* \param[in] bucket user provided bucket
* \return pointer to key held in bucket
*/
typedef const void *(*ares__htable_bucket_key_t)(const void *bucket);
/*! Callback to compare two keys for equality
*
* \param[in] key1 first key
* \param[in] key2 second key
* \return ARES_TRUE if equal, ARES_FALSE if not
*/
typedef ares_bool_t (*ares__htable_key_eq_t)(const void *key1,
const void *key2);
/*! Destroy the initialized hashtable
*
* \param[in] htable initialized hashtable
*/
void ares__htable_destroy(ares__htable_t *htable);
/*! Create a new hashtable
*
* \param[in] hash_func Required. Callback for Hash function.
* \param[in] bucket_key Required. Callback to extract key from bucket.
* \param[in] bucket_free Required. Callback to free bucket.
* \param[in] key_eq Required. Callback to check for key equality.
* \return initialized hashtable. NULL if out of memory or misuse.
*/
ares__htable_t *ares__htable_create(ares__htable_hashfunc_t hash_func,
ares__htable_bucket_key_t bucket_key,
ares__htable_bucket_free_t bucket_free,
ares__htable_key_eq_t key_eq);
/*! Count of keys from initialized hashtable
*
* \param[in] htable Initialized hashtable.
* \return count of keys
*/
size_t ares__htable_num_keys(const ares__htable_t *htable);
/*! Retrieve an array of buckets from the hashtable. This is mainly used as
* a helper for retrieving an array of keys.
*
* \param[in] htable Initialized hashtable
* \param[out] num Count of returned buckets
* \return Array of pointers to the buckets. These are internal pointers
* to data within the hashtable, so if the key is removed, there
* will be a dangling pointer. It is expected wrappers will make
* such values safe by duplicating them.
*/
const void **ares__htable_all_buckets(const ares__htable_t *htable,
size_t *num);
/*! Insert bucket into hashtable
*
* \param[in] htable Initialized hashtable.
* \param[in] bucket User-provided bucket to insert. Takes "ownership". Not
* allowed to be NULL.
* \return ARES_TRUE on success, ARES_FALSE if out of memory
*/
ares_bool_t ares__htable_insert(ares__htable_t *htable, void *bucket);
/*! Retrieve bucket from hashtable based on key.
*
* \param[in] htable Initialized hashtable
* \param[in] key Pointer to key to use for comparison.
* \return matching bucket, or NULL if not found.
*/
void *ares__htable_get(const ares__htable_t *htable, const void *key);
/*! Remove bucket from hashtable by key
*
* \param[in] htable Initialized hashtable
* \param[in] key Pointer to key to use for comparison
* \return ARES_TRUE if found, ARES_FALSE if not found
*/
ares_bool_t ares__htable_remove(ares__htable_t *htable, const void *key);
/*! FNV1a hash algorithm. Can be used as underlying primitive for building
* a wrapper hashtable.
*
* \param[in] key pointer to key
* \param[in] key_len Length of key
* \param[in] seed Seed for generating hash
* \return hash value
*/
unsigned int ares__htable_hash_FNV1a(const unsigned char *key, size_t key_len,
unsigned int seed);
/*! FNV1a hash algorithm, but converts all characters to lowercase before
* hashing to make the hash case-insensitive. Can be used as underlying
* primitive for building a wrapper hashtable. Used on string-based keys.
*
* \param[in] key pointer to key
* \param[in] key_len Length of key
* \param[in] seed Seed for generating hash
* \return hash value
*/
unsigned int ares__htable_hash_FNV1a_casecmp(const unsigned char *key,
size_t key_len, unsigned int seed);
/*! @} */
#endif /* __ARES__HTABLE_H */
|
