RangeMap.h revision 761133029ba2d5bb0c21c3a871dede340b2775fc
1257663e753af15633e48c7b00eb7b5880168090bGreg Clayton//===-- RangeMap.h ----------------------------------------------*- C++ -*-===// 2257663e753af15633e48c7b00eb7b5880168090bGreg Clayton// 3257663e753af15633e48c7b00eb7b5880168090bGreg Clayton// The LLVM Compiler Infrastructure 4257663e753af15633e48c7b00eb7b5880168090bGreg Clayton// 5257663e753af15633e48c7b00eb7b5880168090bGreg Clayton// This file is distributed under the University of Illinois Open Source 6257663e753af15633e48c7b00eb7b5880168090bGreg Clayton// License. See LICENSE.TXT for details. 7257663e753af15633e48c7b00eb7b5880168090bGreg Clayton// 8257663e753af15633e48c7b00eb7b5880168090bGreg Clayton//===----------------------------------------------------------------------===// 9257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 10257663e753af15633e48c7b00eb7b5880168090bGreg Clayton#ifndef liblldb_RangeMap_h_ 11257663e753af15633e48c7b00eb7b5880168090bGreg Clayton#define liblldb_RangeMap_h_ 12257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 13257663e753af15633e48c7b00eb7b5880168090bGreg Clayton#include "lldb/lldb-private.h" 14be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton#include "llvm/ADT/SmallVector.h" 15257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 16c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton// Uncomment to make sure all Range objects are sorted when needed 17c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton//#define ASSERT_RANGEMAP_ARE_SORTED 18c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton 19257663e753af15633e48c7b00eb7b5880168090bGreg Claytonnamespace lldb_private { 20257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 2161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton //---------------------------------------------------------------------- 2261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // Templatized classes for dealing with generic ranges and also 2361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // collections of ranges, or collections of ranges that have associated 2461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // data. 2561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton //---------------------------------------------------------------------- 2661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 2761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton //---------------------------------------------------------------------- 2861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // A simple range class where you get to define the type of the range 2961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // base "B", and the type used for the range byte size "S". 3061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton //---------------------------------------------------------------------- 3161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton template <typename B, typename S> 32257663e753af15633e48c7b00eb7b5880168090bGreg Clayton struct Range 33257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 3461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton typedef B BaseType; 3561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton typedef S SizeType; 3661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 3761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton BaseType base; 3861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton SizeType size; 39257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 40257663e753af15633e48c7b00eb7b5880168090bGreg Clayton Range () : 41257663e753af15633e48c7b00eb7b5880168090bGreg Clayton base (0), 42257663e753af15633e48c7b00eb7b5880168090bGreg Clayton size (0) 43257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 44257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 45257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 4661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton Range (BaseType b, SizeType s) : 47257663e753af15633e48c7b00eb7b5880168090bGreg Clayton base (b), 48257663e753af15633e48c7b00eb7b5880168090bGreg Clayton size (s) 49257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 50257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 51257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 52bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton void 53bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton Clear (BaseType b = 0) 54bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 55bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton base = b; 56bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton size = 0; 57bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 58bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 59257663e753af15633e48c7b00eb7b5880168090bGreg Clayton // Set the start value for the range, and keep the same size 6061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton BaseType 6161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton GetRangeBase () const 62257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 63257663e753af15633e48c7b00eb7b5880168090bGreg Clayton return base; 64257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 65257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 66257663e753af15633e48c7b00eb7b5880168090bGreg Clayton void 6761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton SetRangeBase (BaseType b) 68257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 69257663e753af15633e48c7b00eb7b5880168090bGreg Clayton base = b; 70257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 71257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 72bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton void 73bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton Slide (BaseType slide) 74bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 75bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton base += slide; 76bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 77bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 7861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton BaseType 7961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton GetRangeEnd () const 80257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 81257663e753af15633e48c7b00eb7b5880168090bGreg Clayton return base + size; 82257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 83257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 84257663e753af15633e48c7b00eb7b5880168090bGreg Clayton void 8561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton SetRangeEnd (BaseType end) 86257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 87257663e753af15633e48c7b00eb7b5880168090bGreg Clayton if (end > base) 88257663e753af15633e48c7b00eb7b5880168090bGreg Clayton size = end - base; 89257663e753af15633e48c7b00eb7b5880168090bGreg Clayton else 90257663e753af15633e48c7b00eb7b5880168090bGreg Clayton size = 0; 91257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 92257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 9361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton SizeType 9461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton GetByteSize () const 95257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 96257663e753af15633e48c7b00eb7b5880168090bGreg Clayton return size; 97257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 98257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 99257663e753af15633e48c7b00eb7b5880168090bGreg Clayton void 10061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton SetByteSize (SizeType s) 101257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 102257663e753af15633e48c7b00eb7b5880168090bGreg Clayton size = s; 103257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 104257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 105257663e753af15633e48c7b00eb7b5880168090bGreg Clayton bool 106257663e753af15633e48c7b00eb7b5880168090bGreg Clayton IsValid() const 107257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 108257663e753af15633e48c7b00eb7b5880168090bGreg Clayton return size > 0; 109257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 110257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 111257663e753af15633e48c7b00eb7b5880168090bGreg Clayton bool 11261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton Contains (BaseType r) const 113257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 11461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return (GetRangeBase() <= r) && (r < GetRangeEnd()); 115257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 116257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 117257663e753af15633e48c7b00eb7b5880168090bGreg Clayton bool 11861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton ContainsEndInclusive (BaseType r) const 119257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 12061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return (GetRangeBase() <= r) && (r <= GetRangeEnd()); 121257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 122257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 123257663e753af15633e48c7b00eb7b5880168090bGreg Clayton bool 124257663e753af15633e48c7b00eb7b5880168090bGreg Clayton Contains (const Range& range) const 125257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 12661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return Contains(range.GetRangeBase()) && ContainsEndInclusive(range.GetRangeEnd()); 127257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 128257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 129257663e753af15633e48c7b00eb7b5880168090bGreg Clayton bool 130bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton Overlap (const Range &rhs) const 131bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 132bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton const BaseType lhs_base = this->GetRangeBase(); 133bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton const BaseType rhs_base = rhs.GetRangeBase(); 134bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton const BaseType lhs_end = this->GetRangeEnd(); 135bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton const BaseType rhs_end = rhs.GetRangeEnd(); 136bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton bool result = (lhs_base <= rhs_end) && (lhs_end >= rhs_base); 137bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return result; 138bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 139bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 140bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton bool 141bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton operator < (const Range &rhs) const 142257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 143257663e753af15633e48c7b00eb7b5880168090bGreg Clayton if (base == rhs.base) 144257663e753af15633e48c7b00eb7b5880168090bGreg Clayton return size < rhs.size; 145257663e753af15633e48c7b00eb7b5880168090bGreg Clayton return base < rhs.base; 146257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 147257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 148257663e753af15633e48c7b00eb7b5880168090bGreg Clayton bool 149bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton operator == (const Range &rhs) const 150257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 151257663e753af15633e48c7b00eb7b5880168090bGreg Clayton return base == rhs.base && size == rhs.size; 152257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 153257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 154257663e753af15633e48c7b00eb7b5880168090bGreg Clayton bool 155bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton operator != (const Range &rhs) const 156257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 157257663e753af15633e48c7b00eb7b5880168090bGreg Clayton return base != rhs.base || size != rhs.size; 158257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 159257663e753af15633e48c7b00eb7b5880168090bGreg Clayton }; 16061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 16161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton //---------------------------------------------------------------------- 16261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // A range array class where you get to define the type of the ranges 16361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // that the collection contains. 16461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton //---------------------------------------------------------------------- 165257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 166be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton template <typename B, typename S, unsigned N> 16761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton class RangeArray 168257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 169bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton public: 170bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton typedef B BaseType; 171bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton typedef S SizeType; 17261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton typedef Range<B,S> Entry; 173be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton //typedef std::vector<Entry> Collection; 174be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typedef llvm::SmallVector<Entry, N> Collection; 17561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 176bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton RangeArray () : 177bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton m_entries () 17861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 17961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 18061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 18161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton ~RangeArray() 18261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 18361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 18461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 18561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton void 18661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton Append (const Entry &entry) 18761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 18861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton m_entries.push_back (entry); 18961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 19061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 191761133029ba2d5bb0c21c3a871dede340b2775fcGreg Clayton bool 192761133029ba2d5bb0c21c3a871dede340b2775fcGreg Clayton RemoveEntrtAtIndex (uint32_t idx) 193761133029ba2d5bb0c21c3a871dede340b2775fcGreg Clayton { 194761133029ba2d5bb0c21c3a871dede340b2775fcGreg Clayton if (idx < m_entries.size()) 195761133029ba2d5bb0c21c3a871dede340b2775fcGreg Clayton { 196761133029ba2d5bb0c21c3a871dede340b2775fcGreg Clayton m_entries.erase (m_entries.begin() + idx); 197761133029ba2d5bb0c21c3a871dede340b2775fcGreg Clayton return true; 198761133029ba2d5bb0c21c3a871dede340b2775fcGreg Clayton } 199761133029ba2d5bb0c21c3a871dede340b2775fcGreg Clayton return false; 200761133029ba2d5bb0c21c3a871dede340b2775fcGreg Clayton } 201761133029ba2d5bb0c21c3a871dede340b2775fcGreg Clayton 20261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton void 20361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton Sort () 20461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 20561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if (m_entries.size() > 1) 20661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton std::stable_sort (m_entries.begin(), m_entries.end()); 20761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 20861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 209c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 210c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton bool 211c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton IsSorted () const 212c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton { 213be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator pos, end, prev; 214c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton // First we determine if we can combine any of the Entry objects so we 215c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton // don't end up allocating and making a new collection for no reason 216c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 217c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton { 218c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton if (prev != end && *pos < *prev) 219c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton return false; 220c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton } 221c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton return true; 222c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton } 223c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#endif 22461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton void 225bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton CombineConsecutiveRanges () 22661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 227c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 228c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton assert (IsSorted()); 229c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#endif 230bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // Can't combine if ranges if we have zero or one range 231bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (m_entries.size() > 1) 23261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 233bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // The list should be sorted prior to calling this function 234be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::iterator pos; 235be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::iterator end; 236be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::iterator prev; 237bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton bool can_combine = false; 238bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // First we determine if we can combine any of the Entry objects so we 239bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // don't end up allocating and making a new collection for no reason 240bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 24161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 242bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (prev != end && prev->Overlap(*pos)) 243bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 244bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton can_combine = true; 245bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton break; 246bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 24761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 248bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 249bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // We we can combine at least one entry, then we make a new collection 250bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // and populate it accordingly, and then swap it into place. 251bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (can_combine) 25261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 253be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton Collection minimal_ranges; 254bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 255bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 256bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (prev != end && prev->Overlap(*pos)) 257bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton minimal_ranges.back().SetRangeEnd (std::max<BaseType>(prev->GetRangeEnd(), pos->GetRangeEnd())); 258bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton else 259bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton minimal_ranges.push_back (*pos); 260bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 261bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // Use the swap technique in case our new vector is much smaller. 262bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // We must swap when using the STL because std::vector objects never 263bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // release or reduce the memory once it has been allocated/reserved. 264bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton m_entries.swap (minimal_ranges); 26561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 26661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 26761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 268bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 269bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 270bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton BaseType 271bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton GetMinRangeBase (BaseType fail_value) const 272bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 273c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 274c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton assert (IsSorted()); 275c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#endif 276bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (m_entries.empty()) 277bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return fail_value; 278bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // m_entries must be sorted, so if we aren't empty, we grab the 279bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // first range's base 280bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return m_entries.front().GetRangeBase(); 281bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 282bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 283bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton BaseType 284bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton GetMaxRangeEnd (BaseType fail_value) const 285bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 286c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 287c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton assert (IsSorted()); 288c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#endif 289bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (m_entries.empty()) 290bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return fail_value; 291bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // m_entries must be sorted, so if we aren't empty, we grab the 292bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // last range's end 293bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return m_entries.back().GetRangeEnd(); 294bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 295bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 296bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton void 297bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton Slide (BaseType slide) 298bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 299be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::iterator pos, end; 300bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos) 301bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton pos->Slide (slide); 302bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 30361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 30461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton void 30561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton Clear () 30661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 30761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton m_entries.clear(); 30861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 30961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 31061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton bool 31161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton IsEmpty () const 31261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 31361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return m_entries.empty(); 31461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 31561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 31661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton size_t 317bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton GetSize () const 31861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 31961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return m_entries.size(); 32061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 32161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 32261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton const Entry * 323bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton GetEntryAtIndex (size_t i) const 32461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 32561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if (i<m_entries.size()) 32661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return &m_entries[i]; 32761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return NULL; 32861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 32961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 330bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // Clients must ensure that "i" is a valid index prior to calling this function 331bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton const Entry & 332bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton GetEntryRef (size_t i) const 333bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 334bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return m_entries[i]; 335bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 336bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 33761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton static bool 33861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton BaseLessThan (const Entry& lhs, const Entry& rhs) 33961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 34061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return lhs.GetRangeBase() < rhs.GetRangeBase(); 34161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 34261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 343bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton uint32_t 344bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton FindEntryIndexThatContains (B addr) const 345bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 346c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 347c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton assert (IsSorted()); 348c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#endif 349c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton if (!m_entries.empty()) 350bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 351bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton Entry entry (addr, 1); 352be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator begin = m_entries.begin(); 353be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator end = m_entries.end(); 354be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 355bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 356bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (pos != end && pos->Contains(addr)) 357bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 358bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return std::distance (begin, pos); 359bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 360bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton else if (pos != begin) 361bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 362bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton --pos; 363bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (pos->Contains(addr)) 364bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return std::distance (begin, pos); 365bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 366bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 367bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return UINT32_MAX; 368bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 369bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 37061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton const Entry * 37161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton FindEntryThatContains (B addr) const 37261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 373c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 374c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton assert (IsSorted()); 375c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#endif 376c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton if (!m_entries.empty()) 37761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 37861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton Entry entry (addr, 1); 379be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator begin = m_entries.begin(); 380be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator end = m_entries.end(); 381be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 38261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 38361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if (pos != end && pos->Contains(addr)) 38461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 38561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return &(*pos); 38661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 38761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton else if (pos != begin) 38861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 38961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton --pos; 39061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if (pos->Contains(addr)) 39161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 39261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return &(*pos); 39361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 39461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 39561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 39661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return NULL; 39761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 398bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 399bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton const Entry * 400bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton FindEntryThatContains (const Entry &range) const 401bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 402c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 403c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton assert (IsSorted()); 404c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#endif 405c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton if (!m_entries.empty()) 406bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 407be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator begin = m_entries.begin(); 408be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator end = m_entries.end(); 409be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator pos = std::lower_bound (begin, end, range, BaseLessThan); 410bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 411bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (pos != end && pos->Contains(range)) 412bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 413bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return &(*pos); 414bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 415bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton else if (pos != begin) 416bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 417bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton --pos; 418bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (pos->Contains(range)) 419bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 420bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return &(*pos); 421bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 422bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 423bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 424bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return NULL; 425bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 426bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 42761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton protected: 428be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton Collection m_entries; 42961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton }; 430257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 43161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton //---------------------------------------------------------------------- 43261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // A simple range with data class where you get to define the type of 43361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // the range base "B", the type used for the range byte size "S", and 43461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // the type for the associated data "T". 43561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton //---------------------------------------------------------------------- 43661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton template <typename B, typename S, typename T> 43761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton struct RangeData : public Range<B,S> 43861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 43961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton typedef T DataType; 44061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 44161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton DataType data; 44261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 44361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton RangeData () : 44461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton Range<B,S> (), 445257663e753af15633e48c7b00eb7b5880168090bGreg Clayton data () 446257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 447257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 44861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 44961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton RangeData (B base, S size, DataType d) : 45061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton Range<B,S> (base, size), 451257663e753af15633e48c7b00eb7b5880168090bGreg Clayton data (d) 452257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 453257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 45461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 455257663e753af15633e48c7b00eb7b5880168090bGreg Clayton bool 45661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton operator < (const RangeData &rhs) const 457257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 45861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if (this->base == rhs.base) 459257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 46061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if (this->size == rhs.size) 46161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return this->data < rhs.data; 462257663e753af15633e48c7b00eb7b5880168090bGreg Clayton else 46361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return this->size < rhs.size; 464257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 46561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return this->base < rhs.base; 466257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 46761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 468257663e753af15633e48c7b00eb7b5880168090bGreg Clayton bool 46961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton operator == (const RangeData &rhs) const 470257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 47161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return this->GetRangeBase() == rhs.GetRangeBase() && 47261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton this->GetByteSize() == rhs.GetByteSize() && 47361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton this->data == rhs.data; 474257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 47561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 476257663e753af15633e48c7b00eb7b5880168090bGreg Clayton bool 47761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton operator != (const RangeData &rhs) const 478257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 47961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return this->GetRangeBase() != rhs.GetRangeBase() || 48061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton this->GetByteSize() != rhs.GetByteSize() || 48161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton this->data != rhs.data; 482257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 483257663e753af15633e48c7b00eb7b5880168090bGreg Clayton }; 484257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 485be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton template <typename B, typename S, typename T, unsigned N> 48661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton class RangeDataArray 487257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 48861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton public: 48961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton typedef RangeData<B,S,T> Entry; 490be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton //typedef std::vector<Entry> Collection; 491be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typedef llvm::SmallVector<Entry, N> Collection; 492be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton 493be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton 49461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton RangeDataArray () 49561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 496257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 497257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 49861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton ~RangeDataArray() 49961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 50061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 50161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 50261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton void 50361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton Append (const Entry &entry) 504257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 50561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton m_entries.push_back (entry); 50661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 50761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 50861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton void 50961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton Sort () 51061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 51161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if (m_entries.size() > 1) 51261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton std::stable_sort (m_entries.begin(), m_entries.end()); 51361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 51461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 515c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 516c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton bool 517c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton IsSorted () const 518c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton { 519be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator pos, end, prev; 520c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton // First we determine if we can combine any of the Entry objects so we 521c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton // don't end up allocating and making a new collection for no reason 522c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 523c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton { 524c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton if (prev != end && *pos < *prev) 525c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton return false; 526c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton } 527c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton return true; 528c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton } 529c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#endif 530c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton 53161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton void 53261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton CombineConsecutiveEntriesWithEqualData () 53361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 534c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 535c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton assert (IsSorted()); 536c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#endif 537be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::iterator pos; 538be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::iterator end; 539be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::iterator prev; 54061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton bool can_combine = false; 54161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // First we determine if we can combine any of the Entry objects so we 54261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // don't end up allocating and making a new collection for no reason 543257663e753af15633e48c7b00eb7b5880168090bGreg Clayton for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 544257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 545257663e753af15633e48c7b00eb7b5880168090bGreg Clayton if (prev != end && prev->data == pos->data) 54661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 54761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton can_combine = true; 54861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton break; 54961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 550257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 551257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 55261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // We we can combine at least one entry, then we make a new collection 55361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // and populate it accordingly, and then swap it into place. 55461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if (can_combine) 555257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 556be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton Collection minimal_ranges; 55761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 55861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 55961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if (prev != end && prev->data == pos->data) 56061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton minimal_ranges.back().SetRangeEnd (pos->GetRangeEnd()); 56161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton else 56261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton minimal_ranges.push_back (*pos); 56361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 56461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // Use the swap technique in case our new vector is much smaller. 56561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // We must swap when using the STL because std::vector objects never 56661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // release or reduce the memory once it has been allocated/reserved. 56761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton m_entries.swap (minimal_ranges); 568257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 56961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 57061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 57161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton void 57261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton Clear () 57361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 57461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton m_entries.clear(); 57561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 57661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 57761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton bool 57861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton IsEmpty () const 57961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 58061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return m_entries.empty(); 58161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 58261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 58361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton size_t 584bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton GetSize () const 58561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 58661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return m_entries.size(); 58761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 58861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 58961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton const Entry * 590bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton GetEntryAtIndex (size_t i) const 59161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 59261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if (i<m_entries.size()) 59361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return &m_entries[i]; 59461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return NULL; 59561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 596bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 597bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // Clients must ensure that "i" is a valid index prior to calling this function 598bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton const Entry & 599bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton GetEntryRef (size_t i) const 600bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 601bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return m_entries[i]; 602bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 603bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 60461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton static bool 60561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton BaseLessThan (const Entry& lhs, const Entry& rhs) 60661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 60761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return lhs.GetRangeBase() < rhs.GetRangeBase(); 60861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 60961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 610bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton uint32_t 611bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton FindEntryIndexThatContains (B addr) const 612bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 613c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 614c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton assert (IsSorted()); 615c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#endif 616bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if ( !m_entries.empty() ) 617bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 618bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton Entry entry (addr, 1); 619be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator begin = m_entries.begin(); 620be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator end = m_entries.end(); 621be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 622bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 623bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (pos != end && pos->Contains(addr)) 624bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 625bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return std::distance (begin, pos); 626bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 627bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton else if (pos != begin) 628bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 629bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton --pos; 630bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (pos->Contains(addr)) 631bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return std::distance (begin, pos); 632bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 633bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 634bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return UINT32_MAX; 635bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 636bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 63761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton const Entry * 63861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton FindEntryThatContains (B addr) const 63961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 640c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 641c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton assert (IsSorted()); 642c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#endif 64361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if ( !m_entries.empty() ) 644257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 64561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton Entry entry; 64661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton entry.SetRangeBase(addr); 64761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton entry.SetByteSize(1); 648be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator begin = m_entries.begin(); 649be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator end = m_entries.end(); 650be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 65161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 65261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if (pos != end && pos->Contains(addr)) 653257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 654257663e753af15633e48c7b00eb7b5880168090bGreg Clayton return &(*pos); 655257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 65661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton else if (pos != begin) 65761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 65861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton --pos; 65961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if (pos->Contains(addr)) 66061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 66161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return &(*pos); 66261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 66361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 664257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 66561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return NULL; 666257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 66761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 668bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton const Entry * 669bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton FindEntryThatContains (const Entry &range) const 670bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 671c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 672c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton assert (IsSorted()); 673c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#endif 674bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if ( !m_entries.empty() ) 675bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 676be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator begin = m_entries.begin(); 677be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator end = m_entries.end(); 678be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator pos = std::lower_bound (begin, end, range, BaseLessThan); 679bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 680bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (pos != end && pos->Contains(range)) 681bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 682bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return &(*pos); 683bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 684bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton else if (pos != begin) 685bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 686bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton --pos; 687bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (pos->Contains(range)) 688bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 689bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return &(*pos); 690bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 691bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 692bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 693bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return NULL; 694bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 695bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 69646c9a355af9b39db78c006b2a5cbf97d3c58d947Greg Clayton Entry * 69746c9a355af9b39db78c006b2a5cbf97d3c58d947Greg Clayton Back() 69846c9a355af9b39db78c006b2a5cbf97d3c58d947Greg Clayton { 69946c9a355af9b39db78c006b2a5cbf97d3c58d947Greg Clayton if (!m_entries.empty()) 70046c9a355af9b39db78c006b2a5cbf97d3c58d947Greg Clayton return &m_entries.back(); 70146c9a355af9b39db78c006b2a5cbf97d3c58d947Greg Clayton return NULL; 70246c9a355af9b39db78c006b2a5cbf97d3c58d947Greg Clayton } 70346c9a355af9b39db78c006b2a5cbf97d3c58d947Greg Clayton 70446c9a355af9b39db78c006b2a5cbf97d3c58d947Greg Clayton const Entry * 70546c9a355af9b39db78c006b2a5cbf97d3c58d947Greg Clayton Back() const 70646c9a355af9b39db78c006b2a5cbf97d3c58d947Greg Clayton { 70746c9a355af9b39db78c006b2a5cbf97d3c58d947Greg Clayton if (!m_entries.empty()) 70846c9a355af9b39db78c006b2a5cbf97d3c58d947Greg Clayton return &m_entries.back(); 70946c9a355af9b39db78c006b2a5cbf97d3c58d947Greg Clayton return NULL; 71046c9a355af9b39db78c006b2a5cbf97d3c58d947Greg Clayton } 711bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 71261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton protected: 713be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton Collection m_entries; 71461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton }; 715257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 716257663e753af15633e48c7b00eb7b5880168090bGreg Clayton} // namespace lldb_private 717257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 718257663e753af15633e48c7b00eb7b5880168090bGreg Clayton#endif // liblldb_RangeMap_h_ 719