1 files changed, 158 insertions, 0 deletions
diff --git a/src/processor/range_map.h b/src/processor/range_map.h
new file mode 100644
index 00000000..a55efb13
--- /dev/null
+++ b/src/processor/range_map.h
@@ -0,0 +1,158 @@
+// 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.h: Range maps.
+//
+// A range map associates a range of addresses with a specific object.  This
+// is useful when certain objects of variable size are located within an
+// address space.  The range map makes it simple to determine which object is
+// associated with a specific address, which may be any address within the
+// range associated with an object.
+//
+// Author: Mark Mentovai
+
+#ifndef PROCESSOR_RANGE_MAP_H__
+#define PROCESSOR_RANGE_MAP_H__
+
+
+#include <map>
+
+
+namespace google_airbag {
+
+
+using std::map;
+
+
+template<typename AddressType, typename EntryType>
+class RangeMap {
+  public:
+    RangeMap() : map_() {}
+
+    // Inserts a range into the map.  Returns false for a parameter error,
+    // or if the location of the range would conflict with a range already
+    // stored in the map.
+    bool StoreRange(const AddressType& base,
+                    const AddressType& size,
+                    const EntryType&   entry);
+
+    // Locates the range encompassing the supplied address.  If there is
+    // no such range, or if there is a parameter error, returns false.
+    bool RetrieveRange(const AddressType& address, EntryType* entry);
+
+    // Empties the range map, restoring it to the state it was when it was
+    // initially created.
+    void Clear();
+
+  private:
+    class Range {
+      public:
+        Range(const AddressType& base, const EntryType& entry)
+            : base_(base), entry_(entry) {}
+
+        AddressType base() const { return base_; }
+        EntryType entry() const { return entry_; }
+
+      private:
+        // The base address of the range.  The high address does not need to
+        // be stored, because RangeMap uses it as the key to the map.
+        const AddressType base_;
+
+        // The entry, owned by the Range object.
+        const EntryType   entry_;
+    };
+
+    typedef map<AddressType, Range> AddressToRangeMap;
+
+    // Can't depend on implicit typenames in a template
+    typedef typename AddressToRangeMap::const_iterator const_iterator;
+    typedef typename AddressToRangeMap::value_type value_type;
+
+    // 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) {
+  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
+
+
+#endif // PROCESSOR_RANGE_MAP_H__