package ilist

import "gvisor.dev/gvisor/pkg/ilist"

Package ilist provides the implementation of intrusive linked lists.

Package ring is an implementation of an intrusive circular linked list.

Index ¶

• type Container
• type Element
• type ElementMapper
• type Entry
• func (e *Entry) Add(new *Entry)
• func (e *Entry) Empty() bool
• func (e *Entry) Init(container Container)
• func (e *Entry) Next() Element
• func (e *Entry) Prev() Element
• func (e *Entry) Remove()
• func (e *Entry) SetNext(elem Element)
• func (e *Entry) SetPrev(elem Element)
• type Linker
• type List
• func (l *List) Back() Element
• func (l *List) Empty() bool
• func (l *List) Front() Element
• func (l *List) InsertAfter(b, e Element)
• func (l *List) InsertBefore(a, e Element)
• func (l *List) Len() (count int)
• func (l *List) PushBack(e Element)
• func (l *List) PushBackList(m *List)
• func (l *List) PushFront(e Element)
• func (l *List) PushFrontList(m *List)
• func (l *List) Remove(e Element)
• func (l *List) Reset()

Types ¶

type Container ¶

type Container any

Container is the type that holds the list entries.

type Element ¶

type Element interface {
	Linker
}

Element the item that is used at the API level.

N.B. Like Linker, this is unlikely to be an interface in most cases.

type ElementMapper ¶

type ElementMapper struct{}

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 Entry ¶

type Entry struct {
	// contains filtered or unexported fields
}

Entry is an element in the circular linked list.

+stateify savable

func (*Entry) Add ¶

func (e *Entry) Add(new *Entry)

Add adds new to old's ring.

func (*Entry) Empty ¶

func (e *Entry) Empty() bool

Empty returns true if there are no other elements in the ring.

func (*Entry) Init ¶

func (e *Entry) Init(container Container)

Init instantiates an Element to be an item in a ring (circularly-linked list).

func (*Entry) Next ¶

func (e *Entry) Next() Element

Next returns the entry that follows e in the list.

func (*Entry) Prev ¶

func (e *Entry) Prev() Element

Prev returns the entry that precedes e in the list.

func (*Entry) Remove ¶

func (e *Entry) Remove()

Remove removes e from its ring and reinitializes it.

func (*Entry) SetNext ¶

func (e *Entry) SetNext(elem Element)

SetNext assigns 'entry' as the entry that follows e in the list.

func (*Entry) SetPrev ¶

func (e *Entry) SetPrev(elem Element)

SetPrev assigns 'entry' as the entry that precedes e in the list.

type Linker ¶

type Linker interface {
	Next() Element
	Prev() Element
	SetNext(Element)
	SetPrev(Element)
}

Linker is the interface that objects must implement if they want to be added to and/or removed from List objects.

N.B. When substituted in a template instantiation, Linker doesn't need to be an interface, and in most cases won't be.

type List ¶

type List struct {
	// contains filtered or unexported fields
}

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

func (*List) Back ¶

func (l *List) Back() Element

Back returns the last element of list l or nil.

func (*List) Empty ¶

func (l *List) Empty() bool

Empty returns true iff the list is empty.

func (*List) Front ¶

func (l *List) Front() Element

Front returns the first element of list l or nil.

func (*List) InsertAfter ¶

func (l *List) InsertAfter(b, e Element)

InsertAfter inserts e after b.

func (*List) InsertBefore ¶

func (l *List) InsertBefore(a, e Element)

InsertBefore inserts e before a.

func (*List) Len ¶

func (l *List) Len() (count int)

Len returns the number of elements in the list.

NOTE: This is an O(n) operation.

func (*List) PushBack ¶

func (l *List) PushBack(e Element)

PushBack inserts the element e at the back of list l.

func (*List) PushBackList ¶

func (l *List) PushBackList(m *List)

PushBackList inserts list m at the end of list l, emptying m.

func (*List) PushFront ¶

func (l *List) PushFront(e Element)

PushFront inserts the element e at the front of list l.

func (*List) PushFrontList ¶

func (l *List) PushFrontList(m *List)

PushFrontList inserts list m at the start of list l, emptying m.

func (*List) Remove ¶

func (l *List) Remove(e Element)

Remove removes e from l.

func (*List) Reset ¶

func (l *List) Reset()

Reset resets list l to the empty state.

Source Files ¶

list.go ring.go