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 WAVL 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│ └───┴───┴───┴───┴───┴───┴───┴───┘

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	key_offset
CCC_Key_comparator *	order
CCC_Allocator *	allocate
void *	context

Field Documentation

allocate

CCC_Allocator* CCC_Array_adaptive_map::allocate

The provided allocation function, if any.

capacity

size_t CCC_Array_adaptive_map::capacity

The current capacity.

context

void* CCC_Array_adaptive_map::context

The provided context data, if any.

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 WAVL tree meta data.

order

CCC_Key_comparator* CCC_Array_adaptive_map::order

The provided key comparison function.

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/private/private_array_adaptive_map.h