graph

package
v0.0.0-...-6764ea0 Latest Latest
Warning

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

Go to latest
Published: Apr 16, 2015 License: Apache-2.0 Imports: 12 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

View Source
var (
	ErrQuadExists   = errors.New("quad exists")
	ErrQuadNotExist = errors.New("quad does not exist")
)
View Source
var (
	IgnoreDup     = flag.Bool("ignoredup", false, "Don't stop loading on duplicated key on add")
	IgnoreMissing = flag.Bool("ignoremissing", false, "Don't stop loading on missing key on delete")
)
View Source
var ErrCannotBulkLoad = errors.New("quadstore: cannot bulk load")

Functions

func ContainsLogIn

func ContainsLogIn(it Iterator, val Value)

func ContainsLogOut

func ContainsLogOut(it Iterator, val Value, good bool) bool

func Height

func Height(it Iterator, until Type) int

Height is a convienence function to measure the height of an iterator tree.

func InitQuadStore

func InitQuadStore(name, dbpath string, opts Options) error

func IsPersistent

func IsPersistent(name string) bool

func Next

func Next(it Iterator) bool

Next is a convenience function that conditionally calls the Next method of an Iterator if it is a Nexter. If the Iterator is not a Nexter, Next returns false.

func NextLogIn

func NextLogIn(it Iterator)

func NextLogOut

func NextLogOut(it Iterator, val Value, ok bool) bool

func PrintResultTreeEvaluator

func PrintResultTreeEvaluator(it Nexter)

func QuadStores

func QuadStores() []string

func RegisterQuadStore

func RegisterQuadStore(name string, persists bool, newFunc NewStoreFunc, initFunc InitStoreFunc, newForRequestFunc NewStoreForRequestFunc)

func RegisterWriter

func RegisterWriter(name string, newFunc NewQuadWriterFunc)

func StringResultTreeEvaluator

func StringResultTreeEvaluator(it Nexter) string

func WriterMethods

func WriterMethods() []string

Types

type BulkLoader

type BulkLoader interface {
	// BulkLoad loads Quads from a quad.Unmarshaler in bulk to the QuadStore.
	// It returns ErrCannotBulkLoad if bulk loading is not possible. For example if
	// you cannot load in bulk to a non-empty database, and the db is non-empty.
	BulkLoad(quad.Unmarshaler) error
}

type Delta

type Delta struct {
	ID        PrimaryKey
	Quad      quad.Quad
	Action    Procedure
	Timestamp time.Time
}

type Description

type Description struct {
	UID       uint64         `json:",omitempty"`
	Name      string         `json:",omitempty"`
	Type      Type           `json:",omitempty"`
	Tags      []string       `json:",omitempty"`
	Size      int64          `json:",omitempty"`
	Direction quad.Direction `json:",omitempty"`
	Iterator  *Description   `json:",omitempty"`
	Iterators []Description  `json:",omitempty"`
}

type FixedIterator

type FixedIterator interface {
	Iterator
	Add(Value)
}

FixedIterator wraps iterators that are modifiable by addition of fixed value sets.

type Handle

type Handle struct {
	QuadStore  QuadStore
	QuadWriter QuadWriter
}

func (*Handle) Close

func (h *Handle) Close()

type IgnoreOpts

type IgnoreOpts struct {
	IgnoreDup, IgnoreMissing bool
}

type InitStoreFunc

type InitStoreFunc func(string, Options) error

type Iterator

type Iterator interface {
	Tagger() *Tagger

	// Fills a tag-to-result-value map.
	TagResults(map[string]Value)

	// Returns the current result.
	Result() Value

	// DEPRECATED -- Fills a ResultTree struct with Result().
	ResultTree() *ResultTree

	// These methods are the heart and soul of the iterator, as they constitute
	// the iteration interface.
	//
	// To get the full results of iteration, do the following:
	//
	//  for graph.Next(it) {
	//  	val := it.Result()
	//  	... do things with val.
	//  	for it.NextPath() {
	//  		... find other paths to iterate
	//  	}
	//  }
	//
	// All of them should set iterator.Last to be the last returned value, to
	// make results work.
	//
	// NextPath() advances iterators that may have more than one valid result,
	// from the bottom up.
	NextPath() bool

	// Contains returns whether the value is within the set held by the iterator.
	Contains(Value) bool

	// Err returns any error that was encountered by the Iterator.
	Err() error

	// Start iteration from the beginning
	Reset()

	// Create a new iterator just like this one
	Clone() Iterator

	// These methods relate to choosing the right iterator, or optimizing an
	// iterator tree
	//
	// Stats() returns the relative costs of calling the iteration methods for
	// this iterator, as well as the size. Roughly, it will take NextCost * Size
	// "cost units" to get everything out of the iterator. This is a wibbly-wobbly
	// thing, and not exact, but a useful heuristic.
	Stats() IteratorStats

	// Helpful accessor for the number of things in the iterator. The first return
	// value is the size, and the second return value is whether that number is exact,
	// or a conservative estimate.
	Size() (int64, bool)

	// Returns a string relating to what the function of the iterator is. By
	// knowing the names of the iterators, we can devise optimization strategies.
	Type() Type

	// Optimizes an iterator. Can replace the iterator, or merely move things
	// around internally. if it chooses to replace it with a better iterator,
	// returns (the new iterator, true), if not, it returns (self, false).
	Optimize() (Iterator, bool)

	// Return a slice of the subiterators for this iterator.
	SubIterators() []Iterator

	// Return a string representation of the iterator.
	Describe() Description

	// Close the iterator and do internal cleanup.
	Close() error

	// UID returns the unique identifier of the iterator.
	UID() uint64
}

type IteratorStats

type IteratorStats struct {
	ContainsCost int64
	NextCost     int64
	Size         int64
	Next         int64
	Contains     int64
	ContainsNext int64
}

type NewQuadWriterFunc

type NewQuadWriterFunc func(QuadStore, Options) (QuadWriter, error)

type NewStoreForRequestFunc

type NewStoreForRequestFunc func(QuadStore, Options) (QuadStore, error)

type NewStoreFunc

type NewStoreFunc func(string, Options) (QuadStore, error)

type Nexter

type Nexter interface {
	// Next advances the iterator to the next value, which will then be available through
	// the Result method. It returns false if no further advancement is possible, or if an
	// error was encountered during iteration.  Err should be consulted to distinguish
	// between the two cases.
	Next() bool

	Iterator
}

type Options

type Options map[string]interface{}

func (Options) BoolKey

func (d Options) BoolKey(key string) (bool, bool, error)

func (Options) IntKey

func (d Options) IntKey(key string) (int, bool, error)

func (Options) StringKey

func (d Options) StringKey(key string) (string, bool, error)

type PrimaryKey

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

func NewSequentialKey

func NewSequentialKey(horizon int64) PrimaryKey

func NewUniqueKey

func NewUniqueKey(horizon string) PrimaryKey

func (*PrimaryKey) Int

func (p *PrimaryKey) Int() int64

func (PrimaryKey) MarshalJSON

func (p PrimaryKey) MarshalJSON() ([]byte, error)

func (*PrimaryKey) Next

func (p *PrimaryKey) Next() PrimaryKey

func (*PrimaryKey) String

func (p *PrimaryKey) String() string

func (*PrimaryKey) UnmarshalJSON

func (p *PrimaryKey) UnmarshalJSON(bytes []byte) error

type Procedure

type Procedure int8
const (
	Add    Procedure = +1
	Delete Procedure = -1
)

The different types of actions a transaction can do.

type QuadStore

type QuadStore interface {
	// The only way in is through building a transaction, which
	// is done by a replication strategy.
	ApplyDeltas([]Delta, IgnoreOpts) error

	// Given an opaque token, returns the quad for that token from the store.
	Quad(Value) quad.Quad

	// Given a direction and a token, creates an iterator of links which have
	// that node token in that directional field.
	QuadIterator(quad.Direction, Value) Iterator

	// Returns an iterator enumerating all nodes in the graph.
	NodesAllIterator() Iterator

	// Returns an iterator enumerating all links in the graph.
	QuadsAllIterator() Iterator

	// Given a node ID, return the opaque token used by the QuadStore
	// to represent that id.
	ValueOf(string) Value

	// Given an opaque token, return the node that it represents.
	NameOf(Value) string

	// Returns the number of quads currently stored.
	Size() int64

	// The last replicated transaction ID that this quadstore has verified.
	Horizon() PrimaryKey

	// Creates a fixed iterator which can compare Values
	FixedIterator() FixedIterator

	// Optimize an iterator in the context of the quad store.
	// Suppose we have a better index for the passed tree; this
	// gives the QuadStore the opportunity to replace it
	// with a more efficient iterator.
	OptimizeIterator(it Iterator) (Iterator, bool)

	// Close the quad store and clean up. (Flush to disk, cleanly
	// sever connections, etc)
	Close()

	// Convenience function for speed. Given a quad token and a direction
	// return the node token for that direction. Sometimes, a QuadStore
	// can do this without going all the way to the backing store, and
	// gives the QuadStore the opportunity to make this optimization.
	//
	// Iterators will call this. At worst, a valid implementation is
	//
	//  qs.ValueOf(qs.Quad(id).Get(dir))
	//
	QuadDirection(id Value, d quad.Direction) Value

	// Get the type of QuadStore
	//TODO replace this using reflection
	Type() string
}

func NewQuadStore

func NewQuadStore(name, dbpath string, opts Options) (QuadStore, error)

func NewQuadStoreForRequest

func NewQuadStoreForRequest(qs QuadStore, opts Options) (QuadStore, error)

type QuadWriter

type QuadWriter interface {
	// Add a quad to the store.
	AddQuad(quad.Quad) error

	// Add a set of quads to the store, atomically if possible.
	AddQuadSet([]quad.Quad) error

	// Removes a quad matching the given one  from the database,
	// if it exists. Does nothing otherwise.
	RemoveQuad(quad.Quad) error

	// Cleans up replication and closes the writing aspect of the database.
	Close() error
}

func NewQuadWriter

func NewQuadWriter(name string, qs QuadStore, opts Options) (QuadWriter, error)

type ResultTree

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

func NewResultTree

func NewResultTree(result Value) *ResultTree

func (*ResultTree) AddSubtree

func (t *ResultTree) AddSubtree(sub *ResultTree)

func (*ResultTree) String

func (t *ResultTree) String() string

type StatsContainer

type StatsContainer struct {
	UID  uint64
	Type Type
	IteratorStats
	SubIts []StatsContainer
}

func DumpStats

func DumpStats(it Iterator) StatsContainer

type Tagger

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

func (*Tagger) Add

func (t *Tagger) Add(tag string)

Add a tag to the iterator.

func (*Tagger) AddFixed

func (t *Tagger) AddFixed(tag string, value Value)

func (*Tagger) CopyFrom

func (t *Tagger) CopyFrom(src Iterator)

func (*Tagger) Fixed

func (t *Tagger) Fixed() map[string]Value

Fixed returns the fixed tags held in the tagger. The returned value must not be mutated.

func (*Tagger) Tags

func (t *Tagger) Tags() []string

Tags returns the tags held in the tagger. The returned value must not be mutated.

type Type

type Type int

Type enumerates the set of Iterator types.

const (
	Invalid Type = iota
	All
	And
	Or
	HasA
	LinksTo
	Comparison
	Null
	Fixed
	Not
	Optional
	Materialize
)

These are the iterator types, defined as constants

func RegisterIterator

func RegisterIterator(name string) Type

RegisterIterator adds a new iterator type to the set of acceptable types, returning the registered Type. Calls to Register are idempotent and must be made prior to use of the iterator. The conventional approach for use is to include a call to Register in a package init() function, saving the Type to a private package var.

func (*Type) MarshalText

func (t *Type) MarshalText() (text []byte, err error)

func (Type) String

func (t Type) String() string

String returns a string representation of the Type.

func (*Type) UnmarshalText

func (t *Type) UnmarshalText(text []byte) error

type Value

type Value interface{}

Value defines an opaque "quad store value" type. However the backend wishes to implement it, a Value is merely a token to a quad or a node that the backing store itself understands, and the base iterators pass around.

For example, in a very traditional, graphd-style graph, these are int64s (guids of the primitives). In a very direct sort of graph, these could be pointers to structs, or merely quads, or whatever works best for the backing store.

These must be comparable, or implement a `Key() interface{}` function so that they may be stored in maps.

Directories

Path Synopsis
b
Package b implements a B+tree.
Package b implements a B+tree.

Jump to

Keyboard shortcuts

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