diff options
Diffstat (limited to 'Algorithms/Btree.c')
| -rw-r--r-- | Algorithms/Btree.c | 1219 |
1 files changed, 1219 insertions, 0 deletions
diff --git a/Algorithms/Btree.c b/Algorithms/Btree.c new file mode 100644 index 0000000..643ef2a --- /dev/null +++ b/Algorithms/Btree.c @@ -0,0 +1,1219 @@ +//IMPLEMENTATION OF B+ TREE IN C +#include <stdio.h> +#include <stdlib.h> +#include <stdbool.h> +#ifdef WINDOWS +#define bool char +#define false 0 +#define true 1 +#endif + + +// Default order is 4. +#define DEFAULT_ORDER 4 + +// Minimum order is necessarily 3. We set the maximum +// order arbitrarily. +#define MIN_ORDER 3 +#define MAX_ORDER 20 + + +// TYPES. + +typedef struct record { + int value; +} record; + + +typedef struct node { + void ** pointers; + int * keys; + struct node * parent; + bool is_leaf; + int num_keys; + struct node * next; // Used for queue. +} node; + + + +int order = DEFAULT_ORDER; + +node * queue = NULL; + +bool verbose_output = false; + + +// FUNCTION PROTOTYPES. + + +void message_1( void ); +void message_2( void ); +void message_3( void ); +void enqueue( node * new_node ); +node * dequeue( void ); +int height( node * root ); +int path_to_root( node * root, node * child ); +void print_leaves( node * root ); +void display( node * root ); +void find_and_print(node * root, int key, bool verbose); +void find_and_print_range(node * root, int range1, int range2, bool verbose); +int find_range( node * root, int key_start, int key_end, bool verbose, +int returned_keys[], void * returned_pointers[]); +node * find_leaf( node * root, int key, bool verbose ); +record * find( node * root, int key, bool verbose ); +int cut( int length ); + +// Insertion. + +record * make_record(int value); +node * make_node( void ); +node * make_leaf( void ); +int get_left_index(node * parent, node * left); +node * insert_into_leaf( node * leaf, int key, record * pointer ); +node * insert_into_leaf_after_splitting(node * root, node * leaf, int key, record * pointer); +node * insert_into_node(node * root, node * parent, + int left_index, int key, node * right); +node * insert_into_node_after_splitting(node * root, node * parent, int left_index, + int key, node * right); +node * insert_into_parent(node * root, node * left, int key, node * right); +node * insert_into_new_root(node * left, int key, node * right); +node * start_new_tree(int key, record * pointer); +node * insert( node * root, int key, int value ); + +// Deletion. + +int get_neighbor_index( node * n ); +node * adjust_root(node * root); +node * merge_nodes(node * root, node * n, node * neighbor, int neighbor_index, int k_prime); +node * redistribute_nodes(node * root, node * n, node * neighbor, int neighbor_index, + int k_prime_index, int k_prime); +node * delete_entry( node * root, node * n, int key, void * pointer ); +node * delete( node * root, int key ); + + + + +// FUNCTION DEFINITIONS. + +// Prints the bottom row of keys of the tree (with their respective +// pointers, if the verbose_output flag is set. +void print_leaves( node * root ) { + int i; + node * c = root; + if (root == NULL) { + printf("Empty tree.\n"); + return; + } + while (!c->is_leaf) + c = c->pointers[0]; + while (true) { + for (i = 0; i < c->num_keys; i++) { + if (verbose_output) + printf("%lx ", (unsigned long)c->pointers[i]); + printf("%d ", c->keys[i]); + } + if (verbose_output) + printf("%lx ", (unsigned long)c->pointers[order - 1]); + if (c->pointers[order - 1] != NULL) { + printf(" | "); + c = c->pointers[order - 1]; + } + else + break; + } + printf("\n"); +} + + +//FUNCTION FOR RETURNING HEIGHT OF THE TREE +int height( node * root ) { + int h = 0; + node * c = root; + while (!c->is_leaf) { + c = c->pointers[0]; + h++; + } + return h; +} + + +//FUNCTION RETURNS THE LENGTH IN PATH +int path_to_root( node * root, node * child ) { + int length = 0; + node * c = child; + while (c != root) { + c = c->parent; + length++; + } + return length; +} + +/* Helper function for printing the + * tree out. See display. + */ +void enqueue( node * new_node ) { + node * c; + if (queue == NULL) { + queue = new_node; + queue->next = NULL; + } + else { + c = queue; + while(c->next != NULL) { + c = c->next; + } + c->next = new_node; + new_node->next = NULL; + } +} + + +/* Helper function for printing the + * tree out. See display. + */ +node * dequeue( void ) { + node * n = queue; + queue = queue->next; + n->next = NULL; + return n; +} + +//print the tree in the order of the level of nodes. || symbol is used to seperate the nodes +//if verbose flag is set, the pointer to the keys will also be displayed +void display( node * root ) { + + node * n = NULL; + int i = 0; + int rank = 0; + int new_rank = 0; + + if (root == NULL) { + printf("Empty tree.\n"); + return; + } + queue = NULL; + enqueue(root); + while( queue != NULL ) { + n = dequeue(); + if (n->parent != NULL && n == n->parent->pointers[0]) { + new_rank = path_to_root( root, n ); + if (new_rank != rank) { + rank = new_rank; + printf("\n"); + } + } + if (verbose_output) + printf("(%lx)", (unsigned long)n); + for (i = 0; i < n->num_keys; i++) { + if (verbose_output) + printf("%lx ", (unsigned long)n->pointers[i]); + printf("%d ", n->keys[i]); + } + if (!n->is_leaf) + for (i = 0; i <= n->num_keys; i++) + enqueue(n->pointers[i]); + if (verbose_output) { + if (n->is_leaf) + printf("%lx ", (unsigned long)n->pointers[order - 1]); + else + printf("%lx ", (unsigned long)n->pointers[n->num_keys]); + } + printf("| "); + } + printf("\n"); +} + + +// Finds the record under a given key and prints an appropriate message +void find_and_print(node * root, int key, bool verbose) { + record * r = find(root, key, verbose); + if (r == NULL) + printf("Record not found under key %d.\n", key); + else + printf("Record at %lx -- key %d, value %d.\n", + (unsigned long)r, key, r->value); +} + + +// Finds and prints the keys, pointers, and values within a range +void find_and_print_range( node * root, int key_start, int key_end, + bool verbose ) { + int i; + int array_size = key_end - key_start + 1; + int returned_keys[array_size]; + void * returned_pointers[array_size]; + int num_found = find_range( root, key_start, key_end, verbose, + returned_keys, returned_pointers ); + if (!num_found) + printf("None found.\n"); + else { + for (i = 0; i < num_found; i++) + printf("Key: %d Location: %lx Value: %d\n", + returned_keys[i], + (unsigned long)returned_pointers[i], + ((record *) + returned_pointers[i])->value); + } +} + + +int find_range( node * root, int key_start, int key_end, bool verbose, + int returned_keys[], void * returned_pointers[]) { + int i, num_found; + num_found = 0; + node * n = find_leaf( root, key_start, verbose ); + if (n == NULL) return 0; + for (i = 0; i < n->num_keys && n->keys[i] < key_start; i++) ; + if (i == n->num_keys) return 0; + while (n != NULL) { + for ( ; i < n->num_keys && n->keys[i] <= key_end; i++) { + returned_keys[num_found] = n->keys[i]; + returned_pointers[num_found] = n->pointers[i]; + num_found++; + } + n = n->pointers[order - 1]; + i = 0; + } + return num_found; +} + + +//Displays information about leaf path if verbose flag is set +node * find_leaf( node * root, int key, bool verbose ) { + int i = 0; + node * c = root; + if (c == NULL) { + if (verbose) + printf("Empty tree.\n"); + return c; + } + while (!c->is_leaf) { + if (verbose) { + printf("["); + for (i = 0; i < c->num_keys - 1; i++) + printf("%d ", c->keys[i]); + printf("%d] ", c->keys[i]); + } + i = 0; + while (i < c->num_keys) { + if (key >= c->keys[i]) i++; + else break; + } + if (verbose) + printf("%d ->\n", i); + c = (node *)c->pointers[i]; + } + if (verbose) { + printf("Leaf ["); + for (i = 0; i < c->num_keys - 1; i++) + printf("%d ", c->keys[i]); + printf("%d] ->\n", c->keys[i]); + } + return c; +} + + +// Finds and returns the record to which a key refers. +record * find( node * root, int key, bool verbose ) { + int i = 0; + node * c = find_leaf( root, key, verbose ); + if (c == NULL) return NULL; + for (i = 0; i < c->num_keys; i++) + if (c->keys[i] == key) break; + if (i == c->num_keys) + return NULL; + else + return (record *)c->pointers[i]; +} + +// Finds the appropriate place to split a node that is too big into two. +int cut( int length ) { + if (length % 2 == 0) + return length/2; + else + return length/2 + 1; +} + + +// INSERTION + +// Creates a new record to hold the value to which a key refers. +record * make_record(int value) { + record * new_record = (record *)malloc(sizeof(record)); + if (new_record == NULL) { + perror("Record creation."); + exit(EXIT_FAILURE); + } + else { + new_record->value = value; + } + return new_record; +} + + +//Creates a new node +node * make_node( void ) { + node * new_node; + new_node = malloc(sizeof(node)); + if (new_node == NULL) { + perror("Node creation."); + exit(EXIT_FAILURE); + } + new_node->keys = malloc( (order - 1) * sizeof(int) ); + if (new_node->keys == NULL) { + perror("New node keys array."); + exit(EXIT_FAILURE); + } + new_node->pointers = malloc( order * sizeof(void *) ); + if (new_node->pointers == NULL) { + perror("New node pointers array."); + exit(EXIT_FAILURE); + } + new_node->is_leaf = false; + new_node->num_keys = 0; + new_node->parent = NULL; + new_node->next = NULL; + return new_node; +} + +// Creates a new leaf by creating a node and then adapting it appropriately. +node * make_leaf( void ) { + node * leaf = make_node(); + leaf->is_leaf = true; + return leaf; +} + + +// Helper function used in insert_into_parent to find the index of the parent's pointer to +// the node to the left of the key to be inserted. +int get_left_index(node * parent, node * left) { + + int left_index = 0; + while (left_index <= parent->num_keys && + parent->pointers[left_index] != left) + left_index++; + return left_index; +} + +// Inserts a new pointer to a record and its corresponding key into a leaf. Returns the altered leaf. +node * insert_into_leaf( node * leaf, int key, record * pointer ) { + + int i, insertion_point; + + insertion_point = 0; + while (insertion_point < leaf->num_keys && leaf->keys[insertion_point] < key) + insertion_point++; + + for (i = leaf->num_keys; i > insertion_point; i--) { + leaf->keys[i] = leaf->keys[i - 1]; + leaf->pointers[i] = leaf->pointers[i - 1]; + } + leaf->keys[insertion_point] = key; + leaf->pointers[insertion_point] = pointer; + leaf->num_keys++; + return leaf; +} + + +// Inserts a new key and pointer to a new record into a leaf so as to exceed the tree's order, causing the leaf to be split +// in half. +node * insert_into_leaf_after_splitting(node * root, node * leaf, int key, record * pointer) { + + node * new_leaf; + int * temp_keys; + void ** temp_pointers; + int insertion_index, split, new_key, i, j; + + new_leaf = make_leaf(); + + temp_keys = malloc( order * sizeof(int) ); + if (temp_keys == NULL) { + perror("Temporary keys array."); + exit(EXIT_FAILURE); + } + + temp_pointers = malloc( order * sizeof(void *) ); + if (temp_pointers == NULL) { + perror("Temporary pointers array."); + exit(EXIT_FAILURE); + } + + insertion_index = 0; + while (insertion_index < order - 1 && leaf->keys[insertion_index] < key) + insertion_index++; + + for (i = 0, j = 0; i < leaf->num_keys; i++, j++) { + if (j == insertion_index) j++; + temp_keys[j] = leaf->keys[i]; + temp_pointers[j] = leaf->pointers[i]; + } + + temp_keys[insertion_index] = key; + temp_pointers[insertion_index] = pointer; + + leaf->num_keys = 0; + + split = cut(order - 1); + + for (i = 0; i < split; i++) { + leaf->pointers[i] = temp_pointers[i]; + leaf->keys[i] = temp_keys[i]; + leaf->num_keys++; + } + + for (i = split, j = 0; i < order; i++, j++) { + new_leaf->pointers[j] = temp_pointers[i]; + new_leaf->keys[j] = temp_keys[i]; + new_leaf->num_keys++; + } + + free(temp_pointers); + free(temp_keys); + + new_leaf->pointers[order - 1] = leaf->pointers[order - 1]; + leaf->pointers[order - 1] = new_leaf; + + for (i = leaf->num_keys; i < order - 1; i++) + leaf->pointers[i] = NULL; + for (i = new_leaf->num_keys; i < order - 1; i++) + new_leaf->pointers[i] = NULL; + + new_leaf->parent = leaf->parent; + new_key = new_leaf->keys[0]; + + return insert_into_parent(root, leaf, new_key, new_leaf); +} + + +// Inserts a new key and pointer to a node into a node into which these can fit +// without violating the B+ tree properties. +node * insert_into_node(node * root, node * n, + int left_index, int key, node * right) { + int i; + + for (i = n->num_keys; i > left_index; i--) { + n->pointers[i + 1] = n->pointers[i]; + n->keys[i] = n->keys[i - 1]; + } + n->pointers[left_index + 1] = right; + n->keys[left_index] = key; + n->num_keys++; + return root; +} + + +// Inserts a new key and pointer to a node into a node, causing the node's size to exceed +// the order, and causing the node to split into two. +node * insert_into_node_after_splitting(node * root, node * old_node, int left_index, + int key, node * right) { + + int i, j, split, k_prime; + node * new_node, * child; + int * temp_keys; + node ** temp_pointers; + + /* First create a temporary set of keys and pointers + * to hold everything in order, including + * the new key and pointer, inserted in their + * correct places. + * Then create a new node and copy half of the + * keys and pointers to the old node and + * the other half to the new. + */ + + temp_pointers = malloc( (order + 1) * sizeof(node *) ); + if (temp_pointers == NULL) { + perror("Temporary pointers array for splitting nodes."); + exit(EXIT_FAILURE); + } + temp_keys = malloc( order * sizeof(int) ); + if (temp_keys == NULL) { + perror("Temporary keys array for splitting nodes."); + exit(EXIT_FAILURE); + } + + for (i = 0, j = 0; i < old_node->num_keys + 1; i++, j++) { + if (j == left_index + 1) j++; + temp_pointers[j] = old_node->pointers[i]; + } + + for (i = 0, j = 0; i < old_node->num_keys; i++, j++) { + if (j == left_index) j++; + temp_keys[j] = old_node->keys[i]; + } + + temp_pointers[left_index + 1] = right; + temp_keys[left_index] = key; + + /* Create the new node and copy + * half the keys and pointers to the + * old and half to the new. + */ + split = cut(order); + new_node = make_node(); + old_node->num_keys = 0; + for (i = 0; i < split - 1; i++) { + old_node->pointers[i] = temp_pointers[i]; + old_node->keys[i] = temp_keys[i]; + old_node->num_keys++; + } + old_node->pointers[i] = temp_pointers[i]; + k_prime = temp_keys[split - 1]; + for (++i, j = 0; i < order; i++, j++) { + new_node->pointers[j] = temp_pointers[i]; + new_node->keys[j] = temp_keys[i]; + new_node->num_keys++; + } + new_node->pointers[j] = temp_pointers[i]; + free(temp_pointers); + free(temp_keys); + new_node->parent = old_node->parent; + for (i = 0; i <= new_node->num_keys; i++) { + child = new_node->pointers[i]; + child->parent = new_node; + } + + /* Insert a new key into the parent of the two + * nodes resulting from the split, with + * the old node to the left and the new to the right. + */ + + return insert_into_parent(root, old_node, k_prime, new_node); +} + + + +/* Inserts a new node (leaf or internal node) into the B+ tree. + * Returns the root of the tree after insertion. + */ +node * insert_into_parent(node * root, node * left, int key, node * right) { + + int left_index; + node * parent; + + parent = left->parent; + + /* Case: new root. */ + + if (parent == NULL) + return insert_into_new_root(left, key, right); + + /* Case: leaf or node. (Remainder of + * function body.) + */ + + /* Find the parent's pointer to the left + * node. + */ + + left_index = get_left_index(parent, left); + + + /* Simple case: the new key fits into the node. + */ + + if (parent->num_keys < order - 1) + return insert_into_node(root, parent, left_index, key, right); + + /* Harder case: split a node in order + * to preserve the B+ tree properties. + */ + + return insert_into_node_after_splitting(root, parent, left_index, key, right); +} + + +/* Creates a new root for two subtrees + * and inserts the appropriate key into + * the new root. + */ +node * insert_into_new_root(node * left, int key, node * right) { + + node * root = make_node(); + root->keys[0] = key; + root->pointers[0] = left; + root->pointers[1] = right; + root->num_keys++; + root->parent = NULL; + left->parent = root; + right->parent = root; + return root; +} + + + +/* First insertion: + * start a new tree. + */ +node * start_new_tree(int key, record * pointer) { + + node * root = make_leaf(); + root->keys[0] = key; + root->pointers[0] = pointer; + root->pointers[order - 1] = NULL; + root->parent = NULL; + root->num_keys++; + return root; +} + + + +//Main insertion function +node * insert( node * root, int key, int value ) { + + record * pointer; + node * leaf; + + /* The current implementation ignores + * duplicates. + */ + + if (find(root, key, false) != NULL) + return root; + + /* Create a new record for the + * value. + */ + pointer = make_record(value); + + + /* Case: the tree does not exist yet. + * Start a new tree. + */ + + if (root == NULL) + return start_new_tree(key, pointer); + + + /* Case: the tree already exists. + * (Rest of function body.) + */ + + leaf = find_leaf(root, key, false); + + /* Case: leaf has room for key and pointer. + */ + + if (leaf->num_keys < order - 1) { + leaf = insert_into_leaf(leaf, key, pointer); + return root; + } + + + /* Case: leaf must be split. + */ + + return insert_into_leaf_after_splitting(root, leaf, key, pointer); +} + + + + +// DELETION. + +int get_neighbor_index( node * n ) { + + int i; + + /* Return the index of the key to the left + * of the pointer in the parent pointing + * to n. + * If n is the leftmost child, this means + * return -1. + */ + for (i = 0; i <= n->parent->num_keys; i++) + if (n->parent->pointers[i] == n) + return i - 1; + + // Error state. + printf("Search for nonexistent pointer to node in parent.\n"); + printf("Node: %#lx\n", (unsigned long)n); + exit(EXIT_FAILURE); +} + + +node * remove_entry_from_node(node * n, int key, node * pointer) { + + int i, num_pointers; + + // Remove the key and shift other keys accordingly. + i = 0; + while (n->keys[i] != key) + i++; + for (++i; i < n->num_keys; i++) + n->keys[i - 1] = n->keys[i]; + + // Remove the pointer and shift other pointers accordingly. + // First determine number of pointers. + num_pointers = n->is_leaf ? n->num_keys : n->num_keys + 1; + i = 0; + while (n->pointers[i] != pointer) + i++; + for (++i; i < num_pointers; i++) + n->pointers[i - 1] = n->pointers[i]; + + + // One key fewer. + n->num_keys--; + + // Set the other pointers to NULL for tidiness. + // A leaf uses the last pointer to point to the next leaf. + if (n->is_leaf) + for (i = n->num_keys; i < order - 1; i++) + n->pointers[i] = NULL; + else + for (i = n->num_keys + 1; i < order; i++) + n->pointers[i] = NULL; + + return n; +} + + +node * adjust_root(node * root) { + + node * new_root; + + if (root->num_keys > 0) + return root; + + if (!root->is_leaf) { + new_root = root->pointers[0]; + new_root->parent = NULL; + } + + // If it is a leaf (has no children), + // then the whole tree is empty. + + else + new_root = NULL; + + free(root->keys); + free(root->pointers); + free(root); + + return new_root; +} + + +//merge nodes that became small after deletion +node * merge_nodes(node * root, node * n, node * neighbor, int neighbor_index, int k_prime) { + + int i, j, neighbor_insertion_index, n_start, n_end, new_k_prime; + node * tmp; + bool split; + + /* Swap neighbor with node if node is on the + * extreme left and neighbor is to its right. + */ + + if (neighbor_index == -1) { + tmp = n; + n = neighbor; + neighbor = tmp; + } + + /* Starting point in the neighbor for copying + * keys and pointers from n. + * Recall that n and neighbor have swapped places + * in the special case of n being a leftmost child. + */ + + neighbor_insertion_index = neighbor->num_keys; + + + split = false; + + + if (!n->is_leaf) { + + /* Append k_prime. + */ + + neighbor->keys[neighbor_insertion_index] = k_prime; + neighbor->num_keys++; + + + /* Case (default): there is room for all of n's keys and pointers + * in the neighbor after appending k_prime. + */ + + n_end = n->num_keys; + + /* Case (special): k cannot fit with all the other keys and pointers + * into one merged node. + */ + n_start = 0; // Only used in this special case. + if (n->num_keys + neighbor->num_keys >= order) { + split = true; + n_end = cut(order) - 2; + } + + for (i = neighbor_insertion_index + 1, j = 0; j < n_end; i++, j++) { + neighbor->keys[i] = n->keys[j]; + neighbor->pointers[i] = n->pointers[j]; + neighbor->num_keys++; + n->num_keys--; + n_start++; + } + + /* The number of pointers is always + * one more than the number of keys. + */ + + neighbor->pointers[i] = n->pointers[j]; + + /* If the nodes are still split, remove the first key from + * n. + */ + if (split) { + new_k_prime = n->keys[n_start]; + for (i = 0, j = n_start + 1; i < n->num_keys; i++, j++) { + n->keys[i] = n->keys[j]; + n->pointers[i] = n->pointers[j]; + } + n->pointers[i] = n->pointers[j]; + n->num_keys--; + } + + /* All children must now point up to the same parent. + */ + + for (i = 0; i < neighbor->num_keys + 1; i++) { + tmp = (node *)neighbor->pointers[i]; + tmp->parent = neighbor; + } + } + + /* In a leaf, append the keys and pointers of + * n to the neighbor. + * Set the neighbor's last pointer to point to + * what had been n's right neighbor. + */ + + else { + for (i = neighbor_insertion_index, j = 0; j < n->num_keys; i++, j++) { + neighbor->keys[i] = n->keys[j]; + neighbor->pointers[i] = n->pointers[j]; + neighbor->num_keys++; + } + neighbor->pointers[order - 1] = n->pointers[order - 1]; + } + + if (!split) { + root = delete_entry(root, n->parent, k_prime, n); + free(n->keys); + free(n->pointers); + free(n); + } + else + for (i = 0; i < n->parent->num_keys; i++) + if (n->parent->pointers[i + 1] == n) { + n->parent->keys[i] = new_k_prime; + break; + } + + return root; + +} + + +/* Redistributes entries between two nodes when + * one has become too small after deletion + * but its neighbor is too big to append the + * small node's entries without exceeding the + * maximum + */ +node * redistribute_nodes(node * root, node * n, node * neighbor, int neighbor_index, + int k_prime_index, int k_prime) { + + int i; + node * tmp; + + /* Case: n has a neighbor to the left. + * Pull the neighbor's last key-pointer pair over + * from the neighbor's right end to n's left end. + */ + + if (neighbor_index != -1) { + if (!n->is_leaf) + n->pointers[n->num_keys + 1] = n->pointers[n->num_keys]; + for (i = n->num_keys; i > 0; i--) { + n->keys[i] = n->keys[i - 1]; + n->pointers[i] = n->pointers[i - 1]; + } + if (!n->is_leaf) { + n->pointers[0] = neighbor->pointers[neighbor->num_keys]; + tmp = (node *)n->pointers[0]; + tmp->parent = n; + neighbor->pointers[neighbor->num_keys] = NULL; + n->keys[0] = k_prime; + n->parent->keys[k_prime_index] = neighbor->keys[neighbor->num_keys - 1]; + } + else { + n->pointers[0] = neighbor->pointers[neighbor->num_keys - 1]; + neighbor->pointers[neighbor->num_keys - 1] = NULL; + n->keys[0] = neighbor->keys[neighbor->num_keys - 1]; + n->parent->keys[k_prime_index] = n->keys[0]; + } + } + + /* Case: n is the leftmost child. + * Take a key-pointer pair from the neighbor to the right. + * Move the neighbor's leftmost key-pointer pair + * to n's rightmost position. + */ + + else { + if (n->is_leaf) { + n->keys[n->num_keys] = neighbor->keys[0]; + n->pointers[n->num_keys] = neighbor->pointers[0]; + n->parent->keys[k_prime_index] = neighbor->keys[1]; + } + else { + n->keys[n->num_keys] = k_prime; + n->pointers[n->num_keys + 1] = neighbor->pointers[0]; + tmp = (node *)n->pointers[n->num_keys + 1]; + tmp->parent = n; + n->parent->keys[k_prime_index] = neighbor->keys[0]; + } + for (i = 0; i < neighbor->num_keys; i++) { + neighbor->keys[i] = neighbor->keys[i + 1]; + neighbor->pointers[i] = neighbor->pointers[i + 1]; + } + if (!n->is_leaf) + neighbor->pointers[i] = neighbor->pointers[i + 1]; + } + + /* n now has one more key and one more pointer; + * the neighbor has one fewer of each. + */ + + n->num_keys++; + neighbor->num_keys--; + + return root; +} + + +// Deletes an entry from the B+ tree. + node * delete_entry( node * root, node * n, int key, void * pointer ) { + + int min_keys; + node * neighbor; + int neighbor_index; + int k_prime_index, k_prime; + int capacity; + + // Remove key and pointer from node. + + n = remove_entry_from_node(n, key, pointer); + + /* Case: deletion from the root. + */ + + if (n == root) + return adjust_root(root); + + + // Case: deletion from a node below the root. + + // Determine minimum allowable size of node, to be preserved after deletion. + + + min_keys = n->is_leaf ? cut(order - 1) : cut(order) - 1; + + // Case: node stays at or above minimum. + + if (n->num_keys >= min_keys) + return root; + + /* Find the appropriate neighbor node with which + * to merge. + * Also find the key (k_prime) in the parent + * between the pointer to node n and the pointer + * to the neighbor. + */ + + neighbor_index = get_neighbor_index( n ); + k_prime_index = neighbor_index == -1 ? 0 : neighbor_index; + k_prime = n->parent->keys[k_prime_index]; + neighbor = neighbor_index == -1 ? n->parent->pointers[1] : + n->parent->pointers[neighbor_index]; + + capacity = n->is_leaf ? order : order - 1; + + /* mergence. */ + + if (neighbor->num_keys + n->num_keys < capacity) + return merge_nodes(root, n, neighbor, neighbor_index, k_prime); + + /* Redistribution. */ + + else + return redistribute_nodes(root, n, neighbor, neighbor_index, k_prime_index, k_prime); +} + + + +/* Master deletion function. + */ +node * delete(node * root, int key) { + + node * key_leaf; + record * key_record; + + key_record = find(root, key, false); + key_leaf = find_leaf(root, key, false); + if (key_record != NULL && key_leaf != NULL) { + root = delete_entry(root, key_leaf, key, key_record); + free(key_record); + } + return root; +} + + +void destroy_tree_nodes(node * root) { + int i; + if (root->is_leaf) + for (i = 0; i < root->num_keys; i++) + free(root->pointers[i]); + else + for (i = 0; i < root->num_keys + 1; i++) + destroy_tree_nodes(root->pointers[i]); + free(root->pointers); + free(root->keys); + free(root); +} + + +node * destroy_tree(node * root) { + destroy_tree_nodes(root); + return NULL; +} + +/* First message to the user. + */ +void message_1( void ) { + printf("B+ Tree of Order %d.\n", order); + printf("____________________________________\nTo start with input from a file\nof newline-delimited integers, \n"); + printf("enter as below while executing:\n" + "\tbpt <order> <inputfile> .\n____________________________________\n"); +} + + +/* Second message to the user. + */ +void message_2( void ) { + printf("ENTER THE COMMAND :\n"); + printf("\ti <key> => INSERT <key> (an integer) AS BOTH KEY & VALUE).\n"); + printf("\tf <key> => DISPLAY THE VALUE OF THE KEY.\n"); + printf("\tr <key1> <key2> => PRINT THE KEYS IN THE ENTERED RANGE [<key1>,<key2>]\n"); + printf("\td <key> => DELETE THE KEY & ITS ASSOCIATED VALUE.\n\n"); + printf("\tx => DELETE THE TREE.\n"); + printf("\tp => PRINT THE B+ TREE.\n"); + printf("\tl => PRINT THE KEYS OF LEAVES (bottom row of the tree).\n"); + printf("\tv => TOGGLE OUTPUT OF POINTER ADDRESS(\"verbose\")\n"); + printf("\tq => QUIT.\n"); + printf("\t? => DISPLAY THIS LIST OF COMMANDS.\n"); +} + + +void message_3( void ) { + printf("Message: ./bpt [<order>]\n"); + printf("\twhere %d <= order <= %d .\n", MIN_ORDER, MAX_ORDER); +} + + +int main( int argc, char ** argv ) { + + char * input_file; + FILE * fp; + node * root; + int input, range2; + char instruction; + char license_part; + + root = NULL; + verbose_output = false; + + if (argc > 1) { + order = atoi(argv[1]); + if (order < MIN_ORDER || order > MAX_ORDER) { + fprintf(stderr, "Invalid order: %d .\n\n", order); + message_3(); + exit(EXIT_FAILURE); + } + } + + + message_1(); + message_2(); + + if (argc > 2) { + input_file = argv[2]; + fp = fopen(input_file, "r"); + if (fp == NULL) { + perror("Failure to open input file."); + exit(EXIT_FAILURE); + } + while (!feof(fp)) { + fscanf(fp, "%d\n", &input); + root = insert(root, input, input); + } + fclose(fp); + display(root); + } + + printf("> "); + while (scanf("%c", &instruction) != EOF) { + switch (instruction) { + case 'd': + scanf("%d", &input); + root = delete(root, input); + break; + case 'i': + scanf("%d", &input); + root = insert(root, input, input); + printf("Key %d inserted\n",input); + break; + case 'f': + scanf("%d", &input); + find_and_print(root, input, instruction == 'p'); + break; + case 'r': + scanf("%d %d", &input, &range2); + if (input > range2) { + int tmp = range2; + range2 = input; + input = tmp; + } + find_and_print_range(root, input, range2, instruction == 'p'); + break; + case 'l': + print_leaves(root); + break; + case 'q': + while (getchar() != (int)'\n'); + return EXIT_SUCCESS; + case 'p': + display(root); + break; + case 'v': + verbose_output = !verbose_output; + break; + case 'x': + if (root) + root = destroy_tree(root); + display(root); + break; + default: + message_2(); + break; + } + while (getchar() != (int)'\n'); + printf("> "); + } + printf("\n"); + + return EXIT_SUCCESS; +} |