aboutsummaryrefslogtreecommitdiffstats
path: root/shared/shabptree
diff options
context:
space:
mode:
Diffstat (limited to 'shared/shabptree')
-rw-r--r--shared/shabptree/dune5
-rw-r--r--shared/shabptree/shabptree.c1031
2 files changed, 1036 insertions, 0 deletions
diff --git a/shared/shabptree/dune b/shared/shabptree/dune
new file mode 100644
index 0000000..43cba80
--- /dev/null
+++ b/shared/shabptree/dune
@@ -0,0 +1,5 @@
+(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
new file mode 100644
index 0000000..0337345
--- /dev/null
+++ b/shared/shabptree/shabptree.c
@@ -0,0 +1,1031 @@
+#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";
+ }
+}
generated by cgit v1.2.3 (git 2.25.1) at 2026-11-04 02:07:58 +0000