1 /*

     2  * Copyright (c) 2014, 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 #include "precompiled.hpp"

    26 #include "jfr/leakprofiler/sampling/objectSample.hpp"

    27 #include "jfr/leakprofiler/sampling/samplePriorityQueue.hpp"

    28 #include "memory/allocation.inline.hpp"

    29 #include "oops/oop.inline.hpp"

    30 

    31 SamplePriorityQueue::SamplePriorityQueue(size_t size) :

    32   _allocated_size(size),

    33   _count(0),

    34   _total(0) {

    35   _items =  NEW_C_HEAP_ARRAY(ObjectSample*, size, mtTracing);

    36   memset(_items, 0, sizeof(ObjectSample*) * size);

    37 }

    38 

    39 SamplePriorityQueue::~SamplePriorityQueue() {

    40   FREE_C_HEAP_ARRAY(ObjectSample*, _items);

    41   _items = NULL;

    42 }

    43 

    44 void SamplePriorityQueue::push(ObjectSample* item) {

    45   assert(item != NULL, "invariant");

    46   assert(_items[_count] == NULL, "invariant");

    47 

    48   _items[_count] = item;

    49   _items[_count]->set_index(_count);

    50   _count++;

    51   moveUp(_count - 1);

    52   _total += item->span();

    53 }

    54 

    55 size_t SamplePriorityQueue::total() const {

    56   return _total;

    57 }

    58 

    59 ObjectSample* SamplePriorityQueue::pop() {

    60   if (_count == 0) {

    61     return NULL;

    62   }

    63 

    64   ObjectSample* const s = _items[0];

    65   assert(s != NULL, "invariant");

    66   swap(0, _count - 1);

    67   _count--;

    68   assert(s == _items[_count], "invariant");

    69   // clear from heap

    70   _items[_count] = NULL;

    71   moveDown(0);

    72   _total -= s->span();

    73   return s;

    74 }

    75 

    76 void SamplePriorityQueue::swap(int i, int j) {

    77   ObjectSample* tmp = _items[i];

    78   _items[i] = _items[j];

    79   _items[j] = tmp;

    80   _items[i]->set_index(i);

    81   _items[j]->set_index(j);

    82 }

    83 

    84 static int left(int i) {

    85   return 2 * i + 1;

    86 }

    87 

    88 static int right(int i) {

    89   return 2 * i + 2;

    90 }

    91 

    92 static int parent(int i) {

    93   return (i - 1) / 2;

    94 }

    95 

    96 void SamplePriorityQueue::moveDown(int i) {

    97   do {

    98     int j = -1;

    99     int r = right(i);

   100     if (r < _count && _items[r]->span() < _items[i]->span()) {

   101       int l = left(i);

   102       if (_items[l]->span() < _items[r]->span()) {

   103         j = l;

   104       } else {

   105         j = r;

   106       }

   107     } else {

   108       int l = left(i);

   109       if (l < _count && _items[l]->span() < _items[i]->span()) {

   110         j = l;

   111       }

   112     }

   113     if (j >= 0) {

   114       swap(i, j);

   115     }

   116     i = j;

   117   } while (i >= 0);

   118 

   119 }

   120 

   121 void SamplePriorityQueue::moveUp(int i) {

   122   int p = parent(i);

   123   while (i > 0 && _items[i]->span() < _items[p]->span()) {

   124     swap(i,p);

   125     i = p;

   126     p = parent(i);

   127   }

   128 }

   129 

   130 void SamplePriorityQueue::remove(ObjectSample* s) {

   131   assert(s != NULL, "invariant");

   132   const size_t realSpan = s->span();

   133   s->set_span(0);

   134   moveUp(s->index());

   135   s->set_span(realSpan);

   136   pop();

   137 }

   138 

   139 int SamplePriorityQueue::count() const {

   140   return _count;

   141 }

   142 

   143 const ObjectSample* SamplePriorityQueue::peek() const {

   144   return _count == 0 ? NULL : _items[0];

   145 }

   146 

   147 ObjectSample* SamplePriorityQueue::item_at(int index) {

   148   assert(index >= 0 && index < _count, "out of range");

   149   return _items[index];

   150 }