1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
|
#pragma once
#include "IStorageBackend.h"
#include <string>
#include <utility>
#include <vector>
/**
* @file MultigroupCodec.h
* @brief Thin facade over Merkle<std::string> for multigroup snapshots.
*
* A multigroup snapshot is a `Merkle<std::string>` B-tree mapping each
* relation name to that relation's merkle root. The snapshot identifier is
* the hex hash of the tree's root node — the same path-localised content
* addressing used at the tuple level inside each relation.
*
* Stored relations and ephemeral relations are represented uniformly: only
* the relation's name and its current merkle_root participate in the tree,
* regardless of how that root was derived.
*
* The codec used to be a flat `SHA256(sorted [(name, root)])` over a single
* blob. That collapsed all relations into one rehash on any mutation. With
* the merkle B-tree, a single relation update touches `O(log_B(n_rels))`
* nodes on the way to the new root — sibling subtrees stay byte-identical.
*
* `RelationEntry` is `(relation_name, relation_root_hex)`. Both forms are
* hex strings on the wire; the codec hex-decodes internally before handing
* payloads to `Merkle<std::string>`.
*/
namespace nt::MultigroupCodec
{
/** @brief One entry in a multigroup snapshot: (relation_name, root_hex). */
using RelationEntry = std::pair<std::string, std::string>;
/**
* @brief Build a multigroup tree from a list of (name, root) entries.
*
* Each `Insert` advances the root through `O(log_B)` nodes. The final
* root hash is the snapshot identifier. The list need not be pre-sorted —
* the merkle B-tree imposes order intrinsically.
*
* @param store KV backend; receives all node blobs.
* @param relations Entries to load. Duplicates collapse to the last value.
* @return Root node hash (empty string when `relations` is empty).
*/
std::string Build(IStorageBackend& store,
const std::vector<RelationEntry>& relations);
/**
* @brief Enumerate all (name, root_hex) pairs at a multigroup root.
*
* Pages the entire tree (offset 0, no limit). Returned entries are in
* key-sorted order. Empty input root yields an empty list.
*/
std::vector<RelationEntry> List(IStorageBackend& store,
const std::string& root_hex);
/**
* @brief Insert or overwrite one (relation_name → root_hex) entry.
*
* Equivalent to `Merkle<std::string>::Insert` after hex-decoding the
* payload. The caller threads the returned root hash through subsequent
* mutations. Pass an empty `root_hex` for the prior-state argument to
* start from an empty tree.
*/
std::string InsertOne(IStorageBackend& store,
const std::string& root_hex,
const std::string& relation_name,
const std::string& relation_root_hex);
/**
* @brief Remove one relation entry from the multigroup tree.
*
* Returns the new root hash; empty when the tree becomes empty.
*/
std::string RemoveOne(IStorageBackend& store,
const std::string& root_hex,
const std::string& relation_name);
/**
* @brief Look up one relation's root hex by name.
* @return Hex root, or empty string when the name is absent.
*/
std::string Lookup(IStorageBackend& store,
const std::string& root_hex,
const std::string& relation_name);
}
|
