2
\$\begingroup\$

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!

\$\endgroup\$

2 Answers 2

0
\$\begingroup\$

Self answer: the code above missed something.

When a read from an input stream succeeds but the value is invalid, the reader has a duty to mark std::ios_base::failbit to the input stream, so that the operator bool() of the input stream is false where is >> tree is evaluated.

So the code should be like this:

    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";
      is.clear(std::ios_base::failbit); // should set failbit
      return is;
    }
\$\endgroup\$
0
\$\begingroup\$

Throughout the code, I miss documentation:
What are the functions specified to return?
Why would deserialisation replicate the tree structure serialised,
instead of constructing a "suitably balanced" tree?

As a test, I think checking iteration results would be stronger than just contains.
Consider checking "the Multies".

\$\endgroup\$
3
  • \$\begingroup\$ Balancedness and tree invariants are already being checked in the line assert(tree.verify()); at the end of deserialization, but yes, it is a good catch \$\endgroup\$
    – frozenca
    Jul 25 at 5:54
  • \$\begingroup\$ assert(tree.verify()); at the end of deserialization is a white-box insight. And I doubt either that or contains would catch getting multiplicities wrong. \$\endgroup\$
    – greybeard
    Jul 25 at 8:19
  • \$\begingroup\$ counting multiplicities is count(), it is supported for BTreeMultiSet, BTreeSet doesn't allow duplicates. But yes, I'll add tests for that. Actually there are four types, BTreeSet, BTreeMap, BTreeMultiSet and BTreeMultiMap. I'll ban possible conversions via serialization/deserialization between different types \$\endgroup\$
    – frozenca
    Jul 25 at 8:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.