nemea-common 1.6.3
|
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_t * | bpt_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_t * | bpt_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. | |
#define EQUAL 0 |
Definition at line 62 of file b_plus_tree.h.
#define LESS -1 |
Definition at line 63 of file b_plus_tree.h.
#define MORE 1 |
Definition at line 64 of file b_plus_tree.h.
typedef struct bpt_list_item_t bpt_list_item_t |
Structure - B+ tree - list item structure Structure used to create list of items.
typedef struct bpt_nd_t bpt_nd_t |
Definition at line 70 of file b_plus_tree.h.
typedef struct bpt_t bpt_t |
Structure - B+ tree - main structure Structure used to keep informations about 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.
[in] | btree | pointer to B+ tree main structure |
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.
[in] | size_of_btree_node | count of items in one node. |
[in] | comp | pointer 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_key | size of key. |
[in] | size_of_value | size of value. |
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.
[in] | btree | pointer to B+ tree. |
[in] | key | key to insert. |
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)
[in] | btree | pointer to B+ tree. |
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.
[in] | btree | pointer to B+ tree. |
[in] | key | key to delete. |
void bpt_list_clean | ( | bpt_list_item_t * | item | ) |
Destroy b+ tree Function deallocates the iteration structure.
[in] | item | pointer to iteration structure. |
bpt_list_item_t * bpt_list_init | ( | bpt_t * | btree | ) |
Initialization of iteration structure. Function allocates structure used for iteration.
[in] | btree | pointer to B+ tree. |
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.)
[in] | btree | pointer to tree. |
[in,out] | delete_item | structure to list item. |
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.
[in] | tree | pointer to B+ tree. |
[in,out] | item | pointer to iteration structure. |
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.
[in] | tree | pointer to B+ tree. |
[out] | item | pointer to iteration structure. |
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.
[in] | btree | pointer to B+ tree. |
[in] | key | key to search. |
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.
[in] | btree | pointer to B+ tree. |
[in] | key | key to insert. |