RangeMap.h revision 263363
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 21namespace 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.reserve (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 while(pos != begin && pos[-1].Contains(addr)) 1233 --pos; 1234 1235 if (pos != end && pos->Contains(addr)) 1236 return std::distance (begin, pos); 1237 } 1238 return UINT32_MAX; 1239 } 1240 1241 Entry * 1242 FindEntryThatContains (B addr) 1243 { 1244#ifdef ASSERT_RANGEMAP_ARE_SORTED 1245 assert (IsSorted()); 1246#endif 1247 if ( !m_entries.empty() ) 1248 { 1249 Entry entry; 1250 entry.SetRangeBase(addr); 1251 entry.SetByteSize(1); 1252 typename Collection::iterator begin = m_entries.begin(); 1253 typename Collection::iterator end = m_entries.end(); 1254 typename Collection::iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 1255 1256 while(pos != begin && pos[-1].Contains(addr)) 1257 --pos; 1258 1259 if (pos != end && pos->Contains(addr)) 1260 return &(*pos); 1261 } 1262 return NULL; 1263 } 1264 const Entry * 1265 FindEntryThatContains (B addr) const 1266 { 1267#ifdef ASSERT_RANGEMAP_ARE_SORTED 1268 assert (IsSorted()); 1269#endif 1270 if ( !m_entries.empty() ) 1271 { 1272 Entry entry; 1273 entry.SetRangeBase(addr); 1274 entry.SetByteSize(1); 1275 typename Collection::const_iterator begin = m_entries.begin(); 1276 typename Collection::const_iterator end = m_entries.end(); 1277 typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 1278 1279 while(pos != begin && pos[-1].Contains(addr)) 1280 --pos; 1281 1282 if (pos != end && pos->Contains(addr)) 1283 return &(*pos); 1284 } 1285 return NULL; 1286 } 1287 1288 const Entry * 1289 FindEntryThatContains (const Entry &range) const 1290 { 1291#ifdef ASSERT_RANGEMAP_ARE_SORTED 1292 assert (IsSorted()); 1293#endif 1294 if ( !m_entries.empty() ) 1295 { 1296 typename Collection::const_iterator begin = m_entries.begin(); 1297 typename Collection::const_iterator end = m_entries.end(); 1298 typename Collection::const_iterator pos = std::lower_bound (begin, end, range, BaseLessThan); 1299 1300 while(pos != begin && pos[-1].Contains(range)) 1301 --pos; 1302 1303 if (pos != end && pos->Contains(range)) 1304 return &(*pos); 1305 } 1306 return NULL; 1307 } 1308 1309 Entry * 1310 Back() 1311 { 1312 if (!m_entries.empty()) 1313 return &m_entries.back(); 1314 return NULL; 1315 } 1316 1317 const Entry * 1318 Back() const 1319 { 1320 if (!m_entries.empty()) 1321 return &m_entries.back(); 1322 return NULL; 1323 } 1324 1325 protected: 1326 Collection m_entries; 1327 }; 1328 1329 1330 //---------------------------------------------------------------------- 1331 // A simple range with data class where you get to define the type of 1332 // the range base "B", the type used for the range byte size "S", and 1333 // the type for the associated data "T". 1334 //---------------------------------------------------------------------- 1335 template <typename B, typename T> 1336 struct AddressData 1337 { 1338 typedef B BaseType; 1339 typedef T DataType; 1340 1341 BaseType addr; 1342 DataType data; 1343 1344 AddressData () : 1345 addr (), 1346 data () 1347 { 1348 } 1349 1350 AddressData (B a, DataType d) : 1351 addr (a), 1352 data (d) 1353 { 1354 } 1355 1356 bool 1357 operator < (const AddressData &rhs) const 1358 { 1359 if (this->addr == rhs.addr) 1360 return this->data < rhs.data; 1361 return this->addr < rhs.addr; 1362 } 1363 1364 bool 1365 operator == (const AddressData &rhs) const 1366 { 1367 return this->addr == rhs.addr && 1368 this->data == rhs.data; 1369 } 1370 1371 bool 1372 operator != (const AddressData &rhs) const 1373 { 1374 return this->addr != rhs.addr || 1375 this->data == rhs.data; 1376 } 1377 }; 1378 1379 1380 template <typename B, typename T, unsigned N> 1381 class AddressDataArray 1382 { 1383 public: 1384 typedef AddressData<B,T> Entry; 1385 typedef llvm::SmallVector<Entry, N> Collection; 1386 1387 1388 AddressDataArray () 1389 { 1390 } 1391 1392 ~AddressDataArray() 1393 { 1394 } 1395 1396 void 1397 Append (const Entry &entry) 1398 { 1399 m_entries.push_back (entry); 1400 } 1401 1402 void 1403 Sort () 1404 { 1405 if (m_entries.size() > 1) 1406 std::stable_sort (m_entries.begin(), m_entries.end()); 1407 } 1408 1409#ifdef ASSERT_RANGEMAP_ARE_SORTED 1410 bool 1411 IsSorted () const 1412 { 1413 typename Collection::const_iterator pos, end, prev; 1414 // First we determine if we can combine any of the Entry objects so we 1415 // don't end up allocating and making a new collection for no reason 1416 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 1417 { 1418 if (prev != end && *pos < *prev) 1419 return false; 1420 } 1421 return true; 1422 } 1423#endif 1424 1425 void 1426 Clear () 1427 { 1428 m_entries.clear(); 1429 } 1430 1431 bool 1432 IsEmpty () const 1433 { 1434 return m_entries.empty(); 1435 } 1436 1437 size_t 1438 GetSize () const 1439 { 1440 return m_entries.size(); 1441 } 1442 1443 const Entry * 1444 GetEntryAtIndex (size_t i) const 1445 { 1446 if (i<m_entries.size()) 1447 return &m_entries[i]; 1448 return NULL; 1449 } 1450 1451 // Clients must ensure that "i" is a valid index prior to calling this function 1452 const Entry & 1453 GetEntryRef (size_t i) const 1454 { 1455 return m_entries[i]; 1456 } 1457 1458 static bool 1459 BaseLessThan (const Entry& lhs, const Entry& rhs) 1460 { 1461 return lhs.addr < rhs.addr; 1462 } 1463 1464 Entry * 1465 FindEntry (B addr, bool exact_match_only) 1466 { 1467#ifdef ASSERT_RANGEMAP_ARE_SORTED 1468 assert (IsSorted()); 1469#endif 1470 if ( !m_entries.empty() ) 1471 { 1472 Entry entry; 1473 entry.addr = addr; 1474 typename Collection::iterator begin = m_entries.begin(); 1475 typename Collection::iterator end = m_entries.end(); 1476 typename Collection::iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 1477 1478 while(pos != begin && pos[-1].addr == addr) 1479 --pos; 1480 1481 if (pos != end) 1482 { 1483 if (pos->addr == addr || !exact_match_only) 1484 return &(*pos); 1485 } 1486 } 1487 return NULL; 1488 } 1489 1490 const Entry * 1491 FindNextEntry (const Entry *entry) 1492 { 1493 if (entry >= &*m_entries.begin() && entry + 1 < &*m_entries.end()) 1494 return entry + 1; 1495 return NULL; 1496 } 1497 1498 Entry * 1499 Back() 1500 { 1501 if (!m_entries.empty()) 1502 return &m_entries.back(); 1503 return NULL; 1504 } 1505 1506 const Entry * 1507 Back() const 1508 { 1509 if (!m_entries.empty()) 1510 return &m_entries.back(); 1511 return NULL; 1512 } 1513 1514 protected: 1515 Collection m_entries; 1516 }; 1517 1518} // namespace lldb_private 1519 1520#endif // liblldb_RangeMap_h_ 1521