1  // Copyright 2010 Google LLC
  2  //
  3  // Redistribution and use in source and binary forms, with or without
  4  // modification, are permitted provided that the following conditions are
  5  // met:
  6  //
  7  //     * Redistributions of source code must retain the above copyright
  8  // notice, this list of conditions and the following disclaimer.
  9  //     * Redistributions in binary form must reproduce the above
 10  // copyright notice, this list of conditions and the following disclaimer
 11  // in the documentation and/or other materials provided with the
 12  // distribution.
 13  //     * Neither the name of Google LLC nor the names of its
 14  // contributors may be used to endorse or promote products derived from
 15  // this software without specific prior written permission.
 16  //
 17  // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 18  // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 19  // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 20  // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 21  // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 22  // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 23  // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 24  // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 25  // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 26  // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 27  // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 28  
 29  // static_contained_range_map.h: StaticContainedRangeMap.
 30  //
 31  // StaticContainedRangeMap is similar to ContainedRangeMap.  However,
 32  // StaticContainedRangeMap wraps a StaticMap instead of std::map, and does not
 33  // support dynamic operations like StoreRange(...).
 34  // StaticContainedRangeMap provides same RetrieveRange(...) interfaces as
 35  // ContainedRangeMap.
 36  //
 37  // Please see contained_range_map.h for more documentation.
 38  //
 39  // Author: Siyang Xie (lambxsy@google.com)
 40  
 41  #ifndef PROCESSOR_STATIC_CONTAINED_RANGE_MAP_H__
 42  #define PROCESSOR_STATIC_CONTAINED_RANGE_MAP_H__
 43  
 44  #include <vector>
 45  #include "processor/static_map-inl.h"
 46  
 47  namespace google_breakpad {
 48  
 49  template<typename AddressType, typename EntryType>
 50  class StaticContainedRangeMap {
 51   public:
 52    StaticContainedRangeMap(): base_(), entry_size_(), entry_ptr_(), map_() { }
 53    explicit StaticContainedRangeMap(const char *base);
 54  
 55    // Retrieves the most specific (smallest) descendant range encompassing
 56    // the specified address.  This method will only return entries held by
 57    // child ranges, and not the entry contained by |this|.  This is necessary
 58    // to support a sparsely-populated root range.  If no descendant range
 59    // encompasses the address, returns false.
 60    bool RetrieveRange(const AddressType& address, const EntryType*& entry) const;
 61  
 62    // Retrieves the vector of entries encompassing the specified address from the
 63    // innermost entry to the outermost entry.
 64    bool RetrieveRanges(const AddressType& address,
 65                        std::vector<const EntryType*>& entry) const;
 66  
 67   private:
 68    friend class ModuleComparer;
 69    // AddressToRangeMap stores pointers.  This makes reparenting simpler in
 70    // StoreRange, because it doesn't need to copy entire objects.
 71    typedef StaticContainedRangeMap* SelfPtr;
 72    typedef
 73    StaticMap<AddressType, StaticContainedRangeMap> AddressToRangeMap;
 74    typedef typename AddressToRangeMap::const_iterator MapConstIterator;
 75  
 76    // The base address of this range.  The high address does not need to
 77    // be stored, because it is used as the key to an object in its parent's
 78    // map, and all ContainedRangeMaps except for the root range are contained
 79    // within maps.  The root range does not actually contain an entry, so its
 80    // base_ field is meaningless, and the fact that it has no parent and thus
 81    // no key is unimportant.  For this reason, the base_ field should only be
 82    // is accessed on child ContainedRangeMap objects, and never on |this|.
 83    AddressType base_;
 84  
 85    // The entry corresponding to this range.  The root range does not
 86    // actually contain an entry, so its entry_ field is meaningless.  For
 87    // this reason, the entry_ field should only be accessed on child
 88    // ContainedRangeMap objects, and never on |this|.
 89    uint32_t entry_size_;
 90    const EntryType *entry_ptr_;
 91  
 92    // The map containing child ranges, keyed by each child range's high
 93    // address.  This is a pointer to avoid allocating map structures for
 94    // leaf nodes, where they are not needed.
 95    AddressToRangeMap map_;
 96  };
 97  
 98  }  // namespace google_breakpad
 99  
100  
101  #endif  // PROCESSOR_STATIC_CONTAINED_RANGE_MAP_H__