From 15e62510104bc0e2b9180b66e5845d985cac03cc Mon Sep 17 00:00:00 2001 From: Benji Dial Date: Wed, 10 Jan 2024 00:17:29 -0500 Subject: partial (largely untested) memory block device and tar file system support --- include/mercury/kernel/utility.hpp | 261 ++++++++++++++++++++++++++++--------- 1 file changed, 196 insertions(+), 65 deletions(-) (limited to 'include/mercury/kernel/utility.hpp') 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 - struct string_tree { + struct list { - std::optional value_here = {}; - string_tree *parent = 0; - string_tree *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 *last_with_value = 0; - const char *leftover_at_last_with_value = 0; - string_tree *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 + 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 *on = this; - for (size_t i = 0; i < str_len; ++i) { - string_tree *&subtree = on->subtrees[(uint8_t)str[i]]; - if (!subtree) { - subtree = new string_tree(); - subtree->parent = on; - } - on = subtree; - } + vector &operator =(const vector &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 &operator =(vector &&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 &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 string; - template - struct flist { + template + struct trie { - struct node { - value_t value; - node *next; + typedef vector key_t; + + struct child { + key_component_t component; + trie tr; }; - node *first; + //really this should be a hashmap or something + vector 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_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; } }; -- cgit v1.2.3