UNIXworkcode
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