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
31typedef BitMap::idx_t idx_t;
32typedef BitMap::bm_word_t bm_word_t;
33
34static const idx_t BITMAP_SIZE = 1024;
35
36static 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.
41static const size_t search_offsets[] =
42 { 0, 1, 2, 29, 30, 31, 32, 33, 34, 60, 62, 63 };
43
44static const size_t search_noffsets = ARRAY_SIZE(search_offsets);
45
46static const size_t search_nchunks = BITMAP_SIZE / search_chunk_size;
47STATIC_ASSERT(search_nchunks * search_chunk_size == BITMAP_SIZE);
48
49namespace {
50class TestIteratorFn : public BitMapClosure {
51public:
52 TestIteratorFn(size_t start, size_t end, size_t left, size_t right);
53 virtual bool do_bit(size_t offset);
54
55private:
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
69TestIteratorFn::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
81void 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
89bool TestIteratorFn::do_bit(size_t offset) {
90 do_bit_aux(offset);
91 return true;
92}
93
94static 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
111static 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_aligned_right with full range of map.
121 EXPECT_EQ(left, test_ones.get_next_one_offset_aligned_right(0, BITMAP_SIZE));
122 EXPECT_EQ(right, test_ones.get_next_one_offset_aligned_right(left + 1, BITMAP_SIZE));
123 EXPECT_EQ(BITMAP_SIZE, test_ones.get_next_one_offset_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_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_aligned_right(start2, end));
190 }
191 }
192 }
193 }
194 }
195}
196
197TEST(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}
259