private_array_tree_map.h File Reference

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

#include "../types.h"

Include dependency graph for private_array_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 Array Tree Map Types and Interface.

The private struct-of-array based WAVL tree. The goal of this implementation is to optimize space while providing stable indices for the lifetime of user allocations of elements in the buffer. The intrusive variant offers pointer stability and is significantly less space efficient.

Data Structures
struct	CCC_Array_tree_map_node
struct	CCC_Array_tree_map
struct	CCC_Array_tree_map_handle

Macros
#define	CCC_private_array_tree_map_blocks(private_cap)
#define	CCC_private_array_tree_map_compound_literal_array_capacity( private_type_compound_literal_array)
#define	CCC_private_array_tree_map_storage_for( private_type_compound_literal_array, optional_storage_specifier...)
#define	CCC_private_array_tree_map_default( private_type_name, private_key_field, private_comparator...)
#define	CCC_private_array_tree_map_for( private_type_name, private_key_field, private_comparator, private_capacity, private_memory_pointer)
#define	CCC_private_array_tree_map_from( private_key_field, private_comparator, private_allocator, private_optional_cap, private_array_compound_literal...)
#define	CCC_private_array_tree_map_with_capacity( private_type_name, private_key_field, private_comparator, private_allocator, private_cap)
#define	CCC_private_array_tree_map_with_storage( private_key_node_field, private_comparator, private_compound_literal, private_optional_storage_specifier...)
#define	CCC_private_array_tree_map_as( array_tree_map_pointer, type_name, handle...)
#define	CCC_private_array_tree_map_with_allocator_storage( private_key_field, private_comparator, private_allocator, private_compound_literal)
#define	CCC_private_array_tree_map_and_modify_with( array_tree_map_handle_pointer, closure_parameter, closure_over_closure_parameter...)
#define	CCC_private_array_tree_map_or_insert_with( array_tree_map_handle_pointer, private_allocator_pointer, type_compound_literal...)
#define	CCC_private_array_tree_map_insert_handle_with( array_tree_map_handle_pointer, private_allocator_pointer, type_compound_literal...)
#define	CCC_private_array_tree_map_try_insert_with( array_tree_map_pointer, key, private_allocator_pointer, type_compound_literal...)
#define	CCC_private_array_tree_map_insert_or_assign_with( array_tree_map_pointer, key, private_allocator_pointer, type_compound_literal...)

Functions
void *	CCC_private_array_tree_map_data_at (struct CCC_Array_tree_map const *, size_t)
void *	CCC_private_array_tree_map_key_at (struct CCC_Array_tree_map const *, size_t)
struct CCC_Array_tree_map_handle	CCC_private_array_tree_map_handle (struct CCC_Array_tree_map const *, void const *)
void	CCC_private_array_tree_map_insert (struct CCC_Array_tree_map *, size_t, CCC_Order, size_t)
size_t	CCC_private_array_tree_map_allocate_slot (struct CCC_Array_tree_map *, CCC_Allocator const *)

Macro Definition Documentation

CCC_private_array_tree_map_and_modify_with

#define CCC_private_array_tree_map_and_modify_with	(		array_tree_map_handle_pointer,
			closure_parameter,
			closure_over_closure_parameter...
	)

Value:

    (__extension__({                                                           \
        struct CCC_Array_tree_map_handle const *const                          \
            private_array_tree_map_hndl_pointer                                \
            = (array_tree_map_handle_pointer);                                 \
        struct CCC_Array_tree_map_handle private_array_tree_map_mod_hndl       \
            = {.status = CCC_ENTRY_ARGUMENT_ERROR};                            \
        if (private_array_tree_map_hndl_pointer) {                             \
            private_array_tree_map_mod_hndl                                    \
                = *private_array_tree_map_hndl_pointer;                        \
            if (private_array_tree_map_mod_hndl.status & CCC_ENTRY_OCCUPIED) { \
                closure_parameter = CCC_private_array_tree_map_data_at(        \
                    private_array_tree_map_mod_hndl.map,                       \
                    private_array_tree_map_mod_hndl.index                      \
                );                                                             \
                closure_over_closure_parameter                                 \
            }                                                                  \
        }                                                                      \
        private_array_tree_map_mod_hndl;                                       \
    }))

CCC_private_array_tree_map_as

#define CCC_private_array_tree_map_as	(		array_tree_map_pointer,
			type_name,
			handle...
	)

Value:

    ((type_name *)CCC_private_array_tree_map_data_at(                          \
        (array_tree_map_pointer), (handle)                                     \
    ))

CCC_private_array_tree_map_blocks

#define CCC_private_array_tree_map_blocks

(

private_cap

)

Value:

    (((private_cap)                                                            \
      + ((sizeof(*(struct CCC_Array_tree_map){}.parity) * CHAR_BIT) - 1))      \
     / (sizeof(*(struct CCC_Array_tree_map){}.parity) * CHAR_BIT))

Calculates the number of parity blocks needed to support the given capacity. Provide the type used for the parity block array and the number of blocks needed to round up to will be returned.

CCC_private_array_tree_map_compound_literal_array_capacity

#define CCC_private_array_tree_map_compound_literal_array_capacity

(

private_type_compound_literal_array

)

Value:

    (sizeof(private_type_compound_literal_array)                               \
     / sizeof(*(private_type_compound_literal_array)))

CCC_private_array_tree_map_default

#define CCC_private_array_tree_map_default	(		private_type_name,
			private_key_field,
			private_comparator...
	)

Value:

    (struct CCC_Array_tree_map) {                                              \
        .sizeof_type = sizeof(private_type_name),                              \
        .alignof_type = alignof(private_type_name),                            \
        .key_offset = offsetof(private_type_name, private_key_field),          \
        .comparator = (private_comparator),                                    \
    }

All other fields default to NULL or 0.

CCC_private_array_tree_map_for

#define CCC_private_array_tree_map_for	(		private_type_name,
			private_key_field,
			private_comparator,
			private_capacity,
			private_memory_pointer
	)

Value:

    (struct CCC_Array_tree_map) {                                              \
        .data = (private_memory_pointer), .nodes = NULL, .parity = NULL,       \
        .capacity = (private_capacity), .count = 0, .root = 0, .free_list = 0, \
        .sizeof_type = sizeof(private_type_name),                              \
        .alignof_type = alignof(private_type_name),                            \
        .key_offset = offsetof(private_type_name, private_key_field),          \
        .comparator = (private_comparator),                                    \
    }

Initialization only tracks pointers to support a variety of memory sources for both fixed and dynamic maps. The nodes and parity pointers will be lazily initialized upon the first runtime opportunity. This allows the initial memory provided to the data pointer to come from any source at compile or runtime.

CCC_private_array_tree_map_from

#define CCC_private_array_tree_map_from	(		private_key_field,
			private_comparator,
			private_allocator,
			private_optional_cap,
			private_array_compound_literal...
	)

Initialize an array tree map from user input list.

CCC_private_array_tree_map_insert_handle_with

#define CCC_private_array_tree_map_insert_handle_with	(		array_tree_map_handle_pointer,
			private_allocator_pointer,
			type_compound_literal...
	)

CCC_private_array_tree_map_insert_or_assign_with

#define CCC_private_array_tree_map_insert_or_assign_with	(		array_tree_map_pointer,
			key,
			private_allocator_pointer,
			type_compound_literal...
	)

CCC_private_array_tree_map_or_insert_with

#define CCC_private_array_tree_map_or_insert_with	(		array_tree_map_handle_pointer,
			private_allocator_pointer,
			type_compound_literal...
	)

CCC_private_array_tree_map_storage_for

#define CCC_private_array_tree_map_storage_for	(		private_type_compound_literal_array,
			optional_storage_specifier...
	)

Value:

    (optional_storage_specifier struct {                                       \
        static_assert(                                                         \
            CCC_private_array_tree_map_compound_literal_array_capacity(        \
                private_type_compound_literal_array                            \
            ) > 1,                                                             \
            "fixed size map must have capacity greater than 1"                 \
        );                                                                     \
        alignas(                                                               \
            alignof(*(private_type_compound_literal_array))                    \
                    > alignof(struct CCC_Array_tree_map_node)                  \
                ? alignof(*(private_type_compound_literal_array))              \
                : alignof(struct CCC_Array_tree_map_node)                      \
        ) typeof(*(private_type_compound_literal_array))                       \
            data[CCC_private_array_tree_map_compound_literal_array_capacity(   \
                private_type_compound_literal_array                            \
            )];                                                                \
        struct CCC_Array_tree_map_node                                         \
            nodes[CCC_private_array_tree_map_compound_literal_array_capacity(  \
                private_type_compound_literal_array                            \
            )];                                                                \
        typeof(*(struct CCC_Array_tree_map){}.parity)                          \
            parity[CCC_private_array_tree_map_blocks(                          \
                CCC_private_array_tree_map_compound_literal_array_capacity(    \
                    private_type_compound_literal_array                        \
                )                                                              \
            )];                                                                \
    }) {                                                                       \
    }

The user can declare a fixed size realtime ordered map with the help of static asserts to ensure the layout is compatible with our internal metadata.

CCC_private_array_tree_map_try_insert_with

#define CCC_private_array_tree_map_try_insert_with	(		array_tree_map_pointer,
			key,
			private_allocator_pointer,
			type_compound_literal...
	)

CCC_private_array_tree_map_with_allocator_storage

#define CCC_private_array_tree_map_with_allocator_storage	(		private_key_field,
			private_comparator,
			private_allocator,
			private_compound_literal
	)

Helper for allocating a fixed size map dynamically.

CCC_private_array_tree_map_with_capacity

#define CCC_private_array_tree_map_with_capacity	(		private_type_name,
			private_key_field,
			private_comparator,
			private_allocator,
			private_cap
	)

Value:

    (struct { struct CCC_Array_tree_map private; }){(__extension__({           \
        struct CCC_Array_tree_map private_array_tree_map                       \
            = CCC_private_array_tree_map_default(                              \
                private_type_name, private_key_field, private_comparator       \
            );                                                                 \
        (void)CCC_array_tree_map_reserve(                                      \
            &private_array_tree_map, private_cap, &(private_allocator)         \
        );                                                                     \
        private_array_tree_map;                                                \
    }))}.private

CCC_private_array_tree_map_with_storage

#define CCC_private_array_tree_map_with_storage	(		private_key_node_field,
			private_comparator,
			private_compound_literal,
			private_optional_storage_specifier...
	)

Value:

    (struct CCC_Array_tree_map) {                                              \
        .data = &CCC_private_array_tree_map_storage_for(                       \
            private_compound_literal, private_optional_storage_specifier       \
        ),                                                                     \
        .nodes = NULL, .parity = NULL,                                         \
        .capacity                                                              \
            = CCC_private_array_tree_map_compound_literal_array_capacity(      \
                private_compound_literal                                       \
            ),                                                                 \
        .count = 0, .root = 0, .free_list = 0,                                 \
        .sizeof_type = sizeof(*(private_compound_literal)),                    \
        .alignof_type = alignof(*(private_compound_literal)),                  \
        .key_offset = offsetof(                                                \
            typeof(*(private_compound_literal)), private_key_node_field        \
        ),                                                                     \
        .comparator = (private_comparator),                                    \
    }

Function Documentation

CCC_private_array_tree_map_allocate_slot()

size_t CCC_private_array_tree_map_allocate_slot	(	struct CCC_Array_tree_map *	,
		CCC_Allocator const *
	)

CCC_private_array_tree_map_data_at()

void * CCC_private_array_tree_map_data_at	(	struct CCC_Array_tree_map const *	,
		size_t
	)

CCC_private_array_tree_map_handle()

struct CCC_Array_tree_map_handle CCC_private_array_tree_map_handle	(	struct CCC_Array_tree_map const *	,
		void const *
	)

CCC_private_array_tree_map_insert()

void CCC_private_array_tree_map_insert	(	struct CCC_Array_tree_map *	,
		size_t	,
		CCC_Order	,
		size_t
	)

CCC_private_array_tree_map_key_at()

void * CCC_private_array_tree_map_key_at	(	struct CCC_Array_tree_map const *	,
		size_t
	)