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 } 5912d63ae1820e622335caf58f86a86164a2a160931Jason Molenda 5922d63ae1820e622335caf58f86a86164a2a160931Jason Molenda void 5932d63ae1820e622335caf58f86a86164a2a160931Jason Molenda Reserve (typename Collection::size_type size) 5942d63ae1820e622335caf58f86a86164a2a160931Jason Molenda { 5952d63ae1820e622335caf58f86a86164a2a160931Jason Molenda m_entries.resize (size); 5962d63ae1820e622335caf58f86a86164a2a160931Jason Molenda } 5972d63ae1820e622335caf58f86a86164a2a160931Jason Molenda 59861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton bool 59961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton IsEmpty () const 60061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 60161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return m_entries.empty(); 60261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 60361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 60461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton size_t 605bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton GetSize () const 60661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 60761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return m_entries.size(); 60861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 60961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 61061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton const Entry * 611bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton GetEntryAtIndex (size_t i) const 61261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 61361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if (i<m_entries.size()) 61461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return &m_entries[i]; 61561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return NULL; 61661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 617464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 618bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // Clients must ensure that "i" is a valid index prior to calling this function 619bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton const Entry & 620bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton GetEntryRef (size_t i) const 621bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 622bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return m_entries[i]; 623bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 624464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 625464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Entry * 626464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Back() 627464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 628464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (m_entries.empty()) 629464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return NULL; 630464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return &m_entries.back(); 631464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 632464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 633464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton const Entry * 634464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Back() const 635464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 636464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (m_entries.empty()) 637464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return NULL; 638464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return &m_entries.back(); 639464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 640464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 6414aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton static bool 64261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton BaseLessThan (const Entry& lhs, const Entry& rhs) 64361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 64461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return lhs.GetRangeBase() < rhs.GetRangeBase(); 64561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 64661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 647bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton uint32_t 648bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton FindEntryIndexThatContains (B addr) const 649bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 650c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 651c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton assert (IsSorted()); 652c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#endif 653464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (!m_entries.empty()) 654bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 655bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton Entry entry (addr, 1); 656be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator begin = m_entries.begin(); 657be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator end = m_entries.end(); 658be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 659bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 660bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (pos != end && pos->Contains(addr)) 661bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 662bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return std::distance (begin, pos); 663bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 664bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton else if (pos != begin) 665bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 666bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton --pos; 667bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (pos->Contains(addr)) 668bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return std::distance (begin, pos); 669bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 670bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 671bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return UINT32_MAX; 672bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 673464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 67461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton const Entry * 67561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton FindEntryThatContains (B addr) const 67661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 677c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 678c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton assert (IsSorted()); 679c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#endif 680464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (!m_entries.empty()) 681257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 682464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Entry entry (addr, 1); 683be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator begin = m_entries.begin(); 684be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator end = m_entries.end(); 685be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 68661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 68761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if (pos != end && pos->Contains(addr)) 688257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 689464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return &(*pos); 690257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 69161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton else if (pos != begin) 69261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 69361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton --pos; 69461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if (pos->Contains(addr)) 69561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 696464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return &(*pos); 69761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 69861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 699257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 70061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return NULL; 701257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 70261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 703bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton const Entry * 704bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton FindEntryThatContains (const Entry &range) const 705bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 706c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 707c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton assert (IsSorted()); 708c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#endif 709464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (!m_entries.empty()) 710bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 711be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator begin = m_entries.begin(); 712be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator end = m_entries.end(); 713be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator pos = std::lower_bound (begin, end, range, BaseLessThan); 714bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 715bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (pos != end && pos->Contains(range)) 716bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 717464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return &(*pos); 718bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 719bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton else if (pos != begin) 720bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 721bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton --pos; 722bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (pos->Contains(range)) 723bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 724464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return &(*pos); 725bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 726bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 727bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 728bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return NULL; 729bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 730bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 731464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton protected: 732464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Collection m_entries; 733464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton }; 73446c9a355af9b39db78c006b2a5cbf97d3c58d947Greg Clayton 735464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton //---------------------------------------------------------------------- 736464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // A simple range with data class where you get to define the type of 737464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // the range base "B", the type used for the range byte size "S", and 738464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // the type for the associated data "T". 739464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton //---------------------------------------------------------------------- 740464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton template <typename B, typename S, typename T> 741464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton struct RangeData : public Range<B,S> 742464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 743464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typedef T DataType; 744464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 745464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton DataType data; 746464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 747464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton RangeData () : 748464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Range<B,S> (), 749464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton data () 750464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 751464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 752464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 753464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton RangeData (B base, S size) : 754464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Range<B,S> (base, size), 755464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton data () 756464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 757464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 758464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 759464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton RangeData (B base, S size, DataType d) : 760464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Range<B,S> (base, size), 761464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton data (d) 762464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 763464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 764464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 765464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton bool 766464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton operator < (const RangeData &rhs) const 767464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 768464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (this->base == rhs.base) 769464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 770464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (this->size == rhs.size) 771464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return this->data < rhs.data; 772464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton else 773464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return this->size < rhs.size; 774464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 775464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return this->base < rhs.base; 776464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 777464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 778464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton bool 779464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton operator == (const RangeData &rhs) const 780464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 781464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return this->GetRangeBase() == rhs.GetRangeBase() && 782464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton this->GetByteSize() == rhs.GetByteSize() && 783464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton this->data == rhs.data; 784464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 785464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 786464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton bool 787464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton operator != (const RangeData &rhs) const 788464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 789464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return this->GetRangeBase() != rhs.GetRangeBase() || 790464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton this->GetByteSize() != rhs.GetByteSize() || 791464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton this->data != rhs.data; 792464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 793464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton }; 794464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 795464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton template <typename B, typename S, typename T, unsigned N> 796464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton class RangeDataArray 797464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 798464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton public: 799464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typedef RangeData<B,S,T> Entry; 800464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typedef llvm::SmallVector<Entry, N> Collection; 801464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 802464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 803464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton RangeDataArray () 804464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 805464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 806464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 807464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton ~RangeDataArray() 808464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 809464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 810464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 811464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton void 812464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Append (const Entry &entry) 813464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 814464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton m_entries.push_back (entry); 815464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 816464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 817464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton void 818464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Sort () 819464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 820464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (m_entries.size() > 1) 821464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton std::stable_sort (m_entries.begin(), m_entries.end()); 822464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 823464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 824464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 825464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton bool 826464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton IsSorted () const 827464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 828464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::const_iterator pos, end, prev; 829464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // First we determine if we can combine any of the Entry objects so we 830464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // don't end up allocating and making a new collection for no reason 831464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 832464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 833464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (prev != end && *pos < *prev) 834464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return false; 835464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 836464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return true; 837464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 838464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#endif 839464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 840464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton void 841464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton CombineConsecutiveEntriesWithEqualData () 842464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 843464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 844464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton assert (IsSorted()); 845464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#endif 846464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::iterator pos; 847464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::iterator end; 848464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::iterator prev; 849464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton bool can_combine = false; 850464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // First we determine if we can combine any of the Entry objects so we 851464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // don't end up allocating and making a new collection for no reason 852464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 853464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 854464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (prev != end && prev->data == pos->data) 855464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 856464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton can_combine = true; 857464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton break; 858464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 859464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 860464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 861464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // We we can combine at least one entry, then we make a new collection 862464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // and populate it accordingly, and then swap it into place. 863464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (can_combine) 864464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 865464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Collection minimal_ranges; 866464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 867464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 868464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (prev != end && prev->data == pos->data) 869464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton minimal_ranges.back().SetRangeEnd (pos->GetRangeEnd()); 870464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton else 871464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton minimal_ranges.push_back (*pos); 872464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 873464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // Use the swap technique in case our new vector is much smaller. 874464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // We must swap when using the STL because std::vector objects never 875464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // release or reduce the memory once it has been allocated/reserved. 876464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton m_entries.swap (minimal_ranges); 877464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 878464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 879464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 880464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton void 881464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Clear () 882464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 883464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton m_entries.clear(); 884464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 885464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 886464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton bool 887464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton IsEmpty () const 888464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 889464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return m_entries.empty(); 890464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 891464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 892464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton size_t 893464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton GetSize () const 894464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 895464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return m_entries.size(); 896464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 897464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 898464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton const Entry * 899464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton GetEntryAtIndex (size_t i) const 900464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 901464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (i<m_entries.size()) 902464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return &m_entries[i]; 903464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return NULL; 904464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 905464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 906464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // Clients must ensure that "i" is a valid index prior to calling this function 907464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton const Entry & 908464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton GetEntryRef (size_t i) const 909464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 910464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return m_entries[i]; 911464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 912464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 913464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton static bool 914464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton BaseLessThan (const Entry& lhs, const Entry& rhs) 915464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 916464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return lhs.GetRangeBase() < rhs.GetRangeBase(); 917464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 918464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 919464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton uint32_t 920464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton FindEntryIndexThatContains (B addr) const 921464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 922464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 923464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton assert (IsSorted()); 924464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#endif 925464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if ( !m_entries.empty() ) 926464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 927464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Entry entry (addr, 1); 928464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::const_iterator begin = m_entries.begin(); 929464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::const_iterator end = m_entries.end(); 930464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 931464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 932464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (pos != end && pos->Contains(addr)) 933464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 934464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return std::distance (begin, pos); 935464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 936464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton else if (pos != begin) 937464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 938464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton --pos; 939464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (pos->Contains(addr)) 940464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return std::distance (begin, pos); 941464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 942464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 943464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return UINT32_MAX; 944464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 945464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 946464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Entry * 947464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton FindEntryThatContains (B addr) 948464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 949464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 950464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton assert (IsSorted()); 951464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#endif 952464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if ( !m_entries.empty() ) 953464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 954464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Entry entry; 955464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton entry.SetRangeBase(addr); 956464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton entry.SetByteSize(1); 957464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::iterator begin = m_entries.begin(); 958464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::iterator end = m_entries.end(); 959464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 960464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 961464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (pos != end && pos->Contains(addr)) 962464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 963464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return &(*pos); 964464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 965464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton else if (pos != begin) 966464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 967464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton --pos; 968464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (pos->Contains(addr)) 969464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 970464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return &(*pos); 971464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 972464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 973464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 974464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return NULL; 975464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 976464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton const Entry * 977464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton FindEntryThatContains (B addr) const 978464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 979464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 980464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton assert (IsSorted()); 981464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#endif 982464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if ( !m_entries.empty() ) 983464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 984464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Entry entry; 985464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton entry.SetRangeBase(addr); 986464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton entry.SetByteSize(1); 987464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::const_iterator begin = m_entries.begin(); 988464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::const_iterator end = m_entries.end(); 989464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 990464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 991464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (pos != end && pos->Contains(addr)) 992464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 993464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return &(*pos); 994464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 995464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton else if (pos != begin) 996464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 997464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton --pos; 998464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (pos->Contains(addr)) 999464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1000464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return &(*pos); 1001464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1002464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1003464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1004464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return NULL; 1005464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1006464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1007464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton const Entry * 1008464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton FindEntryThatContains (const Entry &range) const 1009464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1010464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 1011464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton assert (IsSorted()); 1012464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#endif 1013464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if ( !m_entries.empty() ) 1014464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1015464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::const_iterator begin = m_entries.begin(); 1016464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::const_iterator end = m_entries.end(); 1017464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::const_iterator pos = std::lower_bound (begin, end, range, BaseLessThan); 1018464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1019464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (pos != end && pos->Contains(range)) 1020464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1021464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return &(*pos); 1022464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1023464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton else if (pos != begin) 1024464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1025464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton --pos; 1026464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (pos->Contains(range)) 1027464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1028464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return &(*pos); 1029464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1030464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1031464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1032464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return NULL; 1033464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1034464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1035464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Entry * 1036464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Back() 1037464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1038464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (!m_entries.empty()) 1039464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return &m_entries.back(); 1040464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return NULL; 1041464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1042464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1043464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton const Entry * 1044464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Back() const 1045464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1046464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (!m_entries.empty()) 104746c9a355af9b39db78c006b2a5cbf97d3c58d947Greg Clayton return &m_entries.back(); 104846c9a355af9b39db78c006b2a5cbf97d3c58d947Greg Clayton return NULL; 104946c9a355af9b39db78c006b2a5cbf97d3c58d947Greg Clayton } 1050bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 105161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton protected: 1052be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton Collection m_entries; 105361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton }; 1054464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1055464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // Same as RangeDataArray, but uses std::vector as to not 1056464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // require static storage of N items in the class itself 1057464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton template <typename B, typename S, typename T> 1058464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton class RangeDataVector 1059464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1060464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton public: 1061464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typedef RangeData<B,S,T> Entry; 1062464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typedef std::vector<Entry> Collection; 1063464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1064464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton RangeDataVector () 1065464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1066464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1067464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1068464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton ~RangeDataVector() 1069464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1070464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1071464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1072464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton void 1073464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Append (const Entry &entry) 1074464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1075464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton m_entries.push_back (entry); 1076464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1077464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1078464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton void 1079464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Sort () 1080464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1081464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (m_entries.size() > 1) 1082464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton std::stable_sort (m_entries.begin(), m_entries.end()); 1083464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1084464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1085464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 1086464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton bool 1087464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton IsSorted () const 1088464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1089464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::const_iterator pos, end, prev; 1090464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // First we determine if we can combine any of the Entry objects so we 1091464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // don't end up allocating and making a new collection for no reason 1092464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 1093464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1094464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (prev != end && *pos < *prev) 1095464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return false; 1096464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1097464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return true; 1098464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1099464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#endif 1100464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1101464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton void 1102464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton CombineConsecutiveEntriesWithEqualData () 1103464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1104464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 1105464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton assert (IsSorted()); 1106464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#endif 1107464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::iterator pos; 1108464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::iterator end; 1109464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::iterator prev; 1110464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton bool can_combine = false; 1111464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // First we determine if we can combine any of the Entry objects so we 1112464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // don't end up allocating and making a new collection for no reason 1113464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 1114464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1115464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (prev != end && prev->data == pos->data) 1116464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1117464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton can_combine = true; 1118464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton break; 1119464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1120464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1121464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1122464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // We we can combine at least one entry, then we make a new collection 1123464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // and populate it accordingly, and then swap it into place. 1124464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (can_combine) 1125464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1126464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Collection minimal_ranges; 1127464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 1128464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1129464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (prev != end && prev->data == pos->data) 1130464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton minimal_ranges.back().SetRangeEnd (pos->GetRangeEnd()); 1131464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton else 1132464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton minimal_ranges.push_back (*pos); 1133464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1134464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // Use the swap technique in case our new vector is much smaller. 1135464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // We must swap when using the STL because std::vector objects never 1136464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // release or reduce the memory once it has been allocated/reserved. 1137464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton m_entries.swap (minimal_ranges); 1138464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1139464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1140464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 11417940069905bee0b2e5f0661bf37c9f906ddf8603Greg Clayton // Calculate the byte size of ranges with zero byte sizes by finding 11427940069905bee0b2e5f0661bf37c9f906ddf8603Greg Clayton // the next entry with a base address > the current base address 11437940069905bee0b2e5f0661bf37c9f906ddf8603Greg Clayton void 11447940069905bee0b2e5f0661bf37c9f906ddf8603Greg Clayton CalculateSizesOfZeroByteSizeRanges () 11457940069905bee0b2e5f0661bf37c9f906ddf8603Greg Clayton { 11467940069905bee0b2e5f0661bf37c9f906ddf8603Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 11477940069905bee0b2e5f0661bf37c9f906ddf8603Greg Clayton assert (IsSorted()); 11487940069905bee0b2e5f0661bf37c9f906ddf8603Greg Clayton#endif 11497940069905bee0b2e5f0661bf37c9f906ddf8603Greg Clayton typename Collection::iterator pos; 11507940069905bee0b2e5f0661bf37c9f906ddf8603Greg Clayton typename Collection::iterator end; 11517940069905bee0b2e5f0661bf37c9f906ddf8603Greg Clayton typename Collection::iterator next; 11527940069905bee0b2e5f0661bf37c9f906ddf8603Greg Clayton for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos) 11537940069905bee0b2e5f0661bf37c9f906ddf8603Greg Clayton { 11547940069905bee0b2e5f0661bf37c9f906ddf8603Greg Clayton if (pos->GetByteSize() == 0) 11557940069905bee0b2e5f0661bf37c9f906ddf8603Greg Clayton { 11567940069905bee0b2e5f0661bf37c9f906ddf8603Greg Clayton // Watch out for multiple entries with same address and make sure 11577940069905bee0b2e5f0661bf37c9f906ddf8603Greg Clayton // we find an entry that is greater than the current base address 11587940069905bee0b2e5f0661bf37c9f906ddf8603Greg Clayton // before we use that for the size 11597940069905bee0b2e5f0661bf37c9f906ddf8603Greg Clayton auto curr_base = pos->GetRangeBase(); 11607940069905bee0b2e5f0661bf37c9f906ddf8603Greg Clayton for (next = pos + 1; next != end; ++next) 11617940069905bee0b2e5f0661bf37c9f906ddf8603Greg Clayton { 11627940069905bee0b2e5f0661bf37c9f906ddf8603Greg Clayton auto next_base = next->GetRangeBase(); 11637940069905bee0b2e5f0661bf37c9f906ddf8603Greg Clayton if (next_base > curr_base) 11647940069905bee0b2e5f0661bf37c9f906ddf8603Greg Clayton { 11657940069905bee0b2e5f0661bf37c9f906ddf8603Greg Clayton pos->SetByteSize (next_base - curr_base); 11667940069905bee0b2e5f0661bf37c9f906ddf8603Greg Clayton break; 11677940069905bee0b2e5f0661bf37c9f906ddf8603Greg Clayton } 11687940069905bee0b2e5f0661bf37c9f906ddf8603Greg Clayton } 11697940069905bee0b2e5f0661bf37c9f906ddf8603Greg Clayton } 11707940069905bee0b2e5f0661bf37c9f906ddf8603Greg Clayton } 11717940069905bee0b2e5f0661bf37c9f906ddf8603Greg Clayton 11727940069905bee0b2e5f0661bf37c9f906ddf8603Greg Clayton } 11737940069905bee0b2e5f0661bf37c9f906ddf8603Greg Clayton 1174464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton void 1175464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Clear () 1176464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1177464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton m_entries.clear(); 1178464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 11792d63ae1820e622335caf58f86a86164a2a160931Jason Molenda 11802d63ae1820e622335caf58f86a86164a2a160931Jason Molenda void 11812d63ae1820e622335caf58f86a86164a2a160931Jason Molenda Reserve (typename Collection::size_type size) 11822d63ae1820e622335caf58f86a86164a2a160931Jason Molenda { 11832d63ae1820e622335caf58f86a86164a2a160931Jason Molenda m_entries.resize (size); 11842d63ae1820e622335caf58f86a86164a2a160931Jason Molenda } 11852d63ae1820e622335caf58f86a86164a2a160931Jason Molenda 1186464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton bool 1187464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton IsEmpty () const 1188464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1189464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return m_entries.empty(); 1190464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1191464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1192464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton size_t 1193464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton GetSize () const 1194464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1195464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return m_entries.size(); 1196464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1197464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1198464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton const Entry * 1199464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton GetEntryAtIndex (size_t i) const 1200464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1201464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (i<m_entries.size()) 1202464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return &m_entries[i]; 1203464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return NULL; 1204464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1205464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1206464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton // Clients must ensure that "i" is a valid index prior to calling this function 1207464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton const Entry & 1208464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton GetEntryRef (size_t i) const 1209464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1210464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return m_entries[i]; 1211464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1212464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1213464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton static bool 1214464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton BaseLessThan (const Entry& lhs, const Entry& rhs) 1215464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1216464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return lhs.GetRangeBase() < rhs.GetRangeBase(); 1217464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1218464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1219464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton uint32_t 1220464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton FindEntryIndexThatContains (B addr) const 1221464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1222464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 1223464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton assert (IsSorted()); 1224464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#endif 1225464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if ( !m_entries.empty() ) 1226464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1227464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Entry entry (addr, 1); 1228464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::const_iterator begin = m_entries.begin(); 1229464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::const_iterator end = m_entries.end(); 1230464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 1231464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1232464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (pos != end && pos->Contains(addr)) 1233464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1234464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return std::distance (begin, pos); 1235464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1236464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton else if (pos != begin) 1237464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1238464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton --pos; 1239464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (pos->Contains(addr)) 1240464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return std::distance (begin, pos); 1241464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1242464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1243464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return UINT32_MAX; 1244464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1245464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1246464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Entry * 1247464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton FindEntryThatContains (B addr) 1248464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1249464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 1250464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton assert (IsSorted()); 1251464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#endif 1252464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if ( !m_entries.empty() ) 1253464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1254464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Entry entry; 1255464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton entry.SetRangeBase(addr); 1256464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton entry.SetByteSize(1); 1257464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::iterator begin = m_entries.begin(); 1258464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::iterator end = m_entries.end(); 1259464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 1260464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1261464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (pos != end && pos->Contains(addr)) 1262464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1263464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return &(*pos); 1264464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1265464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton else if (pos != begin) 1266464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1267464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton --pos; 1268464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (pos->Contains(addr)) 1269464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1270464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return &(*pos); 1271464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1272464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1273464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1274464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return NULL; 1275464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1276464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton const Entry * 1277464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton FindEntryThatContains (B addr) const 1278464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1279464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 1280464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton assert (IsSorted()); 1281464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#endif 1282464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if ( !m_entries.empty() ) 1283464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1284464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Entry entry; 1285464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton entry.SetRangeBase(addr); 1286464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton entry.SetByteSize(1); 1287464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::const_iterator begin = m_entries.begin(); 1288464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::const_iterator end = m_entries.end(); 1289464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 1290464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1291464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (pos != end && pos->Contains(addr)) 1292464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1293464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return &(*pos); 1294464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1295464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton else if (pos != begin) 1296464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1297464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton --pos; 1298464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (pos->Contains(addr)) 1299464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1300464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return &(*pos); 1301464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1302464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1303464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1304464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return NULL; 1305464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1306464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1307464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton const Entry * 1308464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton FindEntryThatContains (const Entry &range) const 1309464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1310464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 1311464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton assert (IsSorted()); 1312464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton#endif 1313464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if ( !m_entries.empty() ) 1314464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1315464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::const_iterator begin = m_entries.begin(); 1316464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::const_iterator end = m_entries.end(); 1317464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton typename Collection::const_iterator pos = std::lower_bound (begin, end, range, BaseLessThan); 13184aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 1319464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (pos != end && pos->Contains(range)) 1320464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1321464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return &(*pos); 1322464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1323464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton else if (pos != begin) 1324464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1325464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton --pos; 1326464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (pos->Contains(range)) 1327464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1328464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return &(*pos); 1329464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1330464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1331464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1332464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return NULL; 1333464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1334464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1335464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Entry * 1336464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Back() 1337464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1338464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (!m_entries.empty()) 1339464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return &m_entries.back(); 1340464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return NULL; 1341464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1342464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1343464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton const Entry * 1344464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Back() const 1345464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton { 1346464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton if (!m_entries.empty()) 1347464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return &m_entries.back(); 1348464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton return NULL; 1349464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton } 1350464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 1351464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton protected: 1352464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton Collection m_entries; 1353464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton }; 1354464a5063bc59755cb6ec063d0b2491097302d2abGreg Clayton 13554aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 13564aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton //---------------------------------------------------------------------- 13574aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton // A simple range with data class where you get to define the type of 13584aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton // the range base "B", the type used for the range byte size "S", and 13594aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton // the type for the associated data "T". 13604aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton //---------------------------------------------------------------------- 13614aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton template <typename B, typename T> 13624aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton struct AddressData 13634aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 13644aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton typedef B BaseType; 13654aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton typedef T DataType; 13664aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 13674aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton BaseType addr; 13684aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton DataType data; 13694aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 13704aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton AddressData () : 13714aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton addr (), 13724aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton data () 13734aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 13744aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 13754aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 13764aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton AddressData (B a, DataType d) : 13774aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton addr (a), 13784aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton data (d) 13794aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 13804aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 13814aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 13824aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton bool 13834aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton operator < (const AddressData &rhs) const 13844aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 13854aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton if (this->addr == rhs.addr) 13864aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton return this->data < rhs.data; 13874aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton return this->addr < rhs.addr; 13884aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 13894aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 13904aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton bool 13914aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton operator == (const AddressData &rhs) const 13924aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 13934aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton return this->addr == rhs.addr && 13944aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton this->data == rhs.data; 13954aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 13964aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 13974aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton bool 13984aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton operator != (const AddressData &rhs) const 13994aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 14004aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton return this->addr != rhs.addr || 14014aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton this->data == rhs.data; 14024aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 14034aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton }; 14044aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 14054aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 14064aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton template <typename B, typename T, unsigned N> 14074aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton class AddressDataArray 14084aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 14094aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton public: 14104aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton typedef AddressData<B,T> Entry; 14114aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton typedef llvm::SmallVector<Entry, N> Collection; 14124aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 14134aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 14144aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton AddressDataArray () 14154aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 14164aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 14174aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 14184aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton ~AddressDataArray() 14194aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 14204aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 14214aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 14224aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton void 14234aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton Append (const Entry &entry) 14244aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 14254aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton m_entries.push_back (entry); 14264aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 14274aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 14284aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton void 14294aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton Sort () 14304aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 14314aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton if (m_entries.size() > 1) 14324aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton std::stable_sort (m_entries.begin(), m_entries.end()); 14334aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 14344aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 14354aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 14364aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton bool 14374aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton IsSorted () const 14384aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 14394aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton typename Collection::const_iterator pos, end, prev; 14404aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton // First we determine if we can combine any of the Entry objects so we 14414aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton // don't end up allocating and making a new collection for no reason 14424aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 14434aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 14444aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton if (prev != end && *pos < *prev) 14454aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton return false; 14464aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 14474aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton return true; 14484aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 14494aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton#endif 14504aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 14514aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton void 14524aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton Clear () 14534aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 14544aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton m_entries.clear(); 14554aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 14564aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 14574aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton bool 14584aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton IsEmpty () const 14594aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 14604aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton return m_entries.empty(); 14614aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 14624aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 14634aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton size_t 14644aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton GetSize () const 14654aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 14664aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton return m_entries.size(); 14674aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 14684aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 14694aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton const Entry * 14704aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton GetEntryAtIndex (size_t i) const 14714aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 14724aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton if (i<m_entries.size()) 14734aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton return &m_entries[i]; 14744aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton return NULL; 14754aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 14764aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 14774aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton // Clients must ensure that "i" is a valid index prior to calling this function 14784aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton const Entry & 14794aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton GetEntryRef (size_t i) const 14804aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 14814aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton return m_entries[i]; 14824aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 14834aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 14844aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton static bool 14854aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton BaseLessThan (const Entry& lhs, const Entry& rhs) 14864aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 14874aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton return lhs.addr < rhs.addr; 14884aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 14894aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 14904aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton Entry * 14914aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton FindEntry (B addr, bool exact_match_only) 14924aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 14934aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 14944aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton assert (IsSorted()); 14954aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton#endif 14964aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton if ( !m_entries.empty() ) 14974aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 14984aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton Entry entry; 14994aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton entry.addr = addr; 15004aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton typename Collection::iterator begin = m_entries.begin(); 15014aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton typename Collection::iterator end = m_entries.end(); 15024aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton typename Collection::iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 15034aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 15044aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton if (pos != end) 15054aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 15064aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton if (pos->addr == addr || !exact_match_only) 15074aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton return &(*pos); 15084aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 15094aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 15104aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton return NULL; 15114aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 15124aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 15134aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton const Entry * 15144aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton FindNextEntry (const Entry *entry) 15154aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 15164aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton if (entry >= &*m_entries.begin() && entry + 1 < &*m_entries.end()) 15174aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton return entry + 1; 15184aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton return NULL; 15194aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 15204aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 15214aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton Entry * 15224aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton Back() 15234aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 15244aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton if (!m_entries.empty()) 15254aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton return &m_entries.back(); 15264aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton return NULL; 15274aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 15284aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 15294aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton const Entry * 15304aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton Back() const 15314aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton { 15324aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton if (!m_entries.empty()) 15334aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton return &m_entries.back(); 15344aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton return NULL; 15354aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton } 15364aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton 15374aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton protected: 15384aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton Collection m_entries; 15394aa2edf602fa60693afa33d4fe0d1d459a488333Greg Clayton }; 1540257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 1541257663e753af15633e48c7b00eb7b5880168090bGreg Clayton} // namespace lldb_private 1542257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 1543257663e753af15633e48c7b00eb7b5880168090bGreg Clayton#endif // liblldb_RangeMap_h_ 1544