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
30template <typename T> class ZList;
31
32// Element in a doubly linked list
33template <typename T>
34class ZListNode {
35 friend class ZList<T>;
36
37private:
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
50public:
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// Doubly linked list
65template <typename T>
66class ZList {
67private:
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
100public:
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
210template <typename T, bool forward>
211class ZListIteratorImpl : public StackObj {
212private:
213 const ZList<T>* const _list;
214 T* _next;
215
216public:
217 ZListIteratorImpl(const 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
226template <typename T>
227class ZListIterator : public ZListIteratorImpl<T, ZLIST_FORWARD> {
228public:
229 ZListIterator(const ZList<T>* list) :
230 ZListIteratorImpl<T, ZLIST_FORWARD>(list) {}
231};
232
233template <typename T>
234class ZListReverseIterator : public ZListIteratorImpl<T, ZLIST_REVERSE> {
235public:
236 ZListReverseIterator(const ZList<T>* list) :
237 ZListIteratorImpl<T, ZLIST_REVERSE>(list) {}
238};
239
240#endif // SHARE_GC_Z_ZLIST_HPP
241