roaring

package module
v0.22.3 Latest Latest
Warning

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

 Go to latest Published: Apr 17, 2024 License: Apache-2.0 Imports: 17 Imported by: 2

README

roaring

Taken from pilosa and cleaned up

Documentation

Overview

Copyright 2022 Molecula Corp. (DBA FeatureBase). SPDX-License-Identifier: Apache-2.0

Copyright 2022 Molecula Corp. (DBA FeatureBase). SPDX-License-Identifier: Apache-2.0

Copyright 2022 Molecula Corp. (DBA FeatureBase). SPDX-License-Identifier: Apache-2.0

Copyright 2022 Molecula Corp. (DBA FeatureBase). SPDX-License-Identifier: Apache-2.0

Copyright 2022 Molecula Corp. (DBA FeatureBase). SPDX-License-Identifier: Apache-2.0

Copyright 2022 Molecula Corp. (DBA FeatureBase). SPDX-License-Identifier: Apache-2.0

Copyright 2022 Molecula Corp. (DBA FeatureBase). SPDX-License-Identifier: Apache-2.0

Copyright 2022 Molecula Corp. (DBA FeatureBase). SPDX-License-Identifier: Apache-2.0

Copyright 2022 Molecula Corp. (DBA FeatureBase). SPDX-License-Identifier: Apache-2.0 Package roaring implements roaring bitmaps with support for incremental changes.

Copyright 2022 Molecula Corp. (DBA FeatureBase). SPDX-License-Identifier: Apache-2.0

Index

Constants

View Source 
const (
	// MagicNumber is an identifier, in bytes 0-1 of the file.
	MagicNumber = uint32(12348)

	MaxContainerVal = 0xffff
)
View Source 
const (
	ContainerNil    byte = iota // no container
	ContainerArray              // slice of bit position values
	ContainerBitmap             // slice of 1024 uint64s
	ContainerRun                // container of run-encoded bits
)
View Source 
const ArrayMaxSize = 4096

ArrayMaxSize represents the maximum size of array containers.

Variables

View Source 
var ContainerArchetypeNames = []string{
	"Empty",
	"Ary1",
	"Ary16",
	"Ary256",
	"Ary512",
	"Ary1024",
	"Ary4096",
	"RunFull",
	"RunSplit",
	"Run16",
	"Run16Small",
	"Run256",
	"Run256Small",
	"Run1024",
	"BM512",
	"BM1024",
	"BM4096",
	"BM4097",
	"BM32768",
	"BM65000",
}

ContainerArchetypeNames is the list of supported container archetypes used in some testing. This is exported for use in a benchmark-analysis tool.

View Source 
var NewFileBitmap = NewBTreeBitmap

NewFileBitmap returns a Bitmap with an initial set of values, used for file storage.

Functions

func ApplyFilterToIterator 

func ApplyFilterToIterator(filter BitmapFilter, iter ContainerIterator) error

ApplyFilterToIterator is a simplistic implementation that applies a bitmap filter to a ContainerIterator, returning an error if it encounters an error.

This mostly exists for testing purposes; a Tx implementation where generating containers is expensive should almost certainly implement a better way to use filters which only generates data if it needs to.

func ArrayCountRange 

func ArrayCountRange(array []uint16, start, end int32) (n int32)

func AsArray 

func AsArray(c *Container) []uint16

func AsBitmap 

func AsBitmap(c *Container) []uint64

func BinSearchRuns 

func BinSearchRuns(v uint16, a []Interval16) (int32, bool)

BinSearchRuns returns the index of the run containing v, and true, when v is contained; or the index of the next run starting after v, and false, when v is not contained.

func BitmapCountRange 

func BitmapCountRange(bitmap []uint64, start, end int32) int32

BitmapCountRange counts bits set in [start,end).

func BitmapsToRoaring 

func BitmapsToRoaring(bitmaps []*Bitmap) []byte

BitmapsToRoaring renders a series of non-overlapping bitmaps as a unified roaring file.

func CompareBitmapMap 

func CompareBitmapMap(b *Bitmap, vals map[uint64]struct{}) (bool, error)

CompareBitmapMap checks whether a bitmap has the same values in it that a provided map[uint64]struct{} has as keys.

func CompareBitmapSlice 

func CompareBitmapSlice(b *Bitmap, vals []uint64) (bool, error)

CompareBitmapSlice checks whether a bitmap has the same values in it that a provided slice does.

func ContainerCallback 

func ContainerCallback(a *Container, fn func(uint16))

func ContainerType 

func ContainerType(c *Container) byte

func GetMatchingKeysFrom 

func GetMatchingKeysFrom(source []uint64, key uint64) (matching []uint64, remaining []uint64, nextKey uint64)

GetMatchingKeysFrom is a helper function which, given a sorted input list which starts at or above the given key, returns the portion of it matching that key, the remainder, and a next key to check, or ^0 if it's done.

If the list is unsorted, this function does not make much sense, but if the key it's called with is the key of the first element, it will still "work", producing the values matching that key, the remainder, and the next value as expected.

func InitContainerArchetypes 

func InitContainerArchetypes() ([][]*Container, error)

InitContainerArchetypes ensures that createContainerArchetypes has been called, and returns the results of that one call.

func IntersectionAny 

func IntersectionAny(a, b *Container) bool

IntersectionAny checks whether two containers have any overlap without counting past the first bit found.

func IntersectionCount 

func IntersectionCount(x, y *Container) int32

func Merge 

func Merge(a, b []uint16)

func NewRepeatedRowContainerIterator 

func NewRepeatedRowContainerIterator(iter ContainerIterator) *repeatedRowIterator

NewRepeatedRowContainerIterator returns a ContainerIterator which reads the first "row" of containers out of iter (as determined by shard width, so up to and including key 15 by default). It then returns a ContainerIterator which will repeatedly emit the containers in that row, but with increasing keys such that each time a particular container is emitted it has its key from the last time plus number of containers in a row (16 by default).

func RunCountRange 

func RunCountRange(runs []Interval16, start, end int32) (n int32)

RunCountRange returns the ranged bit count for RLE pairs.

Types

type AdvisoryError 

type AdvisoryError interface {
	error
	AdvisoryOnly()
}

AdvisoryError is used for the special case where we probably want to *report* an error reading a file, but don't want to actually count the file as not being read. For instance, a partial ops-log entry is *probably* harmless; we probably crashed while writing (?) and as such didn't report the write as successful. We hope.

type Bitmap 

type Bitmap struct {
	Containers Containers

	// User-defined flags.
	Flags byte

	// Writer where operations are appended to.
	OpWriter io.Writer
	// contains filtered or unexported fields
}

Bitmap represents a roaring bitmap.

func Add 

func Add(x, y []*Bitmap) []*Bitmap

Add two BSI bitmaps producing a new BSI bitmap.

func InspectBinary 

func InspectBinary(data []byte, mapped bool, info *BitmapInfo) (b *Bitmap, mappedAny bool, err error)

InspectBinary reads a roaring bitmap, plus a possible ops log, and reports back on the contents, including distinguishing between the original ops log and the post-ops-log contents.

func NewBTreeBitmap 

func NewBTreeBitmap(a ...uint64) *Bitmap

func NewBitMatrix 

func NewBitMatrix(shardWidth uint64, rows ...[]uint64) *Bitmap

NewBitMatrix is a convenience function which returns a new bitmap which is the concatenation of all the rows, with each row shifted by a shardwdith. For example, all values in the second row will have shardWidth added to them before being added to the bitmap. Modifies rows in place.

func NewBitmap 

func NewBitmap(a ...uint64) *Bitmap

NewBitmap returns a Bitmap with an initial set of values.

func NewSliceBitmap 

func NewSliceBitmap(a ...uint64) *Bitmap

NewSliceBitmap makes a new bitmap, explicitly selecting the slice containers type, which performs better in cases where we expect a contiguous block of containers added in ascending order, such as when extracting a range from another bitmap.

func RoaringToBitmaps 

func RoaringToBitmaps(data []byte, shardWidth uint64) ([]*Bitmap, []uint64)

RoaringToBitmaps yields a series of bitmaps with specified shard keys, based on a single roaring file, with splits at multiples of shardWidth, which should be a multiple of container size.

func (*Bitmap) Add 

func (b *Bitmap) Add(a ...uint64) (changed bool, err error)

Add adds values to the bitmap. TODO(2.0) deprecate - use the more general AddN (though be aware that it modifies 'a' in place).

func (*Bitmap) AddN 

func (b *Bitmap) AddN(a ...uint64) (changed int, err error)

AddN adds values to the bitmap, appending them all to the op log in a batched write. It returns the number of changed bits. The input slice may be reordered, and the set of changed bits will end up in a[:changed].

func (*Bitmap) Any 

func (b *Bitmap) Any() bool

Any checks whether there are any set bits within the bitmap.

func (*Bitmap) AsContainerMatrixString 

func (b *Bitmap) AsContainerMatrixString() (r string)

AsContainerMatrixString returns a string showing the matrix of rows in a shard, showing the count of hot (1) bits in each container.

func (*Bitmap) BitwiseEqual 

func (b *Bitmap) BitwiseEqual(c *Bitmap) (bool, error)

BitwiseEqual is used mostly in test cases to confirm that two bitmaps came out the same. It does not expect corresponding opN, or OpWriter, but expects identical bit contents. It does not expect identical representations; a bitmap container can be identical to an array container. It returns a boolean value, and also an explanation for a false value.

func (*Bitmap) Check 

func (b *Bitmap) Check() error

Check performs a consistency check on the bitmap. Returns nil if consistent.

func (*Bitmap) Clone 

func (b *Bitmap) Clone() *Bitmap

Clone returns a heap allocated copy of the bitmap. Note: The OpWriter IS NOT copied to the new bitmap.

func (*Bitmap) Contains 

func (b *Bitmap) Contains(v uint64) bool

Contains returns true if v is in the bitmap.

func (*Bitmap) Count 

func (b *Bitmap) Count() (n uint64)

Count returns the number of bits set in the bitmap.

func (*Bitmap) CountRange 

func (b *Bitmap) CountRange(start, end uint64) (n uint64)

CountRange returns the number of bits set between [start, end).

func (*Bitmap) Difference 

func (b *Bitmap) Difference(other ...*Bitmap) *Bitmap

Difference returns the difference of b and other.

func (*Bitmap) DifferenceInPlace 

func (b *Bitmap) DifferenceInPlace(others ...*Bitmap)

DifferenceInPlace returns the bitwise difference of b and others, modifying b in place.

func (*Bitmap) DirectAdd 

func (b *Bitmap) DirectAdd(v uint64) bool

DirectAdd adds a value to the bitmap by bypassing the op log. TODO(2.0) deprecate in favor of DirectAddN.

func (*Bitmap) DirectAddN 

func (b *Bitmap) DirectAddN(a ...uint64) (changed int)

DirectAddN sets multiple bits in the bitmap, returning how many changed. It modifies the slice 'a' in place such that once it's complete a[:changed] will be list of changed bits. It is more efficient than repeated calls to DirectAdd for semi-dense sorted data because it reuses the container from the previous value if the new value has the same highbits instead of looking it up each time. TODO: if Containers implementations cached the last few Container objects returned from calls like Get and GetOrCreate, this optimization would be less useful.

func (*Bitmap) DirectRemoveN 

func (b *Bitmap) DirectRemoveN(a ...uint64) (changed int)

DirectRemoveN behaves analgously to DirectAddN.

func (*Bitmap) Flip 

func (b *Bitmap) Flip(start, end uint64) *Bitmap

Flip performs a logical negate of the bits in the range [start,end].

func (*Bitmap) ForEach 

func (b *Bitmap) ForEach(fn func(uint64) error) error

ForEach executes fn for each value in the bitmap.

func (*Bitmap) ForEachRange 

func (b *Bitmap) ForEachRange(start, end uint64, fn func(uint64) error) error

ForEachRange executes fn for each value in the bitmap between [start, end).

func (*Bitmap) Freeze 

func (b *Bitmap) Freeze() *Bitmap

Freeze returns a shallow copy of the bitmap. The new bitmap is a distinct bitmap, with a new Containers object, but the actual containers it holds are the same as the parent's containers, but have been frozen.

func (*Bitmap) Hash 

func (b *Bitmap) Hash(hash uint64) uint64

func (*Bitmap) ImportRoaringBits 

func (b *Bitmap) ImportRoaringBits(data []byte, clear bool, log bool, rowSize uint64) (changed int, rowSet map[uint64]int, err error)

ImportRoaringBits sets-or-clears bits based on a provided Roaring bitmap. This should be equivalent to unmarshalling the bitmap, then executing either `b = Union(b, newB)` or `b = Difference(b, newB)`, but with lower overhead. The log parameter controls whether to write to the op log; the answer should always be yes, except if you're calling using this to apply the op log.

If rowSize is non-zero, we should return a map of rows we altered, where "rows" are sets of rowSize containers. Otherwise the map isn't used. (This allows ImportRoaring to update caches; see fragment.go.)

func (*Bitmap) ImportRoaringRawIterator 

func (b *Bitmap) ImportRoaringRawIterator(itr RoaringIterator, clear bool, log bool, rowSize uint64) (changed int, rowSet map[uint64]int, err error)

func (*Bitmap) Info 

func (b *Bitmap) Info(includeContainers bool) BitmapInfo

Info returns stats for the bitmap.

func (*Bitmap) Intersect 

func (b *Bitmap) Intersect(other *Bitmap) *Bitmap

Intersect returns the intersection of b and other.

func (*Bitmap) IntersectInPlace 

func (b *Bitmap) IntersectInPlace(others ...*Bitmap)

IntersectInPlace returns the bitwise intersection of b and others, modifying b in place.

func (*Bitmap) IntersectionCount 

func (b *Bitmap) IntersectionCount(other *Bitmap) uint64

IntersectionCount returns the number of set bits that would result in an intersection between b and other. It is more efficient than actually intersecting the two and counting the result.

func (*Bitmap) Iterator 

func (b *Bitmap) Iterator() *Iterator

Iterator returns a new iterator for the bitmap.

func (*Bitmap) IteratorAt 

func (b *Bitmap) IteratorAt(start uint64) *Iterator

func (*Bitmap) MarshalBinary 

func (b *Bitmap) MarshalBinary() ([]byte, error)

func (*Bitmap) Max 

func (b *Bitmap) Max() uint64

Max returns the highest value in the bitmap. Returns zero if the bitmap is empty.

func (*Bitmap) MergeRoaringRawIteratorIntoExists 

func (b *Bitmap) MergeRoaringRawIteratorIntoExists(itr RoaringIterator, rowSize uint64) error

MergeRoaringRawIteratorIntoExists is a special merge iterator that flattens the results onto a single row which is used for determining existence. All row references are removed and only the column is considered.

func (*Bitmap) Min 

func (b *Bitmap) Min() (uint64, bool)

Min returns the lowest value in the bitmap. Second return value is true if containers exist in the bitmap.

func (*Bitmap) MinAt 

func (b *Bitmap) MinAt(start uint64) (uint64, bool)

MinAt returns the lowest value in the bitmap at least equal to its argument. Second return value is true if containers exist in the bitmap.

func (*Bitmap) OffsetRange 

func (b *Bitmap) OffsetRange(offset, start, end uint64) *Bitmap

OffsetRange returns a new bitmap with a containers offset by start. The containers themselves are shared, so they get frozen so it will be safe to interact with them.

func (*Bitmap) Ops 

func (b *Bitmap) Ops() (ops int, opN int)

Ops returns the number of write ops the bitmap is aware of in its ops log, and their total bit count.

func (*Bitmap) Optimize 

func (b *Bitmap) Optimize()

Optimize converts array and bitmap containers to run containers as necessary.

func (*Bitmap) PreferMapping 

func (b *Bitmap) PreferMapping(preferred bool)

func (*Bitmap) Put 

func (b *Bitmap) Put(key uint64, c *Container)

func (*Bitmap) RemapRoaringStorage 

func (b *Bitmap) RemapRoaringStorage(data []byte) (mappedAny bool, returnErr error)

RemapRoaringStorage tries to update all containers to refer to the roaring bitmap in the provided []byte. If any containers are marked as mapped, but do not match the provided storage, they will be unmapped. The boolean return indicates whether or not any containers were mapped to the given storage.

Regardless, after this function runs, no containers have mapped storage which does not refer to data; either they got mapped to the new storage, or storage was allocated for them.

func (*Bitmap) Remove 

func (b *Bitmap) Remove(a ...uint64) (changed bool, err error)

Remove removes values from the bitmap (writing to the op log if available). TODO(2.0) deprecate - use the more general RemoveN (though be aware that it modifies 'a' in place).

func (*Bitmap) RemoveN 

func (b *Bitmap) RemoveN(a ...uint64) (changed int, err error)

RemoveN behaves analagously to AddN.

func (*Bitmap) Roaring 

func (b *Bitmap) Roaring() []byte

Roaring encodes the bitmap in the Pilosa roaring format. Convenience wrapper around WriteTo.

func (*Bitmap) SanityCheckMapping 

func (b *Bitmap) SanityCheckMapping(from, to uintptr) (mappedIn int64, mappedOut int64, unmappedIn int64, errs int, err error)

SanityCheckMapping is a debugging function which checks whether containers are *correctly* recorded as mapped or unmapped.

func (*Bitmap) SetOps 

func (b *Bitmap) SetOps(ops int, opN int)

SetOps lets us reset the operation count in the weird case where we know we've changed an underlying file, without actually refreshing the bitmap.

func (*Bitmap) Shift 

func (b *Bitmap) Shift(n int) (*Bitmap, error)

Shift shifts the contents of b by 1.

NOTE: This method is unsupported. See the `Shift()` method on `Row` in `row.go`.

func (*Bitmap) Size 

func (b *Bitmap) Size() int

Size returns the number of bytes required for the bitmap.

func (*Bitmap) Slice 

func (b *Bitmap) Slice() []uint64

Slice returns a slice of all integers in the bitmap.

func (*Bitmap) SliceRange 

func (b *Bitmap) SliceRange(start, end uint64) []uint64

SliceRange returns a slice of integers between [start, end).

func (*Bitmap) String 

func (b *Bitmap) String() (r string)

func (*Bitmap) Union 

func (b *Bitmap) Union(others ...*Bitmap) *Bitmap

Union returns the bitwise union of b and others as a new bitmap.

func (*Bitmap) UnionInPlace 

func (b *Bitmap) UnionInPlace(others ...*Bitmap)

UnionInPlace returns the bitwise union of b and others, modifying b in place.

func (*Bitmap) UnmarshalBinary 

func (b *Bitmap) UnmarshalBinary(data []byte) (err error)

UnmarshalBinary reads Pilosa's format, or upstream roaring (mostly; it may not handle some edge cases), and decodes them into the given bitmap, replacing the existing contents.

func (*Bitmap) WriteTo 

func (b *Bitmap) WriteTo(w io.Writer) (n int64, err error)

WriteTo writes b to w.

func (*Bitmap) Xor 

func (b *Bitmap) Xor(other *Bitmap) *Bitmap

Xor returns the bitwise exclusive or of b and other.

type BitmapBSICountFilter 

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

BitmapBSICountFilter gives counts of values in each value-holding row of a BSI field, constrained by a filter. The first row of the data is taken to be an existence bit, which is intersected into the filter to constrain it, and the second is used as a sign bit. The rows after that are treated as value rows, and their counts of bits, overlapping with positive and negative bits in the sign rows, are returned to a callback function.

The total counts of positions evaluated are returned with a row count of ^uint64(0) prior to row counts.

func NewBitmapBSICountFilter 

func NewBitmapBSICountFilter(filter *Bitmap) *BitmapBSICountFilter

NewBitmapBSICountFilter creates a BitmapBSICountFilter, used for tasks like computing the sum of a BSI field matching a given filter.

The input filter is assumed to represent one "row" of a shard's data, which is to say, a range of up to rowWidth consecutive containers starting at some multiple of rowWidth. We coerce that to the 0..rowWidth range because offset-within-row is what we care about.

func (*BitmapBSICountFilter) ConsiderData 

func (b *BitmapBSICountFilter) ConsiderData(key FilterKey, data *Container) FilterResult

func (*BitmapBSICountFilter) ConsiderKey 

func (b *BitmapBSICountFilter) ConsiderKey(key FilterKey, n int32) FilterResult

func (*BitmapBSICountFilter) Total 

func (b *BitmapBSICountFilter) Total() (count int32, total int64)

type BitmapBitmapFilter 

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

BitmapBitmapFilter builds a list of positions in the bitmap which match those in a provided bitmap. It is shard-agnostic; no matter what offsets the input bitmap's containers have, it matches them against corresponding keys.

func NewBitmapBitmapFilter 

func NewBitmapBitmapFilter(filter *Bitmap, callback func(uint64) error) *BitmapBitmapFilter

NewBitmapBitmapFilter creates a filter which can report all the positions within a bitmap which are set, and which have positions corresponding to the specified columns. It calls the provided callback function on each value it finds, terminating early if that returns an error.

The input filter is assumed to represent one "row" of a shard's data, which is to say, a range of up to rowWidth consecutive containers starting at some multiple of rowWidth. We coerce that to the 0..rowWidth range because offset-within-row is what we care about.

func (*BitmapBitmapFilter) ConsiderData 

func (b *BitmapBitmapFilter) ConsiderData(key FilterKey, data *Container) FilterResult

func (*BitmapBitmapFilter) ConsiderKey 

func (b *BitmapBitmapFilter) ConsiderKey(key FilterKey, n int32) FilterResult

func (*BitmapBitmapFilter) SetCallback 

func (b *BitmapBitmapFilter) SetCallback(cb func(uint64) error)

type BitmapBitmapTrimmer 

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

BitmapBitmapTrimmer is like BitmapBitmapFilter, but instead of calling a callback per bit found in the intersection, it calls a callback with the original raw container and the corresponding filter container, and also provides the writeback func it got from the bitmap. So for instance, to implement a "subtract these bits" function, you would difference-in-place the raw container with the filter container, then pass that to the writeback function.

It's called a Trimmer because it won't add containers; it won't *add* containers. It calls the callback function for every container, whether or not it matches the filter; this allows an intersect-like filter to work too.

Note, however, that the caller's ContainerWriteback function *may* create containers, even though the Trimmer won't have called RewriteData with those keys.

func NewBitmapBitmapTrimmer 

func NewBitmapBitmapTrimmer(filter *Bitmap, callback func(FilterKey, *Container, *Container, ContainerWriteback) error) *BitmapBitmapTrimmer

NewBitmapBitmapTrimmer creates a filter which calls a callback on every container in a bitmap, with corresponding elements from an initial filter bitmap. It does not call its callback for cases where there's no container in the original bitmap.

The input filter is assumed to represent one "row" of a shard's data, which is to say, a range of up to rowWidth consecutive containers starting at some multiple of rowWidth. We coerce that to the 0..rowWidth range because offset-within-row is what we care about.

func (*BitmapBitmapTrimmer) ConsiderKey 

func (b *BitmapBitmapTrimmer) ConsiderKey(key FilterKey, n int32) FilterResult

func (*BitmapBitmapTrimmer) RewriteData 

func (b *BitmapBitmapTrimmer) RewriteData(key FilterKey, data *Container, writeback ContainerWriteback) FilterResult

func (*BitmapBitmapTrimmer) SetCallback 

func (b *BitmapBitmapTrimmer) SetCallback(cb func(FilterKey, *Container, *Container, ContainerWriteback) error)

type BitmapColumnFilter 

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

BitmapColumnFilter is a BitmapFilter which checks for containers matching a given column within a row; thus, only the one container per row which matches the column needs to be evaluated, and it's evaluated as matching if it contains the relevant bit.

func (*BitmapColumnFilter) ConsiderData 

func (f *BitmapColumnFilter) ConsiderData(key FilterKey, data *Container) FilterResult

func (*BitmapColumnFilter) ConsiderKey 

func (f *BitmapColumnFilter) ConsiderKey(key FilterKey, n int32) FilterResult

type BitmapFilter 

type BitmapFilter interface {
	ConsiderKey(key FilterKey, n int32) FilterResult
	ConsiderData(key FilterKey, data *Container) FilterResult
}

BitmapFilter is, given a series of key/data pairs, considered to "match" some of those containers. Matching may be dependent on key values and cardinalities alone, or on the contents of the container.

The ConsiderData function must not retain the container, or the data from the container; if it needs access to that information later, it needs to make a copy.

Many filters are, by virtue of how they operate, able to predict their results on future keys. To accommodate this, and allow operations to avoid processing keys they don't need to process, the result of a filter operation can indicate not just whether a given key matches, but whether some upcoming keys will, or won't, match. If ConsiderKey yields a non-zero number of matches or non-matches for a given key, ConsiderData will not be called for that key.

If multiple filters are combined, they are only called if their input is needed to determine a value.

func NewBitmapColumnFilter 

func NewBitmapColumnFilter(col uint64) BitmapFilter

func NewBitmapRowFilter 

func NewBitmapRowFilter(callback func(uint64) error, filters ...BitmapFilter) BitmapFilter

BitmapRowLister returns a pointer to a slice which it will populate when invoked as a bitmap filter.

func NewBitmapRowFilterMultiFilter 

func NewBitmapRowFilterMultiFilter(callback func(row uint64) error, filters ...BitmapFilter) BitmapFilter

BitmapRowFilterMultiFilter will call a

func NewBitmapRowsFilter 

func NewBitmapRowsFilter(rows []uint64) BitmapFilter

type BitmapInfo 

type BitmapInfo struct {
	OpN            int
	Ops            int
	OpDetails      []OpInfo `json:"OpDetails,omitempty"`
	BitCount       uint64
	ContainerCount int
	Containers     []ContainerInfo `json:"Containers,omitempty"`   // The containers found in the bitmap originally
	OpContainers   []ContainerInfo `json:"OpContainers,omitempty"` // The containers resulting from ops log changes.
	From, To       uintptr         // if set, indicates the address range used when unpacking
}

BitmapInfo represents a point-in-time snapshot of bitmap stats.

type BitmapMutexDupFilter 

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

BitmapMutexDupFilter is a filter which identifies cases where the same position has a bit set in more than one row.

We keep a slice of the first value seen for every row, with ^0 as the default; when that's already set, things get appended to the entries in the map. At the end, for each entry in the map, we also add its first value to it. Thus, the map holds all the entries, but we're only using the map in the (hopefully rarer) cases where there's duplicate values.

The slice is local-coordinates (first column 0), but the map is global coordinates (first column is whatever base was).

func NewBitmapMutexDupFilter 

func NewBitmapMutexDupFilter(base uint64, details bool, limit int) *BitmapMutexDupFilter

func (*BitmapMutexDupFilter) ConsiderData 

func (b *BitmapMutexDupFilter) ConsiderData(key FilterKey, data *Container) FilterResult

func (*BitmapMutexDupFilter) ConsiderKey 

func (b *BitmapMutexDupFilter) ConsiderKey(key FilterKey, n int32) FilterResult

func (*BitmapMutexDupFilter) Report 

func (b *BitmapMutexDupFilter) Report() map[uint64][]uint64

Report returns the set of duplicate values identified.

type BitmapRangeFilter 

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

BitmapRangeFilter limits filter operations to a specified range, and performs key or data callbacks.

On seeing a key in its range: If the key callback is present, and returns true, match the key. Otherwise, if a data callback is present, request the data, and in the data handler, call the data callback, then match the single key. If neither is present, match the entire range at once.

func NewBitmapRangeFilter 

func NewBitmapRangeFilter(min, max FilterKey, keyCallback func(FilterKey, int32) (bool, error), dataCallback func(FilterKey, *Container) error) *BitmapRangeFilter

func (*BitmapRangeFilter) ConsiderData 

func (b *BitmapRangeFilter) ConsiderData(key FilterKey, data *Container) FilterResult

func (*BitmapRangeFilter) ConsiderKey 

func (b *BitmapRangeFilter) ConsiderKey(key FilterKey, n int32) FilterResult

type BitmapRewriter 

type BitmapRewriter interface {
	ConsiderKey(key FilterKey, n int32) FilterResult
	RewriteData(key FilterKey, data *Container, writeback ContainerWriteback) FilterResult
}

A BitmapRewriter is like a bitmap filter, but can modify the bitmap it's being called on during the iteration.

After the last container is returned, ConsiderData will be called with an unspecified key and a nil container pointer, so the rewriter can write any trailing containers it has. A nil container passed to writeback implies a delete operation on the container. Writeback should only be called with keys greater than any previously given container key, and less than or equal to the current key. So for instance, if ConsiderData is called with key 3, and then with key 5, the call with key 5 may call writeback with key 4, and then key 5, but may not call it with keys 3 or lower, or 6 or higher. When the container provided to the call is nil, any monotonically increasing keys greater than the previous key are allowed. (If there was no previous key, 0 and higher are allowed.)

type BitmapRowFilterBase 

type BitmapRowFilterBase struct {
	FilterResult
	// contains filtered or unexported fields
}

BitmapRowFilterBase is a generic form of a row-aware wrapper; it handles making decisions about keys once you tell it a yesKey and noKey that it should be using, and makes callbacks per row.

func NewBitmapRowFilterBase 

func NewBitmapRowFilterBase(callback func(row uint64) error) *BitmapRowFilterBase

func (*BitmapRowFilterBase) ConsiderData 

func (b *BitmapRowFilterBase) ConsiderData(key FilterKey, data *Container) FilterResult

This should probably never be reached?

func (*BitmapRowFilterBase) ConsiderKey 

func (b *BitmapRowFilterBase) ConsiderKey(key FilterKey, n int32) FilterResult

Without a sub-filter, we always-succeed; if we get a key that isn't already answered by our YesKey/NoKey/lastRow, we will match this key, reject the rest of the row, and update our keys accordingly. We'll also hit the callback, and return an error from it if appropriate.

func (*BitmapRowFilterBase) DetermineByKey 

func (b *BitmapRowFilterBase) DetermineByKey(key FilterKey) (FilterResult, bool)

DetermineByKey decides whether it can produce a meaningful FilterResult for a given key. This encapsulates all the logic for row callbacks and figuring out when to wrap a row.

func (*BitmapRowFilterBase) SetResult 

func (b *BitmapRowFilterBase) SetResult(key FilterKey, result FilterResult) FilterResult

SetResult is a convenience function so that things embedding this can just call this instead of using a long series of dotted names. It returns the new result of DetermineByKey after this change.

type BitmapRowFilterMultiFilter 

type BitmapRowFilterMultiFilter struct {
	BitmapRowFilterBase
	// contains filtered or unexported fields
}

BitmapRowFilterMultiFilter is a BitmapFilter which wraps other bitmap filters, calling a callback function once per row whenever it finds a container for which all the filters returned true.

func (*BitmapRowFilterMultiFilter) ConsiderData 

func (b *BitmapRowFilterMultiFilter) ConsiderData(key FilterKey, data *Container) FilterResult

ConsiderData only gets called in cases where f.toDo had a list of filters for which we needed to get data to make a decision. That means that everything but the indexes in f.toDo must be a "yes" right now.

func (*BitmapRowFilterMultiFilter) ConsiderKey 

func (b *BitmapRowFilterMultiFilter) ConsiderKey(key FilterKey, n int32) FilterResult

type BitmapRowFilterSingleFilter 

type BitmapRowFilterSingleFilter struct {
	BitmapRowFilterBase
	// contains filtered or unexported fields
}

BitmapRowFilterSingleFilter is a row iterator with a single filter, which is simpler than one with multiple filters where it coincidentally turns out that N==1.

func NewBitmapRowFilterSingleFilter 

func NewBitmapRowFilterSingleFilter(callback func(row uint64) error, filter BitmapFilter) *BitmapRowFilterSingleFilter

func (*BitmapRowFilterSingleFilter) ConsiderData 

func (b *BitmapRowFilterSingleFilter) ConsiderData(key FilterKey, data *Container) FilterResult

func (*BitmapRowFilterSingleFilter) ConsiderKey 

func (b *BitmapRowFilterSingleFilter) ConsiderKey(key FilterKey, n int32) FilterResult

type BitmapRowLimitFilter 

type BitmapRowLimitFilter struct {
	BitmapRowFilterBase
	// contains filtered or unexported fields
}

func NewBitmapRowLimitFilter 

func NewBitmapRowLimitFilter(limit uint64) *BitmapRowLimitFilter

func (*BitmapRowLimitFilter) ConsiderData 

func (b *BitmapRowLimitFilter) ConsiderData(key FilterKey, data *Container) FilterResult

This should probably never be reached?

func (*BitmapRowLimitFilter) ConsiderKey 

func (b *BitmapRowLimitFilter) ConsiderKey(key FilterKey, n int32) FilterResult

Without a sub-filter, we always-succeed; if we get a key that isn't already answered by our YesKey/NoKey/lastRow, we will match the whole row.

type BitmapRowsFilter 

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

BitmapRowsFilter is a BitmapFilter which checks for containers that are in any of a provided list of rows. The row list should be sorted.

func (*BitmapRowsFilter) ConsiderData 

func (f *BitmapRowsFilter) ConsiderData(key FilterKey, data *Container) FilterResult

func (*BitmapRowsFilter) ConsiderKey 

func (f *BitmapRowsFilter) ConsiderKey(key FilterKey, n int32) FilterResult

type BitmapRowsUnion 

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

BitmapRowsUnion is a BitmapFilter which produces a union of all the rows listed in a []uint64.

func NewBitmapRowsUnion 

func NewBitmapRowsUnion(rows []uint64) *BitmapRowsUnion

NewBitmapRowsUnion yields a BitmapRowsUnion which can give you the union of all containers matching a given row.

func (*BitmapRowsUnion) ConsiderData 

func (f *BitmapRowsUnion) ConsiderData(key FilterKey, data *Container) FilterResult

func (*BitmapRowsUnion) ConsiderKey 

func (f *BitmapRowsUnion) ConsiderKey(key FilterKey, n int32) FilterResult

func (*BitmapRowsUnion) Reset 

func (f *BitmapRowsUnion) Reset()

Reset the internal container buffer. You must use this before reusing a filter.

func (*BitmapRowsUnion) Results 

func (f *BitmapRowsUnion) Results(shard uint64) *Bitmap

Yield the bitmap containing our results, adjusted for a particular shard if necessary (because we expect the results to correspond to our shard ID).

type ClearAndSetRewriter 

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

ClearAndSetRewriter is a BitmapRewriter which can operate on two ContainerIterators, clearing bits from one and setting bits from the other. It tries to do this pretty efficiently such that it doesn't look at the clear iterator unless there is actually a container that might need bits cleared, and it doesn't write a container unless bits have actually changed.

func NewClearAndSetRewriter 

func NewClearAndSetRewriter(clear, set ContainerIterator) (*ClearAndSetRewriter, error)

NewClearAndSetRewriter instantiates a ClearAndSetRewriter

func (*ClearAndSetRewriter) ConsiderKey 

func (csr *ClearAndSetRewriter) ConsiderKey(key FilterKey, n int32) FilterResult

func (*ClearAndSetRewriter) RewriteData 

func (csr *ClearAndSetRewriter) RewriteData(key FilterKey, data *Container, writeback ContainerWriteback) FilterResult

type Container 

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

Container represents a Container for uint16 integers.

These are used for storing the low bits of numbers in larger sets of uint64. The high bits are stored in a Container's key which is tracked by a separate data structure. Integers in a Container can be encoded in one of three ways - the encoding used is usually whichever is most compact, though any Container type should be able to encode any set of integers safely. For containers with less than 4,096 values, an array is often used. Containers with long runs of integers would use run length encoding, and more random data usually uses bitmap encoding.

The Container type has somewhat magical semantics. Containers can be marked as "frozen" by the Freeze method, after which, nothing should ever modify that specific container object again, no matter what. Because of this, but also sometimes for Even More Esoteric Reasons, *no* container method should ever be assumed to be genuinely modifying the container it was called on, and *every* container method that might modify a container should return the "modified" *Container, which *may point to a different object*. The caller should always use this resulting container, and if you're storing a *Container in a data structure, you need to update the data structure's pointer too.

A nil *Container is a valid empty container.

In general, operations on containers which produce new containers *may* yield new containers, and *may* yield their operands.

The reason for all of this is to allow containers to have copy-on-write semantics, which allow us to reduce memory usage dramatically, and GC load even more dramatically.

func ConvertArrayToBitmap 

func ConvertArrayToBitmap(c *Container) *Container

func ConvertRunToBitmap 

func ConvertRunToBitmap(c *Container) *Container

func Difference 

func Difference(a, b *Container) *Container

func Intersect 

func Intersect(x, y *Container) *Container

func NewContainer 

func NewContainer() *Container

NewContainer returns a new instance of container. This trivial function may later become more interesting.

func NewContainerArray 

func NewContainerArray(set []uint16) *Container

NewContainerArray returns an array container using the provided set of values. It's okay if the slice is nil; that's a length of zero.

func NewContainerArrayCopy 

func NewContainerArrayCopy(set []uint16) *Container

NewContainerArrayCopy returns an array container using the provided set of values. It's okay if the slice is nil; that's a length of zero. It copies the provided slice to new storage.

func NewContainerArrayN 

func NewContainerArrayN(set []uint16, n int32) *Container

NewContainerArrayN returns an array container using the specified set of values, but overriding n. This is deprecated. It never worked in the first place. The provided value of n is ignored and instead derived from the set length.

func NewContainerBitmap 

func NewContainerBitmap(n int, bitmap []uint64) *Container

NewContainerBitmap makes a bitmap container using the provided bitmap, or an empty one if provided bitmap is nil. If the provided bitmap is too short, it will be padded. This function's API is wrong; it should have been written as NewContainerBitmapN, and this should not take the n argument, but I did it wrong initially and now that would be a breaking change.

func NewContainerBitmapN 

func NewContainerBitmapN(bitmap []uint64, n int32) *Container

NewContainerBitmapN makes a bitmap container using the provided bitmap, or an empty one if provided bitmap is nil. If the provided bitmap is too short, it will be padded. The container's count is specified directly.

func NewContainerRun 

func NewContainerRun(set []Interval16) *Container

NewContainerRun creates a new run container using a provided (possibly nil) slice of intervals.

func NewContainerRunCopy 

func NewContainerRunCopy(set []Interval16) *Container

NewContainerRunCopy creates a new run container using a provided (possibly nil) slice of intervals. It copies the provided slice to new storage.

func NewContainerRunN 

func NewContainerRunN(set []Interval16, n int32) *Container

NewContainerRunN creates a new run array using a provided (possibly nil) slice of intervals. It overrides n using the provided value.

func Optimize 

func Optimize(c *Container) *Container

Optimize yields a container with the same bits as c, but adjusted to the smallest-storage type by Roaring rules (thus, runs where that's smaller, otherwise arrays for N < 4096 and bitmaps for N >= 4096).

func RemakeContainerArray 

func RemakeContainerArray(c *Container, array []uint16) *Container

RemakeContainerArray populates c with an array container using the provided array. It must not be used on a frozen container.

func RemakeContainerBitmap 

func RemakeContainerBitmap(c *Container, bitmap []uint64) *Container

RemakeContainerBitmap overwrites the contents of c, which must not be frozen, with a provided bitmap, and computes a correct N.

func RemakeContainerBitmapN 

func RemakeContainerBitmapN(c *Container, bitmap []uint64, n int32) *Container

RemakeContainerBitmapN uses the provided n instead of counting bits. The provided container must not be frozen.

func RemakeContainerFrom 

func RemakeContainerFrom(c *Container, source []uint64) (result *Container)

RemakeContainerFrom takes an input list of uint64, and an existing container, and remakes the container using those values.

For lists of values under 4,080 (the RBF cutoff for array size), we just smash values into a type-punned []uint16 backed by the corresponding portion of source. For larger values, we shuffle data into the []uint16 until we have enough extra space to do a 1024-word bitmap, then populate that bitmap.

DANGER: RemakeContainerFrom *overwrites its inputs* to avoid allocation. For array containers, it scribbles uint16 values over the initial period of source. For bitmaps, it scribbles some uint16 values to free up space, then makes a bitmap container in the middle of source. The parts of the source slice that are not returned may have been arbitrarily overwritten and may be getting used in containers. You should not look at the original slice again, and you should not write to that storage.

If overwriting the input data is a problem, don't use this, or make a fresh copy of the input to use it on. If being unable to write to the input data later is a problem, clone the containers this returns so they have their own storage.

The input should be sorted, but if it's not, this will still work at some performance penalty.

func RemakeContainerRun 

func RemakeContainerRun(c *Container, intervals []Interval16) *Container

RemakeContainerRun repopulates c with the provided intervals. c must not be frozen.

func RemakeContainerRunN 

func RemakeContainerRunN(c *Container, intervals []Interval16, n int32) *Container

RemakeContainerRunN repopulates c with the provided intervals, but assumes the provided n is accurate. c must not be frozen.

func Union 

func Union(a, b *Container) (c *Container)

func (*Container) Add 

func (c *Container) Add(v uint16) (newC *Container, added bool)

Add yields a container identical to c, but with the given bit set; added is true if the bit wasn't previously set. It is unspecified whether the original container is modified.

func (*Container) AsBitmap 

func (c *Container) AsBitmap(target []uint64) (out []uint64)

AsBitmap yields a 65k-bit bitmap, storing it in the target if a target is provided. The target should be zeroed, or this becomes an implicit union.

func (*Container) BitwiseCompare 

func (c *Container) BitwiseCompare(c2 *Container) error

BitwiseCompare reports whether two containers are equal. It returns an error describing any difference it finds. This is mostly intended for use in tests that expect equality.

func (*Container) CheckN 

func (c *Container) CheckN()

CheckN verifies that a container's cached count is correct, but there are two versions; this is the one which doesn't actually do anything, because the check is expensive. Which one you get is controlled by the roaringparanoia build tag.

func (*Container) Clone 

func (c *Container) Clone() (out *Container)

Clone returns a copy of c.

func (*Container) Contains 

func (c *Container) Contains(v uint16) bool

Contains returns true if v is in the container.

func (*Container) CountRange 

func (c *Container) CountRange(start, end int32) (n int32)

func (*Container) Difference 

func (c *Container) Difference(other *Container) *Container

func (*Container) DifferenceInPlace 

func (c *Container) DifferenceInPlace(other *Container) *Container

func (*Container) Freeze 

func (c *Container) Freeze() *Container

Freeze returns an unmodifiable container identical to c. This might be c, now marked unmodifiable, or might be a new container. If c is currently marked as "mapped", referring to a backing store that's not a conventional Go pointer, the storage may (or may not) be copied. Do not call Freeze on a temporarily-corrupt container, such as one returned from UnionInPlace but on which you haven't since called Repair.

func (*Container) Mapped 

func (c *Container) Mapped() bool

Mapped returns the internal mapped field, which indicates whether the slice's backing store is believed to be associated with unwriteable mmapped space.

func (*Container) Max 

func (c *Container) Max() uint16

func (*Container) N 

func (c *Container) N() int32

N returns the 1-count of the container.

func (*Container) Remove 

func (c *Container) Remove(v uint16) (c2 *Container, removed bool)

Add yields a container identical to c, but with the given bit cleared; removed is true if the bit was previously set. It is unspecified whether the original container is modified.

func (*Container) Repair 

func (c *Container) Repair()

Repair repairs the cardinality of c if it has been corrupted by optimized operations.

func (*Container) SafeN 

func (c *Container) SafeN() (int32, bool)

SafeN returns N, true if it can, otherwise it returns 0, false. For instance, a container subject to in-place operations can not know its current N, and it's not meaningful or safe to query it until a repair, so you can use this to get N "if it's available".

func (*Container) SetMapped 

func (c *Container) SetMapped(mapped bool)

SetMapped marks a container as "mapped"; do this if you're setting a container's storage to something that it shouldn't write to, like mmapped memory.

func (*Container) Slice 

func (c *Container) Slice() (r []uint16)

Slice returns an array of the values in the container as uint16. Do NOT modify the result; it could be the container's actual storage.

func (*Container) String 

func (c *Container) String() string

func (*Container) Thaw 

func (c *Container) Thaw() *Container

Thaw returns a modifiable container identical to c. This may be c, or it may be a new container with distinct backing store.

func (*Container) UnionInPlace 

func (c *Container) UnionInPlace(other *Container) (r *Container)

UnionInPlace yields a container containing all the bits set in either c or other. It may, or may not, modify c. The resulting container's count, as returned by c.N(), may be incorrect; see (*Container).Repair(). Do not freeze a container produced by this operation before repairing it. We don't want this to call repair immediately because it can be faster for Bitmap.UnionInPlace to do it all at once after potentially many Container.UnionInPlace calls.

func (*Container) WriteTo 

func (c *Container) WriteTo(w io.Writer) (n int64, err error)

WriteTo writes c to w.

type ContainerInfo 

type ContainerInfo struct {
	Key     uint64  // container key
	Type    string  // container type (array, bitmap, or run)
	Flags   string  // flag state
	N       int32   // number of bits
	Alloc   int     // memory used
	Pointer uintptr // address
	Mapped  bool    // whether this container thinks it is mmapped
}

ContainerInfo represents a point-in-time snapshot of container stats.

type ContainerIterator 

type ContainerIterator interface {
	Next() bool
	Value() (uint64, *Container)
	Close()
}

func NewContainerIterator 

func NewContainerIterator(data []byte) (ContainerIterator, error)

NewContainerIterator takes a byte slice which is either standard roaring or pilosa roaring and returns a ContainerIterator.

func NewRepeatedRowIteratorFromBytes 

func NewRepeatedRowIteratorFromBytes(data []byte) (ContainerIterator, error)

NewRepeatedRowIteratorFromBytes interprets "data" as a roaring bitmap and returns a ContainerIterator which will repeatedly return the first "row" of data as determined by shard width, but with increasing keys. It is essentially a conveniece wrapper around NewContainerIterator and NewRepeatedRowContainerIterator. It treats empty "data" as valid and returns a no-op iterator.

func NewUnionContainerIterator 

func NewUnionContainerIterator(iters ...ContainerIterator) ContainerIterator

NewUnionContainerIterator unions multiple container iterators to one.

type ContainerWriteback 

type ContainerWriteback func(key FilterKey, data *Container) error

ContainerWriteback is the type for functions which can feed updated containers back to things from filters.

type Containers 

type Containers interface {
	// Get returns nil if the key does not exist.
	Get(key uint64) *Container

	// Put adds the container at key.
	Put(key uint64, c *Container)

	// Remove takes the container at key out.
	Remove(key uint64)

	// GetOrCreate returns the container at key, creating a new empty container if necessary.
	GetOrCreate(key uint64) *Container

	// Clone does a deep copy of Containers, including cloning all containers contained.
	Clone() Containers

	// Freeze creates a shallow copy of Containers, freezing all the containers
	// contained. The new copy is a distinct Containers, but the individual containers
	// are shared (but marked as frozen).
	Freeze() Containers

	// Last returns the highest key and associated container.
	Last() (key uint64, c *Container)

	// Size returns the number of containers stored.
	Size() int

	// Update calls fn (existing-container, existed), and expects
	// (new-container, write). If write is true, the container is used to
	// replace the given container.
	Update(key uint64, fn func(*Container, bool) (*Container, bool))

	// UpdateEvery calls fn (existing-container, existed), and expects
	// (new-container, write). If write is true, the container is used to
	// replace the given container.
	UpdateEvery(fn func(uint64, *Container, bool) (*Container, bool))

	// Iterator returns a ContainterIterator which after a call to Next(), a call to Value() will
	// return the first container at or after key. found will be true if a
	// container is found at key.
	Iterator(key uint64) (citer ContainerIterator, found bool)

	Count() uint64

	// Reset clears the containers collection to allow for recycling during snapshot
	Reset()
	// ResetN clears the collection but hints at a needed size.
	ResetN(int)

	// Repair will repair the cardinality of any containers whose cardinality were corrupted
	// due to optimized operations.
	Repair()
}

type ErrorList 

type ErrorList []error //nolint:errname

ErrorList represents a list of errors.

func (*ErrorList) Append 

func (a *ErrorList) Append(err error)

Append appends an error to the list. If err is an ErrorList then all errors are appended.

func (*ErrorList) AppendWithPrefix 

func (a *ErrorList) AppendWithPrefix(err error, prefix string)

AppendWithPrefix appends an error to the list and includes a prefix.

func (ErrorList) Error 

func (a ErrorList) Error() string

type FileShouldBeTruncatedError 

type FileShouldBeTruncatedError interface {
	AdvisoryError
	SuggestedLength() int64
}

type FilterKey 

type FilterKey uint64
const KEY_DONE FilterKey = math.MaxUint64

func (FilterKey) Add 

func (f FilterKey) Add(x uint64) FilterKey

Add adds an offset to a key.

func (FilterKey) Done 

func (f FilterKey) Done() FilterResult

Done indicates that nothing can ever match.

func (FilterKey) Fail 

func (f FilterKey) Fail(err error) FilterResult

Fail() reports a fatal error that should terminate processing.

func (FilterKey) Failf 

func (f FilterKey) Failf(msg string, args ...interface{}) FilterResult

Failf() is just like Errorf, etc

func (FilterKey) MatchOne 

func (f FilterKey) MatchOne() FilterResult

func (FilterKey) MatchOneRejectRow 

func (f FilterKey) MatchOneRejectRow() FilterResult

MatchOneRejectRow indicates that this item matched but no further items in this row can match.

func (FilterKey) MatchOneUntilOffset 

func (f FilterKey) MatchOneUntilOffset(offset uint64) FilterResult

MatchUntilOffset matches the current container, then skips any other containers until the given offset.

func (FilterKey) MatchOneUntilSameOffset 

func (f FilterKey) MatchOneUntilSameOffset() FilterResult

Match the current container, then skip any others until the same offset is reached again.

func (FilterKey) MatchReject 

func (f FilterKey) MatchReject(y, n FilterKey) FilterResult

MatchReject just sets Yes and No appropriately.

func (FilterKey) MatchRow 

func (f FilterKey) MatchRow() FilterResult

MatchRow indicates that the current row matches the filter.

func (FilterKey) MatchRowAndDone 

func (f FilterKey) MatchRowAndDone() FilterResult

MatchRowAndDone matches this row and nothing after that.

func (FilterKey) MatchRowUntilRow 

func (f FilterKey) MatchRowUntilRow(rowID uint64) FilterResult

MatchRowUntilRow matches this row, then rejects everything else until the given row ID.

func (FilterKey) NeedData 

func (f FilterKey) NeedData() FilterResult

NeedData() is only really meaningful for ConsiderKey, and indicates that a decision can't be made from the key alone.

func (FilterKey) Reject 

func (f FilterKey) Reject(n uint64) FilterResult

Reject rejects N items.

func (FilterKey) RejectOne 

func (f FilterKey) RejectOne() FilterResult

Reject rejects this item only.

func (FilterKey) RejectRow 

func (f FilterKey) RejectRow() FilterResult

RejectRow indicates that this entire row is rejected.

func (FilterKey) RejectUntil 

func (f FilterKey) RejectUntil(until FilterKey) FilterResult

RejectUntil rejects everything up to the given key.

func (FilterKey) RejectUntilOffset 

func (f FilterKey) RejectUntilOffset(offset uint64) FilterResult

RejectUntilOffset rejects this container, and any others until the given in-row offset.

func (FilterKey) RejectUntilRow 

func (f FilterKey) RejectUntilRow(rowID uint64) FilterResult

RejectUntilRow rejects everything until the given row ID.

func (FilterKey) Row 

func (f FilterKey) Row() uint64

Row() computes the row number of a key.

func (FilterKey) Sub 

func (f FilterKey) Sub(o FilterKey) uint64

Sub determines the distance from o to f.

type FilterResult 

type FilterResult struct {
	YesKey FilterKey // The lowest container key this filter is known NOT to match.
	NoKey  FilterKey // The highest container key after YesKey that this filter is known to not match.
	Err    error     // An error which should terminate processing.
}

FilterResult represents the results of a BitmapFilter considering a key, or data. The values are represented as exclusive upper bounds on a series of matches followed by a series of rejections. So for instance, if called on key 23, the result {YesKey: 23, NoKey: 24} indicates that key 23 is a "no" and 24 is unknown and will be the next to be Consider()ed. This may seem confusing but it makes the math a lot easier to write. It can also report an error, which indicates that the entire operation should be stopped with that error.

type Interval16 

type Interval16 struct {
	Start uint16
	Last  uint16
}

func AsRuns 

func AsRuns(c *Container) []Interval16

type Iterator 

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

Iterator represents an iterator over a Bitmap.

func (*Iterator) Close 

func (itr *Iterator) Close()

This exists because we used to support a backend which needed it, and I don't want to re-experience the joy of figuring out where close calls are needed.

func (*Iterator) Next 

func (itr *Iterator) Next() (v uint64, eof bool)

Next returns the next value in the bitmap. Returns eof as true if there are no values left in the iterator.

func (*Iterator) Seek 

func (itr *Iterator) Seek(seek uint64)

Seek moves to the first value equal to or greater than `seek`.

type OpInfo 

type OpInfo struct {
	Type string
	OpN  int
	Size int
}

OpInfo is a description of an op.

type RoaringIterator 

type RoaringIterator interface {
	// Len reports the number of containers total.
	Len() (count int64)
	// Next yields the information about the next container
	Next() (key uint64, cType byte, n int, length int, pointer *uint16, err error)
	// Remaining yields the bytes left over past the end of the roaring data,
	// which is typically an ops log in our case, and also its offset in case
	// we need to talk about truncation.
	Remaining() ([]byte, int64)

	// NextContainer is a helper that is used in place of Next(). It will
	// allocate a Container from the output of its internal call to Next(),
	// and return the key and container rc. If Next returns an error, then
	// NextContainer will return 0, nil.
	// TODO: have this reuse the *Container?
	NextContainer() (key uint64, rc *Container)

	// Data returns the underlying data, esp for the Ops log.
	Data() []byte

	// Clone copies the iterator, preserving it at this point in the iteration.
	// It may well share much underlying data.
	Clone() RoaringIterator

	// ContainerKeys provides all the
	// container keys that the iterator will return.
	// The current implementation requires that the underlying header
	// lists the keys in ascending order.
	// If there are no keys, then an empty slice will be returned.
	ContainerKeys() (slc []uint64)

	// Skip will move the iterator forward by 1 without
	// materializing the container.
	Skip()
}

RoaringIterator represents something which can iterate through a roaring bitmap and yield information about containers, including type, size, and the location of their data structures.

func NewRoaringIterator 

func NewRoaringIterator(data []byte) (RoaringIterator, error)

Source Files

View all Source files

Directories

Path Synopsis

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.