README
¶
go-bitfield
Advanced RLE+ implementation
Features iterator based primitives that scale with number of runs instead of number of bits.
License
The Filecoin Project is dual-licensed under Apache 2.0 and MIT terms:
- Apache License, Version 2.0, (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
- MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)
Documentation
¶
Index ¶
- Constants
- Variables
- type BitField
- func CutBitField(a, b BitField) (BitField, error)
- func IntersectBitField(a, b BitField) (BitField, error)
- func MergeBitFields(a, b BitField) (BitField, error)
- func MultiMerge(bfs ...BitField) (BitField, error)
- func New() BitField
- func NewFromBytes(rle []byte) (BitField, error)
- func NewFromIter(r rlepluslazy.RunIterator) (BitField, error)
- func NewFromSet(setBits []uint64) BitField
- func SubtractBitField(a, b BitField) (BitField, error)
- func (bf BitField) All(max uint64) ([]uint64, error)
- func (bf BitField) AllMap(max uint64) (map[uint64]bool, error)
- func (bf BitField) BitIterator() (rlepluslazy.BitIterator, error)
- func (bf BitField) Copy() (BitField, error)
- func (bf BitField) Count() (uint64, error)
- func (bf BitField) First() (uint64, error)
- func (bf BitField) ForEach(f func(uint64) error) error
- func (bf BitField) IsEmpty() (bool, error)
- func (bf BitField) IsSet(x uint64) (bool, error)
- func (bf BitField) Last() (uint64, error)
- func (bf BitField) MarshalCBOR(w io.Writer) error
- func (bf BitField) MarshalJSON() ([]byte, error)
- func (bf BitField) RunIterator() (rlepluslazy.RunIterator, error)
- func (bf BitField) Set(bit uint64)
- func (bf BitField) Slice(start, count uint64) (BitField, error)
- func (bf *BitField) UnmarshalCBOR(r io.Reader) error
- func (bf *BitField) UnmarshalJSON(b []byte) error
- func (bf BitField) Unset(bit uint64)
Constants ¶
const MaxEncodedSize = 32 << 10
MaxEncodedSize is the maximum encoded size of a bitfield. When expanded into a slice of runs, a bitfield of this size should not exceed 2MiB of memory.
This bitfield can fit at least 3072 sparse elements.
Variables ¶
var ( ErrBitFieldTooMany = errors.New("to many items in RLE") ErrNoBitsSet = errors.New("bitfield has no set bits") )
Functions ¶
This section is empty.
Types ¶
type BitField ¶
type BitField struct {
// contains filtered or unexported fields
}
func CutBitField ¶
CutBitField cuts bitfield B from bitfield A. For every bit in B cut from A, subsequent entries in A are shifted down by one.
For example:
a: 0 1 0 1 1 1 b: 0 1 1 0 0 0 c: 0 1 1 1 // cut c: 0 1 1 1 // remove holes
func IntersectBitField ¶
IntersectBitField returns the intersection of the two BitFields.
For example, given two BitFields:
0 1 1 0 1 1 1 0 1 0
IntersectBitField would return
0 1 0 0 0
This operation's runtime is O(number of runs).
func MergeBitFields ¶
MergeBitFields returns the union of the two BitFields.
For example, given two BitFields:
0 1 1 0 1 1 1 0 1 0
MergeBitFields would return
1 1 1 1 1
This operation's runtime is O(number of runs).
func MultiMerge ¶
MultiMerge returns the unions of all the passed BitFields.
Calling MultiMerge is identical to calling MergeBitFields repeatedly, just more efficient when merging more than two BitFields.
This operation's runtime is O(number of runs * number of bitfields).
func NewFromBytes ¶
NewFromBytes deserializes the encoded bitfield.
func NewFromIter ¶
func NewFromIter(r rlepluslazy.RunIterator) (BitField, error)
NewFromIter constructs a BitField from the RunIterator.
func NewFromSet ¶
NewFromSet constructs a bitfield from the given set.
func SubtractBitField ¶
SubtractBitField returns the difference between the two BitFields. That is, it returns a bitfield of all bits set in a but not set in b.
For example, given two BitFields:
0 1 1 0 1 // a 1 1 0 1 0 // b
SubtractBitFields would return
0 0 1 0 1
This operation's runtime is O(number of runs).
func (BitField) All ¶
All returns a slice of set bits in sorted order.
For example, given:
1 0 0 1
All will return:
[]uint64{0, 3}
This operation's runtime is O(number of bits).
func (BitField) AllMap ¶
AllMap returns a map of all set bits.
For example, given:
1 0 0 1
All will return:
map[uint64]bool{0: true, 3: true}
This operation's runtime is O(number of bits).
func (BitField) BitIterator ¶
func (bf BitField) BitIterator() (rlepluslazy.BitIterator, error)
BitIterator iterates over the bits in the bitmap
func (BitField) Copy ¶
Copy flushes the bitfield and returns a copy that can be mutated without changing the original values
func (BitField) Count ¶
Count counts the non-zero bits in the bitfield.
For example, given:
1 0 1 1
Count() will return 3.
This operation's runtime is O(number of runs).
func (BitField) First ¶
First returns the index of the first set bit. This function returns ErrNoBitsSet when no bits have been set.
This operation's runtime is O(1).
func (BitField) ForEach ¶
ForEach iterates over each set bit.
This operation's runtime is O(bits set).
func (BitField) IsEmpty ¶
IsEmpty returns true if the bitset is empty.
This operation's runtime is O(1).
func (BitField) IsSet ¶
IsSet returns true if the given bit is set.
This operation's runtime is O(number of runs).
func (BitField) Last ¶
Last returns the index of the last set bit. This function returns ErrNoBitsSet when no bits have been set.
This operation's runtime is O(n).
func (BitField) MarshalJSON ¶
func (BitField) RunIterator ¶
func (bf BitField) RunIterator() (rlepluslazy.RunIterator, error)
func (BitField) Set ¶
Set sets the given bit in the BitField
This operation's runtime is O(1) up-front. However, it adds an O(bits explicitly set) cost to all other operations.
func (BitField) Slice ¶
Slice treats the BitField as an ordered set of set bits, then slices this set.
That is, it skips start set bits, then returns the next count set bits.
For example, given:
1 0 1 1 0 1 1
bf.Slice(2, 2) would return:
0 0 0 1 0 1 0
This operation's runtime is O(number of runs).
Source Files
Directories