Intrusive List

An intrusive list embeds the link pointers (next, prev) directly into the data objects that are linked, instead of allocating separate container nodes around them. uC++ uses intrusive lists everywhere internally: every uBaseTask and uCondition node has built-in list fields so they can be enqueued onto run queues, entry queues, and condition queues without a malloc.

Why intrusive instead of std::list<T*>?

Because the scheduler runs thousands of enqueue/dequeue operations per second, and a non-intrusive list allocates a wrapper node every insert. Intrusive lists are zero-allocation: the task is the node. They also let an object sit on exactly one list at a time without the wrapper needing to know the object’s type.

Sketch

struct Node {
    Node *next, *prev;              // intrusive links
    // ... payload fields
};
class List {
    Node *head, *tail;
public:
    void push_back( Node &n ) { /* splice n into tail */ }
    Node *pop_front() { /* unlink head */ }
};

Compare to std::list<Node> which allocates a separate _List_node<Node> wrapper per element.

In uC++ monitor internals

• Entry queue: intrusive FIFO of uBaseTasks waiting on mutex members.
• Condition queue: intrusive FIFO on each uCondition.
• Acceptor/signalled stack (A/S stack): intrusive LIFO used to track who resumes next when the current mutex member returns.

Trade-offs

• Object can be on at most one list at a time (or needs multiple next/prev sets).
• Tight coupling: list fields pollute the domain type.
• Wins on allocator pressure, cache locality, and constant-time splice.

Related

• Monitor
• uCondLock
• Internal Scheduling