crdt

package
v0.4.0 Latest Latest
Warning

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

 Go to latest Published: Jun 5, 2023 License: Apache-2.0 Imports: 14 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

View Source 
const (
	// DummyHeadType is a type of dummy head. It is used to represent the head node of RGASplit.
	DummyHeadType = "dummy"
)

Variables

View Source 
var (
	// DummyTreePos is a dummy position of Tree. It is used to represent the head node of RGASplit.
	DummyTreePos = &TreePos{
		CreatedAt: time.InitialTicket,
		Offset:    0,
	}
)

Functions

func CounterValueFromBytes 

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

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{}

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) *Array

NewArray creates a new instance of Array.

func (*Array) Add 

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

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

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

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)

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)

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)

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) 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) StructureAsString added in v0.2.19 

func (a *Array) StructureAsString() string

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

	// 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
}

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

NewCounter creates a new instance of Counter.

func (*Counter) Bytes 

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

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

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

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

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)

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

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)

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

DeleteByCreatedAt deletes the given element.

func (*RGATreeList) FindPrevCreatedAt 

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

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)

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)

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) StructureAsString added in v0.2.19 

func (a *RGATreeList) StructureAsString() string

StructureAsString 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]) StructureAsString added in v0.2.19 

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

StructureAsString 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]) 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, latestCreatedAt *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) StructureAsString added in v0.2.19 

func (id *RGATreeSplitNodeID) StructureAsString() string

StructureAsString 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 the 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) StructureAsString added in v0.2.19 

func (pos *RGATreeSplitNodePos) StructureAsString() string

StructureAsString 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

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

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

Remove removes the Element of the given key.

func (*RHT) Set 

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

Set sets the value of the given key.

type RHTNode 

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

RHTNode is a node of RHT(Replicated Hashtable).

func (*RHTNode) Key 

func (n *RHTNode) Key() string

Key returns the key of this node.

func (*RHTNode) Remove 

func (n *RHTNode) Remove(removedAt *time.Ticket)

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

func (*RHTNode) RemovedAt 

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

RemovedAt returns the deletion time of this node.

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

func (r *Root) DeregisterElement(elem Element)

DeregisterElement deregister the given element from hash tables.

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

GarbageCollect purge elements that were removed before the given time.

func (*Root) GarbageLen 

func (r *Root) GarbageLen() int

GarbageLen returns the count of removed elements.

func (*Root) Object 

func (r *Root) Object() *Object

Object returns the root object of the JSON.

func (*Root) RegisterElement 

func (r *Root) RegisterElement(elem Element)

RegisterElement registers the given element to hash table.

func (*Root) RegisterRemovedElementPair 

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

RegisterRemovedElementPair register the given element pair to hash table.

func (*Root) RegisterTextElementWithGarbage 

func (r *Root) RegisterTextElementWithGarbage(textType TextElement)

RegisterTextElementWithGarbage register the given text element with garbage to hash table.

func (*Root) RemovedElementLen 

func (r *Root) RemovedElementLen() int

RemovedElementLen returns the size of removed element map.

type Selection 

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

Selection represents the selection of text range in the editor.

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,
	latestCreatedAtMapByActor map[string]*time.Ticket,
	content string,
	attributes map[string]string,
	executedAt *time.Ticket,
) (*RGATreeSplitNodePos, map[string]*time.Ticket, error)

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

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

func (t *Text) Select(
	from *RGATreeSplitNodePos,
	to *RGATreeSplitNodePos,
	executedAt *time.Ticket,
)

Select stores that the given range has been selected.

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) StructureAsString added in v0.2.19 

func (t *Text) StructureAsString() string

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

func (*Text) Style added in v0.3.0 

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

Style applies the given attributes of the given range.

type TextElement 

type TextElement interface {
	Element
	// contains filtered or unexported methods
}

TextElement represents Text.

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) 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) 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 {
	DummyHead    *TreeNode
	IndexTree    *index.Tree[*TreeNode]
	NodeMapByPos *llrb.Tree[*TreePos, *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, content *TreeNode, editedAt *time.Ticket)

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

func (*Tree) EditByIndex added in v0.4.0 

func (t *Tree) EditByIndex(start, end int, content *TreeNode, editedAt *time.Ticket)

EditByIndex 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

FindPos finds the position of the given index in the tree.

func (*Tree) InsertAfter added in v0.4.0 

func (t *Tree) InsertAfter(prevNode *TreeNode, newNode *TreeNode)

InsertAfter inserts the given node after the given previous node.

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

PathToPos returns the position of the given path

func (*Tree) Remove added in v0.4.0 

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

Remove removes this Text.

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) Structure added in v0.4.0 

func (t *Tree) Structure() TreeNodeForTest

Structure returns the structure of this tree.

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 {
	IndexTreeNode *index.Node[*TreeNode]

	Pos       *TreePos
	RemovedAt *time.Ticket

	Next    *TreeNode
	Prev    *TreeNode
	InsPrev *TreeNode

	Value string
}

TreeNode is a node of Tree.

func NewTreeNode added in v0.4.0 

func NewTreeNode(pos *TreePos, nodeType string, value ...string) *TreeNode

NewTreeNode creates a new instance of TreeNode.

func (*TreeNode) Append added in v0.4.0 

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

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

func (*TreeNode) Child added in v0.4.0 

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

Child returns the child of the given offset.

func (*TreeNode) DeepCopy added in v0.4.0 

func (n *TreeNode) DeepCopy() *TreeNode

DeepCopy copies itself deeply.

func (*TreeNode) InsertAt added in v0.4.0 

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

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)

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

func (*TreeNode) Split added in v0.4.0 

func (n *TreeNode) Split(offset int) *TreeNode

Split splits the node at the given offset.

func (*TreeNode) SplitText added in v0.4.0 

func (n *TreeNode) SplitText(offset int) *TreeNode

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.

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 ToStructure added in v0.4.0 

func ToStructure(node *TreeNode) TreeNodeForTest

ToStructure returns the JSON of this tree for debugging.

type TreePos added in v0.4.0 

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

TreePos represents the position of Tree.

func NewTreePos added in v0.4.0 

func NewTreePos(createdAt *time.Ticket, offset int) *TreePos

NewTreePos creates a new instance of TreePos.

func (*TreePos) Compare added in v0.4.0 

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

Compare 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.