17daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// Copyright (c) 2006, Google Inc. 27daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// All rights reserved. 38c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai// 47daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// Redistribution and use in source and binary forms, with or without 57daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// modification, are permitted provided that the following conditions are 67daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// met: 78c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai// 87daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// * Redistributions of source code must retain the above copyright 97daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// notice, this list of conditions and the following disclaimer. 107daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// * Redistributions in binary form must reproduce the above 117daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// copyright notice, this list of conditions and the following disclaimer 127daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// in the documentation and/or other materials provided with the 137daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// distribution. 147daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// * Neither the name of Google Inc. nor the names of its 157daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// contributors may be used to endorse or promote products derived from 167daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// this software without specific prior written permission. 178c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai// 187daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 197daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 207daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 217daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 227daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 237daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 247daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 257daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 267daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 277daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 287daf246e4baf0837e25429668cc23e92b6afe3b3mmentovai// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 298c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai 308c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai// contained_range_map.h: Hierarchically-organized range maps. 318c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai// 328c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai// A contained range map is similar to a standard range map, except it allows 338c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai// objects to be organized hierarchically. A contained range map allows 348c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai// objects to contain other objects. It is not sensitive to the order that 358c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai// objects are added to the map: larger, more general, containing objects 368c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai// may be added either before or after smaller, more specific, contained 378c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai// ones. 388c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai// 398c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai// Contained range maps guarantee that each object may only contain smaller 408c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai// objects than itself, and that a parent object may only contain child 418c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai// objects located entirely within the parent's address space. Attempts 428c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai// to introduce objects (via StoreRange) that violate these rules will fail. 438c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai// Retrieval (via RetrieveRange) always returns the most specific (smallest) 448c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai// object that contains the address being queried. Note that while it is 458c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai// not possible to insert two objects into a map that have exactly the same 468c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai// geometry (base address and size), it is possible to completely mask a 478c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai// larger object by inserting smaller objects that entirely fill the larger 488c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai// object's address space. 498c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai// 508c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai// Internally, contained range maps are implemented as a tree. Each tree 518c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai// node except for the root node describes an object in the map. Each node 528c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai// maintains its list of children in a map similar to a standard range map, 538c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai// keyed by the highest address that each child occupies. Each node's 548c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai// children occupy address ranges entirely within the node. The root node 558c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai// is the only node directly accessible to the user, and represents the 568c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai// entire address space. 578c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai// 588c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai// Author: Mark Mentovai 598c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai 608c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai#ifndef PROCESSOR_CONTAINED_RANGE_MAP_H__ 618c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai#define PROCESSOR_CONTAINED_RANGE_MAP_H__ 628c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai 638c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai 648c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai#include <map> 658c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai 668c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai 67e5dc60822e5938fea2ae892ccddb906641ba174emmentovainamespace google_breakpad { 688c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai 6908730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com// Forward declarations (for later friend declarations of specialized template). 7008730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.comtemplate<class, class> class ContainedRangeMapSerializer; 718c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai 728c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovaitemplate<typename AddressType, typename EntryType> 738c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovaiclass ContainedRangeMap { 748c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai public: 758c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai // The default constructor creates a ContainedRangeMap with no geometry 768c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai // and no entry, and as such is only suitable for the root node of a 778c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai // ContainedRangeMap tree. 788c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai ContainedRangeMap() : base_(), entry_(), map_(NULL) {} 798c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai 808c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai ~ContainedRangeMap(); 818c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai 828c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai // Inserts a range into the map. If the new range is encompassed by 838c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai // an existing child range, the new range is passed into the child range's 848c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai // StoreRange method. If the new range encompasses any existing child 858c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai // ranges, those child ranges are moved to the new range, becoming 868c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai // grandchildren of this ContainedRangeMap. Returns false for a 878c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai // parameter error, or if the ContainedRangeMap hierarchy guarantees 888c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai // would be violated. 898c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai bool StoreRange(const AddressType &base, 908c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai const AddressType &size, 918c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai const EntryType &entry); 9280e98391dc7ff361355e72c24c0fb222518bcdfcmmentovai 938c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai // Retrieves the most specific (smallest) descendant range encompassing 948c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai // the specified address. This method will only return entries held by 958c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai // child ranges, and not the entry contained by |this|. This is necessary 968c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai // to support a sparsely-populated root range. If no descendant range 9765571f17edb82d122b5f6dc741bd7d4b9e315e1bmmentovai // encompasses the address, returns false. 988c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai bool RetrieveRange(const AddressType &address, EntryType *entry) const; 998c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai 1008c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai // Removes all children. Note that Clear only removes descendants, 1018c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai // leaving the node on which it is called intact. Because the only 1028c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai // meaningful things contained by a root node are descendants, this 1038c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai // is sufficient to restore an entire ContainedRangeMap to its initial 1048c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai // empty state when called on the root node. 1058c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai void Clear(); 1068c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai 1078c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai private: 10808730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com friend class ContainedRangeMapSerializer<AddressType, EntryType>; 10941f998fe5a0630506d6d2a1bae78b1be179fe850SiyangXie@gmail.com friend class ModuleComparer; 11008730fc9a639e5b962f9a803ae8f5e91630e9484SiyangXie@gmail.com 1118c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai // AddressToRangeMap stores pointers. This makes reparenting simpler in 1128c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai // StoreRange, because it doesn't need to copy entire objects. 1138c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai typedef std::map<AddressType, ContainedRangeMap *> AddressToRangeMap; 1148c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai typedef typename AddressToRangeMap::const_iterator MapConstIterator; 1158c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai typedef typename AddressToRangeMap::iterator MapIterator; 1168c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai typedef typename AddressToRangeMap::value_type MapValue; 1178c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai 1188c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai // Creates a new ContainedRangeMap with the specified base address, entry, 1198c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai // and initial child map, which may be NULL. This is only used internally 1208c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai // by ContainedRangeMap when it creates a new child. 1218c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai ContainedRangeMap(const AddressType &base, const EntryType &entry, 1228c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai AddressToRangeMap *map) 1238c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai : base_(base), entry_(entry), map_(map) {} 1248c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai 1258c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai // The base address of this range. The high address does not need to 1268c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai // be stored, because it is used as the key to an object in its parent's 1278c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai // map, and all ContainedRangeMaps except for the root range are contained 1288c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai // within maps. The root range does not actually contain an entry, so its 1298c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai // base_ field is meaningless, and the fact that it has no parent and thus 1308c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai // no key is unimportant. For this reason, the base_ field should only be 1318c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai // is accessed on child ContainedRangeMap objects, and never on |this|. 1328c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai const AddressType base_; 1338c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai 1348c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai // The entry corresponding to this range. The root range does not 1358c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai // actually contain an entry, so its entry_ field is meaningless. For 1368c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai // this reason, the entry_ field should only be accessed on child 1378c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai // ContainedRangeMap objects, and never on |this|. 1388c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai const EntryType entry_; 1398c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai 1408c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai // The map containing child ranges, keyed by each child range's high 1418c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai // address. This is a pointer to avoid allocating map structures for 1428c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai // leaf nodes, where they are not needed. 1438c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai AddressToRangeMap *map_; 1448c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai}; 1458c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai 1468c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai 147e5dc60822e5938fea2ae892ccddb906641ba174emmentovai} // namespace google_breakpad 1488c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai 1498c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai 1508c2a4def4ecfbf6293b27eff4359a274e9774b4emmentovai#endif // PROCESSOR_CONTAINED_RANGE_MAP_H__ 151