← Back to branch summary

~ubuntu-branches/ubuntu/wily/ruby-passenger/wily-proposed

« back to all changes in this revision

Viewing changes to ext/boost/unordered/detail/util.hpp

  • Committer: Package Import Robot
  • Author(s): Felix Geyer
  • Date: 2013-11-23 23:50:02 UTC
  • mfrom: (1.1.4)
  • Revision ID: package-import@ubuntu.com-20131123235002-8fdhsq7afj15o2z2
Tags: 4.0.25-1
http://bugs.debian.org/725591
* New upstream release.
* Refresh fix_install_path.patch.
* Build for Ruby 2.0 instead of 1.8. (Closes: #725591)
* Add fix_ftbfs_fortify_source.patch.
* Install passenger template files.

Show diffs side-by-side

added added

removed removed

Lines of Context:
ext/boost/unordered/detail/util.hpp
 
1
 
 
2
// Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard.
 
3
// Copyright (C) 2005-2011 Daniel James
 
4
// Distributed under the Boost Software License, Version 1.0. (See accompanying
 
5
// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
 
6
 
 
7
#ifndef BOOST_UNORDERED_DETAIL_UTIL_HPP_INCLUDED
 
8
#define BOOST_UNORDERED_DETAIL_UTIL_HPP_INCLUDED
 
9
 
 
10
#if defined(_MSC_VER) && (_MSC_VER >= 1020)
 
11
# pragma once
 
12
#endif
 
13
 
 
14
#include <boost/type_traits/is_convertible.hpp>
 
15
#include <boost/type_traits/is_empty.hpp>
 
16
#include <boost/iterator/iterator_categories.hpp>
 
17
#include <boost/utility/enable_if.hpp>
 
18
#include <boost/detail/select_type.hpp>
 
19
#include <boost/move/move.hpp>
 
20
#include <boost/preprocessor/seq/size.hpp>
 
21
#include <boost/preprocessor/seq/enum.hpp>
 
22
#include <boost/swap.hpp>
 
23
 
 
24
namespace boost { namespace unordered { namespace detail {
 
25
 
 
26
    static const float minimum_max_load_factor = 1e-3f;
 
27
    static const std::size_t default_bucket_count = 11;
 
28
    struct move_tag {};
 
29
    struct empty_emplace {};
 
30
 
 
31
    ////////////////////////////////////////////////////////////////////////////
 
32
    // iterator SFINAE
 
33
 
 
34
    template <typename I>
 
35
    struct is_forward :
 
36
        boost::is_convertible<
 
37
            typename boost::iterator_traversal<I>::type,
 
38
            boost::forward_traversal_tag>
 
39
    {};
 
40
 
 
41
    template <typename I, typename ReturnType>
 
42
    struct enable_if_forward :
 
43
        boost::enable_if_c<
 
44
            boost::unordered::detail::is_forward<I>::value,
 
45
            ReturnType>
 
46
    {};
 
47
 
 
48
    template <typename I, typename ReturnType>
 
49
    struct disable_if_forward :
 
50
        boost::disable_if_c<
 
51
            boost::unordered::detail::is_forward<I>::value,
 
52
            ReturnType>
 
53
    {};
 
54
 
 
55
    ////////////////////////////////////////////////////////////////////////////
 
56
    // primes
 
57
 
 
58
#define BOOST_UNORDERED_PRIMES \
 
59
    (17ul)(29ul)(37ul)(53ul)(67ul)(79ul) \
 
60
    (97ul)(131ul)(193ul)(257ul)(389ul)(521ul)(769ul) \
 
61
    (1031ul)(1543ul)(2053ul)(3079ul)(6151ul)(12289ul)(24593ul) \
 
62
    (49157ul)(98317ul)(196613ul)(393241ul)(786433ul) \
 
63
    (1572869ul)(3145739ul)(6291469ul)(12582917ul)(25165843ul) \
 
64
    (50331653ul)(100663319ul)(201326611ul)(402653189ul)(805306457ul) \
 
65
    (1610612741ul)(3221225473ul)(4294967291ul)
 
66
 
 
67
    template<class T> struct prime_list_template
 
68
    {
 
69
        static std::size_t const value[];
 
70
 
 
71
#if !defined(SUNPRO_CC)
 
72
        static std::ptrdiff_t const length;
 
73
#else
 
74
        static std::ptrdiff_t const length
 
75
            = BOOST_PP_SEQ_SIZE(BOOST_UNORDERED_PRIMES);
 
76
#endif
 
77
    };
 
78
 
 
79
    template<class T>
 
80
    std::size_t const prime_list_template<T>::value[] = {
 
81
        BOOST_PP_SEQ_ENUM(BOOST_UNORDERED_PRIMES)
 
82
    };
 
83
 
 
84
#if !defined(SUNPRO_CC)
 
85
    template<class T>
 
86
    std::ptrdiff_t const prime_list_template<T>::length
 
87
        = BOOST_PP_SEQ_SIZE(BOOST_UNORDERED_PRIMES);
 
88
#endif
 
89
 
 
90
#undef BOOST_UNORDERED_PRIMES
 
91
 
 
92
    typedef prime_list_template<std::size_t> prime_list;
 
93
 
 
94
    // no throw
 
95
    inline std::size_t next_prime(std::size_t num) {
 
96
        std::size_t const* const prime_list_begin = prime_list::value;
 
97
        std::size_t const* const prime_list_end = prime_list_begin +
 
98
            prime_list::length;
 
99
        std::size_t const* bound =
 
100
            std::lower_bound(prime_list_begin, prime_list_end, num);
 
101
        if(bound == prime_list_end)
 
102
            bound--;
 
103
        return *bound;
 
104
    }
 
105
 
 
106
    // no throw
 
107
    inline std::size_t prev_prime(std::size_t num) {
 
108
        std::size_t const* const prime_list_begin = prime_list::value;
 
109
        std::size_t const* const prime_list_end = prime_list_begin +
 
110
            prime_list::length;
 
111
        std::size_t const* bound =
 
112
            std::upper_bound(prime_list_begin,prime_list_end, num);
 
113
        if(bound != prime_list_begin)
 
114
            bound--;
 
115
        return *bound;
 
116
    }
 
117
 
 
118
    ////////////////////////////////////////////////////////////////////////////
 
119
    // insert_size/initial_size
 
120
 
 
121
#if !defined(BOOST_NO_STD_DISTANCE)
 
122
 
 
123
    using ::std::distance;
 
124
 
 
125
#else
 
126
 
 
127
    template <class ForwardIterator>
 
128
    inline std::size_t distance(ForwardIterator i, ForwardIterator j) {
 
129
        std::size_t x;
 
130
        std::distance(i, j, x);
 
131
        return x;
 
132
    }
 
133
 
 
134
#endif
 
135
 
 
136
    template <class I>
 
137
    inline typename
 
138
        boost::unordered::detail::enable_if_forward<I, std::size_t>::type
 
139
        insert_size(I i, I j)
 
140
    {
 
141
        return std::distance(i, j);
 
142
    }
 
143
 
 
144
    template <class I>
 
145
    inline typename
 
146
        boost::unordered::detail::disable_if_forward<I, std::size_t>::type
 
147
        insert_size(I, I)
 
148
    {
 
149
        return 1;
 
150
    }
 
151
 
 
152
    template <class I>
 
153
    inline std::size_t initial_size(I i, I j,
 
154
        std::size_t num_buckets =
 
155
            boost::unordered::detail::default_bucket_count)
 
156
    {
 
157
        // TODO: Why +1?
 
158
        return (std::max)(
 
159
            boost::unordered::detail::insert_size(i, j) + 1,
 
160
            num_buckets);
 
161
    }
 
162
 
 
163
    ////////////////////////////////////////////////////////////////////////////
 
164
    // compressed
 
165
 
 
166
    template <typename T, int Index>
 
167
    struct compressed_base : private T
 
168
    {
 
169
        compressed_base(T const& x) : T(x) {}
 
170
        compressed_base(T& x, move_tag) : T(boost::move(x)) {}
 
171
 
 
172
        T& get() { return *this; }
 
173
        T const& get() const { return *this; }
 
174
    };
 
175
    
 
176
    template <typename T, int Index>
 
177
    struct uncompressed_base
 
178
    {
 
179
        uncompressed_base(T const& x) : value_(x) {}
 
180
        uncompressed_base(T& x, move_tag) : value_(boost::move(x)) {}
 
181
 
 
182
        T& get() { return value_; }
 
183
        T const& get() const { return value_; }
 
184
    private:
 
185
        T value_;
 
186
    };
 
187
    
 
188
    template <typename T, int Index>
 
189
    struct generate_base
 
190
      : boost::detail::if_true<
 
191
            boost::is_empty<T>::value
 
192
        >:: BOOST_NESTED_TEMPLATE then<
 
193
            boost::unordered::detail::compressed_base<T, Index>,
 
194
            boost::unordered::detail::uncompressed_base<T, Index>
 
195
        >
 
196
    {};
 
197
    
 
198
    template <typename T1, typename T2>
 
199
    struct compressed
 
200
      : private boost::unordered::detail::generate_base<T1, 1>::type,
 
201
        private boost::unordered::detail::generate_base<T2, 2>::type
 
202
    {
 
203
        typedef typename generate_base<T1, 1>::type base1;
 
204
        typedef typename generate_base<T2, 2>::type base2;
 
205
 
 
206
        typedef T1 first_type;
 
207
        typedef T2 second_type;
 
208
        
 
209
        first_type& first() {
 
210
            return static_cast<base1*>(this)->get();
 
211
        }
 
212
 
 
213
        first_type const& first() const {
 
214
            return static_cast<base1 const*>(this)->get();
 
215
        }
 
216
 
 
217
        second_type& second() {
 
218
            return static_cast<base2*>(this)->get();
 
219
        }
 
220
 
 
221
        second_type const& second() const {
 
222
            return static_cast<base2 const*>(this)->get();
 
223
        }
 
224
 
 
225
        template <typename First, typename Second>
 
226
        compressed(First const& x1, Second const& x2)
 
227
            : base1(x1), base2(x2) {}
 
228
 
 
229
        compressed(compressed const& x)
 
230
            : base1(x.first()), base2(x.second()) {}
 
231
 
 
232
        compressed(compressed& x, move_tag m)
 
233
            : base1(x.first(), m), base2(x.second(), m) {}
 
234
 
 
235
        void assign(compressed const& x)
 
236
        {
 
237
            first() = x.first();
 
238
            second() = x.second();
 
239
        }
 
240
 
 
241
        void move_assign(compressed& x)
 
242
        {
 
243
            first() = boost::move(x.first());
 
244
            second() = boost::move(x.second());
 
245
        }
 
246
        
 
247
        void swap(compressed& x)
 
248
        {
 
249
            boost::swap(first(), x.first());
 
250
            boost::swap(second(), x.second());
 
251
        }
 
252
 
 
253
    private:
 
254
        // Prevent assignment just to make use of assign or
 
255
        // move_assign explicit.
 
256
        compressed& operator=(compressed const&);
 
257
    };
 
258
}}}
 
259
 
 
260
#endif