2  * Copyright (c) 2015, 2017, Oracle and/or its affiliates. All rights reserved.

     2  * Copyright (c) 2015, 2019, Oracle and/or its affiliates. All rights reserved.

    41   ZListNode(ZListNode* next, ZListNode* prev) :

    40   ZListNode(ZListNode* next, ZListNode* prev);

    42       _next(next),

    43       _prev(prev) {}

    45   void set_unused() {

    42   void set_unused();

    46     _next = NULL;

    47     _prev = NULL;

    48   }

    51   ZListNode() {

    45   ZListNode();

    52     set_unused();

    46   ~ZListNode();

    53   }

    55   ~ZListNode() {

    48   bool is_unused() const;

    56     set_unused();

    57   }

    58 

    59   bool is_unused() const {

    60     return _next == NULL && _prev == NULL;

    61   }

    75   void verify() const {

    62   void verify() const;

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

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

    78   }

    80   void insert(ZListNode<T>* before, ZListNode<T>* node) {

    64   void insert(ZListNode<T>* before, ZListNode<T>* node);

    81     verify();

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

    66   ZListNode<T>* cast_to_inner(T* elem) const;

    84     node->_prev = before;

    67   T* cast_to_outer(ZListNode<T>* node) const;

    85     node->_next = before->_next;

    86     before->_next = node;

    87     node->_next->_prev = node;

    88 

    89     _size++;

    90   }

    91 

    92   ZListNode<T>* cast_to_inner(T* elem) const {

    93     return &elem->_node;

    94   }

    95 

    96   T* cast_to_outer(ZListNode<T>* node) const {

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

    98   }

   101   ZList() :

    70   ZList();

   102       _head(&_head, &_head),

   103       _size(0) {

   104     verify();

   105   }

   107   size_t size() const {

    72   size_t size() const;

   108     verify();

    73   bool is_empty() const;

   109     return _size;

   110   }

   112   bool is_empty() const {

    75   T* first() const;

   113     return _size == 0;

    76   T* last() const;

   114   }

    77   T* next(T* elem) const;

    78   T* prev(T* elem) const;

   116   T* first() const {

    80   void insert_first(T* elem);

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

    81   void insert_last(T* elem);

   118   }

    82   void insert_before(T* before, T* elem);

    83   void insert_after(T* after, T* elem);

   120   T* last() const {

    85   void remove(T* elem);

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

    86   T* remove_first();

   122   }

    87   T* remove_last();

   124   T* next(T* elem) const {

    89   void transfer(ZList<T>* list);

   125     verify();

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

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

   128   }

   129 

   130   T* prev(T* elem) const {

   131     verify();

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

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

   134   }

   135 

   136   void insert_first(T* elem) {

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

   138   }

   139 

   140   void insert_last(T* elem) {

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

   142   }

   143 

   144   void insert_before(T* before, T* elem) {

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

   146   }

   147 

   148   void insert_after(T* after, T* elem) {

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

   150   }

   151 

   152   void remove(T* elem) {

   153     verify();

   154 

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

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

   157 

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

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

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

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

   162 

   163     prev->_next = next;

   164     next->_prev = prev;

   165     node->set_unused();

   166 

   167     _size--;

   168   }

   169 

   170   T* remove_first() {

   171     T* elem = first();

   172     if (elem != NULL) {

   173       remove(elem);

   174     }

   175 

   176     return elem;

   177   }

   178 

   179   T* remove_last() {

   180     T* elem = last();

   181     if (elem != NULL) {

   182       remove(elem);

   183     }

   184 

   185     return elem;

   186   }

   187 

   188   void transfer(ZList<T>* list) {

   189     verify();

   190 

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

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

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

   194 

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

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

   197 

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

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

   200 

   201       _size += list->_size;

   202       list->_size = 0;

   203 

   204       list->verify();

   205       verify();

   206     }

   207   }

   229   ZListIterator(const ZList<T>* list) :

   111   ZListIterator(const ZList<T>* list);

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

   236   ZListReverseIterator(const ZList<T>* list) :

   117   ZListReverseIterator(const ZList<T>* list);

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