← Back to branch summary

~alinuxninja/nginx-edge/trunk

« back to all changes in this revision

Viewing changes to debian/modules/ngx_pagespeed/psol/include/third_party/rdestl/algorithm.h

  • Committer: Vivian
  • Date: 2015-12-04 18:20:11 UTC
  • Revision ID: git-v1:a36f2bc32e884f7473b3a47040e5411306144d7d
* Do not extract psol.tar.gz

Show diffs side-by-side

added added

removed removed

Lines of Context:
debian/modules/ngx_pagespeed/psol/include/third_party/rdestl/algorithm.h
1
 
#ifndef RDESTL_ALGORITHM_H
2
 
#define RDESTL_ALGORITHM_H
3
 
 
4
 
#include "int_to_type.h"
5
 
#include "iterator.h"
6
 
#include "type_traits.h"
7
 
#include "utility.h"
8
 
 
9
 
namespace rde
10
 
{
11
 
 
12
 
//-----------------------------------------------------------------------------
13
 
template<typename T> RDE_FORCEINLINE
14
 
void copy_construct(T* mem, const T& orig)
15
 
{
16
 
        //new (mem) T(orig);
17
 
        internal::copy_construct(mem, orig, int_to_type<has_trivial_copy<T>::value>());
18
 
}
19
 
 
20
 
//-----------------------------------------------------------------------------
21
 
template<typename T> RDE_FORCEINLINE
22
 
void construct(T* mem)
23
 
{
24
 
        internal::construct(mem, int_to_type<has_trivial_constructor<T>::value>());
25
 
}
26
 
 
27
 
//-----------------------------------------------------------------------------
28
 
template<typename T> RDE_FORCEINLINE
29
 
void destruct(T* mem)
30
 
{
31
 
        internal::destruct(mem, int_to_type<has_trivial_destructor<T>::value>());
32
 
}
33
 
 
34
 
//-----------------------------------------------------------------------------
35
 
template<typename T>
36
 
void copy_n(const T* first, size_t n, T* result)
37
 
{
38
 
        internal::copy_n(first, n, result, int_to_type<has_trivial_copy<T>::value>());
39
 
}
40
 
 
41
 
//-----------------------------------------------------------------------------
42
 
template<typename T>
43
 
void copy(const T* first, const T* last, T* result)
44
 
{
45
 
        internal::copy(first, last, result, int_to_type<has_trivial_copy<T>::value>());
46
 
}
47
 
 
48
 
//-----------------------------------------------------------------------------
49
 
template<typename T>
50
 
void copy_construct_n(T* first, size_t n, T* result)
51
 
{
52
 
        internal::copy_construct_n(first, n, result, int_to_type<has_trivial_copy<T>::value>());
53
 
}
54
 
 
55
 
//-----------------------------------------------------------------------------
56
 
template<typename T>
57
 
void move_n(const T* from, size_t n, T* result)
58
 
{
59
 
        RDE_ASSERT(from != result || n == 0);
60
 
        // Overlap? 
61
 
        if (result + n >= from && result < from + n)
62
 
        {
63
 
                internal::move_n(from, n, result, int_to_type<has_trivial_copy<T>::value>());
64
 
        }
65
 
        else
66
 
        {
67
 
                internal::copy_n(from, n, result, int_to_type<has_trivial_copy<T>::value>());
68
 
        }
69
 
}
70
 
 
71
 
//-----------------------------------------------------------------------------
72
 
template<typename T>
73
 
inline void move(const T* first, const T* last, T* result)
74
 
{
75
 
        RDE_ASSERT(first != result || first == last);
76
 
        const size_t n = reinterpret_cast<uintptr_t>(last) - reinterpret_cast<uintptr_t>(first);
77
 
        const unsigned char* resultEnd = reinterpret_cast<const unsigned char*>(result) + n;
78
 
        if (resultEnd >= reinterpret_cast<const unsigned char*>(first) && result < last)
79
 
        {
80
 
                internal::move(first, last, result, int_to_type<has_trivial_copy<T>::value>());
81
 
        }
82
 
        else
83
 
        {
84
 
                internal::copy(first, last, result, int_to_type<has_trivial_copy<T>::value>());
85
 
        }
86
 
}
87
 
 
88
 
//-----------------------------------------------------------------------------
89
 
template<typename T>
90
 
void construct_n(T* first, size_t n)
91
 
{
92
 
        internal::construct_n(first, n, int_to_type<has_trivial_constructor<T>::value>());
93
 
}
94
 
 
95
 
//-----------------------------------------------------------------------------
96
 
template<typename T>
97
 
void destruct_n(T* first, size_t n)
98
 
{
99
 
        internal::destruct_n(first, n, int_to_type<has_trivial_destructor<T>::value>());
100
 
}
101
 
 
102
 
//-----------------------------------------------------------------------------
103
 
template<typename T> RDE_FORCEINLINE
104
 
void fill_n(T* first, size_t n, const T& val)
105
 
{
106
 
        //for (size_t i = 0; i < n; ++i)
107
 
        //      first[i] = val;
108
 
        // Loop unrolling with Duff's Device.
109
 
        T* last = first + n;
110
 
        switch (n & 0x7)
111
 
        {
112
 
        case 0:
113
 
                while (first != last)
114
 
                {
115
 
                        *first = val; ++first;
116
 
        case 7: *first = val; ++first;
117
 
        case 6: *first = val; ++first;
118
 
        case 5: *first = val; ++first;
119
 
        case 4: *first = val; ++first;
120
 
        case 3: *first = val; ++first;
121
 
        case 2: *first = val; ++first;
122
 
        case 1: *first = val; ++first;
123
 
                }
124
 
        }
125
 
}
126
 
 
127
 
//-----------------------------------------------------------------------------
128
 
template<typename TIter, typename TDist> inline
129
 
void distance(TIter first, TIter last, TDist& dist)
130
 
{
131
 
        internal::distance(first, last, dist, typename iterator_traits<TIter>::iterator_category());
132
 
}
133
 
 
134
 
//-----------------------------------------------------------------------------
135
 
template<typename TIter, typename TDist> inline
136
 
void advance(TIter& iter, TDist off)
137
 
{
138
 
        internal::advance(iter, off, typename iterator_traits<TIter>::iterator_category());
139
 
}
140
 
 
141
 
//-----------------------------------------------------------------------------
142
 
template<class TIter, typename T, class TPred> inline
143
 
TIter lower_bound(TIter first, TIter last, const T& val, const TPred& pred)
144
 
{
145
 
        internal::test_ordering(first, last, pred);
146
 
        int dist(0);
147
 
        distance(first, last, dist);
148
 
        while (dist > 0)
149
 
        {
150
 
                const int halfDist = dist >> 1;
151
 
                TIter mid = first;
152
 
                advance(mid, halfDist);
153
 
                if (internal::debug_pred(pred, *mid, val))
154
 
                        first = ++mid, dist -= halfDist + 1;
155
 
                else
156
 
                        dist = halfDist;
157
 
        }
158
 
        return first;
159
 
}
160
 
 
161
 
//-----------------------------------------------------------------------------
162
 
template<class TIter, typename T, class TPred> inline
163
 
TIter upper_bound(TIter first, TIter last, const T& val, const TPred& pred)
164
 
{
165
 
        internal::test_ordering(first, last, pred);
166
 
        int dist(0);
167
 
        distance(first, last, dist);
168
 
        while (dist > 0)
169
 
        {
170
 
                const int halfDist = dist >> 1;
171
 
                TIter mid = first;
172
 
                advance(mid, halfDist);
173
 
                if (!internal::debug_pred(pred, val, *mid))
174
 
                        first = ++mid, dist -= halfDist + 1;
175
 
                else
176
 
                        dist = halfDist;
177
 
        }
178
 
        return first;
179
 
}
180
 
 
181
 
//-----------------------------------------------------------------------------
182
 
template<class TIter, typename T>
183
 
TIter find(TIter first, TIter last, const T& val)
184
 
{
185
 
        while (first != last)
186
 
        {
187
 
                if ((*first) == val)
188
 
                        return first;
189
 
                ++first;
190
 
        }
191
 
        return last;
192
 
}
193
 
 
194
 
//-----------------------------------------------------------------------------
195
 
template<class TIter, typename T, class TPred>
196
 
TIter find_if(TIter first, TIter last, const T& val, const TPred& pred)
197
 
{
198
 
        while (first != last)
199
 
        {
200
 
                if (pred(*first, val))
201
 
                        return first;
202
 
                ++first;
203
 
        }
204
 
        return last;
205
 
}
206
 
 
207
 
//-----------------------------------------------------------------------------
208
 
template<class TIter, typename T>
209
 
void accumulate(TIter first, TIter last, T& result)
210
 
{
211
 
        while (first != last)
212
 
        {
213
 
                result += *first;
214
 
                ++first;
215
 
        }
216
 
}
217
 
 
218
 
//-----------------------------------------------------------------------------
219
 
template<typename T>
220
 
T abs(const T& t)
221
 
{
222
 
        return t >= T(0) ? t : -t;
223
 
}
224
 
// No branches, Hacker's Delight way.
225
 
RDE_FORCEINLINE int abs(int x)
226
 
{
227
 
        const int y = x >> 31;
228
 
        return (x ^ y) - y;
229
 
}
230
 
RDE_FORCEINLINE short abs(short x)
231
 
{
232
 
        const short y = x >> 15;
233
 
        return (x ^ y) - y;
234
 
}
235
 
 
236
 
//-----------------------------------------------------------------------------
237
 
template<typename T> inline
238
 
T max(const T& x, const T& y)
239
 
{
240
 
    return x > y ? x : y;
241
 
}
242
 
 
243
 
//-----------------------------------------------------------------------------
244
 
template<typename T> inline
245
 
T min(const T& x, const T& y)
246
 
{
247
 
        return x < y ? x : y;
248
 
}
249
 
// @TODO: determine if it REALLY is quicker than version with branches.
250
 
/*RDE_FORCEINLINE float min(float x, float y)
251
 
{
252
 
        float result;
253
 
        __asm
254
 
        {
255
 
                fld             [x]
256
 
                fld             [y]
257
 
                fcomi   st(0), st(1)
258
 
                fcmovnb st(0), st(1)
259
 
                fstp    [result]
260
 
                fcomp
261
 
        }
262
 
        return result;
263
 
}*/
264
 
 
265
 
//-----------------------------------------------------------------------------
266
 
template<typename TAssignable>
267
 
void swap(TAssignable& a, TAssignable& b)
268
 
{
269
 
        TAssignable tmp(a);
270
 
        a = b;
271
 
        b = tmp;
272
 
}
273
 
 
274
 
} // namespace rde
275
 
 
276
 
//-----------------------------------------------------------------------------
277
 
#endif // #ifndef RDESTL_ALGORITHM_H
278