arbo/addbatch.go
addbatch.goRaw
1package arbo
2
3import (
4 "bytes"
5 "fmt"
6 "math"
7 "runtime"
8 "sort"
9 "sync"
10
11 "github.com/iden3/go-merkletree/db"
12)
13
14/*
15
16AddBatch design
17===============
18
19
20CASE A: Empty Tree --> if tree is empty (root==0)
21=================================================
22- Build the full tree from bottom to top (from all the leaf to the root)
23
24
25CASE B: ALMOST CASE A, Almost empty Tree --> if Tree has numLeafs < minLeafsThreshold
26==============================================================================
27- Get the Leafs (key & value) (iterate the tree from the current root getting
28the leafs)
29- Create a new empty Tree
30- Do CASE A for the new Tree, giving the already existing key&values (leafs)
31from the original Tree + the new key&values to be added from the AddBatch call
32
33
34 R R
35 / \ / \
36 A * / \
37 / \ / \
38 B C * *
39 / | / \
40 / | / \
41 / | / \
42 L: A B G D
43 / \
44 / \
45 / \
46 C *
47 / \
48 / \
49 / \
50 ... ... (nLeafs < minLeafsThreshold)
51
52
53CASE C: ALMOST CASE B --> if Tree has few Leafs (but numLeafs>=minLeafsThreshold)
54==============================================================================
55- Use A, B, G, F as Roots of subtrees
56- Do CASE B for each subtree
57- Then go from L to the Root
58
59 R
60 / \
61 / \
62 / \
63 * *
64 / | / \
65 / | / \
66 / | / \
67L: A B G D
68 / \
69 / \
70 / \
71 C *
72 / \
73 / \
74 / \
75 ... ... (nLeafs >= minLeafsThreshold)
76
77
78
79CASE D: Already populated Tree
80==============================
81- Use A, B, C, D as subtree
82- Sort the Keys in Buckets that share the initial part of the path
83- For each subtree add there the new leafs
84
85 R
86 / \
87 / \
88 / \
89 * *
90 / | / \
91 / | / \
92 / | / \
93L: A B C D
94 /\ /\ / \ / \
95 ... ... ... ... ... ...
96
97
98CASE E: Already populated Tree Unbalanced
99=========================================
100- Need to fill M1 and M2, and then will be able to use CASE D
101 - Search for M1 & M2 in the inputed Keys
102 - Add M1 & M2 to the Tree
103 - From here can use CASE D
104
105 R
106 / \
107 / \
108 / \
109 * *
110 | \
111 | \
112 | \
113L: M1 * M2 * (where M1 and M2 are empty)
114 / | /
115 / | /
116 / | /
117 A * *
118 / \ | \
119 / \ | \
120 / \ | \
121 B * * C
122 / \ |\
123 ... ... | \
124 | \
125 D E
126
127
128
129Algorithm decision
130==================
131- if nLeafs==0 (root==0): CASE A
132- if nLeafs<minLeafsThreshold: CASE B
133- if nLeafs>=minLeafsThreshold && (nLeafs/nBuckets) < minLeafsThreshold: CASE C
134- else: CASE D & CASE E
135
136
137- Multiple tree.Add calls: O(n log n)
138 - Used in: cases A, B, C
139- Tree from bottom to top: O(log n)
140 - Used in: cases D, E
141
142*/
143
144const (
145 minLeafsThreshold = 100 // nolint:gomnd // TMP WIP this will be autocalculated
146)
147
148// AddBatch adds a batch of key-values to the Tree. Returns an array containing
149// the indexes of the keys failed to add.
150func (t *Tree) AddBatch(keys, values [][]byte) ([]int, error) {
151 t.updateAccessTime()
152 t.Lock()
153 defer t.Unlock()
154
155 vt, err := t.loadVT()
156 if err != nil {
157 return nil, err
158 }
159
160 invalids, err := vt.addBatch(keys, values)
161 if err != nil {
162 return nil, err
163 }
164
165 pairs, err := vt.computeHashes()
166 if err != nil {
167 return nil, err
168 }
169 t.root = vt.root.h
170
171 // store pairs in db
172 t.tx, err = t.db.NewTx()
173 if err != nil {
174 return nil, err
175 }
176 for i := 0; i < len(pairs); i++ {
177 if err := t.dbPut(pairs[i][0], pairs[i][1]); err != nil {
178 return nil, err
179 }
180 }
181
182 return t.finalizeAddBatch(len(keys), invalids)
183}
184
185// AddBatchOLD adds a batch of key-values to the Tree. Returns an array containing
186// the indexes of the keys failed to add.
187func (t *Tree) AddBatchOLD(keys, values [][]byte) ([]int, error) {
188 // TODO: support vaules=nil
189 t.updateAccessTime()
190 t.Lock()
191 defer t.Unlock()
192
193 kvs, err := t.keysValuesToKvs(keys, values)
194 if err != nil {
195 return nil, err
196 }
197
198 t.tx, err = t.db.NewTx()
199 if err != nil {
200 return nil, err
201 }
202
203 // if nCPU is not a power of two, cut at the highest power of two under
204 // nCPU
205 nCPU := flp2(runtime.NumCPU())
206 l := int(math.Log2(float64(nCPU)))
207 var invalids []int
208
209 // CASE A: if nLeafs==0 (root==0)
210 if bytes.Equal(t.root, t.emptyHash) {
211 invalids, err = t.caseA(nCPU, kvs)
212 if err != nil {
213 return nil, err
214 }
215
216 return t.finalizeAddBatch(len(keys), invalids)
217 }
218
219 // CASE B: if nLeafs<nBuckets
220 nLeafs, err := t.GetNLeafs()
221 if err != nil {
222 return nil, err
223 }
224 if nLeafs < minLeafsThreshold { // CASE B
225 invalids, err = t.caseB(nCPU, 0, kvs)
226 if err != nil {
227 return nil, err
228 }
229
230 return t.finalizeAddBatch(len(keys), invalids)
231 }
232
233 keysAtL, err := t.getKeysAtLevel(l + 1)
234 if err != nil {
235 return nil, err
236 }
237
238 // CASE C: if nLeafs>=minLeafsThreshold && (nLeafs/nBuckets) < minLeafsThreshold
239 // available parallelization, will need to be a power of 2 (2**n)
240 if nLeafs >= minLeafsThreshold &&
241 (nLeafs/nCPU) < minLeafsThreshold &&
242 len(keysAtL) == nCPU {
243 invalids, err = t.caseC(nCPU, l, keysAtL, kvs)
244 if err != nil {
245 return nil, err
246 }
247
248 return t.finalizeAddBatch(len(keys), invalids)
249 }
250
251 // CASE E
252 if len(keysAtL) != nCPU {
253 // CASE E: add one key at each bucket, and then do CASE D
254 buckets := splitInBuckets(kvs, nCPU)
255 kvs = []kv{}
256 for i := 0; i < len(buckets); i++ {
257 // add one leaf of the bucket, if there is an error when
258 // adding the k-v, try to add the next one of the bucket
259 // (until one is added)
260 var inserted int
261 for j := 0; j < len(buckets[i]); j++ {
262 if err := t.add(0, buckets[i][j].k, buckets[i][j].v); err == nil {
263 inserted = j
264 break
265 }
266 }
267
268 // put the buckets elements except the inserted one
269 kvs = append(kvs, buckets[i][:inserted]...)
270 kvs = append(kvs, buckets[i][inserted+1:]...)
271 }
272 keysAtL, err = t.getKeysAtLevel(l + 1)
273 if err != nil {
274 return nil, err
275 }
276 }
277
278 // CASE D
279 if len(keysAtL) == nCPU { // enter in CASE D if len(keysAtL)=nCPU, if not, CASE E
280 invalidsCaseD, err := t.caseD(nCPU, l, keysAtL, kvs)
281 if err != nil {
282 return nil, err
283 }
284 invalids = append(invalids, invalidsCaseD...)
285
286 return t.finalizeAddBatch(len(keys), invalids)
287 }
288
289 return nil, fmt.Errorf("UNIMPLEMENTED")
290}
291
292func (t *Tree) finalizeAddBatch(nKeys int, invalids []int) ([]int, error) {
293 // store root to db
294 if err := t.dbPut(dbKeyRoot, t.root); err != nil {
295 return nil, err
296 }
297
298 // update nLeafs
299 if err := t.incNLeafs(nKeys - len(invalids)); err != nil {
300 return nil, err
301 }
302
303 // commit db tx
304 if err := t.tx.Commit(); err != nil {
305 return nil, err
306 }
307 return invalids, nil
308}
309
310func (t *Tree) caseA(nCPU int, kvs []kv) ([]int, error) {
311 invalids, err := t.buildTreeFromLeafs(nCPU, kvs)
312 if err != nil {
313 return nil, err
314 }
315 return invalids, nil
316}
317
318func (t *Tree) caseB(nCPU, l int, kvs []kv) ([]int, error) {
319 // get already existing keys
320 aKs, aVs, err := t.getLeafs(t.root)
321 if err != nil {
322 return nil, err
323 }
324 aKvs, err := t.keysValuesToKvs(aKs, aVs)
325 if err != nil {
326 return nil, err
327 }
328 // add already existing key-values to the inputted key-values
329 // kvs = append(kvs, aKvs...)
330 kvs, invalids := combineInKVSet(aKvs, kvs)
331
332 // proceed with CASE A
333 sortKvs(kvs)
334
335 var invalids2 []int
336 if nCPU > 1 {
337 invalids2, err = t.buildTreeFromLeafs(nCPU, kvs)
338 if err != nil {
339 return nil, err
340 }
341 } else {
342 invalids2, err = t.buildTreeFromLeafsSingleThread(l, kvs)
343 if err != nil {
344 return nil, err
345 }
346 }
347 invalids = append(invalids, invalids2...)
348
349 return invalids, nil
350}
351
352func (t *Tree) caseC(nCPU, l int, keysAtL [][]byte, kvs []kv) ([]int, error) {
353 // 1. go down until level L (L=log2(nBuckets)): keysAtL
354
355 var excedents []kv
356 buckets := splitInBuckets(kvs, nCPU)
357
358 // 2. use keys at level L as roots of the subtrees under each one
359 subRoots := make([][]byte, nCPU)
360 dbgStatsPerBucket := make([]*dbgStats, nCPU)
361 txs := make([]db.Tx, nCPU)
362 var wg sync.WaitGroup
363 wg.Add(nCPU)
364 for i := 0; i < nCPU; i++ {
365 go func(cpu int) {
366 var err error
367 txs[cpu], err = t.db.NewTx()
368 if err != nil {
369 panic(err) // TODO WIP
370 }
371 if err := txs[cpu].Add(t.tx); err != nil {
372 panic(err) // TODO
373 }
374 bucketTree := Tree{tx: txs[cpu], db: t.db, maxLevels: t.maxLevels,
375 hashFunction: t.hashFunction, root: keysAtL[cpu],
376 emptyHash: t.emptyHash, dbg: newDbgStats()}
377
378 // 3. do CASE B (with 1 cpu) for each key at level L
379 _, err = bucketTree.caseB(1, l, buckets[cpu]) // TODO handle invalids
380 if err != nil {
381 panic(err) // TODO WIP
382 // return nil, err
383 }
384 subRoots[cpu] = bucketTree.root
385 dbgStatsPerBucket[cpu] = bucketTree.dbg
386 wg.Done()
387 }(i)
388 }
389 wg.Wait()
390
391 // merge buckets txs into Tree.tx
392 for i := 0; i < len(txs); i++ {
393 if err := t.tx.Add(txs[i]); err != nil {
394 return nil, err
395 }
396 }
397
398 // 4. go upFromKeys from the new roots of the subtrees
399 newRoot, err := t.upFromKeys(subRoots)
400 if err != nil {
401 return nil, err
402 }
403 t.root = newRoot
404
405 // add the key-values that have not been used yet
406 var invalids []int
407 for i := 0; i < len(excedents); i++ {
408 if err = t.add(0, excedents[i].k, excedents[i].v); err != nil {
409 invalids = append(invalids, excedents[i].pos)
410 }
411 }
412
413 for i := 0; i < len(dbgStatsPerBucket); i++ {
414 t.dbg.add(dbgStatsPerBucket[i])
415 }
416
417 return invalids, nil
418}
419
420func (t *Tree) caseD(nCPU, l int, keysAtL [][]byte, kvs []kv) ([]int, error) {
421 if nCPU == 1 { // CASE D, but with 1 cpu
422 var invalids []int
423 for i := 0; i < len(kvs); i++ {
424 if err := t.add(0, kvs[i].k, kvs[i].v); err != nil {
425 invalids = append(invalids, kvs[i].pos)
426 }
427 }
428 return invalids, nil
429 }
430
431 buckets := splitInBuckets(kvs, nCPU)
432
433 subRoots := make([][]byte, nCPU)
434 invalidsInBucket := make([][]int, nCPU)
435 dbgStatsPerBucket := make([]*dbgStats, nCPU)
436 txs := make([]db.Tx, nCPU)
437
438 var wg sync.WaitGroup
439 wg.Add(nCPU)
440 for i := 0; i < nCPU; i++ {
441 go func(cpu int) {
442 var err error
443 txs[cpu], err = t.db.NewTx()
444 if err != nil {
445 panic(err) // TODO WIP
446 }
447 // put already existing tx into txs[cpu], as txs[cpu]
448 // needs the pending key-values that are not in tree.db,
449 // but are in tree.tx
450 if err := txs[cpu].Add(t.tx); err != nil {
451 panic(err) // TODO WIP
452 }
453
454 bucketTree := Tree{tx: txs[cpu], db: t.db, maxLevels: t.maxLevels - l,
455 hashFunction: t.hashFunction, root: keysAtL[cpu],
456 emptyHash: t.emptyHash, dbg: newDbgStats()} // TODO bucketTree.dbg should be optional
457
458 for j := 0; j < len(buckets[cpu]); j++ {
459 if err = bucketTree.add(l, buckets[cpu][j].k, buckets[cpu][j].v); err != nil {
460 invalidsInBucket[cpu] = append(invalidsInBucket[cpu], buckets[cpu][j].pos)
461 }
462 }
463 subRoots[cpu] = bucketTree.root
464 dbgStatsPerBucket[cpu] = bucketTree.dbg
465 wg.Done()
466 }(i)
467 }
468 wg.Wait()
469
470 // merge buckets txs into Tree.tx
471 for i := 0; i < len(txs); i++ {
472 if err := t.tx.Add(txs[i]); err != nil {
473 return nil, err
474 }
475 }
476
477 newRoot, err := t.upFromKeys(subRoots)
478 if err != nil {
479 return nil, err
480 }
481 t.root = newRoot
482
483 var invalids []int
484 for i := 0; i < len(invalidsInBucket); i++ {
485 invalids = append(invalids, invalidsInBucket[i]...)
486 }
487
488 for i := 0; i < len(dbgStatsPerBucket); i++ {
489 t.dbg.add(dbgStatsPerBucket[i])
490 }
491
492 return invalids, nil
493}
494
495func splitInBuckets(kvs []kv, nBuckets int) [][]kv {
496 buckets := make([][]kv, nBuckets)
497 // 1. classify the keyvalues into buckets
498 for i := 0; i < len(kvs); i++ {
499 pair := kvs[i]
500
501 // bucketnum := keyToBucket(pair.k, nBuckets)
502 bucketnum := keyToBucket(pair.keyPath, nBuckets)
503 buckets[bucketnum] = append(buckets[bucketnum], pair)
504 }
505 return buckets
506}
507
508// TODO rename in a more 'real' name (calculate bucket from/for key)
509func keyToBucket(k []byte, nBuckets int) int {
510 nLevels := int(math.Log2(float64(nBuckets)))
511 b := make([]int, nBuckets)
512 for i := 0; i < nBuckets; i++ {
513 b[i] = i
514 }
515 r := b
516 mid := len(r) / 2 //nolint:gomnd
517 for i := 0; i < nLevels; i++ {
518 if int(k[i/8]&(1<<(i%8))) != 0 {
519 r = r[mid:]
520 mid = len(r) / 2 //nolint:gomnd
521 } else {
522 r = r[:mid]
523 mid = len(r) / 2 //nolint:gomnd
524 }
525 }
526 return r[0]
527}
528
529type kv struct {
530 pos int // original position in the array
531 keyPath []byte
532 k []byte
533 v []byte
534}
535
536// compareBytes compares byte slices where the bytes are compared from left to
537// right and each byte is compared by bit from right to left
538func compareBytes(a, b []byte) bool {
539 // WIP
540 for i := 0; i < len(a); i++ {
541 for j := 0; j < 8; j++ {
542 aBit := a[i] & (1 << j)
543 bBit := b[i] & (1 << j)
544 if aBit > bBit {
545 return false
546 } else if aBit < bBit {
547 return true
548 }
549 }
550 }
551 return false
552}
553
554// sortKvs sorts the kv by path
555func sortKvs(kvs []kv) {
556 sort.Slice(kvs, func(i, j int) bool {
557 return compareBytes(kvs[i].keyPath, kvs[j].keyPath)
558 })
559}
560
561func (t *Tree) keysValuesToKvs(ks, vs [][]byte) ([]kv, error) {
562 if len(ks) != len(vs) {
563 return nil, fmt.Errorf("len(keys)!=len(values) (%d!=%d)",
564 len(ks), len(vs))
565 }
566 kvs := make([]kv, len(ks))
567 for i := 0; i < len(ks); i++ {
568 keyPath := make([]byte, t.hashFunction.Len())
569 copy(keyPath[:], ks[i])
570 kvs[i].pos = i
571 kvs[i].keyPath = keyPath
572 kvs[i].k = ks[i]
573 kvs[i].v = vs[i]
574 }
575
576 return kvs, nil
577}
578
579/*
580func (t *Tree) kvsToKeysValues(kvs []kv) ([][]byte, [][]byte) {
581 ks := make([][]byte, len(kvs))
582 vs := make([][]byte, len(kvs))
583 for i := 0; i < len(kvs); i++ {
584 ks[i] = kvs[i].k
585 vs[i] = kvs[i].v
586 }
587 return ks, vs
588}
589*/
590
591// buildTreeFromLeafs splits the key-values into n Buckets (where n is the number
592// of CPUs), in parallel builds a subtree for each bucket, once all the subtrees
593// are built, uses the subtrees roots as keys for a new tree, which as result
594// will have the complete Tree build from bottom to up, where until the
595// log2(nCPU) level it has been computed in parallel.
596func (t *Tree) buildTreeFromLeafs(nCPU int, kvs []kv) ([]int, error) {
597 l := int(math.Log2(float64(nCPU)))
598 buckets := splitInBuckets(kvs, nCPU)
599
600 subRoots := make([][]byte, nCPU)
601 invalidsInBucket := make([][]int, nCPU)
602 dbgStatsPerBucket := make([]*dbgStats, nCPU)
603 txs := make([]db.Tx, nCPU)
604
605 var wg sync.WaitGroup
606 wg.Add(nCPU)
607 for i := 0; i < nCPU; i++ {
608 go func(cpu int) {
609 sortKvs(buckets[cpu])
610
611 var err error
612 txs[cpu], err = t.db.NewTx()
613 if err != nil {
614 panic(err) // TODO
615 }
616 if err := txs[cpu].Add(t.tx); err != nil {
617 panic(err) // TODO
618 }
619 bucketTree := Tree{tx: txs[cpu], db: t.db, maxLevels: t.maxLevels,
620 hashFunction: t.hashFunction, root: t.emptyHash,
621 emptyHash: t.emptyHash, dbg: newDbgStats()}
622
623 currInvalids, err := bucketTree.buildTreeFromLeafsSingleThread(l, buckets[cpu])
624 if err != nil {
625 panic(err) // TODO
626 }
627 invalidsInBucket[cpu] = currInvalids
628 subRoots[cpu] = bucketTree.root
629 dbgStatsPerBucket[cpu] = bucketTree.dbg
630 wg.Done()
631 }(i)
632 }
633 wg.Wait()
634
635 // merge buckets txs into Tree.tx
636 for i := 0; i < len(txs); i++ {
637 if err := t.tx.Add(txs[i]); err != nil {
638 return nil, err
639 }
640 }
641
642 newRoot, err := t.upFromKeys(subRoots)
643 if err != nil {
644 return nil, err
645 }
646 t.root = newRoot
647
648 var invalids []int
649 for i := 0; i < len(invalidsInBucket); i++ {
650 invalids = append(invalids, invalidsInBucket[i]...)
651 }
652
653 for i := 0; i < len(dbgStatsPerBucket); i++ {
654 t.dbg.add(dbgStatsPerBucket[i])
655 }
656
657 return invalids, err
658}
659
660// buildTreeFromLeafsSingleThread builds the tree with the given []kv from bottom
661// to the root
662func (t *Tree) buildTreeFromLeafsSingleThread(l int, kvsRaw []kv) ([]int, error) {
663 // TODO check that log2(len(leafs)) < t.maxLevels, if not, maxLevels
664 // would be reached and should return error
665 if len(kvsRaw) == 0 {
666 return nil, nil
667 }
668
669 vt := newVT(t.maxLevels, t.hashFunction)
670 if t.dbg != nil {
671 vt.params.dbg = newDbgStats()
672 }
673
674 for i := 0; i < len(kvsRaw); i++ {
675 if err := vt.add(l, kvsRaw[i].k, kvsRaw[i].v); err != nil {
676 return nil, err
677 }
678 }
679 pairs, err := vt.computeHashes()
680 if err != nil {
681 return nil, err
682 }
683
684 // store pairs in db
685 for i := 0; i < len(pairs); i++ {
686 if err := t.dbPut(pairs[i][0], pairs[i][1]); err != nil {
687 return nil, err
688 }
689 }
690 t.dbg.add(vt.params.dbg)
691
692 // set tree.root from the virtual tree root
693 t.root = vt.root.h
694
695 return nil, nil // TODO invalids
696}
697
698// keys & values must be sorted by path, and the array ks must be length
699// multiple of 2
700func (t *Tree) upFromKeys(ks [][]byte) ([]byte, error) {
701 if len(ks) == 1 {
702 return ks[0], nil
703 }
704
705 var rKs [][]byte
706 for i := 0; i < len(ks); i += 2 {
707 if bytes.Equal(ks[i], t.emptyHash) && bytes.Equal(ks[i+1], t.emptyHash) {
708 // when both sub keys are empty, the key is also empty
709 rKs = append(rKs, t.emptyHash)
710 continue
711 }
712 k, v, err := newIntermediate(t.hashFunction, ks[i], ks[i+1])
713 if err != nil {
714 return nil, err
715 }
716 // store k-v to db
717 if err = t.dbPut(k, v); err != nil {
718 return nil, err
719 }
720 rKs = append(rKs, k)
721 }
722 return t.upFromKeys(rKs)
723}
724
725func (t *Tree) getLeafs(root []byte) ([][]byte, [][]byte, error) {
726 var ks, vs [][]byte
727 err := t.iter(root, func(k, v []byte) {
728 if v[0] != PrefixValueLeaf {
729 return
730 }
731 leafK, leafV := ReadLeafValue(v)
732 ks = append(ks, leafK)
733 vs = append(vs, leafV)
734 })
735 return ks, vs, err
736}
737
738func (t *Tree) getKeysAtLevel(l int) ([][]byte, error) {
739 var keys [][]byte
740 err := t.iterWithStop(t.root, 0, func(currLvl int, k, v []byte) bool {
741 if currLvl == l && !bytes.Equal(k, t.emptyHash) {
742 keys = append(keys, k)
743 }
744 if currLvl >= l {
745 return true // to stop the iter from going down
746 }
747 return false
748 })
749
750 return keys, err
751}
752
753// flp2 computes the floor power of 2, the highest power of 2 under the given
754// value.
755func flp2(n int) int {
756 res := 0
757 for i := n; i >= 1; i-- {
758 if (i & (i - 1)) == 0 {
759 res = i
760 break
761 }
762 }
763 return res
764}
765
766// combineInKVSet combines two kv array in one single array without repeated
767// keys.
768func combineInKVSet(base, toAdd []kv) ([]kv, []int) {
769 // TODO this is a naive version, this will be implemented in a more
770 // efficient way or through maps, or through sorted binary search
771 r := base
772 var invalids []int
773 for i := 0; i < len(toAdd); i++ {
774 e := false
775 // check if toAdd[i] exists in the base set
776 for j := 0; j < len(base); j++ {
777 if bytes.Equal(toAdd[i].k, base[j].k) {
778 e = true
779 }
780 }
781 if !e {
782 r = append(r, toAdd[i])
783 } else {
784 invalids = append(invalids, toAdd[i].pos)
785 }
786 }
787 return r, invalids
788}
789
790// loadVT loads a new virtual tree (vt) from the current Tree, which contains
791// the same leafs.
792func (t *Tree) loadVT() (vt, error) {
793 vt := newVT(t.maxLevels, t.hashFunction)
794 vt.params.dbg = t.dbg
795 err := t.Iterate(func(k, v []byte) {
796 switch v[0] {
797 case PrefixValueEmpty:
798 case PrefixValueLeaf:
799 leafK, leafV := ReadLeafValue(v)
800 if err := vt.add(0, leafK, leafV); err != nil {
801 panic(err)
802 }
803 case PrefixValueIntermediate:
804 default:
805 }
806 })
807
808 return vt, err
809}
810
811// func computeSimpleAddCost(nLeafs int) int {
812// // nLvls 2^nLvls
813// nLvls := int(math.Log2(float64(nLeafs)))
814// return nLvls * int(math.Pow(2, float64(nLvls)))
815// }
816//
817// func computeFromLeafsAddCost(nLeafs int) int {
818// // 2^nLvls * 2 - 1
819// nLvls := int(math.Log2(float64(nLeafs)))
820// return (int(math.Pow(2, float64(nLvls))) * 2) - 1
821// }