108730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com// Copyright (c) 2010, Google Inc. 208730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com// All rights reserved. 308730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com// 408730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com// Redistribution and use in source and binary forms, with or without 508730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com// modification, are permitted provided that the following conditions are 608730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com// met: 708730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com// 808730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com// * Redistributions of source code must retain the above copyright 908730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com// notice, this list of conditions and the following disclaimer. 1008730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com// * Redistributions in binary form must reproduce the above 1108730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com// copyright notice, this list of conditions and the following disclaimer 1208730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com// in the documentation and/or other materials provided with the 1308730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com// distribution. 1408730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com// * Neither the name of Google Inc. nor the names of its 1508730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com// contributors may be used to endorse or promote products derived from 1608730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com// this software without specific prior written permission. 1708730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com// 1808730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1908730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 2008730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 2108730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2208730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2308730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2408730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2508730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2608730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2708730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2808730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2908730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com 3008730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com// static_contained_range_map-inl.h: Hierarchically-organized range map, 3108730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com// i.e., StaticContainedRangeMap implementation. 3208730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com// 3308730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com// See static_contained_range_map.h for documentation. 3408730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com// 3508730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com// Author: Siyang Xie (lambxsy@google.com) 3608730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com 3708730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com#ifndef PROCESSOR_STATIC_CONTAINED_RANGE_MAP_INL_H__ 3808730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com#define PROCESSOR_STATIC_CONTAINED_RANGE_MAP_INL_H__ 3908730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com 4008730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com#include "processor/static_contained_range_map.h" 4108730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com#include "processor/logging.h" 4208730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com 4308730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.comnamespace google_breakpad { 4408730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com 4508730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.comtemplate<typename AddressType, typename EntryType> 4608730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.comStaticContainedRangeMap<AddressType, EntryType>::StaticContainedRangeMap( 4708730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com const char *base) 4808730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com : base_(*(reinterpret_cast<const AddressType*>(base))), 496162aed3c3fcfc53373c963ac375d39a5dfa5a25ted.mielczarek@gmail.com entry_size_(*(reinterpret_cast<const uint32_t*>(base + sizeof(base_)))), 5008730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com entry_ptr_(reinterpret_cast<const EntryType *>( 5108730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com base + sizeof(base_) + sizeof(entry_size_))), 5208730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com map_(base + sizeof(base_) + sizeof(entry_size_) + entry_size_) { 5308730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com if (entry_size_ == 0) 5408730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com entry_ptr_ = NULL; 5508730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com} 5608730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com 5708730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com 5808730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.comtemplate<typename AddressType, typename EntryType> 5908730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.combool StaticContainedRangeMap<AddressType, EntryType>::RetrieveRange( 6008730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com const AddressType &address, const EntryType *&entry) const { 6108730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com 6208730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com // Get an iterator to the child range whose high address is equal to or 6308730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com // greater than the supplied address. If the supplied address is higher 6408730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com // than all of the high addresses in the range, then this range does not 6508730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com // contain a child at address, so return false. If the supplied address 6608730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com // is lower than the base address of the child range, then it is not within 6708730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com // the child range, so return false. 6808730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com MapConstIterator iterator = map_.lower_bound(address); 6908730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com 7008730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com if (iterator == map_.end()) 7108730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com return false; 7208730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com 7308730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com const char *memory_child = 7408730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com reinterpret_cast<const char*>(iterator.GetValuePtr()); 7508730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com 7608730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com StaticContainedRangeMap child_map(memory_child); 7708730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com 7808730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com if (address < child_map.base_) 7908730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com return false; 8008730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com 8108730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com // The child in iterator->second contains the specified address. Find out 8208730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com // if it has a more-specific descendant that also contains it. If it does, 8308730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com // it will set |entry| appropriately. If not, set |entry| to the child. 8408730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com if (!child_map.RetrieveRange(address, entry)) 8508730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com entry = child_map.entry_ptr_; 8608730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com 8708730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com return true; 8808730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com} 8908730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com 9008730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com} // namespace google_breakpad 9108730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com 9208730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com#endif // PROCESSOR_STATIC_CONTAINED_RANGE_MAP_INL_H__ 93