X-Git-Url: https://gerrit.opnfv.org/gerrit/gitweb?a=blobdiff_plain;f=qemu%2Fdisas%2Flibvixl%2Fvixl%2Finvalset.h;fp=qemu%2Fdisas%2Flibvixl%2Fvixl%2Finvalset.h;h=ffdc0237b47ca7d915858ecd0408b1f5d9e85d50;hb=437fd90c0250dee670290f9b714253671a990160;hp=0000000000000000000000000000000000000000;hpb=5bbd6fe9b8bab2a93e548c5a53b032d1939eec05;p=kvmfornfv.git

diff --git a/qemu/disas/libvixl/vixl/invalset.h b/qemu/disas/libvixl/vixl/invalset.h
new file mode 100644
index 000000000..ffdc0237b
--- /dev/null
+++ b/qemu/disas/libvixl/vixl/invalset.h
@@ -0,0 +1,775 @@
+// 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 <string.h>
+
+#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_