1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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
37namespace vixl {
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
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 \
82ElementType, N_PREALLOCATED_ELEMENTS, \
83KeyType, INVALID_KEY, RECLAIM_FROM, RECLAIM_FACTOR
84
85template<class S> class InvalSetIterator;
86
87template<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
96 void insert(const ElementType& element);
97
98
99 void erase(const ElementType& element);
100
101
102 size_t size() const;
103
104
105
106
107 bool empty() const;
108
109 void clear();
110
111 const ElementType min_element();
112
113
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
122
123 ElementType* Search(const ElementType& element);
124
125
126
127
128 void EraseInternal(ElementType* element);
129
130
131 ElementType* BinarySearch(const ElementType& element,
132 ElementType* start,
133 ElementType* end) const;
134
135
136 enum SortType {
137
138
139 kHardSort,
140
141
142 kSoftSort
143 };
144 void Sort(SortType sort_type);
145
146
147
148 void Clean();
149
150 const ElementType Front() const;
151 const ElementType Back() const;
152
153
154
155 const ElementType CleanBack();
156
157
158 const ElementType* StorageBegin() const;
159 const ElementType* StorageEnd() const;
160 ElementType* StorageBegin();
161 ElementType* StorageEnd();
162
163
164
165 size_t ElementIndex(const ElementType* element) const;
166
167
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
184
185
186 bool valid_cached_min_;
187 size_t cached_min_index_;
188 KeyType cached_min_key_;
189
190
191 bool sorted_;
192
193
194 size_t size_;
195
196
197
198
199
200
201
202 ElementType preallocated_[kNPreallocatedElements];
203 std::vector<ElementType>* vector_;
204
205#ifdef VIXL_DEBUG
206
207
208
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
224template<class S> class InvalSetIterator {
225 private:
226
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
239 void Finish();
240
241
242
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
252
253 const bool using_vector_;
254
255
256 size_t index_;
257 typename std::vector<ElementType>::iterator iterator_;
258 S* inval_set_;
259};
260
261
262template<TEMPLATE_INVALSET_P_DECL>
263InvalSet<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
272template<TEMPLATE_INVALSET_P_DECL>
273InvalSet<TEMPLATE_INVALSET_P_DEF>::~InvalSet() {
274 VIXL_ASSERT(monitor_ == 0);
275 delete vector_;
276}
277
278
279template<TEMPLATE_INVALSET_P_DECL>
280void 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
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
311template<TEMPLATE_INVALSET_P_DECL>
312void 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
322template<TEMPLATE_INVALSET_P_DECL>
323ElementType* 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
342template<TEMPLATE_INVALSET_P_DECL>
343size_t InvalSet<TEMPLATE_INVALSET_P_DEF>::size() const {
344 return size_;
345}
346
347
348template<TEMPLATE_INVALSET_P_DECL>
349bool InvalSet<TEMPLATE_INVALSET_P_DEF>::empty() const {
350 return size_ == 0;
351}
352
353
354template<TEMPLATE_INVALSET_P_DECL>
355void 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
366template<TEMPLATE_INVALSET_P_DECL>
367const 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
375template<TEMPLATE_INVALSET_P_DECL>
376KeyType 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
386template<TEMPLATE_INVALSET_P_DECL>
387bool InvalSet<TEMPLATE_INVALSET_P_DEF>::IsValid(const ElementType& element) {
388 return Key(element) != kInvalidKey;
389}
390
391
392template<TEMPLATE_INVALSET_P_DECL>
393void InvalSet<TEMPLATE_INVALSET_P_DEF>::EraseInternal(ElementType* element) {
394
395
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
425template<TEMPLATE_INVALSET_P_DECL>
426ElementType* 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
436
437 ElementType* elements = start;
438 size_t low = 0;
439 size_t high = (end - start) - 1;
440 while (low < high) {
441
442 while (!IsValid(elements[low]) && (low < high)) ++low;
443 while (!IsValid(elements[high]) && (low < high)) --high;
444 VIXL_ASSERT(low <= high);
445
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
468template<TEMPLATE_INVALSET_P_DECL>
469void 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
490template<TEMPLATE_INVALSET_P_DECL>
491void InvalSet<TEMPLATE_INVALSET_P_DEF>::Clean() {
492 VIXL_ASSERT(monitor() == 0);
493 if (empty() || !IsUsingVector()) {
494 return;
495 }
496
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
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
533template<TEMPLATE_INVALSET_P_DECL>
534const ElementType InvalSet<TEMPLATE_INVALSET_P_DEF>::Front() const {
535 VIXL_ASSERT(!empty());
536 return IsUsingVector() ? vector_->front() : preallocated_[0];
537}
538
539
540template<TEMPLATE_INVALSET_P_DECL>
541const ElementType InvalSet<TEMPLATE_INVALSET_P_DEF>::Back() const {
542 VIXL_ASSERT(!empty());
543 return IsUsingVector() ? vector_->back() : preallocated_[size_ - 1];
544}
545
546
547template<TEMPLATE_INVALSET_P_DECL>
548const ElementType InvalSet<TEMPLATE_INVALSET_P_DEF>::CleanBack() {
549 VIXL_ASSERT(monitor() == 0);
550 if (IsUsingVector()) {
551
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
562template<TEMPLATE_INVALSET_P_DECL>
563const ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::StorageBegin() const {
564 return IsUsingVector() ? &(vector_->front()) : preallocated_;
565}
566
567
568template<TEMPLATE_INVALSET_P_DECL>
569const ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::StorageEnd() const {
570 return IsUsingVector() ? &(vector_->back()) + 1 : preallocated_ + size_;
571}
572
573
574template<TEMPLATE_INVALSET_P_DECL>
575ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::StorageBegin() {
576 return IsUsingVector() ? &(vector_->front()) : preallocated_;
577}
578
579
580template<TEMPLATE_INVALSET_P_DECL>
581ElementType* InvalSet<TEMPLATE_INVALSET_P_DEF>::StorageEnd() {
582 return IsUsingVector() ? &(vector_->back()) + 1 : preallocated_ + size_;
583}
584
585
586template<TEMPLATE_INVALSET_P_DECL>
587size_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
594template<TEMPLATE_INVALSET_P_DECL>
595const 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
602template<TEMPLATE_INVALSET_P_DECL>
603ElementType* 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
609template<TEMPLATE_INVALSET_P_DECL>
610const 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
619template<TEMPLATE_INVALSET_P_DECL>
620void 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
640template<TEMPLATE_INVALSET_P_DECL>
641bool 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
651template<TEMPLATE_INVALSET_P_DECL>
652void InvalSet<TEMPLATE_INVALSET_P_DEF>::ReclaimMemory() {
653 VIXL_ASSERT(monitor() == 0);
654 Clean();
655}
656
657
658template<class S>
659InvalSetIterator<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
677template<class S>
678InvalSetIterator<S>::~InvalSetIterator() {
679#ifdef VIXL_DEBUG
680 if (inval_set_ != NULL) {
681 inval_set_->Release();
682 }
683#endif
684}
685
686
687template<class S>
688typename 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
698template<class S>
699void 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
713template<class S>
714bool 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
725template<class S>
726void 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
735template<class S>
736void 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
746template<class S>
747bool InvalSetIterator<S>::IsValid(const ElementType& element) {
748 return S::IsValid(element);
749}
750
751
752template<class S>
753typename S::_KeyType InvalSetIterator<S>::Key(const ElementType& element) {
754 return S::Key(element);
755}
756
757
758template<class S>
759void 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
767 }
768}
769
770#undef TEMPLATE_INVALSET_P_DECL
771#undef TEMPLATE_INVALSET_P_DEF
772
773}
774
775#endif
776