ilist

Documentation

Overview

Package ilist provides the implementation of intrusive linked lists.

Index

• type Element
• type ElementMapper
• type Entry
  • func (e *Entry) Next() Element
  • func (e *Entry) Prev() Element
  • 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) Remove(e Element)
  • func (l *List) Reset()

Types

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

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) 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) 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.