michael@0: // Copyright (c) 2006, Google Inc. michael@0: // All rights reserved. michael@0: // michael@0: // Redistribution and use in source and binary forms, with or without michael@0: // modification, are permitted provided that the following conditions are michael@0: // met: michael@0: // michael@0: // * Redistributions of source code must retain the above copyright michael@0: // notice, this list of conditions and the following disclaimer. michael@0: // * Redistributions in binary form must reproduce the above michael@0: // copyright notice, this list of conditions and the following disclaimer michael@0: // in the documentation and/or other materials provided with the michael@0: // distribution. michael@0: // * Neither the name of Google Inc. nor the names of its michael@0: // contributors may be used to endorse or promote products derived from michael@0: // this software without specific prior written permission. michael@0: // michael@0: // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS michael@0: // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT michael@0: // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR michael@0: // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT michael@0: // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, michael@0: // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT michael@0: // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, michael@0: // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY michael@0: // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT michael@0: // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE michael@0: // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. michael@0: michael@0: // contained_range_map.h: Hierarchically-organized range maps. michael@0: // michael@0: // A contained range map is similar to a standard range map, except it allows michael@0: // objects to be organized hierarchically. A contained range map allows michael@0: // objects to contain other objects. It is not sensitive to the order that michael@0: // objects are added to the map: larger, more general, containing objects michael@0: // may be added either before or after smaller, more specific, contained michael@0: // ones. michael@0: // michael@0: // Contained range maps guarantee that each object may only contain smaller michael@0: // objects than itself, and that a parent object may only contain child michael@0: // objects located entirely within the parent's address space. Attempts michael@0: // to introduce objects (via StoreRange) that violate these rules will fail. michael@0: // Retrieval (via RetrieveRange) always returns the most specific (smallest) michael@0: // object that contains the address being queried. Note that while it is michael@0: // not possible to insert two objects into a map that have exactly the same michael@0: // geometry (base address and size), it is possible to completely mask a michael@0: // larger object by inserting smaller objects that entirely fill the larger michael@0: // object's address space. michael@0: // michael@0: // Internally, contained range maps are implemented as a tree. Each tree michael@0: // node except for the root node describes an object in the map. Each node michael@0: // maintains its list of children in a map similar to a standard range map, michael@0: // keyed by the highest address that each child occupies. Each node's michael@0: // children occupy address ranges entirely within the node. The root node michael@0: // is the only node directly accessible to the user, and represents the michael@0: // entire address space. michael@0: // michael@0: // Author: Mark Mentovai michael@0: michael@0: #ifndef PROCESSOR_CONTAINED_RANGE_MAP_H__ michael@0: #define PROCESSOR_CONTAINED_RANGE_MAP_H__ michael@0: michael@0: michael@0: #include michael@0: michael@0: michael@0: namespace google_breakpad { michael@0: michael@0: // Forward declarations (for later friend declarations of specialized template). michael@0: template class ContainedRangeMapSerializer; michael@0: michael@0: template michael@0: class ContainedRangeMap { michael@0: public: michael@0: // The default constructor creates a ContainedRangeMap with no geometry michael@0: // and no entry, and as such is only suitable for the root node of a michael@0: // ContainedRangeMap tree. michael@0: ContainedRangeMap() : base_(), entry_(), map_(NULL) {} michael@0: michael@0: ~ContainedRangeMap(); michael@0: michael@0: // Inserts a range into the map. If the new range is encompassed by michael@0: // an existing child range, the new range is passed into the child range's michael@0: // StoreRange method. If the new range encompasses any existing child michael@0: // ranges, those child ranges are moved to the new range, becoming michael@0: // grandchildren of this ContainedRangeMap. Returns false for a michael@0: // parameter error, or if the ContainedRangeMap hierarchy guarantees michael@0: // would be violated. michael@0: bool StoreRange(const AddressType &base, michael@0: const AddressType &size, michael@0: const EntryType &entry); michael@0: michael@0: // Retrieves the most specific (smallest) descendant range encompassing michael@0: // the specified address. This method will only return entries held by michael@0: // child ranges, and not the entry contained by |this|. This is necessary michael@0: // to support a sparsely-populated root range. If no descendant range michael@0: // encompasses the address, returns false. michael@0: bool RetrieveRange(const AddressType &address, EntryType *entry) const; michael@0: michael@0: // Removes all children. Note that Clear only removes descendants, michael@0: // leaving the node on which it is called intact. Because the only michael@0: // meaningful things contained by a root node are descendants, this michael@0: // is sufficient to restore an entire ContainedRangeMap to its initial michael@0: // empty state when called on the root node. michael@0: void Clear(); michael@0: michael@0: private: michael@0: friend class ContainedRangeMapSerializer; michael@0: friend class ModuleComparer; michael@0: michael@0: // AddressToRangeMap stores pointers. This makes reparenting simpler in michael@0: // StoreRange, because it doesn't need to copy entire objects. michael@0: typedef std::map AddressToRangeMap; michael@0: typedef typename AddressToRangeMap::const_iterator MapConstIterator; michael@0: typedef typename AddressToRangeMap::iterator MapIterator; michael@0: typedef typename AddressToRangeMap::value_type MapValue; michael@0: michael@0: // Creates a new ContainedRangeMap with the specified base address, entry, michael@0: // and initial child map, which may be NULL. This is only used internally michael@0: // by ContainedRangeMap when it creates a new child. michael@0: ContainedRangeMap(const AddressType &base, const EntryType &entry, michael@0: AddressToRangeMap *map) michael@0: : base_(base), entry_(entry), map_(map) {} michael@0: michael@0: // The base address of this range. The high address does not need to michael@0: // be stored, because it is used as the key to an object in its parent's michael@0: // map, and all ContainedRangeMaps except for the root range are contained michael@0: // within maps. The root range does not actually contain an entry, so its michael@0: // base_ field is meaningless, and the fact that it has no parent and thus michael@0: // no key is unimportant. For this reason, the base_ field should only be michael@0: // is accessed on child ContainedRangeMap objects, and never on |this|. michael@0: const AddressType base_; michael@0: michael@0: // The entry corresponding to this range. The root range does not michael@0: // actually contain an entry, so its entry_ field is meaningless. For michael@0: // this reason, the entry_ field should only be accessed on child michael@0: // ContainedRangeMap objects, and never on |this|. michael@0: const EntryType entry_; michael@0: michael@0: // The map containing child ranges, keyed by each child range's high michael@0: // address. This is a pointer to avoid allocating map structures for michael@0: // leaf nodes, where they are not needed. michael@0: AddressToRangeMap *map_; michael@0: }; michael@0: michael@0: michael@0: } // namespace google_breakpad michael@0: michael@0: michael@0: #endif // PROCESSOR_CONTAINED_RANGE_MAP_H__