private_tree_map.h File Reference

The Private Tree Map Types and Interface. More...

#include "../types.h"

Include dependency graph for private_tree_map.h:

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

Go to the source code of this file.

Detailed Description

The Private Tree Map Types and Interface.

The private intrusive WAVL tree map interface and type header. This intrusive map is still a fast viable option for users. However, one should seriously consider if the Array_tree_map as well. Due to the struct of array layout, the Array_tree_map variant can use significantly less space than this intrusive variant with almost identical runtime guarantees. However, it relies on indexes in a buffer remaining stable rather than pointers provided by an allocator interface function. These concepts are similar but not identical, so a user may require this intrusive implementation.

Data Structures
struct	CCC_Tree_map_node
struct	CCC_Tree_map
struct	CCC_Tree_map_entry

Macros
#define	CCC_private_tree_map_for( private_struct_name, private_node_field, private_key_node_field, private_comparator...)
#define	CCC_private_tree_map_default( private_struct_name, private_node_field, private_key_node_field, private_comparator...)
#define	CCC_private_tree_map_from( private_type_intruder_field_name, private_key_field_name, private_comparator, private_allocator, private_destructor, private_compound_literal_array...)
#define	CCC_private_tree_map_new( private_tree_map_entry, private_allocator_pointer)
#define	CCC_private_tree_map_insert_key_val( private_tree_map_entry, new_data, type_compound_literal...)
#define	CCC_private_tree_map_insert_and_copy_key( tree_map_insert_entry, tree_map_insert_entry_ret, key, private_allocator_pointer, type_compound_literal...)
#define	CCC_private_tree_map_and_modify_with( private_tree_map_entry_pointer, closure_parameter, closure_over_closure_parameter...)
#define	CCC_private_tree_map_or_insert_with( private_tree_map_entry_pointer, private_allocator_pointer, type_compound_literal...)
#define	CCC_private_tree_map_insert_entry_with( private_tree_map_entry_pointer, private_allocator_pointer, type_compound_literal...)
#define	CCC_private_tree_map_try_insert_with( Tree_map_pointer, key, private_allocator_pointer, type_compound_literal...)
#define	CCC_private_tree_map_insert_or_assign_with( Tree_map_pointer, key, private_allocator_pointer, type_compound_literal...)

Functions
void *	CCC_private_tree_map_key_in_slot (struct CCC_Tree_map const *, void const *slot)
struct CCC_Tree_map_node *	CCC_private_tree_map_node_in_slot (struct CCC_Tree_map const *, void const *slot)
struct CCC_Tree_map_entry	CCC_private_tree_map_entry (struct CCC_Tree_map const *, void const *key)
void *	CCC_private_tree_map_insert (struct CCC_Tree_map *, struct CCC_Tree_map_node *parent, CCC_Order last_order, struct CCC_Tree_map_node *type_output_intruder)

Macro Definition Documentation

CCC_private_tree_map_and_modify_with

#define CCC_private_tree_map_and_modify_with	(		private_tree_map_entry_pointer,
			closure_parameter,
			closure_over_closure_parameter...
	)

Value:

    (__extension__({                                                           \
        struct CCC_Tree_map_entry const *const private_tree_map_ent_pointer    \
            = (private_tree_map_entry_pointer);                                \
        struct CCC_Tree_map_entry private_tree_map_mod_ent                     \
            = {.entry = {.status = CCC_ENTRY_ARGUMENT_ERROR}};                 \
        if (private_tree_map_ent_pointer) {                                    \
            private_tree_map_mod_ent = *private_tree_map_ent_pointer;          \
            if (private_tree_map_mod_ent.entry.status & CCC_ENTRY_OCCUPIED) {  \
                closure_parameter = private_tree_map_mod_ent.entry.type;       \
                closure_over_closure_parameter                                 \
            }                                                                  \
        }                                                                      \
        private_tree_map_mod_ent;                                              \
    }))

CCC_private_tree_map_default

#define CCC_private_tree_map_default	(		private_struct_name,
			private_node_field,
			private_key_node_field,
			private_comparator...
	)

Value:

    CCC_private_tree_map_for(                                                  \
        private_struct_name,                                                   \
        private_node_field,                                                    \
        private_key_node_field,                                                \
        private_comparator                                                     \
    )

CCC_private_tree_map_for

#define CCC_private_tree_map_for	(		private_struct_name,
			private_node_field,
			private_key_node_field,
			private_comparator...
	)

Value:

    (struct CCC_Tree_map) {                                                    \
        .root = NULL, .count = 0,                                              \
        .key_offset = offsetof(private_struct_name, private_key_node_field),   \
        .type_intruder_offset                                                  \
            = offsetof(private_struct_name, private_node_field),               \
        .sizeof_type = sizeof(private_struct_name),                            \
        .alignof_type = alignof(private_struct_name),                          \
        .comparator = (private_comparator),                                    \
    }

CCC_private_tree_map_from

#define CCC_private_tree_map_from	(		private_type_intruder_field_name,
			private_key_field_name,
			private_comparator,
			private_allocator,
			private_destructor,
			private_compound_literal_array...
	)

CCC_private_tree_map_insert_and_copy_key

#define CCC_private_tree_map_insert_and_copy_key	(		tree_map_insert_entry,
			tree_map_insert_entry_ret,
			key,
			private_allocator_pointer,
			type_compound_literal...
	)

Value:

    (__extension__({                                                           \
        typeof(type_compound_literal) *private_tree_map_new_ins_base           \
            = CCC_private_tree_map_new(                                        \
                (&tree_map_insert_entry), private_allocator_pointer            \
            );                                                                 \
        tree_map_insert_entry_ret = (CCC_Entry){                               \
            .type = private_tree_map_new_ins_base,                             \
            .status = CCC_ENTRY_INSERT_ERROR,                                  \
        };                                                                     \
        if (private_tree_map_new_ins_base) {                                   \
            tree_map_insert_entry_ret.status = CCC_ENTRY_VACANT;               \
            *private_tree_map_new_ins_base = type_compound_literal;            \
            *((typeof(key) *)CCC_private_tree_map_key_in_slot(                 \
                tree_map_insert_entry.map, private_tree_map_new_ins_base       \
            )) = key;                                                          \
            (void)CCC_private_tree_map_insert(                                 \
                tree_map_insert_entry.map,                                     \
                CCC_private_tree_map_node_in_slot(                             \
                    tree_map_insert_entry.map,                                 \
                    tree_map_insert_entry.entry.type                           \
                ),                                                             \
                tree_map_insert_entry.last_order,                              \
                CCC_private_tree_map_node_in_slot(                             \
                    tree_map_insert_entry.map, private_tree_map_new_ins_base   \
                )                                                              \
            );                                                                 \
        }                                                                      \
    }))

CCC_private_tree_map_insert_entry_with

#define CCC_private_tree_map_insert_entry_with	(		private_tree_map_entry_pointer,
			private_allocator_pointer,
			type_compound_literal...
	)

CCC_private_tree_map_insert_key_val

#define CCC_private_tree_map_insert_key_val	(		private_tree_map_entry,
			new_data,
			type_compound_literal...
	)

Value:

    (__extension__({                                                           \
        if (new_data) {                                                        \
            *new_data = type_compound_literal;                                 \
            new_data = CCC_private_tree_map_insert(                            \
                (private_tree_map_entry)->map,                                 \
                CCC_private_tree_map_node_in_slot(                             \
                    (private_tree_map_entry)->map,                             \
                    (private_tree_map_entry)->entry.type                       \
                ),                                                             \
                (private_tree_map_entry)->last_order,                          \
                CCC_private_tree_map_node_in_slot(                             \
                    (private_tree_map_entry)->map, new_data                    \
                )                                                              \
            );                                                                 \
        }                                                                      \
    }))

CCC_private_tree_map_insert_or_assign_with

#define CCC_private_tree_map_insert_or_assign_with	(		Tree_map_pointer,
			key,
			private_allocator_pointer,
			type_compound_literal...
	)

CCC_private_tree_map_new

#define CCC_private_tree_map_new	(		private_tree_map_entry,
			private_allocator_pointer
	)

Value:

    (__extension__({                                                           \
        void *private_tree_map_ins_allocate_ret = NULL;                        \
        if ((private_allocator_pointer)->allocate) {                           \
            private_tree_map_ins_allocate_ret                                  \
                = (private_allocator_pointer)                                  \
                      ->allocate((CCC_Allocator_arguments){                    \
                          .input = NULL,                                       \
                          .bytes = (private_tree_map_entry)->map->sizeof_type, \
                          .alignment                                           \
                          = (private_tree_map_entry)->map->alignof_type,       \
                          .context = (private_allocator_pointer)->context,     \
                      });                                                      \
        }                                                                      \
        private_tree_map_ins_allocate_ret;                                     \
    }))

CCC_private_tree_map_or_insert_with

#define CCC_private_tree_map_or_insert_with	(		private_tree_map_entry_pointer,
			private_allocator_pointer,
			type_compound_literal...
	)

Value:

    (__extension__({                                                           \
        struct CCC_Tree_map_entry const *const private_or_ins_entry_pointer    \
            = (private_tree_map_entry_pointer);                                \
        typeof(type_compound_literal) *private_tree_map_or_ins_ret = NULL;     \
        CCC_Allocator const *const private_tree_map_allocator                  \
            = (private_allocator_pointer);                                     \
        if (private_tree_map_allocator && private_or_ins_entry_pointer) {      \
            if (private_or_ins_entry_pointer->entry.status                     \
                == CCC_ENTRY_OCCUPIED) {                                       \
                private_tree_map_or_ins_ret                                    \
                    = private_or_ins_entry_pointer->entry.type;                \
            } else {                                                           \
                private_tree_map_or_ins_ret = CCC_private_tree_map_new(        \
                    private_or_ins_entry_pointer, private_tree_map_allocator   \
                );                                                             \
                CCC_private_tree_map_insert_key_val(                           \
                    private_or_ins_entry_pointer,                              \
                    private_tree_map_or_ins_ret,                               \
                    type_compound_literal                                      \
                );                                                             \
            }                                                                  \
        }                                                                      \
        private_tree_map_or_ins_ret;                                           \
    }))

CCC_private_tree_map_try_insert_with

#define CCC_private_tree_map_try_insert_with	(		Tree_map_pointer,
			key,
			private_allocator_pointer,
			type_compound_literal...
	)

Value:

    (__extension__({                                                           \
        struct CCC_Tree_map *const private_try_ins_map_pointer                 \
            = (Tree_map_pointer);                                              \
        CCC_Entry private_tree_map_try_ins_ent_ret                             \
            = {.status = CCC_ENTRY_ARGUMENT_ERROR};                            \
        CCC_Allocator const *const private_tree_map_allocator                  \
            = (private_allocator_pointer);                                     \
        if (private_tree_map_allocator && private_try_ins_map_pointer) {       \
            __auto_type private_tree_map_key = (key);                          \
            struct CCC_Tree_map_entry private_tree_map_try_ins_ent             \
                = CCC_private_tree_map_entry(                                  \
                    private_try_ins_map_pointer, (void *)&private_tree_map_key \
                );                                                             \
            if (!(private_tree_map_try_ins_ent.entry.status                    \
                  & CCC_ENTRY_OCCUPIED)) {                                     \
                CCC_private_tree_map_insert_and_copy_key(                      \
                    private_tree_map_try_ins_ent,                              \
                    private_tree_map_try_ins_ent_ret,                          \
                    private_tree_map_key,                                      \
                    private_tree_map_allocator,                                \
                    type_compound_literal                                      \
                );                                                             \
            } else if (private_tree_map_try_ins_ent.entry.status               \
                       == CCC_ENTRY_OCCUPIED) {                                \
                private_tree_map_try_ins_ent_ret                               \
                    = private_tree_map_try_ins_ent.entry;                      \
            }                                                                  \
        }                                                                      \
        private_tree_map_try_ins_ent_ret;                                      \
    }))

Function Documentation

CCC_private_tree_map_entry()

struct CCC_Tree_map_entry CCC_private_tree_map_entry	(	struct CCC_Tree_map const *	,
		void const *	key
	)

CCC_private_tree_map_insert()

void * CCC_private_tree_map_insert	(	struct CCC_Tree_map *	,
		struct CCC_Tree_map_node *	parent,
		CCC_Order	last_order,
		struct CCC_Tree_map_node *	type_output_intruder
	)

CCC_private_tree_map_key_in_slot()

void * CCC_private_tree_map_key_in_slot	(	struct CCC_Tree_map const *	,
		void const *	slot
	)

CCC_private_tree_map_node_in_slot()

struct CCC_Tree_map_node * CCC_private_tree_map_node_in_slot	(	struct CCC_Tree_map const *	,
		void const *	slot
	)