1 /*

     2  * Copyright (c) 2014, Oracle and/or its affiliates. All rights reserved.

     3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

     4  *

     5  * This code is free software; you can redistribute it and/or modify it

     6  * under the terms of the GNU General Public License version 2 only, as

     7  * published by the Free Software Foundation.

     8  *

     9  * This code is distributed in the hope that it will be useful, but WITHOUT

    10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

    11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

    12  * version 2 for more details (a copy is included in the LICENSE file that

    13  * accompanied this code).

    14  *

    15  * You should have received a copy of the GNU General Public License version

    16  * 2 along with this work; if not, write to the Free Software Foundation,

    17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

    18  *

    19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

    20  * or visit www.oracle.com if you need additional information or have any

    21  * questions.

    22  *

    23  */

    24 

    25 #ifndef SHARE_VM_UTILITIES_LINKED_LIST_HPP

    26 #define SHARE_VM_UTILITIES_LINKED_LIST_HPP

    27 

    28 #include "memory/allocation.hpp"

    29 

    30 /*

    31  * The implementation of a generic linked list, which uses various

    32  * backing storages, such as C heap, arena and resource, etc.

    33  */

    34 

    35 

    36 // An entry in a linked list. It should use the same backing storage

    37 // as the linked list that contains this entry.

    38 template <class E> class LinkedListNode : public ResourceObj {

    39  private:

    40   E                       _data;  // embedded content

    41   LinkedListNode<E>*      _next;  // next entry

    42 

    43  protected:

    44   LinkedListNode() : _next(NULL) { }

    45 

    46  public:

    47   LinkedListNode(const E& e): _data(e), _next(NULL) { }

    48 

    49   inline void set_next(LinkedListNode<E>* node) { _next = node; }

    50   inline LinkedListNode<E> * next() const       { return _next; }

    51 

    52   E*  data() { return &_data; }

    53   const E* peek() const { return &_data; }

    54 };

    55 

    56 // A linked list interface. It does not specify

    57 // any storage type it uses, so all methods involving

    58 // memory allocation or deallocation are pure virtual

    59 template <class E> class LinkedList : public ResourceObj {

    60  protected:

    61   LinkedListNode<E>*    _head;

    62 

    63  public:

    64   LinkedList() : _head(NULL) { }

    65 

    66   inline void set_head(LinkedListNode<E>* h) { _head = h; }

    67   inline LinkedListNode<E>* head() const     { return _head; }

    68   inline bool is_empty()           const     { return head() == NULL; }

    69 

    70   inline size_t size() const {

    71     LinkedListNode<E>* p;

    72     size_t count = 0;

    73     for (p = head(); p != NULL; count++, p = p->next());

    74     return count;

    75  }

    76 

    77   // Move all entries from specified linked list to this one

    78   virtual void move(LinkedList<E>* list) = 0;

    79 

    80   // Add an entry to this linked list

    81   virtual LinkedListNode<E>* add(const E& e) = 0;

    82   // Add all entries from specified linked list to this one,

    83   virtual void add(LinkedListNode<E>* node) = 0;

    84 

    85   // Add a linked list to this linked list

    86   virtual bool  add(const LinkedList<E>* list) = 0;

    87 

    88   // Search entry in the linked list

    89   virtual LinkedListNode<E>* find_node(const E& e) = 0;

    90   virtual E* find(const E& e) = 0;

    91 

    92   // Insert entry to the linked list

    93   virtual LinkedListNode<E>* insert_before(const E& e, LinkedListNode<E>* ref) = 0;

    94   virtual LinkedListNode<E>* insert_after (const E& e, LinkedListNode<E>* ref) = 0;

    95 

    96   // Remove entry from the linked list

    97   virtual bool               remove(const E& e) = 0;

    98   virtual bool               remove(LinkedListNode<E>* node) = 0;

    99   virtual bool               remove_before(LinkedListNode<E>* ref) = 0;

   100   virtual bool               remove_after(LinkedListNode<E>*  ref) = 0;

   101 

   102   LinkedListNode<E>* unlink_head() {

   103     LinkedListNode<E>* h = this->head();

   104     if (h != NULL) {

   105       this->set_head(h->next());

   106     }

   107     return h;

   108   }

   109 

   110   DEBUG_ONLY(virtual ResourceObj::allocation_type storage_type() = 0;)

   111 };

   112 

   113 // A linked list implementation.

   114 // The linked list can be allocated in various type of memory: C heap, arena and resource area, etc.

   115 template <class E, ResourceObj::allocation_type T = ResourceObj::C_HEAP,

   116   MEMFLAGS F = mtNMT, AllocFailType alloc_failmode = AllocFailStrategy::RETURN_NULL>

   117   class LinkedListImpl : public LinkedList<E> {

   118  protected:

   119   Arena*                 _arena;

   120  public:

   121   LinkedListImpl() :  _arena(NULL) { }

   122   LinkedListImpl(Arena* a) : _arena(a) { }

   123 

   124   virtual ~LinkedListImpl() {

   125     clear();

   126   }

   127 

   128   virtual void clear() {

   129     LinkedListNode<E>* p = this->head();

   130     this->set_head(NULL);

   131     while (p != NULL) {

   132       LinkedListNode<E>* to_delete = p;

   133       p = p->next();

   134       delete_node(to_delete);

   135     }

   136   }

   137 

   138   // Add an entry to the linked list

   139   virtual LinkedListNode<E>* add(const E& e)  {

   140     LinkedListNode<E>* node = this->new_node(e);

   141     if (node != NULL) {

   142       this->add(node);

   143     }

   144 

   145     return node;

   146   }

   147 

   148   virtual void add(LinkedListNode<E>* node) {

   149     assert(node != NULL, "NULL pointer");

   150     node->set_next(this->head());

   151     this->set_head(node);

   152   }

   153 

   154   // Move a linked list to this linked list, both have to be allocated on the same

   155   // storage type.

   156   virtual void move(LinkedList<E>* list) {

   157     assert(list->storage_type() == this->storage_type(), "Different storage type");

   158     LinkedListNode<E>* node = this->head();

   159     while (node != NULL && node->next() != NULL) {

   160       node = node->next();

   161     }

   162     if (node == NULL) {

   163       this->set_head(list->head());

   164     } else {

   165       node->set_next(list->head());

   166     }

   167     // All entries are moved

   168     list->set_head(NULL);

   169   }

   170 

   171   virtual bool add(const LinkedList<E>* list) {

   172     LinkedListNode<E>* node = list->head();

   173     while (node != NULL) {

   174       if (this->add(*node->peek()) == NULL) {

   175         return false;

   176       }

   177       node = node->next();

   178     }

   179     return true;

   180   }

   181 

   182 

   183   virtual LinkedListNode<E>* find_node(const E& e) {

   184     LinkedListNode<E>* p = this->head();

   185     while (p != NULL && !p->peek()->equals(e)) {

   186       p = p->next();

   187     }

   188     return p;

   189   }

   190 

   191   E* find(const E& e) {

   192     LinkedListNode<E>* node = find_node(e);

   193     return (node == NULL) ? NULL : node->data();

   194   }

   195 

   196 

   197   // Add an entry in front of the reference entry

   198   LinkedListNode<E>* insert_before(const E& e, LinkedListNode<E>* ref_node) {

   199     LinkedListNode<E>* node = this->new_node(e);

   200     if (node == NULL) return NULL;

   201     if (ref_node == this->head()) {

   202       node->set_next(ref_node);

   203       this->set_head(node);

   204     } else {

   205       LinkedListNode<E>* p = this->head();

   206       while (p != NULL && p->next() != ref_node) {

   207         p = p->next();

   208       }

   209       assert(p != NULL, "ref_node not in the list");

   210       node->set_next(ref_node);

   211       p->set_next(node);

   212     }

   213     return node;

   214   }

   215 

   216    // Add an entry behind the reference entry

   217    LinkedListNode<E>* insert_after(const E& e, LinkedListNode<E>* ref_node) {

   218      LinkedListNode<E>* node = this->new_node(e);

   219      if (node == NULL) return NULL;

   220      node->set_next(ref_node->next());

   221      ref_node->set_next(node);

   222      return node;

   223    }

   224 

   225    // Remove an entry from the linked list.

   226    // Return true if the entry is successfully removed

   227    virtual bool remove(const E& e) {

   228      LinkedListNode<E>* tmp = this->head();

   229      LinkedListNode<E>* prev = NULL;

   230 

   231      while (tmp != NULL) {

   232        if (tmp->peek()->equals(e)) {

   233          return remove_after(prev);

   234        }

   235        prev = tmp;

   236        tmp = tmp->next();

   237      }

   238      return false;

   239   }

   240 

   241   // Remove the node after the reference entry

   242   virtual bool remove_after(LinkedListNode<E>* prev) {

   243     LinkedListNode<E>* to_delete;

   244     if (prev == NULL) {

   245       to_delete = this->unlink_head();

   246     } else {

   247       to_delete = prev->next();

   248       if (to_delete != NULL) {

   249         prev->set_next(to_delete->next());

   250       }

   251     }

   252 

   253     if (to_delete != NULL) {

   254       delete_node(to_delete);

   255       return true;

   256     }

   257     return false;

   258   }

   259 

   260   virtual bool remove(LinkedListNode<E>* node) {

   261     LinkedListNode<E>* p = this->head();

   262     if (p == node) {

   263       this->set_head(p->next());

   264       delete_node(node);

   265       return true;

   266     }

   267     while (p != NULL && p->next() != node) {

   268       p = p->next();

   269     }

   270     if (p != NULL) {

   271       p->set_next(node->next());

   272       delete_node(node);

   273       return true;

   274     } else {

   275       return false;

   276     }

   277   }

   278 

   279   virtual bool remove_before(LinkedListNode<E>* ref) {

   280     assert(ref != NULL, "NULL pointer");

   281     LinkedListNode<E>* p = this->head();

   282     LinkedListNode<E>* to_delete = NULL; // to be deleted

   283     LinkedListNode<E>* prev = NULL;      // node before the node to be deleted

   284     while (p != NULL && p != ref) {

   285       prev = to_delete;

   286       to_delete = p;

   287       p = p->next();

   288     }

   289     if (p == NULL || to_delete == NULL) return false;

   290     assert(to_delete->next() == ref, "Wrong node to delete");

   291     assert(prev == NULL || prev->next() == to_delete,

   292       "Sanity check");

   293     if (prev == NULL) {

   294       assert(to_delete == this->head(), "Must be head");

   295       this->set_head(to_delete->next());

   296     } else {

   297       prev->set_next(to_delete->next());

   298     }

   299     delete_node(to_delete);

   300     return true;

   301   }

   302 

   303   DEBUG_ONLY(ResourceObj::allocation_type storage_type() { return T; })

   304  protected:

   305   // Create new linked list node object in specified storage

   306   LinkedListNode<E>* new_node(const E& e) const {

   307      switch(T) {

   308        case ResourceObj::ARENA: {

   309          assert(_arena != NULL, "Arena not set");

   310          return new(_arena) LinkedListNode<E>(e);

   311        }

   312        case ResourceObj::RESOURCE_AREA:

   313        case ResourceObj::C_HEAP: {

   314          if (alloc_failmode == AllocFailStrategy::RETURN_NULL) {

   315            return new(std::nothrow, T, F) LinkedListNode<E>(e);

   316          } else {

   317            return new(T, F) LinkedListNode<E>(e);

   318          }

   319        }

   320        default:

   321          ShouldNotReachHere();

   322      }

   323      return NULL;

   324   }

   325 

   326   // Delete linked list node object

   327   void delete_node(LinkedListNode<E>* node) {

   328     if (T == ResourceObj::C_HEAP) {

   329       delete node;

   330     }

   331   }

   332 };

   333 

   334 // Sorted linked list. The linked list maintains sorting order specified by the comparison

   335 // function

   336 template <class E, int (*FUNC)(const E&, const E&),

   337   ResourceObj::allocation_type T = ResourceObj::C_HEAP,

   338   MEMFLAGS F = mtNMT, AllocFailType alloc_failmode = AllocFailStrategy::RETURN_NULL>

   339   class SortedLinkedList : public LinkedListImpl<E, T, F, alloc_failmode> {

   340  public:

   341   SortedLinkedList() { }

   342   SortedLinkedList(Arena* a) : LinkedListImpl<E, T, F, alloc_failmode>(a) { }

   343 

   344   virtual LinkedListNode<E>* add(const E& e) {

   345     return LinkedListImpl<E, T, F, alloc_failmode>::add(e);

   346   }

   347 

   348   virtual void move(LinkedList<E>* list) {

   349     assert(list->storage_type() == this->storage_type(), "Different storage type");

   350     LinkedListNode<E>* node;

   351     while ((node = list->unlink_head()) != NULL) {

   352       this->add(node);

   353     }

   354     assert(list->is_empty(), "All entries are moved");

   355   }

   356 

   357   virtual void add(LinkedListNode<E>* node) {

   358     assert(node != NULL, "NULL pointer");

   359     LinkedListNode<E>* tmp = this->head();

   360     LinkedListNode<E>* prev = NULL;

   361 

   362     int cmp_val;

   363     while (tmp != NULL) {

   364       cmp_val = FUNC(*tmp->peek(), *node->peek());

   365       if (cmp_val >= 0) {

   366         break;

   367       }

   368       prev = tmp;

   369       tmp = tmp->next();

   370     }

   371 

   372     if (prev != NULL) {

   373       node->set_next(prev->next());

   374       prev->set_next(node);

   375     } else {

   376       node->set_next(this->head());

   377       this->set_head(node);

   378     }

   379   }

   380 

   381   virtual bool add(const LinkedList<E>* list) {

   382     return LinkedListImpl<E, T, F, alloc_failmode>::add(list);

   383   }

   384 

   385   virtual LinkedListNode<E>* find_node(const E& e) {

   386     LinkedListNode<E>* p = this->head();

   387 

   388     while (p != NULL) {

   389       int comp_val = FUNC(*p->peek(), e);

   390       if (comp_val == 0) {

   391         return p;

   392       } else if (comp_val > 0) {

   393         return NULL;

   394       }

   395       p = p->next();

   396     }

   397     return NULL;

   398   }

   399 };

   400 

   401 // Iterates all entries in the list

   402 template <class E> class LinkedListIterator : public StackObj {

   403  private:

   404   LinkedListNode<E>* _p;

   405   bool               _is_empty;

   406  public:

   407   LinkedListIterator(LinkedListNode<E>* head) : _p(head) {

   408     _is_empty = (head == NULL);

   409   }

   410 

   411   bool is_empty() const { return _is_empty; }

   412 

   413   const E* next() {

   414     if (_p == NULL) return NULL;

   415     const E* e = _p->peek();

   416     _p = _p->next();

   417     return e;

   418   }

   419 };

   420 

   421 #endif