README
¶
Bitmap index in Go
This package contaisn a bitmap index which is backed by uint64 slice, easily encodable to/from a []byte without copying memory around so it can be present
in both disk and memory. As opposed to something as roaring bitmaps, this is a simple impementation designed to be used for small to medium dense collections.
Benchmarks
Benchmarks below were run on a large pre-allocated bitmap (slice of 100 elements).
cpu: Intel(R) Core(TM) i7-9700K CPU @ 3.60GHz
BenchmarkBitmap/set-8 606936064 1.984 ns/op 0 B/op 0 allocs/op
BenchmarkBitmap/remove-8 763688641 1.559 ns/op 0 B/op 0 allocs/op
BenchmarkBitmap/contains-8 915751614 1.299 ns/op 0 B/op 0 allocs/op
BenchmarkBitmap/and-8 31582188 38.38 ns/op 0 B/op 0 allocs/op
BenchmarkBitmap/andnot-8 23472387 50.65 ns/op 0 B/op 0 allocs/op
BenchmarkBitmap/or-8 23695324 50.98 ns/op 0 B/op 0 allocs/op
BenchmarkBitmap/xor-8 23197326 51.23 ns/op 0 B/op 0 allocs/op
BenchmarkBitmap/clear-8 205686652 5.897 ns/op 0 B/op 0 allocs/op
BenchmarkBitmap/ones-8 40554514 29.33 ns/op 0 B/op 0 allocs/op
BenchmarkBitmap/first-zero-8 30062228 40.39 ns/op 0 B/op 0 allocs/op
BenchmarkBitmap/min-8 381730626 3.131 ns/op 0 B/op 0 allocs/op
BenchmarkBitmap/max-8 684005834 1.756 ns/op 0 B/op 0 allocs/op
BenchmarkRange/count-8 34223232 35.20 ns/op 0 B/op 0 allocs/op
BenchmarkBitmap/clone-8 7676722 143.9 ns/op 896 B/op 1 allocs/op
Documentation
¶
Index ¶
- type Bitmap
- func (dst *Bitmap) And(b Bitmap)
- func (dst *Bitmap) AndNot(b Bitmap)
- func (dst *Bitmap) Clear()
- func (dst Bitmap) Clone(into Bitmap) Bitmap
- func (dst Bitmap) Contains(x uint32) bool
- func (dst Bitmap) Count() int
- func (dst *Bitmap) Filter(f func(x uint32) bool)
- func (dst Bitmap) FirstZero() (uint32, bool)
- func (dst Bitmap) Max() (uint32, bool)
- func (dst Bitmap) Min() (uint32, bool)
- func (dst Bitmap) Ones()
- func (dst *Bitmap) Or(b Bitmap)
- func (dst Bitmap) Range(f func(x uint32) bool)
- func (dst *Bitmap) Remove(x uint32)
- func (dst *Bitmap) Set(x uint32)
- func (dst *Bitmap) ToBytes() (out []byte)
- func (dst *Bitmap) WriteTo(w io.Writer) (int64, error)
- func (dst *Bitmap) Xor(b Bitmap)
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Bitmap ¶
type Bitmap []uint64
Bitmap represents a scalar-backed bitmap index
func (*Bitmap) And ¶
And computes the intersection between two bitmaps and stores the result in the current bitmap
func (*Bitmap) AndNot ¶
AndNot computes the difference between two bitmaps and stores the result in the current bitmap
func (Bitmap) Clone ¶
Clone clones the bitmap. If a destination bitmap is provided, the bitmap will be cloned inside, otherwise a new Bitmap will be allocated and returned
func (*Bitmap) Filter ¶
Filter iterates over the bitmap elements and calls a predicate provided for each containing element. If the predicate returns false, the bitmap at the element's position is set to zero.
func (Bitmap) FirstZero ¶
FirstZero finds the first zero bit and returns its index, assuming the bitmap is not empty.
func (Bitmap) Max ¶
Max get the largest value stored in this bitmap, assuming the bitmap is not empty.
func (Bitmap) Min ¶
Min get the smallest value stored in this bitmap, assuming the bitmap is not empty.
func (*Bitmap) Or ¶
Or computes the union between two bitmaps and stores the result in the current bitmap
func (Bitmap) Range ¶
Range iterates over the bitmap elements. If the callback returns false it halts the iteration.
func (*Bitmap) ToBytes ¶
ToBytes converts the bitmap to binary representation without copying the underlying data. The output buffer should not be modified, since it would also change the bitmap.
Source Files