cubefs

1
// Copyright 2014 Google Inc.
2
//
3
// Licensed under the Apache License, Version 2.0 (the "License");
4
// you may not use this file except in compliance with the License.
5
// You may obtain a copy of the License at
6
//
7
//     http://www.apache.org/licenses/LICENSE-2.0
8
//
9
// Unless required by applicable law or agreed to in writing, software
10
// distributed under the License is distributed on an "AS IS" BASIS,
11
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12
// See the License for the specific language governing permissions and
13
// limitations under the License.
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
// perm returns a random permutation of n Int items in the range [0, n).
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
// rang returns an ordered list of Int items in the range [0, n).
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
// all extracts all items from a tree in order as a slice.
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
// rangerev returns a reversed ordered list of Int items in the range [0, n).
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
// allrev extracts all items from a tree in reverse order as a slice.
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 x := tr.ReplaceOrInsert(item); x == nil {
95
				t.Fatal("insert didn't find item", item)
96
			}
97
		}
98
		if min, want := tr.Min(), Item(Int(0)); min != want {
99
			t.Fatalf("min: want %+v, got %+v", want, min)
100
		}
101
		if max, want := tr.Max(), Item(Int(treeSize-1)); max != want {
102
			t.Fatalf("max: want %+v, got %+v", want, max)
103
		}
104
		got := all(tr)
105
		want := rang(treeSize)
106
		if !reflect.DeepEqual(got, want) {
107
			t.Fatalf("mismatch:\n got: %v\nwant: %v", got, want)
108
		}
109

110
		gotrev := allrev(tr)
111
		wantrev := rangrev(treeSize)
112
		if !reflect.DeepEqual(gotrev, wantrev) {
113
			t.Fatalf("mismatch:\n got: %v\nwant: %v", got, want)
114
		}
115

116
		for _, item := range perm(treeSize) {
117
			if x := tr.Delete(item); x == nil {
118
				t.Fatalf("didn't find %v", item)
119
			}
120
		}
121
		if got = all(tr); len(got) > 0 {
122
			t.Fatalf("some left!: %v", got)
123
		}
124
	}
125
}
126

127
func ExampleBTree() {
128
	tr := New(*btreeDegree)
129
	for i := Int(0); i < 10; i++ {
130
		tr.ReplaceOrInsert(i)
131
	}
132
	fmt.Println("len:       ", tr.Len())
133
	fmt.Println("get3:      ", tr.Get(Int(3)))
134
	fmt.Println("get100:    ", tr.Get(Int(100)))
135
	fmt.Println("del4:      ", tr.Delete(Int(4)))
136
	fmt.Println("del100:    ", tr.Delete(Int(100)))
137
	fmt.Println("replace5:  ", tr.ReplaceOrInsert(Int(5)))
138
	fmt.Println("replace100:", tr.ReplaceOrInsert(Int(100)))
139
	fmt.Println("min:       ", tr.Min())
140
	fmt.Println("delmin:    ", tr.DeleteMin())
141
	fmt.Println("max:       ", tr.Max())
142
	fmt.Println("delmax:    ", tr.DeleteMax())
143
	fmt.Println("len:       ", tr.Len())
144
	// Output:
145
	// len:        10
146
	// get3:       3
147
	// get100:     <nil>
148
	// del4:       4
149
	// del100:     <nil>
150
	// replace5:   5
151
	// replace100: <nil>
152
	// min:        0
153
	// delmin:     0
154
	// max:        100
155
	// delmax:     100
156
	// len:        8
157
}
158

159
func TestDeleteMin(t *testing.T) {
160
	tr := New(3)
161
	for _, v := range perm(100) {
162
		tr.ReplaceOrInsert(v)
163
	}
164
	var got []Item
165
	for v := tr.DeleteMin(); v != nil; v = tr.DeleteMin() {
166
		got = append(got, v)
167
	}
168
	if want := rang(100); !reflect.DeepEqual(got, want) {
169
		t.Fatalf("ascendrange:\n got: %v\nwant: %v", got, want)
170
	}
171
}
172

173
func TestDeleteMax(t *testing.T) {
174
	tr := New(3)
175
	for _, v := range perm(100) {
176
		tr.ReplaceOrInsert(v)
177
	}
178
	var got []Item
179
	for v := tr.DeleteMax(); v != nil; v = tr.DeleteMax() {
180
		got = append(got, v)
181
	}
182
	// Reverse our list.
183
	for i := 0; i < len(got)/2; i++ {
184
		got[i], got[len(got)-i-1] = got[len(got)-i-1], got[i]
185
	}
186
	if want := rang(100); !reflect.DeepEqual(got, want) {
187
		t.Fatalf("ascendrange:\n got: %v\nwant: %v", got, want)
188
	}
189
}
190

191
func TestAscendRange(t *testing.T) {
192
	tr := New(2)
193
	for _, v := range perm(100) {
194
		tr.ReplaceOrInsert(v)
195
	}
196
	var got []Item
197
	tr.AscendRange(Int(40), Int(60), func(a Item) bool {
198
		got = append(got, a)
199
		return true
200
	})
201
	if want := rang(100)[40:60]; !reflect.DeepEqual(got, want) {
202
		t.Fatalf("ascendrange:\n got: %v\nwant: %v", got, want)
203
	}
204
	got = got[:0]
205
	tr.AscendRange(Int(40), Int(60), func(a Item) bool {
206
		if a.(Int) > 50 {
207
			return false
208
		}
209
		got = append(got, a)
210
		return true
211
	})
212
	if want := rang(100)[40:51]; !reflect.DeepEqual(got, want) {
213
		t.Fatalf("ascendrange:\n got: %v\nwant: %v", got, want)
214
	}
215
}
216

217
func TestDescendRange(t *testing.T) {
218
	tr := New(2)
219
	for _, v := range perm(100) {
220
		tr.ReplaceOrInsert(v)
221
	}
222
	var got []Item
223
	tr.DescendRange(Int(60), Int(40), func(a Item) bool {
224
		got = append(got, a)
225
		return true
226
	})
227
	if want := rangrev(100)[39:59]; !reflect.DeepEqual(got, want) {
228
		t.Fatalf("descendrange:\n got: %v\nwant: %v", got, want)
229
	}
230
	got = got[:0]
231
	tr.DescendRange(Int(60), Int(40), func(a Item) bool {
232
		if a.(Int) < 50 {
233
			return false
234
		}
235
		got = append(got, a)
236
		return true
237
	})
238
	if want := rangrev(100)[39:50]; !reflect.DeepEqual(got, want) {
239
		t.Fatalf("descendrange:\n got: %v\nwant: %v", got, want)
240
	}
241
}
242

243
func TestAscendLessThan(t *testing.T) {
244
	tr := New(*btreeDegree)
245
	for _, v := range perm(100) {
246
		tr.ReplaceOrInsert(v)
247
	}
248
	var got []Item
249
	tr.AscendLessThan(Int(60), func(a Item) bool {
250
		got = append(got, a)
251
		return true
252
	})
253
	if want := rang(100)[:60]; !reflect.DeepEqual(got, want) {
254
		t.Fatalf("ascendrange:\n got: %v\nwant: %v", got, want)
255
	}
256
	got = got[:0]
257
	tr.AscendLessThan(Int(60), func(a Item) bool {
258
		if a.(Int) > 50 {
259
			return false
260
		}
261
		got = append(got, a)
262
		return true
263
	})
264
	if want := rang(100)[:51]; !reflect.DeepEqual(got, want) {
265
		t.Fatalf("ascendrange:\n got: %v\nwant: %v", got, want)
266
	}
267
}
268

269
func TestDescendLessOrEqual(t *testing.T) {
270
	tr := New(*btreeDegree)
271
	for _, v := range perm(100) {
272
		tr.ReplaceOrInsert(v)
273
	}
274
	var got []Item
275
	tr.DescendLessOrEqual(Int(40), func(a Item) bool {
276
		got = append(got, a)
277
		return true
278
	})
279
	if want := rangrev(100)[59:]; !reflect.DeepEqual(got, want) {
280
		t.Fatalf("descendlessorequal:\n got: %v\nwant: %v", got, want)
281
	}
282
	got = got[:0]
283
	tr.DescendLessOrEqual(Int(60), func(a Item) bool {
284
		if a.(Int) < 50 {
285
			return false
286
		}
287
		got = append(got, a)
288
		return true
289
	})
290
	if want := rangrev(100)[39:50]; !reflect.DeepEqual(got, want) {
291
		t.Fatalf("descendlessorequal:\n got: %v\nwant: %v", got, want)
292
	}
293
}
294

295
func TestAscendGreaterOrEqual(t *testing.T) {
296
	tr := New(*btreeDegree)
297
	for _, v := range perm(100) {
298
		tr.ReplaceOrInsert(v)
299
	}
300
	var got []Item
301
	tr.AscendGreaterOrEqual(Int(40), func(a Item) bool {
302
		got = append(got, a)
303
		return true
304
	})
305
	if want := rang(100)[40:]; !reflect.DeepEqual(got, want) {
306
		t.Fatalf("ascendrange:\n got: %v\nwant: %v", got, want)
307
	}
308
	got = got[:0]
309
	tr.AscendGreaterOrEqual(Int(40), func(a Item) bool {
310
		if a.(Int) > 50 {
311
			return false
312
		}
313
		got = append(got, a)
314
		return true
315
	})
316
	if want := rang(100)[40:51]; !reflect.DeepEqual(got, want) {
317
		t.Fatalf("ascendrange:\n got: %v\nwant: %v", got, want)
318
	}
319
}
320

321
func TestDescendGreaterThan(t *testing.T) {
322
	tr := New(*btreeDegree)
323
	for _, v := range perm(100) {
324
		tr.ReplaceOrInsert(v)
325
	}
326
	var got []Item
327
	tr.DescendGreaterThan(Int(40), func(a Item) bool {
328
		got = append(got, a)
329
		return true
330
	})
331
	if want := rangrev(100)[:59]; !reflect.DeepEqual(got, want) {
332
		t.Fatalf("descendgreaterthan:\n got: %v\nwant: %v", got, want)
333
	}
334
	got = got[:0]
335
	tr.DescendGreaterThan(Int(40), func(a Item) bool {
336
		if a.(Int) < 50 {
337
			return false
338
		}
339
		got = append(got, a)
340
		return true
341
	})
342
	if want := rangrev(100)[:50]; !reflect.DeepEqual(got, want) {
343
		t.Fatalf("descendgreaterthan:\n got: %v\nwant: %v", got, want)
344
	}
345
}
346

347
const benchmarkTreeSize = 10000
348

349
func BenchmarkInsert(b *testing.B) {
350
	b.StopTimer()
351
	insertP := perm(benchmarkTreeSize)
352
	b.StartTimer()
353
	i := 0
354
	for i < b.N {
355
		tr := New(*btreeDegree)
356
		for _, item := range insertP {
357
			tr.ReplaceOrInsert(item)
358
			i++
359
			if i >= b.N {
360
				return
361
			}
362
		}
363
	}
364
}
365

366
func BenchmarkSeek(b *testing.B) {
367
	b.StopTimer()
368
	size := 100000
369
	insertP := perm(size)
370
	tr := New(*btreeDegree)
371
	for _, item := range insertP {
372
		tr.ReplaceOrInsert(item)
373
	}
374
	b.StartTimer()
375

376
	for i := 0; i < b.N; i++ {
377
		tr.AscendGreaterOrEqual(Int(i%size), func(i Item) bool { return false })
378
	}
379
}
380

381
func BenchmarkDeleteInsert(b *testing.B) {
382
	b.StopTimer()
383
	insertP := perm(benchmarkTreeSize)
384
	tr := New(*btreeDegree)
385
	for _, item := range insertP {
386
		tr.ReplaceOrInsert(item)
387
	}
388
	b.StartTimer()
389
	for i := 0; i < b.N; i++ {
390
		tr.Delete(insertP[i%benchmarkTreeSize])
391
		tr.ReplaceOrInsert(insertP[i%benchmarkTreeSize])
392
	}
393
}
394

395
func BenchmarkDeleteInsertCloneOnce(b *testing.B) {
396
	b.StopTimer()
397
	insertP := perm(benchmarkTreeSize)
398
	tr := New(*btreeDegree)
399
	for _, item := range insertP {
400
		tr.ReplaceOrInsert(item)
401
	}
402
	tr = tr.Clone()
403
	b.StartTimer()
404
	for i := 0; i < b.N; i++ {
405
		tr.Delete(insertP[i%benchmarkTreeSize])
406
		tr.ReplaceOrInsert(insertP[i%benchmarkTreeSize])
407
	}
408
}
409

410
func BenchmarkDeleteInsertCloneEachTime(b *testing.B) {
411
	b.StopTimer()
412
	insertP := perm(benchmarkTreeSize)
413
	tr := New(*btreeDegree)
414
	for _, item := range insertP {
415
		tr.ReplaceOrInsert(item)
416
	}
417
	b.StartTimer()
418
	for i := 0; i < b.N; i++ {
419
		tr = tr.Clone()
420
		tr.Delete(insertP[i%benchmarkTreeSize])
421
		tr.ReplaceOrInsert(insertP[i%benchmarkTreeSize])
422
	}
423
}
424

425
func BenchmarkDelete(b *testing.B) {
426
	b.StopTimer()
427
	insertP := perm(benchmarkTreeSize)
428
	removeP := perm(benchmarkTreeSize)
429
	b.StartTimer()
430
	i := 0
431
	for i < b.N {
432
		b.StopTimer()
433
		tr := New(*btreeDegree)
434
		for _, v := range insertP {
435
			tr.ReplaceOrInsert(v)
436
		}
437
		b.StartTimer()
438
		for _, item := range removeP {
439
			tr.Delete(item)
440
			i++
441
			if i >= b.N {
442
				return
443
			}
444
		}
445
		if tr.Len() > 0 {
446
			panic(tr.Len())
447
		}
448
	}
449
}
450

451
func BenchmarkGet(b *testing.B) {
452
	b.StopTimer()
453
	insertP := perm(benchmarkTreeSize)
454
	removeP := perm(benchmarkTreeSize)
455
	b.StartTimer()
456
	i := 0
457
	for i < b.N {
458
		b.StopTimer()
459
		tr := New(*btreeDegree)
460
		for _, v := range insertP {
461
			tr.ReplaceOrInsert(v)
462
		}
463
		b.StartTimer()
464
		for _, item := range removeP {
465
			tr.Get(item)
466
			i++
467
			if i >= b.N {
468
				return
469
			}
470
		}
471
	}
472
}
473

474
func BenchmarkGetCloneEachTime(b *testing.B) {
475
	b.StopTimer()
476
	insertP := perm(benchmarkTreeSize)
477
	removeP := perm(benchmarkTreeSize)
478
	b.StartTimer()
479
	i := 0
480
	for i < b.N {
481
		b.StopTimer()
482
		tr := New(*btreeDegree)
483
		for _, v := range insertP {
484
			tr.ReplaceOrInsert(v)
485
		}
486
		b.StartTimer()
487
		for _, item := range removeP {
488
			tr = tr.Clone()
489
			tr.Get(item)
490
			i++
491
			if i >= b.N {
492
				return
493
			}
494
		}
495
	}
496
}
497

498
type byInts []Item
499

500
func (a byInts) Len() int {
501
	return len(a)
502
}
503

504
func (a byInts) Less(i, j int) bool {
505
	return a[i].(Int) < a[j].(Int)
506
}
507

508
func (a byInts) Swap(i, j int) {
509
	a[i], a[j] = a[j], a[i]
510
}
511

512
func BenchmarkAscend(b *testing.B) {
513
	arr := perm(benchmarkTreeSize)
514
	tr := New(*btreeDegree)
515
	for _, v := range arr {
516
		tr.ReplaceOrInsert(v)
517
	}
518
	sort.Sort(byInts(arr))
519
	b.ResetTimer()
520
	for i := 0; i < b.N; i++ {
521
		j := 0
522
		tr.Ascend(func(item Item) bool {
523
			if item.(Int) != arr[j].(Int) {
524
				b.Fatalf("mismatch: expected: %v, got %v", arr[j].(Int), item.(Int))
525
			}
526
			j++
527
			return true
528
		})
529
	}
530
}
531

532
func BenchmarkDescend(b *testing.B) {
533
	arr := perm(benchmarkTreeSize)
534
	tr := New(*btreeDegree)
535
	for _, v := range arr {
536
		tr.ReplaceOrInsert(v)
537
	}
538
	sort.Sort(byInts(arr))
539
	b.ResetTimer()
540
	for i := 0; i < b.N; i++ {
541
		j := len(arr) - 1
542
		tr.Descend(func(item Item) bool {
543
			if item.(Int) != arr[j].(Int) {
544
				b.Fatalf("mismatch: expected: %v, got %v", arr[j].(Int), item.(Int))
545
			}
546
			j--
547
			return true
548
		})
549
	}
550
}
551

552
func BenchmarkAscendRange(b *testing.B) {
553
	arr := perm(benchmarkTreeSize)
554
	tr := New(*btreeDegree)
555
	for _, v := range arr {
556
		tr.ReplaceOrInsert(v)
557
	}
558
	sort.Sort(byInts(arr))
559
	b.ResetTimer()
560
	for i := 0; i < b.N; i++ {
561
		j := 100
562
		tr.AscendRange(Int(100), arr[len(arr)-100], func(item Item) bool {
563
			if item.(Int) != arr[j].(Int) {
564
				b.Fatalf("mismatch: expected: %v, got %v", arr[j].(Int), item.(Int))
565
			}
566
			j++
567
			return true
568
		})
569
		if j != len(arr)-100 {
570
			b.Fatalf("expected: %v, got %v", len(arr)-100, j)
571
		}
572
	}
573
}
574

575
func BenchmarkDescendRange(b *testing.B) {
576
	arr := perm(benchmarkTreeSize)
577
	tr := New(*btreeDegree)
578
	for _, v := range arr {
579
		tr.ReplaceOrInsert(v)
580
	}
581
	sort.Sort(byInts(arr))
582
	b.ResetTimer()
583
	for i := 0; i < b.N; i++ {
584
		j := len(arr) - 100
585
		tr.DescendRange(arr[len(arr)-100], Int(100), func(item Item) bool {
586
			if item.(Int) != arr[j].(Int) {
587
				b.Fatalf("mismatch: expected: %v, got %v", arr[j].(Int), item.(Int))
588
			}
589
			j--
590
			return true
591
		})
592
		if j != 100 {
593
			b.Fatalf("expected: %v, got %v", len(arr)-100, j)
594
		}
595
	}
596
}
597

598
func BenchmarkAscendGreaterOrEqual(b *testing.B) {
599
	arr := perm(benchmarkTreeSize)
600
	tr := New(*btreeDegree)
601
	for _, v := range arr {
602
		tr.ReplaceOrInsert(v)
603
	}
604
	sort.Sort(byInts(arr))
605
	b.ResetTimer()
606
	for i := 0; i < b.N; i++ {
607
		j := 100
608
		k := 0
609
		tr.AscendGreaterOrEqual(Int(100), func(item Item) bool {
610
			if item.(Int) != arr[j].(Int) {
611
				b.Fatalf("mismatch: expected: %v, got %v", arr[j].(Int), item.(Int))
612
			}
613
			j++
614
			k++
615
			return true
616
		})
617
		if j != len(arr) {
618
			b.Fatalf("expected: %v, got %v", len(arr), j)
619
		}
620
		if k != len(arr)-100 {
621
			b.Fatalf("expected: %v, got %v", len(arr)-100, k)
622
		}
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) {
657
	t.Logf("Starting new clone at %v", start)
658
	*trees = append(*trees, b)
659
	for i := start; i < cloneTestSize; i++ {
660
		b.ReplaceOrInsert(p[i])
661
		if i%(cloneTestSize/5) == 0 {
662
			wg.Add(1)
663
			go cloneTest(t, b.Clone(), i+1, p, wg, trees)
664
		}
665
	}
666
	wg.Done()
667
}
668

669
func TestCloneConcurrentOperations(t *testing.T) {
670
	b := New(*btreeDegree)
671
	trees := []*BTree{}
672
	p := perm(cloneTestSize)
673
	var wg sync.WaitGroup
674
	wg.Add(1)
675
	go cloneTest(t, b, 0, p, &wg, &trees)
676
	wg.Wait()
677
	want := rang(cloneTestSize)
678
	t.Logf("Starting equality checks on %d trees", len(trees))
679
	for i, tree := range trees {
680
		if !reflect.DeepEqual(want, all(tree)) {
681
			t.Errorf("tree %v mismatch", i)
682
		}
683
	}
684
	t.Log("Removing half from first half")
685
	toRemove := rang(cloneTestSize)[cloneTestSize/2:]
686
	for i := 0; i < len(trees)/2; i++ {
687
		tree := trees[i]
688
		wg.Add(1)
689
		go func() {
690
			for _, item := range toRemove {
691
				tree.Delete(item)
692
			}
693
			wg.Done()
694
		}()
695
	}
696
	wg.Wait()
697
	t.Log("Checking all values again")
698
	for i, tree := range trees {
699
		var wantpart []Item
700
		if i < len(trees)/2 {
701
			wantpart = want[:cloneTestSize/2]
702
		} else {
703
			wantpart = want
704
		}
705
		if got := all(tree); !reflect.DeepEqual(wantpart, got) {
706
			t.Errorf("tree %v mismatch, want %v got %v", i, len(want), len(got))
707
		}
708
	}
709
}
710

711
func BenchmarkDeleteAndRestore(b *testing.B) {
712
	items := perm(16392)
713
	b.ResetTimer()
714
	b.Run(`CopyBigFreeList`, func(b *testing.B) {
715
		fl := NewFreeList(16392)
716
		tr := NewWithFreeList(*btreeDegree, fl)
717
		for _, v := range items {
718
			tr.ReplaceOrInsert(v)
719
		}
720
		b.ReportAllocs()
721
		b.ResetTimer()
722
		for i := 0; i < b.N; i++ {
723
			dels := make([]Item, 0, tr.Len())
724
			tr.Ascend(ItemIterator(func(b Item) bool {
725
				dels = append(dels, b)
726
				return true
727
			}))
728
			for _, del := range dels {
729
				tr.Delete(del)
730
			}
731
			// tr is now empty, we make a new empty copy of it.
732
			tr = NewWithFreeList(*btreeDegree, fl)
733
			for _, v := range items {
734
				tr.ReplaceOrInsert(v)
735
			}
736
		}
737
	})
738
	b.Run(`Copy`, func(b *testing.B) {
739
		tr := New(*btreeDegree)
740
		for _, v := range items {
741
			tr.ReplaceOrInsert(v)
742
		}
743
		b.ReportAllocs()
744
		b.ResetTimer()
745
		for i := 0; i < b.N; i++ {
746
			dels := make([]Item, 0, tr.Len())
747
			tr.Ascend(ItemIterator(func(b Item) bool {
748
				dels = append(dels, b)
749
				return true
750
			}))
751
			for _, del := range dels {
752
				tr.Delete(del)
753
			}
754
			// tr is now empty, we make a new empty copy of it.
755
			tr = New(*btreeDegree)
756
			for _, v := range items {
757
				tr.ReplaceOrInsert(v)
758
			}
759
		}
760
	})
761
	b.Run(`ClearBigFreelist`, func(b *testing.B) {
762
		fl := NewFreeList(16392)
763
		tr := NewWithFreeList(*btreeDegree, fl)
764
		for _, v := range items {
765
			tr.ReplaceOrInsert(v)
766
		}
767
		b.ReportAllocs()
768
		b.ResetTimer()
769
		for i := 0; i < b.N; i++ {
770
			tr.Clear(true)
771
			for _, v := range items {
772
				tr.ReplaceOrInsert(v)
773
			}
774
		}
775
	})
776
	b.Run(`Clear`, func(b *testing.B) {
777
		tr := New(*btreeDegree)
778
		for _, v := range items {
779
			tr.ReplaceOrInsert(v)
780
		}
781
		b.ReportAllocs()
782
		b.ResetTimer()
783
		for i := 0; i < b.N; i++ {
784
			tr.Clear(true)
785
			for _, v := range items {
786
				tr.ReplaceOrInsert(v)
787
			}
788
		}
789
	})
790
}
791