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
32typedef BitMap::idx_t idx_t;
33typedef BitMap::bm_word_t bm_word_t;
34
35class BitMapMemory {
36private:
37  idx_t _words;
38  bm_word_t* _memory;
39
40public:
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
60const idx_t aligned_size = 4 * BitsPerWord;
61const idx_t unaligned_size = aligned_size - (BitsPerWord / 2);
62
63static 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
74const bm_word_t even_bits = make_even_bits();
75const bm_word_t odd_bits = ~even_bits;
76const bm_word_t one_bits = ~bm_word_t(0);
77const bm_word_t zero_bits = 0;
78
79// Scoped set a clear bit and restore to clear.
80class WithBitSet {
81private:
82  BitMap& _bm;
83  idx_t _index;
84
85public:
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.
98class WithBitClear {
99private:
100  BitMap& _bm;
101  idx_t _index;
102
103public:
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
118TEST(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
130TEST(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
161TEST(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
183TEST(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
206TEST(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
232TEST(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
244TEST(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
274TEST(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
287TEST(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
328static 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
340static 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
359static 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
397CHECK_MOD_SETOP(set_from, even, even, even)
398CHECK_MOD_SETOP(set_from, even, odd, odd)
399CHECK_MOD_SETOP(set_from, even, one, one)
400CHECK_MOD_SETOP(set_from, even, zero, zero)
401
402CHECK_MOD_SETOPS(set_union, even, even, even)
403CHECK_MOD_SETOPS(set_union, even, odd, one)
404CHECK_MOD_SETOPS(set_union, even, one, one)
405CHECK_MOD_SETOPS(set_union, even, zero, even)
406
407CHECK_MOD_SETOPS(set_difference, even, even, zero)
408CHECK_MOD_SETOPS(set_difference, even, odd, even)
409CHECK_MOD_SETOPS(set_difference, even, one, zero)
410CHECK_MOD_SETOPS(set_difference, even, zero, even)
411
412CHECK_MOD_SETOPS(set_intersection, even, even, even)
413CHECK_MOD_SETOPS(set_intersection, even, odd, zero)
414CHECK_MOD_SETOPS(set_intersection, even, one, even)
415CHECK_MOD_SETOPS(set_intersection, even, zero, zero)
416
417