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