RangeMap.h revision 464a5063bc59755cb6ec063d0b2491097302d2ab
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 13464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#include <vector> 14464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 15257663e753af15633e48c7b00eb7b5880168090bGreg Clayton#include "lldb/lldb-private.h" 16be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton#include "llvm/ADT/SmallVector.h" 17257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 18c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton// Uncomment to make sure all Range objects are sorted when needed 19c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton//#define ASSERT_RANGEMAP_ARE_SORTED 20c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton 21257663e753af15633e48c7b00eb7b5880168090bGreg Claytonnamespace lldb_private { 22257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 234aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 2461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton //---------------------------------------------------------------------- 254aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton // Templatized classes for dealing with generic ranges and also 2661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // collections of ranges, or collections of ranges that have associated 2761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // data. 2861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton //---------------------------------------------------------------------- 2961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 3061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton //---------------------------------------------------------------------- 3161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // A simple range class where you get to define the type of the range 3261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // base "B", and the type used for the range byte size "S". 3361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton //---------------------------------------------------------------------- 3461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton template <typename B, typename S> 35257663e753af15633e48c7b00eb7b5880168090bGreg Clayton struct Range 36257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 3761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton typedef B BaseType; 3861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton typedef S SizeType; 3961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 4061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton BaseType base; 4161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton SizeType size; 42257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 43257663e753af15633e48c7b00eb7b5880168090bGreg Clayton Range () : 44257663e753af15633e48c7b00eb7b5880168090bGreg Clayton base (0), 45257663e753af15633e48c7b00eb7b5880168090bGreg Clayton size (0) 46257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 47257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 48257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 4961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton Range (BaseType b, SizeType s) : 50257663e753af15633e48c7b00eb7b5880168090bGreg Clayton base (b), 51257663e753af15633e48c7b00eb7b5880168090bGreg Clayton size (s) 52257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 53257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 54257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 55bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton void 56bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton Clear (BaseType b = 0) 57bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 58bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton base = b; 59bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton size = 0; 60bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 61bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 62257663e753af15633e48c7b00eb7b5880168090bGreg Clayton // Set the start value for the range, and keep the same size 6361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton BaseType 6461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton GetRangeBase () const 65257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 66257663e753af15633e48c7b00eb7b5880168090bGreg Clayton return base; 67257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 68257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 69257663e753af15633e48c7b00eb7b5880168090bGreg Clayton void 7061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton SetRangeBase (BaseType b) 71257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 72257663e753af15633e48c7b00eb7b5880168090bGreg Clayton base = b; 73257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 74257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 75bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton void 76bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton Slide (BaseType slide) 77bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 78bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton base += slide; 79bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 80bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 8161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton BaseType 8261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton GetRangeEnd () const 83257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 84257663e753af15633e48c7b00eb7b5880168090bGreg Clayton return base + size; 85257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 86257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 87257663e753af15633e48c7b00eb7b5880168090bGreg Clayton void 8861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton SetRangeEnd (BaseType end) 89257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 90257663e753af15633e48c7b00eb7b5880168090bGreg Clayton if (end > base) 91257663e753af15633e48c7b00eb7b5880168090bGreg Clayton size = end - base; 92257663e753af15633e48c7b00eb7b5880168090bGreg Clayton else 93257663e753af15633e48c7b00eb7b5880168090bGreg Clayton size = 0; 94257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 95257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 9661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton SizeType 9761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton GetByteSize () const 98257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 99257663e753af15633e48c7b00eb7b5880168090bGreg Clayton return size; 100257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 101257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 102257663e753af15633e48c7b00eb7b5880168090bGreg Clayton void 10361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton SetByteSize (SizeType s) 104257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 105257663e753af15633e48c7b00eb7b5880168090bGreg Clayton size = s; 106257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 107257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 108257663e753af15633e48c7b00eb7b5880168090bGreg Clayton bool 109257663e753af15633e48c7b00eb7b5880168090bGreg Clayton IsValid() const 110257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 111257663e753af15633e48c7b00eb7b5880168090bGreg Clayton return size > 0; 112257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 113257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 114257663e753af15633e48c7b00eb7b5880168090bGreg Clayton bool 11561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton Contains (BaseType r) const 116257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 11761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return (GetRangeBase() <= r) && (r < GetRangeEnd()); 118257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 119257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 120257663e753af15633e48c7b00eb7b5880168090bGreg Clayton bool 12161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton ContainsEndInclusive (BaseType r) const 122257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 12361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return (GetRangeBase() <= r) && (r <= GetRangeEnd()); 124257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 125257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 126257663e753af15633e48c7b00eb7b5880168090bGreg Clayton bool 127257663e753af15633e48c7b00eb7b5880168090bGreg Clayton Contains (const Range& range) const 128257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 12961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return Contains(range.GetRangeBase()) && ContainsEndInclusive(range.GetRangeEnd()); 130257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 131257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 132257663e753af15633e48c7b00eb7b5880168090bGreg Clayton bool 133bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton Overlap (const Range &rhs) const 134bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 135bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton const BaseType lhs_base = this->GetRangeBase(); 136bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton const BaseType rhs_base = rhs.GetRangeBase(); 137bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton const BaseType lhs_end = this->GetRangeEnd(); 138bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton const BaseType rhs_end = rhs.GetRangeEnd(); 139bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton bool result = (lhs_base <= rhs_end) && (lhs_end >= rhs_base); 140bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return result; 141bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 142bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 143bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton bool 144bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton operator < (const Range &rhs) const 145257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 146257663e753af15633e48c7b00eb7b5880168090bGreg Clayton if (base == rhs.base) 147257663e753af15633e48c7b00eb7b5880168090bGreg Clayton return size < rhs.size; 148257663e753af15633e48c7b00eb7b5880168090bGreg Clayton return base < rhs.base; 149257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 150257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 151257663e753af15633e48c7b00eb7b5880168090bGreg Clayton bool 152bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton operator == (const Range &rhs) const 153257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 154257663e753af15633e48c7b00eb7b5880168090bGreg Clayton return base == rhs.base && size == rhs.size; 155257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 156257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 157257663e753af15633e48c7b00eb7b5880168090bGreg Clayton bool 158bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton operator != (const Range &rhs) const 159257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 160257663e753af15633e48c7b00eb7b5880168090bGreg Clayton return base != rhs.base || size != rhs.size; 161257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 162257663e753af15633e48c7b00eb7b5880168090bGreg Clayton }; 16361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 16461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton //---------------------------------------------------------------------- 16561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // A range array class where you get to define the type of the ranges 16661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // that the collection contains. 16761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton //---------------------------------------------------------------------- 168257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 169be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton template <typename B, typename S, unsigned N> 17061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton class RangeArray 171257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 172bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton public: 173bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton typedef B BaseType; 174bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton typedef S SizeType; 17561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton typedef Range<B,S> Entry; 176be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typedef llvm::SmallVector<Entry, N> Collection; 17761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 178bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton RangeArray () : 179bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton m_entries () 18061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 18161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 18261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 18361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton ~RangeArray() 18461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 18561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 18661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 18761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton void 18861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton Append (const Entry &entry) 18961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 19061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton m_entries.push_back (entry); 19161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 19261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 193761133029ba2d5bb0c21c3a871dede340b2775fcGreg Clayton bool 194761133029ba2d5bb0c21c3a871dede340b2775fcGreg Clayton RemoveEntrtAtIndex (uint32_t idx) 195761133029ba2d5bb0c21c3a871dede340b2775fcGreg Clayton { 196761133029ba2d5bb0c21c3a871dede340b2775fcGreg Clayton if (idx < m_entries.size()) 197761133029ba2d5bb0c21c3a871dede340b2775fcGreg Clayton { 198761133029ba2d5bb0c21c3a871dede340b2775fcGreg Clayton m_entries.erase (m_entries.begin() + idx); 199761133029ba2d5bb0c21c3a871dede340b2775fcGreg Clayton return true; 200761133029ba2d5bb0c21c3a871dede340b2775fcGreg Clayton } 201761133029ba2d5bb0c21c3a871dede340b2775fcGreg Clayton return false; 202761133029ba2d5bb0c21c3a871dede340b2775fcGreg Clayton } 203761133029ba2d5bb0c21c3a871dede340b2775fcGreg Clayton 20461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton void 20561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton Sort () 20661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 20761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if (m_entries.size() > 1) 20861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton std::stable_sort (m_entries.begin(), m_entries.end()); 20961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 21061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 211c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 212c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton bool 213c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton IsSorted () const 214c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton { 215be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator pos, end, prev; 216c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton // First we determine if we can combine any of the Entry objects so we 217c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton // don't end up allocating and making a new collection for no reason 218c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 219c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton { 220c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton if (prev != end && *pos < *prev) 221c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton return false; 222c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton } 223c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton return true; 224c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton } 225c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#endif 22661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton void 227bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton CombineConsecutiveRanges () 22861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 229c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 230c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton assert (IsSorted()); 231c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#endif 232bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // Can't combine if ranges if we have zero or one range 233bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (m_entries.size() > 1) 23461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 235bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // The list should be sorted prior to calling this function 236be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::iterator pos; 237be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::iterator end; 238be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::iterator prev; 239bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton bool can_combine = false; 240bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // First we determine if we can combine any of the Entry objects so we 241bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // don't end up allocating and making a new collection for no reason 242bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 24361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 244bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (prev != end && prev->Overlap(*pos)) 245bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 246bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton can_combine = true; 247bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton break; 248bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 24961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 250bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 251bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // We we can combine at least one entry, then we make a new collection 252bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // and populate it accordingly, and then swap it into place. 253bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (can_combine) 25461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 255be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton Collection minimal_ranges; 256bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 257bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 258bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (prev != end && prev->Overlap(*pos)) 259bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton minimal_ranges.back().SetRangeEnd (std::max<BaseType>(prev->GetRangeEnd(), pos->GetRangeEnd())); 260bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton else 261bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton minimal_ranges.push_back (*pos); 262bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 263bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // Use the swap technique in case our new vector is much smaller. 264bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // We must swap when using the STL because std::vector objects never 265bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // release or reduce the memory once it has been allocated/reserved. 266bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton m_entries.swap (minimal_ranges); 26761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 26861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 26961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 270bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 271bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 272bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton BaseType 273bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton GetMinRangeBase (BaseType fail_value) const 274bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 275c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 276c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton assert (IsSorted()); 277c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#endif 278bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (m_entries.empty()) 279bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return fail_value; 280bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // m_entries must be sorted, so if we aren't empty, we grab the 281bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // first range's base 282bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return m_entries.front().GetRangeBase(); 283bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 284bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 285bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton BaseType 286bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton GetMaxRangeEnd (BaseType fail_value) const 287bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 288c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 289c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton assert (IsSorted()); 290c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#endif 291bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (m_entries.empty()) 292bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return fail_value; 293bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // m_entries must be sorted, so if we aren't empty, we grab the 294bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // last range's end 295bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return m_entries.back().GetRangeEnd(); 296bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 297bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 298bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton void 299bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton Slide (BaseType slide) 300bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 301be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::iterator pos, end; 302bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos) 303bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton pos->Slide (slide); 304bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 30561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 30661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton void 30761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton Clear () 30861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 30961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton m_entries.clear(); 31061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 31161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 31261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton bool 31361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton IsEmpty () const 31461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 31561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return m_entries.empty(); 31661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 31761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 31861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton size_t 319bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton GetSize () const 32061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 32161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return m_entries.size(); 32261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 32361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 32461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton const Entry * 325bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton GetEntryAtIndex (size_t i) const 32661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 32761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if (i<m_entries.size()) 32861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return &m_entries[i]; 32961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return NULL; 33061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 33161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 332bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // Clients must ensure that "i" is a valid index prior to calling this function 333bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton const Entry & 334bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton GetEntryRef (size_t i) const 335bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 336bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return m_entries[i]; 337bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 338bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 3394aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton Entry * 3404aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton Back() 3414aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 3424aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton if (m_entries.empty()) 3434aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton return NULL; 3444aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton return &m_entries.back(); 3454aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 3464aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 3474aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton const Entry * 3484aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton Back() const 3494aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 3504aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton if (m_entries.empty()) 3514aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton return NULL; 3524aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton return &m_entries.back(); 3534aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 3544aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 35561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton static bool 35661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton BaseLessThan (const Entry& lhs, const Entry& rhs) 35761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 35861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return lhs.GetRangeBase() < rhs.GetRangeBase(); 35961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 36061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 361bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton uint32_t 362bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton FindEntryIndexThatContains (B addr) const 363bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 364c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 365c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton assert (IsSorted()); 366c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#endif 367c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton if (!m_entries.empty()) 368bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 369bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton Entry entry (addr, 1); 370be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator begin = m_entries.begin(); 371be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator end = m_entries.end(); 372be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 373bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 374bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (pos != end && pos->Contains(addr)) 375bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 376bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return std::distance (begin, pos); 377bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 378bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton else if (pos != begin) 379bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 380bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton --pos; 381bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (pos->Contains(addr)) 382bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return std::distance (begin, pos); 383bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 384bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 385bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return UINT32_MAX; 386bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 387bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 38861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton const Entry * 38961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton FindEntryThatContains (B addr) const 39061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 391c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 392c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton assert (IsSorted()); 393c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#endif 394c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton if (!m_entries.empty()) 39561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 39661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton Entry entry (addr, 1); 397be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator begin = m_entries.begin(); 398be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator end = m_entries.end(); 399be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 40061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 40161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if (pos != end && pos->Contains(addr)) 40261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 40361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return &(*pos); 40461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 40561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton else if (pos != begin) 40661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 40761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton --pos; 40861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if (pos->Contains(addr)) 40961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 41061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return &(*pos); 41161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 41261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 41361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 41461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return NULL; 41561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 416bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 417bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton const Entry * 418bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton FindEntryThatContains (const Entry &range) const 419bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 420c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 421c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton assert (IsSorted()); 422c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#endif 423c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton if (!m_entries.empty()) 424bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 425be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator begin = m_entries.begin(); 426be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator end = m_entries.end(); 427be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator pos = std::lower_bound (begin, end, range, BaseLessThan); 428bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 429bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (pos != end && pos->Contains(range)) 430bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 431bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return &(*pos); 432bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 433bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton else if (pos != begin) 434bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 435bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton --pos; 436bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (pos->Contains(range)) 437bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 438bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return &(*pos); 439bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 440bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 441bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 442bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return NULL; 443bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 444bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 44561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton protected: 446be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton Collection m_entries; 44761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton }; 448257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 449464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton template <typename B, typename S> 450464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton class RangeVector 45161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 452464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton public: 453464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typedef B BaseType; 454464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typedef S SizeType; 455464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typedef Range<B,S> Entry; 456464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typedef std::vector<Entry> Collection; 45761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 458464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton RangeVector () : 459464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton m_entries () 460257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 461257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 46261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 463464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton ~RangeVector() 464257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 465257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 46661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 467464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton void 468464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Append (const Entry &entry) 469257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 470464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton m_entries.push_back (entry); 471257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 47261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 473257663e753af15633e48c7b00eb7b5880168090bGreg Clayton bool 474464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton RemoveEntrtAtIndex (uint32_t idx) 47561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 476464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (idx < m_entries.size()) 477464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 478464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton m_entries.erase (m_entries.begin() + idx); 479464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return true; 480464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 481464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return false; 48261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 48361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 48461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton void 48561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton Sort () 48661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 48761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if (m_entries.size() > 1) 48861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton std::stable_sort (m_entries.begin(), m_entries.end()); 48961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 490464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 491c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 492c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton bool 493c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton IsSorted () const 494c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton { 495be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator pos, end, prev; 496c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton // First we determine if we can combine any of the Entry objects so we 497c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton // don't end up allocating and making a new collection for no reason 498c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 499c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton { 500c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton if (prev != end && *pos < *prev) 501c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton return false; 502c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton } 503c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton return true; 504c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton } 505c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#endif 50661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton void 507464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton CombineConsecutiveRanges () 50861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 509c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 510c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton assert (IsSorted()); 511c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#endif 512464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // Can't combine if ranges if we have zero or one range 513464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (m_entries.size() > 1) 514257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 515464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // The list should be sorted prior to calling this function 516464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::iterator pos; 517464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::iterator end; 518464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::iterator prev; 519464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton bool can_combine = false; 520464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // First we determine if we can combine any of the Entry objects so we 521464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // don't end up allocating and making a new collection for no reason 522464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 52361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 524464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (prev != end && prev->Overlap(*pos)) 525464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 526464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton can_combine = true; 527464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton break; 528464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 52961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 530464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 531464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // We we can combine at least one entry, then we make a new collection 532464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // and populate it accordingly, and then swap it into place. 533464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (can_combine) 53461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 535464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Collection minimal_ranges; 536464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 537464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 538464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (prev != end && prev->Overlap(*pos)) 539464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton minimal_ranges.back().SetRangeEnd (std::max<BaseType>(prev->GetRangeEnd(), pos->GetRangeEnd())); 540464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton else 541464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton minimal_ranges.push_back (*pos); 542464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 543464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // Use the swap technique in case our new vector is much smaller. 544464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // We must swap when using the STL because std::vector objects never 545464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // release or reduce the memory once it has been allocated/reserved. 546464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton m_entries.swap (minimal_ranges); 54761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 548257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 54961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 550464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 551464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 552464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton BaseType 553464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton GetMinRangeBase (BaseType fail_value) const 554464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 555464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 556464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton assert (IsSorted()); 557464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#endif 558464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (m_entries.empty()) 559464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return fail_value; 560464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // m_entries must be sorted, so if we aren't empty, we grab the 561464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // first range's base 562464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return m_entries.front().GetRangeBase(); 563464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 564464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 565464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton BaseType 566464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton GetMaxRangeEnd (BaseType fail_value) const 567464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 568464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 569464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton assert (IsSorted()); 570464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#endif 571464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (m_entries.empty()) 572464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return fail_value; 573464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // m_entries must be sorted, so if we aren't empty, we grab the 574464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // last range's end 575464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return m_entries.back().GetRangeEnd(); 576464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 577464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 578464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton void 579464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Slide (BaseType slide) 580464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 581464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::iterator pos, end; 582464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos) 583464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton pos->Slide (slide); 584464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 585464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 58661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton void 58761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton Clear () 58861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 58961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton m_entries.clear(); 59061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 59161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 59261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton bool 59361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton IsEmpty () const 59461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 59561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return m_entries.empty(); 59661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 59761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 59861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton size_t 599bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton GetSize () const 60061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 60161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return m_entries.size(); 60261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 60361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 60461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton const Entry * 605bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton GetEntryAtIndex (size_t i) const 60661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 60761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if (i<m_entries.size()) 60861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return &m_entries[i]; 60961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return NULL; 61061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 611464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 612bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // Clients must ensure that "i" is a valid index prior to calling this function 613bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton const Entry & 614bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton GetEntryRef (size_t i) const 615bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 616bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return m_entries[i]; 617bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 618464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 619464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Entry * 620464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Back() 621464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 622464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (m_entries.empty()) 623464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return NULL; 624464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return &m_entries.back(); 625464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 626464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 627464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton const Entry * 628464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Back() const 629464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 630464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (m_entries.empty()) 631464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return NULL; 632464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return &m_entries.back(); 633464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 634464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 6354aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton static bool 63661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton BaseLessThan (const Entry& lhs, const Entry& rhs) 63761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 63861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return lhs.GetRangeBase() < rhs.GetRangeBase(); 63961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 64061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 641bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton uint32_t 642bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton FindEntryIndexThatContains (B addr) const 643bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 644c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 645c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton assert (IsSorted()); 646c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#endif 647464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (!m_entries.empty()) 648bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 649bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton Entry entry (addr, 1); 650be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator begin = m_entries.begin(); 651be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator end = m_entries.end(); 652be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 653bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 654bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (pos != end && pos->Contains(addr)) 655bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 656bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return std::distance (begin, pos); 657bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 658bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton else if (pos != begin) 659bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 660bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton --pos; 661bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (pos->Contains(addr)) 662bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return std::distance (begin, pos); 663bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 664bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 665bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return UINT32_MAX; 666bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 667464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 66861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton const Entry * 66961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton FindEntryThatContains (B addr) const 67061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 671c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 672c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton assert (IsSorted()); 673c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#endif 674464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (!m_entries.empty()) 675257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 676464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Entry entry (addr, 1); 677be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator begin = m_entries.begin(); 678be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator end = m_entries.end(); 679be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 68061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 68161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if (pos != end && pos->Contains(addr)) 682257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 683464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return &(*pos); 684257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 68561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton else if (pos != begin) 68661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 68761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton --pos; 68861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if (pos->Contains(addr)) 68961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 690464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return &(*pos); 69161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 69261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 693257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 69461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return NULL; 695257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 69661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 697bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton const Entry * 698bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton FindEntryThatContains (const Entry &range) const 699bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 700c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 701c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton assert (IsSorted()); 702c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#endif 703464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (!m_entries.empty()) 704bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 705be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator begin = m_entries.begin(); 706be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator end = m_entries.end(); 707be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator pos = std::lower_bound (begin, end, range, BaseLessThan); 708bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 709bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (pos != end && pos->Contains(range)) 710bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 711464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return &(*pos); 712bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 713bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton else if (pos != begin) 714bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 715bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton --pos; 716bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (pos->Contains(range)) 717bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 718464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return &(*pos); 719bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 720bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 721bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 722bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return NULL; 723bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 724bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 725464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton protected: 726464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Collection m_entries; 727464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton }; 72846c9a355af9b39db78c006b2a5cbf97d3c58d947Greg Clayton 729464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton //---------------------------------------------------------------------- 730464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // A simple range with data class where you get to define the type of 731464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // the range base "B", the type used for the range byte size "S", and 732464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // the type for the associated data "T". 733464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton //---------------------------------------------------------------------- 734464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton template <typename B, typename S, typename T> 735464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton struct RangeData : public Range<B,S> 736464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 737464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typedef T DataType; 738464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 739464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton DataType data; 740464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 741464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton RangeData () : 742464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Range<B,S> (), 743464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton data () 744464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 745464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 746464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 747464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton RangeData (B base, S size) : 748464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Range<B,S> (base, size), 749464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton data () 750464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 751464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 752464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 753464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton RangeData (B base, S size, DataType d) : 754464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Range<B,S> (base, size), 755464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton data (d) 756464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 757464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 758464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 759464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton bool 760464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton operator < (const RangeData &rhs) const 761464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 762464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (this->base == rhs.base) 763464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 764464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (this->size == rhs.size) 765464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return this->data < rhs.data; 766464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton else 767464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return this->size < rhs.size; 768464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 769464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return this->base < rhs.base; 770464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 771464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 772464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton bool 773464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton operator == (const RangeData &rhs) const 774464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 775464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return this->GetRangeBase() == rhs.GetRangeBase() && 776464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton this->GetByteSize() == rhs.GetByteSize() && 777464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton this->data == rhs.data; 778464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 779464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 780464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton bool 781464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton operator != (const RangeData &rhs) const 782464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 783464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return this->GetRangeBase() != rhs.GetRangeBase() || 784464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton this->GetByteSize() != rhs.GetByteSize() || 785464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton this->data != rhs.data; 786464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 787464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton }; 788464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 789464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton template <typename B, typename S, typename T, unsigned N> 790464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton class RangeDataArray 791464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 792464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton public: 793464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typedef RangeData<B,S,T> Entry; 794464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typedef llvm::SmallVector<Entry, N> Collection; 795464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 796464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 797464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton RangeDataArray () 798464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 799464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 800464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 801464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton ~RangeDataArray() 802464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 803464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 804464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 805464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton void 806464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Append (const Entry &entry) 807464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 808464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton m_entries.push_back (entry); 809464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 810464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 811464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton void 812464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Sort () 813464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 814464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (m_entries.size() > 1) 815464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton std::stable_sort (m_entries.begin(), m_entries.end()); 816464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 817464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 818464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 819464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton bool 820464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton IsSorted () const 821464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 822464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::const_iterator pos, end, prev; 823464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // First we determine if we can combine any of the Entry objects so we 824464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // don't end up allocating and making a new collection for no reason 825464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 826464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 827464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (prev != end && *pos < *prev) 828464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return false; 829464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 830464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return true; 831464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 832464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#endif 833464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 834464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton void 835464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton CombineConsecutiveEntriesWithEqualData () 836464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 837464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 838464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton assert (IsSorted()); 839464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#endif 840464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::iterator pos; 841464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::iterator end; 842464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::iterator prev; 843464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton bool can_combine = false; 844464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // First we determine if we can combine any of the Entry objects so we 845464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // don't end up allocating and making a new collection for no reason 846464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 847464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 848464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (prev != end && prev->data == pos->data) 849464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 850464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton can_combine = true; 851464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton break; 852464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 853464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 854464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 855464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // We we can combine at least one entry, then we make a new collection 856464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // and populate it accordingly, and then swap it into place. 857464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (can_combine) 858464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 859464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Collection minimal_ranges; 860464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 861464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 862464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (prev != end && prev->data == pos->data) 863464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton minimal_ranges.back().SetRangeEnd (pos->GetRangeEnd()); 864464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton else 865464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton minimal_ranges.push_back (*pos); 866464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 867464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // Use the swap technique in case our new vector is much smaller. 868464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // We must swap when using the STL because std::vector objects never 869464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // release or reduce the memory once it has been allocated/reserved. 870464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton m_entries.swap (minimal_ranges); 871464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 872464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 873464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 874464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton void 875464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Clear () 876464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 877464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton m_entries.clear(); 878464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 879464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 880464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton bool 881464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton IsEmpty () const 882464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 883464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return m_entries.empty(); 884464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 885464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 886464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton size_t 887464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton GetSize () const 888464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 889464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return m_entries.size(); 890464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 891464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 892464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton const Entry * 893464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton GetEntryAtIndex (size_t i) const 894464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 895464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (i<m_entries.size()) 896464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return &m_entries[i]; 897464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return NULL; 898464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 899464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 900464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // Clients must ensure that "i" is a valid index prior to calling this function 901464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton const Entry & 902464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton GetEntryRef (size_t i) const 903464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 904464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return m_entries[i]; 905464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 906464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 907464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton static bool 908464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton BaseLessThan (const Entry& lhs, const Entry& rhs) 909464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 910464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return lhs.GetRangeBase() < rhs.GetRangeBase(); 911464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 912464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 913464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton uint32_t 914464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton FindEntryIndexThatContains (B addr) const 915464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 916464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 917464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton assert (IsSorted()); 918464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#endif 919464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if ( !m_entries.empty() ) 920464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 921464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Entry entry (addr, 1); 922464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::const_iterator begin = m_entries.begin(); 923464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::const_iterator end = m_entries.end(); 924464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 925464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 926464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (pos != end && pos->Contains(addr)) 927464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 928464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return std::distance (begin, pos); 929464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 930464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton else if (pos != begin) 931464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 932464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton --pos; 933464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (pos->Contains(addr)) 934464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return std::distance (begin, pos); 935464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 936464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 937464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return UINT32_MAX; 938464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 939464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 940464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Entry * 941464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton FindEntryThatContains (B addr) 942464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 943464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 944464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton assert (IsSorted()); 945464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#endif 946464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if ( !m_entries.empty() ) 947464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 948464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Entry entry; 949464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton entry.SetRangeBase(addr); 950464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton entry.SetByteSize(1); 951464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::iterator begin = m_entries.begin(); 952464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::iterator end = m_entries.end(); 953464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 954464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 955464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (pos != end && pos->Contains(addr)) 956464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 957464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return &(*pos); 958464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 959464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton else if (pos != begin) 960464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 961464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton --pos; 962464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (pos->Contains(addr)) 963464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 964464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return &(*pos); 965464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 966464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 967464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 968464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return NULL; 969464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 970464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton const Entry * 971464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton FindEntryThatContains (B addr) const 972464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 973464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 974464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton assert (IsSorted()); 975464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#endif 976464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if ( !m_entries.empty() ) 977464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 978464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Entry entry; 979464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton entry.SetRangeBase(addr); 980464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton entry.SetByteSize(1); 981464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::const_iterator begin = m_entries.begin(); 982464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::const_iterator end = m_entries.end(); 983464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 984464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 985464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (pos != end && pos->Contains(addr)) 986464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 987464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return &(*pos); 988464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 989464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton else if (pos != begin) 990464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 991464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton --pos; 992464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (pos->Contains(addr)) 993464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 994464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return &(*pos); 995464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 996464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 997464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 998464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return NULL; 999464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1000464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1001464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton const Entry * 1002464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton FindEntryThatContains (const Entry &range) const 1003464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1004464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 1005464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton assert (IsSorted()); 1006464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#endif 1007464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if ( !m_entries.empty() ) 1008464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1009464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::const_iterator begin = m_entries.begin(); 1010464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::const_iterator end = m_entries.end(); 1011464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::const_iterator pos = std::lower_bound (begin, end, range, BaseLessThan); 1012464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1013464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (pos != end && pos->Contains(range)) 1014464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1015464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return &(*pos); 1016464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1017464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton else if (pos != begin) 1018464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1019464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton --pos; 1020464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (pos->Contains(range)) 1021464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1022464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return &(*pos); 1023464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1024464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1025464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1026464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return NULL; 1027464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1028464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1029464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Entry * 1030464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Back() 1031464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1032464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (!m_entries.empty()) 1033464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return &m_entries.back(); 1034464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return NULL; 1035464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1036464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1037464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton const Entry * 1038464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Back() const 1039464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1040464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (!m_entries.empty()) 104146c9a355af9b39db78c006b2a5cbf97d3c58d947Greg Clayton return &m_entries.back(); 104246c9a355af9b39db78c006b2a5cbf97d3c58d947Greg Clayton return NULL; 104346c9a355af9b39db78c006b2a5cbf97d3c58d947Greg Clayton } 1044bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 104561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton protected: 1046be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton Collection m_entries; 104761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton }; 1048464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1049464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // Same as RangeDataArray, but uses std::vector as to not 1050464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // require static storage of N items in the class itself 1051464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton template <typename B, typename S, typename T> 1052464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton class RangeDataVector 1053464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1054464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton public: 1055464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typedef RangeData<B,S,T> Entry; 1056464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typedef std::vector<Entry> Collection; 1057464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1058464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton RangeDataVector () 1059464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1060464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1061464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1062464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton ~RangeDataVector() 1063464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1064464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1065464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1066464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton void 1067464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Append (const Entry &entry) 1068464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1069464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton m_entries.push_back (entry); 1070464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1071464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1072464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton void 1073464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Sort () 1074464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1075464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (m_entries.size() > 1) 1076464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton std::stable_sort (m_entries.begin(), m_entries.end()); 1077464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1078464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1079464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 1080464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton bool 1081464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton IsSorted () const 1082464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1083464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::const_iterator pos, end, prev; 1084464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // First we determine if we can combine any of the Entry objects so we 1085464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // don't end up allocating and making a new collection for no reason 1086464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 1087464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1088464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (prev != end && *pos < *prev) 1089464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return false; 1090464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1091464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return true; 1092464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1093464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#endif 1094464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1095464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton void 1096464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton CombineConsecutiveEntriesWithEqualData () 1097464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1098464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 1099464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton assert (IsSorted()); 1100464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#endif 1101464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::iterator pos; 1102464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::iterator end; 1103464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::iterator prev; 1104464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton bool can_combine = false; 1105464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // First we determine if we can combine any of the Entry objects so we 1106464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // don't end up allocating and making a new collection for no reason 1107464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 1108464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1109464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (prev != end && prev->data == pos->data) 1110464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1111464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton can_combine = true; 1112464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton break; 1113464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1114464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1115464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1116464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // We we can combine at least one entry, then we make a new collection 1117464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // and populate it accordingly, and then swap it into place. 1118464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (can_combine) 1119464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1120464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Collection minimal_ranges; 1121464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 1122464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1123464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (prev != end && prev->data == pos->data) 1124464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton minimal_ranges.back().SetRangeEnd (pos->GetRangeEnd()); 1125464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton else 1126464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton minimal_ranges.push_back (*pos); 1127464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1128464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // Use the swap technique in case our new vector is much smaller. 1129464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // We must swap when using the STL because std::vector objects never 1130464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // release or reduce the memory once it has been allocated/reserved. 1131464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton m_entries.swap (minimal_ranges); 1132464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1133464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1134464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1135464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton void 1136464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Clear () 1137464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1138464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton m_entries.clear(); 1139464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1140464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1141464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton bool 1142464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton IsEmpty () const 1143464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1144464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return m_entries.empty(); 1145464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1146464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1147464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton size_t 1148464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton GetSize () const 1149464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1150464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return m_entries.size(); 1151464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1152464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1153464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton const Entry * 1154464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton GetEntryAtIndex (size_t i) const 1155464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1156464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (i<m_entries.size()) 1157464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return &m_entries[i]; 1158464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return NULL; 1159464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1160464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1161464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // Clients must ensure that "i" is a valid index prior to calling this function 1162464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton const Entry & 1163464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton GetEntryRef (size_t i) const 1164464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1165464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return m_entries[i]; 1166464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1167464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1168464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton static bool 1169464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton BaseLessThan (const Entry& lhs, const Entry& rhs) 1170464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1171464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return lhs.GetRangeBase() < rhs.GetRangeBase(); 1172464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1173464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1174464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton uint32_t 1175464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton FindEntryIndexThatContains (B addr) const 1176464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1177464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 1178464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton assert (IsSorted()); 1179464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#endif 1180464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if ( !m_entries.empty() ) 1181464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1182464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Entry entry (addr, 1); 1183464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::const_iterator begin = m_entries.begin(); 1184464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::const_iterator end = m_entries.end(); 1185464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 1186464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1187464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (pos != end && pos->Contains(addr)) 1188464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1189464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return std::distance (begin, pos); 1190464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1191464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton else if (pos != begin) 1192464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1193464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton --pos; 1194464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (pos->Contains(addr)) 1195464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return std::distance (begin, pos); 1196464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1197464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1198464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return UINT32_MAX; 1199464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1200464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1201464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Entry * 1202464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton FindEntryThatContains (B addr) 1203464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1204464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 1205464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton assert (IsSorted()); 1206464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#endif 1207464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if ( !m_entries.empty() ) 1208464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1209464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Entry entry; 1210464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton entry.SetRangeBase(addr); 1211464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton entry.SetByteSize(1); 1212464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::iterator begin = m_entries.begin(); 1213464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::iterator end = m_entries.end(); 1214464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 1215464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1216464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (pos != end && pos->Contains(addr)) 1217464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1218464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return &(*pos); 1219464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1220464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton else if (pos != begin) 1221464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1222464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton --pos; 1223464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (pos->Contains(addr)) 1224464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1225464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return &(*pos); 1226464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1227464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1228464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1229464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return NULL; 1230464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1231464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton const Entry * 1232464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton FindEntryThatContains (B addr) const 1233464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1234464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 1235464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton assert (IsSorted()); 1236464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#endif 1237464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if ( !m_entries.empty() ) 1238464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1239464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Entry entry; 1240464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton entry.SetRangeBase(addr); 1241464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton entry.SetByteSize(1); 1242464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::const_iterator begin = m_entries.begin(); 1243464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::const_iterator end = m_entries.end(); 1244464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 1245464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1246464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (pos != end && pos->Contains(addr)) 1247464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1248464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return &(*pos); 1249464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1250464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton else if (pos != begin) 1251464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1252464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton --pos; 1253464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (pos->Contains(addr)) 1254464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1255464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return &(*pos); 1256464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1257464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1258464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1259464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return NULL; 1260464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1261464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1262464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton const Entry * 1263464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton FindEntryThatContains (const Entry &range) const 1264464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1265464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 1266464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton assert (IsSorted()); 1267464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#endif 1268464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if ( !m_entries.empty() ) 1269464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1270464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::const_iterator begin = m_entries.begin(); 1271464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::const_iterator end = m_entries.end(); 1272464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::const_iterator pos = std::lower_bound (begin, end, range, BaseLessThan); 12734aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 1274464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (pos != end && pos->Contains(range)) 1275464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1276464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return &(*pos); 1277464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1278464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton else if (pos != begin) 1279464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1280464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton --pos; 1281464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (pos->Contains(range)) 1282464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1283464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return &(*pos); 1284464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1285464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1286464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1287464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return NULL; 1288464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1289464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1290464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Entry * 1291464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Back() 1292464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1293464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (!m_entries.empty()) 1294464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return &m_entries.back(); 1295464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return NULL; 1296464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1297464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1298464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton const Entry * 1299464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Back() const 1300464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1301464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (!m_entries.empty()) 1302464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return &m_entries.back(); 1303464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return NULL; 1304464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1305464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1306464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton protected: 1307464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Collection m_entries; 1308464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton }; 1309464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 13104aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 13114aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton //---------------------------------------------------------------------- 13124aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton // A simple range with data class where you get to define the type of 13134aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton // the range base "B", the type used for the range byte size "S", and 13144aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton // the type for the associated data "T". 13154aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton //---------------------------------------------------------------------- 13164aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton template <typename B, typename T> 13174aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton struct AddressData 13184aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 13194aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton typedef B BaseType; 13204aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton typedef T DataType; 13214aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 13224aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton BaseType addr; 13234aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton DataType data; 13244aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 13254aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton AddressData () : 13264aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton addr (), 13274aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton data () 13284aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 13294aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 13304aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 13314aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton AddressData (B a, DataType d) : 13324aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton addr (a), 13334aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton data (d) 13344aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 13354aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 13364aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 13374aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton bool 13384aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton operator < (const AddressData &rhs) const 13394aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 13404aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton if (this->addr == rhs.addr) 13414aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton return this->data < rhs.data; 13424aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton return this->addr < rhs.addr; 13434aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 13444aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 13454aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton bool 13464aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton operator == (const AddressData &rhs) const 13474aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 13484aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton return this->addr == rhs.addr && 13494aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton this->data == rhs.data; 13504aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 13514aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 13524aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton bool 13534aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton operator != (const AddressData &rhs) const 13544aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 13554aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton return this->addr != rhs.addr || 13564aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton this->data == rhs.data; 13574aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 13584aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton }; 13594aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 13604aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 13614aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton template <typename B, typename T, unsigned N> 13624aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton class AddressDataArray 13634aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 13644aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton public: 13654aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton typedef AddressData<B,T> Entry; 13664aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton typedef llvm::SmallVector<Entry, N> Collection; 13674aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 13684aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 13694aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton AddressDataArray () 13704aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 13714aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 13724aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 13734aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton ~AddressDataArray() 13744aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 13754aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 13764aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 13774aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton void 13784aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton Append (const Entry &entry) 13794aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 13804aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton m_entries.push_back (entry); 13814aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 13824aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 13834aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton void 13844aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton Sort () 13854aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 13864aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton if (m_entries.size() > 1) 13874aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton std::stable_sort (m_entries.begin(), m_entries.end()); 13884aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 13894aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 13904aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 13914aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton bool 13924aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton IsSorted () const 13934aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 13944aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton typename Collection::const_iterator pos, end, prev; 13954aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton // First we determine if we can combine any of the Entry objects so we 13964aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton // don't end up allocating and making a new collection for no reason 13974aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 13984aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 13994aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton if (prev != end && *pos < *prev) 14004aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton return false; 14014aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 14024aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton return true; 14034aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 14044aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton#endif 14054aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 14064aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton void 14074aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton Clear () 14084aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 14094aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton m_entries.clear(); 14104aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 14114aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 14124aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton bool 14134aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton IsEmpty () const 14144aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 14154aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton return m_entries.empty(); 14164aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 14174aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 14184aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton size_t 14194aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton GetSize () const 14204aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 14214aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton return m_entries.size(); 14224aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 14234aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 14244aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton const Entry * 14254aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton GetEntryAtIndex (size_t i) const 14264aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 14274aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton if (i<m_entries.size()) 14284aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton return &m_entries[i]; 14294aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton return NULL; 14304aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 14314aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 14324aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton // Clients must ensure that "i" is a valid index prior to calling this function 14334aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton const Entry & 14344aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton GetEntryRef (size_t i) const 14354aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 14364aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton return m_entries[i]; 14374aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 14384aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 14394aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton static bool 14404aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton BaseLessThan (const Entry& lhs, const Entry& rhs) 14414aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 14424aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton return lhs.addr < rhs.addr; 14434aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 14444aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 14454aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton Entry * 14464aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton FindEntry (B addr, bool exact_match_only) 14474aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 14484aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 14494aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton assert (IsSorted()); 14504aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton#endif 14514aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton if ( !m_entries.empty() ) 14524aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 14534aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton Entry entry; 14544aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton entry.addr = addr; 14554aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton typename Collection::iterator begin = m_entries.begin(); 14564aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton typename Collection::iterator end = m_entries.end(); 14574aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton typename Collection::iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 14584aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 14594aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton if (pos != end) 14604aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 14614aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton if (pos->addr == addr || !exact_match_only) 14624aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton return &(*pos); 14634aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 14644aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 14654aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton return NULL; 14664aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 14674aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 14684aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton const Entry * 14694aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton FindNextEntry (const Entry *entry) 14704aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 14714aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton if (entry >= &*m_entries.begin() && entry + 1 < &*m_entries.end()) 14724aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton return entry + 1; 14734aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton return NULL; 14744aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 14754aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 14764aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton Entry * 14774aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton Back() 14784aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 14794aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton if (!m_entries.empty()) 14804aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton return &m_entries.back(); 14814aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton return NULL; 14824aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 14834aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 14844aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton const Entry * 14854aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton Back() const 14864aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 14874aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton if (!m_entries.empty()) 14884aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton return &m_entries.back(); 14894aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton return NULL; 14904aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 14914aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 14924aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton protected: 14934aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton Collection m_entries; 14944aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton }; 1495257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 1496257663e753af15633e48c7b00eb7b5880168090bGreg Clayton} // namespace lldb_private 1497257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 1498257663e753af15633e48c7b00eb7b5880168090bGreg Clayton#endif // liblldb_RangeMap_h_ 1499