From 430a991cd53273c2869e9b37e42438f4e827d1d0 Mon Sep 17 00:00:00 2001 From: Vsevolod Stakhov Date: Fri, 8 Apr 2016 21:29:50 +0100 Subject: [PATCH] [Fix] Fix couple of issues with heap code --- src/libutil/heap.c | 27 +++++++++++++++++---------- 1 file changed, 17 insertions(+), 10 deletions(-) diff --git a/src/libutil/heap.c b/src/libutil/heap.c index fe88cca88..ba1b44793 100644 --- a/src/libutil/heap.c +++ b/src/libutil/heap.c @@ -22,9 +22,9 @@ struct rspamd_min_heap { }; #define heap_swap(h,e1,e2) do { \ - gpointer telt = (h)->ar->pdata[(e1)->idx]; \ - (h)->ar->pdata[(e1)->idx] = (h)->ar->pdata[(e2)->idx]; \ - (h)->ar->pdata[(e2)->idx] = telt; \ + gpointer telt = (h)->ar->pdata[(e1)->idx - 1]; \ + (h)->ar->pdata[(e1)->idx - 1] = (h)->ar->pdata[(e2)->idx - 1]; \ + (h)->ar->pdata[(e2)->idx - 1] = telt; \ guint tidx = (e1)->idx; \ (e1)->idx = (e2)->idx; \ (e2)->idx = tidx; \ @@ -41,8 +41,8 @@ rspamd_min_heap_swim (struct rspamd_min_heap *heap, { struct rspamd_min_heap_elt *parent; - while (elt->idx > 0) { - parent = g_ptr_array_index (heap->ar, elt->idx / 2); + while (elt->idx > 1) { + parent = g_ptr_array_index (heap->ar, elt->idx / 2 - 1); if (parent->pri > elt->pri) { heap_swap (heap, elt, parent); @@ -62,9 +62,9 @@ rspamd_min_heap_sink (struct rspamd_min_heap *heap, { struct rspamd_min_heap_elt *c1, *c2, *m; - while (elt->idx < heap->ar->len - 1) { - c1 = g_ptr_array_index (heap->ar, elt->idx * 2); - c2 = g_ptr_array_index (heap->ar, elt->idx * 2 + 1); + while (elt->idx * 2 < heap->ar->len) { + c1 = g_ptr_array_index (heap->ar, elt->idx * 2 - 1); + c2 = g_ptr_array_index (heap->ar, elt->idx * 2); m = min_elt (c1, c2); if (elt->pri > m->pri) { @@ -74,6 +74,13 @@ rspamd_min_heap_sink (struct rspamd_min_heap *heap, break; } } + + if (elt->idx * 2 - 1 < heap->ar->len) { + m = g_ptr_array_index (heap->ar, elt->idx * 2 - 1); + if (elt->pri > m->pri) { + heap_swap (heap, elt, m); + } + } } struct rspamd_min_heap * @@ -95,7 +102,7 @@ rspamd_min_heap_push (struct rspamd_min_heap *heap, g_assert (elt != NULL); /* Add to the end */ - elt->idx = heap->ar->len; + elt->idx = heap->ar->len + 1; g_ptr_array_add (heap->ar, elt); /* Now swim it up */ rspamd_min_heap_swim (heap, elt); @@ -129,7 +136,7 @@ rspamd_min_heap_update_elt (struct rspamd_min_heap *heap, guint oldpri; g_assert (heap != NULL); - g_assert (elt->idx >= 0 && elt->idx < heap->ar->len); + g_assert (elt->idx > 0 && elt->idx <= heap->ar->len); oldpri = elt->pri; -- 2.39.5