Tue, 28 Mar 2023 21:00:33 +0200
allow NULL for allocator and comparator
1 /*
2 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
3 *
4 * Copyright 2021 Mike Becker, Olaf Wintermann All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are met:
8 *
9 * 1. Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 *
12 * 2. Redistributions in binary form must reproduce the above copyright
13 * notice, this list of conditions and the following disclaimer in the
14 * documentation and/or other materials provided with the distribution.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 */
28 /**
29 * \file map.h
30 * \brief Interface for map implementations.
31 * \author Mike Becker
32 * \author Olaf Wintermann
33 * \version 3.0
34 * \copyright 2-Clause BSD License
35 */
37 #ifndef UCX_MAP_H
38 #define UCX_MAP_H
40 #include "common.h"
41 #include "allocator.h"
42 #include "iterator.h"
43 #include "hash_key.h"
45 #ifdef __cplusplus
46 extern "C" {
47 #endif
49 #ifndef CX_STORE_POINTERS
50 /**
51 * Special constant used for creating collections that are storing pointers.
52 */
53 #define CX_STORE_POINTERS 0
54 #endif
56 /** Type for the UCX map. */
57 typedef struct cx_map_s CxMap;
59 /** Type for a map entry. */
60 typedef struct cx_map_entry_s CxMapEntry;
62 /** Type for map class definitions. */
63 typedef struct cx_map_class_s cx_map_class;
65 /** Structure for the UCX map. */
66 struct cx_map_s {
67 /** The map class definition. */
68 cx_map_class *cl;
69 /** An allocator that is used for the map elements. */
70 CxAllocator *allocator;
71 /** The number of elements currently stored. */
72 size_t size;
73 /**
74 * The size of an element.
75 */
76 size_t itemsize;
77 /**
78 * True, if this map shall store pointers instead
79 * of copies of objects.
80 */
81 bool store_pointers;
82 };
84 /**
85 * The class definition for arbitrary maps.
86 */
87 struct cx_map_class_s {
88 /**
89 * Deallocates the entire memory.
90 */
91 __attribute__((__nonnull__))
92 void (*destructor)(struct cx_map_s *map);
94 /**
95 * Removes all elements.
96 */
97 __attribute__((__nonnull__))
98 void (*clear)(struct cx_map_s *map);
100 /**
101 * Add or overwrite an element.
102 */
103 __attribute__((__nonnull__))
104 int (*put)(
105 CxMap *map,
106 CxHashKey key,
107 void *value
108 );
110 /**
111 * Returns an element.
112 */
113 __attribute__((__nonnull__, __warn_unused_result__))
114 void *(*get)(
115 CxMap const *map,
116 CxHashKey key
117 );
119 /**
120 * Removes an element.
121 */
122 __attribute__((__nonnull__))
123 void *(*remove)(
124 CxMap *map,
125 CxHashKey key
126 );
128 /**
129 * Iterator over the key/value pairs.
130 */
131 __attribute__((__nonnull__, __warn_unused_result__))
132 CxIterator (*iterator)(CxMap const *map);
134 /**
135 * Iterator over the keys.
136 */
137 __attribute__((__nonnull__, __warn_unused_result__))
138 CxIterator (*iterator_keys)(CxMap const *map);
140 /**
141 * Iterator over the values.
142 */
143 __attribute__((__nonnull__, __warn_unused_result__))
144 CxIterator (*iterator_values)(CxMap const *map);
146 /**
147 * Mutating iterator over the key/value pairs.
148 */
149 __attribute__((__nonnull__, __warn_unused_result__))
150 CxMutIterator (*mut_iterator)(CxMap *map);
152 /**
153 * Mutating iterator over the keys.
154 */
155 __attribute__((__nonnull__, __warn_unused_result__))
156 CxMutIterator (*mut_iterator_keys)(CxMap *map);
158 /**
159 * Mutating iterator over the values.
160 */
161 __attribute__((__nonnull__, __warn_unused_result__))
162 CxMutIterator (*mut_iterator_values)(CxMap *map);
163 };
165 /**
166 * A map entry.
167 */
168 struct cx_map_entry_s {
169 /**
170 * A pointer to the key.
171 */
172 CxHashKey const *key;
173 /**
174 * A pointer to the value.
175 */
176 void *value;
177 };
179 /**
180 * Advises the map to store copies of the objects (default mode of operation).
181 *
182 * Retrieving objects from this map will yield pointers to the copies stored
183 * within this list.
184 *
185 * @param map the map
186 * @see cxMapStorePointers()
187 */
188 __attribute__((__nonnull__))
189 static inline void cxMapStoreObjects(CxMap *map) {
190 map->store_pointers = false;
191 }
193 /**
194 * Advises the map to only store pointers to the objects.
195 *
196 * Retrieving objects from this list will yield the original pointers stored.
197 *
198 * @note This function forcibly sets the element size to the size of a pointer.
199 * Invoking this function on a non-empty map that already stores copies of
200 * objects is undefined.
201 *
202 * @param map the map
203 * @see cxMapStoreObjects()
204 */
205 __attribute__((__nonnull__))
206 static inline void cxMapStorePointers(CxMap *map) {
207 map->store_pointers = true;
208 map->itemsize = sizeof(void *);
209 }
212 /**
213 * Deallocates the memory of the specified map.
214 *
215 * @param map the map to be destroyed
216 */
217 __attribute__((__nonnull__))
218 static inline void cxMapDestroy(CxMap *map) {
219 // TODO: likely to add auto-free feature for contents in the future
220 map->cl->destructor(map);
221 }
224 /**
225 * Clears a map by removing all elements.
226 *
227 * @param map the map to be cleared
228 */
229 __attribute__((__nonnull__))
230 static inline void cxMapClear(CxMap *map) {
231 map->cl->clear(map);
232 }
234 /**
235 * Puts a key/value-pair into the map.
236 *
237 * @param map the map
238 * @param key the key
239 * @param value the value
240 * @return 0 on success, non-zero value on failure
241 */
242 __attribute__((__nonnull__))
243 static inline int cxMapPut(
244 CxMap *map,
245 CxHashKey key,
246 void *value
247 ) {
248 return map->cl->put(map, key, value);
249 }
251 /**
252 * Retrieves a value by using a key.
253 *
254 * @param map the map
255 * @param key the key
256 * @return the value
257 */
258 __attribute__((__nonnull__, __warn_unused_result__))
259 static inline void *cxMapGet(
260 CxMap const *map,
261 CxHashKey key
262 ) {
263 return map->cl->get(map, key);
264 }
266 /**
267 * Removes a key/value-pair from the map by using the key.
268 *
269 * If this map is storing pointers, you should make sure that the map
270 * is not the last location where this pointer is stored.
271 * Otherwise, use cxMapRemoveAndGet() to retrieve the pointer while
272 * removing it from the map.
273 *
274 * @param map the map
275 * @param key the key
276 * @see cxMapRemoveAndGet()
277 */
278 __attribute__((__nonnull__))
279 static inline void cxMapRemove(
280 CxMap *map,
281 CxHashKey key
282 ) {
283 (void) map->cl->remove(map, key);
284 }
286 /**
287 * Removes a key/value-pair from the map by using the key.
288 *
289 * This function should only be used when the map is storing pointers,
290 * in order to retrieve the pointer you are about to remove.
291 * In any other case, cxMapRemove() is sufficient.
292 *
293 * @param map the map
294 * @param key the key
295 * @return the stored pointer or \c NULL if either the key is not present
296 * in the map or the map is not storing pointers
297 * @see cxMapStorePointers()
298 */
299 __attribute__((__nonnull__, __warn_unused_result__))
300 static inline void *cxMapRemoveAndGet(
301 CxMap *map,
302 CxHashKey key
303 ) {
304 return map->cl->remove(map, key);
305 }
307 // TODO: set-like map operations (union, intersect, difference)
309 /**
310 * Creates a value iterator for a map.
311 *
312 * \note An iterator iterates over all elements successively. Therefore the order
313 * highly depends on the map implementation and may change arbitrarily when the contents change.
314 *
315 * @param map the map to create the iterator for
316 * @return an iterator for the currently stored values
317 */
318 __attribute__((__nonnull__, __warn_unused_result__))
319 static inline CxIterator cxMapIteratorValues(CxMap *map) {
320 return map->cl->iterator_values(map);
321 }
323 /**
324 * Creates a key iterator for a map.
325 *
326 * The elements of the iterator are keys of type CxHashKey.
327 *
328 * \note An iterator iterates over all elements successively. Therefore the order
329 * highly depends on the map implementation and may change arbitrarily when the contents change.
330 *
331 * @param map the map to create the iterator for
332 * @return an iterator for the currently stored keys
333 */
334 __attribute__((__nonnull__, __warn_unused_result__))
335 static inline CxIterator cxMapIteratorKeys(CxMap *map) {
336 return map->cl->iterator_keys(map);
337 }
339 /**
340 * Creates an iterator for a map.
341 *
342 * The elements of the iterator are key/value pairs of type CxMapEntry.
343 *
344 * \note An iterator iterates over all elements successively. Therefore the order
345 * highly depends on the map implementation and may change arbitrarily when the contents change.
346 *
347 * @param map the map to create the iterator for
348 * @return an iterator for the currently stored entries
349 * @see cxMapIteratorKeys()
350 * @see cxMapIteratorValues()
351 */
352 __attribute__((__nonnull__, __warn_unused_result__))
353 static inline CxIterator cxMapIterator(CxMap *map) {
354 return map->cl->iterator(map);
355 }
358 /**
359 * Creates a mutating iterator over the values of a map.
360 *
361 * \note An iterator iterates over all elements successively. Therefore the order
362 * highly depends on the map implementation and may change arbitrarily when the contents change.
363 *
364 * @param map the map to create the iterator for
365 * @return an iterator for the currently stored values
366 */
367 __attribute__((__nonnull__, __warn_unused_result__))
368 static inline CxMutIterator cxMapMutIteratorValues(CxMap *map) {
369 return map->cl->mut_iterator_values(map);
370 }
372 /**
373 * Creates a mutating iterator over the keys of a map.
374 *
375 * The elements of the iterator are keys of type CxHashKey.
376 *
377 * \note An iterator iterates over all elements successively. Therefore the order
378 * highly depends on the map implementation and may change arbitrarily when the contents change.
379 *
380 * @param map the map to create the iterator for
381 * @return an iterator for the currently stored keys
382 */
383 __attribute__((__nonnull__, __warn_unused_result__))
384 static inline CxMutIterator cxMapMutIteratorKeys(CxMap *map) {
385 return map->cl->mut_iterator_keys(map);
386 }
388 /**
389 * Creates a mutating iterator for a map.
390 *
391 * The elements of the iterator are key/value pairs of type CxMapEntry.
392 *
393 * \note An iterator iterates over all elements successively. Therefore the order
394 * highly depends on the map implementation and may change arbitrarily when the contents change.
395 *
396 * @param map the map to create the iterator for
397 * @return an iterator for the currently stored entries
398 * @see cxMapMutIteratorKeys()
399 * @see cxMapMutIteratorValues()
400 */
401 __attribute__((__nonnull__, __warn_unused_result__))
402 static inline CxMutIterator cxMapMutIterator(CxMap *map) {
403 return map->cl->mut_iterator(map);
404 }
406 #ifdef __cplusplus
407 }
408 #endif
410 #endif // UCX_MAP_H