Branch data Line data Source code
1 : : /* -*- Mode: C++; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2 : : /*
3 : : * Generic B+Tree
4 : : * (C) 2013 Jung-Sang Ahn <jungsang.ahn@gmail.com>
5 : : */
6 : :
7 : : #include <stdio.h>
8 : : #include <stdlib.h>
9 : : #include <string.h>
10 : : #include <assert.h>
11 : :
12 : : #include "btree.h"
13 : : #include "common.h"
14 : :
15 : : #include "list.h"
16 : :
17 : : #ifdef __DEBUG
18 : : #include "memleak.h"
19 : : #ifndef __DEBUG_BTREE
20 : : #undef DBG
21 : : #undef DBGCMD
22 : : #undef DBGSW
23 : : #define DBG(...)
24 : : #define DBGCMD(...)
25 : : #define DBGSW(n, ...)
26 : : #endif
27 : : #endif
28 : :
29 : : #define METASIZE_ALIGN_UNIT (16)
30 : : #ifdef METASIZE_ALIGN_UNIT
31 : : #define _metasize_align(size) \
32 : : (((( (size + sizeof(metasize_t)) + (METASIZE_ALIGN_UNIT-1)) \
33 : : / METASIZE_ALIGN_UNIT) * METASIZE_ALIGN_UNIT) - sizeof(metasize_t))
34 : : #else
35 : : #define _metasize_align(size) (size)
36 : : #endif
37 : :
38 : 124724593 : INLINE int is_subblock(bid_t subbid)
39 : : {
40 : : uint8_t flag;
41 : 124724593 : flag = (subbid >> (8 * (sizeof(bid_t)-2))) & 0x00ff;
42 : 124724593 : return flag;
43 : : }
44 : :
45 : 148729749 : INLINE struct bnode *_fetch_bnode(struct btree *btree, void *addr, uint16_t level)
46 : : {
47 : 148729749 : struct bnode *node = NULL;
48 : :
49 : 148729749 : node = (struct bnode *)addr;
50 : :
51 [ + + ]: 148729749 : if (!(node->flag & BNODE_MASK_METADATA)) {
52 : : // no metadata
53 : 63908403 : node->data = (uint8_t *)addr + sizeof(struct bnode);
54 : : } else {
55 : : // metadata
56 : : metasize_t metasize;
57 : 84821346 : memcpy(&metasize, (uint8_t *)addr + sizeof(struct bnode), sizeof(metasize_t));
58 : 84821346 : metasize = _endian_decode(metasize);
59 : : node->data = (uint8_t *)addr + sizeof(struct bnode) + sizeof(metasize_t) +
60 : 84821346 : _metasize_align(metasize);
61 : : }
62 : 148729749 : return node;
63 : : }
64 : :
65 : 26370247 : struct bnode ** btree_get_bnode_array(void *addr, size_t *nnode_out)
66 : : {
67 : : // original b+tree always has only a single node per block
68 : : struct bnode **ret;
69 : 26370247 : *nnode_out = 1;
70 : 26370247 : ret = (struct bnode **)malloc(sizeof(struct bnode*) * (*nnode_out));
71 : 26370247 : ret[0] = _fetch_bnode(NULL, addr, 0);
72 : :
73 : 26372846 : return ret;
74 : : }
75 : :
76 : 8605000 : INLINE int _bnode_size(
77 : : struct btree *btree, struct bnode *node, void *new_minkey, void *key_arr, void *value_arr, size_t len)
78 : : {
79 : 8605000 : int nodesize = 0;
80 : :
81 [ + + ]: 8605000 : if (node->flag & BNODE_MASK_METADATA) {
82 : : metasize_t size;
83 : 92803 : memcpy(&size, (uint8_t *)node + sizeof(struct bnode), sizeof(metasize_t));
84 : 92803 : size = _endian_decode(size);
85 : : nodesize =
86 : : sizeof(struct bnode) +
87 : 92803 : btree->kv_ops->get_data_size(node, new_minkey, key_arr, value_arr, len) +
88 : 92803 : _metasize_align(size) + sizeof(metasize_t);
89 : : }else{
90 : : nodesize =
91 : : sizeof(struct bnode) +
92 : 8512197 : btree->kv_ops->get_data_size(node, new_minkey, key_arr, value_arr, len);
93 : : }
94 : :
95 : 8605009 : return nodesize;
96 : : }
97 : :
98 : : struct kv_ins_item {
99 : : void *key;
100 : : void *value;
101 : : struct list_elem le;
102 : : };
103 : :
104 : 8602510 : INLINE struct kv_ins_item * _kv_ins_item_create(
105 : : struct btree *btree, void *key, void *value)
106 : : {
107 : : struct kv_ins_item *item;
108 : 8602510 : item = (struct kv_ins_item*)malloc(sizeof(struct kv_ins_item));
109 : 8602510 : item->key = (void *)malloc(btree->ksize);
110 : 8602510 : item->value = (void *)malloc(btree->vsize);
111 : :
112 [ + - ]: 8602510 : if (btree->kv_ops->init_kv_var) {
113 : 8602519 : btree->kv_ops->init_kv_var(btree, item->key, item->value);
114 : : }
115 [ + + ]: 8602516 : if (key) {
116 : 8548577 : btree->kv_ops->set_key(btree, item->key, key);
117 : : }
118 [ + - ]: 8602516 : if (value) {
119 : 8602516 : btree->kv_ops->set_value(btree, item->value, value);
120 : : }
121 : 8602514 : return item;
122 : : }
123 : :
124 : 8602513 : INLINE void _kv_ins_item_free(struct kv_ins_item *item){
125 : 8602513 : free(item->key);
126 : 8602513 : free(item->value);
127 : 8602513 : free(item);
128 : 8602513 : }
129 : :
130 : 8604993 : INLINE int _bnode_size_check(
131 : : struct btree *btree, bid_t bid, struct bnode *node,
132 : : void *new_minkey, struct list *kv_ins_list, size_t *size_out)
133 : : {
134 : : size_t nitem;
135 : : size_t cursize;
136 : : size_t nodesize;
137 : : struct list_elem *e;
138 : : struct kv_ins_item *item;
139 : :
140 : 8604993 : nodesize = btree->blk_ops->blk_get_size(btree->blk_handle, bid);
141 : : #ifdef __CRC32
142 : 8604997 : nodesize -= BLK_MARKER_SIZE;
143 : : #endif
144 : :
145 : 8604997 : nitem = 0;
146 [ + + ]: 8604997 : if (kv_ins_list) {
147 : 8604995 : e = list_begin(kv_ins_list);
148 [ + + ]: 17209770 : while(e){
149 : 8604776 : nitem++;
150 : 8604776 : e = list_next(e);
151 : : }
152 : : }
153 : :
154 [ - + ]: 8604996 : if (nitem > 1) {
155 : : int i;
156 : : void *key_arr, *value_arr;
157 : :
158 : 0 : key_arr = (void*)malloc(btree->ksize * nitem);
159 : 0 : value_arr = (void*)malloc(btree->vsize * nitem);
160 : :
161 : 0 : i = 0;
162 : 0 : e = list_begin(kv_ins_list);
163 [ # # ]: 0 : while(e){
164 : 0 : item = _get_entry(e, struct kv_ins_item, le);
165 : 0 : memcpy((uint8_t *)key_arr + btree->ksize * i, item->key, btree->ksize);
166 : 0 : memcpy((uint8_t *)value_arr + btree->ksize * i, item->value, btree->ksize);
167 : 0 : i++;
168 : 0 : e = list_next(e);
169 : : }
170 : 0 : cursize = _bnode_size(btree, node, new_minkey, key_arr, value_arr, nitem);
171 : :
172 : 0 : free(key_arr);
173 : 0 : free(value_arr);
174 [ + + ]: 8604996 : }else if (nitem == 1) {
175 : 8604776 : e = list_begin(kv_ins_list);
176 : 8604775 : item = _get_entry(e, struct kv_ins_item, le);
177 : 8604775 : cursize = _bnode_size(btree, node, new_minkey, item->key, item->value, 1);
178 : : } else {
179 [ - + ]: 220 : assert(nitem == 0); /* nitem should never be negative due to size_t */
180 : 220 : cursize = _bnode_size(btree, node, new_minkey, NULL, NULL, 0);
181 : : }
182 : :
183 : 8605002 : *size_out = cursize;
184 : 8605002 : return ( cursize <= nodesize );
185 : : }
186 : :
187 : 56998 : INLINE struct bnode * _btree_init_node(
188 : : struct btree *btree, bid_t bid, void *addr, bnode_flag_t flag, uint16_t level, struct btree_meta *meta)
189 : : {
190 : : struct bnode *node;
191 : : void *node_addr;
192 : : metasize_t _size;
193 : :
194 : 56998 : node_addr = addr;
195 : :
196 : 56998 : node = (struct bnode *)node_addr;
197 : 56998 : node->kvsize = btree->ksize<<4 | btree->vsize;
198 : 56998 : node->nentry = 0;
199 : 56998 : node->level = level;
200 : 56998 : node->flag = flag;
201 : :
202 [ + + ][ + - ]: 56998 : if ((flag & BNODE_MASK_METADATA) && meta) {
203 : 2481 : _size = _endian_encode(meta->size);
204 : 2481 : memcpy((uint8_t *)node_addr + sizeof(struct bnode), &_size, sizeof(metasize_t));
205 : 2481 : memcpy((uint8_t *)node_addr + sizeof(struct bnode) + sizeof(metasize_t),
206 : 4962 : meta->data, meta->size);
207 : : node->data = (uint8_t *)node_addr + sizeof(struct bnode) + sizeof(metasize_t) +
208 : 2481 : _metasize_align(meta->size);
209 : : }else{
210 : 54517 : node->data = (uint8_t *)node_addr + sizeof(struct bnode);
211 : : }
212 : :
213 : 56998 : return node;
214 : : }
215 : :
216 : 54469 : INLINE size_t _btree_get_nsplitnode(struct btree *btree, bid_t bid, struct bnode *node, size_t size)
217 : : {
218 : : size_t headersize, dataspace;
219 : : size_t nodesize;
220 : 54469 : size_t nnode = 0;
221 : :
222 : 54469 : nodesize = btree->blk_ops->blk_get_size(btree->blk_handle, bid);
223 : : #ifdef __CRC32
224 : 54469 : nodesize -= BLK_MARKER_SIZE;
225 : : #endif
226 : :
227 [ + + ]: 54469 : if (node->flag & BNODE_MASK_METADATA) {
228 : : metasize_t size;
229 : 510 : memcpy(&size, (uint8_t *)node + sizeof(struct bnode), sizeof(metasize_t));
230 : 510 : size = _endian_decode(size);
231 : 510 : headersize = sizeof(struct bnode) + _metasize_align(size) + sizeof(metasize_t);
232 : : }else{
233 : 53959 : headersize = sizeof(struct bnode);
234 : : }
235 : :
236 : 54469 : dataspace = nodesize - headersize;
237 : : // round up
238 : 54469 : nnode = ((size - headersize) + (dataspace-1)) / dataspace;
239 : :
240 : 54469 : return nnode;
241 : : }
242 : :
243 : 24476795 : metasize_t btree_read_meta(struct btree *btree, void *buf)
244 : : {
245 : : void *addr;
246 : : void *ptr;
247 : : metasize_t size;
248 : : struct bnode *node;
249 : :
250 : 24476795 : addr = btree->blk_ops->blk_read(btree->blk_handle, btree->root_bid);
251 : 24471099 : node = _fetch_bnode(btree, addr, btree->height);
252 [ + + ]: 24477158 : if (node->flag & BNODE_MASK_METADATA) {
253 : 24477138 : ptr = ((uint8_t *)node) + sizeof(struct bnode);
254 : 24477138 : memcpy(&size, (uint8_t *)ptr, sizeof(metasize_t));
255 : 24477138 : size = _endian_decode(size);
256 : 24477138 : memcpy(buf, (uint8_t *)ptr + sizeof(metasize_t), size);
257 : : } else {
258 : 20 : size = 0;
259 : : }
260 : :
261 : 24477158 : return size;
262 : : }
263 : :
264 : 576 : void btree_update_meta(struct btree *btree, struct btree_meta *meta)
265 : : {
266 : : void *addr;
267 : : void *ptr;
268 : : metasize_t metasize, _metasize;
269 : : metasize_t old_metasize;
270 : : struct bnode *node;
271 : :
272 : : // read root node
273 : 576 : addr = btree->blk_ops->blk_read(btree->blk_handle, btree->root_bid);
274 : 576 : node = _fetch_bnode(btree, addr, btree->height);
275 : :
276 : 576 : ptr = ((uint8_t *)node) + sizeof(struct bnode);
277 : :
278 [ + + ]: 576 : if (node->flag & BNODE_MASK_METADATA) {
279 : 556 : memcpy(&old_metasize, ptr, sizeof(metasize_t));
280 : 556 : old_metasize = _endian_decode(old_metasize);
281 : : }
282 : :
283 [ + + ]: 576 : if (meta) {
284 : 46 : metasize = meta->size;
285 : :
286 : : // new meta size cannot be larger than old meta size
287 [ - + ]: 46 : assert(metasize <= old_metasize);
288 : : (void)metasize;
289 : :
290 : : // overwrite
291 [ + - ]: 46 : if (meta->size > 0) {
292 : 46 : _metasize = _endian_encode(metasize);
293 : 46 : memcpy(ptr, &_metasize, sizeof(metasize_t));
294 : 46 : memcpy((uint8_t *)ptr + sizeof(metasize_t), meta->data, metasize);
295 : 46 : node->flag |= BNODE_MASK_METADATA;
296 : : }else{
297 : : // clear the flag
298 : 0 : node->flag &= ~BNODE_MASK_METADATA;
299 : : }
300 : : // move kv-pairs (only if meta size is changed)
301 [ + + ]: 46 : if (_metasize_align(metasize) < _metasize_align(old_metasize)){
302 : : memmove(
303 : 1 : (uint8_t *)ptr + sizeof(metasize_t) + _metasize_align(metasize),
304 : : node->data,
305 : 1 : btree->kv_ops->get_data_size(node, NULL, NULL, NULL, 0));
306 : : node->data = (uint8_t *)node->data - (_metasize_align(old_metasize) -
307 : 1 : _metasize_align(metasize));
308 : : }
309 : :
310 : : }else {
311 [ + + ]: 530 : if (node->flag & BNODE_MASK_METADATA) {
312 : : // existing metadata is removed
313 : : memmove(ptr, node->data, btree->kv_ops->get_data_size(node,
314 : 510 : NULL, NULL, NULL, 0));
315 : : node->data = (uint8_t *)node->data - (_metasize_align(old_metasize) +
316 : 510 : sizeof(metasize_t));
317 : : // clear the flag
318 : 510 : node->flag &= ~BNODE_MASK_METADATA;
319 : : }
320 : : }
321 : :
322 [ + + ]: 576 : if (!btree->blk_ops->blk_is_writable(btree->blk_handle, btree->root_bid)) {
323 : : // already flushed block -> cannot overwrite, we have to move to new block
324 : : btree->blk_ops->blk_move(btree->blk_handle, btree->root_bid,
325 : 5 : &btree->root_bid);
326 : : }else{
327 : 571 : btree->blk_ops->blk_set_dirty(btree->blk_handle, btree->root_bid);
328 : : }
329 : 576 : }
330 : :
331 : 24490989 : btree_result btree_init_from_bid(struct btree *btree, void *blk_handle,
332 : : struct btree_blk_ops *blk_ops,
333 : : struct btree_kv_ops *kv_ops,
334 : : uint32_t nodesize, bid_t root_bid)
335 : : {
336 : : void *addr;
337 : : struct bnode *root;
338 : :
339 : 24490989 : btree->blk_ops = blk_ops;
340 : 24490989 : btree->blk_handle = blk_handle;
341 : 24490989 : btree->kv_ops = kv_ops;
342 : 24490989 : btree->blksize = nodesize;
343 : 24490989 : btree->root_bid = root_bid;
344 : :
345 : 24490989 : addr = btree->blk_ops->blk_read(btree->blk_handle, btree->root_bid);
346 : 24478102 : root = _fetch_bnode(btree, addr, 0);
347 : :
348 : 24481625 : btree->root_flag = root->flag;
349 : 24481625 : btree->height = root->level;
350 : 24481625 : _get_kvsize(root->kvsize, btree->ksize, btree->vsize);
351 : :
352 : 24481625 : return BTREE_RESULT_SUCCESS;
353 : : }
354 : :
355 : 2000 : btree_result btree_init(
356 : : struct btree *btree, void *blk_handle,
357 : : struct btree_blk_ops *blk_ops, struct btree_kv_ops *kv_ops,
358 : : uint32_t nodesize, uint8_t ksize, uint8_t vsize,
359 : : bnode_flag_t flag, struct btree_meta *meta)
360 : : {
361 : : void *addr;
362 : 2000 : size_t min_nodesize = 0;
363 : :
364 : 2000 : btree->root_flag = BNODE_MASK_ROOT | flag;
365 : 2000 : btree->blk_ops = blk_ops;
366 : 2000 : btree->blk_handle = blk_handle;
367 : 2000 : btree->kv_ops = kv_ops;
368 : 2000 : btree->height = 1;
369 : 2000 : btree->blksize = nodesize;
370 : 2000 : btree->ksize = ksize;
371 : 2000 : btree->vsize = vsize;
372 [ + + ]: 2000 : if (meta) {
373 : 1972 : btree->root_flag |= BNODE_MASK_METADATA;
374 : : min_nodesize = sizeof(struct bnode) + _metasize_align(meta->size) +
375 : 1972 : sizeof(metasize_t) + BLK_MARKER_SIZE;
376 : : } else {
377 : 28 : min_nodesize = sizeof(struct bnode) + BLK_MARKER_SIZE;
378 : : }
379 : :
380 [ + + ]: 2000 : if (min_nodesize > btree->blksize) {
381 : : // too large metadata .. init fail
382 : 1 : return BTREE_RESULT_FAIL;
383 : : }
384 : :
385 : : // create the first root node
386 [ + - ][ + - ]: 1999 : if (btree->blk_ops->blk_alloc_sub && btree->blk_ops->blk_enlarge_node) {
387 : 1999 : addr = btree->blk_ops->blk_alloc_sub(btree->blk_handle, &btree->root_bid);
388 [ + + ]: 1999 : if (meta) {
389 : : // check if the initial node size including metadata is
390 : : // larger than the subblock size
391 : : size_t subblock_size;
392 : : subblock_size = btree->blk_ops->blk_get_size(btree->blk_handle,
393 : 1971 : btree->root_bid);
394 [ + + ]: 1971 : if (subblock_size < min_nodesize) {
395 : : addr = btree->blk_ops->blk_enlarge_node(btree->blk_handle,
396 : : btree->root_bid,
397 : : min_nodesize,
398 : 305 : &btree->root_bid);
399 : : }
400 : 1999 : }
401 : : } else {
402 : 0 : addr = btree->blk_ops->blk_alloc (btree->blk_handle, &btree->root_bid);
403 : : }
404 : : _btree_init_node(btree, btree->root_bid, addr,
405 : 1999 : btree->root_flag, BNODE_MASK_ROOT, meta);
406 : :
407 : 2000 : return BTREE_RESULT_SUCCESS;
408 : : }
409 : :
410 : : /*
411 : : return index# of largest key equal or smaller than KEY
412 : : example)
413 : : node: [2 4 6 8]
414 : : key: 5
415 : : largest key equal or smaller than KEY: 4
416 : : return: 1 (index# of the key '4')
417 : : */
418 : 75926138 : idx_t _btree_find_entry(struct btree *btree, struct bnode *node, void *key)
419 : : {
420 : : idx_t start, end, middle, temp;
421 : 75926138 : uint8_t *k = alca(uint8_t, btree->ksize);
422 : : int cmp;
423 : : #ifdef __BIT_CMP
424 : 75926138 : idx_t *_map1[3] = {&end, &start, &start};
425 : 75926138 : idx_t *_map2[3] = {&temp, &end, &temp};
426 : : #endif
427 : :
428 [ + - ]: 75926138 : if (btree->kv_ops->init_kv_var) btree->kv_ops->init_kv_var(btree, k, NULL);
429 : :
430 : 75928544 : start = middle = 0;
431 : 75928544 : end = node->nentry;
432 : :
433 [ + + ]: 75928544 : if (end > 0) {
434 : : // compare with smallest key
435 : 75926059 : btree->kv_ops->get_kv(node, 0, k, NULL);
436 : : // smaller than smallest key
437 [ + + ]: 75922409 : if (btree->kv_ops->cmp(key, k, btree->aux) < 0) {
438 [ + + ]: 7043 : if (btree->kv_ops->free_kv_var) btree->kv_ops->free_kv_var(btree, k, NULL);
439 : 7043 : return BTREE_IDX_NOT_FOUND;
440 : : }
441 : :
442 : : // compare with largest key
443 : 75888864 : btree->kv_ops->get_kv(node, end-1, k, NULL);
444 : : // larger than largest key
445 [ + + ]: 75901578 : if (btree->kv_ops->cmp(key, k, btree->aux) >= 0) {
446 [ + + ]: 42576253 : if (btree->kv_ops->free_kv_var) btree->kv_ops->free_kv_var(btree, k, NULL);
447 : 42577358 : return end-1;
448 : : }
449 : :
450 : : // binary search
451 [ + + ]: 248147986 : while(start+1 < end) {
452 : 214790048 : middle = (start + end) >> 1;
453 : :
454 : : // get key at middle
455 : 214790048 : btree->kv_ops->get_kv(node, middle, k, NULL);
456 : 214832374 : cmp = btree->kv_ops->cmp(key, k, btree->aux);
457 : :
458 : : #ifdef __BIT_CMP
459 : 214798720 : cmp = _MAP(cmp) + 1;
460 : 214798720 : *_map1[cmp] = middle;
461 : 214798720 : *_map2[cmp] = 0;
462 : : #else
463 : : if (cmp < 0) end = middle;
464 : : else if (cmp > 0) start = middle;
465 : : else {
466 : : if (btree->kv_ops->free_kv_var) btree->kv_ops->free_kv_var(btree, k, NULL);
467 : : return middle;
468 : : }
469 : : #endif
470 : : }
471 [ + + ]: 33357938 : if (btree->kv_ops->free_kv_var) btree->kv_ops->free_kv_var(btree, k, NULL);
472 : 33370678 : return start;
473 : : }
474 : :
475 [ + + ]: 2485 : if (btree->kv_ops->free_kv_var) btree->kv_ops->free_kv_var(btree, k, NULL);
476 : 75957564 : return BTREE_IDX_NOT_FOUND;
477 : : }
478 : :
479 : 8603566 : idx_t _btree_add_entry(struct btree *btree, struct bnode *node, void *key, void *value)
480 : : {
481 : : idx_t idx, idx_insert;
482 : 8603566 : uint8_t *k = alca(uint8_t, btree->ksize);
483 : :
484 [ + - ]: 8603566 : if (btree->kv_ops->init_kv_var) btree->kv_ops->init_kv_var(btree, k, NULL);
485 : :
486 [ + + ]: 8603567 : if (node->nentry > 0) {
487 : 8601043 : idx = _btree_find_entry(btree, node, key);
488 : :
489 [ + + ]: 8601059 : if (idx == BTREE_IDX_NOT_FOUND) idx_insert = 0;
490 : : else {
491 : 8598959 : btree->kv_ops->get_kv(node, idx, k, NULL);
492 [ + + ]: 8598958 : if (!btree->kv_ops->cmp(key, k, btree->aux)) {
493 : : // if same key already exists -> update its value
494 : 505632 : btree->kv_ops->set_kv(node, idx, key, value);
495 [ + + ]: 505632 : if (btree->kv_ops->free_kv_var) btree->kv_ops->free_kv_var(btree, k, NULL);
496 : 505632 : return idx;
497 : : }else{
498 : 8093322 : idx_insert = idx+1;
499 : : }
500 : : }
501 : :
502 [ + + ]: 8095422 : if (idx_insert < node->nentry) {
503 : :
504 : : /*
505 : : shift [idx+1, nentry) key-value pairs to right
506 : : example)
507 : : idx = 1 (i.e. idx_insert = 2)
508 : : [2 4 6 8] -> [2 4 _ 6 8]
509 : : return 2
510 : : */
511 : 3860741 : btree->kv_ops->ins_kv(node, idx_insert, key, value);
512 : : }else{
513 : 4234681 : btree->kv_ops->set_kv(node, idx_insert, key, value);
514 : : }
515 : :
516 : : }else{
517 : 2524 : idx_insert = 0;
518 : : // add at idx_insert
519 : 2524 : btree->kv_ops->set_kv(node, idx_insert, key, value);
520 : : }
521 : :
522 : : // add at idx_insert
523 : 8097914 : node->nentry++;
524 : :
525 [ + + ]: 8097914 : if (btree->kv_ops->free_kv_var) btree->kv_ops->free_kv_var(btree, k, NULL);
526 : 8603546 : return idx_insert;
527 : : }
528 : :
529 : 16 : idx_t _btree_remove_entry(struct btree *btree, struct bnode *node, void *key)
530 : : {
531 : : idx_t idx;
532 : :
533 [ + - ]: 16 : if (node->nentry > 0) {
534 : 16 : idx = _btree_find_entry(btree, node, key);
535 : :
536 [ - + ]: 16 : if (idx == BTREE_IDX_NOT_FOUND) return idx;
537 : :
538 : : /*
539 : : shift [idx+1, nentry) key-value pairs to left
540 : : example)
541 : : idx = 2
542 : : [2 4 6 8 10] -> [2 4 8 10]
543 : : return 2
544 : : */
545 : 16 : btree->kv_ops->ins_kv(node, idx, NULL, NULL);
546 : :
547 : 16 : node->nentry--;
548 : :
549 : 16 : return idx;
550 : :
551 : : }else{
552 : 16 : return BTREE_IDX_NOT_FOUND;
553 : : }
554 : : }
555 : :
556 : 88 : void _btree_print_node(struct btree *btree, int depth, bid_t bid, btree_print_func func)
557 : : {
558 : : int i;
559 : 88 : uint8_t *k = alca(uint8_t, btree->ksize);
560 : 88 : uint8_t *v = alca(uint8_t, btree->vsize);
561 : : void *addr;
562 : : bid_t _bid;
563 : : struct bnode *node;
564 : :
565 [ + - ]: 88 : if (btree->kv_ops->init_kv_var) btree->kv_ops->init_kv_var(btree, k, v);
566 : :
567 : 88 : addr = btree->blk_ops->blk_read(btree->blk_handle, bid);
568 : 88 : node = _fetch_bnode(btree, addr, depth);
569 : :
570 : 88 : fprintf(stderr, "[d:%d n:%d f:%x b:%" _F64 " ", node->level, node->nentry, node->flag, bid);
571 : :
572 [ + + ]: 274 : for (i=0;i<node->nentry;++i){
573 : 186 : btree->kv_ops->get_kv(node, i, k, v);
574 : 186 : _bid = btree->kv_ops->value2bid(v);
575 : 186 : _bid = _endian_decode(_bid);
576 : 186 : func(btree, k, (void*)&_bid);
577 : : }
578 : 88 : fprintf(stderr, "]\n");
579 [ + + ]: 88 : if (depth > 1) {
580 [ + + ]: 112 : for (i=0;i<node->nentry;++i){
581 : 78 : btree->kv_ops->get_kv(node, i, k, v);
582 : 78 : _bid = btree->kv_ops->value2bid(v);
583 : 78 : _bid = _endian_decode(_bid);
584 : 78 : _btree_print_node(btree, depth-1, _bid, func);
585 : : }
586 : : }
587 : :
588 [ - + ]: 88 : if (btree->kv_ops->free_kv_var) btree->kv_ops->free_kv_var(btree, k, v);
589 : 88 : }
590 : :
591 : 10 : void btree_print_node(struct btree *btree, btree_print_func func)
592 : : {
593 : 10 : fprintf(stderr, "tree height: %d\n", btree->height);
594 : 10 : _btree_print_node(btree, btree->height, btree->root_bid, func);
595 : 10 : }
596 : :
597 : 5 : btree_result btree_get_key_range(
598 : : struct btree *btree, idx_t num, idx_t den, void *key_begin, void *key_end)
599 : : {
600 : : void *addr;
601 : 5 : uint8_t *k = alca(uint8_t, btree->ksize);
602 : 5 : uint8_t *v = alca(uint8_t, btree->vsize);
603 : : idx_t idx_begin, idx_end, idx;
604 : : bid_t bid;
605 : : struct bnode *root, *node;
606 : : uint64_t _num, _den, _nentry, resolution, mask, _idx_begin, _idx_end;
607 : :
608 [ - + ]: 5 : assert(num < den);
609 : 5 : resolution = 1<<4; mask = resolution-1;
610 : :
611 [ + - ]: 5 : if (btree->kv_ops->init_kv_var) btree->kv_ops->init_kv_var(btree, k, v);
612 : 5 : _num = (uint64_t)num * resolution;
613 : 5 : _den = (uint64_t)den * resolution;
614 : :
615 : : // get root node
616 : 5 : addr = btree->blk_ops->blk_read(btree->blk_handle, btree->root_bid);
617 : 5 : root = _fetch_bnode(btree, addr, btree->height);
618 : 5 : _nentry = (uint64_t)root->nentry * resolution;
619 : :
620 [ + - ]: 5 : if (btree->height == 1) {
621 : 5 : btree->kv_ops->get_kv(root, ((num+0) * root->nentry / den)-0, key_begin, NULL);
622 : 5 : btree->kv_ops->get_kv(root, ((num+1) * root->nentry / den)-1, key_end, NULL);
623 : : }else{
624 : 0 : _idx_begin = (_num * _nentry / _den);
625 : 0 : _idx_end = ((_num+resolution) * _nentry / _den)-1;
626 : :
627 : 0 : idx_begin = _idx_begin / resolution;
628 : 0 : idx_end = (_idx_end / resolution);
629 [ # # ]: 0 : if (idx_end >= root->nentry) idx_end = root->nentry-1;
630 : :
631 : : // get first child node (for KEY_BEGIN)
632 : 0 : btree->kv_ops->get_kv(root, idx_begin, k, v);
633 : 0 : bid = btree->kv_ops->value2bid(v);
634 : 0 : bid = _endian_decode(bid);
635 : 0 : addr = btree->blk_ops->blk_read(btree->blk_handle, bid);
636 : 0 : node = _fetch_bnode(btree, addr, btree->height-1);
637 : :
638 : 0 : idx = ((_idx_begin & mask) * (node->nentry-1) / (resolution-1));
639 : 0 : btree->kv_ops->get_kv(node, idx, key_begin, NULL);
640 : :
641 : : // get second child node (for KEY_END)
642 [ # # ]: 0 : if (idx_end != idx_begin) {
643 : 0 : btree->kv_ops->get_kv(root, idx_end, k, v);
644 : 0 : bid = btree->kv_ops->value2bid(v);
645 : 0 : bid = _endian_decode(bid);
646 : 0 : addr = btree->blk_ops->blk_read(btree->blk_handle, bid);
647 : 0 : node = _fetch_bnode(btree, addr, btree->height-1);
648 : : }
649 : :
650 : 0 : idx = ((_idx_end & mask) * (node->nentry-1) / (resolution-1));
651 : 0 : btree->kv_ops->get_kv(node, idx, key_end, NULL);
652 : : }
653 : :
654 [ - + ]: 5 : if (btree->kv_ops->free_kv_var) btree->kv_ops->free_kv_var(btree, k, v);
655 : 5 : return BTREE_RESULT_SUCCESS;
656 : : }
657 : :
658 : 24674718 : btree_result btree_find(struct btree *btree, void *key, void *value_buf)
659 : : {
660 : : void *addr;
661 : 24674718 : uint8_t *k = alca(uint8_t, btree->ksize);
662 : 24674718 : uint8_t *v = alca(uint8_t, btree->vsize);
663 : 24674718 : idx_t *idx = alca(idx_t, btree->height);
664 : 24674718 : bid_t *bid = alca(bid_t, btree->height);
665 : 24674718 : struct bnode **node = alca(struct bnode *, btree->height);
666 : : int i;
667 : :
668 [ + - ]: 24674718 : if (btree->kv_ops->init_kv_var) btree->kv_ops->init_kv_var(btree, k, v);
669 : :
670 : : // set root
671 : 24679879 : bid[btree->height-1] = btree->root_bid;
672 : :
673 [ + + ]: 59743769 : for (i=btree->height-1; i>=0; --i) {
674 : : // read block using bid
675 : 44938591 : addr = btree->blk_ops->blk_read(btree->blk_handle, bid[i]);
676 : : // fetch node structure from block
677 : 44937951 : node[i] = _fetch_bnode(btree, addr, i+1);
678 : :
679 : : // lookup key in current node
680 : 44930881 : idx[i] = _btree_find_entry(btree, node[i], key);
681 : :
682 [ + + ]: 44935201 : if (idx[i] == BTREE_IDX_NOT_FOUND) {
683 : : // not found .. return NULL
684 [ - + ]: 949 : if (btree->blk_ops->blk_operation_end)
685 : 0 : btree->blk_ops->blk_operation_end(btree->blk_handle);
686 [ + + ]: 949 : if (btree->kv_ops->free_kv_var) btree->kv_ops->free_kv_var(btree, k, v);
687 : 949 : return BTREE_RESULT_FAIL;
688 : : }
689 : :
690 : 44934252 : btree->kv_ops->get_kv(node[i], idx[i], k, v);
691 : :
692 [ + + ]: 44950423 : if (i>0) {
693 : : // index (non-leaf) node
694 : : // get bid of child node from value
695 : 20282080 : bid[i-1] = btree->kv_ops->value2bid(v);
696 : 20284709 : bid[i-1] = _endian_decode(bid[i-1]);
697 : : }else{
698 : : // leaf node
699 : : // return (address of) value if KEY == k
700 [ + + ]: 24668343 : if (!btree->kv_ops->cmp(key, k, btree->aux)) {
701 : 14805105 : btree->kv_ops->set_value(btree, value_buf, v);
702 : : }else{
703 [ - + ]: 9868001 : if (btree->blk_ops->blk_operation_end)
704 : 0 : btree->blk_ops->blk_operation_end(btree->blk_handle);
705 [ + + ]: 9868002 : if (btree->kv_ops->free_kv_var) {
706 : 7719 : btree->kv_ops->free_kv_var(btree, k, v);
707 : : }
708 : 9868002 : return BTREE_RESULT_FAIL;
709 : : }
710 : : }
711 : : }
712 [ - + ]: 14805178 : if (btree->blk_ops->blk_operation_end) {
713 : 0 : btree->blk_ops->blk_operation_end(btree->blk_handle);
714 : : }
715 [ + + ]: 14805189 : if (btree->kv_ops->free_kv_var) btree->kv_ops->free_kv_var(btree, k, v);
716 : 24674140 : return BTREE_RESULT_SUCCESS;
717 : : }
718 : :
719 : 54469 : int _btree_split_node(
720 : : struct btree *btree, void *key, struct bnode **node, bid_t *bid, idx_t *idx, int i,
721 : : struct list *kv_ins_list, size_t nsplitnode, void *k, void *v,
722 : : int8_t *modified, int8_t *minkey_replace, int8_t *ins)
723 : : {
724 : : void *addr;
725 : 54469 : size_t nnode = nsplitnode;
726 : 54469 : int j, *nentry = alca(int, nnode);
727 : : bid_t _bid;
728 : 54469 : bid_t *new_bid = alca(bid_t, nnode);
729 : 54469 : idx_t *split_idx = alca(idx_t, nnode+1);
730 : 54469 : idx_t *idx_ins = alca(idx_t, btree->height);
731 : : struct list_elem *e;
732 : 54469 : struct bnode **new_node = alca(struct bnode *, nnode);
733 : : struct kv_ins_item *kv_item;
734 : :
735 : : // allocate new block(s)
736 : 54469 : new_node[0] = node[i];
737 [ + + ]: 108938 : for (j=1;j<nnode;++j){
738 : 54469 : addr = btree->blk_ops->blk_alloc(btree->blk_handle, &new_bid[j]);
739 : 108938 : new_node[j] = _btree_init_node(btree, new_bid[j], addr, 0x0,
740 : 54469 : node[i]->level, NULL);
741 : : }
742 : :
743 : : // calculate # entry
744 [ + + ]: 217876 : for (j=0;j<nnode+1;++j){
745 : 163407 : btree->kv_ops->get_nth_idx(node[i], j, nnode, &split_idx[j]);
746 [ + + ]: 163407 : if (j>0) {
747 : 108938 : nentry[j-1] = split_idx[j] - split_idx[j-1];
748 : : }
749 : : }
750 : :
751 : : // copy kv-pairs to new node(s)
752 [ + + ]: 108938 : for (j=1;j<nnode;++j){
753 : 163407 : btree->kv_ops->copy_kv(new_node[j], node[i], 0, split_idx[j],
754 : 54469 : nentry[j]);
755 : : }
756 : 54469 : j = 0;
757 : 54469 : btree->kv_ops->copy_kv(new_node[j], node[i], 0, split_idx[j], nentry[j]);
758 : :
759 : : // header
760 [ + + ]: 163407 : for (j=0;j<nnode;++j){
761 : 108938 : new_node[j]->nentry = nentry[j];
762 : : }
763 : 54469 : modified[i] = 1;
764 : :
765 [ + - ]: 54469 : if (ins[i]) {
766 : : // insert kv-pair(s) to appropriate node
767 : 54469 : e = list_begin(&kv_ins_list[i]);
768 [ + + ]: 108938 : while(e) {
769 : 54469 : kv_item = _get_entry(e, struct kv_ins_item, le);
770 : :
771 : 54469 : idx_ins[i] = BTREE_IDX_NOT_FOUND;
772 [ + + ]: 99062 : for (j=1;j<nnode;++j){
773 : 54469 : btree->kv_ops->get_kv(new_node[j], 0, k, v);
774 [ + + ]: 54469 : if (btree->kv_ops->cmp(kv_item->key, k, btree->aux) < 0) {
775 : 9876 : idx_ins[i] =
776 : 9876 : _btree_add_entry(btree, new_node[j-1], kv_item->key,
777 : 9876 : kv_item->value);
778 : 9876 : break;
779 : : }
780 : : }
781 [ + + ]: 54469 : if (idx_ins[i] == BTREE_IDX_NOT_FOUND) {
782 : : // insert into the last split node
783 : 44593 : idx_ins[i] =
784 : 44593 : _btree_add_entry(btree, new_node[nnode-1], kv_item->key,
785 : 44593 : kv_item->value);
786 : : }
787 : 54469 : e = list_next(e);
788 : : }
789 : : }
790 [ - + ]: 54469 : if (minkey_replace[i]){
791 : : // replace the minimum key in the (first split) node to KEY
792 : 0 : btree->kv_ops->get_kv(new_node[0], idx[i], k, v);
793 : 0 : btree->kv_ops->set_kv(new_node[0], idx[i], key, v);
794 : : }
795 : :
796 [ + + ]: 54469 : if (i+1 < btree->height) {
797 : : // non-root node
798 : : // reserve kv-pair (i.e. splitters) to be inserted into parent node
799 [ + + ]: 107878 : for (j=1; j<nnode; ++j){
800 : 53939 : _bid = _endian_encode(new_bid[j]);
801 : 53939 : kv_item = _kv_ins_item_create(btree, NULL, (void *)&_bid);
802 : 107878 : btree->kv_ops->get_nth_splitter(new_node[j-1], new_node[j],
803 : 53939 : kv_item->key);
804 : 53939 : list_push_back(&kv_ins_list[i+1], &kv_item->le);
805 : : }
806 : 53939 : ins[i+1] = 1;
807 : :
808 : : }else{
809 : : //2 root node -> height grow up
810 : : // allocate new block for new root node
811 : : bid_t new_root_bid;
812 : : struct bnode *new_root;
813 : 530 : uint8_t *buf = alca(uint8_t, btree->blksize);
814 : : struct btree_meta meta;
815 : :
816 : 530 : meta.size = btree_read_meta(btree, buf);
817 : 530 : meta.data = buf;
818 : : // remove metadata section of existing node
819 : : // (this node is not root anymore)
820 : 530 : btree_update_meta(btree, NULL);
821 : :
822 : 530 : btree->height++;
823 : :
824 : 530 : addr = btree->blk_ops->blk_alloc(btree->blk_handle, &new_root_bid);
825 [ + + ]: 530 : if (meta.size > 0)
826 : : new_root =
827 : : _btree_init_node(
828 : : btree, new_root_bid, addr, btree->root_flag,
829 : 510 : node[i]->level + 1, &meta);
830 : : else
831 : : new_root =
832 : : _btree_init_node(
833 : : btree, new_root_bid, addr, btree->root_flag,
834 : 20 : node[i]->level + 1, NULL);
835 : :
836 : : // clear old root node flag
837 : 530 : node[i]->flag &= ~BNODE_MASK_ROOT;
838 : 530 : node[i]->flag &= ~BNODE_MASK_SEQTREE;
839 : : // change root bid
840 : 530 : btree->root_bid = new_root_bid;
841 : :
842 : : // move the former node if not dirty
843 [ + + ]: 530 : if (!btree->blk_ops->blk_is_writable(btree->blk_handle, bid[i])) {
844 : 5 : addr = btree->blk_ops->blk_move(btree->blk_handle, bid[i], &bid[i]);
845 : 5 : node[i] = _fetch_bnode(btree, addr, i+1);
846 : : }else{
847 : 525 : btree->blk_ops->blk_set_dirty(btree->blk_handle, bid[i]);
848 : : }
849 : :
850 : : // insert kv-pairs pointing to their child nodes
851 : : // original (i.e. the first node)
852 : 530 : btree->kv_ops->get_kv(node[i], 0, k, v);
853 : 530 : _bid = _endian_encode(bid[i]);
854 : 530 : _btree_add_entry(btree, new_root, k, btree->kv_ops->bid2value(&_bid));
855 : :
856 : : // the others
857 [ + + ]: 1060 : for (j=1;j<nnode;++j){
858 : : //btree->kv_ops->get_kv(new_node[j], 0, k, v);
859 : 530 : btree->kv_ops->get_nth_splitter(new_node[j-1], new_node[j], k);
860 : 530 : _bid = _endian_encode(new_bid[j]);
861 : : _btree_add_entry(btree, new_root, k,
862 : 530 : btree->kv_ops->bid2value(&_bid));
863 : : }
864 : :
865 : 54469 : return 1;
866 : : } // height growup
867 : :
868 : 53939 : return 0;
869 : : }
870 : :
871 : 36194 : int _btree_move_modified_node(
872 : : struct btree *btree, void *key, struct bnode **node, bid_t *bid,
873 : : idx_t *idx, int i,
874 : : struct list *kv_ins_list, void *k, void *v,
875 : : int8_t *modified, int8_t *minkey_replace, int8_t *ins, int8_t *moved)
876 : : {
877 : : void *addr;
878 : :
879 : : // get new bid[i]
880 : 36194 : addr = btree->blk_ops->blk_move(btree->blk_handle, bid[i], &bid[i]);
881 : : (void)addr;
882 : : //node[i] = _fetch_bnode(btree, addr, i+1);
883 : 36194 : moved[i] = 1;
884 : :
885 [ + + ]: 36194 : if (i+1 == btree->height)
886 : : // if moved node is root node
887 : 2787 : btree->root_bid = bid[i];
888 : :
889 : 36194 : return 0;
890 : : }
891 : :
892 : 8548582 : btree_result btree_insert(struct btree *btree, void *key, void *value)
893 : : {
894 : : void *addr;
895 : 8548582 : size_t nsplitnode = 1;
896 : 8548582 : uint8_t *k = alca(uint8_t, btree->ksize);
897 : 8548582 : uint8_t *v = alca(uint8_t, btree->vsize);
898 : : // index# and block ID for each level
899 : 8548582 : idx_t *idx = alca(idx_t, btree->height);
900 : 8548582 : bid_t *bid = alca(bid_t, btree->height);
901 : : bid_t _bid;
902 : : // flags
903 : 8548582 : int8_t *modified = alca(int8_t, btree->height);
904 : 8548582 : int8_t *moved = alca(int8_t, btree->height);
905 : 8548582 : int8_t *ins = alca(int8_t, btree->height);
906 : 8548582 : int8_t *minkey_replace = alca(int8_t, btree->height);
907 : : int8_t height_growup;
908 : :
909 : : // key, value to be inserted
910 : 8548582 : struct list *kv_ins_list = alca(struct list, btree->height);
911 : : struct kv_ins_item *kv_item;
912 : : struct list_elem *e;
913 : :
914 : : // index# where kv is inserted
915 : 8548582 : idx_t *idx_ins = alca(idx_t, btree->height);
916 : 8548582 : struct bnode **node = alca(struct bnode *, btree->height);
917 : 8548582 : int i, j, _is_update = 0;
918 : :
919 : : // initialize flags
920 [ + + ]: 30938361 : for (i=0;i<btree->height;++i) {
921 : 22389779 : moved[i] = modified[i] = ins[i] = minkey_replace[i] = 0;
922 : : }
923 : 8548582 : height_growup = 0;
924 : :
925 : : // initialize temporary variables
926 [ + - ]: 8548582 : if (btree->kv_ops->init_kv_var) {
927 : 8548582 : btree->kv_ops->init_kv_var(btree, k, v);
928 [ + + ]: 30938366 : for (i=0;i<btree->height;++i){
929 : 22389784 : list_init(&kv_ins_list[i]);
930 : : }
931 : : }
932 : :
933 : : // copy key-value pair to be inserted into leaf node
934 : 8548582 : kv_item = _kv_ins_item_create(btree, key, value);
935 : 8548575 : list_push_back(&kv_ins_list[0], &kv_item->le);
936 : :
937 : 8548498 : ins[0] = 1;
938 : :
939 : : // set root node
940 : 8548498 : bid[btree->height-1] = btree->root_bid;
941 : :
942 : : // find path from root to leaf
943 [ + + ]: 30938157 : for (i=btree->height-1; i>=0; --i){
944 : : // read block using bid
945 : 22389600 : addr = btree->blk_ops->blk_read(btree->blk_handle, bid[i]);
946 : : // fetch node structure from block
947 : 22389601 : node[i] = _fetch_bnode(btree, addr, i+1);
948 : :
949 : : // lookup key in current node
950 : 22389616 : idx[i] = _btree_find_entry(btree, node[i], key);
951 : :
952 [ + + ]: 22389655 : if (i > 0) {
953 : : // index (non-leaf) node
954 [ + + ]: 13841174 : if (idx[i] == BTREE_IDX_NOT_FOUND)
955 : : // KEY is smaller than the smallest key in this node ..
956 : : // just follow the smallest key
957 : 223 : idx[i] = 0;
958 : :
959 : : // get bid of child node from value
960 : 13841174 : btree->kv_ops->get_kv(node[i], idx[i], k, v);
961 : 13841178 : bid[i-1] = btree->kv_ops->value2bid(v);
962 : 13841178 : bid[i-1] = _endian_decode(bid[i-1]);
963 : : }else{
964 : : // leaf node .. do nothing
965 : : }
966 : : }
967 : :
968 : : // cascaded insert from leaf to root
969 [ + + ]: 30937758 : for (i=0;i<btree->height;++i){
970 : :
971 [ + + ]: 22389678 : if (idx[i] != BTREE_IDX_NOT_FOUND)
972 : 22385610 : btree->kv_ops->get_kv(node[i], idx[i], k, NULL);
973 : :
974 [ + + ]: 22389704 : if (i > 0) {
975 : : // in case of index node
976 : : // when KEY is smaller than smallest key in index node
977 [ + + ][ + + ]: 13841208 : if (idx[i] == 0 && btree->kv_ops->cmp(key, k, btree->aux) < 0) {
[ + + ]
978 : : // change node's smallest key
979 : 223 : minkey_replace[i] = 1;
980 : : }
981 : :
982 : : // when child node is moved to new block
983 [ + + ]: 13841208 : if (moved[i-1]) {
984 : : // replace the bid (value)
985 : 33407 : _bid = _endian_encode(bid[i-1]);
986 : 66814 : btree->kv_ops->set_kv(node[i], idx[i], k,
987 : 33407 : btree->kv_ops->bid2value(&_bid));
988 : 33407 : modified[i] = 1;
989 : : }
990 : : }
991 : :
992 [ + + ][ + + ]: 22389704 : if (ins[i] || minkey_replace[i]) {
993 : : // there is a key-value pair to be inserted into this (level of)
994 : : // node check whether btree node space is enough to add new
995 : : // key-value pair or not, OR action is not insertion but update
996 : : // (key_ins exists in current node)
997 : 8602714 : _is_update = 0;
998 : : size_t nodesize;
999 [ + + ]: 8602714 : void *new_minkey = (minkey_replace[i])?(key):(NULL);
1000 : :
1001 [ + + ]: 8602714 : if (i==0) {
1002 : 8548558 : e = list_begin(&kv_ins_list[i]);
1003 : 8548559 : kv_item = _get_entry(e, struct kv_ins_item, le);
1004 : : _is_update =
1005 : 8548559 : (idx[i] != BTREE_IDX_NOT_FOUND &&
1006 [ + + ][ + + ]: 8548559 : !btree->kv_ops->cmp(kv_item->key, k, btree->aux));
1007 : : }
1008 : :
1009 : : check_node:;
1010 : : int _size_check =
1011 : 17209982 : _bnode_size_check(btree, bid[i], node[i], new_minkey,
1012 : 8604991 : &kv_ins_list[i], &nodesize);
1013 : :
1014 [ + + ][ + + ]: 8605001 : if (_size_check || _is_update ) {
1015 : : //2 enough space
1016 [ + + ]: 8548261 : if (ins[i]) {
1017 : : // insert key/value pair(s)
1018 : : // insert all kv pairs on list
1019 : 8548041 : e = list_begin(&kv_ins_list[i]);
1020 [ + + ]: 17096054 : while(e) {
1021 : 8548038 : kv_item = _get_entry(e, struct kv_ins_item, le);
1022 : 17096076 : idx_ins[i] = _btree_add_entry(btree, node[i],
1023 : 8548038 : kv_item->key, kv_item->value);
1024 : 8548018 : e = list_next(e);
1025 : : }
1026 : : }
1027 [ + + ]: 8548236 : if (minkey_replace[i]) {
1028 : : // replace the minimum key in the node to KEY
1029 : 223 : btree->kv_ops->get_kv(node[i], idx[i], k, v);
1030 : 223 : btree->kv_ops->set_kv(node[i], idx[i], key, v);
1031 : : }
1032 : 8548240 : modified[i] = 1;
1033 : :
1034 : : }else{
1035 : : //2 not enough
1036 : : // first check if the node can be enlarged
1037 [ + - + + ]: 113480 : if (btree->blk_ops->blk_enlarge_node &&
[ + + ]
1038 : 56740 : is_subblock(bid[i])) {
1039 : : bid_t new_bid;
1040 : : addr = btree->blk_ops->blk_enlarge_node(btree->blk_handle,
1041 : 2271 : bid[i], nodesize, &new_bid);
1042 [ + - ]: 2271 : if (addr) {
1043 : : // the node can be enlarged .. fetch the enlarged node
1044 : 2271 : moved[i] = 1;
1045 : 2271 : bid[i] = new_bid;
1046 : 2271 : node[i] = _fetch_bnode(btree, addr, i+1);
1047 [ + - ]: 2271 : if (i+1 == btree->height) {
1048 : : // if moved node is root node
1049 : 2271 : btree->root_bid = bid[i];
1050 : : }
1051 : : // start over
1052 : 2271 : goto check_node;
1053 : : }
1054 : : }
1055 : :
1056 : : //otherwise, split the node
1057 : : nsplitnode = _btree_get_nsplitnode(btree, BLK_NOT_FOUND,
1058 : 54469 : node[i], nodesize);
1059 : : // force the node split when the node size of new layout is
1060 : : // larger than the current node size
1061 [ - + ]: 54469 : if (nsplitnode == 1) nsplitnode = 2;
1062 : :
1063 : : height_growup = _btree_split_node(
1064 : : btree, key, node, bid, idx, i,
1065 : : kv_ins_list, nsplitnode, k, v,
1066 : 54469 : modified, minkey_replace, ins);
1067 : : } // split
1068 : : } // insert
1069 : :
1070 [ + + ]: 22389699 : if (height_growup) break;
1071 : :
1072 [ + + ]: 22389169 : if (modified[i]) {
1073 : : //2 when the node is modified
1074 [ + + ]: 8635584 : if (!btree->blk_ops->blk_is_writable(btree->blk_handle, bid[i])) {
1075 : : // not writable .. already flushed block -> cannot overwrite,
1076 : : // we have to move to new block
1077 : : height_growup = _btree_move_modified_node(
1078 : : btree, key, node, bid, idx, i,
1079 : : kv_ins_list, k, v,
1080 : 36194 : modified, minkey_replace, ins, moved);
1081 : :
1082 [ - + ]: 36194 : if (height_growup) break;
1083 : : }else{
1084 : : // writable .. just set dirty to write back into storage
1085 : 8599425 : btree->blk_ops->blk_set_dirty(btree->blk_handle, bid[i]);
1086 : : } // is writable
1087 : : } // is modified
1088 : : } // for loop
1089 : :
1090 : : // release temporary resources
1091 [ - + ]: 8548610 : if (btree->blk_ops->blk_operation_end) {
1092 : 0 : btree->blk_ops->blk_operation_end(btree->blk_handle);
1093 : : }
1094 [ + + ]: 8548561 : if (btree->kv_ops->free_kv_var) btree->kv_ops->free_kv_var(btree, k, v);
1095 : :
1096 [ + + ][ + + ]: 30938355 : for (j=0; j < ((height_growup)?(btree->height-1):(btree->height)); ++j){
1097 : 22389772 : e = list_begin(&kv_ins_list[j]);
1098 [ + + ]: 30992307 : while(e) {
1099 : 8602513 : kv_item = _get_entry(e, struct kv_ins_item, le);
1100 : 8602513 : e = list_remove(&kv_ins_list[j], e);
1101 : :
1102 [ + + ]: 8602513 : if (btree->kv_ops->free_kv_var) {
1103 : 9346 : btree->kv_ops->free_kv_var(btree, kv_item->key, kv_item->value);
1104 : : }
1105 : 8602513 : _kv_ins_item_free(kv_item);
1106 : : }
1107 : : }
1108 : :
1109 [ + + ]: 8548583 : if (_is_update) {
1110 : 505632 : return BTREE_RESULT_UPDATE;
1111 : : }else{
1112 : 8548583 : return BTREE_RESULT_SUCCESS;
1113 : : }
1114 : : }
1115 : :
1116 : 16 : btree_result btree_remove(struct btree *btree, void *key)
1117 : : {
1118 : : void *addr;
1119 : 16 : uint8_t *k = alca(uint8_t, btree->ksize);
1120 : 16 : uint8_t *v= alca(uint8_t, btree->vsize);
1121 : 16 : uint8_t *kk = alca(uint8_t, btree->ksize);
1122 : 16 : uint8_t *vv = alca(uint8_t, btree->vsize);
1123 : : // index# and block ID for each level
1124 : 16 : idx_t *idx = alca(idx_t, btree->height);
1125 : 16 : bid_t *bid= alca(bid_t, btree->height);
1126 : : bid_t _bid;
1127 : : // flags
1128 : 16 : int8_t *modified = alca(int8_t, btree->height);
1129 : 16 : int8_t *moved = alca(int8_t, btree->height);
1130 : 16 : int8_t *rmv = alca(int8_t, btree->height);
1131 : : // index# of removed key
1132 : 16 : idx_t *idx_rmv = alca(idx_t, btree->height);
1133 : 16 : struct bnode **node = alca(struct bnode *, btree->height);
1134 : : int i;
1135 : :
1136 : : // initialize flags
1137 [ + + ]: 32 : for (i=0;i<btree->height;++i) {
1138 : 16 : moved[i] = modified[i] = rmv[i] = 0;
1139 : : }
1140 [ + - ]: 16 : if (btree->kv_ops->init_kv_var) {
1141 : 16 : btree->kv_ops->init_kv_var(btree, k, v);
1142 : 16 : btree->kv_ops->init_kv_var(btree, kk, vv);
1143 : : }
1144 : :
1145 : 16 : rmv[0] = 1;
1146 : :
1147 : : // set root
1148 : 16 : bid[btree->height-1] = btree->root_bid;
1149 : :
1150 : : // find path from root to leaf
1151 [ + + ]: 32 : for (i=btree->height-1; i>=0; --i) {
1152 : : // read block using bid
1153 : 16 : addr = btree->blk_ops->blk_read(btree->blk_handle, bid[i]);
1154 : : // fetch node structure from block
1155 : 16 : node[i] = _fetch_bnode(btree, addr, i+1);
1156 : :
1157 : : // lookup key in current node
1158 : 16 : idx[i] = _btree_find_entry(btree, node[i], key);
1159 : :
1160 [ - + ]: 16 : if (idx[i] == BTREE_IDX_NOT_FOUND) {
1161 : : // not found
1162 [ # # ]: 0 : if (btree->blk_ops->blk_operation_end)
1163 : 0 : btree->blk_ops->blk_operation_end(btree->blk_handle);
1164 [ # # ]: 0 : if (btree->kv_ops->free_kv_var) {
1165 : 0 : btree->kv_ops->free_kv_var(btree, k, v);
1166 : 0 : btree->kv_ops->free_kv_var(btree, kk, vv);
1167 : : }
1168 : 0 : return BTREE_RESULT_FAIL;
1169 : : }
1170 : :
1171 : 16 : btree->kv_ops->get_kv(node[i], idx[i], k, v);
1172 : :
1173 [ - + ]: 16 : if (i>0) {
1174 : : // index (non-leaf) node
1175 : : // get bid of child node from value
1176 : 0 : bid[i-1] = btree->kv_ops->value2bid(v);
1177 : 0 : bid[i-1] = _endian_decode(bid[i-1]);
1178 : : }else{
1179 : : // leaf node
1180 : : }
1181 : : }
1182 : :
1183 : : // cascaded remove from leaf to root
1184 [ + + ]: 32 : for (i=0;i<btree->height;++i){
1185 : : // in case of index node
1186 [ - + ]: 16 : if (i > 0) {
1187 : 0 : btree->kv_ops->get_kv(node[i], idx[i], k, v);
1188 : :
1189 : : // when child node's smallest key is changed due to remove
1190 [ # # ]: 0 : if (node[i-1]->nentry > 0) {
1191 : 0 : btree->kv_ops->get_kv(node[i-1], 0, kk, vv);
1192 [ # # ]: 0 : if (btree->kv_ops->cmp(kk, k, btree->aux)) {
1193 : : // change current node's corresponding key
1194 : 0 : btree->kv_ops->set_kv(node[i], idx[i], kk, v);
1195 : : //memcpy(k, kk, btree->ksize);
1196 : 0 : btree->kv_ops->set_key(btree, k, kk);
1197 : 0 : modified[i] = 1;
1198 : : }
1199 : : }
1200 : :
1201 : : // when child node is moved to new block
1202 [ # # ]: 0 : if (moved[i-1]) {
1203 : : // replace the bid (value)
1204 : 0 : _bid = _endian_encode(bid[i-1]);
1205 : 0 : btree->kv_ops->set_kv(node[i], idx[i], k,
1206 : 0 : btree->kv_ops->bid2value(&_bid));
1207 : 0 : modified[i] = 1;
1208 : : }
1209 : : }
1210 : :
1211 [ + - ]: 16 : if (rmv[i]) {
1212 : : // there is a key-value pair to be removed
1213 : 16 : btree->kv_ops->get_kv(node[i], idx[i], k, v);
1214 : 16 : idx_rmv[i] = _btree_remove_entry(btree, node[i], k);
1215 : 16 : modified[i] = 1;
1216 : :
1217 : : /*
1218 : : remove the node when
1219 : : 1. non-root node has no kv-pair or
1220 : : 2. root node has less or equal than one kv-pair
1221 : : */
1222 [ + + ][ + - ]: 16 : if (((node[i]->nentry < 1 && i+1 < btree->height) ||
[ + + ][ + - ]
[ - + ]
1223 : 16 : (node[i]->nentry <= 1 && i+1 == btree->height)) &&
1224 : : btree->height > 1) {
1225 : : // remove the node
1226 : 0 : btree->blk_ops->blk_remove(btree->blk_handle, bid[i]);
1227 [ # # ]: 0 : if (i+1 < btree->height) {
1228 : : // if non-root node
1229 : 0 : rmv[i+1] = 1;
1230 : : }else{
1231 : : // if root node
1232 : 0 : btree->height--;
1233 : 0 : btree->kv_ops->get_kv(node[i], 0, k, v);
1234 : 0 : btree->root_bid = btree->kv_ops->value2bid(v);
1235 : 0 : btree->root_bid = _endian_decode(btree->root_bid);
1236 : : }
1237 : : }
1238 : : }
1239 : :
1240 [ + - ]: 16 : if (modified[i]) {
1241 : : // when node is modified
1242 [ + + ]: 16 : if (!btree->blk_ops->blk_is_writable(btree->blk_handle, bid[i])) {
1243 : : // already flushed block -> cannot overwrite, so
1244 : : // we have to move to new block
1245 : : // get new bid[i]
1246 : 11 : addr = btree->blk_ops->blk_move(btree->blk_handle, bid[i],
1247 : 11 : &bid[i]);
1248 : 11 : node[i] = _fetch_bnode(btree, addr, i+1);
1249 : 11 : moved[i] = 1;
1250 : :
1251 [ + - ]: 11 : if (i+1 == btree->height)
1252 : : // if moved node is root node
1253 : 11 : btree->root_bid = bid[i];
1254 : :
1255 : : }else{
1256 : 5 : btree->blk_ops->blk_set_dirty(btree->blk_handle, bid[i]);
1257 : : }
1258 : :
1259 : : }
1260 : : }
1261 : :
1262 [ - + ]: 16 : if (btree->blk_ops->blk_operation_end) {
1263 : 0 : btree->blk_ops->blk_operation_end(btree->blk_handle);
1264 : : }
1265 [ + + ]: 16 : if (btree->kv_ops->free_kv_var) {
1266 : 1 : btree->kv_ops->free_kv_var(btree, k, v);
1267 : 1 : btree->kv_ops->free_kv_var(btree, kk, vv);
1268 : : }
1269 : 16 : return BTREE_RESULT_SUCCESS;
1270 : : }
1271 : :
1272 : 0 : btree_result btree_operation_end(struct btree *btree)
1273 : : {
1274 [ # # ]: 0 : if (btree->blk_ops->blk_operation_end) {
1275 : 0 : btree->blk_ops->blk_operation_end(btree->blk_handle);
1276 : : }
1277 : 0 : return BTREE_RESULT_SUCCESS;
1278 : : }
1279 : :
1280 : 15783 : btree_result btree_iterator_init(struct btree *btree,
1281 : : struct btree_iterator *it, void *initial_key)
1282 : : {
1283 : : int i;
1284 : :
1285 : 15783 : it->btree = *btree;
1286 : 15783 : it->curkey = (void *)mempool_alloc(btree->ksize);
1287 [ + - ]: 15783 : if (btree->kv_ops->init_kv_var) {
1288 : 15783 : btree->kv_ops->init_kv_var(btree, it->curkey, NULL);
1289 : : }
1290 [ + + ]: 15783 : if (initial_key) {
1291 : : // set initial key if exists
1292 : : //memcpy(it->curkey, initial_key, btree->ksize);
1293 : 11886 : btree->kv_ops->set_key(btree, it->curkey, initial_key);
1294 : : }else{
1295 : : // NULL initial key .. set minimum key (start from leftmost key)
1296 : : // replaced by kv_ops->init_kv_var
1297 : : //memset(it->curkey, 0, btree->ksize);
1298 : : }
1299 : 15783 : it->bid = (bid_t*)mempool_alloc(sizeof(bid_t) * btree->height);
1300 : 15783 : it->idx = (idx_t*)mempool_alloc(sizeof(idx_t) * btree->height);
1301 : : it->node = (struct bnode **)mempool_alloc(sizeof(struct bnode *)
1302 : 15783 : * btree->height);
1303 : 15783 : it->addr = (void**)mempool_alloc(sizeof(void*) * btree->height);
1304 : :
1305 [ + + ]: 31671 : for (i=0;i<btree->height;++i){
1306 : 15888 : it->bid[i] = BTREE_BLK_NOT_FOUND;
1307 : 15888 : it->idx[i] = BTREE_IDX_NOT_FOUND;
1308 : 15888 : it->node[i] = NULL;
1309 : 15888 : it->addr[i] = NULL;
1310 : : }
1311 : 15783 : it->bid[btree->height-1] = btree->root_bid;
1312 : 15783 : it->flags = 0;
1313 : :
1314 : 15783 : return BTREE_RESULT_SUCCESS;
1315 : : }
1316 : :
1317 : 15783 : btree_result btree_iterator_free(struct btree_iterator *it)
1318 : : {
1319 : : int i;
1320 [ + + ]: 15783 : if (it->btree.kv_ops->free_kv_var) {
1321 : 35 : it->btree.kv_ops->free_kv_var(&it->btree, it->curkey, NULL);
1322 : : }
1323 : 15783 : mempool_free(it->curkey);
1324 : 15783 : mempool_free(it->bid);
1325 : 15783 : mempool_free(it->idx);
1326 [ + + ]: 31671 : for (i=0;i<it->btree.height;++i){
1327 [ + + ]: 15888 : if (it->node[i]) mempool_free(it->addr[i]);
1328 : : }
1329 : 15783 : mempool_free(it->node);
1330 : 15783 : mempool_free(it->addr);
1331 : 15783 : return BTREE_RESULT_SUCCESS;
1332 : : }
1333 : :
1334 : 33641 : btree_result _btree_prev(struct btree_iterator *it, void *key_buf,
1335 : : void *value_buf, int depth)
1336 : : {
1337 : : struct btree *btree;
1338 : 33641 : btree = &it->btree;
1339 : : int i;
1340 : 33641 : uint8_t *k = alca(uint8_t, btree->ksize);
1341 : 33641 : uint8_t *v = alca(uint8_t, btree->vsize);
1342 : : void *addr;
1343 : : struct bnode *node;
1344 : : btree_result r;
1345 : :
1346 [ + - ]: 33641 : if (it->btree.kv_ops->init_kv_var) {
1347 : 33641 : it->btree.kv_ops->init_kv_var(&it->btree, k, v);
1348 : : }
1349 : :
1350 [ + + ]: 33641 : if (it->node[depth] == NULL){
1351 : : size_t blksize;
1352 : 6620 : addr = btree->blk_ops->blk_read(btree->blk_handle, it->bid[depth]);
1353 : 6620 : it->addr[depth] = (void *)mempool_alloc(btree->blksize);
1354 : : blksize = btree->blk_ops->blk_get_size(btree->blk_handle,
1355 : 6620 : it->bid[depth]);
1356 : 6620 : memcpy(it->addr[depth], addr, blksize);
1357 : 6620 : it->node[depth] = _fetch_bnode(&it->btree, it->addr[depth], depth+1);
1358 : : }
1359 : 33641 : node = _fetch_bnode(&it->btree, it->addr[depth], depth+1);
1360 : : //assert(node->level == depth+1);
1361 : :
1362 [ - + ]: 33641 : if (node->nentry <= 0) {
1363 [ # # ]: 0 : if (it->btree.kv_ops->free_kv_var) {
1364 : 0 : it->btree.kv_ops->free_kv_var(&it->btree, k, v);
1365 : : }
1366 [ # # ]: 0 : if (it->node[depth] != NULL) mempool_free(it->addr[depth]);
1367 : 0 : it->node[depth] = NULL;
1368 : 0 : it->addr[depth] = NULL;
1369 : 0 : return BTREE_RESULT_FAIL;
1370 : : }
1371 : :
1372 [ + + ]: 33641 : if (it->idx[depth] == BTREE_IDX_NOT_FOUND) {
1373 : : // curkey: lastly returned key
1374 : 6620 : it->idx[depth] = _btree_find_entry(btree, node, it->curkey);
1375 [ + + ]: 6620 : if (it->idx[depth] == BTREE_IDX_NOT_FOUND) {
1376 : 38 : it->idx[depth] = 0;
1377 : : // it->idx[depth] = node->nentry - 1;
1378 : : }
1379 : 6620 : btree->kv_ops->get_kv(node, it->idx[depth], key_buf, value_buf);
1380 [ + + ][ + + ]: 6620 : if (btree->kv_ops->cmp(it->curkey, key_buf, btree->aux) < 0 &&
[ + + ]
1381 : : depth == 0) {
1382 : : // in leaf node, prev key must be smaller than current key
1383 : 37 : it->idx[depth] = it->idx[depth] ? it->idx[depth] - 1
1384 [ - + ]: 37 : : BTREE_IDX_NOT_FOUND;
1385 : : } // else return the value at idx[depth] at this turn
1386 : : }
1387 : :
1388 [ + + ][ + + ]: 33641 : if (BTREE_ITR_IS_FWD(it) && depth ==0) {
1389 [ + + ]: 2401 : if (it->idx[depth] >= 2) {
1390 : 1953 : it->idx[depth] -= 2;
1391 : : } else {
1392 : : // out-of-bounds
1393 : 448 : it->idx[depth] = node->nentry; // ending condition
1394 : : // we have to reset flag because _btree_prev will recursively
1395 : : // visit the left leaf node.
1396 : 448 : BTREE_ITR_SET_NONE(it);
1397 : : }
1398 : : }
1399 : :
1400 [ + + ]: 33641 : if (it->idx[depth] >= node->nentry) { // reused nentry for ending iteration
1401 : : // out of bound .. go up to parent node
1402 : 4764 : it->idx[depth] = BTREE_IDX_NOT_FOUND; // reset for btree_next
1403 [ + - ]: 4764 : if (it->node[depth] != NULL) mempool_free(it->addr[depth]);
1404 : 4764 : it->node[depth] = NULL;
1405 : 4764 : it->addr[depth] = NULL;
1406 : :
1407 [ + + ]: 4764 : if (it->btree.kv_ops->free_kv_var) {
1408 : 2 : it->btree.kv_ops->free_kv_var(&it->btree, k, v);
1409 : : }
1410 : 4764 : return BTREE_RESULT_FAIL;
1411 : : }
1412 : :
1413 [ + + ]: 28877 : if (depth > 0) {
1414 : : // index node
1415 [ + + ]: 1073 : if (it->node[depth-1] == NULL) {
1416 : 4 : btree->kv_ops->get_kv(node, it->idx[depth], k, v);
1417 : 4 : it->bid[depth-1] = btree->kv_ops->value2bid(v);
1418 : 4 : it->bid[depth-1] = _endian_decode(it->bid[depth-1]);
1419 : : }
1420 : 1073 : r = _btree_prev(it, key_buf, value_buf, depth-1);
1421 : :
1422 [ + + ]: 1073 : if (r == BTREE_RESULT_FAIL) {
1423 : : // move index to left
1424 : 31 : it->idx[depth] = it->idx[depth] ? it->idx[depth] - 1
1425 [ + + ]: 18 : : node->nentry; // ending condition
1426 : :
1427 [ + + ]: 18 : if (it->idx[depth] >= node->nentry){
1428 : : // out of bound .. go up to parent node
1429 : 5 : it->idx[depth] = BTREE_IDX_NOT_FOUND;
1430 [ + - ]: 5 : if (it->node[depth] != NULL) mempool_free(it->addr[depth]);
1431 : 5 : it->node[depth] = NULL;
1432 : 5 : it->addr[depth] = NULL;
1433 : :
1434 [ - + ]: 5 : if (it->btree.kv_ops->free_kv_var) {
1435 : 0 : it->btree.kv_ops->free_kv_var(&it->btree, k, v);
1436 : : }
1437 : 5 : return BTREE_RESULT_FAIL;
1438 : : }else{
1439 : 13 : btree->kv_ops->get_kv(node, it->idx[depth], k, v);
1440 : 13 : it->bid[depth-1] = btree->kv_ops->value2bid(v);
1441 : 13 : it->bid[depth-1] = _endian_decode(it->bid[depth-1]);
1442 : : // reset child index
1443 [ + + ]: 26 : for (i=depth-1; i>=0; --i) {
1444 : 13 : it->idx[i] = BTREE_IDX_NOT_FOUND;
1445 [ - + ]: 13 : if (it->node[i] != NULL) mempool_free(it->addr[i]);
1446 : 13 : it->node[i] = NULL;
1447 : 13 : it->addr[i] = NULL;
1448 : : }
1449 : : // retry
1450 : 13 : r = _btree_prev(it, key_buf, value_buf, depth-1);
1451 : : }
1452 : : }
1453 [ - + ]: 1068 : if (it->btree.kv_ops->free_kv_var) {
1454 : 0 : it->btree.kv_ops->free_kv_var(&it->btree, k, v);
1455 : : }
1456 : 1068 : return r;
1457 : : }else{
1458 : : // leaf node
1459 : 27804 : btree->kv_ops->get_kv(node, it->idx[depth], key_buf, value_buf);
1460 : : //memcpy(it->curkey, key_buf, btree->ksize);
1461 : 27804 : btree->kv_ops->set_key(btree, it->curkey, key_buf);
1462 : 49221 : it->idx[depth] = it->idx[depth] ? it->idx[depth] - 1
1463 [ + + ]: 27804 : : node->nentry; // condition for ending
1464 [ + + ]: 27804 : if (it->btree.kv_ops->free_kv_var) {
1465 : 51 : it->btree.kv_ops->free_kv_var(&it->btree, k, v);
1466 : : }
1467 : 33641 : return BTREE_RESULT_SUCCESS;
1468 : : }
1469 : : }
1470 : :
1471 : 32555 : btree_result btree_prev(struct btree_iterator *it, void *key_buf,
1472 : : void *value_buf)
1473 : : {
1474 : 32555 : btree_result br = _btree_prev(it, key_buf, value_buf, it->btree.height-1);
1475 [ + + ]: 32555 : if (br == BTREE_RESULT_SUCCESS) {
1476 : 27804 : BTREE_ITR_SET_REV(it);
1477 : : } else {
1478 : 4751 : BTREE_ITR_SET_NONE(it);
1479 : : }
1480 : 32555 : return br;
1481 : : }
1482 : :
1483 : 6132666 : btree_result _btree_next(struct btree_iterator *it, void *key_buf,
1484 : : void *value_buf, int depth)
1485 : : {
1486 : : struct btree *btree;
1487 : 6132666 : btree = &it->btree;
1488 : : int i;
1489 : 6132666 : uint8_t *k = alca(uint8_t, btree->ksize);
1490 : 6132666 : uint8_t *v = alca(uint8_t, btree->vsize);
1491 : : void *addr;
1492 : : struct bnode *node;
1493 : : btree_result r;
1494 : :
1495 [ + - ]: 6132666 : if (it->btree.kv_ops->init_kv_var) {
1496 : 6132815 : it->btree.kv_ops->init_kv_var(&it->btree, k, v);
1497 : : }
1498 : :
1499 [ + + ]: 6132606 : if (it->node[depth] == NULL){
1500 : : size_t blksize;
1501 : 21333 : addr = btree->blk_ops->blk_read(btree->blk_handle, it->bid[depth]);
1502 : 21333 : it->addr[depth] = (void *)mempool_alloc(btree->blksize);
1503 : : blksize = btree->blk_ops->blk_get_size(btree->blk_handle,
1504 : 21333 : it->bid[depth]);
1505 : 21333 : memcpy(it->addr[depth], addr, blksize);
1506 : 21333 : it->node[depth] = _fetch_bnode(&it->btree, it->addr[depth], depth+1);
1507 : : }
1508 : 6132606 : node = _fetch_bnode(&it->btree, it->addr[depth], depth+1);
1509 : : //assert(node->level == depth+1);
1510 : :
1511 [ - + ]: 6133129 : if (node->nentry <= 0) {
1512 [ # # ]: 0 : if (it->btree.kv_ops->free_kv_var) it->btree.kv_ops->free_kv_var(
1513 : 0 : &it->btree, k, v);
1514 [ # # ]: 0 : if (it->node[depth] != NULL) mempool_free(it->addr[depth]);
1515 : 0 : it->node[depth] = NULL;
1516 : 0 : it->addr[depth] = NULL;
1517 : 0 : return BTREE_RESULT_FAIL;
1518 : : }
1519 : :
1520 [ + + ]: 6133129 : if (it->idx[depth] == BTREE_IDX_NOT_FOUND) {
1521 : : // curkey: lastly returned key
1522 : 9281 : it->idx[depth] = _btree_find_entry(btree, node, it->curkey);
1523 [ + + ]: 9281 : if (it->idx[depth] == BTREE_IDX_NOT_FOUND) {
1524 : 2222 : it->idx[depth] = 0;
1525 : : }
1526 : 9281 : btree->kv_ops->get_kv(node, it->idx[depth], key_buf, value_buf);
1527 [ + + ][ + + ]: 9281 : if (btree->kv_ops->cmp(it->curkey, key_buf, btree->aux) > 0 &&
[ + + ]
1528 : : depth == 0) {
1529 : : // in leaf node, next key must be larger than previous key
1530 : : // (i.e. it->curkey)
1531 : 1182 : it->idx[depth]++;
1532 : : }
1533 : : }
1534 : :
1535 [ + + ][ + + ]: 6133129 : if (BTREE_ITR_IS_REV(it) && depth == 0) {
1536 [ + + ]: 1932 : if (it->idx[depth] >= node->nentry) {
1537 : : // 'idx' becomes out-of-bounds by previous btree_prev() call.
1538 : : // this means that the last returned entry was the smallest entry.
1539 : : // set idx to the second smallest entry.
1540 : 400 : it->idx[depth] = 1;
1541 : : } else {
1542 : 1532 : it->idx[depth] += 2;
1543 : : }
1544 : : }
1545 : :
1546 [ + + ]: 6133129 : if (it->idx[depth] >= node->nentry) {
1547 : : // out of bound .. go up to parent node
1548 : 17108 : it->idx[depth] = BTREE_IDX_NOT_FOUND; // reset for btree_prev
1549 [ + - ]: 17108 : if (it->node[depth] != NULL) mempool_free(it->addr[depth]);
1550 : 17108 : it->node[depth] = NULL;
1551 : 17108 : it->addr[depth] = NULL;
1552 : :
1553 [ + + ]: 17108 : if (it->btree.kv_ops->free_kv_var) {
1554 : 73 : it->btree.kv_ops->free_kv_var(&it->btree, k, v);
1555 : : }
1556 : 17108 : return BTREE_RESULT_FAIL;
1557 : : }
1558 : :
1559 [ + + ]: 6116021 : if (depth > 0) {
1560 : : // index node
1561 [ + + ]: 4021349 : if (it->node[depth-1] == NULL) {
1562 : 157 : btree->kv_ops->get_kv(node, it->idx[depth], k, v);
1563 : 157 : it->bid[depth-1] = btree->kv_ops->value2bid(v);
1564 : 157 : it->bid[depth-1] = _endian_decode(it->bid[depth-1]);
1565 : : }
1566 : 4021349 : r = _btree_next(it, key_buf, value_buf, depth-1);
1567 : :
1568 [ + + ]: 4021253 : if (r == BTREE_RESULT_FAIL) {
1569 : : // move index to right
1570 : 12148 : it->idx[depth]++;
1571 : :
1572 [ + + ]: 12148 : if (it->idx[depth] >= node->nentry){
1573 : : // out of bound .. go up to parent node
1574 : 152 : it->idx[depth] = BTREE_IDX_NOT_FOUND;
1575 [ + - ]: 152 : if (it->node[depth] != NULL) mempool_free(it->addr[depth]);
1576 : 152 : it->node[depth] = NULL;
1577 : 152 : it->addr[depth] = NULL;
1578 : :
1579 [ + + ]: 152 : if (it->btree.kv_ops->free_kv_var) {
1580 : 6 : it->btree.kv_ops->free_kv_var(&it->btree, k, v);
1581 : : }
1582 : 152 : return BTREE_RESULT_FAIL;
1583 : : }else{
1584 : 11996 : btree->kv_ops->get_kv(node, it->idx[depth], k, v);
1585 : 11996 : it->bid[depth-1] = btree->kv_ops->value2bid(v);
1586 : 11996 : it->bid[depth-1] = _endian_decode(it->bid[depth-1]);
1587 : : // reset child index
1588 [ + + ]: 24048 : for (i=depth-1; i>=0; --i) {
1589 : 12052 : it->idx[i] = 0;
1590 [ - + ]: 12052 : if (it->node[i] != NULL) mempool_free(it->addr[i]);
1591 : 12052 : it->node[i] = NULL;
1592 : 12052 : it->addr[i] = NULL;
1593 : : }
1594 : : // retry
1595 : 11996 : r = _btree_next(it, key_buf, value_buf, depth-1);
1596 : : }
1597 : : }
1598 [ + + ]: 4021101 : if (it->btree.kv_ops->free_kv_var) {
1599 : 4019 : it->btree.kv_ops->free_kv_var(&it->btree, k, v);
1600 : : }
1601 : 4021275 : return r;
1602 : : }else{
1603 : : // leaf node
1604 : 2094672 : btree->kv_ops->get_kv(node, it->idx[depth], key_buf, value_buf);
1605 : : //memcpy(it->curkey, key_buf, btree->ksize);
1606 : 2094661 : btree->kv_ops->set_key(btree, it->curkey, key_buf);
1607 : 2094640 : it->idx[depth]++;
1608 [ + + ]: 2094640 : if (it->btree.kv_ops->free_kv_var) {
1609 : 4441 : it->btree.kv_ops->free_kv_var(&it->btree, k, v);
1610 : : }
1611 : 6133178 : return BTREE_RESULT_SUCCESS;
1612 : : }
1613 : : }
1614 : :
1615 : 2099802 : btree_result btree_next(struct btree_iterator *it, void *key_buf,
1616 : : void *value_buf)
1617 : : {
1618 : 2099802 : btree_result br = _btree_next(it, key_buf, value_buf, it->btree.height-1);
1619 [ + + ]: 2099596 : if (br == BTREE_RESULT_SUCCESS) {
1620 : 2094484 : BTREE_ITR_SET_FWD(it);
1621 : : } else {
1622 : 5112 : BTREE_ITR_SET_NONE(it);
1623 : : }
1624 : 2099596 : return br;
1625 : : }
1626 : :
|
