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.
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.
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).
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.
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
24
#include "precompiled.hpp"
25
#include "runtime/os.hpp"
26
#include "utilities/align.hpp"
27
#include "utilities/bitMap.inline.hpp"
28
#include "utilities/copy.hpp"
29
#include "utilities/debug.hpp"
30
#include "utilities/globalDefinitions.hpp"
31
#include "unittest.hpp"
35
typedef BitMap::idx_t idx_t;
36
typedef BitMap::bm_word_t bm_word_t;
38
inline idx_t word_align_down(idx_t bit) {
39
return align_down(bit, BitsPerWord);
48
BitMapMemory(idx_t bits) :
49
_words(BitMap::calc_size_in_words(bits)),
50
_memory(static_cast<bm_word_t*>(os::malloc(_words * sizeof(bm_word_t), mtTest)))
57
BitMapView make_view(idx_t bits, bm_word_t value) {
58
vmassert(BitMap::calc_size_in_words(bits) <= _words, "invalid request");
59
STATIC_ASSERT(sizeof(bm_word_t) == sizeof(HeapWord));
60
Copy::fill_to_aligned_words((HeapWord*)_memory, _words, value);
61
return BitMapView(_memory, bits);
64
bm_word_t* memory() { return _memory; }
67
const idx_t aligned_size = 4 * BitsPerWord;
68
const idx_t unaligned_size = aligned_size - (BitsPerWord / 2);
70
static bm_word_t make_even_bits() {
73
bm_word_t next = (result << 2) | 1;
81
const bm_word_t even_bits = make_even_bits();
82
const bm_word_t odd_bits = ~even_bits;
83
const bm_word_t one_bits = ~bm_word_t(0);
84
const bm_word_t zero_bits = 0;
86
// Scoped set a clear bit and restore to clear.
93
WithBitSet(BitMap& bm, idx_t index) : _bm(bm), _index(index) {
94
// Failure may indicate test bug; can't use ASSERT_xxx in constructor.
95
EXPECT_FALSE(_bm.at(_index));
100
_bm.clear_bit(_index);
104
// Scoped clear a set bit and restore to set.
111
WithBitClear(BitMap& bm, idx_t index) : _bm(bm), _index(index) {
112
// Failure may indicate test bug; can't use ASSERT_xxx in constructor.
113
EXPECT_TRUE(_bm.at(_index));
114
bm.clear_bit(_index);
122
//////////////////////////////////////////////////////////////////////////////
123
// bool is_same(const BitMap& bits);
125
TEST(BitMap, is_same__aligned) {
126
BitMapMemory mx(aligned_size);
127
BitMapMemory my(aligned_size);
129
BitMapView x = mx.make_view(aligned_size, even_bits);
130
BitMapView y = my.make_view(aligned_size, even_bits);
131
EXPECT_TRUE(x.is_same(y));
133
WithBitClear wbc(x, aligned_size / 2);
134
EXPECT_FALSE(x.is_same(y));
137
TEST(BitMap, is_same__unaligned) {
138
BitMapMemory mx(aligned_size);
139
BitMapMemory my(aligned_size);
141
BitMapView x = mx.make_view(unaligned_size, even_bits);
142
BitMapView y = my.make_view(unaligned_size, even_bits);
144
// Check that a difference beyond the end of x/y doesn't count.
146
BitMapView aligned = BitMapView(mx.memory(), aligned_size);
147
const idx_t index = aligned_size - 2;
148
STATIC_ASSERT(unaligned_size <= index);
150
WithBitClear wbc(aligned, index);
151
EXPECT_TRUE(x.is_same(y));
154
// Check that a difference in the final partial word does count.
156
idx_t index = unaligned_size - 2;
157
ASSERT_LE(word_align_down(unaligned_size), index);
159
WithBitClear wbc(y, index);
160
EXPECT_FALSE(x.is_same(y));
164
//////////////////////////////////////////////////////////////////////////////
168
TEST(BitMap, is_full_or_empty__aligned) {
169
BitMapMemory mx(aligned_size);
172
BitMapView x = mx.make_view(aligned_size, even_bits);
173
EXPECT_FALSE(x.is_full());
174
EXPECT_FALSE(x.is_empty());
178
BitMapView x = mx.make_view(aligned_size, zero_bits);
179
EXPECT_FALSE(x.is_full());
180
EXPECT_TRUE(x.is_empty());
184
BitMapView x = mx.make_view(aligned_size, one_bits);
185
EXPECT_TRUE(x.is_full());
186
EXPECT_FALSE(x.is_empty());
190
TEST(BitMap, is_full__unaligned) {
191
BitMapMemory mx(aligned_size);
193
BitMapView x = mx.make_view(unaligned_size, one_bits);
194
EXPECT_TRUE(x.is_full());
196
// Check that a missing bit beyond the end doesn't count.
198
idx_t index = aligned_size - 1;
199
BitMapView aligned = BitMapView(mx.memory(), aligned_size);
201
WithBitClear wcb(aligned, index);
202
EXPECT_FALSE(aligned.is_full());
203
EXPECT_TRUE(x.is_full());
206
// Check that a missing bit in the final partial word does count.
208
WithBitClear wcb(x, unaligned_size - 1);
209
EXPECT_FALSE(x.is_full());
213
TEST(BitMap, is_empty__unaligned) {
214
BitMapMemory mx(aligned_size);
216
BitMapView x = mx.make_view(unaligned_size, zero_bits);
217
EXPECT_TRUE(x.is_empty());
219
// Check that a set bit beyond the end doesn't count.
221
idx_t index = aligned_size - 1;
222
BitMapView aligned = BitMapView(mx.memory(), aligned_size);
224
WithBitSet wbs(aligned, index);
225
EXPECT_FALSE(aligned.is_empty());
226
EXPECT_TRUE(x.is_empty());
229
// Check that a set bit in the final partial word does count.
231
WithBitSet wbs(x, unaligned_size - 1);
232
EXPECT_FALSE(x.is_empty());
236
//////////////////////////////////////////////////////////////////////////////
237
// bool contains(const BitMap& bits);
239
TEST(BitMap, contains__aligned) {
240
BitMapMemory mx(aligned_size);
241
BitMapMemory my(aligned_size);
243
BitMapView x = mx.make_view(aligned_size, even_bits);
244
BitMapView y = my.make_view(aligned_size, even_bits);
245
EXPECT_TRUE(x.contains(y));
247
WithBitClear wbc(x, aligned_size / 2);
248
EXPECT_FALSE(x.contains(y));
251
TEST(BitMap, contains__unaligned) {
252
BitMapMemory mx(aligned_size);
253
BitMapMemory my(aligned_size);
255
BitMapView x = mx.make_view(unaligned_size, even_bits);
256
BitMapView y = my.make_view(unaligned_size, even_bits);
258
// Check that a missing bit beyond the end of x doesn't count.
260
BitMapView aligned = BitMapView(mx.memory(), aligned_size);
261
const idx_t index = aligned_size - 2;
262
STATIC_ASSERT(unaligned_size <= index);
264
WithBitClear wbc(aligned, index);
265
EXPECT_TRUE(x.contains(y));
268
// Check that a missing bit in the final partial word does count.
270
idx_t index = unaligned_size - 2;
271
ASSERT_LE(word_align_down(unaligned_size), index);
273
WithBitClear wbc(x, index);
274
EXPECT_FALSE(x.contains(y));
278
//////////////////////////////////////////////////////////////////////////////
279
// bool intersects(const BitMap& bits);
281
TEST(BitMap, intersects__aligned) {
282
BitMapMemory mx(aligned_size);
283
BitMapMemory my(aligned_size);
285
BitMapView x = mx.make_view(aligned_size, even_bits);
286
BitMapView y = my.make_view(aligned_size, zero_bits);
287
EXPECT_FALSE(x.intersects(y));
289
ASSERT_TRUE(x.at(aligned_size / 2));
290
WithBitSet wbs(y, aligned_size / 2);
291
EXPECT_TRUE(x.intersects(y));
294
TEST(BitMap, intersects__unaligned) {
295
BitMapMemory mx(aligned_size);
296
BitMapMemory my(aligned_size);
298
BitMapView x = mx.make_view(unaligned_size, even_bits);
299
BitMapView y = my.make_view(unaligned_size, zero_bits);
300
EXPECT_FALSE(x.intersects(y));
302
// Check that adding a bit beyond the end of y doesn't count.
304
BitMapView aligned_x = BitMapView(mx.memory(), aligned_size);
305
BitMapView aligned_y = BitMapView(my.memory(), aligned_size);
306
const idx_t index = aligned_size - 2;
307
STATIC_ASSERT(unaligned_size <= index);
308
ASSERT_TRUE(aligned_x.at(index));
310
WithBitSet wbs(aligned_y, index);
311
EXPECT_FALSE(x.intersects(y));
314
// Check that adding a bit in the final partial word does count.
316
idx_t index = unaligned_size - 2;
317
ASSERT_LE(word_align_down(unaligned_size), index);
318
ASSERT_TRUE(x.at(index));
320
WithBitSet wbs(y, index);
321
EXPECT_TRUE(x.intersects(y));
325
//////////////////////////////////////////////////////////////////////////////
326
// void set_from(const BitMap& bits);
327
// void set_union(const BitMap& bits);
328
// void set_difference(const BitMap& bits);
329
// void set_intersection(const BitMap& bits);
331
// bool set_union_with_result(const BitMap& bits);
332
// bool set_difference_with_result(const BitMap& bits);
333
// bool set_intersection_with_result(const BitMap& bits);
335
static void check_tail_unmodified(BitMapMemory& mem,
337
bm_word_t fill_word) {
338
if (!is_aligned(bits, BitsPerWord)) {
339
idx_t last_word_bit_index = word_align_down(bits);
340
idx_t last_word_index = BitMap::calc_size_in_words(last_word_bit_index);
341
bm_word_t last_word = mem.memory()[last_word_index];
342
idx_t shift = bits - last_word_bit_index;
343
EXPECT_EQ(fill_word >> shift, last_word >> shift);
347
static void check_mod_setop(void (BitMap::*f)(const BitMap&),
352
BitMapMemory mx(bits);
353
BitMapMemory my(bits);
354
BitMapMemory mexp(bits);
356
BitMapView x = mx.make_view(bits, wx);
357
BitMapView y = my.make_view(bits, wy);
358
BitMapView exp = mexp.make_view(bits, wexp);
362
EXPECT_TRUE(exp.is_same(x));
363
check_tail_unmodified(mx, bits, wx);
366
static void check_mod_setop_with_result(bool (BitMap::*f)(const BitMap&),
371
BitMapMemory mx(bits);
372
BitMapMemory my(bits);
373
BitMapMemory mexp(bits);
375
BitMapView x = mx.make_view(bits, wx);
376
BitMapView y = my.make_view(bits, wy);
377
BitMapView exp = mexp.make_view(bits, wexp);
379
bool value = (x.*f)(y);
380
EXPECT_EQ(value, wx != wexp);
382
EXPECT_TRUE(exp.is_same(x));
383
check_tail_unmodified(mx, bits, wx);
386
#define CHECK_MOD_SETOP_AUX(checker, name, x, y, exp) \
387
TEST(BitMap, name ## __ ## x ## _ ## y) { \
388
checker(&BitMap::name, aligned_size, \
389
x ## _bits, y ## _bits, exp ## _bits); \
390
checker(&BitMap::name, unaligned_size, \
391
x ## _bits, y ## _bits, exp ## _bits); \
394
#define CHECK_MOD_SETOP(name, x, y, exp) \
395
CHECK_MOD_SETOP_AUX(check_mod_setop, name, x, y, exp)
397
#define CHECK_MOD_SETOP_WITH_RESULT(name, x, y, exp) \
398
CHECK_MOD_SETOP_AUX(check_mod_setop_with_result, name, x, y, exp)
400
#define CHECK_MOD_SETOPS(name, x, y, exp) \
401
CHECK_MOD_SETOP(name, x, y, exp) \
402
CHECK_MOD_SETOP_WITH_RESULT(name ## _with_result, x, y, exp)
404
CHECK_MOD_SETOP(set_from, even, even, even)
405
CHECK_MOD_SETOP(set_from, even, odd, odd)
406
CHECK_MOD_SETOP(set_from, even, one, one)
407
CHECK_MOD_SETOP(set_from, even, zero, zero)
409
CHECK_MOD_SETOPS(set_union, even, even, even)
410
CHECK_MOD_SETOPS(set_union, even, odd, one)
411
CHECK_MOD_SETOPS(set_union, even, one, one)
412
CHECK_MOD_SETOPS(set_union, even, zero, even)
414
CHECK_MOD_SETOPS(set_difference, even, even, zero)
415
CHECK_MOD_SETOPS(set_difference, even, odd, even)
416
CHECK_MOD_SETOPS(set_difference, even, one, zero)
417
CHECK_MOD_SETOPS(set_difference, even, zero, even)
419
CHECK_MOD_SETOPS(set_intersection, even, even, even)
420
CHECK_MOD_SETOPS(set_intersection, even, odd, zero)
421
CHECK_MOD_SETOPS(set_intersection, even, one, even)
422
CHECK_MOD_SETOPS(set_intersection, even, zero, zero)