1 /*
2 * Copyright (c) 2020, Oracle and/or its affiliates. All rights reserved.
3 * Copyright (c) 2020 SAP SE. All rights reserved.
4 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
5 *
6 * This code is free software; you can redistribute it and/or modify it
7 * under the terms of the GNU General Public License version 2 only, as
8 * published by the Free Software Foundation.
9 *
10 * This code is distributed in the hope that it will be useful, but WITHOUT
11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13 * version 2 for more details (a copy is included in the LICENSE file that
14 * accompanied this code).
15 *
16 * You should have received a copy of the GNU General Public License version
17 * 2 along with this work; if not, write to the Free Software Foundation,
18 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
19 *
20 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
21 * or visit www.oracle.com if you need additional information or have any
22 * questions.
23 *
24 */
25
26 #ifndef GTEST_METASPACE_METASPACEGTESTSPARSEARRAY_HPP
27 #define GTEST_METASPACE_METASPACEGTESTSPARSEARRAY_HPP
28
29 #include "memory/allocation.hpp"
30 #include "runtime/os.hpp"
31 #include "utilities/debug.hpp"
32
33 #include "metaspaceGtestCommon.hpp"
34 #include "metaspaceGtestRangeHelpers.hpp"
35
36 /////// SparseArray<T> ////////////////
37
38 // Throughout these tests we need to keep track of allocated items (ranges of metaspace memory, metachunks, ..)
39 // and be able to random-access them. Makes sense to have a helper for that.
40 template <class T>
41 class SparseArray : public StackObj {
42
43 T* const _slots;
44 const int _num;
45
46 // For convenience: a range covering all possible slot indices.
47 const IntRange _index_range;
48
49 bool contains(int index) const {
50 return _index_range.contains(index);
51 }
52
53 // Check slot intex for oob
54 void check_index(int i) const {
55 assert(contains(i), "Sanity");
56 }
57
58 // Swap the content of two slots.
59 void swap(int i1, int i2) {
60 check_index(i1);
61 check_index(i2);
62 T tmp = _slots[i1];
63 _slots[i1] = _slots[i2];
64 _slots[i2] = tmp;
65 }
66
67 enum condition_t { cond_null = 0, cond_non_null = 1, cond_dontcare = 2 };
68
69 // Helper for next_matching_slot
70 bool slot_matches(int slot, condition_t c) const {
71 switch(c) {
72 case cond_null: return _slots[slot] == NULL;
73 case cond_non_null: return _slots[slot] != NULL;
74 case cond_dontcare: return true;
75 }
76 ShouldNotReachHere();
77 return false;
78 }
79
80 // Starting at (including) index, find the next matching slot. Returns index or -1 if none found.
81 int next_matching_slot(int slot, condition_t c) const {
82 while(slot < _num) {
83 if (slot_matches(slot, c)) {
84 return slot;
85 }
86 slot++;
87 }
88 return -1;
89 }
90
91 public:
92
93 SparseArray(int num)
94 : _slots(NEW_C_HEAP_ARRAY(T, num, mtInternal)),
95 _num(num),
96 _index_range(num)
97 {
98 for (int i = 0; i < _num; i++) {
99 _slots[i] = NULL;
100 }
101 }
102
103 T at(int i) { return _slots[i]; }
104 const T at(int i) const { return _slots[i]; }
105 void set_at(int i, T e) { _slots[i] = e; }
106
107 int size() const { return _num; }
108
109 bool slot_is_null(int i) const { check_index(i); return _slots[i] == NULL; }
110
111 DEBUG_ONLY(void check_slot_is_null(int i) const { assert(slot_is_null(i), "Slot %d is not null", i); })
112 DEBUG_ONLY(void check_slot_is_not_null(int i) const { assert(!slot_is_null(i), "Slot %d is null", i); })
113
114 // Shuffle all elements randomly
115 void shuffle() {
116 for (int i = 0; i < _num; i++) {
117 swap(i, random_slot_index());
118 }
119 }
120
121 // Reverse elements
122 void reverse() {
123 for (int i = 0; i < _num / 2; i++) {
124 swap(i, _num - i);
125 }
126 }
127
128 int first_slot() const { return 0; }
129 int next_slot(int index) const { return index == _index_range.highest() ? -1 : index + 1; }
130
131 int first_non_null_slot() const { return next_matching_slot(0, cond_non_null); }
132 int next_non_null_slot(int index) const { return next_matching_slot(index + 1, cond_non_null); }
133
134 int first_null_slot() const { return next_matching_slot(0, cond_null); }
135 int next_null_slot(int index) const { return next_matching_slot(index + 1, cond_null); }
136
137 // Return a random slot index.
138 int random_slot_index() const {
139 return _index_range.random_value();
140 }
141
142 int random_non_null_slot_index() const {
143 int i = next_non_null_slot(_index_range.random_value());
144 if (i == -1) {
145 i = first_non_null_slot();
146 }
147 return i;
148 }
149
150 int random_null_slot_index() const {
151 int i = next_null_slot(_index_range.random_value());
152 if (i == -1) {
153 i = first_null_slot();
154 }
155 return i;
156 }
157
158 IntRange random_slot_range() const {
159 return _index_range.random_subrange();
160 }
161
162 };
163
164 #endif // GTEST_METASPACE_METASPACEGTESTSPARSEARRAY_HPP
165