RangeMap.h revision 464a5063bc59755cb6ec063d0b2491097302d2ab
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 bool 593 IsEmpty () const 594 { 595 return m_entries.empty(); 596 } 597 598 size_t 599 GetSize () const 600 { 601 return m_entries.size(); 602 } 603 604 const Entry * 605 GetEntryAtIndex (size_t i) const 606 { 607 if (i<m_entries.size()) 608 return &m_entries[i]; 609 return NULL; 610 } 611 612 // Clients must ensure that "i" is a valid index prior to calling this function 613 const Entry & 614 GetEntryRef (size_t i) const 615 { 616 return m_entries[i]; 617 } 618 619 Entry * 620 Back() 621 { 622 if (m_entries.empty()) 623 return NULL; 624 return &m_entries.back(); 625 } 626 627 const Entry * 628 Back() const 629 { 630 if (m_entries.empty()) 631 return NULL; 632 return &m_entries.back(); 633 } 634 635 static bool 636 BaseLessThan (const Entry& lhs, const Entry& rhs) 637 { 638 return lhs.GetRangeBase() < rhs.GetRangeBase(); 639 } 640 641 uint32_t 642 FindEntryIndexThatContains (B addr) const 643 { 644#ifdef ASSERT_RANGEMAP_ARE_SORTED 645 assert (IsSorted()); 646#endif 647 if (!m_entries.empty()) 648 { 649 Entry entry (addr, 1); 650 typename Collection::const_iterator begin = m_entries.begin(); 651 typename Collection::const_iterator end = m_entries.end(); 652 typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 653 654 if (pos != end && pos->Contains(addr)) 655 { 656 return std::distance (begin, pos); 657 } 658 else if (pos != begin) 659 { 660 --pos; 661 if (pos->Contains(addr)) 662 return std::distance (begin, pos); 663 } 664 } 665 return UINT32_MAX; 666 } 667 668 const Entry * 669 FindEntryThatContains (B addr) const 670 { 671#ifdef ASSERT_RANGEMAP_ARE_SORTED 672 assert (IsSorted()); 673#endif 674 if (!m_entries.empty()) 675 { 676 Entry entry (addr, 1); 677 typename Collection::const_iterator begin = m_entries.begin(); 678 typename Collection::const_iterator end = m_entries.end(); 679 typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 680 681 if (pos != end && pos->Contains(addr)) 682 { 683 return &(*pos); 684 } 685 else if (pos != begin) 686 { 687 --pos; 688 if (pos->Contains(addr)) 689 { 690 return &(*pos); 691 } 692 } 693 } 694 return NULL; 695 } 696 697 const Entry * 698 FindEntryThatContains (const Entry &range) const 699 { 700#ifdef ASSERT_RANGEMAP_ARE_SORTED 701 assert (IsSorted()); 702#endif 703 if (!m_entries.empty()) 704 { 705 typename Collection::const_iterator begin = m_entries.begin(); 706 typename Collection::const_iterator end = m_entries.end(); 707 typename Collection::const_iterator pos = std::lower_bound (begin, end, range, BaseLessThan); 708 709 if (pos != end && pos->Contains(range)) 710 { 711 return &(*pos); 712 } 713 else if (pos != begin) 714 { 715 --pos; 716 if (pos->Contains(range)) 717 { 718 return &(*pos); 719 } 720 } 721 } 722 return NULL; 723 } 724 725 protected: 726 Collection m_entries; 727 }; 728 729 //---------------------------------------------------------------------- 730 // A simple range with data class where you get to define the type of 731 // the range base "B", the type used for the range byte size "S", and 732 // the type for the associated data "T". 733 //---------------------------------------------------------------------- 734 template <typename B, typename S, typename T> 735 struct RangeData : public Range<B,S> 736 { 737 typedef T DataType; 738 739 DataType data; 740 741 RangeData () : 742 Range<B,S> (), 743 data () 744 { 745 } 746 747 RangeData (B base, S size) : 748 Range<B,S> (base, size), 749 data () 750 { 751 } 752 753 RangeData (B base, S size, DataType d) : 754 Range<B,S> (base, size), 755 data (d) 756 { 757 } 758 759 bool 760 operator < (const RangeData &rhs) const 761 { 762 if (this->base == rhs.base) 763 { 764 if (this->size == rhs.size) 765 return this->data < rhs.data; 766 else 767 return this->size < rhs.size; 768 } 769 return this->base < rhs.base; 770 } 771 772 bool 773 operator == (const RangeData &rhs) const 774 { 775 return this->GetRangeBase() == rhs.GetRangeBase() && 776 this->GetByteSize() == rhs.GetByteSize() && 777 this->data == rhs.data; 778 } 779 780 bool 781 operator != (const RangeData &rhs) const 782 { 783 return this->GetRangeBase() != rhs.GetRangeBase() || 784 this->GetByteSize() != rhs.GetByteSize() || 785 this->data != rhs.data; 786 } 787 }; 788 789 template <typename B, typename S, typename T, unsigned N> 790 class RangeDataArray 791 { 792 public: 793 typedef RangeData<B,S,T> Entry; 794 typedef llvm::SmallVector<Entry, N> Collection; 795 796 797 RangeDataArray () 798 { 799 } 800 801 ~RangeDataArray() 802 { 803 } 804 805 void 806 Append (const Entry &entry) 807 { 808 m_entries.push_back (entry); 809 } 810 811 void 812 Sort () 813 { 814 if (m_entries.size() > 1) 815 std::stable_sort (m_entries.begin(), m_entries.end()); 816 } 817 818#ifdef ASSERT_RANGEMAP_ARE_SORTED 819 bool 820 IsSorted () const 821 { 822 typename Collection::const_iterator pos, end, prev; 823 // First we determine if we can combine any of the Entry objects so we 824 // don't end up allocating and making a new collection for no reason 825 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 826 { 827 if (prev != end && *pos < *prev) 828 return false; 829 } 830 return true; 831 } 832#endif 833 834 void 835 CombineConsecutiveEntriesWithEqualData () 836 { 837#ifdef ASSERT_RANGEMAP_ARE_SORTED 838 assert (IsSorted()); 839#endif 840 typename Collection::iterator pos; 841 typename Collection::iterator end; 842 typename Collection::iterator prev; 843 bool can_combine = false; 844 // First we determine if we can combine any of the Entry objects so we 845 // don't end up allocating and making a new collection for no reason 846 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 847 { 848 if (prev != end && prev->data == pos->data) 849 { 850 can_combine = true; 851 break; 852 } 853 } 854 855 // We we can combine at least one entry, then we make a new collection 856 // and populate it accordingly, and then swap it into place. 857 if (can_combine) 858 { 859 Collection minimal_ranges; 860 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 861 { 862 if (prev != end && prev->data == pos->data) 863 minimal_ranges.back().SetRangeEnd (pos->GetRangeEnd()); 864 else 865 minimal_ranges.push_back (*pos); 866 } 867 // Use the swap technique in case our new vector is much smaller. 868 // We must swap when using the STL because std::vector objects never 869 // release or reduce the memory once it has been allocated/reserved. 870 m_entries.swap (minimal_ranges); 871 } 872 } 873 874 void 875 Clear () 876 { 877 m_entries.clear(); 878 } 879 880 bool 881 IsEmpty () const 882 { 883 return m_entries.empty(); 884 } 885 886 size_t 887 GetSize () const 888 { 889 return m_entries.size(); 890 } 891 892 const Entry * 893 GetEntryAtIndex (size_t i) const 894 { 895 if (i<m_entries.size()) 896 return &m_entries[i]; 897 return NULL; 898 } 899 900 // Clients must ensure that "i" is a valid index prior to calling this function 901 const Entry & 902 GetEntryRef (size_t i) const 903 { 904 return m_entries[i]; 905 } 906 907 static bool 908 BaseLessThan (const Entry& lhs, const Entry& rhs) 909 { 910 return lhs.GetRangeBase() < rhs.GetRangeBase(); 911 } 912 913 uint32_t 914 FindEntryIndexThatContains (B addr) const 915 { 916#ifdef ASSERT_RANGEMAP_ARE_SORTED 917 assert (IsSorted()); 918#endif 919 if ( !m_entries.empty() ) 920 { 921 Entry entry (addr, 1); 922 typename Collection::const_iterator begin = m_entries.begin(); 923 typename Collection::const_iterator end = m_entries.end(); 924 typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 925 926 if (pos != end && pos->Contains(addr)) 927 { 928 return std::distance (begin, pos); 929 } 930 else if (pos != begin) 931 { 932 --pos; 933 if (pos->Contains(addr)) 934 return std::distance (begin, pos); 935 } 936 } 937 return UINT32_MAX; 938 } 939 940 Entry * 941 FindEntryThatContains (B addr) 942 { 943#ifdef ASSERT_RANGEMAP_ARE_SORTED 944 assert (IsSorted()); 945#endif 946 if ( !m_entries.empty() ) 947 { 948 Entry entry; 949 entry.SetRangeBase(addr); 950 entry.SetByteSize(1); 951 typename Collection::iterator begin = m_entries.begin(); 952 typename Collection::iterator end = m_entries.end(); 953 typename Collection::iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 954 955 if (pos != end && pos->Contains(addr)) 956 { 957 return &(*pos); 958 } 959 else if (pos != begin) 960 { 961 --pos; 962 if (pos->Contains(addr)) 963 { 964 return &(*pos); 965 } 966 } 967 } 968 return NULL; 969 } 970 const Entry * 971 FindEntryThatContains (B addr) const 972 { 973#ifdef ASSERT_RANGEMAP_ARE_SORTED 974 assert (IsSorted()); 975#endif 976 if ( !m_entries.empty() ) 977 { 978 Entry entry; 979 entry.SetRangeBase(addr); 980 entry.SetByteSize(1); 981 typename Collection::const_iterator begin = m_entries.begin(); 982 typename Collection::const_iterator end = m_entries.end(); 983 typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 984 985 if (pos != end && pos->Contains(addr)) 986 { 987 return &(*pos); 988 } 989 else if (pos != begin) 990 { 991 --pos; 992 if (pos->Contains(addr)) 993 { 994 return &(*pos); 995 } 996 } 997 } 998 return NULL; 999 } 1000 1001 const Entry * 1002 FindEntryThatContains (const Entry &range) const 1003 { 1004#ifdef ASSERT_RANGEMAP_ARE_SORTED 1005 assert (IsSorted()); 1006#endif 1007 if ( !m_entries.empty() ) 1008 { 1009 typename Collection::const_iterator begin = m_entries.begin(); 1010 typename Collection::const_iterator end = m_entries.end(); 1011 typename Collection::const_iterator pos = std::lower_bound (begin, end, range, BaseLessThan); 1012 1013 if (pos != end && pos->Contains(range)) 1014 { 1015 return &(*pos); 1016 } 1017 else if (pos != begin) 1018 { 1019 --pos; 1020 if (pos->Contains(range)) 1021 { 1022 return &(*pos); 1023 } 1024 } 1025 } 1026 return NULL; 1027 } 1028 1029 Entry * 1030 Back() 1031 { 1032 if (!m_entries.empty()) 1033 return &m_entries.back(); 1034 return NULL; 1035 } 1036 1037 const Entry * 1038 Back() const 1039 { 1040 if (!m_entries.empty()) 1041 return &m_entries.back(); 1042 return NULL; 1043 } 1044 1045 protected: 1046 Collection m_entries; 1047 }; 1048 1049 // Same as RangeDataArray, but uses std::vector as to not 1050 // require static storage of N items in the class itself 1051 template <typename B, typename S, typename T> 1052 class RangeDataVector 1053 { 1054 public: 1055 typedef RangeData<B,S,T> Entry; 1056 typedef std::vector<Entry> Collection; 1057 1058 RangeDataVector () 1059 { 1060 } 1061 1062 ~RangeDataVector() 1063 { 1064 } 1065 1066 void 1067 Append (const Entry &entry) 1068 { 1069 m_entries.push_back (entry); 1070 } 1071 1072 void 1073 Sort () 1074 { 1075 if (m_entries.size() > 1) 1076 std::stable_sort (m_entries.begin(), m_entries.end()); 1077 } 1078 1079#ifdef ASSERT_RANGEMAP_ARE_SORTED 1080 bool 1081 IsSorted () const 1082 { 1083 typename Collection::const_iterator pos, end, prev; 1084 // First we determine if we can combine any of the Entry objects so we 1085 // don't end up allocating and making a new collection for no reason 1086 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 1087 { 1088 if (prev != end && *pos < *prev) 1089 return false; 1090 } 1091 return true; 1092 } 1093#endif 1094 1095 void 1096 CombineConsecutiveEntriesWithEqualData () 1097 { 1098#ifdef ASSERT_RANGEMAP_ARE_SORTED 1099 assert (IsSorted()); 1100#endif 1101 typename Collection::iterator pos; 1102 typename Collection::iterator end; 1103 typename Collection::iterator prev; 1104 bool can_combine = false; 1105 // First we determine if we can combine any of the Entry objects so we 1106 // don't end up allocating and making a new collection for no reason 1107 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 1108 { 1109 if (prev != end && prev->data == pos->data) 1110 { 1111 can_combine = true; 1112 break; 1113 } 1114 } 1115 1116 // We we can combine at least one entry, then we make a new collection 1117 // and populate it accordingly, and then swap it into place. 1118 if (can_combine) 1119 { 1120 Collection minimal_ranges; 1121 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 1122 { 1123 if (prev != end && prev->data == pos->data) 1124 minimal_ranges.back().SetRangeEnd (pos->GetRangeEnd()); 1125 else 1126 minimal_ranges.push_back (*pos); 1127 } 1128 // Use the swap technique in case our new vector is much smaller. 1129 // We must swap when using the STL because std::vector objects never 1130 // release or reduce the memory once it has been allocated/reserved. 1131 m_entries.swap (minimal_ranges); 1132 } 1133 } 1134 1135 void 1136 Clear () 1137 { 1138 m_entries.clear(); 1139 } 1140 1141 bool 1142 IsEmpty () const 1143 { 1144 return m_entries.empty(); 1145 } 1146 1147 size_t 1148 GetSize () const 1149 { 1150 return m_entries.size(); 1151 } 1152 1153 const Entry * 1154 GetEntryAtIndex (size_t i) const 1155 { 1156 if (i<m_entries.size()) 1157 return &m_entries[i]; 1158 return NULL; 1159 } 1160 1161 // Clients must ensure that "i" is a valid index prior to calling this function 1162 const Entry & 1163 GetEntryRef (size_t i) const 1164 { 1165 return m_entries[i]; 1166 } 1167 1168 static bool 1169 BaseLessThan (const Entry& lhs, const Entry& rhs) 1170 { 1171 return lhs.GetRangeBase() < rhs.GetRangeBase(); 1172 } 1173 1174 uint32_t 1175 FindEntryIndexThatContains (B addr) const 1176 { 1177#ifdef ASSERT_RANGEMAP_ARE_SORTED 1178 assert (IsSorted()); 1179#endif 1180 if ( !m_entries.empty() ) 1181 { 1182 Entry entry (addr, 1); 1183 typename Collection::const_iterator begin = m_entries.begin(); 1184 typename Collection::const_iterator end = m_entries.end(); 1185 typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 1186 1187 if (pos != end && pos->Contains(addr)) 1188 { 1189 return std::distance (begin, pos); 1190 } 1191 else if (pos != begin) 1192 { 1193 --pos; 1194 if (pos->Contains(addr)) 1195 return std::distance (begin, pos); 1196 } 1197 } 1198 return UINT32_MAX; 1199 } 1200 1201 Entry * 1202 FindEntryThatContains (B addr) 1203 { 1204#ifdef ASSERT_RANGEMAP_ARE_SORTED 1205 assert (IsSorted()); 1206#endif 1207 if ( !m_entries.empty() ) 1208 { 1209 Entry entry; 1210 entry.SetRangeBase(addr); 1211 entry.SetByteSize(1); 1212 typename Collection::iterator begin = m_entries.begin(); 1213 typename Collection::iterator end = m_entries.end(); 1214 typename Collection::iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 1215 1216 if (pos != end && pos->Contains(addr)) 1217 { 1218 return &(*pos); 1219 } 1220 else if (pos != begin) 1221 { 1222 --pos; 1223 if (pos->Contains(addr)) 1224 { 1225 return &(*pos); 1226 } 1227 } 1228 } 1229 return NULL; 1230 } 1231 const Entry * 1232 FindEntryThatContains (B addr) const 1233 { 1234#ifdef ASSERT_RANGEMAP_ARE_SORTED 1235 assert (IsSorted()); 1236#endif 1237 if ( !m_entries.empty() ) 1238 { 1239 Entry entry; 1240 entry.SetRangeBase(addr); 1241 entry.SetByteSize(1); 1242 typename Collection::const_iterator begin = m_entries.begin(); 1243 typename Collection::const_iterator end = m_entries.end(); 1244 typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 1245 1246 if (pos != end && pos->Contains(addr)) 1247 { 1248 return &(*pos); 1249 } 1250 else if (pos != begin) 1251 { 1252 --pos; 1253 if (pos->Contains(addr)) 1254 { 1255 return &(*pos); 1256 } 1257 } 1258 } 1259 return NULL; 1260 } 1261 1262 const Entry * 1263 FindEntryThatContains (const Entry &range) const 1264 { 1265#ifdef ASSERT_RANGEMAP_ARE_SORTED 1266 assert (IsSorted()); 1267#endif 1268 if ( !m_entries.empty() ) 1269 { 1270 typename Collection::const_iterator begin = m_entries.begin(); 1271 typename Collection::const_iterator end = m_entries.end(); 1272 typename Collection::const_iterator pos = std::lower_bound (begin, end, range, BaseLessThan); 1273 1274 if (pos != end && pos->Contains(range)) 1275 { 1276 return &(*pos); 1277 } 1278 else if (pos != begin) 1279 { 1280 --pos; 1281 if (pos->Contains(range)) 1282 { 1283 return &(*pos); 1284 } 1285 } 1286 } 1287 return NULL; 1288 } 1289 1290 Entry * 1291 Back() 1292 { 1293 if (!m_entries.empty()) 1294 return &m_entries.back(); 1295 return NULL; 1296 } 1297 1298 const Entry * 1299 Back() const 1300 { 1301 if (!m_entries.empty()) 1302 return &m_entries.back(); 1303 return NULL; 1304 } 1305 1306 protected: 1307 Collection m_entries; 1308 }; 1309 1310 1311 //---------------------------------------------------------------------- 1312 // A simple range with data class where you get to define the type of 1313 // the range base "B", the type used for the range byte size "S", and 1314 // the type for the associated data "T". 1315 //---------------------------------------------------------------------- 1316 template <typename B, typename T> 1317 struct AddressData 1318 { 1319 typedef B BaseType; 1320 typedef T DataType; 1321 1322 BaseType addr; 1323 DataType data; 1324 1325 AddressData () : 1326 addr (), 1327 data () 1328 { 1329 } 1330 1331 AddressData (B a, DataType d) : 1332 addr (a), 1333 data (d) 1334 { 1335 } 1336 1337 bool 1338 operator < (const AddressData &rhs) const 1339 { 1340 if (this->addr == rhs.addr) 1341 return this->data < rhs.data; 1342 return this->addr < rhs.addr; 1343 } 1344 1345 bool 1346 operator == (const AddressData &rhs) const 1347 { 1348 return this->addr == rhs.addr && 1349 this->data == rhs.data; 1350 } 1351 1352 bool 1353 operator != (const AddressData &rhs) const 1354 { 1355 return this->addr != rhs.addr || 1356 this->data == rhs.data; 1357 } 1358 }; 1359 1360 1361 template <typename B, typename T, unsigned N> 1362 class AddressDataArray 1363 { 1364 public: 1365 typedef AddressData<B,T> Entry; 1366 typedef llvm::SmallVector<Entry, N> Collection; 1367 1368 1369 AddressDataArray () 1370 { 1371 } 1372 1373 ~AddressDataArray() 1374 { 1375 } 1376 1377 void 1378 Append (const Entry &entry) 1379 { 1380 m_entries.push_back (entry); 1381 } 1382 1383 void 1384 Sort () 1385 { 1386 if (m_entries.size() > 1) 1387 std::stable_sort (m_entries.begin(), m_entries.end()); 1388 } 1389 1390#ifdef ASSERT_RANGEMAP_ARE_SORTED 1391 bool 1392 IsSorted () const 1393 { 1394 typename Collection::const_iterator pos, end, prev; 1395 // First we determine if we can combine any of the Entry objects so we 1396 // don't end up allocating and making a new collection for no reason 1397 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 1398 { 1399 if (prev != end && *pos < *prev) 1400 return false; 1401 } 1402 return true; 1403 } 1404#endif 1405 1406 void 1407 Clear () 1408 { 1409 m_entries.clear(); 1410 } 1411 1412 bool 1413 IsEmpty () const 1414 { 1415 return m_entries.empty(); 1416 } 1417 1418 size_t 1419 GetSize () const 1420 { 1421 return m_entries.size(); 1422 } 1423 1424 const Entry * 1425 GetEntryAtIndex (size_t i) const 1426 { 1427 if (i<m_entries.size()) 1428 return &m_entries[i]; 1429 return NULL; 1430 } 1431 1432 // Clients must ensure that "i" is a valid index prior to calling this function 1433 const Entry & 1434 GetEntryRef (size_t i) const 1435 { 1436 return m_entries[i]; 1437 } 1438 1439 static bool 1440 BaseLessThan (const Entry& lhs, const Entry& rhs) 1441 { 1442 return lhs.addr < rhs.addr; 1443 } 1444 1445 Entry * 1446 FindEntry (B addr, bool exact_match_only) 1447 { 1448#ifdef ASSERT_RANGEMAP_ARE_SORTED 1449 assert (IsSorted()); 1450#endif 1451 if ( !m_entries.empty() ) 1452 { 1453 Entry entry; 1454 entry.addr = addr; 1455 typename Collection::iterator begin = m_entries.begin(); 1456 typename Collection::iterator end = m_entries.end(); 1457 typename Collection::iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 1458 1459 if (pos != end) 1460 { 1461 if (pos->addr == addr || !exact_match_only) 1462 return &(*pos); 1463 } 1464 } 1465 return NULL; 1466 } 1467 1468 const Entry * 1469 FindNextEntry (const Entry *entry) 1470 { 1471 if (entry >= &*m_entries.begin() && entry + 1 < &*m_entries.end()) 1472 return entry + 1; 1473 return NULL; 1474 } 1475 1476 Entry * 1477 Back() 1478 { 1479 if (!m_entries.empty()) 1480 return &m_entries.back(); 1481 return NULL; 1482 } 1483 1484 const Entry * 1485 Back() const 1486 { 1487 if (!m_entries.empty()) 1488 return &m_entries.back(); 1489 return NULL; 1490 } 1491 1492 protected: 1493 Collection m_entries; 1494 }; 1495 1496} // namespace lldb_private 1497 1498#endif // liblldb_RangeMap_h_ 1499