goulist

README

goulist

Goulist package is an Urolled Linked List written in pure Go.

TOC

• Version
• Install
• Content
• Usage

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

Java implementation

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 NewUlist() *Ulist
  • func NewUlistCustomCap(c int) *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.

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

func NewUlistCustomCap(c int) *Ulist

NewUlistCustomCap creates new empty unrolled linked list. Elem fields of list's nodes have length equal c. Returns pointer to empty list.

func (*Ulist) Clear

func (ul *Ulist) Clear()

Clear sets all list's element to nil.

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

func (ul *Ulist) Get(nodeNum, elemNum int) (interface{}, error)

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

func (ul *Ulist) GetSize() int

GetSize returns number of list's nodes

func (*Ulist) Insert

func (ul *Ulist) Insert(val interface{}, num int) error

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

func (ul *Ulist) IsContains(val interface{}) bool

IsContains returns true if list contains at least one element val.

func (*Ulist) IsContainsAll

func (ul *Ulist) IsContainsAll(vals []interface{}) bool

IsContainsAll returns true if this list contains all of the elements of the given slice.

func (*Ulist) Len

func (ul *Ulist) Len() int

Len returns number of all non-nil elements stored in list

func (*Ulist) Print

func (ul *Ulist) Print()

Print prints each list's element.

func (*Ulist) Printc

func (ul *Ulist) Printc(w io.Writer)

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

func (ul *Ulist) Push(val interface{}) error

Push appends new element val to the end of list. Returns the error on failure.

func (*Ulist) PushAll

func (ul *Ulist) PushAll(vals []interface{}) error

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

func (ul *Ulist) RemoveFromNode(nodeNum, elemNum int) error

RemoveInNode removes element with index elemNum from node with index nodeNum. Returns error if node's index is greater than list's size.

func (*Ulist) Set

func (ul *Ulist) Set(nodeNum, elemNum int, val interface{}) (interface{}, error)

Set replaces the element at index elemNum in node with index nodeNum with given element val. Returns new value of the element and error if node's index is greater than list's size.