BLI_heap: add validation check, improve tests
authorCampbell Barton <ideasman42@gmail.com>
Sun, 29 Oct 2017 07:23:33 +0000 (18:23 +1100)
committerCampbell Barton <ideasman42@gmail.com>
Sun, 29 Oct 2017 07:23:33 +0000 (18:23 +1100)
Also minor readability changes, avoid running both heap_up/down
gives minor speedup too.

source/blender/blenlib/BLI_heap.h
source/blender/blenlib/intern/BLI_heap.c
tests/gtests/blenlib/BLI_heap_test.cc

index dcdbf53c0bbb16f93fed8196512602aa73029096..d3f6d44e164b5f72d8258881fb13d229f17e0cd4 100644 (file)
@@ -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__ */
index 4643b98f520a63f6be3340d97a81a71b9d9518ed..7c24934454138ac70b1fa03a195651d4b020a022 100644 (file)
@@ -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);
+}
+
 /** \} */
+
index e23e89b9cae52dfbffc9f5a57589d0fd41fc8772..89e271d516731bdc6c393418ef2ef91ebc2447a4 100644 (file)
@@ -158,18 +158,21 @@ TEST(heap, ReInsertSimple)
        MEM_freeN(nodes);
 }
 
-TEST(heap, ReInsertRandom)
+static void random_heap_reinsert_helper(
+        const int items_total,
+        const int random_seed)
 {
-       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);
+       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);
@@ -180,3 +183,9 @@ TEST(heap, ReInsertRandom)
        BLI_heap_free(heap, NULL);
        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); }