1 
2 // Copyright 2017 Daniel James.
3 // Distributed under the Boost Software License, Version 1.0. (See accompanying
4 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
5 
6 // clang-format off
7 #include "../helpers/prefix.hpp"
8 #include <boost/unordered_map.hpp>
9 #include <boost/unordered_set.hpp>
10 #include "../helpers/postfix.hpp"
11 // clang-format on
12 
13 #include "../helpers/test.hpp"
14 #include <map>
15 
16 // Pretty inefficient, but the test is fast enough.
17 // Might be too slow if we had larger primes?
is_prime(std::size_t x)18 bool is_prime(std::size_t x)
19 {
20   if (x == 2) {
21     return true;
22   } else if (x == 1 || x % 2 == 0) {
23     return false;
24   } else {
25     // y*y <= x had rounding errors, so instead use y <= (x/y).
26     for (std::size_t y = 3; y <= (x / y); y += 2) {
27       if (x % y == 0) {
28         return false;
29         break;
30       }
31     }
32 
33     return true;
34   }
35 }
36 
test_next_prime(std::size_t value)37 void test_next_prime(std::size_t value)
38 {
39   std::size_t x = boost::unordered::detail::next_prime(value);
40   BOOST_TEST(is_prime(x));
41   BOOST_TEST(x >= value);
42 }
43 
test_prev_prime(std::size_t value)44 void test_prev_prime(std::size_t value)
45 {
46   std::size_t x = boost::unordered::detail::prev_prime(value);
47   BOOST_TEST(is_prime(x));
48   BOOST_TEST(x <= value);
49   if (x > value) {
50     BOOST_LIGHTWEIGHT_TEST_OSTREAM << x << "," << value << std::endl;
51   }
52 }
53 
UNORDERED_AUTO_TEST(next_prime_test)54 UNORDERED_AUTO_TEST (next_prime_test) {
55   BOOST_TEST(!is_prime(0));
56   BOOST_TEST(!is_prime(1));
57   BOOST_TEST(is_prime(2));
58   BOOST_TEST(is_prime(3));
59   BOOST_TEST(is_prime(13));
60   BOOST_TEST(!is_prime(4));
61   BOOST_TEST(!is_prime(100));
62 
63   BOOST_TEST(boost::unordered::detail::next_prime(0) > 0);
64 
65   // test_prev_prime doesn't work for values less than 17.
66   // Which should be okay, unless an allocator has a really tiny
67   // max_size?
68   const std::size_t min_prime = 17;
69 
70   // test_next_prime doesn't work for values greater than this,
71   // which might be a problem if you've got terrabytes of memory?
72   // I seriously doubt the container would work well at such sizes
73   // regardless.
74   const std::size_t max_prime = 4294967291ul;
75 
76   std::size_t i;
77 
78   BOOST_TEST(is_prime(min_prime));
79   BOOST_TEST(is_prime(max_prime));
80 
81   for (i = 0; i < 10000; ++i) {
82     if (i < min_prime) {
83       BOOST_TEST(boost::unordered::detail::prev_prime(i) == min_prime);
84     } else {
85       test_prev_prime(i);
86     }
87     test_next_prime(i);
88   }
89 
90   std::size_t last = i - 1;
91   for (; i > last; last = i, i += i / 5) {
92     if (i > max_prime) {
93       BOOST_TEST(boost::unordered::detail::next_prime(i) == max_prime);
94     } else {
95       test_next_prime(i);
96     }
97     test_prev_prime(i);
98   }
99 }
100 
101 RUN_TESTS()
102