| // 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_ |