author | mgronlun |
Wed, 30 Oct 2019 19:43:52 +0100 | |
changeset 58863 | c16ac7a2eba4 |
parent 53244 | 9807daeb47c4 |
permissions | -rw-r--r-- |
50113 | 1 |
/* |
53244
9807daeb47c4
8216167: Update include guards to reflect correct directories
coleenp
parents:
50113
diff
changeset
|
2 |
* Copyright (c) 2016, 2019, Oracle and/or its affiliates. All rights reserved. |
50113 | 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 |
||
53244
9807daeb47c4
8216167: Update include guards to reflect correct directories
coleenp
parents:
50113
diff
changeset
|
25 |
#ifndef SHARE_JFR_UTILITIES_JFRDOUBLYLINKEDLIST_HPP |
9807daeb47c4
8216167: Update include guards to reflect correct directories
coleenp
parents:
50113
diff
changeset
|
26 |
#define SHARE_JFR_UTILITIES_JFRDOUBLYLINKEDLIST_HPP |
50113 | 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); |
|
58863 | 51 |
bool in_list(const T* const target_node) const; |
52 |
bool locate(const T* start_node, const T* const target_node) const; |
|
50113 | 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 |
template <typename T> |
|
157 |
bool JfrDoublyLinkedList<T>::locate(const T* node, const T* const target) const { |
|
158 |
assert(target != NULL, "invariant"); |
|
159 |
while (node != NULL) { |
|
160 |
if (node == target) { |
|
161 |
return true; |
|
162 |
} |
|
163 |
node = (T*)node->next(); |
|
164 |
} |
|
165 |
return false; |
|
166 |
} |
|
167 |
||
168 |
template <typename T> |
|
169 |
bool JfrDoublyLinkedList<T>::in_list(const T* const target) const { |
|
170 |
assert(target != NULL, "invariant"); |
|
171 |
return locate(head(), target); |
|
172 |
} |
|
173 |
||
174 |
template <typename T> |
|
175 |
inline void validate_count_param(T* node, size_t count_param) { |
|
176 |
assert(node != NULL, "invariant"); |
|
177 |
size_t count = 0; |
|
178 |
while (node) { |
|
179 |
++count; |
|
180 |
node = (T*)node->next(); |
|
181 |
} |
|
182 |
assert(count_param == count, "invariant"); |
|
183 |
} |
|
184 |
||
185 |
template <typename T> |
|
186 |
void JfrDoublyLinkedList<T>::append_list(T* const head_node, T* const tail_node, size_t count) { |
|
187 |
assert(head_node != NULL, "invariant"); |
|
188 |
assert(!in_list(head_node), "already in list error"); |
|
189 |
assert(tail_node != NULL, "invariant"); |
|
190 |
assert(!in_list(tail_node), "already in list error"); |
|
191 |
assert(tail_node->next() == NULL, "invariant"); |
|
192 |
// ensure passed in list nodes are connected |
|
193 |
assert(locate(head_node, tail_node), "invariant"); |
|
194 |
T** lt = list_tail(); |
|
195 |
if (*lt != NULL) { |
|
196 |
head_node->set_prev(*lt); |
|
197 |
(*lt)->set_next(head_node); |
|
198 |
} else { |
|
199 |
// no head |
|
200 |
assert(*lt == NULL, "invariant"); |
|
201 |
T** lh = list_head(); |
|
202 |
assert(*lh == NULL, "invariant"); |
|
203 |
head_node->set_prev(NULL); |
|
204 |
*lh = head_node; |
|
205 |
assert(head() == head_node, "invariant"); |
|
206 |
} |
|
207 |
*lt = tail_node; |
|
208 |
const T* node = head_node; |
|
209 |
debug_only(validate_count_param(node, count);) |
|
210 |
_count += count; |
|
211 |
assert(tail() == tail_node, "invariant"); |
|
212 |
assert(in_list(tail_node), "not in list error"); |
|
213 |
assert(in_list(head_node), "not in list error"); |
|
214 |
} |
|
215 |
||
53244
9807daeb47c4
8216167: Update include guards to reflect correct directories
coleenp
parents:
50113
diff
changeset
|
216 |
#endif // SHARE_JFR_UTILITIES_JFRDOUBLYLINKEDLIST_HPP |