ceph/src/boost/boost/heap/detail/stable_heap.hpp

   1 // boost heap: helper classes for stable priority queues
   2 //
   3 // Copyright (C) 2010 Tim Blechmann
   4 //
   5 // Distributed under the Boost Software License, Version 1.0. (See
   6 // accompanying file LICENSE_1_0.txt or copy at
   7 // http://www.boost.org/LICENSE_1_0.txt)
   8
   9 #ifndef BOOST_HEAP_DETAIL_STABLE_HEAP_HPP
  10 #define BOOST_HEAP_DETAIL_STABLE_HEAP_HPP
  11
  12 #include <limits>
  13 #include <stdexcept>
  14 #include <utility>
  15
  16 #include <boost/cstdint.hpp>
  17 #include <boost/throw_exception.hpp>
  18 #include <boost/iterator/iterator_adaptor.hpp>
  19
  20 #include <boost/heap/policies.hpp>
  21 #include <boost/heap/heap_merge.hpp>
  22
  23 #include <boost/type_traits/is_nothrow_move_constructible.hpp>
  24 #include <boost/type_traits/is_nothrow_move_assignable.hpp>
  25
  26 namespace boost  {
  27 namespace heap   {
  28 namespace detail {
  29
  30 template<bool ConstantSize, class SizeType>
  31 struct size_holder
  32 {
  33     static const bool constant_time_size = ConstantSize;
  34     typedef SizeType  size_type;
  35
  36     size_holder(void) BOOST_NOEXCEPT:
  37         size_(0)
  38     {}
  39
  40 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
  41     size_holder(size_holder && rhs) BOOST_NOEXCEPT:
  42         size_(rhs.size_)
  43     {
  44         rhs.size_ = 0;
  45     }
  46
  47     size_holder(size_holder const & rhs) BOOST_NOEXCEPT:
  48         size_(rhs.size_)
  49     {}
  50
  51     size_holder & operator=(size_holder && rhs) BOOST_NOEXCEPT
  52     {
  53         size_ = rhs.size_;
  54         rhs.size_ = 0;
  55         return *this;
  56     }
  57
  58     size_holder & operator=(size_holder const & rhs) BOOST_NOEXCEPT
  59     {
  60         size_ = rhs.size_;
  61         return *this;
  62     }
  63 #endif
  64
  65     SizeType get_size() const BOOST_NOEXCEPT
  66     {  return size_;  }
  67
  68     void set_size(SizeType size) BOOST_NOEXCEPT
  69     {  size_ = size; }
  70
  71     void decrement() BOOST_NOEXCEPT
  72     {  --size_; }
  73
  74     void increment() BOOST_NOEXCEPT
  75     {  ++size_; }
  76
  77     void add(SizeType value) BOOST_NOEXCEPT
  78     {  size_ += value; }
  79
  80     void sub(SizeType value) BOOST_NOEXCEPT
  81     {  size_ -= value; }
  82
  83     void swap(size_holder & rhs) BOOST_NOEXCEPT
  84     {  std::swap(size_, rhs.size_); }
  85
  86     SizeType size_;
  87 };
  88
  89 template<class SizeType>
  90 struct size_holder<false, SizeType>
  91 {
  92     static const bool constant_time_size = false;
  93     typedef SizeType  size_type;
  94
  95     size_holder(void) BOOST_NOEXCEPT
  96     {}
  97
  98 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
  99     size_holder(size_holder && rhs) BOOST_NOEXCEPT
 100     {}
 101
 102     size_holder(size_holder const & rhs) BOOST_NOEXCEPT
 103     {}
 104
 105     size_holder & operator=(size_holder && rhs) BOOST_NOEXCEPT
 106     {
 107         return *this;
 108     }
 109
 110     size_holder & operator=(size_holder const & rhs) BOOST_NOEXCEPT
 111     {
 112         return *this;
 113     }
 114 #endif
 115
 116     size_type get_size() const BOOST_NOEXCEPT
 117     {  return 0;  }
 118
 119     void set_size(size_type) BOOST_NOEXCEPT
 120     {}
 121
 122     void decrement() BOOST_NOEXCEPT
 123     {}
 124
 125     void increment() BOOST_NOEXCEPT
 126     {}
 127
 128     void add(SizeType /*value*/) BOOST_NOEXCEPT
 129     {}
 130
 131     void sub(SizeType /*value*/) BOOST_NOEXCEPT
 132     {}
 133
 134     void swap(size_holder & /*rhs*/) BOOST_NOEXCEPT
 135     {}
 136 };
 137
 138 // note: MSVC does not implement lookup correctly, we therefore have to place the Cmp object as member inside the
 139 //       struct. of course, this prevents EBO and significantly reduces the readability of this code
 140 template <typename T,
 141           typename Cmp,
 142           bool constant_time_size,
 143           typename StabilityCounterType = boost::uintmax_t,
 144           bool stable = false
 145          >
 146 struct heap_base:
 147 #ifndef BOOST_MSVC
 148     Cmp,
 149 #endif
 150     size_holder<constant_time_size, size_t>
 151 {
 152     typedef StabilityCounterType stability_counter_type;
 153     typedef T value_type;
 154     typedef T internal_type;
 155     typedef size_holder<constant_time_size, size_t> size_holder_type;
 156     typedef Cmp value_compare;
 157     typedef Cmp internal_compare;
 158     static const bool is_stable = stable;
 159
 160 #ifdef BOOST_MSVC
 161     Cmp cmp_;
 162 #endif
 163
 164     heap_base (Cmp const & cmp = Cmp()):
 165 #ifndef BOOST_MSVC
 166         Cmp(cmp)
 167 #else
 168         cmp_(cmp)
 169 #endif
 170     {}
 171
 172 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
 173     heap_base(heap_base && rhs) BOOST_NOEXCEPT_IF(boost::is_nothrow_move_constructible<Cmp>::value):
 174 #ifndef BOOST_MSVC
 175         Cmp(std::move(static_cast<Cmp&>(rhs))),
 176 #else
 177         cmp_(std::move(rhs.cmp_)),
 178 #endif
 179         size_holder_type(std::move(static_cast<size_holder_type&>(rhs)))
 180     {}
 181
 182     heap_base(heap_base const & rhs):
 183 #ifndef BOOST_MSVC
 184         Cmp(static_cast<Cmp const &>(rhs)),
 185 #else
 186         cmp_(rhs.value_comp()),
 187 #endif
 188         size_holder_type(static_cast<size_holder_type const &>(rhs))
 189     {}
 190
 191     heap_base & operator=(heap_base && rhs) BOOST_NOEXCEPT_IF(boost::is_nothrow_move_assignable<Cmp>::value)
 192     {
 193         value_comp_ref().operator=(std::move(rhs.value_comp_ref()));
 194         size_holder_type::operator=(std::move(static_cast<size_holder_type&>(rhs)));
 195         return *this;
 196     }
 197
 198     heap_base & operator=(heap_base const & rhs)
 199     {
 200         value_comp_ref().operator=(rhs.value_comp());
 201         size_holder_type::operator=(static_cast<size_holder_type const &>(rhs));
 202         return *this;
 203     }
 204 #endif
 205
 206     bool operator()(internal_type const & lhs, internal_type const & rhs) const
 207     {
 208         return value_comp().operator()(lhs, rhs);
 209     }
 210
 211     internal_type make_node(T const & val)
 212     {
 213         return val;
 214     }
 215
 216 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
 217     T && make_node(T && val)
 218     {
 219         return std::forward<T>(val);
 220     }
 221 #endif
 222
 223 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
 224     template <class... Args>
 225     internal_type make_node(Args && ... val)
 226     {
 227         return internal_type(std::forward<Args>(val)...);
 228     }
 229 #endif
 230
 231     static T & get_value(internal_type & val) BOOST_NOEXCEPT
 232     {
 233         return val;
 234     }
 235
 236     static T const & get_value(internal_type const & val) BOOST_NOEXCEPT
 237     {
 238         return val;
 239     }
 240
 241     Cmp const & value_comp(void) const BOOST_NOEXCEPT
 242     {
 243 #ifndef BOOST_MSVC
 244         return *this;
 245 #else
 246         return cmp_;
 247 #endif
 248     }
 249
 250     Cmp const & get_internal_cmp(void) const BOOST_NOEXCEPT
 251     {
 252         return value_comp();
 253     }
 254
 255     void swap(heap_base & rhs) BOOST_NOEXCEPT_IF(boost::is_nothrow_move_constructible<Cmp>::value && boost::is_nothrow_move_assignable<Cmp>::value)
 256     {
 257         std::swap(value_comp_ref(), rhs.value_comp_ref());
 258         size_holder<constant_time_size, size_t>::swap(rhs);
 259     }
 260
 261     stability_counter_type get_stability_count(void) const BOOST_NOEXCEPT
 262     {
 263         return 0;
 264     }
 265
 266     void set_stability_count(stability_counter_type) BOOST_NOEXCEPT
 267     {}
 268
 269     template <typename Heap1, typename Heap2>
 270     friend struct heap_merge_emulate;
 271
 272 private:
 273     Cmp & value_comp_ref(void)
 274     {
 275 #ifndef BOOST_MSVC
 276         return *this;
 277 #else
 278         return cmp_;
 279 #endif
 280     }
 281 };
 282
 283
 284 template <typename T,
 285           typename Cmp,
 286           bool constant_time_size,
 287           typename StabilityCounterType
 288          >
 289 struct heap_base<T, Cmp, constant_time_size, StabilityCounterType, true>:
 290 #ifndef BOOST_MSVC
 291     Cmp,
 292 #endif
 293     size_holder<constant_time_size, size_t>
 294 {
 295     typedef StabilityCounterType stability_counter_type;
 296     typedef T value_type;
 297
 298     struct internal_type
 299     {
 300 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
 301         template <class ...Args>
 302         internal_type(stability_counter_type cnt, Args && ... args):
 303             first(std::forward<Args>(args)...), second(cnt)
 304         {}
 305 #endif
 306
 307         internal_type(stability_counter_type const & cnt, T const & value):
 308             first(value), second(cnt)
 309         {}
 310
 311         T first;
 312         stability_counter_type second;
 313     };
 314
 315     typedef size_holder<constant_time_size, size_t> size_holder_type;
 316     typedef Cmp value_compare;
 317
 318 #ifdef BOOST_MSVC
 319     Cmp cmp_;
 320 #endif
 321
 322     heap_base (Cmp const & cmp = Cmp()):
 323 #ifndef BOOST_MSVC
 324         Cmp(cmp),
 325 #else
 326         cmp_(cmp),
 327 #endif
 328         counter_(0)
 329     {}
 330
 331 #ifndef BOOST_NO_CXX11_RVALUE_REFERENCES
 332     heap_base(heap_base && rhs) BOOST_NOEXCEPT_IF(boost::is_nothrow_move_constructible<Cmp>::value):
 333 #ifndef BOOST_MSVC
 334         Cmp(std::move(static_cast<Cmp&>(rhs))),
 335 #else
 336         cmp_(std::move(rhs.cmp_)),
 337 #endif
 338         size_holder_type(std::move(static_cast<size_holder_type&>(rhs))), counter_(rhs.counter_)
 339     {
 340         rhs.counter_ = 0;
 341     }
 342
 343     heap_base(heap_base const & rhs):
 344 #ifndef BOOST_MSVC
 345         Cmp(static_cast<Cmp const&>(rhs)),
 346 #else
 347         cmp_(rhs.value_comp()),
 348 #endif
 349         size_holder_type(static_cast<size_holder_type const &>(rhs)), counter_(rhs.counter_)
 350     {}
 351
 352     heap_base & operator=(heap_base && rhs) BOOST_NOEXCEPT_IF(boost::is_nothrow_move_assignable<Cmp>::value)
 353     {
 354         value_comp_ref().operator=(std::move(rhs.value_comp_ref()));
 355         size_holder_type::operator=(std::move(static_cast<size_holder_type&>(rhs)));
 356
 357         counter_ = rhs.counter_;
 358         rhs.counter_ = 0;
 359         return *this;
 360     }
 361
 362     heap_base & operator=(heap_base const & rhs)
 363     {
 364         value_comp_ref().operator=(rhs.value_comp());
 365         size_holder_type::operator=(static_cast<size_holder_type const &>(rhs));
 366
 367         counter_ = rhs.counter_;
 368         return *this;
 369     }
 370 #endif
 371
 372     bool operator()(internal_type const & lhs, internal_type const & rhs) const
 373     {
 374         return get_internal_cmp()(lhs, rhs);
 375     }
 376
 377     bool operator()(T const & lhs, T const & rhs) const
 378     {
 379         return value_comp()(lhs, rhs);
 380     }
 381
 382     internal_type make_node(T const & val)
 383     {
 384         stability_counter_type count = ++counter_;
 385         if (counter_ == (std::numeric_limits<stability_counter_type>::max)())
 386             BOOST_THROW_EXCEPTION(std::runtime_error("boost::heap counter overflow"));
 387         return internal_type(count, val);
 388     }
 389
 390 #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES) && !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
 391     template <class... Args>
 392     internal_type make_node(Args&&... args)
 393     {
 394         stability_counter_type count = ++counter_;
 395         if (counter_ == (std::numeric_limits<stability_counter_type>::max)())
 396             BOOST_THROW_EXCEPTION(std::runtime_error("boost::heap counter overflow"));
 397         return internal_type (count, std::forward<Args>(args)...);
 398     }
 399 #endif
 400
 401     static T & get_value(internal_type & val) BOOST_NOEXCEPT
 402     {
 403         return val.first;
 404     }
 405
 406     static T const & get_value(internal_type const & val) BOOST_NOEXCEPT
 407     {
 408         return val.first;
 409     }
 410
 411     Cmp const & value_comp(void) const BOOST_NOEXCEPT
 412     {
 413 #ifndef BOOST_MSVC
 414         return *this;
 415 #else
 416         return cmp_;
 417 #endif
 418     }
 419
 420     struct internal_compare:
 421         Cmp
 422     {
 423         internal_compare(Cmp const & cmp = Cmp()):
 424             Cmp(cmp)
 425         {}
 426
 427         bool operator()(internal_type const & lhs, internal_type const & rhs) const
 428         {
 429             if (Cmp::operator()(lhs.first, rhs.first))
 430                 return true;
 431
 432             if (Cmp::operator()(rhs.first, lhs.first))
 433                 return false;
 434
 435             return lhs.second > rhs.second;
 436         }
 437     };
 438
 439     internal_compare get_internal_cmp(void) const
 440     {
 441         return internal_compare(value_comp());
 442     }
 443
 444     void swap(heap_base & rhs) BOOST_NOEXCEPT_IF(boost::is_nothrow_move_constructible<Cmp>::value && boost::is_nothrow_move_assignable<Cmp>::value)
 445     {
 446 #ifndef BOOST_MSVC
 447         std::swap(static_cast<Cmp&>(*this), static_cast<Cmp&>(rhs));
 448 #else
 449         std::swap(cmp_, rhs.cmp_);
 450 #endif
 451         std::swap(counter_, rhs.counter_);
 452         size_holder<constant_time_size, size_t>::swap(rhs);
 453     }
 454
 455     stability_counter_type get_stability_count(void) const
 456     {
 457         return counter_;
 458     }
 459
 460     void set_stability_count(stability_counter_type new_count)
 461     {
 462         counter_ = new_count;
 463     }
 464
 465     template <typename Heap1, typename Heap2>
 466     friend struct heap_merge_emulate;
 467
 468 private:
 469     Cmp & value_comp_ref(void) BOOST_NOEXCEPT
 470     {
 471 #ifndef BOOST_MSVC
 472         return *this;
 473 #else
 474         return cmp_;
 475 #endif
 476     }
 477
 478     stability_counter_type counter_;
 479 };
 480
 481 template <typename node_pointer,
 482           typename extractor,
 483           typename reference
 484          >
 485 struct node_handle
 486 {
 487     explicit node_handle(node_pointer n = 0):
 488         node_(n)
 489     {}
 490
 491     reference operator*() const
 492     {
 493         return extractor::get_value(node_->value);
 494     }
 495
 496     bool operator==(node_handle const & rhs) const
 497     {
 498         return node_ == rhs.node_;
 499     }
 500
 501     bool operator!=(node_handle const & rhs) const
 502     {
 503         return node_ != rhs.node_;
 504     }
 505
 506     node_pointer node_;
 507 };
 508
 509 template <typename value_type,
 510           typename internal_type,
 511           typename extractor
 512          >
 513 struct value_extractor
 514 {
 515     value_type const & operator()(internal_type const & data) const
 516     {
 517         return extractor::get_value(data);
 518     }
 519 };
 520
 521 template <typename T,
 522           typename ContainerIterator,
 523           typename Extractor>
 524 class stable_heap_iterator:
 525     public boost::iterator_adaptor<stable_heap_iterator<T, ContainerIterator, Extractor>,
 526                                    ContainerIterator,
 527                                    T const,
 528                                    boost::random_access_traversal_tag>
 529 {
 530     typedef boost::iterator_adaptor<stable_heap_iterator,
 531                                     ContainerIterator,
 532                                     T const,
 533                                     boost::random_access_traversal_tag> super_t;
 534
 535 public:
 536     stable_heap_iterator(void):
 537         super_t(0)
 538     {}
 539
 540     explicit stable_heap_iterator(ContainerIterator const & it):
 541         super_t(it)
 542     {}
 543
 544 private:
 545     friend class boost::iterator_core_access;
 546
 547     T const & dereference() const
 548     {
 549         return Extractor::get_value(*super_t::base());
 550     }
 551 };
 552
 553 template <typename T, typename Parspec, bool constant_time_size>
 554 struct make_heap_base
 555 {
 556     typedef typename parameter::binding<Parspec, tag::compare, std::less<T> >::type compare_argument;
 557     typedef typename parameter::binding<Parspec, tag::allocator, std::allocator<T> >::type allocator_argument;
 558     typedef typename parameter::binding<Parspec, tag::stability_counter_type, boost::uintmax_t >::type stability_counter_type;
 559
 560     static const bool is_stable = extract_stable<Parspec>::value;
 561
 562     typedef heap_base<T, compare_argument, constant_time_size, stability_counter_type, is_stable> type;
 563 };
 564
 565
 566 template <typename Alloc>
 567 struct extract_allocator_types
 568 {
 569     typedef typename Alloc::size_type size_type;
 570     typedef typename Alloc::difference_type difference_type;
 571     typedef typename Alloc::reference reference;
 572     typedef typename Alloc::const_reference const_reference;
 573     typedef typename Alloc::pointer pointer;
 574     typedef typename Alloc::const_pointer const_pointer;
 575 };
 576
 577
 578 } /* namespace detail */
 579 } /* namespace heap */
 580 } /* namespace boost */
 581
 582 #endif /* BOOST_HEAP_DETAIL_STABLE_HEAP_HPP */