Mercurial > hg > truffle
comparison src/share/vm/utilities/linkedlist.hpp @ 20360:833b0f92429a
8046598: Scalable Native memory tracking development
Summary: Enhance scalability of native memory tracking
Reviewed-by: coleenp, ctornqvi, gtriantafill
author | zgu |
---|---|
date | Wed, 27 Aug 2014 08:19:12 -0400 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
20359:4d3a43351904 | 20360:833b0f92429a |
---|---|
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 |