The C Container Collection offers a variety of containers for C programmers who want fine-grained control of memory in their programs. All containers offer both allocating and non-allocating interfaces. For the motivations of why such a library is helpful in C read on.
The following are required for install:
- GCC or Clang supporting
C23.- The oldest compilers I am aware of that build a release package are Clang 19.1.1 and GCC 14.2. Older compilers may work as well.
- To build the samples, tests, and utilities that are not included in the release package newer compilers are needed. At the time of writing Clang 22.1.0 and GCC 15.2 cover the newer C features used such as
defer. These newer compilers are only needed for developers looking to contribute to the collection.
- CMake >= 3.23.
- Read INSTALL.md for easy installation. Freestanding environments are also supported!
Currently, this library supports a FetchContent or manual installation via CMake. The INSTALL.md file is included in all Releases.
- Read the DOCS.
- Read types.h to understand the
CCC_Allocator_interfaceinterface. - Read the header for the desired container to understand its functionality.
- Read about generic traits.h shared across containers to make code more succinct.
- Read CONTRIBUTING.md and the coverage report if interested in the project structure, tools, and todos.
adaptive_map.h (dropdown)
A pointer stable ordered map that stores unique keys, implemented with a self-optimizing tree structure.#include <assert.h>
#include <string.h>
#define ADAPTIVE_MAP_USING_NAMESPACE_CCC
#define TRAITS_USING_NAMESPACE_CCC
#include "ccc/adaptive_map.h"
#include "ccc/traits.h"
struct Name {
Adaptive_map_node e;
char const *name;
};
CCC_Order
key_val_cmp(CCC_Key_comparator_arguments cmp) {
char const *const key = *(char **)cmp.key_left;
struct Name const *const right = cmp.type_right;
int const res = strcmp(key, right->name);
if (res == 0) {
return CCC_ORDER_EQUAL;
}
if (res < 0) {
return CCC_ORDER_LESSER;
}
return CCC_ORDER_GREATER;
}
int
main(void) {
struct Name nodes[5];
Adaptive_map om = adaptive_map_default(
struct Name,
e,
name,
(CCC_Key_comparator){.compare = key_val_cmp}
);
char const *const sorted_names[5]
= {"Ferris", "Glenda", "Rocky", "Tux", "Ziggy"};
size_t const size = sizeof(sorted_names) / sizeof(sorted_names[0]);
size_t j = 7 % size;
for (size_t i = 0; i < size; ++i, j = (j + 7) % size) {
nodes[count(&om).count].name = sorted_names[j];
CCC_Entry e = insert_or_assign(
&om,
&nodes[count(&om).count].e
&(CCC_Allocator){}
);
assert(!insert_error(&e) && !occupied(&e));
}
j = 0;
for (struct Name const *n = begin(&om); n != end(&om);
n = next(&om, &n->e)) {
assert(n->name == sorted_names[j]);
assert(strcmp(n->name, sorted_names[j]) == 0);
++j;
}
assert(count(&om).count == size);
CCC_Entry e = try_insert(
&om,
&(struct Name){.name = "Ferris"}.e,
&(CCC_Allocator){}
);
assert(count(&om).count == size);
assert(occupied(&e));
return 0;
}array_adaptive_map.h (dropdown)
An ordered map implemented in array with an index based self-optimizing tree. Offers handle stability. Handles remain valid until an element is removed from a table regardless of other insertions, other deletions, or resizing of the array.#include <assert.h>
#include <stdbool.h>
#define ARRAY_ADAPTIVE_MAP_USING_NAMESPACE_CCC
#define TRAITS_USING_NAMESPACE_CCC
#define TYPES_USING_NAMESPACE_CCC
#include "ccc/array_adaptive_map.h"
#include "ccc/traits.h"
struct Key_val {
int key;
int val;
};
static CCC_Order
key_val_cmp(CCC_Key_comparator_arguments const cmp) {
struct Key_val const *const right = cmp.type_right;
int const key_left = *((int *)cmp.key_left);
return (key_left > right->key) - (key_left < right->key);
}
int
main(void) {
/* stack array of 25 elements with one slot for sentinel, intrusive field
named elem, key field named key, no allocation permission, key comparison
function, no context data. */
Array_adaptive_map s = array_adaptive_map_with_storage(
key,
(CCC_Key_comparator){.compare = key_val_cmp},
(struct Key_val[26]){}
);
int const num_nodes = 25;
/* 0, 5, 10, 15, 20, 25, 30, 35,... 120 */
for (int i = 0, id = 0; i < num_nodes; ++i, id += 5) {
(void)insert_or_assign(
&s, &(struct Key_val){.key = id, .val = i}.elem, &(CCC_Allocator){}
);
}
/* This should be the following Range [6,44). 6 should raise to
next value not less than 6, 10 and 44 should be the first
value greater than 44, 45. */
int range_keys[8] = {10, 15, 20, 25, 30, 35, 40, 45};
Handle_range r = equal_range(&s, &(int){6}, &(int){44});
int index = 0;
for (Handle_index i = range_begin(&r); i != range_end(&r);
i = next(&s, i)) {
struct Key_val const *const kv = array_adaptive_map_at(&s, i);
assert(kv->key == range_keys[index]);
++index;
}
/* This should be the following Range [119,84). 119 should be
dropped to first value not greater than 119 and last should
be dropped to first value less than 84. */
int range_reverse_keys[8] = {115, 110, 105, 100, 95, 90, 85, 80};
Handle_range_reverse rr = equal_range_reverse(&s, &(int){119}, &(int){84});
index = 0;
for (Handle_index i = range_reverse_begin(&rr); i != range_reverse_end(&rr);
i = reverse_next(&s, i)) {
struct Key_val const *const kv = array_adaptive_map_at(&s, i);
assert(kv->key == range_reverse_keys[index]);
++index;
}
return 0;
}array_tree_map.h (dropdown)
An ordered map with strict runtime bounds implemented in an array with indices tracking the tree structure. Offers handle stability. Handles remain valid until an element is removed from a table regardless of other insertions, other deletions, or resizing of the array.#include <assert.h>
#include <stdbool.h>
#define ARRAY_TREE_MAP_USING_NAMESPACE_CCC
#define TRAITS_USING_NAMESPACE_CCC
#define TYPES_USING_NAMESPACE_CCC
#include "ccc/array_tree_map.h"
#include "ccc/traits.h"
struct Key_val {
int key;
int val;
};
static CCC_Order
key_val_cmp(CCC_Key_comparator_arguments const cmp) {
struct Key_val const *const right = cmp.type_right;
int const key_left = *((int *)cmp.key_left);
return (key_left > right->key) - (key_left < right->key);
}
int
main(void) {
/* stack array, user defined type, key field named key, no allocation
permission, key comparison function, no context data. */
Array_tree_map s = array_tree_map_with_storage(
key,
(CCC_Key_comparator){.compare = key_val_cmp},
(struct Kay_val[64]){}
);
int const num_nodes = 25;
/* 0, 5, 10, 15, 20, 25, 30, 35,... 120 */
for (int i = 0, id = 0; i < num_nodes; ++i, id += 5) {
(void)insert_or_assign(
&s,
&(struct Key_val){.key = id, .val = i}.elem,
&(CCC_Allocator){}
);
}
/* This should be the following Range [6,44). 6 should raise to
next value not less than 6, 10 and 44 should be the first
value greater than 44, 45. */
int range_keys[8] = {10, 15, 20, 25, 30, 35, 40, 45};
Handle_range r = equal_range(&s, &(int){6}, &(int){44});
int index = 0;
for (Handle_index i = range_begin(&r); i != range_end(&r);
i = next(&s, &i->elem)) {
struct Key_val const *const kv = array_tree_map_at(&s, i);
assert(kv->key == range_keys[index]);
++index;
}
/* This should be the following Range [119,84). 119 should be
dropped to first value not greater than 119 and last should
be dropped to first value less than 84. */
int range_reverse_keys[8] = {115, 110, 105, 100, 95, 90, 85, 80};
Handle_range_reverse rr = equal_range_reverse(&s, &(int){119}, &(int){84});
index = 0;
for (Handle_index i = range_reverse_begin(&rr); i != range_reverse_end(&rr);
i = reverse_next(&s, &i->elem)) {
struct Key_val const *const kv = array_tree_map_at(&s, i);
assert(kv->key == range_reverse_keys[index]);
++index;
}
return 0;
}doubly_linked_list.h (dropdown)
A dynamic container for efficient insertion and removal at any position.#include <assert.h>
#define DOUBLY_LINKED_LIST_USING_NAMESPACE_CCC
#define TRAITS_USING_NAMESPACE_CCC
#include "ccc/doubly_linked_list.h"
#include "ccc/traits.h"
struct Int_node {
int i;
Doubly_linked_list_node e;
};
static CCC_Order
int_cmp(CCC_Comparator_arguments const cmp) {
struct Int_node const *const left = cmp.type_left;
struct Int_node const *const right = cmp.type_right;
return (left->i > right->i) - (left->i < right->i);
}
int
main(void) {
Doubly_linked_list l = doubly_linked_list_default(l, struct Int_node, e);
struct Int_node elems[3] = {{.i = 3}, {.i = 2}, {.i = 1}};
(void)push_back(&l, &elems[0].e, &(CCC_Allocator){});
(void)push_front(&l, &elems[1].e, &(CCC_Allocator){});
(void)push_back(&l, &elems[2].e, &(CCC_Allocator){});
(void)pop_back(&l, &(CCC_Allocator){});
struct Int_node *e = back(&l);
assert(e->i == 3);
return 0;
}flat_bitset.h (dropdown)
A fixed or dynamic contiguous array of bits for set operations.#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#define FLAT_BITSET_USING_NAMESPACE_CCC
#include "ccc/flat_bitset.h"
#include "ccc/types.h"
#define DIGITS 9L
#define ROWS DIGITS
#define COLS DIGITS
#define BOX_SIZE 3L
/* clang-format off */
static int const valid_board[9][9] =
{{5,3,0, 0,7,0, 0,0,0}
,{6,0,0, 1,9,5, 0,0,0}
,{0,9,8, 0,0,0, 0,6,0}
,{8,0,0, 0,6,0, 0,0,3}
,{4,0,0, 8,0,3, 0,0,1}
,{7,0,0, 0,2,0, 0,0,6}
,{0,6,0, 0,0,0, 2,8,0}
,{0,0,0, 4,1,9, 0,0,5}
,{0,0,0, 0,8,0, 0,7,9}};
static int const invalid_board[9][9] =
{{8,3,0, 0,7,0, 0,0,0} /* 8 in first box top left. */
,{6,0,0, 1,9,5, 0,0,0}
,{0,9,8, 0,0,0, 0,6,0} /* 8 in first box bottom right. */
,{8,0,0, 0,6,0, 0,0,3} /* 8 also overlaps with 8 in top left by row. */
,{4,0,0, 8,0,3, 0,0,1}
,{7,0,0, 0,2,0, 0,0,6}
,{0,6,0, 0,0,0, 2,8,0}
,{0,0,0, 4,1,9, 0,0,5}
,{0,0,0, 0,8,0, 0,7,9}};
/* clang-format on */
/* Returns if the box is valid (CCC_TRUE if valid CCC_FALSE if not). */
static CCC_Tribool
validate_sudoku_box(int const board[9][9], Flat_bitset *const row_check,
Flat_bitset *const col_check, size_t const row_start,
size_t const col_start) {
Flat_bitset box_check
= flat_bitset_with_storage(DIGITS, flat_bitset_storage_for(DIGITS));
CCC_Tribool was_on = CCC_FALSE;
for (size_t r = row_start; r < row_start + BOX_SIZE; ++r) {
for (size_t c = col_start; c < col_start + BOX_SIZE; ++c) {
if (!board[r][c]) {
continue;
}
/* Need the zero based digit. */
size_t const digit = board[r][c] - 1;
was_on = flat_bitset_set(&box_check, digit, CCC_TRUE);
if (was_on) {
return CCC_FALSE;
}
was_on = flat_bitset_set(row_check, (r * DIGITS) + digit, CCC_TRUE);
if (was_on) {
return CCC_FALSE;
}
was_on = flat_bitset_set(col_check, (c * DIGITS) + digit, CCC_TRUE);
if (was_on) {
return CCC_FALSE;
}
}
}
return CCC_TRUE;
}
/* A small problem like this is a perfect use case for a stack based bit set.
All sizes are known at compile time meaning we get memory management for
free and the optimal space and time complexity for this problem. */
static CCC_Tribool
is_valid_sudoku(int const board[9][9]) {
Flat_bitset row_check = flat_bitset_with_storage(
ROWS * DIGITS, flat_bitset_storage_for(ROWS * DIGITS));
Flat_bitset col_check = flat_bitset_with_storage(
COLS * DIGITS, flat_bitset_storage_for(COLS * DIGITS));
for (size_t row = 0; row < ROWS; row += BOX_SIZE) {
for (size_t col = 0; col < COLS; col += BOX_SIZE) {
if (!validate_sudoku_box(board, &row_check, &col_check, row, col)) {
return CCC_FALSE;
}
}
}
return CCC_TRUE;
}
int
main(void) {
CCC_Tribool result = is_valid_sudoku(valid_board);
assert(result == CCC_TRUE);
result = is_valid_sudoku(invalid_board);
assert(result == CCC_FALSE);
return 0;
}flat_buffer.h (dropdown)
A fixed or dynamic contiguous array of a single user defined type.#include <assert.h>
#define FLAT_BUFFER_USING_NAMESPACE_CCC
#define TRAITS_USING_NAMESPACE_CCC
#include "ccc/flat_buffer.h"
#include "ccc/traits.h"
enum : size_t {
HCAP = 12,
};
static inline int
maxint(int const a, int const b) {
return a > b ? a : b;
}
/* Trapping rainwater Leetcode problem with iterators */
int
main(void) {
Flat_buffer const heights = flat_buffer_with_storage(
HCAP, (int[HCAP]){0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1});
int const correct_trapped = 6;
int trapped = 0;
int lpeak = *flat_buffer_front_as(&heights, int);
int rpeak = *flat_buffer_back_as(&heights, int);
/* Easy way to have a "skip first" iterator because the iterator is
returned from each iterator function. */
int const *l = next(&heights, begin(&heights));
int const *r = reverse_next(&heights, reverse_begin(&heights));
while (l <= r) {
if (lpeak < rpeak) {
lpeak = maxint(lpeak, *l);
trapped += (lpeak - *l);
l = next(&heights, l);
} else {
rpeak = maxint(rpeak, *r);
trapped += (rpeak - *r);
r = reverse_next(&heights, r);
}
}
assert(trapped == correct_trapped);
return 0;
}flat_doubled_ended_queue.h (dropdown)
A dynamic or fixed size double ended queue offering contiguously stored elements. When fixed size, its behavior is that of a ring buffer.#include <assert.h>
#define FLAT_DOUBLE_ENDED_QUEUE_USING_NAMESPACE_CCC
#define TRAITS_USING_NAMESPACE_CCC
#include "ccc/flat_double_ended_queue.h"
#include "ccc/traits.h"
int
main(void) {
Flat_doubled_ended_queue q
= flat_doubled_ended_queue_with_storage(2, (int[2]){});
(void)push_back(&q, &(int){3}, &(CCC_Allocator){});
(void)push_front(&q, &(int){2}, &(CCC_Allocator){});
(void)push_back(&q, &(int){1}, &(CCC_Allocator){}); /* Overwrite 2. */
int *i = front(&q);
assert(*i == 3);
i = back(&q);
assert(*i == 1);
(void)pop_back(&q);
i = back(&q);
assert(*i == 3);
i = front(&q);
assert(*i == 3);
return 0;
}flat_hash_map.h (dropdown)
Amortized O(1) access to elements stored in a flat array by key. Not pointer stable.#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
#define FLAT_HASH_MAP_USING_NAMESPACE_CCC
#define TRAITS_USING_NAMESPACE_CCC
#include "ccc/flat_hash_map.h"
#include "ccc/traits.h"
struct Key_val {
int key;
int val;
};
static uint64_t
flat_hash_map_int_to_u64(CCC_Key_arguments const k) {
int const key_int = *((int *)k.key);
uint64_t x = key_int;
x = (x ^ (x >> 30)) * UINT64_C(0xbf58476d1ce4e5b9);
x = (x ^ (x >> 27)) * UINT64_C(0x94d049bb133111eb);
x = x ^ (x >> 31);
return x;
}
static CCC_Order
flat_hash_map_id_order(CCC_Key_comparator_arguments const cmp) {
struct Key_val const *const right = cmp.type_right;
int const left = *((int *)cmp.key_left;
return (left > right->key) - (left < right->key);
}
enum : size_t {
STANDARD_FIXED_CAP = 1024,
};
/* Longest Consecutive Sequence Leetcode Problem */
int
main(void) {
Flat_hash_map fh = flat_hash_map_with_storage(
key,
((CCC_Hasher){
.hash = flat_hash_map_int_to_u64,
.compare = flat_hash_map_id_order,
}),
(struct Key_val[STANDARD_FIXED_CAP]){}
);
/* Longest sequence is 1,2,3,4,5,6,7,8,9,10 of length 10. */
int const nums[] = {
99, 54, 1, 4, 9, 2, 3, 4, 8, 271, 32, 45, 86, 44, 7, 777, 6, 20,
19, 5, 9, 1, 10, 4, 101, 15, 16, 17, 18, 19, 20, 10, 21, 22, 23,
};
static_assert(sizeof(nums) / sizeof(nums[0]) < STANDARD_FIXED_CAP / 2);
int const correct_max_run = 10;
size_t const nums_size = sizeof(nums) / sizeof(nums[0]);
int max_run = 0;
for (size_t i = 0; i < nums_size; ++i) {
int const n = nums[i];
CCC_Entry const *const seen_n = flat_hash_map_try_insert_wrap(
&fh, &(struct Key_val){.key = n, .val = 1}, &(CCC_Allocator){}
);
/* We have already connected this run as much as possible. */
if (occupied(seen_n)) {
continue;
}
/* There may or may not be runs already existing to left and right. */
struct Key_val const *const connect_left
= get_key_value(&fh, &(int){n - 1});
struct Key_val const *const connect_right
= get_key_value(&fh, &(int){n + 1});
int const left_run = connect_left ? connect_left->val : 0;
int const right_run = connect_right ? connect_right->val : 0;
int const full_run = left_run + 1 + right_run;
/* Track solution to problem. */
max_run = full_run > max_run ? full_run : max_run;
/* Update the boundaries of the full run range. */
((struct Key_val *)unwrap(seen_n))->val = full_run;
CCC_Entry const *const run_min = flat_hash_map_insert_or_assign_wrap(
&fh,
&(struct Key_val){.key = n - left_run, .val = full_run},
&(CCC_Allocator){}
);
CCC_Entry const *const run_max = flat_hash_map_insert_or_assign_wrap(
&fh,
&(struct Key_val){.key = n + right_run, .val = full_run},
&(CCC_Allocator){}
);
/* Validate for testing purposes. */
assert(occupied(run_min));
assert(occupied(run_max));
assert(!insert_error(run_min));
assert(!insert_error(run_max));
}
assert(max_run == correct_max_run);
return 0;
}flat_priority_queue.h (dropdown)
#include <assert.h>
#define FLAT_PRIORITY_QUEUE_USING_NAMESPACE_CCC
#define TRAITS_USING_NAMESPACE_CCC
#include "ccc/flat_priority_queue.h"
#include "ccc/traits.h"
static CCC_Order
int_cmp(CCC_Comparator_arguments const ints) {
int const left = *(int *)ints.type_left;
int const right = *(int *)ints.type_right;
return (left > right) - (left < right);
}
/* In place O(N) heapify. */
int
main(void) {
int heap[20] = {12, 61, -39, 76, 48, -93, -77, -81, 35, 21,
-3, 90, 20, 27, 97, -22, -20, -19, 70, 76};
enum : size_t {
HCAP = sizeof(heap) / sizeof(*heap),
};
Flat_priority_queue priority_queue = flat_priority_queue_heapify(
int,
CCC_ORDER_LESSER,
(CCC_Comparator){.compare = int_cmp},
HCAP,
HCAP,
heap
);
int const prev = INT_MIN;
while (!is_empty(&priority_queue))
int const *const cur = front(&priority_queue);
assert(prev <= *cur);
prev = *cur;
pop(&priority_queue, &(int){});
}
return 0;
}priority_queue.h (dropdown)
A pointer stable priority queue offering O(1) push and efficient decrease, increase, erase, and extract operations.#include <assert.h>
#include <stdbool.h>
#define PRIORITY_QUEUE_USING_NAMESPACE_CCC
#define TRAITS_USING_NAMESPACE_CCC
#define TYPES_USING_NAMESPACE_CCC
#include "ccc/priority_queue.h"
#include "ccc/traits.h"
struct Val {
Priority_queue_node elem;
int val;
};
static CCC_Order
val_cmp(CCC_Comparator_arguments const cmp) {
struct Val const *const left = cmp.type_left;
struct Val const *const right = cmp.type_right;
return (left->val > right->val) - (left->val < right->val);
}
int
main(void) {
struct Val elems[5]
= {{.val = 3}, {.val = 3}, {.val = 7}, {.val = -1}, {.val = 5}};
Priority_queue priority_queue = priority_queue_default(
struct Val,
elem,
CCC_ORDER_LESSER,
(CCC_Comparator){.compare = val_cmp}
);
for (size_t i = 0; i < (sizeof(elems) / sizeof(elems[0])); ++i) {
struct Val const *const v
= push(&priority_queue, &elems[i].elem, &(CCC_Allocator){});
assert(v && v->val == elems[i].val);
}
bool const decreased = priority_queue_decrease_with(
&priority_queue, &elems[4].elem, { elems[4].val = -99; }
);
assert(decreased);
struct Val const *const v = front(&priority_queue);
assert(v->val == -99);
return 0;
}singly_linked_list.h (dropdown)
A low overhead push-to-front container. When contiguity is not possible and the access pattern resembles a stack this is more-efficient than a doubly-linked list.#include <assert.h>
#define SINGLY_LINKED_LIST_USING_NAMESPACE_CCC
#define TRAITS_USING_NAMESPACE_CCC
#include "ccc/singly_linked_list.h"
#include "ccc/traits.h"
struct Int_node {
int i;
Singly_linked_list_node e;
};
static CCC_Order
int_cmp(CCC_Comparator_arguments const cmp) {
struct Int_node const *const left = cmp.type_left;
struct Int_node const *const right = cmp.type_right;
return (left->i > right->i) - (left->i < right->i);
}
int
main(void) {
/* singly linked list l, list elem field e, no allocation permission,
comparing integers, no context data. */
Singly_linked_list l = singly_linked_list_default(struct Int_node, e);
struct Int_node elems[3] = {{.i = 3}, {.i = 2}, {.i = 1}};
(void)push_front(&l, &elems[0].e, &(CCC_Allocator){});
(void)push_front(&l, &elems[1].e, &(CCC_Allocator){});
(void)push_front(&l, &elems[2].e, &(CCC_Allocator){});
struct Int_node const *i = front(&l);
assert(i->i == 1);
pop_front(&l, &(CCC_Allocator){});
i = front(&l);
assert(i->i == 2);
return 0;
}tree_map.h (dropdown)
A pointer stable ordered map meeting strict O(lg N) runtime bounds for realtime applications.#include <assert.h>
#define TREE_MAP_USING_NAMESPACE_CCC
#define TRAITS_USING_NAMESPACE_CCC
#define TYPES_USING_NAMESPACE_CCC
#include "ccc/traits.h"
#include "ccc/tree_map.h"
struct Key_val {
Tree_map_node elem;
int key;
int val;
};
static CCC_Order
key_val_cmp(CCC_Key_comparator_arguments const cmp) {
struct Key_val const *const right = cmp.type_right;
int const key_left = *((int *)cmp.key_left);
return (key_left > right->key) - (key_left < right->key);
}
int
main(void) {
struct Key_val elems[25];
Tree_map s = tree_map_default(
struct Key_val,
elem,
key,
(CCC_Key_comparator){.compare = key_val_cmp}
);
int const num_nodes = 25;
/* 0, 5, 10, 15, 20, 25, 30, 35,... 120 */
for (int i = 0, id = 0; i < num_nodes; ++i, id += 5) {
elems[i].key = id;
elems[i].val = i;
(void)insert_or_assign(&s, &elems[i].elem, &(CCC_Allocator){});
}
/* This should be the following Range [6,44). 6 should raise to
next value not less than 6, 10 and 44 should be the first
value greater than 44, 45. */
int range_keys[8] = {10, 15, 20, 25, 30, 35, 40, 45};
Range r = equal_range(&s, &(int){6}, &(int){44});
int index = 0;
for (struct Key_val *i = range_begin(&r); i != range_end(&r);
i = next(&s, &i->elem)) {
assert(i->key == range_keys[index]);
++index;
}
/* This should be the following Range [119,84). 119 should be
dropped to first value not greater than 119 and last should
be dropped to first value less than 84. */
int range_reverse_keys[8] = {115, 110, 105, 100, 95, 90, 85, 80};
Range_reverse rr = equal_range_reverse(&s, &(int){119}, &(int){84});
index = 0;
for (struct Key_val *i = range_reverse_begin(&rr);
i != range_reverse_end(&rr); i = reverse_next(&s, &i->elem)) {
assert(i->key == range_reverse_keys[index]);
++index;
}
return 0;
}- Intrusive and non-intrusive containers.
- Allocator passing.
- Compile time initialization.
- Metadata is trivially copyable.
- No
container_ofmacro required of the user to get to their type after a function call. - Rust's Entry API for associative containers with C and C++ influences.
- Opt-in macros for more succinct insertion and in place modifications (see "closures" in the and_modify_wth interface for associative containers).
- Container Traits implemented with C
_Genericcapabilities.
Currently, many associative containers ask the user to store an element in their type. This means wrapping an element in a struct such as this type found in samples/graph.c for the priority queue.
struct Cost {
CCC_Priority_queue_node node;
int cost;
char name;
char from;
};The interface may then ask for a handle to this type for certain operations. For example, a priority queue has the following interface for pushing an element.
void *CCC_priority_queue_push(
CCC_Priority_queue *priority_queue,
CCC_Priority_queue_node *elem,
CCC_Allocator const *allocator
);Non-Intrusive containers exist when a flat container can operate without such help from the user. The Flat_priority_queue is a good example of this. When initializing we give it the following information.
CCC_Flat_priority_queue flat_priority_queue
= CCC_flat_priority_queue_with_storage(
CCC_ORDER_LESSER,
(CCC_Comparator){.compare = int_cmp},
(int[40]){}
);Here a small min priority queue of integers with a maximum capacity of 40 has been allocated on the stack with no allocation permission and no context data needed. As long as the flat priority queue knows the type upon initialization no intrusive elements are needed. We could have also initialized this container as empty.
CCC_Flat_priority_queue flat_priority_queue
= CCC_flat_priority_queue_default(
int,
CCC_ORDER_LESSER,
(CCC_Comparator){.compare = int_cmp},
);The interface then looks like this.
void *CCC_flat_priority_queue_push(
CCC_Flat_priority_queue *flat_priority_queue,
void const *element,
void *temp,
CCC_Allocator const *allocator
);The element element here is just a generic reference to whatever type the user stores in the container and temp is a swap slot provided by the user.
The C Container Collection does not call malloc, realloc, or free directly. Instead, containers that may need to allocate memory accept an allocator argument at every call site where allocation could occur. This makes allocation visible in code rather than hidden inside container operations.
An allocator is a small struct bundling a function pointer and optional context.
typedef struct {
CCC_Allocator_interface *allocate;
void *context;
} CCC_Allocator;The CCC_Allocator_interface function type implements a unified interface for allocation, reallocation, and deallocation. See types.h for the full contract. A standard library backed allocator might look like this:
void *
std_allocate(CCC_Allocator_arguments const arguments)
{
if (!arguments.input && !arguments.bytes) {
return NULL;
}
if (!arguments.input) {
return malloc(arguments.bytes);
}
if (!arguments.bytes) {
free(arguments.input);
return NULL;
}
return realloc(arguments.input, arguments.bytes);
}
static CCC_Allocator const std_allocator = {.allocate = std_allocate};Container code always accepts the allocator by const *, so sharing an allocator instance across threads is safe if the allocator provided is thread safe.
Any function that may need to allocate accepts a CCC_Allocator const * as its last argument:
CCC_flat_priority_queue_push(&pq, &(int){1}, &(int){}, &std_allocator);
CCC_flat_priority_queue_push(
&pq,
&(int){2},
&(int){},
&(CCC_Allocator){.allocate = arena_allocate, .context = &arena}
);Functions that never allocate do not accept an allocator argument. The presence or absence of the allocator argument in a function signature is the signal of whether that function may allocate.
To explicitly prevent allocation pass an empty allocator.
CCC_flat_priority_queue_push(&pq, &(int){1}, &(int){}, &(CCC_Allocator){});An empty CCC_Allocator has NULL internal fields. The container checks for this and returns an appropriate error rather than attempting allocation. Never pass NULL to any function in the C Container Collection.
Passing allocators makes auditing CCC code easy.
Important
A non-empty allocator allocator argument signals allocation may occur.
An empty allocator argument signals allocation is forbidden.
A NULL argument at any C Container Collection function call site is always a programmer error.
Because the user may choose the source of memory for a container, initialization at compile time is possible for all intrusive and non-intrusive containers.
This is especially helpful for the containers that use buffer, arrays, and flat memory layouts when their capacity will be fixed for their lifetime. These containers can be prepared at compile time.
struct Key_val {
int key;
int val;
};
static CCC_Array_adaptive_map adaptive_map
= CCC_array_adaptive_map_with_storage(
key,
(CCC_Key_comparator){.compare = compare_int_key},
(struct Key_val[1024]){}
);
static CCC_Array_tree_map tree_map
= CCC_array_tree_map_with_storage(
key,
(CCC_Key_comparator){.compare = compare_int_key},
(struct Key_val[1024]){}
);
static CCC_Flat_hash_map hash_map
= CCC_flat_hash_map_with_storage(
key,
((CCC_Hasher){.hash = hash_int, .compare = compare_int_key}),
(struct Key_val[1024]){}
);
static CCC_Flat_priority_queue priority_queue
= CCC_flat_priority_queue_with_storage(
CCC_ORDER_LESSER,
(CCC_Comparator){.compare = compare_int},
(int[1024]){}
);
static CCC_Flat_double_ended_queue ring_buffer
= CCC_flat_double_ended_queue_with_storage(
0,
(int[1024]){}
);
static CCC_Flat_buffer buffer
= CCC_flat_buffer_with_storage(
0,
(int[1024]){}
);
static CCC_Flat_bitset bitset
= CCC_flat_bitset_with_storage(
1024,
(CCC_Bit[1024]){}
);Because the above containers are of fixed size, the empty &(CCC_Allocator){} will be passed to any functions requesting an allocator. If containers are going to grow dynamically at runtime, they can still be initialized at compile time.
static CCC_Flat_hash_map hash_map = CCC_flat_hash_map_default(
struct Key_val,
key,
((CCC_Hasher){.hash = hash_int, .compare = compare_int_key})
);Then, a non empty &std_allocator or &(CCC_Allocator){.allocate = arena_allocate, .context = &arena} will be passed to functions that accept an allocator.
For all containers, the metadata structure that is passed to interface functions is separate from the underlying storage and has no self-referential pointers. The metadata only stores configuration and references to externally managed storage. Therefore, the metadata structure can be safely copied and returned by value.
static CCC_Doubly_linked_list
construct_empty(void) {
CCC_Doubly_linked_list this = CCC_doubly_linked_list_default(struct Val, e);
return this;
}
int
main(void) {
CCC_Doubly_linked_list list = construct_empty();
doubly_linked_list_push_front(&list, &(struct Val){.val = 1}.e);
assert(is_empty(&list) == false);
assert(validate(&list));
return 0;
}For other C container libraries the metadata structure may contain sentinel fields to which the metadata structure or external allocations point, making the above example exhibit undefined behavior. In the C Container Collection, fields within a metadata structure are never referenced from either the metadata structure itself or the allocations it manages. Therefore, returning the metadata structure for a container is well defined. This means users can organize their code how they wish, given their own standards of encapsulation and readability. However, keep in mind that C performs shallow copies by default. Therefore, copying a container metadata structure does not duplicate underlying nodes, buffers, or arrays to which it points. Instead, the new metadata instance will refer to the same underlying storage as the original container.
Traditionally, intrusive containers provide the following macro.
/** list_entry - get the struct for this entry
@pointer the &struct list_node pointer.
@type the type of the struct this is embedded in.
@member the name of the list_node within the struct. */
#define list_entry(pointer, type, member) container_of(pointer, type, member)
/* A provided function by the container. */
struct List_node *list_front(list *l);Then, the user code looks like this.
struct Id {
int id;
struct List_node id_node;
};
int
main(void) {
static struct List id_list = list_initialize(id_list);
/* ...fill list... */
struct Id *front = list_entry(list_front(&id_list), struct Id, id_node);
}Here, it may seem manageable to use such a macro, but it is required at every location in the code where the user type is needed. The opportunity for bugs in entering the type or field name grows the more the macro is used. It is better to take care of this step for the user and present a cleaner interface.
Here is the same list example in the C Container Collection.
struct Id {
int id;
CCC_Doubly_linked_list_node id_node;
};
int
main(void) {
static CCC_Doubly_linked_list id_list
= CCC_doubly_linked_list_default(struct Id, id_node);
/* ...fill list... */
struct Id *front = CCC_doubly_linked_list_front(&id_list);
struct Id *new_id = generate_id();
struct Id *new_front = CCC_doubly_linked_list_push_front(
&id_list, &new_id->id_node, &std_allocator
);
}Internally the containers will remember the offsets of the provided elements within the user struct wrapping the intruder. Then, the contract of the interface is simpler: provide a handle to the container and receive your type in return. The user takes on less complexity overall by providing a slightly more detailed initialization. If the container does not require intrusive elements than this is not a concern to begin with. However, this ensures consistency across return values to access user types for intrusive and non-intrusive containers: a reference to the user type is always returned.
Rust has solid interfaces for associative containers, largely due to the Entry Interface. In the C Container Collection the core of all associative containers is inspired by the Entry Interface (these versions are found in ccc/traits.h but specific names, behaviors, and parameters can be read in each container's header).
CCC_Entry(container_pointer, key_pointer...)- Obtains an entry, a view into an Occupied or Vacant user type stored in the container.CCC_and_modify(entry_pointer, mod_fn)- Modify an occupied entry with a callback.CCC_and_context_modify(entry_pointer, mod_fn, context_arguments)- Modify an Occupied entry with a callback that requires context data.CCC_or_insert(entry_pointer, or_insert_arguments)- Insert a default key value if Vacant or return the Occupied entry.CCC_insert_entry(entry_pointer, insert_entry_arguments)- Invariantly insert a new key value, overwriting an Occupied entry if needed.CCC_remove_entry(entry_pointer)- Remove an Occupied entry from the container or do nothing.
Other Rust Interface functions like get_key_value, insert, and remove are included and can provide information about previous values stored in the container.
Each container offers it's own C version of "closures" for the and_modify_with. Here is an example from the samples/words.c program.
and_modify_with(map_entry_pointer, closure_parameter, closure_over_closure_parameter...)- Run code inclosure_over_closure_parameteron the user named pointer type for that closure.
typedef struct {
String_offset ofs;
int cnt;
} Word;
/* Increment a found Word or insert a default count of 1. */
CCC_Handle_index const h = array_adaptive_map_or_insert_with(
array_adaptive_map_and_modify_with(
handle_wrap(&hom, &key_ofs), Word * w, { w->cnt++; }
),
&std_allocator,
(Word){.ofs = ofs, .cnt = 1}
);This is possible because of the details discussed in the previous section. Containers can always provide the user type stored in the container directly. However, there are other options to achieve the same result.
Some C++ associative container interfaces have also been adapted to the Entry Interface.
CCC_try_insert(container_pointer, try_insert_arguments...)- Inserts a new element if none was present and reports if a previous entry existed.CCC_insert_or_assign(container_pointer, insert_or_assign_arguments...)- Inserts a new element invariantly and reports if a previous entry existed.
Many other containers fall back to C++ style interfaces when it makes sense to do so.
Many of the above functions come with an optional macro variant. For example, the or_insert function for associative containers will come with an or_insert_with variant. The word "with" in this context means a direct r-value.
Here is an example for generating a maze with Prim's algorithm in the samples/maze.c sample.
The functional version.
struct Point const next = {
.r = c->cell.r + dir_offsets[i].r,
.c = c->cell.c + dir_offsets[i].c,
};
struct Prim_cell new = (struct Prim_cell){
.cell = next,
.cost = rand_range(0, 100),
};
struct Prim_cell *const cell = or_insert(
flat_hash_map_entry_wrap(&cost_map, &next, &std_allocator), &new
);The lazily evaluated macro version.
struct Point const next = {
.r = c->cell.r + dir_offsets[i].r,
.c = c->cell.c + dir_offsets[i].c,
};
struct Prim_cell const *const cell = flat_hash_map_or_insert_with(
flat_hash_map_entry_wrap(&cost_map, &next, &std_allocator),
(struct Prim_cell){ .cell = next, .cost = rand_range(0, 100)}
);The second example is slightly more convenient and efficient. The compound literal is provided to be directly assigned to a Vacant memory location allowing the compiler to decide how the copy should be performed; it is only constructed if there is no entry present. This also means the random generation function is only called if a Vacant entry requires the insertion of a new value. So, expensive function calls can be lazily evaluated only when needed.
The lazy evaluation of the _with family of functions offer an expressive way to write C code when needed. See each container's header for more.
Traits, found in ccc/traits.h, offer a more succinct way to use shared functionality across containers. Instead of calling CCC_flat_hash_map_entry when trying to obtain an entry from a flat hash map, one can simply call entry. Traits utilize _Generic in C to choose the correct container function based on parameters provided.
Traits cost nothing at runtime but may slightly increase compilation memory use.
#define TRAITS_USING_NAMESPACE_CCC
typedef struct {
str_ofs ofs;
int cnt;
} Word;
/* ... Elsewhere generate offset ofs as key. */
Word default = {.ofs = ofs, .cnt = 1};
CCC_Handle_index const h = or_insert(
and_modify(array_tree_map_handle_wrap(&map, &ofs), increment),
&default,
&std_allocator
);Or the following.
#define TRAITS_USING_NAMESPACE_CCC
typedef struct {
str_ofs ofs;
int cnt;
} Word;
/* ... Elsewhere generate offset ofs as key. */
Word default = {.ofs = ofs, .cnt = 1};
Array_adaptive_map_handle *h = array_tree_map_handle_wrap(&map, &ofs);
h = and_modify(h, increment);
Word *w = array_adaptive_map_at(&map, or_insert(h, &default, &std_allocator));Traits are completely opt-in by including the traits.h header.
Another concern for the programmer related to allocation may be constructors and destructors, a C++ shaped peg for a C shaped hole. In general, this library has some limited support for destruction but does not provide an interface for direct constructors as C++ would define them; though this may change.
Consider a constructor. If the container is allowed to allocate, and the user wants to insert a new element, they may see an interface like this (pseudocode as all containers are slightly different).
void *insert_or_assign(Container *c, Container_node *e, Allocator const *);Because the user has wrapped the intrusive container element in their type, the entire user type will be written to the new allocation. All interfaces can also confirm when insertion succeeds if global state needs to be set in this case. So, if some action beyond setting values needs to be performed, there are multiple opportunities to do so.
For destructors, the argument is similar but the container does offer more help. If an action other than freeing the memory of a user type is needed upon removal, there are options in an interface to obtain the element to be removed. Associative containers offer functions that can obtain entries (similar to Rust's Entry API). This reference can then be examined and complex destructor actions can occur before removal. Other containers like lists or priority queues offer references to an element of interest such as front, back, max, min, etc. These can all allow destructor-like actions before removal. One exception is the following interfaces.
The clear function works for pointer stable containers and flat containers.
Result clear(Container *c, Destructor const *destuctor);The clear and free function works for flat containers.
Result clear_and_free(
Container *c,
Destructor const *destructor,
Allocator const *allocator
);The above functions free the resources of the container. Because there is no way to access each element before it is freed when this function is called, a destructor callback can be passed to operate on each element before the allocator is called.
For examples of what code that uses these ideas looks like, read and use the sample programs in the samples/. I try to only add non-trivial samples that do something mildly interesting to give a good idea of how to take advantage of this flexible memory philosophy.
The samples are not included in the release. To build them, clone the repository. Usage instructions should be available with the -h flag to any program or at the top of the file.
Clang.
make all-clang-release
./build/bin/[SAMPLE] [SAMPLE CLI ARGS]GCC.
make all-gcc-release
./build/bin/[SAMPLE] [SAMPLE CLI ARGS]The tests also include various use cases that may be of interest. Tests are not included in the release. Clone the repository.
Clang.
make all-clang-release
make testGCC.
make all-gcc-release
make testThe C Container Collection is extensively tested and analyzed both statically and at runtime. See the tests/ repository which is always seeking valuable additions. Also, visit CONTRIBUTING.md to see the extensive tooling that is constantly run locally and over CI via actions in the .github/workflows folder. Tools include clang-format, clang-tidy, pre-commit, GCC's -fanalyzer, and GCC's extensive address and undefined behavior sanitizers. Builds for both Linux x86 and MacOS ARM run on every commit in pull requests, with additional portable implementation variants built. I aim to deliver a high quality library and welcome any suggestions for tools to further improve code quality.
If you are interested in contributing, tests that increase code coverage are a good way to start. View the coverage report here.
- Why explicit allocator passing? The C Container Collection does not call
malloc,realloc, orfreedirectly. Passing allocators at call sites makes allocation visible and auditable rather than hidden inside container operations. It also decouples the container from any specific memory strategy. This is particularly valuable in kernel and embedded contexts where allocation in certain code paths is forbidden. The overall idea is taken from Zig, which I think got this approach right in terms of useful patterns. See the Allocator Passing section for more. - Why are non-allocating containers needed? They are quite common in Operating Systems development. Kernel code may manage a process or thread that is part of many OS subsystems: the CPU scheduler, the virtual memory paging system, the child and parent process spawn and wait mechanisms. All of these systems require that the process use or be a part of some data structures. It is easiest to separate participation in these data structures from memory allocation. The process holds handles to intrusive elements to participate in these data structures because the thread/task/process will live until it has finished executing meaning its lifetime is greater than or equal to the longest lifetime data structure of which it is a part. Embedded developers also often seem interested in non-allocating containers when an entire program's memory use is known before execution begins. However, this library explores if non-allocating containers can have more general applications for creative C programming.
- Why is initialization so ugly? Yes, this is a valid concern. Upfront complexity helps eliminate the need for a
container_ofmacro for the user see the no container_of macros section for more. Later code becomes much cleaner and simpler. - Why callbacks? Freedom for more varied comparisons and allocations. Learn to love context data. Also you have the chance to craft the optimal function for your application; for example writing a perfectly tailored hash function for your data set.
- Why not header only? Readability, maintainability, and update ability, for changing implementations in the source files. If the user wants to explore the implementation everything should be easily understandable. This can also be helpful if the user wants to fork and change a data structure to fit their needs. Smaller object size and easier modular compilation is also nice.
- Why not opaque pointers and true implementation hiding? This is not possible in C if the user is in charge of memory. The container types must be complete if the user wishes to store them on the stack or data segment. I try to present a clean interface.
- Why
Array_andFlat_maps? Mostly experimenting. A flat hash map offers the ability to pack user data and fingerprint meta data in separate contiguous arrays within the same allocation. The handle variants of containers offer the same benefit along with handle stability. Many also follow the example of Zig with its Struct of Arrays approach to many data structures. Struct of Array (SOA) style data structures focus on space optimizations due to perfect alignment of user types, container metadata, and any supplementary data in separate arrays but within the same allocation. - Why
C23? Several C23 features are foundational to this library: typed enums for precise constant types,static_assertin more contexts for compile time validation, improved compound literal semantics for compile time initialization, andtypeoffor macro type safety. Clang 19.1.1 and GCC 14.2 cover the features needed for release packages.
If these containers do not fit your needs, here are some other data structure libraries I have found for C. If your project is at the application layer, where type safety and ergonomics are the primary concerns, these libraries are excellent choices and may be simpler to integrate than the C Container Collection. This collection is designed for projects where explicit memory control, allocation auditability, and separations between data structure and data memory management may be required.
A few containers are based off of important work by other data structure developers and researchers. Here are the data structures that inspired some containers in this collection. Full citations and notices of changes can be read in the respective implementations in source/ directory.
- Rust's hashbrown hash table was the basis for the
flat_hash_map.hcontainer. - Phil Vachon's implementation of a WAVL tree was the inspiration for the
tree_map.hcontainers. - Research by Daniel Sleator in implementations of Splay Trees helped shape the
adaptive_map.hcontainers.