RangeMap.h revision be42123fa214b039b86ad152bd21d910db7a7af2
1257663e753af15633e48c7b00eb7b5880168090bGreg Clayton//===-- RangeMap.h ----------------------------------------------*- C++ -*-===// 2257663e753af15633e48c7b00eb7b5880168090bGreg Clayton// 3257663e753af15633e48c7b00eb7b5880168090bGreg Clayton// The LLVM Compiler Infrastructure 4257663e753af15633e48c7b00eb7b5880168090bGreg Clayton// 5257663e753af15633e48c7b00eb7b5880168090bGreg Clayton// This file is distributed under the University of Illinois Open Source 6257663e753af15633e48c7b00eb7b5880168090bGreg Clayton// License. See LICENSE.TXT for details. 7257663e753af15633e48c7b00eb7b5880168090bGreg Clayton// 8257663e753af15633e48c7b00eb7b5880168090bGreg Clayton//===----------------------------------------------------------------------===// 9257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 10257663e753af15633e48c7b00eb7b5880168090bGreg Clayton#ifndef liblldb_RangeMap_h_ 11257663e753af15633e48c7b00eb7b5880168090bGreg Clayton#define liblldb_RangeMap_h_ 12257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 13257663e753af15633e48c7b00eb7b5880168090bGreg Clayton#include "lldb/lldb-private.h" 14be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton#include "llvm/ADT/SmallVector.h" 15257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 16c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton// Uncomment to make sure all Range objects are sorted when needed 17c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton//#define ASSERT_RANGEMAP_ARE_SORTED 18c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton 19257663e753af15633e48c7b00eb7b5880168090bGreg Claytonnamespace lldb_private { 20257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 2161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton //---------------------------------------------------------------------- 2261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // Templatized classes for dealing with generic ranges and also 2361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // collections of ranges, or collections of ranges that have associated 2461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // data. 2561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton //---------------------------------------------------------------------- 2661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 2761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton //---------------------------------------------------------------------- 2861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // A simple range class where you get to define the type of the range 2961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // base "B", and the type used for the range byte size "S". 3061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton //---------------------------------------------------------------------- 3161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton template <typename B, typename S> 32257663e753af15633e48c7b00eb7b5880168090bGreg Clayton struct Range 33257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 3461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton typedef B BaseType; 3561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton typedef S SizeType; 3661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 3761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton BaseType base; 3861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton SizeType size; 39257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 40257663e753af15633e48c7b00eb7b5880168090bGreg Clayton Range () : 41257663e753af15633e48c7b00eb7b5880168090bGreg Clayton base (0), 42257663e753af15633e48c7b00eb7b5880168090bGreg Clayton size (0) 43257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 44257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 45257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 4661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton Range (BaseType b, SizeType s) : 47257663e753af15633e48c7b00eb7b5880168090bGreg Clayton base (b), 48257663e753af15633e48c7b00eb7b5880168090bGreg Clayton size (s) 49257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 50257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 51257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 52bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton void 53bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton Clear (BaseType b = 0) 54bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 55bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton base = b; 56bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton size = 0; 57bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 58bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 59257663e753af15633e48c7b00eb7b5880168090bGreg Clayton // Set the start value for the range, and keep the same size 6061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton BaseType 6161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton GetRangeBase () const 62257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 63257663e753af15633e48c7b00eb7b5880168090bGreg Clayton return base; 64257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 65257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 66257663e753af15633e48c7b00eb7b5880168090bGreg Clayton void 6761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton SetRangeBase (BaseType b) 68257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 69257663e753af15633e48c7b00eb7b5880168090bGreg Clayton base = b; 70257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 71257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 72bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton void 73bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton Slide (BaseType slide) 74bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 75bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton base += slide; 76bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 77bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 7861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton BaseType 7961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton GetRangeEnd () const 80257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 81257663e753af15633e48c7b00eb7b5880168090bGreg Clayton return base + size; 82257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 83257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 84257663e753af15633e48c7b00eb7b5880168090bGreg Clayton void 8561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton SetRangeEnd (BaseType end) 86257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 87257663e753af15633e48c7b00eb7b5880168090bGreg Clayton if (end > base) 88257663e753af15633e48c7b00eb7b5880168090bGreg Clayton size = end - base; 89257663e753af15633e48c7b00eb7b5880168090bGreg Clayton else 90257663e753af15633e48c7b00eb7b5880168090bGreg Clayton size = 0; 91257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 92257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 9361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton SizeType 9461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton GetByteSize () const 95257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 96257663e753af15633e48c7b00eb7b5880168090bGreg Clayton return size; 97257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 98257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 99257663e753af15633e48c7b00eb7b5880168090bGreg Clayton void 10061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton SetByteSize (SizeType s) 101257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 102257663e753af15633e48c7b00eb7b5880168090bGreg Clayton size = s; 103257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 104257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 105257663e753af15633e48c7b00eb7b5880168090bGreg Clayton bool 106257663e753af15633e48c7b00eb7b5880168090bGreg Clayton IsValid() const 107257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 108257663e753af15633e48c7b00eb7b5880168090bGreg Clayton return size > 0; 109257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 110257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 111257663e753af15633e48c7b00eb7b5880168090bGreg Clayton bool 11261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton Contains (BaseType r) const 113257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 11461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return (GetRangeBase() <= r) && (r < GetRangeEnd()); 115257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 116257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 117257663e753af15633e48c7b00eb7b5880168090bGreg Clayton bool 11861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton ContainsEndInclusive (BaseType r) const 119257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 12061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return (GetRangeBase() <= r) && (r <= GetRangeEnd()); 121257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 122257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 123257663e753af15633e48c7b00eb7b5880168090bGreg Clayton bool 124257663e753af15633e48c7b00eb7b5880168090bGreg Clayton Contains (const Range& range) const 125257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 12661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return Contains(range.GetRangeBase()) && ContainsEndInclusive(range.GetRangeEnd()); 127257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 128257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 129257663e753af15633e48c7b00eb7b5880168090bGreg Clayton bool 130bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton Overlap (const Range &rhs) const 131bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 132bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton const BaseType lhs_base = this->GetRangeBase(); 133bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton const BaseType rhs_base = rhs.GetRangeBase(); 134bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton const BaseType lhs_end = this->GetRangeEnd(); 135bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton const BaseType rhs_end = rhs.GetRangeEnd(); 136bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton bool result = (lhs_base <= rhs_end) && (lhs_end >= rhs_base); 137bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return result; 138bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 139bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 140bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton bool 141bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton operator < (const Range &rhs) const 142257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 143257663e753af15633e48c7b00eb7b5880168090bGreg Clayton if (base == rhs.base) 144257663e753af15633e48c7b00eb7b5880168090bGreg Clayton return size < rhs.size; 145257663e753af15633e48c7b00eb7b5880168090bGreg Clayton return base < rhs.base; 146257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 147257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 148257663e753af15633e48c7b00eb7b5880168090bGreg Clayton bool 149bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton operator == (const Range &rhs) const 150257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 151257663e753af15633e48c7b00eb7b5880168090bGreg Clayton return base == rhs.base && size == rhs.size; 152257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 153257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 154257663e753af15633e48c7b00eb7b5880168090bGreg Clayton bool 155bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton operator != (const Range &rhs) const 156257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 157257663e753af15633e48c7b00eb7b5880168090bGreg Clayton return base != rhs.base || size != rhs.size; 158257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 159257663e753af15633e48c7b00eb7b5880168090bGreg Clayton }; 16061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 16161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton //---------------------------------------------------------------------- 16261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // A range array class where you get to define the type of the ranges 16361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // that the collection contains. 16461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton //---------------------------------------------------------------------- 165257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 166be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton template <typename B, typename S, unsigned N> 16761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton class RangeArray 168257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 169bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton public: 170bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton typedef B BaseType; 171bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton typedef S SizeType; 17261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton typedef Range<B,S> Entry; 173be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton //typedef std::vector<Entry> Collection; 174be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typedef llvm::SmallVector<Entry, N> Collection; 17561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 176bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton RangeArray () : 177bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton m_entries () 17861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 17961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 18061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 18161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton ~RangeArray() 18261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 18361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 18461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 18561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton void 18661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton Append (const Entry &entry) 18761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 18861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton m_entries.push_back (entry); 18961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 19061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 19161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton void 19261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton Sort () 19361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 19461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if (m_entries.size() > 1) 19561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton std::stable_sort (m_entries.begin(), m_entries.end()); 19661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 19761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 198c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 199c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton bool 200c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton IsSorted () const 201c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton { 202be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator pos, end, prev; 203c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton // First we determine if we can combine any of the Entry objects so we 204c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton // don't end up allocating and making a new collection for no reason 205c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 206c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton { 207c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton if (prev != end && *pos < *prev) 208c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton return false; 209c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton } 210c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton return true; 211c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton } 212c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#endif 21361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton void 214bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton CombineConsecutiveRanges () 21561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 216c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 217c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton assert (IsSorted()); 218c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#endif 219bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // Can't combine if ranges if we have zero or one range 220bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (m_entries.size() > 1) 22161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 222bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // The list should be sorted prior to calling this function 223be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::iterator pos; 224be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::iterator end; 225be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::iterator prev; 226bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton bool can_combine = false; 227bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // First we determine if we can combine any of the Entry objects so we 228bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // don't end up allocating and making a new collection for no reason 229bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 23061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 231bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (prev != end && prev->Overlap(*pos)) 232bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 233bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton can_combine = true; 234bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton break; 235bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 23661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 237bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 238bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // We we can combine at least one entry, then we make a new collection 239bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // and populate it accordingly, and then swap it into place. 240bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (can_combine) 24161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 242be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton Collection minimal_ranges; 243bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 244bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 245bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (prev != end && prev->Overlap(*pos)) 246bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton minimal_ranges.back().SetRangeEnd (std::max<BaseType>(prev->GetRangeEnd(), pos->GetRangeEnd())); 247bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton else 248bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton minimal_ranges.push_back (*pos); 249bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 250bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // Use the swap technique in case our new vector is much smaller. 251bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // We must swap when using the STL because std::vector objects never 252bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // release or reduce the memory once it has been allocated/reserved. 253bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton m_entries.swap (minimal_ranges); 25461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 25561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 25661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 257bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 258bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 259bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton BaseType 260bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton GetMinRangeBase (BaseType fail_value) const 261bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 262c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 263c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton assert (IsSorted()); 264c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#endif 265bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (m_entries.empty()) 266bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return fail_value; 267bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // m_entries must be sorted, so if we aren't empty, we grab the 268bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // first range's base 269bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return m_entries.front().GetRangeBase(); 270bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 271bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 272bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton BaseType 273bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton GetMaxRangeEnd (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 // last range's end 282bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return m_entries.back().GetRangeEnd(); 283bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 284bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 285bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton void 286bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton Slide (BaseType slide) 287bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 288be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::iterator pos, end; 289bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos) 290bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton pos->Slide (slide); 291bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 29261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 29361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton void 29461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton Clear () 29561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 29661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton m_entries.clear(); 29761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 29861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 29961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton bool 30061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton IsEmpty () const 30161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 30261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return m_entries.empty(); 30361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 30461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 30561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton size_t 306bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton GetSize () const 30761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 30861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return m_entries.size(); 30961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 31061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 31161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton const Entry * 312bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton GetEntryAtIndex (size_t i) const 31361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 31461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if (i<m_entries.size()) 31561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return &m_entries[i]; 31661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return NULL; 31761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 31861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 319bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // Clients must ensure that "i" is a valid index prior to calling this function 320bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton const Entry & 321bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton GetEntryRef (size_t i) const 322bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 323bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return m_entries[i]; 324bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 325bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 32661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton static bool 32761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton BaseLessThan (const Entry& lhs, const Entry& rhs) 32861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 32961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return lhs.GetRangeBase() < rhs.GetRangeBase(); 33061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 33161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 332bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton uint32_t 333bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton FindEntryIndexThatContains (B addr) const 334bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 335c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 336c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton assert (IsSorted()); 337c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#endif 338c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton if (!m_entries.empty()) 339bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 340bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton Entry entry (addr, 1); 341be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator begin = m_entries.begin(); 342be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator end = m_entries.end(); 343be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 344bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 345bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (pos != end && pos->Contains(addr)) 346bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 347bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return std::distance (begin, pos); 348bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 349bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton else if (pos != begin) 350bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 351bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton --pos; 352bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (pos->Contains(addr)) 353bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return std::distance (begin, pos); 354bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 355bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 356bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return UINT32_MAX; 357bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 358bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 35961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton const Entry * 36061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton FindEntryThatContains (B addr) const 36161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 362c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 363c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton assert (IsSorted()); 364c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#endif 365c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton if (!m_entries.empty()) 36661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 36761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton Entry entry (addr, 1); 368be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator begin = m_entries.begin(); 369be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator end = m_entries.end(); 370be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 37161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 37261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if (pos != end && pos->Contains(addr)) 37361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 37461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return &(*pos); 37561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 37661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton else if (pos != begin) 37761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 37861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton --pos; 37961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if (pos->Contains(addr)) 38061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 38161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return &(*pos); 38261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 38361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 38461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 38561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return NULL; 38661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 387bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 388bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton const Entry * 389bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton FindEntryThatContains (const Entry &range) const 390bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 391c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 392c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton assert (IsSorted()); 393c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#endif 394c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton if (!m_entries.empty()) 395bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 396be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator begin = m_entries.begin(); 397be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator end = m_entries.end(); 398be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator pos = std::lower_bound (begin, end, range, BaseLessThan); 399bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 400bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (pos != end && pos->Contains(range)) 401bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 402bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return &(*pos); 403bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 404bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton else if (pos != begin) 405bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 406bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton --pos; 407bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (pos->Contains(range)) 408bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 409bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return &(*pos); 410bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 411bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 412bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 413bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return NULL; 414bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 415bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 41661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton protected: 417be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton Collection m_entries; 41861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton }; 419257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 42061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton //---------------------------------------------------------------------- 42161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // A simple range with data class where you get to define the type of 42261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // the range base "B", the type used for the range byte size "S", and 42361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // the type for the associated data "T". 42461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton //---------------------------------------------------------------------- 42561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton template <typename B, typename S, typename T> 42661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton struct RangeData : public Range<B,S> 42761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 42861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton typedef T DataType; 42961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 43061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton DataType data; 43161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 43261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton RangeData () : 43361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton Range<B,S> (), 434257663e753af15633e48c7b00eb7b5880168090bGreg Clayton data () 435257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 436257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 43761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 43861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton RangeData (B base, S size, DataType d) : 43961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton Range<B,S> (base, size), 440257663e753af15633e48c7b00eb7b5880168090bGreg Clayton data (d) 441257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 442257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 44361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 444257663e753af15633e48c7b00eb7b5880168090bGreg Clayton bool 44561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton operator < (const RangeData &rhs) const 446257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 44761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if (this->base == rhs.base) 448257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 44961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if (this->size == rhs.size) 45061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return this->data < rhs.data; 451257663e753af15633e48c7b00eb7b5880168090bGreg Clayton else 45261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return this->size < rhs.size; 453257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 45461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return this->base < rhs.base; 455257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 45661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 457257663e753af15633e48c7b00eb7b5880168090bGreg Clayton bool 45861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton operator == (const RangeData &rhs) const 459257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 46061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return this->GetRangeBase() == rhs.GetRangeBase() && 46161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton this->GetByteSize() == rhs.GetByteSize() && 46261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton this->data == rhs.data; 463257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 46461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 465257663e753af15633e48c7b00eb7b5880168090bGreg Clayton bool 46661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton operator != (const RangeData &rhs) const 467257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 46861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return this->GetRangeBase() != rhs.GetRangeBase() || 46961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton this->GetByteSize() != rhs.GetByteSize() || 47061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton this->data != rhs.data; 471257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 472257663e753af15633e48c7b00eb7b5880168090bGreg Clayton }; 473257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 474be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton template <typename B, typename S, typename T, unsigned N> 47561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton class RangeDataArray 476257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 47761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton public: 47861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton typedef RangeData<B,S,T> Entry; 479be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton //typedef std::vector<Entry> Collection; 480be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typedef llvm::SmallVector<Entry, N> Collection; 481be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton 482be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton 48361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton RangeDataArray () 48461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 485257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 486257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 48761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton ~RangeDataArray() 48861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 48961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 49061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 49161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton void 49261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton Append (const Entry &entry) 493257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 49461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton m_entries.push_back (entry); 49561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 49661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 49761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton void 49861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton Sort () 49961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 50061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if (m_entries.size() > 1) 50161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton std::stable_sort (m_entries.begin(), m_entries.end()); 50261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 50361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 504c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 505c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton bool 506c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton IsSorted () const 507c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton { 508be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator pos, end, prev; 509c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton // First we determine if we can combine any of the Entry objects so we 510c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton // don't end up allocating and making a new collection for no reason 511c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 512c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton { 513c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton if (prev != end && *pos < *prev) 514c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton return false; 515c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton } 516c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton return true; 517c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton } 518c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#endif 519c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton 52061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton void 52161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton CombineConsecutiveEntriesWithEqualData () 52261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 523c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 524c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton assert (IsSorted()); 525c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#endif 526be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::iterator pos; 527be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::iterator end; 528be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::iterator prev; 52961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton bool can_combine = false; 53061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // First we determine if we can combine any of the Entry objects so we 53161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // don't end up allocating and making a new collection for no reason 532257663e753af15633e48c7b00eb7b5880168090bGreg Clayton for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 533257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 534257663e753af15633e48c7b00eb7b5880168090bGreg Clayton if (prev != end && prev->data == pos->data) 53561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 53661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton can_combine = true; 53761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton break; 53861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 539257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 540257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 54161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // We we can combine at least one entry, then we make a new collection 54261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // and populate it accordingly, and then swap it into place. 54361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if (can_combine) 544257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 545be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton Collection minimal_ranges; 54661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 54761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 54861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if (prev != end && prev->data == pos->data) 54961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton minimal_ranges.back().SetRangeEnd (pos->GetRangeEnd()); 55061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton else 55161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton minimal_ranges.push_back (*pos); 55261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 55361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // Use the swap technique in case our new vector is much smaller. 55461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // We must swap when using the STL because std::vector objects never 55561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton // release or reduce the memory once it has been allocated/reserved. 55661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton m_entries.swap (minimal_ranges); 557257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 55861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 55961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 56061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton void 56161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton Clear () 56261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 56361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton m_entries.clear(); 56461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 56561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 56661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton bool 56761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton IsEmpty () const 56861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 56961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return m_entries.empty(); 57061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 57161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 57261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton size_t 573bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton GetSize () const 57461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 57561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return m_entries.size(); 57661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 57761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 57861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton const Entry * 579bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton GetEntryAtIndex (size_t i) const 58061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 58161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if (i<m_entries.size()) 58261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return &m_entries[i]; 58361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return NULL; 58461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 585bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 586bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton // Clients must ensure that "i" is a valid index prior to calling this function 587bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton const Entry & 588bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton GetEntryRef (size_t i) const 589bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 590bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return m_entries[i]; 591bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 592bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 59361aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton static bool 59461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton BaseLessThan (const Entry& lhs, const Entry& rhs) 59561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 59661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return lhs.GetRangeBase() < rhs.GetRangeBase(); 59761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 59861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 599bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton uint32_t 600bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton FindEntryIndexThatContains (B addr) const 601bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 602c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 603c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton assert (IsSorted()); 604c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#endif 605bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if ( !m_entries.empty() ) 606bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 607bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton Entry entry (addr, 1); 608be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator begin = m_entries.begin(); 609be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator end = m_entries.end(); 610be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 611bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 612bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (pos != end && pos->Contains(addr)) 613bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 614bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return std::distance (begin, pos); 615bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 616bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton else if (pos != begin) 617bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 618bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton --pos; 619bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (pos->Contains(addr)) 620bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return std::distance (begin, pos); 621bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 622bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 623bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return UINT32_MAX; 624bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 625bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 62661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton const Entry * 62761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton FindEntryThatContains (B addr) const 62861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 629c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 630c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton assert (IsSorted()); 631c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#endif 63261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if ( !m_entries.empty() ) 633257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 63461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton Entry entry; 63561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton entry.SetRangeBase(addr); 63661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton entry.SetByteSize(1); 637be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator begin = m_entries.begin(); 638be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator end = m_entries.end(); 639be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 64061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 64161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if (pos != end && pos->Contains(addr)) 642257663e753af15633e48c7b00eb7b5880168090bGreg Clayton { 643257663e753af15633e48c7b00eb7b5880168090bGreg Clayton return &(*pos); 644257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 64561aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton else if (pos != begin) 64661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 64761aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton --pos; 64861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton if (pos->Contains(addr)) 64961aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton { 65061aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return &(*pos); 65161aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 65261aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton } 653257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 65461aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton return NULL; 655257663e753af15633e48c7b00eb7b5880168090bGreg Clayton } 65661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton 657bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton const Entry * 658bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton FindEntryThatContains (const Entry &range) const 659bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 660c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#ifdef ASSERT_RANGEMAP_ARE_SORTED 661c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton assert (IsSorted()); 662c03a99ae9cced3e3086f10db444ddc90d115a3f3Greg Clayton#endif 663bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if ( !m_entries.empty() ) 664bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 665be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator begin = m_entries.begin(); 666be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator end = m_entries.end(); 667be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton typename Collection::const_iterator pos = std::lower_bound (begin, end, range, BaseLessThan); 668bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 669bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (pos != end && pos->Contains(range)) 670bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 671bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return &(*pos); 672bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 673bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton else if (pos != begin) 674bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 675bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton --pos; 676bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton if (pos->Contains(range)) 677bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton { 678bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return &(*pos); 679bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 680bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 681bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 682bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton return NULL; 683bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton } 684bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 685bc36a861b8e0b2f2dde34f27c9fa9629a357d598Greg Clayton 68661aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton protected: 687be42123fa214b039b86ad152bd21d910db7a7af2Greg Clayton Collection m_entries; 68861aca5dd78f07de66e997d41af521ab9d8c16b89Greg Clayton }; 689257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 690257663e753af15633e48c7b00eb7b5880168090bGreg Clayton} // namespace lldb_private 691257663e753af15633e48c7b00eb7b5880168090bGreg Clayton 692257663e753af15633e48c7b00eb7b5880168090bGreg Clayton#endif // liblldb_RangeMap_h_ 693