From: Florian Forster <octo@leeloo.lan.home.verplant.org>
Date: Thu, 19 Aug 2010 13:00:26 +0000 (+0200)
Subject: src/utils_heap.c: Fix calculation of the parent's index.
X-Git-Tag: collectd-4.9.4~21
X-Git-Url: https://git.octo.it/?p=collectd.git;a=commitdiff_plain;h=69149f2f18463f82a567ca27ff1eb2fc4bb8dc3d

src/utils_heap.c: Fix calculation of the parent's index.

This resulted in the "upwards" reheap function to return prematurely,
leaving the heap condition violated.
---

diff --git a/src/utils_heap.c b/src/utils_heap.c
index 086649a1..f8f74058 100644
--- a/src/utils_heap.c
+++ b/src/utils_heap.c
@@ -96,7 +96,7 @@ static void reheap (c_heap_t *h, size_t root, enum reheap_direction dir)
     return;
 
   if (dir == DIR_UP)
-    reheap (h, root / 2, dir);
+    reheap (h, (root - 1) / 2, dir);
   else if (dir == DIR_DOWN)
     reheap (h, min, dir);
 } /* void reheap */
@@ -140,6 +140,8 @@ void c_heap_destroy (c_heap_t *h)
 
 int c_heap_insert (c_heap_t *h, void *ptr)
 {
+  size_t index;
+
   if ((h == NULL) || (ptr == NULL))
     return (-EINVAL);
 
@@ -162,11 +164,12 @@ int c_heap_insert (c_heap_t *h, void *ptr)
   }
 
   /* Insert the new node as a leaf. */
-  h->list[h->list_len] = ptr;
+  index = h->list_len;
+  h->list[index] = ptr;
   h->list_len++;
 
   /* Reorganize the heap from bottom up. */
-  reheap (h, /* parent of this node = */ (h->list_len - 1) / 2, DIR_UP);
+  reheap (h, /* parent of this node = */ (index - 1) / 2, DIR_UP);
   
   pthread_mutex_unlock (&h->lock);
   return (0);