Mercurial > hg > ucx / file revision

# 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);

CxMap *cxHashMapCreateSimple(size_t itemsize);
```

The function `cxHashMapCreate()` creates a new map where both the map structure
and the contained buckets are allocated by the specified `allocator`.
The default stdlib allocator is used in `cxHashMapCreateSimple()`.

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`, or use `cxHashMapSimple()`,
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.

## Examples

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

int main() {
    CxMap *contacts = cxHashMapCreateSimple(CX_STORE_POINTERS);

    // 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_strn(entry->key->data, entry->key->len);
        const char *phone = entry->value;
        printf("%.*s: %s\n", (int) name.length, name.ptr, 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 of 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 = cxHashMapCreateSimple(sizeof(cxmutstr));
    // ...which are automatically freed when removed
    cxDefineDestructor(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: %.*s\n",
                            (int) phone->length, phone->ptr);
                    }
                }
            } 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_strn(entry->key->data,
                                            entry->key->len);
                    // ... except that here we get cxmutstr*
                    cxmutstr *phone = entry->value;
                    printf("%.*s: %.*s\n",
                        (int) name.length, name.ptr,
                        (int) phone->length, phone->ptr);
                }
            } 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;
}
```

> In the following Sections, the type for the key is denoted `KeyType`.
> All functions are implemented as generics, so that the following types are supported:
> `CxHashKey`, `cxstring`, `cxmutstr`, `const char*`, and `char*`.
> {style="note"}

## Insert

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

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

The function `cxMapPut()` stores the specified `key` / `value` pair.

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.

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

This function returns zero if the element was successfully put into the map and non-zero otherwise.

## Access

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

void *cxMapGet(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 `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 sufficiently large 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);

CxMapIterator cxMapMutIterator(CxMap *map);

CxMapIterator cxMapMutIteratorKeys(CxMap *map);

CxMapIterator cxMapMutIteratorValues(CxMap *map);
```

The above functions create a ([mutating](iterator.h.md#mutating-iterators)) iterator over the
pairs, keys, or values of the specified `map`, respectively.

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

Iterators over keys yield elements of 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.

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

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

<warning>
TODO: example
</warning>

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. Return non-zero when allocating memory 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>