Core Concepts

Relevant source files

• src/linked_list.rs
• src/raw_list.rs

This page provides a deep dive into the fundamental concepts that enable the linked_list_r4l crate to provide intrusive linked lists with constant-time arbitrary removal and thread safety. It covers the trait system, memory layout, atomic operations, and safety architecture that form the foundation of the library.

For basic usage patterns, see Quick Start Guide. For detailed API documentation, see API Reference. For memory management specifics, see Memory Management. For thread safety implementation details, see Thread Safety.

The GetLinks Trait System

The core of the linked list architecture is built around two key traits that enable intrusive linking while maintaining type safety and flexible ownership models.

GetLinks Trait

The GetLinks trait is the fundamental abstraction that allows any type to participate in a linked list by providing access to embedded linking metadata.

flowchart TD
GetLinks["GetLinks trait"]
EntryType["type EntryType: ?Sized"]
GetLinksMethod["fn get_links(&EntryType) -> &Links"]
UserStruct["User-defined struct"]
LinksField["links: Links"]
UserImpl["impl GetLinks for UserStruct"]

GetLinks --> EntryType
GetLinks --> GetLinksMethod
GetLinksMethod --> LinksField
UserImpl --> GetLinks
UserStruct --> LinksField
UserStruct --> UserImpl

GetLinks Trait Definition and Usage

The trait defines two essential components:

• EntryType: The type of objects that will be stored in the list
• get_links(): A function that returns a reference to the Links struct embedded in the entry

This design enables a type to be in multiple different lists simultaneously by implementing GetLinks multiple times with different associated types.

GetLinksWrapped Trait

The GetLinksWrapped trait extends GetLinks to add ownership management through the Wrapper trait, enabling safe memory management across different allocation strategies.

flowchart TD
GetLinksWrapped["GetLinksWrapped trait"]
GetLinksBase["extends GetLinks"]
WrappedType["type Wrapped: Wrapper"]
BoxImpl["impl GetLinksWrapped for Box"]
ArcImpl["impl GetLinksWrapped for Arc"]
BoxWrapper["Box: Wrapper"]
ArcWrapper["Arc: Wrapper"]
RefWrapper["&T: Wrapper"]
Wrapper["Wrapper trait"]
IntoPtr["fn into_pointer(self) -> NonNull"]
FromPtr["unsafe fn from_pointer(NonNull) -> Self"]
AsRef["fn as_ref(&self) -> &T"]

ArcImpl --> ArcWrapper
ArcImpl --> GetLinksWrapped
ArcWrapper --> Wrapper
BoxImpl --> BoxWrapper
BoxImpl --> GetLinksWrapped
BoxWrapper --> Wrapper
GetLinksWrapped --> GetLinksBase
GetLinksWrapped --> WrappedType
RefWrapper --> Wrapper
Wrapper --> AsRef
Wrapper --> FromPtr
Wrapper --> IntoPtr

Trait Relationship and Implementation

Sources: src/raw_list.rs(L23 - L29)  src/linked_list.rs(L86 - L96)  src/linked_list.rs(L18 - L31) 

Links and ListEntry Structure

The Links struct contains the core linking infrastructure that enables intrusive list membership with atomic insertion tracking.

Memory Layout and Components

flowchart TD
subgraph subGraph2["ListEntry Structure"]
    ListEntry["ListEntry"]
    Next["next: Option>"]
    Prev["prev: Option>"]
end
subgraph subGraph1["Links Structure"]
    Links["Links"]
    Inserted["inserted: AtomicBool"]
    Entry["entry: UnsafeCell>"]
end
subgraph subGraph0["Node Memory Layout"]
    Node["User Node Struct"]
    UserData["user data fields"]
    LinksField["links: Links"]
end

Entry --> ListEntry
Links --> Entry
Links --> Inserted
LinksField --> Links
ListEntry --> Next
ListEntry --> Prev
Node --> LinksField
Node --> UserData

Links Structure Components

The Links<T> struct contains two critical fields:

1. inserted: AtomicBool - Atomic flag tracking whether the node is currently inserted in any list
2. entry: UnsafeCell<ListEntry<T>> - Contains the actual next/prev pointers wrapped in UnsafeCell for interior mutability

The ListEntry<T> struct contains the doubly-linked list pointers:

• next: Option<NonNull<T>> - Pointer to the next node in the list
• prev: Option<NonNull<T>> - Pointer to the previous node in the list

Atomic Insertion Tracking

The atomic insertion flag provides thread-safe tracking of list membership and prevents double-insertion:

Sources: src/raw_list.rs(L35 - L66)  src/raw_list.rs(L74 - L86) 

Constant-Time Arbitrary Removal

The intrusive design enables O(1) removal of any node from the list without requiring traversal to find the node's neighbors.

Removal Algorithm

Key Algorithmic Properties

1. No Traversal Required: Because each node contains its own links, removal requires no list traversal
2. Atomic Safety: The inserted flag prevents concurrent modifications during removal
3. Neighbor Updates: Only the immediate neighbors need pointer updates
4. Head Management: Special handling when removing the head node

The algorithm handles three cases:

• Single node: Set head = None
• Head node: Update head to point to next node
• Interior node: Update neighbor pointers only

Insertion Tracking and Race Prevention

Race Condition Prevention

The atomic inserted flag prevents several race conditions:

• Double insertion: Only one thread can successfully set inserted from false to true
• Insertion during removal: Removal always succeeds once a node is inserted
• Memory ordering: Acquire on insertion synchronizes with Release on removal

Sources: src/raw_list.rs(L57 - L65)  src/raw_list.rs(L199 - L235)  src/raw_list.rs(L140 - L151) 

Memory Safety Architecture

The library implements a layered safety model that transitions from safe ownership management to unsafe pointer operations.

Safety Boundary and Wrapper Abstraction

flowchart TD
subgraph subGraph2["Unsafe Zone"]
    NonNullPtrs["NonNull"]
    RawList["RawList operations"]
    PtrArithmetic["Pointer manipulation"]
end
subgraph subGraph1["Wrapper Boundary"]
    WrapperTrait["Wrapper trait"]
    IntoPtr["into_pointer() -> NonNull"]
    FromPtr["from_pointer(NonNull) -> Self"]
    AsRef["as_ref() -> &T"]
end
subgraph subGraph0["Safe Zone"]
    UserCode["User Code"]
    BoxOwned["Box"]
    ArcShared["Arc"]
    RefBorrowed["&Node"]
end

ArcShared --> WrapperTrait
BoxOwned --> WrapperTrait
FromPtr --> NonNullPtrs
IntoPtr --> NonNullPtrs
NonNullPtrs --> RawList
RawList --> PtrArithmetic
RefBorrowed --> WrapperTrait
UserCode --> ArcShared
UserCode --> BoxOwned
UserCode --> RefBorrowed
WrapperTrait --> AsRef
WrapperTrait --> FromPtr
WrapperTrait --> IntoPtr

Ownership Model Abstraction

The Wrapper trait abstracts over different ownership models:

Safe-to-Unsafe Transition

The transition from safe to unsafe code follows a specific protocol:

1. Entry: Safe wrapper objects are converted to raw pointers via into_pointer()
2. Operation: Unsafe RawList operations manipulate the raw pointers
3. Exit: Raw pointers are converted back to safe wrappers via from_pointer()

This ensures that:

• Memory safety is maintained at the boundaries
• Ownership transfer is explicit and controlled
• Unsafe operations are isolated to the core implementation

Sources: src/linked_list.rs(L18 - L83)  src/linked_list.rs(L86 - L89)  src/linked_list.rs(L127 - L162) 

Cursors and Iteration

The library provides cursor-based iteration that enables both inspection and mutation of list elements during traversal.

Cursor Implementation Architecture

flowchart TD
subgraph subGraph2["List Integration"]
    RawList["**RawList"]
    ListHead["head: Option>"]
    CircularLinks["Circular next/prev pointers"]
end
subgraph subGraph1["Common Operations"]
    CommonCursor["**CommonCursor"]
    MoveNext["move_next()"]
    MovePrev["move_prev()"]
    Current["cur: Option>"]
end
subgraph subGraph0["Cursor Types"]
    Cursor["Cursor<'a, G>"]
    CursorMut["CursorMut<'a, G>"]
    Iterator["Iterator<'a, G>"]
end

CommonCursor --> Current
CommonCursor --> MoveNext
CommonCursor --> MovePrev
Cursor --> CommonCursor
CursorMut --> CommonCursor
Iterator --> Cursor
MoveNext --> RawList
MovePrev --> RawList
RawList --> CircularLinks
RawList --> ListHead

Cursor Navigation Logic

Cursors navigate the circular list structure by:

1. Forward movement: Follow next pointers until reaching the head again
2. Backward movement: Follow prev pointers until reaching the head again
3. Boundary detection: Stop iteration when returning to the starting position

The circular structure simplifies navigation logic and eliminates special cases for list boundaries.

Mutable Cursor Operations

CursorMut provides additional operations for list modification during iteration:

Sources: src/raw_list.rs(L286 - L329)  src/raw_list.rs(L339 - L423)  src/raw_list.rs(L433 - L464)