BLI_heap: minor changes to the API
Recent addition of 'reinsert' didn't match logic for ghash API. Rename to BLI_heap_node_value_update, also add BLI_heap_insert_or_update since it's a common operation.
This commit is contained in:
parent
336885beba
commit
3425732926
Notes:
blender-bot
2023-02-14 08:06:33 +01:00
Referenced by issue #53683, 2.79a release
|
@ -44,12 +44,12 @@ void BLI_heap_free(Heap *heap, HeapFreeFP ptrfreefp) ATTR_NONNULL(1);
|
|||
* duplicate values are allowed. */
|
||||
HeapNode *BLI_heap_insert(Heap *heap, float value, void *ptr) ATTR_NONNULL(1);
|
||||
|
||||
/* Insert or update */
|
||||
void BLI_heap_insert_or_update(Heap *heap, HeapNode **node_p, float value, void *ptr) ATTR_NONNULL(1, 2);
|
||||
|
||||
/* 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);
|
||||
|
||||
|
@ -62,6 +62,10 @@ HeapNode *BLI_heap_top(Heap *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1)
|
|||
/* Pop the top node off the heap and return it's pointer. */
|
||||
void *BLI_heap_popmin(Heap *heap) ATTR_NONNULL(1);
|
||||
|
||||
/* Update the priority in the heap (may be slow but generally faster than remove/insert). */
|
||||
void BLI_heap_node_value_update(Heap *heap, HeapNode *node, float value) ATTR_NONNULL(1, 2);
|
||||
void BLI_heap_node_value_update_ptr(Heap *heap, HeapNode *node, float value, void *ptr) ATTR_NONNULL(1, 2);
|
||||
|
||||
/* Return the value or pointer of a heap node. */
|
||||
float BLI_heap_node_value(HeapNode *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1);
|
||||
void *BLI_heap_node_ptr(HeapNode *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1);
|
||||
|
|
|
@ -275,6 +275,20 @@ HeapNode *BLI_heap_insert(Heap *heap, float value, void *ptr)
|
|||
return node;
|
||||
}
|
||||
|
||||
/**
|
||||
* Convenience function since this is a common pattern.
|
||||
*/
|
||||
void BLI_heap_insert_or_update(Heap *heap, HeapNode **node_p, float value, void *ptr)
|
||||
{
|
||||
if (*node_p == NULL) {
|
||||
*node_p = BLI_heap_insert(heap, value, ptr);
|
||||
}
|
||||
else {
|
||||
BLI_heap_node_value_update_ptr(heap, *node_p, value, ptr);
|
||||
}
|
||||
}
|
||||
|
||||
|
||||
bool BLI_heap_is_empty(Heap *heap)
|
||||
{
|
||||
return (heap->size == 0);
|
||||
|
@ -306,16 +320,6 @@ 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;
|
||||
|
@ -332,6 +336,28 @@ void BLI_heap_remove(Heap *heap, HeapNode *node)
|
|||
BLI_heap_popmin(heap);
|
||||
}
|
||||
|
||||
/**
|
||||
* Can be used to avoid #BLI_heap_remove, #BLI_heap_insert calls,
|
||||
* balancing the tree still has a performance cost,
|
||||
* but is often much less than remove/insert, difference is most noticable with large heaps.
|
||||
*/
|
||||
void BLI_heap_node_value_update(Heap *heap, HeapNode *node, float value)
|
||||
{
|
||||
if (value == node->value) {
|
||||
return;
|
||||
}
|
||||
node->value = value;
|
||||
/* Can be called in either order, makes no difference. */
|
||||
heap_up(heap, node->index);
|
||||
heap_down(heap, node->index);
|
||||
}
|
||||
|
||||
void BLI_heap_node_value_update_ptr(Heap *heap, HeapNode *node, float value, void *ptr)
|
||||
{
|
||||
node->ptr = ptr;
|
||||
BLI_heap_node_value_update(heap, node, value);
|
||||
}
|
||||
|
||||
float BLI_heap_node_value(HeapNode *node)
|
||||
{
|
||||
return node->value;
|
||||
|
|
|
@ -226,12 +226,7 @@ static void polyedge_beauty_cost_update_single(
|
|||
* Actually, FLT_EPSILON is too small in some cases, 1e-6f seems to work OK hopefully?
|
||||
* See T43578, T49478. */
|
||||
if (cost < -1e-6f) {
|
||||
if (eheap_table[i]) {
|
||||
BLI_heap_reinsert(eheap, eheap_table[i], cost);
|
||||
}
|
||||
else {
|
||||
eheap_table[i] = BLI_heap_insert(eheap, cost, e);
|
||||
}
|
||||
BLI_heap_insert_or_update(eheap, &eheap_table[i], cost, e);
|
||||
}
|
||||
else {
|
||||
if (eheap_table[i]) {
|
||||
|
|
|
@ -337,12 +337,7 @@ static void bm_decim_build_edge_cost_single(
|
|||
}
|
||||
}
|
||||
|
||||
if (eheap_table[BM_elem_index_get(e)]) {
|
||||
BLI_heap_reinsert(eheap, eheap_table[BM_elem_index_get(e)], cost);
|
||||
}
|
||||
else {
|
||||
eheap_table[BM_elem_index_get(e)] = BLI_heap_insert(eheap, cost, e);
|
||||
}
|
||||
BLI_heap_insert_or_update(eheap, &eheap_table[BM_elem_index_get(e)], cost, e);
|
||||
return;
|
||||
|
||||
clear:
|
||||
|
|
|
@ -146,7 +146,7 @@ TEST(heap, ReInsertSimple)
|
|||
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));
|
||||
BLI_heap_node_value_update(heap, nodes[i], (float)(items_total + i));
|
||||
}
|
||||
|
||||
for (int out_test = 0; out_test < items_total; out_test++) {
|
||||
|
@ -168,7 +168,7 @@ TEST(heap, ReInsertRandom)
|
|||
}
|
||||
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);
|
||||
BLI_heap_node_value_update(heap, nodes[i], (float)i);
|
||||
}
|
||||
for (int out_test = 0; out_test < items_total; out_test++) {
|
||||
HeapNode *node_top = BLI_heap_top(heap);
|
||||
|
|
Loading…
Reference in New Issue