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