btree.c File Reference

B+tree implementation. More...

Include dependency graph for btree.c:

Go to the source code of this file.

Defines
#define	ROOT_NODE(n)   (!(n)->parent)
#define	INDEX_NODE(n)   ((n)->subtree[0] != NULL)
#define	LEAF_NODE(n)   ((n)->subtree[0] == NULL)
#define	FILL_FACTOR   ((BTREE_M-1)/2)
#define	MEDIAN_LOW_INDEX(n)   (((n)->keys-1)/2)
#define	MEDIAN_HIGH_INDEX(n)   ((n)->keys/2)
#define	MEDIAN_LOW(n)   ((n)->key[MEDIAN_LOW_INDEX((n))]);
#define	MEDIAN_HIGH(n)   ((n)->key[MEDIAN_HIGH_INDEX((n))]);
Functions
static void	btree_destroy_subtree (btree_node_t *root)
static void	_btree_insert (btree_t *t, btree_key_t key, void *value, btree_node_t *rsubtree, btree_node_t *node)
static void	_btree_remove (btree_t *t, btree_key_t key, btree_node_t *node)
static void	node_initialize (btree_node_t *node)
static void	node_insert_key_and_lsubtree (btree_node_t *node, btree_key_t key, void *value, btree_node_t *lsubtree)
static void	node_insert_key_and_rsubtree (btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree)
static void	node_remove_key_and_lsubtree (btree_node_t *node, btree_key_t key)
static void	node_remove_key_and_rsubtree (btree_node_t *node, btree_key_t key)
static btree_node_t *	node_split (btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree, btree_key_t *median)
static btree_node_t *	node_combine (btree_node_t *node)
static index_t	find_key_by_subtree (btree_node_t *node, btree_node_t *subtree, bool right)
static void	rotate_from_right (btree_node_t *lnode, btree_node_t *rnode, index_t idx)
static void	rotate_from_left (btree_node_t *lnode, btree_node_t *rnode, index_t idx)
static bool	try_insert_by_rotation_to_left (btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree)
static bool	try_insert_by_rotation_to_right (btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree)
static bool	try_rotation_from_left (btree_node_t *rnode)
static bool	try_rotation_from_right (btree_node_t *lnode)
void	btree_init (void)
void	btree_create (btree_t *t)
void	btree_destroy (btree_t *t)
void	btree_insert (btree_t *t, btree_key_t key, void *value, btree_node_t *leaf_node)
void	btree_remove (btree_t *t, btree_key_t key, btree_node_t *leaf_node)
void *	btree_search (btree_t *t, btree_key_t key, btree_node_t **leaf_node)
btree_node_t *	btree_leaf_node_left_neighbour (btree_t *t, btree_node_t *node)
btree_node_t *	btree_leaf_node_right_neighbour (btree_t *t, btree_node_t *node)
void	btree_print (btree_t *t)
Variables
static slab_cache_t *	btree_node_slab

---

Detailed Description

This file implements B+tree type and operations.

The B+tree has the following properties:

• it is a ballanced 3-4-5 tree (i.e. BTREE_M = 5)
• values (i.e. pointers to values) are stored only in leaves
• leaves are linked in a list

Be carefull when using these trees. They need to allocate and deallocate memory for their index nodes and as such can sleep.

Definition in file btree.c.

---