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 // TestMutableIterator ensures that the general behavior of mutable treap
14 // iterators is as expected including tests for first, last, ordered and reverse
15 // ordered iteration, limiting the range, seeking, and initially unpositioned.
16 func TestMutableIterator(t *testing.T) {
29 // No range limits. Values are the set (0, 1, 2, ..., 49).
30 // Seek existing value.
34 expectedFirst: serializeUint32(0),
35 expectedLast: serializeUint32(49),
36 seekKey: serializeUint32(12),
37 expectedSeek: serializeUint32(12),
40 // Limited to range [24, end]. Values are the set
41 // (0, 2, 4, ..., 48). Seek value that doesn't exist and is
42 // greater than largest existing key.
46 startKey: serializeUint32(24),
47 expectedFirst: serializeUint32(24),
48 expectedLast: serializeUint32(48),
49 seekKey: serializeUint32(49),
53 // Limited to range [start, 25). Values are the set
54 // (0, 3, 6, ..., 48). Seek value that doesn't exist but is
55 // before an existing value within the range.
59 limitKey: serializeUint32(25),
60 expectedFirst: serializeUint32(0),
61 expectedLast: serializeUint32(24),
62 seekKey: serializeUint32(17),
63 expectedSeek: serializeUint32(18),
66 // Limited to range [10, 21). Values are the set
67 // (0, 4, ..., 48). Seek value that exists, but is before the
68 // minimum allowed range.
72 startKey: serializeUint32(10),
73 limitKey: serializeUint32(21),
74 expectedFirst: serializeUint32(12),
75 expectedLast: serializeUint32(20),
76 seekKey: serializeUint32(4),
80 // Limited by prefix {0,0,0}, range [{0,0,0}, {0,0,1}).
81 // Since it's a bytewise compare, {0,0,0,...} < {0,0,1}.
82 // Seek existing value within the allowed range.
86 startKey: []byte{0x00, 0x00, 0x00},
87 limitKey: []byte{0x00, 0x00, 0x01},
88 expectedFirst: serializeUint32(0),
89 expectedLast: serializeUint32(255),
90 seekKey: serializeUint32(100),
91 expectedSeek: serializeUint32(100),
96 for i, test := range tests {
97 // Insert a bunch of keys.
98 testTreap := NewMutable()
99 for i := 0; i < test.numKeys; i += test.step {
100 key := serializeUint32(uint32(i))
101 testTreap.Put(key, key)
104 // Create new iterator limited by the test params.
105 iter := testTreap.Iterator(test.startKey, test.limitKey)
107 // Ensure the first item is accurate.
108 hasFirst := iter.First()
109 if !hasFirst && test.expectedFirst != nil {
110 t.Errorf("First #%d: unexpected exhausted iterator", i)
114 if !bytes.Equal(gotKey, test.expectedFirst) {
115 t.Errorf("First.Key #%d: unexpected key - got %x, "+
116 "want %x", i, gotKey, test.expectedFirst)
119 gotVal := iter.Value()
120 if !bytes.Equal(gotVal, test.expectedFirst) {
121 t.Errorf("First.Value #%d: unexpected value - got %x, "+
122 "want %x", i, gotVal, test.expectedFirst)
126 // Ensure the iterator gives the expected items in order.
127 curNum := binary.BigEndian.Uint32(test.expectedFirst)
129 curNum += uint32(test.step)
131 // Ensure key is as expected.
133 expectedKey := serializeUint32(curNum)
134 if !bytes.Equal(gotKey, expectedKey) {
135 t.Errorf("iter.Key #%d (%d): unexpected key - "+
136 "got %x, want %x", i, curNum, gotKey,
141 // Ensure value is as expected.
142 gotVal := iter.Value()
143 if !bytes.Equal(gotVal, expectedKey) {
144 t.Errorf("iter.Value #%d (%d): unexpected "+
145 "value - got %x, want %x", i, curNum,
151 // Ensure iterator is exhausted.
153 t.Errorf("Valid #%d: iterator should be exhausted", i)
157 // Ensure the last item is accurate.
158 hasLast := iter.Last()
159 if !hasLast && test.expectedLast != nil {
160 t.Errorf("Last #%d: unexpected exhausted iterator", i)
164 if !bytes.Equal(gotKey, test.expectedLast) {
165 t.Errorf("Last.Key #%d: unexpected key - got %x, "+
166 "want %x", i, gotKey, test.expectedLast)
169 gotVal = iter.Value()
170 if !bytes.Equal(gotVal, test.expectedLast) {
171 t.Errorf("Last.Value #%d: unexpected value - got %x, "+
172 "want %x", i, gotVal, test.expectedLast)
176 // Ensure the iterator gives the expected items in reverse
178 curNum = binary.BigEndian.Uint32(test.expectedLast)
180 curNum -= uint32(test.step)
182 // Ensure key is as expected.
184 expectedKey := serializeUint32(curNum)
185 if !bytes.Equal(gotKey, expectedKey) {
186 t.Errorf("iter.Key #%d (%d): unexpected key - "+
187 "got %x, want %x", i, curNum, gotKey,
192 // Ensure value is as expected.
193 gotVal := iter.Value()
194 if !bytes.Equal(gotVal, expectedKey) {
195 t.Errorf("iter.Value #%d (%d): unexpected "+
196 "value - got %x, want %x", i, curNum,
202 // Ensure iterator is exhausted.
204 t.Errorf("Valid #%d: iterator should be exhausted", i)
208 // Seek to the provided key.
209 seekValid := iter.Seek(test.seekKey)
210 if !seekValid && test.expectedSeek != nil {
211 t.Errorf("Seek #%d: unexpected exhausted iterator", i)
215 if !bytes.Equal(gotKey, test.expectedSeek) {
216 t.Errorf("Seek.Key #%d: unexpected key - got %x, "+
217 "want %x", i, gotKey, test.expectedSeek)
220 gotVal = iter.Value()
221 if !bytes.Equal(gotVal, test.expectedSeek) {
222 t.Errorf("Seek.Value #%d: unexpected value - got %x, "+
223 "want %x", i, gotVal, test.expectedSeek)
227 // Recreate the iterator and ensure calling Next on it before it
228 // has been positioned gives the first element.
229 iter = testTreap.Iterator(test.startKey, test.limitKey)
230 hasNext := iter.Next()
231 if !hasNext && test.expectedFirst != nil {
232 t.Errorf("Next #%d: unexpected exhausted iterator", i)
236 if !bytes.Equal(gotKey, test.expectedFirst) {
237 t.Errorf("Next.Key #%d: unexpected key - got %x, "+
238 "want %x", i, gotKey, test.expectedFirst)
241 gotVal = iter.Value()
242 if !bytes.Equal(gotVal, test.expectedFirst) {
243 t.Errorf("Next.Value #%d: unexpected value - got %x, "+
244 "want %x", i, gotVal, test.expectedFirst)
248 // Recreate the iterator and ensure calling Prev on it before it
249 // has been positioned gives the first element.
250 iter = testTreap.Iterator(test.startKey, test.limitKey)
251 hasPrev := iter.Prev()
252 if !hasPrev && test.expectedLast != nil {
253 t.Errorf("Prev #%d: unexpected exhausted iterator", i)
257 if !bytes.Equal(gotKey, test.expectedLast) {
258 t.Errorf("Prev.Key #%d: unexpected key - got %x, "+
259 "want %x", i, gotKey, test.expectedLast)
262 gotVal = iter.Value()
263 if !bytes.Equal(gotVal, test.expectedLast) {
264 t.Errorf("Next.Value #%d: unexpected value - got %x, "+
265 "want %x", i, gotVal, test.expectedLast)
271 // TestMutableEmptyIterator ensures that the various functions behave as
272 // expected when a mutable treap is empty.
273 func TestMutableEmptyIterator(t *testing.T) {
276 // Create iterator against empty treap.
277 testTreap := NewMutable()
278 iter := testTreap.Iterator(nil, nil)
280 // Ensure Valid on empty iterator reports it as exhausted.
282 t.Fatal("Valid: iterator should be exhausted")
285 // Ensure First and Last on empty iterator report it as exhausted.
287 t.Fatal("First: iterator should be exhausted")
290 t.Fatal("Last: iterator should be exhausted")
293 // Ensure Next and Prev on empty iterator report it as exhausted.
295 t.Fatal("Next: iterator should be exhausted")
298 t.Fatal("Prev: iterator should be exhausted")
301 // Ensure Key and Value on empty iterator are nil.
302 if gotKey := iter.Key(); gotKey != nil {
303 t.Fatalf("Key: should be nil - got %q", gotKey)
305 if gotVal := iter.Value(); gotVal != nil {
306 t.Fatalf("Value: should be nil - got %q", gotVal)
309 // Ensure Next and Prev report exhausted after forcing a reseek on an
313 t.Fatal("Next: iterator should be exhausted")
317 t.Fatal("Prev: iterator should be exhausted")
321 // TestIteratorUpdates ensures that issuing a call to ForceReseek on an iterator
322 // that had the underlying mutable treap updated works as expected.
323 func TestIteratorUpdates(t *testing.T) {
326 // Create a new treap with various values inserted in no particular
327 // order. The resulting keys are the set (2, 4, 7, 11, 18, 25).
328 testTreap := NewMutable()
329 testTreap.Put(serializeUint32(7), nil)
330 testTreap.Put(serializeUint32(2), nil)
331 testTreap.Put(serializeUint32(18), nil)
332 testTreap.Put(serializeUint32(11), nil)
333 testTreap.Put(serializeUint32(25), nil)
334 testTreap.Put(serializeUint32(4), nil)
336 // Create an iterator against the treap with a range that excludes the
337 // lowest and highest entries. The limited set is then (4, 7, 11, 18)
338 iter := testTreap.Iterator(serializeUint32(3), serializeUint32(25))
340 // Delete a key from the middle of the range and notify the iterator to
342 testTreap.Delete(serializeUint32(11))
345 // Ensure that calling Next on the iterator after the forced reseek
346 // gives the expected key. The limited set of keys at this point is
347 // (4, 7, 18) and the iterator has not yet been positioned.
349 t.Fatal("ForceReseek.Next: unexpected exhausted iterator")
351 wantKey := serializeUint32(4)
353 if !bytes.Equal(gotKey, wantKey) {
354 t.Fatalf("ForceReseek.Key: unexpected key - got %x, want %x",
358 // Delete the key the iterator is currently position at and notify the
359 // iterator to force a reseek.
360 testTreap.Delete(serializeUint32(4))
363 // Ensure that calling Next on the iterator after the forced reseek
364 // gives the expected key. The limited set of keys at this point is
365 // (7, 18) and the iterator is positioned at a deleted entry before 7.
367 t.Fatal("ForceReseek.Next: unexpected exhausted iterator")
369 wantKey = serializeUint32(7)
371 if !bytes.Equal(gotKey, wantKey) {
372 t.Fatalf("ForceReseek.Key: unexpected key - got %x, want %x",
376 // Add a key before the current key the iterator is position at and
377 // notify the iterator to force a reseek.
378 testTreap.Put(serializeUint32(4), nil)
381 // Ensure that calling Prev on the iterator after the forced reseek
382 // gives the expected key. The limited set of keys at this point is
383 // (4, 7, 18) and the iterator is positioned at 7.
385 t.Fatal("ForceReseek.Prev: unexpected exhausted iterator")
387 wantKey = serializeUint32(4)
389 if !bytes.Equal(gotKey, wantKey) {
390 t.Fatalf("ForceReseek.Key: unexpected key - got %x, want %x",
394 // Delete the next key the iterator would ordinarily move to then notify
395 // the iterator to force a reseek.
396 testTreap.Delete(serializeUint32(7))
399 // Ensure that calling Next on the iterator after the forced reseek
400 // gives the expected key. The limited set of keys at this point is
401 // (4, 18) and the iterator is positioned at 4.
403 t.Fatal("ForceReseek.Next: unexpected exhausted iterator")
405 wantKey = serializeUint32(18)
407 if !bytes.Equal(gotKey, wantKey) {
408 t.Fatalf("ForceReseek.Key: unexpected key - got %x, want %x",
413 // TestImmutableIterator ensures that the general behavior of immutable treap
414 // iterators is as expected including tests for first, last, ordered and reverse
415 // ordered iteration, limiting the range, seeking, and initially unpositioned.
416 func TestImmutableIterator(t *testing.T) {
429 // No range limits. Values are the set (0, 1, 2, ..., 49).
430 // Seek existing value.
434 expectedFirst: serializeUint32(0),
435 expectedLast: serializeUint32(49),
436 seekKey: serializeUint32(12),
437 expectedSeek: serializeUint32(12),
440 // Limited to range [24, end]. Values are the set
441 // (0, 2, 4, ..., 48). Seek value that doesn't exist and is
442 // greater than largest existing key.
446 startKey: serializeUint32(24),
447 expectedFirst: serializeUint32(24),
448 expectedLast: serializeUint32(48),
449 seekKey: serializeUint32(49),
453 // Limited to range [start, 25). Values are the set
454 // (0, 3, 6, ..., 48). Seek value that doesn't exist but is
455 // before an existing value within the range.
459 limitKey: serializeUint32(25),
460 expectedFirst: serializeUint32(0),
461 expectedLast: serializeUint32(24),
462 seekKey: serializeUint32(17),
463 expectedSeek: serializeUint32(18),
466 // Limited to range [10, 21). Values are the set
467 // (0, 4, ..., 48). Seek value that exists, but is before the
468 // minimum allowed range.
472 startKey: serializeUint32(10),
473 limitKey: serializeUint32(21),
474 expectedFirst: serializeUint32(12),
475 expectedLast: serializeUint32(20),
476 seekKey: serializeUint32(4),
480 // Limited by prefix {0,0,0}, range [{0,0,0}, {0,0,1}).
481 // Since it's a bytewise compare, {0,0,0,...} < {0,0,1}.
482 // Seek existing value within the allowed range.
486 startKey: []byte{0x00, 0x00, 0x00},
487 limitKey: []byte{0x00, 0x00, 0x01},
488 expectedFirst: serializeUint32(0),
489 expectedLast: serializeUint32(255),
490 seekKey: serializeUint32(100),
491 expectedSeek: serializeUint32(100),
496 for i, test := range tests {
497 // Insert a bunch of keys.
498 testTreap := NewImmutable()
499 for i := 0; i < test.numKeys; i += test.step {
500 key := serializeUint32(uint32(i))
501 testTreap = testTreap.Put(key, key)
504 // Create new iterator limited by the test params.
505 iter := testTreap.Iterator(test.startKey, test.limitKey)
507 // Ensure the first item is accurate.
508 hasFirst := iter.First()
509 if !hasFirst && test.expectedFirst != nil {
510 t.Errorf("First #%d: unexpected exhausted iterator", i)
514 if !bytes.Equal(gotKey, test.expectedFirst) {
515 t.Errorf("First.Key #%d: unexpected key - got %x, "+
516 "want %x", i, gotKey, test.expectedFirst)
519 gotVal := iter.Value()
520 if !bytes.Equal(gotVal, test.expectedFirst) {
521 t.Errorf("First.Value #%d: unexpected value - got %x, "+
522 "want %x", i, gotVal, test.expectedFirst)
526 // Ensure the iterator gives the expected items in order.
527 curNum := binary.BigEndian.Uint32(test.expectedFirst)
529 curNum += uint32(test.step)
531 // Ensure key is as expected.
533 expectedKey := serializeUint32(curNum)
534 if !bytes.Equal(gotKey, expectedKey) {
535 t.Errorf("iter.Key #%d (%d): unexpected key - "+
536 "got %x, want %x", i, curNum, gotKey,
541 // Ensure value is as expected.
542 gotVal := iter.Value()
543 if !bytes.Equal(gotVal, expectedKey) {
544 t.Errorf("iter.Value #%d (%d): unexpected "+
545 "value - got %x, want %x", i, curNum,
551 // Ensure iterator is exhausted.
553 t.Errorf("Valid #%d: iterator should be exhausted", i)
557 // Ensure the last item is accurate.
558 hasLast := iter.Last()
559 if !hasLast && test.expectedLast != nil {
560 t.Errorf("Last #%d: unexpected exhausted iterator", i)
564 if !bytes.Equal(gotKey, test.expectedLast) {
565 t.Errorf("Last.Key #%d: unexpected key - got %x, "+
566 "want %x", i, gotKey, test.expectedLast)
569 gotVal = iter.Value()
570 if !bytes.Equal(gotVal, test.expectedLast) {
571 t.Errorf("Last.Value #%d: unexpected value - got %x, "+
572 "want %x", i, gotVal, test.expectedLast)
576 // Ensure the iterator gives the expected items in reverse
578 curNum = binary.BigEndian.Uint32(test.expectedLast)
580 curNum -= uint32(test.step)
582 // Ensure key is as expected.
584 expectedKey := serializeUint32(curNum)
585 if !bytes.Equal(gotKey, expectedKey) {
586 t.Errorf("iter.Key #%d (%d): unexpected key - "+
587 "got %x, want %x", i, curNum, gotKey,
592 // Ensure value is as expected.
593 gotVal := iter.Value()
594 if !bytes.Equal(gotVal, expectedKey) {
595 t.Errorf("iter.Value #%d (%d): unexpected "+
596 "value - got %x, want %x", i, curNum,
602 // Ensure iterator is exhausted.
604 t.Errorf("Valid #%d: iterator should be exhausted", i)
608 // Seek to the provided key.
609 seekValid := iter.Seek(test.seekKey)
610 if !seekValid && test.expectedSeek != nil {
611 t.Errorf("Seek #%d: unexpected exhausted iterator", i)
615 if !bytes.Equal(gotKey, test.expectedSeek) {
616 t.Errorf("Seek.Key #%d: unexpected key - got %x, "+
617 "want %x", i, gotKey, test.expectedSeek)
620 gotVal = iter.Value()
621 if !bytes.Equal(gotVal, test.expectedSeek) {
622 t.Errorf("Seek.Value #%d: unexpected value - got %x, "+
623 "want %x", i, gotVal, test.expectedSeek)
627 // Recreate the iterator and ensure calling Next on it before it
628 // has been positioned gives the first element.
629 iter = testTreap.Iterator(test.startKey, test.limitKey)
630 hasNext := iter.Next()
631 if !hasNext && test.expectedFirst != nil {
632 t.Errorf("Next #%d: unexpected exhausted iterator", i)
636 if !bytes.Equal(gotKey, test.expectedFirst) {
637 t.Errorf("Next.Key #%d: unexpected key - got %x, "+
638 "want %x", i, gotKey, test.expectedFirst)
641 gotVal = iter.Value()
642 if !bytes.Equal(gotVal, test.expectedFirst) {
643 t.Errorf("Next.Value #%d: unexpected value - got %x, "+
644 "want %x", i, gotVal, test.expectedFirst)
648 // Recreate the iterator and ensure calling Prev on it before it
649 // has been positioned gives the first element.
650 iter = testTreap.Iterator(test.startKey, test.limitKey)
651 hasPrev := iter.Prev()
652 if !hasPrev && test.expectedLast != nil {
653 t.Errorf("Prev #%d: unexpected exhausted iterator", i)
657 if !bytes.Equal(gotKey, test.expectedLast) {
658 t.Errorf("Prev.Key #%d: unexpected key - got %x, "+
659 "want %x", i, gotKey, test.expectedLast)
662 gotVal = iter.Value()
663 if !bytes.Equal(gotVal, test.expectedLast) {
664 t.Errorf("Next.Value #%d: unexpected value - got %x, "+
665 "want %x", i, gotVal, test.expectedLast)
671 // TestImmutableEmptyIterator ensures that the various functions behave as
672 // expected when an immutable treap is empty.
673 func TestImmutableEmptyIterator(t *testing.T) {
676 // Create iterator against empty treap.
677 testTreap := NewImmutable()
678 iter := testTreap.Iterator(nil, nil)
680 // Ensure Valid on empty iterator reports it as exhausted.
682 t.Fatal("Valid: iterator should be exhausted")
685 // Ensure First and Last on empty iterator report it as exhausted.
687 t.Fatal("First: iterator should be exhausted")
690 t.Fatal("Last: iterator should be exhausted")
693 // Ensure Next and Prev on empty iterator report it as exhausted.
695 t.Fatal("Next: iterator should be exhausted")
698 t.Fatal("Prev: iterator should be exhausted")
701 // Ensure Key and Value on empty iterator are nil.
702 if gotKey := iter.Key(); gotKey != nil {
703 t.Fatalf("Key: should be nil - got %q", gotKey)
705 if gotVal := iter.Value(); gotVal != nil {
706 t.Fatalf("Value: should be nil - got %q", gotVal)
709 // Ensure calling ForceReseek on an immutable treap iterator does not
710 // cause any issues since it only applies to mutable treap iterators.
713 t.Fatal("Next: iterator should be exhausted")
717 t.Fatal("Prev: iterator should be exhausted")