1 /*

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

     3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

     4  *

     5  * This code is free software; you can redistribute it and/or modify it

     6  * under the terms of the GNU General Public License version 2 only, as

     7  * published by the Free Software Foundation.

     8  *

     9  * This code is distributed in the hope that it will be useful, but WITHOUT

    10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

    11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

    12  * version 2 for more details (a copy is included in the LICENSE file that

    13  * accompanied this code).

    14  *

    15  * You should have received a copy of the GNU General Public License version

    16  * 2 along with this work; if not, write to the Free Software Foundation,

    17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

    18  *

    19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

    20  * or visit www.oracle.com if you need additional information or have any

    21  * questions.

    22  */

    23 

    24 #ifndef SHARE_GC_Z_ZLIST_HPP

    25 #define SHARE_GC_Z_ZLIST_HPP

    26 

    27 #include "memory/allocation.hpp"

    28 #include "utilities/debug.hpp"

    29 

    30 template <typename T> class ZList;

    31 

    32 // Element in a double linked list

    33 template <typename T>

    34 class ZListNode {

    35   friend class ZList<T>;

    36 

    37 private:

    38   ZListNode* _next;

    39   ZListNode* _prev;

    40 

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

    42       _next(next),

    43       _prev(prev) {}

    44 

    45   void set_unused() {

    46     _next = NULL;

    47     _prev = NULL;

    48   }

    49 

    50 public:

    51   ZListNode() {

    52     set_unused();

    53   }

    54 

    55   ~ZListNode() {

    56     set_unused();

    57   }

    58 

    59   bool is_unused() const {

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

    61   }

    62 };

    63 

    64 // Double-linked list

    65 template <typename T>

    66 class ZList {

    67 private:

    68   ZListNode<T> _head;

    69   size_t       _size;

    70 

    71   // Passing by value and assignment is not allowed

    72   ZList(const ZList<T>& list);

    73   ZList<T>& operator=(const ZList<T>& list);

    74 

    75   void verify() const {

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

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

    78   }

    79 

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

    81     verify();

    82 

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

    84     node->_prev = before;

    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   }

    99 

   100 public:

   101   ZList() :

   102       _head(&_head, &_head),

   103       _size(0) {

   104     verify();

   105   }

   106 

   107   size_t size() const {

   108     verify();

   109     return _size;

   110   }

   111 

   112   bool is_empty() const {

   113     return _size == 0;

   114   }

   115 

   116   T* first() const {

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

   118   }

   119 

   120   T* last() const {

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

   122   }

   123 

   124   T* next(T* elem) const {

   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   }

   208 };

   209 

   210 template <typename T, bool forward>

   211 class ZListIteratorImpl : public StackObj {

   212 private:

   213   ZList<T>* const _list;

   214   T*              _next;

   215 

   216 public:

   217   ZListIteratorImpl(ZList<T>* list);

   218 

   219   bool next(T** elem);

   220 };

   221 

   222 // Iterator types

   223 #define ZLIST_FORWARD        true

   224 #define ZLIST_REVERSE        false

   225 

   226 template <typename T>

   227 class ZListIterator : public ZListIteratorImpl<T, ZLIST_FORWARD> {

   228 public:

   229   ZListIterator(ZList<T>* list) :

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

   231 };

   232 

   233 template <typename T>

   234 class ZListReverseIterator : public ZListIteratorImpl<T, ZLIST_REVERSE> {

   235 public:

   236   ZListReverseIterator(ZList<T>* list) :

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

   238 };

   239 

   240 #endif // SHARE_GC_Z_ZLIST_HPP