aboutsummaryrefslogtreecommitdiff
path: root/externals/breakpad/src/processor/static_map_unittest.cc
diff options
context:
space:
mode:
authorDawid Potocki <dawid@dawidpotocki.com>2024-03-05 14:09:27 +1300
committerDawid Potocki <dawid@dawidpotocki.com>2024-03-05 20:34:15 +1300
commit063e15900bda8453fb0fc6751e78d064501ccbae (patch)
treea4cd5f01dbca33a262333aff10e1e035217a30c8 /externals/breakpad/src/processor/static_map_unittest.cc
parent537296095ab24eddcb196b5ef98004f91de9c8c2 (diff)
Replace broken submodules with vendored source codeHEADpatched
Diffstat (limited to 'externals/breakpad/src/processor/static_map_unittest.cc')
-rw-r--r--externals/breakpad/src/processor/static_map_unittest.cc389
1 files changed, 389 insertions, 0 deletions
diff --git a/externals/breakpad/src/processor/static_map_unittest.cc b/externals/breakpad/src/processor/static_map_unittest.cc
new file mode 100644
index 0000000000..67b201b63d
--- /dev/null
+++ b/externals/breakpad/src/processor/static_map_unittest.cc
@@ -0,0 +1,389 @@
+// Copyright 2010 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.
+
+// static_map_unittest.cc: Unit tests for StaticMap.
+//
+// Author: Siyang Xie (lambxsy@google.com)
+
+#ifdef HAVE_CONFIG_H
+#include <config.h> // Must come first
+#endif
+
+#include <climits>
+#include <map>
+
+#include "breakpad_googletest_includes.h"
+#include "processor/static_map-inl.h"
+
+
+typedef int ValueType;
+typedef int KeyType;
+typedef google_breakpad::StaticMap< KeyType, ValueType > TestMap;
+typedef std::map< KeyType, ValueType > StdMap;
+
+template<typename Key, typename Value>
+class SimpleMapSerializer {
+ public:
+ static char* Serialize(const std::map<Key, Value>& stdmap,
+ unsigned int* size = NULL) {
+ unsigned int size_per_node =
+ sizeof(uint32_t) + sizeof(Key) + sizeof(Value);
+ unsigned int memsize = sizeof(int32_t) + size_per_node * stdmap.size();
+ if (size) *size = memsize;
+
+ // Allocate memory for serialized data:
+ char* mem = reinterpret_cast<char*>(operator new(memsize));
+ char* address = mem;
+
+ // Writer the number of nodes:
+ new (address) uint32_t(static_cast<uint32_t>(stdmap.size()));
+ address += sizeof(uint32_t);
+
+ // Nodes' offset:
+ uint32_t* offsets = reinterpret_cast<uint32_t*>(address);
+ address += sizeof(uint32_t) * stdmap.size();
+
+ // Keys:
+ Key* keys = reinterpret_cast<Key*>(address);
+ address += sizeof(Key) * stdmap.size();
+
+ // Traversing map:
+ typename std::map<Key, Value>::const_iterator iter = stdmap.begin();
+ for (int index = 0; iter != stdmap.end(); ++iter, ++index) {
+ offsets[index] = static_cast<unsigned int>(address - mem);
+ keys[index] = iter->first;
+ new (address) Value(iter->second);
+ address += sizeof(Value);
+ }
+ return mem;
+ }
+};
+
+
+class TestInvalidMap : public ::testing::Test {
+ protected:
+ void SetUp() {
+ memset(data, 0, kMemorySize);
+ }
+
+ // 40 Bytes memory can hold a StaticMap with up to 3 nodes.
+ static const int kMemorySize = 40;
+ char data[kMemorySize];
+ TestMap test_map;
+};
+
+TEST_F(TestInvalidMap, TestNegativeNumberNodes) {
+ memset(data, 0xff, sizeof(uint32_t)); // Set the number of nodes = -1
+ test_map = TestMap(data);
+ ASSERT_FALSE(test_map.ValidateInMemoryStructure());
+}
+
+TEST_F(TestInvalidMap, TestWrongOffsets) {
+ uint32_t* header = reinterpret_cast<uint32_t*>(data);
+ const uint32_t kNumNodes = 2;
+ const uint32_t kHeaderOffset =
+ sizeof(uint32_t) + kNumNodes * (sizeof(uint32_t) + sizeof(KeyType));
+
+ header[0] = kNumNodes;
+ header[1] = kHeaderOffset + 3; // Wrong offset for first node
+ test_map = TestMap(data);
+ ASSERT_FALSE(test_map.ValidateInMemoryStructure());
+
+ header[1] = kHeaderOffset; // Correct offset for first node
+ header[2] = kHeaderOffset - 1; // Wrong offset for second node
+ test_map = TestMap(data);
+ ASSERT_FALSE(test_map.ValidateInMemoryStructure());
+}
+
+TEST_F(TestInvalidMap, TestUnSortedKeys) {
+ uint32_t* header = reinterpret_cast<uint32_t*>(data);
+ const uint32_t kNumNodes = 2;
+ const uint32_t kHeaderOffset =
+ sizeof(uint32_t) + kNumNodes * (sizeof(uint32_t) + sizeof(KeyType));
+ header[0] = kNumNodes;
+ header[1] = kHeaderOffset;
+ header[2] = kHeaderOffset + sizeof(ValueType);
+
+ KeyType* keys = reinterpret_cast<KeyType*>(
+ data + (kNumNodes + 1) * sizeof(uint32_t));
+ // Set keys in non-increasing order.
+ keys[0] = 10;
+ keys[1] = 7;
+ test_map = TestMap(data);
+ ASSERT_FALSE(test_map.ValidateInMemoryStructure());
+}
+
+
+class TestValidMap : public ::testing::Test {
+ protected:
+ void SetUp() {
+ int testcase = 0;
+
+ // Empty map.
+ map_data[testcase] =
+ serializer.Serialize(std_map[testcase], &size[testcase]);
+ test_map[testcase] = TestMap(map_data[testcase]);
+ ++testcase;
+
+ // Single element.
+ std_map[testcase].insert(std::make_pair(2, 8));
+ map_data[testcase] =
+ serializer.Serialize(std_map[testcase], &size[testcase]);
+ test_map[testcase] = TestMap(map_data[testcase]);
+ ++testcase;
+
+ // 100 elements.
+ for (int i = 0; i < 100; ++i)
+ std_map[testcase].insert(std::make_pair(i, 2 * i));
+ map_data[testcase] =
+ serializer.Serialize(std_map[testcase], &size[testcase]);
+ test_map[testcase] = TestMap(map_data[testcase]);
+ ++testcase;
+
+ // 1000 random elements.
+ for (int i = 0; i < 1000; ++i)
+ std_map[testcase].insert(std::make_pair(rand(), rand()));
+ map_data[testcase] =
+ serializer.Serialize(std_map[testcase], &size[testcase]);
+ test_map[testcase] = TestMap(map_data[testcase]);
+
+ // Set correct size of memory allocation for each test case.
+ unsigned int size_per_node =
+ sizeof(uint32_t) + sizeof(KeyType) + sizeof(ValueType);
+ for (testcase = 0; testcase < kNumberTestCases; ++testcase) {
+ correct_size[testcase] =
+ sizeof(uint32_t) + std_map[testcase].size() * size_per_node;
+ }
+ }
+
+ void TearDown() {
+ for (int i = 0;i < kNumberTestCases; ++i)
+ ::operator delete(map_data[i]);
+ }
+
+
+ void IteratorTester(int test_case) {
+ // scan through:
+ iter_test = test_map[test_case].begin();
+ iter_std = std_map[test_case].begin();
+
+ for (; iter_test != test_map[test_case].end() &&
+ iter_std != std_map[test_case].end();
+ ++iter_test, ++iter_std) {
+ ASSERT_EQ(iter_test.GetKey(), iter_std->first);
+ ASSERT_EQ(*(iter_test.GetValuePtr()), iter_std->second);
+ }
+ ASSERT_TRUE(iter_test == test_map[test_case].end()
+ && iter_std == std_map[test_case].end());
+
+ // Boundary testcase.
+ if (!std_map[test_case].empty()) {
+ // rear boundary case:
+ iter_test = test_map[test_case].end();
+ iter_std = std_map[test_case].end();
+ --iter_std;
+ --iter_test;
+ ASSERT_EQ(iter_test.GetKey(), iter_std->first);
+ ASSERT_EQ(*(iter_test.GetValuePtr()), iter_std->second);
+
+ ++iter_test;
+ ++iter_std;
+ ASSERT_TRUE(iter_test == test_map[test_case].end());
+
+ --iter_test;
+ --iter_std;
+ ASSERT_TRUE(iter_test != test_map[test_case].end());
+ ASSERT_TRUE(iter_test == test_map[test_case].last());
+ ASSERT_EQ(iter_test.GetKey(), iter_std->first);
+ ASSERT_EQ(*(iter_test.GetValuePtr()), iter_std->second);
+
+ // front boundary case:
+ iter_test = test_map[test_case].begin();
+ --iter_test;
+ ASSERT_TRUE(iter_test == test_map[test_case].begin());
+ }
+ }
+
+ void CompareLookupResult(int test_case) {
+ bool found1 = (iter_test != test_map[test_case].end());
+ bool found2 = (iter_std != std_map[test_case].end());
+ ASSERT_EQ(found1, found2);
+
+ if (found1 && found2) {
+ ASSERT_EQ(iter_test.GetKey(), iter_std->first);
+ ASSERT_EQ(*(iter_test.GetValuePtr()), iter_std->second);
+ }
+ }
+
+ void FindTester(int test_case, const KeyType& key) {
+ iter_test = test_map[test_case].find(key);
+ iter_std = std_map[test_case].find(key);
+ CompareLookupResult(test_case);
+ }
+
+ void LowerBoundTester(int test_case, const KeyType& key) {
+ iter_test = test_map[test_case].lower_bound(key);
+ iter_std = std_map[test_case].lower_bound(key);
+ CompareLookupResult(test_case);
+ }
+
+ void UpperBoundTester(int test_case, const KeyType& key) {
+ iter_test = test_map[test_case].upper_bound(key);
+ iter_std = std_map[test_case].upper_bound(key);
+ CompareLookupResult(test_case);
+ }
+
+ void LookupTester(int test_case) {
+ StdMap::const_iterator iter;
+ // Test find():
+ for (iter = std_map[test_case].begin();
+ iter != std_map[test_case].end();
+ ++iter) {
+ FindTester(test_case, iter->first);
+ FindTester(test_case, iter->first + 1);
+ FindTester(test_case, iter->first - 1);
+ }
+ FindTester(test_case, INT_MIN);
+ FindTester(test_case, INT_MAX);
+ // random test:
+ for (int i = 0; i < rand()%5000 + 5000; ++i)
+ FindTester(test_case, rand());
+
+ // Test lower_bound():
+ for (iter = std_map[test_case].begin();
+ iter != std_map[test_case].end();
+ ++iter) {
+ LowerBoundTester(test_case, iter->first);
+ LowerBoundTester(test_case, iter->first + 1);
+ LowerBoundTester(test_case, iter->first - 1);
+ }
+ LowerBoundTester(test_case, INT_MIN);
+ LowerBoundTester(test_case, INT_MAX);
+ // random test:
+ for (int i = 0; i < rand()%5000 + 5000; ++i)
+ LowerBoundTester(test_case, rand());
+
+ // Test upper_bound():
+ for (iter = std_map[test_case].begin();
+ iter != std_map[test_case].end();
+ ++iter) {
+ UpperBoundTester(test_case, iter->first);
+ UpperBoundTester(test_case, iter->first + 1);
+ UpperBoundTester(test_case, iter->first - 1);
+ }
+ UpperBoundTester(test_case, INT_MIN);
+ UpperBoundTester(test_case, INT_MAX);
+ // random test:
+ for (int i = 0; i < rand()%5000 + 5000; ++i)
+ UpperBoundTester(test_case, rand());
+ }
+
+ static const int kNumberTestCases = 4;
+ StdMap std_map[kNumberTestCases];
+ TestMap test_map[kNumberTestCases];
+ TestMap::const_iterator iter_test;
+ StdMap::const_iterator iter_std;
+ char* map_data[kNumberTestCases];
+ unsigned int size[kNumberTestCases];
+ unsigned int correct_size[kNumberTestCases];
+ SimpleMapSerializer<KeyType, ValueType> serializer;
+};
+
+TEST_F(TestValidMap, TestEmptyMap) {
+ int test_case = 0;
+ // Assert memory size allocated during serialization is correct.
+ ASSERT_EQ(correct_size[test_case], size[test_case]);
+
+ // Sanity check of serialized data:
+ ASSERT_TRUE(test_map[test_case].ValidateInMemoryStructure());
+ ASSERT_EQ(std_map[test_case].empty(), test_map[test_case].empty());
+ ASSERT_EQ(std_map[test_case].size(), test_map[test_case].size());
+
+ // Test Iterator.
+ IteratorTester(test_case);
+
+ // Test lookup operations.
+ LookupTester(test_case);
+}
+
+TEST_F(TestValidMap, TestSingleElement) {
+ int test_case = 1;
+ // Assert memory size allocated during serialization is correct.
+ ASSERT_EQ(correct_size[test_case], size[test_case]);
+
+ // Sanity check of serialized data:
+ ASSERT_TRUE(test_map[test_case].ValidateInMemoryStructure());
+ ASSERT_EQ(std_map[test_case].empty(), test_map[test_case].empty());
+ ASSERT_EQ(std_map[test_case].size(), test_map[test_case].size());
+
+ // Test Iterator.
+ IteratorTester(test_case);
+
+ // Test lookup operations.
+ LookupTester(test_case);
+}
+
+TEST_F(TestValidMap, Test100Elements) {
+ int test_case = 2;
+ // Assert memory size allocated during serialization is correct.
+ ASSERT_EQ(correct_size[test_case], size[test_case]);
+
+ // Sanity check of serialized data:
+ ASSERT_TRUE(test_map[test_case].ValidateInMemoryStructure());
+ ASSERT_EQ(std_map[test_case].empty(), test_map[test_case].empty());
+ ASSERT_EQ(std_map[test_case].size(), test_map[test_case].size());
+
+ // Test Iterator.
+ IteratorTester(test_case);
+
+ // Test lookup operations.
+ LookupTester(test_case);
+}
+
+TEST_F(TestValidMap, Test1000RandomElements) {
+ int test_case = 3;
+ // Assert memory size allocated during serialization is correct.
+ ASSERT_EQ(correct_size[test_case], size[test_case]);
+
+ // Sanity check of serialized data:
+ ASSERT_TRUE(test_map[test_case].ValidateInMemoryStructure());
+ ASSERT_EQ(std_map[test_case].empty(), test_map[test_case].empty());
+ ASSERT_EQ(std_map[test_case].size(), test_map[test_case].size());
+
+ // Test Iterator.
+ IteratorTester(test_case);
+
+ // Test lookup operations.
+ LookupTester(test_case);
+}
+
+int main(int argc, char *argv[]) {
+ ::testing::InitGoogleTest(&argc, argv);
+
+ return RUN_ALL_TESTS();
+}
generated by cgit v1.2.3-70-g09d2 (git 2.49.0) at 2025-04-14 03:30:44 +0000