diff options
Diffstat (limited to 'vendor/github.com/RoaringBitmap/roaring/bitmapcontainer.go')
| -rw-r--r-- | vendor/github.com/RoaringBitmap/roaring/bitmapcontainer.go | 146 |
1 files changed, 125 insertions, 21 deletions
diff --git a/vendor/github.com/RoaringBitmap/roaring/bitmapcontainer.go b/vendor/github.com/RoaringBitmap/roaring/bitmapcontainer.go index 5e58b31f2b..e749721bb2 100644 --- a/vendor/github.com/RoaringBitmap/roaring/bitmapcontainer.go +++ b/vendor/github.com/RoaringBitmap/roaring/bitmapcontainer.go @@ -110,14 +110,54 @@ func (bcsi *bitmapContainerShortIterator) hasNext() bool { return bcsi.i >= 0 } +func (bcsi *bitmapContainerShortIterator) peekNext() uint16 { + return uint16(bcsi.i) +} + +func (bcsi *bitmapContainerShortIterator) advanceIfNeeded(minval uint16) { + if bcsi.hasNext() && bcsi.peekNext() < minval { + bcsi.i = bcsi.ptr.NextSetBit(int(minval)) + } +} + func newBitmapContainerShortIterator(a *bitmapContainer) *bitmapContainerShortIterator { return &bitmapContainerShortIterator{a, a.NextSetBit(0)} } -func (bc *bitmapContainer) getShortIterator() shortIterable { +func (bc *bitmapContainer) getShortIterator() shortPeekable { return newBitmapContainerShortIterator(bc) } +type reverseBitmapContainerShortIterator struct { + ptr *bitmapContainer + i int +} + +func (bcsi *reverseBitmapContainerShortIterator) next() uint16 { + if bcsi.i == -1 { + panic("reverseBitmapContainerShortIterator.next() going beyond what is available") + } + + j := bcsi.i + bcsi.i = bcsi.ptr.PrevSetBit(bcsi.i - 1) + return uint16(j) +} + +func (bcsi *reverseBitmapContainerShortIterator) hasNext() bool { + return bcsi.i >= 0 +} + +func newReverseBitmapContainerShortIterator(a *bitmapContainer) *reverseBitmapContainerShortIterator { + if a.cardinality == 0 { + return &reverseBitmapContainerShortIterator{a, -1} + } + return &reverseBitmapContainerShortIterator{a, int(a.maximum())} +} + +func (bc *bitmapContainer) getReverseIterator() shortIterable { + return newReverseBitmapContainerShortIterator(bc) +} + type bitmapContainerManyIterator struct { ptr *bitmapContainer base int @@ -131,7 +171,7 @@ func (bcmi *bitmapContainerManyIterator) nextMany(hs uint32, buf []uint32) int { for n < len(buf) { if bitset == 0 { - base += 1 + base++ if base >= len(bcmi.ptr.bitmap) { bcmi.base = base bcmi.bitset = bitset @@ -177,16 +217,13 @@ func bitmapContainerSizeInBytes() int { func bitmapEquals(a, b []uint64) bool { if len(a) != len(b) { - //p("bitmaps differ on length. len(a)=%v; len(b)=%v", len(a), len(b)) return false } for i, v := range a { if v != b[i] { - //p("bitmaps differ on element i=%v", i) return false } } - //p("bitmapEquals returning true") return true } @@ -209,9 +246,7 @@ func (bc *bitmapContainer) fillLeastSignificant16bits(x []uint32, i int, mask ui func (bc *bitmapContainer) equals(o container) bool { srb, ok := o.(*bitmapContainer) if ok { - //p("bitmapContainers.equals: both are bitmapContainers") if srb.cardinality != bc.cardinality { - //p("bitmapContainers.equals: card differs: %v vs %v", srb.cardinality, bc.cardinality) return false } return bitmapEquals(bc.bitmap, srb.bitmap) @@ -261,12 +296,6 @@ func (bc *bitmapContainer) iremoveReturnMinimized(i uint16) container { // iremove returns true if i was found. func (bc *bitmapContainer) iremove(i uint16) bool { - /* branchless code - w := bc.bitmap[i>>6] - mask := uint64(1) << (i % 64) - neww := w &^ mask - bc.cardinality -= int((w ^ neww) >> (i % 64)) - bc.bitmap[i>>6] = neww */ if bc.contains(i) { bc.cardinality-- bc.bitmap[i/64] &^= (uint64(1) << (i % 64)) @@ -306,14 +335,10 @@ func (bc *bitmapContainer) iremoveRange(firstOfRange, lastOfRange int) container // flip all values in range [firstOfRange,endx) func (bc *bitmapContainer) inot(firstOfRange, endx int) container { - p("bc.inot() called with [%v, %v)", firstOfRange, endx) if endx-firstOfRange == maxCapacity { - //p("endx-firstOfRange == maxCapacity") flipBitmapRange(bc.bitmap, firstOfRange, endx) bc.cardinality = maxCapacity - bc.cardinality - //p("bc.cardinality is now %v", bc.cardinality) } else if endx-firstOfRange > maxCapacity/2 { - //p("endx-firstOfRange > maxCapacity/2") flipBitmapRange(bc.bitmap, firstOfRange, endx) bc.computeCardinality() } else { @@ -517,11 +542,31 @@ func (bc *bitmapContainer) iorBitmap(value2 *bitmapContainer) container { func (bc *bitmapContainer) lazyIORArray(value2 *arrayContainer) container { answer := bc c := value2.getCardinality() - for k := 0; k < c; k++ { + for k := 0; k+3 < c; k += 4 { + content := (*[4]uint16)(unsafe.Pointer(&value2.content[k])) + vc0 := content[0] + i0 := uint(vc0) >> 6 + answer.bitmap[i0] = answer.bitmap[i0] | (uint64(1) << (vc0 % 64)) + + vc1 := content[1] + i1 := uint(vc1) >> 6 + answer.bitmap[i1] = answer.bitmap[i1] | (uint64(1) << (vc1 % 64)) + + vc2 := content[2] + i2 := uint(vc2) >> 6 + answer.bitmap[i2] = answer.bitmap[i2] | (uint64(1) << (vc2 % 64)) + + vc3 := content[3] + i3 := uint(vc3) >> 6 + answer.bitmap[i3] = answer.bitmap[i3] | (uint64(1) << (vc3 % 64)) + } + + for k := c &^ 3; k < c; k++ { vc := value2.content[k] i := uint(vc) >> 6 answer.bitmap[i] = answer.bitmap[i] | (uint64(1) << (vc % 64)) } + answer.cardinality = invalidCardinality return answer } @@ -789,8 +834,6 @@ func (bc *bitmapContainer) andNotRun16(rc *runContainer16) container { } func (bc *bitmapContainer) iandNot(a container) container { - //p("bitmapContainer.iandNot() starting") - switch x := a.(type) { case *arrayContainer: return bc.iandNotArray(x) @@ -844,12 +887,15 @@ func (bc *bitmapContainer) andNotBitmap(value2 *bitmapContainer) container { return ac } -func (bc *bitmapContainer) iandNotBitmapSurely(value2 *bitmapContainer) *bitmapContainer { +func (bc *bitmapContainer) iandNotBitmapSurely(value2 *bitmapContainer) container { newCardinality := int(popcntMaskSlice(bc.bitmap, value2.bitmap)) for k := 0; k < len(bc.bitmap); k++ { bc.bitmap[k] = bc.bitmap[k] &^ value2.bitmap[k] } bc.cardinality = newCardinality + if bc.getCardinality() <= arrayDefaultMaxSize { + return bc.toArrayContainer() + } return bc } @@ -917,6 +963,32 @@ func (bc *bitmapContainer) NextSetBit(i int) int { return -1 } +func (bc *bitmapContainer) PrevSetBit(i int) int { + if i < 0 { + return -1 + } + x := i / 64 + if x >= len(bc.bitmap) { + return -1 + } + + w := bc.bitmap[x] + + b := i % 64 + + w = w << uint(63-b) + if w != 0 { + return i - countLeadingZeros(w) + } + x-- + for ; x >= 0; x-- { + if bc.bitmap[x] != 0 { + return (x * 64) + 63 - countLeadingZeros(bc.bitmap[x]) + } + } + return -1 +} + // reference the java implementation // https://github.com/RoaringBitmap/RoaringBitmap/blob/master/src/main/java/org/roaringbitmap/BitmapContainer.java#L875-L892 // @@ -980,3 +1052,35 @@ func newBitmapContainerFromRun(rc *runContainer16) *bitmapContainer { func (bc *bitmapContainer) containerType() contype { return bitmapContype } + +func (bc *bitmapContainer) addOffset(x uint16) []container { + low := newBitmapContainer() + high := newBitmapContainer() + b := uint32(x) >> 6 + i := uint32(x) % 64 + end := uint32(1024) - b + if i == 0 { + copy(low.bitmap[b:], bc.bitmap[:end]) + copy(high.bitmap[:b], bc.bitmap[end:]) + } else { + low.bitmap[b] = bc.bitmap[0] << i + for k := uint32(1); k < end; k++ { + newval := bc.bitmap[k] << i + if newval == 0 { + newval = bc.bitmap[k-1] >> (64 - i) + } + low.bitmap[b+k] = newval + } + for k := end; k < 1024; k++ { + newval := bc.bitmap[k] << i + if newval == 0 { + newval = bc.bitmap[k-1] >> (64 - i) + } + high.bitmap[k-end] = newval + } + high.bitmap[b] = bc.bitmap[1023] >> (64 - i) + } + low.computeCardinality() + high.computeCardinality() + return []container{low, high} +} |