crdt

package
v0.5.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Sep 5, 2024 License: Apache-2.0 Imports: 15 Imported by: 0

Documentation

Overview

Package crdt provides the implementation of the CRDT data structure. The CRDT data structure is a data structure that can be replicated and shared among multiple replicas.

Index

Constants

This section is empty.

Variables

View Source 
var ErrChildNotFound = errors.New("child not found")

ErrChildNotFound is returned when the child is not found in the container.

View Source 
var (
	// ErrNodeNotFound is returned when the node is not found.
	ErrNodeNotFound = errors.New("node not found")
)
View Source 
var ErrUnsupportedType = errors.New("unsupported type")

ErrUnsupportedType is returned when the given type is not supported.

Functions

func CounterValueFromBytes 

func CounterValueFromBytes(counterType CounterType, value []byte) (interface{}, error)

CounterValueFromBytes parses the given bytes into value.

func EscapeString 

func EscapeString(s string) string

EscapeString returns a string that is safe to embed in a JSON document.

func ToXML added in v0.4.0 

func ToXML(node *TreeNode) string

ToXML returns the XML representation of this tree.

func ValueFromBytes 

func ValueFromBytes(valueType ValueType, value []byte) (interface{}, error)

ValueFromBytes parses the given bytes into value.

Types

type Array 

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

Array represents JSON array data structure including logical clock. Array implements Element interface.

func NewArray 

func NewArray(elements *RGATreeList, createdAt *time.Ticket, value ...[]Element) *Array

NewArray creates a new instance of Array.

func (*Array) Add 

func (a *Array) Add(elem Element) error

Add adds the given element at the last.

func (*Array) CreatedAt 

func (a *Array) CreatedAt() *time.Ticket

CreatedAt returns the creation time of this array.

func (*Array) DeepCopy 

func (a *Array) DeepCopy() (Element, error)

DeepCopy copies itself deeply.

func (*Array) Delete 

func (a *Array) Delete(idx int, deletedAt *time.Ticket) (Element, error)

Delete deletes the element of the given index.

func (*Array) DeleteByCreatedAt 

func (a *Array) DeleteByCreatedAt(createdAt *time.Ticket, deletedAt *time.Ticket) (Element, error)

DeleteByCreatedAt deletes the given element.

func (*Array) Descendants 

func (a *Array) Descendants(callback func(elem Element, parent Container) bool)

Descendants traverse the descendants of this array.

func (*Array) Elements 

func (a *Array) Elements() []Element

Elements returns an array of elements contained in this RGATreeList.

func (*Array) FindPrevCreatedAt 

func (a *Array) FindPrevCreatedAt(createdAt *time.Ticket) (*time.Ticket, error)

FindPrevCreatedAt returns the creation time of the previous element of the given element.

func (*Array) Get 

func (a *Array) Get(idx int) (Element, error)

Get returns the element of the given index.

func (*Array) InsertAfter 

func (a *Array) InsertAfter(prevCreatedAt *time.Ticket, element Element) error

InsertAfter inserts the given element after the given previous element.

func (*Array) LastCreatedAt 

func (a *Array) LastCreatedAt() *time.Ticket

LastCreatedAt returns the creation time of the last element.

func (*Array) Len 

func (a *Array) Len() int

Len returns length of this Array.

func (*Array) Marshal 

func (a *Array) Marshal() string

Marshal returns the JSON encoding of this Array.

func (*Array) MoveAfter 

func (a *Array) MoveAfter(prevCreatedAt, createdAt, executedAt *time.Ticket) error

MoveAfter moves the given `createdAt` element after the `prevCreatedAt` element.

func (*Array) MovedAt 

func (a *Array) MovedAt() *time.Ticket

MovedAt returns the move time of this array.

func (*Array) Purge 

func (a *Array) Purge(elem Element) error

Purge physically purge child element.

func (*Array) RGANodes 

func (a *Array) RGANodes() []*RGATreeListNode

RGANodes returns the slices of RGATreeListNode.

func (*Array) Remove 

func (a *Array) Remove(removedAt *time.Ticket) bool

Remove removes this array.

func (*Array) RemovedAt 

func (a *Array) RemovedAt() *time.Ticket

RemovedAt returns the removal time of this array.

func (*Array) Set added in v0.5.0 

func (a *Array) Set(createdAt *time.Ticket, element Element, executedAt *time.Ticket) (Element, error)

Set sets the given element at the given position of the creation time.

func (*Array) SetMovedAt 

func (a *Array) SetMovedAt(movedAt *time.Ticket)

SetMovedAt sets the move time of this array.

func (*Array) SetRemovedAt 

func (a *Array) SetRemovedAt(removedAt *time.Ticket)

SetRemovedAt sets the removal time of this array.

func (*Array) ToTestString added in v0.4.8 

func (a *Array) ToTestString() string

ToTestString returns a String containing the metadata of the elements for debugging purpose.

type Container 

type Container interface {
	Element

	// Purge physically purges the given child element.
	Purge(child Element) error

	// Descendants returns all descendants of this container.
	Descendants(callback func(elem Element, parent Container) bool)

	// DeleteByCreatedAt removes the given element from this container.
	DeleteByCreatedAt(createdAt *time.Ticket, deletedAt *time.Ticket) (Element, error)
}

Container represents Array or Object.

type Counter 

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

Counter represents changeable number data type.

func NewCounter 

func NewCounter(valueType CounterType, value interface{}, createdAt *time.Ticket) (*Counter, error)

NewCounter creates a new instance of Counter.

func (*Counter) Bytes 

func (p *Counter) Bytes() ([]byte, error)

Bytes creates an array representing the value.

func (*Counter) CreatedAt 

func (p *Counter) CreatedAt() *time.Ticket

CreatedAt returns the creation time.

func (*Counter) DeepCopy 

func (p *Counter) DeepCopy() (Element, error)

DeepCopy copies itself deeply.

func (*Counter) Increase 

func (p *Counter) Increase(v *Primitive) (*Counter, error)

Increase increases integer, long or double. If the result of the operation is greater than MaxInt32 or less than MinInt32, Counter's value type can be changed Integer to Long. Because in golang, int can be either int32 or int64. So we need to assert int to int32.

func (*Counter) IsNumericType 

func (p *Counter) IsNumericType() bool

IsNumericType checks for numeric types.

func (*Counter) Marshal 

func (p *Counter) Marshal() string

Marshal returns the JSON encoding of the value.

func (*Counter) MovedAt 

func (p *Counter) MovedAt() *time.Ticket

MovedAt returns the move time of this element.

func (*Counter) Remove 

func (p *Counter) Remove(removedAt *time.Ticket) bool

Remove removes this element.

func (*Counter) RemovedAt 

func (p *Counter) RemovedAt() *time.Ticket

RemovedAt returns the removal time of this element.

func (*Counter) SetMovedAt 

func (p *Counter) SetMovedAt(movedAt *time.Ticket)

SetMovedAt sets the move time of this element.

func (*Counter) SetRemovedAt 

func (p *Counter) SetRemovedAt(removedAt *time.Ticket)

SetRemovedAt sets the removal time of this element.

func (*Counter) Value added in v0.4.13 

func (p *Counter) Value() interface{}

Value returns the value of this counter. TODO(hackerwins): We need to use generics to avoid using interface{}.

func (*Counter) ValueType 

func (p *Counter) ValueType() CounterType

ValueType returns the type of the value.

type CounterType 

type CounterType int

CounterType represents any type that can be used as a counter. 

const (
	IntegerCnt CounterType = iota
	LongCnt
)

The values below are the types that can be used as counters.

type Element 

type Element interface {
	// Marshal returns the JSON encoding of this element.
	Marshal() string

	// DeepCopy copies itself deeply.
	DeepCopy() (Element, error)

	// CreatedAt returns the creation time of this element.
	CreatedAt() *time.Ticket

	// MovedAt returns the move time of this element.
	MovedAt() *time.Ticket

	// SetMovedAt sets the move time of this element.
	SetMovedAt(*time.Ticket)

	// RemovedAt returns the removal time of this element.
	RemovedAt() *time.Ticket

	// Remove removes this element.
	Remove(*time.Ticket) bool
}

Element represents JSON element.

type ElementPair 

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

ElementPair represents pair that has a parent element and child element.

type ElementRHT added in v0.3.1 

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

ElementRHT is a hashtable with logical clock(Replicated hashtable).

func NewElementRHT added in v0.3.1 

func NewElementRHT() *ElementRHT

NewElementRHT creates a new instance of ElementRHT.

func (*ElementRHT) Delete added in v0.3.1 

func (rht *ElementRHT) Delete(k string, deletedAt *time.Ticket) Element

Delete deletes the Element of the given key.

func (*ElementRHT) DeleteByCreatedAt added in v0.3.1 

func (rht *ElementRHT) DeleteByCreatedAt(createdAt *time.Ticket, deletedAt *time.Ticket) (Element, error)

DeleteByCreatedAt deletes the Element of the given creation time.

func (*ElementRHT) Elements added in v0.3.1 

func (rht *ElementRHT) Elements() map[string]Element

Elements returns a map of elements because the map easy to use for loop. TODO: If we encounter performance issues, we need to replace this with other solution.

func (*ElementRHT) Get added in v0.3.1 

func (rht *ElementRHT) Get(key string) Element

Get returns the value of the given key.

func (*ElementRHT) Has added in v0.3.1 

func (rht *ElementRHT) Has(key string) bool

Has returns whether the element exists of the given key or not.

func (*ElementRHT) Marshal added in v0.3.1 

func (rht *ElementRHT) Marshal() string

Marshal returns the JSON encoding of this map.

func (*ElementRHT) Nodes added in v0.3.1 

func (rht *ElementRHT) Nodes() []*ElementRHTNode

Nodes returns a map of elements because the map easy to use for loop. TODO: If we encounter performance issues, we need to replace this with other solution.

func (*ElementRHT) Set added in v0.3.1 

func (rht *ElementRHT) Set(k string, v Element) Element

Set sets the value of the given key. If there is an existing value, it is removed.

type ElementRHTNode added in v0.3.1 

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

ElementRHTNode is a node of ElementRHT.

func (*ElementRHTNode) Element added in v0.3.1 

func (n *ElementRHTNode) Element() Element

Element returns the element of this node.

func (*ElementRHTNode) Key added in v0.3.1 

func (n *ElementRHTNode) Key() string

Key returns the key of this node.

func (*ElementRHTNode) Remove added in v0.3.1 

func (n *ElementRHTNode) Remove(removedAt *time.Ticket) bool

Remove removes this node. It only marks the deleted time (tombstone).

type GCChild added in v0.4.20 

type GCChild interface {
	IDString() string
	RemovedAt() *time.Ticket
}

GCChild is an interface for the child of the garbage collection target.

type GCPair added in v0.4.20 

type GCPair struct {
	Parent GCParent
	Child  GCChild
}

GCPair is a structure that represents a pair of parent and child for garbage collection.

type GCParent added in v0.4.20 

type GCParent interface {
	Purge(node GCChild) error
}

GCParent is an interface for the parent of the garbage collection target.

type Object 

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

Object represents a JSON object, but unlike regular JSON, it has time tickets which is created by logical clock.

func NewObject 

func NewObject(memberNodes *ElementRHT, createdAt *time.Ticket, value ...map[string]Element) *Object

NewObject creates a new instance of Object.

func (*Object) CreatedAt 

func (o *Object) CreatedAt() *time.Ticket

CreatedAt returns the creation time of this object.

func (*Object) DeepCopy 

func (o *Object) DeepCopy() (Element, error)

DeepCopy copies itself deeply.

func (*Object) Delete 

func (o *Object) Delete(k string, deletedAt *time.Ticket) Element

Delete deletes the element of the given key.

func (*Object) DeleteByCreatedAt 

func (o *Object) DeleteByCreatedAt(createdAt *time.Ticket, deletedAt *time.Ticket) (Element, error)

DeleteByCreatedAt deletes the element of the given creation time.

func (*Object) Descendants 

func (o *Object) Descendants(callback func(elem Element, parent Container) bool)

Descendants traverse the descendants of this object.

func (*Object) Get 

func (o *Object) Get(k string) Element

Get returns the value of the given key.

func (*Object) Has 

func (o *Object) Has(k string) bool

Has returns whether the element exists of the given key or not.

func (*Object) Marshal 

func (o *Object) Marshal() string

Marshal returns the JSON encoding of this object.

func (*Object) Members 

func (o *Object) Members() map[string]Element

Members returns the member of this object as a map.

func (*Object) MovedAt 

func (o *Object) MovedAt() *time.Ticket

MovedAt returns the move time of this object.

func (*Object) Purge 

func (o *Object) Purge(elem Element) error

Purge physically purge child element.

func (*Object) RHTNodes 

func (o *Object) RHTNodes() []*ElementRHTNode

RHTNodes returns the ElementRHT nodes.

func (*Object) Remove 

func (o *Object) Remove(removedAt *time.Ticket) bool

Remove removes this object.

func (*Object) RemovedAt 

func (o *Object) RemovedAt() *time.Ticket

RemovedAt returns the removal time of this object.

func (*Object) Set 

func (o *Object) Set(k string, v Element) Element

Set sets the given element of the given key.

func (*Object) SetMovedAt 

func (o *Object) SetMovedAt(movedAt *time.Ticket)

SetMovedAt sets the move time of this object.

func (*Object) SetRemovedAt 

func (o *Object) SetRemovedAt(removedAt *time.Ticket)

SetRemovedAt sets the removal time of this array.

type Primitive 

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

Primitive represents JSON primitive data type including logical lock.

func NewPrimitive 

func NewPrimitive(value interface{}, createdAt *time.Ticket) (*Primitive, error)

NewPrimitive creates a new instance of Primitive.

func (*Primitive) Bytes 

func (p *Primitive) Bytes() []byte

Bytes creates an array representing the value.

func (*Primitive) CreatedAt 

func (p *Primitive) CreatedAt() *time.Ticket

CreatedAt returns the creation time.

func (*Primitive) DeepCopy 

func (p *Primitive) DeepCopy() (Element, error)

DeepCopy copies itself deeply.

func (*Primitive) IsNumericType 

func (p *Primitive) IsNumericType() bool

IsNumericType checks for numeric types.

func (*Primitive) Marshal 

func (p *Primitive) Marshal() string

Marshal returns the JSON encoding of the value.

func (*Primitive) MovedAt 

func (p *Primitive) MovedAt() *time.Ticket

MovedAt returns the move time of this element.

func (*Primitive) Remove 

func (p *Primitive) Remove(removedAt *time.Ticket) bool

Remove removes this element.

func (*Primitive) RemovedAt 

func (p *Primitive) RemovedAt() *time.Ticket

RemovedAt returns the removal time of this element.

func (*Primitive) SetMovedAt 

func (p *Primitive) SetMovedAt(movedAt *time.Ticket)

SetMovedAt sets the move time of this element.

func (*Primitive) SetRemovedAt 

func (p *Primitive) SetRemovedAt(removedAt *time.Ticket)

SetRemovedAt sets the removal time of this element.

func (*Primitive) Value 

func (p *Primitive) Value() interface{}

Value returns the value of Primitive.

func (*Primitive) ValueType 

func (p *Primitive) ValueType() ValueType

ValueType returns the type of the value.

type RGATreeList 

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

RGATreeList is a list with improved index-based lookup in RGA. RGA is a linked list that has a logical clock and tombstone. Since RGA is composed as a linked list, index-based element search is slow, O(n). To optimise for fast insertions and removals at any index in the list, RGATreeList has a tree.

func NewRGATreeList 

func NewRGATreeList() *RGATreeList

NewRGATreeList creates a new instance of RGATreeList.

func (*RGATreeList) Add 

func (a *RGATreeList) Add(elem Element) error

Add adds the given element at the last.

func (*RGATreeList) Delete 

func (a *RGATreeList) Delete(idx int, deletedAt *time.Ticket) (*RGATreeListNode, error)

Delete deletes the node of the given index.

func (*RGATreeList) DeleteByCreatedAt 

func (a *RGATreeList) DeleteByCreatedAt(createdAt *time.Ticket, deletedAt *time.Ticket) (*RGATreeListNode, error)

DeleteByCreatedAt deletes the given element.

func (*RGATreeList) FindPrevCreatedAt 

func (a *RGATreeList) FindPrevCreatedAt(createdAt *time.Ticket) (*time.Ticket, error)

FindPrevCreatedAt returns the creation time of the previous element of the given element.

func (*RGATreeList) Get 

func (a *RGATreeList) Get(idx int) (*RGATreeListNode, error)

Get returns the element of the given index.

func (*RGATreeList) InsertAfter 

func (a *RGATreeList) InsertAfter(prevCreatedAt *time.Ticket, elem Element) error

InsertAfter inserts the given element after the given previous element.

func (*RGATreeList) LastCreatedAt 

func (a *RGATreeList) LastCreatedAt() *time.Ticket

LastCreatedAt returns the creation time of last elements.

func (*RGATreeList) Len 

func (a *RGATreeList) Len() int

Len returns length of this RGATreeList.

func (*RGATreeList) Marshal 

func (a *RGATreeList) Marshal() string

Marshal returns the JSON encoding of this RGATreeList.

func (*RGATreeList) MoveAfter 

func (a *RGATreeList) MoveAfter(prevCreatedAt, createdAt, executedAt *time.Ticket) error

MoveAfter moves the given `createdAt` element after the `prevCreatedAt` element.

func (*RGATreeList) Nodes 

func (a *RGATreeList) Nodes() []*RGATreeListNode

Nodes returns an array of elements contained in this RGATreeList. TODO: If we encounter performance issues, we need to replace this with other solution.

func (*RGATreeList) Set added in v0.5.0 

func (a *RGATreeList) Set(
	createdAt *time.Ticket,
	element Element,
	executedAt *time.Ticket,
) (*RGATreeListNode, error)

Set sets the given element at the given creation time.

func (*RGATreeList) ToTestString added in v0.4.8 

func (a *RGATreeList) ToTestString() string

ToTestString returns a String containing the metadata of the node id for debugging purpose.

type RGATreeListNode 

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

RGATreeListNode is a node of RGATreeList.

func (*RGATreeListNode) CreatedAt 

func (n *RGATreeListNode) CreatedAt() *time.Ticket

CreatedAt returns the creation time of this element.

func (*RGATreeListNode) Element 

func (n *RGATreeListNode) Element() Element

Element returns the element of this node.

func (*RGATreeListNode) Len 

func (n *RGATreeListNode) Len() int

Len returns the length of this node.

func (*RGATreeListNode) PositionedAt 

func (n *RGATreeListNode) PositionedAt() *time.Ticket

PositionedAt returns the time this element was positioned.

func (*RGATreeListNode) String 

func (n *RGATreeListNode) String() string

String returns the string representation of this node.

type RGATreeSplit 

type RGATreeSplit[V RGATreeSplitValue] struct {
	// contains filtered or unexported fields
}

RGATreeSplit is a block-based list with improved index-based lookup in RGA. The difference from RGATreeList is that it has data on a block basis to reduce the size of CRDT metadata. When an Edit occurs on a block, the block is split.

func NewRGATreeSplit 

func NewRGATreeSplit[V RGATreeSplitValue](initialHead *RGATreeSplitNode[V]) *RGATreeSplit[V]

NewRGATreeSplit creates a new instance of RGATreeSplit.

func (*RGATreeSplit[V]) CheckWeight 

func (s *RGATreeSplit[V]) CheckWeight() bool

CheckWeight returns false when there is an incorrect weight node. for debugging purpose.

func (*RGATreeSplit[V]) FindNode 

func (s *RGATreeSplit[V]) FindNode(id *RGATreeSplitNodeID) *RGATreeSplitNode[V]

FindNode returns the node of the given ID.

func (*RGATreeSplit[V]) InitialHead 

func (s *RGATreeSplit[V]) InitialHead() *RGATreeSplitNode[V]

InitialHead returns the head node of this RGATreeSplit.

func (*RGATreeSplit[V]) InsertAfter 

func (s *RGATreeSplit[V]) InsertAfter(prev, node *RGATreeSplitNode[V]) *RGATreeSplitNode[V]

InsertAfter inserts the given node after the given previous node.

func (*RGATreeSplit[V]) Purge added in v0.4.20 

func (s *RGATreeSplit[V]) Purge(child GCChild) error

Purge physically purge the given node from RGATreeSplit.

func (*RGATreeSplit[V]) ToTestString added in v0.4.8 

func (s *RGATreeSplit[V]) ToTestString() string

ToTestString returns a String containing the metadata of the nodes for debugging purpose.

type RGATreeSplitNode 

type RGATreeSplitNode[V RGATreeSplitValue] struct {
	// contains filtered or unexported fields
}

RGATreeSplitNode is a node of RGATreeSplit.

func InitialTextNode 

func InitialTextNode() *RGATreeSplitNode[*TextValue]

InitialTextNode creates an initial node of Text. The text is edited as this node is split into multiple nodes.

func NewRGATreeSplitNode 

func NewRGATreeSplitNode[V RGATreeSplitValue](id *RGATreeSplitNodeID, value V) *RGATreeSplitNode[V]

NewRGATreeSplitNode creates a new instance of RGATreeSplit.

func (*RGATreeSplitNode[V]) DeepCopy 

func (s *RGATreeSplitNode[V]) DeepCopy() *RGATreeSplitNode[V]

DeepCopy returns a new instance of this RGATreeSplitNode without structural info.

func (*RGATreeSplitNode[V]) ID 

func (s *RGATreeSplitNode[V]) ID() *RGATreeSplitNodeID

ID returns the ID of this RGATreeSplitNode.

func (*RGATreeSplitNode[V]) IDString added in v0.4.20 

func (s *RGATreeSplitNode[V]) IDString() string

IDString returns the string representation of the ID.

func (*RGATreeSplitNode[V]) InsPrevID 

func (s *RGATreeSplitNode[V]) InsPrevID() *RGATreeSplitNodeID

InsPrevID returns previous node ID at the time of this node insertion.

func (*RGATreeSplitNode[V]) Len 

func (s *RGATreeSplitNode[V]) Len() int

Len returns the length of this node.

func (*RGATreeSplitNode[V]) Marshal 

func (s *RGATreeSplitNode[V]) Marshal() string

Marshal returns the JSON encoding of this node.

func (*RGATreeSplitNode[V]) Remove 

func (s *RGATreeSplitNode[V]) Remove(removedAt *time.Ticket, maxCreatedAt *time.Ticket) bool

Remove removes this node if it created before the time of deletion are deleted. It only marks the deleted time (tombstone).

func (*RGATreeSplitNode[V]) RemovedAt 

func (s *RGATreeSplitNode[V]) RemovedAt() *time.Ticket

RemovedAt return the remove time of this node.

func (*RGATreeSplitNode[V]) SetInsPrev 

func (s *RGATreeSplitNode[V]) SetInsPrev(node *RGATreeSplitNode[V])

SetInsPrev sets previous node of this node insertion.

func (*RGATreeSplitNode[V]) String 

func (s *RGATreeSplitNode[V]) String() string

String returns the string representation of this node.

func (*RGATreeSplitNode[V]) Value 

func (s *RGATreeSplitNode[V]) Value() V

Value returns the value of this node.

type RGATreeSplitNodeID 

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

RGATreeSplitNodeID is an ID of RGATreeSplitNode.

func NewRGATreeSplitNodeID 

func NewRGATreeSplitNodeID(createdAt *time.Ticket, offset int) *RGATreeSplitNodeID

NewRGATreeSplitNodeID creates a new instance of RGATreeSplitNodeID.

func (*RGATreeSplitNodeID) Compare 

func (id *RGATreeSplitNodeID) Compare(other llrb.Key) int

Compare returns an integer comparing two ID. The result will be 0 if id==other, -1 if id < other, and +1 if id > other. If the receiver or argument is nil, it would panic at runtime. This method is following golang standard interface.

func (*RGATreeSplitNodeID) CreatedAt 

func (id *RGATreeSplitNodeID) CreatedAt() *time.Ticket

CreatedAt returns the creation time of this ID.

func (*RGATreeSplitNodeID) Equal 

func (id *RGATreeSplitNodeID) Equal(other llrb.Key) bool

Equal returns whether given ID equals to this ID or not.

func (*RGATreeSplitNodeID) Offset 

func (id *RGATreeSplitNodeID) Offset() int

Offset returns the offset of this ID.

func (*RGATreeSplitNodeID) Split 

func (id *RGATreeSplitNodeID) Split(offset int) *RGATreeSplitNodeID

Split creates a new ID with an offset from this ID.

func (*RGATreeSplitNodeID) ToTestString added in v0.4.8 

func (id *RGATreeSplitNodeID) ToTestString() string

ToTestString returns a String containing the metadata of the node id for debugging purpose.

type RGATreeSplitNodePos 

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

RGATreeSplitNodePos is the position of the text inside the node.

func NewRGATreeSplitNodePos 

func NewRGATreeSplitNodePos(id *RGATreeSplitNodeID, offset int) *RGATreeSplitNodePos

NewRGATreeSplitNodePos creates a new instance of RGATreeSplitNodePos.

func (*RGATreeSplitNodePos) Equal 

func (pos *RGATreeSplitNodePos) Equal(other *RGATreeSplitNodePos) bool

Equal returns whether the given pos equals or not.

func (*RGATreeSplitNodePos) ID 

func (pos *RGATreeSplitNodePos) ID() *RGATreeSplitNodeID

ID returns the ID of this RGATreeSplitNodePos.

func (*RGATreeSplitNodePos) RelativeOffset 

func (pos *RGATreeSplitNodePos) RelativeOffset() int

RelativeOffset returns the relative offset of this RGATreeSplitNodePos.

func (*RGATreeSplitNodePos) ToTestString added in v0.4.8 

func (pos *RGATreeSplitNodePos) ToTestString() string

ToTestString returns a String containing the metadata of the position for debugging purpose.

type RGATreeSplitValue 

type RGATreeSplitValue interface {
	Split(offset int) RGATreeSplitValue
	Len() int
	DeepCopy() RGATreeSplitValue
	String() string
	Marshal() string
	// contains filtered or unexported methods
}

RGATreeSplitValue is a value of RGATreeSplitNode.

type RHT 

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

RHT is a hashtable with logical clock(Replicated hashtable). For more details about RHT: http://csl.skku.edu/papers/jpdc11.pdf NOTE(justiceHui): RHT and ElementRHT has duplicated functions.

func NewRHT 

func NewRHT() *RHT

NewRHT creates a new instance of RHT.

func (*RHT) DeepCopy 

func (rht *RHT) DeepCopy() *RHT

DeepCopy copies itself deeply.

func (*RHT) Elements 

func (rht *RHT) Elements() map[string]string

Elements returns a map of elements because the map easy to use for loop. TODO: If we encounter performance issues, we need to replace this with other solution.

func (*RHT) Get 

func (rht *RHT) Get(key string) string

Get returns the value of the given key.

func (*RHT) Has 

func (rht *RHT) Has(key string) bool

Has returns whether the element exists of the given key or not.

func (*RHT) Len added in v0.4.2 

func (rht *RHT) Len() int

Len returns the number of elements.

func (*RHT) Marshal 

func (rht *RHT) Marshal() string

Marshal returns the JSON encoding of this hashtable.

func (*RHT) Nodes 

func (rht *RHT) Nodes() []*RHTNode

Nodes returns a map of elements because the map easy to use for loop. TODO: If we encounter performance issues, we need to replace this with other solution.

func (*RHT) Purge added in v0.4.20 

func (rht *RHT) Purge(child *RHTNode) error

Purge purges the given child node.

func (*RHT) Remove 

func (rht *RHT) Remove(k string, executedAt *time.Ticket) []*RHTNode

Remove removes the value of the given key.

func (*RHT) Set 

func (rht *RHT) Set(k, v string, executedAt *time.Ticket) *RHTNode

Set sets the value of the given key.

func (*RHT) SetInternal added in v0.4.22 

func (rht *RHT) SetInternal(k string, v string, updatedAt *time.Ticket, removed bool)

SetInternal sets the value of the given key internally.

type RHTNode 

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

RHTNode is a node of RHT(Replicated Hashtable).

func (*RHTNode) IDString added in v0.4.20 

func (n *RHTNode) IDString() string

IDString returns the string representation of this node.

func (*RHTNode) IsRemoved added in v0.4.22 

func (n *RHTNode) IsRemoved() bool

IsRemoved returns whether this node is removed or not.

func (*RHTNode) Key 

func (n *RHTNode) Key() string

Key returns the key of this node.

func (*RHTNode) RemovedAt 

func (n *RHTNode) RemovedAt() *time.Ticket

RemovedAt returns the time when this node was removed.

func (*RHTNode) UpdatedAt 

func (n *RHTNode) UpdatedAt() *time.Ticket

UpdatedAt returns the last update time.

func (*RHTNode) Value 

func (n *RHTNode) Value() string

Value returns the value of this node.

type Root 

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

Root is a structure represents the root of JSON. It has a hash table of all JSON elements to find a specific element when applying remote changes received from server.

Every element has a unique time ticket at creation, which allows us to find a particular element.

func NewRoot 

func NewRoot(root *Object) *Root

NewRoot creates a new instance of Root.

func (*Root) DeepCopy 

func (r *Root) DeepCopy() (*Root, error)

DeepCopy copies itself deeply.

func (*Root) ElementMapLen 

func (r *Root) ElementMapLen() int

ElementMapLen returns the size of element map.

func (*Root) FindByCreatedAt 

func (r *Root) FindByCreatedAt(createdAt *time.Ticket) Element

FindByCreatedAt returns the element of given creation time.

func (*Root) GarbageCollect 

func (r *Root) GarbageCollect(ticket *time.Ticket) (int, error)

GarbageCollect purge elements that were removed before the given time.

func (*Root) GarbageElementLen added in v0.4.20 

func (r *Root) GarbageElementLen() int

GarbageElementLen return the count of removed elements.

func (*Root) GarbageLen 

func (r *Root) GarbageLen() int

GarbageLen returns the count of removed elements and internal nodes.

func (*Root) Object 

func (r *Root) Object() *Object

Object returns the root object of the JSON.

func (*Root) RegisterElement 

func (r *Root) RegisterElement(element Element)

RegisterElement registers the given element to hash table.

func (*Root) RegisterGCPair added in v0.4.20 

func (r *Root) RegisterGCPair(pair GCPair)

RegisterGCPair registers the given pair to hash table.

func (*Root) RegisterRemovedElementPair 

func (r *Root) RegisterRemovedElementPair(parent Container, elem Element)

RegisterRemovedElementPair register the given element pair to hash table.

type Text 

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

Text is an extended data type for the contents of a text editor.

func NewText 

func NewText(elements *RGATreeSplit[*TextValue], createdAt *time.Ticket) *Text

NewText creates a new instance of Text.

func (*Text) CheckWeight 

func (t *Text) CheckWeight() bool

CheckWeight returns false when there is an incorrect weight node. for debugging purpose.

func (*Text) CreateRange 

func (t *Text) CreateRange(from, to int) (*RGATreeSplitNodePos, *RGATreeSplitNodePos, error)

CreateRange returns a pair of RGATreeSplitNodePos of the given integer offsets.

func (*Text) CreatedAt 

func (t *Text) CreatedAt() *time.Ticket

CreatedAt returns the creation time of this Text.

func (*Text) DeepCopy 

func (t *Text) DeepCopy() (Element, error)

DeepCopy copies itself deeply.

func (*Text) Edit 

func (t *Text) Edit(
	from,
	to *RGATreeSplitNodePos,
	maxCreatedAtMapByActor map[string]*time.Ticket,
	content string,
	attributes map[string]string,
	executedAt *time.Ticket,
) (*RGATreeSplitNodePos, map[string]*time.Ticket, []GCPair, error)

Edit edits the given range with the given content and attributes.

func (*Text) GCPairs added in v0.4.20 

func (t *Text) GCPairs() []GCPair

GCPairs returns the pairs of GC.

func (*Text) Marshal 

func (t *Text) Marshal() string

Marshal returns the JSON encoding of this Text.

func (*Text) MovedAt 

func (t *Text) MovedAt() *time.Ticket

MovedAt returns the move time of this Text.

func (*Text) Nodes 

func (t *Text) Nodes() []*RGATreeSplitNode[*TextValue]

Nodes returns the internal nodes of this Text.

func (*Text) Remove 

func (t *Text) Remove(removedAt *time.Ticket) bool

Remove removes this Text.

func (*Text) RemovedAt 

func (t *Text) RemovedAt() *time.Ticket

RemovedAt returns the removal time of this Text.

func (*Text) SetMovedAt 

func (t *Text) SetMovedAt(movedAt *time.Ticket)

SetMovedAt sets the move time of this Text.

func (*Text) SetRemovedAt 

func (t *Text) SetRemovedAt(removedAt *time.Ticket)

SetRemovedAt sets the removal time of this array.

func (*Text) String 

func (t *Text) String() string

String returns the string representation of this Text.

func (*Text) Style added in v0.3.0 

func (t *Text) Style(
	from,
	to *RGATreeSplitNodePos,
	maxCreatedAtMapByActor map[string]*time.Ticket,
	attributes map[string]string,
	executedAt *time.Ticket,
) (map[string]*time.Ticket, []GCPair, error)

Style applies the given attributes of the given range.

func (*Text) ToTestString added in v0.4.8 

func (t *Text) ToTestString() string

ToTestString returns a String containing the metadata of the text for debugging purpose.

func (*Text) TreeByID added in v0.4.26 

func (t *Text) TreeByID() *llrb.Tree[*RGATreeSplitNodeID, *RGATreeSplitNode[*TextValue]]

TreeByID returns the tree by ID for debugging purpose.

func (*Text) TreeByIndex added in v0.4.26 

func (t *Text) TreeByIndex() *splay.Tree[*RGATreeSplitNode[*TextValue]]

TreeByIndex returns IndexTree of the text for debugging purpose.

type TextValue 

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

TextValue is a value of Text which has an attributes that represent the text style.

func NewTextValue 

func NewTextValue(value string, attrs *RHT) *TextValue

NewTextValue creates a value of Text.

func (*TextValue) Attrs added in v0.3.0 

func (t *TextValue) Attrs() *RHT

Attrs returns the attributes of this value.

func (*TextValue) DeepCopy 

func (t *TextValue) DeepCopy() RGATreeSplitValue

DeepCopy copies itself deeply.

func (*TextValue) GCPairs added in v0.4.20 

func (t *TextValue) GCPairs() []GCPair

GCPairs returns the pairs of GC.

func (*TextValue) Len 

func (t *TextValue) Len() int

Len returns the length of this value. It is calculated in UTF-16 code units.

func (*TextValue) Marshal 

func (t *TextValue) Marshal() string

Marshal returns the JSON encoding of this text.

func (*TextValue) Purge added in v0.4.20 

func (t *TextValue) Purge(child GCChild) error

Purge removes the given ticket from this value.

func (*TextValue) Split 

func (t *TextValue) Split(offset int) RGATreeSplitValue

Split splits this value by the given offset.

func (*TextValue) String 

func (t *TextValue) String() string

String returns the string representation of this value.

func (*TextValue) Value added in v0.3.0 

func (t *TextValue) Value() string

Value returns the value of this text value.

type Tree added in v0.4.0 

type Tree struct {
	IndexTree   *index.Tree[*TreeNode]
	NodeMapByID *llrb.Tree[*TreeNodeID, *TreeNode]
	// contains filtered or unexported fields
}

Tree represents the tree of CRDT. It has doubly linked list structure and index tree structure.

func NewTree added in v0.4.0 

func NewTree(root *TreeNode, createdAt *time.Ticket) *Tree

NewTree creates a new instance of Tree.

func (*Tree) CreatedAt added in v0.4.0 

func (t *Tree) CreatedAt() *time.Ticket

CreatedAt returns the creation time of this Tree.

func (*Tree) DeepCopy added in v0.4.0 

func (t *Tree) DeepCopy() (Element, error)

DeepCopy copies itself deeply.

func (*Tree) Edit added in v0.4.0 

func (t *Tree) Edit(
	from, to *TreePos,
	contents []*TreeNode,
	splitLevel int,
	editedAt *time.Ticket,
	issueTimeTicket func() *time.Ticket,
	maxCreatedAtMapByActor map[string]*time.Ticket,
) (map[string]*time.Ticket, []GCPair, error)

Edit edits the tree with the given range and content. If the content is undefined, the range will be removed.

func (*Tree) EditT added in v0.4.10 

func (t *Tree) EditT(
	start, end int,
	contents []*TreeNode,
	splitLevel int,
	editedAt *time.Ticket,
	issueTimeTicket func() *time.Ticket,
) error

EditT edits the given range with the given value. This method uses indexes instead of a pair of TreePos for testing.

func (*Tree) FindPos added in v0.4.0 

func (t *Tree) FindPos(offset int) (*TreePos, error)

FindPos finds the position of the given index in the tree. (local) index -> (local) TreePos in indexTree -> (logical) TreePos in Tree

func (*Tree) FindTreeNodesWithSplitText added in v0.4.6 

func (t *Tree) FindTreeNodesWithSplitText(pos *TreePos, editedAt *time.Ticket) (
	*TreeNode, *TreeNode, error,
)

FindTreeNodesWithSplitText finds TreeNode of the given crdt.TreePos and splits the text node if the position is in the middle of the text node. crdt.TreePos is a position in the CRDT perspective. This is different from indexTree.TreePos which is a position of the tree in physical perspective.

func (*Tree) GCPairs added in v0.4.20 

func (t *Tree) GCPairs() []GCPair

GCPairs returns the pairs of GC.

func (*Tree) Marshal added in v0.4.0 

func (t *Tree) Marshal() string

Marshal returns the JSON encoding of this Tree.

func (*Tree) MovedAt added in v0.4.0 

func (t *Tree) MovedAt() *time.Ticket

MovedAt returns the move time of this Tree.

func (*Tree) NodeLen added in v0.4.21 

func (t *Tree) NodeLen() int

NodeLen returns the size of the LLRBTree.

func (*Tree) Nodes added in v0.4.0 

func (t *Tree) Nodes() []*TreeNode

Nodes traverses the tree and returns the list of nodes.

func (*Tree) PathToPos added in v0.4.0 

func (t *Tree) PathToPos(path []int) (*TreePos, error)

PathToPos returns the position of the given path

func (*Tree) Purge added in v0.4.3 

func (t *Tree) Purge(child GCChild) error

Purge physically purges the given node.

func (*Tree) Remove added in v0.4.0 

func (t *Tree) Remove(removedAt *time.Ticket) bool

Remove removes this Text.

func (*Tree) RemoveStyle added in v0.4.13 

func (t *Tree) RemoveStyle(
	from *TreePos,
	to *TreePos,
	attrs []string,
	editedAt *time.Ticket,
	maxCreatedAtMapByActor map[string]*time.Ticket,
) (map[string]*time.Ticket, []GCPair, error)

RemoveStyle removes the given attributes of the given range.

func (*Tree) RemovedAt added in v0.4.0 

func (t *Tree) RemovedAt() *time.Ticket

RemovedAt returns the removal time of this Tree.

func (*Tree) Root added in v0.4.0 

func (t *Tree) Root() *TreeNode

Root returns the root node of the tree.

func (*Tree) SetMovedAt added in v0.4.0 

func (t *Tree) SetMovedAt(movedAt *time.Ticket)

SetMovedAt sets the move time of this Text.

func (*Tree) SetRemovedAt added in v0.4.0 

func (t *Tree) SetRemovedAt(removedAt *time.Ticket)

SetRemovedAt sets the removal time of this array.

func (*Tree) Style added in v0.4.2 

func (t *Tree) Style(
	from, to *TreePos,
	attrs map[string]string,
	editedAt *time.Ticket,
	maxCreatedAtMapByActor map[string]*time.Ticket,
) (map[string]*time.Ticket, []GCPair, error)

Style applies the given attributes of the given range.

func (*Tree) StyleByIndex added in v0.4.2 

func (t *Tree) StyleByIndex(
	start, end int,
	attributes map[string]string,
	editedAt *time.Ticket,
	maxCreatedAtMapByActor map[string]*time.Ticket,
) (map[string]*time.Ticket, []GCPair, error)

StyleByIndex applies the given attributes of the given range. This method uses indexes instead of a pair of TreePos for testing.

func (*Tree) ToIndex added in v0.4.6 

func (t *Tree) ToIndex(parentNode, leftSiblingNode *TreeNode) (int, error)

ToIndex converts the given CRDTTreePos to the index of the tree.

func (*Tree) ToPath added in v0.4.16 

func (t *Tree) ToPath(parentNode, leftSiblingNode *TreeNode) ([]int, error)

ToPath returns path from given CRDTTreePos

func (*Tree) ToTreeNodeForTest added in v0.4.8 

func (t *Tree) ToTreeNodeForTest() TreeNodeForTest

ToTreeNodeForTest returns the JSON of this tree for debugging.

func (*Tree) ToTreeNodes added in v0.4.16 

func (t *Tree) ToTreeNodes(pos *TreePos) (*TreeNode, *TreeNode)

ToTreeNodes converts the pos to parent and left sibling nodes. If the position points to the middle of a node, then the left sibling node is the node that contains the position. Otherwise, the left sibling node is the node that is the left of the position.

func (*Tree) ToXML added in v0.4.0 

func (t *Tree) ToXML() string

ToXML returns the XML encoding of this tree.

type TreeNode added in v0.4.0 

type TreeNode struct {
	Index *index.Node[*TreeNode]

	InsPrevID *TreeNodeID
	InsNextID *TreeNodeID

	// Value is optional. If the value is not empty, it means that the node is a
	// text node.
	Value string

	// Attrs is optional. If the value is not empty,
	//it means that the node is an element node.
	Attrs *RHT
	// contains filtered or unexported fields
}

TreeNode is a node of Tree.

func NewTreeNode added in v0.4.0 

func NewTreeNode(id *TreeNodeID, nodeType string, attributes *RHT, value ...string) *TreeNode

NewTreeNode creates a new instance of TreeNode.

func (*TreeNode) Append added in v0.4.0 

func (n *TreeNode) Append(newNodes ...*TreeNode) error

Append appends the given node to the end of the children.

func (*TreeNode) Attributes added in v0.4.2 

func (n *TreeNode) Attributes() string

Attributes returns the string representation of this node's attributes.

func (*TreeNode) Child added in v0.4.0 

func (n *TreeNode) Child(offset int) (*TreeNode, error)

Child returns the child of the given offset.

func (*TreeNode) DeepCopy added in v0.4.0 

func (n *TreeNode) DeepCopy() (*TreeNode, error)

DeepCopy copies itself deeply.

func (*TreeNode) GCPairs added in v0.4.20 

func (n *TreeNode) GCPairs() []GCPair

GCPairs returns the pairs of GC.

func (*TreeNode) ID added in v0.4.6 

func (n *TreeNode) ID() *TreeNodeID

ID returns the ID of this Node.

func (*TreeNode) IDString added in v0.4.20 

func (n *TreeNode) IDString() string

IDString returns the IDString of this Node.

func (*TreeNode) InsertAfter added in v0.4.10 

func (n *TreeNode) InsertAfter(content *TreeNode, children *TreeNode) error

InsertAfter inserts the given node after the given leftSibling.

func (*TreeNode) InsertAt added in v0.4.0 

func (n *TreeNode) InsertAt(newNode *TreeNode, offset int) error

InsertAt inserts the given node at the given offset.

func (*TreeNode) IsRemoved added in v0.4.0 

func (n *TreeNode) IsRemoved() bool

IsRemoved returns whether the Node is removed or not.

func (*TreeNode) IsText added in v0.4.0 

func (n *TreeNode) IsText() bool

IsText returns whether the Node is text or not.

func (*TreeNode) Len added in v0.4.0 

func (n *TreeNode) Len() int

Len returns the length of the Node.

func (*TreeNode) Length added in v0.4.0 

func (n *TreeNode) Length() int

Length returns the length of this node.

func (*TreeNode) Prepend added in v0.4.0 

func (n *TreeNode) Prepend(newNodes ...*TreeNode) error

Prepend prepends the given node to the beginning of the children.

func (*TreeNode) Purge added in v0.4.20 

func (n *TreeNode) Purge(child GCChild) error

Purge removes the given child from the children.

func (*TreeNode) RemoveAttr added in v0.4.20 

func (n *TreeNode) RemoveAttr(k string, ticket *time.Ticket) []*RHTNode

RemoveAttr removes the given attribute of the element.

func (*TreeNode) RemovedAt added in v0.4.0 

func (n *TreeNode) RemovedAt() *time.Ticket

RemovedAt returns the removal time of this Node.

func (*TreeNode) SetAttr added in v0.4.20 

func (n *TreeNode) SetAttr(k string, v string, ticket *time.Ticket) *RHTNode

SetAttr sets the given attribute of the element.

func (*TreeNode) SetRemovedAt added in v0.4.20 

func (n *TreeNode) SetRemovedAt(ticket *time.Ticket)

SetRemovedAt sets the removal time of this node.

func (*TreeNode) Split added in v0.4.0 

func (n *TreeNode) Split(tree *Tree, offset int, issueTimeTicket func() *time.Ticket) error

Split splits the node at the given offset.

func (*TreeNode) SplitElement added in v0.4.6 

func (n *TreeNode) SplitElement(offset int, issueTimeTicket func() *time.Ticket) (*TreeNode, error)

SplitElement splits the given element at the given offset.

func (*TreeNode) SplitText added in v0.4.0 

func (n *TreeNode) SplitText(offset, absOffset int) (*TreeNode, error)

SplitText splits the text node at the given offset.

func (*TreeNode) String added in v0.4.0 

func (n *TreeNode) String() string

String returns the string representation of this node's value.

func (*TreeNode) Type added in v0.4.0 

func (n *TreeNode) Type() string

Type returns the type of the Node.

type TreeNodeForTest added in v0.4.0 

type TreeNodeForTest struct {
	Type      string
	Children  []TreeNodeForTest
	Value     string
	Size      int
	IsRemoved bool
}

TreeNodeForTest is a TreeNode for test.

func ToTreeNodeForTest added in v0.4.8 

func ToTreeNodeForTest(node *TreeNode) TreeNodeForTest

ToTreeNodeForTest returns the JSON of this tree for debugging.

type TreeNodeID added in v0.4.6 

type TreeNodeID struct {
	CreatedAt *time.Ticket
	Offset    int
}

TreeNodeID represent an ID of a node in the tree. It is used to identify a node in the tree. It is composed of the creation time of the node and the offset from the beginning of the node if the node is split.

Some replicas may have nodes that are not split yet. In this case, we can use `map.floorEntry()` to find the adjacent node.

func NewTreeNodeID added in v0.4.6 

func NewTreeNodeID(createdAt *time.Ticket, offset int) *TreeNodeID

NewTreeNodeID creates a new instance of TreeNodeID.

func (*TreeNodeID) Compare added in v0.4.6 

func (t *TreeNodeID) Compare(other llrb.Key) int

Compare compares the given two CRDTTreePos.

func (*TreeNodeID) Equals added in v0.4.10 

func (t *TreeNodeID) Equals(id *TreeNodeID) bool

Equals returns whether given ID is equal to this ID or not.

type TreePos added in v0.4.0 

type TreePos struct {
	// ParentID is the ID of the parent node.
	ParentID *TreeNodeID

	// LeftSiblingID is the ID of the left sibling node. If the node is the
	// parent, it means that the position is leftmost.
	LeftSiblingID *TreeNodeID
}

TreePos represents a position in the tree. It is used to determine the position of insertion, deletion, and style change.

func NewTreePos added in v0.4.0 

func NewTreePos(parentID *TreeNodeID, leftSiblingID *TreeNodeID) *TreePos

NewTreePos creates a new instance of TreePos.

func (*TreePos) Equals added in v0.4.6 

func (t *TreePos) Equals(other *TreePos) bool

Equals compares the given two CRDTTreePos.

type ValueType 

type ValueType int

ValueType represents the type of Primitive value. 

const (
	Null ValueType = iota
	Boolean
	Integer
	Long
	Double
	String
	Bytes
	Date
)

Primitive can have the following types:

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.