roaring

Documentation

Overview

package roaring implements roaring bitmaps with support for incremental changes.

Index

• Constants
• func BSFQ(memory uint64) int
• func POPCNTQ(memory uint64) int
• func WriteUint16(w io.Writer, b []byte, v uint16) (int, error)
• func WriteUint32(w io.Writer, b []byte, v uint32) (int, error)
• func WriteUint64(w io.Writer, b []byte, v uint64) (int, error)
• type Bitmap
  • func NewBitmap(a ...uint64) *Bitmap
  • func (b *Bitmap) Add(a ...uint64) (changed bool, err error)
  • func (b *Bitmap) Check() error
  • func (b *Bitmap) Clone() *Bitmap
  • func (b *Bitmap) Contains(v uint64) bool
  • func (b *Bitmap) Count() (n uint64)
  • func (b *Bitmap) CountRange(start, end uint64) (n uint64)
  • func (b *Bitmap) Difference(other *Bitmap) *Bitmap
  • func (b *Bitmap) Flip(start, end uint64) *Bitmap
  • func (b *Bitmap) ForEach(fn func(uint64))
  • func (b *Bitmap) ForEachRange(start, end uint64, fn func(uint64))
  • func (b *Bitmap) Info() BitmapInfo
  • func (b *Bitmap) Intersect(other *Bitmap) *Bitmap
  • func (b *Bitmap) IntersectionCount(other *Bitmap) uint64
  • func (b *Bitmap) Iterator() *Iterator
  • func (b *Bitmap) Max() uint64
  • func (b *Bitmap) OffsetRange(offset, start, end uint64) *Bitmap
  • func (b *Bitmap) Optimize()
  • func (b *Bitmap) Remove(a ...uint64) (changed bool, err error)
  • func (b *Bitmap) Slice() []uint64
  • func (b *Bitmap) SliceRange(start, end uint64) []uint64
  • func (b *Bitmap) Union(other *Bitmap) *Bitmap
  • func (b *Bitmap) UnmarshalBinary(data []byte) error
  • func (b *Bitmap) WriteTo(w io.Writer) (n int64, err error)
  • func (b *Bitmap) Xor(other *Bitmap) *Bitmap
• type BitmapInfo
• type ContainerInfo
• type ErrorList
  • func (a *ErrorList) Append(err error)
  • func (a *ErrorList) AppendWithPrefix(err error, prefix string)
  • func (a ErrorList) Error() string
• type Iterator
  • func (itr *Iterator) Next() (v uint64, eof bool)
  • func (itr *Iterator) Seek(seek uint64)

Constants

const (
	ContainerArray  = byte(1)
	ContainerBitmap = byte(2)
	ContainerRun    = byte(3)
)

const ArrayMaxSize = 4096

The maximum size of array containers.

const RunMaxSize = 2048

The maximum size of run length encoded containers.

Functions

func BSFQ

func BSFQ(memory uint64) int

func POPCNTQ

func POPCNTQ(memory uint64) int

func WriteUint16

func WriteUint16(w io.Writer, b []byte, v uint16) (int, error)

hoping this in-lines

func WriteUint32

func WriteUint32(w io.Writer, b []byte, v uint32) (int, error)

func WriteUint64

func WriteUint64(w io.Writer, b []byte, v uint64) (int, error)

Types

type Bitmap

type Bitmap struct {

	// Writer where operations are appended to.
	OpWriter io.Writer
	// contains filtered or unexported fields
}

Bitmap represents a roaring bitmap.

func NewBitmap

func NewBitmap(a ...uint64) *Bitmap

NewBitmap returns a Bitmap with an initial set of values.

func (*Bitmap) Add

func (b *Bitmap) Add(a ...uint64) (changed bool, err error)

Add adds values to the bitmap.

func (*Bitmap) Check

func (b *Bitmap) Check() error

Check performs a consistency check on the bitmap. Returns nil if consistent.

func (*Bitmap) Clone

func (b *Bitmap) Clone() *Bitmap

Clone returns a heap allocated copy of the bitmap. Note: The OpWriter IS NOT copied to the new bitmap.

func (*Bitmap) Contains

func (b *Bitmap) Contains(v uint64) bool

Contains returns true if v is in the bitmap.

func (*Bitmap) Count

func (b *Bitmap) Count() (n uint64)

Count returns the number of bits set in the bitmap.

func (*Bitmap) CountRange

func (b *Bitmap) CountRange(start, end uint64) (n uint64)

CountRange returns the number of bits set between [start, end).

func (*Bitmap) Difference

func (b *Bitmap) Difference(other *Bitmap) *Bitmap

Difference returns the difference of b and other.

func (*Bitmap) Flip

func (b *Bitmap) Flip(start, end uint64) *Bitmap

Perform a logical negate of the bits in the range [start,end].

func (*Bitmap) ForEach

func (b *Bitmap) ForEach(fn func(uint64))

ForEach executes fn for each value in the bitmap.

func (*Bitmap) ForEachRange

func (b *Bitmap) ForEachRange(start, end uint64, fn func(uint64))

ForEachRange executes fn for each value in the bitmap between [start, end).

func (*Bitmap) Info

func (b *Bitmap) Info() BitmapInfo

Info returns stats for the bitmap.

func (*Bitmap) Intersect

func (b *Bitmap) Intersect(other *Bitmap) *Bitmap

Intersect returns the intersection of b and other.

func (*Bitmap) IntersectionCount

func (b *Bitmap) IntersectionCount(other *Bitmap) uint64

IntersectionCount returns the number of set bits that would result in an intersection between b and other. It is more efficient than actually intersecting the two and counting the result.

func (*Bitmap) Iterator

func (b *Bitmap) Iterator() *Iterator

Iterator returns a new iterator for the bitmap.

func (*Bitmap) Max

func (b *Bitmap) Max() uint64

Max returns the highest value in the bitmap. Returns zero if the bitmap is empty.

func (*Bitmap) OffsetRange

func (b *Bitmap) OffsetRange(offset, start, end uint64) *Bitmap

OffsetRange returns a new bitmap with a containers offset by start.

func (*Bitmap) Optimize

func (b *Bitmap) Optimize()

Optimize converts array and bitmap containers to run containers as necessary.

func (*Bitmap) Remove

func (b *Bitmap) Remove(a ...uint64) (changed bool, err error)

Remove removes values from the bitmap.

func (*Bitmap) Slice

func (b *Bitmap) Slice() []uint64

Slice returns a slice of all integers in the bitmap.

func (*Bitmap) SliceRange

func (b *Bitmap) SliceRange(start, end uint64) []uint64

SliceRange returns a slice of integers between [start, end).

func (*Bitmap) Union

func (b *Bitmap) Union(other *Bitmap) *Bitmap

Union returns the bitwise union of b and other.

func (*Bitmap) UnmarshalBinary

func (b *Bitmap) UnmarshalBinary(data []byte) error

UnmarshalBinary decodes b from a binary-encoded byte slice.

func (*Bitmap) WriteTo

func (b *Bitmap) WriteTo(w io.Writer) (n int64, err error)

WriteTo writes b to w.

func (*Bitmap) Xor

func (b *Bitmap) Xor(other *Bitmap) *Bitmap

Xor returns the bitwise exclusive or of b and other.

type BitmapInfo

type BitmapInfo struct {
	OpN        int
	Containers []ContainerInfo
}

BitmapInfo represents a point-in-time snapshot of bitmap stats.

type ContainerInfo

type ContainerInfo struct {
	Key     uint64         // container key
	Type    string         // container type (array, bitmap, or run)
	N       int            // number of bits
	Alloc   int            // memory used
	Pointer unsafe.Pointer // offset within the mmap
}

ContainerInfo represents a point-in-time snapshot of container stats.

type ErrorList

type ErrorList []error

ErrorList represents a list of errors.

func (*ErrorList) Append

func (a *ErrorList) Append(err error)

Append appends an error to the list. If err is an ErrorList then all errors are appended.

func (*ErrorList) AppendWithPrefix

func (a *ErrorList) AppendWithPrefix(err error, prefix string)

AppendWithPrefix appends an error to the list and includes a prefix.

func (ErrorList) Error

func (a ErrorList) Error() string

type Iterator

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

Iterator represents an iterator over a Bitmap.

func (*Iterator) Next

func (itr *Iterator) Next() (v uint64, eof bool)

Next returns the next value in the bitmap. Returns eof as true if there are no values left in the iterator.

func (*Iterator) Seek

func (itr *Iterator) Seek(seek uint64)

Seek moves to the first value equal to or greater than `seek`.