![[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 ordered 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 file is free software: you can redistribute it and/or modify
6 it under the terms of the GNU Lesser General Public License as
7 published by the Free Software Foundation; either version 2.1 of the
8 License, or (at your option) any later version.
9
10 This file 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 Lesser General Public License for more details.
14
15 You should have received a copy of the GNU Lesser General Public License
16 along with this program. If not, see <https://www.gnu.org/licenses/>. */
17
18 #ifndef _GL_OMAP_H
19 #define _GL_OMAP_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_OMAP_INLINE
29 # define GL_OMAP_INLINE _GL_INLINE
30 #endif
31
32 #ifdef __cplusplus
33 extern "C" {
34 #endif
35
36
37 /* gl_omap is an abstract ordered map data type. It can contain any number
38 of (key, value) pairs, where
39 - keys and values are objects ('void *' or 'const void *' pointers),
40 - The (key, value) pairs are ordered by the key, in the order of a given
41 comparator function.
42 - There are no (key, value1) and (key, value2) pairs with the same key
43 (in the sense of the comparator function).
44
45 There are several implementations of this ordered map datatype, optimized
46 for different operations or for memory. You can start using the simplest
47 ordered map implementation, GL_ARRAY_OMAP, and switch to a different
48 implementation later, when you realize which operations are performed
49 the most frequently. The API of the different implementations is exactly
50 the same; when switching to a different implementation, you only have to
51 change the gl_omap_create call.
52
53 The implementations are:
54 GL_ARRAY_OMAP a growable array
55 GL_AVLTREE_OMAP a binary tree (AVL tree)
56 GL_RBTREE_OMAP a binary tree (red-black tree)
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 pair, GL_ARRAY_OMAP is the most compact representation, and
61 GL_AVLTREE_OMAP, GL_RBTREE_OMAP need more memory.
62
63 The guaranteed average performance of the operations is, for a map of
64 n pairs:
65
66 Operation ARRAY TREE
67
68 gl_omap_size O(1) O(1)
69 gl_omap_get O(log n) O(log n)
70 gl_omap_put O(n) O(log n)
71 gl_omap_remove O(n) O(log n)
72 gl_omap_search O(log n) O(log n)
73 gl_omap_search_atleast O(log n) O(log n)
74 gl_omap_iterator O(1) O(log n)
75 gl_omap_iterator_next O(1) O(log n)
76 */
77
78 /* -------------------------- gl_omap_t Data Type -------------------------- */
79
80 /* Type of function used to compare two keys. Same as for qsort().
81 NULL denotes pointer comparison. */
82 typedef int (*gl_mapkey_compar_fn) (const void *key1, const void *key2);
83
84 #ifndef _GL_MAP_DISPOSE_FNS_DEFINED
85
86 /* Type of function used to dispose a key once a (key, value) pair is removed
87 from a map. NULL denotes a no-op. */
88 typedef void (*gl_mapkey_dispose_fn) (const void *key);
89
90 /* Type of function used to dispose a value once a (key, value) pair is removed
91 from a map. NULL denotes a no-op. */
92 typedef void (*gl_mapvalue_dispose_fn) (const void *value);
93
94 # define _GL_MAP_DISPOSE_FNS_DEFINED 1
95 #endif
96
97 /* Type of function used to compare a key with a threshold.
98 Returns true if the key is greater or equal than the threshold. */
99 typedef bool (*gl_mapkey_threshold_fn) (const void *key, const void *threshold);
100
101 struct gl_omap_impl;
102 /* Type representing an entire ordered map. */
103 typedef struct gl_omap_impl * gl_omap_t;
104
105 struct gl_omap_implementation;
106 /* Type representing a ordered map datatype implementation. */
107 typedef const struct gl_omap_implementation * gl_omap_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_OMAP, GL_AVLTREE_OMAP, GL_RBTREE_OMAP.
113 COMPAR_FN is a key comparison function or NULL.
114 KDISPOSE_FN is a key disposal function or NULL.
115 VDISPOSE_FN is a value disposal function or NULL. */
116 /* declared in gl_xomap.h */
117 extern gl_omap_t gl_omap_create_empty (gl_omap_implementation_t implementation,
/* ![[next]](../icons/right.png)
![[first]](../icons/n_first.png)
![[top]](../icons/top.png)
*/
118 gl_mapkey_compar_fn compar_fn,
119 gl_mapkey_dispose_fn kdispose_fn,
120 gl_mapvalue_dispose_fn vdispose_fn)
121 /*_GL_ATTRIBUTE_DEALLOC (gl_omap_free, 1)*/
122 _GL_ATTRIBUTE_RETURNS_NONNULL;
123 /* Likewise. Returns NULL upon out-of-memory. */
124 extern gl_omap_t gl_omap_nx_create_empty (gl_omap_implementation_t implementation,
125 gl_mapkey_compar_fn compar_fn,
126 gl_mapkey_dispose_fn kdispose_fn,
127 gl_mapvalue_dispose_fn vdispose_fn)
128 /*_GL_ATTRIBUTE_DEALLOC (gl_omap_free, 1)*/;
129
130 /* Returns the current number of pairs in an ordered map. */
131 extern size_t gl_omap_size (gl_omap_t map);
132
133 /* Searches whether a pair with the given key is already in the ordered map.
134 Returns the value if found, or NULL if not present in the map. */
135 extern const void * gl_omap_get (gl_omap_t map, const void *key);
136
137 /* Searches whether a pair with the given key is already in the ordered map.
138 Returns true and sets *VALUEP to the value if found.
139 Returns false if not present in the map. */
140 extern bool gl_omap_search (gl_omap_t map, const void *key,
141 const void **valuep);
142
143 /* Searches the pair with the least key in the ordered map that compares
144 greater or equal to the given THRESHOLD. The representation of the
145 THRESHOLD is defined by the THRESHOLD_FN.
146 Returns true and stores the found pair in *KEYP and *VALUEP if found.
147 Otherwise returns false. */
148 extern bool gl_omap_search_atleast (gl_omap_t map,
149 gl_mapkey_threshold_fn threshold_fn,
150 const void *threshold,
151 const void **keyp, const void **valuep);
152
153 /* Adds a pair to an ordered map.
154 Returns true if a pair with the given key was not already in the map and so
155 this pair was added.
156 Returns false if a pair with the given key was already in the map and only
157 its value was replaced. */
158 /* declared in gl_xomap.h */
159 extern bool gl_omap_put (gl_omap_t map, const void *key, const void *value);
160 /* Likewise. Returns -1 upon out-of-memory. */
161 _GL_ATTRIBUTE_NODISCARD
162 extern int gl_omap_nx_put (gl_omap_t map, const void *key, const void *value);
163
164 /* Adds a pair to an ordered map and retrieves the previous value.
165 Returns true if a pair with the given key was not already in the map and so
166 this pair was added.
167 Returns false and sets *OLDVALUEP to the previous value, if a pair with the
168 given key was already in the map and only its value was replaced. */
169 /* declared in gl_xomap.h */
170 extern bool gl_omap_getput (gl_omap_t map, const void *key, const void *value,
171 const void **oldvaluep);
172 /* Likewise. Returns -1 upon out-of-memory. */
173 _GL_ATTRIBUTE_NODISCARD
174 extern int gl_omap_nx_getput (gl_omap_t map, const void *key, const void *value,
175 const void **oldvaluep);
176
177 /* Removes a pair from an ordered map.
178 Returns true if the key was found and its pair removed.
179 Returns false otherwise. */
180 extern bool gl_omap_remove (gl_omap_t map, const void *key);
181
182 /* Removes a pair from an ordered map and retrieves the previous value.
183 Returns true and sets *OLDVALUEP to the previous value, if the key was found
184 and its pair removed.
185 Returns false otherwise. */
186 extern bool gl_omap_getremove (gl_omap_t map, const void *key,
187 const void **oldvaluep);
188
189 /* Frees an entire ordered map.
190 (But this call does not free the keys and values of the pairs in the map.
191 It only invokes the KDISPOSE_FN on each key and the VDISPOSE_FN on each value
192 of the pairs in the map.) */
193 extern void gl_omap_free (gl_omap_t map);
194
195 #endif /* End of inline and gl_xomap.h-defined functions. */
196
197 /* ---------------------- gl_omap_iterator_t Data Type ---------------------- */
198
199 /* Functions for iterating through an ordered map. */
200
201 /* Type of an iterator that traverses an ordered map.
202 This is a fixed-size struct, so that creation of an iterator doesn't need
203 memory allocation on the heap. */
204 typedef struct
205 {
206 /* For fast dispatch of gl_omap_iterator_next. */
207 const struct gl_omap_implementation *vtable;
208 /* For detecting whether the last returned pair was removed. */
209 gl_omap_t map;
210 size_t count;
211 /* Other, implementation-private fields. */
212 void *p; void *q;
213 size_t i; size_t j;
214 } gl_omap_iterator_t;
215
216 #if 0 /* These are defined inline below. */
217
218 /* Creates an iterator traversing an ordered map.
219 The map's contents must not be modified while the iterator is in use,
220 except for modifying the value of the last returned key or removing the
221 last returned pair. */
222 extern gl_omap_iterator_t gl_omap_iterator (gl_omap_t map);
223
224 /* If there is a next pair, stores the next pair in *KEYP and *VALUEP, advances
225 the iterator, and returns true. Otherwise, returns false. */
226 extern bool gl_omap_iterator_next (gl_omap_iterator_t *iterator,
227 const void **keyp, const void **valuep);
228
229 /* Frees an iterator. */
230 extern void gl_omap_iterator_free (gl_omap_iterator_t *iterator);
231
232 #endif /* End of inline functions. */
233
234 /* ------------------------- Implementation Details ------------------------- */
235
236 struct gl_omap_implementation
237 {
238 /* gl_omap_t functions. */
239 gl_omap_t (*nx_create_empty) (gl_omap_implementation_t implementation,
240 gl_mapkey_compar_fn compar_fn,
241 gl_mapkey_dispose_fn kdispose_fn,
242 gl_mapvalue_dispose_fn vdispose_fn);
243 size_t (*size) (gl_omap_t map);
244 bool (*search) (gl_omap_t map, const void *key, const void **valuep);
245 bool (*search_atleast) (gl_omap_t map,
246 gl_mapkey_threshold_fn threshold_fn,
247 const void *threshold,
248 const void **keyp, const void **valuep);
249 int (*nx_getput) (gl_omap_t map, const void *key, const void *value,
250 const void **oldvaluep);
251 bool (*getremove) (gl_omap_t map, const void *key, const void **oldvaluep);
252 void (*omap_free) (gl_omap_t map);
253 /* gl_omap_iterator_t functions. */
254 gl_omap_iterator_t (*iterator) (gl_omap_t map);
255 bool (*iterator_next) (gl_omap_iterator_t *iterator,
256 const void **keyp, const void **valuep);
257 void (*iterator_free) (gl_omap_iterator_t *iterator);
258 };
259
260 struct gl_omap_impl_base
261 {
262 const struct gl_omap_implementation *vtable;
263 gl_mapkey_compar_fn compar_fn;
264 gl_mapkey_dispose_fn kdispose_fn;
265 gl_mapvalue_dispose_fn vdispose_fn;
266 };
267
268 /* Define most functions of this file as accesses to the
269 struct gl_omap_implementation. */
270
271 GL_OMAP_INLINE
272 /*_GL_ATTRIBUTE_DEALLOC (gl_omap_free, 1)*/
273 gl_omap_t
274 gl_omap_nx_create_empty (gl_omap_implementation_t implementation,
/* ![[previous]](../icons/left.png)
*/
275 gl_mapkey_compar_fn compar_fn,
276 gl_mapkey_dispose_fn kdispose_fn,
277 gl_mapvalue_dispose_fn vdispose_fn)
278 {
279 return implementation->nx_create_empty (implementation, compar_fn,
280 kdispose_fn, vdispose_fn);
281 }
282
283 GL_OMAP_INLINE size_t
284 gl_omap_size (gl_omap_t map)
/* */
285 {
286 return ((const struct gl_omap_impl_base *) map)->vtable->size (map);
287 }
288
289 GL_OMAP_INLINE bool
290 gl_omap_search (gl_omap_t map, const void *key, const void **valuep)
/* */
291 {
292 return ((const struct gl_omap_impl_base *) map)->vtable
293 ->search (map, key, valuep);
294 }
295
296 GL_OMAP_INLINE bool
297 gl_omap_search_atleast (gl_omap_t map,
/* */
298 gl_mapkey_threshold_fn threshold_fn,
299 const void *threshold,
300 const void **keyp, const void **valuep)
301 {
302 return ((const struct gl_omap_impl_base *) map)->vtable
303 ->search_atleast (map, threshold_fn, threshold, keyp, valuep);
304 }
305
306 _GL_ATTRIBUTE_NODISCARD GL_OMAP_INLINE int
307 gl_omap_nx_getput (gl_omap_t map, const void *key, const void *value,
/* */
308 const void **oldvaluep)
309 {
310 return ((const struct gl_omap_impl_base *) map)->vtable
311 ->nx_getput (map, key, value, oldvaluep);
312 }
313
314 GL_OMAP_INLINE bool
315 gl_omap_getremove (gl_omap_t map, const void *key, const void **oldvaluep)
/* */
316 {
317 return ((const struct gl_omap_impl_base *) map)->vtable
318 ->getremove (map, key, oldvaluep);
319 }
320
321 GL_OMAP_INLINE void
322 gl_omap_free (gl_omap_t map)
/* */
323 {
324 ((const struct gl_omap_impl_base *) map)->vtable->omap_free (map);
325 }
326
327 GL_OMAP_INLINE gl_omap_iterator_t
328 gl_omap_iterator (gl_omap_t map)
/* */
329 {
330 return ((const struct gl_omap_impl_base *) map)->vtable->iterator (map);
331 }
332
333 GL_OMAP_INLINE bool
334 gl_omap_iterator_next (gl_omap_iterator_t *iterator,
/* */
335 const void **keyp, const void **valuep)
336 {
337 return iterator->vtable->iterator_next (iterator, keyp, valuep);
338 }
339
340 GL_OMAP_INLINE void
341 gl_omap_iterator_free (gl_omap_iterator_t *iterator)
/* */
342 {
343 iterator->vtable->iterator_free (iterator);
344 }
345
346 /* Define the convenience functions, that is, the functions that are independent
347 of the implementation. */
348
349 GL_OMAP_INLINE const void *
350 gl_omap_get (gl_omap_t map, const void *key)
/* */
351 {
352 const void *value = NULL;
353 gl_omap_search (map, key, &value);
354 return value;
355 }
356
357 _GL_ATTRIBUTE_NODISCARD GL_OMAP_INLINE int
358 gl_omap_nx_put (gl_omap_t map, const void *key, const void *value)
/* */
359 {
360 const void *oldvalue;
361 int result = gl_omap_nx_getput (map, key, value, &oldvalue);
362 if (result == 0)
363 {
364 gl_mapvalue_dispose_fn vdispose_fn =
365 ((const struct gl_omap_impl_base *) map)->vdispose_fn;
366 if (vdispose_fn != NULL)
367 vdispose_fn (oldvalue);
368 }
369 return result;
370 }
371
372 GL_OMAP_INLINE bool
373 gl_omap_remove (gl_omap_t map, const void *key)
/* ![[last]](../icons/n_last.png)
*/
374 {
375 const void *oldvalue;
376 bool result = gl_omap_getremove (map, key, &oldvalue);
377 if (result)
378 {
379 gl_mapvalue_dispose_fn vdispose_fn =
380 ((const struct gl_omap_impl_base *) map)->vdispose_fn;
381 if (vdispose_fn != NULL)
382 vdispose_fn (oldvalue);
383 }
384 return result;
385 }
386
387 #ifdef __cplusplus
388 }
389 #endif
390
391 _GL_INLINE_HEADER_END
392
393 #endif /* _GL_OMAP_H */
![[bottom]](../icons/n_bottom.png){kind=icon}
*/