about.md- allocator.h.md
- array_list.h.md
- buffer.h.md
- collection.h.md
- collections.md
- compare.h.md
- features.md
- hash_key.h.md
- hash_map.h.md
- install.md
- iterator.h.md
- json.h.md
- kv_list.h.md
- license.md
- linked_list.h.md
- list.h.md
- map.h.md
- memory.md
- mempool.h.md
- parsers.md
- printf.h.md
- properties.h.md
- streams.h.md
- string.h.md
- strings.md
- test.h.md
- tree.h.md
- utils.md
1 # Map Interface
2
3 Similar to the list interface, the map interface provides a common API for implementing maps.
4
5 UCX is shipped with a [hash map](hash_map.h.md) implementation of this interface.
6
7 ```C
8 #include <cx/hash_map.h>
9
10 CxMap *cxHashMapCreate(const CxAllocator *allocator,
11 size_t itemsize, size_t buckets);
12 ```
13
14 The function `cxHashMapCreate()` creates a new map where both the map structure
15 and the contained buckets are allocated by the specified `allocator`.
16
17 The map will store items of size `itemsize`.
18 You can use the `CX_STORE_POINTERS` macro for `itemsize` to indicate that the map shall store
19 pointers instead of actual items.
20
21 If you pass zero for the number of `buckets`,
22 the map is initialized with a default of 16 buckets; otherwise the specified number of buckets is allocated.
23
24 > If you want to lazy-initialize maps, you can use the global `cxEmptyMap` symbol as a placeholder instead of using a `NULL`-pointer.
25 > While you *must not* insert elements into that map, you can safely access this map or create iterators.
26 > This allows you to write clean code without checking for `NULL`-pointer everywhere.
27 > You still need to make sure that the placeholder is replaced with an actual map before inserting elements.
28
29 > All functions working with keys are implemented as generics, so that the following types are supported:
30 > `CxHashKey`, `cxstring`, `cxmutstr`, `const char*`, and `char*`.
31 > When we write `KeyType`, we mean any of these types.
32 > {style="note"}
33
34 ## Examples
35
36 ```C
37 #include <stdio.h>
38 #include <cx/hash_map.h>
39
40 int main() {
41 CxMap *contacts = cxHashMapCreate(NULL, CX_STORE_POINTERS, 0);
42
43 // Build a small phone book
44 cxMapPut(contacts, "John", "123-0815");
45 cxMapPut(contacts, "Jane", "987-4711");
46 cxMapPut(contacts, "Michelle", "555-3141");
47 cxMapPut(contacts, "Oliver", "000-9999");
48
49 // Retrieve a phone number
50 const char *janes_phone = cxMapGet(contacts, "Jane");
51 printf("The number of Jane is: %s\n", janes_phone);
52
53 // Update number
54 cxMapPut(contacts, "Jane", "987-1337");
55
56 // Remove and retrieve number
57 cxMapRemoveAndGet(contacts, "Jane", &janes_phone);
58 printf("The number of Jane was: %s\n", janes_phone);
59 janes_phone = cxMapGet(contacts, "Jane");
60 if (janes_phone == NULL) printf("Jane's number was deleted.\n");
61
62 // Iterate through the contact list
63 CxMapIterator iter = cxMapIterator(contacts);
64 cx_foreach(CxMapEntry *, entry, iter) {
65 cxstring name = cx_strn(entry->key->data, entry->key->len);
66 const char *phone = entry->value;
67 printf("%" CX_PRIstr ": %s\n", CX_SFMT(name), phone);
68 }
69
70 cxMapFree(contacts);
71
72 return 0;
73 }
74 ```
75
76 The above example illustrates basic operations with a map.
77
78 In the first part we add several entries to the map.
79 Then the example shows retrieval, updating, and removal of information.
80 The last part shows how to iterate over the pairs inside the map and how to recover the string from the key.
81
82 In real-world situations, however, it is quite unlikely that you will use a map to store string literals.
83 The next example shows a more realistic program, where it is necessary to store strings based on user input.
84
85 ```C
86 #include <stdio.h>
87 #include <string.h>
88 #include <cx/hash_map.h>
89
90 int main() {
91 // store strings in the map...
92 CxMap *contacts = cxHashMapCreate(NULL, sizeof(cxmutstr), 0);
93 // ...which are automatically freed when removed
94 cxSetDestructor(contacts, cx_strfree);
95
96 // build a small interactive program
97 const unsigned buffer_size = 256;
98 char input[buffer_size];
99 bool running = true;
100
101 while (running) {
102 puts("\n*** Contacts - Menu ***");
103 puts("1) Add entry");
104 puts("2) Look up entry");
105 puts("3) Remove entry");
106 puts("4) Show all entries");
107 puts("0) Exit");
108 fputs("> ", stdout);
109
110 if (fgets(input, buffer_size, stdin)) {
111 if (input[1] != '\n') {
112 puts("Please select a menu item.\n");
113 } else if (input[0] == '1') {
114 fputs("Name > ", stdout);
115 if (fgets(input, buffer_size, stdin)) {
116 // Copy the name (alternative: use 2nd input buf)
117 cxmutstr name = cx_strdup(
118 cx_strn(input, strcspn(input, "\n")));
119 fputs("Phone > ", stdout);
120 if (fgets(input, buffer_size, stdin)) {
121 // add the entry, note that only the contents
122 // of the cxmutstr are copied, not the string
123 // data - therefore we have to call cx_strdup
124 cxmutstr phone = cx_strdup(
125 cx_strn(input, strcspn(input, "\n")));
126 // note, that we can simply use the cxmutstr
127 // for the name as key, because cxMapPut uses
128 // generic selection
129 cxMapPut(contacts, name, &phone);
130 }
131 cx_strfree(&name);
132 }
133 } else if (input[0] == '2') {
134 fputs("Name > ", stdout);
135 if (fgets(input, buffer_size, stdin)) {
136 // Look up the name
137 input[strcspn(input, "\n")] = '\0';
138 cxmutstr *phone = cxMapGet(contacts, input);
139 if (phone == NULL) {
140 puts("No record.");
141 } else {
142 printf("Result: %" CX_PRIstr "\n",
143 CX_SFMT(*phone));
144 }
145 }
146 } else if (input[0] == '3') {
147 fputs("Name > ", stdout);
148 if (fgets(input, buffer_size, stdin)) {
149 // Remove the entry
150 // Since we registered cx_strfree as destructor,
151 // the memory is automatically freed
152 input[strcspn(input, "\n")] = '\0';
153 if (cxMapRemove(contacts, input)) {
154 puts("No such record.");
155 } else {
156 puts("Removed.");
157 }
158 }
159 } else if (input[0] == '4') {
160 // Almost the same iteration loop as above ...
161 CxMapIterator iter = cxMapIterator(contacts);
162 cx_foreach(CxMapEntry *, entry, iter) {
163 cxstring name = cx_strn(entry->key->data,
164 entry->key->len);
165 // ... except that here we get cxmutstr*
166 cxmutstr *phone = entry->value;
167 printf("%" CX_PRIstr ": %" CX_PRIstr "\n",
168 CX_SFMT(name), CX_SFMT(*phone));
169 }
170 } else if (input[0] == '0') {
171 running = false;
172 } else {
173 puts("Please select a menu item.\n");
174 }
175 } else {
176 running = false;
177 }
178 }
179
180 // this will free all remaining strings that are in the map
181 cxMapFree(contacts);
182
183 return 0;
184 }
185 ```
186
187 ## Insert
188
189 ```C
190 #include <cx/map.h>
191
192 int cxMapPut(CxMap *map, KeyType key, void *value);
193
194 void *cxMapEmplace(CxMap *map, KeyType key);
195 ```
196
197 The function `cxMapPut()` stores the specified `key` / `value` pair
198 and returns zero if the element was successfully put into the map and non-zero otherwise.
199
200 The key is always copied.
201 The behavior for the value is dependent on whether the map is storing pointers.
202 If it is storing pointers, the `value` pointer is directly stored in the map.
203 Otherwise, the memory pointed to by `value` is copied, using the element size of the collection.
204
205 The function `cxMapEmplace()` is similar to `cxMapPut()`, but instead of adding an existing value to the map,
206 it returns a pointer to newly allocated memory for the value.
207 The memory is allocated using the allocator of the map.
208 If the map is storing pointers, the allocated memory will only be that for a pointer.
209 Otherwise, the memory is allocated using the known element size.
210
211 Both functions, if an element is already associated with the specified key, replace the existing element.
212 If [destructor functions](collection.h.md#destructor-functions) are registered,
213 they are invoked for the old element before it is replaced.
214
215 ## Access
216
217 ```C
218 #include <cx/map.h>
219
220 void *cxMapGet(CxMap *map, KeyType key);
221
222 bool cxMapContains(CxMap *map, KeyType key);
223
224 size_t cxMapSize(const CxMap *map);
225 ```
226
227 With the function `cxMapGet()` you can retrieve a value stored under the specified `key`.
228 If there is no such value, this function returns `NULL`.
229
230 The function `cxMapContains()` returns `true` if the map contains an element with the specified `key`,
231 and `false` otherwise.
232
233 The function `cxMapSize()` returns how many key/value-pairs are currently stored in the map.
234
235 ## Remove
236
237 ```C
238 #include <cx/map.h>
239
240 int cxMapRemove(CxMap *map, KeyType key);
241
242 int cxMapRemoveAndGet(CxMap *map, KeyType key, void* targetbuf);
243
244 void cxMapClear(CxMap *map);
245 ```
246
247 The function `cxMapRemove()` retrieves and removes a value stored under the specified `key`.
248 If [destructor functions](collection.h.md#destructor-functions) are registered, they are called before removal.
249
250 On the other hand, `cxMapRemoveAndGet()` does not invoke the destructor functions
251 and instead copies the value into the `targetbuf`, which must be large enough to hold the value.
252
253 In either case, the functions return zero when an element was found under the specified key, and non-zero otherwise.
254
255 The function `cxMapClear()` removes all elements from the map, invoking the destructor functions for each of them.
256
257 ## Iterators
258
259 ```C
260 #include <cx/map.h>
261
262 CxMapIterator cxMapIterator(const CxMap *map);
263
264 CxMapIterator cxMapIteratorKeys(const CxMap *map);
265
266 CxMapIterator cxMapIteratorValues(const CxMap *map);
267 ```
268
269 The above functions create iterators over the
270 pairs, keys, or values of the specified `map`, respectively.
271
272 Iterators over pairs yield elements of the type `CxMapEntry*` which is a struct containing a pointer to the `key` and the value, respectively.
273
274 Iterators over keys yield elements of the type `const CxHashKey*` (cf. [CxHashKey documentation](hash_key.h.md)).
275
276 The behavior of iterators over values depends on the concrete implementation.
277 Implementations are encouraged to support `CX_STORE_POINTERS`.
278 If used, the `void*` elements the iterator yields shall be directly the stored pointers.
279 Otherwise, the iterator shall yield pointers to the map's memory where the value is stored.
280
281 It is always safe to call the above functions on a `NULL`-pointer.
282 In that case, the returned iterator will behave like an iterator over an empty map.
283
284 ## Compare
285
286 ```C
287 #include <cx/map.h>
288
289 int cxMapCompare(const CxMap *map, const CxMap *other);
290 ```
291
292 Arbitrary maps can be compared with `cxMapCompare()`.
293 That means, for example, you can compare a [hash map](hash_map.h.md) with the map aspect of a [key/value list](kv_list.h.md).
294
295 The return value of `cxMapCompare()` is zero if the lists contain the same keys and their values are pairwise equivalent, according to the map's compare function.
296 If the `map` contains fewer keys than the `other` map, the function returns a negative value, and if it contains more values, it returns a positive value, respectively.
297 When both maps contain the same number of keys but differ in either a key or a value, the return value is non-zero, but otherwise unspecified.
298
299 ## Clone
300
301 ```C
302 #include <cx/allocator.h>
303
304 typedef void*(cx_clone_func)(
305 void *target, const void *source,
306 const CxAllocator *allocator,
307 void *data);
308
309 #include <cx/map.h>
310
311 int cxMapClone(CxMap *dst, const CxMap *src,
312 cx_clone_func clone_func,
313 const CxAllocator *clone_allocator,
314 void *data);
315
316 int cxMapCloneShallow(CxMap *dst, const CxMap *src);
317
318 int cxMapDifference(CxMap *dst,
319 const CxMap *minuend, const CxMap *subtrahend,
320 cx_clone_func clone_func,
321 const CxAllocator *clone_allocator,
322 void *data);
323
324 int cxMapDifferenceShallow(CxMap *dst,
325 const CxMap *minuend, const CxMap *subtrahend);
326
327 int cxMapListDifference(CxMap *dst,
328 const CxMap *src, const CxList *keys,
329 cx_clone_func clone_func,
330 const CxAllocator *clone_allocator,
331 void *data);
332
333 int cxMapListDifferenceShallow(CxMap *dst,
334 const CxMap *src, const CxList *keys);
335
336 int cxMapIntersection(CxMap *dst,
337 const CxMap *src, const CxMap *other,
338 cx_clone_func clone_func,
339 const CxAllocator *clone_allocator,
340 void *data);
341
342 int cxMapIntersectionShallow(CxMap *dst,
343 const CxMap *src, const CxMap *other);
344
345 int cxMapListIntersection(CxMap *dst,
346 const CxMap *src, const CxList *keys,
347 cx_clone_func clone_func,
348 const CxAllocator *clone_allocator,
349 void *data);
350
351 int cxMapListIntersectionShallow(CxMap *dst,
352 const CxMap *src, const CxList *keys);
353
354 int cxMapUnion(CxMap *dst, const CxMap *src,
355 cx_clone_func clone_func,
356 const CxAllocator *clone_allocator,
357 void *data);
358
359 int cxMapUnionShallow(CxMap *dst, const CxMap *src);
360 ```
361
362 With `cxMapClone()` you can create deep copies of the values in one map and insert them into another map.
363 The destination map does not need to be empty.
364 But when a key already exists in the destination map, the value is overwritten with the clone from the source map.
365 If the destination map has destructors defined, they are called for the replaced element.
366
367 The functions `cxMapDifference()` and `cxMapListDifference()` are similar to `cxMapClone()`
368 except that they only clone an element from the source map, when the key is _not_ contained in the
369 other map (or list, respectively).
370 This is equivalent to computing the set difference for the set of keys.
371 Likewise, `cxMapIntersection()` and `cxMapListIntersection()` only clone an element from the source map
372 when the key is contained in _both_ collections.
373 The function `cxMapUnion()` only clones elements from `src` to `dst` when their key is not present in `dst`.
374
375 > The function `cxMapUnion()` does not operate on three maps for the sake of simplicity.
376 > If you want to combine two maps without modifying either of them, you can first use `cxMapClone()`
377 > to clone the first map into a new, empty, map, and then use `cxMapUnion()`.
378
379 Refer to the documentation of the [clone-function callback](allocator.h.md#clone-function) to learn how to implement it.
380
381 The _simple_ versions of the above functions use an internal shallow clone function
382 which uses `memcpy()` to copy the values.
383 If the destination map is storing pointers, this internal clone function uses the current default allocator to allocate the memory.
384
385 The functions return zero if and only if all clone operations were successful.
386
387 > It is perfectly possible to clone items into a map of a different type.
388 > For example, you can clone entries from a map that is just storing pointers (`CX_STORE_POINTERS`) to a map that
389 > allocates the memory for the objects (and vice versa).
390
391 > The maps passed to the above functions must all be different.
392 > Passing the same pointer for different map arguments may result in erroneous behavior.
393 >{style="warning"}
394
395 ## Dispose
396
397 ```C
398 #include <cx/map.h>
399
400 void cxMapFree(CxMap *map);
401 ```
402
403 The function `cxMapFree()` invokes the [destructor functions](collection.h.md#destructor-functions) for all elements
404 and then deallocates the entire memory for the map.
405
406 ## Implement own Map Structures
407
408 If the UCX [hash map](hash_map.h.md) implementation does not suit your needs,
409 you can also implement your own map.
410 To be compatible with the `CxMap` interface, it needs to store key/value pairs of the following form.
411
412 ```C
413 typedef struct {
414 const CxHashKey *key;
415 void *value;
416 } CxMapEntry;
417 ```
418
419 When you are declaring your map structure, a `CxMap` member must be embedded as the first member of this structure.
420 Secondly, you need to implement the `cx_map_class` and assign it when allocating your map.
421
422 ```C
423 #include <cx/map.h>
424
425 typedef struct {
426 CxMap base;
427 // ... data members for storing CxMapEntry elements go here ...
428 } MyMap;
429
430 // declare the class - implement the functions somewhere
431 static cx_map_class my_map_class = {
432 my_map_destructor,
433 my_map_clear,
434 my_map_put,
435 my_map_get,
436 my_map_remove,
437 my_map_iterator,
438 };
439
440 // this function will create the map
441 CxMap *myMapCreate(const CxAllocator *allocator, size_t itemsize) {
442 if (allocator == NULL) {
443 allocator = cxDefaultAllocator;
444 }
445
446 // allocate memory
447 MyMap *map = cxCalloc(allocator, 1, sizeof(MyMap));
448 if (map == NULL) return NULL;
449
450 // initialize base members
451 map->base.cl = &my_map_class; // <--- assign class here
452 map->base.collection.allocator = allocator;
453 if (itemsize == CX_STORE_POINTERS) {
454 map->base.collection.elem_size = sizeof(void *);
455 map->base.collection.store_pointer = true;
456 } else {
457 map->base.collection.elem_size = itemsize;
458 }
459
460 // ... initialization of data members go here ...
461
462 return (CxMap *) map;
463 }
464 ```
465
466 The required behavior for the implementations is described in the following table.
467 You can always look at the source code of the UCX hash map to get inspiration.
468
469 | Function | Description |
470 |--------------|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
471 | `clear` | Invoke [destructor functions](collection.h.md#destructor-functions) on all elements and remove them from the map. |
472 | `deallocate` | Invoke destructor functions on all elements and deallocate the entire map memory. |
473 | `put` | Store an element in the map. If an element is already stored, invoke the destructor functions on that element and replace it with the new element. When the value pointer is `NULL`, only allocate memory without copying an existing value. Return `CxMapEntry` where the `key` is `NULL` when allocation fails. |
474 | `get` | Look up the specified key and return the associated value (or `NULL` if the key was not found). |
475 | `remove` | Remove an element from the map. If a target buffer is specified, copy the elements to that buffer. Otherwise, invoke the destructor functions for the element. If the key was not found in the map, return non-zero. |
476 | `iterator` | Return an iterator over the pairs, the keys, or the values, depending on the iterator type passed with the last argument. |
477
478 > In contrast to the list interface, there is no `cx_map_init()` function which automatically
479 > configures a wrapping mechanism when `CX_STORE_POINTERS` is used.
480 > That means, in the implementation of the above functions you must take care of distinguishing between
481 > maps that are storing pointers and that are storing elements yourself (if you want to support both).
482 >{style="note"}
483
484 <seealso>
485 <category ref="apidoc">
486 <a href="https://ucx.sourceforge.io/api/map_8h.html">map.h</a>
487 </category>
488 </seealso>
489
490