1 //===-- RangeMap.h ----------------------------------------------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #ifndef LLDB_UTILITY_RANGEMAP_H 10 #define LLDB_UTILITY_RANGEMAP_H 11 12 #include <algorithm> 13 #include <vector> 14 15 #include "llvm/ADT/SmallVector.h" 16 17 #include "lldb/lldb-private.h" 18 19 // Uncomment to make sure all Range objects are sorted when needed 20 //#define ASSERT_RANGEMAP_ARE_SORTED 21 22 namespace lldb_private { 23 24 // Templatized classes for dealing with generic ranges and also collections of 25 // ranges, or collections of ranges that have associated data. 26 27 // A simple range class where you get to define the type of the range 28 // base "B", and the type used for the range byte size "S". 29 template <typename B, typename S> struct Range { 30 typedef B BaseType; 31 typedef S SizeType; 32 33 BaseType base; 34 SizeType size; 35 RangeRange36 Range() : base(0), size(0) {} 37 RangeRange38 Range(BaseType b, SizeType s) : base(b), size(s) {} 39 40 void Clear(BaseType b = 0) { 41 base = b; 42 size = 0; 43 } 44 45 // Set the start value for the range, and keep the same size GetRangeBaseRange46 BaseType GetRangeBase() const { return base; } 47 SetRangeBaseRange48 void SetRangeBase(BaseType b) { base = b; } 49 SlideRange50 void Slide(BaseType slide) { base += slide; } 51 UnionRange52 bool Union(const Range &rhs) { 53 if (DoesAdjoinOrIntersect(rhs)) { 54 auto new_end = std::max<BaseType>(GetRangeEnd(), rhs.GetRangeEnd()); 55 base = std::min<BaseType>(base, rhs.base); 56 size = new_end - base; 57 return true; 58 } 59 return false; 60 } 61 GetRangeEndRange62 BaseType GetRangeEnd() const { return base + size; } 63 SetRangeEndRange64 void SetRangeEnd(BaseType end) { 65 if (end > base) 66 size = end - base; 67 else 68 size = 0; 69 } 70 GetByteSizeRange71 SizeType GetByteSize() const { return size; } 72 SetByteSizeRange73 void SetByteSize(SizeType s) { size = s; } 74 IsValidRange75 bool IsValid() const { return size > 0; } 76 ContainsRange77 bool Contains(BaseType r) const { 78 return (GetRangeBase() <= r) && (r < GetRangeEnd()); 79 } 80 ContainsEndInclusiveRange81 bool ContainsEndInclusive(BaseType r) const { 82 return (GetRangeBase() <= r) && (r <= GetRangeEnd()); 83 } 84 ContainsRange85 bool Contains(const Range &range) const { 86 return Contains(range.GetRangeBase()) && 87 ContainsEndInclusive(range.GetRangeEnd()); 88 } 89 90 // Returns true if the two ranges adjoing or intersect DoesAdjoinOrIntersectRange91 bool DoesAdjoinOrIntersect(const Range &rhs) const { 92 const BaseType lhs_base = this->GetRangeBase(); 93 const BaseType rhs_base = rhs.GetRangeBase(); 94 const BaseType lhs_end = this->GetRangeEnd(); 95 const BaseType rhs_end = rhs.GetRangeEnd(); 96 bool result = (lhs_base <= rhs_end) && (lhs_end >= rhs_base); 97 return result; 98 } 99 100 // Returns true if the two ranges intersect DoesIntersectRange101 bool DoesIntersect(const Range &rhs) const { 102 const BaseType lhs_base = this->GetRangeBase(); 103 const BaseType rhs_base = rhs.GetRangeBase(); 104 const BaseType lhs_end = this->GetRangeEnd(); 105 const BaseType rhs_end = rhs.GetRangeEnd(); 106 bool result = (lhs_base < rhs_end) && (lhs_end > rhs_base); 107 return result; 108 } 109 110 bool operator<(const Range &rhs) const { 111 if (base == rhs.base) 112 return size < rhs.size; 113 return base < rhs.base; 114 } 115 116 bool operator==(const Range &rhs) const { 117 return base == rhs.base && size == rhs.size; 118 } 119 120 bool operator!=(const Range &rhs) const { 121 return base != rhs.base || size != rhs.size; 122 } 123 }; 124 125 template <typename B, typename S, unsigned N = 0> class RangeVector { 126 public: 127 typedef B BaseType; 128 typedef S SizeType; 129 typedef Range<B, S> Entry; 130 typedef llvm::SmallVector<Entry, N> Collection; 131 132 RangeVector() = default; 133 134 ~RangeVector() = default; 135 Append(const Entry & entry)136 void Append(const Entry &entry) { m_entries.push_back(entry); } 137 Append(B base,S size)138 void Append(B base, S size) { m_entries.emplace_back(base, size); } 139 140 // Insert an item into a sorted list and optionally combine it with any 141 // adjacent blocks if requested. Insert(const Entry & entry,bool combine)142 void Insert(const Entry &entry, bool combine) { 143 if (m_entries.empty()) { 144 m_entries.push_back(entry); 145 return; 146 } 147 auto begin = m_entries.begin(); 148 auto end = m_entries.end(); 149 auto pos = std::lower_bound(begin, end, entry); 150 if (combine) { 151 if (pos != end && pos->Union(entry)) { 152 CombinePrevAndNext(pos); 153 return; 154 } 155 if (pos != begin) { 156 auto prev = pos - 1; 157 if (prev->Union(entry)) { 158 CombinePrevAndNext(prev); 159 return; 160 } 161 } 162 } 163 m_entries.insert(pos, entry); 164 } 165 RemoveEntryAtIndex(uint32_t idx)166 bool RemoveEntryAtIndex(uint32_t idx) { 167 if (idx < m_entries.size()) { 168 m_entries.erase(m_entries.begin() + idx); 169 return true; 170 } 171 return false; 172 } 173 Sort()174 void Sort() { 175 if (m_entries.size() > 1) 176 std::stable_sort(m_entries.begin(), m_entries.end()); 177 } 178 179 #ifdef ASSERT_RANGEMAP_ARE_SORTED IsSorted()180 bool IsSorted() const { 181 typename Collection::const_iterator pos, end, prev; 182 // First we determine if we can combine any of the Entry objects so we 183 // don't end up allocating and making a new collection for no reason 184 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; 185 prev = pos++) { 186 if (prev != end && *pos < *prev) 187 return false; 188 } 189 return true; 190 } 191 #endif 192 CombineConsecutiveRanges()193 void CombineConsecutiveRanges() { 194 #ifdef ASSERT_RANGEMAP_ARE_SORTED 195 assert(IsSorted()); 196 #endif 197 auto first_intersect = std::adjacent_find( 198 m_entries.begin(), m_entries.end(), [](const Entry &a, const Entry &b) { 199 return a.DoesAdjoinOrIntersect(b); 200 }); 201 if (first_intersect == m_entries.end()) 202 return; 203 204 // We we can combine at least one entry, then we make a new collection and 205 // populate it accordingly, and then swap it into place. 206 auto pos = std::next(first_intersect); 207 Collection minimal_ranges(m_entries.begin(), pos); 208 for (; pos != m_entries.end(); ++pos) { 209 Entry &back = minimal_ranges.back(); 210 if (back.DoesAdjoinOrIntersect(*pos)) 211 back.SetRangeEnd(std::max(back.GetRangeEnd(), pos->GetRangeEnd())); 212 else 213 minimal_ranges.push_back(*pos); 214 } 215 m_entries.swap(minimal_ranges); 216 } 217 GetMinRangeBase(BaseType fail_value)218 BaseType GetMinRangeBase(BaseType fail_value) const { 219 #ifdef ASSERT_RANGEMAP_ARE_SORTED 220 assert(IsSorted()); 221 #endif 222 if (m_entries.empty()) 223 return fail_value; 224 // m_entries must be sorted, so if we aren't empty, we grab the first 225 // range's base 226 return m_entries.front().GetRangeBase(); 227 } 228 GetMaxRangeEnd(BaseType fail_value)229 BaseType GetMaxRangeEnd(BaseType fail_value) const { 230 #ifdef ASSERT_RANGEMAP_ARE_SORTED 231 assert(IsSorted()); 232 #endif 233 if (m_entries.empty()) 234 return fail_value; 235 // m_entries must be sorted, so if we aren't empty, we grab the last 236 // range's end 237 return m_entries.back().GetRangeEnd(); 238 } 239 Slide(BaseType slide)240 void Slide(BaseType slide) { 241 typename Collection::iterator pos, end; 242 for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos) 243 pos->Slide(slide); 244 } 245 Clear()246 void Clear() { m_entries.clear(); } 247 Reserve(typename Collection::size_type size)248 void Reserve(typename Collection::size_type size) { m_entries.reserve(size); } 249 IsEmpty()250 bool IsEmpty() const { return m_entries.empty(); } 251 GetSize()252 size_t GetSize() const { return m_entries.size(); } 253 GetEntryAtIndex(size_t i)254 const Entry *GetEntryAtIndex(size_t i) const { 255 return ((i < m_entries.size()) ? &m_entries[i] : nullptr); 256 } 257 258 // Clients must ensure that "i" is a valid index prior to calling this 259 // function GetEntryRef(size_t i)260 Entry &GetEntryRef(size_t i) { return m_entries[i]; } GetEntryRef(size_t i)261 const Entry &GetEntryRef(size_t i) const { return m_entries[i]; } 262 Back()263 Entry *Back() { return (m_entries.empty() ? nullptr : &m_entries.back()); } 264 Back()265 const Entry *Back() const { 266 return (m_entries.empty() ? nullptr : &m_entries.back()); 267 } 268 BaseLessThan(const Entry & lhs,const Entry & rhs)269 static bool BaseLessThan(const Entry &lhs, const Entry &rhs) { 270 return lhs.GetRangeBase() < rhs.GetRangeBase(); 271 } 272 FindEntryIndexThatContains(B addr)273 uint32_t FindEntryIndexThatContains(B addr) const { 274 #ifdef ASSERT_RANGEMAP_ARE_SORTED 275 assert(IsSorted()); 276 #endif 277 if (!m_entries.empty()) { 278 Entry entry(addr, 1); 279 typename Collection::const_iterator begin = m_entries.begin(); 280 typename Collection::const_iterator end = m_entries.end(); 281 typename Collection::const_iterator pos = 282 std::lower_bound(begin, end, entry, BaseLessThan); 283 284 if (pos != end && pos->Contains(addr)) { 285 return std::distance(begin, pos); 286 } else if (pos != begin) { 287 --pos; 288 if (pos->Contains(addr)) 289 return std::distance(begin, pos); 290 } 291 } 292 return UINT32_MAX; 293 } 294 FindEntryThatContains(B addr)295 const Entry *FindEntryThatContains(B addr) const { 296 #ifdef ASSERT_RANGEMAP_ARE_SORTED 297 assert(IsSorted()); 298 #endif 299 if (!m_entries.empty()) { 300 Entry entry(addr, 1); 301 typename Collection::const_iterator begin = m_entries.begin(); 302 typename Collection::const_iterator end = m_entries.end(); 303 typename Collection::const_iterator pos = 304 std::lower_bound(begin, end, entry, BaseLessThan); 305 306 if (pos != end && pos->Contains(addr)) { 307 return &(*pos); 308 } else if (pos != begin) { 309 --pos; 310 if (pos->Contains(addr)) { 311 return &(*pos); 312 } 313 } 314 } 315 return nullptr; 316 } 317 FindEntryThatContains(const Entry & range)318 const Entry *FindEntryThatContains(const Entry &range) const { 319 #ifdef ASSERT_RANGEMAP_ARE_SORTED 320 assert(IsSorted()); 321 #endif 322 if (!m_entries.empty()) { 323 typename Collection::const_iterator begin = m_entries.begin(); 324 typename Collection::const_iterator end = m_entries.end(); 325 typename Collection::const_iterator pos = 326 std::lower_bound(begin, end, range, BaseLessThan); 327 328 if (pos != end && pos->Contains(range)) { 329 return &(*pos); 330 } else if (pos != begin) { 331 --pos; 332 if (pos->Contains(range)) { 333 return &(*pos); 334 } 335 } 336 } 337 return nullptr; 338 } 339 340 using const_iterator = typename Collection::const_iterator; begin()341 const_iterator begin() const { return m_entries.begin(); } end()342 const_iterator end() const { return m_entries.end(); } 343 344 protected: CombinePrevAndNext(typename Collection::iterator pos)345 void CombinePrevAndNext(typename Collection::iterator pos) { 346 // Check if the prev or next entries in case they need to be unioned with 347 // the entry pointed to by "pos". 348 if (pos != m_entries.begin()) { 349 auto prev = pos - 1; 350 if (prev->Union(*pos)) 351 m_entries.erase(pos); 352 pos = prev; 353 } 354 355 auto end = m_entries.end(); 356 if (pos != end) { 357 auto next = pos + 1; 358 if (next != end) { 359 if (pos->Union(*next)) 360 m_entries.erase(next); 361 } 362 } 363 return; 364 } 365 366 Collection m_entries; 367 }; 368 369 // A simple range with data class where you get to define the type of 370 // the range base "B", the type used for the range byte size "S", and the type 371 // for the associated data "T". 372 template <typename B, typename S, typename T> 373 struct RangeData : public Range<B, S> { 374 typedef T DataType; 375 376 DataType data; 377 RangeDataRangeData378 RangeData() : Range<B, S>(), data() {} 379 RangeDataRangeData380 RangeData(B base, S size) : Range<B, S>(base, size), data() {} 381 RangeDataRangeData382 RangeData(B base, S size, DataType d) : Range<B, S>(base, size), data(d) {} 383 }; 384 385 // We can treat the vector as a flattened Binary Search Tree, augmenting it 386 // with upper bounds (max of range endpoints) for every index allows us to 387 // query for range containment quicker. 388 template <typename B, typename S, typename T> 389 struct AugmentedRangeData : public RangeData<B, S, T> { 390 B upper_bound; 391 AugmentedRangeDataAugmentedRangeData392 AugmentedRangeData(const RangeData<B, S, T> &rd) 393 : RangeData<B, S, T>(rd), upper_bound() {} 394 }; 395 396 template <typename B, typename S, typename T, unsigned N = 0, 397 class Compare = std::less<T>> 398 class RangeDataVector { 399 public: 400 typedef lldb_private::Range<B, S> Range; 401 typedef RangeData<B, S, T> Entry; 402 typedef AugmentedRangeData<B, S, T> AugmentedEntry; 403 typedef llvm::SmallVector<AugmentedEntry, N> Collection; 404 m_compare(compare)405 RangeDataVector(Compare compare = Compare()) : m_compare(compare) {} 406 407 ~RangeDataVector() = default; 408 Append(const Entry & entry)409 void Append(const Entry &entry) { m_entries.emplace_back(entry); } 410 Sort()411 void Sort() { 412 if (m_entries.size() > 1) 413 std::stable_sort(m_entries.begin(), m_entries.end(), 414 [&compare = m_compare](const Entry &a, const Entry &b) { 415 if (a.base != b.base) 416 return a.base < b.base; 417 if (a.size != b.size) 418 return a.size < b.size; 419 return compare(a.data, b.data); 420 }); 421 if (!m_entries.empty()) 422 ComputeUpperBounds(0, m_entries.size()); 423 } 424 425 #ifdef ASSERT_RANGEMAP_ARE_SORTED IsSorted()426 bool IsSorted() const { 427 typename Collection::const_iterator pos, end, prev; 428 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; 429 prev = pos++) { 430 if (prev != end && *pos < *prev) 431 return false; 432 } 433 return true; 434 } 435 #endif 436 CombineConsecutiveEntriesWithEqualData()437 void CombineConsecutiveEntriesWithEqualData() { 438 #ifdef ASSERT_RANGEMAP_ARE_SORTED 439 assert(IsSorted()); 440 #endif 441 typename Collection::iterator pos; 442 typename Collection::iterator end; 443 typename Collection::iterator prev; 444 bool can_combine = false; 445 // First we determine if we can combine any of the Entry objects so we 446 // don't end up allocating and making a new collection for no reason 447 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; 448 prev = pos++) { 449 if (prev != end && prev->data == pos->data) { 450 can_combine = true; 451 break; 452 } 453 } 454 455 // We we can combine at least one entry, then we make a new collection and 456 // populate it accordingly, and then swap it into place. 457 if (can_combine) { 458 Collection minimal_ranges; 459 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; 460 pos != end; prev = pos++) { 461 if (prev != end && prev->data == pos->data) 462 minimal_ranges.back().SetRangeEnd(pos->GetRangeEnd()); 463 else 464 minimal_ranges.push_back(*pos); 465 } 466 // Use the swap technique in case our new vector is much smaller. We must 467 // swap when using the STL because std::vector objects never release or 468 // reduce the memory once it has been allocated/reserved. 469 m_entries.swap(minimal_ranges); 470 } 471 } 472 Clear()473 void Clear() { m_entries.clear(); } 474 IsEmpty()475 bool IsEmpty() const { return m_entries.empty(); } 476 GetSize()477 size_t GetSize() const { return m_entries.size(); } 478 GetEntryAtIndex(size_t i)479 const Entry *GetEntryAtIndex(size_t i) const { 480 return ((i < m_entries.size()) ? &m_entries[i] : nullptr); 481 } 482 GetMutableEntryAtIndex(size_t i)483 Entry *GetMutableEntryAtIndex(size_t i) { 484 return ((i < m_entries.size()) ? &m_entries[i] : nullptr); 485 } 486 487 // Clients must ensure that "i" is a valid index prior to calling this 488 // function GetEntryRef(size_t i)489 Entry &GetEntryRef(size_t i) { return m_entries[i]; } GetEntryRef(size_t i)490 const Entry &GetEntryRef(size_t i) const { return m_entries[i]; } 491 BaseLessThan(const Entry & lhs,const Entry & rhs)492 static bool BaseLessThan(const Entry &lhs, const Entry &rhs) { 493 return lhs.GetRangeBase() < rhs.GetRangeBase(); 494 } 495 FindEntryIndexThatContains(B addr)496 uint32_t FindEntryIndexThatContains(B addr) const { 497 const AugmentedEntry *entry = 498 static_cast<const AugmentedEntry *>(FindEntryThatContains(addr)); 499 if (entry) 500 return std::distance(m_entries.begin(), entry); 501 return UINT32_MAX; 502 } 503 FindEntryIndexesThatContain(B addr,std::vector<uint32_t> & indexes)504 uint32_t FindEntryIndexesThatContain(B addr, std::vector<uint32_t> &indexes) { 505 #ifdef ASSERT_RANGEMAP_ARE_SORTED 506 assert(IsSorted()); 507 #endif 508 if (!m_entries.empty()) 509 FindEntryIndexesThatContain(addr, 0, m_entries.size(), indexes); 510 511 return indexes.size(); 512 } 513 FindEntryThatContains(B addr)514 Entry *FindEntryThatContains(B addr) { 515 return const_cast<Entry *>( 516 static_cast<const RangeDataVector *>(this)->FindEntryThatContains( 517 addr)); 518 } 519 FindEntryThatContains(B addr)520 const Entry *FindEntryThatContains(B addr) const { 521 return FindEntryThatContains(Entry(addr, 1)); 522 } 523 FindEntryThatContains(const Entry & range)524 const Entry *FindEntryThatContains(const Entry &range) const { 525 #ifdef ASSERT_RANGEMAP_ARE_SORTED 526 assert(IsSorted()); 527 #endif 528 if (!m_entries.empty()) { 529 typename Collection::const_iterator begin = m_entries.begin(); 530 typename Collection::const_iterator end = m_entries.end(); 531 typename Collection::const_iterator pos = 532 std::lower_bound(begin, end, range, BaseLessThan); 533 534 while (pos != begin && pos[-1].Contains(range)) 535 --pos; 536 537 if (pos != end && pos->Contains(range)) 538 return &(*pos); 539 } 540 return nullptr; 541 } 542 FindEntryStartsAt(B addr)543 const Entry *FindEntryStartsAt(B addr) const { 544 #ifdef ASSERT_RANGEMAP_ARE_SORTED 545 assert(IsSorted()); 546 #endif 547 if (!m_entries.empty()) { 548 auto begin = m_entries.begin(), end = m_entries.end(); 549 auto pos = std::lower_bound(begin, end, Entry(addr, 1), BaseLessThan); 550 if (pos != end && pos->base == addr) 551 return &(*pos); 552 } 553 return nullptr; 554 } 555 556 // This method will return the entry that contains the given address, or the 557 // entry following that address. If you give it an address of 0 and the 558 // first entry starts at address 0x100, you will get the entry at 0x100. 559 // 560 // For most uses, FindEntryThatContains is the correct one to use, this is a 561 // less commonly needed behavior. It was added for core file memory regions, 562 // where we want to present a gap in the memory regions as a distinct region, 563 // so we need to know the start address of the next memory section that 564 // exists. FindEntryThatContainsOrFollows(B addr)565 const Entry *FindEntryThatContainsOrFollows(B addr) const { 566 #ifdef ASSERT_RANGEMAP_ARE_SORTED 567 assert(IsSorted()); 568 #endif 569 if (!m_entries.empty()) { 570 typename Collection::const_iterator begin = m_entries.begin(); 571 typename Collection::const_iterator end = m_entries.end(); 572 typename Collection::const_iterator pos = 573 std::lower_bound(m_entries.begin(), end, addr, 574 [](const Entry &lhs, B rhs_base) -> bool { 575 return lhs.GetRangeEnd() <= rhs_base; 576 }); 577 578 while (pos != begin && pos[-1].Contains(addr)) 579 --pos; 580 581 if (pos != end) 582 return &(*pos); 583 } 584 return nullptr; 585 } 586 Back()587 Entry *Back() { return (m_entries.empty() ? nullptr : &m_entries.back()); } 588 Back()589 const Entry *Back() const { 590 return (m_entries.empty() ? nullptr : &m_entries.back()); 591 } 592 593 protected: 594 Collection m_entries; 595 Compare m_compare; 596 597 private: 598 // Compute extra information needed for search ComputeUpperBounds(size_t lo,size_t hi)599 B ComputeUpperBounds(size_t lo, size_t hi) { 600 size_t mid = (lo + hi) / 2; 601 AugmentedEntry &entry = m_entries[mid]; 602 603 entry.upper_bound = entry.base + entry.size; 604 605 if (lo < mid) 606 entry.upper_bound = 607 std::max(entry.upper_bound, ComputeUpperBounds(lo, mid)); 608 609 if (mid + 1 < hi) 610 entry.upper_bound = 611 std::max(entry.upper_bound, ComputeUpperBounds(mid + 1, hi)); 612 613 return entry.upper_bound; 614 } 615 616 // This is based on the augmented tree implementation found at 617 // https://en.wikipedia.org/wiki/Interval_tree#Augmented_tree FindEntryIndexesThatContain(B addr,size_t lo,size_t hi,std::vector<uint32_t> & indexes)618 void FindEntryIndexesThatContain(B addr, size_t lo, size_t hi, 619 std::vector<uint32_t> &indexes) { 620 size_t mid = (lo + hi) / 2; 621 const AugmentedEntry &entry = m_entries[mid]; 622 623 // addr is greater than the rightmost point of any interval below mid 624 // so there are cannot be any matches. 625 if (addr > entry.upper_bound) 626 return; 627 628 // Recursively search left subtree 629 if (lo < mid) 630 FindEntryIndexesThatContain(addr, lo, mid, indexes); 631 632 // If addr is smaller than the start of the current interval it 633 // cannot contain it nor can any of its right subtree. 634 if (addr < entry.base) 635 return; 636 637 if (entry.Contains(addr)) 638 indexes.push_back(entry.data); 639 640 // Recursively search right subtree 641 if (mid + 1 < hi) 642 FindEntryIndexesThatContain(addr, mid + 1, hi, indexes); 643 } 644 }; 645 646 // A simple range with data class where you get to define the type of 647 // the range base "B", the type used for the range byte size "S", and the type 648 // for the associated data "T". 649 template <typename B, typename T> struct AddressData { 650 typedef B BaseType; 651 typedef T DataType; 652 653 BaseType addr; 654 DataType data; 655 AddressDataAddressData656 AddressData() : addr(), data() {} 657 AddressDataAddressData658 AddressData(B a, DataType d) : addr(a), data(d) {} 659 660 bool operator<(const AddressData &rhs) const { 661 if (this->addr == rhs.addr) 662 return this->data < rhs.data; 663 return this->addr < rhs.addr; 664 } 665 666 bool operator==(const AddressData &rhs) const { 667 return this->addr == rhs.addr && this->data == rhs.data; 668 } 669 670 bool operator!=(const AddressData &rhs) const { 671 return this->addr != rhs.addr || this->data == rhs.data; 672 } 673 }; 674 675 template <typename B, typename T, unsigned N> class AddressDataArray { 676 public: 677 typedef AddressData<B, T> Entry; 678 typedef llvm::SmallVector<Entry, N> Collection; 679 680 AddressDataArray() = default; 681 682 ~AddressDataArray() = default; 683 Append(const Entry & entry)684 void Append(const Entry &entry) { m_entries.push_back(entry); } 685 Sort()686 void Sort() { 687 if (m_entries.size() > 1) 688 std::stable_sort(m_entries.begin(), m_entries.end()); 689 } 690 691 #ifdef ASSERT_RANGEMAP_ARE_SORTED IsSorted()692 bool IsSorted() const { 693 typename Collection::const_iterator pos, end, prev; 694 // First we determine if we can combine any of the Entry objects so we 695 // don't end up allocating and making a new collection for no reason 696 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; 697 prev = pos++) { 698 if (prev != end && *pos < *prev) 699 return false; 700 } 701 return true; 702 } 703 #endif 704 Clear()705 void Clear() { m_entries.clear(); } 706 IsEmpty()707 bool IsEmpty() const { return m_entries.empty(); } 708 GetSize()709 size_t GetSize() const { return m_entries.size(); } 710 GetEntryAtIndex(size_t i)711 const Entry *GetEntryAtIndex(size_t i) const { 712 return ((i < m_entries.size()) ? &m_entries[i] : nullptr); 713 } 714 715 // Clients must ensure that "i" is a valid index prior to calling this 716 // function GetEntryRef(size_t i)717 const Entry &GetEntryRef(size_t i) const { return m_entries[i]; } 718 BaseLessThan(const Entry & lhs,const Entry & rhs)719 static bool BaseLessThan(const Entry &lhs, const Entry &rhs) { 720 return lhs.addr < rhs.addr; 721 } 722 FindEntry(B addr,bool exact_match_only)723 Entry *FindEntry(B addr, bool exact_match_only) { 724 #ifdef ASSERT_RANGEMAP_ARE_SORTED 725 assert(IsSorted()); 726 #endif 727 if (!m_entries.empty()) { 728 Entry entry; 729 entry.addr = addr; 730 typename Collection::iterator begin = m_entries.begin(); 731 typename Collection::iterator end = m_entries.end(); 732 typename Collection::iterator pos = 733 std::lower_bound(begin, end, entry, BaseLessThan); 734 735 while (pos != begin && pos[-1].addr == addr) 736 --pos; 737 738 if (pos != end) { 739 if (pos->addr == addr || !exact_match_only) 740 return &(*pos); 741 } 742 } 743 return nullptr; 744 } 745 FindNextEntry(const Entry * entry)746 const Entry *FindNextEntry(const Entry *entry) { 747 if (entry >= &*m_entries.begin() && entry + 1 < &*m_entries.end()) 748 return entry + 1; 749 return nullptr; 750 } 751 Back()752 Entry *Back() { return (m_entries.empty() ? nullptr : &m_entries.back()); } 753 Back()754 const Entry *Back() const { 755 return (m_entries.empty() ? nullptr : &m_entries.back()); 756 } 757 758 protected: 759 Collection m_entries; 760 }; 761 762 } // namespace lldb_private 763 764 #endif // LLDB_UTILITY_RANGEMAP_H 765