b+ tree implementation More...

#include <bplustree.h>
#include <memory.h>
#include <indexer.h>
#include <list.h>
#include <utils.h>

Classes
struct	bplustree_node_internal_t
	internal tree node More...

struct	bplustree_internal_t
	internal tree struct. used as metadata of index. More...

struct	bplustree_iterator_internal_t
	internal iterator struct More...

Typedefs
typedef struct bplustree_node_internal_t	bplustree_node_internal_t
	short hand for struct

typedef struct bplustree_internal_t	bplustree_internal_t
	short hand for struct

typedef struct bplustree_iterator_internal_t	bplustree_iterator_internal_t
	short hand for struct

Functions
	MODULE ("turnstone.lib")

int8_t	bplustree_insert (index_t idx, const void key, const void data, void *removed_data)

int8_t	bplustree_delete (index_t idx, const void key, void **deleted_data)

boolean_t	bplustree_contains (index_t idx, const void key)

const void *	bplustree_find (index_t idx, const void key)

iterator_t *	bplustree_search (index_t idx, const void key1, const void *key2, const index_key_search_criteria_t criteria)

uint64_t	bplustree_size (index_t *idx)

bplustree_node_internal_t *	bplustree_split_node (index_t idx, bplustree_node_internal_t node, void **ptr_par_key)
	splits node into two half with min key constraint.

const void *	bplustree_get_min_key (index_t idx, const bplustree_node_internal_t node)
	finds left leaf min key

int8_t	bplustree_toss_root (index_t *idx)
	toss root, so level of tree become smaller.

iterator_t *	bplustree_iterator_create (index_t *idx)
	creates b+ tree iterator

int8_t	bplustree_iterator_destroy (iterator_t *iterator)
	destroys the iterator

int8_t	bplustree_iterator_end_of_index (iterator_t *iterator)
	returns 0 at and of tree

iterator_t *	bplustree_iterator_next (iterator_t *iterator)
	fetches next key/value

const void *	bplustree_iterator_get_key (iterator_t *iterator)
	returns current key at iterator.

const void *	bplustree_iterator_get_data (iterator_t *iterator)
	returns current data at iterator.

int8_t	bplustree_set_comparator_for_unique_subpart_for_non_unique_index (index_t *idx, index_key_comparator_f comparator)
	sets a comparator for unique subpart for non unique index

int8_t	bplustree_set_key_destroyer (index_t *idx, bplustree_key_destroyer_f destroyer)
	sets a key destroyer for index

int8_t	bplustree_set_key_cloner (index_t *idx, bplustree_key_cloner_f cloner)
	sets a key cloner for index

index_t *	bplustree_create_index_with_heap_and_unique (memory_heap_t *heap, uint64_t max_key_count, index_key_comparator_f comparator, boolean_t unique)
	creates b+ tree index implementation

int8_t	bplustree_destroy_index (index_t *idx)
	destroys index

Detailed Description

b+ tree implementation

This work is licensed under TURNSTONE OS Public License. Please read and understand latest version of Licence.

Function Documentation

◆ bplustree_contains()

boolean_t bplustree_contains	(	index_t *	idx,
		const void *	key )

b+ tree contains implementation. see also index_t contains method

◆ bplustree_create_index_with_heap_and_unique()

index_t * bplustree_create_index_with_heap_and_unique	(	memory_heap_t *	heap,
		uint64_t	max_key_count,
		index_key_comparator_f	comparator,
		boolean_t	unique )

creates b+ tree index implementation

Parameters

heap	heap to use
max_key_count	maximum key count at each tree node
comparator	key comparator
unique	if unique flag set remove and insert key,value

Returns: index interface

◆ bplustree_delete()

int8_t bplustree_delete	(	index_t *	idx,
		const void *	key,
		void **	deleted_data )

b+ tree delete implementation. see also index_t delete method

◆ bplustree_destroy_index()

int8_t bplustree_destroy_index ( index_t * idx )

destroys index

Parameters

[in] idx index to be destroyed

Returns: 0 if successed.

destroys only b+tree not data. if data will not be destroyed a memory leak will be happened.

◆ bplustree_find()

const void * bplustree_find	(	index_t *	idx,
		const void *	key )

b+ tree find implementation. see also index_t find method

◆ bplustree_get_min_key()

const void * bplustree_get_min_key	(	index_t *	idx,
		const bplustree_node_internal_t *	node )

finds left leaf min key

Parameters

[in] node node to start search

Returns: min key.

◆ bplustree_insert()

int8_t bplustree_insert	(	index_t *	idx,
		const void *	key,
		const void *	data,
		void **	removed_data )

b+ tree insert implementation. see also index_t insert method

◆ bplustree_iterator_create()

iterator_t * bplustree_iterator_create ( index_t * idx )

creates b+ tree iterator

Parameters

[in] idx source of b+ tree

Returns: iterator

the iterator travels only leaf nodes.

◆ bplustree_iterator_destroy()

int8_t bplustree_iterator_destroy ( iterator_t * iterator )

destroys the iterator

Parameters

[in] iterator iterator to destroy

Returns: 0 if succeed

◆ bplustree_iterator_end_of_index()

int8_t bplustree_iterator_end_of_index ( iterator_t * iterator )

returns 0 at and of tree

Parameters

[in] iterator iterator to check

Returns: 0 if end of tree.

◆ bplustree_iterator_get_data()

const void * bplustree_iterator_get_data ( iterator_t * iterator )

returns current data at iterator.

Parameters

[in] iterator iterator to get data

Returns: the data.

◆ bplustree_iterator_get_key()

const void * bplustree_iterator_get_key ( iterator_t * iterator )

returns current key at iterator.

Parameters

[in] iterator iterator to get key

Returns: the key.

◆ bplustree_iterator_next()

iterator_t * bplustree_iterator_next ( iterator_t * iterator )

fetches next key/value

Parameters

[in] iterator iterator to travel

Returns: itself

◆ bplustree_search()

iterator_t * bplustree_search	(	index_t *	idx,
		const void *	key1,
		const void *	key2,
		const index_key_search_criteria_t	criteria )

b+ tree search implementation. see also index_t search method

◆ bplustree_set_comparator_for_unique_subpart_for_non_unique_index()

int8_t bplustree_set_comparator_for_unique_subpart_for_non_unique_index	(	index_t *	idx,
		index_key_comparator_f	comparator )

sets a comparator for unique subpart for non unique index

Parameters

[in]	idx	index
[in]	comparator	comparator

Returns: 0 if successed.

◆ bplustree_set_key_cloner()

int8_t bplustree_set_key_cloner	(	index_t *	idx,
		bplustree_key_cloner_f	cloner )

sets a key cloner for index

Parameters

[in]	idx	index
[in]	cloner	cloner

Returns: 0 if successed.

◆ bplustree_set_key_destroyer()

int8_t bplustree_set_key_destroyer	(	index_t *	idx,
		bplustree_key_destroyer_f	destroyer )

sets a key destroyer for index

Parameters

[in]	idx	index
[in]	destroyer	destroyer

Returns: 0 if successed.

◆ bplustree_size()

uint64_t bplustree_size ( index_t * idx )

b+ tree size implementation.

◆ bplustree_split_node()

bplustree_node_internal_t * bplustree_split_node	(	index_t *	idx,
		bplustree_node_internal_t *	node,
		void **	ptr_par_key )

splits node into two half with min key constraint.

Parameters

[in]	idx	b+ tree index
[in]	node	source node
[out]	ptr_par_key	the middle key of partition (right node min key)

Returns: new node (right one)

◆ bplustree_toss_root()

int8_t bplustree_toss_root ( index_t * idx )

toss root, so level of tree become smaller.

Parameters

[in] idx b+ tree index

Returns: 0 if succeed.

Classes

Typedefs

Functions

Detailed Description

Function Documentation

◆ bplustree_contains()

◆ bplustree_create_index_with_heap_and_unique()

◆ bplustree_delete()

◆ bplustree_destroy_index()

◆ bplustree_find()

◆ bplustree_get_min_key()

◆ bplustree_insert()

◆ bplustree_iterator_create()

◆ bplustree_iterator_destroy()

◆ bplustree_iterator_end_of_index()

◆ bplustree_iterator_get_data()

◆ bplustree_iterator_get_key()

◆ bplustree_iterator_next()

◆ bplustree_search()

◆ bplustree_set_comparator_for_unique_subpart_for_non_unique_index()

◆ bplustree_set_key_cloner()

◆ bplustree_set_key_destroyer()

◆ bplustree_size()

◆ bplustree_split_node()

◆ bplustree_toss_root()