LLDB  mainline
RangeMap.h
Go to the documentation of this file.
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 
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  Range Intersect(const Range &rhs) const {
63  const BaseType lhs_base = this->GetRangeBase();
64  const BaseType rhs_base = rhs.GetRangeBase();
65  const BaseType lhs_end = this->GetRangeEnd();
66  const BaseType rhs_end = rhs.GetRangeEnd();
67  Range range;
68  range.SetRangeBase(std::max(lhs_base, rhs_base));
69  range.SetRangeEnd(std::min(lhs_end, rhs_end));
70  return range;
71  }
72 
73  BaseType GetRangeEnd() const { return base + size; }
74 
75  void SetRangeEnd(BaseType end) {
76  if (end > base)
77  size = end - base;
78  else
79  size = 0;
80  }
81 
82  SizeType GetByteSize() const { return size; }
83 
84  void SetByteSize(SizeType s) { size = s; }
85 
86  bool IsValid() const { return size > 0; }
87 
88  bool Contains(BaseType r) const {
89  return (GetRangeBase() <= r) && (r < GetRangeEnd());
90  }
91 
93  return (GetRangeBase() <= r) && (r <= GetRangeEnd());
94  }
95 
96  bool Contains(const Range &range) const {
97  return Contains(range.GetRangeBase()) &&
98  ContainsEndInclusive(range.GetRangeEnd());
99  }
100 
101  // Returns true if the two ranges adjoing or intersect
102  bool DoesAdjoinOrIntersect(const Range &rhs) const {
103  const BaseType lhs_base = this->GetRangeBase();
104  const BaseType rhs_base = rhs.GetRangeBase();
105  const BaseType lhs_end = this->GetRangeEnd();
106  const BaseType rhs_end = rhs.GetRangeEnd();
107  bool result = (lhs_base <= rhs_end) && (lhs_end >= rhs_base);
108  return result;
109  }
110 
111  // Returns true if the two ranges intersect
112  bool DoesIntersect(const Range &rhs) const {
113  return Intersect(rhs).IsValid();
114  }
115 
116  bool operator<(const Range &rhs) const {
117  if (base == rhs.base)
118  return size < rhs.size;
119  return base < rhs.base;
120  }
121 
122  bool operator==(const Range &rhs) const {
123  return base == rhs.base && size == rhs.size;
124  }
125 
126  bool operator!=(const Range &rhs) const {
127  return base != rhs.base || size != rhs.size;
128  }
129 };
130 
131 template <typename B, typename S, unsigned N = 0> class RangeVector {
132 public:
133  typedef B BaseType;
134  typedef S SizeType;
136  typedef llvm::SmallVector<Entry, N> Collection;
137 
138  RangeVector() = default;
139 
140  ~RangeVector() = default;
141 
142  static RangeVector GetOverlaps(const RangeVector &vec1,
143  const RangeVector &vec2) {
144 #ifdef ASSERT_RANGEMAP_ARE_SORTED
145  assert(vec1.IsSorted() && vec2.IsSorted());
146 #endif
147  RangeVector result;
148  auto pos1 = vec1.begin();
149  auto end1 = vec1.end();
150  auto pos2 = vec2.begin();
151  auto end2 = vec2.end();
152  while (pos1 != end1 && pos2 != end2) {
153  Entry entry = pos1->Intersect(*pos2);
154  if (entry.IsValid())
155  result.Append(entry);
156  if (pos1->GetRangeEnd() < pos2->GetRangeEnd())
157  ++pos1;
158  else
159  ++pos2;
160  }
161  return result;
162  }
163 
164  bool operator==(const RangeVector &rhs) const {
165  if (GetSize() != rhs.GetSize())
166  return false;
167  for (size_t i = 0; i < GetSize(); ++i) {
168  if (GetEntryRef(i) != rhs.GetEntryRef(i))
169  return false;
170  }
171  return true;
172  }
173 
174  void Append(const Entry &entry) { m_entries.push_back(entry); }
175 
176  void Append(B base, S size) { m_entries.emplace_back(base, size); }
177 
178  // Insert an item into a sorted list and optionally combine it with any
179  // adjacent blocks if requested.
180  void Insert(const Entry &entry, bool combine) {
181  if (m_entries.empty()) {
182  m_entries.push_back(entry);
183  return;
184  }
185  auto begin = m_entries.begin();
186  auto end = m_entries.end();
187  auto pos = std::lower_bound(begin, end, entry);
188  if (combine) {
189  if (pos != end && pos->Union(entry)) {
190  CombinePrevAndNext(pos);
191  return;
192  }
193  if (pos != begin) {
194  auto prev = pos - 1;
195  if (prev->Union(entry)) {
196  CombinePrevAndNext(prev);
197  return;
198  }
199  }
200  }
201  m_entries.insert(pos, entry);
202  }
203 
205  if (idx < m_entries.size()) {
206  m_entries.erase(m_entries.begin() + idx);
207  return true;
208  }
209  return false;
210  }
211 
212  void Sort() {
213  if (m_entries.size() > 1)
214  std::stable_sort(m_entries.begin(), m_entries.end());
215  }
216 
217 #ifdef ASSERT_RANGEMAP_ARE_SORTED
218  bool IsSorted() const {
219  typename Collection::const_iterator pos, end, prev;
220  // First we determine if we can combine any of the Entry objects so we
221  // don't end up allocating and making a new collection for no reason
222  for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end;
223  prev = pos++) {
224  if (prev != end && *pos < *prev)
225  return false;
226  }
227  return true;
228  }
229 #endif
230 
232 #ifdef ASSERT_RANGEMAP_ARE_SORTED
233  assert(IsSorted());
234 #endif
235  auto first_intersect = std::adjacent_find(
236  m_entries.begin(), m_entries.end(), [](const Entry &a, const Entry &b) {
237  return a.DoesAdjoinOrIntersect(b);
238  });
239  if (first_intersect == m_entries.end())
240  return;
241 
242  // We we can combine at least one entry, then we make a new collection and
243  // populate it accordingly, and then swap it into place.
244  auto pos = std::next(first_intersect);
245  Collection minimal_ranges(m_entries.begin(), pos);
246  for (; pos != m_entries.end(); ++pos) {
247  Entry &back = minimal_ranges.back();
248  if (back.DoesAdjoinOrIntersect(*pos))
249  back.SetRangeEnd(std::max(back.GetRangeEnd(), pos->GetRangeEnd()));
250  else
251  minimal_ranges.push_back(*pos);
252  }
253  m_entries.swap(minimal_ranges);
254  }
255 
256  BaseType GetMinRangeBase(BaseType fail_value) const {
257 #ifdef ASSERT_RANGEMAP_ARE_SORTED
258  assert(IsSorted());
259 #endif
260  if (m_entries.empty())
261  return fail_value;
262  // m_entries must be sorted, so if we aren't empty, we grab the first
263  // range's base
264  return m_entries.front().GetRangeBase();
265  }
266 
267  BaseType GetMaxRangeEnd(BaseType fail_value) const {
268 #ifdef ASSERT_RANGEMAP_ARE_SORTED
269  assert(IsSorted());
270 #endif
271  if (m_entries.empty())
272  return fail_value;
273  // m_entries must be sorted, so if we aren't empty, we grab the last
274  // range's end
275  return m_entries.back().GetRangeEnd();
276  }
277 
278  void Slide(BaseType slide) {
279  typename Collection::iterator pos, end;
280  for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos)
281  pos->Slide(slide);
282  }
283 
284  void Clear() { m_entries.clear(); }
285 
286  void Reserve(typename Collection::size_type size) { m_entries.reserve(size); }
287 
288  bool IsEmpty() const { return m_entries.empty(); }
289 
290  size_t GetSize() const { return m_entries.size(); }
291 
292  const Entry *GetEntryAtIndex(size_t i) const {
293  return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
294  }
295 
296  // Clients must ensure that "i" is a valid index prior to calling this
297  // function
298  Entry &GetEntryRef(size_t i) { return m_entries[i]; }
299  const Entry &GetEntryRef(size_t i) const { return m_entries[i]; }
300 
301  Entry *Back() { return (m_entries.empty() ? nullptr : &m_entries.back()); }
302 
303  const Entry *Back() const {
304  return (m_entries.empty() ? nullptr : &m_entries.back());
305  }
306 
307  static bool BaseLessThan(const Entry &lhs, const Entry &rhs) {
308  return lhs.GetRangeBase() < rhs.GetRangeBase();
309  }
310 
312 #ifdef ASSERT_RANGEMAP_ARE_SORTED
313  assert(IsSorted());
314 #endif
315  if (!m_entries.empty()) {
316  Entry entry(addr, 1);
317  typename Collection::const_iterator begin = m_entries.begin();
318  typename Collection::const_iterator end = m_entries.end();
319  typename Collection::const_iterator pos =
320  std::lower_bound(begin, end, entry, BaseLessThan);
321 
322  if (pos != end && pos->Contains(addr)) {
323  return std::distance(begin, pos);
324  } else if (pos != begin) {
325  --pos;
326  if (pos->Contains(addr))
327  return std::distance(begin, pos);
328  }
329  }
330  return UINT32_MAX;
331  }
332 
333  const Entry *FindEntryThatContains(B addr) const {
334 #ifdef ASSERT_RANGEMAP_ARE_SORTED
335  assert(IsSorted());
336 #endif
337  if (!m_entries.empty()) {
338  Entry entry(addr, 1);
339  typename Collection::const_iterator begin = m_entries.begin();
340  typename Collection::const_iterator end = m_entries.end();
341  typename Collection::const_iterator pos =
342  std::lower_bound(begin, end, entry, BaseLessThan);
343 
344  if (pos != end && pos->Contains(addr)) {
345  return &(*pos);
346  } else if (pos != begin) {
347  --pos;
348  if (pos->Contains(addr)) {
349  return &(*pos);
350  }
351  }
352  }
353  return nullptr;
354  }
355 
356  const Entry *FindEntryThatContains(const Entry &range) const {
357 #ifdef ASSERT_RANGEMAP_ARE_SORTED
358  assert(IsSorted());
359 #endif
360  if (!m_entries.empty()) {
361  typename Collection::const_iterator begin = m_entries.begin();
362  typename Collection::const_iterator end = m_entries.end();
363  typename Collection::const_iterator pos =
364  std::lower_bound(begin, end, range, BaseLessThan);
365 
366  if (pos != end && pos->Contains(range)) {
367  return &(*pos);
368  } else if (pos != begin) {
369  --pos;
370  if (pos->Contains(range)) {
371  return &(*pos);
372  }
373  }
374  }
375  return nullptr;
376  }
377 
378  using const_iterator = typename Collection::const_iterator;
379  const_iterator begin() const { return m_entries.begin(); }
380  const_iterator end() const { return m_entries.end(); }
381 
382 protected:
383  void CombinePrevAndNext(typename Collection::iterator pos) {
384  // Check if the prev or next entries in case they need to be unioned with
385  // the entry pointed to by "pos".
386  if (pos != m_entries.begin()) {
387  auto prev = pos - 1;
388  if (prev->Union(*pos))
389  m_entries.erase(pos);
390  pos = prev;
391  }
392 
393  auto end = m_entries.end();
394  if (pos != end) {
395  auto next = pos + 1;
396  if (next != end) {
397  if (pos->Union(*next))
398  m_entries.erase(next);
399  }
400  }
401  }
402 
404 };
405 
406 // A simple range with data class where you get to define the type of
407 // the range base "B", the type used for the range byte size "S", and the type
408 // for the associated data "T".
409 template <typename B, typename S, typename T>
410 struct RangeData : public Range<B, S> {
411  typedef T DataType;
412 
414 
415  RangeData() : Range<B, S>(), data() {}
416 
417  RangeData(B base, S size) : Range<B, S>(base, size), data() {}
418 
419  RangeData(B base, S size, DataType d) : Range<B, S>(base, size), data(d) {}
420 };
421 
422 // We can treat the vector as a flattened Binary Search Tree, augmenting it
423 // with upper bounds (max of range endpoints) for every index allows us to
424 // query for range containment quicker.
425 template <typename B, typename S, typename T>
426 struct AugmentedRangeData : public RangeData<B, S, T> {
428 
430  : RangeData<B, S, T>(rd), upper_bound() {}
431 };
432 
433 template <typename B, typename S, typename T, unsigned N = 0,
434  class Compare = std::less<T>>
436 public:
440  typedef llvm::SmallVector<AugmentedEntry, N> Collection;
441 
442  RangeDataVector(Compare compare = Compare()) : m_compare(compare) {}
443 
444  ~RangeDataVector() = default;
445 
446  void Append(const Entry &entry) { m_entries.emplace_back(entry); }
447 
448  void Sort() {
449  if (m_entries.size() > 1)
450  std::stable_sort(m_entries.begin(), m_entries.end(),
451  [&compare = m_compare](const Entry &a, const Entry &b) {
452  if (a.base != b.base)
453  return a.base < b.base;
454  if (a.size != b.size)
455  return a.size < b.size;
456  return compare(a.data, b.data);
457  });
458  if (!m_entries.empty())
459  ComputeUpperBounds(0, m_entries.size());
460  }
461 
462 #ifdef ASSERT_RANGEMAP_ARE_SORTED
463  bool IsSorted() const {
464  typename Collection::const_iterator pos, end, prev;
465  for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end;
466  prev = pos++) {
467  if (prev != end && *pos < *prev)
468  return false;
469  }
470  return true;
471  }
472 #endif
473 
475 #ifdef ASSERT_RANGEMAP_ARE_SORTED
476  assert(IsSorted());
477 #endif
478  typename Collection::iterator pos;
479  typename Collection::iterator end;
480  typename Collection::iterator prev;
481  bool can_combine = false;
482  // First we determine if we can combine any of the Entry objects so we
483  // don't end up allocating and making a new collection for no reason
484  for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end;
485  prev = pos++) {
486  if (prev != end && prev->data == pos->data) {
487  can_combine = true;
488  break;
489  }
490  }
491 
492  // We we can combine at least one entry, then we make a new collection and
493  // populate it accordingly, and then swap it into place.
494  if (can_combine) {
495  Collection minimal_ranges;
496  for (pos = m_entries.begin(), end = m_entries.end(), prev = end;
497  pos != end; prev = pos++) {
498  if (prev != end && prev->data == pos->data)
499  minimal_ranges.back().SetRangeEnd(pos->GetRangeEnd());
500  else
501  minimal_ranges.push_back(*pos);
502  }
503  // Use the swap technique in case our new vector is much smaller. We must
504  // swap when using the STL because std::vector objects never release or
505  // reduce the memory once it has been allocated/reserved.
506  m_entries.swap(minimal_ranges);
507  }
508  }
509 
510  void Clear() { m_entries.clear(); }
511 
512  bool IsEmpty() const { return m_entries.empty(); }
513 
514  size_t GetSize() const { return m_entries.size(); }
515 
516  const Entry *GetEntryAtIndex(size_t i) const {
517  return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
518  }
519 
521  return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
522  }
523 
524  // Clients must ensure that "i" is a valid index prior to calling this
525  // function
526  Entry &GetEntryRef(size_t i) { return m_entries[i]; }
527  const Entry &GetEntryRef(size_t i) const { return m_entries[i]; }
528 
529  static bool BaseLessThan(const Entry &lhs, const Entry &rhs) {
530  return lhs.GetRangeBase() < rhs.GetRangeBase();
531  }
532 
534  const AugmentedEntry *entry =
535  static_cast<const AugmentedEntry *>(FindEntryThatContains(addr));
536  if (entry)
537  return std::distance(m_entries.begin(), entry);
538  return UINT32_MAX;
539  }
540 
541  uint32_t FindEntryIndexesThatContain(B addr, std::vector<uint32_t> &indexes) {
542 #ifdef ASSERT_RANGEMAP_ARE_SORTED
543  assert(IsSorted());
544 #endif
545  if (!m_entries.empty())
546  FindEntryIndexesThatContain(addr, 0, m_entries.size(), indexes);
547 
548  return indexes.size();
549  }
550 
552  return const_cast<Entry *>(
553  static_cast<const RangeDataVector *>(this)->FindEntryThatContains(
554  addr));
555  }
556 
557  const Entry *FindEntryThatContains(B addr) const {
558  return FindEntryThatContains(Entry(addr, 1));
559  }
560 
561  const Entry *FindEntryThatContains(const Entry &range) const {
562 #ifdef ASSERT_RANGEMAP_ARE_SORTED
563  assert(IsSorted());
564 #endif
565  if (!m_entries.empty()) {
566  typename Collection::const_iterator begin = m_entries.begin();
567  typename Collection::const_iterator end = m_entries.end();
568  typename Collection::const_iterator pos =
569  std::lower_bound(begin, end, range, BaseLessThan);
570 
571  while (pos != begin && pos[-1].Contains(range))
572  --pos;
573 
574  if (pos != end && pos->Contains(range))
575  return &(*pos);
576  }
577  return nullptr;
578  }
579 
580  const Entry *FindEntryStartsAt(B addr) const {
581 #ifdef ASSERT_RANGEMAP_ARE_SORTED
582  assert(IsSorted());
583 #endif
584  if (!m_entries.empty()) {
585  auto begin = m_entries.begin(), end = m_entries.end();
586  auto pos = std::lower_bound(begin, end, Entry(addr, 1), BaseLessThan);
587  if (pos != end && pos->base == addr)
588  return &(*pos);
589  }
590  return nullptr;
591  }
592 
593  // This method will return the entry that contains the given address, or the
594  // entry following that address. If you give it an address of 0 and the
595  // first entry starts at address 0x100, you will get the entry at 0x100.
596  //
597  // For most uses, FindEntryThatContains is the correct one to use, this is a
598  // less commonly needed behavior. It was added for core file memory regions,
599  // where we want to present a gap in the memory regions as a distinct region,
600  // so we need to know the start address of the next memory section that
601  // exists.
602  const Entry *FindEntryThatContainsOrFollows(B addr) const {
603 #ifdef ASSERT_RANGEMAP_ARE_SORTED
604  assert(IsSorted());
605 #endif
606  if (!m_entries.empty()) {
607  typename Collection::const_iterator begin = m_entries.begin();
608  typename Collection::const_iterator end = m_entries.end();
609  typename Collection::const_iterator pos =
610  std::lower_bound(m_entries.begin(), end, addr,
611  [](const Entry &lhs, B rhs_base) -> bool {
612  return lhs.GetRangeEnd() <= rhs_base;
613  });
614 
615  while (pos != begin && pos[-1].Contains(addr))
616  --pos;
617 
618  if (pos != end)
619  return &(*pos);
620  }
621  return nullptr;
622  }
623 
624  Entry *Back() { return (m_entries.empty() ? nullptr : &m_entries.back()); }
625 
626  const Entry *Back() const {
627  return (m_entries.empty() ? nullptr : &m_entries.back());
628  }
629 
630 protected:
633 
634 private:
635  // Compute extra information needed for search
636  B ComputeUpperBounds(size_t lo, size_t hi) {
637  size_t mid = (lo + hi) / 2;
638  AugmentedEntry &entry = m_entries[mid];
639 
640  entry.upper_bound = entry.base + entry.size;
641 
642  if (lo < mid)
643  entry.upper_bound =
644  std::max(entry.upper_bound, ComputeUpperBounds(lo, mid));
645 
646  if (mid + 1 < hi)
647  entry.upper_bound =
648  std::max(entry.upper_bound, ComputeUpperBounds(mid + 1, hi));
649 
650  return entry.upper_bound;
651  }
652 
653  // This is based on the augmented tree implementation found at
654  // https://en.wikipedia.org/wiki/Interval_tree#Augmented_tree
655  void FindEntryIndexesThatContain(B addr, size_t lo, size_t hi,
656  std::vector<uint32_t> &indexes) {
657  size_t mid = (lo + hi) / 2;
658  const AugmentedEntry &entry = m_entries[mid];
659 
660  // addr is greater than the rightmost point of any interval below mid
661  // so there are cannot be any matches.
662  if (addr > entry.upper_bound)
663  return;
664 
665  // Recursively search left subtree
666  if (lo < mid)
667  FindEntryIndexesThatContain(addr, lo, mid, indexes);
668 
669  // If addr is smaller than the start of the current interval it
670  // cannot contain it nor can any of its right subtree.
671  if (addr < entry.base)
672  return;
673 
674  if (entry.Contains(addr))
675  indexes.push_back(entry.data);
676 
677  // Recursively search right subtree
678  if (mid + 1 < hi)
679  FindEntryIndexesThatContain(addr, mid + 1, hi, indexes);
680  }
681 };
682 
683 // A simple range with data class where you get to define the type of
684 // the range base "B", the type used for the range byte size "S", and the type
685 // for the associated data "T".
686 template <typename B, typename T> struct AddressData {
687  typedef B BaseType;
688  typedef T DataType;
689 
692 
693  AddressData() : addr(), data() {}
694 
695  AddressData(B a, DataType d) : addr(a), data(d) {}
696 
697  bool operator<(const AddressData &rhs) const {
698  if (this->addr == rhs.addr)
699  return this->data < rhs.data;
700  return this->addr < rhs.addr;
701  }
702 
703  bool operator==(const AddressData &rhs) const {
704  return this->addr == rhs.addr && this->data == rhs.data;
705  }
706 
707  bool operator!=(const AddressData &rhs) const {
708  return this->addr != rhs.addr || this->data == rhs.data;
709  }
710 };
711 
712 template <typename B, typename T, unsigned N> class AddressDataArray {
713 public:
715  typedef llvm::SmallVector<Entry, N> Collection;
716 
717  AddressDataArray() = default;
718 
719  ~AddressDataArray() = default;
720 
721  void Append(const Entry &entry) { m_entries.push_back(entry); }
722 
723  void Sort() {
724  if (m_entries.size() > 1)
725  std::stable_sort(m_entries.begin(), m_entries.end());
726  }
727 
728 #ifdef ASSERT_RANGEMAP_ARE_SORTED
729  bool IsSorted() const {
730  typename Collection::const_iterator pos, end, prev;
731  // First we determine if we can combine any of the Entry objects so we
732  // don't end up allocating and making a new collection for no reason
733  for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end;
734  prev = pos++) {
735  if (prev != end && *pos < *prev)
736  return false;
737  }
738  return true;
739  }
740 #endif
741 
742  void Clear() { m_entries.clear(); }
743 
744  bool IsEmpty() const { return m_entries.empty(); }
745 
746  size_t GetSize() const { return m_entries.size(); }
747 
748  const Entry *GetEntryAtIndex(size_t i) const {
749  return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
750  }
751 
752  // Clients must ensure that "i" is a valid index prior to calling this
753  // function
754  const Entry &GetEntryRef(size_t i) const { return m_entries[i]; }
755 
756  static bool BaseLessThan(const Entry &lhs, const Entry &rhs) {
757  return lhs.addr < rhs.addr;
758  }
759 
760  Entry *FindEntry(B addr, bool exact_match_only) {
761 #ifdef ASSERT_RANGEMAP_ARE_SORTED
762  assert(IsSorted());
763 #endif
764  if (!m_entries.empty()) {
765  Entry entry;
766  entry.addr = addr;
767  typename Collection::iterator begin = m_entries.begin();
768  typename Collection::iterator end = m_entries.end();
769  typename Collection::iterator pos =
770  std::lower_bound(begin, end, entry, BaseLessThan);
771 
772  while (pos != begin && pos[-1].addr == addr)
773  --pos;
774 
775  if (pos != end) {
776  if (pos->addr == addr || !exact_match_only)
777  return &(*pos);
778  }
779  }
780  return nullptr;
781  }
782 
783  const Entry *FindNextEntry(const Entry *entry) {
784  if (entry >= &*m_entries.begin() && entry + 1 < &*m_entries.end())
785  return entry + 1;
786  return nullptr;
787  }
788 
789  Entry *Back() { return (m_entries.empty() ? nullptr : &m_entries.back()); }
790 
791  const Entry *Back() const {
792  return (m_entries.empty() ? nullptr : &m_entries.back());
793  }
794 
795 protected:
797 };
798 
799 } // namespace lldb_private
800 
801 #endif // LLDB_UTILITY_RANGEMAP_H
lldb_private::RangeDataVector::FindEntryIndexesThatContain
void FindEntryIndexesThatContain(B addr, size_t lo, size_t hi, std::vector< uint32_t > &indexes)
Definition: RangeMap.h:655
lldb_private::RangeDataVector::Range
lldb_private::Range< B, S > Range
Definition: RangeMap.h:437
lldb_private::Range::GetRangeBase
BaseType GetRangeBase() const
Definition: RangeMap.h:46
lldb_private::RangeDataVector::Back
const Entry * Back() const
Definition: RangeMap.h:626
lldb_private::RangeDataVector::FindEntryThatContains
const Entry * FindEntryThatContains(const Entry &range) const
Definition: RangeMap.h:561
lldb_private::Range::SizeType
S SizeType
Definition: RangeMap.h:31
lldb_private::Range::DoesIntersect
bool DoesIntersect(const Range &rhs) const
Definition: RangeMap.h:112
lldb_private::RangeVector::FindEntryIndexThatContains
uint32_t FindEntryIndexThatContains(B addr) const
Definition: RangeMap.h:311
lldb_private::RangeVector::SizeType
S SizeType
Definition: RangeMap.h:134
lldb_private::AugmentedRangeData
Definition: RangeMap.h:426
lldb_private::RangeDataVector::GetEntryRef
Entry & GetEntryRef(size_t i)
Definition: RangeMap.h:526
lldb_private::AddressDataArray::~AddressDataArray
~AddressDataArray()=default
lldb_private::RangeVector::Sort
void Sort()
Definition: RangeMap.h:212
lldb_private::RangeVector::GetOverlaps
static RangeVector GetOverlaps(const RangeVector &vec1, const RangeVector &vec2)
Definition: RangeMap.h:142
lldb_private::RangeVector::GetEntryRef
const Entry & GetEntryRef(size_t i) const
Definition: RangeMap.h:299
lldb_private::RangeVector::Back
Entry * Back()
Definition: RangeMap.h:301
lldb_private::Range::Range
Range()
Definition: RangeMap.h:36
lldb_private::AddressData::addr
BaseType addr
Definition: RangeMap.h:690
lldb_private::AddressDataArray::Entry
AddressData< B, T > Entry
Definition: RangeMap.h:714
lldb_private::RangeVector::Collection
llvm::SmallVector< Entry, N > Collection
Definition: RangeMap.h:136
lldb_private::RangeVector::RangeVector
RangeVector()=default
lldb_private::AddressDataArray::Back
const Entry * Back() const
Definition: RangeMap.h:791
lldb_private::RangeVector< uint32_t, uint32_t >::const_iterator
typename Collection::const_iterator const_iterator
Definition: RangeMap.h:378
lldb_private::RangeVector::~RangeVector
~RangeVector()=default
lldb_private::Range::operator==
bool operator==(const Range &rhs) const
Definition: RangeMap.h:122
lldb_private::RangeVector::GetMinRangeBase
BaseType GetMinRangeBase(BaseType fail_value) const
Definition: RangeMap.h:256
lldb_private::RangeVector::GetEntryRef
Entry & GetEntryRef(size_t i)
Definition: RangeMap.h:298
lldb_private::AddressDataArray::Collection
llvm::SmallVector< Entry, N > Collection
Definition: RangeMap.h:715
lldb_private::RangeDataVector::Sort
void Sort()
Definition: RangeMap.h:448
lldb_private::AugmentedRangeData::AugmentedRangeData
AugmentedRangeData(const RangeData< B, S, T > &rd)
Definition: RangeMap.h:429
lldb_private::AddressData::AddressData
AddressData()
Definition: RangeMap.h:693
lldb_private::RangeDataVector::Clear
void Clear()
Definition: RangeMap.h:510
lldb_private::RangeDataVector::GetEntryAtIndex
const Entry * GetEntryAtIndex(size_t i) const
Definition: RangeMap.h:516
lldb_private::Range::BaseType
B BaseType
Definition: RangeMap.h:30
lldb_private::Range::size
SizeType size
Definition: RangeMap.h:34
lldb_private::RangeData
Definition: RangeMap.h:410
lldb_private::Range::Range
Range(BaseType b, SizeType s)
Definition: RangeMap.h:38
lldb_private::RangeVector::Clear
void Clear()
Definition: RangeMap.h:284
lldb_private::RangeVector::Reserve
void Reserve(typename Collection::size_type size)
Definition: RangeMap.h:286
lldb_private::AddressDataArray::BaseLessThan
static bool BaseLessThan(const Entry &lhs, const Entry &rhs)
Definition: RangeMap.h:756
lldb_private::RangeVector::CombineConsecutiveRanges
void CombineConsecutiveRanges()
Definition: RangeMap.h:231
lldb_private::RangeVector::Append
void Append(const Entry &entry)
Definition: RangeMap.h:174
lldb_private::AddressDataArray::Back
Entry * Back()
Definition: RangeMap.h:789
lldb_private::RangeDataVector::Entry
RangeData< B, S, T > Entry
Definition: RangeMap.h:438
lldb_private::Range::operator<
bool operator<(const Range &rhs) const
Definition: RangeMap.h:116
lldb_private::AddressData::operator==
bool operator==(const AddressData &rhs) const
Definition: RangeMap.h:703
lldb_private::RangeData::RangeData
RangeData(B base, S size)
Definition: RangeMap.h:417
lldb_private::RangeDataVector::FindEntryThatContains
Entry * FindEntryThatContains(B addr)
Definition: RangeMap.h:551
lldb_private::Range::SetRangeEnd
void SetRangeEnd(BaseType end)
Definition: RangeMap.h:75
lldb_private::RangeVector::Back
const Entry * Back() const
Definition: RangeMap.h:303
lldb_private::RangeDataVector::Append
void Append(const Entry &entry)
Definition: RangeMap.h:446
lldb_private::RangeDataVector::FindEntryIndexesThatContain
uint32_t FindEntryIndexesThatContain(B addr, std::vector< uint32_t > &indexes)
Definition: RangeMap.h:541
lldb_private::RangeVector::begin
const_iterator begin() const
Definition: RangeMap.h:379
lldb_private::Range::IsValid
bool IsValid() const
Definition: RangeMap.h:86
lldb_private::Range::ContainsEndInclusive
bool ContainsEndInclusive(BaseType r) const
Definition: RangeMap.h:92
lldb_private::AddressData::BaseType
B BaseType
Definition: RangeMap.h:687
lldb_private::Range::operator!=
bool operator!=(const Range &rhs) const
Definition: RangeMap.h:126
lldb_private::AddressData::DataType
T DataType
Definition: RangeMap.h:688
Compare
static bool Compare(BreakpointLocationSP lhs, lldb::break_id_t val)
Definition: BreakpointLocationList.cpp:63
lldb_private::AddressDataArray::FindNextEntry
const Entry * FindNextEntry(const Entry *entry)
Definition: RangeMap.h:783
lldb_private::AugmentedRangeData::upper_bound
B upper_bound
Definition: RangeMap.h:427
lldb_private::RangeDataVector::m_compare
Compare m_compare
Definition: RangeMap.h:632
lldb_private::RangeVector::Slide
void Slide(BaseType slide)
Definition: RangeMap.h:278
lldb_private::AddressDataArray::Append
void Append(const Entry &entry)
Definition: RangeMap.h:721
lldb_private::RangeVector::FindEntryThatContains
const Entry * FindEntryThatContains(const Entry &range) const
Definition: RangeMap.h:356
lldb_private::AddressDataArray
Definition: RangeMap.h:712
lldb_private::AddressData
Definition: RangeMap.h:686
lldb_private::RangeVector::m_entries
Collection m_entries
Definition: RangeMap.h:403
lldb_private::AddressDataArray::Clear
void Clear()
Definition: RangeMap.h:742
lldb_private::Range
Definition: Process.h:61
lldb_private::RangeDataVector::RangeDataVector
RangeDataVector(Compare compare=Compare())
Definition: RangeMap.h:442
lldb_private::Range::Slide
void Slide(BaseType slide)
Definition: RangeMap.h:50
lldb_private::RangeVector::Insert
void Insert(const Entry &entry, bool combine)
Definition: RangeMap.h:180
lldb_private::RangeVector::operator==
bool operator==(const RangeVector &rhs) const
Definition: RangeMap.h:164
lldb_private::RangeVector::GetMaxRangeEnd
BaseType GetMaxRangeEnd(BaseType fail_value) const
Definition: RangeMap.h:267
lldb_private::RangeVector::IsEmpty
bool IsEmpty() const
Definition: RangeMap.h:288
lldb_private::RangeVector::CombinePrevAndNext
void CombinePrevAndNext(typename Collection::iterator pos)
Definition: RangeMap.h:383
lldb_private::RangeVector
Definition: RangeMap.h:131
lldb_private::RangeDataVector::FindEntryIndexThatContains
uint32_t FindEntryIndexThatContains(B addr) const
Definition: RangeMap.h:533
lldb-private.h
lldb_private::RangeDataVector::FindEntryStartsAt
const Entry * FindEntryStartsAt(B addr) const
Definition: RangeMap.h:580
lldb_private::AddressData::data
DataType data
Definition: RangeMap.h:691
lldb_private::RangeDataVector::m_entries
Collection m_entries
Definition: RangeMap.h:631
lldb_private::RangeDataVector::Back
Entry * Back()
Definition: RangeMap.h:624
lldb_private::AddressDataArray::GetEntryRef
const Entry & GetEntryRef(size_t i) const
Definition: RangeMap.h:754
lldb_private::Range::DoesAdjoinOrIntersect
bool DoesAdjoinOrIntersect(const Range &rhs) const
Definition: RangeMap.h:102
lldb_private::RangeVector::Entry
Range< B, S > Entry
Definition: RangeMap.h:135
lldb_private::Range::Intersect
Range Intersect(const Range &rhs) const
Definition: RangeMap.h:62
uint32_t
lldb_private::RangeVector::RemoveEntryAtIndex
bool RemoveEntryAtIndex(uint32_t idx)
Definition: RangeMap.h:204
lldb_private::RangeVector::BaseType
B BaseType
Definition: RangeMap.h:133
lldb_private::RangeDataVector::GetSize
size_t GetSize() const
Definition: RangeMap.h:514
lldb_private::RangeDataVector::Collection
llvm::SmallVector< AugmentedEntry, N > Collection
Definition: RangeMap.h:440
lldb_private::AddressDataArray::GetSize
size_t GetSize() const
Definition: RangeMap.h:746
lldb_private::NameMatch::Contains
@ Contains
lldb_private::RangeDataVector
Definition: RangeMap.h:435
lldb_private::RangeDataVector::IsEmpty
bool IsEmpty() const
Definition: RangeMap.h:512
lldb_private::RangeVector::Append
void Append(B base, S size)
Definition: RangeMap.h:176
lldb_private::RangeData::RangeData
RangeData(B base, S size, DataType d)
Definition: RangeMap.h:419
lldb_private::Range::SetRangeBase
void SetRangeBase(BaseType b)
Definition: RangeMap.h:48
lldb_private::Range::GetByteSize
SizeType GetByteSize() const
Definition: RangeMap.h:82
UINT32_MAX
#define UINT32_MAX
Definition: lldb-defines.h:19
lldb_private::Range::SetByteSize
void SetByteSize(SizeType s)
Definition: RangeMap.h:84
lldb_private::RangeData::DataType
T DataType
Definition: RangeMap.h:411
lldb_private::AddressDataArray::FindEntry
Entry * FindEntry(B addr, bool exact_match_only)
Definition: RangeMap.h:760
lldb_private::AddressDataArray::Sort
void Sort()
Definition: RangeMap.h:723
lldb_private::Range::Contains
bool Contains(const Range &range) const
Definition: RangeMap.h:96
lldb_private::AddressData::AddressData
AddressData(B a, DataType d)
Definition: RangeMap.h:695
lldb_private::RangeDataVector::FindEntryThatContains
const Entry * FindEntryThatContains(B addr) const
Definition: RangeMap.h:557
lldb_private
A class that represents a running process on the host machine.
Definition: SBCommandInterpreterRunOptions.h:16
lldb_private::RangeDataVector::GetMutableEntryAtIndex
Entry * GetMutableEntryAtIndex(size_t i)
Definition: RangeMap.h:520
lldb_private::AddressDataArray::m_entries
Collection m_entries
Definition: RangeMap.h:796
lldb_private::AddressDataArray::GetEntryAtIndex
const Entry * GetEntryAtIndex(size_t i) const
Definition: RangeMap.h:748
lldb_private::RangeVector::BaseLessThan
static bool BaseLessThan(const Entry &lhs, const Entry &rhs)
Definition: RangeMap.h:307
lldb_private::AddressDataArray::AddressDataArray
AddressDataArray()=default
lldb_private::RangeDataVector::GetEntryRef
const Entry & GetEntryRef(size_t i) const
Definition: RangeMap.h:527
lldb_private::RangeVector::FindEntryThatContains
const Entry * FindEntryThatContains(B addr) const
Definition: RangeMap.h:333
lldb_private::RangeDataVector::AugmentedEntry
AugmentedRangeData< B, S, T > AugmentedEntry
Definition: RangeMap.h:439
lldb_private::RangeDataVector::ComputeUpperBounds
B ComputeUpperBounds(size_t lo, size_t hi)
Definition: RangeMap.h:636
lldb_private::RangeDataVector::FindEntryThatContainsOrFollows
const Entry * FindEntryThatContainsOrFollows(B addr) const
Definition: RangeMap.h:602
lldb_private::RangeData::data
DataType data
Definition: RangeMap.h:413
lldb_private::AddressData::operator<
bool operator<(const AddressData &rhs) const
Definition: RangeMap.h:697
lldb_private::RangeData::RangeData
RangeData()
Definition: RangeMap.h:415
lldb_private::RangeDataVector::BaseLessThan
static bool BaseLessThan(const Entry &lhs, const Entry &rhs)
Definition: RangeMap.h:529
lldb_private::RangeVector::end
const_iterator end() const
Definition: RangeMap.h:380
lldb_private::RangeDataVector::CombineConsecutiveEntriesWithEqualData
void CombineConsecutiveEntriesWithEqualData()
Definition: RangeMap.h:474
lldb_private::Range::Contains
bool Contains(BaseType r) const
Definition: RangeMap.h:88
lldb_private::Range::base
BaseType base
Definition: RangeMap.h:33
lldb_private::AddressDataArray::IsEmpty
bool IsEmpty() const
Definition: RangeMap.h:744
lldb_private::Range::Union
bool Union(const Range &rhs)
Definition: RangeMap.h:52
lldb_private::Range::Clear
void Clear(BaseType b=0)
Definition: RangeMap.h:40
lldb_private::RangeVector::GetEntryAtIndex
const Entry * GetEntryAtIndex(size_t i) const
Definition: RangeMap.h:292
lldb_private::RangeDataVector::~RangeDataVector
~RangeDataVector()=default
lldb_private::AddressData::operator!=
bool operator!=(const AddressData &rhs) const
Definition: RangeMap.h:707
lldb_private::RangeVector::GetSize
size_t GetSize() const
Definition: RangeMap.h:290
lldb_private::Range::GetRangeEnd
BaseType GetRangeEnd() const
Definition: RangeMap.h:73