CCC_Doubly_linked_list Struct Reference

#include <private_doubly_linked_list.h>

Collaboration diagram for CCC_Doubly_linked_list:

Detailed Description

A doubly linked list storing head and tail pointers. The list supports O(1) push, pop, insert, and erase at arbitrary positions.

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 NULL head and tail pointers 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_Doubly_linked_list_node *	head
struct CCC_Doubly_linked_list_node *	tail
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_Doubly_linked_list::allocate

The user provided allocation function, if any.

compare

CCC_Type_comparator* CCC_Doubly_linked_list::compare

The user provided comparison callback for sorting.

context

void* CCC_Doubly_linked_list::context

User provided context data, if any.

count

size_t CCC_Doubly_linked_list::count

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

head

struct CCC_Doubly_linked_list_node* CCC_Doubly_linked_list::head

Pointer to the head element or NULL if list empty.

sizeof_type

size_t CCC_Doubly_linked_list::sizeof_type

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

tail

struct CCC_Doubly_linked_list_node* CCC_Doubly_linked_list::tail

Pointer to the tail element or NULL if list empty.

type_intruder_offset

size_t CCC_Doubly_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_doubly_linked_list.h