diff options
author | Tavian Barnes <tavianator@tavianator.com> | 2018-02-01 06:57:14 -0500 |
---|---|---|
committer | Tavian Barnes <tavianator@tavianator.com> | 2018-02-01 06:57:14 -0500 |
commit | 113edac300ca54359d34c748c2b7057ba493ab4e (patch) | |
tree | da6999455ab581044f5fbd201a77b1f343f74ed6 /bftw.c | |
parent | 54696b2e975c8ca9979743be98187d733ce64de4 (diff) | |
download | bfs-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.c | 22 |
1 files changed, 21 insertions, 1 deletions
@@ -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); } } |