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
|
/* -*- 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/. */
#include "mozilla/PodOperations.h"
#include "ds/Bitmap.h"
#include "jsapi-tests/tests.h"
using namespace js;
BEGIN_TEST(testSparseBitmapBasics) {
SparseBitmap bitmap;
// Test bits in first block are initially zero.
for (size_t i = 0; i < 100; i++) {
CHECK(!bitmap.getBit(i));
}
// Test bits in different blocks are initially zero.
for (size_t i = 0; i < 100; i++) {
CHECK(!bitmap.getBit(i * 1000));
}
// Set some bits in the first block and check they are set.
for (size_t i = 0; i < 100; i += 2) {
bitmap.setBit(i);
}
for (size_t i = 0; i < 100; i++) {
CHECK(bitmap.getBit(i) == ((i % 2) == 0));
}
// Set some bits in different blocks and check they are set.
for (size_t i = 0; i < 100; i += 2) {
bitmap.setBit(i * 1000);
}
for (size_t i = 0; i < 100; i++) {
CHECK(bitmap.getBit(i * 1000) == ((i % 2) == 0));
}
// Create another bitmap with different bits set.
SparseBitmap other;
for (size_t i = 1; i < 100; i += 2) {
other.setBit(i * 1000);
}
for (size_t i = 0; i < 100; i++) {
CHECK(other.getBit(i * 1000) == ((i % 2) != 0));
}
// OR some bits into this bitmap and check the result.
bitmap.bitwiseOrWith(other);
for (size_t i = 0; i < 100; i++) {
CHECK(bitmap.getBit(i * 1000));
}
// AND some bits into this bitmap and check the result.
DenseBitmap dense;
size_t wordCount = (100 * 1000) / JS_BITS_PER_WORD + 1;
CHECK(dense.ensureSpace(wordCount));
other.bitwiseOrInto(dense);
bitmap.bitwiseAndWith(dense);
for (size_t i = 0; i < 100; i++) {
CHECK(bitmap.getBit(i * 1000) == ((i % 2) != 0));
}
return true;
}
END_TEST(testSparseBitmapBasics)
BEGIN_TEST(testSparseBitmapExternalOR) {
// Testing ORing data into an external array.
const size_t wordCount = 10;
// Create a bitmap with one bit set per word so we can tell them apart.
SparseBitmap bitmap;
for (size_t i = 0; i < wordCount; i++) {
bitmap.setBit(i * JS_BITS_PER_WORD + i);
}
// Copy a single word.
uintptr_t target[wordCount];
mozilla::PodArrayZero(target);
bitmap.bitwiseOrRangeInto(0, 1, target);
CHECK(target[0] == 1u << 0);
CHECK(target[1] == 0);
// Copy a word at an offset.
mozilla::PodArrayZero(target);
bitmap.bitwiseOrRangeInto(1, 1, target);
CHECK(target[0] == 1u << 1);
CHECK(target[1] == 0);
// Check data is ORed with original target contents.
mozilla::PodArrayZero(target);
bitmap.bitwiseOrRangeInto(0, 1, target);
bitmap.bitwiseOrRangeInto(1, 1, target);
CHECK(target[0] == ((1u << 0) | (1u << 1)));
// Copy multiple words at an offset.
mozilla::PodArrayZero(target);
bitmap.bitwiseOrRangeInto(2, wordCount - 2, target);
for (size_t i = 0; i < wordCount - 2; i++) {
CHECK(target[i] == (1u << (i + 2)));
}
CHECK(target[wordCount - 1] == 0);
return true;
}
END_TEST(testSparseBitmapExternalOR)
BEGIN_TEST(testSparseBitmapExternalAND) {
// Testing ANDing data from an external array.
const size_t wordCount = 4;
// Create a bitmap with two bits set per word based on the word index.
SparseBitmap bitmap;
for (size_t i = 0; i < wordCount; i++) {
bitmap.setBit(i * JS_BITS_PER_WORD + i);
bitmap.setBit(i * JS_BITS_PER_WORD + i + 1);
}
// Update a single word, clearing one of the bits.
uintptr_t source[wordCount];
CHECK(bitmap.getBit(0));
CHECK(bitmap.getBit(1));
source[0] = ~(1 << 1);
bitmap.bitwiseAndRangeWith(0, 1, source);
CHECK(bitmap.getBit(0));
CHECK(!bitmap.getBit(1));
// Update a word at an offset.
CHECK(bitmap.getBit(JS_BITS_PER_WORD + 1));
CHECK(bitmap.getBit(JS_BITS_PER_WORD + 2));
source[0] = ~(1 << 2);
bitmap.bitwiseAndRangeWith(1, 1, source);
CHECK(bitmap.getBit(JS_BITS_PER_WORD + 1));
CHECK(!bitmap.getBit(JS_BITS_PER_WORD + 2));
// Update multiple words at an offset.
CHECK(bitmap.getBit(JS_BITS_PER_WORD * 2 + 2));
CHECK(bitmap.getBit(JS_BITS_PER_WORD * 2 + 3));
CHECK(bitmap.getBit(JS_BITS_PER_WORD * 3 + 3));
CHECK(bitmap.getBit(JS_BITS_PER_WORD * 3 + 4));
source[0] = ~(1 << 3);
source[1] = ~(1 << 4);
bitmap.bitwiseAndRangeWith(2, 2, source);
CHECK(bitmap.getBit(JS_BITS_PER_WORD * 2 + 2));
CHECK(!bitmap.getBit(JS_BITS_PER_WORD * 2 + 3));
CHECK(bitmap.getBit(JS_BITS_PER_WORD * 3 + 3));
CHECK(!bitmap.getBit(JS_BITS_PER_WORD * 3 + 4));
return true;
}
END_TEST(testSparseBitmapExternalAND)
|
