CCC_Singly_linked_list Struct Reference

#include <private_singly_linked_list.h>

Collaboration diagram for CCC_Singly_linked_list:

Detailed Description

A singly linked list storing head and tail pointers. The list supports O(1) push and pop at the front position.

Sentinel-based lists are common in C++ and other languages, but they are problematic in standard C. A sentinel stored inside the list struct requires a stable address. However, by default C copies struct by value, and such copies would also copy the sentinel node. For example, if the user writes a simple helper function that initializes the list with some extra constructor-like actions and returns it to the caller a copy occurs. The sentinel next and previous pointers would then point into the old stack frame, producing immediate undefined behavior once the original struct goes out of scope.

Because C has no constructors, destructors, or move semantics, the API cannot prevent users from copying the list structure. Therefore, a sentinel embedded in the list cannot be used safely. To ensure correct behavior under normal C copy semantics, this implementation uses a NULL head pointer to represent an empty list, and performs the required NULL checks when modifying nodes.

This design also improves composability in multithreaded programs. Because the list does not rely on a static global sentinel either, each thread may create its own independent list (e.g., inside a per-thread memory arena or thread stack frame) without hidden static state. The user can pass in context upon initialization for these more advanced use cases.

Note that the list itself is not thread-safe; external synchronization is still required if multiple threads access the same list.

Data Fields
struct CCC_Singly_linked_list_node *	head
size_t	count
size_t	sizeof_type
size_t	type_intruder_offset
CCC_Type_comparator *	compare
CCC_Allocator *	allocate
void *	context

Field Documentation

allocate

CCC_Allocator* CCC_Singly_linked_list::allocate

The user provided allocation function, if any.

compare

CCC_Type_comparator* CCC_Singly_linked_list::compare

The user provided comparison callback for sorting.

context

void* CCC_Singly_linked_list::context

User provided context data, if any.

count

size_t CCC_Singly_linked_list::count

The number of elements constantly tracked for O(1) check.

head

struct CCC_Singly_linked_list_node* CCC_Singly_linked_list::head

The pointer to the current head of the list.

sizeof_type

size_t CCC_Singly_linked_list::sizeof_type

The size in bytes of the type which wraps this handle.

type_intruder_offset

size_t CCC_Singly_linked_list::type_intruder_offset

The offset in bytes of the intrusive element in user type.

---

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

• ccc/private/private_singly_linked_list.h