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 #include "precompiled.hpp"
25 #include "utilities/bitMap.inline.hpp"
26 #include "utilities/copy.hpp"
27 #include "utilities/debug.hpp"
28 #include "utilities/globalDefinitions.hpp"
29 #include <stdlib.h>
30 #include "unittest.hpp"
31
32 typedef BitMap::idx_t idx_t;
33 typedef BitMap::bm_word_t bm_word_t;
34
35 class BitMapMemory {
36 private:
37 idx_t _words;
38 bm_word_t* _memory;
39
40 public:
41 BitMapMemory(idx_t bits) :
42 _words(BitMap::calc_size_in_words(bits)),
43 _memory(static_cast<bm_word_t*>(malloc(_words * sizeof(bm_word_t))))
44 { }
45
46 ~BitMapMemory() {
47 free(_memory);
48 }
49
50 BitMapView make_view(idx_t bits, bm_word_t value) {
51 vmassert(BitMap::calc_size_in_words(bits) <= _words, "invalid request");
52 STATIC_ASSERT(sizeof(bm_word_t) == sizeof(HeapWord));
53 Copy::fill_to_aligned_words((HeapWord*)_memory, _words, value);
54 return BitMapView(_memory, bits);
130 TEST(BitMap, is_same__unaligned) {
131 BitMapMemory mx(aligned_size);
132 BitMapMemory my(aligned_size);
133
134 BitMapView x = mx.make_view(unaligned_size, even_bits);
135 BitMapView y = my.make_view(unaligned_size, even_bits);
136
137 // Check that a difference beyond the end of x/y doesn't count.
138 {
139 BitMapView aligned = BitMapView(mx.memory(), aligned_size);
140 const idx_t index = aligned_size - 2;
141 STATIC_ASSERT(unaligned_size <= index);
142
143 WithBitClear wbc(aligned, index);
144 EXPECT_TRUE(x.is_same(y));
145 }
146
147 // Check that a difference in the final partial word does count.
148 {
149 idx_t index = unaligned_size - 2;
150 ASSERT_LE(BitMap::word_align_down(unaligned_size), index);
151
152 WithBitClear wbc(y, index);
153 EXPECT_FALSE(x.is_same(y));
154 }
155 }
156
157 //////////////////////////////////////////////////////////////////////////////
158 // bool is_full();
159 // bool is_empty();
160
161 TEST(BitMap, is_full_or_empty__aligned) {
162 BitMapMemory mx(aligned_size);
163
164 {
165 BitMapView x = mx.make_view(aligned_size, even_bits);
166 EXPECT_FALSE(x.is_full());
167 EXPECT_FALSE(x.is_empty());
168 }
169
170 {
244 TEST(BitMap, contains__unaligned) {
245 BitMapMemory mx(aligned_size);
246 BitMapMemory my(aligned_size);
247
248 BitMapView x = mx.make_view(unaligned_size, even_bits);
249 BitMapView y = my.make_view(unaligned_size, even_bits);
250
251 // Check that a missing bit beyond the end of x doesn't count.
252 {
253 BitMapView aligned = BitMapView(mx.memory(), aligned_size);
254 const idx_t index = aligned_size - 2;
255 STATIC_ASSERT(unaligned_size <= index);
256
257 WithBitClear wbc(aligned, index);
258 EXPECT_TRUE(x.contains(y));
259 }
260
261 // Check that a missing bit in the final partial word does count.
262 {
263 idx_t index = unaligned_size - 2;
264 ASSERT_LE(BitMap::word_align_down(unaligned_size), index);
265
266 WithBitClear wbc(x, index);
267 EXPECT_FALSE(x.contains(y));
268 }
269 }
270
271 //////////////////////////////////////////////////////////////////////////////
272 // bool intersects(const BitMap& bits);
273
274 TEST(BitMap, intersects__aligned) {
275 BitMapMemory mx(aligned_size);
276 BitMapMemory my(aligned_size);
277
278 BitMapView x = mx.make_view(aligned_size, even_bits);
279 BitMapView y = my.make_view(aligned_size, zero_bits);
280 EXPECT_FALSE(x.intersects(y));
281
282 ASSERT_TRUE(x.at(aligned_size / 2));
283 WithBitSet wbs(y, aligned_size / 2);
284 EXPECT_TRUE(x.intersects(y));
290
291 BitMapView x = mx.make_view(unaligned_size, even_bits);
292 BitMapView y = my.make_view(unaligned_size, zero_bits);
293 EXPECT_FALSE(x.intersects(y));
294
295 // Check that adding a bit beyond the end of y doesn't count.
296 {
297 BitMapView aligned_x = BitMapView(mx.memory(), aligned_size);
298 BitMapView aligned_y = BitMapView(my.memory(), aligned_size);
299 const idx_t index = aligned_size - 2;
300 STATIC_ASSERT(unaligned_size <= index);
301 ASSERT_TRUE(aligned_x.at(index));
302
303 WithBitSet wbs(aligned_y, index);
304 EXPECT_FALSE(x.intersects(y));
305 }
306
307 // Check that adding a bit in the final partial word does count.
308 {
309 idx_t index = unaligned_size - 2;
310 ASSERT_LE(BitMap::word_align_down(unaligned_size), index);
311 ASSERT_TRUE(x.at(index));
312
313 WithBitSet wbs(y, index);
314 EXPECT_TRUE(x.intersects(y));
315 }
316 }
317
318 //////////////////////////////////////////////////////////////////////////////
319 // void set_from(const BitMap& bits);
320 // void set_union(const BitMap& bits);
321 // void set_difference(const BitMap& bits);
322 // void set_intersection(const BitMap& bits);
323 //
324 // bool set_union_with_result(const BitMap& bits);
325 // bool set_difference_with_result(const BitMap& bits);
326 // bool set_intersection_with_result(const BitMap& bits);
327
328 static void check_tail_unmodified(BitMapMemory& mem,
329 idx_t bits,
330 bm_word_t fill_word) {
331 if (!BitMap::is_word_aligned(bits)) {
332 idx_t last_word_bit_index = BitMap::word_align_down(bits);
333 idx_t last_word_index = BitMap::calc_size_in_words(last_word_bit_index);
334 bm_word_t last_word = mem.memory()[last_word_index];
335 idx_t shift = bits - last_word_bit_index;
336 EXPECT_EQ(fill_word >> shift, last_word >> shift);
337 }
338 }
339
340 static void check_mod_setop(void (BitMap::*f)(const BitMap&),
341 idx_t bits,
342 bm_word_t wx,
343 bm_word_t wy,
344 bm_word_t wexp) {
345 BitMapMemory mx(bits);
346 BitMapMemory my(bits);
347 BitMapMemory mexp(bits);
348
349 BitMapView x = mx.make_view(bits, wx);
350 BitMapView y = my.make_view(bits, wy);
351 BitMapView exp = mexp.make_view(bits, wexp);
352
|
1 /*
2 * Copyright (c) 2016, 2019, 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 #include "precompiled.hpp"
25 #include "utilities/align.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 inline idx_t word_align_down(idx_t bit) {
37 return align_down(bit, BitsPerWord);
38 }
39
40 class BitMapMemory {
41 private:
42 idx_t _words;
43 bm_word_t* _memory;
44
45 public:
46 BitMapMemory(idx_t bits) :
47 _words(BitMap::calc_size_in_words(bits)),
48 _memory(static_cast<bm_word_t*>(malloc(_words * sizeof(bm_word_t))))
49 { }
50
51 ~BitMapMemory() {
52 free(_memory);
53 }
54
55 BitMapView make_view(idx_t bits, bm_word_t value) {
56 vmassert(BitMap::calc_size_in_words(bits) <= _words, "invalid request");
57 STATIC_ASSERT(sizeof(bm_word_t) == sizeof(HeapWord));
58 Copy::fill_to_aligned_words((HeapWord*)_memory, _words, value);
59 return BitMapView(_memory, bits);
135 TEST(BitMap, is_same__unaligned) {
136 BitMapMemory mx(aligned_size);
137 BitMapMemory my(aligned_size);
138
139 BitMapView x = mx.make_view(unaligned_size, even_bits);
140 BitMapView y = my.make_view(unaligned_size, even_bits);
141
142 // Check that a difference beyond the end of x/y doesn't count.
143 {
144 BitMapView aligned = BitMapView(mx.memory(), aligned_size);
145 const idx_t index = aligned_size - 2;
146 STATIC_ASSERT(unaligned_size <= index);
147
148 WithBitClear wbc(aligned, index);
149 EXPECT_TRUE(x.is_same(y));
150 }
151
152 // Check that a difference in the final partial word does count.
153 {
154 idx_t index = unaligned_size - 2;
155 ASSERT_LE(word_align_down(unaligned_size), index);
156
157 WithBitClear wbc(y, index);
158 EXPECT_FALSE(x.is_same(y));
159 }
160 }
161
162 //////////////////////////////////////////////////////////////////////////////
163 // bool is_full();
164 // bool is_empty();
165
166 TEST(BitMap, is_full_or_empty__aligned) {
167 BitMapMemory mx(aligned_size);
168
169 {
170 BitMapView x = mx.make_view(aligned_size, even_bits);
171 EXPECT_FALSE(x.is_full());
172 EXPECT_FALSE(x.is_empty());
173 }
174
175 {
249 TEST(BitMap, contains__unaligned) {
250 BitMapMemory mx(aligned_size);
251 BitMapMemory my(aligned_size);
252
253 BitMapView x = mx.make_view(unaligned_size, even_bits);
254 BitMapView y = my.make_view(unaligned_size, even_bits);
255
256 // Check that a missing bit beyond the end of x doesn't count.
257 {
258 BitMapView aligned = BitMapView(mx.memory(), aligned_size);
259 const idx_t index = aligned_size - 2;
260 STATIC_ASSERT(unaligned_size <= index);
261
262 WithBitClear wbc(aligned, index);
263 EXPECT_TRUE(x.contains(y));
264 }
265
266 // Check that a missing bit in the final partial word does count.
267 {
268 idx_t index = unaligned_size - 2;
269 ASSERT_LE(word_align_down(unaligned_size), index);
270
271 WithBitClear wbc(x, index);
272 EXPECT_FALSE(x.contains(y));
273 }
274 }
275
276 //////////////////////////////////////////////////////////////////////////////
277 // bool intersects(const BitMap& bits);
278
279 TEST(BitMap, intersects__aligned) {
280 BitMapMemory mx(aligned_size);
281 BitMapMemory my(aligned_size);
282
283 BitMapView x = mx.make_view(aligned_size, even_bits);
284 BitMapView y = my.make_view(aligned_size, zero_bits);
285 EXPECT_FALSE(x.intersects(y));
286
287 ASSERT_TRUE(x.at(aligned_size / 2));
288 WithBitSet wbs(y, aligned_size / 2);
289 EXPECT_TRUE(x.intersects(y));
295
296 BitMapView x = mx.make_view(unaligned_size, even_bits);
297 BitMapView y = my.make_view(unaligned_size, zero_bits);
298 EXPECT_FALSE(x.intersects(y));
299
300 // Check that adding a bit beyond the end of y doesn't count.
301 {
302 BitMapView aligned_x = BitMapView(mx.memory(), aligned_size);
303 BitMapView aligned_y = BitMapView(my.memory(), aligned_size);
304 const idx_t index = aligned_size - 2;
305 STATIC_ASSERT(unaligned_size <= index);
306 ASSERT_TRUE(aligned_x.at(index));
307
308 WithBitSet wbs(aligned_y, index);
309 EXPECT_FALSE(x.intersects(y));
310 }
311
312 // Check that adding a bit in the final partial word does count.
313 {
314 idx_t index = unaligned_size - 2;
315 ASSERT_LE(word_align_down(unaligned_size), index);
316 ASSERT_TRUE(x.at(index));
317
318 WithBitSet wbs(y, index);
319 EXPECT_TRUE(x.intersects(y));
320 }
321 }
322
323 //////////////////////////////////////////////////////////////////////////////
324 // void set_from(const BitMap& bits);
325 // void set_union(const BitMap& bits);
326 // void set_difference(const BitMap& bits);
327 // void set_intersection(const BitMap& bits);
328 //
329 // bool set_union_with_result(const BitMap& bits);
330 // bool set_difference_with_result(const BitMap& bits);
331 // bool set_intersection_with_result(const BitMap& bits);
332
333 static void check_tail_unmodified(BitMapMemory& mem,
334 idx_t bits,
335 bm_word_t fill_word) {
336 if (!is_aligned(bits, BitsPerWord)) {
337 idx_t last_word_bit_index = word_align_down(bits);
338 idx_t last_word_index = BitMap::calc_size_in_words(last_word_bit_index);
339 bm_word_t last_word = mem.memory()[last_word_index];
340 idx_t shift = bits - last_word_bit_index;
341 EXPECT_EQ(fill_word >> shift, last_word >> shift);
342 }
343 }
344
345 static void check_mod_setop(void (BitMap::*f)(const BitMap&),
346 idx_t bits,
347 bm_word_t wx,
348 bm_word_t wy,
349 bm_word_t wexp) {
350 BitMapMemory mx(bits);
351 BitMapMemory my(bits);
352 BitMapMemory mexp(bits);
353
354 BitMapView x = mx.make_view(bits, wx);
355 BitMapView y = my.make_view(bits, wy);
356 BitMapView exp = mexp.make_view(bits, wexp);
357
|