aboutsummaryrefslogtreecommitdiffstats
path: root/shared/shabptree/shabptree.c
diff options
context:
space:
mode:
Diffstat (limited to 'shared/shabptree/shabptree.c')
-rw-r--r--shared/shabptree/shabptree.c1031
1 files changed, 0 insertions, 1031 deletions
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";
- }
-}
generated by cgit v1.2.3 (git 2.25.1) at 2026-11-04 05:25:51 +0000