1 // Copyright (c) 2010, Google Inc. 2 // All rights reserved. 3 // 4 // Redistribution and use in source and binary forms, with or without 5 // modification, are permitted provided that the following conditions are 6 // met: 7 // 8 // * Redistributions of source code must retain the above copyright 9 // notice, this list of conditions and the following disclaimer. 10 // * Redistributions in binary form must reproduce the above 11 // copyright notice, this list of conditions and the following disclaimer 12 // in the documentation and/or other materials provided with the 13 // distribution. 14 // * Neither the name of Google Inc. nor the names of its 15 // contributors may be used to endorse or promote products derived from 16 // this software without specific prior written permission. 17 // 18 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 19 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 20 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 21 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 22 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 23 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 24 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 25 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 26 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 27 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 28 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29 30 // static_contained_range_map-inl.h: Hierarchically-organized range map, 31 // i.e., StaticContainedRangeMap implementation. 32 // 33 // See static_contained_range_map.h for documentation. 34 // 35 // Author: Siyang Xie (lambxsy (at) google.com) 36 37 #ifndef PROCESSOR_STATIC_CONTAINED_RANGE_MAP_INL_H__ 38 #define PROCESSOR_STATIC_CONTAINED_RANGE_MAP_INL_H__ 39 40 #include "processor/static_contained_range_map.h" 41 #include "processor/logging.h" 42 43 namespace google_breakpad { 44 45 template<typename AddressType, typename EntryType> 46 StaticContainedRangeMap<AddressType, EntryType>::StaticContainedRangeMap( 47 const char *base) 48 : base_(*(reinterpret_cast<const AddressType*>(base))), 49 entry_size_(*(reinterpret_cast<const uint32_t*>(base + sizeof(base_)))), 50 entry_ptr_(reinterpret_cast<const EntryType *>( 51 base + sizeof(base_) + sizeof(entry_size_))), 52 map_(base + sizeof(base_) + sizeof(entry_size_) + entry_size_) { 53 if (entry_size_ == 0) 54 entry_ptr_ = NULL; 55 } 56 57 58 template<typename AddressType, typename EntryType> 59 bool StaticContainedRangeMap<AddressType, EntryType>::RetrieveRange( 60 const AddressType &address, const EntryType *&entry) const { 61 62 // Get an iterator to the child range whose high address is equal to or 63 // greater than the supplied address. If the supplied address is higher 64 // than all of the high addresses in the range, then this range does not 65 // contain a child at address, so return false. If the supplied address 66 // is lower than the base address of the child range, then it is not within 67 // the child range, so return false. 68 MapConstIterator iterator = map_.lower_bound(address); 69 70 if (iterator == map_.end()) 71 return false; 72 73 const char *memory_child = 74 reinterpret_cast<const char*>(iterator.GetValuePtr()); 75 76 StaticContainedRangeMap child_map(memory_child); 77 78 if (address < child_map.base_) 79 return false; 80 81 // The child in iterator->second contains the specified address. Find out 82 // if it has a more-specific descendant that also contains it. If it does, 83 // it will set |entry| appropriately. If not, set |entry| to the child. 84 if (!child_map.RetrieveRange(address, entry)) 85 entry = child_map.entry_ptr_; 86 87 return true; 88 } 89 90 } // namespace google_breakpad 91 92 #endif // PROCESSOR_STATIC_CONTAINED_RANGE_MAP_INL_H__ 93