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

1 files changed, 21 insertions, 1 deletions

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);
 	}
 }