path: root/include/mercury/kernel/utility.hpp

#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];
  };

  //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 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;
    }

  };

  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() {
      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;
      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;
    }

  };

  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)
        return false;
      *on->value_here = value;
      return true;
    }

  };

}

#endif