1 /////////////////////////////////////////////////////////////////////////////
2 //
3 // (C) Copyright Ion Gaztanaga 2007-2013
4 //
5 // Distributed under the Boost Software License, Version 1.0.
6 // (See accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
8 //
9 // See http://www.boost.org/libs/intrusive for documentation.
10 //
11 /////////////////////////////////////////////////////////////////////////////
12
13 //Includes for tests
14 #include <boost/intrusive/detail/config_begin.hpp>
15 #include <boost/config.hpp>
16 #include <iostream>
17 #include <vector>
18 #include <boost/intrusive/set.hpp>
19 #include <boost/intrusive/sg_set.hpp>
20 #include <boost/intrusive/avl_set.hpp>
21 #include <boost/date_time/posix_time/posix_time.hpp>
22 #include <cstdlib>
23
24 using namespace boost::posix_time;
25 using namespace boost::intrusive;
26
27 template<bool BigSize> struct filler { int dummy[10]; };
28 template <> struct filler<false> {};
29
30 template<bool BigSize> //The object for non-intrusive containers
31 struct test_class : private filler<BigSize>
32 {
33 std::size_t i_;
operator <(const test_class & l,const test_class & r)34 friend bool operator <(const test_class &l, const test_class &r) { return l.i_ < r.i_; }
operator >(const test_class & l,const test_class & r)35 friend bool operator >(const test_class &l, const test_class &r) { return l.i_ > r.i_; }
36 };
37
38 template <bool BigSize, class HookType>
39 struct itest_class //The object for intrusive containers
40 : public HookType, public test_class<BigSize>
41 {
42 };
43
44 #ifdef NDEBUG
45 const std::size_t NumElem = 1000000;
46 #else
47 const std::size_t NumElem = 10000;
48 #endif
49 const std::size_t NumRepeat = 4;
50
51 enum InsertionType
52 {
53 Monotonic,
54 Random
55 };
56
57 template<class Container>
fill_vector(Container & values,InsertionType insertion_type)58 void fill_vector(Container &values, InsertionType insertion_type)
59 {
60 switch(insertion_type){
61 case Monotonic:{
62 for( typename Container::size_type i = 0, max = values.size()
63 ; i != max
64 ; ++i){
65 values[i].i_ = i;
66 }
67 }
68 break;
69 case Random:{
70 std::srand(0);
71 for( typename Container::size_type i = 0, max = values.size()
72 ; i != max
73 ; ++i){
74 values[i].i_ = i;
75 }
76 std::random_shuffle(values.begin(), values.end());
77 }
78 break;
79 default:{
80 std::abort();
81 }
82 }
83 }
84
85 template<class Container>
test_insertion(Container & c,const char * ContainerName,InsertionType insertion_type)86 void test_insertion(Container &c, const char *ContainerName, InsertionType insertion_type)
87 {
88 std::cout << "Container " << ContainerName << std::endl;
89 //Prepare
90 typedef typename Container::size_type size_type;
91 typedef typename Container::value_type value_type;
92 ptime tini, tend;
93 std::vector<Container::value_type> values(NumElem);
94 {
95 fill_vector(values, insertion_type);
96 //Insert
97 tini = microsec_clock::universal_time();
98 for( size_type repeat = 0, repeat_max = NumRepeat
99 ; repeat != repeat_max
100 ; ++repeat){
101 c.clear();
102 for( size_type i = 0, max = values.size()
103 ; i != max
104 ; ++i){
105 c.insert(values[i]);
106 }
107 if(c.size() != values.size()){
108 std::cout << " ERROR: size not consistent" << std::endl;
109 }
110 }
111 tend = microsec_clock::universal_time();
112 std::cout << " Insert ns/iter: " << double((tend-tini).total_nanoseconds())/double(NumElem*NumRepeat) << std::endl;
113 }
114 //Search
115 {
116 value_type v;
117 tini = microsec_clock::universal_time();
118 for( size_type repeat = 0, repeat_max = NumRepeat
119 ; repeat != repeat_max
120 ; ++repeat){
121 size_type found = 0;
122 for( size_type i = 0, max = values.size()
123 ; i != max
124 ; ++i){
125 v.i_ = i;
126 found += static_cast<size_type>(c.end() != c.find(v));
127 }
128 if(found != NumElem){
129 std::cout << " ERROR: all not found (" << found << ") vs. (" << NumElem << ")" << std::endl;
130 }
131 }
132 tend = microsec_clock::universal_time();
133 std::cout << " Search ns/iter: " << double((tend-tini).total_nanoseconds())/double(NumElem*NumRepeat) << std::endl;
134 }
135 }
136
137
test_insert_search(InsertionType insertion_type)138 void test_insert_search(InsertionType insertion_type)
139 {
140 {
141 typedef set_base_hook< link_mode<normal_link> > SetHook;
142 typedef set< itest_class<true, SetHook> > Set;
143 Set c;
144 test_insertion(c, "Set", insertion_type);
145 }
146 {
147 typedef avl_set_base_hook< link_mode<normal_link> > AvlSetHook;
148 typedef avl_set< itest_class<true, AvlSetHook> > AvlSet;
149 AvlSet c;
150 test_insertion(c, "AvlSet", insertion_type);
151 }
152 {
153 typedef bs_set_base_hook< link_mode<normal_link> > BsSetHook;
154 typedef sg_set< itest_class<true, BsSetHook> > SgSet;
155 SgSet c;
156 c.balance_factor(0.55f);
157 test_insertion(c, "SgSet(alpha 0.55)", insertion_type);
158 }
159 {
160 typedef bs_set_base_hook< link_mode<normal_link> > BsSetHook;
161 typedef sg_set< itest_class<true, BsSetHook> > SgSet;
162 SgSet c;
163 c.balance_factor(0.60f);
164 test_insertion(c, "SgSet(alpha 0.60)", insertion_type);
165 }
166 {
167 typedef bs_set_base_hook< link_mode<normal_link> > BsSetHook;
168 typedef sg_set< itest_class<true, BsSetHook> > SgSet;
169 SgSet c;
170 c.balance_factor(0.65f);
171 test_insertion(c, "SgSet(alpha 0.65)", insertion_type);
172 }
173 {
174 typedef bs_set_base_hook< link_mode<normal_link> > BsSetHook;
175 typedef sg_set< itest_class<true, BsSetHook> > SgSet;
176 SgSet c;
177 test_insertion(c, "SgSet(alpha 0.7)", insertion_type);
178 }
179 {
180 typedef bs_set_base_hook< link_mode<normal_link> > BsSetHook;
181 typedef sg_set< itest_class<true, BsSetHook> > SgSet;
182 SgSet c;
183 c.balance_factor(0.75f);
184 test_insertion(c, "SgSet(alpha 0.75)", insertion_type);
185 }
186 {
187 typedef bs_set_base_hook< link_mode<normal_link> > BsSetHook;
188 typedef sg_set< itest_class<true, BsSetHook> > SgSet;
189 SgSet c;
190 c.balance_factor(0.80f);
191 test_insertion(c, "SgSet(alpha 0.80)", insertion_type);
192 }
193 {
194 typedef bs_set_base_hook< link_mode<normal_link> > BsSetHook;
195 typedef sg_set< itest_class<true, BsSetHook>, floating_point<false> > SgSet;
196 SgSet c;
197 test_insertion(c, "SgSet(no float, alpha 1/sqrt(2)~0,7071)", insertion_type);
198 }
199 }
200
main()201 int main()
202 {
203 std::cout << "MONOTONIC INPUTS\n";
204 std::cout << "----------------\n\n";
205 test_insert_search(Monotonic);
206 std::cout << "----------------\n\n";
207 std::cout << "RANDOM INPUTS\n";
208 std::cout << "----------------\n\n";
209 test_insert_search(Random);
210 std::cout << "----------------\n\n";
211 return 0;
212 }
213
214 #include <boost/intrusive/detail/config_end.hpp>
215