tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

BitArray.h (2988B)

      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 #ifndef ds_BitArray_h
      8 #define ds_BitArray_h
      9 
     10 #include "mozilla/MathAlgorithms.h"
     11 
     12 #include <limits.h>
     13 #include <string.h>
     14 
     15 #include "jstypes.h"
     16 
     17 namespace js {
     18 
     19 namespace detail {
     20 
     21 template <typename WordT>
     22 inline uint_fast8_t CountTrailingZeroes(WordT word);
     23 
     24 template <>
     25 inline uint_fast8_t CountTrailingZeroes(uint32_t word) {
     26  return mozilla::CountTrailingZeroes32(word);
     27 }
     28 
     29 template <>
     30 inline uint_fast8_t CountTrailingZeroes(uint64_t word) {
     31  return mozilla::CountTrailingZeroes64(word);
     32 }
     33 
     34 }  // namespace detail
     35 
     36 template <size_t nbits>
     37 class BitArray {
     38 public:
     39  // Use a 32 bit word to make it easier to access a BitArray from JIT code.
     40  using WordT = uint32_t;
     41 
     42  static const size_t bitsPerElement = sizeof(WordT) * CHAR_BIT;
     43  static const size_t numSlots =
     44      nbits / bitsPerElement + (nbits % bitsPerElement == 0 ? 0 : 1);
     45 
     46 private:
     47  static const size_t paddingBits = (numSlots * bitsPerElement) - nbits;
     48  static_assert(paddingBits < bitsPerElement,
     49                "More padding bits than expected.");
     50  static const WordT paddingMask = WordT(-1) >> paddingBits;
     51 
     52  WordT map[numSlots];
     53 
     54 public:
     55  constexpr BitArray() : map() {};
     56 
     57  void clear(bool value) {
     58    memset(map, value ? 0xFF : 0, sizeof(map));
     59    if (value) {
     60      map[numSlots - 1] &= paddingMask;
     61    }
     62  }
     63 
     64  inline bool get(size_t offset) const {
     65    size_t index;
     66    WordT mask;
     67    getIndexAndMask(offset, &index, &mask);
     68    MOZ_ASSERT(index < nbits);
     69    return map[index] & mask;
     70  }
     71 
     72  void set(size_t offset) {
     73    size_t index;
     74    WordT mask;
     75    getIndexAndMask(offset, &index, &mask);
     76    map[index] |= mask;
     77  }
     78 
     79  void unset(size_t offset) {
     80    size_t index;
     81    WordT mask;
     82    getIndexAndMask(offset, &index, &mask);
     83    map[index] &= ~mask;
     84  }
     85 
     86  bool isAllClear() const {
     87    for (size_t i = 0; i < numSlots; i++) {
     88      if (map[i]) {
     89        return false;
     90      }
     91    }
     92    return true;
     93  }
     94 
     95  // For iterating over the set bits in the bit array, get a word at a time.
     96  WordT getWord(size_t elementIndex) const {
     97    MOZ_ASSERT(elementIndex < nbits);
     98    return map[elementIndex];
     99  }
    100 
    101  // Update a word at a time.
    102  void setWord(size_t elementIndex, WordT value) {
    103    MOZ_ASSERT(elementIndex < nbits);
    104    map[elementIndex] = value;
    105  }
    106 
    107  static void getIndexAndMask(size_t offset, size_t* indexp, WordT* maskp) {
    108    MOZ_ASSERT(offset < nbits);
    109    static_assert(bitsPerElement == 32, "unexpected bitsPerElement value");
    110    *indexp = offset / bitsPerElement;
    111    *maskp = WordT(1) << (offset % bitsPerElement);
    112  }
    113 
    114  static size_t offsetOfMap() { return offsetof(BitArray<nbits>, map); }
    115 };
    116 
    117 } /* namespace js */
    118 
    119 #endif /* ds_BitArray_h */