123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154 |
- #ifndef DINIT_LL_INCLUDED
- #define DINIT_LL_INCLUDED 1
- // Simple single- and doubly-linked list implementation, where the contained element includes the
- // list node. This allows a single item to be a member of several different kinds of list, without
- // requiring dynamic allocation of nodes for the different lists.
- //
- // To accomplish this without abstraction penalty, the function to retrieve the list node from the
- // element is specified as the second template parameter.
- // Doubly-linked list node:
- template <typename T>
- struct lld_node
- {
- T * next = nullptr;
- T * prev = nullptr;
- };
- // Singly-linked list node:
- template <typename T>
- struct lls_node
- {
- T * next = nullptr;
- };
- // Doubly-linked list implementation. The list is circular, so 'first->prev' yields the tail of
- // the list, though we still need to special-case the empty list (where first == nullptr).
- // next/prev pointers in a node are set to nullptr when the node is not linked into a list
- // (and are never equal to nullptr when the node is linked into a list).
- template <typename T, lld_node<T> &(*E)(T *)>
- class dlist
- {
- T * first;
- // E extractor;
- public:
- dlist() noexcept : first(nullptr) { }
- bool is_queued(T *e) noexcept
- {
- auto &node = E(e);
- return node.next != nullptr;
- }
- void append(T *e) noexcept
- {
- auto &node = E(e);
- if (first == nullptr) {
- first = e;
- node.next = e;
- node.prev = e;
- }
- else {
- node.next = first;
- node.prev = E(first).prev;
- E(E(first).prev).next = e;
- E(first).prev = e;
- }
- }
- T * tail() noexcept
- {
- if (first == nullptr) {
- return nullptr;
- }
- else {
- return E(first).prev;
- }
- }
- bool is_empty() noexcept
- {
- return first == nullptr;
- }
- T * pop_front() noexcept
- {
- auto r = first;
- auto &first_node = E(first);
- if (first_node.next == first) {
- // Only one node in the queue:
- first_node.next = nullptr;
- first_node.prev = nullptr;
- first = nullptr;
- }
- else {
- // Unlink first node:
- auto &node = E(first_node.next);
- node.prev = first_node.prev;
- E(node.prev).next = first_node.next;
- first = first_node.next;
- // Return original first node:
- first_node.next = nullptr;
- first_node.prev = nullptr;
- }
- return r;
- }
- void unlink(T *record) noexcept
- {
- auto &node = E(record);
- if (first == record) {
- first = node.next;
- if (first == record) {
- // unlinking the only node in the list:
- first = nullptr;
- }
- }
- E(node.next).prev = node.prev;
- E(node.prev).next = node.next;
- node.next = nullptr;
- node.prev = nullptr;
- }
- };
- // Singly-linked list implementation.
- template <typename T, lls_node<T> &(*E)(T *)>
- class slist
- {
- T * first;
- public:
- slist() noexcept : first(nullptr) { }
- bool is_queued(T *e) noexcept
- {
- auto &node = E(e);
- return node.next != nullptr || first == e;
- }
- void insert(T *e) noexcept
- {
- auto &node = E(e);
- node.next = first;
- first = e;
- }
- bool is_empty() noexcept
- {
- return first == nullptr;
- }
- T * pop_front() noexcept
- {
- T * r = first;
- auto &node = E(r);
- first = node.next;
- node.next = nullptr;
- return r;
- }
- };
- #endif
|