1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*-
2 * vim: set ts=8 sw=4 et tw=99 ft=cpp:
4 * ***** BEGIN LICENSE BLOCK *****
5 * Version: MPL 1.1/GPL 2.0/LGPL 2.1
7 * The contents of this file are subject to the Mozilla Public License Version
8 * 1.1 (the "License"); you may not use this file except in compliance with
9 * the License. You may obtain a copy of the License at
10 * http://www.mozilla.org/MPL/
12 * Software distributed under the License is distributed on an "AS IS" basis,
13 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
14 * for the specific language governing rights and limitations under the
17 * The Original Code is Mozilla SpiderMonkey JavaScript 1.9 code, released
20 * The Initial Developer of the Original Code is
21 * the Mozilla Corporation.
24 * Luke Wagner <lw@mozilla.com>
26 * Alternatively, the contents of this file may be used under the terms of
27 * either of the GNU General Public License Version 2 or later (the "GPL"),
28 * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
29 * in which case the provisions of the GPL or the LGPL are applicable instead
30 * of those above. If you wish to allow use of your version of this file only
31 * under the terms of either the GPL or the LGPL, and not to allow others to
32 * use your version of this file under the terms of the MPL, indicate your
33 * decision by deleting the provisions above and replace them with the notice
34 * and other provisions required by the GPL or the LGPL. If you do not delete
35 * the provisions above, a recipient may use your version of this file under
36 * the terms of any one of the MPL, the GPL or the LGPL.
38 * ***** END LICENSE BLOCK ***** */
50 /* JavaScript Template Library. */
53 /* Compute min/max/clamp. */
54 template <size_t i
, size_t j
> struct Min
{
55 static const size_t result
= i
< j
? i
: j
;
57 template <size_t i
, size_t j
> struct Max
{
58 static const size_t result
= i
> j
? i
: j
;
60 template <size_t i
, size_t min
, size_t max
> struct Clamp
{
61 static const size_t result
= i
< min
? min
: (i
> max
? max
: i
);
65 template <size_t x
, size_t y
> struct Pow
{
66 static const size_t result
= x
* Pow
<x
, y
- 1>::result
;
68 template <size_t x
> struct Pow
<x
,0> {
69 static const size_t result
= 1;
72 /* Compute floor(log2(i)). */
73 template <size_t i
> struct FloorLog2
{
74 static const size_t result
= 1 + FloorLog2
<i
/ 2>::result
;
76 template <> struct FloorLog2
<0> { /* Error */ };
77 template <> struct FloorLog2
<1> { static const size_t result
= 0; };
79 /* Compute ceiling(log2(i)). */
80 template <size_t i
> struct CeilingLog2
{
81 static const size_t result
= FloorLog2
<2 * i
- 1>::result
;
84 /* Round up to the nearest power of 2. */
85 template <size_t i
> struct RoundUpPow2
{
86 static const size_t result
= 1u << CeilingLog2
<i
>::result
;
88 template <> struct RoundUpPow2
<0> {
89 static const size_t result
= 1;
92 /* Compute the number of bits in the given unsigned type. */
93 template <class T
> struct BitSize
{
94 static const size_t result
= sizeof(T
) * JS_BITS_PER_BYTE
;
97 /* Allow Assertions by only including the 'result' typedef if 'true'. */
98 template <bool> struct StaticAssert
{};
99 template <> struct StaticAssert
<true> { typedef int result
; };
101 /* Boolean test for whether two types are the same. */
102 template <class T
, class U
> struct IsSameType
{
103 static const bool result
= false;
105 template <class T
> struct IsSameType
<T
,T
> {
106 static const bool result
= true;
110 * Produce an N-bit mask, where N <= BitSize<size_t>::result. Handle the
111 * language-undefined edge case when N = BitSize<size_t>::result.
113 template <size_t N
> struct NBitMask
{
114 typedef typename StaticAssert
<N
< BitSize
<size_t>::result
>::result _
;
115 static const size_t result
= (size_t(1) << N
) - 1;
117 template <> struct NBitMask
<BitSize
<size_t>::result
> {
118 static const size_t result
= size_t(-1);
122 * For the unsigned integral type size_t, compute a mask M for N such that
123 * for all X, !(X & M) implies X * N will not overflow (w.r.t size_t)
125 template <size_t N
> struct MulOverflowMask
{
126 static const size_t result
=
127 ~NBitMask
<BitSize
<size_t>::result
- CeilingLog2
<N
>::result
>::result
;
129 template <> struct MulOverflowMask
<0> { /* Error */ };
130 template <> struct MulOverflowMask
<1> { static const size_t result
= 0; };
133 * Generate a mask for T such that if (X & sUnsafeRangeSizeMask), an X-sized
134 * array of T's is big enough to cause a ptrdiff_t overflow when subtracting
135 * a pointer to the end of the array from the beginning.
137 template <class T
> struct UnsafeRangeSizeMask
{
139 * The '2' factor means the top bit is clear, sizeof(T) converts from
140 * units of elements to bytes.
142 static const size_t result
= MulOverflowMask
<2 * sizeof(T
)>::result
;
145 /* Return T stripped of any const-ness. */
146 template <class T
> struct StripConst
{ typedef T result
; };
147 template <class T
> struct StripConst
<const T
> { typedef T result
; };
150 * Traits class for identifying POD types. Until C++0x, there is no automatic
151 * way to detect PODs, so for the moment it is done manually.
153 template <class T
> struct IsPodType
{ static const bool result
= false; };
154 template <> struct IsPodType
<char> { static const bool result
= true; };
155 template <> struct IsPodType
<signed char> { static const bool result
= true; };
156 template <> struct IsPodType
<unsigned char> { static const bool result
= true; };
157 template <> struct IsPodType
<short> { static const bool result
= true; };
158 template <> struct IsPodType
<unsigned short> { static const bool result
= true; };
159 template <> struct IsPodType
<int> { static const bool result
= true; };
160 template <> struct IsPodType
<unsigned int> { static const bool result
= true; };
161 template <> struct IsPodType
<long> { static const bool result
= true; };
162 template <> struct IsPodType
<unsigned long> { static const bool result
= true; };
163 template <> struct IsPodType
<float> { static const bool result
= true; };
164 template <> struct IsPodType
<double> { static const bool result
= true; };
166 /* Return the size/end of an array without using macros. */
167 template <class T
, size_t N
> inline T
*ArraySize(T (&)[N
]) { return N
; }
168 template <class T
, size_t N
> inline T
*ArrayEnd(T (&arr
)[N
]) { return arr
+ N
; }
172 /* Useful for implementing containers that assert non-reentrancy */
173 class ReentrancyGuard
175 /* ReentrancyGuard is not copyable. */
176 ReentrancyGuard(const ReentrancyGuard
&);
177 void operator=(const ReentrancyGuard
&);
185 ReentrancyGuard(T
&obj
)
186 : entered(obj
.entered
)
188 ReentrancyGuard(T
&/*obj*/)
205 * Round x up to the nearest power of 2. This function assumes that the most
206 * significant bit of x is not set, which would lead to overflow.
208 JS_ALWAYS_INLINE
size_t
209 RoundUpPow2(size_t x
)
211 size_t log2
= JS_CEILING_LOG2W(x
);
212 JS_ASSERT(log2
< tl::BitSize
<size_t>::result
);
213 size_t result
= size_t(1) << log2
;
218 * Safely subtract two pointers when it is known that end > begin. This avoids
219 * the common compiler bug that if (size_t(end) - size_t(begin)) has the MSB
220 * set, the unsigned subtraction followed by right shift will produce -1, or
221 * size_t(-1), instead of the real difference.
224 JS_ALWAYS_INLINE
size_t
225 PointerRangeSize(T
*begin
, T
*end
)
227 return (size_t(end
) - size_t(begin
)) / sizeof(T
);
231 * Allocation policies. These model the concept:
232 * - public copy constructor, assignment, destructor
233 * - void *malloc(size_t)
234 * Responsible for OOM reporting on NULL return value.
235 * - void *realloc(size_t)
236 * Responsible for OOM reporting on NULL return value.
237 * - void free(void *)
238 * - reportAllocOverflow()
239 * Called on overflow before the container returns NULL.
242 /* Policy for using system memory functions and doing no error reporting. */
243 class SystemAllocPolicy
246 void *malloc(size_t bytes
) { return js_malloc(bytes
); }
247 void *realloc(void *p
, size_t bytes
) { return js_realloc(p
, bytes
); }
248 void free(void *p
) { js_free(p
); }
249 void reportAllocOverflow() const {}
253 * This utility pales in comparison to Boost's aligned_storage. The utility
254 * simply assumes that JSUint64 is enough alignment for anyone. This may need
255 * to be extended one day...
257 * As an important side effect, pulling the storage into this template is
258 * enough obfuscation to confuse gcc's strict-aliasing analysis into not giving
259 * false negatives when we cast from the char buffer to whatever type we've
260 * constructed using the bytes.
262 template <size_t nbytes
>
263 struct AlignedStorage
270 const void *addr() const { return u
.bytes
; }
271 void *addr() { return u
.bytes
; }
275 * Small utility for lazily constructing objects without using dynamic storage.
276 * When a LazilyConstructed<T> is constructed, it is |empty()|, i.e., no value
277 * of T has been constructed and no T destructor will be called when the
278 * LazilyConstructed<T> is destroyed. Upon calling |construct|, a T object will
279 * be constructed with the given arguments and that object will be destroyed
280 * when the owning LazilyConstructed<T> is destroyed.
283 class LazilyConstructed
285 AlignedStorage
<sizeof(T
)> storage
;
288 T
&asT() { return *reinterpret_cast<T
*>(storage
.addr()); }
291 LazilyConstructed() { constructed
= false; }
292 ~LazilyConstructed() { if (constructed
) asT().~T(); }
294 bool empty() const { return !constructed
; }
297 JS_ASSERT(!constructed
);
298 new(storage
.addr()) T();
303 void construct(const T1
&t1
) {
304 JS_ASSERT(!constructed
);
305 new(storage
.addr()) T(t1
);
309 template <class T1
, class T2
>
310 void construct(const T1
&t1
, const T2
&t2
) {
311 JS_ASSERT(!constructed
);
312 new(storage
.addr()) T(t1
, t2
);
316 template <class T1
, class T2
, class T3
>
317 void construct(const T1
&t1
, const T2
&t2
, const T3
&t3
) {
318 JS_ASSERT(!constructed
);
319 new(storage
.addr()) T(t1
, t2
, t3
);
324 JS_ASSERT(constructed
);
329 JS_ASSERT(constructed
);
336 class Conditionally
{
337 LazilyConstructed
<T
> t
;
340 Conditionally(bool b
) { if (b
) t
.construct(); }
343 Conditionally(bool b
, const T1
&t1
) { if (b
) t
.construct(t1
); }
347 JS_ALWAYS_INLINE
static void
350 memset(t
, 0, sizeof(T
));
354 JS_ALWAYS_INLINE
static void
355 PodZero(T
*t
, size_t nelem
)
357 memset(t
, 0, nelem
* sizeof(T
));
361 * Arrays implicitly convert to pointers to their first element, which is
362 * dangerous when combined with the above PodZero definitions. Adding an
363 * overload for arrays is ambiguous, so we need another identifier. The
364 * ambiguous overload is left to catch mistaken uses of PodZero; if you get a
365 * compile error involving PodZero and array types, use PodArrayZero instead.
367 template <class T
, size_t N
> static void PodZero(T (&)[N
]); /* undefined */
368 template <class T
, size_t N
> static void PodZero(T (&)[N
], size_t); /* undefined */
370 template <class T
, size_t N
>
371 JS_ALWAYS_INLINE
static void
372 PodArrayZero(T (&t
)[N
])
374 memset(t
, 0, N
* sizeof(T
));