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 #include <boost/intrusive/unordered_set.hpp>
13 #include <boost/intrusive/detail/mpl.hpp>
14 #include <boost/functional/hash.hpp>
15 #include <boost/static_assert.hpp>
16 #include <vector>
17
18 using namespace boost::intrusive;
19
20 class MyClass : public unordered_set_base_hook<>
21 {
22 int int_;
23
24 public:
MyClass(int i=0)25 MyClass(int i = 0) : int_(i)
26 {}
27 unordered_set_member_hook<> member_hook_;
28
operator ==(const MyClass & l,const MyClass & r)29 friend bool operator==(const MyClass &l, const MyClass &r)
30 { return l.int_ == r.int_; }
31
hash_value(const MyClass & v)32 friend std::size_t hash_value(const MyClass &v)
33 { return boost::hash_value(v.int_); }
34 };
35
36 struct uset_value_traits
37 {
38 typedef slist_node_traits<void*> node_traits;
39 typedef node_traits::node_ptr node_ptr;
40 typedef node_traits::const_node_ptr const_node_ptr;
41 typedef MyClass value_type;
42 typedef MyClass * pointer;
43 typedef const MyClass * const_pointer;
44 static const link_mode_type link_mode = normal_link;
45
to_node_ptruset_value_traits46 static node_ptr to_node_ptr (value_type &value)
47 { return node_ptr(&value); }
to_node_ptruset_value_traits48 static const_node_ptr to_node_ptr (const value_type &value)
49 { return const_node_ptr(&value); }
to_value_ptruset_value_traits50 static pointer to_value_ptr(node_ptr n)
51 { return static_cast<value_type*>(n); }
to_value_ptruset_value_traits52 static const_pointer to_value_ptr(const_node_ptr n)
53 { return static_cast<const value_type*>(n); }
54 };
55
56 //Base
57 typedef base_hook< unordered_set_base_hook<> > BaseHook;
58 typedef unordered_bucket<BaseHook>::type BaseBucketType;
59 typedef unordered_bucket_ptr<BaseHook>::type BaseBucketPtrType;
60 typedef unordered_set<MyClass, BaseHook> BaseUset;
61 //Member
62 typedef member_hook
63 < MyClass, unordered_set_member_hook<>
64 , &MyClass::member_hook_ > MemberHook;
65 typedef unordered_bucket<MemberHook>::type MemberBucketType;
66 typedef unordered_bucket_ptr<MemberHook>::type MemberBucketPtrType;
67 typedef unordered_set<MyClass, MemberHook> MemberUset;
68 //Explicit
69 typedef value_traits< uset_value_traits > Traits;
70 typedef unordered_bucket<Traits>::type TraitsBucketType;
71 typedef unordered_bucket_ptr<Traits>::type TraitsBucketPtrType;
72 typedef unordered_set<MyClass, Traits> TraitsUset;
73
74 struct uset_bucket_traits
75 {
76 //Power of two bucket length
77 static const std::size_t NumBuckets = 128;
78
uset_bucket_traitsuset_bucket_traits79 uset_bucket_traits(BaseBucketType *buckets)
80 : buckets_(buckets)
81 {}
82
uset_bucket_traitsuset_bucket_traits83 uset_bucket_traits(const uset_bucket_traits &other)
84 : buckets_(other.buckets_)
85 {}
86
bucket_beginuset_bucket_traits87 BaseBucketType * bucket_begin() const
88 { return buckets_; }
89
bucket_countuset_bucket_traits90 std::size_t bucket_count() const
91 { return NumBuckets; }
92
93 BaseBucketType *buckets_;
94 };
95
96 typedef unordered_set
97 <MyClass, bucket_traits<uset_bucket_traits>, power_2_buckets<true> >
98 BucketTraitsUset;
99
main()100 int main()
101 {
102 BOOST_STATIC_ASSERT((detail::is_same<BaseUset::bucket_type, BaseBucketType>::value));
103 BOOST_STATIC_ASSERT((detail::is_same<MemberUset::bucket_type, MemberBucketType>::value));
104 BOOST_STATIC_ASSERT((detail::is_same<TraitsUset::bucket_type, TraitsBucketType>::value));
105 BOOST_STATIC_ASSERT((detail::is_same<BaseBucketType, MemberBucketType>::value));
106 BOOST_STATIC_ASSERT((detail::is_same<BaseBucketType, TraitsBucketType>::value));
107 BOOST_STATIC_ASSERT((detail::is_same<BaseBucketPtrType, TraitsBucketPtrType>::value));
108 BOOST_STATIC_ASSERT((detail::is_same<BaseBucketPtrType, MemberBucketPtrType>::value));
109 BOOST_STATIC_ASSERT((detail::is_same<BaseBucketPtrType, BaseBucketType*>::value));
110
111 typedef std::vector<MyClass>::iterator VectIt;
112 typedef std::vector<MyClass>::reverse_iterator VectRit;
113 std::vector<MyClass> values;
114
115 for(int i = 0; i < 100; ++i) values.push_back(MyClass(i));
116
117 BaseBucketType buckets[uset_bucket_traits::NumBuckets];
118 uset_bucket_traits btraits(buckets);
119 BucketTraitsUset uset(btraits);
120
121 for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it)
122 uset.insert(*it);
123
124 for( VectRit it(values.rbegin()), itend(values.rend()); it != itend; ++it){
125 if(uset.find(*it) == uset.cend()) return 1;
126 }
127
128 return 0;
129 }
130