Source code
Revision control
Copy as Markdown
Other Tools
/* -*- 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
#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)