arbo/addbatch_test.go
addbatch_test.goRaw
1package arbo
2
3import (
4 "crypto/rand"
5 "encoding/hex"
6 "fmt"
7 "math/big"
8 "runtime"
9 "testing"
10 "time"
11
12 qt "github.com/frankban/quicktest"
13 "github.com/iden3/go-merkletree/db/leveldb"
14 "github.com/iden3/go-merkletree/db/memory"
15)
16
17var debug = true
18
19func debugTime(descr string, time1, time2 time.Duration) {
20 if debug {
21 fmt.Printf("%s was %f times faster than without AddBatch\n",
22 descr, float64(time1)/float64(time2))
23 }
24}
25
26func testInit(c *qt.C, n int) (*Tree, *Tree) {
27 tree1, err := NewTree(memory.NewMemoryStorage(), 100, HashFunctionPoseidon)
28 c.Assert(err, qt.IsNil)
29 defer tree1.db.Close()
30
31 tree2, err := NewTree(memory.NewMemoryStorage(), 100, HashFunctionPoseidon)
32 c.Assert(err, qt.IsNil)
33 defer tree2.db.Close()
34
35 // add the initial leafs to fill a bit the trees before calling the
36 // AddBatch method
37 for i := 0; i < n; i++ {
38 k := BigIntToBytes(big.NewInt(int64(i)))
39 v := BigIntToBytes(big.NewInt(int64(i * 2)))
40 if err := tree1.Add(k, v); err != nil {
41 c.Fatal(err)
42 }
43 if err := tree2.Add(k, v); err != nil {
44 c.Fatal(err)
45 }
46 }
47 return tree1, tree2
48}
49
50func TestAddBatchCaseA(t *testing.T) {
51 c := qt.New(t)
52
53 nLeafs := 1024
54
55 tree, err := NewTree(memory.NewMemoryStorage(), 100, HashFunctionPoseidon)
56 c.Assert(err, qt.IsNil)
57 defer tree.db.Close()
58
59 start := time.Now()
60 for i := 0; i < nLeafs; i++ {
61 k := BigIntToBytes(big.NewInt(int64(i)))
62 v := BigIntToBytes(big.NewInt(int64(i * 2)))
63 if err := tree.Add(k, v); err != nil {
64 t.Fatal(err)
65 }
66 }
67 time1 := time.Since(start)
68
69 tree2, err := NewTree(memory.NewMemoryStorage(), 100, HashFunctionPoseidon)
70 c.Assert(err, qt.IsNil)
71 defer tree2.db.Close()
72
73 var keys, values [][]byte
74 for i := 0; i < nLeafs; i++ {
75 k := BigIntToBytes(big.NewInt(int64(i)))
76 v := BigIntToBytes(big.NewInt(int64(i * 2)))
77 keys = append(keys, k)
78 values = append(values, v)
79 }
80 start = time.Now()
81 indexes, err := tree2.AddBatch(keys, values)
82 c.Assert(err, qt.IsNil)
83 time2 := time.Since(start)
84 debugTime("CASE A, AddBatch", time1, time2)
85 c.Check(len(indexes), qt.Equals, 0)
86
87 // check that both trees roots are equal
88 c.Check(tree2.Root(), qt.DeepEquals, tree.Root())
89}
90
91func TestAddBatchCaseANotPowerOf2(t *testing.T) {
92 c := qt.New(t)
93
94 nLeafs := 1027
95
96 tree, err := NewTree(memory.NewMemoryStorage(), 100, HashFunctionPoseidon)
97 c.Assert(err, qt.IsNil)
98 defer tree.db.Close()
99
100 for i := 0; i < nLeafs; i++ {
101 k := BigIntToBytes(big.NewInt(int64(i)))
102 v := BigIntToBytes(big.NewInt(int64(i * 2)))
103 if err := tree.Add(k, v); err != nil {
104 t.Fatal(err)
105 }
106 }
107
108 tree2, err := NewTree(memory.NewMemoryStorage(), 100, HashFunctionPoseidon)
109 c.Assert(err, qt.IsNil)
110 defer tree2.db.Close()
111
112 var keys, values [][]byte
113 for i := 0; i < nLeafs; i++ {
114 k := BigIntToBytes(big.NewInt(int64(i)))
115 v := BigIntToBytes(big.NewInt(int64(i * 2)))
116 keys = append(keys, k)
117 values = append(values, v)
118 }
119 indexes, err := tree2.AddBatch(keys, values)
120 c.Assert(err, qt.IsNil)
121 c.Check(len(indexes), qt.Equals, 0)
122
123 // check that both trees roots are equal
124 c.Check(tree2.Root(), qt.DeepEquals, tree.Root())
125}
126
127func randomBytes(n int) []byte {
128 b := make([]byte, n)
129 _, err := rand.Read(b)
130 if err != nil {
131 panic(err)
132 }
133 return b
134}
135
136func TestBuildTreeBottomUpSingleThread(t *testing.T) {
137 c := qt.New(t)
138 tree1, err := NewTree(memory.NewMemoryStorage(), 100, HashFunctionBlake2b)
139 c.Assert(err, qt.IsNil)
140 defer tree1.db.Close()
141
142 tree2, err := NewTree(memory.NewMemoryStorage(), 100, HashFunctionBlake2b)
143 c.Assert(err, qt.IsNil)
144 defer tree2.db.Close()
145
146 testvectorKeys := []string{
147 "1c7c2265e368314ca58ed2e1f33a326f1220e234a566d55c3605439dbe411642",
148 "2c9f0a578afff5bfa4e0992a43066460faaab9e8e500db0b16647c701cdb16bf",
149 "1c45cb31f2fa39ec7b9ebf0fad40e0b8296016b5ce8844ae06ff77226379d9a5",
150 "d8af98bbbb585129798ae54d5eabbc9d0561d583faf1663b3a3724d15bda4ec7",
151 }
152 var keys, values [][]byte
153 for i := 0; i < len(testvectorKeys); i++ {
154 key, err := hex.DecodeString(testvectorKeys[i])
155 c.Assert(err, qt.IsNil)
156 keys = append(keys, key)
157 values = append(values, []byte{0})
158 }
159
160 for i := 0; i < len(keys); i++ {
161 if err := tree1.Add(keys[i], values[i]); err != nil {
162 t.Fatal(err)
163 }
164 }
165
166 kvs, err := tree2.keysValuesToKvs(keys, values)
167 c.Assert(err, qt.IsNil)
168 sortKvs(kvs)
169
170 tree2.tx, err = tree2.db.NewTx()
171 c.Assert(err, qt.IsNil)
172 // indexes, err := tree2.buildTreeBottomUpSingleThread(kvs)
173 indexes, err := tree2.buildTreeBottomUp(4, kvs)
174 c.Assert(err, qt.IsNil)
175 // tree1.PrintGraphviz(nil)
176 // tree2.PrintGraphviz(nil)
177
178 c.Check(len(indexes), qt.Equals, 0)
179
180 // check that both trees roots are equal
181 c.Check(tree2.Root(), qt.DeepEquals, tree1.Root())
182 // 15b6a23945ae6c81342b7eb14e70fff50812dc8791cb15ec791eb08f91784139
183}
184
185func TestAddBatchCaseATestVector(t *testing.T) {
186 c := qt.New(t)
187 tree1, err := NewTree(memory.NewMemoryStorage(), 100, HashFunctionBlake2b)
188 c.Assert(err, qt.IsNil)
189 defer tree1.db.Close()
190
191 tree2, err := NewTree(memory.NewMemoryStorage(), 100, HashFunctionBlake2b)
192 c.Assert(err, qt.IsNil)
193 defer tree2.db.Close()
194
195 // leafs in 2nd level subtrees: [ 6, 0, 1, 1]
196 testvectorKeys := []string{
197 "1c7c2265e368314ca58ed2e1f33a326f1220e234a566d55c3605439dbe411642",
198 "2c9f0a578afff5bfa4e0992a43066460faaab9e8e500db0b16647c701cdb16bf",
199 "1c45cb31f2fa39ec7b9ebf0fad40e0b8296016b5ce8844ae06ff77226379d9a5",
200 "d8af98bbbb585129798ae54d5eabbc9d0561d583faf1663b3a3724d15bda4ec7",
201 }
202 var keys, values [][]byte
203 for i := 0; i < len(testvectorKeys); i++ {
204 key, err := hex.DecodeString(testvectorKeys[i])
205 c.Assert(err, qt.IsNil)
206 keys = append(keys, key)
207 values = append(values, []byte{0})
208 }
209
210 for i := 0; i < len(keys); i++ {
211 if err := tree1.Add(keys[i], values[i]); err != nil {
212 t.Fatal(err)
213 }
214 }
215
216 indexes, err := tree2.AddBatch(keys, values)
217 c.Assert(err, qt.IsNil)
218 // tree1.PrintGraphviz(nil)
219 // tree2.PrintGraphviz(nil)
220
221 c.Check(len(indexes), qt.Equals, 0)
222
223 // check that both trees roots are equal
224 // fmt.Println(hex.EncodeToString(tree1.Root()))
225 c.Check(tree2.Root(), qt.DeepEquals, tree1.Root())
226}
227
228func TestAddBatchCaseARandomKeys(t *testing.T) {
229 c := qt.New(t)
230
231 nLeafs := 8
232
233 tree1, err := NewTree(memory.NewMemoryStorage(), 100, HashFunctionBlake2b)
234 c.Assert(err, qt.IsNil)
235 defer tree1.db.Close()
236
237 tree2, err := NewTree(memory.NewMemoryStorage(), 100, HashFunctionBlake2b)
238 c.Assert(err, qt.IsNil)
239 defer tree2.db.Close()
240
241 var keys, values [][]byte
242 for i := 0; i < nLeafs; i++ {
243 keys = append(keys, randomBytes(32))
244 // values = append(values, randomBytes(32))
245 values = append(values, []byte{0})
246 // fmt.Println("K", hex.EncodeToString(keys[i]))
247 }
248
249 // TMP:
250 keys[0], _ = hex.DecodeString("1c7c2265e368314ca58ed2e1f33a326f1220e234a566d55c3605439dbe411642")
251 keys[1], _ = hex.DecodeString("2c9f0a578afff5bfa4e0992a43066460faaab9e8e500db0b16647c701cdb16bf")
252 keys[2], _ = hex.DecodeString("9cb87ec67e875c61390edcd1ab517f443591047709a4d4e45b0f9ed980857b8e")
253 keys[3], _ = hex.DecodeString("9b4e9e92e974a589f426ceeb4cb291dc24893513fecf8e8460992dcf52621d4d")
254 keys[4], _ = hex.DecodeString("1c45cb31f2fa39ec7b9ebf0fad40e0b8296016b5ce8844ae06ff77226379d9a5")
255 keys[5], _ = hex.DecodeString("d8af98bbbb585129798ae54d5eabbc9d0561d583faf1663b3a3724d15bda4ec7")
256 keys[6], _ = hex.DecodeString("3cd55dbfb8f975f20a0925dfbdabe79fa2d51dd0268afbb8ba6b01de9dfcdd3c")
257 keys[7], _ = hex.DecodeString("5d0a9d6d9f197c091bf054fac9cb60e11ec723d6610ed8578e617b4d46cb43d5")
258
259 for i := 0; i < len(keys); i++ {
260 if err := tree1.Add(keys[i], values[i]); err != nil {
261 t.Fatal(err)
262 }
263 }
264
265 indexes, err := tree2.AddBatch(keys, values)
266 c.Assert(err, qt.IsNil)
267 // tree1.PrintGraphviz(nil)
268 // tree2.PrintGraphviz(nil)
269
270 c.Check(len(indexes), qt.Equals, 0)
271
272 // check that both trees roots are equal
273 c.Check(tree2.Root(), qt.DeepEquals, tree1.Root())
274}
275
276func TestAddBatchCaseB(t *testing.T) {
277 c := qt.New(t)
278
279 nLeafs := 1024
280 initialNLeafs := 99 // TMP TODO use const minLeafsThreshold-1 once ready
281
282 tree1, tree2 := testInit(c, initialNLeafs)
283
284 start := time.Now()
285 for i := initialNLeafs; i < nLeafs; i++ {
286 k := BigIntToBytes(big.NewInt(int64(i)))
287 v := BigIntToBytes(big.NewInt(int64(i * 2)))
288 if err := tree1.Add(k, v); err != nil {
289 t.Fatal(err)
290 }
291 }
292 time1 := time.Since(start)
293
294 // prepare the key-values to be added
295 var keys, values [][]byte
296 for i := initialNLeafs; i < nLeafs; i++ {
297 k := BigIntToBytes(big.NewInt(int64(i)))
298 v := BigIntToBytes(big.NewInt(int64(i * 2)))
299 keys = append(keys, k)
300 values = append(values, v)
301 }
302 start = time.Now()
303 indexes, err := tree2.AddBatch(keys, values)
304 c.Assert(err, qt.IsNil)
305 time2 := time.Since(start)
306 debugTime("CASE B, AddBatch", time1, time2)
307 c.Check(len(indexes), qt.Equals, 0)
308
309 // check that both trees roots are equal
310 c.Check(tree2.Root(), qt.DeepEquals, tree1.Root())
311}
312
313func TestAddBatchCaseBRepeatedLeafs(t *testing.T) {
314 c := qt.New(t)
315
316 nLeafs := 1024
317 initialNLeafs := 99 // TMP TODO use const minLeafsThreshold-1 once ready
318
319 tree1, tree2 := testInit(c, initialNLeafs)
320
321 for i := initialNLeafs; i < nLeafs; i++ {
322 k := BigIntToBytes(big.NewInt(int64(i)))
323 v := BigIntToBytes(big.NewInt(int64(i * 2)))
324 if err := tree1.Add(k, v); err != nil {
325 t.Fatal(err)
326 }
327 }
328
329 // prepare the key-values to be added, including already existing keys
330 var keys, values [][]byte
331 for i := 0; i < nLeafs; i++ {
332 k := BigIntToBytes(big.NewInt(int64(i)))
333 v := BigIntToBytes(big.NewInt(int64(i * 2)))
334 keys = append(keys, k)
335 values = append(values, v)
336 }
337 indexes, err := tree2.AddBatch(keys, values)
338 c.Assert(err, qt.IsNil)
339 c.Check(len(indexes), qt.Equals, initialNLeafs)
340
341 // check that both trees roots are equal
342 c.Check(tree2.Root(), qt.DeepEquals, tree1.Root())
343}
344
345func TestCombineInKVSet(t *testing.T) {
346 c := qt.New(t)
347
348 var a, b, expected []kv
349 for i := 0; i < 10; i++ {
350 k := BigIntToBytes(big.NewInt(int64(i)))
351 kv := kv{k: k}
352 if i < 7 {
353 a = append(a, kv)
354 }
355 if i >= 4 {
356 b = append(b, kv)
357 }
358 expected = append(expected, kv)
359 }
360
361 r, invalids := combineInKVSet(a, b)
362 for i := 0; i < len(r); i++ {
363 c.Assert(r[i].k, qt.DeepEquals, expected[i].k)
364 }
365 c.Assert(len(invalids), qt.Equals, 7-4)
366}
367
368func TestGetKeysAtLevel(t *testing.T) {
369 c := qt.New(t)
370
371 tree, err := NewTree(memory.NewMemoryStorage(), 100, HashFunctionPoseidon)
372 c.Assert(err, qt.IsNil)
373 defer tree.db.Close()
374
375 for i := 0; i < 32; i++ {
376 k := BigIntToBytes(big.NewInt(int64(i)))
377 v := BigIntToBytes(big.NewInt(int64(i * 2)))
378 if err := tree.Add(k, v); err != nil {
379 t.Fatal(err)
380 }
381 }
382
383 keys, err := tree.getKeysAtLevel(2)
384 c.Assert(err, qt.IsNil)
385 expected := []string{
386 "a5d5f14fce7348e40751496cf25d107d91b0bd043435b9577d778a01f8aa6111",
387 "e9e8dd9b28a7f81d1ff34cb5cefc0146dd848b31031a427b79bdadb62e7f6910",
388 }
389 for i := 0; i < len(keys); i++ {
390 c.Assert(hex.EncodeToString(keys[i]), qt.Equals, expected[i])
391 }
392
393 keys, err = tree.getKeysAtLevel(3)
394 c.Assert(err, qt.IsNil)
395 expected = []string{
396 "9f12c13e52bca96ad4882a26558e48ab67ddd63e062b839207e893d961390f01",
397 "16d246dd6826ec7346c7328f11c4261facf82d4689f33263ff6e207956a77f21",
398 "4a22cc901c6337daa17a431fa20170684b710e5f551509511492ec24e81a8f2f",
399 "470d61abcbd154977bffc9a9ec5a8daff0caabcf2a25e8441f604c79daa0f82d",
400 }
401 for i := 0; i < len(keys); i++ {
402 c.Assert(hex.EncodeToString(keys[i]), qt.Equals, expected[i])
403 }
404
405 keys, err = tree.getKeysAtLevel(4)
406 c.Assert(err, qt.IsNil)
407 expected = []string{
408 "7a5d1c81f7b96318012de3417e53d4f13df5b1337718651cd29d0cb0a66edd20",
409 "3408213e4e844bdf3355eb8781c74e31626812898c2dbe141ed6d2c92256fc1c",
410 "dfd8a4d0b6954a3e9f3892e655b58d456eeedf9367f27dfdd9bc2dd6a5577312",
411 "9e99fbec06fb2a6725997c12c4995f62725eb4cce4808523a5a5e80cca64b007",
412 "0befa1e070231dbf4e8ff841c05878cdec823e0c09594c24910a248b3ff5a628",
413 "b7131b0a15c772a57005a4dc5d0d6dd4b3414f5d9ee7408ce5e86c5ab3520e04",
414 "6d1abe0364077846a56bab1deb1a04883eb796b74fe531a7676a9a370f83ab21",
415 "4270116394bede69cf9cd72069eca018238080380bef5de75be8dcbbe968e105",
416 }
417 for i := 0; i < len(keys); i++ {
418 c.Assert(hex.EncodeToString(keys[i]), qt.Equals, expected[i])
419 }
420}
421
422func TestSplitInBuckets(t *testing.T) {
423 c := qt.New(t)
424
425 nLeafs := 16
426 kvs := make([]kv, nLeafs)
427 for i := 0; i < nLeafs; i++ {
428 k := BigIntToBytes(big.NewInt(int64(i)))
429 v := BigIntToBytes(big.NewInt(int64(i * 2)))
430 keyPath := make([]byte, 32)
431 copy(keyPath[:], k)
432 kvs[i].pos = i
433 kvs[i].keyPath = k
434 kvs[i].k = k
435 kvs[i].v = v
436 }
437
438 // check keyToBucket results for 4 buckets & 8 keys
439 c.Assert(keyToBucket(kvs[0].k, 4), qt.Equals, 0)
440 c.Assert(keyToBucket(kvs[1].k, 4), qt.Equals, 2)
441 c.Assert(keyToBucket(kvs[2].k, 4), qt.Equals, 1)
442 c.Assert(keyToBucket(kvs[3].k, 4), qt.Equals, 3)
443 c.Assert(keyToBucket(kvs[4].k, 4), qt.Equals, 0)
444 c.Assert(keyToBucket(kvs[5].k, 4), qt.Equals, 2)
445 c.Assert(keyToBucket(kvs[6].k, 4), qt.Equals, 1)
446 c.Assert(keyToBucket(kvs[7].k, 4), qt.Equals, 3)
447
448 // check keyToBucket results for 8 buckets & 8 keys
449 c.Assert(keyToBucket(kvs[0].k, 8), qt.Equals, 0)
450 c.Assert(keyToBucket(kvs[1].k, 8), qt.Equals, 4)
451 c.Assert(keyToBucket(kvs[2].k, 8), qt.Equals, 2)
452 c.Assert(keyToBucket(kvs[3].k, 8), qt.Equals, 6)
453 c.Assert(keyToBucket(kvs[4].k, 8), qt.Equals, 1)
454 c.Assert(keyToBucket(kvs[5].k, 8), qt.Equals, 5)
455 c.Assert(keyToBucket(kvs[6].k, 8), qt.Equals, 3)
456 c.Assert(keyToBucket(kvs[7].k, 8), qt.Equals, 7)
457
458 buckets := splitInBuckets(kvs, 4)
459
460 expected := [][]string{
461 {
462 "00000000", // bucket 0
463 "08000000",
464 "04000000",
465 "0c000000",
466 },
467 {
468 "02000000", // bucket 1
469 "0a000000",
470 "06000000",
471 "0e000000",
472 },
473 {
474 "01000000", // bucket 2
475 "09000000",
476 "05000000",
477 "0d000000",
478 },
479 {
480 "03000000", // bucket 3
481 "0b000000",
482 "07000000",
483 "0f000000",
484 },
485 }
486
487 for i := 0; i < len(buckets); i++ {
488 sortKvs(buckets[i])
489 c.Assert(len(buckets[i]), qt.Equals, len(expected[i]))
490 for j := 0; j < len(buckets[i]); j++ {
491 c.Check(hex.EncodeToString(buckets[i][j].k[:4]), qt.Equals, expected[i][j])
492 }
493 }
494}
495
496func TestAddBatchCaseC(t *testing.T) {
497 c := qt.New(t)
498
499 nLeafs := 1024
500 initialNLeafs := 101 // TMP TODO use const minLeafsThreshold+1 once ready
501
502 tree1, tree2 := testInit(c, initialNLeafs)
503
504 start := time.Now()
505 for i := initialNLeafs; i < nLeafs; i++ {
506 k := BigIntToBytes(big.NewInt(int64(i)))
507 v := BigIntToBytes(big.NewInt(int64(i * 2)))
508 if err := tree1.Add(k, v); err != nil {
509 t.Fatal(err)
510 }
511 }
512 time1 := time.Since(start)
513
514 // prepare the key-values to be added
515 var keys, values [][]byte
516 for i := initialNLeafs; i < nLeafs; i++ {
517 k := BigIntToBytes(big.NewInt(int64(i)))
518 v := BigIntToBytes(big.NewInt(int64(i * 2)))
519 keys = append(keys, k)
520 values = append(values, v)
521 }
522 start = time.Now()
523 indexes, err := tree2.AddBatch(keys, values)
524 c.Assert(err, qt.IsNil)
525 time2 := time.Since(start)
526 debugTime("CASE C, AddBatch", time1, time2)
527 c.Check(len(indexes), qt.Equals, 0)
528
529 // check that both trees roots are equal
530 c.Check(tree2.Root(), qt.DeepEquals, tree1.Root())
531}
532
533func TestAddBatchCaseD(t *testing.T) {
534 c := qt.New(t)
535
536 nLeafs := 4096
537 initialNLeafs := 900
538
539 tree1, tree2 := testInit(c, initialNLeafs)
540
541 start := time.Now()
542 for i := initialNLeafs; i < nLeafs; i++ {
543 k := BigIntToBytes(big.NewInt(int64(i)))
544 v := BigIntToBytes(big.NewInt(int64(i * 2)))
545 if err := tree1.Add(k, v); err != nil {
546 t.Fatal(err)
547 }
548 }
549 time1 := time.Since(start)
550
551 // prepare the key-values to be added
552 var keys, values [][]byte
553 for i := initialNLeafs; i < nLeafs; i++ {
554 k := BigIntToBytes(big.NewInt(int64(i)))
555 v := BigIntToBytes(big.NewInt(int64(i * 2)))
556 keys = append(keys, k)
557 values = append(values, v)
558 }
559 start = time.Now()
560 indexes, err := tree2.AddBatch(keys, values)
561 c.Assert(err, qt.IsNil)
562 time2 := time.Since(start)
563 debugTime("CASE D, AddBatch", time1, time2)
564 c.Check(len(indexes), qt.Equals, 0)
565
566 // check that both trees roots are equal
567 c.Check(tree2.Root(), qt.DeepEquals, tree1.Root())
568}
569
570func TestAddBatchCaseE(t *testing.T) {
571 c := qt.New(t)
572
573 nLeafs := 4096
574 initialNLeafs := 900
575
576 tree1, _ := testInit(c, initialNLeafs)
577
578 start := time.Now()
579 for i := initialNLeafs; i < nLeafs; i++ {
580 k := BigIntToBytes(big.NewInt(int64(i)))
581 v := BigIntToBytes(big.NewInt(int64(i * 2)))
582 if err := tree1.Add(k, v); err != nil {
583 t.Fatal(err)
584 }
585 }
586 time1 := time.Since(start)
587
588 tree2, err := NewTree(memory.NewMemoryStorage(), 100, HashFunctionPoseidon)
589 c.Assert(err, qt.IsNil)
590 defer tree2.db.Close()
591
592 var keys, values [][]byte
593 // add the initial leafs to fill a bit the tree before calling the
594 // AddBatch method
595 for i := 0; i < initialNLeafs; i++ {
596 k := BigIntToBytes(big.NewInt(int64(i)))
597 v := BigIntToBytes(big.NewInt(int64(i * 2)))
598 // use only the keys of one bucket, store the not used ones for
599 // later
600 if i%4 != 0 {
601 keys = append(keys, k)
602 values = append(values, v)
603 continue
604 }
605 if err := tree2.Add(k, v); err != nil {
606 t.Fatal(err)
607 }
608 }
609
610 for i := initialNLeafs; i < nLeafs; i++ {
611 k := BigIntToBytes(big.NewInt(int64(i)))
612 v := BigIntToBytes(big.NewInt(int64(i * 2)))
613 keys = append(keys, k)
614 values = append(values, v)
615 }
616 start = time.Now()
617 indexes, err := tree2.AddBatch(keys, values)
618 c.Assert(err, qt.IsNil)
619 time2 := time.Since(start)
620 debugTime("CASE E, AddBatch", time1, time2)
621 c.Check(len(indexes), qt.Equals, 0)
622
623 // check that both trees roots are equal
624 c.Check(tree2.Root(), qt.DeepEquals, tree1.Root())
625}
626
627func TestFlp2(t *testing.T) {
628 c := qt.New(t)
629 c.Assert(flp2(31), qt.Equals, 16)
630 c.Assert(flp2(32), qt.Equals, 32)
631 c.Assert(flp2(33), qt.Equals, 32)
632 c.Assert(flp2(63), qt.Equals, 32)
633 c.Assert(flp2(64), qt.Equals, 64)
634 c.Assert(flp2(9000), qt.Equals, 8192)
635}
636
637func TestAddBatchBench(t *testing.T) {
638 nLeafs := 50_000
639 fmt.Printf("TestAddBatchBench\n nCPU: %d, nLeafs: %d, hash: Blake2b, db: leveldb\n",
640 runtime.NumCPU(), nLeafs)
641
642 // prepare inputs
643 var ks, vs [][]byte
644 for i := 0; i < nLeafs; i++ {
645 k := randomBytes(32)
646 v := randomBytes(32)
647 ks = append(ks, k)
648 vs = append(vs, v)
649 }
650
651 benchAdd(t, ks, vs)
652
653 benchAddBatch(t, ks, vs)
654}
655
656func benchAdd(t *testing.T, ks, vs [][]byte) {
657 c := qt.New(t)
658
659 dbDir := t.TempDir()
660 storage, err := leveldb.NewLevelDbStorage(dbDir, false)
661 c.Assert(err, qt.IsNil)
662 tree, err := NewTree(storage, 140, HashFunctionBlake2b)
663 c.Assert(err, qt.IsNil)
664
665 start := time.Now()
666 for i := 0; i < len(ks); i++ {
667 err = tree.Add(ks[i], vs[i])
668 c.Assert(err, qt.IsNil)
669 }
670 printRes(" Add loop", time.Since(start))
671}
672
673func benchAddBatch(t *testing.T, ks, vs [][]byte) {
674 c := qt.New(t)
675
676 dbDir := t.TempDir()
677 storage, err := leveldb.NewLevelDbStorage(dbDir, false)
678 c.Assert(err, qt.IsNil)
679 tree, err := NewTree(storage, 140, HashFunctionBlake2b)
680 c.Assert(err, qt.IsNil)
681
682 start := time.Now()
683 invalids, err := tree.AddBatch(ks, vs)
684 printRes(" AddBatch", time.Since(start))
685 c.Assert(err, qt.IsNil)
686 c.Assert(len(invalids), qt.Equals, 0)
687}
688
689func printRes(name string, duration time.Duration) {
690 if debug {
691 fmt.Printf(" %s: %s \n", name, duration)
692 }
693}
694
695// func printLeafs(name string, t *Tree) {
696// w := bytes.NewBufferString("")
697//
698// err := t.Iterate(func(k, v []byte) {
699// if v[0] != PrefixValueLeaf {
700// return
701// }
702// leafK, _ := readLeafValue(v)
703// fmt.Fprintf(w, hex.EncodeToString(leafK[:4])+"\n")
704// })
705// if err != nil {
706// panic(err)
707// }
708// err = ioutil.WriteFile(name, w.Bytes(), 0644)
709// if err != nil {
710// panic(err)
711// }
712//
713// }
714
715// func TestComputeCosts(t *testing.T) {
716// fmt.Println(computeSimpleAddCost(10))
717// fmt.Println(computeBottomUpAddCost(10))
718//
719// fmt.Println(computeSimpleAddCost(1024))
720// fmt.Println(computeBottomUpAddCost(1024))
721// }
722
723// TODO test tree with nLeafs > minLeafsThreshold, but that at level L, there is
724// less keys than nBuckets (so CASE C could be applied if first few leafs are
725// added to balance the tree)
726
727// TODO test adding batch with repeated keys in the batch
728// TODO test adding batch with multiple invalid keys