package bitutils

Import Path
	github.com/apache/arrow-go/v18/internal/bitutils (on go.dev)

Dependency Relation
	imports 8 packages, and imported by 2 packages



Package-Level Type Names (total 9)


	/* sort by:  |  */
	
		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

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

			
				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

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

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

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


	
		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.

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

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

		
			func (*BinaryBitBlockCounter).NextAndNotWord() BitBlockCount
			func (*BinaryBitBlockCounter).NextAndWord() BitBlockCount
			func (*BinaryBitBlockCounter).NextOrNotWord() BitBlockCount
			func (*BinaryBitBlockCounter).NextOrWord() BitBlockCount
			func (*BitBlockCounter).NextFourWords() BitBlockCount
			func (*BitBlockCounter).NextWord() BitBlockCount
			func (*OptionalBitBlockCounter).NextBlock() BitBlockCount
			func (*OptionalBitBlockCounter).NextWord() BitBlockCount


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

		
			
				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.

			
				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.

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


	
		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.

		
			Len int64
			Set bool
		
			( BitRun) String() string
		
			 BitRun : expvar.Var
			 BitRun : fmt.Stringer
		
			func BitRunReader.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.

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


	
		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.

		
			
				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).

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

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


	
		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.

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

			
				Equal returns whether rhs is the same run as s

		
			func SetBitRunReader.NextRun() SetBitRun
		
			func SetBitRun.Equal(rhs SetBitRun) bool


	
		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.

		
			
				NextRun will return the next run of contiguous set bits in the bitmap

			
				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.

			
				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.

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


	
		VisitFn is a callback function for visiting runs of contiguous bits

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




Package-Level Functions (total 15)


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


	
		GenerateBitsUnrolled is like GenerateBits but unrolls its main loop for
		higher performance.
		
		See the benchmarks for evidence.


	
		IsMultipleOf64 returns whether v is a multiple of 64.


	
		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)


	
		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.


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


	
		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.


	
		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.


	
		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.


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


	
		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.


	
		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.


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


	 func VisitSetBitRunsNoErr(bitmap []byte, bitmapOffset int64, length int64, visitFn func(pos, length int64))
	 func VisitTwoBitBlocks(leftBitmap, rightBitmap []byte, leftOffset, rightOffset int64, len int64, visitValid func(pos int64), visitNull func())