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 #include "metaspaceGtestCommon.hpp" 33 #include "metaspaceGtestRangeHelpers.hpp" 34 35 /////// SparseArray<T> //////////////// 36 37 // Throughout these tests we need to keep track of allocated items (ranges of metaspace memory, metachunks, ..) 38 // and be able to random-access them. Makes sense to have a helper for that. 39 template <class T> 40 class SparseArray : public StackObj { 41 42 T* const _slots; 43 const int _num; 44 45 // For convenience: a range covering all possible slot indices. 46 const IntRange _index_range; 47 contains(int index) const48 bool contains(int index) const { 49 return _index_range.contains(index); 50 } 51 52 // Check slot intex for oob check_index(int i) const53 void check_index(int i) const { 54 assert(contains(i), "Sanity"); 55 } 56 57 // Swap the content of two slots. swap(int i1,int i2)58 void swap(int i1, int i2) { 59 check_index(i1); 60 check_index(i2); 61 T tmp = _slots[i1]; 62 _slots[i1] = _slots[i2]; 63 _slots[i2] = tmp; 64 } 65 66 enum condition_t { cond_null = 0, cond_non_null = 1, cond_dontcare = 2 }; 67 68 // Helper for next_matching_slot slot_matches(int slot,condition_t c) const69 bool slot_matches(int slot, condition_t c) const { 70 switch(c) { 71 case cond_null: return _slots[slot] == NULL; 72 case cond_non_null: return _slots[slot] != NULL; 73 case cond_dontcare: return true; 74 } 75 ShouldNotReachHere(); 76 return false; 77 } 78 79 // Starting at (including) index, find the next matching slot. Returns index or -1 if none found. next_matching_slot(int slot,condition_t c) const80 int next_matching_slot(int slot, condition_t c) const { 81 while(slot < _num) { 82 if (slot_matches(slot, c)) { 83 return slot; 84 } 85 slot++; 86 } 87 return -1; 88 } 89 90 public: 91 SparseArray(int num)92 SparseArray(int num) : 93 _slots(NEW_C_HEAP_ARRAY(T, num, mtInternal)), 94 _num(num), 95 _index_range(num) 96 { 97 for (int i = 0; i < _num; i++) { 98 _slots[i] = NULL; 99 } 100 } 101 at(int i)102 T at(int i) { return _slots[i]; } at(int i) const103 const T at(int i) const { return _slots[i]; } set_at(int i,T e)104 void set_at(int i, T e) { _slots[i] = e; } 105 size() const106 int size() const { return _num; } 107 slot_is_null(int i) const108 bool slot_is_null(int i) const { check_index(i); return _slots[i] == NULL; } 109 110 DEBUG_ONLY(void check_slot_is_null(int i) const { assert(slot_is_null(i), "Slot %d is not null", i); }) DEBUG_ONLY(void check_slot_is_not_null (int i)const{ assert(!slot_is_null(i), "Slot %d is null", i); })111 DEBUG_ONLY(void check_slot_is_not_null(int i) const { assert(!slot_is_null(i), "Slot %d is null", i); }) 112 113 // Shuffle all elements randomly 114 void shuffle() { 115 for (int i = 0; i < _num; i++) { 116 swap(i, random_slot_index()); 117 } 118 } 119 120 // Reverse elements reverse()121 void reverse() { 122 for (int i = 0; i < _num / 2; i++) { 123 swap(i, _num - i); 124 } 125 } 126 first_slot() const127 int first_slot() const { return 0; } next_slot(int index) const128 int next_slot(int index) const { return index == _index_range.highest() ? -1 : index + 1; } 129 first_non_null_slot() const130 int first_non_null_slot() const { return next_matching_slot(0, cond_non_null); } next_non_null_slot(int index) const131 int next_non_null_slot(int index) const { return next_matching_slot(index + 1, cond_non_null); } 132 first_null_slot() const133 int first_null_slot() const { return next_matching_slot(0, cond_null); } next_null_slot(int index) const134 int next_null_slot(int index) const { return next_matching_slot(index + 1, cond_null); } 135 136 // Return a random slot index. random_slot_index() const137 int random_slot_index() const { 138 return _index_range.random_value(); 139 } 140 random_non_null_slot_index() const141 int random_non_null_slot_index() const { 142 int i = next_non_null_slot(_index_range.random_value()); 143 if (i == -1) { 144 i = first_non_null_slot(); 145 } 146 return i; 147 } 148 random_null_slot_index() const149 int random_null_slot_index() const { 150 int i = next_null_slot(_index_range.random_value()); 151 if (i == -1) { 152 i = first_null_slot(); 153 } 154 return i; 155 } 156 random_slot_range() const157 IntRange random_slot_range() const { 158 return _index_range.random_subrange(); 159 } 160 161 }; 162 163 #endif // GTEST_METASPACE_METASPACEGTESTSPARSEARRAY_HPP 164 165