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