1 #ifndef DINIT_LL_INCLUDED
2 #define DINIT_LL_INCLUDED 1
4 // Simple single- and doubly-linked list implementation, where the contained element includes the
5 // list node. This allows a single item to be a member of several different kinds of list, without
6 // requiring dynamic allocation of nodes for the different lists.
8 // To accomplish this without abstraction penalty, the function to retrieve the list node from the
9 // element is specified as the second template parameter.
11 // Doubly-linked list node:
19 // Singly-linked list node:
26 // Doubly-linked list implementation. The list is circular, so 'first->prev' yields the tail of
27 // the list, though we still need to special-case the empty list (where first == nullptr).
28 // next/prev pointers in a node are set to nullptr when the node is not linked into a list
29 // (and are never equal to nullptr when the node is linked into a list).
30 template <typename T, lld_node<T> &(*E)(T *)>
37 dlist() noexcept : first(nullptr) { }
39 bool is_queued(T *e) noexcept
42 return node.next != nullptr;
45 void append(T *e) noexcept
48 if (first == nullptr) {
55 node.prev = E(first).prev;
56 E(E(first).prev).next = e;
63 if (first == nullptr) {
71 bool is_empty() noexcept
73 return first == nullptr;
76 T * pop_front() noexcept
79 auto &first_node = E(first);
80 if (first_node.next == first) {
81 // Only one node in the queue:
82 first_node.next = nullptr;
83 first_node.prev = nullptr;
88 auto &node = E(first_node.next);
89 node.prev = first_node.prev;
90 E(node.prev).next = first_node.next;
91 first = first_node.next;
92 // Return original first node:
93 first_node.next = nullptr;
94 first_node.prev = nullptr;
99 void unlink(T *record) noexcept
101 auto &node = E(record);
102 if (first == record) {
104 if (first == record) {
105 // unlinking the only node in the list:
109 E(node.next).prev = node.prev;
110 E(node.prev).next = node.next;
116 // Singly-linked list implementation.
117 template <typename T, lls_node<T> &(*E)(T *)>
123 slist() noexcept : first(nullptr) { }
125 bool is_queued(T *e) noexcept
128 return node.next != nullptr || first == e;
131 void insert(T *e) noexcept
138 bool is_empty() noexcept
140 return first == nullptr;
143 T * pop_front() noexcept