1 /* Copyright 2009-2016 Francesco Biscani (bluescarni@gmail.com)
2
3 This file is part of the Piranha library.
4
5 The Piranha library is free software; you can redistribute it and/or modify
6 it under the terms of either:
7
8 * the GNU Lesser General Public License as published by the Free
9 Software Foundation; either version 3 of the License, or (at your
10 option) any later version.
11
12 or
13
14 * the GNU General Public License as published by the Free Software
15 Foundation; either version 3 of the License, or (at your option) any
16 later version.
17
18 or both in parallel, as here.
19
20 The Piranha library is distributed in the hope that it will be useful, but
21 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
22 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
23 for more details.
24
25 You should have received copies of the GNU General Public License and the
26 GNU Lesser General Public License along with the Piranha library. If not,
27 see https://www.gnu.org/licenses/. */
28
29 #include "../src/small_vector.hpp"
30
31 #define BOOST_TEST_MODULE small_vector_01_test
32 #include <boost/test/included/unit_test.hpp>
33
34 #include <algorithm>
35 #include <boost/functional/hash.hpp>
36 #include <boost/mpl/for_each.hpp>
37 #include <boost/mpl/vector.hpp>
38 #include <cstddef>
39 #include <functional>
40 #include <initializer_list>
41 #include <iostream>
42 #include <iterator>
43 #include <memory>
44 #include <new>
45 #include <random>
46 #include <sstream>
47 #include <stdexcept>
48 #include <tuple>
49 #include <type_traits>
50 #include <vector>
51
52 #include "../src/detail/prepare_for_print.hpp"
53 #include "../src/exceptions.hpp"
54 #include "../src/init.hpp"
55 #include "../src/mp_integer.hpp"
56 #include "../src/mp_rational.hpp"
57 #include "../src/s11n.hpp"
58 #include "../src/safe_cast.hpp"
59
60 // NOTE: in these tests we are assuming a few things:
61 // - we can generally go a few elements beyond the numerical limits of sizes without wrapping over,
62 // - the static size will be less than the dynamic size,
63 // - we can interoperate safely with the size_type of std::vector.
64 // These seem pretty safe in any concievable situation, but just keep it in mind. Note that the implementation
65 // does not care about these assumptions, it's just the tests that do.
66
67 static const int ntries = 1000;
68 static std::mt19937 rng;
69
70 using namespace piranha;
71
72 typedef boost::mpl::vector<signed char, short, int, long, long long, integer, rational> value_types;
73 typedef boost::mpl::vector<std::integral_constant<std::size_t, 0u>, std::integral_constant<std::size_t, 1u>,
74 std::integral_constant<std::size_t, 5u>, std::integral_constant<std::size_t, 10u>>
75 size_types;
76
77 // Class that throws after a few copies.
78 struct time_bomb {
time_bombtime_bomb79 time_bomb() : m_vector(5)
80 {
81 }
82 time_bomb(time_bomb &&) = default;
time_bombtime_bomb83 time_bomb(const time_bomb &other) : m_vector(other.m_vector)
84 {
85 if (s_counter == 2u) {
86 throw std::runtime_error("ka-pow!");
87 }
88 ++s_counter;
89 }
operator =time_bomb90 time_bomb &operator=(time_bomb &&other) noexcept
91 {
92 m_vector = std::move(other.m_vector);
93 return *this;
94 }
~time_bombtime_bomb95 ~time_bomb() noexcept
96 {
97 }
98 std::vector<int> m_vector;
99 static unsigned s_counter;
100 };
101
102 unsigned time_bomb::s_counter = 0u;
103
104 struct dynamic_tester {
105 template <typename T>
operator ()dynamic_tester106 void operator()(const T &)
107 {
108 typedef detail::dynamic_storage<T> d1;
109 BOOST_CHECK(is_container_element<d1>::value);
110 d1 ds1;
111 BOOST_CHECK(ds1.begin() == ds1.end());
112 BOOST_CHECK(static_cast<const d1 &>(ds1).begin() == static_cast<const d1 &>(ds1).end());
113 BOOST_CHECK(static_cast<const d1 &>(ds1).begin() == ds1.end());
114 BOOST_CHECK(ds1.begin() == static_cast<const d1 &>(ds1).end());
115 BOOST_CHECK(ds1.empty());
116 BOOST_CHECK(ds1.size() == 0u);
117 BOOST_CHECK(ds1.capacity() == 0u);
118 d1 ds2(ds1);
119 BOOST_CHECK(ds2.size() == 0u);
120 BOOST_CHECK(ds2.capacity() == 0u);
121 ds1.push_back(T(0));
122 BOOST_CHECK(ds1[0u] == T(0));
123 BOOST_CHECK(ds1.capacity() == 1u);
124 BOOST_CHECK(ds1.size() == 1u);
125 BOOST_CHECK(!ds1.empty());
126 d1 ds3(ds1);
127 BOOST_CHECK(ds3[0u] == T(0));
128 BOOST_CHECK(ds3.capacity() == 1u);
129 BOOST_CHECK(ds3.size() == 1u);
130 d1 ds4(std::move(ds3));
131 BOOST_CHECK(ds4[0u] == T(0));
132 BOOST_CHECK(ds4.capacity() == 1u);
133 BOOST_CHECK(ds4.size() == 1u);
134 BOOST_CHECK(ds3.capacity() == 0u);
135 BOOST_CHECK(ds3.size() == 0u);
136 d1 ds5(ds2);
137 BOOST_CHECK(ds5.size() == 0u);
138 BOOST_CHECK(ds5.capacity() == 0u);
139 T tmp(1);
140 ds1.push_back(tmp);
141 BOOST_CHECK(ds1[1u] == T(1));
142 BOOST_CHECK(ds1.capacity() == 2u);
143 BOOST_CHECK(ds1.size() == 2u);
144 ds1.reserve(1u);
145 BOOST_CHECK(ds1[0u] == T(0));
146 BOOST_CHECK(ds1[1u] == T(1));
147 BOOST_CHECK(ds1.capacity() == 2u);
148 BOOST_CHECK(ds1.size() == 2u);
149 d1 ds6(std::move(ds1));
150 BOOST_CHECK(ds6[0u] == T(0));
151 BOOST_CHECK(ds6[1u] == T(1));
152 BOOST_CHECK(ds6.capacity() == 2u);
153 BOOST_CHECK(ds6.size() == 2u);
154 d1 ds7;
155 ds7.reserve(10u);
156 BOOST_CHECK(ds7.capacity() == 10u);
157 BOOST_CHECK(ds7.size() == 0u);
158 for (int i = 0; i < 11; ++i) {
159 ds7.push_back(T(i));
160 }
161 BOOST_CHECK(ds7.capacity() == 20u);
162 BOOST_CHECK(ds7.size() == 11u);
163 std::vector<T> tmp_vec = {T(0), T(1), T(2), T(3), T(4), T(5), T(6), T(7), T(8), T(9), T(10)};
164 BOOST_CHECK(std::equal(tmp_vec.begin(), tmp_vec.end(), ds7.begin()));
165 d1 ds8;
166 std::vector<T> tmp_vec2;
167 for (typename d1::size_type i = 0; i < d1::max_size; ++i) {
168 ds8.push_back(T(i));
169 tmp_vec2.push_back(T(i));
170 }
171 BOOST_CHECK(std::equal(ds8.begin(), ds8.end(), tmp_vec2.begin()));
172 BOOST_CHECK_THROW(ds8.push_back(T(0)), std::bad_alloc);
173 d1 ds9;
174 ds9.reserve(d1::max_size - 1u);
175 for (typename d1::size_type i = 0; i < d1::max_size; ++i) {
176 ds9.push_back(T(i));
177 }
178 BOOST_CHECK(std::equal(ds9.begin(), ds9.end(), ds8.begin()));
179 detail::dynamic_storage<time_bomb> ds10;
180 ds10.push_back(time_bomb{});
181 ds10.push_back(time_bomb{});
182 ds10.push_back(time_bomb{});
183 ds10.push_back(time_bomb{});
184 BOOST_CHECK_THROW((detail::dynamic_storage<time_bomb>{ds10}), std::runtime_error);
185 // Assignment.
186 d1 ds11, ds12;
187 ds11.push_back(T(42));
188 auto ptr1 = &ds11[0u];
189 ds11 = ds11;
190 ds11 = std::move(ds11);
191 BOOST_CHECK(ptr1 == &ds11[0u]);
192 BOOST_CHECK(ds11.size() == 1u);
193 BOOST_CHECK(ds11.capacity() == 1u);
194 BOOST_CHECK(ds11[0u] == T(42));
195 ds12 = std::move(ds11);
196 BOOST_CHECK(ds12.size() == 1u);
197 BOOST_CHECK(ds12.capacity() == 1u);
198 BOOST_CHECK(ds12[0u] == T(42));
199 BOOST_CHECK(ds11.size() == 0u);
200 BOOST_CHECK(ds11.capacity() == 0u);
201 // Revive with assignment.
202 ds11 = ds12;
203 BOOST_CHECK(ds11.size() == 1u);
204 BOOST_CHECK(ds11.capacity() == 1u);
205 BOOST_CHECK(ds11[0u] == T(42));
206 auto ds13 = std::move(ds11);
207 ds11 = std::move(ds13);
208 BOOST_CHECK(ds11.size() == 1u);
209 BOOST_CHECK(ds11.capacity() == 1u);
210 BOOST_CHECK(ds11[0u] == T(42));
211 ds11.push_back(T(43));
212 ds11.push_back(T(44));
213 ds11.push_back(T(45));
214 BOOST_CHECK(ds11.size() == 4u);
215 BOOST_CHECK(ds11.capacity() == 4u);
216 // Iterators tests.
217 auto it1 = ds11.begin();
218 std::advance(it1, 4);
219 BOOST_CHECK(it1 == ds11.end());
220 auto it2 = static_cast<d1 const &>(ds11).begin();
221 std::advance(it2, 4);
222 BOOST_CHECK(it2 == static_cast<d1 const &>(ds11).end());
223 BOOST_CHECK(ds11.begin() == &ds11[0u]);
224 // Some STL algos.
225 d1 ds14;
226 std::copy(tmp_vec.rbegin(), tmp_vec.rend(), std::back_inserter(ds14));
227 std::random_shuffle(ds14.begin(), ds14.end());
228 std::stable_sort(ds14.begin(), ds14.end());
229 BOOST_CHECK(*std::max_element(ds14.begin(), ds14.end()) == T(10));
230 BOOST_CHECK(*std::min_element(ds14.begin(), ds14.end()) == T(0));
231 BOOST_CHECK(std::equal(ds14.begin(), ds14.end(), tmp_vec.begin()));
232 // Capacity tests.
233 const auto orig_cap = ds14.capacity();
234 const auto orig_ptr = ds14[0u];
235 ds14.reserve(0u);
236 BOOST_CHECK(ds14.capacity() == orig_cap);
237 BOOST_CHECK(orig_ptr == ds14[0u]);
238 ds14.reserve(orig_cap);
239 BOOST_CHECK(ds14.capacity() == orig_cap);
240 BOOST_CHECK(orig_ptr == ds14[0u]);
241 // Hash.
242 d1 ds15;
243 BOOST_CHECK(ds15.hash() == 0u);
244 ds15.push_back(T(1));
245 BOOST_CHECK(ds15.hash() == std::hash<T>()(T(1)));
246 // Resizing.
247 auto ptr = &ds15[0u];
248 ds15.resize(1u);
249 BOOST_CHECK(ds15.size() == 1u);
250 BOOST_CHECK(ds15.capacity() == 1u);
251 BOOST_CHECK(&ds15[0u] == ptr);
252 ds15.resize(0u);
253 BOOST_CHECK(ds15.size() == 0u);
254 BOOST_CHECK(ds15.capacity() == 1u);
255 ds15.resize(0u);
256 BOOST_CHECK(ds15.size() == 0u);
257 BOOST_CHECK(ds15.capacity() == 1u);
258 ds15.resize(100u);
259 BOOST_CHECK(std::equal(ds15.begin(), ds15.end(), std::vector<T>(100u).begin()));
260 ds15.resize(200u);
261 BOOST_CHECK(std::equal(ds15.begin(), ds15.end(), std::vector<T>(200u).begin()));
262 ds15.resize(199u);
263 BOOST_CHECK(std::equal(ds15.begin(), ds15.end(), std::vector<T>(199u).begin()));
264 d1 ds16;
265 std::vector<T> cmp;
266 int n = 0;
267 std::generate_n(std::back_inserter(cmp), 100, [&n]() { return T(n++); });
268 n = 0;
269 std::generate_n(std::back_inserter(ds16), 100, [&n]() { return T(n++); });
270 BOOST_CHECK(std::equal(ds16.begin(), ds16.end(), cmp.begin()));
271 ptr = &ds16[0u];
272 ds16.resize(101);
273 BOOST_CHECK(ptr == &ds16[0u]);
274 cmp.resize(101);
275 BOOST_CHECK(std::equal(ds16.begin(), ds16.end(), cmp.begin()));
276 ds16.resize(100);
277 BOOST_CHECK(ptr == &ds16[0u]);
278 cmp.resize(100);
279 BOOST_CHECK(std::equal(ds16.begin(), ds16.end(), cmp.begin()));
280 auto old_cap = ds16.capacity();
281 ds16.resize(129);
282 cmp.resize(129);
283 BOOST_CHECK(std::equal(ds16.begin(), ds16.end(), cmp.begin()));
284 BOOST_CHECK(old_cap != ds16.capacity());
285 old_cap = ds16.capacity();
286 ptr = &ds16[0];
287 ds16.resize(1);
288 cmp.resize(1);
289 BOOST_CHECK(ptr == &ds16[0]);
290 BOOST_CHECK(cmp[0] == ds16[0]);
291 ds16.resize(1);
292 BOOST_CHECK(ptr == &ds16[0]);
293 ds16.resize(0);
294 BOOST_CHECK(old_cap == ds16.capacity());
295 {
296 // Erase testing.
297 typedef detail::dynamic_storage<T> vector_type;
298 vector_type v1;
299 v1.push_back(boost::lexical_cast<T>(1));
300 auto it = v1.erase(v1.begin());
301 BOOST_CHECK(v1.empty());
302 BOOST_CHECK(it == v1.end());
303 v1.push_back(boost::lexical_cast<T>(1));
304 v1.push_back(boost::lexical_cast<T>(2));
305 it = v1.erase(v1.begin());
306 BOOST_CHECK_EQUAL(v1.size(), 1u);
307 BOOST_CHECK(it == v1.begin());
308 BOOST_CHECK_EQUAL(v1[0u], boost::lexical_cast<T>(2));
309 it = v1.erase(v1.begin());
310 BOOST_CHECK(v1.empty());
311 BOOST_CHECK(it == v1.end());
312 v1.push_back(boost::lexical_cast<T>(1));
313 v1.push_back(boost::lexical_cast<T>(2));
314 it = v1.erase(v1.begin() + 1);
315 BOOST_CHECK_EQUAL(v1.size(), 1u);
316 BOOST_CHECK(it == v1.end());
317 BOOST_CHECK_EQUAL(v1[0u], boost::lexical_cast<T>(1));
318 it = v1.erase(v1.begin());
319 BOOST_CHECK(v1.empty());
320 BOOST_CHECK(it == v1.end());
321 v1.push_back(boost::lexical_cast<T>(1));
322 v1.push_back(boost::lexical_cast<T>(2));
323 v1.push_back(boost::lexical_cast<T>(3));
324 v1.push_back(boost::lexical_cast<T>(4));
325 it = v1.erase(v1.begin());
326 BOOST_CHECK_EQUAL(v1.size(), 3u);
327 BOOST_CHECK(it == v1.begin());
328 BOOST_CHECK_EQUAL(v1[0u], boost::lexical_cast<T>(2));
329 BOOST_CHECK_EQUAL(v1[1u], boost::lexical_cast<T>(3));
330 BOOST_CHECK_EQUAL(v1[2u], boost::lexical_cast<T>(4));
331 it = v1.erase(v1.begin() + 1);
332 BOOST_CHECK_EQUAL(v1.size(), 2u);
333 BOOST_CHECK(it == v1.begin() + 1);
334 BOOST_CHECK_EQUAL(v1[0u], boost::lexical_cast<T>(2));
335 BOOST_CHECK_EQUAL(v1[1u], boost::lexical_cast<T>(4));
336 it = v1.erase(v1.begin());
337 BOOST_CHECK_EQUAL(v1.size(), 1u);
338 BOOST_CHECK(it == v1.begin());
339 BOOST_CHECK_EQUAL(v1[0u], boost::lexical_cast<T>(4));
340 it = v1.erase(v1.begin());
341 BOOST_CHECK_EQUAL(v1.size(), 0u);
342 BOOST_CHECK(it == v1.end());
343 }
344 }
345 };
346
BOOST_AUTO_TEST_CASE(small_vector_dynamic_test)347 BOOST_AUTO_TEST_CASE(small_vector_dynamic_test)
348 {
349 init();
350 boost::mpl::for_each<value_types>(dynamic_tester());
351 }
352
353 struct constructor_tester {
354 template <typename T>
355 struct runner {
356 template <typename U>
operator ()constructor_tester::runner357 void operator()(const U &)
358 {
359 using v_type = small_vector<T, U>;
360 v_type v1;
361 BOOST_CHECK(v1.size() == 0u);
362 BOOST_CHECK(v1.begin() == v1.end());
363 BOOST_CHECK(static_cast<v_type const &>(v1).begin() == static_cast<v_type const &>(v1).end());
364 BOOST_CHECK(v1.begin() == static_cast<v_type const &>(v1).end());
365 BOOST_CHECK(static_cast<v_type const &>(v1).begin() == v1.end());
366 BOOST_CHECK(v1.is_static());
367 int n = 0;
368 std::generate_n(std::back_inserter(v1), safe_cast<int>(integer(v_type::max_static_size) * 8 + 3),
369 [&n]() { return T(n++); });
370 BOOST_CHECK(!v1.is_static());
371 v_type v2(v1);
372 BOOST_CHECK(!v2.is_static());
373 BOOST_CHECK(std::equal(v1.begin(), v1.end(), v2.begin()));
374 v_type v3(std::move(v2));
375 BOOST_CHECK(std::equal(v1.begin(), v1.end(), v3.begin()));
376 n = 0;
377 v_type v4;
378 std::generate_n(std::back_inserter(v4), safe_cast<int>(integer(v_type::max_static_size)),
379 [&n]() { return T(n++); });
380 BOOST_CHECK(v4.is_static());
381 v_type v5(v4);
382 BOOST_CHECK(v5.is_static());
383 BOOST_CHECK(std::equal(v4.begin(), v4.end(), v5.begin()));
384 v_type v6(std::move(v5));
385 BOOST_CHECK(std::equal(v4.begin(), v4.end(), v6.begin()));
386 // Constructor from size and value.
387 v_type v7(0, T(1));
388 BOOST_CHECK_EQUAL(v7.size(), 0u);
389 v_type v8(1u, T(42));
390 BOOST_CHECK_EQUAL(v8.size(), 1u);
391 BOOST_CHECK_EQUAL((*v8.begin()), T(42));
392 v_type v9(3u, T(42));
393 BOOST_CHECK_EQUAL(v9.size(), 3u);
394 BOOST_CHECK_EQUAL((*v9.begin()), T(42));
395 BOOST_CHECK_EQUAL(*(v9.begin() + 1), T(42));
396 BOOST_CHECK_EQUAL(*(v9.begin() + 2), T(42));
397 }
398 };
399 template <typename T>
operator ()constructor_tester400 void operator()(const T &)
401 {
402 boost::mpl::for_each<size_types>(runner<T>());
403 }
404 };
405
BOOST_AUTO_TEST_CASE(small_vector_constructor_test)406 BOOST_AUTO_TEST_CASE(small_vector_constructor_test)
407 {
408 boost::mpl::for_each<value_types>(constructor_tester());
409 }
410
411 struct assignment_tester {
412 template <typename T>
413 struct runner {
414 template <typename U>
operator ()assignment_tester::runner415 void operator()(const U &)
416 {
417 using v_type = small_vector<T, U>;
418 v_type v1;
419 v1.push_back(T(0));
420 auto *ptr = std::addressof(v1[0]);
421 // Verify that self assignment does not do anything funky.
422 v1 = v1;
423 v1 = std::move(v1);
424 BOOST_CHECK(ptr == std::addressof(v1[0]));
425 v_type v2;
426 // This will be static vs static (there is always enough static storage for at least 1 element).
427 v2 = v1;
428 BOOST_CHECK(v2.size() == 1u);
429 BOOST_CHECK(v2[0] == v1[0]);
430 // Push enough into v1 to make it dynamic.
431 int n = 0;
432 std::generate_n(std::back_inserter(v1), safe_cast<int>(integer(v_type::max_static_size)),
433 [&n]() { return T(n++); });
434 BOOST_CHECK(!v1.is_static());
435 BOOST_CHECK(v2.is_static());
436 // Static vs dynamic.
437 v2 = v1;
438 BOOST_CHECK(!v2.is_static());
439 BOOST_CHECK(std::equal(v2.begin(), v2.end(), v1.begin()));
440 v_type v3;
441 // Dynamic vs static.
442 v1 = v3;
443 BOOST_CHECK(v1.is_static());
444 BOOST_CHECK(v1.size() == 0u);
445 // Dynamic vs dynamic.
446 v_type v4(v2), v5(v2);
447 std::transform(v5.begin(), v5.end(), v5.begin(), [](const T &x) { return x / 2; });
448 v4 = v5;
449 BOOST_CHECK(std::equal(v4.begin(), v4.end(), v5.begin()));
450 v4 = std::move(v5);
451 BOOST_CHECK(v5.size() == 0u);
452 BOOST_CHECK(!v5.is_static());
453 }
454 };
455 template <typename T>
operator ()assignment_tester456 void operator()(const T &)
457 {
458 boost::mpl::for_each<size_types>(runner<T>());
459 }
460 };
461
BOOST_AUTO_TEST_CASE(small_vector_assignment_test)462 BOOST_AUTO_TEST_CASE(small_vector_assignment_test)
463 {
464 boost::mpl::for_each<value_types>(assignment_tester());
465 }
466
467 struct push_back_tester {
468 template <typename T>
469 struct runner {
470 template <typename U>
operator ()push_back_tester::runner471 void operator()(const U &)
472 {
473 using v_type = small_vector<T, U>;
474 v_type v1;
475 std::vector<T> check;
476 BOOST_CHECK(v1.size() == 0u);
477 for (typename std::decay<decltype(v_type::max_static_size)>::type i = 0u; i < v_type::max_static_size;
478 ++i) {
479 v1.push_back(T(i));
480 check.push_back(T(i));
481 }
482 v1.push_back(T(5));
483 check.push_back(T(5));
484 v1.push_back(T(6));
485 check.push_back(T(6));
486 v1.push_back(T(7));
487 check.push_back(T(7));
488 BOOST_CHECK(v1.size() == integer(v_type::max_static_size) + 3);
489 BOOST_CHECK(std::equal(check.begin(), check.end(), v1.begin()));
490 check.resize(0u);
491 v_type v2;
492 BOOST_CHECK(v2.size() == 0u);
493 T tmp;
494 for (typename std::decay<decltype(v_type::max_static_size)>::type i = 0u; i < v_type::max_static_size;
495 ++i) {
496 tmp = T(i);
497 check.push_back(tmp);
498 v2.push_back(tmp);
499 }
500 tmp = T(5);
501 v2.push_back(tmp);
502 check.push_back(tmp);
503 tmp = T(6);
504 v2.push_back(tmp);
505 check.push_back(tmp);
506 tmp = T(7);
507 v2.push_back(tmp);
508 check.push_back(tmp);
509 BOOST_CHECK(v2.size() == integer(v_type::max_static_size) + 3);
510 BOOST_CHECK(std::equal(check.begin(), check.end(), v2.begin()));
511 }
512 };
513 template <typename T>
operator ()push_back_tester514 void operator()(const T &)
515 {
516 boost::mpl::for_each<size_types>(runner<T>());
517 }
518 };
519
BOOST_AUTO_TEST_CASE(small_vector_push_back_test)520 BOOST_AUTO_TEST_CASE(small_vector_push_back_test)
521 {
522 boost::mpl::for_each<value_types>(push_back_tester());
523 }
524
525 struct equality_tester {
526 template <typename T>
527 struct runner {
528 template <typename U>
operator ()equality_tester::runner529 void operator()(const U &)
530 {
531 using v_type = small_vector<T, U>;
532 v_type v1;
533 BOOST_CHECK(v1 == v1);
534 BOOST_CHECK(!(v1 != v1));
535 v_type v2 = v1;
536 v1.push_back(T(0));
537 BOOST_CHECK(v2 != v1);
538 BOOST_CHECK(!(v2 == v1));
539 BOOST_CHECK(v1 != v2);
540 BOOST_CHECK(!(v1 == v2));
541 v2.push_back(T(0));
542 BOOST_CHECK(v2 == v1);
543 BOOST_CHECK(!(v2 != v1));
544 BOOST_CHECK(v1 == v2);
545 BOOST_CHECK(!(v1 != v2));
546 // Push enough into v1 to make it dynamic.
547 int n = 0;
548 std::generate_n(std::back_inserter(v1), safe_cast<int>(integer(v_type::max_static_size)),
549 [&n]() { return T(n++); });
550 BOOST_CHECK(v2 != v1);
551 BOOST_CHECK(!(v2 == v1));
552 BOOST_CHECK(v1 != v2);
553 BOOST_CHECK(!(v1 == v2));
554 v2 = v1;
555 BOOST_CHECK(v2 == v1);
556 BOOST_CHECK(!(v2 != v1));
557 BOOST_CHECK(v1 == v2);
558 BOOST_CHECK(!(v1 != v2));
559 v2.push_back(T(5));
560 BOOST_CHECK(v2 != v1);
561 BOOST_CHECK(!(v2 == v1));
562 BOOST_CHECK(v1 != v2);
563 BOOST_CHECK(!(v1 == v2));
564 }
565 };
566 template <typename T>
operator ()equality_tester567 void operator()(const T &)
568 {
569 boost::mpl::for_each<size_types>(runner<T>());
570 }
571 };
572
BOOST_AUTO_TEST_CASE(small_vector_equality_test)573 BOOST_AUTO_TEST_CASE(small_vector_equality_test)
574 {
575 boost::mpl::for_each<value_types>(equality_tester());
576 }
577
578 struct hash_tester {
579 template <typename T>
580 struct runner {
581 template <typename U>
operator ()hash_tester::runner582 void operator()(const U &)
583 {
584 using v_type = small_vector<T, U>;
585 v_type v1;
586 BOOST_CHECK(v1.hash() == 0u);
587 v1.push_back(T(2));
588 BOOST_CHECK(v1.hash() == std::hash<T>()(T(2)));
589 // Push enough into v1 to make it dynamic.
590 int n = 0;
591 std::generate_n(std::back_inserter(v1), safe_cast<int>(integer(v_type::max_static_size)),
592 [&n]() { return T(n++); });
593 std::hash<T> hasher;
594 std::size_t retval = hasher(v1[0u]);
595 for (decltype(v1.size()) i = 1u; i < v1.size(); ++i) {
596 boost::hash_combine(retval, hasher(v1[i]));
597 }
598 BOOST_CHECK(retval == v1.hash());
599 }
600 };
601 template <typename T>
operator ()hash_tester602 void operator()(const T &)
603 {
604 boost::mpl::for_each<size_types>(runner<T>());
605 }
606 };
607
BOOST_AUTO_TEST_CASE(small_vector_hash_test)608 BOOST_AUTO_TEST_CASE(small_vector_hash_test)
609 {
610 boost::mpl::for_each<value_types>(hash_tester());
611 }
612
613 struct resize_tester {
614 template <typename T>
615 struct runner {
616 template <typename U>
operator ()resize_tester::runner617 void operator()(const U &)
618 {
619 using v_type = small_vector<T, U>;
620 v_type v1;
621 v1.resize(0);
622 BOOST_CHECK(v1.size() == 0u);
623 v1.resize(1);
624 BOOST_CHECK(v1.size() == 1u);
625 BOOST_CHECK(v1[0] == T());
626 auto ptr = &v1[0];
627 v1.resize(v_type::max_static_size);
628 std::vector<T> cmp;
629 cmp.resize(v_type::max_static_size);
630 BOOST_CHECK(ptr == &v1[0]);
631 BOOST_CHECK(std::equal(v1.begin(), v1.end(), cmp.begin()));
632 v1.resize(v_type::max_static_size + 1u);
633 cmp.resize(v_type::max_static_size + 1u);
634 BOOST_CHECK(ptr != &v1[0]);
635 BOOST_CHECK(std::equal(v1.begin(), v1.end(), cmp.begin()));
636 v1.resize(v_type::max_static_size + 2u);
637 cmp.resize(v_type::max_static_size + 2u);
638 ptr = &v1[0];
639 BOOST_CHECK(std::equal(v1.begin(), v1.end(), cmp.begin()));
640 v1.resize(0);
641 BOOST_CHECK(v1.size() == 0u);
642 v1.resize(1);
643 BOOST_CHECK(ptr == &v1[0]);
644 }
645 };
646 template <typename T>
operator ()resize_tester647 void operator()(const T &)
648 {
649 boost::mpl::for_each<size_types>(runner<T>());
650 }
651 };
652
BOOST_AUTO_TEST_CASE(small_vector_resize_test)653 BOOST_AUTO_TEST_CASE(small_vector_resize_test)
654 {
655 boost::mpl::for_each<value_types>(resize_tester());
656 }
657
658 // Class that throws after a few constructions.
659 struct time_bomb2 {
time_bomb2time_bomb2660 time_bomb2() : m_vector(5)
661 {
662 }
663 time_bomb2(time_bomb2 &&) = default;
664 time_bomb2(const time_bomb2 &) = default;
time_bomb2time_bomb2665 time_bomb2(int)
666 {
667 if (s_counter == 4u) {
668 throw std::runtime_error("ka-pow!");
669 }
670 ++s_counter;
671 }
operator =time_bomb2672 time_bomb2 &operator=(time_bomb2 &&other) noexcept
673 {
674 m_vector = std::move(other.m_vector);
675 return *this;
676 }
~time_bomb2time_bomb2677 ~time_bomb2() noexcept
678 {
679 }
680 std::vector<int> m_vector;
681 static unsigned s_counter;
682 };
683
684 namespace piranha
685 {
686
687 template <>
688 struct safe_cast_impl<time_bomb2, int, void> {
operator ()piranha::safe_cast_impl689 time_bomb2 operator()(int n) const
690 {
691 try {
692 return time_bomb2(n);
693 } catch (...) {
694 piranha_throw(safe_cast_failure, "noooo");
695 }
696 }
697 };
698 }
699
700 unsigned time_bomb2::s_counter = 0u;
701
702 struct init_list_tester {
703 template <typename T>
704 struct runner {
705 template <typename U>
operator ()init_list_tester::runner706 void operator()(const U &)
707 {
708 using v_type = small_vector<T, U>;
709 v_type v1({1});
710 BOOST_CHECK(v1[0] == T(1));
711 v_type v2({1, 2, 3});
712 BOOST_CHECK(v2[0] == T(1));
713 BOOST_CHECK(v2[1] == T(2));
714 BOOST_CHECK(v2[2] == T(3));
715 v_type v3({1, 2, 3, 4, 5, 6, 7, 8, 9, 0});
716 std::vector<int> cmp({1, 2, 3, 4, 5, 6, 7, 8, 9, 0});
717 BOOST_CHECK(v3.size() == cmp.size());
718 BOOST_CHECK(std::equal(v3.begin(), v3.end(), cmp.begin()));
719 BOOST_CHECK((std::is_constructible<v_type, std::initializer_list<int>>::value));
720 BOOST_CHECK((!std::is_constructible<v_type, std::initializer_list<time_bomb2>>::value));
721 using v_type2 = small_vector<time_bomb2, U>;
722 time_bomb2::s_counter = 0u;
723 BOOST_CHECK_THROW(v_type2({1, 2, 3, 4, 5, 6, 7}), std::invalid_argument);
724 }
725 };
726 template <typename T>
operator ()init_list_tester727 void operator()(const T &)
728 {
729 boost::mpl::for_each<size_types>(runner<T>());
730 }
731 };
732
BOOST_AUTO_TEST_CASE(small_vector_init_list_test)733 BOOST_AUTO_TEST_CASE(small_vector_init_list_test)
734 {
735 boost::mpl::for_each<value_types>(init_list_tester());
736 }
737
738 struct add_tester {
739 template <typename T>
740 struct runner {
741 template <typename U>
operator ()add_tester::runner742 void operator()(const U &)
743 {
744 using v_type = small_vector<T, U>;
745 v_type v1, v2, v3;
746 v1.add(v3, v2);
747 BOOST_CHECK(v3.size() == 0u);
748 v1.push_back(T(1));
749 BOOST_CHECK_THROW(v1.add(v3, v2), std::invalid_argument);
750 BOOST_CHECK(v1.size() == 1u);
751 BOOST_CHECK_EQUAL(*v1.begin(), T(1));
752 v2.push_back(T(2));
753 v1.add(v3, v2);
754 BOOST_CHECK(v3.size() == 1u);
755 BOOST_CHECK(v3[0] == T(3));
756 v1 = v_type{1, 2, 3, 4, 5, 6};
757 v2 = v_type{7, 8, 9, 0, 1, 2};
758 v1.add(v3, v2);
759 BOOST_CHECK((v3 == v_type{8, 10, 12, 4, 6, 8}));
760 v3.resize(0);
761 v1.add(v3, v2);
762 BOOST_CHECK((v3 == v_type{8, 10, 12, 4, 6, 8}));
763 v3.resize(100);
764 v1.add(v3, v2);
765 BOOST_CHECK((v3 == v_type{8, 10, 12, 4, 6, 8}));
766 v3.add(v3, v3);
767 BOOST_CHECK((v3 == v_type{8 * 2, 10 * 2, 12 * 2, 4 * 2, 6 * 2, 8 * 2}));
768 v3.add(v3, v2);
769 BOOST_CHECK((v3 == v_type{8 * 2 + 7, 10 * 2 + 8, 12 * 2 + 9, 4 * 2, 6 * 2 + 1, 8 * 2 + 2}));
770 }
771 };
772 template <typename T>
operator ()add_tester773 void operator()(const T &)
774 {
775 boost::mpl::for_each<size_types>(runner<T>());
776 }
777 };
778
BOOST_AUTO_TEST_CASE(small_vector_add_test)779 BOOST_AUTO_TEST_CASE(small_vector_add_test)
780 {
781 boost::mpl::for_each<value_types>(add_tester());
782 }
783
784 struct sub_tester {
785 template <typename T>
786 struct runner {
787 template <typename U>
operator ()sub_tester::runner788 void operator()(const U &)
789 {
790 using v_type = small_vector<T, U>;
791 v_type v1, v2, v3;
792 v1.sub(v3, v2);
793 BOOST_CHECK(v3.size() == 0u);
794 v1.push_back(T(1));
795 BOOST_CHECK_THROW(v1.sub(v3, v2), std::invalid_argument);
796 BOOST_CHECK(v1.size() == 1u);
797 BOOST_CHECK_EQUAL(*v1.begin(), T(1));
798 v2.push_back(T(2));
799 v1.sub(v3, v2);
800 BOOST_CHECK(v3.size() == 1u);
801 BOOST_CHECK(v3[0] == T(-1));
802 v1 = v_type{1, 2, 3, 4, 5, 6};
803 v2 = v_type{7, 8, 9, 0, 1, 2};
804 v1.sub(v3, v2);
805 BOOST_CHECK((v3 == v_type{-6, -6, -6, 4, 4, 4}));
806 v3.resize(0);
807 v1.sub(v3, v2);
808 BOOST_CHECK((v3 == v_type{-6, -6, -6, 4, 4, 4}));
809 v3.resize(100);
810 v1.sub(v3, v2);
811 BOOST_CHECK((v3 == v_type{-6, -6, -6, 4, 4, 4}));
812 v3.sub(v3, v3);
813 BOOST_CHECK((v3 == v_type{0, 0, 0, 0, 0, 0}));
814 v3.sub(v3, v2);
815 BOOST_CHECK((v3 == v_type{-7, -8, -9, 0, -1, -2}));
816 }
817 };
818 template <typename T>
operator ()sub_tester819 void operator()(const T &)
820 {
821 boost::mpl::for_each<size_types>(runner<T>());
822 }
823 };
824
BOOST_AUTO_TEST_CASE(small_vector_sub_test)825 BOOST_AUTO_TEST_CASE(small_vector_sub_test)
826 {
827 boost::mpl::for_each<value_types>(sub_tester());
828 }
829
BOOST_AUTO_TEST_CASE(small_vector_print_sizes)830 BOOST_AUTO_TEST_CASE(small_vector_print_sizes)
831 {
832 std::cout << "Signed char: " << sizeof(small_vector<signed char>) << ','
833 << detail::prepare_for_print(small_vector<signed char>::max_static_size) << ','
834 << detail::prepare_for_print(small_vector<signed char>::max_dynamic_size) << ','
835 << alignof(small_vector<signed char>) << '\n';
836 std::cout << "Short : " << sizeof(small_vector<short>) << ','
837 << detail::prepare_for_print(small_vector<short>::max_static_size) << ','
838 << detail::prepare_for_print(small_vector<short>::max_dynamic_size) << ',' << alignof(small_vector<short>)
839 << '\n';
840 std::cout << "Int : " << sizeof(small_vector<int>) << ','
841 << detail::prepare_for_print(small_vector<int>::max_static_size) << ','
842 << detail::prepare_for_print(small_vector<int>::max_dynamic_size) << ',' << alignof(small_vector<int>)
843 << '\n';
844 std::cout << "Long : " << sizeof(small_vector<long>) << ','
845 << detail::prepare_for_print(small_vector<long>::max_static_size) << ','
846 << detail::prepare_for_print(small_vector<long>::max_dynamic_size) << ',' << alignof(small_vector<long>)
847 << '\n';
848 std::cout << "Long long : " << sizeof(small_vector<long long>) << ','
849 << detail::prepare_for_print(small_vector<long long>::max_static_size) << ','
850 << detail::prepare_for_print(small_vector<long long>::max_dynamic_size) << ','
851 << alignof(small_vector<long long>) << '\n';
852 }
853
854 struct move_tester {
855 template <typename T>
856 struct runner {
857 template <typename U>
operator ()move_tester::runner858 void operator()(const U &)
859 {
860 using v_type = small_vector<T, U>;
861 v_type v1;
862 v1.push_back(T(1));
863 v_type v2(std::move(v1));
864 BOOST_CHECK_EQUAL(v2.size(), 1u);
865 BOOST_CHECK_EQUAL(v2[0u], T(1));
866 BOOST_CHECK_EQUAL(v1.size(), 0u);
867 BOOST_CHECK(v1.begin() == v1.end());
868 BOOST_CHECK(v1.is_static());
869 BOOST_CHECK(v2.is_static());
870 v1 = std::move(v2);
871 BOOST_CHECK_EQUAL(v1.size(), 1u);
872 BOOST_CHECK_EQUAL(v1[0u], T(1));
873 BOOST_CHECK_EQUAL(v2.size(), 0u);
874 BOOST_CHECK(v2.begin() == v2.end());
875 BOOST_CHECK(v2.is_static());
876 BOOST_CHECK(v1.is_static());
877 v1 = v_type();
878 int n = 0;
879 std::generate_n(std::back_inserter(v1), safe_cast<int>(integer(v_type::max_static_size) + 1),
880 [&n]() { return T(n++); });
881 BOOST_CHECK(!v1.is_static());
882 v_type v3(std::move(v1));
883 BOOST_CHECK_EQUAL(integer(v3.size()), integer(v_type::max_static_size) + 1);
884 BOOST_CHECK_EQUAL(v1.size(), 0u);
885 BOOST_CHECK(v1.begin() == v1.end());
886 BOOST_CHECK(!v1.is_static());
887 BOOST_CHECK(!v3.is_static());
888 v1 = std::move(v3);
889 BOOST_CHECK_EQUAL(integer(v1.size()), integer(v_type::max_static_size) + 1);
890 BOOST_CHECK_EQUAL(v3.size(), 0u);
891 BOOST_CHECK(v3.begin() == v3.end());
892 BOOST_CHECK(!v3.is_static());
893 BOOST_CHECK(!v1.is_static());
894 }
895 };
896 template <typename T>
operator ()move_tester897 void operator()(const T &)
898 {
899 boost::mpl::for_each<size_types>(runner<T>());
900 }
901 };
902
BOOST_AUTO_TEST_CASE(small_vector_move_test)903 BOOST_AUTO_TEST_CASE(small_vector_move_test)
904 {
905 boost::mpl::for_each<value_types>(move_tester());
906 }
907
908 struct serialization_tester {
909 template <typename T>
operator ()serialization_tester910 void operator()(const T &)
911 {
912 using v_type = small_vector<int, T>;
913 using size_type = typename v_type::size_type;
914 std::uniform_int_distribution<int> int_dist(std::numeric_limits<int>::min(), std::numeric_limits<int>::max());
915 std::uniform_int_distribution<size_type> size_dist(0u, 10u);
916 v_type tmp;
917 for (int i = 0; i < ntries; ++i) {
918 // Create a vector of random size and with random contents.
919 v_type v;
920 const auto size = size_dist(rng);
921 for (size_type j = 0u; j < size; ++j) {
922 v.push_back(int_dist(rng));
923 }
924 // Serialize it.
925 std::stringstream ss;
926 {
927 boost::archive::text_oarchive oa(ss);
928 oa << v;
929 }
930 {
931 boost::archive::text_iarchive ia(ss);
932 ia >> tmp;
933 }
934 BOOST_CHECK(tmp == v);
935 }
936 // Try with integer.
937 using v_type2 = small_vector<integer, T>;
938 v_type2 tmp2;
939 for (int i = 0; i < ntries; ++i) {
940 v_type2 v;
941 const auto size = size_dist(rng);
942 for (size_type j = 0u; j < size; ++j) {
943 v.push_back(integer(int_dist(rng)));
944 }
945 // Serialize it.
946 std::stringstream ss;
947 {
948 boost::archive::text_oarchive oa(ss);
949 oa << v;
950 }
951 {
952 boost::archive::text_iarchive ia(ss);
953 ia >> tmp2;
954 }
955 BOOST_CHECK(tmp2 == v);
956 }
957 }
958 };
959
BOOST_AUTO_TEST_CASE(small_vector_serialization_test)960 BOOST_AUTO_TEST_CASE(small_vector_serialization_test)
961 {
962 boost::mpl::for_each<size_types>(serialization_tester());
963 }
964
965 struct empty_tester {
966 template <typename T>
967 struct runner {
968 template <typename U>
operator ()empty_tester::runner969 void operator()(const U &)
970 {
971 using v_type = small_vector<T, U>;
972 v_type v1;
973 BOOST_CHECK(v1.empty());
974 BOOST_CHECK(v1.is_static());
975 v1.push_back(T(1));
976 BOOST_CHECK(!v1.empty());
977 BOOST_CHECK(v1.is_static());
978 int n = 0;
979 std::generate_n(std::back_inserter(v1), safe_cast<int>(integer(v_type::max_static_size) + 1),
980 [&n]() { return T(n++); });
981 BOOST_CHECK(!v1.is_static());
982 BOOST_CHECK(!v1.empty());
983 v1.resize(0u);
984 BOOST_CHECK(!v1.is_static());
985 BOOST_CHECK(v1.empty());
986 }
987 };
988 template <typename T>
operator ()empty_tester989 void operator()(const T &)
990 {
991 boost::mpl::for_each<size_types>(runner<T>());
992 }
993 };
994
BOOST_AUTO_TEST_CASE(small_vector_empty_test)995 BOOST_AUTO_TEST_CASE(small_vector_empty_test)
996 {
997 boost::mpl::for_each<value_types>(empty_tester());
998 }
999
1000 struct erase_tester {
1001 template <typename T>
1002 struct runner {
1003 template <typename U>
operator ()erase_tester::runner1004 void operator()(const U &)
1005 {
1006 if (U::value < 2u) {
1007 return;
1008 }
1009 using v_type = small_vector<T, U>;
1010 v_type v1;
1011 BOOST_CHECK(v1.empty());
1012 BOOST_CHECK(v1.is_static());
1013 v1.push_back(T(1));
1014 auto it = v1.erase(v1.begin());
1015 BOOST_CHECK(it == v1.end());
1016 BOOST_CHECK(v1.empty());
1017 BOOST_CHECK(v1.is_static());
1018 int n = 0;
1019 std::generate_n(std::back_inserter(v1), safe_cast<int>(integer(v_type::max_static_size) + 1),
1020 [&n]() { return T(n++); });
1021 BOOST_CHECK(!v1.is_static());
1022 BOOST_CHECK(!v1.empty());
1023 it = v1.erase(v1.begin());
1024 BOOST_CHECK(!v1.is_static());
1025 BOOST_CHECK(!v1.empty());
1026 BOOST_CHECK(it != v1.end());
1027 BOOST_CHECK_EQUAL(*it, integer(1));
1028 BOOST_CHECK_EQUAL(v1.size(), integer(v_type::max_static_size));
1029 it = v1.erase(v1.end() - 1);
1030 BOOST_CHECK(!v1.is_static());
1031 BOOST_CHECK(!v1.empty());
1032 BOOST_CHECK_EQUAL(v1.size(), integer(v_type::max_static_size) - 1);
1033 BOOST_CHECK(it == v1.end());
1034 }
1035 };
1036 template <typename T>
operator ()erase_tester1037 void operator()(const T &)
1038 {
1039 boost::mpl::for_each<size_types>(runner<T>());
1040 }
1041 };
1042
BOOST_AUTO_TEST_CASE(small_vector_erase_test)1043 BOOST_AUTO_TEST_CASE(small_vector_erase_test)
1044 {
1045 boost::mpl::for_each<value_types>(erase_tester());
1046 }
1047
1048 struct size_be_tester {
1049 template <typename T>
1050 struct runner {
1051 template <typename U>
operator ()size_be_tester::runner1052 void operator()(const U &)
1053 {
1054 if (U::value < 2u) {
1055 return;
1056 }
1057 using v_type = small_vector<T, U>;
1058 v_type v1;
1059 BOOST_CHECK(v1.empty());
1060 BOOST_CHECK(v1.is_static());
1061 auto t0 = v1.size_begin_end();
1062 BOOST_CHECK_EQUAL(std::get<0>(t0), 0u);
1063 BOOST_CHECK(std::get<1>(t0) == std::get<2>(t0));
1064 BOOST_CHECK(std::get<1>(t0) == v1.begin());
1065 BOOST_CHECK(std::get<2>(t0) == v1.end());
1066 // Check the const counterpart too.
1067 auto t1 = static_cast<const v_type &>(v1).size_begin_end();
1068 BOOST_CHECK_EQUAL(std::get<0>(t1), 0u);
1069 BOOST_CHECK(std::get<1>(t1) == std::get<2>(t1));
1070 BOOST_CHECK(std::get<1>(t1) == static_cast<const v_type &>(v1).begin());
1071 BOOST_CHECK(std::get<2>(t1) == static_cast<const v_type &>(v1).end());
1072 // Switch to dynamic.
1073 int n = 0;
1074 std::generate_n(std::back_inserter(v1), safe_cast<int>(integer(v_type::max_static_size) + 1),
1075 [&n]() { return T(n++); });
1076 t0 = v1.size_begin_end();
1077 BOOST_CHECK_EQUAL(std::get<0>(t0), integer(v_type::max_static_size) + 1);
1078 BOOST_CHECK(std::get<1>(t0) == v1.begin());
1079 BOOST_CHECK(std::get<2>(t0) == v1.end());
1080 // Check again const.
1081 t1 = static_cast<const v_type &>(v1).size_begin_end();
1082 BOOST_CHECK_EQUAL(std::get<0>(t1), integer(v_type::max_static_size) + 1);
1083 BOOST_CHECK(std::get<1>(t1) == static_cast<const v_type &>(v1).begin());
1084 BOOST_CHECK(std::get<2>(t1) == static_cast<const v_type &>(v1).end());
1085 // Resize back to zero.
1086 v1.resize(0u);
1087 t0 = v1.size_begin_end();
1088 BOOST_CHECK_EQUAL(std::get<0>(t0), 0u);
1089 BOOST_CHECK(std::get<1>(t0) == std::get<2>(t0));
1090 BOOST_CHECK(std::get<1>(t0) == v1.begin());
1091 BOOST_CHECK(std::get<2>(t0) == v1.end());
1092 t1 = static_cast<const v_type &>(v1).size_begin_end();
1093 BOOST_CHECK_EQUAL(std::get<0>(t1), 0u);
1094 BOOST_CHECK(std::get<1>(t1) == std::get<2>(t1));
1095 BOOST_CHECK(std::get<1>(t1) == static_cast<const v_type &>(v1).begin());
1096 BOOST_CHECK(std::get<2>(t1) == static_cast<const v_type &>(v1).end());
1097 }
1098 };
1099 template <typename T>
operator ()size_be_tester1100 void operator()(const T &)
1101 {
1102 boost::mpl::for_each<size_types>(runner<T>());
1103 }
1104 };
1105
BOOST_AUTO_TEST_CASE(small_vector_size_begin_end_test)1106 BOOST_AUTO_TEST_CASE(small_vector_size_begin_end_test)
1107 {
1108 boost::mpl::for_each<value_types>(size_be_tester());
1109 }
1110