28 #include "utilities/debug.hpp"

    29 

    30 template <typename T>

    31 inline ZListNode<T>::ZListNode(ZListNode* next, ZListNode* prev) :

    32     _next(next),

    33     _prev(prev) {}

    34 

    35 template <typename T>

    36 inline void ZListNode<T>::set_unused() {

    37   _next = NULL;

    38   _prev = NULL;

    39 }

    40 

    41 template <typename T>

    42 inline ZListNode<T>::ZListNode() {

    43   set_unused();

    44 }

    45 

    46 template <typename T>

    47 inline ZListNode<T>::~ZListNode() {

    48   set_unused();

    49 }

    50 

    51 template <typename T>

    52 inline bool ZListNode<T>::is_unused() const {

    53   return _next == NULL && _prev == NULL;

    54 }

    55 

    56 template <typename T>

    57 inline void ZList<T>::verify() const {

    58   assert(_head._next->_prev == &_head, "List corrupt");

    59   assert(_head._prev->_next == &_head, "List corrupt");

    60 }

    61 

    62 template <typename T>

    63 inline void ZList<T>::insert(ZListNode<T>* before, ZListNode<T>* node) {

    64   verify();

    65 

    66   assert(node->is_unused(), "Already in a list");

    67   node->_prev = before;

    68   node->_next = before->_next;

    69   before->_next = node;

    70   node->_next->_prev = node;

    71 

    72   _size++;

    73 }

    74 

    75 template <typename T>

    76 inline ZListNode<T>* ZList<T>::cast_to_inner(T* elem) const {

    77   return &elem->_node;

    78 }

    79 

    80 template <typename T>

    81 inline T* ZList<T>::cast_to_outer(ZListNode<T>* node) const {

    82   return (T*)((uintptr_t)node - offset_of(T, _node));

    83 }

    84 

    85 template <typename T>

    86 inline ZList<T>::ZList() :

    87     _head(&_head, &_head),

    88     _size(0) {

    89   verify();

    90 }

    91 

    92 template <typename T>

    93 inline size_t ZList<T>::size() const {

    94   verify();

    95   return _size;

    96 }

    97 

    98 template <typename T>

    99 inline bool ZList<T>::is_empty() const {

   100   return _size == 0;

   101 }

   102 

   103 template <typename T>

   104 inline T* ZList<T>::first() const {

   105   return is_empty() ? NULL : cast_to_outer(_head._next);

   106 }

   107 

   108 template <typename T>

   109 inline T* ZList<T>::last() const {

   110   return is_empty() ? NULL : cast_to_outer(_head._prev);

   111 }

   112 

   113 template <typename T>

   114 inline T* ZList<T>::next(T* elem) const {

   115   verify();

   116   ZListNode<T>* next = cast_to_inner(elem)->_next;

   117   return (next == &_head) ? NULL : cast_to_outer(next);

   118 }

   119 

   120 template <typename T>

   121 inline T* ZList<T>::prev(T* elem) const {

   122   verify();

   123   ZListNode<T>* prev = cast_to_inner(elem)->_prev;

   124   return (prev == &_head) ? NULL : cast_to_outer(prev);

   125 }

   126 

   127 template <typename T>

   128 inline void ZList<T>::insert_first(T* elem) {

   129   insert(&_head, cast_to_inner(elem));

   130 }

   131 

   132 template <typename T>

   133 inline void ZList<T>::insert_last(T* elem) {

   134   insert(_head._prev, cast_to_inner(elem));

   135 }

   136 

   137 template <typename T>

   138 inline void ZList<T>::insert_before(T* before, T* elem) {

   139   insert(cast_to_inner(before)->_prev, cast_to_inner(elem));

   140 }

   141 

   142 template <typename T>

   143 inline void ZList<T>::insert_after(T* after, T* elem) {

   144   insert(cast_to_inner(after), cast_to_inner(elem));

   145 }

   146 

   147 template <typename T>

   148 inline void ZList<T>::remove(T* elem) {

   149   verify();

   150 

   151   ZListNode<T>* const node = cast_to_inner(elem);

   152   assert(!node->is_unused(), "Not in a list");

   153 

   154   ZListNode<T>* const next = node->_next;

   155   ZListNode<T>* const prev = node->_prev;

   156   assert(next->_prev == node, "List corrupt");

   157   assert(prev->_next == node, "List corrupt");

   158 

   159   prev->_next = next;

   160   next->_prev = prev;

   161   node->set_unused();

   162 

   163   _size--;

   164 }

   165 

   166 template <typename T>

   167 inline T* ZList<T>::remove_first() {

   168   T* elem = first();

   169   if (elem != NULL) {

   170     remove(elem);

   171   }

   172 

   173   return elem;

   174 }

   175 

   176 template <typename T>

   177 inline T* ZList<T>::remove_last() {

   178   T* elem = last();

   179   if (elem != NULL) {

   180     remove(elem);

   181   }

   182 

   183   return elem;

   184 }

   185 

   186 template <typename T>

   187 inline void ZList<T>::transfer(ZList<T>* list) {

   188   verify();

   189 

   190   if (!list->is_empty()) {

   191     list->_head._next->_prev = _head._prev;

   192     list->_head._prev->_next = _head._prev->_next;

   193 

   194     _head._prev->_next = list->_head._next;

   195     _head._prev = list->_head._prev;

   196 

   197     list->_head._next = &list->_head;

   198     list->_head._prev = &list->_head;

   199 

   200     _size += list->_size;

   201     list->_size = 0;

   202 

   203     list->verify();

   204     verify();

   205   }

   206 }

   225 template <typename T>

   226 inline ZListIterator<T>::ZListIterator(const ZList<T>* list) :

   227     ZListIteratorImpl<T, ZLIST_FORWARD>(list) {}

   228 

   229 template <typename T>

   230 inline ZListReverseIterator<T>::ZListReverseIterator(const ZList<T>* list) :

   231     ZListIteratorImpl<T, ZLIST_REVERSE>(list) {}

   232