diff options
Diffstat (limited to 'Algorithms')
38 files changed, 7415 insertions, 0 deletions
diff --git a/Algorithms/BPlusTree/btree b/Algorithms/BPlusTree/btree Binary files differnew file mode 100644 index 0000000..7b9ebf2 --- /dev/null +++ b/Algorithms/BPlusTree/btree diff --git a/Algorithms/BPlusTree/btree.c b/Algorithms/BPlusTree/btree.c new file mode 100644 index 0000000..41d96b0 --- /dev/null +++ b/Algorithms/BPlusTree/btree.c @@ -0,0 +1,60 @@ +#include <stdio.h> +#include <stdlib.h> +#include <stdbool.h> + +#include "btree.h" + +struct b_node *ROOT; + +struct b_node* init_node(void) +{ + struct b_node* node; + node = malloc(sizeof(struct b_node)); + + if (!node) + return NULL; + + node->key_count = 0; + node->is_leaf = false; + node->keys = NULL; + node->ptrs = NULL; + node->leaf = NULL; + + return node; +} + +void print_leaf(struct b_node *node) +{ + if (!node->is_leaf) { + printf("Error: trying to print a node instead of a leaf\n"); + return; + } + + /* printf(" Parent node: */ + printf("Data: %d\n", node->leaf->data); + printf("Next sib: %p\n", node->leaf->) + +void print_root(void) +{ + printf("This is the ROOT of the tree \n"); + + if (ROOT->is_leaf) + print_leaf(ROOT); + else + print_node(ROOT); +} + +int main(void) { + + ROOT = init_node(); + if (!ROOT) { + printf("Error to initialize root node\n"); + goto exit0; + } + + printf("ROOT: %p\n", ROOT); + free(ROOT); + +exit0: + return 0; +} diff --git a/Algorithms/BPlusTree/btree.h b/Algorithms/BPlusTree/btree.h new file mode 100644 index 0000000..a045dd4 --- /dev/null +++ b/Algorithms/BPlusTree/btree.h @@ -0,0 +1,23 @@ + +#define ORDER 4 +#define PTRS 5 + +/* + * ptrs: will point to data when the node is a leaf + * will contain the next nodes when just a node + * accessed as an array MAX = PTRS + * sib: will only be valid when the node is a leaf + */ +struct b_node { + int key_count; + bool is_leaf; + int *keys; + void **ptrs; + struct b_leaf *leaf; + struct b_node *sib; +}; + +struct b_leaf { + int data; + struct b_leaf *sib; +}; diff --git a/Algorithms/BST/bst.c b/Algorithms/BST/bst.c new file mode 100644 index 0000000..826d1bd --- /dev/null +++ b/Algorithms/BST/bst.c @@ -0,0 +1,192 @@ +#include <stdio.h> +#include <stdlib.h> + +struct b_node { + int key; + struct b_node *left; + struct b_node *right; +}; + +struct b_node* init_node(int key) +{ + struct b_node *node = malloc(sizeof(struct b_node)); + + if (!node) { + printf("Error initializing the node\n"); + goto out; + } + + node->key = key; + node->left = NULL; + node->right = NULL; + +out: + return node; +} + +struct b_node* search_node(struct b_node *ROOT, int key) +{ +} + +void alloc_root(struct b_node **ROOT) +{ + int key; + struct b_node *new; + + printf("Type the ROOT key: "); + scanf(" %d", &key); + + new = malloc(sizeof(struct b_node)); + new->key = key; + new->left = NULL; + new->right = NULL; + + *ROOT = new; + printf("ROOOOT = %p\n", new); +} + +int insert_node(struct b_node *ROOT) +{ + struct b_node *cur; + struct b_node *new; + int key; + int error = 0; + + if (!ROOT) { + printf("Please initialize root node\n"); + return 0; + } + + printf("Type a new key: "); + scanf(" %d", &key); + + new = init_node(key); + if (!new) + return 1; + + + cur = ROOT; + +// printf("new item key = %d\n", new->key); +// printf("cur = %p ROOT = %p\n", cur, ROOT); + + while (1) { + if (new->key <= cur->key) { + /*go left*/ + if (cur->left == NULL) { + cur->left = new; + break; + } else { + cur = cur->left; + continue; + } + } else { + printf("Current right: %p\n", cur); + /*go right*/ + if (cur->right == NULL) { + cur->right = new; + break; + } else { + cur = cur->right; + continue; + } + } + } + +// printf("KEEP ROOT = %p\n",ROOT); + return 0; + +} + +int delete_node(struct b_node *ROOT, int key) +{ +} + +void print_tree(struct b_node *ROOT) +{ +} + +void print_right(struct b_node *ROOT) +{ + struct b_node *cur; + + if (ROOT == NULL) { + printf ("Tree doesn't exist\n"); + return; + } + + cur = ROOT; + + while (cur) { + printf(" Node: %p - Key : %d\n", cur, cur->key); + cur = cur->right; + } +} + +void print_left(struct b_node *ROOT) +{ + struct b_node *cur; + + if (ROOT == NULL) { + printf ("Tree doesn't exist\n"); + return; + } + + cur = ROOT; + + while (cur) { + printf(" Node: %p - Key : %d\n", cur, cur->key); + cur = cur->left; + } +} + + +void usage() +{ + printf("Usage: \n"); + printf("a: Alloc root node\n"); + printf("i: Insert node\n"); + printf("d: Delete node\n"); + printf("s: Search node\n"); + printf("r: Print the right nodes \n"); + printf("l: Print the left nodes \n"); + return; +} + +int main(void) { + + struct b_node *ROOT = NULL; + + while (1) { + char opt; + + printf(" Option: "); + scanf(" %c", &opt); + + switch(opt) { + case 'a': + alloc_root(&ROOT); + break; + case 'i': + insert_node(ROOT); + break; + case 'l': + print_left(ROOT); + break; + case 'r': + print_right(ROOT); + break; + case 'q': + goto out; + default: + usage(); + break; + } + } + +out: + if (ROOT) + free(ROOT); + + return 0; +} 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; +} diff --git a/Algorithms/bplus-tree/.gitignore b/Algorithms/bplus-tree/.gitignore new file mode 100644 index 0000000..6844bf6 --- /dev/null +++ b/Algorithms/bplus-tree/.gitignore @@ -0,0 +1,2 @@ +build/ +coverage/ diff --git a/Algorithms/bplus-tree/.uncrustifyrc b/Algorithms/bplus-tree/.uncrustifyrc new file mode 100644 index 0000000..a53a884 --- /dev/null +++ b/Algorithms/bplus-tree/.uncrustifyrc @@ -0,0 +1,1485 @@ +# Uncrustify 0.59 + +# +# General options +# + +# The type of line endings +newlines = lf # auto/lf/crlf/cr + +# The original size of tabs in the input +input_tab_size = 4 # number + +# The size of tabs in the output (only used if align_with_tabs=true) +# output_tab_size = 8 # number + +# The ASCII value of the string escape char, usually 92 (\) or 94 (^). (Pawn) +# string_escape_char = 92 # number + +# Alternate string escape char for Pawn. Only works right before the quote char. +# string_escape_char2 = 0 # number + +# Allow interpreting '>=' and '>>=' as part of a template in 'void f(list<list<B>>=val);'. +# If true (default), 'assert(x<0 && y>=3)' will be broken. +# Improvements to template detection may make this option obsolete. +# tok_split_gte = false # false/true + +# Control what to do with the UTF-8 BOM (recommend 'remove') +utf8_bom = remove # ignore/add/remove/force + +# If the file contains bytes with values between 128 and 255, but is not UTF-8, then output as UTF-8 +# utf8_byte = false # false/true + +# Force the output encoding to UTF-8 +utf8_force = true # false/true + +# +# Indenting +# + +# The number of columns to indent per level. +# Usually 2, 3, 4, or 8. +indent_columns = 4 # number + +# The continuation indent. If non-zero, this overrides the indent of '(' and '=' continuation indents. +# For FreeBSD, this is set to 4. Negative value is absolute and not increased for each ( level +# indent_continue = 0 # number + +# How to use tabs when indenting code +# 0=spaces only +# 1=indent with tabs to brace level, align with spaces +# 2=indent and align with tabs, using spaces when not on a tabstop +indent_with_tabs = 0 # number + +# Comments that are not a brace level are indented with tabs on a tabstop. +# Requires indent_with_tabs=2. If false, will use spaces. +# indent_cmt_with_tabs = false # false/true + +# Whether to indent strings broken by '\' so that they line up +indent_align_string = true # false/true + +# The number of spaces to indent multi-line XML strings. +# Requires indent_align_string=True +# indent_xml_string = 0 # number + +# Spaces to indent '{' from level +# indent_brace = 0 # number + +# Whether braces are indented to the body level +# indent_braces = false # false/true + +# Disabled indenting function braces if indent_braces is true +# indent_braces_no_func = false # false/true + +# Disabled indenting class braces if indent_braces is true +# indent_braces_no_class = false # false/true + +# Disabled indenting struct braces if indent_braces is true +# indent_braces_no_struct = false # false/true + +# Indent based on the size of the brace parent, i.e. 'if' => 3 spaces, 'for' => 4 spaces, etc. +# indent_brace_parent = false # false/true + +# Whether the 'namespace' body is indented +indent_namespace = true # false/true + +# The number of spaces to indent a namespace block +indent_namespace_level = 2 # number + +# If the body of the namespace is longer than this number, it won't be indented. +# Requires indent_namespace=true. Default=0 (no limit) +# indent_namespace_limit = 0 # number + +# Whether the 'extern "C"' body is indented +# indent_extern = false # false/true + +# Whether the 'class' body is indented +indent_class = true # false/true + +# Whether to indent the stuff after a leading class colon +indent_class_colon = false # false/true + +# Additional indenting for constructor initializer list +indent_ctor_init = 0 # number + +# False=treat 'else\nif' as 'else if' for indenting purposes +# True=indent the 'if' one level +indent_else_if = true # false/true + +# Amount to indent variable declarations after a open brace. neg=relative, pos=absolute +indent_var_def_blk = 0 # number + +# Indent continued variable declarations instead of aligning. +indent_var_def_cont = false # false/true + +# True: indent continued function call parameters one indent level +# False: align parameters under the open paren +indent_func_call_param = false # false/true + +# Same as indent_func_call_param, but for function defs +indent_func_def_param = false # false/true + +# Same as indent_func_call_param, but for function protos +indent_func_proto_param = false # false/true + +# Same as indent_func_call_param, but for class declarations +indent_func_class_param = false # false/true + +# Same as indent_func_call_param, but for class variable constructors +indent_func_ctor_var_param = false # false/true + +# Same as indent_func_call_param, but for templates +indent_template_param = false # false/true + +# Double the indent for indent_func_xxx_param options +indent_func_param_double = false # false/true + +# Indentation column for standalone 'const' function decl/proto qualifier +indent_func_const = 0 # number + +# Indentation column for standalone 'throw' function decl/proto qualifier +indent_func_throw = 0 # number + +# The number of spaces to indent a continued '->' or '.' +# Usually set to 0, 1, or indent_columns. +indent_member = 0 # number + +# Spaces to indent single line ('//') comments on lines before code +indent_sing_line_comments = 0 # number + +# If set, will indent trailing single line ('//') comments relative +# to the code instead of trying to keep the same absolute column +indent_relative_single_line_comments = false # false/true + +# Spaces to indent 'case' from 'switch' +# Usually 0 or indent_columns. +indent_switch_case = 2 # number + +# Spaces to shift the 'case' line, without affecting any other lines +# Usually 0. +indent_case_shift = 0 # number + +# Spaces to indent '{' from 'case'. +# By default, the brace will appear under the 'c' in case. +# Usually set to 0 or indent_columns. +indent_case_brace = 0 # number + +# Whether to indent comments found in first column +indent_col1_comment = true # false/true + +# How to indent goto labels +# >0 : absolute column where 1 is the leftmost column +# <=0 : subtract from brace indent +indent_label = 1 # number + +# Same as indent_label, but for access specifiers that are followed by a colon +indent_access_spec = 1 # number + +# Indent the code after an access specifier by one level. +# If set, this option forces 'indent_access_spec=0' +indent_access_spec_body = true # false/true + +# If an open paren is followed by a newline, indent the next line so that it lines up after the open paren (not recommended) +indent_paren_nl = false # false/true + +# Controls the indent of a close paren after a newline. +# 0: Indent to body level +# 1: Align under the open paren +# 2: Indent to the brace level +indent_paren_close = 0 # number + +# Controls the indent of a comma when inside a paren.If TRUE, aligns under the open paren +indent_comma_paren = false # false/true + +# Controls the indent of a BOOL operator when inside a paren.If TRUE, aligns under the open paren +indent_bool_paren = false # false/true + +# If 'indent_bool_paren' is true, controls the indent of the first expression. If TRUE, aligns the first expression to the following ones +indent_first_bool_expr = false # false/true + +# If an open square is followed by a newline, indent the next line so that it lines up after the open square (not recommended) +indent_square_nl = false # false/true + +# Don't change the relative indent of ESQL/C 'EXEC SQL' bodies +indent_preserve_sql = false # false/true + +# Align continued statements at the '='. Default=True +# If FALSE or the '=' is followed by a newline, the next line is indent one tab. +indent_align_assign = true # false/true + +# +# Spacing options +# + +# Add or remove space around arithmetic operator '+', '-', '/', '*', etc +sp_arith = force # ignore/add/remove/force + +# Add or remove space around assignment operator '=', '+=', etc +sp_assign = force # ignore/add/remove/force + +# Add or remove space around assignment operator '=' in a prototype +sp_assign_default = remove # ignore/add/remove/force + +# Add or remove space before assignment operator '=', '+=', etc. Overrides sp_assign. +# sp_before_assign = ignore # ignore/add/remove/force + +# Add or remove space after assignment operator '=', '+=', etc. Overrides sp_assign. +# sp_after_assign = ignore # ignore/add/remove/force + +# Add or remove space around assignment '=' in enum +sp_enum_assign = remove # ignore/add/remove/force + +# Add or remove space before assignment '=' in enum. Overrides sp_enum_assign. +# sp_enum_before_assign = ignore # ignore/add/remove/force + +# Add or remove space after assignment '=' in enum. Overrides sp_enum_assign. +# sp_enum_after_assign = ignore # ignore/add/remove/force + +# Add or remove space around preprocessor '##' concatenation operator. Default=Add +sp_pp_concat = force # ignore/add/remove/force + +# Add or remove space after preprocessor '#' stringify operator. Also affects the '#@' charizing operator. Default=Add +sp_pp_stringify = force # ignore/add/remove/force + +# Add or remove space around boolean operators '&&' and '||' +sp_bool = force # ignore/add/remove/force + +# Add or remove space around compare operator '<', '>', '==', etc +sp_compare = force # ignore/add/remove/force + +# Add or remove space inside '(' and ')' +sp_inside_paren = remove # ignore/add/remove/force + +# Add or remove space between nested parens +sp_paren_paren = remove # ignore/add/remove/force + +# Whether to balance spaces inside nested parens +# sp_balance_nested_parens = false # false/true + +# Add or remove space between ')' and '{' +sp_paren_brace = force # ignore/add/remove/force + +# Add or remove space before pointer star '*' +sp_before_ptr_star = remove # ignore/add/remove/force + +# Add or remove space before pointer star '*' that isn't followed by a variable name +# If set to 'ignore', sp_before_ptr_star is used instead. +# sp_before_unnamed_ptr_star = ignore # ignore/add/remove/force + +# Add or remove space between pointer stars '*' +sp_between_ptr_star = remove # ignore/add/remove/force + +# Add or remove space after pointer star '*', if followed by a word. +sp_after_ptr_star = force # ignore/add/remove/force + +# Add or remove space after a pointer star '*', if followed by a func proto/def. +sp_after_ptr_star_func = force # ignore/add/remove/force + +# Add or remove space before a pointer star '*', if followed by a func proto/def. +sp_before_ptr_star_func = remove # ignore/add/remove/force + +# Add or remove space before a reference sign '&' +sp_before_byref = remove # ignore/add/remove/force + +# Add or remove space before a reference sign '&' that isn't followed by a variable name +# If set to 'ignore', sp_before_byref is used instead. +# sp_before_unnamed_byref = ignore # ignore/add/remove/force + +# Add or remove space after reference sign '&', if followed by a word. +sp_after_byref = force # ignore/add/remove/force + +# Add or remove space after a reference sign '&', if followed by a func proto/def. +sp_after_byref_func = force # ignore/add/remove/force + +# Add or remove space before a reference sign '&', if followed by a func proto/def. +sp_before_byref_func = remove # ignore/add/remove/force + +# Add or remove space between type and word. Default=Force +# sp_after_type = force # ignore/add/remove/force + +# Add or remove space before the paren in the D constructs 'template Foo(' and 'class Foo('. +sp_before_template_paren = remove # ignore/add/remove/force + +# Add or remove space in 'template <' vs 'template<'. +# If set to ignore, sp_before_angle is used. +# sp_template_angle = ignore # ignore/add/remove/force + +# Add or remove space before '<>' +sp_before_angle = remove # ignore/add/remove/force + +# Add or remove space inside '<' and '>' +sp_inside_angle = force # ignore/add/remove/force + +# Add or remove space after '<>' +sp_after_angle = force # ignore/add/remove/force + +# Add or remove space between '<>' and '(' as found in 'new List<byte>();' +sp_angle_paren = remove # ignore/add/remove/force + +# Add or remove space between '<>' and a word as in 'List<byte> m;' +sp_angle_word = force # ignore/add/remove/force + +# Add or remove space between '>' and '>' in '>>' (template stuff C++/C# only). Default=Add +sp_angle_shift = force # ignore/add/remove/force + +# Add or remove space before '(' of 'if', 'for', 'switch', and 'while' +sp_before_sparen = force # ignore/add/remove/force + +# Add or remove space inside if-condition '(' and ')' +sp_inside_sparen = remove # ignore/add/remove/force + +# Add or remove space before if-condition ')'. Overrides sp_inside_sparen. +# sp_inside_sparen_close = ignore # ignore/add/remove/force + +# Add or remove space after ')' of 'if', 'for', 'switch', and 'while' +sp_after_sparen = force # ignore/add/remove/force + +# Add or remove space between ')' and '{' of 'if', 'for', 'switch', and 'while' +sp_sparen_brace = force # ignore/add/remove/force + +# Add or remove space between 'invariant' and '(' in the D language. +sp_invariant_paren = force # ignore/add/remove/force + +# Add or remove space after the ')' in 'invariant (C) c' in the D language. +sp_after_invariant_paren = force # ignore/add/remove/force + +# Add or remove space before empty statement ';' on 'if', 'for' and 'while' +sp_special_semi = remove # ignore/add/remove/force + +# Add or remove space before ';'. Default=Remove +# sp_before_semi = remove # ignore/add/remove/force + +# Add or remove space before ';' in non-empty 'for' statements +sp_before_semi_for = remove # ignore/add/remove/force + +# Add or remove space before a semicolon of an empty part of a for statement. +sp_before_semi_for_empty = remove # ignore/add/remove/force + +# Add or remove space after ';', except when followed by a comment. Default=Add +sp_after_semi = force # ignore/add/remove/force + +# Add or remove space after ';' in non-empty 'for' statements. Default=Force +# sp_after_semi_for = force # ignore/add/remove/force + +# Add or remove space after the final semicolon of an empty part of a for statement: for ( ; ; <here> ). +sp_after_semi_for_empty = remove # ignore/add/remove/force + +# Add or remove space before '[' (except '[]') +sp_before_square = remove # ignore/add/remove/force + +# Add or remove space before '[]' +sp_before_squares = remove # ignore/add/remove/force + +# Add or remove space inside a non-empty '[' and ']' +sp_inside_square = remove # ignore/add/remove/force + +# Add or remove space after ',' +sp_after_comma = force # ignore/add/remove/force + +# Add or remove space before ',' +# sp_before_comma = remove # ignore/add/remove/force + +# Add or remove space between an open paren and comma: '(,' vs '( ,' +sp_paren_comma = remove # ignore/add/remove/force + +# Add or remove space before the variadic '...' when preceded by a non-punctuator +sp_before_ellipsis = force # ignore/add/remove/force + +# Add or remove space after class ':' +sp_after_class_colon = force # ignore/add/remove/force + +# Add or remove space before class ':' +sp_before_class_colon = force # ignore/add/remove/force + +# Add or remove space before case ':'. Default=Remove +# sp_before_case_colon = remove # ignore/add/remove/force + +# Add or remove space between 'operator' and operator sign +sp_after_operator = remove # ignore/add/remove/force + +# Add or remove space between the operator symbol and the open paren, as in 'operator ++(' +sp_after_operator_sym = remove # ignore/add/remove/force + +# Add or remove space after C/D cast, i.e. 'cast(int)a' vs 'cast(int) a' or '(int)a' vs '(int) a' +sp_after_cast = force # ignore/add/remove/force + +# Add or remove spaces inside cast parens +sp_inside_paren_cast = remove # ignore/add/remove/force + +# Add or remove space between the type and open paren in a C++ cast, i.e. 'int(exp)' vs 'int (exp)' +sp_cpp_cast_paren = remove # ignore/add/remove/force + +# Add or remove space between 'sizeof' and '(' +sp_sizeof_paren = remove # ignore/add/remove/force + +# Add or remove space after the tag keyword (Pawn) +sp_after_tag = force # ignore/add/remove/force + +# Add or remove space inside enum '{' and '}' +sp_inside_braces_enum = force # ignore/add/remove/force + +# Add or remove space inside struct/union '{' and '}' +sp_inside_braces_struct = force # ignore/add/remove/force + +# Add or remove space inside '{' and '}' +sp_inside_braces = force # ignore/add/remove/force + +# Add or remove space inside '{}' +sp_inside_braces_empty = remove # ignore/add/remove/force + +# Add or remove space between return type and function name +# A minimum of 1 is forced except for pointer return types. +sp_type_func = force # ignore/add/remove/force + +# Add or remove space between function name and '(' on function declaration +sp_func_proto_paren = remove # ignore/add/remove/force + +# Add or remove space between function name and '(' on function definition +sp_func_def_paren = remove # ignore/add/remove/force + +# Add or remove space inside empty function '()' +sp_inside_fparens = remove # ignore/add/remove/force + +# Add or remove space inside function '(' and ')' +sp_inside_fparen = remove # ignore/add/remove/force + +# Add or remove space between ']' and '(' when part of a function call. +sp_square_fparen = remove # ignore/add/remove/force + +# Add or remove space between ')' and '{' of function +sp_fparen_brace = force # ignore/add/remove/force + +# Add or remove space between function name and '(' on function calls +sp_func_call_paren = remove # ignore/add/remove/force + +# Add or remove space between function name and '()' on function calls without parameters. +# If set to 'ignore' (the default), sp_func_call_paren is used. +# sp_func_call_paren_empty = ignore # ignore/add/remove/force + +# Add or remove space between the user function name and '(' on function calls +# You need to set a keyword to be a user function, like this: 'set func_call_user _' in the config file. +# sp_func_call_user_paren = ignore # ignore/add/remove/force + +# Add or remove space between a constructor/destructor and the open paren +sp_func_class_paren = remove # ignore/add/remove/force + +# Add or remove space between 'return' and '(' +sp_return_paren = force # ignore/add/remove/force + +# Add or remove space between '__attribute__' and '(' +sp_attribute_paren = remove # ignore/add/remove/force + +# Add or remove space between 'defined' and '(' in '#if defined (FOO)' +sp_defined_paren = remove # ignore/add/remove/force + +# Add or remove space between 'throw' and '(' in 'throw (something)' +sp_throw_paren = force # ignore/add/remove/force + +# Add or remove space between 'catch' and '(' in 'catch (something) { }' +# If set to ignore, sp_before_sparen is used. +# sp_catch_paren = ignore # ignore/add/remove/force + +# Add or remove space between 'version' and '(' in 'version (something) { }' (D language) +# If set to ignore, sp_before_sparen is used. +# sp_version_paren = ignore # ignore/add/remove/force + +# Add or remove space between 'scope' and '(' in 'scope (something) { }' (D language) +# If set to ignore, sp_before_sparen is used. +# sp_scope_paren = ignore # ignore/add/remove/force + +# Add or remove space between macro and value +sp_macro = force # ignore/add/remove/force + +# Add or remove space between macro function ')' and value +sp_macro_func = force # ignore/add/remove/force + +# Add or remove space between 'else' and '{' if on the same line +sp_else_brace = force # ignore/add/remove/force + +# Add or remove space between '}' and 'else' if on the same line +sp_brace_else = force # ignore/add/remove/force + +# Add or remove space between '}' and the name of a typedef on the same line +sp_brace_typedef = force # ignore/add/remove/force + +# Add or remove space between 'catch' and '{' if on the same line +sp_catch_brace = force # ignore/add/remove/force + +# Add or remove space between '}' and 'catch' if on the same line +sp_brace_catch = force # ignore/add/remove/force + +# Add or remove space between 'finally' and '{' if on the same line +sp_finally_brace = force # ignore/add/remove/force + +# Add or remove space between '}' and 'finally' if on the same line +sp_brace_finally = force # ignore/add/remove/force + +# Add or remove space between 'try' and '{' if on the same line +sp_try_brace = force # ignore/add/remove/force + +# Add or remove space between get/set and '{' if on the same line +sp_getset_brace = force # ignore/add/remove/force + +# Add or remove space before the '::' operator +sp_before_dc = remove # ignore/add/remove/force + +# Add or remove space after the '::' operator +sp_after_dc = remove # ignore/add/remove/force + +# Add or remove around the D named array initializer ':' operator +sp_d_array_colon = remove # ignore/add/remove/force + +# Add or remove space after the '!' (not) operator. Default=Remove +# sp_not = remove # ignore/add/remove/force + +# Add or remove space after the '~' (invert) operator. Default=Remove +# sp_inv = remove # ignore/add/remove/force + +# Add or remove space after the '&' (address-of) operator. Default=Remove +# This does not affect the spacing after a '&' that is part of a type. +# sp_addr = remove # ignore/add/remove/force + +# Add or remove space around the '.' or '->' operators. Default=Remove +# sp_member = remove # ignore/add/remove/force + +# Add or remove space after the '*' (dereference) operator. Default=Remove +# This does not affect the spacing after a '*' that is part of a type. +# sp_deref = remove # ignore/add/remove/force + +# Add or remove space after '+' or '-', as in 'x = -5' or 'y = +7'. Default=Remove +# sp_sign = remove # ignore/add/remove/force + +# Add or remove space before or after '++' and '--', as in '(--x)' or 'y++;'. Default=Remove +# sp_incdec = remove # ignore/add/remove/force + +# Add or remove space before a backslash-newline at the end of a line. Default=Add +# sp_before_nl_cont = add # ignore/add/remove/force + +# Add or remove space after the scope '+' or '-', as in '-(void) foo;' or '+(int) bar;' +sp_after_oc_scope = remove # ignore/add/remove/force + +# Add or remove space after the colon in message specs +# '-(int) f:(int) x;' vs '-(int) f: (int) x;' +sp_after_oc_colon = force # ignore/add/remove/force + +# Add or remove space before the colon in message specs +# '-(int) f: (int) x;' vs '-(int) f : (int) x;' +sp_before_oc_colon = force # ignore/add/remove/force + +# Add or remove space after the colon in message specs +# '[object setValue:1];' vs '[object setValue: 1];' +sp_after_send_oc_colon = force # ignore/add/remove/force + +# Add or remove space before the colon in message specs +# '[object setValue:1];' vs '[object setValue :1];' +sp_before_send_oc_colon = remove # ignore/add/remove/force + +# Add or remove space after the (type) in message specs +# '-(int)f: (int) x;' vs '-(int)f: (int)x;' +sp_after_oc_type = remove # ignore/add/remove/force + +# Add or remove space after the first (type) in message specs +# '-(int) f:(int)x;' vs '-(int)f:(int)x;' +sp_after_oc_return_type = remove # ignore/add/remove/force + +# Add or remove space between '@selector' and '(' +# '@selector(msgName)' vs '@selector (msgName)' +# Also applies to @protocol() constructs +sp_after_oc_at_sel = remove # ignore/add/remove/force + +# Add or remove space between '@selector(x)' and the following word +# '@selector(foo) a:' vs '@selector(foo)a:' +sp_after_oc_at_sel_parens = force # ignore/add/remove/force + +# Add or remove space inside '@selector' parens +# '@selector(foo)' vs '@selector( foo )' +# Also applies to @protocol() constructs +sp_inside_oc_at_sel_parens = remove # ignore/add/remove/force + +# Add or remove space before a block pointer caret +# '^int (int arg){...}' vs. ' ^int (int arg){...}' +sp_before_oc_block_caret = remove # ignore/add/remove/force + +# Add or remove space after a block pointer caret +# '^int (int arg){...}' vs. '^ int (int arg){...}' +sp_after_oc_block_caret = remove # ignore/add/remove/force + +# Add or remove space around the ':' in 'b ? t : f' +sp_cond_colon = force # ignore/add/remove/force + +# Add or remove space around the '?' in 'b ? t : f' +sp_cond_question = force # ignore/add/remove/force + +# Fix the spacing between 'case' and the label. Only 'ignore' and 'force' make sense here. +sp_case_label = force # ignore/add/remove/force + +# Control the space around the D '..' operator. +sp_range = remove # ignore/add/remove/force + +# Control the space after the opening of a C++ comment '// A' vs '//A' +sp_cmt_cpp_start = force # ignore/add/remove/force + +# Controls the spaces between #else or #endif and a trailing comment +sp_endif_cmt = force # ignore/add/remove/force + +# Controls the spaces after 'new', 'delete', and 'delete[]' +sp_after_new = force # ignore/add/remove/force + +# Controls the spaces before a trailing or embedded comment +sp_before_tr_emb_cmt = force # ignore/add/remove/force + +# Number of spaces before a trailing or embedded comment +# sp_num_before_tr_emb_cmt = 0 # number + +# +# Code alignment (not left column spaces/tabs) +# + +# Whether to keep non-indenting tabs +# align_keep_tabs = false # false/true + +# Whether to use tabs for aligning +# align_with_tabs = false # false/true + +# Whether to bump out to the next tab when aligning +# align_on_tabstop = false # false/true + +# Whether to left-align numbers +align_number_left = false # false/true + +# Align variable definitions in prototypes and functions +align_func_params = true # false/true + +# Align parameters in single-line functions that have the same name. +# The function names must already be aligned with each other. +align_same_func_call_params = false # false/true + +# The span for aligning variable definitions (0=don't align) +align_var_def_span = 1 # number + +# How to align the star in variable definitions. +# 0=Part of the type 'void * foo;' +# 1=Part of the variable 'void *foo;' +# 2=Dangling 'void *foo;' +# align_var_def_star_style = 0 # number + +# How to align the '&' in variable definitions. +# 0=Part of the type +# 1=Part of the variable +# 2=Dangling +# align_var_def_amp_style = 0 # number + +# The threshold for aligning variable definitions (0=no limit) +align_var_def_thresh = 0 # number + +# The gap for aligning variable definitions +align_var_def_gap = 0 # number + +# Whether to align the colon in struct bit fields +align_var_def_colon = true # false/true + +# Whether to align any attribute after the variable name +align_var_def_attribute = true # false/true + +# Whether to align inline struct/enum/union variable definitions +align_var_def_inline = true # false/true + +# The span for aligning on '=' in assignments (0=don't align) +align_assign_span = 1 # number + +# The threshold for aligning on '=' in assignments (0=no limit) +align_assign_thresh = 0 # number + +# The span for aligning on '=' in enums (0=don't align) +align_enum_equ_span = 1 # number + +# The threshold for aligning on '=' in enums (0=no limit) +align_enum_equ_thresh = 0 # number + +# The span for aligning struct/union (0=don't align) +align_var_struct_span = 1 # number + +# The threshold for aligning struct/union member definitions (0=no limit) +align_var_struct_thresh = 0 # number + +# The gap for aligning struct/union member definitions +align_var_struct_gap = 0 # number + +# The span for aligning struct initializer values (0=don't align) +align_struct_init_span = 1 # number + +# The minimum space between the type and the synonym of a typedef +align_typedef_gap = 0 # number + +# The span for aligning single-line typedefs (0=don't align) +align_typedef_span = 1 # number + +# How to align typedef'd functions with other typedefs +# 0: Don't mix them at all +# 1: align the open paren with the types +# 2: align the function type name with the other type names +align_typedef_func = 1 # number + +# Controls the positioning of the '*' in typedefs. Just try it. +# 0: Align on typedef type, ignore '*' +# 1: The '*' is part of type name: typedef int *pint; +# 2: The '*' is part of the type, but dangling: typedef int *pint; +align_typedef_star_style = 0 # number + +# Controls the positioning of the '&' in typedefs. Just try it. +# 0: Align on typedef type, ignore '&' +# 1: The '&' is part of type name: typedef int &pint; +# 2: The '&' is part of the type, but dangling: typedef int &pint; +align_typedef_amp_style = 0 # number + +# The span for aligning comments that end lines (0=don't align) +align_right_cmt_span = 1 # number + +# If aligning comments, mix with comments after '}' and #endif with less than 3 spaces before the comment +align_right_cmt_mix = false # false/true + +# If a trailing comment is more than this number of columns away from the text it follows, +# it will qualify for being aligned. This has to be > 0 to do anything. +align_right_cmt_gap = 0 # number + +# Align trailing comment at or beyond column N; 'pulls in' comments as a bonus side effect (0=ignore) +align_right_cmt_at_col = 1 # number + +# The span for aligning function prototypes (0=don't align) +align_func_proto_span = 1 # number + +# Minimum gap between the return type and the function name. +align_func_proto_gap = 0 # number + +# Align function protos on the 'operator' keyword instead of what follows +align_on_operator = false # false/true + +# Whether to mix aligning prototype and variable declarations. +# If true, align_var_def_XXX options are used instead of align_func_proto_XXX options. +align_mix_var_proto = false # false/true + +# Align single-line functions with function prototypes, uses align_func_proto_span +align_single_line_func = false # false/true + +# Aligning the open brace of single-line functions. +# Requires align_single_line_func=true, uses align_func_proto_span +align_single_line_brace = false # false/true + +# Gap for align_single_line_brace. +align_single_line_brace_gap = 0 # number + +# The span for aligning ObjC msg spec (0=don't align) +align_oc_msg_spec_span = 0 # number + +# Whether to align macros wrapped with a backslash and a newline. +# This will not work right if the macro contains a multi-line comment. +align_nl_cont = true # false/true + +# # Align macro functions and variables together +align_pp_define_together = true # false/true + +# The minimum space between label and value of a preprocessor define +align_pp_define_gap = 1 # number + +# The span for aligning on '#define' bodies (0=don't align) +align_pp_define_span = 1 # number + +# Align lines that start with '<<' with previous '<<'. Default=true +# align_left_shift = true # false/true + +# Span for aligning parameters in an Obj-C message call on the ':' (0=don't align) +# align_oc_msg_colon_span = 0 # number + +# Aligning parameters in an Obj-C '+' or '-' declaration on the ':' +# align_oc_decl_colon = false # false/true + +# +# Newline adding and removing options +# + +# Whether to collapse empty blocks between '{' and '}' +nl_collapse_empty_body = true # false/true + +# Don't split one-line braced assignments - 'foo_t f = { 1, 2 };' +nl_assign_leave_one_liners = true # false/true + +# Don't split one-line braced statements inside a class xx { } body +nl_class_leave_one_liners = true # false/true + +# Don't split one-line enums: 'enum foo { BAR = 15 };' +nl_enum_leave_one_liners = true # false/true + +# Don't split one-line get or set functions +nl_getset_leave_one_liners = true # false/true + +# Don't split one-line function definitions - 'int foo() { return 0; }' +nl_func_leave_one_liners = true # false/true + +# Don't split one-line if/else statements - 'if(a) b++;' +# nl_if_leave_one_liners = false # false/true + +# Add or remove newlines at the start of the file +nl_start_of_file = remove # ignore/add/remove/force + +# The number of newlines at the start of the file (only used if nl_start_of_file is 'add' or 'force' +# nl_start_of_file_min = 0 # number + +# Add or remove newline at the end of the file +nl_end_of_file = force # ignore/add/remove/force + +# The number of newlines at the end of the file (only used if nl_end_of_file is 'add' or 'force') +nl_end_of_file_min = 1 # number + +# Add or remove newline between '=' and '{' +nl_assign_brace = remove # ignore/add/remove/force + +# Add or remove newline between '=' and '[' (D only) +nl_assign_square = remove # ignore/add/remove/force + +# Add or remove newline after '= [' (D only). Will also affect the newline before the ']' +# nl_after_square_assign = ignore # ignore/add/remove/force + +# The number of blank lines after a block of variable definitions at the top of a function body +# 0 = No change (default) +nl_func_var_def_blk = 0 # number + +# The number of newlines before a block of typedefs +# 0 = No change (default) +nl_typedef_blk_start = 1 # number + +# The number of newlines after a block of typedefs +# 0 = No change (default) +nl_typedef_blk_end = 2 # number + +# The maximum consecutive newlines within a block of typedefs +# 0 = No change (default) +nl_typedef_blk_in = 2 # number + +# The number of newlines before a block of variable definitions not at the top of a function body +# 0 = No change (default) +# nl_var_def_blk_start = 0 # number + +# The number of newlines after a block of variable definitions not at the top of a function body +# 0 = No change (default) +# nl_var_def_blk_end = 0 # number + +# The maximum consecutive newlines within a block of variable definitions +# 0 = No change (default) +# nl_var_def_blk_in = 0 # number + +# Add or remove newline between a function call's ')' and '{', as in: +# list_for_each(item, &list) { } +nl_fcall_brace = force # ignore/add/remove/force + +# Add or remove newline between 'enum' and '{' +nl_enum_brace = force # ignore/add/remove/force + +# Add or remove newline between 'struct and '{' +nl_struct_brace = force # ignore/add/remove/force + +# Add or remove newline between 'union' and '{' +nl_union_brace = force # ignore/add/remove/force + +# Add or remove newline between 'if' and '{' +nl_if_brace = force # ignore/add/remove/force + +# Add or remove newline between '}' and 'else' +nl_brace_else = force # ignore/add/remove/force + +# Add or remove newline between 'else if' and '{' +# If set to ignore, nl_if_brace is used instead +nl_elseif_brace = force # ignore/add/remove/force + +# Add or remove newline between 'else' and '{' +nl_else_brace = force # ignore/add/remove/force + +# Add or remove newline between 'else' and 'if' +nl_else_if = remove # ignore/add/remove/force + +# Add or remove newline between '}' and 'finally' +nl_brace_finally = force # ignore/add/remove/force + +# Add or remove newline between 'finally' and '{' +nl_finally_brace = force # ignore/add/remove/force + +# Add or remove newline between 'try' and '{' +nl_try_brace = force # ignore/add/remove/force + +# Add or remove newline between get/set and '{' +nl_getset_brace = force # ignore/add/remove/force + +# Add or remove newline between 'for' and '{' +nl_for_brace = force # ignore/add/remove/force + +# Add or remove newline between 'catch' and '{' +nl_catch_brace = force # ignore/add/remove/force + +# Add or remove newline between '}' and 'catch' +nl_brace_catch = force # ignore/add/remove/force + +# Add or remove newline between 'while' and '{' +nl_while_brace = force # ignore/add/remove/force + +# Add or remove newline between 'scope (x)' and '{' (D) +nl_scope_brace = force # ignore/add/remove/force + +# Add or remove newline between 'unittest' and '{' (D) +nl_unittest_brace = force # ignore/add/remove/force + +# Add or remove newline between 'version (x)' and '{' (D) +nl_version_brace = force # ignore/add/remove/force + +# Add or remove newline between 'using' and '{' +nl_using_brace = force # ignore/add/remove/force + +# Add or remove newline between two open or close braces. +# Due to general newline/brace handling, REMOVE may not work. +nl_brace_brace = force # ignore/add/remove/force + +# Add or remove newline between 'do' and '{' +nl_do_brace = force # ignore/add/remove/force + +# Add or remove newline between '}' and 'while' of 'do' statement +nl_brace_while = force # ignore/add/remove/force + +# Add or remove newline between 'switch' and '{' +nl_switch_brace = force # ignore/add/remove/force + +# Add a newline between ')' and '{' if the ')' is on a different line than the if/for/etc. +# Overrides nl_for_brace, nl_if_brace, nl_switch_brace, nl_while_switch, and nl_catch_brace. +# nl_multi_line_cond = false # false/true + +# Force a newline in a define after the macro name for multi-line defines. +nl_multi_line_define = true # false/true + +# Whether to put a newline before 'case' statement +nl_before_case = true # false/true + +# Add or remove newline between ')' and 'throw' +nl_before_throw = force # ignore/add/remove/force + +# Whether to put a newline after 'case' statement +nl_after_case = true # false/true + +# Add or remove a newline between a case ':' and '{'. Overrides nl_after_case. +nl_case_colon_brace = remove # ignore/add/remove/force + +# Newline between namespace and { +nl_namespace_brace = force # ignore/add/remove/force + +# Add or remove newline between 'template<>' and whatever follows. +# nl_template_class = ignore # ignore/add/remove/force + +# Add or remove newline between 'class' and '{' +nl_class_brace = force # ignore/add/remove/force + +# Add or remove newline after each ',' in the constructor member initialization +nl_class_init_args = force # ignore/add/remove/force + +# Add or remove newline between return type and function name in a function definition +nl_func_type_name = remove # ignore/add/remove/force + +# Add or remove newline between return type and function name inside a class {} +# Uses nl_func_type_name or nl_func_proto_type_name if set to ignore. +nl_func_type_name_class = remove # ignore/add/remove/force + +# Add or remove newline between function scope and name in a definition +# Controls the newline after '::' in 'void A::f() { }' +nl_func_scope_name = remove # ignore/add/remove/force + +# Add or remove newline between return type and function name in a prototype +nl_func_proto_type_name = remove # ignore/add/remove/force + +# Add or remove newline between a function name and the opening '(' +nl_func_paren = remove # ignore/add/remove/force + +# Add or remove newline between a function name and the opening '(' in the definition +nl_func_def_paren = remove # ignore/add/remove/force + +# Add or remove newline after '(' in a function declaration +nl_func_decl_start = remove # ignore/add/remove/force + +# Add or remove newline after '(' in a function definition +nl_func_def_start = remove # ignore/add/remove/force + +# Overrides nl_func_decl_start when there is only one parameter. +# nl_func_decl_start_single = ignore # ignore/add/remove/force + +# Overrides nl_func_def_start when there is only one parameter. +# nl_func_def_start_single = ignore # ignore/add/remove/force + +# Add or remove newline after each ',' in a function declaration +nl_func_decl_args = ignore # ignore/add/remove/force + +# Add or remove newline after each ',' in a function definition +nl_func_def_args = ignore # ignore/add/remove/force + +# Add or remove newline before the ')' in a function declaration +nl_func_decl_end = remove # ignore/add/remove/force + +# Add or remove newline before the ')' in a function definition +nl_func_def_end = remove # ignore/add/remove/force + +# Overrides nl_func_decl_end when there is only one parameter. +# nl_func_decl_end_single = ignore # ignore/add/remove/force + +# Overrides nl_func_def_end when there is only one parameter. +# nl_func_def_end_single = ignore # ignore/add/remove/force + +# Add or remove newline between '()' in a function declaration. +nl_func_decl_empty = remove # ignore/add/remove/force + +# Add or remove newline between '()' in a function definition. +nl_func_def_empty = remove # ignore/add/remove/force + +# Add or remove newline between function signature and '{' +nl_fdef_brace = force # ignore/add/remove/force + +# Add or remove a newline between the return keyword and return expression. +nl_return_expr = remove # ignore/add/remove/force + +# Whether to put a newline after semicolons, except in 'for' statements +nl_after_semicolon = true # false/true + +# Whether to put a newline after brace open. +# This also adds a newline before the matching brace close. +nl_after_brace_open = true # false/true + +# If nl_after_brace_open and nl_after_brace_open_cmt are true, a newline is +# placed between the open brace and a trailing single-line comment. +nl_after_brace_open_cmt = true # false/true + +# Whether to put a newline after a virtual brace open with a non-empty body. +# These occur in un-braced if/while/do/for statement bodies. +nl_after_vbrace_open = true # false/true + +# Whether to put a newline after a virtual brace open with an empty body. +# These occur in un-braced if/while/do/for statement bodies. +nl_after_vbrace_open_empty = true # false/true + +# Whether to put a newline after a brace close. +# Does not apply if followed by a necessary ';'. +nl_after_brace_close = false # false/true + +# Whether to put a newline after a virtual brace close. +# Would add a newline before return in: 'if (foo) a++; return;' +nl_after_vbrace_close = true # false/true + +# Whether to alter newlines in '#define' macros +nl_define_macro = true # false/true + +# Whether to not put blanks after '#ifxx', '#elxx', or before '#endif' +nl_squeeze_ifdef = false # false/true + +# Add or remove blank line before 'if' +nl_before_if = ignore # ignore/add/remove/force + +# Add or remove blank line after 'if' statement +nl_after_if = ignore # ignore/add/remove/force + +# Add or remove blank line before 'for' +nl_before_for = ignore # ignore/add/remove/force + +# Add or remove blank line after 'for' statement +nl_after_for = ignore # ignore/add/remove/force + +# Add or remove blank line before 'while' +nl_before_while = ignore # ignore/add/remove/force + +# Add or remove blank line after 'while' statement +nl_after_while = ignore # ignore/add/remove/force + +# Add or remove blank line before 'switch' +nl_before_switch = ignore # ignore/add/remove/force + +# Add or remove blank line after 'switch' statement +nl_after_switch = ignore # ignore/add/remove/force + +# Add or remove blank line before 'do' +nl_before_do = ignore # ignore/add/remove/force + +# Add or remove blank line after 'do/while' statement +nl_after_do = ignore # ignore/add/remove/force + +# Whether to double-space commented-entries in struct/enum +nl_ds_struct_enum_cmt = true # false/true + +# Whether to double-space before the close brace of a struct/union/enum +# (lower priority than 'eat_blanks_before_close_brace') +nl_ds_struct_enum_close_brace = false # false/true + +# Add or remove a newline around a class colon. +# Related to pos_class_colon, nl_class_init_args, and pos_comma. +nl_class_colon = ignore # ignore/add/remove/force + +# Change simple unbraced if statements into a one-liner +# 'if(b)\n i++;' => 'if(b) i++;' +nl_create_if_one_liner = false # false/true + +# Change simple unbraced for statements into a one-liner +# 'for (i=0;i<5;i++)\n foo(i);' => 'for (i=0;i<5;i++) foo(i);' +nl_create_for_one_liner = false # false/true + +# Change simple unbraced while statements into a one-liner +# 'while (i<5)\n foo(i++);' => 'while (i<5) foo(i++);' +nl_create_while_one_liner = false # false/true + +# +# Positioning options +# + +# The position of arithmetic operators in wrapped expressions +pos_arith = ignore # ignore/join/lead/lead_break/lead_force/trail/trail_break/trail_force + +# The position of assignment in wrapped expressions. +# Do not affect '=' followed by '{' +pos_assign = ignore # ignore/join/lead/lead_break/lead_force/trail/trail_break/trail_force + +# The position of boolean operators in wrapped expressions +pos_bool = ignore # ignore/join/lead/lead_break/lead_force/trail/trail_break/trail_force + +# The position of comparison operators in wrapped expressions +pos_compare = ignore # ignore/join/lead/lead_break/lead_force/trail/trail_break/trail_force + +# The position of conditional (b ? t : f) operators in wrapped expressions +pos_conditional = ignore # ignore/join/lead/lead_break/lead_force/trail/trail_break/trail_force + +# The position of the comma in wrapped expressions +pos_comma = ignore # ignore/join/lead/lead_break/lead_force/trail/trail_break/trail_force + +# The position of the comma in the constructor initialization list +pos_class_comma = ignore # ignore/join/lead/lead_break/lead_force/trail/trail_break/trail_force + +# The position of colons between constructor and member initialization +pos_class_colon = ignore # ignore/join/lead/lead_break/lead_force/trail/trail_break/trail_force + +# +# Line Splitting options +# + +# Try to limit code width to N number of columns +code_width = 0 # number + +# Whether to fully split long 'for' statements at semi-colons +ls_for_split_full = true # false/true + +# Whether to fully split long function protos/calls at commas +ls_func_split_full = true # false/true + +# Whether to split lines as close to code_width as possible and ignore some groupings +ls_code_width = false # false/true + +# +# Blank line options +# + +# The maximum consecutive newlines +nl_max = 2 # number + +# The number of newlines after a function prototype, if followed by another function prototype +nl_after_func_proto = 1 # number + +# The number of newlines after a function prototype, if not followed by another function prototype +nl_after_func_proto_group = 1 # number + +# The number of newlines after '}' of a multi-line function body +nl_after_func_body = 2 # number + +# The number of newlines after '}' of a multi-line function body in a class declaration +nl_after_func_body_class = 2 # number + +# The number of newlines after '}' of a single line function body +nl_after_func_body_one_liner = 2 # number + +# The minimum number of newlines before a multi-line comment. +# Doesn't apply if after a brace open or another multi-line comment. +nl_before_block_comment = 2 # number + +# The minimum number of newlines before a single-line C comment. +# Doesn't apply if after a brace open or other single-line C comments. +nl_before_c_comment = 2 # number + +# The minimum number of newlines before a CPP comment. +# Doesn't apply if after a brace open or other CPP comments. +nl_before_cpp_comment = 2 # number + +# Whether to force a newline after a multi-line comment. +nl_after_multiline_comment = true # false/true + +# The number of newlines after '}' or ';' of a struct/enum/union definition +nl_after_struct = 2 # number + +# The number of newlines after '}' or ';' of a class definition +nl_after_class = 2 # number + +# The number of newlines before a 'private:', 'public:', 'protected:', 'signals:', or 'slots:' label. +# Will not change the newline count if after a brace open. +# 0 = No change. +nl_before_access_spec = 2 # number + +# The number of newlines after a 'private:', 'public:', 'protected:', 'signals:', or 'slots:' label. +# 0 = No change. +nl_after_access_spec = 1 # number + +# The number of newlines between a function def and the function comment. +# 0 = No change. +nl_comment_func_def = 1 # number + +# The number of newlines after a try-catch-finally block that isn't followed by a brace close. +# 0 = No change. +nl_after_try_catch_finally = 2 # number + +# The number of newlines before and after a property, indexer or event decl. +# 0 = No change. +nl_around_cs_property = 1 # number + +# The number of newlines between the get/set/add/remove handlers in C#. +# 0 = No change. +nl_between_get_set = 1 # number + +# Add or remove newline between C# property and the '{' +nl_property_brace = remove # ignore/add/remove/force + +# Whether to remove blank lines after '{' +eat_blanks_after_open_brace = false # false/true + +# Whether to remove blank lines before '}' +eat_blanks_before_close_brace = false # false/true + +# How aggressively to remove extra newlines not in preproc. +# 0: No change +# 1: Remove most newlines not handled by other config +# 2: Remove all newlines and reformat completely by config +nl_remove_extra_newlines = 0 # number + +# Whether to put a blank line before 'return' statements, unless after an open brace. +nl_before_return = true # false/true + +# Whether to put a blank line after 'return' statements, unless followed by a close brace. +nl_after_return = false # false/true + +# +# Code modifying options (non-whitespace) +# + +# Add or remove braces on single-line 'do' statement +mod_full_brace_do = remove # ignore/add/remove/force + +# Add or remove braces on single-line 'for' statement +mod_full_brace_for = remove # ignore/add/remove/force + +# Add or remove braces on single-line function definitions. (Pawn) +mod_full_brace_function = remove # ignore/add/remove/force + +# Add or remove braces on single-line 'if' statement. Will not remove the braces if they contain an 'else'. +mod_full_brace_if = remove # ignore/add/remove/force + +# Make all if/elseif/else statements in a chain be braced or not. Overrides mod_full_brace_if. +# If any must be braced, they are all braced. If all can be unbraced, then the braces are removed. +mod_full_brace_if_chain = true # false/true + +# Don't remove braces around statements that span N newlines +mod_full_brace_nl = 0 # number + +# Add or remove braces on single-line 'while' statement +mod_full_brace_while = remove # ignore/add/remove/force + +# Add or remove braces on single-line 'using ()' statement +mod_full_brace_using = remove # ignore/add/remove/force + +# Add or remove unnecessary paren on 'return' statement +mod_paren_on_return = remove # ignore/add/remove/force + +# Whether to change optional semicolons to real semicolons +mod_pawn_semicolon = true # false/true + +# Add parens on 'while' and 'if' statement around bools +mod_full_paren_if_bool = true # false/true + +# Whether to remove superfluous semicolons +mod_remove_extra_semicolon = true # false/true + +# If a function body exceeds the specified number of newlines and doesn't have a comment after +# the close brace, a comment will be added. +mod_add_long_function_closebrace_comment = 50 # number + +# If a switch body exceeds the specified number of newlines and doesn't have a comment after +# the close brace, a comment will be added. +mod_add_long_switch_closebrace_comment = 50 # number + +# If an #ifdef body exceeds the specified number of newlines and doesn't have a comment after +# the #endif, a comment will be added. +mod_add_long_ifdef_endif_comment = 1 # number + +# If an #ifdef or #else body exceeds the specified number of newlines and doesn't have a comment after +# the #else, a comment will be added. +mod_add_long_ifdef_else_comment = 1 # number + +# If TRUE, will sort consecutive single-line 'import' statements [Java, D] +mod_sort_import = false # false/true + +# If TRUE, will sort consecutive single-line 'using' statements [C#] +mod_sort_using = false # false/true + +# If TRUE, will sort consecutive single-line '#include' statements [C/C++] and '#import' statements [Obj-C] +# This is generally a bad idea, as it may break your code. +mod_sort_include = false # false/true + +# If TRUE, it will move a 'break' that appears after a fully braced 'case' before the close brace. +mod_move_case_break = true # false/true + +# Will add or remove the braces around a fully braced case statement. +# Will only remove the braces if there are no variable declarations in the block. +mod_case_brace = remove # ignore/add/remove/force + +# If TRUE, it will remove a void 'return;' that appears as the last statement in a function. +mod_remove_empty_return = true # false/true + +# +# Comment modifications +# + +# Try to wrap comments at cmt_width columns +cmt_width = 120 # number + +# Set the comment reflow mode (default: 0) +# 0: no reflowing (apart from the line wrapping due to cmt_width) +# 1: no touching at all +# 2: full reflow +cmt_reflow_mode = 1 # number + +# If false, disable all multi-line comment changes, including cmt_width. keyword substitution, and leading chars. +# Default is true. +# cmt_indent_multi = true # false/true + +# Whether to group c-comments that look like they are in a block +cmt_c_group = true # false/true + +# Whether to put an empty '/*' on the first line of the combined c-comment +cmt_c_nl_start = false # false/true + +# Whether to put a newline before the closing '*/' of the combined c-comment +cmt_c_nl_end = true # false/true + +# Whether to group cpp-comments that look like they are in a block +cmt_cpp_group = true # false/true + +# Whether to put an empty '/*' on the first line of the combined cpp-comment +cmt_cpp_nl_start = false # false/true + +# Whether to put a newline before the closing '*/' of the combined cpp-comment +cmt_cpp_nl_end = true # false/true + +# Whether to change cpp-comments into c-comments +cmt_cpp_to_c = false # false/true + +# Whether to put a star on subsequent comment lines +cmt_star_cont = true # false/true + +# The number of spaces to insert at the start of subsequent comment lines +cmt_sp_before_star_cont = 0 # number + +# The number of spaces to insert after the star on subsequent comment lines +cmt_sp_after_star_cont = 0 # number + +# For multi-line comments with a '*' lead, remove leading spaces if the first and last lines of +# the comment are the same length. Default=True +cmt_multi_check_last = false # false/true + +# The filename that contains text to insert at the head of a file if the file doesn't start with a C/C++ comment. +# Will substitute $(filename) with the current file's name. +cmt_insert_file_header = "" # string + +# The filename that contains text to insert at the end of a file if the file doesn't end with a C/C++ comment. +# Will substitute $(filename) with the current file's name. +cmt_insert_file_footer = "" # string + +# The filename that contains text to insert before a function implementation if the function isn't preceded with a C/C++ comment. +# Will substitute $(function) with the function name and $(javaparam) with the javadoc @param and @return stuff. +# Will also substitute $(fclass) with the class name: void CFoo::Bar() { ... } +cmt_insert_func_header = "" # string + +# The filename that contains text to insert before a class if the class isn't preceded with a C/C++ comment. +# Will substitute $(class) with the class name. +cmt_insert_class_header = "" # string + +# The filename that contains text to insert before a Obj-C message specification if the method isn't preceeded with a C/C++ comment. +# Will substitute $(message) with the function name and $(javaparam) with the javadoc @param and @return stuff. +cmt_insert_oc_msg_header = "" # string + +# If a preprocessor is encountered when stepping backwards from a function name, then +# this option decides whether the comment should be inserted. +# Affects cmt_insert_oc_msg_header, cmt_insert_func_header and cmt_insert_class_header. +cmt_insert_before_preproc = false # false/true + +# +# Preprocessor options +# + +# Control indent of preprocessors inside #if blocks at brace level 0 +pp_indent = remove # ignore/add/remove/force + +# Whether to indent #if/#else/#endif at the brace level (true) or from column 1 (false) +pp_indent_at_level = false # false/true + +# If pp_indent_at_level=false, specifies the number of columns to indent per level. Default=1. +pp_indent_count = 1 # number + +# Add or remove space after # based on pp_level of #if blocks +pp_space = force # ignore/add/remove/force + +# Sets the number of spaces added with pp_space +pp_space_count = 1 # number + +# The indent for #region and #endregion in C# and '#pragma region' in C/C++ +pp_indent_region = 0 # number + +# Whether to indent the code between #region and #endregion +pp_region_indent_code = false # false/true + +# If pp_indent_at_level=true, sets the indent for #if, #else, and #endif when not at file-level +pp_indent_if = 0 # number + +# Control whether to indent the code between #if, #else and #endif when not at file-level +pp_if_indent_code = false # false/true + +# Whether to indent '#define' at the brace level (true) or from column 1 (false) +pp_define_at_level = false # false/true + +# You can force a token to be a type with the 'type' option. +# Example: +# type myfoo1 myfoo2 +# +# You can create custom macro-based indentation using macro-open, +# macro-else and macro-close. +# Example: +# macro-open BEGIN_TEMPLATE_MESSAGE_MAP +# macro-open BEGIN_MESSAGE_MAP +# macro-close END_MESSAGE_MAP +# +# You can assign any keyword to any type with the set option. +# set func_call_user _ N_ +# +# The full syntax description of all custom definition config entries +# is shown below: +# +# define custom tokens as: +# - embed whitespace in token using '' escape character, or +# put token in quotes +# - these: ' " and ` are recognized as quote delimiters +# +# type token1 token2 token3 ... +# ^ optionally specify multiple tokens on a single line +# define def_token output_token +# ^ output_token is optional, then NULL is assumed +# macro-open token +# macro-close token +# macro-else token +# set id token1 token2 ... +# ^ optionally specify multiple tokens on a single line +# ^ id is one of the names in token_enum.h sans the CT_ prefix, +# e.g. PP_PRAGMA +# +# all tokens are separated by any mix of ',' commas, '=' equal signs +# and whitespace (space, tab) +# diff --git a/Algorithms/bplus-tree/LICENSE b/Algorithms/bplus-tree/LICENSE new file mode 100644 index 0000000..36b7cd9 --- /dev/null +++ b/Algorithms/bplus-tree/LICENSE @@ -0,0 +1,23 @@ +Boost Software License - Version 1.0 - August 17th, 2003 + +Permission is hereby granted, free of charge, to any person or organization +obtaining a copy of the software and accompanying documentation covered by +this license (the "Software") to use, reproduce, display, distribute, +execute, and transmit the Software, and to prepare derivative works of the +Software, and to permit third-parties to whom the Software is furnished to +do so, all subject to the following: + +The copyright notices in the Software and this entire statement, including +the above license grant, this restriction and the following disclaimer, +must be included in all copies of the Software, in whole or in part, and +all derivative works of the Software, unless such copies or derivative +works are solely in the form of machine-executable object code generated by +a source language processor. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT +SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE +FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE, +ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER +DEALINGS IN THE SOFTWARE. diff --git a/Algorithms/bplus-tree/Makefile b/Algorithms/bplus-tree/Makefile new file mode 100644 index 0000000..1d4f373 --- /dev/null +++ b/Algorithms/bplus-tree/Makefile @@ -0,0 +1,22 @@ +## +# Distributed under the Boost Software License, Version 1.0. +# See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt +## + +all: build/bplus_tree_test + +build: Makefile + install -d build + +coverage: Makefile + install -d coverage + +test: Makefile build/bplus_tree_test coverage/bplus_tree_test + ./build/bplus_tree_test + cd coverage && ./bplus_tree_test 1>/dev/null 2>/dev/null && lcov --capture --directory . --output bplus_tree_test.info && genhtml bplus_tree_test.info + +coverage/bplus_tree_test: Makefile coverage src/*.[ch] include/*.h test/*.c + cd coverage && gcc -std=c99 -fprofile-arcs -ftest-coverage -o bplus_tree_test ../test/bplus_tree_test.c `pkg-config --cflags --libs glib-2.0` -g -ggdb -I../include/ -I../src/ + +build/bplus_tree_test: Makefile build src/*.[ch] include/*.h test/*.c + cd build && clang -std=c99 -o bplus_tree_test ../test/bplus_tree_test.c `pkg-config --cflags --libs glib-2.0` -g -ggdb -I../include/ -I../src/ diff --git a/Algorithms/bplus-tree/include/bplus_tree.h b/Algorithms/bplus-tree/include/bplus_tree.h new file mode 100644 index 0000000..7bb3e1d --- /dev/null +++ b/Algorithms/bplus-tree/include/bplus_tree.h @@ -0,0 +1,63 @@ +/** + * Distributed under the Boost Software License, Version 1.0. + * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt + */ + +#ifndef __BPLUS_TREE_H__ +#define __BPLUS_TREE_H__ + +#include <stdint.h> +#include <stdlib.h> + +#include <glib.h> + +#ifdef __cplusplus +extern "C" +{ +#endif /* __cplusplus */ + +typedef uint64_t BplusKey; +typedef void* BplusValue; +typedef struct _BplusItem BplusItem; + +struct _BplusItem +{ + BplusKey key; + BplusValue value; +}; + +typedef struct _BplusTree BplusTree; +typedef struct _BplusIterator BplusIterator; + +typedef void (BplusForeachItemFunc)(BplusTree const* tree, BplusItem* item, void* argument); + +BplusTree* bplus_tree_new(); +BplusTree* bplus_tree_new_full(gboolean allow_duplicate_keys); +void bplus_tree_destroy(BplusTree* tree); +void bplus_tree_destroy_each(BplusTree* tree, BplusForeachItemFunc* foreach, void* argument); + +void bplus_tree_insert(BplusTree* tree, BplusKey const key, BplusValue const value); +BplusValue bplus_tree_remove(BplusTree* tree, BplusKey const key); +BplusValue bplus_tree_remove_first(BplusTree* tree); +void bplus_tree_remove_value(BplusTree* tree, BplusKey const key, BplusValue const value); +BplusValue bplus_tree_get(BplusTree* tree, BplusKey const key); + +BplusValue bplus_tree_get_first(BplusTree const* tree); +BplusValue bplus_tree_get_nth(BplusTree const* tree, size_t position); + +BplusIterator* bplus_iterator_new(BplusTree const* tree); +void bplus_iterator_destroy(BplusIterator* iterator); +gboolean bplus_iterator_next(BplusIterator* iterator); +gboolean bplus_iterator_previous(BplusIterator* iterator); +BplusItem const* bplus_iterator_get_item(BplusIterator const* iterator); +BplusIterator* bplus_tree_first(BplusTree const* tree); +BplusIterator* bplus_iterator_from_key(BplusTree const* tree, BplusKey const key); +BplusIterator* bplus_iterator_to_key(BplusTree const* tree, BplusKey const key); +BplusIterator* bplus_iterator_for_key(BplusTree const* tree, BplusKey const key); +BplusIterator* bplus_iterator_for_key_range(BplusTree const* tree, BplusKey const key_from, BplusKey const key_to); + +#ifdef __cplusplus +} +#endif /* __cplusplus */ + +#endif // ifndef __BPLUS_TREE_H__ diff --git a/Algorithms/bplus-tree/src/bplus_foreach.c b/Algorithms/bplus-tree/src/bplus_foreach.c new file mode 100644 index 0000000..e9184b7 --- /dev/null +++ b/Algorithms/bplus-tree/src/bplus_foreach.c @@ -0,0 +1,39 @@ +/** + * Distributed under the Boost Software License, Version 1.0. + * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt + */ + +#include "bplus_foreach.h" + +#include "bplus_node.h" + +void bplus_foreach_item_in_node(BplusTree* tree, BplusNode* node, BplusForeachItemFunc* foreach, void* argument) +{ + if (!node->is_leaf) + for (size_t i = 0; i < node->length; ++i) + bplus_foreach_item_in_node(tree, bplus_node_at(node, i), foreach, argument); + + else + for (size_t i = 0; i < node->length; ++i) + foreach(tree, node->items + i, argument); + +} + +void bplus_foreach_item_in_tree(BplusTree* tree, BplusForeachItemFunc* foreach, void* argument) +{ + bplus_foreach_item_in_node(tree, tree->root, foreach, argument); +} + +void bplus_foreach_node_in_node(BplusTree* tree, BplusNode* node, BplusForeachNodeFunc* foreach, void* argument) +{ + if (!node->is_leaf) + for (size_t i = 0; i < node->length; ++i) + bplus_foreach_node_in_node(tree, bplus_node_at(node, i), foreach, argument); + + foreach(tree, node, argument); +} + +void bplus_foreach_node_in_tree(BplusTree* tree, BplusForeachNodeFunc* foreach, void* argument) +{ + bplus_foreach_node_in_node(tree, tree->root, foreach, argument); +} diff --git a/Algorithms/bplus-tree/src/bplus_foreach.h b/Algorithms/bplus-tree/src/bplus_foreach.h new file mode 100644 index 0000000..69849a6 --- /dev/null +++ b/Algorithms/bplus-tree/src/bplus_foreach.h @@ -0,0 +1,27 @@ +/** + * Distributed under the Boost Software License, Version 1.0. + * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt + */ + +#ifndef __BPLUS_FOREACH_H__ +#define __BPLUS_FOREACH_H__ + +#include "bplus_tree_private.h" + +#ifdef __cplusplus +extern "C" +{ +#endif // ifdef __cplusplus + +void bplus_foreach_item_in_node(BplusTree* tree, BplusNode* node, BplusForeachItemFunc* foreach, void* argument); +void bplus_foreach_item_in_tree(BplusTree* tree, BplusForeachItemFunc* foreach, void* argument); + +typedef void (BplusForeachNodeFunc)(BplusTree* tree, BplusNode* node, void* argument); +void bplus_foreach_node_in_node(BplusTree* tree, BplusNode* node, BplusForeachNodeFunc* foreach, void* argument); +void bplus_foreach_node_in_tree(BplusTree* tree, BplusForeachNodeFunc* foreach, void* argument); + +#ifdef __cplusplus +} +#endif // ifdef __cplusplus + +#endif // ifndef __BPLUS_FOREACH_H__ diff --git a/Algorithms/bplus-tree/src/bplus_insert.c b/Algorithms/bplus-tree/src/bplus_insert.c new file mode 100644 index 0000000..9cd3ea7 --- /dev/null +++ b/Algorithms/bplus-tree/src/bplus_insert.c @@ -0,0 +1,58 @@ +/** + * Distributed under the Boost Software License, Version 1.0. + * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt + */ + +#include "bplus_insert.h" + +#include "bplus_node.h" +#include "bplus_search.h" +#include "bplus_rebalance.h" + +#include <string.h> + +static void bplus_leaf_insert_at(BplusTree const* tree, BplusNode* node, size_t const index, BplusKey const key, BplusValue const value) +{ + g_return_if_fail(node != NULL); + g_return_if_fail(index <= node->length); + + bplus_node_move_and_resize_data(tree, node, index + 1, index); + bplus_key_at(node, index) = key; + bplus_value_at(node, index) = value; +} + +void bplus_node_insert_at(BplusTree const* tree, BplusNode* node, size_t const index, size_t const length, BplusItem const* const items) +{ + g_return_if_fail(node != NULL); + g_return_if_fail(index <= node->length); + g_return_if_fail(node->length + length <= BPLUS_TREE_ORDER); + + bplus_node_move_and_resize_data(tree, node, index + length, index); + memcpy(node->items + index, items, length * sizeof(BplusItem)); + + if (node->is_leaf) + return; + + for (size_t i = index; i < index + length; ++i) + bplus_node_at(node, i)->parent = node; +} + +void bplus_tree_insert(BplusTree* tree, BplusKey const key, BplusValue const value) +{ + BplusPath path; + bplus_tree_get_path_to_key(tree, key, &path); + + size_t index = path.index[0]; + BplusNode* node = (BplusNode*) path.leaf; + + /* If the node is not empty, we will insert it after the given index */ + if ((index < node->length) && bplus_key_lte(tree, bplus_key_at(node, index), key)) + index++; + + bplus_leaf_insert_at(tree, node, index, key, value); + if (index == 0) + bplus_rebalance_propagate(tree, &path); + + if (bplus_node_overfilled(node)) + bplus_rebalance_overfilled(tree, &path); +} diff --git a/Algorithms/bplus-tree/src/bplus_insert.h b/Algorithms/bplus-tree/src/bplus_insert.h new file mode 100644 index 0000000..e73f963 --- /dev/null +++ b/Algorithms/bplus-tree/src/bplus_insert.h @@ -0,0 +1,22 @@ +/** + * Distributed under the Boost Software License, Version 1.0. + * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt + */ + +#ifndef __BPLUS_INSERT_H__ +#define __BPLUS_INSERT_H__ + +#include "bplus_tree_private.h" + +#ifdef __cplusplus +extern "C" +{ +#endif // ifdef __cplusplus + +void bplus_node_insert_at(BplusTree const* tree, BplusNode* node, size_t const index, size_t const length, BplusItem const* const items); + +#ifdef __cplusplus +} +#endif // ifdef __cplusplus + +#endif // ifndef __BPLUS_INSERT_H__ diff --git a/Algorithms/bplus-tree/src/bplus_iterator.c b/Algorithms/bplus-tree/src/bplus_iterator.c new file mode 100644 index 0000000..8ab796e --- /dev/null +++ b/Algorithms/bplus-tree/src/bplus_iterator.c @@ -0,0 +1,161 @@ +/** + * Distributed under the Boost Software License, Version 1.0. + * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt + */ + +#include "bplus_iterator.h" + +#include "bplus_leaf.h" +#include "bplus_search.h" + +static BplusIterator* bplus_iterator_new_full(BplusTree const* tree, + BplusLeaf const* leaf_from, BplusItem const* item_from, + BplusLeaf const* leaf_to, BplusItem const* item_to) +{ + BplusIterator* iterator = g_slice_new(BplusIterator); + + iterator->leaf_from = leaf_from; + iterator->item_from = item_from; + iterator->leaf_to = leaf_to; + iterator->item_to = item_to; + iterator->item = item_from; + iterator->leaf = leaf_from; + + return iterator; +} + +static BplusIterator* bplus_iterator_new_to_last(BplusTree const* tree, BplusLeaf const* leaf_from, BplusItem const* item_from) +{ + return bplus_iterator_new_full(tree, leaf_from, item_from, tree->last, tree->last->node.items + tree->last->node.length); +} + +static BplusIterator* bplus_iterator_new_from_first(BplusTree const* tree, BplusLeaf const* leaf_to, BplusItem const* item_to) +{ + return bplus_iterator_new_full(tree, tree->first, tree->first->node.items, leaf_to, item_to); +} + +BplusIterator* bplus_iterator_new(BplusTree const* tree) +{ + return bplus_iterator_new_to_last(tree, tree->first, tree->first->node.items); +} + +void bplus_iterator_destroy(BplusIterator* iterator) +{ + g_return_if_fail(iterator != NULL); + + g_slice_free(BplusIterator, iterator); +} + +gboolean bplus_iterator_next(BplusIterator* iterator) +{ + g_return_val_if_fail(iterator != NULL, FALSE); + + BplusItem const* const next = iterator->item + 1; + BplusLeaf const* const leaf = iterator->leaf; + if (next == iterator->item_to) + return FALSE; + + if (next - leaf->node.items < leaf->node.length) + { + ++iterator->item; + } + else + { + if (leaf->right == NULL) + return FALSE; + + iterator->leaf = leaf->right; + iterator->item = leaf->right->node.items; + } + + return TRUE; +} + +gboolean bplus_iterator_previous(BplusIterator* iterator) +{ + g_return_val_if_fail(iterator != NULL, FALSE); + + BplusItem const* const item = iterator->item; + BplusLeaf const* const leaf = iterator->leaf; + + if (item == iterator->item_from) + return FALSE; + + if (item - leaf->node.items == 0) + { + if (leaf->left == NULL) + return FALSE; + + iterator->leaf = leaf->left; + iterator->item = leaf->left->node.items + leaf->left->node.length; + } + + --iterator->item; + + return TRUE; +} + +BplusItem const* bplus_iterator_get_item(BplusIterator const* iterator) +{ + g_return_val_if_fail(iterator != NULL, NULL); + + if (iterator->item_from == iterator->item_to) + return NULL; + + return iterator->item; +} + +BplusIterator* bplus_tree_first(BplusTree const* tree) +{ + g_return_val_if_fail(tree != NULL, NULL); + + return bplus_iterator_new(tree); +} + +BplusIterator* bplus_iterator_from_key(BplusTree const* tree, BplusKey const key) +{ + g_return_val_if_fail(tree != NULL, NULL); + + BplusPath path_from; + BplusPath path_to; + bplus_tree_get_paths_to_key_range(tree, key, key, &path_from, &path_to); + + return bplus_iterator_new_to_last(tree, (BplusLeaf*) path_from.leaf, path_from.leaf->items + path_from.index[0]); +} + +BplusIterator* bplus_iterator_to_key(BplusTree const* tree, BplusKey const key) +{ + g_return_val_if_fail(tree != NULL, NULL); + + BplusPath path_from; + BplusPath path_to; + bplus_tree_get_paths_to_key_range(tree, key, key, &path_from, &path_to); + + return bplus_iterator_new_from_first(tree, (BplusLeaf*) path_to.leaf, path_to.leaf->items + path_to.index[0]); +} + +BplusIterator* bplus_iterator_for_key(BplusTree const* tree, BplusKey const key) +{ + g_return_val_if_fail(tree != NULL, NULL); + + BplusPath path_from; + BplusPath path_to; + bplus_tree_get_paths_to_key_range(tree, key, key, &path_from, &path_to); + + return bplus_iterator_new_full(tree, + (BplusLeaf*) path_from.leaf, path_from.leaf->items + path_from.index[0], + (BplusLeaf*) path_to.leaf, path_to.leaf->items + path_to.index[0]); +} + +BplusIterator* bplus_iterator_for_key_range(BplusTree const* tree, BplusKey const key_from, BplusKey const key_to) +{ + g_return_val_if_fail(tree != NULL, NULL); + + BplusPath path_from; + BplusPath path_to; + bplus_tree_get_paths_to_key_range(tree, key_from, key_to, &path_from, &path_to); + + return bplus_iterator_new_full(tree, + (BplusLeaf*) path_from.leaf, path_from.leaf->items + path_from.index[0], + (BplusLeaf*) path_to.leaf, path_to.leaf->items + path_to.index[0]); +} diff --git a/Algorithms/bplus-tree/src/bplus_iterator.h b/Algorithms/bplus-tree/src/bplus_iterator.h new file mode 100644 index 0000000..c7ae9b2 --- /dev/null +++ b/Algorithms/bplus-tree/src/bplus_iterator.h @@ -0,0 +1,31 @@ +/** + * Distributed under the Boost Software License, Version 1.0. + * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt + */ + +#ifndef __BPLUS_ITERATOR_H__ +#define __BPLUS_ITERATOR_H__ + +#include "bplus_tree_private.h" + +#ifdef __cplusplus +extern "C" +{ +#endif // ifdef __cplusplus + +struct _BplusIterator +{ + BplusItem const* item; + BplusLeaf const* leaf; + + BplusLeaf const* leaf_from; + BplusItem const* item_from; + BplusLeaf const* leaf_to; + BplusItem const* item_to; +}; + +#ifdef __cplusplus +} +#endif // ifdef __cplusplus + +#endif // ifndef __BPLUS_ITERATOR_H__ diff --git a/Algorithms/bplus-tree/src/bplus_leaf.c b/Algorithms/bplus-tree/src/bplus_leaf.c new file mode 100644 index 0000000..a6b6ae5 --- /dev/null +++ b/Algorithms/bplus-tree/src/bplus_leaf.c @@ -0,0 +1,71 @@ +/** + * Distributed under the Boost Software License, Version 1.0. + * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt + */ + +#include "bplus_leaf.h" + +BplusLeaf* bplus_leaf_new(BplusTree* tree) +{ + g_return_val_if_fail(tree != NULL, NULL); + + BplusLeaf* leaf = g_slice_new(BplusLeaf); + + bplus_node_init(&leaf->node, TRUE); + leaf->left = NULL; + leaf->right = NULL; + +#ifdef BPLUS_TREE_GATHER_STATS + tree->node_count++; + tree->leaf_count++; + tree->underflow_count++; +#endif /* ifdef BPLUS_TREE_GATHER_STATS */ + + return leaf; +} + +BplusLeaf* bplus_leaf_new_right(BplusTree* tree, BplusLeaf* leaf_left) +{ + g_return_val_if_fail(tree != NULL, NULL); + g_return_val_if_fail(leaf_left != NULL, NULL); + + BplusLeaf* leaf_right = bplus_leaf_new(tree); + + leaf_right->left = leaf_left; + leaf_right->right = leaf_left->right; + leaf_left->right = leaf_right; + + if (leaf_right->right != NULL) + leaf_right->right->left = leaf_right; + + if (tree->last == leaf_left) + tree->last = leaf_right; + + return leaf_right; +} + +void bplus_leaf_destroy(BplusTree* tree, BplusLeaf* leaf) +{ + g_return_if_fail(tree != NULL); + g_return_if_fail(leaf != NULL); + + if (leaf->left != NULL) + leaf->left->right = leaf->right; + + if (leaf->right != NULL) + leaf->right->left = leaf->left; + + if (tree->first == leaf) + tree->first = leaf->right; + + if (tree->last == leaf) + tree->last = leaf->left; + +#ifdef BPLUS_TREE_GATHER_STATS + tree->node_count--; + tree->leaf_count--; + tree->underflow_count--; +#endif /* ifdef BPLUS_TREE_GATHER_STATS */ + + g_slice_free(BplusLeaf, leaf); +} diff --git a/Algorithms/bplus-tree/src/bplus_leaf.h b/Algorithms/bplus-tree/src/bplus_leaf.h new file mode 100644 index 0000000..482a933 --- /dev/null +++ b/Algorithms/bplus-tree/src/bplus_leaf.h @@ -0,0 +1,34 @@ +/** + * Distributed under the Boost Software License, Version 1.0. + * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt + */ + +#ifndef __BPLUS_LEAF_H__ +#define __BPLUS_LEAF_H__ + +#include "bplus_tree_private.h" + +#include "bplus_node.h" + +#ifdef __cplusplus +extern "C" +{ +#endif // ifdef __cplusplus + +struct _BplusLeaf +{ + BplusNode node; + + BplusLeaf* left; + BplusLeaf* right; +}; + +BplusLeaf* bplus_leaf_new(BplusTree* tree); +BplusLeaf* bplus_leaf_new_right(BplusTree* tree, BplusLeaf* leaf_left); +void bplus_leaf_destroy(BplusTree* tree, BplusLeaf* leaf); + +#ifdef __cplusplus +} +#endif // ifdef __cplusplus + +#endif // ifndef __BPLUS_LEAF_H__ diff --git a/Algorithms/bplus-tree/src/bplus_node.c b/Algorithms/bplus-tree/src/bplus_node.c new file mode 100644 index 0000000..6637367 --- /dev/null +++ b/Algorithms/bplus-tree/src/bplus_node.c @@ -0,0 +1,111 @@ +/** + * Distributed under the Boost Software License, Version 1.0. + * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt + */ + +#include "bplus_node.h" + +#include "bplus_leaf.h" + +#include <string.h> + +BplusNode* bplus_node_new(BplusTree* tree) +{ + g_return_val_if_fail(tree != NULL, NULL); + + BplusNode* node = g_slice_new(BplusNode); + + bplus_node_init(node, FALSE); + +#ifdef BPLUS_TREE_GATHER_STATS + tree->node_count++; + tree->underflow_count++; +#endif /* ifdef BPLUS_TREE_GATHER_STATS */ + + return node; +} + +BplusNode* bplus_node_new_right(BplusTree* tree, BplusNode* node_left) +{ + g_return_val_if_fail(tree != NULL, NULL); + g_return_val_if_fail(node_left != NULL, NULL); + + BplusNode* node_right; + + if (node_left->is_leaf) + node_right = (BplusNode*) bplus_leaf_new_right(tree, (BplusLeaf*) node_left); + else + node_right = bplus_node_new(tree); + + node_right->parent = node_left->parent; + + return node_right; +} + +void bplus_node_init(BplusNode* node, gboolean is_leaf) +{ + g_return_if_fail(node != NULL); + + node->parent = NULL; + node->is_leaf = is_leaf; + + node->length = 0; +} + +void bplus_node_destroy(BplusTree* tree, BplusNode* node) +{ + g_return_if_fail(tree != NULL); + g_return_if_fail(node != NULL); + + if (node->is_leaf) + { + bplus_leaf_destroy(tree, (BplusLeaf*) node); + } + else + { +#ifdef BPLUS_TREE_GATHER_STATS + tree->node_count--; + tree->underflow_count--; +#endif /* ifdef BPLUS_TREE_GATHER_STATS */ + + g_slice_free(BplusNode, node); + } +} + +void bplus_node_move_and_resize_data(BplusTree const* tree, BplusNode* node, size_t const index_to, size_t const index_from) +{ + g_return_if_fail(node != NULL); + g_return_if_fail(index_from <= node->length); + +#ifdef BPLUS_TREE_GATHER_STATS + int was_underfilled = bplus_node_underfilled(node); + int was_overfilled = bplus_node_overfilled(node); +#endif /* ifdef BPLUS_TREE_GATHER_STATS */ + + int64_t const resize_length = index_to - index_from; + if (resize_length == 0) + return; + + int64_t const move_length = node->length - index_from; + if (move_length > 0) + memmove(node->items + index_to, node->items + index_from, move_length * sizeof(BplusItem)); + + if (resize_length > 0) + node->length += resize_length; + + else if (resize_length < 0) + node->length -= -resize_length; + +#ifdef BPLUS_TREE_GATHER_STATS + if (!bplus_node_underfilled(node) && was_underfilled) + tree->underflow_count--; + else if (bplus_node_underfilled(node) && !was_underfilled) + tree->underflow_count++; + + if (bplus_node_overfilled(node) && !was_overfilled) + tree->overflow_count++; + else if (!bplus_node_overfilled(node) && was_overfilled) + tree->overflow_count--; +#endif /* ifdef BPLUS_TREE_GATHER_STATS */ + +} diff --git a/Algorithms/bplus-tree/src/bplus_node.h b/Algorithms/bplus-tree/src/bplus_node.h new file mode 100644 index 0000000..83a4d9a --- /dev/null +++ b/Algorithms/bplus-tree/src/bplus_node.h @@ -0,0 +1,55 @@ +/** + * Distributed under the Boost Software License, Version 1.0. + * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt + */ + +#ifndef __BPLUS_NODE_H__ +#define __BPLUS_NODE_H__ + +#include "bplus_tree_private.h" + +#ifdef __cplusplus +extern "C" +{ +#endif // ifdef __cplusplus + +struct _BplusNode +{ + size_t length; + BplusItem items[BPLUS_TREE_ORDER]; + + uint8_t is_leaf; + BplusNode* parent; +}; + +#define bplus_key_gt(bplus_tree_m, k1, k2) ((k1) > (k2)) +#define bplus_key_gte(bplus_tree_m, k1, k2) ((k1) >= (k2)) +#define bplus_key_lt(bplus_tree_m, k1, k2) ((k1) < (k2)) +#define bplus_key_lte(bplus_tree_m, k1, k2) ((k1) <= (k2)) +#define bplus_key_eq(bplus_tree_m, k1, k2) ((k1) == (k2)) +#define bplus_key_neq(bplus_tree_m, k1, k2) ((k1) != (k2)) + +#define bplus_key_at(node_m, index_m) (((BplusNode*) node_m)->items[(index_m)].key) +#define bplus_key_first(node_m) bplus_key_at(node_m, 0) +#define bplus_key_last(node_m) bplus_key_at(node_m, (node_m)->length - 1) +#define bplus_value_at(node_m, index_m) (((BplusNode*) node_m)->items[(index_m)].value) +#define bplus_value_first(node_m) bplus_value_at(node_m, 0) +#define bplus_value_last(node_m) bplus_value_at(node_m, (node_m)->length - 1) +#define bplus_node_at(node_m, index_m) ((BplusNode*) bplus_value_at(node_m, index_m)) +#define bplus_node_first(node_m) ((BplusNode*) bplus_value_first(node_m)) +#define bplus_node_last(node_m) ((BplusNode*) bplus_value_last(node_m)) + +#define bplus_node_overfilled(node_m) ((node_m)->length > (BPLUS_TREE_ORDER - 1)) +#define bplus_node_underfilled(node_m) ((node_m)->length <= 1) + +BplusNode* bplus_node_new(BplusTree* tree); +BplusNode* bplus_node_new_right(BplusTree* tree, BplusNode* node_left); +void bplus_node_destroy(BplusTree* tree, BplusNode* node); +void bplus_node_init(BplusNode* node, gboolean is_leaf); +void bplus_node_move_and_resize_data(BplusTree const* tree, BplusNode* node, size_t const index_to, size_t const index_from); + +#ifdef __cplusplus +} +#endif // ifdef __cplusplus + +#endif // ifndef __BPLUS_NODE_H__ diff --git a/Algorithms/bplus-tree/src/bplus_rebalance.c b/Algorithms/bplus-tree/src/bplus_rebalance.c new file mode 100644 index 0000000..a3cf401 --- /dev/null +++ b/Algorithms/bplus-tree/src/bplus_rebalance.c @@ -0,0 +1,279 @@ +/** + * Distributed under the Boost Software License, Version 1.0. + * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt + */ + +#include "bplus_rebalance.h" + +#include "bplus_node.h" +#include "bplus_search.h" +#include "bplus_insert.h" +#include "bplus_remove.h" + +void bplus_rebalance_propagate(BplusTree const* tree, BplusPath* path) +{ + g_return_if_fail(tree != NULL); + g_return_if_fail(path != NULL); + + BplusNode* node = path->leaf; + for (size_t i = 1; i < path->length; ++i) + { + size_t const index = path->index[i]; + BplusKey const key = bplus_key_first(node); + + if (bplus_key_gt(tree, bplus_key_at(node->parent, index), key)) + bplus_key_at(node->parent, index) = key; + else + break; + + node = node->parent; + } +} + +static int64_t bplus_node_get_rebalance_amount(BplusTree const* tree, BplusNode const* node_left, BplusNode const* node_right) +{ + g_return_val_if_fail(tree != NULL, 0); + g_return_val_if_fail(node_left != NULL, 0); + g_return_val_if_fail(node_right != NULL, 0); + + size_t const total = node_left->length + node_right->length; + + /* If the nodes can be merged without overfilling */ + if (total <= (BPLUS_TREE_ORDER / 3)) + return -node_right->length; + + /* If the data can be balanced over the two without overfilling */ + else if (total < (BPLUS_TREE_ORDER * 5 / 3)) + return node_left->length - (total + 1) / 2; + + return 0; +} + +static gboolean bplus_node_find_merge_candidate(BplusTree const* tree, size_t const index, BplusNode* node, + BplusNode** node_left, BplusNode** node_right) +{ + g_return_val_if_fail(tree != NULL, FALSE); + g_return_val_if_fail(node != NULL, FALSE); + + *node_left = node; + *node_right = node; + if ((node->parent == NULL) || (node->parent->length <= 1)) + return FALSE; + + if (index == 0) + { + *node_right = bplus_node_at(node->parent, index + 1); + if (bplus_node_get_rebalance_amount(tree, node, *node_right) == 0) + *node_right = node; + + } + else if (index == node->parent->length - 1) + { + *node_left = bplus_node_at(node->parent, index - 1); + if (bplus_node_get_rebalance_amount(tree, *node_left, node) == 0) + *node_left = node; + + } + else + { + *node_left = bplus_node_at(node->parent, index - 1); + *node_right = bplus_node_at(node->parent, index + 1); + + int64_t const merge_amount_right = bplus_node_get_rebalance_amount(tree, node, *node_right); + int64_t const merge_amount_left = bplus_node_get_rebalance_amount(tree, *node_left, node); + + if (merge_amount_left < 0) + { + /* Merge with left copies data to the left. + * Prefer a merge with right only if it copies less data from the right. + */ + if (merge_amount_right >= 0) + *node_right = node; + else if (merge_amount_right < merge_amount_left) + *node_right = node; + else + *node_left = node; + } + else if (merge_amount_left > 0) + { + /* Merge with left copies data from the left. + * Prefer a merge with right if it copies less data to the right or data from right. + */ + if (merge_amount_right == 0) + *node_right = node; + else if (merge_amount_right > merge_amount_left) + *node_right = node; + else + *node_left = node; + } + else if (merge_amount_right != 0) + { + /* Merge with left is impossible. + * Prefer a merge with right. + */ + *node_left = node; + } + else + { + *node_left = node; + *node_right = node; + } + } + + return *node_left != *node_right; +} /* bplus_node_find_merge_candidate */ + +static size_t bplus_rebalance_data(BplusTree const* tree, BplusNode* node_left, BplusNode* node_right) +{ + g_return_val_if_fail(tree != NULL, 0); + g_return_val_if_fail(node_left != NULL, 0); + g_return_val_if_fail(node_right != NULL, 0); + + int64_t const amount = bplus_node_get_rebalance_amount(tree, node_left, node_right); + g_return_val_if_fail(amount <= 0 || amount < node_left->length, 0); + g_return_val_if_fail(amount >= 0 || -amount <= node_right->length, 0); + + if (amount > 0) + { + size_t const index = node_left->length - amount; + BplusItem const* items = node_left->items + index; + + bplus_node_insert_at(tree, node_right, 0, amount, items); + bplus_node_remove_at(tree, node_left, index, amount); + + } + else if (amount < 0) + { + size_t const index = node_left->length; + BplusItem const* items = node_right->items; + + bplus_node_insert_at(tree, node_left, index, -amount, items); + bplus_node_remove_at(tree, node_right, 0, -amount); + } + + return 0; +} /* bplus_rebalance_data */ + +static void bplus_rebalance_split_node(BplusTree* tree, BplusNode* node_left, size_t const index) +{ + g_return_if_fail(tree != NULL); + g_return_if_fail(node_left != NULL); + + BplusNode* const node_right = bplus_node_new_right(tree, node_left); + bplus_rebalance_data(tree, node_left, node_right); + + BplusItem const item = { .key = bplus_key_first(node_right), .value = node_right }; + bplus_node_insert_at(tree, node_left->parent, index + 1, 1, &item); +} + +static void bplus_rebalance_new_root(BplusTree* tree) +{ + g_return_if_fail(tree != NULL); + + BplusNode* const node = tree->root; + BplusNode* const root = bplus_node_new(tree); + bplus_key_first(root) = bplus_key_first(node); + bplus_value_first(root) = node; + root->length = 1; + node->parent = root; + tree->root = root; + tree->height++; +} + +static int bplus_rebalance_try_merge(BplusTree* tree, BplusNode* node, size_t const index) +{ + g_return_val_if_fail(tree != NULL, 0); + g_return_val_if_fail(node != NULL, 0); + + BplusNode* node_left; + BplusNode* node_right; + if (!bplus_node_find_merge_candidate(tree, index, node, &node_left, &node_right)) + return 0; + + size_t const index_right = (node == node_left) ? index + 1 : index; + bplus_rebalance_data(tree, node_left, node_right); + + if (node_right->length == 0) + { + bplus_node_remove_at(tree, node->parent, index_right, 1); + bplus_node_destroy(tree, node_right); + } + else + { + bplus_key_at(node->parent, index_right) = bplus_key_first(node_right); + } + + return 1; +} + +void bplus_rebalance_overfilled(BplusTree* tree, BplusPath const* path) +{ + g_return_if_fail(tree != NULL); + g_return_if_fail(path != NULL); + + BplusNode* node = (BplusNode*) path->leaf; + for (size_t i = 1; i < path->length; ++i) + { + if (!bplus_node_overfilled(node)) + break; + + size_t const index = path->index[i]; + if (!bplus_rebalance_try_merge(tree, node, index)) + bplus_rebalance_split_node(tree, node, index); + + node = node->parent; + } + + if (bplus_node_overfilled(node)) + { + bplus_rebalance_new_root(tree); + bplus_rebalance_split_node(tree, node, 0); + } +} + +static void bplus_rebalance_shrink_tree(BplusTree* tree) +{ + g_return_if_fail(tree != NULL); + g_return_if_fail(tree->root != NULL); + + size_t i = 0; + for (; i < tree->height; ++i) + { + if (tree->root->length != 1) + break; + if (tree->root->is_leaf) + break; + + BplusNode* node = tree->root; + tree->root = bplus_node_first(tree->root); + tree->root->parent = NULL; + node->length = 0; + bplus_node_destroy(tree, node); + } + + tree->height -= i; +} + +void bplus_rebalance_underfilled(BplusTree* tree, BplusPath const* path) +{ + g_return_if_fail(tree != NULL); + g_return_if_fail(path != NULL); + + BplusNode* node = (BplusNode*) path->leaf; + for (size_t i = 1; i < path->length; ++i) + { + if (!bplus_node_underfilled(node)) + break; + + size_t const index = path->index[i]; + if (!bplus_rebalance_try_merge(tree, node, index) && (node->length == 0)) + { + bplus_node_remove_at(tree, node->parent, index, 1); + bplus_node_destroy(tree, node); + } + + node = node->parent; + } + + bplus_rebalance_shrink_tree(tree); +} diff --git a/Algorithms/bplus-tree/src/bplus_rebalance.h b/Algorithms/bplus-tree/src/bplus_rebalance.h new file mode 100644 index 0000000..3872f4d --- /dev/null +++ b/Algorithms/bplus-tree/src/bplus_rebalance.h @@ -0,0 +1,24 @@ +/** + * Distributed under the Boost Software License, Version 1.0. + * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt + */ + +#ifndef __BPLUS_REBALANCE_H__ +#define __BPLUS_REBALANCE_H__ + +#include "bplus_tree_private.h" + +#ifdef __cplusplus +extern "C" +{ +#endif // ifdef __cplusplus + +void bplus_rebalance_propagate(BplusTree const* tree, BplusPath* path); +void bplus_rebalance_overfilled(BplusTree* tree, BplusPath const* path); +void bplus_rebalance_underfilled(BplusTree* tree, BplusPath const* path); + +#ifdef __cplusplus +} +#endif // ifdef __cplusplus + +#endif // ifndef __BPLUS_REBALANCE_H__ diff --git a/Algorithms/bplus-tree/src/bplus_remove.c b/Algorithms/bplus-tree/src/bplus_remove.c new file mode 100644 index 0000000..9265ce1 --- /dev/null +++ b/Algorithms/bplus-tree/src/bplus_remove.c @@ -0,0 +1,60 @@ +/** + * Distributed under the Boost Software License, Version 1.0. + * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt + */ + +#include "bplus_remove.h" + +#include "bplus_node.h" +#include "bplus_search.h" +#include "bplus_rebalance.h" + +void bplus_node_remove_at(BplusTree const* tree, BplusNode* node, size_t const index, size_t const length) +{ + g_return_if_fail(node != NULL); + g_return_if_fail(index < node->length); + g_return_if_fail(index + length <= node->length); + + bplus_node_move_and_resize_data(tree, node, index, index + length); +} + +BplusValue bplus_tree_remove_first(BplusTree* tree) +{ + BplusPath path = { .leaf = (BplusNode*) tree->first }; + BplusNode* node = (BplusNode*) path.leaf; + size_t const index = path.index[0]; + + BplusValue value = bplus_value_at(node, 0); + bplus_node_remove_at(tree, node, index, 1); + if (index == 0) + bplus_rebalance_propagate(tree, &path); + + if (bplus_node_underfilled(node)) + bplus_rebalance_underfilled(tree, &path); + + return value; +} + +BplusValue bplus_tree_remove(BplusTree* tree, BplusKey const key) +{ + BplusPath path; + bplus_tree_get_path_to_key(tree, key, &path); + + size_t const index = path.index[0]; + BplusNode* node = (BplusNode*) path.leaf; + + if (bplus_key_eq(tree, bplus_key_at(node, index), key)) + { + BplusValue value = bplus_value_at(node, index); + bplus_node_remove_at(tree, node, index, 1); + if (index == 0) + bplus_rebalance_propagate(tree, &path); + + if (bplus_node_underfilled(node)) + bplus_rebalance_underfilled(tree, &path); + + return value; + } + + return NULL; +} diff --git a/Algorithms/bplus-tree/src/bplus_remove.h b/Algorithms/bplus-tree/src/bplus_remove.h new file mode 100644 index 0000000..81b94d3 --- /dev/null +++ b/Algorithms/bplus-tree/src/bplus_remove.h @@ -0,0 +1,22 @@ +/** + * Distributed under the Boost Software License, Version 1.0. + * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt + */ + +#ifndef __BPLUS_REMOVE_H__ +#define __BPLUS_REMOVE_H__ + +#include "bplus_tree_private.h" + +#ifdef __cplusplus +extern "C" +{ +#endif // ifdef __cplusplus + +void bplus_node_remove_at(BplusTree const* tree, BplusNode* node, size_t const index, size_t const length); + +#ifdef __cplusplus +} +#endif // ifdef __cplusplus + +#endif // ifndef __BPLUS_REMOVE_H__ diff --git a/Algorithms/bplus-tree/src/bplus_search.c b/Algorithms/bplus-tree/src/bplus_search.c new file mode 100644 index 0000000..a1e7c3b --- /dev/null +++ b/Algorithms/bplus-tree/src/bplus_search.c @@ -0,0 +1,127 @@ +/** + * Distributed under the Boost Software License, Version 1.0. + * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt + */ + +#include "bplus_search.h" + +#include "bplus_node.h" +#include "bplus_leaf.h" + +#define bplus_node_get_key_index_op(operator_m, tree_m, node_m, key_m) \ + do \ + { \ + size_t index = 1; \ + while (index < (node_m)->length) \ + { \ + if (operator_m((tree_m), bplus_key_at(node_m, index), (key_m))) \ + break; \ + ++index; \ + } \ + \ + return --index; \ + } \ + while (0) + +static size_t bplus_node_get_key_index(BplusTree const* tree, BplusNode const* node, BplusKey const key) +{ + g_return_val_if_fail(tree != NULL, 0); + g_return_val_if_fail(node != NULL, 0); + + bplus_node_get_key_index_op(bplus_key_gt, tree, node, key); +} + +static size_t bplus_node_get_key_index_before(BplusTree const* tree, BplusNode const* node, BplusKey const key) +{ + g_return_val_if_fail(tree != NULL, 0); + g_return_val_if_fail(node != NULL, 0); + + bplus_node_get_key_index_op(bplus_key_gte, tree, node, key); +} + +#define bplus_tree_get_path_to_key_op(operator_m, tree_m, key_m, path_m) \ + do \ + { \ + if (__builtin_expect(((tree_m)->root->length == 0), 0)) \ + { \ + (path_m)->length = 1; \ + (path_m)->index[0] = 0; \ + (path_m)->leaf = tree->root; \ + return; \ + } \ + \ + BplusNode const* node = (tree_m)->root; \ + size_t const length = (tree_m)->height; \ + for (size_t i = length; i > 0; --i) \ + { \ + for (int i = 0; i < BPLUS_TREE_ORDER * sizeof(*node->items) / 64; ++i) \ + { \ + __builtin_prefetch(node->items + i * 64 / sizeof(*node->items)); \ + } \ + \ + size_t const index = operator_m((tree_m), node, (key_m)); \ + (path_m)->index[i - 1] = index; \ + \ + if (i == 1) \ + break; \ + \ + node = bplus_node_at(node, index); \ + } \ + \ + (path_m)->length = length; \ + (path_m)->leaf = (BplusNode*) node; \ + } \ + while (0) + +void bplus_tree_get_path_to_key(BplusTree const* tree, BplusKey const key, BplusPath* path) +{ + g_return_if_fail(tree != NULL); + g_assert(tree->height < sizeof((path)->index) / sizeof(*(path)->index)); + + bplus_tree_get_path_to_key_op(bplus_node_get_key_index, tree, key, path); +} + +static void bplus_tree_get_path_to_key_before(BplusTree const* tree, BplusKey const key, BplusPath* path) +{ + g_return_if_fail(tree != NULL); + g_assert(tree->height < sizeof((path)->index) / sizeof(*(path)->index)); + + bplus_tree_get_path_to_key_op(bplus_node_get_key_index_before, tree, key, path); +} + +void bplus_tree_get_paths_to_key_range(BplusTree const* tree, BplusKey key_from, BplusKey key_to, BplusPath* path_from, BplusPath* path_to) +{ + g_return_if_fail(tree != NULL); + g_assert(tree->height < sizeof((path_from)->index) / sizeof(*(path_from)->index)); + g_assert(tree->height < sizeof((path_to)->index) / sizeof(*(path_to)->index)); + + if (bplus_key_gt(tree, key_from, key_to)) + { + BplusKey tmp = key_to; + key_to = key_from; + key_from = tmp; + } + + bplus_tree_get_path_to_key(tree, key_to, path_to); + if (!bplus_key_gt(tree, bplus_key_at(path_to->leaf, path_to->index[0]), key_to)) + path_to->index[0]++; + + bplus_tree_get_path_to_key_before(tree, key_from, path_from); + if (!bplus_key_gte(tree, bplus_key_at(path_from->leaf, path_from->index[0]), key_from)) + path_from->index[0]++; + + BplusLeaf const* const leaf = (BplusLeaf*) path_from->leaf; + if (path_from->index[0] == leaf->node.length) + { + if (leaf->right == NULL) + { + path_from->leaf = path_to->leaf; + path_from->index[0] = path_to->index[0]; + } + else + { + path_from->leaf = (BplusNode*) leaf->right; + path_from->index[0] = 0; + } + } +} diff --git a/Algorithms/bplus-tree/src/bplus_search.h b/Algorithms/bplus-tree/src/bplus_search.h new file mode 100644 index 0000000..3e76a39 --- /dev/null +++ b/Algorithms/bplus-tree/src/bplus_search.h @@ -0,0 +1,23 @@ +/** + * Distributed under the Boost Software License, Version 1.0. + * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt + */ + +#ifndef __BPLUS_SEARCH_H__ +#define __BPLUS_SEARCH_H__ + +#include "bplus_tree_private.h" + +#ifdef __cplusplus +extern "C" +{ +#endif // ifdef __cplusplus + +void bplus_tree_get_path_to_key(BplusTree const* tree, BplusKey const key, BplusPath* path); +void bplus_tree_get_paths_to_key_range(BplusTree const* tree, BplusKey key_from, BplusKey key_to, BplusPath* path_from, BplusPath* path_to); + +#ifdef __cplusplus +} +#endif // ifdef __cplusplus + +#endif // ifndef __BPLUS_SEARCH_H__ diff --git a/Algorithms/bplus-tree/src/bplus_tree.c b/Algorithms/bplus-tree/src/bplus_tree.c new file mode 100644 index 0000000..fc8bb8e --- /dev/null +++ b/Algorithms/bplus-tree/src/bplus_tree.c @@ -0,0 +1,202 @@ +/** + * Distributed under the Boost Software License, Version 1.0. + * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt + */ + +#include "bplus_tree_private.h" + +#include "bplus_leaf.h" +#include "bplus_search.h" +#include "bplus_iterator.h" +#include "bplus_foreach.h" + +#include <stdint.h> +#include <stdlib.h> +#include <string.h> +#include <stdarg.h> +#include <stdio.h> + +int bplus_tree_print(BplusTree const* const tree, char const* format, ...) __attribute__((format(printf, 2, 3))); + +BplusTree* bplus_tree_new() +{ + return bplus_tree_new_full(1); +} + +BplusTree* bplus_tree_new_full(gboolean allow_duplicate_keys) +{ + BplusTree* tree = malloc(sizeof(BplusTree)); + + tree->first = bplus_leaf_new(tree); + tree->last = tree->first; + tree->root = (BplusNode*) tree->first; + + tree->height = 1; + tree->allow_duplicate_keys = allow_duplicate_keys; + + return tree; +} + +void bplus_tree_print_stats(BplusTree* tree); + +static void bplus_foreach_node_destroy(BplusTree* tree, BplusNode* node, void* argument) +{ + bplus_node_destroy(tree, node); +} + +void bplus_tree_destroy(BplusTree* tree) +{ + g_return_if_fail(tree != NULL); + +#ifdef BPLUS_TREE_GATHER_STATS + bplus_tree_print_stats(tree); +#endif /* ifdef BPLUS_TREE_GATHER_STATS */ + + bplus_foreach_node_in_tree(tree, &bplus_foreach_node_destroy, NULL); + free(tree); +} + +void bplus_tree_destroy_each(BplusTree* tree, BplusForeachItemFunc* foreach, void* argument) +{ + bplus_foreach_item_in_tree(tree, foreach, argument); + bplus_tree_destroy(tree); +} + +#ifdef BPLUS_TREE_GATHER_STATS + +void bplus_tree_print_stats(BplusTree* tree) +{ + printf("tree height: %zu\n", tree->height); + printf("node count: %zu\n", tree->node_count); + printf("leaf count: %zu\n", tree->leaf_count); + printf("underflow count: %zu\n", tree->underflow_count); + printf("overflow count: %zu\n", tree->overflow_count); +} + +#endif /* ifdef BPLUS_TREE_GATHER_STATS */ + +BplusValue bplus_tree_get(BplusTree* tree, BplusKey key) +{ + BplusPath path; + bplus_tree_get_path_to_key(tree, key, &path); + + size_t const index = path.index[0]; + BplusNode const* node = path.leaf; + BplusValue value = NULL; + + if ((index < node->length) && bplus_key_eq(tree, bplus_key_at(node, index), key)) + value = bplus_value_at(node, index); + + return value; +} + +BplusValue bplus_tree_get_first(BplusTree const* tree) +{ + if (tree->first->node.length == 0) + return NULL; + + return tree->first->node.items[0].value; +} + +BplusValue bplus_tree_get_nth(BplusTree const* tree, size_t position) +{ + BplusLeaf* leaf = tree->first; + if (leaf->node.length == 0) + return NULL; + + while (leaf != NULL && position >= leaf->node.length) + { + position -= leaf->node.length; + leaf = leaf->right; + } + + if (leaf != NULL) + return leaf->node.items[position].value; + + return NULL; +} + +void bplus_value_print(BplusNode* node, size_t const index, BplusKey key, BplusValue value, int depth) +{ + static char const* indent = " "; + + fprintf(stderr, "%*.s n%p_%zu[label=\"%lu\",fontcolor=\"#000099\"];", 0, indent, node, index, key); + fprintf(stderr, "%*.s n%p->n%p_%zu;", 0, indent, node, node, index); +} + +void bplus_node_print(BplusNode* parent, BplusKey key, BplusNode* node, int depth) +{ + static char const* indent = " "; + + fprintf(stderr, "%*.s n%p[label=\"%lu\"];", 0, indent, node, key); + fprintf(stderr, "%*.s n%p->n%p;", 0, indent, parent, node); + + if (node->is_leaf) + { + if (((BplusLeaf*) node)->right != NULL) + fprintf(stderr, "n%p->n%p[constraint=false];", node, ((BplusLeaf*) node)->right); + if (((BplusLeaf*) node)->left != NULL) + fprintf(stderr, "n%p->n%p[constraint=false];", node, ((BplusLeaf*) node)->left); + } + + for (size_t i = 0; i < node->length; ++i) + { + if (node->is_leaf) + bplus_value_print(node, i, bplus_key_at(node, i), bplus_value_at(node, i), 2); + else + bplus_node_print(node, bplus_key_at(node, i), bplus_node_at(node, i), depth + 2); + + } +} + +int bplus_tree_print(BplusTree const* const tree, char const* format, ...) +{ + static int count = 0; + + fprintf(stderr, "echo 'digraph {"); + fprintf(stderr, "graph[ordering=\"out\"];\n"); + fprintf(stderr, "node[width=0.2,height=0.2,fixedsize=true,fontsize=6,fontcolor=\"#990000\",shape=plaintext];"); + fprintf(stderr, "edge[arrowsize=0.1,fontsize=6];"); + + BplusNode* node = tree->root; + fprintf(stderr, "n%p[label=\"0\"];", node); + if (node->is_leaf) + { + if (((BplusLeaf*) node)->right != NULL) + fprintf(stderr, "n%p->n%p[constraint=false];", node, ((BplusLeaf*) node)->right); + if (((BplusLeaf*) node)->left != NULL) + fprintf(stderr, "n%p->n%p[constraint=false];", node, ((BplusLeaf*) node)->left); + } + + for (size_t i = 0; i < node->length; ++i) + { + if (node->is_leaf) + bplus_value_print(node, i, bplus_key_at(node, i), bplus_value_at(node, i), 2); + else + bplus_node_print(node, bplus_key_at(node, i), bplus_node_at(node, i), 2); + + } + + va_list vargs; + va_start(vargs, format); + vfprintf(stderr, format, vargs); + va_end(vargs); + + fprintf(stderr, "}'| dot -T png -o tree-%d.png\n", count); + count++; + return 0; +} + +int bplus_iterator_print(BplusTree const* tree, BplusIterator const* iterator) +{ + bplus_tree_print(tree, + "label=\"iterator\"; i[fontcolor=\"#009900\",label=\"i\"];" + "n%p_%zu->i[label=\"from\"];" + "n%p_%zu->i[color=\"#009900\"];" + "n%p_%zu->i[label=\"to\"];", + iterator->leaf_from, iterator->item_from - iterator->leaf_from->node.items, + iterator->leaf, iterator->item - iterator->leaf->node.items, + iterator->leaf_to, iterator->item_to - iterator->leaf_to->node.items - 1); + + return 0; +} diff --git a/Algorithms/bplus-tree/src/bplus_tree_private.h b/Algorithms/bplus-tree/src/bplus_tree_private.h new file mode 100644 index 0000000..97b873f --- /dev/null +++ b/Algorithms/bplus-tree/src/bplus_tree_private.h @@ -0,0 +1,53 @@ +/** + * Distributed under the Boost Software License, Version 1.0. + * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt + */ + +#ifndef __BPLUS_TREE_PRIVATE_H__ +#define __BPLUS_TREE_PRIVATE_H__ + +#include "bplus_tree.h" + +#ifdef __cplusplus +extern "C" +{ +#endif // ifdef __cplusplus + +#ifndef BPLUS_TREE_ORDER +# define BPLUS_TREE_ORDER 32 +#endif /* ifndef BPLUS_TREE_ORDER */ + +typedef struct _BplusNode BplusNode; +typedef struct _BplusLeaf BplusLeaf; +typedef struct _BplusPath BplusPath; + +struct _BplusPath +{ + size_t length; + size_t index[16]; + BplusNode* leaf; +}; + +struct _BplusTree +{ + BplusNode* root; + + BplusLeaf* first; + BplusLeaf* last; + + size_t height; + gboolean allow_duplicate_keys; + +#ifdef BPLUS_TREE_GATHER_STATS + size_t node_count; + size_t leaf_count; + size_t underflow_count; + size_t overflow_count; +#endif /* ifdef BPLUS_TREE_GATHER_STATS */ +}; + +#ifdef __cplusplus +} +#endif // ifdef __cplusplus + +#endif // ifndef __BPLUS_TREE_PRIVATE_H__ diff --git a/Algorithms/bplus-tree/test/bplus_tree_all.c b/Algorithms/bplus-tree/test/bplus_tree_all.c new file mode 100644 index 0000000..1186dc8 --- /dev/null +++ b/Algorithms/bplus-tree/test/bplus_tree_all.c @@ -0,0 +1,14 @@ +/** + * Distributed under the Boost Software License, Version 1.0. + * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt + */ + +#include "bplus_tree.c" +#include "bplus_search.c" +#include "bplus_remove.c" +#include "bplus_rebalance.c" +#include "bplus_node.c" +#include "bplus_leaf.c" +#include "bplus_iterator.c" +#include "bplus_insert.c" +#include "bplus_foreach.c" diff --git a/Algorithms/bplus-tree/test/bplus_tree_test.c b/Algorithms/bplus-tree/test/bplus_tree_test.c new file mode 100644 index 0000000..5ddd69f --- /dev/null +++ b/Algorithms/bplus-tree/test/bplus_tree_test.c @@ -0,0 +1,560 @@ +/** + * Distributed under the Boost Software License, Version 1.0. + * See accompanying file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt + */ + +#ifndef BPLUS_TREE_ORDER +# define BPLUS_TREE_ORDER 4 +#endif /* ifndef BPLUS_TREE_ORDER */ + +#include "bplus_tree_all.c" + +void test_search_key_index(void) +{ + BplusTree tree; + BplusNode node; + + node.length = 0; + g_assert(bplus_node_get_key_index(&tree, &node, 0) == 0); + g_assert(bplus_node_get_key_index(&tree, &node, 0xFF) == 0); + + g_assert(bplus_node_get_key_index(&tree, &node, 0) == 0); + g_assert(bplus_node_get_key_index(&tree, &node, 0xFF) == 0); + + bplus_key_at(&node, 0) = 1; + node.length++; + g_assert(bplus_node_get_key_index(&tree, &node, 0) == 0); + g_assert(bplus_node_get_key_index(&tree, &node, 1) == 0); + g_assert(bplus_node_get_key_index(&tree, &node, 2) == 0); + g_assert(bplus_node_get_key_index(&tree, &node, 0xFF) == 0); + + bplus_key_at(&node, 0) = 1; + bplus_key_at(&node, 1) = 1; + node.length++; + g_assert(bplus_node_get_key_index(&tree, &node, 0) == 0); + g_assert(bplus_node_get_key_index(&tree, &node, 1) == 1); + g_assert(bplus_node_get_key_index(&tree, &node, 2) == 1); + g_assert(bplus_node_get_key_index(&tree, &node, 0xFF) == 1); + + bplus_key_at(&node, 0) = 1; + bplus_key_at(&node, 1) = 1; + bplus_key_at(&node, 2) = 2; + node.length++; + g_assert(bplus_node_get_key_index(&tree, &node, 0) == 0); + g_assert(bplus_node_get_key_index(&tree, &node, 1) == 1); + g_assert(bplus_node_get_key_index(&tree, &node, 2) == 2); + g_assert(bplus_node_get_key_index(&tree, &node, 3) == 2); + g_assert(bplus_node_get_key_index(&tree, &node, 0xFF) == 2); + + bplus_key_at(&node, 0) = 1; + bplus_key_at(&node, 1) = 1; + bplus_key_at(&node, 2) = 3; + bplus_key_at(&node, 3) = 3; + node.length++; + g_assert(bplus_node_get_key_index(&tree, &node, 0) == 0); + g_assert(bplus_node_get_key_index(&tree, &node, 1) == 1); + g_assert(bplus_node_get_key_index(&tree, &node, 2) == 1); + g_assert(bplus_node_get_key_index(&tree, &node, 3) == 3); + g_assert(bplus_node_get_key_index(&tree, &node, 4) == 3); + g_assert(bplus_node_get_key_index(&tree, &node, 0xFF) == 3); + + bplus_key_at(&node, 0) = 1; + bplus_key_at(&node, 1) = 1; + bplus_key_at(&node, 2) = 1; + bplus_key_at(&node, 3) = 1; + g_assert(bplus_node_get_key_index(&tree, &node, 0) == 0); + g_assert(bplus_node_get_key_index(&tree, &node, 1) == 3); + g_assert(bplus_node_get_key_index(&tree, &node, 2) == 3); + g_assert(bplus_node_get_key_index(&tree, &node, 3) == 3); + g_assert(bplus_node_get_key_index(&tree, &node, 4) == 3); + g_assert(bplus_node_get_key_index(&tree, &node, 0xFF) == 3); + + // bplus_key_at(&node, 0) = 1; + // bplus_key_at(&node, 1) = 2; + // bplus_key_at(&node, 2) = 3; + // bplus_key_at(&node, 3) = 4; + // bplus_key_at(&node, 4) = 4; + // bplus_key_at(&node, 5) = 4; + // bplus_key_at(&node, 6) = 6; + // bplus_key_at(&node, 7) = 6; + // bplus_key_at(&node, 8) = 9; + // node.length = 9; + // g_assert(bplus_node_get_key_index(&tree, &node, 0) == 0); + // g_assert(bplus_node_get_key_index(&tree, &node, 1) == 0); + // g_assert(bplus_node_get_key_index(&tree, &node, 2) == 1); + // g_assert(bplus_node_get_key_index(&tree, &node, 3) == 2); + // g_assert(bplus_node_get_key_index(&tree, &node, 4) == 5); + // g_assert(bplus_node_get_key_index(&tree, &node, 0xFF) == 8); +} /* test_search_key_index */ + +void test_search_bplus_tree_new(void) +{ + BplusTree* tree = bplus_tree_new(); + + g_assert(tree != NULL); + g_assert(tree->root != NULL); + g_assert((void*) tree->root == (void*) tree->first); + g_assert((void*) tree->root == (void*) tree->last); + + g_assert(tree->root->is_leaf); + g_assert(tree->root->parent == NULL); + g_assert(tree->root->length == 0); + + g_assert(tree->first->left == NULL); + g_assert(tree->first->right == NULL); + + bplus_tree_destroy(tree); +} + +void test_search_bplus_node_insert_at(void) +{ + // BplusTree* tree = bplus_tree_new(); + + // bplus_node_insert_at(tree, tree->root, 0, 0, (void*) 1); + + // g_assert(tree->root->is_leaf); + // g_assert(tree->root->parent == NULL); + // g_assert(tree->root->length == 1); + + // g_assert(bplus_key_first(tree->root) == 0); + // g_assert(bplus_value_first(tree->root) == (void*) 1); + + // bplus_node_insert_at(tree, tree->root, 0, 0, (void*) 2); + // bplus_node_insert_at(tree, tree->root, 0, 0, (void*) 3); + + // g_assert(bplus_value_first(tree->root) == (void*) 3); + // g_assert(bplus_value_at(tree->root, 1) == (void*) 2); + // g_assert(bplus_value_at(tree->root, 2) == (void*) 1); + + // bplus_node_insert_at(tree, tree->root, 0, 0, (void*) 4); + + // /* We should have splitted here */ + // g_assert(!tree->root->is_leaf); + // g_assert(tree->root->parent == NULL); + // g_assert(tree->root->length == 2); + + // g_assert(bplus_key_first(tree->root) == 0); + // BplusNode* left = (BplusNode*) bplus_value_first(tree->root); + // g_assert(left != NULL); + + // g_assert(bplus_key_at(tree->root, 1) == 0); + // BplusNode* right = (BplusNode*) bplus_value_at(tree->root, 1); + // g_assert(right != NULL); + + // g_assert(left->is_leaf); + // g_assert(left->parent == tree->root); + // g_assert(left->length == 2); + // g_assert(bplus_key_first(left) == 0); + // g_assert(bplus_value_first(left) == (void*) 4); + // g_assert(bplus_key_at(left, 1) == 0); + // g_assert(bplus_value_at(left, 1) == (void*) 3); + + // g_assert(right->is_leaf); + // g_assert(right->parent == tree->root); + // g_assert(right->length == 2); + // g_assert(bplus_key_first(right) == 0); + // g_assert(bplus_value_first(right) == (void*) 2); + // g_assert(bplus_key_at(right, 1) == 0); + // g_assert(bplus_value_at(right, 1) == (void*) 1); + + // bplus_node_insert_at(tree, left, 2, 0, (void*) 1); + // bplus_node_insert_at(tree, left, 2, 0, (void*) 2); + + // g_assert(tree->root->length == 3); + + // g_assert(bplus_key_at(tree->root, 1) == 0); + // BplusNode* middle = (BplusNode*) bplus_value_at(tree->root, 1); + // g_assert(middle != NULL); + // g_assert(middle != left); + // g_assert(middle != right); + + // g_assert(bplus_key_first(tree->root) == 0); + // g_assert(bplus_value_first(tree->root) == left); + // g_assert(bplus_key_at(tree->root, 1) == 0); + // g_assert(bplus_value_at(tree->root, 1) == middle); + // g_assert(bplus_key_at(tree->root, 2) == 0); + // g_assert(bplus_value_at(tree->root, 2) == right); + + // g_assert(middle->is_leaf); + // g_assert(middle->parent == tree->root); + // g_assert(middle->length == 2); + // g_assert(bplus_key_first(middle) == 0); + // g_assert(bplus_value_first(middle) == (void*) 2); + // g_assert(bplus_key_at(middle, 1) == 0); + // g_assert(bplus_value_at(middle, 1) == (void*) 1); + + // g_assert(tree->first == (BplusLeaf*) left); + // g_assert(tree->last == (BplusLeaf*) right); + // g_assert(((BplusLeaf*) left)->right == (BplusLeaf*) middle); + // g_assert(((BplusLeaf*) right)->left == (BplusLeaf*) middle); + // g_assert(((BplusLeaf*) left)->left == NULL); + // g_assert(((BplusLeaf*) right)->right == NULL); + // g_assert(((BplusLeaf*) middle)->left == (BplusLeaf*) left); + // g_assert(((BplusLeaf*) middle)->right == (BplusLeaf*) right); + + // bplus_tree_destroy(tree); +} /* test_search_bplus_node_insert_at */ + +void test_search_bplus_tree_insert_k0(void) +{ + BplusTree* tree = bplus_tree_new(); + + bplus_tree_insert(tree, 0, (void*) 1); + + g_assert(tree->root->is_leaf); + g_assert(tree->root->parent == NULL); + g_assert(tree->root->length == 1); + + g_assert(bplus_key_first(tree->root) == 0); + g_assert(bplus_value_first(tree->root) == (void*) 1); + + bplus_tree_insert(tree, 0, (void*) 2); + bplus_tree_insert(tree, 0, (void*) 3); + + g_assert(bplus_value_first(tree->root) == (void*) 1); + g_assert(bplus_value_at(tree->root, 1) == (void*) 2); + g_assert(bplus_value_at(tree->root, 2) == (void*) 3); + + bplus_tree_insert(tree, 0, (void*) 4); + + /* We should have splitted here */ + g_assert(!tree->root->is_leaf); + g_assert(tree->root->parent == NULL); + g_assert(tree->root->length == 2); + + g_assert(bplus_key_first(tree->root) == 0); + BplusNode* left = (BplusNode*) bplus_value_first(tree->root); + g_assert(left != NULL); + + g_assert(bplus_key_at(tree->root, 1) == 0); + BplusNode* right = (BplusNode*) bplus_value_at(tree->root, 1); + g_assert(right != NULL); + + g_assert(left->is_leaf); + g_assert(left->parent == tree->root); + g_assert(left->length == 2); + g_assert(bplus_key_first(left) == 0); + g_assert(bplus_value_first(left) == (void*) 1); + g_assert(bplus_key_at(left, 1) == 0); + g_assert(bplus_value_at(left, 1) == (void*) 2); + + g_assert(right->is_leaf); + g_assert(right->parent == tree->root); + g_assert(right->length == 2); + g_assert(bplus_key_first(right) == 0); + g_assert(bplus_value_first(right) == (void*) 3); + g_assert(bplus_key_at(right, 1) == 0); + g_assert(bplus_value_at(right, 1) == (void*) 4); + + bplus_tree_insert(tree, 0, (void*) 5); + bplus_tree_insert(tree, 0, (void*) 6); + + g_assert(tree->root->length == 3); + + g_assert(bplus_key_at(tree->root, 2) == 0); + BplusNode* middle = right; + right = (BplusNode*) bplus_value_at(tree->root, 2); + g_assert(middle != NULL); + g_assert(middle != left); + g_assert(middle != right); + + g_assert(bplus_key_first(tree->root) == 0); + g_assert(bplus_value_first(tree->root) == left); + g_assert(bplus_key_at(tree->root, 1) == 0); + g_assert(bplus_value_at(tree->root, 1) == middle); + g_assert(bplus_key_at(tree->root, 2) == 0); + g_assert(bplus_value_at(tree->root, 2) == right); + + g_assert(right->is_leaf); + g_assert(right->parent == tree->root); + g_assert(right->length == 2); + g_assert(bplus_key_first(right) == 0); + g_assert(bplus_value_first(right) == (void*) 5); + g_assert(bplus_key_at(right, 1) == 0); + g_assert(bplus_value_at(right, 1) == (void*) 6); + + g_assert(tree->first == (BplusLeaf*) left); + g_assert(tree->last == (BplusLeaf*) right); + g_assert(((BplusLeaf*) left)->right == (BplusLeaf*) middle); + g_assert(((BplusLeaf*) right)->left == (BplusLeaf*) middle); + g_assert(((BplusLeaf*) left)->left == NULL); + g_assert(((BplusLeaf*) right)->right == NULL); + g_assert(((BplusLeaf*) middle)->left == (BplusLeaf*) left); + g_assert(((BplusLeaf*) middle)->right == (BplusLeaf*) right); + + bplus_tree_destroy(tree); +} /* test_search_bplus_tree_insert_k0 */ + +void test_search_bplus_tree_insert_k(void) +{ + BplusTree* tree = bplus_tree_new(); + + bplus_tree_insert(tree, 3, (void*) 1); + + g_assert(tree->root->is_leaf); + g_assert(tree->root->parent == NULL); + g_assert(tree->root->length == 1); + + g_assert(bplus_key_first(tree->root) == 3); + g_assert(bplus_value_first(tree->root) == (void*) 1); + + bplus_tree_insert(tree, 1, (void*) 2); + g_assert(bplus_value_first(tree->root) == (void*) 2); + g_assert(bplus_value_at(tree->root, 1) == (void*) 1); + + bplus_tree_insert(tree, 2, (void*) 3); + + g_assert(bplus_value_first(tree->root) == (void*) 2); + g_assert(bplus_value_at(tree->root, 1) == (void*) 3); + g_assert(bplus_value_at(tree->root, 2) == (void*) 1); + + bplus_tree_insert(tree, 2, (void*) 4); + + /* We should have splitted here */ + g_assert(!tree->root->is_leaf); + g_assert(tree->root->parent == NULL); + g_assert(tree->root->length == 2); + + g_assert(bplus_key_first(tree->root) == 1); + BplusNode* left = (BplusNode*) bplus_value_first(tree->root); + g_assert(left != NULL); + + g_assert(bplus_key_at(tree->root, 1) == 2); + BplusNode* right = (BplusNode*) bplus_value_at(tree->root, 1); + g_assert(right != NULL); + + g_assert(left->is_leaf); + g_assert(left->parent == tree->root); + g_assert(left->length == 2); + g_assert(bplus_key_first(left) == 1); + g_assert(bplus_value_first(left) == (void*) 2); + g_assert(bplus_key_at(left, 1) == 2); + g_assert(bplus_value_at(left, 1) == (void*) 3); + + g_assert(right->is_leaf); + g_assert(right->parent == tree->root); + g_assert(right->length == 2); + g_assert(bplus_key_first(right) == 2); + g_assert(bplus_value_first(right) == (void*) 4); + g_assert(bplus_key_at(right, 1) == 3); + g_assert(bplus_value_at(right, 1) == (void*) 1); + + g_assert(bplus_key_first(tree->root) == 1); + g_assert(bplus_key_at(tree->root, 1) == 2); + + bplus_tree_insert(tree, 3, (void*) 5); + bplus_tree_insert(tree, 3, (void*) 6); + g_assert(tree->root->length == 3); + + /* Should not have splitted */ + g_assert(bplus_value_first(tree->root) == (void*) left); + g_assert(bplus_value_at(tree->root, 1) == (void*) right); + + bplus_tree_insert(tree, 2, (void*) 7); + g_assert(tree->root->length == 3); + g_assert(bplus_key_first(tree->root) == 1); + g_assert(bplus_key_at(tree->root, 1) == 2); + g_assert(bplus_key_at(tree->root, 2) == 3); + + // /* Should split root again */ + // bplus_tree_insert(tree, 4, (void*) 8); + // g_assert(tree->root->length == 3); + // g_assert(bplus_value_first(tree->root) != (void*) left); + // g_assert(bplus_value_at(tree->root, 1) != (void*) right); + + // g_assert(bplus_key_first(tree->root) == 1); + // g_assert(bplus_key_at(tree->root, 1) == 3); + + /* This should propagate 0 up to root */ + bplus_tree_insert(tree, 0, (void*) 9); + g_assert((bplus_key_first(tree->root) == 0)); + + // for (int i = 0; i < 10000; ++i) { + // bplus_tree_insert(tree, random(), (void*) i + 1); + // } + + bplus_tree_destroy(tree); +} /* test_search_bplus_tree_insert_k */ + +void test_search_bplus_tree_remove_k(void) +{ + BplusTree* tree = bplus_tree_new(); + + bplus_tree_insert(tree, 3, (void*) 1); + bplus_tree_insert(tree, 1, (void*) 2); + bplus_tree_insert(tree, 2, (void*) 3); + bplus_tree_insert(tree, 2, (void*) 4); + bplus_tree_insert(tree, 3, (void*) 5); + bplus_tree_insert(tree, 3, (void*) 6); + bplus_tree_insert(tree, 2, (void*) 7); + bplus_tree_insert(tree, 4, (void*) 8); + bplus_tree_insert(tree, 0, (void*) 9); + + // bplus_tree_print(tree, "label=\"remove(0)\";"); + bplus_tree_remove(tree, 0); + + // bplus_tree_print(tree, "label=\"remove(1)\";"); + bplus_tree_remove(tree, 1); + + // bplus_tree_print(tree, "label=\"remove(4)\";"); + bplus_tree_remove(tree, 4); + + // bplus_tree_print(tree, "label=\"remove(3)\";"); + bplus_tree_remove(tree, 3); + + // bplus_tree_print(tree, "label=\"remove(2)\";"); + bplus_tree_remove(tree, 2); + + // bplus_tree_print(tree, "label=\"remove(3)\";"); + bplus_tree_remove(tree, 3); + + // bplus_tree_print(tree, "label=\"remove(3)\";"); + bplus_tree_remove(tree, 3); + + // bplus_tree_print(tree, "label=\"remove(2)\";"); + bplus_tree_remove(tree, 2); + + // bplus_tree_print(tree, "label=\"remove(2)\";"); + bplus_tree_remove(tree, 2); + + // bplus_tree_print(tree, ""); + + bplus_tree_destroy(tree); +} /* test_search_bplus_tree_insert_k */ + +void test_search_bplus_tree_iterator(void) +{ + BplusTree* tree = bplus_tree_new(); + + bplus_tree_insert(tree, 3, (void*) 1); + bplus_tree_insert(tree, 1, (void*) 2); + bplus_tree_insert(tree, 2, (void*) 3); + bplus_tree_insert(tree, 2, (void*) 4); + bplus_tree_insert(tree, 3, (void*) 5); + bplus_tree_insert(tree, 3, (void*) 6); + bplus_tree_insert(tree, 2, (void*) 7); + bplus_tree_insert(tree, 4, (void*) 8); + bplus_tree_insert(tree, 0, (void*) 9); + + BplusKey keys[] = { 0, 1, 2, 2, 2, 3, 3, 3, 4 }; + BplusValue values[] = { (BplusValue*) 9, (BplusValue*) 2, (BplusValue*) 3, (BplusValue*) 4, (BplusValue*) 7, (BplusValue*) 1, (BplusValue*) 5, (BplusValue*) 6, (BplusValue*) 8 }; + + BplusIterator* iterator = bplus_tree_first(tree); + for (int i = 0; i < 9; ++i) + { + BplusItem const* item = bplus_iterator_get_item(iterator); + g_assert(item->key == keys[i]); + g_assert(item->value == values[i]); + if (i < 8) + bplus_iterator_next(iterator); + } + g_assert(!bplus_iterator_next(iterator)); + bplus_iterator_destroy(iterator); + + iterator = bplus_iterator_to_key(tree, 2); + for (int i = 0; i < 5; ++i) + { + BplusItem const* item = bplus_iterator_get_item(iterator); + g_assert(item->key == keys[i]); + g_assert(item->value == values[i]); + if (i < 4) + bplus_iterator_next(iterator); + } + g_assert(!bplus_iterator_next(iterator)); + for (int i = 4; i >= 0; --i) + { + BplusItem const* item = bplus_iterator_get_item(iterator); + g_assert(item->key == keys[i]); + g_assert(item->value == values[i]); + if (i > 0) + bplus_iterator_previous(iterator); + } + g_assert(!bplus_iterator_previous(iterator)); + bplus_iterator_destroy(iterator); + + iterator = bplus_iterator_for_key(tree, 2); + for (int i = 0; i < 3; ++i) + { + BplusItem const* item = bplus_iterator_get_item(iterator); + g_assert(item->key == keys[i + 2]); + g_assert(item->value == values[i + 2]); + if (i < 2) + bplus_iterator_next(iterator); + } + g_assert(!bplus_iterator_next(iterator)); + bplus_iterator_destroy(iterator); + + iterator = bplus_iterator_from_key(tree, 2); + for (int i = 0; i < 7; ++i) + { + BplusItem const* item = bplus_iterator_get_item(iterator); + g_assert(item->key == keys[i + 2]); + g_assert(item->value == values[i + 2]); + if (i < 6) + bplus_iterator_next(iterator); + } + g_assert(!bplus_iterator_next(iterator)); + bplus_iterator_destroy(iterator); + + iterator = bplus_iterator_for_key_range(tree, 2, 3); + for (int i = 0; i < 6; ++i) + { + BplusItem const* item = bplus_iterator_get_item(iterator); + g_assert(item->key == keys[i + 2]); + g_assert(item->value == values[i + 2]); + if (i < 5) + bplus_iterator_next(iterator); + } + g_assert(!bplus_iterator_next(iterator)); + bplus_iterator_destroy(iterator); + + iterator = bplus_iterator_for_key_range(tree, 3, 2); + for (int i = 0; i < 6; ++i) + { + BplusItem const* item = bplus_iterator_get_item(iterator); + g_assert(item->key == keys[i + 2]); + g_assert(item->value == values[i + 2]); + if (i < 5) + bplus_iterator_next(iterator); + } + g_assert(!bplus_iterator_next(iterator)); + bplus_iterator_destroy(iterator); + + iterator = bplus_iterator_for_key_range(tree, 4, 5); + for (int i = 0; i < 1; ++i) + { + BplusItem const* item = bplus_iterator_get_item(iterator); + g_assert(item->key == keys[i + 8]); + g_assert(item->value == values[i + 8]); + } + g_assert(!bplus_iterator_next(iterator)); + bplus_iterator_destroy(iterator); + + iterator = bplus_iterator_for_key_range(tree, 5, 5); + g_assert(bplus_iterator_get_item(iterator) == NULL); + g_assert(!bplus_iterator_next(iterator)); + bplus_iterator_destroy(iterator); + + iterator = bplus_iterator_for_key_range(tree, 5, 6); + g_assert(bplus_iterator_get_item(iterator) == NULL); + g_assert(!bplus_iterator_next(iterator)); + bplus_iterator_destroy(iterator); + + bplus_tree_destroy(tree); +} /* test_search_bplus_tree_iterator */ + +int main(int argc, char** argv) +{ + g_test_init(&argc, &argv, NULL); + + g_test_add_func("/tree/search_key_index", test_search_key_index); + g_test_add_func("/tree/new", test_search_bplus_tree_new); + g_test_add_func("/tree/insert_at", test_search_bplus_node_insert_at); + g_test_add_func("/tree/insert_k0", test_search_bplus_tree_insert_k0); + g_test_add_func("/tree/insert_k", test_search_bplus_tree_insert_k); + g_test_add_func("/tree/remove_k", test_search_bplus_tree_remove_k); + g_test_add_func("/tree/iterator", test_search_bplus_tree_iterator); + + g_test_run(); + return 0; +} diff --git a/Algorithms/bpt.c b/Algorithms/bpt.c new file mode 100644 index 0000000..0e7e756 --- /dev/null +++ b/Algorithms/bpt.c @@ -0,0 +1,1471 @@ +/* + * bpt.c + */ +#define Version "1.14" +/* + * + * bpt: B+ Tree Implementation + * Copyright (C) 2010-2016 Amittai Aviram http://www.amittai.com + * All rights reserved. + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimer. + * + * 2. Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + + * 3. Neither the name of the copyright holder nor the names of its + * contributors may be used to endorse or promote products derived from this + * software without specific prior written permission. + + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + * POSSIBILITY OF SUCH DAMAGE. + + * Author: Amittai Aviram + * http://www.amittai.com + * Original Date: 26 June 2010 + * Last modified: 17 June 2016 + * + * This implementation demonstrates the B+ tree data structure + * for educational purposes, includin insertion, deletion, search, and display + * of the search path, the leaves, or the whole tree. + * + * Must be compiled with a C99-compliant C compiler such as the latest GCC. + * + * Usage: bpt [order] + * where order is an optional argument + * (integer MIN_ORDER <= order <= MAX_ORDER) + * defined as the maximal number of pointers in any node. + * + */ + +// Uncomment the line below if you are compiling on Windows. +// #define WINDOWS +#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. You may change the maximum order. +#define MIN_ORDER 3 +#define MAX_ORDER 20 + +// Constants for printing part or all of the GPL license. +#define LICENSE_FILE "LICENSE.txt" +#define LICENSE_WARRANTEE 0 +#define LICENSE_WARRANTEE_START 592 +#define LICENSE_WARRANTEE_END 624 +#define LICENSE_CONDITIONS 1 +#define LICENSE_CONDITIONS_START 70 +#define LICENSE_CONDITIONS_END 625 + +// TYPES. + +/* Type representing the record + * to which a given key refers. + * In a real B+ tree system, the + * record would hold data (in a database) + * or a file (in an operating system) + * or some other information. + * Users can rewrite this part of the code + * to change the type and content + * of the value field. + */ +typedef struct record { + int value; +} record; + +/* Type representing a node in the B+ tree. + * This type is general enough to serve for both + * the leaf and the internal node. + * The heart of the node is the array + * of keys and the array of corresponding + * pointers. The relation between keys + * and pointers differs between leaves and + * internal nodes. In a leaf, the index + * of each key equals the index of its corresponding + * pointer, with a maximum of order - 1 key-pointer + * pairs. The last pointer points to the + * leaf to the right (or NULL in the case + * of the rightmost leaf). + * In an internal node, the first pointer + * refers to lower nodes with keys less than + * the smallest key in the keys array. Then, + * with indices i starting at 0, the pointer + * at i + 1 points to the subtree with keys + * greater than or equal to the key in this + * node at index i. + * The num_keys field is used to keep + * track of the number of valid keys. + * In an internal node, the number of valid + * pointers is always num_keys + 1. + * In a leaf, the number of valid pointers + * to data is always num_keys. The + * last leaf pointer points to the next leaf. + */ +typedef struct node { + void ** pointers; + int * keys; + struct node * parent; + bool is_leaf; + int num_keys; + struct node * next; // Used for queue. +} node; + + +// GLOBALS. + +/* The order determines the maximum and minimum + * number of entries (keys and pointers) in any + * node. Every node has at most order - 1 keys and + * at least (roughly speaking) half that number. + * Every leaf has as many pointers to data as keys, + * and every internal node has one more pointer + * to a subtree than the number of keys. + * This global variable is initialized to the + * default value. + */ +int order = DEFAULT_ORDER; + +/* The queue is used to print the tree in + * level order, starting from the root + * printing each entire rank on a separate + * line, finishing with the leaves. + */ +node * queue = NULL; + +/* The user can toggle on and off the "verbose" + * property, which causes the pointer addresses + * to be printed out in hexadecimal notation + * next to their corresponding keys. + */ +bool verbose_output = false; + + +// FUNCTION PROTOTYPES. + +// Output and utility. + +void license_notice( void ); +void print_license( int licence_part ); +void usage_1( void ); +void usage_2( void ); +void usage_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 print_tree( 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 * coalesce_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. + +// OUTPUT AND UTILITIES + +/* Copyright and license notice to user at startup. + */ +void license_notice( void ) { + printf("bpt version %s -- Copyright (C) 2010 Amittai Aviram " + "http://www.amittai.com\n", Version); + printf("This program comes with ABSOLUTELY NO WARRANTY; for details " + "type `show w'.\n" + "This is free software, and you are welcome to redistribute it\n" + "under certain conditions; type `show c' for details.\n\n"); +} + + +/* Routine to print portion of GPL license to stdout. + */ +void print_license( int license_part ) { + int start, end, line; + FILE * fp; + char buffer[0x100]; + + switch(license_part) { + case LICENSE_WARRANTEE: + start = LICENSE_WARRANTEE_START; + end = LICENSE_WARRANTEE_END; + break; + case LICENSE_CONDITIONS: + start = LICENSE_CONDITIONS_START; + end = LICENSE_CONDITIONS_END; + break; + default: + return; + } + + fp = fopen(LICENSE_FILE, "r"); + if (fp == NULL) { + perror("print_license: fopen"); + exit(EXIT_FAILURE); + } + for (line = 0; line < start; line++) + fgets(buffer, sizeof(buffer), fp); + for ( ; line < end; line++) { + fgets(buffer, sizeof(buffer), fp); + printf("%s", buffer); + } + fclose(fp); +} + + +/* First message to the user. + */ +void usage_1( void ) { + printf("B+ Tree of Order %d.\n", order); + printf("Following Silberschatz, Korth, Sidarshan, Database Concepts, " + "5th ed.\n\n" + "To build a B+ tree of a different order, start again and enter " + "the order\n" + "as an integer argument: bpt <order> "); + printf("(%d <= order <= %d).\n", MIN_ORDER, MAX_ORDER); + printf("To start with input from a file of newline-delimited integers, \n" + "start again and enter the order followed by the filename:\n" + "bpt <order> <inputfile> .\n"); +} + + +/* Second message to the user. + */ +void usage_2( void ) { + printf("Enter any of the following commands after the prompt > :\n" + "\ti <k> -- Insert <k> (an integer) as both key and value).\n" + "\tf <k> -- Find the value under key <k>.\n" + "\tp <k> -- Print the path from the root to key k and its associated " + "value.\n" + "\tr <k1> <k2> -- Print the keys and values found in the range " + "[<k1>, <k2>\n" + "\td <k> -- Delete key <k> and its associated value.\n" + "\tx -- Destroy the whole tree. Start again with an empty tree of the " + "same order.\n" + "\tt -- Print the B+ tree.\n" + "\tl -- Print the keys of the leaves (bottom row of the tree).\n" + "\tv -- Toggle output of pointer addresses (\"verbose\") in tree and " + "leaves.\n" + "\tq -- Quit. (Or use Ctl-D.)\n" + "\t? -- Print this help message.\n"); +} + + +/* Brief usage note. + */ +void usage_3( void ) { + printf("Usage: ./bpt [<order>]\n"); + printf("\twhere %d <= order <= %d .\n", MIN_ORDER, MAX_ORDER); +} + + +/* Helper function for printing the + * tree out. See print_tree. + */ +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 print_tree. + */ +node * dequeue( void ) { + node * n = queue; + queue = queue->next; + n->next = NULL; + return n; +} + + +/* 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"); +} + + +/* Utility function to give the height + * of the tree, which length in number of edges + * of the path from the root to any leaf. + */ +int height( node * root ) { + int h = 0; + node * c = root; + while (!c->is_leaf) { + c = c->pointers[0]; + h++; + } + return h; +} + + +/* Utility function to give the length in edges + * of the path from any node to the root. + */ +int path_to_root( node * root, node * child ) { + int length = 0; + node * c = child; + while (c != root) { + c = c->parent; + length++; + } + return length; +} + + +/* Prints the B+ tree in the command + * line in level (rank) order, with the + * keys in each node and the '|' symbol + * to separate nodes. + * With the verbose_output flag set. + * the values of the pointers corresponding + * to the keys also appear next to their respective + * keys, in hexadecimal notation. + */ +void print_tree( 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 to stdout. + */ +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 + * of keys between key_start and key_end, including both bounds. + */ +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); + } +} + + +/* Finds keys and their pointers, if present, in the range specified + * by key_start and key_end, inclusive. Places these in the arrays + * returned_keys and returned_pointers, and returns the number of + * entries found. + */ +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; +} + + +/* Traces the path from the root to a leaf, searching + * by key. Displays information about the path + * if the verbose flag is set. + * Returns the leaf containing the given key. + */ +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 general node, which can be adapted + * to serve as either a leaf or an internal 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; +} + + + +/* Master insertion function. + * Inserts a key and an associated value into + * the B+ tree, causing the tree to be adjusted + * however necessary to maintain the B+ tree + * properties. + */ +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. + +/* Utility function for deletion. Retrieves + * the index of a node's nearest neighbor (sibling) + * to the left if one exists. If not (the node + * is the leftmost child), returns -1 to signify + * this special case. + */ +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; + + /* Case: nonempty root. + * Key and pointer have already been deleted, + * so nothing to be done. + */ + + if (root->num_keys > 0) + return root; + + /* Case: empty root. + */ + + // If it has a child, promote + // the first (only) child + // as the new 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; +} + + +/* Coalesces a node that has become + * too small after deletion + * with a neighboring node that + * can accept the additional entries + * without exceeding the maximum. + */ +node * coalesce_nodes(node * root, node * n, node * neighbor, int neighbor_index, int k_prime) { + + int i, j, neighbor_insertion_index, n_end; + node * tmp; + + /* 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; + + /* Case: nonleaf node. + * Append k_prime and the following pointer. + * Append all pointers and keys from the neighbor. + */ + + if (!n->is_leaf) { + + /* Append k_prime. + */ + + neighbor->keys[neighbor_insertion_index] = k_prime; + neighbor->num_keys++; + + + n_end = n->num_keys; + + 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--; + } + + /* The number of pointers is always + * one more than the number of keys. + */ + + neighbor->pointers[i] = n->pointers[j]; + + /* 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]; + } + + root = delete_entry(root, n->parent, k_prime, n); + free(n->keys); + free(n->pointers); + free(n); + 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 - 1; 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. + * Removes the record and its key and pointer + * from the leaf, and then makes all appropriate + * changes to preserve the B+ tree properties. + */ +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. + * (Rest of function body.) + */ + + /* 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. + * (The simple case.) + */ + + if (n->num_keys >= min_keys) + return root; + + /* Case: node falls below minimum. + * Either coalescence or redistribution + * is needed. + */ + + /* Find the appropriate neighbor node with which + * to coalesce. + * 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; + + /* Coalescence. */ + + if (neighbor->num_keys + n->num_keys < capacity) + return coalesce_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; +} + + +// MAIN + +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); + usage_3(); + exit(EXIT_FAILURE); + } + } + + license_notice(); + usage_1(); + usage_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); + print_tree(root); + } + + printf("> "); + while (scanf("%c", &instruction) != EOF) { + switch (instruction) { + case 'd': + scanf("%d", &input); + root = delete(root, input); + print_tree(root); + break; + case 'i': + scanf("%d", &input); + root = insert(root, input, input); + print_tree(root); + break; + case 'f': + case 'p': + 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; + break; + case 't': + print_tree(root); + break; + case 'v': + verbose_output = !verbose_output; + break; + case 'x': + if (root) + root = destroy_tree(root); + print_tree(root); + break; + default: + usage_2(); + break; + } + while (getchar() != (int)'\n'); + printf("> "); + } + printf("\n"); + + return EXIT_SUCCESS; +} diff --git a/Algorithms/facttail.c b/Algorithms/facttail.c new file mode 100644 index 0000000..c150a05 --- /dev/null +++ b/Algorithms/facttail.c @@ -0,0 +1,37 @@ +/* + * Tail recursion + * + * Implements a factorial function using tail recursion instead of regular + * recursion + */ + +#include <stdio.h> + +int facttail(int n, int cur) { + + if (n < 0) + return 0; + + switch (n){ + case (0): + return 1; + break; + case (1): + return cur; + break; + default: + facttail(n - 1, cur * n); + } +} + +int main(void) { + int a = 3; + int b = 1; + int res = 0; + + res = facttail(a, 1); + + printf("Res: %d\n", res); + return 0; +} + diff --git a/Algorithms/frames.c b/Algorithms/frames.c new file mode 100644 index 0000000..99cdf20 --- /dev/null +++ b/Algorithms/frames.c @@ -0,0 +1,39 @@ +#include <stdlib.h> + +#include "frames.h" +#include "lists.h" + +int alloc_frame(List *frames) +{ + + int frame_number, *data; + + if (list_size(frames) == 0) {/* No frames available */ + return -1; + + } else { + if (list_rem_next(frames, NULL, (void **)&data) != 0) { + return -1; + } else { + frame_number = *data; + free(data); + } + } + + return frame_number; +} + +int free_frame(List *frames, int frame_number) +{ + int *data; + + if ((data = (int *)malloc(sizeof(int))) == NULL) + return -1; + + *data = frame_number; + + if (list_ins_next(frames, NULL, data) != 0) + return -1; + + return 0; +} diff --git a/Algorithms/linked_list.c b/Algorithms/linked_list.c new file mode 100644 index 0000000..16bf24b --- /dev/null +++ b/Algorithms/linked_list.c @@ -0,0 +1,177 @@ +/* + * Copyright (c) Carlos Maiolino <[email protected]>. + * All Rights Reserved. + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License as + * published by the Free Software Foundation. + * + * This program is distributed in the hope that it would be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA + */ + + /* This is a simple example of double linked lists I wrote for fun + * Because I had nothing better to do :) + */ + +#include <stdio.h> +#include <stdlib.h> + +struct list_item { + int key; + struct list_item *prev; + struct list_item *next; +}; + +struct list_item *list_add(struct list_item *HEAD, int key) +{ + struct list_item *item = malloc(sizeof(struct list_item)); + + if (!item) + goto err_out; + + item->key = key; + item->prev = NULL; + + /* list is empty, just asign this item as HEAD */ + if (!HEAD) { + item->next = NULL; + HEAD = item; + return HEAD; + } + + item->next = HEAD; + HEAD->prev = item; + HEAD = item; + return HEAD; + +err_out: + return NULL; +} + +void list_del_by_item(struct list_item **HEAD, int i) +{ + struct list_item *item = *HEAD; + + for (; i > 0; i--) { + if (item) { + item = item->next; + } else { + printf("Can't free an inexistent item\n"); + return; + } + } + + /* if this is the last item, item->next is already NULL */ + if (item->prev) + item->prev->next = item->next; + else { + *HEAD = item->next; + } + + if (item->next) + item->next->prev = item->prev; + + free(item); + return; +} +/* +int list_del_by_key(list, key) +int list_search(list, key) +*/ + +void print_list(struct list_item *HEAD) +{ + struct list_item *iter = HEAD; + + if (!HEAD) { + printf("List is empty\n"); + return; + } + + if (HEAD->prev != NULL) { + printf("Item is not the head of the list\n"); + return; + } + + while (iter) { + printf(" %d", iter->key); + iter = iter->next; + } + printf("\nEND OF LIST\n"); +} + +void print_node(struct list_item *item) +{ + int *val = &(item->key); + printf("NODE= %p \n", item); + printf(" .prev = %p\n", item->prev); + printf(" .next = %p\n", item->next); + printf(" .key = %p\n", &(item->key)); + printf(" .key = %d\n", *(&(item->key))); + printf(" .key = %d\n", *val); +} + +void debug_list(struct list_item *HEAD) +{ + while (HEAD) { + print_node(HEAD); + HEAD = HEAD->next; + } +} + +int main(void) +{ + /* Init list head */ + struct list_item *HEAD = NULL; + int val; + char cmd; + + while (1) { + printf("Select option: "); + scanf(" %c", &cmd); + + switch (cmd) { + case 'a': + printf("Add value: "); + scanf(" %d", &val); + HEAD = list_add(HEAD, val); + break; + case 'd': + printf("Item to delete (starting on 0): "); + scanf(" %d", &val); + if (HEAD) + list_del_by_item(&HEAD, val); + else + printf("List is empty\n"); + break; + + case 'p': + print_list(HEAD); + break; + case 'D': + debug_list(HEAD); + break; + case 'q': + goto out; + default: + printf("a: add to list, d: del item, p: print\n"); + break; + } + } + +out: + while (HEAD) { + struct list_item *next = HEAD->next; + free(HEAD); + HEAD = next; + } + + return 0; +} diff --git a/Algorithms/lists.c b/Algorithms/lists.c new file mode 100644 index 0000000..0e73801 --- /dev/null +++ b/Algorithms/lists.c @@ -0,0 +1,225 @@ +/* + * Linked lists implementation +*/ + +#include <stdlib.h> +#include <string.h> + +#include "lists.h" + +/* SINGLY LINKED LIST */ + +void list_init(List *list, void (*destroy)(void *data)) +{ + list->size = 0; + list->destroy = destroy; + list->head = NULL; + list-tail = NULL; + + return; +} + +void list_destroy(List *list) +{ + void *data = NULL; + + while (list_size(list) > 0) { + /* list_rem_next removes head's element if passed NULL */ + if (list_rem_next(list, NULL, (void **)&data) == 0 && + list->destroy != NULL) + list->destroy(data); + } + + memset(list, 0, sizeof(List)); + return; +} + +int list_ins_next(List *list, ListElmt *element, const void *data) +{ + ListElmt *new_element; + + if ((new_element = (ListElmt *)malloc(sizeof(ListElmt))) == NULL) + return -1; + + new_element->data = (void *)data; + + if (element == NULL) { + if (list_size(list) == 0) + list->tail = new_element; + + new_element->next = list->head; + list->head = new_element; + } else { + if (element->next == NULL) + list->tail = new_element; + + new_element->next = element->next; + element->next = new_element + } + + list->size++; + return 0; +} + +int list_rem_next(List *list, ListElmt *element, void **data) { + ListElmt *old_element; + + if (list_size(list) == 0) + return -1; + + if (element == NULL) { + *data = list->head->data; + old_element = list->head; + list->head = list->head->next; + + if (list_size(list) == 1) + list->tail = NULL; + + } else { + if (element->next == NULL) + return -1; + + *data = element->next->data; + old_element = element->next; + element->next = element->next->next; + + if (element->next == NULL) + list->tail = element; + } + + free(old_element); + list->size--; + return 0; +} + +/* SINGLY LINKED LIST -- END */ + +/* DOUBLY LINKED LIST */ + +void dlist_init(struct DList *list, void (*destroy)(void *data)) { + + /* Initialize list */ + list->size = 0; + list->destroy = destroy; + list->head = NULL; + list->tail = NULL; + return; +} + +void dlist_destroy(struct DList *list) { + void *data; + + /* Remove elements */ + while (dlist_size(list) > 0) { + if (dlist_remove(list, dlist_tail(list), (void **)&data) == 0 + && list->destroy != NULL) + list->destroy(data); + } + + /* clear list struct just in case */ + memset(list, 0, sizeof(DList)); + return; +} + +int dlist_ins_next(struct DList *list, + struct DListElmt *element, + const void *data) +{ + struct DListElmt *new; + + /* No NULL elements allowed */ + if (element == NULL && dlist_size(list) != 0) + return -1; + + if ((new = (struct DListElmt *)malloc(sizeof(struct DListElmt))) == NULL) + return -1; + + new->data = (void *)data; + + if (dlist_size(list) == 0) { + list->head = new; + list->head->prev = NULL; + list->head->next = NULL; + list->tail = new; + } else { + new->next = element->next; + new->prev = element; + + if (new->next == NULL) + list->tail = new; + else + new->next->prev = new; + + element->next = new; + } + + list->size++; + return 0 +} + +int dlist_ins_prev(struct DList *list, + struct DListElmt *element, + const void *data) +{ + struct DListElmt *new; + + /* No NULL elements allowed */ + if (element == NULL && dlist_size(list) != 0) + return -1; + + if ((new = (struct DListElmt *)malloc(sizeof(struct DListElmt))) == NULL) + return -1; + + new->data = (void *)data; + + if (dlist_size(list) == 0) { + /* insert on head */ + list->head = new; + list->head->prev = NULL; + list->head->next = NULL; + list->tail = new; + } else { + new->next = element; + new->prev = element->prev; + + if (new->prev == NULL) + list->head = new; + else + element->prev->next = new; + + element->prev = new; + } + + list_size++; + return 0; +} + +int dlist_remove(struct DList *list, struct DListElmt *element, void **data) +{ + /* No NULL element allowed or removal from empty */ + if (element == NULL || dlist_size(list == 0)) + return -1; + + /* Remove element */ + *data = element->data; + + if (element == list->head) { + list->head = element->next; + + if (list->head == NULL) + list->tail = NULL; + else + list->head->prev = NULL; + } else { + element->prev->next = element->next; + + if (element->next == NULL) + list->tail = element->prev; + else + element->next->prev = element->prev; + } + + free(element); + list->size--; + return 0; +} diff --git a/Algorithms/lists.h b/Algorithms/lists.h new file mode 100644 index 0000000..20ddb45 --- /dev/null +++ b/Algorithms/lists.h @@ -0,0 +1,113 @@ +#ifndef LIST_H +#define LIST_H + +#include <stdlib.h> + +struct ListElmt { + void *data; + struct ListElmt *next; +}; + +struct List { + int size; + + int (*match)(const void *key1, const void *key2); + void (*destroy)(void *data); + + struct ListElmt *head, *tail; +} + +/* + * Initializes a linked list + * List: Linked list to initialize + * destructor: helper to destruct and free data allocated for the list + */ +void list_init(List *list, void (*destroy)(void *data)); + +/* + * Destroy a linked list, its elements and calls its destructor. + * May or may not free memory, depends on its desctructor. + */ +void list_destroy(List *list); + +/* + * Insert a new element AFTER 'element'. If 'element is NULL, the new element is + * inserted at the head of the list. The new element contains a pointer to + * 'data', so, its pointer should remain valid as long as the element remains in + * the list. It's caller's responsibility to manage storage associated with data. + * Return: 0 if successful, negative otherwise + */ +int list_ins_next(List *list, ListElmt *element, const void *data); + +/* + * Remove the element just after 'element', if NULL, remove the element at the + * list head. Upon return, 'data' points to the data stored in the removed + * element. It's caller's responsibility to manage storage associated with data. + * Return: 0 if successful, negative otherwise + */ +int list_rem_next(List *list, ListElmt *element, void **data); + +#define list_size(list) ((list)->size) +#define list_head(list) ((list)->head) +#define list_tail(list) ((list)->tail) + +/* Return: 1 if the element is at the head of the list, 0 otherwise */ +#define list_is_head(list, element) ((element) == ((list)->head) ? 1 : 0) + +/* Return: 1 if the element is at the tail of the list, 0 otherwise */ +#define list_is_tail(element) ((element)->next == NULL ? 1 : 0) + +/* Return: Data stored in the element */ +#define list_data(element) ((element)->data) + +/* Return: Element following the specified element */ +#define list_next(element) ((element)->next) + +#endif /* LIST_H */ + + +#ifndef DLIST_H +#define DLIST_H +/* Doubly Linked List implementation */ + +/* doubly-linked list elements */ +struct DListElmt { + void *data; + struct DListElmt *prev; + struct DListElmt *next; +}; + +/* doubly-linked list structure */ + +struct DList { + int size; + int (*match)(const void *key1, const void *key2); + void (*destroy)(void *data); + + struct DlistElmt *head, *tail; +}; + +/* Public interface */ + +void dlist_init(struct Dlist *List, void (*destroy)(void *data)); +void dlist_destroy(struct DList *list); + +int dlist_ins_next(struct DList *list, struct DListElmt *element, + const void *data); +int dlist_ins_prev(struct DList *list, struct DListElmt *element, + const void *data); + +int dlist_remove(struct DList *list, struct DListElmt *element, void **data); + +#define dlist_size(list) ((list)->size) +#define dlist_head(list) ((list)->head) +#define dlist_tail(list) ((list)->tail) + +#define dlist_is_head(element) ((element)->prev == NULL ? 1 : 0) +#define dlist_is_tail(element) ((element)->next == NULL ? 1 : 0) + +#define dlist_data(element) ((element)->data) +#define dlist_next(element) ((element)->next) +#define dlist_prev(element) ((element)->prev) + +#endif /* DLIST_H */ diff --git a/Algorithms/queue_static.c b/Algorithms/queue_static.c new file mode 100644 index 0000000..5124a01 --- /dev/null +++ b/Algorithms/queue_static.c @@ -0,0 +1,166 @@ +#include <stdio.h> + +#define QUEUE_SIZE 10 + +/* + * Simple queue algorithm implementation + * + * tail will always point to the next available slot + */ +struct queue { + int data[QUEUE_SIZE]; + int head; + int tail; +}; + +int queue_empty(struct queue *Q) +{ + return Q->head == Q->tail; +} + +/* + * Queue is full when: + * tail + 1 == HEAD or + * TAIL == QUEUE_SIZE - 1 and HEAD == 0 + */ +int queue_full(struct queue *Q) +{ + if (((Q->tail + 1) == Q->head) || + ((Q->tail == (QUEUE_SIZE - 1)) && (Q->head == 0))) + return 1; + else + return 0; +} + +int queue_push(struct queue *Q, int value) +{ + if (queue_full(Q)) { + printf("Queue is full, avoiding overflow\n"); + return 0; + } + + Q->data[Q->tail] = value; + + if (Q->tail == (QUEUE_SIZE - 1)) + Q->tail = 0; + else + Q->tail++; + + return value; + +} + +/* FIXME: function return 0 in case of failure, should return something + * else, once 0 is a valid value to the queue + */ +int queue_pop(struct queue *Q) +{ + int value = 0; + + if (queue_empty(Q)) { + printf("Queue is empty, avoiding underflow\n"); + return value; + } + + value = Q->data[Q->head]; + + if (Q->head == (QUEUE_SIZE - 1)) + Q->head = 0; + else + Q->head++; + + return value; +} + +void print_queue(struct queue *Q) +{ + int i = Q->head; + int pos = 1; + + if (queue_empty(Q)) { + printf("Nothing to print, queue is empty\n"); + return; + } + + printf(" Pos | Tail \n"); + for (;;) { + printf(" %d | %d \n", pos, Q->data[i]); + + if (i == (QUEUE_SIZE - 1)) + i = 0; + else + i++; + pos++; + + if (i == Q->tail) + break; + } +} + +void debug_queue(struct queue *Q) +{ + int i; + + for (i = 0; i < QUEUE_SIZE; i++) { + printf("| %d | ", Q->data[i]); + + if (i == Q->head) + printf("<-- HEAD "); + if (i == Q->tail) + printf("<-- TAIL"); + printf("\n"); + } +} + +int main(void) +{ + struct queue my_queue; + int i, val; + char cmd; + + /* Init queue */ + my_queue.head = 0; + my_queue.tail = 0; + for (i = 0; i < QUEUE_SIZE; i++) + my_queue.data[i] = 0; + + while (1) { + printf("Select an option: "); + scanf(" %c", &cmd); + + switch (cmd) { + case 'a': + printf("Value to add: "); + scanf(" %d", &val); + queue_push(&my_queue, val); + break; + case 'p': + queue_pop(&my_queue); + break; + case 'd': + debug_queue(&my_queue); + break; + case 'l': + print_queue(&my_queue); + break; + default: + printf("Invalid option\n"); + printf("a = add, p = pop, d = debug, l = print\n"); + } + } + + return 0; +} + + + + + + + + + + + + + diff --git a/Algorithms/stack_static.c b/Algorithms/stack_static.c new file mode 100644 index 0000000..299cf70 --- /dev/null +++ b/Algorithms/stack_static.c @@ -0,0 +1,125 @@ +#include <stdio.h> +#include <stdbool.h> + +#define STACK_SIZE 10 + +struct stack { + int data[STACK_SIZE]; + int top; +}; + +bool stack_empty(struct stack *S) +{ + if (S->top) + return false; + else + return true; +} + +/* + * Push an element to the top of the stack + * - Return the element pushed in case of success + * - Return 0 otherwise + */ +int stack_push(struct stack *S, int value) +{ + if (S->top == (STACK_SIZE - 1)) { + printf("Stack full, avoiding overflow\n"); + return 0; + } + + S->top++; + S->data[S->top] = value; + printf("Last element into stack: %d\n", S->data[S->top]); + return value; +} + +int stack_pop(struct stack *S) +{ + int ret = 0; + + if (S->top == -1) { + printf("Stack empty, avoiding underflow\n"); + return 0; + } + + ret = S->data[S->top]; + S->top--; + return ret; +} + +void print_stack(struct stack *S) +{ + int i; + + printf("Elements into stack: %d\n", S->top + 1); + + if (S->top < 0) { + printf("Stack is empty\n"); + return; + } + + printf("Pos | Val"); + for (i = 0; i <= S->top; i++) + printf("\n %d | %d", i, S->data[i]); + printf(" <-- TOP\n"); +} + +void debug_stack(struct stack *S) +{ + int i; + + printf(" Stack Pointer is: %d\n", S->top); + + for (i = 0; i < STACK_SIZE; i++) + printf("Position: %d - Value: %d\n", i, S->data[i]); +} + + +int main(void) +{ + /* Initialize the stack and all its elements to 0 */ + struct stack mystack; + int i = STACK_SIZE; + char cmd; + + mystack.top = -1; /* Stack is empty */ + for (i = 0; i < STACK_SIZE; i++) + mystack.data[i] = 0; + + + while (1) { + int val = 0; + printf("Select option (h for help): \n"); + scanf(" %c", &cmd); + + switch (cmd) { + case 'a': + printf(" Push value: "); + scanf(" %d", &val); + stack_push(&mystack, val); + break; + case 'o': + printf("Popping stack\n"); + stack_pop(&mystack); + break; + case 'p': + print_stack(&mystack); + break; + case 'd': + debug_stack(&mystack); + break; + case 'q': + return 0; + default: + printf("Invalid entry, please use:\n"); + printf("a - Push value to the stack\n"); + printf("o - Pop value from the stack\n"); + printf("p - Print the whole stack\n"); + printf("d - Debug stack, print all elements\n"); + printf(" into the stack array even beyond TOP\n"); + printf("q - Exit stack fun\n"); + } + } + return 0; +} |