tor-browser

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

Bitmap.cpp (3233B)

      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 #include "ds/Bitmap.h"
      8 
      9 #include <algorithm>
     10 
     11 #include "js/UniquePtr.h"
     12 
     13 using namespace js;
     14 
     15 SparseBitmap::~SparseBitmap() {
     16  for (Data::Range r(data.all()); !r.empty(); r.popFront()) {
     17    js_delete(r.front().value());
     18  }
     19 }
     20 
     21 size_t SparseBitmap::sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) {
     22  size_t size = data.shallowSizeOfExcludingThis(mallocSizeOf);
     23  for (Data::Range r(data.all()); !r.empty(); r.popFront()) {
     24    size += mallocSizeOf(r.front().value());
     25  }
     26  return size;
     27 }
     28 
     29 SparseBitmap::BitBlock* SparseBitmap::createBlock(Data::AddPtr p,
     30                                                  size_t blockId) {
     31  MOZ_ASSERT(!p);
     32  auto block = js::MakeUnique<BitBlock>();
     33  if (!block || !data.add(p, blockId, block.get())) {
     34    return nullptr;
     35  }
     36  std::fill(block->begin(), block->end(), 0);
     37  return block.release();
     38 }
     39 
     40 bool SparseBitmap::getBit(size_t bit) const {
     41  size_t word = bit / JS_BITS_PER_WORD;
     42  size_t blockWord = blockStartWord(word);
     43 
     44  const BitBlock* block = getBlock(blockWord / WordsInBlock);
     45  if (block) {
     46    return (*block)[word - blockWord] & bitMask(bit);
     47  }
     48  return false;
     49 }
     50 
     51 bool SparseBitmap::readonlyThreadsafeGetBit(size_t bit) const {
     52  size_t word = bit / JS_BITS_PER_WORD;
     53  size_t blockWord = blockStartWord(word);
     54 
     55  const BitBlock* block = readonlyThreadsafeGetBlock(blockWord / WordsInBlock);
     56  if (block) {
     57    return (*block)[word - blockWord] & bitMask(bit);
     58  }
     59  return false;
     60 }
     61 
     62 void SparseBitmap::bitwiseAndWith(const DenseBitmap& other) {
     63  for (Data::Enum e(data); !e.empty(); e.popFront()) {
     64    BitBlock& block = *e.front().value();
     65    size_t blockWord = e.front().key() * WordsInBlock;
     66    bool anySet = false;
     67    size_t numWords = wordIntersectCount(blockWord, other);
     68    for (size_t i = 0; i < numWords; i++) {
     69      block[i] &= other.word(blockWord + i);
     70      anySet |= !!block[i];
     71    }
     72    if (!anySet) {
     73      js_delete(&block);
     74      e.removeFront();
     75    }
     76  }
     77 }
     78 
     79 bool SparseBitmap::bitwiseOrWith(const SparseBitmap& other) {
     80  for (Data::Range r(other.data.all()); !r.empty(); r.popFront()) {
     81    const BitBlock& otherBlock = *r.front().value();
     82    BitBlock* block = getOrCreateBlock(r.front().key());
     83    if (!block) {
     84      return false;
     85    }
     86    for (size_t i = 0; i < WordsInBlock; i++) {
     87      (*block)[i] |= otherBlock[i];
     88    }
     89  }
     90 
     91  return true;
     92 }
     93 
     94 void SparseBitmap::bitwiseOrInto(DenseBitmap& other) const {
     95  for (Data::Range r(data.all()); !r.empty(); r.popFront()) {
     96    BitBlock& block = *r.front().value();
     97    size_t blockWord = r.front().key() * WordsInBlock;
     98    size_t numWords = wordIntersectCount(blockWord, other);
     99 #ifdef DEBUG
    100    // Any words out of range in other should be zero in this bitmap.
    101    for (size_t i = numWords; i < WordsInBlock; i++) {
    102      MOZ_ASSERT(!block[i]);
    103    }
    104 #endif
    105    for (size_t i = 0; i < numWords; i++) {
    106      other.word(blockWord + i) |= block[i];
    107    }
    108  }
    109 }