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-inl.h: StaticMap implementation. 30 // 31 // See static_map.h for documentation. 32 // 33 // Author: Siyang Xie (lambxsy (at) google.com) 34 35 36 #ifndef PROCESSOR_STATIC_MAP_INL_H__ 37 #define PROCESSOR_STATIC_MAP_INL_H__ 38 39 #include "processor/static_map.h" 40 #include "processor/static_map_iterator-inl.h" 41 #include "processor/logging.h" 42 43 namespace google_breakpad { 44 45 template<typename Key, typename Value, typename Compare> 46 StaticMap<Key, Value, Compare>::StaticMap(const char* raw_data) 47 : raw_data_(raw_data), 48 compare_() { 49 // First 4 Bytes store the number of nodes. 50 num_nodes_ = *(reinterpret_cast<const uint32_t*>(raw_data_)); 51 52 offsets_ = reinterpret_cast<const uint32_t*>( 53 raw_data_ + sizeof(num_nodes_)); 54 55 keys_ = reinterpret_cast<const Key*>( 56 raw_data_ + (1 + num_nodes_) * sizeof(uint32_t)); 57 } 58 59 // find(), lower_bound() and upper_bound() implement binary search algorithm. 60 template<typename Key, typename Value, typename Compare> 61 StaticMapIterator<Key, Value, Compare> 62 StaticMap<Key, Value, Compare>::find(const Key &key) const { 63 int begin = 0; 64 int end = num_nodes_; 65 int middle; 66 int compare_result; 67 while (begin < end) { 68 middle = begin + (end - begin) / 2; 69 compare_result = compare_(key, GetKeyAtIndex(middle)); 70 if (compare_result == 0) 71 return IteratorAtIndex(middle); 72 if (compare_result < 0) { 73 end = middle; 74 } else { 75 begin = middle + 1; 76 } 77 } 78 return this->end(); 79 } 80 81 template<typename Key, typename Value, typename Compare> 82 StaticMapIterator<Key, Value, Compare> 83 StaticMap<Key, Value, Compare>::lower_bound(const Key &key) const { 84 int begin = 0; 85 int end = num_nodes_; 86 int middle; 87 int comp_result; 88 while (begin < end) { 89 middle = begin + (end - begin) / 2; 90 comp_result = compare_(key, GetKeyAtIndex(middle)); 91 if (comp_result == 0) 92 return IteratorAtIndex(middle); 93 if (comp_result < 0) { 94 end = middle; 95 } else { 96 begin = middle + 1; 97 } 98 } 99 return IteratorAtIndex(begin); 100 } 101 102 template<typename Key, typename Value, typename Compare> 103 StaticMapIterator<Key, Value, Compare> 104 StaticMap<Key, Value, Compare>::upper_bound(const Key &key) const { 105 int begin = 0; 106 int end = num_nodes_; 107 int middle; 108 int compare_result; 109 while (begin < end) { 110 middle = begin + (end - begin) / 2; 111 compare_result = compare_(key, GetKeyAtIndex(middle)); 112 if (compare_result == 0) 113 return IteratorAtIndex(middle + 1); 114 if (compare_result < 0) { 115 end = middle; 116 } else { 117 begin = middle + 1; 118 } 119 } 120 return IteratorAtIndex(begin); 121 } 122 123 template<typename Key, typename Value, typename Compare> 124 bool StaticMap<Key, Value, Compare>::ValidateInMemoryStructure() const { 125 // check the number of nodes is non-negative: 126 if (!raw_data_) return false; 127 int32_t num_nodes = *(reinterpret_cast<const int32_t*>(raw_data_)); 128 if (num_nodes < 0) { 129 BPLOG(INFO) << "StaticMap check failed: negative number of nodes"; 130 return false; 131 } 132 133 int node_index = 0; 134 if (num_nodes_) { 135 uint64_t first_offset = sizeof(int32_t) * (num_nodes_ + 1) 136 + sizeof(Key) * num_nodes_; 137 // Num_nodes_ is too large. 138 if (first_offset > 0xffffffffUL) { 139 BPLOG(INFO) << "StaticMap check failed: size exceeds limit"; 140 return false; 141 } 142 if (offsets_[node_index] != static_cast<uint32_t>(first_offset)) { 143 BPLOG(INFO) << "StaticMap check failed: first node offset is incorrect"; 144 return false; 145 } 146 } 147 148 for (node_index = 1; node_index < num_nodes_; ++node_index) { 149 // Check offsets[i] is strictly increasing: 150 if (offsets_[node_index] <= offsets_[node_index - 1]) { 151 BPLOG(INFO) << "StaticMap check failed: node offsets non-increasing"; 152 return false; 153 } 154 // Check Key[i] is strictly increasing as no duplicate keys are allowed. 155 if (compare_(GetKeyAtIndex(node_index), 156 GetKeyAtIndex(node_index - 1)) <= 0) { 157 BPLOG(INFO) << "StaticMap check failed: node keys non-increasing"; 158 return false; 159 } 160 } 161 return true; 162 } 163 164 template<typename Key, typename Value, typename Compare> 165 const Key StaticMap<Key, Value, Compare>::GetKeyAtIndex(int index) const { 166 if (index < 0 || index >= num_nodes_) { 167 BPLOG(ERROR) << "Key index out of range error"; 168 // Key type is required to be primitive type. Return 0 if index is invalid. 169 return 0; 170 } 171 return keys_[index]; 172 } 173 174 } // namespace google_breakpad 175 176 #endif // PROCESSOR_STATIC_MAP_INL_H__ 177
