path: root/src/processor/contained_range_map_unittest.cc

// Copyright 2006 Google LLC
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//     * Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above
// copyright notice, this list of conditions and the following disclaimer
// in the documentation and/or other materials provided with the
// distribution.
//     * Neither the name of Google LLC nor the names of its
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

// contained_range_map_unittest.cc: Unit tests for ContainedRangeMap
//
// Author: Mark Mentovai

#ifdef HAVE_CONFIG_H
#include <config.h>  // Must come first
#endif

#include <stdio.h>

#include "processor/contained_range_map-inl.h"

#include "processor/logging.h"


#define ASSERT_TRUE(condition) \
  if (!(condition)) { \
    fprintf(stderr, "FAIL: %s @ %s:%d\n", #condition, __FILE__, __LINE__); \
    return false; \
  }

#define ASSERT_FALSE(condition) ASSERT_TRUE(!(condition))


namespace {


using google_breakpad::ContainedRangeMap;
// The first is the querying address, the second is the entries vector result.
using EntriesTestPair = std::pair<unsigned, std::vector<int>>;
using EntriesTestPairVec = std::vector<EntriesTestPair>;

static bool RunTestsWithRetrieveRange(
    const ContainedRangeMap<unsigned int, int>& crm,
    const int* test_data,
    unsigned int test_length) {
  // Now, do the RetrieveRange tests.  This further validates that the
  // objects were stored properly and that retrieval returns the correct
  // object.
  // If GENERATE_TEST_DATA is defined, instead of the retrieval tests, a
  // new test_data array will be printed.  Exercise caution when doing this.
  // Be sure to verify the results manually!
#ifdef GENERATE_TEST_DATA
  printf("  const int test_data[] = {\n");
#endif  // GENERATE_TEST_DATA

  for (unsigned int address = 0; address < test_length; ++address) {
    int value;
    if (!crm.RetrieveRange(address, &value))
      value = 0;

#ifndef GENERATE_TEST_DATA
    // Don't use ASSERT inside the loop because it won't show the failed
    // |address|, and the line number will always be the same.  That makes
    // it difficult to figure out which test failed.
    if (value != test_data[address]) {
      fprintf(stderr, "FAIL: retrieve %d expected %d observed %d @ %s:%d\n",
              address, test_data[address], value, __FILE__, __LINE__);
      return false;
    }
#else   // !GENERATE_TEST_DATA
    printf("    %d%c%s  // %d\n", value, address == test_high - 1 ? ' ' : ',',
           value < 10 ? " " : "", address);
#endif  // !GENERATE_TEST_DATA
  }

#ifdef GENERATE_TEST_DATA
  printf("  };\n");
#endif  // GENERATE_TEST_DATA

  return true;
}

static bool RunTestsWithRetrieveRangeVector(
    const ContainedRangeMap<unsigned int, int>& crm,
    const EntriesTestPairVec& entries_tests) {
  for (const EntriesTestPair& entries_test : entries_tests) {
    std::vector<const int*> entries;
    crm.RetrieveRanges(entries_test.first, entries);
    if (entries.size() != entries_test.second.size()) {
      fprintf(stderr,
              "FAIL: retrieving entries at address %u has size %zu "
              "expected to have size %zu "
              "@ %s: %d\n",
              entries_test.first, entries.size(), entries_test.second.size(),
              __FILE__, __LINE__);
      return false;
    }
    for (size_t i = 0; i < entries.size(); ++i) {
      if (*entries[i] != entries_test.second[i]) {
        fprintf(stderr,
                "FAIL: retrieving entries at address %u entries[%zu] is %d "
                "expected %d"
                "@ %s: %d\n",
                entries_test.first, i, *entries[i], entries_test.second[i],
                __FILE__, __LINE__);
        return false;
      }
    }
  }
  return true;
}

static bool RunTestsWithNoEqualRange() {
  ContainedRangeMap<unsigned int, int> crm;

  // First, do the StoreRange tests.  This validates the containment
  // rules.
  ASSERT_TRUE (crm.StoreRange(10, 10,  1));
  ASSERT_FALSE(crm.StoreRange(10, 10,  2));  // exactly equal to 1
  ASSERT_FALSE(crm.StoreRange(11, 10,  3));  // begins inside 1 and extends up
  ASSERT_FALSE(crm.StoreRange( 9, 10,  4));  // begins below 1 and ends inside
  ASSERT_TRUE (crm.StoreRange(11,  9,  5));  // contained by existing
  ASSERT_TRUE (crm.StoreRange(12,  7,  6));
  ASSERT_TRUE (crm.StoreRange( 9, 12,  7));  // contains existing
  ASSERT_TRUE (crm.StoreRange( 9, 13,  8));
  ASSERT_TRUE (crm.StoreRange( 8, 14,  9));
  ASSERT_TRUE (crm.StoreRange(30,  3, 10));
  ASSERT_TRUE (crm.StoreRange(33,  3, 11));
  ASSERT_TRUE (crm.StoreRange(30,  6, 12));  // storable but totally masked
  ASSERT_TRUE (crm.StoreRange(40,  8, 13));  // will be totally masked
  ASSERT_TRUE (crm.StoreRange(40,  4, 14));
  ASSERT_TRUE (crm.StoreRange(44,  4, 15));
  ASSERT_FALSE(crm.StoreRange(32, 10, 16));  // begins in #10, ends in #14
  ASSERT_FALSE(crm.StoreRange(50,  0, 17));  // zero length
  ASSERT_TRUE (crm.StoreRange(50, 10, 18));
  ASSERT_TRUE (crm.StoreRange(50,  1, 19));
  ASSERT_TRUE (crm.StoreRange(59,  1, 20));
  ASSERT_TRUE (crm.StoreRange(60,  1, 21));
  ASSERT_TRUE (crm.StoreRange(69,  1, 22));
  ASSERT_TRUE (crm.StoreRange(60, 10, 23));
  ASSERT_TRUE (crm.StoreRange(68,  1, 24));
  ASSERT_TRUE (crm.StoreRange(61,  1, 25));
  ASSERT_TRUE (crm.StoreRange(61,  8, 26));
  ASSERT_FALSE(crm.StoreRange(59,  9, 27));
  ASSERT_FALSE(crm.StoreRange(59, 10, 28));
  ASSERT_FALSE(crm.StoreRange(59, 11, 29));
  ASSERT_TRUE (crm.StoreRange(70, 10, 30));
  ASSERT_TRUE (crm.StoreRange(74,  2, 31));
  ASSERT_TRUE (crm.StoreRange(77,  2, 32));
  ASSERT_FALSE(crm.StoreRange(72,  6, 33));
  ASSERT_TRUE (crm.StoreRange(80,  3, 34));
  ASSERT_TRUE (crm.StoreRange(81,  1, 35));
  ASSERT_TRUE (crm.StoreRange(82,  1, 36));
  ASSERT_TRUE (crm.StoreRange(83,  3, 37));
  ASSERT_TRUE (crm.StoreRange(84,  1, 38));
  ASSERT_TRUE (crm.StoreRange(83,  1, 39));
  ASSERT_TRUE (crm.StoreRange(86,  5, 40));
  ASSERT_TRUE (crm.StoreRange(88,  1, 41));
  ASSERT_TRUE (crm.StoreRange(90,  1, 42));
  ASSERT_TRUE (crm.StoreRange(86,  1, 43));
  ASSERT_TRUE (crm.StoreRange(87,  1, 44));
  ASSERT_TRUE (crm.StoreRange(89,  1, 45));
  ASSERT_TRUE (crm.StoreRange(87,  4, 46));
  ASSERT_TRUE (crm.StoreRange(87,  3, 47));
  ASSERT_FALSE(crm.StoreRange(86,  2, 48));

  // Each element in test_data contains the expected result when calling
  // RetrieveRange on an address.
  const int test_data[] = {
    0,   // 0
    0,   // 1
    0,   // 2
    0,   // 3
    0,   // 4
    0,   // 5
    0,   // 6
    0,   // 7
    9,   // 8
    7,   // 9
    1,   // 10
    5,   // 11
    6,   // 12
    6,   // 13
    6,   // 14
    6,   // 15
    6,   // 16
    6,   // 17
    6,   // 18
    5,   // 19
    7,   // 20
    8,   // 21
    0,   // 22
    0,   // 23
    0,   // 24
    0,   // 25
    0,   // 26
    0,   // 27
    0,   // 28
    0,   // 29
    10,  // 30
    10,  // 31
    10,  // 32
    11,  // 33
    11,  // 34
    11,  // 35
    0,   // 36
    0,   // 37
    0,   // 38
    0,   // 39
    14,  // 40
    14,  // 41
    14,  // 42
    14,  // 43
    15,  // 44
    15,  // 45
    15,  // 46
    15,  // 47
    0,   // 48
    0,   // 49
    19,  // 50
    18,  // 51
    18,  // 52
    18,  // 53
    18,  // 54
    18,  // 55
    18,  // 56
    18,  // 57
    18,  // 58
    20,  // 59
    21,  // 60
    25,  // 61
    26,  // 62
    26,  // 63
    26,  // 64
    26,  // 65
    26,  // 66
    26,  // 67
    24,  // 68
    22,  // 69
    30,  // 70
    30,  // 71
    30,  // 72
    30,  // 73
    31,  // 74
    31,  // 75
    30,  // 76
    32,  // 77
    32,  // 78
    30,  // 79
    34,  // 80
    35,  // 81
    36,  // 82
    39,  // 83
    38,  // 84
    37,  // 85
    43,  // 86
    44,  // 87
    41,  // 88
    45,  // 89
    42,  // 90
    0,   // 91
    0,   // 92
    0,   // 93
    0,   // 94
    0,   // 95
    0,   // 96
    0,   // 97
    0,   // 98
    0    // 99
  };
  unsigned int test_length = sizeof(test_data) / sizeof(int);
  return RunTestsWithRetrieveRange(crm, test_data, test_length);
}

static bool RunTestsWithEqualRange() {
  ContainedRangeMap<unsigned int, int> crm(true);

  // First, do the StoreRange tests.  This validates the containment
  // rules.
  ASSERT_TRUE (crm.StoreRange(1,  3,  1));
  ASSERT_TRUE (crm.StoreRange(1,  3,  2));  // exactly equal to 1
  ASSERT_TRUE (crm.StoreRange(1,  3,  3));  // exactly equal to 1, 2
  ASSERT_TRUE (crm.StoreRange(1,  3,  4));  // exactly equal to 1, 2, 3
  ASSERT_FALSE(crm.StoreRange(0,  3,  5));  // partial overlap.
  ASSERT_FALSE(crm.StoreRange(2,  3,  6));  // partial overlap.

  ASSERT_TRUE (crm.StoreRange(5,  3,  7));
  ASSERT_TRUE (crm.StoreRange(5,  3,  8));  // exactly equal to 7
  ASSERT_TRUE (crm.StoreRange(5,  3,  9));  // exactly equal to 7, 8
  ASSERT_TRUE (crm.StoreRange(5,  4, 10));  // encompasses 7, 8, 9
  ASSERT_TRUE (crm.StoreRange(5,  5, 11));  // encompasses 7, 8, 9, 10

  ASSERT_TRUE (crm.StoreRange(10, 3, 12));
  ASSERT_TRUE (crm.StoreRange(10, 3, 13));  // exactly equal to 12
  ASSERT_TRUE (crm.StoreRange(11, 2, 14));  // encompasses by 12
  ASSERT_TRUE (crm.StoreRange(11, 1, 15));  // encompasses by 12, 13

  ASSERT_TRUE (crm.StoreRange(14, 3, 16));
  ASSERT_TRUE (crm.StoreRange(14, 3, 17));  // exactly equal to 14
  ASSERT_TRUE (crm.StoreRange(14, 1, 18));  // encompasses by 14, 15
  ASSERT_TRUE (crm.StoreRange(14, 2, 19));  // encompasses by 14, 15 and encompasses 16
  ASSERT_TRUE (crm.StoreRange(14, 1, 20));  // exactly equal to 18
  ASSERT_TRUE (crm.StoreRange(14, 2, 21));  // exactly equal to 19

  // Each element in test_data contains the expected result when calling
  // RetrieveRange on an address.
  const int test_data[] = {
      0,   // 0
      4,   // 1
      4,   // 2
      4,   // 3
      0,   // 4
      9,   // 5
      9,   // 6
      9,   // 7
      10,  // 8
      11,   // 9
      13,  // 10
      15,  // 11
      14,  // 12
      0,   // 13
      20,  // 14
      21,  // 15
      17,  // 16
      0,   // 17
  };
  unsigned int test_length = sizeof(test_data) / sizeof(int);
  EntriesTestPairVec entries_tests = {
      {0,  {}},
      {1,  {4, 3, 2, 1}},
      {2,  {4, 3, 2, 1}},
      {3,  {4, 3, 2, 1}},
      {4,  {}},
      {5,  {9, 8, 7, 10, 11}},
      {6,  {9, 8, 7, 10, 11}},
      {7,  {9, 8, 7, 10, 11}},
      {8,  {10, 11}},
      {9,  {11}},
      {10, {13, 12}},
      {11, {15, 14, 13, 12}},
      {12, {14, 13, 12}},
      {13, {}},
      {14, {20, 18, 21, 19, 17, 16}},
      {15, {21, 19, 17, 16}},
      {16, {17, 16}},
      {17, {}},
  };
  return RunTestsWithRetrieveRange(crm, test_data, test_length) &&
         RunTestsWithRetrieveRangeVector(crm, entries_tests);
}

static bool RunTests() {
  return RunTestsWithNoEqualRange() && RunTestsWithEqualRange();
}


}  // namespace


int main(int argc, char** argv) {
  BPLOG_INIT(&argc, &argv);

  return RunTests() ? 0 : 1;
}