git.sesse.net Git - casparcg/blob - dependencies/boost/boost/intrusive/options.hpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga  2007-2009
   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 the function object that will
 347 //!be used to convert between values to be inserted in a container
 348 //!and the hook to be used for that purpose.
 349 template< typename Functor>
 350 struct function_hook
 351 {
 352 /// @cond
 353    typedef detail::function_hook_traits
 354       <Functor> function_value_traits;
 355    template<class Base>
 356    struct pack : Base
 357    {
 358       typedef function_value_traits value_traits;
 359    };
 360 /// @endcond
 361 };
 362
 363
 364 //!This option setter specifies that the container
 365 //!must use the specified base hook
 366 template<typename BaseHook>
 367 struct base_hook
 368 {
 369 /// @cond
 370    template<class Base>
 371    struct pack : Base
 372    {
 373       typedef BaseHook value_traits;
 374    };
 375 /// @endcond
 376 };
 377
 378 //!This option setter specifies the type of
 379 //!a void pointer. This will instruct the hook
 380 //!to use this type of pointer instead of the
 381 //!default one
 382 template<class VoidPointer>
 383 struct void_pointer
 384 {
 385 /// @cond
 386    template<class Base>
 387    struct pack : Base
 388    {
 389       typedef VoidPointer void_pointer;
 390    };
 391 /// @endcond
 392 };
 393
 394 //!This option setter specifies the type of
 395 //!the tag of a base hook. A type cannot have two
 396 //!base hooks of the same type, so a tag can be used
 397 //!to differentiate two base hooks with otherwise same type
 398 template<class Tag>
 399 struct tag
 400 {
 401 /// @cond
 402    template<class Base>
 403    struct pack : Base
 404    {
 405       typedef Tag tag;
 406    };
 407 /// @endcond
 408 };
 409
 410 //!This option setter specifies the link mode
 411 //!(normal_link, safe_link or auto_unlink)
 412 template<link_mode_type LinkType>
 413 struct link_mode
 414 {
 415 /// @cond
 416    template<class Base>
 417    struct pack : Base
 418    {
 419       static const link_mode_type link_mode = LinkType;
 420    };
 421 /// @endcond
 422 };
 423
 424 //!This option setter specifies if the hook
 425 //!should be optimized for size instead of for speed.
 426 template<bool Enabled>
 427 struct optimize_size
 428 {
 429 /// @cond
 430    template<class Base>
 431    struct pack : Base
 432    {
 433       static const bool optimize_size = Enabled;
 434    };
 435 /// @endcond
 436 };
 437
 438 //!This option setter specifies if the list container should
 439 //!use a linear implementation instead of a circular one.
 440 template<bool Enabled>
 441 struct linear
 442 {
 443 /// @cond
 444    template<class Base>
 445    struct pack : Base
 446    {
 447       static const bool linear = Enabled;
 448    };
 449 /// @endcond
 450 };
 451
 452 //!This option setter specifies if the list container should
 453 //!use a linear implementation instead of a circular one.
 454 template<bool Enabled>
 455 struct cache_last
 456 {
 457 /// @cond
 458    template<class Base>
 459    struct pack : Base
 460    {
 461       static const bool cache_last = Enabled;
 462    };
 463 /// @endcond
 464 };
 465
 466 //!This option setter specifies the bucket traits
 467 //!class for unordered associative containers. When this option is specified,
 468 //!instead of using the default bucket traits, a user defined holder will be defined
 469 template<class BucketTraits>
 470 struct bucket_traits
 471 {
 472 /// @cond
 473    template<class Base>
 474    struct pack : Base
 475    {
 476       typedef BucketTraits bucket_traits;
 477    };
 478 /// @endcond
 479 };
 480
 481 //!This option setter specifies if the unordered hook
 482 //!should offer room to store the hash value.
 483 //!Storing the hash in the hook will speed up rehashing
 484 //!processes in applications where rehashing is frequent,
 485 //!rehashing might throw or the value is heavy to hash.
 486 template<bool Enabled>
 487 struct store_hash
 488 {
 489 /// @cond
 490     template<class Base>
 491     struct pack : Base
 492     {
 493         static const bool store_hash = Enabled;
 494     };
 495 /// @endcond
 496 };
 497
 498 //!This option setter specifies if the unordered hook
 499 //!should offer room to store another link to another node
 500 //!with the same key.
 501 //!Storing this link will speed up lookups and insertions on
 502 //!unordered_multiset containers with a great number of elements
 503 //!with the same key.
 504 template<bool Enabled>
 505 struct optimize_multikey
 506 {
 507 /// @cond
 508     template<class Base>
 509     struct pack : Base
 510     {
 511         static const bool optimize_multikey = Enabled;
 512     };
 513 /// @endcond
 514 };
 515
 516 //!This option setter specifies if the bucket array will be always power of two.
 517 //!This allows using masks instead of the default modulo operation to determine
 518 //!the bucket number from the hash value, leading to better performance.
 519 //!In debug mode, if power of two buckets mode is activated, the bucket length
 520 //!will be checked to through assertions to assure the bucket length is power of two.
 521 template<bool Enabled>
 522 struct power_2_buckets
 523 {
 524 /// @cond
 525    template<class Base>
 526    struct pack : Base
 527    {
 528       static const bool power_2_buckets = Enabled;
 529    };
 530 /// @endcond
 531 };
 532
 533 //!This option setter specifies if the container will cache a pointer to the first
 534 //!non-empty bucket so that begin() is always constant-time.
 535 //!This is specially helpful when we can have containers with a few elements
 536 //!but with big bucket arrays (that is, hashtables with low load factors).
 537 template<bool Enabled>
 538 struct cache_begin
 539 {
 540 /// @cond
 541    template<class Base>
 542    struct pack : Base
 543    {
 544       static const bool cache_begin = Enabled;
 545    };
 546 /// @endcond
 547 };
 548
 549
 550 //!This option setter specifies if the container will compare the hash value
 551 //!before comparing objects. This option can't be specified if store_hash<>
 552 //!is not true.
 553 //!This is specially helpful when we have containers with a high load factor.
 554 //!and the comparison function is much more expensive that comparing already
 555 //!stored hash values.
 556 template<bool Enabled>
 557 struct compare_hash
 558 {
 559 /// @cond
 560    template<class Base>
 561    struct pack : Base
 562    {
 563       static const bool compare_hash = Enabled;
 564    };
 565 /// @endcond
 566 };
 567
 568 //!This option setter specifies if the hash container will use incremental
 569 //!hashing. With incremental hashing the cost of hash table expansion is spread
 570 //!out across each hash table insertion operation, as opposed to be incurred all at once.
 571 //!Therefore linear hashing is well suited for interactive applications or real-time
 572 //!appplications where the worst-case insertion time of non-incremental hash containers
 573 //!(rehashing the whole bucket array) is not admisible.
 574 template<bool Enabled>
 575 struct incremental
 576 {
 577    /// @cond
 578    template<class Base>
 579    struct pack : Base
 580    {
 581       static const bool incremental = Enabled;
 582    };
 583    /// @endcond
 584 };
 585
 586 /// @cond
 587
 588 //To-do: pass to variadic templates
 589 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 590
 591 template<class Prev, class Next>
 592 struct do_pack
 593 {
 594    //Use "pack" member template to pack options
 595    typedef typename Next::template pack<Prev> type;
 596 };
 597
 598 template<class Prev>
 599 struct do_pack<Prev, none>
 600 {
 601    //Avoid packing "none" to shorten template names
 602    typedef Prev type;
 603 };
 604
 605 template
 606    < class DefaultOptions
 607    , class O1         = none
 608    , class O2         = none
 609    , class O3         = none
 610    , class O4         = none
 611    , class O5         = none
 612    , class O6         = none
 613    , class O7         = none
 614    , class O8         = none
 615    , class O9         = none
 616    , class O10        = none
 617    , class O11        = none
 618    >
 619 struct pack_options
 620 {
 621    // join options
 622    typedef
 623       typename do_pack
 624       <  typename do_pack
 625          <  typename do_pack
 626             <  typename do_pack
 627                <  typename do_pack
 628                   <  typename do_pack
 629                      <  typename do_pack
 630                         <  typename do_pack
 631                            <  typename do_pack
 632                               <  typename do_pack
 633                                  <  typename do_pack
 634                                     < DefaultOptions
 635                                     , O1
 636                                     >::type
 637                                  , O2
 638                                  >::type
 639                               , O3
 640                               >::type
 641                            , O4
 642                            >::type
 643                         , O5
 644                         >::type
 645                      , O6
 646                      >::type
 647                   , O7
 648                   >::type
 649                , O8
 650                >::type
 651             , O9
 652             >::type
 653          , O10
 654          >::type
 655       , O11
 656       >::type
 657    type;
 658 };
 659 #else
 660
 661 //index_tuple
 662 template<int... Indexes>
 663 struct index_tuple{};
 664
 665 //build_number_seq
 666 template<std::size_t Num, typename Tuple = index_tuple<> >
 667 struct build_number_seq;
 668
 669 template<std::size_t Num, int... Indexes>
 670 struct build_number_seq<Num, index_tuple<Indexes...> >
 671    : build_number_seq<Num - 1, index_tuple<Indexes..., sizeof...(Indexes)> >
 672 {};
 673
 674 template<int... Indexes>
 675 struct build_number_seq<0, index_tuple<Indexes...> >
 676 {  typedef index_tuple<Indexes...> type;  };
 677
 678 template<class ...Types>
 679 struct typelist
 680 {};
 681
 682 //invert_typelist
 683 template<class T>
 684 struct invert_typelist;
 685
 686 template<int I, typename Tuple>
 687 struct typelist_element;
 688
 689 template<int I, typename Head, typename... Tail>
 690 struct typelist_element<I, typelist<Head, Tail...> >
 691 {
 692    typedef typename typelist_element<I-1, typelist<Tail...> >::type type;
 693 };
 694
 695 template<typename Head, typename... Tail>
 696 struct typelist_element<0, typelist<Head, Tail...> >
 697 {
 698    typedef Head type;
 699 };
 700
 701 template<int ...Ints, class ...Types>
 702 typelist<typename typelist_element<(sizeof...(Types) - 1) - Ints, typelist<Types...> >::type...>
 703    inverted_typelist(index_tuple<Ints...>, typelist<Types...>)
 704 {
 705    return typelist<typename typelist_element<(sizeof...(Types) - 1) - Ints, typelist<Types...> >::type...>();
 706 }
 707
 708 //sizeof_typelist
 709 template<class Typelist>
 710 struct sizeof_typelist;
 711
 712 template<class ...Types>
 713 struct sizeof_typelist< typelist<Types...> >
 714 {
 715    static const std::size_t value = sizeof...(Types);
 716 };
 717
 718 //invert_typelist_impl
 719 template<class Typelist, class Indexes>
 720 struct invert_typelist_impl;
 721
 722
 723 template<class Typelist, int ...Ints>
 724 struct invert_typelist_impl< Typelist, index_tuple<Ints...> >
 725 {
 726    static const std::size_t last_idx = sizeof_typelist<Typelist>::value - 1;
 727    typedef typelist
 728       <typename typelist_element<last_idx - Ints, Typelist>::type...> type;
 729 };
 730
 731 template<class Typelist, int Int>
 732 struct invert_typelist_impl< Typelist, index_tuple<Int> >
 733 {
 734    typedef Typelist type;
 735 };
 736
 737 template<class Typelist>
 738 struct invert_typelist_impl< Typelist, index_tuple<> >
 739 {
 740    typedef Typelist type;
 741 };
 742
 743 //invert_typelist
 744 template<class Typelist>
 745 struct invert_typelist;
 746
 747 template<class ...Types>
 748 struct invert_typelist< typelist<Types...> >
 749 {
 750    typedef typelist<Types...> typelist_t;
 751    typedef typename build_number_seq<sizeof...(Types)>::type indexes_t;
 752    typedef typename invert_typelist_impl<typelist_t, indexes_t>::type type;
 753 };
 754
 755 //Do pack
 756 template<class Typelist>
 757 struct do_pack;
 758
 759 template<>
 760 struct do_pack<typelist<> >;
 761
 762 template<class Prev>
 763 struct do_pack<typelist<Prev> >
 764 {
 765    typedef Prev type;
 766 };
 767
 768 template<class Prev, class Last>
 769 struct do_pack<typelist<Prev, Last> >
 770 {
 771    typedef typename Prev::template pack<Last> type;
 772 };
 773
 774 template<class Prev, class ...Others>
 775 struct do_pack<typelist<Prev, Others...> >
 776 {
 777    typedef typename Prev::template pack
 778       <typename do_pack<typelist<Others...> >::type> type;
 779 };
 780
 781
 782 template<class ...Options>
 783 struct pack_options
 784 {
 785    typedef typelist<Options...> typelist_t;
 786    typedef typename invert_typelist<typelist_t>::type inverted_typelist;
 787    typedef typename do_pack<inverted_typelist>::type type;
 788 };
 789
 790 #endif
 791
 792 struct hook_defaults
 793    :  public pack_options
 794       < none
 795       , void_pointer<void*>
 796       , link_mode<safe_link>
 797       , tag<default_tag>
 798       , optimize_size<false>
 799       , store_hash<false>
 800       , linear<false>
 801       , optimize_multikey<false>
 802       >::type
 803 {};
 804
 805 /// @endcond
 806
 807 }  //namespace intrusive {
 808 }  //namespace boost {
 809
 810 #include <boost/intrusive/detail/config_end.hpp>
 811
 812 #endif   //#ifndef BOOST_INTRUSIVE_OPTIONS_HPP