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