From 8c2a4def4ecfbf6293b27eff4359a274e9774b4e Mon Sep 17 00:00:00 2001 From: mmentovai Date: Wed, 20 Sep 2006 16:20:15 +0000 Subject: Handle frame pointer omission (#21), part 1: ContainedRangeMap. r=bryner. - ContainedRangeMap is the data structure that will be used to store and look up debugging information for frames by instruction address. The debugging information includes a way to locate the calling frame in the absence of a saved frame pointer. - Restructure RangeMap into an -inl file to match ContainedRangeMap. http://groups.google.com/group/airbag-dev/browse_thread/thread/c5823bfc1828ed42 git-svn-id: http://google-breakpad.googlecode.com/svn/trunk@29 4c0a9323-5329-0410-9bdc-e9ce6186880e --- src/processor/contained_range_map-inl.h | 157 +++++++++++++++++ src/processor/contained_range_map.h | 131 ++++++++++++++ src/processor/contained_range_map_unittest.cc | 238 ++++++++++++++++++++++++++ src/processor/minidump.cc | 1 + src/processor/range_map-inl.h | 101 +++++++++++ src/processor/range_map.h | 71 +------- src/processor/range_map_unittest.cc | 2 +- src/processor/source_line_resolver.cc | 2 +- 8 files changed, 632 insertions(+), 71 deletions(-) create mode 100644 src/processor/contained_range_map-inl.h create mode 100644 src/processor/contained_range_map.h create mode 100644 src/processor/contained_range_map_unittest.cc create mode 100644 src/processor/range_map-inl.h (limited to 'src') diff --git a/src/processor/contained_range_map-inl.h b/src/processor/contained_range_map-inl.h new file mode 100644 index 00000000..4b22e376 --- /dev/null +++ b/src/processor/contained_range_map-inl.h @@ -0,0 +1,157 @@ +// Copyright (C) 2006 Google Inc. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +// contained_range_map-inl.h: Hierarchically-organized range map implementation. +// +// See contained_range_map.h for documentation. +// +// Author: Mark Mentovai + +#ifndef PROCESSOR_CONTAINED_RANGE_MAP_INL_H__ +#define PROCESSOR_CONTAINED_RANGE_MAP_INL_H__ + + +#include "processor/contained_range_map.h" + + +namespace google_airbag { + + +template +ContainedRangeMap::~ContainedRangeMap() { + // Clear frees the children pointed to by the map, and frees the map itself. + Clear(); +} + + +template +bool ContainedRangeMap::StoreRange( + const AddressType &base, const AddressType &size, const EntryType &entry) { + AddressType high = base + size - 1; + + // Check for undersize or overflow. + if (size <= 0 || high < base) + return false; + + if (!map_) + map_ = new AddressToRangeMap(); + + MapIterator iterator_base = map_->lower_bound(base); + MapIterator iterator_high = map_->lower_bound(high); + MapConstIterator iterator_end = map_->end(); + + if (iterator_base == iterator_high && iterator_base != iterator_end && + base >= iterator_base->second->base_) { + // The new range is entirely within an existing child range. + + // If the new range's geometry is exactly equal to an existing child + // range's, it violates the containment rules, and an attempt to store + // it must fail. iterator_base->first contains the key, which was the + // containing child's high address. + if (iterator_base->second->base_ == base && iterator_base->first == high) + return false; + + // Pass the new range on to the child to attempt to store. + return iterator_base->second->StoreRange(base, size, entry); + } + + // iterator_high might refer to an irrelevant range: one whose base address + // is higher than the new range's high address. Set contains_high to true + // only if iterator_high refers to a range that is at least partially + // within the new range. + bool contains_high = iterator_high != iterator_end && + high >= iterator_high->second->base_; + + // If the new range encompasses any existing child ranges, it must do so + // fully. Partial containment isn't allowed. + if ((iterator_base != iterator_end && base > iterator_base->second->base_) || + (contains_high && high < iterator_high->first)) { + return false; + } + + // When copying and erasing contained ranges, the "end" iterator needs to + // point one past the last item of the range to copy. If contains_high is + // false, the iterator's already in the right place; the increment is safe + // because contains_high can't be true if iterator_high == iterator_end. + if (contains_high) + ++iterator_high; + + // Optimization: if the iterators are equal, no child ranges would be + // moved. Create the new child range with a NULL map to conserve space + // in leaf nodes, of which there will be many. + AddressToRangeMap *child_map = NULL; + + if (iterator_base != iterator_high) { + // The children of this range that are contained by the new range must + // be transferred over to the new range. Create the new child range map + // and copy the pointers to range maps it should contain into it. + child_map = new AddressToRangeMap(iterator_base, iterator_high); + + // Remove the copied child pointers from this range's map of children. + map_->erase(iterator_base, iterator_high); + } + + // Store the new range in the map by its high address. Any children that + // the new child range contains were formerly children of this range but + // are now this range's grandchildren. Ownership of these is transferred + // to the new child range. + map_->insert(MapValue(high, + new ContainedRangeMap(base, entry, child_map))); + return true; +} + + +template +bool ContainedRangeMap::RetrieveRange( + const AddressType &address, EntryType *entry) const { + if (!entry || !map_) + return false; + + // Get an iterator to the child range whose high address is equal to or + // greater than the supplied address. If the supplied address is higher + // than all of the high addresses in the range, then this range does not + // contain a child at address, so return false. If the supplied address + // is lower than the base address of the child range, then it is not within + // the child range, so return false. + MapConstIterator iterator = map_->lower_bound(address); + if (iterator == map_->end() || address < iterator->second->base_) + return false; + + // The child in iterator->second contains the specified address. Find out + // if it has a more-specific descendant that also contains it. If it does, + // it will set |entry| appropriately. If not, set |entry| to the child. + if (!iterator->second->RetrieveRange(address, entry)) + *entry = iterator->second->entry_; + + return true; +} + + +template +void ContainedRangeMap::Clear() { + if (map_) { + MapConstIterator end = map_->end(); + for (MapConstIterator child = map_->begin(); child != end; ++child) + delete child->second; + + delete map_; + map_ = NULL; + } +} + + +} // namespace google_airbag + + +#endif // PROCESSOR_CONTAINED_RANGE_MAP_INL_H__ diff --git a/src/processor/contained_range_map.h b/src/processor/contained_range_map.h new file mode 100644 index 00000000..7fe14b6d --- /dev/null +++ b/src/processor/contained_range_map.h @@ -0,0 +1,131 @@ +// Copyright (C) 2006 Google Inc. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +// contained_range_map.h: Hierarchically-organized range maps. +// +// A contained range map is similar to a standard range map, except it allows +// objects to be organized hierarchically. A contained range map allows +// objects to contain other objects. It is not sensitive to the order that +// objects are added to the map: larger, more general, containing objects +// may be added either before or after smaller, more specific, contained +// ones. +// +// Contained range maps guarantee that each object may only contain smaller +// objects than itself, and that a parent object may only contain child +// objects located entirely within the parent's address space. Attempts +// to introduce objects (via StoreRange) that violate these rules will fail. +// Retrieval (via RetrieveRange) always returns the most specific (smallest) +// object that contains the address being queried. Note that while it is +// not possible to insert two objects into a map that have exactly the same +// geometry (base address and size), it is possible to completely mask a +// larger object by inserting smaller objects that entirely fill the larger +// object's address space. +// +// Internally, contained range maps are implemented as a tree. Each tree +// node except for the root node describes an object in the map. Each node +// maintains its list of children in a map similar to a standard range map, +// keyed by the highest address that each child occupies. Each node's +// children occupy address ranges entirely within the node. The root node +// is the only node directly accessible to the user, and represents the +// entire address space. +// +// Author: Mark Mentovai + +#ifndef PROCESSOR_CONTAINED_RANGE_MAP_H__ +#define PROCESSOR_CONTAINED_RANGE_MAP_H__ + + +#include + + +namespace google_airbag { + + +template +class ContainedRangeMap { + public: + // The default constructor creates a ContainedRangeMap with no geometry + // and no entry, and as such is only suitable for the root node of a + // ContainedRangeMap tree. + ContainedRangeMap() : base_(), entry_(), map_(NULL) {} + + ~ContainedRangeMap(); + + // Inserts a range into the map. If the new range is encompassed by + // an existing child range, the new range is passed into the child range's + // StoreRange method. If the new range encompasses any existing child + // ranges, those child ranges are moved to the new range, becoming + // grandchildren of this ContainedRangeMap. Returns false for a + // parameter error, or if the ContainedRangeMap hierarchy guarantees + // would be violated. + bool StoreRange(const AddressType &base, + const AddressType &size, + const EntryType &entry); + + // Retrieves the most specific (smallest) descendant range encompassing + // the specified address. This method will only return entries held by + // child ranges, and not the entry contained by |this|. This is necessary + // to support a sparsely-populated root range. If no descendant range + // encompasses the address, or if there is a parameter error, returns + // false. + bool RetrieveRange(const AddressType &address, EntryType *entry) const; + + // Removes all children. Note that Clear only removes descendants, + // leaving the node on which it is called intact. Because the only + // meaningful things contained by a root node are descendants, this + // is sufficient to restore an entire ContainedRangeMap to its initial + // empty state when called on the root node. + void Clear(); + + private: + // AddressToRangeMap stores pointers. This makes reparenting simpler in + // StoreRange, because it doesn't need to copy entire objects. + typedef std::map AddressToRangeMap; + typedef typename AddressToRangeMap::const_iterator MapConstIterator; + typedef typename AddressToRangeMap::iterator MapIterator; + typedef typename AddressToRangeMap::value_type MapValue; + + // Creates a new ContainedRangeMap with the specified base address, entry, + // and initial child map, which may be NULL. This is only used internally + // by ContainedRangeMap when it creates a new child. + ContainedRangeMap(const AddressType &base, const EntryType &entry, + AddressToRangeMap *map) + : base_(base), entry_(entry), map_(map) {} + + // The base address of this range. The high address does not need to + // be stored, because it is used as the key to an object in its parent's + // map, and all ContainedRangeMaps except for the root range are contained + // within maps. The root range does not actually contain an entry, so its + // base_ field is meaningless, and the fact that it has no parent and thus + // no key is unimportant. For this reason, the base_ field should only be + // is accessed on child ContainedRangeMap objects, and never on |this|. + const AddressType base_; + + // The entry corresponding to this range. The root range does not + // actually contain an entry, so its entry_ field is meaningless. For + // this reason, the entry_ field should only be accessed on child + // ContainedRangeMap objects, and never on |this|. + const EntryType entry_; + + // The map containing child ranges, keyed by each child range's high + // address. This is a pointer to avoid allocating map structures for + // leaf nodes, where they are not needed. + AddressToRangeMap *map_; +}; + + +} // namespace google_airbag + + +#endif // PROCESSOR_CONTAINED_RANGE_MAP_H__ diff --git a/src/processor/contained_range_map_unittest.cc b/src/processor/contained_range_map_unittest.cc new file mode 100644 index 00000000..ad918499 --- /dev/null +++ b/src/processor/contained_range_map_unittest.cc @@ -0,0 +1,238 @@ +// Copyright (C) 2006 Google Inc. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +// contained_range_map_unittest.cc: Unit tests for ContainedRangeMap +// +// Author: Mark Mentovai + +#include + +#include "processor/contained_range_map-inl.h" + + +#define ASSERT_TRUE(condition) \ + if (!(condition)) { \ + fprintf(stderr, "FAIL: %s @ %s:%d\n", #condition, __FILE__, __LINE__); \ + return false; \ + } + +#define ASSERT_FALSE(condition) ASSERT_TRUE(!(condition)) + + +using google_airbag::ContainedRangeMap; + + +static bool RunTests() { + ContainedRangeMap crm; + + // First, do the StoreRange tests. This validates the containment + // rules. + ASSERT_TRUE (crm.StoreRange(10, 10, 1)); + ASSERT_FALSE(crm.StoreRange(10, 10, 2)); // exactly equal to 1 + ASSERT_FALSE(crm.StoreRange(11, 10, 3)); // begins inside 1 and extends up + ASSERT_FALSE(crm.StoreRange( 9, 10, 4)); // begins below 1 and ends inside + ASSERT_TRUE (crm.StoreRange(11, 9, 5)); // contained by existing + ASSERT_TRUE (crm.StoreRange(12, 7, 6)); + ASSERT_TRUE (crm.StoreRange( 9, 12, 7)); // contains existing + ASSERT_TRUE (crm.StoreRange( 9, 13, 8)); + ASSERT_TRUE (crm.StoreRange( 8, 14, 9)); + ASSERT_TRUE (crm.StoreRange(30, 3, 10)); + ASSERT_TRUE (crm.StoreRange(33, 3, 11)); + ASSERT_TRUE (crm.StoreRange(30, 6, 12)); // storable but totally masked + ASSERT_TRUE (crm.StoreRange(40, 8, 13)); // will be totally masked + ASSERT_TRUE (crm.StoreRange(40, 4, 14)); + ASSERT_TRUE (crm.StoreRange(44, 4, 15)); + ASSERT_FALSE(crm.StoreRange(32, 10, 16)); // begins in #10, ends in #14 + ASSERT_FALSE(crm.StoreRange(50, 0, 17)); // zero length + ASSERT_TRUE (crm.StoreRange(50, 10, 18)); + ASSERT_TRUE (crm.StoreRange(50, 1, 19)); + ASSERT_TRUE (crm.StoreRange(59, 1, 20)); + ASSERT_TRUE (crm.StoreRange(60, 1, 21)); + ASSERT_TRUE (crm.StoreRange(69, 1, 22)); + ASSERT_TRUE (crm.StoreRange(60, 10, 23)); + ASSERT_TRUE (crm.StoreRange(68, 1, 24)); + ASSERT_TRUE (crm.StoreRange(61, 1, 25)); + ASSERT_TRUE (crm.StoreRange(61, 8, 26)); + ASSERT_FALSE(crm.StoreRange(59, 9, 27)); + ASSERT_FALSE(crm.StoreRange(59, 10, 28)); + ASSERT_FALSE(crm.StoreRange(59, 11, 29)); + ASSERT_TRUE (crm.StoreRange(70, 10, 30)); + ASSERT_TRUE (crm.StoreRange(74, 2, 31)); + ASSERT_TRUE (crm.StoreRange(77, 2, 32)); + ASSERT_FALSE(crm.StoreRange(72, 6, 33)); + ASSERT_TRUE (crm.StoreRange(80, 3, 34)); + ASSERT_TRUE (crm.StoreRange(81, 1, 35)); + ASSERT_TRUE (crm.StoreRange(82, 1, 36)); + ASSERT_TRUE (crm.StoreRange(83, 3, 37)); + ASSERT_TRUE (crm.StoreRange(84, 1, 38)); + ASSERT_TRUE (crm.StoreRange(83, 1, 39)); + ASSERT_TRUE (crm.StoreRange(86, 5, 40)); + ASSERT_TRUE (crm.StoreRange(88, 1, 41)); + ASSERT_TRUE (crm.StoreRange(90, 1, 42)); + ASSERT_TRUE (crm.StoreRange(86, 1, 43)); + ASSERT_TRUE (crm.StoreRange(87, 1, 44)); + ASSERT_TRUE (crm.StoreRange(89, 1, 45)); + ASSERT_TRUE (crm.StoreRange(87, 4, 46)); + ASSERT_TRUE (crm.StoreRange(87, 3, 47)); + ASSERT_FALSE(crm.StoreRange(86, 2, 48)); + + // Each element in test_data contains the expected result when calling + // RetrieveRange on an address. + const int test_data[] = { + 0, // 0 + 0, // 1 + 0, // 2 + 0, // 3 + 0, // 4 + 0, // 5 + 0, // 6 + 0, // 7 + 9, // 8 + 7, // 9 + 1, // 10 + 5, // 11 + 6, // 12 + 6, // 13 + 6, // 14 + 6, // 15 + 6, // 16 + 6, // 17 + 6, // 18 + 5, // 19 + 7, // 20 + 8, // 21 + 0, // 22 + 0, // 23 + 0, // 24 + 0, // 25 + 0, // 26 + 0, // 27 + 0, // 28 + 0, // 29 + 10, // 30 + 10, // 31 + 10, // 32 + 11, // 33 + 11, // 34 + 11, // 35 + 0, // 36 + 0, // 37 + 0, // 38 + 0, // 39 + 14, // 40 + 14, // 41 + 14, // 42 + 14, // 43 + 15, // 44 + 15, // 45 + 15, // 46 + 15, // 47 + 0, // 48 + 0, // 49 + 19, // 50 + 18, // 51 + 18, // 52 + 18, // 53 + 18, // 54 + 18, // 55 + 18, // 56 + 18, // 57 + 18, // 58 + 20, // 59 + 21, // 60 + 25, // 61 + 26, // 62 + 26, // 63 + 26, // 64 + 26, // 65 + 26, // 66 + 26, // 67 + 24, // 68 + 22, // 69 + 30, // 70 + 30, // 71 + 30, // 72 + 30, // 73 + 31, // 74 + 31, // 75 + 30, // 76 + 32, // 77 + 32, // 78 + 30, // 79 + 34, // 80 + 35, // 81 + 36, // 82 + 39, // 83 + 38, // 84 + 37, // 85 + 43, // 86 + 44, // 87 + 41, // 88 + 45, // 89 + 42, // 90 + 0, // 91 + 0, // 92 + 0, // 93 + 0, // 94 + 0, // 95 + 0, // 96 + 0, // 97 + 0, // 98 + 0 // 99 + }; + unsigned int test_high = sizeof(test_data) / sizeof(int); + + // Now, do the RetrieveRange tests. This further validates that the + // objects were stored properly and that retrieval returns the correct + // object. + // If GENERATE_TEST_DATA is defined, instead of the retrieval tests, a + // new test_data array will be printed. Exercise caution when doing this. + // Be sure to verify the results manually! +#ifdef GENERATE_TEST_DATA + printf(" const int test_data[] = {\n"); +#endif // GENERATE_TEST_DATA + + for (unsigned int address = 0; address < test_high; ++address) { + int value; + if (!crm.RetrieveRange(address, &value)) + value = 0; + +#ifndef GENERATE_TEST_DATA + // Don't use ASSERT inside the loop because it won't show the failed + // |address|, and the line number will always be the same. That makes + // it difficult to figure out which test failed. + if (value != test_data[address]) { + fprintf(stderr, "FAIL: retrieve %d expected %d observed %d @ %s:%d\n", + address, test_data[address], value, __FILE__, __LINE__); + return false; + } +#else // !GENERATE_TEST_DATA + printf(" %d%c%s // %d\n", value, + address == test_high - 1 ? ' ' : ',', + value < 10 ? " " : "", + address); +#endif // !GENERATE_TEST_DATA + } + +#ifdef GENERATE_TEST_DATA + printf(" };\n"); +#endif // GENERATE_TEST_DATA + + return true; +} + + +int main(int argc, char **argv) { + return RunTests() ? 0 : 1; +} diff --git a/src/processor/minidump.cc b/src/processor/minidump.cc index a0b0ace2..087eaded 100644 --- a/src/processor/minidump.cc +++ b/src/processor/minidump.cc @@ -38,6 +38,7 @@ typedef SSIZE_T ssize_t; #include #include "processor/minidump.h" +#include "processor/range_map-inl.h" namespace google_airbag { diff --git a/src/processor/range_map-inl.h b/src/processor/range_map-inl.h new file mode 100644 index 00000000..4ba70933 --- /dev/null +++ b/src/processor/range_map-inl.h @@ -0,0 +1,101 @@ +// Copyright (C) 2006 Google Inc. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +// range_map-inl.h: Range map implementation. +// +// See range_map.h for documentation. +// +// Author: Mark Mentovai + +#ifndef PROCESSOR_RANGE_MAP_INL_H__ +#define PROCESSOR_RANGE_MAP_INL_H__ + + +#include "processor/range_map.h" + + +namespace google_airbag { + + +template +bool RangeMap::StoreRange(const AddressType &base, + const AddressType &size, + const EntryType &entry) { + AddressType high = base + size - 1; + + // Check for undersize or overflow. + if (size <= 0 || high < base) + return false; + + // Ensure that this range does not overlap with another one already in the + // map. + MapConstIterator iterator_base = map_.lower_bound(base); + MapConstIterator iterator_high = map_.lower_bound(high); + + if (iterator_base != iterator_high) { + // Some other range begins in the space used by this range. It may be + // contained within the space used by this range, or it may extend lower. + // Regardless, it is an error. + return false; + } + + if (iterator_high != map_.end()) { + if (iterator_high->second.base() <= high) { + // The range above this one overlaps with this one. It may fully + // contain this range, or it may begin within this range and extend + // higher. Regardless, it's an error. + return false; + } + } + + // Store the range in the map by its high address, so that lower_bound can + // be used to quickly locate a range by address. + map_.insert(MapValue(high, Range(base, entry))); + return true; +} + + +template +bool RangeMap::RetrieveRange( + const AddressType &address, EntryType *entry) const { + if (!entry) + return false; + + MapConstIterator iterator = map_.lower_bound(address); + if (iterator == map_.end()) + return false; + + // The map is keyed by the high address of each range, so |address| is + // guaranteed to be lower than the range's high address. If |range| is + // not directly preceded by another range, it's possible for address to + // be below the range's low address, though. When that happens, address + // references something not within any range, so return false. + if (address < iterator->second.base()) + return false; + + *entry = iterator->second.entry(); + return true; +} + + +template +void RangeMap::Clear() { + map_.clear(); +} + + +} // namespace google_airbag + + +#endif // PROCESSOR_RANGE_MAP_INL_H__ diff --git a/src/processor/range_map.h b/src/processor/range_map.h index 1395c924..06015c98 100644 --- a/src/processor/range_map.h +++ b/src/processor/range_map.h @@ -72,81 +72,14 @@ class RangeMap { // Convenience types. typedef std::map AddressToRangeMap; - typedef typename AddressToRangeMap::const_iterator const_iterator; - typedef typename AddressToRangeMap::value_type value_type; + typedef typename AddressToRangeMap::const_iterator MapConstIterator; + typedef typename AddressToRangeMap::value_type MapValue; // Maps the high address of each range to a EntryType. AddressToRangeMap map_; }; -template -bool RangeMap::StoreRange(const AddressType &base, - const AddressType &size, - const EntryType &entry) { - AddressType high = base + size - 1; - - // Check for undersize or overflow. - if (size <= 0 || high < base) - return false; - - // Ensure that this range does not overlap with another one already in the - // map. - const_iterator iterator_base = map_.lower_bound(base); - const_iterator iterator_high = map_.lower_bound(high); - - if (iterator_base != iterator_high) { - // Some other range begins in the space used by this range. It may be - // contained within the space used by this range, or it may extend lower. - // Regardless, it is an error. - return false; - } - - if (iterator_high != map_.end()) { - if (iterator_high->second.base() <= high) { - // The range above this one overlaps with this one. It may fully - // contain this range, or it may begin within this range and extend - // higher. Regardless, it's an error. - return false; - } - } - - // Store the range in the map by its high address, so that lower_bound can - // be used to quickly locate a range by address. - map_.insert(value_type(high, Range(base, entry))); - return true; -} - - -template -bool RangeMap::RetrieveRange( - const AddressType &address, EntryType *entry) const { - if (!entry) - return false; - - const_iterator iterator = map_.lower_bound(address); - if (iterator == map_.end()) - return false; - - // The map is keyed by the high address of each range, so |address| is - // guaranteed to be lower than the range's high address. If |range| is - // not directly preceded by another range, it's possible for address to - // be below the range's low address, though. When that happens, address - // references something not within any range, so return false. - if (address < iterator->second.base()) - return false; - - *entry = iterator->second.entry(); - return true; -} - - -template -void RangeMap::Clear() { - map_.clear(); -} - - } // namespace google_airbag diff --git a/src/processor/range_map_unittest.cc b/src/processor/range_map_unittest.cc index ecb76c79..02b2fdbe 100644 --- a/src/processor/range_map_unittest.cc +++ b/src/processor/range_map_unittest.cc @@ -21,7 +21,7 @@ #include #include -#include "processor/range_map.h" +#include "processor/range_map-inl.h" using std::auto_ptr; diff --git a/src/processor/source_line_resolver.cc b/src/processor/source_line_resolver.cc index 00acce1e..e6edd2c9 100644 --- a/src/processor/source_line_resolver.cc +++ b/src/processor/source_line_resolver.cc @@ -20,7 +20,7 @@ #include "processor/source_line_resolver.h" #include "google/stack_frame.h" #include "processor/linked_ptr.h" -#include "processor/range_map.h" +#include "processor/range_map-inl.h" using std::map; using std::vector; -- cgit v1.2.1