Added full dir list and rudimentary block allocator

In writing the initial allocator, I ran into the rather
difficult problem of trying to iterate through the entire
filesystem cheaply and with only constant memory consumption
(which prohibits recursive functions).

The solution was to simply thread all directory blocks onto a
massive linked-list that spans the entire filesystem.

With the linked-list it was easy to create a traverse function
for all blocks in use on the filesystem (which has potential
for other utility), and add the rudimentary block allocator
using a bit-vector.

While the linked-list may add complexity (especially where
needing to maintain atomic operations), the linked-list helps
simplify what is currently the most expensive operation in
the filesystem, with no cost to space (the linked-list can
reuse the pointers used for chained directory blocks).

1 files changed, 13 insertions, 11 deletions

diff --git a/lfs.h b/lfs.h
index 7b1f01b..4ac48ff 100644
--- a/lfs.h
+++ b/lfs.h
@@ -96,11 +96,6 @@ typedef struct lfs_dir {
         uint32_t rev;
         lfs_size_t size;
         lfs_block_t tail[2];
-
-        struct lfs_disk_free {
-            uint32_t begin;
-            uint32_t end;
-        } free;
     } d;
 } lfs_dir_t;
 
@@ -118,18 +113,23 @@ typedef struct lfs_superblock {
 
 // Little filesystem type
 typedef struct lfs {
+    lfs_size_t read_size;   // size of read
+    lfs_size_t prog_size;   // size of program
+    lfs_size_t block_size;  // size of erase (block size)
+    lfs_size_t block_count; // number of erasable blocks
+    lfs_size_t words;       // number of 32-bit words that can fit in a block
+
     lfs_bd_t *bd;
     const struct lfs_bd_ops *bd_ops;
 
     lfs_block_t root[2];
     lfs_block_t cwd[2];
-    struct lfs_disk_free free;
+    struct {
+        lfs_block_t begin;
+        lfs_block_t end;
+    } free;
 
-    lfs_size_t read_size;   // size of read
-    lfs_size_t prog_size;   // size of program
-    lfs_size_t block_size;  // size of erase (block size)
-    lfs_size_t block_count; // number of erasable blocks
-    lfs_size_t words;       // number of 32-bit words that can fit in a block
+    uint32_t lookahead[LFS_CFG_LOOKAHEAD/32];
 } lfs_t;
 
 // Functions
@@ -137,6 +137,8 @@ int lfs_format(lfs_t *lfs, const struct lfs_config *config);
 int lfs_mount(lfs_t *lfs, const struct lfs_config *config);
 int lfs_unmount(lfs_t *lfs);
 
+int lfs_remove(lfs_t *lfs, const char *path);
+
 int lfs_mkdir(lfs_t *lfs, const char *path);
 int lfs_dir_open(lfs_t *lfs, lfs_dir_t *dir, const char *path);
 int lfs_dir_close(lfs_t *lfs, lfs_dir_t *dir);