set.h File Reference

Implementation of a set container. More...

#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include "cmagic/memory.h"
#include "cmagic/utils.h"

Go to the source code of this file.

Classes
struct	cmagic_set_iterator_t
struct	cmagic_set_insert_result_t
	Set insertion result. More...

Macros
#define	CMAGIC_SET(key_type)   key_type*
	Convenient alias for type*. Returned type of CMAGIC_SET_NEW. More...
#define	CMAGIC_SET_NEW(key_type, key_comparator, alloc_packet)   ((CMAGIC_SET(key_type))cmagic_set_new(sizeof(key_type), (key_comparator), (alloc_packet)))
	Allocates and returns an address of a newly created empty set. More...
#define	CMAGIC_SET_FREE(cmagic_set)   cmagic_set_free((void*)(cmagic_set))
	Frees the resources allocated by the set before. More...
#define	CMAGIC_SET_ALLOCATE(cmagic_set, key)
	Allocates space for a new element but does not initialize it. More...
#define	CMAGIC_SET_INSERT(cmagic_set, key)
	Allocates space for a new element and initializes it with data under key. More...
#define	CMAGIC_SET_ERASE_EXT(cmagic_set, key, destructor)
	Extended version of CMAGIC_SET_ERASE. More...
#define	CMAGIC_SET_ERASE(cmagic_set, key)   CMAGIC_SET_ERASE_EXT(cmagic_set, key, NULL)
	Removes a single element from the set. More...
#define	CMAGIC_SET_CLEAR(cmagic_set)   cmagic_set_clear((void*)(cmagic_set))
	Removes all elements from the set. More...
#define	CMAGIC_SET_SIZE(cmagic_set)   cmagic_set_size((void*)(cmagic_set))
	Returns the number of elements in the set. More...
#define	CMAGIC_SET_FIRST(cmagic_set)   cmagic_set_first((void*)(cmagic_set))
	Return iterator to the first element in set. More...
#define	CMAGIC_SET_LAST(cmagic_set)   cmagic_set_last((void*)(cmagic_set))
	Return iterator to the last element in set. More...
#define	CMAGIC_SET_ITERATOR_NEXT(iterator)   cmagic_set_iterator_next(iterator)
	Returns iterator to the next element in container. More...
#define	CMAGIC_SET_ITERATOR_PREV(iterator)   cmagic_set_iterator_prev(iterator)
	Returns iterator to the previous element in container. More...
#define	CMAGIC_SET_FIND(cmagic_set, key)
	Searches the container for an element equivalent to key and returns an iterator to it if found, otherwise it returns NULL. More...
#define	CMAGIC_SET_GET_KEY(key_type, iterator)   (assert(iterator), assert((iterator)->key), *((const key_type*)(iterator)->key))
	Helper macro for retrieving the key value from the iterator. More...
#define	CMAGIC_SET_GET_ALLOC_PACKET(cmagic_set)   cmagic_set_get_alloc_packet((void*)(cmagic_set))
	Retrieves cmagic_memory_alloc_packet_t associated with the set. More...

Typedefs
typedef int(*	cmagic_set_key_comparator_t) (const void *key1, const void *key2)
	Pointer to a function that compares two elements. More...
typedef void(*	cmagic_set_erase_destructor_t) (void *key)
	User defined additional tasks to be executed right before key deletion. More...

Detailed Description

Implementation of a set container.

Please use provided macros instead of raw functions to gain additional type checks.

Macro Definition Documentation

CMAGIC_SET

#define CMAGIC_SET

(

key_type

)

key_type*

Convenient alias for type*. Returned type of CMAGIC_SET_NEW.

Parameters

type	type of set elements

CMAGIC_SET_ALLOCATE

#define CMAGIC_SET_ALLOCATE	(		cmagic_set,
			key
	)

Value:

(CMAGIC_UTILS_ASSERT_SAME_TYPE(*(cmagic_set), *(key)), \
    cmagic_set_allocate((void*)(cmagic_set), (key)))

Allocates space for a new element but does not initialize it.

New element is allocated only if it doesn't already exist in the set.

Warning

The new element must be initialized right after calling this function. Especially it must be ready then to call cmagic_set_key_comparator_t on it and return the same value as for key. Otherwise the set will be in an undefined state.

Parameters

cmagic_set	a set allocated before with CMAGIC_SET_NEW
key	pointer to the key value, needed to place a new element in the right place in the internal binary tree

Returns

cmagic_set_insert_result_t pointing to the new or already existing element

CMAGIC_SET_CLEAR

#define CMAGIC_SET_CLEAR

(

cmagic_set

)

cmagic_set_clear((void*)(cmagic_set))

Removes all elements from the set.

Parameters

cmagic_set

a set allocated before with CMAGIC_SET_NEW

CMAGIC_SET_ERASE

#define CMAGIC_SET_ERASE	(		cmagic_set,
			key
	)		CMAGIC_SET_ERASE_EXT(cmagic_set, key, NULL)

Removes a single element from the set.

Parameters

cmagic_set	a set allocated before with CMAGIC_SET_NEW
key	pointer to a value to be removed from the set. This function compares by a value, the key doesn't have to be an address of the original key. Does nothing if the element doesn't exist in the set.

CMAGIC_SET_ERASE_EXT

#define CMAGIC_SET_ERASE_EXT	(		cmagic_set,
			key,
			destructor
	)

Value:

(CMAGIC_UTILS_ASSERT_SAME_TYPE(*(cmagic_set), *(key)), \
    cmagic_set_erase((void*)(cmagic_set), (key), (destructor)))

Extended version of CMAGIC_SET_ERASE.

Parameters

cmagic_set	a set allocated before with CMAGIC_SET_NEW
key	pointer to a value to be removed from the set. This function compares by a value, the key doesn't have to be an address of the original key. Does nothing if the element doesn't exist in the set.
destructor	function of type cmagic_set_erase_destructor_t to be called on the key right before deleting it

CMAGIC_SET_FIND

#define CMAGIC_SET_FIND	(		cmagic_set,
			key
	)

Value:

(CMAGIC_UTILS_ASSERT_SAME_TYPE(*(cmagic_set), *(key)), \
    cmagic_set_find((void*)(cmagic_set), (key)))

Searches the container for an element equivalent to key and returns an iterator to it if found, otherwise it returns NULL.

Parameters

key	pointer to a value to be searched for

Returns

an iterator to the element, if key is found, or NULL otherwise

CMAGIC_SET_FIRST

#define CMAGIC_SET_FIRST

(

cmagic_set

)

cmagic_set_first((void*)(cmagic_set))

Return iterator to the first element in set.

Returns an iterator pointing to the first element in the set according to the order defined by cmagic_set_key_comparator_t.

Parameters

cmagic_set

a set allocated before with CMAGIC_SET_NEW

Returns

an iterator to the first element or NULL if the set is empty

CMAGIC_SET_FREE

#define CMAGIC_SET_FREE

(

cmagic_set

)

cmagic_set_free((void*)(cmagic_set))

Frees the resources allocated by the set before.

Must not use cmagic_set after free.

Parameters

cmagic_set

a set allocated before with CMAGIC_SET_NEW

CMAGIC_SET_GET_ALLOC_PACKET

#define CMAGIC_SET_GET_ALLOC_PACKET

(

cmagic_set

)

cmagic_set_get_alloc_packet((void*)(cmagic_set))

Retrieves cmagic_memory_alloc_packet_t associated with the set.

Parameters

cmagic_set

a set allocated before with CMAGIC_SET_NEW

Returns

cmagic_memory_alloc_packet_t associated with the set

CMAGIC_SET_GET_KEY

#define CMAGIC_SET_GET_KEY	(		key_type,
			iterator
	)		(assert(iterator), assert((iterator)->key), *((const key_type*)(iterator)->key))

Helper macro for retrieving the key value from the iterator.

Warning

iterator must not be NULL

Parameters

key_type	type of set elements to which the iterator points to
iterator	cmagic_set_iterator_t object

Returns

value of the key

CMAGIC_SET_INSERT

#define CMAGIC_SET_INSERT	(		cmagic_set,
			key
	)

Value:

(CMAGIC_UTILS_ASSERT_SAME_TYPE(*(cmagic_set), *(key)), \
    cmagic_set_insert((void*)(cmagic_set), (key)))

Allocates space for a new element and initializes it with data under key.

Parameters

cmagic_set	a set allocated before with CMAGIC_SET_NEW
key	pointer to the key value

Returns

cmagic_set_insert_result_t pointing to the new or already existing element

CMAGIC_SET_ITERATOR_NEXT

#define CMAGIC_SET_ITERATOR_NEXT

(

iterator

)

cmagic_set_iterator_next(iterator)

Returns iterator to the next element in container.

Parameters

iterator

cmagic_set_iterator_t object

Returns

iterator to the next element or NULL if iterator was the last element in container

CMAGIC_SET_ITERATOR_PREV

#define CMAGIC_SET_ITERATOR_PREV

(

iterator

)

cmagic_set_iterator_prev(iterator)

Returns iterator to the previous element in container.

Parameters

iterator

cmagic_set_iterator_t object

Returns

iterator to the previous element or NULL if iterator was the first element in container

CMAGIC_SET_LAST

#define CMAGIC_SET_LAST

(

cmagic_set

)

cmagic_set_last((void*)(cmagic_set))

Return iterator to the last element in set.

Returns an iterator pointing to the last element in the set according to the order defined by cmagic_set_key_comparator_t.

Parameters

cmagic_set

a set allocated before with CMAGIC_SET_NEW

Returns

an iterator to the last element or NULL if the set is empty

CMAGIC_SET_NEW

#define CMAGIC_SET_NEW	(		key_type,
			key_comparator,
			alloc_packet
	)		((CMAGIC_SET(key_type))cmagic_set_new(sizeof(key_type), (key_comparator), (alloc_packet)))

Allocates and returns an address of a newly created empty set.

Parameters

key_type	type of set elements
key_comparator	function of type cmagic_set_key_comparator_t determining the order of the elements
alloc_packet	cmagic_memory_alloc_packet_t suite of dynamic memory managing functions

Returns

a new empty set

CMAGIC_SET_SIZE

#define CMAGIC_SET_SIZE

(

cmagic_set

)

cmagic_set_size((void*)(cmagic_set))

Returns the number of elements in the set.

Parameters

cmagic_set

a set allocated before with CMAGIC_SET_NEW

Returns

number of elements in the set

Typedef Documentation

cmagic_set_erase_destructor_t

typedef void(* cmagic_set_erase_destructor_t) (void *key)

User defined additional tasks to be executed right before key deletion.

Warning

Do not call free function on the key. It's called later internally by set implementation

Parameters

key	pointer to key to be deleted

cmagic_set_key_comparator_t

typedef int(* cmagic_set_key_comparator_t) (const void *key1, const void *key2)

Pointer to a function that compares two elements.

This function is called by the set implementation to compare two elements, which is necessary to properly construct and move inside its internal binary tree. Both arguments must be manually casted to a type corresponding to the type of the set. This function defines the order of the elements.

Parameters

key1	pointer to the first key value
key2	pointer to the second first key value

Returns

value	meaning
<0	The element pointed to by key1 goes before the element pointed to by key2
0	The element pointed to by key1 is equivalent to the element pointed to by key2
>0	The element pointed to by key1 goes after the element pointed to by key2