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

8 files changed, 632 insertions, 71 deletions

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<typename AddressType, typename EntryType>
+ContainedRangeMap<AddressType, EntryType>::~ContainedRangeMap() {
+  // Clear frees the children pointed to by the map, and frees the map itself.
+  Clear();
+}
+
+
+template<typename AddressType, typename EntryType>
+bool ContainedRangeMap<AddressType, EntryType>::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<typename AddressType, typename EntryType>
+bool ContainedRangeMap<AddressType, EntryType>::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<typename AddressType, typename EntryType>
+void ContainedRangeMap<AddressType, EntryType>::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 <map>
+
+
+namespace google_airbag {
+
+
+template<typename AddressType, typename EntryType>
+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<AddressType, ContainedRangeMap *> 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 <cstdio>
+
+#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<unsigned int, int> 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 <vector>
 
 #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<typename AddressType, typename EntryType>
+bool RangeMap<AddressType, EntryType>::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<typename AddressType, typename EntryType>
+bool RangeMap<AddressType, EntryType>::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<typename AddressType, typename EntryType>
+void RangeMap<AddressType, EntryType>::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<AddressType, Range> 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<typename AddressType, typename EntryType>
-bool RangeMap<AddressType, EntryType>::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<typename AddressType, typename EntryType>
-bool RangeMap<AddressType, EntryType>::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<typename AddressType, typename EntryType>
-void RangeMap<AddressType, EntryType>::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 <cstdio>
 #include <memory>
 
-#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;