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
31SamplePriorityQueue::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
39SamplePriorityQueue::~SamplePriorityQueue() {
40 FREE_C_HEAP_ARRAY(ObjectSample*, _items);
41 _items = NULL;
42}
43
44void 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
55size_t SamplePriorityQueue::total() const {
56 return _total;
57}
58
59ObjectSample* 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
76void 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
84static int left(int i) {
85 return 2 * i + 1;
86}
87
88static int right(int i) {
89 return 2 * i + 2;
90}
91
92static int parent(int i) {
93 return (i - 1) / 2;
94}
95
96void 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
121void 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
130void 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
139int SamplePriorityQueue::count() const {
140 return _count;
141}
142
143const ObjectSample* SamplePriorityQueue::peek() const {
144 return _count == 0 ? NULL : _items[0];
145}
146
147ObjectSample* SamplePriorityQueue::item_at(int index) {
148 assert(index >= 0 && index < _count, "out of range");
149 return _items[index];
150}
151