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