ceph/src/boost/boost/heap/policies.hpp

   1 // boost heap
   2 //
   3 // Copyright (C) 2010-2011 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_POLICIES_HPP
  10 #define BOOST_HEAP_POLICIES_HPP
  11
  12 #include <boost/parameter.hpp>
  13 #include <boost/mpl/bool.hpp>
  14 #include <boost/mpl/int.hpp>
  15 #include <boost/mpl/void.hpp>
  16 #include <boost/concept_check.hpp>
  17
  18 #ifdef BOOST_HAS_PRAGMA_ONCE
  19 #pragma once
  20 #endif
  21
  22 namespace boost {
  23 namespace heap {
  24
  25 #ifndef BOOST_DOXYGEN_INVOKED
  26 BOOST_PARAMETER_TEMPLATE_KEYWORD(allocator)
  27 BOOST_PARAMETER_TEMPLATE_KEYWORD(compare)
  28
  29 namespace tag { struct stable; }
  30
  31 template <bool T>
  32 struct stable:
  33     boost::parameter::template_keyword<tag::stable, boost::mpl::bool_<T> >
  34 {};
  35
  36 namespace tag { struct mutable_; }
  37
  38 template <bool T>
  39 struct mutable_:
  40     boost::parameter::template_keyword<tag::mutable_, boost::mpl::bool_<T> >
  41 {};
  42
  43
  44 namespace tag { struct constant_time_size; }
  45
  46 template <bool T>
  47 struct constant_time_size:
  48     boost::parameter::template_keyword<tag::constant_time_size, boost::mpl::bool_<T> >
  49 {};
  50
  51 namespace tag { struct store_parent_pointer; }
  52
  53 template <bool T>
  54 struct store_parent_pointer:
  55     boost::parameter::template_keyword<tag::store_parent_pointer, boost::mpl::bool_<T> >
  56 {};
  57
  58 namespace tag { struct arity; }
  59
  60 template <unsigned int T>
  61 struct arity:
  62     boost::parameter::template_keyword<tag::arity, boost::mpl::int_<T> >
  63 {};
  64
  65 namespace tag { struct objects_per_page; }
  66
  67 template <unsigned int T>
  68 struct objects_per_page:
  69     boost::parameter::template_keyword<tag::objects_per_page, boost::mpl::int_<T> >
  70 {};
  71
  72 BOOST_PARAMETER_TEMPLATE_KEYWORD(stability_counter_type)
  73
  74 namespace detail {
  75
  76 namespace mpl = boost::mpl;
  77
  78 template <typename bound_args, typename tag_type>
  79 struct has_arg
  80 {
  81     typedef typename boost::parameter::binding<bound_args, tag_type, mpl::void_>::type type;
  82     static const bool value = mpl::is_not_void_<type>::type::value;
  83 };
  84
  85 template <typename bound_args>
  86 struct extract_stable
  87 {
  88     static const bool has_stable = has_arg<bound_args, tag::stable>::value;
  89
  90     typedef typename mpl::if_c<has_stable,
  91                                typename has_arg<bound_args, tag::stable>::type,
  92                                mpl::bool_<false>
  93                               >::type stable_t;
  94
  95     static const bool value = stable_t::value;
  96 };
  97
  98 template <typename bound_args>
  99 struct extract_mutable
 100 {
 101     static const bool has_mutable = has_arg<bound_args, tag::mutable_>::value;
 102
 103     typedef typename mpl::if_c<has_mutable,
 104                                typename has_arg<bound_args, tag::mutable_>::type,
 105                                mpl::bool_<false>
 106                               >::type mutable_t;
 107
 108     static const bool value = mutable_t::value;
 109 };
 110
 111 }
 112
 113 #else
 114
 115 /** \brief Specifies the predicate for the heap order
 116  */
 117 template <typename T>
 118 struct compare{};
 119
 120 /** \brief Configure heap as mutable
 121  *
 122  *  Certain heaps need to be configured specifically do be mutable.
 123  *
 124  * */
 125 template <bool T>
 126 struct mutable_{};
 127
 128 /** \brief Specifies allocator for the internal memory management
 129  */
 130 template <typename T>
 131 struct allocator{};
 132
 133 /** \brief Configure a heap as \b stable
 134  *
 135  * A priority queue is stable, if elements with the same priority are popped from the heap, in the same order as
 136  * they are inserted.
 137  * */
 138 template <bool T>
 139 struct stable{};
 140
 141 /** \brief Specifies the type for stability counter
 142  *
 143  * */
 144 template <typename IntType>
 145 struct stability_counter_type{};
 146
 147 /** \brief Configures complexity of <tt> size() </tt>
 148  *
 149  * Specifies, whether size() should have linear or constant complexity.
 150  * */
 151 template <bool T>
 152 struct constant_time_size{};
 153
 154 /** \brief Store parent pointer in heap node.
 155  *
 156  * Maintaining a parent pointer adds some maintenance and size overhead, but iterating a heap is more efficient.
 157  * */
 158 template <bool T>
 159 struct store_parent_pointer{};
 160
 161 /** \brief Specify arity.
 162  *
 163  * Specifies the arity of a D-ary heap
 164  * */
 165 template <unsigned int T>
 166 struct arity{};
 167 #endif
 168
 169 } /* namespace heap */
 170 } /* namespace boost */
 171
 172 #endif /* BOOST_HEAP_POLICIES_HPP */