Skip to content
Snippets Groups Projects
Select Git revision
  • 5833c8e52df79b15586aa0ff1bd73e006528bb99
  • main default protected
  • update_2024
  • fix_formatting
4 results

ownership.md

Blame
  • 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);
        }
    }