|
1 /* |
|
2 * Copyright (c) 2016, 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/copy.hpp" |
|
28 #include "utilities/debug.hpp" |
|
29 #include "utilities/globalDefinitions.hpp" |
|
30 #include <stdlib.h> |
|
31 #include "unittest.hpp" |
|
32 |
|
33 typedef BitMap::idx_t idx_t; |
|
34 typedef BitMap::bm_word_t bm_word_t; |
|
35 |
|
36 class BitMapMemory { |
|
37 private: |
|
38 idx_t _words; |
|
39 bm_word_t* _memory; |
|
40 |
|
41 public: |
|
42 BitMapMemory(idx_t bits) : |
|
43 _words(BitMap::calc_size_in_words(bits)), |
|
44 _memory(static_cast<bm_word_t*>(malloc(_words * sizeof(bm_word_t)))) |
|
45 { } |
|
46 |
|
47 ~BitMapMemory() { |
|
48 free(_memory); |
|
49 } |
|
50 |
|
51 BitMapView make_view(idx_t bits, bm_word_t value) { |
|
52 vmassert(BitMap::calc_size_in_words(bits) <= _words, "invalid request"); |
|
53 STATIC_ASSERT(sizeof(bm_word_t) == sizeof(HeapWord)); |
|
54 Copy::fill_to_aligned_words((HeapWord*)_memory, _words, value); |
|
55 return BitMapView(_memory, bits); |
|
56 } |
|
57 |
|
58 bm_word_t* memory() { return _memory; } |
|
59 }; |
|
60 |
|
61 const idx_t aligned_size = 4 * BitsPerWord; |
|
62 const idx_t unaligned_size = aligned_size - (BitsPerWord / 2); |
|
63 |
|
64 static bm_word_t make_even_bits() { |
|
65 bm_word_t result = 1; |
|
66 while (true) { |
|
67 bm_word_t next = (result << 2) | 1; |
|
68 if (next == result) { |
|
69 return result; |
|
70 } |
|
71 result = next; |
|
72 } |
|
73 } |
|
74 |
|
75 const bm_word_t even_bits = make_even_bits(); |
|
76 const bm_word_t odd_bits = ~even_bits; |
|
77 const bm_word_t one_bits = ~bm_word_t(0); |
|
78 const bm_word_t zero_bits = 0; |
|
79 |
|
80 // Scoped set a clear bit and restore to clear. |
|
81 class WithBitSet { |
|
82 private: |
|
83 BitMap& _bm; |
|
84 idx_t _index; |
|
85 |
|
86 public: |
|
87 WithBitSet(BitMap& bm, idx_t index) : _bm(bm), _index(index) { |
|
88 // Failure may indicate test bug; can't use ASSERT_xxx in constructor. |
|
89 EXPECT_FALSE(_bm.at(_index)); |
|
90 bm.set_bit(_index); |
|
91 } |
|
92 |
|
93 ~WithBitSet() { |
|
94 _bm.clear_bit(_index); |
|
95 } |
|
96 }; |
|
97 |
|
98 // Scoped clear a set bit and restore to set. |
|
99 class WithBitClear { |
|
100 private: |
|
101 BitMap& _bm; |
|
102 idx_t _index; |
|
103 |
|
104 public: |
|
105 WithBitClear(BitMap& bm, idx_t index) : _bm(bm), _index(index) { |
|
106 // Failure may indicate test bug; can't use ASSERT_xxx in constructor. |
|
107 EXPECT_TRUE(_bm.at(_index)); |
|
108 bm.clear_bit(_index); |
|
109 } |
|
110 |
|
111 ~WithBitClear() { |
|
112 _bm.set_bit(_index); |
|
113 } |
|
114 }; |
|
115 |
|
116 ////////////////////////////////////////////////////////////////////////////// |
|
117 // bool is_same(const BitMap& bits); |
|
118 |
|
119 TEST(BitMap, is_same__aligned) { |
|
120 BitMapMemory mx(aligned_size); |
|
121 BitMapMemory my(aligned_size); |
|
122 |
|
123 BitMapView x = mx.make_view(aligned_size, even_bits); |
|
124 BitMapView y = my.make_view(aligned_size, even_bits); |
|
125 EXPECT_TRUE(x.is_same(y)); |
|
126 |
|
127 WithBitClear wbc(x, aligned_size / 2); |
|
128 EXPECT_FALSE(x.is_same(y)); |
|
129 } |
|
130 |
|
131 TEST(BitMap, is_same__unaligned) { |
|
132 BitMapMemory mx(aligned_size); |
|
133 BitMapMemory my(aligned_size); |
|
134 |
|
135 BitMapView x = mx.make_view(unaligned_size, even_bits); |
|
136 BitMapView y = my.make_view(unaligned_size, even_bits); |
|
137 |
|
138 // Check that a difference beyond the end of x/y doesn't count. |
|
139 { |
|
140 BitMapView aligned = BitMapView(mx.memory(), aligned_size); |
|
141 const idx_t index = aligned_size - 2; |
|
142 STATIC_ASSERT(unaligned_size <= index); |
|
143 |
|
144 WithBitClear wbc(aligned, index); |
|
145 EXPECT_TRUE(x.is_same(y)); |
|
146 } |
|
147 |
|
148 // Check that a difference in the final partial word does count. |
|
149 { |
|
150 idx_t index = unaligned_size - 2; |
|
151 ASSERT_LE(BitMap::word_align_down(unaligned_size), index); |
|
152 |
|
153 WithBitClear wbc(y, index); |
|
154 EXPECT_FALSE(x.is_same(y)); |
|
155 } |
|
156 } |
|
157 |
|
158 ////////////////////////////////////////////////////////////////////////////// |
|
159 // bool is_full(); |
|
160 // bool is_empty(); |
|
161 |
|
162 TEST(BitMap, is_full_or_empty__aligned) { |
|
163 BitMapMemory mx(aligned_size); |
|
164 |
|
165 { |
|
166 BitMapView x = mx.make_view(aligned_size, even_bits); |
|
167 EXPECT_FALSE(x.is_full()); |
|
168 EXPECT_FALSE(x.is_empty()); |
|
169 } |
|
170 |
|
171 { |
|
172 BitMapView x = mx.make_view(aligned_size, zero_bits); |
|
173 EXPECT_FALSE(x.is_full()); |
|
174 EXPECT_TRUE(x.is_empty()); |
|
175 } |
|
176 |
|
177 { |
|
178 BitMapView x = mx.make_view(aligned_size, one_bits); |
|
179 EXPECT_TRUE(x.is_full()); |
|
180 EXPECT_FALSE(x.is_empty()); |
|
181 } |
|
182 } |
|
183 |
|
184 TEST(BitMap, is_full__unaligned) { |
|
185 BitMapMemory mx(aligned_size); |
|
186 |
|
187 BitMapView x = mx.make_view(unaligned_size, one_bits); |
|
188 EXPECT_TRUE(x.is_full()); |
|
189 |
|
190 // Check that a missing bit beyond the end doesn't count. |
|
191 { |
|
192 idx_t index = aligned_size - 1; |
|
193 BitMapView aligned = BitMapView(mx.memory(), aligned_size); |
|
194 |
|
195 WithBitClear wcb(aligned, index); |
|
196 EXPECT_FALSE(aligned.is_full()); |
|
197 EXPECT_TRUE(x.is_full()); |
|
198 } |
|
199 |
|
200 // Check that a missing bit in the final partial word does count. |
|
201 { |
|
202 WithBitClear wcb(x, unaligned_size - 1); |
|
203 EXPECT_FALSE(x.is_full()); |
|
204 } |
|
205 } |
|
206 |
|
207 TEST(BitMap, is_empty__unaligned) { |
|
208 BitMapMemory mx(aligned_size); |
|
209 |
|
210 BitMapView x = mx.make_view(unaligned_size, zero_bits); |
|
211 EXPECT_TRUE(x.is_empty()); |
|
212 |
|
213 // Check that a set bit beyond the end doesn't count. |
|
214 { |
|
215 idx_t index = aligned_size - 1; |
|
216 BitMapView aligned = BitMapView(mx.memory(), aligned_size); |
|
217 |
|
218 WithBitSet wbs(aligned, index); |
|
219 EXPECT_FALSE(aligned.is_empty()); |
|
220 EXPECT_TRUE(x.is_empty()); |
|
221 } |
|
222 |
|
223 // Check that a set bit in the final partial word does count. |
|
224 { |
|
225 WithBitSet wbs(x, unaligned_size - 1); |
|
226 EXPECT_FALSE(x.is_empty()); |
|
227 } |
|
228 } |
|
229 |
|
230 ////////////////////////////////////////////////////////////////////////////// |
|
231 // bool contains(const BitMap& bits); |
|
232 |
|
233 TEST(BitMap, contains__aligned) { |
|
234 BitMapMemory mx(aligned_size); |
|
235 BitMapMemory my(aligned_size); |
|
236 |
|
237 BitMapView x = mx.make_view(aligned_size, even_bits); |
|
238 BitMapView y = my.make_view(aligned_size, even_bits); |
|
239 EXPECT_TRUE(x.contains(y)); |
|
240 |
|
241 WithBitClear wbc(x, aligned_size / 2); |
|
242 EXPECT_FALSE(x.contains(y)); |
|
243 } |
|
244 |
|
245 TEST(BitMap, contains__unaligned) { |
|
246 BitMapMemory mx(aligned_size); |
|
247 BitMapMemory my(aligned_size); |
|
248 |
|
249 BitMapView x = mx.make_view(unaligned_size, even_bits); |
|
250 BitMapView y = my.make_view(unaligned_size, even_bits); |
|
251 |
|
252 // Check that a missing bit beyond the end of x doesn't count. |
|
253 { |
|
254 BitMapView aligned = BitMapView(mx.memory(), aligned_size); |
|
255 const idx_t index = aligned_size - 2; |
|
256 STATIC_ASSERT(unaligned_size <= index); |
|
257 |
|
258 WithBitClear wbc(aligned, index); |
|
259 EXPECT_TRUE(x.contains(y)); |
|
260 } |
|
261 |
|
262 // Check that a missing bit in the final partial word does count. |
|
263 { |
|
264 idx_t index = unaligned_size - 2; |
|
265 ASSERT_LE(BitMap::word_align_down(unaligned_size), index); |
|
266 |
|
267 WithBitClear wbc(x, index); |
|
268 EXPECT_FALSE(x.contains(y)); |
|
269 } |
|
270 } |
|
271 |
|
272 ////////////////////////////////////////////////////////////////////////////// |
|
273 // bool intersects(const BitMap& bits); |
|
274 |
|
275 TEST(BitMap, intersects__aligned) { |
|
276 BitMapMemory mx(aligned_size); |
|
277 BitMapMemory my(aligned_size); |
|
278 |
|
279 BitMapView x = mx.make_view(aligned_size, even_bits); |
|
280 BitMapView y = my.make_view(aligned_size, zero_bits); |
|
281 EXPECT_FALSE(x.intersects(y)); |
|
282 |
|
283 ASSERT_TRUE(x.at(aligned_size / 2)); |
|
284 WithBitSet wbs(y, aligned_size / 2); |
|
285 EXPECT_TRUE(x.intersects(y)); |
|
286 } |
|
287 |
|
288 TEST(BitMap, intersects__unaligned) { |
|
289 BitMapMemory mx(aligned_size); |
|
290 BitMapMemory my(aligned_size); |
|
291 |
|
292 BitMapView x = mx.make_view(unaligned_size, even_bits); |
|
293 BitMapView y = my.make_view(unaligned_size, zero_bits); |
|
294 EXPECT_FALSE(x.intersects(y)); |
|
295 |
|
296 // Check that adding a bit beyond the end of y doesn't count. |
|
297 { |
|
298 BitMapView aligned_x = BitMapView(mx.memory(), aligned_size); |
|
299 BitMapView aligned_y = BitMapView(my.memory(), aligned_size); |
|
300 const idx_t index = aligned_size - 2; |
|
301 STATIC_ASSERT(unaligned_size <= index); |
|
302 ASSERT_TRUE(aligned_x.at(index)); |
|
303 |
|
304 WithBitSet wbs(aligned_y, index); |
|
305 EXPECT_FALSE(x.intersects(y)); |
|
306 } |
|
307 |
|
308 // Check that adding a bit in the final partial word does count. |
|
309 { |
|
310 idx_t index = unaligned_size - 2; |
|
311 ASSERT_LE(BitMap::word_align_down(unaligned_size), index); |
|
312 ASSERT_TRUE(x.at(index)); |
|
313 |
|
314 WithBitSet wbs(y, index); |
|
315 EXPECT_TRUE(x.intersects(y)); |
|
316 } |
|
317 } |
|
318 |
|
319 ////////////////////////////////////////////////////////////////////////////// |
|
320 // void set_from(const BitMap& bits); |
|
321 // void set_union(const BitMap& bits); |
|
322 // void set_difference(const BitMap& bits); |
|
323 // void set_intersection(const BitMap& bits); |
|
324 // |
|
325 // bool set_union_with_result(const BitMap& bits); |
|
326 // bool set_difference_with_result(const BitMap& bits); |
|
327 // bool set_intersection_with_result(const BitMap& bits); |
|
328 |
|
329 static void check_tail_unmodified(BitMapMemory& mem, |
|
330 idx_t bits, |
|
331 bm_word_t fill_word) { |
|
332 if (!BitMap::is_word_aligned(bits)) { |
|
333 idx_t last_word_bit_index = BitMap::word_align_down(bits); |
|
334 idx_t last_word_index = BitMap::calc_size_in_words(last_word_bit_index); |
|
335 bm_word_t last_word = mem.memory()[last_word_index]; |
|
336 idx_t shift = bits - last_word_bit_index; |
|
337 EXPECT_EQ(fill_word >> shift, last_word >> shift); |
|
338 } |
|
339 } |
|
340 |
|
341 static void check_mod_setop(void (BitMap::*f)(const BitMap&), |
|
342 idx_t bits, |
|
343 bm_word_t wx, |
|
344 bm_word_t wy, |
|
345 bm_word_t wexp) { |
|
346 BitMapMemory mx(bits); |
|
347 BitMapMemory my(bits); |
|
348 BitMapMemory mexp(bits); |
|
349 |
|
350 BitMapView x = mx.make_view(bits, wx); |
|
351 BitMapView y = my.make_view(bits, wy); |
|
352 BitMapView exp = mexp.make_view(bits, wexp); |
|
353 |
|
354 (x.*f)(y); |
|
355 |
|
356 EXPECT_TRUE(exp.is_same(x)); |
|
357 check_tail_unmodified(mx, bits, wx); |
|
358 } |
|
359 |
|
360 static void check_mod_setop_with_result(bool (BitMap::*f)(const BitMap&), |
|
361 idx_t bits, |
|
362 bm_word_t wx, |
|
363 bm_word_t wy, |
|
364 bm_word_t wexp) { |
|
365 BitMapMemory mx(bits); |
|
366 BitMapMemory my(bits); |
|
367 BitMapMemory mexp(bits); |
|
368 |
|
369 BitMapView x = mx.make_view(bits, wx); |
|
370 BitMapView y = my.make_view(bits, wy); |
|
371 BitMapView exp = mexp.make_view(bits, wexp); |
|
372 |
|
373 bool value = (x.*f)(y); |
|
374 EXPECT_EQ(value, wx != wexp); |
|
375 |
|
376 EXPECT_TRUE(exp.is_same(x)); |
|
377 check_tail_unmodified(mx, bits, wx); |
|
378 } |
|
379 |
|
380 #define CHECK_MOD_SETOP_AUX(checker, name, x, y, exp) \ |
|
381 TEST(BitMap, name ## __ ## x ## _ ## y) { \ |
|
382 checker(&BitMap::name, aligned_size, \ |
|
383 x ## _bits, y ## _bits, exp ## _bits); \ |
|
384 checker(&BitMap::name, unaligned_size, \ |
|
385 x ## _bits, y ## _bits, exp ## _bits); \ |
|
386 } |
|
387 |
|
388 #define CHECK_MOD_SETOP(name, x, y, exp) \ |
|
389 CHECK_MOD_SETOP_AUX(check_mod_setop, name, x, y, exp) |
|
390 |
|
391 #define CHECK_MOD_SETOP_WITH_RESULT(name, x, y, exp) \ |
|
392 CHECK_MOD_SETOP_AUX(check_mod_setop_with_result, name, x, y, exp) |
|
393 |
|
394 #define CHECK_MOD_SETOPS(name, x, y, exp) \ |
|
395 CHECK_MOD_SETOP(name, x, y, exp) \ |
|
396 CHECK_MOD_SETOP_WITH_RESULT(name ## _with_result, x, y, exp) |
|
397 |
|
398 CHECK_MOD_SETOP(set_from, even, even, even) |
|
399 CHECK_MOD_SETOP(set_from, even, odd, odd) |
|
400 CHECK_MOD_SETOP(set_from, even, one, one) |
|
401 CHECK_MOD_SETOP(set_from, even, zero, zero) |
|
402 |
|
403 CHECK_MOD_SETOPS(set_union, even, even, even) |
|
404 CHECK_MOD_SETOPS(set_union, even, odd, one) |
|
405 CHECK_MOD_SETOPS(set_union, even, one, one) |
|
406 CHECK_MOD_SETOPS(set_union, even, zero, even) |
|
407 |
|
408 CHECK_MOD_SETOPS(set_difference, even, even, zero) |
|
409 CHECK_MOD_SETOPS(set_difference, even, odd, even) |
|
410 CHECK_MOD_SETOPS(set_difference, even, one, zero) |
|
411 CHECK_MOD_SETOPS(set_difference, even, zero, even) |
|
412 |
|
413 CHECK_MOD_SETOPS(set_intersection, even, even, even) |
|
414 CHECK_MOD_SETOPS(set_intersection, even, odd, zero) |
|
415 CHECK_MOD_SETOPS(set_intersection, even, one, even) |
|
416 CHECK_MOD_SETOPS(set_intersection, even, zero, zero) |
|
417 |