Linked List

Introduction

Overview

This document describes the Linked List component of the Easy Embedded Framework. The linked list is a fundamental data structure that provides dynamic memory organization and efficient insertion/removal operations.

What This Component Does

The linked list component provides a doubly-linked circular list implementation inspired by the Linux kernel’s list implementation. It enables:

• Dynamic collection of nodes without fixed size constraints

• Forward and backward traversal through the list

• Embedding list nodes directly into user-defined structures

• Generic container for organizing data of any type

What This Component Does NOT Do

• Does NOT provide automatic memory allocation (nodes must be pre-allocated or managed by user)

• Does NOT include sorting or searching algorithms

• Does NOT provide thread-safety or locking mechanisms

• Does NOT manage data payload directly (only manages the linking structure)

Component’s Structure

Architecture Overview

The linked list component consists of:

1. Core Data Structure: struct Node - metadata holding next and previous pointers

2. Helper Macros: Convenience macros for common operations (iteration, insertion, extraction)

3. Public API Functions: Core operations like append, insert, unlink, and search

4. Design Pattern: Intrusive linked list (nodes embedded in user structures)

The intrusive design allows the list node to be embedded anywhere in a user-defined structure, avoiding separate allocation for the list metadata.

Node Structure

The node structure is minimal and efficient:

struct Node {
    struct Node * next;  // Pointer to next node in the list
    struct Node * prev;  // Pointer to previous node in the list
};

Circular List Design

The linked list uses a circular doubly-linked design where:

• The list is represented by a head/sentinel node

• The head node’s next points to the first data node

• The head node’s prev points to the last data node

• An empty list has the head pointing to itself

• This eliminates special cases for list boundaries

Visual representation of a circular list with 3 nodes:

        graph LR
    Head["Head<br/>(Sentinel Node)"]
    Node1["Node 1"]
    Node2["Node 2"]
    Node3["Node 3"]

    Head -->|next| Node1
    Node1 -->|next| Node2
    Node2 -->|next| Node3
    Node3 -->|next| Head

    Head -.->|prev| Node3
    Node3 -.->|prev| Node2
    Node2 -.->|prev| Node1
    Node1 -.->|prev| Head
    

Intrusive Design Pattern

Instead of wrapping data in a node, the node is embedded in the user’s structure:

// User-defined structure containing a list node
struct Task {
    uint32_t task_id;
    void (*handler)(void);
    struct Node list_node;  // Embedded node
};

// To get the parent structure from a node:
struct Task *task = EZ_LINKEDLIST_GET_PARENT_OF(node, list_node, struct Task);

This approach provides:

• Memory Efficiency: No extra allocation for list metadata

• Flexibility: One structure can participate in multiple lists (multiple embedded nodes)

• Cache Locality: Data and list metadata reside close together

Component’s Behavior

External Behavior

The component provides the following operations:

Initialization

void ezLinkedList_InitNode(struct Node* node);

Initializes a new node with both next and prev pointing to itself (empty single-node state).

List Operations

// Append new_node after node in the list
bool ezLinkedList_AppendNode(struct Node *new_node, struct Node *node);

// Insert new_node at the head position
struct Node *ezLinkedList_InsertNewHead(struct Node *current_head,
                                        struct Node *new_node);

// Remove the head node from the list
struct Node *ezLinkedList_UnlinkCurrentHead(struct Node *head);

Query Operations

// Get the number of nodes in the list
uint16_t ezLinkedList_GetListSize(struct Node* list_head);

// Check if a node exists in the list
bool ezLinkedList_IsNodeInList(struct Node *head, struct Node *searched_node);

Helper Macros

// Iterate through all nodes in a list
EZ_LINKEDLIST_FOR_EACH(node, head)

// Initialize a node (compile-time)
EZ_LINKEDLIST_INIT_NODE(name)

// Add node at head position
EZ_LINKEDLIST_ADD_HEAD(list_head, node)

// Add node at tail position
EZ_LINKEDLIST_ADD_TAIL(list_head, node)

// Unlink a node from the list
EZ_LINKEDLIST_UNLINK_NODE(node)

// Check if list is empty
IS_LIST_EMPTY(list_head)

// Get the parent structure from an embedded node
EZ_LINKEDLIST_GET_PARENT_OF(ptr, member, type)

State Diagram

A single node’s state transitions:

        stateDiagram-v2
    [*] --> Initialized: ezLinkedList_InitNode()
    Initialized --> InList: AppendNode()<br/>InsertNewHead()
    InList --> Initialized: UnlinkCurrentHead()<br/>UNLINK_NODE()
    Initialized --> [*]
    

Operation Sequences

Appending a Node

        sequenceDiagram
    participant New as New Node
    participant Ref as Reference Node
    participant Next as Next Node

    Note over New: new_node->next<br/>new_node->prev
    Note over Ref: ref_node
    Note over Next: next_node

    New->>Ref: Get ref->next
    activate Ref
    Ref-->>New: Returns next_node
    deactivate Ref

    Note over New: 1. new_node->next = next_node
    Note over New: 2. new_node->prev = ref_node
    Note over Next: 3. next_node->prev = new_node
    Note over Ref: 4. ref_node->next = new_node
    

List Iteration

        flowchart TD
    A["Start: node = head->next"] --> B{"node != head?"}
    B -->|Yes| C["Process node"]
    C --> D["node = node->next"]
    D --> B
    B -->|No| E["End"]
    

Internal Behavior

Circular Structure Advantages

The circular design eliminates special cases:

1. No NULL checks for end of list: The sentinel wraps around to the beginning

2. Same operation for head and tail: Both use the same append mechanism

3. Efficient empty list check: Simply compare head->next == head

Append Operation Details

The ezLinkedList_AppendNode() function inserts new_node after a given node:

bool ezLinkedList_AppendNode(struct Node* new_node, struct Node* node)
{
    if (new_node != NULL && node != NULL)
    {
        new_node->next = node->next;      // 1. new_node points to node's next
        new_node->prev = node;             // 2. new_node's prev points to node
        node->next->prev = new_node;       // 3. old next node's prev points to new_node
        node->next = new_node;             // 4. node's next points to new_node
        return true;
    }
    return false;
}

This operation is atomic and maintains list integrity.

Component’s Data Type

Node Structure Definition

struct Node {
    struct Node * next;  /**< pointer to the next node in a linked list*/
    struct Node * prev;  /**< pointer to the previous node in a linked list*/
};

Properties:

• Size: 2 × pointer size (typically 16 bytes on 64-bit systems)

• Alignment: Pointer-aligned

• Initialization: Via ezLinkedList_InitNode() or EZ_LINKEDLIST_INIT_NODE()

• Lifecycle: Created by user, managed through API functions

Type Safety Mechanisms

The intrusive design is type-safe through the EZ_LINKEDLIST_GET_PARENT_OF macro:

#define OFFSET(type, member) \
    ((char*)&(((type*)0)->member) - (char*)((type*)0))

#define EZ_LINKEDLIST_GET_PARENT_OF(ptr, member, type) \
    (type*)((char*)ptr - OFFSET(type, member))

This macro:

1. Calculates the byte offset of the member within the type

2. Subtracts this offset from the node pointer to get the parent structure

3. Casts to the correct type

4. Provides compile-time type checking

Configuration

The linked list is conditionally compiled based on:

#if (EZ_LINKEDLIST == 1U)
// Linked list code is compiled
#endif

Enable linked list support in the target configuration header: ez_target_config.h