js/src/util/BitArray.h

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
   2  * vim: set ts=8 sts=2 et sw=2 tw=80:
   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 /*
   8  * A bit array is an array of bits represented by an array of words (size_t).
   9  */
  10
  11 #ifndef util_BitArray_h
  12 #define util_BitArray_h
  13
  14 #include "mozilla/Assertions.h"
  15
  16 #include <limits.h>
  17 #include <stddef.h>
  18
  19 namespace js {
  20
  21 static const size_t BitArrayElementBits = sizeof(size_t) * CHAR_BIT;
  22
  23 static inline unsigned NumWordsForBitArrayOfLength(size_t length) {
  24   return (length + (BitArrayElementBits - 1)) / BitArrayElementBits;
  25 }
  26
  27 static inline unsigned BitArrayIndexToWordIndex(size_t length,
  28                                                 size_t bitIndex) {
  29   unsigned wordIndex = bitIndex / BitArrayElementBits;
  30   MOZ_ASSERT(wordIndex < length);
  31   return wordIndex;
  32 }
  33
  34 static inline size_t BitArrayIndexToWordMask(size_t i) {
  35   return size_t(1) << (i % BitArrayElementBits);
  36 }
  37
  38 static inline bool IsBitArrayElementSet(const size_t* array, size_t length,
  39                                         size_t i) {
  40   return array[BitArrayIndexToWordIndex(length, i)] &
  41          BitArrayIndexToWordMask(i);
  42 }
  43
  44 static inline bool IsAnyBitArrayElementSet(const size_t* array, size_t length) {
  45   unsigned numWords = NumWordsForBitArrayOfLength(length);
  46   for (unsigned i = 0; i < numWords; ++i) {
  47     if (array[i]) {
  48       return true;
  49     }
  50   }
  51   return false;
  52 }
  53
  54 static inline void SetBitArrayElement(size_t* array, size_t length, size_t i) {
  55   array[BitArrayIndexToWordIndex(length, i)] |= BitArrayIndexToWordMask(i);
  56 }
  57
  58 static inline void ClearBitArrayElement(size_t* array, size_t length,
  59                                         size_t i) {
  60   array[BitArrayIndexToWordIndex(length, i)] &= ~BitArrayIndexToWordMask(i);
  61 }
  62
  63 static inline void ClearAllBitArrayElements(size_t* array, size_t length) {
  64   for (unsigned i = 0; i < length; ++i) {
  65     array[i] = 0;
  66   }
  67 }
  68
  69 } /* namespace js */
  70
  71 #endif /* util_BitArray_h */