#pragma once #include #include #include #include #include #include #include struct String_buffer; struct __String_handle; typedef __String_handle* String_handle; typedef uint32_t String_hash; constexpr size_t initial_size = 1024; // Initial size of the string buffer (in bytes) constexpr size_t hash_size = 317; // Hash size String_hash hash_fn(const char* str); bool equal(const __String_handle* a, const __String_handle* b); __String_handle* append(const __String_handle* a, const __String_handle* b, String_buffer& buffer); struct __String_handle { friend struct String_buffer; friend bool equal(const __String_handle* a, const __String_handle* b); friend __String_handle* append(const __String_handle* a, const __String_handle* b, String_buffer& buffer); public: __String_handle(const String_buffer& buffer, uint32_t offset, uint32_t size); ~__String_handle() = default; const char* data() const; uint32_t get_size() const; private: bool operator==(const __String_handle& b) const; private: const String_buffer& string_buffer; const uint32_t offset, size; public: const String_hash hash; }; struct String_buffer { public: String_buffer(); ~String_buffer(); String_handle get_next_handle(); void push(char c); String_handle push_string(const std::string_view& str); private: void reallocate(); public: char* buffer = nullptr; size_t buffer_size = 0; uint32_t idx = 0; uint32_t idx_of_last_handle = 0; char last_pushed_char = -1; std::vector> handles; String_handle err_msg; }; template struct String_hash_map { private: struct Entry { const __String_handle* key; T value; long next = -1; }; public: String_hash_map() { // Initialize table to -1 for (size_t i = 0; i < hash_size; ++i) table[i] = -1; } std::optional get(const __String_handle* key) const { String_hash hash = key->hash; long idx = table[hash]; while (idx != -1) { const Entry& e = entries[idx]; if (equal(e.key, key)) { return e.value; } idx = e.next; } return {}; } bool exists(const __String_handle* key) { return get(key).has_value(); } bool put(const __String_handle* key, T value) { if (exists(key)) { return false; } // Create a new entry struct String_hash hash = key->hash; { Entry entry; entry.key = key; entry.value = value; entry.next = table[hash]; entries.push_back(std::move(entry)); } table[hash] = entries.size() - 1; ++num_elements_inserted; return true; } std::vector keys() const { std::vector keys; keys.reserve(num_elements_inserted); for (const auto& e : entries) { keys.push_back(e.key); } return keys; } std::vector values() const { std::vector values; values.reserve(num_elements_inserted); for (const auto& e : entries) { values.push_back(e.value); } return values; } size_t size() { return num_elements_inserted; } private: std::vector entries = {}; long table[hash_size]; size_t num_elements_inserted = 0; };