• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 // Copyright 2015, VIXL authors
2 // All rights reserved.
3 //
4 // Redistribution and use in source and binary forms, with or without
5 // modification, are permitted provided that the following conditions are met:
6 //
7 //   * Redistributions of source code must retain the above copyright notice,
8 //     this list of conditions and the following disclaimer.
9 //   * Redistributions in binary form must reproduce the above copyright notice,
10 //     this list of conditions and the following disclaimer in the documentation
11 //     and/or other materials provided with the distribution.
12 //   * Neither the name of ARM Limited nor the names of its contributors may be
13 //     used to endorse or promote products derived from this software without
14 //     specific prior written permission.
15 //
16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS CONTRIBUTORS "AS IS" AND
17 // ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
18 // WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
19 // DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
20 // FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
21 // DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
22 // SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
23 // CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
24 // OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
25 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 
27 #ifndef VIXL_INVALSET_H_
28 #define VIXL_INVALSET_H_
29 
30 #include <cstring>
31 
32 #include <algorithm>
33 #include <vector>
34 
35 #include "globals-vixl.h"
36 
37 namespace vixl {
38 
39 // We define a custom data structure template and its iterator as `std`
40 // containers do not fit the performance requirements for some of our use cases.
41 //
42 // The structure behaves like an iterable unordered set with special properties
43 // and restrictions. "InvalSet" stands for "Invalidatable Set".
44 //
45 // Restrictions and requirements:
46 // - Adding an element already present in the set is illegal. In debug mode,
47 //   this is checked at insertion time.
48 // - The templated class `ElementType` must provide comparison operators so that
49 //   `std::sort()` can be used.
50 // - A key must be available to represent invalid elements.
51 // - Elements with an invalid key must compare higher or equal to any other
52 //   element.
53 //
54 // Use cases and performance considerations:
55 // Our use cases present two specificities that allow us to design this
56 // structure to provide fast insertion *and* fast search and deletion
57 // operations:
58 // - Elements are (generally) inserted in order (sorted according to their key).
59 // - A key is available to mark elements as invalid (deleted).
60 // The backing `std::vector` allows for fast insertions. When
61 // searching for an element we ensure the elements are sorted (this is generally
62 // the case) and perform a binary search. When deleting an element we do not
63 // free the associated memory immediately. Instead, an element to be deleted is
64 // marked with the 'invalid' key. Other methods of the container take care of
65 // ignoring entries marked as invalid.
66 // To avoid the overhead of the `std::vector` container when only few entries
67 // are used, a number of elements are preallocated.
68 
69 // 'ElementType' and 'KeyType' are respectively the types of the elements and
70 // their key. The structure only reclaims memory when safe to do so, if the
71 // number of elements that can be reclaimed is greater than `RECLAIM_FROM` and
72 // greater than `<total number of elements> / RECLAIM_FACTOR.
73 // clang-format off
74 #define TEMPLATE_INVALSET_P_DECL                                               \
75   class ElementType,                                                           \
76   unsigned N_PREALLOCATED_ELEMENTS,                                            \
77   class KeyType,                                                               \
78   KeyType INVALID_KEY,                                                         \
79   size_t RECLAIM_FROM,                                                         \
80   unsigned RECLAIM_FACTOR
81 // clang-format on
82 
83 #define TEMPLATE_INVALSET_P_DEF                                             \
84   ElementType, N_PREALLOCATED_ELEMENTS, KeyType, INVALID_KEY, RECLAIM_FROM, \
85       RECLAIM_FACTOR
86 
87 template <class S>
88 class InvalSetIterator;  // Forward declaration.
89 
90 template <TEMPLATE_INVALSET_P_DECL>
91 class InvalSet {
92  public:
93   InvalSet();
94   ~InvalSet() VIXL_NEGATIVE_TESTING_ALLOW_EXCEPTION;
95 
96   static const size_t kNPreallocatedElements = N_PREALLOCATED_ELEMENTS;
97   static const KeyType kInvalidKey = INVALID_KEY;
98 
99   // C++ STL iterator interface.
100   typedef InvalSetIterator<InvalSet<TEMPLATE_INVALSET_P_DEF> > iterator;
101   iterator begin();
102   iterator end();
103 
104   // It is illegal to insert an element already present in the set.
105   void insert(const ElementType& element);
106 
107   // Looks for the specified element in the set and - if found - deletes it.
108   // The return value is the number of elements erased: either 0 or 1.
109   size_t erase(const ElementType& element);
110 
111   // This indicates the number of (valid) elements stored in this set.
112   size_t size() const;
113 
114   // Returns true if no elements are stored in the set.
115   // Note that this does not mean the the backing storage is empty: it can still
116   // contain invalid elements.
117   bool empty() const;
118 
119   void clear();
120 
121   const ElementType GetMinElement();
122 
123   // This returns the key of the minimum element in the set.
124   KeyType GetMinElementKey();
125 
126   static bool IsValid(const ElementType& element);
127   static KeyType GetKey(const ElementType& element);
128   static void SetKey(ElementType* element, KeyType key);
129 
130   typedef ElementType _ElementType;
131   typedef KeyType _KeyType;
132 
133  protected:
134   // Returns a pointer to the element in vector_ if it was found, or NULL
135   // otherwise.
136   ElementType* Search(const ElementType& element);
137 
138   // The argument *must* point to an element stored in *this* set.
139   // This function is not allowed to move elements in the backing vector
140   // storage.
141   void EraseInternal(ElementType* element);
142 
143   // The elements in the range searched must be sorted.
144   ElementType* BinarySearch(const ElementType& element,
145                             ElementType* start,
146                             ElementType* end) const;
147 
148   // Sort the elements.
149   enum SortType {
150     // The 'hard' version guarantees that invalid elements are moved to the end
151     // of the container.
152     kHardSort,
153     // The 'soft' version only guarantees that the elements will be sorted.
154     // Invalid elements may still be present anywhere in the set.
155     kSoftSort
156   };
157   void Sort(SortType sort_type);
158 
159   // Delete the elements that have an invalid key. The complexity is linear
160   // with the size of the vector.
161   void Clean();
162 
163   const ElementType Front() const;
164   const ElementType Back() const;
165 
166   // Delete invalid trailing elements and return the last valid element in the
167   // set.
168   const ElementType CleanBack();
169 
170   // Returns a pointer to the start or end of the backing storage.
171   const ElementType* StorageBegin() const;
172   const ElementType* StorageEnd() const;
173   ElementType* StorageBegin();
174   ElementType* StorageEnd();
175 
176   // Returns the index of the element within the backing storage. The element
177   // must belong to the backing storage.
178   size_t GetElementIndex(const ElementType* element) const;
179 
180   // Returns the element at the specified index in the backing storage.
181   const ElementType* GetElementAt(size_t index) const;
182   ElementType* GetElementAt(size_t index);
183 
184   static const ElementType* GetFirstValidElement(const ElementType* from,
185                                                  const ElementType* end);
186 
187   void CacheMinElement();
188   const ElementType GetCachedMinElement() const;
189 
190   bool ShouldReclaimMemory() const;
191   void ReclaimMemory();
192 
IsUsingVector()193   bool IsUsingVector() const { return vector_ != NULL; }
SetSorted(bool sorted)194   void SetSorted(bool sorted) { sorted_ = sorted; }
195 
196   // We cache some data commonly required by users to improve performance.
197   // We cannot cache pointers to elements as we do not control the backing
198   // storage.
199   bool valid_cached_min_;
200   size_t cached_min_index_;  // Valid iff `valid_cached_min_` is true.
201   KeyType cached_min_key_;   // Valid iff `valid_cached_min_` is true.
202 
203   // Indicates whether the elements are sorted.
204   bool sorted_;
205 
206   // This represents the number of (valid) elements in this set.
207   size_t size_;
208 
209   // The backing storage is either the array of preallocated elements or the
210   // vector. The structure starts by using the preallocated elements, and
211   // transitions (permanently) to using the vector once more than
212   // kNPreallocatedElements are used.
213   // Elements are only invalidated when using the vector. The preallocated
214   // storage always only contains valid elements.
215   ElementType preallocated_[kNPreallocatedElements];
216   std::vector<ElementType>* vector_;
217 
218   // Iterators acquire and release this monitor. While a set is acquired,
219   // certain operations are illegal to ensure that the iterator will
220   // correctly iterate over the elements in the set.
221   int monitor_;
222 #ifdef VIXL_DEBUG
monitor()223   int monitor() const { return monitor_; }
Acquire()224   void Acquire() { monitor_++; }
Release()225   void Release() {
226     monitor_--;
227     VIXL_ASSERT(monitor_ >= 0);
228   }
229 #endif
230 
231  private:
232 // The copy constructor and assignment operator are not used and the defaults
233 // are unsafe, so disable them (without an implementation).
234 #if __cplusplus >= 201103L
235   InvalSet(const InvalSet& other) = delete;
236   InvalSet operator=(const InvalSet& other) = delete;
237 #else
238   InvalSet(const InvalSet& other);
239   InvalSet operator=(const InvalSet& other);
240 #endif
241 
242   friend class InvalSetIterator<InvalSet<TEMPLATE_INVALSET_P_DEF> >;
243 };
244 
245 
246 template <class S>
247 class InvalSetIterator : public std::iterator<std::forward_iterator_tag,
248                                               typename S::_ElementType> {
249  private:
250   // Redefine types to mirror the associated set types.
251   typedef typename S::_ElementType ElementType;
252   typedef typename S::_KeyType KeyType;
253 
254  public:
255   explicit InvalSetIterator(S* inval_set = NULL);
256 
257   // This class implements the standard copy-swap idiom.
258   ~InvalSetIterator();
259   InvalSetIterator(const InvalSetIterator<S>& other);
260   InvalSetIterator<S>& operator=(InvalSetIterator<S> other);
261 #if __cplusplus >= 201103L
262   InvalSetIterator(InvalSetIterator<S>&& other) noexcept;
263 #endif
264 
swap(InvalSetIterator<S> & a,InvalSetIterator<S> & b)265   friend void swap(InvalSetIterator<S>& a, InvalSetIterator<S>& b) {
266     using std::swap;
267     swap(a.using_vector_, b.using_vector_);
268     swap(a.index_, b.index_);
269     swap(a.inval_set_, b.inval_set_);
270   }
271 
272   // Return true if the iterator is at the end of the set.
273   bool Done() const;
274 
275   // Move this iterator to the end of the set.
276   void Finish();
277 
278   // Delete the current element and advance the iterator to point to the next
279   // element.
280   void DeleteCurrentAndAdvance();
281 
282   static bool IsValid(const ElementType& element);
283   static KeyType GetKey(const ElementType& element);
284 
285   // Extra helpers to support the forward-iterator interface.
286   InvalSetIterator<S>& operator++();    // Pre-increment.
287   InvalSetIterator<S> operator++(int);  // Post-increment.
288   bool operator==(const InvalSetIterator<S>& rhs) const;
289   bool operator!=(const InvalSetIterator<S>& rhs) const {
290     return !(*this == rhs);
291   }
292   ElementType& operator*() { return *Current(); }
293   const ElementType& operator*() const { return *Current(); }
294   ElementType* operator->() { return Current(); }
295   const ElementType* operator->() const { return Current(); }
296 
297  protected:
298   void MoveToValidElement();
299 
300   // Indicates if the iterator is looking at the vector or at the preallocated
301   // elements.
302   bool using_vector_;
303   // Used when looking at the preallocated elements, or in debug mode when using
304   // the vector to track how many times the iterator has advanced.
305   size_t index_;
306   typename std::vector<ElementType>::iterator iterator_;
307   S* inval_set_;
308 
309   // TODO: These helpers are deprecated and will be removed in future versions
310   // of VIXL.
311   ElementType* Current() const;
312   void Advance();
313 };
314 
315 
316 template <TEMPLATE_INVALSET_P_DECL>
InvalSet()317 InvalSet<TEMPLATE_INVALSET_P_DEF>::InvalSet()
318     : valid_cached_min_(false), sorted_(true), size_(0), vector_(NULL) {
319 #ifdef VIXL_DEBUG
320   monitor_ = 0;
321 #endif
322 }
323 
324 
325 template <TEMPLATE_INVALSET_P_DECL>
~InvalSet()326 InvalSet<TEMPLATE_INVALSET_P_DEF>::~InvalSet()
327     VIXL_NEGATIVE_TESTING_ALLOW_EXCEPTION {
328   VIXL_ASSERT(monitor_ == 0);
329   delete vector_;
330 }
331 
332 
333 template <TEMPLATE_INVALSET_P_DECL>
334 typename InvalSet<TEMPLATE_INVALSET_P_DEF>::iterator
begin()335 InvalSet<TEMPLATE_INVALSET_P_DEF>::begin() {
336   return iterator(this);
337 }
338 
339 
340 template <TEMPLATE_INVALSET_P_DECL>
341 typename InvalSet<TEMPLATE_INVALSET_P_DEF>::iterator
end()342 InvalSet<TEMPLATE_INVALSET_P_DEF>::end() {
343   iterator end(this);
344   end.Finish();
345   return end;
346 }
347 
348 
349 template <TEMPLATE_INVALSET_P_DECL>
insert(const ElementType & element)350 void InvalSet<TEMPLATE_INVALSET_P_DEF>::insert(const ElementType& element) {
351   VIXL_ASSERT(monitor() == 0);
352   VIXL_ASSERT(IsValid(element));
353   VIXL_ASSERT(Search(element) == NULL);
354   SetSorted(empty() || (sorted_ && (element > CleanBack())));
355   if (IsUsingVector()) {
356     vector_->push_back(element);
357   } else {
358     if (size_ < kNPreallocatedElements) {
359       preallocated_[size_] = element;
360     } else {
361       // Transition to using the vector.
362       vector_ =
363           new std::vector<ElementType>(preallocated_, preallocated_ + size_);
364       vector_->push_back(element);
365     }
366   }
367   size_++;
368 
369   if (valid_cached_min_ && (element < GetMinElement())) {
370     cached_min_index_ = IsUsingVector() ? vector_->size() - 1 : size_ - 1;
371     cached_min_key_ = GetKey(element);
372     valid_cached_min_ = true;
373   }
374 
375   if (ShouldReclaimMemory()) {
376     ReclaimMemory();
377   }
378 }
379 
380 
381 template <TEMPLATE_INVALSET_P_DECL>
erase(const ElementType & element)382 size_t InvalSet<TEMPLATE_INVALSET_P_DEF>::erase(const ElementType& element) {
383   VIXL_ASSERT(monitor() == 0);
384   VIXL_ASSERT(IsValid(element));
385   ElementType* local_element = Search(element);
386   if (local_element != NULL) {
387     EraseInternal(local_element);
388     return 1;
389   }
390   return 0;
391 }
392 
393 
394 template <TEMPLATE_INVALSET_P_DECL>
Search(const ElementType & element)395 ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::Search(
396     const ElementType& element) {
397   VIXL_ASSERT(monitor() == 0);
398   if (empty()) {
399     return NULL;
400   }
401   if (ShouldReclaimMemory()) {
402     ReclaimMemory();
403   }
404   if (!sorted_) {
405     Sort(kHardSort);
406   }
407   if (!valid_cached_min_) {
408     CacheMinElement();
409   }
410   return BinarySearch(element, GetElementAt(cached_min_index_), StorageEnd());
411 }
412 
413 
414 template <TEMPLATE_INVALSET_P_DECL>
size()415 size_t InvalSet<TEMPLATE_INVALSET_P_DEF>::size() const {
416   return size_;
417 }
418 
419 
420 template <TEMPLATE_INVALSET_P_DECL>
empty()421 bool InvalSet<TEMPLATE_INVALSET_P_DEF>::empty() const {
422   return size_ == 0;
423 }
424 
425 
426 template <TEMPLATE_INVALSET_P_DECL>
clear()427 void InvalSet<TEMPLATE_INVALSET_P_DEF>::clear() {
428   VIXL_ASSERT(monitor() == 0);
429   size_ = 0;
430   if (IsUsingVector()) {
431     vector_->clear();
432   }
433   SetSorted(true);
434   valid_cached_min_ = false;
435 }
436 
437 
438 template <TEMPLATE_INVALSET_P_DECL>
GetMinElement()439 const ElementType InvalSet<TEMPLATE_INVALSET_P_DEF>::GetMinElement() {
440   VIXL_ASSERT(monitor() == 0);
441   VIXL_ASSERT(!empty());
442   CacheMinElement();
443   return *GetElementAt(cached_min_index_);
444 }
445 
446 
447 template <TEMPLATE_INVALSET_P_DECL>
GetMinElementKey()448 KeyType InvalSet<TEMPLATE_INVALSET_P_DEF>::GetMinElementKey() {
449   VIXL_ASSERT(monitor() == 0);
450   if (valid_cached_min_) {
451     return cached_min_key_;
452   } else {
453     return GetKey(GetMinElement());
454   }
455 }
456 
457 
458 template <TEMPLATE_INVALSET_P_DECL>
IsValid(const ElementType & element)459 bool InvalSet<TEMPLATE_INVALSET_P_DEF>::IsValid(const ElementType& element) {
460   return GetKey(element) != kInvalidKey;
461 }
462 
463 
464 template <TEMPLATE_INVALSET_P_DECL>
EraseInternal(ElementType * element)465 void InvalSet<TEMPLATE_INVALSET_P_DEF>::EraseInternal(ElementType* element) {
466   // Note that this function must be safe even while an iterator has acquired
467   // this set.
468   VIXL_ASSERT(element != NULL);
469   size_t deleted_index = GetElementIndex(element);
470   if (IsUsingVector()) {
471     VIXL_ASSERT((&(vector_->front()) <= element) &&
472                 (element <= &(vector_->back())));
473     SetKey(element, kInvalidKey);
474   } else {
475     VIXL_ASSERT((preallocated_ <= element) &&
476                 (element < (preallocated_ + kNPreallocatedElements)));
477     ElementType* end = preallocated_ + kNPreallocatedElements;
478     size_t copy_size = sizeof(*element) * (end - element - 1);
479     memmove(element, element + 1, copy_size);
480   }
481   size_--;
482 
483   if (valid_cached_min_ && (deleted_index == cached_min_index_)) {
484     if (sorted_ && !empty()) {
485       const ElementType* min = GetFirstValidElement(element, StorageEnd());
486       cached_min_index_ = GetElementIndex(min);
487       cached_min_key_ = GetKey(*min);
488       valid_cached_min_ = true;
489     } else {
490       valid_cached_min_ = false;
491     }
492   }
493 }
494 
495 
496 template <TEMPLATE_INVALSET_P_DECL>
BinarySearch(const ElementType & element,ElementType * start,ElementType * end)497 ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::BinarySearch(
498     const ElementType& element, ElementType* start, ElementType* end) const {
499   if (start == end) {
500     return NULL;
501   }
502   VIXL_ASSERT(sorted_);
503   VIXL_ASSERT(start < end);
504   VIXL_ASSERT(!empty());
505 
506   // Perform a binary search through the elements while ignoring invalid
507   // elements.
508   ElementType* elements = start;
509   size_t low = 0;
510   size_t high = (end - start) - 1;
511   while (low < high) {
512     // Find valid bounds.
513     while (!IsValid(elements[low]) && (low < high)) ++low;
514     while (!IsValid(elements[high]) && (low < high)) --high;
515     VIXL_ASSERT(low <= high);
516     // Avoid overflow when computing the middle index.
517     size_t middle = low + (high - low) / 2;
518     if ((middle == low) || (middle == high)) {
519       break;
520     }
521     while ((middle < high - 1) && !IsValid(elements[middle])) ++middle;
522     while ((low + 1 < middle) && !IsValid(elements[middle])) --middle;
523     if (!IsValid(elements[middle])) {
524       break;
525     }
526     if (elements[middle] < element) {
527       low = middle;
528     } else {
529       high = middle;
530     }
531   }
532 
533   if (elements[low] == element) return &elements[low];
534   if (elements[high] == element) return &elements[high];
535   return NULL;
536 }
537 
538 
539 template <TEMPLATE_INVALSET_P_DECL>
Sort(SortType sort_type)540 void InvalSet<TEMPLATE_INVALSET_P_DEF>::Sort(SortType sort_type) {
541   if (sort_type == kSoftSort) {
542     if (sorted_) {
543       return;
544     }
545   }
546   VIXL_ASSERT(monitor() == 0);
547   if (empty()) {
548     return;
549   }
550 
551   Clean();
552   std::sort(StorageBegin(), StorageEnd());
553 
554   SetSorted(true);
555   cached_min_index_ = 0;
556   cached_min_key_ = GetKey(Front());
557   valid_cached_min_ = true;
558 }
559 
560 
561 template <TEMPLATE_INVALSET_P_DECL>
Clean()562 void InvalSet<TEMPLATE_INVALSET_P_DEF>::Clean() {
563   VIXL_ASSERT(monitor() == 0);
564   if (empty() || !IsUsingVector()) {
565     return;
566   }
567   // Manually iterate through the vector storage to discard invalid elements.
568   ElementType* start = &(vector_->front());
569   ElementType* end = start + vector_->size();
570   ElementType* c = start;
571   ElementType* first_invalid;
572   ElementType* first_valid;
573   ElementType* next_invalid;
574 
575   while ((c < end) && IsValid(*c)) c++;
576   first_invalid = c;
577 
578   while (c < end) {
579     while ((c < end) && !IsValid(*c)) c++;
580     first_valid = c;
581     while ((c < end) && IsValid(*c)) c++;
582     next_invalid = c;
583 
584     ptrdiff_t n_moved_elements = (next_invalid - first_valid);
585     memmove(first_invalid, first_valid, n_moved_elements * sizeof(*c));
586     first_invalid = first_invalid + n_moved_elements;
587     c = next_invalid;
588   }
589 
590   // Delete the trailing invalid elements.
591   vector_->erase(vector_->begin() + (first_invalid - start), vector_->end());
592   VIXL_ASSERT(vector_->size() == size_);
593 
594   if (sorted_) {
595     valid_cached_min_ = true;
596     cached_min_index_ = 0;
597     cached_min_key_ = GetKey(*GetElementAt(0));
598   } else {
599     valid_cached_min_ = false;
600   }
601 }
602 
603 
604 template <TEMPLATE_INVALSET_P_DECL>
Front()605 const ElementType InvalSet<TEMPLATE_INVALSET_P_DEF>::Front() const {
606   VIXL_ASSERT(!empty());
607   return IsUsingVector() ? vector_->front() : preallocated_[0];
608 }
609 
610 
611 template <TEMPLATE_INVALSET_P_DECL>
Back()612 const ElementType InvalSet<TEMPLATE_INVALSET_P_DEF>::Back() const {
613   VIXL_ASSERT(!empty());
614   return IsUsingVector() ? vector_->back() : preallocated_[size_ - 1];
615 }
616 
617 
618 template <TEMPLATE_INVALSET_P_DECL>
CleanBack()619 const ElementType InvalSet<TEMPLATE_INVALSET_P_DEF>::CleanBack() {
620   VIXL_ASSERT(monitor() == 0);
621   if (IsUsingVector()) {
622     // Delete the invalid trailing elements.
623     typename std::vector<ElementType>::reverse_iterator it = vector_->rbegin();
624     while (!IsValid(*it)) {
625       it++;
626     }
627     vector_->erase(it.base(), vector_->end());
628   }
629   return Back();
630 }
631 
632 
633 template <TEMPLATE_INVALSET_P_DECL>
StorageBegin()634 const ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::StorageBegin() const {
635   return IsUsingVector() ? &(vector_->front()) : preallocated_;
636 }
637 
638 
639 template <TEMPLATE_INVALSET_P_DECL>
StorageEnd()640 const ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::StorageEnd() const {
641   return IsUsingVector() ? &(vector_->back()) + 1 : preallocated_ + size_;
642 }
643 
644 
645 template <TEMPLATE_INVALSET_P_DECL>
StorageBegin()646 ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::StorageBegin() {
647   return IsUsingVector() ? &(vector_->front()) : preallocated_;
648 }
649 
650 
651 template <TEMPLATE_INVALSET_P_DECL>
StorageEnd()652 ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::StorageEnd() {
653   return IsUsingVector() ? &(vector_->back()) + 1 : preallocated_ + size_;
654 }
655 
656 
657 template <TEMPLATE_INVALSET_P_DECL>
GetElementIndex(const ElementType * element)658 size_t InvalSet<TEMPLATE_INVALSET_P_DEF>::GetElementIndex(
659     const ElementType* element) const {
660   VIXL_ASSERT((StorageBegin() <= element) && (element < StorageEnd()));
661   return element - StorageBegin();
662 }
663 
664 
665 template <TEMPLATE_INVALSET_P_DECL>
GetElementAt(size_t index)666 const ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::GetElementAt(
667     size_t index) const {
668   VIXL_ASSERT((IsUsingVector() && (index < vector_->size())) ||
669               (index < size_));
670   return StorageBegin() + index;
671 }
672 
673 template <TEMPLATE_INVALSET_P_DECL>
GetElementAt(size_t index)674 ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::GetElementAt(size_t index) {
675   VIXL_ASSERT((IsUsingVector() && (index < vector_->size())) ||
676               (index < size_));
677   return StorageBegin() + index;
678 }
679 
680 template <TEMPLATE_INVALSET_P_DECL>
GetFirstValidElement(const ElementType * from,const ElementType * end)681 const ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::GetFirstValidElement(
682     const ElementType* from, const ElementType* end) {
683   while ((from < end) && !IsValid(*from)) {
684     from++;
685   }
686   return from;
687 }
688 
689 
690 template <TEMPLATE_INVALSET_P_DECL>
CacheMinElement()691 void InvalSet<TEMPLATE_INVALSET_P_DEF>::CacheMinElement() {
692   VIXL_ASSERT(monitor() == 0);
693   VIXL_ASSERT(!empty());
694 
695   if (valid_cached_min_) {
696     return;
697   }
698 
699   if (sorted_) {
700     const ElementType* min = GetFirstValidElement(StorageBegin(), StorageEnd());
701     cached_min_index_ = GetElementIndex(min);
702     cached_min_key_ = GetKey(*min);
703     valid_cached_min_ = true;
704   } else {
705     Sort(kHardSort);
706   }
707   VIXL_ASSERT(valid_cached_min_);
708 }
709 
710 
711 template <TEMPLATE_INVALSET_P_DECL>
ShouldReclaimMemory()712 bool InvalSet<TEMPLATE_INVALSET_P_DEF>::ShouldReclaimMemory() const {
713   if (!IsUsingVector()) {
714     return false;
715   }
716   size_t n_invalid_elements = vector_->size() - size_;
717   return (n_invalid_elements > RECLAIM_FROM) &&
718          (n_invalid_elements > vector_->size() / RECLAIM_FACTOR);
719 }
720 
721 
722 template <TEMPLATE_INVALSET_P_DECL>
ReclaimMemory()723 void InvalSet<TEMPLATE_INVALSET_P_DEF>::ReclaimMemory() {
724   VIXL_ASSERT(monitor() == 0);
725   Clean();
726 }
727 
728 
729 template <class S>
InvalSetIterator(S * inval_set)730 InvalSetIterator<S>::InvalSetIterator(S* inval_set)
731     : using_vector_((inval_set != NULL) && inval_set->IsUsingVector()),
732       index_(0),
733       inval_set_(inval_set) {
734   if (inval_set != NULL) {
735     inval_set->Sort(S::kSoftSort);
736 #ifdef VIXL_DEBUG
737     inval_set->Acquire();
738 #endif
739     if (using_vector_) {
740       iterator_ = typename std::vector<ElementType>::iterator(
741           inval_set_->vector_->begin());
742     }
743     MoveToValidElement();
744   }
745 }
746 
747 
748 template <class S>
~InvalSetIterator()749 InvalSetIterator<S>::~InvalSetIterator() {
750 #ifdef VIXL_DEBUG
751   if (inval_set_ != NULL) inval_set_->Release();
752 #endif
753 }
754 
755 
756 template <class S>
Current()757 typename S::_ElementType* InvalSetIterator<S>::Current() const {
758   VIXL_ASSERT(!Done());
759   if (using_vector_) {
760     return &(*iterator_);
761   } else {
762     return &(inval_set_->preallocated_[index_]);
763   }
764 }
765 
766 
767 template <class S>
Advance()768 void InvalSetIterator<S>::Advance() {
769   ++(*this);
770 }
771 
772 
773 template <class S>
Done()774 bool InvalSetIterator<S>::Done() const {
775   if (using_vector_) {
776     bool done = (iterator_ == inval_set_->vector_->end());
777     VIXL_ASSERT(done == (index_ == inval_set_->size()));
778     return done;
779   } else {
780     return index_ == inval_set_->size();
781   }
782 }
783 
784 
785 template <class S>
Finish()786 void InvalSetIterator<S>::Finish() {
787   VIXL_ASSERT(inval_set_->sorted_);
788   if (using_vector_) {
789     iterator_ = inval_set_->vector_->end();
790   }
791   index_ = inval_set_->size();
792 }
793 
794 
795 template <class S>
DeleteCurrentAndAdvance()796 void InvalSetIterator<S>::DeleteCurrentAndAdvance() {
797   if (using_vector_) {
798     inval_set_->EraseInternal(&(*iterator_));
799     MoveToValidElement();
800   } else {
801     inval_set_->EraseInternal(inval_set_->preallocated_ + index_);
802   }
803 }
804 
805 
806 template <class S>
IsValid(const ElementType & element)807 bool InvalSetIterator<S>::IsValid(const ElementType& element) {
808   return S::IsValid(element);
809 }
810 
811 
812 template <class S>
GetKey(const ElementType & element)813 typename S::_KeyType InvalSetIterator<S>::GetKey(const ElementType& element) {
814   return S::GetKey(element);
815 }
816 
817 
818 template <class S>
MoveToValidElement()819 void InvalSetIterator<S>::MoveToValidElement() {
820   if (using_vector_) {
821     while ((iterator_ != inval_set_->vector_->end()) && !IsValid(*iterator_)) {
822       iterator_++;
823     }
824   } else {
825     VIXL_ASSERT(inval_set_->empty() || IsValid(inval_set_->preallocated_[0]));
826     // Nothing to do.
827   }
828 }
829 
830 
831 template <class S>
InvalSetIterator(const InvalSetIterator<S> & other)832 InvalSetIterator<S>::InvalSetIterator(const InvalSetIterator<S>& other)
833     : using_vector_(other.using_vector_),
834       index_(other.index_),
835       inval_set_(other.inval_set_) {
836 #ifdef VIXL_DEBUG
837   if (inval_set_ != NULL) inval_set_->Acquire();
838 #endif
839 }
840 
841 
842 #if __cplusplus >= 201103L
843 template <class S>
InvalSetIterator(InvalSetIterator<S> && other)844 InvalSetIterator<S>::InvalSetIterator(InvalSetIterator<S>&& other) noexcept
845     : using_vector_(false),
846       index_(0),
847       inval_set_(NULL) {
848   swap(*this, other);
849 }
850 #endif
851 
852 
853 template <class S>
854 InvalSetIterator<S>& InvalSetIterator<S>::operator=(InvalSetIterator<S> other) {
855   swap(*this, other);
856   return *this;
857 }
858 
859 
860 template <class S>
861 bool InvalSetIterator<S>::operator==(const InvalSetIterator<S>& rhs) const {
862   bool equal = (inval_set_ == rhs.inval_set_);
863 
864   // If the inval_set_ matches, using_vector_ must also match.
865   VIXL_ASSERT(!equal || (using_vector_ == rhs.using_vector_));
866 
867   if (using_vector_) {
868     equal = equal && (iterator_ == rhs.iterator_);
869     // In debug mode, index_ is maintained even with using_vector_.
870     VIXL_ASSERT(!equal || (index_ == rhs.index_));
871   } else {
872     equal = equal && (index_ == rhs.index_);
873 #ifdef DEBUG
874     // If not using_vector_, iterator_ should be default-initialised.
875     typename std::vector<ElementType>::iterator default_iterator;
876     VIXL_ASSERT(iterator_ == default_iterator);
877     VIXL_ASSERT(rhs.iterator_ == default_iterator);
878 #endif
879   }
880   return equal;
881 }
882 
883 
884 template <class S>
885 InvalSetIterator<S>& InvalSetIterator<S>::operator++() {
886   // Pre-increment.
887   VIXL_ASSERT(!Done());
888   if (using_vector_) {
889     iterator_++;
890 #ifdef VIXL_DEBUG
891     index_++;
892 #endif
893     MoveToValidElement();
894   } else {
895     index_++;
896   }
897   return *this;
898 }
899 
900 
901 template <class S>
902 InvalSetIterator<S> InvalSetIterator<S>::operator++(int /* unused */) {
903   // Post-increment.
904   VIXL_ASSERT(!Done());
905   InvalSetIterator<S> old(*this);
906   ++(*this);
907   return old;
908 }
909 
910 
911 #undef TEMPLATE_INVALSET_P_DECL
912 #undef TEMPLATE_INVALSET_P_DEF
913 
914 }  // namespace vixl
915 
916 #endif  // VIXL_INVALSET_H_
917