cachepc-qemu

invalset.h (23114B)

// Copyright 2015, ARM Limited
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//
//   * Redistributions of source code must retain the above copyright notice,
//     this list of conditions and the following disclaimer.
//   * Redistributions in binary form must reproduce the above copyright notice,
//     this list of conditions and the following disclaimer in the documentation
//     and/or other materials provided with the distribution.
//   * Neither the name of ARM Limited nor the names of its contributors may be
//     used to endorse or promote products derived from this software without
//     specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS CONTRIBUTORS "AS IS" AND
// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
// WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
// FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
// SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
// CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
// OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

#ifndef VIXL_INVALSET_H_
#define VIXL_INVALSET_H_

#include <cstring>

#include <algorithm>
#include <vector>

#include "vixl/globals.h"

namespace vixl {

// We define a custom data structure template and its iterator as `std`
// containers do not fit the performance requirements for some of our use cases.
//
// The structure behaves like an iterable unordered set with special properties
// and restrictions. "InvalSet" stands for "Invalidatable Set".
//
// Restrictions and requirements:
// - Adding an element already present in the set is illegal. In debug mode,
//   this is checked at insertion time.
// - The templated class `ElementType` must provide comparison operators so that
//   `std::sort()` can be used.
// - A key must be available to represent invalid elements.
// - Elements with an invalid key must compare higher or equal to any other
//   element.
//
// Use cases and performance considerations:
// Our use cases present two specificities that allow us to design this
// structure to provide fast insertion *and* fast search and deletion
// operations:
// - Elements are (generally) inserted in order (sorted according to their key).
// - A key is available to mark elements as invalid (deleted).
// The backing `std::vector` allows for fast insertions. When
// searching for an element we ensure the elements are sorted (this is generally
// the case) and perform a binary search. When deleting an element we do not
// free the associated memory immediately. Instead, an element to be deleted is
// marked with the 'invalid' key. Other methods of the container take care of
// ignoring entries marked as invalid.
// To avoid the overhead of the `std::vector` container when only few entries
// are used, a number of elements are preallocated.

// 'ElementType' and 'KeyType' are respectively the types of the elements and
// their key.  The structure only reclaims memory when safe to do so, if the
// number of elements that can be reclaimed is greater than `RECLAIM_FROM` and
// greater than `<total number of elements> / RECLAIM_FACTOR.
#define TEMPLATE_INVALSET_P_DECL                                               \
  class ElementType,                                                           \
  unsigned N_PREALLOCATED_ELEMENTS,                                            \
  class KeyType,                                                               \
  KeyType INVALID_KEY,                                                         \
  size_t RECLAIM_FROM,                                                         \
  unsigned RECLAIM_FACTOR

#define TEMPLATE_INVALSET_P_DEF                                                \
ElementType, N_PREALLOCATED_ELEMENTS,                                          \
KeyType, INVALID_KEY, RECLAIM_FROM, RECLAIM_FACTOR

template<class S> class InvalSetIterator;  // Forward declaration.

template<TEMPLATE_INVALSET_P_DECL> class InvalSet {
 public:
  InvalSet();
  ~InvalSet();

  static const size_t kNPreallocatedElements = N_PREALLOCATED_ELEMENTS;
  static const KeyType kInvalidKey = INVALID_KEY;

  // It is illegal to insert an element already present in the set.
  void insert(const ElementType& element);

  // Looks for the specified element in the set and - if found - deletes it.
  void erase(const ElementType& element);

  // This indicates the number of (valid) elements stored in this set.
  size_t size() const;

  // Returns true if no elements are stored in the set.
  // Note that this does not mean the the backing storage is empty: it can still
  // contain invalid elements.
  bool empty() const;

  void clear();

  const ElementType min_element();

  // This returns the key of the minimum element in the set.
  KeyType min_element_key();

  static bool IsValid(const ElementType& element);
  static KeyType Key(const ElementType& element);
  static void SetKey(ElementType* element, KeyType key);

 protected:
  // Returns a pointer to the element in vector_ if it was found, or NULL
  // otherwise.
  ElementType* Search(const ElementType& element);

  // The argument *must* point to an element stored in *this* set.
  // This function is not allowed to move elements in the backing vector
  // storage.
  void EraseInternal(ElementType* element);

  // The elements in the range searched must be sorted.
  ElementType* BinarySearch(const ElementType& element,
                            ElementType* start,
                            ElementType* end) const;

  // Sort the elements.
  enum SortType {
    // The 'hard' version guarantees that invalid elements are moved to the end
    // of the container.
    kHardSort,
    // The 'soft' version only guarantees that the elements will be sorted.
    // Invalid elements may still be present anywhere in the set.
    kSoftSort
  };
  void Sort(SortType sort_type);

  // Delete the elements that have an invalid key. The complexity is linear
  // with the size of the vector.
  void Clean();

  const ElementType Front() const;
  const ElementType Back() const;

  // Delete invalid trailing elements and return the last valid element in the
  // set.
  const ElementType CleanBack();

  // Returns a pointer to the start or end of the backing storage.
  const ElementType* StorageBegin() const;
  const ElementType* StorageEnd() const;
  ElementType* StorageBegin();
  ElementType* StorageEnd();

  // Returns the index of the element within the backing storage. The element
  // must belong to the backing storage.
  size_t ElementIndex(const ElementType* element) const;

  // Returns the element at the specified index in the backing storage.
  const ElementType* ElementAt(size_t index) const;
  ElementType* ElementAt(size_t index);

  static const ElementType* FirstValidElement(const ElementType* from,
                                              const ElementType* end);

  void CacheMinElement();
  const ElementType CachedMinElement() const;

  bool ShouldReclaimMemory() const;
  void ReclaimMemory();

  bool IsUsingVector() const { return vector_ != NULL; }
  void set_sorted(bool sorted) { sorted_ = sorted; }

  // We cache some data commonly required by users to improve performance.
  // We cannot cache pointers to elements as we do not control the backing
  // storage.
  bool valid_cached_min_;
  size_t cached_min_index_;  // Valid iff `valid_cached_min_` is true.
  KeyType cached_min_key_;         // Valid iff `valid_cached_min_` is true.

  // Indicates whether the elements are sorted.
  bool sorted_;

  // This represents the number of (valid) elements in this set.
  size_t size_;

  // The backing storage is either the array of preallocated elements or the
  // vector. The structure starts by using the preallocated elements, and
  // transitions (permanently) to using the vector once more than
  // kNPreallocatedElements are used.
  // Elements are only invalidated when using the vector. The preallocated
  // storage always only contains valid elements.
  ElementType preallocated_[kNPreallocatedElements];
  std::vector<ElementType>* vector_;

#ifdef VIXL_DEBUG
  // Iterators acquire and release this monitor. While a set is acquired,
  // certain operations are illegal to ensure that the iterator will
  // correctly iterate over the elements in the set.
  int monitor_;
  int monitor() const { return monitor_; }
  void Acquire() { monitor_++; }
  void Release() {
    monitor_--;
    VIXL_ASSERT(monitor_ >= 0);
  }
#endif

  friend class InvalSetIterator<InvalSet<TEMPLATE_INVALSET_P_DEF> >;
  typedef ElementType _ElementType;
  typedef KeyType _KeyType;
};


template<class S> class InvalSetIterator {
 private:
  // Redefine types to mirror the associated set types.
  typedef typename S::_ElementType ElementType;
  typedef typename S::_KeyType KeyType;

 public:
  explicit InvalSetIterator(S* inval_set);
  ~InvalSetIterator();

  ElementType* Current() const;
  void Advance();
  bool Done() const;

  // Mark this iterator as 'done'.
  void Finish();

  // Delete the current element and advance the iterator to point to the next
  // element.
  void DeleteCurrentAndAdvance();

  static bool IsValid(const ElementType& element);
  static KeyType Key(const ElementType& element);

 protected:
  void MoveToValidElement();

  // Indicates if the iterator is looking at the vector or at the preallocated
  // elements.
  const bool using_vector_;
  // Used when looking at the preallocated elements, or in debug mode when using
  // the vector to track how many times the iterator has advanced.
  size_t index_;
  typename std::vector<ElementType>::iterator iterator_;
  S* inval_set_;
};


template<TEMPLATE_INVALSET_P_DECL>
InvalSet<TEMPLATE_INVALSET_P_DEF>::InvalSet()
  : valid_cached_min_(false),
    sorted_(true), size_(0), vector_(NULL) {
#ifdef VIXL_DEBUG
  monitor_ = 0;
#endif
}


template<TEMPLATE_INVALSET_P_DECL>
InvalSet<TEMPLATE_INVALSET_P_DEF>::~InvalSet() {
  VIXL_ASSERT(monitor_ == 0);
  delete vector_;
}


template<TEMPLATE_INVALSET_P_DECL>
void InvalSet<TEMPLATE_INVALSET_P_DEF>::insert(const ElementType& element) {
  VIXL_ASSERT(monitor() == 0);
  VIXL_ASSERT(IsValid(element));
  VIXL_ASSERT(Search(element) == NULL);
  set_sorted(empty() || (sorted_ && (element > CleanBack())));
  if (IsUsingVector()) {
    vector_->push_back(element);
  } else {
    if (size_ < kNPreallocatedElements) {
      preallocated_[size_] = element;
    } else {
      // Transition to using the vector.
      vector_ = new std::vector<ElementType>(preallocated_,
                                             preallocated_ + size_);
      vector_->push_back(element);
    }
  }
  size_++;

  if (valid_cached_min_ && (element < min_element())) {
    cached_min_index_ = IsUsingVector() ? vector_->size() - 1 : size_ - 1;
    cached_min_key_ = Key(element);
    valid_cached_min_ = true;
  }

  if (ShouldReclaimMemory()) {
    ReclaimMemory();
  }
}


template<TEMPLATE_INVALSET_P_DECL>
void InvalSet<TEMPLATE_INVALSET_P_DEF>::erase(const ElementType& element) {
  VIXL_ASSERT(monitor() == 0);
  VIXL_ASSERT(IsValid(element));
  ElementType* local_element = Search(element);
  if (local_element != NULL) {
    EraseInternal(local_element);
  }
}


template<TEMPLATE_INVALSET_P_DECL>
ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::Search(
    const ElementType& element) {
  VIXL_ASSERT(monitor() == 0);
  if (empty()) {
    return NULL;
  }
  if (ShouldReclaimMemory()) {
    ReclaimMemory();
  }
  if (!sorted_) {
    Sort(kHardSort);
  }
  if (!valid_cached_min_) {
    CacheMinElement();
  }
  return BinarySearch(element, ElementAt(cached_min_index_), StorageEnd());
}


template<TEMPLATE_INVALSET_P_DECL>
size_t InvalSet<TEMPLATE_INVALSET_P_DEF>::size() const {
  return size_;
}


template<TEMPLATE_INVALSET_P_DECL>
bool InvalSet<TEMPLATE_INVALSET_P_DEF>::empty() const {
  return size_ == 0;
}


template<TEMPLATE_INVALSET_P_DECL>
void InvalSet<TEMPLATE_INVALSET_P_DEF>::clear() {
  VIXL_ASSERT(monitor() == 0);
  size_ = 0;
  if (IsUsingVector()) {
    vector_->clear();
  }
  set_sorted(true);
  valid_cached_min_ = false;
}


template<TEMPLATE_INVALSET_P_DECL>
const ElementType InvalSet<TEMPLATE_INVALSET_P_DEF>::min_element() {
  VIXL_ASSERT(monitor() == 0);
  VIXL_ASSERT(!empty());
  CacheMinElement();
  return *ElementAt(cached_min_index_);
}


template<TEMPLATE_INVALSET_P_DECL>
KeyType InvalSet<TEMPLATE_INVALSET_P_DEF>::min_element_key() {
  VIXL_ASSERT(monitor() == 0);
  if (valid_cached_min_) {
    return cached_min_key_;
  } else {
    return Key(min_element());
  }
}


template<TEMPLATE_INVALSET_P_DECL>
bool InvalSet<TEMPLATE_INVALSET_P_DEF>::IsValid(const ElementType& element) {
  return Key(element) != kInvalidKey;
}


template<TEMPLATE_INVALSET_P_DECL>
void InvalSet<TEMPLATE_INVALSET_P_DEF>::EraseInternal(ElementType* element) {
  // Note that this function must be safe even while an iterator has acquired
  // this set.
  VIXL_ASSERT(element != NULL);
  size_t deleted_index = ElementIndex(element);
  if (IsUsingVector()) {
    VIXL_ASSERT((&(vector_->front()) <= element) &&
                (element <= &(vector_->back())));
    SetKey(element, kInvalidKey);
  } else {
    VIXL_ASSERT((preallocated_ <= element) &&
                (element < (preallocated_ + kNPreallocatedElements)));
    ElementType* end = preallocated_ + kNPreallocatedElements;
    size_t copy_size = sizeof(*element) * (end - element - 1);
    memmove(element, element + 1, copy_size);
  }
  size_--;

  if (valid_cached_min_ &&
      (deleted_index == cached_min_index_)) {
    if (sorted_ && !empty()) {
      const ElementType* min = FirstValidElement(element, StorageEnd());
      cached_min_index_ = ElementIndex(min);
      cached_min_key_ = Key(*min);
      valid_cached_min_ = true;
    } else {
      valid_cached_min_ = false;
    }
  }
}


template<TEMPLATE_INVALSET_P_DECL>
ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::BinarySearch(
    const ElementType& element, ElementType* start, ElementType* end) const {
  if (start == end) {
    return NULL;
  }
  VIXL_ASSERT(sorted_);
  VIXL_ASSERT(start < end);
  VIXL_ASSERT(!empty());

  // Perform a binary search through the elements while ignoring invalid
  // elements.
  ElementType* elements = start;
  size_t low = 0;
  size_t high = (end - start) - 1;
  while (low < high) {
    // Find valid bounds.
    while (!IsValid(elements[low]) && (low < high)) ++low;
    while (!IsValid(elements[high]) && (low < high)) --high;
    VIXL_ASSERT(low <= high);
    // Avoid overflow when computing the middle index.
    size_t middle = low / 2 + high / 2 + (low & high & 1);
    if ((middle == low) || (middle == high)) {
      break;
    }
    while (!IsValid(elements[middle]) && (middle < high - 1)) ++middle;
    while (!IsValid(elements[middle]) && (low + 1 < middle)) --middle;
    if (!IsValid(elements[middle])) {
      break;
    }
    if (elements[middle] < element) {
      low = middle;
    } else {
      high = middle;
    }
  }

  if (elements[low] == element) return &elements[low];
  if (elements[high] == element) return &elements[high];
  return NULL;
}


template<TEMPLATE_INVALSET_P_DECL>
void InvalSet<TEMPLATE_INVALSET_P_DEF>::Sort(SortType sort_type) {
  VIXL_ASSERT(monitor() == 0);
  if (sort_type == kSoftSort) {
    if (sorted_) {
      return;
    }
  }
  if (empty()) {
    return;
  }

  Clean();
  std::sort(StorageBegin(), StorageEnd());

  set_sorted(true);
  cached_min_index_ = 0;
  cached_min_key_ = Key(Front());
  valid_cached_min_ = true;
}


template<TEMPLATE_INVALSET_P_DECL>
void InvalSet<TEMPLATE_INVALSET_P_DEF>::Clean() {
  VIXL_ASSERT(monitor() == 0);
  if (empty() || !IsUsingVector()) {
    return;
  }
  // Manually iterate through the vector storage to discard invalid elements.
  ElementType* start = &(vector_->front());
  ElementType* end = start + vector_->size();
  ElementType* c = start;
  ElementType* first_invalid;
  ElementType* first_valid;
  ElementType* next_invalid;

  while (c < end && IsValid(*c)) { c++; }
  first_invalid = c;

  while (c < end) {
    while (c < end && !IsValid(*c)) { c++; }
    first_valid = c;
    while (c < end && IsValid(*c)) { c++; }
    next_invalid = c;

    ptrdiff_t n_moved_elements = (next_invalid - first_valid);
    memmove(first_invalid, first_valid,  n_moved_elements * sizeof(*c));
    first_invalid = first_invalid + n_moved_elements;
    c = next_invalid;
  }

  // Delete the trailing invalid elements.
  vector_->erase(vector_->begin() + (first_invalid - start), vector_->end());
  VIXL_ASSERT(vector_->size() == size_);

  if (sorted_) {
    valid_cached_min_ = true;
    cached_min_index_ = 0;
    cached_min_key_ = Key(*ElementAt(0));
  } else {
    valid_cached_min_ = false;
  }
}


template<TEMPLATE_INVALSET_P_DECL>
const ElementType InvalSet<TEMPLATE_INVALSET_P_DEF>::Front() const {
  VIXL_ASSERT(!empty());
  return IsUsingVector() ? vector_->front() : preallocated_[0];
}


template<TEMPLATE_INVALSET_P_DECL>
const ElementType InvalSet<TEMPLATE_INVALSET_P_DEF>::Back() const {
  VIXL_ASSERT(!empty());
  return IsUsingVector() ? vector_->back() : preallocated_[size_ - 1];
}


template<TEMPLATE_INVALSET_P_DECL>
const ElementType InvalSet<TEMPLATE_INVALSET_P_DEF>::CleanBack() {
  VIXL_ASSERT(monitor() == 0);
  if (IsUsingVector()) {
    // Delete the invalid trailing elements.
    typename std::vector<ElementType>::reverse_iterator it = vector_->rbegin();
    while (!IsValid(*it)) {
      it++;
    }
    vector_->erase(it.base(), vector_->end());
  }
  return Back();
}


template<TEMPLATE_INVALSET_P_DECL>
const ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::StorageBegin() const {
  return IsUsingVector() ? &(vector_->front()) : preallocated_;
}


template<TEMPLATE_INVALSET_P_DECL>
const ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::StorageEnd() const {
  return IsUsingVector() ? &(vector_->back()) + 1 : preallocated_ + size_;
}


template<TEMPLATE_INVALSET_P_DECL>
ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::StorageBegin() {
  return IsUsingVector() ? &(vector_->front()) : preallocated_;
}


template<TEMPLATE_INVALSET_P_DECL>
ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::StorageEnd() {
  return IsUsingVector() ? &(vector_->back()) + 1 : preallocated_ + size_;
}


template<TEMPLATE_INVALSET_P_DECL>
size_t InvalSet<TEMPLATE_INVALSET_P_DEF>::ElementIndex(
    const ElementType* element) const {
  VIXL_ASSERT((StorageBegin() <= element) && (element < StorageEnd()));
  return element - StorageBegin();
}


template<TEMPLATE_INVALSET_P_DECL>
const ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::ElementAt(
    size_t index) const {
  VIXL_ASSERT(
      (IsUsingVector() && (index < vector_->size())) || (index < size_));
  return StorageBegin() + index;
}

template<TEMPLATE_INVALSET_P_DECL>
ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::ElementAt(size_t index) {
  VIXL_ASSERT(
      (IsUsingVector() && (index < vector_->size())) || (index < size_));
  return StorageBegin() + index;
}

template<TEMPLATE_INVALSET_P_DECL>
const ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::FirstValidElement(
    const ElementType* from, const ElementType* end) {
  while ((from < end) && !IsValid(*from)) {
    from++;
  }
  return from;
}


template<TEMPLATE_INVALSET_P_DECL>
void InvalSet<TEMPLATE_INVALSET_P_DEF>::CacheMinElement() {
  VIXL_ASSERT(monitor() == 0);
  VIXL_ASSERT(!empty());

  if (valid_cached_min_) {
    return;
  }

  if (sorted_) {
    const ElementType* min = FirstValidElement(StorageBegin(), StorageEnd());
    cached_min_index_ = ElementIndex(min);
    cached_min_key_ = Key(*min);
    valid_cached_min_ = true;
  } else {
    Sort(kHardSort);
  }
  VIXL_ASSERT(valid_cached_min_);
}


template<TEMPLATE_INVALSET_P_DECL>
bool InvalSet<TEMPLATE_INVALSET_P_DEF>::ShouldReclaimMemory() const {
  if (!IsUsingVector()) {
    return false;
  }
  size_t n_invalid_elements = vector_->size() - size_;
  return (n_invalid_elements > RECLAIM_FROM) &&
         (n_invalid_elements > vector_->size() / RECLAIM_FACTOR);
}


template<TEMPLATE_INVALSET_P_DECL>
void InvalSet<TEMPLATE_INVALSET_P_DEF>::ReclaimMemory() {
  VIXL_ASSERT(monitor() == 0);
  Clean();
}


template<class S>
InvalSetIterator<S>::InvalSetIterator(S* inval_set)
    : using_vector_((inval_set != NULL) && inval_set->IsUsingVector()),
      index_(0),
      inval_set_(inval_set) {
  if (inval_set != NULL) {
    inval_set->Sort(S::kSoftSort);
#ifdef VIXL_DEBUG
    inval_set->Acquire();
#endif
    if (using_vector_) {
      iterator_ = typename std::vector<ElementType>::iterator(
          inval_set_->vector_->begin());
    }
    MoveToValidElement();
  }
}


template<class S>
InvalSetIterator<S>::~InvalSetIterator() {
#ifdef VIXL_DEBUG
  if (inval_set_ != NULL) {
    inval_set_->Release();
  }
#endif
}


template<class S>
typename S::_ElementType* InvalSetIterator<S>::Current() const {
  VIXL_ASSERT(!Done());
  if (using_vector_) {
    return &(*iterator_);
  } else {
    return &(inval_set_->preallocated_[index_]);
  }
}


template<class S>
void InvalSetIterator<S>::Advance() {
  VIXL_ASSERT(!Done());
  if (using_vector_) {
    iterator_++;
#ifdef VIXL_DEBUG
    index_++;
#endif
    MoveToValidElement();
  } else {
    index_++;
  }
}


template<class S>
bool InvalSetIterator<S>::Done() const {
  if (using_vector_) {
    bool done = (iterator_ == inval_set_->vector_->end());
    VIXL_ASSERT(done == (index_ == inval_set_->size()));
    return done;
  } else {
    return index_ == inval_set_->size();
  }
}


template<class S>
void InvalSetIterator<S>::Finish() {
  VIXL_ASSERT(inval_set_->sorted_);
  if (using_vector_) {
    iterator_ = inval_set_->vector_->end();
  }
  index_ = inval_set_->size();
}


template<class S>
void InvalSetIterator<S>::DeleteCurrentAndAdvance() {
  if (using_vector_) {
    inval_set_->EraseInternal(&(*iterator_));
    MoveToValidElement();
  } else {
    inval_set_->EraseInternal(inval_set_->preallocated_ + index_);
  }
}


template<class S>
bool InvalSetIterator<S>::IsValid(const ElementType& element) {
  return S::IsValid(element);
}


template<class S>
typename S::_KeyType InvalSetIterator<S>::Key(const ElementType& element) {
  return S::Key(element);
}


template<class S>
void InvalSetIterator<S>::MoveToValidElement() {
  if (using_vector_) {
    while ((iterator_ != inval_set_->vector_->end()) && !IsValid(*iterator_)) {
      iterator_++;
    }
  } else {
    VIXL_ASSERT(inval_set_->empty() || IsValid(inval_set_->preallocated_[0]));
    // Nothing to do.
  }
}

#undef TEMPLATE_INVALSET_P_DECL
#undef TEMPLATE_INVALSET_P_DEF

}  // namespace vixl

#endif  // VIXL_INVALSET_H_