temelia/src/b_tree.c

/*!
 Temelia - B-tree implementation source file.

 Copyright (C) 2008, 2009 Ceata (http://ceata.org/proiecte/temelia).

 @author Dascalu Laurentiu

 This program is free software; you can redistribute it and
 modify it under the terms of the GNU General Public License
 as published by the Free Software Foundation; either version 3
 of the License, or (at your option) any later version.

 This program is distributed in the hope that it will 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 to the Free Software
 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 */

#include "include/b_tree.h"
#include "include/vector.h"
#include <stdlib.h>

/*
 * The source file contains, for the most important functions: search, insert
 * and delete; the pseudo code is taken from
 * http://cs-netlab-01.lynchburg.edu/courses/DataStII/BTreeOps.htm
 */

struct _b_tree_t
{
	/*! reference to root */
	b_tree_node_t root;

	/*! degree - maximum children number */
	int degree;

	int size;
};

struct _b_tree_node_t
{
	/*! reference to parent */
	struct _b_tree_node_t *parent;

	/*! reference to children */
	vector_t children;

	/*! keys in current node */
	vector_t keys;
};

static b_tree_node_t _b_tree_new_node(int degree);

static void _b_tree_delete(b_tree_node_t node);

static void _b_tree_delete_node(b_tree_node_t node);

static b_tree_node_t _b_tree_search(b_tree_node_t b_tree, void *key,
		int compare(void *x, void *y, void *context), void *context);

static void _b_tree_divide(int degree, b_tree_node_t x, int index,
		b_tree_node_t y);

static b_tree_node_t _b_tree_insert(b_tree_node_t root, void *key, int compare(
		void *x, void *y, void *context), void *context, int degree);

static void _b_tree_show_indented(b_tree_node_t root, void key_handler(
		void *key, int level, void *fout), int level, void *fout);

static void _b_tree_level_order(b_tree_node_t root, int level,
		void key_handler(void *x, void *fout), void *fout);

static int _b_tree_get_height(b_tree_node_t node);

static void
*_b_tree_remove(b_tree_t b_tree, b_tree_node_t node, void *key, int compare(
		void *x, void *y, void *context), void *context, int degree);

static INLINE void *_b_tree_node_find_predecesor(b_tree_node_t node);

b_tree_t b_tree_new(int degree)
{
	b_tree_t b_tree;

	/*
	 * Allocate memory for a new B-tree, set it's root to NULL and degree
	 * to the given value.
	 */
	b_tree = (struct _b_tree_t *) _new(sizeof(struct _b_tree_t));
	b_tree->root = NULL;
	b_tree->degree = degree;
	b_tree->size = 0;

	return b_tree;
}

void b_tree_delete(b_tree_t b_tree)
{
	_ASSERT(b_tree, ==, NULL, NULL_POINTER,);

	/*
	 * If the root is not empty, then start deleting the root.
	 * For this purpose, I created the function _b_tree_delete.
	 */
	if (b_tree->root)
		_b_tree_delete(b_tree->root);

	/*
	 * Set B-tree's root to NULL and degree to 0.
	 */
	b_tree->root = NULL;
	b_tree->degree = 0;
	b_tree->size = 0;

	_delete(b_tree);
}

b_tree_node_t b_tree_get_root(b_tree_t b_tree)
{
	_ASSERT(b_tree, ==, NULL, NULL_POINTER, NULL);

	return b_tree->root;
}

int b_tree_get_degree(b_tree_t b_tree)
{
	_ASSERT(b_tree, ==, NULL, NULL_POINTER, -1);

	return b_tree->degree;
}

int b_tree_get_height(b_tree_t b_tree)
{
	_ASSERT(b_tree, ==, NULL, NULL_POINTER, -1);

	return _b_tree_get_height(b_tree->root);
}

int b_tree_node_get_depth(b_tree_node_t node)
{
	int i = 0;
	_ASSERT(node, ==, NULL, NULL_POINTER, -1);

	/*
	 * The algorithm is very simple and checks for a superior limit.
	 * If i is too big, then it will become negative and the loop will be broken.
	 * The result will be a negative number.
	 */
	while ((node = node->parent) && ++i > 0)
		;

	return i;
}

b_tree_node_t b_tree_node_get_parent(b_tree_node_t node)
{
	_ASSERT(node, ==, NULL, NULL_POINTER, NULL);

	return node->parent;
}

int b_tree_node_get_children_number(b_tree_node_t node)
{
	_ASSERT(node, ==, NULL, NULL_POINTER, -1);

	return vector_get_size(node->children);
}

b_tree_node_t b_tree_node_get_child(b_tree_node_t node, int index)
{
	_ASSERT(node, ==, NULL, NULL_POINTER, NULL);

	return vector_get_key_at(node->children, index);
}

int b_tree_node_get_keys_number(b_tree_node_t node)
{
	_ASSERT(node, ==, NULL, NULL_POINTER, -1);

	return vector_get_size(node->keys);
}

void *b_tree_node_get_key(b_tree_node_t node, int index)
{
	_ASSERT(node, ==, NULL, NULL_POINTER, NULL);

	return vector_get_key_at(node->keys, index);
}

b_tree_node_t b_tree_search(b_tree_t b_tree, void *key, int compare(void *x,
		void *y, void *context), void *context)
{
	_ASSERT(b_tree, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(compare, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(b_tree->size, <=, 0, INVALID_INPUT, NULL);

	/*
	 *  Search(btree, k)
	 *  //Search a B-tree, btree, for a key, k.
	 *  //if found k then return pointer to node containing k
	 *  //else return NULL
	 *
	 *  current_node = root(btree)
	 *
	 *  while current_node is not NULL
	 *  	Search through keys in current_node until
	 *  		1. found k
	 *  		2. found first key (ki) larger than k or
	 *  		3. passed last key in current_node
	 *
	 *  	Case 1.
	 *  		return pointer to current_node
	 *
	 *  	Case 2.
	 *  		current_node = ith child of current_node
	 *
	 *  	Case 3.
	 *  		current_node = last child of current_node
	 *  end while
	 *
	 *  return NULL
	 */
	return _b_tree_search(b_tree->root, key, compare, context);
}

b_tree_node_t b_tree_insert(b_tree_t b_tree, void *key, int compare(void *x,
		void *y, void *context), void *context, int add_if_exists)
{
	b_tree_node_t root = NULL, add = NULL;
	int degree = 0;

	_ASSERT(b_tree, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(compare, ==, NULL, NULL_POINTER, NULL);

	/*
	 * B-Tree-Insert(void *, k)
	 * 		//Insert the key, k, into tree, void *.
	 * 		r = root[void *]
	 * 	if the root is full (i.e., has 2t-1 keys) then
	 * 		Allocate a new node and call it s. //s will be the new root.
	 * 		root[void *] = s //make s the root. r still points to original root.
	 * 		set the number of nodes in s to 0.
	 * 		set the only child pointer of s (c1[s]) to point to r.
	 * 			//r is now the child of s.
	 * 		call B-Tree-Split-Child(s, 1, r) to split r and move its middle key up into s.
	 * 		call B-Tree-Insert-NonFull(s, k) to insert the key, k, into the B-Tree
	 * 			with root, s.
	 * 	else //root is not full
	 * 		call B-Tree-Insert-NonFull(r, k) to insert the key, k, into
	 * 			the B-Tree with root, r.
	 * 	end if
	 *
	 *
	 * B-Tree-Insert-NonFull(x, k)
	 * //Inserts the key, k, into a B-Tree. (k will ultimately be inserted into a leaf).
	 * //Begin by attempting to insert k into nonfull node, x.
	 * i = the number of keys in x.
	 *
	 * 	if x is a leaf then
	 * 		since x is not full insert k into its proper place in x.
	 * 		add one to the number of keys in x and update x on disk.
	 * 	else //x is not a leaf
	 * 		Move back from the last key of x until find child pointer to node
	 * 		that is root of subtree in which k should be placed.
	 *
	 * 		if this child node is full then call B-Tree-Split-Child(x, i, ci[x])
	 * 		//Note: we split full nodes on the way down the tree so that
	 * 		//	if a child of that node needs to be split its parent will
	 *      //	be able to accept the middle key.
	 * 			set i = index of whichever child of x is root of subtree in which
	 * 				k should be placed.
	 * 			call B-Tree-Insert-NonFull(ci[x], k) //Note: Recursive call
	 * 	end if
	 */

	root = b_tree->root;
	degree = b_tree->degree;

	if (root == NULL)
	{
		root = _b_tree_new_node(degree);
		vector_push_back(root->keys, key);
		b_tree->root = root;
		b_tree->size = 1;
		return root;
	}

	if (!add_if_exists && b_tree_search(b_tree, key, compare, context) != NULL)
		return NULL;

	b_tree->size++;

	if (vector_get_size(root->keys) == (2 * degree - 1))
	{
		add = _b_tree_new_node(degree);
		b_tree->root = add;
		root->parent = add;
		vector_push_back(add->children, root);
		_b_tree_divide(degree, add, 0, root);
		return _b_tree_insert(add, key, compare, context, degree);
	}
	return _b_tree_insert(root, key, compare, context, degree);
}

int b_tree_remove(b_tree_t b_tree, void *key, int compare(void *x, void *y,
		void *context), void *context)
{
	int result;

	_ASSERT(b_tree, ==, NULL, NULL_POINTER, -1);
	_ASSERT(compare, ==, NULL, NULL_POINTER, -1);
	_ASSERT(b_tree->size, <=, 0, INVALID_INPUT, -1);

	/*
	 * The algorithm is : B-Tree-Delete(x, k)
	 *  k is the key to be deleted and
	 *  x is the root of the subtree from which k is to be deleted.
	 *  B-Tree-Delete returns true if it successfully deletes k else it returns false.
	 *
	 *  if x is a leaf then
	 *  	if k is in x then
	 *  		delete k from x and return true
	 *  	else return false //k is not in subtree
	 *
	 *  else //x is an internal node
	 *  	if k is in x then
	 *  		y = the child of x that precedes k
	 *
	 *  		if y has at least t keys then
	 *  			k' = the predecessor of k (use B-Tree-FindLargest)
	 *  			Copy k' over k //i.e., replace k with k'
	 *  			B-Tree-Delete(y, k') //Note: recursive call
	 *
	 *  		else //y has t-1 keys
	 *  			z = the child of x that follows k
	 *
	 *  			if z has at least t keys then
	 *  				k' = the successor of k
	 *  				Copy k' over k //i.e., replace k with k'
	 *  				B-Tree-Delete(z, k');
	 *
	 *  			else //both y and z have t-1 keys
	 *  				merge k and all of z into y //y now contains 2t-1 keys.
	 *  				//k and the pointer to z will be deleted from x.
	 *  				B-Tree-Delete(y, k) //Note: recursive call
	 *
	 *  	else //k is not in internal node x.
	 *  		ci[x] points to the root, c, of the subtree that could contain k.
	 *
	 *  		if c has t-1 keys then
	 *
	 *  			if c has an immediate left/right sibling, z, with t or more keys
	 *  					then
	 *  				Let k1 be the key in x that precedes/follows c.
	 *  				Move k1 into c as the first/last key in c.
	 *  				Let k2 be the last/first key in the immediate left/right
	 *  					sibling, z.
	 *  				Replace k1 in x with k2 from z (i.e., move k2 up into x).
	 *  				Move the last/first child subtree of z to be the first/last
	 *  					child subtree of c.
	 *
	 *  		else //c and both of its immediate siblings have t-1 keys.
	 *  			//we cannot descend to a child node with only t-1 keys so
	 *  			merge c with one of its immediate siblings and
	 *  			make the appropriate key of x the middle key of the new node, c.
	 *  			//Note: This may cause the root to collapse, thus making c the
	 *  				new root.
	 *  		B-Tree-Delete(c, k)
	 */
	result = _b_tree_remove(b_tree, b_tree->root, key, compare, context,
			b_tree->degree) != NULL;

	if (result)
		b_tree->size--;
	return result;
}

b_tree_node_t b_tree_get_min(b_tree_t b_tree)
{
	b_tree_node_t root = NULL;

	/*
	 * The minimum node is the left-most node.
	 * current_node = root;
	 * while(current_node is not leaf)
	 * 		current_node = first child of current_node;
	 */

	_ASSERT(b_tree, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(b_tree->root, ==, NULL, NULL_POINTER, NULL);

	root = b_tree->root;
	while (vector_get_size(root->children) > 0)
		root = vector_get_key_at(root->children, 0);
	return root;
}

void *b_tree_get_min_key(b_tree_t b_tree)
{
	b_tree_node_t node = b_tree_get_min(b_tree);

	_ASSERT(node, ==, NULL, NULL_POINTER, NULL);

	/*
	 * The minimum key is in the left-most node.
	 * I find the left-most node, calling b_tree_get_min,
	 * and then I return the first key contained by it.
	 */

	return vector_get_key_at(node->keys, 0);
}

b_tree_node_t b_tree_get_max(b_tree_t b_tree)
{
	b_tree_node_t root = NULL;

	/*
	 * The maximum node is the right-most node.
	 * current_node = root;
	 * while(current_node is not leaf)
	 * 		current_node = last child of current_node;
	 */

	_ASSERT(b_tree, ==, NULL, NULL_POINTER, NULL);
	_ASSERT(b_tree->root, ==, NULL, NULL_POINTER, NULL);

	root = b_tree->root;
	while (vector_get_size(root->children) > 0)
		root = vector_get_key_at(root->children,
				vector_get_size(root->children) - 1);

	return root;
}

void *b_tree_get_max_key(b_tree_t b_tree)
{
	b_tree_node_t node = b_tree_get_max(b_tree);

	_ASSERT(node, ==, NULL, NULL_POINTER, NULL);

	/*
	 * The maximum key is in the right-most node.
	 * I find the right-most node, calling b_tree_get_max,
	 * and then I return the last key contained by it.
	 */

	return vector_get_key_at(node->keys, vector_get_size(node->keys) - 1);
}

void b_tree_level_order(b_tree_t b_tree, void key_handler(void *x,
		void *context), void *context)
{
	_ASSERT(b_tree, ==, NULL, NULL_POINTER,);
	_ASSERT(key_handler, ==, NULL, NULL_POINTER,);

	_b_tree_level_order(b_tree->root, 0, key_handler, context);
}

void b_tree_show_indented(b_tree_t b_tree, void key_handler(void *key,
		int level, void *context), void *context)
{
	_ASSERT(b_tree, ==, NULL, NULL_POINTER,);
	_ASSERT(b_tree->root, ==, NULL, NULL_POINTER,);
	_ASSERT(key_handler, ==, NULL, NULL_POINTER,);

	_b_tree_show_indented(b_tree->root, key_handler, 0, context);
}

static b_tree_node_t _b_tree_new_node(int degree)
{
	b_tree_node_t node;

	/*
	 * An empty node has :
	 * 	- NULL parent
	 *  - 2 * degree -1 maximum keys; initial 0 keys
	 *  - 2 * degree maximum children; initial 0 children
	 */
	node = (struct _b_tree_node_t *) _new(sizeof(struct _b_tree_node_t));
	node->parent = NULL;
	node->keys = vector_new(2 * degree - 1);
	node->children = vector_new(2 * degree);

	return node;
}

static b_tree_node_t _b_tree_search(b_tree_node_t b_tree, void *key,
		int compare(void *x, void *y, void *context), void *context)
{
	int i = 0, n = 0;

	_ASSERT(b_tree, ==, NULL, NULL_POINTER, NULL);

	n = vector_get_size(b_tree->keys);
	while (i < n && compare(key, vector_get_key_at(b_tree->keys, i), context)
			> 0)
		i++;
	if (i < n && compare(key, vector_get_key_at(b_tree->keys, i), context) == 0)
		return b_tree;

	if (vector_get_size(b_tree->children) == 0)
		return NULL;
	else
		return _b_tree_search(vector_get_key_at(b_tree->children, i), key,
				compare, context);
}

static void _b_tree_divide(int degree, b_tree_node_t x, int index,
		b_tree_node_t y)
{
	int j;
	b_tree_node_t z;
	void *median = NULL;

	/*
	 * //Splits a node, y, in a B-Tree and moves y's median key up to y's parent, x.
	 * //y is the ith child of x.
	 * //This function will only be called if y is full; i.e., has 2t-1 keys.
	 *
	 * 	1. Allocate a new node and call it z. //z will be the new sibling of y.
	 * 	2. If y is a leaf then mark z as a leaf, else mark z as an internal node.
	 * 	3. set the number of keys in z to t-1
	 * 	4. copy the last t-1 keys of y into z.
	 * 	5. if z is not a leaf then copy the last t pointers of y into z.
	 * 	6. set the number of keys in y to t-1.
	 * 	7. insert a (child) pointer to node z into node x.
	 * 	8. insert the original middle key of node y up into node x, moving other keys
	 * and pointers as necessary
	 * 	9. increment the number of keys in x by one.
	 * 	10. Update x, y and z on disk.
	 */
	z = _b_tree_new_node(degree);

	// Divide keys
	for (j = 0; j < degree - 1; j++)
		vector_push_back(z->keys, vector_get_key_at(y->keys, j + degree));

	// Divide children references
	if (vector_get_size(y->children) > 0)
		for (j = 0; j < degree; j++)
			vector_push_back(z->children, vector_get_key_at(y->children, j
					+ degree));

	median = vector_get_key_at(y->keys, degree - 1);
	vector_set_size(y->keys, degree - 1);

	if (vector_get_size(y->children) > degree)
		vector_set_size(y->children, degree);

	// Adjust the x, the parent of y and z
	vector_push_back(x->keys, NULL);
	for (j = vector_get_size(x->keys) - 2; j >= index; j--)
		vector_set_key_at(x->keys, j + 1, vector_get_key_at(x->keys, j));

	vector_set_key_at(x->keys, index, median);
	vector_push_after(x->children, z, y, compare_pointers, NULL);
	z->parent = x;
}

static b_tree_node_t _b_tree_insert(b_tree_node_t root, void *key, int compare(
		void *x, void *y, void *context), void *context, int degree)
{
	int i = vector_get_size(root->keys);
	b_tree_node_t child = NULL;

	if (vector_get_size(root->children) == 0)
	{
		// I'm in a leaf node.
		vector_push_back(root->keys, NULL);

		while (i > 0 && compare(key, vector_get_key_at(root->keys, i - 1),
				context) < 0)
		{
			vector_set_key_at(root->keys, i, vector_get_key_at(root->keys, i
					- 1));
			i--;
		}

		vector_set_key_at(root->keys, i, key);

		return root;
	}
	else
	{
		// I may use a binary search, but i don't think it's useful because
		// the degree of a b-tree is small, in general.
		while (i > 0 && compare(key, vector_get_key_at(root->keys, i - 1),
				context) < 0)
			i--;

		child = vector_get_key_at(root->children, i);

		if (vector_get_size(child->keys) == (2 * degree - 1))
		{
			_b_tree_divide(degree, root, i, child);
			if (compare(key, vector_get_key_at(root->keys, i), context) > 0)
				return _b_tree_insert(vector_get_key_at(root->children, i + 1),
						key, compare, context, degree);
		}

		return _b_tree_insert(child, key, compare, context, degree);
	}
}

static void _b_tree_delete(b_tree_node_t node)
{
	int i = 0;

	/*
	 * Free the memory occupied by the children then
	 * free current node.
	 */
	for (; i < vector_get_size(node->children); i++)
		_b_tree_delete(vector_get_key_at(node->children, i));

	vector_delete(node->keys);
	vector_delete(node->children);

	node->keys = node->children = NULL;
	node->parent = NULL;

	_delete(node);
}

static void _b_tree_delete_node(b_tree_node_t node)
{
	/*
	 * Deleting a node implies :
	 * 	- deleting the keys's vector
	 * 	- deleting the children's vector
	 * 	- setting keys, children and parent to NULL
	 */
	vector_delete(node->keys);
	vector_delete(node->children);

	node->keys = node->children = NULL;
	node->parent = NULL;

	_delete(node);
}

static void _b_tree_show_indented(b_tree_node_t root, void key_handler(
		void *key, int level, void *context), int level, void *context)
{
	int i = 0, n = 0;

	if (root == NULL)
		return;

	n = vector_get_size(root->keys);

	LOGGER("[_b_tree_show_indented] node %p has %d keys and %d children\n",
			root, vector_get_size(root->keys), vector_get_size(root->children));

	/*
	 * for index in 0 to keys_number
	 * 	call _b_tree_show_indented for the current node (addressable by index)
	 * 	call key_handler for the current key (addressable by index)
	 * call _b_tree_show_indented for the last node
	 */
	for (; i < n; i++)
	{
		if (vector_get_size(root->children) > i)
			_b_tree_show_indented(vector_get_key_at(root->children, i),
					key_handler, level + 1, context);
		key_handler(vector_get_key_at(root->keys, i), level, context);
	}
	if (vector_get_size(root->children) > i)
		_b_tree_show_indented(vector_get_key_at(root->children, i),
				key_handler, level + 1, context);
}

static void _b_tree_level_order(b_tree_node_t root, int level,
		void key_handler(void *x, void *context), void *context)
{
	int i;

	for (i = 0; i < level; i++)
		LOGGER("  ");
	LOGGER("( ");
	for (i = 0; i < vector_get_size(root->keys); i++)
	{
		/*
		 * Calls key_handler for each key in the current node.
		 */
		key_handler(vector_get_key_at(root->keys, i), context);
		LOGGER(" ");
	}
	LOGGER(")\n");

	for (i = 0; i < vector_get_size(root->children); i++)
		/*
		 * Calls _b_tree_level_order for each children of the current node.
		 */
		_b_tree_level_order(vector_get_key_at(root->children, i), level + 1,
				key_handler, context);
}

static int _b_tree_get_height(b_tree_node_t node)
{
	int i = 1, max_height = 0;

	_ASSERT(node, ==, NULL, NOT_EXCEPTION, 0);
	_ASSERT(vector_get_size(node->children), ==, 0, NOT_EXCEPTION, 1);

	/*
	 * height(NULL) = 0
	 * height(node) = 1 + MAX(child_node | child_node is a child of node)
	 */
	max_height = _b_tree_get_height(vector_get_key_at(node->children, 0));
	for (; i < vector_get_size(node->children) - 1; i++)
		max_height = MAX(max_height, _b_tree_get_height(vector_get_key_at(
								node->children, i)));

	return 1 + max_height;
}

static INLINE void *_b_tree_node_find_predecesor(b_tree_node_t node)
{
	/*
	 * Move to the right-most node, starting from the current node
	 * and then return the last key stored in it.
	 */
	while (b_tree_node_get_children_number(node))
		node = vector_get_key_at(node->children,
				vector_get_size(node->children) - 1);
	return vector_get_key_at(node->keys, vector_get_size(node->keys) - 1);
}

static INLINE void *_b_tree_node_find_successor(b_tree_node_t node, void *key)
{
	int i = vector_search(node->keys, key, compare_pointers, NULL);
	b_tree_node_t child = NULL;

	/*
	 * If there is a key after current key, then return it,
	 * else return the first key stored in the next node.
	 */
	if (i < vector_get_size(node->keys) - 1)
		return vector_get_key_at(node->keys, i + 1);

	child = vector_get_key_at(node->children, i + 1);
	if (child)
		return vector_get_key_at(child->keys, 0);
	return NULL;
}

static void *_b_tree_remove(b_tree_t b_tree, b_tree_node_t node, void *key,
		int compare(void *x, void *y, void *context), void *context, int degree)
{
	int i = 0, j = 0;
	b_tree_node_t child = NULL, left = NULL, right = NULL;
	void *new_key = NULL;

	if (b_tree_node_get_children_number(node) == 0)
	{
		LOGGER("[_b_tree_remove] on leaf node %p\n", node);

		// Current node is leaf
		i = vector_search(node->keys, key, compare, context);

		if (i == -1)
			return NULL;

		vector_remove_key_at(node->keys, i);
		return key;
	}
	else
	{
		// Current node is internal node
		i = vector_search(node->keys, key, compare, context);

		if (i != -1)
		{
			LOGGER(
					"[_b_tree_remove] key is in an internal node %p at position %d\n",
					node, i);

			// Key is in current node
			left = vector_get_key_at(node->children, i);
			right = vector_get_key_at(node->children, i + 1);

			LOGGER("[_b_tree_remove] left node %p, right node %p\n", left,
					right);

			if (left && vector_get_size(left->keys) >= degree)
			{
				LOGGER("[_b_tree_remove] left node %p has %d keys\n", node,
						vector_get_size(left->keys));

				new_key = _b_tree_node_find_predecesor(left);
				LOGGER("[_b_tree_remove] successor %p, keys %d, position %d\n",
						new_key, vector_get_size(node->keys), i);
				if (new_key)
				{
					vector_set_key_at(node->keys, i, new_key);

					return _b_tree_remove(b_tree, left, new_key, compare,
							context, degree);
				}
			}
			else if (right && vector_get_size(right->keys) >= degree)
			{
				LOGGER("[_b_tree_remove] right node %p has %d keys\n", node,
						vector_get_size(right->keys));

				new_key = _b_tree_node_find_successor(right, key);
				LOGGER("[_b_tree_remove] successor %p, keys %d, position %d\n",
						new_key, vector_get_size(node->keys), i);

				if (new_key)
				{
					vector_set_key_at(node->keys, i, new_key);

					return _b_tree_remove(b_tree, right, new_key, compare,
							context, degree);
				}
			}
			else
			{
				LOGGER(
						"[_b_tree_remove] merging left node %p and right node %p\n",
						left, right);

				_ASSERT(left, ==, NULL, NULL_POINTER, NULL);

				// Both nodes have degree keys, so I have to merge them.
				vector_push_back(left->keys, key);

				for (i = 0; right && i < vector_get_size(right->keys); i++)
					vector_push_back(left->keys, vector_get_key_at(right->keys,
							i));

				for (i = 0; right && i < vector_get_size(right->children); i++)
					vector_push_back(left->children, vector_get_key_at(
							right->children, i));

				if (right)
				{
					vector_remove_key(node->children, right, compare_pointers,
							NULL);
					_b_tree_delete_node(right);
				}

				vector_remove_key(node->keys, key, compare_pointers, NULL);

				return _b_tree_remove(b_tree, left, key, compare, context,
						degree);
			}
		}
		else
		{
			i = vector_get_size(node->keys);

			// Key isn't in current node
			while (i > 0 && compare(key, vector_get_key_at(node->keys, i - 1),
					context) < 0)
				i--;

			LOGGER("[_b_tree_remove] keys %d, children %d, position %d\n",
					vector_get_size(node->keys),
					vector_get_size(node->children), i);
			child = vector_get_key_at(node->children, i);

			if (child)
				LOGGER(
						"[_b_tree_remove] child %p at position %d and %d keys\n",
						child, i, vector_get_size(child->keys));
			else
				LOGGER("[_b_tree_remove] child %p at position %d\n", child, i);

			if (child && vector_get_size(child->keys) == degree - 1)
			{
				if (i > 0)
					left = vector_get_key_at(node->children, i - 1);
				else
					left = NULL;

				if (i < vector_get_size(node->children) - 1)
					right = vector_get_key_at(node->children, i + 1);
				else
					right = NULL;

				LOGGER(
						"[_b_tree_remove] left child %p, right child %p, degree %d\n",
						left, right, degree);

				if (left)
					LOGGER("[_b_tree_remove] left node has %d keys\n",
							vector_get_size(left->keys));

				if (right)
					LOGGER("[_b_tree_remove] right node has %d keys\n",
							vector_get_size(right->keys));

				if ((left && vector_get_size(left->keys) >= degree) || (right
						&& vector_get_size(right->keys) >= degree))
				{
					if (left && vector_get_size(left->keys) >= degree)
					{
						if (vector_get_size(node->keys) > i - 1)
						{
							vector_push_front(child->keys, vector_get_key_at(
									node->keys, i - 1));

							vector_push_before(node->keys,
									vector_get_key_at(left->keys,
											vector_get_size(left->keys) - 1),
									vector_get_key_at(node->keys, i - 1),
									compare_pointers, NULL);

							vector_remove_key_at(node->keys, i);
							vector_remove_key_at(left->keys, vector_get_size(
									left->keys) - 1);
						}
					}

					if (right && vector_get_size(right->keys) >= degree)
					{
						if (vector_get_size(node->keys) > i)
						{
							vector_push_back(child->keys, vector_get_key_at(
									node->keys, i));

							vector_push_after(node->keys, vector_get_key_at(
									right->keys, 0), vector_get_key_at(
									node->keys, i), compare_pointers, NULL);

							vector_remove_key_at(node->keys, i);
							vector_remove_key_at(right->keys, 0);
						}
					}
				}
				else
				{
					if (left)
					{
						vector_push_front(child->keys, vector_get_key_at(
								node->keys, i - 1));
						vector_remove_key_at(node->children, i - 1);
						vector_remove_key_at(node->keys, i - 1);

						for (j = vector_get_size(left->keys) - 1; j >= 0; j--)
							vector_push_front(child->keys, vector_get_key_at(
									left->keys, j));

						for (j = vector_get_size(left->children) - 1; j >= 0; j--)
						{
							vector_push_front(child->children,
									vector_get_key_at(left->children, j));
							((b_tree_node_t) vector_get_key_at(left->children,
									j))->parent = child;
						}

						_b_tree_delete_node(left);
					}
					else if (right)
					{
						vector_push_back(child->keys, vector_get_key_at(
								node->keys, i));
						vector_remove_key_at(node->children, i + 1);
						vector_remove_key_at(node->keys, i);

						for (j = 0; j < vector_get_size(right->keys); j++)
							vector_push_back(child->keys, vector_get_key_at(
									right->keys, j));

						for (j = 0; j < vector_get_size(right->children); j++)
						{
							vector_push_back(child->children,
									vector_get_key_at(right->children, j));
							((b_tree_node_t) vector_get_key_at(right->children,
									j))->parent = child;
						}

						_b_tree_delete_node(right);
					}

					// The root may collapse
					if (vector_get_size(node->keys) == 0)
					{
						if (node == b_tree->root)
						{
							_b_tree_delete_node(b_tree->root);
							b_tree->root = child;
							child->parent = NULL;
						}
						else if (node->parent)
						{
							i = vector_search(node->parent->children, node,
									compare_pointers, NULL);
							vector_set_key_at(node->parent->children, i, child);
							child->parent = node->parent;
						}
					}
				}
			}

			if (child)
				return _b_tree_remove(b_tree, child, key, compare, context,
						degree);
		}
	}
	return NULL;
}

int b_tree_get_size(b_tree_t btree)
{
	_ASSERT(btree, ==, NULL, NULL_POINTER, -1);

	LOGGER("[b_tree_get_size] b-tree %p with size %d\n", btree, btree->size);

	return btree->size;
}