memstore

package
v0.7.5 Latest Latest
Warning

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

 Go to latest Published: Nov 26, 2018 License: Apache-2.0 Imports: 10 Imported by: 0

Documentation

Overview

Package b implements a B+tree.

Changelog

2014-06-26: Lower GC presure by recycling things.

2014-04-18: Added new method Put.

Generic types

Keys and their associated values are interface{} typed, similar to all of the containers in the standard library.

Semiautomatic production of a type specific variant of this package is supported via 

$ make generic

This command will write to stdout a version of the btree.go file where every key type occurrence is replaced by the word 'key' (written in all CAPS) and every value type occurrence is replaced by the word 'value' (written in all CAPS). Then you have to replace these tokens with your desired type(s), using any technique you're comfortable with.

This is how, for example, 'example/int.go' was created: 

$ mkdir example
$
$ # Note: the command bellow must be actually written using the words
$ # 'key' and 'value' in all CAPS. The proper form is avoided in this
$ # documentation to not confuse any text replacement mechanism.
$
$ make generic | sed -e 's/key/int/g' -e 's/value/int/g' > example/int.go

No other changes to int.go are necessary, it compiles just fine.

Running the benchmarks for 1000 keys on a machine with Intel i5-4670 CPU @ 3.4GHz, Go release 1.3. 

$ go test -bench 1e3 example/all_test.go example/int.go
PASS
BenchmarkSetSeq1e3	   10000	    146740 ns/op
BenchmarkGetSeq1e3	   10000	    108261 ns/op
BenchmarkSetRnd1e3	   10000	    254359 ns/op
BenchmarkGetRnd1e3	   10000	    134621 ns/op
BenchmarkDelRnd1e3	   10000	    211864 ns/op
BenchmarkSeekSeq1e3	   10000	    148628 ns/op
BenchmarkSeekRnd1e3	   10000	    215166 ns/op
BenchmarkNext1e3	  200000	      9211 ns/op
BenchmarkPrev1e3	  200000	      8843 ns/op
ok  	command-line-arguments	25.071s
$

Index

Constants

View Source 
const QuadStoreType = "memstore"

Variables

This section is empty.

Functions

This section is empty.

Types

type AllIterator 

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

func (*AllIterator) Clone 

func (it *AllIterator) Clone() graph.Iterator

func (*AllIterator) Close 

func (it *AllIterator) Close() error

func (*AllIterator) Contains 

func (it *AllIterator) Contains(ctx context.Context, v graph.Value) bool

func (*AllIterator) Err 

func (it *AllIterator) Err() error

func (*AllIterator) Next 

func (it *AllIterator) Next(ctx context.Context) bool

func (*AllIterator) NextPath 

func (it *AllIterator) NextPath(ctx context.Context) bool

func (*AllIterator) Optimize 

func (it *AllIterator) Optimize() (graph.Iterator, bool)

func (*AllIterator) Reset 

func (it *AllIterator) Reset()

func (*AllIterator) Result 

func (it *AllIterator) Result() graph.Value

func (*AllIterator) Size 

func (it *AllIterator) Size() (int64, bool)

func (*AllIterator) Stats 

func (it *AllIterator) Stats() graph.IteratorStats

func (*AllIterator) String 

func (it *AllIterator) String() string

func (*AllIterator) SubIterators 

func (it *AllIterator) SubIterators() []graph.Iterator

func (*AllIterator) TagResults 

func (it *AllIterator) TagResults(dst map[string]graph.Value)

func (*AllIterator) Tagger 

func (it *AllIterator) Tagger() *graph.Tagger

func (*AllIterator) Type 

func (it *AllIterator) Type() graph.Type

func (*AllIterator) UID 

func (it *AllIterator) UID() uint64

type Cmp 

type Cmp func(a, b int64) int

Cmp compares a and b. Return value is: 

< 0 if a <  b
  0 if a == b
> 0 if a >  b

type Enumerator 

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

Enumerator captures the state of enumerating a tree. It is returned from the Seek* methods. The enumerator is aware of any mutations made to the tree in the process of enumerating it and automatically resumes the enumeration at the proper key, if possible.

However, once an Enumerator returns io.EOF to signal "no more items", it does no more attempt to "resync" on tree mutation(s). In other words, io.EOF from an Enumaretor is "sticky" (idempotent).

func (*Enumerator) Close 

func (e *Enumerator) Close()

Close recycles e to a pool for possible later reuse. No references to e should exist or such references must not be used afterwards.

func (*Enumerator) Next 

func (e *Enumerator) Next() (k int64, v *primitive, err error)

Next returns the currently enumerated item, if it exists and moves to the next item in the key collation order. If there is no item to return, err == io.EOF is returned.

func (*Enumerator) Prev 

func (e *Enumerator) Prev() (k int64, v *primitive, err error)

Prev returns the currently enumerated item, if it exists and moves to the previous item in the key collation order. If there is no item to return, err == io.EOF is returned.

type Iterator 

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

func NewIterator 

func NewIterator(tree *Tree, qs *QuadStore, d quad.Direction, value int64) *Iterator

func (*Iterator) Clone 

func (it *Iterator) Clone() graph.Iterator

func (*Iterator) Close 

func (it *Iterator) Close() error

func (*Iterator) Contains 

func (it *Iterator) Contains(ctx context.Context, v graph.Value) bool

func (*Iterator) Err 

func (it *Iterator) Err() error

func (*Iterator) Next 

func (it *Iterator) Next(ctx context.Context) bool

func (*Iterator) NextPath 

func (it *Iterator) NextPath(ctx context.Context) bool

func (*Iterator) Optimize 

func (it *Iterator) Optimize() (graph.Iterator, bool)

func (*Iterator) Reset 

func (it *Iterator) Reset()

func (*Iterator) Result 

func (it *Iterator) Result() graph.Value

func (*Iterator) Size 

func (it *Iterator) Size() (int64, bool)

func (*Iterator) Sorted 

func (it *Iterator) Sorted() bool

func (*Iterator) Stats 

func (it *Iterator) Stats() graph.IteratorStats

func (*Iterator) String 

func (it *Iterator) String() string

func (*Iterator) SubIterators 

func (it *Iterator) SubIterators() []graph.Iterator

No subiterators.

func (*Iterator) TagResults 

func (it *Iterator) TagResults(dst map[string]graph.Value)

func (*Iterator) Tagger 

func (it *Iterator) Tagger() *graph.Tagger

func (*Iterator) Type 

func (it *Iterator) Type() graph.Type

func (*Iterator) UID 

func (it *Iterator) UID() uint64

type QuadDirectionIndex 

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

func NewQuadDirectionIndex 

func NewQuadDirectionIndex() QuadDirectionIndex

func (QuadDirectionIndex) Get 

func (qdi QuadDirectionIndex) Get(d quad.Direction, id int64) (*Tree, bool)

func (QuadDirectionIndex) Tree 

func (qdi QuadDirectionIndex) Tree(d quad.Direction, id int64) *Tree

type QuadStore 

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

func New 

func New(quads ...quad.Quad) *QuadStore

New creates a new in-memory quad store and loads provided quads.

func (*QuadStore) AddBNode 

func (qs *QuadStore) AddBNode() int64

AddNode adds a blank node (with no value) to quad store. It returns an id of the node.

func (*QuadStore) AddQuad 

func (qs *QuadStore) AddQuad(q quad.Quad) (int64, bool)

AddQuad adds a quad to quad store. It returns an id of the quad. False is returned as a second parameter if quad exists already.

func (*QuadStore) AddValue 

func (qs *QuadStore) AddValue(v quad.Value) (int64, bool)

AddNode adds a value to quad store. It returns an id of the value. False is returned as a second parameter if value exists already.

func (*QuadStore) ApplyDeltas 

func (qs *QuadStore) ApplyDeltas(deltas []graph.Delta, ignoreOpts graph.IgnoreOpts) error

func (*QuadStore) Close 

func (qs *QuadStore) Close() error

func (*QuadStore) Delete 

func (qs *QuadStore) Delete(id int64) bool

func (*QuadStore) NameOf 

func (qs *QuadStore) NameOf(v graph.Value) quad.Value

func (*QuadStore) NodesAllIterator 

func (qs *QuadStore) NodesAllIterator() graph.Iterator

func (*QuadStore) OptimizeIterator 

func (qs *QuadStore) OptimizeIterator(it graph.Iterator) (graph.Iterator, bool)

func (*QuadStore) Quad 

func (qs *QuadStore) Quad(index graph.Value) quad.Quad

func (*QuadStore) QuadDirection 

func (qs *QuadStore) QuadDirection(val graph.Value, d quad.Direction) graph.Value

func (*QuadStore) QuadIterator 

func (qs *QuadStore) QuadIterator(d quad.Direction, value graph.Value) graph.Iterator

func (*QuadStore) QuadsAllIterator 

func (qs *QuadStore) QuadsAllIterator() graph.Iterator

func (*QuadStore) Size 

func (qs *QuadStore) Size() int64

func (*QuadStore) ValueOf 

func (qs *QuadStore) ValueOf(name quad.Value) graph.Value

func (*QuadStore) WriteQuad deprecated 

func (qs *QuadStore) WriteQuad(q quad.Quad) error

WriteQuad adds a quad to quad store.

Deprecated: use AddQuad instead.

type Tree 

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

Tree is a B+tree.

func TreeNew 

func TreeNew(cmp Cmp) *Tree

TreeNew returns a newly created, empty Tree. The compare function is used for key collation.

func (*Tree) Clear 

func (t *Tree) Clear()

Clear removes all K/V pairs from the tree.

func (*Tree) Close 

func (t *Tree) Close()

Close performs Clear and recycles t to a pool for possible later reuse. No references to t should exist or such references must not be used afterwards.

func (*Tree) Delete 

func (t *Tree) Delete(k int64) (ok bool)

Delete removes the k's KV pair, if it exists, in which case Delete returns true.

func (*Tree) First 

func (t *Tree) First() (k int64, v *primitive)

First returns the first item of the tree in the key collating order, or (zero-value, zero-value) if the tree is empty.

func (*Tree) Get 

func (t *Tree) Get(k int64) (v *primitive, ok bool)

Get returns the value associated with k and true if it exists. Otherwise Get returns (zero-value, false).

func (*Tree) Last 

func (t *Tree) Last() (k int64, v *primitive)

Last returns the last item of the tree in the key collating order, or (zero-value, zero-value) if the tree is empty.

func (*Tree) Len 

func (t *Tree) Len() int

Len returns the number of items in the tree.

func (*Tree) Put 

func (t *Tree) Put(k int64, upd func(oldV *primitive, exists bool) (newV *primitive, write bool)) (oldV *primitive, written bool)

Put combines Get and Set in a more efficient way where the tree is walked only once. The upd(ater) receives (old-value, true) if a KV pair for k exists or (zero-value, false) otherwise. It can then return a (new-value, true) to create or overwrite the existing value in the KV pair, or (whatever, false) if it decides not to create or not to update the value of the KV pair. 

tree.Set(k, v) call conceptually equals calling

tree.Put(k, func(int64, bool){ return v, true })

modulo the differing return values.

func (*Tree) Seek 

func (t *Tree) Seek(k int64) (e *Enumerator, ok bool)

Seek returns an Enumerator positioned on a an item such that k >= item's key. ok reports if k == item.key The Enumerator's position is possibly after the last item in the tree.

func (*Tree) SeekFirst 

func (t *Tree) SeekFirst() (e *Enumerator, err error)

SeekFirst returns an enumerator positioned on the first KV pair in the tree, if any. For an empty tree, err == io.EOF is returned and e will be nil.

func (*Tree) SeekLast 

func (t *Tree) SeekLast() (e *Enumerator, err error)

SeekLast returns an enumerator positioned on the last KV pair in the tree, if any. For an empty tree, err == io.EOF is returned and e will be nil.

func (*Tree) Set 

func (t *Tree) Set(k int64, v *primitive)

Set sets the value associated with k.

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.