diff options
author | RajithaY <rajithax.yerrumsetty@intel.com> | 2017-04-25 03:31:15 -0700 |
---|---|---|
committer | Rajitha Yerrumchetty <rajithax.yerrumsetty@intel.com> | 2017-05-22 06:48:08 +0000 |
commit | bb756eebdac6fd24e8919e2c43f7d2c8c4091f59 (patch) | |
tree | ca11e03542edf2d8f631efeca5e1626d211107e3 /qemu/disas/libvixl/vixl/invalset.h | |
parent | a14b48d18a9ed03ec191cf16b162206998a895ce (diff) |
Adding qemu as a submodule of KVMFORNFV
This Patch includes the changes to add qemu as a submodule to
kvmfornfv repo and make use of the updated latest qemu for the
execution of all testcase
Change-Id: I1280af507a857675c7f81d30c95255635667bdd7
Signed-off-by:RajithaY<rajithax.yerrumsetty@intel.com>
Diffstat (limited to 'qemu/disas/libvixl/vixl/invalset.h')
-rw-r--r-- | qemu/disas/libvixl/vixl/invalset.h | 775 |
1 files changed, 0 insertions, 775 deletions
diff --git a/qemu/disas/libvixl/vixl/invalset.h b/qemu/disas/libvixl/vixl/invalset.h deleted file mode 100644 index ffdc0237b..000000000 --- a/qemu/disas/libvixl/vixl/invalset.h +++ /dev/null @@ -1,775 +0,0 @@ -// 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_ |