--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/hotspot/src/share/vm/utilities/linkedlist.hpp	Thu Aug 07 12:18:58 2014 -0700
@@ -0,0 +1,416 @@
+/*
+ * 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