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