testSparseBitmap.cpp (4749B)
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 */ 4 /* This Source Code Form is subject to the terms of the Mozilla Public 5 * License, v. 2.0. If a copy of the MPL was not distributed with this 6 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ 7 8 #include "mozilla/PodOperations.h" 9 10 #include "ds/Bitmap.h" 11 12 #include "jsapi-tests/tests.h" 13 14 using namespace js; 15 16 BEGIN_TEST(testSparseBitmapBasics) { 17 SparseBitmap bitmap; 18 19 // Test bits in first block are initially zero. 20 for (size_t i = 0; i < 100; i++) { 21 CHECK(!bitmap.getBit(i)); 22 } 23 24 // Test bits in different blocks are initially zero. 25 for (size_t i = 0; i < 100; i++) { 26 CHECK(!bitmap.getBit(i * 1000)); 27 } 28 29 // Set some bits in the first block and check they are set. 30 for (size_t i = 0; i < 100; i += 2) { 31 CHECK(bitmap.setBit(i)); 32 } 33 for (size_t i = 0; i < 100; i++) { 34 CHECK(bitmap.getBit(i) == ((i % 2) == 0)); 35 } 36 37 // Set some bits in different blocks and check they are set. 38 for (size_t i = 0; i < 100; i += 2) { 39 CHECK(bitmap.setBit(i * 1000)); 40 } 41 for (size_t i = 0; i < 100; i++) { 42 CHECK(bitmap.getBit(i * 1000) == ((i % 2) == 0)); 43 } 44 45 // Create another bitmap with different bits set. 46 SparseBitmap other; 47 for (size_t i = 1; i < 100; i += 2) { 48 CHECK(other.setBit(i * 1000)); 49 } 50 for (size_t i = 0; i < 100; i++) { 51 CHECK(other.getBit(i * 1000) == ((i % 2) != 0)); 52 } 53 54 // OR some bits into this bitmap and check the result. 55 CHECK(bitmap.bitwiseOrWith(other)); 56 for (size_t i = 0; i < 100; i++) { 57 CHECK(bitmap.getBit(i * 1000)); 58 } 59 60 // AND some bits into this bitmap and check the result. 61 DenseBitmap dense; 62 size_t wordCount = (100 * 1000) / JS_BITS_PER_WORD + 1; 63 CHECK(dense.ensureSpace(wordCount)); 64 other.bitwiseOrInto(dense); 65 bitmap.bitwiseAndWith(dense); 66 for (size_t i = 0; i < 100; i++) { 67 CHECK(bitmap.getBit(i * 1000) == ((i % 2) != 0)); 68 } 69 70 return true; 71 } 72 END_TEST(testSparseBitmapBasics) 73 74 BEGIN_TEST(testSparseBitmapExternalOR) { 75 // Testing ORing data into an external array. 76 77 const size_t wordCount = 10; 78 79 // Create a bitmap with one bit set per word so we can tell them apart. 80 SparseBitmap bitmap; 81 for (size_t i = 0; i < wordCount; i++) { 82 CHECK(bitmap.setBit(i * JS_BITS_PER_WORD + i)); 83 } 84 85 // Copy a single word. 86 uintptr_t target[wordCount]; 87 mozilla::PodArrayZero(target); 88 bitmap.bitwiseOrRangeInto(0, 1, target); 89 CHECK(target[0] == 1u << 0); 90 CHECK(target[1] == 0); 91 92 // Copy a word at an offset. 93 mozilla::PodArrayZero(target); 94 bitmap.bitwiseOrRangeInto(1, 1, target); 95 CHECK(target[0] == 1u << 1); 96 CHECK(target[1] == 0); 97 98 // Check data is ORed with original target contents. 99 mozilla::PodArrayZero(target); 100 bitmap.bitwiseOrRangeInto(0, 1, target); 101 bitmap.bitwiseOrRangeInto(1, 1, target); 102 CHECK(target[0] == ((1u << 0) | (1u << 1))); 103 104 // Copy multiple words at an offset. 105 mozilla::PodArrayZero(target); 106 bitmap.bitwiseOrRangeInto(2, wordCount - 2, target); 107 for (size_t i = 0; i < wordCount - 2; i++) { 108 CHECK(target[i] == (1u << (i + 2))); 109 } 110 CHECK(target[wordCount - 1] == 0); 111 112 return true; 113 } 114 END_TEST(testSparseBitmapExternalOR) 115 116 BEGIN_TEST(testSparseBitmapExternalAND) { 117 // Testing ANDing data from an external array. 118 119 const size_t wordCount = 4; 120 121 // Create a bitmap with two bits set per word based on the word index. 122 SparseBitmap bitmap; 123 for (size_t i = 0; i < wordCount; i++) { 124 CHECK(bitmap.setBit(i * JS_BITS_PER_WORD + i)); 125 CHECK(bitmap.setBit(i * JS_BITS_PER_WORD + i + 1)); 126 } 127 128 // Update a single word, clearing one of the bits. 129 uintptr_t source[wordCount]; 130 CHECK(bitmap.getBit(0)); 131 CHECK(bitmap.getBit(1)); 132 source[0] = ~(1 << 1); 133 bitmap.bitwiseAndRangeWith(0, 1, source); 134 CHECK(bitmap.getBit(0)); 135 CHECK(!bitmap.getBit(1)); 136 137 // Update a word at an offset. 138 CHECK(bitmap.getBit(JS_BITS_PER_WORD + 1)); 139 CHECK(bitmap.getBit(JS_BITS_PER_WORD + 2)); 140 source[0] = ~(1 << 2); 141 bitmap.bitwiseAndRangeWith(1, 1, source); 142 CHECK(bitmap.getBit(JS_BITS_PER_WORD + 1)); 143 CHECK(!bitmap.getBit(JS_BITS_PER_WORD + 2)); 144 145 // Update multiple words at an offset. 146 CHECK(bitmap.getBit(JS_BITS_PER_WORD * 2 + 2)); 147 CHECK(bitmap.getBit(JS_BITS_PER_WORD * 2 + 3)); 148 CHECK(bitmap.getBit(JS_BITS_PER_WORD * 3 + 3)); 149 CHECK(bitmap.getBit(JS_BITS_PER_WORD * 3 + 4)); 150 source[0] = ~(1 << 3); 151 source[1] = ~(1 << 4); 152 bitmap.bitwiseAndRangeWith(2, 2, source); 153 CHECK(bitmap.getBit(JS_BITS_PER_WORD * 2 + 2)); 154 CHECK(!bitmap.getBit(JS_BITS_PER_WORD * 2 + 3)); 155 CHECK(bitmap.getBit(JS_BITS_PER_WORD * 3 + 3)); 156 CHECK(!bitmap.getBit(JS_BITS_PER_WORD * 3 + 4)); 157 158 return true; 159 } 160 END_TEST(testSparseBitmapExternalAND)