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);
55 }
56
57 bm_word_t* memory() { return _memory; }
58 };
59
60 const idx_t aligned_size = 4 * BitsPerWord;
61 const idx_t unaligned_size = aligned_size - (BitsPerWord / 2);
62
63 static bm_word_t make_even_bits() {
64 bm_word_t result = 1;
65 while (true) {
66 bm_word_t next = (result << 2) | 1;
67 if (next == result) {
68 return result;
69 }
70 result = next;
71 }
72 }
73
74 const bm_word_t even_bits = make_even_bits();
75 const bm_word_t odd_bits = ~even_bits;
76 const bm_word_t one_bits = ~bm_word_t(0);
77 const bm_word_t zero_bits = 0;
78
79 // Scoped set a clear bit and restore to clear.
80 class WithBitSet {
81 private:
82 BitMap& _bm;
83 idx_t _index;
84
85 public:
86 WithBitSet(BitMap& bm, idx_t index) : _bm(bm), _index(index) {
87 // Failure may indicate test bug; can't use ASSERT_xxx in constructor.
88 EXPECT_FALSE(_bm.at(_index));
89 bm.set_bit(_index);
90 }
91
92 ~WithBitSet() {
93 _bm.clear_bit(_index);
94 }
95 };
96
97 // Scoped clear a set bit and restore to set.
98 class WithBitClear {
99 private:
100 BitMap& _bm;
101 idx_t _index;
102
103 public:
104 WithBitClear(BitMap& bm, idx_t index) : _bm(bm), _index(index) {
105 // Failure may indicate test bug; can't use ASSERT_xxx in constructor.
106 EXPECT_TRUE(_bm.at(_index));
107 bm.clear_bit(_index);
108 }
109
110 ~WithBitClear() {
111 _bm.set_bit(_index);
112 }
113 };
114
115 //////////////////////////////////////////////////////////////////////////////
116 // bool is_same(const BitMap& bits);
117
118 TEST(BitMap, is_same__aligned) {
119 BitMapMemory mx(aligned_size);
120 BitMapMemory my(aligned_size);
121
122 BitMapView x = mx.make_view(aligned_size, even_bits);
123 BitMapView y = my.make_view(aligned_size, even_bits);
124 EXPECT_TRUE(x.is_same(y));
125
126 WithBitClear wbc(x, aligned_size / 2);
127 EXPECT_FALSE(x.is_same(y));
128 }
129
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 {
171 BitMapView x = mx.make_view(aligned_size, zero_bits);
172 EXPECT_FALSE(x.is_full());
173 EXPECT_TRUE(x.is_empty());
174 }
175
176 {
177 BitMapView x = mx.make_view(aligned_size, one_bits);
178 EXPECT_TRUE(x.is_full());
179 EXPECT_FALSE(x.is_empty());
180 }
181 }
182
183 TEST(BitMap, is_full__unaligned) {
184 BitMapMemory mx(aligned_size);
185
186 BitMapView x = mx.make_view(unaligned_size, one_bits);
187 EXPECT_TRUE(x.is_full());
188
189 // Check that a missing bit beyond the end doesn't count.
190 {
191 idx_t index = aligned_size - 1;
192 BitMapView aligned = BitMapView(mx.memory(), aligned_size);
193
194 WithBitClear wcb(aligned, index);
195 EXPECT_FALSE(aligned.is_full());
196 EXPECT_TRUE(x.is_full());
197 }
198
199 // Check that a missing bit in the final partial word does count.
200 {
201 WithBitClear wcb(x, unaligned_size - 1);
202 EXPECT_FALSE(x.is_full());
203 }
204 }
205
206 TEST(BitMap, is_empty__unaligned) {
207 BitMapMemory mx(aligned_size);
208
209 BitMapView x = mx.make_view(unaligned_size, zero_bits);
210 EXPECT_TRUE(x.is_empty());
211
212 // Check that a set bit beyond the end doesn't count.
213 {
214 idx_t index = aligned_size - 1;
215 BitMapView aligned = BitMapView(mx.memory(), aligned_size);
216
217 WithBitSet wbs(aligned, index);
218 EXPECT_FALSE(aligned.is_empty());
219 EXPECT_TRUE(x.is_empty());
220 }
221
222 // Check that a set bit in the final partial word does count.
223 {
224 WithBitSet wbs(x, unaligned_size - 1);
225 EXPECT_FALSE(x.is_empty());
226 }
227 }
228
229 //////////////////////////////////////////////////////////////////////////////
230 // bool contains(const BitMap& bits);
231
232 TEST(BitMap, contains__aligned) {
233 BitMapMemory mx(aligned_size);
234 BitMapMemory my(aligned_size);
235
236 BitMapView x = mx.make_view(aligned_size, even_bits);
237 BitMapView y = my.make_view(aligned_size, even_bits);
238 EXPECT_TRUE(x.contains(y));
239
240 WithBitClear wbc(x, aligned_size / 2);
241 EXPECT_FALSE(x.contains(y));
242 }
243
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));
285 }
286
287 TEST(BitMap, intersects__unaligned) {
288 BitMapMemory mx(aligned_size);
289 BitMapMemory my(aligned_size);
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
353 (x.*f)(y);
354
355 EXPECT_TRUE(exp.is_same(x));
356 check_tail_unmodified(mx, bits, wx);
357 }
358
359 static void check_mod_setop_with_result(bool (BitMap::*f)(const BitMap&),
360 idx_t bits,
361 bm_word_t wx,
362 bm_word_t wy,
363 bm_word_t wexp) {
364 BitMapMemory mx(bits);
365 BitMapMemory my(bits);
366 BitMapMemory mexp(bits);
367
368 BitMapView x = mx.make_view(bits, wx);
369 BitMapView y = my.make_view(bits, wy);
370 BitMapView exp = mexp.make_view(bits, wexp);
371
372 bool value = (x.*f)(y);
373 EXPECT_EQ(value, wx != wexp);
374
375 EXPECT_TRUE(exp.is_same(x));
376 check_tail_unmodified(mx, bits, wx);
377 }
378
379 #define CHECK_MOD_SETOP_AUX(checker, name, x, y, exp) \
380 TEST(BitMap, name ## __ ## x ## _ ## y) { \
381 checker(&BitMap::name, aligned_size, \
382 x ## _bits, y ## _bits, exp ## _bits); \
383 checker(&BitMap::name, unaligned_size, \
384 x ## _bits, y ## _bits, exp ## _bits); \
385 }
386
387 #define CHECK_MOD_SETOP(name, x, y, exp) \
388 CHECK_MOD_SETOP_AUX(check_mod_setop, name, x, y, exp)
389
390 #define CHECK_MOD_SETOP_WITH_RESULT(name, x, y, exp) \
391 CHECK_MOD_SETOP_AUX(check_mod_setop_with_result, name, x, y, exp)
392
393 #define CHECK_MOD_SETOPS(name, x, y, exp) \
394 CHECK_MOD_SETOP(name, x, y, exp) \
395 CHECK_MOD_SETOP_WITH_RESULT(name ## _with_result, x, y, exp)
396
397 CHECK_MOD_SETOP(set_from, even, even, even)
398 CHECK_MOD_SETOP(set_from, even, odd, odd)
399 CHECK_MOD_SETOP(set_from, even, one, one)
400 CHECK_MOD_SETOP(set_from, even, zero, zero)
401
402 CHECK_MOD_SETOPS(set_union, even, even, even)
403 CHECK_MOD_SETOPS(set_union, even, odd, one)
404 CHECK_MOD_SETOPS(set_union, even, one, one)
405 CHECK_MOD_SETOPS(set_union, even, zero, even)
406
407 CHECK_MOD_SETOPS(set_difference, even, even, zero)
408 CHECK_MOD_SETOPS(set_difference, even, odd, even)
409 CHECK_MOD_SETOPS(set_difference, even, one, zero)
410 CHECK_MOD_SETOPS(set_difference, even, zero, even)
411
412 CHECK_MOD_SETOPS(set_intersection, even, even, even)
413 CHECK_MOD_SETOPS(set_intersection, even, odd, zero)
414 CHECK_MOD_SETOPS(set_intersection, even, one, even)
415 CHECK_MOD_SETOPS(set_intersection, even, zero, zero)
416