| ///////////////////////////////////////////////////////////////////////////// |
| // |
| // (C) Copyright Ion Gaztanaga 2007-2009 |
| // |
| // Distributed under the Boost Software License, Version 1.0. |
| // (See accompanying file LICENSE_1_0.txt or copy at |
| // http://www.boost.org/LICENSE_1_0.txt) |
| // |
| // See http://www.boost.org/libs/intrusive for documentation. |
| // |
| ///////////////////////////////////////////////////////////////////////////// |
| #include <boost/intrusive/list.hpp> |
| #include <boost/intrusive/slist.hpp> |
| #include <boost/intrusive/rbtree.hpp> |
| #include <boost/intrusive/hashtable.hpp> |
| #include <boost/pointer_to_other.hpp> |
| #include <functional> |
| #include <vector> |
| |
| using namespace boost::intrusive; |
| |
| class MyClass |
| { |
| public: |
| int int_; |
| |
| MyClass(int i = 0) |
| : int_(i) |
| {} |
| friend bool operator > (const MyClass &l, const MyClass &r) |
| { return l.int_ > r.int_; } |
| friend bool operator == (const MyClass &l, const MyClass &r) |
| { return l.int_ == r.int_; } |
| friend std::size_t hash_value(const MyClass &v) |
| { return boost::hash_value(v.int_); } |
| }; |
| |
| const int NumElements = 100; |
| |
| template<class NodeTraits> |
| struct external_traits |
| { |
| typedef NodeTraits node_traits; |
| typedef typename node_traits::node node; |
| typedef typename node_traits::node_ptr node_ptr; |
| typedef typename node_traits::const_node_ptr const_node_ptr; |
| typedef MyClass value_type; |
| typedef typename boost::pointer_to_other |
| <node_ptr, MyClass>::type pointer; |
| typedef typename boost::pointer_to_other |
| <node_ptr, const MyClass>::type const_pointer; |
| static const link_mode_type link_mode = normal_link; |
| |
| external_traits(pointer values, std::size_t NumElem) |
| : values_(values), node_array_(NumElem) |
| {} |
| |
| node_ptr to_node_ptr (value_type &value) |
| { return (&node_array_[0]) + (&value - values_); } |
| |
| const_node_ptr to_node_ptr (const value_type &value) const |
| { return &node_array_[0] + (&value - values_); } |
| |
| pointer to_value_ptr(node_ptr n) |
| { return values_ + (n - &node_array_[0]); } |
| |
| const_pointer to_value_ptr(const_node_ptr n) const |
| { return values_ + (n - &node_array_[0]); } |
| |
| pointer values_; |
| std::vector<node> node_array_; |
| }; |
| |
| template<class NodeTraits> |
| struct value_traits_proxy; |
| |
| template<class T> |
| struct traits_holder |
| : public T |
| {}; |
| |
| typedef value_traits_proxy<list_node_traits<void*> > list_value_traits_proxy; |
| typedef value_traits_proxy<slist_node_traits<void*> > slist_value_traits_proxy; |
| typedef value_traits_proxy<rbtree_node_traits<void*> > rbtree_value_traits_proxy; |
| typedef value_traits_proxy<traits_holder<slist_node_traits<void*> > > hash_value_traits_proxy; |
| |
| struct uset_bucket_traits |
| { |
| private: |
| typedef unordered_bucket<value_traits<external_traits |
| <traits_holder<slist_node_traits<void*> > > > >::type bucket_type; |
| |
| //Non-copyable |
| uset_bucket_traits(const uset_bucket_traits &other); |
| uset_bucket_traits & operator=(const uset_bucket_traits &other); |
| |
| public: |
| static const std::size_t NumBuckets = 100; |
| |
| uset_bucket_traits(){} |
| |
| bucket_type * bucket_begin() const |
| { return buckets_; } |
| |
| std::size_t bucket_count() const |
| { return NumBuckets; } |
| |
| mutable bucket_type buckets_[NumBuckets]; |
| }; |
| |
| struct bucket_traits_proxy |
| { |
| static const bool external_bucket_traits = true; |
| typedef uset_bucket_traits bucket_traits; |
| |
| template<class Container> |
| bucket_traits &get_bucket_traits(Container &cont); |
| |
| template<class Container> |
| const bucket_traits &get_bucket_traits(const Container &cont) const; |
| }; |
| |
| //Define a list that will store MyClass using the external hook |
| typedef list<MyClass, value_traits<list_value_traits_proxy> > List; |
| //Define a slist that will store MyClass using the external hook |
| typedef slist<MyClass, value_traits<slist_value_traits_proxy> > Slist; |
| //Define a rbtree that will store MyClass using the external hook |
| typedef rbtree< MyClass |
| , value_traits<rbtree_value_traits_proxy> |
| , compare<std::greater<MyClass> > > Rbtree; |
| //Define a hashtable that will store MyClass using the external hook |
| typedef hashtable< MyClass |
| , value_traits<hash_value_traits_proxy> |
| , bucket_traits<bucket_traits_proxy> |
| > Hash; |
| |
| template<class NodeTraits> |
| struct value_traits_proxy |
| { |
| static const bool external_value_traits = true; |
| typedef external_traits<NodeTraits> value_traits; |
| |
| template<class Container> |
| const value_traits &get_value_traits(const Container &cont) const; |
| |
| template<class Container> |
| value_traits &get_value_traits(Container &cont); |
| }; |
| |
| struct ContainerHolder |
| : public uset_bucket_traits |
| , public List |
| , public external_traits<list_node_traits<void*> > |
| , public Slist |
| , public external_traits<slist_node_traits<void*> > |
| , public Rbtree |
| , public external_traits<rbtree_node_traits<void*> > |
| , public Hash |
| , public external_traits<traits_holder<slist_node_traits<void*> > > |
| { |
| static const std::size_t NumBucket = 100; |
| ContainerHolder(MyClass *values, std::size_t num_elem) |
| : uset_bucket_traits() |
| , List() |
| , external_traits<list_node_traits<void*> >(values, num_elem) |
| , Slist() |
| , external_traits<slist_node_traits<void*> >(values, num_elem) |
| , Rbtree() |
| , external_traits<rbtree_node_traits<void*> >(values, num_elem) |
| , Hash(Hash::bucket_traits()) |
| , external_traits<traits_holder<slist_node_traits<void*> > >(values, num_elem) |
| {} |
| }; |
| |
| template<class NodeTraits> |
| template<class Container> |
| typename value_traits_proxy<NodeTraits>::value_traits & |
| value_traits_proxy<NodeTraits>::get_value_traits(Container &cont) |
| { return static_cast<value_traits&>(static_cast<ContainerHolder&>(cont)); } |
| |
| template<class NodeTraits> |
| template<class Container> |
| const typename value_traits_proxy<NodeTraits>::value_traits & |
| value_traits_proxy<NodeTraits>::get_value_traits(const Container &cont) const |
| { return static_cast<const value_traits&>(static_cast<const ContainerHolder&>(cont)); } |
| |
| template<class Container> |
| typename bucket_traits_proxy::bucket_traits & |
| bucket_traits_proxy::get_bucket_traits(Container &cont) |
| { return static_cast<bucket_traits&>(static_cast<ContainerHolder&>(cont)); } |
| |
| template<class Container> |
| const typename bucket_traits_proxy::bucket_traits & |
| bucket_traits_proxy::get_bucket_traits(const Container &cont) const |
| { return static_cast<const bucket_traits&>(static_cast<const ContainerHolder&>(cont)); } |
| |
| int main() |
| { |
| MyClass values [NumElements]; |
| //Create several MyClass objects, each one with a different value |
| for(int i = 0; i < NumElements; ++i) |
| values[i].int_ = i; |
| |
| ContainerHolder cont_holder(values, NumElements); |
| List &my_list = static_cast<List &> (cont_holder); |
| Slist &my_slist = static_cast<Slist &> (cont_holder); |
| Rbtree &my_rbtree = static_cast<Rbtree &> (cont_holder); |
| Hash &my_hash = static_cast<Hash &> (cont_holder); |
| |
| //Now insert them in containers |
| for(MyClass * it(&values[0]), *itend(&values[NumElements]) |
| ; it != itend; ++it){ |
| my_list.push_front(*it); |
| my_slist.push_front(*it); |
| my_rbtree.insert_unique(*it); |
| my_hash.insert_unique(*it); |
| } |
| |
| //Now test containers |
| { |
| List::const_iterator list_it (my_list.cbegin()); |
| Slist::const_iterator slist_it (my_slist.cbegin()); |
| Rbtree::const_iterator rbtree_it (my_rbtree.cbegin()); |
| Hash::const_iterator hash_it (my_hash.cbegin()); |
| MyClass *it_val(&values[NumElements] - 1), *it_rbeg_val(&values[0]-1); |
| |
| //Test inserted objects |
| for(; it_val != it_rbeg_val; --it_val, ++list_it, ++slist_it, ++rbtree_it){ |
| if(&*list_it != &*it_val) return 1; |
| if(&*slist_it != &*it_val) return 1; |
| if(&*rbtree_it != &*it_val) return 1; |
| hash_it = my_hash.find(*it_val); |
| if(hash_it == my_hash.cend() || &*hash_it != &*it_val) |
| return 1; |
| } |
| } |
| |
| return 0; |
| } |