1 | // Copyright 2010 Google Inc. All Rights Reserved. |
2 | // |
3 | // Redistribution and use in source and binary forms, with or without |
4 | // modification, are permitted provided that the following conditions are |
5 | // met: |
6 | // |
7 | // * Redistributions of source code must retain the above copyright |
8 | // notice, this list of conditions and the following disclaimer. |
9 | // * Redistributions in binary form must reproduce the above |
10 | // copyright notice, this list of conditions and the following disclaimer |
11 | // in the documentation and/or other materials provided with the |
12 | // distribution. |
13 | // * Neither the name of Google Inc. nor the names of its |
14 | // contributors may be used to endorse or promote products derived from |
15 | // this software without specific prior written permission. |
16 | // |
17 | // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
18 | // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
19 | // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
20 | // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
21 | // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
22 | // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
23 | // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
24 | // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
25 | // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
26 | // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
27 | // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
28 | |
29 | // static_map.h: StaticMap. |
30 | // |
31 | // StaticMap provides lookup interfaces and iterators similar as stl::map's. |
32 | // These lookup operations are purely Read-Only, thus memory |
33 | // allocation & deallocation is mostly avoided (intentionally). |
34 | // |
35 | // The chunk of memory should contain data with pre-defined pattern: |
36 | // **************** header *************** |
37 | // uint32 (4 bytes): number of nodes |
38 | // uint32 (4 bytes): address offset of node1's mapped_value |
39 | // uint32 (4 bytes): address offset of node2's mapped_value |
40 | // ... |
41 | // uint32 (4 bytes): address offset of nodeN's mapped_value |
42 | // |
43 | // ************* Key array ************ |
44 | // (X bytes): node1's key |
45 | // (X bytes): node2's key |
46 | // ... |
47 | // (X bytes): nodeN's key |
48 | // |
49 | // ************* Value array ********** |
50 | // (? bytes): node1's mapped_value |
51 | // (? bytes): node2's mapped_value |
52 | // ... |
53 | // (? bytes): nodeN's mapped_value |
54 | // |
55 | // REQUIREMENT: Key type MUST be primitive type or pointers so that: |
56 | // X = sizeof(typename Key); |
57 | // |
58 | // Note: since address offset is stored as uint32, user should keep in mind that |
59 | // StaticMap only supports up to 4GB size of memory data. |
60 | |
61 | // Author: Siyang Xie (lambxsy@google.com) |
62 | |
63 | |
64 | #ifndef PROCESSOR_STATIC_MAP_H__ |
65 | #define PROCESSOR_STATIC_MAP_H__ |
66 | |
67 | #include "processor/static_map_iterator-inl.h" |
68 | |
69 | namespace google_breakpad { |
70 | |
71 | // Default functor to compare keys. |
72 | template<typename Key> |
73 | class DefaultCompare { |
74 | public: |
75 | int operator()(const Key& k1, const Key& k2) const { |
76 | if (k1 < k2) return -1; |
77 | if (k1 == k2) return 0; |
78 | return 1; |
79 | } |
80 | }; |
81 | |
82 | template<typename Key, typename Value, typename Compare = DefaultCompare<Key> > |
83 | class StaticMap { |
84 | public: |
85 | typedef StaticMapIterator<Key, Value, Compare> iterator; |
86 | typedef StaticMapIterator<Key, Value, Compare> const_iterator; |
87 | |
88 | StaticMap() : raw_data_(0), |
89 | num_nodes_(0), |
90 | offsets_(0), |
91 | compare_() { } |
92 | |
93 | explicit StaticMap(const char* raw_data); |
94 | |
95 | inline bool empty() const { return num_nodes_ == 0; } |
96 | inline unsigned int size() const { return num_nodes_; } |
97 | |
98 | // Return iterators. |
99 | inline iterator begin() const { return IteratorAtIndex(0); } |
100 | inline iterator last() const { return IteratorAtIndex(num_nodes_ - 1); } |
101 | inline iterator end() const { return IteratorAtIndex(num_nodes_); } |
102 | inline iterator IteratorAtIndex(int index) const { |
103 | return iterator(raw_data_, index); |
104 | } |
105 | |
106 | // Lookup operations. |
107 | iterator find(const Key& k) const; |
108 | |
109 | // lower_bound(k) searches in a sorted range for the first element that has a |
110 | // key not less than the argument k. |
111 | iterator lower_bound(const Key& k) const; |
112 | |
113 | // upper_bound(k) searches in a sorted range for the first element that has a |
114 | // key greater than the argument k. |
115 | iterator upper_bound(const Key& k) const; |
116 | |
117 | // Checks if the underlying memory data conforms to the predefined pattern: |
118 | // first check the number of nodes is non-negative, |
119 | // then check both offsets and keys are strictly increasing (sorted). |
120 | bool ValidateInMemoryStructure() const; |
121 | |
122 | private: |
123 | const Key GetKeyAtIndex(int i) const; |
124 | |
125 | // Start address of a raw memory chunk with serialized data. |
126 | const char* raw_data_; |
127 | |
128 | // Number of nodes in the static map. |
129 | int32_t num_nodes_; |
130 | |
131 | // Array of offset addresses for stored values. |
132 | // For example: |
133 | // address_of_i-th_node_value = raw_data_ + offsets_[i] |
134 | const uint32_t* offsets_; |
135 | |
136 | // keys_[i] = key of i_th node |
137 | const Key* keys_; |
138 | |
139 | Compare compare_; |
140 | }; |
141 | |
142 | } // namespace google_breakpad |
143 | |
144 | #endif // PROCESSOR_STATIC_MAP_H__ |
145 | |