Documentation
¶
Index ¶
- Variables
- func LexicographicallySortableFloat64(in float64) ([]byte, error)
- func LexicographicallySortableInt64(in int64) ([]byte, error)
- func LexicographicallySortableUint64(in uint64) ([]byte, error)
- func NewMissingFilterableIndexError(propName string) error
- func NewMissingFilterableMetaCountIndexError(propName string) error
- func NewMissingSearchableIndexError(propName string) error
- func ParseLexicographicallySortableFloat64(in []byte) (float64, error)
- func ParseLexicographicallySortableInt64(in []byte) (int64, error)
- func ParseLexicographicallySortableUint64(in []byte) (uint64, error)
- func PutLexicographicallySortableFloat64(dst []byte, in float64)
- func PutLexicographicallySortableInt64(dst []byte, in int64)
- type FixedKeyBuilder
- type MissingIndexError
- type SortedKeys
- type VarKeyBuilder
Constants ¶
This section is empty.
Variables ¶
var ErrInternal = errors.New("inverted: internal fault")
ErrInternal reports that a list could not be built because this package, or its caller, is wrong — not because a filter value was. A builder's other rejections and this one reach the API through the same return, so without a sentinel a broken sort would look like a malformed query; a searcher can tell them apart and log an internal fault as one.
Returned rather than panicked: the gRPC search path installs no recovery interceptor, so a panic here ends the process, and would do so again on every replay of the query.
Functions ¶
func LexicographicallySortableFloat64 ¶ added in v1.30.7
LexicographicallySortableFloat64 transforms a conversion to a lexicographically sortable byte slice. In general, for lexicographical sorting big endian notatino is required. Additionally the sign needs to be flipped in any case, but additionally each remaining byte also needs to be flipped if the number is negative
NaN is unsupported: it does not reliably round-trip (math.NaN() decodes to a finite value) and has no meaningful sort position. Callers must not pass NaN; its equality and range semantics through this encoding are undefined.
func LexicographicallySortableInt64 ¶ added in v1.30.7
LexicographicallySortableInt64 performs a conversion to a lexicographically sortable byte slice. For this, big endian notation is required and the sign must be flipped
func LexicographicallySortableUint64 ¶ added in v1.30.7
LexicographicallySortableUint64 performs a conversion to a lexicographically sortable byte slice. For this, big endian notation is required.
func ParseLexicographicallySortableFloat64 ¶ added in v1.30.7
ParseLexicographicallySortableFloat64 reverses the changes in LexicographicallySortableFloat64
func ParseLexicographicallySortableInt64 ¶ added in v1.30.7
ParseLexicographicallySortableInt64 reverses the changes in LexicographicallySortableInt64
func ParseLexicographicallySortableUint64 ¶ added in v1.30.7
ParseLexicographicallySortableUint64 reverses the changes in LexicographicallySortableUint64
func PutLexicographicallySortableFloat64 ¶ added in v1.38.14
PutLexicographicallySortableFloat64 is the allocation-free variant of LexicographicallySortableFloat64, writing the 8-byte key into dst. dst must be at least 8 bytes; it panics otherwise.
func PutLexicographicallySortableInt64 ¶ added in v1.38.14
PutLexicographicallySortableInt64 is the allocation-free variant of LexicographicallySortableInt64, writing the 8-byte key into dst. dst must be at least 8 bytes; it panics otherwise.
Types ¶
type FixedKeyBuilder ¶ added in v1.38.14
type FixedKeyBuilder struct {
// contains filtered or unexported fields
}
FixedKeyBuilder fills a SortedKeys whose keys are all one width. It records no offsets, since key i is at i*w, and the type is what keeps that true: nothing can append a key of another length to it.
func NewFixedKeyBuilder ¶ added in v1.38.14
func NewFixedKeyBuilder(numKeys, keyWidth int) *FixedKeyBuilder
NewFixedKeyBuilder sizes the slab for numKeys keys of keyWidth bytes each, and panics on invalid arguments.
keyWidth is one key's width, not the batch total — the reverse of NewVarKeyBuilder's argument, and the compiler can't catch the swap. A width above the widest key any family encodes is rejected here, before it silently produces wrong-width keys that would sort and dedup normally.
func (*FixedKeyBuilder) AppendBuf ¶ added in v1.38.14
func (b *FixedKeyBuilder) AppendBuf() []byte
AppendBuf appends a key and returns its zeroed bytes for the encoder to write into directly. The slice is capped at its own end, so writing through it cannot reach the next key.
Valid only until the next append or Build: a buffer held across a slab growth would alias the stale array, and one held across Build would land on whatever key the sort moved into that slot.
func (*FixedKeyBuilder) Build ¶ added in v1.38.14
func (b *FixedKeyBuilder) Build() (SortedKeys, error)
Build orders the keys in place, drops duplicates, and returns the finished list, consuming the builder — see VarKeyBuilder.Build for why.
At one width, key i sits at offset i*w, so ordering moves only the slab and there are no offsets to reorder alongside it — and what lets these keys be radix sorted rather than compared.
type MissingIndexError ¶
type MissingIndexError struct {
// contains filtered or unexported fields
}
func (MissingIndexError) Error ¶
func (e MissingIndexError) Error() string
type SortedKeys ¶ added in v1.38.14
type SortedKeys struct {
// contains filtered or unexported fields
}
SortedKeys is an ascending, immutable list of encoded index keys, held as one slab plus per-key offsets — or a shared width, when keys are all one size — rather than a [][]byte, whose 24-byte headers would outweigh the 8-to-16-byte keys they describe.
Only a builder's Build and SortedKeys.Sub return one, so the order and the absence of duplicates need no re-checking; dropping duplicates means a list can be shorter than what was appended.
The zero value is a valid empty list.
func (SortedKeys) All ¶ added in v1.38.14
func (k SortedKeys) All() iter.Seq2[int, []byte]
All iterates the keys in order, yielding each key's position and bytes, aliasing the slab.
One func literal covers both layouts: separate ones would keep the compiler from devirtualizing the yield, heap-allocating the caller's loop body.
The layout is branched on once, outside the loop, and keys are sliced directly rather than via At, which would add a branch and a redundant range check per key. BenchmarkIterate: 38us vs 159us over 100,000 keys.
func (SortedKeys) At ¶ added in v1.38.14
func (k SortedKeys) At(i int) []byte
At returns key i, aliasing the slab; callers must not modify it. The result's capacity ends at the key itself, so append reallocates rather than overwriting the next key.
Out-of-range panics via the compiler's generated bounds check rather than an explicit one: naming the index and count here costs At its inlining — 271 against an 80 budget, versus 53 without — and At is called per key by readers that need keys out of order. SortedKeys.All reads the slab directly and pays neither cost.
One case the generated check misses: a zero width, where i*0 legally slices to [0:0:0] against any slab. Refused explicitly in the body, or an unbuilt SortedKeys would answer every index with an empty key instead of panicking.
One case neither checks: an index near maxint can wrap i*k.w into a legal range and return the wrong key. No caller holds one — Len bounds every derived index — and guarding it slows [BenchmarkIterate]'s width arm, so this is documented rather than enforced.
func (SortedKeys) FirstAtOrAfter ¶ added in v1.38.14
func (k SortedKeys) FirstAtOrAfter(from, to int, target []byte) int
FirstAtOrAfter returns the first position in [from, to) whose key is at or past target, or to if there is none. It searches a sub-range rather than the whole list, which is what a caller walking two sorted runs past each other needs.
from is a hint, not a bound the answer has to clear: a target already at or before keys[from] answers from.
to is required, not a hint: 0 <= from <= to <= Len(), unchecked. Trimming a range the caller got wrong would answer as if they had got it right.
func (SortedKeys) Len ¶ added in v1.38.14
func (k SortedKeys) Len() int
Len returns the number of keys.
Derived from the backing arrays rather than stored, so it can't drift out of sync with them — callers route on this count.
func (SortedKeys) Sub ¶
func (k SortedKeys) Sub(from, to int) SortedKeys
Sub returns the keys in [from, to) as a list of their own, aliasing this one's storage rather than copying it. 0 <= from <= to <= Len().
The check exists because the slice expressions would otherwise panic with a bare bounds error — and because a zero-width layout slices to an empty list at any index, where they would not panic at all.
type VarKeyBuilder ¶ added in v1.38.14
type VarKeyBuilder struct {
// contains filtered or unexported fields
}
VarKeyBuilder fills a SortedKeys whose keys vary in length, appended in any order; VarKeyBuilder.Build sorts them and rebuilds the slab to match.
The layout isn't chosen by watching appended lengths here — that per-key test would push AppendString past Go's inlining budget.
func NewVarKeyBuilder ¶ added in v1.38.14
func NewVarKeyBuilder(numKeys, totalBytes int) *VarKeyBuilder
NewVarKeyBuilder sizes both arrays up front so neither grows, since a producer knows its key count and total byte length before it starts. It panics on negative arguments.
totalBytes is the batch total, not a per-key width — the reverse of NewFixedKeyBuilder's argument, and the compiler can't catch the swap.
func (*VarKeyBuilder) AppendString ¶ added in v1.38.14
func (b *VarKeyBuilder) AppendString(key string)
AppendString copies a key onto the slab without materializing a []byte for the conversion.
func (*VarKeyBuilder) Build ¶ added in v1.38.14
func (b *VarKeyBuilder) Build() (SortedKeys, error)
Build orders the keys, drops duplicates, and returns the finished list, consuming the builder. Ordering happens here rather than in a separate Sort call, so the invariant SortedKeys promises can't be skipped.
The result can be shorter than the number of appends — duplicates are dropped (see [dedupFixed], [dedupVariable]) — so a caller needing its own count must not substitute this one. Keys that share a width come back without offsets; the sort already scans for that, so it costs nothing extra.
Scratch isn't pooled: measured no faster at any batch size, and pooling would hold a large batch's buffers for the process's lifetime.
Source Files