CCC_Array_adaptive_map Struct Reference

#include <private_array_adaptive_map.h>

Collaboration diagram for CCC_Array_adaptive_map:

Detailed Description

A handle ordered map is a modified struct of arrays layout with the modification being that we may have the arrays as pointer offsets in a contiguous allocation if the user desires a dynamic map.

The user data array comes first allowing the user to store any type they wish in the container contiguously with no intrusive element padding, saving space.

The nodes array is next. These nodes track the indices of the child and parent nodes in the tree.

Here is the layout in one contiguous array.

(D = Data Array, N = Nodes Array, _N = Capacity - 1)
 
┌───┬───┬───┬───┬───┬───┬───┬───┐
│D_0│D_1│...│D_N│N_0│N_1│...│N_N│
└───┴───┴───┴───┴───┴───┴───┴───┘

The base allocation, the 0th user data element, is required to satisfy max(alignof(T), alignof(struct CCC_Array_adaptive_map_node)), where T is the user type. This ensures that both the user data array and the node array begin at valid alignment boundaries for their respective element types. Each subsequent region is derived via explicit byte-offset computation using aligned rounding, guaranteeing that the start of each array is aligned to at least its required element alignment.

This layout costs us in consulting both the data and nodes array during the top down splay operation. However, the benefit of space saving and no wasted padding bytes between element fields or multiple elements in an array is the goal of this implementation. Speed is a secondary goal to space for these implementations as the space savings can be significant.

Data Fields
void *	data
struct CCC_Array_adaptive_map_node *	nodes
size_t	capacity
size_t	count
size_t	root
size_t	free_list
size_t	sizeof_type
size_t	alignof_type
size_t	key_offset
CCC_Key_comparator	comparator

Field Documentation

alignof_type

size_t CCC_Array_adaptive_map::alignof_type

The alignment of the type being stored.

capacity

size_t CCC_Array_adaptive_map::capacity

The current capacity.

comparator

CCC_Key_comparator CCC_Array_adaptive_map::comparator

The provided key comparison function and context.

count

size_t CCC_Array_adaptive_map::count

The current size.

data

void* CCC_Array_adaptive_map::data

The contiguous array of user data.

free_list

size_t CCC_Array_adaptive_map::free_list

The start of the free singly linked list.

key_offset

size_t CCC_Array_adaptive_map::key_offset

Where user key can be found in type.

nodes

struct CCC_Array_adaptive_map_node* CCC_Array_adaptive_map::nodes

The contiguous array of tree meta data.

root

size_t CCC_Array_adaptive_map::root

The root node of the Splay Tree.

sizeof_type

size_t CCC_Array_adaptive_map::sizeof_type

The size of the type stored in the map.

---

The documentation for this struct was generated from the following file:

• ccc/specialized/private/private_array_adaptive_map.h