clist

package
v0.0.4 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Jul 5, 2023 License: Apache-2.0 Imports: 3 Imported by: 0

Documentation

Index

Constants

View Source
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.

Variables

This section is empty.

Functions

This section is empty.

Types

type CElement

type CElement struct {
	Value interface{} // 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 interface{}) *CElement

Panics if list grows beyond its max length.

func (*CList) Remove

func (l *CList) Remove(e *CElement) interface{}

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.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL