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