js/src/jstl.h

   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:
   3  *
   4  * ***** BEGIN LICENSE BLOCK *****
   5  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   6  *
   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/
  11  *
  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
  15  * License.
  16  *
  17  * The Original Code is Mozilla SpiderMonkey JavaScript 1.9 code, released
  18  * July 16, 2009.
  19  *
  20  * The Initial Developer of the Original Code is
  21  *   the Mozilla Corporation.
  22  *
  23  * Contributor(s):
  24  *   Luke Wagner <lw@mozilla.com>
  25  *
  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.
  37  *
  38  * ***** END LICENSE BLOCK ***** */
  39
  40 #ifndef jstl_h_
  41 #define jstl_h_
  42
  43 #include "jsbit.h"
  44 #include "jsstaticcheck.h"
  45
  46 #include <new>
  47 #include <string.h>
  48
  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"
  54 #endif
  55
  56 namespace js {
  57
  58 /* JavaScript Template Library. */
  59 namespace tl {
  60
  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;
  64 };
  65 template <size_t i, size_t j> struct Max {
  66     static const size_t result = i > j ? i : j;
  67 };
  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);
  70 };
  71
  72 /* Compute x^y. */
  73 template <size_t x, size_t y> struct Pow {
  74     static const size_t result = x * Pow<x, y - 1>::result;
  75 };
  76 template <size_t x> struct Pow<x,0> {
  77     static const size_t result = 1;
  78 };
  79
  80 /* Compute floor(log2(i)). */
  81 template <size_t i> struct FloorLog2 {
  82     static const size_t result = 1 + FloorLog2<i / 2>::result;
  83 };
  84 template <> struct FloorLog2<0> { /* Error */ };
  85 template <> struct FloorLog2<1> { static const size_t result = 0; };
  86
  87 /* Compute ceiling(log2(i)). */
  88 template <size_t i> struct CeilingLog2 {
  89     static const size_t result = FloorLog2<2 * i - 1>::result;
  90 };
  91
  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;
  95 };
  96 template <> struct RoundUpPow2<0> {
  97     static const size_t result = 1;
  98 };
  99
 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;
 103 };
 104
 105 /* Allow Assertions by only including the 'result' typedef if 'true'. */
 106 template <bool> struct StaticAssert {};
 107 template <> struct StaticAssert<true> { typedef int result; };
 108
 109 /* Boolean test for whether two types are the same. */
 110 template <class T, class U> struct IsSameType {
 111     static const bool result = false;
 112 };
 113 template <class T> struct IsSameType<T,T> {
 114     static const bool result = true;
 115 };
 116
 117 /*
 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.
 120  */
 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;
 124 };
 125 template <> struct NBitMask<BitSize<size_t>::result> {
 126     static const size_t result = size_t(-1);
 127 };
 128
 129 /*
 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)
 132  */
 133 template <size_t N> struct MulOverflowMask {
 134     static const size_t result =
 135         ~NBitMask<BitSize<size_t>::result - CeilingLog2<N>::result>::result;
 136 };
 137 template <> struct MulOverflowMask<0> { /* Error */ };
 138 template <> struct MulOverflowMask<1> { static const size_t result = 0; };
 139
 140 /*
 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.
 144  */
 145 template <class T> struct UnsafeRangeSizeMask {
 146     /*
 147      * The '2' factor means the top bit is clear, sizeof(T) converts from
 148      * units of elements to bytes.
 149      */
 150     static const size_t result = MulOverflowMask<2 * sizeof(T)>::result;
 151 };
 152
 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; };
 156
 157 /*
 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.
 160  */
 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; };
 173
 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; }
 177
 178 } /* namespace tl */
 179
 180 /* Useful for implementing containers that assert non-reentrancy */
 181 class ReentrancyGuard
 182 {
 183     /* ReentrancyGuard is not copyable. */
 184     ReentrancyGuard(const ReentrancyGuard &);
 185     void operator=(const ReentrancyGuard &);
 186
 187 #ifdef DEBUG
 188     bool &entered;
 189 #endif
 190   public:
 191     template <class T>
 192 #ifdef DEBUG
 193     ReentrancyGuard(T &obj)
 194       : entered(obj.entered)
 195 #else
 196     ReentrancyGuard(T &/*obj*/)
 197 #endif
 198     {
 199 #ifdef DEBUG
 200         JS_ASSERT(!entered);
 201         entered = true;
 202 #endif
 203     }
 204     ~ReentrancyGuard()
 205     {
 206 #ifdef DEBUG
 207         entered = false;
 208 #endif
 209     }
 210 };
 211
 212 /*
 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.
 215  */
 216 STATIC_POSTCONDITION_ASSUME(return >= x)
 217 JS_ALWAYS_INLINE size_t
 218 RoundUpPow2(size_t x)
 219 {
 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;
 223     return result;
 224 }
 225
 226 /*
 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.
 231  */
 232 template <class T>
 233 JS_ALWAYS_INLINE size_t
 234 PointerRangeSize(T *begin, T *end)
 235 {
 236     return (size_t(end) - size_t(begin)) / sizeof(T);
 237 }
 238
 239 /*
 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.
 249  */
 250
 251 /* Policy for using system memory functions and doing no error reporting. */
 252 class SystemAllocPolicy
 253 {
 254   public:
 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 {}
 259 };
 260
 261 /*
 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...
 265  *
 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.
 270  */
 271 template <size_t nbytes>
 272 struct AlignedStorage
 273 {
 274     union U {
 275         char bytes[nbytes];
 276         uint64 _;
 277     } u;
 278
 279     const void *addr() const { return u.bytes; }
 280     void *addr() { return u.bytes; }
 281 };
 282
 283 template <class T>
 284 struct AlignedStorage2
 285 {
 286     union U {
 287         char bytes[sizeof(T)];
 288         uint64 _;
 289     } u;
 290
 291     const T *addr() const { return (const T *)u.bytes; }
 292     T *addr() { return (T *)u.bytes; }
 293 };
 294
 295 /*
 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.
 302  *
 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.
 305  */
 306 template <class T>
 307 class LazilyConstructed
 308 {
 309     AlignedStorage2<T> storage;
 310     bool constructed;
 311
 312     T &asT() { return *storage.addr(); }
 313
 314   public:
 315     LazilyConstructed() { constructed = false; }
 316     ~LazilyConstructed() { if (constructed) asT().~T(); }
 317
 318     bool empty() const { return !constructed; }
 319
 320     void construct() {
 321         JS_ASSERT(!constructed);
 322         new(storage.addr()) T();
 323         constructed = true;
 324     }
 325
 326     template <class T1>
 327     void construct(const T1 &t1) {
 328         JS_ASSERT(!constructed);
 329         new(storage.addr()) T(t1);
 330         constructed = true;
 331     }
 332
 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);
 337         constructed = true;
 338     }
 339
 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);
 344         constructed = true;
 345     }
 346
 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);
 351         constructed = true;
 352     }
 353
 354     T *addr() {
 355         JS_ASSERT(constructed);
 356         return &asT();
 357     }
 358
 359     T &ref() {
 360         JS_ASSERT(constructed);
 361         return asT();
 362     }
 363
 364     void destroy() {
 365         ref().~T();
 366         constructed = false;
 367     }
 368 };
 369
 370
 371 /*
 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.
 374  */
 375 template <class T>
 376 class Conditionally {
 377     LazilyConstructed<T> t;
 378
 379   public:
 380     Conditionally(bool b) { if (b) t.construct(); }
 381
 382     template <class T1>
 383     Conditionally(bool b, const T1 &t1) { if (b) t.construct(t1); }
 384
 385     template <class T1, class T2>
 386     Conditionally(bool b, const T1 &t1, const T2 &t2) { if (b) t.construct(t1, t2); }
 387 };
 388
 389 template <class T>
 390 class AlignedPtrAndFlag
 391 {
 392     uintptr_t bits;
 393
 394   public:
 395     AlignedPtrAndFlag(T *t, bool flag) {
 396         JS_ASSERT((uintptr_t(t) & 1) == 0);
 397         bits = uintptr_t(t) | uintptr_t(flag);
 398     }
 399
 400     T *ptr() const {
 401         return (T *)(bits & ~uintptr_t(1));
 402     }
 403
 404     bool flag() const {
 405         return (bits & 1) != 0;
 406     }
 407
 408     void setPtr(T *t) {
 409         JS_ASSERT((uintptr_t(t) & 1) == 0);
 410         bits = uintptr_t(t) | uintptr_t(flag());
 411     }
 412
 413     void setFlag() {
 414         bits |= 1;
 415     }
 416
 417     void unsetFlag() {
 418         bits &= ~uintptr_t(1);
 419     }
 420
 421     void set(T *t, bool flag) {
 422         JS_ASSERT((uintptr_t(t) & 1) == 0);
 423         bits = uintptr_t(t) | flag;
 424     }
 425 };
 426
 427 template <class T>
 428 static inline void
 429 Reverse(T *beg, T *end)
 430 {
 431     while (beg != end) {
 432         if (--end == beg)
 433             return;
 434         T tmp = *beg;
 435         *beg = *end;
 436         *end = tmp;
 437         ++beg;
 438     }
 439 }
 440
 441 template <class T>
 442 static inline T *
 443 Find(T *beg, T *end, const T &v)
 444 {
 445     for (T *p = beg; p != end; ++p) {
 446         if (*p == v)
 447             return p;
 448     }
 449     return end;
 450 }
 451
 452 template <class Container>
 453 static inline typename Container::ElementType *
 454 Find(Container &c, const typename Container::ElementType &v)
 455 {
 456     return Find(c.begin(), c.end(), v);
 457 }
 458
 459 template <typename InputIterT, typename CallableT>
 460 void
 461 ForEach(InputIterT begin, InputIterT end, CallableT f)
 462 {
 463     for (; begin != end; ++begin)
 464         f(*begin);
 465 }
 466
 467 template <class T>
 468 static inline T
 469 Min(T t1, T t2)
 470 {
 471     return t1 < t2 ? t1 : t2;
 472 }
 473
 474 template <class T>
 475 static inline T
 476 Max(T t1, T t2)
 477 {
 478     return t1 > t2 ? t1 : t2;
 479 }
 480
 481 /* Allows a const variable to be initialized after its declaration. */
 482 template <class T>
 483 static T&
 484 InitConst(const T &t)
 485 {
 486     return const_cast<T &>(t);
 487 }
 488
 489 } /* namespace js */
 490
 491 #ifdef JSSTL_UNDEFD_MOZALLOC_WRAPPERS
 492 #  include "mozilla/mozalloc_macro_wrappers.h"
 493 #endif
 494
 495 #endif /* jstl_h_ */