graph

package
v3.5.0 Latest Latest
Warning

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

Go to latest
Published: Feb 6, 2023 License: Apache-2.0 Imports: 11 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type Flag

type Flag interface {
	// GetIndex should return unique index among all defined flags, starting
	// from 0.
	GetIndex() int

	// GetName should return name of the flag.
	GetName() string

	// GetValue return the associated value. Can be empty.
	GetValue() string
}

Flag is a (index+name):value pair.

type FlagSelector

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

FlagSelector is used to select node with(out) given flags assigned.

Flag value=="" => any value

func WithFlags

func WithFlags(flags ...Flag) FlagSelector

WithFlags creates flag selector selecting nodes that have all the listed flags assigned.

func WithoutFlags

func WithoutFlags(flags ...Flag) FlagSelector

WithoutFlags creates flag selector selecting nodes that do not have any of the listed flags assigned.

type FlagStats

type FlagStats struct {
	TotalCount    uint            // number of revisions with the given flag assigned
	PerValueCount map[string]uint // number of revisions with the given flag having the given value
}

FlagStats is a summary of the usage for a given flag.

type Graph

type Graph interface {
	// Read returns a graph handle for read-only access.
	// The graph supports multiple concurrent readers.
	// Release eventually using Release() method.
	Read() ReadAccess // acquires R-lock

	// Write returns a graph handle for read-write access.
	// The graph supports at most one writer at a time - i.e. it is assumed
	// there is no write-concurrency.
	// If <inPlace> is enabled, the changes are applied with immediate effect,
	// otherwise they are propagated to the graph using Save().
	// In-place Write handle holds write lock, therefore reading is blocked until
	// the handle is released.
	// If <record> is true, the changes will be recorded once the handle is
	// released.
	// Release eventually using Release() method.
	Write(inPlace, record bool) RWAccess
}

Graph is an in-memory graph representation of key-value pairs and their relations, where nodes are kv-pairs and each relation is a separate set of direct labeled edges.

The graph furthermore allows to associate metadata and flags (idx/name:value pairs) with every node. It is possible to register instances of NamedMapping, each for a different set of selected nodes, and the graph will keep them up-to-date with the latest value-label->metadata associations.

The graph provides various getter method, for example it is possible to select a set of nodes using a key selector and/or a flag selector. As for editing, Graph allows to either write in-place (immediate effect) or to prepare new changes and then save them later or let them get discarded by GC.

The graph supports multiple-readers single-writer access, i.e. it is assumed there is no write-concurrency.

Last but not least, the graph maintains a history of revisions for all nodes that have ever existed. The history of changes and a graph snapshot from a selected moment in time are exposed via ReadAccess interface.

func NewGraph

func NewGraph(opts Opts) Graph

NewGraph creates and new instance of key-value graph. <recordOldRevs> if enabled, will cause the graph to record the previous revisions of every node that have ever existed. <recordAgeLimit> is in minutes and allows to limit the maximum age of a record to keep, avoiding infinite memory usage growth. The initial phase of the execution is, however, of greater significance and <permanentInitPeriod> allows to keep records from that period permanently in memory.

type MethodTracker

type MethodTracker func(method string) (onReturn func())

MethodTracker can be optionally supplied to track beginning and end of calls for (non-trivial) graph methods.

type Node

type Node interface {
	// GetKey returns the key associated with the node.
	GetKey() string

	// GetLabel returns the label associated with this node.
	GetLabel() string

	// GetValue returns the value associated with the node.
	GetValue() proto.Message

	// GetFlag returns reference to the given flag or nil if the node doesn't have
	// this flag associated.
	GetFlag(flagIndex int) Flag

	// GetMetadata returns the value metadata associated with the node.
	GetMetadata() interface{}

	// GetTargets returns a set of nodes, indexed by relation labels, that the
	// edges of the given relation points to.
	GetTargets(relation string) RuntimeTargets

	// IterTargets allows to iterate over the set of nodes that the edges of the given
	// relation points to.
	IterTargets(relation string, callback TargetIterator)

	// GetSources returns edges pointing to this node in the reverse
	// orientation.
	GetSources(relation string) RuntimeTargets
}

Node is a read-only handle to a single graph node.

type NodeRW

type NodeRW interface {
	Node

	// SetLabel associates given label with this node.
	SetLabel(label string)

	// SetValue associates given value with this node.
	SetValue(value proto.Message)

	// SetFlags associates given flag with this node.
	SetFlags(flags ...Flag)

	// DelFlags removes given flags from this node.
	DelFlags(flagIndexes ...int)

	// SetMetadataMap chooses metadata map to be used to store the association
	// between this node's value label and metadata.
	SetMetadataMap(mapName string)

	// SetMetadata associates given value metadata with this node.
	SetMetadata(metadata interface{})

	// SetTargets updates definitions of all edges pointing from this node.
	SetTargets(targets []RelationTargetDef)
}

NodeRW is a read-write handle to a single graph node.

type Opts

type Opts struct {
	RecordOldRevs       bool
	RecordAgeLimit      uint32
	PermanentInitPeriod uint32

	MethodTracker MethodTracker
}

Opts groups input options for the graph constructor.

type RWAccess

type RWAccess interface {
	ReadAccess

	// RegisterMetadataMap registers new metadata map for value-label->metadata
	// associations of selected node.
	RegisterMetadataMap(mapName string, mapping idxmap.NamedMappingRW)

	// SetNode creates new node or returns read-write handle to an existing node.
	// If in-place writing is disabled, the changes are propagated to the graph
	// only after Save() is called.
	SetNode(key string) NodeRW

	// DeleteNode deletes node with the given key.
	// Returns true if the node really existed before the operation.
	DeleteNode(key string) bool

	// Save propagates all changes to the graph.
	// Use for **not-in-place** writing.
	// NOOP if no changes performed, acquires RW-lock for the time of the operation
	Save()
}

RWAccess lists operations provided by the read-write graph handle.

type ReadAccess

type ReadAccess interface {
	// GetMetadataMap returns registered metadata map.
	GetMetadataMap(mapName string) idxmap.NamedMapping

	// GetKeys returns sorted keys.
	GetKeys() []string

	// GetNode returns node with the given key or nil if the key is unused.
	GetNode(key string) Node

	// GetNodes returns a set of nodes matching the key selector (can be nil)
	// and every provided flag selector.
	GetNodes(keySelector KeySelector, flagSelectors ...FlagSelector) []Node

	// GetFlagStats returns stats for a given flag.
	GetFlagStats(flagIndex int, filter KeySelector) FlagStats

	// GetNodeTimeline returns timeline of all node revisions, ordered from
	// the oldest to the newest.
	GetNodeTimeline(key string) []*RecordedNode

	// GetSnapshot returns the snapshot of the graph at a given time.
	GetSnapshot(time time.Time) []*RecordedNode

	// Dump returns a human-readable string representation of the current graph
	// content for debugging purposes.
	Dump() string

	// Release releases the graph handle (both Read() & Write() should end with
	// release).
	// For reader, the method releases R-lock.
	// For in-place writer, the method releases W-lock.
	Release()

	// ValidateEdges checks if targets and sources of all nodes correspond with
	// each other.
	// Use only for UTs, debugging, etc.
	ValidateEdges() error
}

ReadAccess lists operations provided by the read-only graph handle.

type RecordedFlags

type RecordedFlags struct {
	Flags [maxFlags]Flag
}

RecordedFlags is a record of assigned flags at a given time.

func (RecordedFlags) GetFlag

func (rf RecordedFlags) GetFlag(flagIndex int) Flag

GetFlag returns reference to the given flag or nil if the node hasn't had this flag associated at the given time.

func (RecordedFlags) MarshalJSON

func (rf RecordedFlags) MarshalJSON() ([]byte, error)

MarshalJSON marshalls recorded flags into JSON.

type RecordedNode

type RecordedNode struct {
	Since            time.Time
	Until            time.Time
	Key              string
	Label            string
	Value            proto.Message
	Flags            RecordedFlags
	MetadataFields   map[string][]string // field name -> values
	Targets          Targets
	TargetUpdateOnly bool // true if only runtime Targets have changed since the last rev
}

RecordedNode saves all attributes of a single node revision.

func (*RecordedNode) GetFlag

func (node *RecordedNode) GetFlag(flagIndex int) Flag

GetFlag returns reference to the given flag or nil if the node didn't have this flag associated at the time when it was recorded.

type RelationTargetDef

type RelationTargetDef struct {
	// Relation name.
	Relation string

	// Label for the edge.
	Label string // mandatory, unique for a given (source, relation)

	// Key of the target node.
	Key string

	// Selector selecting a set of target nodes.
	Selector TargetSelector
}

RelationTargetDef is a definition of a relation between a source node and a set of target nodes.

func (RelationTargetDef) Compare

func (t RelationTargetDef) Compare(t2 RelationTargetDef) (equal bool, order int)

Compare compares two relation target definitions (with the exception of KeySelector-s).

func (RelationTargetDef) Singleton

func (t RelationTargetDef) Singleton() bool

Singleton returns true if the target matches at most one key.

func (RelationTargetDef) WithKeySelector

func (t RelationTargetDef) WithKeySelector() bool

WithKeySelector returns true if the target is defined with key selector.

type RuntimeTarget

type RuntimeTarget struct {
	Label string
	Nodes []Node
}

RuntimeTarget, unlike Target, contains direct runtime references pointing to instances of target nodes (suitable for runtime processing but not for recording).

type RuntimeTargets

type RuntimeTargets []RuntimeTarget

RuntimeTargets is a slice of single-relation (runtime reference-based) targets, grouped by labels.

func (RuntimeTargets) GetTargetForLabel

func (rt RuntimeTargets) GetTargetForLabel(label string) *RuntimeTarget

GetTargetForLabel returns target (single node or a set of nodes) for the given label. Linear complexity is OK, it is used only in UTs.

type Target

type Target struct {
	Relation     string
	Label        string
	ExpectedKey  string // empty if Selector is used instead
	MatchingKeys utils.KeySet
}

Target nodes - not referenced directly, instead via their keys (suitable for recording).

type TargetIterator

type TargetIterator func(target Node, label string) (skipLabel, abort bool)

TargetIterator is a callback applied on every target. For each label it will be called n+1 times, where n is the number of targets available for the given label and the extra call will be made with nil target.

type TargetSelector

type TargetSelector struct {
	// KeyPrefixes is a list of key prefixes, each selecting a subset of target
	// nodes, which are then combined together - i.e. **union** is computed.
	KeyPrefixes []string

	// KeySelector allows to dynamically select target nodes.
	KeySelector KeySelector
}

TargetSelector allows to dynamically select a set of target nodes. The selections of KeyPrefixes and KeySelector are **intersected**.

type Targets

type Targets []Target

Targets is a slice of all targets of a single node, sorted by relation+label (in this order).

func (Targets) GetTargetForLabel

func (ts Targets) GetTargetForLabel(relation, label string) (t *Target, idx int)

GetTargetForLabel returns reference(+index) to target with the given relation+label.

func (Targets) RelationBegin

func (ts Targets) RelationBegin(relation string) int

RelationBegin returns index where targets for a given relation start in the array, or len(ts) if there are none.

func (Targets) String

func (ts Targets) String() string

String returns human-readable string representation of Targets.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL