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