Yesterday I wrote a serialization/deserialization for my B-Tree library (link)
Since the code for whole tree is too large to upload here, I'll upload only serialization/deserialization and node class definition/tree class member variable parts here.
I think my code is not broken, but I want to know how to do error checks better
Type checks:
template <typename T>
concept DiskAllocable = std::is_same_v<std::remove_cvref_t<T>, T> &&
std::is_trivially_copyable_v<T> &&(sizeof(T) % alignof(T) == 0);
// ...
static constexpr bool is_disk_ = DiskAllocable<V>;
Serialization/deserialization:
// serialization and deserialization
static constexpr std::uint64_t begin_code = 0x6567696e; // 'begin'
static constexpr std::uint64_t end_code = 0x656e64; // 'end'
// for tree, we write a root height
// for each node, we only read/write two information:
// 1. number of keys (attr_t, int32)
// 2. byte stream for key data (sizeof(V) * nkeys())
// all other information can be inferred during tree traversal
// number of max bytes for serializing/deserializing a single node
static constexpr std::size_t keydata_size = sizeof(V) * disk_max_nkeys;
// maximum possible height for B-Tree
// if height exceeds this value, this means that serialization/deserialization
// size will exceed 16TB, much more likely a user mistake or a malicious
// attack
static constexpr std::size_t max_possible_height =
(44UL - std::bit_width(static_cast<std::size_t>(2 * Fanout))) /
std::bit_width(keydata_size);
friend std::istream &operator>>(std::istream &is,
BTreeBase &tree) requires(is_disk_) {
std::uint64_t tree_code = 0;
if (!is.read(reinterpret_cast<char *>(&tree_code), sizeof(std::uint64_t))) {
std::cerr << "Tree deserialization: begin code parse error\n";
return is;
}
if (tree_code != begin_code) {
std::cerr << "Tree deserialization: begin code is invalid\n";
return is;
}
attr_t tree_height = 0;
if (!is.read(reinterpret_cast<char *>(&tree_height), sizeof(attr_t))) {
std::cerr << "Tree deserialization: tree height parse error\n";
return is;
}
if (static_cast<std::size_t>(tree_height) > max_possible_height) {
std::cerr << "Tree deserialization: height is invalid\n";
return is;
}
auto node = tree.root_.get();
assert(node);
if (!tree.deserialize_node(is, node, 0, tree_height)) {
return is;
}
if (!is.read(reinterpret_cast<char *>(&tree_code), sizeof(std::uint64_t))) {
std::cerr << "Tree deserialization: end code parse error\n";
tree.clear();
return is;
}
if (tree_code != end_code) {
std::cerr << "Tree deserialization: end code is invalid\n";
tree.clear();
return is;
}
tree.set_begin();
assert(tree.verify());
return is;
}
// preorder DFS traversal
bool deserialize_node(std::istream &is, Node *node, attr_t node_index,
attr_t node_height) requires(is_disk_) {
assert(node);
node->index_ = node_index;
node->height_ = node_height;
if (!is.read(reinterpret_cast<char *>(&node->num_keys_), sizeof(attr_t))) {
std::cerr << "Tree deserialization: nkeys parse error\n";
return false;
}
if (node->num_keys_ >= 2 * Fanout ||
(node != root_.get() && node->num_keys_ < Fanout - 1) ||
node->num_keys_ < 0) {
std::cerr << "Tree deserialization: nkeys is invalid\n";
return false;
}
if (!is.read(reinterpret_cast<char *>(node->keys_.data()),
static_cast<std::size_t>(node->num_keys_) * sizeof(V))) {
std::cerr << "Tree deserialization: key data read error\n";
return false;
}
node->size_ = node->num_keys_;
if (node_height > 0) {
node->children_.reserve(2 * Fanout);
node->children_.resize(node->num_keys_ + 1);
for (attr_t i = 0; i <= node->num_keys_; ++i) {
node->children_[i] = std::make_unique<Node>(alloc_);
node->children_[i]->parent_ = node;
if (!deserialize_node(is, node->children_[i].get(), i,
node_height - 1)) {
return false;
}
}
}
if (node->parent_) {
node->parent_->size_ += node->size_;
}
return true;
}
friend std::ostream &operator<<(std::ostream &os,
const BTreeBase &tree) requires(is_disk_) {
std::uint64_t tree_code = begin_code;
if (!os.write(reinterpret_cast<char *>(&tree_code),
sizeof(std::uint64_t))) {
std::cerr << "Tree serialization: begin code write error\n";
return os;
}
attr_t tree_height = tree.height();
if (!os.write(reinterpret_cast<char *>(&tree_height), sizeof(attr_t))) {
std::cerr << "Tree serialization: tree height write error\n";
return os;
}
auto node = tree.root_.get();
assert(node);
if (!tree.serialize_node(os, node)) {
return os;
}
tree_code = end_code;
if (!os.write(reinterpret_cast<char *>(&tree_code),
sizeof(std::uint64_t))) {
std::cerr << "Tree serialization: end code write error\n";
return os;
}
return os;
}
// preorder DFS traversal
bool serialize_node(std::ostream &os, const Node *node) const
requires(is_disk_) {
assert(node);
if (!os.write(reinterpret_cast<const char *>(&node->num_keys_),
sizeof(attr_t))) {
std::cerr << "Tree serialization: nkeys write error\n";
return false;
}
if (!os.write(reinterpret_cast<const char *>(node->keys_.data()),
static_cast<std::size_t>(node->num_keys_) * sizeof(V))) {
std::cerr << "Tree serialization: key data write error\n";
return false;
}
if (node->height_ > 0) {
for (attr_t i = 0; i <= node->num_keys_; ++i) {
if (!serialize_node(os, node->children_[i].get())) {
return false;
}
}
}
return true;
}
Node definition:
struct Node {
using keys_type = std::conditional_t<is_disk_, std::span<V, disk_max_nkeys>,
std::vector<V, Alloc>>;
// invariant: except root, t - 1 <= #(key) <= 2 * t - 1
// invariant: for root, 0 <= #(key) <= 2 * t - 1
// invariant: keys are sorted
// invariant: for internal nodes, t <= #(child) == (#(key) + 1)) <= 2 * t
// invariant: for root, 0 <= #(child) == (#(key) + 1)) <= 2 * t
// invariant: for leaves, 0 == #(child)
// invariant: child_0 <= key_0 <= child_1 <= ... <= key_(N - 1) <= child_N
[[no_unique_address]] Alloc alloc_;
keys_type keys_;
std::vector<std::unique_ptr<Node>> children_;
Node *parent_ = nullptr;
attr_t size_ = 0; // number of keys in the subtree (not keys in this node)
attr_t index_ = 0;
attr_t height_ = 0;
attr_t num_keys_ =
0; // number of keys in this node, used only for disk variant
// can throw bad_alloc
explicit Node(Alloc &alloc, bool is_leaf = true) requires(is_disk_)
: alloc_{alloc},
keys_(alloc_.allocate(disk_max_nkeys), disk_max_nkeys) {}
~Node() {
if constexpr (is_disk_) {
alloc_.deallocate(keys_.data(), disk_max_nkeys);
}
}
Node(const Node &node) = delete;
Node &operator=(const Node &node) = delete;
Node(Node &&node) = delete;
Node &operator=(Node &&node) = delete;
// ... unrelated details ...
};
Tree class members
private:
[[no_unique_address]] Alloc alloc_;
std::unique_ptr<Node> root_;
const_iterator_type begin_;
Test code:
#include "fc_btree.h"
#include <fstream>
#include <iostream>
int main() {
namespace fc = frozenca;
fc::BTreeSet<int> btree_out;
constexpr int n = 100;
for (int i = 0; i < n; ++i) {
btree_out.insert(i);
}
{
std::ofstream ofs{"btree.bin", std::ios_base::out | std::ios_base::binary |
std::ios_base::trunc};
ofs << btree_out;
}
fc::BTreeSet<int> btree_in;
{
std::ifstream ifs{"btree.bin", std::ios_base::in | std::ios_base::binary};
ifs >> btree_in;
}
for (int i = 0; i < n; ++i) {
if (!btree_in.contains(i)) {
std::cout << "deserialized tree key lookup failed\n";
}
}
std::cout << "OK\n";
}
The code for the entire tree class
Feel free to comment anything!
