README
¶
goulist
Goulist package is an Urolled Linked List written in pure Go.
TOC
Version
1.0.3
Install
go get github.com/hIMEI29A/goulist
Content
Unrolled linked list
Unrolled linked list (ULL) is an doubly linked list each node of which holds up to a certain maximum number of elements, typically just large enough so that the node fills a single cache line or a small multiple thereof.
It has a special algorithm for insertion and deletion of elements.
As Wikipedia says,
To insert a new element, we simply find the node the element should be in and insert the element into the elements array, incrementing numElements. If the array is already full, we first insert a new node either preceding or following the current one and move half of the elements in the current node into it.
To remove an element, we simply find the node it is in and delete it from the elements array, decrementing numElements. If this reduces the node to less than half-full, then we move elements from the next node to fill it back up above half. If this leaves the next node less than half full, then we move all its remaining elements into the current node, then bypass and delete it.
After deletion, all nil elements in the node are shifted to the right to avoid empty spaces.
Default constructor of ULL creates list the length of the arrays (slices in fact) at the nodes of which is equal to cache line size. Creation with custom array (slice) length is also possible.
See Wikipedia article for details.
Related
Another Golang implementation, but it seems does not work as expected.
Usage
Import package:
import (
"github.com/hIMEI29A/goulist"
)
Documentation
¶
Overview ¶
Package ulist implements unrolled linked list.
Each node holds up to a certain maximum number of elements, typically just large enough so that the node fills a single cache line or a small multiple thereof. To insert a new element, we simply find the node the element should be in and insert the element into the elements array, incrementing numElements. If the array is already full, we first insert a new node either preceding or following the current one and move half of the elements in the current node into it. To remove an element, we simply find the node it is in and delete it from the elements array, decrementing numElements. If this reduces the node to less than half-full, then we move elements from the next node to fill it back up above half. If this leaves the next node less than half full, then we move all its remaining elements into the current node, then bypass and delete it.
See http://en.wikipedia.org/wiki/Unrolled_linked_list for details
Index ¶
- Constants
- type Ulist
- func (ul *Ulist) Clear()
- func (ul *Ulist) Do(fn func(*interface{}))
- func (ul *Ulist) ExportElems() []interface{}
- func (ul *Ulist) Get(nodeNum, elemNum int) (interface{}, error)
- func (ul *Ulist) GetFirst() []interface{}
- func (ul *Ulist) GetLast() []interface{}
- func (ul *Ulist) GetSize() int
- func (ul *Ulist) Insert(val interface{}, num int) error
- func (ul *Ulist) IsContains(val interface{}) bool
- func (ul *Ulist) IsContainsAll(vals []interface{}) bool
- func (ul *Ulist) Len() int
- func (ul *Ulist) Print()
- func (ul *Ulist) Printc(w io.Writer)
- func (ul *Ulist) Push(val interface{}) error
- func (ul *Ulist) PushAll(vals []interface{}) error
- func (ul *Ulist) RemoveAllOccurrences(val interface{})
- func (ul *Ulist) RemoveAllOfSlice(vals []interface{})
- func (ul *Ulist) RemoveFromNode(nodeNum, elemNum int) error
- func (ul *Ulist) Set(nodeNum, elemNum int, val interface{}) (interface{}, error)
Constants ¶
const CacheLineSize = int(unsafe.Sizeof(cpu.CacheLinePad{}))
CacheLineSize represents the cache line size of the current CPU. See https://en.wikipedia.org/wiki/CPU_cache for details.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Ulist ¶
type Ulist struct {
// contains filtered or unexported fields
}
Ulist is an unrolled linked list itself. It contains links to first and last nodes and number of nodes.
func NewUlist ¶
func NewUlist() *Ulist
NewUlist creates new empty unrolled linked list. It has only one (empty) node which is first and last same time. Elem fields of list's nodes have length equal to CacheLineSize. Returns pointer to empty list.
func NewUlistCustomCap ¶
NewUlistCustomCap creates new empty unrolled linked list. Elem fields of list's nodes have length equal c. Returns pointer to empty list.
func (*Ulist) Do ¶
func (ul *Ulist) Do(fn func(*interface{}))
Do calls function fn on each list's element.
func (*Ulist) ExportElems ¶
func (ul *Ulist) ExportElems() []interface{}
ExportElems returns slice filled with all list's elements.
func (*Ulist) Get ¶
Get returns element stored at the index elemNum in node with index nodeNum and error if node's index is greater than list's size.
func (*Ulist) GetFirst ¶
func (ul *Ulist) GetFirst() []interface{}
GetFirst returns slice filled with all list's first node non-nil elements.
func (*Ulist) GetLast ¶
func (ul *Ulist) GetLast() []interface{}
GetLast returns slice filled with all list's last node non-nil elements.
func (*Ulist) Insert ¶
Insert inserts a new element val at the target node with index num. If target node is full, it creates a new node and moves there the number of elements of the target node equal to half the length of the node. New element val will be added to the end of new node. New node will be inserted to list after target node. Function returns error if given index is greater than node.capacity.
func (*Ulist) IsContains ¶
IsContains returns true if list contains at least one element val.
func (*Ulist) IsContainsAll ¶
IsContainsAll returns true if this list contains all of the elements of the given slice.
func (*Ulist) Printc ¶
Printc (Print custom) prints each list's element to given io,Writer w. It calls fmt.Errorf and os.Exit(1) in case of error.
func (*Ulist) PushAll ¶
PushAll appends all of the elements of the given slice vals to the end of the list, in the original order. Returns error on failure.
func (*Ulist) RemoveAllOccurrences ¶
func (ul *Ulist) RemoveAllOccurrences(val interface{})
RemoveAllOccurrences removes all occurrences of element val from list.
func (*Ulist) RemoveAllOfSlice ¶
func (ul *Ulist) RemoveAllOfSlice(vals []interface{})
RemoveAllOfSlice removes all elements of given slice vals from the list.
func (*Ulist) RemoveFromNode ¶
RemoveInNode removes element with index elemNum from node with index nodeNum. Returns error if node's index is greater than list's size.
Source Files