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

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