DXR is a code search and navigation tool aimed at making sense of large projects. It supports full-text and regex searches as well as structural queries.

Implementation

Mercurial (b6d82b1a6b02)

VCS Links

Line Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
 * vim: set ts=8 sts=2 et sw=2 tw=80:
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#ifndef jit_BitSet_h
#define jit_BitSet_h

#include "mozilla/MathAlgorithms.h"

#include "jit/JitAllocPolicy.h"

namespace js {
namespace jit {

// Provides constant time set insertion and removal, and fast linear
// set operations such as intersection, difference, and union.
// N.B. All set operations must be performed on sets with the same number
// of bits.
class BitSet {
 public:
  static const size_t BitsPerWord = 8 * sizeof(uint32_t);

  static size_t RawLengthForBits(size_t bits) {
    return (bits + BitsPerWord - 1) / BitsPerWord;
  }

 private:
  uint32_t* bits_;
  const unsigned int numBits_;

  static inline uint32_t bitForValue(unsigned int value) {
    return 1l << uint32_t(value % BitsPerWord);
  }

  static inline unsigned int wordForValue(unsigned int value) {
    return value / BitsPerWord;
  }

  inline unsigned int numWords() const { return RawLengthForBits(numBits_); }

  BitSet(const BitSet&) = delete;
  void operator=(const BitSet&) = delete;

 public:
  class Iterator;

  explicit BitSet(unsigned int numBits) : bits_(nullptr), numBits_(numBits) {}

  MOZ_MUST_USE bool init(TempAllocator& alloc);

  unsigned int getNumBits() const { return numBits_; }

  // O(1): Check if this set contains the given value.
  bool contains(unsigned int value) const {
    MOZ_ASSERT(bits_);
    MOZ_ASSERT(value < numBits_);

    return !!(bits_[wordForValue(value)] & bitForValue(value));
  }

  // O(numBits): Check if this set contains any value.
  bool empty() const;

  // O(1): Insert the given value into this set.
  void insert(unsigned int value) {
    MOZ_ASSERT(bits_);
    MOZ_ASSERT(value < numBits_);

    bits_[wordForValue(value)] |= bitForValue(value);
  }

  // O(numBits): Insert every element of the given set into this set.
  void insertAll(const BitSet& other);

  // O(1): Remove the given value from this set.
  void remove(unsigned int value) {
    MOZ_ASSERT(bits_);
    MOZ_ASSERT(value < numBits_);

    bits_[wordForValue(value)] &= ~bitForValue(value);
  }

  // O(numBits): Remove the every element of the given set from this set.
  void removeAll(const BitSet& other);

  // O(numBits): Intersect this set with the given set.
  void intersect(const BitSet& other);

  // O(numBits): Intersect this set with the given set; return whether the
  // intersection caused the set to change.
  bool fixedPointIntersect(const BitSet& other);

  // O(numBits): Does inplace complement of the set.
  void complement();

  // O(numBits): Clear this set.
  void clear();

  uint32_t* raw() const { return bits_; }
  size_t rawLength() const { return numWords(); }
};

class BitSet::Iterator {
 private:
  BitSet& set_;
  unsigned index_;
  unsigned word_;
  uint32_t value_;

  void skipEmpty() {
    // Skip words containing only zeros.
    unsigned numWords = set_.numWords();
    const uint32_t* bits = set_.bits_;
    while (value_ == 0) {
      word_++;
      if (word_ == numWords) {
        return;
      }

      index_ = word_ * BitSet::BitsPerWord;
      value_ = bits[word_];
    }

    // Be careful: the result of CountTrailingZeroes32 is undefined if the
    // input is 0.
    int numZeros = mozilla::CountTrailingZeroes32(value_);
    index_ += numZeros;
    value_ >>= numZeros;

    MOZ_ASSERT_IF(index_ < set_.numBits_, set_.contains(index_));
  }

 public:
  explicit Iterator(BitSet& set)
      : set_(set), index_(0), word_(0), value_(set.bits_[0]) {
    skipEmpty();
  }

  inline bool more() const { return word_ < set_.numWords(); }
  explicit operator bool() const { return more(); }

  inline void operator++() {
    MOZ_ASSERT(more());
    MOZ_ASSERT(index_ < set_.numBits_);

    index_++;
    value_ >>= 1;

    skipEmpty();
  }

  unsigned int operator*() {
    MOZ_ASSERT(index_ < set_.numBits_);
    return index_;
  }
};

}  // namespace jit
}  // namespace js

#endif /* jit_BitSet_h */