test/native/utilities/test_bitMap_search.cpp

rev 12505 : [mq]: stefank_review

@@ -89,10 +89,27 @@
 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.

@@ -116,53 +133,61 @@
 
   // 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;
+        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) {
-            c_end = search_nchunks;
             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 = left;
-          if (start > left) expected = right;
-          if (start > right) expected = end;
-          if (expected > end) expected = end;
+          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_inline_aligned_right(start, end));
           }
 
-          idx_t start2 = expected + 1;
-          if (start2 > end) start2 = end;
-          expected = right;
-          if (start2 > right) expected = end;
-          if (expected > end) expected = end;
+          idx_t start2 = MIN2(expected + 1, end);
+          idx_t expected2 = compute_expected(start2, end, left, right);
 
-          EXPECT_EQ(expected, test_ones.get_next_one_offset(start2, end));
-          EXPECT_EQ(expected, test_zeros.get_next_zero_offset(start2, end));
+          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(
-              expected,
+              expected2,
               test_ones.get_next_one_offset_inline_aligned_right(start2, end));
           }
         }
       }
     }