From ab70e5461b98ddf2b56268c53c171cab89157027 Mon Sep 17 00:00:00 2001 From: Estevan Castilho Date: Thu, 2 Jul 2026 00:31:57 +0000 Subject: Nuke the old code --- include/Merkle.h | 185 ------------------------------------------------------- 1 file changed, 185 deletions(-) delete mode 100644 include/Merkle.h (limited to 'include/Merkle.h') diff --git a/include/Merkle.h b/include/Merkle.h deleted file mode 100644 index 6256ddc..0000000 --- a/include/Merkle.h +++ /dev/null @@ -1,185 +0,0 @@ -#pragma once - -#include "IStorageBackend.h" - -#include -#include -#include -#include -#include -#include - -/** - * @file Merkle.h - * @brief Generic sorted content-addressed B-tree over a templated key type. - * - * Maps `Key → Hash32 payload` with `Key` totally ordered. Each tree node is - * stored as an immutable blob in IStorageBackend via Put/Get. All operations - * load only the nodes on the path from root to the target leaf — O(log_B(n)) - * nodes in memory at once, never the whole tree. - * - * Instantiated three times in RNT: - * - * | Level | Key | Payload (Hash32) | - * |---------------|----------------|-------------------------| - * | Branch tree | `std::string` | multigroup snapshot hash| - * | Multigroup | `std::string` | relation merkle root | - * | Relation | `nt::Hash32` | tuple hash (key=payload)| - * - * **Branching factor B = 64**. At 64 children per node and a billion leaves the - * tree is at most 5 levels deep (~20 KB peak working set). - * - * **Immutability**: nodes are never overwritten once written (content-addressed). - * Insert / Remove produce new nodes only along the modified path; old nodes - * remain valid for any snapshot that still holds their root hash. - * - * **Leaf node** stores a sorted-by-key list of `(Key, Hash32 payload)` pairs, - * length ≤ B. For the relation level the key and payload happen to carry the - * same value (the tuple hash); callers pass it twice. Storing both keeps the - * tree shape uniform across the three levels. - * - * **Internal node entry** layout (`leaf_count | min_key | child_hash`): - * - `leaf_count` enables O(log_B(n) + limit) offset navigation for Page() - * without loading sibling subtrees. - * - `min_key` is the smallest key in the subtree — the routing key. - * - `child_hash` is the content-addressed hash of the child node blob. - * - * **Invariants** (asserted in debug builds): - * - No leaf or internal node is ever empty. - * - Leaf entries are sorted ascending by key. - * - Internal entries are sorted ascending by min_key. - * - * **Wire format**: tagged 1-byte node kind ('L' or 'I'), then big-endian u32 - * count, then count repetitions of either a leaf entry or a child entry. - * Key encoding is per-specialisation: `Hash32` is 32 raw bytes; `std::string` - * is `u32_be length | bytes`. Wire format is content-addressed — any change - * here invalidates every existing stored snapshot. - */ - -namespace nt { - - /** @brief 32-byte hash, the universal payload type for all merkle levels. */ - using Hash32 = std::array; - - /** @brief Decode a 64-character lowercase-hex SHA256 string into raw bytes. - * Throws std::invalid_argument when the string is not exactly 64 hex chars. */ - Hash32 hex_to_bin(const std::string& hex); - - /** @brief Encode raw 32 bytes back into a 64-character lowercase-hex string. */ - std::string bin_to_hex(const Hash32& bin); - - template class Merkle { - public: - static constexpr size_t B = 64; - - /** - * @brief Insert or overwrite a `(key, payload)` mapping. - * @param store KV backend for node serialisation. - * @param root_hex Current root hash (empty string = empty tree). - * @param key Routing/identity key. - * @param payload Hash this key maps to (child root one level down, or - * the key itself at the relation level). - * @return New root hash. Equal to root_hex when an insertion of an - * identical (key, payload) pair would be a no-op. - */ - static std::string Insert(IStorageBackend& store, const std::string& root_hex, - const Key& key, const Hash32& payload); - - /** - * @brief Remove a key from the tree. - * @return New root hash. Empty string when the tree becomes empty. - * Equal to root_hex when the key is absent. - */ - static std::string Remove(IStorageBackend& store, const std::string& root_hex, - const Key& key); - - /** - * @brief Look up the payload for a key. - * @return The payload when present, std::nullopt when absent. - */ - static std::optional Get(IStorageBackend& store, const std::string& root_hex, - const Key& key); - - /** @brief One (key, payload) pair returned by Page(). */ - struct Entry { - Key key; - Hash32 payload; - }; - - /** - * @brief Page through entries in key-sorted order. - * - * Descends to the leaf at logical position @p offset using cumulative - * leaf_counts stored in internal nodes, then walks forward collecting at - * most @p limit entries. Only the nodes on the active path are loaded; - * sibling subtrees are never touched. - */ - static std::vector Page(IStorageBackend& store, const std::string& root_hex, - size_t offset, size_t limit); - - private: - struct LeafEntry { - Key key; - Hash32 payload; - }; - - struct LeafNode { - std::vector entries; - }; - - struct ChildEntry { - uint64_t leaf_count; - Key min_key; - Hash32 child_hash; - }; - - struct InternalNode { - std::vector entries; - }; - - // Wire format - static std::vector encode_leaf(const LeafNode& n); - static std::vector encode_internal(const InternalNode& n); - static LeafNode decode_leaf(const std::vector& bytes); - static InternalNode decode_internal(const std::vector& bytes); - static bool is_leaf_bytes(const std::vector& bytes); - - // Storage helpers - static std::vector load_node(IStorageBackend& store, const std::string& hash_hex); - static std::string store_leaf(IStorageBackend& store, const LeafNode& n); - static std::string store_internal(IStorageBackend& store, const InternalNode& n); - - /** @brief Returns the smallest key in the subtree rooted at @p node_hex. */ - static Key subtree_min_key(IStorageBackend& store, const std::string& node_hex); - - /** @brief Routes a key to the rightmost child whose min_key ≤ target. */ - static size_t route(const InternalNode& node, const Key& target); - - struct InsertResult { - std::string new_hash; - uint64_t leaf_count = 0; - bool did_split = false; - uint64_t split_leaf_count = 0; - Key split_min_key{}; - std::string split_hash; - }; - - static InsertResult insert_into(IStorageBackend& store, const std::string& node_hex, - const Key& key, const Hash32& payload); - - struct RemoveResult { - std::string new_hash; - uint64_t leaf_count = 0; - }; - - static RemoveResult remove_from(IStorageBackend& store, const std::string& node_hex, - const Key& key); - - static void page_from(IStorageBackend& store, const std::string& node_hex, size_t& offset, - size_t limit, std::vector& out); - - static std::optional get_from(IStorageBackend& store, const std::string& node_hex, - const Key& key); - }; - -} // namespace nt -- cgit v1.2.3