mvslice

Documentation

Overview

Package mvslice defines a multi value slice container. The purpose of the container is to be a replacement for a slice in scenarios where many objects of the same type share a copy of an identical or nearly identical slice. In such case using the multi value slice should result in less memory allocation because many values of the slice can be shared between objects.

The multi value slice should be initialized by calling the Init function and passing the initial values of the slice. After initializing the slice, it can be shared between object by using the Copy function. Note that simply assigning the same multi value slice to several objects is not enough for it to work properly. Calling Copy is required in most circumstances (an exception is when the source object has only shared values).

s := &Slice[int, *testObject]{}
s.Init([]int{1, 2, 3})
src := &testObject{id: id1, slice: s} // id1 is some UUID
dst := &testObject{id: id2, slice: s} // id2 is some UUID
s.Copy(src, dst)

Each Value stores a value of type V along with identifiers to objects that have this value. A MultiValueItem is a slice of Value elements. A Slice contains shared items, individual items and appended items.

You can think of a shared value as the original value (i.e. the value at the point in time when the multi value slice was constructed), and of an individual value as a changed value. There is no notion of a shared appended value because appended values never have an original value (appended values are empty when the slice is created).

Whenever any of the slice’s functions (apart from Init) is called, the function needs to know which object it is dealing with. This is because if an object has an individual/appended value, the function must get/set/change this particular value instead of the shared value or another individual/appended value.

The way appended items are stored is as follows. Let’s say appended items were a regular slice that is initially empty, and we append an item for object0 and then append another item for object1. Now we have two items in the slice, but object1 only has an item in index 1. This makes things very confusing and hard to deal with. If we make appended items a []*Value, things don’t become much better. It is therefore easiest to make appended items a []*MultiValueItem, which allows each object to have its own values starting at index 0 and not having any “gaps”.

The Detach function should be called when an object gets garbage collected. Its purpose is to clean up the slice from individual/appended values of the collected object. Otherwise the slice will get polluted with values for non-existing objects.

Example diagram illustrating what happens after copying, updating and detaching:

	Create object o1 with value 10. At this point we only have a shared value.

	===================
	shared | individual
	===================
	10     |

	Copy object o1 to object o2. o2 shares the value with o1, no individual value is created.

	===================
	shared | individual
	===================
	10     |

	Update value of object o2 to 20. An individual value is created.

	===================
	shared | individual
	===================
	10     | 20: [o2]

	 Copy object o2 to object o3. The individual value's object list is updated.

	===================
	shared | individual
	===================
	10     | 20: [o2,o3]

	 Update value of object o3 to 30. There are two individual values now, one for o2 and one for o3.

	===================
	shared | individual
	===================
	10     | 20: [o2]
	       | 30: [o3]

	 Update value of object o2 to 10. o2 no longer has an individual value
	 because it got "reverted" to the original, shared value,

	===================
	shared | individual
 ===================
	10     | 30: [o3]

	 Detach object o3. Individual value for o3 is removed.

	===================
	shared | individual
	===================
	10     |

Index

• type EmptyMVSlice
  • func (e EmptyMVSlice[V]) At(_ Identifiable, index uint64) (V, error)
  • func (e EmptyMVSlice[V]) Len(_ Identifiable) int
  • func (e EmptyMVSlice[V]) Value(_ Identifiable) []V
• type Id
• type Identifiable
• type MultiValueItem
• type MultiValueSlice
• type MultiValueSliceComposite
  • func BuildEmptyCompositeSlice[V comparable](values []V) MultiValueSliceComposite[V]
  • func (m MultiValueSliceComposite[V]) State() Identifiable
• type MultiValueStatistics
• type Slice
  • func (s *Slice[V]) Append(obj Identifiable, val V)
  • func (s *Slice[V]) At(obj Identifiable, index uint64) (V, error)
  • func (s *Slice[V]) Copy(src, dst Identifiable)
  • func (s *Slice[V]) Detach(obj Identifiable)
  • func (s *Slice[V]) Init(items []V)
  • func (s *Slice[V]) IsFragmented() bool
  • func (s *Slice[V]) Len(obj Identifiable) int
  • func (s *Slice[V]) MultiValueStatistics() MultiValueStatistics
  • func (s *Slice[V]) Reset(obj Identifiable) *Slice[V]
  • func (s *Slice[V]) UpdateAt(obj Identifiable, index uint64, val V) error
  • func (s *Slice[V]) Value(obj Identifiable) []V
• type Value

Types

type EmptyMVSlice

type EmptyMVSlice[V comparable] struct {
	// contains filtered or unexported fields
}

EmptyMVSlice specifies a type which allows a normal slice to conform to the multivalue slice interface.

func (EmptyMVSlice[V]) At

func (e EmptyMVSlice[V]) At(_ Identifiable, index uint64) (V, error)

func (EmptyMVSlice[V]) Len

func (e EmptyMVSlice[V]) Len(_ Identifiable) int

func (EmptyMVSlice[V]) Value

func (e EmptyMVSlice[V]) Value(_ Identifiable) []V

type Id

type Id = uint64

Id is an object identifier.

type Identifiable

type Identifiable interface {
	Id() Id
}

Identifiable represents an object that can be uniquely identified by its Id.

type MultiValueItem

type MultiValueItem[V any] struct {
	Values []*Value[V]
}

MultiValueItem defines a collection of Value items.

type MultiValueSlice

type MultiValueSlice[V comparable] interface {
	Len(obj Identifiable) int
	At(obj Identifiable, index uint64) (V, error)
	Value(obj Identifiable) []V
}

MultiValueSlice defines an abstraction over all concrete implementations of the generic Slice.

type MultiValueSliceComposite

type MultiValueSliceComposite[V comparable] struct {
	Identifiable
	MultiValueSlice[V]
}

MultiValueSliceComposite describes a struct for which we have access to a multivalue slice along with the desired state.

func BuildEmptyCompositeSlice

func BuildEmptyCompositeSlice[V comparable](values []V) MultiValueSliceComposite[V]

BuildEmptyCompositeSlice builds a composite multivalue object with a native slice.

func (MultiValueSliceComposite[V]) State

func (m MultiValueSliceComposite[V]) State() Identifiable

State returns the referenced state.

type MultiValueStatistics

type MultiValueStatistics struct {
	TotalIndividualElements       int
	TotalAppendedElements         int
	TotalIndividualElemReferences int
	TotalAppendedElemReferences   int
}

MultiValueStatistics represents the internal properties of a multivalue slice.

type Slice

type Slice[V comparable] struct {
	// contains filtered or unexported fields
}

Slice is the main component of the multi-value slice data structure. It has two type parameters:

• V comparable - the type of values stored the slice. The constraint is required because certain operations (e.g. updating, appending) have to compare values against each other.
• O interfaces.Identifiable - the type of objects sharing the slice. The constraint is required because we need a way to compare objects against each other in order to know which objects values should be accessed.

func (*Slice[V]) Append

func (s *Slice[V]) Append(obj Identifiable, val V)

Append adds a new item to the input object.

func (*Slice[V]) At

func (s *Slice[V]) At(obj Identifiable, index uint64) (V, error)

At returns the item at the requested index for the input object. Appended items' indices are always larger than shared/individual items' indices. We first check if the index is within the length of shared items. If it is, then we return an individual value at that index - if it exists - or a shared value otherwise. If the index is beyond the length of shared values, it is an appended item and that's what gets returned.

func (*Slice[V]) Copy

func (s *Slice[V]) Copy(src, dst Identifiable)

Copy copies items between the source and destination.

func (*Slice[V]) Detach

func (s *Slice[V]) Detach(obj Identifiable)

Detach removes the input object from the multi-value slice. What this means in practice is that we remove all individual and appended values for that object and clear the cached length.

func (*Slice[V]) Init

func (s *Slice[V]) Init(items []V)

Init initializes the slice with sensible defaults. Input values are assigned to shared items.

func (*Slice[V]) IsFragmented

func (s *Slice[V]) IsFragmented() bool

IsFragmented checks if our mutlivalue object is fragmented (individual references held). If the number of references is higher than our threshold we return true.

func (*Slice[V]) Len

func (s *Slice[V]) Len(obj Identifiable) int

Len returns the number of items for the input object.

func (*Slice[V]) MultiValueStatistics

func (s *Slice[V]) MultiValueStatistics() MultiValueStatistics

MultiValueStatistics generates the multi-value stats object for the respective multivalue slice.

func (*Slice[V]) Reset

func (s *Slice[V]) Reset(obj Identifiable) *Slice[V]

Reset builds a new multivalue object with respect to the provided object's id. The base slice will be based on this particular id.

func (*Slice[V]) UpdateAt

func (s *Slice[V]) UpdateAt(obj Identifiable, index uint64, val V) error

UpdateAt updates the item at the required index for the input object to the passed in value.

func (*Slice[V]) Value

func (s *Slice[V]) Value(obj Identifiable) []V

Value returns all items for the input object.

type Value

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

Value defines a single value along with one or more IDs that share this value.