docs/Writerside/topics/map.h.md

# Map Interface

Similar to the list interface, the map interface provides a common API for implementing maps.

UCX is shipped with a [hash map](hash_map.h.md) implementation of this interface. 

```C
#include <cx/hash_map.h>

CxMap *cxHashMapCreate(const CxAllocator *allocator,
        size_t itemsize, size_t buckets);
```

The function `cxHashMapCreate()` creates a new map where both the map structure
and the contained buckets are allocated by the specified `allocator`.

The map will store items of size `itemsize`.
You can use the `CX_STORE_POINTERS` macro for `itemsize` to indicate that the map shall store
pointers instead of actual items.

If you pass zero for the number of `buckets`,
the map is initialized with a default of 16 buckets; otherwise the specified number of buckets is allocated.

> If you want to lazy-initialize maps, you can use the global `cxEmptyMap` symbol as a placeholder instead of using a `NULL`-pointer.
> While you *must not* insert elements into that map, you can safely access this map or create iterators.
> This allows you to write clean code without checking for `NULL`-pointer everywhere.
> You still need to make sure that the placeholder is replaced with an actual map before inserting elements.

> All functions working with keys are implemented as generics, so that the following types are supported:
> `CxHashKey`, `cxstring`, `cxmutstr`, `const char*`, and `char*`.
> When we write `KeyType`, we mean any of these types.
> {style="note"}

## Examples

```C
#include <stdio.h> 
#include <cx/hash_map.h>

int main() {
    CxMap *contacts = cxHashMapCreate(NULL, CX_STORE_POINTERS, 0);

    // Build a small phone book
    cxMapPut(contacts, "John", "123-0815");
    cxMapPut(contacts, "Jane", "987-4711");
    cxMapPut(contacts, "Michelle", "555-3141");
    cxMapPut(contacts, "Oliver", "000-9999");
    
    // Retrieve a phone number
    const char *janes_phone = cxMapGet(contacts, "Jane");
    printf("The number of Jane is: %s\n", janes_phone);
    
    // Update number
    cxMapPut(contacts, "Jane", "987-1337");
    
    // Remove and retrieve number
    cxMapRemoveAndGet(contacts, "Jane", &janes_phone);
    printf("The number of Jane was: %s\n", janes_phone);
    janes_phone = cxMapGet(contacts, "Jane");
    if (janes_phone == NULL) printf("Jane's number was deleted.\n");

    // Iterate through the contact list
    CxMapIterator iter = cxMapIterator(contacts);
    cx_foreach(CxMapEntry *, entry, iter) {
        cxstring name = cx_hash_key_as_string(entry->key);
        const char *phone = entry->value;
        printf("%" CX_PRIstr ": %s\n", CX_SFMT(name), phone);
    }

    cxMapFree(contacts);

    return 0;
}
```

The above example illustrates basic operations with a map.

In the first part we add several entries to the map.
Then the example shows retrieval, updating, and removal of information.
The last part shows how to iterate over the pairs inside the map and how to recover the string from the key.

In real-world situations, however, it is quite unlikely that you will use a map to store string literals.
The next example shows a more realistic program, where it is necessary to store strings based on user input.

```C
#include <stdio.h> 
#include <string.h>
#include <cx/hash_map.h>

int main() {
    // store strings in the map...
    CxMap *contacts = cxHashMapCreate(NULL, sizeof(cxmutstr), 0);
    // ...which are automatically freed when removed
    cxSetDestructor(contacts, cx_strfree);
    
    // build a small interactive program
    const unsigned buffer_size = 256;
    char input[buffer_size];
    bool running = true;

    while (running) {
        puts("\n*** Contacts - Menu ***");
        puts("1) Add entry");
        puts("2) Look up entry");
        puts("3) Remove entry");
        puts("4) Show all entries");
        puts("0) Exit");
        fputs("> ", stdout);

        if (fgets(input, buffer_size, stdin)) {
            if (input[1] != '\n') {
                puts("Please select a menu item.\n");
            } else if (input[0] == '1') {
                fputs("Name > ", stdout);
                if (fgets(input, buffer_size, stdin)) {
                    // Copy the name (alternative: use 2nd input buf) 
                    cxmutstr name = cx_strdup(
                            cx_strn(input, strcspn(input, "\n")));
                    fputs("Phone > ", stdout);
                    if (fgets(input, buffer_size, stdin)) {
                        // add the entry, note that only the contents
                        // of the cxmutstr are copied, not the string
                        // data - therefore we have to call cx_strdup
                        cxmutstr phone = cx_strdup(
                                cx_strn(input, strcspn(input, "\n")));
                        // note, that we can simply use the cxmutstr
                        // for the name as key, because cxMapPut uses
                        // generic selection
                        cxMapPut(contacts, name, &phone);
                    }
                    cx_strfree(&name);
                }
            } else if (input[0] == '2') {
                fputs("Name > ", stdout);
                if (fgets(input, buffer_size, stdin)) {
                    // Look up the name
                    input[strcspn(input, "\n")] = '\0';
                    cxmutstr *phone = cxMapGet(contacts, input);
                    if (phone == NULL) {
                        puts("No record.");
                    } else {
                        printf("Result: %" CX_PRIstr "\n",
                                CX_SFMT(*phone));
                    }
                }
            } else if (input[0] == '3') {
                fputs("Name > ", stdout);
                if (fgets(input, buffer_size, stdin)) {
                    // Remove the entry
                    // Since we registered cx_strfree as destructor,
                    // the memory is automatically freed
                    input[strcspn(input, "\n")] = '\0';
                    if (cxMapRemove(contacts, input)) {
                        puts("No such record.");
                    } else {
                        puts("Removed.");
                    }
                }
            } else if (input[0] == '4') {
                // Almost the same iteration loop as above ...
                CxMapIterator iter = cxMapIterator(contacts);
                cx_foreach(CxMapEntry *, entry, iter) {
                    cxstring name = cx_hash_key_as_string(entry->key);
                    // ... except that here we get cxmutstr*
                    cxmutstr *phone = entry->value;
                    printf("%" CX_PRIstr ": %" CX_PRIstr "\n",
                        CX_SFMT(name), CX_SFMT(*phone));
                }
            } else if (input[0] == '0') {
                running = false;
            } else {
                puts("Please select a menu item.\n");
            }
        } else {
            running = false;
        }
    }

    // this will free all remaining strings that are in the map
    cxMapFree(contacts);

    return 0;
}
```

## Insert

```C
#include <cx/map.h>

int cxMapPut(CxMap *map, KeyType key, void *value);

void *cxMapEmplace(CxMap *map, KeyType key);
```

The function `cxMapPut()` stores the specified `key` / `value` pair 
and returns zero if the element was successfully put into the map and non-zero otherwise.

The key is always copied.
The behavior for the value is dependent on whether the map is storing pointers.
If it is storing pointers, the `value` pointer is directly stored in the map.
Otherwise, the memory pointed to by `value` is copied, using the element size of the collection.

The function `cxMapEmplace()` is similar to `cxMapPut()`, but instead of adding an existing value to the map,
it returns a pointer to newly allocated memory for the value.
The memory is allocated using the allocator of the map.
If the map is storing pointers, the allocated memory will only be that for a pointer.
Otherwise, the memory is allocated using the known element size.

Both functions, if an element is already associated with the specified key, replace the existing element.
If [destructor functions](collection.h.md#destructor-functions) are registered,
they are invoked for the old element before it is replaced.

## Access

```C
#include <cx/map.h>

void *cxMapGet(CxMap *map, KeyType key);

bool cxMapContains(CxMap *map, KeyType key);

size_t cxMapSize(const CxMap *map);
```

With the function `cxMapGet()` you can retrieve a value stored under the specified `key`.
If there is no such value, this function returns `NULL`.

The function `cxMapContains()` returns `true` if the map contains an element with the specified `key`,
and `false` otherwise.

The function `cxMapSize()` returns how many key/value-pairs are currently stored in the map.

## Remove

```C
#include <cx/map.h>

int cxMapRemove(CxMap *map, KeyType key);

int cxMapRemoveAndGet(CxMap *map, KeyType key, void* targetbuf);

void cxMapClear(CxMap *map);
```

The function `cxMapRemove()` retrieves and removes a value stored under the specified `key`.
If [destructor functions](collection.h.md#destructor-functions) are registered, they are called before removal.

On the other hand, `cxMapRemoveAndGet()` does not invoke the destructor functions 
and instead copies the value into the `targetbuf`, which must be large enough to hold the value.

In either case, the functions return zero when an element was found under the specified key, and non-zero otherwise.

The function `cxMapClear()` removes all elements from the map, invoking the destructor functions for each of them. 

## Iterators

```C
#include <cx/map.h>

CxMapIterator cxMapIterator(const CxMap *map);

CxMapIterator cxMapIteratorKeys(const CxMap *map);

CxMapIterator cxMapIteratorValues(const CxMap *map);
```

The above functions create iterators over the
pairs, keys, or values of the specified `map`, respectively.

Iterators over pairs yield elements of the type `CxMapEntry*` which is a struct containing a pointer to the `key` and the value, respectively.

Iterators over keys yield elements of the type `const CxHashKey*` (cf. [CxHashKey documentation](hash_key.h.md)).

The behavior of iterators over values depends on the concrete implementation.
Implementations are encouraged to support `CX_STORE_POINTERS`.
If used, the `void*` elements the iterator yields shall be directly the stored pointers.
Otherwise, the iterator shall yield pointers to the map's memory where the value is stored.

It is always safe to call the above functions on a `NULL`-pointer.
In that case, the returned iterator will behave like an iterator over an empty map.

## Compare

```C
#include <cx/map.h>

int cxMapCompare(const CxMap *map, const CxMap *other);
```

Arbitrary maps can be compared with `cxMapCompare()`.
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).

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.
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.
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.

## Clone

```C
#include <cx/allocator.h>

typedef void*(cx_clone_func)(
        void *target, const void *source,
        const CxAllocator *allocator,
        void *data);

#include <cx/map.h>

int cxMapClone(CxMap *dst, const CxMap *src,
        cx_clone_func clone_func,
        const CxAllocator *clone_allocator,
        void *data);

int cxMapCloneShallow(CxMap *dst, const CxMap *src);
        
int cxMapDifference(CxMap *dst,
        const CxMap *minuend, const CxMap *subtrahend,
        cx_clone_func clone_func,
        const CxAllocator *clone_allocator,
        void *data);

int cxMapDifferenceShallow(CxMap *dst,
        const CxMap *minuend, const CxMap *subtrahend);

int cxMapListDifference(CxMap *dst,
        const CxMap *src, const CxList *keys,
        cx_clone_func clone_func,
        const CxAllocator *clone_allocator,
        void *data);

int cxMapListDifferenceShallow(CxMap *dst,
        const CxMap *src, const CxList *keys);

int cxMapIntersection(CxMap *dst,
        const CxMap *src, const CxMap *other,
        cx_clone_func clone_func,
        const CxAllocator *clone_allocator,
        void *data);

int cxMapIntersectionShallow(CxMap *dst,
        const CxMap *src, const CxMap *other);

int cxMapListIntersection(CxMap *dst,
        const CxMap *src, const CxList *keys,
        cx_clone_func clone_func,
        const CxAllocator *clone_allocator,
        void *data);

int cxMapListIntersectionShallow(CxMap *dst,
        const CxMap *src, const CxList *keys);

int cxMapUnion(CxMap *dst, const CxMap *src,
        cx_clone_func clone_func,
        const CxAllocator *clone_allocator,
        void *data);

int cxMapUnionShallow(CxMap *dst, const CxMap *src);
```

With `cxMapClone()` you can create deep copies of the values in one map and insert them into another map.
The destination map does not need to be empty.
But when a key already exists in the destination map, the value is overwritten with the clone from the source map.
If the destination map has destructors defined, they are called for the replaced element.

The functions `cxMapDifference()` and `cxMapListDifference()` are similar to `cxMapClone()`
except that they only clone an element from the source map, when the key is _not_ contained in the
other map (or list, respectively).
This is equivalent to computing the set difference for the set of keys.
Likewise, `cxMapIntersection()` and `cxMapListIntersection()` only clone an element from the source map 
when the key is contained in _both_ collections.
The function `cxMapUnion()` only clones elements from `src` to `dst` when their key is not present in `dst`.

> The function `cxMapUnion()` does not operate on three maps for the sake of simplicity.
> If you want to combine two maps without modifying either of them, you can first use `cxMapClone()`
> to clone the first map into a new, empty, map, and then use `cxMapUnion()`.

Refer to the documentation of the [clone-function callback](allocator.h.md#clone-function) to learn how to implement it.

The _simple_ versions of the above functions use an internal shallow clone function
which uses `memcpy()` to copy the values.
If the destination map is storing pointers, this internal clone function uses the current default allocator to allocate the memory.

The functions return zero if and only if all clone operations were successful.

> It is perfectly possible to clone items into a map of a different type.
> For example, you can clone entries from a map that is just storing pointers (`CX_STORE_POINTERS`) to a map that
> allocates the memory for the objects (and vice versa).

> The maps passed to the above functions must all be different.
> Passing the same pointer for different map arguments may result in erroneous behavior.
>{style="warning"}

## Dispose

```C
#include <cx/map.h>

void cxMapFree(CxMap *map);
```

The function `cxMapFree()` invokes the [destructor functions](collection.h.md#destructor-functions) for all elements 
and then deallocates the entire memory for the map.  

## Implement own Map Structures 

If the UCX [hash map](hash_map.h.md) implementation does not suit your needs,
you can also implement your own map.
To be compatible with the `CxMap` interface, it needs to store key/value pairs of the following form.

```C
typedef struct {
    const CxHashKey *key;
    void *value;
} CxMapEntry;
```

When you are declaring your map structure, a `CxMap` member must be embedded as the first member of this structure.
Secondly, you need to implement the `cx_map_class` and assign it when allocating your map.

```C
#include <cx/map.h>

typedef struct {
    CxMap base;
    // ... data members for storing CxMapEntry elements go here ...
} MyMap;

// declare the class - implement the functions somewhere 
static cx_map_class my_map_class = {
        my_map_destructor,
        my_map_clear,
        my_map_put,
        my_map_get,
        my_map_remove,
        my_map_iterator,
};

// this function will create the map
CxMap *myMapCreate(const CxAllocator *allocator, size_t itemsize) {
    if (allocator == NULL) {
        allocator = cxDefaultAllocator;
    }

    // allocate memory
    MyMap *map = cxCalloc(allocator, 1, sizeof(MyMap));
    if (map == NULL) return NULL;

    // initialize base members
    map->base.cl = &my_map_class; // <--- assign class here
    map->base.collection.allocator = allocator;
    if (itemsize == CX_STORE_POINTERS) {
        map->base.collection.elem_size = sizeof(void *);
        map->base.collection.store_pointer = true;
    } else {
        map->base.collection.elem_size = itemsize;
    }
    
    // ... initialization of data members go here ...

    return (CxMap *) map;
}
```

The required behavior for the implementations is described in the following table.
You can always look at the source code of the UCX hash map to get inspiration.

| Function     | Description                                                                                                                                                                                                                                                                                                       |
|--------------|-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| `clear`      | Invoke [destructor functions](collection.h.md#destructor-functions) on all elements and remove them from the map.                                                                                                                                                                                                 |
| `deallocate` | Invoke destructor functions on all elements and deallocate the entire map memory.                                                                                                                                                                                                                                 |
| `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. |
| `get`        | Look up the specified key and return the associated value (or `NULL` if the key was not found).                                                                                                                                                                                                                   |
| `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.                                                                                              |
| `iterator`   | Return an iterator over the pairs, the keys, or the values, depending on the iterator type passed with the last argument.                                                                                                                                                                                         |

> In contrast to the list interface, there is no `cx_map_init()` function which automatically
> configures a wrapping mechanism when `CX_STORE_POINTERS` is used.
> That means, in the implementation of the above functions you must take care of distinguishing between
> maps that are storing pointers and that are storing elements yourself (if you want to support both).
>{style="note"}

<seealso>
<category ref="apidoc">
<a href="https://ucx.sourceforge.io/api/map_8h.html">map.h</a>
</category>
</seealso>