summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/utils/src/btree.c62
1 files changed, 31 insertions, 31 deletions
diff --git a/src/utils/src/btree.c b/src/utils/src/btree.c
index 1e85e6c..9411072 100644
--- a/src/utils/src/btree.c
+++ b/src/utils/src/btree.c
@@ -11,8 +11,8 @@
typedef unsigned char byte;
struct node {
- ssize_t n; /* number of items/keys/elements */
- ssize_t c; /* number of children */
+ size_t n; /* number of items/keys/elements */
+ size_t c; /* number of children */
byte* items;
struct node** children;
};
@@ -24,7 +24,7 @@ struct btree {
/* Size stuffs */
size_t elem_size;
- ssize_t degree;
+ size_t degree;
struct node* root;
@@ -57,7 +57,7 @@ struct btree_iter_t {
/* `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 ssize_t degree, const size_t elem_size) {
+struct node* node_new(const size_t degree, const size_t elem_size) {
const size_t max_items = 2 * degree;
struct node* retval = calloc(1, sizeof(struct node));
@@ -73,9 +73,9 @@ struct node* node_new(const ssize_t degree, const size_t elem_size) {
* allocated.
* returnvalue: `false` if we we're unable to allocate space for the new
* children. */
-bool node_transition(struct node* node, const ssize_t degree) {
- const int max_children = 2 * degree + 1;
- int c;
+bool node_transition(struct node* node, const size_t degree) {
+ const size_t max_children = 2 * degree + 1;
+ size_t c;
if (!node_leaf(node)) {
perror("node_transition was called on an already non-leaf node?");
@@ -102,7 +102,7 @@ void node_free(struct node** node, size_t elem_size, void (*dealloc)(void*)) {
if (*node == NULL) return;
if (!node_leaf((*node))) {
- ssize_t i;
+ size_t i;
for (i = 0; i < (*node)->c; i++) {
node_free(&((*node)->children[i]), elem_size, dealloc);
}
@@ -126,11 +126,11 @@ void node_free(struct node** node, size_t elem_size, void (*dealloc)(void*)) {
* full nodes we encounter on the way down, including the leafs themselves.
* By doing this, we are assured that whenever we split a node, its parent has
* room for the median key. */
-void node_tree_split_child(const ssize_t t, const size_t elem_size,
- struct node* nonfull, ssize_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];
- ssize_t j;
+ size_t j;
/* `z` should be a branching node if `y` is */
if (!node_leaf(y)) {
@@ -192,11 +192,11 @@ void node_tree_split_child(const ssize_t t, const size_t elem_size,
*
* WARNING: THIS FUNCTION ASSUMES THAT `i` IS A VALID INDEX
*/
-void node_child_merge(struct node* x, ssize_t i, const size_t elem_size,
+void node_child_merge(struct node* x, size_t i, const size_t elem_size,
void (*dealloc)(void*)) {
struct node* y = x->children[i];
struct node* z = x->children[i + 1];
- int j = 0;
+ size_t j = 0;
/* append k to y */
memcpy(y->items + (elem_size * y->n++), x->items + (elem_size * i),
@@ -228,7 +228,7 @@ void node_child_merge(struct node* x, ssize_t i, const size_t elem_size,
}
/* ASSUME i < x->c */
-void node_shift_left(struct node* x, ssize_t i, const size_t elem_size) {
+void node_shift_left(struct node* x, size_t i, const size_t elem_size) {
struct node* y = x->children[i];
struct node* z = x->children[i + 1];
byte* x_k = x->items + (elem_size * i);
@@ -243,7 +243,7 @@ void node_shift_left(struct node* x, ssize_t i, const size_t elem_size) {
memmove(z->items, z->items + elem_size, elem_size * (z->n - 1));
if (!node_leaf(z)) {
- ssize_t j;
+ size_t j;
/* append first child of z to y */
y->children[y->c++] = z->children[0];
@@ -257,7 +257,7 @@ void node_shift_left(struct node* x, ssize_t i, const size_t elem_size) {
z->n--;
}
-void node_shift_right(struct node* x, ssize_t i, const size_t elem_size) {
+void node_shift_right(struct node* x, size_t i, const size_t elem_size) {
struct node* y = x->children[i];
struct node* z = x->children[i + 1];
byte* x_k = x->items + (elem_size * i);
@@ -287,12 +287,12 @@ void node_shift_right(struct node* x, ssize_t i, const size_t elem_size) {
}
/* return: Returns the new root, if a split happens */
-void node_insert_nonfull(struct node* root, void* elem, const ssize_t degree,
+void node_insert_nonfull(struct node* root, void* elem, const size_t degree,
const size_t elem_size,
int (*cmp)(const void* a, const void* b)) {
/* TODO check correctness */
- ssize_t i = root->n - 1;
+ size_t i = root->n - 1;
if (node_leaf(root)) {
size_t offset = elem_size * i;
@@ -328,7 +328,7 @@ void node_insert_nonfull(struct node* root, void* elem, const ssize_t degree,
}
/* Returns the new root, if a split occurs */
-struct node* node_insert(struct node* root, void* elem, const ssize_t degree,
+struct node* node_insert(struct node* root, void* elem, const size_t degree,
const size_t elem_size,
int (*cmp)(const void* a, const void* b)) {
@@ -357,7 +357,7 @@ void* node_search(struct node* x, void* key,
const size_t elem_size) {
/* We set to one, since we pre-emptively do a comparison with the assumption
* that there's already one in the items */
- ssize_t i = 0;
+ size_t i = 0;
int last_cmp_res = 0;
while (i < x->n &&
@@ -366,7 +366,7 @@ void* node_search(struct node* x, void* key,
i++;
}
- if ((ssize_t)i < x->n && last_cmp_res == 0) {
+ if (i < x->n && last_cmp_res == 0) {
return (void*)(x->items + (i * elem_size));
} else if (node_leaf(x)) {
return NULL;
@@ -377,11 +377,11 @@ void* node_search(struct node* x, void* key,
}
int node_delete(struct node* x, void* key,
- int (*cmp)(const void* a, const void* b), const ssize_t degree,
+ int (*cmp)(const void* a, const void* b), const size_t degree,
const size_t elem_size, void* (*alloc)(size_t),
void (*dealloc)(void*)) {
/* Determine wether the key is in the node */
- int i = 0; /* Index of `k`, if found */
+ size_t i = 0; /* Index of `k`, if found */
int last_cmp_res = 0;
while (i < x->n &&
@@ -395,7 +395,7 @@ int node_delete(struct node* x, void* key,
if (node_leaf(x)) {
/* 1. k ϵ x && node_leaf(x) */
/* Delete k from x */
- int j = i;
+ size_t j = i;
while (j + 1 < x->n) {
const size_t offset_dst = elem_size * j;
const size_t offset_src = elem_size * (j + 1);
@@ -475,7 +475,7 @@ int node_delete(struct node* x, void* key,
/* if x is a leaf, then it is not in the tree */
struct node* y;
- int ii; /* index of x.c[i] */
+ size_t ii; /* index of x.c[i] */
/* Determine x.c[i] that must contain k */
/* if last cmp < 0, then the child must be in the left child of x.items[i]*/
@@ -589,7 +589,7 @@ int btree_delete(struct btree* btree, void* elem) {
void node_print(struct node* root, const size_t elem_size, const int indent,
void (*print_elem)(const void*)) {
- ssize_t i;
+ size_t i;
int t;
for (t = 0; t < indent - 1; t++) {
@@ -722,8 +722,8 @@ void btree_iter_t_reset(struct btree* tree, struct btree_iter_t** it) {
void* btree_iter(struct btree* tree, struct btree_iter_t* iter) {
register int pos = 0;
- register ssize_t head = 0;
- register ssize_t n = 0;
+ register size_t head = 0;
+ register size_t n = 0;
if (iter->stack[head].node == NULL) return NULL;
@@ -749,7 +749,7 @@ void* btree_iter(struct btree* tree, struct btree_iter_t* iter) {
/* Leafs are a special case, as, if the only node is the root node, we might
* want to exit */
- if (node_leaf(iter->stack[iter->head].node) && pos >= 2 * n) {
+ if (node_leaf(iter->stack[iter->head].node) && (size_t)pos >= 2 * n) {
if (head == 0) return NULL;
/* Pop, if so */
@@ -758,7 +758,7 @@ void* btree_iter(struct btree* tree, struct btree_iter_t* iter) {
}
/* Otherwise, pop while we have reached the end of a node */
- while (pos > 2 * n) {
+ while ((size_t)pos > 2 * n) {
if (head == 0) return NULL;
/* Pop, if so */
@@ -796,5 +796,5 @@ void* btree_iter(struct btree* tree, struct btree_iter_t* iter) {
pos = iter->stack[head].pos;
}
- return iter->stack[head].node->items + tree->elem_size * ((pos - 1) / 2);
+ return iter->stack[head].node->items + tree->elem_size * (((size_t)pos - 1) / 2);
}
generated by cgit v1.3 (git 2.53.0) at 2026-05-23 23:53:26 +0000