Mercurial > hg > graal-compiler
view src/share/vm/utilities/linkedlist.hpp @ 22295:d86b226e331a
Enable derived oop processing by the GC with JVMCI
author | Tom Rodriguez <tom.rodriguez@oracle.com> |
---|---|
date | Tue, 21 Jul 2015 15:00:07 -0700 |
parents | 833b0f92429a |
children |
line wrap: on
line source
/* * Copyright (c) 2014, Oracle and/or its affiliates. All rights reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License version 2 only, as * published by the Free Software Foundation. * * This code is distributed in the hope that it will be useful, but WITHOUT * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License * version 2 for more details (a copy is included in the LICENSE file that * accompanied this code). * * You should have received a copy of the GNU General Public License version * 2 along with this work; if not, write to the Free Software Foundation, * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. * * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA * or visit www.oracle.com if you need additional information or have any * questions. * */ #ifndef SHARE_VM_UTILITIES_LINKED_LIST_HPP #define SHARE_VM_UTILITIES_LINKED_LIST_HPP #include "memory/allocation.hpp" /* * The implementation of a generic linked list, which uses various * backing storages, such as C heap, arena and resource, etc. */ // An entry in a linked list. It should use the same backing storage // as the linked list that contains this entry. template <class E> class LinkedListNode : public ResourceObj { private: E _data; // embedded content LinkedListNode<E>* _next; // next entry protected: LinkedListNode() : _next(NULL) { } public: LinkedListNode(const E& e): _data(e), _next(NULL) { } inline void set_next(LinkedListNode<E>* node) { _next = node; } inline LinkedListNode<E> * next() const { return _next; } E* data() { return &_data; } const E* peek() const { return &_data; } }; // A linked list interface. It does not specify // any storage type it uses, so all methods involving // memory allocation or deallocation are pure virtual template <class E> class LinkedList : public ResourceObj { protected: LinkedListNode<E>* _head; public: LinkedList() : _head(NULL) { } inline void set_head(LinkedListNode<E>* h) { _head = h; } inline LinkedListNode<E>* head() const { return _head; } inline bool is_empty() const { return head() == NULL; } inline size_t size() const { LinkedListNode<E>* p; size_t count = 0; for (p = head(); p != NULL; count++, p = p->next()); return count; } // Move all entries from specified linked list to this one virtual void move(LinkedList<E>* list) = 0; // Add an entry to this linked list virtual LinkedListNode<E>* add(const E& e) = 0; // Add all entries from specified linked list to this one, virtual void add(LinkedListNode<E>* node) = 0; // Add a linked list to this linked list virtual bool add(const LinkedList<E>* list) = 0; // Search entry in the linked list virtual LinkedListNode<E>* find_node(const E& e) = 0; virtual E* find(const E& e) = 0; // Insert entry to the linked list virtual LinkedListNode<E>* insert_before(const E& e, LinkedListNode<E>* ref) = 0; virtual LinkedListNode<E>* insert_after (const E& e, LinkedListNode<E>* ref) = 0; // Remove entry from the linked list virtual bool remove(const E& e) = 0; virtual bool remove(LinkedListNode<E>* node) = 0; virtual bool remove_before(LinkedListNode<E>* ref) = 0; virtual bool remove_after(LinkedListNode<E>* ref) = 0; LinkedListNode<E>* unlink_head() { LinkedListNode<E>* h = this->head(); if (h != NULL) { this->set_head(h->next()); } return h; } DEBUG_ONLY(virtual ResourceObj::allocation_type storage_type() = 0;) }; // A linked list implementation. // The linked list can be allocated in various type of memory: C heap, arena and resource area, etc. template <class E, ResourceObj::allocation_type T = ResourceObj::C_HEAP, MEMFLAGS F = mtNMT, AllocFailType alloc_failmode = AllocFailStrategy::RETURN_NULL> class LinkedListImpl : public LinkedList<E> { protected: Arena* _arena; public: LinkedListImpl() : _arena(NULL) { } LinkedListImpl(Arena* a) : _arena(a) { } virtual ~LinkedListImpl() { clear(); } virtual void clear() { LinkedListNode<E>* p = this->head(); this->set_head(NULL); while (p != NULL) { LinkedListNode<E>* to_delete = p; p = p->next(); delete_node(to_delete); } } // Add an entry to the linked list virtual LinkedListNode<E>* add(const E& e) { LinkedListNode<E>* node = this->new_node(e); if (node != NULL) { this->add(node); } return node; } virtual void add(LinkedListNode<E>* node) { assert(node != NULL, "NULL pointer"); node->set_next(this->head()); this->set_head(node); } // Move a linked list to this linked list, both have to be allocated on the same // storage type. virtual void move(LinkedList<E>* list) { assert(list->storage_type() == this->storage_type(), "Different storage type"); LinkedListNode<E>* node = this->head(); while (node != NULL && node->next() != NULL) { node = node->next(); } if (node == NULL) { this->set_head(list->head()); } else { node->set_next(list->head()); } // All entries are moved list->set_head(NULL); } virtual bool add(const LinkedList<E>* list) { LinkedListNode<E>* node = list->head(); while (node != NULL) { if (this->add(*node->peek()) == NULL) { return false; } node = node->next(); } return true; } virtual LinkedListNode<E>* find_node(const E& e) { LinkedListNode<E>* p = this->head(); while (p != NULL && !p->peek()->equals(e)) { p = p->next(); } return p; } E* find(const E& e) { LinkedListNode<E>* node = find_node(e); return (node == NULL) ? NULL : node->data(); } // Add an entry in front of the reference entry LinkedListNode<E>* insert_before(const E& e, LinkedListNode<E>* ref_node) { LinkedListNode<E>* node = this->new_node(e); if (node == NULL) return NULL; if (ref_node == this->head()) { node->set_next(ref_node); this->set_head(node); } else { LinkedListNode<E>* p = this->head(); while (p != NULL && p->next() != ref_node) { p = p->next(); } assert(p != NULL, "ref_node not in the list"); node->set_next(ref_node); p->set_next(node); } return node; } // Add an entry behind the reference entry LinkedListNode<E>* insert_after(const E& e, LinkedListNode<E>* ref_node) { LinkedListNode<E>* node = this->new_node(e); if (node == NULL) return NULL; node->set_next(ref_node->next()); ref_node->set_next(node); return node; } // Remove an entry from the linked list. // Return true if the entry is successfully removed virtual bool remove(const E& e) { LinkedListNode<E>* tmp = this->head(); LinkedListNode<E>* prev = NULL; while (tmp != NULL) { if (tmp->peek()->equals(e)) { return remove_after(prev); } prev = tmp; tmp = tmp->next(); } return false; } // Remove the node after the reference entry virtual bool remove_after(LinkedListNode<E>* prev) { LinkedListNode<E>* to_delete; if (prev == NULL) { to_delete = this->unlink_head(); } else { to_delete = prev->next(); if (to_delete != NULL) { prev->set_next(to_delete->next()); } } if (to_delete != NULL) { delete_node(to_delete); return true; } return false; } virtual bool remove(LinkedListNode<E>* node) { LinkedListNode<E>* p = this->head(); while (p != NULL && p->next() != node) { p = p->next(); } if (p != NULL) { p->set_next(node->next()); delete_node(node); return true; } else { return false; } } virtual bool remove_before(LinkedListNode<E>* ref) { assert(ref != NULL, "NULL pointer"); LinkedListNode<E>* p = this->head(); LinkedListNode<E>* to_delete = NULL; // to be deleted LinkedListNode<E>* prev = NULL; // node before the node to be deleted while (p != NULL && p != ref) { prev = to_delete; to_delete = p; p = p->next(); } if (p == NULL || to_delete == NULL) return false; assert(to_delete->next() == ref, "Wrong node to delete"); assert(prev == NULL || prev->next() == to_delete, "Sanity check"); if (prev == NULL) { assert(to_delete == this->head(), "Must be head"); this->set_head(to_delete->next()); } else { prev->set_next(to_delete->next()); } delete_node(to_delete); return true; } DEBUG_ONLY(ResourceObj::allocation_type storage_type() { return T; }) protected: // Create new linked list node object in specified storage LinkedListNode<E>* new_node(const E& e) const { switch(T) { case ResourceObj::ARENA: { assert(_arena != NULL, "Arena not set"); return new(_arena) LinkedListNode<E>(e); } case ResourceObj::RESOURCE_AREA: case ResourceObj::C_HEAP: { if (alloc_failmode == AllocFailStrategy::RETURN_NULL) { return new(std::nothrow, T, F) LinkedListNode<E>(e); } else { return new(T, F) LinkedListNode<E>(e); } } default: ShouldNotReachHere(); } return NULL; } // Delete linked list node object void delete_node(LinkedListNode<E>* node) { if (T == ResourceObj::C_HEAP) { delete node; } } }; // Sorted linked list. The linked list maintains sorting order specified by the comparison // function template <class E, int (*FUNC)(const E&, const E&), ResourceObj::allocation_type T = ResourceObj::C_HEAP, MEMFLAGS F = mtNMT, AllocFailType alloc_failmode = AllocFailStrategy::RETURN_NULL> class SortedLinkedList : public LinkedListImpl<E, T, F, alloc_failmode> { public: SortedLinkedList() { } SortedLinkedList(Arena* a) : LinkedListImpl<E, T, F, alloc_failmode>(a) { } virtual LinkedListNode<E>* add(const E& e) { return LinkedListImpl<E, T, F, alloc_failmode>::add(e); } virtual void move(LinkedList<E>* list) { assert(list->storage_type() == this->storage_type(), "Different storage type"); LinkedListNode<E>* node; while ((node = list->unlink_head()) != NULL) { this->add(node); } assert(list->is_empty(), "All entries are moved"); } virtual void add(LinkedListNode<E>* node) { assert(node != NULL, "NULL pointer"); LinkedListNode<E>* tmp = this->head(); LinkedListNode<E>* prev = NULL; int cmp_val; while (tmp != NULL) { cmp_val = FUNC(*tmp->peek(), *node->peek()); if (cmp_val >= 0) { break; } prev = tmp; tmp = tmp->next(); } if (prev != NULL) { node->set_next(prev->next()); prev->set_next(node); } else { node->set_next(this->head()); this->set_head(node); } } virtual bool add(const LinkedList<E>* list) { return LinkedListImpl<E, T, F, alloc_failmode>::add(list); } virtual LinkedListNode<E>* find_node(const E& e) { LinkedListNode<E>* p = this->head(); while (p != NULL) { int comp_val = FUNC(*p->peek(), e); if (comp_val == 0) { return p; } else if (comp_val > 0) { return NULL; } p = p->next(); } return NULL; } }; // Iterates all entries in the list template <class E> class LinkedListIterator : public StackObj { private: LinkedListNode<E>* _p; bool _is_empty; public: LinkedListIterator(LinkedListNode<E>* head) : _p(head) { _is_empty = (head == NULL); } bool is_empty() const { return _is_empty; } const E* next() { if (_p == NULL) return NULL; const E* e = _p->peek(); _p = _p->next(); return e; } }; #endif