1 // Copyright 2014, 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 #include "test-runner.h"
28
29 #include "vixl/invalset.h"
30
31 namespace vixl {
32
33 // This file contains tests for the `InvalSet` and `InvalSetIterator` classes.
34
35 #define TEST(name) TEST_(INVALSET_##name)
36
37 typedef ptrdiff_t KeyType;
38 typedef ptrdiff_t ValType;
39
40 // We test with an object for which the key and the value are distinct.
41 class Obj {
42 public:
Obj()43 Obj() {}
Obj(KeyType key,ValType val)44 Obj(KeyType key, ValType val) : key_(key), val_(val) {}
45 KeyType key_;
46 ValType val_;
47
operator ==(const Obj & other) const48 bool operator==(const Obj& other) const {
49 return (key_ == other.key_) && (val_ == other.val_);
50 }
operator <(const Obj & other) const51 bool operator<(const Obj& other) const {
52 return (key_ < other.key_) ||
53 ((key_ == other.key_) && (val_ < other.val_));
54 }
operator <=(const Obj & other) const55 bool operator<=(const Obj& other) const {
56 return (key_ <= other.key_) ||
57 ((key_ == other.key_) && (val_ <= other.val_));
58 }
operator >(const Obj & other) const59 bool operator>(const Obj& other) const {
60 return (key_ > other.key_) ||
61 ((key_ == other.key_) && (val_ > other.val_));
62 }
63 };
64
65 static const unsigned kNPreallocatedElements = 8;
66 static const KeyType kInvalidKey = PTRDIFF_MAX;
67 static const size_t kReclaimFrom = 1000;
68 static const unsigned kReclaimFactor = 10;
69
70 typedef InvalSet<Obj,
71 kNPreallocatedElements,
72 KeyType,
73 kInvalidKey,
74 kReclaimFrom,
75 kReclaimFactor> TestSet;
76
77 template<>
78 inline KeyType InvalSet<Obj,
79 kNPreallocatedElements,
80 KeyType,
81 kInvalidKey,
82 kReclaimFrom,
Key(const Obj & obj)83 kReclaimFactor>::Key(const Obj& obj) {
84 return obj.key_;
85 }
86 template<>
87 inline void InvalSet<Obj,
88 kNPreallocatedElements,
89 KeyType,
90 kInvalidKey,
91 kReclaimFrom,
SetKey(Obj * obj,KeyType key)92 kReclaimFactor>::SetKey(Obj* obj, KeyType key) {
93 obj->key_ = key;
94 }
95
96
TEST(basic_test)97 TEST(basic_test) {
98 TestSet set;
99 VIXL_CHECK(set.empty() && (set.size() == 0));
100
101 for (unsigned i = 0; i < kNPreallocatedElements; i++) {
102 set.insert(Obj(i, i));
103 }
104 VIXL_CHECK(set.size() == kNPreallocatedElements);
105
106 set.insert(Obj(-123, 456));
107 set.insert(Obj(2718, 2871828));
108 VIXL_CHECK(set.size() == kNPreallocatedElements + 2);
109 VIXL_CHECK(set.min_element() == Obj(-123, 456));
110
111 set.erase(Obj(-123, 456));
112 VIXL_CHECK(set.min_element_key() == 0);
113
114 set.clear();
115 VIXL_CHECK(set.empty() && (set.size() == 0));
116 }
117
118
TEST(valid_element)119 TEST(valid_element) {
120 VIXL_CHECK(TestSet::IsValid(Obj(0, 0)));
121 VIXL_CHECK(TestSet::IsValid(Obj(-1, 0)));
122 VIXL_CHECK(TestSet::IsValid(Obj(kInvalidKey - 1, 0)));
123 VIXL_CHECK(!TestSet::IsValid(Obj(kInvalidKey, 0)));
124 }
125
126
TEST(insert)127 TEST(insert) {
128 TestSet set;
129 VIXL_CHECK(set.empty() && (set.size() == 0));
130
131 for (unsigned i = 0; i < kNPreallocatedElements; i++) {
132 set.insert(Obj(i, i));
133 }
134 VIXL_CHECK(set.size() == kNPreallocatedElements);
135 set.insert(Obj(-123, 1));
136 VIXL_CHECK(set.size() == kNPreallocatedElements + 1);
137 set.insert(Obj(-123, 2));
138 set.insert(Obj(-123, 3));
139 VIXL_CHECK(set.size() == kNPreallocatedElements + 3);
140
141 set.clear();
142 VIXL_CHECK(set.empty() && (set.size() == 0));
143 }
144
145
TEST(erase)146 TEST(erase) {
147 TestSet set;
148 VIXL_CHECK(set.empty() && (set.size() == 0));
149
150 // Test with only preallocated elements in the set.
151 VIXL_STATIC_ASSERT(kNPreallocatedElements >= 2);
152 set.insert(Obj(2718, 0));
153 set.erase(Obj(2718, 0));
154 VIXL_CHECK(set.empty() && (set.size() == 0));
155 set.insert(Obj(2718, 0));
156 VIXL_CHECK(set.size() == 1);
157 set.insert(Obj(2718, 1));
158 VIXL_CHECK(set.size() == 2);
159 set.erase(Obj(2718, 0));
160 VIXL_CHECK(set.size() == 1);
161
162 // Test with more elements.
163 for (unsigned i = 0; i < 100 * kNPreallocatedElements; i++) {
164 set.insert(Obj(i * i, i % 30));
165 set.insert(Obj(i, -1));
166 }
167 size_t max_size = set.size();
168 set.erase(Obj(100, -1));
169 VIXL_CHECK(set.size() == max_size - 1);
170 for (size_t i = 2; i <= max_size; i++) {
171 set.erase(set.min_element());
172 VIXL_CHECK(set.size() == max_size - i);
173 }
174
175 VIXL_CHECK(set.empty() && (set.size() == 0));
176 }
177
178
TEST(min)179 TEST(min) {
180 TestSet set;
181 VIXL_CHECK(set.empty() && (set.size() == 0));
182
183 // Test with only preallocated elements in the set.
184 VIXL_STATIC_ASSERT(kNPreallocatedElements >= 4);
185 set.insert(Obj(-1, -1));
186 set.insert(Obj(-1, 0));
187 set.insert(Obj(0, 0));
188 set.insert(Obj(1, 0));
189 VIXL_CHECK(set.min_element() == Obj(-1, -1));
190 VIXL_CHECK(set.min_element_key() == -1);
191 VIXL_CHECK(set.min_element().key_ == set.min_element_key());
192
193 // Test with more elements.
194 set.clear();
195 int max_index = 100 * kNPreallocatedElements;
196 for (int i = 0; i <= max_index; i++) {
197 // Insert elements out of order.
198 int sign = ((i % 2) == 0) ? -1 : 1;
199 set.insert(Obj(sign * i, i));
200 }
201 VIXL_CHECK(set.min_element() == Obj(-max_index, max_index));
202 VIXL_CHECK(set.min_element().key_ == set.min_element_key());
203
204 set.erase(Obj(0, 0));
205 VIXL_CHECK(set.min_element() == Obj(-max_index, max_index));
206 set.erase(set.min_element());
207 VIXL_CHECK(set.min_element() == Obj(-(max_index - 2), max_index - 2));
208
209 set.clear();
210 VIXL_CHECK(set.empty() && (set.size() == 0));
211 }
212
213
TEST(iterator)214 TEST(iterator) {
215 TestSet set;
216 VIXL_CHECK(set.empty() && (set.size() == 0));
217
218 // Test with only preallocated elements in the set.
219 for (unsigned i = 0; i < kNPreallocatedElements; i++) {
220 set.insert(Obj(i, i));
221 }
222
223 size_t size = 0;
224 for (InvalSetIterator<TestSet> it(&set); !it.Done(); it.Advance()) {
225 size++;
226 }
227 VIXL_CHECK(size == set.size());
228
229 // Test with more elements.
230 for (unsigned i = kNPreallocatedElements;
231 i < 4 * kNPreallocatedElements;
232 i++) {
233 set.insert(Obj(i, i));
234 }
235
236 size = 0;
237 for (InvalSetIterator<TestSet> it(&set); !it.Done(); it.Advance()) {
238 size++;
239 }
240 VIXL_CHECK(size == set.size());
241
242 // Test after an element has been deleted.
243 size = 0;
244 set.erase(Obj(0, 0));
245 for (InvalSetIterator<TestSet> it(&set); !it.Done(); it.Advance()) {
246 size++;
247 }
248 VIXL_CHECK(size == set.size());
249 }
250
251 } // namespace vixl
252