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>
  40     struct Range
  41     {
  42         typedef B BaseType;
  43         typedef S SizeType;
  44
  45         BaseType base;
  46         SizeType size;
  47
  48         Range () :
  49             base (0),
  50             size (0)
  51         {
  52         }
  53
  54         Range (BaseType b, SizeType s) :
  55             base (b),
  56             size (s)
  57         {
  58         }
  59
  60         void
  61         Clear (BaseType b = 0)
  62         {
  63             base = b;
  64             size = 0;
  65         }
  66
  67         // Set the start value for the range, and keep the same size
  68         BaseType
  69         GetRangeBase () const
  70         {
  71             return base;
  72         }
  73
  74         void
  75         SetRangeBase (BaseType b)
  76         {
  77             base = b;
  78         }
  79
  80         void
  81         Slide (BaseType slide)
  82         {
  83             base += slide;
  84         }
  85
  86         BaseType
  87         GetRangeEnd () const
  88         {
  89             return base + size;
  90         }
  91
  92         void
  93         SetRangeEnd (BaseType end)
  94         {
  95             if (end > base)
  96                 size = end - base;
  97             else
  98                 size = 0;
  99         }
 100
 101         SizeType
 102         GetByteSize () const
 103         {
 104             return size;
 105         }
 106
 107         void
 108         SetByteSize (SizeType s)
 109         {
 110             size = s;
 111         }
 112
 113         bool
 114         IsValid() const
 115         {
 116             return size > 0;
 117         }
 118
 119         bool
 120         Contains (BaseType r) const
 121         {
 122             return (GetRangeBase() <= r) && (r < GetRangeEnd());
 123         }
 124
 125         bool
 126         ContainsEndInclusive (BaseType r) const
 127         {
 128             return (GetRangeBase() <= r) && (r <= GetRangeEnd());
 129         }
 130
 131         bool
 132         Contains (const Range& range) const
 133         {
 134             return Contains(range.GetRangeBase()) && ContainsEndInclusive(range.GetRangeEnd());
 135         }
 136
 137         // Returns true if the two ranges adjoing or intersect
 138         bool
 139         DoesAdjoinOrIntersect (const Range &rhs) const
 140         {
 141             const BaseType lhs_base = this->GetRangeBase();
 142             const BaseType rhs_base = rhs.GetRangeBase();
 143             const BaseType lhs_end = this->GetRangeEnd();
 144             const BaseType rhs_end = rhs.GetRangeEnd();
 145             bool result = (lhs_base <= rhs_end) && (lhs_end >= rhs_base);
 146             return result;
 147         }
 148
 149         // Returns true if the two ranges intersect
 150         bool
 151         DoesIntersect (const Range &rhs) const
 152         {
 153             const BaseType lhs_base = this->GetRangeBase();
 154             const BaseType rhs_base = rhs.GetRangeBase();
 155             const BaseType lhs_end = this->GetRangeEnd();
 156             const BaseType rhs_end = rhs.GetRangeEnd();
 157             bool result = (lhs_base < rhs_end) && (lhs_end > rhs_base);
 158             return result;
 159         }
 160
 161         bool
 162         operator < (const Range &rhs) const
 163         {
 164             if (base == rhs.base)
 165                 return size < rhs.size;
 166             return base < rhs.base;
 167         }
 168
 169         bool
 170         operator == (const Range &rhs) const
 171         {
 172             return base == rhs.base && size == rhs.size;
 173         }
 174
 175         bool
 176         operator != (const Range &rhs) const
 177         {
 178             return  base != rhs.base || size != rhs.size;
 179         }
 180     };
 181
 182     //----------------------------------------------------------------------
 183     // A range array class where you get to define the type of the ranges
 184     // that the collection contains.
 185     //----------------------------------------------------------------------
 186
 187     template <typename B, typename S, unsigned N>
 188     class RangeArray
 189     {
 190     public:
 191         typedef B BaseType;
 192         typedef S SizeType;
 193         typedef Range<B,S> Entry;
 194         typedef llvm::SmallVector<Entry, N> Collection;
 195
 196         RangeArray() = default;
 197
 198         ~RangeArray() = default;
 199
 200         void
 201         Append (const Entry &entry)
 202         {
 203             m_entries.push_back (entry);
 204         }
 205
 206         void
 207         Append (B base, S size)
 208         {
 209             m_entries.emplace_back(base, size);
 210         }
 211
 212         bool
 213         RemoveEntrtAtIndex (uint32_t idx)
 214         {
 215             if (idx < m_entries.size())
 216             {
 217                 m_entries.erase (m_entries.begin() + idx);
 218                 return true;
 219             }
 220             return false;
 221         }
 222
 223         void
 224         Sort ()
 225         {
 226             if (m_entries.size() > 1)
 227                 std::stable_sort (m_entries.begin(), m_entries.end());
 228         }
 229
 230 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 231         bool
 232         IsSorted () const
 233         {
 234             typename Collection::const_iterator pos, end, prev;
 235             // First we determine if we can combine any of the Entry objects so we
 236             // don't end up allocating and making a new collection for no reason
 237             for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
 238             {
 239                 if (prev != end && *pos < *prev)
 240                     return false;
 241             }
 242             return true;
 243         }
 244 #endif
 245
 246         void
 247         CombineConsecutiveRanges ()
 248         {
 249 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 250             assert (IsSorted());
 251 #endif
 252             // Can't combine if ranges if we have zero or one range
 253             if (m_entries.size() > 1)
 254             {
 255                 // The list should be sorted prior to calling this function
 256                 typename Collection::iterator pos;
 257                 typename Collection::iterator end;
 258                 typename Collection::iterator prev;
 259                 bool can_combine = false;
 260                 // First we determine if we can combine any of the Entry objects so we
 261                 // don't end up allocating and making a new collection for no reason
 262                 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
 263                 {
 264                     if (prev != end && prev->DoesAdjoinOrIntersect(*pos))
 265                     {
 266                         can_combine = true;
 267                         break;
 268                     }
 269                 }
 270
 271                 // We we can combine at least one entry, then we make a new collection
 272                 // and populate it accordingly, and then swap it into place.
 273                 if (can_combine)
 274                 {
 275                     Collection minimal_ranges;
 276                     for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
 277                     {
 278                         if (prev != end && prev->DoesAdjoinOrIntersect(*pos))
 279                             minimal_ranges.back().SetRangeEnd (std::max<BaseType>(prev->GetRangeEnd(), pos->GetRangeEnd()));
 280                         else
 281                             minimal_ranges.push_back (*pos);
 282                     }
 283                     // Use the swap technique in case our new vector is much smaller.
 284                     // We must swap when using the STL because std::vector objects never
 285                     // release or reduce the memory once it has been allocated/reserved.
 286                     m_entries.swap (minimal_ranges);
 287                 }
 288             }
 289         }
 290
 291         BaseType
 292         GetMinRangeBase (BaseType fail_value) const
 293         {
 294 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 295             assert (IsSorted());
 296 #endif
 297             if (m_entries.empty())
 298                 return fail_value;
 299             // m_entries must be sorted, so if we aren't empty, we grab the
 300             // first range's base
 301             return m_entries.front().GetRangeBase();
 302         }
 303
 304         BaseType
 305         GetMaxRangeEnd (BaseType fail_value) const
 306         {
 307 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 308             assert (IsSorted());
 309 #endif
 310             if (m_entries.empty())
 311                 return fail_value;
 312             // m_entries must be sorted, so if we aren't empty, we grab the
 313             // last range's end
 314             return m_entries.back().GetRangeEnd();
 315         }
 316
 317         void
 318         Slide (BaseType slide)
 319         {
 320             typename Collection::iterator pos, end;
 321             for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos)
 322                 pos->Slide (slide);
 323         }
 324
 325         void
 326         Clear ()
 327         {
 328             m_entries.clear();
 329         }
 330
 331         bool
 332         IsEmpty () const
 333         {
 334             return m_entries.empty();
 335         }
 336
 337         size_t
 338         GetSize () const
 339         {
 340             return m_entries.size();
 341         }
 342
 343         const Entry *
 344         GetEntryAtIndex (size_t i) const
 345         {
 346             return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
 347         }
 348
 349         // Clients must ensure that "i" is a valid index prior to calling this function
 350         const Entry &
 351         GetEntryRef (size_t i) const
 352         {
 353             return m_entries[i];
 354         }
 355
 356         Entry *
 357         Back()
 358         {
 359             return (m_entries.empty() ? nullptr : &m_entries.back());
 360         }
 361
 362         const Entry *
 363         Back() const
 364         {
 365             return (m_entries.empty() ? nullptr : &m_entries.back());
 366         }
 367
 368         static bool
 369         BaseLessThan (const Entry& lhs, const Entry& rhs)
 370         {
 371             return lhs.GetRangeBase() < rhs.GetRangeBase();
 372         }
 373
 374         uint32_t
 375         FindEntryIndexThatContains (B addr) const
 376         {
 377 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 378             assert (IsSorted());
 379 #endif
 380             if (!m_entries.empty())
 381             {
 382                 Entry entry (addr, 1);
 383                 typename Collection::const_iterator begin = m_entries.begin();
 384                 typename Collection::const_iterator end = m_entries.end();
 385                 typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
 386
 387                 if (pos != end && pos->Contains(addr))
 388                 {
 389                     return std::distance (begin, pos);
 390                 }
 391                 else if (pos != begin)
 392                 {
 393                     --pos;
 394                     if (pos->Contains(addr))
 395                         return std::distance (begin, pos);
 396                 }
 397             }
 398             return UINT32_MAX;
 399         }
 400
 401         const Entry *
 402         FindEntryThatContains (B addr) const
 403         {
 404 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 405             assert (IsSorted());
 406 #endif
 407             if (!m_entries.empty())
 408             {
 409                 Entry entry (addr, 1);
 410                 typename Collection::const_iterator begin = m_entries.begin();
 411                 typename Collection::const_iterator end = m_entries.end();
 412                 typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
 413
 414                 if (pos != end && pos->Contains(addr))
 415                 {
 416                     return &(*pos);
 417                 }
 418                 else if (pos != begin)
 419                 {
 420                     --pos;
 421                     if (pos->Contains(addr))
 422                     {
 423                         return &(*pos);
 424                     }
 425                 }
 426             }
 427             return nullptr;
 428         }
 429
 430         const Entry *
 431         FindEntryThatContains (const Entry &range) const
 432         {
 433 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 434             assert (IsSorted());
 435 #endif
 436             if (!m_entries.empty())
 437             {
 438                 typename Collection::const_iterator begin = m_entries.begin();
 439                 typename Collection::const_iterator end = m_entries.end();
 440                 typename Collection::const_iterator pos = std::lower_bound (begin, end, range, BaseLessThan);
 441
 442                 if (pos != end && pos->Contains(range))
 443                 {
 444                     return &(*pos);
 445                 }
 446                 else if (pos != begin)
 447                 {
 448                     --pos;
 449                     if (pos->Contains(range))
 450                     {
 451                         return &(*pos);
 452                     }
 453                 }
 454             }
 455             return nullptr;
 456         }
 457
 458     protected:
 459         Collection m_entries;
 460     };
 461
 462     template <typename B, typename S>
 463     class RangeVector
 464     {
 465     public:
 466         typedef B BaseType;
 467         typedef S SizeType;
 468         typedef Range<B,S> Entry;
 469         typedef std::vector<Entry> Collection;
 470
 471         RangeVector() = default;
 472
 473         ~RangeVector() = default;
 474
 475         void
 476         Append (const Entry &entry)
 477         {
 478             m_entries.push_back (entry);
 479         }
 480
 481         void
 482         Append (B base, S size)
 483         {
 484             m_entries.emplace_back(base, size);
 485         }
 486
 487         bool
 488         RemoveEntrtAtIndex (uint32_t idx)
 489         {
 490             if (idx < m_entries.size())
 491             {
 492                 m_entries.erase (m_entries.begin() + idx);
 493                 return true;
 494             }
 495             return false;
 496         }
 497
 498         void
 499         Sort ()
 500         {
 501             if (m_entries.size() > 1)
 502                 std::stable_sort (m_entries.begin(), m_entries.end());
 503         }
 504
 505 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 506         bool
 507         IsSorted () const
 508         {
 509             typename Collection::const_iterator pos, end, prev;
 510             // First we determine if we can combine any of the Entry objects so we
 511             // don't end up allocating and making a new collection for no reason
 512             for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
 513             {
 514                 if (prev != end && *pos < *prev)
 515                     return false;
 516             }
 517             return true;
 518         }
 519 #endif
 520
 521         void
 522         CombineConsecutiveRanges ()
 523         {
 524 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 525             assert (IsSorted());
 526 #endif
 527             // Can't combine if ranges if we have zero or one range
 528             if (m_entries.size() > 1)
 529             {
 530                 // The list should be sorted prior to calling this function
 531                 typename Collection::iterator pos;
 532                 typename Collection::iterator end;
 533                 typename Collection::iterator prev;
 534                 bool can_combine = false;
 535                 // First we determine if we can combine any of the Entry objects so we
 536                 // don't end up allocating and making a new collection for no reason
 537                 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
 538                 {
 539                     if (prev != end && prev->DoesAdjoinOrIntersect(*pos))
 540                     {
 541                         can_combine = true;
 542                         break;
 543                     }
 544                 }
 545
 546                 // We we can combine at least one entry, then we make a new collection
 547                 // and populate it accordingly, and then swap it into place.
 548                 if (can_combine)
 549                 {
 550                     Collection minimal_ranges;
 551                     for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
 552                     {
 553                         if (prev != end && prev->DoesAdjoinOrIntersect(*pos))
 554                             minimal_ranges.back().SetRangeEnd (std::max<BaseType>(prev->GetRangeEnd(), pos->GetRangeEnd()));
 555                         else
 556                             minimal_ranges.push_back (*pos);
 557                     }
 558                     // Use the swap technique in case our new vector is much smaller.
 559                     // We must swap when using the STL because std::vector objects never
 560                     // release or reduce the memory once it has been allocated/reserved.
 561                     m_entries.swap (minimal_ranges);
 562                 }
 563             }
 564         }
 565
 566         BaseType
 567         GetMinRangeBase (BaseType fail_value) const
 568         {
 569 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 570             assert (IsSorted());
 571 #endif
 572             if (m_entries.empty())
 573                 return fail_value;
 574             // m_entries must be sorted, so if we aren't empty, we grab the
 575             // first range's base
 576             return m_entries.front().GetRangeBase();
 577         }
 578
 579         BaseType
 580         GetMaxRangeEnd (BaseType fail_value) const
 581         {
 582 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 583             assert (IsSorted());
 584 #endif
 585             if (m_entries.empty())
 586                 return fail_value;
 587             // m_entries must be sorted, so if we aren't empty, we grab the
 588             // last range's end
 589             return m_entries.back().GetRangeEnd();
 590         }
 591
 592         void
 593         Slide (BaseType slide)
 594         {
 595             typename Collection::iterator pos, end;
 596             for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos)
 597                 pos->Slide (slide);
 598         }
 599
 600         void
 601         Clear ()
 602         {
 603             m_entries.clear();
 604         }
 605
 606         void
 607         Reserve (typename Collection::size_type size)
 608         {
 609             m_entries.reserve (size);
 610         }
 611
 612         bool
 613         IsEmpty () const
 614         {
 615             return m_entries.empty();
 616         }
 617
 618         size_t
 619         GetSize () const
 620         {
 621             return m_entries.size();
 622         }
 623
 624         const Entry *
 625         GetEntryAtIndex (size_t i) const
 626         {
 627             return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
 628         }
 629
 630         // Clients must ensure that "i" is a valid index prior to calling this function
 631         const Entry &
 632         GetEntryRef (size_t i) const
 633         {
 634             return m_entries[i];
 635         }
 636
 637         Entry *
 638         Back()
 639         {
 640             return (m_entries.empty() ? nullptr : &m_entries.back());
 641         }
 642
 643         const Entry *
 644         Back() const
 645         {
 646             return (m_entries.empty() ? nullptr : &m_entries.back());
 647         }
 648
 649         static bool
 650         BaseLessThan (const Entry& lhs, const Entry& rhs)
 651         {
 652             return lhs.GetRangeBase() < rhs.GetRangeBase();
 653         }
 654
 655         uint32_t
 656         FindEntryIndexThatContains (B addr) const
 657         {
 658 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 659             assert (IsSorted());
 660 #endif
 661             if (!m_entries.empty())
 662             {
 663                 Entry entry (addr, 1);
 664                 typename Collection::const_iterator begin = m_entries.begin();
 665                 typename Collection::const_iterator end = m_entries.end();
 666                 typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
 667
 668                 if (pos != end && pos->Contains(addr))
 669                 {
 670                     return std::distance (begin, pos);
 671                 }
 672                 else if (pos != begin)
 673                 {
 674                     --pos;
 675                     if (pos->Contains(addr))
 676                         return std::distance (begin, pos);
 677                 }
 678             }
 679             return UINT32_MAX;
 680         }
 681
 682         const Entry *
 683         FindEntryThatContains (B addr) const
 684         {
 685 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 686             assert (IsSorted());
 687 #endif
 688             if (!m_entries.empty())
 689             {
 690                 Entry entry (addr, 1);
 691                 typename Collection::const_iterator begin = m_entries.begin();
 692                 typename Collection::const_iterator end = m_entries.end();
 693                 typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
 694
 695                 if (pos != end && pos->Contains(addr))
 696                 {
 697                     return &(*pos);
 698                 }
 699                 else if (pos != begin)
 700                 {
 701                     --pos;
 702                     if (pos->Contains(addr))
 703                     {
 704                         return &(*pos);
 705                     }
 706                 }
 707             }
 708             return nullptr;
 709         }
 710
 711         const Entry *
 712         FindEntryThatContains (const Entry &range) const
 713         {
 714 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 715             assert (IsSorted());
 716 #endif
 717             if (!m_entries.empty())
 718             {
 719                 typename Collection::const_iterator begin = m_entries.begin();
 720                 typename Collection::const_iterator end = m_entries.end();
 721                 typename Collection::const_iterator pos = std::lower_bound (begin, end, range, BaseLessThan);
 722
 723                 if (pos != end && pos->Contains(range))
 724                 {
 725                     return &(*pos);
 726                 }
 727                 else if (pos != begin)
 728                 {
 729                     --pos;
 730                     if (pos->Contains(range))
 731                     {
 732                         return &(*pos);
 733                     }
 734                 }
 735             }
 736             return nullptr;
 737         }
 738
 739     protected:
 740         Collection m_entries;
 741     };
 742
 743     //----------------------------------------------------------------------
 744     // A simple range  with data class where you get to define the type of
 745     // the range base "B", the type used for the range byte size "S", and
 746     // the type for the associated data "T".
 747     //----------------------------------------------------------------------
 748     template <typename B, typename S, typename T>
 749     struct RangeData : public Range<B,S>
 750     {
 751         typedef T DataType;
 752
 753         DataType data;
 754
 755         RangeData () :
 756             Range<B,S> (),
 757             data ()
 758         {
 759         }
 760
 761         RangeData (B base, S size) :
 762             Range<B,S> (base, size),
 763             data ()
 764         {
 765         }
 766
 767         RangeData (B base, S size, DataType d) :
 768             Range<B,S> (base, size),
 769             data (d)
 770         {
 771         }
 772
 773         bool
 774         operator < (const RangeData &rhs) const
 775         {
 776             if (this->base == rhs.base)
 777             {
 778                 if (this->size == rhs.size)
 779                     return this->data < rhs.data;
 780                 else
 781                     return this->size < rhs.size;
 782             }
 783             return this->base < rhs.base;
 784         }
 785
 786         bool
 787         operator == (const RangeData &rhs) const
 788         {
 789             return this->GetRangeBase() == rhs.GetRangeBase() &&
 790                    this->GetByteSize() == rhs.GetByteSize() &&
 791                    this->data      == rhs.data;
 792         }
 793
 794         bool
 795         operator != (const RangeData &rhs) const
 796         {
 797             return this->GetRangeBase() != rhs.GetRangeBase() ||
 798                    this->GetByteSize() != rhs.GetByteSize() ||
 799                    this->data      != rhs.data;
 800         }
 801     };
 802
 803     template <typename B, typename S, typename T, unsigned N>
 804     class RangeDataArray
 805     {
 806     public:
 807         typedef RangeData<B,S,T> Entry;
 808         typedef llvm::SmallVector<Entry, N> Collection;
 809
 810         RangeDataArray() = default;
 811
 812         ~RangeDataArray() = default;
 813
 814         void
 815         Append (const Entry &entry)
 816         {
 817             m_entries.push_back (entry);
 818         }
 819
 820         void
 821         Sort ()
 822         {
 823             if (m_entries.size() > 1)
 824                 std::stable_sort (m_entries.begin(), m_entries.end());
 825         }
 826
 827 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 828         bool
 829         IsSorted () const
 830         {
 831             typename Collection::const_iterator pos, end, prev;
 832             // First we determine if we can combine any of the Entry objects so we
 833             // don't end up allocating and making a new collection for no reason
 834             for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
 835             {
 836                 if (prev != end && *pos < *prev)
 837                     return false;
 838             }
 839             return true;
 840         }
 841 #endif
 842
 843         void
 844         CombineConsecutiveEntriesWithEqualData ()
 845         {
 846 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 847             assert (IsSorted());
 848 #endif
 849             typename Collection::iterator pos;
 850             typename Collection::iterator end;
 851             typename Collection::iterator prev;
 852             bool can_combine = false;
 853             // First we determine if we can combine any of the Entry objects so we
 854             // don't end up allocating and making a new collection for no reason
 855             for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
 856             {
 857                 if (prev != end && prev->data == pos->data)
 858                 {
 859                     can_combine = true;
 860                     break;
 861                 }
 862             }
 863
 864             // We we can combine at least one entry, then we make a new collection
 865             // and populate it accordingly, and then swap it into place.
 866             if (can_combine)
 867             {
 868                 Collection minimal_ranges;
 869                 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
 870                 {
 871                     if (prev != end && prev->data == pos->data)
 872                         minimal_ranges.back().SetRangeEnd (pos->GetRangeEnd());
 873                     else
 874                         minimal_ranges.push_back (*pos);
 875                 }
 876                 // Use the swap technique in case our new vector is much smaller.
 877                 // We must swap when using the STL because std::vector objects never
 878                 // release or reduce the memory once it has been allocated/reserved.
 879                 m_entries.swap (minimal_ranges);
 880             }
 881         }
 882
 883         void
 884         Clear ()
 885         {
 886             m_entries.clear();
 887         }
 888
 889         bool
 890         IsEmpty () const
 891         {
 892             return m_entries.empty();
 893         }
 894
 895         size_t
 896         GetSize () const
 897         {
 898             return m_entries.size();
 899         }
 900
 901         const Entry *
 902         GetEntryAtIndex (size_t i) const
 903         {
 904             return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
 905         }
 906
 907         // Clients must ensure that "i" is a valid index prior to calling this function
 908         const Entry &
 909         GetEntryRef (size_t i) const
 910         {
 911             return m_entries[i];
 912         }
 913
 914         static bool
 915         BaseLessThan (const Entry& lhs, const Entry& rhs)
 916         {
 917             return lhs.GetRangeBase() < rhs.GetRangeBase();
 918         }
 919
 920         uint32_t
 921         FindEntryIndexThatContains (B addr) const
 922         {
 923 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 924             assert (IsSorted());
 925 #endif
 926             if ( !m_entries.empty() )
 927             {
 928                 Entry entry (addr, 1);
 929                 typename Collection::const_iterator begin = m_entries.begin();
 930                 typename Collection::const_iterator end = m_entries.end();
 931                 typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
 932
 933                 if (pos != end && pos->Contains(addr))
 934                 {
 935                     return std::distance (begin, pos);
 936                 }
 937                 else if (pos != begin)
 938                 {
 939                     --pos;
 940                     if (pos->Contains(addr))
 941                         return std::distance (begin, pos);
 942                 }
 943             }
 944             return UINT32_MAX;
 945         }
 946
 947         Entry *
 948         FindEntryThatContains (B addr)
 949         {
 950 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 951             assert (IsSorted());
 952 #endif
 953             if ( !m_entries.empty() )
 954             {
 955                 Entry entry;
 956                 entry.SetRangeBase(addr);
 957                 entry.SetByteSize(1);
 958                 typename Collection::iterator begin = m_entries.begin();
 959                 typename Collection::iterator end = m_entries.end();
 960                 typename Collection::iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
 961
 962                 if (pos != end && pos->Contains(addr))
 963                 {
 964                     return &(*pos);
 965                 }
 966                 else if (pos != begin)
 967                 {
 968                     --pos;
 969                     if (pos->Contains(addr))
 970                     {
 971                         return &(*pos);
 972                     }
 973                 }
 974             }
 975             return nullptr;
 976         }
 977
 978         const Entry *
 979         FindEntryThatContains (B addr) const
 980         {
 981 #ifdef ASSERT_RANGEMAP_ARE_SORTED
 982             assert (IsSorted());
 983 #endif
 984             if ( !m_entries.empty() )
 985             {
 986                 Entry entry;
 987                 entry.SetRangeBase(addr);
 988                 entry.SetByteSize(1);
 989                 typename Collection::const_iterator begin = m_entries.begin();
 990                 typename Collection::const_iterator end = m_entries.end();
 991                 typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
 992
 993                 if (pos != end && pos->Contains(addr))
 994                 {
 995                     return &(*pos);
 996                 }
 997                 else if (pos != begin)
 998                 {
 999                     --pos;
1000                     if (pos->Contains(addr))
1001                     {
1002                         return &(*pos);
1003                     }
1004                 }
1005             }
1006             return nullptr;
1007         }
1008
1009         const Entry *
1010         FindEntryThatContains (const Entry &range) const
1011         {
1012 #ifdef ASSERT_RANGEMAP_ARE_SORTED
1013             assert (IsSorted());
1014 #endif
1015             if ( !m_entries.empty() )
1016             {
1017                 typename Collection::const_iterator begin = m_entries.begin();
1018                 typename Collection::const_iterator end = m_entries.end();
1019                 typename Collection::const_iterator pos = std::lower_bound (begin, end, range, BaseLessThan);
1020
1021                 if (pos != end && pos->Contains(range))
1022                 {
1023                     return &(*pos);
1024                 }
1025                 else if (pos != begin)
1026                 {
1027                     --pos;
1028                     if (pos->Contains(range))
1029                     {
1030                         return &(*pos);
1031                     }
1032                 }
1033             }
1034             return nullptr;
1035         }
1036
1037         Entry *
1038         Back()
1039         {
1040             return (m_entries.empty() ? nullptr : &m_entries.back());
1041         }
1042
1043         const Entry *
1044         Back() const
1045         {
1046             return (m_entries.empty() ? nullptr : &m_entries.back());
1047         }
1048
1049     protected:
1050         Collection m_entries;
1051     };
1052
1053     // Same as RangeDataArray, but uses std::vector as to not
1054     // require static storage of N items in the class itself
1055     template <typename B, typename S, typename T>
1056     class RangeDataVector
1057     {
1058     public:
1059         typedef RangeData<B,S,T> Entry;
1060         typedef std::vector<Entry> Collection;
1061
1062         RangeDataVector() = default;
1063
1064         ~RangeDataVector() = default;
1065
1066         void
1067         Append (const Entry &entry)
1068         {
1069             m_entries.push_back (entry);
1070         }
1071
1072         void
1073         Sort ()
1074         {
1075             if (m_entries.size() > 1)
1076                 std::stable_sort (m_entries.begin(), m_entries.end());
1077         }
1078
1079 #ifdef ASSERT_RANGEMAP_ARE_SORTED
1080         bool
1081         IsSorted () const
1082         {
1083             typename Collection::const_iterator pos, end, prev;
1084             // First we determine if we can combine any of the Entry objects so we
1085             // don't end up allocating and making a new collection for no reason
1086             for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
1087             {
1088                 if (prev != end && *pos < *prev)
1089                     return false;
1090             }
1091             return true;
1092         }
1093 #endif
1094
1095         void
1096         CombineConsecutiveEntriesWithEqualData ()
1097         {
1098 #ifdef ASSERT_RANGEMAP_ARE_SORTED
1099             assert (IsSorted());
1100 #endif
1101             typename Collection::iterator pos;
1102             typename Collection::iterator end;
1103             typename Collection::iterator prev;
1104             bool can_combine = false;
1105             // First we determine if we can combine any of the Entry objects so we
1106             // don't end up allocating and making a new collection for no reason
1107             for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
1108             {
1109                 if (prev != end && prev->data == pos->data)
1110                 {
1111                     can_combine = true;
1112                     break;
1113                 }
1114             }
1115
1116             // We we can combine at least one entry, then we make a new collection
1117             // and populate it accordingly, and then swap it into place.
1118             if (can_combine)
1119             {
1120                 Collection minimal_ranges;
1121                 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
1122                 {
1123                     if (prev != end && prev->data == pos->data)
1124                         minimal_ranges.back().SetRangeEnd (pos->GetRangeEnd());
1125                     else
1126                         minimal_ranges.push_back (*pos);
1127                 }
1128                 // Use the swap technique in case our new vector is much smaller.
1129                 // We must swap when using the STL because std::vector objects never
1130                 // release or reduce the memory once it has been allocated/reserved.
1131                 m_entries.swap (minimal_ranges);
1132             }
1133         }
1134
1135         // Calculate the byte size of ranges with zero byte sizes by finding
1136         // the next entry with a base address > the current base address
1137         void
1138         CalculateSizesOfZeroByteSizeRanges (S full_size = 0)
1139         {
1140 #ifdef ASSERT_RANGEMAP_ARE_SORTED
1141             assert (IsSorted());
1142 #endif
1143             typename Collection::iterator pos;
1144             typename Collection::iterator end;
1145             typename Collection::iterator next;
1146             for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos)
1147             {
1148                 if (pos->GetByteSize() == 0)
1149                 {
1150                     // Watch out for multiple entries with same address and make sure
1151                     // we find an entry that is greater than the current base address
1152                     // before we use that for the size
1153                     auto curr_base = pos->GetRangeBase();
1154                     for (next = pos + 1; next != end; ++next)
1155                     {
1156                         auto next_base = next->GetRangeBase();
1157                         if (next_base > curr_base)
1158                         {
1159                             pos->SetByteSize (next_base - curr_base);
1160                             break;
1161                         }
1162                     }
1163                     if (next == end && full_size > curr_base)
1164                         pos->SetByteSize (full_size - curr_base);
1165                 }
1166             }
1167         }
1168
1169         void
1170         Clear ()
1171         {
1172             m_entries.clear();
1173         }
1174
1175         void
1176         Reserve (typename Collection::size_type size)
1177         {
1178             m_entries.resize (size);
1179         }
1180
1181         bool
1182         IsEmpty () const
1183         {
1184             return m_entries.empty();
1185         }
1186
1187         size_t
1188         GetSize () const
1189         {
1190             return m_entries.size();
1191         }
1192
1193         const Entry *
1194         GetEntryAtIndex (size_t i) const
1195         {
1196             return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
1197         }
1198
1199         Entry *
1200         GetMutableEntryAtIndex (size_t i)
1201         {
1202             return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
1203         }
1204
1205         // Clients must ensure that "i" is a valid index prior to calling this function
1206         const Entry &
1207         GetEntryRef (size_t i) const
1208         {
1209             return m_entries[i];
1210         }
1211
1212         static bool
1213         BaseLessThan (const Entry& lhs, const Entry& rhs)
1214         {
1215             return lhs.GetRangeBase() < rhs.GetRangeBase();
1216         }
1217
1218         uint32_t
1219         FindEntryIndexThatContains (B addr) const
1220         {
1221 #ifdef ASSERT_RANGEMAP_ARE_SORTED
1222             assert (IsSorted());
1223 #endif
1224             if ( !m_entries.empty() )
1225             {
1226                 Entry entry (addr, 1);
1227                 typename Collection::const_iterator begin = m_entries.begin();
1228                 typename Collection::const_iterator end = m_entries.end();
1229                 typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
1230
1231                 while(pos != begin && pos[-1].Contains(addr))
1232                     --pos;
1233
1234                 if (pos != end && pos->Contains(addr))
1235                     return std::distance (begin, pos);
1236             }
1237             return UINT32_MAX;
1238         }
1239
1240         uint32_t
1241         FindEntryIndexesThatContain(B addr, std::vector<uint32_t> &indexes) const
1242         {
1243 #ifdef ASSERT_RANGEMAP_ARE_SORTED
1244             assert (IsSorted());
1245 #endif
1246
1247             if (!m_entries.empty())
1248             {
1249                 typename Collection::const_iterator pos;
1250                 for (const auto &entry : m_entries)
1251                 {
1252                     if (entry.Contains(addr))
1253                         indexes.push_back(entry.data);
1254                 }
1255             }
1256             return indexes.size() ;
1257         }
1258
1259         Entry *
1260         FindEntryThatContains (B addr)
1261         {
1262 #ifdef ASSERT_RANGEMAP_ARE_SORTED
1263             assert (IsSorted());
1264 #endif
1265             if ( !m_entries.empty() )
1266             {
1267                 Entry entry;
1268                 entry.SetRangeBase(addr);
1269                 entry.SetByteSize(1);
1270                 typename Collection::iterator begin = m_entries.begin();
1271                 typename Collection::iterator end = m_entries.end();
1272                 typename Collection::iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
1273
1274                 while(pos != begin && pos[-1].Contains(addr))
1275                     --pos;
1276
1277                 if (pos != end && pos->Contains(addr))
1278                     return &(*pos);
1279             }
1280             return nullptr;
1281         }
1282
1283         const Entry *
1284         FindEntryThatContains (B addr) const
1285         {
1286 #ifdef ASSERT_RANGEMAP_ARE_SORTED
1287             assert (IsSorted());
1288 #endif
1289             if ( !m_entries.empty() )
1290             {
1291                 Entry entry;
1292                 entry.SetRangeBase(addr);
1293                 entry.SetByteSize(1);
1294                 typename Collection::const_iterator begin = m_entries.begin();
1295                 typename Collection::const_iterator end = m_entries.end();
1296                 typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
1297
1298                 while(pos != begin && pos[-1].Contains(addr))
1299                     --pos;
1300
1301                 if (pos != end && pos->Contains(addr))
1302                     return &(*pos);
1303             }
1304             return nullptr;
1305         }
1306
1307         const Entry *
1308         FindEntryThatContains (const Entry &range) const
1309         {
1310 #ifdef ASSERT_RANGEMAP_ARE_SORTED
1311             assert (IsSorted());
1312 #endif
1313             if ( !m_entries.empty() )
1314             {
1315                 typename Collection::const_iterator begin = m_entries.begin();
1316                 typename Collection::const_iterator end = m_entries.end();
1317                 typename Collection::const_iterator pos = std::lower_bound (begin, end, range, BaseLessThan);
1318
1319                 while(pos != begin && pos[-1].Contains(range))
1320                     --pos;
1321
1322                 if (pos != end && pos->Contains(range))
1323                     return &(*pos);
1324             }
1325             return nullptr;
1326         }
1327
1328         const Entry*
1329         FindEntryStartsAt (B addr) const
1330         {
1331 #ifdef ASSERT_RANGEMAP_ARE_SORTED
1332             assert (IsSorted());
1333 #endif
1334             if (!m_entries.empty())
1335             {
1336                 auto begin = m_entries.begin(), end = m_entries.end();
1337                 auto pos = std::lower_bound (begin, end, Entry(addr, 1), BaseLessThan);
1338                 if (pos != end && pos->base == addr)
1339                     return &(*pos);
1340             }
1341             return nullptr;
1342         }
1343
1344         const Entry *
1345         FindEntryThatContainsOrFollows(B addr) const
1346         {
1347 #ifdef ASSERT_RANGEMAP_ARE_SORTED
1348             assert(IsSorted());
1349 #endif
1350             if (!m_entries.empty())
1351             {
1352                 typename Collection::const_iterator end = m_entries.end();
1353                 typename Collection::const_iterator pos =
1354                     std::lower_bound(m_entries.begin(), end, addr, [](const Entry &lhs, B rhs_base) -> bool {
1355                         return lhs.GetRangeEnd() <= rhs_base;
1356                     });
1357
1358                 if (pos != end)
1359                     return &(*pos);
1360             }
1361             return nullptr;
1362         }
1363
1364         Entry *
1365         Back()
1366         {
1367             return (m_entries.empty() ? nullptr : &m_entries.back());
1368         }
1369
1370         const Entry *
1371         Back() const
1372         {
1373             return (m_entries.empty() ? nullptr : &m_entries.back());
1374         }
1375
1376     protected:
1377         Collection m_entries;
1378     };
1379
1380     //----------------------------------------------------------------------
1381     // A simple range  with data class where you get to define the type of
1382     // the range base "B", the type used for the range byte size "S", and
1383     // the type for the associated data "T".
1384     //----------------------------------------------------------------------
1385     template <typename B, typename T>
1386     struct AddressData
1387     {
1388         typedef B BaseType;
1389         typedef T DataType;
1390
1391         BaseType addr;
1392         DataType data;
1393
1394         AddressData () :
1395             addr (),
1396             data ()
1397         {
1398         }
1399
1400         AddressData (B a, DataType d) :
1401             addr (a),
1402             data (d)
1403         {
1404         }
1405
1406         bool
1407         operator < (const AddressData &rhs) const
1408         {
1409             if (this->addr == rhs.addr)
1410                 return this->data < rhs.data;
1411             return this->addr < rhs.addr;
1412         }
1413
1414         bool
1415         operator == (const AddressData &rhs) const
1416         {
1417             return this->addr == rhs.addr &&
1418                    this->data == rhs.data;
1419         }
1420
1421         bool
1422         operator != (const AddressData &rhs) const
1423         {
1424             return this->addr != rhs.addr ||
1425                    this->data == rhs.data;
1426         }
1427     };
1428
1429     template <typename B, typename T, unsigned N>
1430     class AddressDataArray
1431     {
1432     public:
1433         typedef AddressData<B,T> Entry;
1434         typedef llvm::SmallVector<Entry, N> Collection;
1435
1436         AddressDataArray() = default;
1437
1438         ~AddressDataArray() = default;
1439
1440         void
1441         Append (const Entry &entry)
1442         {
1443             m_entries.push_back (entry);
1444         }
1445
1446         void
1447         Sort ()
1448         {
1449             if (m_entries.size() > 1)
1450                 std::stable_sort (m_entries.begin(), m_entries.end());
1451         }
1452
1453 #ifdef ASSERT_RANGEMAP_ARE_SORTED
1454         bool
1455         IsSorted () const
1456         {
1457             typename Collection::const_iterator pos, end, prev;
1458             // First we determine if we can combine any of the Entry objects so we
1459             // don't end up allocating and making a new collection for no reason
1460             for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++)
1461             {
1462                 if (prev != end && *pos < *prev)
1463                     return false;
1464             }
1465             return true;
1466         }
1467 #endif
1468
1469         void
1470         Clear ()
1471         {
1472             m_entries.clear();
1473         }
1474
1475         bool
1476         IsEmpty () const
1477         {
1478             return m_entries.empty();
1479         }
1480
1481         size_t
1482         GetSize () const
1483         {
1484             return m_entries.size();
1485         }
1486
1487         const Entry *
1488         GetEntryAtIndex (size_t i) const
1489         {
1490             return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
1491         }
1492
1493         // Clients must ensure that "i" is a valid index prior to calling this function
1494         const Entry &
1495         GetEntryRef (size_t i) const
1496         {
1497             return m_entries[i];
1498         }
1499
1500         static bool
1501         BaseLessThan (const Entry& lhs, const Entry& rhs)
1502         {
1503             return lhs.addr < rhs.addr;
1504         }
1505
1506         Entry *
1507         FindEntry (B addr, bool exact_match_only)
1508         {
1509 #ifdef ASSERT_RANGEMAP_ARE_SORTED
1510             assert (IsSorted());
1511 #endif
1512             if ( !m_entries.empty() )
1513             {
1514                 Entry entry;
1515                 entry.addr = addr;
1516                 typename Collection::iterator begin = m_entries.begin();
1517                 typename Collection::iterator end = m_entries.end();
1518                 typename Collection::iterator pos = std::lower_bound (begin, end, entry, BaseLessThan);
1519
1520                 while(pos != begin && pos[-1].addr == addr)
1521                     --pos;
1522
1523                 if (pos != end)
1524                 {
1525                     if (pos->addr == addr || !exact_match_only)
1526                         return &(*pos);
1527                 }
1528             }
1529             return nullptr;
1530         }
1531
1532         const Entry *
1533         FindNextEntry (const Entry *entry)
1534         {
1535             if (entry >= &*m_entries.begin() && entry + 1 < &*m_entries.end())
1536                 return entry + 1;
1537             return nullptr;
1538         }
1539
1540         Entry *
1541         Back()
1542         {
1543             return (m_entries.empty() ? nullptr : &m_entries.back());
1544         }
1545
1546         const Entry *
1547         Back() const
1548         {
1549             return (m_entries.empty() ? nullptr : &m_entries.back());
1550         }
1551
1552     protected:
1553         Collection m_entries;
1554     };
1555
1556 } // namespace lldb_private
1557
1558 #endif // liblldb_RangeMap_h_