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.

## Overview

<warning>
TODO: example
</warning>

> 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 cx_map_entry_s {
    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>