Documentation ¶
Overview ¶
Package vellum is a library for building, serializing and executing an FST (finite state transducer).
There are two distinct phases, building an FST and using it.
When building an FST, you insert keys ([]byte) and their associated value (uint64). Insert operations MUST be done in lexicographic order. While building the FST, data is streamed to an underlying Writer. At the conclusion of building, you MUST call Close() on the builder.
After completion of the build phase, you can either Open() the FST if you serialized it to disk. Alternatively, if you already have the bytes in memory, you can use Load(). By default, Open() will use mmap to avoid loading the entire file into memory.
Once the FST is ready, you can use the Contains() method to see if a keys is in the FST. You can use the Get() method to see if a key is in the FST and retrieve it's associated value. And, you can use the Iterator method to enumerate key/value pairs within a specified range.
Example ¶
package main import ( "bytes" "fmt" "log" "github.com/couchbaselabs/vellum" ) func main() { var buf bytes.Buffer builder, err := vellum.New(&buf, nil) if err != nil { log.Fatal(err) } err = builder.Insert([]byte("cat"), 1) if err != nil { log.Fatal(err) } err = builder.Insert([]byte("dog"), 2) if err != nil { log.Fatal(err) } err = builder.Insert([]byte("fish"), 3) if err != nil { log.Fatal(err) } err = builder.Close() if err != nil { log.Fatal(err) } fst, err := vellum.Load(buf.Bytes()) if err != nil { log.Fatal(err) } val, exists, err := fst.Get([]byte("cat")) if err != nil { log.Fatal(err) } if exists { fmt.Println(val) } val, exists, err = fst.Get([]byte("dog")) if err != nil { log.Fatal(err) } if exists { fmt.Println(val) } val, exists, err = fst.Get([]byte("fish")) if err != nil { log.Fatal(err) } if exists { fmt.Println(val) } }
Output: 1 2 3
Index ¶
- Variables
- type AlwaysMatch
- type Automaton
- type Builder
- type BuilderOpts
- type FST
- func (f *FST) Close() error
- func (f *FST) Contains(val []byte) (bool, error)
- func (f *FST) Debug(callback func(int, interface{}) error) error
- func (f *FST) Get(input []byte) (uint64, bool, error)
- func (f *FST) Iterator(startKeyInclusive, endKeyExclusive []byte) (*Iterator, error)
- func (f *FST) Len() int
- func (f *FST) Search(aut Automaton, startKeyInclusive, endKeyExclusive []byte) (*Iterator, error)
- func (f *FST) Version() int
- type Iterator
Examples ¶
Constants ¶
This section is empty.
Variables ¶
var ErrIteratorDone = errors.New("iterator-done")
ErrIteratorDone is returned by Iterator/Next/Seek methods when the Current() value pointed to by the iterator is greater than the last key in this FST, or outside the configured startKeyInclusive/endKeyExclusive range of the Iterator.
var ErrOutOfOrder = errors.New("values not inserted in lexicographic order")
ErrOutOfOrder is returned when values are not inserted in lexicographic order.
Functions ¶
This section is empty.
Types ¶
type AlwaysMatch ¶
type AlwaysMatch struct{}
AlwaysMatch is an Automaton implementation which always matches
func (*AlwaysMatch) Accept ¶
func (m *AlwaysMatch) Accept(int, byte) int
Accept returns the next AlwaysMatch state
func (*AlwaysMatch) CanMatch ¶
func (m *AlwaysMatch) CanMatch(int) bool
CanMatch always returns true
func (*AlwaysMatch) Start ¶
func (m *AlwaysMatch) Start() int
Start returns the AlwaysMatch start state
func (*AlwaysMatch) WillAlwaysMatch ¶
func (m *AlwaysMatch) WillAlwaysMatch(int) bool
WillAlwaysMatch always returns true
type Automaton ¶
type Automaton interface { // Start returns the start state Start() int // IsMatch returns true if and only if the state is a match IsMatch(int) bool // CanMatch returns true if and only if it is possible to reach a match // in zero or more steps CanMatch(int) bool // WillAlwaysMatch returns true if and only if the current state matches // and will always match no matter what steps are taken WillAlwaysMatch(int) bool // Accept returns the next state given the input to the specified state Accept(int, byte) int }
Automaton represents the general contract of a byte-based finite automaton
type Builder ¶
type Builder struct {
// contains filtered or unexported fields
}
A Builder is used to build a new FST. When possible data is streamed out to the underlying Writer as soon as possible.
func New ¶
func New(w io.Writer, opts *BuilderOpts) (*Builder, error)
New returns a new Builder which will stream out the underlying representation to the provided Writer as the set is built.
type BuilderOpts ¶
BuilderOpts is a structure to let advanced users customize the behavior of the builder and some aspects of the generated FST.
type FST ¶
type FST struct {
// contains filtered or unexported fields
}
FST is an in-memory representation of a finite state transducer, capable of returning the uint64 value associated with each []byte key stored, as well as enumerating all of the keys in order.
func (*FST) Close ¶
Close will unmap any mmap'd data (if managed by vellum) and it will close the backing file (if managed by vellum). You MUST call Close() for any FST instance that is created.
func (*FST) Debug ¶
Debug is only intended for debug purposes, it simply asks the underlying decoder visit each state, and pass it to the provided callback.
func (*FST) Get ¶
Get returns the value associated with the key. NOTE: a value of zero does not imply the key does not exist, you must consult the second return value as well.
func (*FST) Iterator ¶
Iterator returns a new Iterator capable of enumerating the key/value pairs between the provided startKeyInclusive and endKeyExclusive.
type Iterator ¶
type Iterator struct {
// contains filtered or unexported fields
}
Iterator is a structure for iterating key/value pairs in this FST in lexicographic order. Iterators should be constructed with the Iterator method on the parent FST structure.
func (*Iterator) Current ¶
Current returns the key and value currently pointed to by the iterator. If the iterator is not pointing at a valid value (because Iterator/Next/Seek) returned an error previously, it may return nil,0.
func (*Iterator) Next ¶
Next advances this iterator to the next key/value pair. If there is none or the advancement goes beyond the configured endKeyExclusive, then ErrIteratorDone is returned.
func (*Iterator) Seek ¶
Seek advances this iterator to the specified key/value pair. If this key is not in the FST, Current() will return the next largest key. If this seek operation would go past the last key, or outside the configured startKeyInclusive/endKeyExclusive then ErrIteratorDone is returned.