index

package
v0.0.0-...-886857c Latest Latest
Warning

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

 Go to latest Published: Jan 2, 2023 License: MIT Imports: 7 Imported by: 0

Documentation

Overview

Package index provides for datum indexes implemented on btrees.

Index

Constants

This section is empty.

Variables

View Source 
var AEVIndex = IndexType{
	StringLesser: LessAEV[string],
	IntLesser:    LessAEV[int64],
	UintLesser:   LessAEV[uint64],
	FloatLesser:  LessAEV[float64],
}

AEVIndex is the AEV index type.

View Source 
var AVEIndex = IndexType{
	StringLesser: LessAVE[string],
	IntLesser:    LessAVE[int64],
	UintLesser:   LessAVE[uint64],
	FloatLesser:  LessAVE[float64],
}

AVEIndex is the AVE index type.

View Source 
var EAVIndex = IndexType{
	StringLesser: LessEAV[string],
	IntLesser:    LessEAV[int64],
	UintLesser:   LessEAV[uint64],
	FloatLesser:  LessEAV[float64],
}

EAVIndex is the EAV index type.

View Source 
var VAEIndex = IndexType{
	StringLesser: LessVAE[string],
	IntLesser:    LessVAE[int64],
	UintLesser:   LessVAE[uint64],
	FloatLesser:  LessVAE[float64],
}

VAEIndex is the VAE index type.

Functions

func CompareA 

func CompareA[X constraints.Ordered](d1 TypedDatum[X], d2 TypedDatum[X]) (diff int)

func CompareAE 

func CompareAE[X constraints.Ordered](d1 TypedDatum[X], d2 TypedDatum[X]) (diff int)

func CompareAEV 

func CompareAEV[X constraints.Ordered](d1 TypedDatum[X], d2 TypedDatum[X]) (diff int)

func CompareAV 

func CompareAV[X constraints.Ordered](d1 TypedDatum[X], d2 TypedDatum[X]) (diff int)

func CompareAVE 

func CompareAVE[X constraints.Ordered](d1 TypedDatum[X], d2 TypedDatum[X]) (diff int)

func CompareE 

func CompareE[X constraints.Ordered](d1 TypedDatum[X], d2 TypedDatum[X]) (diff int)

func CompareEA 

func CompareEA[X constraints.Ordered](d1 TypedDatum[X], d2 TypedDatum[X]) (diff int)

func CompareEAV 

func CompareEAV[X constraints.Ordered](d1 TypedDatum[X], d2 TypedDatum[X]) (diff int)

func CompareV 

func CompareV[X constraints.Ordered](d1 TypedDatum[X], d2 TypedDatum[X]) (diff int)

func CompareVA 

func CompareVA[X constraints.Ordered](d1 TypedDatum[X], d2 TypedDatum[X]) (diff int)

func CompareVAE 

func CompareVAE[X constraints.Ordered](d1 TypedDatum[X], d2 TypedDatum[X]) (diff int)

func LessAEV 

func LessAEV[X constraints.Ordered](d1 TypedDatum[X], d2 TypedDatum[X]) (less bool)

func LessAVE 

func LessAVE[X constraints.Ordered](d1 TypedDatum[X], d2 TypedDatum[X]) (less bool)

func LessEAV 

func LessEAV[X constraints.Ordered](d1 TypedDatum[X], d2 TypedDatum[X]) (less bool)

func LessVAE 

func LessVAE[X constraints.Ordered](d1 TypedDatum[X], d2 TypedDatum[X]) (less bool)

Types

type Comparer 

type Comparer[X constraints.Ordered] func(d1 TypedDatum[X], d2 TypedDatum[X]) int

type CompositeIndex 

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

CompositeIndex is an index of indexes of the discrete types.

func NewCompositeIndex 

func NewCompositeIndex(degree int, indexType IndexType, attrTypes map[ID]ID) (composite *CompositeIndex)

NewCompositeIndex returns a new composite index of the given degree and index type. This creates a btree index for each of the four go scalar types to which the system attribute types most naturally serialize.

func (*CompositeIndex) Clone 

func (idx *CompositeIndex) Clone() (clone Index)

func (*CompositeIndex) Count 

func (idx *CompositeIndex) Count(p PartialIndex, datum Datum) (count int)

func (*CompositeIndex) Delete 

func (idx *CompositeIndex) Delete(datum Datum) (extant bool)

func (*CompositeIndex) Find 

func (idx *CompositeIndex) Find(datum Datum) (extant bool)

func (*CompositeIndex) First 

func (idx *CompositeIndex) First(p PartialIndex, datum Datum) (match Datum, extant bool)

func (*CompositeIndex) Insert 

func (idx *CompositeIndex) Insert(datum Datum) (extant bool)

func (*CompositeIndex) Select 

func (idx *CompositeIndex) Select(p PartialIndex, datum Datum) (iter *iterator.Iterator[Datum])

type Devaluer 

type Devaluer[X constraints.Ordered] func(value Value) (v X)

type Index 

type Index interface {
	// Find returns true if a datum with the given datum's eav values is present in the indexed set.
	Find(datum Datum) (extant bool)
	// Insert ensures a datum with the given datum's eav values is present in the indexed set. If
	// this returns true, the indexed datum will have the given datum's t value.
	Insert(datum Datum) (extant bool)
	// Delete ensures no datum with the given datum's eav values is present in the indexed set.
	// If this returns true, a datum was deleted in so doing.
	Delete(datum Datum) (extant bool)
	// Select returns an iterator of datums that match the given datum according to the partial
	// index.
	Select(p PartialIndex, datum Datum) (iter *iterator.Iterator[Datum])
	// First returns the first datum matching the partial index, if any.
	First(p PartialIndex, datum Datum) (match Datum, extant bool)
	// Count returns the number of datums matching the partial index.
	Count(p PartialIndex, datum Datum) (count int)
	// Clone returns a copy of the index. Both instances are hereafter safe to change without affecting
	// the other.
	Clone() (clone Index)
}

Index is a sorted set of datums, where the basis for uniqueness is eav. An index will retain the extant datum if a new one is inserted for the same eav.

Index instances are safe for concurrent reads, not for concurrent writes.

type IndexType 

type IndexType struct {
	StringLesser Lesser[string]
	IntLesser    Lesser[int64]
	UintLesser   Lesser[uint64]
	FloatLesser  Lesser[float64]
}

IndexType is a type of datum index, e.g. EAV.

type Lesser 

type Lesser[X constraints.Ordered] func(d1 TypedDatum[X], d2 TypedDatum[X]) bool

type PartialIndex 

type PartialIndex int8
const A PartialIndex = 4
const AE PartialIndex = 3
const AV PartialIndex = 5
const E PartialIndex = 2
const EA PartialIndex = 1
const VA PartialIndex = 6

type TypeValuer 

type TypeValuer[X constraints.Ordered] struct {
	// contains filtered or unexported fields
}

type TypedDatum 

type TypedDatum[X constraints.Ordered] struct {
	E ID
	A ID
	V X
	T ID
}

TypedDatum represents a datum with a specific V type. These will use less memory than interface V types and their values can be compared with an operator. Note that we probably lose throughput and add memory churn on select as we convert TypedDatum instances into Datum instances. Possibly it would be least bad to store the data as datums with interface v and use unsafe pointer foo to interpret the v memory efficiently based on the type of a.

type TypedIndex 

type TypedIndex[X constraints.Ordered] interface {
	// Find returns true if the given datum is in the index.
	Find(datum TypedDatum[X]) (extant bool)
	// Insert ensures the given datum is present in the index, returning true if it was already.
	Insert(datum TypedDatum[X]) (extant bool)
	// Delete ensures the given datum is not present in the index, returning true if it was.
	Delete(datum TypedDatum[X]) (extant bool)
	// Clone returns a copy of the index. Both the original and the clone may be changed hereafter
	// without either affecting the other.
	Clone() (clone TypedIndex[X])
	// Select returns an ascending iterator of datums starting at the point datum would occupy in the
	// ordered set for which the comparer returns 0. The v values of those datums are converted from
	// indexed storage values to datum Values with the valuer function.
	Select(comparer Comparer[X], valuer Valuer[X], datum TypedDatum[X]) (iter *iterator.Iterator[Datum])
	// Count returns the number of datums starting at the point datum would occupy in the ordered
	// set for which the comparer returns 0.
	Count(comparer Comparer[X], datum TypedDatum[X]) (count int)
	// First returns the first datum after the point datum would occupy in the ordered set for which
	// the comparer returns 0, if any. The v value of the datum is converted from indexed storage
	// value to datum Value with the valuer function.
	First(comparer Comparer[X], valuer Valuer[X], datum TypedDatum[X]) (match Datum, extant bool)
}

TypedIndex instances maintain sorted sets of typed datums. Indexes are safe for concurrent read operations but may not be safe for concurrent write operations, including cloning.

func NewBTreeIndex 

func NewBTreeIndex[X constraints.Ordered](degree int, lesser Lesser[X]) (index TypedIndex[X])

NewBTreeIndex returns a btree index of the given degree that sorts its set of typed datums according to the given lesser function, which returns true iff the first arg is less than the second.

type Valuer 

type Valuer[X constraints.Ordered] func(v X) (value Value)

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.