summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/btree_naive.c90
1 files changed, 54 insertions, 36 deletions
diff --git a/src/btree_naive.c b/src/btree_naive.c
index be6fdd3..6e96f7f 100644
--- a/src/btree_naive.c
+++ b/src/btree_naive.c
@@ -5,12 +5,14 @@
#include <stdlib.h>
#include <string.h>
+#include <sys/types.h>
+
/* Definitions */
typedef unsigned char byte;
struct node {
- size_t n; /* number of items/keys/elements */
- size_t c; /* number of children */
+ ssize_t n; /* number of items/keys/elements */
+ ssize_t c; /* number of children */
byte *items;
struct node **children;
};
@@ -22,7 +24,7 @@ struct btree {
/* Size stuffs */
size_t elem_size;
- size_t degree;
+ ssize_t degree;
struct node *root;
@@ -41,21 +43,24 @@ node_maxdegree(t) (2 * t - 1)
node_mindegree(t) (t - 1)
#define \
-node_full(degree, t) (t->n == 2 * degree - 1)
+node_full(degree, t) (t->n >= 2 * degree - 1)
/* Node memory */
/* `node_new` allocates a new leaf node, children should be added and allocated
* when the node is no longer a leaf node */
-struct node* node_new(const size_t degree, const size_t elem_size) {
- const size_t max_items = 2 * degree - 1;
+struct node* node_new(const ssize_t degree, const size_t elem_size) {
+ const size_t max_items = 2 * degree;
struct node *retval = malloc(sizeof(struct node));
+ printf("Allocating node with %ld bytes: max_items:%ld elem_size:%ld\n", max_items * elem_size, max_items, elem_size);
retval->n = 0;
retval->c = 0;
- retval->items = calloc(max_items, sizeof(elem_size));
+ retval->items = calloc(max_items, elem_size);
retval->children = NULL;
+ printf("Item address: %p\n", (void*)retval->items);
+
return retval;
}
@@ -63,8 +68,8 @@ struct node* node_new(const size_t degree, const size_t elem_size) {
* for it.
* returnvalue: `false` if we we're unable to allocate space for the new
* children. */
-bool node_transition(const size_t degree, const size_t elem_size, struct node *node) {
- const int max_children = 2 * degree;
+bool node_transition(const ssize_t degree, const size_t elem_size, struct node *node) {
+ const int max_children = 2 * degree + 1;
int c;
/* Allocate pointers for children */
node->children = calloc(max_children, sizeof(struct node*));
@@ -87,41 +92,45 @@ bool node_transition(const size_t degree, const size_t elem_size, struct node *n
}
}
- node->c = c;
+ /* node->c = c; */
return true;
}
void node_free(struct node *node, size_t elem_size, void (*dealloc)(void*)) {
- size_t i;
+ ssize_t i;
if (node == NULL) return;
- for (i = 0; i < node->c; i++) {
- node_free((node->children)[i], elem_size, dealloc);
+ if (!node_leaf(node)) {
+ for (i = 0; i < node->c; i++) {
+ node_free((node->children)[i], elem_size, dealloc);
+ }
}
- if (!node_leaf(node))
- dealloc(node->items);
+ dealloc(node->items);
+ node->items = NULL;
free(node);
}
/* Split a child of `nonfull` of index `i` */
-void node_tree_split_child(const size_t t, const size_t elem_size, struct node *nonfull, size_t i) {
+void node_tree_split_child(
+ const size_t t,
+ const size_t elem_size,
+ struct node *nonfull,
+ size_t i) {
struct node *z = node_new(t, elem_size);
struct node *y = nonfull->children[i];
size_t j;
-
- printf("Splitting tree!\n");
- __asm__("int3");
+ const ssize_t min_elem = (t-1 <= 2) ? 2 : t-1;
/* `z` should be a branching node if `y` is */
- if (node_leaf(y)) {
+ if (!node_leaf(y)) {
node_transition(t, elem_size, z);
}
z->n = t - 1;
- for (j = 0; j < t - 1; j++) {
+ for (j = 0; j < min_elem; j++) {
const size_t offset_dst = elem_size * j;
const size_t offset_src = offset_dst + elem_size * t;
memcpy((z->items) + offset_dst, (y->items) + offset_src, elem_size);
@@ -141,6 +150,7 @@ void node_tree_split_child(const size_t t, const size_t elem_size, struct node *
nonfull->children[j + 1] = nonfull->children[j];
}
nonfull->children[i+1] = z;
+ nonfull->c++;
for (j = nonfull->n; j > i; j--) {
const size_t offset = j * elem_size;
@@ -150,13 +160,10 @@ void node_tree_split_child(const size_t t, const size_t elem_size, struct node *
}
memcpy((nonfull->items) + i * elem_size,
- (y->items) + elem_size * t,
+ (y->items) + elem_size * (t-1),
elem_size);
nonfull->n++;
-
- __asm__("int3");
-
}
/* `node_split` splits a _full_ node (c = 2t-1 items) into two nodes with t-1
@@ -175,14 +182,15 @@ struct node *node_split() {
return NULL;
}
+/* return: Returns the new root, if a split happens */
struct node* node_insert_nonfull(
struct node *root,
void *elem,
- const size_t degree,
+ const ssize_t degree,
const size_t elem_size,
int (*cmp)(const void *a, const void *b)) {
/* TODO check correctness */
- size_t i = root->n - 1;
+ ssize_t i = root->n - 1;
if (node_leaf(root)) {
size_t offset = elem_size * i;
while (i >= 0 && cmp(elem, root->items + offset) == BTREE_CMP_LT) {
@@ -191,17 +199,19 @@ struct node* node_insert_nonfull(
i--;
offset = elem_size * i;
}
- offset = elem_size * (i++);
+ offset = elem_size * (++i);
memcpy(root->items + offset, elem, elem_size);
+ root->n++;
} else {
size_t offset = elem_size * i;
+ struct node *nextchild = NULL;
while (i >= 0 && cmp(elem, root->items + offset) == BTREE_CMP_LT) {
i--;
offset = elem_size * i;
}
i++;
- struct node *nextchild = root->children[i];
+ nextchild = root->children[i];
if (node_full(degree, nextchild)) {
/* TODO Check if the root has changed */
node_tree_split_child(degree, elem_size, root, i);
@@ -211,33 +221,38 @@ struct node* node_insert_nonfull(
}
return node_insert_nonfull(nextchild, elem, degree, elem_size, cmp);
}
+ return NULL; /* TODO: Fix return value */
}
+/* Returns the new root, if a split occurs */
struct node* node_insert(
struct node *root,
void *elem,
- const size_t degree,
+ const ssize_t degree,
const size_t elem_size,
int (*cmp)(const void *a, const void *b)) {
+
+ struct node *s = root;
+
if (node_full(degree, root)) {
- struct node *s = node_new(degree, elem_size);
+ s = node_new(degree, elem_size);
node_transition(degree, elem_size, s);
s->children[s->c++] = root;
/* TODO Check if the root has changed */
node_tree_split_child(degree, elem_size, s, 0);
- return node_insert_nonfull(s, elem, degree, elem_size, cmp);
+ node_insert_nonfull(s, elem, degree, elem_size, cmp);
}
else {
- return node_insert_nonfull(root, elem, degree, elem_size, cmp);
+ node_insert_nonfull(s, elem, degree, elem_size, cmp);
}
- return NULL;
+ return s;
}
void* node_search(struct node *x,
void *key,
int(*cmp)(const void *a, const void *b),
const size_t elem_size) {
- size_t i = 0;
+ ssize_t i = 0;
int last_cmp_res = cmp(key, (const void*)x->items);
while (i < x->n && last_cmp_res > 0) {
@@ -245,7 +260,7 @@ void* node_search(struct node *x,
last_cmp_res = cmp(key, (const void*)(x->items + (i * elem_size)));
}
- if (i < x->n && last_cmp_res == BTREE_CMP_EQ) {
+ if ((ssize_t)i < x->n && last_cmp_res == BTREE_CMP_EQ) {
return (void*)(x->items + (i * elem_size));
} else if (node_leaf(x)) {
return NULL;
@@ -292,6 +307,9 @@ void btree_insert(struct btree *btree, void *elem) {
btree->root = node_new(btree->degree, btree->elem_size);
node_insert(btree->root, elem, btree->degree, btree->elem_size, btree->cmp);
}
+ else {
+ btree->root = node_insert(btree->root, elem, btree->degree, btree->elem_size, btree->cmp);
+ }
}
void* btree_search(struct btree *btree, void *elem) {
generated by cgit v1.3 (git 2.53.0) at 2026-05-23 16:25:52 +0000