Blender  V3.3
BLI_heap_simple_test.cc
Go to the documentation of this file.
1 /* SPDX-License-Identifier: Apache-2.0 */
2 
3 #include "testing/testing.h"
4 #include <cstring>
5 
6 #include "MEM_guardedalloc.h"
7 
8 #include "BLI_compiler_attrs.h"
9 #include "BLI_heap_simple.h"
10 #include "BLI_rand.h"
11 #include "BLI_sys_types.h"
12 #include "BLI_utildefines.h"
13 
14 #define SIZE 1024
15 
16 static void range_fl(float *array_tar, const int size)
17 {
18  float *array_pt = array_tar + (size - 1);
19  int i = size;
20  while (i--) {
21  *(array_pt--) = (float)i;
22  }
23 }
24 
25 TEST(heap, SimpleEmpty)
26 {
27  HeapSimple *heap;
28 
29  heap = BLI_heapsimple_new();
30  EXPECT_TRUE(BLI_heapsimple_is_empty(heap));
31  EXPECT_EQ(BLI_heapsimple_len(heap), 0);
32  BLI_heapsimple_free(heap, nullptr);
33 }
34 
35 TEST(heap, SimpleOne)
36 {
37  HeapSimple *heap;
38  const char *in = "test";
39 
40  heap = BLI_heapsimple_new();
41 
42  BLI_heapsimple_insert(heap, 0.0f, (void *)in);
43  EXPECT_FALSE(BLI_heapsimple_is_empty(heap));
44  EXPECT_EQ(BLI_heapsimple_len(heap), 1);
46  EXPECT_TRUE(BLI_heapsimple_is_empty(heap));
47  EXPECT_EQ(BLI_heapsimple_len(heap), 0);
48  BLI_heapsimple_free(heap, nullptr);
49 }
50 
51 TEST(heap, SimpleRange)
52 {
53  const int items_total = SIZE;
55  for (int in = 0; in < items_total; in++) {
56  BLI_heapsimple_insert(heap, (float)in, POINTER_FROM_INT(in));
57  }
58  for (int out_test = 0; out_test < items_total; out_test++) {
60  }
61  EXPECT_TRUE(BLI_heapsimple_is_empty(heap));
62  BLI_heapsimple_free(heap, nullptr);
63 }
64 
65 TEST(heap, SimpleRangeReverse)
66 {
67  const int items_total = SIZE;
69  for (int in = 0; in < items_total; in++) {
70  BLI_heapsimple_insert(heap, (float)-in, POINTER_FROM_INT(-in));
71  }
72  for (int out_test = items_total - 1; out_test >= 0; out_test--) {
74  }
75  EXPECT_TRUE(BLI_heapsimple_is_empty(heap));
76  BLI_heapsimple_free(heap, nullptr);
77 }
78 
79 TEST(heap, SimpleDuplicates)
80 {
81  const int items_total = SIZE;
83  for (int in = 0; in < items_total; in++) {
84  BLI_heapsimple_insert(heap, 1.0f, nullptr);
85  }
86  for (int out_test = 0; out_test < items_total; out_test++) {
88  }
89  EXPECT_TRUE(BLI_heapsimple_is_empty(heap));
90  BLI_heapsimple_free(heap, nullptr);
91 }
92 
93 static void random_heapsimple_helper(const int items_total, const int random_seed)
94 {
96  float *values = (float *)MEM_mallocN(sizeof(float) * items_total, __func__);
97  range_fl(values, items_total);
98  BLI_array_randomize(values, sizeof(float), items_total, random_seed);
99  for (int i = 0; i < items_total; i++) {
100  BLI_heapsimple_insert(heap, values[i], POINTER_FROM_INT((int)values[i]));
101  }
102  for (int out_test = 0; out_test < items_total; out_test++) {
104  }
105  EXPECT_TRUE(BLI_heapsimple_is_empty(heap));
106  BLI_heapsimple_free(heap, nullptr);
107  MEM_freeN(values);
108 }
109 
110 TEST(heap, SimpleRand1)
111 {
112  random_heapsimple_helper(1, 1234);
113 }
114 TEST(heap, SimpleRand2)
115 {
116  random_heapsimple_helper(2, 1234);
117 }
118 TEST(heap, SimpleRand100)
119 {
120  random_heapsimple_helper(100, 4321);
121 }
EXPECT_EQ(BLI_expr_pylike_eval(expr, nullptr, 0, &result), EXPR_PYLIKE_INVALID)
A min-heap / priority queue ADT.
void BLI_heapsimple_free(HeapSimple *heap, HeapSimpleFreeFP ptrfreefp) ATTR_NONNULL(1)
HeapSimple * BLI_heapsimple_new(void) ATTR_WARN_UNUSED_RESULT
void * BLI_heapsimple_pop_min(HeapSimple *heap) ATTR_NONNULL(1)
bool BLI_heapsimple_is_empty(const HeapSimple *heap) ATTR_NONNULL(1)
uint BLI_heapsimple_len(const HeapSimple *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
void BLI_heapsimple_insert(HeapSimple *heap, float value, void *ptr) ATTR_NONNULL(1)
static void random_heapsimple_helper(const int items_total, const int random_seed)
#define SIZE
static void range_fl(float *array_tar, const int size)
TEST(heap, SimpleEmpty)
Random number functions.
void BLI_array_randomize(void *data, unsigned int elem_size, unsigned int elem_num, unsigned int seed)
Definition: rand.cc:188
#define POINTER_FROM_INT(i)
#define POINTER_AS_INT(i)
Read Guarded memory(de)allocation.
static DBVT_INLINE btScalar size(const btDbvtVolume &a)
Definition: btDbvt.cpp:52
void(* MEM_freeN)(void *vmemh)
Definition: mallocn.c:27
void *(* MEM_mallocN)(size_t len, const char *str)
Definition: mallocn.c:33