1//
2// OrderedContainersTest.h
3//
4// Definition of the OrderedContainersTest class.
5//
6// SPDX-License-Identifier: BSL-1.0
7//
8
9
10#ifndef OrderedContainersTest_INCLUDED
11#define OrderedContainersTest_INCLUDED
12
13
14#include "Poco/Foundation.h"
15#include "Poco/CppUnit/TestCase.h"
16#include "Poco/OrderedMap.h"
17#include "Poco/OrderedSet.h"
18#include "ordered_map_util.h"
19#include <tuple>
20#include <deque>
21
22#ifdef POCO_COMPILER_MSVC
23#pragma warning(push)
24#pragma warning(disable : 4244)
25#pragma warning(disable : 4267)
26#endif // POCO_COMPILER_MSVC
27
28class OrderedContainersTest: public CppUnit::TestCase
29{
30public:
31 OrderedContainersTest(const std::string& name);
32 ~OrderedContainersTest();
33
34 void testMapInsert();
35 void testRangeInsert();
36 void testInsertWithHint();
37 void testEmplace();
38 void testTryEmplace();
39 void testTryEmplace2();
40 void testTryEmplaceHint();
41 void testInsertOrAssign();
42 void testInsertOrAssignHint();
43 void testInsertAtPosition();
44 void testTryEmplaceAtPosition();
45 void testRangeErase();
46 void testMapEraseLoop();
47 void testMapInsertEraseInsert();
48 void testRangeEraseAll();
49 void testRangeEraseSameIterators();
50 void testUnorderedErase();
51 void testCompare();
52 void testClear();
53 void testReverseIterator();
54 void testIteratorArithmetic();
55 void testIteratorComparators();
56 void testModifyValue();
57 void testAssignOperator();
58 void testMoveConstructor();
59 void testMoveOperator();
60 void testReassignMovedObjectMoveConstructor();
61 void testReassignMovedObjectMoveOperator();
62 void testCopyConstructorOperator();
63 void testAt();
64 void testEqualRange();
65 void testData();
66 void testAccessOperator();
67 void testSwap();
68 void testFrontBack();
69 void testNth();
70 void testHeterogeneousLookups();
71 void testEmptyMap();
72 void testPrecalculatedHash();
73
74 void testSetInsert();
75
76 void testCustomAllocator1();
77
78 void setUp();
79 void tearDown();
80
81 static CppUnit::Test* suite();
82
83private:
84
85#define testMapFuncFwd(cont, func) { \
86 func<cont<std::int64_t, std::int64_t>>(); \
87 func<cont<std::int64_t, std::int64_t, \
88 std::hash<std::int64_t>, std::equal_to<std::int64_t>, \
89 std::allocator<std::pair<std::int64_t, std::int64_t>>, \
90 std::deque<std::pair<std::int64_t, std::int64_t>>>>(); \
91 func<cont<std::int64_t, std::int64_t, \
92 std::hash<std::int64_t>, std::equal_to<std::int64_t>, \
93 std::allocator<std::pair<std::int64_t, std::int64_t>>, \
94 std::vector<std::pair<std::int64_t, std::int64_t>>>>(); \
95 func<cont<std::string, std::string>>(); \
96 func<cont<std::string, std::string, mod_hash<9>>>(); \
97 }
98// needs significant CppUnit or test changes, maybe one day ...
99//func<cont<move_only_test, move_only_test, mod_hash<9>>>();
100
101#define testSetFuncFwd(cont, func) { \
102 func<cont<std::int64_t, std::hash<std::int64_t>, \
103 std::equal_to<std::int64_t>, \
104 std::allocator<std::int64_t>, \
105 std::deque<std::int64_t>>>(); \
106 func<cont<std::int64_t, std::hash<std::int64_t>, \
107 std::equal_to<std::int64_t>, \
108 std::allocator<std::int64_t>, \
109 std::vector<std::int64_t>>>(); \
110 func<cont<std::int64_t, mod_hash<9>>>(); \
111 func<cont<std::string>>(); \
112 func<cont<std::string, mod_hash<9>>>(); \
113 }
114
115 template <typename T>
116 void testMapInsertImpl()
117 {
118 // insert x values, insert them again, check values through find, check order through iterator
119 using key_tt = typename T::key_type;
120 using value_tt = typename T::mapped_type;
121
122 const std::size_t nb_values = 1000;
123
124 T map;
125 typename T::iterator it;
126 bool inserted;
127
128 for(std::size_t i = 0; i < nb_values; i++)
129 {
130 // Avoid sequential values by splitting the values with modulo
131 const std::size_t insert_val = (i%2 == 0) ? i : nb_values + i;
132 std::tie(it, inserted) = map.insert({utils::get_key<key_tt>(insert_val),
133 utils::get_value<value_tt>(insert_val)});
134
135 assertEquals(it->first, utils::get_key<key_tt>(insert_val));
136 assertEquals(it->second, utils::get_value<value_tt>(insert_val));
137 assertTrue(inserted);
138 }
139 assertEquals(map.size(), nb_values);
140
141 for(std::size_t i = 0; i < nb_values; i++)
142 {
143 const std::size_t insert_val = (i%2 == 0)?i:nb_values + i;
144 std::tie(it, inserted) = map.insert({utils::get_key<key_tt>(insert_val),
145 utils::get_value<value_tt>(insert_val + 1)});
146
147 assertEquals(it->first, utils::get_key<key_tt>(insert_val));
148 assertEquals(it->second, utils::get_value<value_tt>(insert_val));
149 assertTrue(!inserted);
150 }
151 assertEquals(map.size(), nb_values);
152
153 for(std::size_t i = 0; i < nb_values; i++)
154 {
155 const std::size_t insert_val = (i%2 == 0)?i:nb_values + i;
156 it = map.find(utils::get_key<key_tt>(insert_val));
157
158 assertEquals(it->first, utils::get_key<key_tt>(insert_val));
159 assertEquals(it->second, utils::get_value<value_tt>(insert_val));
160 }
161
162 std::size_t i = 0;
163 for(const auto& key_value: map)
164 {
165 const std::size_t insert_val = (i%2 == 0)?i:nb_values + i;
166
167 assertEquals(key_value.first, utils::get_key<key_tt>(insert_val));
168 assertEquals(key_value.second, utils::get_value<value_tt>(insert_val));
169
170 i++;
171 }
172 }
173
174 template <typename T>
175 void testMapEraseLoopImpl()
176 {
177 // insert x values, delete all one by one
178 std::size_t nb_values = 1000;
179
180 T map = utils::get_filled_hash_map<T>(nb_values);
181 T map2 = utils::get_filled_hash_map<T>(nb_values);
182
183 auto it = map.begin();
184 // Use second map to check for key after delete as we may not copy the key with move-only types.
185 auto it2 = map2.begin();
186 while(it != map.end()) {
187 it = map.erase(it);
188 --nb_values;
189
190 assertEquals(map.count(it2->first), 0);
191 assertEquals(map.size(), nb_values);
192 ++it2;
193 }
194
195 assertTrue(map.empty());
196 }
197
198 template <typename T>
199 void testMapInsertEraseInsertImpl()
200 {
201 // insert x/2 values, delete x/4 values, insert x/2 values, find each value, check order of values
202 using key_tt = typename T::key_type; using value_tt = typename T:: mapped_type;
203
204 const std::size_t nb_values = 2000;
205 T map;
206 typename T::iterator it;
207 bool inserted;
208
209 // Insert nb_values/2
210 for(std::size_t i = 0; i < nb_values/2; i++)
211 {
212 std::tie(it, inserted) = map.insert({utils::get_key<key_tt>(i), utils::get_value<value_tt>(i)});
213
214 assertEquals(it->first, utils::get_key<key_tt>(i));
215 assertEquals(it->second, utils::get_value<value_tt>(i));
216 assertTrue(inserted);
217 }
218 assertEquals(map.size(), nb_values/2);
219
220
221 // Delete nb_values/4
222 for(std::size_t i = 0; i < nb_values/2; i++)
223 {
224 if(i%2 == 0) {
225 assertEquals(map.erase(utils::get_key<key_tt>(i)), 1);
226 }
227 }
228 assertEquals(map.size(), nb_values/4);
229
230
231 // Insert nb_values/2
232 for(std::size_t i = nb_values/2; i < nb_values; i++)
233 {
234 std::tie(it, inserted) = map.insert({utils::get_key<key_tt>(i), utils::get_value<value_tt>(i)});
235
236 assertEquals(it->first, utils::get_key<key_tt>(i));
237 assertEquals(it->second, utils::get_value<value_tt>(i));
238 assertTrue(inserted);
239 }
240 assertEquals(map.size(), nb_values-nb_values/4);
241
242
243 // Find
244 for(std::size_t i = 0; i < nb_values; i++)
245 {
246 if(i%2 == 0 && i < nb_values/2)
247 {
248 it = map.find(utils::get_key<key_tt>(i));
249 assertTrue(it == map.cend());
250 }
251 else {
252 it = map.find(utils::get_key<key_tt>(i));
253 assertEquals(it->first, utils::get_key<key_tt>(i));
254 assertEquals(it->second, utils::get_value<value_tt>(i));
255 }
256 }
257
258 // Check order
259 std::size_t i = 1;
260 for(const auto& key_value: map)
261 {
262 if(i < nb_values/2)
263 {
264 assertEquals(key_value.first, utils::get_key<key_tt>(i));
265 assertEquals(key_value.second, utils::get_value<value_tt>(i));
266
267 i = std::min(i+2, nb_values/2);
268 }
269 else
270 {
271 assertEquals(key_value.first, utils::get_key<key_tt>(i));
272 assertEquals(key_value.second, utils::get_value<value_tt>(i));
273
274 i++;
275 }
276 }
277 }
278
279 template <typename T>
280 void testSetInsertImpl()
281 {
282 // insert x values, insert them again, check values through find, check order through iterator
283 using key_t = typename T::key_type;
284
285 const std::size_t nb_values = 1000;
286
287 T set;
288 typename T::iterator it;
289 bool inserted;
290
291 for(std::size_t i = 0; i < nb_values; i++)
292 {
293 const std::size_t insert_val = (i%2 == 0)?i:nb_values + i;
294 std::tie(it, inserted) = set.insert(utils::get_key<key_t>(insert_val));
295
296 assertEquals(*it, utils::get_key<key_t>(insert_val));
297 assertTrue(inserted);
298 }
299 assertEquals(set.size(), nb_values);
300
301 for(std::size_t i = 0; i < nb_values; i++)
302 {
303 const std::size_t insert_val = (i%2 == 0)?i:nb_values + i;
304 std::tie(it, inserted) = set.insert(utils::get_key<key_t>(insert_val));
305
306 assertEquals(*it, utils::get_key<key_t>(insert_val));
307 assertTrue(!inserted);
308 }
309 assertEquals(set.size(), nb_values);
310
311 for(std::size_t i = 0; i < nb_values; i++)
312 {
313 const std::size_t insert_val = (i%2 == 0)?i:nb_values + i;
314 it = set.find(utils::get_key<key_t>(insert_val));
315
316 assertEquals(*it, utils::get_key<key_t>(insert_val));
317 }
318
319 std::size_t i = 0;
320 for(const auto& value: set)
321 {
322 const std::size_t insert_val = (i%2 == 0)?i:nb_values + i;
323
324 assertEquals(value, utils::get_key<key_t>(insert_val));
325
326 i++;
327 }
328 }
329};
330
331#ifdef POCO_COMPILER_MSVC
332#pragma warning(pop)
333#endif // POCO_COMPILER_MSVC
334
335#endif // OrderedContainersTest_INCLUDED
336