nemea-common 1.6.3
Data Structures
b_plus_tree.h File Reference

B+ tree data structure. More...

Go to the source code of this file.

Data Structures

struct  bpt_t
 Structure - B+ tree - main structure Structure used to keep informations about tree. More...
 
struct  bpt_nd_t
 Structure - B+ tree - node structure Structure used to keep information about node and pointer to inner or leaf node. More...
 
struct  bpt_list_item_t
 Structure - B+ tree - list item structure Structure used to create list of items. More...
 

Return codes from compare function

Function for comparing two keys shod return one of these values. Example function for int values: int compare_int(void <em>key1, void *key2) { int a = *((int)key1), b = *((int*)key2); if (a < b) { return LESS; } else if (a > b) { return MORE; } else { return EQUAL; } }

#define EQUAL   0
 
#define LESS   -1
 
#define MORE   1
 
typedef struct bpt_nd_t bpt_nd_t
 
typedef struct bpt_t bpt_t
 Structure - B+ tree - main structure Structure used to keep informations about tree.
 
typedef struct bpt_list_item_t bpt_list_item_t
 Structure - B+ tree - list item structure Structure used to create list of items.
 
bpt_tbpt_init (unsigned int size_of_btree_node, int(*comp)(void *, void *), unsigned int size_of_value, unsigned int size_of_key)
 Initialization of B+ tree Function creates main structure of the B+ tree.
 
void bpt_clean (bpt_t *btree)
 Destroy B+ tree Function removes all the keys, values and nodes in the tree. The main structure is than deallocated.
 
void * bpt_search_or_insert (bpt_t *btree, void *key)
 Insert or find item in B+ tree Function tries to find key in the tree. If the key is found, the appropriate value is returned. Otherwise it inserts key into the tree and allocates and zeroes space for a new value which is returned.
 
void * bpt_insert (bpt_t *btree, void *key)
 Insert item to B+ tree Function inserts key to the tree and allocates and zeroes space for value, which is returned. If the key is already in the tree, the NULL is returned.
 
void * bpt_search (bpt_t *btree, void *key)
 Search item in B+ tree Function find item in the tree and returns it's value. If the key is not in the tree, NULL is returned.
 
int bpt_item_del (bpt_t *btree, void *key)
 Remove item from B+ tree Function searches key in B+ tree and removes the item from it.
 
unsigned long int bpt_item_cnt (bpt_t *btree)
 Items count in B+ tree Function returns count of item in B+ tree. (Getter of btree->count_of_values)
 
bpt_list_item_tbpt_list_init (bpt_t *btree)
 Initialization of iteration structure. Function allocates structure used for iteration.
 
int bpt_list_start (bpt_t *tree, bpt_list_item_t *item)
 Reset iteration Function reset the iteration structure to point to the first item in the sorted list. Key is than stored in item->key and value in item->value.
 
int bpt_list_item_next (bpt_t *tree, bpt_list_item_t *item)
 Get next item from list Function sets the iteration structure to next item in the list. Actual key is than stored in item->key and value in item->value.
 
int bpt_list_item_del (bpt_t *btree, bpt_list_item_t *delete_item)
 Remove item Function removes actual item in the iteration structure and sets iteration to next item in the list (if it was not the last one). (The item will be removed in B+ tree. Do not use function bpt_item_del() while iterating the list.)
 
void bpt_list_clean (bpt_list_item_t *item)
 Destroy b+ tree Function deallocates the iteration structure.
 

Detailed Description

B+ tree data structure.

Author
Zdenek Rosa rosaz.nosp@m.den@.nosp@m.fit.c.nosp@m.vut..nosp@m.cz
Date
2014

Definition in file b_plus_tree.h.

Macro Definition Documentation

◆ EQUAL

#define EQUAL   0

Definition at line 62 of file b_plus_tree.h.

◆ LESS

#define LESS   -1

Definition at line 63 of file b_plus_tree.h.

◆ MORE

#define MORE   1

Definition at line 64 of file b_plus_tree.h.

Typedef Documentation

◆ bpt_list_item_t

typedef struct bpt_list_item_t bpt_list_item_t

Structure - B+ tree - list item structure Structure used to create list of items.

◆ bpt_nd_t

typedef struct bpt_nd_t bpt_nd_t

Definition at line 70 of file b_plus_tree.h.

◆ bpt_t

typedef struct bpt_t bpt_t

Structure - B+ tree - main structure Structure used to keep informations about tree.

Function Documentation

◆ bpt_clean()

void bpt_clean ( bpt_t * btree)

Destroy B+ tree Function removes all the keys, values and nodes in the tree. The main structure is than deallocated.

Parameters
[in]btreepointer to B+ tree main structure

◆ bpt_init()

bpt_t * bpt_init ( unsigned int size_of_btree_node,
int(*)(void *, void *) comp,
unsigned int size_of_value,
unsigned int size_of_key )

Initialization of B+ tree Function creates main structure of the B+ tree.

Parameters
[in]size_of_btree_nodecount of items in one node.
[in]comppointer to key comparing function. Function should have two attributes (to get the keys), then it should return value EQUAL, MORE or LESS.
[in]size_of_keysize of key.
[in]size_of_valuesize of value.
Returns
pointer to created bpt_t structure.

◆ bpt_insert()

void * bpt_insert ( bpt_t * btree,
void * key )

Insert item to B+ tree Function inserts key to the tree and allocates and zeroes space for value, which is returned. If the key is already in the tree, the NULL is returned.

Parameters
[in]btreepointer to B+ tree.
[in]keykey to insert.
Returns
pointer to value or NULL.

◆ bpt_item_cnt()

unsigned long int bpt_item_cnt ( bpt_t * btree)

Items count in B+ tree Function returns count of item in B+ tree. (Getter of btree->count_of_values)

Parameters
[in]btreepointer to B+ tree.
Returns
count of items.

◆ bpt_item_del()

int bpt_item_del ( bpt_t * btree,
void * key )

Remove item from B+ tree Function searches key in B+ tree and removes the item from it.

Parameters
[in]btreepointer to B+ tree.
[in]keykey to delete.
Returns
1 ON SUCCESS, OTHERWISE 0.

◆ bpt_list_clean()

void bpt_list_clean ( bpt_list_item_t * item)

Destroy b+ tree Function deallocates the iteration structure.

Parameters
[in]itempointer to iteration structure.

◆ bpt_list_init()

bpt_list_item_t * bpt_list_init ( bpt_t * btree)

Initialization of iteration structure. Function allocates structure used for iteration.

Parameters
[in]btreepointer to B+ tree.
Returns
pointer to the allocated structure.

◆ bpt_list_item_del()

int bpt_list_item_del ( bpt_t * btree,
bpt_list_item_t * delete_item )

Remove item Function removes actual item in the iteration structure and sets iteration to next item in the list (if it was not the last one). (The item will be removed in B+ tree. Do not use function bpt_item_del() while iterating the list.)

Parameters
[in]btreepointer to tree.
[in,out]delete_itemstructure to list item.
Returns
1 ON SUCCESS, 0 END OF LIST.

◆ bpt_list_item_next()

int bpt_list_item_next ( bpt_t * tree,
bpt_list_item_t * item )

Get next item from list Function sets the iteration structure to next item in the list. Actual key is than stored in item->key and value in item->value.

Parameters
[in]treepointer to B+ tree.
[in,out]itempointer to iteration structure.
Returns
1 ON SUCCESS, 0 END OF LIST.

◆ bpt_list_start()

int bpt_list_start ( bpt_t * tree,
bpt_list_item_t * item )

Reset iteration Function reset the iteration structure to point to the first item in the sorted list. Key is than stored in item->key and value in item->value.

Parameters
[in]treepointer to B+ tree.
[out]itempointer to iteration structure.
Returns
1 ON SUCCESS, 0 tree is empty.

◆ bpt_search()

void * bpt_search ( bpt_t * btree,
void * key )

Search item in B+ tree Function find item in the tree and returns it's value. If the key is not in the tree, NULL is returned.

Parameters
[in]btreepointer to B+ tree.
[in]keykey to search.
Returns
pointer to value or NULL.

◆ bpt_search_or_insert()

void * bpt_search_or_insert ( bpt_t * btree,
void * key )

Insert or find item in B+ tree Function tries to find key in the tree. If the key is found, the appropriate value is returned. Otherwise it inserts key into the tree and allocates and zeroes space for a new value which is returned.

Parameters
[in]btreepointer to B+ tree.
[in]keykey to insert.
Returns
pointer to the value. New allocated or found in the tree.