ulist

ulist

import "github.com/zyedidia/generic/ulist"

Example

// Ideally 'entriesPerBlock' is the size of a cache line (64) or multiples there of.
entriesPerBlock := int(64 / unsafe.Sizeof(int(0)))
ul := New[int](entriesPerBlock)
ul.PushBack(1)
ul.PushBack(2)
ul.PushFront(0)

for iter := ul.Begin(); iter.IsValid(); iter.Next() {
	fmt.Printf("%d\n", iter.Get())
}
// Output:
// 0
// 1
// 2

Output

0
1
2

Index

• type UList
  • func New[V any](entriesPerBlock int) *UList[V]
  • func (ul *UList[V]) AddAfter(iter *UListIter[V], v V)
  • func (ul *UList[V]) AddBefore(iter *UListIter[V], v V)
  • func (ul *UList[V]) Begin() *UListIter[V]
  • func (ul *UList[V]) End() *UListIter[V]
  • func (ul *UList[V]) PushBack(v V)
  • func (ul *UList[V]) PushFront(v V)
  • func (ul *UList[V]) Remove(iter *UListIter[V])
  • func (ul *UList[V]) Size() int
• type UListIter
  • func (iter *UListIter[V]) Get() V
  • func (iter *UListIter[V]) IsValid() bool
  • func (iter *UListIter[V]) Next() bool
  • func (iter *UListIter[V]) Prev() bool

type UList

UList implements a doubly-linked unolled list.

type UList[V any] struct {
    // contains filtered or unexported fields
}

func New

func New[V any](entriesPerBlock int) *UList[V]

New returns an empty unrolled linked list. 'entriesPerBlock' is the number of entries to store in each block. This value should ideally be the size of a cache-line or multiples there-of. See: https://en.wikipedia.org/wiki/Unrolled_linked_list

func (*UList[V]) AddAfter

func (ul *UList[V]) AddAfter(iter *UListIter[V], v V)

AddAfter adds 'v' to 'ul' after the entry pointed to by 'iter'. 'iter' is expected to be valid, i.e. iter->IsValid() == true. 'iter' is updated to now point to the new entry added, such that iter->Get() == 'v'.

func (*UList[V]) AddBefore

func (ul *UList[V]) AddBefore(iter *UListIter[V], v V)

AddBefore adds 'v' to 'ul' before the entry pointed to by 'iter'. 'iter' is expected to be valid, i.e. iter->IsValid() == true. 'iter' is updated to now point to the new entry added, such that iter->Get() == 'v'.

func (*UList[V]) Begin

func (ul *UList[V]) Begin() *UListIter[V]

Begin returns an UListIter pointing to the first entry in the UList.

func (*UList[V]) End

func (ul *UList[V]) End() *UListIter[V]

End returns an UListIter pointing to the last entry in the UList.

func (*UList[V]) PushBack

func (ul *UList[V]) PushBack(v V)

PushBack adds 'v' to the end of the ulist.

func (*UList[V]) PushFront

func (ul *UList[V]) PushFront(v V)

PushFront adds 'v' to the beginning of the ulist.

func (*UList[V]) Remove

func (ul *UList[V]) Remove(iter *UListIter[V])

Remove deletes the entry in 'ul' pointed to by 'iter'. 'iter' is moved forward in the process. i.e. iter.Get() returns the element in 'ul' that occurs after the deleted entry.

func (*UList[V]) Size

func (ul *UList[V]) Size() int

Size returns the number of entries in 'ul'.

type UListIter

A UListIter points to an element in the UList.

type UListIter[V any] struct {
    // contains filtered or unexported fields
}

func (*UListIter[V]) Get

func (iter *UListIter[V]) Get() V

Get returns the entry in the UList that the 'iter' is pointing to. This call should only ever be made when iter.IsValid() is true.

func (*UListIter[V]) IsValid

func (iter *UListIter[V]) IsValid() bool

IsValid returns true if the iterator points to a valid entry in the UList.

func (*UListIter[V]) Next

func (iter *UListIter[V]) Next() bool

Next moves the iterator one step forward and returns true if the iterator is valid.

func (*UListIter[V]) Prev

func (iter *UListIter[V]) Prev() bool

Prev moves the iterator one step back and returns true if the iterator is valid.

Generated by gomarkdoc