Nugget
bitset.h
1 // Copyright (c) Electronic Arts Inc. All rights reserved.
4 
6 // This file implements a bitset much like the C++ std::bitset class.
7 // The primary distinctions between this list and std::bitset are:
8 // - bitset is more efficient than some other std::bitset implementations,
9 // notably the bitset that comes with Microsoft and other 1st party platforms.
10 // - bitset is savvy to an environment that doesn't have exception handling,
11 // as is sometimes the case with console or embedded environments.
12 // - bitset is savvy to environments in which 'unsigned long' is not the
13 // most efficient integral data type. std::bitset implementations use
14 // unsigned long, even if it is an inefficient integer type.
15 // - bitset removes as much function calls as practical, in order to allow
16 // debug builds to run closer in speed and code footprint to release builds.
17 // - bitset doesn't support string functionality. We can add this if
18 // it is deemed useful.
19 //
21 
22 
23 #ifndef EASTL_BITSET_H
24 #define EASTL_BITSET_H
25 
26 
27 #include <EASTL/internal/config.h>
28 #include <EASTL/algorithm.h>
29 
30 EA_DISABLE_ALL_VC_WARNINGS();
31 
32 #include <stddef.h>
33 #include <string.h>
34 
35 EA_RESTORE_ALL_VC_WARNINGS();
36 
37 #if EASTL_EXCEPTIONS_ENABLED
38  EA_DISABLE_ALL_VC_WARNINGS();
39 
40  #include <stdexcept> // std::out_of_range, std::length_error.
41 
42  EA_RESTORE_ALL_VC_WARNINGS();
43 #endif
44 
45 EA_DISABLE_VC_WARNING(4127); // Conditional expression is constant
46 
47 #if defined(EA_PRAGMA_ONCE_SUPPORTED)
48  #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.
49 #endif
50 
51 
52 
53 namespace eastl
54 {
55  // To consider: Enable this for backwards compatibility with any user code that might be using BitsetWordType:
56  // #define BitsetWordType EASTL_BITSET_WORD_TYPE_DEFAULT
57 
58 
65  #if !defined(__GNUC__) || (__GNUC__ >= 3) // GCC 2.x can't handle the simpler declaration below.
66  #define BITSET_WORD_COUNT(nBitCount, WordType) (nBitCount == 0 ? 1 : ((nBitCount - 1) / (8 * sizeof(WordType)) + 1))
67  #else
68  #define BITSET_WORD_COUNT(nBitCount, WordType) ((nBitCount - 1) / (8 * sizeof(WordType)) + 1)
69  #endif
70 
71 
77  #if defined(__GNUC__) && (EA_COMPILER_VERSION > 4007) && defined(EA_PLATFORM_ANDROID) // Earlier than GCC 4.7
78  #define EASTL_DISABLE_BITSET_ARRAYBOUNDS_WARNING 1
79  #else
80  #define EASTL_DISABLE_BITSET_ARRAYBOUNDS_WARNING 0
81  #endif
82 
83 
84 
89  template <size_t NW, typename WordType> // Templated on the number of words used to hold the bitset and the word type.
90  struct BitsetBase
91  {
92  typedef WordType word_type;
93  typedef BitsetBase<NW, WordType> this_type;
94  #if EASTL_BITSET_SIZE_T
95  typedef size_t size_type;
96  #else
97  typedef eastl_size_t size_type;
98  #endif
99 
100  enum {
101  kBitsPerWord = (8 * sizeof(word_type)),
102  kBitsPerWordMask = (kBitsPerWord - 1),
103  kBitsPerWordShift = ((kBitsPerWord == 8) ? 3 : ((kBitsPerWord == 16) ? 4 : ((kBitsPerWord == 32) ? 5 : (((kBitsPerWord == 64) ? 6 : 7)))))
104  };
105 
106  public:
107  word_type mWord[NW];
108 
109  public:
110  BitsetBase();
111  BitsetBase(uint32_t value); // This exists only for compatibility with std::bitset, which has a 'long' constructor.
112  //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.
113 
114  void operator&=(const this_type& x);
115  void operator|=(const this_type& x);
116  void operator^=(const this_type& x);
117 
118  void operator<<=(size_type n);
119  void operator>>=(size_type n);
120 
121  void flip();
122  void set();
123  void set(size_type i, bool value);
124  void reset();
125 
126  bool operator==(const this_type& x) const;
127 
128  bool any() const;
129  size_type count() const;
130 
131  void from_uint32(uint32_t value);
132  void from_uint64(uint64_t value);
133 
134  unsigned long to_ulong() const;
135  uint32_t to_uint32() const;
136  uint64_t to_uint64() const;
137 
138  word_type& DoGetWord(size_type i);
139  word_type DoGetWord(size_type i) const;
140 
141  size_type DoFindFirst() const;
142  size_type DoFindNext(size_type last_find) const;
143 
144  size_type DoFindLast() const; // Returns NW * kBitsPerWord (the bit count) if no bits are set.
145  size_type DoFindPrev(size_type last_find) const; // Returns NW * kBitsPerWord (the bit count) if no bits are set.
146 
147  }; // class BitsetBase
148 
149 
150 
155  template <typename WordType>
156  struct BitsetBase<1, WordType>
157  {
158  typedef WordType word_type;
159  typedef BitsetBase<1, WordType> this_type;
160  #if EASTL_BITSET_SIZE_T
161  typedef size_t size_type;
162  #else
163  typedef eastl_size_t size_type;
164  #endif
165 
166  enum {
167  kBitsPerWord = (8 * sizeof(word_type)),
168  kBitsPerWordMask = (kBitsPerWord - 1),
169  kBitsPerWordShift = ((kBitsPerWord == 8) ? 3 : ((kBitsPerWord == 16) ? 4 : ((kBitsPerWord == 32) ? 5 : (((kBitsPerWord == 64) ? 6 : 7)))))
170  };
171 
172  public:
173  word_type mWord[1]; // Defined as an array of 1 so that bitset can treat this BitsetBase like others.
174 
175  public:
176  BitsetBase();
177  BitsetBase(uint32_t value);
178  //BitsetBase(uint64_t value); // Disabled because it causes conflicts with the 32 bit version with existing user code. Use from_uint64 instead.
179 
180  void operator&=(const this_type& x);
181  void operator|=(const this_type& x);
182  void operator^=(const this_type& x);
183 
184  void operator<<=(size_type n);
185  void operator>>=(size_type n);
186 
187  void flip();
188  void set();
189  void set(size_type i, bool value);
190  void reset();
191 
192  bool operator==(const this_type& x) const;
193 
194  bool any() const;
195  size_type count() const;
196 
197  void from_uint32(uint32_t value);
198  void from_uint64(uint64_t value);
199 
200  unsigned long to_ulong() const;
201  uint32_t to_uint32() const;
202  uint64_t to_uint64() const;
203 
204  word_type& DoGetWord(size_type);
205  word_type DoGetWord(size_type) const;
206 
207  size_type DoFindFirst() const;
208  size_type DoFindNext(size_type last_find) const;
209 
210  size_type DoFindLast() const; // Returns 1 * kBitsPerWord (the bit count) if no bits are set.
211  size_type DoFindPrev(size_type last_find) const; // Returns 1 * kBitsPerWord (the bit count) if no bits are set.
212 
213  }; // BitsetBase<1, WordType>
214 
215 
216 
222  template <typename WordType>
223  struct BitsetBase<2, WordType>
224  {
225  typedef WordType word_type;
226  typedef BitsetBase<2, WordType> this_type;
227  #if EASTL_BITSET_SIZE_T
228  typedef size_t size_type;
229  #else
230  typedef eastl_size_t size_type;
231  #endif
232 
233  enum {
234  kBitsPerWord = (8 * sizeof(word_type)),
235  kBitsPerWordMask = (kBitsPerWord - 1),
236  kBitsPerWordShift = ((kBitsPerWord == 8) ? 3 : ((kBitsPerWord == 16) ? 4 : ((kBitsPerWord == 32) ? 5 : (((kBitsPerWord == 64) ? 6 : 7)))))
237  };
238 
239  public:
240  word_type mWord[2];
241 
242  public:
243  BitsetBase();
244  BitsetBase(uint32_t value);
245  //BitsetBase(uint64_t value); // Disabled because it causes conflicts with the 32 bit version with existing user code. Use from_uint64 instead.
246 
247  void operator&=(const this_type& x);
248  void operator|=(const this_type& x);
249  void operator^=(const this_type& x);
250 
251  void operator<<=(size_type n);
252  void operator>>=(size_type n);
253 
254  void flip();
255  void set();
256  void set(size_type i, bool value);
257  void reset();
258 
259  bool operator==(const this_type& x) const;
260 
261  bool any() const;
262  size_type count() const;
263 
264  void from_uint32(uint32_t value);
265  void from_uint64(uint64_t value);
266 
267  unsigned long to_ulong() const;
268  uint32_t to_uint32() const;
269  uint64_t to_uint64() const;
270 
271  word_type& DoGetWord(size_type);
272  word_type DoGetWord(size_type) const;
273 
274  size_type DoFindFirst() const;
275  size_type DoFindNext(size_type last_find) const;
276 
277  size_type DoFindLast() const; // Returns 2 * kBitsPerWord (the bit count) if no bits are set.
278  size_type DoFindPrev(size_type last_find) const; // Returns 2 * kBitsPerWord (the bit count) if no bits are set.
279 
280  }; // BitsetBase<2, WordType>
281 
282 
283 
284 
302  template <size_t N, typename WordType = EASTL_BITSET_WORD_TYPE_DEFAULT>
303  class bitset : private BitsetBase<BITSET_WORD_COUNT(N, WordType), WordType>
304  {
305  public:
306  typedef BitsetBase<BITSET_WORD_COUNT(N, WordType), WordType> base_type;
307  typedef bitset<N, WordType> this_type;
308  typedef WordType word_type;
309  typedef typename base_type::size_type size_type;
310 
311  enum
312  {
313  kBitsPerWord = (8 * sizeof(word_type)),
314  kBitsPerWordMask = (kBitsPerWord - 1),
315  kBitsPerWordShift = ((kBitsPerWord == 8) ? 3 : ((kBitsPerWord == 16) ? 4 : ((kBitsPerWord == 32) ? 5 : (((kBitsPerWord == 64) ? 6 : 7))))),
316  kSize = N, // The number of bits the bitset holds
317  kWordSize = sizeof(word_type), // The size of individual words the bitset uses to hold the bits.
318  kWordCount = BITSET_WORD_COUNT(N, WordType) // The number of words the bitset uses to hold the bits. sizeof(bitset<N, WordType>) == kWordSize * kWordCount.
319  };
320 
321  using base_type::mWord;
322  using base_type::DoGetWord;
323  using base_type::DoFindFirst;
324  using base_type::DoFindNext;
325  using base_type::DoFindLast;
326  using base_type::DoFindPrev;
327  using base_type::to_ulong;
328  using base_type::to_uint32;
329  using base_type::to_uint64;
330  using base_type::count;
331  using base_type::any;
332 
333  public:
341  class reference
342  {
343  protected:
344  friend class bitset<N, WordType>;
345 
346  word_type* mpBitWord;
347  size_type mnBitIndex;
348 
349  reference(){} // The C++ standard specifies that this is private.
350 
351  public:
352  reference(const bitset& x, size_type i);
353 
354  reference& operator=(bool value);
355  reference& operator=(const reference& x);
356 
357  bool operator~() const;
358  operator bool() const // Defined inline because CodeWarrior fails to be able to compile it outside.
359  { return (*mpBitWord & (static_cast<word_type>(1) << (mnBitIndex & kBitsPerWordMask))) != 0; }
360 
361  reference& flip();
362  };
363 
364  public:
365  friend class reference;
366 
367  bitset();
368  bitset(uint32_t value);
369  //bitset(uint64_t value); // Disabled because it causes conflicts with the 32 bit version with existing user code. Use from_uint64 instead.
370 
371  // We don't define copy constructor and operator= because
372  // the compiler-generated versions will suffice.
373 
374  this_type& operator&=(const this_type& x);
375  this_type& operator|=(const this_type& x);
376  this_type& operator^=(const this_type& x);
377 
378  this_type& operator<<=(size_type n);
379  this_type& operator>>=(size_type n);
380 
381  this_type& set();
382  this_type& set(size_type i, bool value = true);
383 
384  this_type& reset();
385  this_type& reset(size_type i);
386 
387  this_type& flip();
388  this_type& flip(size_type i);
389  this_type operator~() const;
390 
391  reference operator[](size_type i);
392  bool operator[](size_type i) const;
393 
394  const word_type* data() const;
395  word_type* data();
396 
397  void from_uint32(uint32_t value);
398  void from_uint64(uint64_t value);
399 
400  //unsigned long to_ulong() const; // We inherit this from the base class.
401  //uint32_t to_uint32() const;
402  //uint64_t to_uint64() const;
403 
404  //size_type count() const; // We inherit this from the base class.
405  size_type size() const;
406 
407  bool operator==(const this_type& x) const;
408  bool operator!=(const this_type& x) const;
409 
410  bool test(size_type i) const;
411  //bool any() const; // We inherit this from the base class.
412  bool all() const;
413  bool none() const;
414 
415  this_type operator<<(size_type n) const;
416  this_type operator>>(size_type n) const;
417 
418  // Finds the index of the first "on" bit, returns kSize if none are set.
419  size_type find_first() const;
420 
421  // Finds the index of the next "on" bit after last_find, returns kSize if none are set.
422  size_type find_next(size_type last_find) const;
423 
424  // Finds the index of the last "on" bit, returns kSize if none are set.
425  size_type find_last() const;
426 
427  // Finds the index of the last "on" bit before last_find, returns kSize if none are set.
428  size_type find_prev(size_type last_find) const;
429 
430  }; // bitset
431 
432 
433 
434 
435 
436 
437 
442  inline uint32_t BitsetCountBits(uint64_t x)
443  {
444  // GCC 3.x's implementation of UINT64_C is broken and fails to deal with
445  // the code below correctly. So we make a workaround for it. Earlier and
446  // later versions of GCC don't have this bug.
447 
448  #if defined(__GNUC__) && (__GNUC__ == 3)
449  x = x - ((x >> 1) & 0x5555555555555555ULL);
450  x = (x & 0x3333333333333333ULL) + ((x >> 2) & 0x3333333333333333ULL);
451  x = (x + (x >> 4)) & 0x0F0F0F0F0F0F0F0FULL;
452  return (uint32_t)((x * 0x0101010101010101ULL) >> 56);
453  #else
454  x = x - ((x >> 1) & UINT64_C(0x5555555555555555));
455  x = (x & UINT64_C(0x3333333333333333)) + ((x >> 2) & UINT64_C(0x3333333333333333));
456  x = (x + (x >> 4)) & UINT64_C(0x0F0F0F0F0F0F0F0F);
457  return (uint32_t)((x * UINT64_C(0x0101010101010101)) >> 56);
458  #endif
459  }
460 
461  inline uint32_t BitsetCountBits(uint32_t x)
462  {
463  x = x - ((x >> 1) & 0x55555555);
464  x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
465  x = (x + (x >> 4)) & 0x0F0F0F0F;
466  return (uint32_t)((x * 0x01010101) >> 24);
467  }
468 
469  inline uint32_t BitsetCountBits(uint16_t x)
470  {
471  return BitsetCountBits((uint32_t)x);
472  }
473 
474  inline uint32_t BitsetCountBits(uint8_t x)
475  {
476  return BitsetCountBits((uint32_t)x);
477  }
478 
479 
480  // const static char kBitsPerUint16[16] = { 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4 };
481  #define EASTL_BITSET_COUNT_STRING "\0\1\1\2\1\2\2\3\1\2\2\3\2\3\3\4"
482 
483 
484  inline uint32_t GetFirstBit(uint8_t x)
485  {
486  if(x)
487  {
488  uint32_t n = 1;
489 
490  if((x & 0x0000000F) == 0) { n += 4; x >>= 4; }
491  if((x & 0x00000003) == 0) { n += 2; x >>= 2; }
492 
493  return (uint32_t)(n - (x & 1));
494  }
495 
496  return 8;
497  }
498 
499  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
500  {
501  if(x)
502  {
503  uint32_t n = 1;
504 
505  if((x & 0x000000FF) == 0) { n += 8; x >>= 8; }
506  if((x & 0x0000000F) == 0) { n += 4; x >>= 4; }
507  if((x & 0x00000003) == 0) { n += 2; x >>= 2; }
508 
509  return (uint32_t)(n - (x & 1));
510  }
511 
512  return 16;
513  }
514 
515  inline uint32_t GetFirstBit(uint32_t x)
516  {
517  if(x)
518  {
519  uint32_t n = 1;
520 
521  if((x & 0x0000FFFF) == 0) { n += 16; x >>= 16; }
522  if((x & 0x000000FF) == 0) { n += 8; x >>= 8; }
523  if((x & 0x0000000F) == 0) { n += 4; x >>= 4; }
524  if((x & 0x00000003) == 0) { n += 2; x >>= 2; }
525 
526  return (n - (x & 1));
527  }
528 
529  return 32;
530  }
531 
532  inline uint32_t GetFirstBit(uint64_t x)
533  {
534  if(x)
535  {
536  uint32_t n = 1;
537 
538  if((x & 0xFFFFFFFF) == 0) { n += 32; x >>= 32; }
539  if((x & 0x0000FFFF) == 0) { n += 16; x >>= 16; }
540  if((x & 0x000000FF) == 0) { n += 8; x >>= 8; }
541  if((x & 0x0000000F) == 0) { n += 4; x >>= 4; }
542  if((x & 0x00000003) == 0) { n += 2; x >>= 2; }
543 
544  return (n - ((uint32_t)x & 1));
545  }
546 
547  return 64;
548  }
549 
550 
551  #if EASTL_INT128_SUPPORTED
552  inline uint32_t GetFirstBit(eastl_uint128_t x)
553  {
554  if(x)
555  {
556  uint32_t n = 1;
557 
558  if((x & UINT64_C(0xFFFFFFFFFFFFFFFF)) == 0) { n += 64; x >>= 64; }
559  if((x & 0xFFFFFFFF) == 0) { n += 32; x >>= 32; }
560  if((x & 0x0000FFFF) == 0) { n += 16; x >>= 16; }
561  if((x & 0x000000FF) == 0) { n += 8; x >>= 8; }
562  if((x & 0x0000000F) == 0) { n += 4; x >>= 4; }
563  if((x & 0x00000003) == 0) { n += 2; x >>= 2; }
564 
565  return (n - ((uint32_t)x & 1));
566  }
567 
568  return 128;
569  }
570  #endif
571 
572  inline uint32_t GetLastBit(uint8_t x)
573  {
574  if(x)
575  {
576  uint32_t n = 0;
577 
578  if(x & 0xFFF0) { n += 4; x >>= 4; }
579  if(x & 0xFFFC) { n += 2; x >>= 2; }
580  if(x & 0xFFFE) { n += 1; }
581 
582  return n;
583  }
584 
585  return 8;
586  }
587 
588  inline uint32_t GetLastBit(uint16_t x)
589  {
590  if(x)
591  {
592  uint32_t n = 0;
593 
594  if(x & 0xFF00) { n += 8; x >>= 8; }
595  if(x & 0xFFF0) { n += 4; x >>= 4; }
596  if(x & 0xFFFC) { n += 2; x >>= 2; }
597  if(x & 0xFFFE) { n += 1; }
598 
599  return n;
600  }
601 
602  return 16;
603  }
604 
605  inline uint32_t GetLastBit(uint32_t x)
606  {
607  if(x)
608  {
609  uint32_t n = 0;
610 
611  if(x & 0xFFFF0000) { n += 16; x >>= 16; }
612  if(x & 0xFFFFFF00) { n += 8; x >>= 8; }
613  if(x & 0xFFFFFFF0) { n += 4; x >>= 4; }
614  if(x & 0xFFFFFFFC) { n += 2; x >>= 2; }
615  if(x & 0xFFFFFFFE) { n += 1; }
616 
617  return n;
618  }
619 
620  return 32;
621  }
622 
623  inline uint32_t GetLastBit(uint64_t x)
624  {
625  if(x)
626  {
627  uint32_t n = 0;
628 
629  if(x & UINT64_C(0xFFFFFFFF00000000)) { n += 32; x >>= 32; }
630  if(x & 0xFFFF0000) { n += 16; x >>= 16; }
631  if(x & 0xFFFFFF00) { n += 8; x >>= 8; }
632  if(x & 0xFFFFFFF0) { n += 4; x >>= 4; }
633  if(x & 0xFFFFFFFC) { n += 2; x >>= 2; }
634  if(x & 0xFFFFFFFE) { n += 1; }
635 
636  return n;
637  }
638 
639  return 64;
640  }
641 
642  #if EASTL_INT128_SUPPORTED
643  inline uint32_t GetLastBit(eastl_uint128_t x)
644  {
645  if(x)
646  {
647  uint32_t n = 0;
648 
649  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.
650  mask <<= 64;
651 
652  if(x & mask) { n += 64; x >>= 64; }
653  if(x & UINT64_C(0xFFFFFFFF00000000)) { n += 32; x >>= 32; }
654  if(x & UINT64_C(0x00000000FFFF0000)) { n += 16; x >>= 16; }
655  if(x & UINT64_C(0x00000000FFFFFF00)) { n += 8; x >>= 8; }
656  if(x & UINT64_C(0x00000000FFFFFFF0)) { n += 4; x >>= 4; }
657  if(x & UINT64_C(0x00000000FFFFFFFC)) { n += 2; x >>= 2; }
658  if(x & UINT64_C(0x00000000FFFFFFFE)) { n += 1; }
659 
660  return n;
661  }
662 
663  return 128;
664  }
665  #endif
666 
667 
668 
669 
671  // BitsetBase
672  //
673  // We tried two forms of array access here:
674  // for(word_type *pWord(mWord), *pWordEnd(mWord + NW); pWord < pWordEnd; ++pWord)
675  // *pWord = ...
676  // and
677  // for(size_t i = 0; i < NW; i++)
678  // mWord[i] = ...
679  //
680  // For our tests (~NW < 16), the latter (using []) access resulted in faster code.
682 
683  template <size_t NW, typename WordType>
684  inline BitsetBase<NW, WordType>::BitsetBase()
685  {
686  reset();
687  }
688 
689 
690  template <size_t NW, typename WordType>
691  inline BitsetBase<NW, WordType>::BitsetBase(uint32_t value)
692  {
693  // This implementation assumes that sizeof(value) <= sizeof(word_type).
694  //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.
695 
696  reset();
697  mWord[0] = static_cast<word_type>(value);
698  }
699 
700 
701  /*
702  template <size_t NW, typename WordType>
703  inline BitsetBase<NW, WordType>::BitsetBase(uint64_t value)
704  {
705  reset();
706 
707  #if(EA_PLATFORM_WORD_SIZE == 4)
708  mWord[0] = static_cast<word_type>(value);
709 
710  EASTL_CT_ASSERT(NW > 2); // We can assume this because we have specializations of BitsetBase for <1> and <2>.
711  //if(NW > 1) // NW is a template constant, but it would be a little messy to take advantage of it's const-ness.
712  mWord[1] = static_cast<word_type>(value >> 32);
713  #else
714  mWord[0] = static_cast<word_type>(value);
715  #endif
716  }
717  */
718 
719 
720  template <size_t NW, typename WordType>
721  inline void BitsetBase<NW, WordType>::operator&=(const this_type& x)
722  {
723  for(size_t i = 0; i < NW; i++)
724  mWord[i] &= x.mWord[i];
725  }
726 
727 
728  template <size_t NW, typename WordType>
729  inline void BitsetBase<NW, WordType>::operator|=(const this_type& x)
730  {
731  for(size_t i = 0; i < NW; i++)
732  mWord[i] |= x.mWord[i];
733  }
734 
735 
736  template <size_t NW, typename WordType>
737  inline void BitsetBase<NW, WordType>::operator^=(const this_type& x)
738  {
739  for(size_t i = 0; i < NW; i++)
740  mWord[i] ^= x.mWord[i];
741  }
742 
743 
744  template <size_t NW, typename WordType>
745  inline void BitsetBase<NW, WordType>::operator<<=(size_type n)
746  {
747  const size_type nWordShift = (size_type)(n >> kBitsPerWordShift);
748 
749  if(nWordShift)
750  {
751  for(int i = (int)(NW - 1); i >= 0; --i)
752  mWord[i] = (nWordShift <= (size_type)i) ? mWord[i - nWordShift] : (word_type)0;
753  }
754 
755  if(n &= kBitsPerWordMask)
756  {
757  for(size_t i = (NW - 1); i > 0; --i)
758  mWord[i] = (word_type)((mWord[i] << n) | (mWord[i - 1] >> (kBitsPerWord - n)));
759  mWord[0] <<= n;
760  }
761 
762  // We let the parent class turn off any upper bits.
763  }
764 
765 
766  template <size_t NW, typename WordType>
767  inline void BitsetBase<NW, WordType>::operator>>=(size_type n)
768  {
769  const size_type nWordShift = (size_type)(n >> kBitsPerWordShift);
770 
771  if(nWordShift)
772  {
773  for(size_t i = 0; i < NW; ++i)
774  mWord[i] = ((nWordShift < (NW - i)) ? mWord[i + nWordShift] : (word_type)0);
775  }
776 
777  if(n &= kBitsPerWordMask)
778  {
779  for(size_t i = 0; i < (NW - 1); ++i)
780  mWord[i] = (word_type)((mWord[i] >> n) | (mWord[i + 1] << (kBitsPerWord - n)));
781  mWord[NW - 1] >>= n;
782  }
783  }
784 
785 
786  template <size_t NW, typename WordType>
787  inline void BitsetBase<NW, WordType>::flip()
788  {
789  for(size_t i = 0; i < NW; i++)
790  mWord[i] = ~mWord[i];
791  // We let the parent class turn off any upper bits.
792  }
793 
794 
795  template <size_t NW, typename WordType>
796  inline void BitsetBase<NW, WordType>::set()
797  {
798  for(size_t i = 0; i < NW; i++)
799  mWord[i] = static_cast<word_type>(~static_cast<word_type>(0));
800  // We let the parent class turn off any upper bits.
801  }
802 
803 
804  template <size_t NW, typename WordType>
805  inline void BitsetBase<NW, WordType>::set(size_type i, bool value)
806  {
807  if(value)
808  mWord[i >> kBitsPerWordShift] |= (static_cast<word_type>(1) << (i & kBitsPerWordMask));
809  else
810  mWord[i >> kBitsPerWordShift] &= ~(static_cast<word_type>(1) << (i & kBitsPerWordMask));
811  }
812 
813 
814  template <size_t NW, typename WordType>
815  inline void BitsetBase<NW, WordType>::reset()
816  {
817  if(NW > 16) // This is a constant expression and should be optimized away.
818  {
819  // This will be fastest if compiler intrinsic function optimizations are enabled.
820  memset(mWord, 0, sizeof(mWord));
821  }
822  else
823  {
824  for(size_t i = 0; i < NW; i++)
825  mWord[i] = 0;
826  }
827  }
828 
829 
830  template <size_t NW, typename WordType>
831  inline bool BitsetBase<NW, WordType>::operator==(const this_type& x) const
832  {
833  for(size_t i = 0; i < NW; i++)
834  {
835  if(mWord[i] != x.mWord[i])
836  return false;
837  }
838  return true;
839  }
840 
841 
842  template <size_t NW, typename WordType>
843  inline bool BitsetBase<NW, WordType>::any() const
844  {
845  for(size_t i = 0; i < NW; i++)
846  {
847  if(mWord[i])
848  return true;
849  }
850  return false;
851  }
852 
853 
854  template <size_t NW, typename WordType>
855  inline typename BitsetBase<NW, WordType>::size_type
856  BitsetBase<NW, WordType>::count() const
857  {
858  size_type n = 0;
859 
860  for(size_t i = 0; i < NW; i++)
861  {
862  #if defined(__GNUC__) && (((__GNUC__ * 100) + __GNUC_MINOR__) >= 304) && !defined(EA_PLATFORM_ANDROID) // GCC 3.4 or later
863  #if(EA_PLATFORM_WORD_SIZE == 4)
864  n += (size_type)__builtin_popcountl(mWord[i]);
865  #else
866  n += (size_type)__builtin_popcountll(mWord[i]);
867  #endif
868  #elif defined(__GNUC__) && (__GNUC__ < 3)
869  n += BitsetCountBits(mWord[i]); // GCC 2.x compiler inexplicably blows up on the code below.
870  #else
871  // todo: use __popcnt16, __popcnt, __popcnt64 for msvc builds
872  // https://msdn.microsoft.com/en-us/library/bb385231(v=vs.140).aspx
873  for(word_type w = mWord[i]; w; w >>= 4)
874  n += EASTL_BITSET_COUNT_STRING[w & 0xF];
875 
876  // Version which seems to run slower in benchmarks:
877  // n += BitsetCountBits(mWord[i]);
878  #endif
879 
880  }
881  return n;
882  }
883 
884 
885  template <size_t NW, typename WordType>
886  inline void BitsetBase<NW, WordType>::from_uint32(uint32_t value)
887  {
888  reset();
889  mWord[0] = static_cast<word_type>(value);
890  }
891 
892 
893  template <size_t NW, typename WordType>
894  inline void BitsetBase<NW, WordType>::from_uint64(uint64_t value)
895  {
896  reset();
897 
898  #if(EA_PLATFORM_WORD_SIZE == 4)
899  mWord[0] = static_cast<word_type>(value);
900 
901  EASTL_CT_ASSERT(NW > 2); // We can assume this because we have specializations of BitsetBase for <1> and <2>.
902  //if(NW > 1) // NW is a template constant, but it would be a little messy to take advantage of it's const-ness.
903  mWord[1] = static_cast<word_type>(value >> 32);
904  #else
905  mWord[0] = static_cast<word_type>(value);
906  #endif
907  }
908 
909 
910  template <size_t NW, typename WordType>
911  inline unsigned long BitsetBase<NW, WordType>::to_ulong() const
912  {
913  #if EASTL_EXCEPTIONS_ENABLED
914  for(size_t i = 1; i < NW; ++i)
915  {
916  if(mWord[i])
917  throw std::overflow_error("BitsetBase::to_ulong");
918  }
919  #endif
920  return (unsigned long)mWord[0]; // Todo: We need to deal with the case whereby sizeof(word_type) < sizeof(unsigned long)
921  }
922 
923 
924  template <size_t NW, typename WordType>
925  inline uint32_t BitsetBase<NW, WordType>::to_uint32() const
926  {
927  #if EASTL_EXCEPTIONS_ENABLED
928  // Verify that high words or bits are not set and thus that to_uint32 doesn't lose information.
929  for(size_t i = 1; i < NW; ++i)
930  {
931  if(mWord[i])
932  throw std::overflow_error("BitsetBase::to_uint32");
933  }
934 
935  #if(EA_PLATFORM_WORD_SIZE > 4) // if we have 64 bit words...
936  if(mWord[0] >> 32)
937  throw std::overflow_error("BitsetBase::to_uint32");
938  #endif
939  #endif
940 
941  return (uint32_t)mWord[0];
942  }
943 
944 
945  template <size_t NW, typename WordType>
946  inline uint64_t BitsetBase<NW, WordType>::to_uint64() const
947  {
948  #if EASTL_EXCEPTIONS_ENABLED
949  // Verify that high words are not set and thus that to_uint64 doesn't lose information.
950 
951  EASTL_CT_ASSERT(NW > 2); // We can assume this because we have specializations of BitsetBase for <1> and <2>.
952  for(size_t i = 2; i < NW; ++i)
953  {
954  if(mWord[i])
955  throw std::overflow_error("BitsetBase::to_uint64");
956  }
957  #endif
958 
959  #if(EA_PLATFORM_WORD_SIZE == 4)
960  EASTL_CT_ASSERT(NW > 2); // We can assume this because we have specializations of BitsetBase for <1> and <2>.
961  return (mWord[1] << 32) | mWord[0];
962  #else
963  return (uint64_t)mWord[0];
964  #endif
965  }
966 
967 
968  template <size_t NW, typename WordType>
969  inline typename BitsetBase<NW, WordType>::word_type&
970  BitsetBase<NW, WordType>::DoGetWord(size_type i)
971  {
972  return mWord[i >> kBitsPerWordShift];
973  }
974 
975 
976  template <size_t NW, typename WordType>
977  inline typename BitsetBase<NW, WordType>::word_type
978  BitsetBase<NW, WordType>::DoGetWord(size_type i) const
979  {
980  return mWord[i >> kBitsPerWordShift];
981  }
982 
983 
984  template <size_t NW, typename WordType>
985  inline typename BitsetBase<NW, WordType>::size_type
986  BitsetBase<NW, WordType>::DoFindFirst() const
987  {
988  for(size_type word_index = 0; word_index < NW; ++word_index)
989  {
990  const size_type fbiw = GetFirstBit(mWord[word_index]);
991 
992  if(fbiw != kBitsPerWord)
993  return (word_index * kBitsPerWord) + fbiw;
994  }
995 
996  return (size_type)NW * kBitsPerWord;
997  }
998 
999 
1000 #if EASTL_DISABLE_BITSET_ARRAYBOUNDS_WARNING
1001 EA_DISABLE_GCC_WARNING(-Warray-bounds)
1002 #endif
1003 
1004  template <size_t NW, typename WordType>
1005  inline typename BitsetBase<NW, WordType>::size_type
1006  BitsetBase<NW, WordType>::DoFindNext(size_type last_find) const
1007  {
1008  // Start looking from the next bit.
1009  ++last_find;
1010 
1011  // Set initial state based on last find.
1012  size_type word_index = static_cast<size_type>(last_find >> kBitsPerWordShift);
1013  size_type bit_index = static_cast<size_type>(last_find & kBitsPerWordMask);
1014 
1015  // To do: There probably is a more elegant way to write looping below.
1016  if(word_index < NW)
1017  {
1018  // Mask off previous bits of the word so our search becomes a "find first".
1019  word_type this_word = mWord[word_index] & (~static_cast<word_type>(0) << bit_index);
1020 
1021  for(;;)
1022  {
1023  const size_type fbiw = GetFirstBit(this_word);
1024 
1025  if(fbiw != kBitsPerWord)
1026  return (word_index * kBitsPerWord) + fbiw;
1027 
1028  if(++word_index < NW)
1029  this_word = mWord[word_index];
1030  else
1031  break;
1032  }
1033  }
1034 
1035  return (size_type)NW * kBitsPerWord;
1036  }
1037 
1038 #if EASTL_DISABLE_BITSET_ARRAYBOUNDS_WARNING
1039 EA_RESTORE_GCC_WARNING()
1040 #endif
1041 
1042 
1043 
1044  template <size_t NW, typename WordType>
1045  inline typename BitsetBase<NW, WordType>::size_type
1046  BitsetBase<NW, WordType>::DoFindLast() const
1047  {
1048  for(size_type word_index = (size_type)NW; word_index > 0; --word_index)
1049  {
1050  const size_type lbiw = GetLastBit(mWord[word_index - 1]);
1051 
1052  if(lbiw != kBitsPerWord)
1053  return ((word_index - 1) * kBitsPerWord) + lbiw;
1054  }
1055 
1056  return (size_type)NW * kBitsPerWord;
1057  }
1058 
1059 
1060  template <size_t NW, typename WordType>
1061  inline typename BitsetBase<NW, WordType>::size_type
1062  BitsetBase<NW, WordType>::DoFindPrev(size_type last_find) const
1063  {
1064  if(last_find > 0)
1065  {
1066  // Set initial state based on last find.
1067  size_type word_index = static_cast<size_type>(last_find >> kBitsPerWordShift);
1068  size_type bit_index = static_cast<size_type>(last_find & kBitsPerWordMask);
1069 
1070  // Mask off subsequent bits of the word so our search becomes a "find last".
1071  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.
1072  word_type this_word = mWord[word_index] & mask;
1073 
1074  for(;;)
1075  {
1076  const size_type lbiw = GetLastBit(this_word);
1077 
1078  if(lbiw != kBitsPerWord)
1079  return (word_index * kBitsPerWord) + lbiw;
1080 
1081  if(word_index > 0)
1082  this_word = mWord[--word_index];
1083  else
1084  break;
1085  }
1086  }
1087 
1088  return (size_type)NW * kBitsPerWord;
1089  }
1090 
1091 
1092 
1094  // BitsetBase<1, WordType>
1096 
1097  template <typename WordType>
1098  inline BitsetBase<1, WordType>::BitsetBase()
1099  {
1100  mWord[0] = 0;
1101  }
1102 
1103 
1104  template <typename WordType>
1105  inline BitsetBase<1, WordType>::BitsetBase(uint32_t value)
1106  {
1107  // This implementation assumes that sizeof(value) <= sizeof(word_type).
1108  //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.
1109 
1110  mWord[0] = static_cast<word_type>(value);
1111  }
1112 
1113 
1114  /*
1115  template <typename WordType>
1116  inline BitsetBase<1, WordType>::BitsetBase(uint64_t value)
1117  {
1118  #if(EA_PLATFORM_WORD_SIZE == 4)
1119  EASTL_ASSERT(value <= 0xffffffff);
1120  mWord[0] = static_cast<word_type>(value); // This potentially loses data, but that's what the user is requesting.
1121  #else
1122  mWord[0] = static_cast<word_type>(value);
1123  #endif
1124  }
1125  */
1126 
1127 
1128  template <typename WordType>
1129  inline void BitsetBase<1, WordType>::operator&=(const this_type& x)
1130  {
1131  mWord[0] &= x.mWord[0];
1132  }
1133 
1134 
1135  template <typename WordType>
1136  inline void BitsetBase<1, WordType>::operator|=(const this_type& x)
1137  {
1138  mWord[0] |= x.mWord[0];
1139  }
1140 
1141 
1142  template <typename WordType>
1143  inline void BitsetBase<1, WordType>::operator^=(const this_type& x)
1144  {
1145  mWord[0] ^= x.mWord[0];
1146  }
1147 
1148 
1149  template <typename WordType>
1150  inline void BitsetBase<1, WordType>::operator<<=(size_type n)
1151  {
1152  mWord[0] <<= n;
1153  // We let the parent class turn off any upper bits.
1154  }
1155 
1156 
1157  template <typename WordType>
1158  inline void BitsetBase<1, WordType>::operator>>=(size_type n)
1159  {
1160  mWord[0] >>= n;
1161  }
1162 
1163 
1164  template <typename WordType>
1165  inline void BitsetBase<1, WordType>::flip()
1166  {
1167  mWord[0] = ~mWord[0];
1168  // We let the parent class turn off any upper bits.
1169  }
1170 
1171 
1172  template <typename WordType>
1173  inline void BitsetBase<1, WordType>::set()
1174  {
1175  mWord[0] = static_cast<word_type>(~static_cast<word_type>(0));
1176  // We let the parent class turn off any upper bits.
1177  }
1178 
1179 
1180  template <typename WordType>
1181  inline void BitsetBase<1, WordType>::set(size_type i, bool value)
1182  {
1183  if(value)
1184  mWord[0] |= (static_cast<word_type>(1) << i);
1185  else
1186  mWord[0] &= ~(static_cast<word_type>(1) << i);
1187  }
1188 
1189 
1190  template <typename WordType>
1191  inline void BitsetBase<1, WordType>::reset()
1192  {
1193  mWord[0] = 0;
1194  }
1195 
1196 
1197  template <typename WordType>
1198  inline bool BitsetBase<1, WordType>::operator==(const this_type& x) const
1199  {
1200  return mWord[0] == x.mWord[0];
1201  }
1202 
1203 
1204  template <typename WordType>
1205  inline bool BitsetBase<1, WordType>::any() const
1206  {
1207  return mWord[0] != 0;
1208  }
1209 
1210 
1211  template <typename WordType>
1212  inline typename BitsetBase<1, WordType>::size_type
1213  BitsetBase<1, WordType>::count() const
1214  {
1215  #if defined(__GNUC__) && (((__GNUC__ * 100) + __GNUC_MINOR__) >= 304) && !defined(EA_PLATFORM_ANDROID) // GCC 3.4 or later
1216  #if(EA_PLATFORM_WORD_SIZE == 4)
1217  return (size_type)__builtin_popcountl(mWord[0]);
1218  #else
1219  return (size_type)__builtin_popcountll(mWord[0]);
1220  #endif
1221  #elif defined(__GNUC__) && (__GNUC__ < 3)
1222  return BitsetCountBits(mWord[0]); // GCC 2.x compiler inexplicably blows up on the code below.
1223  #else
1224  size_type n = 0;
1225  for(word_type w = mWord[0]; w; w >>= 4)
1226  n += EASTL_BITSET_COUNT_STRING[w & 0xF];
1227  return n;
1228  #endif
1229  }
1230 
1231 
1232  template <typename WordType>
1233  inline void BitsetBase<1, WordType>::from_uint32(uint32_t value)
1234  {
1235  mWord[0] = static_cast<word_type>(value);
1236  }
1237 
1238 
1239  template <typename WordType>
1240  inline void BitsetBase<1, WordType>::from_uint64(uint64_t value)
1241  {
1242  #if(EA_PLATFORM_WORD_SIZE == 4)
1243  EASTL_ASSERT(value <= 0xffffffff);
1244  mWord[0] = static_cast<word_type>(value); // This potentially loses data, but that's what the user is requesting.
1245  #else
1246  mWord[0] = static_cast<word_type>(value);
1247  #endif
1248  }
1249 
1250 
1251  template <typename WordType>
1252  inline unsigned long BitsetBase<1, WordType>::to_ulong() const
1253  {
1254  #if EASTL_EXCEPTIONS_ENABLED
1255  #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.
1256  // Verify that high bits are not set and thus that to_ulong doesn't lose information.
1257  if(mWord[0] >> 32)
1258  throw std::overflow_error("BitsetBase::to_ulong");
1259  #endif
1260  #endif
1261 
1262  return static_cast<unsigned long>(mWord[0]);
1263  }
1264 
1265 
1266  template <typename WordType>
1267  inline uint32_t BitsetBase<1, WordType>::to_uint32() const
1268  {
1269  #if EASTL_EXCEPTIONS_ENABLED
1270  #if(EA_PLATFORM_WORD_SIZE > 4) // If we are using 64 bit words...
1271  // Verify that high bits are not set and thus that to_uint32 doesn't lose information.
1272  if(mWord[0] >> 32)
1273  throw std::overflow_error("BitsetBase::to_uint32");
1274  #endif
1275  #endif
1276 
1277  return static_cast<uint32_t>(mWord[0]);
1278  }
1279 
1280 
1281  template <typename WordType>
1282  inline uint64_t BitsetBase<1, WordType>::to_uint64() const
1283  {
1284  // This implementation is the same regardless of the word size, and there is no possibility of overflow_error.
1285  return static_cast<uint64_t>(mWord[0]);
1286  }
1287 
1288 
1289  template <typename WordType>
1290  inline typename BitsetBase<1, WordType>::word_type&
1291  BitsetBase<1, WordType>::DoGetWord(size_type)
1292  {
1293  return mWord[0];
1294  }
1295 
1296 
1297  template <typename WordType>
1298  inline typename BitsetBase<1, WordType>::word_type
1299  BitsetBase<1, WordType>::DoGetWord(size_type) const
1300  {
1301  return mWord[0];
1302  }
1303 
1304 
1305  template <typename WordType>
1306  inline typename BitsetBase<1, WordType>::size_type
1307  BitsetBase<1, WordType>::DoFindFirst() const
1308  {
1309  return GetFirstBit(mWord[0]);
1310  }
1311 
1312 
1313  template <typename WordType>
1314  inline typename BitsetBase<1, WordType>::size_type
1315  BitsetBase<1, WordType>::DoFindNext(size_type last_find) const
1316  {
1317  if(++last_find < kBitsPerWord)
1318  {
1319  // Mask off previous bits of word so our search becomes a "find first".
1320  const word_type this_word = mWord[0] & ((~static_cast<word_type>(0)) << last_find);
1321 
1322  return GetFirstBit(this_word);
1323  }
1324 
1325  return kBitsPerWord;
1326  }
1327 
1328 
1329  template <typename WordType>
1330  inline typename BitsetBase<1, WordType>::size_type
1331  BitsetBase<1, WordType>::DoFindLast() const
1332  {
1333  return GetLastBit(mWord[0]);
1334  }
1335 
1336 
1337  template <typename WordType>
1338  inline typename BitsetBase<1, WordType>::size_type
1339  BitsetBase<1, WordType>::DoFindPrev(size_type last_find) const
1340  {
1341  if(last_find > 0)
1342  {
1343  // Mask off previous bits of word so our search becomes a "find first".
1344  const word_type this_word = mWord[0] & ((~static_cast<word_type>(0)) >> (kBitsPerWord - last_find));
1345 
1346  return GetLastBit(this_word);
1347  }
1348 
1349  return kBitsPerWord;
1350  }
1351 
1352 
1353 
1354 
1356  // BitsetBase<2, WordType>
1358 
1359  template <typename WordType>
1360  inline BitsetBase<2, WordType>::BitsetBase()
1361  {
1362  mWord[0] = 0;
1363  mWord[1] = 0;
1364  }
1365 
1366 
1367  template <typename WordType>
1368  inline BitsetBase<2, WordType>::BitsetBase(uint32_t value)
1369  {
1370  // This implementation assumes that sizeof(value) <= sizeof(word_type).
1371  //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.
1372 
1373  mWord[0] = static_cast<word_type>(value);
1374  mWord[1] = 0;
1375  }
1376 
1377 
1378  /*
1379  template <typename WordType>
1380  inline BitsetBase<2, WordType>::BitsetBase(uint64_t value)
1381  {
1382  #if(EA_PLATFORM_WORD_SIZE == 4)
1383  mWord[0] = static_cast<word_type>(value);
1384  mWord[1] = static_cast<word_type>(value >> 32);
1385  #else
1386  mWord[0] = static_cast<word_type>(value);
1387  mWord[1] = 0;
1388  #endif
1389  }
1390  */
1391 
1392 
1393  template <typename WordType>
1394  inline void BitsetBase<2, WordType>::operator&=(const this_type& x)
1395  {
1396  mWord[0] &= x.mWord[0];
1397  mWord[1] &= x.mWord[1];
1398  }
1399 
1400 
1401  template <typename WordType>
1402  inline void BitsetBase<2, WordType>::operator|=(const this_type& x)
1403  {
1404  mWord[0] |= x.mWord[0];
1405  mWord[1] |= x.mWord[1];
1406  }
1407 
1408 
1409  template <typename WordType>
1410  inline void BitsetBase<2, WordType>::operator^=(const this_type& x)
1411  {
1412  mWord[0] ^= x.mWord[0];
1413  mWord[1] ^= x.mWord[1];
1414  }
1415 
1416 
1417  template <typename WordType>
1418  inline void BitsetBase<2, WordType>::operator<<=(size_type n)
1419  {
1420  if(n) // to avoid a shift by kBitsPerWord, which is undefined
1421  {
1422  if(EASTL_UNLIKELY(n >= kBitsPerWord)) // parent expected to handle high bits and n >= 64
1423  {
1424  mWord[1] = mWord[0];
1425  mWord[0] = 0;
1426  n -= kBitsPerWord;
1427  }
1428 
1429  mWord[1] = (mWord[1] << n) | (mWord[0] >> (kBitsPerWord - n)); // Intentionally use | instead of +.
1430  mWord[0] <<= n;
1431  // We let the parent class turn off any upper bits.
1432  }
1433  }
1434 
1435 
1436  template <typename WordType>
1437  inline void BitsetBase<2, WordType>::operator>>=(size_type n)
1438  {
1439  if(n) // to avoid a shift by kBitsPerWord, which is undefined
1440  {
1441  if(EASTL_UNLIKELY(n >= kBitsPerWord)) // parent expected to handle n >= 64
1442  {
1443  mWord[0] = mWord[1];
1444  mWord[1] = 0;
1445  n -= kBitsPerWord;
1446  }
1447 
1448  mWord[0] = (mWord[0] >> n) | (mWord[1] << (kBitsPerWord - n)); // Intentionally use | instead of +.
1449  mWord[1] >>= n;
1450  }
1451  }
1452 
1453 
1454  template <typename WordType>
1455  inline void BitsetBase<2, WordType>::flip()
1456  {
1457  mWord[0] = ~mWord[0];
1458  mWord[1] = ~mWord[1];
1459  // We let the parent class turn off any upper bits.
1460  }
1461 
1462 
1463  template <typename WordType>
1464  inline void BitsetBase<2, WordType>::set()
1465  {
1466  mWord[0] = ~static_cast<word_type>(0);
1467  mWord[1] = ~static_cast<word_type>(0);
1468  // We let the parent class turn off any upper bits.
1469  }
1470 
1471 
1472  template <typename WordType>
1473  inline void BitsetBase<2, WordType>::set(size_type i, bool value)
1474  {
1475  if(value)
1476  mWord[i >> kBitsPerWordShift] |= (static_cast<word_type>(1) << (i & kBitsPerWordMask));
1477  else
1478  mWord[i >> kBitsPerWordShift] &= ~(static_cast<word_type>(1) << (i & kBitsPerWordMask));
1479  }
1480 
1481 
1482  template <typename WordType>
1483  inline void BitsetBase<2, WordType>::reset()
1484  {
1485  mWord[0] = 0;
1486  mWord[1] = 0;
1487  }
1488 
1489 
1490  template <typename WordType>
1491  inline bool BitsetBase<2, WordType>::operator==(const this_type& x) const
1492  {
1493  return (mWord[0] == x.mWord[0]) && (mWord[1] == x.mWord[1]);
1494  }
1495 
1496 
1497  template <typename WordType>
1498  inline bool BitsetBase<2, WordType>::any() const
1499  {
1500  // Or with two branches: { return (mWord[0] != 0) || (mWord[1] != 0); }
1501  return (mWord[0] | mWord[1]) != 0;
1502  }
1503 
1504  template <typename WordType>
1505  inline typename BitsetBase<2, WordType>::size_type
1506  BitsetBase<2, WordType>::count() const
1507  {
1508  #if (defined(__GNUC__) && (((__GNUC__ * 100) + __GNUC_MINOR__) >= 304)) || defined(__clang__) // GCC 3.4 or later
1509  #if(EA_PLATFORM_WORD_SIZE == 4)
1510  return (size_type)__builtin_popcountl(mWord[0]) + (size_type)__builtin_popcountl(mWord[1]);
1511  #else
1512  return (size_type)__builtin_popcountll(mWord[0]) + (size_type)__builtin_popcountll(mWord[1]);
1513  #endif
1514 
1515  #else
1516  return BitsetCountBits(mWord[0]) + BitsetCountBits(mWord[1]);
1517  #endif
1518  }
1519 
1520 
1521  template <typename WordType>
1522  inline void BitsetBase<2, WordType>::from_uint32(uint32_t value)
1523  {
1524  mWord[0] = static_cast<word_type>(value);
1525  mWord[1] = 0;
1526  }
1527 
1528 
1529  template <typename WordType>
1530  inline void BitsetBase<2, WordType>::from_uint64(uint64_t value)
1531  {
1532  #if(EA_PLATFORM_WORD_SIZE == 4)
1533  mWord[0] = static_cast<word_type>(value);
1534  mWord[1] = static_cast<word_type>(value >> 32);
1535  #else
1536  mWord[0] = static_cast<word_type>(value);
1537  mWord[1] = 0;
1538  #endif
1539  }
1540 
1541 
1542  template <typename WordType>
1543  inline unsigned long BitsetBase<2, WordType>::to_ulong() const
1544  {
1545  #if EASTL_EXCEPTIONS_ENABLED
1546  if(mWord[1])
1547  throw std::overflow_error("BitsetBase::to_ulong");
1548  #endif
1549  return (unsigned long)mWord[0]; // Todo: We need to deal with the case whereby sizeof(word_type) < sizeof(unsigned long)
1550  }
1551 
1552 
1553  template <typename WordType>
1554  inline uint32_t BitsetBase<2, WordType>::to_uint32() const
1555  {
1556  #if EASTL_EXCEPTIONS_ENABLED
1557  // Verify that high words or bits are not set and thus that to_uint32 doesn't lose information.
1558 
1559  #if(EA_PLATFORM_WORD_SIZE == 4)
1560  if(mWord[1])
1561  throw std::overflow_error("BitsetBase::to_uint32");
1562  #else
1563  if(mWord[1] || (mWord[0] >> 32))
1564  throw std::overflow_error("BitsetBase::to_uint32");
1565  #endif
1566  #endif
1567 
1568  return (uint32_t)mWord[0];
1569  }
1570 
1571 
1572  template <typename WordType>
1573  inline uint64_t BitsetBase<2, WordType>::to_uint64() const
1574  {
1575  #if(EA_PLATFORM_WORD_SIZE == 4)
1576  // There can't possibly be an overflow_error here.
1577 
1578  return ((uint64_t)mWord[1] << 32) | mWord[0];
1579  #else
1580  #if EASTL_EXCEPTIONS_ENABLED
1581  if(mWord[1])
1582  throw std::overflow_error("BitsetBase::to_uint64");
1583  #endif
1584 
1585  return (uint64_t)mWord[0];
1586  #endif
1587  }
1588 
1589 
1590  template <typename WordType>
1591  inline typename BitsetBase<2, WordType>::word_type&
1592  BitsetBase<2, WordType>::DoGetWord(size_type i)
1593  {
1594  return mWord[i >> kBitsPerWordShift];
1595  }
1596 
1597 
1598  template <typename WordType>
1599  inline typename BitsetBase<2, WordType>::word_type
1600  BitsetBase<2, WordType>::DoGetWord(size_type i) const
1601  {
1602  return mWord[i >> kBitsPerWordShift];
1603  }
1604 
1605 
1606  template <typename WordType>
1607  inline typename BitsetBase<2, WordType>::size_type
1608  BitsetBase<2, WordType>::DoFindFirst() const
1609  {
1610  size_type fbiw = GetFirstBit(mWord[0]);
1611 
1612  if(fbiw != kBitsPerWord)
1613  return fbiw;
1614 
1615  fbiw = GetFirstBit(mWord[1]);
1616 
1617  if(fbiw != kBitsPerWord)
1618  return kBitsPerWord + fbiw;
1619 
1620  return 2 * kBitsPerWord;
1621  }
1622 
1623 
1624  template <typename WordType>
1625  inline typename BitsetBase<2, WordType>::size_type
1626  BitsetBase<2, WordType>::DoFindNext(size_type last_find) const
1627  {
1628  // If the last find was in the first word, we must check it and then possibly the second.
1629  if(++last_find < (size_type)kBitsPerWord)
1630  {
1631  // Mask off previous bits of word so our search becomes a "find first".
1632  word_type this_word = mWord[0] & ((~static_cast<word_type>(0)) << last_find);
1633 
1634  // Step through words.
1635  size_type fbiw = GetFirstBit(this_word);
1636 
1637  if(fbiw != kBitsPerWord)
1638  return fbiw;
1639 
1640  fbiw = GetFirstBit(mWord[1]);
1641 
1642  if(fbiw != kBitsPerWord)
1643  return kBitsPerWord + fbiw;
1644  }
1645  else if(last_find < (size_type)(2 * kBitsPerWord))
1646  {
1647  // The last find was in the second word, remove the bit count of the first word from the find.
1648  last_find -= kBitsPerWord;
1649 
1650  // Mask off previous bits of word so our search becomes a "find first".
1651  word_type this_word = mWord[1] & ((~static_cast<word_type>(0)) << last_find);
1652 
1653  const size_type fbiw = GetFirstBit(this_word);
1654 
1655  if(fbiw != kBitsPerWord)
1656  return kBitsPerWord + fbiw;
1657  }
1658 
1659  return 2 * kBitsPerWord;
1660  }
1661 
1662 
1663  template <typename WordType>
1664  inline typename BitsetBase<2, WordType>::size_type
1665  BitsetBase<2, WordType>::DoFindLast() const
1666  {
1667  size_type lbiw = GetLastBit(mWord[1]);
1668 
1669  if(lbiw != kBitsPerWord)
1670  return kBitsPerWord + lbiw;
1671 
1672  lbiw = GetLastBit(mWord[0]);
1673 
1674  if(lbiw != kBitsPerWord)
1675  return lbiw;
1676 
1677  return 2 * kBitsPerWord;
1678  }
1679 
1680 
1681  template <typename WordType>
1682  inline typename BitsetBase<2, WordType>::size_type
1683  BitsetBase<2, WordType>::DoFindPrev(size_type last_find) const
1684  {
1685  // If the last find was in the second word, we must check it and then possibly the first.
1686  if(last_find > (size_type)kBitsPerWord)
1687  {
1688  // This has the same effect as last_find %= kBitsPerWord in our case.
1689  last_find -= kBitsPerWord;
1690 
1691  // Mask off previous bits of word so our search becomes a "find first".
1692  word_type this_word = mWord[1] & ((~static_cast<word_type>(0)) >> (kBitsPerWord - last_find));
1693 
1694  // Step through words.
1695  size_type lbiw = GetLastBit(this_word);
1696 
1697  if(lbiw != kBitsPerWord)
1698  return kBitsPerWord + lbiw;
1699 
1700  lbiw = GetLastBit(mWord[0]);
1701 
1702  if(lbiw != kBitsPerWord)
1703  return lbiw;
1704  }
1705  else if(last_find != 0)
1706  {
1707  // Mask off previous bits of word so our search becomes a "find first".
1708  word_type this_word = mWord[0] & ((~static_cast<word_type>(0)) >> (kBitsPerWord - last_find));
1709 
1710  const size_type lbiw = GetLastBit(this_word);
1711 
1712  if(lbiw != kBitsPerWord)
1713  return lbiw;
1714  }
1715 
1716  return 2 * kBitsPerWord;
1717  }
1718 
1719 
1720 
1722  // bitset::reference
1724 
1725  template <size_t N, typename WordType>
1726  inline bitset<N, WordType>::reference::reference(const bitset& x, size_type i)
1727  : mpBitWord(&const_cast<bitset&>(x).DoGetWord(i)),
1728  mnBitIndex(i & kBitsPerWordMask)
1729  { // We have an issue here because the above is casting away the const-ness of the source bitset.
1730  // Empty
1731  }
1732 
1733 
1734  template <size_t N, typename WordType>
1735  inline typename bitset<N, WordType>::reference&
1736  bitset<N, WordType>::reference::operator=(bool value)
1737  {
1738  if(value)
1739  *mpBitWord |= (static_cast<word_type>(1) << (mnBitIndex & kBitsPerWordMask));
1740  else
1741  *mpBitWord &= ~(static_cast<word_type>(1) << (mnBitIndex & kBitsPerWordMask));
1742  return *this;
1743  }
1744 
1745 
1746  template <size_t N, typename WordType>
1747  inline typename bitset<N, WordType>::reference&
1748  bitset<N, WordType>::reference::operator=(const reference& x)
1749  {
1750  if(*x.mpBitWord & (static_cast<word_type>(1) << (x.mnBitIndex & kBitsPerWordMask)))
1751  *mpBitWord |= (static_cast<word_type>(1) << (mnBitIndex & kBitsPerWordMask));
1752  else
1753  *mpBitWord &= ~(static_cast<word_type>(1) << (mnBitIndex & kBitsPerWordMask));
1754  return *this;
1755  }
1756 
1757 
1758  template <size_t N, typename WordType>
1759  inline bool bitset<N, WordType>::reference::operator~() const
1760  {
1761  return (*mpBitWord & (static_cast<word_type>(1) << (mnBitIndex & kBitsPerWordMask))) == 0;
1762  }
1763 
1764 
1765  //Defined inline in the class because Metrowerks fails to be able to compile it here.
1766  //template <size_t N, typename WordType>
1767  //inline bitset<N, WordType>::reference::operator bool() const
1768  //{
1769  // return (*mpBitWord & (static_cast<word_type>(1) << (mnBitIndex & kBitsPerWordMask))) != 0;
1770  //}
1771 
1772 
1773  template <size_t N, typename WordType>
1774  inline typename bitset<N, WordType>::reference&
1775  bitset<N, WordType>::reference::flip()
1776  {
1777  *mpBitWord ^= static_cast<word_type>(1) << (mnBitIndex & kBitsPerWordMask);
1778  return *this;
1779  }
1780 
1781 
1782 
1783 
1785  // bitset
1787 
1788  template <size_t N, typename WordType>
1789  inline bitset<N, WordType>::bitset()
1790  : base_type()
1791  {
1792  // Empty. The base class will set all bits to zero.
1793  }
1794 
1795  EA_DISABLE_VC_WARNING(6313)
1796  template <size_t N, typename WordType>
1797  inline bitset<N, WordType>::bitset(uint32_t value)
1798  : base_type(value)
1799  {
1800  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.
1801  mWord[kWordCount - 1] &= ~(static_cast<word_type>(~static_cast<word_type>(0)) << (N & kBitsPerWordMask)); // This clears any high unused bits.
1802  }
1803  EA_RESTORE_VC_WARNING()
1804 
1805  /*
1806  template <size_t N, typename WordType>
1807  inline bitset<N, WordType>::bitset(uint64_t value)
1808  : base_type(value)
1809  {
1810  if((N & kBitsPerWordMask) || (N == 0)) // If there are any high bits to clear...
1811  mWord[kWordCount - 1] &= ~(~static_cast<word_type>(0) << (N & kBitsPerWordMask)); // This clears any high unused bits.
1812  }
1813  */
1814 
1815 
1816  template <size_t N, typename WordType>
1817  inline typename bitset<N, WordType>::this_type&
1818  bitset<N, WordType>::operator&=(const this_type& x)
1819  {
1820  base_type::operator&=(x);
1821  return *this;
1822  }
1823 
1824 
1825  template <size_t N, typename WordType>
1826  inline typename bitset<N, WordType>::this_type&
1827  bitset<N, WordType>::operator|=(const this_type& x)
1828  {
1829  base_type::operator|=(x);
1830  return *this;
1831  }
1832 
1833 
1834  template <size_t N, typename WordType>
1835  inline typename bitset<N, WordType>::this_type&
1836  bitset<N, WordType>::operator^=(const this_type& x)
1837  {
1838  base_type::operator^=(x);
1839  return *this;
1840  }
1841 
1842 
1843  template <size_t N, typename WordType>
1844  inline typename bitset<N, WordType>::this_type&
1845  bitset<N, WordType>::operator<<=(size_type n)
1846  {
1847  if(EASTL_LIKELY((intptr_t)n < (intptr_t)N))
1848  {
1849  EA_DISABLE_VC_WARNING(6313)
1850  base_type::operator<<=(n);
1851  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.
1852  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.
1853  EA_RESTORE_VC_WARNING()
1854  }
1855  else
1856  base_type::reset();
1857  return *this;
1858  }
1859 
1860 
1861  template <size_t N, typename WordType>
1862  inline typename bitset<N, WordType>::this_type&
1863  bitset<N, WordType>::operator>>=(size_type n)
1864  {
1865  if(EASTL_LIKELY(n < N))
1866  base_type::operator>>=(n);
1867  else
1868  base_type::reset();
1869  return *this;
1870  }
1871 
1872 
1873  template <size_t N, typename WordType>
1874  inline typename bitset<N, WordType>::this_type&
1875  bitset<N, WordType>::set()
1876  {
1877  base_type::set(); // This sets all bits.
1878  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.
1879  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.
1880  return *this;
1881  }
1882 
1883 
1884  template <size_t N, typename WordType>
1885  inline typename bitset<N, WordType>::this_type&
1886  bitset<N, WordType>::set(size_type i, bool value)
1887  {
1888  if(i < N)
1889  base_type::set(i, value);
1890  else
1891  {
1892  #if EASTL_ASSERT_ENABLED
1893  if(EASTL_UNLIKELY(!(i < N)))
1894  EASTL_FAIL_MSG("bitset::set -- out of range");
1895  #endif
1896 
1897  #if EASTL_EXCEPTIONS_ENABLED
1898  throw std::out_of_range("bitset::set");
1899  #endif
1900  }
1901 
1902  return *this;
1903  }
1904 
1905 
1906  template <size_t N, typename WordType>
1907  inline typename bitset<N, WordType>::this_type&
1908  bitset<N, WordType>::reset()
1909  {
1910  base_type::reset();
1911  return *this;
1912  }
1913 
1914 
1915  template <size_t N, typename WordType>
1916  inline typename bitset<N, WordType>::this_type&
1917  bitset<N, WordType>::reset(size_type i)
1918  {
1919  if(EASTL_LIKELY(i < N))
1920  DoGetWord(i) &= ~(static_cast<word_type>(1) << (i & kBitsPerWordMask));
1921  else
1922  {
1923  #if EASTL_ASSERT_ENABLED
1924  if(EASTL_UNLIKELY(!(i < N)))
1925  EASTL_FAIL_MSG("bitset::reset -- out of range");
1926  #endif
1927 
1928  #if EASTL_EXCEPTIONS_ENABLED
1929  throw std::out_of_range("bitset::reset");
1930  #endif
1931  }
1932 
1933  return *this;
1934  }
1935 
1936 
1937  template <size_t N, typename WordType>
1938  inline typename bitset<N, WordType>::this_type&
1939  bitset<N, WordType>::flip()
1940  {
1941  EA_DISABLE_VC_WARNING(6313)
1942  base_type::flip();
1943  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.
1944  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.
1945  return *this;
1946  EA_RESTORE_VC_WARNING()
1947  }
1948 
1949 
1950  template <size_t N, typename WordType>
1951  inline typename bitset<N, WordType>::this_type&
1952  bitset<N, WordType>::flip(size_type i)
1953  {
1954  if(EASTL_LIKELY(i < N))
1955  DoGetWord(i) ^= (static_cast<word_type>(1) << (i & kBitsPerWordMask));
1956  else
1957  {
1958  #if EASTL_ASSERT_ENABLED
1959  if(EASTL_UNLIKELY(!(i < N)))
1960  EASTL_FAIL_MSG("bitset::flip -- out of range");
1961  #endif
1962 
1963  #if EASTL_EXCEPTIONS_ENABLED
1964  throw std::out_of_range("bitset::flip");
1965  #endif
1966  }
1967  return *this;
1968  }
1969 
1970 
1971  template <size_t N, typename WordType>
1972  inline typename bitset<N, WordType>::this_type
1973  bitset<N, WordType>::operator~() const
1974  {
1975  return this_type(*this).flip();
1976  }
1977 
1978 
1979  template <size_t N, typename WordType>
1980  inline typename bitset<N, WordType>::reference
1981  bitset<N, WordType>::operator[](size_type i)
1982  {
1983  #if EASTL_ASSERT_ENABLED
1984  if(EASTL_UNLIKELY(!(i < N)))
1985  EASTL_FAIL_MSG("bitset::operator[] -- out of range");
1986  #endif
1987 
1988  return reference(*this, i);
1989  }
1990 
1991 
1992  template <size_t N, typename WordType>
1993  inline bool bitset<N, WordType>::operator[](size_type i) const
1994  {
1995  #if EASTL_ASSERT_ENABLED
1996  if(EASTL_UNLIKELY(!(i < N)))
1997  EASTL_FAIL_MSG("bitset::operator[] -- out of range");
1998  #endif
1999 
2000  return (DoGetWord(i) & (static_cast<word_type>(1) << (i & kBitsPerWordMask))) != 0;
2001  }
2002 
2003 
2004  template <size_t N, typename WordType>
2005  inline const typename bitset<N, WordType>::word_type* bitset<N, WordType>::data() const
2006  {
2007  return base_type::mWord;
2008  }
2009 
2010 
2011  template <size_t N, typename WordType>
2012  inline typename bitset<N, WordType>::word_type* bitset<N, WordType>::data()
2013  {
2014  return base_type::mWord;
2015  }
2016 
2017 
2018  template <size_t N, typename WordType>
2019  inline void bitset<N, WordType>::from_uint32(uint32_t value)
2020  {
2021  base_type::from_uint32(value);
2022 
2023  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.
2024  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.
2025  }
2026 
2027 
2028  template <size_t N, typename WordType>
2029  inline void bitset<N, WordType>::from_uint64(uint64_t value)
2030  {
2031  base_type::from_uint64(value);
2032 
2033  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.
2034  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.
2035  }
2036 
2037 
2038  // template <size_t N, typename WordType>
2039  // inline unsigned long bitset<N, WordType>::to_ulong() const
2040  // {
2041  // return base_type::to_ulong();
2042  // }
2043 
2044 
2045  // template <size_t N, typename WordType>
2046  // inline uint32_t bitset<N, WordType>::to_uint32() const
2047  // {
2048  // return base_type::to_uint32();
2049  // }
2050 
2051 
2052  // template <size_t N, typename WordType>
2053  // inline uint64_t bitset<N, WordType>::to_uint64() const
2054  // {
2055  // return base_type::to_uint64();
2056  // }
2057 
2058 
2059  // template <size_t N, typename WordType>
2060  // inline typename bitset<N, WordType>::size_type
2061  // bitset<N, WordType>::count() const
2062  // {
2063  // return base_type::count();
2064  // }
2065 
2066 
2067  template <size_t N, typename WordType>
2068  inline typename bitset<N, WordType>::size_type
2069  bitset<N, WordType>::size() const
2070  {
2071  return (size_type)N;
2072  }
2073 
2074 
2075  template <size_t N, typename WordType>
2076  inline bool bitset<N, WordType>::operator==(const this_type& x) const
2077  {
2078  return base_type::operator==(x);
2079  }
2080 
2081 
2082  template <size_t N, typename WordType>
2083  inline bool bitset<N, WordType>::operator!=(const this_type& x) const
2084  {
2085  return !base_type::operator==(x);
2086  }
2087 
2088 
2089  template <size_t N, typename WordType>
2090  inline bool bitset<N, WordType>::test(size_type i) const
2091  {
2092  if(EASTL_UNLIKELY(i < N))
2093  return (DoGetWord(i) & (static_cast<word_type>(1) << (i & kBitsPerWordMask))) != 0;
2094 
2095  #if EASTL_ASSERT_ENABLED
2096  EASTL_FAIL_MSG("bitset::test -- out of range");
2097  #endif
2098 
2099  #if EASTL_EXCEPTIONS_ENABLED
2100  throw std::out_of_range("bitset::test");
2101  #else
2102  return false;
2103  #endif
2104  }
2105 
2106 
2107  // template <size_t N, typename WordType>
2108  // inline bool bitset<N, WordType>::any() const
2109  // {
2110  // return base_type::any();
2111  // }
2112 
2113 
2114  template <size_t N, typename WordType>
2115  inline bool bitset<N, WordType>::all() const
2116  {
2117  return count() == size();
2118  }
2119 
2120 
2121  template <size_t N, typename WordType>
2122  inline bool bitset<N, WordType>::none() const
2123  {
2124  return !base_type::any();
2125  }
2126 
2127 
2128  template <size_t N, typename WordType>
2129  inline typename bitset<N, WordType>::this_type
2130  bitset<N, WordType>::operator<<(size_type n) const
2131  {
2132  return this_type(*this).operator<<=(n);
2133  }
2134 
2135 
2136  template <size_t N, typename WordType>
2137  inline typename bitset<N, WordType>::this_type
2138  bitset<N, WordType>::operator>>(size_type n) const
2139  {
2140  return this_type(*this).operator>>=(n);
2141  }
2142 
2143 
2144  template <size_t N, typename WordType>
2145  inline typename bitset<N, WordType>::size_type
2146  bitset<N, WordType>::find_first() const
2147  {
2148  const size_type i = base_type::DoFindFirst();
2149 
2150  if(i < kSize)
2151  return i;
2152  // Else i could be the base type bit count, so we clamp it to our size.
2153 
2154  return kSize;
2155  }
2156 
2157 
2158  template <size_t N, typename WordType>
2159  inline typename bitset<N, WordType>::size_type
2160  bitset<N, WordType>::find_next(size_type last_find) const
2161  {
2162  const size_type i = base_type::DoFindNext(last_find);
2163 
2164  if(i < kSize)
2165  return i;
2166  // Else i could be the base type bit count, so we clamp it to our size.
2167 
2168  return kSize;
2169  }
2170 
2171 
2172  template <size_t N, typename WordType>
2173  inline typename bitset<N, WordType>::size_type
2174  bitset<N, WordType>::find_last() const
2175  {
2176  const size_type i = base_type::DoFindLast();
2177 
2178  if(i < kSize)
2179  return i;
2180  // Else i could be the base type bit count, so we clamp it to our size.
2181 
2182  return kSize;
2183  }
2184 
2185 
2186  template <size_t N, typename WordType>
2187  inline typename bitset<N, WordType>::size_type
2188  bitset<N, WordType>::find_prev(size_type last_find) const
2189  {
2190  const size_type i = base_type::DoFindPrev(last_find);
2191 
2192  if(i < kSize)
2193  return i;
2194  // Else i could be the base type bit count, so we clamp it to our size.
2195 
2196  return kSize;
2197  }
2198 
2199 
2200 
2202  // global operators
2204 
2205  template <size_t N, typename WordType>
2206  inline bitset<N, WordType> operator&(const bitset<N, WordType>& a, const bitset<N, WordType>& b)
2207  {
2208  // We get betting inlining when we don't declare temporary variables.
2209  return bitset<N, WordType>(a).operator&=(b);
2210  }
2211 
2212 
2213  template <size_t N, typename WordType>
2214  inline bitset<N, WordType> operator|(const bitset<N, WordType>& a, const bitset<N, WordType>& b)
2215  {
2216  return bitset<N, WordType>(a).operator|=(b);
2217  }
2218 
2219 
2220  template <size_t N, typename WordType>
2221  inline bitset<N, WordType> operator^(const bitset<N, WordType>& a, const bitset<N, WordType>& b)
2222  {
2223  return bitset<N, WordType>(a).operator^=(b);
2224  }
2225 
2226 
2227 } // namespace eastl
2228 
2229 
2230 EA_RESTORE_VC_WARNING();
2231 
2232 #endif // Header include guard
eastl::any
Definition: any.h:104
eastl::bitset::reference
Definition: bitset.h:342
eastl::bitset
Definition: bitset.h:304
eastl::set
Definition: set.h:85
eastl
EA Standard Template Library.
Definition: algorithm.h:288
eastl::BitsetCountBits
uint32_t BitsetCountBits(uint64_t x)
Definition: bitset.h:442
eastl::BitsetBase< 1, WordType >
Definition: bitset.h:157
eastl::BitsetBase< 2, WordType >
Definition: bitset.h:224
eastl::BitsetBase
Definition: bitset.h:91
Generated by doxygen 1.9.1