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