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
31namespace vixl {
32
33// This file contains tests for the `InvalSet` and `InvalSetIterator` classes.
34
35#define TEST(name)  TEST_(INVALSET_##name)
36
37typedef ptrdiff_t KeyType;
38typedef ptrdiff_t ValType;
39
40// We test with an object for which the key and the value are distinct.
41class Obj {
42 public:
43  Obj() {}
44  Obj(KeyType key, ValType val) : key_(key), val_(val) {}
45  KeyType key_;
46  ValType val_;
47
48  bool operator==(const Obj& other) const {
49    return (key_ == other.key_) && (val_ == other.val_);
50  }
51  bool operator<(const Obj& other) const {
52    return (key_ < other.key_) ||
53        ((key_ == other.key_) && (val_ < other.val_));
54  }
55  bool operator<=(const Obj& other) const {
56    return (key_ <= other.key_) ||
57        ((key_ == other.key_) && (val_ <= other.val_));
58  }
59  bool operator>(const Obj& other) const {
60    return (key_ > other.key_) ||
61        ((key_ == other.key_) && (val_ > other.val_));
62  }
63};
64
65static const unsigned kNPreallocatedElements = 8;
66static const KeyType kInvalidKey = PTRDIFF_MAX;
67static const size_t kReclaimFrom = 1000;
68static const unsigned kReclaimFactor = 10;
69
70typedef InvalSet<Obj,
71                 kNPreallocatedElements,
72                 KeyType,
73                 kInvalidKey,
74                 kReclaimFrom,
75                 kReclaimFactor> TestSet;
76
77template<>
78inline KeyType InvalSet<Obj,
79                        kNPreallocatedElements,
80                        KeyType,
81                        kInvalidKey,
82                        kReclaimFrom,
83                        kReclaimFactor>::Key(const Obj& obj) {
84  return obj.key_;
85}
86template<>
87inline void InvalSet<Obj,
88                     kNPreallocatedElements,
89                     KeyType,
90                     kInvalidKey,
91                     kReclaimFrom,
92                     kReclaimFactor>::SetKey(Obj* obj, KeyType key) {
93  obj->key_ = key;
94}
95
96
97TEST(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
119TEST(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
127TEST(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
146TEST(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
179TEST(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
214TEST(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