jdk8-mips64-public/hotspot: src/share/vm/utilities/linkedlist.hpp@833b0f92429a (annotated)

src/share/vm/utilities/linkedlist.hpp@833b0f92429a (annotated)

src/share/vm/utilities/linkedlist.hpp

Wed, 27 Aug 2014 08:19:12 -0400

author: zgu
date: Wed, 27 Aug 2014 08:19:12 -0400
changeset 7074: 833b0f92429a
permissions: -rw-r--r--

8046598: Scalable Native memory tracking development
Summary: Enhance scalability of native memory tracking
Reviewed-by: coleenp, ctornqvi, gtriantafill

 /*
  * 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

Mercurial > jdk8-mips64-public > hotspot / annotate

src/share/vm/utilities/linkedlist.hpp@833b0f92429a (annotated)

src/share/vm/utilities/linkedlist.hpp