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