roaring

package
v0.0.0-...-ac8920c Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Jan 28, 2019 License: Apache-2.0 Imports: 9 Imported by: 8

Documentation

Overview

Package roaring implements roaring bitmaps with support for incremental changes.

Index

Constants

View Source
const ArrayMaxSize = 4096

ArrayMaxSize represents the maximum size of array containers.

Variables

View Source
var NewFileBitmap func(a ...uint64) *Bitmap = NewBitmap

NewFileBitmap returns a Bitmap with an initial set of values, used for file storage. By default, this is a copy of NewBitmap, but is replaced with B+Tree in server/enterprise.go

Functions

This section is empty.

Types

type Bitmap

type Bitmap struct {
	Containers Containers

	// 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 NewBitmapWithDefaultPooling

func NewBitmapWithDefaultPooling(maxPoolCapacity int, a ...uint64) *Bitmap

NewBitmapWithDefaultPooling returns a new bitmap with the default pooling configuration. See the comment for NewBitmapWithPooling for more details about the pooling implementation.

func NewBitmapWithPooling

func NewBitmapWithPooling(pooling ContainerPoolingConfiguration, a ...uint64) *Bitmap

NewBitmapWithPooling returns a new Bitmap with the provided container pooling configuration and initial set of values.

Container Pooling is useful for reusing short lived Bitmaps (common in the situation where temporary bitmaps are being created for the sake of computation instead of storage). In that case, allocating new containers over and over again is unecessarily expensive. Instead, when you need an empty bitmap, you can call the Reset() method on an existing one. That will clear all the data it contains and return its containers (up to the configured maximum) to its pool so that when you start adding new data, the already allocated containers can be reused.

In exchange for reduced memory pressure / allocations, bitmaps with pooling enabled will use significantly more memory. This is for two reasons:

  1. Even when there is no data in the bitmap, a configurable number of containers have already been pre-allocated and are waiting in reserve.
  2. Every container that is allocated when pooling is enabled is pre-allocated such that it can seamlessly switch between a run, array, or a bitmap with zero allocations. This means it can be used for performing calculations very quickly and without causing G.C pressure, but it will use much more space.

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

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

DirectAdd adds a value to the bitmap by bypassing the op log.

func (*Bitmap) Flip

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

Flip performs 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) Reset

func (b *Bitmap) Reset()

Reset reset the bitmap and the underlying containers for re-use.

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(others ...*Bitmap) *Bitmap

Union returns the bitwise union of b and others as a new bitmap.

func (*Bitmap) UnionInPlace

func (b *Bitmap) UnionInPlace(others ...*Bitmap)

UnionInPlace returns the bitwise union of b and others, modifying b in place.

func (*Bitmap) UnmarshalBinary

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

UnmarshalBinary decodes b from a binary-encoded byte slice. data can be in either official roaring format or Pilosa's roaring format.

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 Container

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

Container represents a Container for uint16 integers.

These are used for storing the low bits of numbers in larger sets of uint64. The high bits are stored in a Container's key which is tracked by a separate data structure. Integers in a Container can be encoded in one of three ways - the encoding used is usually whichever is most compact, though any Container type should be able to encode any set of integers safely. For containers with less than 4,096 values, an array is often used. Containers with long runs of integers would use run length encoding, and more random data usually uses bitmap encoding.

func NewContainer

func NewContainer() *Container

newContainer returns a new instance of container.

func NewContainerWithPooling

func NewContainerWithPooling(poolingConfig ContainerPoolingConfiguration) *Container

NewContainerWithPooling creates a new container with the provided pooling configuration.

func (*Container) Clone

func (c *Container) Clone() *Container

Clone returns a copy of c.

func (*Container) Contains

func (c *Container) Contains(v uint16) bool

Contains returns true if v is in the container.

func (*Container) Mapped

func (c *Container) Mapped() bool

Mapped returns true if the container is mapped directly to a byte slice

func (*Container) N

func (c *Container) N() int32

N returns the cached bit count of the container

func (*Container) Repair

func (c *Container) Repair()

Repair repairs the cardinality of c if it has been corrupted by optimized operations.

func (*Container) Reset

func (c *Container) Reset()

Reset the container so it can be reused while maintaining any allocated datastructures.

func (*Container) Update

func (c *Container) Update(containerType byte, n int32, mapped bool)

Update updates the container

func (*Container) WriteTo

func (c *Container) WriteTo(w io.Writer) (n int64, err error)

WriteTo writes c to w.

type ContainerIterator

type ContainerIterator interface {
	Next() bool
	Value() (uint64, *Container)
}

type ContainerPoolingConfiguration

type ContainerPoolingConfiguration struct {
	// Maximum size of the allocated array that will be maintained in the pool.
	MaxArraySize int
	// Whether a bitmap should be allocated for each pooled container.
	AllocateBitmap bool
	// Maximum size of the allocated runs that will be maintained in the pool.
	MaxRunsSize int

	// Maximum number of containers to pool.
	MaxCapacity int
	// Maximum size of keys and containers slice to maintain after calls to Reset().
	MaxKeysAndContainersSliceLength int
}

ContainerPoolingConfiguration represents the configuration for container pooling.

func NewDefaultContainerPoolingConfiguration

func NewDefaultContainerPoolingConfiguration(maxCapacity int) ContainerPoolingConfiguration

NewDefaultContainerPoolingConfiguration creates a ContainerPoolingConfiguration with default configuration.

type Containers

type Containers interface {
	// Get returns nil if the key does not exist.
	Get(key uint64) *Container

	// Put adds the container at key.
	Put(key uint64, c *Container)

	// PutContainerValues updates an existing container at key.
	// If a container does not exist for key, a new one is allocated.
	// TODO(2.0) make n  int32
	PutContainerValues(key uint64, containerType byte, n int, mapped bool)

	// Remove takes the container at key out.
	Remove(key uint64)

	// GetOrCreate returns the container at key, creating a new empty container if necessary.
	GetOrCreate(key uint64) *Container

	// Clone does a deep copy of Containers, including cloning all containers contained.
	Clone() Containers

	// Last returns the highest key and associated container.
	Last() (key uint64, c *Container)

	// Size returns the number of containers stored.
	Size() int

	// Iterator returns a Contiterator which after a call to Next(), a call to Value() will
	// return the first container at or after key. found will be true if a
	// container is found at key.
	Iterator(key uint64) (citer ContainerIterator, found bool)

	Count() uint64

	// Reset clears the containers collection to allow for recycling during snapshot
	Reset()

	// Repair will repair the cardinality of any containers whose cardinality were corrupted
	// due to optimized operations.
	Repair()
}

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

func (itr *Iterator) Reset(b *Bitmap)

Reset allows the iterator to be re-used between iterating different bitmaps so if frequent iteration is needed across different bitmaps, the same iterator can be reused.

func (*Iterator) Seek

func (itr *Iterator) Seek(seek uint64)

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

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL