michael@0: // Copyright 2010 Google Inc. All Rights Reserved.
michael@0: //
michael@0: // Redistribution and use in source and binary forms, with or without
michael@0: // modification, are permitted provided that the following conditions are
michael@0: // met:
michael@0: //
michael@0: //     * Redistributions of source code must retain the above copyright
michael@0: // notice, this list of conditions and the following disclaimer.
michael@0: //     * Redistributions in binary form must reproduce the above
michael@0: // copyright notice, this list of conditions and the following disclaimer
michael@0: // in the documentation and/or other materials provided with the
michael@0: // distribution.
michael@0: //     * Neither the name of Google Inc. nor the names of its
michael@0: // contributors may be used to endorse or promote products derived from
michael@0: // this software without specific prior written permission.
michael@0: //
michael@0: // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
michael@0: // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
michael@0: // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
michael@0: // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
michael@0: // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
michael@0: // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
michael@0: // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
michael@0: // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
michael@0: // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
michael@0: // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
michael@0: // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
michael@0: 
michael@0: // static_map-inl.h: StaticMap implementation.
michael@0: //
michael@0: // See static_map.h for documentation.
michael@0: //
michael@0: // Author: Siyang Xie (lambxsy@google.com)
michael@0: 
michael@0: 
michael@0: #ifndef PROCESSOR_STATIC_MAP_INL_H__
michael@0: #define PROCESSOR_STATIC_MAP_INL_H__
michael@0: 
michael@0: #include "processor/static_map.h"
michael@0: #include "processor/static_map_iterator-inl.h"
michael@0: #include "common/logging.h"
michael@0: 
michael@0: namespace google_breakpad {
michael@0: 
michael@0: template<typename Key, typename Value, typename Compare>
michael@0: StaticMap<Key, Value, Compare>::StaticMap(const char* raw_data)
michael@0:     : raw_data_(raw_data),
michael@0:       compare_() {
michael@0:   // First 4 Bytes store the number of nodes.
michael@0:   num_nodes_ = *(reinterpret_cast<const uint32_t*>(raw_data_));
michael@0: 
michael@0:   offsets_ = reinterpret_cast<const uint32_t*>(
michael@0:       raw_data_ + sizeof(num_nodes_));
michael@0: 
michael@0:   keys_ = reinterpret_cast<const Key*>(
michael@0:       raw_data_ + (1 + num_nodes_) * sizeof(uint32_t));
michael@0: }
michael@0: 
michael@0: // find(), lower_bound() and upper_bound() implement binary search algorithm.
michael@0: template<typename Key, typename Value, typename Compare>
michael@0: StaticMapIterator<Key, Value, Compare>
michael@0: StaticMap<Key, Value, Compare>::find(const Key &key) const {
michael@0:   int begin = 0;
michael@0:   int end = num_nodes_;
michael@0:   int middle;
michael@0:   int compare_result;
michael@0:   while (begin < end) {
michael@0:     middle = begin + (end - begin) / 2;
michael@0:     compare_result = compare_(key, GetKeyAtIndex(middle));
michael@0:     if (compare_result == 0)
michael@0:       return IteratorAtIndex(middle);
michael@0:     if (compare_result < 0) {
michael@0:       end = middle;
michael@0:     } else {
michael@0:       begin = middle + 1;
michael@0:     }
michael@0:   }
michael@0:   return this->end();
michael@0: }
michael@0: 
michael@0: template<typename Key, typename Value, typename Compare>
michael@0: StaticMapIterator<Key, Value, Compare>
michael@0: StaticMap<Key, Value, Compare>::lower_bound(const Key &key) const {
michael@0:   int begin = 0;
michael@0:   int end = num_nodes_;
michael@0:   int middle;
michael@0:   int comp_result;
michael@0:   while (begin < end) {
michael@0:     middle = begin + (end - begin) / 2;
michael@0:     comp_result = compare_(key, GetKeyAtIndex(middle));
michael@0:     if (comp_result == 0)
michael@0:       return IteratorAtIndex(middle);
michael@0:     if (comp_result < 0) {
michael@0:       end = middle;
michael@0:     } else {
michael@0:       begin = middle + 1;
michael@0:     }
michael@0:   }
michael@0:   return IteratorAtIndex(begin);
michael@0: }
michael@0: 
michael@0: template<typename Key, typename Value, typename Compare>
michael@0: StaticMapIterator<Key, Value, Compare>
michael@0: StaticMap<Key, Value, Compare>::upper_bound(const Key &key) const {
michael@0:   int begin = 0;
michael@0:   int end = num_nodes_;
michael@0:   int middle;
michael@0:   int compare_result;
michael@0:   while (begin < end) {
michael@0:     middle = begin + (end - begin) / 2;
michael@0:     compare_result = compare_(key, GetKeyAtIndex(middle));
michael@0:     if (compare_result == 0)
michael@0:       return IteratorAtIndex(middle + 1);
michael@0:     if (compare_result < 0) {
michael@0:       end = middle;
michael@0:     } else {
michael@0:       begin = middle + 1;
michael@0:     }
michael@0:   }
michael@0:   return IteratorAtIndex(begin);
michael@0: }
michael@0: 
michael@0: template<typename Key, typename Value, typename Compare>
michael@0: bool StaticMap<Key, Value, Compare>::ValidateInMemoryStructure() const {
michael@0:   // check the number of nodes is non-negative:
michael@0:   if (!raw_data_) return false;
michael@0:   int32_t num_nodes = *(reinterpret_cast<const int32_t*>(raw_data_));
michael@0:   if (num_nodes < 0) {
michael@0:     BPLOG(INFO) << "StaticMap check failed: negative number of nodes";
michael@0:     return false;
michael@0:   }
michael@0: 
michael@0:   int node_index = 0;
michael@0:   if (num_nodes_) {
michael@0:     uint64_t first_offset = sizeof(int32_t) * (num_nodes_ + 1)
michael@0:                            + sizeof(Key) * num_nodes_;
michael@0:     // Num_nodes_ is too large.
michael@0:     if (first_offset > 0xffffffffUL) {
michael@0:       BPLOG(INFO) << "StaticMap check failed: size exceeds limit";
michael@0:       return false;
michael@0:     }
michael@0:     if (offsets_[node_index] != static_cast<uint32_t>(first_offset)) {
michael@0:       BPLOG(INFO) << "StaticMap check failed: first node offset is incorrect";
michael@0:       return false;
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   for (node_index = 1; node_index < num_nodes_; ++node_index) {
michael@0:     // Check offsets[i] is strictly increasing:
michael@0:     if (offsets_[node_index] <= offsets_[node_index - 1]) {
michael@0:       BPLOG(INFO) << "StaticMap check failed: node offsets non-increasing";
michael@0:       return false;
michael@0:     }
michael@0:     // Check Key[i] is strictly increasing as no duplicate keys are allowed.
michael@0:     if (compare_(GetKeyAtIndex(node_index),
michael@0:                  GetKeyAtIndex(node_index - 1)) <= 0) {
michael@0:       BPLOG(INFO) << "StaticMap check failed: node keys non-increasing";
michael@0:       return false;
michael@0:     }
michael@0:   }
michael@0:   return true;
michael@0: }
michael@0: 
michael@0: template<typename Key, typename Value, typename Compare>
michael@0: const Key StaticMap<Key, Value, Compare>::GetKeyAtIndex(int index) const {
michael@0:   if (index < 0 || index >= num_nodes_) {
michael@0:     BPLOG(ERROR) << "Key index out of range error";
michael@0:     // Key type is required to be primitive type.  Return 0 if index is invalid.
michael@0:     return 0;
michael@0:   }
michael@0:   return keys_[index];
michael@0: }
michael@0: 
michael@0: }  // namespace google_breakpad
michael@0: 
michael@0: #endif  // PROCESSOR_STATIC_MAP_INL_H__