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