1 files changed, 224 insertions, 0 deletions
diff --git a/include/hilbert/kernel/utility.hpp b/include/hilbert/kernel/utility.hpp
new file mode 100644
index 0000000..930264a
--- /dev/null
+++ b/include/hilbert/kernel/utility.hpp
@@ -0,0 +1,224 @@
+#ifndef HILBERT_KERNEL_UTILITY_HPP
+#define HILBERT_KERNEL_UTILITY_HPP
+
+#include <optional>
+#include <cstdint>
+
+namespace hilbert::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];
+  };
+
+  //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;
+  }
+
+  //if c appears in str, this returns the index of the last time it appears.
+  //otherwise, this returns len.
+  static inline unsigned find_last(const char *str, unsigned len, char c) {
+    for (unsigned i = len; i > 0; --i)
+      if (str[i - 1] == c)
+        return i - 1;
+    return len;
+  }
+
+  //str1 starts with str2
+  static inline bool starts_with(
+    const char *str1, unsigned str1_len, const char *str2, unsigned str2_len
+  ) {
+    if (str1_len < str2_len)
+      return false;
+    for (unsigned i = 0; i < str2_len; ++i)
+      if (str1[i] != str2[i])
+        return false;
+    return true;
+  }
+
+  template <class value_t>
+  struct list {
+
+    struct node {
+      value_t value;
+      node *next;
+      node *prev;
+    };
+
+    node *first;
+    node *last;
+
+    list() : first(0), last(0) {}
+
+    ~list() {
+      if (first) {
+        for (node *n = first->next; n; n = n->next)
+          delete n->prev;
+        delete last;
+      }
+    }
+
+    void insert_end(const value_t &value) {
+      node *n = new node {};
+      n->value = value;
+      n->next = 0;
+      n->prev = last;
+      last = n;
+    }
+
+    void insert_end(value_t &&value) {
+      node *n = new node {};
+      n->value = value;
+      n->next = 0;
+      n->prev = last;
+      last = n;
+    }
+
+    void clear() {
+      for (node *n = first; n; n = n->next)
+        delete n;
+      first = 0;
+      last = 0;
+    }
+
+    //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;
+    }
+
+    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>
+  struct vector {
+
+    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];
+    }
+
+    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;
+    }
+
+    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;
+      count = other.count;
+      for (unsigned i = 0; i < other.count; ++i)
+        buffer[i] = other.buffer[i];
+      return *this;
+    }
+
+    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;
+      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;
+    }
+
+    bool starts_with(const vector<value_t> &other) {
+      if (count < other.count)
+        return false;
+      for (unsigned i = 0; i < other.count; ++i)
+        if (buffer[i] != other.buffer[i])
+          return false;
+      return true;
+    }
+
+  };
+
+  typedef vector<char> string;
+
+}
+
+#endif