1 /*

     2  * Copyright (c) 2017, 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/debug.hpp"

    28 #include "utilities/globalDefinitions.hpp"

    29 #include "unittest.hpp"

    30 

    31 typedef BitMap::idx_t idx_t;

    32 typedef BitMap::bm_word_t bm_word_t;

    33 

    34 static const idx_t BITMAP_SIZE = 1024;

    35 

    36 static const size_t search_chunk_size = 64;

    37 

    38 // Entries must be monotonically increasing.

    39 // Maximum entry must be < search_chunk_size.

    40 // Cluster values around possible word-size boundaries.

    41 static const size_t search_offsets[] =

    42   { 0, 1, 2, 29, 30, 31, 32, 33, 34, 60, 62, 63 };

    43 

    44 static const size_t search_noffsets = ARRAY_SIZE(search_offsets);

    45 

    46 static const size_t search_nchunks = BITMAP_SIZE / search_chunk_size;

    47 STATIC_ASSERT(search_nchunks * search_chunk_size == BITMAP_SIZE);

    48 

    49 namespace {

    50 class TestIteratorFn : public BitMapClosure {

    51 public:

    52   TestIteratorFn(size_t start, size_t end, size_t left, size_t right);

    53   virtual bool do_bit(size_t offset);

    54 

    55 private:

    56   size_t _entries[2];

    57   size_t _index;

    58   size_t _count;

    59   size_t _start;

    60   size_t _end;

    61   size_t _left;

    62   size_t _right;

    63 

    64   void do_bit_aux(size_t offset);

    65 

    66 };

    67 } // anonymous namespace

    68 

    69 TestIteratorFn::TestIteratorFn(size_t start, size_t end,

    70                                size_t left, size_t right) :

    71   _index(0), _count(0), _start(start), _end(end), _left(left), _right(right)

    72 {

    73   if ((_start <= _left) && (_left < _end)) {

    74     _entries[_count++] = _left;

    75   }

    76   if ((_start <= _right) && (_right < _end)) {

    77     _entries[_count++] = _right;

    78   }

    79 }

    80 

    81 void TestIteratorFn::do_bit_aux(size_t offset) {

    82   EXPECT_LT(_index, _count);

    83   if (_index < _count) {

    84     EXPECT_EQ(_entries[_index], offset);

    85     _index += 1;

    86   }

    87 }

    88 

    89 bool TestIteratorFn::do_bit(size_t offset) {

    90   do_bit_aux(offset);

    91   return true;

    92 }

    93 

    94 static idx_t compute_expected(idx_t search_start,

    95                               idx_t search_end,

    96                               idx_t left_bit,

    97                               idx_t right_bit) {

    98   idx_t expected = search_end;

    99   if (search_start <= left_bit) {

   100     if (left_bit < search_end) {

   101       expected = left_bit;

   102     }

   103   } else if (search_start <= right_bit) {

   104     if (right_bit < search_end) {

   105       expected = right_bit;

   106     }

   107   }

   108   return expected;

   109 }

   110 

   111 static void test_search_ranges(BitMap& test_ones,

   112                                BitMap& test_zeros,

   113                                idx_t left,

   114                                idx_t right) {

   115   // Test get_next_one_offset with full range of map.

   116   EXPECT_EQ(left, test_ones.get_next_one_offset(0));

   117   EXPECT_EQ(right, test_ones.get_next_one_offset(left + 1));

   118   EXPECT_EQ(BITMAP_SIZE, test_ones.get_next_one_offset(right + 1));

   119 

   120   // Test get_next_one_offset_aligned_right with full range of map.

   121   EXPECT_EQ(left, test_ones.get_next_one_offset_aligned_right(0, BITMAP_SIZE));

   122   EXPECT_EQ(right, test_ones.get_next_one_offset_aligned_right(left + 1, BITMAP_SIZE));

   123   EXPECT_EQ(BITMAP_SIZE, test_ones.get_next_one_offset_aligned_right(right + 1, BITMAP_SIZE));

   124 

   125   // Test get_next_zero_offset with full range of map.

   126   EXPECT_EQ(left, test_zeros.get_next_zero_offset(0));

   127   EXPECT_EQ(right, test_zeros.get_next_zero_offset(left + 1));

   128   EXPECT_EQ(BITMAP_SIZE, test_zeros.get_next_zero_offset(right + 1));

   129 

   130   // Check that iterate invokes the closure function on left and right values.

   131   TestIteratorFn test_iteration(0, BITMAP_SIZE, left, right);

   132   test_ones.iterate(&test_iteration, 0, BITMAP_SIZE);

   133 

   134   // Test searches with various start and end ranges.

   135   for (size_t c_start = 0; c_start < search_nchunks; ++c_start) {

   136     for (size_t o_start = 0; o_start < search_noffsets; ++o_start) {

   137       idx_t start = c_start * search_chunk_size + search_offsets[o_start];

   138       // Terminate start iteration if start is more than two full

   139       // chunks beyond left.  There isn't anything new to learn by

   140       // continuing the iteration, and this noticably reduces the

   141       // time to run the test.

   142       if (left + 2 * search_chunk_size < start) {

   143         c_start = search_nchunks; // Set to limit to terminate iteration.

   144         break;

   145       }

   146 

   147       for (size_t c_end = c_start; c_end < search_nchunks; ++c_end) {

   148         for (size_t o_end = (c_start == c_end) ? o_start : 0;

   149              o_end < search_noffsets;

   150              ++o_end) {

   151           idx_t end = c_end * search_chunk_size + search_offsets[o_end];

   152           // Similarly to start and left, terminate end iteration if

   153           // end is more than two full chunks beyond right.

   154           if (right + 2 * search_chunk_size < end) {

   155             c_end = search_nchunks; // Set to limit to terminate iteration.

   156             break;

   157           }

   158           // Skip this chunk if right is much larger than max(left, start)

   159           // and this chunk is one of many similar chunks in between,

   160           // again to reduce testing time.

   161           if (MAX2(start, left) + 2 * search_chunk_size < end) {

   162             if (end + 2 * search_chunk_size < right) {

   163               break;

   164             }

   165           }

   166 

   167           bool aligned_right = search_offsets[o_end] == 0;

   168           ASSERT_LE(start, end);       // test bug if fail

   169           ASSERT_LT(end, BITMAP_SIZE); // test bug if fail

   170 

   171           idx_t expected = compute_expected(start, end, left, right);

   172 

   173           EXPECT_EQ(expected, test_ones.get_next_one_offset(start, end));

   174           EXPECT_EQ(expected, test_zeros.get_next_zero_offset(start, end));

   175           if (aligned_right) {

   176             EXPECT_EQ(

   177               expected,

   178               test_ones.get_next_one_offset_aligned_right(start, end));

   179           }

   180 

   181           idx_t start2 = MIN2(expected + 1, end);

   182           idx_t expected2 = compute_expected(start2, end, left, right);

   183 

   184           EXPECT_EQ(expected2, test_ones.get_next_one_offset(start2, end));

   185           EXPECT_EQ(expected2, test_zeros.get_next_zero_offset(start2, end));

   186           if (aligned_right) {

   187             EXPECT_EQ(

   188               expected2,

   189               test_ones.get_next_one_offset_aligned_right(start2, end));

   190           }

   191         }

   192       }

   193     }

   194   }

   195 }

   196 

   197 TEST(BitMap, search) {

   198   CHeapBitMap test_ones(BITMAP_SIZE);

   199   CHeapBitMap test_zeros(BITMAP_SIZE);

   200 

   201   // test_ones is used to test searching for 1s in a region of 0s.

   202   // test_zeros is used to test searching for 0s in a region of 1s.

   203   test_ones.clear_range(0, test_ones.size());

   204   test_zeros.set_range(0, test_zeros.size());

   205 

   206   // Searching "empty" sequence should return size.

   207   EXPECT_EQ(BITMAP_SIZE, test_ones.get_next_one_offset(0));

   208   EXPECT_EQ(BITMAP_SIZE, test_zeros.get_next_zero_offset(0));

   209 

   210   // With left being in the first or second chunk...

   211   for (size_t c_left = 0; c_left < 2; ++c_left) {

   212     // Right bit is in the same chunk as left, or next chunk, or far away...

   213     for (size_t c_right = c_left;

   214          c_right < search_nchunks;

   215          (c_right == c_left + 1) ? c_right = search_nchunks - 1 : ++c_right) {

   216       // For each offset within the left chunk...

   217       for (size_t o_left = 0; o_left < search_noffsets; ++o_left) {

   218         // left is start of left chunk + offset.

   219         idx_t left = c_left * search_chunk_size + search_offsets[o_left];

   220 

   221         // Install the left bit.

   222         test_ones.set_bit(left);

   223         test_zeros.clear_bit(left);

   224         EXPECT_TRUE(test_ones.at(left));

   225         EXPECT_FALSE(test_zeros.at(left));

   226 

   227         // For each offset within the right chunk and > left...

   228         for (size_t o_right = (c_left == c_right) ? o_left + 1 : 0;

   229              o_right < search_noffsets;

   230              ++o_right) {

   231           // right is start of right chunk + offset.

   232           idx_t right = c_right * search_chunk_size + search_offsets[o_right];

   233 

   234           // Install the right bit.

   235           test_ones.set_bit(right);

   236           test_zeros.clear_bit(right);

   237           EXPECT_TRUE(test_ones.at(right));

   238           EXPECT_FALSE(test_zeros.at(right));

   239 

   240           // Apply the test.

   241           test_search_ranges(test_ones, test_zeros, left, right);

   242 

   243           // Remove the right bit.

   244           test_ones.clear_bit(right);

   245           test_zeros.set_bit(right);

   246           EXPECT_FALSE(test_ones.at(right));

   247           EXPECT_TRUE(test_zeros.at(right));

   248         }

   249 

   250         // Remove the left bit.

   251         test_ones.clear_bit(left);

   252         test_zeros.set_bit(left);

   253         EXPECT_FALSE(test_ones.at(left));

   254         EXPECT_TRUE(test_zeros.at(left));

   255       }

   256     }

   257   }

   258 }