1 | /* Boost.MultiIndex test for standard hash operations. |
---|---|
2 | * |
3 | * Copyright 2003-2013 Joaquin M Lopez Munoz. |
4 | * Distributed under the Boost Software License, Version 1.0. |
5 | * (See accompanying file LICENSE_1_0.txt or copy at |
6 | * http://www.boost.org/LICENSE_1_0.txt) |
7 | * |
8 | * See http://www.boost.org/libs/multi_index for library home page. |
9 | */ |
10 | |
11 | #include "test_hash_ops.hpp" |
12 | |
13 | #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */ |
14 | #include <iterator> |
15 | #include <boost/detail/lightweight_test.hpp> |
16 | #include "pre_multi_index.hpp" |
17 | #include <boost/multi_index_container.hpp> |
18 | #include <boost/multi_index/hashed_index.hpp> |
19 | #include <boost/multi_index/identity.hpp> |
20 | #include <vector> |
21 | |
22 | #include <iostream> |
23 | |
24 | using namespace boost::multi_index; |
25 | |
26 | template<typename HashedContainer> |
27 | void check_load_factor(const HashedContainer& hc) |
28 | { |
29 | float lf=(float)hc.size()/hc.bucket_count(); |
30 | BOOST_TEST(lf<=hc.load_factor()+1.E-6); |
31 | BOOST_TEST(lf>=hc.load_factor()-1.E-6); |
32 | BOOST_TEST(lf<=hc.max_load_factor()+1.E-6); |
33 | } |
34 | |
35 | typedef multi_index_container< |
36 | int, |
37 | indexed_by< |
38 | hashed_unique<identity<int> > |
39 | > |
40 | > hash_container; |
41 | |
42 | void test_hash_ops() |
43 | { |
44 | hash_container hc; |
45 | |
46 | BOOST_TEST(hc.max_load_factor()==1.0f); |
47 | BOOST_TEST(hc.bucket_count()<=hc.max_bucket_count()); |
48 | |
49 | hc.insert(x: 1000); |
50 | hash_container::size_type buc=hc.bucket(k: 1000); |
51 | hash_container::local_iterator it0=hc.begin(n: buc); |
52 | hash_container::local_iterator it1=hc.end(n: buc); |
53 | BOOST_TEST( |
54 | (hash_container::size_type)std::distance(it0,it1)==hc.bucket_size(buc)&& |
55 | hc.bucket_size(buc)==1&&*it0==1000); |
56 | |
57 | hc.clear(); |
58 | |
59 | for(hash_container::size_type s=2*hc.bucket_count();s--;){ |
60 | hc.insert(x: (int)s); |
61 | } |
62 | check_load_factor(hc); |
63 | |
64 | hc.max_load_factor(z: 0.5f); |
65 | BOOST_TEST(hc.max_load_factor()==0.5f); |
66 | hc.insert(x: -1); |
67 | check_load_factor(hc); |
68 | |
69 | hc.rehash(n: 1); |
70 | BOOST_TEST(hc.bucket_count()>=1); |
71 | check_load_factor(hc); |
72 | |
73 | hc.max_load_factor(z: 0.25f); |
74 | hc.rehash(n: 1); |
75 | BOOST_TEST(hc.bucket_count()>=1); |
76 | check_load_factor(hc); |
77 | |
78 | hash_container::size_type bc=4*hc.bucket_count(); |
79 | hc.max_load_factor(z: 0.125f); |
80 | hc.rehash(n: bc); |
81 | BOOST_TEST(hc.bucket_count()>=bc); |
82 | check_load_factor(hc); |
83 | |
84 | bc=2*hc.bucket_count(); |
85 | hc.rehash(n: bc); |
86 | BOOST_TEST(hc.bucket_count()>=bc); |
87 | check_load_factor(hc); |
88 | |
89 | hc.clear(); |
90 | hc.insert(x: 0); |
91 | hc.rehash(n: 1); |
92 | BOOST_TEST(hc.bucket_count()>=1); |
93 | check_load_factor(hc); |
94 | |
95 | hash_container hc2; |
96 | hc2.insert(x: 0); |
97 | hc2.max_load_factor(z: 0.5f/hc2.bucket_count()); |
98 | BOOST_TEST(hc2.load_factor()>hc2.max_load_factor()); |
99 | hc2.reserve(n: 1); |
100 | BOOST_TEST(hc2.load_factor()<hc2.max_load_factor()); |
101 | |
102 | hash_container hc3; |
103 | hc3.clear(); |
104 | hc3.max_load_factor(z: 1.0f); |
105 | hc3.reserve(n: 1000); |
106 | hash_container::size_type bc3=hc3.bucket_count(); |
107 | BOOST_TEST(bc3>=1000); |
108 | std::vector<int> v; |
109 | for(unsigned int n=0;n<bc3;++n)v.push_back(x: n); |
110 | hc3.insert(first: v.begin(),last: v.end()); |
111 | BOOST_TEST(hc3.bucket_count()==bc3); /* LWG issue 2156 */ |
112 | hc3.max_load_factor(z: 0.25f); |
113 | hc3.reserve(n: 100); |
114 | BOOST_TEST(hc3.bucket_count()>bc3); |
115 | bc3=hc3.bucket_count(); |
116 | hc3.reserve(n: (hash_container::size_type)(3.0f*hc3.max_load_factor()*bc3)); |
117 | BOOST_TEST(hc3.bucket_count()>bc3); |
118 | } |
119 |