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