contrib/llvm/tools/lldb/include/lldb/Core/RangeMap.h

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