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@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 | template <typename AddressType, typename EntryType> |
91 | bool StaticContainedRangeMap<AddressType, EntryType>::RetrieveRanges( |
92 | const AddressType& address, |
93 | std::vector<const EntryType*>& entries) const { |
94 | MapConstIterator iterator = map_.lower_bound(address); |
95 | if (iterator == map_.end()) |
96 | return false; |
97 | const char* memory_child = |
98 | reinterpret_cast<const char*>(iterator.GetValuePtr()); |
99 | StaticContainedRangeMap child_map(memory_child); |
100 | if (address < child_map.base_) |
101 | return false; |
102 | child_map.RetrieveRanges(address, entries); |
103 | entries.push_back(child_map.entry_ptr_); |
104 | return true; |
105 | } |
106 | |
107 | } // namespace google_breakpad |
108 | |
109 | #endif // PROCESSOR_STATIC_CONTAINED_RANGE_MAP_INL_H__ |
110 | |