summaryrefslogtreecommitdiffstats
path: root/bftw.c
diff options
context:
space:
mode:
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);
}
}