list.h — Doubly-Linked Circular List

Introduction

list.h provides an intrusive doubly-linked circular list, derived from the Linux kernel's include/linux/list.h. Instead of storing payloads inside list nodes, the caller embeds an xList node inside their own struct and uses xContainerOf to recover the enclosing struct. This design avoids dynamic allocation for the list itself and works with any element type without generic macros or function pointers.

Design Philosophy

1. Intrusive Design — The list node (xList) is embedded inside the user's struct rather than wrapping it. This eliminates per-element heap allocation and makes the list usable for any type without templates or void * casts.

2. Circular Sentinel — The list head is itself an xList node whose next and prev point back to itself when empty. This eliminates special-case branching for head/tail operations — every insertion and deletion follows the same pointer manipulation.

3. Inline Implementation — All functions are declared XCAPI_INLINE, so the entire list implementation lives in the header with no separate .c file. This gives the compiler full visibility for inlining and constant propagation, yielding zero-overhead list operations.

4. Poison Pointers — After removal, a node's next and prev are overwritten with sentinel values (0xDEAD / 0xBEEF). Accessing a removed node's links will trigger an obvious crash, catching use-after-remove bugs early.

5. Safe Iteration Macros — xListForEachSafe and xListForEachEntrySafe stash the next pointer before the current node is visited, allowing deletion during iteration without invalidating the loop.

Architecture

graph TD
    INIT["xListInit(head)"] --> CIRCULAR["head ⇄ head<br/>(empty circle)"]
    ADD["xListAdd(prev, node)"] --> INSERT["Insert after prev"]
    ADDH["xListAddHead(head, node)"] --> INSERTH["Insert at head<br/>(= xListAdd(head, node))"]
    ADDT["xListAddTail(head, node)"] --> INSERTT["Insert at tail<br/>(= xListAdd(head→prev, node))"]
    ADDB["xListAddBefore(next, node)"] --> INSERTB["Insert before next"]
    DEL["xListDel(node)"] --> REMOVE["Unlink + poison"]
    EMPTY["xListEmpty(head)"] --> CHECK["head→next == head?"]

    CIRCULAR --> ADD
    CIRCULAR --> ADDH
    CIRCULAR --> ADDT
    CIRCULAR --> ADDB
    ADD --> DEL
    ADDH --> DEL
    ADDT --> DEL
    ADDB --> DEL

    style INIT fill:#4a90d9,color:#fff
    style ADD fill:#50b86c,color:#fff
    style ADDH fill:#50b86c,color:#fff
    style ADDT fill:#50b86c,color:#fff
    style ADDB fill:#50b86c,color:#fff
    style DEL fill:#e74c3c,color:#fff
    style EMPTY fill:#f5a623,color:#fff

Implementation Details

Data Structure

typedef struct xList {
  struct xList *next;
  struct xList *prev;
} xList;

Circular Layout

Empty list:

        ┌──────────────┐
        │    head       │
        │ next ──┐      │
        │ prev ──┼──┐   │
        │        │  │   │
        └────────┼──┼───┘
                 ▼  ▼
               (self)

List with three nodes:

  head ⇄ A ⇄ B ⇄ C ⇄ head
       ┌─►──────────────────┐
       │                    ▼
  head ──► A ──► B ──► C ──┘
    ▲      ◄──   ◄──   ◄── │
    └──────────────────────┘

Operations and Complexity

Pointer Manipulation

Inserting node after prev:

Before:  prev ⇄ next
After:   prev ⇄ node ⇄ next

  next->prev = node;
  node->next = next;
  node->prev = prev;
  prev->next = node;

Removing node:

Before:  prev ⇄ node ⇄ next
After:   prev ⇄ next   (node: 0xDEAD / 0xBEEF)

  next->prev = prev;
  prev->next = next;
  node->next = 0xDEAD;
  node->prev = 0xBEEF;

API Reference

Types

Functions

Macros

Usage Examples

Basic List Operations

#include <stdio.h>
#include <xbase/list.h>

struct Task {
  xList list;
  int   id;
};

int main(void) {
  xList head;
  xListInit(&head);

  struct Task t1 = { .id = 1 };
  struct Task t2 = { .id = 2 };
  struct Task t3 = { .id = 3 };

  /* Append to the end */
  xListAddTail(&head, &t1.list);
  xListAddTail(&head, &t2.list);
  xListAddTail(&head, &t3.list);

  /* Iterate: 1, 2, 3 */
  struct Task *pos;
  xListForEachEntry(pos, &head, list) {
    printf("task id = %d\n", pos->id);
  }

  /* Remove t2 */
  xListDel(&t2.list);

  /* Iterate: 1, 3 */
  xListForEachEntry(pos, &head, list) {
    printf("task id = %d\n", pos->id);
  }

  return 0;
}

Safe Deletion During Iteration

#include <xbase/list.h>

struct Node {
  xList list;
  int   value;
};

void remove_all(xList *head) {
  struct Node *pos, *tmp;
  xListForEachEntrySafe(pos, tmp, head, list) {
    xListDel(&pos->list);
    /* pos is now unlinked; safe to free if dynamically allocated */
  }
}

Stack (LIFO) with xListAddHead

#include <xbase/list.h>

struct Item {
  xList list;
  int   data;
};

void stack_push(xList *stack, struct Item *item) {
  xListAddHead(stack, &item->list);  /* insert at head = top of stack */
}

struct Item *stack_pop(xList *stack) {
  if (xListEmpty(stack)) return NULL;
  xList *first = stack->next;
  xListDel(first);
  return xContainerOf(first, struct Item, list);
}

Queue (FIFO) with xListAddTail

#include <xbase/list.h>

struct Entry {
  xList list;
  int   data;
};

void queue_push(xList *queue, struct Entry *entry) {
  xListAddTail(queue, &entry->list);  /* insert at tail */
}

struct Entry *queue_pop(xList *queue) {
  if (xListEmpty(queue)) return NULL;
  xList *first = queue->next;
  xListDel(first);
  return xContainerOf(first, struct Entry, list);
}

Use Cases

1. Timer Entry Queue — timer.h links timer entries via an embedded xList node for O(1) insertion and removal of timer callbacks.

2. Connection List — Async socket implementations can chain active connections in a list, enabling O(1) connect/disconnect without external allocation.

3. Task Scheduling — A thread pool can maintain per-worker task lists using xListAddHead/xListAddTail/xListDel, with xListForEachEntrySafe for graceful shutdown that drains and cancels pending tasks.

4. Event Callback Chains — Multiple listeners on the same event can be linked in a list, each embedding an xList node in their handler struct.

Best Practices

• Always use the safe variants when deleting during iteration. xListForEach / xListForEachEntry will crash if the current node is deleted mid-loop. Use xListForEachSafe / xListForEachEntrySafe instead.
• Initialize before use. An uninitialized xList has indeterminate pointers. Always call xListInit() before any other operation.
• Don't re-add a node without removing it first. Adding a node that is already in a list will corrupt both the old and new lists. Call xListDel() before re-inserting.
• Use xListAddTail(head, ...) for tail insertion. In a circular list, xListAddTail inserts before the head sentinel, appending to the tail in O(1). Similarly, use xListAddHead(head, ...) for head insertion.
• Check poison after removal for debugging. After xListDel(), node->next == 0xDEAD signals a use-after-remove bug if you accidentally access the node's links.

Comparison with Other Libraries

Key Differentiator: xbase's list follows the same proven intrusive design as the Linux kernel's list.h, adapted for user-space C99 with xContainerOf (equivalent to kernel's container_of). The inline implementation and poison pointers provide zero-overhead operations and early detection of use-after-remove bugs.