|
|
Boost-Commit : |
From: igaztanaga_at_[hidden]
Date: 2007-10-30 03:02:12
Author: igaztanaga
Date: 2007-10-30 03:02:10 EDT (Tue, 30 Oct 2007)
New Revision: 40598
URL: http://svn.boost.org/trac/boost/changeset/40598
Log:
Added avl trees
Added:
trunk/libs/intrusive/example/doc_avl_set.cpp (contents, props changed)
trunk/libs/intrusive/example/doc_avltree_algorithms.cpp (contents, props changed)
trunk/libs/intrusive/example/doc_splaytree_algorithms.cpp (contents, props changed)
trunk/libs/intrusive/proj/vc7ide/avl_multiset/
trunk/libs/intrusive/proj/vc7ide/avl_multiset/avl_multiset.vcproj (contents, props changed)
trunk/libs/intrusive/proj/vc7ide/avl_set/
trunk/libs/intrusive/proj/vc7ide/avl_set/avl_set.vcproj (contents, props changed)
trunk/libs/intrusive/test/avl_multiset_test.cpp (contents, props changed)
trunk/libs/intrusive/test/avl_set_test.cpp (contents, props changed)
Text files modified:
trunk/libs/intrusive/doc/Jamfile.v2 | 5
trunk/libs/intrusive/doc/intrusive.qbk | 234 +++++++++++++++++++++++++++++++++++++--
trunk/libs/intrusive/proj/vc7ide/Intrusive.sln | 16 ++
trunk/libs/intrusive/proj/vc7ide/_intrusivelib/_intrusivelib.vcproj | 30 ++++
trunk/libs/intrusive/test/itestvalue.hpp | 39 ++++++
trunk/libs/intrusive/test/smart_ptr.hpp | 76 ++++++++++++
6 files changed, 380 insertions(+), 20 deletions(-)
Modified: trunk/libs/intrusive/doc/Jamfile.v2
==============================================================================
--- trunk/libs/intrusive/doc/Jamfile.v2 (original)
+++ trunk/libs/intrusive/doc/Jamfile.v2 2007-10-30 03:02:10 EDT (Tue, 30 Oct 2007)
@@ -32,7 +32,10 @@
"hashtable_impl=hashtable" \\
"splay_set_impl=splay_set" \\
"splay_multiset_impl=splay_multiset" \\
- "splaytree_impl=splaytree""
+ "splaytree_impl=splaytree" \\
+ "avl_set_impl=avl_set" \\
+ "avl_multiset_impl=avl_multiset" \\
+ "avltree_impl=avltree""
;
xml intrusive : intrusive.qbk ;
Modified: trunk/libs/intrusive/doc/intrusive.qbk
==============================================================================
--- trunk/libs/intrusive/doc/intrusive.qbk (original)
+++ trunk/libs/intrusive/doc/intrusive.qbk 2007-10-30 03:02:10 EDT (Tue, 30 Oct 2007)
@@ -928,7 +928,8 @@
containers, like most STL associative container implemenatations are based on
red-black trees.
-The memory overhead of these containers is usually 3 pointers and an integer.
+The memory overhead of these containers is usually 3 pointers and a bit (with
+alignment issues, this means 3 pointers and an integer).
This size can be reduced to 3 pointers if pointers have even alignment
(which is usually true in most systems).
@@ -1259,11 +1260,11 @@
[endsect]
-[section:splay_set_multiset Intrusive splay tree-based associative containers: splay_set, splay_multiset]
+[section:splay_set_multiset Intrusive splay tree based associative containers: splay_set, splay_multiset and , splay_tree]
C++ associative containers are usually based on red-black tree implementations (e.g.: STL,
-Boost.Intrusive associative containers). However, there are other interesting data structures
-that offer some advantages (and also disadvantages).
+Boost.Intrusive associative containers). However, there are other interesting data
+structures that offer some advantages (and also disadvantages).
Splay trees are self-adjusting binary search trees used tipically in caches, memory
allocators and other applications, because splay trees have a "caching effect": recently
@@ -1305,8 +1306,8 @@
[section:splay_set_multiset_hooks splay_set, splay_multiset and splaytree hooks]
-[classref boost::intrusive::set set],
-[classref boost::intrusive::multiset multiset] and
+[classref boost::intrusive::splay_set splay_set],
+[classref boost::intrusive::splay_multiset splay_multiset] and
[classref boost::intrusive::splaytree splaytree]
share the same hooks.
@@ -1395,6 +1396,135 @@
[endsect]
+
+[section:avl_set_multiset Intrusive avl tree based associative containers: avl_set, avl_multiset and avltree]
+
+Similar to red-black trees, AVL trees are balanced binary trees.
+AVL trees are often compared with red-black trees because they support the same set of operations
+and because red-black trees also take O(log n) time for the basic operations.
+AVL trees are more rigidly balanced than Red-Black trees, leading to slower insertion and
+removal but faster retrieval, so AVL trees perform better
+than red-black trees for lookup-intensive applications.
+
+[*Boost.Intrusive] offers 3 containers based on avl trees:
+[classref boost::intrusive::avl_set avl_set],
+[classref boost::intrusive::avl_multiset avl_multiset] and
+[classref boost::intrusive::avltree avltree]. 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 usually 3
+pointers and 2 bits (due to alignment, this usually means 3 pointers plus an integer).
+This size can be reduced to 3 pointers if pointers have 4 byte alignment
+(which is usually true in 32 bit systems).
+
+An empty, non constant-time size [classref boost::intrusive::avl_set avl_set],
+[classref boost::intrusive::avl_multiset avl_multiset] or
+[classref boost::intrusive::avltree avltree]
+has also the size of 3 pointers and an integer (3 pointers when optimized for size).
+
+[section:avl_set_multiset_hooks avl_set, avl_multiset and avltree hooks]
+
+[classref boost::intrusive::avl_set avl_set],
+[classref boost::intrusive::avl_multiset avl_multiset] and
+[classref boost::intrusive::avltree avltree]
+share the same hooks.
+
+[c++]
+
+ template <class ...Options>
+ class avl_set_base_hook;
+
+* [classref boost::intrusive::avl_set_base_hook avl_set_base_hook]:
+ the user class derives publicly from this class to make
+ it compatible with avl tree based containers.
+
+[c++]
+
+ template <class ...Options>
+ class avl_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 avl tree based containers.
+
+[classref boost::intrusive::avl_set_base_hook avl_set_base_hook] and
+[classref boost::intrusive::avl_set_member_hook avl_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:
+
+* [*`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*>`.
+
+* [*`optimize_size<bool Enable>`]: The hook will be optimized for size
+ instead of speed. The hook will embed the balance bits of the AVL
+ tree node in the parent pointer if pointer alignment is multiple of 4.
+ Optimizing the size will reduce speed performance a bit since masking
+ operations will be needed to access parent pointer and balance factor attributes.
+ Default: `optimize_size<false>`.
+
+[endsect]
+
+[section:set_multiset_containers avl_set, avl_multiset and avltree containers]
+
+[c++]
+
+ template <class T, class ...Options>
+ class avl_set;
+
+ template <class T, class ...Options>
+ class avl_multiset;
+
+ template <class T, class ...Options>
+ class avltree;
+
+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 know about value traits go to the section
+ titled [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 an additional option:
+
+* [*`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> >`
+
+[endsect]
+
+[section:avl_set_multiset_example Example]
+
+Now let's see an small example using both hooks and
+[classref boost::intrusive::avl_set avl_set]/
+[classref boost::intrusive::avl_multiset avl_multiset]
+containers:
+
+[import ../example/doc_avl_set.cpp]
+[doc_avl_set_code]
+
+[endsect]
+
+[endsect]
+
+
[section:advanced_lookups_insertions Advanced lookup and insertion functions for associative containers]
[section:advanced_lookups Advanced lookups]
@@ -2056,7 +2186,7 @@
[import ../example/doc_rbtree_algorithms.cpp]
[doc_rbtree_algorithms_code]
-For a complete rbtree of functions see
+For a complete list of functions see
[classref boost::intrusive::rbtree_algorithms rbtree_algorithms reference].
[endsect]
@@ -2064,7 +2194,7 @@
[section:splaytree_algorithms Intrusive splay tree algorithms]
These algorithms are static
-members of the [classref boost::intrusive::rbtree_algorithms splaytree_algorithms] class:
+members of the [classref boost::intrusive::splaytree_algorithms splaytree_algorithms] class:
[c++]
@@ -2074,14 +2204,14 @@
An empty tree is formed by a node whose pointer to the parent node is null,
the pointers to the left and right nodes to itself.
-[classref boost::intrusive::splaytree_algorithms rbtree_algorithms]
+[classref boost::intrusive::splaytree_algorithms splaytree_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 rbtree
+* `node`: The type of the node that forms the circular splaytree
* `node_ptr`: The type of a pointer to a node (usually node*)
@@ -2107,20 +2237,88 @@
* `static void set_right(node_ptr n, node_ptr r);`:
Sets the pointer to the right node stored in "n" to "r".
-* `static color get_color(const_node_ptr n);`:
- Returns the color stored in "n".
-
Once we have a node traits configuration we can use [*Boost.Intrusive] algorithms
with our nodes:
[import ../example/doc_splaytree_algorithms.cpp]
[doc_splaytree_algorithms_code]
-For a complete rbtree of functions see
+For a complete list of functions see
[classref boost::intrusive::splaytree_algorithms splaytree_algorithms reference].
[endsect]
+[section:avltree_algorithms Intrusive avl tree algorithms]
+
+[classref boost::intrusive::avltree_algorithms avltree_algorithms] have the same
+interface as [classref boost::intrusive::rbtree_algorithms rbtree_algorithms].
+
+[c++]
+
+ template<class NodeTraits>
+ struct avltree_algorithms;
+
+[classref boost::intrusive::avltree_algorithms avltree_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 avltree
+
+* `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*)
+
+* `balance`: A type that can represent 3 balance types (usually an integer)
+
+[*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".
+
+* `static balance get_balance(const_node_ptr n);`:
+ Returns the balance factor stored in "n".
+
+* `static void set_balance(node_ptr n, balance b);`:
+ Sets the balance factor stored in "n" to "b".
+
+* `static balance negative();`:
+ Returns a value representing a negative balance factor.
+
+* `static balance zero();`:
+ Returns a value representing a zero balance factor.
+
+* `static balance positive();`:
+ Returns a value representing a positive balance factor.
+
+Once we have a node traits configuration we can use [*Boost.Intrusive] algorithms
+with our nodes:
+
+[import ../example/doc_avltree_algorithms.cpp]
+[doc_avltree_algorithms_code]
+
+For a complete list of functions see
+[classref boost::intrusive::avltree_algorithms avltree_algorithms reference].
+
+[endsect]
+
[endsect]
[section:value_traits Containers with custom ValueTraits]
@@ -2976,8 +3174,12 @@
[*Tom Brinkman] and [*Steven Watanabe]
for their comments and reviews in the Boost.Intrusive formal review.
-* Thanks to of Julienne Walker and The EC Team ([@http://eternallyconfuzzled.com]) for their
- great algorithms.
+* Thanks to of [*Julienne Walker] and [*The EC Team] ([@http://eternallyconfuzzled.com])
+ for their great algorithms.
+
+* Thanks to [*Daniel K. O.] for his AVL tree rebalancing code.
+
+* Thanks to [*Ralf Mattethat] for his splay tree article and code.
* Special thanks to [*Steven Watanabe] and [*Tobias Schwinger] for their
invaluable suggestions and improvements.
Added: trunk/libs/intrusive/example/doc_avl_set.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/intrusive/example/doc_avl_set.cpp 2007-10-30 03:02:10 EDT (Tue, 30 Oct 2007)
@@ -0,0 +1,88 @@
+/////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2006-2007
+//
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+//
+// See http://www.boost.org/libs/intrusive for documentation.
+//
+/////////////////////////////////////////////////////////////////////////////
+//[doc_avl_set_code
+#include <boost/intrusive/avl_set.hpp>
+#include <vector>
+#include <algorithm>
+#include <cassert>
+
+using namespace boost::intrusive;
+
+ //This is a base hook optimized for size
+class MyClass : public avl_set_base_hook<optimize_size<true> >
+{
+ int int_;
+
+ public:
+ //This is a member hook
+ avl_set_member_hook<> member_hook_;
+
+ MyClass(int i)
+ : int_(i)
+ {}
+ friend bool operator< (const MyClass &a, const MyClass &b)
+ { return a.int_ < b.int_; }
+ friend bool operator> (const MyClass &a, const MyClass &b)
+ { return a.int_ > b.int_; }
+ friend bool operator== (const MyClass &a, const MyClass &b)
+ { return a.int_ < b.int_; }
+};
+
+//Define an avl_set using the base hook that will store values in reverse order
+typedef avl_set< MyClass, compare<std::greater<MyClass> > > BaseSet;
+
+//Define an multiset using the member hook
+typedef member_hook<MyClass, avl_set_member_hook<>, &MyClass::member_hook_> MemberOption;
+typedef avl_multiset< MyClass, MemberOption> MemberMultiset;
+
+int main()
+{
+ typedef std::vector<MyClass>::iterator VectIt;
+ typedef std::vector<MyClass>::reverse_iterator VectRit;
+
+ //Create several MyClass objects, each one with a different value
+ std::vector<MyClass> values;
+ for(int i = 0; i < 100; ++i) values.push_back(MyClass(i));
+
+ BaseSet baseset;
+ MemberMultiset membermultiset;
+
+ //Check that size optimization is activated in the base hook
+ assert(sizeof(avl_set_base_hook<optimize_size<true> >) == 3*sizeof(void*));
+ //Check that size optimization is deactivated in the member hook
+ assert(sizeof(avl_set_member_hook<>) > 3*sizeof(void*));
+
+ //Now insert them in the reverse order in the base hook avl_set
+ for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it)
+ baseset.insert(*it);
+
+ //Now insert them in the same order as in vector in the member hook avl_set
+ for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it)
+ membermultiset.insert(*it);
+
+ //Now test avl_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 avl_set
+ for(; it != itend; ++it, ++rbit)
+ if(&*rbit != &*it) return 1;
+
+ //Test the objects inserted in the member hook avl_set
+ for(it = values.begin(); it != itend; ++it, ++mit)
+ if(&*mit != &*it) return 1;
+ }
+ return 0;
+}
+//]
Added: trunk/libs/intrusive/example/doc_avltree_algorithms.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/intrusive/example/doc_avltree_algorithms.cpp 2007-10-30 03:02:10 EDT (Tue, 30 Oct 2007)
@@ -0,0 +1,85 @@
+/////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2007
+//
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+//
+// See http://www.boost.org/libs/intrusive for documentation.
+//
+/////////////////////////////////////////////////////////////////////////////
+//[doc_avltree_algorithms_code
+#include <boost/intrusive/avltree_algorithms.hpp>
+#include <cassert>
+
+struct my_node
+{
+ my_node(int i = 0)
+ : int_(i)
+ {}
+ my_node *parent_, *left_, *right_;
+ int balance_;
+ //other members
+ int int_;
+};
+
+//Define our own avltree_node_traits
+struct my_avltree_node_traits
+{
+ typedef my_node node;
+ typedef my_node * node_ptr;
+ typedef const my_node * const_node_ptr;
+ typedef int balance;
+
+ static node_ptr get_parent(const_node_ptr n) { return n->parent_; }
+ static void set_parent(node_ptr n, node_ptr parent){ n->parent_ = parent; }
+ static node_ptr get_left(const_node_ptr n) { return n->left_; }
+ static void set_left(node_ptr n, node_ptr left) { n->left_ = left; }
+ static node_ptr get_right(const_node_ptr n) { return n->right_; }
+ static void set_right(node_ptr n, node_ptr right) { n->right_ = right; }
+ static balance get_balance(const_node_ptr n) { return n->balance_; }
+ static void set_balance(node_ptr n, balance b) { n->balance_ = b; }
+ static balance negative() { return -1; }
+ static balance zero() { return 0; }
+ static balance positive() { return 1; }
+};
+
+struct node_ptr_compare
+{
+ bool operator()(my_node *a, my_node *b)
+ { return a->int_ < b->int_; }
+};
+
+int main()
+{
+ typedef boost::intrusive::avltree_algorithms<my_avltree_node_traits> algo;
+ my_node header, two(2), three(3);
+
+ //Create an empty avltree container:
+ //"header" will be the header node of the tree
+ algo::init_header(&header);
+
+ //Now insert node "two" in the tree using the sorting functor
+ algo::insert_equal_upper_bound(&header, &two, node_ptr_compare());
+
+ //Now insert node "three" in the tree using the sorting functor
+ algo::insert_equal_lower_bound(&header, &three, node_ptr_compare());
+
+ //Now take the first node (the left node of the header)
+ my_node *n = header.left_;
+ assert(n == &two);
+
+ //Now go to the next node
+ n = algo::next_node(n);
+ assert(n == &three);
+
+ //Erase a node just using a pointer to it
+ algo::unlink(&two);
+
+ //Erase a node using also the header (faster)
+ algo::erase(&header, &three);
+ return 0;
+}
+
+//]
Added: trunk/libs/intrusive/example/doc_splaytree_algorithms.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/intrusive/example/doc_splaytree_algorithms.cpp 2007-10-30 03:02:10 EDT (Tue, 30 Oct 2007)
@@ -0,0 +1,78 @@
+/////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2007
+//
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+//
+// See http://www.boost.org/libs/intrusive for documentation.
+//
+/////////////////////////////////////////////////////////////////////////////
+//[doc_splaytree_algorithms_code
+#include <boost/intrusive/splaytree_algorithms.hpp>
+#include <cassert>
+
+struct my_node
+{
+ my_node(int i = 0)
+ : int_(i)
+ {}
+ my_node *parent_, *left_, *right_;
+ //other members
+ int int_;
+};
+
+//Define our own splaytree_node_traits
+struct my_splaytree_node_traits
+{
+ typedef my_node node;
+ typedef my_node * node_ptr;
+ typedef const my_node * const_node_ptr;
+
+ static node_ptr get_parent(const_node_ptr n) { return n->parent_; }
+ static void set_parent(node_ptr n, node_ptr parent){ n->parent_ = parent; }
+ static node_ptr get_left(const_node_ptr n) { return n->left_; }
+ static void set_left(node_ptr n, node_ptr left) { n->left_ = left; }
+ static node_ptr get_right(const_node_ptr n) { return n->right_; }
+ static void set_right(node_ptr n, node_ptr right) { n->right_ = right; }
+};
+
+struct node_ptr_compare
+{
+ bool operator()(my_node *a, my_node *b)
+ { return a->int_ < b->int_; }
+};
+
+int main()
+{
+ typedef boost::intrusive::splaytree_algorithms<my_splaytree_node_traits> algo;
+ my_node header, two(2), three(3);
+
+ //Create an empty splaytree container:
+ //"header" will be the header node of the tree
+ algo::init_header(&header);
+
+ //Now insert node "two" in the tree using the sorting functor
+ algo::insert_equal_upper_bound(&header, &two, node_ptr_compare());
+
+ //Now insert node "three" in the tree using the sorting functor
+ algo::insert_equal_lower_bound(&header, &three, node_ptr_compare());
+
+ //Now take the first node (the left node of the header)
+ my_node *n = header.left_;
+ assert(n == &two);
+
+ //Now go to the next node
+ n = algo::next_node(n);
+ assert(n == &three);
+
+ //Erase a node just using a pointer to it
+ algo::unlink(&two);
+
+ //Erase a node using also the header (faster)
+ algo::erase(&header, &three);
+ return 0;
+}
+
+//]
Modified: trunk/libs/intrusive/proj/vc7ide/Intrusive.sln
==============================================================================
--- trunk/libs/intrusive/proj/vc7ide/Intrusive.sln (original)
+++ trunk/libs/intrusive/proj/vc7ide/Intrusive.sln 2007-10-30 03:02:10 EDT (Tue, 30 Oct 2007)
@@ -63,6 +63,14 @@
ProjectSection(ProjectDependencies) = postProject
EndProjectSection
EndProject
+Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "avl_multiset", "avl_multiset\avl_multiset.vcproj", "{0AE70176-5B8C-4BC7-392C-A4A312B07893}"
+ ProjectSection(ProjectDependencies) = postProject
+ EndProjectSection
+EndProject
+Project("{8BC9CEB8-8B4A-11D0-8D11-00A0C91BC942}") = "avl_set", "avl_set\avl_set.vcproj", "{16909EE7-24AF-97C1-C76B-204B971BA959}"
+ ProjectSection(ProjectDependencies) = postProject
+ EndProjectSection
+EndProject
Global
GlobalSection(SolutionConfiguration) = preSolution
Debug = Debug
@@ -135,6 +143,14 @@
{1E6909E7-C971-F24A-6C7B-A92094B71B59}.Debug.Build.0 = Debug|Win32
{1E6909E7-C971-F24A-6C7B-A92094B71B59}.Release.ActiveCfg = Release|Win32
{1E6909E7-C971-F24A-6C7B-A92094B71B59}.Release.Build.0 = Release|Win32
+ {0AE70176-5B8C-4BC7-392C-A4A312B07893}.Debug.ActiveCfg = Debug|Win32
+ {0AE70176-5B8C-4BC7-392C-A4A312B07893}.Debug.Build.0 = Debug|Win32
+ {0AE70176-5B8C-4BC7-392C-A4A312B07893}.Release.ActiveCfg = Release|Win32
+ {0AE70176-5B8C-4BC7-392C-A4A312B07893}.Release.Build.0 = Release|Win32
+ {16909EE7-24AF-97C1-C76B-204B971BA959}.Debug.ActiveCfg = Debug|Win32
+ {16909EE7-24AF-97C1-C76B-204B971BA959}.Debug.Build.0 = Debug|Win32
+ {16909EE7-24AF-97C1-C76B-204B971BA959}.Release.ActiveCfg = Release|Win32
+ {16909EE7-24AF-97C1-C76B-204B971BA959}.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 2007-10-30 03:02:10 EDT (Tue, 30 Oct 2007)
@@ -106,6 +106,18 @@
Filter="h;hpp;hxx;hm;inl;inc;xsd"
UniqueIdentifier="{93995380-89BD-4b04-88EB-625FBE52EBFB}">
<File
+ RelativePath="..\..\..\..\..\boost\intrusive\avl_set.hpp">
+ </File>
+ <File
+ RelativePath="..\..\..\..\..\boost\intrusive\avl_set_hook.hpp">
+ </File>
+ <File
+ RelativePath="..\..\..\..\..\boost\intrusive\avltree.hpp">
+ </File>
+ <File
+ RelativePath="..\..\..\..\..\boost\intrusive\avltree_algorithms.hpp">
+ </File>
+ <File
RelativePath="..\..\..\..\..\boost\intrusive\circular_list_algorithms.hpp">
</File>
<File
@@ -136,6 +148,9 @@
RelativePath="..\..\..\..\..\boost\intrusive\options.hpp">
</File>
<File
+ RelativePath="..\..\..\..\..\boost\intrusive\pointer_plus_2_bits.hpp">
+ </File>
+ <File
RelativePath="..\..\..\..\..\boost\intrusive\pointer_plus_bit.hpp">
</File>
<File
@@ -184,6 +199,9 @@
RelativePath="..\..\..\..\..\boost\intrusive\detail\assert.hpp">
</File>
<File
+ RelativePath="..\..\..\..\..\boost\intrusive\detail\avltree_node.hpp">
+ </File>
+ <File
RelativePath="..\..\..\..\..\boost\intrusive\detail\config_begin.hpp">
</File>
<File
@@ -220,9 +238,6 @@
RelativePath="..\..\..\..\..\boost\intrusive\detail\slist_node.hpp">
</File>
<File
- RelativePath="..\..\..\..\..\boost\intrusive\detail\splaytree_node.hpp">
- </File>
- <File
RelativePath="..\..\..\..\..\boost\intrusive\detail\transform_iterator.hpp">
</File>
<File
@@ -287,6 +302,12 @@
RelativePath="..\..\..\example\doc_auto_unlink.cpp">
</File>
<File
+ RelativePath="..\..\..\example\doc_avl_set.cpp">
+ </File>
+ <File
+ RelativePath="..\..\..\example\doc_avltree_algorithms.cpp">
+ </File>
+ <File
RelativePath="..\..\..\example\doc_bucket_traits.cpp">
</File>
<File
@@ -335,6 +356,9 @@
RelativePath="..\..\..\example\doc_splay_set.cpp">
</File>
<File
+ RelativePath="..\..\..\example\doc_splaytree_algorithms.cpp">
+ </File>
+ <File
RelativePath="..\..\..\example\doc_stateful_value_traits.cpp">
</File>
<File
Added: trunk/libs/intrusive/proj/vc7ide/avl_multiset/avl_multiset.vcproj
==============================================================================
--- (empty file)
+++ trunk/libs/intrusive/proj/vc7ide/avl_multiset/avl_multiset.vcproj 2007-10-30 03:02:10 EDT (Tue, 30 Oct 2007)
@@ -0,0 +1,127 @@
+<?xml version="1.0" encoding="Windows-1252"?>
+<VisualStudioProject
+ ProjectType="Visual C++"
+ Version="7.10"
+ Name="avl_multiset"
+ ProjectGUID="{0AE70176-5B8C-4BC7-392C-A4A312B07893}"
+ 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"
+ GeneratePreprocessedFile="0"
+ MinimalRebuild="TRUE"
+ BasicRuntimeChecks="3"
+ RuntimeLibrary="5"
+ DisableLanguageExtensions="TRUE"
+ ForceConformanceInForLoopScope="TRUE"
+ UsePrecompiledHeader="0"
+ WarningLevel="3"
+ Detect64BitPortabilityProblems="TRUE"
+ DebugInformationFormat="4"/>
+ <Tool
+ Name="VCCustomBuildTool"/>
+ <Tool
+ Name="VCLinkerTool"
+ OutputFile="$(OutDir)/avl_multiset.exe"
+ LinkIncremental="2"
+ GenerateDebugInformation="TRUE"
+ ProgramDatabaseFile="$(OutDir)/avl_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)/avl_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="{F9A837FC-4236-A8D7-745E-2D383A2E13EA}">
+ <File
+ RelativePath="..\..\..\test\avl_multiset_test.cpp">
+ </File>
+ </Filter>
+ </Files>
+ <Globals>
+ </Globals>
+</VisualStudioProject>
Added: trunk/libs/intrusive/proj/vc7ide/avl_set/avl_set.vcproj
==============================================================================
--- (empty file)
+++ trunk/libs/intrusive/proj/vc7ide/avl_set/avl_set.vcproj 2007-10-30 03:02:10 EDT (Tue, 30 Oct 2007)
@@ -0,0 +1,126 @@
+<?xml version="1.0" encoding="Windows-1252"?>
+<VisualStudioProject
+ ProjectType="Visual C++"
+ Version="7.10"
+ Name="avl_set"
+ ProjectGUID="{16909EE7-24AF-97C1-C76B-204B971BA959}"
+ 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"
+ ForceConformanceInForLoopScope="TRUE"
+ UsePrecompiledHeader="0"
+ WarningLevel="3"
+ Detect64BitPortabilityProblems="TRUE"
+ DebugInformationFormat="4"/>
+ <Tool
+ Name="VCCustomBuildTool"/>
+ <Tool
+ Name="VCLinkerTool"
+ OutputFile="$(OutDir)/avl_set.exe"
+ LinkIncremental="2"
+ GenerateDebugInformation="TRUE"
+ ProgramDatabaseFile="$(OutDir)/avl_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)/avl_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="{FC776C11-2A4F-326F-1E35-4C72A23B325A}">
+ <File
+ RelativePath="..\..\..\test\avl_set_test.cpp">
+ </File>
+ </Filter>
+ </Files>
+ <Globals>
+ </Globals>
+</VisualStudioProject>
Added: trunk/libs/intrusive/test/avl_multiset_test.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/intrusive/test/avl_multiset_test.cpp 2007-10-30 03:02:10 EDT (Tue, 30 Oct 2007)
@@ -0,0 +1,394 @@
+/////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Olaf Krzikalla 2004-2006.
+// (C) Copyright Ion Gaztanaga 2006-2007.
+//
+// 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/avl_set.hpp>
+#include <boost/intrusive/detail/pointer_to_other.hpp>
+#include "itestvalue.hpp"
+#include "smart_ptr.hpp"
+#include "common_functors.hpp"
+#include <vector>
+#include <boost/detail/lightweight_test.hpp>
+#include "test_macros.hpp"
+#include "test_container.hpp"
+#include <set>
+
+namespace boost { namespace intrusive { namespace test {
+
+template<class T, class O1, class O2, class O3, class O4>
+struct has_const_overloads<boost::intrusive::avl_multiset<T, O1, O2, O3, O4> >
+{
+ static const bool value = false;
+};
+
+}}}
+
+using namespace boost::intrusive;
+template<class ValueTraits>
+struct test_avl_multiset
+{
+ typedef typename ValueTraits::value_type value_type;
+ static void test_all (std::vector<value_type>& values);
+ static void test_sort(std::vector<value_type>& values);
+ static void test_insert(std::vector<value_type>& values);
+ static void test_swap(std::vector<value_type>& values);
+ static void test_find(std::vector<value_type>& values);
+ static void test_impl();
+ static void test_clone(std::vector<value_type>& values);
+ static void test_container_from_end(std::vector<value_type>& values);
+};
+
+template<class ValueTraits>
+void test_avl_multiset<ValueTraits>::test_all
+ (std::vector<typename ValueTraits::value_type>& values)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef avl_multiset
+ < value_type
+ , value_traits<ValueTraits>
+ , constant_time_size<value_type::constant_time_size>
+ > avl_multiset_type;
+ {
+ avl_multiset_type testset(values.begin(), values.end());
+ test::test_container(testset);
+ testset.clear();
+ testset.insert(values.begin(), values.end());
+ test::test_common_unordered_and_associative_container(testset, values);
+ testset.clear();
+ testset.insert(values.begin(), values.end());
+ test::test_associative_container(testset, values);
+ testset.clear();
+ testset.insert(values.begin(), values.end());
+ test::test_non_unique_container(testset, values);
+ }
+ test_sort(values);
+ test_insert(values);
+ test_swap(values);
+ test_find(values);
+ test_impl();
+ test_clone(values);
+ test_container_from_end(values);
+}
+
+//test case due to an error in tree implementation:
+template<class ValueTraits>
+void test_avl_multiset<ValueTraits>::test_impl()
+{
+ typedef typename ValueTraits::value_type value_type;
+ std::vector<value_type> values (5);
+ for (int i = 0; i < 5; ++i)
+ values[i].value_ = i;
+ typedef typename ValueTraits::value_type value_type;
+ typedef avl_multiset
+ < value_type
+ , value_traits<ValueTraits>
+ , constant_time_size<value_type::constant_time_size>
+ > multiset_type;
+
+ multiset_type testset;
+ for (int i = 0; i < 5; ++i)
+ testset.insert (values[i]);
+
+ testset.erase (testset.iterator_to (values[0]));
+ testset.erase (testset.iterator_to (values[1]));
+ testset.insert (values[1]);
+
+ testset.erase (testset.iterator_to (values[2]));
+ testset.erase (testset.iterator_to (values[3]));
+}
+
+//test: constructor, iterator, clear, reverse_iterator, front, back, size:
+template<class ValueTraits>
+void test_avl_multiset<ValueTraits>::test_sort
+(std::vector<typename ValueTraits::value_type>& values)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef avl_multiset
+ < value_type
+ , value_traits<ValueTraits>
+ , constant_time_size<value_type::constant_time_size>
+ > multiset_type;
+
+ multiset_type testset1 (values.begin(), values.end());
+ { int init_values [] = { 1, 2, 2, 3, 4, 5 };
+ TEST_INTRUSIVE_SEQUENCE( init_values, testset1.begin() ); }
+
+ testset1.clear();
+ BOOST_TEST (testset1.empty());
+
+ typedef avl_multiset
+ <value_type
+ , compare<even_odd>
+ , value_traits<ValueTraits>
+ , constant_time_size<value_type::constant_time_size>
+ > multiset_type2;
+ multiset_type2 testset2 (&values[0], &values[0] + 6);
+ { int init_values [] = { 5, 3, 1, 4, 2, 2 };
+ TEST_INTRUSIVE_SEQUENCE( init_values, testset2.rbegin() ); }
+
+ BOOST_TEST (testset2.begin()->value_ == 2);
+ BOOST_TEST (testset2.rbegin()->value_ == 5);
+}
+
+//test: insert, const_iterator, const_reverse_iterator, erase, iterator_to:
+template<class ValueTraits>
+void test_avl_multiset<ValueTraits>::test_insert
+(std::vector<typename ValueTraits::value_type>& values)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef avl_multiset
+ < value_type
+ , value_traits<ValueTraits>
+ , size_type<std::size_t>
+ , constant_time_size<value_type::constant_time_size>
+ > multiset_type;
+
+ multiset_type testset;
+ testset.insert(&values[0] + 2, &values[0] + 5);
+ { int init_values [] = { 1, 4, 5 };
+ TEST_INTRUSIVE_SEQUENCE( init_values, testset.begin() ); }
+
+ typename multiset_type::iterator i = testset.begin();
+ BOOST_TEST (i->value_ == 1);
+
+ i = testset.insert (i, values[0]);
+ BOOST_TEST (&*i == &values[0]);
+
+ { int init_values [] = { 5, 4, 3, 1 };
+ TEST_INTRUSIVE_SEQUENCE( init_values, testset.rbegin() ); }
+
+ i = testset.iterator_to (values[2]);
+ BOOST_TEST (&*i == &values[2]);
+
+ i = multiset_type::s_iterator_to (values[2]);
+ BOOST_TEST (&*i == &values[2]);
+
+ testset.erase(i);
+
+ { int init_values [] = { 1, 3, 5 };
+ TEST_INTRUSIVE_SEQUENCE( init_values, testset.begin() ); }
+}
+
+//test: insert (seq-version), swap, erase (seq-version), size:
+template<class ValueTraits>
+void test_avl_multiset<ValueTraits>::test_swap
+(std::vector<typename ValueTraits::value_type>& values)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef avl_multiset
+ < value_type
+ , value_traits<ValueTraits>
+ , size_type<std::size_t>
+ , constant_time_size<value_type::constant_time_size>
+ > multiset_type;
+ multiset_type testset1 (&values[0], &values[0] + 2);
+ multiset_type testset2;
+ testset2.insert (&values[0] + 2, &values[0] + 6);
+
+ { int init_values [] = { 1, 2, 4, 5 };
+ TEST_INTRUSIVE_SEQUENCE( init_values, testset2.begin() ); }
+ { int init_values [] = { 2, 3 };
+ TEST_INTRUSIVE_SEQUENCE( init_values, testset1.begin() ); }
+
+ testset1.swap (testset2);
+
+ { int init_values [] = { 1, 2, 4, 5 };
+ TEST_INTRUSIVE_SEQUENCE( init_values, testset1.begin() ); }
+ { int init_values [] = { 2, 3 };
+ TEST_INTRUSIVE_SEQUENCE( init_values, testset2.begin() ); }
+
+ testset1.erase (testset1.iterator_to(values[5]), testset1.end());
+ BOOST_TEST (testset1.size() == 1);
+ BOOST_TEST (&*testset1.begin() == &values[3]);
+}
+
+//test: find, equal_range (lower_bound, upper_bound):
+template<class ValueTraits>
+void test_avl_multiset<ValueTraits>::test_find
+(std::vector<typename ValueTraits::value_type>& values)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef avl_multiset
+ < value_type
+ , value_traits<ValueTraits>
+ , size_type<std::size_t>
+ , constant_time_size<value_type::constant_time_size>
+ > multiset_type;
+ multiset_type testset (values.begin(), values.end());
+ typedef typename multiset_type::iterator iterator;
+
+ value_type cmp_val;
+ cmp_val.value_ = 2;
+ iterator i = testset.find (cmp_val);
+ BOOST_TEST (i->value_ == 2);
+ BOOST_TEST ((++i)->value_ == 2);
+ std::pair<iterator,iterator> range = testset.equal_range (cmp_val);
+
+ BOOST_TEST (range.first->value_ == 2);
+ BOOST_TEST (range.second->value_ == 3);
+ BOOST_TEST (std::distance (range.first, range.second) == 2);
+
+ cmp_val.value_ = 7;
+ BOOST_TEST (testset.find (cmp_val) == testset.end());
+}
+
+template<class ValueTraits>
+void test_avl_multiset<ValueTraits>::test_clone
+ (std::vector<typename ValueTraits::value_type>& values)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef avl_multiset
+ < value_type
+ , value_traits<ValueTraits>
+ , size_type<std::size_t>
+ , constant_time_size<value_type::constant_time_size>
+ > multiset_type;
+ multiset_type testmultiset1 (&values[0], &values[0] + values.size());
+ multiset_type testmultiset2;
+
+ testmultiset2.clone_from(testmultiset1, test::new_cloner<value_type>(), test::delete_disposer<value_type>());
+ BOOST_TEST (testmultiset2 == testmultiset1);
+ testmultiset2.clear_and_dispose(test::delete_disposer<value_type>());
+ BOOST_TEST (testmultiset2.empty());
+}
+
+template<class ValueTraits>
+void test_avl_multiset<ValueTraits>::test_container_from_end
+ (std::vector<typename ValueTraits::value_type>& values)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef avl_multiset
+ < value_type
+ , value_traits<ValueTraits>
+ , size_type<std::size_t>
+ , constant_time_size<value_type::constant_time_size>
+ > multiset_type;
+
+ multiset_type testmultiset (&values[0], &values[0] + values.size());
+ BOOST_TEST (testmultiset == multiset_type::container_from_end_iterator(testmultiset.end()));
+ BOOST_TEST (testmultiset == multiset_type::container_from_end_iterator(testmultiset.cend()));
+}
+
+template<class VoidPointer, bool constant_time_size>
+class test_main_template
+{
+ public:
+ int operator()()
+ {
+ for(int n = 0; n < 2; ++n){
+ typedef testvalue<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);
+ for (int i = 0; i < 6; ++i)
+ data[i].value_ = random_init[i];
+
+ test_avl_multiset < typename detail::get_base_value_traits
+ < value_type
+ , typename value_type::avl_set_base_hook_t
+ >::type
+ >::test_all(data);
+ test_avl_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_
+ >
+ >::type
+ >::test_all(data);
+ }
+ return 0;
+ }
+};
+
+template<class VoidPointer>
+class test_main_template<VoidPointer, false>
+{
+ public:
+ int operator()()
+ {
+ for(int n = 0; n < 2; ++n){
+ typedef testvalue<VoidPointer, false> value_type;
+ static const int random_init[6] = { 3, 2, 4, 1, 5, 2 };
+ std::vector<testvalue<VoidPointer, false> > data (6);
+ for (int i = 0; i < 6; ++i)
+ data[i].value_ = random_init[i];
+
+ test_avl_multiset < typename detail::get_base_value_traits
+ < value_type
+ , typename value_type::avl_set_base_hook_t
+ >::type
+ >::test_all(data);
+
+ test_avl_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_
+ >
+ >::type
+ >::test_all(data);
+
+ test_avl_multiset < typename detail::get_base_value_traits
+ < value_type
+ , typename value_type::avl_set_auto_base_hook_t
+ >::type
+ >::test_all(data);
+
+ test_avl_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_
+ >
+ >::type
+ >::test_all(data);
+ }
+ return 0;
+ }
+};
+
+//Explicit instantiations of non-counted classes
+//template class multiset
+// <set_base_raw, std::less<set_base_raw::value_type>, false>;
+//template class multiset
+// <set_member_raw, std::less<set_member_raw::value_type>, false>;
+//template class multiset
+// <set_auto_base_raw, std::less<set_auto_base_raw::value_type>, false>;
+//template class multiset
+// <set_auto_member_raw, std::less<set_auto_member_raw::value_type>, false>;
+//template class multiset
+// <set_base_smart, std::less<set_base_smart::value_type>, false>;
+//template class multiset
+// <set_member_smart, std::less<set_member_smart::value_type>, false>;
+//template class multiset
+// <set_auto_base_smart, std::less<set_auto_base_smart::value_type>, false>;
+//template class multiset
+// <set_auto_member_smart, std::less<set_auto_member_smart::value_type>, false>;
+
+//Explicit instantiation of counted classes
+//template class multiset
+// <set_base_raw_t, std::less<set_base_raw_t::value_type>, true>;
+//template class multiset
+// <set_member_raw_t, std::less<set_member_raw_t::value_type>, true>;
+//template class multiset
+// <set_base_smart_t, std::less<set_base_smart_t::value_type>, true>;
+//template class multiset
+// <set_member_smart_t, std::less<set_member_smart_t::value_type>, true>;
+
+int main( int, char* [] )
+{
+ test_main_template<void*, false>()();
+ test_main_template<smart_ptr<void>, false>()();
+ test_main_template<void*, true>()();
+ test_main_template<smart_ptr<void>, true>()();
+ return boost::report_errors();
+}
Added: trunk/libs/intrusive/test/avl_set_test.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/intrusive/test/avl_set_test.cpp 2007-10-30 03:02:10 EDT (Tue, 30 Oct 2007)
@@ -0,0 +1,350 @@
+/////////////////////////////////////////////////////////////////////////////
+//
+// (C) Copyright Ion Gaztanaga 2007.
+//
+// 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/avl_set.hpp>
+#include <boost/intrusive/detail/pointer_to_other.hpp>
+#include "itestvalue.hpp"
+#include "smart_ptr.hpp"
+#include "common_functors.hpp"
+#include <vector>
+#include <boost/detail/lightweight_test.hpp>
+#include "test_macros.hpp"
+#include "test_container.hpp"
+#include <set>
+
+namespace boost { namespace intrusive { namespace test {
+
+template<class T, class O1, class O2, class O3, class O4>
+struct has_const_overloads<boost::intrusive::avl_set<T, O1, O2, O3, O4> >
+{
+ static const bool value = false;
+};
+
+}}}
+
+using namespace boost::intrusive;
+
+template<class ValueTraits>
+struct test_avl_set
+{
+ typedef typename ValueTraits::value_type value_type;
+ static void test_all(std::vector<value_type>& values);
+ static void test_sort(std::vector<value_type>& values);
+ static void test_insert(std::vector<value_type>& values);
+ static void test_swap(std::vector<value_type>& values);
+ static void test_find(std::vector<value_type>& values);
+ static void test_impl();
+ static void test_clone(std::vector<value_type>& values);
+ static void test_container_from_end(std::vector<value_type>& values);
+};
+
+template<class ValueTraits>
+void test_avl_set<ValueTraits>::test_all(std::vector<typename ValueTraits::value_type>& values)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef avl_set
+ < value_type
+ , value_traits<ValueTraits>
+ , constant_time_size<value_type::constant_time_size>
+ > avl_set_type;
+ {
+ avl_set_type testset(values.begin(), values.end());
+ test::test_container(testset);
+ testset.clear();
+ testset.insert(values.begin(), values.end());
+ test::test_common_unordered_and_associative_container(testset, values);
+ testset.clear();
+ testset.insert(values.begin(), values.end());
+ test::test_associative_container(testset, values);
+ testset.clear();
+ testset.insert(values.begin(), values.end());
+ test::test_unique_container(testset, values);
+ }
+
+ test_sort(values);
+ test_insert(values);
+ test_swap(values);
+ test_find(values);
+ test_impl();
+ test_clone(values);
+ test_container_from_end(values);
+}
+
+//test case due to an error in tree implementation:
+template<class ValueTraits>
+void test_avl_set<ValueTraits>::test_impl()
+{
+ typedef typename ValueTraits::value_type value_type;
+ std::vector<value_type> values (5);
+ for (int i = 0; i < 5; ++i)
+ values[i].value_ = i;
+
+ typedef typename ValueTraits::value_type value_type;
+ typedef avl_set
+ < value_type
+ , value_traits<ValueTraits>
+ , constant_time_size<value_type::constant_time_size>
+ > avl_set_type;
+ avl_set_type testset;
+ for (int i = 0; i < 5; ++i)
+ testset.insert (values[i]);
+
+ testset.erase (testset.iterator_to (values[0]));
+ testset.erase (testset.iterator_to (values[1]));
+ testset.insert (values[1]);
+
+ testset.erase (testset.iterator_to (values[2]));
+ testset.erase (testset.iterator_to (values[3]));
+}
+
+//test: constructor, iterator, clear, reverse_iterator, front, back, size:
+template<class ValueTraits>
+void test_avl_set<ValueTraits>::test_sort(std::vector<typename ValueTraits::value_type>& values)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef avl_set
+ < value_type
+ , value_traits<ValueTraits>
+ , constant_time_size<value_type::constant_time_size>
+ > avl_set_type;
+ avl_set_type testset1 (values.begin(), values.end());
+ { int init_values [] = { 1, 2, 3, 4, 5 };
+ TEST_INTRUSIVE_SEQUENCE( init_values, testset1.begin() ); }
+
+ testset1.clear();
+ BOOST_TEST (testset1.empty());
+
+ typedef typename ValueTraits::value_type value_type;
+ typedef avl_set
+ < value_type
+ , compare<even_odd>
+ , value_traits<ValueTraits>
+ , constant_time_size<value_type::constant_time_size>
+ > set_type2;
+ set_type2 testset2 (&values[0], &values[0] + 6);
+ { int init_values [] = { 5, 3, 1, 4, 2 };
+ TEST_INTRUSIVE_SEQUENCE( init_values, testset2.rbegin() ); }
+ BOOST_TEST (testset2.begin()->value_ == 2);
+ BOOST_TEST (testset2.rbegin()->value_ == 5);
+}
+
+//test: insert, const_iterator, const_reverse_iterator, erase, s_iterator_to:
+template<class ValueTraits>
+void test_avl_set<ValueTraits>::test_insert(std::vector<typename ValueTraits::value_type>& values)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef avl_set
+ < value_type
+ , value_traits<ValueTraits>
+ , constant_time_size<value_type::constant_time_size>
+ > avl_set_type;
+ avl_set_type testset;
+ testset.insert(&values[0] + 2, &values[0] + 5);
+
+ const avl_set_type& const_testset = testset;
+ { int init_values [] = { 1, 4, 5 };
+ TEST_INTRUSIVE_SEQUENCE( init_values, const_testset.begin() ); }
+
+ typename avl_set_type::iterator i = testset.begin();
+ BOOST_TEST (i->value_ == 1);
+
+ i = testset.insert (i, values[0]);
+ BOOST_TEST (&*i == &values[0]);
+
+ { int init_values [] = { 5, 4, 3, 1 };
+ TEST_INTRUSIVE_SEQUENCE( init_values, testset.rbegin() ); }
+
+ i = testset.iterator_to (values[2]);
+ BOOST_TEST (&*i == &values[2]);
+
+ i = avl_set_type::s_iterator_to(values[2]);
+ BOOST_TEST (&*i == &values[2]);
+
+ testset.erase (i);
+ { int init_values [] = { 1, 3, 5 };
+ TEST_INTRUSIVE_SEQUENCE( init_values, testset.begin() ); }
+}
+
+//test: insert (seq-version), swap, erase (seq-version), size:
+template<class ValueTraits>
+void test_avl_set<ValueTraits>::test_swap(std::vector<typename ValueTraits::value_type>& values)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef avl_set
+ < value_type
+ , value_traits<ValueTraits>
+ , constant_time_size<value_type::constant_time_size>
+ > avl_set_type;
+ avl_set_type testset1 (&values[0], &values[0] + 2);
+ avl_set_type testset2;
+ testset2.insert (&values[0] + 2, &values[0] + 6);
+ testset1.swap (testset2);
+
+ { int init_values [] = { 1, 2, 4, 5 };
+ TEST_INTRUSIVE_SEQUENCE( init_values, testset1.begin() ); }
+
+ { int init_values [] = { 2, 3 };
+ TEST_INTRUSIVE_SEQUENCE( init_values, testset2.begin() ); }
+
+ testset1.erase (testset1.iterator_to(values[5]), testset1.end());
+ BOOST_TEST (testset1.size() == 1);
+ // BOOST_TEST (&testset1.front() == &values[3]);
+ BOOST_TEST (&*testset1.begin() == &values[3]);
+}
+
+//test: find, equal_range (lower_bound, upper_bound):
+template<class ValueTraits>
+void test_avl_set<ValueTraits>::test_find(std::vector<typename ValueTraits::value_type>& values)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef avl_set
+ < value_type
+ , value_traits<ValueTraits>
+ , constant_time_size<value_type::constant_time_size>
+ > avl_set_type;
+ avl_set_type testset (values.begin(), values.end());
+ typedef typename avl_set_type::iterator iterator;
+
+ value_type cmp_val;
+ cmp_val.value_ = 2;
+ iterator i = testset.find (cmp_val);
+ BOOST_TEST (i->value_ == 2);
+ BOOST_TEST ((++i)->value_ != 2);
+ std::pair<iterator,iterator> range = testset.equal_range (cmp_val);
+
+ BOOST_TEST (range.first->value_ == 2);
+ BOOST_TEST (range.second->value_ == 3);
+ BOOST_TEST (std::distance (range.first, range.second) == 1);
+
+ cmp_val.value_ = 7;
+ BOOST_TEST (testset.find (cmp_val) == testset.end());
+}
+
+template<class ValueTraits>
+void test_avl_set<ValueTraits>
+ ::test_clone(std::vector<typename ValueTraits::value_type>& values)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef avl_set
+ < value_type
+ , value_traits<ValueTraits>
+ , constant_time_size<value_type::constant_time_size>
+ > avl_set_type;
+
+ avl_set_type testset1 (&values[0], &values[0] + values.size());
+ avl_set_type testset2;
+
+ testset2.clone_from(testset1, test::new_cloner<value_type>(), test::delete_disposer<value_type>());
+ BOOST_TEST (testset2 == testset1);
+ testset2.clear_and_dispose(test::delete_disposer<value_type>());
+ BOOST_TEST (testset2.empty());
+}
+
+template<class ValueTraits>
+void test_avl_set<ValueTraits>
+ ::test_container_from_end(std::vector<typename ValueTraits::value_type>& values)
+{
+ typedef typename ValueTraits::value_type value_type;
+ typedef avl_set
+ < value_type
+ , value_traits<ValueTraits>
+ , constant_time_size<value_type::constant_time_size>
+ > avl_set_type;
+ avl_set_type testset (&values[0], &values[0] + values.size());
+ BOOST_TEST (testset == avl_set_type::container_from_end_iterator(testset.end()));
+ BOOST_TEST (testset == avl_set_type::container_from_end_iterator(testset.cend()));
+}
+
+template<class VoidPointer, bool constant_time_size>
+class test_main_template
+{
+ public:
+ int operator()()
+ {
+ typedef testvalue<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);
+ for (int i = 0; i < 6; ++i)
+ data[i].value_ = random_init[i];
+
+ test_avl_set < typename detail::get_base_value_traits
+ < value_type
+ , typename value_type::avl_set_base_hook_t
+ >::type
+ >::test_all(data);
+ test_avl_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_
+ >
+ >::type
+ >::test_all(data);
+ return 0;
+ }
+};
+
+template<class VoidPointer>
+class test_main_template<VoidPointer, false>
+{
+ public:
+ int operator()()
+ {
+ typedef testvalue<VoidPointer, false> value_type;
+ static const int random_init[6] = { 3, 2, 4, 1, 5, 2 };
+ std::vector<testvalue<VoidPointer, false> > data (6);
+ for (int i = 0; i < 6; ++i)
+ data[i].value_ = random_init[i];
+
+ test_avl_set < typename detail::get_base_value_traits
+ < value_type
+ , typename value_type::avl_set_base_hook_t
+ >::type
+ >::test_all(data);
+
+ test_avl_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_
+ >
+ >::type
+ >::test_all(data);
+
+ test_avl_set < typename detail::get_base_value_traits
+ < value_type
+ , typename value_type::avl_set_auto_base_hook_t
+ >::type
+ >::test_all(data);
+
+ test_avl_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_
+ >
+ >::type
+ >::test_all(data);
+
+ return 0;
+ }
+};
+
+int main( int, char* [] )
+{
+ test_main_template<void*, false>()();
+ test_main_template<smart_ptr<void>, false>()();
+ test_main_template<void*, true>()();
+ test_main_template<smart_ptr<void>, true>()();
+ return boost::report_errors();
+}
+#include <boost/intrusive/detail/config_end.hpp>
Modified: trunk/libs/intrusive/test/itestvalue.hpp
==============================================================================
--- trunk/libs/intrusive/test/itestvalue.hpp (original)
+++ trunk/libs/intrusive/test/itestvalue.hpp 2007-10-30 03:02:10 EDT (Tue, 30 Oct 2007)
@@ -19,6 +19,7 @@
#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/options.hpp>
#include <boost/functional/hash.hpp>
#include "smart_ptr.hpp"
@@ -61,6 +62,22 @@
{ typedef splay_set_member_hook<link_mode<auto_unlink>, 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; };
@@ -114,6 +131,8 @@
, set_auto_base_hook_type<VoidPointer>::type
, splay_set_base_hook_type<VoidPointer>::type
, splay_set_auto_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
@@ -131,6 +150,11 @@
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 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;
@@ -154,6 +178,10 @@
splay_set_member_hook_t splay_set_node_;
splay_set_auto_member_hook_t splay_set_auto_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_;
@@ -196,6 +224,11 @@
this->splay_set_node_ = src.splay_set_node_;
this->splay_set_auto_node_ = src.splay_set_auto_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_;
@@ -229,6 +262,12 @@
splay_set_node_.swap_nodes(other.splay_set_node_);
splay_set_auto_node_.swap_nodes(other.splay_set_auto_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);
Modified: trunk/libs/intrusive/test/smart_ptr.hpp
==============================================================================
--- trunk/libs/intrusive/test/smart_ptr.hpp (original)
+++ trunk/libs/intrusive/test/smart_ptr.hpp 2007-10-30 03:02:10 EDT (Tue, 30 Oct 2007)
@@ -12,6 +12,8 @@
#define BOOST_INTRUSIVE_SMART_PTR_HPP
#include <boost/iterator.hpp>
+#include <boost/intrusive/pointer_plus_bit.hpp>
+#include <boost/intrusive/pointer_plus_2_bits.hpp>
#if (defined _MSC_VER) && (_MSC_VER >= 1200)
# pragma once
@@ -343,4 +345,78 @@
} //namespace intrusive {
} //namespace boost {
+namespace boost{
+
+//This is to support embedding a bit in the pointer
+//for intrusive containers, saving space
+namespace intrusive {
+
+template<std::size_t N>
+struct has_pointer_plus_bit<smart_ptr<void>, N>
+{
+ static const bool value = has_pointer_plus_bit<void*, N>::value;
+};
+
+//Specialization
+template<class T>
+struct pointer_plus_bit<smart_ptr<T> >
+{
+ typedef smart_ptr<T> pointer;
+
+ static pointer get_pointer(const pointer &n)
+ { return pointer_plus_bit<T*>::get_pointer(n.get()); }
+
+ static void set_pointer(pointer &n, pointer p)
+ {
+ T *raw_n = n.get();
+ pointer_plus_bit<T*>::set_pointer(raw_n, p.get());
+ n = raw_n;
+ }
+
+ static bool get_bit(const pointer &n)
+ { return pointer_plus_bit<T*>::get_bit(n.get()); }
+
+ static void set_bit(pointer &n, bool c)
+ {
+ T *raw_n = n.get();
+ pointer_plus_bit<T*>::set_bit(raw_n, c);
+ n = raw_n;
+ }
+};
+
+template<std::size_t N>
+struct has_pointer_plus_2_bits<smart_ptr<void>, N>
+{
+ static const bool value = has_pointer_plus_2_bits<void*, N>::value;
+};
+
+template<class T>
+struct pointer_plus_2_bits<smart_ptr<T> >
+{
+ typedef smart_ptr<T> pointer;
+
+ static pointer get_pointer(const pointer &n)
+ { return pointer_plus_2_bits<T*>::get_pointer(n.get()); }
+
+ static void set_pointer(pointer &n, pointer p)
+ {
+ T *raw_n = n.get();
+ pointer_plus_2_bits<T*>::set_pointer(raw_n, p.get());
+ n = raw_n;
+ }
+
+ static std::size_t get_bits(const pointer &n)
+ { return pointer_plus_2_bits<T*>::get_bits(n.get()); }
+
+ static void set_bits(pointer &n, std::size_t c)
+ {
+ T *raw_n = n.get();
+ pointer_plus_2_bits<T*>::set_bits(raw_n, c);
+ n = raw_n;
+ }
+};
+
+} //namespace intrusive
+} //namespace boost{
+
#endif //#ifndef BOOST_INTRUSIVE_SMART_PTR_HPP
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk