qemu/disas/libvixl/vixl/invalset.h

   1 // Copyright 2015, ARM Limited
   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 <string.h>
  31
  32 #include <algorithm>
  33 #include <vector>
  34
  35 #include "vixl/globals.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 #define TEMPLATE_INVALSET_P_DECL                                               \
  74   class ElementType,                                                           \
  75   unsigned N_PREALLOCATED_ELEMENTS,                                            \
  76   class KeyType,                                                               \
  77   KeyType INVALID_KEY,                                                         \
  78   size_t RECLAIM_FROM,                                                         \
  79   unsigned RECLAIM_FACTOR
  80
  81 #define TEMPLATE_INVALSET_P_DEF                                                \
  82 ElementType, N_PREALLOCATED_ELEMENTS,                                          \
  83 KeyType, INVALID_KEY, RECLAIM_FROM, RECLAIM_FACTOR
  84
  85 template<class S> class InvalSetIterator;  // Forward declaration.
  86
  87 template<TEMPLATE_INVALSET_P_DECL> class InvalSet {
  88  public:
  89   InvalSet();
  90   ~InvalSet();
  91
  92   static const size_t kNPreallocatedElements = N_PREALLOCATED_ELEMENTS;
  93   static const KeyType kInvalidKey = INVALID_KEY;
  94
  95   // It is illegal to insert an element already present in the set.
  96   void insert(const ElementType& element);
  97
  98   // Looks for the specified element in the set and - if found - deletes it.
  99   void erase(const ElementType& element);
 100
 101   // This indicates the number of (valid) elements stored in this set.
 102   size_t size() const;
 103
 104   // Returns true if no elements are stored in the set.
 105   // Note that this does not mean the the backing storage is empty: it can still
 106   // contain invalid elements.
 107   bool empty() const;
 108
 109   void clear();
 110
 111   const ElementType min_element();
 112
 113   // This returns the key of the minimum element in the set.
 114   KeyType min_element_key();
 115
 116   static bool IsValid(const ElementType& element);
 117   static KeyType Key(const ElementType& element);
 118   static void SetKey(ElementType* element, KeyType key);
 119
 120  protected:
 121   // Returns a pointer to the element in vector_ if it was found, or NULL
 122   // otherwise.
 123   ElementType* Search(const ElementType& element);
 124
 125   // The argument *must* point to an element stored in *this* set.
 126   // This function is not allowed to move elements in the backing vector
 127   // storage.
 128   void EraseInternal(ElementType* element);
 129
 130   // The elements in the range searched must be sorted.
 131   ElementType* BinarySearch(const ElementType& element,
 132                             ElementType* start,
 133                             ElementType* end) const;
 134
 135   // Sort the elements.
 136   enum SortType {
 137     // The 'hard' version guarantees that invalid elements are moved to the end
 138     // of the container.
 139     kHardSort,
 140     // The 'soft' version only guarantees that the elements will be sorted.
 141     // Invalid elements may still be present anywhere in the set.
 142     kSoftSort
 143   };
 144   void Sort(SortType sort_type);
 145
 146   // Delete the elements that have an invalid key. The complexity is linear
 147   // with the size of the vector.
 148   void Clean();
 149
 150   const ElementType Front() const;
 151   const ElementType Back() const;
 152
 153   // Delete invalid trailing elements and return the last valid element in the
 154   // set.
 155   const ElementType CleanBack();
 156
 157   // Returns a pointer to the start or end of the backing storage.
 158   const ElementType* StorageBegin() const;
 159   const ElementType* StorageEnd() const;
 160   ElementType* StorageBegin();
 161   ElementType* StorageEnd();
 162
 163   // Returns the index of the element within the backing storage. The element
 164   // must belong to the backing storage.
 165   size_t ElementIndex(const ElementType* element) const;
 166
 167   // Returns the element at the specified index in the backing storage.
 168   const ElementType* ElementAt(size_t index) const;
 169   ElementType* ElementAt(size_t index);
 170
 171   static const ElementType* FirstValidElement(const ElementType* from,
 172                                               const ElementType* end);
 173
 174   void CacheMinElement();
 175   const ElementType CachedMinElement() const;
 176
 177   bool ShouldReclaimMemory() const;
 178   void ReclaimMemory();
 179
 180   bool IsUsingVector() const { return vector_ != NULL; }
 181   void set_sorted(bool sorted) { sorted_ = sorted; }
 182
 183   // We cache some data commonly required by users to improve performance.
 184   // We cannot cache pointers to elements as we do not control the backing
 185   // storage.
 186   bool valid_cached_min_;
 187   size_t cached_min_index_;  // Valid iff `valid_cached_min_` is true.
 188   KeyType cached_min_key_;         // Valid iff `valid_cached_min_` is true.
 189
 190   // Indicates whether the elements are sorted.
 191   bool sorted_;
 192
 193   // This represents the number of (valid) elements in this set.
 194   size_t size_;
 195
 196   // The backing storage is either the array of preallocated elements or the
 197   // vector. The structure starts by using the preallocated elements, and
 198   // transitions (permanently) to using the vector once more than
 199   // kNPreallocatedElements are used.
 200   // Elements are only invalidated when using the vector. The preallocated
 201   // storage always only contains valid elements.
 202   ElementType preallocated_[kNPreallocatedElements];
 203   std::vector<ElementType>* vector_;
 204
 205 #ifdef VIXL_DEBUG
 206   // Iterators acquire and release this monitor. While a set is acquired,
 207   // certain operations are illegal to ensure that the iterator will
 208   // correctly iterate over the elements in the set.
 209   int monitor_;
 210   int monitor() const { return monitor_; }
 211   void Acquire() { monitor_++; }
 212   void Release() {
 213     monitor_--;
 214     VIXL_ASSERT(monitor_ >= 0);
 215   }
 216 #endif
 217
 218   friend class InvalSetIterator<InvalSet<TEMPLATE_INVALSET_P_DEF> >;
 219   typedef ElementType _ElementType;
 220   typedef KeyType _KeyType;
 221 };
 222
 223
 224 template<class S> class InvalSetIterator {
 225  private:
 226   // Redefine types to mirror the associated set types.
 227   typedef typename S::_ElementType ElementType;
 228   typedef typename S::_KeyType KeyType;
 229
 230  public:
 231   explicit InvalSetIterator(S* inval_set);
 232   ~InvalSetIterator();
 233
 234   ElementType* Current() const;
 235   void Advance();
 236   bool Done() const;
 237
 238   // Mark this iterator as 'done'.
 239   void Finish();
 240
 241   // Delete the current element and advance the iterator to point to the next
 242   // element.
 243   void DeleteCurrentAndAdvance();
 244
 245   static bool IsValid(const ElementType& element);
 246   static KeyType Key(const ElementType& element);
 247
 248  protected:
 249   void MoveToValidElement();
 250
 251   // Indicates if the iterator is looking at the vector or at the preallocated
 252   // elements.
 253   const bool using_vector_;
 254   // Used when looking at the preallocated elements, or in debug mode when using
 255   // the vector to track how many times the iterator has advanced.
 256   size_t index_;
 257   typename std::vector<ElementType>::iterator iterator_;
 258   S* inval_set_;
 259 };
 260
 261
 262 template<TEMPLATE_INVALSET_P_DECL>
 263 InvalSet<TEMPLATE_INVALSET_P_DEF>::InvalSet()
 264   : valid_cached_min_(false),
 265     sorted_(true), size_(0), vector_(NULL) {
 266 #ifdef VIXL_DEBUG
 267   monitor_ = 0;
 268 #endif
 269 }
 270
 271
 272 template<TEMPLATE_INVALSET_P_DECL>
 273 InvalSet<TEMPLATE_INVALSET_P_DEF>::~InvalSet() {
 274   VIXL_ASSERT(monitor_ == 0);
 275   delete vector_;
 276 }
 277
 278
 279 template<TEMPLATE_INVALSET_P_DECL>
 280 void InvalSet<TEMPLATE_INVALSET_P_DEF>::insert(const ElementType& element) {
 281   VIXL_ASSERT(monitor() == 0);
 282   VIXL_ASSERT(IsValid(element));
 283   VIXL_ASSERT(Search(element) == NULL);
 284   set_sorted(empty() || (sorted_ && (element > CleanBack())));
 285   if (IsUsingVector()) {
 286     vector_->push_back(element);
 287   } else {
 288     if (size_ < kNPreallocatedElements) {
 289       preallocated_[size_] = element;
 290     } else {
 291       // Transition to using the vector.
 292       vector_ = new std::vector<ElementType>(preallocated_,
 293                                              preallocated_ + size_);
 294       vector_->push_back(element);
 295     }
 296   }
 297   size_++;
 298
 299   if (valid_cached_min_ && (element < min_element())) {
 300     cached_min_index_ = IsUsingVector() ? vector_->size() - 1 : size_ - 1;
 301     cached_min_key_ = Key(element);
 302     valid_cached_min_ = true;
 303   }
 304
 305   if (ShouldReclaimMemory()) {
 306     ReclaimMemory();
 307   }
 308 }
 309
 310
 311 template<TEMPLATE_INVALSET_P_DECL>
 312 void InvalSet<TEMPLATE_INVALSET_P_DEF>::erase(const ElementType& element) {
 313   VIXL_ASSERT(monitor() == 0);
 314   VIXL_ASSERT(IsValid(element));
 315   ElementType* local_element = Search(element);
 316   if (local_element != NULL) {
 317     EraseInternal(local_element);
 318   }
 319 }
 320
 321
 322 template<TEMPLATE_INVALSET_P_DECL>
 323 ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::Search(
 324     const ElementType& element) {
 325   VIXL_ASSERT(monitor() == 0);
 326   if (empty()) {
 327     return NULL;
 328   }
 329   if (ShouldReclaimMemory()) {
 330     ReclaimMemory();
 331   }
 332   if (!sorted_) {
 333     Sort(kHardSort);
 334   }
 335   if (!valid_cached_min_) {
 336     CacheMinElement();
 337   }
 338   return BinarySearch(element, ElementAt(cached_min_index_), StorageEnd());
 339 }
 340
 341
 342 template<TEMPLATE_INVALSET_P_DECL>
 343 size_t InvalSet<TEMPLATE_INVALSET_P_DEF>::size() const {
 344   return size_;
 345 }
 346
 347
 348 template<TEMPLATE_INVALSET_P_DECL>
 349 bool InvalSet<TEMPLATE_INVALSET_P_DEF>::empty() const {
 350   return size_ == 0;
 351 }
 352
 353
 354 template<TEMPLATE_INVALSET_P_DECL>
 355 void InvalSet<TEMPLATE_INVALSET_P_DEF>::clear() {
 356   VIXL_ASSERT(monitor() == 0);
 357   size_ = 0;
 358   if (IsUsingVector()) {
 359     vector_->clear();
 360   }
 361   set_sorted(true);
 362   valid_cached_min_ = false;
 363 }
 364
 365
 366 template<TEMPLATE_INVALSET_P_DECL>
 367 const ElementType InvalSet<TEMPLATE_INVALSET_P_DEF>::min_element() {
 368   VIXL_ASSERT(monitor() == 0);
 369   VIXL_ASSERT(!empty());
 370   CacheMinElement();
 371   return *ElementAt(cached_min_index_);
 372 }
 373
 374
 375 template<TEMPLATE_INVALSET_P_DECL>
 376 KeyType InvalSet<TEMPLATE_INVALSET_P_DEF>::min_element_key() {
 377   VIXL_ASSERT(monitor() == 0);
 378   if (valid_cached_min_) {
 379     return cached_min_key_;
 380   } else {
 381     return Key(min_element());
 382   }
 383 }
 384
 385
 386 template<TEMPLATE_INVALSET_P_DECL>
 387 bool InvalSet<TEMPLATE_INVALSET_P_DEF>::IsValid(const ElementType& element) {
 388   return Key(element) != kInvalidKey;
 389 }
 390
 391
 392 template<TEMPLATE_INVALSET_P_DECL>
 393 void InvalSet<TEMPLATE_INVALSET_P_DEF>::EraseInternal(ElementType* element) {
 394   // Note that this function must be safe even while an iterator has acquired
 395   // this set.
 396   VIXL_ASSERT(element != NULL);
 397   size_t deleted_index = ElementIndex(element);
 398   if (IsUsingVector()) {
 399     VIXL_ASSERT((&(vector_->front()) <= element) &&
 400                 (element <= &(vector_->back())));
 401     SetKey(element, kInvalidKey);
 402   } else {
 403     VIXL_ASSERT((preallocated_ <= element) &&
 404                 (element < (preallocated_ + kNPreallocatedElements)));
 405     ElementType* end = preallocated_ + kNPreallocatedElements;
 406     size_t copy_size = sizeof(*element) * (end - element - 1);
 407     memmove(element, element + 1, copy_size);
 408   }
 409   size_--;
 410
 411   if (valid_cached_min_ &&
 412       (deleted_index == cached_min_index_)) {
 413     if (sorted_ && !empty()) {
 414       const ElementType* min = FirstValidElement(element, StorageEnd());
 415       cached_min_index_ = ElementIndex(min);
 416       cached_min_key_ = Key(*min);
 417       valid_cached_min_ = true;
 418     } else {
 419       valid_cached_min_ = false;
 420     }
 421   }
 422 }
 423
 424
 425 template<TEMPLATE_INVALSET_P_DECL>
 426 ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::BinarySearch(
 427     const ElementType& element, ElementType* start, ElementType* end) const {
 428   if (start == end) {
 429     return NULL;
 430   }
 431   VIXL_ASSERT(sorted_);
 432   VIXL_ASSERT(start < end);
 433   VIXL_ASSERT(!empty());
 434
 435   // Perform a binary search through the elements while ignoring invalid
 436   // elements.
 437   ElementType* elements = start;
 438   size_t low = 0;
 439   size_t high = (end - start) - 1;
 440   while (low < high) {
 441     // Find valid bounds.
 442     while (!IsValid(elements[low]) && (low < high)) ++low;
 443     while (!IsValid(elements[high]) && (low < high)) --high;
 444     VIXL_ASSERT(low <= high);
 445     // Avoid overflow when computing the middle index.
 446     size_t middle = low / 2 + high / 2 + (low & high & 1);
 447     if ((middle == low) || (middle == high)) {
 448       break;
 449     }
 450     while (!IsValid(elements[middle]) && (middle < high - 1)) ++middle;
 451     while (!IsValid(elements[middle]) && (low + 1 < middle)) --middle;
 452     if (!IsValid(elements[middle])) {
 453       break;
 454     }
 455     if (elements[middle] < element) {
 456       low = middle;
 457     } else {
 458       high = middle;
 459     }
 460   }
 461
 462   if (elements[low] == element) return &elements[low];
 463   if (elements[high] == element) return &elements[high];
 464   return NULL;
 465 }
 466
 467
 468 template<TEMPLATE_INVALSET_P_DECL>
 469 void InvalSet<TEMPLATE_INVALSET_P_DEF>::Sort(SortType sort_type) {
 470   VIXL_ASSERT(monitor() == 0);
 471   if (sort_type == kSoftSort) {
 472     if (sorted_) {
 473       return;
 474     }
 475   }
 476   if (empty()) {
 477     return;
 478   }
 479
 480   Clean();
 481   std::sort(StorageBegin(), StorageEnd());
 482
 483   set_sorted(true);
 484   cached_min_index_ = 0;
 485   cached_min_key_ = Key(Front());
 486   valid_cached_min_ = true;
 487 }
 488
 489
 490 template<TEMPLATE_INVALSET_P_DECL>
 491 void InvalSet<TEMPLATE_INVALSET_P_DEF>::Clean() {
 492   VIXL_ASSERT(monitor() == 0);
 493   if (empty() || !IsUsingVector()) {
 494     return;
 495   }
 496   // Manually iterate through the vector storage to discard invalid elements.
 497   ElementType* start = &(vector_->front());
 498   ElementType* end = start + vector_->size();
 499   ElementType* c = start;
 500   ElementType* first_invalid;
 501   ElementType* first_valid;
 502   ElementType* next_invalid;
 503
 504   while (c < end && IsValid(*c)) { c++; }
 505   first_invalid = c;
 506
 507   while (c < end) {
 508     while (c < end && !IsValid(*c)) { c++; }
 509     first_valid = c;
 510     while (c < end && IsValid(*c)) { c++; }
 511     next_invalid = c;
 512
 513     ptrdiff_t n_moved_elements = (next_invalid - first_valid);
 514     memmove(first_invalid, first_valid,  n_moved_elements * sizeof(*c));
 515     first_invalid = first_invalid + n_moved_elements;
 516     c = next_invalid;
 517   }
 518
 519   // Delete the trailing invalid elements.
 520   vector_->erase(vector_->begin() + (first_invalid - start), vector_->end());
 521   VIXL_ASSERT(vector_->size() == size_);
 522
 523   if (sorted_) {
 524     valid_cached_min_ = true;
 525     cached_min_index_ = 0;
 526     cached_min_key_ = Key(*ElementAt(0));
 527   } else {
 528     valid_cached_min_ = false;
 529   }
 530 }
 531
 532
 533 template<TEMPLATE_INVALSET_P_DECL>
 534 const ElementType InvalSet<TEMPLATE_INVALSET_P_DEF>::Front() const {
 535   VIXL_ASSERT(!empty());
 536   return IsUsingVector() ? vector_->front() : preallocated_[0];
 537 }
 538
 539
 540 template<TEMPLATE_INVALSET_P_DECL>
 541 const ElementType InvalSet<TEMPLATE_INVALSET_P_DEF>::Back() const {
 542   VIXL_ASSERT(!empty());
 543   return IsUsingVector() ? vector_->back() : preallocated_[size_ - 1];
 544 }
 545
 546
 547 template<TEMPLATE_INVALSET_P_DECL>
 548 const ElementType InvalSet<TEMPLATE_INVALSET_P_DEF>::CleanBack() {
 549   VIXL_ASSERT(monitor() == 0);
 550   if (IsUsingVector()) {
 551     // Delete the invalid trailing elements.
 552     typename std::vector<ElementType>::reverse_iterator it = vector_->rbegin();
 553     while (!IsValid(*it)) {
 554       it++;
 555     }
 556     vector_->erase(it.base(), vector_->end());
 557   }
 558   return Back();
 559 }
 560
 561
 562 template<TEMPLATE_INVALSET_P_DECL>
 563 const ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::StorageBegin() const {
 564   return IsUsingVector() ? &(vector_->front()) : preallocated_;
 565 }
 566
 567
 568 template<TEMPLATE_INVALSET_P_DECL>
 569 const ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::StorageEnd() const {
 570   return IsUsingVector() ? &(vector_->back()) + 1 : preallocated_ + size_;
 571 }
 572
 573
 574 template<TEMPLATE_INVALSET_P_DECL>
 575 ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::StorageBegin() {
 576   return IsUsingVector() ? &(vector_->front()) : preallocated_;
 577 }
 578
 579
 580 template<TEMPLATE_INVALSET_P_DECL>
 581 ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::StorageEnd() {
 582   return IsUsingVector() ? &(vector_->back()) + 1 : preallocated_ + size_;
 583 }
 584
 585
 586 template<TEMPLATE_INVALSET_P_DECL>
 587 size_t InvalSet<TEMPLATE_INVALSET_P_DEF>::ElementIndex(
 588     const ElementType* element) const {
 589   VIXL_ASSERT((StorageBegin() <= element) && (element < StorageEnd()));
 590   return element - StorageBegin();
 591 }
 592
 593
 594 template<TEMPLATE_INVALSET_P_DECL>
 595 const ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::ElementAt(
 596     size_t index) const {
 597   VIXL_ASSERT(
 598       (IsUsingVector() && (index < vector_->size())) || (index < size_));
 599   return StorageBegin() + index;
 600 }
 601
 602 template<TEMPLATE_INVALSET_P_DECL>
 603 ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::ElementAt(size_t index) {
 604   VIXL_ASSERT(
 605       (IsUsingVector() && (index < vector_->size())) || (index < size_));
 606   return StorageBegin() + index;
 607 }
 608
 609 template<TEMPLATE_INVALSET_P_DECL>
 610 const ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::FirstValidElement(
 611     const ElementType* from, const ElementType* end) {
 612   while ((from < end) && !IsValid(*from)) {
 613     from++;
 614   }
 615   return from;
 616 }
 617
 618
 619 template<TEMPLATE_INVALSET_P_DECL>
 620 void InvalSet<TEMPLATE_INVALSET_P_DEF>::CacheMinElement() {
 621   VIXL_ASSERT(monitor() == 0);
 622   VIXL_ASSERT(!empty());
 623
 624   if (valid_cached_min_) {
 625     return;
 626   }
 627
 628   if (sorted_) {
 629     const ElementType* min = FirstValidElement(StorageBegin(), StorageEnd());
 630     cached_min_index_ = ElementIndex(min);
 631     cached_min_key_ = Key(*min);
 632     valid_cached_min_ = true;
 633   } else {
 634     Sort(kHardSort);
 635   }
 636   VIXL_ASSERT(valid_cached_min_);
 637 }
 638
 639
 640 template<TEMPLATE_INVALSET_P_DECL>
 641 bool InvalSet<TEMPLATE_INVALSET_P_DEF>::ShouldReclaimMemory() const {
 642   if (!IsUsingVector()) {
 643     return false;
 644   }
 645   size_t n_invalid_elements = vector_->size() - size_;
 646   return (n_invalid_elements > RECLAIM_FROM) &&
 647          (n_invalid_elements > vector_->size() / RECLAIM_FACTOR);
 648 }
 649
 650
 651 template<TEMPLATE_INVALSET_P_DECL>
 652 void InvalSet<TEMPLATE_INVALSET_P_DEF>::ReclaimMemory() {
 653   VIXL_ASSERT(monitor() == 0);
 654   Clean();
 655 }
 656
 657
 658 template<class S>
 659 InvalSetIterator<S>::InvalSetIterator(S* inval_set)
 660     : using_vector_((inval_set != NULL) && inval_set->IsUsingVector()),
 661       index_(0),
 662       inval_set_(inval_set) {
 663   if (inval_set != NULL) {
 664     inval_set->Sort(S::kSoftSort);
 665 #ifdef VIXL_DEBUG
 666     inval_set->Acquire();
 667 #endif
 668     if (using_vector_) {
 669       iterator_ = typename std::vector<ElementType>::iterator(
 670           inval_set_->vector_->begin());
 671     }
 672     MoveToValidElement();
 673   }
 674 }
 675
 676
 677 template<class S>
 678 InvalSetIterator<S>::~InvalSetIterator() {
 679 #ifdef VIXL_DEBUG
 680   if (inval_set_ != NULL) {
 681     inval_set_->Release();
 682   }
 683 #endif
 684 }
 685
 686
 687 template<class S>
 688 typename S::_ElementType* InvalSetIterator<S>::Current() const {
 689   VIXL_ASSERT(!Done());
 690   if (using_vector_) {
 691     return &(*iterator_);
 692   } else {
 693     return &(inval_set_->preallocated_[index_]);
 694   }
 695 }
 696
 697
 698 template<class S>
 699 void InvalSetIterator<S>::Advance() {
 700   VIXL_ASSERT(!Done());
 701   if (using_vector_) {
 702     iterator_++;
 703 #ifdef VIXL_DEBUG
 704     index_++;
 705 #endif
 706     MoveToValidElement();
 707   } else {
 708     index_++;
 709   }
 710 }
 711
 712
 713 template<class S>
 714 bool InvalSetIterator<S>::Done() const {
 715   if (using_vector_) {
 716     bool done = (iterator_ == inval_set_->vector_->end());
 717     VIXL_ASSERT(done == (index_ == inval_set_->size()));
 718     return done;
 719   } else {
 720     return index_ == inval_set_->size();
 721   }
 722 }
 723
 724
 725 template<class S>
 726 void InvalSetIterator<S>::Finish() {
 727   VIXL_ASSERT(inval_set_->sorted_);
 728   if (using_vector_) {
 729     iterator_ = inval_set_->vector_->end();
 730   }
 731   index_ = inval_set_->size();
 732 }
 733
 734
 735 template<class S>
 736 void InvalSetIterator<S>::DeleteCurrentAndAdvance() {
 737   if (using_vector_) {
 738     inval_set_->EraseInternal(&(*iterator_));
 739     MoveToValidElement();
 740   } else {
 741     inval_set_->EraseInternal(inval_set_->preallocated_ + index_);
 742   }
 743 }
 744
 745
 746 template<class S>
 747 bool InvalSetIterator<S>::IsValid(const ElementType& element) {
 748   return S::IsValid(element);
 749 }
 750
 751
 752 template<class S>
 753 typename S::_KeyType InvalSetIterator<S>::Key(const ElementType& element) {
 754   return S::Key(element);
 755 }
 756
 757
 758 template<class S>
 759 void InvalSetIterator<S>::MoveToValidElement() {
 760   if (using_vector_) {
 761     while ((iterator_ != inval_set_->vector_->end()) && !IsValid(*iterator_)) {
 762       iterator_++;
 763     }
 764   } else {
 765     VIXL_ASSERT(inval_set_->empty() || IsValid(inval_set_->preallocated_[0]));
 766     // Nothing to do.
 767   }
 768 }
 769
 770 #undef TEMPLATE_INVALSET_P_DECL
 771 #undef TEMPLATE_INVALSET_P_DEF
 772
 773 }  // namespace vixl
 774
 775 #endif  // VIXL_INVALSET_H_