Documentation
¶
Overview ¶
Package bitmap implements the Arrow validity bitmap.
A bitmap holds one bit per value, packed least significant bit first within each byte, which is the layout the Arrow columnar specification requires. A set bit means the value at that position is valid, and a clear bit means it is null.
The zero Bitmap is empty and ready to use. Append grows it.
Bits past the length live in the last byte and are always zero. Every operation that could leave them set clears them again before returning, so CountOnes and Bytes never have to think about it. This is not merely tidy: Arrow requires the padding to be zero for a buffer to round trip through IPC correctly.
Stability: tier 1, stable.
Index ¶
- type Bitmap
- func (b *Bitmap) And(other *Bitmap)
- func (b *Bitmap) AndNot(other *Bitmap)
- func (b *Bitmap) Append(v bool)
- func (b *Bitmap) Bytes() []byte
- func (b *Bitmap) Clone() *Bitmap
- func (b *Bitmap) CountOnes() int
- func (b *Bitmap) CountOnesRange(i, j int) int
- func (b *Bitmap) Get(i int) bool
- func (b *Bitmap) Len() int
- func (b *Bitmap) Not()
- func (b *Bitmap) Or(other *Bitmap)
- func (b *Bitmap) Set(i int, v bool)
- func (b *Bitmap) Slice(i, j int) *Bitmap
- func (b *Bitmap) Xor(other *Bitmap)
- type Builder
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Bitmap ¶
type Bitmap struct {
// contains filtered or unexported fields
}
Bitmap is a growable sequence of bits.
Example ¶
package main
import (
"fmt"
"github.com/tamnd/kuma/bitmap"
)
func main() {
// A column of five values where the third one is missing.
valid := bitmap.NewSet(5)
valid.Set(2, false)
fmt.Println(valid.Len(), valid.CountOnes())
fmt.Println(valid.Get(1), valid.Get(2))
}
Output: 5 4 true false
func FromBytes ¶
FromBytes wraps an existing byte slice as a bitmap of n bits without copying. The caller must not modify buf afterwards. It panics if buf is too short to hold n bits.
func NewSet ¶
NewSet returns a bitmap of n bits, all set. This is the common case for a column with no nulls, so it is worth having rather than looping over New.
func (*Bitmap) And ¶
And sets b to the intersection of b and other. Both must have the same length. This is the operation that combines two validity bitmaps in a binary kernel, where a result is valid only if both inputs were.
Example ¶
package main
import (
"fmt"
"github.com/tamnd/kuma/bitmap"
)
func main() {
// Adding two columns: the result is valid only where both inputs were.
a := bitmap.NewSet(4)
a.Set(1, false)
b := bitmap.NewSet(4)
b.Set(3, false)
a.And(b)
for i := range a.Len() {
fmt.Print(a.Get(i), " ")
}
fmt.Println()
}
Output: true false true false
func (*Bitmap) AndNot ¶
AndNot clears in b every bit that is set in other. Both must have the same length.
func (*Bitmap) Append ¶
Append adds one bit to the end.
Example ¶
package main
import (
"fmt"
"github.com/tamnd/kuma/bitmap"
)
func main() {
// The zero value is ready to use.
var b bitmap.Bitmap
for _, v := range []bool{true, false, true} {
b.Append(v)
}
fmt.Println(b.Len(), b.CountOnes())
}
Output: 3 2
func (*Bitmap) Bytes ¶
Bytes returns the underlying storage. The padding bits in the final byte are zero. Modifying the result modifies the bitmap.
func (*Bitmap) CountOnes ¶
CountOnes returns the number of set bits, which for a validity bitmap is the number of valid values.
It reads the whole buffer including the final byte, which is correct because the bits past the length there are always zero.
func (*Bitmap) CountOnesRange ¶
CountOnesRange returns the number of set bits in positions i through j-1. It panics if the range is out of bounds.
This is what a column reports as its null count after being sliced. Slicing is meant to be constant time, so the array layer keeps an offset into a bitmap it shares rather than copying one, and then it needs the count over a range that does not start on a byte boundary.
func (*Bitmap) Get ¶
Get reports whether bit i is set. It panics if i is out of range, matching the behavior of an ordinary slice index.
func (*Bitmap) Slice ¶
Slice returns bits i through j-1 as a new bitmap, renumbered so that bit i becomes bit 0. It panics if the range is out of bounds.
It copies rather than aliasing. A bitmap could carry a starting bit offset and slice in constant time, which is what an Arrow array does, but then Bytes would no longer return a buffer that begins at bit zero with zeroed padding, and every operation and every caller would have to carry an offset that is almost always zero. Copying costs one byte per eight bits, so slicing a chunk of eight thousand rows moves a kilobyte. The layers above this one keep their own offset for the places where constant time slicing is worth the complexity.
Example ¶
package main
import (
"fmt"
"github.com/tamnd/kuma/bitmap"
)
func main() {
valid := bitmap.NewSet(10)
valid.Set(4, false)
valid.Set(7, false)
// Rows 3 through 7 of the column, renumbered from zero.
window := valid.Slice(3, 8)
for i := range window.Len() {
fmt.Print(window.Get(i), " ")
}
fmt.Println()
}
Output: true false true true false
type Builder ¶
type Builder struct {
// contains filtered or unexported fields
}
Builder accumulates bits and hands over the finished Bitmap.
Bitmap.Append works one bit at a time, which is the right shape when the values arrive one at a time. A builder exists for the case that dominates when a column is being read, which is a long run of the same bit: a chunk with no nulls is n set bits in a row, and AppendMany writes the whole bytes of that run as a fill instead of n calls that each recompute the same byte index and mask.
The zero Builder is empty and ready to use.
Example ¶
package main
import (
"fmt"
"github.com/tamnd/kuma/bitmap"
)
func main() {
// Reading a column of a thousand values where only the last ten are
// missing. The long run of valid values is one call rather than a loop.
var b bitmap.Builder
b.Grow(1000)
b.AppendMany(true, 990)
b.AppendMany(false, 10)
valid := b.Finish()
fmt.Println(valid.Len(), valid.CountOnes())
}
Output: 1000 990
func (*Builder) AppendBools ¶
AppendBools adds one bit per element of vals.
func (*Builder) AppendMany ¶
AppendMany adds n copies of v to the end. AppendMany(true, n) is how a column with no nulls builds its validity bitmap, so it is the path worth keeping fast.
func (*Builder) Finish ¶
Finish returns the accumulated bits and resets the builder to empty.
The returned bitmap takes over the buffer rather than copying it, so a builder cannot be used to observe or modify a bitmap it has already handed over. Call Finish once per bitmap.
Source Files