--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/hotspot/share/jfr/leakprofiler/sampling/samplePriorityQueue.cpp Tue May 15 20:24:34 2018 +0200
@@ -0,0 +1,150 @@
+/*
+ * 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();
+ s->set_span(0);
+ moveUp(s->index());
+ s->set_span(realSpan);
+ pop();
+}
+
+int SamplePriorityQueue::count() const {
+ return _count;
+}
+
+const ObjectSample* SamplePriorityQueue::peek() const {
+ return _count == 0 ? NULL : _items[0];
+}
+
+ObjectSample* SamplePriorityQueue::item_at(int index) {
+ assert(index >= 0 && index < _count, "out of range");
+ return _items[index];
+}