BLI_hash: add BLI_heap_reinsert
Allows avoiding remove/insert calls.
This commit is contained in:
parent
b84e3dc7f3
commit
4af1af70ad
Notes:
blender-bot
2023-02-14 06:17:15 +01:00
Referenced by issue #53683, 2.79a release
|
@ -47,6 +47,9 @@ HeapNode *BLI_heap_insert(Heap *heap, float value, void *ptr) ATTR_NONNULL
|
|||
/* Remove a heap node. */
|
||||
void BLI_heap_remove(Heap *heap, HeapNode *node) ATTR_NONNULL(1, 2);
|
||||
|
||||
/* Set new value for existing node. */
|
||||
void BLI_heap_reinsert(Heap *heap, HeapNode *node, float value);
|
||||
|
||||
/* Return 0 if the heap is empty, 1 otherwise. */
|
||||
bool BLI_heap_is_empty(Heap *heap) ATTR_NONNULL(1);
|
||||
|
||||
|
|
|
@ -306,6 +306,16 @@ void *BLI_heap_popmin(Heap *heap)
|
|||
return ptr;
|
||||
}
|
||||
|
||||
void BLI_heap_reinsert(Heap *heap, HeapNode *node, float value)
|
||||
{
|
||||
if (value == node->value) {
|
||||
return;
|
||||
}
|
||||
node->value = value;
|
||||
heap_up(heap, node->index);
|
||||
heap_down(heap, node->index);
|
||||
}
|
||||
|
||||
void BLI_heap_remove(Heap *heap, HeapNode *node)
|
||||
{
|
||||
uint i = node->index;
|
||||
|
|
|
@ -135,3 +135,48 @@ static void random_heap_helper(
|
|||
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_reinsert(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);
|
||||
}
|
||||
|
||||
TEST(heap, ReInsertRandom)
|
||||
{
|
||||
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));
|
||||
}
|
||||
BLI_array_randomize(nodes, sizeof(HeapNode *), items_total, 1234);
|
||||
for (int i = 0; i < items_total; i++) {
|
||||
BLI_heap_reinsert(heap, nodes[i], (float)i);
|
||||
}
|
||||
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);
|
||||
}
|
||||
|
|
Loading…
Reference in New Issue