first commit

1 files changed, 124 insertions, 0 deletions

diff --git a/include/mercury/kernel/utility.hpp b/include/mercury/kernel/utility.hpp
new file mode 100644
index 0000000..dbf0cf9
--- /dev/null
+++ b/include/mercury/kernel/utility.hpp
@@ -0,0 +1,124 @@
+#ifndef MERCURY_KERNEL_UTILITY_HPP
+#define MERCURY_KERNEL_UTILITY_HPP
+
+#include <optional>
+#include <cstdint>
+
+namespace mercury::kernel::utility {
+
+  template <class t>
+  static inline t min(t a, t b) {
+    return a < b ? a : b;
+  }
+
+  //includes start_i, does not include end_i
+  void mark_bitmap_region_zero(uint64_t *bitmap, uint64_t start_i, uint64_t end_i);
+  //includes start_i, does not include end_i
+  void mark_bitmap_region_one(uint64_t *bitmap, uint64_t start_i, uint64_t end_i);
+
+  struct uuid {
+    uint8_t bytes[16];
+  };
+
+  template <class value_t>
+  struct string_tree {
+
+    std::optional<value_t> value_here = {};
+    string_tree<value_t> *parent = 0;
+    string_tree<value_t> *subtrees[256] = {};
+
+    //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) {
+
+      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;
+
+      while (true) {
+
+        if (on->value_here) {
+          last_with_value = on;
+          leftover_at_last_with_value = str + len_so_far;
+        }
+
+        if (len_so_far == str_len)
+          break;
+
+        on = on->subtrees[(uint8_t)str[len_so_far]];
+        if (!on)
+          break;
+
+        ++len_so_far;
+
+      }
+
+      if (last_with_value) {
+        leftover_out = leftover_at_last_with_value;
+        return *last_with_value;
+      }
+
+      leftover_out = 0;
+      return *this;
+
+    }
+
+    bool try_insert(const char *str, size_t str_len, value_t value) {
+
+      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;
+      }
+
+      if (on->value_here)
+        return false;
+      on->value_here = value;
+      return true;
+
+    }
+
+  };
+
+  //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;
+  }
+
+  template <class value_t>
+  struct flist {
+
+    struct node {
+      value_t value;
+      node *next;
+    };
+
+    node *first;
+
+    flist() : first(0) {}
+
+    void insert(value_t value) {
+      first = new node {
+        .value = value,
+        .next = first
+      };
+    }
+
+  };
+
+}
+
+#endif