Line data    Source code

       1             : /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
       2             :  * vim: set ts=8 sts=4 et sw=4 tw=99:
       3             :  * This Source Code Form is subject to the terms of the Mozilla Public
       4             :  * License, v. 2.0. If a copy of the MPL was not distributed with this
       5             :  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
       6             : 
       7             : #ifndef ds_BitArray_h
       8             : #define ds_BitArray_h
       9             : 
      10             : #include "mozilla/TemplateLib.h"
      11             : 
      12             : #include <limits.h>
      13             : 
      14             : #include "jstypes.h"
      15             : 
      16             : namespace js {
      17             : 
      18             : template <size_t nbits>
      19             : class BitArray
      20             : {
      21             :   private:
      22             :     // Use a 32 bit word to make it easier to access a BitArray from JIT code.
      23             :     using WordT = uint32_t;
      24             : 
      25             :     static const size_t bitsPerElement = sizeof(WordT) * CHAR_BIT;
      26             :     static const size_t numSlots = nbits / bitsPerElement + (nbits % bitsPerElement == 0 ? 0 : 1);
      27             :     static const size_t paddingBits = (numSlots * bitsPerElement) - nbits;
      28             :     static_assert(paddingBits < bitsPerElement, "More padding bits than expected.");
      29             :     static const WordT paddingMask = WordT(-1) >> paddingBits;
      30             : 
      31             :     WordT map[numSlots];
      32             : 
      33             :   public:
      34         119 :     void clear(bool value) {
      35         119 :         memset(map, value ? 0xFF : 0, sizeof(map));
      36         119 :         if (value)
      37          50 :             map[numSlots - 1] &= paddingMask;
      38         119 :     }
      39             : 
      40       38918 :     inline bool get(size_t offset) const {
      41             :         size_t index;
      42             :         WordT mask;
      43       38918 :         getIndexAndMask(offset, &index, &mask);
      44       38918 :         return map[index] & mask;
      45             :     }
      46             : 
      47         402 :     void set(size_t offset) {
      48             :         size_t index;
      49             :         WordT mask;
      50         402 :         getIndexAndMask(offset, &index, &mask);
      51         402 :         map[index] |= mask;
      52         402 :     }
      53             : 
      54        6657 :     void unset(size_t offset) {
      55             :         size_t index;
      56             :         WordT mask;
      57        6657 :         getIndexAndMask(offset, &index, &mask);
      58        6657 :         map[index] &= ~mask;
      59        6657 :     }
      60             : 
      61         402 :     bool isAllClear() const {
      62        2715 :         for (size_t i = 0; i < numSlots; i++) {
      63        2715 :             if (map[i])
      64         402 :                 return false;
      65             :         }
      66           0 :         return true;
      67             :     }
      68             : 
      69       45982 :     static void getIndexAndMask(size_t offset, size_t* indexp, WordT* maskp) {
      70             :         static_assert(bitsPerElement == 32, "unexpected bitsPerElement value");
      71       45982 :         *indexp = offset / bitsPerElement;
      72       45982 :         *maskp = WordT(1) << (offset % bitsPerElement);
      73       45982 :     }
      74             : 
      75             :     static size_t offsetOfMap() {
      76             :         return offsetof(BitArray<nbits>, map);
      77             :     }
      78             : };
      79             : 
      80             : } /* namespace js */
      81             : 
      82             : #endif /* ds_BitArray_h */