| /* Licensed to the Apache Software Foundation (ASF) under one or more |
| * contributor license agreements. See the NOTICE file distributed with |
| * this work for additional information regarding copyright ownership. |
| * The ASF licenses this file to You under the Apache License, Version 2.0 |
| * (the "License"); you may not use this file except in compliance with |
| * the License. You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| */ |
| |
| #define C_TESTLUCY_TESTBITVECTOR |
| #define TESTLUCY_USE_SHORT_NAMES |
| #include "Lucy/Util/ToolSet.h" |
| |
| #include "Clownfish/TestHarness/TestBatchRunner.h" |
| #include "Clownfish/TestHarness/TestUtils.h" |
| #include "Lucy/Test.h" |
| #include "Lucy/Test/TestUtils.h" |
| #include "Lucy/Test/Object/TestBitVector.h" |
| |
| #include <stdlib.h> |
| |
| TestBitVector* |
| TestBitVector_new() { |
| return (TestBitVector*)Class_Make_Obj(TESTBITVECTOR); |
| } |
| |
| static void |
| test_Set_and_Get(TestBatchRunner *runner) { |
| const size_t three = 3; |
| const size_t seventeen = 17; |
| BitVector *bit_vec = BitVec_new(8); |
| |
| BitVec_Set(bit_vec, three); |
| TEST_TRUE(runner, BitVec_Get_Capacity(bit_vec) < seventeen, |
| "set below cap"); |
| BitVec_Set(bit_vec, seventeen); |
| TEST_TRUE(runner, BitVec_Get_Capacity(bit_vec) > seventeen, |
| "set above cap causes BitVector to grow"); |
| |
| size_t i, max; |
| for (i = 0, max = BitVec_Get_Capacity(bit_vec); i < max; i++) { |
| if (i == three || i == seventeen) { |
| TEST_TRUE(runner, BitVec_Get(bit_vec, i), "set/get %u", (unsigned)i); |
| } |
| else { |
| TEST_FALSE(runner, BitVec_Get(bit_vec, i), "get %u", (unsigned)i); |
| } |
| } |
| TEST_FALSE(runner, BitVec_Get(bit_vec, i), "out of range get"); |
| |
| DECREF(bit_vec); |
| } |
| |
| static void |
| test_Flip(TestBatchRunner *runner) { |
| BitVector *bit_vec = BitVec_new(0); |
| |
| unsigned i; |
| for (i = 0; i <= 20; i++) { BitVec_Flip(bit_vec, i); } |
| for (i = 0; i <= 20; i++) { |
| TEST_TRUE(runner, BitVec_Get(bit_vec, i), "flip on %u", i); |
| } |
| TEST_FALSE(runner, BitVec_Get(bit_vec, i), "no flip %u", i); |
| for (i = 0; i <= 20; i++) { BitVec_Flip(bit_vec, i); } |
| for (i = 0; i <= 20; i++) { |
| TEST_FALSE(runner, BitVec_Get(bit_vec, i), "flip off %u", i); |
| } |
| TEST_FALSE(runner, BitVec_Get(bit_vec, 21), "still no flip %u", i); |
| |
| DECREF(bit_vec); |
| } |
| |
| static void |
| test_Flip_Block_ascending(TestBatchRunner *runner) { |
| BitVector *bit_vec = BitVec_new(0); |
| |
| for (unsigned i = 0; i <= 20; i++) { |
| BitVec_Flip_Block(bit_vec, i, 21 - i); |
| } |
| |
| for (unsigned i = 0; i <= 20; i++) { |
| if (i % 2 == 0) { |
| TEST_TRUE(runner, BitVec_Get(bit_vec, i), |
| "Flip_Block ascending %u", i); |
| } |
| else { |
| TEST_FALSE(runner, BitVec_Get(bit_vec, i), |
| "Flip_Block ascending %u", i); |
| } |
| } |
| |
| DECREF(bit_vec); |
| } |
| |
| static void |
| test_Flip_Block_descending(TestBatchRunner *runner) { |
| BitVector *bit_vec = BitVec_new(0); |
| |
| for (int i = 19; i >= 0; i--) { |
| BitVec_Flip_Block(bit_vec, 1, (size_t)i); |
| } |
| |
| for (unsigned i = 0; i <= 20; i++) { |
| if (i % 2) { |
| TEST_TRUE(runner, BitVec_Get(bit_vec, i), |
| "Flip_Block descending %u", i); |
| } |
| else { |
| TEST_FALSE(runner, BitVec_Get(bit_vec, i), |
| "Flip_Block descending %u", i); |
| } |
| } |
| |
| DECREF(bit_vec); |
| } |
| |
| static void |
| test_Flip_Block_bulk(TestBatchRunner *runner) { |
| for (unsigned offset = 0; offset <= 17; offset++) { |
| for (unsigned len = 0; len <= 17; len++) { |
| int upper = (int)offset + (int)len - 1; |
| BitVector *bit_vec = BitVec_new(0); |
| |
| BitVec_Flip_Block(bit_vec, offset, len); |
| unsigned i; |
| for (i = 0; i <= 17; i++) { |
| if (i >= offset && (int)i <= upper) { |
| if (!BitVec_Get(bit_vec, i)) { break; } |
| } |
| else { |
| if (BitVec_Get(bit_vec, i)) { break; } |
| } |
| } |
| TEST_UINT_EQ(runner, i, 18, "Flip_Block(%u, %u)", offset, len); |
| |
| DECREF(bit_vec); |
| } |
| } |
| } |
| |
| static void |
| test_Mimic(TestBatchRunner *runner) { |
| for (unsigned foo = 0; foo <= 17; foo++) { |
| for (unsigned bar = 0; bar <= 17; bar++) { |
| BitVector *foo_vec = BitVec_new(0); |
| BitVector *bar_vec = BitVec_new(0); |
| |
| BitVec_Set(foo_vec, foo); |
| BitVec_Set(bar_vec, bar); |
| BitVec_Mimic(foo_vec, (Obj*)bar_vec); |
| |
| unsigned i; |
| for (i = 0; i <= 17; i++) { |
| if (BitVec_Get(foo_vec, i) && i != bar) { break; } |
| } |
| TEST_UINT_EQ(runner, i, 18, "Mimic(%u, %u)", foo, bar); |
| |
| DECREF(foo_vec); |
| DECREF(bar_vec); |
| } |
| } |
| } |
| |
| static BitVector* |
| S_create_set(int set_num) { |
| unsigned nums_1[] = { 1, 2, 3, 10, 20, 30, 0 }; |
| unsigned nums_2[] = { 2, 3, 4, 5, 6, 7, 8, 9, 10, |
| 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 0 |
| }; |
| unsigned *nums = set_num == 1 ? nums_1 : nums_2; |
| BitVector *bit_vec = BitVec_new(31); |
| for (unsigned i = 0; nums[i] != 0; i++) { |
| BitVec_Set(bit_vec, nums[i]); |
| } |
| return bit_vec; |
| } |
| |
| #define OP_OR 1 |
| #define OP_XOR 2 |
| #define OP_AND 3 |
| #define OP_AND_NOT 4 |
| static unsigned |
| S_verify_logical_op(BitVector *bit_vec, BitVector *set_1, BitVector *set_2, |
| int op) { |
| unsigned i; |
| |
| for (i = 0; i < 50; i++) { |
| bool wanted; |
| |
| switch (op) { |
| case OP_OR: |
| wanted = BitVec_Get(set_1, i) || BitVec_Get(set_2, i); |
| break; |
| case OP_XOR: |
| wanted = (!BitVec_Get(set_1, i)) != (!BitVec_Get(set_2, i)); |
| break; |
| case OP_AND: |
| wanted = BitVec_Get(set_1, i) && BitVec_Get(set_2, i); |
| break; |
| case OP_AND_NOT: |
| wanted = BitVec_Get(set_1, i) && (!BitVec_Get(set_2, i)); |
| break; |
| default: |
| wanted = false; |
| THROW(ERR, "unknown op: %d", op); |
| } |
| |
| if (BitVec_Get(bit_vec, i) != wanted) { break; } |
| } |
| |
| return i; |
| } |
| |
| static void |
| test_Or(TestBatchRunner *runner) { |
| BitVector *smaller = S_create_set(1); |
| BitVector *larger = S_create_set(2); |
| BitVector *set_1 = S_create_set(1); |
| BitVector *set_2 = S_create_set(2); |
| |
| BitVec_Or(smaller, set_2); |
| TEST_UINT_EQ(runner, S_verify_logical_op(smaller, set_1, set_2, OP_OR), |
| 50, "OR with self smaller than other"); |
| BitVec_Or(larger, set_1); |
| TEST_UINT_EQ(runner, S_verify_logical_op(larger, set_1, set_2, OP_OR), |
| 50, "OR with other smaller than self"); |
| |
| DECREF(smaller); |
| DECREF(larger); |
| DECREF(set_1); |
| DECREF(set_2); |
| } |
| |
| static void |
| test_Xor(TestBatchRunner *runner) { |
| BitVector *smaller = S_create_set(1); |
| BitVector *larger = S_create_set(2); |
| BitVector *set_1 = S_create_set(1); |
| BitVector *set_2 = S_create_set(2); |
| |
| BitVec_Xor(smaller, set_2); |
| TEST_UINT_EQ(runner, S_verify_logical_op(smaller, set_1, set_2, OP_XOR), |
| 50, "XOR with self smaller than other"); |
| BitVec_Xor(larger, set_1); |
| TEST_UINT_EQ(runner, S_verify_logical_op(larger, set_1, set_2, OP_XOR), |
| 50, "XOR with other smaller than self"); |
| |
| DECREF(smaller); |
| DECREF(larger); |
| DECREF(set_1); |
| DECREF(set_2); |
| } |
| |
| static void |
| test_And(TestBatchRunner *runner) { |
| BitVector *smaller = S_create_set(1); |
| BitVector *larger = S_create_set(2); |
| BitVector *set_1 = S_create_set(1); |
| BitVector *set_2 = S_create_set(2); |
| |
| BitVec_And(smaller, set_2); |
| TEST_UINT_EQ(runner, S_verify_logical_op(smaller, set_1, set_2, OP_AND), |
| 50, "AND with self smaller than other"); |
| BitVec_And(larger, set_1); |
| TEST_UINT_EQ(runner, S_verify_logical_op(larger, set_1, set_2, OP_AND), |
| 50, "AND with other smaller than self"); |
| |
| DECREF(smaller); |
| DECREF(larger); |
| DECREF(set_1); |
| DECREF(set_2); |
| } |
| |
| static void |
| test_And_Not(TestBatchRunner *runner) { |
| BitVector *smaller = S_create_set(1); |
| BitVector *larger = S_create_set(2); |
| BitVector *set_1 = S_create_set(1); |
| BitVector *set_2 = S_create_set(2); |
| |
| BitVec_And_Not(smaller, set_2); |
| TEST_UINT_EQ(runner, |
| S_verify_logical_op(smaller, set_1, set_2, OP_AND_NOT), |
| 50, "AND_NOT with self smaller than other"); |
| BitVec_And_Not(larger, set_1); |
| TEST_UINT_EQ(runner, |
| S_verify_logical_op(larger, set_2, set_1, OP_AND_NOT), |
| 50, "AND_NOT with other smaller than self"); |
| |
| DECREF(smaller); |
| DECREF(larger); |
| DECREF(set_1); |
| DECREF(set_2); |
| } |
| |
| static void |
| test_Count(TestBatchRunner *runner) { |
| unsigned shuffled[64]; |
| BitVector *bit_vec = BitVec_new(64); |
| |
| for (unsigned i = 0; i < 64; i++) { shuffled[i] = i; } |
| for (unsigned i = 0; i < 64; i++) { |
| unsigned shuffle_pos = (unsigned)rand() % 64; |
| unsigned temp = shuffled[shuffle_pos]; |
| shuffled[shuffle_pos] = shuffled[i]; |
| shuffled[i] = temp; |
| } |
| unsigned i; |
| for (i = 0; i < 64; i++) { |
| BitVec_Set(bit_vec, shuffled[i]); |
| if (BitVec_Count(bit_vec) != (uint32_t)(i + 1)) { break; } |
| } |
| TEST_UINT_EQ(runner, i, 64, "Count() returns the right number of bits"); |
| |
| DECREF(bit_vec); |
| } |
| |
| static void |
| test_Next_Hit(TestBatchRunner *runner) { |
| for (int i = 24; i <= 33; i++) { |
| BitVector *bit_vec = BitVec_new(64); |
| BitVec_Set(bit_vec, (size_t)i); |
| TEST_INT_EQ(runner, BitVec_Next_Hit(bit_vec, 0), i, |
| "Next_Hit for 0 is %d", i); |
| TEST_INT_EQ(runner, BitVec_Next_Hit(bit_vec, 1), i, |
| "Next_Hit for 1 is %d", i); |
| for (int probe = 15; probe <= i; probe++) { |
| TEST_INT_EQ(runner, BitVec_Next_Hit(bit_vec, (size_t)probe), i, |
| "Next_Hit for %d is %d", probe, i); |
| } |
| for (int probe = i + 1; probe <= i + 9; probe++) { |
| TEST_INT_EQ(runner, BitVec_Next_Hit(bit_vec, (size_t)probe), -1, |
| "no Next_Hit for %d when max is %d", probe, i); |
| } |
| TEST_INT_EQ(runner, BitVec_Next_Hit(bit_vec, INT32_MAX), -1, |
| "no Next_Hit for INT32_MAX when max is %d", i); |
| DECREF(bit_vec); |
| } |
| } |
| |
| static void |
| test_Clear_All(TestBatchRunner *runner) { |
| BitVector *bit_vec = BitVec_new(64); |
| BitVec_Flip_Block(bit_vec, 0, 63); |
| BitVec_Clear_All(bit_vec); |
| TEST_INT_EQ(runner, BitVec_Next_Hit(bit_vec, 0), -1, "Clear_All"); |
| DECREF(bit_vec); |
| } |
| |
| static void |
| test_Clone(TestBatchRunner *runner) { |
| BitVector *self = BitVec_new(30); |
| BitVector *twin; |
| |
| BitVec_Set(self, 2); |
| BitVec_Set(self, 3); |
| BitVec_Set(self, 10); |
| BitVec_Set(self, 20); |
| |
| twin = BitVec_Clone(self); |
| size_t i; |
| for (i = 0; i < 50; i++) { |
| if (BitVec_Get(self, i) != BitVec_Get(twin, i)) { break; } |
| } |
| TEST_UINT_EQ(runner, i, 50, "Clone"); |
| TEST_UINT_EQ(runner, BitVec_Count(twin), 4, "clone Count"); |
| |
| DECREF(self); |
| DECREF(twin); |
| } |
| |
| static int |
| S_compare_u64s(const void *va, const void *vb) { |
| uint64_t a = *(uint64_t*)va; |
| uint64_t b = *(uint64_t*)vb; |
| return a == b ? 0 : a < b ? -1 : 1; |
| } |
| |
| static void |
| test_To_Array(TestBatchRunner *runner) { |
| uint64_t *source_ints = TestUtils_random_u64s(NULL, 20, 0, 200); |
| BitVector *bit_vec = BitVec_new(0); |
| I32Array *array; |
| unsigned num_unique = 0; |
| |
| // Unique the random ints. |
| qsort(source_ints, 20, sizeof(uint64_t), S_compare_u64s); |
| for (unsigned i = 0; i < 19; i++) { |
| if (source_ints[i] != source_ints[i + 1]) { |
| source_ints[num_unique] = source_ints[i]; |
| num_unique++; |
| } |
| } |
| |
| // Set bits. |
| for (unsigned i = 0; i < num_unique; i++) { |
| BitVec_Set(bit_vec, (size_t)source_ints[i]); |
| } |
| |
| // Create the array and compare it to the source. |
| array = BitVec_To_Array(bit_vec); |
| unsigned i; |
| for (i = 0; i < num_unique; i++) { |
| if (I32Arr_Get(array, (size_t)i) != (int32_t)source_ints[i]) { break; } |
| } |
| TEST_UINT_EQ(runner, i, num_unique, "To_Array (%u == %u)", i, |
| num_unique); |
| |
| DECREF(array); |
| DECREF(bit_vec); |
| FREEMEM(source_ints); |
| } |
| |
| |
| // Valgrind only - detect off-by-one error. |
| static void |
| test_off_by_one_error() { |
| for (unsigned cap = 5; cap <= 24; cap++) { |
| BitVector *bit_vec = BitVec_new(cap); |
| BitVec_Set(bit_vec, cap - 2); |
| DECREF(bit_vec); |
| } |
| } |
| |
| void |
| TestBitVector_Run_IMP(TestBitVector *self, TestBatchRunner *runner) { |
| TestBatchRunner_Plan(runner, (TestBatch*)self, 1039); |
| test_Set_and_Get(runner); |
| test_Flip(runner); |
| test_Flip_Block_ascending(runner); |
| test_Flip_Block_descending(runner); |
| test_Flip_Block_bulk(runner); |
| test_Mimic(runner); |
| test_Or(runner); |
| test_Xor(runner); |
| test_And(runner); |
| test_And_Not(runner); |
| test_Count(runner); |
| test_Next_Hit(runner); |
| test_Clear_All(runner); |
| test_Clone(runner); |
| test_To_Array(runner); |
| test_off_by_one_error(); |
| } |
| |
| |