1 /* Abstract map data type.
2 Copyright (C) 2006-2007, 2009-2023 Free Software Foundation, Inc.
3 Written by Bruno Haible <bruno@clisp.org>, 2018.
4
5 This program is free software: you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation, either version 3 of the License, or
8 (at your option) any later version.
9
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see <https://www.gnu.org/licenses/>. */
17
18 #ifndef _GL_MAP_H
19 #define _GL_MAP_H
20
21 /* This file uses _GL_INLINE_HEADER_BEGIN, _GL_INLINE,
22 _GL_ATTRIBUTE_NODISCARD. */
23 #if !_GL_CONFIG_H_INCLUDED
24 #error "Please include config.h first."
25 #endif
26
27 #include <stddef.h>
28
29 _GL_INLINE_HEADER_BEGIN
30 #ifndef GL_MAP_INLINE
31 # define GL_MAP_INLINE _GL_INLINE
32 #endif
33
34 #ifdef __cplusplus
35 extern "C" {
36 #endif
37
38
39 /* gl_map is an abstract map data type. It can contain any number of
40 (key, value) pairs, where
41 - keys and values are objects ('void *' or 'const void *' pointers),
42 - There are no (key, value1) and (key, value2) pairs with the same key
43 (in the sense of a given comparator function).
44
45 There are several implementations of this map datatype, optimized for
46 different operations or for memory. You can start using the simplest map
47 implementation, GL_ARRAY_MAP, and switch to a different implementation
48 later, when you realize which operations are performed the most frequently.
49 The API of the different implementations is exactly the same; when switching
50 to a different implementation, you only have to change the gl_map_create
51 call.
52
53 The implementations are:
54 GL_ARRAY_MAP a growable array
55 GL_LINKEDHASH_MAP a hash table with a linked list
56 GL_HASH_MAP a hash table
57
58 The memory consumption is asymptotically the same: O(1) for every pair
59 in the map. When looking more closely at the average memory consumed
60 for an object, GL_ARRAY_MAP is the most compact representation, then comes
61 GL_HASH_MAP, and GL_LINKEDHASH_MAP needs the most memory.
62
63 The guaranteed average performance of the operations is, for a map of
64 n pairs:
65
66 Operation ARRAY LINKEDHASH
67 HASH
68
69 gl_map_size O(1) O(1)
70 gl_map_get O(n) O(1)
71 gl_map_put O(n) O(1)
72 gl_map_remove O(n) O(1)
73 gl_map_search O(n) O(1)
74 gl_map_iterator O(1) O(1)
75 gl_map_iterator_next O(1) O(1)
76 */
77
78 /* --------------------------- gl_map_t Data Type --------------------------- */
79
80 /* Type of function used to compare two keys.
81 NULL denotes pointer comparison. */
82 typedef bool (*gl_mapkey_equals_fn) (const void *key1, const void *key2);
83
84 /* Type of function used to compute a hash code.
85 NULL denotes a function that depends only on the pointer itself. */
86 typedef size_t (*gl_mapkey_hashcode_fn) (const void *key);
87
88 #ifndef _GL_MAP_DISPOSE_FNS_DEFINED
89
90 /* Type of function used to dispose a key once a (key, value) pair is removed
91 from a map. NULL denotes a no-op. */
92 typedef void (*gl_mapkey_dispose_fn) (const void *key);
93
94 /* Type of function used to dispose a value once a (key, value) pair is removed
95 from a map. NULL denotes a no-op. */
96 typedef void (*gl_mapvalue_dispose_fn) (const void *value);
97
98 # define _GL_MAP_DISPOSE_FNS_DEFINED 1
99 #endif
100
101 struct gl_map_impl;
102 /* Type representing an entire map. */
103 typedef struct gl_map_impl * gl_map_t;
104
105 struct gl_map_implementation;
106 /* Type representing a map datatype implementation. */
107 typedef const struct gl_map_implementation * gl_map_implementation_t;
108
109 #if 0 /* Unless otherwise specified, these are defined inline below. */
110
111 /* Creates an empty map.
112 IMPLEMENTATION is one of GL_ARRAY_MAP, GL_LINKEDHASH_MAP, GL_HASH_MAP.
113 EQUALS_FN is a key comparison function or NULL.
114 HASHCODE_FN is a key hash code function or NULL.
115 KDISPOSE_FN is a key disposal function or NULL.
116 VDISPOSE_FN is a value disposal function or NULL. */
117 /* declared in gl_xmap.h */
118 extern gl_map_t gl_map_create_empty (gl_map_implementation_t implementation,
119 gl_mapkey_equals_fn equals_fn,
120 gl_mapkey_hashcode_fn hashcode_fn,
121 gl_mapkey_dispose_fn kdispose_fn,
122 gl_mapvalue_dispose_fn vdispose_fn)
123 /*_GL_ATTRIBUTE_DEALLOC (gl_map_free, 1)*/
124 _GL_ATTRIBUTE_RETURNS_NONNULL;
125 /* Likewise. Returns NULL upon out-of-memory. */
126 extern gl_map_t gl_map_nx_create_empty (gl_map_implementation_t implementation,
127 gl_mapkey_equals_fn equals_fn,
128 gl_mapkey_hashcode_fn hashcode_fn,
129 gl_mapkey_dispose_fn kdispose_fn,
130 gl_mapvalue_dispose_fn vdispose_fn)
131 /*_GL_ATTRIBUTE_DEALLOC (gl_map_free, 1)*/;
132
133 /* Returns the current number of pairs in a map. */
134 extern size_t gl_map_size (gl_map_t map);
135
136 /* Searches whether a pair with the given key is already in the map.
137 Returns the value if found, or NULL if not present in the map. */
138 extern const void * gl_map_get (gl_map_t map, const void *key);
139
140 /* Searches whether a pair with the given key is already in the map.
141 Returns true and sets *VALUEP to the value if found.
142 Returns false if not present in the map. */
143 extern bool gl_map_search (gl_map_t map, const void *key, const void **valuep);
144
145 /* Adds a pair to a map.
146 Returns true if a pair with the given key was not already in the map and so
147 this pair was added.
148 Returns false if a pair with the given key was already in the map and only
149 its value was replaced. */
150 /* declared in gl_xmap.h */
151 extern bool gl_map_put (gl_map_t map, const void *key, const void *value);
152 /* Likewise. Returns -1 upon out-of-memory. */
153 _GL_ATTRIBUTE_NODISCARD
154 extern int gl_map_nx_put (gl_map_t map, const void *key, const void *value);
155
156 /* Adds a pair to a map and retrieves the previous value.
157 Returns true if a pair with the given key was not already in the map and so
158 this pair was added.
159 Returns false and sets *OLDVALUEP to the previous value, if a pair with the
160 given key was already in the map and only its value was replaced. */
161 /* declared in gl_xmap.h */
162 extern bool gl_map_getput (gl_map_t map, const void *key, const void *value,
163 const void **oldvaluep);
164 /* Likewise. Returns -1 upon out-of-memory. */
165 _GL_ATTRIBUTE_NODISCARD
166 extern int gl_map_nx_getput (gl_map_t map, const void *key, const void *value,
167 const void **oldvaluep);
168
169 /* Removes a pair from a map.
170 Returns true if the key was found and its pair removed.
171 Returns false otherwise. */
172 extern bool gl_map_remove (gl_map_t map, const void *key);
173
174 /* Removes a pair from a map and retrieves the previous value.
175 Returns true and sets *OLDVALUEP to the previous value, if the key was found
176 and its pair removed.
177 Returns false otherwise. */
178 extern bool gl_map_getremove (gl_map_t map, const void *key,
179 const void **oldvaluep);
180
181 /* Frees an entire map.
182 (But this call does not free the keys and values of the pairs in the map.
183 It only invokes the KDISPOSE_FN on each key and the VDISPOSE_FN on each value
184 of the pairs in the map.) */
185 extern void gl_map_free (gl_map_t map);
186
187 #endif /* End of inline and gl_xmap.h-defined functions. */
188
189 /* ---------------------- gl_map_iterator_t Data Type ---------------------- */
190
191 /* Functions for iterating through a map.
192 Note: Iterating through a map of type GL_HASH_MAP returns the pairs in an
193 unpredictable order. If you need a predictable order, use GL_LINKEDHASH_MAP
194 instead of GL_HASH_MAP. */
195
196 /* Type of an iterator that traverses a map.
197 This is a fixed-size struct, so that creation of an iterator doesn't need
198 memory allocation on the heap. */
199 typedef struct
200 {
201 /* For fast dispatch of gl_map_iterator_next. */
202 const struct gl_map_implementation *vtable;
203 /* For detecting whether the last returned pair was removed. */
204 gl_map_t map;
205 size_t count;
206 /* Other, implementation-private fields. */
207 void *p; void *q;
208 size_t i; size_t j;
209 } gl_map_iterator_t;
210
211 #if 0 /* These are defined inline below. */
212
213 /* Creates an iterator traversing a map.
214 The map's contents must not be modified while the iterator is in use,
215 except for modifying the value of the last returned key or removing the
216 last returned pair. */
217 extern gl_map_iterator_t gl_map_iterator (gl_map_t map);
218
219 /* If there is a next pair, stores the next pair in *KEYP and *VALUEP, advances
220 the iterator, and returns true. Otherwise, returns false. */
221 extern bool gl_map_iterator_next (gl_map_iterator_t *iterator,
222 const void **keyp, const void **valuep);
223
224 /* Frees an iterator. */
225 extern void gl_map_iterator_free (gl_map_iterator_t *iterator);
226
227 #endif /* End of inline functions. */
228
229 /* ------------------------- Implementation Details ------------------------- */
230
231 struct gl_map_implementation
232 {
233 /* gl_map_t functions. */
234 gl_map_t (*nx_create_empty) (gl_map_implementation_t implementation,
235 gl_mapkey_equals_fn equals_fn,
236 gl_mapkey_hashcode_fn hashcode_fn,
237 gl_mapkey_dispose_fn kdispose_fn,
238 gl_mapvalue_dispose_fn vdispose_fn);
239 size_t (*size) (gl_map_t map);
240 bool (*search) (gl_map_t map, const void *key, const void **valuep);
241 int (*nx_getput) (gl_map_t map, const void *key, const void *value,
242 const void **oldvaluep);
243 bool (*getremove) (gl_map_t map, const void *key, const void **oldvaluep);
244 void (*map_free) (gl_map_t map);
245 /* gl_map_iterator_t functions. */
246 gl_map_iterator_t (*iterator) (gl_map_t map);
247 bool (*iterator_next) (gl_map_iterator_t *iterator,
248 const void **keyp, const void **valuep);
249 void (*iterator_free) (gl_map_iterator_t *iterator);
250 };
251
252 struct gl_map_impl_base
253 {
254 const struct gl_map_implementation *vtable;
255 gl_mapkey_equals_fn equals_fn;
256 gl_mapkey_dispose_fn kdispose_fn;
257 gl_mapvalue_dispose_fn vdispose_fn;
258 };
259
260 /* Define most functions of this file as accesses to the
261 struct gl_map_implementation. */
262
263 GL_MAP_INLINE
264 /*_GL_ATTRIBUTE_DEALLOC (gl_map_free, 1)*/
265 gl_map_t
266 gl_map_nx_create_empty (gl_map_implementation_t implementation,
267 gl_mapkey_equals_fn equals_fn,
268 gl_mapkey_hashcode_fn hashcode_fn,
269 gl_mapkey_dispose_fn kdispose_fn,
270 gl_mapvalue_dispose_fn vdispose_fn)
271 {
272 return implementation->nx_create_empty (implementation,
273 equals_fn, hashcode_fn,
274 kdispose_fn, vdispose_fn);
275 }
276
277 GL_MAP_INLINE size_t
278 gl_map_size (gl_map_t map)
279 {
280 return ((const struct gl_map_impl_base *) map)->vtable->size (map);
281 }
282
283 GL_MAP_INLINE bool
284 gl_map_search (gl_map_t map, const void *key, const void **valuep)
285 {
286 return ((const struct gl_map_impl_base *) map)->vtable
287 ->search (map, key, valuep);
288 }
289
290 _GL_ATTRIBUTE_NODISCARD GL_MAP_INLINE int
291 gl_map_nx_getput (gl_map_t map, const void *key, const void *value,
292 const void **oldvaluep)
293 {
294 return ((const struct gl_map_impl_base *) map)->vtable
295 ->nx_getput (map, key, value, oldvaluep);
296 }
297
298 GL_MAP_INLINE bool
299 gl_map_getremove (gl_map_t map, const void *key, const void **oldvaluep)
300 {
301 return ((const struct gl_map_impl_base *) map)->vtable
302 ->getremove (map, key, oldvaluep);
303 }
304
305 GL_MAP_INLINE void
306 gl_map_free (gl_map_t map)
307 {
308 ((const struct gl_map_impl_base *) map)->vtable->map_free (map);
309 }
310
311 GL_MAP_INLINE gl_map_iterator_t
312 gl_map_iterator (gl_map_t map)
313 {
314 return ((const struct gl_map_impl_base *) map)->vtable->iterator (map);
315 }
316
317 GL_MAP_INLINE bool
318 gl_map_iterator_next (gl_map_iterator_t *iterator,
319 const void **keyp, const void **valuep)
320 {
321 return iterator->vtable->iterator_next (iterator, keyp, valuep);
322 }
323
324 GL_MAP_INLINE void
325 gl_map_iterator_free (gl_map_iterator_t *iterator)
326 {
327 iterator->vtable->iterator_free (iterator);
328 }
329
330 /* Define the convenience functions, that is, the functions that are independent
331 of the implementation. */
332
333 GL_MAP_INLINE const void *
334 gl_map_get (gl_map_t map, const void *key)
335 {
336 const void *value = NULL;
337 gl_map_search (map, key, &value);
338 return value;
339 }
340
341 _GL_ATTRIBUTE_NODISCARD GL_MAP_INLINE int
342 gl_map_nx_put (gl_map_t map, const void *key, const void *value)
343 {
344 const void *oldvalue;
345 int result = gl_map_nx_getput (map, key, value, &oldvalue);
346 if (result == 0)
347 {
348 gl_mapvalue_dispose_fn vdispose_fn =
349 ((const struct gl_map_impl_base *) map)->vdispose_fn;
350 if (vdispose_fn != NULL)
351 vdispose_fn (oldvalue);
352 }
353 return result;
354 }
355
356 GL_MAP_INLINE bool
357 gl_map_remove (gl_map_t map, const void *key)
358 {
359 const void *oldvalue;
360 bool result = gl_map_getremove (map, key, &oldvalue);
361 if (result)
362 {
363 gl_mapvalue_dispose_fn vdispose_fn =
364 ((const struct gl_map_impl_base *) map)->vdispose_fn;
365 if (vdispose_fn != NULL)
366 vdispose_fn (oldvalue);
367 }
368 return result;
369 }
370
371 #ifdef __cplusplus
372 }
373 #endif
374
375 _GL_INLINE_HEADER_END
376
377 #endif /* _GL_MAP_H */