1 // Copyright 2015, VIXL authors 2 // All rights reserved. 3 // 4 // Redistribution and use in source and binary forms, with or without 5 // modification, are permitted provided that the following conditions are met: 6 // 7 // * Redistributions of source code must retain the above copyright notice, 8 // this list of conditions and the following disclaimer. 9 // * Redistributions in binary form must reproduce the above copyright notice, 10 // this list of conditions and the following disclaimer in the documentation 11 // and/or other materials provided with the distribution. 12 // * Neither the name of ARM Limited nor the names of its contributors may be 13 // used to endorse or promote products derived from this software without 14 // specific prior written permission. 15 // 16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS CONTRIBUTORS "AS IS" AND 17 // ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 18 // WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 19 // DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE 20 // FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 21 // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 22 // SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 23 // CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 24 // OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 25 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 26 27 #ifndef VIXL_INVALSET_H_ 28 #define VIXL_INVALSET_H_ 29 30 #include <cstring> 31 32 #include <algorithm> 33 #include <vector> 34 35 #include "globals-vixl.h" 36 37 namespace vixl { 38 39 // We define a custom data structure template and its iterator as `std` 40 // containers do not fit the performance requirements for some of our use cases. 41 // 42 // The structure behaves like an iterable unordered set with special properties 43 // and restrictions. "InvalSet" stands for "Invalidatable Set". 44 // 45 // Restrictions and requirements: 46 // - Adding an element already present in the set is illegal. In debug mode, 47 // this is checked at insertion time. 48 // - The templated class `ElementType` must provide comparison operators so that 49 // `std::sort()` can be used. 50 // - A key must be available to represent invalid elements. 51 // - Elements with an invalid key must compare higher or equal to any other 52 // element. 53 // 54 // Use cases and performance considerations: 55 // Our use cases present two specificities that allow us to design this 56 // structure to provide fast insertion *and* fast search and deletion 57 // operations: 58 // - Elements are (generally) inserted in order (sorted according to their key). 59 // - A key is available to mark elements as invalid (deleted). 60 // The backing `std::vector` allows for fast insertions. When 61 // searching for an element we ensure the elements are sorted (this is generally 62 // the case) and perform a binary search. When deleting an element we do not 63 // free the associated memory immediately. Instead, an element to be deleted is 64 // marked with the 'invalid' key. Other methods of the container take care of 65 // ignoring entries marked as invalid. 66 // To avoid the overhead of the `std::vector` container when only few entries 67 // are used, a number of elements are preallocated. 68 69 // 'ElementType' and 'KeyType' are respectively the types of the elements and 70 // their key. The structure only reclaims memory when safe to do so, if the 71 // number of elements that can be reclaimed is greater than `RECLAIM_FROM` and 72 // greater than `<total number of elements> / RECLAIM_FACTOR. 73 // clang-format off 74 #define TEMPLATE_INVALSET_P_DECL \ 75 class ElementType, \ 76 unsigned N_PREALLOCATED_ELEMENTS, \ 77 class KeyType, \ 78 KeyType INVALID_KEY, \ 79 size_t RECLAIM_FROM, \ 80 unsigned RECLAIM_FACTOR 81 // clang-format on 82 83 #define TEMPLATE_INVALSET_P_DEF \ 84 ElementType, N_PREALLOCATED_ELEMENTS, KeyType, INVALID_KEY, RECLAIM_FROM, \ 85 RECLAIM_FACTOR 86 87 template <class S> 88 class InvalSetIterator; // Forward declaration. 89 90 template <TEMPLATE_INVALSET_P_DECL> 91 class InvalSet { 92 public: 93 InvalSet(); 94 ~InvalSet(); 95 96 static const size_t kNPreallocatedElements = N_PREALLOCATED_ELEMENTS; 97 static const KeyType kInvalidKey = INVALID_KEY; 98 99 // C++ STL iterator interface. 100 typedef InvalSetIterator<InvalSet<TEMPLATE_INVALSET_P_DEF> > iterator; 101 iterator begin(); 102 iterator end(); 103 104 // It is illegal to insert an element already present in the set. 105 void insert(const ElementType& element); 106 107 // Looks for the specified element in the set and - if found - deletes it. 108 // The return value is the number of elements erased: either 0 or 1. 109 size_t erase(const ElementType& element); 110 111 // This indicates the number of (valid) elements stored in this set. 112 size_t size() const; 113 114 // Returns true if no elements are stored in the set. 115 // Note that this does not mean the the backing storage is empty: it can still 116 // contain invalid elements. 117 bool empty() const; 118 119 void clear(); 120 121 const ElementType GetMinElement(); 122 123 // This returns the key of the minimum element in the set. 124 KeyType GetMinElementKey(); 125 126 static bool IsValid(const ElementType& element); 127 static KeyType GetKey(const ElementType& element); 128 static void SetKey(ElementType* element, KeyType key); 129 130 typedef ElementType _ElementType; 131 typedef KeyType _KeyType; 132 133 protected: 134 // Returns a pointer to the element in vector_ if it was found, or NULL 135 // otherwise. 136 ElementType* Search(const ElementType& element); 137 138 // The argument *must* point to an element stored in *this* set. 139 // This function is not allowed to move elements in the backing vector 140 // storage. 141 void EraseInternal(ElementType* element); 142 143 // The elements in the range searched must be sorted. 144 ElementType* BinarySearch(const ElementType& element, 145 ElementType* start, 146 ElementType* end) const; 147 148 // Sort the elements. 149 enum SortType { 150 // The 'hard' version guarantees that invalid elements are moved to the end 151 // of the container. 152 kHardSort, 153 // The 'soft' version only guarantees that the elements will be sorted. 154 // Invalid elements may still be present anywhere in the set. 155 kSoftSort 156 }; 157 void Sort(SortType sort_type); 158 159 // Delete the elements that have an invalid key. The complexity is linear 160 // with the size of the vector. 161 void Clean(); 162 163 const ElementType Front() const; 164 const ElementType Back() const; 165 166 // Delete invalid trailing elements and return the last valid element in the 167 // set. 168 const ElementType CleanBack(); 169 170 // Returns a pointer to the start or end of the backing storage. 171 const ElementType* StorageBegin() const; 172 const ElementType* StorageEnd() const; 173 ElementType* StorageBegin(); 174 ElementType* StorageEnd(); 175 176 // Returns the index of the element within the backing storage. The element 177 // must belong to the backing storage. 178 size_t GetElementIndex(const ElementType* element) const; 179 180 // Returns the element at the specified index in the backing storage. 181 const ElementType* GetElementAt(size_t index) const; 182 ElementType* GetElementAt(size_t index); 183 184 static const ElementType* GetFirstValidElement(const ElementType* from, 185 const ElementType* end); 186 187 void CacheMinElement(); 188 const ElementType GetCachedMinElement() const; 189 190 bool ShouldReclaimMemory() const; 191 void ReclaimMemory(); 192 193 bool IsUsingVector() const { return vector_ != NULL; } 194 void SetSorted(bool sorted) { sorted_ = sorted; } 195 196 // We cache some data commonly required by users to improve performance. 197 // We cannot cache pointers to elements as we do not control the backing 198 // storage. 199 bool valid_cached_min_; 200 size_t cached_min_index_; // Valid iff `valid_cached_min_` is true. 201 KeyType cached_min_key_; // Valid iff `valid_cached_min_` is true. 202 203 // Indicates whether the elements are sorted. 204 bool sorted_; 205 206 // This represents the number of (valid) elements in this set. 207 size_t size_; 208 209 // The backing storage is either the array of preallocated elements or the 210 // vector. The structure starts by using the preallocated elements, and 211 // transitions (permanently) to using the vector once more than 212 // kNPreallocatedElements are used. 213 // Elements are only invalidated when using the vector. The preallocated 214 // storage always only contains valid elements. 215 ElementType preallocated_[kNPreallocatedElements]; 216 std::vector<ElementType>* vector_; 217 218 // Iterators acquire and release this monitor. While a set is acquired, 219 // certain operations are illegal to ensure that the iterator will 220 // correctly iterate over the elements in the set. 221 int monitor_; 222 #ifdef VIXL_DEBUG 223 int monitor() const { return monitor_; } 224 void Acquire() { monitor_++; } 225 void Release() { 226 monitor_--; 227 VIXL_ASSERT(monitor_ >= 0); 228 } 229 #endif 230 231 private: 232 // The copy constructor and assignment operator are not used and the defaults 233 // are unsafe, so disable them (without an implementation). 234 #if __cplusplus >= 201103L 235 InvalSet(const InvalSet& other) = delete; 236 InvalSet operator=(const InvalSet& other) = delete; 237 #else 238 InvalSet(const InvalSet& other); 239 InvalSet operator=(const InvalSet& other); 240 #endif 241 242 friend class InvalSetIterator<InvalSet<TEMPLATE_INVALSET_P_DEF> >; 243 }; 244 245 246 template <class S> 247 class InvalSetIterator : public std::iterator<std::forward_iterator_tag, 248 typename S::_ElementType> { 249 private: 250 // Redefine types to mirror the associated set types. 251 typedef typename S::_ElementType ElementType; 252 typedef typename S::_KeyType KeyType; 253 254 public: 255 explicit InvalSetIterator(S* inval_set = NULL); 256 257 // This class implements the standard copy-swap idiom. 258 ~InvalSetIterator(); 259 InvalSetIterator(const InvalSetIterator<S>& other); 260 InvalSetIterator<S>& operator=(InvalSetIterator<S> other); 261 #if __cplusplus >= 201103L 262 InvalSetIterator(InvalSetIterator<S>&& other) noexcept; 263 #endif 264 265 friend void swap(InvalSetIterator<S>& a, InvalSetIterator<S>& b) { 266 using std::swap; 267 swap(a.using_vector_, b.using_vector_); 268 swap(a.index_, b.index_); 269 swap(a.inval_set_, b.inval_set_); 270 } 271 272 // Return true if the iterator is at the end of the set. 273 bool Done() const; 274 275 // Move this iterator to the end of the set. 276 void Finish(); 277 278 // Delete the current element and advance the iterator to point to the next 279 // element. 280 void DeleteCurrentAndAdvance(); 281 282 static bool IsValid(const ElementType& element); 283 static KeyType GetKey(const ElementType& element); 284 285 // Extra helpers to support the forward-iterator interface. 286 InvalSetIterator<S>& operator++(); // Pre-increment. 287 InvalSetIterator<S> operator++(int); // Post-increment. 288 bool operator==(const InvalSetIterator<S>& rhs) const; 289 bool operator!=(const InvalSetIterator<S>& rhs) const { 290 return !(*this == rhs); 291 } 292 ElementType& operator*() { return *Current(); } 293 const ElementType& operator*() const { return *Current(); } 294 ElementType* operator->() { return Current(); } 295 const ElementType* operator->() const { return Current(); } 296 297 protected: 298 void MoveToValidElement(); 299 300 // Indicates if the iterator is looking at the vector or at the preallocated 301 // elements. 302 bool using_vector_; 303 // Used when looking at the preallocated elements, or in debug mode when using 304 // the vector to track how many times the iterator has advanced. 305 size_t index_; 306 typename std::vector<ElementType>::iterator iterator_; 307 S* inval_set_; 308 309 // TODO: These helpers are deprecated and will be removed in future versions 310 // of VIXL. 311 ElementType* Current() const; 312 void Advance(); 313 }; 314 315 316 template <TEMPLATE_INVALSET_P_DECL> 317 InvalSet<TEMPLATE_INVALSET_P_DEF>::InvalSet() 318 : valid_cached_min_(false), sorted_(true), size_(0), vector_(NULL) { 319 #ifdef VIXL_DEBUG 320 monitor_ = 0; 321 #endif 322 } 323 324 325 template <TEMPLATE_INVALSET_P_DECL> 326 InvalSet<TEMPLATE_INVALSET_P_DEF>::~InvalSet() { 327 VIXL_ASSERT(monitor_ == 0); 328 delete vector_; 329 } 330 331 332 template <TEMPLATE_INVALSET_P_DECL> 333 typename InvalSet<TEMPLATE_INVALSET_P_DEF>::iterator 334 InvalSet<TEMPLATE_INVALSET_P_DEF>::begin() { 335 return iterator(this); 336 } 337 338 339 template <TEMPLATE_INVALSET_P_DECL> 340 typename InvalSet<TEMPLATE_INVALSET_P_DEF>::iterator 341 InvalSet<TEMPLATE_INVALSET_P_DEF>::end() { 342 iterator end(this); 343 end.Finish(); 344 return end; 345 } 346 347 348 template <TEMPLATE_INVALSET_P_DECL> 349 void InvalSet<TEMPLATE_INVALSET_P_DEF>::insert(const ElementType& element) { 350 VIXL_ASSERT(monitor() == 0); 351 VIXL_ASSERT(IsValid(element)); 352 VIXL_ASSERT(Search(element) == NULL); 353 SetSorted(empty() || (sorted_ && (element > CleanBack()))); 354 if (IsUsingVector()) { 355 vector_->push_back(element); 356 } else { 357 if (size_ < kNPreallocatedElements) { 358 preallocated_[size_] = element; 359 } else { 360 // Transition to using the vector. 361 vector_ = 362 new std::vector<ElementType>(preallocated_, preallocated_ + size_); 363 vector_->push_back(element); 364 } 365 } 366 size_++; 367 368 if (valid_cached_min_ && (element < GetMinElement())) { 369 cached_min_index_ = IsUsingVector() ? vector_->size() - 1 : size_ - 1; 370 cached_min_key_ = GetKey(element); 371 valid_cached_min_ = true; 372 } 373 374 if (ShouldReclaimMemory()) { 375 ReclaimMemory(); 376 } 377 } 378 379 380 template <TEMPLATE_INVALSET_P_DECL> 381 size_t InvalSet<TEMPLATE_INVALSET_P_DEF>::erase(const ElementType& element) { 382 VIXL_ASSERT(monitor() == 0); 383 VIXL_ASSERT(IsValid(element)); 384 ElementType* local_element = Search(element); 385 if (local_element != NULL) { 386 EraseInternal(local_element); 387 return 1; 388 } 389 return 0; 390 } 391 392 393 template <TEMPLATE_INVALSET_P_DECL> 394 ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::Search( 395 const ElementType& element) { 396 VIXL_ASSERT(monitor() == 0); 397 if (empty()) { 398 return NULL; 399 } 400 if (ShouldReclaimMemory()) { 401 ReclaimMemory(); 402 } 403 if (!sorted_) { 404 Sort(kHardSort); 405 } 406 if (!valid_cached_min_) { 407 CacheMinElement(); 408 } 409 return BinarySearch(element, GetElementAt(cached_min_index_), StorageEnd()); 410 } 411 412 413 template <TEMPLATE_INVALSET_P_DECL> 414 size_t InvalSet<TEMPLATE_INVALSET_P_DEF>::size() const { 415 return size_; 416 } 417 418 419 template <TEMPLATE_INVALSET_P_DECL> 420 bool InvalSet<TEMPLATE_INVALSET_P_DEF>::empty() const { 421 return size_ == 0; 422 } 423 424 425 template <TEMPLATE_INVALSET_P_DECL> 426 void InvalSet<TEMPLATE_INVALSET_P_DEF>::clear() { 427 VIXL_ASSERT(monitor() == 0); 428 size_ = 0; 429 if (IsUsingVector()) { 430 vector_->clear(); 431 } 432 SetSorted(true); 433 valid_cached_min_ = false; 434 } 435 436 437 template <TEMPLATE_INVALSET_P_DECL> 438 const ElementType InvalSet<TEMPLATE_INVALSET_P_DEF>::GetMinElement() { 439 VIXL_ASSERT(monitor() == 0); 440 VIXL_ASSERT(!empty()); 441 CacheMinElement(); 442 return *GetElementAt(cached_min_index_); 443 } 444 445 446 template <TEMPLATE_INVALSET_P_DECL> 447 KeyType InvalSet<TEMPLATE_INVALSET_P_DEF>::GetMinElementKey() { 448 VIXL_ASSERT(monitor() == 0); 449 if (valid_cached_min_) { 450 return cached_min_key_; 451 } else { 452 return GetKey(GetMinElement()); 453 } 454 } 455 456 457 template <TEMPLATE_INVALSET_P_DECL> 458 bool InvalSet<TEMPLATE_INVALSET_P_DEF>::IsValid(const ElementType& element) { 459 return GetKey(element) != kInvalidKey; 460 } 461 462 463 template <TEMPLATE_INVALSET_P_DECL> 464 void InvalSet<TEMPLATE_INVALSET_P_DEF>::EraseInternal(ElementType* element) { 465 // Note that this function must be safe even while an iterator has acquired 466 // this set. 467 VIXL_ASSERT(element != NULL); 468 size_t deleted_index = GetElementIndex(element); 469 if (IsUsingVector()) { 470 VIXL_ASSERT((&(vector_->front()) <= element) && 471 (element <= &(vector_->back()))); 472 SetKey(element, kInvalidKey); 473 } else { 474 VIXL_ASSERT((preallocated_ <= element) && 475 (element < (preallocated_ + kNPreallocatedElements))); 476 ElementType* end = preallocated_ + kNPreallocatedElements; 477 size_t copy_size = sizeof(*element) * (end - element - 1); 478 memmove(element, element + 1, copy_size); 479 } 480 size_--; 481 482 if (valid_cached_min_ && (deleted_index == cached_min_index_)) { 483 if (sorted_ && !empty()) { 484 const ElementType* min = GetFirstValidElement(element, StorageEnd()); 485 cached_min_index_ = GetElementIndex(min); 486 cached_min_key_ = GetKey(*min); 487 valid_cached_min_ = true; 488 } else { 489 valid_cached_min_ = false; 490 } 491 } 492 } 493 494 495 template <TEMPLATE_INVALSET_P_DECL> 496 ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::BinarySearch( 497 const ElementType& element, ElementType* start, ElementType* end) const { 498 if (start == end) { 499 return NULL; 500 } 501 VIXL_ASSERT(sorted_); 502 VIXL_ASSERT(start < end); 503 VIXL_ASSERT(!empty()); 504 505 // Perform a binary search through the elements while ignoring invalid 506 // elements. 507 ElementType* elements = start; 508 size_t low = 0; 509 size_t high = (end - start) - 1; 510 while (low < high) { 511 // Find valid bounds. 512 while (!IsValid(elements[low]) && (low < high)) ++low; 513 while (!IsValid(elements[high]) && (low < high)) --high; 514 VIXL_ASSERT(low <= high); 515 // Avoid overflow when computing the middle index. 516 size_t middle = low + (high - low) / 2; 517 if ((middle == low) || (middle == high)) { 518 break; 519 } 520 while ((middle < high - 1) && !IsValid(elements[middle])) ++middle; 521 while ((low + 1 < middle) && !IsValid(elements[middle])) --middle; 522 if (!IsValid(elements[middle])) { 523 break; 524 } 525 if (elements[middle] < element) { 526 low = middle; 527 } else { 528 high = middle; 529 } 530 } 531 532 if (elements[low] == element) return &elements[low]; 533 if (elements[high] == element) return &elements[high]; 534 return NULL; 535 } 536 537 538 template <TEMPLATE_INVALSET_P_DECL> 539 void InvalSet<TEMPLATE_INVALSET_P_DEF>::Sort(SortType sort_type) { 540 if (sort_type == kSoftSort) { 541 if (sorted_) { 542 return; 543 } 544 } 545 VIXL_ASSERT(monitor() == 0); 546 if (empty()) { 547 return; 548 } 549 550 Clean(); 551 std::sort(StorageBegin(), StorageEnd()); 552 553 SetSorted(true); 554 cached_min_index_ = 0; 555 cached_min_key_ = GetKey(Front()); 556 valid_cached_min_ = true; 557 } 558 559 560 template <TEMPLATE_INVALSET_P_DECL> 561 void InvalSet<TEMPLATE_INVALSET_P_DEF>::Clean() { 562 VIXL_ASSERT(monitor() == 0); 563 if (empty() || !IsUsingVector()) { 564 return; 565 } 566 // Manually iterate through the vector storage to discard invalid elements. 567 ElementType* start = &(vector_->front()); 568 ElementType* end = start + vector_->size(); 569 ElementType* c = start; 570 ElementType* first_invalid; 571 ElementType* first_valid; 572 ElementType* next_invalid; 573 574 while ((c < end) && IsValid(*c)) c++; 575 first_invalid = c; 576 577 while (c < end) { 578 while ((c < end) && !IsValid(*c)) c++; 579 first_valid = c; 580 while ((c < end) && IsValid(*c)) c++; 581 next_invalid = c; 582 583 ptrdiff_t n_moved_elements = (next_invalid - first_valid); 584 memmove(first_invalid, first_valid, n_moved_elements * sizeof(*c)); 585 first_invalid = first_invalid + n_moved_elements; 586 c = next_invalid; 587 } 588 589 // Delete the trailing invalid elements. 590 vector_->erase(vector_->begin() + (first_invalid - start), vector_->end()); 591 VIXL_ASSERT(vector_->size() == size_); 592 593 if (sorted_) { 594 valid_cached_min_ = true; 595 cached_min_index_ = 0; 596 cached_min_key_ = GetKey(*GetElementAt(0)); 597 } else { 598 valid_cached_min_ = false; 599 } 600 } 601 602 603 template <TEMPLATE_INVALSET_P_DECL> 604 const ElementType InvalSet<TEMPLATE_INVALSET_P_DEF>::Front() const { 605 VIXL_ASSERT(!empty()); 606 return IsUsingVector() ? vector_->front() : preallocated_[0]; 607 } 608 609 610 template <TEMPLATE_INVALSET_P_DECL> 611 const ElementType InvalSet<TEMPLATE_INVALSET_P_DEF>::Back() const { 612 VIXL_ASSERT(!empty()); 613 return IsUsingVector() ? vector_->back() : preallocated_[size_ - 1]; 614 } 615 616 617 template <TEMPLATE_INVALSET_P_DECL> 618 const ElementType InvalSet<TEMPLATE_INVALSET_P_DEF>::CleanBack() { 619 VIXL_ASSERT(monitor() == 0); 620 if (IsUsingVector()) { 621 // Delete the invalid trailing elements. 622 typename std::vector<ElementType>::reverse_iterator it = vector_->rbegin(); 623 while (!IsValid(*it)) { 624 it++; 625 } 626 vector_->erase(it.base(), vector_->end()); 627 } 628 return Back(); 629 } 630 631 632 template <TEMPLATE_INVALSET_P_DECL> 633 const ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::StorageBegin() const { 634 return IsUsingVector() ? &(vector_->front()) : preallocated_; 635 } 636 637 638 template <TEMPLATE_INVALSET_P_DECL> 639 const ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::StorageEnd() const { 640 return IsUsingVector() ? &(vector_->back()) + 1 : preallocated_ + size_; 641 } 642 643 644 template <TEMPLATE_INVALSET_P_DECL> 645 ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::StorageBegin() { 646 return IsUsingVector() ? &(vector_->front()) : preallocated_; 647 } 648 649 650 template <TEMPLATE_INVALSET_P_DECL> 651 ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::StorageEnd() { 652 return IsUsingVector() ? &(vector_->back()) + 1 : preallocated_ + size_; 653 } 654 655 656 template <TEMPLATE_INVALSET_P_DECL> 657 size_t InvalSet<TEMPLATE_INVALSET_P_DEF>::GetElementIndex( 658 const ElementType* element) const { 659 VIXL_ASSERT((StorageBegin() <= element) && (element < StorageEnd())); 660 return element - StorageBegin(); 661 } 662 663 664 template <TEMPLATE_INVALSET_P_DECL> 665 const ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::GetElementAt( 666 size_t index) const { 667 VIXL_ASSERT((IsUsingVector() && (index < vector_->size())) || 668 (index < size_)); 669 return StorageBegin() + index; 670 } 671 672 template <TEMPLATE_INVALSET_P_DECL> 673 ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::GetElementAt(size_t index) { 674 VIXL_ASSERT((IsUsingVector() && (index < vector_->size())) || 675 (index < size_)); 676 return StorageBegin() + index; 677 } 678 679 template <TEMPLATE_INVALSET_P_DECL> 680 const ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::GetFirstValidElement( 681 const ElementType* from, const ElementType* end) { 682 while ((from < end) && !IsValid(*from)) { 683 from++; 684 } 685 return from; 686 } 687 688 689 template <TEMPLATE_INVALSET_P_DECL> 690 void InvalSet<TEMPLATE_INVALSET_P_DEF>::CacheMinElement() { 691 VIXL_ASSERT(monitor() == 0); 692 VIXL_ASSERT(!empty()); 693 694 if (valid_cached_min_) { 695 return; 696 } 697 698 if (sorted_) { 699 const ElementType* min = GetFirstValidElement(StorageBegin(), StorageEnd()); 700 cached_min_index_ = GetElementIndex(min); 701 cached_min_key_ = GetKey(*min); 702 valid_cached_min_ = true; 703 } else { 704 Sort(kHardSort); 705 } 706 VIXL_ASSERT(valid_cached_min_); 707 } 708 709 710 template <TEMPLATE_INVALSET_P_DECL> 711 bool InvalSet<TEMPLATE_INVALSET_P_DEF>::ShouldReclaimMemory() const { 712 if (!IsUsingVector()) { 713 return false; 714 } 715 size_t n_invalid_elements = vector_->size() - size_; 716 return (n_invalid_elements > RECLAIM_FROM) && 717 (n_invalid_elements > vector_->size() / RECLAIM_FACTOR); 718 } 719 720 721 template <TEMPLATE_INVALSET_P_DECL> 722 void InvalSet<TEMPLATE_INVALSET_P_DEF>::ReclaimMemory() { 723 VIXL_ASSERT(monitor() == 0); 724 Clean(); 725 } 726 727 728 template <class S> 729 InvalSetIterator<S>::InvalSetIterator(S* inval_set) 730 : using_vector_((inval_set != NULL) && inval_set->IsUsingVector()), 731 index_(0), 732 inval_set_(inval_set) { 733 if (inval_set != NULL) { 734 inval_set->Sort(S::kSoftSort); 735 #ifdef VIXL_DEBUG 736 inval_set->Acquire(); 737 #endif 738 if (using_vector_) { 739 iterator_ = typename std::vector<ElementType>::iterator( 740 inval_set_->vector_->begin()); 741 } 742 MoveToValidElement(); 743 } 744 } 745 746 747 template <class S> 748 InvalSetIterator<S>::~InvalSetIterator() { 749 #ifdef VIXL_DEBUG 750 if (inval_set_ != NULL) inval_set_->Release(); 751 #endif 752 } 753 754 755 template <class S> 756 typename S::_ElementType* InvalSetIterator<S>::Current() const { 757 VIXL_ASSERT(!Done()); 758 if (using_vector_) { 759 return &(*iterator_); 760 } else { 761 return &(inval_set_->preallocated_[index_]); 762 } 763 } 764 765 766 template <class S> 767 void InvalSetIterator<S>::Advance() { 768 ++(*this); 769 } 770 771 772 template <class S> 773 bool InvalSetIterator<S>::Done() const { 774 if (using_vector_) { 775 bool done = (iterator_ == inval_set_->vector_->end()); 776 VIXL_ASSERT(done == (index_ == inval_set_->size())); 777 return done; 778 } else { 779 return index_ == inval_set_->size(); 780 } 781 } 782 783 784 template <class S> 785 void InvalSetIterator<S>::Finish() { 786 VIXL_ASSERT(inval_set_->sorted_); 787 if (using_vector_) { 788 iterator_ = inval_set_->vector_->end(); 789 } 790 index_ = inval_set_->size(); 791 } 792 793 794 template <class S> 795 void InvalSetIterator<S>::DeleteCurrentAndAdvance() { 796 if (using_vector_) { 797 inval_set_->EraseInternal(&(*iterator_)); 798 MoveToValidElement(); 799 } else { 800 inval_set_->EraseInternal(inval_set_->preallocated_ + index_); 801 } 802 } 803 804 805 template <class S> 806 bool InvalSetIterator<S>::IsValid(const ElementType& element) { 807 return S::IsValid(element); 808 } 809 810 811 template <class S> 812 typename S::_KeyType InvalSetIterator<S>::GetKey(const ElementType& element) { 813 return S::GetKey(element); 814 } 815 816 817 template <class S> 818 void InvalSetIterator<S>::MoveToValidElement() { 819 if (using_vector_) { 820 while ((iterator_ != inval_set_->vector_->end()) && !IsValid(*iterator_)) { 821 iterator_++; 822 } 823 } else { 824 VIXL_ASSERT(inval_set_->empty() || IsValid(inval_set_->preallocated_[0])); 825 // Nothing to do. 826 } 827 } 828 829 830 template <class S> 831 InvalSetIterator<S>::InvalSetIterator(const InvalSetIterator<S>& other) 832 : using_vector_(other.using_vector_), 833 index_(other.index_), 834 inval_set_(other.inval_set_) { 835 #ifdef VIXL_DEBUG 836 if (inval_set_ != NULL) inval_set_->Acquire(); 837 #endif 838 } 839 840 841 #if __cplusplus >= 201103L 842 template <class S> 843 InvalSetIterator<S>::InvalSetIterator(InvalSetIterator<S>&& other) noexcept 844 : using_vector_(false), 845 index_(0), 846 inval_set_(NULL) { 847 swap(*this, other); 848 } 849 #endif 850 851 852 template <class S> 853 InvalSetIterator<S>& InvalSetIterator<S>::operator=(InvalSetIterator<S> other) { 854 swap(*this, other); 855 return *this; 856 } 857 858 859 template <class S> 860 bool InvalSetIterator<S>::operator==(const InvalSetIterator<S>& rhs) const { 861 bool equal = (inval_set_ == rhs.inval_set_); 862 863 // If the inval_set_ matches, using_vector_ must also match. 864 VIXL_ASSERT(!equal || (using_vector_ == rhs.using_vector_)); 865 866 if (using_vector_) { 867 equal = equal && (iterator_ == rhs.iterator_); 868 // In debug mode, index_ is maintained even with using_vector_. 869 VIXL_ASSERT(!equal || (index_ == rhs.index_)); 870 } else { 871 equal = equal && (index_ == rhs.index_); 872 #ifdef DEBUG 873 // If not using_vector_, iterator_ should be default-initialised. 874 typename std::vector<ElementType>::iterator default_iterator; 875 VIXL_ASSERT(iterator_ == default_iterator); 876 VIXL_ASSERT(rhs.iterator_ == default_iterator); 877 #endif 878 } 879 return equal; 880 } 881 882 883 template <class S> 884 InvalSetIterator<S>& InvalSetIterator<S>::operator++() { 885 // Pre-increment. 886 VIXL_ASSERT(!Done()); 887 if (using_vector_) { 888 iterator_++; 889 #ifdef VIXL_DEBUG 890 index_++; 891 #endif 892 MoveToValidElement(); 893 } else { 894 index_++; 895 } 896 return *this; 897 } 898 899 900 template <class S> 901 InvalSetIterator<S> InvalSetIterator<S>::operator++(int /* unused */) { 902 // Post-increment. 903 VIXL_ASSERT(!Done()); 904 InvalSetIterator<S> old(*this); 905 ++(*this); 906 return old; 907 } 908 909 910 #undef TEMPLATE_INVALSET_P_DECL 911 #undef TEMPLATE_INVALSET_P_DEF 912 913 } // namespace vixl 914 915 #endif // VIXL_INVALSET_H_ 916