mutable_test.go raw
1 package treap
2
3 import (
4 "bytes"
5 "crypto/sha256"
6 "testing"
7 )
8
9 // TestMutableEmpty ensures calling functions on an empty mutable treap works as
10 // expected.
11 func TestMutableEmpty(t *testing.T) {
12 t.Parallel()
13 // Ensure the treap length is the expected value.
14 testTreap := NewMutable()
15 if gotLen := testTreap.Len(); gotLen != 0 {
16 t.Fatalf("Len: unexpected length - got %d, want %d", gotLen, 0)
17 }
18 // Ensure the reported size is 0.
19 if gotSize := testTreap.Size(); gotSize != 0 {
20 t.Fatalf("Size: unexpected byte size - got %d, want 0",
21 gotSize,
22 )
23 }
24 // Ensure there are no errors with requesting keys from an empty treap.
25 key := serializeUint32(0)
26 if gotVal := testTreap.Has(key); gotVal {
27 t.Fatalf("Has: unexpected result - got %v, want false", gotVal)
28 }
29 if gotVal := testTreap.Get(key); gotVal != nil {
30 t.Fatalf("Get: unexpected result - got %x, want nil", gotVal)
31 }
32 // Ensure there are no panics when deleting keys from an empty treap.
33 testTreap.Delete(key)
34 // Ensure the number of keys iterated by ForEach on an empty treap is
35 // zero.
36 var numIterated int
37 testTreap.ForEach(func(k, v []byte) bool {
38 numIterated++
39 return true
40 },
41 )
42 if numIterated != 0 {
43 t.Fatalf("ForEach: unexpected iterate count - got %d, want 0",
44 numIterated,
45 )
46 }
47 }
48
49 // TestMutableReset ensures that resetting an existing mutable treap works as expected.
50 func TestMutableReset(t *testing.T) {
51 t.Parallel()
52 // Insert a few keys.
53 numItems := 10
54 testTreap := NewMutable()
55 for i := 0; i < numItems; i++ {
56 key := serializeUint32(uint32(i))
57 testTreap.Put(key, key)
58 }
59 // Reset it.
60 testTreap.Reset()
61 // Ensure the treap length is now 0.
62 if gotLen := testTreap.Len(); gotLen != 0 {
63 t.Fatalf("Len: unexpected length - got %d, want %d", gotLen, 0)
64 }
65 // Ensure the reported size is now 0.
66 if gotSize := testTreap.Size(); gotSize != 0 {
67 t.Fatalf("Size: unexpected byte size - got %d, want 0",
68 gotSize,
69 )
70 }
71 // Ensure the treap no longer has any of the keys.
72 for i := 0; i < numItems; i++ {
73 key := serializeUint32(uint32(i))
74 // Ensure the treap no longer has the key.
75 if testTreap.Has(key) {
76 t.Fatalf("Has #%d: key %q is in treap", i, key)
77 }
78 // Get the key that no longer exists from the treap and ensure
79 // it is nil.
80 if gotVal := testTreap.Get(key); gotVal != nil {
81 t.Fatalf("Get #%d: unexpected value - got %x, want nil",
82 i, gotVal,
83 )
84 }
85 }
86 // Ensure the number of keys iterated by ForEach is zero.
87 var numIterated int
88 testTreap.ForEach(func(k, v []byte) bool {
89 numIterated++
90 return true
91 },
92 )
93 if numIterated != 0 {
94 t.Fatalf("ForEach: unexpected iterate count - got %d, want 0",
95 numIterated,
96 )
97 }
98 }
99
100 // TestMutableSequential ensures that putting keys into a mutable treap in sequential order works as expected.
101 func TestMutableSequential(t *testing.T) {
102 t.Parallel()
103 // Insert a bunch of sequential keys while checking several of the treap functions work as expected.
104 expectedSize := uint64(0)
105 numItems := 1000
106 testTreap := NewMutable()
107 for i := 0; i < numItems; i++ {
108 key := serializeUint32(uint32(i))
109 testTreap.Put(key, key)
110 // Ensure the treap length is the expected value.
111 if gotLen := testTreap.Len(); gotLen != i+1 {
112 t.Fatalf("Len #%d: unexpected length - got %d, want %d",
113 i, gotLen, i+1,
114 )
115 }
116 // Ensure the treap has the key.
117 if !testTreap.Has(key) {
118 t.Fatalf("Has #%d: key %q is not in treap", i, key)
119 }
120 // Get the key from the treap and ensure it is the expected value.
121 if gotVal := testTreap.Get(key); !bytes.Equal(gotVal, key) {
122 t.Fatalf("Get #%d: unexpected value - got %x, want %x",
123 i, gotVal, key,
124 )
125 }
126 // Ensure the expected size is reported.
127 expectedSize += nodeFieldsSize + 8
128 if gotSize := testTreap.Size(); gotSize != expectedSize {
129 t.Fatalf("Size #%d: unexpected byte size - got %d, "+
130 "want %d", i, gotSize, expectedSize,
131 )
132 }
133 }
134 // Ensure the all keys are iterated by ForEach in order.
135 var numIterated int
136 testTreap.ForEach(func(k, v []byte) bool {
137 wantKey := serializeUint32(uint32(numIterated))
138 // Ensure the key is as expected.
139 if !bytes.Equal(k, wantKey) {
140 t.Fatalf("ForEach #%d: unexpected key - got %x, want %x",
141 numIterated, k, wantKey,
142 )
143 }
144 // Ensure the value is as expected.
145 if !bytes.Equal(v, wantKey) {
146 t.Fatalf("ForEach #%d: unexpected value - got %x, want %x",
147 numIterated, v, wantKey,
148 )
149 }
150 numIterated++
151 return true
152 },
153 )
154 // Ensure all items were iterated.
155 if numIterated != numItems {
156 t.Fatalf("ForEach: unexpected iterate count - got %d, want %d",
157 numIterated, numItems,
158 )
159 }
160 // Delete the keys one-by-one while checking several of the treap functions work as expected.
161 for i := 0; i < numItems; i++ {
162 key := serializeUint32(uint32(i))
163 testTreap.Delete(key)
164 // Ensure the treap length is the expected value.
165 if gotLen := testTreap.Len(); gotLen != numItems-i-1 {
166 t.Fatalf("Len #%d: unexpected length - got %d, want %d",
167 i, gotLen, numItems-i-1,
168 )
169 }
170 // Ensure the treap no longer has the key.
171 if testTreap.Has(key) {
172 t.Fatalf("Has #%d: key %q is in treap", i, key)
173 }
174 // Get the key that no longer exists from the treap and ensure it is nil.
175 if gotVal := testTreap.Get(key); gotVal != nil {
176 t.Fatalf("Get #%d: unexpected value - got %x, want nil",
177 i, gotVal,
178 )
179 }
180 // Ensure the expected size is reported.
181 expectedSize -= nodeFieldsSize + 8
182 if gotSize := testTreap.Size(); gotSize != expectedSize {
183 t.Fatalf("Size #%d: unexpected byte size - got %d, "+
184 "want %d", i, gotSize, expectedSize,
185 )
186 }
187 }
188 }
189
190 // TestMutableReverseSequential ensures that putting keys into a mutable treap in reverse sequential order works as
191 // expected.
192 func TestMutableReverseSequential(t *testing.T) {
193 t.Parallel()
194 // Insert a bunch of sequential keys while checking several of the treap functions work as expected.
195 expectedSize := uint64(0)
196 numItems := 1000
197 testTreap := NewMutable()
198 for i := 0; i < numItems; i++ {
199 key := serializeUint32(uint32(numItems - i - 1))
200 testTreap.Put(key, key)
201 // Ensure the treap length is the expected value.
202 if gotLen := testTreap.Len(); gotLen != i+1 {
203 t.Fatalf("Len #%d: unexpected length - got %d, want %d",
204 i, gotLen, i+1,
205 )
206 }
207 // Ensure the treap has the key.
208 if !testTreap.Has(key) {
209 t.Fatalf("Has #%d: key %q is not in treap", i, key)
210 }
211 // Get the key from the treap and ensure it is the expected value.
212 if gotVal := testTreap.Get(key); !bytes.Equal(gotVal, key) {
213 t.Fatalf("Get #%d: unexpected value - got %x, want %x",
214 i, gotVal, key,
215 )
216 }
217 // Ensure the expected size is reported.
218 expectedSize += nodeFieldsSize + 8
219 if gotSize := testTreap.Size(); gotSize != expectedSize {
220 t.Fatalf("Size #%d: unexpected byte size - got %d, "+
221 "want %d", i, gotSize, expectedSize,
222 )
223 }
224 }
225 // Ensure the all keys are iterated by ForEach in order.
226 var numIterated int
227 testTreap.ForEach(func(k, v []byte) bool {
228 wantKey := serializeUint32(uint32(numIterated))
229 // Ensure the key is as expected.
230 if !bytes.Equal(k, wantKey) {
231 t.Fatalf("ForEach #%d: unexpected key - got %x, want %x",
232 numIterated, k, wantKey,
233 )
234 }
235 // Ensure the value is as expected.
236 if !bytes.Equal(v, wantKey) {
237 t.Fatalf("ForEach #%d: unexpected value - got %x, want %x",
238 numIterated, v, wantKey,
239 )
240 }
241 numIterated++
242 return true
243 },
244 )
245 // Ensure all items were iterated.
246 if numIterated != numItems {
247 t.Fatalf("ForEach: unexpected iterate count - got %d, want %d",
248 numIterated, numItems,
249 )
250 }
251 // Delete the keys one-by-one while checking several of the treap functions work as expected.
252 for i := 0; i < numItems; i++ {
253 // Intentionally use the reverse order they were inserted here.
254 key := serializeUint32(uint32(i))
255 testTreap.Delete(key)
256 // Ensure the treap length is the expected value.
257 if gotLen := testTreap.Len(); gotLen != numItems-i-1 {
258 t.Fatalf("Len #%d: unexpected length - got %d, want %d",
259 i, gotLen, numItems-i-1,
260 )
261 }
262 // Ensure the treap no longer has the key.
263 if testTreap.Has(key) {
264 t.Fatalf("Has #%d: key %q is in treap", i, key)
265 }
266 // Get the key that no longer exists from the treap and ensure it is nil.
267 if gotVal := testTreap.Get(key); gotVal != nil {
268 t.Fatalf("Get #%d: unexpected value - got %x, want nil",
269 i, gotVal,
270 )
271 }
272 // Ensure the expected size is reported.
273 expectedSize -= nodeFieldsSize + 8
274 if gotSize := testTreap.Size(); gotSize != expectedSize {
275 t.Fatalf("Size #%d: unexpected byte size - got %d, "+
276 "want %d", i, gotSize, expectedSize,
277 )
278 }
279 }
280 }
281
282 // TestMutableUnordered ensures that putting keys into a mutable treap in no particular order works as expected.
283 func TestMutableUnordered(t *testing.T) {
284 t.Parallel()
285 // Insert a bunch of out-of-order keys while checking several of the treap functions work as expected.
286 expectedSize := uint64(0)
287 numItems := 1000
288 testTreap := NewMutable()
289 for i := 0; i < numItems; i++ {
290 // Hash the serialized int to generate out-of-order keys.
291 hash := sha256.Sum256(serializeUint32(uint32(i)))
292 key := hash[:]
293 testTreap.Put(key, key)
294 // Ensure the treap length is the expected value.
295 if gotLen := testTreap.Len(); gotLen != i+1 {
296 t.Fatalf("Len #%d: unexpected length - got %d, want %d",
297 i, gotLen, i+1,
298 )
299 }
300 // Ensure the treap has the key.
301 if !testTreap.Has(key) {
302 t.Fatalf("Has #%d: key %q is not in treap", i, key)
303 }
304 // Get the key from the treap and ensure it is the expected
305 // value.
306 if gotVal := testTreap.Get(key); !bytes.Equal(gotVal, key) {
307 t.Fatalf("Get #%d: unexpected value - got %x, want %x",
308 i, gotVal, key,
309 )
310 }
311 // Ensure the expected size is reported.
312 expectedSize += nodeFieldsSize + uint64(len(key)+len(key))
313 if gotSize := testTreap.Size(); gotSize != expectedSize {
314 t.Fatalf("Size #%d: unexpected byte size - got %d, "+
315 "want %d", i, gotSize, expectedSize,
316 )
317 }
318 }
319 // Delete the keys one-by-one while checking several of the treap functions work as expected.
320 for i := 0; i < numItems; i++ {
321 // Hash the serialized int to generate out-of-order keys.
322 hash := sha256.Sum256(serializeUint32(uint32(i)))
323 key := hash[:]
324 testTreap.Delete(key)
325 // Ensure the treap length is the expected value.
326 if gotLen := testTreap.Len(); gotLen != numItems-i-1 {
327 t.Fatalf("Len #%d: unexpected length - got %d, want %d",
328 i, gotLen, numItems-i-1,
329 )
330 }
331 // Ensure the treap no longer has the key.
332 if testTreap.Has(key) {
333 t.Fatalf("Has #%d: key %q is in treap", i, key)
334 }
335 // Get the key that no longer exists from the treap and ensure it is nil.
336 if gotVal := testTreap.Get(key); gotVal != nil {
337 t.Fatalf("Get #%d: unexpected value - got %x, want nil",
338 i, gotVal,
339 )
340 }
341 // Ensure the expected size is reported.
342 expectedSize -= nodeFieldsSize + 64
343 if gotSize := testTreap.Size(); gotSize != expectedSize {
344 t.Fatalf("Size #%d: unexpected byte size - got %d, "+
345 "want %d", i, gotSize, expectedSize,
346 )
347 }
348 }
349 }
350
351 // TestMutableDuplicatePut ensures that putting a duplicate key into a mutable treap updates the existing value.
352 func TestMutableDuplicatePut(t *testing.T) {
353 t.Parallel()
354 key := serializeUint32(0)
355 val := []byte("testval")
356 // Put the key twice with the second put being the expected final value.
357 testTreap := NewMutable()
358 testTreap.Put(key, key)
359 testTreap.Put(key, val)
360 // Ensure the key still exists and is the new value.
361 if gotVal := testTreap.Has(key); !gotVal {
362 t.Fatalf("Has: unexpected result - got %v, want true", gotVal)
363 }
364 if gotVal := testTreap.Get(key); !bytes.Equal(gotVal, val) {
365 t.Fatalf("Get: unexpected result - got %x, want %x", gotVal, val)
366 }
367 // Ensure the expected size is reported.
368 expectedSize := uint64(nodeFieldsSize + len(key) + len(val))
369 if gotSize := testTreap.Size(); gotSize != expectedSize {
370 t.Fatalf("Size: unexpected byte size - got %d, want %d",
371 gotSize, expectedSize,
372 )
373 }
374 }
375
376 // TestMutableNilValue ensures that putting a nil value into a mutable treap results in a key being added with an empty
377 // byte slice.
378 func TestMutableNilValue(t *testing.T) {
379 t.Parallel()
380 key := serializeUint32(0)
381 // Put the key with a nil value.
382 testTreap := NewMutable()
383 testTreap.Put(key, nil)
384 // Ensure the key exists and is an empty byte slice.
385 if gotVal := testTreap.Has(key); !gotVal {
386 t.Fatalf("Has: unexpected result - got %v, want true", gotVal)
387 }
388 if gotVal := testTreap.Get(key); gotVal == nil {
389 t.Fatalf("Get: unexpected result - got nil, want empty slice")
390 }
391 if gotVal := testTreap.Get(key); len(gotVal) != 0 {
392 t.Fatalf("Get: unexpected result - got %x, want empty slice",
393 gotVal,
394 )
395 }
396 }
397
398 // TestMutableForEachStopIterator ensures that returning false from the ForEach callback of a mutable treap stops
399 // iteration early.
400 func TestMutableForEachStopIterator(t *testing.T) {
401 t.Parallel()
402 // Insert a few keys.
403 numItems := 10
404 testTreap := NewMutable()
405 for i := 0; i < numItems; i++ {
406 key := serializeUint32(uint32(i))
407 testTreap.Put(key, key)
408 }
409 // Ensure ForEach exits early on false return by caller.
410 var numIterated int
411 testTreap.ForEach(func(k, v []byte) bool {
412 numIterated++
413 return numIterated != numItems/2
414 },
415 )
416 if numIterated != numItems/2 {
417 t.Fatalf("ForEach: unexpected iterate count - got %d, want %d",
418 numIterated, numItems/2,
419 )
420 }
421 }
422