1 /////////////////////////////////////////////////////////////////////////////
2 //
3 // (C) Copyright Ion Gaztanaga 2014-2014
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 #include <boost/detail/lightweight_test.hpp>
13 #include <cstddef>
14
15 #include <boost/intrusive/list.hpp>
16 #include <boost/intrusive/slist.hpp>
17 #include <boost/intrusive/set.hpp>
18 #include <boost/intrusive/avl_set.hpp>
19 #include <boost/intrusive/bs_set.hpp>
20 #include <boost/intrusive/sg_set.hpp>
21 #include <boost/intrusive/splay_set.hpp>
22 #include <boost/intrusive/treap_set.hpp>
23 #include <boost/intrusive/unordered_set.hpp>
24 #include <boost/static_assert.hpp>
25 #include "itestvalue.hpp"
26
27 using namespace boost::intrusive;
28
29 BOOST_INTRUSIVE_INSTANTIATE_DEFAULT_TYPE_TMPLT(reverse_iterator)
30 BOOST_INTRUSIVE_INSTANTIATE_DEFAULT_TYPE_TMPLT(const_reverse_iterator)
31
32 template<bool Value>
33 struct boolean
34 {
35 static const bool value = Value;
36 };
37
38 template<class A, class B>
39 struct pow2_and_equal_sizes
40 {
41 static const std::size_t a_size = sizeof(A);
42 static const std::size_t b_size = sizeof(B);
43 static const bool a_b_sizes_equal = a_size == b_size;
44 static const bool value = !(a_size & (a_size - 1u));
45 };
46
47 template<class Hook>
48 struct node : Hook
49 {};
50
51 //Avoid testing for uncommon architectures
test_sizes(boolean<false>,std::size_t)52 void test_sizes(boolean<false>, std::size_t)
53 {}
54
55 template<class C>
test_iterator_sizes(std::size_t size)56 void test_iterator_sizes(std::size_t size)
57 {
58 typedef typename C::iterator iterator;
59 typedef typename C::const_iterator const_iterator;
60 typedef BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT
61 (::, C, reverse_iterator, iterator) reverse_iterator;
62 typedef BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT
63 (::, C, const_reverse_iterator, const_iterator) const_reverse_iterator;
64
65 BOOST_TEST_EQ(sizeof(iterator), size);
66 BOOST_TEST_EQ(sizeof(const_iterator), size);
67 BOOST_TEST_EQ(sizeof(iterator), sizeof(reverse_iterator));
68 BOOST_TEST_EQ(sizeof(const_iterator), size);
69 BOOST_TEST_EQ(sizeof(const_iterator), sizeof(const_reverse_iterator));
70 }
71
72 //Test sizes for common 32 and 64 bit architectures
test_sizes(boolean<true>,std::size_t wordsize)73 void test_sizes(boolean<true>, std::size_t wordsize)
74 {
75 { //list
76 typedef list<node<list_base_hook<> > > c;
77 BOOST_TEST_EQ(sizeof(c), wordsize*3);
78 test_iterator_sizes<c>(wordsize);
79 }
80 {
81 typedef list<node<list_base_hook<> >, constant_time_size<false> > c;
82 BOOST_TEST_EQ(sizeof(c), wordsize*2);
83 test_iterator_sizes<c>(wordsize);
84 }
85 {
86 typedef list< node< list_base_hook<> >, header_holder_type< heap_node_holder< list_node<void*>* > > > c;
87 BOOST_TEST_EQ(sizeof(c), wordsize*2);
88 test_iterator_sizes<c>(wordsize);
89 }
90 {
91 typedef list< node< list_base_hook<> >, constant_time_size<false>, header_holder_type< heap_node_holder< list_node<void*>* > > > c;
92 BOOST_TEST_EQ(sizeof(c), wordsize*1);
93 test_iterator_sizes<c>(wordsize);
94 }
95 { //slist
96 typedef slist<node< slist_base_hook<> > > c;
97 BOOST_TEST_EQ(sizeof(c), wordsize*2);
98 test_iterator_sizes<c>(wordsize);
99 }
100 {
101 typedef slist<node< slist_base_hook<> >, constant_time_size<false> > c;
102 BOOST_TEST_EQ(sizeof(c), wordsize*1);
103 test_iterator_sizes<c>(wordsize);
104 }
105 {
106 typedef slist<node< slist_base_hook<> >, cache_last<true> > c;
107 BOOST_TEST_EQ(sizeof(c), wordsize*3);
108 test_iterator_sizes<c>(wordsize);
109 }
110 { //set
111 typedef set<node< set_base_hook<> > > c;
112 BOOST_TEST_EQ(sizeof(c), wordsize*5);
113 test_iterator_sizes<c>(wordsize);
114 }
115 {
116 typedef set<node< set_base_hook<> > , constant_time_size<false> > c;
117 BOOST_TEST_EQ(sizeof(c), wordsize*4);
118 test_iterator_sizes<c>(wordsize);
119 }
120 {
121 typedef set<node< set_base_hook<optimize_size<true> > > , constant_time_size<false> > c;
122 BOOST_TEST_EQ(sizeof(c), wordsize*3);
123 test_iterator_sizes<c>(wordsize);
124 }
125 {
126 typedef set< node< set_base_hook<> >, header_holder_type< heap_node_holder< rbtree_node<void*>* > > > c;
127 BOOST_TEST_EQ(sizeof(c), wordsize*2);
128 test_iterator_sizes<c>(wordsize);
129 }
130 {
131 typedef set< node< set_base_hook<> >, constant_time_size<false>, header_holder_type< heap_node_holder< rbtree_node<void*>* > > > c;
132 BOOST_TEST_EQ(sizeof(c), wordsize*1);
133 test_iterator_sizes<c>(wordsize);
134 }
135 { //avl
136 typedef avl_set<node< avl_set_base_hook<> > > c;
137 BOOST_TEST_EQ(sizeof(c), wordsize*5);
138 test_iterator_sizes<c>(wordsize);
139 }
140 {
141 typedef avl_set<node< avl_set_base_hook<> > , constant_time_size<false> > c;
142 BOOST_TEST_EQ(sizeof(c), wordsize*4);
143 test_iterator_sizes<c>(wordsize);
144 }
145 {
146 typedef avl_set<node< avl_set_base_hook<optimize_size<true> > > , constant_time_size<false> > c;
147 BOOST_TEST_EQ(sizeof(c), wordsize*3);
148 test_iterator_sizes<c>(wordsize);
149 }
150 {
151 typedef avl_set< node< avl_set_base_hook<> >, header_holder_type< heap_node_holder< avltree_node<void*>* > > > c;
152 BOOST_TEST_EQ(sizeof(c), wordsize*2);
153 test_iterator_sizes<c>(wordsize);
154 }
155 {
156 typedef avl_set< node< avl_set_base_hook<> >, constant_time_size<false>, header_holder_type< heap_node_holder< avltree_node<void*>* > > > c;
157 BOOST_TEST_EQ(sizeof(c), wordsize*1);
158 test_iterator_sizes<c>(wordsize);
159 }
160 { //bs
161 typedef bs_set<node< bs_set_base_hook<> > > c;
162 BOOST_TEST_EQ(sizeof(c), wordsize*4);
163 test_iterator_sizes<c>(wordsize);
164 }
165 {
166 typedef bs_set<node< bs_set_base_hook<> > , constant_time_size<false> > c;
167 BOOST_TEST_EQ(sizeof(c), wordsize*3);
168 test_iterator_sizes<c>(wordsize);
169 }
170 { //splay
171 typedef splay_set<node< bs_set_base_hook<> > > c;
172 BOOST_TEST_EQ(sizeof(c), wordsize*4);
173 test_iterator_sizes<c>(wordsize);
174 }
175 {
176 typedef splay_set<node< bs_set_base_hook<> > , constant_time_size<false> > c;
177 BOOST_TEST_EQ(sizeof(c), wordsize*3);
178 test_iterator_sizes<c>(wordsize);
179 }
180 { //scapegoat
181 typedef sg_set<node< bs_set_base_hook<> > > c;
182 BOOST_TEST_EQ(sizeof(c), (wordsize*5+sizeof(float)*2));
183 test_iterator_sizes<c>(wordsize);
184 }
185 { //treap
186 typedef treap_set<node< bs_set_base_hook<> > > c;
187 BOOST_TEST_EQ(sizeof(c), wordsize*4);
188 test_iterator_sizes<c>(wordsize);
189 }
190 {
191 typedef treap_set<node< bs_set_base_hook<> > , constant_time_size<false> > c;
192 BOOST_TEST_EQ(sizeof(c), wordsize*3);
193 test_iterator_sizes<c>(wordsize);
194 }
195 { //unordered
196 typedef unordered_set<node< unordered_set_base_hook<> > > c;
197 BOOST_TEST_EQ(sizeof(c), wordsize*3);
198 test_iterator_sizes<c>(wordsize*2);
199 }
200 {
201 typedef unordered_set<node< unordered_set_base_hook<> > , power_2_buckets<true> > c;
202 BOOST_TEST_EQ(sizeof(c), wordsize*3);
203 test_iterator_sizes<c>(wordsize*2);
204 }
205 {
206 typedef unordered_set<node< unordered_set_base_hook<> >, constant_time_size<false> > c;
207 BOOST_TEST_EQ(sizeof(c), wordsize*2);
208 test_iterator_sizes<c>(wordsize*2);
209 }
210 {
211 typedef unordered_set<node< unordered_set_base_hook< optimize_multikey<true> > >, constant_time_size<false> > c;
212 BOOST_TEST_EQ(sizeof(c), wordsize*2);
213 test_iterator_sizes<c>(wordsize*2);
214 }
215 {
216 typedef unordered_set<node< unordered_set_base_hook< optimize_multikey<true> > >, incremental<true> > c;
217 BOOST_TEST_EQ(sizeof(c), wordsize*4);
218 test_iterator_sizes<c>(wordsize*2);
219 }
220 }
221
main()222 int main()
223 {
224 test_sizes(boolean< pow2_and_equal_sizes<std::size_t, void*>::value >(), sizeof(std::size_t));
225 return ::boost::report_errors();
226 }
227