addrindex_test.go raw
1 package index
2
3 import (
4 "bytes"
5 "fmt"
6 "testing"
7
8 "github.com/p9c/p9/pkg/wire"
9 )
10
11 // addrIndexBucket provides a mock address index database bucket by implementing the internalBucket interface.
12 type addrIndexBucket struct {
13 levels map[[levelKeySize]byte][]byte
14 }
15
16 // Clone returns a deep copy of the mock address index bucket.
17 func (b *addrIndexBucket) Clone() *addrIndexBucket {
18 levels := make(map[[levelKeySize]byte][]byte)
19 for k, v := range b.levels {
20 vCopy := make([]byte, len(v))
21 copy(vCopy, v)
22 levels[k] = vCopy
23 }
24 return &addrIndexBucket{levels: levels}
25 }
26
27 // Get returns the value associated with the key from the mock address index bucket.
28 //
29 // This is part of the internalBucket interface.
30 func (b *addrIndexBucket) Get(key []byte) []byte {
31 var levelKey [levelKeySize]byte
32 copy(levelKey[:], key)
33 return b.levels[levelKey]
34 }
35
36 // Put stores the provided key/value pair to the mock address index bucket.
37 //
38 // This is part of the internalBucket interface.
39 func (b *addrIndexBucket) Put(key []byte, value []byte) (e error) {
40 var levelKey [levelKeySize]byte
41 copy(levelKey[:], key)
42 b.levels[levelKey] = value
43 return nil
44 }
45
46 // Delete removes the provided key from the mock address index bucket.
47 //
48 // This is part of the internalBucket interface.
49 func (b *addrIndexBucket) Delete(key []byte) (e error) {
50 var levelKey [levelKeySize]byte
51 copy(levelKey[:], key)
52 delete(b.levels, levelKey)
53 return nil
54 }
55
56 // printLevels returns a string with a visual representation of the provided address key taking into account the max
57 // size of each level. It is useful when creating and debugging test cases.
58 func (b *addrIndexBucket) printLevels(addrKey [addrKeySize]byte) string {
59 highestLevel := uint8(0)
60 for k := range b.levels {
61 if !bytes.Equal(k[:levelOffset], addrKey[:]) {
62 continue
63 }
64 level := k[levelOffset]
65 if level > highestLevel {
66 highestLevel = level
67 }
68 }
69 var levelBuf bytes.Buffer
70 _, _ = levelBuf.WriteString("\n")
71 maxEntries := level0MaxEntries
72 for level := uint8(0); level <= highestLevel; level++ {
73 data := b.levels[keyForLevel(addrKey, level)]
74 numEntries := len(data) / txEntrySize
75 for i := 0; i < numEntries; i++ {
76 start := i * txEntrySize
77 num := byteOrder.Uint32(data[start:])
78 _, _ = levelBuf.WriteString(fmt.Sprintf("%02d ", num))
79 }
80 for i := numEntries; i < maxEntries; i++ {
81 _, _ = levelBuf.WriteString("_ ")
82 }
83 _, _ = levelBuf.WriteString("\n")
84 maxEntries *= 2
85 }
86 return levelBuf.String()
87 }
88
89 // sanityCheck ensures that all data stored in the bucket for the given address adheres to the level-based rules
90 // described by the address index documentation.
91 func (b *addrIndexBucket) sanityCheck(addrKey [addrKeySize]byte, expectedTotal int) (e error) {
92 // Find the highest level for the key.
93 highestLevel := uint8(0)
94 for k := range b.levels {
95 if !bytes.Equal(k[:levelOffset], addrKey[:]) {
96 continue
97 }
98 level := k[levelOffset]
99 if level > highestLevel {
100 highestLevel = level
101 }
102 }
103 // Ensure the expected total number of entries are present and that all levels adhere to the rules described in the
104 // address index documentation.
105 var totalEntries int
106 maxEntries := level0MaxEntries
107 for level := uint8(0); level <= highestLevel; level++ {
108 // Level 0 can'have more entries than the max allowed if the levels after it have data and it can't be empty.
109 // All other levels must either be half full or full.
110 data := b.levels[keyForLevel(addrKey, level)]
111 numEntries := len(data) / txEntrySize
112 totalEntries += numEntries
113 if level == 0 {
114 if (highestLevel != 0 && numEntries == 0) ||
115 numEntries > maxEntries {
116 return fmt.Errorf("level %d has %d entries",
117 level, numEntries,
118 )
119 }
120 } else if numEntries != maxEntries && numEntries != maxEntries/2 {
121 return fmt.Errorf("level %d has %d entries", level,
122 numEntries,
123 )
124 }
125 maxEntries *= 2
126 }
127 if totalEntries != expectedTotal {
128 return fmt.Errorf("expected %d entries - got %d", expectedTotal,
129 totalEntries,
130 )
131 }
132 // Ensure all of the numbers are in order starting from the highest level moving to the lowest level.
133 expectedNum := uint32(0)
134 for level := highestLevel + 1; level > 0; level-- {
135 data := b.levels[keyForLevel(addrKey, level)]
136 numEntries := len(data) / txEntrySize
137 for i := 0; i < numEntries; i++ {
138 start := i * txEntrySize
139 num := byteOrder.Uint32(data[start:])
140 if num != expectedNum {
141 return fmt.Errorf("level %d offset %d does "+
142 "not contain the expected number of "+
143 "%d - got %d", level, i, num,
144 expectedNum,
145 )
146 }
147 expectedNum++
148 }
149 }
150 return nil
151 }
152
153 // TestAddrIndexLevels ensures that adding and deleting entries to the address index creates multiple levels as
154 // described by the address index documentation.
155 func TestAddrIndexLevels(t *testing.T) {
156 t.Parallel()
157 tests := []struct {
158 name string
159 key [addrKeySize]byte
160 numInsert int
161 printLevels bool // Set to help debug a specific test.
162 }{
163 {
164 name: "level 0 not full",
165 numInsert: level0MaxEntries - 1,
166 },
167 {
168 name: "level 1 half",
169 numInsert: level0MaxEntries + 1,
170 },
171 {
172 name: "level 1 full",
173 numInsert: level0MaxEntries*2 + 1,
174 },
175 {
176 name: "level 2 half, level 1 half",
177 numInsert: level0MaxEntries*3 + 1,
178 },
179 {
180 name: "level 2 half, level 1 full",
181 numInsert: level0MaxEntries*4 + 1,
182 },
183 {
184 name: "level 2 full, level 1 half",
185 numInsert: level0MaxEntries*5 + 1,
186 },
187 {
188 name: "level 2 full, level 1 full",
189 numInsert: level0MaxEntries*6 + 1,
190 },
191 {
192 name: "level 3 half, level 2 half, level 1 half",
193 numInsert: level0MaxEntries*7 + 1,
194 },
195 {
196 name: "level 3 full, level 2 half, level 1 full",
197 numInsert: level0MaxEntries*12 + 1,
198 },
199 }
200 nextTest:
201 for testNum, test := range tests {
202 // Insert entries in order.
203 populatedBucket := &addrIndexBucket{
204 levels: make(map[[levelKeySize]byte][]byte),
205 }
206 for i := 0; i < test.numInsert; i++ {
207 txLoc := wire.TxLoc{TxStart: i * 2}
208 e := dbPutAddrIndexEntry(populatedBucket, test.key,
209 uint32(i), txLoc,
210 )
211 if e != nil {
212 t.Errorf("dbPutAddrIndexEntry #%d (%s) - "+
213 "unexpected error: %v", testNum,
214 test.name, e,
215 )
216 continue nextTest
217 }
218 }
219 if test.printLevels {
220 t.Log(populatedBucket.printLevels(test.key))
221 }
222 // Delete entries from the populated bucket until all entries have been deleted. The bucket is reset to the
223 // fully populated bucket on each iteration so every combination is tested. Notice the upper limit purposes
224 // exceeds the number of entries to ensure attempting to delete more entries than there are works correctly.
225 for numDelete := 0; numDelete <= test.numInsert+1; numDelete++ {
226 // Clone populated bucket to run each delete against.
227 bucket := populatedBucket.Clone()
228 // Remove the number of entries for this iteration.
229 e := dbRemoveAddrIndexEntries(bucket, test.key,
230 numDelete,
231 )
232 if e != nil {
233 if numDelete <= test.numInsert {
234 t.Errorf("dbRemoveAddrIndexEntries (%s) "+
235 " delete %d - unexpected error: "+
236 "%v", test.name, numDelete, e,
237 )
238 continue nextTest
239 }
240 }
241 if test.printLevels {
242 t.Log(bucket.printLevels(test.key))
243 }
244 // Sanity check the levels to ensure the adhere to all rules.
245 numExpected := test.numInsert
246 if numDelete <= test.numInsert {
247 numExpected -= numDelete
248 }
249 e = bucket.sanityCheck(test.key, numExpected)
250 if e != nil {
251 t.Errorf("sanity check fail (%s) delete %d: %v",
252 test.name, numDelete, e,
253 )
254 continue nextTest
255 }
256 }
257 }
258 }
259