preparation cleanup for RNT integration

2 files changed, 0 insertions, 1045 deletions

diff --git a/shared/shabptree/dune b/shared/shabptree/dune
deleted file mode 100644
index ee86221..0000000
--- a/shared/shabptree/dune
+++ /dev/null
@@ -1,14 +0,0 @@
-(rule
- (target sakura_shabptree.dll)
- (deps shabptree.c)
- (action
-  (run
-   %{cc}
-   -std=c99
-   -Wall
-   -Wextra
-   -DSAKURA_BPTREE_BUILDING_DLL
-   -shared
-   -o
-   %{target}
-   %{deps})))
diff --git a/shared/shabptree/shabptree.c b/shared/shabptree/shabptree.c
deleted file mode 100644
index 0337345..0000000
--- a/shared/shabptree/shabptree.c
+++ /dev/null
@@ -1,1031 +0,0 @@
-#include <stddef.h>
-#include <stdint.h>
-#include <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-
-#if defined(_WIN32) && defined(SAKURA_BPTREE_BUILDING_DLL)
-#define SAKURA_BPTREE_API __declspec(dllexport)
-#elif defined(_WIN32)
-#define SAKURA_BPTREE_API __declspec(dllimport)
-#else
-#define SAKURA_BPTREE_API
-#endif
-
-#define SAKURA_SHA32_KEY_SIZE 32u
-
-typedef struct sakura_bptree sakura_bptree;
-
-typedef enum sakura_bptree_status {
-    SAKURA_BPTREE_OK = 0,
-    SAKURA_BPTREE_NOT_FOUND = 1,
-    SAKURA_BPTREE_INVALID_ARGUMENT = 2,
-    SAKURA_BPTREE_OUT_OF_MEMORY = 3,
-    SAKURA_BPTREE_IO_ERROR = 4,
-    SAKURA_BPTREE_CORRUPT_FILE = 5
-} sakura_bptree_status;
-
-typedef void (*sakura_bptree_iter_cb)(const uint8_t key[SAKURA_SHA32_KEY_SIZE],
-                                      const void *value,
-                                      uint64_t value_len,
-                                      void *user_data);
-
-#define BPTREE_ORDER 32
-#define BPTREE_MAX_KEYS (BPTREE_ORDER - 1)
-#define BPTREE_MAGIC "SKBPT1\0\0"
-#define BPTREE_MAGIC_SIZE 8u
-#define BPTREE_VERSION 1u
-
-typedef struct bptree_value {
-    uint8_t *data;
-    uint64_t len;
-} bptree_value;
-
-typedef struct bptree_node {
-    int is_leaf;
-    int key_count;
-    uint8_t keys[BPTREE_ORDER][SAKURA_SHA32_KEY_SIZE];
-    struct bptree_node *parent;
-    struct bptree_node *next;
-    union {
-        struct bptree_node *children[BPTREE_ORDER + 1];
-        bptree_value values[BPTREE_ORDER];
-    } slots;
-} bptree_node;
-
-struct sakura_bptree {
-    bptree_node *root;
-    bptree_node *first_leaf;
-    uint64_t len;
-};
-
-static int key_cmp(const uint8_t a[SAKURA_SHA32_KEY_SIZE],
-                   const uint8_t b[SAKURA_SHA32_KEY_SIZE])
-{
-    return memcmp(a, b, SAKURA_SHA32_KEY_SIZE);
-}
-
-static void key_copy(uint8_t dst[SAKURA_SHA32_KEY_SIZE],
-                     const uint8_t src[SAKURA_SHA32_KEY_SIZE])
-{
-    memcpy(dst, src, SAKURA_SHA32_KEY_SIZE);
-}
-
-static bptree_node *node_create(int is_leaf)
-{
-    bptree_node *node = (bptree_node *)calloc(1, sizeof(bptree_node));
-    if (node == NULL) {
-        return NULL;
-    }
-    node->is_leaf = is_leaf;
-    return node;
-}
-
-static void node_free(bptree_node *node)
-{
-    int i;
-
-    if (node == NULL) {
-        return;
-    }
-
-    if (node->is_leaf) {
-        for (i = 0; i < node->key_count; i++) {
-            free(node->slots.values[i].data);
-        }
-    } else {
-        for (i = 0; i <= node->key_count; i++) {
-            node_free(node->slots.children[i]);
-        }
-    }
-
-    free(node);
-}
-
-static int lower_bound_keys(const uint8_t keys[][SAKURA_SHA32_KEY_SIZE],
-                            int count,
-                            const uint8_t key[SAKURA_SHA32_KEY_SIZE])
-{
-    int lo = 0;
-    int hi = count;
-
-    while (lo < hi) {
-        int mid = lo + (hi - lo) / 2;
-        if (key_cmp(keys[mid], key) < 0) {
-            lo = mid + 1;
-        } else {
-            hi = mid;
-        }
-    }
-
-    return lo;
-}
-
-static int upper_bound_keys(const uint8_t keys[][SAKURA_SHA32_KEY_SIZE],
-                            int count,
-                            const uint8_t key[SAKURA_SHA32_KEY_SIZE])
-{
-    int lo = 0;
-    int hi = count;
-
-    while (lo < hi) {
-        int mid = lo + (hi - lo) / 2;
-        if (key_cmp(keys[mid], key) <= 0) {
-            lo = mid + 1;
-        } else {
-            hi = mid;
-        }
-    }
-
-    return lo;
-}
-
-static bptree_node *find_leaf(const sakura_bptree *tree,
-                              const uint8_t key[SAKURA_SHA32_KEY_SIZE])
-{
-    bptree_node *node;
-
-    if (tree == NULL || tree->root == NULL) {
-        return NULL;
-    }
-
-    node = tree->root;
-    while (!node->is_leaf) {
-        int idx = upper_bound_keys(node->keys, node->key_count, key);
-        node = node->slots.children[idx];
-    }
-
-    return node;
-}
-
-static void refresh_first_leaf(sakura_bptree *tree)
-{
-    bptree_node *node;
-
-    if (tree == NULL || tree->root == NULL) {
-        return;
-    }
-
-    node = tree->root;
-    while (!node->is_leaf) {
-        node = node->slots.children[0];
-    }
-    tree->first_leaf = node;
-}
-
-static int subtree_first_key(const bptree_node *node,
-                             uint8_t out[SAKURA_SHA32_KEY_SIZE])
-{
-    while (node != NULL && !node->is_leaf) {
-        node = node->slots.children[0];
-    }
-    if (node == NULL || node->key_count == 0) {
-        return 0;
-    }
-    key_copy(out, node->keys[0]);
-    return 1;
-}
-
-static void update_parent_separator(bptree_node *node)
-{
-    bptree_node *parent;
-    uint8_t first_key[SAKURA_SHA32_KEY_SIZE];
-
-    while (node != NULL && node->parent != NULL) {
-        int i;
-        parent = node->parent;
-        for (i = 1; i <= parent->key_count; i++) {
-            if (parent->slots.children[i] == node) {
-                if (subtree_first_key(node, first_key)) {
-                    key_copy(parent->keys[i - 1], first_key);
-                }
-                return;
-            }
-        }
-        node = parent;
-    }
-}
-
-static sakura_bptree_status value_make(bptree_value *slot,
-                                       const void *value,
-                                       uint64_t value_len)
-{
-    uint8_t *copy = NULL;
-
-    if (value_len > 0 && value == NULL) {
-        return SAKURA_BPTREE_INVALID_ARGUMENT;
-    }
-
-    if (value_len > 0) {
-        if ((uint64_t)((size_t)value_len) != value_len) {
-            return SAKURA_BPTREE_INVALID_ARGUMENT;
-        }
-        copy = (uint8_t *)malloc((size_t)value_len);
-        if (copy == NULL) {
-            return SAKURA_BPTREE_OUT_OF_MEMORY;
-        }
-        memcpy(copy, value, (size_t)value_len);
-    }
-
-    slot->data = copy;
-    slot->len = value_len;
-    return SAKURA_BPTREE_OK;
-}
-
-static sakura_bptree_status value_replace(bptree_value *slot,
-                                          const void *value,
-                                          uint64_t value_len)
-{
-    bptree_value next;
-    sakura_bptree_status status;
-
-    next.data = NULL;
-    next.len = 0;
-    status = value_make(&next, value, value_len);
-    if (status != SAKURA_BPTREE_OK) {
-        return status;
-    }
-
-    free(slot->data);
-    *slot = next;
-    return SAKURA_BPTREE_OK;
-}
-
-static sakura_bptree_status insert_into_parent(sakura_bptree *tree,
-                                               bptree_node *left,
-                                               const uint8_t key[SAKURA_SHA32_KEY_SIZE],
-                                               bptree_node *right);
-
-static sakura_bptree_status split_internal(sakura_bptree *tree, bptree_node *node)
-{
-    bptree_node *right;
-    int split;
-    int right_keys;
-    int i;
-    uint8_t promote[SAKURA_SHA32_KEY_SIZE];
-
-    right = node_create(0);
-    if (right == NULL) {
-        return SAKURA_BPTREE_OUT_OF_MEMORY;
-    }
-
-    split = BPTREE_ORDER / 2;
-    right_keys = node->key_count - split - 1;
-    key_copy(promote, node->keys[split]);
-
-    for (i = 0; i < right_keys; i++) {
-        key_copy(right->keys[i], node->keys[split + 1 + i]);
-    }
-    for (i = 0; i <= right_keys; i++) {
-        right->slots.children[i] = node->slots.children[split + 1 + i];
-        if (right->slots.children[i] != NULL) {
-            right->slots.children[i]->parent = right;
-        }
-        node->slots.children[split + 1 + i] = NULL;
-    }
-
-    right->key_count = right_keys;
-    node->key_count = split;
-    right->parent = node->parent;
-
-    return insert_into_parent(tree, node, promote, right);
-}
-
-static sakura_bptree_status insert_into_parent(sakura_bptree *tree,
-                                               bptree_node *left,
-                                               const uint8_t key[SAKURA_SHA32_KEY_SIZE],
-                                               bptree_node *right)
-{
-    bptree_node *parent;
-    int left_index;
-    int i;
-
-    if (left->parent == NULL) {
-        bptree_node *root = node_create(0);
-        if (root == NULL) {
-            return SAKURA_BPTREE_OUT_OF_MEMORY;
-        }
-        key_copy(root->keys[0], key);
-        root->slots.children[0] = left;
-        root->slots.children[1] = right;
-        root->key_count = 1;
-        left->parent = root;
-        right->parent = root;
-        tree->root = root;
-        return SAKURA_BPTREE_OK;
-    }
-
-    parent = left->parent;
-    left_index = 0;
-    while (left_index <= parent->key_count && parent->slots.children[left_index] != left) {
-        left_index++;
-    }
-    if (left_index > parent->key_count) {
-        return SAKURA_BPTREE_CORRUPT_FILE;
-    }
-
-    for (i = parent->key_count; i > left_index; i--) {
-        key_copy(parent->keys[i], parent->keys[i - 1]);
-    }
-    for (i = parent->key_count + 1; i > left_index + 1; i--) {
-        parent->slots.children[i] = parent->slots.children[i - 1];
-    }
-
-    key_copy(parent->keys[left_index], key);
-    parent->slots.children[left_index + 1] = right;
-    right->parent = parent;
-    parent->key_count++;
-
-    if (parent->key_count <= BPTREE_MAX_KEYS) {
-        return SAKURA_BPTREE_OK;
-    }
-
-    return split_internal(tree, parent);
-}
-
-static sakura_bptree_status split_leaf_and_insert(sakura_bptree *tree,
-                                                  bptree_node *leaf,
-                                                  const uint8_t key[SAKURA_SHA32_KEY_SIZE],
-                                                  const void *value,
-                                                  uint64_t value_len)
-{
-    uint8_t temp_keys[BPTREE_ORDER][SAKURA_SHA32_KEY_SIZE];
-    bptree_value temp_values[BPTREE_ORDER];
-    bptree_value new_value;
-    bptree_node *right;
-    int insert_at;
-    int split;
-    int right_count;
-    int i;
-    sakura_bptree_status status;
-
-    memset(temp_values, 0, sizeof(temp_values));
-    new_value.data = NULL;
-    new_value.len = 0;
-    status = value_make(&new_value, value, value_len);
-    if (status != SAKURA_BPTREE_OK) {
-        return status;
-    }
-
-    right = node_create(1);
-    if (right == NULL) {
-        free(new_value.data);
-        return SAKURA_BPTREE_OUT_OF_MEMORY;
-    }
-
-    insert_at = lower_bound_keys(leaf->keys, leaf->key_count, key);
-
-    for (i = 0; i < insert_at; i++) {
-        key_copy(temp_keys[i], leaf->keys[i]);
-        temp_values[i] = leaf->slots.values[i];
-        leaf->slots.values[i].data = NULL;
-        leaf->slots.values[i].len = 0;
-    }
-    key_copy(temp_keys[insert_at], key);
-    temp_values[insert_at] = new_value;
-    for (i = insert_at; i < leaf->key_count; i++) {
-        key_copy(temp_keys[i + 1], leaf->keys[i]);
-        temp_values[i + 1] = leaf->slots.values[i];
-        leaf->slots.values[i].data = NULL;
-        leaf->slots.values[i].len = 0;
-    }
-
-    split = BPTREE_ORDER / 2;
-    leaf->key_count = split;
-    right_count = BPTREE_ORDER - split;
-    right->key_count = right_count;
-    right->parent = leaf->parent;
-    right->next = leaf->next;
-    leaf->next = right;
-
-    for (i = 0; i < split; i++) {
-        key_copy(leaf->keys[i], temp_keys[i]);
-        leaf->slots.values[i] = temp_values[i];
-    }
-    for (i = 0; i < right_count; i++) {
-        key_copy(right->keys[i], temp_keys[split + i]);
-        right->slots.values[i] = temp_values[split + i];
-    }
-
-    tree->len++;
-    return insert_into_parent(tree, leaf, right->keys[0], right);
-}
-
-SAKURA_BPTREE_API sakura_bptree *sakura_bptree_create(void)
-{
-    sakura_bptree *tree = (sakura_bptree *)calloc(1, sizeof(sakura_bptree));
-    if (tree == NULL) {
-        return NULL;
-    }
-
-    tree->root = node_create(1);
-    if (tree->root == NULL) {
-        free(tree);
-        return NULL;
-    }
-    tree->first_leaf = tree->root;
-    return tree;
-}
-
-SAKURA_BPTREE_API void sakura_bptree_free(sakura_bptree *tree)
-{
-    if (tree == NULL) {
-        return;
-    }
-    node_free(tree->root);
-    free(tree);
-}
-
-SAKURA_BPTREE_API uint64_t sakura_bptree_len(const sakura_bptree *tree)
-{
-    return tree == NULL ? 0 : tree->len;
-}
-
-SAKURA_BPTREE_API sakura_bptree_status sakura_bptree_put(sakura_bptree *tree,
-                                                         const uint8_t key[SAKURA_SHA32_KEY_SIZE],
-                                                         const void *value,
-                                                         uint64_t value_len)
-{
-    bptree_node *leaf;
-    int pos;
-    int i;
-    sakura_bptree_status status;
-
-    if (tree == NULL || key == NULL || (value == NULL && value_len > 0)) {
-        return SAKURA_BPTREE_INVALID_ARGUMENT;
-    }
-
-    leaf = find_leaf(tree, key);
-    if (leaf == NULL) {
-        return SAKURA_BPTREE_CORRUPT_FILE;
-    }
-
-    pos = lower_bound_keys(leaf->keys, leaf->key_count, key);
-    if (pos < leaf->key_count && key_cmp(leaf->keys[pos], key) == 0) {
-        return value_replace(&leaf->slots.values[pos], value, value_len);
-    }
-
-    if (leaf->key_count == BPTREE_MAX_KEYS) {
-        return split_leaf_and_insert(tree, leaf, key, value, value_len);
-    }
-
-    for (i = leaf->key_count; i > pos; i--) {
-        key_copy(leaf->keys[i], leaf->keys[i - 1]);
-        leaf->slots.values[i] = leaf->slots.values[i - 1];
-    }
-
-    key_copy(leaf->keys[pos], key);
-    leaf->slots.values[pos].data = NULL;
-    leaf->slots.values[pos].len = 0;
-    status = value_make(&leaf->slots.values[pos], value, value_len);
-    if (status != SAKURA_BPTREE_OK) {
-        return status;
-    }
-
-    leaf->key_count++;
-    tree->len++;
-    if (pos == 0) {
-        update_parent_separator(leaf);
-    }
-
-    return SAKURA_BPTREE_OK;
-}
-
-SAKURA_BPTREE_API sakura_bptree_status sakura_bptree_get(const sakura_bptree *tree,
-                                                         const uint8_t key[SAKURA_SHA32_KEY_SIZE],
-                                                         const void **value,
-                                                         uint64_t *value_len)
-{
-    bptree_node *leaf;
-    int pos;
-
-    if (tree == NULL || key == NULL || value == NULL || value_len == NULL) {
-        return SAKURA_BPTREE_INVALID_ARGUMENT;
-    }
-
-    leaf = find_leaf(tree, key);
-    if (leaf == NULL) {
-        return SAKURA_BPTREE_NOT_FOUND;
-    }
-
-    pos = lower_bound_keys(leaf->keys, leaf->key_count, key);
-    if (pos >= leaf->key_count || key_cmp(leaf->keys[pos], key) != 0) {
-        return SAKURA_BPTREE_NOT_FOUND;
-    }
-
-    *value = leaf->slots.values[pos].data;
-    *value_len = leaf->slots.values[pos].len;
-    return SAKURA_BPTREE_OK;
-}
-
-SAKURA_BPTREE_API sakura_bptree_status sakura_bptree_copy_value(const sakura_bptree *tree,
-                                                                const uint8_t key[SAKURA_SHA32_KEY_SIZE],
-                                                                void *buffer,
-                                                                uint64_t buffer_len,
-                                                                uint64_t *value_len)
-{
-    const void *value;
-    uint64_t len;
-    sakura_bptree_status status;
-
-    if (value_len == NULL || (buffer == NULL && buffer_len > 0)) {
-        return SAKURA_BPTREE_INVALID_ARGUMENT;
-    }
-
-    status = sakura_bptree_get(tree, key, &value, &len);
-    if (status != SAKURA_BPTREE_OK) {
-        return status;
-    }
-
-    *value_len = len;
-    if (buffer_len < len) {
-        return SAKURA_BPTREE_INVALID_ARGUMENT;
-    }
-    if (len > 0) {
-        memcpy(buffer, value, (size_t)len);
-    }
-    return SAKURA_BPTREE_OK;
-}
-
-SAKURA_BPTREE_API sakura_bptree_status sakura_bptree_remove(sakura_bptree *tree,
-                                                            const uint8_t key[SAKURA_SHA32_KEY_SIZE])
-{
-    bptree_node *leaf;
-    int pos;
-    int i;
-
-    if (tree == NULL || key == NULL) {
-        return SAKURA_BPTREE_INVALID_ARGUMENT;
-    }
-
-    leaf = find_leaf(tree, key);
-    if (leaf == NULL) {
-        return SAKURA_BPTREE_NOT_FOUND;
-    }
-    pos = lower_bound_keys(leaf->keys, leaf->key_count, key);
-    if (pos >= leaf->key_count || key_cmp(leaf->keys[pos], key) != 0) {
-        return SAKURA_BPTREE_NOT_FOUND;
-    }
-
-    free(leaf->slots.values[pos].data);
-    for (i = pos; i < leaf->key_count - 1; i++) {
-        key_copy(leaf->keys[i], leaf->keys[i + 1]);
-        leaf->slots.values[i] = leaf->slots.values[i + 1];
-    }
-    leaf->slots.values[leaf->key_count - 1].data = NULL;
-    leaf->slots.values[leaf->key_count - 1].len = 0;
-    leaf->key_count--;
-    tree->len--;
-
-    if (leaf->key_count > 0 && pos == 0) {
-        update_parent_separator(leaf);
-    }
-
-    return SAKURA_BPTREE_OK;
-}
-
-SAKURA_BPTREE_API void sakura_bptree_iterate(const sakura_bptree *tree,
-                                             sakura_bptree_iter_cb callback,
-                                             void *user_data)
-{
-    bptree_node *node;
-
-    if (tree == NULL || callback == NULL) {
-        return;
-    }
-
-    node = tree->first_leaf;
-    while (node != NULL) {
-        int i;
-        for (i = 0; i < node->key_count; i++) {
-            callback(node->keys[i], node->slots.values[i].data,
-                     node->slots.values[i].len, user_data);
-        }
-        node = node->next;
-    }
-}
-
-typedef struct buf_writer {
-    uint8_t *data;
-    uint64_t len;
-    uint64_t cap;
-} buf_writer;
-
-static int buf_writer_init(buf_writer *w)
-{
-    w->data = (uint8_t *)malloc(256);
-    if (w->data == NULL) {
-        return 0;
-    }
-    w->len = 0;
-    w->cap = 256;
-    return 1;
-}
-
-static int buf_writer_write(buf_writer *w, const void *src, uint64_t n)
-{
-    uint64_t needed = w->len + n;
-    if (needed > w->cap) {
-        uint64_t new_cap = w->cap * 2;
-        uint8_t *p;
-        while (new_cap < needed) {
-            new_cap *= 2;
-        }
-        p = (uint8_t *)realloc(w->data, (size_t)new_cap);
-        if (p == NULL) {
-            return 0;
-        }
-        w->data = p;
-        w->cap = new_cap;
-    }
-    memcpy(w->data + w->len, src, (size_t)n);
-    w->len += n;
-    return 1;
-}
-
-typedef struct buf_reader {
-    const uint8_t *data;
-    uint64_t len;
-    uint64_t pos;
-} buf_reader;
-
-static int buf_reader_read(buf_reader *r, void *dst, uint64_t n)
-{
-    if (r->pos + n > r->len) {
-        return 0;
-    }
-    memcpy(dst, r->data + r->pos, (size_t)n);
-    r->pos += n;
-    return 1;
-}
-
-static int buf_write_u32(buf_writer *w, uint32_t value)
-{
-    uint8_t b[4];
-    b[0] = (uint8_t)(value & 0xffu);
-    b[1] = (uint8_t)((value >> 8) & 0xffu);
-    b[2] = (uint8_t)((value >> 16) & 0xffu);
-    b[3] = (uint8_t)((value >> 24) & 0xffu);
-    return buf_writer_write(w, b, sizeof(b));
-}
-
-static int buf_write_u64(buf_writer *w, uint64_t value)
-{
-    uint8_t b[8];
-    int i;
-    for (i = 0; i < 8; i++) {
-        b[i] = (uint8_t)((value >> (8 * i)) & 0xffu);
-    }
-    return buf_writer_write(w, b, sizeof(b));
-}
-
-static int buf_read_u32(buf_reader *r, uint32_t *value)
-{
-    uint8_t b[4];
-    if (!buf_reader_read(r, b, sizeof(b))) {
-        return 0;
-    }
-    *value = ((uint32_t)b[0]) | ((uint32_t)b[1] << 8) |
-             ((uint32_t)b[2] << 16) | ((uint32_t)b[3] << 24);
-    return 1;
-}
-
-static int buf_read_u64(buf_reader *r, uint64_t *value)
-{
-    uint8_t b[8];
-    int i;
-    if (!buf_reader_read(r, b, sizeof(b))) {
-        return 0;
-    }
-    *value = 0;
-    for (i = 0; i < 8; i++) {
-        *value |= ((uint64_t)b[i]) << (8 * i);
-    }
-    return 1;
-}
-
-static int write_u32(FILE *file, uint32_t value)
-{
-    uint8_t b[4];
-    b[0] = (uint8_t)(value & 0xffu);
-    b[1] = (uint8_t)((value >> 8) & 0xffu);
-    b[2] = (uint8_t)((value >> 16) & 0xffu);
-    b[3] = (uint8_t)((value >> 24) & 0xffu);
-    return fwrite(b, 1, sizeof(b), file) == sizeof(b);
-}
-
-static int write_u64(FILE *file, uint64_t value)
-{
-    uint8_t b[8];
-    int i;
-    for (i = 0; i < 8; i++) {
-        b[i] = (uint8_t)((value >> (8 * i)) & 0xffu);
-    }
-    return fwrite(b, 1, sizeof(b), file) == sizeof(b);
-}
-
-static int read_u32(FILE *file, uint32_t *value)
-{
-    uint8_t b[4];
-    if (fread(b, 1, sizeof(b), file) != sizeof(b)) {
-        return 0;
-    }
-    *value = ((uint32_t)b[0]) | ((uint32_t)b[1] << 8) |
-             ((uint32_t)b[2] << 16) | ((uint32_t)b[3] << 24);
-    return 1;
-}
-
-static int read_u64(FILE *file, uint64_t *value)
-{
-    uint8_t b[8];
-    int i;
-
-    if (fread(b, 1, sizeof(b), file) != sizeof(b)) {
-        return 0;
-    }
-
-    *value = 0;
-    for (i = 0; i < 8; i++) {
-        *value |= ((uint64_t)b[i]) << (8 * i);
-    }
-    return 1;
-}
-
-SAKURA_BPTREE_API sakura_bptree_status sakura_bptree_save(const sakura_bptree *tree,
-                                                          const char *path)
-{
-    FILE *file;
-    bptree_node *node;
-
-    if (tree == NULL || path == NULL) {
-        return SAKURA_BPTREE_INVALID_ARGUMENT;
-    }
-
-    file = fopen(path, "wb");
-    if (file == NULL) {
-        return SAKURA_BPTREE_IO_ERROR;
-    }
-
-    if (fwrite(BPTREE_MAGIC, 1, BPTREE_MAGIC_SIZE, file) != BPTREE_MAGIC_SIZE ||
-        !write_u32(file, BPTREE_VERSION) ||
-        !write_u32(file, SAKURA_SHA32_KEY_SIZE) ||
-        !write_u64(file, tree->len)) {
-        fclose(file);
-        return SAKURA_BPTREE_IO_ERROR;
-    }
-
-    node = tree->first_leaf;
-    while (node != NULL) {
-        int i;
-        for (i = 0; i < node->key_count; i++) {
-            if (node->slots.values[i].len > 0 &&
-                (uint64_t)((size_t)node->slots.values[i].len) != node->slots.values[i].len) {
-                fclose(file);
-                return SAKURA_BPTREE_INVALID_ARGUMENT;
-            }
-            if (fwrite(node->keys[i], 1, SAKURA_SHA32_KEY_SIZE, file) != SAKURA_SHA32_KEY_SIZE ||
-                !write_u64(file, node->slots.values[i].len) ||
-                (node->slots.values[i].len > 0 &&
-                 fwrite(node->slots.values[i].data, 1, (size_t)node->slots.values[i].len, file) !=
-                     (size_t)node->slots.values[i].len)) {
-                fclose(file);
-                return SAKURA_BPTREE_IO_ERROR;
-            }
-        }
-        node = node->next;
-    }
-
-    if (fclose(file) != 0) {
-        return SAKURA_BPTREE_IO_ERROR;
-    }
-    return SAKURA_BPTREE_OK;
-}
-
-SAKURA_BPTREE_API sakura_bptree_status sakura_bptree_load(const char *path,
-                                                          sakura_bptree **tree_out)
-{
-    FILE *file;
-    uint8_t magic[BPTREE_MAGIC_SIZE];
-    uint32_t version;
-    uint32_t key_size;
-    uint64_t count;
-    uint64_t i;
-    sakura_bptree *tree;
-
-    if (path == NULL || tree_out == NULL) {
-        return SAKURA_BPTREE_INVALID_ARGUMENT;
-    }
-    *tree_out = NULL;
-
-    file = fopen(path, "rb");
-    if (file == NULL) {
-        return SAKURA_BPTREE_IO_ERROR;
-    }
-
-    if (fread(magic, 1, sizeof(magic), file) != sizeof(magic) ||
-        memcmp(magic, BPTREE_MAGIC, BPTREE_MAGIC_SIZE) != 0 ||
-        !read_u32(file, &version) ||
-        !read_u32(file, &key_size) ||
-        !read_u64(file, &count) ||
-        version != BPTREE_VERSION ||
-        key_size != SAKURA_SHA32_KEY_SIZE) {
-        fclose(file);
-        return SAKURA_BPTREE_CORRUPT_FILE;
-    }
-
-    tree = sakura_bptree_create();
-    if (tree == NULL) {
-        fclose(file);
-        return SAKURA_BPTREE_OUT_OF_MEMORY;
-    }
-
-    for (i = 0; i < count; i++) {
-        uint8_t key[SAKURA_SHA32_KEY_SIZE];
-        uint64_t value_len;
-        uint8_t *value = NULL;
-        sakura_bptree_status status;
-
-        if (fread(key, 1, SAKURA_SHA32_KEY_SIZE, file) != SAKURA_SHA32_KEY_SIZE ||
-            !read_u64(file, &value_len) ||
-            (value_len > 0 && (uint64_t)((size_t)value_len) != value_len)) {
-            sakura_bptree_free(tree);
-            fclose(file);
-            return SAKURA_BPTREE_CORRUPT_FILE;
-        }
-        if (value_len > 0) {
-            value = (uint8_t *)malloc((size_t)value_len);
-            if (value == NULL) {
-                sakura_bptree_free(tree);
-                fclose(file);
-                return SAKURA_BPTREE_OUT_OF_MEMORY;
-            }
-            if (fread(value, 1, (size_t)value_len, file) != (size_t)value_len) {
-                free(value);
-                sakura_bptree_free(tree);
-                fclose(file);
-                return SAKURA_BPTREE_CORRUPT_FILE;
-            }
-        }
-
-        status = sakura_bptree_put(tree, key, value, value_len);
-        free(value);
-        if (status != SAKURA_BPTREE_OK) {
-            sakura_bptree_free(tree);
-            fclose(file);
-            return status;
-        }
-    }
-
-    if (fgetc(file) != EOF) {
-        sakura_bptree_free(tree);
-        fclose(file);
-        return SAKURA_BPTREE_CORRUPT_FILE;
-    }
-
-    fclose(file);
-    refresh_first_leaf(tree);
-    *tree_out = tree;
-    return SAKURA_BPTREE_OK;
-}
-
-SAKURA_BPTREE_API sakura_bptree_status sakura_bptree_serialize(const sakura_bptree *tree,
-                                                               uint8_t **out,
-                                                               uint64_t *out_len)
-{
-    buf_writer w;
-    bptree_node *node;
-
-    if (tree == NULL || out == NULL || out_len == NULL) {
-        return SAKURA_BPTREE_INVALID_ARGUMENT;
-    }
-
-    if (!buf_writer_init(&w)) {
-        return SAKURA_BPTREE_OUT_OF_MEMORY;
-    }
-
-    if (!buf_writer_write(&w, BPTREE_MAGIC, BPTREE_MAGIC_SIZE) ||
-        !buf_write_u32(&w, BPTREE_VERSION) ||
-        !buf_write_u32(&w, SAKURA_SHA32_KEY_SIZE) ||
-        !buf_write_u64(&w, tree->len)) {
-        free(w.data);
-        return SAKURA_BPTREE_OUT_OF_MEMORY;
-    }
-
-    node = tree->first_leaf;
-    while (node != NULL) {
-        int i;
-        for (i = 0; i < node->key_count; i++) {
-            uint64_t vlen = node->slots.values[i].len;
-            if (!buf_writer_write(&w, node->keys[i], SAKURA_SHA32_KEY_SIZE) ||
-                !buf_write_u64(&w, vlen) ||
-                (vlen > 0 && !buf_writer_write(&w, node->slots.values[i].data, vlen))) {
-                free(w.data);
-                return SAKURA_BPTREE_OUT_OF_MEMORY;
-            }
-        }
-        node = node->next;
-    }
-
-    *out = w.data;
-    *out_len = w.len;
-    return SAKURA_BPTREE_OK;
-}
-
-SAKURA_BPTREE_API sakura_bptree_status sakura_bptree_deserialize(const uint8_t *data,
-                                                                  uint64_t data_len,
-                                                                  sakura_bptree **tree_out)
-{
-    buf_reader r;
-    uint8_t magic[BPTREE_MAGIC_SIZE];
-    uint32_t version;
-    uint32_t key_size;
-    uint64_t count;
-    uint64_t i;
-    sakura_bptree *tree;
-
-    if (data == NULL || tree_out == NULL) {
-        return SAKURA_BPTREE_INVALID_ARGUMENT;
-    }
-    *tree_out = NULL;
-
-    r.data = data;
-    r.len = data_len;
-    r.pos = 0;
-
-    if (!buf_reader_read(&r, magic, BPTREE_MAGIC_SIZE) ||
-        memcmp(magic, BPTREE_MAGIC, BPTREE_MAGIC_SIZE) != 0 ||
-        !buf_read_u32(&r, &version) ||
-        !buf_read_u32(&r, &key_size) ||
-        !buf_read_u64(&r, &count) ||
-        version != BPTREE_VERSION ||
-        key_size != SAKURA_SHA32_KEY_SIZE) {
-        return SAKURA_BPTREE_CORRUPT_FILE;
-    }
-
-    tree = sakura_bptree_create();
-    if (tree == NULL) {
-        return SAKURA_BPTREE_OUT_OF_MEMORY;
-    }
-
-    for (i = 0; i < count; i++) {
-        uint8_t key[SAKURA_SHA32_KEY_SIZE];
-        uint64_t value_len;
-        uint8_t *value = NULL;
-        sakura_bptree_status status;
-
-        if (!buf_reader_read(&r, key, SAKURA_SHA32_KEY_SIZE) ||
-            !buf_read_u64(&r, &value_len) ||
-            (value_len > 0 && (uint64_t)((size_t)value_len) != value_len)) {
-            sakura_bptree_free(tree);
-            return SAKURA_BPTREE_CORRUPT_FILE;
-        }
-        if (value_len > 0) {
-            value = (uint8_t *)malloc((size_t)value_len);
-            if (value == NULL) {
-                sakura_bptree_free(tree);
-                return SAKURA_BPTREE_OUT_OF_MEMORY;
-            }
-            if (!buf_reader_read(&r, value, value_len)) {
-                free(value);
-                sakura_bptree_free(tree);
-                return SAKURA_BPTREE_CORRUPT_FILE;
-            }
-        }
-
-        status = sakura_bptree_put(tree, key, value, value_len);
-        free(value);
-        if (status != SAKURA_BPTREE_OK) {
-            sakura_bptree_free(tree);
-            return status;
-        }
-    }
-
-    if (r.pos != r.len) {
-        sakura_bptree_free(tree);
-        return SAKURA_BPTREE_CORRUPT_FILE;
-    }
-
-    refresh_first_leaf(tree);
-    *tree_out = tree;
-    return SAKURA_BPTREE_OK;
-}
-
-SAKURA_BPTREE_API const char *sakura_bptree_status_string(sakura_bptree_status status)
-{
-    switch (status) {
-    case SAKURA_BPTREE_OK:
-        return "ok";
-    case SAKURA_BPTREE_NOT_FOUND:
-        return "not found";
-    case SAKURA_BPTREE_INVALID_ARGUMENT:
-        return "invalid argument";
-    case SAKURA_BPTREE_OUT_OF_MEMORY:
-        return "out of memory";
-    case SAKURA_BPTREE_IO_ERROR:
-        return "io error";
-    case SAKURA_BPTREE_CORRUPT_FILE:
-        return "corrupt file";
-    default:
-        return "unknown";
-    }
-}