720 lines
21 KiB
Go
720 lines
21 KiB
Go
|
// Copyright (c) 2015-2016 The btcsuite developers
|
||
|
|
// Use of this source code is governed by an ISC
|
||
|
|
// license that can be found in the LICENSE file.
|
||
|
|
|
||
|
|
package treap
|
||
|
|
|
||
|
|
import (
|
||
|
|
"bytes"
|
||
|
|
"encoding/binary"
|
||
|
|
"testing"
|
||
|
|
)
|
||
|
|
|
||
|
|
// TestMutableIterator ensures that the general behavior of mutable treap
|
||
|
|
// iterators is as expected including tests for first, last, ordered and reverse
|
||
|
|
// ordered iteration, limiting the range, seeking, and initially unpositioned.
|
||
|
|
func TestMutableIterator(t *testing.T) {
|
||
|
|
t.Parallel()
|
||
|
|
|
||
|
|
tests := []struct {
|
||
|
|
numKeys int
|
||
|
|
step int
|
||
|
|
startKey []byte
|
||
|
|
limitKey []byte
|
||
|
|
expectedFirst []byte
|
||
|
|
expectedLast []byte
|
||
|
|
seekKey []byte
|
||
|
|
expectedSeek []byte
|
||
|
|
}{
|
||
|
|
// No range limits. Values are the set (0, 1, 2, ..., 49).
|
||
|
|
// Seek existing value.
|
||
|
|
{
|
||
|
|
numKeys: 50,
|
||
|
|
step: 1,
|
||
|
|
expectedFirst: serializeUint32(0),
|
||
|
|
expectedLast: serializeUint32(49),
|
||
|
|
seekKey: serializeUint32(12),
|
||
|
|
expectedSeek: serializeUint32(12),
|
||
|
|
},
|
||
|
|
|
||
|
|
// Limited to range [24, end]. Values are the set
|
||
|
|
// (0, 2, 4, ..., 48). Seek value that doesn't exist and is
|
||
|
|
// greater than largest existing key.
|
||
|
|
{
|
||
|
|
numKeys: 50,
|
||
|
|
step: 2,
|
||
|
|
startKey: serializeUint32(24),
|
||
|
|
expectedFirst: serializeUint32(24),
|
||
|
|
expectedLast: serializeUint32(48),
|
||
|
|
seekKey: serializeUint32(49),
|
||
|
|
expectedSeek: nil,
|
||
|
|
},
|
||
|
|
|
||
|
|
// Limited to range [start, 25). Values are the set
|
||
|
|
// (0, 3, 6, ..., 48). Seek value that doesn't exist but is
|
||
|
|
// before an existing value within the range.
|
||
|
|
{
|
||
|
|
numKeys: 50,
|
||
|
|
step: 3,
|
||
|
|
limitKey: serializeUint32(25),
|
||
|
|
expectedFirst: serializeUint32(0),
|
||
|
|
expectedLast: serializeUint32(24),
|
||
|
|
seekKey: serializeUint32(17),
|
||
|
|
expectedSeek: serializeUint32(18),
|
||
|
|
},
|
||
|
|
|
||
|
|
// Limited to range [10, 21). Values are the set
|
||
|
|
// (0, 4, ..., 48). Seek value that exists, but is before the
|
||
|
|
// minimum allowed range.
|
||
|
|
{
|
||
|
|
numKeys: 50,
|
||
|
|
step: 4,
|
||
|
|
startKey: serializeUint32(10),
|
||
|
|
limitKey: serializeUint32(21),
|
||
|
|
expectedFirst: serializeUint32(12),
|
||
|
|
expectedLast: serializeUint32(20),
|
||
|
|
seekKey: serializeUint32(4),
|
||
|
|
expectedSeek: nil,
|
||
|
|
},
|
||
|
|
|
||
|
|
// Limited by prefix {0,0,0}, range [{0,0,0}, {0,0,1}).
|
||
|
|
// Since it's a bytewise compare, {0,0,0,...} < {0,0,1}.
|
||
|
|
// Seek existing value within the allowed range.
|
||
|
|
{
|
||
|
|
numKeys: 300,
|
||
|
|
step: 1,
|
||
|
|
startKey: []byte{0x00, 0x00, 0x00},
|
||
|
|
limitKey: []byte{0x00, 0x00, 0x01},
|
||
|
|
expectedFirst: serializeUint32(0),
|
||
|
|
expectedLast: serializeUint32(255),
|
||
|
|
seekKey: serializeUint32(100),
|
||
|
|
expectedSeek: serializeUint32(100),
|
||
|
|
},
|
||
|
|
}
|
||
|
|
|
||
|
|
testLoop:
|
||
|
|
for i, test := range tests {
|
||
|
|
// Insert a bunch of keys.
|
||
|
|
testTreap := NewMutable()
|
||
|
|
for i := 0; i < test.numKeys; i += test.step {
|
||
|
|
key := serializeUint32(uint32(i))
|
||
|
|
testTreap.Put(key, key)
|
||
|
|
}
|
||
|
|
|
||
|
|
// Create new iterator limited by the test params.
|
||
|
|
iter := testTreap.Iterator(test.startKey, test.limitKey)
|
||
|
|
|
||
|
|
// Ensure the first item is accurate.
|
||
|
|
hasFirst := iter.First()
|
||
|
|
if !hasFirst && test.expectedFirst != nil {
|
||
|
|
t.Errorf("First #%d: unexpected exhausted iterator", i)
|
||
|
|
continue
|
||
|
|
}
|
||
|
|
gotKey := iter.Key()
|
||
|
|
if !bytes.Equal(gotKey, test.expectedFirst) {
|
||
|
|
t.Errorf("First.Key #%d: unexpected key - got %x, "+
|
||
|
|
"want %x", i, gotKey, test.expectedFirst)
|
||
|
|
continue
|
||
|
|
}
|
||
|
|
gotVal := iter.Value()
|
||
|
|
if !bytes.Equal(gotVal, test.expectedFirst) {
|
||
|
|
t.Errorf("First.Value #%d: unexpected value - got %x, "+
|
||
|
|
"want %x", i, gotVal, test.expectedFirst)
|
||
|
|
continue
|
||
|
|
}
|
||
|
|
|
||
|
|
// Ensure the iterator gives the expected items in order.
|
||
|
|
curNum := binary.BigEndian.Uint32(test.expectedFirst)
|
||
|
|
for iter.Next() {
|
||
|
|
curNum += uint32(test.step)
|
||
|
|
|
||
|
|
// Ensure key is as expected.
|
||
|
|
gotKey := iter.Key()
|
||
|
|
expectedKey := serializeUint32(curNum)
|
||
|
|
if !bytes.Equal(gotKey, expectedKey) {
|
||
|
|
t.Errorf("iter.Key #%d (%d): unexpected key - "+
|
||
|
|
"got %x, want %x", i, curNum, gotKey,
|
||
|
|
expectedKey)
|
||
|
|
continue testLoop
|
||
|
|
}
|
||
|
|
|
||
|
|
// Ensure value is as expected.
|
||
|
|
gotVal := iter.Value()
|
||
|
|
if !bytes.Equal(gotVal, expectedKey) {
|
||
|
|
t.Errorf("iter.Value #%d (%d): unexpected "+
|
||
|
|
"value - got %x, want %x", i, curNum,
|
||
|
|
gotVal, expectedKey)
|
||
|
|
continue testLoop
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
// Ensure iterator is exhausted.
|
||
|
|
if iter.Valid() {
|
||
|
|
t.Errorf("Valid #%d: iterator should be exhausted", i)
|
||
|
|
continue
|
||
|
|
}
|
||
|
|
|
||
|
|
// Ensure the last item is accurate.
|
||
|
|
hasLast := iter.Last()
|
||
|
|
if !hasLast && test.expectedLast != nil {
|
||
|
|
t.Errorf("Last #%d: unexpected exhausted iterator", i)
|
||
|
|
continue
|
||
|
|
}
|
||
|
|
gotKey = iter.Key()
|
||
|
|
if !bytes.Equal(gotKey, test.expectedLast) {
|
||
|
|
t.Errorf("Last.Key #%d: unexpected key - got %x, "+
|
||
|
|
"want %x", i, gotKey, test.expectedLast)
|
||
|
|
continue
|
||
|
|
}
|
||
|
|
gotVal = iter.Value()
|
||
|
|
if !bytes.Equal(gotVal, test.expectedLast) {
|
||
|
|
t.Errorf("Last.Value #%d: unexpected value - got %x, "+
|
||
|
|
"want %x", i, gotVal, test.expectedLast)
|
||
|
|
continue
|
||
|
|
}
|
||
|
|
|
||
|
|
// Ensure the iterator gives the expected items in reverse
|
||
|
|
// order.
|
||
|
|
curNum = binary.BigEndian.Uint32(test.expectedLast)
|
||
|
|
for iter.Prev() {
|
||
|
|
curNum -= uint32(test.step)
|
||
|
|
|
||
|
|
// Ensure key is as expected.
|
||
|
|
gotKey := iter.Key()
|
||
|
|
expectedKey := serializeUint32(curNum)
|
||
|
|
if !bytes.Equal(gotKey, expectedKey) {
|
||
|
|
t.Errorf("iter.Key #%d (%d): unexpected key - "+
|
||
|
|
"got %x, want %x", i, curNum, gotKey,
|
||
|
|
expectedKey)
|
||
|
|
continue testLoop
|
||
|
|
}
|
||
|
|
|
||
|
|
// Ensure value is as expected.
|
||
|
|
gotVal := iter.Value()
|
||
|
|
if !bytes.Equal(gotVal, expectedKey) {
|
||
|
|
t.Errorf("iter.Value #%d (%d): unexpected "+
|
||
|
|
"value - got %x, want %x", i, curNum,
|
||
|
|
gotVal, expectedKey)
|
||
|
|
continue testLoop
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
// Ensure iterator is exhausted.
|
||
|
|
if iter.Valid() {
|
||
|
|
t.Errorf("Valid #%d: iterator should be exhausted", i)
|
||
|
|
continue
|
||
|
|
}
|
||
|
|
|
||
|
|
// Seek to the provided key.
|
||
|
|
seekValid := iter.Seek(test.seekKey)
|
||
|
|
if !seekValid && test.expectedSeek != nil {
|
||
|
|
t.Errorf("Seek #%d: unexpected exhausted iterator", i)
|
||
|
|
continue
|
||
|
|
}
|
||
|
|
gotKey = iter.Key()
|
||
|
|
if !bytes.Equal(gotKey, test.expectedSeek) {
|
||
|
|
t.Errorf("Seek.Key #%d: unexpected key - got %x, "+
|
||
|
|
"want %x", i, gotKey, test.expectedSeek)
|
||
|
|
continue
|
||
|
|
}
|
||
|
|
gotVal = iter.Value()
|
||
|
|
if !bytes.Equal(gotVal, test.expectedSeek) {
|
||
|
|
t.Errorf("Seek.Value #%d: unexpected value - got %x, "+
|
||
|
|
"want %x", i, gotVal, test.expectedSeek)
|
||
|
|
continue
|
||
|
|
}
|
||
|
|
|
||
|
|
// Recreate the iterator and ensure calling Next on it before it
|
||
|
|
// has been positioned gives the first element.
|
||
|
|
iter = testTreap.Iterator(test.startKey, test.limitKey)
|
||
|
|
hasNext := iter.Next()
|
||
|
|
if !hasNext && test.expectedFirst != nil {
|
||
|
|
t.Errorf("Next #%d: unexpected exhausted iterator", i)
|
||
|
|
continue
|
||
|
|
}
|
||
|
|
gotKey = iter.Key()
|
||
|
|
if !bytes.Equal(gotKey, test.expectedFirst) {
|
||
|
|
t.Errorf("Next.Key #%d: unexpected key - got %x, "+
|
||
|
|
"want %x", i, gotKey, test.expectedFirst)
|
||
|
|
continue
|
||
|
|
}
|
||
|
|
gotVal = iter.Value()
|
||
|
|
if !bytes.Equal(gotVal, test.expectedFirst) {
|
||
|
|
t.Errorf("Next.Value #%d: unexpected value - got %x, "+
|
||
|
|
"want %x", i, gotVal, test.expectedFirst)
|
||
|
|
continue
|
||
|
|
}
|
||
|
|
|
||
|
|
// Recreate the iterator and ensure calling Prev on it before it
|
||
|
|
// has been positioned gives the first element.
|
||
|
|
iter = testTreap.Iterator(test.startKey, test.limitKey)
|
||
|
|
hasPrev := iter.Prev()
|
||
|
|
if !hasPrev && test.expectedLast != nil {
|
||
|
|
t.Errorf("Prev #%d: unexpected exhausted iterator", i)
|
||
|
|
continue
|
||
|
|
}
|
||
|
|
gotKey = iter.Key()
|
||
|
|
if !bytes.Equal(gotKey, test.expectedLast) {
|
||
|
|
t.Errorf("Prev.Key #%d: unexpected key - got %x, "+
|
||
|
|
"want %x", i, gotKey, test.expectedLast)
|
||
|
|
continue
|
||
|
|
}
|
||
|
|
gotVal = iter.Value()
|
||
|
|
if !bytes.Equal(gotVal, test.expectedLast) {
|
||
|
|
t.Errorf("Next.Value #%d: unexpected value - got %x, "+
|
||
|
|
"want %x", i, gotVal, test.expectedLast)
|
||
|
|
continue
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
// TestMutableEmptyIterator ensures that the various functions behave as
|
||
|
|
// expected when a mutable treap is empty.
|
||
|
|
func TestMutableEmptyIterator(t *testing.T) {
|
||
|
|
t.Parallel()
|
||
|
|
|
||
|
|
// Create iterator against empty treap.
|
||
|
|
testTreap := NewMutable()
|
||
|
|
iter := testTreap.Iterator(nil, nil)
|
||
|
|
|
||
|
|
// Ensure Valid on empty iterator reports it as exhausted.
|
||
|
|
if iter.Valid() {
|
||
|
|
t.Fatal("Valid: iterator should be exhausted")
|
||
|
|
}
|
||
|
|
|
||
|
|
// Ensure First and Last on empty iterator report it as exhausted.
|
||
|
|
if iter.First() {
|
||
|
|
t.Fatal("First: iterator should be exhausted")
|
||
|
|
}
|
||
|
|
if iter.Last() {
|
||
|
|
t.Fatal("Last: iterator should be exhausted")
|
||
|
|
}
|
||
|
|
|
||
|
|
// Ensure Next and Prev on empty iterator report it as exhausted.
|
||
|
|
if iter.Next() {
|
||
|
|
t.Fatal("Next: iterator should be exhausted")
|
||
|
|
}
|
||
|
|
if iter.Prev() {
|
||
|
|
t.Fatal("Prev: iterator should be exhausted")
|
||
|
|
}
|
||
|
|
|
||
|
|
// Ensure Key and Value on empty iterator are nil.
|
||
|
|
if gotKey := iter.Key(); gotKey != nil {
|
||
|
|
t.Fatalf("Key: should be nil - got %q", gotKey)
|
||
|
|
}
|
||
|
|
if gotVal := iter.Value(); gotVal != nil {
|
||
|
|
t.Fatalf("Value: should be nil - got %q", gotVal)
|
||
|
|
}
|
||
|
|
|
||
|
|
// Ensure Next and Prev report exhausted after forcing a reseek on an
|
||
|
|
// empty iterator.
|
||
|
|
iter.ForceReseek()
|
||
|
|
if iter.Next() {
|
||
|
|
t.Fatal("Next: iterator should be exhausted")
|
||
|
|
}
|
||
|
|
iter.ForceReseek()
|
||
|
|
if iter.Prev() {
|
||
|
|
t.Fatal("Prev: iterator should be exhausted")
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
// TestIteratorUpdates ensures that issuing a call to ForceReseek on an iterator
|
||
|
|
// that had the underlying mutable treap updated works as expected.
|
||
|
|
func TestIteratorUpdates(t *testing.T) {
|
||
|
|
t.Parallel()
|
||
|
|
|
||
|
|
// Create a new treap with various values inserted in no particular
|
||
|
|
// order. The resulting keys are the set (2, 4, 7, 11, 18, 25).
|
||
|
|
testTreap := NewMutable()
|
||
|
|
testTreap.Put(serializeUint32(7), nil)
|
||
|
|
testTreap.Put(serializeUint32(2), nil)
|
||
|
|
testTreap.Put(serializeUint32(18), nil)
|
||
|
|
testTreap.Put(serializeUint32(11), nil)
|
||
|
|
testTreap.Put(serializeUint32(25), nil)
|
||
|
|
testTreap.Put(serializeUint32(4), nil)
|
||
|
|
|
||
|
|
// Create an iterator against the treap with a range that excludes the
|
||
|
|
// lowest and highest entries. The limited set is then (4, 7, 11, 18)
|
||
|
|
iter := testTreap.Iterator(serializeUint32(3), serializeUint32(25))
|
||
|
|
|
||
|
|
// Delete a key from the middle of the range and notify the iterator to
|
||
|
|
// force a reseek.
|
||
|
|
testTreap.Delete(serializeUint32(11))
|
||
|
|
iter.ForceReseek()
|
||
|
|
|
||
|
|
// Ensure that calling Next on the iterator after the forced reseek
|
||
|
|
// gives the expected key. The limited set of keys at this point is
|
||
|
|
// (4, 7, 18) and the iterator has not yet been positioned.
|
||
|
|
if !iter.Next() {
|
||
|
|
t.Fatal("ForceReseek.Next: unexpected exhausted iterator")
|
||
|
|
}
|
||
|
|
wantKey := serializeUint32(4)
|
||
|
|
gotKey := iter.Key()
|
||
|
|
if !bytes.Equal(gotKey, wantKey) {
|
||
|
|
t.Fatalf("ForceReseek.Key: unexpected key - got %x, want %x",
|
||
|
|
gotKey, wantKey)
|
||
|
|
}
|
||
|
|
|
||
|
|
// Delete the key the iterator is currently position at and notify the
|
||
|
|
// iterator to force a reseek.
|
||
|
|
testTreap.Delete(serializeUint32(4))
|
||
|
|
iter.ForceReseek()
|
||
|
|
|
||
|
|
// Ensure that calling Next on the iterator after the forced reseek
|
||
|
|
// gives the expected key. The limited set of keys at this point is
|
||
|
|
// (7, 18) and the iterator is positioned at a deleted entry before 7.
|
||
|
|
if !iter.Next() {
|
||
|
|
t.Fatal("ForceReseek.Next: unexpected exhausted iterator")
|
||
|
|
}
|
||
|
|
wantKey = serializeUint32(7)
|
||
|
|
gotKey = iter.Key()
|
||
|
|
if !bytes.Equal(gotKey, wantKey) {
|
||
|
|
t.Fatalf("ForceReseek.Key: unexpected key - got %x, want %x",
|
||
|
|
gotKey, wantKey)
|
||
|
|
}
|
||
|
|
|
||
|
|
// Add a key before the current key the iterator is position at and
|
||
|
|
// notify the iterator to force a reseek.
|
||
|
|
testTreap.Put(serializeUint32(4), nil)
|
||
|
|
iter.ForceReseek()
|
||
|
|
|
||
|
|
// Ensure that calling Prev on the iterator after the forced reseek
|
||
|
|
// gives the expected key. The limited set of keys at this point is
|
||
|
|
// (4, 7, 18) and the iterator is positioned at 7.
|
||
|
|
if !iter.Prev() {
|
||
|
|
t.Fatal("ForceReseek.Prev: unexpected exhausted iterator")
|
||
|
|
}
|
||
|
|
wantKey = serializeUint32(4)
|
||
|
|
gotKey = iter.Key()
|
||
|
|
if !bytes.Equal(gotKey, wantKey) {
|
||
|
|
t.Fatalf("ForceReseek.Key: unexpected key - got %x, want %x",
|
||
|
|
gotKey, wantKey)
|
||
|
|
}
|
||
|
|
|
||
|
|
// Delete the next key the iterator would ordinarily move to then notify
|
||
|
|
// the iterator to force a reseek.
|
||
|
|
testTreap.Delete(serializeUint32(7))
|
||
|
|
iter.ForceReseek()
|
||
|
|
|
||
|
|
// Ensure that calling Next on the iterator after the forced reseek
|
||
|
|
// gives the expected key. The limited set of keys at this point is
|
||
|
|
// (4, 18) and the iterator is positioned at 4.
|
||
|
|
if !iter.Next() {
|
||
|
|
t.Fatal("ForceReseek.Next: unexpected exhausted iterator")
|
||
|
|
}
|
||
|
|
wantKey = serializeUint32(18)
|
||
|
|
gotKey = iter.Key()
|
||
|
|
if !bytes.Equal(gotKey, wantKey) {
|
||
|
|
t.Fatalf("ForceReseek.Key: unexpected key - got %x, want %x",
|
||
|
|
gotKey, wantKey)
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
// TestImmutableIterator ensures that the general behavior of immutable treap
|
||
|
|
// iterators is as expected including tests for first, last, ordered and reverse
|
||
|
|
// ordered iteration, limiting the range, seeking, and initially unpositioned.
|
||
|
|
func TestImmutableIterator(t *testing.T) {
|
||
|
|
t.Parallel()
|
||
|
|
|
||
|
|
tests := []struct {
|
||
|
|
numKeys int
|
||
|
|
step int
|
||
|
|
startKey []byte
|
||
|
|
limitKey []byte
|
||
|
|
expectedFirst []byte
|
||
|
|
expectedLast []byte
|
||
|
|
seekKey []byte
|
||
|
|
expectedSeek []byte
|
||
|
|
}{
|
||
|
|
// No range limits. Values are the set (0, 1, 2, ..., 49).
|
||
|
|
// Seek existing value.
|
||
|
|
{
|
||
|
|
numKeys: 50,
|
||
|
|
step: 1,
|
||
|
|
expectedFirst: serializeUint32(0),
|
||
|
|
expectedLast: serializeUint32(49),
|
||
|
|
seekKey: serializeUint32(12),
|
||
|
|
expectedSeek: serializeUint32(12),
|
||
|
|
},
|
||
|
|
|
||
|
|
// Limited to range [24, end]. Values are the set
|
||
|
|
// (0, 2, 4, ..., 48). Seek value that doesn't exist and is
|
||
|
|
// greater than largest existing key.
|
||
|
|
{
|
||
|
|
numKeys: 50,
|
||
|
|
step: 2,
|
||
|
|
startKey: serializeUint32(24),
|
||
|
|
expectedFirst: serializeUint32(24),
|
||
|
|
expectedLast: serializeUint32(48),
|
||
|
|
seekKey: serializeUint32(49),
|
||
|
|
expectedSeek: nil,
|
||
|
|
},
|
||
|
|
|
||
|
|
// Limited to range [start, 25). Values are the set
|
||
|
|
// (0, 3, 6, ..., 48). Seek value that doesn't exist but is
|
||
|
|
// before an existing value within the range.
|
||
|
|
{
|
||
|
|
numKeys: 50,
|
||
|
|
step: 3,
|
||
|
|
limitKey: serializeUint32(25),
|
||
|
|
expectedFirst: serializeUint32(0),
|
||
|
|
expectedLast: serializeUint32(24),
|
||
|
|
seekKey: serializeUint32(17),
|
||
|
|
expectedSeek: serializeUint32(18),
|
||
|
|
},
|
||
|
|
|
||
|
|
// Limited to range [10, 21). Values are the set
|
||
|
|
// (0, 4, ..., 48). Seek value that exists, but is before the
|
||
|
|
// minimum allowed range.
|
||
|
|
{
|
||
|
|
numKeys: 50,
|
||
|
|
step: 4,
|
||
|
|
startKey: serializeUint32(10),
|
||
|
|
limitKey: serializeUint32(21),
|
||
|
|
expectedFirst: serializeUint32(12),
|
||
|
|
expectedLast: serializeUint32(20),
|
||
|
|
seekKey: serializeUint32(4),
|
||
|
|
expectedSeek: nil,
|
||
|
|
},
|
||
|
|
|
||
|
|
// Limited by prefix {0,0,0}, range [{0,0,0}, {0,0,1}).
|
||
|
|
// Since it's a bytewise compare, {0,0,0,...} < {0,0,1}.
|
||
|
|
// Seek existing value within the allowed range.
|
||
|
|
{
|
||
|
|
numKeys: 300,
|
||
|
|
step: 1,
|
||
|
|
startKey: []byte{0x00, 0x00, 0x00},
|
||
|
|
limitKey: []byte{0x00, 0x00, 0x01},
|
||
|
|
expectedFirst: serializeUint32(0),
|
||
|
|
expectedLast: serializeUint32(255),
|
||
|
|
seekKey: serializeUint32(100),
|
||
|
|
expectedSeek: serializeUint32(100),
|
||
|
|
},
|
||
|
|
}
|
||
|
|
|
||
|
|
testLoop:
|
||
|
|
for i, test := range tests {
|
||
|
|
// Insert a bunch of keys.
|
||
|
|
testTreap := NewImmutable()
|
||
|
|
for i := 0; i < test.numKeys; i += test.step {
|
||
|
|
key := serializeUint32(uint32(i))
|
||
|
|
testTreap = testTreap.Put(key, key)
|
||
|
|
}
|
||
|
|
|
||
|
|
// Create new iterator limited by the test params.
|
||
|
|
iter := testTreap.Iterator(test.startKey, test.limitKey)
|
||
|
|
|
||
|
|
// Ensure the first item is accurate.
|
||
|
|
hasFirst := iter.First()
|
||
|
|
if !hasFirst && test.expectedFirst != nil {
|
||
|
|
t.Errorf("First #%d: unexpected exhausted iterator", i)
|
||
|
|
continue
|
||
|
|
}
|
||
|
|
gotKey := iter.Key()
|
||
|
|
if !bytes.Equal(gotKey, test.expectedFirst) {
|
||
|
|
t.Errorf("First.Key #%d: unexpected key - got %x, "+
|
||
|
|
"want %x", i, gotKey, test.expectedFirst)
|
||
|
|
continue
|
||
|
|
}
|
||
|
|
gotVal := iter.Value()
|
||
|
|
if !bytes.Equal(gotVal, test.expectedFirst) {
|
||
|
|
t.Errorf("First.Value #%d: unexpected value - got %x, "+
|
||
|
|
"want %x", i, gotVal, test.expectedFirst)
|
||
|
|
continue
|
||
|
|
}
|
||
|
|
|
||
|
|
// Ensure the iterator gives the expected items in order.
|
||
|
|
curNum := binary.BigEndian.Uint32(test.expectedFirst)
|
||
|
|
for iter.Next() {
|
||
|
|
curNum += uint32(test.step)
|
||
|
|
|
||
|
|
// Ensure key is as expected.
|
||
|
|
gotKey := iter.Key()
|
||
|
|
expectedKey := serializeUint32(curNum)
|
||
|
|
if !bytes.Equal(gotKey, expectedKey) {
|
||
|
|
t.Errorf("iter.Key #%d (%d): unexpected key - "+
|
||
|
|
"got %x, want %x", i, curNum, gotKey,
|
||
|
|
expectedKey)
|
||
|
|
continue testLoop
|
||
|
|
}
|
||
|
|
|
||
|
|
// Ensure value is as expected.
|
||
|
|
gotVal := iter.Value()
|
||
|
|
if !bytes.Equal(gotVal, expectedKey) {
|
||
|
|
t.Errorf("iter.Value #%d (%d): unexpected "+
|
||
|
|
"value - got %x, want %x", i, curNum,
|
||
|
|
gotVal, expectedKey)
|
||
|
|
continue testLoop
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
// Ensure iterator is exhausted.
|
||
|
|
if iter.Valid() {
|
||
|
|
t.Errorf("Valid #%d: iterator should be exhausted", i)
|
||
|
|
continue
|
||
|
|
}
|
||
|
|
|
||
|
|
// Ensure the last item is accurate.
|
||
|
|
hasLast := iter.Last()
|
||
|
|
if !hasLast && test.expectedLast != nil {
|
||
|
|
t.Errorf("Last #%d: unexpected exhausted iterator", i)
|
||
|
|
continue
|
||
|
|
}
|
||
|
|
gotKey = iter.Key()
|
||
|
|
if !bytes.Equal(gotKey, test.expectedLast) {
|
||
|
|
t.Errorf("Last.Key #%d: unexpected key - got %x, "+
|
||
|
|
"want %x", i, gotKey, test.expectedLast)
|
||
|
|
continue
|
||
|
|
}
|
||
|
|
gotVal = iter.Value()
|
||
|
|
if !bytes.Equal(gotVal, test.expectedLast) {
|
||
|
|
t.Errorf("Last.Value #%d: unexpected value - got %x, "+
|
||
|
|
"want %x", i, gotVal, test.expectedLast)
|
||
|
|
continue
|
||
|
|
}
|
||
|
|
|
||
|
|
// Ensure the iterator gives the expected items in reverse
|
||
|
|
// order.
|
||
|
|
curNum = binary.BigEndian.Uint32(test.expectedLast)
|
||
|
|
for iter.Prev() {
|
||
|
|
curNum -= uint32(test.step)
|
||
|
|
|
||
|
|
// Ensure key is as expected.
|
||
|
|
gotKey := iter.Key()
|
||
|
|
expectedKey := serializeUint32(curNum)
|
||
|
|
if !bytes.Equal(gotKey, expectedKey) {
|
||
|
|
t.Errorf("iter.Key #%d (%d): unexpected key - "+
|
||
|
|
"got %x, want %x", i, curNum, gotKey,
|
||
|
|
expectedKey)
|
||
|
|
continue testLoop
|
||
|
|
}
|
||
|
|
|
||
|
|
// Ensure value is as expected.
|
||
|
|
gotVal := iter.Value()
|
||
|
|
if !bytes.Equal(gotVal, expectedKey) {
|
||
|
|
t.Errorf("iter.Value #%d (%d): unexpected "+
|
||
|
|
"value - got %x, want %x", i, curNum,
|
||
|
|
gotVal, expectedKey)
|
||
|
|
continue testLoop
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
// Ensure iterator is exhausted.
|
||
|
|
if iter.Valid() {
|
||
|
|
t.Errorf("Valid #%d: iterator should be exhausted", i)
|
||
|
|
continue
|
||
|
|
}
|
||
|
|
|
||
|
|
// Seek to the provided key.
|
||
|
|
seekValid := iter.Seek(test.seekKey)
|
||
|
|
if !seekValid && test.expectedSeek != nil {
|
||
|
|
t.Errorf("Seek #%d: unexpected exhausted iterator", i)
|
||
|
|
continue
|
||
|
|
}
|
||
|
|
gotKey = iter.Key()
|
||
|
|
if !bytes.Equal(gotKey, test.expectedSeek) {
|
||
|
|
t.Errorf("Seek.Key #%d: unexpected key - got %x, "+
|
||
|
|
"want %x", i, gotKey, test.expectedSeek)
|
||
|
|
continue
|
||
|
|
}
|
||
|
|
gotVal = iter.Value()
|
||
|
|
if !bytes.Equal(gotVal, test.expectedSeek) {
|
||
|
|
t.Errorf("Seek.Value #%d: unexpected value - got %x, "+
|
||
|
|
"want %x", i, gotVal, test.expectedSeek)
|
||
|
|
continue
|
||
|
|
}
|
||
|
|
|
||
|
|
// Recreate the iterator and ensure calling Next on it before it
|
||
|
|
// has been positioned gives the first element.
|
||
|
|
iter = testTreap.Iterator(test.startKey, test.limitKey)
|
||
|
|
hasNext := iter.Next()
|
||
|
|
if !hasNext && test.expectedFirst != nil {
|
||
|
|
t.Errorf("Next #%d: unexpected exhausted iterator", i)
|
||
|
|
continue
|
||
|
|
}
|
||
|
|
gotKey = iter.Key()
|
||
|
|
if !bytes.Equal(gotKey, test.expectedFirst) {
|
||
|
|
t.Errorf("Next.Key #%d: unexpected key - got %x, "+
|
||
|
|
"want %x", i, gotKey, test.expectedFirst)
|
||
|
|
continue
|
||
|
|
}
|
||
|
|
gotVal = iter.Value()
|
||
|
|
if !bytes.Equal(gotVal, test.expectedFirst) {
|
||
|
|
t.Errorf("Next.Value #%d: unexpected value - got %x, "+
|
||
|
|
"want %x", i, gotVal, test.expectedFirst)
|
||
|
|
continue
|
||
|
|
}
|
||
|
|
|
||
|
|
// Recreate the iterator and ensure calling Prev on it before it
|
||
|
|
// has been positioned gives the first element.
|
||
|
|
iter = testTreap.Iterator(test.startKey, test.limitKey)
|
||
|
|
hasPrev := iter.Prev()
|
||
|
|
if !hasPrev && test.expectedLast != nil {
|
||
|
|
t.Errorf("Prev #%d: unexpected exhausted iterator", i)
|
||
|
|
continue
|
||
|
|
}
|
||
|
|
gotKey = iter.Key()
|
||
|
|
if !bytes.Equal(gotKey, test.expectedLast) {
|
||
|
|
t.Errorf("Prev.Key #%d: unexpected key - got %x, "+
|
||
|
|
"want %x", i, gotKey, test.expectedLast)
|
||
|
|
continue
|
||
|
|
}
|
||
|
|
gotVal = iter.Value()
|
||
|
|
if !bytes.Equal(gotVal, test.expectedLast) {
|
||
|
|
t.Errorf("Next.Value #%d: unexpected value - got %x, "+
|
||
|
|
"want %x", i, gotVal, test.expectedLast)
|
||
|
|
continue
|
||
|
|
}
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
// TestImmutableEmptyIterator ensures that the various functions behave as
|
||
|
|
// expected when an immutable treap is empty.
|
||
|
|
func TestImmutableEmptyIterator(t *testing.T) {
|
||
|
|
t.Parallel()
|
||
|
|
|
||
|
|
// Create iterator against empty treap.
|
||
|
|
testTreap := NewImmutable()
|
||
|
|
iter := testTreap.Iterator(nil, nil)
|
||
|
|
|
||
|
|
// Ensure Valid on empty iterator reports it as exhausted.
|
||
|
|
if iter.Valid() {
|
||
|
|
t.Fatal("Valid: iterator should be exhausted")
|
||
|
|
}
|
||
|
|
|
||
|
|
// Ensure First and Last on empty iterator report it as exhausted.
|
||
|
|
if iter.First() {
|
||
|
|
t.Fatal("First: iterator should be exhausted")
|
||
|
|
}
|
||
|
|
if iter.Last() {
|
||
|
|
t.Fatal("Last: iterator should be exhausted")
|
||
|
|
}
|
||
|
|
|
||
|
|
// Ensure Next and Prev on empty iterator report it as exhausted.
|
||
|
|
if iter.Next() {
|
||
|
|
t.Fatal("Next: iterator should be exhausted")
|
||
|
|
}
|
||
|
|
if iter.Prev() {
|
||
|
|
t.Fatal("Prev: iterator should be exhausted")
|
||
|
|
}
|
||
|
|
|
||
|
|
// Ensure Key and Value on empty iterator are nil.
|
||
|
|
if gotKey := iter.Key(); gotKey != nil {
|
||
|
|
t.Fatalf("Key: should be nil - got %q", gotKey)
|
||
|
|
}
|
||
|
|
if gotVal := iter.Value(); gotVal != nil {
|
||
|
|
t.Fatalf("Value: should be nil - got %q", gotVal)
|
||
|
|
}
|
||
|
|
|
||
|
|
// Ensure calling ForceReseek on an immutable treap iterator does not
|
||
|
|
// cause any issues since it only applies to mutable treap iterators.
|
||
|
|
iter.ForceReseek()
|
||
|
|
if iter.Next() {
|
||
|
|
t.Fatal("Next: iterator should be exhausted")
|
||
|
|
}
|
||
|
|
iter.ForceReseek()
|
||
|
|
if iter.Prev() {
|
||
|
|
t.Fatal("Prev: iterator should be exhausted")
|
||
|
|
}
|
||
|
|
}
|