libs/intrusive/test/treap_set_test.cpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga  2006-2013.
   4 //
   5 // Distributed under the Boost Software License, Version 1.0.
   6 //    (See accompanying file LICENSE_1_0.txt or copy at
   7 //          http://www.boost.org/LICENSE_1_0.txt)
   8 //
   9 // See http://www.boost.org/libs/intrusive for documentation.
  10 //
  11 /////////////////////////////////////////////////////////////////////////////
  12 #include <boost/intrusive/treap_set.hpp>
  13 #include "itestvalue.hpp"
  14 #include "bptr_value.hpp"
  15 #include "smart_ptr.hpp"
  16 #include "generic_set_test.hpp"
  17
  18 namespace boost { namespace intrusive { namespace test {
  19
  20 #if !defined (BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
  21 template<class T, class O1, class O2, class O3, class O4, class O5>
  22 #else
  23 template<class T, class ...Options>
  24 #endif
  25 struct has_insert_before<boost::intrusive::treap_set<T,
  26    #if !defined (BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
  27    O1, O2, O3, O4, O5
  28    #else
  29    Options...
  30    #endif
  31 > >
  32 {
  33    static const bool value = true;
  34 };
  35
  36 #if !defined (BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
  37 template<class T, class O1, class O2, class O3, class O4, class O5>
  38 #else
  39 template<class T, class ...Options>
  40 #endif
  41 struct is_treap<boost::intrusive::treap_set<T,
  42    #if !defined (BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
  43    O1, O2, O3, O4, O5
  44    #else
  45    Options...
  46    #endif
  47 > >
  48 {
  49    static const bool value = true;
  50 };
  51
  52 }}}
  53
  54
  55 using namespace boost::intrusive;
  56
  57 struct my_tag;
  58
  59 template<class VoidPointer>
  60 struct hooks
  61 {
  62    typedef bs_set_base_hook<void_pointer<VoidPointer> >     base_hook_type;
  63    typedef bs_set_base_hook
  64       < void_pointer<VoidPointer>
  65       , tag<my_tag> >                                       auto_base_hook_type;
  66    typedef bs_set_member_hook
  67       < void_pointer<VoidPointer> >                         member_hook_type;
  68    typedef bs_set_member_hook
  69       < void_pointer<VoidPointer> >                         auto_member_hook_type;
  70    typedef nonhook_node_member< tree_node_traits< VoidPointer >,
  71                                 treap_algorithms
  72                               > nonhook_node_member_type;
  73 };
  74
  75 // container generator with void node allocator
  76 template < bool Default_Holder >
  77 struct GetContainer_With_Holder
  78 {
  79 template< class ValueType
  80         , class Option1 =void
  81         , class Option2 =void
  82         , class Option3 =void
  83         >
  84 struct GetContainer
  85 {
  86    typedef boost::intrusive::treap_set
  87       < ValueType
  88       , Option1
  89       , Option2
  90       , Option3
  91       > type;
  92 };
  93 };
  94
  95 // container generator with standard (non-void) node allocator
  96 template <>
  97 struct GetContainer_With_Holder< false >
  98 {
  99 template< class ValueType
 100         , class Option1 =void
 101         , class Option2 =void
 102         , class Option3 =void
 103         >
 104 struct GetContainer
 105 {
 106    // extract node type through options->value_traits->node_traits->node
 107    typedef typename pack_options< treap_defaults, Option1, Option2, Option3 >::type packed_options;
 108    typedef typename detail::get_value_traits< ValueType, typename packed_options::proto_value_traits>::type value_traits;
 109    typedef typename value_traits::node_traits::node node;
 110
 111    typedef boost::intrusive::treap_set
 112       < ValueType
 113       , Option1
 114       , Option2
 115       , Option3
 116       , header_holder_type< pointer_holder< node > >
 117       > type;
 118 };
 119 };
 120
 121 template<class VoidPointer, bool constant_time_size, bool Default_Holder>
 122 class test_main_template
 123 {
 124    public:
 125    int operator()()
 126    {
 127       using namespace boost::intrusive;
 128       typedef testvalue<hooks<VoidPointer> , constant_time_size> value_type;
 129
 130       test::test_generic_set < typename detail::get_base_value_traits
 131                   < value_type
 132                   , typename hooks<VoidPointer>::base_hook_type
 133                   >::type
 134                 , GetContainer_With_Holder< Default_Holder >::template GetContainer
 135                 >::test_all();
 136       test::test_generic_set < typename detail::get_member_value_traits
 137                   < member_hook< value_type
 138                                , typename hooks<VoidPointer>::member_hook_type
 139                                , &value_type::node_
 140                                >
 141                   >::type
 142                 , GetContainer_With_Holder< Default_Holder >::template GetContainer
 143                 >::test_all();
 144       test::test_generic_set < nonhook_node_member_value_traits< value_type,
 145                                                                  typename hooks<VoidPointer>::nonhook_node_member_type,
 146                                                                  &value_type::nhn_member_,
 147                                                                  safe_link
 148                                                                >,
 149                                GetContainer_With_Holder< Default_Holder >::template GetContainer
 150                              >::test_all();
 151       return 0;
 152    }
 153 };
 154
 155 template<class VoidPointer, bool Default_Holder>
 156 class test_main_template<VoidPointer, false, Default_Holder>
 157 {
 158    public:
 159    int operator()()
 160    {
 161       using namespace boost::intrusive;
 162       typedef testvalue<hooks<VoidPointer> , false> value_type;
 163
 164       test::test_generic_set < typename detail::get_base_value_traits
 165                   < value_type
 166                   , typename hooks<VoidPointer>::base_hook_type
 167                   >::type
 168                 , GetContainer_With_Holder< Default_Holder >::template GetContainer
 169                 >::test_all();
 170
 171       test::test_generic_set < typename detail::get_member_value_traits
 172                   < member_hook< value_type
 173                                , typename hooks<VoidPointer>::member_hook_type
 174                                , &value_type::node_
 175                                >
 176                   >::type
 177                 , GetContainer_With_Holder< Default_Holder >::template GetContainer
 178                 >::test_all();
 179
 180       test::test_generic_set < typename detail::get_base_value_traits
 181                   < value_type
 182                   , typename hooks<VoidPointer>::auto_base_hook_type
 183                   >::type
 184                 , GetContainer_With_Holder< Default_Holder >::template GetContainer
 185                 >::test_all();
 186
 187       test::test_generic_set < typename detail::get_member_value_traits
 188                   < member_hook< value_type
 189                                , typename hooks<VoidPointer>::auto_member_hook_type
 190                                , &value_type::auto_node_
 191                                >
 192                   >::type
 193                 , GetContainer_With_Holder< Default_Holder >::template GetContainer
 194                 >::test_all();
 195
 196       return 0;
 197    }
 198 };
 199
 200 // container generator which ignores further parametrization, except for compare option
 201 template < typename Value_Traits, bool ConstantTimeSize, typename HeaderHolder >
 202 struct Get_Preset_Container
 203 {
 204     template < class
 205              , class Option1 = void
 206              , class Option2 = void
 207              , class Option3 = void
 208              >
 209     struct GetContainer
 210     {
 211         // ignore further paramatrization except for the compare option
 212         // notably ignore the size option (use preset)
 213         typedef typename pack_options< treap_defaults, Option1, Option2, Option3 >::type packed_options;
 214         typedef typename packed_options::compare compare_option;
 215
 216         typedef boost::intrusive::treap_set< typename Value_Traits::value_type,
 217                                            value_traits< Value_Traits >,
 218                                            constant_time_size< ConstantTimeSize >,
 219                                            compare< compare_option >,
 220                                            header_holder_type< HeaderHolder >
 221                                          > type;
 222     };
 223 };
 224
 225 template < bool ConstantTimeSize >
 226 struct test_main_template_bptr
 227 {
 228     void operator () ()
 229     {
 230         typedef BPtr_Value value_type;
 231         typedef BPtr_Value_Traits< Tree_BPtr_Node_Traits > value_traits;
 232         typedef bounded_allocator< value_type > allocator_type;
 233
 234         allocator_type::init();
 235         test::test_generic_set< value_traits,
 236                                 Get_Preset_Container< value_traits, ConstantTimeSize,
 237                                                       bounded_pointer_holder< value_type > >::template GetContainer
 238                               >::test_all();
 239         assert(allocator_type::is_clear());
 240         allocator_type::destroy();
 241     }
 242 };
 243
 244 int main()
 245 {
 246    // test (plain/smart pointers) x (nonconst/const size) x (void node allocator)
 247    test_main_template<void*, false, true>()();
 248    test_main_template<boost::intrusive::smart_ptr<void>, false, true>()();
 249    test_main_template<void*, true, true>()();
 250    test_main_template<boost::intrusive::smart_ptr<void>, true, true>()();
 251    // test (bounded pointers) x (nonconst/const size) x (special node allocator)
 252    test_main_template_bptr< true >()();
 253    test_main_template_bptr< false >()();
 254
 255    return boost::report_errors();
 256 }