summaryrefslogtreecommitdiffstats
path: root/bftw.c
diff options
context:
space:
mode:
authorTavian Barnes <tavianator@tavianator.com>2018-02-01 06:57:14 -0500
committerTavian Barnes <tavianator@tavianator.com>2018-02-01 06:57:14 -0500
commit113edac300ca54359d34c748c2b7057ba493ab4e (patch)
treeda6999455ab581044f5fbd201a77b1f343f74ed6 /bftw.c
parent54696b2e975c8ca9979743be98187d733ce64de4 (diff)
downloadbfs-113edac300ca54359d34c748c2b7057ba493ab4e.tar.xz
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
Diffstat (limited to 'bftw.c')
-rw-r--r--bftw.c22
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);
}
}