http://git-wip-us.apache.org/repos/asf/lucy/blob/572d3564/test/Lucy/Test/Util/TestNumberUtils.c ---------------------------------------------------------------------- diff --git a/test/Lucy/Test/Util/TestNumberUtils.c b/test/Lucy/Test/Util/TestNumberUtils.c new file mode 100644 index 0000000..f9cf3a1 --- /dev/null +++ b/test/Lucy/Test/Util/TestNumberUtils.c @@ -0,0 +1,473 @@ +/* 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. + */ + +#include <stdlib.h> +#include <time.h> + +#define TESTLUCY_USE_SHORT_NAMES +#include "Lucy/Util/ToolSet.h" + +#include "charmony.h" + +#include "Lucy/Test/Util/TestNumberUtils.h" + +#include "Clownfish/TestHarness/TestBatchRunner.h" +#include "Clownfish/TestHarness/TestUtils.h" +#include "Lucy/Util/NumberUtils.h" + +TestNumberUtils* +TestNumUtil_new() { + return (TestNumberUtils*)Class_Make_Obj(TESTNUMBERUTILS); +} + +static void +test_u1(TestBatchRunner *runner) { + size_t count = 64; + uint64_t *ints = TestUtils_random_u64s(NULL, count, 0, 2); + size_t amount = count / 8; + uint8_t *bits = (uint8_t*)CALLOCATE(amount, sizeof(uint8_t)); + + for (size_t i = 0; i < count; i++) { + if (ints[i]) { NumUtil_u1set(bits, i); } + } + for (size_t i = 0; i < count; i++) { + TEST_UINT_EQ(runner, NumUtil_u1get(bits, i), ints[i], "u1 set/get"); + } + + for (size_t i = 0; i < count; i++) { + NumUtil_u1flip(bits, i); + } + for (size_t i = 0; i < count; i++) { + TEST_UINT_EQ(runner, NumUtil_u1get(bits, i), !ints[i], "u1 flip"); + } + + FREEMEM(bits); + FREEMEM(ints); +} + +static void +test_u2(TestBatchRunner *runner) { + size_t count = 32; + uint64_t *ints = TestUtils_random_u64s(NULL, count, 0, 4); + uint8_t *bits = (uint8_t*)CALLOCATE((count / 4), sizeof(uint8_t)); + + for (size_t i = 0; i < count; i++) { + NumUtil_u2set(bits, i, (uint8_t)ints[i]); + } + for (size_t i = 0; i < count; i++) { + TEST_UINT_EQ(runner, NumUtil_u2get(bits, i), ints[i], "u2"); + } + + FREEMEM(bits); + FREEMEM(ints); +} + +static void +test_u4(TestBatchRunner *runner) { + size_t count = 128; + uint64_t *ints = TestUtils_random_u64s(NULL, count, 0, 16); + uint8_t *bits = (uint8_t*)CALLOCATE((count / 2), sizeof(uint8_t)); + + for (size_t i = 0; i < count; i++) { + NumUtil_u4set(bits, i, (uint8_t)ints[i]); + } + for (size_t i = 0; i < count; i++) { + TEST_UINT_EQ(runner, NumUtil_u4get(bits, i), ints[i], "u4"); + } + + FREEMEM(bits); + FREEMEM(ints); +} + +static void +test_ci32(TestBatchRunner *runner) { + int64_t mins[] = { -500, -0x4000 - 100, INT32_MIN }; + int64_t limits[] = { 500, -0x4000 + 100, INT32_MIN + 10 }; + int32_t set_num; + int32_t num_sets = sizeof(mins) / sizeof(int64_t); + size_t count = 64; + int64_t *ints = NULL; + size_t amount = count * CI32_MAX_BYTES; + char *encoded = (char*)CALLOCATE(amount, sizeof(char)); + char *target = encoded; + char *limit = target + amount; + const char *decode; + + for (set_num = 0; set_num < num_sets; set_num++) { + const char *skip; + ints = TestUtils_random_i64s(ints, count, + mins[set_num], limits[set_num]); + target = encoded; + for (size_t i = 0; i < count; i++) { + NumUtil_encode_ci32((int32_t)ints[i], &target); + } + decode = encoded; + skip = encoded; + for (size_t i = 0; i < count; i++) { + TEST_INT_EQ(runner, NumUtil_decode_ci32(&decode), ints[i], + "ci32 %" PRId64, ints[i]); + NumUtil_skip_cint(&skip); + if (decode > limit) { THROW(ERR, "overrun"); } + } + TEST_TRUE(runner, skip == decode, "skip %p == %p", skip, decode); + } + + target = encoded; + NumUtil_encode_ci32(INT32_MAX, &target); + decode = encoded; + TEST_INT_EQ(runner, NumUtil_decode_ci32(&decode), INT32_MAX, + "ci32 INT32_MAX"); + target = encoded; + NumUtil_encode_ci32(INT32_MIN, &target); + decode = encoded; + TEST_INT_EQ(runner, NumUtil_decode_ci32(&decode), INT32_MIN, + "ci32 INT32_MIN"); + + FREEMEM(encoded); + FREEMEM(ints); +} + +static void +test_cu32(TestBatchRunner *runner) { + uint64_t mins[] = { 0, 0x4000 - 100, (uint32_t)INT32_MAX - 100, UINT32_MAX - 10 }; + uint64_t limits[] = { 500, 0x4000 + 100, (uint32_t)INT32_MAX + 100, UINT32_MAX }; + uint32_t set_num; + uint32_t num_sets = sizeof(mins) / sizeof(uint64_t); + size_t count = 64; + uint64_t *ints = NULL; + size_t amount = count * CU32_MAX_BYTES; + char *encoded = (char*)CALLOCATE(amount, sizeof(char)); + char *target = encoded; + char *limit = target + amount; + const char *decode; + + for (set_num = 0; set_num < num_sets; set_num++) { + const char *skip; + ints = TestUtils_random_u64s(ints, count, + mins[set_num], limits[set_num]); + target = encoded; + for (size_t i = 0; i < count; i++) { + ints[i] = (uint32_t)ints[i]; + NumUtil_encode_cu32((uint32_t)ints[i], &target); + } + decode = encoded; + skip = encoded; + for (size_t i = 0; i < count; i++) { + TEST_UINT_EQ(runner, NumUtil_decode_cu32(&decode), ints[i], + "cu32 %lu", (unsigned long)ints[i]); + NumUtil_skip_cint(&skip); + if (decode > limit) { THROW(ERR, "overrun"); } + } + TEST_TRUE(runner, skip == decode, "skip %p == %p", skip, decode); + + target = encoded; + for (size_t i = 0; i < count; i++) { + NumUtil_encode_padded_cu32((uint32_t)ints[i], &target); + } + TEST_TRUE(runner, target == limit, + "padded cu32 uses 5 bytes (%p == %p)", target, limit); + decode = encoded; + skip = encoded; + for (size_t i = 0; i < count; i++) { + TEST_UINT_EQ(runner, NumUtil_decode_cu32(&decode), ints[i], + "padded cu32 %lu", (unsigned long)ints[i]); + NumUtil_skip_cint(&skip); + if (decode > limit) { THROW(ERR, "overrun"); } + } + TEST_TRUE(runner, skip == decode, "skip padded %p == %p", skip, + decode); + } + + target = encoded; + NumUtil_encode_cu32(UINT32_MAX, &target); + decode = encoded; + TEST_UINT_EQ(runner, NumUtil_decode_cu32(&decode), UINT32_MAX, "cu32 UINT32_MAX"); + + FREEMEM(encoded); + FREEMEM(ints); +} + +static void +test_ci64(TestBatchRunner *runner) { + int64_t mins[] = { -500, -0x4000 - 100, (int64_t)INT32_MIN - 100, INT64_MIN }; + int64_t limits[] = { 500, -0x4000 + 100, (int64_t)INT32_MIN + 1000, INT64_MIN + 10 }; + int32_t set_num; + int32_t num_sets = sizeof(mins) / sizeof(int64_t); + size_t count = 64; + int64_t *ints = NULL; + size_t amount = count * CI64_MAX_BYTES; + char *encoded = (char*)CALLOCATE(amount, sizeof(char)); + char *target = encoded; + char *limit = target + amount; + const char *decode; + + for (set_num = 0; set_num < num_sets; set_num++) { + const char *skip; + ints = TestUtils_random_i64s(ints, count, + mins[set_num], limits[set_num]); + target = encoded; + for (size_t i = 0; i < count; i++) { + NumUtil_encode_ci64(ints[i], &target); + } + decode = encoded; + skip = encoded; + for (size_t i = 0; i < count; i++) { + int64_t got = NumUtil_decode_ci64(&decode); + TEST_INT_EQ(runner, got, ints[i], + "ci64 %" PRId64 " == %" PRId64, got, ints[i]); + if (decode > limit) { THROW(ERR, "overrun"); } + NumUtil_skip_cint(&skip); + } + TEST_TRUE(runner, skip == decode, "skip %p == %p", skip, decode); + } + + target = encoded; + NumUtil_encode_ci64(INT64_MAX, &target); + decode = encoded; + int64_t got = NumUtil_decode_ci64(&decode); + TEST_INT_EQ(runner, got, INT64_MAX, "ci64 INT64_MAX"); + + target = encoded; + NumUtil_encode_ci64(INT64_MIN, &target); + decode = encoded; + got = NumUtil_decode_ci64(&decode); + TEST_INT_EQ(runner, got, INT64_MIN, "ci64 INT64_MIN"); + + FREEMEM(encoded); + FREEMEM(ints); +} + +static void +test_cu64(TestBatchRunner *runner) { + uint64_t mins[] = { 0, 0x4000 - 100, (uint64_t)UINT32_MAX - 100, UINT64_MAX - 10 }; + uint64_t limits[] = { 500, 0x4000 + 100, (uint64_t)UINT32_MAX + 1000, UINT64_MAX }; + uint32_t set_num; + uint32_t num_sets = sizeof(mins) / sizeof(uint64_t); + size_t count = 64; + uint64_t *ints = NULL; + size_t amount = count * CU64_MAX_BYTES; + char *encoded = (char*)CALLOCATE(amount, sizeof(char)); + char *target = encoded; + char *limit = target + amount; + const char *decode; + + for (set_num = 0; set_num < num_sets; set_num++) { + const char *skip; + ints = TestUtils_random_u64s(ints, count, + mins[set_num], limits[set_num]); + target = encoded; + for (size_t i = 0; i < count; i++) { + NumUtil_encode_cu64(ints[i], &target); + } + decode = encoded; + skip = encoded; + for (size_t i = 0; i < count; i++) { + uint64_t got = NumUtil_decode_cu64(&decode); + TEST_TRUE(runner, got == ints[i], + "cu64 %" PRIu64 " == %" PRIu64, got, ints[i]); + if (decode > limit) { THROW(ERR, "overrun"); } + NumUtil_skip_cint(&skip); + } + TEST_TRUE(runner, skip == decode, "skip %p == %p", skip, decode); + } + + target = encoded; + NumUtil_encode_cu64(UINT64_MAX, &target); + + decode = encoded; + uint64_t got = NumUtil_decode_cu64(&decode); + TEST_TRUE(runner, got == UINT64_MAX, "cu64 UINT64_MAX"); + + FREEMEM(encoded); + FREEMEM(ints); +} + +static void +test_bigend_u16(TestBatchRunner *runner) { + size_t count = 32; + uint64_t *ints = TestUtils_random_u64s(NULL, count, 0, UINT16_MAX + 1); + size_t amount = (count + 1) * sizeof(uint16_t); + char *allocated = (char*)CALLOCATE(amount, sizeof(char)); + char *encoded = allocated + 1; // Intentionally misaligned. + char *target = encoded; + + for (size_t i = 0; i < count; i++) { + NumUtil_encode_bigend_u16((uint16_t)ints[i], &target); + target += sizeof(uint16_t); + } + target = encoded; + for (size_t i = 0; i < count; i++) { + uint16_t got = NumUtil_decode_bigend_u16(target); + TEST_INT_EQ(runner, got, (long)ints[i], "bigend u16"); + target += sizeof(uint16_t); + } + + target = encoded; + NumUtil_encode_bigend_u16(1, &target); + TEST_INT_EQ(runner, encoded[0], 0, "Truly big-endian u16"); + TEST_INT_EQ(runner, encoded[1], 1, "Truly big-endian u16"); + + FREEMEM(allocated); + FREEMEM(ints); +} + +static void +test_bigend_u32(TestBatchRunner *runner) { + size_t count = 32; + uint64_t *ints = TestUtils_random_u64s(NULL, count, 0, UINT64_C(1) + UINT32_MAX); + size_t amount = (count + 1) * sizeof(uint32_t); + char *allocated = (char*)CALLOCATE(amount, sizeof(char)); + char *encoded = allocated + 1; // Intentionally misaligned. + char *target = encoded; + + for (size_t i = 0; i < count; i++) { + ints[i] = (uint32_t)ints[i]; + NumUtil_encode_bigend_u32((uint32_t)ints[i], &target); + target += sizeof(uint32_t); + } + target = encoded; + for (size_t i = 0; i < count; i++) { + uint32_t got = NumUtil_decode_bigend_u32(target); + TEST_UINT_EQ(runner, got, ints[i], "bigend u32"); + target += sizeof(uint32_t); + } + + target = encoded; + NumUtil_encode_bigend_u32(1, &target); + TEST_INT_EQ(runner, encoded[0], 0, "Truly big-endian u32"); + TEST_INT_EQ(runner, encoded[3], 1, "Truly big-endian u32"); + + FREEMEM(allocated); + FREEMEM(ints); +} + +static void +test_bigend_u64(TestBatchRunner *runner) { + size_t count = 32; + uint64_t *ints = TestUtils_random_u64s(NULL, count, 0, UINT64_MAX); + size_t amount = (count + 1) * sizeof(uint64_t); + char *allocated = (char*)CALLOCATE(amount, sizeof(char)); + char *encoded = allocated + 1; // Intentionally misaligned. + char *target = encoded; + + for (size_t i = 0; i < count; i++) { + NumUtil_encode_bigend_u64(ints[i], &target); + target += sizeof(uint64_t); + } + target = encoded; + for (size_t i = 0; i < count; i++) { + uint64_t got = NumUtil_decode_bigend_u64(target); + TEST_TRUE(runner, got == ints[i], "bigend u64"); + target += sizeof(uint64_t); + } + + target = encoded; + NumUtil_encode_bigend_u64(1, &target); + TEST_INT_EQ(runner, encoded[0], 0, "Truly big-endian"); + TEST_INT_EQ(runner, encoded[7], 1, "Truly big-endian"); + + FREEMEM(allocated); + FREEMEM(ints); +} + +static void +test_bigend_f32(TestBatchRunner *runner) { + float source[] = { -1.3f, 0.0f, 100.2f }; + size_t count = 3; + size_t amount = (count + 1) * sizeof(float); + uint8_t *allocated = (uint8_t*)CALLOCATE(amount, sizeof(uint8_t)); + uint8_t *encoded = allocated + 1; // Intentionally misaligned. + uint8_t *target = encoded; + + for (size_t i = 0; i < count; i++) { + NumUtil_encode_bigend_f32(source[i], &target); + target += sizeof(float); + } + target = encoded; + for (size_t i = 0; i < count; i++) { + float got = NumUtil_decode_bigend_f32(target); + TEST_TRUE(runner, got == source[i], "bigend f32"); + target += sizeof(float); + } + + target = encoded; + NumUtil_encode_bigend_f32(-2.0f, &target); + TEST_INT_EQ(runner, (encoded[0] & 0x80), 0x80, + "Truly big-endian (IEEE 754 sign bit set for negative number)"); + TEST_INT_EQ(runner, encoded[0], 0xC0, + "IEEE 754 representation of -2.0f, byte 0"); + for (size_t i = 1; i < sizeof(float); i++) { + TEST_INT_EQ(runner, encoded[i], 0, + "IEEE 754 representation of -2.0f, byte %d", (int)i); + } + + FREEMEM(allocated); +} + +static void +test_bigend_f64(TestBatchRunner *runner) { + double source[] = { -1.3, 0.0, 100.2 }; + size_t count = 3; + size_t amount = (count + 1) * sizeof(double); + uint8_t *allocated = (uint8_t*)CALLOCATE(amount, sizeof(uint8_t)); + uint8_t *encoded = allocated + 1; // Intentionally misaligned. + uint8_t *target = encoded; + + for (size_t i = 0; i < count; i++) { + NumUtil_encode_bigend_f64(source[i], &target); + target += sizeof(double); + } + target = encoded; + for (size_t i = 0; i < count; i++) { + double got = NumUtil_decode_bigend_f64(target); + TEST_TRUE(runner, got == source[i], "bigend f64"); + target += sizeof(double); + } + + target = encoded; + NumUtil_encode_bigend_f64(-2.0, &target); + TEST_INT_EQ(runner, (encoded[0] & 0x80), 0x80, + "Truly big-endian (IEEE 754 sign bit set for negative number)"); + TEST_INT_EQ(runner, encoded[0], 0xC0, + "IEEE 754 representation of -2.0, byte 0"); + for (size_t i = 1; i < sizeof(double); i++) { + TEST_INT_EQ(runner, encoded[i], 0, + "IEEE 754 representation of -2.0, byte %d", (int)i); + } + + FREEMEM(allocated); +} + +void +TestNumUtil_Run_IMP(TestNumberUtils *self, TestBatchRunner *runner) { + TestBatchRunner_Plan(runner, (TestBatch*)self, 1655); + srand((unsigned int)time((time_t*)NULL)); + test_u1(runner); + test_u2(runner); + test_u4(runner); + test_ci32(runner); + test_cu32(runner); + test_ci64(runner); + test_cu64(runner); + test_bigend_u16(runner); + test_bigend_u32(runner); + test_bigend_u64(runner); + test_bigend_f32(runner); + test_bigend_f64(runner); +} + + +
http://git-wip-us.apache.org/repos/asf/lucy/blob/572d3564/test/Lucy/Test/Util/TestNumberUtils.cfh ---------------------------------------------------------------------- diff --git a/test/Lucy/Test/Util/TestNumberUtils.cfh b/test/Lucy/Test/Util/TestNumberUtils.cfh new file mode 100644 index 0000000..fcb20a9 --- /dev/null +++ b/test/Lucy/Test/Util/TestNumberUtils.cfh @@ -0,0 +1,29 @@ +/* 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. + */ + +parcel TestLucy; + +class Lucy::Test::Util::TestNumberUtils nickname TestNumUtil + inherits Clownfish::TestHarness::TestBatch { + + inert incremented TestNumberUtils* + new(); + + void + Run(TestNumberUtils *self, TestBatchRunner *runner); +} + + http://git-wip-us.apache.org/repos/asf/lucy/blob/572d3564/test/Lucy/Test/Util/TestPriorityQueue.c ---------------------------------------------------------------------- diff --git a/test/Lucy/Test/Util/TestPriorityQueue.c b/test/Lucy/Test/Util/TestPriorityQueue.c new file mode 100644 index 0000000..7265170 --- /dev/null +++ b/test/Lucy/Test/Util/TestPriorityQueue.c @@ -0,0 +1,165 @@ +/* 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_TESTPRIORITYQUEUE +#define TESTLUCY_USE_SHORT_NAMES +#include "Lucy/Util/ToolSet.h" + +#include "Clownfish/Num.h" +#include "Clownfish/TestHarness/TestBatchRunner.h" +#include "Lucy/Test.h" +#include "Lucy/Test/Util/TestPriorityQueue.h" +#include "Lucy/Util/PriorityQueue.h" + +TestPriorityQueue* +TestPriQ_new() { + return (TestPriorityQueue*)Class_Make_Obj(TESTPRIORITYQUEUE); +} + +NumPriorityQueue* +NumPriQ_new(uint32_t max_size) { + NumPriorityQueue *self + = (NumPriorityQueue*)Class_Make_Obj(NUMPRIORITYQUEUE); + return (NumPriorityQueue*)PriQ_init((PriorityQueue*)self, max_size); +} + +bool +NumPriQ_Less_Than_IMP(NumPriorityQueue *self, Obj *a, Obj *b) { + Float *num_a = (Float*)a; + Float *num_b = (Float*)b; + UNUSED_VAR(self); + return Float_Get_Value(num_a) < Float_Get_Value(num_b) ? true : false; +} + +static void +S_insert_num(NumPriorityQueue *pq, int32_t value) { + NumPriQ_Insert(pq, (Obj*)Float_new((double)value)); +} + +static int32_t +S_pop_num(NumPriorityQueue *pq) { + Float *num = (Float*)NumPriQ_Pop(pq); + int32_t retval; + if (!num) { THROW(ERR, "Queue is empty"); } + retval = (int32_t)Float_Get_Value(num); + DECREF(num); + return retval; +} + +static void +test_Peek_and_Pop_All(TestBatchRunner *runner) { + NumPriorityQueue *pq = NumPriQ_new(5); + Float *val; + + S_insert_num(pq, 3); + S_insert_num(pq, 1); + S_insert_num(pq, 2); + S_insert_num(pq, 20); + S_insert_num(pq, 10); + val = (Float*)CERTIFY(NumPriQ_Peek(pq), FLOAT); + TEST_INT_EQ(runner, (long)Float_Get_Value(val), 1, + "peek at the least item in the queue"); + + Vector *got = NumPriQ_Pop_All(pq); + val = (Float*)CERTIFY(Vec_Fetch(got, 0), FLOAT); + TEST_INT_EQ(runner, (long)Float_Get_Value(val), 20, "pop_all"); + val = (Float*)CERTIFY(Vec_Fetch(got, 1), FLOAT); + TEST_INT_EQ(runner, (long)Float_Get_Value(val), 10, "pop_all"); + val = (Float*)CERTIFY(Vec_Fetch(got, 2), FLOAT); + TEST_INT_EQ(runner, (long)Float_Get_Value(val), 3, "pop_all"); + val = (Float*)CERTIFY(Vec_Fetch(got, 3), FLOAT); + TEST_INT_EQ(runner, (long)Float_Get_Value(val), 2, "pop_all"); + val = (Float*)CERTIFY(Vec_Fetch(got, 4), FLOAT); + TEST_INT_EQ(runner, (long)Float_Get_Value(val), 1, "pop_all"); + + DECREF(got); + DECREF(pq); +} + +static void +test_Insert_and_Pop(TestBatchRunner *runner) { + NumPriorityQueue *pq = NumPriQ_new(5); + + S_insert_num(pq, 3); + S_insert_num(pq, 1); + S_insert_num(pq, 2); + S_insert_num(pq, 20); + S_insert_num(pq, 10); + + TEST_INT_EQ(runner, S_pop_num(pq), 1, "Pop"); + TEST_INT_EQ(runner, S_pop_num(pq), 2, "Pop"); + TEST_INT_EQ(runner, S_pop_num(pq), 3, "Pop"); + TEST_INT_EQ(runner, S_pop_num(pq), 10, "Pop"); + + S_insert_num(pq, 7); + TEST_INT_EQ(runner, S_pop_num(pq), 7, + "Insert after Pop still sorts correctly"); + + DECREF(pq); +} + +static void +test_discard(TestBatchRunner *runner) { + int32_t i; + NumPriorityQueue *pq = NumPriQ_new(5); + + for (i = 1; i <= 10; i++) { S_insert_num(pq, i); } + S_insert_num(pq, -3); + for (i = 1590; i <= 1600; i++) { S_insert_num(pq, i); } + S_insert_num(pq, 5); + + TEST_INT_EQ(runner, S_pop_num(pq), 1596, "discard waste"); + TEST_INT_EQ(runner, S_pop_num(pq), 1597, "discard waste"); + TEST_INT_EQ(runner, S_pop_num(pq), 1598, "discard waste"); + TEST_INT_EQ(runner, S_pop_num(pq), 1599, "discard waste"); + TEST_INT_EQ(runner, S_pop_num(pq), 1600, "discard waste"); + + DECREF(pq); +} + +static void +test_random_insertion(TestBatchRunner *runner) { + int i; + int shuffled[64]; + NumPriorityQueue *pq = NumPriQ_new(64); + + for (i = 0; i < 64; i++) { shuffled[i] = i; } + for (i = 0; i < 64; i++) { + int shuffle_pos = rand() % 64; + int temp = shuffled[shuffle_pos]; + shuffled[shuffle_pos] = shuffled[i]; + shuffled[i] = temp; + } + for (i = 0; i < 64; i++) { S_insert_num(pq, shuffled[i]); } + for (i = 0; i < 64; i++) { + if (S_pop_num(pq) != i) { break; } + } + TEST_INT_EQ(runner, i, 64, "random insertion"); + + DECREF(pq); +} + +void +TestPriQ_Run_IMP(TestPriorityQueue *self, TestBatchRunner *runner) { + TestBatchRunner_Plan(runner, (TestBatch*)self, 17); + test_Peek_and_Pop_All(runner); + test_Insert_and_Pop(runner); + test_discard(runner); + test_random_insertion(runner); +} + + + http://git-wip-us.apache.org/repos/asf/lucy/blob/572d3564/test/Lucy/Test/Util/TestPriorityQueue.cfh ---------------------------------------------------------------------- diff --git a/test/Lucy/Test/Util/TestPriorityQueue.cfh b/test/Lucy/Test/Util/TestPriorityQueue.cfh new file mode 100644 index 0000000..4f434f1 --- /dev/null +++ b/test/Lucy/Test/Util/TestPriorityQueue.cfh @@ -0,0 +1,39 @@ +/* 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. + */ + +parcel TestLucy; + +class Lucy::Test::Util::NumPriorityQueue nickname NumPriQ + inherits Lucy::Util::PriorityQueue { + + inert incremented NumPriorityQueue* + new(uint32_t max_size); + + bool + Less_Than(NumPriorityQueue *self, Obj *a, Obj *b); +} + +class Lucy::Test::Util::TestPriorityQueue nickname TestPriQ + inherits Clownfish::TestHarness::TestBatch { + + inert incremented TestPriorityQueue* + new(); + + void + Run(TestPriorityQueue *self, TestBatchRunner *runner); +} + + http://git-wip-us.apache.org/repos/asf/lucy/blob/572d3564/test/Lucy/Test/Util/TestSortExternal.c ---------------------------------------------------------------------- diff --git a/test/Lucy/Test/Util/TestSortExternal.c b/test/Lucy/Test/Util/TestSortExternal.c new file mode 100644 index 0000000..b55dcc2 --- /dev/null +++ b/test/Lucy/Test/Util/TestSortExternal.c @@ -0,0 +1,324 @@ +/* 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. + */ + +#include <stdlib.h> +#include <string.h> +#include <time.h> + +#define TESTLUCY_USE_SHORT_NAMES +#include "Lucy/Util/ToolSet.h" +#include "Lucy/Test/Util/TestSortExternal.h" + +#include "Clownfish/Blob.h" +#include "Clownfish/TestHarness/TestBatchRunner.h" +#include "Lucy/Util/BlobSortEx.h" +#include "Lucy/Util/SortExternal.h" + +static Blob *a_blob; +static Blob *b_blob; +static Blob *c_blob; +static Blob *d_blob; +static Blob *x_blob; +static Blob *y_blob; +static Blob *z_blob; + +TestSortExternal* +TestSortExternal_new() { + return (TestSortExternal*)Class_Make_Obj(TESTSORTEXTERNAL); +} + +static void +S_init_blobs() { + a_blob = Blob_new("a", 1); + b_blob = Blob_new("b", 1); + c_blob = Blob_new("c", 1); + d_blob = Blob_new("d", 1); + x_blob = Blob_new("x", 1); + y_blob = Blob_new("y", 1); + z_blob = Blob_new("z", 1); +} + +static void +S_destroy_blobs() { + DECREF(a_blob); + DECREF(b_blob); + DECREF(c_blob); + DECREF(d_blob); + DECREF(x_blob); + DECREF(y_blob); + DECREF(z_blob); +} + +static void +test_bbsortex(TestBatchRunner *runner) { + BlobSortEx *sortex = BlobSortEx_new(4, NULL); + + BlobSortEx_Feed(sortex, INCREF(c_blob)); + TEST_INT_EQ(runner, BlobSortEx_Buffer_Count(sortex), 1, + "feed elem into cache"); + + BlobSortEx_Feed(sortex, INCREF(b_blob)); + BlobSortEx_Feed(sortex, INCREF(d_blob)); + BlobSortEx_Sort_Buffer(sortex); + + { + Vector *cache = BlobSortEx_Peek_Cache(sortex); + Vector *wanted = Vec_new(3); + Vec_Push(wanted, INCREF(b_blob)); + Vec_Push(wanted, INCREF(c_blob)); + Vec_Push(wanted, INCREF(d_blob)); + TEST_TRUE(runner, Vec_Equals(cache, (Obj*)wanted), "sort cache"); + DECREF(wanted); + DECREF(cache); + } + + BlobSortEx_Feed(sortex, INCREF(a_blob)); + TEST_INT_EQ(runner, BlobSortEx_Buffer_Count(sortex), 0, + "cache flushed automatically when mem_thresh crossed"); + TEST_INT_EQ(runner, BlobSortEx_Get_Num_Runs(sortex), 1, "run added"); + + Vector *external = Vec_new(3); + Vec_Push(external, INCREF(x_blob)); + Vec_Push(external, INCREF(y_blob)); + Vec_Push(external, INCREF(z_blob)); + BlobSortEx *run = BlobSortEx_new(0x1000000, external); + BlobSortEx_Add_Run(sortex, (SortExternal*)run); + BlobSortEx_Flip(sortex); + + { + Vector *got = Vec_new(7); + Obj *object; + while (NULL != (object = BlobSortEx_Fetch(sortex))) { + Vec_Push(got, object); + } + + Vector *wanted = Vec_new(7); + Vec_Push(wanted, INCREF(a_blob)); + Vec_Push(wanted, INCREF(b_blob)); + Vec_Push(wanted, INCREF(c_blob)); + Vec_Push(wanted, INCREF(d_blob)); + Vec_Push(wanted, INCREF(x_blob)); + Vec_Push(wanted, INCREF(y_blob)); + Vec_Push(wanted, INCREF(z_blob)); + + TEST_TRUE(runner, Vec_Equals(got, (Obj*)wanted), "Add_Run"); + + DECREF(wanted); + DECREF(got); + } + + DECREF(external); + DECREF(sortex); +} + +static void +test_clear_buffer(TestBatchRunner *runner) { + BlobSortEx *sortex = BlobSortEx_new(4, NULL); + + BlobSortEx_Feed(sortex, INCREF(c_blob)); + BlobSortEx_Clear_Buffer(sortex); + TEST_INT_EQ(runner, BlobSortEx_Buffer_Count(sortex), 0, "Clear_Buffer"); + + BlobSortEx_Feed(sortex, INCREF(b_blob)); + BlobSortEx_Feed(sortex, INCREF(a_blob)); + BlobSortEx_Flush(sortex); + BlobSortEx_Flip(sortex); + Obj *object = BlobSortEx_Peek(sortex); + TEST_TRUE(runner, Blob_Equals(a_blob, object), "Peek"); + + Vector *got = Vec_new(2); + while (NULL != (object = BlobSortEx_Fetch(sortex))) { + Vec_Push(got, object); + } + Vector *wanted = Vec_new(2); + Vec_Push(wanted, INCREF(a_blob)); + Vec_Push(wanted, INCREF(b_blob)); + TEST_TRUE(runner, Vec_Equals(got, (Obj*)wanted), + "elements cleared via Clear_Buffer truly cleared"); + + DECREF(wanted); + DECREF(got); + DECREF(sortex); +} + +static void +S_test_sort(TestBatchRunner *runner, Vector *blobs, uint32_t mem_thresh, + const char *test_name) { + size_t size = Vec_Get_Size(blobs); + BlobSortEx *sortex = BlobSortEx_new(mem_thresh, NULL); + Blob **shuffled = (Blob**)MALLOCATE(size * sizeof(Blob*)); + + for (size_t i = 0; i < size; ++i) { + shuffled[i] = (Blob*)CERTIFY(Vec_Fetch(blobs, i), BLOB); + } + for (int i = (int)size - 1; i > 0; --i) { + int shuffle_pos = rand() % (i + 1); + Blob *temp = shuffled[shuffle_pos]; + shuffled[shuffle_pos] = shuffled[i]; + shuffled[i] = temp; + } + for (size_t i = 0; i < size; ++i) { + BlobSortEx_Feed(sortex, INCREF(shuffled[i])); + } + + BlobSortEx_Flip(sortex); + Vector *got = Vec_new(size); + Obj *object; + while (NULL != (object = BlobSortEx_Fetch(sortex))) { + Vec_Push(got, object); + } + TEST_TRUE(runner, Vec_Equals(got, (Obj*)blobs), test_name); + + FREEMEM(shuffled); + DECREF(got); + DECREF(sortex); +} + +static void +S_test_sort_letters(TestBatchRunner *runner, const char *letters, + uint32_t mem_thresh, const char *test_name) { + size_t num_letters = strlen(letters); + Vector *blobs = Vec_new(num_letters); + + for (size_t i = 0; i < num_letters; ++i) { + char ch = letters[i]; + size_t size = ch == '_' ? 0 : 1; + Blob *blob = Blob_new(&ch, size); + Vec_Push(blobs, (Obj*)blob); + } + + S_test_sort(runner, blobs, mem_thresh, test_name); + + DECREF(blobs); +} + +static void +test_sort_letters(TestBatchRunner *runner) { + S_test_sort_letters(runner, "abcdefghijklmnopqrstuvwxyz", 0x1000000, + "sort letters"); + S_test_sort_letters(runner, "aaabcdxxxxxxyy", 0x1000000, + "sort repeated letters"); + S_test_sort_letters(runner, "__abcdefghijklmnopqrstuvwxyz", 0x1000000, + "sort letters and empty strings"); + S_test_sort_letters(runner, "abcdefghijklmnopqrstuvwxyz", 30, + "... with an absurdly low mem_thresh"); + S_test_sort_letters(runner, "abcdefghijklmnopqrstuvwxyz", 1, + "... with an even lower mem_thresh"); +} + +static void +test_sort_nothing(TestBatchRunner *runner) { + BlobSortEx *sortex = BlobSortEx_new(0x1000000, NULL); + BlobSortEx_Flip(sortex); + TEST_TRUE(runner, BlobSortEx_Fetch(sortex) == NULL, + "Sorting nothing returns undef"); + DECREF(sortex); +} + +static void +test_sort_packed_ints(TestBatchRunner *runner) { + size_t num_ints = 11001; + Vector *blobs = Vec_new(num_ints); + + for (uint32_t i = 0; i < num_ints; ++i) { + uint8_t buf[4]; + buf[0] = (uint8_t)((i >> 24) & 0xFF); + buf[1] = (uint8_t)((i >> 16) & 0xFF); + buf[2] = (uint8_t)((i >> 8) & 0xFF); + buf[3] = (uint8_t)(i & 0xFF); + Blob *blob = Blob_new((char*)buf, 4); + Vec_Push(blobs, (Obj*)blob); + } + + S_test_sort(runner, blobs, 5000, "Sorting packed integers..."); + + DECREF(blobs); +} + +static void +test_sort_random_strings(TestBatchRunner *runner) { + size_t num_strings = 1001; + Vector *blobs = Vec_new(num_strings); + + for (uint32_t i = 0; i < num_strings; ++i) { + uint8_t buf[1201]; + int size = rand() % 1200 + 1; + for (int i = 0; i < size; ++i) { + buf[i] = (uint8_t)(rand() % 256); + } + Blob *blob = Blob_new((char*)buf, (size_t)size); + Vec_Push(blobs, (Obj*)blob); + } + + Vec_Sort(blobs); + S_test_sort(runner, blobs, 15000, + "Random binary strings of random length"); + + DECREF(blobs); +} + +static void +test_run(TestBatchRunner *runner) { + Vector *letters = Vec_new(26); + for (char i = 0; i < 26; ++i) { + char ch = 'a' + i; + Blob *blob = Blob_new(&ch, 1); + Vec_Push(letters, (Obj*)blob); + } + BlobSortEx *run = BlobSortEx_new(0x1000000, letters); + BlobSortEx_Set_Mem_Thresh(run, 5); + + BlobSortEx_Refill(run); + TEST_INT_EQ(runner, BlobSortEx_Buffer_Count(run), 5, + "Refill doesn't exceed memory threshold"); + + Obj *endpost = BlobSortEx_Peek_Last(run); + Blob *wanted = Blob_new("e", 1); + TEST_TRUE(runner, Blob_Equals(wanted, endpost), "Peek_Last"); + + Vector *elems = Vec_new(26); + do { + while (BlobSortEx_Buffer_Count(run) > 0) { + Obj *object = BlobSortEx_Fetch(run); + Vec_Push(elems, object); + } + } while (BlobSortEx_Refill(run) > 0); + TEST_TRUE(runner, Vec_Equals(elems, (Obj*)letters), "retrieve all elems"); + + DECREF(elems); + DECREF(wanted); + DECREF(endpost); + DECREF(letters); + DECREF(run); +} + +void +TestSortExternal_Run_IMP(TestSortExternal *self, TestBatchRunner *runner) { + TestBatchRunner_Plan(runner, (TestBatch*)self, 19); + + srand((unsigned int)time((time_t*)NULL)); + S_init_blobs(); + test_bbsortex(runner); + test_clear_buffer(runner); + test_sort_letters(runner); + test_sort_nothing(runner); + test_sort_packed_ints(runner); + test_sort_random_strings(runner); + test_run(runner); + S_destroy_blobs(); +} + + http://git-wip-us.apache.org/repos/asf/lucy/blob/572d3564/test/Lucy/Test/Util/TestSortExternal.cfh ---------------------------------------------------------------------- diff --git a/test/Lucy/Test/Util/TestSortExternal.cfh b/test/Lucy/Test/Util/TestSortExternal.cfh new file mode 100644 index 0000000..028b322 --- /dev/null +++ b/test/Lucy/Test/Util/TestSortExternal.cfh @@ -0,0 +1,29 @@ +/* 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. + */ + +parcel TestLucy; + +class Lucy::Test::Util::TestSortExternal + inherits Clownfish::TestHarness::TestBatch { + + inert incremented TestSortExternal* + new(); + + void + Run(TestSortExternal *self, TestBatchRunner *runner); +} + + http://git-wip-us.apache.org/repos/asf/lucy/blob/572d3564/test/TestLucy.c ---------------------------------------------------------------------- diff --git a/test/TestLucy.c b/test/TestLucy.c new file mode 100644 index 0000000..f499da5 --- /dev/null +++ b/test/TestLucy.c @@ -0,0 +1,22 @@ +/* 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. + */ + +#include "testlucy_parcel.h" + +void +testlucy_init_parcel() { +} + http://git-wip-us.apache.org/repos/asf/lucy/blob/572d3564/test/TestLucy.cfp ---------------------------------------------------------------------- diff --git a/test/TestLucy.cfp b/test/TestLucy.cfp new file mode 100644 index 0000000..a3aef6e --- /dev/null +++ b/test/TestLucy.cfp @@ -0,0 +1,8 @@ +{ + "name": "TestLucy", + "version": "v0.5.0", + "prerequisites": { + "Clownfish": "v0.5.0", + "Lucy": "v0.5.0" + } +}
