tor-browser

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

BitSet.h (4250B)

      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 jit_BitSet_h
      8 #define jit_BitSet_h
      9 
     10 #include "mozilla/Assertions.h"
     11 #include "mozilla/MathAlgorithms.h"
     12 
     13 #include <stddef.h>
     14 #include <stdint.h>
     15 
     16 namespace js {
     17 namespace jit {
     18 
     19 class TempAllocator;
     20 
     21 // Provides constant time set insertion and removal, and fast linear
     22 // set operations such as intersection, difference, and union.
     23 // N.B. All set operations must be performed on sets with the same number
     24 // of bits.
     25 class BitSet {
     26 public:
     27  static const size_t BitsPerWord = 8 * sizeof(uint32_t);
     28 
     29  static size_t RawLengthForBits(size_t bits) {
     30    return (bits + BitsPerWord - 1) / BitsPerWord;
     31  }
     32 
     33 private:
     34  uint32_t* bits_;
     35  const unsigned int numBits_;
     36 
     37  static inline uint32_t bitForValue(unsigned int value) {
     38    return 1l << uint32_t(value % BitsPerWord);
     39  }
     40 
     41  static inline unsigned int wordForValue(unsigned int value) {
     42    return value / BitsPerWord;
     43  }
     44 
     45  inline unsigned int numWords() const { return RawLengthForBits(numBits_); }
     46 
     47  BitSet(const BitSet&) = delete;
     48  void operator=(const BitSet&) = delete;
     49 
     50 public:
     51  class Iterator;
     52 
     53  explicit BitSet(unsigned int numBits) : bits_(nullptr), numBits_(numBits) {}
     54 
     55  [[nodiscard]] bool init(TempAllocator& alloc);
     56 
     57  unsigned int getNumBits() const { return numBits_; }
     58 
     59  // O(1): Check if this set contains the given value.
     60  bool contains(unsigned int value) const {
     61    MOZ_ASSERT(bits_);
     62    MOZ_ASSERT(value < numBits_);
     63 
     64    return !!(bits_[wordForValue(value)] & bitForValue(value));
     65  }
     66 
     67  // O(numBits): Check if this set contains any value.
     68  bool empty() const;
     69 
     70  // O(1): Insert the given value into this set.
     71  void insert(unsigned int value) {
     72    MOZ_ASSERT(bits_);
     73    MOZ_ASSERT(value < numBits_);
     74 
     75    bits_[wordForValue(value)] |= bitForValue(value);
     76  }
     77 
     78  // O(numBits): Insert every element of the given set into this set.
     79  void insertAll(const BitSet& other);
     80 
     81  // O(1): Remove the given value from this set.
     82  void remove(unsigned int value) {
     83    MOZ_ASSERT(bits_);
     84    MOZ_ASSERT(value < numBits_);
     85 
     86    bits_[wordForValue(value)] &= ~bitForValue(value);
     87  }
     88 
     89  // O(numBits): Remove the every element of the given set from this set.
     90  void removeAll(const BitSet& other);
     91 
     92  // O(numBits): Intersect this set with the given set.
     93  void intersect(const BitSet& other);
     94 
     95  // O(numBits): Intersect this set with the given set; return whether the
     96  // intersection caused the set to change.
     97  bool fixedPointIntersect(const BitSet& other);
     98 
     99  // O(numBits): Does inplace complement of the set.
    100  void complement();
    101 
    102  // O(numBits): Clear this set.
    103  void clear();
    104 
    105  uint32_t* raw() const { return bits_; }
    106  size_t rawLength() const { return numWords(); }
    107 };
    108 
    109 class BitSet::Iterator {
    110 private:
    111  BitSet& set_;
    112  unsigned index_;
    113  unsigned word_;
    114  uint32_t value_;
    115 
    116  void skipEmpty() {
    117    // Skip words containing only zeros.
    118    unsigned numWords = set_.numWords();
    119    const uint32_t* bits = set_.bits_;
    120    while (value_ == 0) {
    121      word_++;
    122      if (word_ == numWords) {
    123        return;
    124      }
    125 
    126      index_ = word_ * BitSet::BitsPerWord;
    127      value_ = bits[word_];
    128    }
    129 
    130    // Be careful: the result of CountTrailingZeroes32 is undefined if the
    131    // input is 0.
    132    int numZeros = mozilla::CountTrailingZeroes32(value_);
    133    index_ += numZeros;
    134    value_ >>= numZeros;
    135 
    136    MOZ_ASSERT_IF(index_ < set_.numBits_, set_.contains(index_));
    137  }
    138 
    139 public:
    140  explicit Iterator(BitSet& set)
    141      : set_(set), index_(0), word_(0), value_(set.bits_[0]) {
    142    skipEmpty();
    143  }
    144 
    145  inline bool more() const { return word_ < set_.numWords(); }
    146  explicit operator bool() const { return more(); }
    147 
    148  inline void operator++() {
    149    MOZ_ASSERT(more());
    150    MOZ_ASSERT(index_ < set_.numBits_);
    151 
    152    index_++;
    153    value_ >>= 1;
    154 
    155    skipEmpty();
    156  }
    157 
    158  unsigned int operator*() {
    159    MOZ_ASSERT(index_ < set_.numBits_);
    160    return index_;
    161  }
    162 };
    163 
    164 }  // namespace jit
    165 }  // namespace js
    166 
    167 #endif /* jit_BitSet_h */