1 files changed, 196 insertions, 65 deletions

diff --git a/include/mercury/kernel/utility.hpp b/include/mercury/kernel/utility.hpp
index dbf0cf9..f12101a 100644
--- a/include/mercury/kernel/utility.hpp
+++ b/include/mercury/kernel/utility.hpp
@@ -20,101 +20,232 @@ namespace mercury::kernel::utility {
     uint8_t bytes[16];
   };
 
+  //if c appears in str, this returns the index of the first time it appears.
+  //otherwise, this returns len.
+  static inline unsigned find(const char *str, unsigned len, char c) {
+    for (unsigned i = 0; i < len; ++i)
+      if (str[i] == c)
+        return i;
+    return len;
+  }
+
   template <class value_t>
-  struct string_tree {
+  struct list {
 
-    std::optional<value_t> value_here = {};
-    string_tree<value_t> *parent = 0;
-    string_tree<value_t> *subtrees[256] = {};
+    struct node {
+      value_t value;
+      node *next;
+      node *prev;
+    };
 
-    //if there is a node whose key has a prefix in common with str, then this
-    //returns the deepest such node, and sets leftover_out to point to the
-    //character of str after the common prefix with that returned node. if
-    //there is no such node, this returns the current node and sets
-    //leftover_out to a null pointer.
-    string_tree &max_common_prefix(
-        const char *str, size_t str_len, const char *&leftover_out) {
+    node *first;
+    node *last;
 
-      string_tree<value_t> *last_with_value = 0;
-      const char *leftover_at_last_with_value = 0;
-      string_tree<value_t> *on = this;
-      size_t len_so_far = 0;
+    list() : first(0), last(0) {}
 
-      while (true) {
+    ~list() {
+      if (first) {
+        for (node *n = first->next; n; n = n->next)
+          delete n->prev;
+        delete last;
+      }
+    }
 
-        if (on->value_here) {
-          last_with_value = on;
-          leftover_at_last_with_value = str + len_so_far;
-        }
+    void insert_end(const value_t &value) {
+      node *n = new node {};
+      n->value = value;
+      n->next = 0;
+      n->prev = last;
+      last = n;
+    }
 
-        if (len_so_far == str_len)
-          break;
+    void insert_end(value_t &&value) {
+      node *n = new node {};
+      n->value = value;
+      n->next = 0;
+      n->prev = last;
+      last = n;
+    }
 
-        on = on->subtrees[(uint8_t)str[len_so_far]];
-        if (!on)
-          break;
+    void clear() {
+      for (node *n = first; n; n = n->next)
+        delete n;
+      first = 0;
+      last = 0;
+    }
 
-        ++len_so_far;
+    //assumes there is a last.
+    void remove_last() {
+      node *new_last = last->prev;
+      if (new_last)
+        new_last->next = 0;
+      else
+        first = 0;
+      delete last;
+      last = new_last;
+    }
 
-      }
+  };
 
-      if (last_with_value) {
-        leftover_out = leftover_at_last_with_value;
-        return *last_with_value;
-      }
+  template <class value_t>
+  struct vector {
 
-      leftover_out = 0;
-      return *this;
+    value_t *buffer;
+    unsigned buffer_len;
+    unsigned count;
+
+    vector(unsigned buffer_len = 16)
+      : buffer(new value_t[buffer_len]), buffer_len(buffer_len), count(0) {}
 
+    vector(const value_t *copy_from, unsigned len)
+      : buffer(new value_t[len]), buffer_len(len), count(len) {
+      for (unsigned i = 0; i < len; ++i)
+        buffer[i] = copy_from[i];
     }
 
-    bool try_insert(const char *str, size_t str_len, value_t value) {
+    ~vector() {
+      if (buffer)
+        delete[] buffer;
+    }
 
-      string_tree<value_t> *on = this;
-      for (size_t i = 0; i < str_len; ++i) {
-        string_tree<value_t> *&subtree = on->subtrees[(uint8_t)str[i]];
-        if (!subtree) {
-          subtree = new string_tree<value_t>();
-          subtree->parent = on;
-        }
-        on = subtree;
-      }
+    vector<value_t> &operator =(const vector<value_t> &other) {
+      if (buffer)
+        delete[] buffer;
+      buffer = new value_t[other.buffer_len];
+      buffer_len = other.buffer_len;
+      for (unsigned i = 0; i < other.count; ++i)
+        buffer[i] = other.buffer[i];
+      return *this;
+    }
 
-      if (on->value_here)
+    vector<value_t> &operator =(vector<value_t> &&other) {
+      if (buffer)
+        delete[] buffer;
+      buffer = other.buffer;
+      buffer_len = other.buffer_len;
+      count = other.count;
+      other.buffer = 0;
+      return *this;
+    }
+
+    bool operator ==(const vector<value_t> &other) {
+      if (other.count != count)
         return false;
-      on->value_here = value;
+      for (unsigned i = 0; i < count; ++i)
+        if (other.buffer[i] != buffer[i])
+          return false;
       return true;
+    }
 
+    void verify_buffer_len(unsigned target_len) {
+      if (buffer_len >= target_len)
+        return;
+      unsigned new_buffer_len = buffer_len;
+      do
+        new_buffer_len *= 2;
+      while (new_buffer_len < target_len);
+      value_t *new_buffer = new value_t[new_buffer_len];
+      for (unsigned i = 0; i < count; ++i)
+        new_buffer[i] = std::move(buffer[i]);
+      delete[] buffer;
+      buffer = new_buffer;
+      buffer_len = new_buffer_len;
+    }
+
+    void add_end(value_t &&v) {
+      verify_buffer_len(count + 1);
+      buffer[count] = std::move(v);
+      ++count;
+    }
+
+    void add_end(const value_t &v) {
+      verify_buffer_len(count + 1);
+      buffer[count] = v;
+      ++count;
     }
 
   };
 
-  //if c appears in str, this returns the index of the first time it appears.
-  //otherwise, this returns len.
-  static inline size_t find(const char *str, size_t len, char c) {
-    for (size_t i = 0; i < len; ++i)
-      if (str[i] == c)
-        return i;
-    return len;
-  }
+  typedef vector<char> string;
 
-  template <class value_t>
-  struct flist {
+  template <class key_component_t, class value_t>
+  struct trie {
 
-    struct node {
-      value_t value;
-      node *next;
+    typedef vector<key_component_t> key_t;
+
+    struct child {
+      key_component_t component;
+      trie tr;
     };
 
-    node *first;
+    //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) {}
 
-    flist() : first(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 {
 
-    void insert(value_t value) {
-      first = new node {
-        .value = value,
-        .next = first
-      };
+      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)
+        return false;
+      *on->value_here = value;
+      return true;
     }
 
   };