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 
70 typedef struct bpt_nd_t bpt_nd_t;
71 
76 typedef 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 */
83 } bpt_t;
84 
89 struct 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 
101 typedef 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 
124 bpt_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 
135 void bpt_clean(bpt_t *btree);
136 
147 void *bpt_search_or_insert(bpt_t *btree, void *key);
148 
158 void *bpt_insert(bpt_t *btree, void *key);
159 
168 void *bpt_search(bpt_t *btree, void *key);
169 
170 
179 int bpt_item_del(bpt_t *btree, void *key);
180 
188 unsigned 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 
212 int bpt_list_start(bpt_t *tree, bpt_list_item_t *item);
213 
214 
223 int bpt_list_item_next(bpt_t *tree, bpt_list_item_t *item);
224 
235 int bpt_list_item_del(bpt_t *btree, bpt_list_item_t *delete_item);
236 
242 void bpt_list_clean(bpt_list_item_t *item);
243 
244 #endif /* _B_PLUS_TREE_ */
245 
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...
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...
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...
int size_of_value
Definition: b_plus_tree.h:79
void bpt_list_clean(bpt_list_item_t *item)
Destroy b+ tree Function deallocates the iteration structure.
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_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...
bpt_nd_t * leaf
Definition: b_plus_tree.h:104
int count
Definition: b_plus_tree.h:94
bpt_list_item_t * bpt_list_init(bpt_t *btree)
Initialization of iteration structure. Function allocates structure used for iteration.
Structure - B+ tree - main structure Structure used to keep informations about tree.
Definition: b_plus_tree.h:76
int(* compare)(void *, void *)
Definition: b_plus_tree.h:82
struct bpt_list_item_t bpt_list_item_t
Structure - B+ tree - list item structure Structure used to create list of items. ...
void * bpt_search(bpt_t *btree, void *key)
Search item in B+ tree Function find item in the tree and returns it&#39;s value. If the key is not in th...
unsigned long int count_of_values
Definition: b_plus_tree.h:77
Structure - B+ tree - node structure Structure used to keep information about node and pointer to inn...
Definition: b_plus_tree.h:89
void * key
Definition: b_plus_tree.h:93
unsigned int index_of_value
Definition: b_plus_tree.h:105
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.
Structure - B+ tree - list item structure Structure used to create list of items. ...
Definition: b_plus_tree.h:101
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 m
Definition: b_plus_tree.h:78
bpt_nd_t * parent
Definition: b_plus_tree.h:92
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...
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 th...
int size_of_key
Definition: b_plus_tree.h:80
unsigned char state_extend
Definition: b_plus_tree.h:91
void * extend
Definition: b_plus_tree.h:90
bpt_nd_t * root
Definition: b_plus_tree.h:81