1
2
3
4
5
6
7 package leveldb
8
9 import (
10 "encoding/binary"
11 "math/rand"
12 "reflect"
13 "testing"
14
15 "github.com/onsi/gomega"
16 "github.com/syndtr/goleveldb/leveldb/storage"
17 "github.com/syndtr/goleveldb/leveldb/testutil"
18 )
19
20 func TestGetOverlaps(t *testing.T) {
21 gomega.RegisterTestingT(t)
22 stor := testutil.NewStorage()
23 defer stor.Close()
24 s, err := newSession(stor, nil)
25 if err != nil {
26 t.Fatal(err)
27 }
28
29 v := newVersion(s)
30 v.newStaging()
31
32 tmp := make([]byte, 4)
33 mik := func(i uint64, typ keyType, ukey bool) []byte {
34 if i == 0 {
35 return nil
36 }
37 binary.BigEndian.PutUint32(tmp, uint32(i))
38 if ukey {
39 key := make([]byte, 4)
40 copy(key, tmp)
41 return key
42 }
43 return []byte(makeInternalKey(nil, tmp, 0, typ))
44 }
45
46 rec := &sessionRecord{}
47 for i, f := range []struct {
48 min uint64
49 max uint64
50 level int
51 }{
52
53 {1, 8, 0},
54 {4, 5, 0},
55 {6, 10, 0},
56
57 {2, 3, 1},
58 {8, 10, 1},
59 {13, 13, 1},
60 {20, 100, 1},
61 } {
62 rec.addTable(f.level, int64(i), 1, mik(f.min, keyTypeVal, false), mik(f.max, keyTypeVal, false))
63 }
64 vs := v.newStaging()
65 vs.commit(rec)
66 v = vs.finish(false)
67
68 for i, x := range []struct {
69 min uint64
70 max uint64
71 level int
72 expected []int64
73 }{
74
75 {0, 0, 0, []int64{2, 1, 0}},
76 {1, 0, 0, []int64{2, 1, 0}},
77 {0, 10, 0, []int64{2, 1, 0}},
78 {2, 7, 0, []int64{2, 1, 0}},
79
80
81 {1, 1, 1, nil},
82 {0, 100, 1, []int64{3, 4, 5, 6}},
83 {5, 0, 1, []int64{4, 5, 6}},
84 {5, 4, 1, nil},
85 {1, 13, 1, []int64{3, 4, 5}},
86 {2, 13, 1, []int64{3, 4, 5}},
87 {3, 13, 1, []int64{3, 4, 5}},
88 {4, 13, 1, []int64{4, 5}},
89 {4, 19, 1, []int64{4, 5}},
90 {4, 20, 1, []int64{4, 5, 6}},
91 {4, 100, 1, []int64{4, 5, 6}},
92 {4, 105, 1, []int64{4, 5, 6}},
93 } {
94 tf := v.levels[x.level]
95 res := tf.getOverlaps(nil, s.icmp, mik(x.min, keyTypeSeek, true), mik(x.max, keyTypeSeek, true), x.level == 0)
96
97 var fnums []int64
98 for _, f := range res {
99 fnums = append(fnums, f.fd.Num)
100 }
101 if !reflect.DeepEqual(x.expected, fnums) {
102 t.Errorf("case %d failed, expected %v, got %v", i, x.expected, fnums)
103 }
104 }
105 }
106
107 func BenchmarkGetOverlapLevel0(b *testing.B) {
108 benchmarkGetOverlap(b, 0, 500000)
109 }
110
111 func BenchmarkGetOverlapNonLevel0(b *testing.B) {
112 benchmarkGetOverlap(b, 1, 500000)
113 }
114
115 func benchmarkGetOverlap(b *testing.B, level int, size int) {
116 stor := storage.NewMemStorage()
117 defer stor.Close()
118 s, err := newSession(stor, nil)
119 if err != nil {
120 b.Fatal(err)
121 }
122
123 v := newVersion(s)
124 v.newStaging()
125
126 tmp := make([]byte, 4)
127 mik := func(i uint64, typ keyType, ukey bool) []byte {
128 if i == 0 {
129 return nil
130 }
131 binary.BigEndian.PutUint32(tmp, uint32(i))
132 if ukey {
133 key := make([]byte, 4)
134 copy(key, tmp)
135 return key
136 }
137 return []byte(makeInternalKey(nil, tmp, 0, typ))
138 }
139
140 rec := &sessionRecord{}
141 for i := 1; i <= size; i++ {
142 min := mik(uint64(2*i), keyTypeVal, false)
143 max := mik(uint64(2*i+1), keyTypeVal, false)
144 rec.addTable(level, int64(i), 1, min, max)
145 }
146 vs := v.newStaging()
147 vs.commit(rec)
148 v = vs.finish(false)
149
150 b.ResetTimer()
151 b.ReportAllocs()
152
153 for i := 0; i < b.N; i++ {
154 files := v.levels[level]
155 start := rand.Intn(size)
156 end := rand.Intn(size-start) + start
157 files.getOverlaps(nil, s.icmp, mik(uint64(2*start), keyTypeVal, true), mik(uint64(2*end), keyTypeVal, true), level == 0)
158 }
159 }
160
View as plain text