boost/intrusive/detail/utilities.hpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga  2006-2012
   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_DETAIL_UTILITIES_HPP
  14 #define BOOST_INTRUSIVE_DETAIL_UTILITIES_HPP
  15
  16 #include <boost/intrusive/detail/config_begin.hpp>
  17 #include <boost/intrusive/pointer_traits.hpp>
  18 #include <boost/intrusive/detail/parent_from_member.hpp>
  19 #include <boost/intrusive/detail/ebo_functor_holder.hpp>
  20 #include <boost/intrusive/link_mode.hpp>
  21 #include <boost/intrusive/detail/mpl.hpp>
  22 #include <boost/intrusive/detail/assert.hpp>
  23 #include <boost/intrusive/detail/is_stateful_value_traits.hpp>
  24 #include <boost/intrusive/pointer_traits.hpp>
  25 #include <boost/cstdint.hpp>
  26 #include <cstddef>
  27 #include <climits>
  28 #include <iterator>
  29 #include <boost/cstdint.hpp>
  30 #include <boost/static_assert.hpp>
  31
  32 namespace boost {
  33 namespace intrusive {
  34 namespace detail {
  35
  36 template <class T>
  37 struct internal_member_value_traits
  38 {
  39    template <class U> static detail::one test(...);
  40    template <class U> static detail::two test(typename U::member_value_traits* = 0);
  41    static const bool value = sizeof(test<T>(0)) == sizeof(detail::two);
  42 };
  43
  44 template <class T>
  45 struct internal_base_hook_bool
  46 {
  47    template<bool Add>
  48    struct two_or_three {one _[2 + Add];};
  49    template <class U> static one test(...);
  50    template <class U> static two_or_three<U::boost_intrusive_tags::is_base_hook> test (int);
  51    static const std::size_t value = sizeof(test<T>(0));
  52 };
  53
  54 template <class T>
  55 struct internal_base_hook_bool_is_true
  56 {
  57    static const bool value = internal_base_hook_bool<T>::value > sizeof(one)*2;
  58 };
  59
  60 template <class T>
  61 struct internal_any_hook_bool
  62 {
  63    template<bool Add>
  64    struct two_or_three {one _[2 + Add];};
  65    template <class U> static one test(...);
  66    template <class U> static two_or_three<U::is_any_hook> test (int);
  67    static const std::size_t value = sizeof(test<T>(0));
  68 };
  69
  70 template <class T>
  71 struct internal_any_hook_bool_is_true
  72 {
  73    static const bool value = internal_any_hook_bool<T>::value > sizeof(one)*2;
  74 };
  75
  76
  77 template <class T>
  78 struct external_value_traits_bool
  79 {
  80    template<bool Add>
  81    struct two_or_three {one _[2 + Add];};
  82    template <class U> static one test(...);
  83    template <class U> static two_or_three<U::external_value_traits> test (int);
  84    static const std::size_t value = sizeof(test<T>(0));
  85 };
  86
  87 template <class T>
  88 struct external_bucket_traits_bool
  89 {
  90    template<bool Add>
  91    struct two_or_three {one _[2 + Add];};
  92    template <class U> static one test(...);
  93    template <class U> static two_or_three<U::external_bucket_traits> test (int);
  94    static const std::size_t value = sizeof(test<T>(0));
  95 };
  96
  97 template <class T>
  98 struct external_value_traits_is_true
  99 {
 100    static const bool value = external_value_traits_bool<T>::value > sizeof(one)*2;
 101 };
 102
 103 template<class Node, class Tag, link_mode_type LinkMode, int>
 104 struct node_holder
 105    :  public Node
 106 {};
 107
 108 template <class T>
 109 inline T* to_raw_pointer(T* p)
 110 {  return p; }
 111
 112 template <class Pointer>
 113 inline typename boost::intrusive::pointer_traits<Pointer>::element_type*
 114 to_raw_pointer(const Pointer &p)
 115 {  return boost::intrusive::detail::to_raw_pointer(p.operator->());  }
 116
 117 //This functor compares a stored value
 118 //and the one passed as an argument
 119 template<class ConstReference>
 120 class equal_to_value
 121 {
 122    ConstReference t_;
 123
 124    public:
 125    equal_to_value(ConstReference t)
 126       :  t_(t)
 127    {}
 128
 129    bool operator()(ConstReference t)const
 130    {  return t_ == t;   }
 131 };
 132
 133 class null_disposer
 134 {
 135    public:
 136    template <class Pointer>
 137    void operator()(Pointer)
 138    {}
 139 };
 140
 141 template<class NodeAlgorithms>
 142 class init_disposer
 143 {
 144    typedef typename NodeAlgorithms::node_ptr node_ptr;
 145
 146    public:
 147    void operator()(const node_ptr & p)
 148    {  NodeAlgorithms::init(p);   }
 149 };
 150
 151 template<bool ConstantSize, class SizeType>
 152 struct size_holder
 153 {
 154    static const bool constant_time_size = ConstantSize;
 155    typedef SizeType  size_type;
 156
 157    SizeType get_size() const
 158    {  return size_;  }
 159
 160    void set_size(SizeType size)
 161    {  size_ = size; }
 162
 163    void decrement()
 164    {  --size_; }
 165
 166    void increment()
 167    {  ++size_; }
 168
 169    SizeType size_;
 170 };
 171
 172 template<class SizeType>
 173 struct size_holder<false, SizeType>
 174 {
 175    static const bool constant_time_size = false;
 176    typedef SizeType  size_type;
 177
 178    size_type get_size() const
 179    {  return 0;  }
 180
 181    void set_size(size_type)
 182    {}
 183
 184    void decrement()
 185    {}
 186
 187    void increment()
 188    {}
 189 };
 190
 191 template<class KeyValueCompare, class Container>
 192 struct key_nodeptr_comp
 193    :  private detail::ebo_functor_holder<KeyValueCompare>
 194 {
 195    typedef typename Container::real_value_traits         real_value_traits;
 196    typedef typename Container::value_type                value_type;
 197    typedef typename real_value_traits::node_ptr          node_ptr;
 198    typedef typename real_value_traits::const_node_ptr    const_node_ptr;
 199    typedef detail::ebo_functor_holder<KeyValueCompare>   base_t;
 200    key_nodeptr_comp(KeyValueCompare kcomp, const Container *cont)
 201       :  base_t(kcomp), cont_(cont)
 202    {}
 203
 204    template<class T>
 205    struct is_node_ptr
 206    {
 207       static const bool value = is_same<T, const_node_ptr>::value || is_same<T, node_ptr>::value;
 208    };
 209
 210    template<class T>
 211    const value_type & key_forward
 212       (const T &node, typename enable_if_c<is_node_ptr<T>::value>::type * = 0) const
 213    {  return *cont_->get_real_value_traits().to_value_ptr(node);  }
 214
 215    template<class T>
 216    const T & key_forward(const T &key, typename enable_if_c<!is_node_ptr<T>::value>::type* = 0) const
 217    {  return key;  }
 218
 219
 220    template<class KeyType, class KeyType2>
 221    bool operator()(const KeyType &key1, const KeyType2 &key2) const
 222    {  return base_t::get()(this->key_forward(key1), this->key_forward(key2));  }
 223
 224    const Container *cont_;
 225 };
 226
 227 template<class F, class Container>
 228 struct node_cloner
 229    :  private detail::ebo_functor_holder<F>
 230 {
 231    typedef typename Container::real_value_traits         real_value_traits;
 232    typedef typename Container::node_algorithms           node_algorithms;
 233    typedef typename real_value_traits::value_type        value_type;
 234    typedef typename real_value_traits::pointer           pointer;
 235    typedef typename real_value_traits::node_traits::node node;
 236    typedef typename real_value_traits::node_ptr          node_ptr;
 237    typedef typename real_value_traits::const_node_ptr    const_node_ptr;
 238    typedef detail::ebo_functor_holder<F>                 base_t;
 239    enum { safemode_or_autounlink  =
 240             (int)real_value_traits::link_mode == (int)auto_unlink   ||
 241             (int)real_value_traits::link_mode == (int)safe_link     };
 242
 243    node_cloner(F f, const Container *cont)
 244       :  base_t(f), cont_(cont)
 245    {}
 246
 247    node_ptr operator()(const node_ptr & p)
 248    {  return this->operator()(*p); }
 249
 250    node_ptr operator()(const node &to_clone)
 251    {
 252       const value_type &v =
 253          *cont_->get_real_value_traits().to_value_ptr
 254             (pointer_traits<const_node_ptr>::pointer_to(to_clone));
 255       node_ptr n = cont_->get_real_value_traits().to_node_ptr(*base_t::get()(v));
 256       //Cloned node must be in default mode if the linking mode requires it
 257       if(safemode_or_autounlink)
 258          BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(node_algorithms::unique(n));
 259       return n;
 260    }
 261
 262    const Container *cont_;
 263 };
 264
 265 template<class F, class Container>
 266 struct node_disposer
 267    :  private detail::ebo_functor_holder<F>
 268 {
 269    typedef typename Container::real_value_traits   real_value_traits;
 270    typedef typename real_value_traits::node_ptr    node_ptr;
 271    typedef detail::ebo_functor_holder<F>           base_t;
 272    typedef typename Container::node_algorithms     node_algorithms;
 273    enum { safemode_or_autounlink  =
 274             (int)real_value_traits::link_mode == (int)auto_unlink   ||
 275             (int)real_value_traits::link_mode == (int)safe_link     };
 276
 277    node_disposer(F f, const Container *cont)
 278       :  base_t(f), cont_(cont)
 279    {}
 280
 281    void operator()(const node_ptr & p)
 282    {
 283       if(safemode_or_autounlink)
 284          node_algorithms::init(p);
 285       base_t::get()(cont_->get_real_value_traits().to_value_ptr(p));
 286    }
 287    const Container *cont_;
 288 };
 289
 290 struct dummy_constptr
 291 {
 292    dummy_constptr(const void *)
 293    {}
 294
 295    const void *get_ptr() const
 296    {  return 0;  }
 297 };
 298
 299 template<class VoidPointer>
 300 struct constptr
 301 {
 302    typedef typename boost::intrusive::pointer_traits<VoidPointer>::
 303       template rebind_pointer<const void>::type ConstVoidPtr;
 304
 305    constptr(const void *ptr)
 306       :  const_void_ptr_(ptr)
 307    {}
 308
 309    const void *get_ptr() const
 310    {  return boost::intrusive::detail::to_raw_pointer(const_void_ptr_);  }
 311
 312    ConstVoidPtr const_void_ptr_;
 313 };
 314
 315 template <class VoidPointer, bool store_ptr>
 316 struct select_constptr
 317 {
 318    typedef typename detail::if_c
 319       < store_ptr
 320       , constptr<VoidPointer>
 321       , dummy_constptr
 322       >::type type;
 323 };
 324
 325 template<class T, bool Add>
 326 struct add_const_if_c
 327 {
 328    typedef typename detail::if_c
 329       < Add
 330       , typename detail::add_const<T>::type
 331       , T
 332       >::type type;
 333 };
 334
 335 template <link_mode_type LinkMode>
 336 struct link_dispatch
 337 {};
 338
 339 template<class Hook>
 340 void destructor_impl(Hook &hook, detail::link_dispatch<safe_link>)
 341 {  //If this assertion raises, you might have destroyed an object
 342    //while it was still inserted in a container that is alive.
 343    //If so, remove the object from the container before destroying it.
 344    (void)hook; BOOST_INTRUSIVE_SAFE_HOOK_DESTRUCTOR_ASSERT(!hook.is_linked());
 345 }
 346
 347 template<class Hook>
 348 void destructor_impl(Hook &hook, detail::link_dispatch<auto_unlink>)
 349 {  hook.unlink();  }
 350
 351 template<class Hook>
 352 void destructor_impl(Hook &, detail::link_dispatch<normal_link>)
 353 {}
 354
 355 template<class T, class NodeTraits, link_mode_type LinkMode, class Tag, int HookType>
 356 struct base_hook_traits
 357 {
 358    public:
 359    typedef detail::node_holder
 360       <typename NodeTraits::node, Tag, LinkMode, HookType>           node_holder;
 361    typedef typename NodeTraits::node                                 node;
 362    typedef NodeTraits                                                node_traits;
 363    typedef T                                                         value_type;
 364    typedef typename node_traits::node_ptr                            node_ptr;
 365    typedef typename node_traits::const_node_ptr                      const_node_ptr;
 366    typedef typename pointer_traits<node_ptr>::
 367       template rebind_pointer<T>::type                               pointer;
 368    typedef typename pointer_traits<node_ptr>::
 369       template rebind_pointer<const T>::type                         const_pointer;
 370    //typedef typename pointer_traits<pointer>::reference               reference;
 371    //typedef typename pointer_traits<const_pointer>::reference         const_reference;
 372    typedef T &                                                       reference;
 373    typedef const T &                                                 const_reference;
 374    typedef node_holder &                                             node_holder_reference;
 375    typedef const node_holder &                                       const_node_holder_reference;
 376    typedef node&                                                     node_reference;
 377    typedef const node &                                              const_node_reference;
 378
 379    static const link_mode_type link_mode = LinkMode;
 380
 381    static pointer to_value_ptr(const node_ptr & n)
 382    {
 383       return pointer_traits<pointer>::pointer_to
 384          (static_cast<reference>(static_cast<node_holder_reference>(*n)));
 385    }
 386
 387    static const_pointer to_value_ptr(const const_node_ptr & n)
 388    {
 389       return pointer_traits<const_pointer>::pointer_to
 390          (static_cast<const_reference>(static_cast<const_node_holder_reference>(*n)));
 391    }
 392
 393    static node_ptr to_node_ptr(reference value)
 394    {
 395       return pointer_traits<node_ptr>::pointer_to
 396          (static_cast<node_reference>(static_cast<node_holder_reference>(value)));
 397    }
 398
 399    static const_node_ptr to_node_ptr(const_reference value)
 400    {
 401       return pointer_traits<const_node_ptr>::pointer_to
 402          (static_cast<const_node_reference>(static_cast<const_node_holder_reference>(value)));
 403    }
 404 };
 405
 406 template<class T, class Hook, Hook T::* P>
 407 struct member_hook_traits
 408 {
 409    public:
 410    typedef Hook                                                      hook_type;
 411    typedef typename hook_type::boost_intrusive_tags::node_traits     node_traits;
 412    typedef typename node_traits::node                                node;
 413    typedef T                                                         value_type;
 414    typedef typename node_traits::node_ptr                            node_ptr;
 415    typedef typename node_traits::const_node_ptr                      const_node_ptr;
 416    typedef typename pointer_traits<node_ptr>::
 417       template rebind_pointer<T>::type                               pointer;
 418    typedef typename pointer_traits<node_ptr>::
 419       template rebind_pointer<const T>::type                         const_pointer;
 420    typedef T &                                                       reference;
 421    typedef const T &                                                 const_reference;
 422    typedef node&                                                     node_reference;
 423    typedef const node &                                              const_node_reference;
 424    typedef hook_type&                                                hook_reference;
 425    typedef const hook_type &                                         const_hook_reference;
 426
 427    static const link_mode_type link_mode = Hook::boost_intrusive_tags::link_mode;
 428
 429    static node_ptr to_node_ptr(reference value)
 430    {
 431       return pointer_traits<node_ptr>::pointer_to
 432          (static_cast<node_reference>(static_cast<hook_reference>(value.*P)));
 433    }
 434
 435    static const_node_ptr to_node_ptr(const_reference value)
 436    {
 437       return pointer_traits<const_node_ptr>::pointer_to
 438          (static_cast<const_node_reference>(static_cast<const_hook_reference>(value.*P)));
 439    }
 440
 441    static pointer to_value_ptr(const node_ptr & n)
 442    {
 443       return pointer_traits<pointer>::pointer_to
 444          (*detail::parent_from_member<T, Hook>
 445             (static_cast<Hook*>(boost::intrusive::detail::to_raw_pointer(n)), P));
 446    }
 447
 448    static const_pointer to_value_ptr(const const_node_ptr & n)
 449    {
 450       return pointer_traits<const_pointer>::pointer_to
 451          (*detail::parent_from_member<T, Hook>
 452             (static_cast<const Hook*>(boost::intrusive::detail::to_raw_pointer(n)), P));
 453    }
 454 };
 455
 456 template<class Functor>
 457 struct function_hook_traits
 458 {
 459    public:
 460    typedef typename Functor::hook_type                               hook_type;
 461    typedef typename Functor::hook_ptr                                hook_ptr;
 462    typedef typename Functor::const_hook_ptr                          const_hook_ptr;
 463    typedef typename hook_type::boost_intrusive_tags::node_traits     node_traits;
 464    typedef typename node_traits::node                                node;
 465    typedef typename Functor::value_type                              value_type;
 466    typedef typename node_traits::node_ptr                            node_ptr;
 467    typedef typename node_traits::const_node_ptr                      const_node_ptr;
 468    typedef typename pointer_traits<node_ptr>::
 469       template rebind_pointer<value_type>::type                      pointer;
 470    typedef typename pointer_traits<node_ptr>::
 471       template rebind_pointer<const value_type>::type                const_pointer;
 472    typedef value_type &                                              reference;
 473    typedef const value_type &                                        const_reference;
 474    static const link_mode_type link_mode = hook_type::boost_intrusive_tags::link_mode;
 475
 476    static node_ptr to_node_ptr(reference value)
 477    {  return static_cast<node*>(boost::intrusive::detail::to_raw_pointer(Functor::to_hook_ptr(value)));  }
 478
 479    static const_node_ptr to_node_ptr(const_reference value)
 480    {  return static_cast<const node*>(boost::intrusive::detail::to_raw_pointer(Functor::to_hook_ptr(value)));  }
 481
 482    static pointer to_value_ptr(const node_ptr & n)
 483    {  return Functor::to_value_ptr(to_hook_ptr(n));  }
 484
 485    static const_pointer to_value_ptr(const const_node_ptr & n)
 486    {  return Functor::to_value_ptr(to_hook_ptr(n));  }
 487
 488    private:
 489    static hook_ptr to_hook_ptr(const node_ptr & n)
 490    {  return hook_ptr(&*static_cast<hook_type*>(&*n));  }
 491
 492    static const_hook_ptr to_hook_ptr(const const_node_ptr & n)
 493    {  return const_hook_ptr(&*static_cast<const hook_type*>(&*n));  }
 494 };
 495
 496
 497 //This function uses binary search to discover the
 498 //highest set bit of the integer
 499 inline std::size_t floor_log2 (std::size_t x)
 500 {
 501    const std::size_t Bits = sizeof(std::size_t)*CHAR_BIT;
 502    const bool Size_t_Bits_Power_2= !(Bits & (Bits-1));
 503    BOOST_STATIC_ASSERT(Size_t_Bits_Power_2);
 504
 505    std::size_t n = x;
 506    std::size_t log2 = 0;
 507
 508    for(std::size_t shift = Bits >> 1; shift; shift >>= 1){
 509       std::size_t tmp = n >> shift;
 510       if (tmp)
 511          log2 += shift, n = tmp;
 512    }
 513
 514    return log2;
 515 }
 516
 517 inline float fast_log2 (float val)
 518 {
 519    union caster_t
 520    {
 521       boost::uint32_t x;
 522       float val;
 523    } caster;
 524
 525    caster.val = val;
 526    boost::uint32_t x = caster.x;
 527    const int log_2 = (int)(((x >> 23) & 255) - 128);
 528    x &= ~(255 << 23);
 529    x += 127 << 23;
 530    caster.x = x;
 531    val = caster.val;
 532    val = ((-1.0f/3.f) * val + 2.f) * val - (2.0f/3.f);
 533
 534    return (val + log_2);
 535 }
 536
 537 inline std::size_t ceil_log2 (std::size_t x)
 538 {
 539    return ((x & (x-1))!= 0) + floor_log2(x);
 540 }
 541
 542 template<class SizeType, std::size_t N>
 543 struct numbits_eq
 544 {
 545    static const bool value = sizeof(SizeType)*CHAR_BIT == N;
 546 };
 547
 548 template<class SizeType, class Enabler = void >
 549 struct sqrt2_pow_max;
 550
 551 template <class SizeType>
 552 struct sqrt2_pow_max<SizeType, typename enable_if< numbits_eq<SizeType, 32> >::type>
 553 {
 554    static const boost::uint32_t value = 0xb504f334;
 555    static const std::size_t pow   = 31;
 556 };
 557
 558 template <class SizeType>
 559 struct sqrt2_pow_max<SizeType, typename enable_if< numbits_eq<SizeType, 64> >::type>
 560 {
 561    static const boost::uint64_t value = 0xb504f333f9de6484ull;
 562    static const std::size_t pow   = 63;
 563 };
 564
 565 // Returns floor(pow(sqrt(2), x * 2 + 1)).
 566 // Defined for X from 0 up to the number of bits in size_t minus 1.
 567 inline std::size_t sqrt2_pow_2xplus1 (std::size_t x)
 568 {
 569    const std::size_t value = (std::size_t)sqrt2_pow_max<std::size_t>::value;
 570    const std::size_t pow   = (std::size_t)sqrt2_pow_max<std::size_t>::pow;
 571    return (value >> (pow - x)) + 1;
 572 }
 573
 574 template<class Container, class Disposer>
 575 class exception_disposer
 576 {
 577    Container *cont_;
 578    Disposer  &disp_;
 579
 580    exception_disposer(const exception_disposer&);
 581    exception_disposer &operator=(const exception_disposer&);
 582
 583    public:
 584    exception_disposer(Container &cont, Disposer &disp)
 585       :  cont_(&cont), disp_(disp)
 586    {}
 587
 588    void release()
 589    {  cont_ = 0;  }
 590
 591    ~exception_disposer()
 592    {
 593       if(cont_){
 594          cont_->clear_and_dispose(disp_);
 595       }
 596    }
 597 };
 598
 599 template<class Container, class Disposer, class SizeType>
 600 class exception_array_disposer
 601 {
 602    Container *cont_;
 603    Disposer  &disp_;
 604    SizeType  &constructed_;
 605
 606    exception_array_disposer(const exception_array_disposer&);
 607    exception_array_disposer &operator=(const exception_array_disposer&);
 608
 609    public:
 610
 611    exception_array_disposer
 612       (Container &cont, Disposer &disp, SizeType &constructed)
 613       :  cont_(&cont), disp_(disp), constructed_(constructed)
 614    {}
 615
 616    void release()
 617    {  cont_ = 0;  }
 618
 619    ~exception_array_disposer()
 620    {
 621       SizeType n = constructed_;
 622       if(cont_){
 623          while(n--){
 624             cont_[n].clear_and_dispose(disp_);
 625          }
 626       }
 627    }
 628 };
 629
 630 template<class ValueTraits, bool ExternalValueTraits>
 631 struct store_cont_ptr_on_it_impl
 632 {
 633    static const bool value = is_stateful_value_traits<ValueTraits>::value;
 634 };
 635
 636 template<class ValueTraits>
 637 struct  store_cont_ptr_on_it_impl<ValueTraits, true>
 638 {
 639    static const bool value = true;
 640 };
 641
 642 template <class Container>
 643 struct store_cont_ptr_on_it
 644 {
 645    typedef typename Container::value_traits value_traits;
 646    static const bool value = store_cont_ptr_on_it_impl
 647       <value_traits, external_value_traits_is_true<value_traits>::value>::value;
 648 };
 649
 650 template<class Container, bool IsConst>
 651 struct node_to_value
 652    :  public detail::select_constptr
 653       < typename pointer_traits
 654             <typename Container::pointer>::template rebind_pointer<void>::type
 655       , detail::store_cont_ptr_on_it<Container>::value
 656       >::type
 657 {
 658    static const bool store_container_ptr =
 659       detail::store_cont_ptr_on_it<Container>::value;
 660
 661    typedef typename Container::real_value_traits         real_value_traits;
 662    typedef typename real_value_traits::value_type        value_type;
 663    typedef typename detail::select_constptr
 664       < typename pointer_traits
 665             <typename Container::pointer>::template rebind_pointer<void>::type
 666       , store_container_ptr >::type                      Base;
 667    typedef typename real_value_traits::node_traits::node node;
 668    typedef typename detail::add_const_if_c
 669          <value_type, IsConst>::type                  vtype;
 670    typedef typename detail::add_const_if_c
 671          <node, IsConst>::type                        ntype;
 672    typedef typename pointer_traits
 673       <typename Container::pointer>::template rebind_pointer<ntype>::type npointer;
 674
 675    node_to_value(const Container *cont)
 676       :  Base(cont)
 677    {}
 678
 679    typedef vtype &                                 result_type;
 680    typedef ntype &                                 first_argument_type;
 681
 682    const Container *get_container() const
 683    {
 684       if(store_container_ptr)
 685          return static_cast<const Container*>(Base::get_ptr());
 686       else
 687          return 0;
 688    }
 689
 690    const real_value_traits *get_real_value_traits() const
 691    {
 692       if(store_container_ptr)
 693          return &this->get_container()->get_real_value_traits();
 694       else
 695          return 0;
 696    }
 697
 698    result_type operator()(first_argument_type arg) const
 699    {
 700       return *(this->get_real_value_traits()->to_value_ptr
 701          (pointer_traits<npointer>::pointer_to(arg)));
 702    }
 703 };
 704
 705 //This is not standard, but should work with all compilers
 706 union max_align
 707 {
 708    char        char_;
 709    short       short_;
 710    int         int_;
 711    long        long_;
 712    #ifdef BOOST_HAS_LONG_LONG
 713    long long   long_long_;
 714    #endif
 715    float       float_;
 716    double      double_;
 717    long double long_double_;
 718    void *      void_ptr_;
 719 };
 720
 721 template<class T, std::size_t N>
 722 class array_initializer
 723 {
 724    public:
 725    template<class CommonInitializer>
 726    array_initializer(const CommonInitializer &init)
 727    {
 728       char *init_buf = (char*)rawbuf;
 729       std::size_t i = 0;
 730       try{
 731          for(; i != N; ++i){
 732             new(init_buf)T(init);
 733             init_buf += sizeof(T);
 734          }
 735       }
 736       catch(...){
 737          while(i--){
 738             init_buf -= sizeof(T);
 739             ((T*)init_buf)->~T();
 740          }
 741          throw;
 742       }
 743    }
 744
 745    operator T* ()
 746    {  return (T*)(rawbuf);  }
 747
 748    operator const T*() const
 749    {  return (const T*)(rawbuf);  }
 750
 751    ~array_initializer()
 752    {
 753       char *init_buf = (char*)rawbuf + N*sizeof(T);
 754       for(std::size_t i = 0; i != N; ++i){
 755          init_buf -= sizeof(T);
 756          ((T*)init_buf)->~T();
 757       }
 758    }
 759
 760    private:
 761    detail::max_align rawbuf[(N*sizeof(T)-1)/sizeof(detail::max_align)+1];
 762 };
 763
 764
 765
 766
 767 template<class It>
 768 class reverse_iterator
 769         : public std::iterator<
 770                 typename std::iterator_traits<It>::iterator_category,
 771                 typename std::iterator_traits<It>::value_type,
 772                 typename std::iterator_traits<It>::difference_type,
 773                 typename std::iterator_traits<It>::pointer,
 774                 typename std::iterator_traits<It>::reference>
 775 {
 776    public:
 777         typedef typename std::iterator_traits<It>::pointer pointer;
 778         typedef typename std::iterator_traits<It>::reference reference;
 779         typedef typename std::iterator_traits<It>::difference_type difference_type;
 780         typedef It iterator_type;
 781
 782         reverse_iterator(){}
 783
 784         explicit reverse_iterator(It r)
 785                 : m_current(r)
 786    {}
 787
 788         template<class OtherIt>
 789         reverse_iterator(const reverse_iterator<OtherIt>& r)
 790            : m_current(r.base())
 791         {}
 792
 793         It base() const
 794    {  return m_current;  }
 795
 796         reference operator*() const
 797    {  It temp(m_current);   --temp; return *temp; }
 798
 799         pointer operator->() const
 800    {  It temp(m_current);   --temp; return temp.operator->(); }
 801
 802         reference operator[](difference_type off) const
 803         {  return this->m_current[-off];  }
 804
 805         reverse_iterator& operator++()
 806    {  --m_current;   return *this;   }
 807
 808         reverse_iterator operator++(int)
 809         {
 810                 reverse_iterator temp = *this;
 811                 --m_current;
 812                 return temp;
 813         }
 814
 815         reverse_iterator& operator--()
 816         {
 817            ++m_current;
 818                 return *this;
 819    }
 820
 821         reverse_iterator operator--(int)
 822         {
 823            reverse_iterator temp(*this);
 824            ++m_current;
 825            return temp;
 826         }
 827
 828         friend bool operator==(const reverse_iterator& l, const reverse_iterator& r)
 829         {  return l.m_current == r.m_current;  }
 830
 831         friend bool operator!=(const reverse_iterator& l, const reverse_iterator& r)
 832         {  return l.m_current != r.m_current;  }
 833
 834         friend bool operator<(const reverse_iterator& l, const reverse_iterator& r)
 835         {  return l.m_current < r.m_current;  }
 836
 837         friend bool operator<=(const reverse_iterator& l, const reverse_iterator& r)
 838         {  return l.m_current <= r.m_current;  }
 839
 840         friend bool operator>(const reverse_iterator& l, const reverse_iterator& r)
 841         {  return l.m_current > r.m_current;  }
 842
 843         friend bool operator>=(const reverse_iterator& l, const reverse_iterator& r)
 844         {  return l.m_current >= r.m_current;  }
 845
 846         reverse_iterator& operator+=(difference_type off)
 847         {  m_current -= off; return *this;  }
 848
 849         friend reverse_iterator operator+(const reverse_iterator & l, difference_type off)
 850         {
 851       reverse_iterator tmp(l.m_current);
 852       tmp.m_current -= off;
 853       return tmp;
 854    }
 855
 856         reverse_iterator& operator-=(difference_type off)
 857         {  m_current += off; return *this;  }
 858
 859         friend reverse_iterator operator-(const reverse_iterator & l, difference_type off)
 860         {
 861       reverse_iterator tmp(l.m_current);
 862       tmp.m_current += off;
 863       return tmp;
 864    }
 865
 866         friend difference_type operator-(const reverse_iterator& l, const reverse_iterator& r)
 867         {  return r.m_current - l.m_current;  }
 868
 869    private:
 870         It m_current;   // the wrapped iterator
 871 };
 872
 873 } //namespace detail
 874 } //namespace intrusive
 875 } //namespace boost
 876
 877 #include <boost/intrusive/detail/config_end.hpp>
 878
 879 #endif //BOOST_INTRUSIVE_DETAIL_UTILITIES_HPP