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 <assert.h>
22 : :
23 : : #include "hbtrie.h"
24 : : #include "list.h"
25 : : #include "btree.h"
26 : : #include "btree_kv.h"
27 : : #include "btree_fast_str_kv.h"
28 : : #include "internal_types.h"
29 : :
30 : : #include "memleak.h"
31 : :
32 : : #ifdef __DEBUG
33 : : #ifndef __DEBUG_HBTRIE
34 : : #undef DBG
35 : : #undef DBGCMD
36 : : #undef DBGSW
37 : : #define DBG(...)
38 : : #define DBGCMD(...)
39 : : #define DBGSW(n, ...)
40 : : #endif
41 : : #endif
42 : :
43 : : #define HBTRIE_EOK (0xF0)
44 : :
45 : : #define CHUNK_FLAG (0x8000)
46 : : typedef uint16_t chunkno_t;
47 : : struct hbtrie_meta {
48 : : chunkno_t chunkno;
49 : : uint16_t prefix_len;
50 : : void *value;
51 : : void *prefix;
52 : : };
53 : :
54 : : #define _l2c(trie, len) ( ( (len) + ((trie)->chunksize-1) ) / (trie)->chunksize )
55 : :
56 : : // MUST return same value to '_get_nchunk(_hbtrie_reform_key(RAWKEY))'
57 : 30404502 : INLINE int _get_nchunk_raw(struct hbtrie *trie, void *rawkey, int rawkeylen)
58 : : {
59 : 30404502 : return _l2c(trie, rawkeylen) + 1;
60 : : }
61 : :
62 : 7480099 : INLINE int _get_nchunk(struct hbtrie *trie, void *key, int keylen)
63 : : {
64 : 7480099 : return (keylen-1) / trie->chunksize + 1;
65 : : }
66 : :
67 : 16246393 : int _hbtrie_reform_key(struct hbtrie *trie, void *rawkey,
68 : : int rawkeylen, void *outkey)
69 : : {
70 : : int outkeylen;
71 : : int nchunk;
72 : : int i;
73 : : uint8_t rsize;
74 : 16246393 : size_t csize = trie->chunksize;
75 : :
76 : 16246393 : nchunk = _get_nchunk_raw(trie, rawkey, rawkeylen);
77 : 16250230 : outkeylen = nchunk * csize;
78 : :
79 [ + + ]: 16250230 : if (nchunk > 2) {
80 : : // copy chunk[0] ~ chunk[nchunk-2]
81 : 16249965 : rsize = rawkeylen - ((nchunk - 2) * csize);
82 : : } else {
83 : 265 : rsize = rawkeylen;
84 : : }
85 [ + ][ + ][ - ]: 16250230 : assert(rsize && rsize <= trie->chunksize);
[ - ]
86 : 16251541 : memcpy((uint8_t*)outkey, (uint8_t*)rawkey, rawkeylen);
87 : :
88 [ + + ]: 16251541 : if (rsize < csize) {
89 : : // zero-fill rest space
90 : 1182165 : i = nchunk - 2;
91 : 1182165 : memset((uint8_t*)outkey + (i*csize) + rsize, 0x0, 2*csize - rsize);
92 : : } else {
93 : : // zero-fill the last chunk
94 : 15069376 : i = nchunk - 1;
95 : 15069376 : memset((uint8_t*)outkey + i * csize, 0x0, csize);
96 : : }
97 : :
98 : : // assign rsize at the end of the outkey
99 : 16251541 : *((uint8_t*)outkey + outkeylen - 1) = rsize;
100 : :
101 : 16251541 : return outkeylen;
102 : : }
103 : :
104 : : // this function only returns (raw) key length
105 : 7402579 : int _hbtrie_reform_key_reverse(struct hbtrie *trie,
106 : : void *key,
107 : : int keylen)
108 : : {
109 : : uint8_t rsize;
110 : 7402579 : rsize = *((uint8_t*)key + keylen - 1);
111 [ - + ]: 7402579 : assert(rsize);
112 : :
113 [ + + ]: 7402579 : if (rsize == trie->chunksize) {
114 : 6447294 : return keylen - trie->chunksize;
115 : : } else {
116 : : // rsize: 1 ~ chunksize-1
117 : 7402579 : return keylen - (trie->chunksize * 2) + rsize;
118 : : }
119 : : }
120 : :
121 : : #define _get_leaf_kv_ops btree_fast_str_kv_get_kb64_vb64
122 : : #define _get_leaf_key btree_fast_str_kv_get_key
123 : : #define _set_leaf_key btree_fast_str_kv_set_key
124 : : #define _set_leaf_inf_key btree_fast_str_kv_set_inf_key
125 : : #define _free_leaf_key btree_fast_str_kv_free_key
126 : :
127 : 1141 : void hbtrie_init(struct hbtrie *trie, int chunksize, int valuelen,
128 : : int btree_nodesize, bid_t root_bid, void *btreeblk_handle,
129 : : struct btree_blk_ops *btree_blk_ops, void *doc_handle,
130 : : hbtrie_func_readkey *readkey)
131 : : {
132 : : struct btree_kv_ops *btree_kv_ops, *btree_leaf_kv_ops;
133 : :
134 : 1141 : trie->chunksize = chunksize;
135 : 1141 : trie->valuelen = valuelen;
136 : 1141 : trie->btree_nodesize = btree_nodesize;
137 : 1141 : trie->btree_blk_ops = btree_blk_ops;
138 : 1141 : trie->btreeblk_handle = btreeblk_handle;
139 : 1141 : trie->doc_handle = doc_handle;
140 : 1141 : trie->root_bid = root_bid;
141 : 1141 : trie->flag = 0x0;
142 : 1141 : trie->leaf_height_limit = 0;
143 : :
144 : : // assign key-value operations
145 : 1141 : btree_kv_ops = (struct btree_kv_ops *)malloc(sizeof(struct btree_kv_ops));
146 : 1141 : btree_leaf_kv_ops = (struct btree_kv_ops *)malloc(sizeof(struct btree_kv_ops));
147 : :
148 [ + - ][ - + ]: 1141 : assert(chunksize == 4 || chunksize == 8);
149 [ - + ]: 1141 : assert(valuelen == 8);
150 [ - + ]: 1141 : assert(chunksize >= sizeof(void *));
151 : :
152 [ + - ][ + - ]: 1141 : if (chunksize == 8 && valuelen == 8){
153 : 1141 : btree_kv_ops = btree_kv_get_kb64_vb64(btree_kv_ops);
154 : 1141 : btree_leaf_kv_ops = _get_leaf_kv_ops(btree_leaf_kv_ops);
155 [ # # ][ # # ]: 0 : }else if (chunksize == 4 && valuelen == 8) {
156 : 0 : btree_kv_ops = btree_kv_get_kb32_vb64(btree_kv_ops);
157 : 0 : btree_leaf_kv_ops = _get_leaf_kv_ops(btree_leaf_kv_ops);
158 : : }
159 : :
160 : 1141 : trie->btree_kv_ops = btree_kv_ops;
161 : 1141 : trie->btree_leaf_kv_ops = btree_leaf_kv_ops;
162 : 1141 : trie->readkey = readkey;
163 : 1141 : trie->map = NULL;
164 : 1141 : trie->last_map_chunk = (void *)malloc(chunksize);
165 : 1141 : memset(trie->last_map_chunk, 0xff, chunksize); // set 0xffff...
166 : 1141 : }
167 : :
168 : 1138 : void hbtrie_free(struct hbtrie *trie)
169 : : {
170 : 1138 : free(trie->btree_kv_ops);
171 : 1138 : free(trie->btree_leaf_kv_ops);
172 : 1138 : free(trie->last_map_chunk);
173 : 1138 : }
174 : :
175 : 1 : void hbtrie_set_flag(struct hbtrie *trie, uint8_t flag)
176 : : {
177 : 1 : trie->flag = flag;
178 [ + - ]: 1 : if (trie->leaf_height_limit == 0) {
179 : 1 : trie->leaf_height_limit = 1;
180 : : }
181 : 1 : }
182 : :
183 : 520 : void hbtrie_set_leaf_height_limit(struct hbtrie *trie, uint8_t limit)
184 : : {
185 : 520 : trie->leaf_height_limit = limit;
186 : 520 : }
187 : :
188 : 572 : void hbtrie_set_leaf_cmp(struct hbtrie *trie,
189 : : int (*cmp)(void *key1, void *key2, void* aux))
190 : : {
191 : 572 : trie->btree_leaf_kv_ops->cmp = cmp;
192 : 572 : }
193 : :
194 : 514 : void hbtrie_set_map_function(struct hbtrie *trie,
195 : : hbtrie_cmp_map *map_func)
196 : : {
197 : 514 : trie->map = map_func;
198 : 514 : }
199 : :
200 : : // IMPORTANT: hbmeta doesn't have own allocated memory space (pointers only)
201 : 24491875 : void _hbtrie_fetch_meta(struct hbtrie *trie, int metasize,
202 : : struct hbtrie_meta *hbmeta, void *buf)
203 : : {
204 : : // read hbmeta from buf
205 : 24491875 : int offset = 0;
206 : 24491875 : uint32_t valuelen = 0;
207 : :
208 : 24491875 : memcpy(&hbmeta->chunkno, buf, sizeof(hbmeta->chunkno));
209 : 24491875 : hbmeta->chunkno = _endian_decode(hbmeta->chunkno);
210 : 24491875 : offset += sizeof(hbmeta->chunkno);
211 : :
212 : 24491875 : memcpy(&valuelen, (uint8_t*)buf+offset, sizeof(trie->valuelen));
213 : 24491875 : offset += sizeof(trie->valuelen);
214 : :
215 [ + + ]: 24491875 : if (valuelen > 0) {
216 : 47 : hbmeta->value = (uint8_t*)buf + offset;
217 : 47 : offset += trie->valuelen;
218 : : } else {
219 : 24493442 : hbmeta->value = NULL;
220 : : }
221 : :
222 [ + + ]: 24491875 : if (metasize - offset > 0) {
223 : : //memcpy(hbmeta->prefix, buf+offset, metasize - offset);
224 : 13584 : hbmeta->prefix = (uint8_t*)buf + offset;
225 : 13584 : hbmeta->prefix_len = metasize - offset;
226 : : } else {
227 : 24478291 : hbmeta->prefix = NULL;
228 : 24478291 : hbmeta->prefix_len = 0;
229 : : }
230 : 24491875 : }
231 : :
232 : : typedef enum {
233 : : HBMETA_NORMAL,
234 : : HBMETA_LEAF,
235 : : } hbmeta_opt;
236 : 2012 : void _hbtrie_store_meta(struct hbtrie *trie,
237 : : metasize_t *metasize_out,
238 : : chunkno_t chunkno,
239 : : hbmeta_opt opt,
240 : : void *prefix,
241 : : int prefixlen,
242 : : void *value,
243 : : void *buf)
244 : : {
245 : : chunkno_t _chunkno;
246 : :
247 : : // write hbmeta to buf
248 : 2012 : *metasize_out = 0;
249 : :
250 [ + + ]: 2012 : if (opt == HBMETA_LEAF) {
251 : 34 : chunkno |= CHUNK_FLAG;
252 : : }
253 : :
254 : 2012 : _chunkno = _endian_encode(chunkno);
255 : 2012 : memcpy(buf, &_chunkno, sizeof(chunkno));
256 : 2012 : *metasize_out += sizeof(chunkno);
257 : :
258 [ + + ]: 2012 : if (value) {
259 : 6 : memcpy((uint8_t*)buf + *metasize_out,
260 : 12 : &trie->valuelen, sizeof(trie->valuelen));
261 : 6 : *metasize_out += sizeof(trie->valuelen);
262 : 6 : memcpy((uint8_t*)buf + *metasize_out,
263 : 12 : value, trie->valuelen);
264 : 6 : *metasize_out += trie->valuelen;
265 : : }else{
266 : 2006 : memset((uint8_t*)buf + *metasize_out, 0x0, sizeof(trie->valuelen));
267 : 2006 : *metasize_out += sizeof(trie->valuelen);
268 : : }
269 : :
270 [ + + ]: 2012 : if (prefixlen > 0) {
271 : 358 : memcpy((uint8_t*)buf + *metasize_out, prefix, prefixlen);
272 : 358 : *metasize_out += prefixlen;
273 : : }
274 : 2012 : }
275 : :
276 : 1863825 : INLINE int _hbtrie_find_diff_chunk(struct hbtrie *trie,
277 : : void *key1,
278 : : void *key2,
279 : : int start_chunk,
280 : : int end_chunk)
281 : : {
282 : : int i;
283 [ + + ]: 20014666 : for (i=start_chunk; i < end_chunk; ++i) {
284 [ + + ]: 18146967 : if (memcmp((uint8_t*)key1 + trie->chunksize*i,
285 : : (uint8_t*)key2 + trie->chunksize*i,
286 : 18146967 : trie->chunksize)) {
287 : 19 : return i;
288 : : }
289 : : }
290 : 1863825 : return i;
291 : : }
292 : :
293 : : //3 ASSUMPTION: 'VALUE' should be based on same endian to hb+trie
294 : :
295 : : #if defined(__ENDIAN_SAFE) || defined(_BIG_ENDIAN)
296 : : // endian safe option is turned on, OR,
297 : : // the architecture is based on big endian
298 : 5030 : INLINE void _hbtrie_set_msb(struct hbtrie *trie, void *value)
299 : : {
300 : 5030 : *((uint8_t*)value) |= (uint8_t)0x80;
301 : 5030 : }
302 : 12264611 : INLINE void _hbtrie_clear_msb(struct hbtrie *trie, void *value)
303 : : {
304 : 12264611 : *((uint8_t*)value) &= ~((uint8_t)0x80);
305 : 12264611 : }
306 : 16725263 : INLINE int _hbtrie_is_msb_set(struct hbtrie *trie, void *value)
307 : : {
308 : 16725263 : return *((uint8_t*)value) & ((uint8_t)0x80);
309 : : }
310 : : #else
311 : : // little endian
312 : : INLINE void _hbtrie_set_msb(struct hbtrie *trie, void *value)
313 : : {
314 : : *((uint8_t*)value + (trie->valuelen-1)) |= (uint8_t)0x80;
315 : : }
316 : : INLINE void _hbtrie_clear_msb(struct hbtrie *trie, void *value)
317 : : {
318 : : *((uint8_t*)value + (trie->valuelen-1)) &= ~((uint8_t)0x80);
319 : : }
320 : : INLINE int _hbtrie_is_msb_set(struct hbtrie *trie, void *value)
321 : : {
322 : : return *((uint8_t*)value + (trie->valuelen-1)) & ((uint8_t)0x80);
323 : : }
324 : : #endif
325 : :
326 : : struct btreelist_item {
327 : : struct btree btree;
328 : : chunkno_t chunkno;
329 : : bid_t child_rootbid;
330 : : struct list_elem e;
331 : : uint8_t leaf;
332 : : };
333 : :
334 : : struct btreeit_item {
335 : : struct btree_iterator btree_it;
336 : : chunkno_t chunkno;
337 : : struct list_elem le;
338 : : uint8_t leaf;
339 : : };
340 : :
341 : : #define _is_leaf_btree(chunkno) ((chunkno) & CHUNK_FLAG)
342 : : #define _get_chunkno(chunkno) ((chunkno) & (~(CHUNK_FLAG)))
343 : :
344 : 3864 : hbtrie_result hbtrie_iterator_init(struct hbtrie *trie,
345 : : struct hbtrie_iterator *it,
346 : : void *initial_key,
347 : : size_t keylen)
348 : : {
349 : 3864 : it->trie = *trie;
350 : :
351 : : // MUST NOT affect the original trie due to sharing the same memory segment
352 : 3864 : it->trie.last_map_chunk = (void *)malloc(it->trie.chunksize);
353 : 3864 : memset(it->trie.last_map_chunk, 0xff, it->trie.chunksize);
354 : :
355 : 3864 : it->curkey = (void *)malloc(HBTRIE_MAX_KEYLEN);
356 : 3864 : memset(it->curkey, 0, HBTRIE_MAX_KEYLEN);
357 : :
358 [ + + ]: 3864 : if (initial_key) {
359 : 3804 : it->keylen = _hbtrie_reform_key(trie, initial_key, keylen, it->curkey);
360 : : }else{
361 : 60 : it->keylen = 0;
362 : : }
363 : 3864 : list_init(&it->btreeit_list);
364 : 3864 : it->flags = 0;
365 : :
366 : 3864 : return HBTRIE_RESULT_SUCCESS;
367 : : }
368 : :
369 : 3864 : hbtrie_result hbtrie_iterator_free(struct hbtrie_iterator *it)
370 : : {
371 : : struct list_elem *e;
372 : : struct btreeit_item *item;
373 : 3864 : e = list_begin(&it->btreeit_list);
374 [ + + ]: 9782 : while(e){
375 : 5918 : item = _get_entry(e, struct btreeit_item, le);
376 : 5918 : e = list_remove(&it->btreeit_list, e);
377 : 5918 : btree_iterator_free(&item->btree_it);
378 : 5918 : mempool_free(item);
379 : : }
380 : 3864 : free(it->trie.last_map_chunk);
381 [ + + ]: 3864 : if (it->curkey) free(it->curkey);
382 : 3864 : return HBTRIE_RESULT_SUCCESS;
383 : : }
384 : :
385 : : // move iterator's cursor to the end of the key range.
386 : : // hbtrie_prev() call after hbtrie_last() will return the last key.
387 : 0 : hbtrie_result hbtrie_last(struct hbtrie_iterator *it)
388 : : {
389 : : struct hbtrie_iterator temp;
390 : :
391 : 0 : temp = *it;
392 : 0 : hbtrie_iterator_free(it);
393 : :
394 : 0 : it->trie = temp.trie;
395 : : // MUST NOT affect the original trie due to sharing the same memory segment
396 : 0 : it->trie.last_map_chunk = (void *)malloc(it->trie.chunksize);
397 : 0 : memset(it->trie.last_map_chunk, 0xff, it->trie.chunksize);
398 : :
399 : 0 : it->curkey = (void *)malloc(HBTRIE_MAX_KEYLEN);
400 : : // init with the infinite (0xff..) key without reforming
401 : 0 : memset(it->curkey, 0xff, it->trie.chunksize);
402 : 0 : it->keylen = it->trie.chunksize;
403 : :
404 : 0 : list_init(&it->btreeit_list);
405 : 0 : it->flags = 0;
406 : :
407 : 0 : return HBTRIE_RESULT_SUCCESS;
408 : : }
409 : :
410 : : // recursive function
411 : : #define HBTRIE_PREFIX_MATCH_ONLY (0x1)
412 : : #define HBTRIE_PARTIAL_MATCH (0x2)
413 : 68468 : hbtrie_result _hbtrie_prev(struct hbtrie_iterator *it,
414 : : struct btreeit_item *item,
415 : : void *key_buf,
416 : : size_t *keylen,
417 : : void *value_buf,
418 : : uint8_t flag)
419 : : {
420 : 68468 : struct hbtrie *trie = &it->trie;
421 : : struct list_elem *e;
422 : : struct btreeit_item *item_new;
423 : : struct btree btree;
424 : 68468 : hbtrie_result hr = HBTRIE_RESULT_FAIL;
425 : : btree_result br;
426 : : struct hbtrie_meta hbmeta;
427 : : struct btree_meta bmeta;
428 : : void *chunk;
429 : 68468 : uint8_t *k = alca(uint8_t, trie->chunksize);
430 : 68468 : uint8_t *v = alca(uint8_t, trie->valuelen);
431 : : bid_t bid;
432 : : uint64_t offset;
433 : :
434 [ + + ]: 68468 : if (item == NULL) {
435 : : // this happens only when first call
436 : : // create iterator for root b-tree
437 [ + + ]: 1840 : if (it->trie.root_bid == BLK_NOT_FOUND) return HBTRIE_RESULT_FAIL;
438 : : // set current chunk (key for b-tree)
439 : 1838 : chunk = it->curkey;
440 : : // load b-tree
441 : : btree_init_from_bid(
442 : : &btree, trie->btreeblk_handle, trie->btree_blk_ops,
443 : : trie->btree_kv_ops,
444 : 1838 : trie->btree_nodesize, trie->root_bid);
445 : 1838 : btree.aux = trie->aux;
446 : :
447 : : item = (struct btreeit_item *)mempool_alloc(sizeof(
448 : 1838 : struct btreeit_item));
449 : 1838 : item->chunkno = 0;
450 : 1838 : item->leaf = 0;
451 : :
452 : 1838 : br = btree_iterator_init(&btree, &item->btree_it, chunk);
453 [ - + ]: 1838 : if (br == BTREE_RESULT_FAIL) return HBTRIE_RESULT_FAIL;
454 : :
455 : 1838 : list_push_back(&it->btreeit_list, &item->le);
456 : : }
457 : :
458 : 68466 : e = list_next(&item->le);
459 [ + + ]: 68466 : if (e) {
460 : : // if prev sub b-tree exists
461 : 40610 : item_new = _get_entry(e, struct btreeit_item, le);
462 : 40610 : hr = _hbtrie_prev(it, item_new, key_buf, keylen, value_buf, flag);
463 [ + + ]: 40610 : if (hr == HBTRIE_RESULT_SUCCESS) return hr;
464 : 4570 : it->keylen = (item->chunkno+1) * trie->chunksize;
465 : : }
466 : :
467 [ + - ]: 32483 : while (hr == HBTRIE_RESULT_FAIL) {
468 : : // get key-value from current b-tree iterator
469 : 32483 : memset(k, 0, trie->chunksize);
470 : 32483 : br = btree_prev(&item->btree_it, k, v);
471 [ + + ]: 32483 : if (item->leaf) {
472 : 53 : _free_leaf_key(k);
473 : : } else {
474 : 32430 : chunk = (uint8_t*)it->curkey + item->chunkno * trie->chunksize;
475 [ + + ]: 32430 : if (item->btree_it.btree.kv_ops->cmp(k, chunk,
476 : 32430 : item->btree_it.btree.aux) != 0) {
477 : : // not exact match key .. the rest of string is not necessary anymore
478 : 28504 : it->keylen = (item->chunkno+1) * trie->chunksize;
479 : 28504 : HBTRIE_ITR_SET_MOVED(it);
480 : : }
481 : : }
482 : :
483 [ + + ]: 32483 : if (br == BTREE_RESULT_FAIL) {
484 : : // no more KV pair in the b-tree
485 : 4747 : btree_iterator_free(&item->btree_it);
486 : 4747 : list_remove(&it->btreeit_list, &item->le);
487 : 4747 : mempool_free(item);
488 : 4747 : return HBTRIE_RESULT_FAIL;
489 : : }
490 : :
491 : : // check whether v points to doc or sub b-tree
492 [ + + ]: 27736 : if (_hbtrie_is_msb_set(trie, v)) {
493 : : // MSB is set -> sub b-tree
494 : :
495 : : // load sub b-tree and create new iterator for the b-tree
496 : 4776 : _hbtrie_clear_msb(trie, v);
497 : 4776 : bid = trie->btree_kv_ops->value2bid(v);
498 : 4776 : bid = _endian_decode(bid);
499 : : btree_init_from_bid(&btree, trie->btreeblk_handle,
500 : : trie->btree_blk_ops, trie->btree_kv_ops,
501 : 4776 : trie->btree_nodesize, bid);
502 : :
503 : : // get sub b-tree's chunk number
504 : 4776 : bmeta.data = (void *)mempool_alloc(trie->btree_nodesize);
505 : 4776 : bmeta.size = btree_read_meta(&btree, bmeta.data);
506 : 4776 : _hbtrie_fetch_meta(trie, bmeta.size, &hbmeta, bmeta.data);
507 : :
508 : : item_new = (struct btreeit_item *)
509 : 4776 : mempool_alloc(sizeof(struct btreeit_item));
510 [ + + ]: 4776 : if (_is_leaf_btree(hbmeta.chunkno)) {
511 : : void *void_cmp;
512 : :
513 [ + - ]: 2 : if (trie->map) { // custom cmp functions exist
514 [ + - ]: 2 : if (!memcmp(trie->last_map_chunk, it->curkey, trie->chunksize)) {
515 : : // same custom function was used in the last call ..
516 : : // do nothing
517 : : } else {
518 : : // get cmp function corresponding to the key
519 : 2 : void_cmp = trie->map(it->curkey, (void *)trie);
520 [ + - ]: 2 : if (void_cmp) {
521 : 2 : memcpy(trie->last_map_chunk, it->curkey, trie->chunksize);
522 : 2 : trie->aux = void_cmp; // set aux for _fdb_custom_cmp_wrap()
523 : : }
524 : : }
525 : : }
526 : :
527 : 2 : btree.kv_ops = trie->btree_leaf_kv_ops;
528 : 2 : item_new->leaf = 1;
529 : : } else {
530 : 4774 : item_new->leaf = 0;
531 : : }
532 : 4776 : btree.aux = trie->aux;
533 : 4776 : hbmeta.chunkno = _get_chunkno(hbmeta.chunkno);
534 : 4776 : item_new->chunkno = hbmeta.chunkno;
535 : :
536 : : // Note: if user's key is exactly aligned to chunk size, then the
537 : : // dummy chunk will be a zero-filled value, and it is used
538 : : // as a key in the next level of B+tree. Hence, there will be
539 : : // no problem to assign the dummy chunk to the 'chunk' variable.
540 [ + + ]: 4776 : if ( (item_new->chunkno+1) * trie->chunksize <= it->keylen) {
541 : : // happen only once for the first call (for each level of b-trees)
542 : : chunk = (uint8_t*)it->curkey +
543 : 3148 : item_new->chunkno*trie->chunksize;
544 : : } else {
545 : : // chunk number of the b-tree is shorter than current iterator's key
546 [ + + ]: 1628 : if (!HBTRIE_ITR_IS_MOVED(it)) {
547 : : // The first prev call right after iterator init call.
548 : : // This means that the init key is smaller than
549 : : // the smallest key of the current tree, and larger than
550 : : // the largest key of the previous tree.
551 : : // So we have to go back to the parent tree, and
552 : : // return the largest key of the previous tree.
553 : 14 : mempool_free(bmeta.data);
554 : 14 : mempool_free(item_new);
555 : 14 : it->keylen = (item->chunkno+1) * trie->chunksize;
556 : 14 : HBTRIE_ITR_SET_MOVED(it);
557 : 14 : continue;
558 : : }
559 : : // set largest key
560 : 1614 : chunk = alca(uint8_t, trie->chunksize);
561 : 1614 : memset(chunk, 0xff, trie->chunksize);
562 : : }
563 : :
564 [ + + ][ + - ]: 4762 : if (item_new->leaf && chunk) {
565 : 2 : uint8_t *k_temp = alca(uint8_t, trie->chunksize);
566 : 2 : size_t _leaf_keylen, _leaf_keylen_raw = 0;
567 : :
568 : 2 : _leaf_keylen = it->keylen - (item_new->chunkno * trie->chunksize);
569 [ - + ]: 2 : if (_leaf_keylen) {
570 : : _leaf_keylen_raw = _hbtrie_reform_key_reverse(
571 : 0 : trie, chunk, _leaf_keylen);
572 : 0 : _set_leaf_key(k_temp, chunk, _leaf_keylen_raw);
573 [ # # ]: 0 : if (_leaf_keylen_raw) {
574 : 0 : btree_iterator_init(&btree, &item_new->btree_it, k_temp);
575 : : } else {
576 : 0 : btree_iterator_init(&btree, &item_new->btree_it, NULL);
577 : : }
578 : : } else {
579 : : // set initial key as the largest key
580 : : // for reverse scan from the end of the B+tree
581 : 2 : _set_leaf_inf_key(k_temp);
582 : 2 : btree_iterator_init(&btree, &item_new->btree_it, k_temp);
583 : : }
584 : 2 : _free_leaf_key(k_temp);
585 : : } else {
586 : 4760 : btree_iterator_init(&btree, &item_new->btree_it, chunk);
587 : : }
588 : 4762 : list_push_back(&it->btreeit_list, &item_new->le);
589 : :
590 [ - + ][ # # ]: 4762 : if (hbmeta.value && chunk == NULL) {
591 : : // NULL key exists .. the smallest key in this tree .. return first
592 : 0 : offset = trie->btree_kv_ops->value2bid(hbmeta.value);
593 [ # # ]: 0 : if (!(flag & HBTRIE_PREFIX_MATCH_ONLY)) {
594 : 0 : *keylen = trie->readkey(trie->doc_handle, offset, key_buf);
595 : : it->keylen = _hbtrie_reform_key(trie, key_buf, *keylen,
596 : 0 : it->curkey);
597 : : }
598 : 0 : memcpy(value_buf, &offset, trie->valuelen);
599 : 0 : hr = HBTRIE_RESULT_SUCCESS;
600 : : } else {
601 : : hr = _hbtrie_prev(it, item_new, key_buf, keylen, value_buf,
602 : 4762 : flag);
603 : : }
604 : 4762 : mempool_free(bmeta.data);
605 [ + + ]: 4762 : if (hr == HBTRIE_RESULT_SUCCESS)
606 : 4719 : return hr;
607 : :
608 : : // fail searching .. get back to parent tree
609 : : // (this happens when the initial key is smaller than
610 : : // the smallest key in the current tree (ITEM_NEW) ..
611 : : // so return back to ITEM and retrieve next child)
612 : 43 : it->keylen = (item->chunkno+1) * trie->chunksize;
613 : 43 : HBTRIE_ITR_SET_MOVED(it);
614 : :
615 : : } else {
616 : : // MSB is not set -> doc
617 : : // read entire key and return the doc offset
618 : 22960 : offset = trie->btree_kv_ops->value2bid(v);
619 [ + - ]: 22960 : if (!(flag & HBTRIE_PREFIX_MATCH_ONLY)) {
620 : 22960 : *keylen = trie->readkey(trie->doc_handle, offset, key_buf);
621 : 22960 : it->keylen = _hbtrie_reform_key(trie, key_buf, *keylen, it->curkey);
622 : : }
623 : 22960 : memcpy(value_buf, &offset, trie->valuelen);
624 : :
625 : 22960 : return HBTRIE_RESULT_SUCCESS;
626 : : }
627 : : }
628 : 68468 : return HBTRIE_RESULT_FAIL;
629 : : }
630 : :
631 : 24807 : hbtrie_result hbtrie_prev(struct hbtrie_iterator *it,
632 : : void *key_buf,
633 : : size_t *keylen,
634 : : void *value_buf)
635 : : {
636 : : hbtrie_result hr;
637 : :
638 [ + + ][ + + ]: 24807 : if (HBTRIE_ITR_IS_REV(it) && HBTRIE_ITR_IS_FAILED(it)) {
639 : 1711 : return HBTRIE_RESULT_FAIL;
640 : : }
641 : :
642 : 23096 : struct list_elem *e = list_begin(&it->btreeit_list);
643 : 23096 : struct btreeit_item *item = NULL;
644 [ + + ]: 23096 : if (e) item = _get_entry(e, struct btreeit_item, le);
645 : :
646 : 23096 : hr = _hbtrie_prev(it, item, key_buf, keylen, value_buf, 0x0);
647 : 23096 : HBTRIE_ITR_SET_REV(it);
648 [ + + ]: 23096 : if (hr == HBTRIE_RESULT_SUCCESS) {
649 : 22960 : HBTRIE_ITR_CLR_FAILED(it);
650 : 22960 : HBTRIE_ITR_SET_MOVED(it);
651 : : } else {
652 : 136 : HBTRIE_ITR_SET_FAILED(it);
653 : : }
654 : 24807 : return hr;
655 : : }
656 : :
657 : : // recursive function
658 : 4202438 : hbtrie_result _hbtrie_next(struct hbtrie_iterator *it,
659 : : struct btreeit_item *item,
660 : : void *key_buf,
661 : : size_t *keylen,
662 : : void *value_buf,
663 : : uint8_t flag)
664 : : {
665 : 4202438 : struct hbtrie *trie = &it->trie;
666 : : struct list_elem *e;
667 : : struct btreeit_item *item_new;
668 : : struct btree btree;
669 : 4202438 : hbtrie_result hr = HBTRIE_RESULT_FAIL;
670 : : btree_result br;
671 : : struct hbtrie_meta hbmeta;
672 : : struct btree_meta bmeta;
673 : : void *chunk;
674 : 4202438 : uint8_t *k = alca(uint8_t, trie->chunksize);
675 : 4202438 : uint8_t *v = alca(uint8_t, trie->valuelen);
676 : : bid_t bid;
677 : : uint64_t offset;
678 : :
679 [ + + ]: 4202438 : if (item == NULL) {
680 : : // this happens only when first call
681 : : // create iterator for root b-tree
682 [ + + ]: 2028 : if (it->trie.root_bid == BLK_NOT_FOUND) return HBTRIE_RESULT_FAIL;
683 : : // set current chunk (key for b-tree)
684 : 2007 : chunk = it->curkey;
685 : : // load b-tree
686 : : btree_init_from_bid(
687 : : &btree, trie->btreeblk_handle, trie->btree_blk_ops, trie->btree_kv_ops,
688 : 2007 : trie->btree_nodesize, trie->root_bid);
689 : 2007 : btree.aux = trie->aux;
690 : :
691 : 2007 : item = (struct btreeit_item *)mempool_alloc(sizeof(struct btreeit_item));
692 : 2007 : item->chunkno = 0;
693 : 2007 : item->leaf = 0;
694 : :
695 : 2007 : br = btree_iterator_init(&btree, &item->btree_it, chunk);
696 [ - + ]: 2007 : if (br == BTREE_RESULT_FAIL) return HBTRIE_RESULT_FAIL;
697 : :
698 : 2007 : list_push_back(&it->btreeit_list, &item->le);
699 : : }
700 : :
701 : 4202417 : e = list_next(&item->le);
702 [ + + ]: 4202564 : if (e) {
703 : : // if next sub b-tree exists
704 : 2107856 : item_new = _get_entry(e, struct btreeit_item, le);
705 : 2107856 : hr = _hbtrie_next(it, item_new, key_buf, keylen, value_buf, flag);
706 [ + + ]: 2107893 : if (hr == HBTRIE_RESULT_SUCCESS) return hr;
707 : 4850 : it->keylen = (item->chunkno+1) * trie->chunksize;
708 : : }
709 : :
710 [ + - ]: 2099706 : while(hr == HBTRIE_RESULT_FAIL) {
711 : : // get key-value from current b-tree iterator
712 : 2099706 : memset(k, 0, trie->chunksize);
713 : 2099706 : br = btree_next(&item->btree_it, k, v);
714 [ + + ]: 2099488 : if (item->leaf) {
715 : 4450 : _free_leaf_key(k);
716 : : } else {
717 : 2095038 : chunk = (uint8_t*)it->curkey + item->chunkno * trie->chunksize;
718 [ + + ]: 2094855 : if (item->btree_it.btree.kv_ops->cmp(k, chunk,
719 : 2095038 : item->btree_it.btree.aux) != 0) {
720 : : // not exact match key .. the rest of string is not necessary anymore
721 : 2090390 : it->keylen = (item->chunkno+1) * trie->chunksize;
722 : 2090390 : HBTRIE_ITR_SET_MOVED(it);
723 : : }
724 : : }
725 : :
726 [ + + ]: 2099323 : if (br == BTREE_RESULT_FAIL) {
727 : : // no more KV pair in the b-tree
728 : 5106 : btree_iterator_free(&item->btree_it);
729 : 5106 : list_remove(&it->btreeit_list, &item->le);
730 : 5106 : mempool_free(item);
731 : 5106 : return HBTRIE_RESULT_FAIL;
732 : : }
733 : :
734 : : // check whether v points to doc or sub b-tree
735 [ + + ]: 2094217 : if (_hbtrie_is_msb_set(trie, v)) {
736 : : // MSB is set -> sub b-tree
737 : :
738 : : // load sub b-tree and create new iterator for the b-tree
739 : 7164 : _hbtrie_clear_msb(trie, v);
740 : 7164 : bid = trie->btree_kv_ops->value2bid(v);
741 : 7164 : bid = _endian_decode(bid);
742 : : btree_init_from_bid(&btree, trie->btreeblk_handle,
743 : : trie->btree_blk_ops, trie->btree_kv_ops,
744 : 7164 : trie->btree_nodesize, bid);
745 : :
746 : : // get sub b-tree's chunk number
747 : 7164 : bmeta.data = (void *)mempool_alloc(trie->btree_nodesize);
748 : 7164 : bmeta.size = btree_read_meta(&btree, bmeta.data);
749 : 7164 : _hbtrie_fetch_meta(trie, bmeta.size, &hbmeta, bmeta.data);
750 : :
751 : : item_new = (struct btreeit_item *)
752 : 7164 : mempool_alloc(sizeof(struct btreeit_item));
753 [ + + ]: 7164 : if (_is_leaf_btree(hbmeta.chunkno)) {
754 : : void *void_cmp;
755 : :
756 [ + + ]: 31 : if (trie->map) { // custom cmp functions exist
757 [ + + ]: 15 : if (!memcmp(trie->last_map_chunk, it->curkey, trie->chunksize)) {
758 : : // same custom function was used in the last call ..
759 : : // do nothing
760 : : } else {
761 : : // get cmp function corresponding to the key
762 : 12 : void_cmp = trie->map(it->curkey, (void *)trie);
763 [ + + ]: 12 : if (void_cmp) {
764 : 11 : memcpy(trie->last_map_chunk, it->curkey, trie->chunksize);
765 : 11 : trie->aux = void_cmp; // set aux for _fdb_custom_cmp_wrap()
766 : : }
767 : : }
768 : : }
769 : :
770 : 31 : btree.kv_ops = trie->btree_leaf_kv_ops;
771 : 31 : item_new->leaf = 1;
772 : : } else {
773 : 7133 : item_new->leaf = 0;
774 : : }
775 : 7164 : btree.aux = trie->aux;
776 : 7164 : hbmeta.chunkno = _get_chunkno(hbmeta.chunkno);
777 : 7164 : item_new->chunkno = hbmeta.chunkno;
778 : :
779 : : // Note: if user's key is exactly aligned to chunk size, then the
780 : : // dummy chunk will be a zero-filled value, and it is used
781 : : // as a key in the next level of B+tree. Hence, there will be
782 : : // no problem to assign the dummy chunk to the 'chunk' variable.
783 [ + + ]: 7164 : if ( (item_new->chunkno+1) * trie->chunksize <= it->keylen) {
784 : : // happen only once for the first call (for each level of b-trees)
785 : : chunk = (uint8_t*)it->curkey +
786 : 3281 : item_new->chunkno*trie->chunksize;
787 : : }else{
788 : : // chunk number of the b-tree is longer than current iterator's key
789 : : // set smallest key
790 : 3883 : chunk = NULL;
791 : : }
792 : :
793 [ + + ][ + + ]: 7164 : if (item_new->leaf && chunk) {
794 : 9 : uint8_t *k_temp = alca(uint8_t, trie->chunksize);
795 : 9 : size_t _leaf_keylen, _leaf_keylen_raw = 0;
796 : :
797 : 9 : _leaf_keylen = it->keylen - (item_new->chunkno * trie->chunksize);
798 [ + - ]: 9 : if (_leaf_keylen > 0) {
799 : : _leaf_keylen_raw = _hbtrie_reform_key_reverse(
800 : 9 : trie, chunk, _leaf_keylen);
801 : : }
802 [ + + ]: 9 : if (_leaf_keylen_raw) {
803 : 2 : _set_leaf_key(k_temp, chunk, _leaf_keylen_raw);
804 : 2 : btree_iterator_init(&btree, &item_new->btree_it, k_temp);
805 : 2 : _free_leaf_key(k_temp);
806 : : } else {
807 : 7 : btree_iterator_init(&btree, &item_new->btree_it, NULL);
808 : 9 : }
809 : : } else {
810 : 7155 : btree_iterator_init(&btree, &item_new->btree_it, chunk);
811 : : }
812 : 7164 : list_push_back(&it->btreeit_list, &item_new->le);
813 : :
814 [ + + ][ + + ]: 7164 : if (hbmeta.value && chunk == NULL) {
815 : : // NULL key exists .. the smallest key in this tree .. return first
816 : 9 : offset = trie->btree_kv_ops->value2bid(hbmeta.value);
817 [ + + ]: 9 : if (!(flag & HBTRIE_PREFIX_MATCH_ONLY)) {
818 : 7 : *keylen = trie->readkey(trie->doc_handle, offset, key_buf);
819 : 7 : it->keylen = _hbtrie_reform_key(trie, key_buf, *keylen, it->curkey);
820 : : }
821 : 9 : memcpy(value_buf, &offset, trie->valuelen);
822 : 9 : hr = HBTRIE_RESULT_SUCCESS;
823 : : } else {
824 : 7155 : hr = _hbtrie_next(it, item_new, key_buf, keylen, value_buf, flag);
825 : : }
826 : 7164 : mempool_free(bmeta.data);
827 [ + + ]: 7164 : if (hr == HBTRIE_RESULT_SUCCESS)
828 : 7016 : return hr;
829 : :
830 : : // fail searching .. get back to parent tree
831 : : // (this happens when the initial key is greater than
832 : : // the largest key in the current tree (ITEM_NEW) ..
833 : : // so return back to ITEM and retrieve next child)
834 : 148 : it->keylen = (item->chunkno+1) * trie->chunksize;
835 : :
836 : : }else{
837 : : // MSB is not set -> doc
838 : : // read entire key and return the doc offset
839 : 2087050 : offset = trie->btree_kv_ops->value2bid(v);
840 [ + + ]: 2086946 : if (!(flag & HBTRIE_PREFIX_MATCH_ONLY)) {
841 : 206472 : *keylen = trie->readkey(trie->doc_handle, offset, key_buf);
842 : 207178 : it->keylen = _hbtrie_reform_key(trie, key_buf, *keylen, it->curkey);
843 : : }
844 : 2087535 : memcpy(value_buf, &offset, trie->valuelen);
845 : :
846 : 2087535 : return HBTRIE_RESULT_SUCCESS;
847 : : }
848 : : }
849 : 4202721 : return HBTRIE_RESULT_FAIL;
850 : : }
851 : :
852 : 208194 : hbtrie_result hbtrie_next(struct hbtrie_iterator *it,
853 : : void *key_buf,
854 : : size_t *keylen,
855 : : void *value_buf)
856 : : {
857 : : hbtrie_result hr;
858 : :
859 [ + + ][ + + ]: 208194 : if (HBTRIE_ITR_IS_FWD(it) && HBTRIE_ITR_IS_FAILED(it)) {
860 : 1051 : return HBTRIE_RESULT_FAIL;
861 : : }
862 : :
863 : 207143 : struct list_elem *e = list_begin(&it->btreeit_list);
864 : 207111 : struct btreeit_item *item = NULL;
865 [ + + ]: 207111 : if (e) item = _get_entry(e, struct btreeit_item, le);
866 : :
867 : 207111 : hr = _hbtrie_next(it, item, key_buf, keylen, value_buf, 0x0);
868 : 207128 : HBTRIE_ITR_SET_FWD(it);
869 [ + + ]: 207128 : if (hr == HBTRIE_RESULT_SUCCESS) {
870 : 207053 : HBTRIE_ITR_CLR_FAILED(it);
871 : 207053 : HBTRIE_ITR_SET_MOVED(it);
872 : : } else {
873 : 75 : HBTRIE_ITR_SET_FAILED(it);
874 : : }
875 : 208179 : return hr;
876 : : }
877 : :
878 : 1880520 : hbtrie_result hbtrie_next_value_only(struct hbtrie_iterator *it,
879 : : void *value_buf)
880 : : {
881 : : hbtrie_result hr;
882 : :
883 [ - + ]: 1880520 : if (it->curkey == NULL) return HBTRIE_RESULT_FAIL;
884 : :
885 : 1880520 : struct list_elem *e = list_begin(&it->btreeit_list);
886 : 1880520 : struct btreeit_item *item = NULL;
887 [ + + ]: 1880520 : if (e) item = _get_entry(e, struct btreeit_item, le);
888 : :
889 : 1880520 : hr = _hbtrie_next(it, item, NULL, 0, value_buf, HBTRIE_PREFIX_MATCH_ONLY);
890 [ + + ]: 1880520 : if (hr == HBTRIE_RESULT_FAIL) {
891 : : // this iterator reaches the end of hb-trie
892 : 54 : free(it->curkey);
893 : 54 : it->curkey = NULL;
894 : : }
895 : 1880520 : return hr;
896 : : }
897 : :
898 : 8537268 : void _hbtrie_free_btreelist(struct list *btreelist)
899 : : {
900 : : struct btreelist_item *btreeitem;
901 : : struct list_elem *e;
902 : :
903 : : // free all items on list
904 : 8537268 : e = list_begin(btreelist);
905 [ + + ]: 25626613 : while(e) {
906 : 17089343 : btreeitem = _get_entry(e, struct btreelist_item, e);
907 : 17089343 : e = list_remove(btreelist, e);
908 : 17089353 : mempool_free(btreeitem);
909 : : }
910 : 8537270 : }
911 : :
912 : 8537275 : void _hbtrie_btree_cascaded_update(struct hbtrie *trie,
913 : : struct list *btreelist,
914 : : void *key,
915 : : int free_opt)
916 : : {
917 : : bid_t bid_new, _bid;
918 : : struct btreelist_item *btreeitem, *btreeitem_child;
919 : : struct list_elem *e, *e_child;
920 : :
921 : 8537275 : e = e_child = NULL;
922 : :
923 : : //3 cascaded update of each b-tree from leaf to root
924 : 8537275 : e_child = list_end(btreelist);
925 [ + + ]: 8537276 : if (e_child) e = list_prev(e_child);
926 : :
927 [ + + ][ + - ]: 17089380 : while(e && e_child) {
[ + + ]
928 : 8552117 : btreeitem = _get_entry(e, struct btreelist_item, e);
929 : 8552117 : btreeitem_child = _get_entry(e_child, struct btreelist_item, e);
930 : :
931 [ + + ]: 8552117 : if (btreeitem->child_rootbid != btreeitem_child->btree.root_bid) {
932 : : // root node of child sub-tree has been moved to another block
933 : : // update parent sub-tree
934 : 3351 : bid_new = btreeitem_child->btree.root_bid;
935 : 3351 : _bid = _endian_encode(bid_new);
936 : 3351 : _hbtrie_set_msb(trie, (void *)&_bid);
937 : : btree_insert(&btreeitem->btree,
938 : 3351 : (uint8_t*)key + btreeitem->chunkno * trie->chunksize,
939 : 3351 : (void *)&_bid);
940 : : }
941 : 8552117 : e_child = e;
942 : 8552117 : e = list_prev(e);
943 : : }
944 : :
945 : : // update trie root bid
946 [ - + ]: 8537263 : if (e) {
947 : 0 : btreeitem = _get_entry(e, struct btreelist_item, e);
948 : 0 : trie->root_bid = btreeitem->btree.root_bid;
949 [ + - ]: 8537263 : }else if (e_child) {
950 : 8537263 : btreeitem = _get_entry(e_child, struct btreelist_item, e);
951 : 8537263 : trie->root_bid = btreeitem->btree.root_bid;
952 : : }else {
953 : 0 : assert(0);
954 : : }
955 : :
956 [ + - ]: 8537263 : if (free_opt) {
957 : 8537263 : _hbtrie_free_btreelist(btreelist);
958 : : }
959 : 8537270 : }
960 : :
961 : 5625406 : hbtrie_result _hbtrie_find(struct hbtrie *trie, void *key, int keylen,
962 : : void *valuebuf, struct list *btreelist, uint8_t flag)
963 : : {
964 : : int nchunk;
965 : : int rawkeylen;
966 : 5625406 : int prevchunkno, curchunkno, cpt_node = 0;
967 : 5625406 : struct btree *btree = NULL;
968 : : struct btree btree_static;
969 : : btree_result r;
970 : : struct hbtrie_meta hbmeta;
971 : : struct btree_meta meta;
972 : 5625406 : struct btreelist_item *btreeitem = NULL;
973 : 5625406 : uint8_t *k = alca(uint8_t, trie->chunksize);
974 : 5625406 : uint8_t *buf = alca(uint8_t, trie->btree_nodesize);
975 : 5625406 : uint8_t *btree_value = alca(uint8_t, trie->valuelen);
976 : 5625406 : void *chunk = NULL;
977 : : void *void_cmp;
978 : : bid_t bid_new;
979 : 5625406 : nchunk = _get_nchunk(trie, key, keylen);
980 : :
981 : 5624336 : meta.data = buf;
982 : 5624336 : curchunkno = 0;
983 : :
984 [ + + ]: 5624336 : if (trie->map) { // custom cmp functions exist
985 [ + + ]: 5622452 : if (!memcmp(trie->last_map_chunk, key, trie->chunksize)) {
986 : : // same custom function was used in the last call .. do nothing
987 : : } else {
988 : : // get cmp function corresponding to the key
989 : 5602840 : void_cmp = trie->map(key, (void *)trie);
990 [ + + ]: 5602688 : if (void_cmp) { // custom cmp function matches .. turn on leaf b+tree mode
991 : 1987 : memcpy(trie->last_map_chunk, key, trie->chunksize);
992 : 1987 : trie->aux = void_cmp; // set aux for _fdb_custom_cmp_wrap()
993 : : }
994 : : }
995 : : }
996 : :
997 [ + + ]: 5624184 : if (btreelist) {
998 : 22 : list_init(btreelist);
999 : 22 : btreeitem = (struct btreelist_item *)mempool_alloc(sizeof(struct btreelist_item));
1000 : 22 : list_push_back(btreelist, &btreeitem->e);
1001 : 2070 : btree = &btreeitem->btree;
1002 : : } else {
1003 : 5624162 : btree = &btree_static;
1004 : : }
1005 : :
1006 [ + + ]: 5626232 : if (trie->root_bid == BLK_NOT_FOUND) {
1007 : : // retrieval fail
1008 : 1936933 : return HBTRIE_RESULT_FAIL;
1009 : : } else {
1010 : : // read from root_bid
1011 : : r = btree_init_from_bid(btree, trie->btreeblk_handle, trie->btree_blk_ops,
1012 : : trie->btree_kv_ops, trie->btree_nodesize,
1013 : 3689299 : trie->root_bid);
1014 [ - + ]: 3687837 : if (r != BTREE_RESULT_SUCCESS) {
1015 : 0 : return HBTRIE_RESULT_FAIL;
1016 : : }
1017 : 3687837 : btree->aux = trie->aux;
1018 [ + ][ + + ]: 3687837 : assert(btree->ksize == trie->chunksize && btree->vsize == trie->valuelen);
[ - ]
1019 : : }
1020 : :
1021 [ + - ]: 7374760 : while (curchunkno < nchunk) {
1022 : : // get current chunk number
1023 : 7374760 : meta.size = btree_read_meta(btree, meta.data);
1024 : 7379438 : _hbtrie_fetch_meta(trie, meta.size, &hbmeta, meta.data);
1025 : 7395001 : prevchunkno = curchunkno;
1026 [ + + ]: 7395001 : if (_is_leaf_btree(hbmeta.chunkno)) {
1027 : 14342 : cpt_node = 1;
1028 : 14342 : hbmeta.chunkno = _get_chunkno(hbmeta.chunkno);
1029 : 14342 : btree->kv_ops = trie->btree_leaf_kv_ops;
1030 : : }
1031 : 7395001 : curchunkno = hbmeta.chunkno;
1032 : :
1033 [ + + ]: 7395001 : if (btreelist) {
1034 : 29 : btreeitem->chunkno = curchunkno;
1035 : 29 : btreeitem->leaf = cpt_node;
1036 : : }
1037 : :
1038 : : //3 check whether there are skipped prefixes.
1039 [ + + ]: 7395001 : if (curchunkno - prevchunkno > 1) {
1040 [ - + ]: 6003 : assert(hbmeta.prefix != NULL);
1041 : : // prefix comparison (find the first different chunk)
1042 : : int diffchunkno = _hbtrie_find_diff_chunk(
1043 : : trie, hbmeta.prefix,
1044 : 6003 : (uint8_t*)key + trie->chunksize * (prevchunkno+1),
1045 : 6003 : 0, curchunkno - (prevchunkno+1));
1046 [ - + ]: 6003 : if (diffchunkno < curchunkno - (prevchunkno+1)) {
1047 : : // prefix does not match -> retrieval fail
1048 : 0 : return HBTRIE_RESULT_FAIL;
1049 : : }
1050 : : }
1051 : :
1052 : : //3 search b-tree using current chunk (or postfix)
1053 : 7395001 : rawkeylen = _hbtrie_reform_key_reverse(trie, key, keylen);
1054 [ + + ][ + ]: 7394182 : if ((cpt_node && rawkeylen == curchunkno * trie->chunksize) ||
[ + + ][ + + ]
[ + ]
1055 : : (!cpt_node && nchunk == curchunkno)) {
1056 : : // KEY is exactly same as tree's prefix .. return value in metasection
1057 : 4 : memcpy(valuebuf, hbmeta.value, trie->valuelen);
1058 : 4 : return HBTRIE_RESULT_SUCCESS;
1059 : : } else {
1060 : 7394178 : chunk = (uint8_t*)key + curchunkno*trie->chunksize;
1061 [ + + ]: 7394178 : if (cpt_node) {
1062 : : // leaf b-tree
1063 : : size_t rawchunklen =
1064 : : _hbtrie_reform_key_reverse(trie, chunk,
1065 : 14338 : (nchunk-curchunkno)*trie->chunksize);
1066 : :
1067 : 14338 : _set_leaf_key(k, chunk, rawchunklen);
1068 : 14338 : r = btree_find(btree, k, btree_value);
1069 : 14338 : _free_leaf_key(k);
1070 : : } else {
1071 : 7379840 : r = btree_find(btree, chunk, btree_value);
1072 : : }
1073 : : }
1074 : :
1075 [ + + ]: 7388271 : if (r == BTREE_RESULT_FAIL) {
1076 : : // retrieval fail
1077 : 1834039 : return HBTRIE_RESULT_FAIL;
1078 : : } else {
1079 : : // same chunk exists
1080 [ + + ][ + + ]: 5554232 : if (flag & HBTRIE_PARTIAL_MATCH &&
1081 : : curchunkno + 1 == nchunk - 1) {
1082 : : // partial match mode & the last meaningful chunk
1083 : : // return btree value
1084 : 64 : memcpy(valuebuf, btree_value, trie->valuelen);
1085 : 64 : return HBTRIE_RESULT_SUCCESS;
1086 : : }
1087 : :
1088 : : // check whether the value points to sub-tree or document
1089 : : // check MSB
1090 [ + + ]: 5554168 : if (_hbtrie_is_msb_set(trie, btree_value)) {
1091 : : // this is BID of b-tree node (by clearing MSB)
1092 : 3703734 : _hbtrie_clear_msb(trie, btree_value);
1093 : 3703534 : bid_new = trie->btree_kv_ops->value2bid(btree_value);
1094 : 3705584 : bid_new = _endian_decode(bid_new);
1095 : :
1096 [ + + ]: 3705584 : if (btreelist) {
1097 : 7 : btreeitem->child_rootbid = bid_new;
1098 : : btreeitem = (struct btreelist_item *)
1099 : 7 : mempool_alloc(sizeof(struct btreelist_item));
1100 : 7 : list_push_back(btreelist, &btreeitem->e);
1101 : 7 : btree = &btreeitem->btree;
1102 : : }
1103 : :
1104 : : // fetch sub-tree
1105 : : r = btree_init_from_bid(btree, trie->btreeblk_handle, trie->btree_blk_ops,
1106 : 3705584 : trie->btree_kv_ops, trie->btree_nodesize, bid_new);
1107 [ - + ]: 3703245 : if (r != BTREE_RESULT_SUCCESS) {
1108 : 0 : return HBTRIE_RESULT_FAIL;
1109 : : }
1110 : 3703245 : btree->aux = trie->aux;
1111 : : } else {
1112 : : // this is offset of document (as it is)
1113 : : // read entire key
1114 : 1855396 : uint8_t *docrawkey = alca(uint8_t, HBTRIE_MAX_KEYLEN);
1115 : 1855396 : uint8_t *dockey = alca(uint8_t, HBTRIE_MAX_KEYLEN);
1116 : : uint32_t docrawkeylen, dockeylen;
1117 : : uint64_t offset;
1118 : : int docnchunk, diffchunkno;
1119 : :
1120 : : // get offset value from btree_value
1121 : 1855396 : offset = trie->btree_kv_ops->value2bid(btree_value);
1122 [ + + ]: 1854813 : if (!(flag & HBTRIE_PREFIX_MATCH_ONLY)) {
1123 : : // read entire key
1124 : 1354208 : docrawkeylen = trie->readkey(trie->doc_handle, offset, docrawkey);
1125 : 1355315 : dockeylen = _hbtrie_reform_key(trie, docrawkey, docrawkeylen, dockey);
1126 : :
1127 : : // find first different chunk
1128 : 1355312 : docnchunk = _get_nchunk(trie, dockey, dockeylen);
1129 : :
1130 [ + + ]: 1355333 : if (docnchunk == nchunk) {
1131 : : diffchunkno = _hbtrie_find_diff_chunk(trie, key,
1132 : 1355253 : dockey, curchunkno, nchunk);
1133 [ + + ]: 1355289 : if (diffchunkno == nchunk) {
1134 : : // success
1135 : 1355368 : memcpy(valuebuf, btree_value, trie->valuelen);
1136 : 1355368 : return HBTRIE_RESULT_SUCCESS;
1137 : : }
1138 : : }
1139 : 1 : return HBTRIE_RESULT_FAIL;
1140 : : } else {
1141 : : // just return value
1142 : 500605 : memcpy(valuebuf, btree_value, trie->valuelen);
1143 : 500605 : return HBTRIE_RESULT_SUCCESS;
1144 : : }
1145 : : }
1146 : : }
1147 : : }
1148 : :
1149 : 5627014 : return HBTRIE_RESULT_FAIL;
1150 : : }
1151 : :
1152 : 1354999 : hbtrie_result hbtrie_find(struct hbtrie *trie, void *rawkey,
1153 : : int rawkeylen, void *valuebuf)
1154 : : {
1155 : 1354999 : int nchunk = _get_nchunk_raw(trie, rawkey, rawkeylen);
1156 : 1355144 : uint8_t *key = alca(uint8_t, nchunk * trie->chunksize);
1157 : : int keylen;
1158 : :
1159 : 1355144 : keylen = _hbtrie_reform_key(trie, rawkey, rawkeylen, key);
1160 : 1355506 : return _hbtrie_find(trie, key, keylen, valuebuf, NULL, 0x0);
1161 : : }
1162 : :
1163 : 4271114 : hbtrie_result hbtrie_find_offset(struct hbtrie *trie, void *rawkey,
1164 : : int rawkeylen, void *valuebuf)
1165 : : {
1166 : 4271114 : int nchunk = _get_nchunk_raw(trie, rawkey, rawkeylen);
1167 : 4271114 : uint8_t *key = alca(uint8_t, nchunk * trie->chunksize);
1168 : : int keylen;
1169 : :
1170 : 4271114 : keylen = _hbtrie_reform_key(trie, rawkey, rawkeylen, key);
1171 : : return _hbtrie_find(trie, key, keylen, valuebuf, NULL,
1172 : 4271114 : HBTRIE_PREFIX_MATCH_ONLY);
1173 : : }
1174 : :
1175 : 56 : hbtrie_result hbtrie_find_partial(struct hbtrie *trie, void *rawkey,
1176 : : int rawkeylen, void *valuebuf)
1177 : : {
1178 : 56 : int nchunk = _get_nchunk_raw(trie, rawkey, rawkeylen);
1179 : 56 : uint8_t *key = alca(uint8_t, nchunk * trie->chunksize);
1180 : : int keylen;
1181 : :
1182 : 56 : keylen = _hbtrie_reform_key(trie, rawkey, rawkeylen, key);
1183 : : return _hbtrie_find(trie, key, keylen, valuebuf, NULL,
1184 : 56 : HBTRIE_PARTIAL_MATCH);
1185 : : }
1186 : :
1187 : 22 : INLINE hbtrie_result _hbtrie_remove(struct hbtrie *trie,
1188 : : void *rawkey, int rawkeylen,
1189 : : uint8_t flag)
1190 : : {
1191 : 22 : int nchunk = _get_nchunk_raw(trie, rawkey, rawkeylen);
1192 : : int keylen;
1193 : 22 : uint8_t *key = alca(uint8_t, nchunk * trie->chunksize);
1194 : 22 : uint8_t *valuebuf = alca(uint8_t, trie->valuelen);
1195 : : hbtrie_result r;
1196 : : btree_result br;
1197 : : struct list btreelist;
1198 : : struct btreelist_item *btreeitem;
1199 : : struct list_elem *e;
1200 : :
1201 : 22 : keylen = _hbtrie_reform_key(trie, rawkey, rawkeylen, key);
1202 : :
1203 : 22 : r = _hbtrie_find(trie, key, keylen, valuebuf, &btreelist, flag);
1204 : :
1205 [ + + ]: 22 : if (r == HBTRIE_RESULT_SUCCESS) {
1206 : 17 : e = list_end(&btreelist);
1207 [ - + ]: 17 : assert(e);
1208 : :
1209 : 17 : btreeitem = _get_entry(e, struct btreelist_item, e);
1210 [ + + ][ + + ]: 17 : if ( (btreeitem->leaf && rawkeylen ==
[ + + ][ - + ]
1211 : : btreeitem->chunkno * trie->chunksize) ||
1212 : 16 : (!(btreeitem->leaf) && nchunk == btreeitem->chunkno) ) {
1213 : : // key is exactly same as b-tree's prefix .. remove from metasection
1214 : : struct hbtrie_meta hbmeta;
1215 : : struct btree_meta meta;
1216 : : hbmeta_opt opt;
1217 : 1 : uint8_t *buf = alca(uint8_t, trie->btree_nodesize);
1218 : :
1219 : 1 : meta.data = buf;
1220 : 1 : meta.size = btree_read_meta(&btreeitem->btree, meta.data);
1221 : 1 : _hbtrie_fetch_meta(trie, meta.size, &hbmeta, meta.data);
1222 : :
1223 [ + - ]: 1 : opt = (_is_leaf_btree(hbmeta.chunkno))?(HBMETA_LEAF):(HBMETA_NORMAL);
1224 : :
1225 : : // remove value from metasection
1226 : : _hbtrie_store_meta(
1227 : : trie, &meta.size, _get_chunkno(hbmeta.chunkno), opt,
1228 : 1 : hbmeta.prefix, hbmeta.prefix_len, NULL, buf);
1229 : 1 : btree_update_meta(&btreeitem->btree, &meta);
1230 : : } else {
1231 [ + + ]: 16 : if (btreeitem->leaf) {
1232 : : // leaf b-tree
1233 : 1 : uint8_t *k = alca(uint8_t, trie->chunksize);
1234 : 1 : _set_leaf_key(k, key + btreeitem->chunkno * trie->chunksize,
1235 : 1 : rawkeylen - btreeitem->chunkno * trie->chunksize);
1236 : 1 : br = btree_remove(&btreeitem->btree, k);
1237 : 1 : _free_leaf_key(k);
1238 : : } else {
1239 : : // normal b-tree
1240 : : br = btree_remove(&btreeitem->btree,
1241 : 15 : key + trie->chunksize * btreeitem->chunkno);
1242 : : }
1243 : : //assert(br != BTREE_RESULT_FAIL);
1244 [ - + ]: 16 : if (br == BTREE_RESULT_FAIL) r = HBTRIE_RESULT_FAIL;
1245 : : }
1246 : 17 : _hbtrie_btree_cascaded_update(trie, &btreelist, key, 1);
1247 : : } else {
1248 : : // key (to be removed) not found
1249 : : // no update occurred .. we don't need to update b-trees on the path
1250 : : // just free the btreelist
1251 : 5 : _hbtrie_free_btreelist(&btreelist);
1252 : : }
1253 : :
1254 : 22 : return r;
1255 : : }
1256 : :
1257 : 4 : hbtrie_result hbtrie_remove(struct hbtrie *trie,
1258 : : void *rawkey,
1259 : : int rawkeylen)
1260 : : {
1261 : 4 : return _hbtrie_remove(trie, rawkey, rawkeylen, 0x0);
1262 : : }
1263 : :
1264 : 18 : hbtrie_result hbtrie_remove_partial(struct hbtrie *trie,
1265 : : void *rawkey,
1266 : : int rawkeylen)
1267 : : {
1268 : : return _hbtrie_remove(trie, rawkey, rawkeylen,
1269 : 18 : HBTRIE_PARTIAL_MATCH);
1270 : : }
1271 : :
1272 : : struct _key_item {
1273 : : size_t keylen;
1274 : : void *key;
1275 : : void *value;
1276 : : struct list_elem le;
1277 : : };
1278 : :
1279 : 2 : void _hbtrie_extend_leaf_tree(
1280 : : struct hbtrie *trie,
1281 : : struct list *btreelist,
1282 : : struct btreelist_item *btreeitem,
1283 : : void *pre_str,
1284 : : size_t pre_str_len)
1285 : : {
1286 : : struct list keys;
1287 : : struct list_elem *e;
1288 : 2 : struct _key_item *item, *smallest = NULL;
1289 : : struct btree_iterator it;
1290 : : struct btree new_btree;
1291 : : struct btree_meta meta;
1292 : : struct hbtrie_meta hbmeta;
1293 : : btree_result br;
1294 : 2 : void *prefix = NULL, *meta_value = NULL;
1295 : 2 : uint8_t *key_str = alca(uint8_t, HBTRIE_MAX_KEYLEN);
1296 : 2 : uint8_t *key_buf = alca(uint8_t, trie->chunksize);
1297 : 2 : uint8_t *value_buf = alca(uint8_t, trie->valuelen);
1298 : 2 : uint8_t *buf = alca(uint8_t, trie->btree_nodesize);
1299 : 2 : size_t keylen, minchunkno = 0, chunksize;
1300 : :
1301 : 2 : chunksize = trie->chunksize;
1302 : :
1303 : : // fetch metadata
1304 : 2 : meta.data = buf;
1305 : 2 : meta.size = btree_read_meta(&btreeitem->btree, meta.data);
1306 : 2 : _hbtrie_fetch_meta(trie, meta.size, &hbmeta, meta.data);
1307 : :
1308 : : // scan all keys
1309 : 2 : list_init(&keys);
1310 : 2 : memset(key_buf, 0, chunksize);
1311 : 2 : minchunkno = 0;
1312 : :
1313 : 2 : br = btree_iterator_init(&btreeitem->btree, &it, NULL);
1314 [ + - ]: 21 : while (br == BTREE_RESULT_SUCCESS) {
1315 : : // get key
1316 [ + + ]: 21 : if ((br = btree_next(&it, key_buf, value_buf)) ==
1317 : 2 : BTREE_RESULT_FAIL) break;
1318 : :
1319 : 19 : _get_leaf_key(key_buf, key_str, &keylen);
1320 : 19 : _free_leaf_key(key_buf);
1321 : :
1322 : : // insert into list
1323 : 19 : item = (struct _key_item *)malloc(sizeof(struct _key_item));
1324 : :
1325 : 19 : item->key = (void *)malloc(keylen);
1326 : 19 : item->keylen = keylen;
1327 : 19 : memcpy(item->key, key_str, keylen);
1328 : :
1329 : 19 : item->value = (void *)malloc(trie->valuelen);
1330 : 19 : memcpy(item->value, value_buf, trie->valuelen);
1331 : :
1332 : 19 : list_push_back(&keys, &item->le);
1333 : :
1334 [ - + ]: 19 : if (hbmeta.value == NULL) {
1335 : : // check common prefix
1336 [ # # ]: 0 : if (prefix == NULL) {
1337 : : // initialize
1338 : 0 : prefix = item->key;
1339 : 0 : minchunkno = _l2c(trie, item->keylen);
1340 : : } else {
1341 : : // update the length of common prefix
1342 : : minchunkno = _hbtrie_find_diff_chunk(
1343 : : trie, prefix, item->key, 0,
1344 : 0 : MIN(_l2c(trie, item->keylen), minchunkno));
1345 : : }
1346 : :
1347 : : // update smallest (shortest) key
1348 [ # # ]: 0 : if (smallest == NULL) {
1349 : 0 : smallest = item;
1350 : : } else {
1351 [ # # ]: 0 : if (item->keylen < smallest->keylen)
1352 : 0 : smallest = item;
1353 : : }
1354 : : }
1355 : : }
1356 : 2 : btree_iterator_free(&it);
1357 : :
1358 : : // construct new (non-leaf) b-tree
1359 [ + - ]: 2 : if (hbmeta.value) {
1360 : : // insert tree's prefix into the list
1361 : 2 : item = (struct _key_item *)malloc(sizeof(struct _key_item));
1362 : :
1363 : 2 : item->key = NULL;
1364 : 2 : item->keylen = 0;
1365 : :
1366 : 2 : item->value = (void *)malloc(trie->valuelen);
1367 : 2 : memcpy(item->value, hbmeta.value, trie->valuelen);
1368 : :
1369 : 2 : list_push_back(&keys, &item->le);
1370 : :
1371 : 2 : meta_value = smallest = NULL;
1372 : : } else {
1373 [ # # ]: 0 : if (smallest) {
1374 [ # # # # ]: 0 : if (minchunkno > 0 &&
[ # # ]
1375 : 0 : _get_nchunk_raw(trie, smallest->key, smallest->keylen) ==
1376 : : minchunkno) {
1377 : 0 : meta_value = smallest->value;
1378 : : } else {
1379 : 0 : smallest = NULL;
1380 : : }
1381 : : }
1382 : : }
1383 : : _hbtrie_store_meta(
1384 : : trie, &meta.size, _get_chunkno(hbmeta.chunkno) + minchunkno,
1385 : 2 : HBMETA_NORMAL, prefix, minchunkno * chunksize, meta_value, buf);
1386 : :
1387 : : btree_init(&new_btree, trie->btreeblk_handle, trie->btree_blk_ops,
1388 : : trie->btree_kv_ops, trie->btree_nodesize, chunksize, trie->valuelen,
1389 : 2 : 0x0, &meta);
1390 : 2 : new_btree.aux = trie->aux;
1391 : :
1392 : : // reset BTREEITEM
1393 : 2 : btreeitem->btree = new_btree;
1394 : 2 : btreeitem->chunkno = _get_chunkno(hbmeta.chunkno) + minchunkno;
1395 : 2 : btreeitem->leaf = 0;
1396 : :
1397 : 2 : _hbtrie_btree_cascaded_update(trie, btreelist, pre_str, 1);
1398 : :
1399 : : // insert all keys
1400 : 2 : memcpy(key_str, pre_str, pre_str_len);
1401 : 2 : e = list_begin(&keys);
1402 [ + + ]: 23 : while (e) {
1403 : 21 : item = _get_entry(e, struct _key_item, le);
1404 [ + - ]: 21 : if (item != smallest) {
1405 [ + + ]: 21 : if (item->keylen > 0) {
1406 : 19 : memcpy(key_str + pre_str_len, item->key, item->keylen);
1407 : : }
1408 : : hbtrie_insert(trie, key_str, pre_str_len + item->keylen,
1409 : 21 : item->value, value_buf);
1410 : : }
1411 : :
1412 : 21 : e = list_remove(&keys, e);
1413 [ + + ]: 21 : if (item->key) {
1414 : 19 : free(item->key);
1415 : : }
1416 : 21 : free(item->value);
1417 : 21 : free(item);
1418 : : }
1419 : :
1420 : 2 : }
1421 : :
1422 : : // suppose that VALUE and OLDVALUE_OUT are based on the same endian in hb+trie
1423 : : #define HBTRIE_PARTIAL_UPDATE (0x1)
1424 : 8537245 : INLINE hbtrie_result _hbtrie_insert(struct hbtrie *trie,
1425 : : void *rawkey, int rawkeylen,
1426 : : void *value, void *oldvalue_out,
1427 : : uint8_t flag)
1428 : : {
1429 : : /*
1430 : : <insertion cases>
1431 : : 1. normal insert: there is no creation of new b-tree
1432 : : 2. replacing doc by new b-tree: a doc (which has same prefix) already exists
1433 : : 2-1. a new b-tree that has file offset to a doc in its metadata
1434 : : is created, and the other doc is inserted into the tree
1435 : : 2-2. two docs are inserted into the new b-tree
1436 : : 3. create new b-tree between existing b-trees: when prefix mismatches
1437 : : */
1438 : :
1439 : : int nchunk;
1440 : : int keylen;
1441 : : int prevchunkno, curchunkno;
1442 : 8537245 : int cpt_node = 0;
1443 : 8537245 : int leaf_cond = 0;
1444 : 8537245 : uint8_t *k = alca(uint8_t, trie->chunksize);
1445 : :
1446 : : struct list btreelist;
1447 : : //struct btree btree, btree_new;
1448 : : struct btreelist_item *btreeitem, *btreeitem_new;
1449 : 8537245 : hbtrie_result ret_result = HBTRIE_RESULT_SUCCESS;
1450 : : btree_result r;
1451 : : struct btree_kv_ops *kv_ops;
1452 : :
1453 : : struct hbtrie_meta hbmeta;
1454 : : struct btree_meta meta;
1455 : : hbmeta_opt opt;
1456 : : void *void_cmp;
1457 : :
1458 : 8537245 : nchunk = _get_nchunk_raw(trie, rawkey, rawkeylen);
1459 : :
1460 : 8537245 : uint8_t *key = alca(uint8_t, nchunk * trie->chunksize);
1461 : 8537245 : uint8_t *buf = alca(uint8_t, trie->btree_nodesize);
1462 : 8537245 : uint8_t *btree_value = alca(uint8_t, trie->valuelen);
1463 : : void *chunk, *chunk_new;
1464 : : bid_t bid_new, _bid;
1465 : :
1466 : 8537245 : meta.data = buf;
1467 : 8537245 : curchunkno = 0;
1468 : 8537245 : keylen = _hbtrie_reform_key(trie, rawkey, rawkeylen, key);
1469 : : (void)keylen;
1470 : :
1471 [ + + ]: 8537248 : if (trie->map) { // custom cmp functions exist
1472 [ + + ]: 4268035 : if (!memcmp(trie->last_map_chunk, key, trie->chunksize)) {
1473 : : // same custom function was used in the last call .. leaf b+tree
1474 : 9223 : leaf_cond = 1;
1475 : : } else {
1476 : : // get cmp function corresponding to the key
1477 : 4258812 : void_cmp = trie->map(key, (void *)trie);
1478 [ + + ]: 4258812 : if (void_cmp) { // custom cmp function matches .. turn on leaf b+tree mode
1479 : 50 : leaf_cond = 1;
1480 : 50 : memcpy(trie->last_map_chunk, key, trie->chunksize);
1481 : 50 : trie->aux = void_cmp; // set aux for _fdb_custom_cmp_wrap()
1482 : : }
1483 : : }
1484 : : }
1485 : :
1486 : 8537248 : list_init(&btreelist);
1487 : : // btreeitem for root btree
1488 : 8537241 : btreeitem = (struct btreelist_item*)mempool_alloc(sizeof(struct btreelist_item));
1489 : 8537241 : list_push_back(&btreelist, &btreeitem->e);
1490 : :
1491 [ + + ]: 8537255 : if (trie->root_bid == BLK_NOT_FOUND) {
1492 : : // create root b-tree
1493 : 285 : _hbtrie_store_meta(trie, &meta.size, 0, HBMETA_NORMAL, NULL, 0, NULL, buf);
1494 : : r = btree_init(
1495 : : &btreeitem->btree, trie->btreeblk_handle, trie->btree_blk_ops, trie->btree_kv_ops,
1496 : 285 : trie->btree_nodesize, trie->chunksize, trie->valuelen, 0x0, &meta);
1497 [ - + ]: 285 : if (r != BTREE_RESULT_SUCCESS) {
1498 : 0 : return HBTRIE_RESULT_FAIL;
1499 : : }
1500 : : } else {
1501 : : // read from root_bid
1502 : : r = btree_init_from_bid(
1503 : : &btreeitem->btree, trie->btreeblk_handle, trie->btree_blk_ops, trie->btree_kv_ops,
1504 : 8536970 : trie->btree_nodesize, trie->root_bid);
1505 [ - + ]: 8536936 : if (r != BTREE_RESULT_SUCCESS) {
1506 : 0 : return HBTRIE_RESULT_FAIL;
1507 : : }
1508 : : }
1509 : 8537221 : btreeitem->btree.aux = trie->aux;
1510 : :
1511 [ + - ]: 17087492 : while(curchunkno < nchunk){
1512 : : // get current chunk number
1513 : 17087492 : meta.size = btree_read_meta(&btreeitem->btree, meta.data);
1514 : 17087534 : _hbtrie_fetch_meta(trie, meta.size, &hbmeta, meta.data);
1515 : 17087691 : prevchunkno = curchunkno;
1516 [ + + ]: 17087691 : if (_is_leaf_btree(hbmeta.chunkno)) {
1517 : 9240 : cpt_node = 1;
1518 : 9240 : hbmeta.chunkno = _get_chunkno(hbmeta.chunkno);
1519 : 9240 : btreeitem->btree.kv_ops = trie->btree_leaf_kv_ops;
1520 : : }
1521 : 17087691 : btreeitem->chunkno = curchunkno = hbmeta.chunkno;
1522 : :
1523 : : //3 check whether there is skipped prefix
1524 [ + + ]: 17087691 : if (curchunkno - prevchunkno > 1) {
1525 : : // prefix comparison (find the first different chunk)
1526 : : int diffchunkno = _hbtrie_find_diff_chunk(trie, hbmeta.prefix,
1527 : 5717 : key + trie->chunksize * (prevchunkno+1),
1528 : 5717 : 0, curchunkno - (prevchunkno+1));
1529 [ + + ]: 5717 : if (diffchunkno < curchunkno - (prevchunkno+1)) {
1530 : : //3 3. create sub-tree between parent and child tree
1531 : :
1532 : : // metadata (prefix) update in btreeitem->btree
1533 : : int new_prefixlen = trie->chunksize *
1534 : 44 : (curchunkno - (prevchunkno+1) - (diffchunkno+1));
1535 : : // backup old prefix
1536 : 44 : int old_prefixlen = hbmeta.prefix_len;
1537 : 44 : uint8_t *old_prefix = alca(uint8_t, old_prefixlen);
1538 : 44 : memcpy(old_prefix, hbmeta.prefix, old_prefixlen);
1539 : :
1540 [ + + ]: 44 : if (new_prefixlen > 0) {
1541 : 2 : uint8_t *new_prefix = alca(uint8_t, new_prefixlen);
1542 : : memcpy(new_prefix,
1543 : : (uint8_t*)hbmeta.prefix +
1544 : : trie->chunksize * (diffchunkno + 1),
1545 : 2 : new_prefixlen);
1546 : : _hbtrie_store_meta(trie, &meta.size, curchunkno, HBMETA_NORMAL,
1547 : 2 : new_prefix, new_prefixlen, hbmeta.value, buf);
1548 : : }else{
1549 : : _hbtrie_store_meta(trie, &meta.size, curchunkno, HBMETA_NORMAL,
1550 : 42 : NULL, 0, hbmeta.value, buf);
1551 : : }
1552 : : // update metadata for old b-tree
1553 : 44 : btree_update_meta(&btreeitem->btree, &meta);
1554 : :
1555 : : // split prefix and create new sub-tree
1556 : : _hbtrie_store_meta(trie, &meta.size,
1557 : : prevchunkno + diffchunkno + 1,
1558 : : HBMETA_NORMAL, old_prefix,
1559 : 44 : diffchunkno * trie->chunksize, NULL, buf);
1560 : :
1561 : : // create new b-tree
1562 : : btreeitem_new = (struct btreelist_item *)
1563 : 44 : mempool_alloc(sizeof(struct btreelist_item));
1564 : 44 : btreeitem_new->chunkno = prevchunkno + diffchunkno + 1;
1565 : : r = btree_init(&btreeitem_new->btree, trie->btreeblk_handle,
1566 : : trie->btree_blk_ops, trie->btree_kv_ops,
1567 : : trie->btree_nodesize, trie->chunksize,
1568 : 44 : trie->valuelen, 0x0, &meta);
1569 [ - + ]: 44 : if (r != BTREE_RESULT_SUCCESS) {
1570 : 0 : return HBTRIE_RESULT_FAIL;
1571 : : }
1572 : 44 : btreeitem_new->btree.aux = trie->aux;
1573 : 44 : list_insert_before(&btreelist, &btreeitem->e, &btreeitem_new->e);
1574 : :
1575 : : // insert chunk for 'key'
1576 : 44 : chunk_new = key + (prevchunkno + diffchunkno + 1) * trie->chunksize;
1577 : 44 : r = btree_insert(&btreeitem_new->btree, chunk_new, value);
1578 [ - + ]: 44 : if (r == BTREE_RESULT_FAIL) {
1579 : 0 : return HBTRIE_RESULT_FAIL;
1580 : : }
1581 : : // insert chunk for existing btree
1582 : 44 : chunk_new = (uint8_t*)old_prefix + diffchunkno * trie->chunksize;
1583 : 44 : btreeitem_new->child_rootbid = bid_new = btreeitem->btree.root_bid;
1584 : : // set MSB
1585 : 44 : _bid = _endian_encode(bid_new);
1586 : 44 : _hbtrie_set_msb(trie, (void*)&_bid);
1587 : 44 : r = btree_insert(&btreeitem_new->btree, chunk_new, (void*)&_bid);
1588 [ - + ]: 44 : if (r == BTREE_RESULT_FAIL) {
1589 : 0 : return HBTRIE_RESULT_FAIL;
1590 : : }
1591 : :
1592 : 44 : break;
1593 : : }
1594 : : }
1595 : :
1596 : : //3 search b-tree using current chunk
1597 [ + + ][ + + ]: 17087647 : if ((cpt_node && rawkeylen == curchunkno * trie->chunksize) ||
[ + + ][ - + ]
1598 : : (!cpt_node && nchunk == curchunkno)) {
1599 : : // KEY is exactly same as tree's prefix .. insert into metasection
1600 : : _hbtrie_store_meta(
1601 : : trie, &meta.size, curchunkno, (cpt_node)?(HBMETA_LEAF):(HBMETA_NORMAL),
1602 : : hbmeta.prefix, (curchunkno-prevchunkno - 1)*trie->chunksize,
1603 [ + - ]: 1 : value, buf);
1604 : 1 : btree_update_meta(&btreeitem->btree, &meta);
1605 : 1 : break;
1606 : : } else {
1607 : 17087646 : chunk = key + curchunkno*trie->chunksize;
1608 [ + + ]: 17087646 : if (cpt_node) {
1609 : : // leaf b-tree
1610 : 9239 : _set_leaf_key(k, chunk, rawkeylen - curchunkno*trie->chunksize);
1611 : 9239 : r = btree_find(&btreeitem->btree, k, btree_value);
1612 : 9239 : _free_leaf_key(k);
1613 : : } else {
1614 : 17078407 : r = btree_find(&btreeitem->btree, chunk, btree_value);
1615 : : }
1616 : : }
1617 : :
1618 [ + + ]: 17087605 : if (r == BTREE_RESULT_FAIL) {
1619 : : //3 1. normal insert: same chunk does not exist -> just insert
1620 [ - + ]: 8034921 : if (flag & HBTRIE_PARTIAL_UPDATE) {
1621 : : // partial update doesn't allow inserting a new key
1622 : 0 : ret_result = HBTRIE_RESULT_FAIL;
1623 : 0 : break; // while loop
1624 : : }
1625 : :
1626 [ + + ]: 8034921 : if (cpt_node) {
1627 : : // leaf b-tree
1628 : 7638 : _set_leaf_key(k, chunk, rawkeylen - curchunkno*trie->chunksize);
1629 : 7638 : r = btree_insert(&btreeitem->btree, k, value);
1630 [ - + ]: 7638 : if (r == BTREE_RESULT_FAIL) {
1631 : 0 : _free_leaf_key(k);
1632 : 0 : ret_result = HBTRIE_RESULT_FAIL;
1633 : 0 : break; // while loop
1634 : : }
1635 : 7638 : _free_leaf_key(k);
1636 : :
1637 [ + + ]: 7637 : if (btreeitem->btree.height > trie->leaf_height_limit) {
1638 : : // height growth .. extend!
1639 : : _hbtrie_extend_leaf_tree(trie, &btreelist, btreeitem,
1640 : 2 : key, curchunkno * trie->chunksize);
1641 : 2 : return ret_result;
1642 : : }
1643 : : } else {
1644 : 8027283 : r = btree_insert(&btreeitem->btree, chunk, value);
1645 [ - + ]: 8027297 : if (r == BTREE_RESULT_FAIL) {
1646 : 0 : ret_result = HBTRIE_RESULT_FAIL;
1647 : : }
1648 : : }
1649 : 8034932 : break; // while loop
1650 : :
1651 : : } else {
1652 : : // same chunk already exists
1653 [ + + ][ + + ]: 9052684 : if (flag & HBTRIE_PARTIAL_UPDATE &&
1654 : : curchunkno + 1 == nchunk - 1) {
1655 : : // partial update mode & the last meaningful chunk
1656 : : // update the local btree value
1657 [ + - ]: 50 : if (oldvalue_out) {
1658 : 50 : memcpy(oldvalue_out, btree_value, trie->valuelen);
1659 : : }
1660 : : // assume that always normal b-tree
1661 : 50 : r = btree_insert(&btreeitem->btree, chunk, value);
1662 [ - + ]: 50 : if (r == BTREE_RESULT_FAIL) {
1663 : 0 : ret_result = HBTRIE_RESULT_FAIL;
1664 : : } else {
1665 : 50 : ret_result = HBTRIE_RESULT_UPDATE;
1666 : : }
1667 : 50 : break;
1668 : : }
1669 : :
1670 : : // check whether the value points to sub-tree or document
1671 : : // check MSB
1672 [ + + ]: 9052634 : if (_hbtrie_is_msb_set(trie, btree_value)) {
1673 : : // this is BID of b-tree node (by clearing MSB)
1674 : 8550405 : _hbtrie_clear_msb(trie, btree_value);
1675 : 8550405 : bid_new = trie->btree_kv_ops->value2bid(btree_value);
1676 : 8550433 : bid_new = _endian_decode(bid_new);
1677 : 8550433 : btreeitem->child_rootbid = bid_new;
1678 : : //3 traverse to the sub-tree
1679 : : // fetch sub-tree
1680 : : btreeitem = (struct btreelist_item*)
1681 : 8550433 : mempool_alloc(sizeof(struct btreelist_item));
1682 : :
1683 : : r = btree_init_from_bid(&btreeitem->btree,
1684 : : trie->btreeblk_handle,
1685 : : trie->btree_blk_ops,
1686 : : trie->btree_kv_ops,
1687 : 8550433 : trie->btree_nodesize, bid_new);
1688 [ - + ]: 8550410 : if (r == BTREE_RESULT_FAIL) {
1689 : 0 : ret_result = HBTRIE_RESULT_FAIL;
1690 : : }
1691 : 8550410 : btreeitem->btree.aux = trie->aux;
1692 : 8550410 : list_push_back(&btreelist, &btreeitem->e);
1693 : :
1694 : : } else {
1695 : : // this is offset of document (as it is)
1696 : : // create new sub-tree
1697 : :
1698 : : // read entire key
1699 : 502228 : uint8_t *docrawkey = alca(uint8_t, HBTRIE_MAX_KEYLEN);
1700 : 502228 : uint8_t *dockey = alca(uint8_t, HBTRIE_MAX_KEYLEN);
1701 : : uint32_t docrawkeylen, dockeylen, minrawkeylen;
1702 : : uint64_t offset;
1703 : : int docnchunk, minchunkno, newchunkno, diffchunkno;
1704 : :
1705 : : // get offset value from btree_value
1706 : 502228 : offset = trie->btree_kv_ops->value2bid(btree_value);
1707 : :
1708 : : // read entire key
1709 : 502228 : docrawkeylen = trie->readkey(trie->doc_handle, offset, docrawkey);
1710 : 502228 : dockeylen = _hbtrie_reform_key(trie, docrawkey, docrawkeylen, dockey);
1711 : :
1712 : : // find first different chunk
1713 : 502228 : docnchunk = _get_nchunk(trie, dockey, dockeylen);
1714 : :
1715 [ + + ][ + + ]: 502228 : if (trie->flag & HBTRIE_FLAG_COMPACT || leaf_cond) {
1716 : : // optimization mode
1717 : 1634 : newchunkno = curchunkno+1;
1718 : 1634 : minchunkno = MIN(_l2c(trie, rawkeylen) , _l2c(trie, docrawkeylen));
1719 [ - + ]: 1634 : minrawkeylen = MIN(rawkeylen, docrawkeylen);
1720 : : diffchunkno =
1721 : : _hbtrie_find_diff_chunk(trie, rawkey, docrawkey, curchunkno,
1722 : 1634 : minchunkno - ((minrawkeylen%trie->chunksize == 0)?(0):(1)));
1723 [ + + ][ + + ]: 1634 : if (rawkeylen == docrawkeylen && diffchunkno+1 == minchunkno) {
1724 [ + + ]: 1626 : if (!memcmp(rawkey, docrawkey, rawkeylen)) {
1725 : : // same key
1726 : 1601 : diffchunkno = minchunkno;
1727 : : }
1728 : : }
1729 : 1634 : opt = HBMETA_LEAF;
1730 : 1634 : kv_ops = trie->btree_leaf_kv_ops;
1731 : : } else {
1732 : : // original mode
1733 [ - + ]: 500594 : minchunkno = MIN(nchunk, docnchunk);
1734 : : newchunkno = diffchunkno =
1735 : 500594 : _hbtrie_find_diff_chunk(trie, key, dockey, curchunkno, minchunkno);
1736 : 500594 : opt = HBMETA_NORMAL;
1737 : 500594 : kv_ops = trie->btree_kv_ops;
1738 : : }
1739 : :
1740 : : // one key is substring of the other key
1741 [ + + ][ + + ]: 502228 : if (minchunkno == diffchunkno && docnchunk == nchunk) {
1742 : : //3 same key!! .. update the value
1743 : :
1744 [ + - ]: 500593 : if (oldvalue_out) memcpy(oldvalue_out, btree_value, trie->valuelen);
1745 [ + + ]: 500593 : if (cpt_node) {
1746 : : // leaf b-tree
1747 : 1601 : _set_leaf_key(k, chunk, rawkeylen - curchunkno*trie->chunksize);
1748 : 1601 : r = btree_insert(&btreeitem->btree, k, value);
1749 : 1601 : _free_leaf_key(k);
1750 : : } else {
1751 : : // normal b-tree
1752 : 498992 : r = btree_insert(&btreeitem->btree, chunk, value);
1753 : : }
1754 [ - + ]: 500593 : if (r == BTREE_RESULT_FAIL) {
1755 : 0 : ret_result = HBTRIE_RESULT_FAIL;
1756 : : } else {
1757 : 500593 : ret_result = HBTRIE_RESULT_UPDATE;
1758 : : }
1759 : 500593 : break;
1760 : :
1761 [ + + ][ + - ]: 1635 : }else if (minchunkno == diffchunkno && minchunkno == newchunkno) {
1762 : : //3 2-1. create sub-tree
1763 : : //4 which has file offset of one doc (sub-string) in its meta section,
1764 : : //4 and insert the other doc (super-string) into the tree
1765 : :
1766 : : void *key_long, *value_long;
1767 : : void *key_short, *value_short;
1768 : : size_t nchunk_long, rawkeylen_long;
1769 : :
1770 [ + - ]: 5 : if (docnchunk < nchunk) {
1771 : : // dockey is substring of key
1772 : 5 : key_short = dockey;
1773 : 5 : value_short = btree_value;
1774 : :
1775 : 5 : key_long = key;
1776 : 5 : value_long = value;
1777 : :
1778 : 5 : nchunk_long = nchunk;
1779 : 5 : rawkeylen_long = rawkeylen;
1780 : : }else{
1781 : : // key is substring of dockey
1782 : 0 : key_short = key;
1783 : 0 : value_short = value;
1784 : :
1785 : 0 : key_long = dockey;
1786 : 0 : value_long = btree_value;
1787 : :
1788 : 0 : nchunk_long = docnchunk;
1789 : 0 : rawkeylen_long = docrawkeylen;
1790 : : }
1791 : : (void)key_short;
1792 : : (void)nchunk_long;
1793 : :
1794 : : _hbtrie_store_meta(
1795 : : trie, &meta.size, newchunkno, opt,
1796 : 5 : key + trie->chunksize * (curchunkno+1),
1797 : 5 : (newchunkno - (curchunkno+1)) * trie->chunksize, value_short, buf);
1798 : :
1799 : 5 : btreeitem_new = (struct btreelist_item *)mempool_alloc(sizeof(struct btreelist_item));
1800 : 5 : btreeitem_new->chunkno = newchunkno;
1801 : : r = btree_init(
1802 : : &btreeitem_new->btree, trie->btreeblk_handle,
1803 : : trie->btree_blk_ops, kv_ops,
1804 : 5 : trie->btree_nodesize, trie->chunksize, trie->valuelen, 0x0, &meta);
1805 [ - + ]: 5 : if (r == BTREE_RESULT_FAIL) {
1806 : 0 : return HBTRIE_RESULT_FAIL;
1807 : : }
1808 : 5 : btreeitem_new->btree.aux = trie->aux;
1809 : :
1810 : 5 : list_push_back(&btreelist, &btreeitem_new->e);
1811 : :
1812 : : chunk_new = (uint8_t*)key_long +
1813 : 5 : newchunkno * trie->chunksize;
1814 : :
1815 [ + - ]: 5 : if (opt == HBMETA_LEAF) {
1816 : : // optimization mode
1817 : 5 : _set_leaf_key(k, chunk_new, rawkeylen_long - newchunkno*trie->chunksize);
1818 : 5 : r = btree_insert(&btreeitem_new->btree, k, value_long);
1819 [ - + ]: 5 : if (r == BTREE_RESULT_FAIL) {
1820 : 0 : ret_result = HBTRIE_RESULT_FAIL;
1821 : : }
1822 : 5 : _free_leaf_key(k);
1823 : : } else {
1824 : : // normal mode
1825 : 0 : r = btree_insert(&btreeitem_new->btree, chunk_new, value_long);
1826 [ # # ]: 0 : if (r == BTREE_RESULT_FAIL) {
1827 : 0 : ret_result = HBTRIE_RESULT_FAIL;
1828 : : }
1829 : 5 : }
1830 : :
1831 : : } else {
1832 : : //3 2-2. create sub-tree
1833 : : //4 and insert two docs into it
1834 : : _hbtrie_store_meta(
1835 : : trie, &meta.size, newchunkno, opt,
1836 : 1630 : key + trie->chunksize * (curchunkno+1),
1837 : 1630 : (newchunkno - (curchunkno+1)) * trie->chunksize, NULL, buf);
1838 : :
1839 : 1630 : btreeitem_new = (struct btreelist_item *)mempool_alloc(sizeof(struct btreelist_item));
1840 : 1630 : btreeitem_new->chunkno = newchunkno;
1841 : : r = btree_init(
1842 : : &btreeitem_new->btree, trie->btreeblk_handle,
1843 : : trie->btree_blk_ops, kv_ops,
1844 : 1630 : trie->btree_nodesize, trie->chunksize, trie->valuelen, 0x0, &meta);
1845 [ - + ]: 1630 : if (r == BTREE_RESULT_FAIL) {
1846 : 0 : ret_result = HBTRIE_RESULT_FAIL;
1847 : : }
1848 : 1630 : btreeitem_new->btree.aux = trie->aux;
1849 : :
1850 : 1630 : list_push_back(&btreelist, &btreeitem_new->e);
1851 : : // insert KEY
1852 : 1630 : chunk_new = key + newchunkno * trie->chunksize;
1853 [ + + ]: 1630 : if (opt == HBMETA_LEAF) {
1854 : : // optimization mode
1855 : 27 : _set_leaf_key(k, chunk_new, rawkeylen - newchunkno*trie->chunksize);
1856 : 27 : r = btree_insert(&btreeitem_new->btree, k, value);
1857 : 27 : _free_leaf_key(k);
1858 : : } else {
1859 : 1603 : r = btree_insert(&btreeitem_new->btree, chunk_new, value);
1860 : : }
1861 [ - + ]: 1630 : if (r == BTREE_RESULT_FAIL) {
1862 : 0 : ret_result = HBTRIE_RESULT_FAIL;
1863 : : }
1864 : :
1865 : : // insert the original DOCKEY
1866 : 1630 : chunk_new = dockey + newchunkno * trie->chunksize;
1867 [ + + ]: 1630 : if (opt == HBMETA_LEAF) {
1868 : : // optimization mode
1869 : 27 : _set_leaf_key(k, chunk_new, docrawkeylen - newchunkno*trie->chunksize);
1870 : 27 : r = btree_insert(&btreeitem_new->btree, k, btree_value);
1871 : 27 : _free_leaf_key(k);
1872 : : } else {
1873 : 1603 : r = btree_insert(&btreeitem_new->btree, chunk_new, btree_value);
1874 : : }
1875 [ - + ]: 1630 : if (r == BTREE_RESULT_FAIL) {
1876 : 0 : ret_result = HBTRIE_RESULT_FAIL;
1877 : : }
1878 : : }
1879 : :
1880 : : // update previous (parent) b-tree
1881 : 1635 : bid_new = btreeitem_new->btree.root_bid;
1882 : 1635 : btreeitem->child_rootbid = bid_new;
1883 : :
1884 : : // set MSB
1885 : 1635 : _bid = _endian_encode(bid_new);
1886 : 1635 : _hbtrie_set_msb(trie, (void *)&_bid);
1887 : : // ASSUMPTION: parent b-tree always MUST be non-leaf b-tree
1888 : 1635 : r = btree_insert(&btreeitem->btree, chunk, (void*)&_bid);
1889 [ - + ]: 1635 : if (r == BTREE_RESULT_FAIL) {
1890 : 0 : ret_result = HBTRIE_RESULT_FAIL;
1891 : : }
1892 : :
1893 : 1635 : break;
1894 : :
1895 : : } // MSB (b-tree or doc check)
1896 : : } // b-tree result success or fail
1897 : : } // while
1898 : :
1899 : 8537255 : _hbtrie_btree_cascaded_update(trie, &btreelist, key, 1);
1900 : :
1901 : 8537253 : return ret_result;
1902 : : }
1903 : :
1904 : 8537195 : hbtrie_result hbtrie_insert(struct hbtrie *trie,
1905 : : void *rawkey, int rawkeylen,
1906 : : void *value, void *oldvalue_out) {
1907 : 8537195 : return _hbtrie_insert(trie, rawkey, rawkeylen, value, oldvalue_out, 0x0);
1908 : : }
1909 : :
1910 : 50 : hbtrie_result hbtrie_insert_partial(struct hbtrie *trie,
1911 : : void *rawkey, int rawkeylen,
1912 : : void *value, void *oldvalue_out) {
1913 : : return _hbtrie_insert(trie, rawkey, rawkeylen,
1914 : 50 : value, oldvalue_out, HBTRIE_PARTIAL_UPDATE);
1915 : : }
|
