roaring: github.com/RoaringBitmap/roaring Index | Files

package roaring

import "github.com/RoaringBitmap/roaring"

Package roaring is an implementation of Roaring Bitmaps in Go. They provide fast compressed bitmap data structures (also called bitset). They are ideally suited to represent sets of integers over relatively small ranges. See http://roaringbitmap.org for details.

Index

Package Files

arraycontainer.go arraycontainer_gen.go bitmapcontainer.go bitmapcontainer_gen.go clz.go ctz.go fastaggregation.go manyiterator.go parallel.go popcnt.go popcnt_generic.go popcnt_slices.go priorityqueue.go roaring.go roaringarray.go roaringarray_gen.go runcontainer.go runcontainer_gen.go serialization.go serialization_littleendian.go setutil.go shortiterator.go util.go

Constants

const (

    // MaxUint32 is the largest uint32 value.
    MaxUint32 = 4294967295

    // MaxRange is One more than the maximum allowed bitmap bit index. For use as an upper
    // bound for ranges.
    MaxRange uint64 = MaxUint32 + 1

    // MaxUint16 is the largest 16 bit unsigned int.
    // This is the largest value an interval16 can store.
    MaxUint16 = 65535
)

func BoundSerializedSizeInBytes Uses

func BoundSerializedSizeInBytes(cardinality uint64, universeSize uint64) uint64

BoundSerializedSizeInBytes returns an upper bound on the serialized size in bytes assuming that one wants to store "cardinality" integers in [0, universe_size)

type Bitmap Uses

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

Bitmap represents a compressed bitmap where you can add integers.

func AddOffset Uses

func AddOffset(x *Bitmap, offset uint32) (answer *Bitmap)

AddOffset adds the value 'offset' to each and every value in a bitmap, generating a new bitmap in the process

func And Uses

func And(x1, x2 *Bitmap) *Bitmap

And computes the intersection between two bitmaps and returns the result

func AndNot Uses

func AndNot(x1, x2 *Bitmap) *Bitmap

AndNot computes the difference between two bitmaps and returns the result

func BitmapOf Uses

func BitmapOf(dat ...uint32) *Bitmap

BitmapOf generates a new bitmap filled with the specified integers

func FastAnd Uses

func FastAnd(bitmaps ...*Bitmap) *Bitmap

FastAnd computes the intersection between many bitmaps quickly Compared to the And function, it can take many bitmaps as input, thus saving the trouble of manually calling "And" many times.

func FastOr Uses

func FastOr(bitmaps ...*Bitmap) *Bitmap

FastOr computes the union between many bitmaps quickly, as opposed to having to call Or repeatedly. It might also be faster than calling Or repeatedly.

func Flip Uses

func Flip(bm *Bitmap, rangeStart, rangeEnd uint64) *Bitmap

Flip negates the bits in the given range (i.e., [rangeStart,rangeEnd)), any integer present in this range and in the bitmap is removed, and any integer present in the range and not in the bitmap is added, a new bitmap is returned leaving the current bitmap unchanged. The function uses 64-bit parameters even though a Bitmap stores 32-bit values because it is allowed and meaningful to use [0,uint64(0x100000000)) as a range while uint64(0x100000000) cannot be represented as a 32-bit value.

func FlipInt Uses

func FlipInt(bm *Bitmap, rangeStart, rangeEnd int) *Bitmap

FlipInt calls Flip after casting the parameters (convenience method)

func HeapOr Uses

func HeapOr(bitmaps ...*Bitmap) *Bitmap

HeapOr computes the union between many bitmaps quickly using a heap. It might be faster than calling Or repeatedly.

func HeapXor Uses

func HeapXor(bitmaps ...*Bitmap) *Bitmap

HeapXor computes the symmetric difference between many bitmaps quickly (as opposed to calling Xor repeated). Internally, this function uses a heap. It might be faster than calling Xor repeatedly.

func New Uses

func New() *Bitmap

New creates a new empty Bitmap (same as NewBitmap)

func NewBitmap Uses

func NewBitmap() *Bitmap

NewBitmap creates a new empty Bitmap (see also New)

func Or Uses

func Or(x1, x2 *Bitmap) *Bitmap

Or computes the union between two bitmaps and returns the result

func ParAnd Uses

func ParAnd(parallelism int, bitmaps ...*Bitmap) *Bitmap

ParAnd computes the intersection (AND) of all provided bitmaps in parallel, where the parameter "parallelism" determines how many workers are to be used (if it is set to 0, a default number of workers is chosen)

func ParHeapOr Uses

func ParHeapOr(parallelism int, bitmaps ...*Bitmap) *Bitmap

ParHeapOr computes the union (OR) of all provided bitmaps in parallel, where the parameter "parallelism" determines how many workers are to be used (if it is set to 0, a default number of workers is chosen) ParHeapOr uses a heap to compute the union. For rare cases it might be faster than ParOr

func ParOr Uses

func ParOr(parallelism int, bitmaps ...*Bitmap) *Bitmap

ParOr computes the union (OR) of all provided bitmaps in parallel, where the parameter "parallelism" determines how many workers are to be used (if it is set to 0, a default number of workers is chosen)

func Xor Uses

func Xor(x1, x2 *Bitmap) *Bitmap

Xor computes the symmetric difference between two bitmaps and returns the result

func (*Bitmap) Add Uses

func (rb *Bitmap) Add(x uint32)

Add the integer x to the bitmap

func (*Bitmap) AddInt Uses

func (rb *Bitmap) AddInt(x int)

AddInt adds the integer x to the bitmap (convenience method: the parameter is casted to uint32 and we call Add)

func (*Bitmap) AddMany Uses

func (rb *Bitmap) AddMany(dat []uint32)

AddMany add all of the values in dat

func (*Bitmap) AddRange Uses

func (rb *Bitmap) AddRange(rangeStart, rangeEnd uint64)

AddRange adds the integers in [rangeStart, rangeEnd) to the bitmap. The function uses 64-bit parameters even though a Bitmap stores 32-bit values because it is allowed and meaningful to use [0,uint64(0x100000000)) as a range while uint64(0x100000000) cannot be represented as a 32-bit value.

func (*Bitmap) And Uses

func (rb *Bitmap) And(x2 *Bitmap)

And computes the intersection between two bitmaps and stores the result in the current bitmap

func (*Bitmap) AndCardinality Uses

func (rb *Bitmap) AndCardinality(x2 *Bitmap) uint64

AndCardinality returns the cardinality of the intersection between two bitmaps, bitmaps are not modified

func (*Bitmap) AndNot Uses

func (rb *Bitmap) AndNot(x2 *Bitmap)

AndNot computes the difference between two bitmaps and stores the result in the current bitmap

func (*Bitmap) CheckedAdd Uses

func (rb *Bitmap) CheckedAdd(x uint32) bool

CheckedAdd adds the integer x to the bitmap and return true if it was added (false if the integer was already present)

func (*Bitmap) CheckedRemove Uses

func (rb *Bitmap) CheckedRemove(x uint32) bool

CheckedRemove removes the integer x from the bitmap and return true if the integer was effectively remove (and false if the integer was not present)

func (*Bitmap) Clear Uses

func (rb *Bitmap) Clear()

Clear resets the Bitmap to be logically empty, but may retain some memory allocations that may speed up future operations

func (*Bitmap) Clone Uses

func (rb *Bitmap) Clone() *Bitmap

Clone creates a copy of the Bitmap

func (*Bitmap) Contains Uses

func (rb *Bitmap) Contains(x uint32) bool

Contains returns true if the integer is contained in the bitmap

func (*Bitmap) ContainsInt Uses

func (rb *Bitmap) ContainsInt(x int) bool

ContainsInt returns true if the integer is contained in the bitmap (this is a convenience method, the parameter is casted to uint32 and Contains is called)

func (*Bitmap) Equals Uses

func (rb *Bitmap) Equals(o interface{}) bool

Equals returns true if the two bitmaps contain the same integers

func (*Bitmap) Flip Uses

func (rb *Bitmap) Flip(rangeStart, rangeEnd uint64)

Flip negates the bits in the given range (i.e., [rangeStart,rangeEnd)), any integer present in this range and in the bitmap is removed, and any integer present in the range and not in the bitmap is added. The function uses 64-bit parameters even though a Bitmap stores 32-bit values because it is allowed and meaningful to use [0,uint64(0x100000000)) as a range while uint64(0x100000000) cannot be represented as a 32-bit value.

func (*Bitmap) FlipInt Uses

func (rb *Bitmap) FlipInt(rangeStart, rangeEnd int)

FlipInt calls Flip after casting the parameters (convenience method)

func (*Bitmap) FromBase64 Uses

func (rb *Bitmap) FromBase64(str string) (int64, error)

FromBase64 deserializes a bitmap from Base64

func (*Bitmap) FromBuffer Uses

func (rb *Bitmap) FromBuffer(buf []byte) (int64, error)

FromBuffer creates a bitmap from its serialized version stored in buffer

The format specification is available here: https://github.com/RoaringBitmap/RoaringFormatSpec

The provided byte array (buf) is expected to be a constant. The function makes the best effort attempt not to copy data. You should take care not to modify buff as it will likely result in unexpected program behavior.

Resulting bitmaps are effectively immutable in the following sense: a copy-on-write marker is used so that when you modify the resulting bitmap, copies of selected data (containers) are made. You should *not* change the copy-on-write status of the resulting bitmaps (SetCopyOnWrite).

func (*Bitmap) GetCardinality Uses

func (rb *Bitmap) GetCardinality() uint64

GetCardinality returns the number of integers contained in the bitmap

func (*Bitmap) GetCopyOnWrite Uses

func (rb *Bitmap) GetCopyOnWrite() (val bool)

GetCopyOnWrite gets this bitmap's copy-on-write property

func (*Bitmap) GetSerializedSizeInBytes Uses

func (rb *Bitmap) GetSerializedSizeInBytes() uint64

GetSerializedSizeInBytes computes the serialized size in bytes of the Bitmap. It should correspond to the number of bytes written when invoking WriteTo. You can expect that this function is much cheaper computationally than WriteTo.

func (*Bitmap) GetSizeInBytes Uses

func (rb *Bitmap) GetSizeInBytes() uint64

GetSizeInBytes estimates the memory usage of the Bitmap. Note that this might differ slightly from the amount of bytes required for persistent storage

func (*Bitmap) HasRunCompression Uses

func (rb *Bitmap) HasRunCompression() bool

HasRunCompression returns true if the bitmap benefits from run compression

func (*Bitmap) Intersects Uses

func (rb *Bitmap) Intersects(x2 *Bitmap) bool

Intersects checks whether two bitmap intersects, bitmaps are not modified

func (*Bitmap) IsEmpty Uses

func (rb *Bitmap) IsEmpty() bool

IsEmpty returns true if the Bitmap is empty (it is faster than doing (GetCardinality() == 0))

func (*Bitmap) Iterator Uses

func (rb *Bitmap) Iterator() IntIterable

Iterator creates a new IntIterable to iterate over the integers contained in the bitmap, in sorted order; the iterator becomes invalid if the bitmap is modified (e.g., with Add or Remove).

func (*Bitmap) ManyIterator Uses

func (rb *Bitmap) ManyIterator() ManyIntIterable

ManyIterator creates a new ManyIntIterable to iterate over the integers contained in the bitmap, in sorted order; the iterator becomes invalid if the bitmap is modified (e.g., with Add or Remove).

func (*Bitmap) MarshalBinary Uses

func (rb *Bitmap) MarshalBinary() ([]byte, error)

MarshalBinary implements the encoding.BinaryMarshaler interface for the bitmap

func (*Bitmap) Maximum Uses

func (rb *Bitmap) Maximum() uint32

Maximum get the largest value stored in this roaring bitmap, assumes that it is not empty

func (*Bitmap) Minimum Uses

func (rb *Bitmap) Minimum() uint32

Minimum get the smallest value stored in this roaring bitmap, assumes that it is not empty

func (*Bitmap) Or Uses

func (rb *Bitmap) Or(x2 *Bitmap)

Or computes the union between two bitmaps and stores the result in the current bitmap

func (*Bitmap) OrCardinality Uses

func (rb *Bitmap) OrCardinality(x2 *Bitmap) uint64

OrCardinality returns the cardinality of the union between two bitmaps, bitmaps are not modified

func (*Bitmap) Rank Uses

func (rb *Bitmap) Rank(x uint32) uint64

Rank returns the number of integers that are smaller or equal to x (Rank(infinity) would be GetCardinality())

func (*Bitmap) ReadFrom Uses

func (rb *Bitmap) ReadFrom(stream io.Reader) (int64, error)

ReadFrom reads a serialized version of this bitmap from stream. The format is compatible with other RoaringBitmap implementations (Java, C) and is documented here: https://github.com/RoaringBitmap/RoaringFormatSpec

func (*Bitmap) ReadFromMsgpack Uses

func (rb *Bitmap) ReadFromMsgpack(stream io.Reader) (int64, error)

Deprecated: ReadFromMsgpack reads a msgpack2/snappy-streaming serialized version of this bitmap from stream. The format is expected is that written by the WriteToMsgpack() call; see additional notes there.

func (*Bitmap) Remove Uses

func (rb *Bitmap) Remove(x uint32)

Remove the integer x from the bitmap

func (*Bitmap) RemoveRange Uses

func (rb *Bitmap) RemoveRange(rangeStart, rangeEnd uint64)

RemoveRange removes the integers in [rangeStart, rangeEnd) from the bitmap. The function uses 64-bit parameters even though a Bitmap stores 32-bit values because it is allowed and meaningful to use [0,uint64(0x100000000)) as a range while uint64(0x100000000) cannot be represented as a 32-bit value.

func (*Bitmap) ReverseIterator Uses

func (rb *Bitmap) ReverseIterator() IntIterable

ReverseIterator creates a new IntIterable to iterate over the integers contained in the bitmap, in sorted order; the iterator becomes invalid if the bitmap is modified (e.g., with Add or Remove).

func (*Bitmap) RunOptimize Uses

func (rb *Bitmap) RunOptimize()

RunOptimize attempts to further compress the runs of consecutive values found in the bitmap

func (*Bitmap) Select Uses

func (rb *Bitmap) Select(x uint32) (uint32, error)

Select returns the xth integer in the bitmap

func (*Bitmap) SetCopyOnWrite Uses

func (rb *Bitmap) SetCopyOnWrite(val bool)

SetCopyOnWrite sets this bitmap to use copy-on-write so that copies are fast and memory conscious if the parameter is true, otherwise we leave the default where hard copies are made (copy-on-write requires extra care in a threaded context). Calling SetCopyOnWrite(true) on a bitmap created with FromBuffer is unsafe.

func (*Bitmap) Stats Uses

func (rb *Bitmap) Stats() Statistics

Stats returns details on container type usage in a Statistics struct.

func (*Bitmap) String Uses

func (rb *Bitmap) String() string

String creates a string representation of the Bitmap

func (*Bitmap) ToArray Uses

func (rb *Bitmap) ToArray() []uint32

ToArray creates a new slice containing all of the integers stored in the Bitmap in sorted order

func (*Bitmap) ToBase64 Uses

func (rb *Bitmap) ToBase64() (string, error)

ToBase64 serializes a bitmap as Base64

func (*Bitmap) ToBytes Uses

func (rb *Bitmap) ToBytes() ([]byte, error)

ToBytes returns an array of bytes corresponding to what is written when calling WriteTo

func (*Bitmap) UnmarshalBinary Uses

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

UnmarshalBinary implements the encoding.BinaryUnmarshaler interface for the bitmap

func (*Bitmap) WriteTo Uses

func (rb *Bitmap) WriteTo(stream io.Writer) (int64, error)

WriteTo writes a serialized version of this bitmap to stream. The format is compatible with other RoaringBitmap implementations (Java, C) and is documented here: https://github.com/RoaringBitmap/RoaringFormatSpec

func (*Bitmap) WriteToMsgpack Uses

func (rb *Bitmap) WriteToMsgpack(stream io.Writer) (int64, error)

Deprecated: WriteToMsgpack writes a msgpack2/snappy-streaming compressed serialized version of this bitmap to stream. The format is not compatible with the WriteTo() format, and is experimental: it may produce smaller on disk footprint and/or be faster to read, depending on your content. Currently only the Go roaring implementation supports this format.

func (*Bitmap) Xor Uses

func (rb *Bitmap) Xor(x2 *Bitmap)

Xor computes the symmetric difference between two bitmaps and stores the result in the current bitmap

type IntIterable Uses

type IntIterable interface {
    HasNext() bool
    Next() uint32
}

IntIterable allows you to iterate over the values in a Bitmap

type ManyIntIterable Uses

type ManyIntIterable interface {
    // pass in a buffer to fill up with values, returns how many values were returned
    NextMany([]uint32) int
}

ManyIntIterable allows you to iterate over the values in a Bitmap

type Statistics Uses

type Statistics struct {
    Cardinality uint64
    Containers  uint64

    ArrayContainers      uint64
    ArrayContainerBytes  uint64
    ArrayContainerValues uint64

    BitmapContainers      uint64
    BitmapContainerBytes  uint64
    BitmapContainerValues uint64

    RunContainers      uint64
    RunContainerBytes  uint64
    RunContainerValues uint64
}

Statistics provides details on the container types in use.

Package roaring imports 19 packages (graph) and is imported by 55 packages. Updated 2019-01-10. Refresh now. Tools for package owners.