Source file src/go.etcd.io/etcd/server/v3/mvcc/key_index_test.go

Documentation: go.etcd.io/etcd/server/v3/mvcc

     1  // Copyright 2015 The etcd Authors
     2  //
     3  // Licensed under the Apache License, Version 2.0 (the "License");
     4  // you may not use this file except in compliance with the License.
     5  // You may obtain a copy of the License at
     6  //
     7  //     http://www.apache.org/licenses/LICENSE-2.0
     8  //
     9  // Unless required by applicable law or agreed to in writing, software
    10  // distributed under the License is distributed on an "AS IS" BASIS,
    11  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    12  // See the License for the specific language governing permissions and
    13  // limitations under the License.
    14  
    15  package mvcc
    16  
    17  import (
    18  	"reflect"
    19  	"testing"
    20  
    21  	"go.uber.org/zap"
    22  )
    23  
    24  func TestKeyIndexGet(t *testing.T) {
    25  	// key: "foo"
    26  	// rev: 16
    27  	// generations:
    28  	//    {empty}
    29  	//    {{14, 0}[1], {14, 1}[2], {16, 0}(t)[3]}
    30  	//    {{8, 0}[1], {10, 0}[2], {12, 0}(t)[3]}
    31  	//    {{2, 0}[1], {4, 0}[2], {6, 0}(t)[3]}
    32  	ki := newTestKeyIndex()
    33  	ki.compact(zap.NewExample(), 4, make(map[revision]struct{}))
    34  
    35  	tests := []struct {
    36  		rev int64
    37  
    38  		wmod   revision
    39  		wcreat revision
    40  		wver   int64
    41  		werr   error
    42  	}{
    43  		{17, revision{}, revision{}, 0, ErrRevisionNotFound},
    44  		{16, revision{}, revision{}, 0, ErrRevisionNotFound},
    45  
    46  		// get on generation 3
    47  		{15, revision{14, 1}, revision{14, 0}, 2, nil},
    48  		{14, revision{14, 1}, revision{14, 0}, 2, nil},
    49  
    50  		{13, revision{}, revision{}, 0, ErrRevisionNotFound},
    51  		{12, revision{}, revision{}, 0, ErrRevisionNotFound},
    52  
    53  		// get on generation 2
    54  		{11, revision{10, 0}, revision{8, 0}, 2, nil},
    55  		{10, revision{10, 0}, revision{8, 0}, 2, nil},
    56  		{9, revision{8, 0}, revision{8, 0}, 1, nil},
    57  		{8, revision{8, 0}, revision{8, 0}, 1, nil},
    58  
    59  		{7, revision{}, revision{}, 0, ErrRevisionNotFound},
    60  		{6, revision{}, revision{}, 0, ErrRevisionNotFound},
    61  
    62  		// get on generation 1
    63  		{5, revision{4, 0}, revision{2, 0}, 2, nil},
    64  		{4, revision{4, 0}, revision{2, 0}, 2, nil},
    65  
    66  		{3, revision{}, revision{}, 0, ErrRevisionNotFound},
    67  		{2, revision{}, revision{}, 0, ErrRevisionNotFound},
    68  		{1, revision{}, revision{}, 0, ErrRevisionNotFound},
    69  		{0, revision{}, revision{}, 0, ErrRevisionNotFound},
    70  	}
    71  
    72  	for i, tt := range tests {
    73  		mod, creat, ver, err := ki.get(zap.NewExample(), tt.rev)
    74  		if err != tt.werr {
    75  			t.Errorf("#%d: err = %v, want %v", i, err, tt.werr)
    76  		}
    77  		if mod != tt.wmod {
    78  			t.Errorf("#%d: modified = %+v, want %+v", i, mod, tt.wmod)
    79  		}
    80  		if creat != tt.wcreat {
    81  			t.Errorf("#%d: created = %+v, want %+v", i, creat, tt.wcreat)
    82  		}
    83  		if ver != tt.wver {
    84  			t.Errorf("#%d: version = %d, want %d", i, ver, tt.wver)
    85  		}
    86  	}
    87  }
    88  
    89  func TestKeyIndexSince(t *testing.T) {
    90  	ki := newTestKeyIndex()
    91  	ki.compact(zap.NewExample(), 4, make(map[revision]struct{}))
    92  
    93  	allRevs := []revision{{4, 0}, {6, 0}, {8, 0}, {10, 0}, {12, 0}, {14, 1}, {16, 0}}
    94  	tests := []struct {
    95  		rev int64
    96  
    97  		wrevs []revision
    98  	}{
    99  		{17, nil},
   100  		{16, allRevs[6:]},
   101  		{15, allRevs[6:]},
   102  		{14, allRevs[5:]},
   103  		{13, allRevs[5:]},
   104  		{12, allRevs[4:]},
   105  		{11, allRevs[4:]},
   106  		{10, allRevs[3:]},
   107  		{9, allRevs[3:]},
   108  		{8, allRevs[2:]},
   109  		{7, allRevs[2:]},
   110  		{6, allRevs[1:]},
   111  		{5, allRevs[1:]},
   112  		{4, allRevs},
   113  		{3, allRevs},
   114  		{2, allRevs},
   115  		{1, allRevs},
   116  		{0, allRevs},
   117  	}
   118  
   119  	for i, tt := range tests {
   120  		revs := ki.since(zap.NewExample(), tt.rev)
   121  		if !reflect.DeepEqual(revs, tt.wrevs) {
   122  			t.Errorf("#%d: revs = %+v, want %+v", i, revs, tt.wrevs)
   123  		}
   124  	}
   125  }
   126  
   127  func TestKeyIndexPut(t *testing.T) {
   128  	ki := &keyIndex{key: []byte("foo")}
   129  	ki.put(zap.NewExample(), 5, 0)
   130  
   131  	wki := &keyIndex{
   132  		key:         []byte("foo"),
   133  		modified:    revision{5, 0},
   134  		generations: []generation{{created: revision{5, 0}, ver: 1, revs: []revision{{main: 5}}}},
   135  	}
   136  	if !reflect.DeepEqual(ki, wki) {
   137  		t.Errorf("ki = %+v, want %+v", ki, wki)
   138  	}
   139  
   140  	ki.put(zap.NewExample(), 7, 0)
   141  
   142  	wki = &keyIndex{
   143  		key:         []byte("foo"),
   144  		modified:    revision{7, 0},
   145  		generations: []generation{{created: revision{5, 0}, ver: 2, revs: []revision{{main: 5}, {main: 7}}}},
   146  	}
   147  	if !reflect.DeepEqual(ki, wki) {
   148  		t.Errorf("ki = %+v, want %+v", ki, wki)
   149  	}
   150  }
   151  
   152  func TestKeyIndexRestore(t *testing.T) {
   153  	ki := &keyIndex{key: []byte("foo")}
   154  	ki.restore(zap.NewExample(), revision{5, 0}, revision{7, 0}, 2)
   155  
   156  	wki := &keyIndex{
   157  		key:         []byte("foo"),
   158  		modified:    revision{7, 0},
   159  		generations: []generation{{created: revision{5, 0}, ver: 2, revs: []revision{{main: 7}}}},
   160  	}
   161  	if !reflect.DeepEqual(ki, wki) {
   162  		t.Errorf("ki = %+v, want %+v", ki, wki)
   163  	}
   164  }
   165  
   166  func TestKeyIndexTombstone(t *testing.T) {
   167  	ki := &keyIndex{key: []byte("foo")}
   168  	ki.put(zap.NewExample(), 5, 0)
   169  
   170  	err := ki.tombstone(zap.NewExample(), 7, 0)
   171  	if err != nil {
   172  		t.Errorf("unexpected tombstone error: %v", err)
   173  	}
   174  
   175  	wki := &keyIndex{
   176  		key:         []byte("foo"),
   177  		modified:    revision{7, 0},
   178  		generations: []generation{{created: revision{5, 0}, ver: 2, revs: []revision{{main: 5}, {main: 7}}}, {}},
   179  	}
   180  	if !reflect.DeepEqual(ki, wki) {
   181  		t.Errorf("ki = %+v, want %+v", ki, wki)
   182  	}
   183  
   184  	ki.put(zap.NewExample(), 8, 0)
   185  	ki.put(zap.NewExample(), 9, 0)
   186  	err = ki.tombstone(zap.NewExample(), 15, 0)
   187  	if err != nil {
   188  		t.Errorf("unexpected tombstone error: %v", err)
   189  	}
   190  
   191  	wki = &keyIndex{
   192  		key:      []byte("foo"),
   193  		modified: revision{15, 0},
   194  		generations: []generation{
   195  			{created: revision{5, 0}, ver: 2, revs: []revision{{main: 5}, {main: 7}}},
   196  			{created: revision{8, 0}, ver: 3, revs: []revision{{main: 8}, {main: 9}, {main: 15}}},
   197  			{},
   198  		},
   199  	}
   200  	if !reflect.DeepEqual(ki, wki) {
   201  		t.Errorf("ki = %+v, want %+v", ki, wki)
   202  	}
   203  
   204  	err = ki.tombstone(zap.NewExample(), 16, 0)
   205  	if err != ErrRevisionNotFound {
   206  		t.Errorf("tombstone error = %v, want %v", err, ErrRevisionNotFound)
   207  	}
   208  }
   209  
   210  func TestKeyIndexCompactAndKeep(t *testing.T) {
   211  	tests := []struct {
   212  		compact int64
   213  
   214  		wki *keyIndex
   215  		wam map[revision]struct{}
   216  	}{
   217  		{
   218  			1,
   219  			&keyIndex{
   220  				key:      []byte("foo"),
   221  				modified: revision{16, 0},
   222  				generations: []generation{
   223  					{created: revision{2, 0}, ver: 3, revs: []revision{{main: 2}, {main: 4}, {main: 6}}},
   224  					{created: revision{8, 0}, ver: 3, revs: []revision{{main: 8}, {main: 10}, {main: 12}}},
   225  					{created: revision{14, 0}, ver: 3, revs: []revision{{main: 14}, {main: 14, sub: 1}, {main: 16}}},
   226  					{},
   227  				},
   228  			},
   229  			map[revision]struct{}{},
   230  		},
   231  		{
   232  			2,
   233  			&keyIndex{
   234  				key:      []byte("foo"),
   235  				modified: revision{16, 0},
   236  				generations: []generation{
   237  					{created: revision{2, 0}, ver: 3, revs: []revision{{main: 2}, {main: 4}, {main: 6}}},
   238  					{created: revision{8, 0}, ver: 3, revs: []revision{{main: 8}, {main: 10}, {main: 12}}},
   239  					{created: revision{14, 0}, ver: 3, revs: []revision{{main: 14}, {main: 14, sub: 1}, {main: 16}}},
   240  					{},
   241  				},
   242  			},
   243  			map[revision]struct{}{
   244  				{main: 2}: {},
   245  			},
   246  		},
   247  		{
   248  			3,
   249  			&keyIndex{
   250  				key:      []byte("foo"),
   251  				modified: revision{16, 0},
   252  				generations: []generation{
   253  					{created: revision{2, 0}, ver: 3, revs: []revision{{main: 2}, {main: 4}, {main: 6}}},
   254  					{created: revision{8, 0}, ver: 3, revs: []revision{{main: 8}, {main: 10}, {main: 12}}},
   255  					{created: revision{14, 0}, ver: 3, revs: []revision{{main: 14}, {main: 14, sub: 1}, {main: 16}}},
   256  					{},
   257  				},
   258  			},
   259  			map[revision]struct{}{
   260  				{main: 2}: {},
   261  			},
   262  		},
   263  		{
   264  			4,
   265  			&keyIndex{
   266  				key:      []byte("foo"),
   267  				modified: revision{16, 0},
   268  				generations: []generation{
   269  					{created: revision{2, 0}, ver: 3, revs: []revision{{main: 4}, {main: 6}}},
   270  					{created: revision{8, 0}, ver: 3, revs: []revision{{main: 8}, {main: 10}, {main: 12}}},
   271  					{created: revision{14, 0}, ver: 3, revs: []revision{{main: 14}, {main: 14, sub: 1}, {main: 16}}},
   272  					{},
   273  				},
   274  			},
   275  			map[revision]struct{}{
   276  				{main: 4}: {},
   277  			},
   278  		},
   279  		{
   280  			5,
   281  			&keyIndex{
   282  				key:      []byte("foo"),
   283  				modified: revision{16, 0},
   284  				generations: []generation{
   285  					{created: revision{2, 0}, ver: 3, revs: []revision{{main: 4}, {main: 6}}},
   286  					{created: revision{8, 0}, ver: 3, revs: []revision{{main: 8}, {main: 10}, {main: 12}}},
   287  					{created: revision{14, 0}, ver: 3, revs: []revision{{main: 14}, {main: 14, sub: 1}, {main: 16}}},
   288  					{},
   289  				},
   290  			},
   291  			map[revision]struct{}{
   292  				{main: 4}: {},
   293  			},
   294  		},
   295  		{
   296  			6,
   297  			&keyIndex{
   298  				key:      []byte("foo"),
   299  				modified: revision{16, 0},
   300  				generations: []generation{
   301  					{created: revision{8, 0}, ver: 3, revs: []revision{{main: 8}, {main: 10}, {main: 12}}},
   302  					{created: revision{14, 0}, ver: 3, revs: []revision{{main: 14}, {main: 14, sub: 1}, {main: 16}}},
   303  					{},
   304  				},
   305  			},
   306  			map[revision]struct{}{},
   307  		},
   308  		{
   309  			7,
   310  			&keyIndex{
   311  				key:      []byte("foo"),
   312  				modified: revision{16, 0},
   313  				generations: []generation{
   314  					{created: revision{8, 0}, ver: 3, revs: []revision{{main: 8}, {main: 10}, {main: 12}}},
   315  					{created: revision{14, 0}, ver: 3, revs: []revision{{main: 14}, {main: 14, sub: 1}, {main: 16}}},
   316  					{},
   317  				},
   318  			},
   319  			map[revision]struct{}{},
   320  		},
   321  		{
   322  			8,
   323  			&keyIndex{
   324  				key:      []byte("foo"),
   325  				modified: revision{16, 0},
   326  				generations: []generation{
   327  					{created: revision{8, 0}, ver: 3, revs: []revision{{main: 8}, {main: 10}, {main: 12}}},
   328  					{created: revision{14, 0}, ver: 3, revs: []revision{{main: 14}, {main: 14, sub: 1}, {main: 16}}},
   329  					{},
   330  				},
   331  			},
   332  			map[revision]struct{}{
   333  				{main: 8}: {},
   334  			},
   335  		},
   336  		{
   337  			9,
   338  			&keyIndex{
   339  				key:      []byte("foo"),
   340  				modified: revision{16, 0},
   341  				generations: []generation{
   342  					{created: revision{8, 0}, ver: 3, revs: []revision{{main: 8}, {main: 10}, {main: 12}}},
   343  					{created: revision{14, 0}, ver: 3, revs: []revision{{main: 14}, {main: 14, sub: 1}, {main: 16}}},
   344  					{},
   345  				},
   346  			},
   347  			map[revision]struct{}{
   348  				{main: 8}: {},
   349  			},
   350  		},
   351  		{
   352  			10,
   353  			&keyIndex{
   354  				key:      []byte("foo"),
   355  				modified: revision{16, 0},
   356  				generations: []generation{
   357  					{created: revision{8, 0}, ver: 3, revs: []revision{{main: 10}, {main: 12}}},
   358  					{created: revision{14, 0}, ver: 3, revs: []revision{{main: 14}, {main: 14, sub: 1}, {main: 16}}},
   359  					{},
   360  				},
   361  			},
   362  			map[revision]struct{}{
   363  				{main: 10}: {},
   364  			},
   365  		},
   366  		{
   367  			11,
   368  			&keyIndex{
   369  				key:      []byte("foo"),
   370  				modified: revision{16, 0},
   371  				generations: []generation{
   372  					{created: revision{8, 0}, ver: 3, revs: []revision{{main: 10}, {main: 12}}},
   373  					{created: revision{14, 0}, ver: 3, revs: []revision{{main: 14}, {main: 14, sub: 1}, {main: 16}}},
   374  					{},
   375  				},
   376  			},
   377  			map[revision]struct{}{
   378  				{main: 10}: {},
   379  			},
   380  		},
   381  		{
   382  			12,
   383  			&keyIndex{
   384  				key:      []byte("foo"),
   385  				modified: revision{16, 0},
   386  				generations: []generation{
   387  					{created: revision{14, 0}, ver: 3, revs: []revision{{main: 14}, {main: 14, sub: 1}, {main: 16}}},
   388  					{},
   389  				},
   390  			},
   391  			map[revision]struct{}{},
   392  		},
   393  		{
   394  			13,
   395  			&keyIndex{
   396  				key:      []byte("foo"),
   397  				modified: revision{16, 0},
   398  				generations: []generation{
   399  					{created: revision{14, 0}, ver: 3, revs: []revision{{main: 14}, {main: 14, sub: 1}, {main: 16}}},
   400  					{},
   401  				},
   402  			},
   403  			map[revision]struct{}{},
   404  		},
   405  		{
   406  			14,
   407  			&keyIndex{
   408  				key:      []byte("foo"),
   409  				modified: revision{16, 0},
   410  				generations: []generation{
   411  					{created: revision{14, 0}, ver: 3, revs: []revision{{main: 14, sub: 1}, {main: 16}}},
   412  					{},
   413  				},
   414  			},
   415  			map[revision]struct{}{
   416  				{main: 14, sub: 1}: {},
   417  			},
   418  		},
   419  		{
   420  			15,
   421  			&keyIndex{
   422  				key:      []byte("foo"),
   423  				modified: revision{16, 0},
   424  				generations: []generation{
   425  					{created: revision{14, 0}, ver: 3, revs: []revision{{main: 14, sub: 1}, {main: 16}}},
   426  					{},
   427  				},
   428  			},
   429  			map[revision]struct{}{
   430  				{main: 14, sub: 1}: {},
   431  			},
   432  		},
   433  		{
   434  			16,
   435  			&keyIndex{
   436  				key:      []byte("foo"),
   437  				modified: revision{16, 0},
   438  				generations: []generation{
   439  					{},
   440  				},
   441  			},
   442  			map[revision]struct{}{},
   443  		},
   444  	}
   445  
   446  	// Continuous Compaction and finding Keep
   447  	ki := newTestKeyIndex()
   448  	for i, tt := range tests {
   449  		am := make(map[revision]struct{})
   450  		kiclone := cloneKeyIndex(ki)
   451  		ki.keep(tt.compact, am)
   452  		if !reflect.DeepEqual(ki, kiclone) {
   453  			t.Errorf("#%d: ki = %+v, want %+v", i, ki, kiclone)
   454  		}
   455  		if !reflect.DeepEqual(am, tt.wam) {
   456  			t.Errorf("#%d: am = %+v, want %+v", i, am, tt.wam)
   457  		}
   458  		am = make(map[revision]struct{})
   459  		ki.compact(zap.NewExample(), tt.compact, am)
   460  		if !reflect.DeepEqual(ki, tt.wki) {
   461  			t.Errorf("#%d: ki = %+v, want %+v", i, ki, tt.wki)
   462  		}
   463  		if !reflect.DeepEqual(am, tt.wam) {
   464  			t.Errorf("#%d: am = %+v, want %+v", i, am, tt.wam)
   465  		}
   466  	}
   467  
   468  	// Jump Compaction and finding Keep
   469  	ki = newTestKeyIndex()
   470  	for i, tt := range tests {
   471  		if (i%2 == 0 && i < 6) || (i%2 == 1 && i > 6) {
   472  			am := make(map[revision]struct{})
   473  			kiclone := cloneKeyIndex(ki)
   474  			ki.keep(tt.compact, am)
   475  			if !reflect.DeepEqual(ki, kiclone) {
   476  				t.Errorf("#%d: ki = %+v, want %+v", i, ki, kiclone)
   477  			}
   478  			if !reflect.DeepEqual(am, tt.wam) {
   479  				t.Errorf("#%d: am = %+v, want %+v", i, am, tt.wam)
   480  			}
   481  			am = make(map[revision]struct{})
   482  			ki.compact(zap.NewExample(), tt.compact, am)
   483  			if !reflect.DeepEqual(ki, tt.wki) {
   484  				t.Errorf("#%d: ki = %+v, want %+v", i, ki, tt.wki)
   485  			}
   486  			if !reflect.DeepEqual(am, tt.wam) {
   487  				t.Errorf("#%d: am = %+v, want %+v", i, am, tt.wam)
   488  			}
   489  		}
   490  	}
   491  
   492  	kiClone := newTestKeyIndex()
   493  	// Once Compaction and finding Keep
   494  	for i, tt := range tests {
   495  		ki := newTestKeyIndex()
   496  		am := make(map[revision]struct{})
   497  		ki.keep(tt.compact, am)
   498  		if !reflect.DeepEqual(ki, kiClone) {
   499  			t.Errorf("#%d: ki = %+v, want %+v", i, ki, kiClone)
   500  		}
   501  		if !reflect.DeepEqual(am, tt.wam) {
   502  			t.Errorf("#%d: am = %+v, want %+v", i, am, tt.wam)
   503  		}
   504  		am = make(map[revision]struct{})
   505  		ki.compact(zap.NewExample(), tt.compact, am)
   506  		if !reflect.DeepEqual(ki, tt.wki) {
   507  			t.Errorf("#%d: ki = %+v, want %+v", i, ki, tt.wki)
   508  		}
   509  		if !reflect.DeepEqual(am, tt.wam) {
   510  			t.Errorf("#%d: am = %+v, want %+v", i, am, tt.wam)
   511  		}
   512  	}
   513  }
   514  
   515  func cloneKeyIndex(ki *keyIndex) *keyIndex {
   516  	generations := make([]generation, len(ki.generations))
   517  	for i, gen := range ki.generations {
   518  		generations[i] = *cloneGeneration(&gen)
   519  	}
   520  	return &keyIndex{ki.key, ki.modified, generations}
   521  }
   522  
   523  func cloneGeneration(g *generation) *generation {
   524  	if g.revs == nil {
   525  		return &generation{g.ver, g.created, nil}
   526  	}
   527  	tmp := make([]revision, len(g.revs))
   528  	copy(tmp, g.revs)
   529  	return &generation{g.ver, g.created, tmp}
   530  }
   531  
   532  // TestKeyIndexCompactOnFurtherRev to test that compact on version that higher than last modified version works well
   533  func TestKeyIndexCompactOnFurtherRev(t *testing.T) {
   534  	ki := &keyIndex{key: []byte("foo")}
   535  	ki.put(zap.NewExample(), 1, 0)
   536  	ki.put(zap.NewExample(), 2, 0)
   537  	am := make(map[revision]struct{})
   538  	ki.compact(zap.NewExample(), 3, am)
   539  
   540  	wki := &keyIndex{
   541  		key:      []byte("foo"),
   542  		modified: revision{2, 0},
   543  		generations: []generation{
   544  			{created: revision{1, 0}, ver: 2, revs: []revision{{main: 2}}},
   545  		},
   546  	}
   547  	wam := map[revision]struct{}{
   548  		{main: 2}: {},
   549  	}
   550  	if !reflect.DeepEqual(ki, wki) {
   551  		t.Errorf("ki = %+v, want %+v", ki, wki)
   552  	}
   553  	if !reflect.DeepEqual(am, wam) {
   554  		t.Errorf("am = %+v, want %+v", am, wam)
   555  	}
   556  }
   557  
   558  func TestKeyIndexIsEmpty(t *testing.T) {
   559  	tests := []struct {
   560  		ki *keyIndex
   561  		w  bool
   562  	}{
   563  		{
   564  			&keyIndex{
   565  				key:         []byte("foo"),
   566  				generations: []generation{{}},
   567  			},
   568  			true,
   569  		},
   570  		{
   571  			&keyIndex{
   572  				key:      []byte("foo"),
   573  				modified: revision{2, 0},
   574  				generations: []generation{
   575  					{created: revision{1, 0}, ver: 2, revs: []revision{{main: 2}}},
   576  				},
   577  			},
   578  			false,
   579  		},
   580  	}
   581  	for i, tt := range tests {
   582  		g := tt.ki.isEmpty()
   583  		if g != tt.w {
   584  			t.Errorf("#%d: isEmpty = %v, want %v", i, g, tt.w)
   585  		}
   586  	}
   587  }
   588  
   589  func TestKeyIndexFindGeneration(t *testing.T) {
   590  	ki := newTestKeyIndex()
   591  
   592  	tests := []struct {
   593  		rev int64
   594  		wg  *generation
   595  	}{
   596  		{0, nil},
   597  		{1, nil},
   598  		{2, &ki.generations[0]},
   599  		{3, &ki.generations[0]},
   600  		{4, &ki.generations[0]},
   601  		{5, &ki.generations[0]},
   602  		{6, nil},
   603  		{7, nil},
   604  		{8, &ki.generations[1]},
   605  		{9, &ki.generations[1]},
   606  		{10, &ki.generations[1]},
   607  		{11, &ki.generations[1]},
   608  		{12, nil},
   609  		{13, nil},
   610  	}
   611  	for i, tt := range tests {
   612  		g := ki.findGeneration(tt.rev)
   613  		if g != tt.wg {
   614  			t.Errorf("#%d: generation = %+v, want %+v", i, g, tt.wg)
   615  		}
   616  	}
   617  }
   618  
   619  func TestKeyIndexLess(t *testing.T) {
   620  	ki := &keyIndex{key: []byte("foo")}
   621  
   622  	tests := []struct {
   623  		ki *keyIndex
   624  		w  bool
   625  	}{
   626  		{&keyIndex{key: []byte("doo")}, false},
   627  		{&keyIndex{key: []byte("foo")}, false},
   628  		{&keyIndex{key: []byte("goo")}, true},
   629  	}
   630  	for i, tt := range tests {
   631  		g := ki.Less(tt.ki)
   632  		if g != tt.w {
   633  			t.Errorf("#%d: Less = %v, want %v", i, g, tt.w)
   634  		}
   635  	}
   636  }
   637  
   638  func TestGenerationIsEmpty(t *testing.T) {
   639  	tests := []struct {
   640  		g *generation
   641  		w bool
   642  	}{
   643  		{nil, true},
   644  		{&generation{}, true},
   645  		{&generation{revs: []revision{{main: 1}}}, false},
   646  	}
   647  	for i, tt := range tests {
   648  		g := tt.g.isEmpty()
   649  		if g != tt.w {
   650  			t.Errorf("#%d: isEmpty = %v, want %v", i, g, tt.w)
   651  		}
   652  	}
   653  }
   654  
   655  func TestGenerationWalk(t *testing.T) {
   656  	g := &generation{
   657  		ver:     3,
   658  		created: revision{2, 0},
   659  		revs:    []revision{{main: 2}, {main: 4}, {main: 6}},
   660  	}
   661  	tests := []struct {
   662  		f  func(rev revision) bool
   663  		wi int
   664  	}{
   665  		{func(rev revision) bool { return rev.main >= 7 }, 2},
   666  		{func(rev revision) bool { return rev.main >= 6 }, 1},
   667  		{func(rev revision) bool { return rev.main >= 5 }, 1},
   668  		{func(rev revision) bool { return rev.main >= 4 }, 0},
   669  		{func(rev revision) bool { return rev.main >= 3 }, 0},
   670  		{func(rev revision) bool { return rev.main >= 2 }, -1},
   671  	}
   672  	for i, tt := range tests {
   673  		idx := g.walk(tt.f)
   674  		if idx != tt.wi {
   675  			t.Errorf("#%d: index = %d, want %d", i, idx, tt.wi)
   676  		}
   677  	}
   678  }
   679  
   680  func newTestKeyIndex() *keyIndex {
   681  	// key: "foo"
   682  	// rev: 16
   683  	// generations:
   684  	//    {empty}
   685  	//    {{14, 0}[1], {14, 1}[2], {16, 0}(t)[3]}
   686  	//    {{8, 0}[1], {10, 0}[2], {12, 0}(t)[3]}
   687  	//    {{2, 0}[1], {4, 0}[2], {6, 0}(t)[3]}
   688  
   689  	ki := &keyIndex{key: []byte("foo")}
   690  	ki.put(zap.NewExample(), 2, 0)
   691  	ki.put(zap.NewExample(), 4, 0)
   692  	ki.tombstone(zap.NewExample(), 6, 0)
   693  	ki.put(zap.NewExample(), 8, 0)
   694  	ki.put(zap.NewExample(), 10, 0)
   695  	ki.tombstone(zap.NewExample(), 12, 0)
   696  	ki.put(zap.NewExample(), 14, 0)
   697  	ki.put(zap.NewExample(), 14, 1)
   698  	ki.tombstone(zap.NewExample(), 16, 0)
   699  	return ki
   700  }
   701  

View as plain text