bpp_tree.h
Go to the documentation of this file.
1 /******************************************************************************/
34 /******************************************************************************/
35 
36 #if !defined(BPP_TREE_H_)
37 #define BPP_TREE_H_
38 
39 #if defined(__cplusplus)
40 extern "C" {
41 #endif
42 
43 #include <stdio.h>
44 #include <stdlib.h>
45 #include <stdarg.h>
46 #include <string.h>
47 #include <stdint.h>
48 #include "../../key_value/kv_system.h"
49 #include "./../dictionary.h"
50 #include "./../../file/ion_file.h"
51 
52 /****************************
53  * implementation dependent *
54  ****************************/
55 typedef long ion_bpp_external_address_t; /* record address for external record */
56 typedef long ion_bpp_address_t; /* record address for btree node */
57 
58 #define ION_CC_EQ 0
59 #define ION_CC_GT 1
60 #define ION_CC_LT -1
61 
62 /* compare two keys and return:
63  * CC_LT key1 < key2
64  * CC_GT key1 > key2
65  * CC_EQ key1 = key2
66 */
67 typedef char (*ion_bpp_comparison_t)(
68  ion_key_t key1,
69  ion_key_t key2,
70  ion_key_size_t size
71 );
72 
73 /* typedef int (*ion_bpp_comparison_t)(const void *key1, const void *key2, unsigned int size); */
74 
75 /******************************
76  * implementation independent *
77  ******************************/
78 
79 /* statistics */
80 int maxHeight; /* maximum height attained */
81 int nNodesIns; /* number of nodes inserted */
82 int nNodesDel; /* number of nodes deleted */
83 int nKeysIns; /* number of keys inserted */
84 int nKeysDel; /* number of keys deleted */
85 int nDiskReads; /* number of disk reads */
86 int nDiskWrites;/* number of disk writes */
87 
88 /* line number for last IO or memory error */
90 
92 
93 /* typedef enum {false, true} bool; */
94 typedef enum ION_BPP_ERR {
97 
98 typedef void *ion_bpp_handle_t;
99 
100 typedef struct {
101  /* info for bOpen() */
102  char *iName; /* name of index file */
103  int keySize;/* length, in bytes, of key */
104  ion_bpp_bool_t dupKeys; /* true if duplicate keys allowed */
105  size_t sectorSize; /* size of sector on disk */
106  ion_bpp_comparison_t comp; /* pointer to compare function */
108 
109 /***********************
110  * function prototypes *
111  ***********************/
112 ion_bpp_err_t
113 b_open(
114  ion_bpp_open_t info,
115  ion_bpp_handle_t *handle
116 );
117 
118 /*
119  * input:
120  * info info for open
121  * output:
122  * handle handle to btree, used in subsequent calls
123  * returns:
124  * bErrOk open was successful
125  * bErrMemory insufficient memory
126  * bErrSectorSize sector size too small or not 0 mod 4
127  * bErrFileNotOpen unable to open index file
128 */
129 
130 ion_bpp_err_t
131 b_close(
132  ion_bpp_handle_t handle
133 );
134 
135 /*
136  * input:
137  * handle handle returned by bOpen
138  * returns:
139  * bErrOk file closed, resources deleted
140 */
141 
142 ion_bpp_err_t
143 b_insert(
144  ion_bpp_handle_t handle,
145  void *key,
146  ion_bpp_external_address_t rec
147 );
148 
149 /*
150  * input:
151  * handle handle returned by bOpen
152  * key key to insert
153  * rec record address
154  * returns:
155  * bErrOk operation successful
156  * bErrDupKeys duplicate keys (and info.dupKeys = false)
157  * notes:
158  * If dupKeys is false, then all records inserted must have a
159  * unique key. If dupkeys is true, then duplicate keys are
160  * allowed, but they must all have unique record addresses.
161  * In this case, record addresses are included in internal
162  * nodes to generate a "unique" key.
163 */
164 
165 ion_bpp_err_t
166 b_update(
167  ion_bpp_handle_t handle,
168  void *key,
169  ion_bpp_external_address_t rec
170 );
171 
172 /*
173  * input:
174  * handle handle returned by bOpen
175  * key key to update
176  * rec record address
177  * returns:
178  * bErrOk operation successful
179  * bErrDupKeys duplicate keys (and info.dupKeys = false)
180  * notes:
181  * If dupKeys is false, then all records updated must have a
182  * unique key. If dupkeys is true, then duplicate keys are
183  * allowed, but they must all have unique record addresses.
184  * In this case, record addresses are included in internal
185  * nodes to generate a "unique" key.
186 */
187 
188 ion_bpp_err_t
189 b_delete(
190  ion_bpp_handle_t handle,
191  void *key,
192  ion_bpp_external_address_t *rec
193 );
194 
195 /*
196  * input:
197  * handle handle returned by bOpen
198  * key key to delete
199  * rec record address of key to delete
200  * output:
201  * rec record address deleted
202  * returns:
203  * bErrOk operation successful
204  * bErrKeyNotFound key not found
205  * notes:
206  * If dupKeys is false, all keys are unique, and rec is not used
207  * to determine which key to delete. If dupKeys is true, then
208  * rec is used to determine which key to delete.
209 */
210 
211 ion_bpp_err_t
212 b_get(
213  ion_bpp_handle_t handle,
214  void *key,
215  ion_bpp_external_address_t *rec
216 );
217 
218 /*
219  * input:
220  * handle handle returned by bOpen
221  * key key to find
222  * output:
223  * rec record address
224  * returns:
225  * bErrOk operation successful
226  * bErrKeyNotFound key not found
227 */
228 
229 ion_bpp_err_t
231  ion_bpp_handle_t handle,
232  void *key,
233  void *mkey,
234  ion_bpp_external_address_t *rec
235 );
236 
237 /*
238  * input:
239  * handle handle returned by bOpen
240  * key key to find
241  * output:
242  * mkey key associated with the found offset
243  * rec record address of least element greater than or equal to
244  * returns:
245  * bErrOk operation successful
246 */
247 
248 ion_bpp_err_t
250  ion_bpp_handle_t handle,
251  void *key,
252  ion_bpp_external_address_t *rec
253 );
254 
255 /*
256  * input:
257  * handle handle returned by bOpen
258  * output:
259  * key first key in sequential set
260  * rec record address
261  * returns:
262  * bErrOk operation successful
263  * bErrKeyNotFound key not found
264 */
265 
266 ion_bpp_err_t
268  ion_bpp_handle_t handle,
269  void *key,
270  ion_bpp_external_address_t *rec
271 );
272 
273 /*
274  * input:
275  * handle handle returned by bOpen
276  * output:
277  * key last key in sequential set
278  * rec record address
279  * returns:
280  * bErrOk operation successful
281  * bErrKeyNotFound key not found
282 */
283 
284 ion_bpp_err_t
286  ion_bpp_handle_t handle,
287  void *key,
288  ion_bpp_external_address_t *rec
289 );
290 
291 /*
292  * input:
293  * handle handle returned by bOpen
294  * output:
295  * key key found
296  * rec record address
297  * returns:
298  * bErrOk operation successful
299  * bErrKeyNotFound key not found
300 */
301 
302 #if defined(__cplusplus)
303 }
304 #endif
305 
306 #endif
ion_bpp_bool_t dupKeys
Definition: bpp_tree.h:104
ion_bpp_err_t b_insert(ion_bpp_handle_t handle, void *key, ion_bpp_external_address_t rec)
Definition: bpp_tree.c:1155
enum ION_BPP_ERR ion_bpp_err_t
ion_boolean_e ion_bpp_bool_t
Definition: bpp_tree.h:91
int nDiskReads
Definition: bpp_tree.h:85
int nKeysDel
Definition: bpp_tree.h:84
ion_bpp_err_t b_find_first_greater_or_equal(ion_bpp_handle_t handle, void *key, void *mkey, ion_bpp_external_address_t *rec)
Definition: bpp_tree.c:1104
ion_bpp_err_t b_find_next_key(ion_bpp_handle_t handle, void *key, ion_bpp_external_address_t *rec)
Definition: bpp_tree.c:1657
int maxHeight
Definition: bpp_tree.h:80
int nNodesDel
Definition: bpp_tree.h:82
ion_bpp_err_t b_find_last_key(ion_bpp_handle_t handle, void *key, ion_bpp_external_address_t *rec)
Definition: bpp_tree.c:1627
#define key(k)
Definition: bpp_tree.c:75
size_t sectorSize
Definition: bpp_tree.h:105
ion_bpp_err_t b_open(ion_bpp_open_t info, ion_bpp_handle_t *handle)
Definition: bpp_tree.c:887
long ion_bpp_address_t
Definition: bpp_tree.h:56
void * ion_key_t
A dictionary key.
Definition: kv_system.h:241
int nDiskWrites
Definition: bpp_tree.h:86
ion_bpp_err_t b_get(ion_bpp_handle_t handle, void *key, ion_bpp_external_address_t *rec)
Definition: bpp_tree.c:1062
char(* ion_bpp_comparison_t)(ion_key_t key1, ion_key_t key2, ion_key_size_t size)
Definition: bpp_tree.h:67
ion_bpp_comparison_t comp
Definition: bpp_tree.h:106
int nKeysIns
Definition: bpp_tree.h:83
long ion_bpp_external_address_t
Definition: bpp_tree.h:55
void * ion_bpp_handle_t
Definition: bpp_tree.h:98
ion_bpp_err_t b_delete(ion_bpp_handle_t handle, void *key, ion_bpp_external_address_t *rec)
Definition: bpp_tree.c:1441
int bErrLineNo
Definition: bpp_tree.h:89
#define rec(k)
Definition: bpp_tree.c:76
ion_bpp_err_t b_update(ion_bpp_handle_t handle, void *key, ion_bpp_external_address_t rec)
Definition: bpp_tree.c:1333
int ion_key_size_t
The size (length) of a dictionary key in bytes.
Definition: kv_system.h:251
ion_bpp_err_t b_close(ion_bpp_handle_t handle)
Definition: bpp_tree.c:1028
int nNodesIns
Definition: bpp_tree.h:81
enum ION_BOOLEAN ion_boolean_e
Boolean values.
char * iName
Definition: bpp_tree.h:102
ion_bpp_err_t b_find_first_key(ion_bpp_handle_t handle, void *key, ion_bpp_external_address_t *rec)
Definition: bpp_tree.c:1586
ION_BPP_ERR
Definition: bpp_tree.h:94