README

roaring Build Status GoDoc GoDoc Go Report Card Build Status Go-CI Go-ARM-CI Go-Windows-CI

This is a go version of the Roaring bitmap data structure.

Roaring bitmaps are used by several major systems such as Apache Lucene and derivative systems such as Solr and Elasticsearch, Apache Druid (Incubating), LinkedIn Pinot, Netflix Atlas, Apache Spark, OpenSearchServer, Cloud Torrent, Whoosh, Pilosa, Microsoft Visual Studio Team Services (VSTS), and eBay's Apache Kylin. The YouTube SQL Engine, Google Procella, uses Roaring bitmaps for indexing.

Roaring bitmaps are found to work well in many important applications:

Use Roaring for bitmap compression whenever possible. Do not use other bitmap compression methods (Wang et al., SIGMOD 2017)

The roaring Go library is used by

This library is used in production in several systems, it is part of the Awesome Go collection.

There are also Java and C/C++ versions. The Java, C, C++ and Go version are binary compatible: e.g, you can save bitmaps from a Java program and load them back in Go, and vice versa. We have a format specification.

This code is licensed under Apache License, Version 2.0 (ASL2.0).

Copyright 2016-... by the authors.

When should you use a bitmap?

Sets are a fundamental abstraction in software. They can be implemented in various ways, as hash sets, as trees, and so forth. In databases and search engines, sets are often an integral part of indexes. For example, we may need to maintain a set of all documents or rows (represented by numerical identifier) that satisfy some property. Besides adding or removing elements from the set, we need fast functions to compute the intersection, the union, the difference between sets, and so on.

To implement a set of integers, a particularly appealing strategy is the bitmap (also called bitset or bit vector). Using n bits, we can represent any set made of the integers from the range [0,n): the ith bit is set to one if integer i is present in the set. Commodity processors use words of W=32 or W=64 bits. By combining many such words, we can support large values of n. Intersections, unions and differences can then be implemented as bitwise AND, OR and ANDNOT operations. More complicated set functions can also be implemented as bitwise operations.

When the bitset approach is applicable, it can be orders of magnitude faster than other possible implementation of a set (e.g., as a hash set) while using several times less memory.

However, a bitset, even a compressed one is not always applicable. For example, if the you have 1000 random-looking integers, then a simple array might be the best representation. We refer to this case as the "sparse" scenario.

When should you use compressed bitmaps?

An uncompressed BitSet can use a lot of memory. For example, if you take a BitSet and set the bit at position 1,000,000 to true and you have just over 100kB. That is over 100kB to store the position of one bit. This is wasteful even if you do not care about memory: suppose that you need to compute the intersection between this BitSet and another one that has a bit at position 1,000,001 to true, then you need to go through all these zeroes, whether you like it or not. That can become very wasteful.

This being said, there are definitively cases where attempting to use compressed bitmaps is wasteful. For example, if you have a small universe size. E.g., your bitmaps represent sets of integers from [0,n) where n is small (e.g., n=64 or n=128). If you are able to uncompressed BitSet and it does not blow up your memory usage, then compressed bitmaps are probably not useful to you. In fact, if you do not need compression, then a BitSet offers remarkable speed.

The sparse scenario is another use case where compressed bitmaps should not be used. Keep in mind that random-looking data is usually not compressible. E.g., if you have a small set of 32-bit random integers, it is not mathematically possible to use far less than 32 bits per integer, and attempts at compression can be counterproductive.

How does Roaring compares with the alternatives?

Most alternatives to Roaring are part of a larger family of compressed bitmaps that are run-length-encoded bitmaps. They identify long runs of 1s or 0s and they represent them with a marker word. If you have a local mix of 1s and 0, you use an uncompressed word.

There are many formats in this family:

  • Oracle's BBC is an obsolete format at this point: though it may provide good compression, it is likely much slower than more recent alternatives due to excessive branching.
  • WAH is a patented variation on BBC that provides better performance.
  • Concise is a variation on the patented WAH. It some specific instances, it can compress much better than WAH (up to 2x better), but it is generally slower.
  • EWAH is both free of patent, and it is faster than all the above. On the downside, it does not compress quite as well. It is faster because it allows some form of "skipping" over uncompressed words. So though none of these formats are great at random access, EWAH is better than the alternatives.

There is a big problem with these formats however that can hurt you badly in some cases: there is no random access. If you want to check whether a given value is present in the set, you have to start from the beginning and "uncompress" the whole thing. This means that if you want to intersect a big set with a large set, you still have to uncompress the whole big set in the worst case...

Roaring solves this problem. It works in the following manner. It divides the data into chunks of 216 integers (e.g., [0, 216), [216, 2 x 216), ...). Within a chunk, it can use an uncompressed bitmap, a simple list of integers, or a list of runs. Whatever format it uses, they all allow you to check for the present of any one value quickly (e.g., with a binary search). The net result is that Roaring can compute many operations much faster than run-length-encoded formats like WAH, EWAH, Concise... Maybe surprisingly, Roaring also generally offers better compression ratios.

References
  • Daniel Lemire, Owen Kaser, Nathan Kurz, Luca Deri, Chris O'Hara, François Saint-Jacques, Gregory Ssi-Yan-Kai, Roaring Bitmaps: Implementation of an Optimized Software Library, Software: Practice and Experience 48 (4), 2018 arXiv:1709.07821
  • Samy Chambi, Daniel Lemire, Owen Kaser, Robert Godin, Better bitmap performance with Roaring bitmaps, Software: Practice and Experience 46 (5), 2016. http://arxiv.org/abs/1402.6407 This paper used data from http://lemire.me/data/realroaring2014.html
  • Daniel Lemire, Gregory Ssi-Yan-Kai, Owen Kaser, Consistently faster and smaller compressed bitmaps with Roaring, Software: Practice and Experience 46 (11), 2016. http://arxiv.org/abs/1603.06549
Dependencies

Dependencies are fetched automatically by giving the -t flag to go get.

they include

  • github.com/willf/bitset
  • github.com/mschoch/smat
  • github.com/glycerine/go-unsnap-stream
  • github.com/philhofer/fwd
  • github.com/jtolds/gls

Note that the smat library requires Go 1.6 or better.

Installation
  • go get -t github.com/RoaringBitmap/roaring
Example

Here is a simplified but complete example:

package main

import (
    "fmt"
    "github.com/RoaringBitmap/roaring"
    "bytes"
)


func main() {
    // example inspired by https://github.com/fzandona/goroar
    fmt.Println("==roaring==")
    rb1 := roaring.BitmapOf(1, 2, 3, 4, 5, 100, 1000)
    fmt.Println(rb1.String())

    rb2 := roaring.BitmapOf(3, 4, 1000)
    fmt.Println(rb2.String())

    rb3 := roaring.New()
    fmt.Println(rb3.String())

    fmt.Println("Cardinality: ", rb1.GetCardinality())

    fmt.Println("Contains 3? ", rb1.Contains(3))

    rb1.And(rb2)

    rb3.Add(1)
    rb3.Add(5)

    rb3.Or(rb1)

    // computes union of the three bitmaps in parallel using 4 workers  
    roaring.ParOr(4, rb1, rb2, rb3)
    // computes intersection of the three bitmaps in parallel using 4 workers  
    roaring.ParAnd(4, rb1, rb2, rb3)


    // prints 1, 3, 4, 5, 1000
    i := rb3.Iterator()
    for i.HasNext() {
        fmt.Println(i.Next())
    }
    fmt.Println()

    // next we include an example of serialization
    buf := new(bytes.Buffer)
    rb1.WriteTo(buf) // we omit error handling
    newrb:= roaring.New()
    newrb.ReadFrom(buf)
    if rb1.Equals(newrb) {
    	fmt.Println("I wrote the content to a byte stream and read it back.")
    }
    // you can iterate over bitmaps using ReverseIterator(), Iterator, ManyIterator()
}

If you wish to use serialization and handle errors, you might want to consider the following sample of code:

	rb := BitmapOf(1, 2, 3, 4, 5, 100, 1000)
	buf := new(bytes.Buffer)
	size,err:=rb.WriteTo(buf)
	if err != nil {
		t.Errorf("Failed writing")
	}
	newrb:= New()
	size,err=newrb.ReadFrom(buf)
	if err != nil {
		t.Errorf("Failed reading")
	}
	if ! rb.Equals(newrb) {
		t.Errorf("Cannot retrieve serialized version")
	}

Given N integers in [0,x), then the serialized size in bytes of a Roaring bitmap should never exceed this bound:

8 + 9 * ((long)x+65535)/65536 + 2 * N

That is, given a fixed overhead for the universe size (x), Roaring bitmaps never use more than 2 bytes per integer. You can call BoundSerializedSizeInBytes for a more precise estimate.

64-bit Roaring

By default, roaring is used to stored unsigned 32-bit integers. However, we also offer an extension dedicated to 64-bit integers. It supports roughly the same functions:

package main

import (
    "fmt"
    "github.com/RoaringBitmap/roaring/roaring64"
    "bytes"
)


func main() {
    // example inspired by https://github.com/fzandona/goroar
    fmt.Println("==roaring64==")
    rb1 := roaring64.BitmapOf(1, 2, 3, 4, 5, 100, 1000)
    fmt.Println(rb1.String())

    rb2 := roaring64.BitmapOf(3, 4, 1000)
    fmt.Println(rb2.String())

    rb3 := roaring64.New()
    fmt.Println(rb3.String())

    fmt.Println("Cardinality: ", rb1.GetCardinality())

    fmt.Println("Contains 3? ", rb1.Contains(3))

    rb1.And(rb2)

    rb3.Add(1)
    rb3.Add(5)

    rb3.Or(rb1)



    // prints 1, 3, 4, 5, 1000
    i := rb3.Iterator()
    for i.HasNext() {
        fmt.Println(i.Next())
    }
    fmt.Println()

    // next we include an example of serialization
    buf := new(bytes.Buffer)
    rb1.WriteTo(buf) // we omit error handling
    newrb:= roaring64.New()
    newrb.ReadFrom(buf)
    if rb1.Equals(newrb) {
    	fmt.Println("I wrote the content to a byte stream and read it back.")
    }
    // you can iterate over bitmaps using ReverseIterator(), Iterator, ManyIterator()
}

Only the 32-bit roaring format is standard and cross-operable between Java, C++, C and Go. There is no guarantee that the 64-bit versions are compatible.

Documentation

Current documentation is available at http://godoc.org/github.com/RoaringBitmap/roaring and http://godoc.org/github.com/RoaringBitmap/roaring64

Goroutine safety

In general, it should not generally be considered safe to access the same bitmaps using different goroutines--they are left unsynchronized for performance. Should you want to access a Bitmap from more than one goroutine, you should provide synchronization. Typically this is done by using channels to pass the *Bitmap around (in Go style; so there is only ever one owner), or by using sync.Mutex to serialize operations on Bitmaps.

Coverage

We test our software. For a report on our test coverage, see

https://coveralls.io/github/RoaringBitmap/roaring?branch=master

Benchmark

Type

     go test -bench Benchmark -run -

To run benchmarks on Real Roaring Datasets run the following:

go get github.com/RoaringBitmap/real-roaring-datasets
BENCH_REAL_DATA=1 go test -bench BenchmarkRealData -run -
Iterative use

You can use roaring with gore:

  • go get -u github.com/motemen/gore
  • Make sure that $GOPATH/bin is in your $PATH.
  • go get github.com/RoaringBitmap/roaring
$ gore
gore version 0.2.6  :help for help
gore> :import github.com/RoaringBitmap/roaring
gore> x:=roaring.New()
gore> x.Add(1)
gore> x.String()
"{1}"
Fuzzy testing

You can help us test further the library with fuzzy testing:

     go get github.com/dvyukov/go-fuzz/go-fuzz
     go get github.com/dvyukov/go-fuzz/go-fuzz-build
     go test -tags=gofuzz -run=TestGenerateSmatCorpus
     go-fuzz-build github.com/RoaringBitmap/roaring
     go-fuzz -bin=./roaring-fuzz.zip -workdir=workdir/ -timeout=200

Let it run, and if the # of crashers is > 0, check out the reports in the workdir where you should be able to find the panic goroutine stack traces.

Alternative in Go

There is a Go version wrapping the C/C++ implementation https://github.com/RoaringBitmap/gocroaring

For an alternative implementation in Go, see https://github.com/fzandona/goroar The two versions were written independently.

Mailing list/discussion group

https://groups.google.com/forum/#!forum/roaring-bitmaps

Expand ▾ Collapse ▴

Documentation

Overview

    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

    Constants

    View Source
    const (
    
    	// MaxUint32 is the largest uint32 value.
    	MaxUint32 = math.MaxUint32
    
    	// 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 = math.MaxUint16
    )

    Variables

    This section is empty.

    Functions

    func BoundSerializedSizeInBytes

    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)

      Types

      type Bitmap

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

        Bitmap represents a compressed bitmap where you can add integers.

        func AddOffset

        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 AddOffset64

          func AddOffset64(x *Bitmap, offset int64) (answer *Bitmap)

            AddOffset64 adds the value 'offset' to each and every value in a bitmap, generating a new bitmap in the process If offset + element is outside of the range [0,2^32), that the element will be dropped

            func And

            func And(x1, x2 *Bitmap) *Bitmap

              And computes the intersection between two bitmaps and returns the result

              func AndNot

              func AndNot(x1, x2 *Bitmap) *Bitmap

                AndNot computes the difference between two bitmaps and returns the result

                func BitmapOf

                func BitmapOf(dat ...uint32) *Bitmap

                  BitmapOf generates a new bitmap filled with the specified integers

                  func FastAnd

                  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

                    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

                      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

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

                          FlipInt calls Flip after casting the parameters (convenience method)

                          func HeapOr

                          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

                            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

                              func New() *Bitmap

                                New creates a new empty Bitmap (same as NewBitmap)

                                func NewBitmap

                                func NewBitmap() *Bitmap

                                  NewBitmap creates a new empty Bitmap (see also New)

                                  func Or

                                  func Or(x1, x2 *Bitmap) *Bitmap

                                    Or computes the union between two bitmaps and returns the result

                                    func ParAnd

                                    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

                                      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

                                        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

                                          func Xor(x1, x2 *Bitmap) *Bitmap

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

                                            func (*Bitmap) Add

                                            func (rb *Bitmap) Add(x uint32)

                                              Add the integer x to the bitmap

                                              func (*Bitmap) AddInt

                                              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

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

                                                  AddMany add all of the values in dat

                                                  func (*Bitmap) AddRange

                                                  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

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

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

                                                      func (*Bitmap) AndAny

                                                      func (x1 *Bitmap) AndAny(bitmaps ...*Bitmap)

                                                        AndAny provides a result equivalent to x1.And(FastOr(bitmaps)). It's optimized to minimize allocations. It also might be faster than separate calls.

                                                        func (*Bitmap) AndCardinality

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

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

                                                          func (*Bitmap) AndNot

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

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

                                                            func (*Bitmap) CheckedAdd

                                                            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

                                                              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

                                                                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

                                                                  func (rb *Bitmap) Clone() *Bitmap

                                                                    Clone creates a copy of the Bitmap

                                                                    func (*Bitmap) CloneCopyOnWriteContainers

                                                                    func (rb *Bitmap) CloneCopyOnWriteContainers()

                                                                      CloneCopyOnWriteContainers clones all containers which have needCopyOnWrite set to true. This can be used to make sure it is safe to munmap a []byte that the roaring array may still have a reference to, after calling FromBuffer. More generally this function is useful if you call FromBuffer to construct a bitmap with a backing array buf and then later discard the buf array. Note that you should call CloneCopyOnWriteContainers on all bitmaps that were derived from the 'FromBuffer' bitmap since they map have dependencies on the buf array as well.

                                                                      func (*Bitmap) Contains

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

                                                                        Contains returns true if the integer is contained in the bitmap

                                                                        func (*Bitmap) ContainsInt

                                                                        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

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

                                                                            Equals returns true if the two bitmaps contain the same integers

                                                                            func (*Bitmap) Flip

                                                                            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

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

                                                                                FlipInt calls Flip after casting the parameters (convenience method)

                                                                                func (*Bitmap) FromBase64

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

                                                                                  FromBase64 deserializes a bitmap from Base64

                                                                                  func (*Bitmap) FromBuffer

                                                                                  func (rb *Bitmap) FromBuffer(buf []byte) (p int64, err 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).

                                                                                    If buf becomes unavailable, then a bitmap created with FromBuffer would be effectively broken. Furthermore, any bitmap derived from this bitmap (e.g., via Or, And) might also be broken. Thus, before making buf unavailable, you should call CloneCopyOnWriteContainers on all such bitmaps.

                                                                                    func (*Bitmap) GetCardinality

                                                                                    func (rb *Bitmap) GetCardinality() uint64

                                                                                      GetCardinality returns the number of integers contained in the bitmap

                                                                                      func (*Bitmap) GetCopyOnWrite

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

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

                                                                                        func (*Bitmap) GetSerializedSizeInBytes

                                                                                        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

                                                                                          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

                                                                                            func (rb *Bitmap) HasRunCompression() bool

                                                                                              HasRunCompression returns true if the bitmap benefits from run compression

                                                                                              func (*Bitmap) Intersects

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

                                                                                                Intersects checks whether two bitmap intersects, bitmaps are not modified

                                                                                                func (*Bitmap) IsEmpty

                                                                                                func (rb *Bitmap) IsEmpty() bool

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

                                                                                                  func (*Bitmap) Iterate

                                                                                                  func (rb *Bitmap) Iterate(cb func(x uint32) bool)

                                                                                                    Iterate iterates over the bitmap, calling the given callback with each value in the bitmap. If the callback returns false, the iteration is halted. The iteration results are undefined if the bitmap is modified (e.g., with Add or Remove). There is no guarantee as to what order the values will be iterated

                                                                                                    func (*Bitmap) Iterator

                                                                                                    func (rb *Bitmap) Iterator() IntPeekable

                                                                                                      Iterator creates a new IntPeekable 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

                                                                                                      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

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

                                                                                                          MarshalBinary implements the encoding.BinaryMarshaler interface for the bitmap (same as ToBytes)

                                                                                                          func (*Bitmap) Maximum

                                                                                                          func (rb *Bitmap) Maximum() uint32

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

                                                                                                            func (*Bitmap) Minimum

                                                                                                            func (rb *Bitmap) Minimum() uint32

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

                                                                                                              func (*Bitmap) Or

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

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

                                                                                                                func (*Bitmap) OrCardinality

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

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

                                                                                                                  func (*Bitmap) Rank

                                                                                                                  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()). If you pass the smallest value, you get the value 1. If you pass a value that is smaller than the smallest value, you get 0. Note that this function differs in convention from the Select function since it return 1 and not 0 on the smallest value.

                                                                                                                    func (*Bitmap) ReadFrom

                                                                                                                    func (rb *Bitmap) ReadFrom(reader io.Reader) (p int64, err 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

                                                                                                                      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

                                                                                                                        func (rb *Bitmap) Remove(x uint32)

                                                                                                                          Remove the integer x from the bitmap

                                                                                                                          func (*Bitmap) RemoveRange

                                                                                                                          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

                                                                                                                            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

                                                                                                                              func (rb *Bitmap) RunOptimize()

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

                                                                                                                                func (*Bitmap) Select

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

                                                                                                                                  Select returns the xth integer in the bitmap. If you pass 0, you get the smallest element. Note that this function differs in convention from the Rank function which returns 1 on the smallest value.

                                                                                                                                  func (*Bitmap) SetCopyOnWrite

                                                                                                                                  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

                                                                                                                                    func (rb *Bitmap) Stats() Statistics

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

                                                                                                                                      func (*Bitmap) String

                                                                                                                                      func (rb *Bitmap) String() string

                                                                                                                                        String creates a string representation of the Bitmap

                                                                                                                                        func (*Bitmap) ToArray

                                                                                                                                        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

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

                                                                                                                                            ToBase64 serializes a bitmap as Base64

                                                                                                                                            func (*Bitmap) ToBytes

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

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

                                                                                                                                              func (*Bitmap) UnmarshalBinary

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

                                                                                                                                                UnmarshalBinary implements the encoding.BinaryUnmarshaler interface for the bitmap

                                                                                                                                                func (*Bitmap) WriteTo

                                                                                                                                                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

                                                                                                                                                  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

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

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

                                                                                                                                                      type IntIterable

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

                                                                                                                                                        IntIterable allows you to iterate over the values in a Bitmap

                                                                                                                                                        type IntPeekable

                                                                                                                                                        type IntPeekable interface {
                                                                                                                                                        	IntIterable
                                                                                                                                                        	// PeekNext peeks the next value without advancing the iterator
                                                                                                                                                        	PeekNext() uint32
                                                                                                                                                        	// AdvanceIfNeeded advances as long as the next value is smaller than minval
                                                                                                                                                        	AdvanceIfNeeded(minval uint32)
                                                                                                                                                        }

                                                                                                                                                          IntPeekable allows you to look at the next value without advancing and advance as long as the next value is smaller than minval

                                                                                                                                                          type ManyIntIterable

                                                                                                                                                          type ManyIntIterable interface {
                                                                                                                                                          	// NextMany fills buf up with values, returns how many values were returned
                                                                                                                                                          	NextMany(buf []uint32) int
                                                                                                                                                          	// NextMany64 fills up buf with 64 bit values, uses hs as a mask (OR), returns how many values were returned
                                                                                                                                                          	NextMany64(hs uint64, buf []uint64) int
                                                                                                                                                          }

                                                                                                                                                            ManyIntIterable allows you to iterate over the values in a Bitmap

                                                                                                                                                            type Statistics

                                                                                                                                                            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.

                                                                                                                                                              Directories

                                                                                                                                                              Path Synopsis