1/*
2 * Copyright (c) 2014, 2019, 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_UTILITIES_LINKEDLIST_HPP
26#define SHARE_UTILITIES_LINKEDLIST_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.
38template <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
59template <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.
115template <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 if (p == node) {
263 this->set_head(p->next());
264 delete_node(node);
265 return true;
266 }
267 while (p != NULL && p->next() != node) {
268 p = p->next();
269 }
270 if (p != NULL) {
271 p->set_next(node->next());
272 delete_node(node);
273 return true;
274 } else {
275 return false;
276 }
277 }
278
279 virtual bool remove_before(LinkedListNode<E>* ref) {
280 assert(ref != NULL, "NULL pointer");
281 LinkedListNode<E>* p = this->head();
282 LinkedListNode<E>* to_delete = NULL; // to be deleted
283 LinkedListNode<E>* prev = NULL; // node before the node to be deleted
284 while (p != NULL && p != ref) {
285 prev = to_delete;
286 to_delete = p;
287 p = p->next();
288 }
289 if (p == NULL || to_delete == NULL) return false;
290 assert(to_delete->next() == ref, "Wrong node to delete");
291 assert(prev == NULL || prev->next() == to_delete,
292 "Sanity check");
293 if (prev == NULL) {
294 assert(to_delete == this->head(), "Must be head");
295 this->set_head(to_delete->next());
296 } else {
297 prev->set_next(to_delete->next());
298 }
299 delete_node(to_delete);
300 return true;
301 }
302
303 DEBUG_ONLY(ResourceObj::allocation_type storage_type() { return T; })
304 protected:
305 // Create new linked list node object in specified storage
306 LinkedListNode<E>* new_node(const E& e) const {
307 switch(T) {
308 case ResourceObj::ARENA: {
309 assert(_arena != NULL, "Arena not set");
310 return new(_arena) LinkedListNode<E>(e);
311 }
312 case ResourceObj::RESOURCE_AREA:
313 case ResourceObj::C_HEAP: {
314 if (alloc_failmode == AllocFailStrategy::RETURN_NULL) {
315 return new(std::nothrow, T, F) LinkedListNode<E>(e);
316 } else {
317 return new(T, F) LinkedListNode<E>(e);
318 }
319 }
320 default:
321 ShouldNotReachHere();
322 }
323 return NULL;
324 }
325
326 // Delete linked list node object
327 void delete_node(LinkedListNode<E>* node) {
328 if (T == ResourceObj::C_HEAP) {
329 delete node;
330 }
331 }
332};
333
334// Sorted linked list. The linked list maintains sorting order specified by the comparison
335// function
336template <class E, int (*FUNC)(const E&, const E&),
337 ResourceObj::allocation_type T = ResourceObj::C_HEAP,
338 MEMFLAGS F = mtNMT, AllocFailType alloc_failmode = AllocFailStrategy::RETURN_NULL>
339 class SortedLinkedList : public LinkedListImpl<E, T, F, alloc_failmode> {
340 public:
341 SortedLinkedList() { }
342 SortedLinkedList(Arena* a) : LinkedListImpl<E, T, F, alloc_failmode>(a) { }
343
344 virtual LinkedListNode<E>* add(const E& e) {
345 return LinkedListImpl<E, T, F, alloc_failmode>::add(e);
346 }
347
348 virtual void move(LinkedList<E>* list) {
349 assert(list->storage_type() == this->storage_type(), "Different storage type");
350 LinkedListNode<E>* node;
351 while ((node = list->unlink_head()) != NULL) {
352 this->add(node);
353 }
354 assert(list->is_empty(), "All entries are moved");
355 }
356
357 virtual void add(LinkedListNode<E>* node) {
358 assert(node != NULL, "NULL pointer");
359 LinkedListNode<E>* tmp = this->head();
360 LinkedListNode<E>* prev = NULL;
361
362 int cmp_val;
363 while (tmp != NULL) {
364 cmp_val = FUNC(*tmp->peek(), *node->peek());
365 if (cmp_val >= 0) {
366 break;
367 }
368 prev = tmp;
369 tmp = tmp->next();
370 }
371
372 if (prev != NULL) {
373 node->set_next(prev->next());
374 prev->set_next(node);
375 } else {
376 node->set_next(this->head());
377 this->set_head(node);
378 }
379 }
380
381 virtual bool add(const LinkedList<E>* list) {
382 return LinkedListImpl<E, T, F, alloc_failmode>::add(list);
383 }
384
385 virtual LinkedListNode<E>* find_node(const E& e) {
386 LinkedListNode<E>* p = this->head();
387
388 while (p != NULL) {
389 int comp_val = FUNC(*p->peek(), e);
390 if (comp_val == 0) {
391 return p;
392 } else if (comp_val > 0) {
393 return NULL;
394 }
395 p = p->next();
396 }
397 return NULL;
398 }
399};
400
401// Iterates all entries in the list
402template <class E> class LinkedListIterator : public StackObj {
403 private:
404 LinkedListNode<E>* _p;
405 bool _is_empty;
406 public:
407 LinkedListIterator(LinkedListNode<E>* head) : _p(head) {
408 _is_empty = (head == NULL);
409 }
410
411 bool is_empty() const { return _is_empty; }
412
413 const E* next() {
414 if (_p == NULL) return NULL;
415 const E* e = _p->peek();
416 _p = _p->next();
417 return e;
418 }
419};
420
421#endif // SHARE_UTILITIES_LINKEDLIST_HPP
422