1 /*

     2  * Copyright (c) 2016, 2018, 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_JFR_UTILITIES_JFRDOUBLYLINKEDLIST_HPP

    26 #define SHARE_VM_JFR_UTILITIES_JFRDOUBLYLINKEDLIST_HPP

    27 

    28 #include "memory/allocation.hpp"

    29 

    30 template <typename T>

    31 class JfrDoublyLinkedList {

    32  private:

    33   T* _head;

    34   T* _tail;

    35   size_t _count;

    36 

    37   T** list_head() { return &_head; }

    38   T** list_tail() { return &_tail; }

    39 

    40  public:

    41   typedef T Node;

    42   JfrDoublyLinkedList() : _head(NULL), _tail(NULL), _count(0) {}

    43   T* head() const { return _head; }

    44   T* tail() const { return _tail; }

    45   size_t count() const { return _count; }

    46   T* clear(bool return_tail = false);

    47   T* remove(T* const node);

    48   void prepend(T* const node);

    49   void append(T* const node);

    50   void append_list(T* const head_node, T* const tail_node, size_t count);

    51   debug_only(bool in_list(const T* const target_node) const;)

    52   debug_only(bool locate(const T* start_node, const T* const target_node) const;)

    53 };

    54 

    55 template <typename T>

    56 inline void JfrDoublyLinkedList<T>::prepend(T* const node) {

    57   assert(node != NULL, "invariant");

    58   node->set_prev(NULL);

    59   assert(!in_list(node), "already in list error");

    60   T** lh = list_head();

    61   if (*lh != NULL) {

    62     (*lh)->set_prev(node);

    63     node->set_next(*lh);

    64   } else {

    65     T** lt = list_tail();

    66     assert(*lt == NULL, "invariant");

    67     *lt = node;

    68     node->set_next(NULL);

    69     assert(tail() == node, "invariant");

    70     assert(node->next() == NULL, "invariant");

    71   }

    72   *lh = node;

    73   ++_count;

    74   assert(head() == node, "head error");

    75   assert(in_list(node), "not in list error");

    76   assert(node->prev() == NULL, "invariant");

    77 }

    78 

    79 template <typename T>

    80 void JfrDoublyLinkedList<T>::append(T* const node) {

    81   assert(node != NULL, "invariant");

    82   node->set_next(NULL);

    83   assert(!in_list(node), "already in list error");

    84   T** lt = list_tail();

    85   if (*lt != NULL) {

    86     // already an existing tail

    87     node->set_prev(*lt);

    88     (*lt)->set_next(node);

    89   } else {

    90     // if no tail, also update head

    91     assert(*lt == NULL, "invariant");

    92     T** lh = list_head();

    93     assert(*lh == NULL, "invariant");

    94     node->set_prev(NULL);

    95     *lh = node;

    96     assert(head() == node, "invariant");

    97   }

    98   *lt = node;

    99   ++_count;

   100   assert(tail() == node, "invariant");

   101   assert(in_list(node), "not in list error");

   102   assert(node->next() == NULL, "invariant");

   103 }

   104 

   105 template <typename T>

   106 T* JfrDoublyLinkedList<T>::remove(T* const node) {

   107   assert(node != NULL, "invariant");

   108   assert(in_list(node), "invariant");

   109   T* const prev = (T*)node->prev();

   110   T* const next = (T*)node->next();

   111   if (prev == NULL) {

   112     assert(head() == node, "head error");

   113     if (next != NULL) {

   114       next->set_prev(NULL);

   115     } else {

   116       assert(next == NULL, "invariant");

   117       assert(tail() == node, "tail error");

   118       T** lt = list_tail();

   119       *lt = NULL;

   120       assert(tail() == NULL, "invariant");

   121     }

   122     T** lh = list_head();

   123     *lh = next;

   124     assert(head() == next, "invariant");

   125   } else {

   126     assert(prev != NULL, "invariant");

   127     if (next == NULL) {

   128       assert(tail() == node, "tail error");

   129       T** lt = list_tail();

   130       *lt = prev;

   131       assert(tail() == prev, "invariant");

   132     } else {

   133        next->set_prev(prev);

   134     }

   135     prev->set_next(next);

   136   }

   137   --_count;

   138   assert(_count >= 0, "invariant");

   139   assert(!in_list(node), "still in list error");

   140   return node;

   141 }

   142 

   143 template <typename T>

   144 T* JfrDoublyLinkedList<T>::clear(bool return_tail /* false */) {

   145   T* const node = return_tail ? tail() : head();

   146   T** l = list_head();

   147   *l = NULL;

   148   l = list_tail();

   149   *l = NULL;

   150   _count = 0;

   151   assert(head() == NULL, "invariant");

   152   assert(tail() == NULL, "invariant");

   153   return node;

   154 }

   155 

   156 #ifdef ASSERT

   157 template <typename T>

   158 bool JfrDoublyLinkedList<T>::locate(const T* node, const T* const target) const {

   159   assert(target != NULL, "invariant");

   160   while (node != NULL) {

   161     if (node == target) {

   162       return true;

   163     }

   164     node = (T*)node->next();

   165   }

   166   return false;

   167 }

   168 

   169 template <typename T>

   170 bool JfrDoublyLinkedList<T>::in_list(const T* const target) const {

   171   assert(target != NULL, "invariant");

   172   return locate(head(), target);

   173 }

   174 

   175 template <typename T>

   176 inline void validate_count_param(T* node, size_t count_param) {

   177   assert(node != NULL, "invariant");

   178   size_t count = 0;

   179   while (node) {

   180     ++count;

   181     node = (T*)node->next();

   182   }

   183   assert(count_param == count, "invariant");

   184 }

   185 #endif // ASSERT

   186 

   187 template <typename T>

   188 void JfrDoublyLinkedList<T>::append_list(T* const head_node, T* const tail_node, size_t count) {

   189   assert(head_node != NULL, "invariant");

   190   assert(!in_list(head_node), "already in list error");

   191   assert(tail_node != NULL, "invariant");

   192   assert(!in_list(tail_node), "already in list error");

   193   assert(tail_node->next() == NULL, "invariant");

   194   // ensure passed in list nodes are connected

   195   assert(locate(head_node, tail_node), "invariant");

   196   T** lt = list_tail();

   197   if (*lt != NULL) {

   198     head_node->set_prev(*lt);

   199     (*lt)->set_next(head_node);

   200   } else {

   201     // no head

   202     assert(*lt == NULL, "invariant");

   203     T** lh = list_head();

   204     assert(*lh == NULL, "invariant");

   205     head_node->set_prev(NULL);

   206     *lh = head_node;

   207     assert(head() == head_node, "invariant");

   208   }

   209   *lt = tail_node;

   210   const T* node = head_node;

   211   debug_only(validate_count_param(node, count);)

   212     _count += count;

   213   assert(tail() == tail_node, "invariant");

   214   assert(in_list(tail_node), "not in list error");

   215   assert(in_list(head_node), "not in list error");

   216 }

   217 

   218 #endif // SHARE_VM_JFR_UTILITIES_JFRDOUBLYLINKEDLIST_HPP