smap.h File Reference

Generic hashmap implementation. More...

Macros
#define	VTM_SMAP_STRUCT(NODE_TYPE, BUCKETS)
#define	VTM_SMAP_INIT(NAME, KEY_TYPE, FREE_FN)
#define	VTM_SMAP_SET_KEY_FN(NAME, HASH_FN, CMP_FN)
#define	VTM_SMAP_INDEX(NAME, KEY_PTR)   (NAME).fn_key_hash(&((KEY_PTR)->data)) % VTM_ARRAY_LEN(NAME.buckets)
#define	VTM_SMAP_FREE_NODE(NAME, NODE_PTR)
#define	VTM_SMAP_PUT(NAME, NODE_TYPE, NODE_PTR)
#define	VTM_SMAP_GET(NAME, NODE_TYPE, KEY_PTR, OUT_PTR)
#define	VTM_SMAP_REMOVE(NAME, NODE_TYPE, KEY_PTR, OUT_REMOVED)
#define	VTM_SMAP_FOR_EACH_MOD(NAME, BC, NODE_PTR, NEXT_PTR)
#define	VTM_SMAP_FOR_EACH(NAME, BC, NODE_PTR)
#define	VTM_SMAP_GET_SIZE(NAME, BC, NODE_PTR, COUNTER)
#define	VTM_SMAP_CLEAR(NAME, NODE_TYPE)

Macro Definition Documentation

#define VTM_SMAP_STRUCT	(		NODE_TYPE,
			BUCKETS
	)

Value:

struct {                                                     \
        NODE_TYPE* buckets[BUCKETS];                             \
		vtm_hash_elem_fn fn_key_hash;                            \
		vtm_elem_cmp_fn fn_key_cmp;                              \
        void (*fn_free_node)(NODE_TYPE *node);                   \
    }

Defines the struct that holds the map.

The NODE_TYPE struct must meet following requirements:

• a member with type "struct vtm_variant" named "key"
• a member with type "NODE_TYPE*" named "next"

Parameters

NODE_TYPE	name of the struct whose instances are stored as entries in the map
BUCKETS	the number of hash buckets used by the map

#define VTM_SMAP_INIT	(		NAME,
			KEY_TYPE,
			FREE_FN
	)

Value:

do {                                                         \
        size_t i;                                                \
        for (i=0; i < VTM_ARRAY_LEN(NAME.buckets); i++) {        \
            NAME.buckets[i] = NULL;                              \
        }                                                        \
        NAME.fn_key_hash = vtm_hash_elem_get_fn(KEY_TYPE);       \
        NAME.fn_key_cmp = vtm_elem_get_cmp_fn(KEY_TYPE);         \
        NAME.fn_free_node = FREE_FN;                             \
    } while (0)

Initializes the map.

This function must be called, before any of the other functions can be used.

Parameters

NAME	the target map variable
KEY_TYPE	enum vtm_elem_type
FREE_FN	function pointer that is called when a entry is removed from the map

#define VTM_SMAP_SET_KEY_FN	(		NAME,
			HASH_FN,
			CMP_FN
	)

Value:

do {                                                         \
        NAME.fn_key_hash = HASH_FN;                              \
        NAME.fn_key_cmp = CMP_FN;                                \
    } while(0)

Sets an alternative hash function for the key.

Parameters

NAME	the target map variable
HASH_FN	function pointer to hash function
CMP_FN	function pointer to key comparison function

#define VTM_SMAP_INDEX	(		NAME,
			KEY_PTR
	)		(NAME).fn_key_hash(&((KEY_PTR)->data)) % VTM_ARRAY_LEN(NAME.buckets)

INTERNAL: Calculates the bucket index for given key.

#define VTM_SMAP_FREE_NODE	(		NAME,
			NODE_PTR
	)

Value:

do {                                                         \
        if (NAME.fn_free_node)                                   \
            NAME.fn_free_node(NODE_PTR);                         \
        free(NODE_PTR);                                          \
    } while (0)

INTERNAL: Frees the given node.

#define VTM_SMAP_PUT	(		NAME,
			NODE_TYPE,
			NODE_PTR
	)

Stores a new value in the map.

Existing values stored under the same key are removed first.

Parameters

NAME	the target map variable
NODE_TYPE	the type of the value
NODE_PTR	the value that should be stored

#define VTM_SMAP_GET	(		NAME,
			NODE_TYPE,
			KEY_PTR,
			OUT_PTR
	)

Value:

do {                                                         \
        size_t index;                                            \
        index = VTM_SMAP_INDEX(NAME, KEY_PTR);                   \
        if (NAME.buckets[index] != NULL) {                       \
            NODE_TYPE *cur;                                      \
            cur = NAME.buckets[index];                           \
            for(; cur != NULL; cur = cur->next) {                \
                if (NAME.fn_key_cmp(&(cur->key.data),            \
                     &((KEY_PTR)->data))) {                      \
                    OUT_PTR = cur;                               \
                    break;                                       \
                }                                                \
            }                                                    \
        }                                                        \
    } while (0)

Retrieves a stored value from the map.

Parameters

	NAME	the target map variable
	NODE_TYPE	the type of the value
	KEY_PTR	pointer to the key
[out]	OUT_PTR	the retrieved value node

#define VTM_SMAP_REMOVE	(		NAME,
			NODE_TYPE,
			KEY_PTR,
			OUT_REMOVED
	)

Value:

do {                                                         \
        size_t index;                                            \
        OUT_REMOVED = false;                                     \
        index = VTM_SMAP_INDEX(NAME, KEY_PTR);                   \
        if (NAME.buckets[index] != NULL) {                       \
            NODE_TYPE *cur;                                      \
            NODE_TYPE **prev;                                    \
            prev = NULL;                                         \
            cur = NAME.buckets[index];                           \
            while (cur) {                                        \
                if (NAME.fn_key_cmp(&(cur->key.data),            \
                     &((KEY_PTR)->data))) {                      \
                    if (prev)                                    \
                        (*prev)->next = cur->next;               \
                    else                                         \
                        NAME.buckets[index] = cur->next;         \
					VTM_SMAP_FREE_NODE(NAME, cur);               \
                    OUT_REMOVED = true;                          \
                    break;                                       \
                }                                                \
                prev = &cur;                                     \
                cur = cur->next;                                 \
            }                                                    \
        }                                                        \
    } while (0)

Removes a value from the map.

Parameters

	NAME	the target map variable
	NODE_TYPE	the type of the value
	KEY_PTR	pointer to the key
[out]	OUT_REMOVED	true if the value was found and removed

#define VTM_SMAP_FOR_EACH_MOD	(		NAME,
			BC,
			NODE_PTR,
			NEXT_PTR
	)

Value:

for (BC=0; BC < VTM_ARRAY_LEN(NAME.buckets); BC++)           \
        for (NODE_PTR = NAME.buckets[BC],                        \
            NEXT_PTR = NODE_PTR ? NODE_PTR->next : NULL;         \
            NODE_PTR != NULL; NODE_PTR = NEXT_PTR,               \
            NEXT_PTR = NEXT_PTR ? NEXT_PTR->next : NULL)

Iterates through all stored values and allows modifications of the map.

Parameters

	NAME	the target map variable
	BC	bucket counter variable
[out]	NODE_PTR	holds current value
[out]	NEXT_PTR	hold next value

#define VTM_SMAP_FOR_EACH	(		NAME,
			BC,
			NODE_PTR
	)

Value:

for (BC=0; BC < VTM_ARRAY_LEN(NAME.buckets); BC++)           \
        for (NODE_PTR=NAME.buckets[BC]; NODE_PTR != NULL;        \
            NODE_PTR = NODE_PTR->next)

Iterates through all stored values.

Parameters

	NAME	the target map variable
	BC	bucket counter variable
[out]	NODE_PTR	holds current value

#define VTM_SMAP_GET_SIZE	(		NAME,
			BC,
			NODE_PTR,
			COUNTER
	)

Value:

VTM_SMAP_FOR_EACH(NAME, BC, NODE_PTR)                        \
        COUNTER++

Retrieves the number of stored values.

Parameters

	NAME	the target map variable
	BC	bucket counter variable
	NODE_PTR	pointer to value type
[out]	COUNTER	holds the result

#define VTM_SMAP_CLEAR	(		NAME,
			NODE_TYPE
	)

Value:

do {                                                         \
        size_t bc;                                               \
        bc = 0;                                                  \
        NODE_TYPE *ptr;                                          \
        NODE_TYPE *next;                                         \
		VTM_SMAP_FOR_EACH_MOD(NAME, bc, ptr, next) {             \
			VTM_SMAP_FREE_NODE(NAME, ptr);                       \
        }                                                        \
        for (bc=0; bc < VTM_ARRAY_LEN(NAME.buckets); bc++)       \
            NAME.buckets[bc] = NULL;                             \
    } while (0)

Removes all values from the map.

Parameters

NAME	the target map variable
NODE_TYPE	the type of the values