diff options
author | Sybren A. Stüvel <sybren@stuvel.eu> | 2017-10-29 17:14:04 +0300 |
---|---|---|
committer | Sybren A. Stüvel <sybren@stuvel.eu> | 2017-10-29 17:14:04 +0300 |
commit | 7530c54c3cf38016d9038e6879c8ee2b1bd14c9e (patch) | |
tree | a43bf60f8267855f7950017b53c04fd88a5207ac /tests | |
parent | 1186dec916737b69afecd15030736f6d3361694e (diff) | |
parent | d9000495e1273052c895c754fd2aa56c9dbe6175 (diff) |
Merge branch 'master' into blender2.8
Diffstat (limited to 'tests')
-rw-r--r-- | tests/gtests/blenlib/BLI_heap_test.cc | 191 | ||||
-rw-r--r-- | tests/gtests/blenlib/CMakeLists.txt | 1 |
2 files changed, 192 insertions, 0 deletions
diff --git a/tests/gtests/blenlib/BLI_heap_test.cc b/tests/gtests/blenlib/BLI_heap_test.cc new file mode 100644 index 00000000000..89e271d5167 --- /dev/null +++ b/tests/gtests/blenlib/BLI_heap_test.cc @@ -0,0 +1,191 @@ +/* Apache License, Version 2.0 */ + +#include "testing/testing.h" +#include <string.h> + +extern "C" { +#include "BLI_compiler_attrs.h" +#include "BLI_heap.h" +#include "BLI_utildefines.h" +#include "BLI_rand.h" + +#include "MEM_guardedalloc.h" +}; + +#define SIZE 1024 + + +static void range_fl(float *array_tar, const int size) +{ + float *array_pt = array_tar + (size - 1); + int i = size; + while (i--) { + *(array_pt--) = (float)i; + } +} + +TEST(heap, Empty) +{ + Heap *heap; + + heap = BLI_heap_new(); + EXPECT_TRUE(BLI_heap_is_empty(heap)); + EXPECT_EQ(BLI_heap_size(heap), 0); + BLI_heap_free(heap, NULL); +} + +TEST(heap, One) +{ + Heap *heap; + const char *in = "test"; + + heap = BLI_heap_new(); + + BLI_heap_insert(heap, 0.0f, (void *)in); + EXPECT_FALSE(BLI_heap_is_empty(heap)); + EXPECT_EQ(BLI_heap_size(heap), 1); + EXPECT_EQ(in, BLI_heap_popmin(heap)); + EXPECT_TRUE(BLI_heap_is_empty(heap)); + EXPECT_EQ(BLI_heap_size(heap), 0); + BLI_heap_free(heap, NULL); +} + +TEST(heap, Range) +{ + const int items_total = SIZE; + Heap *heap = BLI_heap_new(); + for (int in = 0; in < items_total; in++) { + BLI_heap_insert(heap, (float)in, SET_INT_IN_POINTER(in)); + } + for (int out_test = 0; out_test < items_total; out_test++) { + EXPECT_EQ(out_test, GET_INT_FROM_POINTER(BLI_heap_popmin(heap))); + + } + EXPECT_TRUE(BLI_heap_is_empty(heap)); + BLI_heap_free(heap, NULL); +} + +TEST(heap, RangeReverse) +{ + const int items_total = SIZE; + Heap *heap = BLI_heap_new(); + for (int in = 0; in < items_total; in++) { + BLI_heap_insert(heap, (float)-in, SET_INT_IN_POINTER(-in)); + } + for (int out_test = items_total - 1; out_test >= 0; out_test--) { + EXPECT_EQ(-out_test, GET_INT_FROM_POINTER(BLI_heap_popmin(heap))); + } + EXPECT_TRUE(BLI_heap_is_empty(heap)); + BLI_heap_free(heap, NULL); +} + +TEST(heap, RangeRemove) +{ + const int items_total = SIZE; + Heap *heap = BLI_heap_new(); + HeapNode **nodes = (HeapNode **)MEM_mallocN(sizeof(HeapNode *) * items_total, __func__); + for (int in = 0; in < items_total; in++) { + nodes[in] = BLI_heap_insert(heap, (float)in, SET_INT_IN_POINTER(in)); + } + for (int i = 0; i < items_total; i += 2) { + BLI_heap_remove(heap, nodes[i]); + nodes[i] = NULL; + } + for (int out_test = 1; out_test < items_total; out_test += 2) { + EXPECT_EQ(out_test, GET_INT_FROM_POINTER(BLI_heap_popmin(heap))); + } + EXPECT_TRUE(BLI_heap_is_empty(heap)); + BLI_heap_free(heap, NULL); + MEM_freeN(nodes); +} + +TEST(heap, Duplicates) +{ + const int items_total = SIZE; + Heap *heap = BLI_heap_new(); + for (int in = 0; in < items_total; in++) { + BLI_heap_insert(heap, 1.0f, 0); + } + for (int out_test = 0; out_test < items_total; out_test++) { + EXPECT_EQ(0, GET_INT_FROM_POINTER(BLI_heap_popmin(heap))); + } + EXPECT_TRUE(BLI_heap_is_empty(heap)); + BLI_heap_free(heap, NULL); +} + +static void random_heap_helper( + const int items_total, + const int random_seed) +{ + Heap *heap = BLI_heap_new(); + float *values = (float *)MEM_mallocN(sizeof(float) * items_total, __func__); + range_fl(values, items_total); + BLI_array_randomize(values, sizeof(float), items_total, random_seed); + for (int i = 0; i < items_total; i++) { + BLI_heap_insert(heap, values[i], SET_INT_IN_POINTER((int)values[i])); + } + for (int out_test = 0; out_test < items_total; out_test++) { + EXPECT_EQ(out_test, GET_INT_FROM_POINTER(BLI_heap_popmin(heap))); + } + EXPECT_TRUE(BLI_heap_is_empty(heap)); + BLI_heap_free(heap, NULL); + MEM_freeN(values); +} + +TEST(heap, Rand1) { random_heap_helper(1, 1234); } +TEST(heap, Rand2) { random_heap_helper(2, 1234); } +TEST(heap, Rand100) { random_heap_helper(100, 4321); } + + +TEST(heap, ReInsertSimple) +{ + const int items_total = SIZE; + Heap *heap = BLI_heap_new(); + HeapNode **nodes = (HeapNode **)MEM_mallocN(sizeof(HeapNode *) * items_total, __func__); + for (int in = 0; in < items_total; in++) { + nodes[in] = BLI_heap_insert(heap, (float)in, SET_INT_IN_POINTER(in)); + } + for (int i = 0; i < items_total; i++) { + BLI_heap_node_value_update(heap, nodes[i], (float)(items_total + i)); + } + + for (int out_test = 0; out_test < items_total; out_test++) { + EXPECT_EQ(out_test, GET_INT_FROM_POINTER(BLI_heap_popmin(heap))); + } + + EXPECT_TRUE(BLI_heap_is_empty(heap)); + BLI_heap_free(heap, NULL); + MEM_freeN(nodes); +} + +static void random_heap_reinsert_helper( + const int items_total, + const int random_seed) +{ + Heap *heap = BLI_heap_new(); + HeapNode **nodes = (HeapNode **)MEM_mallocN(sizeof(HeapNode *) * items_total, __func__); + for (int in = 0; in < items_total; in++) { + nodes[in] = BLI_heap_insert(heap, (float)in, SET_INT_IN_POINTER(in)); + } + BLI_array_randomize(nodes, sizeof(HeapNode *), items_total, random_seed); + for (int i = 0; i < items_total; i++) { + BLI_heap_node_value_update(heap, nodes[i], (float)i); + } + EXPECT_TRUE(BLI_heap_is_valid(heap)); + + for (int out_test = 0; out_test < items_total; out_test++) { + HeapNode *node_top = BLI_heap_top(heap); + float out = BLI_heap_node_value(node_top); + EXPECT_EQ((float)out_test, out); + BLI_heap_popmin(heap); + } + EXPECT_TRUE(BLI_heap_is_empty(heap)); + BLI_heap_free(heap, NULL); + MEM_freeN(nodes); +} + +TEST(heap, ReInsertRandom1) { random_heap_reinsert_helper(1, 1234); } +TEST(heap, ReInsertRandom2) { random_heap_reinsert_helper(2, 1234); } +TEST(heap, ReInsertRandom100) { random_heap_reinsert_helper(100, 4321); } +TEST(heap, ReInsertRandom1024) { random_heap_reinsert_helper(1024, 9876); } +TEST(heap, ReInsertRandom2048) { random_heap_reinsert_helper(2048, 5321); } diff --git a/tests/gtests/blenlib/CMakeLists.txt b/tests/gtests/blenlib/CMakeLists.txt index e64bcf821de..f3b2e81c61a 100644 --- a/tests/gtests/blenlib/CMakeLists.txt +++ b/tests/gtests/blenlib/CMakeLists.txt @@ -44,6 +44,7 @@ BLENDER_TEST(BLI_array_store "bf_blenlib") BLENDER_TEST(BLI_array_utils "bf_blenlib") BLENDER_TEST(BLI_ghash "bf_blenlib") BLENDER_TEST(BLI_hash_mm2a "bf_blenlib") +BLENDER_TEST(BLI_heap "bf_blenlib") BLENDER_TEST(BLI_kdopbvh "bf_blenlib") BLENDER_TEST(BLI_listbase "bf_blenlib") BLENDER_TEST(BLI_math_base "bf_blenlib") |