include/am-utility.h
author David Anderson <dvander@alliedmods.net>
Sat Aug 24 02:36:11 2013 -0700 (2013-08-24)
changeset 9 4cd655ff4c2c
parent 5 d5deada8801f
child 10 0ac292cc1467
permissions -rw-r--r--
Fix HashTable/HashMap bugs, and add a clear() method.
     1 // vim: set sts=8 ts=2 sw=2 tw=99 et:
     2 //
     3 // Copyright (C) 2013, David Anderson and AlliedModders LLC
     4 // All rights reserved.
     5 // 
     6 // Redistribution and use in source and binary forms, with or without
     7 // modification, are permitted provided that the following conditions are met:
     8 // 
     9 //  * Redistributions of source code must retain the above copyright notice, this
    10 //    list of conditions and the following disclaimer.
    11 //  * Redistributions in binary form must reproduce the above copyright notice,
    12 //    this list of conditions and the following disclaimer in the documentation
    13 //    and/or other materials provided with the distribution.
    14 //  * Neither the name of AlliedModders LLC nor the names of its contributors
    15 //    may be used to endorse or promote products derived from this software
    16 //    without specific prior written permission.
    17 //
    18 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
    19 // AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    20 // IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
    21 // ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
    22 // LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
    23 // CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
    24 // SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
    25 // INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
    26 // CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
    27 // ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
    28 // POSSIBILITY OF SUCH DAMAGE.
    29 
    30 #ifndef _include_amtl_utility_h_
    31 #define _include_amtl_utility_h_
    32 
    33 #include <assert.h>
    34 #include <stddef.h>
    35 #include <stdlib.h>
    36 #include <stdint.h>
    37 #if defined(_MSC_VER)
    38 # include <intrin.h>
    39 #endif
    40 
    41 #define KE_32BIT
    42 
    43 #if defined(_MSC_VER)
    44 # pragma warning(disable:4355)
    45 #endif
    46 
    47 namespace ke {
    48 
    49 static const size_t kMallocAlignment = sizeof(void *) * 2;
    50 
    51 typedef uint8_t uint8;
    52 typedef int32_t int32;
    53 typedef uint32_t uint32;
    54 typedef int64_t int64;
    55 typedef uint64_t uint64;
    56 
    57 typedef uint8 * Address;
    58 
    59 static const size_t kKB = 1024;
    60 static const size_t kMB = 1024 * kKB;
    61 static const size_t kGB = 1024 * kMB;
    62 
    63 template <typename T> T
    64 ReturnAndVoid(T &t)
    65 {
    66     T saved = t;
    67     t = T();
    68     return saved;
    69 }
    70 
    71 // Wrapper that automatically deletes its contents. The pointer can be taken
    72 // to avoid destruction.
    73 template <typename T>
    74 class AutoPtr
    75 {
    76     T *t_;
    77 
    78   public:
    79     AutoPtr()
    80       : t_(NULL)
    81     {
    82     }
    83     explicit AutoPtr(T *t)
    84       : t_(t)
    85     {
    86     }
    87     ~AutoPtr() {
    88         delete t_;
    89     }
    90     T *take() {
    91         return ReturnAndVoid(t_);
    92     }
    93     T *operator *() const {
    94         return t_;
    95     }
    96     T *operator ->() const {
    97         return t_;
    98     }
    99     operator T *() const {
   100         return t_;
   101     }
   102     void operator =(T *t) {
   103         delete t_;
   104         t_ = t;
   105     }
   106     bool operator !() const {
   107         return !t_;
   108     }
   109 };
   110 
   111 // Wrapper that automatically deletes its contents. The pointer can be taken
   112 // to avoid destruction.
   113 template <typename T>
   114 class AutoArray
   115 {
   116     T *t_;
   117 
   118   public:
   119     AutoArray()
   120       : t_(NULL)
   121     {
   122     }
   123     explicit AutoArray(T *t)
   124       : t_(t)
   125     {
   126     }
   127     ~AutoArray() {
   128         delete [] t_;
   129     }
   130     T *take() {
   131         return ReturnAndVoid(t_);
   132     }
   133     T *operator *() const {
   134         return t_;
   135     }
   136     T &operator [](size_t index) {
   137       return t_[index];
   138     }
   139     const T &operator [](size_t index) const {
   140       return t_[index];
   141     }
   142     operator T *() const {
   143         return t_;
   144     }
   145     void operator =(T *t) {
   146         delete [] t_;
   147         t_ = t;
   148     }
   149     bool operator !() const {
   150         return !t_;
   151     }
   152 };
   153 
   154 static inline size_t
   155 Log2(size_t number)
   156 {
   157     assert(number != 0);
   158 
   159 #ifdef _MSC_VER
   160     unsigned long rval;
   161 # ifdef _M_IX86
   162     _BitScanReverse(&rval, number);
   163 # elif _M_X64
   164     _BitScanReverse64(&rval, number);
   165 # endif
   166     return rval;
   167 #else
   168     size_t bit;
   169     asm("bsr %1, %0\n"
   170         : "=r" (bit)
   171         : "rm" (number));
   172     return bit;
   173 #endif
   174 }
   175 
   176 static inline size_t
   177 FindRightmostBit(size_t number)
   178 {
   179     assert(number != 0);
   180 
   181 #ifdef _MSC_VER
   182     unsigned long rval;
   183 # ifdef _M_IX86
   184     _BitScanForward(&rval, number);
   185 # elif _M_X64
   186     _BitScanForward64(&rval, number);
   187 # endif
   188     return rval;
   189 #else
   190     size_t bit;
   191     asm("bsf %1, %0\n"
   192         : "=r" (bit)
   193         : "rm" (number));
   194     return bit;
   195 #endif
   196 }
   197 
   198 static inline bool
   199 IsPowerOfTwo(size_t value)
   200 {
   201     if (value == 0)
   202         return false;
   203     return !(value & (value - 1));
   204 }
   205 
   206 static inline size_t
   207 Align(size_t count, size_t alignment)
   208 {
   209     assert(IsPowerOfTwo(alignment));
   210     return count + (alignment - (count % alignment)) % alignment;
   211 }
   212 
   213 static inline bool
   214 IsUint32AddSafe(unsigned a, unsigned b)
   215 {
   216     if (!a || !b)
   217         return true;
   218     size_t log2_a = Log2(a);
   219     size_t log2_b = Log2(b);
   220     return (log2_a < sizeof(unsigned) * 8) &&
   221            (log2_b < sizeof(unsigned) * 8);
   222 }
   223 
   224 static inline bool
   225 IsUintPtrAddSafe(size_t a, size_t b)
   226 {
   227     if (!a || !b)
   228         return true;
   229     size_t log2_a = Log2(a);
   230     size_t log2_b = Log2(b);
   231     return (log2_a < sizeof(size_t) * 8) &&
   232            (log2_b < sizeof(size_t) * 8);
   233 }
   234 
   235 static inline bool
   236 IsUint32MultiplySafe(unsigned a, unsigned b)
   237 {
   238     if (a <= 1 || b <= 1)
   239         return true;
   240 
   241     size_t log2_a = Log2(a);
   242     size_t log2_b = Log2(b);
   243     return log2_a + log2_b <= sizeof(unsigned) * 8;
   244 }
   245 
   246 static inline bool
   247 IsUintPtrMultiplySafe(size_t a, size_t b)
   248 {
   249     if (a <= 1 || b <= 1)
   250         return true;
   251 
   252     size_t log2_a = Log2(a);
   253     size_t log2_b = Log2(b);
   254     return log2_a + log2_b <= sizeof(size_t) * 8;
   255 }
   256 
   257 #define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))
   258 #define STATIC_ASSERT(cond) extern int static_assert_f(int a[(cond) ? 1 : -1])
   259 
   260 #define IS_ALIGNED(addr, alignment)    (!(uintptr_t(addr) & ((alignment) - 1)))
   261 
   262 template <typename T>
   263 static inline bool
   264 IsAligned(T addr, size_t alignment)
   265 {
   266     assert(IsPowerOfTwo(alignment));
   267     return !(uintptr_t(addr) & (alignment - 1));
   268 }
   269 
   270 static inline Address
   271 AlignedBase(Address addr, size_t alignment)
   272 {
   273     assert(IsPowerOfTwo(alignment));
   274     return Address(uintptr_t(addr) & ~(alignment - 1));
   275 }
   276 
   277 template <typename T> static inline T
   278 Min(const T &t1, const T &t2)
   279 {
   280     return t1 < t2 ? t1 : t2;
   281 }
   282 
   283 template <typename T> static inline T
   284 Max(const T &t1, const T &t2)
   285 {
   286     return t1 > t2 ? t1 : t2;
   287 }
   288 
   289 template <typename T>
   290 class StorageBuffer
   291 {
   292  public:
   293   T *address() {
   294     return reinterpret_cast<T *>(buffer_);
   295   }
   296   const T *address() const {
   297     return reinterpret_cast<const T *>(buffer_);
   298   }
   299 
   300  private:
   301   union {
   302     char buffer_[sizeof(T)];
   303     uint64_t aligned_;
   304   };
   305 };
   306 
   307 #if __cplusplus >= 201103L
   308 # define KE_CXX11
   309 #endif
   310 
   311 #if defined(KE_CXX11)
   312 # define KE_DELETE delete
   313 # define KE_OVERRIDE override
   314 #else
   315 # define KE_DELETE
   316 # define KE_OVERRIDE
   317 #endif
   318 
   319 #if defined(_MSC_VER)
   320 # define KE_SIZET_FMT           "%Iu"
   321 #elif defined(__GNUC__)
   322 # define KE_SIZET_FMT           "%zu"
   323 #else
   324 # error "Implement format specifier string"
   325 #endif
   326 
   327 #if defined(__GNUC__)
   328 # define KE_CRITICAL_LIKELY(x)  __builtin_expect(!!(x), 1)
   329 #else
   330 # define KE_CRITICAL_LIKELY(x)  x
   331 #endif
   332 
   333 }
   334 
   335 #endif // _include_amtl_utility_h_