11

AIM: Implement various operations on B+ Trees.
PROGRAM:
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// Default order
#define ORDER 3
typedef struct record {
 int value;
} record;
// Node
typedef struct node {
 void **pointers;
 int *keys;
 struct node *parent;
 bool is_leaf;
 int num_keys;
 struct node *next;
} node;
int order = ORDER;
node *queue = NULL;
bool verbose_output = false;
// Enqueue
void enqueue(node *new_node);
// Dequeue
node *dequeue(void);
int height(node *const root);
int pathToLeaves(node *const root, node *child);
void printLeaves(node *const root);
void printTree(node *const root);
void findAndPrint(node *const root, int key, bool verbose);
void findAndPrintRange(node *const root, int range1, int range2, bool verbose);
int findRange(node *const root, int key_start, int key_end, bool verbose,
 int returned_keys[], void *returned_pointers[]);
node *findLeaf(node *const root, int key, bool verbose);
record *find(node *root, int key, bool verbose, node **leaf_out);
int cut(int length);
record *makeRecord(int value);
node *makeNode(void);
node *makeLeaf(void);
int getLeftIndex(node *parent, node *left);
node *insertIntoLeaf(node *leaf, int key, record *pointer);
node *insertIntoLeafAfterSplitting(node *root, node *leaf, int key,
 record *pointer);
node *insertIntoNode(node *root, node *parent,
 int left_index, int key, node *right);
node *insertIntoNodeAfterSplitting(node *root, node *parent,
 int left_index,
 int key, node *right);
node *insertIntoParent(node *root, node *left, int key, node *right);
node *insertIntoNewRoot(node *left, int key, node *right);
node *startNewTree(int key, record *pointer);
node *insert(node *root, int key, int value);
// Enqueue
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;
 }
}
// Dequeue
node *dequeue(void) {
 node *n = queue;
 queue = queue->next;
 n->next = NULL;
 return n;
}
// Print the leaves
void printLeaves(node *const root) {
 if (root == NULL) {
 printf("Empty tree.\n");
 return;
 }
 int i;
 node *c = root;
 while (!c->is_leaf)
 c = c->pointers[0];
 while (true) {
 for (i = 0; i < c->num_keys; i++) {
 if (verbose_output)
 printf("%p ", c->pointers[i]);
 printf("%d ", c->keys[i]);
 }
 if (verbose_output)
 printf("%p ", c->pointers[order - 1]);
 if (c->pointers[order - 1] != NULL) {
 printf(" | ");
 c = c->pointers[order - 1];
 } else
 break;
 }
 printf("\n");
}
// Calculate height
int height(node *const root) {
 int h = 0;
 node *c = root;
 while (!c->is_leaf) {
 c = c->pointers[0];
 h++;
 }
 return h;
}
// Get path to root
int pathToLeaves(node *const root, node *child) {
 int length = 0;
 node *c = child;
 while (c != root) {
 c = c->parent;
 length++;
 }
 return length;
}
// Print the tree
void printTree(node *const 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 = pathToLeaves(root, n);
 if (new_rank != rank) {
 rank = new_rank;
 printf("\n");
 }
 }
 if (verbose_output)
 printf("(%p)", n);
 for (i = 0; i < n->num_keys; i++) {
 if (verbose_output)
 printf("%p ", 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("%p ", n->pointers[order - 1]);
 else
 printf("%p ", n->pointers[n->num_keys]);
 }
 printf("| ");
 }
 printf("\n");
}
// Find the node and print it
void findAndPrint(node *const root, int key, bool verbose) {
 node *leaf = NULL;
 record *r = find(root, key, verbose, NULL);
 if (r == NULL)
 printf("Record not found under key %d.\n", key);
 else
 printf("Record at %p -- key %d, value %d.\n",
 r, key, r->value);
}
// Find and print the range
void findAndPrintRange(node *const 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 = findRange(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: %p Value: %d\n",
 returned_keys[i],
 returned_pointers[i],
 ((record *)
 returned_pointers[i])
 ->value);
 }
}
// Find the range
int findRange(node *const root, int key_start, int key_end, bool verbose,
 int returned_keys[], void *returned_pointers[]) {
 int i, num_found;
 num_found = 0;
 node *n = findLeaf(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;
}
// Find the leaf
node *findLeaf(node *const root, int key, bool verbose) {
 if (root == NULL) {
 if (verbose)
 printf("Empty tree.\n");
 return root;
 }
 int i = 0;
 node *c = root;
 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;
}
record *find(node *root, int key, bool verbose, node **leaf_out) {
 if (root == NULL) {
 if (leaf_out != NULL) {
 *leaf_out = NULL;
 }
 return NULL;
 }
 int i = 0;
 node *leaf = NULL;
 leaf = findLeaf(root, key, verbose);
 for (i = 0; i < leaf->num_keys; i++)
 if (leaf->keys[i] == key)
 break;
 if (leaf_out != NULL) {
 *leaf_out = leaf;
 }
 if (i == leaf->num_keys)
 return NULL;
 else
 return (record *)leaf->pointers[i];
}
int cut(int length) {
 if (length % 2 == 0)
 return length / 2;
 else
 return length / 2 + 1;
}
record *makeRecord(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;
}
node *makeNode(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;
}
node *makeLeaf(void) {
 node *leaf = makeNode();
 leaf->is_leaf = true;
 return leaf;
}
int getLeftIndex(node *parent, node *left) {
 int left_index = 0;
 while (left_index <= parent->num_keys &&
 parent->pointers[left_index] != left)
 left_index++;
 return left_index;
}
node *insertIntoLeaf(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;
}
node *insertIntoLeafAfterSplitting(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 = makeLeaf();
 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 insertIntoParent(root, leaf, new_key, new_leaf);
}
node *insertIntoNode(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;
}
node *insertIntoNodeAfterSplitting(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;
 temp_pointers = malloc((order + 1) * sizeof(node *));
 if (temp_pointers == NULL) {
 exit(EXIT_FAILURE);
 }
 temp_keys = malloc(order * sizeof(int));
 if (temp_keys == NULL) {
 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;
 split = cut(order);
 new_node = makeNode();
 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;
 }
 return insertIntoParent(root, old_node, k_prime, new_node);
}
node *insertIntoParent(node *root, node *left, int key, node *right) {
 int left_index;
 node *parent;
 parent = left->parent;
 if (parent == NULL)
 return insertIntoNewRoot(left, key, right);
 left_index = getLeftIndex(parent, left);
 if (parent->num_keys < order - 1)
 return insertIntoNode(root, parent, left_index, key, right);
 return insertIntoNodeAfterSplitting(root, parent, left_index, key, right);
}
node *insertIntoNewRoot(node *left, int key, node *right) {
 node *root = makeNode();
 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;
}
node *startNewTree(int key, record *pointer) {
 node *root = makeLeaf();
 root->keys[0] = key;
 root->pointers[0] = pointer;
 root->pointers[order - 1] = NULL;
 root->parent = NULL;
 root->num_keys++;
 return root;
}
node *insert(node *root, int key, int value) {
 record *record_pointer = NULL;
 node *leaf = NULL;
 record_pointer = find(root, key, false, NULL);
 if (record_pointer != NULL) {
 record_pointer->value = value;
 return root;
 }
 record_pointer = makeRecord(value);
 if (root == NULL)
 return startNewTree(key, record_pointer);
 leaf = findLeaf(root, key, false);
 if (leaf->num_keys < order - 1) {
 leaf = insertIntoLeaf(leaf, key, record_pointer);
 return root;
 }
 return insertIntoLeafAfterSplitting(root, leaf, key, record_pointer);
}
int main() {
 node *root;
 char instruction;
 root = NULL;
 root = insert(root, 5, 33);
 root = insert(root, 15, 21);
 root = insert(root, 25, 31);
 root = insert(root, 35, 41);
 root = insert(root, 45, 10);
 printTree(root);
 findAndPrint(root, 15, instruction = 'a');
}