Select Git revision
ownership.md
Forked from
orestis.malaspin / rust-101
Source project has a limited visibility.
bp_tree.c 7.28 KiB
#include "bp_tree.h"
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct control {
int value;
node *lhs;
node *rhs;
} control;
const control CONST_CONTR = {.value = 0, .lhs = NULL, .rhs = NULL};
node *bp_create_node() {
node *nd = malloc(sizeof(node));
for (int i = 0; i < M + 1; i++)
nd->childs[i] = NULL;
for (int i = 0; i < M; i++)
nd->data[i] = 0;
nd->count = 0;
nd->next = NULL;
return nd;
}
control value_to_insert(int val) {
control c;
c.value = val;
c.lhs = c.rhs = NULL;
return c;
}
bool bp_is_leaf(node *nd) { return nd->childs[0] == NULL; }
void bp_node_shift(node *nd, int index) {
// as there is one more child than values, we must do one more iteration
// outside of the for
nd->childs[M] = nd->childs[M - 1];
for (int i = M - 1; i > index; i--) {
nd->data[i] = nd->data[i - 1];
nd->childs[i + 1] = nd->childs[i];
}
}
node *bp_split(node *nd) {
node *new = bp_create_node();
/*
this weird thing is for the for loop
up to how many loop do we want to do
we need it outside because if the order of the tree is odd, we must do
one more loop
*/
int upto = (int)floor(M / 2);
int index = upto;
// update the new counts
nd->count = (int)floor(nd->count / 2);
new->count = upto;
// as explained, do shit if the order is odd
if (M % 2 == 1) {
upto++;
new->count++;
}
for (int i = 0; i < upto; i++) {
new->data[i] = nd->data[index + i];
nd->data[index + i] = 0;
new->childs[i] = nd->childs[index + i];
nd->childs[index + i] = NULL;
}
return new;
}
control bp_insert_into(node *nd, control val) {
// look for a 0 in the node (it is guarenteed to exist in this version of
// the algorithm)
for (int i = 0; i < M; i++) {
// if we plainly find a 0
if (nd->data[i] == 0) {
nd->data[i] = val.value;
nd->childs[i] = val.lhs;
break;
}
// if we need to insert the value between two values, we need to
// shifter everything greater than our value one case further
if (nd->data[i] > val.value) {
bp_node_shift(nd, i);
nd->data[i] = val.value;
nd->childs[i] = val.rhs;
break;
}
}
nd->count++;
// if the node is now full, we split
if (nd->count == M) {
control v;
node *new = bp_split(nd);
v.lhs = nd;
v.rhs = new;
v.value = new->data[0];
// if the new node we created is a leaf, we must add it to the
// linked list
if (bp_is_leaf(new))
nd->next = new;
return v;
}
return CONST_CONTR;
}
control bp_insert(node *nd, control val) {
control c; // will help us to return the pivot, and the two pointers of the
// childs-to-be
// if we are in a leaf, we found where to insert the value, so let's do it
if (bp_is_leaf(nd))
c = bp_insert_into(nd, val);
else // otherwise let's keep looking
{
for (int i = 0; i < M; i++) {
if (nd->data[i] > val.value || nd->data[i] == 0) {
c = bp_insert(nd->childs[i], val);
break;
}
}
}
// if a split happened
if (c.value != 0) {
return c;
}
return CONST_CONTR;
}
node *bp_split_root(node *root) {
// TEMPORARY FUNC (COPYRIGHT), HARD WRITTEN NEEDS TO BE SOFT
node *new = bp_create_node();
node *rhs = bp_create_node();
int index = (int)floor(M / 2);
int looper = index;
if (M % 2 == 0) {
looper--;
}
for (int i = 0; i <= looper; i++) {
rhs->childs[i] = root->childs[index + i + 1];
root->childs[index + i + 1] = NULL;
}
for (int i = 0; i < looper; i++) {
rhs->data[i] = root->data[index + i + 1];
root->data[index + i + 1] = 0;
}
new->childs[0] = root;
new->childs[1] = rhs;
new->data[0] = root->data[index];
root->data[index] = 0;
new->count = 1;
root->count = index;
rhs->count = index;
if (M % 2 == 0) {
rhs->count--;
}
return new;
}
node *bp_insert_val(node *tree, int val) {
// Parse the val into a control struct then insert it in the tree
control test = bp_insert(tree, value_to_insert(val));
/*
depending on the control item, we act differently
if the control has pointers to node, then we had a split in the direct
childs of the root. We must add the values upringed to the root
*/
if (test.rhs != NULL) {
/*
if the root isn't a leaf, first we add the value into the node
we can't use bp_insert_into() as if we need a split, the way we
do it is slightly different
*/
if (!bp_is_leaf(tree)) {
for (int i = 0; i < M; i++) {
if (tree->data[i] == 0) {
tree->childs[i + 1] = test.rhs;
tree->data[i] = test.value;
tree->count++;
break;
}
}
// If the root is full, we must split it
if (tree->count == M) {
return bp_split_root(tree);
}
// if not, we can simply return the root
return tree;
}
// if, after a split, the root was a leaf, we must create a new
// node which will contain the values from the control
tree = bp_create_node();
tree->childs[0] = test.lhs;
tree->childs[1] = test.rhs;
tree->data[0] = test.value;
tree->count = 1;
}
return tree;
}
void bp_destroy(node *root) {
if (root == NULL)
return;
// free the childs first
if (!bp_is_leaf(root)) {
for (int i = 0; i < M; i++) {
bp_destroy(root->childs[i]);
}
}
// then free the root
free(root);
}
void bp_print_as_ll(node *root) {
// if we reached the end of the list
if (root == NULL) {
printf("NULL\n");
return;
}
// search for the first leaf on the tree
if (!bp_is_leaf(root)) {
return bp_print_as_ll(root->childs[0]);
}
printf("|");
// print every values in the node until hitting 0, then we can get on the
// next node
for (int i = 0; i < M; i++) {
printf(" %d |", root->data[i]);
if (root->data[i + 1] == 0) {
printf(" -> ");
return bp_print_as_ll(root->next);
}
}
}
void bp_print(node *root, int depth) {
// if we are on a leaf, we can print the values directly next to each other
if (bp_is_leaf(root)) {
for (int i = 0; i < depth; i++)
printf(" ");
for (int i = 0; i < M; i++) {
printf(" %d |", root->data[i]);
// if we reach a 0, we have seen every values in the node
if (root->data[i + 1] == 0)
break;
}
return;
}
for (int i = 0; i < M; i++) {
bp_print(root->childs[i], depth + 1);
printf("\n");
for (int i = 0; i < depth; i++)
printf(" ");
printf(" %d |\n", root->data[i]);
if (root->data[i + 1] == 0)
return bp_print(root->childs[i + 1], depth + 1);
}
}