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 bool OverlapRange133 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 RangeArray()178 RangeArray () : 179 m_entries () 180 { 181 } 182 ~RangeArray()183 ~RangeArray() 184 { 185 } 186 187 void Append(const Entry & entry)188 Append (const Entry &entry) 189 { 190 m_entries.push_back (entry); 191 } 192 193 bool RemoveEntrtAtIndex(uint32_t idx)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 Sort()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 IsSorted()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 CombineConsecutiveRanges()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 GetMinRangeBase(BaseType fail_value)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 GetMaxRangeEnd(BaseType fail_value)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 Slide(BaseType slide)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 Clear()307 Clear () 308 { 309 m_entries.clear(); 310 } 311 312 bool IsEmpty()313 IsEmpty () const 314 { 315 return m_entries.empty(); 316 } 317 318 size_t GetSize()319 GetSize () const 320 { 321 return m_entries.size(); 322 } 323 324 const Entry * GetEntryAtIndex(size_t i)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 & GetEntryRef(size_t i)334 GetEntryRef (size_t i) const 335 { 336 return m_entries[i]; 337 } 338 339 Entry * Back()340 Back() 341 { 342 if (m_entries.empty()) 343 return NULL; 344 return &m_entries.back(); 345 } 346 347 const Entry * Back()348 Back() const 349 { 350 if (m_entries.empty()) 351 return NULL; 352 return &m_entries.back(); 353 } 354 355 static bool BaseLessThan(const Entry & lhs,const Entry & rhs)356 BaseLessThan (const Entry& lhs, const Entry& rhs) 357 { 358 return lhs.GetRangeBase() < rhs.GetRangeBase(); 359 } 360 361 uint32_t FindEntryIndexThatContains(B addr)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 * FindEntryThatContains(B addr)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 * FindEntryThatContains(const Entry & range)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 RangeVector()458 RangeVector () : 459 m_entries () 460 { 461 } 462 ~RangeVector()463 ~RangeVector() 464 { 465 } 466 467 void Append(const Entry & entry)468 Append (const Entry &entry) 469 { 470 m_entries.push_back (entry); 471 } 472 473 bool RemoveEntrtAtIndex(uint32_t idx)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 Sort()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 IsSorted()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 CombineConsecutiveRanges()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 GetMinRangeBase(BaseType fail_value)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 GetMaxRangeEnd(BaseType fail_value)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 Slide(BaseType slide)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 Clear()587 Clear () 588 { 589 m_entries.clear(); 590 } 591 592 void Reserve(typename Collection::size_type size)593 Reserve (typename Collection::size_type size) 594 { 595 m_entries.resize (size); 596 } 597 598 bool IsEmpty()599 IsEmpty () const 600 { 601 return m_entries.empty(); 602 } 603 604 size_t GetSize()605 GetSize () const 606 { 607 return m_entries.size(); 608 } 609 610 const Entry * GetEntryAtIndex(size_t i)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 & GetEntryRef(size_t i)620 GetEntryRef (size_t i) const 621 { 622 return m_entries[i]; 623 } 624 625 Entry * Back()626 Back() 627 { 628 if (m_entries.empty()) 629 return NULL; 630 return &m_entries.back(); 631 } 632 633 const Entry * Back()634 Back() const 635 { 636 if (m_entries.empty()) 637 return NULL; 638 return &m_entries.back(); 639 } 640 641 static bool BaseLessThan(const Entry & lhs,const Entry & rhs)642 BaseLessThan (const Entry& lhs, const Entry& rhs) 643 { 644 return lhs.GetRangeBase() < rhs.GetRangeBase(); 645 } 646 647 uint32_t FindEntryIndexThatContains(B addr)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 * FindEntryThatContains(B addr)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 * FindEntryThatContains(const Entry & range)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 RangeDataRangeData747 RangeData () : 748 Range<B,S> (), 749 data () 750 { 751 } 752 RangeDataRangeData753 RangeData (B base, S size) : 754 Range<B,S> (base, size), 755 data () 756 { 757 } 758 RangeDataRangeData759 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 RangeDataArray()803 RangeDataArray () 804 { 805 } 806 ~RangeDataArray()807 ~RangeDataArray() 808 { 809 } 810 811 void Append(const Entry & entry)812 Append (const Entry &entry) 813 { 814 m_entries.push_back (entry); 815 } 816 817 void Sort()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 IsSorted()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 CombineConsecutiveEntriesWithEqualData()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 Clear()881 Clear () 882 { 883 m_entries.clear(); 884 } 885 886 bool IsEmpty()887 IsEmpty () const 888 { 889 return m_entries.empty(); 890 } 891 892 size_t GetSize()893 GetSize () const 894 { 895 return m_entries.size(); 896 } 897 898 const Entry * GetEntryAtIndex(size_t i)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 & GetEntryRef(size_t i)908 GetEntryRef (size_t i) const 909 { 910 return m_entries[i]; 911 } 912 913 static bool BaseLessThan(const Entry & lhs,const Entry & rhs)914 BaseLessThan (const Entry& lhs, const Entry& rhs) 915 { 916 return lhs.GetRangeBase() < rhs.GetRangeBase(); 917 } 918 919 uint32_t FindEntryIndexThatContains(B addr)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 * FindEntryThatContains(B addr)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 * FindEntryThatContains(B addr)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 * FindEntryThatContains(const Entry & range)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 * Back()1036 Back() 1037 { 1038 if (!m_entries.empty()) 1039 return &m_entries.back(); 1040 return NULL; 1041 } 1042 1043 const Entry * Back()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 RangeDataVector()1064 RangeDataVector () 1065 { 1066 } 1067 ~RangeDataVector()1068 ~RangeDataVector() 1069 { 1070 } 1071 1072 void Append(const Entry & entry)1073 Append (const Entry &entry) 1074 { 1075 m_entries.push_back (entry); 1076 } 1077 1078 void Sort()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 IsSorted()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 CombineConsecutiveEntriesWithEqualData()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 CalculateSizesOfZeroByteSizeRanges()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 Clear()1175 Clear () 1176 { 1177 m_entries.clear(); 1178 } 1179 1180 void Reserve(typename Collection::size_type size)1181 Reserve (typename Collection::size_type size) 1182 { 1183 m_entries.resize (size); 1184 } 1185 1186 bool IsEmpty()1187 IsEmpty () const 1188 { 1189 return m_entries.empty(); 1190 } 1191 1192 size_t GetSize()1193 GetSize () const 1194 { 1195 return m_entries.size(); 1196 } 1197 1198 const Entry * GetEntryAtIndex(size_t i)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 & GetEntryRef(size_t i)1208 GetEntryRef (size_t i) const 1209 { 1210 return m_entries[i]; 1211 } 1212 1213 static bool BaseLessThan(const Entry & lhs,const Entry & rhs)1214 BaseLessThan (const Entry& lhs, const Entry& rhs) 1215 { 1216 return lhs.GetRangeBase() < rhs.GetRangeBase(); 1217 } 1218 1219 uint32_t FindEntryIndexThatContains(B addr)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 * FindEntryThatContains(B addr)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 * FindEntryThatContains(B addr)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 * FindEntryThatContains(const Entry & range)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 * Back()1336 Back() 1337 { 1338 if (!m_entries.empty()) 1339 return &m_entries.back(); 1340 return NULL; 1341 } 1342 1343 const Entry * Back()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 AddressDataAddressData1370 AddressData () : 1371 addr (), 1372 data () 1373 { 1374 } 1375 AddressDataAddressData1376 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 AddressDataArray()1414 AddressDataArray () 1415 { 1416 } 1417 ~AddressDataArray()1418 ~AddressDataArray() 1419 { 1420 } 1421 1422 void Append(const Entry & entry)1423 Append (const Entry &entry) 1424 { 1425 m_entries.push_back (entry); 1426 } 1427 1428 void Sort()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 IsSorted()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 Clear()1452 Clear () 1453 { 1454 m_entries.clear(); 1455 } 1456 1457 bool IsEmpty()1458 IsEmpty () const 1459 { 1460 return m_entries.empty(); 1461 } 1462 1463 size_t GetSize()1464 GetSize () const 1465 { 1466 return m_entries.size(); 1467 } 1468 1469 const Entry * GetEntryAtIndex(size_t i)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 & GetEntryRef(size_t i)1479 GetEntryRef (size_t i) const 1480 { 1481 return m_entries[i]; 1482 } 1483 1484 static bool BaseLessThan(const Entry & lhs,const Entry & rhs)1485 BaseLessThan (const Entry& lhs, const Entry& rhs) 1486 { 1487 return lhs.addr < rhs.addr; 1488 } 1489 1490 Entry * FindEntry(B addr,bool exact_match_only)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 * FindNextEntry(const Entry * 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 * Back()1522 Back() 1523 { 1524 if (!m_entries.empty()) 1525 return &m_entries.back(); 1526 return NULL; 1527 } 1528 1529 const Entry * Back()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_ 1544