1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/toolkit/crashreporter/google-breakpad/src/processor/static_map.h Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,144 @@
1.4 +// Copyright 2010 Google Inc. All Rights Reserved.
1.5 +//
1.6 +// Redistribution and use in source and binary forms, with or without
1.7 +// modification, are permitted provided that the following conditions are
1.8 +// met:
1.9 +//
1.10 +// * Redistributions of source code must retain the above copyright
1.11 +// notice, this list of conditions and the following disclaimer.
1.12 +// * Redistributions in binary form must reproduce the above
1.13 +// copyright notice, this list of conditions and the following disclaimer
1.14 +// in the documentation and/or other materials provided with the
1.15 +// distribution.
1.16 +// * Neither the name of Google Inc. nor the names of its
1.17 +// contributors may be used to endorse or promote products derived from
1.18 +// this software without specific prior written permission.
1.19 +//
1.20 +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1.21 +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1.22 +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1.23 +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1.24 +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1.25 +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1.26 +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1.27 +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1.28 +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1.29 +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1.30 +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1.31 +
1.32 +// static_map.h: StaticMap.
1.33 +//
1.34 +// StaticMap provides lookup interfaces and iterators similar as stl::map's.
1.35 +// These lookup operations are purely Read-Only, thus memory
1.36 +// allocation & deallocation is mostly avoided (intentionally).
1.37 +//
1.38 +// The chunk of memory should contain data with pre-defined pattern:
1.39 +// **************** header ***************
1.40 +// uint32 (4 bytes): number of nodes
1.41 +// uint32 (4 bytes): address offset of node1's mapped_value
1.42 +// uint32 (4 bytes): address offset of node2's mapped_value
1.43 +// ...
1.44 +// uint32 (4 bytes): address offset of nodeN's mapped_value
1.45 +//
1.46 +// ************* Key array ************
1.47 +// (X bytes): node1's key
1.48 +// (X bytes): node2's key
1.49 +// ...
1.50 +// (X bytes): nodeN's key
1.51 +//
1.52 +// ************* Value array **********
1.53 +// (? bytes): node1's mapped_value
1.54 +// (? bytes): node2's mapped_value
1.55 +// ...
1.56 +// (? bytes): nodeN's mapped_value
1.57 +//
1.58 +// REQUIREMENT: Key type MUST be primitive type or pointers so that:
1.59 +// X = sizeof(typename Key);
1.60 +//
1.61 +// Note: since address offset is stored as uint32, user should keep in mind that
1.62 +// StaticMap only supports up to 4GB size of memory data.
1.63 +
1.64 +// Author: Siyang Xie (lambxsy@google.com)
1.65 +
1.66 +
1.67 +#ifndef PROCESSOR_STATIC_MAP_H__
1.68 +#define PROCESSOR_STATIC_MAP_H__
1.69 +
1.70 +#include "processor/static_map_iterator-inl.h"
1.71 +
1.72 +namespace google_breakpad {
1.73 +
1.74 +// Default functor to compare keys.
1.75 +template<typename Key>
1.76 +class DefaultCompare {
1.77 + public:
1.78 + int operator()(const Key &k1, const Key &k2) const {
1.79 + if (k1 < k2) return -1;
1.80 + if (k1 == k2) return 0;
1.81 + return 1;
1.82 + }
1.83 +};
1.84 +
1.85 +template<typename Key, typename Value, typename Compare = DefaultCompare<Key> >
1.86 +class StaticMap {
1.87 + public:
1.88 + typedef StaticMapIterator<Key, Value, Compare> iterator;
1.89 + typedef StaticMapIterator<Key, Value, Compare> const_iterator;
1.90 +
1.91 + StaticMap() : raw_data_(0),
1.92 + num_nodes_(0),
1.93 + offsets_(0),
1.94 + compare_() { }
1.95 +
1.96 + explicit StaticMap(const char* raw_data);
1.97 +
1.98 + inline bool empty() const { return num_nodes_ == 0; }
1.99 + inline unsigned int size() const { return num_nodes_; }
1.100 +
1.101 + // Return iterators.
1.102 + inline iterator begin() const { return IteratorAtIndex(0); }
1.103 + inline iterator last() const { return IteratorAtIndex(num_nodes_ - 1); }
1.104 + inline iterator end() const { return IteratorAtIndex(num_nodes_); }
1.105 + inline iterator IteratorAtIndex(int index) const {
1.106 + return iterator(raw_data_, index);
1.107 + }
1.108 +
1.109 + // Lookup operations.
1.110 + iterator find(const Key &k) const;
1.111 +
1.112 + // lower_bound(k) searches in a sorted range for the first element that has a
1.113 + // key not less than the argument k.
1.114 + iterator lower_bound(const Key &k) const;
1.115 +
1.116 + // upper_bound(k) searches in a sorted range for the first element that has a
1.117 + // key greater than the argument k.
1.118 + iterator upper_bound(const Key &k) const;
1.119 +
1.120 + // Checks if the underlying memory data conforms to the predefined pattern:
1.121 + // first check the number of nodes is non-negative,
1.122 + // then check both offsets and keys are strictly increasing (sorted).
1.123 + bool ValidateInMemoryStructure() const;
1.124 +
1.125 + private:
1.126 + const Key GetKeyAtIndex(int i) const;
1.127 +
1.128 + // Start address of a raw memory chunk with serialized data.
1.129 + const char* raw_data_;
1.130 +
1.131 + // Number of nodes in the static map.
1.132 + int32_t num_nodes_;
1.133 +
1.134 + // Array of offset addresses for stored values.
1.135 + // For example:
1.136 + // address_of_i-th_node_value = raw_data_ + offsets_[i]
1.137 + const uint32_t* offsets_;
1.138 +
1.139 + // keys_[i] = key of i_th node
1.140 + const Key* keys_;
1.141 +
1.142 + Compare compare_;
1.143 +};
1.144 +
1.145 +} // namespace google_breakpad
1.146 +
1.147 +#endif // PROCESSOR_STATIC_MAP_H__
