clist

Documentation

Index

• Constants
• type CElement
  • func (e *CElement) DetachNext()
  • func (e *CElement) DetachPrev()
  • func (e *CElement) Next() *CElement
  • func (e *CElement) NextWait() *CElement
  • func (e *CElement) NextWaitChan() <-chan struct{}
  • func (e *CElement) Prev() *CElement
  • func (e *CElement) PrevWait() *CElement
  • func (e *CElement) PrevWaitChan() <-chan struct{}
  • func (e *CElement) Removed() bool
  • func (e *CElement) SetNext(newNext *CElement)
  • func (e *CElement) SetPrev(newPrev *CElement)
  • func (e *CElement) SetRemoved()
• type CList
  • func New() *CList
  • func (l *CList) Back() *CElement
  • func (l *CList) BackWait() *CElement
  • func (l *CList) Front() *CElement
  • func (l *CList) FrontWait() *CElement
  • func (l *CList) Init() *CList
  • func (l *CList) Len() int
  • func (l *CList) PushBack(v any) *CElement
  • func (l *CList) Remove(e *CElement) any
  • func (l *CList) WaitChan() <-chan struct{}

Constants

const MaxLength = int(^uint(0) >> 1)

MaxLength is the max allowed number of elements a linked list is allowed to contain. If more elements are pushed to the list it will panic.

Types

type CElement

type CElement struct {
	Value any // immutable
	// contains filtered or unexported fields
}

CElement is an element of a linked-list Traversal from a CElement is goroutine-safe.

We can't avoid using WaitGroups or for-loops given the documentation spec without re-implementing the primitives that already exist in golang/sync. Notice that WaitGroup allows many go-routines to be simultaneously released, which is what we want. Mutex doesn't do this. RWMutex does this, but it's clumsy to use in the way that a WaitGroup would be used -- and we'd end up having two RWMutex's for prev/next each, which is doubly confusing.

sync.Cond would be sort-of useful, but we don't need a write-lock in the for-loop. Use sync.Cond when you need serial access to the "condition". In our case our condition is if `next != nil || removed`, and there's no reason to serialize that condition for goroutines waiting on NextWait() (since it's just a read operation).

func (*CElement) DetachNext

func (e *CElement) DetachNext()

func (*CElement) DetachPrev

func (e *CElement) DetachPrev()

func (*CElement) Next

func (e *CElement) Next() *CElement

Nonblocking, may return nil if at the end.

func (*CElement) NextWait

func (e *CElement) NextWait() *CElement

Blocking implementation of Next(). May return nil iff CElement was tail and got removed.

func (*CElement) NextWaitChan

func (e *CElement) NextWaitChan() <-chan struct{}

NextWaitChan can be used to wait until Next becomes not nil. Once it does, channel will be closed.

func (*CElement) Prev

func (e *CElement) Prev() *CElement

Nonblocking, may return nil if at the end.

func (*CElement) PrevWait

func (e *CElement) PrevWait() *CElement

Blocking implementation of Prev(). May return nil iff CElement was head and got removed.

func (*CElement) PrevWaitChan

func (e *CElement) PrevWaitChan() <-chan struct{}

PrevWaitChan can be used to wait until Prev becomes not nil. Once it does, channel will be closed.

func (*CElement) Removed

func (e *CElement) Removed() bool

func (*CElement) SetNext

func (e *CElement) SetNext(newNext *CElement)

NOTE: This function needs to be safe for concurrent goroutines waiting on nextWg.

func (*CElement) SetPrev

func (e *CElement) SetPrev(newPrev *CElement)

NOTE: This function needs to be safe for concurrent goroutines waiting on prevWg.

func (*CElement) SetRemoved

func (e *CElement) SetRemoved()

type CList

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

CList represents a linked list. The zero value for CList is an empty list ready to use. Operations are goroutine-safe. Panics if length grows beyond the max.

func New

func New() *CList

Return CList with MaxLength. CList will panic if it goes beyond MaxLength.

func (*CList) Back

func (l *CList) Back() *CElement

func (*CList) BackWait

func (l *CList) BackWait() *CElement

func (*CList) Front

func (l *CList) Front() *CElement

func (*CList) FrontWait

func (l *CList) FrontWait() *CElement

func (*CList) Init

func (l *CList) Init() *CList

func (*CList) Len

func (l *CList) Len() int

func (*CList) PushBack

func (l *CList) PushBack(v any) *CElement

Panics if list grows beyond its max length.

func (*CList) Remove

func (l *CList) Remove(e *CElement) any

CONTRACT: Caller must call e.DetachPrev() and/or e.DetachNext() to avoid memory leaks. NOTE: As per the contract of CList, removed elements cannot be added back.

func (*CList) WaitChan

func (l *CList) WaitChan() <-chan struct{}

WaitChan can be used to wait until Front or Back becomes not nil. Once it does, channel will be closed.