/*

 * Copyright (c) 2017, Oracle and/or its affiliates. All rights reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 *

 */

#include "precompiled.hpp"

#include "utilities/bitMap.inline.hpp"

#include "utilities/debug.hpp"

#include "utilities/globalDefinitions.hpp"

#include "unittest.hpp"

typedef BitMap::idx_t idx_t;

typedef BitMap::bm_word_t bm_word_t;

static const idx_t BITMAP_SIZE = 1024;

static const size_t search_chunk_size = 64;

// Entries must be monotonically increasing.

// Maximum entry must be < search_chunk_size.

// Cluster values around possible word-size boundaries.

static const size_t search_offsets[] =

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

static const size_t search_noffsets = ARRAY_SIZE(search_offsets);

static const size_t search_nchunks = BITMAP_SIZE / search_chunk_size;

STATIC_ASSERT(search_nchunks * search_chunk_size == BITMAP_SIZE);

namespace {

class TestIteratorFn : public BitMapClosure {

public:

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

  virtual bool do_bit(size_t offset);

private:

  size_t _entries[2];

  size_t _index;

  size_t _count;

  size_t _start;

  size_t _end;

  size_t _left;

  size_t _right;

  void do_bit_aux(size_t offset);

};

} // anonymous namespace

TestIteratorFn::TestIteratorFn(size_t start, size_t end,

                               size_t left, size_t right) :

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

{

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

    _entries[_count++] = _left;

  }

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

    _entries[_count++] = _right;

  }

}

void TestIteratorFn::do_bit_aux(size_t offset) {

  EXPECT_LT(_index, _count);

  if (_index < _count) {

    EXPECT_EQ(_entries[_index], offset);

    _index += 1;

  }

}

bool TestIteratorFn::do_bit(size_t offset) {

  do_bit_aux(offset);

  return true;

}

static idx_t compute_expected(idx_t search_start,

                              idx_t search_end,

                              idx_t left_bit,

                              idx_t right_bit) {

  idx_t expected = search_end;

  if (search_start <= left_bit) {

    if (left_bit < search_end) {

      expected = left_bit;

    }

  } else if (search_start <= right_bit) {

    if (right_bit < search_end) {

      expected = right_bit;

    }

  }

  return expected;

}

static void test_search_ranges(BitMap& test_ones,

                               BitMap& test_zeros,

                               idx_t left,

                               idx_t right) {

  // Test get_next_one_offset with full range of map.

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

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

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

  // Test get_next_one_offset_aligned_right with full range of map.

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

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

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

  // Test get_next_zero_offset with full range of map.

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

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

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

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

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

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

  // Test searches with various start and end ranges.

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

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

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

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

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

      // continuing the iteration, and this noticably reduces the

      // time to run the test.

      if (left + 2 * search_chunk_size < start) {

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

        break;

      }

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

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

             o_end < search_noffsets;

             ++o_end) {

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

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

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

          if (right + 2 * search_chunk_size < end) {

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

            break;

          }

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

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

          // again to reduce testing time.

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

            if (end + 2 * search_chunk_size < right) {

              break;

            }

          }

          bool aligned_right = search_offsets[o_end] == 0;

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

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

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

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

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

          if (aligned_right) {

            EXPECT_EQ(

              expected,

              test_ones.get_next_one_offset_aligned_right(start, end));

          }

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

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

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

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

          if (aligned_right) {

            EXPECT_EQ(

              expected2,

              test_ones.get_next_one_offset_aligned_right(start2, end));

          }

        }

      }

    }

  }

}

TEST(BitMap, search) {

  CHeapBitMap test_ones(BITMAP_SIZE);

  CHeapBitMap test_zeros(BITMAP_SIZE);

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

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

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

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

  // Searching "empty" sequence should return size.

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

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

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

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

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

    for (size_t c_right = c_left;

         c_right < search_nchunks;

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

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

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

        // left is start of left chunk + offset.

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

        // Install the left bit.

        test_ones.set_bit(left);

        test_zeros.clear_bit(left);

        EXPECT_TRUE(test_ones.at(left));

        EXPECT_FALSE(test_zeros.at(left));

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

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

             o_right < search_noffsets;

             ++o_right) {

          // right is start of right chunk + offset.

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

          // Install the right bit.

          test_ones.set_bit(right);

          test_zeros.clear_bit(right);

          EXPECT_TRUE(test_ones.at(right));

          EXPECT_FALSE(test_zeros.at(right));

          // Apply the test.

          test_search_ranges(test_ones, test_zeros, left, right);

          // Remove the right bit.

          test_ones.clear_bit(right);

          test_zeros.set_bit(right);

          EXPECT_FALSE(test_ones.at(right));

          EXPECT_TRUE(test_zeros.at(right));

        }

        // Remove the left bit.

        test_ones.clear_bit(left);

        test_zeros.set_bit(left);

        EXPECT_FALSE(test_ones.at(left));

        EXPECT_TRUE(test_zeros.at(left));

      }

    }

  }

}