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