fptree

Documentation

Index

• Constants
• func AnalyzeTreeNodeRefs(t *testing.T, trees ...*FPTree)
• func CheckTree(t *testing.T, ft *FPTree)
• type DBBackedStore
  • func NewDBBackedStore(db sql.Executor, sts *sqlstore.SyncedTableSnapshot, keyLen int) *DBBackedStore
  • func (s *DBBackedStore) All() rangesync.SeqResult
  • func (s *DBBackedStore) Clone() sqlstore.IDStore
  • func (s *DBBackedStore) From(from rangesync.KeyBytes, sizeHint int) rangesync.SeqResult
  • func (s *DBBackedStore) RegisterKey(k rangesync.KeyBytes) error
  • func (s *DBBackedStore) Release()
  • func (s *DBBackedStore) SetSnapshot(sts *sqlstore.SyncedTableSnapshot)
• type FPResult
• type FPTree
  • func NewFPTree(sizeHint int, idStore sqlstore.IDStore, keyLen, maxDepth int) *FPTree
  • func NewFPTreeWithValues(sizeHint, keyLen int) *FPTree
  • func (ft *FPTree) AddStoredKey(k rangesync.KeyBytes)
  • func (ft *FPTree) All() rangesync.SeqResult
  • func (ft *FPTree) CheckKey(k rangesync.KeyBytes) bool
  • func (ft *FPTree) Clear()
  • func (ft *FPTree) Clone() sqlstore.IDStore
  • func (ft *FPTree) Count() int
  • func (ft *FPTree) Dump(w io.Writer)
  • func (ft *FPTree) DumpToString() string
  • func (ft *FPTree) EnableTrace(enable bool)
  • func (ft *FPTree) FingerprintAll() FPResult
  • func (ft *FPTree) FingerprintInterval(x, y rangesync.KeyBytes, limit int) (fpr FPResult, err error)
  • func (ft *FPTree) From(from rangesync.KeyBytes, sizeHint int) rangesync.SeqResult
  • func (ft *FPTree) RegisterKey(k rangesync.KeyBytes) error
  • func (ft *FPTree) Release()
  • func (ft *FPTree) Split(x, y rangesync.KeyBytes, limit int) (sr SplitResult, err error)
• type SplitResult

Constants

const (
	FingerprintSize = rangesync.FingerprintSize
)

Functions

func AnalyzeTreeNodeRefs

func AnalyzeTreeNodeRefs(t *testing.T, trees ...*FPTree)

AnalyzeTreeNodeRefs checks that the reference counts are correct for the given trees in their respective node pools.

func CheckTree

func CheckTree(t *testing.T, ft *FPTree)

CheckTree checks that the tree has correct structure.

Types

type DBBackedStore

type DBBackedStore struct {
	*sqlstore.SQLIDStore
	*FPTree
}

DBBackedStore is an implementation of IDStore that keeps track of the rows in a database table, using an FPTree to store items that have arrived from a sync peer.

func NewDBBackedStore

func NewDBBackedStore(
	db sql.Executor,
	sts *sqlstore.SyncedTableSnapshot,
	keyLen int,
) *DBBackedStore

NewDBBackedStore creates a new DB-backed store. sizeHint is the expected number of items added to the store via RegisterHash _after_ the store is created.

func (*DBBackedStore) All

func (s *DBBackedStore) All() rangesync.SeqResult

All returns all the items currently in the store. Implements IDStore.

func (*DBBackedStore) Clone

func (s *DBBackedStore) Clone() sqlstore.IDStore

Clone creates a copy of the store. Implements IDStore.Clone.

func (*DBBackedStore) From

func (s *DBBackedStore) From(from rangesync.KeyBytes, sizeHint int) rangesync.SeqResult

From returns all the items in the store that are greater than or equal to the given key. Implements IDStore.

func (*DBBackedStore) RegisterKey

func (s *DBBackedStore) RegisterKey(k rangesync.KeyBytes) error

RegisterKey adds a hash to the store, using the FPTree so that the underlying database table is unchanged. Implements IDStore.

func (*DBBackedStore) Release

func (s *DBBackedStore) Release()

Release releases resources used by the store.

func (*DBBackedStore) SetSnapshot

func (s *DBBackedStore) SetSnapshot(sts *sqlstore.SyncedTableSnapshot)

SetSnapshot sets the table snapshot to be used by the store.

type FPResult

type FPResult struct {
	// Range fingerprint
	FP rangesync.Fingerprint
	// Number of items in the range
	Count uint32
	// Interval type: -1 for normal, 0 for the whole set, 1 for wrapped around ("inverse")
	IType int
	// Items in the range
	Items rangesync.SeqResult
	// The item following the range
	Next rangesync.KeyBytes
}

FPResult represents the result of a range fingerprint query against FPTree, as returned by FingerprintInterval.

type FPTree

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

FPTree is a binary tree data structure designed to perform range fingerprint queries efficiently. FPTree can work on its own, with fingerprint query complexity being O(log n). It can also be backed by an IDStore with a depth limit the binary tree, in which case the query efficiency degrades with the number of items growing. O(log n) query efficiency can be retained in this case for queries which have the number of non-zero bits, starting from the high bit, below maxDepth. FPTree does not do any special balancing and relies on the IDs added on it being uniformly distributed, which is the case for the IDs based on cryptographic hashes.

func NewFPTree

func NewFPTree(sizeHint int, idStore sqlstore.IDStore, keyLen, maxDepth int) *FPTree

NewFPTree creates an FPTree of limited depth backed by an IDStore. sizeHint specifies the approximate expected number of items. keyLen specifies the number of bytes in keys used.

func NewFPTreeWithValues

func NewFPTreeWithValues(sizeHint, keyLen int) *FPTree

NewFPTreeWithValues creates an FPTree which also stores the items themselves and does not make use of a backing IDStore. sizeHint specifies the approximate expected number of items. keyLen specifies the number of bytes in keys used.

func (*FPTree) AddStoredKey

func (ft *FPTree) AddStoredKey(k rangesync.KeyBytes)

AddStoredKey adds a key to the tree, assuming that either the tree doesn't have an IDStore ar the IDStore already contains the key.

func (*FPTree) All

func (ft *FPTree) All() rangesync.SeqResult

All returns all the items currently in the tree (including those in the IDStore). The sequence in SeqResult is either empty or infinite. Implements sqlstore.All.

func (*FPTree) CheckKey

func (ft *FPTree) CheckKey(k rangesync.KeyBytes) bool

CheckKey returns true if the tree contains or may contain the given key. If this function returns false, the tree definitely doesn't contain the key. If this function returns true and the tree stores the values, the key is definitely contained in the tree. If this function returns true and the tree doesn't store the values, the key may be contained in the tree.

func (*FPTree) Clear

func (ft *FPTree) Clear()

Clear removes all items from the tree. It should only be used with trees that were created using NewFPtreeWithValues.

func (*FPTree) Clone

func (ft *FPTree) Clone() sqlstore.IDStore

Clone makes a copy of the tree. The copy operation is thread-safe and has complexity of O(1).

func (*FPTree) Count

func (ft *FPTree) Count() int

Count returns the number of items in the tree.

func (*FPTree) Dump

func (ft *FPTree) Dump(w io.Writer)

Dump prints the tree structure to the writer.

func (*FPTree) DumpToString

func (ft *FPTree) DumpToString() string

DumpToString returns the tree structure as a string.

func (*FPTree) EnableTrace

func (ft *FPTree) EnableTrace(enable bool)

EnableTrace enables or disables tracing for the tree.

func (*FPTree) FingerprintAll

func (ft *FPTree) FingerprintAll() FPResult

FingerprintAll returns FingerprintResult for all items in the tree. Unlike FingerprintInterval, it is guaranteed not to query the underlying idStore, so it will never cause database access.

func (*FPTree) FingerprintInterval

func (ft *FPTree) FingerprintInterval(x, y rangesync.KeyBytes, limit int) (fpr FPResult, err error)

FingerprintInterval performs a range fingerprint query with specified bounds and limit.

func (*FPTree) From

func (ft *FPTree) From(from rangesync.KeyBytes, sizeHint int) rangesync.SeqResult

From returns all the items in the tree that are greater than or equal to the given key. The sequence in SeqResult is either empty or infinite. Implements sqlstore.IDStore.

func (*FPTree) RegisterKey

func (ft *FPTree) RegisterKey(k rangesync.KeyBytes) error

RegisterKey registers a key in the tree. If the tree has an IDStore, the key is also registered with the IDStore.

func (*FPTree) Release

func (ft *FPTree) Release()

Release releases resources used by the tree. Implements sqlstore.IDStore.

func (*FPTree) Split

func (ft *FPTree) Split(x, y rangesync.KeyBytes, limit int) (sr SplitResult, err error)

Split splits an interval in two parts.

type SplitResult

type SplitResult struct {
	// The two parts of the interval
	Part0, Part1 FPResult
	// Middle point value
	Middle rangesync.KeyBytes
}

SplitResult represents the result of a split operation.