summaryrefslogtreecommitdiffhomepage
path: root/pkg/ilist
diff options
context:
space:
mode:
Diffstat (limited to 'pkg/ilist')
-rw-r--r--pkg/ilist/BUILD56
-rw-r--r--pkg/ilist/ilist_state_autogen.go64
-rw-r--r--pkg/ilist/interface_list.go (renamed from pkg/ilist/list.go)15
-rw-r--r--pkg/ilist/list_test.go240
4 files changed, 64 insertions, 311 deletions
diff --git a/pkg/ilist/BUILD b/pkg/ilist/BUILD
deleted file mode 100644
index 3f6eb07df..000000000
--- a/pkg/ilist/BUILD
+++ /dev/null
@@ -1,56 +0,0 @@
-load("//tools:defs.bzl", "go_library", "go_test")
-load("//tools/go_generics:defs.bzl", "go_template", "go_template_instance")
-
-package(licenses = ["notice"])
-
-go_library(
- name = "ilist",
- srcs = [
- "interface_list.go",
- ],
- 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",
- ],
- library = ":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 100644
index 000000000..378b7a895
--- /dev/null
+++ b/pkg/ilist/ilist_state_autogen.go
@@ -0,0 +1,64 @@
+// automatically generated by stateify.
+
+package ilist
+
+import (
+ "gvisor.dev/gvisor/pkg/state"
+)
+
+func (l *List) StateTypeName() string {
+ return "pkg/ilist.List"
+}
+
+func (l *List) StateFields() []string {
+ return []string{
+ "head",
+ "tail",
+ }
+}
+
+func (l *List) beforeSave() {}
+
+func (l *List) StateSave(stateSinkObject state.Sink) {
+ l.beforeSave()
+ stateSinkObject.Save(0, &l.head)
+ stateSinkObject.Save(1, &l.tail)
+}
+
+func (l *List) afterLoad() {}
+
+func (l *List) StateLoad(stateSourceObject state.Source) {
+ stateSourceObject.Load(0, &l.head)
+ stateSourceObject.Load(1, &l.tail)
+}
+
+func (e *Entry) StateTypeName() string {
+ return "pkg/ilist.Entry"
+}
+
+func (e *Entry) StateFields() []string {
+ return []string{
+ "next",
+ "prev",
+ }
+}
+
+func (e *Entry) beforeSave() {}
+
+func (e *Entry) StateSave(stateSinkObject state.Sink) {
+ e.beforeSave()
+ stateSinkObject.Save(0, &e.next)
+ stateSinkObject.Save(1, &e.prev)
+}
+
+func (e *Entry) afterLoad() {}
+
+func (e *Entry) StateLoad(stateSourceObject state.Source) {
+ stateSourceObject.Load(0, &e.next)
+ stateSourceObject.Load(1, &e.prev)
+}
+
+func init() {
+ state.Register((*List)(nil))
+ state.Register((*Entry)(nil))
+}
diff --git a/pkg/ilist/list.go b/pkg/ilist/interface_list.go
index f4a4c33d3..80c655830 100644
--- 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
- }
- }
-}
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-06 09:32:25 +0000