From 113edac300ca54359d34c748c2b7057ba493ab4e Mon Sep 17 00:00:00 2001 From: Tavian Barnes Date: Thu, 1 Feb 2018 06:57:14 -0500 Subject: bftw: Fix the heap implementation There were two problems: - bubble_down() would always bubble the entry all the way down the heap, instead of stopping at the appropriate place - remove() may need to bubble the replacement entry *up* the heap, if it came from a different subtree --- bftw.c | 22 +++++++++++++++++++++- 1 file changed, 21 insertions(+), 1 deletion(-) diff --git a/bftw.c b/bftw.c index 82d216b..9f80c76 100644 --- a/bftw.c +++ b/bftw.c @@ -164,6 +164,10 @@ static void bftw_heap_bubble_down(struct bftw_cache *cache, struct bftw_dir *dir } } + if (bftw_heap_check(dir, child)) { + break; + } + bftw_heap_move(cache, child, i); i = ci; } @@ -171,6 +175,22 @@ static void bftw_heap_bubble_down(struct bftw_cache *cache, struct bftw_dir *dir bftw_heap_move(cache, dir, i); } +/** Bubble an entry up or down the heap. */ +static void bftw_heap_bubble(struct bftw_cache *cache, struct bftw_dir *dir) { + size_t i = dir->heap_index; + + if (i > 0) { + size_t pi = (i - 1)/2; + struct bftw_dir *parent = cache->heap[pi]; + if (!bftw_heap_check(parent, dir)) { + bftw_heap_bubble_up(cache, dir); + return; + } + } + + bftw_heap_bubble_down(cache, dir); +} + /** Increment a bftw_dir's reference count. */ static void bftw_dir_incref(struct bftw_cache *cache, struct bftw_dir *dir) { ++dir->refcount; @@ -209,7 +229,7 @@ static void bftw_cache_remove(struct bftw_cache *cache, struct bftw_dir *dir) { if (i != size) { struct bftw_dir *end = cache->heap[size]; end->heap_index = i; - bftw_heap_bubble_down(cache, end); + bftw_heap_bubble(cache, end); } } -- cgit v1.2.3