1254721Semaste//===-- RangeMap.h ----------------------------------------------*- C++ -*-===// 2254721Semaste// 3254721Semaste// The LLVM Compiler Infrastructure 4254721Semaste// 5254721Semaste// This file is distributed under the University of Illinois Open Source 6254721Semaste// License. See LICENSE.TXT for details. 7254721Semaste// 8254721Semaste//===----------------------------------------------------------------------===// 9254721Semaste 10254721Semaste#ifndef liblldb_RangeMap_h_ 11254721Semaste#define liblldb_RangeMap_h_ 12254721Semaste 13296417Sdim// C Includes 14296417Sdim// C++ Includes 15296417Sdim#include <algorithm> 16254721Semaste#include <vector> 17254721Semaste 18296417Sdim// Other libraries and framework includes 19254721Semaste#include "llvm/ADT/SmallVector.h" 20254721Semaste 21296417Sdim// Project includes 22296417Sdim#include "lldb/lldb-private.h" 23296417Sdim 24254721Semaste// Uncomment to make sure all Range objects are sorted when needed 25254721Semaste//#define ASSERT_RANGEMAP_ARE_SORTED 26254721Semaste 27254721Semastenamespace lldb_private { 28254721Semaste 29254721Semaste //---------------------------------------------------------------------- 30254721Semaste // Templatized classes for dealing with generic ranges and also 31254721Semaste // collections of ranges, or collections of ranges that have associated 32254721Semaste // data. 33254721Semaste //---------------------------------------------------------------------- 34254721Semaste 35254721Semaste //---------------------------------------------------------------------- 36254721Semaste // A simple range class where you get to define the type of the range 37254721Semaste // base "B", and the type used for the range byte size "S". 38254721Semaste //---------------------------------------------------------------------- 39254721Semaste template <typename B, typename S> 40254721Semaste struct Range 41254721Semaste { 42254721Semaste typedef B BaseType; 43254721Semaste typedef S SizeType; 44254721Semaste 45254721Semaste BaseType base; 46254721Semaste SizeType size; 47254721Semaste 48254721Semaste Range () : 49254721Semaste base (0), 50254721Semaste size (0) 51254721Semaste { 52254721Semaste } 53254721Semaste 54254721Semaste Range (BaseType b, SizeType s) : 55254721Semaste base (b), 56254721Semaste size (s) 57254721Semaste { 58254721Semaste } 59254721Semaste 60254721Semaste void 61254721Semaste Clear (BaseType b = 0) 62254721Semaste { 63254721Semaste base = b; 64254721Semaste size = 0; 65254721Semaste } 66254721Semaste 67254721Semaste // Set the start value for the range, and keep the same size 68254721Semaste BaseType 69254721Semaste GetRangeBase () const 70254721Semaste { 71254721Semaste return base; 72254721Semaste } 73254721Semaste 74254721Semaste void 75254721Semaste SetRangeBase (BaseType b) 76254721Semaste { 77254721Semaste base = b; 78254721Semaste } 79254721Semaste 80254721Semaste void 81254721Semaste Slide (BaseType slide) 82254721Semaste { 83254721Semaste base += slide; 84254721Semaste } 85254721Semaste 86254721Semaste BaseType 87254721Semaste GetRangeEnd () const 88254721Semaste { 89254721Semaste return base + size; 90254721Semaste } 91254721Semaste 92254721Semaste void 93254721Semaste SetRangeEnd (BaseType end) 94254721Semaste { 95254721Semaste if (end > base) 96254721Semaste size = end - base; 97254721Semaste else 98254721Semaste size = 0; 99254721Semaste } 100254721Semaste 101254721Semaste SizeType 102254721Semaste GetByteSize () const 103254721Semaste { 104254721Semaste return size; 105254721Semaste } 106254721Semaste 107254721Semaste void 108254721Semaste SetByteSize (SizeType s) 109254721Semaste { 110254721Semaste size = s; 111254721Semaste } 112254721Semaste 113254721Semaste bool 114254721Semaste IsValid() const 115254721Semaste { 116254721Semaste return size > 0; 117254721Semaste } 118254721Semaste 119254721Semaste bool 120254721Semaste Contains (BaseType r) const 121254721Semaste { 122254721Semaste return (GetRangeBase() <= r) && (r < GetRangeEnd()); 123254721Semaste } 124254721Semaste 125254721Semaste bool 126254721Semaste ContainsEndInclusive (BaseType r) const 127254721Semaste { 128254721Semaste return (GetRangeBase() <= r) && (r <= GetRangeEnd()); 129254721Semaste } 130254721Semaste 131254721Semaste bool 132254721Semaste Contains (const Range& range) const 133254721Semaste { 134254721Semaste return Contains(range.GetRangeBase()) && ContainsEndInclusive(range.GetRangeEnd()); 135254721Semaste } 136288943Sdim 137288943Sdim // Returns true if the two ranges adjoing or intersect 138254721Semaste bool 139288943Sdim DoesAdjoinOrIntersect (const Range &rhs) const 140254721Semaste { 141254721Semaste const BaseType lhs_base = this->GetRangeBase(); 142254721Semaste const BaseType rhs_base = rhs.GetRangeBase(); 143254721Semaste const BaseType lhs_end = this->GetRangeEnd(); 144254721Semaste const BaseType rhs_end = rhs.GetRangeEnd(); 145254721Semaste bool result = (lhs_base <= rhs_end) && (lhs_end >= rhs_base); 146254721Semaste return result; 147254721Semaste } 148288943Sdim 149288943Sdim // Returns true if the two ranges intersect 150254721Semaste bool 151288943Sdim DoesIntersect (const Range &rhs) const 152288943Sdim { 153288943Sdim const BaseType lhs_base = this->GetRangeBase(); 154288943Sdim const BaseType rhs_base = rhs.GetRangeBase(); 155288943Sdim const BaseType lhs_end = this->GetRangeEnd(); 156288943Sdim const BaseType rhs_end = rhs.GetRangeEnd(); 157288943Sdim bool result = (lhs_base < rhs_end) && (lhs_end > rhs_base); 158288943Sdim return result; 159288943Sdim } 160288943Sdim 161288943Sdim bool 162254721Semaste operator < (const Range &rhs) const 163254721Semaste { 164254721Semaste if (base == rhs.base) 165254721Semaste return size < rhs.size; 166254721Semaste return base < rhs.base; 167254721Semaste } 168254721Semaste 169254721Semaste bool 170254721Semaste operator == (const Range &rhs) const 171254721Semaste { 172254721Semaste return base == rhs.base && size == rhs.size; 173254721Semaste } 174254721Semaste 175254721Semaste bool 176254721Semaste operator != (const Range &rhs) const 177254721Semaste { 178254721Semaste return base != rhs.base || size != rhs.size; 179254721Semaste } 180254721Semaste }; 181254721Semaste 182254721Semaste //---------------------------------------------------------------------- 183254721Semaste // A range array class where you get to define the type of the ranges 184254721Semaste // that the collection contains. 185254721Semaste //---------------------------------------------------------------------- 186254721Semaste 187254721Semaste template <typename B, typename S, unsigned N> 188254721Semaste class RangeArray 189254721Semaste { 190254721Semaste public: 191254721Semaste typedef B BaseType; 192254721Semaste typedef S SizeType; 193254721Semaste typedef Range<B,S> Entry; 194254721Semaste typedef llvm::SmallVector<Entry, N> Collection; 195296417Sdim 196296417Sdim RangeArray() = default; 197296417Sdim 198296417Sdim ~RangeArray() = default; 199296417Sdim 200254721Semaste void 201254721Semaste Append (const Entry &entry) 202254721Semaste { 203254721Semaste m_entries.push_back (entry); 204254721Semaste } 205254721Semaste 206254721Semaste bool 207254721Semaste RemoveEntrtAtIndex (uint32_t idx) 208254721Semaste { 209254721Semaste if (idx < m_entries.size()) 210254721Semaste { 211254721Semaste m_entries.erase (m_entries.begin() + idx); 212254721Semaste return true; 213254721Semaste } 214254721Semaste return false; 215254721Semaste } 216254721Semaste 217254721Semaste void 218254721Semaste Sort () 219254721Semaste { 220254721Semaste if (m_entries.size() > 1) 221254721Semaste std::stable_sort (m_entries.begin(), m_entries.end()); 222254721Semaste } 223254721Semaste 224254721Semaste#ifdef ASSERT_RANGEMAP_ARE_SORTED 225254721Semaste bool 226254721Semaste IsSorted () const 227254721Semaste { 228254721Semaste typename Collection::const_iterator pos, end, prev; 229254721Semaste // First we determine if we can combine any of the Entry objects so we 230254721Semaste // don't end up allocating and making a new collection for no reason 231254721Semaste for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 232254721Semaste { 233254721Semaste if (prev != end && *pos < *prev) 234254721Semaste return false; 235254721Semaste } 236254721Semaste return true; 237254721Semaste } 238254721Semaste#endif 239296417Sdim 240254721Semaste void 241254721Semaste CombineConsecutiveRanges () 242254721Semaste { 243254721Semaste#ifdef ASSERT_RANGEMAP_ARE_SORTED 244254721Semaste assert (IsSorted()); 245254721Semaste#endif 246254721Semaste // Can't combine if ranges if we have zero or one range 247254721Semaste if (m_entries.size() > 1) 248254721Semaste { 249254721Semaste // The list should be sorted prior to calling this function 250254721Semaste typename Collection::iterator pos; 251254721Semaste typename Collection::iterator end; 252254721Semaste typename Collection::iterator prev; 253254721Semaste bool can_combine = false; 254254721Semaste // First we determine if we can combine any of the Entry objects so we 255254721Semaste // don't end up allocating and making a new collection for no reason 256254721Semaste for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 257254721Semaste { 258288943Sdim if (prev != end && prev->DoesAdjoinOrIntersect(*pos)) 259254721Semaste { 260254721Semaste can_combine = true; 261254721Semaste break; 262254721Semaste } 263254721Semaste } 264254721Semaste 265254721Semaste // We we can combine at least one entry, then we make a new collection 266254721Semaste // and populate it accordingly, and then swap it into place. 267254721Semaste if (can_combine) 268254721Semaste { 269254721Semaste Collection minimal_ranges; 270254721Semaste for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 271254721Semaste { 272288943Sdim if (prev != end && prev->DoesAdjoinOrIntersect(*pos)) 273254721Semaste minimal_ranges.back().SetRangeEnd (std::max<BaseType>(prev->GetRangeEnd(), pos->GetRangeEnd())); 274254721Semaste else 275254721Semaste minimal_ranges.push_back (*pos); 276254721Semaste } 277254721Semaste // Use the swap technique in case our new vector is much smaller. 278254721Semaste // We must swap when using the STL because std::vector objects never 279254721Semaste // release or reduce the memory once it has been allocated/reserved. 280254721Semaste m_entries.swap (minimal_ranges); 281254721Semaste } 282254721Semaste } 283254721Semaste } 284254721Semaste 285254721Semaste BaseType 286254721Semaste GetMinRangeBase (BaseType fail_value) const 287254721Semaste { 288254721Semaste#ifdef ASSERT_RANGEMAP_ARE_SORTED 289254721Semaste assert (IsSorted()); 290254721Semaste#endif 291254721Semaste if (m_entries.empty()) 292254721Semaste return fail_value; 293254721Semaste // m_entries must be sorted, so if we aren't empty, we grab the 294254721Semaste // first range's base 295254721Semaste return m_entries.front().GetRangeBase(); 296254721Semaste } 297254721Semaste 298254721Semaste BaseType 299254721Semaste GetMaxRangeEnd (BaseType fail_value) const 300254721Semaste { 301254721Semaste#ifdef ASSERT_RANGEMAP_ARE_SORTED 302254721Semaste assert (IsSorted()); 303254721Semaste#endif 304254721Semaste if (m_entries.empty()) 305254721Semaste return fail_value; 306254721Semaste // m_entries must be sorted, so if we aren't empty, we grab the 307254721Semaste // last range's end 308254721Semaste return m_entries.back().GetRangeEnd(); 309254721Semaste } 310254721Semaste 311254721Semaste void 312254721Semaste Slide (BaseType slide) 313254721Semaste { 314254721Semaste typename Collection::iterator pos, end; 315254721Semaste for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos) 316254721Semaste pos->Slide (slide); 317254721Semaste } 318254721Semaste 319254721Semaste void 320254721Semaste Clear () 321254721Semaste { 322254721Semaste m_entries.clear(); 323254721Semaste } 324254721Semaste 325254721Semaste bool 326254721Semaste IsEmpty () const 327254721Semaste { 328254721Semaste return m_entries.empty(); 329254721Semaste } 330254721Semaste 331254721Semaste size_t 332254721Semaste GetSize () const 333254721Semaste { 334254721Semaste return m_entries.size(); 335254721Semaste } 336254721Semaste 337254721Semaste const Entry * 338254721Semaste GetEntryAtIndex (size_t i) const 339254721Semaste { 340296417Sdim return ((i < m_entries.size()) ? &m_entries[i] : nullptr); 341254721Semaste } 342254721Semaste 343254721Semaste // Clients must ensure that "i" is a valid index prior to calling this function 344254721Semaste const Entry & 345254721Semaste GetEntryRef (size_t i) const 346254721Semaste { 347254721Semaste return m_entries[i]; 348254721Semaste } 349254721Semaste 350254721Semaste Entry * 351254721Semaste Back() 352254721Semaste { 353296417Sdim return (m_entries.empty() ? nullptr : &m_entries.back()); 354254721Semaste } 355254721Semaste 356254721Semaste const Entry * 357254721Semaste Back() const 358254721Semaste { 359296417Sdim return (m_entries.empty() ? nullptr : &m_entries.back()); 360254721Semaste } 361254721Semaste 362254721Semaste static bool 363254721Semaste BaseLessThan (const Entry& lhs, const Entry& rhs) 364254721Semaste { 365254721Semaste return lhs.GetRangeBase() < rhs.GetRangeBase(); 366254721Semaste } 367254721Semaste 368254721Semaste uint32_t 369254721Semaste FindEntryIndexThatContains (B addr) const 370254721Semaste { 371254721Semaste#ifdef ASSERT_RANGEMAP_ARE_SORTED 372254721Semaste assert (IsSorted()); 373254721Semaste#endif 374254721Semaste if (!m_entries.empty()) 375254721Semaste { 376254721Semaste Entry entry (addr, 1); 377254721Semaste typename Collection::const_iterator begin = m_entries.begin(); 378254721Semaste typename Collection::const_iterator end = m_entries.end(); 379254721Semaste typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 380254721Semaste 381254721Semaste if (pos != end && pos->Contains(addr)) 382254721Semaste { 383254721Semaste return std::distance (begin, pos); 384254721Semaste } 385254721Semaste else if (pos != begin) 386254721Semaste { 387254721Semaste --pos; 388254721Semaste if (pos->Contains(addr)) 389254721Semaste return std::distance (begin, pos); 390254721Semaste } 391254721Semaste } 392254721Semaste return UINT32_MAX; 393254721Semaste } 394254721Semaste 395254721Semaste const Entry * 396254721Semaste FindEntryThatContains (B addr) const 397254721Semaste { 398254721Semaste#ifdef ASSERT_RANGEMAP_ARE_SORTED 399254721Semaste assert (IsSorted()); 400254721Semaste#endif 401254721Semaste if (!m_entries.empty()) 402254721Semaste { 403254721Semaste Entry entry (addr, 1); 404254721Semaste typename Collection::const_iterator begin = m_entries.begin(); 405254721Semaste typename Collection::const_iterator end = m_entries.end(); 406254721Semaste typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 407254721Semaste 408254721Semaste if (pos != end && pos->Contains(addr)) 409254721Semaste { 410254721Semaste return &(*pos); 411254721Semaste } 412254721Semaste else if (pos != begin) 413254721Semaste { 414254721Semaste --pos; 415254721Semaste if (pos->Contains(addr)) 416254721Semaste { 417254721Semaste return &(*pos); 418254721Semaste } 419254721Semaste } 420254721Semaste } 421296417Sdim return nullptr; 422254721Semaste } 423254721Semaste 424254721Semaste const Entry * 425254721Semaste FindEntryThatContains (const Entry &range) const 426254721Semaste { 427254721Semaste#ifdef ASSERT_RANGEMAP_ARE_SORTED 428254721Semaste assert (IsSorted()); 429254721Semaste#endif 430254721Semaste if (!m_entries.empty()) 431254721Semaste { 432254721Semaste typename Collection::const_iterator begin = m_entries.begin(); 433254721Semaste typename Collection::const_iterator end = m_entries.end(); 434254721Semaste typename Collection::const_iterator pos = std::lower_bound (begin, end, range, BaseLessThan); 435254721Semaste 436254721Semaste if (pos != end && pos->Contains(range)) 437254721Semaste { 438254721Semaste return &(*pos); 439254721Semaste } 440254721Semaste else if (pos != begin) 441254721Semaste { 442254721Semaste --pos; 443254721Semaste if (pos->Contains(range)) 444254721Semaste { 445254721Semaste return &(*pos); 446254721Semaste } 447254721Semaste } 448254721Semaste } 449296417Sdim return nullptr; 450254721Semaste } 451254721Semaste 452254721Semaste protected: 453254721Semaste Collection m_entries; 454254721Semaste }; 455254721Semaste 456254721Semaste template <typename B, typename S> 457254721Semaste class RangeVector 458254721Semaste { 459254721Semaste public: 460254721Semaste typedef B BaseType; 461254721Semaste typedef S SizeType; 462254721Semaste typedef Range<B,S> Entry; 463254721Semaste typedef std::vector<Entry> Collection; 464296417Sdim 465296417Sdim RangeVector() = default; 466296417Sdim 467296417Sdim ~RangeVector() = default; 468296417Sdim 469254721Semaste void 470254721Semaste Append (const Entry &entry) 471254721Semaste { 472254721Semaste m_entries.push_back (entry); 473254721Semaste } 474254721Semaste 475254721Semaste bool 476254721Semaste RemoveEntrtAtIndex (uint32_t idx) 477254721Semaste { 478254721Semaste if (idx < m_entries.size()) 479254721Semaste { 480254721Semaste m_entries.erase (m_entries.begin() + idx); 481254721Semaste return true; 482254721Semaste } 483254721Semaste return false; 484254721Semaste } 485254721Semaste 486254721Semaste void 487254721Semaste Sort () 488254721Semaste { 489254721Semaste if (m_entries.size() > 1) 490254721Semaste std::stable_sort (m_entries.begin(), m_entries.end()); 491254721Semaste } 492254721Semaste 493254721Semaste#ifdef ASSERT_RANGEMAP_ARE_SORTED 494254721Semaste bool 495254721Semaste IsSorted () const 496254721Semaste { 497254721Semaste typename Collection::const_iterator pos, end, prev; 498254721Semaste // First we determine if we can combine any of the Entry objects so we 499254721Semaste // don't end up allocating and making a new collection for no reason 500254721Semaste for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 501254721Semaste { 502254721Semaste if (prev != end && *pos < *prev) 503254721Semaste return false; 504254721Semaste } 505254721Semaste return true; 506254721Semaste } 507254721Semaste#endif 508296417Sdim 509254721Semaste void 510254721Semaste CombineConsecutiveRanges () 511254721Semaste { 512254721Semaste#ifdef ASSERT_RANGEMAP_ARE_SORTED 513254721Semaste assert (IsSorted()); 514254721Semaste#endif 515254721Semaste // Can't combine if ranges if we have zero or one range 516254721Semaste if (m_entries.size() > 1) 517254721Semaste { 518254721Semaste // The list should be sorted prior to calling this function 519254721Semaste typename Collection::iterator pos; 520254721Semaste typename Collection::iterator end; 521254721Semaste typename Collection::iterator prev; 522254721Semaste bool can_combine = false; 523254721Semaste // First we determine if we can combine any of the Entry objects so we 524254721Semaste // don't end up allocating and making a new collection for no reason 525254721Semaste for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 526254721Semaste { 527288943Sdim if (prev != end && prev->DoesAdjoinOrIntersect(*pos)) 528254721Semaste { 529254721Semaste can_combine = true; 530254721Semaste break; 531254721Semaste } 532254721Semaste } 533254721Semaste 534254721Semaste // We we can combine at least one entry, then we make a new collection 535254721Semaste // and populate it accordingly, and then swap it into place. 536254721Semaste if (can_combine) 537254721Semaste { 538254721Semaste Collection minimal_ranges; 539254721Semaste for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 540254721Semaste { 541288943Sdim if (prev != end && prev->DoesAdjoinOrIntersect(*pos)) 542254721Semaste minimal_ranges.back().SetRangeEnd (std::max<BaseType>(prev->GetRangeEnd(), pos->GetRangeEnd())); 543254721Semaste else 544254721Semaste minimal_ranges.push_back (*pos); 545254721Semaste } 546254721Semaste // Use the swap technique in case our new vector is much smaller. 547254721Semaste // We must swap when using the STL because std::vector objects never 548254721Semaste // release or reduce the memory once it has been allocated/reserved. 549254721Semaste m_entries.swap (minimal_ranges); 550254721Semaste } 551254721Semaste } 552254721Semaste } 553296417Sdim 554254721Semaste BaseType 555254721Semaste GetMinRangeBase (BaseType fail_value) const 556254721Semaste { 557254721Semaste#ifdef ASSERT_RANGEMAP_ARE_SORTED 558254721Semaste assert (IsSorted()); 559254721Semaste#endif 560254721Semaste if (m_entries.empty()) 561254721Semaste return fail_value; 562254721Semaste // m_entries must be sorted, so if we aren't empty, we grab the 563254721Semaste // first range's base 564254721Semaste return m_entries.front().GetRangeBase(); 565254721Semaste } 566254721Semaste 567254721Semaste BaseType 568254721Semaste GetMaxRangeEnd (BaseType fail_value) const 569254721Semaste { 570254721Semaste#ifdef ASSERT_RANGEMAP_ARE_SORTED 571254721Semaste assert (IsSorted()); 572254721Semaste#endif 573254721Semaste if (m_entries.empty()) 574254721Semaste return fail_value; 575254721Semaste // m_entries must be sorted, so if we aren't empty, we grab the 576254721Semaste // last range's end 577254721Semaste return m_entries.back().GetRangeEnd(); 578254721Semaste } 579254721Semaste 580254721Semaste void 581254721Semaste Slide (BaseType slide) 582254721Semaste { 583254721Semaste typename Collection::iterator pos, end; 584254721Semaste for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos) 585254721Semaste pos->Slide (slide); 586254721Semaste } 587254721Semaste 588254721Semaste void 589254721Semaste Clear () 590254721Semaste { 591254721Semaste m_entries.clear(); 592254721Semaste } 593254721Semaste 594254721Semaste void 595254721Semaste Reserve (typename Collection::size_type size) 596254721Semaste { 597258054Semaste m_entries.reserve (size); 598254721Semaste } 599254721Semaste 600254721Semaste bool 601254721Semaste IsEmpty () const 602254721Semaste { 603254721Semaste return m_entries.empty(); 604254721Semaste } 605254721Semaste 606254721Semaste size_t 607254721Semaste GetSize () const 608254721Semaste { 609254721Semaste return m_entries.size(); 610254721Semaste } 611254721Semaste 612254721Semaste const Entry * 613254721Semaste GetEntryAtIndex (size_t i) const 614254721Semaste { 615296417Sdim return ((i < m_entries.size()) ? &m_entries[i] : nullptr); 616254721Semaste } 617254721Semaste 618254721Semaste // Clients must ensure that "i" is a valid index prior to calling this function 619254721Semaste const Entry & 620254721Semaste GetEntryRef (size_t i) const 621254721Semaste { 622254721Semaste return m_entries[i]; 623254721Semaste } 624254721Semaste 625254721Semaste Entry * 626254721Semaste Back() 627254721Semaste { 628296417Sdim return (m_entries.empty() ? nullptr : &m_entries.back()); 629254721Semaste } 630254721Semaste 631254721Semaste const Entry * 632254721Semaste Back() const 633254721Semaste { 634296417Sdim return (m_entries.empty() ? nullptr : &m_entries.back()); 635254721Semaste } 636254721Semaste 637254721Semaste static bool 638254721Semaste BaseLessThan (const Entry& lhs, const Entry& rhs) 639254721Semaste { 640254721Semaste return lhs.GetRangeBase() < rhs.GetRangeBase(); 641254721Semaste } 642254721Semaste 643254721Semaste uint32_t 644254721Semaste FindEntryIndexThatContains (B addr) const 645254721Semaste { 646254721Semaste#ifdef ASSERT_RANGEMAP_ARE_SORTED 647254721Semaste assert (IsSorted()); 648254721Semaste#endif 649254721Semaste if (!m_entries.empty()) 650254721Semaste { 651254721Semaste Entry entry (addr, 1); 652254721Semaste typename Collection::const_iterator begin = m_entries.begin(); 653254721Semaste typename Collection::const_iterator end = m_entries.end(); 654254721Semaste typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 655254721Semaste 656254721Semaste if (pos != end && pos->Contains(addr)) 657254721Semaste { 658254721Semaste return std::distance (begin, pos); 659254721Semaste } 660254721Semaste else if (pos != begin) 661254721Semaste { 662254721Semaste --pos; 663254721Semaste if (pos->Contains(addr)) 664254721Semaste return std::distance (begin, pos); 665254721Semaste } 666254721Semaste } 667254721Semaste return UINT32_MAX; 668254721Semaste } 669254721Semaste 670254721Semaste const Entry * 671254721Semaste FindEntryThatContains (B addr) const 672254721Semaste { 673254721Semaste#ifdef ASSERT_RANGEMAP_ARE_SORTED 674254721Semaste assert (IsSorted()); 675254721Semaste#endif 676254721Semaste if (!m_entries.empty()) 677254721Semaste { 678254721Semaste Entry entry (addr, 1); 679254721Semaste typename Collection::const_iterator begin = m_entries.begin(); 680254721Semaste typename Collection::const_iterator end = m_entries.end(); 681254721Semaste typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 682254721Semaste 683254721Semaste if (pos != end && pos->Contains(addr)) 684254721Semaste { 685254721Semaste return &(*pos); 686254721Semaste } 687254721Semaste else if (pos != begin) 688254721Semaste { 689254721Semaste --pos; 690254721Semaste if (pos->Contains(addr)) 691254721Semaste { 692254721Semaste return &(*pos); 693254721Semaste } 694254721Semaste } 695254721Semaste } 696296417Sdim return nullptr; 697254721Semaste } 698254721Semaste 699254721Semaste const Entry * 700254721Semaste FindEntryThatContains (const Entry &range) const 701254721Semaste { 702254721Semaste#ifdef ASSERT_RANGEMAP_ARE_SORTED 703254721Semaste assert (IsSorted()); 704254721Semaste#endif 705254721Semaste if (!m_entries.empty()) 706254721Semaste { 707254721Semaste typename Collection::const_iterator begin = m_entries.begin(); 708254721Semaste typename Collection::const_iterator end = m_entries.end(); 709254721Semaste typename Collection::const_iterator pos = std::lower_bound (begin, end, range, BaseLessThan); 710254721Semaste 711254721Semaste if (pos != end && pos->Contains(range)) 712254721Semaste { 713254721Semaste return &(*pos); 714254721Semaste } 715254721Semaste else if (pos != begin) 716254721Semaste { 717254721Semaste --pos; 718254721Semaste if (pos->Contains(range)) 719254721Semaste { 720254721Semaste return &(*pos); 721254721Semaste } 722254721Semaste } 723254721Semaste } 724296417Sdim return nullptr; 725254721Semaste } 726254721Semaste 727254721Semaste protected: 728254721Semaste Collection m_entries; 729254721Semaste }; 730254721Semaste 731254721Semaste //---------------------------------------------------------------------- 732254721Semaste // A simple range with data class where you get to define the type of 733254721Semaste // the range base "B", the type used for the range byte size "S", and 734254721Semaste // the type for the associated data "T". 735254721Semaste //---------------------------------------------------------------------- 736254721Semaste template <typename B, typename S, typename T> 737254721Semaste struct RangeData : public Range<B,S> 738254721Semaste { 739254721Semaste typedef T DataType; 740254721Semaste 741254721Semaste DataType data; 742254721Semaste 743254721Semaste RangeData () : 744254721Semaste Range<B,S> (), 745254721Semaste data () 746254721Semaste { 747254721Semaste } 748254721Semaste 749254721Semaste RangeData (B base, S size) : 750254721Semaste Range<B,S> (base, size), 751254721Semaste data () 752254721Semaste { 753254721Semaste } 754254721Semaste 755254721Semaste RangeData (B base, S size, DataType d) : 756254721Semaste Range<B,S> (base, size), 757254721Semaste data (d) 758254721Semaste { 759254721Semaste } 760254721Semaste 761254721Semaste bool 762254721Semaste operator < (const RangeData &rhs) const 763254721Semaste { 764254721Semaste if (this->base == rhs.base) 765254721Semaste { 766254721Semaste if (this->size == rhs.size) 767254721Semaste return this->data < rhs.data; 768254721Semaste else 769254721Semaste return this->size < rhs.size; 770254721Semaste } 771254721Semaste return this->base < rhs.base; 772254721Semaste } 773254721Semaste 774254721Semaste bool 775254721Semaste operator == (const RangeData &rhs) const 776254721Semaste { 777254721Semaste return this->GetRangeBase() == rhs.GetRangeBase() && 778254721Semaste this->GetByteSize() == rhs.GetByteSize() && 779254721Semaste this->data == rhs.data; 780254721Semaste } 781254721Semaste 782254721Semaste bool 783254721Semaste operator != (const RangeData &rhs) const 784254721Semaste { 785254721Semaste return this->GetRangeBase() != rhs.GetRangeBase() || 786254721Semaste this->GetByteSize() != rhs.GetByteSize() || 787254721Semaste this->data != rhs.data; 788254721Semaste } 789254721Semaste }; 790254721Semaste 791254721Semaste template <typename B, typename S, typename T, unsigned N> 792254721Semaste class RangeDataArray 793254721Semaste { 794254721Semaste public: 795254721Semaste typedef RangeData<B,S,T> Entry; 796254721Semaste typedef llvm::SmallVector<Entry, N> Collection; 797254721Semaste 798296417Sdim RangeDataArray() = default; 799254721Semaste 800296417Sdim ~RangeDataArray() = default; 801296417Sdim 802254721Semaste void 803254721Semaste Append (const Entry &entry) 804254721Semaste { 805254721Semaste m_entries.push_back (entry); 806254721Semaste } 807254721Semaste 808254721Semaste void 809254721Semaste Sort () 810254721Semaste { 811254721Semaste if (m_entries.size() > 1) 812254721Semaste std::stable_sort (m_entries.begin(), m_entries.end()); 813254721Semaste } 814254721Semaste 815254721Semaste#ifdef ASSERT_RANGEMAP_ARE_SORTED 816254721Semaste bool 817254721Semaste IsSorted () const 818254721Semaste { 819254721Semaste typename Collection::const_iterator pos, end, prev; 820254721Semaste // First we determine if we can combine any of the Entry objects so we 821254721Semaste // don't end up allocating and making a new collection for no reason 822254721Semaste for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 823254721Semaste { 824254721Semaste if (prev != end && *pos < *prev) 825254721Semaste return false; 826254721Semaste } 827254721Semaste return true; 828254721Semaste } 829254721Semaste#endif 830254721Semaste 831254721Semaste void 832254721Semaste CombineConsecutiveEntriesWithEqualData () 833254721Semaste { 834254721Semaste#ifdef ASSERT_RANGEMAP_ARE_SORTED 835254721Semaste assert (IsSorted()); 836254721Semaste#endif 837254721Semaste typename Collection::iterator pos; 838254721Semaste typename Collection::iterator end; 839254721Semaste typename Collection::iterator prev; 840254721Semaste bool can_combine = false; 841254721Semaste // First we determine if we can combine any of the Entry objects so we 842254721Semaste // don't end up allocating and making a new collection for no reason 843254721Semaste for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 844254721Semaste { 845254721Semaste if (prev != end && prev->data == pos->data) 846254721Semaste { 847254721Semaste can_combine = true; 848254721Semaste break; 849254721Semaste } 850254721Semaste } 851254721Semaste 852254721Semaste // We we can combine at least one entry, then we make a new collection 853254721Semaste // and populate it accordingly, and then swap it into place. 854254721Semaste if (can_combine) 855254721Semaste { 856254721Semaste Collection minimal_ranges; 857254721Semaste for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 858254721Semaste { 859254721Semaste if (prev != end && prev->data == pos->data) 860254721Semaste minimal_ranges.back().SetRangeEnd (pos->GetRangeEnd()); 861254721Semaste else 862254721Semaste minimal_ranges.push_back (*pos); 863254721Semaste } 864254721Semaste // Use the swap technique in case our new vector is much smaller. 865254721Semaste // We must swap when using the STL because std::vector objects never 866254721Semaste // release or reduce the memory once it has been allocated/reserved. 867254721Semaste m_entries.swap (minimal_ranges); 868254721Semaste } 869254721Semaste } 870254721Semaste 871254721Semaste void 872254721Semaste Clear () 873254721Semaste { 874254721Semaste m_entries.clear(); 875254721Semaste } 876254721Semaste 877254721Semaste bool 878254721Semaste IsEmpty () const 879254721Semaste { 880254721Semaste return m_entries.empty(); 881254721Semaste } 882254721Semaste 883254721Semaste size_t 884254721Semaste GetSize () const 885254721Semaste { 886254721Semaste return m_entries.size(); 887254721Semaste } 888254721Semaste 889254721Semaste const Entry * 890254721Semaste GetEntryAtIndex (size_t i) const 891254721Semaste { 892296417Sdim return ((i < m_entries.size()) ? &m_entries[i] : nullptr); 893254721Semaste } 894254721Semaste 895254721Semaste // Clients must ensure that "i" is a valid index prior to calling this function 896254721Semaste const Entry & 897254721Semaste GetEntryRef (size_t i) const 898254721Semaste { 899254721Semaste return m_entries[i]; 900254721Semaste } 901254721Semaste 902254721Semaste static bool 903254721Semaste BaseLessThan (const Entry& lhs, const Entry& rhs) 904254721Semaste { 905254721Semaste return lhs.GetRangeBase() < rhs.GetRangeBase(); 906254721Semaste } 907254721Semaste 908254721Semaste uint32_t 909254721Semaste FindEntryIndexThatContains (B addr) const 910254721Semaste { 911254721Semaste#ifdef ASSERT_RANGEMAP_ARE_SORTED 912254721Semaste assert (IsSorted()); 913254721Semaste#endif 914254721Semaste if ( !m_entries.empty() ) 915254721Semaste { 916254721Semaste Entry entry (addr, 1); 917254721Semaste typename Collection::const_iterator begin = m_entries.begin(); 918254721Semaste typename Collection::const_iterator end = m_entries.end(); 919254721Semaste typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 920254721Semaste 921254721Semaste if (pos != end && pos->Contains(addr)) 922254721Semaste { 923254721Semaste return std::distance (begin, pos); 924254721Semaste } 925254721Semaste else if (pos != begin) 926254721Semaste { 927254721Semaste --pos; 928254721Semaste if (pos->Contains(addr)) 929254721Semaste return std::distance (begin, pos); 930254721Semaste } 931254721Semaste } 932254721Semaste return UINT32_MAX; 933254721Semaste } 934254721Semaste 935254721Semaste Entry * 936254721Semaste FindEntryThatContains (B addr) 937254721Semaste { 938254721Semaste#ifdef ASSERT_RANGEMAP_ARE_SORTED 939254721Semaste assert (IsSorted()); 940254721Semaste#endif 941254721Semaste if ( !m_entries.empty() ) 942254721Semaste { 943254721Semaste Entry entry; 944254721Semaste entry.SetRangeBase(addr); 945254721Semaste entry.SetByteSize(1); 946254721Semaste typename Collection::iterator begin = m_entries.begin(); 947254721Semaste typename Collection::iterator end = m_entries.end(); 948254721Semaste typename Collection::iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 949254721Semaste 950254721Semaste if (pos != end && pos->Contains(addr)) 951254721Semaste { 952254721Semaste return &(*pos); 953254721Semaste } 954254721Semaste else if (pos != begin) 955254721Semaste { 956254721Semaste --pos; 957254721Semaste if (pos->Contains(addr)) 958254721Semaste { 959254721Semaste return &(*pos); 960254721Semaste } 961254721Semaste } 962254721Semaste } 963296417Sdim return nullptr; 964254721Semaste } 965296417Sdim 966254721Semaste const Entry * 967254721Semaste FindEntryThatContains (B addr) const 968254721Semaste { 969254721Semaste#ifdef ASSERT_RANGEMAP_ARE_SORTED 970254721Semaste assert (IsSorted()); 971254721Semaste#endif 972254721Semaste if ( !m_entries.empty() ) 973254721Semaste { 974254721Semaste Entry entry; 975254721Semaste entry.SetRangeBase(addr); 976254721Semaste entry.SetByteSize(1); 977254721Semaste typename Collection::const_iterator begin = m_entries.begin(); 978254721Semaste typename Collection::const_iterator end = m_entries.end(); 979254721Semaste typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 980254721Semaste 981254721Semaste if (pos != end && pos->Contains(addr)) 982254721Semaste { 983254721Semaste return &(*pos); 984254721Semaste } 985254721Semaste else if (pos != begin) 986254721Semaste { 987254721Semaste --pos; 988254721Semaste if (pos->Contains(addr)) 989254721Semaste { 990254721Semaste return &(*pos); 991254721Semaste } 992254721Semaste } 993254721Semaste } 994296417Sdim return nullptr; 995254721Semaste } 996254721Semaste 997254721Semaste const Entry * 998254721Semaste FindEntryThatContains (const Entry &range) const 999254721Semaste { 1000254721Semaste#ifdef ASSERT_RANGEMAP_ARE_SORTED 1001254721Semaste assert (IsSorted()); 1002254721Semaste#endif 1003254721Semaste if ( !m_entries.empty() ) 1004254721Semaste { 1005254721Semaste typename Collection::const_iterator begin = m_entries.begin(); 1006254721Semaste typename Collection::const_iterator end = m_entries.end(); 1007254721Semaste typename Collection::const_iterator pos = std::lower_bound (begin, end, range, BaseLessThan); 1008254721Semaste 1009254721Semaste if (pos != end && pos->Contains(range)) 1010254721Semaste { 1011254721Semaste return &(*pos); 1012254721Semaste } 1013254721Semaste else if (pos != begin) 1014254721Semaste { 1015254721Semaste --pos; 1016254721Semaste if (pos->Contains(range)) 1017254721Semaste { 1018254721Semaste return &(*pos); 1019254721Semaste } 1020254721Semaste } 1021254721Semaste } 1022296417Sdim return nullptr; 1023254721Semaste } 1024254721Semaste 1025254721Semaste Entry * 1026254721Semaste Back() 1027254721Semaste { 1028296417Sdim return (m_entries.empty() ? nullptr : &m_entries.back()); 1029254721Semaste } 1030254721Semaste 1031254721Semaste const Entry * 1032254721Semaste Back() const 1033254721Semaste { 1034296417Sdim return (m_entries.empty() ? nullptr : &m_entries.back()); 1035254721Semaste } 1036254721Semaste 1037254721Semaste protected: 1038254721Semaste Collection m_entries; 1039254721Semaste }; 1040254721Semaste 1041254721Semaste // Same as RangeDataArray, but uses std::vector as to not 1042254721Semaste // require static storage of N items in the class itself 1043254721Semaste template <typename B, typename S, typename T> 1044254721Semaste class RangeDataVector 1045254721Semaste { 1046254721Semaste public: 1047254721Semaste typedef RangeData<B,S,T> Entry; 1048254721Semaste typedef std::vector<Entry> Collection; 1049296417Sdim 1050296417Sdim RangeDataVector() = default; 1051296417Sdim 1052296417Sdim ~RangeDataVector() = default; 1053296417Sdim 1054254721Semaste void 1055254721Semaste Append (const Entry &entry) 1056254721Semaste { 1057254721Semaste m_entries.push_back (entry); 1058254721Semaste } 1059254721Semaste 1060254721Semaste void 1061254721Semaste Sort () 1062254721Semaste { 1063254721Semaste if (m_entries.size() > 1) 1064254721Semaste std::stable_sort (m_entries.begin(), m_entries.end()); 1065254721Semaste } 1066254721Semaste 1067254721Semaste#ifdef ASSERT_RANGEMAP_ARE_SORTED 1068254721Semaste bool 1069254721Semaste IsSorted () const 1070254721Semaste { 1071254721Semaste typename Collection::const_iterator pos, end, prev; 1072254721Semaste // First we determine if we can combine any of the Entry objects so we 1073254721Semaste // don't end up allocating and making a new collection for no reason 1074254721Semaste for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 1075254721Semaste { 1076254721Semaste if (prev != end && *pos < *prev) 1077254721Semaste return false; 1078254721Semaste } 1079254721Semaste return true; 1080254721Semaste } 1081254721Semaste#endif 1082254721Semaste 1083254721Semaste void 1084254721Semaste CombineConsecutiveEntriesWithEqualData () 1085254721Semaste { 1086254721Semaste#ifdef ASSERT_RANGEMAP_ARE_SORTED 1087254721Semaste assert (IsSorted()); 1088254721Semaste#endif 1089254721Semaste typename Collection::iterator pos; 1090254721Semaste typename Collection::iterator end; 1091254721Semaste typename Collection::iterator prev; 1092254721Semaste bool can_combine = false; 1093254721Semaste // First we determine if we can combine any of the Entry objects so we 1094254721Semaste // don't end up allocating and making a new collection for no reason 1095254721Semaste for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 1096254721Semaste { 1097254721Semaste if (prev != end && prev->data == pos->data) 1098254721Semaste { 1099254721Semaste can_combine = true; 1100254721Semaste break; 1101254721Semaste } 1102254721Semaste } 1103254721Semaste 1104254721Semaste // We we can combine at least one entry, then we make a new collection 1105254721Semaste // and populate it accordingly, and then swap it into place. 1106254721Semaste if (can_combine) 1107254721Semaste { 1108254721Semaste Collection minimal_ranges; 1109254721Semaste for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 1110254721Semaste { 1111254721Semaste if (prev != end && prev->data == pos->data) 1112254721Semaste minimal_ranges.back().SetRangeEnd (pos->GetRangeEnd()); 1113254721Semaste else 1114254721Semaste minimal_ranges.push_back (*pos); 1115254721Semaste } 1116254721Semaste // Use the swap technique in case our new vector is much smaller. 1117254721Semaste // We must swap when using the STL because std::vector objects never 1118254721Semaste // release or reduce the memory once it has been allocated/reserved. 1119254721Semaste m_entries.swap (minimal_ranges); 1120254721Semaste } 1121254721Semaste } 1122254721Semaste 1123254721Semaste // Calculate the byte size of ranges with zero byte sizes by finding 1124254721Semaste // the next entry with a base address > the current base address 1125254721Semaste void 1126254721Semaste CalculateSizesOfZeroByteSizeRanges () 1127254721Semaste { 1128254721Semaste#ifdef ASSERT_RANGEMAP_ARE_SORTED 1129254721Semaste assert (IsSorted()); 1130254721Semaste#endif 1131254721Semaste typename Collection::iterator pos; 1132254721Semaste typename Collection::iterator end; 1133254721Semaste typename Collection::iterator next; 1134254721Semaste for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos) 1135254721Semaste { 1136254721Semaste if (pos->GetByteSize() == 0) 1137254721Semaste { 1138254721Semaste // Watch out for multiple entries with same address and make sure 1139254721Semaste // we find an entry that is greater than the current base address 1140254721Semaste // before we use that for the size 1141254721Semaste auto curr_base = pos->GetRangeBase(); 1142254721Semaste for (next = pos + 1; next != end; ++next) 1143254721Semaste { 1144254721Semaste auto next_base = next->GetRangeBase(); 1145254721Semaste if (next_base > curr_base) 1146254721Semaste { 1147254721Semaste pos->SetByteSize (next_base - curr_base); 1148254721Semaste break; 1149254721Semaste } 1150254721Semaste } 1151254721Semaste } 1152254721Semaste } 1153254721Semaste } 1154254721Semaste 1155254721Semaste void 1156254721Semaste Clear () 1157254721Semaste { 1158254721Semaste m_entries.clear(); 1159254721Semaste } 1160254721Semaste 1161254721Semaste void 1162254721Semaste Reserve (typename Collection::size_type size) 1163254721Semaste { 1164254721Semaste m_entries.resize (size); 1165254721Semaste } 1166254721Semaste 1167254721Semaste bool 1168254721Semaste IsEmpty () const 1169254721Semaste { 1170254721Semaste return m_entries.empty(); 1171254721Semaste } 1172254721Semaste 1173254721Semaste size_t 1174254721Semaste GetSize () const 1175254721Semaste { 1176254721Semaste return m_entries.size(); 1177254721Semaste } 1178254721Semaste 1179254721Semaste const Entry * 1180254721Semaste GetEntryAtIndex (size_t i) const 1181254721Semaste { 1182296417Sdim return ((i < m_entries.size()) ? &m_entries[i] : nullptr); 1183254721Semaste } 1184254721Semaste 1185254721Semaste // Clients must ensure that "i" is a valid index prior to calling this function 1186254721Semaste const Entry & 1187254721Semaste GetEntryRef (size_t i) const 1188254721Semaste { 1189254721Semaste return m_entries[i]; 1190254721Semaste } 1191254721Semaste 1192254721Semaste static bool 1193254721Semaste BaseLessThan (const Entry& lhs, const Entry& rhs) 1194254721Semaste { 1195254721Semaste return lhs.GetRangeBase() < rhs.GetRangeBase(); 1196254721Semaste } 1197254721Semaste 1198254721Semaste uint32_t 1199254721Semaste FindEntryIndexThatContains (B addr) const 1200254721Semaste { 1201254721Semaste#ifdef ASSERT_RANGEMAP_ARE_SORTED 1202254721Semaste assert (IsSorted()); 1203254721Semaste#endif 1204254721Semaste if ( !m_entries.empty() ) 1205254721Semaste { 1206254721Semaste Entry entry (addr, 1); 1207254721Semaste typename Collection::const_iterator begin = m_entries.begin(); 1208254721Semaste typename Collection::const_iterator end = m_entries.end(); 1209254721Semaste typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 1210254721Semaste 1211258054Semaste while(pos != begin && pos[-1].Contains(addr)) 1212258054Semaste --pos; 1213258054Semaste 1214254721Semaste if (pos != end && pos->Contains(addr)) 1215254721Semaste return std::distance (begin, pos); 1216254721Semaste } 1217254721Semaste return UINT32_MAX; 1218254721Semaste } 1219296417Sdim 1220296417Sdim uint32_t 1221296417Sdim FindEntryIndexesThatContain(B addr, std::vector<uint32_t> &indexes) const 1222296417Sdim { 1223296417Sdim#ifdef ASSERT_RANGEMAP_ARE_SORTED 1224296417Sdim assert (IsSorted()); 1225296417Sdim#endif 1226296417Sdim 1227296417Sdim if (!m_entries.empty()) 1228296417Sdim { 1229296417Sdim typename Collection::const_iterator pos; 1230296417Sdim for (const auto &entry : m_entries) 1231296417Sdim { 1232296417Sdim if (entry.Contains(addr)) 1233296417Sdim indexes.push_back(entry.data); 1234296417Sdim } 1235296417Sdim } 1236296417Sdim return indexes.size() ; 1237296417Sdim } 1238254721Semaste 1239254721Semaste Entry * 1240254721Semaste FindEntryThatContains (B addr) 1241254721Semaste { 1242254721Semaste#ifdef ASSERT_RANGEMAP_ARE_SORTED 1243254721Semaste assert (IsSorted()); 1244254721Semaste#endif 1245254721Semaste if ( !m_entries.empty() ) 1246254721Semaste { 1247254721Semaste Entry entry; 1248254721Semaste entry.SetRangeBase(addr); 1249254721Semaste entry.SetByteSize(1); 1250254721Semaste typename Collection::iterator begin = m_entries.begin(); 1251254721Semaste typename Collection::iterator end = m_entries.end(); 1252254721Semaste typename Collection::iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 1253258054Semaste 1254258054Semaste while(pos != begin && pos[-1].Contains(addr)) 1255258054Semaste --pos; 1256254721Semaste 1257254721Semaste if (pos != end && pos->Contains(addr)) 1258254721Semaste return &(*pos); 1259254721Semaste } 1260296417Sdim return nullptr; 1261254721Semaste } 1262296417Sdim 1263254721Semaste const Entry * 1264254721Semaste FindEntryThatContains (B addr) const 1265254721Semaste { 1266254721Semaste#ifdef ASSERT_RANGEMAP_ARE_SORTED 1267254721Semaste assert (IsSorted()); 1268254721Semaste#endif 1269254721Semaste if ( !m_entries.empty() ) 1270254721Semaste { 1271254721Semaste Entry entry; 1272254721Semaste entry.SetRangeBase(addr); 1273254721Semaste entry.SetByteSize(1); 1274254721Semaste typename Collection::const_iterator begin = m_entries.begin(); 1275254721Semaste typename Collection::const_iterator end = m_entries.end(); 1276254721Semaste typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 1277254721Semaste 1278258054Semaste while(pos != begin && pos[-1].Contains(addr)) 1279258054Semaste --pos; 1280258054Semaste 1281254721Semaste if (pos != end && pos->Contains(addr)) 1282258054Semaste return &(*pos); 1283254721Semaste } 1284296417Sdim return nullptr; 1285254721Semaste } 1286254721Semaste 1287254721Semaste const Entry * 1288254721Semaste FindEntryThatContains (const Entry &range) const 1289254721Semaste { 1290254721Semaste#ifdef ASSERT_RANGEMAP_ARE_SORTED 1291254721Semaste assert (IsSorted()); 1292254721Semaste#endif 1293254721Semaste if ( !m_entries.empty() ) 1294254721Semaste { 1295254721Semaste typename Collection::const_iterator begin = m_entries.begin(); 1296254721Semaste typename Collection::const_iterator end = m_entries.end(); 1297254721Semaste typename Collection::const_iterator pos = std::lower_bound (begin, end, range, BaseLessThan); 1298254721Semaste 1299258054Semaste while(pos != begin && pos[-1].Contains(range)) 1300258054Semaste --pos; 1301258054Semaste 1302254721Semaste if (pos != end && pos->Contains(range)) 1303258054Semaste return &(*pos); 1304254721Semaste } 1305296417Sdim return nullptr; 1306254721Semaste } 1307254721Semaste 1308254721Semaste Entry * 1309254721Semaste Back() 1310254721Semaste { 1311296417Sdim return (m_entries.empty() ? nullptr : &m_entries.back()); 1312254721Semaste } 1313254721Semaste 1314254721Semaste const Entry * 1315254721Semaste Back() const 1316254721Semaste { 1317296417Sdim return (m_entries.empty() ? nullptr : &m_entries.back()); 1318254721Semaste } 1319254721Semaste 1320254721Semaste protected: 1321254721Semaste Collection m_entries; 1322254721Semaste }; 1323296417Sdim 1324254721Semaste //---------------------------------------------------------------------- 1325254721Semaste // A simple range with data class where you get to define the type of 1326254721Semaste // the range base "B", the type used for the range byte size "S", and 1327254721Semaste // the type for the associated data "T". 1328254721Semaste //---------------------------------------------------------------------- 1329254721Semaste template <typename B, typename T> 1330254721Semaste struct AddressData 1331254721Semaste { 1332254721Semaste typedef B BaseType; 1333254721Semaste typedef T DataType; 1334254721Semaste 1335254721Semaste BaseType addr; 1336254721Semaste DataType data; 1337254721Semaste 1338254721Semaste AddressData () : 1339254721Semaste addr (), 1340254721Semaste data () 1341254721Semaste { 1342254721Semaste } 1343254721Semaste 1344254721Semaste AddressData (B a, DataType d) : 1345254721Semaste addr (a), 1346254721Semaste data (d) 1347254721Semaste { 1348254721Semaste } 1349254721Semaste 1350254721Semaste bool 1351254721Semaste operator < (const AddressData &rhs) const 1352254721Semaste { 1353254721Semaste if (this->addr == rhs.addr) 1354254721Semaste return this->data < rhs.data; 1355254721Semaste return this->addr < rhs.addr; 1356254721Semaste } 1357254721Semaste 1358254721Semaste bool 1359254721Semaste operator == (const AddressData &rhs) const 1360254721Semaste { 1361254721Semaste return this->addr == rhs.addr && 1362254721Semaste this->data == rhs.data; 1363254721Semaste } 1364254721Semaste 1365254721Semaste bool 1366254721Semaste operator != (const AddressData &rhs) const 1367254721Semaste { 1368254721Semaste return this->addr != rhs.addr || 1369254721Semaste this->data == rhs.data; 1370254721Semaste } 1371254721Semaste }; 1372254721Semaste 1373254721Semaste template <typename B, typename T, unsigned N> 1374254721Semaste class AddressDataArray 1375254721Semaste { 1376254721Semaste public: 1377254721Semaste typedef AddressData<B,T> Entry; 1378254721Semaste typedef llvm::SmallVector<Entry, N> Collection; 1379254721Semaste 1380296417Sdim AddressDataArray() = default; 1381254721Semaste 1382296417Sdim ~AddressDataArray() = default; 1383296417Sdim 1384254721Semaste void 1385254721Semaste Append (const Entry &entry) 1386254721Semaste { 1387254721Semaste m_entries.push_back (entry); 1388254721Semaste } 1389254721Semaste 1390254721Semaste void 1391254721Semaste Sort () 1392254721Semaste { 1393254721Semaste if (m_entries.size() > 1) 1394254721Semaste std::stable_sort (m_entries.begin(), m_entries.end()); 1395254721Semaste } 1396254721Semaste 1397254721Semaste#ifdef ASSERT_RANGEMAP_ARE_SORTED 1398254721Semaste bool 1399254721Semaste IsSorted () const 1400254721Semaste { 1401254721Semaste typename Collection::const_iterator pos, end, prev; 1402254721Semaste // First we determine if we can combine any of the Entry objects so we 1403254721Semaste // don't end up allocating and making a new collection for no reason 1404254721Semaste for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 1405254721Semaste { 1406254721Semaste if (prev != end && *pos < *prev) 1407254721Semaste return false; 1408254721Semaste } 1409254721Semaste return true; 1410254721Semaste } 1411254721Semaste#endif 1412254721Semaste 1413254721Semaste void 1414254721Semaste Clear () 1415254721Semaste { 1416254721Semaste m_entries.clear(); 1417254721Semaste } 1418254721Semaste 1419254721Semaste bool 1420254721Semaste IsEmpty () const 1421254721Semaste { 1422254721Semaste return m_entries.empty(); 1423254721Semaste } 1424254721Semaste 1425254721Semaste size_t 1426254721Semaste GetSize () const 1427254721Semaste { 1428254721Semaste return m_entries.size(); 1429254721Semaste } 1430254721Semaste 1431254721Semaste const Entry * 1432254721Semaste GetEntryAtIndex (size_t i) const 1433254721Semaste { 1434296417Sdim return ((i < m_entries.size()) ? &m_entries[i] : nullptr); 1435254721Semaste } 1436254721Semaste 1437254721Semaste // Clients must ensure that "i" is a valid index prior to calling this function 1438254721Semaste const Entry & 1439254721Semaste GetEntryRef (size_t i) const 1440254721Semaste { 1441254721Semaste return m_entries[i]; 1442254721Semaste } 1443254721Semaste 1444254721Semaste static bool 1445254721Semaste BaseLessThan (const Entry& lhs, const Entry& rhs) 1446254721Semaste { 1447254721Semaste return lhs.addr < rhs.addr; 1448254721Semaste } 1449254721Semaste 1450254721Semaste Entry * 1451254721Semaste FindEntry (B addr, bool exact_match_only) 1452254721Semaste { 1453254721Semaste#ifdef ASSERT_RANGEMAP_ARE_SORTED 1454254721Semaste assert (IsSorted()); 1455254721Semaste#endif 1456254721Semaste if ( !m_entries.empty() ) 1457254721Semaste { 1458254721Semaste Entry entry; 1459254721Semaste entry.addr = addr; 1460254721Semaste typename Collection::iterator begin = m_entries.begin(); 1461254721Semaste typename Collection::iterator end = m_entries.end(); 1462254721Semaste typename Collection::iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 1463254721Semaste 1464258054Semaste while(pos != begin && pos[-1].addr == addr) 1465258054Semaste --pos; 1466258054Semaste 1467254721Semaste if (pos != end) 1468254721Semaste { 1469254721Semaste if (pos->addr == addr || !exact_match_only) 1470254721Semaste return &(*pos); 1471254721Semaste } 1472258054Semaste } 1473296417Sdim return nullptr; 1474254721Semaste } 1475254721Semaste 1476254721Semaste const Entry * 1477254721Semaste FindNextEntry (const Entry *entry) 1478254721Semaste { 1479254721Semaste if (entry >= &*m_entries.begin() && entry + 1 < &*m_entries.end()) 1480254721Semaste return entry + 1; 1481296417Sdim return nullptr; 1482254721Semaste } 1483254721Semaste 1484254721Semaste Entry * 1485254721Semaste Back() 1486254721Semaste { 1487296417Sdim return (m_entries.empty() ? nullptr : &m_entries.back()); 1488254721Semaste } 1489254721Semaste 1490254721Semaste const Entry * 1491254721Semaste Back() const 1492254721Semaste { 1493296417Sdim return (m_entries.empty() ? nullptr : &m_entries.back()); 1494254721Semaste } 1495254721Semaste 1496254721Semaste protected: 1497254721Semaste Collection m_entries; 1498254721Semaste }; 1499254721Semaste 1500254721Semaste} // namespace lldb_private 1501254721Semaste 1502296417Sdim#endif // liblldb_RangeMap_h_ 1503