|
20360
|
1 /*
|
|
|
2 * Copyright (c) 2014, 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_UTILITIES_LINKED_LIST_HPP
|
|
|
26 #define SHARE_VM_UTILITIES_LINKED_LIST_HPP
|
|
|
27
|
|
|
28 #include "memory/allocation.hpp"
|
|
|
29
|
|
|
30 /*
|
|
|
31 * The implementation of a generic linked list, which uses various
|
|
|
32 * backing storages, such as C heap, arena and resource, etc.
|
|
|
33 */
|
|
|
34
|
|
|
35
|
|
|
36 // An entry in a linked list. It should use the same backing storage
|
|
|
37 // as the linked list that contains this entry.
|
|
|
38 template <class E> class LinkedListNode : public ResourceObj {
|
|
|
39 private:
|
|
|
40 E _data; // embedded content
|
|
|
41 LinkedListNode<E>* _next; // next entry
|
|
|
42
|
|
|
43 protected:
|
|
|
44 LinkedListNode() : _next(NULL) { }
|
|
|
45
|
|
|
46 public:
|
|
|
47 LinkedListNode(const E& e): _data(e), _next(NULL) { }
|
|
|
48
|
|
|
49 inline void set_next(LinkedListNode<E>* node) { _next = node; }
|
|
|
50 inline LinkedListNode<E> * next() const { return _next; }
|
|
|
51
|
|
|
52 E* data() { return &_data; }
|
|
|
53 const E* peek() const { return &_data; }
|
|
|
54 };
|
|
|
55
|
|
|
56 // A linked list interface. It does not specify
|
|
|
57 // any storage type it uses, so all methods involving
|
|
|
58 // memory allocation or deallocation are pure virtual
|
|
|
59 template <class E> class LinkedList : public ResourceObj {
|
|
|
60 protected:
|
|
|
61 LinkedListNode<E>* _head;
|
|
|
62
|
|
|
63 public:
|
|
|
64 LinkedList() : _head(NULL) { }
|
|
|
65
|
|
|
66 inline void set_head(LinkedListNode<E>* h) { _head = h; }
|
|
|
67 inline LinkedListNode<E>* head() const { return _head; }
|
|
|
68 inline bool is_empty() const { return head() == NULL; }
|
|
|
69
|
|
|
70 inline size_t size() const {
|
|
|
71 LinkedListNode<E>* p;
|
|
|
72 size_t count = 0;
|
|
|
73 for (p = head(); p != NULL; count++, p = p->next());
|
|
|
74 return count;
|
|
|
75 }
|
|
|
76
|
|
|
77 // Move all entries from specified linked list to this one
|
|
|
78 virtual void move(LinkedList<E>* list) = 0;
|
|
|
79
|
|
|
80 // Add an entry to this linked list
|
|
|
81 virtual LinkedListNode<E>* add(const E& e) = 0;
|
|
|
82 // Add all entries from specified linked list to this one,
|
|
|
83 virtual void add(LinkedListNode<E>* node) = 0;
|
|
|
84
|
|
|
85 // Add a linked list to this linked list
|
|
|
86 virtual bool add(const LinkedList<E>* list) = 0;
|
|
|
87
|
|
|
88 // Search entry in the linked list
|
|
|
89 virtual LinkedListNode<E>* find_node(const E& e) = 0;
|
|
|
90 virtual E* find(const E& e) = 0;
|
|
|
91
|
|
|
92 // Insert entry to the linked list
|
|
|
93 virtual LinkedListNode<E>* insert_before(const E& e, LinkedListNode<E>* ref) = 0;
|
|
|
94 virtual LinkedListNode<E>* insert_after (const E& e, LinkedListNode<E>* ref) = 0;
|
|
|
95
|
|
|
96 // Remove entry from the linked list
|
|
|
97 virtual bool remove(const E& e) = 0;
|
|
|
98 virtual bool remove(LinkedListNode<E>* node) = 0;
|
|
|
99 virtual bool remove_before(LinkedListNode<E>* ref) = 0;
|
|
|
100 virtual bool remove_after(LinkedListNode<E>* ref) = 0;
|
|
|
101
|
|
|
102 LinkedListNode<E>* unlink_head() {
|
|
|
103 LinkedListNode<E>* h = this->head();
|
|
|
104 if (h != NULL) {
|
|
|
105 this->set_head(h->next());
|
|
|
106 }
|
|
|
107 return h;
|
|
|
108 }
|
|
|
109
|
|
|
110 DEBUG_ONLY(virtual ResourceObj::allocation_type storage_type() = 0;)
|
|
|
111 };
|
|
|
112
|
|
|
113 // A linked list implementation.
|
|
|
114 // The linked list can be allocated in various type of memory: C heap, arena and resource area, etc.
|
|
|
115 template <class E, ResourceObj::allocation_type T = ResourceObj::C_HEAP,
|
|
|
116 MEMFLAGS F = mtNMT, AllocFailType alloc_failmode = AllocFailStrategy::RETURN_NULL>
|
|
|
117 class LinkedListImpl : public LinkedList<E> {
|
|
|
118 protected:
|
|
|
119 Arena* _arena;
|
|
|
120 public:
|
|
|
121 LinkedListImpl() : _arena(NULL) { }
|
|
|
122 LinkedListImpl(Arena* a) : _arena(a) { }
|
|
|
123
|
|
|
124 virtual ~LinkedListImpl() {
|
|
|
125 clear();
|
|
|
126 }
|
|
|
127
|
|
|
128 virtual void clear() {
|
|
|
129 LinkedListNode<E>* p = this->head();
|
|
|
130 this->set_head(NULL);
|
|
|
131 while (p != NULL) {
|
|
|
132 LinkedListNode<E>* to_delete = p;
|
|
|
133 p = p->next();
|
|
|
134 delete_node(to_delete);
|
|
|
135 }
|
|
|
136 }
|
|
|
137
|
|
|
138 // Add an entry to the linked list
|
|
|
139 virtual LinkedListNode<E>* add(const E& e) {
|
|
|
140 LinkedListNode<E>* node = this->new_node(e);
|
|
|
141 if (node != NULL) {
|
|
|
142 this->add(node);
|
|
|
143 }
|
|
|
144
|
|
|
145 return node;
|
|
|
146 }
|
|
|
147
|
|
|
148 virtual void add(LinkedListNode<E>* node) {
|
|
|
149 assert(node != NULL, "NULL pointer");
|
|
|
150 node->set_next(this->head());
|
|
|
151 this->set_head(node);
|
|
|
152 }
|
|
|
153
|
|
|
154 // Move a linked list to this linked list, both have to be allocated on the same
|
|
|
155 // storage type.
|
|
|
156 virtual void move(LinkedList<E>* list) {
|
|
|
157 assert(list->storage_type() == this->storage_type(), "Different storage type");
|
|
|
158 LinkedListNode<E>* node = this->head();
|
|
|
159 while (node != NULL && node->next() != NULL) {
|
|
|
160 node = node->next();
|
|
|
161 }
|
|
|
162 if (node == NULL) {
|
|
|
163 this->set_head(list->head());
|
|
|
164 } else {
|
|
|
165 node->set_next(list->head());
|
|
|
166 }
|
|
|
167 // All entries are moved
|
|
|
168 list->set_head(NULL);
|
|
|
169 }
|
|
|
170
|
|
|
171 virtual bool add(const LinkedList<E>* list) {
|
|
|
172 LinkedListNode<E>* node = list->head();
|
|
|
173 while (node != NULL) {
|
|
|
174 if (this->add(*node->peek()) == NULL) {
|
|
|
175 return false;
|
|
|
176 }
|
|
|
177 node = node->next();
|
|
|
178 }
|
|
|
179 return true;
|
|
|
180 }
|
|
|
181
|
|
|
182
|
|
|
183 virtual LinkedListNode<E>* find_node(const E& e) {
|
|
|
184 LinkedListNode<E>* p = this->head();
|
|
|
185 while (p != NULL && !p->peek()->equals(e)) {
|
|
|
186 p = p->next();
|
|
|
187 }
|
|
|
188 return p;
|
|
|
189 }
|
|
|
190
|
|
|
191 E* find(const E& e) {
|
|
|
192 LinkedListNode<E>* node = find_node(e);
|
|
|
193 return (node == NULL) ? NULL : node->data();
|
|
|
194 }
|
|
|
195
|
|
|
196
|
|
|
197 // Add an entry in front of the reference entry
|
|
|
198 LinkedListNode<E>* insert_before(const E& e, LinkedListNode<E>* ref_node) {
|
|
|
199 LinkedListNode<E>* node = this->new_node(e);
|
|
|
200 if (node == NULL) return NULL;
|
|
|
201 if (ref_node == this->head()) {
|
|
|
202 node->set_next(ref_node);
|
|
|
203 this->set_head(node);
|
|
|
204 } else {
|
|
|
205 LinkedListNode<E>* p = this->head();
|
|
|
206 while (p != NULL && p->next() != ref_node) {
|
|
|
207 p = p->next();
|
|
|
208 }
|
|
|
209 assert(p != NULL, "ref_node not in the list");
|
|
|
210 node->set_next(ref_node);
|
|
|
211 p->set_next(node);
|
|
|
212 }
|
|
|
213 return node;
|
|
|
214 }
|
|
|
215
|
|
|
216 // Add an entry behind the reference entry
|
|
|
217 LinkedListNode<E>* insert_after(const E& e, LinkedListNode<E>* ref_node) {
|
|
|
218 LinkedListNode<E>* node = this->new_node(e);
|
|
|
219 if (node == NULL) return NULL;
|
|
|
220 node->set_next(ref_node->next());
|
|
|
221 ref_node->set_next(node);
|
|
|
222 return node;
|
|
|
223 }
|
|
|
224
|
|
|
225 // Remove an entry from the linked list.
|
|
|
226 // Return true if the entry is successfully removed
|
|
|
227 virtual bool remove(const E& e) {
|
|
|
228 LinkedListNode<E>* tmp = this->head();
|
|
|
229 LinkedListNode<E>* prev = NULL;
|
|
|
230
|
|
|
231 while (tmp != NULL) {
|
|
|
232 if (tmp->peek()->equals(e)) {
|
|
|
233 return remove_after(prev);
|
|
|
234 }
|
|
|
235 prev = tmp;
|
|
|
236 tmp = tmp->next();
|
|
|
237 }
|
|
|
238 return false;
|
|
|
239 }
|
|
|
240
|
|
|
241 // Remove the node after the reference entry
|
|
|
242 virtual bool remove_after(LinkedListNode<E>* prev) {
|
|
|
243 LinkedListNode<E>* to_delete;
|
|
|
244 if (prev == NULL) {
|
|
|
245 to_delete = this->unlink_head();
|
|
|
246 } else {
|
|
|
247 to_delete = prev->next();
|
|
|
248 if (to_delete != NULL) {
|
|
|
249 prev->set_next(to_delete->next());
|
|
|
250 }
|
|
|
251 }
|
|
|
252
|
|
|
253 if (to_delete != NULL) {
|
|
|
254 delete_node(to_delete);
|
|
|
255 return true;
|
|
|
256 }
|
|
|
257 return false;
|
|
|
258 }
|
|
|
259
|
|
|
260 virtual bool remove(LinkedListNode<E>* node) {
|
|
|
261 LinkedListNode<E>* p = this->head();
|
|
|
262 while (p != NULL && p->next() != node) {
|
|
|
263 p = p->next();
|
|
|
264 }
|
|
|
265 if (p != NULL) {
|
|
|
266 p->set_next(node->next());
|
|
|
267 delete_node(node);
|
|
|
268 return true;
|
|
|
269 } else {
|
|
|
270 return false;
|
|
|
271 }
|
|
|
272 }
|
|
|
273
|
|
|
274 virtual bool remove_before(LinkedListNode<E>* ref) {
|
|
|
275 assert(ref != NULL, "NULL pointer");
|
|
|
276 LinkedListNode<E>* p = this->head();
|
|
|
277 LinkedListNode<E>* to_delete = NULL; // to be deleted
|
|
|
278 LinkedListNode<E>* prev = NULL; // node before the node to be deleted
|
|
|
279 while (p != NULL && p != ref) {
|
|
|
280 prev = to_delete;
|
|
|
281 to_delete = p;
|
|
|
282 p = p->next();
|
|
|
283 }
|
|
|
284 if (p == NULL || to_delete == NULL) return false;
|
|
|
285 assert(to_delete->next() == ref, "Wrong node to delete");
|
|
|
286 assert(prev == NULL || prev->next() == to_delete,
|
|
|
287 "Sanity check");
|
|
|
288 if (prev == NULL) {
|
|
|
289 assert(to_delete == this->head(), "Must be head");
|
|
|
290 this->set_head(to_delete->next());
|
|
|
291 } else {
|
|
|
292 prev->set_next(to_delete->next());
|
|
|
293 }
|
|
|
294 delete_node(to_delete);
|
|
|
295 return true;
|
|
|
296 }
|
|
|
297
|
|
|
298 DEBUG_ONLY(ResourceObj::allocation_type storage_type() { return T; })
|
|
|
299 protected:
|
|
|
300 // Create new linked list node object in specified storage
|
|
|
301 LinkedListNode<E>* new_node(const E& e) const {
|
|
|
302 switch(T) {
|
|
|
303 case ResourceObj::ARENA: {
|
|
|
304 assert(_arena != NULL, "Arena not set");
|
|
|
305 return new(_arena) LinkedListNode<E>(e);
|
|
|
306 }
|
|
|
307 case ResourceObj::RESOURCE_AREA:
|
|
|
308 case ResourceObj::C_HEAP: {
|
|
|
309 if (alloc_failmode == AllocFailStrategy::RETURN_NULL) {
|
|
|
310 return new(std::nothrow, T, F) LinkedListNode<E>(e);
|
|
|
311 } else {
|
|
|
312 return new(T, F) LinkedListNode<E>(e);
|
|
|
313 }
|
|
|
314 }
|
|
|
315 default:
|
|
|
316 ShouldNotReachHere();
|
|
|
317 }
|
|
|
318 return NULL;
|
|
|
319 }
|
|
|
320
|
|
|
321 // Delete linked list node object
|
|
|
322 void delete_node(LinkedListNode<E>* node) {
|
|
|
323 if (T == ResourceObj::C_HEAP) {
|
|
|
324 delete node;
|
|
|
325 }
|
|
|
326 }
|
|
|
327 };
|
|
|
328
|
|
|
329 // Sorted linked list. The linked list maintains sorting order specified by the comparison
|
|
|
330 // function
|
|
|
331 template <class E, int (*FUNC)(const E&, const E&),
|
|
|
332 ResourceObj::allocation_type T = ResourceObj::C_HEAP,
|
|
|
333 MEMFLAGS F = mtNMT, AllocFailType alloc_failmode = AllocFailStrategy::RETURN_NULL>
|
|
|
334 class SortedLinkedList : public LinkedListImpl<E, T, F, alloc_failmode> {
|
|
|
335 public:
|
|
|
336 SortedLinkedList() { }
|
|
|
337 SortedLinkedList(Arena* a) : LinkedListImpl<E, T, F, alloc_failmode>(a) { }
|
|
|
338
|
|
|
339 virtual LinkedListNode<E>* add(const E& e) {
|
|
|
340 return LinkedListImpl<E, T, F, alloc_failmode>::add(e);
|
|
|
341 }
|
|
|
342
|
|
|
343 virtual void move(LinkedList<E>* list) {
|
|
|
344 assert(list->storage_type() == this->storage_type(), "Different storage type");
|
|
|
345 LinkedListNode<E>* node;
|
|
|
346 while ((node = list->unlink_head()) != NULL) {
|
|
|
347 this->add(node);
|
|
|
348 }
|
|
|
349 assert(list->is_empty(), "All entries are moved");
|
|
|
350 }
|
|
|
351
|
|
|
352 virtual void add(LinkedListNode<E>* node) {
|
|
|
353 assert(node != NULL, "NULL pointer");
|
|
|
354 LinkedListNode<E>* tmp = this->head();
|
|
|
355 LinkedListNode<E>* prev = NULL;
|
|
|
356
|
|
|
357 int cmp_val;
|
|
|
358 while (tmp != NULL) {
|
|
|
359 cmp_val = FUNC(*tmp->peek(), *node->peek());
|
|
|
360 if (cmp_val >= 0) {
|
|
|
361 break;
|
|
|
362 }
|
|
|
363 prev = tmp;
|
|
|
364 tmp = tmp->next();
|
|
|
365 }
|
|
|
366
|
|
|
367 if (prev != NULL) {
|
|
|
368 node->set_next(prev->next());
|
|
|
369 prev->set_next(node);
|
|
|
370 } else {
|
|
|
371 node->set_next(this->head());
|
|
|
372 this->set_head(node);
|
|
|
373 }
|
|
|
374 }
|
|
|
375
|
|
|
376 virtual bool add(const LinkedList<E>* list) {
|
|
|
377 return LinkedListImpl<E, T, F, alloc_failmode>::add(list);
|
|
|
378 }
|
|
|
379
|
|
|
380 virtual LinkedListNode<E>* find_node(const E& e) {
|
|
|
381 LinkedListNode<E>* p = this->head();
|
|
|
382
|
|
|
383 while (p != NULL) {
|
|
|
384 int comp_val = FUNC(*p->peek(), e);
|
|
|
385 if (comp_val == 0) {
|
|
|
386 return p;
|
|
|
387 } else if (comp_val > 0) {
|
|
|
388 return NULL;
|
|
|
389 }
|
|
|
390 p = p->next();
|
|
|
391 }
|
|
|
392 return NULL;
|
|
|
393 }
|
|
|
394 };
|
|
|
395
|
|
|
396 // Iterates all entries in the list
|
|
|
397 template <class E> class LinkedListIterator : public StackObj {
|
|
|
398 private:
|
|
|
399 LinkedListNode<E>* _p;
|
|
|
400 bool _is_empty;
|
|
|
401 public:
|
|
|
402 LinkedListIterator(LinkedListNode<E>* head) : _p(head) {
|
|
|
403 _is_empty = (head == NULL);
|
|
|
404 }
|
|
|
405
|
|
|
406 bool is_empty() const { return _is_empty; }
|
|
|
407
|
|
|
408 const E* next() {
|
|
|
409 if (_p == NULL) return NULL;
|
|
|
410 const E* e = _p->peek();
|
|
|
411 _p = _p->next();
|
|
|
412 return e;
|
|
|
413 }
|
|
|
414 };
|
|
|
415
|
|
|
416 #endif
|
