diff options
Diffstat (limited to 'src/processor')
| -rw-r--r-- | src/processor/static_map-inl.h | 176 | ||||
| -rw-r--r-- | src/processor/static_map.h | 144 | ||||
| -rw-r--r-- | src/processor/static_map_iterator-inl.h | 147 | ||||
| -rw-r--r-- | src/processor/static_map_iterator.h | 112 | ||||
| -rw-r--r-- | src/processor/static_map_unittest.cc | 386 |
5 files changed, 965 insertions, 0 deletions
diff --git a/src/processor/static_map-inl.h b/src/processor/static_map-inl.h new file mode 100644 index 00000000..7727052f --- /dev/null +++ b/src/processor/static_map-inl.h @@ -0,0 +1,176 @@ +// Copyright 2010 Google Inc. All Rights Reserved. +// +// 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 Inc. 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-inl.h: StaticMap implementation. +// +// See static_map.h for documentation. +// +// Author: Siyang Xie (lambxsy@google.com) + + +#ifndef PROCESSOR_STATIC_MAP_INL_H__ +#define PROCESSOR_STATIC_MAP_INL_H__ + +#include "processor/static_map.h" +#include "processor/static_map_iterator-inl.h" +#include "processor/logging.h" + +namespace google_breakpad { + +template<typename Key, typename Value, typename Compare> +StaticMap<Key, Value, Compare>::StaticMap(const char* raw_data) + : raw_data_(raw_data), + compare_() { + // First 4 Bytes store the number of nodes. + num_nodes_ = *(reinterpret_cast<const u_int32_t*>(raw_data_)); + + offsets_ = reinterpret_cast<const u_int32_t*>( + raw_data_ + sizeof(num_nodes_)); + + keys_ = reinterpret_cast<const Key*>( + raw_data_ + (1 + num_nodes_) * sizeof(u_int32_t)); +} + +// find(), lower_bound() and upper_bound() implement binary search algorithm. +template<typename Key, typename Value, typename Compare> +StaticMapIterator<Key, Value, Compare> +StaticMap<Key, Value, Compare>::find(const Key &key) const { + int begin = 0; + int end = num_nodes_; + int middle; + int compare_result; + while (begin < end) { + middle = begin + (end - begin) / 2; + compare_result = compare_(key, GetKeyAtIndex(middle)); + if (compare_result == 0) + return IteratorAtIndex(middle); + if (compare_result < 0) { + end = middle; + } else { + begin = middle + 1; + } + } + return this->end(); +} + +template<typename Key, typename Value, typename Compare> +StaticMapIterator<Key, Value, Compare> +StaticMap<Key, Value, Compare>::lower_bound(const Key &key) const { + int begin = 0; + int end = num_nodes_; + int middle; + int comp_result; + while (begin < end) { + middle = begin + (end - begin) / 2; + comp_result = compare_(key, GetKeyAtIndex(middle)); + if (comp_result == 0) + return IteratorAtIndex(middle); + if (comp_result < 0) { + end = middle; + } else { + begin = middle + 1; + } + } + return IteratorAtIndex(begin); +} + +template<typename Key, typename Value, typename Compare> +StaticMapIterator<Key, Value, Compare> +StaticMap<Key, Value, Compare>::upper_bound(const Key &key) const { + int begin = 0; + int end = num_nodes_; + int middle; + int compare_result; + while (begin < end) { + middle = begin + (end - begin) / 2; + compare_result = compare_(key, GetKeyAtIndex(middle)); + if (compare_result == 0) + return IteratorAtIndex(middle + 1); + if (compare_result < 0) { + end = middle; + } else { + begin = middle + 1; + } + } + return IteratorAtIndex(begin); +} + +template<typename Key, typename Value, typename Compare> +bool StaticMap<Key, Value, Compare>::ValidateInMemoryStructure() const { + // check the number of nodes is non-negative: + if (!raw_data_) return false; + int32_t num_nodes = *(reinterpret_cast<const int32_t*>(raw_data_)); + if (num_nodes < 0) { + BPLOG(INFO) << "StaticMap check failed: negative number of nodes"; + return false; + } + + int node_index = 0; + if (num_nodes_) { + u_int64_t first_offset = sizeof(int32_t) * (num_nodes_ + 1) + + sizeof(Key) * num_nodes_; + // Num_nodes_ is too large. + if (first_offset > 0xffffffffUL) { + BPLOG(INFO) << "StaticMap check failed: size exceeds limit"; + return false; + } + if (offsets_[node_index] != static_cast<u_int32_t>(first_offset)) { + BPLOG(INFO) << "StaticMap check failed: first node offset is incorrect"; + return false; + } + } + + for (node_index = 1; node_index < num_nodes_; ++node_index) { + // Check offsets[i] is strictly increasing: + if (offsets_[node_index] <= offsets_[node_index - 1]) { + BPLOG(INFO) << "StaticMap check failed: node offsets non-increasing"; + return false; + } + // Check Key[i] is strictly increasing as no duplicate keys are allowed. + if (compare_(GetKeyAtIndex(node_index), + GetKeyAtIndex(node_index - 1)) <= 0) { + BPLOG(INFO) << "StaticMap check failed: node keys non-increasing"; + return false; + } + } + return true; +} + +template<typename Key, typename Value, typename Compare> +const Key StaticMap<Key, Value, Compare>::GetKeyAtIndex(int index) const { + if (index < 0 || index >= num_nodes_) { + BPLOG(ERROR) << "Key index out of range error"; + // Key type is required to be primitive type. Return 0 if index is invalid. + return 0; + } + return keys_[index]; +} + +} // namespace google_breakpad + +#endif // PROCESSOR_STATIC_MAP_INL_H__ diff --git a/src/processor/static_map.h b/src/processor/static_map.h new file mode 100644 index 00000000..023ab3a4 --- /dev/null +++ b/src/processor/static_map.h @@ -0,0 +1,144 @@ +// Copyright 2010 Google Inc. All Rights Reserved. +// +// 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 Inc. 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.h: StaticMap. +// +// StaticMap provides lookup interfaces and iterators similar as stl::map's. +// These lookup operations are purely Read-Only, thus memory +// allocation & deallocation is mostly avoided (intentionally). +// +// The chunk of memory should contain data with pre-defined pattern: +// **************** header *************** +// uint32 (4 bytes): number of nodes +// uint32 (4 bytes): address offset of node1's mapped_value +// uint32 (4 bytes): address offset of node2's mapped_value +// ... +// uint32 (4 bytes): address offset of nodeN's mapped_value +// +// ************* Key array ************ +// (X bytes): node1's key +// (X bytes): node2's key +// ... +// (X bytes): nodeN's key +// +// ************* Value array ********** +// (? bytes): node1's mapped_value +// (? bytes): node2's mapped_value +// ... +// (? bytes): nodeN's mapped_value +// +// REQUIREMENT: Key type MUST be primitive type or pointers so that: +// X = sizeof(typename Key); +// +// Note: since address offset is stored as uint32, user should keep in mind that +// StaticMap only supports up to 4GB size of memory data. + +// Author: Siyang Xie (lambxsy@google.com) + + +#ifndef PROCESSOR_STATIC_MAP_H__ +#define PROCESSOR_STATIC_MAP_H__ + +#include "processor/static_map_iterator-inl.h" + +namespace google_breakpad { + +// Default functor to compare keys. +template<typename Key> +class DefaultCompare { + public: + int operator()(const Key &k1, const Key &k2) const { + if (k1 < k2) return -1; + if (k1 == k2) return 0; + return 1; + } +}; + +template<typename Key, typename Value, typename Compare = DefaultCompare<Key> > +class StaticMap { + public: + typedef StaticMapIterator<Key, Value, Compare> iterator; + typedef StaticMapIterator<Key, Value, Compare> const_iterator; + + StaticMap() : raw_data_(0), + num_nodes_(0), + offsets_(0), + compare_() { } + + explicit StaticMap(const char* raw_data); + + inline bool empty() const { return num_nodes_ == 0; } + inline unsigned int size() const { return num_nodes_; } + + // Return iterators. + inline iterator begin() const { return IteratorAtIndex(0); } + inline iterator last() const { return IteratorAtIndex(num_nodes_ - 1); } + inline iterator end() const { return IteratorAtIndex(num_nodes_); } + inline iterator IteratorAtIndex(int index) const { + return iterator(raw_data_, index); + } + + // Lookup operations. + iterator find(const Key &k) const; + + // lower_bound(k) searches in a sorted range for the first element that has a + // key not less than the argument k. + iterator lower_bound(const Key &k) const; + + // upper_bound(k) searches in a sorted range for the first element that has a + // key greater than the argument k. + iterator upper_bound(const Key &k) const; + + // Checks if the underlying memory data conforms to the predefined pattern: + // first check the number of nodes is non-negative, + // then check both offsets and keys are strictly increasing (sorted). + bool ValidateInMemoryStructure() const; + + private: + const Key GetKeyAtIndex(int i) const; + + // Start address of a raw memory chunk with serialized data. + const char* raw_data_; + + // Number of nodes in the static map. + u_int32_t num_nodes_; + + // Array of offset addresses for stored values. + // For example: + // address_of_i-th_node_value = raw_data_ + offsets_[i] + const u_int32_t* offsets_; + + // keys_[i] = key of i_th node + const Key* keys_; + + Compare compare_; +}; + +} // namespace google_breakpad + +#endif // PROCESSOR_STATIC_MAP_H__ diff --git a/src/processor/static_map_iterator-inl.h b/src/processor/static_map_iterator-inl.h new file mode 100644 index 00000000..325046c3 --- /dev/null +++ b/src/processor/static_map_iterator-inl.h @@ -0,0 +1,147 @@ +// Copyright 2010 Google Inc. All Rights Reserved. +// +// 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 Inc. 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_iterator-inl.h: StaticMapIterator implementation. +// +// See static_map_iterator.h for documentation. +// +// Author: Siyang Xie (lambxsy@google.com) + +#ifndef PROCESSOR_STATIC_MAP_ITERATOR_INL_H__ +#define PROCESSOR_STATIC_MAP_ITERATOR_INL_H__ + +#include "processor/static_map_iterator.h" + +#include "processor/logging.h" + +namespace google_breakpad { + +template<typename Key, typename Value, typename Compare> +StaticMapIterator<Key, Value, Compare>::StaticMapIterator(const char* base, + const int &index): + index_(index), base_(base) { + // See static_map.h for documentation on + // bytes format of serialized StaticMap data. + num_nodes_ = *(reinterpret_cast<const int32_t*>(base_)); + offsets_ = reinterpret_cast<const u_int32_t*>(base_ + sizeof(num_nodes_)); + keys_ = reinterpret_cast<const Key*>( + base_ + (1 + num_nodes_) * sizeof(num_nodes_)); +} + +// Increment & Decrement operators: +template<typename Key, typename Value, typename Compare> +StaticMapIterator<Key, Value, Compare>& +StaticMapIterator<Key, Value, Compare>::operator++() { + if (!IsValid()) { + BPLOG(ERROR) << "operator++ on invalid iterator"; + return *this; + } + if (++index_ > num_nodes_) index_ = num_nodes_; + return *this; +} + +template<typename Key, typename Value, typename Compare> +StaticMapIterator<Key, Value, Compare> +StaticMapIterator<Key, Value, Compare>::operator++(int postfix_operator) { + if (!IsValid()) { + BPLOG(ERROR) << "operator++ on invalid iterator"; + return *this; + } + StaticMapIterator<Key, Value, Compare> tmp = *this; + if (++index_ > num_nodes_) index_ = num_nodes_; + return tmp; +} + +template<typename Key, typename Value, typename Compare> +StaticMapIterator<Key, Value, Compare>& +StaticMapIterator<Key, Value, Compare>::operator--() { + if (!IsValid()) { + BPLOG(ERROR) << "operator++ on invalid iterator"; + return *this; + } + + if (--index_ < 0) index_ = 0; + return *this; +} + +template<typename Key, typename Value, typename Compare> +StaticMapIterator<Key, Value, Compare> +StaticMapIterator<Key, Value, Compare>::operator--(int postfix_operator) { + if (!IsValid()) { + BPLOG(ERROR) << "operator++ on invalid iterator"; + return *this; + } + StaticMapIterator<Key, Value, Compare> tmp = *this; + + if (--index_ < 0) index_ = 0; + return tmp; +} + +template<typename Key, typename Value, typename Compare> +const Key* StaticMapIterator<Key, Value, Compare>::GetKeyPtr() const { + if (!IsValid()) { + BPLOG(ERROR) << "call GetKeyPtr() on invalid iterator"; + return NULL; + } + return &(keys_[index_]); +} + +template<typename Key, typename Value, typename Compare> +const char* StaticMapIterator<Key, Value, Compare>::GetValueRawPtr() const { + if (!IsValid()) { + BPLOG(ERROR) << "call GetValuePtr() on invalid iterator"; + return NULL; + } + return base_ + offsets_[index_]; +} + +template<typename Key, typename Value, typename Compare> +bool StaticMapIterator<Key, Value, Compare>::operator==( + const StaticMapIterator<Key, Value, Compare>& x) const { + return base_ == x.base_ && index_ == x.index_; +} + +template<typename Key, typename Value, typename Compare> +bool StaticMapIterator<Key, Value, Compare>::operator!=( + const StaticMapIterator<Key, Value, Compare>& x) const { + // Only need to compare base_ and index_. + // Other data members are auxiliary. + return base_ != x.base_ || index_ != x.index_; +} + +template<typename Key, typename Value, typename Compare> +bool StaticMapIterator<Key, Value, Compare>::IsValid() const { + if (!base_ || index_ < 0 || index_ > num_nodes_) + return false; + + return true; +} + +} // namespace google_breakpad + +#endif // PROCESSOR_STATIC_MAP_ITERATOR_INL_H__ diff --git a/src/processor/static_map_iterator.h b/src/processor/static_map_iterator.h new file mode 100644 index 00000000..8127667b --- /dev/null +++ b/src/processor/static_map_iterator.h @@ -0,0 +1,112 @@ +// Copyright 2010 Google Inc. All Rights Reserved. +// +// 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 Inc. 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_iterator.h: StaticMapIterator template class declaration. +// +// StaticMapIterator provides increment and decrement operators to iterate +// through a StaticMap map. It does not provide *, -> operators, user should +// use GetKeyPtr(), GetKey(), GetValuePtr() interfaces to retrieve data or +// pointer to data. StaticMapIterator is essentially a const_iterator. +// +// Author: Siyang Xie (lambxsy@google.com) + + +#ifndef PROCESSOR_STATIC_MAP_ITERATOR_H__ +#define PROCESSOR_STATIC_MAP_ITERATOR_H__ + +#include <sys/types.h> + +namespace google_breakpad { + +// Forward declaration. +template<typename Key, typename Value, typename Compare> class StaticMap; + +// StaticMapIterator does not support operator*() or operator->(), +// User should use GetKey(), GetKeyPtr(), GetValuePtr() instead; +template<typename Key, typename Value, typename Compare> +class StaticMapIterator { + public: + // Constructors. + StaticMapIterator(): index_(-1), base_(NULL) { } + + // Increment & Decrement operators: + StaticMapIterator& operator++(); + StaticMapIterator operator++(int post_fix_operator); + + StaticMapIterator& operator--(); + StaticMapIterator operator--(int post_fix_operator); + + // Interface for retrieving data / pointer to data. + const Key* GetKeyPtr() const; + + // Run time error will occur if GetKey() is called on an invalid iterator. + inline const Key GetKey() const { return *GetKeyPtr(); } + + // return a raw memory pointer that points to the start address of value. + const char* GetValueRawPtr() const; + + // return a reinterpret-casted pointer to the value. + inline const Value* GetValuePtr() const { + return reinterpret_cast<const Value*>(GetValueRawPtr()); + } + + bool operator==(const StaticMapIterator& x) const; + bool operator!=(const StaticMapIterator& x) const; + + // Check if this iterator is valid. + // If iterator is invalid, user is forbidden to use ++/-- operator + // or interfaces for retrieving data / pointer to data. + bool IsValid() const; + + private: + friend class StaticMap<Key, Value, Compare>; + + // Only StaticMap can call this constructor. + explicit StaticMapIterator(const char* base, const int32_t &index); + + // Index of node that the iterator is pointing to. + int32_t index_; + + // Beginning address of the serialized map data. + const char* base_; + + // Number of nodes in the map. Use it to identify end() iterator. + int32_t num_nodes_; + + // offsets_ is an array of offset addresses of mapped values. + // For example: + // address_of_i-th_node_value = base_ + offsets_[i] + const u_int32_t* offsets_; + + // keys_[i] = key of i_th node. + const Key* keys_; +}; + +} // namespace google_breakpad + +#endif // PROCESSOR_STATIC_MAP_ITERATOR_H__ diff --git a/src/processor/static_map_unittest.cc b/src/processor/static_map_unittest.cc new file mode 100644 index 00000000..4172cac7 --- /dev/null +++ b/src/processor/static_map_unittest.cc @@ -0,0 +1,386 @@ +// Copyright (c) 2010 Google Inc. +// All rights reserved. +// +// 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 Inc. 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) + +#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(u_int32_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) u_int32_t(static_cast<u_int32_t>(stdmap.size())); + address += sizeof(u_int32_t); + + // Nodes' offset: + u_int32_t* offsets = reinterpret_cast<u_int32_t*>(address); + address += sizeof(u_int32_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(u_int32_t)); // Set the number of nodes = -1 + test_map = TestMap(data); + ASSERT_FALSE(test_map.ValidateInMemoryStructure()); +} + +TEST_F(TestInvalidMap, TestWrongOffsets) { + u_int32_t* header = reinterpret_cast<u_int32_t*>(data); + const u_int32_t kNumNodes = 2; + const u_int32_t kHeaderOffset = + sizeof(u_int32_t) + kNumNodes * (sizeof(u_int32_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) { + u_int32_t* header = reinterpret_cast<u_int32_t*>(data); + const u_int32_t kNumNodes = 2; + const u_int32_t kHeaderOffset = + sizeof(u_int32_t) + kNumNodes * (sizeof(u_int32_t) + sizeof(KeyType)); + header[0] = kNumNodes; + header[1] = kHeaderOffset; + header[2] = kHeaderOffset + sizeof(ValueType); + + KeyType* keys = reinterpret_cast<KeyType*>( + data + (kNumNodes + 1) * sizeof(u_int32_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(u_int32_t) + sizeof(KeyType) + sizeof(ValueType); + for (testcase = 0; testcase < kNumberTestCases; ++testcase) { + correct_size[testcase] = + sizeof(u_int32_t) + std_map[testcase].size() * size_per_node; + } + } + + void TearDown() { + for (int i = 0;i < kNumberTestCases; ++i) + 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(); +} |