RangeMap.h revision bc36a861b8e0b2f2dde34f27c9fa9629a357d598
1257663e753af15633e48c7b00eb7b5880168090bGreg Clayton//===-- RangeMap.h ----------------------------------------------*- C++ -*-===// 2257663e753af15633e48c7b00eb7b5880168090bGreg Clayton// 3257663e753af15633e48c7b00eb7b5880168090bGreg Clayton// The LLVM Compiler Infrastructure 4257663e753af15633e48c7b00eb7b5880168090bGreg Clayton// 5257663e753af15633e48c7b00eb7b5880168090bGreg Clayton// This file is distributed under the University of Illinois Open Source 6257663e753af15633e48c7b00eb7b5880168090bGreg Clayton// License. See LICENSE.TXT for details. 7257663e753af15633e48c7b00eb7b5880168090bGreg Clayton// 8257663e753af15633e48c7b00eb7b5880168090bGreg Clayton//===----------------------------------------------------------------------===// 9257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 10257663e753af15633e48c7b00eb7b5880168090bGreg Clayton#ifndef liblldb_RangeMap_h_ 11257663e753af15633e48c7b00eb7b5880168090bGreg Clayton#define liblldb_RangeMap_h_ 12257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 13257663e753af15633e48c7b00eb7b5880168090bGreg Clayton#include "lldb/lldb-private.h" 14257663e753af15633e48c7b00eb7b5880168090bGreg Clayton#include <vector> 15257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 16257663e753af15633e48c7b00eb7b5880168090bGreg Claytonnamespace lldb_private { 17257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 1861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton //---------------------------------------------------------------------- 1961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // Templatized classes for dealing with generic ranges and also 2061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // collections of ranges, or collections of ranges that have associated 2161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // data. 2261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton //---------------------------------------------------------------------- 2361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 2461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton //---------------------------------------------------------------------- 2561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // A simple range class where you get to define the type of the range 2661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // base "B", and the type used for the range byte size "S". 2761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton //---------------------------------------------------------------------- 2861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton template <typename B, typename S> 29257663e753af15633e48c7b00eb7b5880168090bGreg Clayton struct Range 30257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 3161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton typedef B BaseType; 3261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton typedef S SizeType; 3361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 3461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton BaseType base; 3561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton SizeType size; 36257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 37257663e753af15633e48c7b00eb7b5880168090bGreg Clayton Range () : 38257663e753af15633e48c7b00eb7b5880168090bGreg Clayton base (0), 39257663e753af15633e48c7b00eb7b5880168090bGreg Clayton size (0) 40257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 41257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 42257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 4361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton Range (BaseType b, SizeType s) : 44257663e753af15633e48c7b00eb7b5880168090bGreg Clayton base (b), 45257663e753af15633e48c7b00eb7b5880168090bGreg Clayton size (s) 46257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 47257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 48257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 49bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton void 50bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton Clear (BaseType b = 0) 51bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 52bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton base = b; 53bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton size = 0; 54bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 55bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 56257663e753af15633e48c7b00eb7b5880168090bGreg Clayton // Set the start value for the range, and keep the same size 5761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton BaseType 5861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton GetRangeBase () const 59257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 60257663e753af15633e48c7b00eb7b5880168090bGreg Clayton return base; 61257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 62257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 63257663e753af15633e48c7b00eb7b5880168090bGreg Clayton void 6461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton SetRangeBase (BaseType b) 65257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 66257663e753af15633e48c7b00eb7b5880168090bGreg Clayton base = b; 67257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 68257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 69bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton void 70bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton Slide (BaseType slide) 71bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 72bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton base += slide; 73bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 74bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 7561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton BaseType 7661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton GetRangeEnd () const 77257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 78257663e753af15633e48c7b00eb7b5880168090bGreg Clayton return base + size; 79257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 80257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 81257663e753af15633e48c7b00eb7b5880168090bGreg Clayton void 8261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton SetRangeEnd (BaseType end) 83257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 84257663e753af15633e48c7b00eb7b5880168090bGreg Clayton if (end > base) 85257663e753af15633e48c7b00eb7b5880168090bGreg Clayton size = end - base; 86257663e753af15633e48c7b00eb7b5880168090bGreg Clayton else 87257663e753af15633e48c7b00eb7b5880168090bGreg Clayton size = 0; 88257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 89257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 9061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton SizeType 9161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton GetByteSize () const 92257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 93257663e753af15633e48c7b00eb7b5880168090bGreg Clayton return size; 94257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 95257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 96257663e753af15633e48c7b00eb7b5880168090bGreg Clayton void 9761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton SetByteSize (SizeType s) 98257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 99257663e753af15633e48c7b00eb7b5880168090bGreg Clayton size = s; 100257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 101257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 102257663e753af15633e48c7b00eb7b5880168090bGreg Clayton bool 103257663e753af15633e48c7b00eb7b5880168090bGreg Clayton IsValid() const 104257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 105257663e753af15633e48c7b00eb7b5880168090bGreg Clayton return size > 0; 106257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 107257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 108257663e753af15633e48c7b00eb7b5880168090bGreg Clayton bool 10961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton Contains (BaseType r) const 110257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 11161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return (GetRangeBase() <= r) && (r < GetRangeEnd()); 112257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 113257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 114257663e753af15633e48c7b00eb7b5880168090bGreg Clayton bool 11561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton ContainsEndInclusive (BaseType r) const 116257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 11761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return (GetRangeBase() <= r) && (r <= GetRangeEnd()); 118257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 119257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 120257663e753af15633e48c7b00eb7b5880168090bGreg Clayton bool 121257663e753af15633e48c7b00eb7b5880168090bGreg Clayton Contains (const Range& range) const 122257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 12361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return Contains(range.GetRangeBase()) && ContainsEndInclusive(range.GetRangeEnd()); 124257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 125257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 126257663e753af15633e48c7b00eb7b5880168090bGreg Clayton bool 127bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton Overlap (const Range &rhs) const 128bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 129bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton const BaseType lhs_base = this->GetRangeBase(); 130bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton const BaseType rhs_base = rhs.GetRangeBase(); 131bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton const BaseType lhs_end = this->GetRangeEnd(); 132bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton const BaseType rhs_end = rhs.GetRangeEnd(); 133bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton bool result = (lhs_base <= rhs_end) && (lhs_end >= rhs_base); 134bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return result; 135bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 136bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 137bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton bool 138bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton operator < (const Range &rhs) const 139257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 140257663e753af15633e48c7b00eb7b5880168090bGreg Clayton if (base == rhs.base) 141257663e753af15633e48c7b00eb7b5880168090bGreg Clayton return size < rhs.size; 142257663e753af15633e48c7b00eb7b5880168090bGreg Clayton return base < rhs.base; 143257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 144257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 145257663e753af15633e48c7b00eb7b5880168090bGreg Clayton bool 146bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton operator == (const Range &rhs) const 147257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 148257663e753af15633e48c7b00eb7b5880168090bGreg Clayton return base == rhs.base && size == rhs.size; 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 }; 15761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 15861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton //---------------------------------------------------------------------- 15961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // A range array class where you get to define the type of the ranges 16061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // that the collection contains. 16161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton //---------------------------------------------------------------------- 162257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 16361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton template <typename B, typename S> 16461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton class RangeArray 165257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 166bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton public: 167bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton typedef B BaseType; 168bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton typedef S SizeType; 16961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton typedef Range<B,S> Entry; 17061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 171bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton RangeArray () : 172bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton m_entries () 17361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 17461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 17561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 17661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton ~RangeArray() 17761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 17861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 17961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 18061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton void 18161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton Append (const Entry &entry) 18261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 18361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton m_entries.push_back (entry); 18461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 18561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 18661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton void 18761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton Sort () 18861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 18961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if (m_entries.size() > 1) 19061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton std::stable_sort (m_entries.begin(), m_entries.end()); 19161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 19261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 19361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton void 194bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton CombineConsecutiveRanges () 19561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 196bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // Can't combine if ranges if we have zero or one range 197bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (m_entries.size() > 1) 19861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 199bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // The list should be sorted prior to calling this function 200bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton typename std::vector<Entry>::iterator pos; 201bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton typename std::vector<Entry>::iterator end; 202bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton typename std::vector<Entry>::iterator prev; 203bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton bool can_combine = false; 204bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // First we determine if we can combine any of the Entry objects so we 205bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // don't end up allocating and making a new collection for no reason 206bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 20761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 208bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (prev != end && prev->Overlap(*pos)) 209bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 210bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton can_combine = true; 211bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton break; 212bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 21361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 214bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 215bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // We we can combine at least one entry, then we make a new collection 216bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // and populate it accordingly, and then swap it into place. 217bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (can_combine) 21861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 219bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton std::vector<Entry> minimal_ranges; 220bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 221bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 222bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (prev != end && prev->Overlap(*pos)) 223bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton minimal_ranges.back().SetRangeEnd (std::max<BaseType>(prev->GetRangeEnd(), pos->GetRangeEnd())); 224bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton else 225bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton minimal_ranges.push_back (*pos); 226bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 227bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // Use the swap technique in case our new vector is much smaller. 228bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // We must swap when using the STL because std::vector objects never 229bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // release or reduce the memory once it has been allocated/reserved. 230bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton m_entries.swap (minimal_ranges); 23161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 23261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 23361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 234bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 235bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 236bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton BaseType 237bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton GetMinRangeBase (BaseType fail_value) const 238bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 239bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (m_entries.empty()) 240bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return fail_value; 241bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // m_entries must be sorted, so if we aren't empty, we grab the 242bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // first range's base 243bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return m_entries.front().GetRangeBase(); 244bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 245bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 246bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton BaseType 247bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton GetMaxRangeEnd (BaseType fail_value) const 248bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 249bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (m_entries.empty()) 250bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return fail_value; 251bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // m_entries must be sorted, so if we aren't empty, we grab the 252bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // last range's end 253bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return m_entries.back().GetRangeEnd(); 254bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 255bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 256bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton void 257bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton Slide (BaseType slide) 258bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 259bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton typename std::vector<Entry>::iterator pos, end; 260bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos) 261bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton pos->Slide (slide); 262bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 26361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 26461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton void 26561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton Clear () 26661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 26761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton m_entries.clear(); 26861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 26961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 27061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton bool 27161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton IsEmpty () const 27261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 27361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return m_entries.empty(); 27461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 27561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 27661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton size_t 277bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton GetSize () const 27861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 27961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return m_entries.size(); 28061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 28161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 28261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton const Entry * 283bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton GetEntryAtIndex (size_t i) const 28461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 28561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if (i<m_entries.size()) 28661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return &m_entries[i]; 28761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return NULL; 28861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 28961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 290bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // Clients must ensure that "i" is a valid index prior to calling this function 291bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton const Entry & 292bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton GetEntryRef (size_t i) const 293bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 294bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return m_entries[i]; 295bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 296bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 29761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton static bool 29861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton BaseLessThan (const Entry& lhs, const Entry& rhs) 29961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 30061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return lhs.GetRangeBase() < rhs.GetRangeBase(); 30161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 30261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 303bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton uint32_t 304bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton FindEntryIndexThatContains (B addr) const 305bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 306bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if ( !m_entries.empty() ) 307bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 308bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton Entry entry (addr, 1); 309bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton typename std::vector<Entry>::const_iterator begin = m_entries.begin(); 310bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton typename std::vector<Entry>::const_iterator end = m_entries.end(); 311bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton typename std::vector<Entry>::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 312bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 313bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (pos != end && pos->Contains(addr)) 314bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 315bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return std::distance (begin, pos); 316bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 317bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton else if (pos != begin) 318bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 319bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton --pos; 320bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (pos->Contains(addr)) 321bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return std::distance (begin, pos); 322bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 323bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 324bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return UINT32_MAX; 325bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 326bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 32761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton const Entry * 32861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton FindEntryThatContains (B addr) const 32961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 33061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if ( !m_entries.empty() ) 33161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 33261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton Entry entry (addr, 1); 33361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton typename std::vector<Entry>::const_iterator begin = m_entries.begin(); 33461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton typename std::vector<Entry>::const_iterator end = m_entries.end(); 33561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton typename std::vector<Entry>::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 33661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 33761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if (pos != end && pos->Contains(addr)) 33861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 33961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return &(*pos); 34061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 34161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton else if (pos != begin) 34261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 34361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton --pos; 34461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if (pos->Contains(addr)) 34561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 34661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return &(*pos); 34761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 34861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 34961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 35061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return NULL; 35161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 352bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 353bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton const Entry * 354bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton FindEntryThatContains (const Entry &range) const 355bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 356bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if ( !m_entries.empty() ) 357bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 358bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton typename std::vector<Entry>::const_iterator begin = m_entries.begin(); 359bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton typename std::vector<Entry>::const_iterator end = m_entries.end(); 360bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton typename std::vector<Entry>::const_iterator pos = std::lower_bound (begin, end, range, BaseLessThan); 361bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 362bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (pos != end && pos->Contains(range)) 363bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 364bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return &(*pos); 365bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 366bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton else if (pos != begin) 367bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 368bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton --pos; 369bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (pos->Contains(range)) 370bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 371bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return &(*pos); 372bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 373bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 374bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 375bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return NULL; 376bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 377bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 37861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton protected: 37961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton std::vector<Entry> m_entries; 38061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton }; 381257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 38261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton //---------------------------------------------------------------------- 38361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // A simple range with data class where you get to define the type of 38461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // the range base "B", the type used for the range byte size "S", and 38561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // the type for the associated data "T". 38661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton //---------------------------------------------------------------------- 38761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton template <typename B, typename S, typename T> 38861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton struct RangeData : public Range<B,S> 38961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 39061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton typedef T DataType; 39161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 39261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton DataType data; 39361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 39461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton RangeData () : 39561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton Range<B,S> (), 396257663e753af15633e48c7b00eb7b5880168090bGreg Clayton data () 397257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 398257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 39961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 40061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton RangeData (B base, S size, DataType d) : 40161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton Range<B,S> (base, size), 402257663e753af15633e48c7b00eb7b5880168090bGreg Clayton data (d) 403257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 404257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 40561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 406257663e753af15633e48c7b00eb7b5880168090bGreg Clayton bool 40761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton operator < (const RangeData &rhs) const 408257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 40961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if (this->base == rhs.base) 410257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 41161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if (this->size == rhs.size) 41261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return this->data < rhs.data; 413257663e753af15633e48c7b00eb7b5880168090bGreg Clayton else 41461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return this->size < rhs.size; 415257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 41661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return this->base < rhs.base; 417257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 41861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 419257663e753af15633e48c7b00eb7b5880168090bGreg Clayton bool 42061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton operator == (const RangeData &rhs) const 421257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 42261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return this->GetRangeBase() == rhs.GetRangeBase() && 42361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton this->GetByteSize() == rhs.GetByteSize() && 42461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton this->data == rhs.data; 425257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 42661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 427257663e753af15633e48c7b00eb7b5880168090bGreg Clayton bool 42861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton operator != (const RangeData &rhs) const 429257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 43061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return this->GetRangeBase() != rhs.GetRangeBase() || 43161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton this->GetByteSize() != rhs.GetByteSize() || 43261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton this->data != rhs.data; 433257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 434257663e753af15633e48c7b00eb7b5880168090bGreg Clayton }; 435257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 43661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton template <typename B, typename S, typename T> 43761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton class RangeDataArray 438257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 43961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton public: 44061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton typedef RangeData<B,S,T> Entry; 44161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 44261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton RangeDataArray () 44361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 444257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 445257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 44661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton ~RangeDataArray() 44761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 44861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 44961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 45061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton void 45161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton Append (const Entry &entry) 452257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 45361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton m_entries.push_back (entry); 45461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 45561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 45661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton void 45761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton Sort () 45861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 45961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if (m_entries.size() > 1) 46061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton std::stable_sort (m_entries.begin(), m_entries.end()); 46161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 46261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 46361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton void 46461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton CombineConsecutiveEntriesWithEqualData () 46561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 46661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton typename std::vector<Entry>::iterator pos; 46761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton typename std::vector<Entry>::iterator end; 46861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton typename std::vector<Entry>::iterator prev; 46961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton bool can_combine = false; 47061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // First we determine if we can combine any of the Entry objects so we 47161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // don't end up allocating and making a new collection for no reason 472257663e753af15633e48c7b00eb7b5880168090bGreg Clayton for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 473257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 474257663e753af15633e48c7b00eb7b5880168090bGreg Clayton if (prev != end && prev->data == pos->data) 47561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 47661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton can_combine = true; 47761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton break; 47861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 479257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 480257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 48161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // We we can combine at least one entry, then we make a new collection 48261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // and populate it accordingly, and then swap it into place. 48361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if (can_combine) 484257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 48561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton std::vector<Entry> minimal_ranges; 48661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 48761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 48861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if (prev != end && prev->data == pos->data) 48961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton minimal_ranges.back().SetRangeEnd (pos->GetRangeEnd()); 49061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton else 49161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton minimal_ranges.push_back (*pos); 49261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 49361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // Use the swap technique in case our new vector is much smaller. 49461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // We must swap when using the STL because std::vector objects never 49561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // release or reduce the memory once it has been allocated/reserved. 49661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton m_entries.swap (minimal_ranges); 497257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 49861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 49961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 50061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton void 50161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton Clear () 50261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 50361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton m_entries.clear(); 50461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 50561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 50661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton bool 50761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton IsEmpty () const 50861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 50961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return m_entries.empty(); 51061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 51161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 51261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton size_t 513bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton GetSize () const 51461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 51561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return m_entries.size(); 51661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 51761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 51861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton const Entry * 519bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton GetEntryAtIndex (size_t i) const 52061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 52161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if (i<m_entries.size()) 52261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return &m_entries[i]; 52361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return NULL; 52461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 525bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 526bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // Clients must ensure that "i" is a valid index prior to calling this function 527bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton const Entry & 528bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton GetEntryRef (size_t i) const 529bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 530bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return m_entries[i]; 531bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 532bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 53361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton static bool 53461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton BaseLessThan (const Entry& lhs, const Entry& rhs) 53561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 53661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return lhs.GetRangeBase() < rhs.GetRangeBase(); 53761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 53861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 539bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton uint32_t 540bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton FindEntryIndexThatContains (B addr) const 541bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 542bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if ( !m_entries.empty() ) 543bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 544bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton Entry entry (addr, 1); 545bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton typename std::vector<Entry>::const_iterator begin = m_entries.begin(); 546bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton typename std::vector<Entry>::const_iterator end = m_entries.end(); 547bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton typename std::vector<Entry>::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 548bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 549bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (pos != end && pos->Contains(addr)) 550bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 551bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return std::distance (begin, pos); 552bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 553bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton else if (pos != begin) 554bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 555bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton --pos; 556bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (pos->Contains(addr)) 557bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return std::distance (begin, pos); 558bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 559bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 560bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return UINT32_MAX; 561bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 562bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 56361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton const Entry * 56461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton FindEntryThatContains (B addr) const 56561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 56661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if ( !m_entries.empty() ) 567257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 56861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton Entry entry; 56961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton entry.SetRangeBase(addr); 57061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton entry.SetByteSize(1); 57161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton typename std::vector<Entry>::const_iterator begin = m_entries.begin(); 57261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton typename std::vector<Entry>::const_iterator end = m_entries.end(); 57361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton typename std::vector<Entry>::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 57461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 57561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if (pos != end && pos->Contains(addr)) 576257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 577257663e753af15633e48c7b00eb7b5880168090bGreg Clayton return &(*pos); 578257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 57961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton else if (pos != begin) 58061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 58161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton --pos; 58261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if (pos->Contains(addr)) 58361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 58461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return &(*pos); 58561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 58661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 587257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 58861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return NULL; 589257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 59061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 591bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton const Entry * 592bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton FindEntryThatContains (const Entry &range) const 593bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 594bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if ( !m_entries.empty() ) 595bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 596bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton typename std::vector<Entry>::const_iterator begin = m_entries.begin(); 597bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton typename std::vector<Entry>::const_iterator end = m_entries.end(); 598bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton typename std::vector<Entry>::const_iterator pos = std::lower_bound (begin, end, range, BaseLessThan); 599bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 600bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (pos != end && pos->Contains(range)) 601bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 602bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return &(*pos); 603bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 604bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton else if (pos != begin) 605bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 606bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton --pos; 607bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (pos->Contains(range)) 608bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 609bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return &(*pos); 610bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 611bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 612bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 613bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return NULL; 614bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 615bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 616bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 61761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton protected: 61861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton std::vector<Entry> m_entries; 61961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton }; 620257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 621257663e753af15633e48c7b00eb7b5880168090bGreg Clayton} // namespace lldb_private 622257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 623257663e753af15633e48c7b00eb7b5880168090bGreg Clayton#endif // liblldb_RangeMap_h_ 624