Subject: [Boost-commit] svn:boost r50259 - in trunk/libs/intrusive: doc example perf proj/vc7ide proj/vc7ide/_intrusivelib proj/vc7ide/treap_multiset proj/vc7ide/treap_set test
From: igaztanaga_at_[hidden]
Date: 2008-12-13 08:49:36
Author: igaztanaga
Date: 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
New Revision: 50259
URL: http://svn.boost.org/trac/boost/changeset/50259
Log:
* New treap-based containers: treap, treap_set, treap_multiset.
* Corrected compilation bug for Windows-based 64 bit compilers.
* Corrected exception-safety bugs in container constructors.
* Updated documentation to show rvalue-references funcions instead of emulation functions.
Added:
trunk/libs/intrusive/example/doc_treap_algorithms.cpp (contents, props changed)
trunk/libs/intrusive/example/doc_treap_set.cpp (contents, props changed)
trunk/libs/intrusive/proj/vc7ide/treap_multiset/
trunk/libs/intrusive/proj/vc7ide/treap_multiset/treap_multiset.vcproj (contents, props changed)
trunk/libs/intrusive/proj/vc7ide/treap_set/
trunk/libs/intrusive/proj/vc7ide/treap_set/treap_set.vcproj (contents, props changed)
trunk/libs/intrusive/test/treap_multiset_test.cpp (contents, props changed)
trunk/libs/intrusive/test/treap_set_test.cpp (contents, props changed)
Text files modified:
trunk/libs/intrusive/doc/Jamfile.v2 | 5
trunk/libs/intrusive/doc/intrusive.qbk | 232 ++++++++++++++++++++++++
trunk/libs/intrusive/example/doc_advanced_value_traits.cpp | 2
trunk/libs/intrusive/example/doc_advanced_value_traits2.cpp | 2
trunk/libs/intrusive/example/doc_assoc_optimized_code.cpp | 2
trunk/libs/intrusive/example/doc_auto_unlink.cpp | 2
trunk/libs/intrusive/example/doc_avl_set.cpp | 2
trunk/libs/intrusive/example/doc_avltree_algorithms.cpp | 4
trunk/libs/intrusive/example/doc_bucket_traits.cpp | 2
trunk/libs/intrusive/example/doc_clone_from.cpp | 2
trunk/libs/intrusive/example/doc_entity.cpp | 2
trunk/libs/intrusive/example/doc_erasing_and_disposing.cpp | 2
trunk/libs/intrusive/example/doc_external_value_traits.cpp | 2
trunk/libs/intrusive/example/doc_how_to_use.cpp | 2
trunk/libs/intrusive/example/doc_iterator_from_value.cpp | 2
trunk/libs/intrusive/example/doc_list.cpp | 2
trunk/libs/intrusive/example/doc_list_algorithms.cpp | 2
trunk/libs/intrusive/example/doc_offset_ptr.cpp | 2
trunk/libs/intrusive/example/doc_rbtree_algorithms.cpp | 4
trunk/libs/intrusive/example/doc_set.cpp | 2
trunk/libs/intrusive/example/doc_sg_set.cpp | 2
trunk/libs/intrusive/example/doc_slist.cpp | 2
trunk/libs/intrusive/example/doc_slist_algorithms.cpp | 2
trunk/libs/intrusive/example/doc_splay_algorithms.cpp | 4
trunk/libs/intrusive/example/doc_splay_set.cpp | 2
trunk/libs/intrusive/example/doc_splaytree_algorithms.cpp | 4
trunk/libs/intrusive/example/doc_stateful_value_traits.cpp | 2
trunk/libs/intrusive/example/doc_unordered_set.cpp | 2
trunk/libs/intrusive/example/doc_value_traits.cpp | 2
trunk/libs/intrusive/example/doc_window.cpp | 2
trunk/libs/intrusive/perf/perf_list.cpp | 5
trunk/libs/intrusive/proj/vc7ide/Intrusive.sln | 16 +
trunk/libs/intrusive/proj/vc7ide/_intrusivelib/_intrusivelib.vcproj | 18 +
trunk/libs/intrusive/proj/vc7ide/to-do.txt | 23 ++
trunk/libs/intrusive/test/any_test.cpp | 15 +
trunk/libs/intrusive/test/avl_multiset_test.cpp | 44 +++-
trunk/libs/intrusive/test/avl_set_test.cpp | 44 +++-
trunk/libs/intrusive/test/common_functors.hpp | 2
trunk/libs/intrusive/test/custom_bucket_traits_test.cpp | 2
trunk/libs/intrusive/test/default_hook_test.cpp | 2
trunk/libs/intrusive/test/external_value_traits_test.cpp | 2
trunk/libs/intrusive/test/generic_assoc_test.hpp | 27 ++
trunk/libs/intrusive/test/generic_multiset_test.hpp | 2
trunk/libs/intrusive/test/generic_set_test.hpp | 2
trunk/libs/intrusive/test/itestvalue.hpp | 367 ++++-----------------------------------
trunk/libs/intrusive/test/list_test.cpp | 319 ++--------------------------------
trunk/libs/intrusive/test/make_functions_test.cpp | 88 +++++++++
trunk/libs/intrusive/test/multiset_test.cpp | 44 +++-
trunk/libs/intrusive/test/set_test.cpp | 44 +++-
trunk/libs/intrusive/test/sg_multiset_test.cpp | 32 ++
trunk/libs/intrusive/test/sg_set_test.cpp | 30 ++
trunk/libs/intrusive/test/slist_test.cpp | 73 ++++---
trunk/libs/intrusive/test/splay_multiset_test.cpp | 42 +++-
trunk/libs/intrusive/test/splay_set_test.cpp | 40 +++-
trunk/libs/intrusive/test/stateful_value_traits_test.cpp | 2
trunk/libs/intrusive/test/test_container.hpp | 2
trunk/libs/intrusive/test/test_macros.hpp | 2
trunk/libs/intrusive/test/unordered_multiset_test.cpp | 52 ++++-
trunk/libs/intrusive/test/unordered_set_test.cpp | 52 ++++-
trunk/libs/intrusive/test/virtual_base_test.cpp | 2
60 files changed, 872 insertions(+), 824 deletions(-)
Modified: trunk/libs/intrusive/doc/Jamfile.v2
==============================================================================
--- trunk/libs/intrusive/doc/Jamfile.v2 (original)
+++ trunk/libs/intrusive/doc/Jamfile.v2 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -38,7 +38,10 @@
"sgtree_impl=sgtree" \\
"avl_set_impl=avl_set" \\
"avl_multiset_impl=avl_multiset" \\
- "avltree_impl=avltree""
+ "avltree_impl=avltree" \\
+ "treap_set_impl=treap_set" \\
+ "treap_multiset_impl=treap_multiset" \\
+ "treap_impl=treap""
;
xml intrusive : intrusive.qbk ;
Modified: trunk/libs/intrusive/doc/intrusive.qbk
==============================================================================
--- trunk/libs/intrusive/doc/intrusive.qbk (original)
+++ trunk/libs/intrusive/doc/intrusive.qbk 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -8,7 +8,7 @@
[library Boost.Intrusive
[quickbook 1.3]
[authors [Krzikalla, Olaf], [Gaztañaga, Ion]]
- [copyright 2005 Olaf Krzikalla, 2006-2007 Ion Gaztañaga]
+ [copyright 2005 Olaf Krzikalla, 2006-2008 Ion Gaztañaga]
[id intrusive]
[dirname intrusive]
[purpose Intrusive containers]
@@ -1693,7 +1693,7 @@
[classref boost::intrusive::sgtree sgtree] don't use their
own hooks but plain binary search tree hooks. This has many advantages
since binary search tree hooks can also be used to insert values in
-splay containers.
+splay and treap containers.
[c++]
@@ -1716,8 +1716,7 @@
[classref boost::intrusive::bs_set_base_hook bs_set_base_hook] and
[classref boost::intrusive::bs_set_member_hook bs_set_member_hook] receive
the same options explained in the section
-[link intrusive.usage How to use Boost.Intrusive] plus an option to optimize
-the size of the node:
+[link intrusive.usage How to use Boost.Intrusive]:
* [*`tag<class Tag>`] (for base hooks only): This argument serves as a tag,
so you can derive from more than one base hook.
@@ -1786,22 +1785,180 @@
[endsect]
+[section:treap_set_multiset Intrusive treap based associative containers: treap_set, treap_multiset and treap]
+
+The name ['treap] is a mixture of ['tree] and ['heap] indicating that Treaps exhibit the properties of both
+binary search trees and heaps. A treap is a binary search tree that orders the nodes
+by a key but also by a priority attribute. The nodes are ordered so that the keys form a binary search tree and
+the priorities obey the max heap order property.
+
+* If v is a left descendant of u, then key[v] < key[u];
+* If v is a right descendant of u, then key[v] > key[u];
+* If v is a child of u, then priority[v] <= priority[u];
+
+If priorities are non-random, the tree will usually be unbalanced; this worse theoretical average-case
+behavior may be outweighed by better expected-case behavior, as the most important items will be near the root.
+This means most important objects will be retrieved faster than less important items and for items keys with equal keys
+most important objects will be found first. These properties are important for some applications.
+
+The priority comparison will be provided just like the key comparison, via a funcion object that will be
+stored in the intrusive container. This means that the priority can be stored in the value to be introduced
+in the treap or computed on flight (via hashing or similar).
+
+[*Boost.Intrusive] offers 3 containers based on treaps:
+[classref boost::intrusive::treap_set treap_set],
+[classref boost::intrusive::treap_multiset treap_multiset] and
+[classref boost::intrusive::treap treap]. The first two are similar to
+[classref boost::intrusive::set set] or
+[classref boost::intrusive::multiset multiset] and the latter is a generalization
+that offers functions both to insert unique and multiple keys.
+
+The memory overhead of these containers with Boost.Intrusive hooks is 3
+pointers.
+
+An empty, [classref boost::intrusive::treap_set treap_set],
+[classref boost::intrusive::treap_multiset treap_multiset] or
+[classref boost::intrusive::treap treap]
+has also the size of 3 pointers and an integer (supposing empty function objects for key and priority
+comparison and constant-time size).
+
+[section:treap_set_multiset_hooks Using binary search tree hooks: bs_set_base_hook and bs_set_member_hook]
+
+[classref boost::intrusive::treap_set treap_set],
+[classref boost::intrusive::treap_multiset treap_multiset] and
+[classref boost::intrusive::treap treap] don't use their
+own hooks but plain binary search tree hooks. This has many advantages
+since binary search tree hooks can also be used to insert values in
+splay containers and scapegoat trees.
+
+[c++]
+
+ template <class ...Options>
+ class bs_set_base_hook;
+
+* [classref boost::intrusive::bs_set_base_hook bs_set_base_hook]:
+ the user class derives publicly from this class to make
+ it compatible with scapegoat tree based containers.
+
+[c++]
+
+ template <class ...Options>
+ class bs_set_member_hook;
+
+* [classref boost::intrusive::set_member_hook set_member_hook]:
+ the user class contains a public member of this class to make
+ it compatible with scapegoat tree based containers.
+
+[classref boost::intrusive::bs_set_base_hook bs_set_base_hook] and
+[classref boost::intrusive::bs_set_member_hook bs_set_member_hook] receive
+the same options explained in the section
+[link intrusive.usage How to use Boost.Intrusive]:
+
+* [*`tag<class Tag>`] (for base hooks only): This argument serves as a tag,
+ so you can derive from more than one base hook.
+ Default: `tag<default_tag>`.
+
+* [*`link_mode<link_mode_type LinkMode>`]: The linking policy.
+ Default: `link_mode<safe_link>`.
+
+* [*`void_pointer<class VoidPointer>`]: The pointer type to be used
+ internally in the hook and propagated to the container.
+ Default: `void_pointer<void*>`.
+
+[endsect]
+
+[section:treap_set_multiset_containers treap_set, treap_multiset and treap containers]
+
+[c++]
+
+ template <class T, class ...Options>
+ class treap_set;
+
+ template <class T, class ...Options>
+ class treap_multiset;
+
+ template <class T, class ...Options>
+ class treap;
+
+These containers receive the same options explained in the section
+[link intrusive.usage How to use Boost.Intrusive]:
+
+* [*`base_hook<class Hook>`] / [*`member_hook<class T, class Hook, Hook T::* PtrToMember>`] /
+ [*`value_traits<class ValueTraits>`]: To specify the hook type or value traits used
+ to configure the container. (To learn about value traits go to the section
+ [link intrusive.value_traits Containers with custom ValueTraits].)
+
+* [*`constant_time_size<bool Enabled>`]: To activate the constant-time `size()` operation.
+ Default: `constant_time_size<true>`
+
+* [*`size_type<bool Enabled>`]: To specify the type that will be used to store the size
+ of the container. Default: `size_type<std::size_t>`
+
+And they also can receive additional options:
+
+* [*`compare<class Compare>`]: Comparison function for the objects to be inserted
+ in containers. The comparison functor must induce a strict weak ordering.
+ Default: `compare< std::less<T> >`
+
+* [*`priority<class PriorityCompare>`]: Priority Comparison function for the objects to be inserted
+ in containers. The comparison functor must induce a strict weak ordering.
+ Default: `priority< priority_compare<T> >`
+
+The default `priority_compare<T>` object function will call an unqualified function `priority_order`
+passing two constant `T` references as arguments and should return true if the first argument has
+higher priority (it will be searched faster), inducing strict weak ordering.
+The function will be found using ADL lookup so that
+the user just needs to define a `priority_order` function in the same namespace as his class:
+
+[c++]
+ struct MyType
+ {
+ friend bool priority_order(const MyType &a, const MyType &b)
+ {...}
+ };
+or
+ namespace mytype {
+ struct MyType{ ... };
+ bool priority_order(const MyType &a, const MyType &b)
+ {...}
+ } //namespace mytype {
+[endsect]
+[section:treap_set_exceptions Exception safety of treap-based intrusive containers]
+In general, intrusive containers offer strong safety guarantees, but treap containers must deal
+with two possibly throwing functors (one for value ordering, another for priority ordering).
+Moreover, treap erasure operations require rotations based on the priority order function and
+this issue degrades usual `erase(const_iterator)` no-throw guarantee. However, intrusive offers
+the strongest possible behaviour in these situations. In summary:
+* If the priority order functor does not throw, treap-based containers, offer exactly the same
+ guarantees as other tree-based containers.
+* If the priority order functor throws, treap-based containers offer strong guarantee.
+[endsect]
+
+[section:treap_set_multiset_example Example]
+Now let's see a small example using both hooks and
+[classref boost::intrusive::treap_set treap_set]/
+[classref boost::intrusive::treap_multiset treap_multiset]
+containers:
+[import ../example/doc_treap_set.cpp]
+[doc_treap_set_code]
+[endsect]
+[endsect]
[section:advanced_lookups_insertions Advanced lookup and insertion functions for associative containers]
@@ -2643,6 +2800,62 @@
[endsect]
+
+[section:treap_algorithms Intrusive treap algorithms]
+
+[classref boost::intrusive::treap_algorithms treap_algorithms] have the same
+interface as [classref boost::intrusive::rbtree_algorithms rbtree_algorithms].
+
+[c++]
+
+ template<class NodeTraits>
+ struct treap_algorithms;
+
+[classref boost::intrusive::treap_algorithms treap_algorithms]
+is configured with a NodeTraits class, which encapsulates
+the information about the node to be manipulated. NodeTraits must support the
+following interface:
+
+[*Typedefs]:
+
+* `node`: The type of the node that forms the circular treap
+
+* `node_ptr`: The type of a pointer to a node (usually node*)
+
+* `const_node_ptr`: The type of a pointer to a const node (usually const node*)
+
+[*Static functions]:
+
+* `static node_ptr get_parent(const_node_ptr n);`:
+ Returns a pointer to the parent node stored in "n".
+
+* `static void set_parent(node_ptr n, node_ptr p);`:
+ Sets the pointer to the parent node stored in "n" to "p".
+
+* `static node_ptr get_left(const_node_ptr n);`:
+ Returns a pointer to the left node stored in "n".
+
+* `static void set_left(node_ptr n, node_ptr l);`:
+ Sets the pointer to the left node stored in "n" to "l".
+
+* `static node_ptr get_right(const_node_ptr n);`:
+ Returns a pointer to the right node stored in "n".
+
+* `static void set_right(node_ptr n, node_ptr r);`:
+ Sets the pointer to the right node stored in "n" to "r".
+
+Once we have a node traits configuration we can use [*Boost.Intrusive] algorithms
+with our nodes:
+
+[import ../example/doc_treap_algorithms.cpp]
+[doc_treap_algorithms_code]
+
+For a complete list of functions see
+[classref boost::intrusive::treap_algorithms treap_algorithms reference].
+
+[endsect]
+
+
[/
/
/[section:sgtree_algorithms Intrusive sg tree algorithms]
@@ -3488,6 +3701,15 @@
[section:release_notes Release Notes]
+[section:release_notes_boost_1_38_00 Boost 1.38 Release]
+
+* New treap-based containers: treap, treap_set, treap_multiset.
+* Corrected compilation bug for Windows-based 64 bit compilers.
+* Corrected exception-safety bugs in container constructors.
+* Updated documentation to show rvalue-references funcions instead of emulation functions.
+
+[endsect]
+
[section:release_notes_boost_1_37_00 Boost 1.37 Release]
* Intrusive now takes advantage of compilers with variadic templates.
@@ -3577,7 +3799,7 @@
[endsect]
-[xinclude autodoc.xml]
+[/xinclude autodoc.xml]
[section:license_notices License notices]
Modified: trunk/libs/intrusive/example/doc_advanced_value_traits.cpp
==============================================================================
--- trunk/libs/intrusive/example/doc_advanced_value_traits.cpp (original)
+++ trunk/libs/intrusive/example/doc_advanced_value_traits.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
/////////////////////////////////////////////////////////////////////////////
//
-// (C) Copyright Ion Gaztanaga 2006-2007
+// (C) Copyright Ion Gaztanaga 2006-2008
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
Modified: trunk/libs/intrusive/example/doc_advanced_value_traits2.cpp
==============================================================================
--- trunk/libs/intrusive/example/doc_advanced_value_traits2.cpp (original)
+++ trunk/libs/intrusive/example/doc_advanced_value_traits2.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
/////////////////////////////////////////////////////////////////////////////
//
-// (C) Copyright Ion Gaztanaga 2006-2007
+// (C) Copyright Ion Gaztanaga 2006-2008
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
Modified: trunk/libs/intrusive/example/doc_assoc_optimized_code.cpp
==============================================================================
--- trunk/libs/intrusive/example/doc_assoc_optimized_code.cpp (original)
+++ trunk/libs/intrusive/example/doc_assoc_optimized_code.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
/////////////////////////////////////////////////////////////////////////////
//
-// (C) Copyright Ion Gaztanaga 2006-2007
+// (C) Copyright Ion Gaztanaga 2006-2008
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
Modified: trunk/libs/intrusive/example/doc_auto_unlink.cpp
==============================================================================
--- trunk/libs/intrusive/example/doc_auto_unlink.cpp (original)
+++ trunk/libs/intrusive/example/doc_auto_unlink.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
/////////////////////////////////////////////////////////////////////////////
//
-// (C) Copyright Ion Gaztanaga 2006-2007
+// (C) Copyright Ion Gaztanaga 2006-2008
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
Modified: trunk/libs/intrusive/example/doc_avl_set.cpp
==============================================================================
--- trunk/libs/intrusive/example/doc_avl_set.cpp (original)
+++ trunk/libs/intrusive/example/doc_avl_set.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
/////////////////////////////////////////////////////////////////////////////
//
-// (C) Copyright Ion Gaztanaga 2006-2007
+// (C) Copyright Ion Gaztanaga 2006-2008
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
Modified: trunk/libs/intrusive/example/doc_avltree_algorithms.cpp
==============================================================================
--- trunk/libs/intrusive/example/doc_avltree_algorithms.cpp (original)
+++ trunk/libs/intrusive/example/doc_avltree_algorithms.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
/////////////////////////////////////////////////////////////////////////////
//
-// (C) Copyright Ion Gaztanaga 2007
+// (C) Copyright Ion Gaztanaga 2007-2008
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
@@ -47,7 +47,7 @@
struct node_ptr_compare
{
- bool operator()(my_node *a, my_node *b)
+ bool operator()(const my_node *a, const my_node *b)
{ return a->int_ < b->int_; }
};
Modified: trunk/libs/intrusive/example/doc_bucket_traits.cpp
==============================================================================
--- trunk/libs/intrusive/example/doc_bucket_traits.cpp (original)
+++ trunk/libs/intrusive/example/doc_bucket_traits.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
/////////////////////////////////////////////////////////////////////////////
//
-// (C) Copyright Ion Gaztanaga 2007
+// (C) Copyright Ion Gaztanaga 2007-2008
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
Modified: trunk/libs/intrusive/example/doc_clone_from.cpp
==============================================================================
--- trunk/libs/intrusive/example/doc_clone_from.cpp (original)
+++ trunk/libs/intrusive/example/doc_clone_from.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
/////////////////////////////////////////////////////////////////////////////
//
-// (C) Copyright Ion Gaztanaga 2006-2007
+// (C) Copyright Ion Gaztanaga 2006-2008
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
Modified: trunk/libs/intrusive/example/doc_entity.cpp
==============================================================================
--- trunk/libs/intrusive/example/doc_entity.cpp (original)
+++ trunk/libs/intrusive/example/doc_entity.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
/////////////////////////////////////////////////////////////////////////////
//
-// (C) Copyright Ion Gaztanaga 2006-2007
+// (C) Copyright Ion Gaztanaga 2006-2008
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
Modified: trunk/libs/intrusive/example/doc_erasing_and_disposing.cpp
==============================================================================
--- trunk/libs/intrusive/example/doc_erasing_and_disposing.cpp (original)
+++ trunk/libs/intrusive/example/doc_erasing_and_disposing.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
/////////////////////////////////////////////////////////////////////////////
//
-// (C) Copyright Ion Gaztanaga 2006-2007
+// (C) Copyright Ion Gaztanaga 2006-2008
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
Modified: trunk/libs/intrusive/example/doc_external_value_traits.cpp
==============================================================================
--- trunk/libs/intrusive/example/doc_external_value_traits.cpp (original)
+++ trunk/libs/intrusive/example/doc_external_value_traits.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
/////////////////////////////////////////////////////////////////////////////
//
-// (C) Copyright Ion Gaztanaga 2007
+// (C) Copyright Ion Gaztanaga 2007-2008
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
Modified: trunk/libs/intrusive/example/doc_how_to_use.cpp
==============================================================================
--- trunk/libs/intrusive/example/doc_how_to_use.cpp (original)
+++ trunk/libs/intrusive/example/doc_how_to_use.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
/////////////////////////////////////////////////////////////////////////////
//
-// (C) Copyright Ion Gaztanaga 2006-2007
+// (C) Copyright Ion Gaztanaga 2006-2008
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
Modified: trunk/libs/intrusive/example/doc_iterator_from_value.cpp
==============================================================================
--- trunk/libs/intrusive/example/doc_iterator_from_value.cpp (original)
+++ trunk/libs/intrusive/example/doc_iterator_from_value.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
/////////////////////////////////////////////////////////////////////////////
//
-// (C) Copyright Ion Gaztanaga 2006-2007
+// (C) Copyright Ion Gaztanaga 2006-2008
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
Modified: trunk/libs/intrusive/example/doc_list.cpp
==============================================================================
--- trunk/libs/intrusive/example/doc_list.cpp (original)
+++ trunk/libs/intrusive/example/doc_list.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
/////////////////////////////////////////////////////////////////////////////
//
-// (C) Copyright Ion Gaztanaga 2006-2007
+// (C) Copyright Ion Gaztanaga 2006-2008
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
Modified: trunk/libs/intrusive/example/doc_list_algorithms.cpp
==============================================================================
--- trunk/libs/intrusive/example/doc_list_algorithms.cpp (original)
+++ trunk/libs/intrusive/example/doc_list_algorithms.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
/////////////////////////////////////////////////////////////////////////////
//
-// (C) Copyright Ion Gaztanaga 2006-2007
+// (C) Copyright Ion Gaztanaga 2006-2008
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
Modified: trunk/libs/intrusive/example/doc_offset_ptr.cpp
==============================================================================
--- trunk/libs/intrusive/example/doc_offset_ptr.cpp (original)
+++ trunk/libs/intrusive/example/doc_offset_ptr.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
/////////////////////////////////////////////////////////////////////////////
//
-// (C) Copyright Ion Gaztanaga 2006-2007
+// (C) Copyright Ion Gaztanaga 2006-2008
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
Modified: trunk/libs/intrusive/example/doc_rbtree_algorithms.cpp
==============================================================================
--- trunk/libs/intrusive/example/doc_rbtree_algorithms.cpp (original)
+++ trunk/libs/intrusive/example/doc_rbtree_algorithms.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
/////////////////////////////////////////////////////////////////////////////
//
-// (C) Copyright Ion Gaztanaga 2006-2007
+// (C) Copyright Ion Gaztanaga 2006-2008
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
@@ -45,7 +45,7 @@
struct node_ptr_compare
{
- bool operator()(my_node *a, my_node *b)
+ bool operator()(const my_node *a, const my_node *b)
{ return a->int_ < b->int_; }
};
Modified: trunk/libs/intrusive/example/doc_set.cpp
==============================================================================
--- trunk/libs/intrusive/example/doc_set.cpp (original)
+++ trunk/libs/intrusive/example/doc_set.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
/////////////////////////////////////////////////////////////////////////////
//
-// (C) Copyright Ion Gaztanaga 2006-2007
+// (C) Copyright Ion Gaztanaga 2006-2008
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
Modified: trunk/libs/intrusive/example/doc_sg_set.cpp
==============================================================================
--- trunk/libs/intrusive/example/doc_sg_set.cpp (original)
+++ trunk/libs/intrusive/example/doc_sg_set.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
/////////////////////////////////////////////////////////////////////////////
//
-// (C) Copyright Ion Gaztanaga 2007
+// (C) Copyright Ion Gaztanaga 2007-2008
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
Modified: trunk/libs/intrusive/example/doc_slist.cpp
==============================================================================
--- trunk/libs/intrusive/example/doc_slist.cpp (original)
+++ trunk/libs/intrusive/example/doc_slist.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
/////////////////////////////////////////////////////////////////////////////
//
-// (C) Copyright Ion Gaztanaga 2006-2007
+// (C) Copyright Ion Gaztanaga 2006-2008
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
Modified: trunk/libs/intrusive/example/doc_slist_algorithms.cpp
==============================================================================
--- trunk/libs/intrusive/example/doc_slist_algorithms.cpp (original)
+++ trunk/libs/intrusive/example/doc_slist_algorithms.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
/////////////////////////////////////////////////////////////////////////////
//
-// (C) Copyright Ion Gaztanaga 2006-2007
+// (C) Copyright Ion Gaztanaga 2006-2008
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
Modified: trunk/libs/intrusive/example/doc_splay_algorithms.cpp
==============================================================================
--- trunk/libs/intrusive/example/doc_splay_algorithms.cpp (original)
+++ trunk/libs/intrusive/example/doc_splay_algorithms.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
/////////////////////////////////////////////////////////////////////////////
//
-// (C) Copyright Ion Gaztanaga 2006-2007
+// (C) Copyright Ion Gaztanaga 2006-2008
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
@@ -41,7 +41,7 @@
struct node_ptr_compare
{
- bool operator()(my_node *a, my_node *b)
+ bool operator()(const my_node *a, const my_node *b)
{ return a->int_ < b->int_; }
};
Modified: trunk/libs/intrusive/example/doc_splay_set.cpp
==============================================================================
--- trunk/libs/intrusive/example/doc_splay_set.cpp (original)
+++ trunk/libs/intrusive/example/doc_splay_set.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
/////////////////////////////////////////////////////////////////////////////
//
-// (C) Copyright Ion Gaztanaga 2006-2007
+// (C) Copyright Ion Gaztanaga 2006-2008
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
Modified: trunk/libs/intrusive/example/doc_splaytree_algorithms.cpp
==============================================================================
--- trunk/libs/intrusive/example/doc_splaytree_algorithms.cpp (original)
+++ trunk/libs/intrusive/example/doc_splaytree_algorithms.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
/////////////////////////////////////////////////////////////////////////////
//
-// (C) Copyright Ion Gaztanaga 2007
+// (C) Copyright Ion Gaztanaga 2007-2008
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
@@ -40,7 +40,7 @@
struct node_ptr_compare
{
- bool operator()(my_node *a, my_node *b)
+ bool operator()(const my_node *a, const my_node *b)
{ return a->int_ < b->int_; }
};
Modified: trunk/libs/intrusive/example/doc_stateful_value_traits.cpp
==============================================================================
--- trunk/libs/intrusive/example/doc_stateful_value_traits.cpp (original)
+++ trunk/libs/intrusive/example/doc_stateful_value_traits.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
/////////////////////////////////////////////////////////////////////////////
//
-// (C) Copyright Ion Gaztanaga 2007
+// (C) Copyright Ion Gaztanaga 2007-2008
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
Added: trunk/libs/intrusive/example/doc_treap_algorithms.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/intrusive/example/doc_treap_algorithms.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -0,0 +1,79 @@
+/////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2007-2008
+//
+// 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;
+}
+
+//]
Added: trunk/libs/intrusive/example/doc_treap_set.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/intrusive/example/doc_treap_set.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -0,0 +1,106 @@
+/////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2006-2008
+//
+// 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 <algorithm>
+#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()), rbitend(baseset.rend());
+ MemberMultiset::iterator mit(membermultiset.begin()), mitend(membermultiset.end());
+ 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;
+}
+//]
Modified: trunk/libs/intrusive/example/doc_unordered_set.cpp
==============================================================================
--- trunk/libs/intrusive/example/doc_unordered_set.cpp (original)
+++ trunk/libs/intrusive/example/doc_unordered_set.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
/////////////////////////////////////////////////////////////////////////////
//
-// (C) Copyright Ion Gaztanaga 2006-2007
+// (C) Copyright Ion Gaztanaga 2006-2008
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
Modified: trunk/libs/intrusive/example/doc_value_traits.cpp
==============================================================================
--- trunk/libs/intrusive/example/doc_value_traits.cpp (original)
+++ trunk/libs/intrusive/example/doc_value_traits.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
/////////////////////////////////////////////////////////////////////////////
//
-// (C) Copyright Ion Gaztanaga 2006-2007
+// (C) Copyright Ion Gaztanaga 2006-2008
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
Modified: trunk/libs/intrusive/example/doc_window.cpp
==============================================================================
--- trunk/libs/intrusive/example/doc_window.cpp (original)
+++ trunk/libs/intrusive/example/doc_window.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
/////////////////////////////////////////////////////////////////////////////
//
-// (C) Copyright Ion Gaztanaga 2006-2007
+// (C) Copyright Ion Gaztanaga 2006-2008
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
Modified: trunk/libs/intrusive/perf/perf_list.cpp
==============================================================================
--- trunk/libs/intrusive/perf/perf_list.cpp (original)
+++ trunk/libs/intrusive/perf/perf_list.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
/////////////////////////////////////////////////////////////////////////////
//
-// (C) Copyright Ion Gaztanaga 2007
+// (C) Copyright Ion Gaztanaga 2007-2008
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
@@ -11,6 +11,7 @@
/////////////////////////////////////////////////////////////////////////////
//Includes for tests
+#include <boost/intrusive/detail/config_begin.hpp>
#include <boost/config.hpp>
#include <list>
#include <functional>
@@ -545,3 +546,5 @@
do_all_tests<true>();
return 0;
}
+
+#include <boost/intrusive/detail/config_end.hpp>
Modified: trunk/libs/intrusive/proj/vc7ide/Intrusive.sln
==============================================================================
--- trunk/libs/intrusive/proj/vc7ide/Intrusive.sln (original)
+++ trunk/libs/intrusive/proj/vc7ide/Intrusive.sln 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -83,6 +83,14 @@
ProjectSection(ProjectDependencies) = postProject
EndProjectSection
EndProject
+Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "treap_set", "treap_set\treap_set.vcproj", "{1E09E697-4A2F-BC76-7C91-2BA479B29159}"
+ ProjectSection(ProjectDependencies) = postProject
+ EndProjectSection
+EndProject
+Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "treap_multiset", "treap_multiset\treap_multiset.vcproj", "{16E09E95-F4A2-C971-BC76-9BA407191C59}"
+ ProjectSection(ProjectDependencies) = postProject
+ EndProjectSection
+EndProject
Global
GlobalSection(SolutionConfiguration) = preSolution
Debug = Debug
@@ -175,6 +183,14 @@
{97B61B24-4C97-9681-50BF-243175A813B6}.Debug.Build.0 = Debug|Win32
{97B61B24-4C97-9681-50BF-243175A813B6}.Release.ActiveCfg = Release|Win32
{97B61B24-4C97-9681-50BF-243175A813B6}.Release.Build.0 = Release|Win32
+ {1E09E697-4A2F-BC76-7C91-2BA479B29159}.Debug.ActiveCfg = Debug|Win32
+ {1E09E697-4A2F-BC76-7C91-2BA479B29159}.Debug.Build.0 = Debug|Win32
+ {1E09E697-4A2F-BC76-7C91-2BA479B29159}.Release.ActiveCfg = Release|Win32
+ {1E09E697-4A2F-BC76-7C91-2BA479B29159}.Release.Build.0 = Release|Win32
+ {16E09E95-F4A2-C971-BC76-9BA407191C59}.Debug.ActiveCfg = Debug|Win32
+ {16E09E95-F4A2-C971-BC76-9BA407191C59}.Debug.Build.0 = Debug|Win32
+ {16E09E95-F4A2-C971-BC76-9BA407191C59}.Release.ActiveCfg = Release|Win32
+ {16E09E95-F4A2-C971-BC76-9BA407191C59}.Release.Build.0 = Release|Win32
EndGlobalSection
GlobalSection(ExtensibilityGlobals) = postSolution
EndGlobalSection
Modified: trunk/libs/intrusive/proj/vc7ide/_intrusivelib/_intrusivelib.vcproj
==============================================================================
--- trunk/libs/intrusive/proj/vc7ide/_intrusivelib/_intrusivelib.vcproj (original)
+++ trunk/libs/intrusive/proj/vc7ide/_intrusivelib/_intrusivelib.vcproj 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -199,6 +199,15 @@
RelativePath="..\..\..\..\..\boost\intrusive\splaytree_algorithms.hpp">
</File>
<File
+ RelativePath="..\..\..\..\..\boost\intrusive\treap.hpp">
+ </File>
+ <File
+ RelativePath="..\..\..\..\..\boost\intrusive\treap_algorithms.hpp">
+ </File>
+ <File
+ RelativePath="..\..\..\..\..\boost\intrusive\treap_set.hpp">
+ </File>
+ <File
RelativePath="..\..\..\..\..\boost\intrusive\trivial_value_traits.hpp">
</File>
<File
@@ -220,6 +229,9 @@
RelativePath="..\..\..\..\..\boost\intrusive\detail\avltree_node.hpp">
</File>
<File
+ RelativePath="..\..\..\..\..\boost\intrusive\detail\clear_on_destructor_base.hpp">
+ </File>
+ <File
RelativePath="..\..\..\..\..\boost\intrusive\detail\common_slist_algorithms.hpp">
</File>
<File
@@ -398,6 +410,12 @@
RelativePath="..\..\..\example\doc_stateful_value_traits.cpp">
</File>
<File
+ RelativePath="..\..\..\example\doc_treap_algorithms.cpp">
+ </File>
+ <File
+ RelativePath="..\..\..\example\doc_treap_set.cpp">
+ </File>
+ <File
RelativePath="..\..\..\example\doc_unordered_set.cpp">
</File>
<File
Modified: trunk/libs/intrusive/proj/vc7ide/to-do.txt
==============================================================================
--- trunk/libs/intrusive/proj/vc7ide/to-do.txt (original)
+++ trunk/libs/intrusive/proj/vc7ide/to-do.txt 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,3 +1,26 @@
+/////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2006-2008
+//
+// 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.
+//
+/////////////////////////////////////////////////////////////////////////////
-> Implement C++0x features (variadic templates & rvalue references)
-> Offer bidirectional iterator for hashtables
-> Non-array buckets
+-> Document incremental<> option better
+
+-> Revise treap's hooks should be restored if the operation throws
+-> Revise treap help to add priority changes (throw, new functions, etc.)
+-> Revise make_functions, and any hook tests to add missing containers
+-> On exceptions, auto_unlink/safe_link hooks default state should be recovered
+ (insert_equal, insert_lower_bound, insert_equal_upper_bound)
+-> insert_unique_check should also compare priorities.
+-> test insert_unique_check with hint in tests
+-> revise strong exception safety concepts for treap::erase functions.
+ What happens with range deletions?
+-> Assure stable order for optimize_multikey and inverse order otherwise
Added: trunk/libs/intrusive/proj/vc7ide/treap_multiset/treap_multiset.vcproj
==============================================================================
--- (empty file)
+++ trunk/libs/intrusive/proj/vc7ide/treap_multiset/treap_multiset.vcproj 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -0,0 +1,127 @@
+<?xml version="1.0" encoding="Windows-1252"?>
+<VisualStudioProject
+ ProjectType="Visual C++"
+ Version="7.10"
+ Name="treap_multiset"
+ ProjectGUID="{16E09E95-F4A2-C971-BC76-9BA407191C59}"
+ Keyword="Win32Proj">
+ <Platforms>
+ <Platform
+ Name="Win32"/>
+ </Platforms>
+ <Configurations>
+ <Configuration
+ Name="Debug|Win32"
+ OutputDirectory="Debug"
+ IntermediateDirectory="Debug"
+ ConfigurationType="1"
+ CharacterSet="2">
+ <Tool
+ Name="VCCLCompilerTool"
+ Optimization="0"
+ AdditionalIncludeDirectories="../../../../../"
+ PreprocessorDefinitions="WIN32;_DEBUG;_CONSOLE"
+ MinimalRebuild="TRUE"
+ BasicRuntimeChecks="3"
+ RuntimeLibrary="5"
+ DisableLanguageExtensions="TRUE"
+ TreatWChar_tAsBuiltInType="TRUE"
+ ForceConformanceInForLoopScope="TRUE"
+ UsePrecompiledHeader="0"
+ WarningLevel="4"
+ Detect64BitPortabilityProblems="TRUE"
+ DebugInformationFormat="4"/>
+ <Tool
+ Name="VCCustomBuildTool"/>
+ <Tool
+ Name="VCLinkerTool"
+ OutputFile="$(OutDir)/treap_multiset.exe"
+ LinkIncremental="2"
+ GenerateDebugInformation="TRUE"
+ ProgramDatabaseFile="$(OutDir)/treap_multiset.pdb"
+ SubSystem="1"
+ TargetMachine="1"/>
+ <Tool
+ Name="VCMIDLTool"/>
+ <Tool
+ Name="VCPostBuildEventTool"/>
+ <Tool
+ Name="VCPreBuildEventTool"/>
+ <Tool
+ Name="VCPreLinkEventTool"/>
+ <Tool
+ Name="VCResourceCompilerTool"/>
+ <Tool
+ Name="VCWebServiceProxyGeneratorTool"/>
+ <Tool
+ Name="VCXMLDataGeneratorTool"/>
+ <Tool
+ Name="VCWebDeploymentTool"/>
+ <Tool
+ Name="VCManagedWrapperGeneratorTool"/>
+ <Tool
+ Name="VCAuxiliaryManagedWrapperGeneratorTool"/>
+ </Configuration>
+ <Configuration
+ Name="Release|Win32"
+ OutputDirectory="Release"
+ IntermediateDirectory="Release"
+ ConfigurationType="1"
+ CharacterSet="2">
+ <Tool
+ Name="VCCLCompilerTool"
+ AdditionalIncludeDirectories="../../../../../"
+ PreprocessorDefinitions="WIN32;NDEBUG;_CONSOLE"
+ RuntimeLibrary="4"
+ UsePrecompiledHeader="0"
+ WarningLevel="3"
+ Detect64BitPortabilityProblems="TRUE"
+ DebugInformationFormat="3"/>
+ <Tool
+ Name="VCCustomBuildTool"/>
+ <Tool
+ Name="VCLinkerTool"
+ OutputFile="$(OutDir)/treap_multiset.exe"
+ LinkIncremental="1"
+ GenerateDebugInformation="TRUE"
+ SubSystem="1"
+ OptimizeReferences="2"
+ EnableCOMDATFolding="2"
+ TargetMachine="1"/>
+ <Tool
+ Name="VCMIDLTool"/>
+ <Tool
+ Name="VCPostBuildEventTool"/>
+ <Tool
+ Name="VCPreBuildEventTool"/>
+ <Tool
+ Name="VCPreLinkEventTool"/>
+ <Tool
+ Name="VCResourceCompilerTool"/>
+ <Tool
+ Name="VCWebServiceProxyGeneratorTool"/>
+ <Tool
+ Name="VCXMLDataGeneratorTool"/>
+ <Tool
+ Name="VCWebDeploymentTool"/>
+ <Tool
+ Name="VCManagedWrapperGeneratorTool"/>
+ <Tool
+ Name="VCAuxiliaryManagedWrapperGeneratorTool"/>
+ </Configuration>
+ </Configurations>
+ <References>
+ </References>
+ <Files>
+ <Filter
+ Name="Source Files"
+ Filter="cpp;c;cxx;def;odl;idl;hpj;bat;asm;asmx"
+ UniqueIdentifier="{F0B77631-E357-26F3-A4F5-2FA254B7E734}">
+ <File
+ RelativePath="..\..\..\test\treap_multiset_test.cpp">
+ </File>
+ </Filter>
+ </Files>
+ <Globals>
+ </Globals>
+</VisualStudioProject>
Added: trunk/libs/intrusive/proj/vc7ide/treap_set/treap_set.vcproj
==============================================================================
--- (empty file)
+++ trunk/libs/intrusive/proj/vc7ide/treap_set/treap_set.vcproj 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -0,0 +1,127 @@
+<?xml version="1.0" encoding="Windows-1252"?>
+<VisualStudioProject
+ ProjectType="Visual C++"
+ Version="7.10"
+ Name="treap_set"
+ ProjectGUID="{1E09E697-4A2F-BC76-7C91-2BA479B29159}"
+ Keyword="Win32Proj">
+ <Platforms>
+ <Platform
+ Name="Win32"/>
+ </Platforms>
+ <Configurations>
+ <Configuration
+ Name="Debug|Win32"
+ OutputDirectory="Debug"
+ IntermediateDirectory="Debug"
+ ConfigurationType="1"
+ CharacterSet="2">
+ <Tool
+ Name="VCCLCompilerTool"
+ Optimization="0"
+ AdditionalIncludeDirectories="../../../../../"
+ PreprocessorDefinitions="WIN32;_DEBUG;_CONSOLE"
+ MinimalRebuild="TRUE"
+ BasicRuntimeChecks="3"
+ RuntimeLibrary="5"
+ DisableLanguageExtensions="TRUE"
+ TreatWChar_tAsBuiltInType="TRUE"
+ ForceConformanceInForLoopScope="TRUE"
+ UsePrecompiledHeader="0"
+ WarningLevel="4"
+ Detect64BitPortabilityProblems="TRUE"
+ DebugInformationFormat="4"/>
+ <Tool
+ Name="VCCustomBuildTool"/>
+ <Tool
+ Name="VCLinkerTool"
+ OutputFile="$(OutDir)/treap_set.exe"
+ LinkIncremental="2"
+ GenerateDebugInformation="TRUE"
+ ProgramDatabaseFile="$(OutDir)/treap_set.pdb"
+ SubSystem="1"
+ TargetMachine="1"/>
+ <Tool
+ Name="VCMIDLTool"/>
+ <Tool
+ Name="VCPostBuildEventTool"/>
+ <Tool
+ Name="VCPreBuildEventTool"/>
+ <Tool
+ Name="VCPreLinkEventTool"/>
+ <Tool
+ Name="VCResourceCompilerTool"/>
+ <Tool
+ Name="VCWebServiceProxyGeneratorTool"/>
+ <Tool
+ Name="VCXMLDataGeneratorTool"/>
+ <Tool
+ Name="VCWebDeploymentTool"/>
+ <Tool
+ Name="VCManagedWrapperGeneratorTool"/>
+ <Tool
+ Name="VCAuxiliaryManagedWrapperGeneratorTool"/>
+ </Configuration>
+ <Configuration
+ Name="Release|Win32"
+ OutputDirectory="Release"
+ IntermediateDirectory="Release"
+ ConfigurationType="1"
+ CharacterSet="2">
+ <Tool
+ Name="VCCLCompilerTool"
+ AdditionalIncludeDirectories="../../../../../"
+ PreprocessorDefinitions="WIN32;NDEBUG;_CONSOLE"
+ RuntimeLibrary="4"
+ UsePrecompiledHeader="0"
+ WarningLevel="3"
+ Detect64BitPortabilityProblems="TRUE"
+ DebugInformationFormat="3"/>
+ <Tool
+ Name="VCCustomBuildTool"/>
+ <Tool
+ Name="VCLinkerTool"
+ OutputFile="$(OutDir)/treap_set.exe"
+ LinkIncremental="1"
+ GenerateDebugInformation="TRUE"
+ SubSystem="1"
+ OptimizeReferences="2"
+ EnableCOMDATFolding="2"
+ TargetMachine="1"/>
+ <Tool
+ Name="VCMIDLTool"/>
+ <Tool
+ Name="VCPostBuildEventTool"/>
+ <Tool
+ Name="VCPreBuildEventTool"/>
+ <Tool
+ Name="VCPreLinkEventTool"/>
+ <Tool
+ Name="VCResourceCompilerTool"/>
+ <Tool
+ Name="VCWebServiceProxyGeneratorTool"/>
+ <Tool
+ Name="VCXMLDataGeneratorTool"/>
+ <Tool
+ Name="VCWebDeploymentTool"/>
+ <Tool
+ Name="VCManagedWrapperGeneratorTool"/>
+ <Tool
+ Name="VCAuxiliaryManagedWrapperGeneratorTool"/>
+ </Configuration>
+ </Configurations>
+ <References>
+ </References>
+ <Files>
+ <Filter
+ Name="Source Files"
+ Filter="cpp;c;cxx;def;odl;idl;hpj;bat;asm;asmx"
+ UniqueIdentifier="{FB776C10-E357-A4F5-326F-42A2D7254B3F}">
+ <File
+ RelativePath="..\..\..\test\treap_set_test.cpp">
+ </File>
+ </Filter>
+ </Files>
+ <Globals>
+ </Globals>
+</VisualStudioProject>
Modified: trunk/libs/intrusive/test/any_test.cpp
==============================================================================
--- trunk/libs/intrusive/test/any_test.cpp (original)
+++ trunk/libs/intrusive/test/any_test.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,7 +1,7 @@
/////////////////////////////////////////////////////////////////////////////
//
// (C) Copyright Olaf Krzikalla 2004-2006.
-// (C) Copyright Ion Gaztanaga 2006-2007.
+// (C) Copyright Ion Gaztanaga 2006-2008.
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
@@ -18,6 +18,7 @@
#include<boost/intrusive/avltree.hpp>
#include<boost/intrusive/sgtree.hpp>
#include<boost/intrusive/splaytree.hpp>
+#include<boost/intrusive/treap.hpp>
#include<boost/intrusive/hashtable.hpp>
#include<boost/functional/hash.hpp>
#include <vector> //std::vector
@@ -48,8 +49,12 @@
friend std::size_t hash_value(const MyClass &o)
{ return boost::hash<int>()(o.get()); }
+
+ friend bool priority_order(const MyClass &a, const MyClass &b)
+ { return a.int_ < b.int_; }
};
+
void instantiation_test()
{
typedef member_hook< MyClass, any_member_hook<>, &MyClass::member_hook_> MemberHook;
@@ -97,6 +102,14 @@
sgtree_member.insert_unique(myclass);
}
{
+ treap < MyClass, any_to_bs_set_hook< BaseHook > > treap_base;
+ treap_base.insert_unique(myclass);
+ }
+ {
+ treap < MyClass, any_to_bs_set_hook< MemberHook > > treap_member;
+ treap_member.insert_unique(myclass);
+ }
+ {
splaytree < MyClass, any_to_bs_set_hook< BaseHook > > splaytree_base;
splaytree_base.insert_unique(myclass);
}
Modified: trunk/libs/intrusive/test/avl_multiset_test.cpp
==============================================================================
--- trunk/libs/intrusive/test/avl_multiset_test.cpp (original)
+++ trunk/libs/intrusive/test/avl_multiset_test.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,7 +1,7 @@
/////////////////////////////////////////////////////////////////////////////
//
// (C) Copyright Olaf Krzikalla 2004-2006.
-// (C) Copyright Ion Gaztanaga 2006-2007.
+// (C) Copyright Ion Gaztanaga 2006-2008.
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
@@ -17,6 +17,26 @@
#include "smart_ptr.hpp"
#include "generic_multiset_test.hpp"
+using namespace boost::intrusive;
+
+struct my_tag;
+
+template<class VoidPointer>
+struct hooks
+{
+ typedef avl_set_base_hook<void_pointer<VoidPointer> > base_hook_type;
+ typedef avl_set_base_hook
+ <link_mode<auto_unlink>
+ , void_pointer<VoidPointer>
+ , tag<my_tag>
+ , optimize_size<true> > auto_base_hook_type;
+ typedef avl_set_member_hook
+ <void_pointer<VoidPointer> > member_hook_type;
+ typedef avl_set_member_hook
+ < link_mode<auto_unlink>
+ , void_pointer<VoidPointer> > auto_member_hook_type;
+};
+
template< class ValueType
, class Option1 = boost::intrusive::none
, class Option2 = boost::intrusive::none
@@ -39,19 +59,19 @@
int operator()()
{
using namespace boost::intrusive;
- typedef testvalue<VoidPointer, constant_time_size> value_type;
+ typedef testvalue<hooks<VoidPointer> , constant_time_size> value_type;
test::test_generic_multiset < typename detail::get_base_value_traits
< value_type
- , typename value_type::avl_set_base_hook_t
+ , typename hooks<VoidPointer>::base_hook_type
>::type
, GetContainer
>::test_all();
test::test_generic_multiset < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
- , typename value_type::avl_set_member_hook_t
- , &value_type::avl_set_node_
+ , typename hooks<VoidPointer>::member_hook_type
+ , &value_type::node_
>
>::type
, GetContainer
@@ -67,11 +87,11 @@
int operator()()
{
using namespace boost::intrusive;
- typedef testvalue<VoidPointer, false> value_type;
+ typedef testvalue<hooks<VoidPointer> , false> value_type;
test::test_generic_multiset < typename detail::get_base_value_traits
< value_type
- , typename value_type::avl_set_base_hook_t
+ , typename hooks<VoidPointer>::base_hook_type
>::type
, GetContainer
>::test_all();
@@ -79,8 +99,8 @@
test::test_generic_multiset < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
- , typename value_type::avl_set_member_hook_t
- , &value_type::avl_set_node_
+ , typename hooks<VoidPointer>::member_hook_type
+ , &value_type::node_
>
>::type
, GetContainer
@@ -88,7 +108,7 @@
test::test_generic_multiset < typename detail::get_base_value_traits
< value_type
- , typename value_type::avl_set_auto_base_hook_t
+ , typename hooks<VoidPointer>::auto_base_hook_type
>::type
, GetContainer
>::test_all();
@@ -96,8 +116,8 @@
test::test_generic_multiset < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
- , typename value_type::avl_set_auto_member_hook_t
- , &value_type::avl_set_auto_node_
+ , typename hooks<VoidPointer>::auto_member_hook_type
+ , &value_type::auto_node_
>
>::type
, GetContainer
Modified: trunk/libs/intrusive/test/avl_set_test.cpp
==============================================================================
--- trunk/libs/intrusive/test/avl_set_test.cpp (original)
+++ trunk/libs/intrusive/test/avl_set_test.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,7 +1,7 @@
/////////////////////////////////////////////////////////////////////////////
//
// (C) Copyright Olaf Krzikalla 2004-2006.
-// (C) Copyright Ion Gaztanaga 2006-2007.
+// (C) Copyright Ion Gaztanaga 2006-2008.
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
@@ -16,6 +16,26 @@
#include "smart_ptr.hpp"
#include "generic_set_test.hpp"
+using namespace boost::intrusive;
+
+struct my_tag;
+
+template<class VoidPointer>
+struct hooks
+{
+ typedef avl_set_base_hook<void_pointer<VoidPointer> > base_hook_type;
+ typedef avl_set_base_hook
+ <link_mode<auto_unlink>
+ , void_pointer<VoidPointer>
+ , tag<my_tag>
+ , optimize_size<true> > auto_base_hook_type;
+ typedef avl_set_member_hook
+ <void_pointer<VoidPointer> > member_hook_type;
+ typedef avl_set_member_hook
+ < link_mode<auto_unlink>
+ , void_pointer<VoidPointer> > auto_member_hook_type;
+};
+
template< class ValueType
, class Option1 = boost::intrusive::none
, class Option2 = boost::intrusive::none
@@ -38,19 +58,19 @@
int operator()()
{
using namespace boost::intrusive;
- typedef testvalue<VoidPointer, constant_time_size> value_type;
+ typedef testvalue<hooks<VoidPointer> , constant_time_size> value_type;
test::test_generic_set < typename detail::get_base_value_traits
< value_type
- , typename value_type::avl_set_base_hook_t
+ , typename hooks<VoidPointer>::base_hook_type
>::type
, GetContainer
>::test_all();
test::test_generic_set < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
- , typename value_type::avl_set_member_hook_t
- , &value_type::avl_set_node_
+ , typename hooks<VoidPointer>::member_hook_type
+ , &value_type::node_
>
>::type
, GetContainer
@@ -66,11 +86,11 @@
int operator()()
{
using namespace boost::intrusive;
- typedef testvalue<VoidPointer, false> value_type;
+ typedef testvalue<hooks<VoidPointer> , false> value_type;
test::test_generic_set < typename detail::get_base_value_traits
< value_type
- , typename value_type::avl_set_base_hook_t
+ , typename hooks<VoidPointer>::base_hook_type
>::type
, GetContainer
>::test_all();
@@ -78,8 +98,8 @@
test::test_generic_set < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
- , typename value_type::avl_set_member_hook_t
- , &value_type::avl_set_node_
+ , typename hooks<VoidPointer>::member_hook_type
+ , &value_type::node_
>
>::type
, GetContainer
@@ -87,7 +107,7 @@
test::test_generic_set < typename detail::get_base_value_traits
< value_type
- , typename value_type::avl_set_auto_base_hook_t
+ , typename hooks<VoidPointer>::auto_base_hook_type
>::type
, GetContainer
>::test_all();
@@ -95,8 +115,8 @@
test::test_generic_set < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
- , typename value_type::avl_set_auto_member_hook_t
- , &value_type::avl_set_auto_node_
+ , typename hooks<VoidPointer>::auto_member_hook_type
+ , &value_type::auto_node_
>
>::type
, GetContainer
Modified: trunk/libs/intrusive/test/common_functors.hpp
==============================================================================
--- trunk/libs/intrusive/test/common_functors.hpp (original)
+++ trunk/libs/intrusive/test/common_functors.hpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
/////////////////////////////////////////////////////////////////////////////
//
-// (C) Copyright Ion Gaztanaga 2006-2007
+// (C) Copyright Ion Gaztanaga 2006-2008
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
Modified: trunk/libs/intrusive/test/custom_bucket_traits_test.cpp
==============================================================================
--- trunk/libs/intrusive/test/custom_bucket_traits_test.cpp (original)
+++ trunk/libs/intrusive/test/custom_bucket_traits_test.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
/////////////////////////////////////////////////////////////////////////////
//
-// (C) Copyright Ion Gaztanaga 2007
+// (C) Copyright Ion Gaztanaga 2007-2008
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
Modified: trunk/libs/intrusive/test/default_hook_test.cpp
==============================================================================
--- trunk/libs/intrusive/test/default_hook_test.cpp (original)
+++ trunk/libs/intrusive/test/default_hook_test.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
/////////////////////////////////////////////////////////////////////////////
//
-// (C) Copyright Ion Gaztanaga 2007
+// (C) Copyright Ion Gaztanaga 2007-2008
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
Modified: trunk/libs/intrusive/test/external_value_traits_test.cpp
==============================================================================
--- trunk/libs/intrusive/test/external_value_traits_test.cpp (original)
+++ trunk/libs/intrusive/test/external_value_traits_test.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
/////////////////////////////////////////////////////////////////////////////
//
-// (C) Copyright Ion Gaztanaga 2007
+// (C) Copyright Ion Gaztanaga 2007-2008
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
Modified: trunk/libs/intrusive/test/generic_assoc_test.hpp
==============================================================================
--- trunk/libs/intrusive/test/generic_assoc_test.hpp (original)
+++ trunk/libs/intrusive/test/generic_assoc_test.hpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,7 +1,7 @@
/////////////////////////////////////////////////////////////////////////////
//
// (C) Copyright Olaf Krzikalla 2004-2006.
-// (C) Copyright Ion Gaztanaga 2006-2007.
+// (C) Copyright Ion Gaztanaga 2006-2008.
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
@@ -117,16 +117,27 @@
//Now random insertions
std::random_shuffle(values.begin(), values.end());
testset.insert(&values[0], &values[0] + values.size());
- std::sort(values.begin(), values.end());
+ std::vector<value_type> values_ordered(values);
+ std::sort(values_ordered.begin(), values_ordered.end());
TEST_INTRUSIVE_SEQUENCE_EXPECTED(testset, testset.begin());
- //Random erasure
- std::random_shuffle(values.begin(), values.end());
- for(int i = 0; i != MaxValues; ++i){
- it = testset.erase(testset.iterator_to(values[i]));
- }
+ {
+ typedef typename std::vector<value_type>::const_iterator cvec_iterator;
+ //Random erasure
+ std::vector<cvec_iterator> it_vector;
+
+ for(cvec_iterator it(values.begin()), itend(values.end())
+ ; it != itend
+ ; ++it){
+ it_vector.push_back(it);
+ }
+ std::random_shuffle(it_vector.begin(), it_vector.end());
+ for(int i = 0; i != MaxValues; ++i){
+ testset.erase(testset.iterator_to(*it_vector[i]));
+ }
- BOOST_TEST(testset.empty());
+ BOOST_TEST(testset.empty());
+ }
}
template<class ValueTraits, template <class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none, class = ::boost::intrusive::none> class ContainerDefiner>
Modified: trunk/libs/intrusive/test/generic_multiset_test.hpp
==============================================================================
--- trunk/libs/intrusive/test/generic_multiset_test.hpp (original)
+++ trunk/libs/intrusive/test/generic_multiset_test.hpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,7 +1,7 @@
/////////////////////////////////////////////////////////////////////////////
//
// (C) Copyright Olaf Krzikalla 2004-2006.
-// (C) Copyright Ion Gaztanaga 2006-2007.
+// (C) Copyright Ion Gaztanaga 2006-2008.
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
Modified: trunk/libs/intrusive/test/generic_set_test.hpp
==============================================================================
--- trunk/libs/intrusive/test/generic_set_test.hpp (original)
+++ trunk/libs/intrusive/test/generic_set_test.hpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,7 +1,7 @@
/////////////////////////////////////////////////////////////////////////////
//
// (C) Copyright Olaf Krzikalla 2004-2006.
-// (C) Copyright Ion Gaztanaga 2006-2007.
+// (C) Copyright Ion Gaztanaga 2006-2008.
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
Modified: trunk/libs/intrusive/test/itestvalue.hpp
==============================================================================
--- trunk/libs/intrusive/test/itestvalue.hpp (original)
+++ trunk/libs/intrusive/test/itestvalue.hpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,7 +1,7 @@
/////////////////////////////////////////////////////////////////////////////
//
// (C) Copyright Olaf Krzikalla 2004-2006.
-// (C) Copyright Ion Gaztanaga 2006-2007.
+// (C) Copyright Ion Gaztanaga 2006-2008.
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
@@ -14,220 +14,25 @@
#define BOOST_INTRUSIVE_DETAIL_ITESTVALUE_HPP
#include <iostream>
-#include <boost/intrusive/set_hook.hpp>
-#include <boost/intrusive/list_hook.hpp>
-#include <boost/intrusive/slist_hook.hpp>
-#include <boost/intrusive/unordered_set_hook.hpp>
-#include <boost/intrusive/splay_set_hook.hpp>
-#include <boost/intrusive/avl_set_hook.hpp>
-#include <boost/intrusive/bs_set_hook.hpp>
#include <boost/intrusive/options.hpp>
#include <boost/functional/hash.hpp>
-#include "smart_ptr.hpp"
namespace boost{
namespace intrusive{
-struct my_tag;
-
-template<class VoidPointer>
-struct set_base_hook_type
-{ typedef set_base_hook<void_pointer<VoidPointer> > type; };
-
-template<class VoidPointer>
-struct set_auto_base_hook_type
-{ typedef set_base_hook<link_mode<auto_unlink>, void_pointer<VoidPointer>, tag<my_tag>, optimize_size<true> > type; };
-
-template<class VoidPointer>
-struct set_member_hook_type
-{ typedef set_member_hook<void_pointer<VoidPointer>, optimize_size<true> > type; };
-
-template<class VoidPointer>
-struct set_auto_member_hook_type
-{ typedef set_member_hook<link_mode<auto_unlink>, void_pointer<VoidPointer> > type; };
-
-template<class VoidPointer>
-struct splay_set_base_hook_type
-{ typedef splay_set_base_hook<void_pointer<VoidPointer> > type; };
-
-template<class VoidPointer>
-struct splay_set_auto_base_hook_type
-{ typedef splay_set_base_hook<link_mode<auto_unlink>, void_pointer<VoidPointer>, tag<my_tag> > type; };
-
-template<class VoidPointer>
-struct splay_set_member_hook_type
-{ typedef splay_set_member_hook<void_pointer<VoidPointer> > type; };
-
-template<class VoidPointer>
-struct splay_set_auto_member_hook_type
-{ typedef splay_set_member_hook<link_mode<auto_unlink>, void_pointer<VoidPointer> > type; };
-
-template<class VoidPointer>
-struct bs_set_base_hook_type
-{ typedef bs_set_base_hook<void_pointer<VoidPointer> > type; };
-
-template<class VoidPointer>
-struct bs_set_member_hook_type
-{ typedef bs_set_member_hook<void_pointer<VoidPointer> > type; };
-
-template<class VoidPointer>
-struct avl_set_base_hook_type
-{ typedef avl_set_base_hook<void_pointer<VoidPointer> > type; };
-
-template<class VoidPointer>
-struct avl_set_auto_base_hook_type
-{ typedef avl_set_base_hook<link_mode<auto_unlink>, void_pointer<VoidPointer>, tag<my_tag>, optimize_size<true> > type; };
-
-template<class VoidPointer>
-struct avl_set_member_hook_type
-{ typedef avl_set_member_hook<void_pointer<VoidPointer>, optimize_size<true> > type; };
-
-template<class VoidPointer>
-struct avl_set_auto_member_hook_type
-{ typedef avl_set_member_hook<link_mode<auto_unlink>, void_pointer<VoidPointer> > type; };
-
-template<class VoidPointer>
-struct list_base_hook_type
-{ typedef list_base_hook<void_pointer<VoidPointer> > type; };
-
-template<class VoidPointer>
-struct list_auto_base_hook_type
-{ typedef list_base_hook<link_mode<auto_unlink>, void_pointer<VoidPointer>, tag<my_tag> > type; };
-
-template<class VoidPointer>
-struct list_member_hook_type
-{ typedef list_member_hook<void_pointer<VoidPointer> > type; };
-
-template<class VoidPointer>
-struct list_auto_member_hook_type
-{ typedef list_member_hook<link_mode<auto_unlink>, void_pointer<VoidPointer> > type; };
-
-template<class VoidPointer>
-struct slist_base_hook_type
-{ typedef slist_base_hook<void_pointer<VoidPointer> > type; };
-
-template<class VoidPointer>
-struct slist_auto_base_hook_type
-{ typedef slist_base_hook<link_mode<auto_unlink>, void_pointer<VoidPointer>, tag<my_tag> > type; };
-
-template<class VoidPointer>
-struct slist_member_hook_type
-{ typedef slist_member_hook<void_pointer<VoidPointer> > type; };
-
-template<class VoidPointer>
-struct slist_auto_member_hook_type
-{ typedef slist_member_hook<link_mode<auto_unlink>, void_pointer<VoidPointer> > type; };
-
-template<class VoidPointer>
-struct uset_base_hook_type
-{ typedef unordered_set_base_hook<void_pointer<VoidPointer> > type; };
-
-template<class VoidPointer>
-struct uset_auto_base_hook_type
-{
- typedef unordered_set_base_hook
- < link_mode<auto_unlink>
- , void_pointer<VoidPointer>
- , tag<my_tag>
- , store_hash<true>
- > type;
-};
-
-template<class VoidPointer>
-struct uset_member_hook_type
-{
- typedef unordered_set_member_hook
- < void_pointer<VoidPointer>
- , optimize_multikey<true>
- > type;
-};
-
-template<class VoidPointer>
-struct uset_auto_member_hook_type
+struct testvalue_filler
{
- typedef unordered_set_member_hook
- < link_mode<auto_unlink>, void_pointer<VoidPointer>
- , store_hash<true>
- , optimize_multikey<true>
- > type;
+ void *dummy_[3];
};
-template<class VoidPointer, bool ConstantTimeSize>
+template<class Hooks, bool ConstantTimeSize>
struct testvalue
- : set_base_hook_type<VoidPointer>::type
- , set_auto_base_hook_type<VoidPointer>::type
- , splay_set_base_hook_type<VoidPointer>::type
- , splay_set_auto_base_hook_type<VoidPointer>::type
- , bs_set_base_hook_type<VoidPointer>::type
- , avl_set_base_hook_type<VoidPointer>::type
- , avl_set_auto_base_hook_type<VoidPointer>::type
- , list_base_hook_type<VoidPointer>::type
- , list_auto_base_hook_type<VoidPointer>::type
- , slist_base_hook_type<VoidPointer>::type
- , slist_auto_base_hook_type<VoidPointer>::type
- , uset_base_hook_type<VoidPointer>::type
- , uset_auto_base_hook_type<VoidPointer>::type
+ : testvalue_filler
+ , Hooks::base_hook_type
+ , Hooks::auto_base_hook_type
{
- typedef typename set_auto_base_hook_type<VoidPointer>::type set_auto_base_hook_t;
- typedef typename set_base_hook_type<VoidPointer>::type set_base_hook_t;
- typedef typename set_auto_member_hook_type<VoidPointer>::type set_auto_member_hook_t;
- typedef typename set_member_hook_type<VoidPointer>::type set_member_hook_t;
-
- typedef typename splay_set_auto_base_hook_type<VoidPointer>::type splay_set_auto_base_hook_t;
- typedef typename splay_set_base_hook_type<VoidPointer>::type splay_set_base_hook_t;
- typedef typename splay_set_auto_member_hook_type<VoidPointer>::type splay_set_auto_member_hook_t;
- typedef typename splay_set_member_hook_type<VoidPointer>::type splay_set_member_hook_t;
-
- typedef typename bs_set_base_hook_type<VoidPointer>::type bs_set_base_hook_t;
- typedef typename bs_set_member_hook_type<VoidPointer>::type bs_set_member_hook_t;
-
- typedef typename avl_set_auto_base_hook_type<VoidPointer>::type avl_set_auto_base_hook_t;
- typedef typename avl_set_base_hook_type<VoidPointer>::type avl_set_base_hook_t;
- typedef typename avl_set_auto_member_hook_type<VoidPointer>::type avl_set_auto_member_hook_t;
- typedef typename avl_set_member_hook_type<VoidPointer>::type avl_set_member_hook_t;
-
- typedef typename uset_auto_base_hook_type<VoidPointer>::type unordered_set_auto_base_hook_t;
- typedef typename uset_base_hook_type<VoidPointer>::type unordered_set_base_hook_t;
- typedef typename uset_auto_member_hook_type<VoidPointer>::type unordered_set_auto_member_hook_t;
- typedef typename uset_member_hook_type<VoidPointer>::type unordered_set_member_hook_t;
-
- typedef typename list_auto_base_hook_type<VoidPointer>::type list_auto_base_hook_t;
- typedef typename list_base_hook_type<VoidPointer>::type list_base_hook_t;
- typedef typename list_auto_member_hook_type<VoidPointer>::type list_auto_member_hook_t;
- typedef typename list_member_hook_type<VoidPointer>::type list_member_hook_t;
-
- typedef typename slist_auto_base_hook_type<VoidPointer>::type slist_auto_base_hook_t;
- typedef typename slist_base_hook_type<VoidPointer>::type slist_base_hook_t;
- typedef typename slist_auto_member_hook_type<VoidPointer>::type slist_auto_member_hook_t;
- typedef typename slist_member_hook_type<VoidPointer>::type slist_member_hook_t;
-
- //Set members
- set_member_hook_t set_node_;
- set_auto_member_hook_t set_auto_node_;
-
- //SplaySet members
- splay_set_member_hook_t splay_set_node_;
- splay_set_auto_member_hook_t splay_set_auto_node_;
-
- //ScapegoatSet members
- bs_set_member_hook_t sg_set_node_;
-
- //AvlSet members
- avl_set_member_hook_t avl_set_node_;
- avl_set_auto_member_hook_t avl_set_auto_node_;
-
- //Unordered set members
- unordered_set_member_hook_t unordered_set_node_;
- unordered_set_auto_member_hook_t unordered_set_auto_node_;
-
- //List members
- list_member_hook_t list_node_;
- list_auto_member_hook_t list_auto_node_;
-
- //Slist members
- slist_member_hook_t slist_node_;
- slist_auto_member_hook_t slist_auto_node_;
-
+ typename Hooks::member_hook_type node_;
+ typename Hooks::auto_member_hook_type auto_node_;
int value_;
static const bool constant_time_size = ConstantTimeSize;
@@ -245,130 +50,30 @@
// testvalue is used in std::vector and thus prev and next
// have to be handled appropriately when copied:
-
testvalue & operator= (const testvalue& src)
- {/*
- set_base_hook_t::operator=(src);
- set_auto_base_hook_t::operator=(src);
- this->set_node_ = src.set_node_;
- this->set_auto_node_ = src.set_auto_node_;
-
- splay_set_base_hook_t::operator=(src);
- splay_set_auto_base_hook_t::operator=(src);
- this->splay_set_node_ = src.splay_set_node_;
- this->splay_set_auto_node_ = src.splay_set_auto_node_;
-
- bs_set_base_hook_t::operator=(src);
- this->sg_set_node_ = src.sg_set_node_;
-
- avl_set_base_hook_t::operator=(src);
- avl_set_auto_base_hook_t::operator=(src);
- this->avl_set_node_ = src.avl_set_node_;
- this->avl_set_auto_node_ = src.avl_set_auto_node_;
-
- unordered_set_base_hook_t::operator=(src);
- unordered_set_auto_base_hook_t::operator=(src);
- this->unordered_set_node_ = src.unordered_set_node_;
- this->unordered_set_auto_node_ = src.unordered_set_auto_node_;
-
- list_base_hook_t::operator=(src);
- list_auto_base_hook_t::operator=(src);
- this->list_node_ = src.list_node_;
- this->list_auto_node_ = src.list_auto_node_;
-
- slist_base_hook_t::operator=(src);
- slist_auto_base_hook_t::operator=(src);
- this->slist_node_ = src.slist_node_;
- this->slist_auto_node_ = src.slist_auto_node_;
-*/
+ {
+ Hooks::base_hook_type::operator=(src);
+ Hooks::auto_base_hook_type::operator=(src);
+ this->node_ = src.node_;
+ this->auto_node_ = src.auto_node_;
value_ = src.value_;
return *this;
}
void swap_nodes(testvalue &other)
{
- //Set
- set_base_hook_t::swap_nodes(other);
- set_auto_base_hook_t::swap_nodes(other);
- set_node_.swap_nodes(other.set_node_);
- set_auto_node_.swap_nodes(other.set_auto_node_);
-
- //SplaySet
- splay_set_base_hook_t::swap_nodes(other);
- splay_set_auto_base_hook_t::swap_nodes(other);
- splay_set_node_.swap_nodes(other.splay_set_node_);
- splay_set_auto_node_.swap_nodes(other.splay_set_auto_node_);
-
- //ScapeoatSet
- bs_set_base_hook_t::swap_nodes(other);
- sg_set_node_.swap_nodes(other.sg_set_node_);
-
- //AvlSet
- avl_set_base_hook_t::swap_nodes(other);
- avl_set_auto_base_hook_t::swap_nodes(other);
- avl_set_node_.swap_nodes(other.avl_set_node_);
- avl_set_auto_node_.swap_nodes(other.avl_set_auto_node_);
-
- //Unordered set
- unordered_set_base_hook_t::swap_nodes(other);
- unordered_set_auto_base_hook_t::swap_nodes(other);
- unordered_set_node_.swap_nodes(other.unordered_set_node_);
- unordered_set_auto_node_.swap_nodes(other.unordered_set_auto_node_);
-
- //List
- list_base_hook_t::swap_nodes(other);
- list_auto_base_hook_t::swap_nodes(other);
- list_node_.swap_nodes(other.list_node_);
- list_auto_node_.swap_nodes(other.list_auto_node_);
-
- //Slist
- slist_base_hook_t::swap_nodes(other);
- slist_auto_base_hook_t::swap_nodes(other);
- slist_node_.swap_nodes(other.slist_node_);
- slist_auto_node_.swap_nodes(other.slist_auto_node_);
+ Hooks::base_hook_type::swap_nodes(other);
+ Hooks::auto_base_hook_type::swap_nodes(other);
+ node_.swap_nodes(other.node_);
+ auto_node_.swap_nodes(other.auto_node_);
}
bool is_linked() const
{
- //Set
- return set_base_hook_t::is_linked() ||
- set_auto_base_hook_t::is_linked() ||
- set_node_.is_linked() ||
- set_auto_node_.is_linked() ||
-
- //SplaySet
- splay_set_base_hook_t::is_linked() ||
- splay_set_auto_base_hook_t::is_linked() ||
- splay_set_node_.is_linked() ||
- splay_set_auto_node_.is_linked() ||
-
- //ScapeoatSet
- bs_set_base_hook_t::is_linked() ||
- sg_set_node_.is_linked() ||
-
- //AvlSet
- avl_set_base_hook_t::is_linked() ||
- avl_set_auto_base_hook_t::is_linked() ||
- avl_set_node_.is_linked() ||
- avl_set_auto_node_.is_linked() ||
-
- //Unordered set
- unordered_set_base_hook_t::is_linked() ||
- unordered_set_auto_base_hook_t::is_linked() ||
- unordered_set_node_.is_linked() ||
- unordered_set_auto_node_.is_linked() ||
-
- //List
- list_base_hook_t::is_linked() ||
- list_auto_base_hook_t::is_linked() ||
- list_node_.is_linked() ||
- list_auto_node_.is_linked() ||
-
- //Slist
- slist_base_hook_t::is_linked() ||
- slist_auto_base_hook_t::is_linked() ||
- slist_node_.is_linked() ||
- slist_auto_node_.is_linked();
+ return Hooks::base_hook_type::is_linked() ||
+ Hooks::auto_base_hook_type::is_linked() ||
+ node_.is_linked() ||
+ auto_node_.is_linked();
}
~testvalue()
@@ -402,24 +107,34 @@
{ return other1.value_ != other2; }
};
-template<class VoidPointer, bool ConstantTimeSize>
-std::size_t hash_value(const testvalue<VoidPointer, ConstantTimeSize> &t)
+template<class Hooks, bool ConstantTimeSize>
+std::size_t hash_value(const testvalue<Hooks, ConstantTimeSize> &t)
{
boost::hash<int> hasher;
return hasher(t.value_);
}
-template<class VoidPointer, bool constant_time_size>
+template<class Hooks, bool ConstantTimeSize>
+bool priority_order(const testvalue<Hooks, ConstantTimeSize> &t1, const testvalue<Hooks, ConstantTimeSize> &t2)
+{
+ std::size_t hash1 = hash_value(t1);
+ boost::hash_combine(hash1,&t1);
+ std::size_t hash2 = hash_value(t2);
+ boost::hash_combine(hash2,&t2);
+ return hash1 < hash2;
+}
+
+template<class Hooks, bool constant_time_size>
std::ostream& operator<<
- (std::ostream& s, const testvalue<VoidPointer, constant_time_size>& t)
+ (std::ostream& s, const testvalue<Hooks, constant_time_size>& t)
{ return s << t.value_; }
struct even_odd
{
- template<class VoidPointer, bool constant_time_size>
+ template<class Hooks, bool constant_time_size>
bool operator()
- (const testvalue<VoidPointer, constant_time_size>& v1
- ,const testvalue<VoidPointer, constant_time_size>& v2) const
+ (const testvalue<Hooks, constant_time_size>& v1
+ ,const testvalue<Hooks, constant_time_size>& v2) const
{
if ((v1.value_ & 1) == (v2.value_ & 1))
return v1.value_ < v2.value_;
@@ -430,9 +145,9 @@
struct is_even
{
- template<class VoidPointer, bool constant_time_size>
+ template<class Hooks, bool constant_time_size>
bool operator()
- (const testvalue<VoidPointer, constant_time_size>& v1) const
+ (const testvalue<Hooks, constant_time_size>& v1) const
{ return (v1.value_ & 1) == 0; }
};
Modified: trunk/libs/intrusive/test/list_test.cpp
==============================================================================
--- trunk/libs/intrusive/test/list_test.cpp (original)
+++ trunk/libs/intrusive/test/list_test.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,7 +1,7 @@
/////////////////////////////////////////////////////////////////////////////
//
// (C) Copyright Olaf Krzikalla 2004-2006.
-// (C) Copyright Ion Gaztanaga 2006-2007.
+// (C) Copyright Ion Gaztanaga 2006-2008.
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
@@ -25,6 +25,19 @@
using namespace boost::intrusive;
+class my_tag;
+
+template<class VoidPointer>
+struct hooks
+{
+ typedef list_base_hook<void_pointer<VoidPointer> > base_hook_type;
+ typedef list_base_hook< link_mode<auto_unlink>
+ , void_pointer<VoidPointer>, tag<my_tag> > auto_base_hook_type;
+ typedef list_member_hook<void_pointer<VoidPointer>, tag<my_tag> > member_hook_type;
+ typedef list_member_hook< link_mode<auto_unlink>
+ , void_pointer<VoidPointer> > auto_member_hook_type;
+};
+
template<class ValueTraits>
struct test_list
{
@@ -400,21 +413,21 @@
public:
int operator()()
{
- typedef testvalue<VoidPointer, constant_time_size> value_type;
+ typedef testvalue<hooks<VoidPointer>, constant_time_size> value_type;
std::vector<value_type> data (5);
for (int i = 0; i < 5; ++i)
data[i].value_ = i + 1;
test_list < typename detail::get_base_value_traits
< value_type
- , typename value_type::list_base_hook_t
+ , typename hooks<VoidPointer>::base_hook_type
>::type
>::test_all(data);
test_list < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
- , typename value_type::list_member_hook_t
- , &value_type::list_node_
+ , typename hooks<VoidPointer>::member_hook_type
+ , &value_type::node_
>
>::type
>::test_all(data);
@@ -428,22 +441,22 @@
public:
int operator()()
{
- typedef testvalue<VoidPointer, false> value_type;
+ typedef testvalue<hooks<VoidPointer>, false> value_type;
std::vector<value_type> data (5);
for (int i = 0; i < 5; ++i)
data[i].value_ = i + 1;
test_list < typename detail::get_base_value_traits
< value_type
- , typename value_type::list_base_hook_t
+ , typename hooks<VoidPointer>::base_hook_type
>::type
>::test_all(data);
test_list < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
- , typename value_type::list_member_hook_t
- , &value_type::list_node_
+ , typename hooks<VoidPointer>::member_hook_type
+ , &value_type::node_
>
>::type
>::test_all(data);
@@ -455,15 +468,15 @@
// >::test_all(data);
test_list < typename detail::get_base_value_traits
< value_type
- , typename value_type::list_auto_base_hook_t
+ , typename hooks<VoidPointer>::auto_base_hook_type
>::type
>::test_all(data);
test_list < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
- , typename value_type::list_auto_member_hook_t
- , &value_type::list_auto_node_
+ , typename hooks<VoidPointer>::auto_member_hook_type
+ , &value_type::auto_node_
>
>::type
>::test_all(data);
@@ -488,285 +501,3 @@
return boost::report_errors();
}
#include <boost/intrusive/detail/config_end.hpp>
-
-
-
-
-
-
-
-
-
-
-
-
-
-/*
-#include <cstddef>
-
-
-////////////////////////////////////////////////////
-// Builds an index_tuple<0, 1, 2, ..., Num-1>, that will
-// be used to "unpack" into comma-separated values
-// in a function call.
-////////////////////////////////////////////////////
-
-template<int... Indexes>
-struct index_tuple{};
-
-template<std::size_t Num, typename Tuple = index_tuple<> >
-struct build_number_seq;
-
-template<std::size_t Num, int... Indexes>
-struct build_number_seq<Num, index_tuple<Indexes...> >
- : build_number_seq<Num - 1, index_tuple<Indexes..., sizeof...(Indexes)> >
-{};
-
-template<int... Indexes>
-struct build_number_seq<0, index_tuple<Indexes...> >
-{ typedef index_tuple<Indexes...> type; };
-
-template<class ...Types>
-struct typelist
-{};
-
-template<class T>
-struct invert_typelist;
-
-template<int I, typename Tuple>
-struct typelist_element;
-
-template<int I, typename Head, typename... Tail>
-struct typelist_element<I, typelist<Head, Tail...> >
-{
- typedef typename typelist_element<I-1, typelist<Tail...> >::type type;
-};
-
-template<typename Head, typename... Tail>
-struct typelist_element<0, typelist<Head, Tail...> >
-{
- typedef Head type;
-};
-
-template<int ...Ints, class ...Types>
-typelist<typename typelist_element<(sizeof...(Types) - 1) - Ints, typelist<Types...> >::type...>
- inverted_typelist(index_tuple<Ints...>, typelist<Types...>)
-{
- return typelist<typename typelist_element<(sizeof...(Types) - 1) - Ints, typelist<Types...> >::type...>();
-}
-
-
-template<class Typelist>
-struct sizeof_typelist;
-
-template<class ...Types>
-struct sizeof_typelist< typelist<Types...> >
-{
- static const std::size_t value = sizeof...(Types);
-};
-
-//invert_typelist_impl
-template<class Typelist, class Indexes>
-struct invert_typelist_impl;
-
-
-template<class Typelist, int ...Ints>
-struct invert_typelist_impl< Typelist, index_tuple<Ints...> >
-{
- static const std::size_t last_idx = sizeof_typelist<Typelist>::value - 1;
- typedef typelist
- <typename typelist_element<last_idx - Ints, Typelist>::type...> type;
-};
-
-template<class Typelist, int Int>
-struct invert_typelist_impl< Typelist, index_tuple<Int> >
-{
- typedef Typelist type;
-};
-
-template<class Typelist>
-struct invert_typelist_impl< Typelist, index_tuple<> >
-{
- typedef Typelist type;
-};
-
-//invert_typelist
-template<class Typelist>
-struct invert_typelist;
-
-template<class ...Types>
-struct invert_typelist< typelist<Types...> >
-{
- typedef typelist<Types...> typelist_t;
- typedef typename build_number_seq<sizeof...(Types)>::type indexes_t;
- typedef typename invert_typelist_impl<typelist_t, indexes_t>::type type;
-};
-
-struct none
-{
- template<class Base>
- struct pack : Base
- { };
-};
-
-//!This option setter specifies the type of
-//!a void pointer. This will instruct the hook
-//!to use this type of pointer instead of the
-//!default one
-template<class VoidPointer>
-struct void_pointer
-{
-/// @cond
- template<class Base>
- struct pack : Base
- {
- typedef VoidPointer void_pointer;
- };
-/// @endcond
-};
-
-//!This option setter specifies the type of
-//!the tag of a base hook. A type cannot have two
-//!base hooks of the same type, so a tag can be used
-//!to differentiate two base hooks with otherwise same type
-template<class Tag>
-struct tag
-{
-/// @cond
- template<class Base>
- struct pack : Base
- {
- typedef Tag tag;
- };
-/// @endcond
-};
-
-
-//!This option setter specifies if the hook
-//!should be optimized for size instead of for speed.
-template<bool Enabled>
-struct optimize_size
-{
-/// @cond
- template<class Base>
- struct pack : Base
- {
- static const bool optimize_size = Enabled;
- };
-/// @endcond
-};
-
-//!This option setter specifies if the list container should
-//!use a linear implementation instead of a circular one.
-template<bool Enabled>
-struct linear
-{
-/// @cond
- template<class Base>
- struct pack : Base
- {
- static const bool linear = Enabled;
- };
-/// @endcond
-};
-
-//!This option setter specifies if the list container should
-//!use a linear implementation instead of a circular one.
-template<bool Enabled>
-struct cache_last
-{
-/// @cond
- template<class Base>
- struct pack : Base
- {
- static const bool cache_last = Enabled;
- };
-/// @endcond
-};
-
-
-
-template<class Typelist>
-struct do_pack;
-
-template<>
-struct do_pack<typelist<> >;
-
-template<class Prev>
-struct do_pack<typelist<Prev> >
-{
- typedef Prev type;
-};
-
-template<class Prev, class Last>
-struct do_pack<typelist<Prev, Last> >
-{
- typedef typename Prev::template pack<Last> type;
-};
-
-template<class Prev, class ...Others>
-struct do_pack<typelist<Prev, Others...> >
-{
- typedef typename Prev::template pack
- <typename do_pack<typelist<Others...>>::type> type;
-};
-
-
-template<class ...Options>
-struct pack_options
-{
- typedef typelist<Options...> typelist_t;
- typedef typename invert_typelist<typelist_t>::type inverted_typelist;
- typedef typename do_pack<inverted_typelist>::type type;
-};
-
-struct hook_defaults
- : public pack_options
- < none
- , void_pointer<void*>
- , tag<int>
- , optimize_size<false>
- , linear<false>
- >::type
-{};
-
-
-#include <iostream>
-#include <typeinfo>
-
-struct S
-{};
-
-int main()
-{
- {
- typedef typelist<int, float, double> typelist_t;
- typedef invert_typelist<typelist_t>::type inverted_typelist;
- std::cout << "original: " << typeid(typelist_t).name() << std::endl;
- std::cout << "inverted: " << typeid(inverted_typelist).name() << std::endl;
- }
- {
- typedef typelist<int> typelist_t;
- typedef invert_typelist<typelist_t>::type inverted_typelist;
- std::cout << "original: " << typeid(typelist_t).name() << std::endl;
- std::cout << "inverted: " << typeid(inverted_typelist).name() << std::endl;
- }
- {
- typedef typelist<> typelist_t;
- typedef invert_typelist<typelist_t>::type inverted_typelist;
- std::cout << "original: " << typeid(typelist_t).name() << std::endl;
- std::cout << "inverted: " << typeid(inverted_typelist).name() << std::endl;
- }
- {
- typedef pack_options<S, none>::type options_t;
- std::cout << "options_t " << typeid(options_t).name() << std::endl;
- }
- {
- typedef pack_options<S, none, none>::type options_t;
- std::cout << "options_t " << typeid(options_t).name() << std::endl;
- }
-
- hook_defaults h;
- return 1;
-}
-*/
\ No newline at end of file
Modified: trunk/libs/intrusive/test/make_functions_test.cpp
==============================================================================
--- trunk/libs/intrusive/test/make_functions_test.cpp (original)
+++ trunk/libs/intrusive/test/make_functions_test.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
/////////////////////////////////////////////////////////////////////////////
//
-// (C) Copyright Ion Gaztanaga 2007
+// (C) Copyright Ion Gaztanaga 2007-2008
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
@@ -13,12 +13,22 @@
#include <boost/intrusive/slist.hpp>
#include <boost/intrusive/set.hpp>
#include <boost/intrusive/unordered_set.hpp>
+#include <boost/intrusive/avl_set.hpp>
+#include <boost/intrusive/sg_set.hpp>
+#include <boost/intrusive/splay_set.hpp>
+#include <boost/intrusive/treap_set.hpp>
#include <boost/intrusive/detail/mpl.hpp>
#include "smart_ptr.hpp"
#include <vector>
using namespace boost::intrusive;
+struct my_tag;
+
+typedef make_bs_set_base_hook
+ < void_pointer<smart_ptr<void> >, link_mode<normal_link>
+ , tag<my_tag> >::type TreapHook;
+
class MyClass
: public make_list_base_hook
< void_pointer<smart_ptr<void> >, link_mode<normal_link> >::type
@@ -28,6 +38,13 @@
< void_pointer<smart_ptr<void> >, link_mode<normal_link> >::type
, public make_unordered_set_base_hook
< void_pointer<smart_ptr<void> >, link_mode<normal_link> >::type
+, public make_avl_set_base_hook
+ < void_pointer<smart_ptr<void> >, link_mode<normal_link> >::type
+, public make_splay_set_base_hook
+ < void_pointer<smart_ptr<void> >, link_mode<normal_link> >::type
+, public make_bs_set_base_hook
+ < void_pointer<smart_ptr<void> >, link_mode<normal_link> >::type
+, public TreapHook
{
int int_;
@@ -44,6 +61,9 @@
friend std::size_t hash_value(const MyClass &v)
{ return boost::hash_value(v.int_); }
+
+ friend bool priority_order(const MyClass &l, const MyClass &r)
+ { return l.int_ < r.int_; }
};
//Define a list that will store MyClass using the public base hook
@@ -52,6 +72,12 @@
typedef make_set<MyClass>::type Set;
typedef make_unordered_set<MyClass>::type USet;
+typedef make_avl_set<MyClass>::type AvlSet;
+typedef make_splay_set<MyClass>::type SplaySet;
+typedef make_sg_set<MyClass>::type SgSet;
+typedef make_treap_set<MyClass
+ , base_hook<TreapHook> >::type TreapSet;
+
int main()
{
typedef std::vector<MyClass>::iterator VectIt;
@@ -68,12 +94,21 @@
Set my_set;
USet my_uset(USet::bucket_traits(buckets, 100));
+ AvlSet my_avlset;
+ SplaySet my_splayset;
+ SgSet my_sgset;
+ TreapSet my_treapset;
+
//Now insert them in containers
for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it){
my_list.push_front(*it);
my_slist.push_front(*it);
my_set.insert(*it);
my_uset.insert(*it);
+ my_avlset.insert(*it);
+ my_splayset.insert(*it);
+ my_sgset.insert(*it);
+ my_treapset.insert(*it);
}
//Now test lists
@@ -81,14 +116,27 @@
List::const_iterator list_it(my_list.cbegin());
Slist::const_iterator slist_it(my_slist.cbegin());
Set::const_reverse_iterator set_rit(my_set.crbegin());
+
+ AvlSet::const_reverse_iterator avlset_rit(my_avlset.crbegin());
+ SplaySet::const_reverse_iterator splayset_rit(my_splayset.crbegin());
+ SgSet::const_reverse_iterator sgset_rit(my_sgset.crbegin());
+ TreapSet::const_reverse_iterator treapset_rit(my_treapset.crbegin());
+
VectRit vect_it(values.rbegin()), vect_itend(values.rend());
//Test the objects inserted in the base hook list
- for(; vect_it != vect_itend; ++vect_it, ++list_it, ++slist_it, ++set_rit){
+ for( ; vect_it != vect_itend
+ ; ++vect_it, ++list_it, ++slist_it, ++set_rit
+ , ++avlset_rit, ++splayset_rit, ++sgset_rit, ++treapset_rit
+ ){
if(&*list_it != &*vect_it) return 1;
if(&*slist_it != &*vect_it) return 1;
if(&*set_rit != &*vect_it) return 1;
if(my_uset.find(*set_rit) == my_uset.cend()) return 1;
+ if(&*avlset_rit != &*vect_it) return 1;
+ if(&*splayset_rit != &*vect_it) return 1;
+ if(&*sgset_rit != &*vect_it) return 1;
+ if(&*treapset_rit != &*vect_it) return 1;
}
}
@@ -117,6 +165,24 @@
return 1;
}
+ if(detail::is_same<make_avl_set_base_hook<void_pointer<void*>, link_mode<safe_link> >::type
+ ,make_avl_set_base_hook<>::type
+ >::value == false){
+ return 1;
+ }
+
+ if(detail::is_same<make_bs_set_base_hook<void_pointer<void*>, link_mode<safe_link> >::type
+ ,make_bs_set_base_hook<>::type
+ >::value == false){
+ return 1;
+ }
+
+ if(detail::is_same<make_splay_set_base_hook<void_pointer<void*>, link_mode<safe_link> >::type
+ ,make_splay_set_base_hook<>::type
+ >::value == false){
+ return 1;
+ }
+
//Check defined types and implicitly defined types are unequal
if(detail::is_same<make_list_base_hook<void_pointer<void*>, link_mode<normal_link> >::type
,make_list_base_hook<>::type
@@ -142,6 +208,24 @@
return 1;
}
+ if(detail::is_same<make_avl_set_base_hook<void_pointer<void*>, link_mode<normal_link> >::type
+ ,make_avl_set_base_hook<>::type
+ >::value == true){
+ return 1;
+ }
+
+ if(detail::is_same<make_splay_set_base_hook<void_pointer<void*>, link_mode<normal_link> >::type
+ ,make_splay_set_base_hook<>::type
+ >::value == true){
+ return 1;
+ }
+
+ if(detail::is_same<make_bs_set_base_hook<void_pointer<void*>, link_mode<normal_link> >::type
+ ,make_bs_set_base_hook<>::type
+ >::value == true){
+ return 1;
+ }
+
return 0;
}
Modified: trunk/libs/intrusive/test/multiset_test.cpp
==============================================================================
--- trunk/libs/intrusive/test/multiset_test.cpp (original)
+++ trunk/libs/intrusive/test/multiset_test.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,7 +1,7 @@
/////////////////////////////////////////////////////////////////////////////
//
// (C) Copyright Olaf Krzikalla 2004-2006.
-// (C) Copyright Ion Gaztanaga 2006-2007.
+// (C) Copyright Ion Gaztanaga 2006-2008.
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
@@ -16,6 +16,26 @@
#include "smart_ptr.hpp"
#include "generic_multiset_test.hpp"
+using namespace boost::intrusive;
+
+struct my_tag;
+
+template<class VoidPointer>
+struct hooks
+{
+ typedef set_base_hook
+ <void_pointer<VoidPointer> > base_hook_type;
+ typedef set_base_hook
+ <link_mode<auto_unlink>
+ , void_pointer<VoidPointer>
+ , tag<my_tag>
+ , optimize_size<true> > auto_base_hook_type;
+ typedef set_member_hook<void_pointer
+ <VoidPointer>, optimize_size<true> > member_hook_type;
+ typedef set_member_hook
+ <link_mode<auto_unlink>, void_pointer<VoidPointer> > auto_member_hook_type;
+};
+
template< class ValueType
, class Option1 = boost::intrusive::none
, class Option2 = boost::intrusive::none
@@ -38,19 +58,19 @@
int operator()()
{
using namespace boost::intrusive;
- typedef testvalue<VoidPointer, constant_time_size> value_type;
+ typedef testvalue<hooks<VoidPointer> , constant_time_size> value_type;
test::test_generic_multiset < typename detail::get_base_value_traits
< value_type
- , typename value_type::set_base_hook_t
+ , typename hooks<VoidPointer>::base_hook_type
>::type
, GetContainer
>::test_all();
test::test_generic_multiset < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
- , typename value_type::set_member_hook_t
- , &value_type::set_node_
+ , typename hooks<VoidPointer>::member_hook_type
+ , &value_type::node_
>
>::type
, GetContainer
@@ -66,11 +86,11 @@
int operator()()
{
using namespace boost::intrusive;
- typedef testvalue<VoidPointer, false> value_type;
+ typedef testvalue<hooks<VoidPointer> , false> value_type;
test::test_generic_multiset < typename detail::get_base_value_traits
< value_type
- , typename value_type::set_base_hook_t
+ , typename hooks<VoidPointer>::base_hook_type
>::type
, GetContainer
>::test_all();
@@ -78,8 +98,8 @@
test::test_generic_multiset < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
- , typename value_type::set_member_hook_t
- , &value_type::set_node_
+ , typename hooks<VoidPointer>::member_hook_type
+ , &value_type::node_
>
>::type
, GetContainer
@@ -87,7 +107,7 @@
test::test_generic_multiset < typename detail::get_base_value_traits
< value_type
- , typename value_type::set_auto_base_hook_t
+ , typename hooks<VoidPointer>::auto_base_hook_type
>::type
, GetContainer
>::test_all();
@@ -95,8 +115,8 @@
test::test_generic_multiset < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
- , typename value_type::set_auto_member_hook_t
- , &value_type::set_auto_node_
+ , typename hooks<VoidPointer>::auto_member_hook_type
+ , &value_type::auto_node_
>
>::type
, GetContainer
Modified: trunk/libs/intrusive/test/set_test.cpp
==============================================================================
--- trunk/libs/intrusive/test/set_test.cpp (original)
+++ trunk/libs/intrusive/test/set_test.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,7 +1,7 @@
/////////////////////////////////////////////////////////////////////////////
//
// (C) Copyright Olaf Krzikalla 2004-2006.
-// (C) Copyright Ion Gaztanaga 2006-2007.
+// (C) Copyright Ion Gaztanaga 2006-2008.
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
@@ -16,6 +16,26 @@
#include "smart_ptr.hpp"
#include "generic_set_test.hpp"
+struct my_tag;
+
+using namespace boost::intrusive;
+
+template<class VoidPointer>
+struct hooks
+{
+ typedef set_base_hook
+ <void_pointer<VoidPointer> > base_hook_type;
+ typedef set_base_hook
+ <link_mode<auto_unlink>
+ , void_pointer<VoidPointer>
+ , tag<my_tag>
+ , optimize_size<true> > auto_base_hook_type;
+ typedef set_member_hook<void_pointer
+ <VoidPointer>, optimize_size<true> > member_hook_type;
+ typedef set_member_hook
+ <link_mode<auto_unlink>, void_pointer<VoidPointer> > auto_member_hook_type;
+};
+
template< class ValueType
, class Option1 = boost::intrusive::none
, class Option2 = boost::intrusive::none
@@ -38,19 +58,19 @@
int operator()()
{
using namespace boost::intrusive;
- typedef testvalue<VoidPointer, constant_time_size> value_type;
+ typedef testvalue<hooks<VoidPointer> , constant_time_size> value_type;
test::test_generic_set < typename detail::get_base_value_traits
< value_type
- , typename value_type::set_base_hook_t
+ , typename hooks<VoidPointer>::base_hook_type
>::type
, GetContainer
>::test_all();
test::test_generic_set < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
- , typename value_type::set_member_hook_t
- , &value_type::set_node_
+ , typename hooks<VoidPointer>::member_hook_type
+ , &value_type::node_
>
>::type
, GetContainer
@@ -66,11 +86,11 @@
int operator()()
{
using namespace boost::intrusive;
- typedef testvalue<VoidPointer, false> value_type;
+ typedef testvalue<hooks<VoidPointer> , false> value_type;
test::test_generic_set < typename detail::get_base_value_traits
< value_type
- , typename value_type::set_base_hook_t
+ , typename hooks<VoidPointer>::base_hook_type
>::type
, GetContainer
>::test_all();
@@ -78,8 +98,8 @@
test::test_generic_set < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
- , typename value_type::set_member_hook_t
- , &value_type::set_node_
+ , typename hooks<VoidPointer>::member_hook_type
+ , &value_type::node_
>
>::type
, GetContainer
@@ -87,7 +107,7 @@
test::test_generic_set < typename detail::get_base_value_traits
< value_type
- , typename value_type::set_auto_base_hook_t
+ , typename hooks<VoidPointer>::auto_base_hook_type
>::type
, GetContainer
>::test_all();
@@ -95,8 +115,8 @@
test::test_generic_set < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
- , typename value_type::set_auto_member_hook_t
- , &value_type::set_auto_node_
+ , typename hooks<VoidPointer>::auto_member_hook_type
+ , &value_type::auto_node_
>
>::type
, GetContainer
Modified: trunk/libs/intrusive/test/sg_multiset_test.cpp
==============================================================================
--- trunk/libs/intrusive/test/sg_multiset_test.cpp (original)
+++ trunk/libs/intrusive/test/sg_multiset_test.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,7 +1,7 @@
/////////////////////////////////////////////////////////////////////////////
//
// (C) Copyright Olaf Krzikalla 2004-2006.
-// (C) Copyright Ion Gaztanaga 2006-2007.
+// (C) Copyright Ion Gaztanaga 2006-2008.
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
@@ -36,6 +36,22 @@
}}}
+using namespace boost::intrusive;
+
+struct my_tag;
+
+template<class VoidPointer>
+struct hooks
+{
+ typedef bs_set_base_hook<void_pointer<VoidPointer> > base_hook_type;
+ typedef bs_set_member_hook<void_pointer<VoidPointer> > member_hook_type;
+ typedef member_hook_type auto_member_hook_type;
+ struct auto_base_hook_type
+ : bs_set_base_hook<void_pointer<VoidPointer>, tag<my_tag> >
+ {};
+};
+
+
template< class ValueType
, class Option1 = boost::intrusive::none
, class Option2 = boost::intrusive::none
@@ -74,34 +90,34 @@
int operator()()
{
using namespace boost::intrusive;
- typedef testvalue<VoidPointer, true> value_type;
+ typedef testvalue<hooks<VoidPointer> , true> value_type;
test::test_generic_multiset < typename detail::get_base_value_traits
< value_type
- , typename value_type::bs_set_base_hook_t
+ , typename hooks<VoidPointer>::base_hook_type
>::type
, GetContainer
>::test_all();
test::test_generic_multiset < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
- , typename value_type::bs_set_member_hook_t
- , &value_type::sg_set_node_
+ , typename hooks<VoidPointer>::member_hook_type
+ , &value_type::node_
>
>::type
, GetContainer
>::test_all();
test::test_generic_multiset < typename detail::get_base_value_traits
< value_type
- , typename value_type::bs_set_base_hook_t
+ , typename hooks<VoidPointer>::base_hook_type
>::type
, GetContainerFixedAlpha
>::test_all();
test::test_generic_multiset < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
- , typename value_type::bs_set_member_hook_t
- , &value_type::sg_set_node_
+ , typename hooks<VoidPointer>::member_hook_type
+ , &value_type::node_
>
>::type
, GetContainerFixedAlpha
Modified: trunk/libs/intrusive/test/sg_set_test.cpp
==============================================================================
--- trunk/libs/intrusive/test/sg_set_test.cpp (original)
+++ trunk/libs/intrusive/test/sg_set_test.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -35,6 +35,22 @@
}}}
+
+using namespace boost::intrusive;
+
+struct my_tag;
+
+template<class VoidPointer>
+struct hooks
+{
+ typedef bs_set_base_hook<void_pointer<VoidPointer> > base_hook_type;
+ typedef bs_set_member_hook<void_pointer<VoidPointer> > member_hook_type;
+ typedef member_hook_type auto_member_hook_type;
+ struct auto_base_hook_type
+ : bs_set_base_hook<void_pointer<VoidPointer>, tag<my_tag> >
+ {};
+};
+
template< class ValueType
, class Option1 = boost::intrusive::none
, class Option2 = boost::intrusive::none
@@ -73,19 +89,19 @@
int operator()()
{
using namespace boost::intrusive;
- typedef testvalue<VoidPointer, true> value_type;
+ typedef testvalue<hooks<VoidPointer> , true> value_type;
test::test_generic_set < typename detail::get_base_value_traits
< value_type
- , typename value_type::bs_set_base_hook_t
+ , typename hooks<VoidPointer>::base_hook_type
>::type
, GetContainer
>::test_all();
test::test_generic_set < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
- , typename value_type::bs_set_member_hook_t
- , &value_type::sg_set_node_
+ , typename hooks<VoidPointer>::member_hook_type
+ , &value_type::node_
>
>::type
, GetContainer
@@ -93,15 +109,15 @@
test::test_generic_set < typename detail::get_base_value_traits
< value_type
- , typename value_type::bs_set_base_hook_t
+ , typename hooks<VoidPointer>::base_hook_type
>::type
, GetContainerFixedAlpha
>::test_all();
test::test_generic_set < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
- , typename value_type::bs_set_member_hook_t
- , &value_type::sg_set_node_
+ , typename hooks<VoidPointer>::member_hook_type
+ , &value_type::node_
>
>::type
, GetContainerFixedAlpha
Modified: trunk/libs/intrusive/test/slist_test.cpp
==============================================================================
--- trunk/libs/intrusive/test/slist_test.cpp (original)
+++ trunk/libs/intrusive/test/slist_test.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,7 +1,7 @@
/////////////////////////////////////////////////////////////////////////////
//
// (C) Copyright Olaf Krzikalla 2004-2006.
-// (C) Copyright Ion Gaztanaga 2006-2007.
+// (C) Copyright Ion Gaztanaga 2006-2008.
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
@@ -24,6 +24,19 @@
using namespace boost::intrusive;
+struct my_tag;
+
+template<class VoidPointer>
+struct hooks
+{
+ typedef slist_base_hook<void_pointer<VoidPointer> > base_hook_type;
+ typedef slist_base_hook< link_mode<auto_unlink>
+ , void_pointer<VoidPointer>, tag<my_tag> > auto_base_hook_type;
+ typedef slist_member_hook<void_pointer<VoidPointer>, tag<my_tag> > member_hook_type;
+ typedef slist_member_hook< link_mode<auto_unlink>
+ , void_pointer<VoidPointer> > auto_member_hook_type;
+};
+
template<class ValueTraits, bool Linear, bool CacheLast>
struct test_slist
{
@@ -491,14 +504,14 @@
public:
int operator()()
{
- typedef testvalue<VoidPointer, constant_time_size> value_type;
+ typedef testvalue<hooks<VoidPointer> , constant_time_size> value_type;
std::vector<value_type> data (5);
for (int i = 0; i < 5; ++i)
data[i].value_ = i + 1;
test_slist < typename detail::get_base_value_traits
< value_type
- , typename value_type::slist_base_hook_t
+ , typename hooks<VoidPointer>::base_hook_type
>::type
, false
, false
@@ -506,8 +519,8 @@
test_slist < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
- , typename value_type::slist_member_hook_t
- , &value_type::slist_node_
+ , typename hooks<VoidPointer>::member_hook_type
+ , &value_type::node_
>
>::type
, false
@@ -517,7 +530,7 @@
//Now linear slists
test_slist < typename detail::get_base_value_traits
< value_type
- , typename value_type::slist_base_hook_t
+ , typename hooks<VoidPointer>::base_hook_type
>::type
, true
, false
@@ -526,8 +539,8 @@
test_slist < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
- , typename value_type::slist_member_hook_t
- , &value_type::slist_node_
+ , typename hooks<VoidPointer>::member_hook_type
+ , &value_type::node_
>
>::type
, true
@@ -537,7 +550,7 @@
//Now the same but caching the last node
test_slist < typename detail::get_base_value_traits
< value_type
- , typename value_type::slist_base_hook_t
+ , typename hooks<VoidPointer>::base_hook_type
>::type
, false
, true
@@ -545,8 +558,8 @@
test_slist < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
- , typename value_type::slist_member_hook_t
- , &value_type::slist_node_
+ , typename hooks<VoidPointer>::member_hook_type
+ , &value_type::node_
>
>::type
, false
@@ -556,7 +569,7 @@
//Now linear slists
test_slist < typename detail::get_base_value_traits
< value_type
- , typename value_type::slist_base_hook_t
+ , typename hooks<VoidPointer>::base_hook_type
>::type
, true
, true
@@ -565,8 +578,8 @@
test_slist < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
- , typename value_type::slist_member_hook_t
- , &value_type::slist_node_
+ , typename hooks<VoidPointer>::member_hook_type
+ , &value_type::node_
>
>::type
, true
@@ -582,14 +595,14 @@
public:
int operator()()
{
- typedef testvalue<VoidPointer, false> value_type;
+ typedef testvalue<hooks<VoidPointer> , false> value_type;
std::vector<value_type> data (5);
for (int i = 0; i < 5; ++i)
data[i].value_ = i + 1;
test_slist < typename detail::get_base_value_traits
< value_type
- , typename value_type::slist_base_hook_t
+ , typename hooks<VoidPointer>::base_hook_type
>::type
, false
, false
@@ -598,8 +611,8 @@
test_slist < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
- , typename value_type::slist_member_hook_t
- , &value_type::slist_node_
+ , typename hooks<VoidPointer>::member_hook_type
+ , &value_type::node_
>
>::type
, false
@@ -608,7 +621,7 @@
test_slist < typename detail::get_base_value_traits
< value_type
- , typename value_type::slist_auto_base_hook_t
+ , typename hooks<VoidPointer>::auto_base_hook_type
>::type
, false
, false
@@ -617,8 +630,8 @@
test_slist < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
- , typename value_type::slist_auto_member_hook_t
- , &value_type::slist_auto_node_
+ , typename hooks<VoidPointer>::auto_member_hook_type
+ , &value_type::auto_node_
>
>::type
, false
@@ -627,7 +640,7 @@
test_slist < typename detail::get_base_value_traits
< value_type
- , typename value_type::slist_base_hook_t
+ , typename hooks<VoidPointer>::base_hook_type
>::type
, true
, false
@@ -636,8 +649,8 @@
test_slist < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
- , typename value_type::slist_member_hook_t
- , &value_type::slist_node_
+ , typename hooks<VoidPointer>::member_hook_type
+ , &value_type::node_
>
>::type
, true
@@ -647,7 +660,7 @@
//Now cache last
test_slist < typename detail::get_base_value_traits
< value_type
- , typename value_type::slist_base_hook_t
+ , typename hooks<VoidPointer>::base_hook_type
>::type
, false
, true
@@ -656,8 +669,8 @@
test_slist < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
- , typename value_type::slist_member_hook_t
- , &value_type::slist_node_
+ , typename hooks<VoidPointer>::member_hook_type
+ , &value_type::node_
>
>::type
, false
@@ -666,7 +679,7 @@
test_slist < typename detail::get_base_value_traits
< value_type
- , typename value_type::slist_base_hook_t
+ , typename hooks<VoidPointer>::base_hook_type
>::type
, true
, true
@@ -675,8 +688,8 @@
test_slist < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
- , typename value_type::slist_member_hook_t
- , &value_type::slist_node_
+ , typename hooks<VoidPointer>::member_hook_type
+ , &value_type::node_
>
>::type
, true
Modified: trunk/libs/intrusive/test/splay_multiset_test.cpp
==============================================================================
--- trunk/libs/intrusive/test/splay_multiset_test.cpp (original)
+++ trunk/libs/intrusive/test/splay_multiset_test.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,7 +1,7 @@
/////////////////////////////////////////////////////////////////////////////
//
// (C) Copyright Olaf Krzikalla 2004-2006.
-// (C) Copyright Ion Gaztanaga 2006-2007.
+// (C) Copyright Ion Gaztanaga 2006-2008.
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
@@ -70,6 +70,24 @@
}}}
+using namespace boost::intrusive;
+
+struct my_tag;
+
+template<class VoidPointer>
+struct hooks
+{
+ typedef splay_set_base_hook<void_pointer<VoidPointer> > base_hook_type;
+ typedef splay_set_base_hook
+ < link_mode<auto_unlink>
+ , void_pointer<VoidPointer>
+ , tag<my_tag> > auto_base_hook_type;
+ typedef splay_set_member_hook<void_pointer<VoidPointer> > member_hook_type;
+ typedef splay_set_member_hook
+ < link_mode<auto_unlink>
+ , void_pointer<VoidPointer> > auto_member_hook_type;
+};
+
template< class ValueType
, class Option1 = boost::intrusive::none
, class Option2 = boost::intrusive::none
@@ -92,19 +110,19 @@
int operator()()
{
using namespace boost::intrusive;
- typedef testvalue<VoidPointer, constant_time_size> value_type;
+ typedef testvalue<hooks<VoidPointer> , constant_time_size> value_type;
test::test_generic_multiset < typename detail::get_base_value_traits
< value_type
- , typename value_type::splay_set_base_hook_t
+ , typename hooks<VoidPointer>::base_hook_type
>::type
, GetContainer
>::test_all();
test::test_generic_multiset < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
- , typename value_type::splay_set_member_hook_t
- , &value_type::splay_set_node_
+ , typename hooks<VoidPointer>::member_hook_type
+ , &value_type::node_
>
>::type
, GetContainer
@@ -120,11 +138,11 @@
int operator()()
{
using namespace boost::intrusive;
- typedef testvalue<VoidPointer, false> value_type;
+ typedef testvalue<hooks<VoidPointer> , false> value_type;
test::test_generic_multiset < typename detail::get_base_value_traits
< value_type
- , typename value_type::splay_set_base_hook_t
+ , typename hooks<VoidPointer>::base_hook_type
>::type
, GetContainer
>::test_all();
@@ -132,8 +150,8 @@
test::test_generic_multiset < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
- , typename value_type::splay_set_member_hook_t
- , &value_type::splay_set_node_
+ , typename hooks<VoidPointer>::member_hook_type
+ , &value_type::node_
>
>::type
, GetContainer
@@ -141,7 +159,7 @@
test::test_generic_multiset < typename detail::get_base_value_traits
< value_type
- , typename value_type::splay_set_auto_base_hook_t
+ , typename hooks<VoidPointer>::auto_base_hook_type
>::type
, GetContainer
>::test_all();
@@ -149,8 +167,8 @@
test::test_generic_multiset < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
- , typename value_type::splay_set_auto_member_hook_t
- , &value_type::splay_set_auto_node_
+ , typename hooks<VoidPointer>::auto_member_hook_type
+ , &value_type::auto_node_
>
>::type
, GetContainer
Modified: trunk/libs/intrusive/test/splay_set_test.cpp
==============================================================================
--- trunk/libs/intrusive/test/splay_set_test.cpp (original)
+++ trunk/libs/intrusive/test/splay_set_test.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -67,6 +67,24 @@
}}}
+using namespace boost::intrusive;
+
+struct my_tag;
+
+template<class VoidPointer>
+struct hooks
+{
+ typedef splay_set_base_hook<void_pointer<VoidPointer> > base_hook_type;
+ typedef splay_set_base_hook
+ < link_mode<auto_unlink>
+ , void_pointer<VoidPointer>
+ , tag<my_tag> > auto_base_hook_type;
+ typedef splay_set_member_hook<void_pointer<VoidPointer> > member_hook_type;
+ typedef splay_set_member_hook
+ < link_mode<auto_unlink>
+ , void_pointer<VoidPointer> > auto_member_hook_type;
+};
+
template< class ValueType
, class Option1 = boost::intrusive::none
, class Option2 = boost::intrusive::none
@@ -89,19 +107,19 @@
int operator()()
{
using namespace boost::intrusive;
- typedef testvalue<VoidPointer, constant_time_size> value_type;
+ typedef testvalue<hooks<VoidPointer> , constant_time_size> value_type;
test::test_generic_set < typename detail::get_base_value_traits
< value_type
- , typename value_type::splay_set_base_hook_t
+ , typename hooks<VoidPointer>::base_hook_type
>::type
, GetContainer
>::test_all();
test::test_generic_set < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
- , typename value_type::splay_set_member_hook_t
- , &value_type::splay_set_node_
+ , typename hooks<VoidPointer>::member_hook_type
+ , &value_type::node_
>
>::type
, GetContainer
@@ -117,11 +135,11 @@
int operator()()
{
using namespace boost::intrusive;
- typedef testvalue<VoidPointer, false> value_type;
+ typedef testvalue<hooks<VoidPointer> , false> value_type;
test::test_generic_set < typename detail::get_base_value_traits
< value_type
- , typename value_type::splay_set_base_hook_t
+ , typename hooks<VoidPointer>::base_hook_type
>::type
, GetContainer
>::test_all();
@@ -129,8 +147,8 @@
test::test_generic_set < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
- , typename value_type::splay_set_member_hook_t
- , &value_type::splay_set_node_
+ , typename hooks<VoidPointer>::member_hook_type
+ , &value_type::node_
>
>::type
, GetContainer
@@ -138,7 +156,7 @@
test::test_generic_set < typename detail::get_base_value_traits
< value_type
- , typename value_type::splay_set_auto_base_hook_t
+ , typename hooks<VoidPointer>::auto_base_hook_type
>::type
, GetContainer
>::test_all();
@@ -146,8 +164,8 @@
test::test_generic_set < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
- , typename value_type::splay_set_auto_member_hook_t
- , &value_type::splay_set_auto_node_
+ , typename hooks<VoidPointer>::auto_member_hook_type
+ , &value_type::auto_node_
>
>::type
, GetContainer
Modified: trunk/libs/intrusive/test/stateful_value_traits_test.cpp
==============================================================================
--- trunk/libs/intrusive/test/stateful_value_traits_test.cpp (original)
+++ trunk/libs/intrusive/test/stateful_value_traits_test.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
/////////////////////////////////////////////////////////////////////////////
//
-// (C) Copyright Ion Gaztanaga 2007
+// (C) Copyright Ion Gaztanaga 2007-2008
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
Modified: trunk/libs/intrusive/test/test_container.hpp
==============================================================================
--- trunk/libs/intrusive/test/test_container.hpp (original)
+++ trunk/libs/intrusive/test/test_container.hpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
/////////////////////////////////////////////////////////////////////////////
//
-// (C) Copyright Ion Gaztanaga 2007
+// (C) Copyright Ion Gaztanaga 2007-2008
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
Modified: trunk/libs/intrusive/test/test_macros.hpp
==============================================================================
--- trunk/libs/intrusive/test/test_macros.hpp (original)
+++ trunk/libs/intrusive/test/test_macros.hpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
/////////////////////////////////////////////////////////////////////////////
//
-// (C) Copyright Ion Gaztanaga 2006-2007
+// (C) Copyright Ion Gaztanaga 2006-2008
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
Added: trunk/libs/intrusive/test/treap_multiset_test.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/intrusive/test/treap_multiset_test.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -0,0 +1,135 @@
+/////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Olaf Krzikalla 2004-2006.
+// (C) Copyright Ion Gaztanaga 2006-2008.
+//
+// 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/detail/config_begin.hpp>
+#include <boost/intrusive/treap_set.hpp>
+#include "itestvalue.hpp"
+#include "smart_ptr.hpp"
+#include "generic_multiset_test.hpp"
+
+using namespace boost::intrusive;
+
+struct my_tag;
+
+template<class VoidPointer>
+struct hooks
+{
+ typedef bs_set_base_hook<void_pointer<VoidPointer> > base_hook_type;
+ typedef bs_set_base_hook
+ < void_pointer<VoidPointer>
+ , tag<my_tag> > auto_base_hook_type;
+ typedef bs_set_member_hook
+ < void_pointer<VoidPointer> > member_hook_type;
+ typedef bs_set_member_hook
+ < void_pointer<VoidPointer> > auto_member_hook_type;
+};
+
+template< class ValueType
+ , class Option1 = boost::intrusive::none
+ , class Option2 = boost::intrusive::none
+ , class Option3 = boost::intrusive::none
+ >
+struct GetContainer
+{
+ typedef boost::intrusive::treap_multiset
+ < ValueType
+ , Option1
+ , Option2
+ , Option3
+ > type;
+};
+
+template<class VoidPointer, bool constant_time_size>
+class test_main_template
+{
+ public:
+ int operator()()
+ {
+ using namespace boost::intrusive;
+ typedef testvalue<hooks<VoidPointer> , constant_time_size> value_type;
+
+ test::test_generic_multiset < typename detail::get_base_value_traits
+ < value_type
+ , typename hooks<VoidPointer>::base_hook_type
+ >::type
+ , GetContainer
+ >::test_all();
+ test::test_generic_multiset < typename detail::get_member_value_traits
+ < value_type
+ , member_hook< value_type
+ , typename hooks<VoidPointer>::member_hook_type
+ , &value_type::node_
+ >
+ >::type
+ , GetContainer
+ >::test_all();
+ return 0;
+ }
+};
+
+template<class VoidPointer>
+class test_main_template<VoidPointer, false>
+{
+ public:
+ int operator()()
+ {
+ using namespace boost::intrusive;
+ typedef testvalue<hooks<VoidPointer> , false> value_type;
+
+ test::test_generic_multiset < typename detail::get_base_value_traits
+ < value_type
+ , typename hooks<VoidPointer>::base_hook_type
+ >::type
+ , GetContainer
+ >::test_all();
+
+ test::test_generic_multiset < typename detail::get_member_value_traits
+ < value_type
+ , member_hook< value_type
+ , typename hooks<VoidPointer>::member_hook_type
+ , &value_type::node_
+ >
+ >::type
+ , GetContainer
+ >::test_all();
+
+ test::test_generic_multiset < typename detail::get_base_value_traits
+ < value_type
+ , typename hooks<VoidPointer>::auto_base_hook_type
+ >::type
+ , GetContainer
+ >::test_all();
+
+ test::test_generic_multiset < typename detail::get_member_value_traits
+ < value_type
+ , member_hook< value_type
+ , typename hooks<VoidPointer>::auto_member_hook_type
+ , &value_type::auto_node_
+ >
+ >::type
+ , GetContainer
+ >::test_all();
+ return 0;
+ }
+};
+
+int main( int, char* [] )
+{
+ test_main_template<void*, false>()();
+ test_main_template<boost::intrusive::smart_ptr<void>, false>()();
+ test_main_template<void*, true>()();
+ test_main_template<boost::intrusive::smart_ptr<void>, true>()();
+ return boost::report_errors();
+}
+
+#include <boost/intrusive/detail/config_end.hpp>
Added: trunk/libs/intrusive/test/treap_set_test.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/intrusive/test/treap_set_test.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -0,0 +1,134 @@
+/////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2006-2008.
+//
+// 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/detail/config_begin.hpp>
+#include <boost/intrusive/treap_set.hpp>
+#include "itestvalue.hpp"
+#include "smart_ptr.hpp"
+#include "generic_set_test.hpp"
+
+using namespace boost::intrusive;
+
+struct my_tag;
+
+template<class VoidPointer>
+struct hooks
+{
+ typedef bs_set_base_hook<void_pointer<VoidPointer> > base_hook_type;
+ typedef bs_set_base_hook
+ < void_pointer<VoidPointer>
+ , tag<my_tag> > auto_base_hook_type;
+ typedef bs_set_member_hook
+ < void_pointer<VoidPointer> > member_hook_type;
+ typedef bs_set_member_hook
+ < void_pointer<VoidPointer> > auto_member_hook_type;
+};
+
+template< class ValueType
+ , class Option1 = boost::intrusive::none
+ , class Option2 = boost::intrusive::none
+ , class Option3 = boost::intrusive::none
+ >
+struct GetContainer
+{
+ typedef boost::intrusive::treap_set
+ < ValueType
+ , Option1
+ , Option2
+ , Option3
+ > type;
+};
+
+template<class VoidPointer, bool constant_time_size>
+class test_main_template
+{
+ public:
+ int operator()()
+ {
+ using namespace boost::intrusive;
+ typedef testvalue<hooks<VoidPointer> , constant_time_size> value_type;
+
+ test::test_generic_set < typename detail::get_base_value_traits
+ < value_type
+ , typename hooks<VoidPointer>::base_hook_type
+ >::type
+ , GetContainer
+ >::test_all();
+ test::test_generic_set < typename detail::get_member_value_traits
+ < value_type
+ , member_hook< value_type
+ , typename hooks<VoidPointer>::member_hook_type
+ , &value_type::node_
+ >
+ >::type
+ , GetContainer
+ >::test_all();
+ return 0;
+ }
+};
+
+template<class VoidPointer>
+class test_main_template<VoidPointer, false>
+{
+ public:
+ int operator()()
+ {
+ using namespace boost::intrusive;
+ typedef testvalue<hooks<VoidPointer> , false> value_type;
+
+ test::test_generic_set < typename detail::get_base_value_traits
+ < value_type
+ , typename hooks<VoidPointer>::base_hook_type
+ >::type
+ , GetContainer
+ >::test_all();
+
+ test::test_generic_set < typename detail::get_member_value_traits
+ < value_type
+ , member_hook< value_type
+ , typename hooks<VoidPointer>::member_hook_type
+ , &value_type::node_
+ >
+ >::type
+ , GetContainer
+ >::test_all();
+
+ test::test_generic_set < typename detail::get_base_value_traits
+ < value_type
+ , typename hooks<VoidPointer>::auto_base_hook_type
+ >::type
+ , GetContainer
+ >::test_all();
+
+ test::test_generic_set < typename detail::get_member_value_traits
+ < value_type
+ , member_hook< value_type
+ , typename hooks<VoidPointer>::auto_member_hook_type
+ , &value_type::auto_node_
+ >
+ >::type
+ , GetContainer
+ >::test_all();
+
+ return 0;
+ }
+};
+
+int main( int, char* [] )
+{
+ test_main_template<void*, false>()();
+ test_main_template<boost::intrusive::smart_ptr<void>, false>()();
+ test_main_template<void*, true>()();
+ test_main_template<boost::intrusive::smart_ptr<void>, true>()();
+ return boost::report_errors();
+}
+
+#include <boost/intrusive/detail/config_end.hpp>
Modified: trunk/libs/intrusive/test/unordered_multiset_test.cpp
==============================================================================
--- trunk/libs/intrusive/test/unordered_multiset_test.cpp (original)
+++ trunk/libs/intrusive/test/unordered_multiset_test.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,7 +1,7 @@
/////////////////////////////////////////////////////////////////////////////
//
// (C) Copyright Olaf Krzikalla 2004-2006.
-// (C) Copyright Ion Gaztanaga 2006-2007.
+// (C) Copyright Ion Gaztanaga 2006-2008.
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
@@ -25,6 +25,30 @@
using namespace boost::intrusive;
+struct my_tag;
+
+template<class VoidPointer>
+struct hooks
+{
+ typedef unordered_set_base_hook<void_pointer<VoidPointer> > base_hook_type;
+ typedef unordered_set_base_hook
+ < link_mode<auto_unlink>
+ , void_pointer<VoidPointer>
+ , tag<my_tag>
+ , store_hash<true>
+ > auto_base_hook_type;
+
+ typedef unordered_set_member_hook
+ < void_pointer<VoidPointer>
+ , optimize_multikey<true>
+ > member_hook_type;
+ typedef unordered_set_member_hook
+ < link_mode<auto_unlink>, void_pointer<VoidPointer>
+ , store_hash<true>
+ , optimize_multikey<true>
+ > auto_member_hook_type;
+};
+
static const std::size_t BucketSize = 8;
template<class ValueTraits, bool CacheBegin, bool CompareHash, bool Incremental>
@@ -669,15 +693,15 @@
public:
int operator()()
{
- typedef testvalue<VoidPointer, constant_time_size> value_type;
+ typedef testvalue<hooks<VoidPointer> , constant_time_size> value_type;
static const int random_init[6] = { 3, 2, 4, 1, 5, 2 };
- std::vector<testvalue<VoidPointer, constant_time_size> > data (6);
+ std::vector<testvalue<hooks<VoidPointer> , constant_time_size> > data (6);
for (int i = 0; i < 6; ++i)
data[i].value_ = random_init[i];
test_unordered_multiset < typename detail::get_base_value_traits
< value_type
- , typename value_type::unordered_set_base_hook_t
+ , typename hooks<VoidPointer>::base_hook_type
>::type
, true
, false
@@ -687,8 +711,8 @@
test_unordered_multiset < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
- , typename value_type::unordered_set_member_hook_t
- , &value_type::unordered_set_node_
+ , typename hooks<VoidPointer>::member_hook_type
+ , &value_type::node_
>
>::type
, false
@@ -706,15 +730,15 @@
public:
int operator()()
{
- typedef testvalue<VoidPointer, false> value_type;
+ typedef testvalue<hooks<VoidPointer> , false> value_type;
static const int random_init[6] = { 3, 2, 4, 1, 5, 2 };
- std::vector<testvalue<VoidPointer, false> > data (6);
+ std::vector<testvalue<hooks<VoidPointer> , false> > data (6);
for (int i = 0; i < 6; ++i)
data[i].value_ = random_init[i];
test_unordered_multiset < typename detail::get_base_value_traits
< value_type
- , typename value_type::unordered_set_base_hook_t
+ , typename hooks<VoidPointer>::base_hook_type
>::type
, true
, false
@@ -724,8 +748,8 @@
test_unordered_multiset < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
- , typename value_type::unordered_set_member_hook_t
- , &value_type::unordered_set_node_
+ , typename hooks<VoidPointer>::member_hook_type
+ , &value_type::node_
>
>::type
, false
@@ -735,7 +759,7 @@
test_unordered_multiset < typename detail::get_base_value_traits
< value_type
- , typename value_type::unordered_set_auto_base_hook_t
+ , typename hooks<VoidPointer>::auto_base_hook_type
>::type
, true
, true
@@ -745,8 +769,8 @@
test_unordered_multiset < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
- , typename value_type::unordered_set_auto_member_hook_t
- , &value_type::unordered_set_auto_node_
+ , typename hooks<VoidPointer>::auto_member_hook_type
+ , &value_type::auto_node_
>
>::type
, false
Modified: trunk/libs/intrusive/test/unordered_set_test.cpp
==============================================================================
--- trunk/libs/intrusive/test/unordered_set_test.cpp (original)
+++ trunk/libs/intrusive/test/unordered_set_test.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,7 +1,7 @@
/////////////////////////////////////////////////////////////////////////////
//
// (C) Copyright Olaf Krzikalla 2004-2006.
-// (C) Copyright Ion Gaztanaga 2006-2007.
+// (C) Copyright Ion Gaztanaga 2006-2008.
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
@@ -24,6 +24,30 @@
using namespace boost::intrusive;
+struct my_tag;
+
+template<class VoidPointer>
+struct hooks
+{
+ typedef unordered_set_base_hook<void_pointer<VoidPointer> > base_hook_type;
+ typedef unordered_set_base_hook
+ < link_mode<auto_unlink>
+ , void_pointer<VoidPointer>
+ , tag<my_tag>
+ , store_hash<true>
+ > auto_base_hook_type;
+
+ typedef unordered_set_member_hook
+ < void_pointer<VoidPointer>
+ , optimize_multikey<true>
+ > member_hook_type;
+ typedef unordered_set_member_hook
+ < link_mode<auto_unlink>, void_pointer<VoidPointer>
+ , store_hash<true>
+ , optimize_multikey<true>
+ > auto_member_hook_type;
+};
+
static const std::size_t BucketSize = 8;
template<class ValueTraits, bool CacheBegin, bool CompareHash, bool Incremental>
@@ -532,15 +556,15 @@
public:
int operator()()
{
- typedef testvalue<VoidPointer, constant_time_size> value_type;
+ typedef testvalue<hooks<VoidPointer> , constant_time_size> value_type;
static const int random_init[6] = { 3, 2, 4, 1, 5, 2 };
- std::vector<testvalue<VoidPointer, constant_time_size> > data (6);
+ std::vector<testvalue<hooks<VoidPointer> , constant_time_size> > data (6);
for (int i = 0; i < 6; ++i)
data[i].value_ = random_init[i];
test_unordered_set < typename detail::get_base_value_traits
< value_type
- , typename value_type::unordered_set_base_hook_t
+ , typename hooks<VoidPointer>::base_hook_type
>::type
, true
, false
@@ -549,8 +573,8 @@
test_unordered_set < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
- , typename value_type::unordered_set_member_hook_t
- , &value_type::unordered_set_node_
+ , typename hooks<VoidPointer>::member_hook_type
+ , &value_type::node_
>
>::type
, false
@@ -568,15 +592,15 @@
public:
int operator()()
{
- typedef testvalue<VoidPointer, false> value_type;
+ typedef testvalue<hooks<VoidPointer> , false> value_type;
static const int random_init[6] = { 3, 2, 4, 1, 5, 2 };
- std::vector<testvalue<VoidPointer, false> > data (6);
+ std::vector<testvalue<hooks<VoidPointer> , false> > data (6);
for (int i = 0; i < 6; ++i)
data[i].value_ = random_init[i];
test_unordered_set < typename detail::get_base_value_traits
< value_type
- , typename value_type::unordered_set_base_hook_t
+ , typename hooks<VoidPointer>::base_hook_type
>::type
, true
, false
@@ -586,8 +610,8 @@
test_unordered_set < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
- , typename value_type::unordered_set_member_hook_t
- , &value_type::unordered_set_node_
+ , typename hooks<VoidPointer>::member_hook_type
+ , &value_type::node_
>
>::type
, false
@@ -597,7 +621,7 @@
test_unordered_set < typename detail::get_base_value_traits
< value_type
- , typename value_type::unordered_set_auto_base_hook_t
+ , typename hooks<VoidPointer>::auto_base_hook_type
>::type
, true
, true
@@ -607,8 +631,8 @@
test_unordered_set < typename detail::get_member_value_traits
< value_type
, member_hook< value_type
- , typename value_type::unordered_set_auto_member_hook_t
- , &value_type::unordered_set_auto_node_
+ , typename hooks<VoidPointer>::auto_member_hook_type
+ , &value_type::auto_node_
>
>::type
, false
Modified: trunk/libs/intrusive/test/virtual_base_test.cpp
==============================================================================
--- trunk/libs/intrusive/test/virtual_base_test.cpp (original)
+++ trunk/libs/intrusive/test/virtual_base_test.cpp 2008-12-13 08:49:31 EST (Sat, 13 Dec 2008)
@@ -1,6 +1,6 @@
/////////////////////////////////////////////////////////////////////////////
//
-// (C) Copyright Ion Gaztanaga 2007
+// (C) Copyright Ion Gaztanaga 2007-2008
//
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at