contrib/llvm-project/lldb/include/lldb/Utility/RangeMap.h

   1 //===-- RangeMap.h ----------------------------------------------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #ifndef LLDB_UTILITY_RANGEMAP_H
  10 #define LLDB_UTILITY_RANGEMAP_H
  11
  12 #include <algorithm>
  13 #include <vector>
  14
  15 #include "llvm/ADT/SmallVector.h"
  16
  17 #include "lldb/lldb-private.h"
  18
  19 // Uncomment to make sure all Range objects are sorted when needed
  20 //#define ASSERT_RANGEMAP_ARE_SORTED
  21
  22 namespace lldb_private {
  23
  24 // Templatized classes for dealing with generic ranges and also collections of
  25 // ranges, or collections of ranges that have associated data.
  26
  27 // A simple range class where you get to define the type of the range
  28 // base "B", and the type used for the range byte size "S".
  29 template <typename B, typename S> struct Range {
  30   typedef B BaseType;
  31   typedef S SizeType;
  32
  33   BaseType base;
  34   SizeType size;
  35
  36   Range() : base(0), size(0) {}
  37
  38   Range(BaseType b, SizeType s) : base(b), size(s) {}
  39
  40   void Clear(BaseType b = 0) {
  41     base = b;
  42     size = 0;
  43   }
  44
  45   // Set the start value for the range, and keep the same size
  46   BaseType GetRangeBase() const { return base; }
  47
  48   void SetRangeBase(BaseType b) { base = b; }
  49
  50   void Slide(BaseType slide) { base += slide; }
  51
  52   bool Union(const Range &rhs) {
  53     if (DoesAdjoinOrIntersect(rhs)) {
  54       auto new_end = std::max<BaseType>(GetRangeEnd(), rhs.GetRangeEnd());
  55       base = std::min<BaseType>(base, rhs.base);
  56       size = new_end - base;
  57       return true;
  58     }
  59     return false;
  60   }
  61
  62   BaseType GetRangeEnd() const { return base + size; }
  63
  64   void SetRangeEnd(BaseType end) {
  65     if (end > base)
  66       size = end - base;
  67     else
  68       size = 0;
  69   }
  70
  71   SizeType GetByteSize() const { return size; }
  72
  73   void SetByteSize(SizeType s) { size = s; }
  74
  75   bool IsValid() const { return size > 0; }
  76
  77   bool Contains(BaseType r) const {
  78     return (GetRangeBase() <= r) && (r < GetRangeEnd());
  79   }
  80
  81   bool ContainsEndInclusive(BaseType r) const {
  82     return (GetRangeBase() <= r) && (r <= GetRangeEnd());
  83   }
  84
  85   bool Contains(const Range &range) const {
  86     return Contains(range.GetRangeBase()) &&
  87            ContainsEndInclusive(range.GetRangeEnd());
  88   }
  89
  90   // Returns true if the two ranges adjoing or intersect
  91   bool DoesAdjoinOrIntersect(const Range &rhs) const {
  92     const BaseType lhs_base = this->GetRangeBase();
  93     const BaseType rhs_base = rhs.GetRangeBase();
  94     const BaseType lhs_end = this->GetRangeEnd();
  95     const BaseType rhs_end = rhs.GetRangeEnd();
  96     bool result = (lhs_base <= rhs_end) && (lhs_end >= rhs_base);
  97     return result;
  98   }
  99
 100   // Returns true if the two ranges intersect
 101   bool DoesIntersect(const Range &rhs) const {
 102     const BaseType lhs_base = this->GetRangeBase();
 103     const BaseType rhs_base = rhs.GetRangeBase();
 104     const BaseType lhs_end = this->GetRangeEnd();
 105     const BaseType rhs_end = rhs.GetRangeEnd();
 106     bool result = (lhs_base < rhs_end) && (lhs_end > rhs_base);
 107     return result;
 108   }
 109
 110   bool operator<(const Range &rhs) const {
 111     if (base == rhs.base)
 112       return size < rhs.size;
 113     return base < rhs.base;
 114   }
 115
 116   bool operator==(const Range &rhs) const {
 117     return base == rhs.base && size == rhs.size;
 118   }
 119
 120   bool operator!=(const Range &rhs) const {
 121     return base != rhs.base || size != rhs.size;
 122   }
 123 };
 124
 125 // A range array class where you get to define the type of the ranges
 126 // that the collection contains.
 127
 128 template <typename B, typename S, unsigned N> class RangeArray {
 129 public:
 130   typedef B BaseType;
 131   typedef S SizeType;
 132   typedef Range<B, S> Entry;
 133   typedef llvm::SmallVector<Entry, N> Collection;
 134
 135   RangeArray() = default;
 136
 137   ~RangeArray() = default;
 138
 139   void Append(const Entry &entry) { m_entries.push_back(entry); }
 140
 141   void Append(B base, S size) { m_entries.emplace_back(base, size); }
 142
 143   bool RemoveEntrtAtIndex(uint32_t idx) {
 144     if (idx < m_entries.size()) {
 145       m_entries.erase(m_entries.begin() + idx);
 146       return true;
 147     }
 148     return false;
 149   }
 150
 151   void Sort() {
 152     if (m_entries.size() > 1)
 153       std::stable_sort(m_entries.begin(), m_entries.end());
 154   }
 155
 156 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 157   bool IsSorted() const {
 158     typename Collection::const_iterator pos, end, prev;
 159     for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end;
 160          prev = pos++) {
 161       if (prev != end && *pos < *prev)
 162         return false;
 163     }
 164     return true;
 165   }
 166 #endif
 167
 168   void CombineConsecutiveRanges() {
 169 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 170     assert(IsSorted());
 171 #endif
 172     // Can't combine if ranges if we have zero or one range
 173     if (m_entries.size() > 1) {
 174       // The list should be sorted prior to calling this function
 175       typename Collection::iterator pos;
 176       typename Collection::iterator end;
 177       typename Collection::iterator prev;
 178       bool can_combine = false;
 179       // First we determine if we can combine any of the Entry objects so we
 180       // don't end up allocating and making a new collection for no reason
 181       for (pos = m_entries.begin(), end = m_entries.end(), prev = end;
 182            pos != end; prev = pos++) {
 183         if (prev != end && prev->DoesAdjoinOrIntersect(*pos)) {
 184           can_combine = true;
 185           break;
 186         }
 187       }
 188
 189       // We we can combine at least one entry, then we make a new collection
 190       // and populate it accordingly, and then swap it into place.
 191       if (can_combine) {
 192         Collection minimal_ranges;
 193         for (pos = m_entries.begin(), end = m_entries.end(), prev = end;
 194              pos != end; prev = pos++) {
 195           if (prev != end && prev->DoesAdjoinOrIntersect(*pos))
 196             minimal_ranges.back().SetRangeEnd(
 197                 std::max<BaseType>(prev->GetRangeEnd(), pos->GetRangeEnd()));
 198           else
 199             minimal_ranges.push_back(*pos);
 200         }
 201         // Use the swap technique in case our new vector is much smaller. We
 202         // must swap when using the STL because std::vector objects never
 203         // release or reduce the memory once it has been allocated/reserved.
 204         m_entries.swap(minimal_ranges);
 205       }
 206     }
 207   }
 208
 209   BaseType GetMinRangeBase(BaseType fail_value) const {
 210 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 211     assert(IsSorted());
 212 #endif
 213     if (m_entries.empty())
 214       return fail_value;
 215     // m_entries must be sorted, so if we aren't empty, we grab the first
 216     // range's base
 217     return m_entries.front().GetRangeBase();
 218   }
 219
 220   BaseType GetMaxRangeEnd(BaseType fail_value) const {
 221 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 222     assert(IsSorted());
 223 #endif
 224     if (m_entries.empty())
 225       return fail_value;
 226     // m_entries must be sorted, so if we aren't empty, we grab the last
 227     // range's end
 228     return m_entries.back().GetRangeEnd();
 229   }
 230
 231   void Slide(BaseType slide) {
 232     typename Collection::iterator pos, end;
 233     for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos)
 234       pos->Slide(slide);
 235   }
 236
 237   void Clear() { m_entries.clear(); }
 238
 239   bool IsEmpty() const { return m_entries.empty(); }
 240
 241   size_t GetSize() const { return m_entries.size(); }
 242
 243   const Entry *GetEntryAtIndex(size_t i) const {
 244     return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
 245   }
 246
 247   // Clients must ensure that "i" is a valid index prior to calling this
 248   // function
 249   const Entry &GetEntryRef(size_t i) const { return m_entries[i]; }
 250
 251   Entry *Back() { return (m_entries.empty() ? nullptr : &m_entries.back()); }
 252
 253   const Entry *Back() const {
 254     return (m_entries.empty() ? nullptr : &m_entries.back());
 255   }
 256
 257   static bool BaseLessThan(const Entry &lhs, const Entry &rhs) {
 258     return lhs.GetRangeBase() < rhs.GetRangeBase();
 259   }
 260
 261   uint32_t FindEntryIndexThatContains(B addr) const {
 262 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 263     assert(IsSorted());
 264 #endif
 265     if (!m_entries.empty()) {
 266       Entry entry(addr, 1);
 267       typename Collection::const_iterator begin = m_entries.begin();
 268       typename Collection::const_iterator end = m_entries.end();
 269       typename Collection::const_iterator pos =
 270           std::lower_bound(begin, end, entry, BaseLessThan);
 271
 272       if (pos != end && pos->Contains(addr)) {
 273         return std::distance(begin, pos);
 274       } else if (pos != begin) {
 275         --pos;
 276         if (pos->Contains(addr))
 277           return std::distance(begin, pos);
 278       }
 279     }
 280     return UINT32_MAX;
 281   }
 282
 283   const Entry *FindEntryThatContains(B addr) const {
 284 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 285     assert(IsSorted());
 286 #endif
 287     if (!m_entries.empty()) {
 288       Entry entry(addr, 1);
 289       typename Collection::const_iterator begin = m_entries.begin();
 290       typename Collection::const_iterator end = m_entries.end();
 291       typename Collection::const_iterator pos =
 292           std::lower_bound(begin, end, entry, BaseLessThan);
 293
 294       if (pos != end && pos->Contains(addr)) {
 295         return &(*pos);
 296       } else if (pos != begin) {
 297         --pos;
 298         if (pos->Contains(addr)) {
 299           return &(*pos);
 300         }
 301       }
 302     }
 303     return nullptr;
 304   }
 305
 306   const Entry *FindEntryThatContains(const Entry &range) const {
 307 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 308     assert(IsSorted());
 309 #endif
 310     if (!m_entries.empty()) {
 311       typename Collection::const_iterator begin = m_entries.begin();
 312       typename Collection::const_iterator end = m_entries.end();
 313       typename Collection::const_iterator pos =
 314           std::lower_bound(begin, end, range, BaseLessThan);
 315
 316       if (pos != end && pos->Contains(range)) {
 317         return &(*pos);
 318       } else if (pos != begin) {
 319         --pos;
 320         if (pos->Contains(range)) {
 321           return &(*pos);
 322         }
 323       }
 324     }
 325     return nullptr;
 326   }
 327
 328 protected:
 329   Collection m_entries;
 330 };
 331
 332 template <typename B, typename S> class RangeVector {
 333 public:
 334   typedef B BaseType;
 335   typedef S SizeType;
 336   typedef Range<B, S> Entry;
 337   typedef std::vector<Entry> Collection;
 338
 339   RangeVector() = default;
 340
 341   ~RangeVector() = default;
 342
 343   void Append(const Entry &entry) { m_entries.push_back(entry); }
 344
 345   void Append(B base, S size) { m_entries.emplace_back(base, size); }
 346
 347   // Insert an item into a sorted list and optionally combine it with any
 348   // adjacent blocks if requested.
 349   void Insert(const Entry &entry, bool combine) {
 350     if (m_entries.empty()) {
 351       m_entries.push_back(entry);
 352       return;
 353     }
 354     auto begin = m_entries.begin();
 355     auto end = m_entries.end();
 356     auto pos = std::lower_bound(begin, end, entry);
 357     if (combine) {
 358       if (pos != end && pos->Union(entry)) {
 359         CombinePrevAndNext(pos);
 360         return;
 361       }
 362       if (pos != begin) {
 363         auto prev = pos - 1;
 364         if (prev->Union(entry)) {
 365           CombinePrevAndNext(prev);
 366           return;
 367         }
 368       }
 369     }
 370     m_entries.insert(pos, entry);
 371   }
 372
 373   bool RemoveEntryAtIndex(uint32_t idx) {
 374     if (idx < m_entries.size()) {
 375       m_entries.erase(m_entries.begin() + idx);
 376       return true;
 377     }
 378     return false;
 379   }
 380
 381   void Sort() {
 382     if (m_entries.size() > 1)
 383       std::stable_sort(m_entries.begin(), m_entries.end());
 384   }
 385
 386 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 387   bool IsSorted() const {
 388     typename Collection::const_iterator pos, end, prev;
 389     // First we determine if we can combine any of the Entry objects so we
 390     // don't end up allocating and making a new collection for no reason
 391     for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end;
 392          prev = pos++) {
 393       if (prev != end && *pos < *prev)
 394         return false;
 395     }
 396     return true;
 397   }
 398 #endif
 399
 400   void CombineConsecutiveRanges() {
 401 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 402     assert(IsSorted());
 403 #endif
 404     // Can't combine if ranges if we have zero or one range
 405     if (m_entries.size() > 1) {
 406       // The list should be sorted prior to calling this function
 407       typename Collection::iterator pos;
 408       typename Collection::iterator end;
 409       typename Collection::iterator prev;
 410       bool can_combine = false;
 411       // First we determine if we can combine any of the Entry objects so we
 412       // don't end up allocating and making a new collection for no reason
 413       for (pos = m_entries.begin(), end = m_entries.end(), prev = end;
 414            pos != end; prev = pos++) {
 415         if (prev != end && prev->DoesAdjoinOrIntersect(*pos)) {
 416           can_combine = true;
 417           break;
 418         }
 419       }
 420
 421       // We we can combine at least one entry, then we make a new collection
 422       // and populate it accordingly, and then swap it into place.
 423       if (can_combine) {
 424         Collection minimal_ranges;
 425         for (pos = m_entries.begin(), end = m_entries.end(), prev = end;
 426              pos != end; prev = pos++) {
 427           if (prev != end && prev->DoesAdjoinOrIntersect(*pos))
 428             minimal_ranges.back().SetRangeEnd(
 429                 std::max<BaseType>(prev->GetRangeEnd(), pos->GetRangeEnd()));
 430           else
 431             minimal_ranges.push_back(*pos);
 432         }
 433         // Use the swap technique in case our new vector is much smaller. We
 434         // must swap when using the STL because std::vector objects never
 435         // release or reduce the memory once it has been allocated/reserved.
 436         m_entries.swap(minimal_ranges);
 437       }
 438     }
 439   }
 440
 441   BaseType GetMinRangeBase(BaseType fail_value) const {
 442 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 443     assert(IsSorted());
 444 #endif
 445     if (m_entries.empty())
 446       return fail_value;
 447     // m_entries must be sorted, so if we aren't empty, we grab the first
 448     // range's base
 449     return m_entries.front().GetRangeBase();
 450   }
 451
 452   BaseType GetMaxRangeEnd(BaseType fail_value) const {
 453 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 454     assert(IsSorted());
 455 #endif
 456     if (m_entries.empty())
 457       return fail_value;
 458     // m_entries must be sorted, so if we aren't empty, we grab the last
 459     // range's end
 460     return m_entries.back().GetRangeEnd();
 461   }
 462
 463   void Slide(BaseType slide) {
 464     typename Collection::iterator pos, end;
 465     for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos)
 466       pos->Slide(slide);
 467   }
 468
 469   void Clear() { m_entries.clear(); }
 470
 471   void Reserve(typename Collection::size_type size) { m_entries.reserve(size); }
 472
 473   bool IsEmpty() const { return m_entries.empty(); }
 474
 475   size_t GetSize() const { return m_entries.size(); }
 476
 477   const Entry *GetEntryAtIndex(size_t i) const {
 478     return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
 479   }
 480
 481   // Clients must ensure that "i" is a valid index prior to calling this
 482   // function
 483   Entry &GetEntryRef(size_t i) { return m_entries[i]; }
 484   const Entry &GetEntryRef(size_t i) const { return m_entries[i]; }
 485
 486   Entry *Back() { return (m_entries.empty() ? nullptr : &m_entries.back()); }
 487
 488   const Entry *Back() const {
 489     return (m_entries.empty() ? nullptr : &m_entries.back());
 490   }
 491
 492   static bool BaseLessThan(const Entry &lhs, const Entry &rhs) {
 493     return lhs.GetRangeBase() < rhs.GetRangeBase();
 494   }
 495
 496   uint32_t FindEntryIndexThatContains(B addr) const {
 497 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 498     assert(IsSorted());
 499 #endif
 500     if (!m_entries.empty()) {
 501       Entry entry(addr, 1);
 502       typename Collection::const_iterator begin = m_entries.begin();
 503       typename Collection::const_iterator end = m_entries.end();
 504       typename Collection::const_iterator pos =
 505           std::lower_bound(begin, end, entry, BaseLessThan);
 506
 507       if (pos != end && pos->Contains(addr)) {
 508         return std::distance(begin, pos);
 509       } else if (pos != begin) {
 510         --pos;
 511         if (pos->Contains(addr))
 512           return std::distance(begin, pos);
 513       }
 514     }
 515     return UINT32_MAX;
 516   }
 517
 518   const Entry *FindEntryThatContains(B addr) const {
 519 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 520     assert(IsSorted());
 521 #endif
 522     if (!m_entries.empty()) {
 523       Entry entry(addr, 1);
 524       typename Collection::const_iterator begin = m_entries.begin();
 525       typename Collection::const_iterator end = m_entries.end();
 526       typename Collection::const_iterator pos =
 527           std::lower_bound(begin, end, entry, BaseLessThan);
 528
 529       if (pos != end && pos->Contains(addr)) {
 530         return &(*pos);
 531       } else if (pos != begin) {
 532         --pos;
 533         if (pos->Contains(addr)) {
 534           return &(*pos);
 535         }
 536       }
 537     }
 538     return nullptr;
 539   }
 540
 541   const Entry *FindEntryThatContains(const Entry &range) const {
 542 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 543     assert(IsSorted());
 544 #endif
 545     if (!m_entries.empty()) {
 546       typename Collection::const_iterator begin = m_entries.begin();
 547       typename Collection::const_iterator end = m_entries.end();
 548       typename Collection::const_iterator pos =
 549           std::lower_bound(begin, end, range, BaseLessThan);
 550
 551       if (pos != end && pos->Contains(range)) {
 552         return &(*pos);
 553       } else if (pos != begin) {
 554         --pos;
 555         if (pos->Contains(range)) {
 556           return &(*pos);
 557         }
 558       }
 559     }
 560     return nullptr;
 561   }
 562
 563 protected:
 564   void CombinePrevAndNext(typename Collection::iterator pos) {
 565     // Check if the prev or next entries in case they need to be unioned with
 566     // the entry pointed to by "pos".
 567     if (pos != m_entries.begin()) {
 568       auto prev = pos - 1;
 569       if (prev->Union(*pos))
 570         m_entries.erase(pos);
 571       pos = prev;
 572     }
 573
 574     auto end = m_entries.end();
 575     if (pos != end) {
 576       auto next = pos + 1;
 577       if (next != end) {
 578         if (pos->Union(*next))
 579           m_entries.erase(next);
 580       }
 581     }
 582     return;
 583   }
 584
 585   Collection m_entries;
 586 };
 587
 588 // A simple range  with data class where you get to define the type of
 589 // the range base "B", the type used for the range byte size "S", and the type
 590 // for the associated data "T".
 591 template <typename B, typename S, typename T>
 592 struct RangeData : public Range<B, S> {
 593   typedef T DataType;
 594
 595   DataType data;
 596
 597   RangeData() : Range<B, S>(), data() {}
 598
 599   RangeData(B base, S size) : Range<B, S>(base, size), data() {}
 600
 601   RangeData(B base, S size, DataType d) : Range<B, S>(base, size), data(d) {}
 602
 603   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>
 625 class RangeDataVector {
 626 public:
 627   typedef lldb_private::Range<B, S> Range;
 628   typedef RangeData<B, S, T> Entry;
 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
 656   void CombineConsecutiveEntriesWithEqualData() {
 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
 715   uint32_t FindEntryIndexThatContains(B addr) const {
 716     const Entry *entry = FindEntryThatContains(addr);
 717     if (entry)
 718       return std::distance(m_entries.begin(), entry);
 719     return UINT32_MAX;
 720   }
 721
 722   uint32_t FindEntryIndexesThatContain(B addr,
 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:
 851   typedef AddressData<B, T> Entry;
 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