immutable

README

Immutable containers for Golang

This package provides immutable Map and Vector implementations for Golang. The containers are immutable in the sense that all modifying operations return an updated version of the container and keeps the original container untouched.

API docs

Documentation

Overview

Package immutable provides immutable containers for building applications that handle concurrency without locks.

The implementation tries to be as straightforward and minimal as possible, while still being performant enough for everyday use.

Basics

The containers in this package return a new version of themselves as the result of any updating operation. This makes the data structure as a whole immutable. There is no way to change existing instances.

Iterating during modification for example, is not an issue. It simply cannot happen.

The containers hold values of type interface{}.

Copying

Making copies of an immutable container is cheap and independent of the current size.

Copying is not atomic, however, just like as there is no guarantee for atomic assignment of pointers.

Use channels as usual to communicate, or atomic.Value if you really need to.

Performance

Comparing these containers to built-in constructs in Go or other mutable containers is a bit of an apples to oranges comparison.

Modifying a container creates a new instance, which requires memory allocations. There is no need for mutexes to make the containers safe for use in multiple concurrent threads, however.

And the Vector for example, is sparse, so growing from 1 to a million addressable elements is much faster than the same operation for slices.

Check out the benchmarks for some example comparisons of performance.

Basic use

A zero-valued container is empty and ready to use.

var myMap Map
myMap = myMap.Set("thing", 42)

a := Vector{}.Resize(4711)
b := a.Set(1000, "hallå!")

Index

• type Map
  • func (m Map) Delete(key interface{}) Map
  • func (m Map) Get(key interface{}) (interface{}, bool)
  • func (m *Map) Range(visitor func(key, value interface{}) bool)
  • func (m Map) Set(key, value interface{}) Map
  • func (m *Map) Size() uint32
• type Vector
  • func (v Vector) Append(value interface{}) Vector
  • func (v Vector) Elements() VectorRange
  • func (v Vector) Get(index uint32) interface{}
  • func (v Vector) Resize(size uint32) Vector
  • func (v Vector) Set(index uint32, value interface{}) Vector
  • func (v Vector) Size() uint32
  • func (v Vector) Slice(start, end uint32) Vector
• type VectorRange
  • func (vr *VectorRange) Get() interface{}
  • func (vr *VectorRange) Next() bool

Types

type Map

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

Map is an immutable hash map with copy-on-write semantics. Adding to or deleting from the map returns a new map instance. Since the map is immutable, it is safe to use from multiple concurrent threads without locks or other synchronization.

Copying the map is cheap, but since it is a struct, it is not done atomically. To get atomic copying, use channels, atomic.Value or similar.

Map is different from Go map and sync.Map since it safe to copy and is copied by value.

The zero Map is empty and ready for use.

func (Map) Delete

func (m Map) Delete(key interface{}) Map

Delete returns a map without entries matching the key. If no entry matches, the original map is returned.

func (Map) Get

func (m Map) Get(key interface{}) (interface{}, bool)

Get retrieves a value from the map.

func (*Map) Range

func (m *Map) Range(visitor func(key, value interface{}) bool)

Range calls visitor for each element in the map. If visitor returns false, the iteration stops. Since the map is immutable, it will not change during iteration.

func (Map) Set

func (m Map) Set(key, value interface{}) Map

Set adds an entry to a map and returns the updated map.

func (*Map) Size

func (m *Map) Size() uint32

Size returns the number of elements in the map.

type Vector

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

Vector is an immutable vector with copy-on-write semantics. Modifying the vector returns a new vector instance. Since the vector is immutable, it is safe to use from multiple concurrent threads without locks or other synchronization.

Copying the vector is cheap, but since it is a struct, it is not done atomically. To get atomic copying, use channels, atomic.Value or similar.

The zero Vector is empty and ready for use.

func (Vector) Append

func (v Vector) Append(value interface{}) Vector

Append adds an element and returns the updated Vector.

func (Vector) Elements

func (v Vector) Elements() VectorRange

Elements returns a range for iterating through the vector.

func (Vector) Get

func (v Vector) Get(index uint32) interface{}

Get returns the element at the given index. Out of bounds access causes panic.

func (Vector) Resize

func (v Vector) Resize(size uint32) Vector

Resize Grows or shrinks a vector to the given size and returns the resized vector. The vector capacity is not affected unless needed to grow the vector. Allocated but ununsed storage is not affected.

func (Vector) Set

func (v Vector) Set(index uint32, value interface{}) Vector

Set sets the element at the given index and returns the updated Vector. Out of bounds access causes panic.

func (Vector) Size

func (v Vector) Size() uint32

Size returns vector size.

func (Vector) Slice

func (v Vector) Slice(start, end uint32) Vector

Slice returns a slice of a vector for the specified range. Ranges that extend the vector end returns a slice shorter than the given range. Invalid ranges causes panic.

type VectorRange

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

func (*VectorRange) Get

func (vr *VectorRange) Get() interface{}

Get returns the element at the current position of the range.

func (*VectorRange) Next

func (vr *VectorRange) Next() bool

Next moves to the next element and returns true if there are more elements available.