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 RangeRange43 Range () : 44 base (0), 45 size (0) 46 { 47 } 48 RangeRange49 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 GetRangeBaseRange64 GetRangeBase () const 65 { 66 return base; 67 } 68 69 void SetRangeBaseRange70 SetRangeBase (BaseType b) 71 { 72 base = b; 73 } 74 75 void SlideRange76 Slide (BaseType slide) 77 { 78 base += slide; 79 } 80 81 BaseType GetRangeEndRange82 GetRangeEnd () const 83 { 84 return base + size; 85 } 86 87 void SetRangeEndRange88 SetRangeEnd (BaseType end) 89 { 90 if (end > base) 91 size = end - base; 92 else 93 size = 0; 94 } 95 96 SizeType GetByteSizeRange97 GetByteSize () const 98 { 99 return size; 100 } 101 102 void SetByteSizeRange103 SetByteSize (SizeType s) 104 { 105 size = s; 106 } 107 108 bool IsValidRange109 IsValid() const 110 { 111 return size > 0; 112 } 113 114 bool ContainsRange115 Contains (BaseType r) const 116 { 117 return (GetRangeBase() <= r) && (r < GetRangeEnd()); 118 } 119 120 bool ContainsEndInclusiveRange121 ContainsEndInclusive (BaseType r) const 122 { 123 return (GetRangeBase() <= r) && (r <= GetRangeEnd()); 124 } 125 126 bool ContainsRange127 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 DoesAdjoinOrIntersectRange134 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 DoesIntersectRange146 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 RangeArray()191 RangeArray () : 192 m_entries () 193 { 194 } 195 ~RangeArray()196 ~RangeArray() 197 { 198 } 199 200 void Append(const Entry & entry)201 Append (const Entry &entry) 202 { 203 m_entries.push_back (entry); 204 } 205 206 bool RemoveEntrtAtIndex(uint32_t idx)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 Sort()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 IsSorted()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 CombineConsecutiveRanges()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 GetMinRangeBase(BaseType fail_value)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 GetMaxRangeEnd(BaseType fail_value)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 Slide(BaseType slide)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 Clear()320 Clear () 321 { 322 m_entries.clear(); 323 } 324 325 bool IsEmpty()326 IsEmpty () const 327 { 328 return m_entries.empty(); 329 } 330 331 size_t GetSize()332 GetSize () const 333 { 334 return m_entries.size(); 335 } 336 337 const Entry * GetEntryAtIndex(size_t i)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 & GetEntryRef(size_t i)347 GetEntryRef (size_t i) const 348 { 349 return m_entries[i]; 350 } 351 352 Entry * Back()353 Back() 354 { 355 if (m_entries.empty()) 356 return NULL; 357 return &m_entries.back(); 358 } 359 360 const Entry * Back()361 Back() const 362 { 363 if (m_entries.empty()) 364 return NULL; 365 return &m_entries.back(); 366 } 367 368 static bool BaseLessThan(const Entry & lhs,const Entry & rhs)369 BaseLessThan (const Entry& lhs, const Entry& rhs) 370 { 371 return lhs.GetRangeBase() < rhs.GetRangeBase(); 372 } 373 374 uint32_t FindEntryIndexThatContains(B addr)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 * FindEntryThatContains(B addr)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 * FindEntryThatContains(const Entry & range)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 RangeVector()471 RangeVector () : 472 m_entries () 473 { 474 } 475 ~RangeVector()476 ~RangeVector() 477 { 478 } 479 480 void Append(const Entry & entry)481 Append (const Entry &entry) 482 { 483 m_entries.push_back (entry); 484 } 485 486 bool RemoveEntrtAtIndex(uint32_t idx)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 Sort()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 IsSorted()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 CombineConsecutiveRanges()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 GetMinRangeBase(BaseType fail_value)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 GetMaxRangeEnd(BaseType fail_value)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 Slide(BaseType slide)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 Clear()600 Clear () 601 { 602 m_entries.clear(); 603 } 604 605 void Reserve(typename Collection::size_type size)606 Reserve (typename Collection::size_type size) 607 { 608 m_entries.reserve (size); 609 } 610 611 bool IsEmpty()612 IsEmpty () const 613 { 614 return m_entries.empty(); 615 } 616 617 size_t GetSize()618 GetSize () const 619 { 620 return m_entries.size(); 621 } 622 623 const Entry * GetEntryAtIndex(size_t i)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 & GetEntryRef(size_t i)633 GetEntryRef (size_t i) const 634 { 635 return m_entries[i]; 636 } 637 638 Entry * Back()639 Back() 640 { 641 if (m_entries.empty()) 642 return NULL; 643 return &m_entries.back(); 644 } 645 646 const Entry * Back()647 Back() const 648 { 649 if (m_entries.empty()) 650 return NULL; 651 return &m_entries.back(); 652 } 653 654 static bool BaseLessThan(const Entry & lhs,const Entry & rhs)655 BaseLessThan (const Entry& lhs, const Entry& rhs) 656 { 657 return lhs.GetRangeBase() < rhs.GetRangeBase(); 658 } 659 660 uint32_t FindEntryIndexThatContains(B addr)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 * FindEntryThatContains(B addr)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 * FindEntryThatContains(const Entry & range)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 RangeDataRangeData760 RangeData () : 761 Range<B,S> (), 762 data () 763 { 764 } 765 RangeDataRangeData766 RangeData (B base, S size) : 767 Range<B,S> (base, size), 768 data () 769 { 770 } 771 RangeDataRangeData772 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 RangeDataArray()816 RangeDataArray () 817 { 818 } 819 ~RangeDataArray()820 ~RangeDataArray() 821 { 822 } 823 824 void Append(const Entry & entry)825 Append (const Entry &entry) 826 { 827 m_entries.push_back (entry); 828 } 829 830 void Sort()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 IsSorted()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 CombineConsecutiveEntriesWithEqualData()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 Clear()894 Clear () 895 { 896 m_entries.clear(); 897 } 898 899 bool IsEmpty()900 IsEmpty () const 901 { 902 return m_entries.empty(); 903 } 904 905 size_t GetSize()906 GetSize () const 907 { 908 return m_entries.size(); 909 } 910 911 const Entry * GetEntryAtIndex(size_t i)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 & GetEntryRef(size_t i)921 GetEntryRef (size_t i) const 922 { 923 return m_entries[i]; 924 } 925 926 static bool BaseLessThan(const Entry & lhs,const Entry & rhs)927 BaseLessThan (const Entry& lhs, const Entry& rhs) 928 { 929 return lhs.GetRangeBase() < rhs.GetRangeBase(); 930 } 931 932 uint32_t FindEntryIndexThatContains(B addr)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 * FindEntryThatContains(B addr)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 * FindEntryThatContains(B addr)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 * FindEntryThatContains(const Entry & range)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 * Back()1049 Back() 1050 { 1051 if (!m_entries.empty()) 1052 return &m_entries.back(); 1053 return NULL; 1054 } 1055 1056 const Entry * Back()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 RangeDataVector()1077 RangeDataVector () 1078 { 1079 } 1080 ~RangeDataVector()1081 ~RangeDataVector() 1082 { 1083 } 1084 1085 void Append(const Entry & entry)1086 Append (const Entry &entry) 1087 { 1088 m_entries.push_back (entry); 1089 } 1090 1091 void Sort()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 IsSorted()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 CombineConsecutiveEntriesWithEqualData()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 CalculateSizesOfZeroByteSizeRanges()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 Clear()1188 Clear () 1189 { 1190 m_entries.clear(); 1191 } 1192 1193 void Reserve(typename Collection::size_type size)1194 Reserve (typename Collection::size_type size) 1195 { 1196 m_entries.resize (size); 1197 } 1198 1199 bool IsEmpty()1200 IsEmpty () const 1201 { 1202 return m_entries.empty(); 1203 } 1204 1205 size_t GetSize()1206 GetSize () const 1207 { 1208 return m_entries.size(); 1209 } 1210 1211 const Entry * GetEntryAtIndex(size_t i)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 & GetEntryRef(size_t i)1221 GetEntryRef (size_t i) const 1222 { 1223 return m_entries[i]; 1224 } 1225 1226 static bool BaseLessThan(const Entry & lhs,const Entry & rhs)1227 BaseLessThan (const Entry& lhs, const Entry& rhs) 1228 { 1229 return lhs.GetRangeBase() < rhs.GetRangeBase(); 1230 } 1231 1232 uint32_t FindEntryIndexThatContains(B addr)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 * FindEntryThatContains(B addr)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 * FindEntryThatContains(B addr)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 * FindEntryThatContains(const Entry & range)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 * Back()1323 Back() 1324 { 1325 if (!m_entries.empty()) 1326 return &m_entries.back(); 1327 return NULL; 1328 } 1329 1330 const Entry * Back()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 AddressDataAddressData1357 AddressData () : 1358 addr (), 1359 data () 1360 { 1361 } 1362 AddressDataAddressData1363 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 AddressDataArray()1401 AddressDataArray () 1402 { 1403 } 1404 ~AddressDataArray()1405 ~AddressDataArray() 1406 { 1407 } 1408 1409 void Append(const Entry & entry)1410 Append (const Entry &entry) 1411 { 1412 m_entries.push_back (entry); 1413 } 1414 1415 void Sort()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 IsSorted()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 Clear()1439 Clear () 1440 { 1441 m_entries.clear(); 1442 } 1443 1444 bool IsEmpty()1445 IsEmpty () const 1446 { 1447 return m_entries.empty(); 1448 } 1449 1450 size_t GetSize()1451 GetSize () const 1452 { 1453 return m_entries.size(); 1454 } 1455 1456 const Entry * GetEntryAtIndex(size_t i)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 & GetEntryRef(size_t i)1466 GetEntryRef (size_t i) const 1467 { 1468 return m_entries[i]; 1469 } 1470 1471 static bool BaseLessThan(const Entry & lhs,const Entry & rhs)1472 BaseLessThan (const Entry& lhs, const Entry& rhs) 1473 { 1474 return lhs.addr < rhs.addr; 1475 } 1476 1477 Entry * FindEntry(B addr,bool exact_match_only)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 * FindNextEntry(const Entry * 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 * Back()1512 Back() 1513 { 1514 if (!m_entries.empty()) 1515 return &m_entries.back(); 1516 return NULL; 1517 } 1518 1519 const Entry * Back()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_ 1534