feat: page caching layer for vfs

[lunaix-os.git] / lunaix-os / includes / lunaix / ds / btrie.h

diff --git a/lunaix-os/includes/lunaix/ds/btrie.h b/lunaix-os/includes/lunaix/ds/btrie.h
new file mode 100644 (file)
index 0000000..ad3d04c
--- /dev/null
+++ b/lunaix-os/includes/lunaix/ds/btrie.h
@@ -0,0 +1,40 @@
+#ifndef __LUNAIX_SPARSE_H
+#define __LUNAIX_SPARSE_H
+
+#include <lunaix/ds/llist.h>
+#include <lunaix/types.h>
+
+#define BTRIE_BITS 4
+
+struct btrie
+{
+    struct btrie_node* btrie_root;
+    int truncated;
+};
+
+struct btrie_node
+{
+    struct llist_header children;
+    struct llist_header siblings;
+    struct llist_header nodes;
+    struct btrie_node* parent;
+    uint32_t index;
+    void* data;
+};
+
+void
+btrie_init(struct btrie* btrie, uint32_t trunc_bits);
+
+void*
+btrie_get(struct btrie* root, uint32_t index);
+
+void
+btrie_set(struct btrie* root, uint32_t index, void* data);
+
+void*
+btrie_remove(struct btrie* root, uint32_t index);
+
+void
+btrie_release(struct btrie* tree);
+
+#endif /* __LUNAIX_SPARSE_H */