OLD | NEW |
1 // Copyright 2010 Google Inc. All Rights Reserved. | 1 // Copyright 2010 Google Inc. All Rights Reserved. |
2 // | 2 // |
3 // Redistribution and use in source and binary forms, with or without | 3 // Redistribution and use in source and binary forms, with or without |
4 // modification, are permitted provided that the following conditions are | 4 // modification, are permitted provided that the following conditions are |
5 // met: | 5 // met: |
6 // | 6 // |
7 // * Redistributions of source code must retain the above copyright | 7 // * Redistributions of source code must retain the above copyright |
8 // notice, this list of conditions and the following disclaimer. | 8 // notice, this list of conditions and the following disclaimer. |
9 // * Redistributions in binary form must reproduce the above | 9 // * Redistributions in binary form must reproduce the above |
10 // copyright notice, this list of conditions and the following disclaimer | 10 // copyright notice, this list of conditions and the following disclaimer |
(...skipping 29 matching lines...) Expand all Loading... |
40 #include "processor/static_map_iterator-inl.h" | 40 #include "processor/static_map_iterator-inl.h" |
41 #include "processor/logging.h" | 41 #include "processor/logging.h" |
42 | 42 |
43 namespace google_breakpad { | 43 namespace google_breakpad { |
44 | 44 |
45 template<typename Key, typename Value, typename Compare> | 45 template<typename Key, typename Value, typename Compare> |
46 StaticMap<Key, Value, Compare>::StaticMap(const char* raw_data) | 46 StaticMap<Key, Value, Compare>::StaticMap(const char* raw_data) |
47 : raw_data_(raw_data), | 47 : raw_data_(raw_data), |
48 compare_() { | 48 compare_() { |
49 // First 4 Bytes store the number of nodes. | 49 // First 4 Bytes store the number of nodes. |
50 num_nodes_ = *(reinterpret_cast<const u_int32_t*>(raw_data_)); | 50 num_nodes_ = *(reinterpret_cast<const uint32_t*>(raw_data_)); |
51 | 51 |
52 offsets_ = reinterpret_cast<const u_int32_t*>( | 52 offsets_ = reinterpret_cast<const uint32_t*>( |
53 raw_data_ + sizeof(num_nodes_)); | 53 raw_data_ + sizeof(num_nodes_)); |
54 | 54 |
55 keys_ = reinterpret_cast<const Key*>( | 55 keys_ = reinterpret_cast<const Key*>( |
56 raw_data_ + (1 + num_nodes_) * sizeof(u_int32_t)); | 56 raw_data_ + (1 + num_nodes_) * sizeof(uint32_t)); |
57 } | 57 } |
58 | 58 |
59 // find(), lower_bound() and upper_bound() implement binary search algorithm. | 59 // find(), lower_bound() and upper_bound() implement binary search algorithm. |
60 template<typename Key, typename Value, typename Compare> | 60 template<typename Key, typename Value, typename Compare> |
61 StaticMapIterator<Key, Value, Compare> | 61 StaticMapIterator<Key, Value, Compare> |
62 StaticMap<Key, Value, Compare>::find(const Key &key) const { | 62 StaticMap<Key, Value, Compare>::find(const Key &key) const { |
63 int begin = 0; | 63 int begin = 0; |
64 int end = num_nodes_; | 64 int end = num_nodes_; |
65 int middle; | 65 int middle; |
66 int compare_result; | 66 int compare_result; |
(...skipping 58 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
125 // check the number of nodes is non-negative: | 125 // check the number of nodes is non-negative: |
126 if (!raw_data_) return false; | 126 if (!raw_data_) return false; |
127 int32_t num_nodes = *(reinterpret_cast<const int32_t*>(raw_data_)); | 127 int32_t num_nodes = *(reinterpret_cast<const int32_t*>(raw_data_)); |
128 if (num_nodes < 0) { | 128 if (num_nodes < 0) { |
129 BPLOG(INFO) << "StaticMap check failed: negative number of nodes"; | 129 BPLOG(INFO) << "StaticMap check failed: negative number of nodes"; |
130 return false; | 130 return false; |
131 } | 131 } |
132 | 132 |
133 int node_index = 0; | 133 int node_index = 0; |
134 if (num_nodes_) { | 134 if (num_nodes_) { |
135 u_int64_t first_offset = sizeof(int32_t) * (num_nodes_ + 1) | 135 uint64_t first_offset = sizeof(int32_t) * (num_nodes_ + 1) |
136 + sizeof(Key) * num_nodes_; | 136 + sizeof(Key) * num_nodes_; |
137 // Num_nodes_ is too large. | 137 // Num_nodes_ is too large. |
138 if (first_offset > 0xffffffffUL) { | 138 if (first_offset > 0xffffffffUL) { |
139 BPLOG(INFO) << "StaticMap check failed: size exceeds limit"; | 139 BPLOG(INFO) << "StaticMap check failed: size exceeds limit"; |
140 return false; | 140 return false; |
141 } | 141 } |
142 if (offsets_[node_index] != static_cast<u_int32_t>(first_offset)) { | 142 if (offsets_[node_index] != static_cast<uint32_t>(first_offset)) { |
143 BPLOG(INFO) << "StaticMap check failed: first node offset is incorrect"; | 143 BPLOG(INFO) << "StaticMap check failed: first node offset is incorrect"; |
144 return false; | 144 return false; |
145 } | 145 } |
146 } | 146 } |
147 | 147 |
148 for (node_index = 1; node_index < num_nodes_; ++node_index) { | 148 for (node_index = 1; node_index < num_nodes_; ++node_index) { |
149 // Check offsets[i] is strictly increasing: | 149 // Check offsets[i] is strictly increasing: |
150 if (offsets_[node_index] <= offsets_[node_index - 1]) { | 150 if (offsets_[node_index] <= offsets_[node_index - 1]) { |
151 BPLOG(INFO) << "StaticMap check failed: node offsets non-increasing"; | 151 BPLOG(INFO) << "StaticMap check failed: node offsets non-increasing"; |
152 return false; | 152 return false; |
(...skipping 14 matching lines...) Expand all Loading... |
167 BPLOG(ERROR) << "Key index out of range error"; | 167 BPLOG(ERROR) << "Key index out of range error"; |
168 // Key type is required to be primitive type. Return 0 if index is invalid. | 168 // Key type is required to be primitive type. Return 0 if index is invalid. |
169 return 0; | 169 return 0; |
170 } | 170 } |
171 return keys_[index]; | 171 return keys_[index]; |
172 } | 172 } |
173 | 173 |
174 } // namespace google_breakpad | 174 } // namespace google_breakpad |
175 | 175 |
176 #endif // PROCESSOR_STATIC_MAP_INL_H__ | 176 #endif // PROCESSOR_STATIC_MAP_INL_H__ |
OLD | NEW |