src/includes/dinit-ll.h

   1 #ifndef DINIT_LL_INCLUDED
   2 #define DINIT_LL_INCLUDED 1
   3
   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.
   7 //
   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.
  10
  11 // Doubly-linked list node:
  12 template <typename T>
  13 struct lld_node
  14 {
  15     T * next = nullptr;
  16     T * prev = nullptr;
  17 };
  18
  19 // Singly-linked list node:
  20 template <typename T>
  21 struct lls_node
  22 {
  23     T * next = nullptr;
  24 };
  25
  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 *)>
  31 class dlist
  32 {
  33     T * first;
  34     // E extractor;
  35
  36     public:
  37     dlist() noexcept : first(nullptr) { }
  38
  39     bool is_queued(T *e) noexcept
  40     {
  41         auto &node = E(e);
  42         return node.next != nullptr;
  43     }
  44
  45     void append(T *e) noexcept
  46     {
  47         auto &node = E(e);
  48         if (first == nullptr) {
  49             first = e;
  50             node.next = e;
  51             node.prev = e;
  52         }
  53         else {
  54             node.next = first;
  55             node.prev = E(first).prev;
  56             E(E(first).prev).next = e;
  57             E(first).prev = e;
  58         }
  59     }
  60
  61     T * tail() noexcept
  62     {
  63         if (first == nullptr) {
  64             return nullptr;
  65         }
  66         else {
  67             return E(first).prev;
  68         }
  69     }
  70
  71     bool is_empty() noexcept
  72     {
  73         return first == nullptr;
  74     }
  75
  76     T * pop_front() noexcept
  77     {
  78         auto r = first;
  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;
  84             first = nullptr;
  85         }
  86         else {
  87             // Unlink first node:
  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;
  95         }
  96         return r;
  97     }
  98
  99     void unlink(T *record) noexcept
 100     {
 101         auto &node = E(record);
 102         if (first == record) {
 103             first = node.next;
 104             if (first == record) {
 105                 // unlinking the only node in the list:
 106                 first = nullptr;
 107             }
 108         }
 109         E(node.next).prev = node.prev;
 110         E(node.prev).next = node.next;
 111         node.next = nullptr;
 112         node.prev = nullptr;
 113     }
 114 };
 115
 116 // Singly-linked list implementation.
 117 template <typename T, lls_node<T> &(*E)(T *)>
 118 class slist
 119 {
 120     T * first;
 121
 122     public:
 123     slist() noexcept : first(nullptr) { }
 124
 125     bool is_queued(T *e) noexcept
 126     {
 127         auto &node = E(e);
 128         return node.next != nullptr || first == e;
 129     }
 130
 131     void insert(T *e) noexcept
 132     {
 133         auto &node = E(e);
 134         node.next = first;
 135         first = e;
 136     }
 137
 138     bool is_empty() noexcept
 139     {
 140         return first == nullptr;
 141     }
 142
 143     T * pop_front() noexcept
 144     {
 145         T * r = first;
 146         auto &node = E(r);
 147         first = node.next;
 148         node.next = nullptr;
 149         return r;
 150     }
 151 };
 152
 153
 154 #endif