1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 package btree
16
17 import (
18 "flag"
19 "fmt"
20 "math/rand"
21 "reflect"
22 "sort"
23 "sync"
24 "testing"
25 "time"
26 )
27
28 func init() {
29 seed := time.Now().Unix()
30 fmt.Println(seed)
31 rand.Seed(seed)
32 }
33
34
35 func perm(n int) (out []Item) {
36 for _, v := range rand.Perm(n) {
37 out = append(out, Int(v))
38 }
39 return
40 }
41
42
43 func rang(n int) (out []Item) {
44 for i := 0; i < n; i++ {
45 out = append(out, Int(i))
46 }
47 return
48 }
49
50
51 func all(t *BTree) (out []Item) {
52 t.Ascend(func(a Item) bool {
53 out = append(out, a)
54 return true
55 })
56 return
57 }
58
59
60 func rangrev(n int) (out []Item) {
61 for i := n - 1; i >= 0; i-- {
62 out = append(out, Int(i))
63 }
64 return
65 }
66
67
68 func allrev(t *BTree) (out []Item) {
69 t.Descend(func(a Item) bool {
70 out = append(out, a)
71 return true
72 })
73 return
74 }
75
76 var btreeDegree = flag.Int("degree", 32, "B-Tree degree")
77
78 func TestBTree(t *testing.T) {
79 tr := New(*btreeDegree)
80 const treeSize = 10000
81 for i := 0; i < 10; i++ {
82 if min := tr.Min(); min != nil {
83 t.Fatalf("empty min, got %+v", min)
84 }
85 if max := tr.Max(); max != nil {
86 t.Fatalf("empty max, got %+v", max)
87 }
88 for _, item := range perm(treeSize) {
89 if x := tr.ReplaceOrInsert(item); x != nil {
90 t.Fatal("insert found item", item)
91 }
92 }
93 for _, item := range perm(treeSize) {
94 if !tr.Has(item) {
95 t.Fatal("has did not find item", item)
96 }
97 }
98 for _, item := range perm(treeSize) {
99 if x := tr.ReplaceOrInsert(item); x == nil {
100 t.Fatal("insert didn't find item", item)
101 }
102 }
103 if min, want := tr.Min(), Item(Int(0)); min != want {
104 t.Fatalf("min: want %+v, got %+v", want, min)
105 }
106 if max, want := tr.Max(), Item(Int(treeSize-1)); max != want {
107 t.Fatalf("max: want %+v, got %+v", want, max)
108 }
109 got := all(tr)
110 want := rang(treeSize)
111 if !reflect.DeepEqual(got, want) {
112 t.Fatalf("mismatch:\n got: %v\nwant: %v", got, want)
113 }
114
115 gotrev := allrev(tr)
116 wantrev := rangrev(treeSize)
117 if !reflect.DeepEqual(gotrev, wantrev) {
118 t.Fatalf("mismatch:\n got: %v\nwant: %v", got, want)
119 }
120
121 for _, item := range perm(treeSize) {
122 if x := tr.Delete(item); x == nil {
123 t.Fatalf("didn't find %v", item)
124 }
125 }
126 if got = all(tr); len(got) > 0 {
127 t.Fatalf("some left!: %v", got)
128 }
129 }
130 }
131
132 func ExampleBTree() {
133 tr := New(*btreeDegree)
134 for i := Int(0); i < 10; i++ {
135 tr.ReplaceOrInsert(i)
136 }
137 fmt.Println("len: ", tr.Len())
138 fmt.Println("get3: ", tr.Get(Int(3)))
139 fmt.Println("get100: ", tr.Get(Int(100)))
140 fmt.Println("del4: ", tr.Delete(Int(4)))
141 fmt.Println("del100: ", tr.Delete(Int(100)))
142 fmt.Println("replace5: ", tr.ReplaceOrInsert(Int(5)))
143 fmt.Println("replace100:", tr.ReplaceOrInsert(Int(100)))
144 fmt.Println("min: ", tr.Min())
145 fmt.Println("delmin: ", tr.DeleteMin())
146 fmt.Println("max: ", tr.Max())
147 fmt.Println("delmax: ", tr.DeleteMax())
148 fmt.Println("len: ", tr.Len())
149
150
151
152
153
154
155
156
157
158
159
160
161
162 }
163
164 func TestDeleteMin(t *testing.T) {
165 tr := New(3)
166 for _, v := range perm(100) {
167 tr.ReplaceOrInsert(v)
168 }
169 var got []Item
170 for v := tr.DeleteMin(); v != nil; v = tr.DeleteMin() {
171 got = append(got, v)
172 }
173 if want := rang(100); !reflect.DeepEqual(got, want) {
174 t.Fatalf("ascendrange:\n got: %v\nwant: %v", got, want)
175 }
176 }
177
178 func TestDeleteMax(t *testing.T) {
179 tr := New(3)
180 for _, v := range perm(100) {
181 tr.ReplaceOrInsert(v)
182 }
183 var got []Item
184 for v := tr.DeleteMax(); v != nil; v = tr.DeleteMax() {
185 got = append(got, v)
186 }
187
188 for i := 0; i < len(got)/2; i++ {
189 got[i], got[len(got)-i-1] = got[len(got)-i-1], got[i]
190 }
191 if want := rang(100); !reflect.DeepEqual(got, want) {
192 t.Fatalf("ascendrange:\n got: %v\nwant: %v", got, want)
193 }
194 }
195
196 func TestAscendRange(t *testing.T) {
197 tr := New(2)
198 for _, v := range perm(100) {
199 tr.ReplaceOrInsert(v)
200 }
201 var got []Item
202 tr.AscendRange(Int(40), Int(60), func(a Item) bool {
203 got = append(got, a)
204 return true
205 })
206 if want := rang(100)[40:60]; !reflect.DeepEqual(got, want) {
207 t.Fatalf("ascendrange:\n got: %v\nwant: %v", got, want)
208 }
209 got = got[:0]
210 tr.AscendRange(Int(40), Int(60), func(a Item) bool {
211 if a.(Int) > 50 {
212 return false
213 }
214 got = append(got, a)
215 return true
216 })
217 if want := rang(100)[40:51]; !reflect.DeepEqual(got, want) {
218 t.Fatalf("ascendrange:\n got: %v\nwant: %v", got, want)
219 }
220 }
221
222 func TestDescendRange(t *testing.T) {
223 tr := New(2)
224 for _, v := range perm(100) {
225 tr.ReplaceOrInsert(v)
226 }
227 var got []Item
228 tr.DescendRange(Int(60), Int(40), func(a Item) bool {
229 got = append(got, a)
230 return true
231 })
232 if want := rangrev(100)[39:59]; !reflect.DeepEqual(got, want) {
233 t.Fatalf("descendrange:\n got: %v\nwant: %v", got, want)
234 }
235 got = got[:0]
236 tr.DescendRange(Int(60), Int(40), func(a Item) bool {
237 if a.(Int) < 50 {
238 return false
239 }
240 got = append(got, a)
241 return true
242 })
243 if want := rangrev(100)[39:50]; !reflect.DeepEqual(got, want) {
244 t.Fatalf("descendrange:\n got: %v\nwant: %v", got, want)
245 }
246 }
247 func TestAscendLessThan(t *testing.T) {
248 tr := New(*btreeDegree)
249 for _, v := range perm(100) {
250 tr.ReplaceOrInsert(v)
251 }
252 var got []Item
253 tr.AscendLessThan(Int(60), func(a Item) bool {
254 got = append(got, a)
255 return true
256 })
257 if want := rang(100)[:60]; !reflect.DeepEqual(got, want) {
258 t.Fatalf("ascendrange:\n got: %v\nwant: %v", got, want)
259 }
260 got = got[:0]
261 tr.AscendLessThan(Int(60), func(a Item) bool {
262 if a.(Int) > 50 {
263 return false
264 }
265 got = append(got, a)
266 return true
267 })
268 if want := rang(100)[:51]; !reflect.DeepEqual(got, want) {
269 t.Fatalf("ascendrange:\n got: %v\nwant: %v", got, want)
270 }
271 }
272
273 func TestDescendLessOrEqual(t *testing.T) {
274 tr := New(*btreeDegree)
275 for _, v := range perm(100) {
276 tr.ReplaceOrInsert(v)
277 }
278 var got []Item
279 tr.DescendLessOrEqual(Int(40), func(a Item) bool {
280 got = append(got, a)
281 return true
282 })
283 if want := rangrev(100)[59:]; !reflect.DeepEqual(got, want) {
284 t.Fatalf("descendlessorequal:\n got: %v\nwant: %v", got, want)
285 }
286 got = got[:0]
287 tr.DescendLessOrEqual(Int(60), func(a Item) bool {
288 if a.(Int) < 50 {
289 return false
290 }
291 got = append(got, a)
292 return true
293 })
294 if want := rangrev(100)[39:50]; !reflect.DeepEqual(got, want) {
295 t.Fatalf("descendlessorequal:\n got: %v\nwant: %v", got, want)
296 }
297 }
298 func TestAscendGreaterOrEqual(t *testing.T) {
299 tr := New(*btreeDegree)
300 for _, v := range perm(100) {
301 tr.ReplaceOrInsert(v)
302 }
303 var got []Item
304 tr.AscendGreaterOrEqual(Int(40), func(a Item) bool {
305 got = append(got, a)
306 return true
307 })
308 if want := rang(100)[40:]; !reflect.DeepEqual(got, want) {
309 t.Fatalf("ascendrange:\n got: %v\nwant: %v", got, want)
310 }
311 got = got[:0]
312 tr.AscendGreaterOrEqual(Int(40), func(a Item) bool {
313 if a.(Int) > 50 {
314 return false
315 }
316 got = append(got, a)
317 return true
318 })
319 if want := rang(100)[40:51]; !reflect.DeepEqual(got, want) {
320 t.Fatalf("ascendrange:\n got: %v\nwant: %v", got, want)
321 }
322 }
323
324 func TestDescendGreaterThan(t *testing.T) {
325 tr := New(*btreeDegree)
326 for _, v := range perm(100) {
327 tr.ReplaceOrInsert(v)
328 }
329 var got []Item
330 tr.DescendGreaterThan(Int(40), func(a Item) bool {
331 got = append(got, a)
332 return true
333 })
334 if want := rangrev(100)[:59]; !reflect.DeepEqual(got, want) {
335 t.Fatalf("descendgreaterthan:\n got: %v\nwant: %v", got, want)
336 }
337 got = got[:0]
338 tr.DescendGreaterThan(Int(40), func(a Item) bool {
339 if a.(Int) < 50 {
340 return false
341 }
342 got = append(got, a)
343 return true
344 })
345 if want := rangrev(100)[:50]; !reflect.DeepEqual(got, want) {
346 t.Fatalf("descendgreaterthan:\n got: %v\nwant: %v", got, want)
347 }
348 }
349
350 const benchmarkTreeSize = 10000
351
352 func BenchmarkInsert(b *testing.B) {
353 b.StopTimer()
354 insertP := perm(benchmarkTreeSize)
355 b.StartTimer()
356 i := 0
357 for i < b.N {
358 tr := New(*btreeDegree)
359 for _, item := range insertP {
360 tr.ReplaceOrInsert(item)
361 i++
362 if i >= b.N {
363 return
364 }
365 }
366 }
367 }
368
369 func BenchmarkSeek(b *testing.B) {
370 b.StopTimer()
371 size := 100000
372 insertP := perm(size)
373 tr := New(*btreeDegree)
374 for _, item := range insertP {
375 tr.ReplaceOrInsert(item)
376 }
377 b.StartTimer()
378
379 for i := 0; i < b.N; i++ {
380 tr.AscendGreaterOrEqual(Int(i%size), func(i Item) bool { return false })
381 }
382 }
383
384 func BenchmarkDeleteInsert(b *testing.B) {
385 b.StopTimer()
386 insertP := perm(benchmarkTreeSize)
387 tr := New(*btreeDegree)
388 for _, item := range insertP {
389 tr.ReplaceOrInsert(item)
390 }
391 b.StartTimer()
392 for i := 0; i < b.N; i++ {
393 tr.Delete(insertP[i%benchmarkTreeSize])
394 tr.ReplaceOrInsert(insertP[i%benchmarkTreeSize])
395 }
396 }
397
398 func BenchmarkDeleteInsertCloneOnce(b *testing.B) {
399 b.StopTimer()
400 insertP := perm(benchmarkTreeSize)
401 tr := New(*btreeDegree)
402 for _, item := range insertP {
403 tr.ReplaceOrInsert(item)
404 }
405 tr = tr.Clone()
406 b.StartTimer()
407 for i := 0; i < b.N; i++ {
408 tr.Delete(insertP[i%benchmarkTreeSize])
409 tr.ReplaceOrInsert(insertP[i%benchmarkTreeSize])
410 }
411 }
412
413 func BenchmarkDeleteInsertCloneEachTime(b *testing.B) {
414 b.StopTimer()
415 insertP := perm(benchmarkTreeSize)
416 tr := New(*btreeDegree)
417 for _, item := range insertP {
418 tr.ReplaceOrInsert(item)
419 }
420 b.StartTimer()
421 for i := 0; i < b.N; i++ {
422 tr = tr.Clone()
423 tr.Delete(insertP[i%benchmarkTreeSize])
424 tr.ReplaceOrInsert(insertP[i%benchmarkTreeSize])
425 }
426 }
427
428 func BenchmarkDelete(b *testing.B) {
429 b.StopTimer()
430 insertP := perm(benchmarkTreeSize)
431 removeP := perm(benchmarkTreeSize)
432 b.StartTimer()
433 i := 0
434 for i < b.N {
435 b.StopTimer()
436 tr := New(*btreeDegree)
437 for _, v := range insertP {
438 tr.ReplaceOrInsert(v)
439 }
440 b.StartTimer()
441 for _, item := range removeP {
442 tr.Delete(item)
443 i++
444 if i >= b.N {
445 return
446 }
447 }
448 if tr.Len() > 0 {
449 panic(tr.Len())
450 }
451 }
452 }
453
454 func BenchmarkGet(b *testing.B) {
455 b.StopTimer()
456 insertP := perm(benchmarkTreeSize)
457 removeP := perm(benchmarkTreeSize)
458 b.StartTimer()
459 i := 0
460 for i < b.N {
461 b.StopTimer()
462 tr := New(*btreeDegree)
463 for _, v := range insertP {
464 tr.ReplaceOrInsert(v)
465 }
466 b.StartTimer()
467 for _, item := range removeP {
468 tr.Get(item)
469 i++
470 if i >= b.N {
471 return
472 }
473 }
474 }
475 }
476
477 func BenchmarkGetCloneEachTime(b *testing.B) {
478 b.StopTimer()
479 insertP := perm(benchmarkTreeSize)
480 removeP := perm(benchmarkTreeSize)
481 b.StartTimer()
482 i := 0
483 for i < b.N {
484 b.StopTimer()
485 tr := New(*btreeDegree)
486 for _, v := range insertP {
487 tr.ReplaceOrInsert(v)
488 }
489 b.StartTimer()
490 for _, item := range removeP {
491 tr = tr.Clone()
492 tr.Get(item)
493 i++
494 if i >= b.N {
495 return
496 }
497 }
498 }
499 }
500
501 type byInts []Item
502
503 func (a byInts) Len() int {
504 return len(a)
505 }
506
507 func (a byInts) Less(i, j int) bool {
508 return a[i].(Int) < a[j].(Int)
509 }
510
511 func (a byInts) Swap(i, j int) {
512 a[i], a[j] = a[j], a[i]
513 }
514
515 func BenchmarkAscend(b *testing.B) {
516 arr := perm(benchmarkTreeSize)
517 tr := New(*btreeDegree)
518 for _, v := range arr {
519 tr.ReplaceOrInsert(v)
520 }
521 sort.Sort(byInts(arr))
522 b.ResetTimer()
523 for i := 0; i < b.N; i++ {
524 j := 0
525 tr.Ascend(func(item Item) bool {
526 if item.(Int) != arr[j].(Int) {
527 b.Fatalf("mismatch: expected: %v, got %v", arr[j].(Int), item.(Int))
528 }
529 j++
530 return true
531 })
532 }
533 }
534
535 func BenchmarkDescend(b *testing.B) {
536 arr := perm(benchmarkTreeSize)
537 tr := New(*btreeDegree)
538 for _, v := range arr {
539 tr.ReplaceOrInsert(v)
540 }
541 sort.Sort(byInts(arr))
542 b.ResetTimer()
543 for i := 0; i < b.N; i++ {
544 j := len(arr) - 1
545 tr.Descend(func(item Item) bool {
546 if item.(Int) != arr[j].(Int) {
547 b.Fatalf("mismatch: expected: %v, got %v", arr[j].(Int), item.(Int))
548 }
549 j--
550 return true
551 })
552 }
553 }
554 func BenchmarkAscendRange(b *testing.B) {
555 arr := perm(benchmarkTreeSize)
556 tr := New(*btreeDegree)
557 for _, v := range arr {
558 tr.ReplaceOrInsert(v)
559 }
560 sort.Sort(byInts(arr))
561 b.ResetTimer()
562 for i := 0; i < b.N; i++ {
563 j := 100
564 tr.AscendRange(Int(100), arr[len(arr)-100], func(item Item) bool {
565 if item.(Int) != arr[j].(Int) {
566 b.Fatalf("mismatch: expected: %v, got %v", arr[j].(Int), item.(Int))
567 }
568 j++
569 return true
570 })
571 if j != len(arr)-100 {
572 b.Fatalf("expected: %v, got %v", len(arr)-100, j)
573 }
574 }
575 }
576
577 func BenchmarkDescendRange(b *testing.B) {
578 arr := perm(benchmarkTreeSize)
579 tr := New(*btreeDegree)
580 for _, v := range arr {
581 tr.ReplaceOrInsert(v)
582 }
583 sort.Sort(byInts(arr))
584 b.ResetTimer()
585 for i := 0; i < b.N; i++ {
586 j := len(arr) - 100
587 tr.DescendRange(arr[len(arr)-100], Int(100), func(item Item) bool {
588 if item.(Int) != arr[j].(Int) {
589 b.Fatalf("mismatch: expected: %v, got %v", arr[j].(Int), item.(Int))
590 }
591 j--
592 return true
593 })
594 if j != 100 {
595 b.Fatalf("expected: %v, got %v", len(arr)-100, j)
596 }
597 }
598 }
599 func BenchmarkAscendGreaterOrEqual(b *testing.B) {
600 arr := perm(benchmarkTreeSize)
601 tr := New(*btreeDegree)
602 for _, v := range arr {
603 tr.ReplaceOrInsert(v)
604 }
605 sort.Sort(byInts(arr))
606 b.ResetTimer()
607 for i := 0; i < b.N; i++ {
608 j := 100
609 k := 0
610 tr.AscendGreaterOrEqual(Int(100), func(item Item) bool {
611 if item.(Int) != arr[j].(Int) {
612 b.Fatalf("mismatch: expected: %v, got %v", arr[j].(Int), item.(Int))
613 }
614 j++
615 k++
616 return true
617 })
618 if j != len(arr) {
619 b.Fatalf("expected: %v, got %v", len(arr), j)
620 }
621 if k != len(arr)-100 {
622 b.Fatalf("expected: %v, got %v", len(arr)-100, k)
623 }
624 }
625 }
626 func BenchmarkDescendLessOrEqual(b *testing.B) {
627 arr := perm(benchmarkTreeSize)
628 tr := New(*btreeDegree)
629 for _, v := range arr {
630 tr.ReplaceOrInsert(v)
631 }
632 sort.Sort(byInts(arr))
633 b.ResetTimer()
634 for i := 0; i < b.N; i++ {
635 j := len(arr) - 100
636 k := len(arr)
637 tr.DescendLessOrEqual(arr[len(arr)-100], func(item Item) bool {
638 if item.(Int) != arr[j].(Int) {
639 b.Fatalf("mismatch: expected: %v, got %v", arr[j].(Int), item.(Int))
640 }
641 j--
642 k--
643 return true
644 })
645 if j != -1 {
646 b.Fatalf("expected: %v, got %v", -1, j)
647 }
648 if k != 99 {
649 b.Fatalf("expected: %v, got %v", 99, k)
650 }
651 }
652 }
653
654 const cloneTestSize = 10000
655
656 func cloneTest(t *testing.T, b *BTree, start int, p []Item, wg *sync.WaitGroup, trees *[]*BTree, lock *sync.Mutex) {
657 t.Logf("Starting new clone at %v", start)
658 lock.Lock()
659 *trees = append(*trees, b)
660 lock.Unlock()
661 for i := start; i < cloneTestSize; i++ {
662 b.ReplaceOrInsert(p[i])
663 if i%(cloneTestSize/5) == 0 {
664 wg.Add(1)
665 go cloneTest(t, b.Clone(), i+1, p, wg, trees, lock)
666 }
667 }
668 wg.Done()
669 }
670
671 func TestCloneConcurrentOperations(t *testing.T) {
672 b := New(*btreeDegree)
673 trees := []*BTree{}
674 p := perm(cloneTestSize)
675 var wg sync.WaitGroup
676 wg.Add(1)
677 go cloneTest(t, b, 0, p, &wg, &trees, &sync.Mutex{})
678 wg.Wait()
679 want := rang(cloneTestSize)
680 t.Logf("Starting equality checks on %d trees", len(trees))
681 for i, tree := range trees {
682 if !reflect.DeepEqual(want, all(tree)) {
683 t.Errorf("tree %v mismatch", i)
684 }
685 }
686 t.Log("Removing half from first half")
687 toRemove := rang(cloneTestSize)[cloneTestSize/2:]
688 for i := 0; i < len(trees)/2; i++ {
689 tree := trees[i]
690 wg.Add(1)
691 go func() {
692 for _, item := range toRemove {
693 tree.Delete(item)
694 }
695 wg.Done()
696 }()
697 }
698 wg.Wait()
699 t.Log("Checking all values again")
700 for i, tree := range trees {
701 var wantpart []Item
702 if i < len(trees)/2 {
703 wantpart = want[:cloneTestSize/2]
704 } else {
705 wantpart = want
706 }
707 if got := all(tree); !reflect.DeepEqual(wantpart, got) {
708 t.Errorf("tree %v mismatch, want %v got %v", i, len(want), len(got))
709 }
710 }
711 }
712
713 func BenchmarkDeleteAndRestore(b *testing.B) {
714 items := perm(16392)
715 b.ResetTimer()
716 b.Run(`CopyBigFreeList`, func(b *testing.B) {
717 fl := NewFreeList(16392)
718 tr := NewWithFreeList(*btreeDegree, fl)
719 for _, v := range items {
720 tr.ReplaceOrInsert(v)
721 }
722 b.ReportAllocs()
723 b.ResetTimer()
724 for i := 0; i < b.N; i++ {
725 dels := make([]Item, 0, tr.Len())
726 tr.Ascend(ItemIterator(func(b Item) bool {
727 dels = append(dels, b)
728 return true
729 }))
730 for _, del := range dels {
731 tr.Delete(del)
732 }
733
734 tr = NewWithFreeList(*btreeDegree, fl)
735 for _, v := range items {
736 tr.ReplaceOrInsert(v)
737 }
738 }
739 })
740 b.Run(`Copy`, func(b *testing.B) {
741 tr := New(*btreeDegree)
742 for _, v := range items {
743 tr.ReplaceOrInsert(v)
744 }
745 b.ReportAllocs()
746 b.ResetTimer()
747 for i := 0; i < b.N; i++ {
748 dels := make([]Item, 0, tr.Len())
749 tr.Ascend(ItemIterator(func(b Item) bool {
750 dels = append(dels, b)
751 return true
752 }))
753 for _, del := range dels {
754 tr.Delete(del)
755 }
756
757 tr = New(*btreeDegree)
758 for _, v := range items {
759 tr.ReplaceOrInsert(v)
760 }
761 }
762 })
763 b.Run(`ClearBigFreelist`, func(b *testing.B) {
764 fl := NewFreeList(16392)
765 tr := NewWithFreeList(*btreeDegree, fl)
766 for _, v := range items {
767 tr.ReplaceOrInsert(v)
768 }
769 b.ReportAllocs()
770 b.ResetTimer()
771 for i := 0; i < b.N; i++ {
772 tr.Clear(true)
773 for _, v := range items {
774 tr.ReplaceOrInsert(v)
775 }
776 }
777 })
778 b.Run(`Clear`, func(b *testing.B) {
779 tr := New(*btreeDegree)
780 for _, v := range items {
781 tr.ReplaceOrInsert(v)
782 }
783 b.ReportAllocs()
784 b.ResetTimer()
785 for i := 0; i < b.N; i++ {
786 tr.Clear(true)
787 for _, v := range items {
788 tr.ReplaceOrInsert(v)
789 }
790 }
791 })
792 }
793
View as plain text