nemea-common 1.6.3
b_plus_tree.h
Go to the documentation of this file.
1
7/*
8 * Copyright (C) 2014 CESNET
9 *
10 * LICENSE TERMS
11 *
12 * Redistribution and use in source and binary forms, with or without
13 * modification, are permitted provided that the following conditions
14 * are met:
15 * 1. Redistributions of source code must retain the above copyright
16 * notice, this list of conditions and the following disclaimer.
17 * 2. Redistributions in binary form must reproduce the above copyright
18 * notice, this list of conditions and the following disclaimer in
19 * the documentation and/or other materials provided with the
20 * distribution.
21 * 3. Neither the name of the Company nor the names of its contributors
22 * may be used to endorse or promote products derived from this
23 * software without specific prior written permission.
24 *
25 * ALTERNATIVELY, provided that this notice is retained in full, this
26 * product may be distributed under the terms of the GNU General Public
27 * License (GPL) version 2 or later, in which case the provisions
28 * of the GPL apply INSTEAD OF those given above.
29 *
30 * This software is provided ``as is'', and any express or implied
31 * warranties, including, but not limited to, the implied warranties of
32 * merchantability and fitness for a particular purpose are disclaimed.
33 * In no event shall the company or contributors be liable for any
34 * direct, indirect, incidental, special, exemplary, or consequential
35 * damages (including, but not limited to, procurement of substitute
36 * goods or services; loss of use, data, or profits; or business
37 * interruption) however caused and on any theory of liability, whether
38 * in contract, strict liability, or tort (including negligence or
39 * otherwise) arising in any way out of the use of this software, even
40 * if advised of the possibility of such damage.
41 *
42 */
43#ifndef _B_PLUS_TREE_
44#define _B_PLUS_TREE_
45
62#define EQUAL 0
63#define LESS -1
64#define MORE 1
65 /* /} */
66
67// Public Structures
68// -----------------
69
70typedef struct bpt_nd_t bpt_nd_t;
71
76typedef struct bpt_t {
77 unsigned long int count_of_values; /*< count of values in tree */
78 int m; /*< count of descendant in node */
79 int size_of_value; /*< size of value */
80 int size_of_key; /*< size of key */
81 bpt_nd_t *root; /*< root node */
82 int (*compare) (void *, void *); /*< compare function for key */
84
89struct bpt_nd_t {
90 void *extend; /*< pointer to leaf or inner node */
91 unsigned char state_extend; /*< type of extended variable. leaf or inner node */
92 bpt_nd_t *parent; /*< pointer to parent */
93 void *key; /*< pointer to key */
94 int count; /*< count of descendants */
95};
96
101typedef struct bpt_list_item_t {
102 void *value; /*< pointer to value */
103 void *key; /*< pointer to key */
104 bpt_nd_t *leaf; /*< pointer to actual leaf */
105 unsigned int index_of_value; /*< index of value in actual leaf */
107
108// Main Functions
109// --------------
110// Functions for basic usage of the tree:
111// initialization, destruction, inserting items, searching items, deleting items
112
124bpt_t *bpt_init(unsigned int size_of_btree_node,
125 int (*comp)(void *, void *),
126 unsigned int size_of_value,
127 unsigned int size_of_key);
128
135void bpt_clean(bpt_t *btree);
136
147void *bpt_search_or_insert(bpt_t *btree, void *key);
148
158void *bpt_insert(bpt_t *btree, void *key);
159
168void *bpt_search(bpt_t *btree, void *key);
169
170
179int bpt_item_del(bpt_t *btree, void *key);
180
188unsigned long int bpt_item_cnt(bpt_t *btree);
189
190// LIST
191// ----
192// Iterating through all the items in the tree.
193// Items are sorted by their key.
194
202
213
214
224
235int bpt_list_item_del(bpt_t *btree, bpt_list_item_t *delete_item);
236
243
244#endif /* _B_PLUS_TREE_ */
245
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_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,...
struct bpt_list_item_t bpt_list_item_t
Structure - B+ tree - list item structure Structure used to create list of items.
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,...
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....
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 i...
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 th...
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)
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.
void bpt_list_clean(bpt_list_item_t *item)
Destroy b+ tree Function deallocates the iteration structure.
struct bpt_t bpt_t
Structure - B+ tree - main structure Structure used to keep informations about tree.
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....
void bpt_clean(bpt_t *btree)
Destroy B+ tree Function removes all the keys, values and nodes in the tree. The main structure is th...
bpt_list_item_t * bpt_list_init(bpt_t *btree)
Initialization of iteration structure. Function allocates structure used for iteration.
Structure - B+ tree - list item structure Structure used to create list of items.
bpt_nd_t * leaf
unsigned int index_of_value
Structure - B+ tree - node structure Structure used to keep information about node and pointer to inn...
Definition b_plus_tree.h:89
void * extend
Definition b_plus_tree.h:90
void * key
Definition b_plus_tree.h:93
unsigned char state_extend
Definition b_plus_tree.h:91
bpt_nd_t * parent
Definition b_plus_tree.h:92
Structure - B+ tree - main structure Structure used to keep informations about tree.
Definition b_plus_tree.h:76
unsigned long int count_of_values
Definition b_plus_tree.h:77
int size_of_key
Definition b_plus_tree.h:80
int(* compare)(void *, void *)
Definition b_plus_tree.h:82
int m
Definition b_plus_tree.h:78
int size_of_value
Definition b_plus_tree.h:79
bpt_nd_t * root
Definition b_plus_tree.h:81