Reduced ctz traverse runtime by 2x

Unfortunately for us, the ctz skip-list does not offer very much benefit
for full traversals. Since the information about which blocks are in
use are spread throughout the file, we can't use the fast-lanes
embedded in the skip-list without missing blocks.

However, it turns out we can at least use the 2nd level of the skip-list
without missing any blocks. From an asymptotic analysis, a constant speed
up isn't interesting, but from a pragmatic perspective, a 2x speedup is
not bad.

1 files changed, 12 insertions, 2 deletions

diff --git a/lfs.c b/lfs.c
index 4fe66bb..ccc623b 100644
--- a/lfs.c
+++ b/lfs.c
@@ -1195,12 +1195,22 @@ static int lfs_ctz_traverse(lfs_t *lfs,
             return 0;
         }
 
-        err = lfs_cache_read(lfs, rcache, pcache, head, 0, &head, 4);
+        lfs_block_t heads[2];
+        int count = 2 - (index & 1);
+        err = lfs_cache_read(lfs, rcache, pcache, head, 0, &heads, count*4);
         if (err) {
             return err;
         }
 
-        index -= 1;
+        for (int i = 0; i < count-1; i++) {
+            err = cb(data, heads[i]);
+            if (err) {
+                return err;
+            }
+        }
+
+        head = heads[count-1];
+        index -= count;
     }
 }