From 882e74b2191c059a9226cbd8bcb51c97da36247c Mon Sep 17 00:00:00 2001
From: Benji Dial <benji@benjidial.net>
Date: Fri, 12 Jan 2024 20:39:21 -0500
Subject: rewrite file system layer

---
 include/mercury/kernel/utility.hpp | 108 ++++++++++---------------------------
 1 file changed, 28 insertions(+), 80 deletions(-)

(limited to 'include/mercury/kernel/utility.hpp')

diff --git a/include/mercury/kernel/utility.hpp b/include/mercury/kernel/utility.hpp
index 1648e67..3edd7d4 100644
--- a/include/mercury/kernel/utility.hpp
+++ b/include/mercury/kernel/utility.hpp
@@ -106,6 +106,18 @@ namespace mercury::kernel::utility {
       last = new_last;
     }
 
+    void remove(node *n) {
+      if (n->prev)
+        n->prev->next = n->next;
+      else
+        first = n->next;
+      if (n->next)
+        n->next->prev = n->prev;
+      else
+        last = n->prev;
+      delete n;
+    }
+
   };
 
   template <class value_t>
@@ -124,6 +136,14 @@ namespace mercury::kernel::utility {
         buffer[i] = copy_from[i];
     }
 
+    vector(const vector<value_t> &other)
+      : buffer(new value_t[other.buffer_len]),
+        buffer_len(other.buffer_len), count(other.count)
+    {
+      for (unsigned i = 0; i < count; ++i)
+        buffer[i] = other.buffer[i];
+    }
+
     ~vector() {
       if (buffer)
         delete[] buffer;
@@ -134,6 +154,7 @@ namespace mercury::kernel::utility {
         delete[] buffer;
       buffer = new value_t[other.buffer_len];
       buffer_len = other.buffer_len;
+      count = other.count;
       for (unsigned i = 0; i < other.count; ++i)
         buffer[i] = other.buffer[i];
       return *this;
@@ -185,92 +206,19 @@ namespace mercury::kernel::utility {
       ++count;
     }
 
-  };
-
-  typedef vector<char> string;
-
-  template <class key_component_t, class value_t>
-  struct trie {
-
-    typedef vector<key_component_t> key_t;
-
-    struct child {
-      key_component_t component;
-      trie tr;
-    };
-
-    //really this should be a hashmap or something
-    vector<child> children;
-
-    trie *try_get_child(const key_component_t &component) const {
-      for (unsigned i = 0; i < children.count; ++i)
-        if (children.buffer[i].component == component)
-          return &children.buffer[i].tr;
-      return 0;
-    }
-
-    std::optional<value_t> value_here;
-
-    trie() : children(0) {}
-
-    //prefix length is in key components, with the root node having a prefix
-    //length of 0. if no prefix of key has a value, then this just returns the
-    //root node and sets prefix length to 0.
-    const trie &longest_prefix_with_value(
-      const key_t &key, unsigned &prefix_length_out
-    ) const {
-
-      const trie *on = this;
-      unsigned with_i = 0;
-
-      const trie *longest_found = this;
-      prefix_length_out = 0;
-
-      while (true) {
-        if (with_i == key.count)
-          return *longest_found;
-        on = on->try_get_child(key.buffer[with_i]);
-        if (!on)
-          return *longest_found;
-        ++with_i;
-        if (on->value_here) {
-          longest_found = on;
-          prefix_length_out = with_i;
-        }
-      }
-
-    }
-
-    bool has_key(const key_t &key) {
-      const trie *on = this;
-      for (unsigned i = 0; i < key.count; ++i) {
-        on = on->try_get_child(key.buffer[i]);
-        if (!on)
-          return false;
-      }
-      return on->value_here.has_value();
-    }
-
-    //returns false if this key is already in use.
-    bool try_insert(const key_t &key, value_t value) {
-      trie *on = this;
-      for (unsigned i = 0; i < key.count; ++i) {
-        on = on->try_get_child(key.buffer[i]);
-        if (!on) {
-          child ch;
-          ch.component = key.buffer[i];
-          on->children.add_end(std::move(ch));
-          on = &on->children.buffer[on->children.count - 1].tr;
-        }
-      }
-      if (on->value_here)
+    bool starts_with(const vector<value_t> &other) {
+      if (count < other.count)
         return false;
-      *on->value_here = value;
+      for (unsigned i = 0; i < other.count; ++i)
+        if (buffer[i] != other.buffer[i])
+          return false;
       return true;
     }
 
   };
 
+  typedef vector<char> string;
+
 }
 
 #endif
-- 
cgit v1.2.3