1 // Copyright (c) 2015-2016 The btcsuite developers
2 // Use of this source code is governed by an ISC
3 // license that can be found in the LICENSE file.
13 // TestMutableEmpty ensures calling functions on an empty mutable treap works as
15 func TestMutableEmpty(t *testing.T) {
18 // Ensure the treap length is the expected value.
19 testTreap := NewMutable()
20 if gotLen := testTreap.Len(); gotLen != 0 {
21 t.Fatalf("Len: unexpected length - got %d, want %d", gotLen, 0)
24 // Ensure the reported size is 0.
25 if gotSize := testTreap.Size(); gotSize != 0 {
26 t.Fatalf("Size: unexpected byte size - got %d, want 0",
30 // Ensure there are no errors with requesting keys from an empty treap.
31 key := serializeUint32(0)
32 if gotVal := testTreap.Has(key); gotVal {
33 t.Fatalf("Has: unexpected result - got %v, want false", gotVal)
35 if gotVal := testTreap.Get(key); gotVal != nil {
36 t.Fatalf("Get: unexpected result - got %x, want nil", gotVal)
39 // Ensure there are no panics when deleting keys from an empty treap.
42 // Ensure the number of keys iterated by ForEach on an empty treap is
45 testTreap.ForEach(func(k, v []byte) bool {
50 t.Fatalf("ForEach: unexpected iterate count - got %d, want 0",
55 // TestMutableReset ensures that resetting an existing mutable treap works as
57 func TestMutableReset(t *testing.T) {
62 testTreap := NewMutable()
63 for i := 0; i < numItems; i++ {
64 key := serializeUint32(uint32(i))
65 testTreap.Put(key, key)
71 // Ensure the treap length is now 0.
72 if gotLen := testTreap.Len(); gotLen != 0 {
73 t.Fatalf("Len: unexpected length - got %d, want %d", gotLen, 0)
76 // Ensure the reported size is now 0.
77 if gotSize := testTreap.Size(); gotSize != 0 {
78 t.Fatalf("Size: unexpected byte size - got %d, want 0",
82 // Ensure the treap no longer has any of the keys.
83 for i := 0; i < numItems; i++ {
84 key := serializeUint32(uint32(i))
86 // Ensure the treap no longer has the key.
87 if testTreap.Has(key) {
88 t.Fatalf("Has #%d: key %q is in treap", i, key)
91 // Get the key that no longer exists from the treap and ensure
93 if gotVal := testTreap.Get(key); gotVal != nil {
94 t.Fatalf("Get #%d: unexpected value - got %x, want nil",
99 // Ensure the number of keys iterated by ForEach is zero.
101 testTreap.ForEach(func(k, v []byte) bool {
105 if numIterated != 0 {
106 t.Fatalf("ForEach: unexpected iterate count - got %d, want 0",
111 // TestMutableSequential ensures that putting keys into a mutable treap in
112 // sequential order works as expected.
113 func TestMutableSequential(t *testing.T) {
116 // Insert a bunch of sequential keys while checking several of the treap
117 // functions work as expected.
118 expectedSize := uint64(0)
120 testTreap := NewMutable()
121 for i := 0; i < numItems; i++ {
122 key := serializeUint32(uint32(i))
123 testTreap.Put(key, key)
125 // Ensure the treap length is the expected value.
126 if gotLen := testTreap.Len(); gotLen != i+1 {
127 t.Fatalf("Len #%d: unexpected length - got %d, want %d",
131 // Ensure the treap has the key.
132 if !testTreap.Has(key) {
133 t.Fatalf("Has #%d: key %q is not in treap", i, key)
136 // Get the key from the treap and ensure it is the expected
138 if gotVal := testTreap.Get(key); !bytes.Equal(gotVal, key) {
139 t.Fatalf("Get #%d: unexpected value - got %x, want %x",
143 // Ensure the expected size is reported.
144 expectedSize += (nodeFieldsSize + 8)
145 if gotSize := testTreap.Size(); gotSize != expectedSize {
146 t.Fatalf("Size #%d: unexpected byte size - got %d, "+
147 "want %d", i, gotSize, expectedSize)
151 // Ensure the all keys are iterated by ForEach in order.
153 testTreap.ForEach(func(k, v []byte) bool {
154 wantKey := serializeUint32(uint32(numIterated))
156 // Ensure the key is as expected.
157 if !bytes.Equal(k, wantKey) {
158 t.Fatalf("ForEach #%d: unexpected key - got %x, want %x",
159 numIterated, k, wantKey)
162 // Ensure the value is as expected.
163 if !bytes.Equal(v, wantKey) {
164 t.Fatalf("ForEach #%d: unexpected value - got %x, want %x",
165 numIterated, v, wantKey)
172 // Ensure all items were iterated.
173 if numIterated != numItems {
174 t.Fatalf("ForEach: unexpected iterate count - got %d, want %d",
175 numIterated, numItems)
178 // Delete the keys one-by-one while checking several of the treap
179 // functions work as expected.
180 for i := 0; i < numItems; i++ {
181 key := serializeUint32(uint32(i))
182 testTreap.Delete(key)
184 // Ensure the treap length is the expected value.
185 if gotLen := testTreap.Len(); gotLen != numItems-i-1 {
186 t.Fatalf("Len #%d: unexpected length - got %d, want %d",
187 i, gotLen, numItems-i-1)
190 // Ensure the treap no longer has the key.
191 if testTreap.Has(key) {
192 t.Fatalf("Has #%d: key %q is in treap", i, key)
195 // Get the key that no longer exists from the treap and ensure
197 if gotVal := testTreap.Get(key); gotVal != nil {
198 t.Fatalf("Get #%d: unexpected value - got %x, want nil",
202 // Ensure the expected size is reported.
203 expectedSize -= (nodeFieldsSize + 8)
204 if gotSize := testTreap.Size(); gotSize != expectedSize {
205 t.Fatalf("Size #%d: unexpected byte size - got %d, "+
206 "want %d", i, gotSize, expectedSize)
211 // TestMutableReverseSequential ensures that putting keys into a mutable treap
212 // in reverse sequential order works as expected.
213 func TestMutableReverseSequential(t *testing.T) {
216 // Insert a bunch of sequential keys while checking several of the treap
217 // functions work as expected.
218 expectedSize := uint64(0)
220 testTreap := NewMutable()
221 for i := 0; i < numItems; i++ {
222 key := serializeUint32(uint32(numItems - i - 1))
223 testTreap.Put(key, key)
225 // Ensure the treap length is the expected value.
226 if gotLen := testTreap.Len(); gotLen != i+1 {
227 t.Fatalf("Len #%d: unexpected length - got %d, want %d",
231 // Ensure the treap has the key.
232 if !testTreap.Has(key) {
233 t.Fatalf("Has #%d: key %q is not in treap", i, key)
236 // Get the key from the treap and ensure it is the expected
238 if gotVal := testTreap.Get(key); !bytes.Equal(gotVal, key) {
239 t.Fatalf("Get #%d: unexpected value - got %x, want %x",
243 // Ensure the expected size is reported.
244 expectedSize += (nodeFieldsSize + 8)
245 if gotSize := testTreap.Size(); gotSize != expectedSize {
246 t.Fatalf("Size #%d: unexpected byte size - got %d, "+
247 "want %d", i, gotSize, expectedSize)
251 // Ensure the all keys are iterated by ForEach in order.
253 testTreap.ForEach(func(k, v []byte) bool {
254 wantKey := serializeUint32(uint32(numIterated))
256 // Ensure the key is as expected.
257 if !bytes.Equal(k, wantKey) {
258 t.Fatalf("ForEach #%d: unexpected key - got %x, want %x",
259 numIterated, k, wantKey)
262 // Ensure the value is as expected.
263 if !bytes.Equal(v, wantKey) {
264 t.Fatalf("ForEach #%d: unexpected value - got %x, want %x",
265 numIterated, v, wantKey)
272 // Ensure all items were iterated.
273 if numIterated != numItems {
274 t.Fatalf("ForEach: unexpected iterate count - got %d, want %d",
275 numIterated, numItems)
278 // Delete the keys one-by-one while checking several of the treap
279 // functions work as expected.
280 for i := 0; i < numItems; i++ {
281 // Intentionally use the reverse order they were inserted here.
282 key := serializeUint32(uint32(i))
283 testTreap.Delete(key)
285 // Ensure the treap length is the expected value.
286 if gotLen := testTreap.Len(); gotLen != numItems-i-1 {
287 t.Fatalf("Len #%d: unexpected length - got %d, want %d",
288 i, gotLen, numItems-i-1)
291 // Ensure the treap no longer has the key.
292 if testTreap.Has(key) {
293 t.Fatalf("Has #%d: key %q is in treap", i, key)
296 // Get the key that no longer exists from the treap and ensure
298 if gotVal := testTreap.Get(key); gotVal != nil {
299 t.Fatalf("Get #%d: unexpected value - got %x, want nil",
303 // Ensure the expected size is reported.
304 expectedSize -= (nodeFieldsSize + 8)
305 if gotSize := testTreap.Size(); gotSize != expectedSize {
306 t.Fatalf("Size #%d: unexpected byte size - got %d, "+
307 "want %d", i, gotSize, expectedSize)
312 // TestMutableUnordered ensures that putting keys into a mutable treap in no
313 // paritcular order works as expected.
314 func TestMutableUnordered(t *testing.T) {
317 // Insert a bunch of out-of-order keys while checking several of the
318 // treap functions work as expected.
319 expectedSize := uint64(0)
321 testTreap := NewMutable()
322 for i := 0; i < numItems; i++ {
323 // Hash the serialized int to generate out-of-order keys.
324 hash := sha256.Sum256(serializeUint32(uint32(i)))
326 testTreap.Put(key, key)
328 // Ensure the treap length is the expected value.
329 if gotLen := testTreap.Len(); gotLen != i+1 {
330 t.Fatalf("Len #%d: unexpected length - got %d, want %d",
334 // Ensure the treap has the key.
335 if !testTreap.Has(key) {
336 t.Fatalf("Has #%d: key %q is not in treap", i, key)
339 // Get the key from the treap and ensure it is the expected
341 if gotVal := testTreap.Get(key); !bytes.Equal(gotVal, key) {
342 t.Fatalf("Get #%d: unexpected value - got %x, want %x",
346 // Ensure the expected size is reported.
347 expectedSize += nodeFieldsSize + uint64(len(key)+len(key))
348 if gotSize := testTreap.Size(); gotSize != expectedSize {
349 t.Fatalf("Size #%d: unexpected byte size - got %d, "+
350 "want %d", i, gotSize, expectedSize)
354 // Delete the keys one-by-one while checking several of the treap
355 // functions work as expected.
356 for i := 0; i < numItems; i++ {
357 // Hash the serialized int to generate out-of-order keys.
358 hash := sha256.Sum256(serializeUint32(uint32(i)))
360 testTreap.Delete(key)
362 // Ensure the treap length is the expected value.
363 if gotLen := testTreap.Len(); gotLen != numItems-i-1 {
364 t.Fatalf("Len #%d: unexpected length - got %d, want %d",
365 i, gotLen, numItems-i-1)
368 // Ensure the treap no longer has the key.
369 if testTreap.Has(key) {
370 t.Fatalf("Has #%d: key %q is in treap", i, key)
373 // Get the key that no longer exists from the treap and ensure
375 if gotVal := testTreap.Get(key); gotVal != nil {
376 t.Fatalf("Get #%d: unexpected value - got %x, want nil",
380 // Ensure the expected size is reported.
381 expectedSize -= (nodeFieldsSize + 64)
382 if gotSize := testTreap.Size(); gotSize != expectedSize {
383 t.Fatalf("Size #%d: unexpected byte size - got %d, "+
384 "want %d", i, gotSize, expectedSize)
389 // TestMutableDuplicatePut ensures that putting a duplicate key into a mutable
390 // treap updates the existing value.
391 func TestMutableDuplicatePut(t *testing.T) {
394 key := serializeUint32(0)
395 val := []byte("testval")
397 // Put the key twice with the second put being the expected final value.
398 testTreap := NewMutable()
399 testTreap.Put(key, key)
400 testTreap.Put(key, val)
402 // Ensure the key still exists and is the new value.
403 if gotVal := testTreap.Has(key); !gotVal {
404 t.Fatalf("Has: unexpected result - got %v, want true", gotVal)
406 if gotVal := testTreap.Get(key); !bytes.Equal(gotVal, val) {
407 t.Fatalf("Get: unexpected result - got %x, want %x", gotVal, val)
410 // Ensure the expected size is reported.
411 expectedSize := uint64(nodeFieldsSize + len(key) + len(val))
412 if gotSize := testTreap.Size(); gotSize != expectedSize {
413 t.Fatalf("Size: unexpected byte size - got %d, want %d",
414 gotSize, expectedSize)
418 // TestMutableNilValue ensures that putting a nil value into a mutable treap
419 // results in a key being added with an empty byte slice.
420 func TestMutableNilValue(t *testing.T) {
423 key := serializeUint32(0)
425 // Put the key with a nil value.
426 testTreap := NewMutable()
427 testTreap.Put(key, nil)
429 // Ensure the key exists and is an empty byte slice.
430 if gotVal := testTreap.Has(key); !gotVal {
431 t.Fatalf("Has: unexpected result - got %v, want true", gotVal)
433 if gotVal := testTreap.Get(key); gotVal == nil {
434 t.Fatalf("Get: unexpected result - got nil, want empty slice")
436 if gotVal := testTreap.Get(key); len(gotVal) != 0 {
437 t.Fatalf("Get: unexpected result - got %x, want empty slice",
442 // TestMutableForEachStopIterator ensures that returning false from the ForEach
443 // callback of a mutable treap stops iteration early.
444 func TestMutableForEachStopIterator(t *testing.T) {
447 // Insert a few keys.
449 testTreap := NewMutable()
450 for i := 0; i < numItems; i++ {
451 key := serializeUint32(uint32(i))
452 testTreap.Put(key, key)
455 // Ensure ForEach exits early on false return by caller.
457 testTreap.ForEach(func(k, v []byte) bool {
459 return numIterated != numItems/2
461 if numIterated != numItems/2 {
462 t.Fatalf("ForEach: unexpected iterate count - got %d, want %d",
463 numIterated, numItems/2)