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 // C Includes
  14 // C++ Includes
  15 #include <algorithm>
  16 #include <vector>
  17
  18 // Other libraries and framework includes
  19 #include "llvm/ADT/SmallVector.h"
  20
  21 // Project includes
  22 #include "lldb/lldb-private.h"
  23
  24 // Uncomment to make sure all Range objects are sorted when needed
  25 //#define ASSERT_RANGEMAP_ARE_SORTED
  26
  27 namespace lldb_private {
  28
  29 //----------------------------------------------------------------------
  30 // Templatized classes for dealing with generic ranges and also collections of
  31 // ranges, or collections of ranges that have associated data.
  32 //----------------------------------------------------------------------
  33
  34 //----------------------------------------------------------------------
  35 // A simple range class where you get to define the type of the range
  36 // base "B", and the type used for the range byte size "S".
  37 //----------------------------------------------------------------------
  38 template <typename B, typename S> struct Range {
  39   typedef B BaseType;
  40   typedef S SizeType;
  41
  42   BaseType base;
  43   SizeType size;
  44
  45   Range() : base(0), size(0) {}
  46
  47   Range(BaseType b, SizeType s) : base(b), size(s) {}
  48
  49   void Clear(BaseType b = 0) {
  50     base = b;
  51     size = 0;
  52   }
  53
  54   // Set the start value for the range, and keep the same size
  55   BaseType GetRangeBase() const { return base; }
  56
  57   void SetRangeBase(BaseType b) { base = b; }
  58
  59   void Slide(BaseType slide) { base += slide; }
  60
  61   bool Union(const Range &rhs)
  62   {
  63     if (DoesAdjoinOrIntersect(rhs))
  64     {
  65       auto new_end = std::max<BaseType>(GetRangeEnd(), rhs.GetRangeEnd());
  66       base = std::min<BaseType>(base, rhs.base);
  67       size = new_end - base;
  68       return true;
  69     }
  70     return false;
  71   }
  72
  73   BaseType GetRangeEnd() const { return base + size; }
  74
  75   void SetRangeEnd(BaseType end) {
  76     if (end > base)
  77       size = end - base;
  78     else
  79       size = 0;
  80   }
  81
  82   SizeType GetByteSize() const { return size; }
  83
  84   void SetByteSize(SizeType s) { size = s; }
  85
  86   bool IsValid() const { return size > 0; }
  87
  88   bool Contains(BaseType r) const {
  89     return (GetRangeBase() <= r) && (r < GetRangeEnd());
  90   }
  91
  92   bool ContainsEndInclusive(BaseType r) const {
  93     return (GetRangeBase() <= r) && (r <= GetRangeEnd());
  94   }
  95
  96   bool Contains(const Range &range) const {
  97     return Contains(range.GetRangeBase()) &&
  98            ContainsEndInclusive(range.GetRangeEnd());
  99   }
 100
 101   // Returns true if the two ranges adjoing or intersect
 102   bool DoesAdjoinOrIntersect(const Range &rhs) const {
 103     const BaseType lhs_base = this->GetRangeBase();
 104     const BaseType rhs_base = rhs.GetRangeBase();
 105     const BaseType lhs_end = this->GetRangeEnd();
 106     const BaseType rhs_end = rhs.GetRangeEnd();
 107     bool result = (lhs_base <= rhs_end) && (lhs_end >= rhs_base);
 108     return result;
 109   }
 110
 111   // Returns true if the two ranges intersect
 112   bool DoesIntersect(const Range &rhs) const {
 113     const BaseType lhs_base = this->GetRangeBase();
 114     const BaseType rhs_base = rhs.GetRangeBase();
 115     const BaseType lhs_end = this->GetRangeEnd();
 116     const BaseType rhs_end = rhs.GetRangeEnd();
 117     bool result = (lhs_base < rhs_end) && (lhs_end > rhs_base);
 118     return result;
 119   }
 120
 121   bool operator<(const Range &rhs) const {
 122     if (base == rhs.base)
 123       return size < rhs.size;
 124     return base < rhs.base;
 125   }
 126
 127   bool operator==(const Range &rhs) const {
 128     return base == rhs.base && size == rhs.size;
 129   }
 130
 131   bool operator!=(const Range &rhs) const {
 132     return base != rhs.base || size != rhs.size;
 133   }
 134 };
 135
 136 //----------------------------------------------------------------------
 137 // A range array class where you get to define the type of the ranges
 138 // that the collection contains.
 139 //----------------------------------------------------------------------
 140
 141 template <typename B, typename S, unsigned N> class RangeArray {
 142 public:
 143   typedef B BaseType;
 144   typedef S SizeType;
 145   typedef Range<B, S> Entry;
 146   typedef llvm::SmallVector<Entry, N> Collection;
 147
 148   RangeArray() = default;
 149
 150   ~RangeArray() = default;
 151
 152   void Append(const Entry &entry) { m_entries.push_back(entry); }
 153
 154   void Append(B base, S size) { m_entries.emplace_back(base, size); }
 155
 156   bool RemoveEntrtAtIndex(uint32_t idx) {
 157     if (idx < m_entries.size()) {
 158       m_entries.erase(m_entries.begin() + idx);
 159       return true;
 160     }
 161     return false;
 162   }
 163
 164   void Sort() {
 165     if (m_entries.size() > 1)
 166       std::stable_sort(m_entries.begin(), m_entries.end());
 167   }
 168
 169 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 170   bool IsSorted() const {
 171     typename Collection::const_iterator pos, end, prev;
 172     // First we determine if we can combine any of the Entry objects so we
 173     // don't end up allocating and making a new collection for no reason
 174     for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end;
 175          prev = pos++) {
 176       if (prev != end && *pos < *prev)
 177         return false;
 178     }
 179     return true;
 180   }
 181 #endif
 182
 183   void CombineConsecutiveRanges() {
 184 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 185     assert(IsSorted());
 186 #endif
 187     // Can't combine if ranges if we have zero or one range
 188     if (m_entries.size() > 1) {
 189       // The list should be sorted prior to calling this function
 190       typename Collection::iterator pos;
 191       typename Collection::iterator end;
 192       typename Collection::iterator prev;
 193       bool can_combine = false;
 194       // First we determine if we can combine any of the Entry objects so we
 195       // don't end up allocating and making a new collection for no reason
 196       for (pos = m_entries.begin(), end = m_entries.end(), prev = end;
 197            pos != end; prev = pos++) {
 198         if (prev != end && prev->DoesAdjoinOrIntersect(*pos)) {
 199           can_combine = true;
 200           break;
 201         }
 202       }
 203
 204       // We we can combine at least one entry, then we make a new collection
 205       // and populate it accordingly, and then swap it into place.
 206       if (can_combine) {
 207         Collection minimal_ranges;
 208         for (pos = m_entries.begin(), end = m_entries.end(), prev = end;
 209              pos != end; prev = pos++) {
 210           if (prev != end && prev->DoesAdjoinOrIntersect(*pos))
 211             minimal_ranges.back().SetRangeEnd(
 212                 std::max<BaseType>(prev->GetRangeEnd(), pos->GetRangeEnd()));
 213           else
 214             minimal_ranges.push_back(*pos);
 215         }
 216         // Use the swap technique in case our new vector is much smaller. We
 217         // must swap when using the STL because std::vector objects never
 218         // release or reduce the memory once it has been allocated/reserved.
 219         m_entries.swap(minimal_ranges);
 220       }
 221     }
 222   }
 223
 224   BaseType GetMinRangeBase(BaseType fail_value) const {
 225 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 226     assert(IsSorted());
 227 #endif
 228     if (m_entries.empty())
 229       return fail_value;
 230     // m_entries must be sorted, so if we aren't empty, we grab the first
 231     // range's base
 232     return m_entries.front().GetRangeBase();
 233   }
 234
 235   BaseType GetMaxRangeEnd(BaseType fail_value) const {
 236 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 237     assert(IsSorted());
 238 #endif
 239     if (m_entries.empty())
 240       return fail_value;
 241     // m_entries must be sorted, so if we aren't empty, we grab the last
 242     // range's end
 243     return m_entries.back().GetRangeEnd();
 244   }
 245
 246   void Slide(BaseType slide) {
 247     typename Collection::iterator pos, end;
 248     for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos)
 249       pos->Slide(slide);
 250   }
 251
 252   void Clear() { m_entries.clear(); }
 253
 254   bool IsEmpty() const { return m_entries.empty(); }
 255
 256   size_t GetSize() const { return m_entries.size(); }
 257
 258   const Entry *GetEntryAtIndex(size_t i) const {
 259     return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
 260   }
 261
 262   // Clients must ensure that "i" is a valid index prior to calling this
 263   // function
 264   const Entry &GetEntryRef(size_t i) const { return m_entries[i]; }
 265
 266   Entry *Back() { return (m_entries.empty() ? nullptr : &m_entries.back()); }
 267
 268   const Entry *Back() const {
 269     return (m_entries.empty() ? nullptr : &m_entries.back());
 270   }
 271
 272   static bool BaseLessThan(const Entry &lhs, const Entry &rhs) {
 273     return lhs.GetRangeBase() < rhs.GetRangeBase();
 274   }
 275
 276   uint32_t FindEntryIndexThatContains(B addr) const {
 277 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 278     assert(IsSorted());
 279 #endif
 280     if (!m_entries.empty()) {
 281       Entry entry(addr, 1);
 282       typename Collection::const_iterator begin = m_entries.begin();
 283       typename Collection::const_iterator end = m_entries.end();
 284       typename Collection::const_iterator pos =
 285           std::lower_bound(begin, end, entry, BaseLessThan);
 286
 287       if (pos != end && pos->Contains(addr)) {
 288         return std::distance(begin, pos);
 289       } else if (pos != begin) {
 290         --pos;
 291         if (pos->Contains(addr))
 292           return std::distance(begin, pos);
 293       }
 294     }
 295     return UINT32_MAX;
 296   }
 297
 298   const Entry *FindEntryThatContains(B addr) const {
 299 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 300     assert(IsSorted());
 301 #endif
 302     if (!m_entries.empty()) {
 303       Entry entry(addr, 1);
 304       typename Collection::const_iterator begin = m_entries.begin();
 305       typename Collection::const_iterator end = m_entries.end();
 306       typename Collection::const_iterator pos =
 307           std::lower_bound(begin, end, entry, BaseLessThan);
 308
 309       if (pos != end && pos->Contains(addr)) {
 310         return &(*pos);
 311       } else if (pos != begin) {
 312         --pos;
 313         if (pos->Contains(addr)) {
 314           return &(*pos);
 315         }
 316       }
 317     }
 318     return nullptr;
 319   }
 320
 321   const Entry *FindEntryThatContains(const Entry &range) const {
 322 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 323     assert(IsSorted());
 324 #endif
 325     if (!m_entries.empty()) {
 326       typename Collection::const_iterator begin = m_entries.begin();
 327       typename Collection::const_iterator end = m_entries.end();
 328       typename Collection::const_iterator pos =
 329           std::lower_bound(begin, end, range, BaseLessThan);
 330
 331       if (pos != end && pos->Contains(range)) {
 332         return &(*pos);
 333       } else if (pos != begin) {
 334         --pos;
 335         if (pos->Contains(range)) {
 336           return &(*pos);
 337         }
 338       }
 339     }
 340     return nullptr;
 341   }
 342
 343 protected:
 344   Collection m_entries;
 345 };
 346
 347 template <typename B, typename S> class RangeVector {
 348 public:
 349   typedef B BaseType;
 350   typedef S SizeType;
 351   typedef Range<B, S> Entry;
 352   typedef std::vector<Entry> Collection;
 353
 354   RangeVector() = default;
 355
 356   ~RangeVector() = default;
 357
 358   void Append(const Entry &entry) { m_entries.push_back(entry); }
 359
 360   void Append(B base, S size) { m_entries.emplace_back(base, size); }
 361
 362   // Insert an item into a sorted list and optionally combine it with any
 363   // adjacent blocks if requested.
 364   void Insert(const Entry &entry, bool combine) {
 365     if (m_entries.empty()) {
 366       m_entries.push_back(entry);
 367       return;
 368     }
 369     auto begin = m_entries.begin();
 370     auto end = m_entries.end();
 371     auto pos = std::lower_bound(begin, end, entry);
 372     if (combine) {
 373       if (pos != end && pos->Union(entry)) {
 374         CombinePrevAndNext(pos);
 375         return;
 376       }
 377       if (pos != begin) {
 378         auto prev = pos - 1;
 379         if (prev->Union(entry)) {
 380           CombinePrevAndNext(prev);
 381           return;
 382         }
 383       }
 384     }
 385     m_entries.insert(pos, entry);
 386   }
 387
 388   bool RemoveEntryAtIndex(uint32_t idx) {
 389     if (idx < m_entries.size()) {
 390       m_entries.erase(m_entries.begin() + idx);
 391       return true;
 392     }
 393     return false;
 394   }
 395
 396   void Sort() {
 397     if (m_entries.size() > 1)
 398       std::stable_sort(m_entries.begin(), m_entries.end());
 399   }
 400
 401 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 402   bool IsSorted() const {
 403     typename Collection::const_iterator pos, end, prev;
 404     // First we determine if we can combine any of the Entry objects so we
 405     // don't end up allocating and making a new collection for no reason
 406     for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end;
 407          prev = pos++) {
 408       if (prev != end && *pos < *prev)
 409         return false;
 410     }
 411     return true;
 412   }
 413 #endif
 414
 415   void CombineConsecutiveRanges() {
 416 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 417     assert(IsSorted());
 418 #endif
 419     // Can't combine if ranges if we have zero or one range
 420     if (m_entries.size() > 1) {
 421       // The list should be sorted prior to calling this function
 422       typename Collection::iterator pos;
 423       typename Collection::iterator end;
 424       typename Collection::iterator prev;
 425       bool can_combine = false;
 426       // First we determine if we can combine any of the Entry objects so we
 427       // don't end up allocating and making a new collection for no reason
 428       for (pos = m_entries.begin(), end = m_entries.end(), prev = end;
 429            pos != end; prev = pos++) {
 430         if (prev != end && prev->DoesAdjoinOrIntersect(*pos)) {
 431           can_combine = true;
 432           break;
 433         }
 434       }
 435
 436       // We we can combine at least one entry, then we make a new collection
 437       // and populate it accordingly, and then swap it into place.
 438       if (can_combine) {
 439         Collection minimal_ranges;
 440         for (pos = m_entries.begin(), end = m_entries.end(), prev = end;
 441              pos != end; prev = pos++) {
 442           if (prev != end && prev->DoesAdjoinOrIntersect(*pos))
 443             minimal_ranges.back().SetRangeEnd(
 444                 std::max<BaseType>(prev->GetRangeEnd(), pos->GetRangeEnd()));
 445           else
 446             minimal_ranges.push_back(*pos);
 447         }
 448         // Use the swap technique in case our new vector is much smaller. We
 449         // must swap when using the STL because std::vector objects never
 450         // release or reduce the memory once it has been allocated/reserved.
 451         m_entries.swap(minimal_ranges);
 452       }
 453     }
 454   }
 455
 456   BaseType GetMinRangeBase(BaseType fail_value) const {
 457 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 458     assert(IsSorted());
 459 #endif
 460     if (m_entries.empty())
 461       return fail_value;
 462     // m_entries must be sorted, so if we aren't empty, we grab the first
 463     // range's base
 464     return m_entries.front().GetRangeBase();
 465   }
 466
 467   BaseType GetMaxRangeEnd(BaseType fail_value) const {
 468 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 469     assert(IsSorted());
 470 #endif
 471     if (m_entries.empty())
 472       return fail_value;
 473     // m_entries must be sorted, so if we aren't empty, we grab the last
 474     // range's end
 475     return m_entries.back().GetRangeEnd();
 476   }
 477
 478   void Slide(BaseType slide) {
 479     typename Collection::iterator pos, end;
 480     for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos)
 481       pos->Slide(slide);
 482   }
 483
 484   void Clear() { m_entries.clear(); }
 485
 486   void Reserve(typename Collection::size_type size) { m_entries.reserve(size); }
 487
 488   bool IsEmpty() const { return m_entries.empty(); }
 489
 490   size_t GetSize() const { return m_entries.size(); }
 491
 492   const Entry *GetEntryAtIndex(size_t i) const {
 493     return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
 494   }
 495
 496   // Clients must ensure that "i" is a valid index prior to calling this
 497   // function
 498   Entry &GetEntryRef(size_t i) { return m_entries[i]; }
 499   const Entry &GetEntryRef(size_t i) const { return m_entries[i]; }
 500
 501   Entry *Back() { return (m_entries.empty() ? nullptr : &m_entries.back()); }
 502
 503   const Entry *Back() const {
 504     return (m_entries.empty() ? nullptr : &m_entries.back());
 505   }
 506
 507   static bool BaseLessThan(const Entry &lhs, const Entry &rhs) {
 508     return lhs.GetRangeBase() < rhs.GetRangeBase();
 509   }
 510
 511   uint32_t FindEntryIndexThatContains(B addr) const {
 512 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 513     assert(IsSorted());
 514 #endif
 515     if (!m_entries.empty()) {
 516       Entry entry(addr, 1);
 517       typename Collection::const_iterator begin = m_entries.begin();
 518       typename Collection::const_iterator end = m_entries.end();
 519       typename Collection::const_iterator pos =
 520           std::lower_bound(begin, end, entry, BaseLessThan);
 521
 522       if (pos != end && pos->Contains(addr)) {
 523         return std::distance(begin, pos);
 524       } else if (pos != begin) {
 525         --pos;
 526         if (pos->Contains(addr))
 527           return std::distance(begin, pos);
 528       }
 529     }
 530     return UINT32_MAX;
 531   }
 532
 533   const Entry *FindEntryThatContains(B addr) const {
 534 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 535     assert(IsSorted());
 536 #endif
 537     if (!m_entries.empty()) {
 538       Entry entry(addr, 1);
 539       typename Collection::const_iterator begin = m_entries.begin();
 540       typename Collection::const_iterator end = m_entries.end();
 541       typename Collection::const_iterator pos =
 542           std::lower_bound(begin, end, entry, BaseLessThan);
 543
 544       if (pos != end && pos->Contains(addr)) {
 545         return &(*pos);
 546       } else if (pos != begin) {
 547         --pos;
 548         if (pos->Contains(addr)) {
 549           return &(*pos);
 550         }
 551       }
 552     }
 553     return nullptr;
 554   }
 555
 556   const Entry *FindEntryThatContains(const Entry &range) const {
 557 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 558     assert(IsSorted());
 559 #endif
 560     if (!m_entries.empty()) {
 561       typename Collection::const_iterator begin = m_entries.begin();
 562       typename Collection::const_iterator end = m_entries.end();
 563       typename Collection::const_iterator pos =
 564           std::lower_bound(begin, end, range, BaseLessThan);
 565
 566       if (pos != end && pos->Contains(range)) {
 567         return &(*pos);
 568       } else if (pos != begin) {
 569         --pos;
 570         if (pos->Contains(range)) {
 571           return &(*pos);
 572         }
 573       }
 574     }
 575     return nullptr;
 576   }
 577
 578 protected:
 579
 580   void CombinePrevAndNext(typename Collection::iterator pos) {
 581     // Check if the prev or next entries in case they need to be unioned with
 582     // the entry pointed to by "pos".
 583     if (pos != m_entries.begin()) {
 584       auto prev = pos - 1;
 585       if (prev->Union(*pos))
 586         m_entries.erase(pos);
 587       pos = prev;
 588     }
 589
 590     auto end = m_entries.end();
 591     if (pos != end) {
 592       auto next = pos + 1;
 593       if (next != end) {
 594         if (pos->Union(*next))
 595           m_entries.erase(next);
 596       }
 597     }
 598     return;
 599   }
 600
 601   Collection m_entries;
 602 };
 603
 604 //----------------------------------------------------------------------
 605 // A simple range  with data class where you get to define the type of
 606 // the range base "B", the type used for the range byte size "S", and the type
 607 // for the associated data "T".
 608 //----------------------------------------------------------------------
 609 template <typename B, typename S, typename T>
 610 struct RangeData : public Range<B, S> {
 611   typedef T DataType;
 612
 613   DataType data;
 614
 615   RangeData() : Range<B, S>(), data() {}
 616
 617   RangeData(B base, S size) : Range<B, S>(base, size), data() {}
 618
 619   RangeData(B base, S size, DataType d) : Range<B, S>(base, size), data(d) {}
 620
 621   bool operator<(const RangeData &rhs) const {
 622     if (this->base == rhs.base) {
 623       if (this->size == rhs.size)
 624         return this->data < rhs.data;
 625       else
 626         return this->size < rhs.size;
 627     }
 628     return this->base < rhs.base;
 629   }
 630
 631   bool operator==(const RangeData &rhs) const {
 632     return this->GetRangeBase() == rhs.GetRangeBase() &&
 633            this->GetByteSize() == rhs.GetByteSize() && this->data == rhs.data;
 634   }
 635
 636   bool operator!=(const RangeData &rhs) const {
 637     return this->GetRangeBase() != rhs.GetRangeBase() ||
 638            this->GetByteSize() != rhs.GetByteSize() || this->data != rhs.data;
 639   }
 640 };
 641
 642 template <typename B, typename S, typename T, unsigned N> class RangeDataArray {
 643 public:
 644   typedef RangeData<B, S, T> Entry;
 645   typedef llvm::SmallVector<Entry, N> Collection;
 646
 647   RangeDataArray() = default;
 648
 649   ~RangeDataArray() = default;
 650
 651   void Append(const Entry &entry) { m_entries.push_back(entry); }
 652
 653   void Sort() {
 654     if (m_entries.size() > 1)
 655       std::stable_sort(m_entries.begin(), m_entries.end());
 656   }
 657
 658 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 659   bool IsSorted() const {
 660     typename Collection::const_iterator pos, end, prev;
 661     // First we determine if we can combine any of the Entry objects so we
 662     // don't end up allocating and making a new collection for no reason
 663     for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end;
 664          prev = pos++) {
 665       if (prev != end && *pos < *prev)
 666         return false;
 667     }
 668     return true;
 669   }
 670 #endif
 671
 672   void CombineConsecutiveEntriesWithEqualData() {
 673 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 674     assert(IsSorted());
 675 #endif
 676     typename Collection::iterator pos;
 677     typename Collection::iterator end;
 678     typename Collection::iterator prev;
 679     bool can_combine = false;
 680     // First we determine if we can combine any of the Entry objects so we
 681     // don't end up allocating and making a new collection for no reason
 682     for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end;
 683          prev = pos++) {
 684       if (prev != end && prev->data == pos->data) {
 685         can_combine = true;
 686         break;
 687       }
 688     }
 689
 690     // We we can combine at least one entry, then we make a new collection and
 691     // populate it accordingly, and then swap it into place.
 692     if (can_combine) {
 693       Collection minimal_ranges;
 694       for (pos = m_entries.begin(), end = m_entries.end(), prev = end;
 695            pos != end; prev = pos++) {
 696         if (prev != end && prev->data == pos->data)
 697           minimal_ranges.back().SetRangeEnd(pos->GetRangeEnd());
 698         else
 699           minimal_ranges.push_back(*pos);
 700       }
 701       // Use the swap technique in case our new vector is much smaller. We must
 702       // swap when using the STL because std::vector objects never release or
 703       // reduce the memory once it has been allocated/reserved.
 704       m_entries.swap(minimal_ranges);
 705     }
 706   }
 707
 708   void Clear() { m_entries.clear(); }
 709
 710   bool IsEmpty() const { return m_entries.empty(); }
 711
 712   size_t GetSize() const { return m_entries.size(); }
 713
 714   const Entry *GetEntryAtIndex(size_t i) const {
 715     return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
 716   }
 717
 718   // Clients must ensure that "i" is a valid index prior to calling this
 719   // function
 720   const Entry &GetEntryRef(size_t i) const { return m_entries[i]; }
 721
 722   static bool BaseLessThan(const Entry &lhs, const Entry &rhs) {
 723     return lhs.GetRangeBase() < rhs.GetRangeBase();
 724   }
 725
 726   uint32_t FindEntryIndexThatContains(B addr) const {
 727 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 728     assert(IsSorted());
 729 #endif
 730     if (!m_entries.empty()) {
 731       Entry entry(addr, 1);
 732       typename Collection::const_iterator begin = m_entries.begin();
 733       typename Collection::const_iterator end = m_entries.end();
 734       typename Collection::const_iterator pos =
 735           std::lower_bound(begin, end, entry, BaseLessThan);
 736
 737       if (pos != end && pos->Contains(addr)) {
 738         return std::distance(begin, pos);
 739       } else if (pos != begin) {
 740         --pos;
 741         if (pos->Contains(addr))
 742           return std::distance(begin, pos);
 743       }
 744     }
 745     return UINT32_MAX;
 746   }
 747
 748   Entry *FindEntryThatContains(B addr) {
 749 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 750     assert(IsSorted());
 751 #endif
 752     if (!m_entries.empty()) {
 753       Entry entry;
 754       entry.SetRangeBase(addr);
 755       entry.SetByteSize(1);
 756       typename Collection::iterator begin = m_entries.begin();
 757       typename Collection::iterator end = m_entries.end();
 758       typename Collection::iterator pos =
 759           std::lower_bound(begin, end, entry, BaseLessThan);
 760
 761       if (pos != end && pos->Contains(addr)) {
 762         return &(*pos);
 763       } else if (pos != begin) {
 764         --pos;
 765         if (pos->Contains(addr)) {
 766           return &(*pos);
 767         }
 768       }
 769     }
 770     return nullptr;
 771   }
 772
 773   const Entry *FindEntryThatContains(B addr) const {
 774 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 775     assert(IsSorted());
 776 #endif
 777     if (!m_entries.empty()) {
 778       Entry entry;
 779       entry.SetRangeBase(addr);
 780       entry.SetByteSize(1);
 781       typename Collection::const_iterator begin = m_entries.begin();
 782       typename Collection::const_iterator end = m_entries.end();
 783       typename Collection::const_iterator pos =
 784           std::lower_bound(begin, end, entry, BaseLessThan);
 785
 786       if (pos != end && pos->Contains(addr)) {
 787         return &(*pos);
 788       } else if (pos != begin) {
 789         --pos;
 790         if (pos->Contains(addr)) {
 791           return &(*pos);
 792         }
 793       }
 794     }
 795     return nullptr;
 796   }
 797
 798   const Entry *FindEntryThatContains(const Entry &range) 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(begin, end, range, BaseLessThan);
 807
 808       if (pos != end && pos->Contains(range)) {
 809         return &(*pos);
 810       } else if (pos != begin) {
 811         --pos;
 812         if (pos->Contains(range)) {
 813           return &(*pos);
 814         }
 815       }
 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 // Same as RangeDataArray, but uses std::vector as to not require static
 831 // storage of N items in the class itself
 832 template <typename B, typename S, typename T> class RangeDataVector {
 833 public:
 834   typedef RangeData<B, S, T> Entry;
 835   typedef std::vector<Entry> Collection;
 836
 837   RangeDataVector() = default;
 838
 839   ~RangeDataVector() = default;
 840
 841   void Append(const Entry &entry) { m_entries.push_back(entry); }
 842
 843   void Sort() {
 844     if (m_entries.size() > 1)
 845       std::stable_sort(m_entries.begin(), m_entries.end());
 846   }
 847
 848 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 849   bool IsSorted() const {
 850     typename Collection::const_iterator pos, end, prev;
 851     // First we determine if we can combine any of the Entry objects so we
 852     // don't end up allocating and making a new collection for no reason
 853     for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end;
 854          prev = pos++) {
 855       if (prev != end && *pos < *prev)
 856         return false;
 857     }
 858     return true;
 859   }
 860 #endif
 861
 862   void CombineConsecutiveEntriesWithEqualData() {
 863 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 864     assert(IsSorted());
 865 #endif
 866     typename Collection::iterator pos;
 867     typename Collection::iterator end;
 868     typename Collection::iterator prev;
 869     bool can_combine = false;
 870     // First we determine if we can combine any of the Entry objects so we
 871     // don't end up allocating and making a new collection for no reason
 872     for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end;
 873          prev = pos++) {
 874       if (prev != end && prev->data == pos->data) {
 875         can_combine = true;
 876         break;
 877       }
 878     }
 879
 880     // We we can combine at least one entry, then we make a new collection and
 881     // populate it accordingly, and then swap it into place.
 882     if (can_combine) {
 883       Collection minimal_ranges;
 884       for (pos = m_entries.begin(), end = m_entries.end(), prev = end;
 885            pos != end; prev = pos++) {
 886         if (prev != end && prev->data == pos->data)
 887           minimal_ranges.back().SetRangeEnd(pos->GetRangeEnd());
 888         else
 889           minimal_ranges.push_back(*pos);
 890       }
 891       // Use the swap technique in case our new vector is much smaller. We must
 892       // swap when using the STL because std::vector objects never release or
 893       // reduce the memory once it has been allocated/reserved.
 894       m_entries.swap(minimal_ranges);
 895     }
 896   }
 897
 898   // Calculate the byte size of ranges with zero byte sizes by finding the next
 899   // entry with a base address > the current base address
 900   void CalculateSizesOfZeroByteSizeRanges(S full_size = 0) {
 901 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 902     assert(IsSorted());
 903 #endif
 904     typename Collection::iterator pos;
 905     typename Collection::iterator end;
 906     typename Collection::iterator next;
 907     for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos) {
 908       if (pos->GetByteSize() == 0) {
 909         // Watch out for multiple entries with same address and make sure we
 910         // find an entry that is greater than the current base address before
 911         // we use that for the size
 912         auto curr_base = pos->GetRangeBase();
 913         for (next = pos + 1; next != end; ++next) {
 914           auto next_base = next->GetRangeBase();
 915           if (next_base > curr_base) {
 916             pos->SetByteSize(next_base - curr_base);
 917             break;
 918           }
 919         }
 920         if (next == end && full_size > curr_base)
 921           pos->SetByteSize(full_size - curr_base);
 922       }
 923     }
 924   }
 925
 926   void Clear() { m_entries.clear(); }
 927
 928   void Reserve(typename Collection::size_type size) { m_entries.resize(size); }
 929
 930   bool IsEmpty() const { return m_entries.empty(); }
 931
 932   size_t GetSize() const { return m_entries.size(); }
 933
 934   const Entry *GetEntryAtIndex(size_t i) const {
 935     return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
 936   }
 937
 938   Entry *GetMutableEntryAtIndex(size_t i) {
 939     return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
 940   }
 941
 942   // Clients must ensure that "i" is a valid index prior to calling this
 943   // function
 944   const Entry &GetEntryRef(size_t i) const { return m_entries[i]; }
 945
 946   static bool BaseLessThan(const Entry &lhs, const Entry &rhs) {
 947     return lhs.GetRangeBase() < rhs.GetRangeBase();
 948   }
 949
 950   uint32_t FindEntryIndexThatContains(B addr) const {
 951 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 952     assert(IsSorted());
 953 #endif
 954     if (!m_entries.empty()) {
 955       Entry entry(addr, 1);
 956       typename Collection::const_iterator begin = m_entries.begin();
 957       typename Collection::const_iterator end = m_entries.end();
 958       typename Collection::const_iterator pos =
 959           std::lower_bound(begin, end, entry, BaseLessThan);
 960
 961       while (pos != begin && pos[-1].Contains(addr))
 962         --pos;
 963
 964       if (pos != end && pos->Contains(addr))
 965         return std::distance(begin, pos);
 966     }
 967     return UINT32_MAX;
 968   }
 969
 970   uint32_t FindEntryIndexesThatContain(B addr,
 971                                        std::vector<uint32_t> &indexes) const {
 972 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 973     assert(IsSorted());
 974 #endif
 975
 976     if (!m_entries.empty()) {
 977       for (const auto &entry : m_entries) {
 978         if (entry.Contains(addr))
 979           indexes.push_back(entry.data);
 980       }
 981     }
 982     return indexes.size();
 983   }
 984
 985   Entry *FindEntryThatContains(B addr) {
 986 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 987     assert(IsSorted());
 988 #endif
 989     if (!m_entries.empty()) {
 990       Entry entry;
 991       entry.SetRangeBase(addr);
 992       entry.SetByteSize(1);
 993       typename Collection::iterator begin = m_entries.begin();
 994       typename Collection::iterator end = m_entries.end();
 995       typename Collection::iterator pos =
 996           std::lower_bound(begin, end, entry, BaseLessThan);
 997
 998       while (pos != begin && pos[-1].Contains(addr))
 999         --pos;
1000
1001       if (pos != end && pos->Contains(addr))
1002         return &(*pos);
1003     }
1004     return nullptr;
1005   }
1006
1007   const Entry *FindEntryThatContains(B addr) const {
1008 #ifdef ASSERT_RANGEMAP_ARE_SORTED
1009     assert(IsSorted());
1010 #endif
1011     if (!m_entries.empty()) {
1012       Entry entry;
1013       entry.SetRangeBase(addr);
1014       entry.SetByteSize(1);
1015       typename Collection::const_iterator begin = m_entries.begin();
1016       typename Collection::const_iterator end = m_entries.end();
1017       typename Collection::const_iterator pos =
1018           std::lower_bound(begin, end, entry, BaseLessThan);
1019
1020       while (pos != begin && pos[-1].Contains(addr))
1021         --pos;
1022
1023       if (pos != end && pos->Contains(addr))
1024         return &(*pos);
1025     }
1026     return nullptr;
1027   }
1028
1029   const Entry *FindEntryThatContains(const Entry &range) const {
1030 #ifdef ASSERT_RANGEMAP_ARE_SORTED
1031     assert(IsSorted());
1032 #endif
1033     if (!m_entries.empty()) {
1034       typename Collection::const_iterator begin = m_entries.begin();
1035       typename Collection::const_iterator end = m_entries.end();
1036       typename Collection::const_iterator pos =
1037           std::lower_bound(begin, end, range, BaseLessThan);
1038
1039       while (pos != begin && pos[-1].Contains(range))
1040         --pos;
1041
1042       if (pos != end && pos->Contains(range))
1043         return &(*pos);
1044     }
1045     return nullptr;
1046   }
1047
1048   const Entry *FindEntryStartsAt(B addr) const {
1049 #ifdef ASSERT_RANGEMAP_ARE_SORTED
1050     assert(IsSorted());
1051 #endif
1052     if (!m_entries.empty()) {
1053       auto begin = m_entries.begin(), end = m_entries.end();
1054       auto pos = std::lower_bound(begin, end, Entry(addr, 1), BaseLessThan);
1055       if (pos != end && pos->base == addr)
1056         return &(*pos);
1057     }
1058     return nullptr;
1059   }
1060
1061   // This method will return the entry that contains the given address, or the
1062   // entry following that address.  If you give it an address of 0 and the
1063   // first entry starts at address 0x100, you will get the entry at 0x100.
1064   //
1065   // For most uses, FindEntryThatContains is the correct one to use, this is a
1066   // less commonly needed behavior.  It was added for core file memory regions,
1067   // where we want to present a gap in the memory regions as a distinct region,
1068   // so we need to know the start address of the next memory section that
1069   // exists.
1070   const Entry *FindEntryThatContainsOrFollows(B addr) const {
1071 #ifdef ASSERT_RANGEMAP_ARE_SORTED
1072     assert(IsSorted());
1073 #endif
1074     if (!m_entries.empty()) {
1075       typename Collection::const_iterator begin = m_entries.begin();
1076       typename Collection::const_iterator end = m_entries.end();
1077       typename Collection::const_iterator pos =
1078           std::lower_bound(m_entries.begin(), end, addr,
1079                            [](const Entry &lhs, B rhs_base) -> bool {
1080                              return lhs.GetRangeEnd() <= rhs_base;
1081                            });
1082
1083       while (pos != begin && pos[-1].Contains(addr))
1084         --pos;
1085
1086       if (pos != end)
1087         return &(*pos);
1088     }
1089     return nullptr;
1090   }
1091
1092   Entry *Back() { return (m_entries.empty() ? nullptr : &m_entries.back()); }
1093
1094   const Entry *Back() const {
1095     return (m_entries.empty() ? nullptr : &m_entries.back());
1096   }
1097
1098 protected:
1099   Collection m_entries;
1100 };
1101
1102 //----------------------------------------------------------------------
1103 // A simple range  with data class where you get to define the type of
1104 // the range base "B", the type used for the range byte size "S", and the type
1105 // for the associated data "T".
1106 //----------------------------------------------------------------------
1107 template <typename B, typename T> struct AddressData {
1108   typedef B BaseType;
1109   typedef T DataType;
1110
1111   BaseType addr;
1112   DataType data;
1113
1114   AddressData() : addr(), data() {}
1115
1116   AddressData(B a, DataType d) : addr(a), data(d) {}
1117
1118   bool operator<(const AddressData &rhs) const {
1119     if (this->addr == rhs.addr)
1120       return this->data < rhs.data;
1121     return this->addr < rhs.addr;
1122   }
1123
1124   bool operator==(const AddressData &rhs) const {
1125     return this->addr == rhs.addr && this->data == rhs.data;
1126   }
1127
1128   bool operator!=(const AddressData &rhs) const {
1129     return this->addr != rhs.addr || this->data == rhs.data;
1130   }
1131 };
1132
1133 template <typename B, typename T, unsigned N> class AddressDataArray {
1134 public:
1135   typedef AddressData<B, T> Entry;
1136   typedef llvm::SmallVector<Entry, N> Collection;
1137
1138   AddressDataArray() = default;
1139
1140   ~AddressDataArray() = default;
1141
1142   void Append(const Entry &entry) { m_entries.push_back(entry); }
1143
1144   void Sort() {
1145     if (m_entries.size() > 1)
1146       std::stable_sort(m_entries.begin(), m_entries.end());
1147   }
1148
1149 #ifdef ASSERT_RANGEMAP_ARE_SORTED
1150   bool IsSorted() const {
1151     typename Collection::const_iterator pos, end, prev;
1152     // First we determine if we can combine any of the Entry objects so we
1153     // don't end up allocating and making a new collection for no reason
1154     for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end;
1155          prev = pos++) {
1156       if (prev != end && *pos < *prev)
1157         return false;
1158     }
1159     return true;
1160   }
1161 #endif
1162
1163   void Clear() { m_entries.clear(); }
1164
1165   bool IsEmpty() const { return m_entries.empty(); }
1166
1167   size_t GetSize() const { return m_entries.size(); }
1168
1169   const Entry *GetEntryAtIndex(size_t i) const {
1170     return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
1171   }
1172
1173   // Clients must ensure that "i" is a valid index prior to calling this
1174   // function
1175   const Entry &GetEntryRef(size_t i) const { return m_entries[i]; }
1176
1177   static bool BaseLessThan(const Entry &lhs, const Entry &rhs) {
1178     return lhs.addr < rhs.addr;
1179   }
1180
1181   Entry *FindEntry(B addr, bool exact_match_only) {
1182 #ifdef ASSERT_RANGEMAP_ARE_SORTED
1183     assert(IsSorted());
1184 #endif
1185     if (!m_entries.empty()) {
1186       Entry entry;
1187       entry.addr = addr;
1188       typename Collection::iterator begin = m_entries.begin();
1189       typename Collection::iterator end = m_entries.end();
1190       typename Collection::iterator pos =
1191           std::lower_bound(begin, end, entry, BaseLessThan);
1192
1193       while (pos != begin && pos[-1].addr == addr)
1194         --pos;
1195
1196       if (pos != end) {
1197         if (pos->addr == addr || !exact_match_only)
1198           return &(*pos);
1199       }
1200     }
1201     return nullptr;
1202   }
1203
1204   const Entry *FindNextEntry(const Entry *entry) {
1205     if (entry >= &*m_entries.begin() && entry + 1 < &*m_entries.end())
1206       return entry + 1;
1207     return nullptr;
1208   }
1209
1210   Entry *Back() { return (m_entries.empty() ? nullptr : &m_entries.back()); }
1211
1212   const Entry *Back() const {
1213     return (m_entries.empty() ? nullptr : &m_entries.back());
1214   }
1215
1216 protected:
1217   Collection m_entries;
1218 };
1219
1220 } // namespace lldb_private
1221
1222 #endif // liblldb_RangeMap_h_