diff options
Diffstat (limited to 'include/EASTL/bitset.h')
| -rw-r--r-- | include/EASTL/bitset.h | 2234 |
1 files changed, 0 insertions, 2234 deletions
diff --git a/include/EASTL/bitset.h b/include/EASTL/bitset.h deleted file mode 100644 index c31831a..0000000 --- a/include/EASTL/bitset.h +++ /dev/null @@ -1,2234 +0,0 @@ -///////////////////////////////////////////////////////////////////////////// -// Copyright (c) Electronic Arts Inc. All rights reserved. -///////////////////////////////////////////////////////////////////////////// - -/////////////////////////////////////////////////////////////////////////////// -// This file implements a bitset much like the C++ std::bitset class. -// The primary distinctions between this list and std::bitset are: -// - bitset is more efficient than some other std::bitset implementations, -// notably the bitset that comes with Microsoft and other 1st party platforms. -// - bitset is savvy to an environment that doesn't have exception handling, -// as is sometimes the case with console or embedded environments. -// - bitset is savvy to environments in which 'unsigned long' is not the -// most efficient integral data type. std::bitset implementations use -// unsigned long, even if it is an inefficient integer type. -// - bitset removes as much function calls as practical, in order to allow -// debug builds to run closer in speed and code footprint to release builds. -// - bitset doesn't support string functionality. We can add this if -// it is deemed useful. -// -/////////////////////////////////////////////////////////////////////////////// - - -#ifndef EASTL_BITSET_H -#define EASTL_BITSET_H - - -#include <EASTL/internal/config.h> -#include <EASTL/algorithm.h> - -EA_DISABLE_ALL_VC_WARNINGS(); - -#include <stddef.h> -#include <string.h> - -EA_RESTORE_ALL_VC_WARNINGS(); - -#if EASTL_EXCEPTIONS_ENABLED - EA_DISABLE_ALL_VC_WARNINGS(); - - #include <stdexcept> // std::out_of_range, std::length_error. - - EA_RESTORE_ALL_VC_WARNINGS(); -#endif - -EA_DISABLE_VC_WARNING(4127); // Conditional expression is constant - -#if defined(EA_PRAGMA_ONCE_SUPPORTED) - #pragma once // Some compilers (e.g. VC++) benefit significantly from using this. We've measured 3-4% build speed improvements in apps as a result. -#endif - - - -namespace eastl -{ - // To consider: Enable this for backwards compatibility with any user code that might be using BitsetWordType: - // #define BitsetWordType EASTL_BITSET_WORD_TYPE_DEFAULT - - - /// BITSET_WORD_COUNT - /// - /// Defines the number of words we use, based on the number of bits. - /// nBitCount refers to the number of bits in a bitset. - /// WordType refers to the type of integer word which stores bitet data. By default it is BitsetWordType. - /// - #if !defined(__GNUC__) || (__GNUC__ >= 3) // GCC 2.x can't handle the simpler declaration below. - #define BITSET_WORD_COUNT(nBitCount, WordType) (nBitCount == 0 ? 1 : ((nBitCount - 1) / (8 * sizeof(WordType)) + 1)) - #else - #define BITSET_WORD_COUNT(nBitCount, WordType) ((nBitCount - 1) / (8 * sizeof(WordType)) + 1) - #endif - - - /// EASTL_DISABLE_BITSET_ARRAYBOUNDS_WARNING - /// Before GCC 4.7 the '-Warray-bounds' buggy and was very likely to issue false positives for loops that are - /// difficult to evaluate. - /// https://gcc.gnu.org/bugzilla/show_bug.cgi?id=45978 - /// - #if defined(__GNUC__) && (EA_COMPILER_VERSION > 4007) && defined(EA_PLATFORM_ANDROID) // Earlier than GCC 4.7 - #define EASTL_DISABLE_BITSET_ARRAYBOUNDS_WARNING 1 - #else - #define EASTL_DISABLE_BITSET_ARRAYBOUNDS_WARNING 0 - #endif - - - - /// BitsetBase - /// - /// This is a default implementation that works for any number of words. - /// - template <size_t NW, typename WordType> // Templated on the number of words used to hold the bitset and the word type. - struct BitsetBase - { - typedef WordType word_type; - typedef BitsetBase<NW, WordType> this_type; - #if EASTL_BITSET_SIZE_T - typedef size_t size_type; - #else - typedef eastl_size_t size_type; - #endif - - enum { - kBitsPerWord = (8 * sizeof(word_type)), - kBitsPerWordMask = (kBitsPerWord - 1), - kBitsPerWordShift = ((kBitsPerWord == 8) ? 3 : ((kBitsPerWord == 16) ? 4 : ((kBitsPerWord == 32) ? 5 : (((kBitsPerWord == 64) ? 6 : 7))))) - }; - - public: - word_type mWord[NW]; - - public: - BitsetBase(); - BitsetBase(uint32_t value); // This exists only for compatibility with std::bitset, which has a 'long' constructor. - //BitsetBase(uint64_t value); // Disabled because it causes conflicts with the 32 bit version with existing user code. Use from_uint64 to init from a uint64_t instead. - - void operator&=(const this_type& x); - void operator|=(const this_type& x); - void operator^=(const this_type& x); - - void operator<<=(size_type n); - void operator>>=(size_type n); - - void flip(); - void set(); - void set(size_type i, bool value); - void reset(); - - bool operator==(const this_type& x) const; - - bool any() const; - size_type count() const; - - void from_uint32(uint32_t value); - void from_uint64(uint64_t value); - - unsigned long to_ulong() const; - uint32_t to_uint32() const; - uint64_t to_uint64() const; - - word_type& DoGetWord(size_type i); - word_type DoGetWord(size_type i) const; - - size_type DoFindFirst() const; - size_type DoFindNext(size_type last_find) const; - - size_type DoFindLast() const; // Returns NW * kBitsPerWord (the bit count) if no bits are set. - size_type DoFindPrev(size_type last_find) const; // Returns NW * kBitsPerWord (the bit count) if no bits are set. - - }; // class BitsetBase - - - - /// BitsetBase<1, WordType> - /// - /// This is a specialization for a bitset that fits within one word. - /// - template <typename WordType> - struct BitsetBase<1, WordType> - { - typedef WordType word_type; - typedef BitsetBase<1, WordType> this_type; - #if EASTL_BITSET_SIZE_T - typedef size_t size_type; - #else - typedef eastl_size_t size_type; - #endif - - enum { - kBitsPerWord = (8 * sizeof(word_type)), - kBitsPerWordMask = (kBitsPerWord - 1), - kBitsPerWordShift = ((kBitsPerWord == 8) ? 3 : ((kBitsPerWord == 16) ? 4 : ((kBitsPerWord == 32) ? 5 : (((kBitsPerWord == 64) ? 6 : 7))))) - }; - - public: - word_type mWord[1]; // Defined as an array of 1 so that bitset can treat this BitsetBase like others. - - public: - BitsetBase(); - BitsetBase(uint32_t value); - //BitsetBase(uint64_t value); // Disabled because it causes conflicts with the 32 bit version with existing user code. Use from_uint64 instead. - - void operator&=(const this_type& x); - void operator|=(const this_type& x); - void operator^=(const this_type& x); - - void operator<<=(size_type n); - void operator>>=(size_type n); - - void flip(); - void set(); - void set(size_type i, bool value); - void reset(); - - bool operator==(const this_type& x) const; - - bool any() const; - size_type count() const; - - void from_uint32(uint32_t value); - void from_uint64(uint64_t value); - - unsigned long to_ulong() const; - uint32_t to_uint32() const; - uint64_t to_uint64() const; - - word_type& DoGetWord(size_type); - word_type DoGetWord(size_type) const; - - size_type DoFindFirst() const; - size_type DoFindNext(size_type last_find) const; - - size_type DoFindLast() const; // Returns 1 * kBitsPerWord (the bit count) if no bits are set. - size_type DoFindPrev(size_type last_find) const; // Returns 1 * kBitsPerWord (the bit count) if no bits are set. - - }; // BitsetBase<1, WordType> - - - - /// BitsetBase<2, WordType> - /// - /// This is a specialization for a bitset that fits within two words. - /// The difference here is that we avoid branching (ifs and loops). - /// - template <typename WordType> - struct BitsetBase<2, WordType> - { - typedef WordType word_type; - typedef BitsetBase<2, WordType> this_type; - #if EASTL_BITSET_SIZE_T - typedef size_t size_type; - #else - typedef eastl_size_t size_type; - #endif - - enum { - kBitsPerWord = (8 * sizeof(word_type)), - kBitsPerWordMask = (kBitsPerWord - 1), - kBitsPerWordShift = ((kBitsPerWord == 8) ? 3 : ((kBitsPerWord == 16) ? 4 : ((kBitsPerWord == 32) ? 5 : (((kBitsPerWord == 64) ? 6 : 7))))) - }; - - public: - word_type mWord[2]; - - public: - BitsetBase(); - BitsetBase(uint32_t value); - //BitsetBase(uint64_t value); // Disabled because it causes conflicts with the 32 bit version with existing user code. Use from_uint64 instead. - - void operator&=(const this_type& x); - void operator|=(const this_type& x); - void operator^=(const this_type& x); - - void operator<<=(size_type n); - void operator>>=(size_type n); - - void flip(); - void set(); - void set(size_type i, bool value); - void reset(); - - bool operator==(const this_type& x) const; - - bool any() const; - size_type count() const; - - void from_uint32(uint32_t value); - void from_uint64(uint64_t value); - - unsigned long to_ulong() const; - uint32_t to_uint32() const; - uint64_t to_uint64() const; - - word_type& DoGetWord(size_type); - word_type DoGetWord(size_type) const; - - size_type DoFindFirst() const; - size_type DoFindNext(size_type last_find) const; - - size_type DoFindLast() const; // Returns 2 * kBitsPerWord (the bit count) if no bits are set. - size_type DoFindPrev(size_type last_find) const; // Returns 2 * kBitsPerWord (the bit count) if no bits are set. - - }; // BitsetBase<2, WordType> - - - - - /// bitset - /// - /// Implements a bitset much like the C++ std::bitset. - /// - /// As of this writing we don't implement a specialization of bitset<0>, - /// as it is deemed an academic exercise that nobody would actually - /// use and it would increase code space and provide little practical - /// benefit. Note that this doesn't mean bitset<0> isn't supported; - /// it means that our version of it isn't as efficient as it would be - /// if a specialization was made for it. - /// - /// - N can be any unsigned (non-zero) value, though memory usage is - /// linear with respect to N, so large values of N use large amounts of memory. - /// - WordType must be one of [uint16_t, uint32_t, uint64_t, uint128_t] - /// and the compiler must support the type. By default the WordType is - /// the largest native register type that the target platform supports. - /// - template <size_t N, typename WordType = EASTL_BITSET_WORD_TYPE_DEFAULT> - class bitset : private BitsetBase<BITSET_WORD_COUNT(N, WordType), WordType> - { - public: - typedef BitsetBase<BITSET_WORD_COUNT(N, WordType), WordType> base_type; - typedef bitset<N, WordType> this_type; - typedef WordType word_type; - typedef typename base_type::size_type size_type; - - enum - { - kBitsPerWord = (8 * sizeof(word_type)), - kBitsPerWordMask = (kBitsPerWord - 1), - kBitsPerWordShift = ((kBitsPerWord == 8) ? 3 : ((kBitsPerWord == 16) ? 4 : ((kBitsPerWord == 32) ? 5 : (((kBitsPerWord == 64) ? 6 : 7))))), - kSize = N, // The number of bits the bitset holds - kWordSize = sizeof(word_type), // The size of individual words the bitset uses to hold the bits. - kWordCount = BITSET_WORD_COUNT(N, WordType) // The number of words the bitset uses to hold the bits. sizeof(bitset<N, WordType>) == kWordSize * kWordCount. - }; - - using base_type::mWord; - using base_type::DoGetWord; - using base_type::DoFindFirst; - using base_type::DoFindNext; - using base_type::DoFindLast; - using base_type::DoFindPrev; - using base_type::to_ulong; - using base_type::to_uint32; - using base_type::to_uint64; - using base_type::count; - using base_type::any; - - public: - /// reference - /// - /// A reference is a reference to a specific bit in the bitset. - /// The C++ standard specifies that this be a nested class, - /// though it is not clear if a non-nested reference implementation - /// would be non-conforming. - /// - class reference - { - protected: - friend class bitset<N, WordType>; - - word_type* mpBitWord; - size_type mnBitIndex; - - reference(){} // The C++ standard specifies that this is private. - - public: - reference(const bitset& x, size_type i); - - reference& operator=(bool value); - reference& operator=(const reference& x); - - bool operator~() const; - operator bool() const // Defined inline because CodeWarrior fails to be able to compile it outside. - { return (*mpBitWord & (static_cast<word_type>(1) << (mnBitIndex & kBitsPerWordMask))) != 0; } - - reference& flip(); - }; - - public: - friend class reference; - - bitset(); - bitset(uint32_t value); - //bitset(uint64_t value); // Disabled because it causes conflicts with the 32 bit version with existing user code. Use from_uint64 instead. - - // We don't define copy constructor and operator= because - // the compiler-generated versions will suffice. - - this_type& operator&=(const this_type& x); - this_type& operator|=(const this_type& x); - this_type& operator^=(const this_type& x); - - this_type& operator<<=(size_type n); - this_type& operator>>=(size_type n); - - this_type& set(); - this_type& set(size_type i, bool value = true); - - this_type& reset(); - this_type& reset(size_type i); - - this_type& flip(); - this_type& flip(size_type i); - this_type operator~() const; - - reference operator[](size_type i); - bool operator[](size_type i) const; - - const word_type* data() const; - word_type* data(); - - void from_uint32(uint32_t value); - void from_uint64(uint64_t value); - - //unsigned long to_ulong() const; // We inherit this from the base class. - //uint32_t to_uint32() const; - //uint64_t to_uint64() const; - - //size_type count() const; // We inherit this from the base class. - size_type size() const; - - bool operator==(const this_type& x) const; -#if !defined(EA_COMPILER_HAS_THREE_WAY_COMPARISON) - bool operator!=(const this_type& x) const; -#endif - - bool test(size_type i) const; - //bool any() const; // We inherit this from the base class. - bool all() const; - bool none() const; - - this_type operator<<(size_type n) const; - this_type operator>>(size_type n) const; - - // Finds the index of the first "on" bit, returns kSize if none are set. - size_type find_first() const; - - // Finds the index of the next "on" bit after last_find, returns kSize if none are set. - size_type find_next(size_type last_find) const; - - // Finds the index of the last "on" bit, returns kSize if none are set. - size_type find_last() const; - - // Finds the index of the last "on" bit before last_find, returns kSize if none are set. - size_type find_prev(size_type last_find) const; - - }; // bitset - - - - - - - - /// BitsetCountBits - /// - /// This is a fast trick way to count bits without branches nor memory accesses. - /// - inline uint32_t BitsetCountBits(uint64_t x) - { - // GCC 3.x's implementation of UINT64_C is broken and fails to deal with - // the code below correctly. So we make a workaround for it. Earlier and - // later versions of GCC don't have this bug. - - #if defined(__GNUC__) && (__GNUC__ == 3) - x = x - ((x >> 1) & 0x5555555555555555ULL); - x = (x & 0x3333333333333333ULL) + ((x >> 2) & 0x3333333333333333ULL); - x = (x + (x >> 4)) & 0x0F0F0F0F0F0F0F0FULL; - return (uint32_t)((x * 0x0101010101010101ULL) >> 56); - #else - x = x - ((x >> 1) & UINT64_C(0x5555555555555555)); - x = (x & UINT64_C(0x3333333333333333)) + ((x >> 2) & UINT64_C(0x3333333333333333)); - x = (x + (x >> 4)) & UINT64_C(0x0F0F0F0F0F0F0F0F); - return (uint32_t)((x * UINT64_C(0x0101010101010101)) >> 56); - #endif - } - - inline uint32_t BitsetCountBits(uint32_t x) - { - x = x - ((x >> 1) & 0x55555555); - x = (x & 0x33333333) + ((x >> 2) & 0x33333333); - x = (x + (x >> 4)) & 0x0F0F0F0F; - return (uint32_t)((x * 0x01010101) >> 24); - } - - inline uint32_t BitsetCountBits(uint16_t x) - { - return BitsetCountBits((uint32_t)x); - } - - inline uint32_t BitsetCountBits(uint8_t x) - { - return BitsetCountBits((uint32_t)x); - } - - - // const static char kBitsPerUint16[16] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 }; - #define EASTL_BITSET_COUNT_STRING "\0\1\1\2\1\2\2\3\1\2\2\3\2\3\3\4" - - - inline uint32_t GetFirstBit(uint8_t x) - { - if(x) - { - uint32_t n = 1; - - if((x & 0x0000000F) == 0) { n += 4; x >>= 4; } - if((x & 0x00000003) == 0) { n += 2; x >>= 2; } - - return (uint32_t)(n - (x & 1)); - } - - return 8; - } - - inline uint32_t GetFirstBit(uint16_t x) // To do: Update this to use VC++ _BitScanForward, _BitScanForward64; GCC __builtin_ctz, __builtin_ctzl. VC++ __lzcnt16, __lzcnt, __lzcnt64 requires recent CPUs (2013+) and probably can't be used. http://en.wikipedia.org/wiki/Haswell_%28microarchitecture%29#New_features - { - if(x) - { - uint32_t n = 1; - - if((x & 0x000000FF) == 0) { n += 8; x >>= 8; } - if((x & 0x0000000F) == 0) { n += 4; x >>= 4; } - if((x & 0x00000003) == 0) { n += 2; x >>= 2; } - - return (uint32_t)(n - (x & 1)); - } - - return 16; - } - - inline uint32_t GetFirstBit(uint32_t x) - { - if(x) - { - uint32_t n = 1; - - if((x & 0x0000FFFF) == 0) { n += 16; x >>= 16; } - if((x & 0x000000FF) == 0) { n += 8; x >>= 8; } - if((x & 0x0000000F) == 0) { n += 4; x >>= 4; } - if((x & 0x00000003) == 0) { n += 2; x >>= 2; } - - return (n - (x & 1)); - } - - return 32; - } - - inline uint32_t GetFirstBit(uint64_t x) - { - if(x) - { - uint32_t n = 1; - - if((x & 0xFFFFFFFF) == 0) { n += 32; x >>= 32; } - if((x & 0x0000FFFF) == 0) { n += 16; x >>= 16; } - if((x & 0x000000FF) == 0) { n += 8; x >>= 8; } - if((x & 0x0000000F) == 0) { n += 4; x >>= 4; } - if((x & 0x00000003) == 0) { n += 2; x >>= 2; } - - return (n - ((uint32_t)x & 1)); - } - - return 64; - } - - - #if EASTL_INT128_SUPPORTED - inline uint32_t GetFirstBit(eastl_uint128_t x) - { - if(x) - { - uint32_t n = 1; - - if((x & UINT64_C(0xFFFFFFFFFFFFFFFF)) == 0) { n += 64; x >>= 64; } - if((x & 0xFFFFFFFF) == 0) { n += 32; x >>= 32; } - if((x & 0x0000FFFF) == 0) { n += 16; x >>= 16; } - if((x & 0x000000FF) == 0) { n += 8; x >>= 8; } - if((x & 0x0000000F) == 0) { n += 4; x >>= 4; } - if((x & 0x00000003) == 0) { n += 2; x >>= 2; } - - return (n - ((uint32_t)x & 1)); - } - - return 128; - } - #endif - - inline uint32_t GetLastBit(uint8_t x) - { - if(x) - { - uint32_t n = 0; - - if(x & 0xFFF0) { n += 4; x >>= 4; } - if(x & 0xFFFC) { n += 2; x >>= 2; } - if(x & 0xFFFE) { n += 1; } - - return n; - } - - return 8; - } - - inline uint32_t GetLastBit(uint16_t x) - { - if(x) - { - uint32_t n = 0; - - if(x & 0xFF00) { n += 8; x >>= 8; } - if(x & 0xFFF0) { n += 4; x >>= 4; } - if(x & 0xFFFC) { n += 2; x >>= 2; } - if(x & 0xFFFE) { n += 1; } - - return n; - } - - return 16; - } - - inline uint32_t GetLastBit(uint32_t x) - { - if(x) - { - uint32_t n = 0; - - if(x & 0xFFFF0000) { n += 16; x >>= 16; } - if(x & 0xFFFFFF00) { n += 8; x >>= 8; } - if(x & 0xFFFFFFF0) { n += 4; x >>= 4; } - if(x & 0xFFFFFFFC) { n += 2; x >>= 2; } - if(x & 0xFFFFFFFE) { n += 1; } - - return n; - } - - return 32; - } - - inline uint32_t GetLastBit(uint64_t x) - { - if(x) - { - uint32_t n = 0; - - if(x & UINT64_C(0xFFFFFFFF00000000)) { n += 32; x >>= 32; } - if(x & 0xFFFF0000) { n += 16; x >>= 16; } - if(x & 0xFFFFFF00) { n += 8; x >>= 8; } - if(x & 0xFFFFFFF0) { n += 4; x >>= 4; } - if(x & 0xFFFFFFFC) { n += 2; x >>= 2; } - if(x & 0xFFFFFFFE) { n += 1; } - - return n; - } - - return 64; - } - - #if EASTL_INT128_SUPPORTED - inline uint32_t GetLastBit(eastl_uint128_t x) - { - if(x) - { - uint32_t n = 0; - - eastl_uint128_t mask(UINT64_C(0xFFFFFFFF00000000)); // There doesn't seem to exist compiler support for INT128_C() by any compiler. EAStdC's int128_t supports it though. - mask <<= 64; - - if(x & mask) { n += 64; x >>= 64; } - if(x & UINT64_C(0xFFFFFFFF00000000)) { n += 32; x >>= 32; } - if(x & UINT64_C(0x00000000FFFF0000)) { n += 16; x >>= 16; } - if(x & UINT64_C(0x00000000FFFFFF00)) { n += 8; x >>= 8; } - if(x & UINT64_C(0x00000000FFFFFFF0)) { n += 4; x >>= 4; } - if(x & UINT64_C(0x00000000FFFFFFFC)) { n += 2; x >>= 2; } - if(x & UINT64_C(0x00000000FFFFFFFE)) { n += 1; } - - return n; - } - - return 128; - } - #endif - - - - - /////////////////////////////////////////////////////////////////////////// - // BitsetBase - // - // We tried two forms of array access here: - // for(word_type *pWord(mWord), *pWordEnd(mWord + NW); pWord < pWordEnd; ++pWord) - // *pWord = ... - // and - // for(size_t i = 0; i < NW; i++) - // mWord[i] = ... - // - // For our tests (~NW < 16), the latter (using []) access resulted in faster code. - /////////////////////////////////////////////////////////////////////////// - - template <size_t NW, typename WordType> - inline BitsetBase<NW, WordType>::BitsetBase() - { - reset(); - } - - - template <size_t NW, typename WordType> - inline BitsetBase<NW, WordType>::BitsetBase(uint32_t value) - { - // This implementation assumes that sizeof(value) <= sizeof(word_type). - //EASTL_CT_ASSERT(sizeof(value) <= sizeof(word_type)); Disabled because we now have support for uint8_t and uint16_t word types. It would be nice to have a runtime assert that tested this. - - reset(); - mWord[0] = static_cast<word_type>(value); - } - - - /* - template <size_t NW, typename WordType> - inline BitsetBase<NW, WordType>::BitsetBase(uint64_t value) - { - reset(); - - #if(EA_PLATFORM_WORD_SIZE == 4) - mWord[0] = static_cast<word_type>(value); - - EASTL_CT_ASSERT(NW > 2); // We can assume this because we have specializations of BitsetBase for <1> and <2>. - //if(NW > 1) // NW is a template constant, but it would be a little messy to take advantage of it's const-ness. - mWord[1] = static_cast<word_type>(value >> 32); - #else - mWord[0] = static_cast<word_type>(value); - #endif - } - */ - - - template <size_t NW, typename WordType> - inline void BitsetBase<NW, WordType>::operator&=(const this_type& x) - { - for(size_t i = 0; i < NW; i++) - mWord[i] &= x.mWord[i]; - } - - - template <size_t NW, typename WordType> - inline void BitsetBase<NW, WordType>::operator|=(const this_type& x) - { - for(size_t i = 0; i < NW; i++) - mWord[i] |= x.mWord[i]; - } - - - template <size_t NW, typename WordType> - inline void BitsetBase<NW, WordType>::operator^=(const this_type& x) - { - for(size_t i = 0; i < NW; i++) - mWord[i] ^= x.mWord[i]; - } - - - template <size_t NW, typename WordType> - inline void BitsetBase<NW, WordType>::operator<<=(size_type n) - { - const size_type nWordShift = (size_type)(n >> kBitsPerWordShift); - - if(nWordShift) - { - for(int i = (int)(NW - 1); i >= 0; --i) - mWord[i] = (nWordShift <= (size_type)i) ? mWord[i - nWordShift] : (word_type)0; - } - - if(n &= kBitsPerWordMask) - { - for(size_t i = (NW - 1); i > 0; --i) - mWord[i] = (word_type)((mWord[i] << n) | (mWord[i - 1] >> (kBitsPerWord - n))); - mWord[0] <<= n; - } - - // We let the parent class turn off any upper bits. - } - - - template <size_t NW, typename WordType> - inline void BitsetBase<NW, WordType>::operator>>=(size_type n) - { - const size_type nWordShift = (size_type)(n >> kBitsPerWordShift); - - if(nWordShift) - { - for(size_t i = 0; i < NW; ++i) - mWord[i] = ((nWordShift < (NW - i)) ? mWord[i + nWordShift] : (word_type)0); - } - - if(n &= kBitsPerWordMask) - { - for(size_t i = 0; i < (NW - 1); ++i) - mWord[i] = (word_type)((mWord[i] >> n) | (mWord[i + 1] << (kBitsPerWord - n))); - mWord[NW - 1] >>= n; - } - } - - - template <size_t NW, typename WordType> - inline void BitsetBase<NW, WordType>::flip() - { - for(size_t i = 0; i < NW; i++) - mWord[i] = ~mWord[i]; - // We let the parent class turn off any upper bits. - } - - - template <size_t NW, typename WordType> - inline void BitsetBase<NW, WordType>::set() - { - for(size_t i = 0; i < NW; i++) - mWord[i] = static_cast<word_type>(~static_cast<word_type>(0)); - // We let the parent class turn off any upper bits. - } - - - template <size_t NW, typename WordType> - inline void BitsetBase<NW, WordType>::set(size_type i, bool value) - { - if(value) - mWord[i >> kBitsPerWordShift] |= (static_cast<word_type>(1) << (i & kBitsPerWordMask)); - else - mWord[i >> kBitsPerWordShift] &= ~(static_cast<word_type>(1) << (i & kBitsPerWordMask)); - } - - - template <size_t NW, typename WordType> - inline void BitsetBase<NW, WordType>::reset() - { - if(NW > 16) // This is a constant expression and should be optimized away. - { - // This will be fastest if compiler intrinsic function optimizations are enabled. - memset(mWord, 0, sizeof(mWord)); - } - else - { - for(size_t i = 0; i < NW; i++) - mWord[i] = 0; - } - } - - - template <size_t NW, typename WordType> - inline bool BitsetBase<NW, WordType>::operator==(const this_type& x) const - { - for(size_t i = 0; i < NW; i++) - { - if(mWord[i] != x.mWord[i]) - return false; - } - return true; - } - - - template <size_t NW, typename WordType> - inline bool BitsetBase<NW, WordType>::any() const - { - for(size_t i = 0; i < NW; i++) - { - if(mWord[i]) - return true; - } - return false; - } - - - template <size_t NW, typename WordType> - inline typename BitsetBase<NW, WordType>::size_type - BitsetBase<NW, WordType>::count() const - { - size_type n = 0; - - for(size_t i = 0; i < NW; i++) - { - #if defined(__GNUC__) && (((__GNUC__ * 100) + __GNUC_MINOR__) >= 304) && !defined(EA_PLATFORM_ANDROID) // GCC 3.4 or later - #if(EA_PLATFORM_WORD_SIZE == 4) - n += (size_type)__builtin_popcountl(mWord[i]); - #else - n += (size_type)__builtin_popcountll(mWord[i]); - #endif - #elif defined(__GNUC__) && (__GNUC__ < 3) - n += BitsetCountBits(mWord[i]); // GCC 2.x compiler inexplicably blows up on the code below. - #else - // todo: use __popcnt16, __popcnt, __popcnt64 for msvc builds - // https://msdn.microsoft.com/en-us/library/bb385231(v=vs.140).aspx - for(word_type w = mWord[i]; w; w >>= 4) - n += EASTL_BITSET_COUNT_STRING[w & 0xF]; - - // Version which seems to run slower in benchmarks: - // n += BitsetCountBits(mWord[i]); - #endif - - } - return n; - } - - - template <size_t NW, typename WordType> - inline void BitsetBase<NW, WordType>::from_uint32(uint32_t value) - { - reset(); - mWord[0] = static_cast<word_type>(value); - } - - - template <size_t NW, typename WordType> - inline void BitsetBase<NW, WordType>::from_uint64(uint64_t value) - { - reset(); - - #if(EA_PLATFORM_WORD_SIZE == 4) - mWord[0] = static_cast<word_type>(value); - - EASTL_CT_ASSERT(NW > 2); // We can assume this because we have specializations of BitsetBase for <1> and <2>. - //if(NW > 1) // NW is a template constant, but it would be a little messy to take advantage of it's const-ness. - mWord[1] = static_cast<word_type>(value >> 32); - #else - mWord[0] = static_cast<word_type>(value); - #endif - } - - - template <size_t NW, typename WordType> - inline unsigned long BitsetBase<NW, WordType>::to_ulong() const - { - #if EASTL_EXCEPTIONS_ENABLED - for(size_t i = 1; i < NW; ++i) - { - if(mWord[i]) - throw std::overflow_error("BitsetBase::to_ulong"); - } - #endif - return (unsigned long)mWord[0]; // Todo: We need to deal with the case whereby sizeof(word_type) < sizeof(unsigned long) - } - - - template <size_t NW, typename WordType> - inline uint32_t BitsetBase<NW, WordType>::to_uint32() const - { - #if EASTL_EXCEPTIONS_ENABLED - // Verify that high words or bits are not set and thus that to_uint32 doesn't lose information. - for(size_t i = 1; i < NW; ++i) - { - if(mWord[i]) - throw std::overflow_error("BitsetBase::to_uint32"); - } - - #if(EA_PLATFORM_WORD_SIZE > 4) // if we have 64 bit words... - if(mWord[0] >> 32) - throw std::overflow_error("BitsetBase::to_uint32"); - #endif - #endif - - return (uint32_t)mWord[0]; - } - - - template <size_t NW, typename WordType> - inline uint64_t BitsetBase<NW, WordType>::to_uint64() const - { - #if EASTL_EXCEPTIONS_ENABLED - // Verify that high words are not set and thus that to_uint64 doesn't lose information. - - EASTL_CT_ASSERT(NW > 2); // We can assume this because we have specializations of BitsetBase for <1> and <2>. - for(size_t i = 2; i < NW; ++i) - { - if(mWord[i]) - throw std::overflow_error("BitsetBase::to_uint64"); - } - #endif - - #if(EA_PLATFORM_WORD_SIZE == 4) - EASTL_CT_ASSERT(NW > 2); // We can assume this because we have specializations of BitsetBase for <1> and <2>. - return (mWord[1] << 32) | mWord[0]; - #else - return (uint64_t)mWord[0]; - #endif - } - - - template <size_t NW, typename WordType> - inline typename BitsetBase<NW, WordType>::word_type& - BitsetBase<NW, WordType>::DoGetWord(size_type i) - { - return mWord[i >> kBitsPerWordShift]; - } - - - template <size_t NW, typename WordType> - inline typename BitsetBase<NW, WordType>::word_type - BitsetBase<NW, WordType>::DoGetWord(size_type i) const - { - return mWord[i >> kBitsPerWordShift]; - } - - - template <size_t NW, typename WordType> - inline typename BitsetBase<NW, WordType>::size_type - BitsetBase<NW, WordType>::DoFindFirst() const - { - for(size_type word_index = 0; word_index < NW; ++word_index) - { - const size_type fbiw = GetFirstBit(mWord[word_index]); - - if(fbiw != kBitsPerWord) - return (word_index * kBitsPerWord) + fbiw; - } - - return (size_type)NW * kBitsPerWord; - } - - -#if EASTL_DISABLE_BITSET_ARRAYBOUNDS_WARNING -EA_DISABLE_GCC_WARNING(-Warray-bounds) -#endif - - template <size_t NW, typename WordType> - inline typename BitsetBase<NW, WordType>::size_type - BitsetBase<NW, WordType>::DoFindNext(size_type last_find) const - { - // Start looking from the next bit. - ++last_find; - - // Set initial state based on last find. - size_type word_index = static_cast<size_type>(last_find >> kBitsPerWordShift); - size_type bit_index = static_cast<size_type>(last_find & kBitsPerWordMask); - - // To do: There probably is a more elegant way to write looping below. - if(word_index < NW) - { - // Mask off previous bits of the word so our search becomes a "find first". - word_type this_word = mWord[word_index] & (~static_cast<word_type>(0) << bit_index); - - for(;;) - { - const size_type fbiw = GetFirstBit(this_word); - - if(fbiw != kBitsPerWord) - return (word_index * kBitsPerWord) + fbiw; - - if(++word_index < NW) - this_word = mWord[word_index]; - else - break; - } - } - - return (size_type)NW * kBitsPerWord; - } - -#if EASTL_DISABLE_BITSET_ARRAYBOUNDS_WARNING -EA_RESTORE_GCC_WARNING() -#endif - - - - template <size_t NW, typename WordType> - inline typename BitsetBase<NW, WordType>::size_type - BitsetBase<NW, WordType>::DoFindLast() const - { - for(size_type word_index = (size_type)NW; word_index > 0; --word_index) - { - const size_type lbiw = GetLastBit(mWord[word_index - 1]); - - if(lbiw != kBitsPerWord) - return ((word_index - 1) * kBitsPerWord) + lbiw; - } - - return (size_type)NW * kBitsPerWord; - } - - - template <size_t NW, typename WordType> - inline typename BitsetBase<NW, WordType>::size_type - BitsetBase<NW, WordType>::DoFindPrev(size_type last_find) const - { - if(last_find > 0) - { - // Set initial state based on last find. - size_type word_index = static_cast<size_type>(last_find >> kBitsPerWordShift); - size_type bit_index = static_cast<size_type>(last_find & kBitsPerWordMask); - - // Mask off subsequent bits of the word so our search becomes a "find last". - word_type mask = (~static_cast<word_type>(0) >> (kBitsPerWord - 1 - bit_index)) >> 1; // We do two shifts here because many CPUs ignore requests to shift 32 bit integers by 32 bits, which could be the case above. - word_type this_word = mWord[word_index] & mask; - - for(;;) - { - const size_type lbiw = GetLastBit(this_word); - - if(lbiw != kBitsPerWord) - return (word_index * kBitsPerWord) + lbiw; - - if(word_index > 0) - this_word = mWord[--word_index]; - else - break; - } - } - - return (size_type)NW * kBitsPerWord; - } - - - - /////////////////////////////////////////////////////////////////////////// - // BitsetBase<1, WordType> - /////////////////////////////////////////////////////////////////////////// - - template <typename WordType> - inline BitsetBase<1, WordType>::BitsetBase() - { - mWord[0] = 0; - } - - - template <typename WordType> - inline BitsetBase<1, WordType>::BitsetBase(uint32_t value) - { - // This implementation assumes that sizeof(value) <= sizeof(word_type). - //EASTL_CT_ASSERT(sizeof(value) <= sizeof(word_type)); Disabled because we now have support for uint8_t and uint16_t word types. It would be nice to have a runtime assert that tested this. - - mWord[0] = static_cast<word_type>(value); - } - - - /* - template <typename WordType> - inline BitsetBase<1, WordType>::BitsetBase(uint64_t value) - { - #if(EA_PLATFORM_WORD_SIZE == 4) - EASTL_ASSERT(value <= 0xffffffff); - mWord[0] = static_cast<word_type>(value); // This potentially loses data, but that's what the user is requesting. - #else - mWord[0] = static_cast<word_type>(value); - #endif - } - */ - - - template <typename WordType> - inline void BitsetBase<1, WordType>::operator&=(const this_type& x) - { - mWord[0] &= x.mWord[0]; - } - - - template <typename WordType> - inline void BitsetBase<1, WordType>::operator|=(const this_type& x) - { - mWord[0] |= x.mWord[0]; - } - - - template <typename WordType> - inline void BitsetBase<1, WordType>::operator^=(const this_type& x) - { - mWord[0] ^= x.mWord[0]; - } - - - template <typename WordType> - inline void BitsetBase<1, WordType>::operator<<=(size_type n) - { - mWord[0] <<= n; - // We let the parent class turn off any upper bits. - } - - - template <typename WordType> - inline void BitsetBase<1, WordType>::operator>>=(size_type n) - { - mWord[0] >>= n; - } - - - template <typename WordType> - inline void BitsetBase<1, WordType>::flip() - { - mWord[0] = ~mWord[0]; - // We let the parent class turn off any upper bits. - } - - - template <typename WordType> - inline void BitsetBase<1, WordType>::set() - { - mWord[0] = static_cast<word_type>(~static_cast<word_type>(0)); - // We let the parent class turn off any upper bits. - } - - - template <typename WordType> - inline void BitsetBase<1, WordType>::set(size_type i, bool value) - { - if(value) - mWord[0] |= (static_cast<word_type>(1) << i); - else - mWord[0] &= ~(static_cast<word_type>(1) << i); - } - - - template <typename WordType> - inline void BitsetBase<1, WordType>::reset() - { - mWord[0] = 0; - } - - - template <typename WordType> - inline bool BitsetBase<1, WordType>::operator==(const this_type& x) const - { - return mWord[0] == x.mWord[0]; - } - - - template <typename WordType> - inline bool BitsetBase<1, WordType>::any() const - { - return mWord[0] != 0; - } - - - template <typename WordType> - inline typename BitsetBase<1, WordType>::size_type - BitsetBase<1, WordType>::count() const - { - #if defined(__GNUC__) && (((__GNUC__ * 100) + __GNUC_MINOR__) >= 304) && !defined(EA_PLATFORM_ANDROID) // GCC 3.4 or later - #if(EA_PLATFORM_WORD_SIZE == 4) - return (size_type)__builtin_popcountl(mWord[0]); - #else - return (size_type)__builtin_popcountll(mWord[0]); - #endif - #elif defined(__GNUC__) && (__GNUC__ < 3) - return BitsetCountBits(mWord[0]); // GCC 2.x compiler inexplicably blows up on the code below. - #else - size_type n = 0; - for(word_type w = mWord[0]; w; w >>= 4) - n += EASTL_BITSET_COUNT_STRING[w & 0xF]; - return n; - #endif - } - - - template <typename WordType> - inline void BitsetBase<1, WordType>::from_uint32(uint32_t value) - { - mWord[0] = static_cast<word_type>(value); - } - - - template <typename WordType> - inline void BitsetBase<1, WordType>::from_uint64(uint64_t value) - { - #if(EA_PLATFORM_WORD_SIZE == 4) - EASTL_ASSERT(value <= 0xffffffff); - mWord[0] = static_cast<word_type>(value); // This potentially loses data, but that's what the user is requesting. - #else - mWord[0] = static_cast<word_type>(value); - #endif - } - - - template <typename WordType> - inline unsigned long BitsetBase<1, WordType>::to_ulong() const - { - #if EASTL_EXCEPTIONS_ENABLED - #if((EA_PLATFORM_WORD_SIZE > 4) && defined(EA_PLATFORM_MICROSOFT)) // If we are using 64 bit words but ulong is less than 64 bits... Microsoft platforms alone use a 32 bit long under 64 bit platforms. - // Verify that high bits are not set and thus that to_ulong doesn't lose information. - if(mWord[0] >> 32) - throw std::overflow_error("BitsetBase::to_ulong"); - #endif - #endif - - return static_cast<unsigned long>(mWord[0]); - } - - - template <typename WordType> - inline uint32_t BitsetBase<1, WordType>::to_uint32() const - { - #if EASTL_EXCEPTIONS_ENABLED - #if(EA_PLATFORM_WORD_SIZE > 4) // If we are using 64 bit words... - // Verify that high bits are not set and thus that to_uint32 doesn't lose information. - if(mWord[0] >> 32) - throw std::overflow_error("BitsetBase::to_uint32"); - #endif - #endif - - return static_cast<uint32_t>(mWord[0]); - } - - - template <typename WordType> - inline uint64_t BitsetBase<1, WordType>::to_uint64() const - { - // This implementation is the same regardless of the word size, and there is no possibility of overflow_error. - return static_cast<uint64_t>(mWord[0]); - } - - - template <typename WordType> - inline typename BitsetBase<1, WordType>::word_type& - BitsetBase<1, WordType>::DoGetWord(size_type) - { - return mWord[0]; - } - - - template <typename WordType> - inline typename BitsetBase<1, WordType>::word_type - BitsetBase<1, WordType>::DoGetWord(size_type) const - { - return mWord[0]; - } - - - template <typename WordType> - inline typename BitsetBase<1, WordType>::size_type - BitsetBase<1, WordType>::DoFindFirst() const - { - return GetFirstBit(mWord[0]); - } - - - template <typename WordType> - inline typename BitsetBase<1, WordType>::size_type - BitsetBase<1, WordType>::DoFindNext(size_type last_find) const - { - if(++last_find < kBitsPerWord) - { - // Mask off previous bits of word so our search becomes a "find first". - const word_type this_word = mWord[0] & ((~static_cast<word_type>(0)) << last_find); - - return GetFirstBit(this_word); - } - - return kBitsPerWord; - } - - - template <typename WordType> - inline typename BitsetBase<1, WordType>::size_type - BitsetBase<1, WordType>::DoFindLast() const - { - return GetLastBit(mWord[0]); - } - - - template <typename WordType> - inline typename BitsetBase<1, WordType>::size_type - BitsetBase<1, WordType>::DoFindPrev(size_type last_find) const - { - if(last_find > 0) - { - // Mask off previous bits of word so our search becomes a "find first". - const word_type this_word = mWord[0] & ((~static_cast<word_type>(0)) >> (kBitsPerWord - last_find)); - - return GetLastBit(this_word); - } - - return kBitsPerWord; - } - - - - - /////////////////////////////////////////////////////////////////////////// - // BitsetBase<2, WordType> - /////////////////////////////////////////////////////////////////////////// - - template <typename WordType> - inline BitsetBase<2, WordType>::BitsetBase() - { - mWord[0] = 0; - mWord[1] = 0; - } - - - template <typename WordType> - inline BitsetBase<2, WordType>::BitsetBase(uint32_t value) - { - // This implementation assumes that sizeof(value) <= sizeof(word_type). - //EASTL_CT_ASSERT(sizeof(value) <= sizeof(word_type)); Disabled because we now have support for uint8_t and uint16_t word types. It would be nice to have a runtime assert that tested this. - - mWord[0] = static_cast<word_type>(value); - mWord[1] = 0; - } - - - /* - template <typename WordType> - inline BitsetBase<2, WordType>::BitsetBase(uint64_t value) - { - #if(EA_PLATFORM_WORD_SIZE == 4) - mWord[0] = static_cast<word_type>(value); - mWord[1] = static_cast<word_type>(value >> 32); - #else - mWord[0] = static_cast<word_type>(value); - mWord[1] = 0; - #endif - } - */ - - - template <typename WordType> - inline void BitsetBase<2, WordType>::operator&=(const this_type& x) - { - mWord[0] &= x.mWord[0]; - mWord[1] &= x.mWord[1]; - } - - - template <typename WordType> - inline void BitsetBase<2, WordType>::operator|=(const this_type& x) - { - mWord[0] |= x.mWord[0]; - mWord[1] |= x.mWord[1]; - } - - - template <typename WordType> - inline void BitsetBase<2, WordType>::operator^=(const this_type& x) - { - mWord[0] ^= x.mWord[0]; - mWord[1] ^= x.mWord[1]; - } - - - template <typename WordType> - inline void BitsetBase<2, WordType>::operator<<=(size_type n) - { - if(n) // to avoid a shift by kBitsPerWord, which is undefined - { - if(EASTL_UNLIKELY(n >= kBitsPerWord)) // parent expected to handle high bits and n >= 64 - { - mWord[1] = mWord[0]; - mWord[0] = 0; - n -= kBitsPerWord; - } - - mWord[1] = (mWord[1] << n) | (mWord[0] >> (kBitsPerWord - n)); // Intentionally use | instead of +. - mWord[0] <<= n; - // We let the parent class turn off any upper bits. - } - } - - - template <typename WordType> - inline void BitsetBase<2, WordType>::operator>>=(size_type n) - { - if(n) // to avoid a shift by kBitsPerWord, which is undefined - { - if(EASTL_UNLIKELY(n >= kBitsPerWord)) // parent expected to handle n >= 64 - { - mWord[0] = mWord[1]; - mWord[1] = 0; - n -= kBitsPerWord; - } - - mWord[0] = (mWord[0] >> n) | (mWord[1] << (kBitsPerWord - n)); // Intentionally use | instead of +. - mWord[1] >>= n; - } - } - - - template <typename WordType> - inline void BitsetBase<2, WordType>::flip() - { - mWord[0] = ~mWord[0]; - mWord[1] = ~mWord[1]; - // We let the parent class turn off any upper bits. - } - - - template <typename WordType> - inline void BitsetBase<2, WordType>::set() - { - mWord[0] = ~static_cast<word_type>(0); - mWord[1] = ~static_cast<word_type>(0); - // We let the parent class turn off any upper bits. - } - - - template <typename WordType> - inline void BitsetBase<2, WordType>::set(size_type i, bool value) - { - if(value) - mWord[i >> kBitsPerWordShift] |= (static_cast<word_type>(1) << (i & kBitsPerWordMask)); - else - mWord[i >> kBitsPerWordShift] &= ~(static_cast<word_type>(1) << (i & kBitsPerWordMask)); - } - - - template <typename WordType> - inline void BitsetBase<2, WordType>::reset() - { - mWord[0] = 0; - mWord[1] = 0; - } - - - template <typename WordType> - inline bool BitsetBase<2, WordType>::operator==(const this_type& x) const - { - return (mWord[0] == x.mWord[0]) && (mWord[1] == x.mWord[1]); - } - - - template <typename WordType> - inline bool BitsetBase<2, WordType>::any() const - { - // Or with two branches: { return (mWord[0] != 0) || (mWord[1] != 0); } - return (mWord[0] | mWord[1]) != 0; - } - - template <typename WordType> - inline typename BitsetBase<2, WordType>::size_type - BitsetBase<2, WordType>::count() const - { - #if (defined(__GNUC__) && (((__GNUC__ * 100) + __GNUC_MINOR__) >= 304)) || defined(__clang__) // GCC 3.4 or later - #if(EA_PLATFORM_WORD_SIZE == 4) - return (size_type)__builtin_popcountl(mWord[0]) + (size_type)__builtin_popcountl(mWord[1]); - #else - return (size_type)__builtin_popcountll(mWord[0]) + (size_type)__builtin_popcountll(mWord[1]); - #endif - - #else - return BitsetCountBits(mWord[0]) + BitsetCountBits(mWord[1]); - #endif - } - - - template <typename WordType> - inline void BitsetBase<2, WordType>::from_uint32(uint32_t value) - { - mWord[0] = static_cast<word_type>(value); - mWord[1] = 0; - } - - - template <typename WordType> - inline void BitsetBase<2, WordType>::from_uint64(uint64_t value) - { - #if(EA_PLATFORM_WORD_SIZE == 4) - mWord[0] = static_cast<word_type>(value); - mWord[1] = static_cast<word_type>(value >> 32); - #else - mWord[0] = static_cast<word_type>(value); - mWord[1] = 0; - #endif - } - - - template <typename WordType> - inline unsigned long BitsetBase<2, WordType>::to_ulong() const - { - #if EASTL_EXCEPTIONS_ENABLED - if(mWord[1]) - throw std::overflow_error("BitsetBase::to_ulong"); - #endif - return (unsigned long)mWord[0]; // Todo: We need to deal with the case whereby sizeof(word_type) < sizeof(unsigned long) - } - - - template <typename WordType> - inline uint32_t BitsetBase<2, WordType>::to_uint32() const - { - #if EASTL_EXCEPTIONS_ENABLED - // Verify that high words or bits are not set and thus that to_uint32 doesn't lose information. - - #if(EA_PLATFORM_WORD_SIZE == 4) - if(mWord[1]) - throw std::overflow_error("BitsetBase::to_uint32"); - #else - if(mWord[1] || (mWord[0] >> 32)) - throw std::overflow_error("BitsetBase::to_uint32"); - #endif - #endif - - return (uint32_t)mWord[0]; - } - - - template <typename WordType> - inline uint64_t BitsetBase<2, WordType>::to_uint64() const - { - #if(EA_PLATFORM_WORD_SIZE == 4) - // There can't possibly be an overflow_error here. - - return ((uint64_t)mWord[1] << 32) | mWord[0]; - #else - #if EASTL_EXCEPTIONS_ENABLED - if(mWord[1]) - throw std::overflow_error("BitsetBase::to_uint64"); - #endif - - return (uint64_t)mWord[0]; - #endif - } - - - template <typename WordType> - inline typename BitsetBase<2, WordType>::word_type& - BitsetBase<2, WordType>::DoGetWord(size_type i) - { - return mWord[i >> kBitsPerWordShift]; - } - - - template <typename WordType> - inline typename BitsetBase<2, WordType>::word_type - BitsetBase<2, WordType>::DoGetWord(size_type i) const - { - return mWord[i >> kBitsPerWordShift]; - } - - - template <typename WordType> - inline typename BitsetBase<2, WordType>::size_type - BitsetBase<2, WordType>::DoFindFirst() const - { - size_type fbiw = GetFirstBit(mWord[0]); - - if(fbiw != kBitsPerWord) - return fbiw; - - fbiw = GetFirstBit(mWord[1]); - - if(fbiw != kBitsPerWord) - return kBitsPerWord + fbiw; - - return 2 * kBitsPerWord; - } - - - template <typename WordType> - inline typename BitsetBase<2, WordType>::size_type - BitsetBase<2, WordType>::DoFindNext(size_type last_find) const - { - // If the last find was in the first word, we must check it and then possibly the second. - if(++last_find < (size_type)kBitsPerWord) - { - // Mask off previous bits of word so our search becomes a "find first". - word_type this_word = mWord[0] & ((~static_cast<word_type>(0)) << last_find); - - // Step through words. - size_type fbiw = GetFirstBit(this_word); - - if(fbiw != kBitsPerWord) - return fbiw; - - fbiw = GetFirstBit(mWord[1]); - - if(fbiw != kBitsPerWord) - return kBitsPerWord + fbiw; - } - else if(last_find < (size_type)(2 * kBitsPerWord)) - { - // The last find was in the second word, remove the bit count of the first word from the find. - last_find -= kBitsPerWord; - - // Mask off previous bits of word so our search becomes a "find first". - word_type this_word = mWord[1] & ((~static_cast<word_type>(0)) << last_find); - - const size_type fbiw = GetFirstBit(this_word); - - if(fbiw != kBitsPerWord) - return kBitsPerWord + fbiw; - } - - return 2 * kBitsPerWord; - } - - - template <typename WordType> - inline typename BitsetBase<2, WordType>::size_type - BitsetBase<2, WordType>::DoFindLast() const - { - size_type lbiw = GetLastBit(mWord[1]); - - if(lbiw != kBitsPerWord) - return kBitsPerWord + lbiw; - - lbiw = GetLastBit(mWord[0]); - - if(lbiw != kBitsPerWord) - return lbiw; - - return 2 * kBitsPerWord; - } - - - template <typename WordType> - inline typename BitsetBase<2, WordType>::size_type - BitsetBase<2, WordType>::DoFindPrev(size_type last_find) const - { - // If the last find was in the second word, we must check it and then possibly the first. - if(last_find > (size_type)kBitsPerWord) - { - // This has the same effect as last_find %= kBitsPerWord in our case. - last_find -= kBitsPerWord; - - // Mask off previous bits of word so our search becomes a "find first". - word_type this_word = mWord[1] & ((~static_cast<word_type>(0)) >> (kBitsPerWord - last_find)); - - // Step through words. - size_type lbiw = GetLastBit(this_word); - - if(lbiw != kBitsPerWord) - return kBitsPerWord + lbiw; - - lbiw = GetLastBit(mWord[0]); - - if(lbiw != kBitsPerWord) - return lbiw; - } - else if(last_find != 0) - { - // Mask off previous bits of word so our search becomes a "find first". - word_type this_word = mWord[0] & ((~static_cast<word_type>(0)) >> (kBitsPerWord - last_find)); - - const size_type lbiw = GetLastBit(this_word); - - if(lbiw != kBitsPerWord) - return lbiw; - } - - return 2 * kBitsPerWord; - } - - - - /////////////////////////////////////////////////////////////////////////// - // bitset::reference - /////////////////////////////////////////////////////////////////////////// - - template <size_t N, typename WordType> - inline bitset<N, WordType>::reference::reference(const bitset& x, size_type i) - : mpBitWord(&const_cast<bitset&>(x).DoGetWord(i)), - mnBitIndex(i & kBitsPerWordMask) - { // We have an issue here because the above is casting away the const-ness of the source bitset. - // Empty - } - - - template <size_t N, typename WordType> - inline typename bitset<N, WordType>::reference& - bitset<N, WordType>::reference::operator=(bool value) - { - if(value) - *mpBitWord |= (static_cast<word_type>(1) << (mnBitIndex & kBitsPerWordMask)); - else - *mpBitWord &= ~(static_cast<word_type>(1) << (mnBitIndex & kBitsPerWordMask)); - return *this; - } - - - template <size_t N, typename WordType> - inline typename bitset<N, WordType>::reference& - bitset<N, WordType>::reference::operator=(const reference& x) - { - if(*x.mpBitWord & (static_cast<word_type>(1) << (x.mnBitIndex & kBitsPerWordMask))) - *mpBitWord |= (static_cast<word_type>(1) << (mnBitIndex & kBitsPerWordMask)); - else - *mpBitWord &= ~(static_cast<word_type>(1) << (mnBitIndex & kBitsPerWordMask)); - return *this; - } - - - template <size_t N, typename WordType> - inline bool bitset<N, WordType>::reference::operator~() const - { - return (*mpBitWord & (static_cast<word_type>(1) << (mnBitIndex & kBitsPerWordMask))) == 0; - } - - - //Defined inline in the class because Metrowerks fails to be able to compile it here. - //template <size_t N, typename WordType> - //inline bitset<N, WordType>::reference::operator bool() const - //{ - // return (*mpBitWord & (static_cast<word_type>(1) << (mnBitIndex & kBitsPerWordMask))) != 0; - //} - - - template <size_t N, typename WordType> - inline typename bitset<N, WordType>::reference& - bitset<N, WordType>::reference::flip() - { - *mpBitWord ^= static_cast<word_type>(1) << (mnBitIndex & kBitsPerWordMask); - return *this; - } - - - - - /////////////////////////////////////////////////////////////////////////// - // bitset - /////////////////////////////////////////////////////////////////////////// - - template <size_t N, typename WordType> - inline bitset<N, WordType>::bitset() - : base_type() - { - // Empty. The base class will set all bits to zero. - } - - EA_DISABLE_VC_WARNING(6313) - template <size_t N, typename WordType> - inline bitset<N, WordType>::bitset(uint32_t value) - : base_type(value) - { - if((N & kBitsPerWordMask) || (N == 0)) // If there are any high bits to clear... (If we didn't have this check, then the code below would do the wrong thing when N == 32. - mWord[kWordCount - 1] &= ~(static_cast<word_type>(~static_cast<word_type>(0)) << (N & kBitsPerWordMask)); // This clears any high unused bits. - } - EA_RESTORE_VC_WARNING() - - /* - template <size_t N, typename WordType> - inline bitset<N, WordType>::bitset(uint64_t value) - : base_type(value) - { - if((N & kBitsPerWordMask) || (N == 0)) // If there are any high bits to clear... - mWord[kWordCount - 1] &= ~(~static_cast<word_type>(0) << (N & kBitsPerWordMask)); // This clears any high unused bits. - } - */ - - - template <size_t N, typename WordType> - inline typename bitset<N, WordType>::this_type& - bitset<N, WordType>::operator&=(const this_type& x) - { - base_type::operator&=(x); - return *this; - } - - - template <size_t N, typename WordType> - inline typename bitset<N, WordType>::this_type& - bitset<N, WordType>::operator|=(const this_type& x) - { - base_type::operator|=(x); - return *this; - } - - - template <size_t N, typename WordType> - inline typename bitset<N, WordType>::this_type& - bitset<N, WordType>::operator^=(const this_type& x) - { - base_type::operator^=(x); - return *this; - } - - - template <size_t N, typename WordType> - inline typename bitset<N, WordType>::this_type& - bitset<N, WordType>::operator<<=(size_type n) - { - if(EASTL_LIKELY((intptr_t)n < (intptr_t)N)) - { - EA_DISABLE_VC_WARNING(6313) - base_type::operator<<=(n); - if((N & kBitsPerWordMask) || (N == 0)) // If there are any high bits to clear... (If we didn't have this check, then the code below would do the wrong thing when N == 32. - mWord[kWordCount - 1] &= ~(static_cast<word_type>(~static_cast<word_type>(0)) << (N & kBitsPerWordMask)); // This clears any high unused bits. We need to do this so that shift operations proceed correctly. - EA_RESTORE_VC_WARNING() - } - else - base_type::reset(); - return *this; - } - - - template <size_t N, typename WordType> - inline typename bitset<N, WordType>::this_type& - bitset<N, WordType>::operator>>=(size_type n) - { - if(EASTL_LIKELY(n < N)) - base_type::operator>>=(n); - else - base_type::reset(); - return *this; - } - - - template <size_t N, typename WordType> - inline typename bitset<N, WordType>::this_type& - bitset<N, WordType>::set() - { - base_type::set(); // This sets all bits. - if((N & kBitsPerWordMask) || (N == 0)) // If there are any high bits to clear... (If we didn't have this check, then the code below would do the wrong thing when N == 32. - mWord[kWordCount - 1] &= ~(static_cast<word_type>(~static_cast<word_type>(0)) << (N & kBitsPerWordMask)); // This clears any high unused bits. We need to do this so that shift operations proceed correctly. - return *this; - } - - - template <size_t N, typename WordType> - inline typename bitset<N, WordType>::this_type& - bitset<N, WordType>::set(size_type i, bool value) - { - if(i < N) - base_type::set(i, value); - else - { - #if EASTL_ASSERT_ENABLED - if(EASTL_UNLIKELY(!(i < N))) - EASTL_FAIL_MSG("bitset::set -- out of range"); - #endif - - #if EASTL_EXCEPTIONS_ENABLED - throw std::out_of_range("bitset::set"); - #endif - } - - return *this; - } - - - template <size_t N, typename WordType> - inline typename bitset<N, WordType>::this_type& - bitset<N, WordType>::reset() - { - base_type::reset(); - return *this; - } - - - template <size_t N, typename WordType> - inline typename bitset<N, WordType>::this_type& - bitset<N, WordType>::reset(size_type i) - { - if(EASTL_LIKELY(i < N)) - DoGetWord(i) &= ~(static_cast<word_type>(1) << (i & kBitsPerWordMask)); - else - { - #if EASTL_ASSERT_ENABLED - if(EASTL_UNLIKELY(!(i < N))) - EASTL_FAIL_MSG("bitset::reset -- out of range"); - #endif - - #if EASTL_EXCEPTIONS_ENABLED - throw std::out_of_range("bitset::reset"); - #endif - } - - return *this; - } - - - template <size_t N, typename WordType> - inline typename bitset<N, WordType>::this_type& - bitset<N, WordType>::flip() - { - EA_DISABLE_VC_WARNING(6313) - base_type::flip(); - if((N & kBitsPerWordMask) || (N == 0)) // If there are any high bits to clear... (If we didn't have this check, then the code below would do the wrong thing when N == 32. - mWord[kWordCount - 1] &= ~(static_cast<word_type>(~static_cast<word_type>(0)) << (N & kBitsPerWordMask)); // This clears any high unused bits. We need to do this so that shift operations proceed correctly. - return *this; - EA_RESTORE_VC_WARNING() - } - - - template <size_t N, typename WordType> - inline typename bitset<N, WordType>::this_type& - bitset<N, WordType>::flip(size_type i) - { - if(EASTL_LIKELY(i < N)) - DoGetWord(i) ^= (static_cast<word_type>(1) << (i & kBitsPerWordMask)); - else - { - #if EASTL_ASSERT_ENABLED - if(EASTL_UNLIKELY(!(i < N))) - EASTL_FAIL_MSG("bitset::flip -- out of range"); - #endif - - #if EASTL_EXCEPTIONS_ENABLED - throw std::out_of_range("bitset::flip"); - #endif - } - return *this; - } - - - template <size_t N, typename WordType> - inline typename bitset<N, WordType>::this_type - bitset<N, WordType>::operator~() const - { - return this_type(*this).flip(); - } - - - template <size_t N, typename WordType> - inline typename bitset<N, WordType>::reference - bitset<N, WordType>::operator[](size_type i) - { - #if EASTL_ASSERT_ENABLED - if(EASTL_UNLIKELY(!(i < N))) - EASTL_FAIL_MSG("bitset::operator[] -- out of range"); - #endif - - return reference(*this, i); - } - - - template <size_t N, typename WordType> - inline bool bitset<N, WordType>::operator[](size_type i) const - { - #if EASTL_ASSERT_ENABLED - if(EASTL_UNLIKELY(!(i < N))) - EASTL_FAIL_MSG("bitset::operator[] -- out of range"); - #endif - - return (DoGetWord(i) & (static_cast<word_type>(1) << (i & kBitsPerWordMask))) != 0; - } - - - template <size_t N, typename WordType> - inline const typename bitset<N, WordType>::word_type* bitset<N, WordType>::data() const - { - return base_type::mWord; - } - - - template <size_t N, typename WordType> - inline typename bitset<N, WordType>::word_type* bitset<N, WordType>::data() - { - return base_type::mWord; - } - - - template <size_t N, typename WordType> - inline void bitset<N, WordType>::from_uint32(uint32_t value) - { - base_type::from_uint32(value); - - if((N & kBitsPerWordMask) || (N == 0)) // If there are any high bits to clear... (If we didn't have this check, then the code below would do the wrong thing when N == 32. - mWord[kWordCount - 1] &= ~(static_cast<word_type>(~static_cast<word_type>(0)) << (N & kBitsPerWordMask)); // This clears any high unused bits. We need to do this so that shift operations proceed correctly. - } - - - template <size_t N, typename WordType> - inline void bitset<N, WordType>::from_uint64(uint64_t value) - { - base_type::from_uint64(value); - - if((N & kBitsPerWordMask) || (N == 0)) // If there are any high bits to clear... (If we didn't have this check, then the code below would do the wrong thing when N == 32. - mWord[kWordCount - 1] &= ~(static_cast<word_type>(~static_cast<word_type>(0)) << (N & kBitsPerWordMask)); // This clears any high unused bits. We need to do this so that shift operations proceed correctly. - } - - - // template <size_t N, typename WordType> - // inline unsigned long bitset<N, WordType>::to_ulong() const - // { - // return base_type::to_ulong(); - // } - - - // template <size_t N, typename WordType> - // inline uint32_t bitset<N, WordType>::to_uint32() const - // { - // return base_type::to_uint32(); - // } - - - // template <size_t N, typename WordType> - // inline uint64_t bitset<N, WordType>::to_uint64() const - // { - // return base_type::to_uint64(); - // } - - - // template <size_t N, typename WordType> - // inline typename bitset<N, WordType>::size_type - // bitset<N, WordType>::count() const - // { - // return base_type::count(); - // } - - - template <size_t N, typename WordType> - inline typename bitset<N, WordType>::size_type - bitset<N, WordType>::size() const - { - return (size_type)N; - } - - - template <size_t N, typename WordType> - inline bool bitset<N, WordType>::operator==(const this_type& x) const - { - return base_type::operator==(x); - } - -#if !defined(EA_COMPILER_HAS_THREE_WAY_COMPARISON) - template <size_t N, typename WordType> - inline bool bitset<N, WordType>::operator!=(const this_type& x) const - { - return !base_type::operator==(x); - } -#endif - - template <size_t N, typename WordType> - inline bool bitset<N, WordType>::test(size_type i) const - { - if(EASTL_UNLIKELY(i < N)) - return (DoGetWord(i) & (static_cast<word_type>(1) << (i & kBitsPerWordMask))) != 0; - - #if EASTL_ASSERT_ENABLED - EASTL_FAIL_MSG("bitset::test -- out of range"); - #endif - - #if EASTL_EXCEPTIONS_ENABLED - throw std::out_of_range("bitset::test"); - #else - return false; - #endif - } - - - // template <size_t N, typename WordType> - // inline bool bitset<N, WordType>::any() const - // { - // return base_type::any(); - // } - - - template <size_t N, typename WordType> - inline bool bitset<N, WordType>::all() const - { - return count() == size(); - } - - - template <size_t N, typename WordType> - inline bool bitset<N, WordType>::none() const - { - return !base_type::any(); - } - - - template <size_t N, typename WordType> - inline typename bitset<N, WordType>::this_type - bitset<N, WordType>::operator<<(size_type n) const - { - return this_type(*this).operator<<=(n); - } - - - template <size_t N, typename WordType> - inline typename bitset<N, WordType>::this_type - bitset<N, WordType>::operator>>(size_type n) const - { - return this_type(*this).operator>>=(n); - } - - - template <size_t N, typename WordType> - inline typename bitset<N, WordType>::size_type - bitset<N, WordType>::find_first() const - { - const size_type i = base_type::DoFindFirst(); - - if(i < kSize) - return i; - // Else i could be the base type bit count, so we clamp it to our size. - - return kSize; - } - - - template <size_t N, typename WordType> - inline typename bitset<N, WordType>::size_type - bitset<N, WordType>::find_next(size_type last_find) const - { - const size_type i = base_type::DoFindNext(last_find); - - if(i < kSize) - return i; - // Else i could be the base type bit count, so we clamp it to our size. - - return kSize; - } - - - template <size_t N, typename WordType> - inline typename bitset<N, WordType>::size_type - bitset<N, WordType>::find_last() const - { - const size_type i = base_type::DoFindLast(); - - if(i < kSize) - return i; - // Else i could be the base type bit count, so we clamp it to our size. - - return kSize; - } - - - template <size_t N, typename WordType> - inline typename bitset<N, WordType>::size_type - bitset<N, WordType>::find_prev(size_type last_find) const - { - const size_type i = base_type::DoFindPrev(last_find); - - if(i < kSize) - return i; - // Else i could be the base type bit count, so we clamp it to our size. - - return kSize; - } - - - - /////////////////////////////////////////////////////////////////////////// - // global operators - /////////////////////////////////////////////////////////////////////////// - - template <size_t N, typename WordType> - inline bitset<N, WordType> operator&(const bitset<N, WordType>& a, const bitset<N, WordType>& b) - { - // We get betting inlining when we don't declare temporary variables. - return bitset<N, WordType>(a).operator&=(b); - } - - - template <size_t N, typename WordType> - inline bitset<N, WordType> operator|(const bitset<N, WordType>& a, const bitset<N, WordType>& b) - { - return bitset<N, WordType>(a).operator|=(b); - } - - - template <size_t N, typename WordType> - inline bitset<N, WordType> operator^(const bitset<N, WordType>& a, const bitset<N, WordType>& b) - { - return bitset<N, WordType>(a).operator^=(b); - } - - -} // namespace eastl - - -EA_RESTORE_VC_WARNING(); - -#endif // Header include guard |