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 void test_search_ranges(BitMap& test_ones,
  95                                BitMap& test_zeros,
  96                                idx_t left,
  97                                idx_t right) {
  98   // Test get_next_one_offset with full range of map.
  99   EXPECT_EQ(left, test_ones.get_next_one_offset(0));
 100   EXPECT_EQ(right, test_ones.get_next_one_offset(left + 1));
 101   EXPECT_EQ(BITMAP_SIZE, test_ones.get_next_one_offset(right + 1));
 102 
 103   // Test get_next_one_offset_inline_aligned_right with full range of map.
 104   EXPECT_EQ(left, test_ones.get_next_one_offset_inline_aligned_right(0, BITMAP_SIZE));
 105   EXPECT_EQ(right, test_ones.get_next_one_offset_inline_aligned_right(left + 1, BITMAP_SIZE));
 106   EXPECT_EQ(BITMAP_SIZE, test_ones.get_next_one_offset_inline_aligned_right(right + 1, BITMAP_SIZE));
 107 
 108   // Test get_next_zero_offset with full range of map.
 109   EXPECT_EQ(left, test_zeros.get_next_zero_offset(0));
 110   EXPECT_EQ(right, test_zeros.get_next_zero_offset(left + 1));
 111   EXPECT_EQ(BITMAP_SIZE, test_zeros.get_next_zero_offset(right + 1));
 112 
 113   // Check that iterate invokes the closure function on left and right values.
 114   TestIteratorFn test_iteration(0, BITMAP_SIZE, left, right);
 115   test_ones.iterate(&test_iteration, 0, BITMAP_SIZE);
 116 
 117   // Test searches with various start and end ranges.
 118   for (size_t c_start = 0; c_start < search_nchunks; ++c_start) {
 119     for (size_t o_start = 0; o_start < search_noffsets; ++o_start) {
 120       idx_t start = c_start * search_chunk_size + search_offsets[o_start];
 121       if (left + 2 * search_chunk_size < start) {
 122         c_start = search_nchunks;
 123         break;
 124       }
 125 
 126       for (size_t c_end = c_start; c_end < search_nchunks; ++c_end) {
 127         for (size_t o_end = (c_start == c_end) ? o_start : 0;
 128              o_end < search_noffsets;
 129              ++o_end) {
 130           idx_t end = c_end * search_chunk_size + search_offsets[o_end];
 131           if (end + 2 * search_chunk_size < right) {
 132             c_end = search_nchunks;
 133             break;
 134           }
 135 
 136           bool aligned_right = search_offsets[o_end] == 0;
 137           ASSERT_LE(start, end);       // test bug if fail
 138           ASSERT_LT(end, BITMAP_SIZE); // test bug if fail
 139 
 140           idx_t expected = left;
 141           if (start > left) expected = right;
 142           if (start > right) expected = end;
 143           if (expected > end) expected = end;
 144 
 145           EXPECT_EQ(expected, test_ones.get_next_one_offset(start, end));
 146           EXPECT_EQ(expected, test_zeros.get_next_zero_offset(start, end));
 147           if (aligned_right) {
 148             EXPECT_EQ(
 149               expected,
 150               test_ones.get_next_one_offset_inline_aligned_right(start, end));
 151           }
 152 
 153           idx_t start2 = expected + 1;
 154           if (start2 > end) start2 = end;
 155           expected = right;
 156           if (start2 > right) expected = end;
 157           if (expected > end) expected = end;
 158 
 159           EXPECT_EQ(expected, test_ones.get_next_one_offset(start2, end));
 160           EXPECT_EQ(expected, test_zeros.get_next_zero_offset(start2, end));
 161           if (aligned_right) {
 162             EXPECT_EQ(
 163               expected,
 164               test_ones.get_next_one_offset_inline_aligned_right(start2, end));
 165           }
 166         }
 167       }
 168     }
 169   }
 170 }
 171 
 172 TEST(BitMap, search) {
 173   CHeapBitMap test_ones(BITMAP_SIZE);
 174   CHeapBitMap test_zeros(BITMAP_SIZE);
 175 
 176   // test_ones is used to test searching for 1s in a region of 0s.
 177   // test_zeros is used to test searching for 0s in a region of 1s.
 178   test_ones.clear_range(0, test_ones.size());
 179   test_zeros.set_range(0, test_zeros.size());
 180 
 181   // Searching "empty" sequence should return size.
 182   EXPECT_EQ(BITMAP_SIZE, test_ones.get_next_one_offset(0));
 183   EXPECT_EQ(BITMAP_SIZE, test_zeros.get_next_zero_offset(0));
 184 
 185   // With left being in the first or second chunk...
 186   for (size_t c_left = 0; c_left < 2; ++c_left) {
 187     // Right bit is in the same chunk as left, or next chunk, or far away...
 188     for (size_t c_right = c_left;
 189          c_right < search_nchunks;
 190          (c_right == c_left + 1) ? c_right = search_nchunks - 1 : ++c_right) {
 191       // For each offset within the left chunk...
 192       for (size_t o_left = 0; o_left < search_noffsets; ++o_left) {
 193         // left is start of left chunk + offset.
 194         idx_t left = c_left * search_chunk_size + search_offsets[o_left];
 195 
 196         // Install the left bit.
 197         test_ones.set_bit(left);
 198         test_zeros.clear_bit(left);
 199         EXPECT_TRUE(test_ones.at(left));
 200         EXPECT_FALSE(test_zeros.at(left));
 201 
 202         // For each offset within the right chunk and > left...
 203         for (size_t o_right = (c_left == c_right) ? o_left + 1 : 0;
 204              o_right < search_noffsets;
 205              ++o_right) {
 206           // right is start of right chunk + offset.
 207           idx_t right = c_right * search_chunk_size + search_offsets[o_right];
 208 
 209           // Install the right bit.
 210           test_ones.set_bit(right);
 211           test_zeros.clear_bit(right);
 212           EXPECT_TRUE(test_ones.at(right));
 213           EXPECT_FALSE(test_zeros.at(right));
 214 
 215           // Apply the test.
 216           test_search_ranges(test_ones, test_zeros, left, right);
 217 
 218           // Remove the right bit.
 219           test_ones.clear_bit(right);
 220           test_zeros.set_bit(right);
 221           EXPECT_FALSE(test_ones.at(right));
 222           EXPECT_TRUE(test_zeros.at(right));
 223         }
 224 
 225         // Remove the left bit.
 226         test_ones.clear_bit(left);
 227         test_zeros.set_bit(left);
 228         EXPECT_FALSE(test_ones.at(left));
 229         EXPECT_TRUE(test_zeros.at(left));
 230       }
 231     }
 232   }
 233 }