1 // Copyright (c) 2006, 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 // contained_range_map.h: Hierarchically-organized range maps. 31 // 32 // A contained range map is similar to a standard range map, except it allows 33 // objects to be organized hierarchically. A contained range map allows 34 // objects to contain other objects. It is not sensitive to the order that 35 // objects are added to the map: larger, more general, containing objects 36 // may be added either before or after smaller, more specific, contained 37 // ones. 38 // 39 // Contained range maps guarantee that each object may only contain smaller 40 // objects than itself, and that a parent object may only contain child 41 // objects located entirely within the parent's address space. Attempts 42 // to introduce objects (via StoreRange) that violate these rules will fail. 43 // Retrieval (via RetrieveRange) always returns the most specific (smallest) 44 // object that contains the address being queried. Note that while it is 45 // not possible to insert two objects into a map that have exactly the same 46 // geometry (base address and size), it is possible to completely mask a 47 // larger object by inserting smaller objects that entirely fill the larger 48 // object's address space. 49 // 50 // Internally, contained range maps are implemented as a tree. Each tree 51 // node except for the root node describes an object in the map. Each node 52 // maintains its list of children in a map similar to a standard range map, 53 // keyed by the highest address that each child occupies. Each node's 54 // children occupy address ranges entirely within the node. The root node 55 // is the only node directly accessible to the user, and represents the 56 // entire address space. 57 // 58 // Author: Mark Mentovai 59 60 #ifndef PROCESSOR_CONTAINED_RANGE_MAP_H__ 61 #define PROCESSOR_CONTAINED_RANGE_MAP_H__ 62 63 64 #include <map> 65 66 67 namespace google_breakpad { 68 69 // Forward declarations (for later friend declarations of specialized template). 70 template<class, class> class ContainedRangeMapSerializer; 71 72 template<typename AddressType, typename EntryType> 73 class ContainedRangeMap { 74 public: 75 // The default constructor creates a ContainedRangeMap with no geometry 76 // and no entry, and as such is only suitable for the root node of a 77 // ContainedRangeMap tree. ContainedRangeMap()78 ContainedRangeMap() : base_(), entry_(), map_(NULL) {} 79 80 ~ContainedRangeMap(); 81 82 // Inserts a range into the map. If the new range is encompassed by 83 // an existing child range, the new range is passed into the child range's 84 // StoreRange method. If the new range encompasses any existing child 85 // ranges, those child ranges are moved to the new range, becoming 86 // grandchildren of this ContainedRangeMap. Returns false for a 87 // parameter error, or if the ContainedRangeMap hierarchy guarantees 88 // would be violated. 89 bool StoreRange(const AddressType &base, 90 const AddressType &size, 91 const EntryType &entry); 92 93 // Retrieves the most specific (smallest) descendant range encompassing 94 // the specified address. This method will only return entries held by 95 // child ranges, and not the entry contained by |this|. This is necessary 96 // to support a sparsely-populated root range. If no descendant range 97 // encompasses the address, returns false. 98 bool RetrieveRange(const AddressType &address, EntryType *entry) const; 99 100 // Removes all children. Note that Clear only removes descendants, 101 // leaving the node on which it is called intact. Because the only 102 // meaningful things contained by a root node are descendants, this 103 // is sufficient to restore an entire ContainedRangeMap to its initial 104 // empty state when called on the root node. 105 void Clear(); 106 107 private: 108 friend class ContainedRangeMapSerializer<AddressType, EntryType>; 109 friend class ModuleComparer; 110 111 // AddressToRangeMap stores pointers. This makes reparenting simpler in 112 // StoreRange, because it doesn't need to copy entire objects. 113 typedef std::map<AddressType, ContainedRangeMap *> AddressToRangeMap; 114 typedef typename AddressToRangeMap::const_iterator MapConstIterator; 115 typedef typename AddressToRangeMap::iterator MapIterator; 116 typedef typename AddressToRangeMap::value_type MapValue; 117 118 // Creates a new ContainedRangeMap with the specified base address, entry, 119 // and initial child map, which may be NULL. This is only used internally 120 // by ContainedRangeMap when it creates a new child. ContainedRangeMap(const AddressType & base,const EntryType & entry,AddressToRangeMap * map)121 ContainedRangeMap(const AddressType &base, const EntryType &entry, 122 AddressToRangeMap *map) 123 : base_(base), entry_(entry), map_(map) {} 124 125 // The base address of this range. The high address does not need to 126 // be stored, because it is used as the key to an object in its parent's 127 // map, and all ContainedRangeMaps except for the root range are contained 128 // within maps. The root range does not actually contain an entry, so its 129 // base_ field is meaningless, and the fact that it has no parent and thus 130 // no key is unimportant. For this reason, the base_ field should only be 131 // is accessed on child ContainedRangeMap objects, and never on |this|. 132 const AddressType base_; 133 134 // The entry corresponding to this range. The root range does not 135 // actually contain an entry, so its entry_ field is meaningless. For 136 // this reason, the entry_ field should only be accessed on child 137 // ContainedRangeMap objects, and never on |this|. 138 const EntryType entry_; 139 140 // The map containing child ranges, keyed by each child range's high 141 // address. This is a pointer to avoid allocating map structures for 142 // leaf nodes, where they are not needed. 143 AddressToRangeMap *map_; 144 }; 145 146 147 } // namespace google_breakpad 148 149 150 #endif // PROCESSOR_CONTAINED_RANGE_MAP_H__ 151