RangeMap.h revision 761133029ba2d5bb0c21c3a871dede340b2775fc
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 "lldb/lldb-private.h" 14#include "llvm/ADT/SmallVector.h" 15 16// Uncomment to make sure all Range objects are sorted when needed 17//#define ASSERT_RANGEMAP_ARE_SORTED 18 19namespace lldb_private { 20 21 //---------------------------------------------------------------------- 22 // Templatized classes for dealing with generic ranges and also 23 // collections of ranges, or collections of ranges that have associated 24 // data. 25 //---------------------------------------------------------------------- 26 27 //---------------------------------------------------------------------- 28 // A simple range class where you get to define the type of the range 29 // base "B", and the type used for the range byte size "S". 30 //---------------------------------------------------------------------- 31 template <typename B, typename S> 32 struct Range 33 { 34 typedef B BaseType; 35 typedef S SizeType; 36 37 BaseType base; 38 SizeType size; 39 40 Range () : 41 base (0), 42 size (0) 43 { 44 } 45 46 Range (BaseType b, SizeType s) : 47 base (b), 48 size (s) 49 { 50 } 51 52 void 53 Clear (BaseType b = 0) 54 { 55 base = b; 56 size = 0; 57 } 58 59 // Set the start value for the range, and keep the same size 60 BaseType 61 GetRangeBase () const 62 { 63 return base; 64 } 65 66 void 67 SetRangeBase (BaseType b) 68 { 69 base = b; 70 } 71 72 void 73 Slide (BaseType slide) 74 { 75 base += slide; 76 } 77 78 BaseType 79 GetRangeEnd () const 80 { 81 return base + size; 82 } 83 84 void 85 SetRangeEnd (BaseType end) 86 { 87 if (end > base) 88 size = end - base; 89 else 90 size = 0; 91 } 92 93 SizeType 94 GetByteSize () const 95 { 96 return size; 97 } 98 99 void 100 SetByteSize (SizeType s) 101 { 102 size = s; 103 } 104 105 bool 106 IsValid() const 107 { 108 return size > 0; 109 } 110 111 bool 112 Contains (BaseType r) const 113 { 114 return (GetRangeBase() <= r) && (r < GetRangeEnd()); 115 } 116 117 bool 118 ContainsEndInclusive (BaseType r) const 119 { 120 return (GetRangeBase() <= r) && (r <= GetRangeEnd()); 121 } 122 123 bool 124 Contains (const Range& range) const 125 { 126 return Contains(range.GetRangeBase()) && ContainsEndInclusive(range.GetRangeEnd()); 127 } 128 129 bool 130 Overlap (const Range &rhs) const 131 { 132 const BaseType lhs_base = this->GetRangeBase(); 133 const BaseType rhs_base = rhs.GetRangeBase(); 134 const BaseType lhs_end = this->GetRangeEnd(); 135 const BaseType rhs_end = rhs.GetRangeEnd(); 136 bool result = (lhs_base <= rhs_end) && (lhs_end >= rhs_base); 137 return result; 138 } 139 140 bool 141 operator < (const Range &rhs) const 142 { 143 if (base == rhs.base) 144 return size < rhs.size; 145 return base < rhs.base; 146 } 147 148 bool 149 operator == (const Range &rhs) const 150 { 151 return base == rhs.base && size == rhs.size; 152 } 153 154 bool 155 operator != (const Range &rhs) const 156 { 157 return base != rhs.base || size != rhs.size; 158 } 159 }; 160 161 //---------------------------------------------------------------------- 162 // A range array class where you get to define the type of the ranges 163 // that the collection contains. 164 //---------------------------------------------------------------------- 165 166 template <typename B, typename S, unsigned N> 167 class RangeArray 168 { 169 public: 170 typedef B BaseType; 171 typedef S SizeType; 172 typedef Range<B,S> Entry; 173 //typedef std::vector<Entry> Collection; 174 typedef llvm::SmallVector<Entry, N> Collection; 175 176 RangeArray () : 177 m_entries () 178 { 179 } 180 181 ~RangeArray() 182 { 183 } 184 185 void 186 Append (const Entry &entry) 187 { 188 m_entries.push_back (entry); 189 } 190 191 bool 192 RemoveEntrtAtIndex (uint32_t idx) 193 { 194 if (idx < m_entries.size()) 195 { 196 m_entries.erase (m_entries.begin() + idx); 197 return true; 198 } 199 return false; 200 } 201 202 void 203 Sort () 204 { 205 if (m_entries.size() > 1) 206 std::stable_sort (m_entries.begin(), m_entries.end()); 207 } 208 209#ifdef ASSERT_RANGEMAP_ARE_SORTED 210 bool 211 IsSorted () const 212 { 213 typename Collection::const_iterator pos, end, prev; 214 // First we determine if we can combine any of the Entry objects so we 215 // don't end up allocating and making a new collection for no reason 216 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 217 { 218 if (prev != end && *pos < *prev) 219 return false; 220 } 221 return true; 222 } 223#endif 224 void 225 CombineConsecutiveRanges () 226 { 227#ifdef ASSERT_RANGEMAP_ARE_SORTED 228 assert (IsSorted()); 229#endif 230 // Can't combine if ranges if we have zero or one range 231 if (m_entries.size() > 1) 232 { 233 // The list should be sorted prior to calling this function 234 typename Collection::iterator pos; 235 typename Collection::iterator end; 236 typename Collection::iterator prev; 237 bool can_combine = false; 238 // First we determine if we can combine any of the Entry objects so we 239 // don't end up allocating and making a new collection for no reason 240 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 241 { 242 if (prev != end && prev->Overlap(*pos)) 243 { 244 can_combine = true; 245 break; 246 } 247 } 248 249 // We we can combine at least one entry, then we make a new collection 250 // and populate it accordingly, and then swap it into place. 251 if (can_combine) 252 { 253 Collection minimal_ranges; 254 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 255 { 256 if (prev != end && prev->Overlap(*pos)) 257 minimal_ranges.back().SetRangeEnd (std::max<BaseType>(prev->GetRangeEnd(), pos->GetRangeEnd())); 258 else 259 minimal_ranges.push_back (*pos); 260 } 261 // Use the swap technique in case our new vector is much smaller. 262 // We must swap when using the STL because std::vector objects never 263 // release or reduce the memory once it has been allocated/reserved. 264 m_entries.swap (minimal_ranges); 265 } 266 } 267 } 268 269 270 BaseType 271 GetMinRangeBase (BaseType fail_value) const 272 { 273#ifdef ASSERT_RANGEMAP_ARE_SORTED 274 assert (IsSorted()); 275#endif 276 if (m_entries.empty()) 277 return fail_value; 278 // m_entries must be sorted, so if we aren't empty, we grab the 279 // first range's base 280 return m_entries.front().GetRangeBase(); 281 } 282 283 BaseType 284 GetMaxRangeEnd (BaseType fail_value) const 285 { 286#ifdef ASSERT_RANGEMAP_ARE_SORTED 287 assert (IsSorted()); 288#endif 289 if (m_entries.empty()) 290 return fail_value; 291 // m_entries must be sorted, so if we aren't empty, we grab the 292 // last range's end 293 return m_entries.back().GetRangeEnd(); 294 } 295 296 void 297 Slide (BaseType slide) 298 { 299 typename Collection::iterator pos, end; 300 for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos) 301 pos->Slide (slide); 302 } 303 304 void 305 Clear () 306 { 307 m_entries.clear(); 308 } 309 310 bool 311 IsEmpty () const 312 { 313 return m_entries.empty(); 314 } 315 316 size_t 317 GetSize () const 318 { 319 return m_entries.size(); 320 } 321 322 const Entry * 323 GetEntryAtIndex (size_t i) const 324 { 325 if (i<m_entries.size()) 326 return &m_entries[i]; 327 return NULL; 328 } 329 330 // Clients must ensure that "i" is a valid index prior to calling this function 331 const Entry & 332 GetEntryRef (size_t i) const 333 { 334 return m_entries[i]; 335 } 336 337 static bool 338 BaseLessThan (const Entry& lhs, const Entry& rhs) 339 { 340 return lhs.GetRangeBase() < rhs.GetRangeBase(); 341 } 342 343 uint32_t 344 FindEntryIndexThatContains (B addr) const 345 { 346#ifdef ASSERT_RANGEMAP_ARE_SORTED 347 assert (IsSorted()); 348#endif 349 if (!m_entries.empty()) 350 { 351 Entry entry (addr, 1); 352 typename Collection::const_iterator begin = m_entries.begin(); 353 typename Collection::const_iterator end = m_entries.end(); 354 typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 355 356 if (pos != end && pos->Contains(addr)) 357 { 358 return std::distance (begin, pos); 359 } 360 else if (pos != begin) 361 { 362 --pos; 363 if (pos->Contains(addr)) 364 return std::distance (begin, pos); 365 } 366 } 367 return UINT32_MAX; 368 } 369 370 const Entry * 371 FindEntryThatContains (B addr) const 372 { 373#ifdef ASSERT_RANGEMAP_ARE_SORTED 374 assert (IsSorted()); 375#endif 376 if (!m_entries.empty()) 377 { 378 Entry entry (addr, 1); 379 typename Collection::const_iterator begin = m_entries.begin(); 380 typename Collection::const_iterator end = m_entries.end(); 381 typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 382 383 if (pos != end && pos->Contains(addr)) 384 { 385 return &(*pos); 386 } 387 else if (pos != begin) 388 { 389 --pos; 390 if (pos->Contains(addr)) 391 { 392 return &(*pos); 393 } 394 } 395 } 396 return NULL; 397 } 398 399 const Entry * 400 FindEntryThatContains (const Entry &range) const 401 { 402#ifdef ASSERT_RANGEMAP_ARE_SORTED 403 assert (IsSorted()); 404#endif 405 if (!m_entries.empty()) 406 { 407 typename Collection::const_iterator begin = m_entries.begin(); 408 typename Collection::const_iterator end = m_entries.end(); 409 typename Collection::const_iterator pos = std::lower_bound (begin, end, range, BaseLessThan); 410 411 if (pos != end && pos->Contains(range)) 412 { 413 return &(*pos); 414 } 415 else if (pos != begin) 416 { 417 --pos; 418 if (pos->Contains(range)) 419 { 420 return &(*pos); 421 } 422 } 423 } 424 return NULL; 425 } 426 427 protected: 428 Collection m_entries; 429 }; 430 431 //---------------------------------------------------------------------- 432 // A simple range with data class where you get to define the type of 433 // the range base "B", the type used for the range byte size "S", and 434 // the type for the associated data "T". 435 //---------------------------------------------------------------------- 436 template <typename B, typename S, typename T> 437 struct RangeData : public Range<B,S> 438 { 439 typedef T DataType; 440 441 DataType data; 442 443 RangeData () : 444 Range<B,S> (), 445 data () 446 { 447 } 448 449 RangeData (B base, S size, DataType d) : 450 Range<B,S> (base, size), 451 data (d) 452 { 453 } 454 455 bool 456 operator < (const RangeData &rhs) const 457 { 458 if (this->base == rhs.base) 459 { 460 if (this->size == rhs.size) 461 return this->data < rhs.data; 462 else 463 return this->size < rhs.size; 464 } 465 return this->base < rhs.base; 466 } 467 468 bool 469 operator == (const RangeData &rhs) const 470 { 471 return this->GetRangeBase() == rhs.GetRangeBase() && 472 this->GetByteSize() == rhs.GetByteSize() && 473 this->data == rhs.data; 474 } 475 476 bool 477 operator != (const RangeData &rhs) const 478 { 479 return this->GetRangeBase() != rhs.GetRangeBase() || 480 this->GetByteSize() != rhs.GetByteSize() || 481 this->data != rhs.data; 482 } 483 }; 484 485 template <typename B, typename S, typename T, unsigned N> 486 class RangeDataArray 487 { 488 public: 489 typedef RangeData<B,S,T> Entry; 490 //typedef std::vector<Entry> Collection; 491 typedef llvm::SmallVector<Entry, N> Collection; 492 493 494 RangeDataArray () 495 { 496 } 497 498 ~RangeDataArray() 499 { 500 } 501 502 void 503 Append (const Entry &entry) 504 { 505 m_entries.push_back (entry); 506 } 507 508 void 509 Sort () 510 { 511 if (m_entries.size() > 1) 512 std::stable_sort (m_entries.begin(), m_entries.end()); 513 } 514 515#ifdef ASSERT_RANGEMAP_ARE_SORTED 516 bool 517 IsSorted () const 518 { 519 typename Collection::const_iterator pos, end, prev; 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 && *pos < *prev) 525 return false; 526 } 527 return true; 528 } 529#endif 530 531 void 532 CombineConsecutiveEntriesWithEqualData () 533 { 534#ifdef ASSERT_RANGEMAP_ARE_SORTED 535 assert (IsSorted()); 536#endif 537 typename Collection::iterator pos; 538 typename Collection::iterator end; 539 typename Collection::iterator prev; 540 bool can_combine = false; 541 // First we determine if we can combine any of the Entry objects so we 542 // don't end up allocating and making a new collection for no reason 543 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 544 { 545 if (prev != end && prev->data == pos->data) 546 { 547 can_combine = true; 548 break; 549 } 550 } 551 552 // We we can combine at least one entry, then we make a new collection 553 // and populate it accordingly, and then swap it into place. 554 if (can_combine) 555 { 556 Collection minimal_ranges; 557 for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end; prev = pos++) 558 { 559 if (prev != end && prev->data == pos->data) 560 minimal_ranges.back().SetRangeEnd (pos->GetRangeEnd()); 561 else 562 minimal_ranges.push_back (*pos); 563 } 564 // Use the swap technique in case our new vector is much smaller. 565 // We must swap when using the STL because std::vector objects never 566 // release or reduce the memory once it has been allocated/reserved. 567 m_entries.swap (minimal_ranges); 568 } 569 } 570 571 void 572 Clear () 573 { 574 m_entries.clear(); 575 } 576 577 bool 578 IsEmpty () const 579 { 580 return m_entries.empty(); 581 } 582 583 size_t 584 GetSize () const 585 { 586 return m_entries.size(); 587 } 588 589 const Entry * 590 GetEntryAtIndex (size_t i) const 591 { 592 if (i<m_entries.size()) 593 return &m_entries[i]; 594 return NULL; 595 } 596 597 // Clients must ensure that "i" is a valid index prior to calling this function 598 const Entry & 599 GetEntryRef (size_t i) const 600 { 601 return m_entries[i]; 602 } 603 604 static bool 605 BaseLessThan (const Entry& lhs, const Entry& rhs) 606 { 607 return lhs.GetRangeBase() < rhs.GetRangeBase(); 608 } 609 610 uint32_t 611 FindEntryIndexThatContains (B addr) const 612 { 613#ifdef ASSERT_RANGEMAP_ARE_SORTED 614 assert (IsSorted()); 615#endif 616 if ( !m_entries.empty() ) 617 { 618 Entry entry (addr, 1); 619 typename Collection::const_iterator begin = m_entries.begin(); 620 typename Collection::const_iterator end = m_entries.end(); 621 typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 622 623 if (pos != end && pos->Contains(addr)) 624 { 625 return std::distance (begin, pos); 626 } 627 else if (pos != begin) 628 { 629 --pos; 630 if (pos->Contains(addr)) 631 return std::distance (begin, pos); 632 } 633 } 634 return UINT32_MAX; 635 } 636 637 const Entry * 638 FindEntryThatContains (B addr) const 639 { 640#ifdef ASSERT_RANGEMAP_ARE_SORTED 641 assert (IsSorted()); 642#endif 643 if ( !m_entries.empty() ) 644 { 645 Entry entry; 646 entry.SetRangeBase(addr); 647 entry.SetByteSize(1); 648 typename Collection::const_iterator begin = m_entries.begin(); 649 typename Collection::const_iterator end = m_entries.end(); 650 typename Collection::const_iterator pos = std::lower_bound (begin, end, entry, BaseLessThan); 651 652 if (pos != end && pos->Contains(addr)) 653 { 654 return &(*pos); 655 } 656 else if (pos != begin) 657 { 658 --pos; 659 if (pos->Contains(addr)) 660 { 661 return &(*pos); 662 } 663 } 664 } 665 return NULL; 666 } 667 668 const Entry * 669 FindEntryThatContains (const Entry &range) const 670 { 671#ifdef ASSERT_RANGEMAP_ARE_SORTED 672 assert (IsSorted()); 673#endif 674 if ( !m_entries.empty() ) 675 { 676 typename Collection::const_iterator begin = m_entries.begin(); 677 typename Collection::const_iterator end = m_entries.end(); 678 typename Collection::const_iterator pos = std::lower_bound (begin, end, range, BaseLessThan); 679 680 if (pos != end && pos->Contains(range)) 681 { 682 return &(*pos); 683 } 684 else if (pos != begin) 685 { 686 --pos; 687 if (pos->Contains(range)) 688 { 689 return &(*pos); 690 } 691 } 692 } 693 return NULL; 694 } 695 696 Entry * 697 Back() 698 { 699 if (!m_entries.empty()) 700 return &m_entries.back(); 701 return NULL; 702 } 703 704 const Entry * 705 Back() const 706 { 707 if (!m_entries.empty()) 708 return &m_entries.back(); 709 return NULL; 710 } 711 712 protected: 713 Collection m_entries; 714 }; 715 716} // namespace lldb_private 717 718#endif // liblldb_RangeMap_h_ 719