boost/intrusive/options.hpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga  2007-2008
   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
  13 #ifndef BOOST_INTRUSIVE_OPTIONS_HPP
  14 #define BOOST_INTRUSIVE_OPTIONS_HPP
  15
  16 #include <boost/intrusive/detail/config_begin.hpp>
  17 #include <boost/intrusive/intrusive_fwd.hpp>
  18 #include <boost/intrusive/link_mode.hpp>
  19 #include <boost/intrusive/detail/mpl.hpp>
  20 #include <boost/intrusive/detail/utilities.hpp>
  21 #include <boost/static_assert.hpp>
  22
  23
  24 namespace boost {
  25 namespace intrusive {
  26
  27 /// @cond
  28
  29 struct default_tag;
  30 struct member_tag;
  31
  32 namespace detail{
  33
  34 struct default_hook_tag{};
  35
  36 #define BOOST_INTRUSIVE_DEFAULT_HOOK_MARKER_DEFINITION(BOOST_INTRUSIVE_DEFAULT_HOOK_MARKER) \
  37 struct BOOST_INTRUSIVE_DEFAULT_HOOK_MARKER : public default_hook_tag\
  38 {\
  39    template <class T>\
  40    struct apply\
  41    {  typedef typename T::BOOST_INTRUSIVE_DEFAULT_HOOK_MARKER type;  };\
  42 }\
  43
  44 BOOST_INTRUSIVE_DEFAULT_HOOK_MARKER_DEFINITION(default_list_hook);
  45 BOOST_INTRUSIVE_DEFAULT_HOOK_MARKER_DEFINITION(default_slist_hook);
  46 BOOST_INTRUSIVE_DEFAULT_HOOK_MARKER_DEFINITION(default_set_hook);
  47 BOOST_INTRUSIVE_DEFAULT_HOOK_MARKER_DEFINITION(default_uset_hook);
  48 BOOST_INTRUSIVE_DEFAULT_HOOK_MARKER_DEFINITION(default_avl_set_hook);
  49 BOOST_INTRUSIVE_DEFAULT_HOOK_MARKER_DEFINITION(default_splay_set_hook);
  50 BOOST_INTRUSIVE_DEFAULT_HOOK_MARKER_DEFINITION(default_bs_set_hook);
  51
  52 #undef BOOST_INTRUSIVE_DEFAULT_HOOK_MARKER_DEFINITION
  53
  54 template <class ValueTraits>
  55 struct eval_value_traits
  56 {
  57    typedef typename ValueTraits::value_traits type;
  58 };
  59
  60 template <class T>
  61 struct external_bucket_traits_is_true
  62 {
  63    static const bool value = external_bucket_traits_bool<T>::value == 3;
  64 };
  65
  66 template <class BucketTraits>
  67 struct eval_bucket_traits
  68 {
  69    typedef typename BucketTraits::bucket_traits type;
  70 };
  71
  72 template <class T, class BaseHook>
  73 struct concrete_hook_base_value_traits
  74 {
  75    typedef typename BaseHook::boost_intrusive_tags tags;
  76    typedef detail::base_hook_traits
  77       < T
  78       , typename tags::node_traits
  79       , tags::link_mode
  80       , typename tags::tag
  81       , tags::hook_type> type;
  82 };
  83
  84 template <class BaseHook>
  85 struct concrete_hook_base_node_traits
  86 {  typedef typename BaseHook::boost_intrusive_tags::node_traits type;  };
  87
  88 template <class T, class BaseHook>
  89 struct any_hook_base_value_traits
  90 {
  91    typedef typename BaseHook::boost_intrusive_tags tags;
  92    typedef detail::base_hook_traits
  93       < T
  94       , typename BaseHook::node_traits
  95       , tags::link_mode
  96       , typename tags::tag
  97       , tags::hook_type> type;
  98 };
  99
 100 template <class BaseHook>
 101 struct any_hook_base_node_traits
 102 {  typedef typename BaseHook::node_traits type; };
 103
 104 template<class T, class BaseHook>
 105 struct get_base_value_traits
 106 {
 107    typedef typename detail::eval_if_c
 108       < internal_any_hook_bool_is_true<BaseHook>::value
 109       , any_hook_base_value_traits<T, BaseHook>
 110       , concrete_hook_base_value_traits<T, BaseHook>
 111       >::type type;
 112 };
 113
 114 template<class BaseHook>
 115 struct get_base_node_traits
 116 {
 117    typedef typename detail::eval_if_c
 118       < internal_any_hook_bool_is_true<BaseHook>::value
 119       , any_hook_base_node_traits<BaseHook>
 120       , concrete_hook_base_node_traits<BaseHook>
 121       >::type type;
 122 };
 123
 124 template<class T, class MemberHook>
 125 struct get_member_value_traits
 126 {
 127    typedef typename MemberHook::member_value_traits type;
 128 };
 129
 130 template<class MemberHook>
 131 struct get_member_node_traits
 132 {
 133    typedef typename MemberHook::member_value_traits::node_traits type;
 134 };
 135
 136 template<class T, class SupposedValueTraits>
 137 struct get_value_traits
 138 {
 139    typedef typename detail::eval_if_c
 140       <detail::is_convertible<SupposedValueTraits*, detail::default_hook_tag*>::value
 141       ,detail::apply<SupposedValueTraits, T>
 142       ,detail::identity<SupposedValueTraits>
 143    >::type supposed_value_traits;
 144    //...if it's a default hook
 145    typedef typename detail::eval_if_c
 146       < internal_base_hook_bool_is_true<supposed_value_traits>::value
 147       //...get it's internal value traits using
 148       //the provided T value type.
 149       , get_base_value_traits<T, supposed_value_traits>
 150       //...else use it's internal value traits tag
 151       //(member hooks and custom value traits are in this group)
 152       , detail::eval_if_c
 153          < internal_member_value_traits<supposed_value_traits>::value
 154          , get_member_value_traits<T, supposed_value_traits>
 155          , detail::identity<supposed_value_traits>
 156          >
 157       >::type type;
 158 };
 159
 160 template<class ValueTraits>
 161 struct get_explicit_node_traits
 162 {
 163    typedef typename ValueTraits::node_traits type;
 164 };
 165
 166 template<class SupposedValueTraits>
 167 struct get_node_traits
 168 {
 169    typedef SupposedValueTraits supposed_value_traits;
 170    //...if it's a base hook
 171    typedef typename detail::eval_if_c
 172       < internal_base_hook_bool_is_true<supposed_value_traits>::value
 173       //...get it's internal value traits using
 174       //the provided T value type.
 175       , get_base_node_traits<supposed_value_traits>
 176       //...else use it's internal value traits tag
 177       //(member hooks and custom value traits are in this group)
 178       , detail::eval_if_c
 179          < internal_member_value_traits<supposed_value_traits>::value
 180          , get_member_node_traits<supposed_value_traits>
 181          , get_explicit_node_traits<supposed_value_traits>
 182          >
 183       >::type type;
 184 };
 185
 186 }  //namespace detail{
 187
 188
 189 //!This type indicates that no option is being used
 190 //!and that the default options should be used
 191 struct none
 192 {
 193     template<class Base>
 194     struct pack : Base
 195     { };
 196 };
 197
 198 /// @endcond
 199
 200 //!This option setter specifies if the intrusive
 201 //!container stores its size as a member to
 202 //!obtain constant-time size() member.
 203 template<bool Enabled>
 204 struct constant_time_size
 205 {
 206 /// @cond
 207     template<class Base>
 208     struct pack : Base
 209     {
 210         static const bool constant_time_size = Enabled;
 211     };
 212 /// @endcond
 213 };
 214
 215 //!This option setter specifies the type that
 216 //!the container will use to store its size.
 217 template<class SizeType>
 218 struct size_type
 219 {
 220 /// @cond
 221     template<class Base>
 222     struct pack : Base
 223     {
 224         typedef SizeType size_type;
 225     };
 226 /// @endcond
 227 };
 228
 229 //!This option setter specifies the strict weak ordering
 230 //!comparison functor for the value type
 231 template<class Compare>
 232 struct compare
 233 {
 234 /// @cond
 235     template<class Base>
 236     struct pack : Base
 237     {
 238         typedef Compare compare;
 239     };
 240 /// @endcond
 241 };
 242
 243 //!This option setter for scapegoat containers specifies if
 244 //!the intrusive scapegoat container should use a non-variable
 245 //!alpha value that does not need floating-point operations.
 246 //!
 247 //!If activated, the fixed alpha value is 1/sqrt(2). This
 248 //!option also saves some space in the container since
 249 //!the alpha value and some additional data does not need
 250 //!to be stored in the container.
 251 //!
 252 //!If the user only needs an alpha value near 1/sqrt(2), this
 253 //!option also improves performance since avoids logarithm
 254 //!and division operations when rebalancing the tree.
 255 template<bool Enabled>
 256 struct floating_point
 257 {
 258 /// @cond
 259     template<class Base>
 260     struct pack : Base
 261     {
 262         static const bool floating_point = Enabled;
 263     };
 264 /// @endcond
 265 };
 266
 267 //!This option setter specifies the equality
 268 //!functor for the value type
 269 template<class Equal>
 270 struct equal
 271 {
 272 /// @cond
 273     template<class Base>
 274     struct pack : Base
 275     {
 276         typedef Equal equal;
 277     };
 278 /// @endcond
 279 };
 280
 281 //!This option setter specifies the equality
 282 //!functor for the value type
 283 template<class Priority>
 284 struct priority
 285 {
 286 /// @cond
 287     template<class Base>
 288     struct pack : Base
 289     {
 290         typedef Priority priority;
 291     };
 292 /// @endcond
 293 };
 294
 295 //!This option setter specifies the hash
 296 //!functor for the value type
 297 template<class Hash>
 298 struct hash
 299 {
 300 /// @cond
 301     template<class Base>
 302     struct pack : Base
 303     {
 304         typedef Hash hash;
 305     };
 306 /// @endcond
 307 };
 308
 309 //!This option setter specifies the relationship between the type
 310 //!to be managed by the container (the value type) and the node to be
 311 //!used in the node algorithms. It also specifies the linking policy.
 312 template<typename ValueTraits>
 313 struct value_traits
 314 {
 315 /// @cond
 316     template<class Base>
 317     struct pack : Base
 318     {
 319         typedef ValueTraits value_traits;
 320     };
 321 /// @endcond
 322 };
 323
 324 //!This option setter specifies the member hook the
 325 //!container must use.
 326 template< typename Parent
 327         , typename MemberHook
 328         , MemberHook Parent::* PtrToMember>
 329 struct member_hook
 330 {
 331 /// @cond
 332    typedef detail::member_hook_traits
 333       < Parent
 334       , MemberHook
 335       , PtrToMember
 336       > member_value_traits;
 337    template<class Base>
 338    struct pack : Base
 339    {
 340       typedef member_value_traits value_traits;
 341    };
 342 /// @endcond
 343 };
 344
 345
 346 //!This option setter specifies that the container
 347 //!must use the specified base hook
 348 template<typename BaseHook>
 349 struct base_hook
 350 {
 351 /// @cond
 352    template<class Base>
 353    struct pack : Base
 354    {
 355       typedef BaseHook value_traits;
 356    };
 357 /// @endcond
 358 };
 359
 360 //!This option setter specifies the type of
 361 //!a void pointer. This will instruct the hook
 362 //!to use this type of pointer instead of the
 363 //!default one
 364 template<class VoidPointer>
 365 struct void_pointer
 366 {
 367 /// @cond
 368    template<class Base>
 369    struct pack : Base
 370    {
 371       typedef VoidPointer void_pointer;
 372    };
 373 /// @endcond
 374 };
 375
 376 //!This option setter specifies the type of
 377 //!the tag of a base hook. A type cannot have two
 378 //!base hooks of the same type, so a tag can be used
 379 //!to differentiate two base hooks with otherwise same type
 380 template<class Tag>
 381 struct tag
 382 {
 383 /// @cond
 384    template<class Base>
 385    struct pack : Base
 386    {
 387       typedef Tag tag;
 388    };
 389 /// @endcond
 390 };
 391
 392 //!This option setter specifies the link mode
 393 //!(normal_link, safe_link or auto_unlink)
 394 template<link_mode_type LinkType>
 395 struct link_mode
 396 {
 397 /// @cond
 398    template<class Base>
 399    struct pack : Base
 400    {
 401       static const link_mode_type link_mode = LinkType;
 402    };
 403 /// @endcond
 404 };
 405
 406 //!This option setter specifies if the hook
 407 //!should be optimized for size instead of for speed.
 408 template<bool Enabled>
 409 struct optimize_size
 410 {
 411 /// @cond
 412    template<class Base>
 413    struct pack : Base
 414    {
 415       static const bool optimize_size = Enabled;
 416    };
 417 /// @endcond
 418 };
 419
 420 //!This option setter specifies if the list container should
 421 //!use a linear implementation instead of a circular one.
 422 template<bool Enabled>
 423 struct linear
 424 {
 425 /// @cond
 426    template<class Base>
 427    struct pack : Base
 428    {
 429       static const bool linear = Enabled;
 430    };
 431 /// @endcond
 432 };
 433
 434 //!This option setter specifies if the list container should
 435 //!use a linear implementation instead of a circular one.
 436 template<bool Enabled>
 437 struct cache_last
 438 {
 439 /// @cond
 440    template<class Base>
 441    struct pack : Base
 442    {
 443       static const bool cache_last = Enabled;
 444    };
 445 /// @endcond
 446 };
 447
 448 //!This option setter specifies the bucket traits
 449 //!class for unordered associative containers. When this option is specified,
 450 //!instead of using the default bucket traits, a user defined holder will be defined
 451 template<class BucketTraits>
 452 struct bucket_traits
 453 {
 454 /// @cond
 455    template<class Base>
 456    struct pack : Base
 457    {
 458       typedef BucketTraits bucket_traits;
 459    };
 460 /// @endcond
 461 };
 462
 463 //!This option setter specifies if the unordered hook
 464 //!should offer room to store the hash value.
 465 //!Storing the hash in the hook will speed up rehashing
 466 //!processes in applications where rehashing is frequent,
 467 //!rehashing might throw or the value is heavy to hash.
 468 template<bool Enabled>
 469 struct store_hash
 470 {
 471 /// @cond
 472     template<class Base>
 473     struct pack : Base
 474     {
 475         static const bool store_hash = Enabled;
 476     };
 477 /// @endcond
 478 };
 479
 480 //!This option setter specifies if the unordered hook
 481 //!should offer room to store another link to another node
 482 //!with the same key.
 483 //!Storing this link will speed up lookups and insertions on
 484 //!unordered_multiset containers with a great number of elements
 485 //!with the same key.
 486 template<bool Enabled>
 487 struct optimize_multikey
 488 {
 489 /// @cond
 490     template<class Base>
 491     struct pack : Base
 492     {
 493         static const bool optimize_multikey = Enabled;
 494     };
 495 /// @endcond
 496 };
 497
 498 //!This option setter specifies if the bucket array will be always power of two.
 499 //!This allows using masks instead of the default modulo operation to determine
 500 //!the bucket number from the hash value, leading to better performance.
 501 //!In debug mode, if power of two buckets mode is activated, the bucket length
 502 //!will be checked to through assertions to assure the bucket length is power of two.
 503 template<bool Enabled>
 504 struct power_2_buckets
 505 {
 506 /// @cond
 507    template<class Base>
 508    struct pack : Base
 509    {
 510       static const bool power_2_buckets = Enabled;
 511    };
 512 /// @endcond
 513 };
 514
 515 //!This option setter specifies if the container will cache a pointer to the first
 516 //!non-empty bucket so that begin() is always constant-time.
 517 //!This is specially helpful when we can have containers with a few elements
 518 //!but with big bucket arrays (that is, hashtables with low load factors).
 519 template<bool Enabled>
 520 struct cache_begin
 521 {
 522 /// @cond
 523    template<class Base>
 524    struct pack : Base
 525    {
 526       static const bool cache_begin = Enabled;
 527    };
 528 /// @endcond
 529 };
 530
 531
 532 //!This option setter specifies if the container will compare the hash value
 533 //!before comparing objects. This option can't be specified if store_hash<>
 534 //!is not true.
 535 //!This is specially helpful when we have containers with a high load factor.
 536 //!and the comparison function is much more expensive that comparing already
 537 //!stored hash values.
 538 template<bool Enabled>
 539 struct compare_hash
 540 {
 541 /// @cond
 542    template<class Base>
 543    struct pack : Base
 544    {
 545       static const bool compare_hash = Enabled;
 546    };
 547 /// @endcond
 548 };
 549
 550 //!This option setter specifies if the hash container will use incremental
 551 //!hashing. With incremental hashing the cost of hash table expansion is spread
 552 //!out across each hash table insertion operation, as opposed to be incurred all at once.
 553 //!Therefore linear hashing is well suited for interactive applications or real-time
 554 //!appplications where the worst-case insertion time of non-incremental hash containers
 555 //!(rehashing the whole bucket array) is not admisible.
 556 template<bool Enabled>
 557 struct incremental
 558 {
 559    /// @cond
 560    template<class Base>
 561    struct pack : Base
 562    {
 563       static const bool incremental = Enabled;
 564    };
 565    /// @endcond
 566 };
 567
 568 /// @cond
 569
 570 //To-do: pass to variadic templates
 571 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 572
 573 template<class Prev, class Next>
 574 struct do_pack
 575 {
 576    //Use "pack" member template to pack options
 577    typedef typename Next::template pack<Prev> type;
 578 };
 579
 580 template<class Prev>
 581 struct do_pack<Prev, none>
 582 {
 583    //Avoid packing "none" to shorten template names
 584    typedef Prev type;
 585 };
 586
 587 template
 588    < class DefaultOptions
 589    , class O1         = none
 590    , class O2         = none
 591    , class O3         = none
 592    , class O4         = none
 593    , class O5         = none
 594    , class O6         = none
 595    , class O7         = none
 596    , class O8         = none
 597    , class O9         = none
 598    , class O10        = none
 599    , class O11        = none
 600    >
 601 struct pack_options
 602 {
 603    // join options
 604    typedef
 605       typename do_pack
 606       <  typename do_pack
 607          <  typename do_pack
 608             <  typename do_pack
 609                <  typename do_pack
 610                   <  typename do_pack
 611                      <  typename do_pack
 612                         <  typename do_pack
 613                            <  typename do_pack
 614                               <  typename do_pack
 615                                  <  typename do_pack
 616                                     < DefaultOptions
 617                                     , O1
 618                                     >::type
 619                                  , O2
 620                                  >::type
 621                               , O3
 622                               >::type
 623                            , O4
 624                            >::type
 625                         , O5
 626                         >::type
 627                      , O6
 628                      >::type
 629                   , O7
 630                   >::type
 631                , O8
 632                >::type
 633             , O9
 634             >::type
 635          , O10
 636          >::type
 637       , O11
 638       >::type
 639    type;
 640 };
 641 #else
 642
 643 //index_tuple
 644 template<int... Indexes>
 645 struct index_tuple{};
 646
 647 //build_number_seq
 648 template<std::size_t Num, typename Tuple = index_tuple<> >
 649 struct build_number_seq;
 650
 651 template<std::size_t Num, int... Indexes>
 652 struct build_number_seq<Num, index_tuple<Indexes...> >
 653    : build_number_seq<Num - 1, index_tuple<Indexes..., sizeof...(Indexes)> >
 654 {};
 655
 656 template<int... Indexes>
 657 struct build_number_seq<0, index_tuple<Indexes...> >
 658 {  typedef index_tuple<Indexes...> type;  };
 659
 660 template<class ...Types>
 661 struct typelist
 662 {};
 663
 664 //invert_typelist
 665 template<class T>
 666 struct invert_typelist;
 667
 668 template<int I, typename Tuple>
 669 struct typelist_element;
 670
 671 template<int I, typename Head, typename... Tail>
 672 struct typelist_element<I, typelist<Head, Tail...> >
 673 {
 674    typedef typename typelist_element<I-1, typelist<Tail...> >::type type;
 675 };
 676
 677 template<typename Head, typename... Tail>
 678 struct typelist_element<0, typelist<Head, Tail...> >
 679 {
 680    typedef Head type;
 681 };
 682
 683 template<int ...Ints, class ...Types>
 684 typelist<typename typelist_element<(sizeof...(Types) - 1) - Ints, typelist<Types...> >::type...>
 685    inverted_typelist(index_tuple<Ints...>, typelist<Types...>)
 686 {
 687    return typelist<typename typelist_element<(sizeof...(Types) - 1) - Ints, typelist<Types...> >::type...>();
 688 }
 689
 690 //sizeof_typelist
 691 template<class Typelist>
 692 struct sizeof_typelist;
 693
 694 template<class ...Types>
 695 struct sizeof_typelist< typelist<Types...> >
 696 {
 697    static const std::size_t value = sizeof...(Types);
 698 };
 699
 700 //invert_typelist_impl
 701 template<class Typelist, class Indexes>
 702 struct invert_typelist_impl;
 703
 704
 705 template<class Typelist, int ...Ints>
 706 struct invert_typelist_impl< Typelist, index_tuple<Ints...> >
 707 {
 708    static const std::size_t last_idx = sizeof_typelist<Typelist>::value - 1;
 709    typedef typelist
 710       <typename typelist_element<last_idx - Ints, Typelist>::type...> type;
 711 };
 712
 713 template<class Typelist, int Int>
 714 struct invert_typelist_impl< Typelist, index_tuple<Int> >
 715 {
 716    typedef Typelist type;
 717 };
 718
 719 template<class Typelist>
 720 struct invert_typelist_impl< Typelist, index_tuple<> >
 721 {
 722    typedef Typelist type;
 723 };
 724
 725 //invert_typelist
 726 template<class Typelist>
 727 struct invert_typelist;
 728
 729 template<class ...Types>
 730 struct invert_typelist< typelist<Types...> >
 731 {
 732    typedef typelist<Types...> typelist_t;
 733    typedef typename build_number_seq<sizeof...(Types)>::type indexes_t;
 734    typedef typename invert_typelist_impl<typelist_t, indexes_t>::type type;
 735 };
 736
 737 //Do pack
 738 template<class Typelist>
 739 struct do_pack;
 740
 741 template<>
 742 struct do_pack<typelist<> >;
 743
 744 template<class Prev>
 745 struct do_pack<typelist<Prev> >
 746 {
 747    typedef Prev type;
 748 };
 749
 750 template<class Prev, class Last>
 751 struct do_pack<typelist<Prev, Last> >
 752 {
 753    typedef typename Prev::template pack<Last> type;
 754 };
 755
 756 template<class Prev, class ...Others>
 757 struct do_pack<typelist<Prev, Others...> >
 758 {
 759    typedef typename Prev::template pack
 760       <typename do_pack<typelist<Others...>>::type> type;
 761 };
 762
 763
 764 template<class ...Options>
 765 struct pack_options
 766 {
 767    typedef typelist<Options...> typelist_t;
 768    typedef typename invert_typelist<typelist_t>::type inverted_typelist;
 769    typedef typename do_pack<inverted_typelist>::type type;
 770 };
 771
 772 #endif
 773
 774 struct hook_defaults
 775    :  public pack_options
 776       < none
 777       , void_pointer<void*>
 778       , link_mode<safe_link>
 779       , tag<default_tag>
 780       , optimize_size<false>
 781       , store_hash<false>
 782       , linear<false>
 783       , optimize_multikey<false>
 784       >::type
 785 {};
 786
 787 /// @endcond
 788
 789 }  //namespace intrusive {
 790 }  //namespace boost {
 791
 792 #include <boost/intrusive/detail/config_end.hpp>
 793
 794 #endif   //#ifndef BOOST_INTRUSIVE_OPTIONS_HPP