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 
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;
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 
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 
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 
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;
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 
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 
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 
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  bool operator<(const RangeData &rhs) const {
604  if (this->base == rhs.base) {
605  if (this->size == rhs.size)
606  return this->data < rhs.data;
607  else
608  return this->size < rhs.size;
609  }
610  return this->base < rhs.base;
611  }
612 
613  bool operator==(const RangeData &rhs) const {
614  return this->GetRangeBase() == rhs.GetRangeBase() &&
615  this->GetByteSize() == rhs.GetByteSize() && this->data == rhs.data;
616  }
617 
618  bool operator!=(const RangeData &rhs) const {
619  return this->GetRangeBase() != rhs.GetRangeBase() ||
620  this->GetByteSize() != rhs.GetByteSize() || this->data != rhs.data;
621  }
622 };
623 
624 template <typename B, typename S, typename T, unsigned N = 0>
626 public:
629  typedef llvm::SmallVector<Entry, N> Collection;
630 
631  RangeDataVector() = default;
632 
633  ~RangeDataVector() = default;
634 
635  void Append(const Entry &entry) { m_entries.push_back(entry); }
636 
637  void Sort() {
638  if (m_entries.size() > 1)
639  std::stable_sort(m_entries.begin(), m_entries.end());
640  }
641 
642 #ifdef ASSERT_RANGEMAP_ARE_SORTED
643  bool IsSorted() const {
644  typename Collection::const_iterator pos, end, prev;
645  // First we determine if we can combine any of the Entry objects so we
646  // don't end up allocating and making a new collection for no reason
647  for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end;
648  prev = pos++) {
649  if (prev != end && *pos < *prev)
650  return false;
651  }
652  return true;
653  }
654 #endif
655 
657 #ifdef ASSERT_RANGEMAP_ARE_SORTED
658  assert(IsSorted());
659 #endif
660  typename Collection::iterator pos;
661  typename Collection::iterator end;
662  typename Collection::iterator prev;
663  bool can_combine = false;
664  // First we determine if we can combine any of the Entry objects so we
665  // don't end up allocating and making a new collection for no reason
666  for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end;
667  prev = pos++) {
668  if (prev != end && prev->data == pos->data) {
669  can_combine = true;
670  break;
671  }
672  }
673 
674  // We we can combine at least one entry, then we make a new collection and
675  // populate it accordingly, and then swap it into place.
676  if (can_combine) {
677  Collection minimal_ranges;
678  for (pos = m_entries.begin(), end = m_entries.end(), prev = end;
679  pos != end; prev = pos++) {
680  if (prev != end && prev->data == pos->data)
681  minimal_ranges.back().SetRangeEnd(pos->GetRangeEnd());
682  else
683  minimal_ranges.push_back(*pos);
684  }
685  // Use the swap technique in case our new vector is much smaller. We must
686  // swap when using the STL because std::vector objects never release or
687  // reduce the memory once it has been allocated/reserved.
688  m_entries.swap(minimal_ranges);
689  }
690  }
691 
692  void Clear() { m_entries.clear(); }
693 
694  bool IsEmpty() const { return m_entries.empty(); }
695 
696  size_t GetSize() const { return m_entries.size(); }
697 
698  const Entry *GetEntryAtIndex(size_t i) const {
699  return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
700  }
701 
702  Entry *GetMutableEntryAtIndex(size_t i) {
703  return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
704  }
705 
706  // Clients must ensure that "i" is a valid index prior to calling this
707  // function
708  Entry &GetEntryRef(size_t i) { return m_entries[i]; }
709  const Entry &GetEntryRef(size_t i) const { return m_entries[i]; }
710 
711  static bool BaseLessThan(const Entry &lhs, const Entry &rhs) {
712  return lhs.GetRangeBase() < rhs.GetRangeBase();
713  }
714 
716  const Entry *entry = FindEntryThatContains(addr);
717  if (entry)
718  return std::distance(m_entries.begin(), entry);
719  return UINT32_MAX;
720  }
721 
723  std::vector<uint32_t> &indexes) const {
724 #ifdef ASSERT_RANGEMAP_ARE_SORTED
725  assert(IsSorted());
726 #endif
727 
728  if (!m_entries.empty()) {
729  for (const auto &entry : m_entries) {
730  if (entry.Contains(addr))
731  indexes.push_back(entry.data);
732  }
733  }
734  return indexes.size();
735  }
736 
737  Entry *FindEntryThatContains(B addr) {
738  return const_cast<Entry *>(
739  static_cast<const RangeDataVector *>(this)->FindEntryThatContains(
740  addr));
741  }
742 
743  const Entry *FindEntryThatContains(B addr) const {
744  return FindEntryThatContains(Entry(addr, 1));
745  }
746 
747  const Entry *FindEntryThatContains(const Entry &range) const {
748 #ifdef ASSERT_RANGEMAP_ARE_SORTED
749  assert(IsSorted());
750 #endif
751  if (!m_entries.empty()) {
752  typename Collection::const_iterator begin = m_entries.begin();
753  typename Collection::const_iterator end = m_entries.end();
754  typename Collection::const_iterator pos =
755  std::lower_bound(begin, end, range, BaseLessThan);
756 
757  while (pos != begin && pos[-1].Contains(range))
758  --pos;
759 
760  if (pos != end && pos->Contains(range))
761  return &(*pos);
762  }
763  return nullptr;
764  }
765 
766  const Entry *FindEntryStartsAt(B addr) const {
767 #ifdef ASSERT_RANGEMAP_ARE_SORTED
768  assert(IsSorted());
769 #endif
770  if (!m_entries.empty()) {
771  auto begin = m_entries.begin(), end = m_entries.end();
772  auto pos = std::lower_bound(begin, end, Entry(addr, 1), BaseLessThan);
773  if (pos != end && pos->base == addr)
774  return &(*pos);
775  }
776  return nullptr;
777  }
778 
779  // This method will return the entry that contains the given address, or the
780  // entry following that address. If you give it an address of 0 and the
781  // first entry starts at address 0x100, you will get the entry at 0x100.
782  //
783  // For most uses, FindEntryThatContains is the correct one to use, this is a
784  // less commonly needed behavior. It was added for core file memory regions,
785  // where we want to present a gap in the memory regions as a distinct region,
786  // so we need to know the start address of the next memory section that
787  // exists.
788  const Entry *FindEntryThatContainsOrFollows(B addr) const {
789 #ifdef ASSERT_RANGEMAP_ARE_SORTED
790  assert(IsSorted());
791 #endif
792  if (!m_entries.empty()) {
793  typename Collection::const_iterator begin = m_entries.begin();
794  typename Collection::const_iterator end = m_entries.end();
795  typename Collection::const_iterator pos =
796  std::lower_bound(m_entries.begin(), end, addr,
797  [](const Entry &lhs, B rhs_base) -> bool {
798  return lhs.GetRangeEnd() <= rhs_base;
799  });
800 
801  while (pos != begin && pos[-1].Contains(addr))
802  --pos;
803 
804  if (pos != end)
805  return &(*pos);
806  }
807  return nullptr;
808  }
809 
810  Entry *Back() { return (m_entries.empty() ? nullptr : &m_entries.back()); }
811 
812  const Entry *Back() const {
813  return (m_entries.empty() ? nullptr : &m_entries.back());
814  }
815 
816 protected:
817  Collection m_entries;
818 };
819 
820 // A simple range with data class where you get to define the type of
821 // the range base "B", the type used for the range byte size "S", and the type
822 // for the associated data "T".
823 template <typename B, typename T> struct AddressData {
824  typedef B BaseType;
825  typedef T DataType;
826 
827  BaseType addr;
828  DataType data;
829 
830  AddressData() : addr(), data() {}
831 
832  AddressData(B a, DataType d) : addr(a), data(d) {}
833 
834  bool operator<(const AddressData &rhs) const {
835  if (this->addr == rhs.addr)
836  return this->data < rhs.data;
837  return this->addr < rhs.addr;
838  }
839 
840  bool operator==(const AddressData &rhs) const {
841  return this->addr == rhs.addr && this->data == rhs.data;
842  }
843 
844  bool operator!=(const AddressData &rhs) const {
845  return this->addr != rhs.addr || this->data == rhs.data;
846  }
847 };
848 
849 template <typename B, typename T, unsigned N> class AddressDataArray {
850 public:
852  typedef llvm::SmallVector<Entry, N> Collection;
853 
854  AddressDataArray() = default;
855 
856  ~AddressDataArray() = default;
857 
858  void Append(const Entry &entry) { m_entries.push_back(entry); }
859 
860  void Sort() {
861  if (m_entries.size() > 1)
862  std::stable_sort(m_entries.begin(), m_entries.end());
863  }
864 
865 #ifdef ASSERT_RANGEMAP_ARE_SORTED
866  bool IsSorted() const {
867  typename Collection::const_iterator pos, end, prev;
868  // First we determine if we can combine any of the Entry objects so we
869  // don't end up allocating and making a new collection for no reason
870  for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end;
871  prev = pos++) {
872  if (prev != end && *pos < *prev)
873  return false;
874  }
875  return true;
876  }
877 #endif
878 
879  void Clear() { m_entries.clear(); }
880 
881  bool IsEmpty() const { return m_entries.empty(); }
882 
883  size_t GetSize() const { return m_entries.size(); }
884 
885  const Entry *GetEntryAtIndex(size_t i) const {
886  return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
887  }
888 
889  // Clients must ensure that "i" is a valid index prior to calling this
890  // function
891  const Entry &GetEntryRef(size_t i) const { return m_entries[i]; }
892 
893  static bool BaseLessThan(const Entry &lhs, const Entry &rhs) {
894  return lhs.addr < rhs.addr;
895  }
896 
897  Entry *FindEntry(B addr, bool exact_match_only) {
898 #ifdef ASSERT_RANGEMAP_ARE_SORTED
899  assert(IsSorted());
900 #endif
901  if (!m_entries.empty()) {
902  Entry entry;
903  entry.addr = addr;
904  typename Collection::iterator begin = m_entries.begin();
905  typename Collection::iterator end = m_entries.end();
906  typename Collection::iterator pos =
907  std::lower_bound(begin, end, entry, BaseLessThan);
908 
909  while (pos != begin && pos[-1].addr == addr)
910  --pos;
911 
912  if (pos != end) {
913  if (pos->addr == addr || !exact_match_only)
914  return &(*pos);
915  }
916  }
917  return nullptr;
918  }
919 
920  const Entry *FindNextEntry(const Entry *entry) {
921  if (entry >= &*m_entries.begin() && entry + 1 < &*m_entries.end())
922  return entry + 1;
923  return nullptr;
924  }
925 
926  Entry *Back() { return (m_entries.empty() ? nullptr : &m_entries.back()); }
927 
928  const Entry *Back() const {
929  return (m_entries.empty() ? nullptr : &m_entries.back());
930  }
931 
932 protected:
933  Collection m_entries;
934 };
935 
936 } // namespace lldb_private
937 
938 #endif // LLDB_UTILITY_RANGEMAP_H
const Entry * FindEntryThatContains(const Entry &range) const
Definition: RangeMap.h:747
Entry & GetEntryRef(size_t i)
Definition: RangeMap.h:708
void Clear(BaseType b=0)
Definition: RangeMap.h:40
const Entry * GetEntryAtIndex(size_t i) const
Definition: RangeMap.h:698
llvm::SmallVector< Entry, N > Collection
Definition: RangeMap.h:629
const Entry * FindEntryThatContains(const Entry &range) const
Definition: RangeMap.h:541
Enumerations for broadcasting.
Definition: SBLaunchInfo.h:14
bool Contains(BaseType r) const
Definition: RangeMap.h:77
bool operator<(const AddressData &rhs) const
Definition: RangeMap.h:834
Range(BaseType b, SizeType s)
Definition: RangeMap.h:38
const Entry & GetEntryRef(size_t i) const
Definition: RangeMap.h:709
bool IsEmpty() const
Definition: RangeMap.h:239
AddressData< B, T > Entry
Definition: RangeMap.h:851
const Entry & GetEntryRef(size_t i) const
Definition: RangeMap.h:891
const Entry * FindEntryThatContains(B addr) const
Definition: RangeMap.h:743
void Slide(BaseType slide)
Definition: RangeMap.h:231
Entry & GetEntryRef(size_t i)
Definition: RangeMap.h:483
bool DoesIntersect(const Range &rhs) const
Definition: RangeMap.h:101
bool operator!=(const Range &rhs) const
Definition: RangeMap.h:120
Entry * FindEntry(B addr, bool exact_match_only)
Definition: RangeMap.h:897
void Reserve(typename Collection::size_type size)
Definition: RangeMap.h:471
bool ContainsEndInclusive(BaseType r) const
Definition: RangeMap.h:81
static bool BaseLessThan(const Entry &lhs, const Entry &rhs)
Definition: RangeMap.h:893
void SetRangeEnd(BaseType end)
Definition: RangeMap.h:64
void Append(const Entry &entry)
Definition: RangeMap.h:858
lldb_private::Range< B, S > Range
Definition: RangeMap.h:627
Range< B, S > Entry
Definition: RangeMap.h:336
const Entry * FindEntryThatContains(B addr) const
Definition: RangeMap.h:518
BaseType GetMinRangeBase(BaseType fail_value) const
Definition: RangeMap.h:209
RangeData(B base, S size, DataType d)
Definition: RangeMap.h:601
bool RemoveEntryAtIndex(uint32_t idx)
Definition: RangeMap.h:373
static bool BaseLessThan(const Entry &lhs, const Entry &rhs)
Definition: RangeMap.h:711
BaseType GetMaxRangeEnd(BaseType fail_value) const
Definition: RangeMap.h:220
const Entry * FindEntryThatContainsOrFollows(B addr) const
Definition: RangeMap.h:788
void Slide(BaseType slide)
Definition: RangeMap.h:50
#define UINT32_MAX
Definition: lldb-defines.h:31
const Entry * FindNextEntry(const Entry *entry)
Definition: RangeMap.h:920
void Append(B base, S size)
Definition: RangeMap.h:141
const Entry * GetEntryAtIndex(size_t i) const
Definition: RangeMap.h:885
const Entry * Back() const
Definition: RangeMap.h:488
bool operator==(const AddressData &rhs) const
Definition: RangeMap.h:840
const Entry * Back() const
Definition: RangeMap.h:928
static bool BaseLessThan(const Entry &lhs, const Entry &rhs)
Definition: RangeMap.h:492
Entry * FindEntryThatContains(B addr)
Definition: RangeMap.h:737
llvm::SmallVector< Entry, N > Collection
Definition: RangeMap.h:133
bool RemoveEntrtAtIndex(uint32_t idx)
Definition: RangeMap.h:143
BaseType GetMinRangeBase(BaseType fail_value) const
Definition: RangeMap.h:441
bool operator<(const Range &rhs) const
Definition: RangeMap.h:110
const Entry * GetEntryAtIndex(size_t i) const
Definition: RangeMap.h:243
uint32_t FindEntryIndexesThatContain(B addr, std::vector< uint32_t > &indexes) const
Definition: RangeMap.h:722
void Slide(BaseType slide)
Definition: RangeMap.h:463
void CombinePrevAndNext(typename Collection::iterator pos)
Definition: RangeMap.h:564
void Insert(const Entry &entry, bool combine)
Definition: RangeMap.h:349
RangeData(B base, S size)
Definition: RangeMap.h:599
size_t GetSize() const
Definition: RangeMap.h:241
bool IsValid() const
Definition: RangeMap.h:75
const Entry * FindEntryThatContains(B addr) const
Definition: RangeMap.h:283
llvm::SmallVector< Entry, N > Collection
Definition: RangeMap.h:852
static bool BaseLessThan(const Entry &lhs, const Entry &rhs)
Definition: RangeMap.h:257
const Entry * GetEntryAtIndex(size_t i) const
Definition: RangeMap.h:477
const Entry & GetEntryRef(size_t i) const
Definition: RangeMap.h:484
const Entry * FindEntryStartsAt(B addr) const
Definition: RangeMap.h:766
const Entry & GetEntryRef(size_t i) const
Definition: RangeMap.h:249
uint32_t FindEntryIndexThatContains(B addr) const
Definition: RangeMap.h:261
void SetByteSize(SizeType s)
Definition: RangeMap.h:73
void CombineConsecutiveEntriesWithEqualData()
Definition: RangeMap.h:656
void CombineConsecutiveRanges()
Definition: RangeMap.h:168
bool operator<(const RangeData &rhs) const
Definition: RangeMap.h:603
bool DoesAdjoinOrIntersect(const Range &rhs) const
Definition: RangeMap.h:91
void Append(B base, S size)
Definition: RangeMap.h:345
const Entry * Back() const
Definition: RangeMap.h:253
bool operator!=(const RangeData &rhs) const
Definition: RangeMap.h:618
AddressData(B a, DataType d)
Definition: RangeMap.h:832
uint32_t FindEntryIndexThatContains(B addr) const
Definition: RangeMap.h:496
size_t GetSize() const
Definition: RangeMap.h:475
Entry * GetMutableEntryAtIndex(size_t i)
Definition: RangeMap.h:702
void SetRangeBase(BaseType b)
Definition: RangeMap.h:48
uint32_t FindEntryIndexThatContains(B addr) const
Definition: RangeMap.h:715
const Entry * Back() const
Definition: RangeMap.h:812
BaseType GetRangeEnd() const
Definition: RangeMap.h:62
bool operator!=(const AddressData &rhs) const
Definition: RangeMap.h:844
BaseType GetMaxRangeEnd(BaseType fail_value) const
Definition: RangeMap.h:452
bool IsEmpty() const
Definition: RangeMap.h:473
void Append(const Entry &entry)
Definition: RangeMap.h:343
bool operator==(const RangeData &rhs) const
Definition: RangeMap.h:613
SizeType GetByteSize() const
Definition: RangeMap.h:71
const Entry * FindEntryThatContains(const Entry &range) const
Definition: RangeMap.h:306
RangeData< B, S, T > Entry
Definition: RangeMap.h:628
std::vector< Entry > Collection
Definition: RangeMap.h:337
bool Contains(const Range &range) const
Definition: RangeMap.h:85
void Append(const Entry &entry)
Definition: RangeMap.h:139
bool Union(const Range &rhs)
Definition: RangeMap.h:52
BaseType GetRangeBase() const
Definition: RangeMap.h:46
bool operator==(const Range &rhs) const
Definition: RangeMap.h:116
Range< B, S > Entry
Definition: RangeMap.h:132
void Append(const Entry &entry)
Definition: RangeMap.h:635