test/hotspot/gtest/utilities/test_bitMap_search.cpp - platform/libcore - Git at Google

 /*
  * 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));
       }
     }
   }
 }
	/*
	* 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));
	}
	}
	}
	}