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 ***** */
44 #include "jsstaticcheck.h"
49 /* Gross special case for Gecko, which defines malloc/calloc/free. */
50 #ifdef mozilla_mozalloc_macro_wrappers_h
51 # define JSSTL_UNDEFD_MOZALLOC_WRAPPERS
52 /* The "anti-header" */
53 # include "mozilla/mozalloc_undef_macro_wrappers.h"
58 /* JavaScript Template Library. */
61 /* Compute min/max/clamp. */
62 template <size_t i
, size_t j
> struct Min
{
63 static const size_t result
= i
< j
? i
: j
;
65 template <size_t i
, size_t j
> struct Max
{
66 static const size_t result
= i
> j
? i
: j
;
68 template <size_t i
, size_t min
, size_t max
> struct Clamp
{
69 static const size_t result
= i
< min
? min
: (i
> max
? max
: i
);
73 template <size_t x
, size_t y
> struct Pow
{
74 static const size_t result
= x
* Pow
<x
, y
- 1>::result
;
76 template <size_t x
> struct Pow
<x
,0> {
77 static const size_t result
= 1;
80 /* Compute floor(log2(i)). */
81 template <size_t i
> struct FloorLog2
{
82 static const size_t result
= 1 + FloorLog2
<i
/ 2>::result
;
84 template <> struct FloorLog2
<0> { /* Error */ };
85 template <> struct FloorLog2
<1> { static const size_t result
= 0; };
87 /* Compute ceiling(log2(i)). */
88 template <size_t i
> struct CeilingLog2
{
89 static const size_t result
= FloorLog2
<2 * i
- 1>::result
;
92 /* Round up to the nearest power of 2. */
93 template <size_t i
> struct RoundUpPow2
{
94 static const size_t result
= 1u << CeilingLog2
<i
>::result
;
96 template <> struct RoundUpPow2
<0> {
97 static const size_t result
= 1;
100 /* Compute the number of bits in the given unsigned type. */
101 template <class T
> struct BitSize
{
102 static const size_t result
= sizeof(T
) * JS_BITS_PER_BYTE
;
105 /* Allow Assertions by only including the 'result' typedef if 'true'. */
106 template <bool> struct StaticAssert
{};
107 template <> struct StaticAssert
<true> { typedef int result
; };
109 /* Boolean test for whether two types are the same. */
110 template <class T
, class U
> struct IsSameType
{
111 static const bool result
= false;
113 template <class T
> struct IsSameType
<T
,T
> {
114 static const bool result
= true;
118 * Produce an N-bit mask, where N <= BitSize<size_t>::result. Handle the
119 * language-undefined edge case when N = BitSize<size_t>::result.
121 template <size_t N
> struct NBitMask
{
122 typedef typename StaticAssert
<N
< BitSize
<size_t>::result
>::result _
;
123 static const size_t result
= (size_t(1) << N
) - 1;
125 template <> struct NBitMask
<BitSize
<size_t>::result
> {
126 static const size_t result
= size_t(-1);
130 * For the unsigned integral type size_t, compute a mask M for N such that
131 * for all X, !(X & M) implies X * N will not overflow (w.r.t size_t)
133 template <size_t N
> struct MulOverflowMask
{
134 static const size_t result
=
135 ~NBitMask
<BitSize
<size_t>::result
- CeilingLog2
<N
>::result
>::result
;
137 template <> struct MulOverflowMask
<0> { /* Error */ };
138 template <> struct MulOverflowMask
<1> { static const size_t result
= 0; };
141 * Generate a mask for T such that if (X & sUnsafeRangeSizeMask), an X-sized
142 * array of T's is big enough to cause a ptrdiff_t overflow when subtracting
143 * a pointer to the end of the array from the beginning.
145 template <class T
> struct UnsafeRangeSizeMask
{
147 * The '2' factor means the top bit is clear, sizeof(T) converts from
148 * units of elements to bytes.
150 static const size_t result
= MulOverflowMask
<2 * sizeof(T
)>::result
;
153 /* Return T stripped of any const-ness. */
154 template <class T
> struct StripConst
{ typedef T result
; };
155 template <class T
> struct StripConst
<const T
> { typedef T result
; };
158 * Traits class for identifying POD types. Until C++0x, there is no automatic
159 * way to detect PODs, so for the moment it is done manually.
161 template <class T
> struct IsPodType
{ static const bool result
= false; };
162 template <> struct IsPodType
<char> { static const bool result
= true; };
163 template <> struct IsPodType
<signed char> { static const bool result
= true; };
164 template <> struct IsPodType
<unsigned char> { static const bool result
= true; };
165 template <> struct IsPodType
<short> { static const bool result
= true; };
166 template <> struct IsPodType
<unsigned short> { static const bool result
= true; };
167 template <> struct IsPodType
<int> { static const bool result
= true; };
168 template <> struct IsPodType
<unsigned int> { static const bool result
= true; };
169 template <> struct IsPodType
<long> { static const bool result
= true; };
170 template <> struct IsPodType
<unsigned long> { static const bool result
= true; };
171 template <> struct IsPodType
<float> { static const bool result
= true; };
172 template <> struct IsPodType
<double> { static const bool result
= true; };
174 /* Return the size/end of an array without using macros. */
175 template <class T
, size_t N
> inline T
*ArraySize(T (&)[N
]) { return N
; }
176 template <class T
, size_t N
> inline T
*ArrayEnd(T (&arr
)[N
]) { return arr
+ N
; }
180 /* Useful for implementing containers that assert non-reentrancy */
181 class ReentrancyGuard
183 /* ReentrancyGuard is not copyable. */
184 ReentrancyGuard(const ReentrancyGuard
&);
185 void operator=(const ReentrancyGuard
&);
193 ReentrancyGuard(T
&obj
)
194 : entered(obj
.entered
)
196 ReentrancyGuard(T
&/*obj*/)
213 * Round x up to the nearest power of 2. This function assumes that the most
214 * significant bit of x is not set, which would lead to overflow.
216 STATIC_POSTCONDITION_ASSUME(return >= x
)
217 JS_ALWAYS_INLINE
size_t
218 RoundUpPow2(size_t x
)
220 size_t log2
= JS_CEILING_LOG2W(x
);
221 JS_ASSERT(log2
< tl::BitSize
<size_t>::result
);
222 size_t result
= size_t(1) << log2
;
227 * Safely subtract two pointers when it is known that end > begin. This avoids
228 * the common compiler bug that if (size_t(end) - size_t(begin)) has the MSB
229 * set, the unsigned subtraction followed by right shift will produce -1, or
230 * size_t(-1), instead of the real difference.
233 JS_ALWAYS_INLINE
size_t
234 PointerRangeSize(T
*begin
, T
*end
)
236 return (size_t(end
) - size_t(begin
)) / sizeof(T
);
240 * Allocation policies. These model the concept:
241 * - public copy constructor, assignment, destructor
242 * - void *malloc(size_t)
243 * Responsible for OOM reporting on NULL return value.
244 * - void *realloc(size_t)
245 * Responsible for OOM reporting on NULL return value.
246 * - void free(void *)
247 * - reportAllocOverflow()
248 * Called on overflow before the container returns NULL.
251 /* Policy for using system memory functions and doing no error reporting. */
252 class SystemAllocPolicy
255 void *malloc(size_t bytes
) { return js_malloc(bytes
); }
256 void *realloc(void *p
, size_t bytes
) { return js_realloc(p
, bytes
); }
257 void free(void *p
) { js_free(p
); }
258 void reportAllocOverflow() const {}
262 * This utility pales in comparison to Boost's aligned_storage. The utility
263 * simply assumes that JSUint64 is enough alignment for anyone. This may need
264 * to be extended one day...
266 * As an important side effect, pulling the storage into this template is
267 * enough obfuscation to confuse gcc's strict-aliasing analysis into not giving
268 * false negatives when we cast from the char buffer to whatever type we've
269 * constructed using the bytes.
271 template <size_t nbytes
>
272 struct AlignedStorage
279 const void *addr() const { return u
.bytes
; }
280 void *addr() { return u
.bytes
; }
284 struct AlignedStorage2
287 char bytes
[sizeof(T
)];
291 const T
*addr() const { return (const T
*)u
.bytes
; }
292 T
*addr() { return (T
*)u
.bytes
; }
296 * Small utility for lazily constructing objects without using dynamic storage.
297 * When a LazilyConstructed<T> is constructed, it is |empty()|, i.e., no value
298 * of T has been constructed and no T destructor will be called when the
299 * LazilyConstructed<T> is destroyed. Upon calling |construct|, a T object will
300 * be constructed with the given arguments and that object will be destroyed
301 * when the owning LazilyConstructed<T> is destroyed.
303 * N.B. GCC seems to miss some optimizations with LazilyConstructed and may
304 * generate extra branches/loads/stores. Use with caution on hot paths.
307 class LazilyConstructed
309 AlignedStorage2
<T
> storage
;
312 T
&asT() { return *storage
.addr(); }
315 LazilyConstructed() { constructed
= false; }
316 ~LazilyConstructed() { if (constructed
) asT().~T(); }
318 bool empty() const { return !constructed
; }
321 JS_ASSERT(!constructed
);
322 new(storage
.addr()) T();
327 void construct(const T1
&t1
) {
328 JS_ASSERT(!constructed
);
329 new(storage
.addr()) T(t1
);
333 template <class T1
, class T2
>
334 void construct(const T1
&t1
, const T2
&t2
) {
335 JS_ASSERT(!constructed
);
336 new(storage
.addr()) T(t1
, t2
);
340 template <class T1
, class T2
, class T3
>
341 void construct(const T1
&t1
, const T2
&t2
, const T3
&t3
) {
342 JS_ASSERT(!constructed
);
343 new(storage
.addr()) T(t1
, t2
, t3
);
347 template <class T1
, class T2
, class T3
, class T4
>
348 void construct(const T1
&t1
, const T2
&t2
, const T3
&t3
, const T4
&t4
) {
349 JS_ASSERT(!constructed
);
350 new(storage
.addr()) T(t1
, t2
, t3
, t4
);
355 JS_ASSERT(constructed
);
360 JS_ASSERT(constructed
);
372 * N.B. GCC seems to miss some optimizations with Conditionally and may
373 * generate extra branches/loads/stores. Use with caution on hot paths.
376 class Conditionally
{
377 LazilyConstructed
<T
> t
;
380 Conditionally(bool b
) { if (b
) t
.construct(); }
383 Conditionally(bool b
, const T1
&t1
) { if (b
) t
.construct(t1
); }
385 template <class T1
, class T2
>
386 Conditionally(bool b
, const T1
&t1
, const T2
&t2
) { if (b
) t
.construct(t1
, t2
); }
390 class AlignedPtrAndFlag
395 AlignedPtrAndFlag(T
*t
, bool flag
) {
396 JS_ASSERT((uintptr_t(t
) & 1) == 0);
397 bits
= uintptr_t(t
) | uintptr_t(flag
);
401 return (T
*)(bits
& ~uintptr_t(1));
405 return (bits
& 1) != 0;
409 JS_ASSERT((uintptr_t(t
) & 1) == 0);
410 bits
= uintptr_t(t
) | uintptr_t(flag());
418 bits
&= ~uintptr_t(1);
421 void set(T
*t
, bool flag
) {
422 JS_ASSERT((uintptr_t(t
) & 1) == 0);
423 bits
= uintptr_t(t
) | flag
;
429 Reverse(T
*beg
, T
*end
)
443 Find(T
*beg
, T
*end
, const T
&v
)
445 for (T
*p
= beg
; p
!= end
; ++p
) {
452 template <class Container
>
453 static inline typename
Container::ElementType
*
454 Find(Container
&c
, const typename
Container::ElementType
&v
)
456 return Find(c
.begin(), c
.end(), v
);
459 template <typename InputIterT
, typename CallableT
>
461 ForEach(InputIterT begin
, InputIterT end
, CallableT f
)
463 for (; begin
!= end
; ++begin
)
471 return t1
< t2
? t1
: t2
;
478 return t1
> t2
? t1
: t2
;
481 /* Allows a const variable to be initialized after its declaration. */
484 InitConst(const T
&t
)
486 return const_cast<T
&>(t
);
491 #ifdef JSSTL_UNDEFD_MOZALLOC_WRAPPERS
492 # include "mozilla/mozalloc_macro_wrappers.h"