/*
* Copyright (c) 2014, 2018, 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.
*
*/
#include "precompiled.hpp"
#include "jfr/leakprofiler/sampling/objectSample.hpp"
#include "jfr/leakprofiler/sampling/samplePriorityQueue.hpp"
#include "memory/allocation.inline.hpp"
#include "oops/oop.inline.hpp"
SamplePriorityQueue::SamplePriorityQueue(size_t size) :
_allocated_size(size),
_count(0),
_total(0) {
_items = NEW_C_HEAP_ARRAY(ObjectSample*, size, mtTracing);
memset(_items, 0, sizeof(ObjectSample*) * size);
}
SamplePriorityQueue::~SamplePriorityQueue() {
FREE_C_HEAP_ARRAY(ObjectSample*, _items);
_items = NULL;
}
void SamplePriorityQueue::push(ObjectSample* item) {
assert(item != NULL, "invariant");
assert(_items[_count] == NULL, "invariant");
_items[_count] = item;
_items[_count]->set_index(_count);
_count++;
moveUp(_count - 1);
_total += item->span();
}
size_t SamplePriorityQueue::total() const {
return _total;
}
ObjectSample* SamplePriorityQueue::pop() {
if (_count == 0) {
return NULL;
}
ObjectSample* const s = _items[0];
assert(s != NULL, "invariant");
swap(0, _count - 1);
_count--;
assert(s == _items[_count], "invariant");
// clear from heap
_items[_count] = NULL;
moveDown(0);
_total -= s->span();
return s;
}
void SamplePriorityQueue::swap(int i, int j) {
ObjectSample* tmp = _items[i];
_items[i] = _items[j];
_items[j] = tmp;
_items[i]->set_index(i);
_items[j]->set_index(j);
}
static int left(int i) {
return 2 * i + 1;
}
static int right(int i) {
return 2 * i + 2;
}
static int parent(int i) {
return (i - 1) / 2;
}
void SamplePriorityQueue::moveDown(int i) {
do {
int j = -1;
int r = right(i);
if (r < _count && _items[r]->span() < _items[i]->span()) {
int l = left(i);
if (_items[l]->span() < _items[r]->span()) {
j = l;
} else {
j = r;
}
} else {
int l = left(i);
if (l < _count && _items[l]->span() < _items[i]->span()) {
j = l;
}
}
if (j >= 0) {
swap(i, j);
}
i = j;
} while (i >= 0);
}
void SamplePriorityQueue::moveUp(int i) {
int p = parent(i);
while (i > 0 && _items[i]->span() < _items[p]->span()) {
swap(i,p);
i = p;
p = parent(i);
}
}
void SamplePriorityQueue::remove(ObjectSample* s) {
assert(s != NULL, "invariant");
const size_t realSpan = s->span();
/**代码未完, 请加载全部代码(NowJava.com).**/