diff options
Diffstat (limited to 'pkg/ilist')
| -rw-r--r-- | pkg/ilist/BUILD | 57 | ||||
| -rwxr-xr-x | pkg/ilist/ilist_state_autogen.go | 38 | ||||
| -rwxr-xr-x[-rw-r--r--] | pkg/ilist/interface_list.go (renamed from pkg/ilist/list.go) | 15 | ||||
| -rw-r--r-- | pkg/ilist/list_test.go | 240 |
4 files changed, 38 insertions, 312 deletions
diff --git a/pkg/ilist/BUILD b/pkg/ilist/BUILD deleted file mode 100644 index 8f3defa25..000000000 --- a/pkg/ilist/BUILD +++ /dev/null @@ -1,57 +0,0 @@ -load("//tools/go_generics:defs.bzl", "go_template", "go_template_instance") -load("//tools/go_stateify:defs.bzl", "go_library", "go_test") - -package(licenses = ["notice"]) - -go_library( - name = "ilist", - srcs = [ - "interface_list.go", - ], - importpath = "gvisor.dev/gvisor/pkg/ilist", - visibility = ["//visibility:public"], -) - -go_template_instance( - name = "interface_list", - out = "interface_list.go", - package = "ilist", - template = ":generic_list", - types = {}, -) - -# This list is used for benchmarking. -go_template_instance( - name = "test_list", - out = "test_list.go", - package = "ilist", - prefix = "direct", - template = ":generic_list", - types = { - "Element": "*direct", - "Linker": "*direct", - }, -) - -go_test( - name = "list_test", - size = "small", - srcs = [ - "list_test.go", - "test_list.go", - ], - embed = [":ilist"], -) - -go_template( - name = "generic_list", - srcs = [ - "list.go", - ], - opt_types = [ - "Element", - "ElementMapper", - "Linker", - ], - visibility = ["//visibility:public"], -) diff --git a/pkg/ilist/ilist_state_autogen.go b/pkg/ilist/ilist_state_autogen.go new file mode 100755 index 000000000..03d7a9564 --- /dev/null +++ b/pkg/ilist/ilist_state_autogen.go @@ -0,0 +1,38 @@ +// automatically generated by stateify. + +package ilist + +import ( + "gvisor.dev/gvisor/pkg/state" +) + +func (x *List) beforeSave() {} +func (x *List) save(m state.Map) { + x.beforeSave() + m.Save("head", &x.head) + m.Save("tail", &x.tail) +} + +func (x *List) afterLoad() {} +func (x *List) load(m state.Map) { + m.Load("head", &x.head) + m.Load("tail", &x.tail) +} + +func (x *Entry) beforeSave() {} +func (x *Entry) save(m state.Map) { + x.beforeSave() + m.Save("next", &x.next) + m.Save("prev", &x.prev) +} + +func (x *Entry) afterLoad() {} +func (x *Entry) load(m state.Map) { + m.Load("next", &x.next) + m.Load("prev", &x.prev) +} + +func init() { + state.Register("ilist.List", (*List)(nil), state.Fns{Save: (*List).save, Load: (*List).load}) + state.Register("ilist.Entry", (*Entry)(nil), state.Fns{Save: (*Entry).save, Load: (*Entry).load}) +} diff --git a/pkg/ilist/list.go b/pkg/ilist/interface_list.go index 019caadca..940c2d3f6 100644..100755 --- a/pkg/ilist/list.go +++ b/pkg/ilist/interface_list.go @@ -1,18 +1,3 @@ -// Copyright 2018 The gVisor 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 ilist provides the implementation of intrusive linked lists. package ilist // Linker is the interface that objects must implement if they want to be added diff --git a/pkg/ilist/list_test.go b/pkg/ilist/list_test.go deleted file mode 100644 index 3f9abfb56..000000000 --- a/pkg/ilist/list_test.go +++ /dev/null @@ -1,240 +0,0 @@ -// Copyright 2018 The gVisor 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 ilist - -import ( - "testing" -) - -type testEntry struct { - Entry - value int -} - -type direct struct { - directEntry - value int -} - -func verifyEquality(t *testing.T, entries []testEntry, l *List) { - t.Helper() - - i := 0 - for it := l.Front(); it != nil; it = it.Next() { - e := it.(*testEntry) - if e != &entries[i] { - t.Errorf("Wrong entry at index %d", i) - return - } - i++ - } - - if i != len(entries) { - t.Errorf("Wrong number of entries; want = %d, got = %d", len(entries), i) - return - } - - i = 0 - for it := l.Back(); it != nil; it = it.Prev() { - e := it.(*testEntry) - if e != &entries[len(entries)-1-i] { - t.Errorf("Wrong entry at index %d", i) - return - } - i++ - } - - if i != len(entries) { - t.Errorf("Wrong number of entries; want = %d, got = %d", len(entries), i) - return - } -} - -func TestZeroEmpty(t *testing.T) { - var l List - if l.Front() != nil { - t.Error("Front is non-nil") - } - if l.Back() != nil { - t.Error("Back is non-nil") - } -} - -func TestPushBack(t *testing.T) { - var l List - - // Test single entry insertion. - var entry testEntry - l.PushBack(&entry) - - e := l.Front().(*testEntry) - if e != &entry { - t.Error("Wrong entry returned") - } - - // Test inserting 100 entries. - l.Reset() - var entries [100]testEntry - for i := range entries { - l.PushBack(&entries[i]) - } - - verifyEquality(t, entries[:], &l) -} - -func TestPushFront(t *testing.T) { - var l List - - // Test single entry insertion. - var entry testEntry - l.PushFront(&entry) - - e := l.Front().(*testEntry) - if e != &entry { - t.Error("Wrong entry returned") - } - - // Test inserting 100 entries. - l.Reset() - var entries [100]testEntry - for i := range entries { - l.PushFront(&entries[len(entries)-1-i]) - } - - verifyEquality(t, entries[:], &l) -} - -func TestRemove(t *testing.T) { - // Remove entry from single-element list. - var l List - var entry testEntry - l.PushBack(&entry) - l.Remove(&entry) - if l.Front() != nil { - t.Error("List is empty") - } - - var entries [100]testEntry - - // Remove single element from lists of lengths 2 to 101. - for n := 1; n <= len(entries); n++ { - for extra := 0; extra <= n; extra++ { - l.Reset() - for i := 0; i < n; i++ { - if extra == i { - l.PushBack(&entry) - } - l.PushBack(&entries[i]) - } - if extra == n { - l.PushBack(&entry) - } - - l.Remove(&entry) - verifyEquality(t, entries[:n], &l) - } - } -} - -func TestReset(t *testing.T) { - var l List - - // Resetting list of one element. - l.PushBack(&testEntry{}) - if l.Front() == nil { - t.Error("List is empty") - } - - l.Reset() - if l.Front() != nil { - t.Error("List is not empty") - } - - // Resetting list of 10 elements. - for i := 0; i < 10; i++ { - l.PushBack(&testEntry{}) - } - - if l.Front() == nil { - t.Error("List is empty") - } - - l.Reset() - if l.Front() != nil { - t.Error("List is not empty") - } - - // Resetting empty list. - l.Reset() - if l.Front() != nil { - t.Error("List is not empty") - } -} - -func BenchmarkIterateForward(b *testing.B) { - var l List - for i := 0; i < 1000000; i++ { - l.PushBack(&testEntry{value: i}) - } - - for i := b.N; i > 0; i-- { - tmp := 0 - for e := l.Front(); e != nil; e = e.Next() { - tmp += e.(*testEntry).value - } - } -} - -func BenchmarkIterateBackward(b *testing.B) { - var l List - for i := 0; i < 1000000; i++ { - l.PushBack(&testEntry{value: i}) - } - - for i := b.N; i > 0; i-- { - tmp := 0 - for e := l.Back(); e != nil; e = e.Prev() { - tmp += e.(*testEntry).value - } - } -} - -func BenchmarkDirectIterateForward(b *testing.B) { - var l directList - for i := 0; i < 1000000; i++ { - l.PushBack(&direct{value: i}) - } - - for i := b.N; i > 0; i-- { - tmp := 0 - for e := l.Front(); e != nil; e = e.Next() { - tmp += e.value - } - } -} - -func BenchmarkDirectIterateBackward(b *testing.B) { - var l directList - for i := 0; i < 1000000; i++ { - l.PushBack(&direct{value: i}) - } - - for i := b.N; i > 0; i-- { - tmp := 0 - for e := l.Back(); e != nil; e = e.Prev() { - tmp += e.value - } - } -} |