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
#ifndef ds_Bitmap_h
8
#define ds_Bitmap_h
9
10
#include "mozilla/Array.h"
11
#include "mozilla/Assertions.h"
12
#include "mozilla/Attributes.h"
13
#include "mozilla/MemoryChecking.h"
14
15
#include <algorithm>
16
#include <stddef.h>
17
#include <stdint.h>
18
19
#include "js/AllocPolicy.h"
20
#include "js/HashTable.h"
21
#include "js/Vector.h"
22
23
// This file provides two classes for representing bitmaps.
24
//
25
// DenseBitmap is an array of words of bits, with size linear in the maximum
26
// bit which has been set on it.
27
//
28
// SparseBitmap provides a reasonably simple, reasonably efficient (in time and
29
// space) implementation of a sparse bitmap. The basic representation is a hash
30
// table whose entries are fixed length malloc'ed blocks of bits.
31
32
namespace js {
33
34
class DenseBitmap {
35
using Data = Vector<uintptr_t, 0, SystemAllocPolicy>;
36
37
Data data;
38
39
public:
40
size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) {
41
return data.sizeOfExcludingThis(mallocSizeOf);
42
}
43
44
bool ensureSpace(size_t numWords) {
45
MOZ_ASSERT(data.empty());
46
return data.appendN(0, numWords);
47
}
48
49
size_t numWords() const { return data.length(); }
50
uintptr_t word(size_t i) const { return data[i]; }
51
uintptr_t& word(size_t i) { return data[i]; }
52
53
void copyBitsFrom(size_t wordStart, size_t numWords, uintptr_t* source) {
54
MOZ_ASSERT(wordStart + numWords <= data.length());
55
// Use std::copy and not std::copy_n because the former requires no
56
// overlap and so provides extra opportunity to optimize.
57
std::copy(source, source + numWords, &data[wordStart]);
58
}
59
60
void bitwiseOrRangeInto(size_t wordStart, size_t numWords,
61
uintptr_t* target) const {
62
for (size_t i = 0; i < numWords; i++) {
63
target[i] |= data[wordStart + i];
64
}
65
}
66
};
67
68
class SparseBitmap {
69
// The number of words of bits to use for each block mainly affects the
70
// memory usage of the bitmap. To minimize overhead, bitmaps which are
71
// expected to be fairly dense should have a large block size, and bitmaps
72
// which are expected to be very sparse should have a small block size.
73
static const size_t WordsInBlock = 4096 / sizeof(uintptr_t);
74
75
using BitBlock = mozilla::Array<uintptr_t, WordsInBlock>;
76
using Data =
77
HashMap<size_t, BitBlock*, DefaultHasher<size_t>, SystemAllocPolicy>;
78
79
Data data;
80
81
static size_t blockStartWord(size_t word) {
82
return word & ~(WordsInBlock - 1);
83
}
84
85
// Return the number of words in a BitBlock starting at |blockWord| which
86
// are in |other|.
87
static size_t wordIntersectCount(size_t blockWord, const DenseBitmap& other) {
88
long count = other.numWords() - blockWord;
89
return std::min<size_t>((size_t)WordsInBlock, std::max<long>(count, 0));
90
}
91
92
BitBlock& createBlock(Data::AddPtr p, size_t blockId,
93
AutoEnterOOMUnsafeRegion& oomUnsafe);
94
95
BitBlock* createBlock(Data::AddPtr p, size_t blockId);
96
97
MOZ_ALWAYS_INLINE BitBlock* getBlock(size_t blockId) const {
98
Data::Ptr p = data.lookup(blockId);
99
return p ? p->value() : nullptr;
100
}
101
102
MOZ_ALWAYS_INLINE BitBlock& getOrCreateBlock(size_t blockId) {
103
// The lookupForAdd() needs protection against injected OOMs, as does
104
// the add() within createBlock().
105
AutoEnterOOMUnsafeRegion oomUnsafe;
106
Data::AddPtr p = data.lookupForAdd(blockId);
107
if (p) {
108
return *p->value();
109
}
110
return createBlock(p, blockId, oomUnsafe);
111
}
112
113
MOZ_ALWAYS_INLINE BitBlock* getOrCreateBlockFallible(size_t blockId) {
114
Data::AddPtr p = data.lookupForAdd(blockId);
115
if (p) {
116
return p->value();
117
}
118
return createBlock(p, blockId);
119
}
120
121
public:
122
~SparseBitmap();
123
124
size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf);
125
126
MOZ_ALWAYS_INLINE void setBit(size_t bit) {
127
size_t word = bit / JS_BITS_PER_WORD;
128
size_t blockWord = blockStartWord(word);
129
BitBlock& block = getOrCreateBlock(blockWord / WordsInBlock);
130
block[word - blockWord] |= uintptr_t(1) << (bit % JS_BITS_PER_WORD);
131
}
132
133
MOZ_ALWAYS_INLINE bool setBitFallible(size_t bit) {
134
size_t word = bit / JS_BITS_PER_WORD;
135
size_t blockWord = blockStartWord(word);
136
BitBlock* block = getOrCreateBlockFallible(blockWord / WordsInBlock);
137
if (!block) {
138
return false;
139
}
140
(*block)[word - blockWord] |= uintptr_t(1) << (bit % JS_BITS_PER_WORD);
141
return true;
142
}
143
144
bool getBit(size_t bit) const;
145
146
void bitwiseAndWith(const DenseBitmap& other);
147
void bitwiseOrWith(const SparseBitmap& other);
148
void bitwiseOrInto(DenseBitmap& other) const;
149
150
// Currently, this API only supports a range of words that is in a single bit
151
// block.
152
void bitwiseOrRangeInto(size_t wordStart, size_t numWords,
153
uintptr_t* target) const;
154
};
155
156
} // namespace js
157
158
#endif // ds_Bitmap_h