bitutils

package
v16.1.0 Latest Latest
Warning

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

Go to latest
Published: May 9, 2024 License: Apache-2.0, BSD-2-Clause, BSD-3-Clause, + 7 more Imports: 8 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func GenerateBits

func GenerateBits(bitmap []byte, start, length int64, g func() bool)

GenerateBits writes sequential bits to a bitmap. Bits preceding the initial start offset are preserved, bits following the bitmap may get clobbered.

func GenerateBitsUnrolled

func GenerateBitsUnrolled(bitmap []byte, start, length int64, g func() bool)

GenerateBitsUnrolled is like GenerateBits but unrolls its main loop for higher performance.

See the benchmarks for evidence.

func IsMultipleOf64

func IsMultipleOf64(v int64) bool

IsMultipleOf64 returns whether v is a multiple of 64.

func LeastSignificantBitMask

func LeastSignificantBitMask(index int64) uint64

LeastSignificantBitMask returns a bit mask to return the least significant bits for a value starting from the bit index passed in. ie: if you want a mask for the 4 least significant bits, you call LeastSignificantBitMask(4)

func VisitBitBlocks

func VisitBitBlocks(bitmap []byte, offset, length int64, visitValid func(pos int64), visitInvalid func())

VisitBitBlocks is a utility for easily iterating through the blocks of bits in a bitmap, calling the appropriate visitValid/visitInvalid function as we iterate through the bits. visitValid is called with the bitoffset of the valid bit. Don't use this inside a tight loop when performance is needed and instead prefer manually constructing these loops in that scenario.

func VisitBitBlocksShort

func VisitBitBlocksShort(bitmap []byte, offset, length int64, visitValid func(pos int64) error, visitInvalid func() error) error

VisitBitBlocks is a utility for easily iterating through the blocks of bits in a bitmap, calling the appropriate visitValid/visitInvalid function as we iterate through the bits. visitValid is called with the bitoffset of the valid bit. Don't use this inside a tight loop when performance is needed and instead prefer manually constructing these loops in that scenario.

func VisitSetBitRuns

func VisitSetBitRuns(bitmap []byte, bitmapOffset int64, length int64, visitFn VisitFn) error

VisitSetBitRuns is just a convenience function for calling NewSetBitRunReader and then VisitSetBitRuns

func VisitSetBitRunsNoErr

func VisitSetBitRunsNoErr(bitmap []byte, bitmapOffset int64, length int64, visitFn func(pos, length int64))

func VisitTwoBitBlocks

func VisitTwoBitBlocks(leftBitmap, rightBitmap []byte, leftOffset, rightOffset int64, len int64, visitValid func(pos int64), visitNull func())

Types

type BinaryBitBlockCounter

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

BinaryBitBlockCounter computes popcounts on the result of bitwise operations between two bitmaps, 64 bits at a time. A 64-bit word is loaded from each bitmap, then the popcount is computed on e.g. the bitwise-and of the two words

func NewBinaryBitBlockCounter

func NewBinaryBitBlockCounter(left, right []byte, leftOffset, rightOffset int64, length int64) *BinaryBitBlockCounter

NewBinaryBitBlockCounter constructs a binary bit block counter for computing the popcounts on the results of operations between the passed in bitmaps, with their respective offsets.

func (*BinaryBitBlockCounter) NextAndNotWord

func (b *BinaryBitBlockCounter) NextAndNotWord() BitBlockCount

NextAndNotWord is like NextAndWord but performs x &^ y on each run

func (*BinaryBitBlockCounter) NextAndWord

func (b *BinaryBitBlockCounter) NextAndWord() BitBlockCount

NextAndWord returns the popcount of the bitwise-and of the next run of available bits, up to 64. The returned pair contains the size of the run and the number of true values. the last block will have a length less than 64 if the bitmap length is not a multiple of 64, and will return 0-length blocks in subsequent invocations

func (*BinaryBitBlockCounter) NextOrNotWord

func (b *BinaryBitBlockCounter) NextOrNotWord() BitBlockCount

NextOrWord is like NextAndWord but performs x | ^y on each run

func (*BinaryBitBlockCounter) NextOrWord

func (b *BinaryBitBlockCounter) NextOrWord() BitBlockCount

NextOrWord is like NextAndWord but performs x | y on each run

type BitBlockCount

type BitBlockCount struct {
	Len    int16
	Popcnt int16
}

BitBlockCount is returned by the various bit block counter utilities in order to return a length of bits and the population count of that slice of bits.

func (BitBlockCount) AllSet

func (b BitBlockCount) AllSet() bool

AllSet returns true if ALL the bits were 1 in this set, ie: Popcnt == Len

func (BitBlockCount) NoneSet

func (b BitBlockCount) NoneSet() bool

NoneSet returns true if ALL the bits were 0 in this set, ie: Popcnt == 0

type BitBlockCounter

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

BitBlockCounter is a utility for grabbing chunks of a bitmap at a time and efficiently counting the number of bits which are 1.

func NewBitBlockCounter

func NewBitBlockCounter(bitmap []byte, startOffset, nbits int64) *BitBlockCounter

NewBitBlockCounter returns a BitBlockCounter for the passed bitmap starting at startOffset of length nbits.

func (*BitBlockCounter) NextFourWords

func (b *BitBlockCounter) NextFourWords() BitBlockCount

NextFourWords returns the next run of available bits, usually 256. The returned pair contains the size of run and the number of true values. The last block will have a length less than 256 if the bitmap length is not a multiple of 256, and will return 0-length blocks in subsequent invocations.

func (*BitBlockCounter) NextWord

func (b *BitBlockCounter) NextWord() BitBlockCount

NextWord returns the next run of available bits, usually 64. The returned pair contains the size of run and the number of true values. The last block will have a length less than 64 if the bitmap length is not a multiple of 64, and will return 0-length blocks in subsequent invocations.

type BitRun

type BitRun struct {
	Len int64
	Set bool
}

BitRun represents a run of bits with the same value of length Len with Set representing if the group of bits were 1 or 0.

func (BitRun) String

func (b BitRun) String() string

type BitRunReader

type BitRunReader interface {
	NextRun() BitRun
}

BitRunReader is an interface that is usable by multiple callers to provide multiple types of bit run readers such as a reverse reader and so on.

It's a convenience interface for counting contiguous set/unset bits in a bitmap. In places where BitBlockCounter can be used, then it would be preferred to use that as it would be faster than using BitRunReader.

func NewBitRunReader

func NewBitRunReader(bitmap []byte, offset int64, length int64) BitRunReader

NewBitRunReader returns a reader for the given bitmap, offset and length that grabs runs of the same value bit at a time for easy iteration.

type OptionalBitBlockCounter

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

OptionalBitBlockCounter is a useful counter to iterate through a possibly nonexistent validity bitmap to allow us to write one code path for both the with-nulls and no-nulls cases without giving up a lot of performance.

func NewOptionalBitBlockCounter

func NewOptionalBitBlockCounter(bitmap []byte, offset, length int64) *OptionalBitBlockCounter

NewOptionalBitBlockCounter constructs and returns a new bit block counter that can properly handle the case when a bitmap is null, if it is guaranteed that the the bitmap is not nil, then prefer NewBitBlockCounter here.

func (*OptionalBitBlockCounter) NextBlock

func (obc *OptionalBitBlockCounter) NextBlock() BitBlockCount

NextBlock returns block count for next word when the bitmap is available otherwise return a block with length up to INT16_MAX when there is no validity bitmap (so all the referenced values are not null).

func (*OptionalBitBlockCounter) NextWord

func (obc *OptionalBitBlockCounter) NextWord() BitBlockCount

NextWord is like NextBlock, but returns a word-sized block even when there is no validity bitmap

type SetBitRun

type SetBitRun struct {
	Pos    int64
	Length int64
}

SetBitRun describes a run of contiguous set bits in a bitmap with Pos being the starting position of the run and Length being the number of bits.

func (SetBitRun) AtEnd

func (s SetBitRun) AtEnd() bool

AtEnd returns true if this bit run is the end of the set by checking that the length is 0.

func (SetBitRun) Equal

func (s SetBitRun) Equal(rhs SetBitRun) bool

Equal returns whether rhs is the same run as s

type SetBitRunReader

type SetBitRunReader interface {
	// NextRun will return the next run of contiguous set bits in the bitmap
	NextRun() SetBitRun
	// Reset allows re-using the reader by providing a new bitmap, offset and length. The arguments
	// match the New function for the reader being used.
	Reset([]byte, int64, int64)
	// VisitSetBitRuns calls visitFn for each set in a loop starting from the current position
	// it's roughly equivalent to simply looping, calling NextRun and calling visitFn on the run
	// for each run.
	VisitSetBitRuns(visitFn VisitFn) error
}

SetBitRunReader is an interface for reading groups of contiguous set bits from a bitmap. The interface allows us to create different reader implementations that share the same interface easily such as a reverse set reader.

func NewReverseSetBitRunReader

func NewReverseSetBitRunReader(validBits []byte, startOffset, numValues int64) SetBitRunReader

NewReverseSetBitRunReader returns a SetBitRunReader like NewSetBitRunReader, except it will return runs starting from the end of the bitmap until it reaches startOffset rather than starting at startOffset and reading from there. The SetBitRuns will still operate the same, so Pos will still be the position of the "left-most" bit of the run or the "start" of the run. It just returns runs starting from the end instead of starting from the beginning.

func NewSetBitRunReader

func NewSetBitRunReader(validBits []byte, startOffset, numValues int64) SetBitRunReader

NewSetBitRunReader returns a SetBitRunReader for the bitmap starting at startOffset which will read numvalues bits.

type VisitFn

type VisitFn func(pos int64, length int64) error

VisitFn is a callback function for visiting runs of contiguous bits

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL