From 512b879241d79bf91f70eecdc97944505d64bf6e Mon Sep 17 00:00:00 2001
From: Campbell Barton <ideasman42@gmail.com>
Date: Sun, 29 Oct 2017 18:23:33 +1100
Subject: BLI_heap: add validation check, improve tests

Also minor readability changes, avoid running both heap_up/down
gives minor speedup too.
---
 source/blender/blenlib/BLI_heap.h        |  2 +
 source/blender/blenlib/intern/BLI_heap.c | 67 ++++++++++++++++++++++++--------
 2 files changed, 53 insertions(+), 16 deletions(-)

(limited to 'source')

diff --git a/source/blender/blenlib/BLI_heap.h b/source/blender/blenlib/BLI_heap.h
index dcdbf53c0bb..d3f6d44e164 100644
--- a/source/blender/blenlib/BLI_heap.h
+++ b/source/blender/blenlib/BLI_heap.h
@@ -50,5 +50,7 @@ void            BLI_heap_node_value_update_ptr(Heap *heap, HeapNode *node, float
 /* Return the value or pointer of a heap node. */
 float           BLI_heap_node_value(const HeapNode *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1);
 void           *BLI_heap_node_ptr(const HeapNode *heap) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(1);
+/* only for gtest */
+bool            BLI_heap_is_valid(const Heap *heap);
 
 #endif  /* __BLI_HEAP_H__ */
diff --git a/source/blender/blenlib/intern/BLI_heap.c b/source/blender/blenlib/intern/BLI_heap.c
index 4643b98f520..7c249344541 100644
--- a/source/blender/blenlib/intern/BLI_heap.c
+++ b/source/blender/blenlib/intern/BLI_heap.c
@@ -110,10 +110,11 @@ static void heap_down(Heap *heap, uint i)
 	while (1) {
 		const uint l = HEAP_LEFT(i);
 		const uint r = HEAP_RIGHT(i);
-		uint smallest;
-
-		smallest = ((l < size) && HEAP_COMPARE(heap->tree[l], heap->tree[i])) ? l : i;
+		uint smallest = i;
 
+		if ((l < size) && HEAP_COMPARE(heap->tree[l], heap->tree[smallest])) {
+			smallest = l;
+		}
 		if ((r < size) && HEAP_COMPARE(heap->tree[r], heap->tree[smallest])) {
 			smallest = r;
 		}
@@ -321,10 +322,10 @@ HeapNode *BLI_heap_top(const Heap *heap)
  */
 void *BLI_heap_popmin(Heap *heap)
 {
-	void *ptr = heap->tree[0]->ptr;
-
 	BLI_assert(heap->size != 0);
 
+	void *ptr = heap->tree[0]->ptr;
+
 	heap_node_free(heap, heap->tree[0]);
 
 	if (--heap->size) {
@@ -337,13 +338,12 @@ void *BLI_heap_popmin(Heap *heap)
 
 void BLI_heap_remove(Heap *heap, HeapNode *node)
 {
-	uint i = node->index;
-
 	BLI_assert(heap->size != 0);
 
+	uint i = node->index;
+
 	while (i > 0) {
 		uint p = HEAP_PARENT(i);
-
 		heap_swap(heap, p, i);
 		i = p;
 	}
@@ -358,19 +358,27 @@ void BLI_heap_remove(Heap *heap, HeapNode *node)
  */
 void BLI_heap_node_value_update(Heap *heap, HeapNode *node, float value)
 {
-	if (value == node->value) {
-		return;
+	if (value < node->value) {
+		node->value = value;
+		heap_up(heap, node->index);
+	}
+	else if (value > node->value) {
+		node->value = value;
+		heap_down(heap, node->index);
 	}
-	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);
+	node->ptr = ptr; /* only difference */
+	if (value < node->value) {
+		node->value = value;
+		heap_up(heap, node->index);
+	}
+	else if (value > node->value) {
+		node->value = value;
+		heap_down(heap, node->index);
+	}
 }
 
 float BLI_heap_node_value(const HeapNode *node)
@@ -383,4 +391,31 @@ void *BLI_heap_node_ptr(const HeapNode *node)
 	return node->ptr;
 }
 
+static bool heap_is_minheap(const Heap *heap, uint root)
+{
+	if (root < heap->size) {
+		const uint l = HEAP_LEFT(root);
+		if (l < heap->size) {
+			if (HEAP_COMPARE(heap->tree[l], heap->tree[root]) || !heap_is_minheap(heap, l)) {
+				return false;
+			}
+		}
+		const uint r = HEAP_RIGHT(root);
+		if (r < heap->size) {
+			if (HEAP_COMPARE(heap->tree[r], heap->tree[root]) || !heap_is_minheap(heap, r)) {
+				return false;
+			}
+		}
+	}
+	return true;
+}
+/**
+ * Only for checking internal errors (gtest).
+ */
+bool BLI_heap_is_valid(const Heap *heap)
+{
+	return heap_is_minheap(heap, 0);
+}
+
 /** \} */
+
-- 
cgit v1.2.3