1// Copyright (c) 2017 Couchbase, Inc. 2// 3// Licensed under the Apache License, Version 2.0 (the "License"); 4// you may not use this file except in compliance with the License. 5// You may obtain a copy of the License at 6// 7// http://www.apache.org/licenses/LICENSE-2.0 8// 9// Unless required by applicable law or agreed to in writing, software 10// distributed under the License is distributed on an "AS IS" BASIS, 11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12// See the License for the specific language governing permissions and 13// limitations under the License. 14 15/* 16Package vellum is a library for building, serializing and executing an FST (finite 17state transducer). 18 19There are two distinct phases, building an FST and using it. 20 21When building an FST, you insert keys ([]byte) and their associated value 22(uint64). Insert operations MUST be done in lexicographic order. While 23building the FST, data is streamed to an underlying Writer. At the conclusion 24of building, you MUST call Close() on the builder. 25 26After completion of the build phase, you can either Open() the FST if you 27serialized it to disk. Alternatively, if you already have the bytes in 28memory, you can use Load(). By default, Open() will use mmap to avoid loading 29the entire file into memory. 30 31Once the FST is ready, you can use the Contains() method to see if a keys is 32in the FST. You can use the Get() method to see if a key is in the FST and 33retrieve it's associated value. And, you can use the Iterator method to 34enumerate key/value pairs within a specified range. 35 36*/ 37package vellum 38 39import ( 40 "errors" 41 "io" 42) 43 44// ErrOutOfOrder is returned when values are not inserted in 45// lexicographic order. 46var ErrOutOfOrder = errors.New("values not inserted in lexicographic order") 47 48// ErrIteratorDone is returned by Iterator/Next/Seek methods when the 49// Current() value pointed to by the iterator is greater than the last 50// key in this FST, or outside the configured startKeyInclusive/endKeyExclusive 51// range of the Iterator. 52var ErrIteratorDone = errors.New("iterator-done") 53 54// BuilderOpts is a structure to let advanced users customize the behavior 55// of the builder and some aspects of the generated FST. 56type BuilderOpts struct { 57 Encoder int 58 RegistryTableSize int 59 RegistryMRUSize int 60} 61 62// New returns a new Builder which will stream out the 63// underlying representation to the provided Writer as the set is built. 64func New(w io.Writer, opts *BuilderOpts) (*Builder, error) { 65 return newBuilder(w, opts) 66} 67 68// Open loads the FST stored in the provided path 69func Open(path string) (*FST, error) { 70 return open(path) 71} 72 73// Load will return the FST represented by the provided byte slice. 74func Load(data []byte) (*FST, error) { 75 return new(data, nil) 76} 77 78// Merge will iterate through the provided Iterators, merge duplicate keys 79// with the provided MergeFunc, and build a new FST to the provided Writer. 80func Merge(w io.Writer, opts *BuilderOpts, itrs []Iterator, f MergeFunc) error { 81 builder, err := New(w, opts) 82 if err != nil { 83 return err 84 } 85 86 itr, err := NewMergeIterator(itrs, f) 87 for err == nil { 88 k, v := itr.Current() 89 err = builder.Insert(k, v) 90 if err != nil { 91 return err 92 } 93 err = itr.Next() 94 } 95 96 if err != nil && err != ErrIteratorDone { 97 return err 98 } 99 100 err = itr.Close() 101 if err != nil { 102 return err 103 } 104 105 err = builder.Close() 106 if err != nil { 107 return err 108 } 109 110 return nil 111} 112