aboutsummaryrefslogtreecommitdiff
path: root/externals/breakpad/src/processor/static_map-inl.h
diff options
context:
space:
mode:
authorDawid Potocki <dawid@dawidpotocki.com>2024-03-05 14:09:27 +1300
committerDawid Potocki <dawid@dawidpotocki.com>2024-03-05 20:34:15 +1300
commit063e15900bda8453fb0fc6751e78d064501ccbae (patch)
treea4cd5f01dbca33a262333aff10e1e035217a30c8 /externals/breakpad/src/processor/static_map-inl.h
parent537296095ab24eddcb196b5ef98004f91de9c8c2 (diff)
Replace broken submodules with vendored source codeHEADpatched
Diffstat (limited to 'externals/breakpad/src/processor/static_map-inl.h')
-rw-r--r--externals/breakpad/src/processor/static_map-inl.h176
1 files changed, 176 insertions, 0 deletions
diff --git a/externals/breakpad/src/processor/static_map-inl.h b/externals/breakpad/src/processor/static_map-inl.h
new file mode 100644
index 0000000000..f9929efe90
--- /dev/null
+++ b/externals/breakpad/src/processor/static_map-inl.h
@@ -0,0 +1,176 @@
+// Copyright 2010 Google LLC
+//
+// 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 LLC 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 uint32_t*>(raw_data_));
+
+ offsets_ = reinterpret_cast<const uint32_t*>(
+ raw_data_ + sizeof(num_nodes_));
+
+ keys_ = reinterpret_cast<const Key*>(
+ raw_data_ + (1 + num_nodes_) * sizeof(uint32_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_) {
+ uint64_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<uint32_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__
generated by cgit v1.2.3-70-g09d2 (git 2.49.0) at 2025-04-20 07:14:41 +0000