Revision 3fae828623c194feb307c49c15d66dca9366e195 authored by Joe Betz on 10 October 2019, 17:59:40 UTC, committed by Joe Betz on 10 October 2019, 17:59:40 UTC
1 parent 011bd86
index_test.go
// Copyright 2015 The etcd Authors
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package mvcc
import (
"reflect"
"testing"
"github.com/google/btree"
)
func TestIndexGet(t *testing.T) {
ti := newTreeIndex()
ti.Put([]byte("foo"), revision{main: 2})
ti.Put([]byte("foo"), revision{main: 4})
ti.Tombstone([]byte("foo"), revision{main: 6})
tests := []struct {
rev int64
wrev revision
wcreated revision
wver int64
werr error
}{
{0, revision{}, revision{}, 0, ErrRevisionNotFound},
{1, revision{}, revision{}, 0, ErrRevisionNotFound},
{2, revision{main: 2}, revision{main: 2}, 1, nil},
{3, revision{main: 2}, revision{main: 2}, 1, nil},
{4, revision{main: 4}, revision{main: 2}, 2, nil},
{5, revision{main: 4}, revision{main: 2}, 2, nil},
{6, revision{}, revision{}, 0, ErrRevisionNotFound},
}
for i, tt := range tests {
rev, created, ver, err := ti.Get([]byte("foo"), tt.rev)
if err != tt.werr {
t.Errorf("#%d: err = %v, want %v", i, err, tt.werr)
}
if rev != tt.wrev {
t.Errorf("#%d: rev = %+v, want %+v", i, rev, tt.wrev)
}
if created != tt.wcreated {
t.Errorf("#%d: created = %+v, want %+v", i, created, tt.wcreated)
}
if ver != tt.wver {
t.Errorf("#%d: ver = %d, want %d", i, ver, tt.wver)
}
}
}
func TestIndexRange(t *testing.T) {
allKeys := [][]byte{[]byte("foo"), []byte("foo1"), []byte("foo2")}
allRevs := []revision{{main: 1}, {main: 2}, {main: 3}}
ti := newTreeIndex()
for i := range allKeys {
ti.Put(allKeys[i], allRevs[i])
}
atRev := int64(3)
tests := []struct {
key, end []byte
wkeys [][]byte
wrevs []revision
}{
// single key that not found
{
[]byte("bar"), nil, nil, nil,
},
// single key that found
{
[]byte("foo"), nil, allKeys[:1], allRevs[:1],
},
// range keys, return first member
{
[]byte("foo"), []byte("foo1"), allKeys[:1], allRevs[:1],
},
// range keys, return first two members
{
[]byte("foo"), []byte("foo2"), allKeys[:2], allRevs[:2],
},
// range keys, return all members
{
[]byte("foo"), []byte("fop"), allKeys, allRevs,
},
// range keys, return last two members
{
[]byte("foo1"), []byte("fop"), allKeys[1:], allRevs[1:],
},
// range keys, return last member
{
[]byte("foo2"), []byte("fop"), allKeys[2:], allRevs[2:],
},
// range keys, return nothing
{
[]byte("foo3"), []byte("fop"), nil, nil,
},
}
for i, tt := range tests {
keys, revs := ti.Range(tt.key, tt.end, atRev)
if !reflect.DeepEqual(keys, tt.wkeys) {
t.Errorf("#%d: keys = %+v, want %+v", i, keys, tt.wkeys)
}
if !reflect.DeepEqual(revs, tt.wrevs) {
t.Errorf("#%d: revs = %+v, want %+v", i, revs, tt.wrevs)
}
}
}
func TestIndexTombstone(t *testing.T) {
ti := newTreeIndex()
ti.Put([]byte("foo"), revision{main: 1})
err := ti.Tombstone([]byte("foo"), revision{main: 2})
if err != nil {
t.Errorf("tombstone error = %v, want nil", err)
}
_, _, _, err = ti.Get([]byte("foo"), 2)
if err != ErrRevisionNotFound {
t.Errorf("get error = %v, want nil", err)
}
err = ti.Tombstone([]byte("foo"), revision{main: 3})
if err != ErrRevisionNotFound {
t.Errorf("tombstone error = %v, want %v", err, ErrRevisionNotFound)
}
}
func TestIndexRangeSince(t *testing.T) {
allKeys := [][]byte{[]byte("foo"), []byte("foo1"), []byte("foo2"), []byte("foo2"), []byte("foo1"), []byte("foo")}
allRevs := []revision{{main: 1}, {main: 2}, {main: 3}, {main: 4}, {main: 5}, {main: 6}}
ti := newTreeIndex()
for i := range allKeys {
ti.Put(allKeys[i], allRevs[i])
}
atRev := int64(1)
tests := []struct {
key, end []byte
wrevs []revision
}{
// single key that not found
{
[]byte("bar"), nil, nil,
},
// single key that found
{
[]byte("foo"), nil, []revision{{main: 1}, {main: 6}},
},
// range keys, return first member
{
[]byte("foo"), []byte("foo1"), []revision{{main: 1}, {main: 6}},
},
// range keys, return first two members
{
[]byte("foo"), []byte("foo2"), []revision{{main: 1}, {main: 2}, {main: 5}, {main: 6}},
},
// range keys, return all members
{
[]byte("foo"), []byte("fop"), allRevs,
},
// range keys, return last two members
{
[]byte("foo1"), []byte("fop"), []revision{{main: 2}, {main: 3}, {main: 4}, {main: 5}},
},
// range keys, return last member
{
[]byte("foo2"), []byte("fop"), []revision{{main: 3}, {main: 4}},
},
// range keys, return nothing
{
[]byte("foo3"), []byte("fop"), nil,
},
}
for i, tt := range tests {
revs := ti.RangeSince(tt.key, tt.end, atRev)
if !reflect.DeepEqual(revs, tt.wrevs) {
t.Errorf("#%d: revs = %+v, want %+v", i, revs, tt.wrevs)
}
}
}
func TestIndexCompactAndKeep(t *testing.T) {
maxRev := int64(20)
tests := []struct {
key []byte
remove bool
rev revision
created revision
ver int64
}{
{[]byte("foo"), false, revision{main: 1}, revision{main: 1}, 1},
{[]byte("foo1"), false, revision{main: 2}, revision{main: 2}, 1},
{[]byte("foo2"), false, revision{main: 3}, revision{main: 3}, 1},
{[]byte("foo2"), false, revision{main: 4}, revision{main: 3}, 2},
{[]byte("foo"), false, revision{main: 5}, revision{main: 1}, 2},
{[]byte("foo1"), false, revision{main: 6}, revision{main: 2}, 2},
{[]byte("foo1"), true, revision{main: 7}, revision{}, 0},
{[]byte("foo2"), true, revision{main: 8}, revision{}, 0},
{[]byte("foo"), true, revision{main: 9}, revision{}, 0},
{[]byte("foo"), false, revision{10, 0}, revision{10, 0}, 1},
{[]byte("foo1"), false, revision{10, 1}, revision{10, 1}, 1},
}
// Continuous Compact and Keep
ti := newTreeIndex()
for _, tt := range tests {
if tt.remove {
ti.Tombstone(tt.key, tt.rev)
} else {
ti.Put(tt.key, tt.rev)
}
}
for i := int64(1); i < maxRev; i++ {
am := ti.Compact(i)
keep := ti.Keep(i)
if !(reflect.DeepEqual(am, keep)) {
t.Errorf("#%d: compact keep %v != Keep keep %v", i, am, keep)
}
wti := &treeIndex{tree: btree.New(32)}
for _, tt := range tests {
if _, ok := am[tt.rev]; ok || tt.rev.GreaterThan(revision{main: i}) {
if tt.remove {
wti.Tombstone(tt.key, tt.rev)
} else {
restore(wti, tt.key, tt.created, tt.rev, tt.ver)
}
}
}
if !ti.Equal(wti) {
t.Errorf("#%d: not equal ti", i)
}
}
// Once Compact and Keep
for i := int64(1); i < maxRev; i++ {
ti := newTreeIndex()
for _, tt := range tests {
if tt.remove {
ti.Tombstone(tt.key, tt.rev)
} else {
ti.Put(tt.key, tt.rev)
}
}
am := ti.Compact(i)
keep := ti.Keep(i)
if !(reflect.DeepEqual(am, keep)) {
t.Errorf("#%d: compact keep %v != Keep keep %v", i, am, keep)
}
wti := &treeIndex{tree: btree.New(32)}
for _, tt := range tests {
if _, ok := am[tt.rev]; ok || tt.rev.GreaterThan(revision{main: i}) {
if tt.remove {
wti.Tombstone(tt.key, tt.rev)
} else {
restore(wti, tt.key, tt.created, tt.rev, tt.ver)
}
}
}
if !ti.Equal(wti) {
t.Errorf("#%d: not equal ti", i)
}
}
}
func restore(ti *treeIndex, key []byte, created, modified revision, ver int64) {
keyi := &keyIndex{key: key}
ti.Lock()
defer ti.Unlock()
item := ti.tree.Get(keyi)
if item == nil {
keyi.restore(created, modified, ver)
ti.tree.ReplaceOrInsert(keyi)
return
}
okeyi := item.(*keyIndex)
okeyi.put(modified.main, modified.sub)
}
![swh spinner](/static/img/swh-spinner.gif)
Computing file changes ...