Blender V5.3
BLI_heap_test.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: Apache-2.0 */
4
5#include "testing/testing.h"
6#include <cstring>
7
8#include "MEM_guardedalloc.h"
9
10#include "BLI_compiler_attrs.hh"
11#include "BLI_heap.hh"
12#include "BLI_rand_c.hh"
13#include "BLI_utildefines.hh"
14
15namespace blender {
16
17#define SIZE 1024
18
19static void range_fl(float *array_tar, const int size)
20{
21 float *array_pt = array_tar + (size - 1);
22 int i = size;
23 while (i--) {
24 *(array_pt--) = float(i);
25 }
26}
27
28TEST(heap, Empty)
29{
30 Heap *heap;
31
32 heap = BLI_heap_new();
34 EXPECT_EQ(BLI_heap_len(heap), 0);
35 BLI_heap_free(heap, nullptr);
36}
37
38TEST(heap, One)
39{
40 Heap *heap;
41 const char *in = "test";
42
43 heap = BLI_heap_new();
44
45 BLI_heap_insert(heap, 0.0f, const_cast<char *>(in));
47 EXPECT_EQ(BLI_heap_len(heap), 1);
50 EXPECT_EQ(BLI_heap_len(heap), 0);
51 BLI_heap_free(heap, nullptr);
52}
53
54TEST(heap, Range)
55{
56 const int items_total = SIZE;
57 Heap *heap = BLI_heap_new();
58 for (int in = 0; in < items_total; in++) {
59 BLI_heap_insert(heap, float(in), POINTER_FROM_INT(in));
60 }
61 for (int out_test = 0; out_test < items_total; out_test++) {
63 }
65 BLI_heap_free(heap, nullptr);
66}
67
68TEST(heap, RangeReverse)
69{
70 const int items_total = SIZE;
71 Heap *heap = BLI_heap_new();
72 for (int in = 0; in < items_total; in++) {
73 BLI_heap_insert(heap, float(-in), POINTER_FROM_INT(-in));
74 }
75 for (int out_test = items_total - 1; out_test >= 0; out_test--) {
76 EXPECT_EQ(-out_test, POINTER_AS_INT(BLI_heap_pop_min(heap)));
77 }
79 BLI_heap_free(heap, nullptr);
80}
81
82TEST(heap, RangeRemove)
83{
84 const int items_total = SIZE;
85 Heap *heap = BLI_heap_new();
86 HeapNode **nodes = MEM_new_array_uninitialized<HeapNode *>(size_t(items_total), __func__);
87 for (int in = 0; in < items_total; in++) {
88 nodes[in] = BLI_heap_insert(heap, float(in), POINTER_FROM_INT(in));
89 }
90 for (int i = 0; i < items_total; i += 2) {
91 BLI_heap_remove(heap, nodes[i]);
92 nodes[i] = nullptr;
93 }
94 for (int out_test = 1; out_test < items_total; out_test += 2) {
96 }
98 BLI_heap_free(heap, nullptr);
99 MEM_delete(nodes);
100}
101
102TEST(heap, Duplicates)
103{
104 const int items_total = SIZE;
105 Heap *heap = BLI_heap_new();
106 for (int in = 0; in < items_total; in++) {
107 BLI_heap_insert(heap, 1.0f, nullptr);
108 }
109 for (int out_test = 0; out_test < items_total; out_test++) {
111 }
113 BLI_heap_free(heap, nullptr);
114}
115
116static void random_heap_helper(const int items_total, const int random_seed)
117{
118 Heap *heap = BLI_heap_new();
119 float *values = MEM_new_array_uninitialized<float>(size_t(items_total), __func__);
120 range_fl(values, items_total);
121 BLI_array_randomize(values, sizeof(float), items_total, random_seed);
122 for (int i = 0; i < items_total; i++) {
123 BLI_heap_insert(heap, values[i], POINTER_FROM_INT(int(values[i])));
124 }
125 for (int out_test = 0; out_test < items_total; out_test++) {
126 EXPECT_EQ(out_test, POINTER_AS_INT(BLI_heap_pop_min(heap)));
127 }
129 BLI_heap_free(heap, nullptr);
130 MEM_delete(values);
131}
132
133TEST(heap, Rand1)
134{
135 random_heap_helper(1, 1234);
136}
137TEST(heap, Rand2)
138{
139 random_heap_helper(2, 1234);
140}
141TEST(heap, Rand100)
142{
143 random_heap_helper(100, 4321);
144}
145
146TEST(heap, ReInsertSimple)
147{
148 const int items_total = SIZE;
149 Heap *heap = BLI_heap_new();
150 HeapNode **nodes = MEM_new_array_uninitialized<HeapNode *>(size_t(items_total), __func__);
151 for (int in = 0; in < items_total; in++) {
152 nodes[in] = BLI_heap_insert(heap, float(in), POINTER_FROM_INT(in));
153 }
154 for (int i = 0; i < items_total; i++) {
155 BLI_heap_node_value_update(heap, nodes[i], float(items_total + i));
156 }
157
158 for (int out_test = 0; out_test < items_total; out_test++) {
159 EXPECT_EQ(out_test, POINTER_AS_INT(BLI_heap_pop_min(heap)));
160 }
161
163 BLI_heap_free(heap, nullptr);
164 MEM_delete(nodes);
165}
166
167static void random_heap_reinsert_helper(const int items_total, const int random_seed)
168{
169 Heap *heap = BLI_heap_new();
170 HeapNode **nodes = MEM_new_array_uninitialized<HeapNode *>(size_t(items_total), __func__);
171 for (int in = 0; in < items_total; in++) {
172 nodes[in] = BLI_heap_insert(heap, float(in), POINTER_FROM_INT(in));
173 }
174 BLI_array_randomize(nodes, sizeof(HeapNode *), items_total, random_seed);
175 for (int i = 0; i < items_total; i++) {
176 BLI_heap_node_value_update(heap, nodes[i], float(i));
177 }
179
180 for (int out_test = 0; out_test < items_total; out_test++) {
181 HeapNode *node_top = BLI_heap_top(heap);
182 float out = BLI_heap_node_value(node_top);
184 EXPECT_EQ(float(out_test), out);
185 BLI_heap_pop_min(heap);
186 }
188 BLI_heap_free(heap, nullptr);
189 MEM_delete(nodes);
190}
191
192TEST(heap, ReInsertRandom1)
193{
195}
196TEST(heap, ReInsertRandom2)
197{
199}
200TEST(heap, ReInsertRandom100)
201{
203}
204TEST(heap, ReInsertRandom1024)
205{
206 random_heap_reinsert_helper(1024, 9876);
207}
208TEST(heap, ReInsertRandom2048)
209{
210 random_heap_reinsert_helper(2048, 5321);
211}
212
213} // namespace blender
A min-heap / priority queue ADT.
#define SIZE
Random number functions.
Read Blender memory allocation and freeing.
#define POINTER_FROM_INT(i)
#define POINTER_AS_INT(i)
#define EXPECT_FALSE(result)
#define EXPECT_TRUE(result)
BMesh Iterators.
void void bool BLI_heap_is_empty(const Heap *heap) ATTR_NONNULL(1)
Definition BLI_heap.cc:271
unsigned int BLI_heap_len(const Heap *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
Definition BLI_heap.cc:276
HeapNode * BLI_heap_top(const Heap *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
Definition BLI_heap.cc:281
void * MEM_new_array_uninitialized(size_t len, size_t size, const char *str) ATTR_WARN_UNUSED_RESULT ATTR_ALLOC_SIZE(1
void void BLI_heap_remove(Heap *heap, HeapNode *node) ATTR_NONNULL(1
Definition BLI_heap.cc:309
void BLI_heap_free(Heap *heap, HeapFreeFP ptrfreefp) ATTR_NONNULL(1)
Definition BLI_heap.cc:193
void * BLI_heap_pop_min(Heap *heap) ATTR_NONNULL(1)
Definition BLI_heap.cc:293
void BLI_array_randomize(void *data, unsigned int elem_size, unsigned int elem_num, unsigned int seed)
Definition rand.cc:158
TEST(array_store, Nop)
float BLI_heap_top_value(const Heap *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
Definition BLI_heap.cc:286
HeapNode * BLI_heap_insert(Heap *heap, float value, void *ptr) ATTR_NONNULL(1)
Definition BLI_heap.cc:236
static void random_heap_helper(const int items_total, const int random_seed)
EXPECT_EQ(BLI_expr_pylike_eval(expr, nullptr, 0, &result), EXPR_PYLIKE_INVALID)
void BLI_heap_node_value_update(Heap *heap, HeapNode *node, float value) ATTR_NONNULL(1
Definition BLI_heap.cc:324
static void range_fl(float *array_tar, const int size)
Heap * BLI_heap_new() ATTR_WARN_UNUSED_RESULT
Definition BLI_heap.cc:188
bool BLI_heap_is_valid(const Heap *heap)
Definition BLI_heap.cc:380
static void random_heap_reinsert_helper(const int items_total, const int random_seed)
void void float BLI_heap_node_value(const HeapNode *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
Definition BLI_heap.cc:349