1 /* 2 * Copyright (c) 2017, 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 "utilities/bitMap.inline.hpp" 27 #include "utilities/debug.hpp" 28 #include "utilities/globalDefinitions.hpp" 29 #include "unittest.hpp" 30 31 typedef BitMap::idx_t idx_t; 32 typedef BitMap::bm_word_t bm_word_t; 33 34 static const idx_t BITMAP_SIZE = 1024; 35 36 static const size_t search_chunk_size = 64; 37 38 // Entries must be monotonically increasing. 39 // Maximum entry must be < search_chunk_size. 40 // Cluster values around possible word-size boundaries. 41 static const size_t search_offsets[] = 42 { 0, 1, 2, 29, 30, 31, 32, 33, 34, 60, 62, 63 }; 43 44 static const size_t search_noffsets = ARRAY_SIZE(search_offsets); 45 46 static const size_t search_nchunks = BITMAP_SIZE / search_chunk_size; 47 STATIC_ASSERT(search_nchunks * search_chunk_size == BITMAP_SIZE); 48 49 namespace { 50 class TestIteratorFn : public BitMapClosure { 51 public: 52 TestIteratorFn(size_t start, size_t end, size_t left, size_t right); 53 virtual bool do_bit(size_t offset); 54 55 private: 56 size_t _entries[2]; 57 size_t _index; 58 size_t _count; 59 size_t _start; 60 size_t _end; 61 size_t _left; 62 size_t _right; 63 64 void do_bit_aux(size_t offset); 65 66 }; 67 } // anonymous namespace 68 69 TestIteratorFn::TestIteratorFn(size_t start, size_t end, 70 size_t left, size_t right) : 71 _index(0), _count(0), _start(start), _end(end), _left(left), _right(right) 72 { 73 if ((_start <= _left) && (_left < _end)) { 74 _entries[_count++] = _left; 75 } 76 if ((_start <= _right) && (_right < _end)) { 77 _entries[_count++] = _right; 78 } 79 } 80 81 void TestIteratorFn::do_bit_aux(size_t offset) { 82 EXPECT_LT(_index, _count); 83 if (_index < _count) { 84 EXPECT_EQ(_entries[_index], offset); 85 _index += 1; 86 } 87 } 88 89 bool TestIteratorFn::do_bit(size_t offset) { 90 do_bit_aux(offset); 91 return true; 92 } 93 94 static idx_t compute_expected(idx_t search_start, 95 idx_t search_end, 96 idx_t left_bit, 97 idx_t right_bit) { 98 idx_t expected = search_end; 99 if (search_start <= left_bit) { 100 if (left_bit < search_end) { 101 expected = left_bit; 102 } 103 } else if (search_start <= right_bit) { 104 if (right_bit < search_end) { 105 expected = right_bit; 106 } 107 } 108 return expected; 109 } 110 111 static void test_search_ranges(BitMap& test_ones, 112 BitMap& test_zeros, 113 idx_t left, 114 idx_t right) { 115 // Test get_next_one_offset with full range of map. 116 EXPECT_EQ(left, test_ones.get_next_one_offset(0)); 117 EXPECT_EQ(right, test_ones.get_next_one_offset(left + 1)); 118 EXPECT_EQ(BITMAP_SIZE, test_ones.get_next_one_offset(right + 1)); 119 120 // Test get_next_one_offset_inline_aligned_right with full range of map. 121 EXPECT_EQ(left, test_ones.get_next_one_offset_inline_aligned_right(0, BITMAP_SIZE)); 122 EXPECT_EQ(right, test_ones.get_next_one_offset_inline_aligned_right(left + 1, BITMAP_SIZE)); 123 EXPECT_EQ(BITMAP_SIZE, test_ones.get_next_one_offset_inline_aligned_right(right + 1, BITMAP_SIZE)); 124 125 // Test get_next_zero_offset with full range of map. 126 EXPECT_EQ(left, test_zeros.get_next_zero_offset(0)); 127 EXPECT_EQ(right, test_zeros.get_next_zero_offset(left + 1)); 128 EXPECT_EQ(BITMAP_SIZE, test_zeros.get_next_zero_offset(right + 1)); 129 130 // Check that iterate invokes the closure function on left and right values. 131 TestIteratorFn test_iteration(0, BITMAP_SIZE, left, right); 132 test_ones.iterate(&test_iteration, 0, BITMAP_SIZE); 133 134 // Test searches with various start and end ranges. 135 for (size_t c_start = 0; c_start < search_nchunks; ++c_start) { 136 for (size_t o_start = 0; o_start < search_noffsets; ++o_start) { 137 idx_t start = c_start * search_chunk_size + search_offsets[o_start]; 138 // Terminate start iteration if start is more than two full 139 // chunks beyond left. There isn't anything new to learn by 140 // continuing the iteration, and this noticably reduces the 141 // time to run the test. 142 if (left + 2 * search_chunk_size < start) { 143 c_start = search_nchunks; // Set to limit to terminate iteration. 144 break; 145 } 146 147 for (size_t c_end = c_start; c_end < search_nchunks; ++c_end) { 148 for (size_t o_end = (c_start == c_end) ? o_start : 0; 149 o_end < search_noffsets; 150 ++o_end) { 151 idx_t end = c_end * search_chunk_size + search_offsets[o_end]; 152 // Similarly to start and left, terminate end iteration if 153 // end is more than two full chunks beyond right. 154 if (right + 2 * search_chunk_size < end) { 155 c_end = search_nchunks; // Set to limit to terminate iteration. 156 break; 157 } 158 // Skip this chunk if right is much larger than max(left, start) 159 // and this chunk is one of many similar chunks in between, 160 // again to reduce testing time. 161 if (MAX2(start, left) + 2 * search_chunk_size < end) { 162 if (end + 2 * search_chunk_size < right) { 163 break; 164 } 165 } 166 167 bool aligned_right = search_offsets[o_end] == 0; 168 ASSERT_LE(start, end); // test bug if fail 169 ASSERT_LT(end, BITMAP_SIZE); // test bug if fail 170 171 idx_t expected = compute_expected(start, end, left, right); 172 173 EXPECT_EQ(expected, test_ones.get_next_one_offset(start, end)); 174 EXPECT_EQ(expected, test_zeros.get_next_zero_offset(start, end)); 175 if (aligned_right) { 176 EXPECT_EQ( 177 expected, 178 test_ones.get_next_one_offset_inline_aligned_right(start, end)); 179 } 180 181 idx_t start2 = MIN2(expected + 1, end); 182 idx_t expected2 = compute_expected(start2, end, left, right); 183 184 EXPECT_EQ(expected2, test_ones.get_next_one_offset(start2, end)); 185 EXPECT_EQ(expected2, test_zeros.get_next_zero_offset(start2, end)); 186 if (aligned_right) { 187 EXPECT_EQ( 188 expected2, 189 test_ones.get_next_one_offset_inline_aligned_right(start2, end)); 190 } 191 } 192 } 193 } 194 } 195 } 196 197 TEST(BitMap, search) { 198 CHeapBitMap test_ones(BITMAP_SIZE); 199 CHeapBitMap test_zeros(BITMAP_SIZE); 200 201 // test_ones is used to test searching for 1s in a region of 0s. 202 // test_zeros is used to test searching for 0s in a region of 1s. 203 test_ones.clear_range(0, test_ones.size()); 204 test_zeros.set_range(0, test_zeros.size()); 205 206 // Searching "empty" sequence should return size. 207 EXPECT_EQ(BITMAP_SIZE, test_ones.get_next_one_offset(0)); 208 EXPECT_EQ(BITMAP_SIZE, test_zeros.get_next_zero_offset(0)); 209 210 // With left being in the first or second chunk... 211 for (size_t c_left = 0; c_left < 2; ++c_left) { 212 // Right bit is in the same chunk as left, or next chunk, or far away... 213 for (size_t c_right = c_left; 214 c_right < search_nchunks; 215 (c_right == c_left + 1) ? c_right = search_nchunks - 1 : ++c_right) { 216 // For each offset within the left chunk... 217 for (size_t o_left = 0; o_left < search_noffsets; ++o_left) { 218 // left is start of left chunk + offset. 219 idx_t left = c_left * search_chunk_size + search_offsets[o_left]; 220 221 // Install the left bit. 222 test_ones.set_bit(left); 223 test_zeros.clear_bit(left); 224 EXPECT_TRUE(test_ones.at(left)); 225 EXPECT_FALSE(test_zeros.at(left)); 226 227 // For each offset within the right chunk and > left... 228 for (size_t o_right = (c_left == c_right) ? o_left + 1 : 0; 229 o_right < search_noffsets; 230 ++o_right) { 231 // right is start of right chunk + offset. 232 idx_t right = c_right * search_chunk_size + search_offsets[o_right]; 233 234 // Install the right bit. 235 test_ones.set_bit(right); 236 test_zeros.clear_bit(right); 237 EXPECT_TRUE(test_ones.at(right)); 238 EXPECT_FALSE(test_zeros.at(right)); 239 240 // Apply the test. 241 test_search_ranges(test_ones, test_zeros, left, right); 242 243 // Remove the right bit. 244 test_ones.clear_bit(right); 245 test_zeros.set_bit(right); 246 EXPECT_FALSE(test_ones.at(right)); 247 EXPECT_TRUE(test_zeros.at(right)); 248 } 249 250 // Remove the left bit. 251 test_ones.clear_bit(left); 252 test_zeros.set_bit(left); 253 EXPECT_FALSE(test_ones.at(left)); 254 EXPECT_TRUE(test_zeros.at(left)); 255 } 256 } 257 } 258 }