tests/qtest: Add npcm7xx timer test
[qemu.git] / disas / libvixl / vixl / invalset.h
1 // Copyright 2015, ARM Limited
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 <string.h>
31
32 #include <algorithm>
33 #include <vector>
34
35 #include "vixl/globals.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 #define TEMPLATE_INVALSET_P_DECL \
74 class ElementType, \
75 unsigned N_PREALLOCATED_ELEMENTS, \
76 class KeyType, \
77 KeyType INVALID_KEY, \
78 size_t RECLAIM_FROM, \
79 unsigned RECLAIM_FACTOR
80
81 #define TEMPLATE_INVALSET_P_DEF \
82 ElementType, N_PREALLOCATED_ELEMENTS, \
83 KeyType, INVALID_KEY, RECLAIM_FROM, RECLAIM_FACTOR
84
85 template<class S> class InvalSetIterator; // Forward declaration.
86
87 template<TEMPLATE_INVALSET_P_DECL> class InvalSet {
88 public:
89 InvalSet();
90 ~InvalSet();
91
92 static const size_t kNPreallocatedElements = N_PREALLOCATED_ELEMENTS;
93 static const KeyType kInvalidKey = INVALID_KEY;
94
95 // It is illegal to insert an element already present in the set.
96 void insert(const ElementType& element);
97
98 // Looks for the specified element in the set and - if found - deletes it.
99 void erase(const ElementType& element);
100
101 // This indicates the number of (valid) elements stored in this set.
102 size_t size() const;
103
104 // Returns true if no elements are stored in the set.
105 // Note that this does not mean the the backing storage is empty: it can still
106 // contain invalid elements.
107 bool empty() const;
108
109 void clear();
110
111 const ElementType min_element();
112
113 // This returns the key of the minimum element in the set.
114 KeyType min_element_key();
115
116 static bool IsValid(const ElementType& element);
117 static KeyType Key(const ElementType& element);
118 static void SetKey(ElementType* element, KeyType key);
119
120 protected:
121 // Returns a pointer to the element in vector_ if it was found, or NULL
122 // otherwise.
123 ElementType* Search(const ElementType& element);
124
125 // The argument *must* point to an element stored in *this* set.
126 // This function is not allowed to move elements in the backing vector
127 // storage.
128 void EraseInternal(ElementType* element);
129
130 // The elements in the range searched must be sorted.
131 ElementType* BinarySearch(const ElementType& element,
132 ElementType* start,
133 ElementType* end) const;
134
135 // Sort the elements.
136 enum SortType {
137 // The 'hard' version guarantees that invalid elements are moved to the end
138 // of the container.
139 kHardSort,
140 // The 'soft' version only guarantees that the elements will be sorted.
141 // Invalid elements may still be present anywhere in the set.
142 kSoftSort
143 };
144 void Sort(SortType sort_type);
145
146 // Delete the elements that have an invalid key. The complexity is linear
147 // with the size of the vector.
148 void Clean();
149
150 const ElementType Front() const;
151 const ElementType Back() const;
152
153 // Delete invalid trailing elements and return the last valid element in the
154 // set.
155 const ElementType CleanBack();
156
157 // Returns a pointer to the start or end of the backing storage.
158 const ElementType* StorageBegin() const;
159 const ElementType* StorageEnd() const;
160 ElementType* StorageBegin();
161 ElementType* StorageEnd();
162
163 // Returns the index of the element within the backing storage. The element
164 // must belong to the backing storage.
165 size_t ElementIndex(const ElementType* element) const;
166
167 // Returns the element at the specified index in the backing storage.
168 const ElementType* ElementAt(size_t index) const;
169 ElementType* ElementAt(size_t index);
170
171 static const ElementType* FirstValidElement(const ElementType* from,
172 const ElementType* end);
173
174 void CacheMinElement();
175 const ElementType CachedMinElement() const;
176
177 bool ShouldReclaimMemory() const;
178 void ReclaimMemory();
179
180 bool IsUsingVector() const { return vector_ != NULL; }
181 void set_sorted(bool sorted) { sorted_ = sorted; }
182
183 // We cache some data commonly required by users to improve performance.
184 // We cannot cache pointers to elements as we do not control the backing
185 // storage.
186 bool valid_cached_min_;
187 size_t cached_min_index_; // Valid iff `valid_cached_min_` is true.
188 KeyType cached_min_key_; // Valid iff `valid_cached_min_` is true.
189
190 // Indicates whether the elements are sorted.
191 bool sorted_;
192
193 // This represents the number of (valid) elements in this set.
194 size_t size_;
195
196 // The backing storage is either the array of preallocated elements or the
197 // vector. The structure starts by using the preallocated elements, and
198 // transitions (permanently) to using the vector once more than
199 // kNPreallocatedElements are used.
200 // Elements are only invalidated when using the vector. The preallocated
201 // storage always only contains valid elements.
202 ElementType preallocated_[kNPreallocatedElements];
203 std::vector<ElementType>* vector_;
204
205 #ifdef VIXL_DEBUG
206 // Iterators acquire and release this monitor. While a set is acquired,
207 // certain operations are illegal to ensure that the iterator will
208 // correctly iterate over the elements in the set.
209 int monitor_;
210 int monitor() const { return monitor_; }
211 void Acquire() { monitor_++; }
212 void Release() {
213 monitor_--;
214 VIXL_ASSERT(monitor_ >= 0);
215 }
216 #endif
217
218 friend class InvalSetIterator<InvalSet<TEMPLATE_INVALSET_P_DEF> >;
219 typedef ElementType _ElementType;
220 typedef KeyType _KeyType;
221 };
222
223
224 template<class S> class InvalSetIterator {
225 private:
226 // Redefine types to mirror the associated set types.
227 typedef typename S::_ElementType ElementType;
228 typedef typename S::_KeyType KeyType;
229
230 public:
231 explicit InvalSetIterator(S* inval_set);
232 ~InvalSetIterator();
233
234 ElementType* Current() const;
235 void Advance();
236 bool Done() const;
237
238 // Mark this iterator as 'done'.
239 void Finish();
240
241 // Delete the current element and advance the iterator to point to the next
242 // element.
243 void DeleteCurrentAndAdvance();
244
245 static bool IsValid(const ElementType& element);
246 static KeyType Key(const ElementType& element);
247
248 protected:
249 void MoveToValidElement();
250
251 // Indicates if the iterator is looking at the vector or at the preallocated
252 // elements.
253 const bool using_vector_;
254 // Used when looking at the preallocated elements, or in debug mode when using
255 // the vector to track how many times the iterator has advanced.
256 size_t index_;
257 typename std::vector<ElementType>::iterator iterator_;
258 S* inval_set_;
259 };
260
261
262 template<TEMPLATE_INVALSET_P_DECL>
263 InvalSet<TEMPLATE_INVALSET_P_DEF>::InvalSet()
264 : valid_cached_min_(false),
265 sorted_(true), size_(0), vector_(NULL) {
266 #ifdef VIXL_DEBUG
267 monitor_ = 0;
268 #endif
269 }
270
271
272 template<TEMPLATE_INVALSET_P_DECL>
273 InvalSet<TEMPLATE_INVALSET_P_DEF>::~InvalSet() {
274 VIXL_ASSERT(monitor_ == 0);
275 delete vector_;
276 }
277
278
279 template<TEMPLATE_INVALSET_P_DECL>
280 void InvalSet<TEMPLATE_INVALSET_P_DEF>::insert(const ElementType& element) {
281 VIXL_ASSERT(monitor() == 0);
282 VIXL_ASSERT(IsValid(element));
283 VIXL_ASSERT(Search(element) == NULL);
284 set_sorted(empty() || (sorted_ && (element > CleanBack())));
285 if (IsUsingVector()) {
286 vector_->push_back(element);
287 } else {
288 if (size_ < kNPreallocatedElements) {
289 preallocated_[size_] = element;
290 } else {
291 // Transition to using the vector.
292 vector_ = new std::vector<ElementType>(preallocated_,
293 preallocated_ + size_);
294 vector_->push_back(element);
295 }
296 }
297 size_++;
298
299 if (valid_cached_min_ && (element < min_element())) {
300 cached_min_index_ = IsUsingVector() ? vector_->size() - 1 : size_ - 1;
301 cached_min_key_ = Key(element);
302 valid_cached_min_ = true;
303 }
304
305 if (ShouldReclaimMemory()) {
306 ReclaimMemory();
307 }
308 }
309
310
311 template<TEMPLATE_INVALSET_P_DECL>
312 void InvalSet<TEMPLATE_INVALSET_P_DEF>::erase(const ElementType& element) {
313 VIXL_ASSERT(monitor() == 0);
314 VIXL_ASSERT(IsValid(element));
315 ElementType* local_element = Search(element);
316 if (local_element != NULL) {
317 EraseInternal(local_element);
318 }
319 }
320
321
322 template<TEMPLATE_INVALSET_P_DECL>
323 ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::Search(
324 const ElementType& element) {
325 VIXL_ASSERT(monitor() == 0);
326 if (empty()) {
327 return NULL;
328 }
329 if (ShouldReclaimMemory()) {
330 ReclaimMemory();
331 }
332 if (!sorted_) {
333 Sort(kHardSort);
334 }
335 if (!valid_cached_min_) {
336 CacheMinElement();
337 }
338 return BinarySearch(element, ElementAt(cached_min_index_), StorageEnd());
339 }
340
341
342 template<TEMPLATE_INVALSET_P_DECL>
343 size_t InvalSet<TEMPLATE_INVALSET_P_DEF>::size() const {
344 return size_;
345 }
346
347
348 template<TEMPLATE_INVALSET_P_DECL>
349 bool InvalSet<TEMPLATE_INVALSET_P_DEF>::empty() const {
350 return size_ == 0;
351 }
352
353
354 template<TEMPLATE_INVALSET_P_DECL>
355 void InvalSet<TEMPLATE_INVALSET_P_DEF>::clear() {
356 VIXL_ASSERT(monitor() == 0);
357 size_ = 0;
358 if (IsUsingVector()) {
359 vector_->clear();
360 }
361 set_sorted(true);
362 valid_cached_min_ = false;
363 }
364
365
366 template<TEMPLATE_INVALSET_P_DECL>
367 const ElementType InvalSet<TEMPLATE_INVALSET_P_DEF>::min_element() {
368 VIXL_ASSERT(monitor() == 0);
369 VIXL_ASSERT(!empty());
370 CacheMinElement();
371 return *ElementAt(cached_min_index_);
372 }
373
374
375 template<TEMPLATE_INVALSET_P_DECL>
376 KeyType InvalSet<TEMPLATE_INVALSET_P_DEF>::min_element_key() {
377 VIXL_ASSERT(monitor() == 0);
378 if (valid_cached_min_) {
379 return cached_min_key_;
380 } else {
381 return Key(min_element());
382 }
383 }
384
385
386 template<TEMPLATE_INVALSET_P_DECL>
387 bool InvalSet<TEMPLATE_INVALSET_P_DEF>::IsValid(const ElementType& element) {
388 return Key(element) != kInvalidKey;
389 }
390
391
392 template<TEMPLATE_INVALSET_P_DECL>
393 void InvalSet<TEMPLATE_INVALSET_P_DEF>::EraseInternal(ElementType* element) {
394 // Note that this function must be safe even while an iterator has acquired
395 // this set.
396 VIXL_ASSERT(element != NULL);
397 size_t deleted_index = ElementIndex(element);
398 if (IsUsingVector()) {
399 VIXL_ASSERT((&(vector_->front()) <= element) &&
400 (element <= &(vector_->back())));
401 SetKey(element, kInvalidKey);
402 } else {
403 VIXL_ASSERT((preallocated_ <= element) &&
404 (element < (preallocated_ + kNPreallocatedElements)));
405 ElementType* end = preallocated_ + kNPreallocatedElements;
406 size_t copy_size = sizeof(*element) * (end - element - 1);
407 memmove(element, element + 1, copy_size);
408 }
409 size_--;
410
411 if (valid_cached_min_ &&
412 (deleted_index == cached_min_index_)) {
413 if (sorted_ && !empty()) {
414 const ElementType* min = FirstValidElement(element, StorageEnd());
415 cached_min_index_ = ElementIndex(min);
416 cached_min_key_ = Key(*min);
417 valid_cached_min_ = true;
418 } else {
419 valid_cached_min_ = false;
420 }
421 }
422 }
423
424
425 template<TEMPLATE_INVALSET_P_DECL>
426 ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::BinarySearch(
427 const ElementType& element, ElementType* start, ElementType* end) const {
428 if (start == end) {
429 return NULL;
430 }
431 VIXL_ASSERT(sorted_);
432 VIXL_ASSERT(start < end);
433 VIXL_ASSERT(!empty());
434
435 // Perform a binary search through the elements while ignoring invalid
436 // elements.
437 ElementType* elements = start;
438 size_t low = 0;
439 size_t high = (end - start) - 1;
440 while (low < high) {
441 // Find valid bounds.
442 while (!IsValid(elements[low]) && (low < high)) ++low;
443 while (!IsValid(elements[high]) && (low < high)) --high;
444 VIXL_ASSERT(low <= high);
445 // Avoid overflow when computing the middle index.
446 size_t middle = low / 2 + high / 2 + (low & high & 1);
447 if ((middle == low) || (middle == high)) {
448 break;
449 }
450 while (!IsValid(elements[middle]) && (middle < high - 1)) ++middle;
451 while (!IsValid(elements[middle]) && (low + 1 < middle)) --middle;
452 if (!IsValid(elements[middle])) {
453 break;
454 }
455 if (elements[middle] < element) {
456 low = middle;
457 } else {
458 high = middle;
459 }
460 }
461
462 if (elements[low] == element) return &elements[low];
463 if (elements[high] == element) return &elements[high];
464 return NULL;
465 }
466
467
468 template<TEMPLATE_INVALSET_P_DECL>
469 void InvalSet<TEMPLATE_INVALSET_P_DEF>::Sort(SortType sort_type) {
470 VIXL_ASSERT(monitor() == 0);
471 if (sort_type == kSoftSort) {
472 if (sorted_) {
473 return;
474 }
475 }
476 if (empty()) {
477 return;
478 }
479
480 Clean();
481 std::sort(StorageBegin(), StorageEnd());
482
483 set_sorted(true);
484 cached_min_index_ = 0;
485 cached_min_key_ = Key(Front());
486 valid_cached_min_ = true;
487 }
488
489
490 template<TEMPLATE_INVALSET_P_DECL>
491 void InvalSet<TEMPLATE_INVALSET_P_DEF>::Clean() {
492 VIXL_ASSERT(monitor() == 0);
493 if (empty() || !IsUsingVector()) {
494 return;
495 }
496 // Manually iterate through the vector storage to discard invalid elements.
497 ElementType* start = &(vector_->front());
498 ElementType* end = start + vector_->size();
499 ElementType* c = start;
500 ElementType* first_invalid;
501 ElementType* first_valid;
502 ElementType* next_invalid;
503
504 while (c < end && IsValid(*c)) { c++; }
505 first_invalid = c;
506
507 while (c < end) {
508 while (c < end && !IsValid(*c)) { c++; }
509 first_valid = c;
510 while (c < end && IsValid(*c)) { c++; }
511 next_invalid = c;
512
513 ptrdiff_t n_moved_elements = (next_invalid - first_valid);
514 memmove(first_invalid, first_valid, n_moved_elements * sizeof(*c));
515 first_invalid = first_invalid + n_moved_elements;
516 c = next_invalid;
517 }
518
519 // Delete the trailing invalid elements.
520 vector_->erase(vector_->begin() + (first_invalid - start), vector_->end());
521 VIXL_ASSERT(vector_->size() == size_);
522
523 if (sorted_) {
524 valid_cached_min_ = true;
525 cached_min_index_ = 0;
526 cached_min_key_ = Key(*ElementAt(0));
527 } else {
528 valid_cached_min_ = false;
529 }
530 }
531
532
533 template<TEMPLATE_INVALSET_P_DECL>
534 const ElementType InvalSet<TEMPLATE_INVALSET_P_DEF>::Front() const {
535 VIXL_ASSERT(!empty());
536 return IsUsingVector() ? vector_->front() : preallocated_[0];
537 }
538
539
540 template<TEMPLATE_INVALSET_P_DECL>
541 const ElementType InvalSet<TEMPLATE_INVALSET_P_DEF>::Back() const {
542 VIXL_ASSERT(!empty());
543 return IsUsingVector() ? vector_->back() : preallocated_[size_ - 1];
544 }
545
546
547 template<TEMPLATE_INVALSET_P_DECL>
548 const ElementType InvalSet<TEMPLATE_INVALSET_P_DEF>::CleanBack() {
549 VIXL_ASSERT(monitor() == 0);
550 if (IsUsingVector()) {
551 // Delete the invalid trailing elements.
552 typename std::vector<ElementType>::reverse_iterator it = vector_->rbegin();
553 while (!IsValid(*it)) {
554 it++;
555 }
556 vector_->erase(it.base(), vector_->end());
557 }
558 return Back();
559 }
560
561
562 template<TEMPLATE_INVALSET_P_DECL>
563 const ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::StorageBegin() const {
564 return IsUsingVector() ? &(vector_->front()) : preallocated_;
565 }
566
567
568 template<TEMPLATE_INVALSET_P_DECL>
569 const ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::StorageEnd() const {
570 return IsUsingVector() ? &(vector_->back()) + 1 : preallocated_ + size_;
571 }
572
573
574 template<TEMPLATE_INVALSET_P_DECL>
575 ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::StorageBegin() {
576 return IsUsingVector() ? &(vector_->front()) : preallocated_;
577 }
578
579
580 template<TEMPLATE_INVALSET_P_DECL>
581 ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::StorageEnd() {
582 return IsUsingVector() ? &(vector_->back()) + 1 : preallocated_ + size_;
583 }
584
585
586 template<TEMPLATE_INVALSET_P_DECL>
587 size_t InvalSet<TEMPLATE_INVALSET_P_DEF>::ElementIndex(
588 const ElementType* element) const {
589 VIXL_ASSERT((StorageBegin() <= element) && (element < StorageEnd()));
590 return element - StorageBegin();
591 }
592
593
594 template<TEMPLATE_INVALSET_P_DECL>
595 const ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::ElementAt(
596 size_t index) const {
597 VIXL_ASSERT(
598 (IsUsingVector() && (index < vector_->size())) || (index < size_));
599 return StorageBegin() + index;
600 }
601
602 template<TEMPLATE_INVALSET_P_DECL>
603 ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::ElementAt(size_t index) {
604 VIXL_ASSERT(
605 (IsUsingVector() && (index < vector_->size())) || (index < size_));
606 return StorageBegin() + index;
607 }
608
609 template<TEMPLATE_INVALSET_P_DECL>
610 const ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::FirstValidElement(
611 const ElementType* from, const ElementType* end) {
612 while ((from < end) && !IsValid(*from)) {
613 from++;
614 }
615 return from;
616 }
617
618
619 template<TEMPLATE_INVALSET_P_DECL>
620 void InvalSet<TEMPLATE_INVALSET_P_DEF>::CacheMinElement() {
621 VIXL_ASSERT(monitor() == 0);
622 VIXL_ASSERT(!empty());
623
624 if (valid_cached_min_) {
625 return;
626 }
627
628 if (sorted_) {
629 const ElementType* min = FirstValidElement(StorageBegin(), StorageEnd());
630 cached_min_index_ = ElementIndex(min);
631 cached_min_key_ = Key(*min);
632 valid_cached_min_ = true;
633 } else {
634 Sort(kHardSort);
635 }
636 VIXL_ASSERT(valid_cached_min_);
637 }
638
639
640 template<TEMPLATE_INVALSET_P_DECL>
641 bool InvalSet<TEMPLATE_INVALSET_P_DEF>::ShouldReclaimMemory() const {
642 if (!IsUsingVector()) {
643 return false;
644 }
645 size_t n_invalid_elements = vector_->size() - size_;
646 return (n_invalid_elements > RECLAIM_FROM) &&
647 (n_invalid_elements > vector_->size() / RECLAIM_FACTOR);
648 }
649
650
651 template<TEMPLATE_INVALSET_P_DECL>
652 void InvalSet<TEMPLATE_INVALSET_P_DEF>::ReclaimMemory() {
653 VIXL_ASSERT(monitor() == 0);
654 Clean();
655 }
656
657
658 template<class S>
659 InvalSetIterator<S>::InvalSetIterator(S* inval_set)
660 : using_vector_((inval_set != NULL) && inval_set->IsUsingVector()),
661 index_(0),
662 inval_set_(inval_set) {
663 if (inval_set != NULL) {
664 inval_set->Sort(S::kSoftSort);
665 #ifdef VIXL_DEBUG
666 inval_set->Acquire();
667 #endif
668 if (using_vector_) {
669 iterator_ = typename std::vector<ElementType>::iterator(
670 inval_set_->vector_->begin());
671 }
672 MoveToValidElement();
673 }
674 }
675
676
677 template<class S>
678 InvalSetIterator<S>::~InvalSetIterator() {
679 #ifdef VIXL_DEBUG
680 if (inval_set_ != NULL) {
681 inval_set_->Release();
682 }
683 #endif
684 }
685
686
687 template<class S>
688 typename S::_ElementType* InvalSetIterator<S>::Current() const {
689 VIXL_ASSERT(!Done());
690 if (using_vector_) {
691 return &(*iterator_);
692 } else {
693 return &(inval_set_->preallocated_[index_]);
694 }
695 }
696
697
698 template<class S>
699 void InvalSetIterator<S>::Advance() {
700 VIXL_ASSERT(!Done());
701 if (using_vector_) {
702 iterator_++;
703 #ifdef VIXL_DEBUG
704 index_++;
705 #endif
706 MoveToValidElement();
707 } else {
708 index_++;
709 }
710 }
711
712
713 template<class S>
714 bool InvalSetIterator<S>::Done() const {
715 if (using_vector_) {
716 bool done = (iterator_ == inval_set_->vector_->end());
717 VIXL_ASSERT(done == (index_ == inval_set_->size()));
718 return done;
719 } else {
720 return index_ == inval_set_->size();
721 }
722 }
723
724
725 template<class S>
726 void InvalSetIterator<S>::Finish() {
727 VIXL_ASSERT(inval_set_->sorted_);
728 if (using_vector_) {
729 iterator_ = inval_set_->vector_->end();
730 }
731 index_ = inval_set_->size();
732 }
733
734
735 template<class S>
736 void InvalSetIterator<S>::DeleteCurrentAndAdvance() {
737 if (using_vector_) {
738 inval_set_->EraseInternal(&(*iterator_));
739 MoveToValidElement();
740 } else {
741 inval_set_->EraseInternal(inval_set_->preallocated_ + index_);
742 }
743 }
744
745
746 template<class S>
747 bool InvalSetIterator<S>::IsValid(const ElementType& element) {
748 return S::IsValid(element);
749 }
750
751
752 template<class S>
753 typename S::_KeyType InvalSetIterator<S>::Key(const ElementType& element) {
754 return S::Key(element);
755 }
756
757
758 template<class S>
759 void InvalSetIterator<S>::MoveToValidElement() {
760 if (using_vector_) {
761 while ((iterator_ != inval_set_->vector_->end()) && !IsValid(*iterator_)) {
762 iterator_++;
763 }
764 } else {
765 VIXL_ASSERT(inval_set_->empty() || IsValid(inval_set_->preallocated_[0]));
766 // Nothing to do.
767 }
768 }
769
770 #undef TEMPLATE_INVALSET_P_DECL
771 #undef TEMPLATE_INVALSET_P_DEF
772
773 } // namespace vixl
774
775 #endif // VIXL_INVALSET_H_