summaryrefslogtreecommitdiffhomepage
path: root/pkg/buffer
diff options
context:
space:
mode:
Diffstat (limited to 'pkg/buffer')
-rw-r--r--pkg/buffer/BUILD39
-rwxr-xr-x[-rw-r--r--]pkg/buffer/buffer.go0
-rwxr-xr-xpkg/buffer/buffer_list.go173
-rwxr-xr-xpkg/buffer/buffer_state_autogen.go70
-rwxr-xr-x[-rw-r--r--]pkg/buffer/safemem.go0
-rwxr-xr-x[-rw-r--r--]pkg/buffer/view.go0
-rw-r--r--pkg/buffer/view_test.go233
-rwxr-xr-x[-rw-r--r--]pkg/buffer/view_unsafe.go0
8 files changed, 243 insertions, 272 deletions
diff --git a/pkg/buffer/BUILD b/pkg/buffer/BUILD
deleted file mode 100644
index a77a3beea..000000000
--- a/pkg/buffer/BUILD
+++ /dev/null
@@ -1,39 +0,0 @@
-load("//tools:defs.bzl", "go_library", "go_test")
-load("//tools/go_generics:defs.bzl", "go_template_instance")
-
-package(licenses = ["notice"])
-
-go_template_instance(
- name = "buffer_list",
- out = "buffer_list.go",
- package = "buffer",
- prefix = "buffer",
- template = "//pkg/ilist:generic_list",
- types = {
- "Element": "*Buffer",
- "Linker": "*Buffer",
- },
-)
-
-go_library(
- name = "buffer",
- srcs = [
- "buffer.go",
- "buffer_list.go",
- "safemem.go",
- "view.go",
- "view_unsafe.go",
- ],
- visibility = ["//visibility:public"],
- deps = [
- "//pkg/log",
- "//pkg/safemem",
- ],
-)
-
-go_test(
- name = "buffer_test",
- size = "small",
- srcs = ["view_test.go"],
- library = ":buffer",
-)
diff --git a/pkg/buffer/buffer.go b/pkg/buffer/buffer.go
index d5f64609b..d5f64609b 100644..100755
--- a/pkg/buffer/buffer.go
+++ b/pkg/buffer/buffer.go
diff --git a/pkg/buffer/buffer_list.go b/pkg/buffer/buffer_list.go
new file mode 100755
index 000000000..f3c27c42c
--- /dev/null
+++ b/pkg/buffer/buffer_list.go
@@ -0,0 +1,173 @@
+package buffer
+
+// ElementMapper provides an identity mapping by default.
+//
+// This can be replaced to provide a struct that maps elements to linker
+// objects, if they are not the same. An ElementMapper is not typically
+// required if: Linker is left as is, Element is left as is, or Linker and
+// Element are the same type.
+type bufferElementMapper struct{}
+
+// linkerFor maps an Element to a Linker.
+//
+// This default implementation should be inlined.
+//
+//go:nosplit
+func (bufferElementMapper) linkerFor(elem *Buffer) *Buffer { return elem }
+
+// List is an intrusive list. Entries can be added to or removed from the list
+// in O(1) time and with no additional memory allocations.
+//
+// The zero value for List is an empty list ready to use.
+//
+// To iterate over a list (where l is a List):
+// for e := l.Front(); e != nil; e = e.Next() {
+// // do something with e.
+// }
+//
+// +stateify savable
+type bufferList struct {
+ head *Buffer
+ tail *Buffer
+}
+
+// Reset resets list l to the empty state.
+func (l *bufferList) Reset() {
+ l.head = nil
+ l.tail = nil
+}
+
+// Empty returns true iff the list is empty.
+func (l *bufferList) Empty() bool {
+ return l.head == nil
+}
+
+// Front returns the first element of list l or nil.
+func (l *bufferList) Front() *Buffer {
+ return l.head
+}
+
+// Back returns the last element of list l or nil.
+func (l *bufferList) Back() *Buffer {
+ return l.tail
+}
+
+// PushFront inserts the element e at the front of list l.
+func (l *bufferList) PushFront(e *Buffer) {
+ bufferElementMapper{}.linkerFor(e).SetNext(l.head)
+ bufferElementMapper{}.linkerFor(e).SetPrev(nil)
+
+ if l.head != nil {
+ bufferElementMapper{}.linkerFor(l.head).SetPrev(e)
+ } else {
+ l.tail = e
+ }
+
+ l.head = e
+}
+
+// PushBack inserts the element e at the back of list l.
+func (l *bufferList) PushBack(e *Buffer) {
+ bufferElementMapper{}.linkerFor(e).SetNext(nil)
+ bufferElementMapper{}.linkerFor(e).SetPrev(l.tail)
+
+ if l.tail != nil {
+ bufferElementMapper{}.linkerFor(l.tail).SetNext(e)
+ } else {
+ l.head = e
+ }
+
+ l.tail = e
+}
+
+// PushBackList inserts list m at the end of list l, emptying m.
+func (l *bufferList) PushBackList(m *bufferList) {
+ if l.head == nil {
+ l.head = m.head
+ l.tail = m.tail
+ } else if m.head != nil {
+ bufferElementMapper{}.linkerFor(l.tail).SetNext(m.head)
+ bufferElementMapper{}.linkerFor(m.head).SetPrev(l.tail)
+
+ l.tail = m.tail
+ }
+
+ m.head = nil
+ m.tail = nil
+}
+
+// InsertAfter inserts e after b.
+func (l *bufferList) InsertAfter(b, e *Buffer) {
+ a := bufferElementMapper{}.linkerFor(b).Next()
+ bufferElementMapper{}.linkerFor(e).SetNext(a)
+ bufferElementMapper{}.linkerFor(e).SetPrev(b)
+ bufferElementMapper{}.linkerFor(b).SetNext(e)
+
+ if a != nil {
+ bufferElementMapper{}.linkerFor(a).SetPrev(e)
+ } else {
+ l.tail = e
+ }
+}
+
+// InsertBefore inserts e before a.
+func (l *bufferList) InsertBefore(a, e *Buffer) {
+ b := bufferElementMapper{}.linkerFor(a).Prev()
+ bufferElementMapper{}.linkerFor(e).SetNext(a)
+ bufferElementMapper{}.linkerFor(e).SetPrev(b)
+ bufferElementMapper{}.linkerFor(a).SetPrev(e)
+
+ if b != nil {
+ bufferElementMapper{}.linkerFor(b).SetNext(e)
+ } else {
+ l.head = e
+ }
+}
+
+// Remove removes e from l.
+func (l *bufferList) Remove(e *Buffer) {
+ prev := bufferElementMapper{}.linkerFor(e).Prev()
+ next := bufferElementMapper{}.linkerFor(e).Next()
+
+ if prev != nil {
+ bufferElementMapper{}.linkerFor(prev).SetNext(next)
+ } else {
+ l.head = next
+ }
+
+ if next != nil {
+ bufferElementMapper{}.linkerFor(next).SetPrev(prev)
+ } else {
+ l.tail = prev
+ }
+}
+
+// Entry is a default implementation of Linker. Users can add anonymous fields
+// of this type to their structs to make them automatically implement the
+// methods needed by List.
+//
+// +stateify savable
+type bufferEntry struct {
+ next *Buffer
+ prev *Buffer
+}
+
+// Next returns the entry that follows e in the list.
+func (e *bufferEntry) Next() *Buffer {
+ return e.next
+}
+
+// Prev returns the entry that precedes e in the list.
+func (e *bufferEntry) Prev() *Buffer {
+ return e.prev
+}
+
+// SetNext assigns 'entry' as the entry that follows e in the list.
+func (e *bufferEntry) SetNext(elem *Buffer) {
+ e.next = elem
+}
+
+// SetPrev assigns 'entry' as the entry that precedes e in the list.
+func (e *bufferEntry) SetPrev(elem *Buffer) {
+ e.prev = elem
+}
diff --git a/pkg/buffer/buffer_state_autogen.go b/pkg/buffer/buffer_state_autogen.go
new file mode 100755
index 000000000..9565eb6fa
--- /dev/null
+++ b/pkg/buffer/buffer_state_autogen.go
@@ -0,0 +1,70 @@
+// automatically generated by stateify.
+
+package buffer
+
+import (
+ "gvisor.dev/gvisor/pkg/state"
+)
+
+func (x *Buffer) beforeSave() {}
+func (x *Buffer) save(m state.Map) {
+ x.beforeSave()
+ m.Save("data", &x.data)
+ m.Save("read", &x.read)
+ m.Save("write", &x.write)
+ m.Save("bufferEntry", &x.bufferEntry)
+}
+
+func (x *Buffer) afterLoad() {}
+func (x *Buffer) load(m state.Map) {
+ m.Load("data", &x.data)
+ m.Load("read", &x.read)
+ m.Load("write", &x.write)
+ m.Load("bufferEntry", &x.bufferEntry)
+}
+
+func (x *bufferList) beforeSave() {}
+func (x *bufferList) save(m state.Map) {
+ x.beforeSave()
+ m.Save("head", &x.head)
+ m.Save("tail", &x.tail)
+}
+
+func (x *bufferList) afterLoad() {}
+func (x *bufferList) load(m state.Map) {
+ m.Load("head", &x.head)
+ m.Load("tail", &x.tail)
+}
+
+func (x *bufferEntry) beforeSave() {}
+func (x *bufferEntry) save(m state.Map) {
+ x.beforeSave()
+ m.Save("next", &x.next)
+ m.Save("prev", &x.prev)
+}
+
+func (x *bufferEntry) afterLoad() {}
+func (x *bufferEntry) load(m state.Map) {
+ m.Load("next", &x.next)
+ m.Load("prev", &x.prev)
+}
+
+func (x *View) beforeSave() {}
+func (x *View) save(m state.Map) {
+ x.beforeSave()
+ m.Save("data", &x.data)
+ m.Save("size", &x.size)
+}
+
+func (x *View) afterLoad() {}
+func (x *View) load(m state.Map) {
+ m.Load("data", &x.data)
+ m.Load("size", &x.size)
+}
+
+func init() {
+ state.Register("pkg/buffer.Buffer", (*Buffer)(nil), state.Fns{Save: (*Buffer).save, Load: (*Buffer).load})
+ state.Register("pkg/buffer.bufferList", (*bufferList)(nil), state.Fns{Save: (*bufferList).save, Load: (*bufferList).load})
+ state.Register("pkg/buffer.bufferEntry", (*bufferEntry)(nil), state.Fns{Save: (*bufferEntry).save, Load: (*bufferEntry).load})
+ state.Register("pkg/buffer.View", (*View)(nil), state.Fns{Save: (*View).save, Load: (*View).load})
+}
diff --git a/pkg/buffer/safemem.go b/pkg/buffer/safemem.go
index 071aaa488..071aaa488 100644..100755
--- a/pkg/buffer/safemem.go
+++ b/pkg/buffer/safemem.go
diff --git a/pkg/buffer/view.go b/pkg/buffer/view.go
index 00fc11e9c..00fc11e9c 100644..100755
--- a/pkg/buffer/view.go
+++ b/pkg/buffer/view.go
diff --git a/pkg/buffer/view_test.go b/pkg/buffer/view_test.go
deleted file mode 100644
index 37e652f16..000000000
--- a/pkg/buffer/view_test.go
+++ /dev/null
@@ -1,233 +0,0 @@
-// Copyright 2020 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 buffer
-
-import (
- "bytes"
- "strings"
- "testing"
-)
-
-func TestView(t *testing.T) {
- testCases := []struct {
- name string
- input string
- output string
- ops []func(*View)
- }{
- // Prepend.
- {
- name: "prepend",
- input: "world",
- ops: []func(*View){
- func(v *View) {
- v.Prepend([]byte("hello "))
- },
- },
- output: "hello world",
- },
- {
- name: "prepend fill",
- input: strings.Repeat("1", bufferSize-1),
- ops: []func(*View){
- func(v *View) {
- v.Prepend([]byte("0"))
- },
- },
- output: "0" + strings.Repeat("1", bufferSize-1),
- },
- {
- name: "prepend overflow",
- input: strings.Repeat("1", bufferSize),
- ops: []func(*View){
- func(v *View) {
- v.Prepend([]byte("0"))
- },
- },
- output: "0" + strings.Repeat("1", bufferSize),
- },
- {
- name: "prepend multiple buffers",
- input: strings.Repeat("1", bufferSize-1),
- ops: []func(*View){
- func(v *View) {
- v.Prepend([]byte(strings.Repeat("0", bufferSize*3)))
- },
- },
- output: strings.Repeat("0", bufferSize*3) + strings.Repeat("1", bufferSize-1),
- },
-
- // Append.
- {
- name: "append",
- input: "hello",
- ops: []func(*View){
- func(v *View) {
- v.Append([]byte(" world"))
- },
- },
- output: "hello world",
- },
- {
- name: "append fill",
- input: strings.Repeat("1", bufferSize-1),
- ops: []func(*View){
- func(v *View) {
- v.Append([]byte("0"))
- },
- },
- output: strings.Repeat("1", bufferSize-1) + "0",
- },
- {
- name: "append overflow",
- input: strings.Repeat("1", bufferSize),
- ops: []func(*View){
- func(v *View) {
- v.Append([]byte("0"))
- },
- },
- output: strings.Repeat("1", bufferSize) + "0",
- },
- {
- name: "append multiple buffers",
- input: strings.Repeat("1", bufferSize-1),
- ops: []func(*View){
- func(v *View) {
- v.Append([]byte(strings.Repeat("0", bufferSize*3)))
- },
- },
- output: strings.Repeat("1", bufferSize-1) + strings.Repeat("0", bufferSize*3),
- },
-
- // Truncate.
- {
- name: "truncate",
- input: "hello world",
- ops: []func(*View){
- func(v *View) {
- v.Truncate(5)
- },
- },
- output: "hello",
- },
- {
- name: "truncate multiple buffers",
- input: strings.Repeat("1", bufferSize*2),
- ops: []func(*View){
- func(v *View) {
- v.Truncate(bufferSize*2 - 1)
- },
- },
- output: strings.Repeat("1", bufferSize*2-1),
- },
- {
- name: "truncate multiple buffers to one buffer",
- input: strings.Repeat("1", bufferSize*2),
- ops: []func(*View){
- func(v *View) {
- v.Truncate(5)
- },
- },
- output: "11111",
- },
-
- // TrimFront.
- {
- name: "trim",
- input: "hello world",
- ops: []func(*View){
- func(v *View) {
- v.TrimFront(6)
- },
- },
- output: "world",
- },
- {
- name: "trim multiple buffers",
- input: strings.Repeat("1", bufferSize*2),
- ops: []func(*View){
- func(v *View) {
- v.TrimFront(1)
- },
- },
- output: strings.Repeat("1", bufferSize*2-1),
- },
- {
- name: "trim multiple buffers to one buffer",
- input: strings.Repeat("1", bufferSize*2),
- ops: []func(*View){
- func(v *View) {
- v.TrimFront(bufferSize*2 - 1)
- },
- },
- output: "1",
- },
-
- // Grow.
- {
- name: "grow",
- input: "hello world",
- ops: []func(*View){
- func(v *View) {
- v.Grow(1, true)
- },
- },
- output: "hello world",
- },
- {
- name: "grow from zero",
- ops: []func(*View){
- func(v *View) {
- v.Grow(1024, true)
- },
- },
- output: strings.Repeat("\x00", 1024),
- },
- {
- name: "grow from non-zero",
- input: strings.Repeat("1", bufferSize),
- ops: []func(*View){
- func(v *View) {
- v.Grow(bufferSize*2, true)
- },
- },
- output: strings.Repeat("1", bufferSize) + strings.Repeat("\x00", bufferSize),
- },
- }
-
- for _, tc := range testCases {
- t.Run(tc.name, func(t *testing.T) {
- // Construct the new view.
- var view View
- view.Append([]byte(tc.input))
-
- // Run all operations.
- for _, op := range tc.ops {
- op(&view)
- }
-
- // Flatten and validate.
- out := view.Flatten()
- if !bytes.Equal([]byte(tc.output), out) {
- t.Errorf("expected %q, got %q", tc.output, string(out))
- }
-
- // Ensure the size is correct.
- if len(out) != int(view.Size()) {
- t.Errorf("size is wrong: expected %d, got %d", len(out), view.Size())
- }
- })
- }
-}
diff --git a/pkg/buffer/view_unsafe.go b/pkg/buffer/view_unsafe.go
index d1ef39b26..d1ef39b26 100644..100755
--- a/pkg/buffer/view_unsafe.go
+++ b/pkg/buffer/view_unsafe.go
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-15 23:39:52 +0000