gocroaring

package module
v1.2.0 Latest Latest
Warning

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

 Go to latest Published: Nov 4, 2026 License: Apache-2.0 Imports: 9 Imported by: 1

README

gocroaring GoDoc Tests (Ubuntu, macOS)

Well-tested Go wrapper for CRoaring (a C/C++ implementation of Roaring Bitmaps)

Roaring bitmaps are used by several important systems:

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 original java version can be found at https://github.com/RoaringBitmap/RoaringBitmap

There is a native Go version at https://github.com/RoaringBitmap/roaring

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

Copyright 2016 by the authors.

Performance compared with the pure Go version

roaring is a native Go implementation of Roaring bitmaps. It avoids cgo, and it shares the same serialization format, so the two libraries can read each other's bitmaps. Which one is faster depends on how much work each call does.

gocroaring is faster on operations that do a lot of work per call. CRoaring uses SIMD instructions (AVX2, AVX-512, NEON) and allocates outside the Go heap.

  • 32-bit unions, intersections, differences and symmetric differences: 2x to 3x on average, and 10x to 17x on some shapes (runs, or a small bitmap against a large one). An in-place union of two bitmaps made of runs is over 100x faster.
  • Union of many bitmaps (FastOr): 5x to 10x.
  • Counting the size of a union without building it (OrCardinality): 1.5x to 12x.
  • Flip, RunOptimize, Equals, Clone, serialization and deserialization: 1.3x to 10x. Opening a serialized bitmap without copying it (ReadPortableFrozenView, compared with roaring's FromBuffer): 10x.
  • 64-bit set operations on clustered or dense values: 4x to 12x on x86-64 (but about even on the Apple M4).

roaring is faster on operations that do little work per call. Each call into gocroaring crosses the Go/C boundary, which costs about 40 ns.

  • Adding 32-bit values one at a time is 2.5x to 7x slower with gocroaring. Pass them all at once (Add(values...), New(values...)): then gocroaring is as fast or up to 1.3x faster.
  • Moving a NewIterator() one value per call (Next, Previous) is 5x to 20x slower. Read values in blocks instead (Iterator(), or Read and ReadBackward on a NewIterator(), or ToArray): then gocroaring is usually as fast as roaring or faster, though forward iteration over 32-bit values is 2x slower on the Apple M4.
  • Several 64-bit queries are slower in gocroaring: Rank (4x to 14x), Minimum/Maximum (about 15x), Intersects (about 8x) and, on sparse data, Select (2x to 4x). CRoaring walks its 64-bit tree linearly for rank and select.
  • 64-bit bitmaps with one value per 2^32 range (very sparse): most operations are 2x to 4x slower in gocroaring.

To reduce the cost of crossing into C, gocroaring answers short read-only 32-bit queries (Contains, Rank, Minimum, Maximum, Select, Intersect) in Go, reading the CRoaring data structures directly, on amd64 and arm64. On the Xeon below, Contains is then about 2x faster than in roaring. On the Apple M4, roaring remains up to 1.6x faster for Contains.

The numbers below come from the 190 benchmarks of benchmarks/compare. Each one runs the same work in both libraries, on the same data. They compare gocroaring (CRoaring 5.5.5) with roaring 2.30.0 on two machines:

  • x86-64: one core of a Xeon Gold 6548N (Emerald Rapids, AVX-512), Linux, Go 1.26.10;
  • arm64: an Apple M4 Max, macOS, Go 1.24.3.

Times are medians of 10 runs. Results of gocroaring operations are freed explicitly; roaring relies on the garbage collector, whose cost is included. The ratio is the roaring time divided by the gocroaring time: above 1, gocroaring is faster (in bold); below 1, roaring is faster. The wins–losses columns count the benchmarks where gocroaring is faster, and slower, by more than 5%. Each category is summarized by the geometric mean of its ratios; click a category below for its benchmarks.

category benchmarks x86-64 geometric mean x86-64 wins–losses arm64 geometric mean arm64 wins–losses
32-bit binary operations, new result 24 2.73 24–0 2.38 23–1
32-bit in-place operations 25 2.51 25–0 2.64 23–1
32-bit counts and intersection tests 18 2.57 11–6 2.32 12–4
Aggregating many bitmaps 2 4.02 2–0 2.48 2–0
32-bit point queries 18 1.43 13–2 1.08 6–9
32-bit whole-bitmap queries 6 2.16 6–0 2.52 6–0
32-bit updates and construction 12 1.04 7–4 0.78 5–6
32-bit iteration 11 0.65 5–5 0.65 5–5
32-bit serialization and zero-copy views 4 3.84 4–0 2.78 3–0
64-bit queries 19 0.45 8–8 0.48 5–14
64-bit iteration, construction and serialization 28 0.87 15–10 0.98 17–11
64-bit set operations 23 1.75 13–10 0.63 9–9
all 190 1.47 133–45 1.23 116–60
32-bit binary operations, new result (24 benchmarks)

Each pair of bitmaps is one of six shapes: ArrayArray (200k values each over 2^28), SmallArrayBigArray (2k against 900k over 2^24), BitsetBitset (2M each over 2^22), ArrayBitset (30k against 2M over 2^22), RunRun (20k runs each over 2^26) and RunArray.

benchmark x86-64 gocroaring x86-64 roaring ratio arm64 gocroaring arm64 roaring ratio
And / ArrayArray 532 µs 1.86 ms 3.50 932 µs 1.07 ms 1.15
And / SmallArrayBigArray 41.9 µs 120 µs 2.87 36 µs 30.1 µs 0.84
And / BitsetBitset 32.7 µs 83.5 µs 2.55 27.9 µs 50.9 µs 1.83
And / ArrayBitset 26.4 µs 44.9 µs 1.70 18 µs 30.2 µs 1.68
And / RunRun 314 µs 641 µs 2.04 95.5 µs 343 µs 3.59
And / RunArray 626 µs 686 µs 1.09 200 µs 263 µs 1.31
Or / ArrayArray 1.22 ms 2.36 ms 1.93 997 µs 1.19 ms 1.19
Or / SmallArrayBigArray 191 µs 1.25 ms 6.53 82.4 µs 431 µs 5.23
Or / BitsetBitset 31.2 µs 79.4 µs 2.55 21.5 µs 45.9 µs 2.13
Or / ArrayBitset 39.6 µs 117 µs 2.94 37 µs 55.4 µs 1.50
Or / RunRun 333 µs 620 µs 1.86 117 µs 253 µs 2.17
Or / RunArray 759 µs 1.51 ms 1.99 369 µs 878 µs 2.38
Xor / ArrayArray 1.21 ms 2.15 ms 1.78 1.03 ms 1.41 ms 1.37
Xor / SmallArrayBigArray 189 µs 1.11 ms 5.91 80.7 µs 847 µs 10
Xor / BitsetBitset 32.2 µs 84.8 µs 2.63 22.4 µs 49.9 µs 2.23
Xor / ArrayBitset 55.4 µs 120 µs 2.17 40.5 µs 58.3 µs 1.44
Xor / RunRun 380 µs 4.3 ms 11 118 µs 2.02 ms 17
Xor / RunArray 1.7 ms 4.68 ms 2.76 984 µs 2.75 ms 2.79
AndNot / ArrayArray 788 µs 2.02 ms 2.56 920 µs 1.27 ms 1.38
AndNot / SmallArrayBigArray 82.5 µs 696 µs 8.44 53.4 µs 583 µs 11
AndNot / BitsetBitset 30.2 µs 82.8 µs 2.74 21.9 µs 51.9 µs 2.37
AndNot / ArrayBitset 28.3 µs 43.1 µs 1.52 17.9 µs 24.9 µs 1.39
AndNot / RunRun 324 µs 458 µs 1.41 113 µs 178 µs 1.58
AndNot / RunArray 1.17 ms 4.27 ms 3.65 579 µs 2.59 ms 4.47
32-bit in-place operations (25 benchmarks)

The first bitmap is cloned, then modified in place; the clone is part of the measured work in both libraries. OrInPlace merges 500 values into a copy of 2M values.

benchmark x86-64 gocroaring x86-64 roaring ratio arm64 gocroaring arm64 roaring ratio
And / ArrayArray 794 µs 1.99 ms 2.51 992 µs 1.12 ms 1.13
Or / ArrayArray 1.76 ms 2.53 ms 1.44 1.28 ms 1.33 ms 1.04
Xor / ArrayArray 1.52 ms 2.34 ms 1.53 1.17 ms 1.52 ms 1.30
AndNot / ArrayArray 1.64 ms 2.07 ms 1.26 963 µs 1.33 ms 1.38
And / SmallArrayBigArray 52 µs 121 µs 2.33 35.3 µs 30.7 µs 0.87
Or / SmallArrayBigArray 732 µs 1.32 ms 1.80 89.9 µs 458 µs 5.10
Xor / SmallArrayBigArray 298 µs 1.13 ms 3.79 86.5 µs 830 µs 9.60
AndNot / SmallArrayBigArray 83.8 µs 691 µs 8.24 52.4 µs 581 µs 11
And / BitsetBitset 41.5 µs 92.6 µs 2.23 31 µs 53 µs 1.71
Or / BitsetBitset 38.5 µs 91.6 µs 2.38 24.3 µs 52 µs 2.14
Xor / BitsetBitset 37.8 µs 94.6 µs 2.50 24.3 µs 58.4 µs 2.40
AndNot / BitsetBitset 38.1 µs 94.1 µs 2.47 24.2 µs 59 µs 2.43
And / ArrayBitset 30.2 µs 42.7 µs 1.41 20.6 µs 25.9 µs 1.25
Or / ArrayBitset 47.3 µs 126 µs 2.67 40.5 µs 55.9 µs 1.38
Xor / ArrayBitset 61.3 µs 109 µs 1.77 42.2 µs 72.1 µs 1.71
AndNot / ArrayBitset 33.4 µs 40.9 µs 1.22 18.1 µs 25.6 µs 1.41
And / RunRun 375 µs 697 µs 1.86 132 µs 369 µs 2.79
Or / RunRun 391 µs 47.4 ms 121 156 µs 28 ms 179
Xor / RunRun 451 µs 3.04 ms 6.76 142 µs 1.55 ms 11
AndNot / RunRun 390 µs 503 µs 1.29 143 µs 200 µs 1.40
And / RunArray 688 µs 725 µs 1.05 253 µs 290 µs 1.15
Or / RunArray 823 µs 1.5 ms 1.82 393 µs 880 µs 2.24
Xor / RunArray 1.82 ms 3.52 ms 1.93 1 ms 2.53 ms 2.52
AndNot / RunArray 1.31 ms 6.09 ms 4.64 617 µs 4.17 ms 6.75
OrInPlace 1.07 ms 1.23 ms 1.15 436 µs 511 µs 1.17
32-bit counts and intersection tests (18 benchmarks)

Same pairs as the binary operations. Intersects stops at the first common value.

benchmark x86-64 gocroaring x86-64 roaring ratio arm64 gocroaring arm64 roaring ratio
OrCardinality / ArrayArray 426 µs 2.23 ms 5.24 762 µs 1.17 ms 1.54
OrCardinality / SmallArrayBigArray 102 µs 1.21 ms 12 55.1 µs 434 µs 7.87
OrCardinality / BitsetBitset 8.11 µs 74.9 µs 9.24 11.7 µs 44.3 µs 3.79
OrCardinality / ArrayBitset 19.8 µs 111 µs 5.61 11 µs 52.2 µs 4.73
OrCardinality / RunRun 235 µs 624 µs 2.66 74.6 µs 267 µs 3.58
OrCardinality / RunArray 546 µs 1.55 ms 2.84 116 µs 951 µs 8.20
AndCardinality / ArrayArray 410 µs 1.67 ms 4.06 751 µs 933 µs 1.24
AndCardinality / SmallArrayBigArray 102 µs 98.7 µs 0.97 54.2 µs 22.7 µs 0.42
AndCardinality / BitsetBitset 7.98 µs 7.55 µs 0.95 11.6 µs 12.1 µs 1.04
AndCardinality / ArrayBitset 19.8 µs 21.6 µs 1.09 10.9 µs 15 µs 1.37
AndCardinality / RunRun 202 µs 548 µs 2.72 62.8 µs 277 µs 4.41
AndCardinality / RunArray 516 µs 397 µs 0.77 116 µs 181 µs 1.57
Intersects / ArrayArray 178 ns 138 ns 0.77 117 ns 69.3 ns 0.59
Intersects / SmallArrayBigArray 69.2 ns 44.7 ns 0.65 50.2 ns 25.5 ns 0.51
Intersects / BitsetBitset 6.22 ns 4.96 ns 0.80 4.32 ns 3.51 ns 0.81
Intersects / ArrayBitset 6.77 ns 6.19 ns 0.92 4.47 ns 4.64 ns 1.04
Intersects / RunRun 8.54 ns 361 ns 42 5.76 ns 233 ns 40
Intersects / RunArray 27.3 ns 210 ns 7.67 15.6 ns 177 ns 11
Aggregating many bitmaps (2 benchmarks)

Union and symmetric difference of 200 bitmaps of 5000 values each.

benchmark x86-64 gocroaring x86-64 roaring ratio arm64 gocroaring arm64 roaring ratio
FastOr 8.27 ms 87.4 ms 11 9.23 ms 47.2 ms 5.11
FastXor 44.4 ms 68 ms 1.53 35.2 ms 42.4 ms 1.20
32-bit point queries (18 benchmarks)

Small: 1000 values in 4 containers; Sparse: 1M values over 2^26 (array containers); Dense: 2M over 2^22 (bitset containers); Runs: 20k runs. Probes cycle through 4096 values, half present. The rows without a shape use 1M values over 2^26.

benchmark x86-64 gocroaring x86-64 roaring ratio arm64 gocroaring arm64 roaring ratio
Contains / Small 19.2 ns 47.8 ns 2.49 12.1 ns 11.6 ns 0.96
Rank / Small 24.1 ns 46.8 ns 1.94 14.7 ns 12.3 ns 0.84
Select / Small 16.6 ns 13.3 ns 0.80 8.69 ns 5.62 ns 0.65
MinMax / Small 4.47 ns 4.65 ns 1.04 3.9 ns 3.87 ns 0.99
Contains / Sparse 52.8 ns 121 ns 2.29 42.5 ns 26.3 ns 0.62
Rank / Sparse 677 ns 980 ns 1.45 372 ns 678 ns 1.82
Select / Sparse 516 ns 830 ns 1.61 348 ns 972 ns 2.79
MinMax / Sparse 4.5 ns 4.63 ns 1.03 4.07 ns 3.88 ns 0.95
Contains / Dense 16.1 ns 30.6 ns 1.91 11.4 ns 8.1 ns 0.71
Rank / Dense 291 ns 106 ns 0.36 144 ns 96.4 ns 0.67
Select / Dense 275 ns 306 ns 1.12 162 ns 340 ns 2.10
MinMax / Dense 4.93 ns 5.61 ns 1.14 3.98 ns 3.46 ns 0.87
Contains / Runs 42 ns 83.6 ns 1.99 27.4 ns 20.9 ns 0.76
Rank / Runs 3.48 µs 9.43 µs 2.71 1.83 µs 3.37 µs 1.84
Select / Runs 3.47 µs 6.53 µs 1.88 1.84 µs 3.32 µs 1.80
MinMax / Runs 5.04 ns 4.99 ns 0.99 4.33 ns 3.93 ns 0.91
Contains 52.8 ns 116 ns 2.20 33.2 ns 24.7 ns 0.74
Rank 668 ns 966 ns 1.45 368 ns 650 ns 1.77
32-bit whole-bitmap queries (6 benchmarks)

Equals compares a bitmap with its clone.

benchmark x86-64 gocroaring x86-64 roaring ratio arm64 gocroaring arm64 roaring ratio
Equals / Small 107 ns 365 ns 3.41 80.7 ns 305 ns 3.79
Equals / Sparse 158 µs 337 µs 2.13 70.1 µs 277 µs 3.95
Equals / Dense 7.97 µs 25.6 µs 3.22 12.4 µs 18.6 µs 1.51
Equals / Runs 12.3 µs 20.9 µs 1.70 4.76 µs 12.7 µs 2.67
View / Cardinality 235 ns 385 ns 1.63 122 ns 233 ns 1.91
Cardinality 939 ns 1.49 µs 1.58 385 ns 859 ns 2.23
32-bit updates and construction (12 benchmarks)

RemoveAdd removes a present value and adds it back. AddOneByOne adds 50k values with one call each; AddMany builds from a slice of 1M values in one call. AddRemoveRange adds and removes 100k consecutive values.

benchmark x86-64 gocroaring x86-64 roaring ratio arm64 gocroaring arm64 roaring ratio
RemoveAdd / Small 132 ns 105 ns 0.80 127 ns 37.7 ns 0.30
RemoveAdd / Sparse 239 ns 240 ns 1.00 201 ns 93.3 ns 0.46
RemoveAdd / Dense 89.7 ns 38.4 ns 0.43 86.5 ns 22.9 ns 0.26
RemoveAdd / Runs 189 ns 219 ns 1.16 149 ns 97.4 ns 0.65
Ranges32 / AddRemoveRange 198 ns 333 ns 1.69 176 ns 212 ns 1.20
AddOneByOne / Random 2.41 ms 940 µs 0.39 1.93 ms 505 µs 0.26
AddOneByOne / Sorted 2 ms 305 µs 0.15 1.56 ms 215 µs 0.14
AddMany / Random 97.1 ms 127 ms 1.31 72.8 ms 85.9 ms 1.18
AddMany / Sorted 3.07 ms 3.33 ms 1.08 2.21 ms 2.19 ms 0.99
Flip 277 µs 2.67 ms 9.65 171 µs 1.19 ms 6.94
RunOptimize 2.59 ms 6 ms 2.32 1.22 ms 4.06 ms 3.34
Clone 303 µs 406 µs 1.34 85.6 µs 145 µs 1.69
32-bit iteration (11 benchmarks)

IterateBuffered and ReverseIterate read values in blocks of 256 (gocroaring Iterator / ReadBackward, roaring ManyIterator / ReverseIterator). ReverseIterateStepwise moves one value per call (gocroaring Iterator.Previous).

benchmark x86-64 gocroaring x86-64 roaring ratio arm64 gocroaring arm64 roaring ratio
ReverseIterate / Small 2.62 µs 4.99 µs 1.90 1.48 µs 2.88 µs 1.95
ReverseIterateStepwise / Small 38.8 µs 4.98 µs 0.13 30.8 µs 2.88 µs 0.09
ReverseIterate / Sparse 2.15 ms 4.9 ms 2.28 1.15 ms 2.77 ms 2.40
ReverseIterateStepwise / Sparse 38.3 ms 4.88 ms 0.13 30.9 ms 2.75 ms 0.09
ReverseIterate / Dense 6.88 ms 10.6 ms 1.54 2.83 ms 7.88 ms 2.79
ReverseIterateStepwise / Dense 60.2 ms 10.6 ms 0.18 49.9 ms 7.9 ms 0.16
ReverseIterate / Runs 11.7 ms 25.5 ms 2.17 4.08 ms 15.2 ms 3.72
ReverseIterateStepwise / Runs 181 ms 25.3 ms 0.14 153 ms 15.2 ms 0.10
IterateBuffered 830 µs 853 µs 1.03 1.36 ms 642 µs 0.47
IterateCallback 2.27 ms 2.06 ms 0.90 1.15 ms 1.12 ms 0.97
ToArray 621 µs 946 µs 1.52 106 µs 342 µs 3.23
32-bit serialization and zero-copy views (4 benchmarks)

Both libraries write the same portable format (checked byte for byte). Views open a serialized bitmap without copying it: ReadPortableFrozenView in gocroaring, FromBuffer in roaring.

benchmark x86-64 gocroaring x86-64 roaring ratio arm64 gocroaring arm64 roaring ratio
View / Open 629 ns 6.37 µs 10 351 ns 3.83 µs 11
View / Contains 16.7 ns 37.7 ns 2.26 10.5 ns 10.2 ns 0.98
Serialize 48.9 µs 118 µs 2.41 16 µs 34.4 µs 2.15
Deserialize 18.9 µs 74.6 µs 3.96 12.8 µs 33.4 µs 2.61
64-bit queries (19 benchmarks)

Sparse: 1M values over 2^48 (one value per container); Clustered: 1M values in 64 clusters over 2^40; Dense: 1M values over 2^26. 64Contains uses 300k values over 2^40.

benchmark x86-64 gocroaring x86-64 roaring ratio arm64 gocroaring arm64 roaring ratio
Contains / Sparse 105 ns 166 ns 1.58 88.3 ns 40.2 ns 0.46
Rank / Sparse 44.9 ms 2.96 ms 0.07 30.6 ms 3.19 ms 0.10
Select / Sparse 38.8 ms 10.8 ms 0.28 27.6 ms 11.8 ms 0.43
MinMax / Sparse 115 ns 7.23 ns 0.06 80.8 ns 5.6 ns 0.07
RemoveAdd / Sparse 318 ns 344 ns 1.08 223 ns 153 ns 0.69
Cardinality / Sparse 3.56 ms 6.62 ms 1.86 595 µs 8.36 ms 14
Contains / Clustered 67.9 ns 70.8 ns 1.04 61 ns 16.1 ns 0.26
Rank / Clustered 9.62 µs 868 ns 0.09 3.54 µs 638 ns 0.18
Select / Clustered 5.63 µs 2.69 µs 0.48 3.21 µs 1.91 µs 0.59
MinMax / Clustered 114 ns 7.09 ns 0.06 74.6 ns 5.6 ns 0.08
RemoveAdd / Clustered 234 ns 238 ns 1.02 193 ns 97.6 ns 0.51
Cardinality / Clustered 1.26 µs 1.71 µs 1.36 460 ns 1.24 µs 2.70
Contains / Dense 95 ns 126 ns 1.33 88.7 ns 30.8 ns 0.35
Rank / Dense 9.2 µs 960 ns 0.10 2.93 µs 648 ns 0.22
Select / Dense 4.27 µs 4.4 µs 1.03 2.88 µs 3.98 µs 1.38
MinMax / Dense 112 ns 7.17 ns 0.06 75.6 ns 5.63 ns 0.07
RemoveAdd / Dense 217 ns 246 ns 1.13 189 ns 99.2 ns 0.53
Cardinality / Dense 1.28 µs 1.78 µs 1.39 459 ns 1.8 µs 3.91
64Contains 90 ns 110 ns 1.23 71.2 ns 80.5 ns 1.13
64-bit iteration, construction and serialization (28 benchmarks)

Iterate is buffered in both libraries; IterateStepwise uses the gocroaring Iterator64, one call per value. AddOneByOne adds 100k values; AddMany builds from all 1M. The 64-bit serialized bytes are identical in both libraries.

benchmark x86-64 gocroaring x86-64 roaring ratio arm64 gocroaring arm64 roaring ratio
Iterate / Sparse 130 ms 32.3 ms 0.25 74.7 ms 34.6 ms 0.46
IterateStepwise / Sparse 346 ms 32.2 ms 0.09 285 ms 33.6 ms 0.12
IterateCallback / Sparse 128 ms 31.4 ms 0.24 79.9 ms 34.5 ms 0.43
ToArray / Sparse 118 ms 59.8 ms 0.51 64.2 ms 51.6 ms 0.80
Clone / Sparse 432 ms 135 ms 0.31 245 ms 69.5 ms 0.28
AddOneByOne / Sparse 26.2 ms 177 ms 6.73 13.6 ms 144 ms 11
AddMany / Sparse 466 ms 547 ms 1.17 264 ms 435 ms 1.65
Serialize / Sparse 128 ms 58.8 ms 0.46 74.8 ms 32.9 ms 0.44
Deserialize / Sparse 160 ms 81.7 ms 0.51 74.1 ms 37.6 ms 0.51
Iterate / Clustered 2.07 ms 6.95 ms 3.35 770 µs 4.09 ms 5.30
IterateStepwise / Clustered 101 ms 6.92 ms 0.07 89 ms 4.07 ms 0.05
IterateCallback / Clustered 2.18 ms 6.92 ms 3.18 1.45 ms 4.08 ms 2.81
ToArray / Clustered 1.33 ms 1.37 ms 1.03 187 µs 439 µs 2.35
Clone / Clustered 346 µs 428 µs 1.24 137 µs 155 µs 1.13
AddOneByOne / Clustered 10.6 ms 9.91 ms 0.94 8.01 ms 5.56 ms 0.69
AddMany / Clustered 102 ms 133 ms 1.31 78.6 ms 94.9 ms 1.21
Serialize / Clustered 372 µs 712 µs 1.91 74.5 µs 136 µs 1.83
Deserialize / Clustered 325 µs 447 µs 1.38 110 µs 157 µs 1.43
Iterate / Dense 2.1 ms 6.92 ms 3.30 770 µs 4.1 ms 5.32
IterateStepwise / Dense 101 ms 6.92 ms 0.07 89.1 ms 4.09 ms 0.05
IterateCallback / Dense 2.16 ms 6.92 ms 3.20 1.45 ms 4.1 ms 2.82
ToArray / Dense 1.32 ms 1.38 ms 1.04 186 µs 450 µs 2.42
Clone / Dense 327 µs 423 µs 1.29 118 µs 146 µs 1.23
AddOneByOne / Dense 10.1 ms 10.6 ms 1.05 7.81 ms 6.46 ms 0.83
AddMany / Dense 96.5 ms 132 ms 1.37 76.9 ms 90.9 ms 1.18
Serialize / Dense 367 µs 701 µs 1.91 75.3 µs 135 µs 1.79
Deserialize / Dense 309 µs 428 µs 1.38 99.5 µs 146 µs 1.47
64AddMany 86 ms 99.2 ms 1.15 50.8 ms 66.4 ms 1.31
64-bit set operations (23 benchmarks)

The second bitmap shares about half of the values of the first. 64Or uses two sets of 300k values over 2^40, 64And over 2^26.

benchmark x86-64 gocroaring x86-64 roaring ratio arm64 gocroaring arm64 roaring ratio
Or / Sparse 555 ms 234 ms 0.42 358 ms 132 ms 0.37
And / Sparse 476 ms 205 ms 0.43 305 ms 121 ms 0.40
Xor / Sparse 460 ms 199 ms 0.43 308 ms 104 ms 0.34
AndNot / Sparse 437 ms 238 ms 0.54 269 ms 125 ms 0.46
AndCardinality / Sparse 254 ms 65.4 ms 0.26 135 ms 43.7 ms 0.32
OrCardinality / Sparse 263 ms 224 ms 0.85 132 ms 136 ms 1.03
Intersects / Sparse 75.8 ns 8.85 ns 0.12 52.9 ns 6.06 ns 0.11
Or / Clustered 1.23 ms 6.56 ms 5.35 3.39 ms 3.89 ms 1.15
And / Clustered 825 µs 5.3 ms 6.42 3.21 ms 3.16 ms 0.98
Xor / Clustered 1.61 ms 6.62 ms 4.11 3.2 ms 3.99 ms 1.25
AndNot / Clustered 809 µs 5.82 ms 7.19 3.23 ms 3.52 ms 1.09
AndCardinality / Clustered 568 µs 4.8 ms 8.45 3.09 ms 3.09 ms 1.00
OrCardinality / Clustered 564 µs 6.59 ms 12 3.23 ms 4.1 ms 1.27
Intersects / Clustered 72.7 ns 10.2 ns 0.14 47.1 ns 7.11 ns 0.15
Or / Dense 1.2 ms 6.39 ms 5.32 3.23 ms 3.86 ms 1.20
And / Dense 800 µs 5.2 ms 6.50 3.17 ms 3.12 ms 0.98
Xor / Dense 1.56 ms 6.46 ms 4.13 3.2 ms 4 ms 1.25
AndNot / Dense 792 µs 5.68 ms 7.18 3.29 ms 3.5 ms 1.06
AndCardinality / Dense 574 µs 4.79 ms 8.34 3.17 ms 3.08 ms 0.97
OrCardinality / Dense 570 µs 6.46 ms 11 3.19 ms 3.89 ms 1.22
Intersects / Dense 73.3 ns 8.79 ns 0.12 47.1 ns 6.03 ns 0.13
64Or 214 ms 67.5 ms 0.32 103 ms 30.5 ms 0.30
64And 399 µs 2.61 ms 6.54 1.24 ms 1.51 ms 1.22

Your results depend on your data and hardware, so measure with your own workload. To run the comparison:

cd benchmarks/compare
go test -run '^$' -bench . -benchmem -count 10 > results.txt

See also https://github.com/lemire/gobitmapbenchmark.

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 arXiv:1709.07821
  • Samy Chambi, Daniel Lemire, Owen Kaser, Robert Godin, Better bitmap performance with Roaring bitmaps, Software: Practice and Experience Volume 46, Issue 5, pages 709–719, May 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 (accepted in 2016, to appear) http://arxiv.org/abs/1603.06549
Requirements

Go 1.24 or better, and a C compiler (cgo). The CRoaring sources are bundled with the package, so there is nothing else to install:

  • go get github.com/RoaringBitmap/gocroaring

The bundled CRoaring version is reported by gocroaring.CRoaringVersion.

32-bit and 64-bit bitmaps

The package wraps both C APIs. gocroaring.Bitmap stores 32-bit integers and wraps roaring_bitmap_t; gocroaring.Bitmap64 stores 64-bit integers and wraps roaring64_bitmap_t. The two types offer the same operations, with the free functions of the 64-bit type carrying a 64 suffix (Or64, And64, Read64, and so on).

rb := gocroaring.New64()
rb.AddRange(1<<40, 1<<40+1000)
rb.RunOptimize()
fmt.Println(rb.Cardinality(), rb.Contains(1<<40+5))
Memory management

Bitmaps and iterators hold memory allocated by C. That memory is released automatically once the Go value becomes unreachable: we register a cleanup with runtime.AddCleanup rather than a finalizer, which lets the garbage collector reclaim a bitmap in a single cycle instead of two, and makes creating and discarding bitmaps about 20% cheaper than the finalizer-based approach we used previously. You may still call Free to release the C memory eagerly; doing so cancels the cleanup, and calling Free twice is harmless.

Iteration reads values from C in blocks rather than one at a time, so walking a bitmap through Iterator() is more than an order of magnitude faster than paying for a crossing of the Go/C boundary per value. Use NewIterator() when you need to move backwards or seek.

The CRoaring entry points are declared #cgo nocallback (none of them calls back into Go) and, where the function does not keep the buffer it is given, #cgo noescape (so the Go buffers we hand to C are not forced onto the heap). The frozen views are deliberately left out of the noescape list, since they do retain their buffer.

Example

Here is a simplified but complete example:

package main

import (
	"fmt"

	"github.com/RoaringBitmap/gocroaring"
)

func main() {
	// example inspired by https://github.com/fzandona/goroar
	fmt.Println("==roaring==")
	rb1 := gocroaring.New(1, 2, 3, 4, 5, 100, 1000)
	rb1.RunOptimize() // improves compression
	fmt.Println("Cardinality: ", rb1.Cardinality())
	fmt.Println("Contains 3? ", rb1.Contains(3))

	rb2 := gocroaring.New()
	rb2.Add(3, 4, 1000)
	rb2.RunOptimize() // improves compression

	rb1.And(rb2)
	// prints {3,4,1000}
	fmt.Println(rb1)

	rb3 := gocroaring.New(1, 5)
	rb3.Or(rb1)

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

	fmt.Println(rb3.ToArray())
	fmt.Println(rb3)

	rb4 := gocroaring.FastOr(rb1, rb2, rb3) // optimized way to compute unions between many bitmaps
	fmt.Println(rb4)

	// next we include an example of serialization
	buf := make([]byte, rb1.SerializedSizeInBytes())
	rb1.Write(buf) // we omit error handling
	newrb, _ := gocroaring.Read(buf)
	if rb1.Equals(newrb) {
		fmt.Println("I wrote the content to a byte stream and read it back.")
	}

	fmt.Println(rb1.Stats()) // show the cardinality and the numbers of each type of container used.
}
Documentation

Current documentation is available at http://godoc.org/github.com/RoaringBitmap/gocroaring

Mailing list/discussion group

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

Compatibility with Java RoaringBitmap library

You can read bitmaps in Go, Java, C, C++ that have been serialized in Go, Java, C, C++.

Documentation

Overview

Package gocroaring is a wrapper for CRoaring in go. It provides a fast compressed bitmap data structure. See http://roaringbitmap.org for details.

The package exposes two types: Bitmap, which stores 32-bit integers and wraps the roaring_bitmap_t C type, and Bitmap64, which stores 64-bit integers and wraps the roaring64_bitmap_t C type.

Bitmaps hold memory allocated by C. That memory is released automatically once the Go value becomes unreachable (we rely on runtime.AddCleanup), but you may call Free explicitly to release it eagerly.

Index

Constants

View Source 
const CRoaringMajor = C.ROARING_VERSION_MAJOR

CRoaringMajor, CRoaringMinor and CRoaringRevision report the version of the bundled CRoaring library.

View Source 
const CRoaringMinor = C.ROARING_VERSION_MINOR
View Source 
const CRoaringRevision = C.ROARING_VERSION_REVISION
View Source 
const CRoaringVersion = C.ROARING_VERSION

CRoaringVersion is the version of the bundled CRoaring library, as a string.

View Source 
const Frozen64Alignment = 64

Frozen64Alignment is the alignment that a buffer must have before it can back a 64-bit frozen view. See AlignedBuffer64 and ReadFrozenView64.

View Source 
const FrozenAlignment = 32

FrozenAlignment is the alignment that a buffer must have before it can back a frozen view. See AlignedBuffer and ReadFrozenView.

Variables

View Source 
var (
	// ErrNotEnoughSpace is returned by the serialization routines when the
	// provided buffer is too small.
	ErrNotEnoughSpace = errors.New("not enough space")
	// ErrEmptyBuffer is returned when a deserialization routine is handed an
	// empty buffer.
	ErrEmptyBuffer = errors.New("empty buffer")
	// ErrDeserialize is returned when a buffer does not contain a valid bitmap.
	ErrDeserialize = errors.New("failed to read roaring bitmap")
	// ErrMisaligned is returned by the frozen view routines when the buffer is
	// not aligned on a FrozenAlignment boundary.
	ErrMisaligned = fmt.Errorf("buffer is not aligned on a %d-byte boundary", FrozenAlignment)
	// ErrNoSuchElement is returned by Select when the rank is out of range.
	ErrNoSuchElement = errors.New("no such element")
)
View Source 
var ErrMisaligned64 = fmt.Errorf("buffer is not aligned on a %d-byte boundary", Frozen64Alignment)

ErrMisaligned64 is returned by ReadFrozenView64 when the buffer is not aligned on a Frozen64Alignment boundary.

View Source 
var ErrNotShrunken = errors.New("the bitmap must be shrunk to fit before it can be frozen")

ErrNotShrunken is returned by Bitmap64.WriteFrozen when ShrinkToFit has not been called since the last modification of the bitmap.

Functions

func AlignedBuffer added in v1.1.0 

func AlignedBuffer(size int) []byte

AlignedBuffer returns a byte slice of the requested size whose first byte is aligned on a FrozenAlignment boundary, as required by ReadFrozenView.

func AlignedBuffer64 added in v1.1.0 

func AlignedBuffer64(size int) []byte

AlignedBuffer64 returns a byte slice of the requested size whose first byte is aligned on a Frozen64Alignment boundary, as required by ReadFrozenView64.

func PortableDeserializeSize added in v1.1.0 

func PortableDeserializeSize(b []byte) int

PortableDeserializeSize returns how many bytes would be read from b by Read, or zero if b does not start with a valid bitmap.

func PortableDeserializeSize64 added in v1.1.0 

func PortableDeserializeSize64(b []byte) int

PortableDeserializeSize64 returns how many bytes would be read from b by Read64, or zero if b does not start with a valid bitmap.

Types

type Bitmap 

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

Bitmap is a compressed bitmap of 32-bit integers.

A Bitmap is not safe for concurrent modification.

func And 

func And(x1, x2 *Bitmap) *Bitmap

And computes the intersection between two bitmaps and returns the result. This function may panic if the allocation failed.

func AndNot 

func AndNot(x1, x2 *Bitmap) *Bitmap

AndNot computes the difference between two bitmaps and returns the result. This function may panic if the allocation failed.

func FastOr 

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

FastOr computes the union between many bitmaps quickly, as opposed to having to call Or repeatedly. This function may panic if the allocation failed.

func FastOrHeap added in v1.1.0 

func FastOrHeap(bitmaps ...*Bitmap) *Bitmap

FastOrHeap computes the union between many bitmaps using a heap. It can be faster than FastOr when the bitmaps are numerous and of uneven sizes. This function may panic if the allocation failed.

func FastXor added in v1.1.0 

func FastXor(bitmaps ...*Bitmap) *Bitmap

FastXor computes the symmetric difference between many bitmaps quickly, as opposed to having to call Xor repeatedly. This function may panic if the allocation failed.

func Flip 

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

Flip negates the bits in the given range (i.e., [rangeStart, rangeEnd)) and returns the result. This function may panic if the allocation failed.

func FlipClosed added in v1.1.0 

func FlipClosed(bm *Bitmap, rangeStart, rangeEnd uint32) *Bitmap

FlipClosed negates the bits in the given range (i.e., [rangeStart, rangeEnd]) and returns the result. This function may panic if the allocation failed.

func FromRange added in v1.1.0 

func FromRange(min, max uint64, step uint32) *Bitmap

FromRange creates a bitmap containing min, min+step, min+2*step... up to but not including max. An empty range yields an empty bitmap. The step must be strictly positive. This function may panic if the allocation failed.

func LazyOr added in v1.1.0 

func LazyOr(x1, x2 *Bitmap, bitsetconversion bool) *Bitmap

LazyOr computes the union between two bitmaps, leaving the result in an invalid state until RepairAfterLazy is called on it. Set bitsetconversion to true to eagerly convert containers to bitsets when it might help. This function may panic if the allocation failed.

func LazyXor added in v1.1.0 

func LazyXor(x1, x2 *Bitmap) *Bitmap

LazyXor computes the symmetric difference between two bitmaps, leaving the result in an invalid state until RepairAfterLazy is called on it. This function may panic if the allocation failed.

func New added in v0.2.0 

func New(x ...uint32) *Bitmap

New creates a new Bitmap with any number of initial values. This function may panic if the allocation failed.

func NewWithCapacity added in v1.1.0 

func NewWithCapacity(capacity uint32) *Bitmap

NewWithCapacity creates a new Bitmap with room for the given number of containers, avoiding some reallocations when the bitmap is populated. This function may panic if the allocation failed.

func Or 

func Or(x1, x2 *Bitmap) *Bitmap

Or computes the union between two bitmaps and returns the result. This function may panic if the allocation failed.

func Read 

func Read(b []byte) (*Bitmap, error)

Read reads a serialized version of the bitmap, in the portable format. The buffer is not retained. If the data comes from an untrusted source, prefer ReadValidated.

func ReadFrozenView added in v0.2.65 

func ReadFrozenView(b []byte) (*Bitmap, error)

ReadFrozenView reads a frozen serialized version of the bitmap, as written by WriteFrozen. The result is immutable: attempting to mutate it will fail catastrophically. The buffer must be aligned on a FrozenAlignment boundary (see AlignedBuffer) and its length must be exactly the length that was written. A reference to the buffer is retained for the lifetime of the view.

func ReadNative added in v1.1.0 

func ReadNative(b []byte) (*Bitmap, error)

ReadNative reads a bitmap written by WriteNative. The buffer is not retained.

func ReadPortableFrozenView added in v1.1.0 

func ReadPortableFrozenView(b []byte) (*Bitmap, error)

ReadPortableFrozenView reads a bitmap written in the portable format (see Write) without copying the container data: the result is a read-only view over b. A reference to the buffer is retained for the lifetime of the view.

func ReadValidated added in v1.1.0 

func ReadValidated(b []byte) (*Bitmap, error)

ReadValidated reads a serialized version of the bitmap, in the portable format, and checks its internal consistency. Use it when the data comes from an untrusted source. The deserialization and the validation are performed in a single crossing of the Go/C boundary.

func Xor 

func Xor(x1, x2 *Bitmap) *Bitmap

Xor computes the symmetric difference between two bitmaps and returns the result. This function may panic if the allocation failed.

func (*Bitmap) Add 

func (rb *Bitmap) Add(x ...uint32)

Add the integer(s) x to the bitmap.

func (*Bitmap) AddBulk added in v1.1.0 

func (rb *Bitmap) AddBulk(ctx *BulkContext, x uint32)

AddBulk adds the integer x to the bitmap, using ctx to remember the last container visited. Values should be provided in ascending order.

func (*Bitmap) AddChecked added in v1.1.0 

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

AddChecked adds the integer x to the bitmap and reports whether a new value was actually added.

func (*Bitmap) AddOffset added in v1.1.0 

func (rb *Bitmap) AddOffset(offset int64) *Bitmap

AddOffset returns a copy of the bitmap with the given (possibly negative) offset added to every value. Values that fall outside the 32-bit range are dropped. This function may panic if the allocation failed.

func (*Bitmap) AddRange added in v0.3.0 

func (rb *Bitmap) AddRange(min, max uint64)

AddRange adds all values in the range [min, max).

func (*Bitmap) AddRangeClosed added in v1.1.0 

func (rb *Bitmap) AddRangeClosed(min, max uint32)

AddRangeClosed adds all values in the range [min, max].

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) AndCardinality added in v0.2.7 

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

AndCardinality computes the size of the intersection between two bitmaps.

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) AndNotCardinality added in v0.2.7 

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

AndNotCardinality computes the size of the difference between two bitmaps.

func (*Bitmap) Assign added in v0.3.0 

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

Assign copies x2 over rb, returning false if the copy failed.

func (*Bitmap) Cardinality added in v0.2.0 

func (rb *Bitmap) Cardinality() uint64

Cardinality returns the number of integers contained in the bitmap.

func (*Bitmap) Clear added in v0.2.9 

func (rb *Bitmap) Clear()

Clear removes all elements from the bitmap.

func (*Bitmap) Clone 

func (rb *Bitmap) Clone() *Bitmap

Clone creates a copy of the Bitmap. This function may panic if the allocation failed.

func (*Bitmap) Contains 

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

Contains returns true if the integer is contained in the bitmap.

func (*Bitmap) ContainsBulk added in v1.1.0 

func (rb *Bitmap) ContainsBulk(ctx *BulkContext, x uint32) bool

ContainsBulk reports whether the integer x is in the bitmap, using ctx to remember the last container visited. Values should be provided in ascending order.

func (*Bitmap) ContainsRange added in v0.3.0 

func (rb *Bitmap) ContainsRange(x, y uint64) bool

ContainsRange returns true if all the integers in the range [x, y) are contained in the bitmap.

func (*Bitmap) ContainsRangeClosed added in v1.1.0 

func (rb *Bitmap) ContainsRangeClosed(x, y uint32) bool

ContainsRangeClosed returns true if all the integers in the range [x, y] are contained in the bitmap.

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 in the range that was absent is added.

func (*Bitmap) FlipClosed added in v1.1.0 

func (rb *Bitmap) FlipClosed(rangeStart, rangeEnd uint32)

FlipClosed negates the bits in the given range (i.e., [rangeStart, rangeEnd]).

func (*Bitmap) Free added in v0.4.0 

func (rb *Bitmap) Free()

Free releases the memory held by the bitmap. Using the bitmap afterwards is a mistake. Calling Free more than once is harmless.

func (*Bitmap) FrozenSizeInBytes added in v0.2.65 

func (rb *Bitmap) FrozenSizeInBytes() int

FrozenSizeInBytes computes the frozen serialized size in bytes.

func (*Bitmap) GetCardinality 

func (rb *Bitmap) GetCardinality() uint64

GetCardinality returns the number of integers contained in the bitmap.

func (*Bitmap) GetCopyOnWrite added in v1.1.0 

func (rb *Bitmap) GetCopyOnWrite() bool

GetCopyOnWrite reports whether the bitmap uses copy-on-write containers.

func (*Bitmap) GetIndex added in v1.1.0 

func (rb *Bitmap) GetIndex(x uint32) int64

GetIndex returns the index of x in the bitmap, or -1 if x is not present. Unlike Rank, it distinguishes a missing value from a value of rank zero.

func (*Bitmap) InternalValidate added in v1.1.0 

func (rb *Bitmap) InternalValidate() error

InternalValidate performs internal consistency checks. It is useful after deserializing bitmaps from untrusted sources. It returns nil if the bitmap is consistent, and an error describing the problem otherwise.

func (*Bitmap) Intersect added in v0.2.7 

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

Intersect checks whether the two bitmaps intersect.

func (*Bitmap) IntersectWithRange added in v1.1.0 

func (rb *Bitmap) IntersectWithRange(x, y uint64) bool

IntersectWithRange checks whether the bitmap intersects the range [x, y).

func (*Bitmap) IsEmpty 

func (rb *Bitmap) IsEmpty() bool

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

func (*Bitmap) IsStrictSubset added in v1.1.0 

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

IsStrictSubset returns true if every integer of rb is also in x2 and the two bitmaps differ.

func (*Bitmap) IsSubset added in v1.1.0 

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

IsSubset returns true if every integer of rb is also in x2.

func (*Bitmap) Iterate added in v1.1.0 

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

Iterate calls cb with every integer in the bitmap, in sorted order, stopping early if cb returns false.

func (*Bitmap) Iterator added in v0.2.3 

func (rb *Bitmap) Iterator() IntIterable

Iterator creates a new IntIterable to iterate over the integers contained in the bitmap, in sorted order. This function may panic if the allocation failed.

func (*Bitmap) JaccardIndex added in v0.2.7 

func (rb *Bitmap) JaccardIndex(x2 *Bitmap) float64

JaccardIndex computes the Jaccard index between two bitmaps.

func (*Bitmap) LazyOrInplace added in v1.1.0 

func (rb *Bitmap) LazyOrInplace(x2 *Bitmap, bitsetconversion bool)

LazyOrInplace computes the union with x2 in place, leaving the bitmap in an invalid state until RepairAfterLazy is called. Set bitsetconversion to true to eagerly convert containers to bitsets when it might help.

func (*Bitmap) LazyXorInplace added in v1.1.0 

func (rb *Bitmap) LazyXorInplace(x2 *Bitmap)

LazyXorInplace computes the symmetric difference with x2 in place, leaving the bitmap in an invalid state until RepairAfterLazy is called.

func (*Bitmap) Maximum added in v0.2.4 

func (rb *Bitmap) Maximum() uint32

Maximum returns the largest of the integers contained in the bitmap, or 0 if the bitmap is empty.

func (*Bitmap) Minimum added in v0.2.4 

func (rb *Bitmap) Minimum() uint32

Minimum returns the smallest of the integers contained in the bitmap, or math.MaxUint32 if the bitmap is empty.

func (*Bitmap) NativeSerializedSizeInBytes added in v1.1.0 

func (rb *Bitmap) NativeSerializedSizeInBytes() int

NativeSerializedSizeInBytes computes the serialized size in bytes of the Bitmap, using the non-portable native format. The native format is not compatible with the Java and Go implementations; prefer the portable format unless you know what you are doing.

func (*Bitmap) NewIterator added in v1.1.0 

func (rb *Bitmap) NewIterator() *Iterator

NewIterator returns an iterator positioned on the smallest value of the bitmap. This function may panic if the allocation failed.

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 added in v0.2.7 

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

OrCardinality computes the size of the union between two bitmaps.

func (*Bitmap) Printf 

func (rb *Bitmap) Printf()

Printf writes a description of the bitmap to stdout.

func (*Bitmap) RangeCardinality added in v1.1.0 

func (rb *Bitmap) RangeCardinality(min, max uint64) uint64

RangeCardinality returns the number of integers in the bitmap that fall in the range [min, max).

func (*Bitmap) RangeCardinalityClosed added in v1.1.0 

func (rb *Bitmap) RangeCardinalityClosed(min, max uint32) uint64

RangeCardinalityClosed returns the number of integers in the bitmap that fall in the range [min, max].

func (*Bitmap) RangeToArray added in v1.1.0 

func (rb *Bitmap) RangeToArray(offset, limit uint64) []uint32

RangeToArray returns at most limit integers from the bitmap, in sorted order, starting at the given offset (a rank, not a value).

func (*Bitmap) Rank added in v0.2.4 

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

Rank returns the number of values smaller or equal to x.

func (*Bitmap) RankMany added in v1.1.0 

func (rb *Bitmap) RankMany(vals []uint32) []uint64

RankMany returns the rank of each value in vals. The values must be sorted in ascending order. It is faster than calling Rank repeatedly.

func (*Bitmap) Remove 

func (rb *Bitmap) Remove(x uint32)

Remove the integer x from the bitmap.

func (*Bitmap) RemoveChecked added in v1.1.0 

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

RemoveChecked removes the integer x from the bitmap and reports whether a value was actually removed.

func (*Bitmap) RemoveMany added in v1.1.0 

func (rb *Bitmap) RemoveMany(x ...uint32)

RemoveMany removes the integer(s) x from the bitmap.

func (*Bitmap) RemoveRange added in v0.3.0 

func (rb *Bitmap) RemoveRange(min, max uint64)

RemoveRange removes all values in the range [min, max).

func (*Bitmap) RemoveRangeClosed added in v1.1.0 

func (rb *Bitmap) RemoveRangeClosed(min, max uint32)

RemoveRangeClosed removes all values in the range [min, max].

func (*Bitmap) RemoveRunCompression 

func (rb *Bitmap) RemoveRunCompression() bool

RemoveRunCompression removes run-length encoding even when it is more space efficient; it returns whether a change was applied.

func (*Bitmap) RepairAfterLazy added in v1.1.0 

func (rb *Bitmap) RepairAfterLazy()

RepairAfterLazy restores a bitmap produced by the lazy operations to a valid state. It must be called before any other operation.

func (*Bitmap) ReverseIterator added in v1.1.0 

func (rb *Bitmap) ReverseIterator() *Iterator

ReverseIterator returns an iterator positioned on the largest value of the bitmap, meant to be walked with Previous. This function may panic if the allocation failed.

func (*Bitmap) RunOptimize 

func (rb *Bitmap) RunOptimize() bool

RunOptimize improves the compression of the bitmap (call this after populating a new bitmap); it returns true if the bitmap was modified.

func (*Bitmap) Select added in v0.2.4 

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

Select returns the element having the designated rank, if it exists.

func (*Bitmap) SerializedSizeInBytes added in v0.2.0 

func (rb *Bitmap) SerializedSizeInBytes() int

SerializedSizeInBytes computes the serialized size in bytes of the Bitmap, using the portable format.

func (*Bitmap) SetCopyOnWrite added in v1.1.0 

func (rb *Bitmap) SetCopyOnWrite(cow bool)

SetCopyOnWrite turns copy-on-write on or off. Copy-on-write saves memory and avoids copies, but it requires more care in a threaded context. If you enable it, enable it on all of your bitmaps: mixing bitmaps with and without copy-on-write is unsafe.

func (*Bitmap) ShrinkToFit added in v1.1.0 

func (rb *Bitmap) ShrinkToFit() int

ShrinkToFit releases unused memory and returns how many bytes were freed.

func (*Bitmap) Stats added in v0.2.0 

func (rb *Bitmap) Stats() map[string]uint64

Stats returns some statistics about the roaring bitmap.

func (*Bitmap) StatsStruct added in v0.3.0 

func (rb *Bitmap) StatsStruct() Statistics

StatsStruct is the same as Stats but returns a typed struct. See https://github.com/RoaringBitmap/roaring/pull/73 for the rationale.

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) ToBytes added in v1.1.0 

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

ToBytes returns a serialized version of this bitmap, using the portable format.

func (*Bitmap) ToDenseBitset added in v1.1.0 

func (rb *Bitmap) ToDenseBitset() ([]uint64, error)

ToDenseBitset converts the bitmap to an uncompressed bitset, returned as a slice of 64-bit words in little-endian bit order: value x is present when bit x%64 of word x/64 is set. Beware that the result can be large: a bitmap containing a single large value produces a slice proportional to that value.

func (*Bitmap) Write 

func (rb *Bitmap) Write(b []byte) error

Write writes a serialized version of this bitmap to b, using the portable format. The buffer must be at least SerializedSizeInBytes long.

func (*Bitmap) WriteFrozen added in v0.2.65 

func (rb *Bitmap) WriteFrozen(b []byte) error

WriteFrozen writes a serialized version of the bitmap to b in the frozen format. The buffer must be at least FrozenSizeInBytes long. The frozen format is endian-sensitive and version-specific; it is meant for fast reloading of data you produced yourself, not for interchange.

func (*Bitmap) WriteNative added in v1.1.0 

func (rb *Bitmap) WriteNative(b []byte) error

WriteNative writes a serialized version of this bitmap to b, using the non-portable native 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.

func (*Bitmap) XorCardinality added in v0.2.7 

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

XorCardinality computes the size of the symmetric difference between two bitmaps.

type Bitmap64 added in v1.1.0 

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

Bitmap64 is a compressed bitmap of 64-bit integers.

A Bitmap64 is not safe for concurrent modification.

func And64 added in v1.1.0 

func And64(x1, x2 *Bitmap64) *Bitmap64

And64 computes the intersection between two bitmaps and returns the result. This function may panic if the allocation failed.

func AndNot64 added in v1.1.0 

func AndNot64(x1, x2 *Bitmap64) *Bitmap64

AndNot64 computes the difference between two bitmaps and returns the result. This function may panic if the allocation failed.

func Flip64 added in v1.1.0 

func Flip64(bm *Bitmap64, rangeStart, rangeEnd uint64) *Bitmap64

Flip64 negates the bits in the given range (i.e., [rangeStart, rangeEnd)) and returns the result. This function may panic if the allocation failed.

func FlipClosed64 added in v1.1.0 

func FlipClosed64(bm *Bitmap64, rangeStart, rangeEnd uint64) *Bitmap64

FlipClosed64 negates the bits in the given range (i.e., [rangeStart, rangeEnd]) and returns the result. This function may panic if the allocation failed.

func FromRange64 added in v1.1.0 

func FromRange64(min, max, step uint64) *Bitmap64

FromRange64 creates a bitmap containing min, min+step, min+2*step... up to but not including max. An empty range yields an empty bitmap. The step must be strictly positive. This function may panic if the allocation failed.

func MoveFrom32 added in v1.1.0 

func MoveFrom32(from *Bitmap) *Bitmap64

MoveFrom32 builds a 64-bit bitmap by moving the containers out of a 32-bit bitmap. This avoids copying the container data, but it leaves the source bitmap empty.

The containers are taken without regard for copy-on-write sharing, so do not use it on a bitmap whose containers are shared with another one (that is, a bitmap that has copy-on-write enabled and has been cloned). Clone first if you need the source intact. This function may panic if the allocation failed.

func New64 added in v1.1.0 

func New64(x ...uint64) *Bitmap64

New64 creates a new Bitmap64 with any number of initial values. This function may panic if the allocation failed.

func Or64 added in v1.1.0 

func Or64(x1, x2 *Bitmap64) *Bitmap64

Or64 computes the union between two bitmaps and returns the result. This function may panic if the allocation failed.

func Read64 added in v1.1.0 

func Read64(b []byte) (*Bitmap64, error)

Read64 reads a serialized version of the bitmap, in the portable format. The buffer is not retained. If the data comes from an untrusted source, prefer ReadValidated64.

func ReadFrozenView64 added in v1.1.0 

func ReadFrozenView64(b []byte) (*Bitmap64, error)

ReadFrozenView64 reads a frozen serialized version of the bitmap, as written by Bitmap64.WriteFrozen. The result is immutable: attempting to mutate it will fail catastrophically. The buffer must be aligned on a Frozen64Alignment boundary (see AlignedBuffer64) and its length must be exactly the length that was written. A reference to the buffer is retained for the lifetime of the view.

func ReadPortableFrozenView64 added in v1.1.0 

func ReadPortableFrozenView64(b []byte) (*Bitmap64, error)

ReadPortableFrozenView64 reads a bitmap written in the portable format (see Bitmap64.Write) without copying the container data: the result is a read-only view over b. A reference to the buffer is retained for the lifetime of the view. It fails on big-endian systems, where the portable format cannot be viewed in place.

func ReadValidated64 added in v1.1.0 

func ReadValidated64(b []byte) (*Bitmap64, error)

ReadValidated64 reads a serialized version of the bitmap, in the portable format, and checks its internal consistency. Use it when the data comes from an untrusted source. The deserialization and the validation are performed in a single crossing of the Go/C boundary.

func Xor64 added in v1.1.0 

func Xor64(x1, x2 *Bitmap64) *Bitmap64

Xor64 computes the symmetric difference between two bitmaps and returns the result. This function may panic if the allocation failed.

func (*Bitmap64) Add added in v1.1.0 

func (rb *Bitmap64) Add(x ...uint64)

Add the integer(s) x to the bitmap.

func (*Bitmap64) AddBulk added in v1.1.0 

func (rb *Bitmap64) AddBulk(ctx *BulkContext64, x uint64)

AddBulk adds the integer x to the bitmap, using ctx to remember the last container visited. Values should be provided in ascending order.

func (*Bitmap64) AddChecked added in v1.1.0 

func (rb *Bitmap64) AddChecked(x uint64) bool

AddChecked adds the integer x to the bitmap and reports whether a new value was actually added.

func (*Bitmap64) AddOffset added in v1.1.0 

func (rb *Bitmap64) AddOffset(offset int64) *Bitmap64

AddOffset returns a copy of the bitmap with the given (possibly negative) offset added to every value. Values that fall outside the 64-bit range are dropped. This function may panic if the allocation failed.

func (*Bitmap64) AddRange added in v1.1.0 

func (rb *Bitmap64) AddRange(min, max uint64)

AddRange adds all values in the range [min, max).

func (*Bitmap64) AddRangeClosed added in v1.1.0 

func (rb *Bitmap64) AddRangeClosed(min, max uint64)

AddRangeClosed adds all values in the range [min, max].

func (*Bitmap64) And added in v1.1.0 

func (rb *Bitmap64) And(x2 *Bitmap64)

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

func (*Bitmap64) AndCardinality added in v1.1.0 

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

AndCardinality computes the size of the intersection between two bitmaps.

func (*Bitmap64) AndNot added in v1.1.0 

func (rb *Bitmap64) AndNot(x2 *Bitmap64)

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

func (*Bitmap64) AndNotCardinality added in v1.1.0 

func (rb *Bitmap64) AndNotCardinality(x2 *Bitmap64) uint64

AndNotCardinality computes the size of the difference between two bitmaps.

func (*Bitmap64) Assign added in v1.1.0 

func (rb *Bitmap64) Assign(x2 *Bitmap64)

Assign copies x2 over rb.

func (*Bitmap64) Cardinality added in v1.1.0 

func (rb *Bitmap64) Cardinality() uint64

Cardinality returns the number of integers contained in the bitmap.

func (*Bitmap64) Clear added in v1.1.0 

func (rb *Bitmap64) Clear()

Clear removes all elements from the bitmap.

func (*Bitmap64) Clone added in v1.1.0 

func (rb *Bitmap64) Clone() *Bitmap64

Clone creates a copy of the Bitmap64. This function may panic if the allocation failed.

func (*Bitmap64) Contains added in v1.1.0 

func (rb *Bitmap64) Contains(x uint64) bool

Contains returns true if the integer is contained in the bitmap.

func (*Bitmap64) ContainsBulk added in v1.1.0 

func (rb *Bitmap64) ContainsBulk(ctx *BulkContext64, x uint64) bool

ContainsBulk reports whether the integer x is in the bitmap, using ctx to remember the last container visited. Values should be provided in ascending order.

func (*Bitmap64) ContainsRange added in v1.1.0 

func (rb *Bitmap64) ContainsRange(x, y uint64) bool

ContainsRange returns true if all the integers in the range [x, y) are contained in the bitmap.

func (*Bitmap64) ContainsRangeClosed added in v1.1.0 

func (rb *Bitmap64) ContainsRangeClosed(x, y uint64) bool

ContainsRangeClosed returns true if all the integers in the range [x, y] are contained in the bitmap.

func (*Bitmap64) Equals added in v1.1.0 

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

Equals returns true if the two bitmaps contain the same integers.

func (*Bitmap64) Flip added in v1.1.0 

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

Flip negates the bits in the given range (i.e., [rangeStart, rangeEnd)).

func (*Bitmap64) FlipClosed added in v1.1.0 

func (rb *Bitmap64) FlipClosed(rangeStart, rangeEnd uint64)

FlipClosed negates the bits in the given range (i.e., [rangeStart, rangeEnd]).

func (*Bitmap64) Free added in v1.1.0 

func (rb *Bitmap64) Free()

Free releases the memory held by the bitmap. Using the bitmap afterwards is a mistake. Calling Free more than once is harmless.

func (*Bitmap64) FrozenSizeInBytes added in v1.1.0 

func (rb *Bitmap64) FrozenSizeInBytes() int

FrozenSizeInBytes computes the frozen serialized size in bytes. ShrinkToFit must have been called since the last modification of the bitmap; otherwise this returns zero.

func (*Bitmap64) GetCardinality added in v1.1.0 

func (rb *Bitmap64) GetCardinality() uint64

GetCardinality returns the number of integers contained in the bitmap.

func (*Bitmap64) GetIndex added in v1.1.0 

func (rb *Bitmap64) GetIndex(x uint64) int64

GetIndex returns the index of x in the bitmap, or -1 if x is not present. Unlike Rank, it distinguishes a missing value from a value of rank zero.

func (*Bitmap64) InternalValidate added in v1.1.0 

func (rb *Bitmap64) InternalValidate() error

InternalValidate performs internal consistency checks. It is useful after deserializing bitmaps from untrusted sources. It returns nil if the bitmap is consistent, and an error describing the problem otherwise.

func (*Bitmap64) Intersect added in v1.1.0 

func (rb *Bitmap64) Intersect(x2 *Bitmap64) bool

Intersect checks whether the two bitmaps intersect.

func (*Bitmap64) IntersectWithRange added in v1.1.0 

func (rb *Bitmap64) IntersectWithRange(x, y uint64) bool

IntersectWithRange checks whether the bitmap intersects the range [x, y).

func (*Bitmap64) IsEmpty added in v1.1.0 

func (rb *Bitmap64) IsEmpty() bool

IsEmpty returns true if the Bitmap64 is empty (it is faster than doing Cardinality() == 0).

func (*Bitmap64) IsStrictSubset added in v1.1.0 

func (rb *Bitmap64) IsStrictSubset(x2 *Bitmap64) bool

IsStrictSubset returns true if every integer of rb is also in x2 and the two bitmaps differ.

func (*Bitmap64) IsSubset added in v1.1.0 

func (rb *Bitmap64) IsSubset(x2 *Bitmap64) bool

IsSubset returns true if every integer of rb is also in x2.

func (*Bitmap64) Iterate added in v1.1.0 

func (rb *Bitmap64) Iterate(cb func(x uint64) bool)

Iterate calls cb with every integer in the bitmap, in sorted order, stopping early if cb returns false.

func (*Bitmap64) Iterator added in v1.1.0 

func (rb *Bitmap64) Iterator() IntIterable64

Iterator creates a new IntIterable64 to iterate over the integers contained in the bitmap, in sorted order. This function may panic if the allocation failed.

func (*Bitmap64) JaccardIndex added in v1.1.0 

func (rb *Bitmap64) JaccardIndex(x2 *Bitmap64) float64

JaccardIndex computes the Jaccard index between two bitmaps.

func (*Bitmap64) Maximum added in v1.1.0 

func (rb *Bitmap64) Maximum() uint64

Maximum returns the largest of the integers contained in the bitmap, or 0 if the bitmap is empty.

func (*Bitmap64) Minimum added in v1.1.0 

func (rb *Bitmap64) Minimum() uint64

Minimum returns the smallest of the integers contained in the bitmap, or math.MaxUint64 if the bitmap is empty.

func (*Bitmap64) NewIterator added in v1.1.0 

func (rb *Bitmap64) NewIterator() *Iterator64

NewIterator returns an iterator positioned on the smallest value of the bitmap. This function may panic if the allocation failed.

func (*Bitmap64) Or added in v1.1.0 

func (rb *Bitmap64) Or(x2 *Bitmap64)

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

func (*Bitmap64) OrCardinality added in v1.1.0 

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

OrCardinality computes the size of the union between two bitmaps.

func (*Bitmap64) RangeCardinality added in v1.1.0 

func (rb *Bitmap64) RangeCardinality(min, max uint64) uint64

RangeCardinality returns the number of integers in the bitmap that fall in the range [min, max).

func (*Bitmap64) RangeCardinalityClosed added in v1.1.0 

func (rb *Bitmap64) RangeCardinalityClosed(min, max uint64) uint64

RangeCardinalityClosed returns the number of integers in the bitmap that fall in the range [min, max].

func (*Bitmap64) Rank added in v1.1.0 

func (rb *Bitmap64) Rank(x uint64) uint64

Rank returns the number of values smaller or equal to x.

func (*Bitmap64) Remove added in v1.1.0 

func (rb *Bitmap64) Remove(x uint64)

Remove the integer x from the bitmap.

func (*Bitmap64) RemoveBulk added in v1.1.0 

func (rb *Bitmap64) RemoveBulk(ctx *BulkContext64, x uint64)

RemoveBulk removes the integer x from the bitmap, using ctx to remember the last container visited. Values should be provided in ascending order.

func (*Bitmap64) RemoveChecked added in v1.1.0 

func (rb *Bitmap64) RemoveChecked(x uint64) bool

RemoveChecked removes the integer x from the bitmap and reports whether a value was actually removed.

func (*Bitmap64) RemoveMany added in v1.1.0 

func (rb *Bitmap64) RemoveMany(x ...uint64)

RemoveMany removes the integer(s) x from the bitmap.

func (*Bitmap64) RemoveRange added in v1.1.0 

func (rb *Bitmap64) RemoveRange(min, max uint64)

RemoveRange removes all values in the range [min, max).

func (*Bitmap64) RemoveRangeClosed added in v1.1.0 

func (rb *Bitmap64) RemoveRangeClosed(min, max uint64)

RemoveRangeClosed removes all values in the range [min, max].

func (*Bitmap64) RemoveRunCompression added in v1.1.0 

func (rb *Bitmap64) RemoveRunCompression() bool

RemoveRunCompression removes run-length encoding even when it is more space efficient; it returns whether a change was applied.

func (*Bitmap64) ReverseIterator added in v1.1.0 

func (rb *Bitmap64) ReverseIterator() *Iterator64

ReverseIterator returns an iterator positioned on the largest value of the bitmap, meant to be walked with Previous. This function may panic if the allocation failed.

func (*Bitmap64) RunOptimize added in v1.1.0 

func (rb *Bitmap64) RunOptimize() bool

RunOptimize improves the compression of the bitmap (call this after populating a new bitmap); it returns true if the bitmap was modified.

func (*Bitmap64) Select added in v1.1.0 

func (rb *Bitmap64) Select(rank uint64) (uint64, error)

Select returns the element having the designated rank, if it exists.

func (*Bitmap64) SerializedSizeInBytes added in v1.1.0 

func (rb *Bitmap64) SerializedSizeInBytes() int

SerializedSizeInBytes computes the serialized size in bytes of the Bitmap64, using the portable format.

func (*Bitmap64) ShrinkToFit added in v1.1.0 

func (rb *Bitmap64) ShrinkToFit() int

ShrinkToFit releases unused memory and returns how many bytes were freed.

func (*Bitmap64) Stats added in v1.1.0 

func (rb *Bitmap64) Stats() map[string]uint64

Stats returns some statistics about the roaring bitmap.

func (*Bitmap64) StatsStruct added in v1.1.0 

func (rb *Bitmap64) StatsStruct() Statistics

StatsStruct returns statistics describing the internal structure of the bitmap.

func (*Bitmap64) String added in v1.1.0 

func (rb *Bitmap64) String() string

String creates a string representation of the Bitmap64.

func (*Bitmap64) ToArray added in v1.1.0 

func (rb *Bitmap64) ToArray() []uint64

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

func (*Bitmap64) ToBytes added in v1.1.0 

func (rb *Bitmap64) ToBytes() []byte

ToBytes returns a serialized version of this bitmap, using the portable format.

func (*Bitmap64) Write added in v1.1.0 

func (rb *Bitmap64) Write(b []byte) error

Write writes a serialized version of this bitmap to b, using the portable format. The buffer must be at least SerializedSizeInBytes long.

func (*Bitmap64) WriteFrozen added in v1.1.0 

func (rb *Bitmap64) WriteFrozen(b []byte) error

WriteFrozen writes a serialized version of the bitmap to b in the frozen format. ShrinkToFit must have been called since the last modification of the bitmap. The buffer must be at least FrozenSizeInBytes long. The frozen format is endian-sensitive and version-specific; it is meant for fast reloading of data you produced yourself, not for interchange.

func (*Bitmap64) Xor added in v1.1.0 

func (rb *Bitmap64) Xor(x2 *Bitmap64)

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

func (*Bitmap64) XorCardinality added in v1.1.0 

func (rb *Bitmap64) XorCardinality(x2 *Bitmap64) uint64

XorCardinality computes the size of the symmetric difference between two bitmaps.

type BulkContext added in v1.1.0 

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

BulkContext accelerates repeated accesses to a bitmap when the values are provided in ascending order. A context is tied to the bitmap it was last used with: it must not be reused across bitmaps, and it must be discarded whenever the bitmap is modified by anything other than AddBulk.

func NewBulkContext added in v1.1.0 

func NewBulkContext() *BulkContext

NewBulkContext returns a fresh context for use with AddBulk and ContainsBulk.

type BulkContext64 added in v1.1.0 

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

BulkContext64 accelerates repeated accesses to a Bitmap64 when the values are provided in ascending order. A context is tied to the bitmap it was last used with: it must not be reused across bitmaps, and it must be discarded whenever the bitmap is modified by anything other than AddBulk or RemoveBulk.

func NewBulkContext64 added in v1.1.0 

func NewBulkContext64() *BulkContext64

NewBulkContext64 returns a fresh context for use with AddBulk, RemoveBulk and ContainsBulk.

type IntIterable added in v0.2.3 

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

IntIterable allows you to iterate over the values in a Bitmap.

type IntIterable64 added in v1.1.0 

type IntIterable64 interface {
	HasNext() bool
	Next() uint64
}

IntIterable64 allows you to iterate over the values in a Bitmap64.

type Iterator added in v1.1.0 

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

Iterator is a full-featured iterator over the values of a Bitmap. Unlike the iterator returned by Bitmap.Iterator, it can move backwards and can seek.

An Iterator points at a value or is exhausted; use HasValue to tell the two apart. It is invalidated by any modification of the underlying bitmap.

func (*Iterator) AdvanceIfNeeded added in v1.1.0 

func (i *Iterator) AdvanceIfNeeded(x uint32) bool

AdvanceIfNeeded moves the iterator to the smallest value that is greater than or equal to x, and reports whether it points at a value. The iterator does not move if it already points at such a value.

func (*Iterator) Clone added in v1.1.0 

func (i *Iterator) Clone() *Iterator

Clone returns a copy of the iterator, positioned on the same value. This function may panic if the allocation failed.

func (*Iterator) Free added in v1.1.0 

func (i *Iterator) Free()

Free releases the memory held by the iterator. Using the iterator afterwards is a mistake. Calling Free more than once is harmless.

func (*Iterator) HasValue added in v1.1.0 

func (i *Iterator) HasValue() bool

HasValue reports whether the iterator points at a value.

func (*Iterator) Next added in v1.1.0 

func (i *Iterator) Next() bool

Next moves the iterator to the next value and reports whether it points at one.

func (*Iterator) Previous added in v1.1.0 

func (i *Iterator) Previous() bool

Previous moves the iterator to the previous value and reports whether it points at one.

func (*Iterator) Read added in v1.1.0 

func (i *Iterator) Read(buf []uint32) int

Read fills buf with up to len(buf) values, in ascending order, and returns how many were written. A return value smaller than len(buf) means the iterator is exhausted.

func (*Iterator) ReadBackward added in v1.1.0 

func (i *Iterator) ReadBackward(buf []uint32) int

ReadBackward fills buf with up to len(buf) values, in descending order, and returns how many were written.

func (*Iterator) ReadPreviousRanges added in v1.1.0 

func (i *Iterator) ReadPreviousRanges(buf []Range) int

ReadPreviousRanges fills buf with up to len(buf) runs of consecutive values, in descending order, and returns how many were written.

func (*Iterator) ReadRanges added in v1.1.0 

func (i *Iterator) ReadRanges(buf []Range) int

ReadRanges fills buf with up to len(buf) runs of consecutive values, in ascending order, and returns how many were written.

func (*Iterator) Reset added in v1.1.0 

func (i *Iterator) Reset()

Reset repositions the iterator on the smallest value of the bitmap it was created from.

func (*Iterator) ResetToLast added in v1.1.0 

func (i *Iterator) ResetToLast()

ResetToLast repositions the iterator on the largest value of the bitmap it was created from.

func (*Iterator) Skip added in v1.1.0 

func (i *Iterator) Skip(count uint32) uint32

Skip advances the iterator by count values and returns how many values were actually skipped.

func (*Iterator) SkipBackward added in v1.1.0 

func (i *Iterator) SkipBackward(count uint32) uint32

SkipBackward moves the iterator back by count values and returns how many values were actually skipped.

func (*Iterator) Value added in v1.1.0 

func (i *Iterator) Value() uint32

Value returns the value the iterator points at. It is meaningless when HasValue is false.

type Iterator64 added in v1.1.0 

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

Iterator64 is a full-featured iterator over the values of a Bitmap64. Unlike the iterator returned by Bitmap64.Iterator, it can move backwards and can seek.

An Iterator64 points at a value or is exhausted; use HasValue to tell the two apart. It is invalidated by any modification of the underlying bitmap.

func (*Iterator64) AdvanceIfNeeded added in v1.1.0 

func (i *Iterator64) AdvanceIfNeeded(x uint64) bool

AdvanceIfNeeded moves the iterator to the smallest value that is greater than or equal to x, and reports whether it points at a value. The iterator does not move if it already points at such a value.

func (*Iterator64) Clone added in v1.1.0 

func (i *Iterator64) Clone() *Iterator64

Clone returns a copy of the iterator, positioned on the same value. This function may panic if the allocation failed.

func (*Iterator64) Free added in v1.1.0 

func (i *Iterator64) Free()

Free releases the memory held by the iterator. Using the iterator afterwards is a mistake. Calling Free more than once is harmless.

func (*Iterator64) HasValue added in v1.1.0 

func (i *Iterator64) HasValue() bool

HasValue reports whether the iterator points at a value.

func (*Iterator64) Next added in v1.1.0 

func (i *Iterator64) Next() bool

Next moves the iterator to the next value and reports whether it points at one.

func (*Iterator64) Previous added in v1.1.0 

func (i *Iterator64) Previous() bool

Previous moves the iterator to the previous value and reports whether it points at one.

func (*Iterator64) Read added in v1.1.0 

func (i *Iterator64) Read(buf []uint64) int

Read fills buf with up to len(buf) values, in ascending order, and returns how many were written. A return value smaller than len(buf) means the iterator is exhausted.

func (*Iterator64) ReadBackward added in v1.1.0 

func (i *Iterator64) ReadBackward(buf []uint64) int

ReadBackward fills buf with up to len(buf) values, in descending order, and returns how many were written.

func (*Iterator64) ReadPreviousRanges added in v1.1.0 

func (i *Iterator64) ReadPreviousRanges(buf []Range64) int

ReadPreviousRanges fills buf with up to len(buf) runs of consecutive values, in descending order, and returns how many were written.

func (*Iterator64) ReadRanges added in v1.1.0 

func (i *Iterator64) ReadRanges(buf []Range64) int

ReadRanges fills buf with up to len(buf) runs of consecutive values, in ascending order, and returns how many were written.

func (*Iterator64) Reset added in v1.1.0 

func (i *Iterator64) Reset()

Reset repositions the iterator on the smallest value of the bitmap it was created from.

func (*Iterator64) ResetToLast added in v1.1.0 

func (i *Iterator64) ResetToLast()

ResetToLast repositions the iterator on the largest value of the bitmap it was created from.

func (*Iterator64) Value added in v1.1.0 

func (i *Iterator64) Value() uint64

Value returns the value the iterator points at. It is meaningless when HasValue is false.

type Range added in v1.1.0 

type Range struct {
	Min uint32
	Max uint32
}

Range is a closed interval [Min, Max] of 32-bit values.

type Range64 added in v1.1.0 

type Range64 struct {
	Min uint64
	Max uint64
}

Range64 is a closed interval [Min, Max] of 64-bit values.

type Statistics added in v0.3.0 

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

	// MinValue and MaxValue are undefined when Cardinality is zero.
	MinValue uint64
	MaxValue uint64
}

Statistics describes the internal structure of a bitmap.

Source Files

View all Source files

Directories

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.