tor-browser

SparseBitSet.h (5729B)

---

/* -*- 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_SparseBitSet_h
#define jit_SparseBitSet_h

#include "mozilla/Assertions.h"
#include "mozilla/MathAlgorithms.h"

#include <stddef.h>
#include <stdint.h>

#include "ds/InlineTable.h"
#include "ds/LifoAlloc.h"

namespace js::jit {

// jit::SparseBitSet is very similar to jit::BitSet, but optimized for sets that
// can be very large but are often very sparse.
//
// It uses an InlineMap mapping from word-index to 32-bit words storing bits.
//
// For example, consider the following bitmap of 192 bits:
//
//   0xff001100 0x00001000  0x00000000 0x00000000 0x00000000 0x11110000
//   0^         1^          2^         3^         4^         5^
//
// Words 2-4 don't have any bits set, so a SparseBitSet only stores the other
// words:
//
//   0 => 0xff001100
//   1 => 0x00001000
//   5 => 0x11110000
//
// SparseBitSet ensures words in the map are never 0.
template <typename AllocPolicy, typename Owner>
class SparseBitSet {
 // Note: use uint32_t (instead of uintptr_t or uint64_t) to not waste space in
 // InlineMap's array of inline entries. It uses a struct for each key/value
 // pair.
 using WordType = uint32_t;
 static constexpr size_t BitsPerWord = 8 * sizeof(WordType);

 // Note: 8 inline entries is sufficient for the majority of bit sets.
 // Compiling a large PhotoShop Wasm module with Ion, 94.5% of SparseBitSets
 // had <= 8 map entries. For OpenOffice this was more than 98.5%.
 static constexpr size_t NumEntries = 8;
 using Map = InlineMap<uint32_t, WordType, NumEntries, DefaultHasher<uint32_t>,
                       AllocPolicy>;
 using Range = typename Map::Range;
 Map map_;

 static_assert(mozilla::IsPowerOfTwo(BitsPerWord),
               "Must be power-of-two for fast division/modulo");
 static_assert((sizeof(uint32_t) + sizeof(WordType)) * NumEntries ==
                   Map::SizeOfInlineEntries,
               "Array of inline entries must not have unused padding bytes");

 static WordType bitMask(size_t bit) {
   return WordType(1) << (bit % BitsPerWord);
 }

public:
 class Iterator;

 bool contains(size_t bit) {
   uint32_t word = bit / BitsPerWord;
   if (auto p = map_.lookup(word)) {
     return p->value() & bitMask(bit);
   }
   return false;
 }
 void remove(size_t bit) {
   uint32_t word = bit / BitsPerWord;
   if (auto p = map_.lookup(word)) {
     WordType value = p->value() & ~bitMask(bit);
     if (value != 0) {
       p->value() = value;
     } else {
       // The iterator and empty() method rely on the map not containing
       // entries without any bits set.
       map_.remove(p);
     }
   }
 }
 [[nodiscard]] bool insert(size_t bit) {
   uint32_t word = bit / BitsPerWord;
   WordType mask = bitMask(bit);
   auto p = map_.lookupForAdd(word);
   if (p) {
     p->value() |= mask;
     return true;
   }
   return map_.add(p, word, mask);
 }

 bool empty() const { return map_.empty(); }

 [[nodiscard]] bool insertAll(const SparseBitSet& other) {
   for (Range r(other.map_.all()); !r.empty(); r.popFront()) {
     auto index = r.front().key();
     WordType bits = r.front().value();
     MOZ_ASSERT(bits);
     auto p = map_.lookupForAdd(index);
     if (p) {
       p->value() |= bits;
     } else {
       if (!map_.add(p, index, bits)) {
         return false;
       }
     }
   }
   return true;
 }
};

// Iterates over the set bits in a SparseBitSet. For example:
//
//   using Set = SparseBitSet<AllocPolicy>;
//   Set set;
//   ...
//   for (Set::Iterator iter(set); iter; ++iter) {
//     MOZ_ASSERT(set.contains(*iter));
//   }
template <typename AllocPolicy, typename Owner>
class SparseBitSet<AllocPolicy, Owner>::Iterator {
#ifdef DEBUG
 SparseBitSet& bitSet_;
#endif
 SparseBitSet::Range range_;
 WordType currentWord_ = 0;
 // Index of a 1-bit in the SparseBitSet. This is the value returned by
 // |*iter|.
 size_t index_ = 0;

 bool done() const { return range_.empty(); }

 void skipZeroBits() {
   MOZ_ASSERT(!done());
   MOZ_ASSERT(currentWord_ != 0);
   auto numZeroes = mozilla::CountTrailingZeroes32(currentWord_);
   index_ += numZeroes;
   currentWord_ >>= numZeroes;
 }

public:
 explicit Iterator(SparseBitSet& bitSet)
     :
#ifdef DEBUG
       bitSet_(bitSet),
#endif
       range_(bitSet.map_.all()) {
   if (!range_.empty()) {
     index_ = range_.front().key() * BitsPerWord;
     currentWord_ = range_.front().value();
     skipZeroBits();
   }
 }

 size_t operator*() const {
   MOZ_ASSERT(!done());
   MOZ_ASSERT(bitSet_.contains(index_));
   return index_;
 }

 explicit operator bool() const { return !done(); }

 void operator++() {
   MOZ_ASSERT(!done());
   currentWord_ >>= 1;
   if (currentWord_ == 0) {
     range_.popFront();
     if (range_.empty()) {
       // Done iterating.
       return;
     }
     index_ = range_.front().key() * BitsPerWord;
     currentWord_ = range_.front().value();
   } else {
     index_++;
   }
   skipZeroBits();
 }
};

}  // namespace js::jit

namespace js {

// A SparseBitSet may be LifoAllocated only if it is owned by a stack-allocated
// class, since that will cause it to be destroyed when the owner's scope ends.
// Otherwise, this could leak memory.
template <typename T, typename Owner>
struct CanLifoAlloc<js::jit::SparseBitSet<T, Owner>> : Owner::IsStackAllocated {
};

}  // namespace js

#endif /* jit_SparseBitSet_h */