1 files changed, 383 insertions, 0 deletions
diff --git a/externals/breakpad/src/processor/contained_range_map_unittest.cc b/externals/breakpad/src/processor/contained_range_map_unittest.cc
new file mode 100644
index 0000000000..1d681fdfd9
--- /dev/null
+++ b/externals/breakpad/src/processor/contained_range_map_unittest.cc
@@ -0,0 +1,383 @@
+// 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;
+}