libs/intrusive/test/avl_set_test.cpp

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