BLI_heap_test.cc

Go to the documentation of this file.

/* SPDX-FileCopyrightText: 2023 Blender Authors
 *
 * SPDX-License-Identifier: Apache-2.0 */
 
#include "testing/testing.h"
#include <cstring>
 
#include "MEM_guardedalloc.h"
 
#include "BLI_compiler_attrs.h"
#include "BLI_heap.h"
#include "BLI_rand.h"
#include "BLI_utildefines.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_len(heap), 0);
  BLI_heap_free(heap, nullptr);
}
 
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_len(heap), 1);
  EXPECT_EQ(in, BLI_heap_pop_min(heap));
  EXPECT_TRUE(BLI_heap_is_empty(heap));
  EXPECT_EQ(BLI_heap_len(heap), 0);
  BLI_heap_free(heap, nullptr);
}
 
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), POINTER_FROM_INT(in));
  }
  for (int out_test = 0; out_test < items_total; out_test++) {
    EXPECT_EQ(out_test, POINTER_AS_INT(BLI_heap_pop_min(heap)));
  }
  EXPECT_TRUE(BLI_heap_is_empty(heap));
  BLI_heap_free(heap, nullptr);
}
 
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), POINTER_FROM_INT(-in));
  }
  for (int out_test = items_total - 1; out_test >= 0; out_test--) {
    EXPECT_EQ(-out_test, POINTER_AS_INT(BLI_heap_pop_min(heap)));
  }
  EXPECT_TRUE(BLI_heap_is_empty(heap));
  BLI_heap_free(heap, nullptr);
}
 
TEST(heap, RangeRemove)
{
  const int items_total = SIZE;
  Heap *heap = BLI_heap_new();
  HeapNode **nodes = MEM_malloc_arrayN<HeapNode *>(size_t(items_total), __func__);
  for (int in = 0; in < items_total; in++) {
    nodes[in] = BLI_heap_insert(heap, float(in), POINTER_FROM_INT(in));
  }
  for (int i = 0; i < items_total; i += 2) {
    BLI_heap_remove(heap, nodes[i]);
    nodes[i] = nullptr;
  }
  for (int out_test = 1; out_test < items_total; out_test += 2) {
    EXPECT_EQ(out_test, POINTER_AS_INT(BLI_heap_pop_min(heap)));
  }
  EXPECT_TRUE(BLI_heap_is_empty(heap));
  BLI_heap_free(heap, nullptr);
  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, nullptr);
  }
  for (int out_test = 0; out_test < items_total; out_test++) {
    EXPECT_EQ(0, POINTER_AS_INT(BLI_heap_pop_min(heap)));
  }
  EXPECT_TRUE(BLI_heap_is_empty(heap));
  BLI_heap_free(heap, nullptr);
}
 
static void random_heap_helper(const int items_total, const int random_seed)
{
  Heap *heap = BLI_heap_new();
  float *values = MEM_malloc_arrayN<float>(size_t(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], POINTER_FROM_INT(int(values[i])));
  }
  for (int out_test = 0; out_test < items_total; out_test++) {
    EXPECT_EQ(out_test, POINTER_AS_INT(BLI_heap_pop_min(heap)));
  }
  EXPECT_TRUE(BLI_heap_is_empty(heap));
  BLI_heap_free(heap, nullptr);
  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 = MEM_malloc_arrayN<HeapNode *>(size_t(items_total), __func__);
  for (int in = 0; in < items_total; in++) {
    nodes[in] = BLI_heap_insert(heap, float(in), POINTER_FROM_INT(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, POINTER_AS_INT(BLI_heap_pop_min(heap)));
  }
 
  EXPECT_TRUE(BLI_heap_is_empty(heap));
  BLI_heap_free(heap, nullptr);
  MEM_freeN(nodes);
}
 
static void random_heap_reinsert_helper(const int items_total, const int random_seed)
{
  Heap *heap = BLI_heap_new();
  HeapNode **nodes = MEM_malloc_arrayN<HeapNode *>(size_t(items_total), __func__);
  for (int in = 0; in < items_total; in++) {
    nodes[in] = BLI_heap_insert(heap, float(in), POINTER_FROM_INT(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(out, BLI_heap_top_value(heap));
    EXPECT_EQ(float(out_test), out);
    BLI_heap_pop_min(heap);
  }
  EXPECT_TRUE(BLI_heap_is_empty(heap));
  BLI_heap_free(heap, nullptr);
  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);
}