Branch data Line data Source code
1 : : /* -*- Mode: C++; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
2 : : /*
3 : : * Copyright 2010 Couchbase, Inc
4 : : *
5 : : * Licensed under the Apache License, Version 2.0 (the "License");
6 : : * you may not use this file except in compliance with the License.
7 : : * You may obtain a copy of the License at
8 : : *
9 : : * http://www.apache.org/licenses/LICENSE-2.0
10 : : *
11 : : * Unless required by applicable law or agreed to in writing, software
12 : : * distributed under the License is distributed on an "AS IS" BASIS,
13 : : * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 : : * See the License for the specific language governing permissions and
15 : : * limitations under the License.
16 : : */
17 : :
18 : : #include <stdio.h>
19 : : #include <stdlib.h>
20 : : #include <string.h>
21 : : #include <fcntl.h>
22 : :
23 : : #include "libforestdb/forestdb.h"
24 : : #include "fdb_internal.h"
25 : : #include "hbtrie.h"
26 : : #include "docio.h"
27 : : #include "btreeblock.h"
28 : : #include "common.h"
29 : : #include "wal.h"
30 : : #include "snapshot.h"
31 : : #include "avltree.h"
32 : : #include "list.h"
33 : : #include "internal_types.h"
34 : : #include "btree_var_kv_ops.h"
35 : :
36 : : #include "memleak.h"
37 : :
38 : : #ifdef __DEBUG
39 : : #ifndef __DEBUG_FDB
40 : : #undef DBG
41 : : #undef DBGCMD
42 : : #undef DBGSW
43 : : #define DBG(...)
44 : : #define DBGCMD(...)
45 : : #define DBGSW(n, ...)
46 : : #endif
47 : : #endif
48 : :
49 : : // lexicographically compares two variable-length binary streams
50 : 199404 : int _fdb_keycmp(void *key1, size_t keylen1, void *key2, size_t keylen2)
51 : : {
52 [ + + ]: 199404 : if (keylen1 == keylen2) {
53 : 122168 : return memcmp(key1, key2, keylen1);
54 : : }else {
55 [ + + ]: 77236 : size_t len = MIN(keylen1, keylen2);
56 : 77236 : int cmp = memcmp(key1, key2, len);
57 [ + + ]: 77236 : if (cmp != 0) return cmp;
58 : : else {
59 : 199404 : return (int)((int)keylen1 - (int)keylen2);
60 : : }
61 : : }
62 : : }
63 : :
64 : 3389 : int _fdb_seqnum_cmp(struct avl_node *a, struct avl_node *b, void *aux)
65 : : {
66 : : struct snap_wal_entry *aa, *bb;
67 : 3389 : aa = _get_entry(a, struct snap_wal_entry, avl_seq);
68 : 3389 : bb = _get_entry(b, struct snap_wal_entry, avl_seq);
69 : 3389 : return (aa->seqnum - bb->seqnum);
70 : : }
71 : :
72 : 28654 : int _fdb_wal_cmp(struct avl_node *a, struct avl_node *b, void *aux)
73 : : {
74 : 28654 : _fdb_key_cmp_info *info = (_fdb_key_cmp_info*)aux;
75 : : struct snap_wal_entry *aa, *bb;
76 : 28654 : aa = _get_entry(a, struct snap_wal_entry, avl);
77 : 28654 : bb = _get_entry(b, struct snap_wal_entry, avl);
78 : :
79 [ + + ]: 28654 : if (info->kvs_config.custom_cmp) {
80 : : // custom compare function for variable-length key
81 [ + - ]: 10943 : if (info->kvs) {
82 : : // multi KV instance mode
83 : : // KV ID should be compared separately
84 : 10943 : size_t size_id = sizeof(fdb_kvs_id_t);
85 : : fdb_kvs_id_t a_id, b_id, _a_id, _b_id;
86 : 10943 : _a_id = *(fdb_kvs_id_t*)aa->key;
87 : 10943 : _b_id = *(fdb_kvs_id_t*)bb->key;
88 : 10943 : a_id = _endian_decode(_a_id);
89 : 10943 : b_id = _endian_decode(_b_id);
90 : :
91 [ - + ]: 10943 : if (a_id < b_id) {
92 : 0 : return -1;
93 [ - + ]: 10943 : } else if (a_id > b_id) {
94 : 0 : return 1;
95 : : } else {
96 [ - + ]: 10943 : if (aa->keylen == size_id) { // key1 < key2
97 : 0 : return -1;
98 [ + + ]: 10943 : } else if (bb->keylen == size_id) { // key1 > key2
99 : 37 : return 1;
100 : : }
101 : : return info->kvs_config.custom_cmp(
102 : 10906 : (uint8_t*)aa->key + size_id, aa->keylen - size_id,
103 : 10906 : (uint8_t*)bb->key + size_id, bb->keylen - size_id);
104 : : }
105 : : } else {
106 : : return info->kvs_config.custom_cmp(aa->key, aa->keylen,
107 : 0 : bb->key, bb->keylen);
108 : : }
109 : : } else {
110 : 28654 : return _fdb_keycmp(aa->key, aa->keylen, bb->key, bb->keylen);
111 : : }
112 : : }
113 : :
114 : 116765 : int _fdb_key_cmp(fdb_iterator *iterator, void *key1, size_t keylen1,
115 : : void *key2, size_t keylen2) {
116 : : int cmp;
117 [ + + ]: 116765 : if (iterator->handle.kvs_config.custom_cmp) {
118 : : // custom compare function for variable length key
119 [ + - ]: 7873 : if (iterator->handle.kvs) {
120 : : // multi KV instance mode
121 : : // KV ID should be compared separately
122 : 7873 : size_t size_id = sizeof(fdb_kvs_id_t);
123 : : fdb_kvs_id_t a_id, b_id, _a_id, _b_id;
124 : 7873 : _a_id = *(fdb_kvs_id_t*)key1;
125 : 7873 : _b_id = *(fdb_kvs_id_t*)key2;
126 : 7873 : a_id = _endian_decode(_a_id);
127 : 7873 : b_id = _endian_decode(_b_id);
128 : :
129 [ + + ]: 7873 : if (a_id < b_id) {
130 : 102 : cmp = -1;
131 [ + + ]: 7771 : } else if (a_id > b_id) {
132 : 5891 : cmp = 1;
133 : : } else {
134 [ + + ]: 1880 : if (keylen1 == size_id) { // key1 < key2
135 : 1363 : return -1;
136 [ - + ]: 517 : } else if (keylen2 == size_id) { // key1 > key2
137 : 0 : return 1;
138 : : }
139 : : cmp = iterator->handle.kvs_config.custom_cmp(
140 : 517 : (uint8_t*)key1 + size_id, keylen1 - size_id,
141 : 517 : (uint8_t*)key2 + size_id, keylen2 - size_id);
142 : : }
143 : : } else {
144 : : cmp = iterator->handle.kvs_config.custom_cmp(key1, keylen1,
145 : 0 : key2, keylen2);
146 : : }
147 : : } else {
148 : 108892 : cmp = _fdb_keycmp(key1, keylen1, key2, keylen2);
149 : : }
150 : 116765 : return cmp;
151 : : }
152 : :
153 : 84 : fdb_status fdb_iterator_init(fdb_kvs_handle *handle,
154 : : fdb_iterator **ptr_iterator,
155 : : const void *start_key,
156 : : size_t start_keylen,
157 : : const void *end_key,
158 : : size_t end_keylen,
159 : : fdb_iterator_opt_t opt)
160 : : {
161 : : int cmp;
162 : : hbtrie_result hr;
163 : : struct list_elem *he, *ie;
164 : : struct wal_item_header *wal_item_header;
165 : : struct wal_item *wal_item;
166 : : struct snap_wal_entry *snap_item;
167 : :
168 [ + - ][ + - ]: 84 : if (handle == NULL ||
[ + - ][ + - ]
[ - + ]
169 : : start_keylen > FDB_MAX_KEYLEN ||
170 : : start_keylen > handle->config.blocksize - 256 ||
171 : : end_keylen > FDB_MAX_KEYLEN ||
172 : : end_keylen > handle->config.blocksize - 256) {
173 : 0 : return FDB_RESULT_INVALID_ARGS;
174 : : }
175 : :
176 [ + + ][ + - ]: 84 : if ((opt & FDB_ITR_SKIP_MIN_KEY && (!start_key || !start_keylen)) ||
[ + - ][ + + ]
[ + - ][ - + ]
177 : : (opt & FDB_ITR_SKIP_MAX_KEY && (!end_key || !end_keylen))) {
178 : 0 : return FDB_RESULT_INVALID_ARGS;
179 : : }
180 : :
181 [ + + ]: 84 : if (!handle->shandle) {
182 : 76 : fdb_check_file_reopen(handle);
183 : 76 : fdb_link_new_file(handle);
184 : 76 : fdb_sync_db_header(handle);
185 : : }
186 : :
187 : 84 : fdb_iterator *iterator = (fdb_iterator *)calloc(1, sizeof(fdb_iterator));
188 : :
189 : 84 : iterator->handle = *handle;
190 : 84 : iterator->opt = opt;
191 : :
192 : 84 : iterator->_key = (void*)calloc(1, FDB_MAX_KEYLEN_INTERNAL);
193 : 84 : iterator->_keylen = 0;
194 : 84 : iterator->_offset = BLK_NOT_FOUND;
195 : 84 : iterator->hbtrie_iterator = NULL;
196 : 84 : iterator->seqtree_iterator = NULL;
197 : 84 : iterator->seqtrie_iterator = NULL;
198 : :
199 [ + - ]: 84 : if (handle->kvs) {
200 : : // multi KV instance mode .. prepend KV ID
201 : 84 : size_t size_id = sizeof(fdb_kvs_id_t);
202 : : uint8_t *start_key_temp, *end_key_temp;
203 : 84 : fdb_kvs_id_t _kv_id = _endian_encode(handle->kvs->id);
204 : :
205 [ + + ]: 84 : if (start_key == NULL) {
206 : 61 : start_key_temp = alca(uint8_t, size_id);
207 : 61 : memcpy(start_key_temp, &_kv_id, size_id);
208 : 61 : start_key = start_key_temp;
209 : 61 : start_keylen = size_id;
210 : : } else {
211 : 23 : start_key_temp = alca(uint8_t, size_id + start_keylen);
212 : 23 : memcpy(start_key_temp, &_kv_id, size_id);
213 : 23 : memcpy(start_key_temp + size_id, start_key, start_keylen);
214 : 23 : start_key = start_key_temp;
215 : 23 : start_keylen += size_id;
216 : : }
217 : :
218 [ + + ]: 84 : if (end_key == NULL) {
219 : 61 : end_key_temp = alca(uint8_t, size_id);
220 : : // set end_key as NULL key of the next KV ID.
221 : : // NULL key doesn't actually exist so that the iterator ends
222 : : // at the last key of the current KV ID.
223 : 61 : _kv_id = _endian_encode(handle->kvs->id+1);
224 : 61 : memcpy(end_key_temp, &_kv_id, size_id);
225 : 61 : end_key = end_key_temp;
226 : 61 : end_keylen = size_id;
227 : : } else {
228 : 23 : end_key_temp = alca(uint8_t, size_id + end_keylen);
229 : 23 : memcpy(end_key_temp, &_kv_id, size_id);
230 : 23 : memcpy(end_key_temp + size_id, end_key, end_keylen);
231 : 23 : end_key = end_key_temp;
232 : 23 : end_keylen += size_id;
233 : : }
234 : :
235 : 84 : iterator->start_key = (void*)malloc(start_keylen);
236 : 84 : memcpy(iterator->start_key, start_key, start_keylen);
237 : 84 : iterator->start_keylen = start_keylen;
238 : :
239 : 84 : iterator->end_key = (void*)malloc(end_keylen);
240 : 84 : memcpy(iterator->end_key, end_key, end_keylen);
241 : 84 : iterator->end_keylen = end_keylen;
242 : :
243 : : } else { // single KV instance mode
244 [ # # ]: 0 : if (start_key == NULL) {
245 : 0 : iterator->start_key = NULL;
246 : 0 : iterator->start_keylen = 0;
247 : : } else {
248 : 0 : iterator->start_key = (void*)malloc(start_keylen);
249 : 0 : memcpy(iterator->start_key, start_key, start_keylen);
250 : 0 : iterator->start_keylen = start_keylen;
251 : : }
252 : :
253 [ # # ]: 0 : if (end_key == NULL) {
254 : 0 : iterator->end_key = NULL;
255 : 0 : end_keylen = 0;
256 : : }else{
257 : 0 : iterator->end_key = (void*)malloc(end_keylen);
258 : 0 : memcpy(iterator->end_key, end_key, end_keylen);
259 : : }
260 : 0 : iterator->end_keylen = end_keylen;
261 : : }
262 : :
263 : : // create an iterator handle for hb-trie
264 : : iterator->hbtrie_iterator = (struct hbtrie_iterator *)
265 : 84 : malloc(sizeof(struct hbtrie_iterator));
266 : : hr = hbtrie_iterator_init(handle->trie, iterator->hbtrie_iterator,
267 : 84 : (void *)start_key, start_keylen);
268 [ - + ]: 84 : assert(hr == HBTRIE_RESULT_SUCCESS);
269 : :
270 : : // create a snapshot for WAL (avl-tree)
271 : : // (from the beginning to the last committed element)
272 : :
273 : : // init tree
274 [ + + ]: 84 : if (!handle->shandle) {
275 : : struct filemgr *wal_file;
276 : :
277 [ + - ]: 76 : if (handle->new_file == NULL) {
278 : 76 : wal_file = handle->file;
279 : : } else {
280 : 0 : wal_file = handle->new_file;
281 : : }
282 : :
283 : 76 : fdb_txn *txn = handle->fhandle->root->txn;
284 [ + - ]: 76 : if (!txn) {
285 : 76 : txn = &wal_file->global_txn;
286 : : }
287 : :
288 : 76 : iterator->wal_tree = (struct avl_tree*)malloc(sizeof(struct avl_tree));
289 : 76 : avl_init(iterator->wal_tree, (void*)handle);
290 : :
291 : 76 : spin_lock(&wal_file->wal->lock);
292 : 76 : he = list_begin(&wal_file->wal->list);
293 [ + + ]: 3137 : while(he) {
294 : 3061 : wal_item_header = _get_entry(he, struct wal_item_header, list_elem);
295 : 3061 : ie = list_begin(&wal_item_header->items);
296 [ + - ]: 3061 : if (txn->isolation == FDB_ISOLATION_READ_COMMITTED) {
297 : : // Search for the first uncommitted item belonging to this txn..
298 [ + - ]: 3061 : for (; ie; ie = list_next(ie)) {
299 : 3061 : wal_item = _get_entry(ie, struct wal_item, list_elem);
300 [ + - ]: 3061 : if (wal_item->txn == txn) {
301 : 3061 : break;
302 : : } // else fall through and pick the committed item at end..
303 : : }
304 [ - + ]: 3061 : if (!ie) {
305 : 0 : ie = list_end(&wal_item_header->items);
306 : : }
307 : : }
308 : :
309 : 3061 : wal_item = _get_entry(ie, struct wal_item, list_elem);
310 [ - + ]: 3061 : if (wal_item->flag & WAL_ITEM_BY_COMPACTOR) {
311 : : // ignore items moved by compactor
312 : 0 : he = list_next(he);
313 : 0 : continue;
314 : : }
315 [ + + ][ - + ]: 3061 : if ((wal_item->flag & WAL_ITEM_COMMITTED) ||
[ # # ]
316 : : (wal_item->txn == txn) ||
317 : : (txn->isolation == FDB_ISOLATION_READ_UNCOMMITTED)) {
318 [ + - ]: 3061 : if (end_key) {
319 : : cmp = _fdb_key_cmp(iterator,
320 : : (void *)end_key, end_keylen,
321 : : wal_item_header->key,
322 : 3061 : wal_item_header->keylen);
323 [ + + ][ + + ]: 3061 : if ((cmp == 0 && opt & FDB_ITR_SKIP_MAX_KEY) || cmp < 0) {
[ + + ]
324 : 553 : he = list_next(he);
325 : 553 : continue; // skip keys greater than max or equal (opt)
326 : : }
327 : : }
328 [ + - ]: 2508 : if (start_key) {
329 : : cmp = _fdb_key_cmp(iterator,
330 : : (void *)start_key, start_keylen,
331 : : wal_item_header->key,
332 : 2508 : wal_item_header->keylen);
333 [ + + ][ + + ]: 2508 : if ((cmp == 0 && opt & FDB_ITR_SKIP_MIN_KEY) || cmp > 0) {
[ + + ]
334 : 539 : he = list_next(he);
335 : 539 : continue; // skip keys smaller than min or equal (opt)
336 : : }
337 : : }
338 : : // copy from 'wal_item_header'
339 : : snap_item = (struct snap_wal_entry*)malloc(sizeof(
340 : 1969 : struct snap_wal_entry));
341 : 1969 : snap_item->keylen = wal_item_header->keylen;
342 : 1969 : snap_item->key = (void*)malloc(snap_item->keylen);
343 : 1969 : memcpy(snap_item->key, wal_item_header->key, snap_item->keylen);
344 : 1969 : snap_item->action = wal_item->action;
345 : 1969 : snap_item->offset = wal_item->offset;
346 [ - + ]: 1969 : if (wal_file == handle->new_file) {
347 : 0 : snap_item->flag = SNAP_ITEM_IN_NEW_FILE;
348 : : } else {
349 : 1969 : snap_item->flag = 0x0;
350 : : }
351 : :
352 : : // insert into tree
353 : 1969 : avl_insert(iterator->wal_tree, &snap_item->avl, _fdb_wal_cmp);
354 : : }
355 : 1969 : he = list_next(he);
356 : : }
357 : :
358 : 76 : spin_unlock(&wal_file->wal->lock);
359 : : } else {
360 : 8 : iterator->wal_tree = handle->shandle->key_tree;
361 : : }
362 : :
363 [ + - ]: 84 : if (iterator->wal_tree) {
364 [ + - ]: 84 : if (start_key) {
365 : : struct snap_wal_entry query;
366 : 84 : query.key = (void*)start_key;
367 : 84 : query.keylen = start_keylen;
368 : : iterator->tree_cursor = avl_search_greater(iterator->wal_tree,
369 : : &query.avl,
370 : 84 : _fdb_wal_cmp);
371 : : } else {
372 : 0 : iterator->tree_cursor = avl_first(iterator->wal_tree);
373 : : }
374 : : } else {
375 : 0 : iterator->tree_cursor = NULL;
376 : : }
377 : : // to know reverse iteration endpoint store the start cursor
378 : 84 : iterator->tree_cursor_start = iterator->tree_cursor;
379 : 84 : iterator->tree_cursor_prev = NULL;
380 : 84 : iterator->direction = FDB_ITR_DIR_NONE;
381 : 84 : iterator->status = FDB_ITR_IDX;
382 : 84 : iterator->_dhandle = NULL; // populated at the first iterator movement
383 : :
384 : 84 : *ptr_iterator = iterator;
385 : :
386 : 84 : fdb_iterator_next(iterator); // position cursor at first key
387 : :
388 : 84 : return FDB_RESULT_SUCCESS;
389 : : }
390 : :
391 : : LIBFDB_API
392 : 44 : fdb_status fdb_iterator_sequence_init(fdb_kvs_handle *handle,
393 : : fdb_iterator **ptr_iterator,
394 : : const fdb_seqnum_t start_seq,
395 : : const fdb_seqnum_t end_seq,
396 : : fdb_iterator_opt_t opt)
397 : : {
398 : : struct list_elem *he, *ie;
399 : : struct wal_item_header *wal_item_header;
400 : : struct wal_item *wal_item;
401 : : struct snap_wal_entry *snap_item;
402 : 44 : fdb_seqnum_t _start_seq = _endian_encode(start_seq);
403 : : fdb_kvs_id_t kv_id, _kv_id;
404 : : size_t size_id, size_seq;
405 : : uint8_t *start_seq_kv;
406 : :
407 [ + - ][ + - ]: 44 : if (handle == NULL || ptr_iterator == NULL ||
[ - + ]
408 : : start_seq > end_seq) {
409 : 0 : return FDB_RESULT_INVALID_ARGS;
410 : : }
411 : :
412 : : // Sequence trees are a must for byseq operations
413 [ + + ]: 44 : if (handle->config.seqtree_opt != FDB_SEQTREE_USE) {
414 : 1 : return FDB_RESULT_INVALID_CONFIG;
415 : : }
416 : :
417 [ + + ]: 43 : if (!handle->shandle) {
418 : 24 : fdb_check_file_reopen(handle);
419 : 24 : fdb_link_new_file(handle);
420 : 24 : fdb_sync_db_header(handle);
421 : : }
422 : :
423 : 43 : size_id = sizeof(fdb_kvs_id_t);
424 : 43 : size_seq = sizeof(fdb_seqnum_t);
425 : 43 : fdb_iterator *iterator = (fdb_iterator *)calloc(1, sizeof(fdb_iterator));
426 : :
427 : 43 : iterator->handle = *handle;
428 : 43 : iterator->hbtrie_iterator = NULL;
429 : 43 : iterator->_key = NULL;
430 : 43 : iterator->_keylen = 0;
431 : 43 : iterator->opt = opt;
432 : 43 : iterator->_offset = BLK_NOT_FOUND;
433 : 43 : iterator->_seqnum = start_seq;
434 : :
435 : : // For easy API call, treat zero seq as 0xffff...
436 : : // (because zero seq number is not used)
437 [ + + ]: 43 : if (end_seq == 0) {
438 : 21 : iterator->end_seqnum = SEQNUM_NOT_USED;
439 : : } else {
440 : 22 : iterator->end_seqnum = end_seq;
441 : : }
442 : :
443 : 43 : iterator->start_seqnum = start_seq;
444 : :
445 : 43 : iterator->start_key = NULL;
446 : 43 : iterator->end_key = NULL;
447 : :
448 [ + + ]: 43 : if (handle->kvs) {
449 : : // create an iterator handle for hb-trie
450 : 42 : start_seq_kv = alca(uint8_t, size_id + size_seq);
451 : 42 : _kv_id = _endian_encode(handle->kvs->id);
452 : 42 : memcpy(start_seq_kv, &_kv_id, size_id);
453 : 42 : memcpy(start_seq_kv + size_id, &_start_seq, size_seq);
454 : :
455 : : iterator->seqtrie_iterator = (struct hbtrie_iterator *)
456 : 42 : calloc(1, sizeof(struct hbtrie_iterator));
457 : : hbtrie_iterator_init(handle->seqtrie, iterator->seqtrie_iterator,
458 : 42 : start_seq_kv, size_id + size_seq);
459 : : } else {
460 : : // create an iterator handle for b-tree
461 : : iterator->seqtree_iterator = (struct btree_iterator *)
462 : 1 : calloc(1, sizeof(struct btree_iterator));
463 : : btree_iterator_init(handle->seqtree, iterator->seqtree_iterator,
464 [ - + ]: 1 : (void *)(start_seq ? &_start_seq : NULL));
465 : : }
466 : :
467 : : // create a snapshot for WAL (avl-tree)
468 : : // (from the beginning to the last committed element)
469 : :
470 : : // init tree
471 [ + + ]: 43 : if (!handle->shandle) {
472 : : struct filemgr *wal_file;
473 : :
474 [ + - ]: 24 : if (handle->new_file == NULL) {
475 : 24 : wal_file = handle->file;
476 : : } else {
477 : 0 : wal_file = handle->new_file;
478 : : }
479 : :
480 : 24 : fdb_txn *txn = handle->fhandle->root->txn;
481 [ + - ]: 24 : if (!txn) {
482 : 24 : txn = &wal_file->global_txn;
483 : : }
484 : :
485 : : iterator->wal_tree = (struct avl_tree*)
486 : 24 : malloc(sizeof(struct avl_tree));
487 : 24 : avl_init(iterator->wal_tree, (void*)_fdb_seqnum_cmp);
488 : :
489 : 24 : spin_lock(&wal_file->wal->lock);
490 : 24 : he = list_begin(&wal_file->wal->list);
491 [ + + ]: 1535 : while(he) {
492 : 1511 : wal_item_header = _get_entry(he, struct wal_item_header, list_elem);
493 : :
494 : : // compare committed item only (at the end of the list)
495 : 1511 : ie = list_end(&wal_item_header->items);
496 : 1511 : wal_item = _get_entry(ie, struct wal_item, list_elem);
497 [ - + ]: 1511 : if (wal_item->flag & WAL_ITEM_BY_COMPACTOR) {
498 : : // ignore items moved by compactor
499 : 0 : he = list_next(he);
500 : 0 : continue;
501 : : }
502 [ - + ][ # # ]: 1511 : if ((wal_item->flag & WAL_ITEM_COMMITTED) ||
[ # # ]
503 : : (wal_item->txn == txn) ||
504 : : (txn->isolation == FDB_ISOLATION_READ_UNCOMMITTED)) {
505 [ + - ]: 1511 : if (iterator->_seqnum <= wal_item->seqnum) {
506 : : // (documents whose seq numbers are greater than end_seqnum
507 : : // also have to be included for duplication check)
508 : : // copy from WAL_ITEM
509 [ + + ]: 1511 : if (handle->kvs) { // multi KV instance mode
510 : : // get KV ID from key
511 : 1505 : _kv_id = *((fdb_kvs_id_t*)wal_item_header->key);
512 : 1505 : kv_id = _endian_decode(_kv_id);
513 [ + + ]: 1505 : if (kv_id != handle->kvs->id) {
514 : : // KV instance doesn't match
515 : 905 : he = list_next(he);
516 : 905 : continue;
517 : : }
518 : : }
519 : : snap_item = (struct snap_wal_entry*)
520 : 606 : malloc(sizeof(struct snap_wal_entry));
521 : 606 : snap_item->keylen = wal_item_header->keylen;
522 : 606 : snap_item->key = (void*)malloc(snap_item->keylen);
523 : 606 : memcpy(snap_item->key, wal_item_header->key, snap_item->keylen);
524 : 606 : snap_item->seqnum = wal_item->seqnum;
525 : 606 : snap_item->action = wal_item->action;
526 : 606 : snap_item->offset = wal_item->offset;
527 [ - + ]: 606 : if (wal_file == handle->new_file) {
528 : 0 : snap_item->flag = SNAP_ITEM_IN_NEW_FILE;
529 : : } else {
530 : 606 : snap_item->flag = 0x0;
531 : : }
532 : :
533 : : // insert into tree
534 : : avl_insert(iterator->wal_tree, &snap_item->avl_seq,
535 : 606 : _fdb_seqnum_cmp);
536 : : }
537 : : }
538 : 606 : he = list_next(he);
539 : : }
540 : 24 : spin_unlock(&wal_file->wal->lock);
541 : : } else {
542 : 19 : iterator->wal_tree = handle->shandle->seq_tree;
543 : : }
544 : :
545 [ + - ]: 43 : if (iterator->wal_tree) {
546 : 43 : iterator->tree_cursor = avl_first(iterator->wal_tree);
547 : : } else {
548 : 0 : iterator->tree_cursor = NULL;
549 : : }
550 : :
551 : : // to know reverse iteration endpoint store the start cursor
552 : 43 : iterator->tree_cursor_start = iterator->tree_cursor;
553 : 43 : iterator->tree_cursor_prev = iterator->tree_cursor;
554 : 43 : iterator->direction = FDB_ITR_DIR_NONE;
555 : 43 : iterator->status = FDB_ITR_IDX;
556 : 43 : iterator->_dhandle = NULL; // populated at the first iterator movement
557 : :
558 : 43 : *ptr_iterator = iterator;
559 : :
560 : 43 : fdb_iterator_next(iterator); // position cursor at first key
561 : :
562 : 44 : return FDB_RESULT_SUCCESS;
563 : : }
564 : :
565 : 26768 : static fdb_status _fdb_iterator_prev(fdb_iterator *iterator)
566 : : {
567 : : int cmp;
568 : : void *key;
569 : : size_t keylen;
570 : : uint64_t offset;
571 : 26768 : hbtrie_result hr = HBTRIE_RESULT_SUCCESS;
572 : : struct docio_handle *dhandle;
573 : 26768 : struct snap_wal_entry *snap_item = NULL;
574 : :
575 [ + + ]: 26768 : if (iterator->direction == FDB_ITR_FORWARD) {
576 : 1547 : iterator->_offset = BLK_NOT_FOUND; // need to re-examine Trie/trees
577 [ + + ][ + + ]: 1547 : if (!iterator->tree_cursor && iterator->tree_cursor_prev) {
578 : : // this only happens right after seek operation
579 : : // (when seek is executed using a key larger than
580 : : // the largest key in WAL)
581 [ + + ]: 144 : if (iterator->status == FDB_ITR_WAL) {
582 : 48 : iterator->tree_cursor = avl_prev(iterator->tree_cursor_prev);
583 : 48 : iterator->tree_cursor_prev = iterator->tree_cursor;
584 : : } else {
585 : 24 : iterator->tree_cursor = iterator->tree_cursor_prev;
586 : : }
587 [ + + ]: 1475 : } else if (iterator->tree_cursor) { // on turning direction
588 [ + + ]: 1357 : if (iterator->status == FDB_ITR_WAL) { // skip 2 items
589 : 905 : iterator->tree_cursor = avl_prev(iterator->tree_cursor_prev);
590 : : } else { // skip 1 item if the last doc was returned from the main index
591 : 452 : iterator->tree_cursor = avl_prev(iterator->tree_cursor);
592 : : }
593 : 1547 : iterator->tree_cursor_prev = iterator->tree_cursor;
594 : : }
595 : : }
596 : 26768 : iterator->tree_cursor = iterator->tree_cursor_prev;
597 : : start:
598 : 26888 : key = iterator->_key;
599 : 26888 : dhandle = iterator->handle.dhandle;
600 : :
601 : : // retrieve from hb-trie
602 [ + + ]: 26888 : if (iterator->_offset == BLK_NOT_FOUND) {
603 : : // no key waiting for being returned
604 : : // get next key from hb-trie (or idtree)
605 : : struct docio_object _doc;
606 : : uint64_t _offset;
607 : 21581 : do {
608 : : hr = hbtrie_prev(iterator->hbtrie_iterator, key,
609 : 21581 : &iterator->_keylen, (void*)&iterator->_offset);
610 : 21581 : btreeblk_end(iterator->handle.bhandle);
611 : 21581 : iterator->_offset = _endian_decode(iterator->_offset);
612 [ + + ][ + + ]: 21581 : if (!(iterator->opt & FDB_ITR_NO_DELETES) ||
613 : : hr != HBTRIE_RESULT_SUCCESS) {
614 : 11799 : break;
615 : : }
616 : : // deletion check
617 : 9782 : memset(&_doc, 0x0, sizeof(struct docio_object));
618 : 9782 : _offset = docio_read_doc_key_meta(dhandle, iterator->_offset, &_doc);
619 [ - + ]: 9782 : if (_offset == iterator->_offset) { // read fail
620 : 0 : continue; // get prev doc
621 : : }
622 [ + + ]: 9782 : if (_doc.length.flag & DOCIO_DELETED) { // deleted doc
623 : 184 : free(_doc.key);
624 : 184 : free(_doc.meta);
625 : 184 : continue; // get prev doc
626 : : }
627 : 9598 : free(_doc.key);
628 : 9598 : free(_doc.meta);
629 : 9598 : break;
630 : : } while (1);
631 : : }
632 : 26888 : keylen = iterator->_keylen;
633 : 26888 : offset = iterator->_offset;
634 : 26888 : iterator->status = FDB_ITR_IDX;
635 : :
636 [ + + ][ + + ]: 26888 : if (hr == HBTRIE_RESULT_FAIL && !iterator->tree_cursor) {
637 : 128 : return FDB_RESULT_ITERATOR_FAIL;
638 : : }
639 : :
640 [ + + ]: 26880 : while (iterator->tree_cursor) {
641 : : // get the current item of avl-tree
642 : : snap_item = _get_entry(iterator->tree_cursor, struct snap_wal_entry,
643 : 21227 : avl);
644 [ + + ]: 21227 : if (hr != HBTRIE_RESULT_FAIL) {
645 : : cmp = _fdb_key_cmp(iterator, snap_item->key, snap_item->keylen,
646 : 19488 : key, keylen);
647 : : } else {
648 : : // no more docs in hb-trie
649 : 1739 : cmp = 1;
650 : : }
651 : :
652 [ + + ]: 21227 : if (cmp >= 0) {
653 : : // key[WAL] >= key[hb-trie] .. take key[WAL] first
654 : 14513 : iterator->tree_cursor = avl_prev(iterator->tree_cursor);
655 : 14513 : iterator->tree_cursor_prev = iterator->tree_cursor;
656 : : uint8_t drop_logical_deletes =
657 : : (snap_item->action == WAL_ACT_LOGICAL_REMOVE) &&
658 [ + + ][ + - ]: 14513 : (iterator->opt & FDB_ITR_NO_DELETES);
659 [ + + ]: 14513 : if (cmp > 0) {
660 [ + - ][ + + ]: 7309 : if (snap_item->action == WAL_ACT_REMOVE || drop_logical_deletes) {
661 [ + + ][ - + ]: 120 : if (hr == HBTRIE_RESULT_FAIL &&
662 : : iterator->tree_cursor == iterator->tree_cursor_start) {
663 : 0 : return FDB_RESULT_ITERATOR_FAIL;
664 : : }
665 : : // this key is removed .. get prev key[WAL]
666 : 120 : continue;
667 : : }
668 : : }else{ // same key found in WAL
669 : 7204 : iterator->_offset = BLK_NOT_FOUND; // drop key from trie
670 [ - + ][ + + ]: 7204 : if (snap_item->action == WAL_ACT_REMOVE || drop_logical_deletes) {
671 : : // the key is removed .. start over again
672 : : goto start;
673 : : }
674 : : }
675 : :
676 : 14273 : key = snap_item->key;
677 : 14273 : keylen = snap_item->keylen;
678 : : // key[hb-trie] is stashed in iterator->_key for future call
679 : 14273 : offset = snap_item->offset;
680 : 14273 : iterator->status = FDB_ITR_WAL;
681 [ - + ]: 14273 : if (snap_item->flag & SNAP_ITEM_IN_NEW_FILE) {
682 : 0 : dhandle = iterator->handle.new_dhandle;
683 : : }
684 : : }
685 : 20987 : break;
686 : : }
687 : :
688 [ + + ]: 26640 : if (offset == iterator->_offset) {
689 : : // take key[hb-trie] & and fetch the prev key[hb-trie] at next turn
690 : 12367 : iterator->_offset = BLK_NOT_FOUND;
691 : : }
692 : :
693 [ + - ]: 26640 : if (iterator->start_key) {
694 : : cmp = _fdb_key_cmp(iterator, iterator->start_key,
695 : 26640 : iterator->start_keylen, key, keylen);
696 : :
697 [ + + ]: 26640 : if (cmp > 0) {
698 : : // current key (KEY) is lexicographically less than
699 : : // START key terminate the iteration
700 : 1572 : return FDB_RESULT_ITERATOR_FAIL;
701 : : }
702 : : }
703 : :
704 : 25068 : iterator->_dhandle = dhandle; // store for fdb_iterator_get()
705 : 25068 : iterator->_get_offset = offset; // store for fdb_iterator_get()
706 : :
707 : 26768 : return FDB_RESULT_SUCCESS;
708 : : }
709 : :
710 : 30981 : static fdb_status _fdb_iterator_next(fdb_iterator *iterator)
711 : : {
712 : : int cmp;
713 : : void *key;
714 : : size_t keylen;
715 : : uint64_t offset;
716 : 30981 : hbtrie_result hr = HBTRIE_RESULT_SUCCESS;
717 : : struct docio_handle *dhandle;
718 : 30981 : struct snap_wal_entry *snap_item = NULL;
719 : :
720 [ + + ]: 30981 : if (iterator->direction == FDB_ITR_REVERSE) {
721 : 1 : iterator->_offset = BLK_NOT_FOUND; // need to re-examine Trie/trees
722 [ + - ]: 1 : if (iterator->tree_cursor) {
723 : 1 : iterator->tree_cursor = avl_next(iterator->tree_cursor);
724 [ + - ][ + - ]: 1 : if (iterator->tree_cursor &&
725 : : iterator->status == FDB_ITR_WAL) {
726 : : // if the last document was returned from WAL,
727 : : // shift again, past curkey into next
728 : 1 : iterator->tree_cursor = avl_next(iterator->tree_cursor);
729 : : }
730 : : }
731 : : }
732 : :
733 [ + + ][ + + ]: 30981 : if (!iterator->tree_cursor && iterator->direction != FDB_ITR_FORWARD) {
734 : : // In case reverse iteration went past the start, reset the
735 : : // cursor to the start point
736 : 140 : iterator->tree_cursor = iterator->tree_cursor_start;
737 : : }
738 : :
739 : : start:
740 : 31109 : key = iterator->_key;
741 : 31109 : dhandle = iterator->handle.dhandle;
742 : :
743 : : // retrieve from hb-trie
744 [ + + ]: 31109 : if (iterator->_offset == BLK_NOT_FOUND) {
745 : : // no key waiting for being returned
746 : : // get next key from hb-trie (or idtree)
747 : : struct docio_object _doc;
748 : : uint64_t _offset;
749 : 23862 : do {
750 : : hr = hbtrie_next(iterator->hbtrie_iterator, key,
751 : 23862 : &iterator->_keylen, (void*)&iterator->_offset);
752 : 23862 : btreeblk_end(iterator->handle.bhandle);
753 : 23862 : iterator->_offset = _endian_decode(iterator->_offset);
754 [ + + ][ + + ]: 23862 : if (!(iterator->opt & FDB_ITR_NO_DELETES) ||
755 : : hr != HBTRIE_RESULT_SUCCESS) {
756 : 14209 : break;
757 : : }
758 : : // deletion check
759 : 9653 : memset(&_doc, 0x0, sizeof(struct docio_object));
760 : 9653 : _offset = docio_read_doc_key_meta(dhandle, iterator->_offset, &_doc);
761 [ - + ]: 9653 : if (_offset == iterator->_offset) { // read fail
762 : 0 : continue; // get next doc
763 : : }
764 [ + + ]: 9653 : if (_doc.length.flag & DOCIO_DELETED) { // deleted doc
765 : 186 : free(_doc.key);
766 : 186 : free(_doc.meta);
767 : 186 : continue; // get next doc
768 : : }
769 : 9467 : free(_doc.key);
770 : 9467 : free(_doc.meta);
771 : 9467 : break;
772 : : } while (1);
773 : : }
774 : :
775 : 31109 : keylen = iterator->_keylen;
776 : 31109 : offset = iterator->_offset;
777 : 31109 : iterator->status = FDB_ITR_IDX;
778 : :
779 [ + + ][ + + ]: 31109 : if (hr == HBTRIE_RESULT_FAIL && iterator->tree_cursor == NULL) {
780 : 22 : return FDB_RESULT_ITERATOR_FAIL;
781 : : }
782 : :
783 [ + + ]: 31216 : while (iterator->tree_cursor) {
784 : : // get the current item of avl-tree
785 : : snap_item = _get_entry(iterator->tree_cursor, struct snap_wal_entry,
786 : 22497 : avl);
787 [ + + ]: 22497 : if (hr != HBTRIE_RESULT_FAIL) {
788 : : cmp = _fdb_key_cmp(iterator, snap_item->key, snap_item->keylen,
789 : 21440 : key, keylen);
790 : : } else {
791 : : // no more docs in hb-trie
792 : 1057 : cmp = -1;
793 : : }
794 : :
795 [ + + ]: 22497 : if (cmp <= 0) {
796 : : // key[WAL] <= key[hb-trie] .. take key[WAL] first
797 : : // save the current pointer for reverse iteration
798 : 15609 : iterator->tree_cursor_prev = iterator->tree_cursor;
799 : 15609 : iterator->tree_cursor = avl_next(iterator->tree_cursor);
800 : : uint8_t drop_logical_deletes =
801 : : (snap_item->action == WAL_ACT_LOGICAL_REMOVE) &&
802 [ + + ][ + + ]: 15609 : (iterator->opt & FDB_ITR_NO_DELETES);
803 [ + + ]: 15609 : if (cmp < 0) {
804 [ + - ][ + + ]: 8514 : if (snap_item->action == WAL_ACT_REMOVE || drop_logical_deletes) {
805 [ + + ][ - + ]: 129 : if (hr == HBTRIE_RESULT_FAIL &&
806 : : iterator->tree_cursor == NULL) {
807 : 0 : return FDB_RESULT_ITERATOR_FAIL;
808 : : }
809 : : // this key is removed .. get next key[WAL]
810 : 129 : continue;
811 : : }
812 : : }else{ // Same key from trie also found from WAL
813 : 7095 : iterator->_offset = BLK_NOT_FOUND; // drop key from trie
814 [ - + ][ + + ]: 7095 : if (snap_item->action == WAL_ACT_REMOVE || drop_logical_deletes) {
815 : : // the key is removed .. start over again
816 : : goto start;
817 : : }
818 : : }
819 : 15352 : key = snap_item->key;
820 : 15352 : keylen = snap_item->keylen;
821 : : // key[hb-trie] is stashed in iterator->key for next call
822 : 15352 : offset = snap_item->offset;
823 : 15352 : iterator->status = FDB_ITR_WAL;
824 [ - + ]: 15352 : if (snap_item->flag & SNAP_ITEM_IN_NEW_FILE) {
825 : 0 : dhandle = iterator->handle.new_dhandle;
826 : : }
827 : : }
828 : 22240 : break;
829 : : }
830 : :
831 [ + + ]: 30959 : if (offset == iterator->_offset) {
832 : : // take key[hb-trie] & and fetch the next key[hb-trie] at next turn
833 : 15607 : iterator->_offset = BLK_NOT_FOUND;
834 : : }
835 : :
836 [ + - ]: 30959 : if (iterator->end_key) {
837 : : cmp = _fdb_key_cmp(iterator, iterator->end_key, iterator->end_keylen,
838 : 30959 : key, keylen);
839 : :
840 [ + + ]: 30959 : if (cmp < 0) {
841 : : // current key (KEY) is lexicographically greater than END_KEY
842 : : // terminate the iteration
843 : 1710 : return FDB_RESULT_ITERATOR_FAIL;
844 : : }
845 : : }
846 : :
847 : 29249 : iterator->_dhandle = dhandle; // store for fdb_iterator_get()
848 : 29249 : iterator->_get_offset = offset; // store for fdb_iterator_get()
849 : :
850 : 30981 : return FDB_RESULT_SUCCESS;
851 : : }
852 : :
853 : 3409 : fdb_status fdb_iterator_seek(fdb_iterator *iterator,
854 : : const void *seek_key,
855 : : const size_t seek_keylen,
856 : : const fdb_iterator_seek_opt_t seek_preference)
857 : : {
858 : : int cmp, cmp2; // intermediate results of comparison
859 : 3409 : int next_op = 0; // 0: none, -1: prev(), 1: next();
860 : : uint8_t *seek_key_kv;
861 : : uint64_t _offset;
862 : : size_t seek_keylen_kv;
863 : 3409 : bool skip_wal = false, fetch_next = true, fetch_wal = true;
864 : : fdb_kvs_id_t _kv_id;
865 : 3409 : hbtrie_result hr = HBTRIE_RESULT_SUCCESS;
866 : 3409 : struct snap_wal_entry *snap_item = NULL, query;
867 : : struct docio_object _doc;
868 : 3409 : fdb_iterator_seek_opt_t seek_pref = seek_preference;
869 : :
870 : 3409 : iterator->_dhandle = NULL; // setup for get() to return FAIL
871 : :
872 [ + - ][ + - ]: 3409 : if (!iterator || !seek_key || !iterator->_key ||
[ + - ][ + - ]
[ - + ]
873 : : seek_keylen > FDB_MAX_KEYLEN ||
874 : : seek_keylen > iterator->handle.config.blocksize - 256) {
875 : 0 : return FDB_RESULT_INVALID_ARGS;
876 : : }
877 : :
878 [ + - ]: 3409 : if (iterator->handle.kvs) {
879 : 3409 : seek_keylen_kv = seek_keylen + sizeof(fdb_kvs_id_t);
880 : 3409 : seek_key_kv = alca(uint8_t, seek_keylen_kv);
881 : 3409 : _kv_id = _endian_encode(iterator->handle.kvs->id);
882 : 3409 : memcpy(seek_key_kv, &_kv_id, sizeof(fdb_kvs_id_t));
883 : 3409 : memcpy(seek_key_kv + sizeof(fdb_kvs_id_t), seek_key, seek_keylen);
884 : : } else {
885 : 0 : seek_keylen_kv = seek_keylen;
886 : 0 : seek_key_kv = (uint8_t*)seek_key;
887 : : }
888 : :
889 : : // disable seeking beyond the end key...
890 [ + - ]: 3409 : if (iterator->end_key) {
891 : : cmp = _fdb_key_cmp(iterator, (void *)iterator->end_key,
892 : : iterator->end_keylen,
893 : 3409 : (void *)seek_key_kv, seek_keylen_kv);
894 [ + + ][ + + ]: 3409 : if (cmp == 0 && iterator->opt & FDB_ITR_SKIP_MAX_KEY) {
895 : : // seek the end key at this time,
896 : : // and call prev() next.
897 : 14 : next_op = -1;
898 : : }
899 [ - + ]: 3409 : if (cmp < 0) {
900 : 0 : return FDB_RESULT_ITERATOR_FAIL;
901 : : }
902 : : }
903 : :
904 : : // disable seeking beyond the start key...
905 [ + - ]: 3409 : if (iterator->start_key) {
906 : : cmp = _fdb_key_cmp(iterator,
907 : : (void *)iterator->start_key,
908 : : iterator->start_keylen,
909 : 3409 : (void *)seek_key_kv, seek_keylen_kv);
910 [ + + ][ + + ]: 3409 : if (cmp == 0 && iterator->opt & FDB_ITR_SKIP_MIN_KEY) {
911 : : // seek the start key at this time,
912 : : // and call next() next.
913 : 14 : next_op = 1;
914 : : }
915 [ - + ]: 3409 : if (cmp > 0) {
916 : 0 : return FDB_RESULT_ITERATOR_FAIL;
917 : : }
918 : : }
919 : :
920 : 3409 : iterator->direction = FDB_ITR_FORWARD;
921 : :
922 : : // reset HB+trie's iterator
923 : 3409 : hbtrie_iterator_free(iterator->hbtrie_iterator);
924 : : hbtrie_iterator_init(iterator->handle.trie, iterator->hbtrie_iterator,
925 : 3409 : seek_key_kv, seek_keylen_kv);
926 : :
927 : : fetch_hbtrie:
928 [ + + ]: 3425 : if (seek_pref == FDB_ITR_SEEK_HIGHER) {
929 : : // fetch next key
930 : : hr = hbtrie_next(iterator->hbtrie_iterator, iterator->_key,
931 : 1717 : &iterator->_keylen, (void*)&iterator->_offset);
932 : 1717 : btreeblk_end(iterator->handle.bhandle);
933 : :
934 [ + + ]: 1717 : if (hr == HBTRIE_RESULT_SUCCESS) {
935 : : cmp = _fdb_key_cmp(iterator,
936 : : iterator->_key, iterator->_keylen,
937 : 1708 : seek_key_kv, seek_keylen_kv);
938 [ - + ]: 1708 : if (cmp < 0) {
939 : : // key[HB+trie] < seek_key .. move forward
940 : : hr = hbtrie_next(iterator->hbtrie_iterator, iterator->_key,
941 : 0 : &iterator->_keylen, (void*)&iterator->_offset);
942 : 0 : btreeblk_end(iterator->handle.bhandle);
943 : : }
944 : 1708 : iterator->_offset = _endian_decode(iterator->_offset);
945 : :
946 [ + + ][ + - ]: 2565 : while (iterator->opt & FDB_ITR_NO_DELETES &&
[ + + ][ + + ]
947 : : hr == HBTRIE_RESULT_SUCCESS &&
948 : : fetch_next) {
949 : 857 : fetch_next = false;
950 : 857 : memset(&_doc, 0x0, sizeof(struct docio_object));
951 : : _offset = docio_read_doc_key_meta(iterator->handle.dhandle,
952 : 857 : iterator->_offset, &_doc);
953 [ - + ]: 857 : if (_offset == iterator->_offset) { // read fail
954 : 0 : fetch_next = true; // get next
955 [ + + ]: 857 : } else if (_doc.length.flag & DOCIO_DELETED) { // deleted doc
956 : 16 : free(_doc.key);
957 : 16 : free(_doc.meta);
958 : 16 : fetch_next = true; // get next
959 : : } else {
960 : 841 : free(_doc.key);
961 : 841 : free(_doc.meta);
962 : : }
963 [ + + ]: 857 : if (fetch_next) {
964 : : hr = hbtrie_next(iterator->hbtrie_iterator, iterator->_key,
965 : : &iterator->_keylen,
966 : 16 : (void*)&iterator->_offset);
967 : 16 : btreeblk_end(iterator->handle.bhandle);
968 : 16 : iterator->_offset = _endian_decode(iterator->_offset);
969 : : }
970 : : }
971 : : }
972 : : } else {
973 : : // fetch prev key
974 : : hr = hbtrie_prev(iterator->hbtrie_iterator, iterator->_key,
975 : 1708 : &iterator->_keylen, (void*)&iterator->_offset);
976 : 1708 : btreeblk_end(iterator->handle.bhandle);
977 [ + + ]: 1708 : if (hr == HBTRIE_RESULT_SUCCESS) {
978 : : cmp = _fdb_key_cmp(iterator,
979 : : iterator->_key, iterator->_keylen,
980 : 1707 : seek_key_kv, seek_keylen_kv);
981 [ - + ]: 1707 : if (cmp > 0) {
982 : : // key[HB+trie] > seek_key .. move backward
983 : : hr = hbtrie_prev(iterator->hbtrie_iterator, iterator->_key,
984 : 0 : &iterator->_keylen, (void*)&iterator->_offset);
985 : 0 : btreeblk_end(iterator->handle.bhandle);
986 : : }
987 : 1707 : iterator->_offset = _endian_decode(iterator->_offset);
988 : :
989 [ + + ][ + - ]: 2564 : while (iterator->opt & FDB_ITR_NO_DELETES &&
[ + + ][ + + ]
990 : : hr == HBTRIE_RESULT_SUCCESS &&
991 : : fetch_next) {
992 : 857 : fetch_next = false;
993 : 857 : memset(&_doc, 0x0, sizeof(struct docio_object));
994 : : _offset = docio_read_doc_key_meta(iterator->handle.dhandle,
995 : 857 : iterator->_offset, &_doc);
996 [ - + ]: 857 : if (_offset == iterator->_offset) { // read fail
997 : 0 : fetch_next = true; // get prev
998 [ + + ]: 857 : } else if (_doc.length.flag & DOCIO_DELETED) { // deleted doc
999 : 16 : free(_doc.key);
1000 : 16 : free(_doc.meta);
1001 : 16 : fetch_next = true; // get prev
1002 : : } else {
1003 : 841 : free(_doc.key);
1004 : 841 : free(_doc.meta);
1005 : : }
1006 [ + + ]: 857 : if (fetch_next) {
1007 : : hr = hbtrie_prev(iterator->hbtrie_iterator, iterator->_key,
1008 : : &iterator->_keylen,
1009 : 16 : (void*)&iterator->_offset);
1010 : 16 : btreeblk_end(iterator->handle.bhandle);
1011 : 16 : iterator->_offset = _endian_decode(iterator->_offset);
1012 : : }
1013 : : }
1014 : : }
1015 : : }
1016 : :
1017 [ + + ][ + - ]: 3425 : if (hr == HBTRIE_RESULT_SUCCESS && iterator->handle.kvs) {
1018 : : // seek is done byeond the KV ID
1019 [ + + ]: 3415 : if (memcmp(&_kv_id, iterator->_key, sizeof(fdb_kvs_id_t))) {
1020 : 524 : hr = HBTRIE_RESULT_FAIL;
1021 : : }
1022 : : }
1023 : :
1024 [ + + ]: 3425 : if (hr == HBTRIE_RESULT_SUCCESS) {
1025 : 2891 : iterator->_get_offset = iterator->_offset;
1026 : 2891 : iterator->_dhandle = iterator->handle.dhandle;
1027 : : } else {
1028 : : // larger than the largest key or smaller than the smallest key
1029 : 534 : iterator->_get_offset = BLK_NOT_FOUND;
1030 : 534 : iterator->_dhandle = NULL;
1031 : : }
1032 : :
1033 : : // HB+trie's iterator should fetch another entry next time
1034 : 3425 : iterator->_offset = BLK_NOT_FOUND;
1035 : 3425 : iterator->status = FDB_ITR_IDX;
1036 : :
1037 : : // retrieve avl-tree
1038 : 3425 : query.key = seek_key_kv;
1039 : 3425 : query.keylen = seek_keylen_kv;
1040 : :
1041 [ + + ]: 3425 : if (seek_pref == FDB_ITR_SEEK_HIGHER) {
1042 [ + + ]: 1717 : if (fetch_wal) {
1043 : : iterator->tree_cursor = avl_search_greater(iterator->wal_tree,
1044 : : &query.avl,
1045 : 1709 : _fdb_wal_cmp);
1046 : : }
1047 [ + + ][ + + ]: 1717 : if (iterator->opt & FDB_ITR_NO_DELETES &&
1048 : : iterator->tree_cursor) {
1049 : : // skip deleted WAL entry
1050 : 8 : do {
1051 : : snap_item = _get_entry(iterator->tree_cursor,
1052 : 718 : struct snap_wal_entry, avl);
1053 [ + + ]: 718 : if (snap_item->action == WAL_ACT_LOGICAL_REMOVE) {
1054 [ + + ]: 24 : if (iterator->_dhandle) {
1055 : : cmp = _fdb_key_cmp(iterator,
1056 : : snap_item->key, snap_item->keylen,
1057 : 20 : iterator->_key, iterator->_keylen);
1058 [ + + ]: 20 : if (cmp == 0) {
1059 : : // same doc exists in HB+trie
1060 : : // move tree cursor
1061 : : iterator->tree_cursor = avl_next(iterator->
1062 : 8 : tree_cursor);
1063 : : // do not move tree cursor next time
1064 : 8 : fetch_wal = false;
1065 : : // fetch next key[HB+trie]
1066 : 8 : goto fetch_hbtrie;
1067 [ + + ]: 12 : } else if (cmp > 0) {
1068 : 8 : break;
1069 : : }
1070 : : }
1071 : 8 : iterator->tree_cursor = avl_next(iterator->tree_cursor);
1072 : 8 : continue;
1073 : : }
1074 : 702 : break;
1075 : : } while(1);
1076 : : }
1077 [ + + ]: 1709 : if (!iterator->tree_cursor) {
1078 : : // seek_key is larger than the largest key
1079 : : // set prev key to the largest key.
1080 : : // if prev operation is called next, tree_cursor will be set to
1081 : : // tree_cursor_prev.
1082 : : iterator->tree_cursor_prev = avl_search_smaller(iterator->wal_tree,
1083 : : &query.avl,
1084 : 284 : _fdb_wal_cmp);
1085 : : } else {
1086 : 1425 : iterator->tree_cursor_prev = iterator->tree_cursor;
1087 : : }
1088 [ + - ]: 1708 : } else if (seek_pref == FDB_ITR_SEEK_LOWER) {
1089 [ + + ]: 1708 : if (fetch_wal) {
1090 : : iterator->tree_cursor = avl_search_smaller(iterator->wal_tree,
1091 : : &query.avl,
1092 : 1700 : _fdb_wal_cmp);
1093 : : }
1094 [ + + ][ + + ]: 1708 : if (iterator->opt & FDB_ITR_NO_DELETES &&
1095 : : iterator->tree_cursor) {
1096 : : // skip deleted WAL entry
1097 : 8 : do {
1098 : : snap_item = _get_entry(iterator->tree_cursor,
1099 : 730 : struct snap_wal_entry, avl);
1100 [ + + ]: 730 : if (snap_item->action == WAL_ACT_LOGICAL_REMOVE) {
1101 [ + + ]: 24 : if (iterator->_dhandle) {
1102 : : cmp = _fdb_key_cmp(iterator,
1103 : : snap_item->key, snap_item->keylen,
1104 : 20 : iterator->_key, iterator->_keylen);
1105 [ + + ]: 20 : if (cmp == 0) {
1106 : : // same doc exists in HB+trie
1107 : : // move tree cursor
1108 : : iterator->tree_cursor = avl_prev(iterator->
1109 : 8 : tree_cursor);
1110 : : // do not move tree cursor next time
1111 : 8 : fetch_wal = false;
1112 : : // fetch next key[HB+trie]
1113 : 8 : goto fetch_hbtrie;
1114 [ + + ]: 12 : } else if (cmp < 0) {
1115 : 8 : break;
1116 : : }
1117 : : }
1118 : 8 : iterator->tree_cursor = avl_prev(iterator->tree_cursor);
1119 : 8 : continue;
1120 : : }
1121 : 714 : break;
1122 : : } while(1);
1123 : : }
1124 : 1700 : iterator->tree_cursor_prev = iterator->tree_cursor;
1125 [ + + ]: 1700 : if (!iterator->tree_cursor) {
1126 : : // seek_key is smaller than the smallest key
1127 : : iterator->tree_cursor = avl_search_greater(iterator->wal_tree,
1128 : : &query.avl,
1129 : 261 : _fdb_wal_cmp);
1130 : : // need to set direction to NONE.
1131 : : // if next operation is called next, tree_cursor will be set to
1132 : : // cursor_start.
1133 : 261 : iterator->direction = FDB_ITR_DIR_NONE;
1134 : : // since the current key[WAL] is larger than seek_key,
1135 : : // skip key[WAL] this time
1136 : 261 : skip_wal = true;
1137 : : }
1138 : : }
1139 : :
1140 [ + + ][ + + ]: 3409 : if (iterator->tree_cursor && !skip_wal) {
1141 : 2864 : bool take_wal = false;
1142 : 2864 : bool discard_hbtrie = false;
1143 : :
1144 : : snap_item = _get_entry(iterator->tree_cursor, struct snap_wal_entry,
1145 : 2864 : avl);
1146 : :
1147 [ + + ]: 2864 : if (hr == HBTRIE_RESULT_SUCCESS) {
1148 : : cmp = _fdb_key_cmp(iterator,
1149 : : snap_item->key, snap_item->keylen,
1150 : 2359 : iterator->_key, iterator->_keylen);
1151 : :
1152 [ + + ]: 2359 : if (cmp == 0) {
1153 : : // same key exists in both HB+trie and WAL
1154 : 952 : take_wal = true;
1155 : 952 : discard_hbtrie = true;
1156 [ + + ]: 1407 : } else if (cmp < 0) { // key[WAL] < key[HB+trie]
1157 [ + + ]: 707 : if (seek_pref == FDB_ITR_SEEK_HIGHER) {
1158 : : // higher mode .. take smaller one (key[WAL]) first
1159 : 232 : take_wal = true;
1160 : 232 : discard_hbtrie = false;
1161 [ + - ]: 475 : } else if (seek_pref == FDB_ITR_SEEK_LOWER) {
1162 : : // lower mode .. discard smaller one (key[WAL])
1163 : 475 : iterator->tree_cursor = avl_next(iterator->tree_cursor);
1164 : 475 : take_wal = false;
1165 : 475 : discard_hbtrie = false;
1166 : : // In seek_to_max call with skip_max_key option,
1167 [ + + ]: 475 : if (next_op < 0) {
1168 : : // if key[HB+trie] is the largest key
1169 : : // smaller than max key,
1170 : : // do not call prev() next.
1171 [ + - ]: 10 : if (iterator->end_key) {
1172 : : cmp2 = _fdb_key_cmp(iterator,
1173 : : iterator->_key,
1174 : : iterator->_keylen,
1175 : : iterator->end_key,
1176 : 10 : iterator->end_keylen);
1177 : : } else {
1178 : 0 : cmp2 = -1;
1179 : : }
1180 [ + + ]: 10 : if (cmp2 < 0) {
1181 : 2 : next_op = 0;
1182 : : }
1183 : : }
1184 : : }
1185 : : } else { // key[HB+trie] < key[WAL]
1186 [ + + ]: 700 : if (seek_pref == FDB_ITR_SEEK_HIGHER) {
1187 : : // higher mode .. take smaller one (key[HB+trie]) first
1188 : 467 : take_wal = false;
1189 : 467 : discard_hbtrie = false;
1190 : : // In seek_to_min call with skip_min_key option,
1191 [ + + ]: 467 : if (next_op > 0) {
1192 : : // if key[HB+trie] is the smallest key
1193 : : // larger than min key,
1194 : : // do not call next() next.
1195 [ + - ]: 10 : if (iterator->start_key) {
1196 : : cmp2 = _fdb_key_cmp(iterator,
1197 : : iterator->start_key,
1198 : : iterator->start_keylen,
1199 : : iterator->_key,
1200 : 10 : iterator->_keylen);
1201 : : } else {
1202 : 0 : cmp2 = -1;
1203 : : }
1204 [ + + ]: 10 : if (cmp2 < 0) {
1205 : 2 : next_op = 0;
1206 : : }
1207 : : }
1208 [ + - ]: 233 : } else if (seek_pref == FDB_ITR_SEEK_LOWER) {
1209 : : // lower mode .. discard smaller one (key[HB+trie])
1210 : 233 : take_wal = true;
1211 : 233 : discard_hbtrie = true;
1212 : : // reset HB+trie's iterator to get the current
1213 : : // key[HB+trie] one more time
1214 : 233 : hbtrie_iterator_free(iterator->hbtrie_iterator);
1215 : : hbtrie_iterator_init(iterator->handle.trie,
1216 : : iterator->hbtrie_iterator,
1217 : 233 : seek_key_kv, seek_keylen_kv);
1218 : 233 : iterator->_offset = BLK_NOT_FOUND;
1219 : : }
1220 : : }
1221 : : } else {
1222 : : // HB+trie seek fail (key[HB+trie] doesn't exist)
1223 : 505 : take_wal = true;
1224 : 505 : discard_hbtrie = true;
1225 : : // Since WAL tree doesn't contain max/min key if
1226 : : // skip_min/max options are enabled, we don't need to
1227 : : // invoke next()/prev() call if no key is found in
1228 : : // HB+trie.
1229 : 505 : next_op = 0;
1230 : : }
1231 : :
1232 [ + + ]: 2864 : if (take_wal) { // take key[WAL]
1233 [ + + ]: 1922 : if (!discard_hbtrie) { // do not skip the current key[HB+trie]
1234 : : // key[HB+trie] will be returned next time
1235 : 232 : iterator->_offset = iterator->_get_offset;
1236 : : }
1237 : 1922 : iterator->_get_offset = snap_item->offset;
1238 [ - + ]: 1922 : if (snap_item->flag & SNAP_ITEM_IN_NEW_FILE) {
1239 : 0 : iterator->_dhandle = iterator->handle.new_dhandle;
1240 : : } else {
1241 : 1922 : iterator->_dhandle = iterator->handle.dhandle;
1242 : : }
1243 : : // move to next WAL entry
1244 : 1922 : iterator->tree_cursor = avl_next(iterator->tree_cursor);
1245 : 1922 : iterator->status = FDB_ITR_WAL;
1246 : : }
1247 : : }
1248 : :
1249 [ + + ]: 3409 : if (!iterator->_dhandle) {
1250 : 29 : return FDB_RESULT_ITERATOR_FAIL;
1251 : : }
1252 : :
1253 [ + + ]: 3380 : if (next_op < 0) {
1254 : 10 : return fdb_iterator_prev(iterator);
1255 [ + + ]: 3370 : } else if (next_op > 0) {
1256 : 10 : return fdb_iterator_next(iterator);
1257 : : } else {
1258 : 3409 : return FDB_RESULT_SUCCESS;
1259 : : }
1260 : : }
1261 : :
1262 : 32 : fdb_status fdb_iterator_seek_to_min(fdb_iterator *iterator) {
1263 : 32 : size_t size_id = sizeof(fdb_kvs_id_t);
1264 : :
1265 [ + - ][ - + ]: 32 : if (!iterator || !iterator->_key) {
1266 : 0 : return FDB_RESULT_INVALID_ARGS;
1267 : : }
1268 : :
1269 : : // Initialize direction iteration to FORWARD just in case this function was
1270 : : // called right after fdb_iterator_init() so the cursor gets positioned
1271 : : // correctly
1272 : 32 : iterator->direction = FDB_ITR_FORWARD;
1273 [ + + ]: 32 : if (iterator->start_keylen > size_id) {
1274 : : fdb_iterator_seek_opt_t dir = (iterator->opt & FDB_ITR_SKIP_MIN_KEY) ?
1275 [ + + ]: 16 : FDB_ITR_SEEK_HIGHER : FDB_ITR_SEEK_LOWER;
1276 : : fdb_status status = fdb_iterator_seek(iterator,
1277 : : (uint8_t *)iterator->start_key + size_id,
1278 : 16 : iterator->start_keylen - size_id, dir);
1279 [ - + ][ # # ]: 16 : if (status != FDB_RESULT_SUCCESS && dir == FDB_ITR_SEEK_LOWER) {
1280 : 0 : dir = FDB_ITR_SEEK_HIGHER;
1281 : : // It is possible that the min key specified during init does not
1282 : : // exist, so retry the seek with the HIGHER key
1283 : : return fdb_iterator_seek(iterator,
1284 : : (uint8_t *)iterator->start_key + size_id,
1285 : 0 : iterator->start_keylen - size_id, dir);
1286 : : }
1287 : 16 : return status;
1288 : : }
1289 : :
1290 : : // reset HB+trie iterator using start key
1291 : 16 : hbtrie_iterator_free(iterator->hbtrie_iterator);
1292 : : hbtrie_iterator_init(iterator->handle.trie, iterator->hbtrie_iterator,
1293 : 16 : iterator->start_key, iterator->start_keylen);
1294 : :
1295 : : // reset WAL tree cursor
1296 : : iterator->tree_cursor_prev = iterator->tree_cursor =
1297 : 16 : iterator->tree_cursor_start;
1298 : :
1299 : 32 : return fdb_iterator_next(iterator);
1300 : : }
1301 : :
1302 : 34 : fdb_status fdb_iterator_seek_to_max(fdb_iterator *iterator) {
1303 : : int cmp;
1304 : 34 : size_t size_id = sizeof(fdb_kvs_id_t);
1305 : :
1306 [ + - ][ - + ]: 34 : if (!iterator || !iterator->_key) {
1307 : 0 : return FDB_RESULT_INVALID_ARGS;
1308 : : }
1309 : :
1310 : : // Initialize direction iteration to FORWARD just in case this function was
1311 : : // called right after fdb_iterator_init() so the cursor gets positioned
1312 : : // correctly
1313 : 34 : iterator->direction = FDB_ITR_FORWARD;
1314 [ + + ]: 34 : if (iterator->end_keylen > size_id) {
1315 : : fdb_iterator_seek_opt_t dir = (iterator->opt & FDB_ITR_SKIP_MAX_KEY) ?
1316 [ + + ]: 17 : FDB_ITR_SEEK_LOWER : FDB_ITR_SEEK_HIGHER;
1317 : : fdb_status status = fdb_iterator_seek(iterator,
1318 : : (uint8_t *)iterator->end_key + size_id,
1319 : 17 : iterator->end_keylen - size_id, dir);
1320 : :
1321 [ + + ][ + - ]: 17 : if (status != FDB_RESULT_SUCCESS && dir == FDB_ITR_SEEK_HIGHER) {
1322 : 1 : dir = FDB_ITR_SEEK_LOWER;
1323 : : // It is possible that the max key specified during init does not
1324 : : // exist, so retry the seek with the LOWER key
1325 : : return fdb_iterator_seek(iterator,
1326 : : (uint8_t *)iterator->end_key + size_id,
1327 : 1 : iterator->end_keylen - size_id, dir);
1328 : : }
1329 : 16 : return status;
1330 : : }
1331 : 17 : iterator->direction = FDB_ITR_REVERSE; // only reverse iteration possible
1332 : :
1333 [ + - ][ + - ]: 17 : if (iterator->end_key && iterator->end_keylen == size_id) {
1334 : : // end_key exists but end_keylen == size_id
1335 : : // it means that user doesn't assign end_key but
1336 : : // end_key is automatically assigned due to multi KVS mode.
1337 : :
1338 : : // reset HB+trie's iterator using end_key
1339 : 17 : hbtrie_iterator_free(iterator->hbtrie_iterator);
1340 : : hbtrie_iterator_init(iterator->handle.trie, iterator->hbtrie_iterator,
1341 : 17 : iterator->end_key, iterator->end_keylen);
1342 : : // get first key
1343 : : hbtrie_prev(iterator->hbtrie_iterator, iterator->_key,
1344 : 17 : &iterator->_keylen, (void*)&iterator->_offset);
1345 : 17 : iterator->_offset = _endian_decode(iterator->_offset);
1346 : : cmp = _fdb_key_cmp(iterator,
1347 : : iterator->end_key, iterator->end_keylen,
1348 : 17 : iterator->_key, iterator->_keylen);
1349 [ - + ]: 17 : if (cmp < 0) {
1350 : : // returned key is larger than the end key .. skip
1351 : 0 : iterator->_offset = BLK_NOT_FOUND;
1352 : : }
1353 : : } else {
1354 : : // move HB+trie iterator's cursor to the last entry
1355 : 0 : hbtrie_last(iterator->hbtrie_iterator);
1356 : : }
1357 : :
1358 : : // also move WAL tree's cursor to the last entry
1359 : 17 : iterator->tree_cursor = avl_last(iterator->wal_tree);
1360 : 17 : iterator->tree_cursor_prev = iterator->tree_cursor;
1361 : :
1362 : 34 : return fdb_iterator_prev(iterator);
1363 : : }
1364 : :
1365 : 1231 : static fdb_status _fdb_iterator_seq_prev(fdb_iterator *iterator)
1366 : : {
1367 : : size_t size_id, size_seq, seq_kv_len;
1368 : : uint8_t *seq_kv;
1369 : 1231 : uint64_t offset = BLK_NOT_FOUND;
1370 : 1231 : btree_result br = BTREE_RESULT_FAIL;
1371 : : hbtrie_result hr;
1372 : : struct docio_object _doc;
1373 : : struct docio_object _hbdoc;
1374 : : struct docio_handle *dhandle;
1375 : 1231 : struct snap_wal_entry *snap_item = NULL;
1376 : : fdb_seqnum_t seqnum;
1377 : : fdb_kvs_id_t kv_id, _kv_id;
1378 : : struct avl_node *cursor;
1379 : :
1380 : 1231 : size_id = sizeof(fdb_kvs_id_t);
1381 : 1231 : size_seq = sizeof(fdb_seqnum_t);
1382 : 1231 : seq_kv = alca(uint8_t, size_id + size_seq);
1383 : :
1384 : : // in forward iteration, cursor points to the next key to be returned
1385 : : // therefore, in return iteration, make cursor point to prev key
1386 [ + + ]: 1231 : if (iterator->direction == FDB_ITR_FORWARD) {
1387 [ + - ]: 2 : if (iterator->status == FDB_ITR_IDX) {
1388 : 2 : iterator->_offset = BLK_NOT_FOUND; // need to re-examine Trie/trees
1389 : : }
1390 [ + - ]: 2 : if (iterator->tree_cursor) { // on turning direction
1391 [ - + ]: 2 : if (iterator->status == FDB_ITR_WAL) { // skip 2 items
1392 : 0 : iterator->tree_cursor = avl_prev(iterator->tree_cursor_prev);
1393 : : } else { // skip 1 item if the last doc was returned from the main index
1394 : 2 : iterator->tree_cursor = avl_prev(iterator->tree_cursor);
1395 : : }
1396 : 2 : iterator->tree_cursor_prev = iterator->tree_cursor;
1397 : : }
1398 : : }
1399 : 1231 : iterator->tree_cursor = iterator->tree_cursor_prev;
1400 : : start_seq:
1401 : 1531 : seqnum = iterator->_seqnum;
1402 : 1531 : dhandle = iterator->handle.dhandle;
1403 : :
1404 [ + + ][ + + ]: 1531 : if (iterator->_offset == BLK_NOT_FOUND || // was iterating over btree
1405 : 513 : !iterator->tree_cursor) { // WAL exhausted
1406 [ + - ]: 1426 : if (iterator->handle.kvs) { // multi KV instance mode
1407 : : hr = hbtrie_prev(iterator->seqtrie_iterator, seq_kv, &seq_kv_len,
1408 : 1426 : (void *)&offset);
1409 [ + + ]: 1426 : if (hr == HBTRIE_RESULT_SUCCESS) {
1410 : 1423 : br = BTREE_RESULT_SUCCESS;
1411 : 1423 : memcpy(&_kv_id, seq_kv, size_id);
1412 : 1423 : kv_id = _endian_decode(_kv_id);
1413 [ + + ]: 1423 : if (kv_id != iterator->handle.kvs->id) {
1414 : : // iterator is beyond the boundary
1415 : 3 : br = BTREE_RESULT_FAIL;
1416 : : }
1417 : 1423 : memcpy(&seqnum, seq_kv + size_id, size_seq);
1418 : : } else {
1419 : 3 : br = BTREE_RESULT_FAIL;
1420 : : }
1421 : : } else {
1422 : 0 : br = btree_prev(iterator->seqtree_iterator, &seqnum, (void *)&offset);
1423 : : }
1424 : 1426 : btreeblk_end(iterator->handle.bhandle);
1425 [ + + ]: 2846 : if (br == BTREE_RESULT_SUCCESS) {
1426 : 1420 : seqnum = _endian_decode(seqnum);
1427 : 1420 : iterator->_seqnum = seqnum;
1428 [ - + ]: 1420 : if (seqnum < iterator->start_seqnum) {
1429 : 0 : return FDB_RESULT_ITERATOR_FAIL;
1430 : : }
1431 : 1420 : offset = _endian_decode(offset);
1432 : 1420 : iterator->status = FDB_ITR_IDX;
1433 : : } else {
1434 : 6 : iterator->_offset = BLK_NOT_FOUND;
1435 : : // B-tree has no more items
1436 : 6 : return FDB_RESULT_ITERATOR_FAIL;
1437 : : }
1438 [ + - ]: 105 : } else while (iterator->tree_cursor) {
1439 : : // get the current item of avl tree
1440 : : snap_item = _get_entry(iterator->tree_cursor,
1441 : 105 : struct snap_wal_entry, avl_seq);
1442 : 105 : iterator->tree_cursor = avl_prev(iterator->tree_cursor);
1443 : 105 : iterator->tree_cursor_prev = iterator->tree_cursor;
1444 : : uint8_t drop_logical_deletes =
1445 : : (snap_item->action == WAL_ACT_LOGICAL_REMOVE) &&
1446 [ - + ][ # # ]: 105 : (iterator->opt & FDB_ITR_NO_DELETES);
1447 [ + - ][ - + ]: 105 : if (snap_item->action == WAL_ACT_REMOVE ||
1448 : : drop_logical_deletes) {
1449 [ # # ][ # # ]: 0 : if (br == BTREE_RESULT_FAIL && !iterator->tree_cursor) {
1450 : 0 : return FDB_RESULT_ITERATOR_FAIL;
1451 : : }
1452 : : // this key is removed .. get prev key[WAL]
1453 : 0 : continue;
1454 : : }
1455 : :
1456 : 105 : offset = snap_item->offset;
1457 : 105 : iterator->_offset = offset; // WAL is not exhausted, ignore B-Tree
1458 : 105 : iterator->_seqnum = snap_item->seqnum;
1459 : 105 : iterator->status = FDB_ITR_WAL;
1460 [ - + ]: 105 : if (snap_item->flag & SNAP_ITEM_IN_NEW_FILE) {
1461 : 0 : dhandle = iterator->handle.new_dhandle;
1462 : : }
1463 : 105 : break;
1464 : : }
1465 : :
1466 : : // To prevent returning duplicate items from sequence iterator, only return
1467 : : // those b-tree items that exist in HB-trie but not WAL
1468 : : // (WAL items should have already been returned in reverse iteration)
1469 [ + + ]: 1525 : if (br == BTREE_RESULT_SUCCESS) {
1470 : 1420 : _doc.key = NULL;
1471 : 1420 : _doc.length.keylen = 0;
1472 : 1420 : _doc.meta = NULL;
1473 : 1420 : _doc.body = NULL;
1474 : 1420 : uint64_t _offset = docio_read_doc_key_meta(dhandle, offset, &_doc);
1475 [ - + ]: 1420 : if (_offset == offset) {
1476 : 0 : return FDB_RESULT_KEY_NOT_FOUND;
1477 : : }
1478 [ - + ][ # # ]: 1420 : if (_doc.length.flag & DOCIO_DELETED &&
1479 : : (iterator->opt & FDB_ITR_NO_DELETES)) {
1480 : 0 : free(_doc.key);
1481 : 0 : free(_doc.meta);
1482 : 0 : return FDB_RESULT_KEY_NOT_FOUND;
1483 : : }
1484 : :
1485 [ + + ]: 16370 : for (cursor = iterator->tree_cursor_start;
1486 : : cursor;
1487 : : cursor = avl_next(cursor)) {
1488 : : // get the current item of avl tree
1489 : 15150 : snap_item = _get_entry(cursor, struct snap_wal_entry, avl_seq);
1490 : : // we MUST not use 'memcmp' for comparison of two keys
1491 : : // because it returns false positive when snap_item->key is a
1492 : : // sub-string of _doc.key
1493 : : // (e.g, "abc" and "abcd" -> memcmp("abc", "abcd", 3) == 0)
1494 [ + + ]: 15150 : if (!_fdb_keycmp(snap_item->key, snap_item->keylen,
1495 : 15150 : _doc.key, _doc.length.keylen)) {
1496 : 200 : free(_doc.key);
1497 : 200 : free(_doc.meta);
1498 : 200 : goto start_seq; // B-tree item exists in WAL, skip for now
1499 : : }
1500 : : }
1501 : :
1502 : : // Also look in HB-Trie to eliminate duplicates
1503 : : uint64_t hboffset;
1504 : : hr = hbtrie_find(iterator->handle.trie, _doc.key, _doc.length.keylen,
1505 : 1220 : (void *)&hboffset);
1506 : 1220 : btreeblk_end(iterator->handle.bhandle);
1507 : :
1508 [ - + ]: 1220 : if (hr == HBTRIE_RESULT_FAIL) {
1509 : 0 : free(_doc.key);
1510 : 0 : free(_doc.meta);
1511 : 0 : goto start_seq;
1512 : : } else { // If present in HB-trie ensure it's seqnum is in range
1513 : : uint64_t _offset;
1514 : 1220 : _hbdoc.key = _doc.key;
1515 : 1220 : _hbdoc.meta = NULL;
1516 : 1220 : hboffset = _endian_decode(hboffset);
1517 : 1220 : _offset = docio_read_doc_key_meta(iterator->handle.dhandle, hboffset, &_hbdoc);
1518 [ - + ]: 1220 : if (_offset == hboffset) {
1519 : 0 : free(_doc.key);
1520 : 0 : free(_doc.meta);
1521 : 0 : return FDB_RESULT_KEY_NOT_FOUND;
1522 : : }
1523 [ + + ][ + - ]: 1220 : if (_doc.seqnum < _hbdoc.seqnum &&
1524 : : _hbdoc.seqnum <= iterator->end_seqnum) {
1525 : 100 : free(_doc.key);
1526 : 100 : free(_doc.meta);
1527 : 100 : free(_hbdoc.meta);
1528 : 100 : goto start_seq;
1529 : : }
1530 : 1120 : free(_hbdoc.meta);
1531 : : }
1532 : 1120 : free(_doc.key);
1533 : 1120 : free(_doc.meta);
1534 : : }
1535 : :
1536 : 1225 : iterator->_dhandle = dhandle; // store for fdb_iterator_get()
1537 : 1225 : iterator->_get_offset = offset; // store for fdb_iterator_get()
1538 : :
1539 : 1231 : return FDB_RESULT_SUCCESS;
1540 : : }
1541 : :
1542 : 181869 : static fdb_status _fdb_iterator_seq_next(fdb_iterator *iterator)
1543 : : {
1544 : : size_t size_id, size_seq, seq_kv_len;
1545 : : uint8_t *seq_kv;
1546 : 181869 : uint64_t offset = BLK_NOT_FOUND;
1547 : 181869 : btree_result br = BTREE_RESULT_FAIL;
1548 : : hbtrie_result hr;
1549 : : struct docio_object _doc;
1550 : : struct docio_object _hbdoc;
1551 : : struct docio_handle *dhandle;
1552 : 181869 : struct snap_wal_entry *snap_item = NULL;
1553 : : fdb_seqnum_t seqnum;
1554 : : fdb_kvs_id_t kv_id, _kv_id;
1555 : : struct avl_node *cursor;
1556 : :
1557 : 181869 : size_id = sizeof(fdb_kvs_id_t);
1558 : 181869 : size_seq = sizeof(fdb_seqnum_t);
1559 : 181869 : seq_kv = alca(uint8_t, size_id + size_seq);
1560 : :
1561 [ + + ]: 181869 : if (iterator->direction == FDB_ITR_REVERSE) {
1562 [ + - ]: 1 : if (iterator->status == FDB_ITR_IDX) {
1563 : 1 : iterator->_offset = BLK_NOT_FOUND; // need to re-examine Trie/trees
1564 : : }
1565 [ - + ]: 1 : if (iterator->tree_cursor) {
1566 : 0 : iterator->tree_cursor = avl_next(iterator->tree_cursor);
1567 [ # # ][ # # ]: 0 : if (iterator->tree_cursor &&
1568 : : iterator->status == FDB_ITR_WAL) {
1569 : : // if the last document was returned from WAL,
1570 : : // shift again, past curkey into next
1571 : 0 : iterator->tree_cursor = avl_next(iterator->tree_cursor);
1572 : : }
1573 : : }
1574 : : }
1575 : :
1576 [ + + ][ + + ]: 181869 : if (!iterator->tree_cursor && iterator->direction != FDB_ITR_FORWARD) {
1577 : : // In case reverse iteration went past the start, reset the
1578 : : // cursor to the start point
1579 : 23 : iterator->tree_cursor = iterator->tree_cursor_start;
1580 : : }
1581 : :
1582 : : start_seq:
1583 : 182973 : seqnum = iterator->_seqnum;
1584 : 182973 : dhandle = iterator->handle.dhandle;
1585 : :
1586 : : // retrieve from sequence b-tree first
1587 [ + + ]: 182973 : if (iterator->_offset == BLK_NOT_FOUND) {
1588 [ + + ]: 182474 : if (iterator->handle.kvs) { // multi KV instance mode
1589 : : hr = hbtrie_next(iterator->seqtrie_iterator, seq_kv, &seq_kv_len,
1590 : 182468 : (void *)&offset);
1591 [ + + ]: 182438 : if (hr == HBTRIE_RESULT_SUCCESS) {
1592 : 182404 : br = BTREE_RESULT_SUCCESS;
1593 : 182404 : memcpy(&_kv_id, seq_kv, size_id);
1594 : 182404 : kv_id = _endian_decode(_kv_id);
1595 [ + + ]: 182404 : if (kv_id != iterator->handle.kvs->id) {
1596 : : // iterator is beyond the boundary
1597 : 7 : br = BTREE_RESULT_FAIL;
1598 : : }
1599 : 182404 : memcpy(&seqnum, seq_kv + size_id, size_seq);
1600 : : } else {
1601 : 34 : br = BTREE_RESULT_FAIL;
1602 : : }
1603 : : } else {
1604 : 6 : br = btree_next(iterator->seqtree_iterator, &seqnum, (void *)&offset);
1605 : : }
1606 : 182444 : btreeblk_end(iterator->handle.bhandle);
1607 [ + + ]: 182401 : if (br == BTREE_RESULT_SUCCESS) {
1608 : 182357 : seqnum = _endian_decode(seqnum);
1609 : 182357 : iterator->_seqnum = seqnum;
1610 [ - + ]: 182357 : if (seqnum > iterator->end_seqnum) {
1611 : 0 : return FDB_RESULT_ITERATOR_FAIL;
1612 : : }
1613 : 182357 : offset = _endian_decode(offset);
1614 : 182357 : iterator->_offset = BLK_NOT_FOUND; // continue with B-tree
1615 : 182357 : iterator->status = FDB_ITR_IDX;
1616 : : }
1617 : : }
1618 : :
1619 [ + + ]: 182900 : if (br == BTREE_RESULT_FAIL) {
1620 [ + + ]: 551 : if (iterator->tree_cursor == NULL) {
1621 : 37 : return FDB_RESULT_ITERATOR_FAIL;
1622 : : } else {
1623 [ + - ]: 1026 : while (iterator->tree_cursor) {
1624 : : // get the current item of avl tree
1625 : : snap_item = _get_entry(iterator->tree_cursor,
1626 : 517 : struct snap_wal_entry, avl_seq);
1627 : : // save the current point for reverse iteration
1628 : 517 : iterator->tree_cursor_prev = iterator->tree_cursor;
1629 : 517 : iterator->tree_cursor = avl_next(iterator->tree_cursor);
1630 : : uint8_t drop_logical_deletes =
1631 : : (snap_item->action == WAL_ACT_LOGICAL_REMOVE) &&
1632 [ + + ][ + + ]: 517 : (iterator->opt & FDB_ITR_NO_DELETES);
1633 [ + - ][ + + ]: 517 : if (snap_item->action == WAL_ACT_REMOVE ||
1634 : : drop_logical_deletes) {
1635 [ + - ][ + + ]: 4 : if (br == BTREE_RESULT_FAIL && !iterator->tree_cursor) {
1636 : 1 : return FDB_RESULT_ITERATOR_FAIL;
1637 : : }
1638 : : // this key is removed .. get next key[WAL]
1639 : 3 : continue;
1640 : : }
1641 [ - + ]: 513 : if (snap_item->seqnum < iterator->_seqnum) {
1642 : : // smaller than the current seqnum .. get next key[WAL]
1643 : 0 : continue;
1644 : : }
1645 [ + + ]: 513 : if (snap_item->seqnum > iterator->end_seqnum) {
1646 : : // out-of-range .. iterator terminates
1647 : 4 : return FDB_RESULT_ITERATOR_FAIL;
1648 : : }
1649 : :
1650 : 509 : offset = snap_item->offset;
1651 : 509 : iterator->_offset = offset; // stops b-tree lookups. favor wal
1652 : 509 : iterator->_seqnum = snap_item->seqnum;
1653 : 509 : iterator->status = FDB_ITR_WAL;
1654 [ - + ]: 509 : if (snap_item->flag & SNAP_ITEM_IN_NEW_FILE) {
1655 : 0 : dhandle = iterator->handle.new_dhandle;
1656 : : }
1657 : 509 : break;
1658 : : }
1659 : : }
1660 : : }
1661 : :
1662 : : // To prevent returning duplicate items from sequence iterator, only return
1663 : : // those b-tree items that exist in HB-trie but not WAL (visit WAL later)
1664 [ + + ]: 182858 : if (br == BTREE_RESULT_SUCCESS) {
1665 : 182345 : _doc.key = NULL;
1666 : 182345 : _doc.length.keylen = 0;
1667 : 182345 : _doc.meta = NULL;
1668 : 182345 : _doc.body = NULL;
1669 : 182345 : uint64_t _offset = docio_read_doc_key_meta(dhandle, offset, &_doc);
1670 [ - + ]: 182411 : if (_offset == offset) {
1671 : 0 : return FDB_RESULT_KEY_NOT_FOUND;
1672 : : }
1673 [ - + ][ # # ]: 182411 : if (_doc.length.flag & DOCIO_DELETED && (iterator->opt & FDB_ITR_NO_DELETES)) {
1674 : 0 : free(_doc.key);
1675 : 0 : free(_doc.meta);
1676 : 0 : return FDB_RESULT_KEY_NOT_FOUND;
1677 : : }
1678 : :
1679 [ + + ]: 239308 : for (cursor = iterator->tree_cursor; cursor;
1680 : : cursor = avl_next(cursor)) {
1681 : : // get the current item of avl tree
1682 : 57651 : snap_item = _get_entry(cursor, struct snap_wal_entry, avl_seq);
1683 : : // we MUST not use 'memcmp' for comparison of two keys
1684 : : // because it returns false positive when snap_item->key is a
1685 : : // sub-string of _doc.key
1686 : : // (e.g, "abc" and "abcd" -> memcmp("abc", "abcd", 3) == 0)
1687 [ + + ]: 57651 : if (!_fdb_keycmp(snap_item->key, snap_item->keylen,
1688 : 57651 : _doc.key, _doc.length.keylen)) {
1689 : 754 : free(_doc.key);
1690 : 754 : free(_doc.meta);
1691 : 754 : goto start_seq; // B-tree item exists in WAL, skip for now
1692 : : }
1693 : : } // WAL search complete
1694 : :
1695 : : // Also look in HB-Trie to eliminate duplicates
1696 : : uint64_t hboffset;
1697 : : hr = hbtrie_find(iterator->handle.trie, _doc.key, _doc.length.keylen,
1698 : 181657 : (void *)&hboffset);
1699 : 181703 : btreeblk_end(iterator->handle.bhandle);
1700 : :
1701 [ - + ]: 181652 : if (hr == HBTRIE_RESULT_FAIL) {
1702 : 0 : free(_doc.key);
1703 : 0 : free(_doc.meta);
1704 : 0 : goto start_seq;
1705 : : } else { // If present in HB-trie ensure it's seqnum is in range
1706 : : uint64_t _offset;
1707 : 181652 : _hbdoc.key = _doc.key;
1708 : 181652 : _hbdoc.meta = NULL;
1709 : 181652 : hboffset = _endian_decode(hboffset);
1710 : : _offset = docio_read_doc_key_meta(iterator->handle.dhandle,
1711 : 181652 : hboffset, &_hbdoc);
1712 [ - + ]: 181810 : if (_offset == hboffset) {
1713 : 0 : free(_doc.key);
1714 : 0 : free(_doc.meta);
1715 : 0 : return FDB_RESULT_KEY_NOT_FOUND;
1716 : : }
1717 [ + + ][ + - ]: 181810 : if (_doc.seqnum < _hbdoc.seqnum &&
1718 : : _hbdoc.seqnum <= iterator->end_seqnum) {
1719 : 350 : free(_doc.key);
1720 : 350 : free(_doc.meta);
1721 : 350 : free(_hbdoc.meta);
1722 : 350 : goto start_seq;
1723 : : }
1724 : 181460 : free(_hbdoc.meta);
1725 : : }
1726 : 181460 : free(_doc.key);
1727 : 181460 : free(_doc.meta);
1728 : : }
1729 : :
1730 : 181973 : iterator->_dhandle = dhandle; // store for fdb_iterator_get
1731 : 181973 : iterator->_get_offset = offset; // store for fdb_iterator_get
1732 : :
1733 : 182015 : return FDB_RESULT_SUCCESS;
1734 : : }
1735 : :
1736 : 27999 : fdb_status fdb_iterator_prev(fdb_iterator *iterator)
1737 : : {
1738 : 27999 : fdb_status result = FDB_RESULT_SUCCESS;
1739 [ + + ]: 27999 : if (iterator->hbtrie_iterator) {
1740 [ - + ]: 26768 : while ((result = _fdb_iterator_prev(iterator)) ==
1741 : : FDB_RESULT_KEY_NOT_FOUND);
1742 : : } else {
1743 [ - + ]: 1231 : while ((result = _fdb_iterator_seq_prev(iterator)) ==
1744 : : FDB_RESULT_KEY_NOT_FOUND);
1745 : : }
1746 [ + + ]: 27999 : if (result == FDB_RESULT_SUCCESS) {
1747 : 26293 : iterator->direction = FDB_ITR_REVERSE;
1748 : : } else {
1749 : 1706 : iterator->_dhandle = NULL; // fail fdb_iterator_get also
1750 [ + + ]: 1706 : if (iterator->direction != FDB_ITR_DIR_NONE) {
1751 : 1694 : iterator->direction = FDB_ITR_DIR_NONE;
1752 [ + - ][ + + ]: 1694 : if ((iterator->seqtree_iterator || iterator->seqtrie_iterator) &&
[ + - ]
1753 : : iterator->status == FDB_ITR_IDX) {
1754 : 6 : iterator->_offset = BLK_NOT_FOUND;
1755 : : }
1756 [ - + ]: 1694 : if (iterator->tree_cursor) {
1757 : 0 : iterator->tree_cursor = avl_next(iterator->tree_cursor);
1758 [ # # ][ # # ]: 0 : if (iterator->tree_cursor &&
1759 : : iterator->status == FDB_ITR_WAL) {
1760 : : // if the last document was returned from WAL,
1761 : : // shift again, past curkey into next
1762 : 0 : iterator->tree_cursor = avl_next(iterator->tree_cursor);
1763 : : }
1764 : : }
1765 : : }
1766 : : }
1767 : 27999 : return result;
1768 : : }
1769 : :
1770 : 212901 : fdb_status fdb_iterator_next(fdb_iterator *iterator)
1771 : : {
1772 : 212901 : fdb_status result = FDB_RESULT_SUCCESS;
1773 [ + + ]: 212901 : if (iterator->hbtrie_iterator) {
1774 [ + + ]: 31005 : while ((result = _fdb_iterator_next(iterator)) ==
1775 : : FDB_RESULT_KEY_NOT_FOUND);
1776 : : } else {
1777 [ + # ]: 181918 : while ((result = _fdb_iterator_seq_next(iterator)) ==
1778 : : FDB_RESULT_KEY_NOT_FOUND);
1779 : : }
1780 [ + + ]: 212953 : if (result == FDB_RESULT_SUCCESS) {
1781 : 211179 : iterator->direction = FDB_ITR_FORWARD;
1782 : : } else {
1783 : 1774 : iterator->_dhandle = NULL; // fail fdb_iterator_get also
1784 [ + + ]: 1774 : if (iterator->direction != FDB_ITR_DIR_NONE) {
1785 : 1766 : iterator->direction = FDB_ITR_DIR_NONE;
1786 [ + + ][ + + ]: 1766 : if ((iterator->seqtree_iterator || iterator->seqtrie_iterator) &&
[ + + ]
1787 : : iterator->status == FDB_ITR_IDX) {
1788 : 22 : iterator->_offset = BLK_NOT_FOUND;
1789 : : }
1790 [ + + ]: 1766 : if (iterator->tree_cursor) {
1791 [ + - ]: 4 : if (iterator->status == FDB_ITR_WAL) { // move 2 steps
1792 : : iterator->tree_cursor =
1793 : 4 : avl_prev(iterator->tree_cursor_prev);
1794 : : } else {
1795 : : // move 1 step if last doc was returned from the main index
1796 : 0 : iterator->tree_cursor = avl_prev(iterator->tree_cursor);
1797 : : }
1798 : 4 : iterator->tree_cursor_prev = iterator->tree_cursor;
1799 : : }
1800 : : }
1801 : : }
1802 : 212953 : return result;
1803 : : }
1804 : :
1805 : : // DOC returned by this function must be freed using 'fdb_doc_free'
1806 : 240568 : fdb_status fdb_iterator_get(fdb_iterator *iterator, fdb_doc **doc)
1807 : : {
1808 : : struct docio_object _doc;
1809 : 240568 : fdb_status ret = FDB_RESULT_SUCCESS;
1810 : : uint64_t offset;
1811 : : struct docio_handle *dhandle;
1812 : 240568 : size_t size_id = sizeof(fdb_kvs_id_t);
1813 : :
1814 [ + ][ + + ]: 240568 : if (!iterator || !doc) {
[ # ]
1815 : 0 : return FDB_RESULT_INVALID_ARGS;
1816 : : }
1817 : :
1818 : 240568 : dhandle = iterator->_dhandle;
1819 [ + + ][ - + ]: 240568 : if (!dhandle || iterator->_get_offset == BLK_NOT_FOUND) {
1820 : 30 : return FDB_RESULT_ITERATOR_FAIL;
1821 : : }
1822 : :
1823 : 240538 : offset = iterator->_get_offset;
1824 : 240538 : _doc.key = NULL;
1825 : 240538 : _doc.length.keylen = 0;
1826 : 240538 : _doc.meta = NULL;
1827 : 240538 : _doc.body = NULL;
1828 : :
1829 : 240538 : uint64_t _offset = docio_read_doc(dhandle, offset, &_doc);
1830 [ - + ]: 240590 : if (_offset == offset) {
1831 : 0 : return FDB_RESULT_KEY_NOT_FOUND;
1832 : : }
1833 [ + + ][ - + ]: 240590 : if (_doc.length.flag & DOCIO_DELETED &&
1834 : : (iterator->opt & FDB_ITR_NO_DELETES)) {
1835 : 0 : free(_doc.key);
1836 : 0 : free(_doc.meta);
1837 : 0 : free(_doc.body);
1838 : 0 : return FDB_RESULT_KEY_NOT_FOUND;
1839 : : }
1840 : :
1841 : 240590 : ret = fdb_doc_create(doc, NULL, 0, NULL, 0, NULL, 0);
1842 [ - + ]: 240623 : if (ret != FDB_RESULT_SUCCESS) {
1843 : 0 : free(_doc.key);
1844 : 0 : free(_doc.meta);
1845 : 0 : free(_doc.body);
1846 : 0 : return ret;
1847 : : }
1848 : :
1849 [ + + ]: 240623 : if (iterator->handle.kvs) {
1850 : : // eliminate KV ID from key
1851 : 240609 : _doc.length.keylen -= size_id;
1852 : 240609 : memmove(_doc.key, (uint8_t*)_doc.key + size_id, _doc.length.keylen);
1853 : : }
1854 : 240623 : (*doc)->key = _doc.key;
1855 : 240623 : (*doc)->keylen = _doc.length.keylen;
1856 : 240623 : (*doc)->meta = _doc.meta;
1857 : 240623 : (*doc)->metalen = _doc.length.metalen;
1858 : 240623 : (*doc)->body = _doc.body;
1859 : 240623 : (*doc)->bodylen = _doc.length.bodylen;
1860 : 240623 : (*doc)->seqnum = _doc.seqnum;
1861 : 240623 : (*doc)->deleted = _doc.length.flag & DOCIO_DELETED;
1862 : 240623 : (*doc)->offset = offset;
1863 : :
1864 : 240653 : return ret;
1865 : : }
1866 : :
1867 : : // DOC returned by this function must be freed using 'fdb_doc_free'
1868 : 20 : fdb_status fdb_iterator_get_metaonly(fdb_iterator *iterator, fdb_doc **doc)
1869 : : {
1870 : : struct docio_object _doc;
1871 : 20 : fdb_status ret = FDB_RESULT_SUCCESS;
1872 : : uint64_t offset, _offset;
1873 : : struct docio_handle *dhandle;
1874 : 20 : size_t size_id = sizeof(fdb_kvs_id_t);
1875 : :
1876 [ + - ][ - + ]: 20 : if (!iterator || !doc) {
1877 : 0 : return FDB_RESULT_INVALID_ARGS;
1878 : : }
1879 : :
1880 : 20 : dhandle = iterator->_dhandle;
1881 [ + - ][ - + ]: 20 : if (!dhandle || iterator->_get_offset == BLK_NOT_FOUND) {
1882 : 0 : return FDB_RESULT_ITERATOR_FAIL;
1883 : : }
1884 : :
1885 : 20 : offset = iterator->_get_offset;
1886 : :
1887 : 20 : _doc.key = NULL;
1888 : 20 : _doc.length.keylen = 0;
1889 : 20 : _doc.meta = NULL;
1890 : 20 : _doc.body = NULL;
1891 : 20 : _offset = docio_read_doc_key_meta(dhandle, offset, &_doc);
1892 [ - + ]: 20 : if (_offset == offset) {
1893 : 0 : return FDB_RESULT_KEY_NOT_FOUND;
1894 : : }
1895 [ - + ][ # # ]: 20 : if (_doc.length.flag & DOCIO_DELETED &&
1896 : : (iterator->opt & FDB_ITR_NO_DELETES)) {
1897 : 0 : free(_doc.key);
1898 : 0 : free(_doc.meta);
1899 : 0 : return FDB_RESULT_KEY_NOT_FOUND;
1900 : : }
1901 : :
1902 : 20 : ret = fdb_doc_create(doc, NULL, 0, NULL, 0, NULL, 0);
1903 [ - + ]: 20 : if (ret != FDB_RESULT_SUCCESS) {
1904 : 0 : free(_doc.key);
1905 : 0 : free(_doc.meta);
1906 : 0 : free(_doc.body);
1907 : 0 : return ret;
1908 : : }
1909 : :
1910 [ + - ]: 20 : if (iterator->handle.kvs) {
1911 : : // eliminate KV ID from key
1912 : 20 : _doc.length.keylen -= size_id;
1913 : 20 : memmove(_doc.key, (uint8_t*)_doc.key + size_id, _doc.length.keylen);
1914 : : }
1915 : 20 : (*doc)->key = _doc.key;
1916 : 20 : (*doc)->keylen = _doc.length.keylen;
1917 : 20 : (*doc)->meta = _doc.meta;
1918 : 20 : (*doc)->metalen = _doc.length.metalen;
1919 : 20 : (*doc)->bodylen = _doc.length.bodylen;
1920 : 20 : (*doc)->seqnum = _doc.seqnum;
1921 : 20 : (*doc)->deleted = _doc.length.flag & DOCIO_DELETED;
1922 : 20 : (*doc)->offset = offset;
1923 : :
1924 : 20 : return ret;
1925 : : }
1926 : :
1927 : 127 : fdb_status fdb_iterator_close(fdb_iterator *iterator)
1928 : : {
1929 : : struct avl_node *a;
1930 : : struct snap_wal_entry *snap_item;
1931 : :
1932 [ + + ]: 127 : if (iterator->hbtrie_iterator) {
1933 : 84 : hbtrie_iterator_free(iterator->hbtrie_iterator);
1934 : 84 : free(iterator->hbtrie_iterator);
1935 : :
1936 [ + + ]: 84 : if (!iterator->handle.shandle) {
1937 : 76 : a = avl_first(iterator->wal_tree);
1938 [ + + ]: 2045 : while(a) {
1939 : 1969 : snap_item = _get_entry(a, struct snap_wal_entry, avl);
1940 : 1969 : a = avl_next(a);
1941 : 1969 : avl_remove(iterator->wal_tree, &snap_item->avl);
1942 : :
1943 : 1969 : free(snap_item->key);
1944 : 1969 : free(snap_item);
1945 : : }
1946 : :
1947 : 76 : free(iterator->wal_tree);
1948 : : }
1949 : : } else { // sequence iterator
1950 [ + + ]: 43 : if (!iterator->handle.shandle) {
1951 : 24 : a = avl_first(iterator->wal_tree);
1952 [ + + ]: 630 : while(a) {
1953 : 606 : snap_item = _get_entry(a, struct snap_wal_entry, avl_seq);
1954 : 606 : a = avl_next(a);
1955 : 606 : avl_remove(iterator->wal_tree, &snap_item->avl_seq);
1956 : :
1957 : 606 : free(snap_item->key);
1958 : 606 : free(snap_item);
1959 : : }
1960 : :
1961 : 24 : free(iterator->wal_tree);
1962 : : }
1963 : : }
1964 : :
1965 [ + + ]: 127 : if (iterator->seqtree_iterator) {
1966 : 1 : btree_iterator_free(iterator->seqtree_iterator);
1967 : 1 : free(iterator->seqtree_iterator);
1968 : : }
1969 [ + + ]: 127 : if (iterator->seqtrie_iterator) {
1970 : 42 : hbtrie_iterator_free(iterator->seqtrie_iterator);
1971 : 42 : free(iterator->seqtrie_iterator);
1972 : : }
1973 : :
1974 [ + + ]: 127 : if (iterator->start_key) {
1975 : 84 : free(iterator->start_key);
1976 : : }
1977 [ + + ]: 127 : if (iterator->end_key) {
1978 : 84 : free(iterator->end_key);
1979 : : }
1980 : :
1981 : 127 : free(iterator->_key);
1982 : 127 : free(iterator);
1983 : :
1984 : 127 : return FDB_RESULT_SUCCESS;
1985 : : }
|
