diff options
Diffstat (limited to 'src/boost/libs/intrusive/example')
37 files changed, 3226 insertions, 0 deletions
diff --git a/src/boost/libs/intrusive/example/Jamfile.v2 b/src/boost/libs/intrusive/example/Jamfile.v2 new file mode 100644 index 000000000..4e8f44e2a --- /dev/null +++ b/src/boost/libs/intrusive/example/Jamfile.v2 @@ -0,0 +1,39 @@ +# Boost Intrusive Library Example Jamfile + +# (C) Copyright Ion Gaztanaga 2006-2013. +# Use, modification and distribution are subject to 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) + +# Adapted from John Maddock's TR1 Jamfile.v2 +# Copyright John Maddock 2005. +# Use, modification and distribution are subject to 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) + +# this rule enumerates through all the sources and invokes +# the run rule for each source, the result is a list of all +# the run rules, which we can pass on to the test_suite rule: + +rule test_all +{ + local all_rules = ; + + for local fileb in [ glob *.cpp ] + { + all_rules += [ run $(fileb) + : # additional args + : # test-files + : # requirements + <toolset>acc:<linkflags>-lrt + <toolset>acc-pa_risc:<linkflags>-lrt + <toolset>gcc,<target-os>windows:<linkflags>"-lole32 -loleaut32" + <host-os>hpux,<toolset>gcc:<linkflags>"-Wl,+as,mpas" + <host-os>windows,<toolset>clang:<linkflags>"-lole32 -loleaut32 -lpsapi -ladvapi32" + ] ; + } + + return $(all_rules) ; +} + +test-suite intrusive_example : [ test_all r ] : <threading>multi ; diff --git a/src/boost/libs/intrusive/example/doc_advanced_value_traits.cpp b/src/boost/libs/intrusive/example/doc_advanced_value_traits.cpp new file mode 100644 index 000000000..dc5f8d295 --- /dev/null +++ b/src/boost/libs/intrusive/example/doc_advanced_value_traits.cpp @@ -0,0 +1,105 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2006-2013 +// +// 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. +// +///////////////////////////////////////////////////////////////////////////// +//[doc_advanced_value_traits_code +#include <boost/intrusive/link_mode.hpp> +#include <boost/intrusive/list.hpp> +#include <vector> + +//This is the node that will be used with algorithms. +struct simple_node +{ + simple_node *prev_; + simple_node *next_; +}; +//] + +//[doc_advanced_value_traits_value_traits +class base_1{}; +class base_2{}; + +struct value_1 : public base_1, public simple_node +{ int id_; }; + +struct value_2 : public base_1, public base_2, public simple_node +{ float id_; }; + +//Define the node traits. A single node_traits will be enough. +struct simple_node_traits +{ + typedef simple_node node; + typedef node * node_ptr; + typedef const node * const_node_ptr; + static node *get_next(const node *n) { return n->next_; } + static void set_next(node *n, node *next) { n->next_ = next; } + static node *get_previous(const node *n) { return n->prev_; } + static void set_previous(node *n, node *prev) { n->prev_ = prev; } +}; + +//A templatized value traits for value_1 and value_2 +template<class ValueType> +struct simple_value_traits +{ + typedef simple_node_traits node_traits; + typedef node_traits::node_ptr node_ptr; + typedef node_traits::const_node_ptr const_node_ptr; + typedef ValueType value_type; + typedef ValueType * pointer; + typedef const ValueType * const_pointer; + static const boost::intrusive::link_mode_type link_mode = boost::intrusive::normal_link; + static node_ptr to_node_ptr (value_type &value) { return node_ptr(&value); } + static const_node_ptr to_node_ptr (const value_type &value) { return const_node_ptr(&value); } + static pointer to_value_ptr(node_ptr n) { return static_cast<value_type*>(n); } + static const_pointer to_value_ptr(const_node_ptr n) { return static_cast<const value_type*>(n); } +}; +//] + +//[doc_advanced_value_traits_containers +//Now define two intrusive lists. Both lists will use the same algorithms: +// circular_list_algorithms<simple_node_traits> + +using namespace boost::intrusive; +typedef list <value_1, value_traits<simple_value_traits<value_1> > > Value1List; +typedef list <value_2, value_traits<simple_value_traits<value_2> > > Value2List; +//] + +//[doc_advanced_value_traits_test +int main() +{ + typedef std::vector<value_1> Vect1; + typedef std::vector<value_2> Vect2; + + //Create values, with a different internal number + Vect1 values1; + Vect2 values2; + for(int i = 0; i < 100; ++i){ + value_1 v1; v1.id_ = i; values1.push_back(v1); + value_2 v2; v2.id_ = (float)i; values2.push_back(v2); + } + + //Create the lists with the objects + Value1List list1(values1.begin(), values1.end()); + Value2List list2(values2.begin(), values2.end()); + + //Now test both lists + Value1List::const_iterator bit1(list1.begin()), bitend1(list1.end()); + Value2List::const_iterator bit2(list2.begin()), bitend2(list2.end()); + + Vect1::const_iterator it1(values1.begin()), itend1(values1.end()); + Vect2::const_iterator it2(values2.begin()), itend2(values2.end()); + + //Test the objects inserted in our lists + for(; it1 != itend1; ++it1, ++bit1, ++it2, ++bit2){ + if(&*bit1 != &*it1 || &*bit2 != &*it2) return 1; + } + return 0; +} +//] diff --git a/src/boost/libs/intrusive/example/doc_any_hook.cpp b/src/boost/libs/intrusive/example/doc_any_hook.cpp new file mode 100644 index 000000000..2526f70d8 --- /dev/null +++ b/src/boost/libs/intrusive/example/doc_any_hook.cpp @@ -0,0 +1,65 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2008-2013 +// +// 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. +// +///////////////////////////////////////////////////////////////////////////// +//[doc_any_hook +#include <vector> +#include <boost/intrusive/any_hook.hpp> +#include <boost/intrusive/slist.hpp> +#include <boost/intrusive/list.hpp> + +using namespace boost::intrusive; + +class MyClass : public any_base_hook<> //Base hook +{ + int int_; + + public: + any_member_hook<> member_hook_; //Member hook + + MyClass(int i = 0) : int_(i) + {} + //<- + int get_int() const { return int_; } + //-> +}; + +int main() +{ + //Define a base hook option that converts any_base_hook to a slist hook + typedef any_to_slist_hook < base_hook< any_base_hook<> > > BaseSlistOption; + typedef slist<MyClass, BaseSlistOption> BaseSList; + + //Define a member hook option that converts any_member_hook to a list hook + typedef any_to_list_hook< member_hook + < MyClass, any_member_hook<>, &MyClass::member_hook_> > MemberListOption; + typedef list<MyClass, MemberListOption> MemberList; + + //Create several MyClass objects, each one with a different value + std::vector<MyClass> values; + for(int i = 0; i < 100; ++i){ values.push_back(MyClass(i)); } + + BaseSList base_slist; MemberList member_list; + + //Now insert them in reverse order in the slist and in order in the list + for(std::vector<MyClass>::iterator it(values.begin()), itend(values.end()); it != itend; ++it) + base_slist.push_front(*it), member_list.push_back(*it); + + //Now test lists + BaseSList::iterator bit(base_slist.begin()); + MemberList::reverse_iterator mrit(member_list.rbegin()); + std::vector<MyClass>::reverse_iterator rit(values.rbegin()), ritend(values.rend()); + + //Test the objects inserted in the base hook list + for(; rit != ritend; ++rit, ++bit, ++mrit) + if(&*bit != &*rit || &*mrit != &*rit) return 1; + return 0; +} +//] diff --git a/src/boost/libs/intrusive/example/doc_assoc_optimized_code.cpp b/src/boost/libs/intrusive/example/doc_assoc_optimized_code.cpp new file mode 100644 index 000000000..530ad797f --- /dev/null +++ b/src/boost/libs/intrusive/example/doc_assoc_optimized_code.cpp @@ -0,0 +1,260 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2006-2013 +// +// 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. +// +///////////////////////////////////////////////////////////////////////////// +//[doc_assoc_optimized_code_normal_find +#include <boost/intrusive/set.hpp> +#include <boost/intrusive/unordered_set.hpp> +#include <cstring> + +using namespace boost::intrusive; + +// Hash function for strings +struct StrHasher +{ + std::size_t operator()(const char *str) const + { + std::size_t seed = 0; + for(; *str; ++str) boost::hash_combine(seed, *str); + return seed; + } +}; + +class Expensive : public set_base_hook<>, public unordered_set_base_hook<> +{ + std::string key_; + // Other members... + + public: + Expensive(const char *key) + : key_(key) + {} //other expensive initializations... + + const std::string & get_key() const + { return key_; } + + friend bool operator < (const Expensive &a, const Expensive &b) + { return a.key_ < b.key_; } + + friend bool operator == (const Expensive &a, const Expensive &b) + { return a.key_ == b.key_; } + + friend std::size_t hash_value(const Expensive &object) + { return StrHasher()(object.get_key().c_str()); } +}; + +// A set and unordered_set that store Expensive objects +typedef set<Expensive> Set; +typedef unordered_set<Expensive> UnorderedSet; + +// Search functions +Expensive *get_from_set(const char* key, Set &set_object) +{ + Set::iterator it = set_object.find(Expensive(key)); + if( it == set_object.end() ) return 0; + return &*it; +} + +Expensive *get_from_uset(const char* key, UnorderedSet &uset_object) +{ + UnorderedSet::iterator it = uset_object.find(Expensive (key)); + if( it == uset_object.end() ) return 0; + return &*it; +} +//] + +//[doc_assoc_optimized_code_optimized_find +// These compare Expensive and a c-string +struct StrExpComp +{ + bool operator()(const char *str, const Expensive &c) const + { return std::strcmp(str, c.get_key().c_str()) < 0; } + + bool operator()(const Expensive &c, const char *str) const + { return std::strcmp(c.get_key().c_str(), str) < 0; } +}; + +struct StrExpEqual +{ + bool operator()(const char *str, const Expensive &c) const + { return std::strcmp(str, c.get_key().c_str()) == 0; } + + bool operator()(const Expensive &c, const char *str) const + { return std::strcmp(c.get_key().c_str(), str) == 0; } +}; + +// Optimized search functions +Expensive *get_from_set_optimized(const char* key, Set &set_object) +{ + Set::iterator it = set_object.find(key, StrExpComp()); + if( it == set_object.end() ) return 0; + return &*it; +} + +Expensive *get_from_uset_optimized(const char* key, UnorderedSet &uset_object) +{ + UnorderedSet::iterator it = uset_object.find(key, StrHasher(), StrExpEqual()); + if( it == uset_object.end() ) return 0; + return &*it; +} +//] + +//[doc_assoc_optimized_code_normal_insert +// Insertion functions +bool insert_to_set(const char* key, Set &set_object) +{ + Expensive *pobject = new Expensive(key); + bool success = set_object.insert(*pobject).second; + if(!success) delete pobject; + return success; +} + +bool insert_to_uset(const char* key, UnorderedSet &uset_object) +{ + Expensive *pobject = new Expensive(key); + bool success = uset_object.insert(*pobject).second; + if(!success) delete pobject; + return success; +} +//] + +//[doc_assoc_optimized_code_optimized_insert +// Optimized insertion functions +bool insert_to_set_optimized(const char* key, Set &set_object) +{ + Set::insert_commit_data insert_data; + bool success = set_object.insert_check(key, StrExpComp(), insert_data).second; + if(success) set_object.insert_commit(*new Expensive(key), insert_data); + return success; +} + +bool insert_to_uset_optimized(const char* key, UnorderedSet &uset_object) +{ + UnorderedSet::insert_commit_data insert_data; + bool success = uset_object.insert_check + (key, StrHasher(), StrExpEqual(), insert_data).second; + if(success) uset_object.insert_commit(*new Expensive(key), insert_data); + return success; +} +//] + +int main() +{ + Set set; + UnorderedSet::bucket_type buckets[10]; + UnorderedSet unordered_set(UnorderedSet::bucket_traits(buckets, 10)); + + const char * const expensive_key + = "A long string that avoids small string optimization"; + + Expensive value(expensive_key); + + if(get_from_set(expensive_key, set)){ + return 1; + } + + if(get_from_uset(expensive_key, unordered_set)){ + return 1; + } + + if(get_from_set_optimized(expensive_key, set)){ + return 1; + } + + if(get_from_uset_optimized(expensive_key, unordered_set)){ + return 1; + } + + Set::iterator setit = set.insert(value).first; + UnorderedSet::iterator unordered_setit = unordered_set.insert(value).first; + + if(!get_from_set(expensive_key, set)){ + return 1; + } + + if(!get_from_uset(expensive_key, unordered_set)){ + return 1; + } + + if(!get_from_set_optimized(expensive_key, set)){ + return 1; + } + + if(!get_from_uset_optimized(expensive_key, unordered_set)){ + return 1; + } + + set.erase(setit); + unordered_set.erase(unordered_setit); + + if(!insert_to_set(expensive_key, set)){ + return 1; + } + + if(!insert_to_uset(expensive_key, unordered_set)){ + return 1; + } + + { + Expensive *ptr = &*set.begin(); + set.clear(); + delete ptr; + } + + { + Expensive *ptr = &*unordered_set.begin(); + unordered_set.clear(); + delete ptr; + } + + if(!insert_to_set_optimized(expensive_key, set)){ + return 1; + } + + if(!insert_to_uset_optimized(expensive_key, unordered_set)){ + return 1; + } + + { + Expensive *ptr = &*set.begin(); + set.clear(); + delete ptr; + } + + { + Expensive *ptr = &*unordered_set.begin(); + unordered_set.clear(); + delete ptr; + } + + setit = set.insert(value).first; + unordered_setit = unordered_set.insert(value).first; + + if(insert_to_set(expensive_key, set)){ + return 1; + } + + if(insert_to_uset(expensive_key, unordered_set)){ + return 1; + } + + if(insert_to_set_optimized(expensive_key, set)){ + return 1; + } + + if(insert_to_uset_optimized(expensive_key, unordered_set)){ + return 1; + } + + set.erase(value); + unordered_set.erase(value); + + return 0; +} diff --git a/src/boost/libs/intrusive/example/doc_auto_unlink.cpp b/src/boost/libs/intrusive/example/doc_auto_unlink.cpp new file mode 100644 index 000000000..b44dd3113 --- /dev/null +++ b/src/boost/libs/intrusive/example/doc_auto_unlink.cpp @@ -0,0 +1,83 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2006-2013 +// +// 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. +// +///////////////////////////////////////////////////////////////////////////// +//[doc_auto_unlink_code +#include <boost/intrusive/list.hpp> +#include <cassert> + +using namespace boost::intrusive; + +typedef list_base_hook<link_mode<auto_unlink> > auto_unlink_hook; + +class MyClass : public auto_unlink_hook + //This hook removes the node in the destructor +{ + int int_; + + public: + MyClass(int i = 0) : int_(i) {} + int get_int() { return int_; } + void unlink() { auto_unlink_hook::unlink(); } + bool is_linked() { return auto_unlink_hook::is_linked(); } +}; + +//Define a list that will store values using the base hook +//The list can't have constant-time size! +typedef list< MyClass, constant_time_size<false> > List; + +int main() +{ + //Create the list + List l; + { + //Create myclass and check it's linked + MyClass myclass; + assert(myclass.is_linked() == false); + + //Insert the object + l.push_back(myclass); + + //Check that we have inserted the object + assert(l.empty() == false); + assert(&l.front() == &myclass); + assert(myclass.is_linked() == true); + + //Now myclass' destructor will unlink it + //automatically + } + + //Check auto-unlink has been executed + assert(l.empty() == true); + + { + //Now test the unlink() function + + //Create myclass and check it's linked + MyClass myclass; + assert(myclass.is_linked() == false); + + //Insert the object + l.push_back(myclass); + + //Check that we have inserted the object + assert(l.empty() == false); + assert(&l.front() == &myclass); + assert(myclass.is_linked() == true); + + //Now unlink the node + myclass.unlink(); + + //Check auto-unlink has been executed + assert(l.empty() == true); + } + return 0; +} +//] diff --git a/src/boost/libs/intrusive/example/doc_avl_set.cpp b/src/boost/libs/intrusive/example/doc_avl_set.cpp new file mode 100644 index 000000000..ae6768917 --- /dev/null +++ b/src/boost/libs/intrusive/example/doc_avl_set.cpp @@ -0,0 +1,85 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2006-2013 +// +// 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. +// +///////////////////////////////////////////////////////////////////////////// +//[doc_avl_set_code +#include <boost/intrusive/avl_set.hpp> +#include <vector> +#include <functional> +#include <cassert> + +using namespace boost::intrusive; + + //This is a base hook optimized for size +class MyClass : public avl_set_base_hook<optimize_size<true> > +{ + int int_; + + public: + //This is a member hook + avl_set_member_hook<> member_hook_; + + MyClass(int i) + : int_(i) + {} + friend bool operator< (const MyClass &a, const MyClass &b) + { return a.int_ < b.int_; } + friend bool operator> (const MyClass &a, const MyClass &b) + { return a.int_ > b.int_; } + friend bool operator== (const MyClass &a, const MyClass &b) + { return a.int_ == b.int_; } +}; + +//Define an avl_set using the base hook that will store values in reverse order +typedef avl_set< MyClass, compare<std::greater<MyClass> > > BaseSet; + +//Define an multiset using the member hook +typedef member_hook<MyClass, avl_set_member_hook<>, &MyClass::member_hook_> MemberOption; +typedef avl_multiset< MyClass, MemberOption> MemberMultiset; + +int main() +{ + typedef std::vector<MyClass>::iterator VectIt; + + //Create several MyClass objects, each one with a different value + std::vector<MyClass> values; + for(int i = 0; i < 100; ++i) values.push_back(MyClass(i)); + + BaseSet baseset; + MemberMultiset membermultiset; + + //Check that size optimization is activated in the base hook + assert(sizeof(avl_set_base_hook<optimize_size<true> >) == 3*sizeof(void*)); + //Check that size optimization is deactivated in the member hook + assert(sizeof(avl_set_member_hook<>) > 3*sizeof(void*)); + + //Now insert them in the sets + for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it){ + baseset.insert(*it); + membermultiset.insert(*it); + } + + //Now test avl_sets + { + BaseSet::reverse_iterator rbit(baseset.rbegin()); + MemberMultiset::iterator mit(membermultiset.begin()); + VectIt it(values.begin()), itend(values.end()); + + //Test the objects inserted in the base hook avl_set + for(; it != itend; ++it, ++rbit) + if(&*rbit != &*it) return 1; + + //Test the objects inserted in the member hook avl_set + for(it = values.begin(); it != itend; ++it, ++mit) + if(&*mit != &*it) return 1; + } + return 0; +} +//] diff --git a/src/boost/libs/intrusive/example/doc_avltree_algorithms.cpp b/src/boost/libs/intrusive/example/doc_avltree_algorithms.cpp new file mode 100644 index 000000000..d5a71eb8e --- /dev/null +++ b/src/boost/libs/intrusive/example/doc_avltree_algorithms.cpp @@ -0,0 +1,85 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2007-2013 +// +// 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. +// +///////////////////////////////////////////////////////////////////////////// +//[doc_avltree_algorithms_code +#include <boost/intrusive/avltree_algorithms.hpp> +#include <cassert> + +struct my_node +{ + my_node(int i = 0) + : int_(i) + {} + my_node *parent_, *left_, *right_; + int balance_; + //other members + int int_; +}; + +//Define our own avltree_node_traits +struct my_avltree_node_traits +{ + typedef my_node node; + typedef my_node * node_ptr; + typedef const my_node * const_node_ptr; + typedef int balance; + + static node_ptr get_parent(const_node_ptr n) { return n->parent_; } + static void set_parent(node_ptr n, node_ptr parent){ n->parent_ = parent; } + static node_ptr get_left(const_node_ptr n) { return n->left_; } + static void set_left(node_ptr n, node_ptr left) { n->left_ = left; } + static node_ptr get_right(const_node_ptr n) { return n->right_; } + static void set_right(node_ptr n, node_ptr right) { n->right_ = right; } + static balance get_balance(const_node_ptr n) { return n->balance_; } + static void set_balance(node_ptr n, balance b) { n->balance_ = b; } + static balance negative() { return -1; } + static balance zero() { return 0; } + static balance positive() { return 1; } +}; + +struct node_ptr_compare +{ + bool operator()(const my_node *a, const my_node *b) + { return a->int_ < b->int_; } +}; + +int main() +{ + typedef boost::intrusive::avltree_algorithms<my_avltree_node_traits> algo; + my_node header, two(2), three(3); + + //Create an empty avltree container: + //"header" will be the header node of the tree + algo::init_header(&header); + + //Now insert node "two" in the tree using the sorting functor + algo::insert_equal_upper_bound(&header, &two, node_ptr_compare()); + + //Now insert node "three" in the tree using the sorting functor + algo::insert_equal_lower_bound(&header, &three, node_ptr_compare()); + + //Now take the first node (the left node of the header) + my_node *n = header.left_; + assert(n == &two); + + //Now go to the next node + n = algo::next_node(n); + assert(n == &three); + + //Erase a node just using a pointer to it + algo::unlink(&two); + + //Erase a node using also the header (faster) + algo::erase(&header, &three); + return 0; +} + +//] diff --git a/src/boost/libs/intrusive/example/doc_bucket_traits.cpp b/src/boost/libs/intrusive/example/doc_bucket_traits.cpp new file mode 100644 index 000000000..20ce7be92 --- /dev/null +++ b/src/boost/libs/intrusive/example/doc_bucket_traits.cpp @@ -0,0 +1,83 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2007-2013 +// +// 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. +// +///////////////////////////////////////////////////////////////////////////// +//[doc_bucket_traits +#include <boost/intrusive/unordered_set.hpp> +#include <boost/functional/hash.hpp> +#include <vector> + +using namespace boost::intrusive; + +//A class to be inserted in an unordered_set +class MyClass : public unordered_set_base_hook<> +{ + int int_; + + public: + MyClass(int i = 0) : int_(i) + {} + + 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_); } +}; + +//Define the base hook option +typedef base_hook< unordered_set_base_hook<> > BaseHookOption; + +//Obtain the types of the bucket and the bucket pointer +typedef unordered_bucket<BaseHookOption>::type BucketType; +typedef unordered_bucket_ptr<BaseHookOption>::type BucketPtr; + +//The custom bucket traits. +class custom_bucket_traits +{ + public: + static const int NumBuckets = 100; + + custom_bucket_traits(BucketPtr buckets) + : buckets_(buckets) + {} + + //Functions to be implemented by custom bucket traits + BucketPtr bucket_begin() const { return buckets_; } + std::size_t bucket_count() const { return NumBuckets;} + + private: + BucketPtr buckets_; +}; + +//Define the container using the custom bucket traits +typedef unordered_set<MyClass, bucket_traits<custom_bucket_traits> > BucketTraitsUset; + +int main() +{ + typedef std::vector<MyClass>::iterator VectIt; + std::vector<MyClass> values; + + //Fill values + for(int i = 0; i < 100; ++i) values.push_back(MyClass(i)); + + //Now create the bucket array and the custom bucket traits object + BucketType buckets[custom_bucket_traits::NumBuckets]; + custom_bucket_traits btraits(buckets); + + //Now create the unordered set + BucketTraitsUset uset(btraits); + + //Insert the values in the unordered set + for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it) + uset.insert(*it); + + return 0; +} +//] diff --git a/src/boost/libs/intrusive/example/doc_clone_from.cpp b/src/boost/libs/intrusive/example/doc_clone_from.cpp new file mode 100644 index 000000000..eeb844dce --- /dev/null +++ b/src/boost/libs/intrusive/example/doc_clone_from.cpp @@ -0,0 +1,74 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2006-2013 +// +// 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. +// +///////////////////////////////////////////////////////////////////////////// +//[doc_clone_from +#include <boost/intrusive/list.hpp> +#include <iostream> +#include <vector> + +using namespace boost::intrusive; + +//A class that can be inserted in an intrusive list +class my_class : public list_base_hook<> +{ + public: + friend bool operator==(const my_class &a, const my_class &b) + { return a.int_ == b.int_; } + + int int_; + + //... +}; + +//Definition of the intrusive list +typedef list<my_class> my_class_list; + +//Cloner object function +struct new_cloner +{ + my_class *operator()(const my_class &clone_this) + { return new my_class(clone_this); } +}; + +//The disposer object function +struct delete_disposer +{ + void operator()(my_class *delete_this) + { delete delete_this; } +}; + +int main() +{ + const int MaxElem = 100; + std::vector<my_class> nodes(MaxElem); + + //Fill all the nodes and insert them in the list + my_class_list list; + + for(int i = 0; i < MaxElem; ++i) nodes[i].int_ = i; + + list.insert(list.end(), nodes.begin(), nodes.end()); + + //Now clone "list" using "new" and "delete" object functions + my_class_list cloned_list; + cloned_list.clone_from(list, new_cloner(), delete_disposer()); + + //Test that both are equal + if(cloned_list != list) + std::cout << "Both lists are different" << std::endl; + else + std::cout << "Both lists are equal" << std::endl; + + //Don't forget to free the memory from the second list + cloned_list.clear_and_dispose(delete_disposer()); + return 0; +} +//] diff --git a/src/boost/libs/intrusive/example/doc_derivation_value_traits.cpp b/src/boost/libs/intrusive/example/doc_derivation_value_traits.cpp new file mode 100644 index 000000000..c760bb859 --- /dev/null +++ b/src/boost/libs/intrusive/example/doc_derivation_value_traits.cpp @@ -0,0 +1,94 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2006-2014 +// +// 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/link_mode.hpp> +#include <boost/intrusive/list.hpp> +#include <boost/intrusive/derivation_value_traits.hpp> +#include <vector> + +struct simple_node +{ + simple_node *prev_; + simple_node *next_; +}; + +//Define the node traits. A single node_traits will be enough. +struct simple_node_traits +{ + typedef simple_node node; + typedef node * node_ptr; + typedef const node * const_node_ptr; + static node *get_next(const node *n) { return n->next_; } + static void set_next(node *n, node *next) { n->next_ = next; } + static node *get_previous(const node *n) { return n->prev_; } + static void set_previous(node *n, node *prev) { n->prev_ = prev; } +}; + +//[doc_derivation_value_traits_value_traits +class base_1{}; +class base_2{}; + +struct value_1 : public base_1, public simple_node +{ + int id_; + simple_node node_; +}; + +struct value_2 : public base_1, public base_2, public simple_node +{ + simple_node node_; + float id_; +}; + +using namespace boost::intrusive; + +//Now define the needed value traits using derivation_value_traits +typedef derivation_value_traits<value_1, simple_node_traits, normal_link> ValueTraits1; +typedef derivation_value_traits<value_2, simple_node_traits, normal_link> ValueTraits2; + +//Now define two intrusive lists. Both lists will use the same algorithms: +// circular_list_algorithms<simple_node_traits> +typedef list <value_1, value_traits<ValueTraits1> > Value1List; +typedef list <value_2, value_traits<ValueTraits2> > Value2List; +//] + +//[doc_derivation_value_traits_test +int main() +{ + typedef std::vector<value_1> Vect1; + typedef std::vector<value_2> Vect2; + + //Create values, with a different internal number + Vect1 values1; + Vect2 values2; + for(int i = 0; i < 100; ++i){ + value_1 v1; v1.id_ = i; values1.push_back(v1); + value_2 v2; v2.id_ = (float)i; values2.push_back(v2); + } + + //Create the lists with the objects + Value1List list1(values1.begin(), values1.end()); + Value2List list2(values2.begin(), values2.end()); + + //Now test both lists + Value1List::const_iterator bit1(list1.begin()), bitend1(list1.end()); + Value2List::const_iterator bit2(list2.begin()), bitend2(list2.end()); + + Vect1::const_iterator it1(values1.begin()), itend1(values1.end()); + Vect2::const_iterator it2(values2.begin()), itend2(values2.end()); + + //Test the objects inserted in our lists + for(; it1 != itend1; ++it1, ++bit1, ++it2, ++bit2){ + if(&*bit1 != &*it1 || &*bit2 != &*it2) return 1; + } + return 0; +} +//] diff --git a/src/boost/libs/intrusive/example/doc_entity.cpp b/src/boost/libs/intrusive/example/doc_entity.cpp new file mode 100644 index 000000000..531f2294c --- /dev/null +++ b/src/boost/libs/intrusive/example/doc_entity.cpp @@ -0,0 +1,60 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2006-2013 +// +// 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. +// +///////////////////////////////////////////////////////////////////////////// +//[doc_entity_code +#include <boost/intrusive/list.hpp> + +using namespace boost::intrusive; + +//A class that can be inserted in an intrusive list +class entity : public list_base_hook<> +{ + public: + virtual ~entity(); + //... +}; + +//"some_entity" derives from "entity" +class some_entity : public entity +{/**/}; + +//Definition of the intrusive list +struct entity_list : list<entity> +{ + ~entity_list() + { + // entity's destructor removes itself from the global list implicitly + while (!this->empty()) + delete &this->front(); + } +}; + +//A global list +entity_list global_list; + +//The destructor removes itself from the global list +entity::~entity() +{ global_list.erase(entity_list::s_iterator_to(*this)); } + +//Function to insert a new "some_entity" in the global list +void insert_some_entity() +{ global_list.push_back (*new some_entity(/*...*/)); } + +int main() +{ + //Insert some new entities + insert_some_entity(); + insert_some_entity(); + //global_list's destructor will free objects + return 0; +} + +//] diff --git a/src/boost/libs/intrusive/example/doc_erasing_and_disposing.cpp b/src/boost/libs/intrusive/example/doc_erasing_and_disposing.cpp new file mode 100644 index 000000000..7ac20e814 --- /dev/null +++ b/src/boost/libs/intrusive/example/doc_erasing_and_disposing.cpp @@ -0,0 +1,98 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2006-2014 +// +// 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/core/no_exceptions_support.hpp> +//[doc_erasing_and_disposing +#include <boost/intrusive/list.hpp> + +using namespace boost::intrusive; + +//A class that can be inserted in an intrusive list +class my_class : public list_base_hook<> +{ + public: + my_class(int i) + : int_(i) + {} + + int int_; + //... +}; + +//Definition of the intrusive list +typedef list<my_class> my_class_list; + +//The predicate function +struct is_even +{ + bool operator()(const my_class &c) const + { return 0 == (c.int_ % 2); } +}; + +//The disposer object function +struct delete_disposer +{ + void operator()(my_class *delete_this) + { delete delete_this; } +}; + +int main() +{ + const int MaxElem = 100; + + //Fill all the nodes and insert them in the list + my_class_list list; + + //<- + #if 1 + BOOST_TRY{ + #else + //-> + try{ + //<- + #endif + //-> + //Insert new objects in the container + for(int i = 0; i < MaxElem; ++i) list.push_back(*new my_class(i)); + + //Now use remove_and_dispose_if to erase and delete the objects + list.remove_and_dispose_if(is_even(), delete_disposer()); + } + //<- + #if 1 + BOOST_CATCH(...){ + #else + //-> + catch(...){ + //<- + #endif + //-> + //If something throws, make sure that all the memory is freed + list.clear_and_dispose(delete_disposer()); + //<- + #if 1 + BOOST_RETHROW + #else + //-> + throw; + //<- + #endif + //-> + } + //<- + BOOST_CATCH_END + //-> + + //Dispose remaining elements + list.erase_and_dispose(list.begin(), list.end(), delete_disposer()); + return 0; +} +//] diff --git a/src/boost/libs/intrusive/example/doc_function_hooks.cpp b/src/boost/libs/intrusive/example/doc_function_hooks.cpp new file mode 100644 index 000000000..5c7781c9e --- /dev/null +++ b/src/boost/libs/intrusive/example/doc_function_hooks.cpp @@ -0,0 +1,73 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2010-2013 +// +// 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. +// +///////////////////////////////////////////////////////////////////////////// +//[doc_function_hooks +#include <boost/intrusive/list.hpp> +#include <boost/intrusive/parent_from_member.hpp> + +using namespace boost::intrusive; + +struct MyClass +{ + int dummy; + //This internal type has a member hook + struct InnerNode + { + int dummy; + list_member_hook<> hook; + } inner; +}; + +//This functor converts between MyClass and InnerNode's member hook +struct Functor +{ + //Required types + typedef list_member_hook<> hook_type; + typedef hook_type* hook_ptr; + typedef const hook_type* const_hook_ptr; + typedef MyClass value_type; + typedef value_type* pointer; + typedef const value_type* const_pointer; + + //Required static functions + static hook_ptr to_hook_ptr (value_type &value) + { return &value.inner.hook; } + static const_hook_ptr to_hook_ptr(const value_type &value) + { return &value.inner.hook; } + static pointer to_value_ptr(hook_ptr n) + { + return get_parent_from_member<MyClass> + (get_parent_from_member<MyClass::InnerNode>(n, &MyClass::InnerNode::hook) + ,&MyClass::inner + ); + } + static const_pointer to_value_ptr(const_hook_ptr n) + { + return get_parent_from_member<MyClass> + (get_parent_from_member<MyClass::InnerNode>(n, &MyClass::InnerNode::hook) + ,&MyClass::inner + ); + } +}; + +//Define a list that will use the hook accessed through the function object +typedef list< MyClass, function_hook< Functor> > List; + +int main() +{ + MyClass n; + List l; + //Insert the node in both lists + l.insert(l.begin(), n); + assert(l.size() == 1); + return 0; +} +//] diff --git a/src/boost/libs/intrusive/example/doc_how_to_use.cpp b/src/boost/libs/intrusive/example/doc_how_to_use.cpp new file mode 100644 index 000000000..22ea3fdf8 --- /dev/null +++ b/src/boost/libs/intrusive/example/doc_how_to_use.cpp @@ -0,0 +1,77 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2006-2013 +// +// 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. +// +///////////////////////////////////////////////////////////////////////////// +//[doc_how_to_use_code +#include <boost/intrusive/list.hpp> +#include <vector> + +using namespace boost::intrusive; + +class MyClass : public list_base_hook<> +{ + int int_; + + public: + list_member_hook<> member_hook_; + + MyClass(int i) : int_(i) {} + //<- + int get_int() const { return int_; } + //-> +}; + +//Define a list that will store MyClass using the base hook +typedef list<MyClass> BaseList; + +//Define a list that will store MyClass using the member hook +typedef member_hook + < MyClass, list_member_hook<>, &MyClass::member_hook_> MemberOption; +typedef list<MyClass, MemberOption> MemberList; + +int main() +{ + typedef std::vector<MyClass>::iterator VectIt; + + //Create several MyClass objects, each one with a different value + std::vector<MyClass> values; + for(int i = 0; i < 100; ++i) values.push_back(MyClass(i)); + + BaseList baselist; + MemberList memberlist; + + //Now insert them in the reverse order in the base hook list + for(VectIt it(values.begin()), itend(values.end()) + ; it != itend ; ++it){ + baselist.push_front(*it); + } + + //Now insert them in the same order as in vector in the member hook list + for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it) + memberlist.push_back(*it); + + //Now test lists + { + BaseList::reverse_iterator rbit(baselist.rbegin()); + MemberList::iterator mit(memberlist.begin()); + VectIt it(values.begin()), itend(values.end()); + + //Test the objects inserted in the base hook list + for(; it != itend; ++it, ++rbit) + if(&*rbit != &*it) return 1; + + //Test the objects inserted in the member hook list + for(it = values.begin(); it != itend; ++it, ++mit) + if(&*mit != &*it) return 1; + } + + return 0; +} +//] diff --git a/src/boost/libs/intrusive/example/doc_iterator_from_value.cpp b/src/boost/libs/intrusive/example/doc_iterator_from_value.cpp new file mode 100644 index 000000000..f9c1a9a3e --- /dev/null +++ b/src/boost/libs/intrusive/example/doc_iterator_from_value.cpp @@ -0,0 +1,97 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2006-2013 +// +// 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. +// +///////////////////////////////////////////////////////////////////////////// +//[doc_iterator_from_value +#include <boost/intrusive/list.hpp> +#include <boost/intrusive/unordered_set.hpp> +#include <boost/functional/hash.hpp> +#include <vector> + +using namespace boost::intrusive; + +class intrusive_data +{ + int data_id_; + public: + + void set(int id) { data_id_ = id; } + + //This class can be inserted in an intrusive list + list_member_hook<> list_hook_; + + //This class can be inserted in an intrusive unordered_set + unordered_set_member_hook<> unordered_set_hook_; + + //Comparison operators + friend bool operator==(const intrusive_data &a, const intrusive_data &b) + { return a.data_id_ == b.data_id_; } + + friend bool operator!=(const intrusive_data &a, const intrusive_data &b) + { return a.data_id_ != b.data_id_; } + + //The hash function + friend std::size_t hash_value(const intrusive_data &i) + { return boost::hash<int>()(i.data_id_); } +}; + +//Definition of the intrusive list that will hold intrusive_data +typedef member_hook<intrusive_data, list_member_hook<> + , &intrusive_data::list_hook_> MemberListOption; +typedef list<intrusive_data, MemberListOption> list_t; + +//Definition of the intrusive unordered_set that will hold intrusive_data +typedef member_hook + < intrusive_data, unordered_set_member_hook<> + , &intrusive_data::unordered_set_hook_> MemberUsetOption; +typedef boost::intrusive::unordered_set + < intrusive_data, MemberUsetOption> unordered_set_t; + +int main() +{ + //Create MaxElem objects + const int MaxElem = 100; + std::vector<intrusive_data> nodes(MaxElem); + + //Declare the intrusive containers + list_t list; + unordered_set_t::bucket_type buckets[MaxElem]; + unordered_set_t unordered_set + (unordered_set_t::bucket_traits(buckets, MaxElem)); + + //Initialize all the nodes + for(int i = 0; i < MaxElem; ++i) nodes[i].set(i); + + //Now insert them in both intrusive containers + list.insert(list.end(), nodes.begin(), nodes.end()); + unordered_set.insert(nodes.begin(), nodes.end()); + + //Now check the iterator_to function + list_t::iterator list_it(list.begin()); + for(int i = 0; i < MaxElem; ++i, ++list_it) + if(list.iterator_to(nodes[i]) != list_it || + list_t::s_iterator_to(nodes[i]) != list_it) + return 1; + + //Now check unordered_set::s_iterator_to (which is a member function) + //and unordered_set::s_local_iterator_to (which is an static member function) + unordered_set_t::iterator unordered_set_it(unordered_set.begin()); + for(int i = 0; i < MaxElem; ++i){ + unordered_set_it = unordered_set.find(nodes[i]); + if(unordered_set.iterator_to(nodes[i]) != unordered_set_it) + return 1; + if(*unordered_set.local_iterator_to(nodes[i]) != *unordered_set_it || + *unordered_set_t::s_local_iterator_to(nodes[i]) != *unordered_set_it ) + return 1; + } + + return 0; +} +//] diff --git a/src/boost/libs/intrusive/example/doc_list.cpp b/src/boost/libs/intrusive/example/doc_list.cpp new file mode 100644 index 000000000..ec5693a5a --- /dev/null +++ b/src/boost/libs/intrusive/example/doc_list.cpp @@ -0,0 +1,78 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2006-2013 +// +// 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. +// +///////////////////////////////////////////////////////////////////////////// +//[doc_list_code +#include <boost/intrusive/list.hpp> +#include <vector> + +using namespace boost::intrusive; + +class MyClass : public list_base_hook<> //This is a derivation hook +{ + int int_; + + public: + //This is a member hook + list_member_hook<> member_hook_; + + MyClass(int i) + : int_(i) + {} + //<- + int get_int() const { return int_; } + //-> +}; + +//Define a list that will store MyClass using the public base hook +typedef list<MyClass> BaseList; + +//Define a list that will store MyClass using the public member hook +typedef list< MyClass + , member_hook< MyClass, list_member_hook<>, &MyClass::member_hook_> + > MemberList; + +int main() +{ + typedef std::vector<MyClass>::iterator VectIt; + + //Create several MyClass objects, each one with a different value + std::vector<MyClass> values; + for(int i = 0; i < 100; ++i) values.push_back(MyClass(i)); + + BaseList baselist; + MemberList memberlist; + + //Now insert them in the reverse order in the base hook list + for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it) + baselist.push_front(*it); + + //Now insert them in the same order as in vector in the member hook list + for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it) + memberlist.push_back(*it); + + //Now test lists + { + BaseList::reverse_iterator rbit(baselist.rbegin()); + MemberList::iterator mit(memberlist.begin()); + VectIt it(values.begin()), itend(values.end()); + + //Test the objects inserted in the base hook list + for(; it != itend; ++it, ++rbit) + if(&*rbit != &*it) return 1; + + //Test the objects inserted in the member hook list + for(it = values.begin(); it != itend; ++it, ++mit) + if(&*mit != &*it) return 1; + } + + return 0; +} +//] diff --git a/src/boost/libs/intrusive/example/doc_list_algorithms.cpp b/src/boost/libs/intrusive/example/doc_list_algorithms.cpp new file mode 100644 index 000000000..fbb600ee2 --- /dev/null +++ b/src/boost/libs/intrusive/example/doc_list_algorithms.cpp @@ -0,0 +1,66 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2006-2013 +// +// 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. +// +///////////////////////////////////////////////////////////////////////////// +//[doc_list_algorithms_code +#include <boost/intrusive/circular_list_algorithms.hpp> +#include <cassert> + +struct my_node +{ + my_node *next_, *prev_; + //other members... +}; + +//Define our own list_node_traits +struct my_list_node_traits +{ + typedef my_node node; + typedef my_node * node_ptr; + typedef const my_node * const_node_ptr; + static node_ptr get_next(const_node_ptr n) { return n->next_; } + static void set_next(node_ptr n, node_ptr next) { n->next_ = next; } + static node *get_previous(const_node_ptr n) { return n->prev_; } + static void set_previous(node_ptr n, node_ptr prev){ n->prev_ = prev; } +}; + +int main() +{ + typedef boost::intrusive::circular_list_algorithms<my_list_node_traits> algo; + my_node one, two, three; + + //Create an empty doubly linked list container: + //"one" will be the first node of the container + algo::init_header(&one); + assert(algo::count(&one) == 1); + + //Now add a new node before "one" + algo::link_before(&one, &two); + assert(algo::count(&one) == 2); + + //Now add a new node after "two" + algo::link_after(&two, &three); + assert(algo::count(&one) == 3); + + //Now unlink the node after one + algo::unlink(&three); + assert(algo::count(&one) == 2); + + //Now unlink two + algo::unlink(&two); + assert(algo::count(&one) == 1); + + //Now unlink one + algo::unlink(&one); + assert(algo::count(&one) == 1); + + return 0; +} +//] diff --git a/src/boost/libs/intrusive/example/doc_map.cpp b/src/boost/libs/intrusive/example/doc_map.cpp new file mode 100644 index 000000000..41983047b --- /dev/null +++ b/src/boost/libs/intrusive/example/doc_map.cpp @@ -0,0 +1,84 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2015-2015 +// +// 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. +// +///////////////////////////////////////////////////////////////////////////// +//[doc_map_code +#include <boost/static_assert.hpp> +#include <boost/type_traits/is_same.hpp> +#include <boost/intrusive/set.hpp> +#include <boost/intrusive/unordered_set.hpp> +#include <vector> +#include <cassert> + +using namespace boost::intrusive; + +class MyClass : public set_base_hook<> + , public unordered_set_base_hook<> +{ + public: + int first; + explicit MyClass(int i) : first(i){} +}; + +//key_of_value function object, must: +//- be default constructible if the container constructor requires it +//- define the key type using "type" +//- define an operator() taking "const value_type&" and +// returning "type" or "const type &" +struct first_int_is_key +{ + typedef int type; + + const type & operator()(const MyClass& v) const + { return v.first; } +}; + +//Define omap like ordered and unordered classes +typedef set< MyClass, key_of_value<first_int_is_key> > OrderedMap; +typedef unordered_set< MyClass, key_of_value<first_int_is_key> > UnorderedMap; + +int main() +{ + BOOST_STATIC_ASSERT((boost::is_same< OrderedMap::key_type, int>::value)); + BOOST_STATIC_ASSERT((boost::is_same<UnorderedMap::key_type, int>::value)); + + //Create several MyClass objects, each one with a different value + //and insert them into the omap + std::vector<MyClass> values; + for(int i = 0; i < 100; ++i) values.push_back(MyClass(i)); + + //Create ordered/unordered maps and insert values + OrderedMap omap(values.begin(), values.end()); + UnorderedMap::bucket_type buckets[100]; + UnorderedMap umap(values.begin(), values.end(), UnorderedMap::bucket_traits(buckets, 100)); + + //Test each element using the key_type (int) + for(int i = 0; i != 100; ++i){ + assert(omap.find(i) != omap.end()); + assert(umap.find(i) != umap.end()); + assert(omap.lower_bound(i) != omap.end()); + assert(++omap.lower_bound(i) == omap.upper_bound(i)); + assert(omap.equal_range(i).first != omap.equal_range(i).second); + assert(umap.equal_range(i).first != umap.equal_range(i).second); + } + + //Count and erase by key + for(int i = 0; i != 100; ++i){ + assert(1 == omap.count(i)); + assert(1 == umap.count(i)); + assert(1 == omap.erase(i)); + assert(1 == umap.erase(i)); + } + assert(omap.empty()); + assert(umap.empty()); + + return 0; +} +//] diff --git a/src/boost/libs/intrusive/example/doc_member_value_traits.cpp b/src/boost/libs/intrusive/example/doc_member_value_traits.cpp new file mode 100644 index 000000000..37886dd43 --- /dev/null +++ b/src/boost/libs/intrusive/example/doc_member_value_traits.cpp @@ -0,0 +1,95 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2006-2014 +// +// 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/link_mode.hpp> +#include <boost/intrusive/list.hpp> +#include <boost/intrusive/member_value_traits.hpp> +#include <vector> + +struct simple_node +{ + simple_node *prev_; + simple_node *next_; +}; + +//Define the node traits. A single node_traits will be enough. +struct simple_node_traits +{ + typedef simple_node node; + typedef node * node_ptr; + typedef const node * const_node_ptr; + static node *get_next(const node *n) { return n->next_; } + static void set_next(node *n, node *next) { n->next_ = next; } + static node *get_previous(const node *n) { return n->prev_; } + static void set_previous(node *n, node *prev) { n->prev_ = prev; } +}; + +//[doc_member_value_traits_value_traits +class base_1{}; +class base_2{}; + +struct value_1 : public base_1, public simple_node +{ + int id_; + simple_node node_; +}; + +struct value_2 : public base_1, public base_2, public simple_node +{ + simple_node node_; + float id_; +}; + +using namespace boost::intrusive; + +typedef member_value_traits + <value_1, simple_node_traits, &value_1::node_, normal_link> ValueTraits1; +typedef member_value_traits +<value_2, simple_node_traits, &value_2::node_, normal_link> ValueTraits2; + +//Now define two intrusive lists. Both lists will use the same algorithms: +// circular_list_algorithms<simple_node_traits> +typedef list <value_1, value_traits<ValueTraits1> > Value1List; +typedef list <value_2, value_traits<ValueTraits2> > Value2List; +//] + +//[doc_member_value_traits_test +int main() +{ + typedef std::vector<value_1> Vect1; + typedef std::vector<value_2> Vect2; + + //Create values, with a different internal number + Vect1 values1; + Vect2 values2; + for(int i = 0; i < 100; ++i){ + value_1 v1; v1.id_ = i; values1.push_back(v1); + value_2 v2; v2.id_ = (float)i; values2.push_back(v2); + } + + //Create the lists with the objects + Value1List list1(values1.begin(), values1.end()); + Value2List list2(values2.begin(), values2.end()); + + //Now test both lists + Value1List::const_iterator bit1(list1.begin()), bitend1(list1.end()); + Value2List::const_iterator bit2(list2.begin()), bitend2(list2.end()); + + Vect1::const_iterator it1(values1.begin()), itend1(values1.end()); + Vect2::const_iterator it2(values2.begin()), itend2(values2.end()); + + //Test the objects inserted in our lists + for(; it1 != itend1; ++it1, ++bit1, ++it2, ++bit2){ + if(&*bit1 != &*it1 || &*bit2 != &*it2) return 1; + } + return 0; +} +//] diff --git a/src/boost/libs/intrusive/example/doc_offset_ptr.cpp b/src/boost/libs/intrusive/example/doc_offset_ptr.cpp new file mode 100644 index 000000000..f285ac7a2 --- /dev/null +++ b/src/boost/libs/intrusive/example/doc_offset_ptr.cpp @@ -0,0 +1,116 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2006-2013 +// +// 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/config.hpp> + +#ifdef BOOST_NO_EXCEPTIONS + +//Interprocess does not support BOOST_NO_EXCEPTIONS so nothing to test here +int main() +{ + return 0; +} + +#else //!BOOST_NO_EXCEPTIONS + +//This is needed to allow concurrent test execution in +//several platforms. The shared memory must be unique +//for each process... +#include <boost/interprocess/detail/os_thread_functions.hpp> +#include <sstream> + +const char *get_shared_memory_name() +{ + std::stringstream s; + s << "process_" << boost::interprocess::ipcdetail::get_current_process_id(); + static std::string str = s.str(); + return str.c_str(); +} + +//[doc_offset_ptr_0 +#include <boost/intrusive/list.hpp> +#include <boost/interprocess/offset_ptr.hpp> + +using namespace boost::intrusive; +namespace ip = boost::interprocess; + +class shared_memory_data + //Declare the hook with an offset_ptr from Boost.Interprocess + //to make this class compatible with shared memory + : public list_base_hook< void_pointer< ip::offset_ptr<void> > > +{ + int data_id_; + public: + + int get() const { return data_id_; } + void set(int id) { data_id_ = id; } +}; +//] + +//[doc_offset_ptr_1 +#include <boost/interprocess/managed_shared_memory.hpp> +#include <boost/interprocess/containers/vector.hpp> +#include <boost/interprocess/allocators/allocator.hpp> + +//Definition of the shared memory friendly intrusive list +typedef list<shared_memory_data> intrusive_list_t; + +int main() +{ + //Now create an intrusive list in shared memory: + //nodes and the container itself must be created in shared memory + const int MaxElem = 100; + const int ShmSize = 50000; + const char *ShmName = get_shared_memory_name(); + { + //Erase all old shared memory + ip::shared_memory_object::remove(ShmName); + ip::managed_shared_memory shm(ip::create_only, ShmName, ShmSize); + + //Create all nodes in shared memory using a shared memory vector + //See Boost.Interprocess documentation for more information on this + typedef ip::allocator + < shared_memory_data, ip::managed_shared_memory::segment_manager> + shm_allocator_t; + typedef ip::vector<shared_memory_data, shm_allocator_t> shm_vector_t; + shm_allocator_t shm_alloc(shm.get_segment_manager()); + shm_vector_t *pshm_vect = + shm.construct<shm_vector_t>(ip::anonymous_instance)(shm_alloc); + pshm_vect->resize(MaxElem); + + //Initialize all the nodes + for(int i = 0; i < MaxElem; ++i) (*pshm_vect)[i].set(i); + + //Now create the shared memory intrusive list + intrusive_list_t *plist = shm.construct<intrusive_list_t>(ip::anonymous_instance)(); + + //Insert objects stored in shared memory vector in the intrusive list + plist->insert(plist->end(), pshm_vect->begin(), pshm_vect->end()); + + //Check all the inserted nodes + int checker = 0; + for( intrusive_list_t::const_iterator it = plist->begin(), itend(plist->end()) + ; it != itend; ++it, ++checker){ + if(it->get() != checker) return 1; + } + + //Now delete the list and after that, the nodes + shm.destroy_ptr(plist); + shm.destroy_ptr(pshm_vect); + } + ip::shared_memory_object::remove(ShmName); + return 0; +} +//] + +#endif //BOOST_NO_EXCEPTIONS + diff --git a/src/boost/libs/intrusive/example/doc_positional_insertion.cpp b/src/boost/libs/intrusive/example/doc_positional_insertion.cpp new file mode 100644 index 000000000..5d628a0eb --- /dev/null +++ b/src/boost/libs/intrusive/example/doc_positional_insertion.cpp @@ -0,0 +1,74 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2009-2013 +// +// 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. +// +///////////////////////////////////////////////////////////////////////////// +//[doc_positional_insertion +#include <boost/intrusive/set.hpp> +#include <vector> +#include <functional> +#include <cassert> + +using namespace boost::intrusive; + +//A simple class with a set hook +class MyClass : public set_base_hook<> +{ + public: + int int_; + + MyClass(int i) : int_(i) {} + friend bool operator< (const MyClass &a, const MyClass &b) + { return a.int_ < b.int_; } + friend bool operator> (const MyClass &a, const MyClass &b) + { return a.int_ > b.int_; } +}; + +int main() +{ + //Create some ORDERED elements + std::vector<MyClass> values; + for(int i = 0; i < 100; ++i) values.push_back(MyClass(i)); + + { //Data is naturally ordered in the vector with the same criteria + //as multiset's comparison predicate, so we can just push back + //all elements, which is more efficient than normal insertion + multiset<MyClass> mset; + for(int i = 0; i < 100; ++i) mset.push_back(values[i]); + + //Now check orderd invariant + multiset<MyClass>::const_iterator next(mset.cbegin()), it(next++); + for(int i = 0; i < 99; ++i, ++it, ++next) assert(*it < *next); + } + { //Now the correct order for the set is the reverse order + //so let's push front all elements + multiset<MyClass, compare< std::greater<MyClass> > > mset; + for(int i = 0; i < 100; ++i) mset.push_front(values[i]); + + //Now check orderd invariant + multiset<MyClass, compare< std::greater<MyClass> > >:: + const_iterator next(mset.cbegin()), it(next++); + for(int i = 0; i < 99; ++i, ++it, ++next) assert(*it > *next); + } + { //Now push the first and the last and insert the rest + //before the last position using "insert_before" + multiset<MyClass> mset; + mset.insert_before(mset.begin(), values[0]); + multiset<MyClass>::const_iterator pos = + mset.insert_before(mset.end(), values[99]); + for(int i = 1; i < 99; ++i) mset.insert_before(pos, values[i]); + + //Now check orderd invariant + multiset<MyClass>::const_iterator next(mset.cbegin()), it(next++); + for(int i = 0; i < 99; ++i, ++it, ++next) assert(*it < *next); + } + + return 0; +} +//] diff --git a/src/boost/libs/intrusive/example/doc_rbtree_algorithms.cpp b/src/boost/libs/intrusive/example/doc_rbtree_algorithms.cpp new file mode 100644 index 000000000..db5cb2af4 --- /dev/null +++ b/src/boost/libs/intrusive/example/doc_rbtree_algorithms.cpp @@ -0,0 +1,83 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2006-2013 +// +// 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. +// +///////////////////////////////////////////////////////////////////////////// +//[doc_rbtree_algorithms_code +#include <boost/intrusive/rbtree_algorithms.hpp> +#include <cassert> + +struct my_node +{ + my_node(int i = 0) + : int_(i) + {} + my_node *parent_, *left_, *right_; + int color_; + //other members + int int_; +}; + +//Define our own rbtree_node_traits +struct my_rbtree_node_traits +{ + typedef my_node node; + typedef my_node * node_ptr; + typedef const my_node * const_node_ptr; + typedef int color; + static node_ptr get_parent(const_node_ptr n) { return n->parent_; } + static void set_parent(node_ptr n, node_ptr parent){ n->parent_ = parent; } + static node_ptr get_left(const_node_ptr n) { return n->left_; } + static void set_left(node_ptr n, node_ptr left) { n->left_ = left; } + static node_ptr get_right(const_node_ptr n) { return n->right_; } + static void set_right(node_ptr n, node_ptr right) { n->right_ = right; } + static color get_color(const_node_ptr n) { return n->color_; } + static void set_color(node_ptr n, color c) { n->color_ = c; } + static color black() { return color(0); } + static color red() { return color(1); } +}; + +struct node_ptr_compare +{ + bool operator()(const my_node *a, const my_node *b) + { return a->int_ < b->int_; } +}; + +int main() +{ + typedef boost::intrusive::rbtree_algorithms<my_rbtree_node_traits> algo; + my_node header, two(2), three(3); + + //Create an empty rbtree container: + //"header" will be the header node of the tree + algo::init_header(&header); + + //Now insert node "two" in the tree using the sorting functor + algo::insert_equal_upper_bound(&header, &two, node_ptr_compare()); + + //Now insert node "three" in the tree using the sorting functor + algo::insert_equal_lower_bound(&header, &three, node_ptr_compare()); + + //Now take the first node (the left node of the header) + my_node *n = header.left_; + assert(n == &two); + + //Now go to the next node + n = algo::next_node(n); + assert(n == &three); + + //Erase a node just using a pointer to it + algo::unlink(&two); + + //Erase a node using also the header (faster) + algo::erase(&header, &three); + return 0; +} + +//] diff --git a/src/boost/libs/intrusive/example/doc_recursive.cpp b/src/boost/libs/intrusive/example/doc_recursive.cpp new file mode 100644 index 000000000..def4b2835 --- /dev/null +++ b/src/boost/libs/intrusive/example/doc_recursive.cpp @@ -0,0 +1,53 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2006-2013 +// +// 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. +// +///////////////////////////////////////////////////////////////////////////// +//[doc_recursive +#include <boost/intrusive/list.hpp> +#include <cassert> + +using namespace boost::intrusive; + +typedef list_base_hook<> BaseHook; + +//A recursive class +class Recursive : public BaseHook +{ + private: + Recursive(const Recursive&); + Recursive & operator=(const Recursive&); + + public: + Recursive() : BaseHook(), children(){} + list< Recursive, base_hook<BaseHook> > children; +}; + +int main() +{ + Recursive f, f2; + //A recursive list of Recursive + list< Recursive, base_hook<BaseHook> > l; + + //Insert a node in parent list + l.insert(l.begin(), f); + + //Insert a node in child list + l.begin()->children.insert(l.begin()->children.begin(), f2); + + //Objects properly inserted + assert(l.size() == l.begin()->children.size()); + assert(l.size() == 1); + + //Clear both lists + l.begin()->children.clear(); + l.clear(); + return 0; +} +//] diff --git a/src/boost/libs/intrusive/example/doc_recursive_member.cpp b/src/boost/libs/intrusive/example/doc_recursive_member.cpp new file mode 100644 index 000000000..27aa08740 --- /dev/null +++ b/src/boost/libs/intrusive/example/doc_recursive_member.cpp @@ -0,0 +1,83 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2010-2013 +// +// 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. +// +///////////////////////////////////////////////////////////////////////////// +//[doc_recursive_member +#include <boost/intrusive/list.hpp> +#include <boost/intrusive/parent_from_member.hpp> + +using namespace boost::intrusive; + +class Recursive; + +//Declaration of the functor that converts betwen the Recursive +//class and the hook +struct Functor +{ + //Required types + typedef list_member_hook<> hook_type; + typedef hook_type* hook_ptr; + typedef const hook_type* const_hook_ptr; + typedef Recursive value_type; + typedef value_type* pointer; + typedef const value_type* const_pointer; + + //Required static functions + static hook_ptr to_hook_ptr (value_type &value); + static const_hook_ptr to_hook_ptr(const value_type &value); + static pointer to_value_ptr(hook_ptr n); + static const_pointer to_value_ptr(const_hook_ptr n); +}; + +//Define the recursive class +class Recursive +{ + private: + Recursive(const Recursive&); + Recursive & operator=(const Recursive&); + + public: + Recursive() : hook(), children() {} + list_member_hook<> hook; + list< Recursive, function_hook< Functor> > children; +}; + +//Definition of Functor functions +inline Functor::hook_ptr Functor::to_hook_ptr (Functor::value_type &value) + { return &value.hook; } +inline Functor::const_hook_ptr Functor::to_hook_ptr(const Functor::value_type &value) + { return &value.hook; } +inline Functor::pointer Functor::to_value_ptr(Functor::hook_ptr n) + { return get_parent_from_member<Recursive>(n, &Recursive::hook); } +inline Functor::const_pointer Functor::to_value_ptr(Functor::const_hook_ptr n) + { return get_parent_from_member<Recursive>(n, &Recursive::hook); } + +int main() +{ + Recursive f, f2; + //A recursive list of Recursive + list< Recursive, function_hook< Functor> > l; + + //Insert a node in parent list + l.insert(l.begin(), f); + + //Insert a node in child list + l.begin()->children.insert(l.begin()->children.begin(), f2); + + //Objects properly inserted + assert(l.size() == l.begin()->children.size()); + assert(l.size() == 1); + + //Clear both lists + l.begin()->children.clear(); + l.clear(); + return 0; +} +//] diff --git a/src/boost/libs/intrusive/example/doc_set.cpp b/src/boost/libs/intrusive/example/doc_set.cpp new file mode 100644 index 000000000..dae81abc7 --- /dev/null +++ b/src/boost/libs/intrusive/example/doc_set.cpp @@ -0,0 +1,85 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2006-2013 +// +// 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. +// +///////////////////////////////////////////////////////////////////////////// +//[doc_set_code +#include <boost/intrusive/set.hpp> +#include <vector> +#include <functional> +#include <cassert> + +using namespace boost::intrusive; + + //This is a base hook optimized for size +class MyClass : public set_base_hook<optimize_size<true> > +{ + int int_; + + public: + //This is a member hook + set_member_hook<> member_hook_; + + MyClass(int i) + : int_(i) + {} + friend bool operator< (const MyClass &a, const MyClass &b) + { return a.int_ < b.int_; } + friend bool operator> (const MyClass &a, const MyClass &b) + { return a.int_ > b.int_; } + friend bool operator== (const MyClass &a, const MyClass &b) + { return a.int_ == b.int_; } +}; + +//Define a set using the base hook that will store values in reverse order +typedef set< MyClass, compare<std::greater<MyClass> > > BaseSet; + +//Define an multiset using the member hook +typedef member_hook<MyClass, set_member_hook<>, &MyClass::member_hook_> MemberOption; +typedef multiset< MyClass, MemberOption> MemberMultiset; + +int main() +{ + typedef std::vector<MyClass>::iterator VectIt; + + //Create several MyClass objects, each one with a different value + std::vector<MyClass> values; + for(int i = 0; i < 100; ++i) values.push_back(MyClass(i)); + + BaseSet baseset; + MemberMultiset membermultiset; + + //Check that size optimization is activated in the base hook + assert(sizeof(set_base_hook<optimize_size<true> >) == 3*sizeof(void*)); + //Check that size optimization is deactivated in the member hook + assert(sizeof(set_member_hook<>) > 3*sizeof(void*)); + + //Now insert them in the reverse order in the base hook set + for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it){ + baseset.insert(*it); + membermultiset.insert(*it); + } + + //Now test sets + { + BaseSet::reverse_iterator rbit(baseset.rbegin()); + MemberMultiset::iterator mit(membermultiset.begin()); + VectIt it(values.begin()), itend(values.end()); + + //Test the objects inserted in the base hook set + for(; it != itend; ++it, ++rbit) + if(&*rbit != &*it) return 1; + + //Test the objects inserted in the member hook set + for(it = values.begin(); it != itend; ++it, ++mit) + if(&*mit != &*it) return 1; + } + return 0; +} +//] diff --git a/src/boost/libs/intrusive/example/doc_sg_set.cpp b/src/boost/libs/intrusive/example/doc_sg_set.cpp new file mode 100644 index 000000000..4920a76f3 --- /dev/null +++ b/src/boost/libs/intrusive/example/doc_sg_set.cpp @@ -0,0 +1,84 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2007-2013 +// +// 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. +// +///////////////////////////////////////////////////////////////////////////// +//[doc_sg_set_code +#include <boost/intrusive/sg_set.hpp> +#include <vector> +#include <functional> +#include <cassert> + +using namespace boost::intrusive; + +class MyClass : public bs_set_base_hook<> +{ + int int_; + + public: + //This is a member hook + bs_set_member_hook<> member_hook_; + + MyClass(int i) + : int_(i) + {} + friend bool operator< (const MyClass &a, const MyClass &b) + { return a.int_ < b.int_; } + friend bool operator> (const MyClass &a, const MyClass &b) + { return a.int_ > b.int_; } + friend bool operator== (const MyClass &a, const MyClass &b) + { return a.int_ == b.int_; } +}; + +//Define an sg_set using the base hook that will store values in reverse order +//and won't execute floating point operations. +typedef sg_set + < MyClass, compare<std::greater<MyClass> >, floating_point<false> > BaseSet; + +//Define an multiset using the member hook +typedef member_hook<MyClass, bs_set_member_hook<>, &MyClass::member_hook_> MemberOption; +typedef sg_multiset< MyClass, MemberOption> MemberMultiset; + +int main() +{ + typedef std::vector<MyClass>::iterator VectIt; + + //Create several MyClass objects, each one with a different value + std::vector<MyClass> values; + for(int i = 0; i < 100; ++i) values.push_back(MyClass(i)); + + BaseSet baseset; + MemberMultiset membermultiset; + + //Now insert them in the reverse order in the base hook sg_set + for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it){ + baseset.insert(*it); + membermultiset.insert(*it); + } + + //Change balance factor + membermultiset.balance_factor(0.9f); + + //Now test sg_sets + { + BaseSet::reverse_iterator rbit(baseset.rbegin()); + MemberMultiset::iterator mit(membermultiset.begin()); + VectIt it(values.begin()), itend(values.end()); + + //Test the objects inserted in the base hook sg_set + for(; it != itend; ++it, ++rbit) + if(&*rbit != &*it) return 1; + + //Test the objects inserted in the member hook sg_set + for(it = values.begin(); it != itend; ++it, ++mit) + if(&*mit != &*it) return 1; + } + return 0; +} +//] diff --git a/src/boost/libs/intrusive/example/doc_slist.cpp b/src/boost/libs/intrusive/example/doc_slist.cpp new file mode 100644 index 000000000..eda8f85fb --- /dev/null +++ b/src/boost/libs/intrusive/example/doc_slist.cpp @@ -0,0 +1,82 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2006-2013 +// +// 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. +// +///////////////////////////////////////////////////////////////////////////// +//[doc_slist_code +#include <boost/intrusive/slist.hpp> +#include <vector> + +using namespace boost::intrusive; + + //This is a base hook +class MyClass : public slist_base_hook<> +{ + int int_; + + public: + //This is a member hook + slist_member_hook<> member_hook_; + + MyClass(int i) + : int_(i) + {} + //<- + int get_int() const { return int_; } + //-> +}; + +//Define an slist that will store MyClass using the public base hook +typedef slist<MyClass> BaseList; + +//Define an slist that will store MyClass using the public member hook +typedef member_hook<MyClass, slist_member_hook<>, &MyClass::member_hook_> MemberOption; +typedef slist<MyClass, MemberOption> MemberList; + +int main() +{ + typedef std::vector<MyClass>::iterator VectIt; + typedef std::vector<MyClass>::reverse_iterator VectRit; + + //Create several MyClass objects, each one with a different value + std::vector<MyClass> values; + for(int i = 0; i < 100; ++i) values.push_back(MyClass(i)); + + BaseList baselist; + MemberList memberlist; + + //Now insert them in the reverse order in the base hook list + for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it) + baselist.push_front(*it); + + //Now insert them in the same order as in vector in the member hook list + for(BaseList::iterator it(baselist.begin()), itend(baselist.end()) + ; it != itend; ++it){ + memberlist.push_front(*it); + } + + //Now test lists + { + BaseList::iterator bit(baselist.begin()); + MemberList::iterator mit(memberlist.begin()); + VectRit rit(values.rbegin()), ritend(values.rend()); + VectIt it(values.begin()), itend(values.end()); + + //Test the objects inserted in the base hook list + for(; rit != ritend; ++rit, ++bit) + if(&*bit != &*rit) return 1; + + //Test the objects inserted in the member hook list + for(; it != itend; ++it, ++mit) + if(&*mit != &*it) return 1; + } + + return 0; +} +//] diff --git a/src/boost/libs/intrusive/example/doc_slist_algorithms.cpp b/src/boost/libs/intrusive/example/doc_slist_algorithms.cpp new file mode 100644 index 000000000..33c5ae302 --- /dev/null +++ b/src/boost/libs/intrusive/example/doc_slist_algorithms.cpp @@ -0,0 +1,60 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2006-2013 +// +// 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. +// +///////////////////////////////////////////////////////////////////////////// +//[doc_slist_algorithms_code +#include <boost/intrusive/circular_slist_algorithms.hpp> +#include <cassert> + +struct my_node +{ + my_node *next_; + //other members... +}; + +//Define our own slist_node_traits +struct my_slist_node_traits +{ + typedef my_node node; + typedef my_node * node_ptr; + typedef const my_node * const_node_ptr; + static node_ptr get_next(const_node_ptr n) { return n->next_; } + static void set_next(node_ptr n, node_ptr next) { n->next_ = next; } +}; + +int main() +{ + typedef boost::intrusive::circular_slist_algorithms<my_slist_node_traits> algo; + my_node one, two, three; + + //Create an empty singly linked list container: + //"one" will be the first node of the container + algo::init_header(&one); + assert(algo::count(&one) == 1); + + //Now add a new node + algo::link_after(&one, &two); + assert(algo::count(&one) == 2); + + //Now add a new node after "one" + algo::link_after(&one, &three); + assert(algo::count(&one) == 3); + + //Now unlink the node after one + algo::unlink_after(&one); + assert(algo::count(&one) == 2); + + //Now unlink two + algo::unlink(&two); + assert(algo::count(&one) == 1); + + return 0; +} +//] diff --git a/src/boost/libs/intrusive/example/doc_splay_algorithms.cpp b/src/boost/libs/intrusive/example/doc_splay_algorithms.cpp new file mode 100644 index 000000000..99d5f0f0b --- /dev/null +++ b/src/boost/libs/intrusive/example/doc_splay_algorithms.cpp @@ -0,0 +1,78 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2006-2013 +// +// 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. +// +///////////////////////////////////////////////////////////////////////////// +//[doc_splaytree_algorithms_code +#include <boost/intrusive/splaytree_algorithms.hpp> +#include <cassert> + +struct my_node +{ + my_node(int i = 0) + : int_(i) + {} + my_node *parent_, *left_, *right_; + int color_; + //other members + int int_; +}; + +//Define our own splaytree_node_traits +struct my_splaytree_node_traits +{ + typedef my_node node; + typedef my_node * node_ptr; + typedef const my_node * const_node_ptr; + + static node_ptr get_parent(const_node_ptr n) { return n->parent_; } + static void set_parent(node_ptr n, node_ptr parent){ n->parent_ = parent; } + static node_ptr get_left(const_node_ptr n) { return n->left_; } + static void set_left(node_ptr n, node_ptr left) { n->left_ = left; } + static node_ptr get_right(const_node_ptr n) { return n->right_; } + static void set_right(node_ptr n, node_ptr right) { n->right_ = right; } +}; + +struct node_ptr_compare +{ + bool operator()(const my_node *a, const my_node *b) + { return a->int_ < b->int_; } +}; + +int main() +{ + typedef boost::intrusive::splaytree_algorithms<my_splaytree_node_traits> algo; + my_node header, two(2), three(3); + + //Create an empty splaytree container: + //"header" will be the header node of the tree + algo::init_header(&header); + + //Now insert node "two" in the tree using the sorting functor + algo::insert_equal_upper_bound(&header, &two, node_ptr_compare()); + + //Now insert node "three" in the tree using the sorting functor + algo::insert_equal_lower_bound(&header, &three, node_ptr_compare()); + + //Now take the first node (the left node of the header) + my_node *n = header.left_; + assert(n == &two); + + //Now go to the next node + n = algo::next_node(n); + assert(n == &three); + + //Erase a node just using a pointer to it + algo::unlink(&two); + + //Erase a node using also the header (faster) + algo::erase(&header, &three); + return 0; +} +//] diff --git a/src/boost/libs/intrusive/example/doc_splay_set.cpp b/src/boost/libs/intrusive/example/doc_splay_set.cpp new file mode 100644 index 000000000..831fa03be --- /dev/null +++ b/src/boost/libs/intrusive/example/doc_splay_set.cpp @@ -0,0 +1,84 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2006-2013 +// +// 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. +// +///////////////////////////////////////////////////////////////////////////// +//[doc_splay_set_code +#include <boost/intrusive/splay_set.hpp> +#include <vector> +#include <functional> + +using namespace boost::intrusive; + +class mytag; + +class MyClass + : public bs_set_base_hook<> +{ + int int_; + + public: + //This is a member hook + bs_set_member_hook<> member_hook_; + + MyClass(int i) + : int_(i) + {} + friend bool operator< (const MyClass &a, const MyClass &b) + { return a.int_ < b.int_; } + friend bool operator> (const MyClass &a, const MyClass &b) + { return a.int_ > b.int_; } + friend bool operator== (const MyClass &a, const MyClass &b) + { return a.int_ == b.int_; } +}; + +//Define a set using the base hook that will store values in reverse order +typedef splay_set< MyClass, compare<std::greater<MyClass> > > BaseSplaySet; + +//Define an multiset using the member hook +typedef member_hook<MyClass, bs_set_member_hook<>, &MyClass::member_hook_> MemberOption; +typedef splay_multiset< MyClass, MemberOption> MemberSplayMultiset; + +int main() +{ + typedef std::vector<MyClass>::iterator VectIt; + + //Create several MyClass objects, each one with a different value + std::vector<MyClass> values; + for(int i = 0; i < 100; ++i) values.push_back(MyClass(i)); + + BaseSplaySet baseset; + MemberSplayMultiset membermultiset; + + + //Insert values in the container + for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it){ + baseset.insert(*it); + membermultiset.insert(*it); + } + + //Now test sets + { + BaseSplaySet::reverse_iterator rbit(baseset.rbegin()); + MemberSplayMultiset::iterator mit(membermultiset.begin()); + VectIt it(values.begin()), itend(values.end()); + + //Test the objects inserted in the base hook set + for(; it != itend; ++it, ++rbit){ + if(&*rbit != &*it) return 1; + } + + //Test the objects inserted in member and binary search hook sets + for(it = values.begin(); it != itend; ++it, ++mit){ + if(&*mit != &*it) return 1; + } + } + return 0; +} +//] diff --git a/src/boost/libs/intrusive/example/doc_splaytree_algorithms.cpp b/src/boost/libs/intrusive/example/doc_splaytree_algorithms.cpp new file mode 100644 index 000000000..8268fa735 --- /dev/null +++ b/src/boost/libs/intrusive/example/doc_splaytree_algorithms.cpp @@ -0,0 +1,78 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2007-2013 +// +// 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. +// +///////////////////////////////////////////////////////////////////////////// +//[doc_splaytree_algorithms_code +#include <boost/intrusive/splaytree_algorithms.hpp> +#include <cassert> + +struct my_node +{ + my_node(int i = 0) + : int_(i) + {} + my_node *parent_, *left_, *right_; + //other members + int int_; +}; + +//Define our own splaytree_node_traits +struct my_splaytree_node_traits +{ + typedef my_node node; + typedef my_node * node_ptr; + typedef const my_node * const_node_ptr; + + static node_ptr get_parent(const_node_ptr n) { return n->parent_; } + static void set_parent(node_ptr n, node_ptr parent){ n->parent_ = parent; } + static node_ptr get_left(const_node_ptr n) { return n->left_; } + static void set_left(node_ptr n, node_ptr left) { n->left_ = left; } + static node_ptr get_right(const_node_ptr n) { return n->right_; } + static void set_right(node_ptr n, node_ptr right) { n->right_ = right; } +}; + +struct node_ptr_compare +{ + bool operator()(const my_node *a, const my_node *b) + { return a->int_ < b->int_; } +}; + +int main() +{ + typedef boost::intrusive::splaytree_algorithms<my_splaytree_node_traits> algo; + my_node header, two(2), three(3); + + //Create an empty splaytree container: + //"header" will be the header node of the tree + algo::init_header(&header); + + //Now insert node "two" in the tree using the sorting functor + algo::insert_equal_upper_bound(&header, &two, node_ptr_compare()); + + //Now insert node "three" in the tree using the sorting functor + algo::insert_equal_lower_bound(&header, &three, node_ptr_compare()); + + //Now take the first node (the left node of the header) + my_node *n = header.left_; + assert(n == &two); + + //Now go to the next node + n = algo::next_node(n); + assert(n == &three); + + //Erase a node just using a pointer to it + algo::unlink(&two); + + //Erase a node using also the header (faster) + algo::erase(&header, &three); + return 0; +} + +//] diff --git a/src/boost/libs/intrusive/example/doc_stateful_value_traits.cpp b/src/boost/libs/intrusive/example/doc_stateful_value_traits.cpp new file mode 100644 index 000000000..fac0abade --- /dev/null +++ b/src/boost/libs/intrusive/example/doc_stateful_value_traits.cpp @@ -0,0 +1,87 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2007-2013 +// +// 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. +// +///////////////////////////////////////////////////////////////////////////// +//[doc_stateful_value_traits +#include <boost/intrusive/list.hpp> + +using namespace boost::intrusive; + +//This type is not modifiable so we can't store hooks or custom nodes +typedef int identifier_t; + +//This value traits will associate elements from an array of identifiers with +//elements of an array of nodes. The element i of the value array will use the +//node i of the node array: +struct stateful_value_traits +{ + typedef list_node_traits<void*> node_traits; + typedef node_traits::node node; + typedef node * node_ptr; + typedef const node * const_node_ptr; + typedef identifier_t value_type; + typedef identifier_t * pointer; + typedef const identifier_t * const_pointer; + static const link_mode_type link_mode = normal_link; + + stateful_value_traits(pointer ids, node_ptr node_array) + : ids_(ids), nodes_(node_array) + {} + + ///Note: non static functions! + node_ptr to_node_ptr (value_type &value) const + { return this->nodes_ + (&value - this->ids_); } + const_node_ptr to_node_ptr (const value_type &value) const + { return this->nodes_ + (&value - this->ids_); } + pointer to_value_ptr(node_ptr n) const + { return this->ids_ + (n - this->nodes_); } + const_pointer to_value_ptr(const_node_ptr n) const + { return this->ids_ + (n - this->nodes_); } + + private: + pointer ids_; + node_ptr nodes_; +}; + +int main() +{ + const int NumElements = 100; + + //This is an array of ids that we want to "store" + identifier_t ids [NumElements]; + + //This is an array of nodes that is necessary to form the linked list + list_node_traits<void*>::node nodes [NumElements]; + + //Initialize id objects, each one with a different number + for(int i = 0; i != NumElements; ++i) ids[i] = i; + + //Define a list that will "link" identifiers using external nodes + typedef list<identifier_t, value_traits<stateful_value_traits> > List; + + //This list will store ids without modifying identifier_t instances + //Stateful value traits must be explicitly passed in the constructor. + List my_list (stateful_value_traits (ids, nodes)); + + //Insert ids in reverse order in the list + for(identifier_t * it(&ids[0]), *itend(&ids[NumElements]); it != itend; ++it) + my_list.push_front(*it); + + //Now test lists + List::const_iterator list_it (my_list.cbegin()); + identifier_t *it_val(&ids[NumElements]), *it_rbeg_val(&ids[0]); + + //Test the objects inserted in the base hook list + for(; it_val != it_rbeg_val; --it_val, ++list_it) + if(&*list_it != &it_val[-1]) return 1; + + return 0; +} +//] diff --git a/src/boost/libs/intrusive/example/doc_treap_algorithms.cpp b/src/boost/libs/intrusive/example/doc_treap_algorithms.cpp new file mode 100644 index 000000000..96ce48a19 --- /dev/null +++ b/src/boost/libs/intrusive/example/doc_treap_algorithms.cpp @@ -0,0 +1,79 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2007-2013 +// +// 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. +// +///////////////////////////////////////////////////////////////////////////// +//[doc_treap_algorithms_code +#include <boost/intrusive/treap_algorithms.hpp> +#include <cassert> + +struct my_node +{ + my_node(int i = 0, unsigned int priority = 0) + : prio_(priority), int_(i) + {} + my_node *parent_, *left_, *right_; + int prio_; + //other members + int int_; +}; + +//Define our own treap_node_traits +struct my_treap_node_traits +{ + typedef my_node node; + typedef my_node * node_ptr; + typedef const my_node * const_node_ptr; + + static node_ptr get_parent(const_node_ptr n) { return n->parent_; } + static void set_parent(node_ptr n, node_ptr parent){ n->parent_ = parent; } + static node_ptr get_left(const_node_ptr n) { return n->left_; } + static void set_left(node_ptr n, node_ptr left) { n->left_ = left; } + static node_ptr get_right(const_node_ptr n) { return n->right_; } + static void set_right(node_ptr n, node_ptr right) { n->right_ = right; } +}; + +struct node_ptr_compare +{ bool operator()(const my_node *a, const my_node *b) { return a->int_ < b->int_; } }; + +struct node_ptr_priority +{ bool operator()(const my_node *a, const my_node *b) { return a->prio_ < b->prio_;} }; + +int main() +{ + typedef boost::intrusive::treap_algorithms<my_treap_node_traits> algo; + my_node header, two(2, 5), three(3, 1); + + //Create an empty treap container: + //"header" will be the header node of the tree + algo::init_header(&header); + + //Now insert node "two" in the tree using the sorting functor + algo::insert_equal_upper_bound(&header, &two, node_ptr_compare(), node_ptr_priority()); + + //Now insert node "three" in the tree using the sorting functor + algo::insert_equal_lower_bound(&header, &three, node_ptr_compare(), node_ptr_priority()); + + //Now take the first node (the left node of the header) + my_node *n = header.left_; + assert(n == &two); + + //Now go to the next node + n = algo::next_node(n); + assert(n == &three); + + //Erase a node just using a pointer to it + algo::unlink(&two, node_ptr_priority()); + + //Erase a node using also the header (faster) + algo::erase(&header, &three, node_ptr_priority()); + return 0; +} + +//] diff --git a/src/boost/libs/intrusive/example/doc_treap_set.cpp b/src/boost/libs/intrusive/example/doc_treap_set.cpp new file mode 100644 index 000000000..f8abbe585 --- /dev/null +++ b/src/boost/libs/intrusive/example/doc_treap_set.cpp @@ -0,0 +1,106 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2006-2013 +// +// 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. +// +///////////////////////////////////////////////////////////////////////////// +//[doc_treap_set_code +#include <boost/intrusive/treap_set.hpp> +#include <vector> +#include <functional> +#include <cassert> + +using namespace boost::intrusive; + +class MyClass : public bs_set_base_hook<> //This is a base hook +{ + int int_; + unsigned int prio_; + + public: + //This is a member hook + bs_set_member_hook<> member_hook_; + + MyClass(int i, unsigned int prio) : int_(i), prio_(prio) + {} + + unsigned int get_priority() const + { return this->prio_; } + + //Less and greater operators + friend bool operator< (const MyClass &a, const MyClass &b) + { return a.int_ < b.int_; } + friend bool operator> (const MyClass &a, const MyClass &b) + { return a.int_ > b.int_; } + //Default priority compare + friend bool priority_order (const MyClass &a, const MyClass &b) + { return a.prio_ < b.prio_; } //Lower value means higher priority + //Inverse priority compare + friend bool priority_inverse_order (const MyClass &a, const MyClass &b) + { return a.prio_ > b.prio_; } //Higher value means higher priority +}; + +struct inverse_priority +{ + bool operator()(const MyClass &a, const MyClass &b) const + { return priority_inverse_order(a, b); } +}; + + +//Define an treap_set using the base hook that will store values in reverse order +typedef treap_set< MyClass, compare<std::greater<MyClass> > > BaseSet; + +//Define an multiset using the member hook that will store +typedef member_hook<MyClass, bs_set_member_hook<>, &MyClass::member_hook_> MemberOption; +typedef treap_multiset + < MyClass, MemberOption, priority<inverse_priority> > MemberMultiset; + +int main() +{ + typedef std::vector<MyClass>::iterator VectIt; + + //Create several MyClass objects, each one with a different value + std::vector<MyClass> values; + for(int i = 0; i < 100; ++i) values.push_back(MyClass(i, (i % 10))); + + BaseSet baseset; + MemberMultiset membermultiset; + + //Now insert them in the sets + for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it){ + baseset.insert(*it); + membermultiset.insert(*it); + } + + //Now test treap_sets + { + BaseSet::reverse_iterator rbit(baseset.rbegin()); + MemberMultiset::iterator mit(membermultiset.begin()); + VectIt it(values.begin()), itend(values.end()); + + //Test the objects inserted in the base hook treap_set + for(; it != itend; ++it, ++rbit) + if(&*rbit != &*it) return 1; + + //Test the objects inserted in the member hook treap_set + for(it = values.begin(); it != itend; ++it, ++mit) + if(&*mit != &*it) return 1; + + //Test priority order + for(int i = 0; i < 100; ++i){ + if(baseset.top()->get_priority() != static_cast<unsigned int>(i/10)) + return 1; + if(membermultiset.top()->get_priority() != 9u - static_cast<unsigned int>(i/10)) + return 1; + baseset.erase(baseset.top()); + membermultiset.erase(membermultiset.top()); + } + } + return 0; +} +//] diff --git a/src/boost/libs/intrusive/example/doc_unordered_set.cpp b/src/boost/libs/intrusive/example/doc_unordered_set.cpp new file mode 100644 index 000000000..ca0b5be31 --- /dev/null +++ b/src/boost/libs/intrusive/example/doc_unordered_set.cpp @@ -0,0 +1,92 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2006-2013 +// +// 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. +// +///////////////////////////////////////////////////////////////////////////// +//[doc_unordered_set_code +#include <boost/intrusive/unordered_set.hpp> +#include <vector> +#include <functional> +#include <boost/functional/hash.hpp> + +using namespace boost::intrusive; + +class MyClass : public unordered_set_base_hook<> +{ //This is a derivation hook + int int_; + + public: + unordered_set_member_hook<> member_hook_; //This is a member hook + + MyClass(int i) + : int_(i) + {} + + friend bool operator== (const MyClass &a, const MyClass &b) + { return a.int_ == b.int_; } + + friend std::size_t hash_value(const MyClass &value) + { return std::size_t(value.int_); } +}; + +//Define an unordered_set that will store MyClass objects using the base hook +typedef unordered_set<MyClass> BaseSet; + +//Define an unordered_multiset that will store MyClass using the member hook +typedef member_hook<MyClass, unordered_set_member_hook<>, &MyClass::member_hook_> + MemberOption; +typedef unordered_multiset< MyClass, MemberOption> MemberMultiSet; + +int main() +{ + typedef std::vector<MyClass>::iterator VectIt; + + //Create a vector with 100 different MyClass objects + std::vector<MyClass> values; + for(int i = 0; i < 100; ++i) values.push_back(MyClass(i)); + + //Create a copy of the vector + std::vector<MyClass> values2(values); + + //Create a bucket array for base_set + BaseSet::bucket_type base_buckets[100]; + + //Create a bucket array for member_multi_set + MemberMultiSet::bucket_type member_buckets[200]; + + //Create unordered containers taking buckets as arguments + BaseSet base_set(BaseSet::bucket_traits(base_buckets, 100)); + MemberMultiSet member_multi_set + (MemberMultiSet::bucket_traits(member_buckets, 200)); + + //Now insert values's elements in the unordered_set + for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it) + base_set.insert(*it); + + //Now insert values's and values2's elements in the unordered_multiset + for(VectIt it(values.begin()), itend(values.end()), it2(values2.begin()) + ; it != itend; ++it, ++it2){ + member_multi_set.insert(*it); + member_multi_set.insert(*it2); + } + + //Now find every element + { + VectIt it(values.begin()), itend(values.end()); + + for(; it != itend; ++it){ + //base_set should contain one element for each key + if(base_set.count(*it) != 1) return 1; + //member_multi_set should contain two elements for each key + if(member_multi_set.count(*it) != 2) return 1; + } + } + return 0; +} +//] diff --git a/src/boost/libs/intrusive/example/doc_value_traits.cpp b/src/boost/libs/intrusive/example/doc_value_traits.cpp new file mode 100644 index 000000000..52b9f81e1 --- /dev/null +++ b/src/boost/libs/intrusive/example/doc_value_traits.cpp @@ -0,0 +1,118 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2006-2013 +// +// 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. +// +///////////////////////////////////////////////////////////////////////////// +//[doc_value_traits_code_legacy +#include <boost/intrusive/link_mode.hpp> +#include <boost/intrusive/list.hpp> +#include <boost/intrusive/slist.hpp> +//<- +#include <boost/intrusive/trivial_value_traits.hpp> +//-> +#include <vector> + +//This node is the legacy type we can't modify and we want to insert in +//intrusive list and slist containers using only two pointers, since +//we know the object will never be at the same time in both lists. +struct legacy_value +{ + legacy_value *prev_; + legacy_value *next_; + int id_; +}; +//] + +//[doc_value_traits_value_traits +//Define our own NodeTraits that will configure singly and doubly linked +//list algorithms. Note that this node traits is compatible with +//circular_slist_algorithms and circular_list_algorithms. + +namespace bi = boost::intrusive; + +struct legacy_node_traits +{ + typedef legacy_value node; + typedef legacy_value * node_ptr; + typedef const legacy_value * const_node_ptr; + + static node *get_next(const node *n) { return n->next_; } + static void set_next(node *n, node *next) { n->next_ = next; } + static node *get_previous(const node *n) { return n->prev_; } + static void set_previous(node *n, node *prev) { n->prev_ = prev; } +}; + +//This ValueTraits will configure list and slist. In this case, +//legacy_node_traits::node is the same as the +//legacy_value_traits::value_type so to_node_ptr/to_value_ptr +//functions are trivial. +struct legacy_value_traits +{ + typedef legacy_node_traits node_traits; + typedef node_traits::node_ptr node_ptr; + typedef node_traits::const_node_ptr const_node_ptr; + typedef legacy_value value_type; + typedef legacy_value * pointer; + typedef const legacy_value * const_pointer; + static const bi::link_mode_type link_mode = bi::normal_link; + static node_ptr to_node_ptr (value_type &value) { return node_ptr(&value); } + static const_node_ptr to_node_ptr (const value_type &value) { return const_node_ptr(&value); } + static pointer to_value_ptr(node_ptr n) { return pointer(n); } + static const_pointer to_value_ptr(const_node_ptr n) { return const_pointer(n); } +}; + +//] + +//[doc_value_traits_trivial + +typedef bi::trivial_value_traits<legacy_node_traits, bi::normal_link> trivial_legacy_value_traits; + +//] + +//[doc_value_traits_test +//Now define an intrusive list and slist that will store legacy_value objects +typedef bi::value_traits<legacy_value_traits> ValueTraitsOption; +typedef bi::value_traits<trivial_legacy_value_traits> TrivialValueTraitsOption; + +typedef bi::list<legacy_value, ValueTraitsOption> LegacyAbiList; +typedef bi::slist<legacy_value, ValueTraitsOption> LegacyAbiSlist; +typedef bi::list<legacy_value, TrivialValueTraitsOption> TrivialLegacyAbiList; +typedef bi::slist<legacy_value, TrivialValueTraitsOption> TrivialLegacyAbiSlist; + +template<class List> +bool test_list() +{ + typedef std::vector<legacy_value> Vect; + + //Create legacy_value objects, with a different internal number + Vect legacy_vector; + for(int i = 0; i < 100; ++i){ + legacy_value value; value.id_ = i; legacy_vector.push_back(value); + } + + //Create the list with the objects + List mylist(legacy_vector.begin(), legacy_vector.end()); + + //Now test both lists + typename List::const_iterator bit(mylist.begin()), bitend(mylist.end()); + typename Vect::const_iterator it(legacy_vector.begin()), itend(legacy_vector.end()); + + //Test the objects inserted in our list + for(; it != itend; ++it, ++bit) + if(&*bit != &*it) return false; + return true; +} + +int main() +{ + return test_list<LegacyAbiList>() && test_list<LegacyAbiSlist>() && + test_list<TrivialLegacyAbiList>() && test_list<TrivialLegacyAbiSlist>() + ? 0 : 1; +} +//] diff --git a/src/boost/libs/intrusive/example/doc_window.cpp b/src/boost/libs/intrusive/example/doc_window.cpp new file mode 100644 index 000000000..c03387642 --- /dev/null +++ b/src/boost/libs/intrusive/example/doc_window.cpp @@ -0,0 +1,83 @@ +///////////////////////////////////////////////////////////////////////////// +// +// (C) Copyright Ion Gaztanaga 2006-2013 +// +// 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. +// +///////////////////////////////////////////////////////////////////////////// +//[doc_window_code +#include <boost/intrusive/list.hpp> + +using namespace boost::intrusive; + +//An abstract class that can be inserted in an intrusive list +class Window : public list_base_hook<> +{ + public: + //This is a container those value is an abstract class: you can't do this with std::list. + typedef list<Window> win_list; + + //A static intrusive list declaration + static win_list all_windows; + + //Constructor. Includes this window in the list + Window() { all_windows.push_back(*this); } + //Destructor. Removes this node from the list + virtual ~Window() { all_windows.erase(win_list::s_iterator_to(*this)); } + //Pure virtual function to be implemented by derived classes + virtual void Paint() = 0; +}; + +//The static intrusive list declaration +Window::win_list Window::all_windows; + +//Some Window derived classes +class FrameWindow : public Window +{ void Paint(){/**/} }; + +class EditWindow : public Window +{ void Paint(){/**/} }; + +class CanvasWindow : public Window +{ void Paint(){/**/} }; + +//A function that prints all windows stored in the intrusive list +void paint_all_windows() +{ + for(Window::win_list::iterator i(Window::all_windows.begin()) + , e(Window::all_windows.end()) + ; i != e; ++i) + i->Paint(); +} + +//... + +//A class derived from Window +class MainWindow : public Window +{ + FrameWindow frame_; //these are derived from Window too + EditWindow edit_; + CanvasWindow canvas_; + + public: + void Paint(){/**/} + //... +}; + +//Main function +int main() +{ + //When a Window class is created, is automatically registered in the global list + MainWindow window; + + //Paint all the windows, sub-windows and so on + paint_all_windows(); + + //All the windows are automatically unregistered in their destructors. + return 0; +} +//] |