Source code

Revision control

Other Tools

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
SparseBitmap::BitBlock& SparseBitmap::createBlock(
41
Data::AddPtr p, size_t blockId, AutoEnterOOMUnsafeRegion& oomUnsafe) {
42
BitBlock* block = createBlock(p, blockId);
43
if (!block) {
44
oomUnsafe.crash("Bitmap OOM");
45
}
46
return *block;
47
}
48
49
bool SparseBitmap::getBit(size_t bit) const {
50
size_t word = bit / JS_BITS_PER_WORD;
51
size_t blockWord = blockStartWord(word);
52
53
BitBlock* block = getBlock(blockWord / WordsInBlock);
54
if (block) {
55
return (*block)[word - blockWord] &
56
(uintptr_t(1) << (bit % JS_BITS_PER_WORD));
57
}
58
return false;
59
}
60
61
void SparseBitmap::bitwiseAndWith(const DenseBitmap& other) {
62
for (Data::Enum e(data); !e.empty(); e.popFront()) {
63
BitBlock& block = *e.front().value();
64
size_t blockWord = e.front().key() * WordsInBlock;
65
bool anySet = false;
66
size_t numWords = wordIntersectCount(blockWord, other);
67
for (size_t i = 0; i < numWords; i++) {
68
block[i] &= other.word(blockWord + i);
69
anySet |= !!block[i];
70
}
71
if (!anySet) {
72
js_delete(&block);
73
e.removeFront();
74
}
75
}
76
}
77
78
void SparseBitmap::bitwiseOrWith(const SparseBitmap& other) {
79
for (Data::Range r(other.data.all()); !r.empty(); r.popFront()) {
80
const BitBlock& otherBlock = *r.front().value();
81
BitBlock& block = getOrCreateBlock(r.front().key());
82
for (size_t i = 0; i < WordsInBlock; i++) {
83
block[i] |= otherBlock[i];
84
}
85
}
86
}
87
88
void SparseBitmap::bitwiseOrInto(DenseBitmap& other) const {
89
for (Data::Range r(data.all()); !r.empty(); r.popFront()) {
90
BitBlock& block = *r.front().value();
91
size_t blockWord = r.front().key() * WordsInBlock;
92
size_t numWords = wordIntersectCount(blockWord, other);
93
#ifdef DEBUG
94
// Any words out of range in other should be zero in this bitmap.
95
for (size_t i = numWords; i < WordsInBlock; i++) {
96
MOZ_ASSERT(!block[i]);
97
}
98
#endif
99
for (size_t i = 0; i < numWords; i++) {
100
other.word(blockWord + i) |= block[i];
101
}
102
}
103
}
104
105
void SparseBitmap::bitwiseOrRangeInto(size_t wordStart, size_t numWords,
106
uintptr_t* target) const {
107
size_t blockWord = blockStartWord(wordStart);
108
109
// We only support using a single bit block in this API.
110
MOZ_ASSERT(numWords &&
111
(blockWord == blockStartWord(wordStart + numWords - 1)));
112
113
BitBlock* block = getBlock(blockWord / WordsInBlock);
114
if (block) {
115
for (size_t i = 0; i < numWords; i++) {
116
target[i] |= (*block)[wordStart - blockWord + i];
117
}
118
}
119
}