1 //===-- RangeMap.h ----------------------------------------------*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #ifndef liblldb_RangeMap_h_
11 #define liblldb_RangeMap_h_
12 
13 #include <algorithm>
14 #include <vector>
15 
16 #include "llvm/ADT/SmallVector.h"
17 
18 #include "lldb/lldb-private.h"
19 
20 // Uncomment to make sure all Range objects are sorted when needed
21 //#define ASSERT_RANGEMAP_ARE_SORTED
22 
23 namespace lldb_private {
24 
25 //----------------------------------------------------------------------
26 // Templatized classes for dealing with generic ranges and also collections of
27 // ranges, or collections of ranges that have associated data.
28 //----------------------------------------------------------------------
29 
30 //----------------------------------------------------------------------
31 // A simple range class where you get to define the type of the range
32 // base "B", and the type used for the range byte size "S".
33 //----------------------------------------------------------------------
34 template <typename B, typename S> struct Range {
35   typedef B BaseType;
36   typedef S SizeType;
37 
38   BaseType base;
39   SizeType size;
40 
RangeRange41   Range() : base(0), size(0) {}
42 
RangeRange43   Range(BaseType b, SizeType s) : base(b), size(s) {}
44 
45   void Clear(BaseType b = 0) {
46     base = b;
47     size = 0;
48   }
49 
50   // Set the start value for the range, and keep the same size
GetRangeBaseRange51   BaseType GetRangeBase() const { return base; }
52 
SetRangeBaseRange53   void SetRangeBase(BaseType b) { base = b; }
54 
SlideRange55   void Slide(BaseType slide) { base += slide; }
56 
UnionRange57   bool Union(const Range &rhs)
58   {
59     if (DoesAdjoinOrIntersect(rhs))
60     {
61       auto new_end = std::max<BaseType>(GetRangeEnd(), rhs.GetRangeEnd());
62       base = std::min<BaseType>(base, rhs.base);
63       size = new_end - base;
64       return true;
65     }
66     return false;
67   }
68 
GetRangeEndRange69   BaseType GetRangeEnd() const { return base + size; }
70 
SetRangeEndRange71   void SetRangeEnd(BaseType end) {
72     if (end > base)
73       size = end - base;
74     else
75       size = 0;
76   }
77 
GetByteSizeRange78   SizeType GetByteSize() const { return size; }
79 
SetByteSizeRange80   void SetByteSize(SizeType s) { size = s; }
81 
IsValidRange82   bool IsValid() const { return size > 0; }
83 
ContainsRange84   bool Contains(BaseType r) const {
85     return (GetRangeBase() <= r) && (r < GetRangeEnd());
86   }
87 
ContainsEndInclusiveRange88   bool ContainsEndInclusive(BaseType r) const {
89     return (GetRangeBase() <= r) && (r <= GetRangeEnd());
90   }
91 
ContainsRange92   bool Contains(const Range &range) const {
93     return Contains(range.GetRangeBase()) &&
94            ContainsEndInclusive(range.GetRangeEnd());
95   }
96 
97   // Returns true if the two ranges adjoing or intersect
DoesAdjoinOrIntersectRange98   bool DoesAdjoinOrIntersect(const Range &rhs) const {
99     const BaseType lhs_base = this->GetRangeBase();
100     const BaseType rhs_base = rhs.GetRangeBase();
101     const BaseType lhs_end = this->GetRangeEnd();
102     const BaseType rhs_end = rhs.GetRangeEnd();
103     bool result = (lhs_base <= rhs_end) && (lhs_end >= rhs_base);
104     return result;
105   }
106 
107   // Returns true if the two ranges intersect
DoesIntersectRange108   bool DoesIntersect(const Range &rhs) const {
109     const BaseType lhs_base = this->GetRangeBase();
110     const BaseType rhs_base = rhs.GetRangeBase();
111     const BaseType lhs_end = this->GetRangeEnd();
112     const BaseType rhs_end = rhs.GetRangeEnd();
113     bool result = (lhs_base < rhs_end) && (lhs_end > rhs_base);
114     return result;
115   }
116 
117   bool operator<(const Range &rhs) const {
118     if (base == rhs.base)
119       return size < rhs.size;
120     return base < rhs.base;
121   }
122 
123   bool operator==(const Range &rhs) const {
124     return base == rhs.base && size == rhs.size;
125   }
126 
127   bool operator!=(const Range &rhs) const {
128     return base != rhs.base || size != rhs.size;
129   }
130 };
131 
132 //----------------------------------------------------------------------
133 // A range array class where you get to define the type of the ranges
134 // that the collection contains.
135 //----------------------------------------------------------------------
136 
137 template <typename B, typename S, unsigned N> class RangeArray {
138 public:
139   typedef B BaseType;
140   typedef S SizeType;
141   typedef Range<B, S> Entry;
142   typedef llvm::SmallVector<Entry, N> Collection;
143 
144   RangeArray() = default;
145 
146   ~RangeArray() = default;
147 
Append(const Entry & entry)148   void Append(const Entry &entry) { m_entries.push_back(entry); }
149 
Append(B base,S size)150   void Append(B base, S size) { m_entries.emplace_back(base, size); }
151 
RemoveEntrtAtIndex(uint32_t idx)152   bool RemoveEntrtAtIndex(uint32_t idx) {
153     if (idx < m_entries.size()) {
154       m_entries.erase(m_entries.begin() + idx);
155       return true;
156     }
157     return false;
158   }
159 
Sort()160   void Sort() {
161     if (m_entries.size() > 1)
162       std::stable_sort(m_entries.begin(), m_entries.end());
163   }
164 
165 #ifdef ASSERT_RANGEMAP_ARE_SORTED
IsSorted()166   bool IsSorted() const {
167     typename Collection::const_iterator pos, end, prev;
168     for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end;
169          prev = pos++) {
170       if (prev != end && *pos < *prev)
171         return false;
172     }
173     return true;
174   }
175 #endif
176 
CombineConsecutiveRanges()177   void CombineConsecutiveRanges() {
178 #ifdef ASSERT_RANGEMAP_ARE_SORTED
179     assert(IsSorted());
180 #endif
181     // Can't combine if ranges if we have zero or one range
182     if (m_entries.size() > 1) {
183       // The list should be sorted prior to calling this function
184       typename Collection::iterator pos;
185       typename Collection::iterator end;
186       typename Collection::iterator prev;
187       bool can_combine = false;
188       // First we determine if we can combine any of the Entry objects so we
189       // don't end up allocating and making a new collection for no reason
190       for (pos = m_entries.begin(), end = m_entries.end(), prev = end;
191            pos != end; prev = pos++) {
192         if (prev != end && prev->DoesAdjoinOrIntersect(*pos)) {
193           can_combine = true;
194           break;
195         }
196       }
197 
198       // We we can combine at least one entry, then we make a new collection
199       // and populate it accordingly, and then swap it into place.
200       if (can_combine) {
201         Collection minimal_ranges;
202         for (pos = m_entries.begin(), end = m_entries.end(), prev = end;
203              pos != end; prev = pos++) {
204           if (prev != end && prev->DoesAdjoinOrIntersect(*pos))
205             minimal_ranges.back().SetRangeEnd(
206                 std::max<BaseType>(prev->GetRangeEnd(), pos->GetRangeEnd()));
207           else
208             minimal_ranges.push_back(*pos);
209         }
210         // Use the swap technique in case our new vector is much smaller. We
211         // must swap when using the STL because std::vector objects never
212         // release or reduce the memory once it has been allocated/reserved.
213         m_entries.swap(minimal_ranges);
214       }
215     }
216   }
217 
GetMinRangeBase(BaseType fail_value)218   BaseType GetMinRangeBase(BaseType fail_value) const {
219 #ifdef ASSERT_RANGEMAP_ARE_SORTED
220     assert(IsSorted());
221 #endif
222     if (m_entries.empty())
223       return fail_value;
224     // m_entries must be sorted, so if we aren't empty, we grab the first
225     // range's base
226     return m_entries.front().GetRangeBase();
227   }
228 
GetMaxRangeEnd(BaseType fail_value)229   BaseType GetMaxRangeEnd(BaseType fail_value) const {
230 #ifdef ASSERT_RANGEMAP_ARE_SORTED
231     assert(IsSorted());
232 #endif
233     if (m_entries.empty())
234       return fail_value;
235     // m_entries must be sorted, so if we aren't empty, we grab the last
236     // range's end
237     return m_entries.back().GetRangeEnd();
238   }
239 
Slide(BaseType slide)240   void Slide(BaseType slide) {
241     typename Collection::iterator pos, end;
242     for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos)
243       pos->Slide(slide);
244   }
245 
Clear()246   void Clear() { m_entries.clear(); }
247 
IsEmpty()248   bool IsEmpty() const { return m_entries.empty(); }
249 
GetSize()250   size_t GetSize() const { return m_entries.size(); }
251 
GetEntryAtIndex(size_t i)252   const Entry *GetEntryAtIndex(size_t i) const {
253     return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
254   }
255 
256   // Clients must ensure that "i" is a valid index prior to calling this
257   // function
GetEntryRef(size_t i)258   const Entry &GetEntryRef(size_t i) const { return m_entries[i]; }
259 
Back()260   Entry *Back() { return (m_entries.empty() ? nullptr : &m_entries.back()); }
261 
Back()262   const Entry *Back() const {
263     return (m_entries.empty() ? nullptr : &m_entries.back());
264   }
265 
BaseLessThan(const Entry & lhs,const Entry & rhs)266   static bool BaseLessThan(const Entry &lhs, const Entry &rhs) {
267     return lhs.GetRangeBase() < rhs.GetRangeBase();
268   }
269 
FindEntryIndexThatContains(B addr)270   uint32_t FindEntryIndexThatContains(B addr) const {
271 #ifdef ASSERT_RANGEMAP_ARE_SORTED
272     assert(IsSorted());
273 #endif
274     if (!m_entries.empty()) {
275       Entry entry(addr, 1);
276       typename Collection::const_iterator begin = m_entries.begin();
277       typename Collection::const_iterator end = m_entries.end();
278       typename Collection::const_iterator pos =
279           std::lower_bound(begin, end, entry, BaseLessThan);
280 
281       if (pos != end && pos->Contains(addr)) {
282         return std::distance(begin, pos);
283       } else if (pos != begin) {
284         --pos;
285         if (pos->Contains(addr))
286           return std::distance(begin, pos);
287       }
288     }
289     return UINT32_MAX;
290   }
291 
FindEntryThatContains(B addr)292   const Entry *FindEntryThatContains(B addr) const {
293 #ifdef ASSERT_RANGEMAP_ARE_SORTED
294     assert(IsSorted());
295 #endif
296     if (!m_entries.empty()) {
297       Entry entry(addr, 1);
298       typename Collection::const_iterator begin = m_entries.begin();
299       typename Collection::const_iterator end = m_entries.end();
300       typename Collection::const_iterator pos =
301           std::lower_bound(begin, end, entry, BaseLessThan);
302 
303       if (pos != end && pos->Contains(addr)) {
304         return &(*pos);
305       } else if (pos != begin) {
306         --pos;
307         if (pos->Contains(addr)) {
308           return &(*pos);
309         }
310       }
311     }
312     return nullptr;
313   }
314 
FindEntryThatContains(const Entry & range)315   const Entry *FindEntryThatContains(const Entry &range) const {
316 #ifdef ASSERT_RANGEMAP_ARE_SORTED
317     assert(IsSorted());
318 #endif
319     if (!m_entries.empty()) {
320       typename Collection::const_iterator begin = m_entries.begin();
321       typename Collection::const_iterator end = m_entries.end();
322       typename Collection::const_iterator pos =
323           std::lower_bound(begin, end, range, BaseLessThan);
324 
325       if (pos != end && pos->Contains(range)) {
326         return &(*pos);
327       } else if (pos != begin) {
328         --pos;
329         if (pos->Contains(range)) {
330           return &(*pos);
331         }
332       }
333     }
334     return nullptr;
335   }
336 
337 protected:
338   Collection m_entries;
339 };
340 
341 template <typename B, typename S> class RangeVector {
342 public:
343   typedef B BaseType;
344   typedef S SizeType;
345   typedef Range<B, S> Entry;
346   typedef std::vector<Entry> Collection;
347 
348   RangeVector() = default;
349 
350   ~RangeVector() = default;
351 
Append(const Entry & entry)352   void Append(const Entry &entry) { m_entries.push_back(entry); }
353 
Append(B base,S size)354   void Append(B base, S size) { m_entries.emplace_back(base, size); }
355 
356   // Insert an item into a sorted list and optionally combine it with any
357   // adjacent blocks if requested.
Insert(const Entry & entry,bool combine)358   void Insert(const Entry &entry, bool combine) {
359     if (m_entries.empty()) {
360       m_entries.push_back(entry);
361       return;
362     }
363     auto begin = m_entries.begin();
364     auto end = m_entries.end();
365     auto pos = std::lower_bound(begin, end, entry);
366     if (combine) {
367       if (pos != end && pos->Union(entry)) {
368         CombinePrevAndNext(pos);
369         return;
370       }
371       if (pos != begin) {
372         auto prev = pos - 1;
373         if (prev->Union(entry)) {
374           CombinePrevAndNext(prev);
375           return;
376         }
377       }
378     }
379     m_entries.insert(pos, entry);
380   }
381 
RemoveEntryAtIndex(uint32_t idx)382   bool RemoveEntryAtIndex(uint32_t idx) {
383     if (idx < m_entries.size()) {
384       m_entries.erase(m_entries.begin() + idx);
385       return true;
386     }
387     return false;
388   }
389 
Sort()390   void Sort() {
391     if (m_entries.size() > 1)
392       std::stable_sort(m_entries.begin(), m_entries.end());
393   }
394 
395 #ifdef ASSERT_RANGEMAP_ARE_SORTED
IsSorted()396   bool IsSorted() const {
397     typename Collection::const_iterator pos, end, prev;
398     // First we determine if we can combine any of the Entry objects so we
399     // don't end up allocating and making a new collection for no reason
400     for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end;
401          prev = pos++) {
402       if (prev != end && *pos < *prev)
403         return false;
404     }
405     return true;
406   }
407 #endif
408 
CombineConsecutiveRanges()409   void CombineConsecutiveRanges() {
410 #ifdef ASSERT_RANGEMAP_ARE_SORTED
411     assert(IsSorted());
412 #endif
413     // Can't combine if ranges if we have zero or one range
414     if (m_entries.size() > 1) {
415       // The list should be sorted prior to calling this function
416       typename Collection::iterator pos;
417       typename Collection::iterator end;
418       typename Collection::iterator prev;
419       bool can_combine = false;
420       // First we determine if we can combine any of the Entry objects so we
421       // don't end up allocating and making a new collection for no reason
422       for (pos = m_entries.begin(), end = m_entries.end(), prev = end;
423            pos != end; prev = pos++) {
424         if (prev != end && prev->DoesAdjoinOrIntersect(*pos)) {
425           can_combine = true;
426           break;
427         }
428       }
429 
430       // We we can combine at least one entry, then we make a new collection
431       // and populate it accordingly, and then swap it into place.
432       if (can_combine) {
433         Collection minimal_ranges;
434         for (pos = m_entries.begin(), end = m_entries.end(), prev = end;
435              pos != end; prev = pos++) {
436           if (prev != end && prev->DoesAdjoinOrIntersect(*pos))
437             minimal_ranges.back().SetRangeEnd(
438                 std::max<BaseType>(prev->GetRangeEnd(), pos->GetRangeEnd()));
439           else
440             minimal_ranges.push_back(*pos);
441         }
442         // Use the swap technique in case our new vector is much smaller. We
443         // must swap when using the STL because std::vector objects never
444         // release or reduce the memory once it has been allocated/reserved.
445         m_entries.swap(minimal_ranges);
446       }
447     }
448   }
449 
GetMinRangeBase(BaseType fail_value)450   BaseType GetMinRangeBase(BaseType fail_value) const {
451 #ifdef ASSERT_RANGEMAP_ARE_SORTED
452     assert(IsSorted());
453 #endif
454     if (m_entries.empty())
455       return fail_value;
456     // m_entries must be sorted, so if we aren't empty, we grab the first
457     // range's base
458     return m_entries.front().GetRangeBase();
459   }
460 
GetMaxRangeEnd(BaseType fail_value)461   BaseType GetMaxRangeEnd(BaseType fail_value) const {
462 #ifdef ASSERT_RANGEMAP_ARE_SORTED
463     assert(IsSorted());
464 #endif
465     if (m_entries.empty())
466       return fail_value;
467     // m_entries must be sorted, so if we aren't empty, we grab the last
468     // range's end
469     return m_entries.back().GetRangeEnd();
470   }
471 
Slide(BaseType slide)472   void Slide(BaseType slide) {
473     typename Collection::iterator pos, end;
474     for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos)
475       pos->Slide(slide);
476   }
477 
Clear()478   void Clear() { m_entries.clear(); }
479 
Reserve(typename Collection::size_type size)480   void Reserve(typename Collection::size_type size) { m_entries.reserve(size); }
481 
IsEmpty()482   bool IsEmpty() const { return m_entries.empty(); }
483 
GetSize()484   size_t GetSize() const { return m_entries.size(); }
485 
GetEntryAtIndex(size_t i)486   const Entry *GetEntryAtIndex(size_t i) const {
487     return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
488   }
489 
490   // Clients must ensure that "i" is a valid index prior to calling this
491   // function
GetEntryRef(size_t i)492   Entry &GetEntryRef(size_t i) { return m_entries[i]; }
GetEntryRef(size_t i)493   const Entry &GetEntryRef(size_t i) const { return m_entries[i]; }
494 
Back()495   Entry *Back() { return (m_entries.empty() ? nullptr : &m_entries.back()); }
496 
Back()497   const Entry *Back() const {
498     return (m_entries.empty() ? nullptr : &m_entries.back());
499   }
500 
BaseLessThan(const Entry & lhs,const Entry & rhs)501   static bool BaseLessThan(const Entry &lhs, const Entry &rhs) {
502     return lhs.GetRangeBase() < rhs.GetRangeBase();
503   }
504 
FindEntryIndexThatContains(B addr)505   uint32_t FindEntryIndexThatContains(B addr) const {
506 #ifdef ASSERT_RANGEMAP_ARE_SORTED
507     assert(IsSorted());
508 #endif
509     if (!m_entries.empty()) {
510       Entry entry(addr, 1);
511       typename Collection::const_iterator begin = m_entries.begin();
512       typename Collection::const_iterator end = m_entries.end();
513       typename Collection::const_iterator pos =
514           std::lower_bound(begin, end, entry, BaseLessThan);
515 
516       if (pos != end && pos->Contains(addr)) {
517         return std::distance(begin, pos);
518       } else if (pos != begin) {
519         --pos;
520         if (pos->Contains(addr))
521           return std::distance(begin, pos);
522       }
523     }
524     return UINT32_MAX;
525   }
526 
FindEntryThatContains(B addr)527   const Entry *FindEntryThatContains(B addr) const {
528 #ifdef ASSERT_RANGEMAP_ARE_SORTED
529     assert(IsSorted());
530 #endif
531     if (!m_entries.empty()) {
532       Entry entry(addr, 1);
533       typename Collection::const_iterator begin = m_entries.begin();
534       typename Collection::const_iterator end = m_entries.end();
535       typename Collection::const_iterator pos =
536           std::lower_bound(begin, end, entry, BaseLessThan);
537 
538       if (pos != end && pos->Contains(addr)) {
539         return &(*pos);
540       } else if (pos != begin) {
541         --pos;
542         if (pos->Contains(addr)) {
543           return &(*pos);
544         }
545       }
546     }
547     return nullptr;
548   }
549 
FindEntryThatContains(const Entry & range)550   const Entry *FindEntryThatContains(const Entry &range) const {
551 #ifdef ASSERT_RANGEMAP_ARE_SORTED
552     assert(IsSorted());
553 #endif
554     if (!m_entries.empty()) {
555       typename Collection::const_iterator begin = m_entries.begin();
556       typename Collection::const_iterator end = m_entries.end();
557       typename Collection::const_iterator pos =
558           std::lower_bound(begin, end, range, BaseLessThan);
559 
560       if (pos != end && pos->Contains(range)) {
561         return &(*pos);
562       } else if (pos != begin) {
563         --pos;
564         if (pos->Contains(range)) {
565           return &(*pos);
566         }
567       }
568     }
569     return nullptr;
570   }
571 
572 protected:
573 
CombinePrevAndNext(typename Collection::iterator pos)574   void CombinePrevAndNext(typename Collection::iterator pos) {
575     // Check if the prev or next entries in case they need to be unioned with
576     // the entry pointed to by "pos".
577     if (pos != m_entries.begin()) {
578       auto prev = pos - 1;
579       if (prev->Union(*pos))
580         m_entries.erase(pos);
581       pos = prev;
582     }
583 
584     auto end = m_entries.end();
585     if (pos != end) {
586       auto next = pos + 1;
587       if (next != end) {
588         if (pos->Union(*next))
589           m_entries.erase(next);
590       }
591     }
592     return;
593   }
594 
595   Collection m_entries;
596 };
597 
598 //----------------------------------------------------------------------
599 // A simple range  with data class where you get to define the type of
600 // the range base "B", the type used for the range byte size "S", and the type
601 // for the associated data "T".
602 //----------------------------------------------------------------------
603 template <typename B, typename S, typename T>
604 struct RangeData : public Range<B, S> {
605   typedef T DataType;
606 
607   DataType data;
608 
RangeDataRangeData609   RangeData() : Range<B, S>(), data() {}
610 
RangeDataRangeData611   RangeData(B base, S size) : Range<B, S>(base, size), data() {}
612 
RangeDataRangeData613   RangeData(B base, S size, DataType d) : Range<B, S>(base, size), data(d) {}
614 
615   bool operator<(const RangeData &rhs) const {
616     if (this->base == rhs.base) {
617       if (this->size == rhs.size)
618         return this->data < rhs.data;
619       else
620         return this->size < rhs.size;
621     }
622     return this->base < rhs.base;
623   }
624 
625   bool operator==(const RangeData &rhs) const {
626     return this->GetRangeBase() == rhs.GetRangeBase() &&
627            this->GetByteSize() == rhs.GetByteSize() && this->data == rhs.data;
628   }
629 
630   bool operator!=(const RangeData &rhs) const {
631     return this->GetRangeBase() != rhs.GetRangeBase() ||
632            this->GetByteSize() != rhs.GetByteSize() || this->data != rhs.data;
633   }
634 };
635 
636 template <typename B, typename S, typename T, unsigned N = 0>
637 class RangeDataVector {
638 public:
639   typedef RangeData<B, S, T> Entry;
640   typedef llvm::SmallVector<Entry, N> Collection;
641 
642   RangeDataVector() = default;
643 
644   ~RangeDataVector() = default;
645 
Append(const Entry & entry)646   void Append(const Entry &entry) { m_entries.push_back(entry); }
647 
Sort()648   void Sort() {
649     if (m_entries.size() > 1)
650       std::stable_sort(m_entries.begin(), m_entries.end());
651   }
652 
653 #ifdef ASSERT_RANGEMAP_ARE_SORTED
IsSorted()654   bool IsSorted() const {
655     typename Collection::const_iterator pos, end, prev;
656     // First we determine if we can combine any of the Entry objects so we
657     // don't end up allocating and making a new collection for no reason
658     for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end;
659          prev = pos++) {
660       if (prev != end && *pos < *prev)
661         return false;
662     }
663     return true;
664   }
665 #endif
666 
CombineConsecutiveEntriesWithEqualData()667   void CombineConsecutiveEntriesWithEqualData() {
668 #ifdef ASSERT_RANGEMAP_ARE_SORTED
669     assert(IsSorted());
670 #endif
671     typename Collection::iterator pos;
672     typename Collection::iterator end;
673     typename Collection::iterator prev;
674     bool can_combine = false;
675     // First we determine if we can combine any of the Entry objects so we
676     // don't end up allocating and making a new collection for no reason
677     for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end;
678          prev = pos++) {
679       if (prev != end && prev->data == pos->data) {
680         can_combine = true;
681         break;
682       }
683     }
684 
685     // We we can combine at least one entry, then we make a new collection and
686     // populate it accordingly, and then swap it into place.
687     if (can_combine) {
688       Collection minimal_ranges;
689       for (pos = m_entries.begin(), end = m_entries.end(), prev = end;
690            pos != end; prev = pos++) {
691         if (prev != end && prev->data == pos->data)
692           minimal_ranges.back().SetRangeEnd(pos->GetRangeEnd());
693         else
694           minimal_ranges.push_back(*pos);
695       }
696       // Use the swap technique in case our new vector is much smaller. We must
697       // swap when using the STL because std::vector objects never release or
698       // reduce the memory once it has been allocated/reserved.
699       m_entries.swap(minimal_ranges);
700     }
701   }
702 
Clear()703   void Clear() { m_entries.clear(); }
704 
IsEmpty()705   bool IsEmpty() const { return m_entries.empty(); }
706 
GetSize()707   size_t GetSize() const { return m_entries.size(); }
708 
GetEntryAtIndex(size_t i)709   const Entry *GetEntryAtIndex(size_t i) const {
710     return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
711   }
712 
GetMutableEntryAtIndex(size_t i)713   Entry *GetMutableEntryAtIndex(size_t i) {
714     return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
715   }
716 
717   // Clients must ensure that "i" is a valid index prior to calling this
718   // function
GetEntryRef(size_t i)719   const Entry &GetEntryRef(size_t i) const { return m_entries[i]; }
720 
BaseLessThan(const Entry & lhs,const Entry & rhs)721   static bool BaseLessThan(const Entry &lhs, const Entry &rhs) {
722     return lhs.GetRangeBase() < rhs.GetRangeBase();
723   }
724 
FindEntryIndexThatContains(B addr)725   uint32_t FindEntryIndexThatContains(B addr) const {
726     const Entry *entry = FindEntryThatContains(addr);
727     if (entry)
728       return std::distance(m_entries.begin(), entry);
729     return UINT32_MAX;
730   }
731 
FindEntryIndexesThatContain(B addr,std::vector<uint32_t> & indexes)732   uint32_t FindEntryIndexesThatContain(B addr,
733                                        std::vector<uint32_t> &indexes) const {
734 #ifdef ASSERT_RANGEMAP_ARE_SORTED
735     assert(IsSorted());
736 #endif
737 
738     if (!m_entries.empty()) {
739       for (const auto &entry : m_entries) {
740         if (entry.Contains(addr))
741           indexes.push_back(entry.data);
742       }
743     }
744     return indexes.size();
745   }
746 
FindEntryThatContains(B addr)747   Entry *FindEntryThatContains(B addr) {
748     return const_cast<Entry *>(
749         static_cast<const RangeDataVector *>(this)->FindEntryThatContains(
750             addr));
751   }
752 
FindEntryThatContains(B addr)753   const Entry *FindEntryThatContains(B addr) const {
754     return FindEntryThatContains(Entry(addr, 1));
755   }
756 
FindEntryThatContains(const Entry & range)757   const Entry *FindEntryThatContains(const Entry &range) const {
758 #ifdef ASSERT_RANGEMAP_ARE_SORTED
759     assert(IsSorted());
760 #endif
761     if (!m_entries.empty()) {
762       typename Collection::const_iterator begin = m_entries.begin();
763       typename Collection::const_iterator end = m_entries.end();
764       typename Collection::const_iterator pos =
765           std::lower_bound(begin, end, range, BaseLessThan);
766 
767       while (pos != begin && pos[-1].Contains(range))
768         --pos;
769 
770       if (pos != end && pos->Contains(range))
771         return &(*pos);
772     }
773     return nullptr;
774   }
775 
FindEntryStartsAt(B addr)776   const Entry *FindEntryStartsAt(B addr) const {
777 #ifdef ASSERT_RANGEMAP_ARE_SORTED
778     assert(IsSorted());
779 #endif
780     if (!m_entries.empty()) {
781       auto begin = m_entries.begin(), end = m_entries.end();
782       auto pos = std::lower_bound(begin, end, Entry(addr, 1), BaseLessThan);
783       if (pos != end && pos->base == addr)
784         return &(*pos);
785     }
786     return nullptr;
787   }
788 
789   // This method will return the entry that contains the given address, or the
790   // entry following that address.  If you give it an address of 0 and the
791   // first entry starts at address 0x100, you will get the entry at 0x100.
792   //
793   // For most uses, FindEntryThatContains is the correct one to use, this is a
794   // less commonly needed behavior.  It was added for core file memory regions,
795   // where we want to present a gap in the memory regions as a distinct region,
796   // so we need to know the start address of the next memory section that
797   // exists.
FindEntryThatContainsOrFollows(B addr)798   const Entry *FindEntryThatContainsOrFollows(B addr) const {
799 #ifdef ASSERT_RANGEMAP_ARE_SORTED
800     assert(IsSorted());
801 #endif
802     if (!m_entries.empty()) {
803       typename Collection::const_iterator begin = m_entries.begin();
804       typename Collection::const_iterator end = m_entries.end();
805       typename Collection::const_iterator pos =
806           std::lower_bound(m_entries.begin(), end, addr,
807                            [](const Entry &lhs, B rhs_base) -> bool {
808                              return lhs.GetRangeEnd() <= rhs_base;
809                            });
810 
811       while (pos != begin && pos[-1].Contains(addr))
812         --pos;
813 
814       if (pos != end)
815         return &(*pos);
816     }
817     return nullptr;
818   }
819 
Back()820   Entry *Back() { return (m_entries.empty() ? nullptr : &m_entries.back()); }
821 
Back()822   const Entry *Back() const {
823     return (m_entries.empty() ? nullptr : &m_entries.back());
824   }
825 
826 protected:
827   Collection m_entries;
828 };
829 
830 //----------------------------------------------------------------------
831 // A simple range  with data class where you get to define the type of
832 // the range base "B", the type used for the range byte size "S", and the type
833 // for the associated data "T".
834 //----------------------------------------------------------------------
835 template <typename B, typename T> struct AddressData {
836   typedef B BaseType;
837   typedef T DataType;
838 
839   BaseType addr;
840   DataType data;
841 
AddressDataAddressData842   AddressData() : addr(), data() {}
843 
AddressDataAddressData844   AddressData(B a, DataType d) : addr(a), data(d) {}
845 
846   bool operator<(const AddressData &rhs) const {
847     if (this->addr == rhs.addr)
848       return this->data < rhs.data;
849     return this->addr < rhs.addr;
850   }
851 
852   bool operator==(const AddressData &rhs) const {
853     return this->addr == rhs.addr && this->data == rhs.data;
854   }
855 
856   bool operator!=(const AddressData &rhs) const {
857     return this->addr != rhs.addr || this->data == rhs.data;
858   }
859 };
860 
861 template <typename B, typename T, unsigned N> class AddressDataArray {
862 public:
863   typedef AddressData<B, T> Entry;
864   typedef llvm::SmallVector<Entry, N> Collection;
865 
866   AddressDataArray() = default;
867 
868   ~AddressDataArray() = default;
869 
Append(const Entry & entry)870   void Append(const Entry &entry) { m_entries.push_back(entry); }
871 
Sort()872   void Sort() {
873     if (m_entries.size() > 1)
874       std::stable_sort(m_entries.begin(), m_entries.end());
875   }
876 
877 #ifdef ASSERT_RANGEMAP_ARE_SORTED
IsSorted()878   bool IsSorted() const {
879     typename Collection::const_iterator pos, end, prev;
880     // First we determine if we can combine any of the Entry objects so we
881     // don't end up allocating and making a new collection for no reason
882     for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end;
883          prev = pos++) {
884       if (prev != end && *pos < *prev)
885         return false;
886     }
887     return true;
888   }
889 #endif
890 
Clear()891   void Clear() { m_entries.clear(); }
892 
IsEmpty()893   bool IsEmpty() const { return m_entries.empty(); }
894 
GetSize()895   size_t GetSize() const { return m_entries.size(); }
896 
GetEntryAtIndex(size_t i)897   const Entry *GetEntryAtIndex(size_t i) const {
898     return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
899   }
900 
901   // Clients must ensure that "i" is a valid index prior to calling this
902   // function
GetEntryRef(size_t i)903   const Entry &GetEntryRef(size_t i) const { return m_entries[i]; }
904 
BaseLessThan(const Entry & lhs,const Entry & rhs)905   static bool BaseLessThan(const Entry &lhs, const Entry &rhs) {
906     return lhs.addr < rhs.addr;
907   }
908 
FindEntry(B addr,bool exact_match_only)909   Entry *FindEntry(B addr, bool exact_match_only) {
910 #ifdef ASSERT_RANGEMAP_ARE_SORTED
911     assert(IsSorted());
912 #endif
913     if (!m_entries.empty()) {
914       Entry entry;
915       entry.addr = addr;
916       typename Collection::iterator begin = m_entries.begin();
917       typename Collection::iterator end = m_entries.end();
918       typename Collection::iterator pos =
919           std::lower_bound(begin, end, entry, BaseLessThan);
920 
921       while (pos != begin && pos[-1].addr == addr)
922         --pos;
923 
924       if (pos != end) {
925         if (pos->addr == addr || !exact_match_only)
926           return &(*pos);
927       }
928     }
929     return nullptr;
930   }
931 
FindNextEntry(const Entry * entry)932   const Entry *FindNextEntry(const Entry *entry) {
933     if (entry >= &*m_entries.begin() && entry + 1 < &*m_entries.end())
934       return entry + 1;
935     return nullptr;
936   }
937 
Back()938   Entry *Back() { return (m_entries.empty() ? nullptr : &m_entries.back()); }
939 
Back()940   const Entry *Back() const {
941     return (m_entries.empty() ? nullptr : &m_entries.back());
942   }
943 
944 protected:
945   Collection m_entries;
946 };
947 
948 } // namespace lldb_private
949 
950 #endif // liblldb_RangeMap_h_
951