Version bump to 5.9.4
[strongswan.git] / src / libstrongswan / collections / hashtable.h
1 /*
2 * Copyright (C) 2008-2020 Tobias Brunner
3 * HSR Hochschule fuer Technik Rapperswil
4 *
5 * This program is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License as published by the
7 * Free Software Foundation; either version 2 of the License, or (at your
8 * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>.
9 *
10 * This program is distributed in the hope that it will be useful, but
11 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
12 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13 * for more details.
14 */
15
16 /**
17 * @defgroup hashtable hashtable
18 * @{ @ingroup collections
19 */
20
21 #ifndef HASHTABLE_H_
22 #define HASHTABLE_H_
23
24 #include <collections/enumerator.h>
25
26 typedef struct hashtable_t hashtable_t;
27 typedef struct hashlist_t hashlist_t;
28
29 /**
30 * Prototype for a function that computes the hash code from the given key.
31 *
32 * @param key key to hash
33 * @return hash code
34 */
35 typedef u_int (*hashtable_hash_t)(const void *key);
36
37 /**
38 * Hashtable hash function calculation the hash solely based on the key pointer.
39 *
40 * @param key key to hash
41 * @return hash of key
42 */
43 u_int hashtable_hash_ptr(const void *key);
44
45 /**
46 * Hashtable hash function calculation the hash for char* keys.
47 *
48 * @param key key to hash, a char*
49 * @return hash of key
50 */
51 u_int hashtable_hash_str(const void *key);
52
53 /**
54 * Prototype for a function that compares the two keys for equality.
55 *
56 * @param key first key (the one we are looking for/inserting)
57 * @param other_key second key
58 * @return TRUE if the keys are equal
59 */
60 typedef bool (*hashtable_equals_t)(const void *key, const void *other_key);
61
62 /**
63 * Hashtable equals function comparing pointers.
64 *
65 * @param key key to compare
66 * @param other_key other key to compare
67 * @return TRUE if key == other_key
68 */
69 bool hashtable_equals_ptr(const void *key, const void *other_key);
70
71 /**
72 * Hashtable equals function comparing char* keys.
73 *
74 * @param key key to compare
75 * @param other_key other key to compare
76 * @return TRUE if streq(key, other_key)
77 */
78 bool hashtable_equals_str(const void *key, const void *other_key);
79
80 /**
81 * Prototype for a function that compares the two keys in order to sort them.
82 *
83 * @param key first key (the one we are looking for/inserting)
84 * @param other_key second key
85 * @return less than, equal to, or greater than 0 if key is
86 * less than, equal to, or greater than other_key
87 */
88 typedef int (*hashtable_cmp_t)(const void *key, const void *other_key);
89
90 /**
91 * Class implementing a hash table.
92 *
93 * General purpose hash table. This hash table is not synchronized.
94 *
95 * The insertion order is maintained when enumerating entries.
96 */
97 struct hashtable_t {
98
99 /**
100 * Create an enumerator over the hash table key/value pairs.
101 *
102 * @return enumerator over (void *key, void *value)
103 */
104 enumerator_t *(*create_enumerator)(hashtable_t *this);
105
106 /**
107 * Adds the given value with the given key to the hash table, if there
108 * exists no entry with that key. NULL is returned in this case.
109 * Otherwise the existing value is replaced and the function returns the
110 * old value.
111 *
112 * @param key the key to store
113 * @param value the value to store
114 * @return NULL if no item was replaced, the old value otherwise
115 */
116 void *(*put)(hashtable_t *this, const void *key, void *value);
117
118 /**
119 * Returns the value with the given key, if the hash table contains such an
120 * entry, otherwise NULL is returned.
121 *
122 * @param key the key of the requested value
123 * @return the value, NULL if not found
124 */
125 void *(*get)(hashtable_t *this, const void *key);
126
127 /**
128 * Removes the value with the given key from the hash table and returns the
129 * removed value (or NULL if no such value existed).
130 *
131 * @param key the key of the value to remove
132 * @return the removed value, NULL if not found
133 */
134 void *(*remove)(hashtable_t *this, const void *key);
135
136 /**
137 * Removes the key and value pair from the hash table at which the given
138 * enumerator currently points.
139 *
140 * @param enumerator enumerator, from create_enumerator
141 */
142 void (*remove_at)(hashtable_t *this, enumerator_t *enumerator);
143
144 /**
145 * Gets the number of items in the hash table.
146 *
147 * @return number of items
148 */
149 u_int (*get_count)(hashtable_t *this);
150
151 /**
152 * Destroys a hash table object.
153 */
154 void (*destroy)(hashtable_t *this);
155
156 /**
157 * Destroys a hash table object and calls the given function for each
158 * item and its key in the hash table.
159 *
160 * @param function function to call on each item and key
161 */
162 void (*destroy_function)(hashtable_t *this,
163 void (*)(void *val, const void *key));
164 };
165
166 /**
167 * Class implementing a hash table with ordered keys/items and special query
168 * method.
169 *
170 * @note The ordering only pertains to keys/items in the same bucket (with or
171 * without the same hash value), not to the order when enumerating. So unlike
172 * hashtable_t this class does not guarantee any specific order when enumerating
173 * all entries.
174 *
175 * This is intended to be used with hash functions that intentionally return the
176 * same hash value for different keys so multiple items can be retrieved for a
177 * key.
178 *
179 * It's like storing sorted linked lists in a hash table but with less overhead.
180 */
181 struct hashlist_t {
182
183 /**
184 * Implements the hash table interface.
185 */
186 hashtable_t ht;
187
188 /**
189 * Returns the first value with a matching key if the hash table contains
190 * such an entry, otherwise NULL is returned.
191 *
192 * Compared to get() the given match function is used to compare the keys
193 * for equality. The hash function does have to be devised specially in
194 * order to make this work if the match function compares keys differently
195 * than the equals/comparison function provided to the constructor.
196 *
197 * This basically allows to enumerate all entries with the same hash value
198 * in their key's order (insertion order, i.e. without comparison function)
199 * is only guaranteed for items with the same hash value.
200 *
201 * @param key the key to match against
202 * @param match match function to be used when comparing keys
203 * @return the value, NULL if not found
204 */
205 void *(*get_match)(hashlist_t *this, const void *key,
206 hashtable_equals_t match);
207
208 /**
209 * Destroys a hash list object.
210 */
211 void (*destroy)(hashlist_t *this);
212 };
213
214 /**
215 * Creates an empty hash table object.
216 *
217 * @param hash hash function
218 * @param equals equals function
219 * @param size initial size
220 * @return hashtable_t object
221 */
222 hashtable_t *hashtable_create(hashtable_hash_t hash, hashtable_equals_t equals,
223 u_int size);
224
225 /**
226 * Creates an empty hash list object with each bucket's keys in insertion order.
227 *
228 * @param hash hash function
229 * @param equals equals function
230 * @param size initial size
231 * @return hashtable_t object
232 */
233 hashlist_t *hashlist_create(hashtable_hash_t hash, hashtable_equals_t equals,
234 u_int size);
235
236 /**
237 * Creates an empty hash list object with sorted keys in each bucket.
238 *
239 * @param hash hash function
240 * @param cmp comparison function
241 * @param size initial size
242 * @return hashtable_t object.
243 */
244 hashlist_t *hashlist_create_sorted(hashtable_hash_t hash,
245 hashtable_cmp_t cmp, u_int size);
246
247 #endif /** HASHTABLE_H_ @}*/