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 }