50113
|
1 |
/*
|
|
2 |
* Copyright (c) 2016, 2018, 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 |
|
|
25 |
#ifndef SHARE_VM_JFR_UTILITIES_JFRDOUBLYLINKEDLIST_HPP
|
|
26 |
#define SHARE_VM_JFR_UTILITIES_JFRDOUBLYLINKEDLIST_HPP
|
|
27 |
|
|
28 |
#include "memory/allocation.hpp"
|
|
29 |
|
|
30 |
template <typename T>
|
|
31 |
class JfrDoublyLinkedList {
|
|
32 |
private:
|
|
33 |
T* _head;
|
|
34 |
T* _tail;
|
|
35 |
size_t _count;
|
|
36 |
|
|
37 |
T** list_head() { return &_head; }
|
|
38 |
T** list_tail() { return &_tail; }
|
|
39 |
|
|
40 |
public:
|
|
41 |
typedef T Node;
|
|
42 |
JfrDoublyLinkedList() : _head(NULL), _tail(NULL), _count(0) {}
|
|
43 |
T* head() const { return _head; }
|
|
44 |
T* tail() const { return _tail; }
|
|
45 |
size_t count() const { return _count; }
|
|
46 |
T* clear(bool return_tail = false);
|
|
47 |
T* remove(T* const node);
|
|
48 |
void prepend(T* const node);
|
|
49 |
void append(T* const node);
|
|
50 |
void append_list(T* const head_node, T* const tail_node, size_t count);
|
|
51 |
debug_only(bool in_list(const T* const target_node) const;)
|
|
52 |
debug_only(bool locate(const T* start_node, const T* const target_node) const;)
|
|
53 |
};
|
|
54 |
|
|
55 |
template <typename T>
|
|
56 |
inline void JfrDoublyLinkedList<T>::prepend(T* const node) {
|
|
57 |
assert(node != NULL, "invariant");
|
|
58 |
node->set_prev(NULL);
|
|
59 |
assert(!in_list(node), "already in list error");
|
|
60 |
T** lh = list_head();
|
|
61 |
if (*lh != NULL) {
|
|
62 |
(*lh)->set_prev(node);
|
|
63 |
node->set_next(*lh);
|
|
64 |
} else {
|
|
65 |
T** lt = list_tail();
|
|
66 |
assert(*lt == NULL, "invariant");
|
|
67 |
*lt = node;
|
|
68 |
node->set_next(NULL);
|
|
69 |
assert(tail() == node, "invariant");
|
|
70 |
assert(node->next() == NULL, "invariant");
|
|
71 |
}
|
|
72 |
*lh = node;
|
|
73 |
++_count;
|
|
74 |
assert(head() == node, "head error");
|
|
75 |
assert(in_list(node), "not in list error");
|
|
76 |
assert(node->prev() == NULL, "invariant");
|
|
77 |
}
|
|
78 |
|
|
79 |
template <typename T>
|
|
80 |
void JfrDoublyLinkedList<T>::append(T* const node) {
|
|
81 |
assert(node != NULL, "invariant");
|
|
82 |
node->set_next(NULL);
|
|
83 |
assert(!in_list(node), "already in list error");
|
|
84 |
T** lt = list_tail();
|
|
85 |
if (*lt != NULL) {
|
|
86 |
// already an existing tail
|
|
87 |
node->set_prev(*lt);
|
|
88 |
(*lt)->set_next(node);
|
|
89 |
} else {
|
|
90 |
// if no tail, also update head
|
|
91 |
assert(*lt == NULL, "invariant");
|
|
92 |
T** lh = list_head();
|
|
93 |
assert(*lh == NULL, "invariant");
|
|
94 |
node->set_prev(NULL);
|
|
95 |
*lh = node;
|
|
96 |
assert(head() == node, "invariant");
|
|
97 |
}
|
|
98 |
*lt = node;
|
|
99 |
++_count;
|
|
100 |
assert(tail() == node, "invariant");
|
|
101 |
assert(in_list(node), "not in list error");
|
|
102 |
assert(node->next() == NULL, "invariant");
|
|
103 |
}
|
|
104 |
|
|
105 |
template <typename T>
|
|
106 |
T* JfrDoublyLinkedList<T>::remove(T* const node) {
|
|
107 |
assert(node != NULL, "invariant");
|
|
108 |
assert(in_list(node), "invariant");
|
|
109 |
T* const prev = (T*)node->prev();
|
|
110 |
T* const next = (T*)node->next();
|
|
111 |
if (prev == NULL) {
|
|
112 |
assert(head() == node, "head error");
|
|
113 |
if (next != NULL) {
|
|
114 |
next->set_prev(NULL);
|
|
115 |
} else {
|
|
116 |
assert(next == NULL, "invariant");
|
|
117 |
assert(tail() == node, "tail error");
|
|
118 |
T** lt = list_tail();
|
|
119 |
*lt = NULL;
|
|
120 |
assert(tail() == NULL, "invariant");
|
|
121 |
}
|
|
122 |
T** lh = list_head();
|
|
123 |
*lh = next;
|
|
124 |
assert(head() == next, "invariant");
|
|
125 |
} else {
|
|
126 |
assert(prev != NULL, "invariant");
|
|
127 |
if (next == NULL) {
|
|
128 |
assert(tail() == node, "tail error");
|
|
129 |
T** lt = list_tail();
|
|
130 |
*lt = prev;
|
|
131 |
assert(tail() == prev, "invariant");
|
|
132 |
} else {
|
|
133 |
next->set_prev(prev);
|
|
134 |
}
|
|
135 |
prev->set_next(next);
|
|
136 |
}
|
|
137 |
--_count;
|
|
138 |
assert(_count >= 0, "invariant");
|
|
139 |
assert(!in_list(node), "still in list error");
|
|
140 |
return node;
|
|
141 |
}
|
|
142 |
|
|
143 |
template <typename T>
|
|
144 |
T* JfrDoublyLinkedList<T>::clear(bool return_tail /* false */) {
|
|
145 |
T* const node = return_tail ? tail() : head();
|
|
146 |
T** l = list_head();
|
|
147 |
*l = NULL;
|
|
148 |
l = list_tail();
|
|
149 |
*l = NULL;
|
|
150 |
_count = 0;
|
|
151 |
assert(head() == NULL, "invariant");
|
|
152 |
assert(tail() == NULL, "invariant");
|
|
153 |
return node;
|
|
154 |
}
|
|
155 |
|
|
156 |
#ifdef ASSERT
|
|
157 |
template <typename T>
|
|
158 |
bool JfrDoublyLinkedList<T>::locate(const T* node, const T* const target) const {
|
|
159 |
assert(target != NULL, "invariant");
|
|
160 |
while (node != NULL) {
|
|
161 |
if (node == target) {
|
|
162 |
return true;
|
|
163 |
}
|
|
164 |
node = (T*)node->next();
|
|
165 |
}
|
|
166 |
return false;
|
|
167 |
}
|
|
168 |
|
|
169 |
template <typename T>
|
|
170 |
bool JfrDoublyLinkedList<T>::in_list(const T* const target) const {
|
|
171 |
assert(target != NULL, "invariant");
|
|
172 |
return locate(head(), target);
|
|
173 |
}
|
|
174 |
|
|
175 |
template <typename T>
|
|
176 |
inline void validate_count_param(T* node, size_t count_param) {
|
|
177 |
assert(node != NULL, "invariant");
|
|
178 |
size_t count = 0;
|
|
179 |
while (node) {
|
|
180 |
++count;
|
|
181 |
node = (T*)node->next();
|
|
182 |
}
|
|
183 |
assert(count_param == count, "invariant");
|
|
184 |
}
|
|
185 |
#endif // ASSERT
|
|
186 |
|
|
187 |
template <typename T>
|
|
188 |
void JfrDoublyLinkedList<T>::append_list(T* const head_node, T* const tail_node, size_t count) {
|
|
189 |
assert(head_node != NULL, "invariant");
|
|
190 |
assert(!in_list(head_node), "already in list error");
|
|
191 |
assert(tail_node != NULL, "invariant");
|
|
192 |
assert(!in_list(tail_node), "already in list error");
|
|
193 |
assert(tail_node->next() == NULL, "invariant");
|
|
194 |
// ensure passed in list nodes are connected
|
|
195 |
assert(locate(head_node, tail_node), "invariant");
|
|
196 |
T** lt = list_tail();
|
|
197 |
if (*lt != NULL) {
|
|
198 |
head_node->set_prev(*lt);
|
|
199 |
(*lt)->set_next(head_node);
|
|
200 |
} else {
|
|
201 |
// no head
|
|
202 |
assert(*lt == NULL, "invariant");
|
|
203 |
T** lh = list_head();
|
|
204 |
assert(*lh == NULL, "invariant");
|
|
205 |
head_node->set_prev(NULL);
|
|
206 |
*lh = head_node;
|
|
207 |
assert(head() == head_node, "invariant");
|
|
208 |
}
|
|
209 |
*lt = tail_node;
|
|
210 |
const T* node = head_node;
|
|
211 |
debug_only(validate_count_param(node, count);)
|
|
212 |
_count += count;
|
|
213 |
assert(tail() == tail_node, "invariant");
|
|
214 |
assert(in_list(tail_node), "not in list error");
|
|
215 |
assert(in_list(head_node), "not in list error");
|
|
216 |
}
|
|
217 |
|
|
218 |
#endif // SHARE_VM_JFR_UTILITIES_JFRDOUBLYLINKEDLIST_HPP
|