The Tree Map Interface. More...

#include "private/private_tree_map.h"
#include "types.h"

Include dependency graph for tree_map.h:

This graph shows which files directly or indirectly include this file:

Detailed Description

The Tree Map Interface.

A tree map offers insertion, removal, and searching with a strict bound of O(log(N)) time. The map is pointer stable. This map is suitable for realtime environments. Searching is a thread-safe read-only operation. Balancing modifications only occur upon insertion or removal.

To shorten names in the interface, define the following preprocessor directive at the top of your file.

#define TREE_MAP_USING_NAMESPACE_CCC

All types and functions can then be written without the CCC_ prefix.

Initialization Interface
Initialize the container with memory, callbacks, and permissions.
#define	CCC_tree_map_initialize(type_name, type_intruder_field_name, type_key_field_name, compare, allocate, context_data)
	Initializes the tree map at runtime or compile time.

#define	CCC_tree_map_from(type_intruder_field_name, type_key_field_name, compare, allocate, destroy, context_data, compound_literal_array...)
	Initializes a dynamic tree map at runtime.

Entry Interface
Obtain and operate on container entries for efficient queries when non-trivial control flow is needed.
#define	CCC_tree_map_swap_entry_wrap(map_pointer, type_intruder_pointer, temp_intruder_pointer)
	Invariantly inserts the key value wrapping type_intruder_pointer.

#define	CCC_tree_map_try_insert_wrap(map_pointer, type_intruder_pointer)
	Attempts to insert the key value wrapping type_intruder.

#define	CCC_tree_map_try_insert_with(map_pointer, key, type_compound_literal...)
	lazily insert type_compound_literal into the map at key if key is absent.

#define	CCC_tree_map_insert_or_assign_wrap(map_pointer, type_intruder_pointer...)
	Invariantly inserts or overwrites a user struct into the map.

#define	CCC_tree_map_insert_or_assign_with(map_pointer, key, type_compound_literal...)
	Inserts a new key value pair or overwrites the existing entry.

#define	CCC_tree_map_remove_key_value_wrap(map_pointer, output_intruder_pointer)
	Removes the key value in the map storing the old value, if present, in the struct containing output_intruder_pointer provided by the user.

#define	CCC_tree_map_entry_wrap(map_pointer, key_pointer)
	Obtains an entry for the provided key in the map for future use.

#define	CCC_tree_map_and_modify_with(map_pointer, type_name, closure_over_T...)
	Modify an Occupied entry with a closure over user type T.

#define	CCC_tree_map_or_insert_with(map_pointer, type_compound_literal...) CCC_private_tree_map_or_insert_with(map_pointer, type_compound_literal)
	Lazily insert the desired key value into the entry if it is Vacant.

#define	CCC_tree_map_insert_entry_with(map_pointer, type_compound_literal...) CCC_private_tree_map_insert_entry_with(map_pointer, type_compound_literal)
	Write the contents of the compound literal type_compound_literal to a node.

#define	CCC_tree_map_remove_entry_wrap(map_pointer)
	Remove the entry from the map if Occupied.

CCC_Entry	CCC_tree_map_swap_entry (CCC_Tree_map map, CCC_Tree_map_node type_intruder, CCC_Tree_map_node *temp_intruder)
	Invariantly inserts the key value wrapping type_intruder.

CCC_Entry	CCC_tree_map_try_insert (CCC_Tree_map map, CCC_Tree_map_node type_intruder)
	Attempts to insert the key value wrapping type_intruder.

CCC_Entry	CCC_tree_map_insert_or_assign (CCC_Tree_map map, CCC_Tree_map_node type_intruder)
	Invariantly inserts or overwrites a user struct into the map.

CCC_Entry	CCC_tree_map_remove_key_value (CCC_Tree_map map, CCC_Tree_map_node output_intruder)
	Removes the key value in the map storing the old value, if present, in the struct containing output_intruder provided by the user.

CCC_Tree_map_entry	CCC_tree_map_entry (CCC_Tree_map const map, void const key)
	Obtains an entry for the provided key in the map for future use.

CCC_Tree_map_entry *	CCC_tree_map_and_modify (CCC_Tree_map_entry entry, CCC_Type_modifier modify)
	Modifies the provided entry if it is Occupied.

CCC_Tree_map_entry *	CCC_tree_map_and_modify_context (CCC_Tree_map_entry entry, CCC_Type_modifier modify, void *context)
	Modifies the provided entry if it is Occupied.

void *	CCC_tree_map_or_insert (CCC_Tree_map_entry const entry, CCC_Tree_map_node type_intruder)
	Inserts the struct with handle type_intruder if the entry is Vacant.

void *	CCC_tree_map_insert_entry (CCC_Tree_map_entry const entry, CCC_Tree_map_node type_intruder)
	Inserts the provided entry invariantly.

CCC_Entry	CCC_tree_map_remove_entry (CCC_Tree_map_entry const *entry)
	Remove the entry from the map if Occupied.

void *	CCC_tree_map_unwrap (CCC_Tree_map_entry const *entry)
	Unwraps the provided entry to obtain a view into the map element.

CCC_Tribool	CCC_tree_map_insert_error (CCC_Tree_map_entry const *entry)
	Returns the Vacant or Occupied status of the entry.

CCC_Tribool	CCC_tree_map_occupied (CCC_Tree_map_entry const *entry)
	Provides the status of the entry should an insertion follow.

CCC_Entry_status	CCC_tree_map_entry_status (CCC_Tree_map_entry const *entry)
	Obtain the entry status from a container entry.

Iterator Interface
Obtain and manage iterators over the container.
#define	CCC_tree_map_equal_range_wrap(map_pointer, begin_and_end_key_pointers...)
	Returns a compound literal reference to the desired range. Amortized O(lg N).

#define	CCC_tree_map_equal_range_reverse_wrap( map_pointer, reverse_begin_and_reverse_end_key_pointers...)
	Returns a compound literal reference to the desired range_reverse. Amortized O(lg N).

CCC_Range	CCC_tree_map_equal_range (CCC_Tree_map const map, void const begin_key, void const *end_key)
	Return an iterable range of values from [begin_key, end_key). Amortized O(lg N).

CCC_Range_reverse	CCC_tree_map_equal_range_reverse (CCC_Tree_map const map, void const reverse_begin_key, void const *reverse_end_key)
	Return an iterable range_reverse of values from [begin_key, end_key). Amortized O(lg N).

void *	CCC_tree_map_begin (CCC_Tree_map const *map)
	Return the start of an inorder traversal of the map. Amortized O(lg N).

void *	CCC_tree_map_reverse_begin (CCC_Tree_map const *map)
	Return the start of a reverse inorder traversal of the map. Amortized O(lg N).

void *	CCC_tree_map_next (CCC_Tree_map const map, CCC_Tree_map_node const iterator_intruder)
	Return the next element in an inorder traversal of the map. O(1).

void *	CCC_tree_map_reverse_next (CCC_Tree_map const map, CCC_Tree_map_node const iterator_intruder)
	Return the reverse_next element in a reverse inorder traversal of the map. O(1).

void *	CCC_tree_map_end (CCC_Tree_map const *map)
	Return the end of an inorder traversal of the map. O(1).

void *	CCC_tree_map_reverse_end (CCC_Tree_map const *map)
	Return the reverse_end of a reverse inorder traversal of the map. O(1).

Container Types
Types available in the container interface.
typedef struct CCC_Tree_map	CCC_Tree_map
	A container for amortized O(lg N) search, insert, erase, ranges, and pointer stability.

typedef struct CCC_Tree_map_node	CCC_Tree_map_node
	The intrusive element of the user defined struct being stored in the map.

typedef union CCC_Tree_map_entry_wrap	CCC_Tree_map_entry
	A container specific entry used to implement the Entry Interface.

Membership Interface
Test membership or obtain references to stored user types directly.
CCC_Tribool	CCC_tree_map_contains (CCC_Tree_map const map, void const key)
	Searches the map for the presence of key.

void *	CCC_tree_map_get_key_value (CCC_Tree_map const map, void const key)
	Returns a reference into the map at entry key.

Deallocation Interface
Deallocate the container.
CCC_Result	CCC_tree_map_clear (CCC_Tree_map map, CCC_Type_destructor destroy)
	Pops every element from the map calling destructor if destructor is non-NULL. O(N).

State Interface
Obtain the container state.
CCC_Count	CCC_tree_map_count (CCC_Tree_map const *map)
	Returns the count of map occupied nodes.

CCC_Tribool	CCC_tree_map_is_empty (CCC_Tree_map const *map)
	Returns the size status of the map.

CCC_Tribool	CCC_tree_map_validate (CCC_Tree_map const *map)
	Validation of invariants for the map.

Macro Definition Documentation

◆ CCC_tree_map_and_modify_with

#define CCC_tree_map_and_modify_with	(	map_pointer,
		type_name,
		closure_over_T...
	)

Value:

    &(CCC_Tree_map_entry)                                                      \
    {                                                                          \
        CCC_private_tree_map_and_modify_with(map_pointer, type_name,           \
                                             closure_over_T)                   \
    }

Modify an Occupied entry with a closure over user type T.

Parameters

[in]	map_pointer	a pointer to the obtained entry.
[in]	type_name	the name of the user type stored in the container.
[in]	closure_over_T	the code to be run on the reference to user type T, if Occupied. This may be a semicolon separated list of statements to execute on T or a section of code wrapped in braces {code here} which may be preferred for formatting.

Returns: a compound literal reference to the modified entry if it was occupied or a vacant entry if it was vacant.

Note: T is a reference to the user type stored in the entry guaranteed to be non-NULL if the closure executes.

#define TREE_MAP_USING_NAMESPACE_CCC
// Increment the count if found otherwise do nothing.
Tree_map_entry *e =
    tree_map_and_modify_with(
        entry_wrap(&map, &k),
        Word,
        T->cnt++;
    );
// Increment the count if found otherwise insert a default value.
Word *w =
    tree_map_or_insert_with(
        tree_map_and_modify_with(
            entry_wrap(&map, &k),
            Word,
            { T->cnt++; }
        ),
        (Word){.key = k, .cnt = 1}
    );

Note that any code written is only evaluated if the entry is Occupied and the container can deliver the user type T. This means any function calls are lazily evaluated in the closure scope.

◆ CCC_tree_map_entry_wrap

#define CCC_tree_map_entry_wrap	(	map_pointer,
		key_pointer
	)

Value:

    &(CCC_Tree_map_entry)                                                      \
    {                                                                          \
        CCC_tree_map_entry((map_pointer), (key_pointer)).private               \
    }

Obtains an entry for the provided key in the map for future use.

Parameters

[in]	map_pointer	the map to be searched.
[in]	key_pointer	the key used to search the map matching the stored key type.

Returns: a compound literal reference to a specialized entry for use with other functions in the Entry Interface.

Warning: the contents of an entry should not be examined or modified. Use the provided functions, only.

An entry is a search result that provides either an Occupied or Vacant entry in the map. An occupied entry signifies that the search was successful. A Vacant entry means the search was not successful but a handle is gained to where in the map such an element should be inserted.

An entry is rarely useful on its own. It should be passed in a functional style to subsequent calls in the Entry Interface.

◆ CCC_tree_map_equal_range_reverse_wrap

#define CCC_tree_map_equal_range_reverse_wrap	(	map_pointer,
		reverse_begin_and_reverse_end_key_pointers...
	)

Value:

    &(CCC_Range_reverse)                                                       \
    {                                                                          \
        CCC_tree_map_equal_range_reverse(                                      \
            (map_pointer), (reverse_begin_and_reverse_end_key_pointers))       \
            .private                                                           \
    }

Returns a compound literal reference to the desired range_reverse. Amortized O(lg N).

Parameters

[in]	map_pointer	a pointer to the map.
[in]	reverse_begin_and_reverse_end_key_pointers	two pointers, the first to the start of the range_reverse the second to the end of the range_reverse.

Returns: a compound literal reference to the produced range_reverse associated with the enclosing scope. This reference is always non-NULL.

◆ CCC_tree_map_equal_range_wrap

#define CCC_tree_map_equal_range_wrap	(	map_pointer,
		begin_and_end_key_pointers...
	)

Value:

    &(CCC_Range)                                                               \
    {                                                                          \
        CCC_tree_map_equal_range((map_pointer), (begin_and_end_key_pointers))  \
            .private                                                           \
    }

Returns a compound literal reference to the desired range. Amortized O(lg N).

Parameters

[in]	map_pointer	a pointer to the map.
[in]	begin_and_end_key_pointers	two pointers, the first to the start of the range the second to the end of the range.

Returns: a compound literal reference to the produced range associated with the enclosing scope. This reference is always non-NULL.

◆ CCC_tree_map_from

#define CCC_tree_map_from	(	type_intruder_field_name,
		type_key_field_name,
		compare,
		allocate,
		destroy,
		context_data,
		compound_literal_array...
	)

Value:

    CCC_private_tree_map_from(type_intruder_field_name, type_key_field_name,   \
                              compare, allocate, destroy, context_data,        \
                              compound_literal_array)

Initializes a dynamic tree map at runtime.

Parameters

[in]	type_intruder_field_name	the name of the intrusive map elem field.
[in]	type_key_field_name	the name of the field in user type used as key.
[in]	compare	the key comparison function (see types.h).
[in]	allocate	the allocation function or NULL if allocation is banned.
[in]	destroy	the destructor function used to act on every node in case initialization of new nodes fails and map is emptied in a failure state.
[in]	context_data	a pointer to any context data for comparison or destruction.
[in]	compound_literal_array	the array of user types to insert into the map (e.g. (struct My_type[]){ {.key = 1, .val = 1}, {.key = 2, .val = 2}}).

Returns: the struct initialized tree map for direct assignment (e.g. CCC_Tree_map m = CCC_tree_map_from(...);) or an empty map if allocation fails.

Warning: If any node allocation fails while copying in the values in the compound literal array of user types, the map is cleared; if a destructor is provided, it is called on each node and they are freed using the provided allocate function.

◆ CCC_tree_map_initialize

#define CCC_tree_map_initialize	(	type_name,
		type_intruder_field_name,
		type_key_field_name,
		compare,
		allocate,
		context_data
	)

Value:

    CCC_private_tree_map_initialize(type_name, type_intruder_field_name,       \
                                    type_key_field_name, compare, allocate,    \
                                    context_data)

Initializes the tree map at runtime or compile time.

Parameters

[in]	type_name	the user type wrapping the intrusive element.
[in]	type_intruder_field_name	the name of the intrusive map elem field.
[in]	type_key_field_name	the name of the field in user type used as key.
[in]	compare	the key comparison function (see types.h).
[in]	allocate	the allocation function or NULL if allocation is banned.
[in]	context_data	a pointer to any context data for comparison or destruction.

Returns: the struct initialized tree map for direct assignment (i.e. CCC_Tree_map m = CCC_tree_map_initialize(...);).

◆ CCC_tree_map_insert_entry_with

#define CCC_tree_map_insert_entry_with	(	map_pointer,
		type_compound_literal...
	)	CCC_private_tree_map_insert_entry_with(map_pointer, type_compound_literal)

Write the contents of the compound literal type_compound_literal to a node.

Parameters

[in]	map_pointer	a pointer to the obtained entry.
[in]	type_compound_literal	the compound literal to write to a new slot.

Returns: a reference to the newly inserted or overwritten user type. NULL is returned if allocation failed or is not allowed when required.

◆ CCC_tree_map_insert_or_assign_with

#define CCC_tree_map_insert_or_assign_with	(	map_pointer,
		key,
		type_compound_literal...
	)

Value:

    &(CCC_Entry)                                                               \
    {                                                                          \
        CCC_private_tree_map_insert_or_assign_with(map_pointer, key,           \
                                                   type_compound_literal)      \
    }

Inserts a new key value pair or overwrites the existing entry.

Parameters

[in]	map_pointer	the pointer to the flat hash map.
[in]	key	the key to be searched in the map.
[in]	type_compound_literal	the compound literal to insert or use for overwrite.

Returns: a compound literal reference to the entry of the existing or newly inserted value. Occupied indicates the key existed, Vacant indicates the key was absent. Unwrapping in any case provides the current value unless an error occurs that prevents insertion. An insertion error will flag such a case.

Note that for brevity and convenience the user need not write the key to the lazy value compound literal as well. This function ensures the key in the compound literal matches the searched key.

◆ CCC_tree_map_insert_or_assign_wrap

#define CCC_tree_map_insert_or_assign_wrap	(	map_pointer,
		type_intruder_pointer...
	)

Value:

    &(CCC_Entry)                                                               \
    {                                                                          \
        CCC_tree_map_insert_or_assign((map_pointer), type_intruder_pointer)    \
            .private                                                           \
    }

Invariantly inserts or overwrites a user struct into the map.

Parameters

[in]	map_pointer	a pointer to the flat hash map.
[in]	type_intruder_pointer	the handle to the wrapping user type.

Returns: a compound literal reference to an entry. If Occupied an entry was overwritten by the new key value. If Vacant no prior map entry existed. An insert error is returned if insertion failed, in which case unwrapping yields NULL.

Note that this function can be used when the old user type is not needed but the information regarding its presence is helpful. The compound literal reference resides in the automatic storage of the calling scope, like a normal return by value; the reference is returned to enable function chaining.

◆ CCC_tree_map_or_insert_with

#define CCC_tree_map_or_insert_with	(	map_pointer,
		type_compound_literal...
	)	CCC_private_tree_map_or_insert_with(map_pointer, type_compound_literal)

Lazily insert the desired key value into the entry if it is Vacant.

Parameters

[in]	map_pointer	a pointer to the obtained entry.
[in]	type_compound_literal	the compound literal to construct in place if the entry is Vacant.

Returns: a reference to the unwrapped user type in the entry, either the unmodified reference if the entry was Occupied or the newly inserted element if the entry was Vacant. NULL is returned if resizing is required but fails or is not allowed.

Note that if the compound literal uses any function calls to generate values or other data, such functions will not be called if the entry is Occupied.

◆ CCC_tree_map_remove_entry_wrap

#define CCC_tree_map_remove_entry_wrap ( map_pointer )

Value:

    &(CCC_Entry)                                                               \
    {                                                                          \
        CCC_tree_map_remove_entry((map_pointer)).private                       \
    }

Remove the entry from the map if Occupied.

Parameters

[in] map_pointer a pointer to the map entry.

Returns: a compound literal reference to an entry containing NULL or a reference to the old entry. If Occupied an entry in the map existed and was removed. If Vacant, no prior entry existed to be removed.

Note that if allocation is permitted the old element is freed and the entry will contain a NULL reference. If allocation is prohibited the entry can be unwrapped to obtain the old user struct stored in the map and the user may free or use as needed.

◆ CCC_tree_map_remove_key_value_wrap

#define CCC_tree_map_remove_key_value_wrap	(	map_pointer,
		output_intruder_pointer
	)

Value:

    &(CCC_Entry)                                                               \
    {                                                                          \
        CCC_tree_map_remove_key_value((map_pointer),                           \
                                      (output_intruder_pointer))               \
            .private                                                           \
    }

Removes the key value in the map storing the old value, if present, in the struct containing output_intruder_pointer provided by the user.

Parameters

[in]	map_pointer	the pointer to the tree map.
[out]	output_intruder_pointer	the handle to the user type wrapping map elem.

Returns: a compound literal reference to the removed entry. If Occupied it may be unwrapped to obtain the old key value pair. If Vacant the key value pair was not stored in the map. If bad input is provided an input error is set.

Note that this function may write to the struct containing the second parameter and wraps it in an entry to provide information about the old value.

If allocation has been prohibited upon initialization then the entry returned contains the previously stored user type, if any, and nothing is written to the output_intruder_pointer. It is then the user's responsibility to manage their previously stored memory as they see fit.

◆ CCC_tree_map_swap_entry_wrap

#define CCC_tree_map_swap_entry_wrap	(	map_pointer,
		type_intruder_pointer,
		temp_intruder_pointer
	)

Value:

    &(CCC_Entry)                                                               \
    {                                                                          \
        CCC_tree_map_swap_entry((map_pointer), (type_intruder_pointer),        \
                                (temp_intruder_pointer))                       \
            .private                                                           \
    }

Invariantly inserts the key value wrapping type_intruder_pointer.

Parameters

[in]	map_pointer	the pointer to the tree map.
[in]	type_intruder_pointer	the handle to the user type wrapping map elem.
[in]	temp_intruder_pointer	handle to space for swapping in the old value, if present. The same user type stored in the map should wrap temp_intruder_pointer.

Returns: a compound literal reference to an entry. If Vacant, no prior element with key existed and the type wrapping temp_intruder_pointer remains unchanged. If Occupied the old value is written to the type wrapping temp_intruder_pointer and may be unwrapped to view. If more space is needed but allocation fails or has been forbidden, an insert error is set.

Note that this function may write to the struct containing temp_intruder_pointer and wraps it in an entry to provide information about the old value.

◆ CCC_tree_map_try_insert_with

#define CCC_tree_map_try_insert_with	(	map_pointer,
		key,
		type_compound_literal...
	)

Value:

    &(CCC_Entry)                                                               \
    {                                                                          \
        CCC_private_tree_map_try_insert_with(map_pointer, key,                 \
                                             type_compound_literal)            \
    }

lazily insert type_compound_literal into the map at key if key is absent.

Parameters

[in]	map_pointer	a pointer to the map.
[in]	key	the direct key r-value.
[in]	type_compound_literal	the compound literal specifying the value.

Returns: a compound literal reference to the entry of the existing or newly inserted value. Occupied indicates the key existed, Vacant indicates the key was absent. Unwrapping in any case provides the current value unless an error occurs that prevents insertion. An insertion error will flag such a case.

Note that for brevity and convenience the user need not write the key to the lazy value compound literal as well. This function ensures the key in the compound literal matches the searched key.

◆ CCC_tree_map_try_insert_wrap

#define CCC_tree_map_try_insert_wrap	(	map_pointer,
		type_intruder_pointer
	)

Value:

    &(CCC_Entry)                                                               \
    {                                                                          \
        CCC_tree_map_try_insert((map_pointer), (type_intruder_pointer))        \
            .private                                                           \
    }

Attempts to insert the key value wrapping type_intruder.

Parameters

[in]	map_pointer	the pointer to the map.
[in]	type_intruder_pointer	the handle to the user type wrapping map elem.

Returns: a compound literal reference to an entry. If Occupied, the entry contains a reference to the key value user type in the map and may be unwrapped. If Vacant the entry contains a reference to the newly inserted entry in the map. If more space is needed but allocation fails or has been forbidden, an insert error is set.

Typedef Documentation

◆ CCC_Tree_map

typedef struct CCC_Tree_map CCC_Tree_map

A container for amortized O(lg N) search, insert, erase, ranges, and pointer stability.

Warning: it is undefined behavior to access an uninitialized container.

A tree map can be initialized on the stack, heap, or data segment at runtime or compile time.

◆ CCC_Tree_map_entry

typedef union CCC_Tree_map_entry_wrap CCC_Tree_map_entry

A container specific entry used to implement the Entry Interface.

The Entry Interface offers efficient search and subsequent insertion, deletion, or value update based on the needs of the user.

◆ CCC_Tree_map_node

typedef struct CCC_Tree_map_node CCC_Tree_map_node

The intrusive element of the user defined struct being stored in the map.

It can be used in an allocating or non allocating container. If allocation is prohibited the container assumes the element is wrapped in pre-allocated memory with the appropriate lifetime and scope for the user's needs; the container does not allocate or free in this case. If allocation is allowed the container will handle copying the data wrapping the element to allocations and deallocating when necessary.

Function Documentation

◆ CCC_tree_map_and_modify()

CCC_Tree_map_entry * CCC_tree_map_and_modify	(	CCC_Tree_map_entry *	entry,
		CCC_Type_modifier *	modify
	)

Modifies the provided entry if it is Occupied.

Parameters

[in]	entry	the entry obtained from an entry function or macro.
[in]	modify	an update function in which the context argument is unused.

Returns: the updated entry if it was Occupied or the unmodified vacant entry.

This function is intended to make the function chaining in the Entry Interface more succinct if the entry will be modified in place based on its own value without the need of the context argument a CCC_Type_modifier can provide.

◆ CCC_tree_map_and_modify_context()

CCC_Tree_map_entry * CCC_tree_map_and_modify_context	(	CCC_Tree_map_entry *	entry,
		CCC_Type_modifier *	modify,
		void *	context
	)

Modifies the provided entry if it is Occupied.

Parameters

[in]	entry	the entry obtained from an entry function or macro.
[in]	modify	an update function that requires context data.
[in]	context	context data required for the update.

Returns: the updated entry if it was Occupied or the unmodified vacant entry.

This function makes full use of a CCC_Type_modifier capability, meaning a complete CCC_update object will be passed to the update function callback.

◆ CCC_tree_map_begin()

void * CCC_tree_map_begin ( CCC_Tree_map const * map )

Return the start of an inorder traversal of the map. Amortized O(lg N).

Parameters

[in] map a pointer to the map.

Returns: the oldest minimum element of the map.

◆ CCC_tree_map_clear()

CCC_Result CCC_tree_map_clear	(	CCC_Tree_map *	map,
		CCC_Type_destructor *	destroy
	)

Pops every element from the map calling destructor if destructor is non-NULL. O(N).

Parameters

[in]	map	a pointer to the map.
[in]	destroy	a destructor function if required. NULL if unneeded.

Returns: an input error if map points to NULL otherwise OK.

Note that if the map has been given permission to allocate, the destructor will be called on each element before it uses the provided allocator to free the element. Therefore, the destructor should not free the element or a double free will occur.

If the container has not been given allocation permission, then the destructor may free elements or not depending on how and when the user wishes to free elements of the map according to their own memory management schemes.

◆ CCC_tree_map_contains()

CCC_Tribool CCC_tree_map_contains	(	CCC_Tree_map const *	map,
		void const *	key
	)

Searches the map for the presence of key.

Parameters

[in]	map	the map to be searched.
[in]	key	pointer to the key matching the key type of the user struct.

Returns: true if the struct containing key is stored, false if not. Error if map or key is NULL.

◆ CCC_tree_map_count()

CCC_Count CCC_tree_map_count ( CCC_Tree_map const * map )

Returns the count of map occupied nodes.

Parameters

[in] map the map.

Returns: the size or an argument is set if map is NULL.

◆ CCC_tree_map_end()

void * CCC_tree_map_end ( CCC_Tree_map const * map )

Return the end of an inorder traversal of the map. O(1).

Parameters

[in] map a pointer to the map.

Returns: the newest maximum element of the map.

◆ CCC_tree_map_entry()

CCC_Tree_map_entry CCC_tree_map_entry	(	CCC_Tree_map const *	map,
		void const *	key
	)

Obtains an entry for the provided key in the map for future use.

Parameters

[in]	map	the map to be searched.
[in]	key	the key used to search the map matching the stored key type.

Returns: a specialized entry for use with other functions in the Entry Interface.

Warning: the contents of an entry should not be examined or modified. Use the provided functions, only.

An entry is a search result that provides either an Occupied or Vacant entry in the map. An occupied entry signifies that the search was successful. A Vacant entry means the search was not successful but a handle is gained to where in the map such an element should be inserted.

An entry is rarely useful on its own. It should be passed in a functional style to subsequent calls in the Entry Interface.

◆ CCC_tree_map_entry_status()

CCC_Entry_status CCC_tree_map_entry_status ( CCC_Tree_map_entry const * entry )

Obtain the entry status from a container entry.

Parameters

[in] entry a pointer to the entry.

Returns: the status stored in the entry after the required action on the container completes. If entry is NULL an entry input error is returned so ensure e is non-NULL to avoid an inaccurate status returned.

Note that this function can be useful for debugging or if more detailed messages are needed for logging purposes. See CCC_entry_status_message() in ccc/types.h for more information on detailed entry statuses.

◆ CCC_tree_map_equal_range()

CCC_Range CCC_tree_map_equal_range	(	CCC_Tree_map const *	map,
		void const *	begin_key,
		void const *	end_key
	)

Return an iterable range of values from [begin_key, end_key). Amortized O(lg N).

Parameters

[in]	map	a pointer to the map.
[in]	begin_key	a pointer to the key intended as the start of the range.
[in]	end_key	a pointer to the key intended as the end of the range.

Returns: a range containing the first element NOT LESS than the begin_key and the first element GREATER than end_key.

Note that due to the variety of values that can be returned in the range, using the provided range iteration functions from types.h is recommended for example:

for (struct Val *i = range_begin(&range); i != range_end(&range); i = next(&omm, &i->elem)) {}

This avoids any possible errors in handling an end range element that is in the map versus the end map sentinel.

◆ CCC_tree_map_equal_range_reverse()

CCC_Range_reverse CCC_tree_map_equal_range_reverse	(	CCC_Tree_map const *	map,
		void const *	reverse_begin_key,
		void const *	reverse_end_key
	)

Return an iterable range_reverse of values from [begin_key, end_key). Amortized O(lg N).

Parameters

[in]	map	a pointer to the map.
[in]	reverse_begin_key	a pointer to the key intended as the start of the range_reverse.
[in]	reverse_end_key	a pointer to the key intended as the end of the range_reverse.

Returns: a range_reverse containing the first element NOT GREATER than the begin_key and the first element LESS than reverse_end_key.

Note that due to the variety of values that can be returned in the range_reverse, using the provided range_reverse iteration functions from types.h is recommended for example:

for (struct Val *i = range_reverse_begin(&range_reverse); i != range_reverse_end(&range_reverse); i = reverse_next(&omm, &i->elem)) {}

This avoids any possible errors in handling an reverse_end range_reverse element that is in the map versus the end map sentinel.

◆ CCC_tree_map_get_key_value()

void * CCC_tree_map_get_key_value	(	CCC_Tree_map const *	map,
		void const *	key
	)

Returns a reference into the map at entry key.

Parameters

[in]	map	the tree map to search.
[in]	key	the key to search matching stored key type.

Returns: a view of the map entry if it is present, else NULL.

◆ CCC_tree_map_insert_entry()

void * CCC_tree_map_insert_entry	(	CCC_Tree_map_entry const *	entry,
		CCC_Tree_map_node *	type_intruder
	)

Inserts the provided entry invariantly.

Parameters

[in]	entry	the entry returned from a call obtaining an entry.
[in]	type_intruder	a handle to the struct the user intends to insert.

Returns: a pointer to the inserted element or NULL upon allocation failure.

This method can be used when the old value in the map does not need to be preserved. See the regular insert method if the old value is of interest.

◆ CCC_tree_map_insert_error()

CCC_Tribool CCC_tree_map_insert_error ( CCC_Tree_map_entry const * entry )

Returns the Vacant or Occupied status of the entry.

Parameters

[in] entry the entry from a query to the map via function or macro.

Returns: true if the entry is occupied, false if not. Error if entry is NULL.

◆ CCC_tree_map_insert_or_assign()

CCC_Entry CCC_tree_map_insert_or_assign	(	CCC_Tree_map *	map,
		CCC_Tree_map_node *	type_intruder
	)

Invariantly inserts or overwrites a user struct into the map.

Parameters

[in]	map	a pointer to the flat hash map.
[in]	type_intruder	the handle to the wrapping user struct key value.

Returns: an entry. If Occupied an entry was overwritten by the new key value. If Vacant no prior map entry existed.

Note that this function can be used when the old user type is not needed but the information regarding its presence is helpful.

◆ CCC_tree_map_is_empty()

CCC_Tribool CCC_tree_map_is_empty ( CCC_Tree_map const * map )

Returns the size status of the map.

Parameters

[in] map the map.

Returns: true if empty else false. Error if map is NULL.

◆ CCC_tree_map_next()

void * CCC_tree_map_next	(	CCC_Tree_map const *	map,
		CCC_Tree_map_node const *	iterator_intruder
	)

Return the next element in an inorder traversal of the map. O(1).

Parameters

[in]	map	a pointer to the map.
[in]	iterator_intruder	a pointer to the intrusive map element of the current iterator.

Returns: the next user type stored in the map in an inorder traversal.

◆ CCC_tree_map_occupied()

CCC_Tribool CCC_tree_map_occupied ( CCC_Tree_map_entry const * entry )

Provides the status of the entry should an insertion follow.

Parameters

[in] entry the entry from a query to the table via function or macro.

Returns: true if an entry obtained from an insertion attempt failed to insert due to an allocation failure when allocation success was expected. Error if entry is NULL.

◆ CCC_tree_map_or_insert()

void * CCC_tree_map_or_insert	(	CCC_Tree_map_entry const *	entry,
		CCC_Tree_map_node *	type_intruder
	)

Inserts the struct with handle type_intruder if the entry is Vacant.

Parameters

[in]	entry	the entry obtained via function or macro call.
[in]	type_intruder	the handle to the struct to be inserted to a Vacant entry.

Returns: a pointer to entry in the map invariantly. NULL on error.

Because this functions takes an entry and inserts if it is Vacant, the only reason NULL shall be returned is when an insertion error occurs, usually due to a user struct allocation failure.

If no allocation is permitted, this function assumes the user struct wrapping elem has been allocated with the appropriate lifetime and scope by the user.

◆ CCC_tree_map_remove_entry()

CCC_Entry CCC_tree_map_remove_entry ( CCC_Tree_map_entry const * entry )

Remove the entry from the map if Occupied.

Parameters

[in] entry a pointer to the map entry.

Returns: an entry containing NULL or a reference to the old entry. If Occupied an entry in the map existed and was removed. If Vacant, no prior entry existed to be removed.

Note that if allocation is permitted the old element is freed and the entry will contain a NULL reference. If allocation is prohibited the entry can be unwrapped to obtain the old user struct stored in the map and the user may free or use as needed.

◆ CCC_tree_map_remove_key_value()

CCC_Entry CCC_tree_map_remove_key_value	(	CCC_Tree_map *	map,
		CCC_Tree_map_node *	output_intruder
	)

Removes the key value in the map storing the old value, if present, in the struct containing output_intruder provided by the user.

Parameters

[in]	map	the pointer to the tree map.
[out]	output_intruder	the handle to the user type wrapping map elem.

Returns: the removed entry. If Occupied it may be unwrapped to obtain the old key value pair. If Vacant the key value pair was not stored in the map. If bad input is provided an input error is set.

Note that this function may write to the struct containing the second parameter and wraps it in an entry to provide information about the old value.

If allocation has been prohibited upon initialization then the entry returned contains the previously stored user type, if any, and nothing is written to the output_intruder. It is then the user's responsibility to manage their previously stored memory as they see fit.

◆ CCC_tree_map_reverse_begin()

void * CCC_tree_map_reverse_begin ( CCC_Tree_map const * map )

Return the start of a reverse inorder traversal of the map. Amortized O(lg N).

Parameters

[in] map a pointer to the map.

Returns: the oldest maximum element of the map.

◆ CCC_tree_map_reverse_end()

void * CCC_tree_map_reverse_end ( CCC_Tree_map const * map )

Return the reverse_end of a reverse inorder traversal of the map. O(1).

Parameters

[in] map a pointer to the map.

Returns: the newest minimum element of the map.

◆ CCC_tree_map_reverse_next()

void * CCC_tree_map_reverse_next	(	CCC_Tree_map const *	map,
		CCC_Tree_map_node const *	iterator_intruder
	)

Return the reverse_next element in a reverse inorder traversal of the map. O(1).

Parameters

[in]	map	a pointer to the map.
[in]	iterator_intruder	a pointer to the intrusive map element of the current iterator.

Returns: the reverse_next user type stored in the map in a reverse inorder traversal.

◆ CCC_tree_map_swap_entry()

CCC_Entry CCC_tree_map_swap_entry	(	CCC_Tree_map *	map,
		CCC_Tree_map_node *	type_intruder,
		CCC_Tree_map_node *	temp_intruder
	)

Invariantly inserts the key value wrapping type_intruder.

Parameters

[in]	map	the pointer to the tree map.
[in]	type_intruder	the handle to the user type wrapping map elem.
[in]	temp_intruder	handle to space for swapping in the old value, if present. The same user type stored in the map should wrap temp_intruder.

Returns: an entry. If Vacant, no prior element with key existed and the type wrapping temp_intruder remains unchanged. If Occupied the old value is written to the type wrapping temp_intruder and may be unwrapped to view. If more space is needed but allocation fails or has been forbidden, an insert error is set.

Note that this function may write to the struct containing temp_intruder and wraps it in an entry to provide information about the old value.

◆ CCC_tree_map_try_insert()

CCC_Entry CCC_tree_map_try_insert	(	CCC_Tree_map *	map,
		CCC_Tree_map_node *	type_intruder
	)

Attempts to insert the key value wrapping type_intruder.

Parameters

[in]	map	the pointer to the map.
[in]	type_intruder	the handle to the user type wrapping map elem.

Returns: an entry. If Occupied, the entry contains a reference to the key value user type in the map and may be unwrapped. If Vacant the entry contains a reference to the newly inserted entry in the map. If more space is needed but allocation fails, an insert error is set.

◆ CCC_tree_map_unwrap()

void * CCC_tree_map_unwrap ( CCC_Tree_map_entry const * entry )

Unwraps the provided entry to obtain a view into the map element.

Parameters

[in] entry the entry from a query to the map via function or macro.

Returns: a view into the table entry if one is present, or NULL.

◆ CCC_tree_map_validate()

CCC_Tribool CCC_tree_map_validate ( CCC_Tree_map const * map )

Validation of invariants for the map.

Parameters

[in] map the map to validate.

Returns: true if all invariants hold, false if corruption occurs. Error if map is NULL.

Detailed Description

Initialization Interface

Entry Interface

Iterator Interface

Container Types

Membership Interface

Deallocation Interface

State Interface

Macro Definition Documentation

◆ CCC_tree_map_and_modify_with

◆ CCC_tree_map_entry_wrap

◆ CCC_tree_map_equal_range_reverse_wrap

◆ CCC_tree_map_equal_range_wrap

◆ CCC_tree_map_from

◆ CCC_tree_map_initialize

◆ CCC_tree_map_insert_entry_with

◆ CCC_tree_map_insert_or_assign_with

◆ CCC_tree_map_insert_or_assign_wrap

◆ CCC_tree_map_or_insert_with

◆ CCC_tree_map_remove_entry_wrap

◆ CCC_tree_map_remove_key_value_wrap

◆ CCC_tree_map_swap_entry_wrap

◆ CCC_tree_map_try_insert_with

◆ CCC_tree_map_try_insert_wrap

Typedef Documentation

◆ CCC_Tree_map

◆ CCC_Tree_map_entry

◆ CCC_Tree_map_node

Function Documentation

◆ CCC_tree_map_and_modify()

◆ CCC_tree_map_and_modify_context()

◆ CCC_tree_map_begin()

◆ CCC_tree_map_clear()

◆ CCC_tree_map_contains()

◆ CCC_tree_map_count()

◆ CCC_tree_map_end()

◆ CCC_tree_map_entry()

◆ CCC_tree_map_entry_status()

◆ CCC_tree_map_equal_range()

◆ CCC_tree_map_equal_range_reverse()

◆ CCC_tree_map_get_key_value()

◆ CCC_tree_map_insert_entry()

◆ CCC_tree_map_insert_error()

◆ CCC_tree_map_insert_or_assign()

◆ CCC_tree_map_is_empty()

◆ CCC_tree_map_next()

◆ CCC_tree_map_occupied()

◆ CCC_tree_map_or_insert()

◆ CCC_tree_map_remove_entry()

◆ CCC_tree_map_remove_key_value()

◆ CCC_tree_map_reverse_begin()

◆ CCC_tree_map_reverse_end()

◆ CCC_tree_map_reverse_next()

◆ CCC_tree_map_swap_entry()

◆ CCC_tree_map_try_insert()

◆ CCC_tree_map_unwrap()

◆ CCC_tree_map_validate()