|
/*
* Copyright (c) 2014, 2020, 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_UTILITIES_LINKEDLIST_HPP
#define SHARE_UTILITIES_LINKEDLIST_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 AnyObj {
private:
E _data; // embedded content
LinkedListNode<E>* _next; // next entry
// Select member function 'bool U::equals(const U&) const' if 'U' is of class
// type. This works because of the "Substitution Failure Is Not An Error"
// (SFINAE) rule. Notice that this version of 'equal' will also be chosen for
// class types which don't define a corresponding 'equals()' method (and will
// result in a compilation error for them). It is not easily possible to
// specialize this 'equal()' function exclusively for class types which define
// the correct 'equals()' function because that function can be in a base
// class, a dependent base class or have a compatible but slightly different
// signature.
template <class U>
static bool equal(const U& a, const U& b, bool (U::*t)(const U&) const) {
return a.equals(b);
}
template <class U>
static bool equal(const U& a, const U& b, ...) {
return a == b;
}
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; }
bool equals(const E& t) const {
return equal<E>(_data, t, NULL);
}
};
// 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 AnyObj {
protected:
LinkedListNode<E>* _head;
NONCOPYABLE(LinkedList<E>);
public:
LinkedList() : _head(NULL) { }
virtual ~LinkedList() {}
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 AnyObj::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, AnyObj::allocation_type T = AnyObj::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->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->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();
if (p == node) {
this->set_head(p->next());
delete_node(node);
return true;
}
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(AnyObj::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 AnyObj::ARENA: {
assert(_arena != NULL, "Arena not set");
return new(_arena) LinkedListNode<E>(e);
}
case AnyObj::RESOURCE_AREA:
if (alloc_failmode == AllocFailStrategy::RETURN_NULL) {
return new(std::nothrow) LinkedListNode<E>(e);
} else {
return new LinkedListNode<E>(e);
}
case AnyObj::C_HEAP: {
if (alloc_failmode == AllocFailStrategy::RETURN_NULL) {
return new(std::nothrow, F) LinkedListNode<E>(e);
} else {
return new(F) LinkedListNode<E>(e);
}
}
default:
ShouldNotReachHere();
}
return NULL;
}
// Delete linked list node object
void delete_node(LinkedListNode<E>* node) {
if (T == AnyObj::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&),
AnyObj::allocation_type T = AnyObj::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:
mutable LinkedListNode<E>* _p;
public:
LinkedListIterator(LinkedListNode<E>* head) : _p(head) {}
bool is_empty() const { return _p == NULL; }
E* next() {
if (_p == NULL) return NULL;
E* e = _p->data();
_p = _p->next();
return e;
}
const E* next() const {
if (_p == NULL) return NULL;
const E* e = _p->peek();
_p = _p->next();
return e;
}
};
#endif // SHARE_UTILITIES_LINKEDLIST_HPP
¤ Dauer der Verarbeitung: 0.7 Sekunden
(vorverarbeitet)
¤
|
Haftungshinweis
Die Informationen auf dieser Webseite wurden
nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit,
noch Qualität der bereit gestellten Informationen zugesichert.
Bemerkung:
Die farbliche Syntaxdarstellung ist noch experimentell.
|
