Google Git
Sign in
chromium / external / github.com / WebKit / webkit / refs/heads/safari-610.1.23.0-branch / . / Tools / TestWebKitAPI / Tests / WTF / Bitmap.cpp
blob: 38153b26605d62e13df21e5a05ee20943c21ebba [file] [log] [blame] [edit]
/*
* Copyright (C) 2020 Apple Inc. All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
* AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
* THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
* BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
* CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
* SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
* INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
* CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
* THE POSSIBILITY OF SUCH DAMAGE.
*/
#include "config.h"
#include <wtf/Bitmap.h>
namespace TestWebKitAPI {
constexpr size_t size = 128;
constexpr size_t smallSize = 9;
constexpr size_t zeroSize = 0;
static constexpr bool expectedBits1[size] = {
false, false, true, false, false, false, false, false,
false, false, false, false, false, false, false, true,
false, true, false, false, false, false, true, false,
false, false, true, false, false, false, true, true,
true, false, false, false, false, true, false, false,
true, false, false, false, false, true, false, true,
false, false, false, false, false, true, true, false,
false, true, false, false, false, true, true, true,
false, false, true, false, true, false, false, false,
false, false, true, false, true, false, false, true,
true, false, false, false, true, false, true, false,
false, false, false, false, true, false, true, true,
false, false, false, false, true, true, false, false,
false, true, false, false, true, true, false, true,
false, true, false, false, true, true, true, false,
false, false, true, false, true, true, true, true,
};
static constexpr bool expectedBits2[size] = {
false, true, false, true, false, false, false, false,
false, false, false, true, false, false, false, true,
false, false, false, true, false, false, true, false,
false, false, false, true, false, false, true, true,
true, false, false, true, false, true, false, false,
false, false, false, true, false, true, false, true,
false, false, false, true, false, true, true, false,
false, false, true, true, false, true, true, true,
false, true, false, true, true, false, false, false,
false, true, false, true, true, false, false, true,
false, false, false, true, true, false, true, false,
false, false, true, true, true, false, true, true,
true, false, false, true, true, true, false, false,
false, false, true, true, true, true, false, true,
true, false, false, true, true, true, true, false,
false, true, false, true, true, true, true, true,
};
static constexpr bool expectedSmallBits1[smallSize] = {
false, true, true, false, true, false, false, true,
true,
};
static constexpr bool expectedSmallBits2[smallSize] = {
true, true, false, false, false, false, true, true,
false,
};
constexpr size_t countBits(const bool boolArray[], size_t size)
{
size_t result = 0;
for (size_t i = 0; i < size; ++i) {
if (boolArray[i])
result++;
}
return result;
}
constexpr size_t expectedNumberOfSetBits1 = countBits(expectedBits1, size);
constexpr size_t expectedNumberOfSetBits2 = countBits(expectedBits2, size);
#define DECLARE_BITMAPS_FOR_TEST() \
Bitmap<size, WordType> bitmapZeroes; \
Bitmap<size, WordType> bitmap1; /* Will hold values specified in expectedBits1. */ \
Bitmap<size, WordType> bitmap2; /* Will hold values specified in expectedBits2. */ \
Bitmap<size, WordType> bitmap2Clone; /* Same as bitmap2. */ \
Bitmap<size, WordType> bitmapOnes; \
Bitmap<smallSize, WordType> smallBitmapZeroes; \
Bitmap<smallSize, WordType> smallBitmapOnes; \
Bitmap<smallSize, WordType> smallBitmap1; /* Will hold values specified in expectedSmallBits1. */ \
Bitmap<smallSize, WordType> smallBitmap2; /* Will hold values specified in expectedSmallBits2. */ \
#define DECLARE_AND_INIT_BITMAPS_FOR_TEST() \
DECLARE_BITMAPS_FOR_TEST() \
for (size_t i = 0; i < size; ++i) { \
bitmap1.set(i, expectedBits1[i]); \
bitmap2.set(i, expectedBits2[i]); \
bitmap2Clone.set(i, expectedBits2[i]); \
bitmapOnes.set(i); \
} \
for (size_t i = 0; i < smallSize; ++i) { \
smallBitmap1.set(i, expectedSmallBits1[i]); \
smallBitmap2.set(i, expectedSmallBits2[i]); \
smallBitmapOnes.set(i); \
}
template<typename WordType>
void testBitmapSize()
{
DECLARE_BITMAPS_FOR_TEST();
auto verifySize = [=] (auto& bitmap, size_t expectedSize, size_t notExpectedSize) {
EXPECT_EQ(bitmap.size(), expectedSize);
EXPECT_NE(bitmap.size(), notExpectedSize);
};
verifySize(bitmapZeroes, size, smallSize);
verifySize(bitmap1, size, smallSize);
verifySize(bitmap2, size, smallSize);
verifySize(bitmap2Clone, size, smallSize);
verifySize(bitmapOnes, size, smallSize);
verifySize(smallBitmapZeroes, smallSize, size);
verifySize(smallBitmapOnes, smallSize, size);
}
template<typename WordType>
void testBitmapConstructedEmpty()
{
DECLARE_BITMAPS_FOR_TEST();
// Verify that the default constructor initializes all bits to 0.
auto verifyIsEmpty = [=] (const auto& bitmap) {
EXPECT_TRUE(bitmap.isEmpty());
EXPECT_EQ(bitmap.count(), zeroSize);
for (size_t i = 0; i < bitmap.size(); ++i)
EXPECT_FALSE(bitmap.get(i));
};
verifyIsEmpty(bitmapZeroes);
verifyIsEmpty(bitmap1);
verifyIsEmpty(bitmap2);
verifyIsEmpty(bitmap2Clone);
verifyIsEmpty(bitmapOnes);
verifyIsEmpty(smallBitmapZeroes);
verifyIsEmpty(smallBitmapOnes);
}
template<typename WordType>
void testBitmapSetGet()
{
DECLARE_AND_INIT_BITMAPS_FOR_TEST();
auto verifyIsEmpty = [=] (const auto& bitmap) {
EXPECT_TRUE(bitmap.isEmpty());
EXPECT_EQ(bitmap.count(), zeroSize);
for (size_t i = 0; i < bitmap.size(); ++i)
EXPECT_FALSE(bitmap.get(i));
};
for (size_t i = 0; i < size; ++i)
EXPECT_EQ(bitmap1.get(i), expectedBits1[i]);
for (size_t i = 0; i < size; ++i) {
EXPECT_EQ(bitmap2.get(i), expectedBits2[i]);
EXPECT_EQ(bitmap2Clone.get(i), expectedBits2[i]);
}
for (size_t i = 0; i < size; ++i)
EXPECT_EQ(bitmap2.get(i), bitmap2Clone.get(i));
for (size_t i = 0; i < size; ++i)
EXPECT_TRUE(bitmapOnes.get(i));
for (size_t i = 0; i < smallSize; ++i)
EXPECT_TRUE(smallBitmapOnes.get(i));
// Verify that there is no out of bounds write from the above set operations.
verifyIsEmpty(bitmapZeroes);
verifyIsEmpty(smallBitmapZeroes);
}
template<typename WordType>
void testBitmapTestAndSet()
{
DECLARE_AND_INIT_BITMAPS_FOR_TEST();
ASSERT_FALSE(bitmap1.isFull());
for (size_t i = 0; i < size; ++i)
ASSERT_EQ(bitmap1.get(i), expectedBits1[i]);
for (size_t i = 0; i < size; ++i)
ASSERT_EQ(bitmap1.testAndSet(i), expectedBits1[i]);
ASSERT_TRUE(bitmap1.isFull());
ASSERT_FALSE(smallBitmapZeroes.isFull());
ASSERT_TRUE(smallBitmapZeroes.isEmpty());
for (size_t i = 0; i < smallSize; ++i)
ASSERT_FALSE(smallBitmapZeroes.testAndSet(i));
ASSERT_TRUE(smallBitmapZeroes.isFull());
}
template<typename WordType>
void testBitmapTestAndClear()
{
DECLARE_AND_INIT_BITMAPS_FOR_TEST();
ASSERT_FALSE(bitmap1.isEmpty());
for (size_t i = 0; i < size; ++i)
ASSERT_EQ(bitmap1.get(i), expectedBits1[i]);
for (size_t i = 0; i < size; ++i)
ASSERT_EQ(bitmap1.testAndClear(i), expectedBits1[i]);
ASSERT_TRUE(bitmap1.isEmpty());
ASSERT_FALSE(smallBitmapOnes.isEmpty());
ASSERT_TRUE(smallBitmapOnes.isFull());
for (size_t i = 0; i < smallSize; ++i)
ASSERT_TRUE(smallBitmapOnes.testAndClear(i));
ASSERT_TRUE(smallBitmapOnes.isEmpty());
}
template<typename WordType>
void testBitmapConcurrentTestAndSet()
{
DECLARE_AND_INIT_BITMAPS_FOR_TEST();
// FIXME: the following does not test the concurrent part. It only ensures that
// the TestAndSet part of the operation is working.
ASSERT_FALSE(bitmap1.isFull());
for (size_t i = 0; i < size; ++i)
ASSERT_EQ(bitmap1.get(i), expectedBits1[i]);
for (size_t i = 0; i < size; ++i)
ASSERT_EQ(bitmap1.testAndSet(i), expectedBits1[i]);
ASSERT_TRUE(bitmap1.isFull());
ASSERT_FALSE(smallBitmapZeroes.isFull());
ASSERT_TRUE(smallBitmapZeroes.isEmpty());
for (size_t i = 0; i < smallSize; ++i)
ASSERT_FALSE(smallBitmapZeroes.testAndSet(i));
ASSERT_TRUE(smallBitmapZeroes.isFull());
}
template<typename WordType>
void testBitmapConcurrentTestAndClear()
{
DECLARE_AND_INIT_BITMAPS_FOR_TEST();
// FIXME: the following does not test the concurrent part. It only ensures that
// the TestAndClear part of the operation is working.
ASSERT_FALSE(bitmap1.isEmpty());
for (size_t i = 0; i < size; ++i)
ASSERT_EQ(bitmap1.get(i), expectedBits1[i]);
for (size_t i = 0; i < size; ++i)
ASSERT_EQ(bitmap1.testAndClear(i), expectedBits1[i]);
ASSERT_TRUE(bitmap1.isEmpty());
ASSERT_FALSE(smallBitmapOnes.isEmpty());
ASSERT_TRUE(smallBitmapOnes.isFull());
for (size_t i = 0; i < smallSize; ++i)
ASSERT_TRUE(smallBitmapOnes.testAndClear(i));
ASSERT_TRUE(smallBitmapOnes.isEmpty());
}
template<typename WordType>
void testBitmapClear()
{
DECLARE_AND_INIT_BITMAPS_FOR_TEST();
ASSERT_TRUE(bitmapOnes.isFull());
for (size_t i = 0; i < size; ++i) {
if (!expectedBits1[i])
bitmapOnes.clear(i);
}
ASSERT_EQ(bitmapOnes, bitmap1);
}
template<typename WordType>
void testBitmapClearAll()
{
DECLARE_AND_INIT_BITMAPS_FOR_TEST();
auto verifyIsEmpty = [=] (const auto& bitmap) {
EXPECT_TRUE(bitmap.isEmpty());
EXPECT_EQ(bitmap.count(), zeroSize);
for (size_t i = 0; i < bitmap.size(); ++i)
EXPECT_FALSE(bitmap.get(i));
};
auto verifyIsFull = [=] (const auto& bitmap) {
EXPECT_TRUE(bitmap.isFull());
for (size_t i = 0; i < bitmap.size(); ++i)
EXPECT_TRUE(bitmap.get(i));
};
EXPECT_FALSE(bitmap1.isEmpty());
bitmap1.clearAll();
verifyIsEmpty(bitmap1);
verifyIsFull(bitmapOnes);
verifyIsFull(smallBitmapOnes);
EXPECT_FALSE(bitmap2.isEmpty());
bitmap2.clearAll();
verifyIsEmpty(bitmap1);
verifyIsEmpty(bitmap2);
verifyIsFull(bitmapOnes);
verifyIsFull(smallBitmapOnes);
EXPECT_FALSE(bitmap2Clone.isEmpty());
bitmap2Clone.clearAll();
verifyIsEmpty(bitmap1);
verifyIsEmpty(bitmap2);
verifyIsEmpty(bitmap2Clone);
verifyIsFull(bitmapOnes);
verifyIsFull(smallBitmapOnes);
}
template<typename WordType>
void testBitmapInvert()
{
DECLARE_AND_INIT_BITMAPS_FOR_TEST();
auto verifyInvert = [=] (auto& bitmap) {
ASSERT_TRUE(bitmap.isFull());
ASSERT_FALSE(bitmap.isEmpty());
bitmap.invert();
ASSERT_FALSE(bitmap.isFull());
ASSERT_TRUE(bitmap.isEmpty());
bitmap.invert();
ASSERT_TRUE(bitmap.isFull());
ASSERT_FALSE(bitmap.isEmpty());
};
verifyInvert(bitmapOnes);
verifyInvert(smallBitmapOnes);
for (size_t i = 0; i < size; ++i)
ASSERT_EQ(bitmap1.get(i), expectedBits1[i]);
bitmap1.invert();
for (size_t i = 0; i < size; ++i)
ASSERT_EQ(bitmap1.get(i), !expectedBits1[i]);
bitmap1.invert();
for (size_t i = 0; i < size; ++i)
ASSERT_EQ(bitmap1.get(i), expectedBits1[i]);
}
template<typename WordType>
void testBitmapFindRunOfZeros()
{
DECLARE_AND_INIT_BITMAPS_FOR_TEST();
const int64_t bitmap1RunsOfZeros[15] = {
0, 0, 0, 3, 3,
3, 3, 3, 3, 3,
3, 3, 3, -1, -1
};
const int64_t bitmap2RunsOfZeros[15] = {
0, 0, 4, 4, 4,
4, 4, 4, -1, -1,
-1, -1, -1, -1, -1,
};
Bitmap<smallSize, WordType> smallTemp;
smallTemp.set(1, true); // bits low to high are: 0100 0000 0
const int64_t smallTempRunsOfZeros[15] = {
0, 0, 2, 2, 2,
2, 2, 2, -1, -1,
-1, -1, -1, -1, -1
};
for (size_t runLength = 0; runLength < 15; ++runLength) {
ASSERT_EQ(bitmapZeroes.findRunOfZeros(runLength), 0ll);
ASSERT_EQ(bitmap1.findRunOfZeros(runLength), bitmap1RunsOfZeros[runLength]);
ASSERT_EQ(bitmap2.findRunOfZeros(runLength), bitmap2RunsOfZeros[runLength]);
ASSERT_EQ(bitmapOnes.findRunOfZeros(runLength), -1ll);
if (runLength <= smallSize)
ASSERT_EQ(smallBitmapZeroes.findRunOfZeros(runLength), 0ll);
else
ASSERT_EQ(smallBitmapZeroes.findRunOfZeros(runLength), -1ll);
ASSERT_EQ(smallBitmapOnes.findRunOfZeros(runLength), -1ll);
ASSERT_EQ(smallTemp.findRunOfZeros(runLength), smallTempRunsOfZeros[runLength]);
}
}
template<typename WordType>
void testBitmapCount()
{
DECLARE_AND_INIT_BITMAPS_FOR_TEST();
EXPECT_EQ(bitmapZeroes.count(), zeroSize);
EXPECT_EQ(bitmap1.count(), expectedNumberOfSetBits1);
EXPECT_EQ(bitmap2.count(), expectedNumberOfSetBits2);
EXPECT_EQ(bitmap2Clone.count(), expectedNumberOfSetBits2);
EXPECT_EQ(bitmapOnes.count(), size);
EXPECT_EQ(smallBitmapZeroes.count(), zeroSize);
EXPECT_EQ(smallBitmapOnes.count(), smallSize);
}
template<typename WordType>
void testBitmapIsEmpty()
{
DECLARE_AND_INIT_BITMAPS_FOR_TEST();
EXPECT_TRUE(bitmapZeroes.isEmpty());
EXPECT_FALSE(bitmap1.isEmpty());
EXPECT_FALSE(bitmap2.isEmpty());
EXPECT_FALSE(bitmap2Clone.isEmpty());
EXPECT_FALSE(bitmapOnes.isEmpty());
EXPECT_TRUE(smallBitmapZeroes.isEmpty());
EXPECT_FALSE(smallBitmapOnes.isEmpty());
auto verifyIsEmpty = [=] (const auto& bitmap) {
EXPECT_TRUE(bitmap.isEmpty());
EXPECT_EQ(bitmap.count(), zeroSize);
for (size_t i = 0; i < bitmap.size(); ++i)
EXPECT_FALSE(bitmap.get(i));
};
verifyIsEmpty(bitmapZeroes);
verifyIsEmpty(smallBitmapZeroes);
}
template<typename WordType>
void testBitmapIsFull()
{
DECLARE_AND_INIT_BITMAPS_FOR_TEST();
EXPECT_FALSE(bitmapZeroes.isFull());
EXPECT_FALSE(bitmap1.isFull());
EXPECT_FALSE(bitmap2.isFull());
EXPECT_FALSE(bitmap2Clone.isFull());
EXPECT_TRUE(bitmapOnes.isFull());
EXPECT_FALSE(smallBitmapZeroes.isFull());
EXPECT_TRUE(smallBitmapOnes.isFull());
auto verifyIsFull = [=] (auto& bitmap) {
EXPECT_TRUE(bitmap.isFull());
for (size_t i = 0; i < bitmap.size(); ++i)
EXPECT_TRUE(bitmap.get(i));
};
verifyIsFull(bitmapOnes);
verifyIsFull(smallBitmapOnes);
}
template<typename WordType>
void testBitmapMerge()
{
DECLARE_AND_INIT_BITMAPS_FOR_TEST();
ASSERT_TRUE(bitmapZeroes.isEmpty());
ASSERT_EQ(bitmap2, bitmap2Clone);
bitmap2.merge(bitmapZeroes);
ASSERT_EQ(bitmap2, bitmap2Clone);
ASSERT_NE(bitmap1, bitmap2);
ASSERT_NE(bitmap1, bitmap2Clone);
ASSERT_EQ(bitmap2, bitmap2Clone);
bitmap2Clone.merge(bitmap1);
ASSERT_NE(bitmap2, bitmap2Clone);
for (size_t i = 0; i < size; ++i) {
bool expectedBit = expectedBits2[i] | expectedBits1[i];
ASSERT_EQ(bitmap2Clone.get(i), expectedBit);
}
ASSERT_TRUE(bitmapOnes.isFull());
ASSERT_TRUE(bitmapZeroes.isEmpty());
bitmapOnes.merge(bitmapZeroes);
ASSERT_TRUE(bitmapOnes.isFull());
ASSERT_TRUE(bitmapZeroes.isEmpty());
bitmapZeroes.merge(bitmap1);
ASSERT_EQ(bitmapZeroes, bitmap1);
bitmap1.merge(bitmapOnes);
ASSERT_EQ(bitmap1, bitmapOnes);
ASSERT_TRUE(smallBitmapZeroes.isEmpty());
ASSERT_TRUE(smallBitmapOnes.isFull());
smallBitmapZeroes.merge(smallBitmapOnes);
ASSERT_FALSE(smallBitmapZeroes.isEmpty());
ASSERT_TRUE(smallBitmapZeroes.isFull());
ASSERT_TRUE(smallBitmapOnes.isFull());
smallBitmapZeroes.clearAll();
ASSERT_TRUE(smallBitmapZeroes.isEmpty());
ASSERT_TRUE(smallBitmapOnes.isFull());
smallBitmapOnes.merge(smallBitmapZeroes);
ASSERT_TRUE(smallBitmapOnes.isFull());
ASSERT_TRUE(smallBitmapZeroes.isEmpty());
}
template<typename WordType>
void testBitmapFilter()
{
DECLARE_AND_INIT_BITMAPS_FOR_TEST();
ASSERT_TRUE(bitmapOnes.isFull());
ASSERT_EQ(bitmap2, bitmap2Clone);
bitmap2.filter(bitmapOnes);
ASSERT_EQ(bitmap2, bitmap2Clone);
ASSERT_NE(bitmap1, bitmap2);
ASSERT_NE(bitmap1, bitmap2Clone);
ASSERT_EQ(bitmap2, bitmap2Clone);
bitmap2Clone.filter(bitmap1);
ASSERT_NE(bitmap2, bitmap2Clone);
for (size_t i = 0; i < size; ++i) {
bool expectedBit = expectedBits2[i] & expectedBits1[i];
ASSERT_EQ(bitmap2Clone.get(i), expectedBit);
}
ASSERT_TRUE(bitmapZeroes.isEmpty());
bitmap2.filter(bitmapZeroes);
ASSERT_EQ(bitmap2, bitmapZeroes);
ASSERT_TRUE(bitmapZeroes.isEmpty());
bitmapZeroes.filter(bitmap1);
ASSERT_TRUE(bitmapZeroes.isEmpty());
ASSERT_TRUE(bitmapOnes.isFull());
bitmapOnes.filter(bitmap1);
ASSERT_EQ(bitmapOnes, bitmap1);
ASSERT_TRUE(smallBitmapZeroes.isEmpty());
ASSERT_TRUE(smallBitmapOnes.isFull());
smallBitmapZeroes.filter(smallBitmapOnes);
ASSERT_TRUE(smallBitmapZeroes.isEmpty());
ASSERT_FALSE(smallBitmapZeroes.isFull());
ASSERT_TRUE(smallBitmapOnes.isFull());
smallBitmapOnes.filter(smallBitmapZeroes);
ASSERT_FALSE(smallBitmapOnes.isFull());
ASSERT_TRUE(smallBitmapOnes.isEmpty());
ASSERT_TRUE(smallBitmapZeroes.isEmpty());
}
template<typename WordType>
void testBitmapExclude()
{
DECLARE_AND_INIT_BITMAPS_FOR_TEST();
ASSERT_TRUE(bitmapZeroes.isEmpty());
ASSERT_EQ(bitmap2, bitmap2Clone);
bitmap2.exclude(bitmapZeroes);
ASSERT_EQ(bitmap2, bitmap2Clone);
ASSERT_NE(bitmap1, bitmap2);
ASSERT_NE(bitmap1, bitmap2Clone);
ASSERT_EQ(bitmap2, bitmap2Clone);
bitmap2Clone.exclude(bitmap1);
ASSERT_NE(bitmap2, bitmap2Clone);
for (size_t i = 0; i < size; ++i) {
bool expectedBit = expectedBits2[i] & !expectedBits1[i];
ASSERT_EQ(bitmap2Clone.get(i), expectedBit);
}
ASSERT_TRUE(bitmapZeroes.isEmpty());
ASSERT_TRUE(bitmapOnes.isFull());
bitmap2.exclude(bitmapOnes);
ASSERT_EQ(bitmap2, bitmapZeroes);
ASSERT_TRUE(bitmapOnes.isFull());
bitmapOnes.exclude(bitmap1);
bitmap1.invert();
ASSERT_EQ(bitmapOnes, bitmap1);
ASSERT_TRUE(smallBitmapZeroes.isEmpty());
ASSERT_TRUE(smallBitmapOnes.isFull());
smallBitmapZeroes.exclude(smallBitmapOnes);
ASSERT_TRUE(smallBitmapZeroes.isEmpty());
ASSERT_FALSE(smallBitmapZeroes.isFull());
ASSERT_TRUE(smallBitmapOnes.isFull());
smallBitmapOnes.exclude(smallBitmapZeroes);
ASSERT_TRUE(smallBitmapOnes.isFull());
ASSERT_TRUE(smallBitmapZeroes.isEmpty());
smallBitmapOnes.exclude(smallBitmapOnes);
ASSERT_FALSE(smallBitmapOnes.isFull());
ASSERT_TRUE(smallBitmapOnes.isEmpty());
}
template<typename WordType>
void testBitmapConcurrentFilter()
{
DECLARE_AND_INIT_BITMAPS_FOR_TEST();
// FIXME: the following does not test the concurrent part. It only ensures that
// the Filter part of the operation is working.
ASSERT_TRUE(bitmapOnes.isFull());
ASSERT_EQ(bitmap2, bitmap2Clone);
bitmap2.concurrentFilter(bitmapOnes);
ASSERT_EQ(bitmap2, bitmap2Clone);
ASSERT_NE(bitmap1, bitmap2);
ASSERT_NE(bitmap1, bitmap2Clone);
ASSERT_EQ(bitmap2, bitmap2Clone);
bitmap2Clone.concurrentFilter(bitmap1);
ASSERT_NE(bitmap2, bitmap2Clone);
for (size_t i = 0; i < size; ++i) {
bool expectedBit = expectedBits2[i] & expectedBits1[i];
ASSERT_EQ(bitmap2Clone.get(i), expectedBit);
}
ASSERT_TRUE(bitmapZeroes.isEmpty());
bitmap2.concurrentFilter(bitmapZeroes);
ASSERT_EQ(bitmap2, bitmapZeroes);
ASSERT_TRUE(bitmapZeroes.isEmpty());
bitmapZeroes.concurrentFilter(bitmap1);
ASSERT_TRUE(bitmapZeroes.isEmpty());
ASSERT_TRUE(bitmapOnes.isFull());
bitmapOnes.concurrentFilter(bitmap1);
ASSERT_EQ(bitmapOnes, bitmap1);
ASSERT_TRUE(smallBitmapZeroes.isEmpty());
ASSERT_TRUE(smallBitmapOnes.isFull());
smallBitmapZeroes.concurrentFilter(smallBitmapOnes);
ASSERT_TRUE(smallBitmapZeroes.isEmpty());
ASSERT_FALSE(smallBitmapZeroes.isFull());
ASSERT_TRUE(smallBitmapOnes.isFull());
smallBitmapOnes.concurrentFilter(smallBitmapZeroes);
ASSERT_FALSE(smallBitmapOnes.isFull());
ASSERT_TRUE(smallBitmapOnes.isEmpty());
ASSERT_TRUE(smallBitmapZeroes.isEmpty());
}
template<typename WordType>
void testBitmapSubsumes()
{
DECLARE_AND_INIT_BITMAPS_FOR_TEST();
ASSERT_TRUE(bitmapZeroes.isEmpty());
ASSERT_TRUE(bitmapOnes.isFull());
ASSERT_EQ(bitmap2, bitmap2Clone);
ASSERT_TRUE(bitmapZeroes.subsumes(bitmapZeroes));
ASSERT_FALSE(bitmapZeroes.subsumes(bitmap1));
ASSERT_FALSE(bitmapZeroes.subsumes(bitmap2));
ASSERT_FALSE(bitmapZeroes.subsumes(bitmap2Clone));
ASSERT_FALSE(bitmapZeroes.subsumes(bitmapOnes));
ASSERT_TRUE(bitmap1.subsumes(bitmapZeroes));
ASSERT_TRUE(bitmap1.subsumes(bitmap1));
ASSERT_FALSE(bitmap1.subsumes(bitmap2));
ASSERT_FALSE(bitmap1.subsumes(bitmap2Clone));
ASSERT_FALSE(bitmap1.subsumes(bitmapOnes));
ASSERT_TRUE(bitmap2.subsumes(bitmapZeroes));
ASSERT_FALSE(bitmap2.subsumes(bitmap1));
ASSERT_TRUE(bitmap2.subsumes(bitmap2));
ASSERT_TRUE(bitmap2.subsumes(bitmap2Clone));
ASSERT_FALSE(bitmap2.subsumes(bitmapOnes));
ASSERT_TRUE(bitmap2Clone.subsumes(bitmapZeroes));
ASSERT_FALSE(bitmap2Clone.subsumes(bitmap1));
ASSERT_TRUE(bitmap2Clone.subsumes(bitmap2));
ASSERT_TRUE(bitmap2Clone.subsumes(bitmap2Clone));
ASSERT_FALSE(bitmap2Clone.subsumes(bitmapOnes));
ASSERT_TRUE(bitmapOnes.subsumes(bitmapZeroes));
ASSERT_TRUE(bitmapOnes.subsumes(bitmap1));
ASSERT_TRUE(bitmapOnes.subsumes(bitmap2));
ASSERT_TRUE(bitmapOnes.subsumes(bitmap2Clone));
ASSERT_TRUE(bitmapOnes.subsumes(bitmapOnes));
ASSERT_TRUE(smallBitmapOnes.subsumes(smallBitmapOnes));
ASSERT_TRUE(smallBitmapOnes.subsumes(smallBitmapZeroes));
ASSERT_FALSE(smallBitmapZeroes.subsumes(smallBitmapOnes));
ASSERT_TRUE(smallBitmapZeroes.subsumes(smallBitmapZeroes));
}
template<typename WordType>
void testBitmapForEachSetBit()
{
DECLARE_AND_INIT_BITMAPS_FOR_TEST();
size_t count = 0;
ASSERT_TRUE(bitmapZeroes.isEmpty());
bitmapZeroes.forEachSetBit([&] (size_t i) {
constexpr bool notReached = false;
ASSERT_TRUE(notReached);
count++;
});
ASSERT_EQ(count, zeroSize);
count = 0;
bitmap1.forEachSetBit([&] (size_t i) {
ASSERT_TRUE(bitmap1.get(i));
ASSERT_EQ(bitmap1.get(i), expectedBits1[i]);
count++;
});
ASSERT_EQ(count, expectedNumberOfSetBits1);
count = 0;
ASSERT_TRUE(bitmapOnes.isFull());
bitmapOnes.forEachSetBit([&] (size_t i) {
ASSERT_TRUE(bitmapOnes.get(i));
count++;
});
ASSERT_EQ(count, size);
count = 0;
ASSERT_TRUE(smallBitmapZeroes.isEmpty());
smallBitmapZeroes.forEachSetBit([&] (size_t i) {
constexpr bool notReached = false;
ASSERT_TRUE(notReached);
count++;
});
ASSERT_EQ(count, zeroSize);
count = 0;
ASSERT_TRUE(smallBitmapOnes.isFull());
smallBitmapOnes.forEachSetBit([&] (size_t i) {
ASSERT_TRUE(smallBitmapOnes.get(i));
count++;
});
ASSERT_EQ(count, smallSize);
}
template<typename WordType>
void testBitmapFindBit()
{
DECLARE_AND_INIT_BITMAPS_FOR_TEST();
auto findExpectedBit = [=] (auto expectedBits, size_t startIndex, bool value) -> size_t {
for (auto index = startIndex; index < size; ++index) {
if (expectedBits[index] == value)
return index;
}
return startIndex;
};
for (size_t i = 1, lastIndex = 1; i < size; lastIndex = i, i += lastIndex) {
ASSERT_EQ(bitmap1.findBit(i, true), findExpectedBit(expectedBits1, i, true));
ASSERT_EQ(bitmap1.findBit(i, false), findExpectedBit(expectedBits1, i, false));
ASSERT_EQ(bitmap2.findBit(i, true), findExpectedBit(expectedBits2, i, true));
ASSERT_EQ(bitmap2.findBit(i, false), findExpectedBit(expectedBits2, i, false));
ASSERT_EQ(bitmap2.findBit(i, true), bitmap2Clone.findBit(i, true));
ASSERT_EQ(bitmap2.findBit(i, false), bitmap2Clone.findBit(i, false));
}
ASSERT_EQ(bitmapZeroes.findBit(0, false), zeroSize);
ASSERT_EQ(bitmapZeroes.findBit(10, false), static_cast<size_t>(10));
ASSERT_EQ(bitmapZeroes.findBit(size - 1, false), size-1);
ASSERT_EQ(bitmapZeroes.findBit(size, false), size);
ASSERT_EQ(bitmapZeroes.findBit(size + 1, false), size);
ASSERT_EQ(bitmapZeroes.findBit(0, true), size);
ASSERT_EQ(bitmapZeroes.findBit(10, true), size);
ASSERT_EQ(bitmapZeroes.findBit(size - 1, true), size);
ASSERT_EQ(bitmapZeroes.findBit(size, true), size);
ASSERT_EQ(bitmapZeroes.findBit(size + 1, true), size);
ASSERT_EQ(bitmapOnes.findBit(0, false), size);
ASSERT_EQ(bitmapOnes.findBit(10, false), size);
ASSERT_EQ(bitmapOnes.findBit(size - 1, false), size);
ASSERT_EQ(bitmapOnes.findBit(size, false), size);
ASSERT_EQ(bitmapOnes.findBit(size + 1, false), size);
ASSERT_EQ(bitmapOnes.findBit(0, true), zeroSize);
ASSERT_EQ(bitmapOnes.findBit(10, true), static_cast<size_t>(10));
ASSERT_EQ(bitmapOnes.findBit(size - 1, true), size-1);
ASSERT_EQ(bitmapOnes.findBit(size, true), size);
ASSERT_EQ(bitmapOnes.findBit(size + 1, true), size);
}
template<typename WordType>
void testBitmapIteration()
{
DECLARE_AND_INIT_BITMAPS_FOR_TEST();
auto computeSetBitsCount = [=] (auto& bitmap) -> size_t {
size_t count = 0;
for (auto bitIndex : bitmap) {
UNUSED_PARAM(bitIndex);
count++;
}
return count;
};
EXPECT_EQ(computeSetBitsCount(bitmapZeroes), zeroSize);
EXPECT_EQ(computeSetBitsCount(bitmap1), expectedNumberOfSetBits1);
EXPECT_EQ(computeSetBitsCount(bitmap2), expectedNumberOfSetBits2);
EXPECT_EQ(computeSetBitsCount(bitmap2Clone), expectedNumberOfSetBits2);
EXPECT_EQ(computeSetBitsCount(bitmapOnes), size);
EXPECT_EQ(computeSetBitsCount(smallBitmapZeroes), zeroSize);
EXPECT_EQ(computeSetBitsCount(smallBitmapOnes), smallSize);
auto verifySetBits = [=] (auto& bitmap, auto& expectedBits) {
for (auto bitIndex : bitmap) {
EXPECT_TRUE(bitmap.get(bitIndex));
EXPECT_EQ(bitmap.get(bitIndex), expectedBits[bitIndex]);
}
};
verifySetBits(bitmap1, expectedBits1);
verifySetBits(bitmap2, expectedBits2);
verifySetBits(bitmap2Clone, expectedBits2);
auto verifyBitsAllSet = [=] (auto& bitmap) {
size_t lastBitIndex = 0;
for (auto bitIndex : bitmap) {
EXPECT_TRUE(bitmap.get(bitIndex));
if (bitIndex)
EXPECT_EQ(bitIndex, lastBitIndex + 1);
lastBitIndex = bitIndex;
}
};
verifyBitsAllSet(bitmapOnes);
verifyBitsAllSet(smallBitmapOnes);
}
template<typename WordType>
void testBitmapMergeAndClear()
{
DECLARE_AND_INIT_BITMAPS_FOR_TEST();
Bitmap<size, WordType> temp;
Bitmap<size, WordType> savedBitmap1;
ASSERT_FALSE(bitmap2.isEmpty());
savedBitmap1.merge(bitmap1);
ASSERT_EQ(savedBitmap1, bitmap1);
ASSERT_NE(bitmap1, bitmap2);
ASSERT_NE(bitmap1, bitmap2Clone);
ASSERT_EQ(bitmap2Clone, bitmap2);
bitmap1.mergeAndClear(bitmap2Clone);
ASSERT_NE(bitmap1, bitmap2);
ASSERT_NE(bitmap1, savedBitmap1);
ASSERT_TRUE(bitmap2Clone.isEmpty());
for (size_t i = 0; i < size; ++i) {
bool expectedBit = expectedBits1[i] | expectedBits2[i];
ASSERT_EQ(bitmap1.get(i), expectedBit);
}
bitmap2Clone.merge(bitmap2); // restore bitmap2Clone
ASSERT_EQ(bitmap2Clone, bitmap2);
ASSERT_TRUE(temp.isEmpty());
temp.mergeAndClear(bitmap2Clone);
ASSERT_FALSE(temp.isEmpty());
ASSERT_EQ(temp, bitmap2);
ASSERT_TRUE(bitmap2Clone.isEmpty());
Bitmap<size, WordType> savedBitmapOnes;
savedBitmapOnes.merge(bitmapOnes);
temp.clearAll();
ASSERT_TRUE(temp.isEmpty());
ASSERT_FALSE(temp.isFull());
ASSERT_FALSE(bitmapOnes.isEmpty());
ASSERT_TRUE(bitmapOnes.isFull());
temp.mergeAndClear(bitmapOnes);
ASSERT_FALSE(temp.isEmpty());
ASSERT_TRUE(temp.isFull());
ASSERT_TRUE(bitmapOnes.isEmpty());
ASSERT_FALSE(bitmapOnes.isFull());
bitmap2Clone.merge(bitmap2); // restore bitmap2Clone
ASSERT_EQ(bitmap2Clone, bitmap2);
bitmapOnes.merge(savedBitmapOnes); // restore bitmapOnes
ASSERT_TRUE(bitmapOnes.isFull());
ASSERT_TRUE(temp.isFull());
temp.mergeAndClear(bitmap2Clone);
ASSERT_TRUE(temp.isFull());
ASSERT_EQ(temp, bitmapOnes);
ASSERT_TRUE(bitmap2Clone.isEmpty());
Bitmap<smallSize, WordType> smallTemp;
smallTemp.merge(smallBitmapOnes);
ASSERT_TRUE(smallTemp.isFull());
ASSERT_TRUE(smallBitmapZeroes.isEmpty());
smallTemp.mergeAndClear(smallBitmapZeroes);
ASSERT_TRUE(smallTemp.isFull());
ASSERT_FALSE(smallTemp.isEmpty());
ASSERT_TRUE(smallBitmapZeroes.isEmpty());
smallTemp.clearAll();
ASSERT_TRUE(smallBitmapOnes.isFull());
ASSERT_TRUE(smallTemp.isEmpty());
smallTemp.mergeAndClear(smallBitmapOnes);
ASSERT_TRUE(smallTemp.isFull());
ASSERT_TRUE(smallBitmapOnes.isEmpty());
}
template<typename WordType>
void testBitmapSetAndClear()
{
DECLARE_AND_INIT_BITMAPS_FOR_TEST();
Bitmap<size, WordType> temp;
Bitmap<size, WordType> savedBitmap1;
ASSERT_FALSE(bitmap2.isEmpty());
savedBitmap1.merge(bitmap1);
ASSERT_EQ(savedBitmap1, bitmap1);
ASSERT_NE(bitmap1, bitmap2);
ASSERT_NE(bitmap1, bitmap2Clone);
ASSERT_EQ(bitmap2Clone, bitmap2);
bitmap1.setAndClear(bitmap2Clone);
ASSERT_EQ(bitmap1, bitmap2);
ASSERT_NE(bitmap1, savedBitmap1);
ASSERT_TRUE(bitmap2Clone.isEmpty());
bitmap2Clone.merge(bitmap2); // restore bitmap2Clone
ASSERT_EQ(bitmap2Clone, bitmap2);
ASSERT_TRUE(temp.isEmpty());
temp.setAndClear(bitmap2Clone);
ASSERT_FALSE(temp.isEmpty());
ASSERT_EQ(temp, bitmap2);
ASSERT_TRUE(bitmap2Clone.isEmpty());
temp.clearAll();
ASSERT_TRUE(temp.isEmpty());
ASSERT_FALSE(temp.isFull());
ASSERT_FALSE(bitmapOnes.isEmpty());
ASSERT_TRUE(bitmapOnes.isFull());
temp.setAndClear(bitmapOnes);
ASSERT_FALSE(temp.isEmpty());
ASSERT_TRUE(temp.isFull());
ASSERT_TRUE(bitmapOnes.isEmpty());
ASSERT_FALSE(bitmapOnes.isFull());
bitmap2Clone.merge(bitmap2); // restore bitmap2Clone
ASSERT_EQ(bitmap2Clone, bitmap2);
ASSERT_TRUE(temp.isFull());
temp.setAndClear(bitmap2Clone);
ASSERT_FALSE(temp.isFull());
ASSERT_EQ(temp, bitmap2);
ASSERT_TRUE(bitmap2Clone.isEmpty());
Bitmap<smallSize, WordType> smallTemp;
smallTemp.merge(smallBitmapOnes);
ASSERT_TRUE(smallTemp.isFull());
ASSERT_TRUE(smallBitmapZeroes.isEmpty());
smallTemp.setAndClear(smallBitmapZeroes);
ASSERT_TRUE(smallTemp.isEmpty());
ASSERT_TRUE(smallBitmapZeroes.isEmpty());
ASSERT_TRUE(smallBitmapOnes.isFull());
ASSERT_TRUE(smallTemp.isEmpty());
smallTemp.setAndClear(smallBitmapOnes);
ASSERT_TRUE(smallTemp.isFull());
ASSERT_TRUE(smallBitmapOnes.isEmpty());
}
template<typename Bitmap>
void testBitmapSetEachNthBitImpl(size_t size, size_t wordSize, const Bitmap& zeroes, const Bitmap& ones)
{
Bitmap temp;
EXPECT_TRUE(temp == zeroes);
temp.setEachNthBit(1);
EXPECT_TRUE(temp == ones);
size_t nValues[] = { 1, 2, wordSize / 2, wordSize - 1, wordSize, size / 2, size - 1, size };
size_t nValuesCount = sizeof(nValues) / sizeof(nValues[0]);
size_t startEndValues[] = { 0, 1, 2, wordSize / 2, wordSize - 1, wordSize, size / 2, size - 1, size };
constexpr size_t numberOfStartEndValues = sizeof(startEndValues) / sizeof(startEndValues[0]);
for (size_t start = 0; start < numberOfStartEndValues; ++start) {
for (size_t end = start; end < numberOfStartEndValues; ++end) {
size_t startIndex = startEndValues[start];
size_t endIndex = startEndValues[end];
if (endIndex < startIndex)
continue;
if (startIndex > size)
continue;
if (endIndex > size)
continue;
for (size_t j = 0; j < nValuesCount; ++j) {
size_t n = nValues[j];
temp.clearAll();
temp.setEachNthBit(n, startIndex, endIndex);
for (size_t i = 0; i < startIndex; ++i)
EXPECT_FALSE(temp.get(i));
size_t count = 0;
for (size_t i = startIndex; i < endIndex; ++i) {
bool expected = !count;
EXPECT_TRUE(temp.get(i) == expected);
count++;
count = count % n;
}
for (size_t i = endIndex; i < size; ++i)
EXPECT_FALSE(temp.get(i));
}
}
}
}
template<typename WordType>
void testBitmapSetEachNthBit()
{
DECLARE_AND_INIT_BITMAPS_FOR_TEST();
constexpr size_t wordSize = sizeof(WordType) * 8;
testBitmapSetEachNthBitImpl(size, wordSize, bitmapZeroes, bitmapOnes);
testBitmapSetEachNthBitImpl(smallSize, wordSize, smallBitmapZeroes, smallBitmapOnes);
}
template<typename WordType>
void testBitmapOperatorEqual()
{
DECLARE_AND_INIT_BITMAPS_FOR_TEST();
EXPECT_TRUE(bitmapZeroes == bitmapZeroes);
EXPECT_FALSE(bitmapZeroes == bitmap1);
EXPECT_TRUE(bitmap1 == bitmap1);
EXPECT_FALSE(bitmap1 == bitmap2);
EXPECT_FALSE(bitmap1 == bitmap2Clone);
EXPECT_TRUE(bitmap2 == bitmap2Clone);
EXPECT_FALSE(bitmapOnes == bitmap1);
EXPECT_FALSE(smallBitmapZeroes == smallBitmapOnes);
}
template<typename WordType>
void testBitmapOperatorNotEqual()
{
DECLARE_AND_INIT_BITMAPS_FOR_TEST();
EXPECT_FALSE(bitmapZeroes != bitmapZeroes);
EXPECT_TRUE(bitmapZeroes != bitmap1);
EXPECT_FALSE(bitmap1 != bitmap1);
EXPECT_TRUE(bitmap1 != bitmap2);
EXPECT_TRUE(bitmap1 != bitmap2Clone);
EXPECT_FALSE(bitmap2 != bitmap2Clone);
EXPECT_TRUE(bitmapOnes != bitmap1);
EXPECT_TRUE(smallBitmapZeroes != smallBitmapOnes);
}
template<typename Bitmap>
void testBitmapOperatorAssignmentImpl(const Bitmap& bitmap1, const Bitmap& bitmap2, const Bitmap& zeroes, const Bitmap& ones)
{
Bitmap temp;
Bitmap temp2;
EXPECT_TRUE(temp.isEmpty());
EXPECT_TRUE(temp2.isEmpty());
EXPECT_TRUE(temp == zeroes);
EXPECT_TRUE(temp != bitmap1);
temp = bitmap1;
EXPECT_TRUE(temp != zeroes);
EXPECT_TRUE(temp == bitmap1);
EXPECT_TRUE(temp != bitmap2);
temp = bitmap2;
EXPECT_TRUE(temp == bitmap2);
EXPECT_TRUE(temp != bitmap1);
temp.clearAll();
temp2.clearAll();
for (size_t i = 0; i < bitmap1.size(); ++i)
temp.set(i, bitmap1.get(i));
EXPECT_TRUE(temp == bitmap1);
EXPECT_TRUE(temp2.isEmpty());
EXPECT_TRUE(temp2 != bitmap1);
temp2 = temp;
EXPECT_TRUE(temp2 == bitmap1);
}
template<typename WordType>
void testBitmapOperatorAssignment()
{
DECLARE_AND_INIT_BITMAPS_FOR_TEST();
testBitmapOperatorAssignmentImpl(bitmap1, bitmap2, bitmapZeroes, bitmapOnes);
testBitmapOperatorAssignmentImpl(smallBitmap1, smallBitmap2, smallBitmapZeroes, smallBitmapOnes);
}
template<typename Bitmap>
void testBitmapOperatorBitOrAssignmentImpl(size_t size, const Bitmap& bitmap1, const Bitmap& bitmap2, const Bitmap& zeroes, const Bitmap& ones)
{
Bitmap temp;
Bitmap temp1;
// 0 | 0
EXPECT_TRUE(temp == zeroes);
EXPECT_TRUE(temp != ones);
temp |= zeroes;
EXPECT_TRUE(temp == zeroes);
EXPECT_TRUE(temp != ones);
// 0 | 1
EXPECT_TRUE(temp == zeroes);
EXPECT_TRUE(temp != ones);
temp |= ones;
EXPECT_TRUE(temp != zeroes);
EXPECT_TRUE(temp == ones);
// 1 | 0
EXPECT_TRUE(temp != zeroes);
EXPECT_TRUE(temp == ones);
temp |= zeroes;
EXPECT_TRUE(temp != zeroes);
EXPECT_TRUE(temp == ones);
// 1 | 1
EXPECT_TRUE(temp != zeroes);
EXPECT_TRUE(temp == ones);
temp |= ones;
EXPECT_TRUE(temp != zeroes);
EXPECT_TRUE(temp == ones);
temp = zeroes;
EXPECT_TRUE(temp.isEmpty());
EXPECT_TRUE(temp != bitmap1);
temp |= bitmap1;
EXPECT_TRUE(temp == bitmap1);
temp |= bitmap2;
for (size_t i = 0; i < size; ++i)
EXPECT_EQ(temp.get(i), bitmap1.get(i) | bitmap2.get(i));
temp1 = temp;
EXPECT_TRUE(temp1 == temp);
temp |= zeroes;
EXPECT_TRUE(temp == temp1);
EXPECT_TRUE(temp != zeroes);
temp |= ones;
EXPECT_TRUE(temp != temp1);
EXPECT_TRUE(temp == ones);
}
template<typename WordType>
void testBitmapOperatorBitOrAssignment()
{
DECLARE_AND_INIT_BITMAPS_FOR_TEST();
testBitmapOperatorBitOrAssignmentImpl(size, bitmap1, bitmap2, bitmapZeroes, bitmapOnes);
testBitmapOperatorBitOrAssignmentImpl(smallSize, smallBitmap1, smallBitmap2, smallBitmapZeroes, smallBitmapOnes);
}
template<typename Bitmap>
void testBitmapOperatorBitAndAssignmentImpl(size_t size, const Bitmap& bitmap1, const Bitmap& bitmap2, const Bitmap& zeroes, const Bitmap& ones)
{
Bitmap temp;
Bitmap temp1;
// 0 & 0
temp = zeroes;
EXPECT_TRUE(temp == zeroes);
EXPECT_TRUE(temp != ones);
temp &= zeroes;
EXPECT_TRUE(temp == zeroes);
EXPECT_TRUE(temp != ones);
// 0 & 1
temp = zeroes;
EXPECT_TRUE(temp == zeroes);
EXPECT_TRUE(temp != ones);
temp &= ones;
EXPECT_TRUE(temp == zeroes);
EXPECT_TRUE(temp != ones);
// 1 & 0
temp = ones;
EXPECT_TRUE(temp != zeroes);
EXPECT_TRUE(temp == ones);
temp &= zeroes;
EXPECT_TRUE(temp == zeroes);
EXPECT_TRUE(temp != ones);
// 1 & 1
temp = ones;
EXPECT_TRUE(temp != zeroes);
EXPECT_TRUE(temp == ones);
temp &= ones;
EXPECT_TRUE(temp != zeroes);
EXPECT_TRUE(temp == ones);
temp = ones;
EXPECT_TRUE(temp == ones);
EXPECT_TRUE(temp != bitmap1);
temp &= bitmap1;
EXPECT_TRUE(temp == bitmap1);
temp &= bitmap2;
for (size_t i = 0; i < size; ++i)
EXPECT_EQ(temp.get(i), bitmap1.get(i) & bitmap2.get(i));
EXPECT_TRUE(!temp.isEmpty());
temp1 = temp;
EXPECT_TRUE(temp1 == temp);
temp &= zeroes;
EXPECT_TRUE(temp != temp1);
EXPECT_TRUE(temp == zeroes);
temp = temp1;
temp &= ones;
EXPECT_TRUE(temp == temp1);
EXPECT_TRUE(temp != ones);
}
template<typename WordType>
void testBitmapOperatorBitAndAssignment()
{
DECLARE_AND_INIT_BITMAPS_FOR_TEST();
testBitmapOperatorBitAndAssignmentImpl(size, bitmap1, bitmap2, bitmapZeroes, bitmapOnes);
testBitmapOperatorBitAndAssignmentImpl(smallSize, smallBitmap1, smallBitmap2, smallBitmapZeroes, smallBitmapOnes);
}
template<typename Bitmap>
void testBitmapOperatorBitXorAssignmentImpl(size_t size, const Bitmap& bitmap1, const Bitmap& bitmap2, const Bitmap& zeroes, const Bitmap& ones)
{
Bitmap temp;
Bitmap temp1;
// 0 ^ 0
temp = zeroes;
EXPECT_TRUE(temp == zeroes);
EXPECT_TRUE(temp != ones);
temp ^= zeroes;
EXPECT_TRUE(temp == zeroes);
EXPECT_TRUE(temp != ones);
// 0 ^ 1
temp = zeroes;
EXPECT_TRUE(temp == zeroes);
EXPECT_TRUE(temp != ones);
temp ^= ones;
EXPECT_TRUE(temp != zeroes);
EXPECT_TRUE(temp == ones);
// 1 ^ 0
temp = ones;
EXPECT_TRUE(temp != zeroes);
EXPECT_TRUE(temp == ones);
temp ^= zeroes;
EXPECT_TRUE(temp != zeroes);
EXPECT_TRUE(temp == ones);
// 1 ^ 1
temp = ones;
EXPECT_TRUE(temp != zeroes);
EXPECT_TRUE(temp == ones);
temp ^= ones;
EXPECT_TRUE(temp == zeroes);
EXPECT_TRUE(temp != ones);
temp.clearAll();
EXPECT_TRUE(temp.isEmpty());
EXPECT_TRUE(temp != bitmap1);
temp ^= bitmap1;
EXPECT_TRUE(temp == bitmap1);
temp ^= bitmap2;
for (size_t i = 0; i < size; ++i)
EXPECT_EQ(temp.get(i), bitmap1.get(i) ^ bitmap2.get(i));
temp1 = temp;
EXPECT_TRUE(temp1 == temp);
temp ^= zeroes;
EXPECT_TRUE(temp == temp1);
EXPECT_TRUE(temp != zeroes);
temp ^= ones;
EXPECT_TRUE(temp != temp1);
EXPECT_TRUE(temp != ones);
temp1.invert();
EXPECT_TRUE(temp == temp1);
EXPECT_TRUE(temp != ones);
}
template<typename WordType>
void testBitmapOperatorBitXorAssignment()
{
DECLARE_AND_INIT_BITMAPS_FOR_TEST();
testBitmapOperatorBitXorAssignmentImpl(size, bitmap1, bitmap2, bitmapZeroes, bitmapOnes);
testBitmapOperatorBitXorAssignmentImpl(smallSize, smallBitmap1, smallBitmap2, smallBitmapZeroes, smallBitmapOnes);
}
template<typename WordType>
void testBitmapHash()
{
DECLARE_AND_INIT_BITMAPS_FOR_TEST();
constexpr unsigned wordSize = sizeof(WordType) * 8;
constexpr size_t words = (size + wordSize - 1) / wordSize;
auto expectedBitmapZeroesHash = [=] () -> unsigned {
unsigned result = 0;
WordType zeroWord = 0;
for (size_t i = 0; i < words; ++i)
result ^= IntHash<WordType>::hash(zeroWord);
return result;
};
auto expectedBitmapOnesHash = [=] () -> unsigned {
unsigned result = 0;
WordType filledWord = static_cast<WordType>(-1);
for (size_t i = 0; i < words; ++i)
result ^= IntHash<WordType>::hash(filledWord);
return result;
};
ASSERT_EQ(bitmapZeroes.hash(), expectedBitmapZeroesHash());
ASSERT_EQ(bitmapOnes.hash(), expectedBitmapOnesHash());
auto expectedHash = [=] (auto expectedBits, size_t size) {
unsigned result = 0;
for (size_t i = 0; i < size;) {
WordType word = 0;
for (size_t j = 0; j < wordSize && i < size; ++i, ++j)
word |= static_cast<WordType>(!!expectedBits[i]) << j;
result ^= IntHash<WordType>::hash(word);
}
return result;
};
ASSERT_EQ(bitmap1.hash(), expectedHash(expectedBits1, size));
ASSERT_EQ(bitmap2.hash(), expectedHash(expectedBits2, size));
static constexpr bool expectedSmallBits[smallSize] = {
true, false, false, true, false, false, false, true,
true,
};
Bitmap<smallSize, WordType> temp1;
Bitmap<smallSize, WordType> temp2;
auto initTemp = [&] (auto& bitmap) {
for (size_t i = 0; i < smallSize; ++i)
bitmap.set(i, expectedSmallBits[i]);
};
initTemp(temp1);
ASSERT_EQ(temp1.hash(), expectedHash(expectedSmallBits, smallSize));
temp2.invert();
initTemp(temp2);
ASSERT_EQ(temp2.hash(), expectedHash(expectedSmallBits, smallSize));
ASSERT_EQ(temp2.hash(), temp1.hash());
}
TEST(WTF_Bitmap, Size_uint32_t) { testBitmapSize<uint32_t>(); }
TEST(WTF_Bitmap, ConstructedEmpty_uint32_t) { testBitmapConstructedEmpty<uint32_t>(); }
TEST(WTF_Bitmap, SetGet_uint32_t) { testBitmapSetGet<uint32_t>(); }
TEST(WTF_Bitmap, TestAndSet_uint32_t) { testBitmapTestAndSet<uint32_t>(); }
TEST(WTF_Bitmap, TestAndClear_uint32_t) { testBitmapTestAndClear<uint32_t>(); }
TEST(WTF_Bitmap, ConcurrentTestAndSet_uint32_t) { testBitmapConcurrentTestAndSet<uint32_t>(); }
TEST(WTF_Bitmap, ConcurrentTestAndClear_uint32_t) { testBitmapConcurrentTestAndClear<uint32_t>(); }
TEST(WTF_Bitmap, Clear_uint32_t) { testBitmapClear<uint32_t>(); }
TEST(WTF_Bitmap, ClearAll_uint32_t) { testBitmapClearAll<uint32_t>(); }
TEST(WTF_Bitmap, Invert_uint32_t) { testBitmapInvert<uint32_t>(); }
TEST(WTF_Bitmap, FindRunOfZeros_uint32_t) { testBitmapFindRunOfZeros<uint32_t>(); }
TEST(WTF_Bitmap, Count_uint32_t) { testBitmapCount<uint32_t>(); }
TEST(WTF_Bitmap, IsEmpty_uint32_t) { testBitmapIsEmpty<uint32_t>(); }
TEST(WTF_Bitmap, IsFull_uint32_t) { testBitmapIsFull<uint32_t>(); }
TEST(WTF_Bitmap, Merge_uint32_t) { testBitmapMerge<uint32_t>(); }
TEST(WTF_Bitmap, Filter_uint32_t) { testBitmapFilter<uint32_t>(); }
TEST(WTF_Bitmap, Exclude_uint32_t) { testBitmapExclude<uint32_t>(); }
TEST(WTF_Bitmap, ConcurrentFilter_uint32_t) { testBitmapConcurrentFilter<uint32_t>(); }
TEST(WTF_Bitmap, Subsumes_uint32_t) { testBitmapSubsumes<uint32_t>(); }
TEST(WTF_Bitmap, ForEachSetBit_uint32_t) { testBitmapForEachSetBit<uint32_t>(); }
TEST(WTF_Bitmap, FindBit_uint32_t) { testBitmapFindBit<uint32_t>(); }
TEST(WTF_Bitmap, Iteration_uint32_t) { testBitmapIteration<uint32_t>(); }
TEST(WTF_Bitmap, MergeAndClear_uint32_t) { testBitmapMergeAndClear<uint32_t>(); }
TEST(WTF_Bitmap, SetAndClear_uint32_t) { testBitmapSetAndClear<uint32_t>(); }
TEST(WTF_Bitmap, SetEachNthBit_uint32_t) { testBitmapSetEachNthBit<uint32_t>(); }
TEST(WTF_Bitmap, OperatorEqualAccess_uint32_t) { testBitmapOperatorEqual<uint32_t>(); }
TEST(WTF_Bitmap, OperatorNotEqualAccess_uint32_t) { testBitmapOperatorNotEqual<uint32_t>(); }
TEST(WTF_Bitmap, OperatorAssignment_uint32_t) { testBitmapOperatorAssignment<uint32_t>(); }
TEST(WTF_Bitmap, OperatorBitOrAssignment_uint32_t) { testBitmapOperatorBitOrAssignment<uint32_t>(); }
TEST(WTF_Bitmap, OperatorBitAndAssignment_uint32_t) { testBitmapOperatorBitAndAssignment<uint32_t>(); }
TEST(WTF_Bitmap, OperatorBitXorAssignment_uint32_t) { testBitmapOperatorBitXorAssignment<uint32_t>(); }
TEST(WTF_Bitmap, Hash_uint32_t) { testBitmapHash<uint32_t>(); }
#if CPU(REGISTER64)
TEST(WTF_Bitmap, Size_uint64_t) { testBitmapSize<uint64_t>(); }
TEST(WTF_Bitmap, ConstructedEmpty_uint64_t) { testBitmapConstructedEmpty<uint64_t>(); }
TEST(WTF_Bitmap, SetGet_uint64_t) { testBitmapSetGet<uint64_t>(); }
TEST(WTF_Bitmap, TestAndSet_uint64_t) { testBitmapTestAndSet<uint64_t>(); }
TEST(WTF_Bitmap, TestAndClear_uint64_t) { testBitmapTestAndClear<uint64_t>(); }
TEST(WTF_Bitmap, ConcurrentTestAndSet_uint64_t) { testBitmapConcurrentTestAndSet<uint64_t>(); }
TEST(WTF_Bitmap, ConcurrentTestAndClear_uint64_t) { testBitmapConcurrentTestAndClear<uint64_t>(); }
TEST(WTF_Bitmap, Clear_uint64_t) { testBitmapClear<uint64_t>(); }
TEST(WTF_Bitmap, ClearAll_uint64_t) { testBitmapClearAll<uint64_t>(); }
TEST(WTF_Bitmap, Invert_uint64_t) { testBitmapInvert<uint64_t>(); }
TEST(WTF_Bitmap, FindRunOfZeros_uint64_t) { testBitmapFindRunOfZeros<uint64_t>(); }
TEST(WTF_Bitmap, Count_uint64_t) { testBitmapCount<uint64_t>(); }
TEST(WTF_Bitmap, IsEmpty_uint64_t) { testBitmapIsEmpty<uint64_t>(); }
TEST(WTF_Bitmap, IsFull_uint64_t) { testBitmapIsFull<uint64_t>(); }
TEST(WTF_Bitmap, Merge_uint64_t) { testBitmapMerge<uint64_t>(); }
TEST(WTF_Bitmap, Filter_uint64_t) { testBitmapFilter<uint64_t>(); }
TEST(WTF_Bitmap, Exclude_uint64_t) { testBitmapExclude<uint64_t>(); }
TEST(WTF_Bitmap, ConcurrentFilter_uint64_t) { testBitmapConcurrentFilter<uint64_t>(); }
TEST(WTF_Bitmap, Subsumes_uint64_t) { testBitmapSubsumes<uint64_t>(); }
TEST(WTF_Bitmap, ForEachSetBit_uint64_t) { testBitmapForEachSetBit<uint64_t>(); }
TEST(WTF_Bitmap, FindBit_uint64_t) { testBitmapFindBit<uint64_t>(); }
TEST(WTF_Bitmap, Iteration_uint64_t) { testBitmapIteration<uint64_t>(); }
TEST(WTF_Bitmap, MergeAndClear_uint64_t) { testBitmapMergeAndClear<uint64_t>(); }
TEST(WTF_Bitmap, SetAndClear_uint64_t) { testBitmapSetAndClear<uint64_t>(); }
TEST(WTF_Bitmap, SetEachNthBit_uint64_t) { testBitmapSetEachNthBit<uint64_t>(); }
TEST(WTF_Bitmap, OperatorEqualAccess_uint64_t) { testBitmapOperatorEqual<uint64_t>(); }
TEST(WTF_Bitmap, OperatorNotEqualAccess_uint64_t) { testBitmapOperatorNotEqual<uint64_t>(); }
TEST(WTF_Bitmap, OperatorAssignment_uint64_t) { testBitmapOperatorAssignment<uint64_t>(); }
TEST(WTF_Bitmap, OperatorBitOrAssignment_uint64_t) { testBitmapOperatorBitOrAssignment<uint64_t>(); }
TEST(WTF_Bitmap, OperatorBitAndAssignment_uint64_t) { testBitmapOperatorBitAndAssignment<uint64_t>(); }
TEST(WTF_Bitmap, OperatorBitXorAssignment_uint64_t) { testBitmapOperatorBitXorAssignment<uint64_t>(); }
TEST(WTF_Bitmap, Hash_uint64_t) { testBitmapHash<uint64_t>(); }
#endif // CPU(REGISTER64)
} // namespace TestWebKitAPI