Fix HashTable/HashMap bugs, and add a clear() method.
1 // vim: set sts=8 ts=2 sw=2 tw=99 et:
3 // Copyright (C) 2013, David Anderson and AlliedModders LLC
4 // All rights reserved.
6 // Redistribution and use in source and binary forms, with or without
7 // modification, are permitted provided that the following conditions are met:
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.
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.
30 #ifndef _include_amtl_utility_h_
31 #define _include_amtl_utility_h_
44 # pragma warning(disable:4355)
49 static const size_t kMallocAlignment = sizeof(void *) * 2;
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;
57 typedef uint8 * Address;
59 static const size_t kKB = 1024;
60 static const size_t kMB = 1024 * kKB;
61 static const size_t kGB = 1024 * kMB;
63 template <typename T> T
71 // Wrapper that automatically deletes its contents. The pointer can be taken
72 // to avoid destruction.
83 explicit AutoPtr(T *t)
91 return ReturnAndVoid(t_);
93 T *operator *() const {
96 T *operator ->() const {
99 operator T *() const {
102 void operator =(T *t) {
106 bool operator !() const {
111 // Wrapper that automatically deletes its contents. The pointer can be taken
112 // to avoid destruction.
113 template <typename T>
123 explicit AutoArray(T *t)
131 return ReturnAndVoid(t_);
133 T *operator *() const {
136 T &operator [](size_t index) {
139 const T &operator [](size_t index) const {
142 operator T *() const {
145 void operator =(T *t) {
149 bool operator !() const {
162 _BitScanReverse(&rval, number);
164 _BitScanReverse64(&rval, number);
177 FindRightmostBit(size_t number)
184 _BitScanForward(&rval, number);
186 _BitScanForward64(&rval, number);
199 IsPowerOfTwo(size_t value)
203 return !(value & (value - 1));
207 Align(size_t count, size_t alignment)
209 assert(IsPowerOfTwo(alignment));
210 return count + (alignment - (count % alignment)) % alignment;
214 IsUint32AddSafe(unsigned a, unsigned b)
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);
225 IsUintPtrAddSafe(size_t a, size_t b)
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);
236 IsUint32MultiplySafe(unsigned a, unsigned b)
238 if (a <= 1 || b <= 1)
241 size_t log2_a = Log2(a);
242 size_t log2_b = Log2(b);
243 return log2_a + log2_b <= sizeof(unsigned) * 8;
247 IsUintPtrMultiplySafe(size_t a, size_t b)
249 if (a <= 1 || b <= 1)
252 size_t log2_a = Log2(a);
253 size_t log2_b = Log2(b);
254 return log2_a + log2_b <= sizeof(size_t) * 8;
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])
260 #define IS_ALIGNED(addr, alignment) (!(uintptr_t(addr) & ((alignment) - 1)))
262 template <typename T>
264 IsAligned(T addr, size_t alignment)
266 assert(IsPowerOfTwo(alignment));
267 return !(uintptr_t(addr) & (alignment - 1));
270 static inline Address
271 AlignedBase(Address addr, size_t alignment)
273 assert(IsPowerOfTwo(alignment));
274 return Address(uintptr_t(addr) & ~(alignment - 1));
277 template <typename T> static inline T
278 Min(const T &t1, const T &t2)
280 return t1 < t2 ? t1 : t2;
283 template <typename T> static inline T
284 Max(const T &t1, const T &t2)
286 return t1 > t2 ? t1 : t2;
289 template <typename T>
294 return reinterpret_cast<T *>(buffer_);
296 const T *address() const {
297 return reinterpret_cast<const T *>(buffer_);
302 char buffer_[sizeof(T)];
307 #if __cplusplus >= 201103L
311 #if defined(KE_CXX11)
312 # define KE_DELETE delete
313 # define KE_OVERRIDE override
319 #if defined(_MSC_VER)
320 # define KE_SIZET_FMT "%Iu"
321 #elif defined(__GNUC__)
322 # define KE_SIZET_FMT "%zu"
324 # error "Implement format specifier string"
327 #if defined(__GNUC__)
328 # define KE_CRITICAL_LIKELY(x) __builtin_expect(!!(x), 1)
330 # define KE_CRITICAL_LIKELY(x) x
335 #endif // _include_amtl_utility_h_