Similar to the single-linked list in many respects, Zephyr includes a
double-linked implementation. This provides the same algorithmic
behavior for all the existing slist operations, but also allows for
constant-time removal and insertion (at all points: before or after
the head, tail or any internal node). To do this, the list stores two
pointers per node, and thus has somewhat higher runtime code and
memory space needs.
A sys_dlist_t struct may be instantiated by the user in any
accessible memory. It must be initialized with sys_dlist_init()
or SYS_DLIST_STATIC_INIT before use. The sys_dnode_t struct
is expected to be provided by the user for any nodes added to the
list (typically embedded within the struct to be tracked, as described
above). It must be initialized in zeroed/bss memory or with
sys_dnode_init() before use.
As for slist, each node in a dlist can be processed in a natural code
block style using SYS_DLIST_FOR_EACH_NODE. This macro also
exists in a “FROM_NODE” form which allows for iterating from a known
starting point, a “SAFE” variant that allows for removing the node
being inspected within the code block, a “CONTAINER” style that
provides the pointer to a containing struct instead of the raw node,
and a “CONTAINER_SAFE” variant that provides both properties.
Convenience utilities provided by dlist include
sys_dlist_insert_at(), which inserts a node that linearly searches
through a list to find the right insertion point, which is provided by
the user as a C callback function pointer, and
sys_dnode_is_linked(), which will affirmatively return whether or
not a node is currently linked into a dlist or not (via an
implementation that has zero overhead vs. the normal list processing).
Internally, the dlist implementation is minimal: the sys_dlist_t
struct contains “head” and “tail” pointer fields, the sys_dnode_t
contains “prev” and “next” pointers, and no other data is stored. But
in practice the two structs are internally identical, and the list
struct is inserted as a node into the list itself. This allows for a
very clean symmetry of operations:
An empty list has backpointers to itself in the list struct, which
can be trivially detected.
The head and tail of the list can be detected by comparing the
prev/next pointers of a node vs. the list struct address.
An insertion or deletion never needs to check for the special case
of inserting at the head or tail. There are never any NULL pointers
within the list to be avoided. Exactly the same operations are run,
without tests or branches, for all list modification primitives.
Effectively, a dlist of N nodes can be thought of as a “ring” of “N+1”
nodes, where one node represents the list tracking struct.
Insert a node in a location depending on a external condition. The cond() function checks if the node is to be inserted before the current node against which it is checked. This and other sys_dlist_*() functions are not thread safe.
list – the doubly-linked list to operate on
node – the element to insert
cond – a function that determines if the current node is the correct insert point