1.. _dlist_api:
2
3Double-linked List
4==================
5
6Similar to the single-linked list in many respects, Zephyr includes a
7double-linked implementation.  This provides the same algorithmic
8behavior for all the existing slist operations, but also allows for
9constant-time removal and insertion (at all points: before or after
10the head, tail or any internal node).  To do this, the list stores two
11pointers per node, and thus has somewhat higher runtime code and
12memory space needs.
13
14A :c:type:`sys_dlist_t` struct may be instantiated by the user in any
15accessible memory.  It must be initialized with :c:func:`sys_dlist_init`
16or :c:macro:`SYS_DLIST_STATIC_INIT` before use.  The :c:type:`sys_dnode_t` struct
17is expected to be provided by the user for any nodes added to the
18list (typically embedded within the struct to be tracked, as described
19above).  It must be initialized in zeroed/bss memory or with
20:c:func:`sys_dnode_init` before use.
21
22Primitive operations may retrieve the head/tail of a list and the
23next/prev pointers of a node with :c:func:`sys_dlist_peek_head`,
24:c:func:`sys_dlist_peek_tail`, :c:func:`sys_dlist_peek_next` and
25:c:func:`sys_dlist_peek_prev`.  These can all return NULL where
26appropriate (i.e. for empty lists, or nodes at the endpoints of the
27list).
28
29A dlist can be modified in constant time by removing a node with
30:c:func:`sys_dlist_remove`, by adding a node to the head or tail of a list
31with :c:func:`sys_dlist_prepend` and :c:func:`sys_dlist_append`, or by
32inserting a node before an existing node with :c:func:`sys_dlist_insert`.
33
34As for slist, each node in a dlist can be processed in a natural code
35block style using :c:macro:`SYS_DLIST_FOR_EACH_NODE`.  This macro also
36exists in a "FROM_NODE" form which allows for iterating from a known
37starting point, a "SAFE" variant that allows for removing the node
38being inspected within the code block, a "CONTAINER" style that
39provides the pointer to a containing struct instead of the raw node,
40and a "CONTAINER_SAFE" variant that provides both properties.
41
42Convenience utilities provided by dlist include
43:c:func:`sys_dlist_insert_at`, which inserts a node that linearly searches
44through a list to find the right insertion point, which is provided by
45the user as a C callback function pointer, and
46:c:func:`sys_dnode_is_linked`, which will affirmatively return whether or
47not a node is currently linked into a dlist or not (via an
48implementation that has zero overhead vs. the normal list processing).
49
50Double-linked List Internals
51----------------------------
52
53Internally, the dlist implementation is minimal: the :c:type:`sys_dlist_t`
54struct contains "head" and "tail" pointer fields, the :c:type:`sys_dnode_t`
55contains "prev" and "next" pointers, and no other data is stored.  But
56in practice the two structs are internally identical, and the list
57struct is inserted as a node into the list itself.  This allows for a
58very clean symmetry of operations:
59
60* An empty list has backpointers to itself in the list struct, which
61  can be trivially detected.
62
63* The head and tail of the list can be detected by comparing the
64  prev/next pointers of a node vs. the list struct address.
65
66* An insertion or deletion never needs to check for the special case
67  of inserting at the head or tail.  There are never any NULL pointers
68  within the list to be avoided.  Exactly the same operations are run,
69  without tests or branches, for all list modification primitives.
70
71Effectively, a dlist of N nodes can be thought of as a "ring" of "N+1"
72nodes, where one node represents the list tracking struct.
73
74.. figure:: dlist.png
75    :align: center
76    :alt: dlist example
77    :figclass: align-center
78
79    A dlist containing three elements.  Note that the list struct
80    appears as a fourth "element" in the list.
81
82.. figure:: dlist-single.png
83    :align: center
84    :alt: single-element dlist example
85    :figclass: align-center
86
87    An dlist containing just one element.
88
89.. figure:: dlist-empty.png
90    :align: center
91    :alt: dlist example
92    :figclass: align-center
93
94    An empty dlist.
95
96
97Doubly-linked List API Reference
98--------------------------------
99
100.. doxygengroup:: doubly-linked-list_apis
101