1package roaring 2 3import ( 4 "fmt" 5 "unsafe" 6) 7 8//go:generate msgp -unexported 9 10type bitmapContainer struct { 11 cardinality int 12 bitmap []uint64 13} 14 15func (bc bitmapContainer) String() string { 16 var s string 17 for it := bc.getShortIterator(); it.hasNext(); { 18 s += fmt.Sprintf("%v, ", it.next()) 19 } 20 return s 21} 22 23func newBitmapContainer() *bitmapContainer { 24 p := new(bitmapContainer) 25 size := (1 << 16) / 64 26 p.bitmap = make([]uint64, size, size) 27 return p 28} 29 30func newBitmapContainerwithRange(firstOfRun, lastOfRun int) *bitmapContainer { 31 bc := newBitmapContainer() 32 bc.cardinality = lastOfRun - firstOfRun + 1 33 if bc.cardinality == maxCapacity { 34 fill(bc.bitmap, uint64(0xffffffffffffffff)) 35 } else { 36 firstWord := firstOfRun / 64 37 lastWord := lastOfRun / 64 38 zeroPrefixLength := uint64(firstOfRun & 63) 39 zeroSuffixLength := uint64(63 - (lastOfRun & 63)) 40 41 fillRange(bc.bitmap, firstWord, lastWord+1, uint64(0xffffffffffffffff)) 42 bc.bitmap[firstWord] ^= ((uint64(1) << zeroPrefixLength) - 1) 43 blockOfOnes := (uint64(1) << zeroSuffixLength) - 1 44 maskOnLeft := blockOfOnes << (uint64(64) - zeroSuffixLength) 45 bc.bitmap[lastWord] ^= maskOnLeft 46 } 47 return bc 48} 49 50func (bc *bitmapContainer) minimum() uint16 { 51 for i := 0; i < len(bc.bitmap); i++ { 52 w := bc.bitmap[i] 53 if w != 0 { 54 r := countTrailingZeros(w) 55 return uint16(r + i*64) 56 } 57 } 58 return MaxUint16 59} 60 61// i should be non-zero 62func clz(i uint64) int { 63 n := 1 64 x := uint32(i >> 32) 65 if x == 0 { 66 n += 32 67 x = uint32(i) 68 } 69 if x>>16 == 0 { 70 n += 16 71 x = x << 16 72 } 73 if x>>24 == 0 { 74 n += 8 75 x = x << 8 76 } 77 if x>>28 == 0 { 78 n += 4 79 x = x << 4 80 } 81 if x>>30 == 0 { 82 n += 2 83 x = x << 2 84 } 85 return n - int(x>>31) 86} 87 88func (bc *bitmapContainer) maximum() uint16 { 89 for i := len(bc.bitmap); i > 0; i-- { 90 w := bc.bitmap[i-1] 91 if w != 0 { 92 r := clz(w) 93 return uint16((i-1)*64 + 63 - r) 94 } 95 } 96 return uint16(0) 97} 98 99type bitmapContainerShortIterator struct { 100 ptr *bitmapContainer 101 i int 102} 103 104func (bcsi *bitmapContainerShortIterator) next() uint16 { 105 j := bcsi.i 106 bcsi.i = bcsi.ptr.NextSetBit(bcsi.i + 1) 107 return uint16(j) 108} 109func (bcsi *bitmapContainerShortIterator) hasNext() bool { 110 return bcsi.i >= 0 111} 112 113func newBitmapContainerShortIterator(a *bitmapContainer) *bitmapContainerShortIterator { 114 return &bitmapContainerShortIterator{a, a.NextSetBit(0)} 115} 116 117func (bc *bitmapContainer) getShortIterator() shortIterable { 118 return newBitmapContainerShortIterator(bc) 119} 120 121type reverseBitmapContainerShortIterator struct { 122 ptr *bitmapContainer 123 i int 124} 125 126func (bcsi *reverseBitmapContainerShortIterator) next() uint16 { 127 if bcsi.i == -1 { 128 panic("reverseBitmapContainerShortIterator.next() going beyond what is available") 129 } 130 131 j := bcsi.i 132 bcsi.i = bcsi.ptr.PrevSetBit(bcsi.i - 1) 133 return uint16(j) 134} 135 136func (bcsi *reverseBitmapContainerShortIterator) hasNext() bool { 137 return bcsi.i >= 0 138} 139 140func newReverseBitmapContainerShortIterator(a *bitmapContainer) *reverseBitmapContainerShortIterator { 141 if a.cardinality == 0 { 142 return &reverseBitmapContainerShortIterator{a, -1} 143 } 144 return &reverseBitmapContainerShortIterator{a, int(a.maximum())} 145} 146 147func (bc *bitmapContainer) getReverseIterator() shortIterable { 148 return newReverseBitmapContainerShortIterator(bc) 149} 150 151type bitmapContainerManyIterator struct { 152 ptr *bitmapContainer 153 base int 154 bitset uint64 155} 156 157func (bcmi *bitmapContainerManyIterator) nextMany(hs uint32, buf []uint32) int { 158 n := 0 159 base := bcmi.base 160 bitset := bcmi.bitset 161 162 for n < len(buf) { 163 if bitset == 0 { 164 base++ 165 if base >= len(bcmi.ptr.bitmap) { 166 bcmi.base = base 167 bcmi.bitset = bitset 168 return n 169 } 170 bitset = bcmi.ptr.bitmap[base] 171 continue 172 } 173 t := bitset & -bitset 174 buf[n] = uint32(((base * 64) + int(popcount(t-1)))) | hs 175 n = n + 1 176 bitset ^= t 177 } 178 179 bcmi.base = base 180 bcmi.bitset = bitset 181 return n 182} 183 184func newBitmapContainerManyIterator(a *bitmapContainer) *bitmapContainerManyIterator { 185 return &bitmapContainerManyIterator{a, -1, 0} 186} 187 188func (bc *bitmapContainer) getManyIterator() manyIterable { 189 return newBitmapContainerManyIterator(bc) 190} 191 192func (bc *bitmapContainer) getSizeInBytes() int { 193 return len(bc.bitmap) * 8 // + bcBaseBytes 194} 195 196func (bc *bitmapContainer) serializedSizeInBytes() int { 197 //return bc.Msgsize()// NOO! This breaks GetSerializedSizeInBytes 198 return len(bc.bitmap) * 8 199} 200 201const bcBaseBytes = int(unsafe.Sizeof(bitmapContainer{})) 202 203// bitmapContainer doesn't depend on card, always fully allocated 204func bitmapContainerSizeInBytes() int { 205 return bcBaseBytes + (1<<16)/8 206} 207 208func bitmapEquals(a, b []uint64) bool { 209 if len(a) != len(b) { 210 return false 211 } 212 for i, v := range a { 213 if v != b[i] { 214 return false 215 } 216 } 217 return true 218} 219 220func (bc *bitmapContainer) fillLeastSignificant16bits(x []uint32, i int, mask uint32) { 221 // TODO: should be written as optimized assembly 222 pos := i 223 base := mask 224 for k := 0; k < len(bc.bitmap); k++ { 225 bitset := bc.bitmap[k] 226 for bitset != 0 { 227 t := bitset & -bitset 228 x[pos] = base + uint32(popcount(t-1)) 229 pos++ 230 bitset ^= t 231 } 232 base += 64 233 } 234} 235 236func (bc *bitmapContainer) equals(o container) bool { 237 srb, ok := o.(*bitmapContainer) 238 if ok { 239 if srb.cardinality != bc.cardinality { 240 return false 241 } 242 return bitmapEquals(bc.bitmap, srb.bitmap) 243 } 244 245 // use generic comparison 246 if bc.getCardinality() != o.getCardinality() { 247 return false 248 } 249 ait := o.getShortIterator() 250 bit := bc.getShortIterator() 251 252 for ait.hasNext() { 253 if bit.next() != ait.next() { 254 return false 255 } 256 } 257 return true 258} 259 260func (bc *bitmapContainer) iaddReturnMinimized(i uint16) container { 261 bc.iadd(i) 262 if bc.isFull() { 263 return newRunContainer16Range(0, MaxUint16) 264 } 265 return bc 266} 267 268func (bc *bitmapContainer) iadd(i uint16) bool { 269 x := int(i) 270 previous := bc.bitmap[x/64] 271 mask := uint64(1) << (uint(x) % 64) 272 newb := previous | mask 273 bc.bitmap[x/64] = newb 274 bc.cardinality += int((previous ^ newb) >> (uint(x) % 64)) 275 return newb != previous 276} 277 278func (bc *bitmapContainer) iremoveReturnMinimized(i uint16) container { 279 if bc.iremove(i) { 280 if bc.cardinality == arrayDefaultMaxSize { 281 return bc.toArrayContainer() 282 } 283 } 284 return bc 285} 286 287// iremove returns true if i was found. 288func (bc *bitmapContainer) iremove(i uint16) bool { 289 if bc.contains(i) { 290 bc.cardinality-- 291 bc.bitmap[i/64] &^= (uint64(1) << (i % 64)) 292 return true 293 } 294 return false 295} 296 297func (bc *bitmapContainer) isFull() bool { 298 return bc.cardinality == int(MaxUint16)+1 299} 300 301func (bc *bitmapContainer) getCardinality() int { 302 return bc.cardinality 303} 304 305func (bc *bitmapContainer) clone() container { 306 ptr := bitmapContainer{bc.cardinality, make([]uint64, len(bc.bitmap))} 307 copy(ptr.bitmap, bc.bitmap[:]) 308 return &ptr 309} 310 311// add all values in range [firstOfRange,lastOfRange) 312func (bc *bitmapContainer) iaddRange(firstOfRange, lastOfRange int) container { 313 bc.cardinality += setBitmapRangeAndCardinalityChange(bc.bitmap, firstOfRange, lastOfRange) 314 return bc 315} 316 317// remove all values in range [firstOfRange,lastOfRange) 318func (bc *bitmapContainer) iremoveRange(firstOfRange, lastOfRange int) container { 319 bc.cardinality += resetBitmapRangeAndCardinalityChange(bc.bitmap, firstOfRange, lastOfRange) 320 if bc.getCardinality() <= arrayDefaultMaxSize { 321 return bc.toArrayContainer() 322 } 323 return bc 324} 325 326// flip all values in range [firstOfRange,endx) 327func (bc *bitmapContainer) inot(firstOfRange, endx int) container { 328 if endx-firstOfRange == maxCapacity { 329 flipBitmapRange(bc.bitmap, firstOfRange, endx) 330 bc.cardinality = maxCapacity - bc.cardinality 331 } else if endx-firstOfRange > maxCapacity/2 { 332 flipBitmapRange(bc.bitmap, firstOfRange, endx) 333 bc.computeCardinality() 334 } else { 335 bc.cardinality += flipBitmapRangeAndCardinalityChange(bc.bitmap, firstOfRange, endx) 336 } 337 if bc.getCardinality() <= arrayDefaultMaxSize { 338 return bc.toArrayContainer() 339 } 340 return bc 341} 342 343// flip all values in range [firstOfRange,endx) 344func (bc *bitmapContainer) not(firstOfRange, endx int) container { 345 answer := bc.clone() 346 return answer.inot(firstOfRange, endx) 347} 348 349func (bc *bitmapContainer) or(a container) container { 350 switch x := a.(type) { 351 case *arrayContainer: 352 return bc.orArray(x) 353 case *bitmapContainer: 354 return bc.orBitmap(x) 355 case *runContainer16: 356 if x.isFull() { 357 return x.clone() 358 } 359 return x.orBitmapContainer(bc) 360 } 361 panic("unsupported container type") 362} 363 364func (bc *bitmapContainer) orCardinality(a container) int { 365 switch x := a.(type) { 366 case *arrayContainer: 367 return bc.orArrayCardinality(x) 368 case *bitmapContainer: 369 return bc.orBitmapCardinality(x) 370 case *runContainer16: 371 return x.orBitmapContainerCardinality(bc) 372 } 373 panic("unsupported container type") 374} 375 376func (bc *bitmapContainer) ior(a container) container { 377 switch x := a.(type) { 378 case *arrayContainer: 379 return bc.iorArray(x) 380 case *bitmapContainer: 381 return bc.iorBitmap(x) 382 case *runContainer16: 383 if x.isFull() { 384 return x.clone() 385 } 386 for i := range x.iv { 387 bc.iaddRange(int(x.iv[i].start), int(x.iv[i].last())+1) 388 } 389 if bc.isFull() { 390 return newRunContainer16Range(0, MaxUint16) 391 } 392 //bc.computeCardinality() 393 return bc 394 } 395 panic(fmt.Errorf("unsupported container type %T", a)) 396} 397 398func (bc *bitmapContainer) lazyIOR(a container) container { 399 switch x := a.(type) { 400 case *arrayContainer: 401 return bc.lazyIORArray(x) 402 case *bitmapContainer: 403 return bc.lazyIORBitmap(x) 404 case *runContainer16: 405 if x.isFull() { 406 return x.clone() 407 } 408 409 // Manually inlined setBitmapRange function 410 bitmap := bc.bitmap 411 for _, iv := range x.iv { 412 start := int(iv.start) 413 end := int(iv.last()) + 1 414 if start >= end { 415 continue 416 } 417 firstword := start / 64 418 endword := (end - 1) / 64 419 if firstword == endword { 420 bitmap[firstword] |= (^uint64(0) << uint(start%64)) & (^uint64(0) >> (uint(-end) % 64)) 421 continue 422 } 423 bitmap[firstword] |= ^uint64(0) << uint(start%64) 424 for i := firstword + 1; i < endword; i++ { 425 bitmap[i] = ^uint64(0) 426 } 427 bitmap[endword] |= ^uint64(0) >> (uint(-end) % 64) 428 } 429 bc.cardinality = invalidCardinality 430 return bc 431 } 432 panic("unsupported container type") 433} 434 435func (bc *bitmapContainer) lazyOR(a container) container { 436 switch x := a.(type) { 437 case *arrayContainer: 438 return bc.lazyORArray(x) 439 case *bitmapContainer: 440 return bc.lazyORBitmap(x) 441 case *runContainer16: 442 if x.isFull() { 443 return x.clone() 444 } 445 // TODO: implement lazy OR 446 return x.orBitmapContainer(bc) 447 448 } 449 panic("unsupported container type") 450} 451 452func (bc *bitmapContainer) orArray(value2 *arrayContainer) container { 453 answer := bc.clone().(*bitmapContainer) 454 c := value2.getCardinality() 455 for k := 0; k < c; k++ { 456 v := value2.content[k] 457 i := uint(v) >> 6 458 bef := answer.bitmap[i] 459 aft := bef | (uint64(1) << (v % 64)) 460 answer.bitmap[i] = aft 461 answer.cardinality += int((bef - aft) >> 63) 462 } 463 return answer 464} 465 466func (bc *bitmapContainer) orArrayCardinality(value2 *arrayContainer) int { 467 answer := 0 468 c := value2.getCardinality() 469 for k := 0; k < c; k++ { 470 // branchless: 471 v := value2.content[k] 472 i := uint(v) >> 6 473 bef := bc.bitmap[i] 474 aft := bef | (uint64(1) << (v % 64)) 475 answer += int((bef - aft) >> 63) 476 } 477 return answer 478} 479 480func (bc *bitmapContainer) orBitmap(value2 *bitmapContainer) container { 481 answer := newBitmapContainer() 482 for k := 0; k < len(answer.bitmap); k++ { 483 answer.bitmap[k] = bc.bitmap[k] | value2.bitmap[k] 484 } 485 answer.computeCardinality() 486 if answer.isFull() { 487 return newRunContainer16Range(0, MaxUint16) 488 } 489 return answer 490} 491 492func (bc *bitmapContainer) orBitmapCardinality(value2 *bitmapContainer) int { 493 return int(popcntOrSlice(bc.bitmap, value2.bitmap)) 494} 495 496func (bc *bitmapContainer) andBitmapCardinality(value2 *bitmapContainer) int { 497 return int(popcntAndSlice(bc.bitmap, value2.bitmap)) 498} 499 500func (bc *bitmapContainer) computeCardinality() { 501 bc.cardinality = int(popcntSlice(bc.bitmap)) 502} 503 504func (bc *bitmapContainer) iorArray(ac *arrayContainer) container { 505 for k := range ac.content { 506 vc := ac.content[k] 507 i := uint(vc) >> 6 508 bef := bc.bitmap[i] 509 aft := bef | (uint64(1) << (vc % 64)) 510 bc.bitmap[i] = aft 511 bc.cardinality += int((bef - aft) >> 63) 512 } 513 if bc.isFull() { 514 return newRunContainer16Range(0, MaxUint16) 515 } 516 return bc 517} 518 519func (bc *bitmapContainer) iorBitmap(value2 *bitmapContainer) container { 520 answer := bc 521 answer.cardinality = 0 522 for k := 0; k < len(answer.bitmap); k++ { 523 answer.bitmap[k] = bc.bitmap[k] | value2.bitmap[k] 524 } 525 answer.computeCardinality() 526 if bc.isFull() { 527 return newRunContainer16Range(0, MaxUint16) 528 } 529 return answer 530} 531 532func (bc *bitmapContainer) lazyIORArray(value2 *arrayContainer) container { 533 answer := bc 534 c := value2.getCardinality() 535 for k := 0; k < c; k++ { 536 vc := value2.content[k] 537 i := uint(vc) >> 6 538 answer.bitmap[i] = answer.bitmap[i] | (uint64(1) << (vc % 64)) 539 } 540 answer.cardinality = invalidCardinality 541 return answer 542} 543 544func (bc *bitmapContainer) lazyORArray(value2 *arrayContainer) container { 545 answer := bc.clone().(*bitmapContainer) 546 return answer.lazyIORArray(value2) 547} 548 549func (bc *bitmapContainer) lazyIORBitmap(value2 *bitmapContainer) container { 550 answer := bc 551 for k := 0; k < len(answer.bitmap); k++ { 552 answer.bitmap[k] = bc.bitmap[k] | value2.bitmap[k] 553 } 554 bc.cardinality = invalidCardinality 555 return answer 556} 557 558func (bc *bitmapContainer) lazyORBitmap(value2 *bitmapContainer) container { 559 answer := bc.clone().(*bitmapContainer) 560 return answer.lazyIORBitmap(value2) 561} 562 563func (bc *bitmapContainer) xor(a container) container { 564 switch x := a.(type) { 565 case *arrayContainer: 566 return bc.xorArray(x) 567 case *bitmapContainer: 568 return bc.xorBitmap(x) 569 case *runContainer16: 570 return x.xorBitmap(bc) 571 } 572 panic("unsupported container type") 573} 574 575func (bc *bitmapContainer) xorArray(value2 *arrayContainer) container { 576 answer := bc.clone().(*bitmapContainer) 577 c := value2.getCardinality() 578 for k := 0; k < c; k++ { 579 vc := value2.content[k] 580 index := uint(vc) >> 6 581 abi := answer.bitmap[index] 582 mask := uint64(1) << (vc % 64) 583 answer.cardinality += 1 - 2*int((abi&mask)>>(vc%64)) 584 answer.bitmap[index] = abi ^ mask 585 } 586 if answer.cardinality <= arrayDefaultMaxSize { 587 return answer.toArrayContainer() 588 } 589 return answer 590} 591 592func (bc *bitmapContainer) rank(x uint16) int { 593 // TODO: rewrite in assembly 594 leftover := (uint(x) + 1) & 63 595 if leftover == 0 { 596 return int(popcntSlice(bc.bitmap[:(uint(x)+1)/64])) 597 } 598 return int(popcntSlice(bc.bitmap[:(uint(x)+1)/64]) + popcount(bc.bitmap[(uint(x)+1)/64]<<(64-leftover))) 599} 600 601func (bc *bitmapContainer) selectInt(x uint16) int { 602 remaining := x 603 for k := 0; k < len(bc.bitmap); k++ { 604 w := popcount(bc.bitmap[k]) 605 if uint16(w) > remaining { 606 return k*64 + selectBitPosition(bc.bitmap[k], int(remaining)) 607 } 608 remaining -= uint16(w) 609 } 610 return -1 611} 612 613func (bc *bitmapContainer) xorBitmap(value2 *bitmapContainer) container { 614 newCardinality := int(popcntXorSlice(bc.bitmap, value2.bitmap)) 615 616 if newCardinality > arrayDefaultMaxSize { 617 answer := newBitmapContainer() 618 for k := 0; k < len(answer.bitmap); k++ { 619 answer.bitmap[k] = bc.bitmap[k] ^ value2.bitmap[k] 620 } 621 answer.cardinality = newCardinality 622 if answer.isFull() { 623 return newRunContainer16Range(0, MaxUint16) 624 } 625 return answer 626 } 627 ac := newArrayContainerSize(newCardinality) 628 fillArrayXOR(ac.content, bc.bitmap, value2.bitmap) 629 ac.content = ac.content[:newCardinality] 630 return ac 631} 632 633func (bc *bitmapContainer) and(a container) container { 634 switch x := a.(type) { 635 case *arrayContainer: 636 return bc.andArray(x) 637 case *bitmapContainer: 638 return bc.andBitmap(x) 639 case *runContainer16: 640 if x.isFull() { 641 return bc.clone() 642 } 643 return x.andBitmapContainer(bc) 644 } 645 panic("unsupported container type") 646} 647 648func (bc *bitmapContainer) andCardinality(a container) int { 649 switch x := a.(type) { 650 case *arrayContainer: 651 return bc.andArrayCardinality(x) 652 case *bitmapContainer: 653 return bc.andBitmapCardinality(x) 654 case *runContainer16: 655 return x.andBitmapContainerCardinality(bc) 656 } 657 panic("unsupported container type") 658} 659 660func (bc *bitmapContainer) intersects(a container) bool { 661 switch x := a.(type) { 662 case *arrayContainer: 663 return bc.intersectsArray(x) 664 case *bitmapContainer: 665 return bc.intersectsBitmap(x) 666 case *runContainer16: 667 return x.intersects(bc) 668 669 } 670 panic("unsupported container type") 671} 672 673func (bc *bitmapContainer) iand(a container) container { 674 switch x := a.(type) { 675 case *arrayContainer: 676 return bc.iandArray(x) 677 case *bitmapContainer: 678 return bc.iandBitmap(x) 679 case *runContainer16: 680 if x.isFull() { 681 return bc.clone() 682 } 683 return bc.iandRun16(x) 684 } 685 panic("unsupported container type") 686} 687 688func (bc *bitmapContainer) iandRun16(rc *runContainer16) container { 689 rcb := newBitmapContainerFromRun(rc) 690 return bc.iandBitmap(rcb) 691} 692 693func (bc *bitmapContainer) iandArray(ac *arrayContainer) container { 694 acb := ac.toBitmapContainer() 695 return bc.iandBitmap(acb) 696} 697 698func (bc *bitmapContainer) andArray(value2 *arrayContainer) *arrayContainer { 699 answer := newArrayContainerCapacity(len(value2.content)) 700 answer.content = answer.content[:cap(answer.content)] 701 c := value2.getCardinality() 702 pos := 0 703 for k := 0; k < c; k++ { 704 v := value2.content[k] 705 answer.content[pos] = v 706 pos += int(bc.bitValue(v)) 707 } 708 answer.content = answer.content[:pos] 709 return answer 710} 711 712func (bc *bitmapContainer) andArrayCardinality(value2 *arrayContainer) int { 713 c := value2.getCardinality() 714 pos := 0 715 for k := 0; k < c; k++ { 716 v := value2.content[k] 717 pos += int(bc.bitValue(v)) 718 } 719 return pos 720} 721 722func (bc *bitmapContainer) getCardinalityInRange(start, end uint) int { 723 if start >= end { 724 return 0 725 } 726 firstword := start / 64 727 endword := (end - 1) / 64 728 const allones = ^uint64(0) 729 if firstword == endword { 730 return int(popcount(bc.bitmap[firstword] & ((allones << (start % 64)) & (allones >> ((64 - end) & 63))))) 731 } 732 answer := popcount(bc.bitmap[firstword] & (allones << (start % 64))) 733 answer += popcntSlice(bc.bitmap[firstword+1 : endword]) 734 answer += popcount(bc.bitmap[endword] & (allones >> ((64 - end) & 63))) 735 return int(answer) 736} 737 738func (bc *bitmapContainer) andBitmap(value2 *bitmapContainer) container { 739 newcardinality := int(popcntAndSlice(bc.bitmap, value2.bitmap)) 740 if newcardinality > arrayDefaultMaxSize { 741 answer := newBitmapContainer() 742 for k := 0; k < len(answer.bitmap); k++ { 743 answer.bitmap[k] = bc.bitmap[k] & value2.bitmap[k] 744 } 745 answer.cardinality = newcardinality 746 return answer 747 } 748 ac := newArrayContainerSize(newcardinality) 749 fillArrayAND(ac.content, bc.bitmap, value2.bitmap) 750 ac.content = ac.content[:newcardinality] //not sure why i need this 751 return ac 752 753} 754 755func (bc *bitmapContainer) intersectsArray(value2 *arrayContainer) bool { 756 c := value2.getCardinality() 757 for k := 0; k < c; k++ { 758 v := value2.content[k] 759 if bc.contains(v) { 760 return true 761 } 762 } 763 return false 764} 765 766func (bc *bitmapContainer) intersectsBitmap(value2 *bitmapContainer) bool { 767 for k := 0; k < len(bc.bitmap); k++ { 768 if (bc.bitmap[k] & value2.bitmap[k]) != 0 { 769 return true 770 } 771 } 772 return false 773 774} 775 776func (bc *bitmapContainer) iandBitmap(value2 *bitmapContainer) container { 777 newcardinality := int(popcntAndSlice(bc.bitmap, value2.bitmap)) 778 for k := 0; k < len(bc.bitmap); k++ { 779 bc.bitmap[k] = bc.bitmap[k] & value2.bitmap[k] 780 } 781 bc.cardinality = newcardinality 782 783 if newcardinality <= arrayDefaultMaxSize { 784 return newArrayContainerFromBitmap(bc) 785 } 786 return bc 787} 788 789func (bc *bitmapContainer) andNot(a container) container { 790 switch x := a.(type) { 791 case *arrayContainer: 792 return bc.andNotArray(x) 793 case *bitmapContainer: 794 return bc.andNotBitmap(x) 795 case *runContainer16: 796 return bc.andNotRun16(x) 797 } 798 panic("unsupported container type") 799} 800 801func (bc *bitmapContainer) andNotRun16(rc *runContainer16) container { 802 rcb := rc.toBitmapContainer() 803 return bc.andNotBitmap(rcb) 804} 805 806func (bc *bitmapContainer) iandNot(a container) container { 807 switch x := a.(type) { 808 case *arrayContainer: 809 return bc.iandNotArray(x) 810 case *bitmapContainer: 811 return bc.iandNotBitmapSurely(x) 812 case *runContainer16: 813 return bc.iandNotRun16(x) 814 } 815 panic("unsupported container type") 816} 817 818func (bc *bitmapContainer) iandNotArray(ac *arrayContainer) container { 819 acb := ac.toBitmapContainer() 820 return bc.iandNotBitmapSurely(acb) 821} 822 823func (bc *bitmapContainer) iandNotRun16(rc *runContainer16) container { 824 rcb := rc.toBitmapContainer() 825 return bc.iandNotBitmapSurely(rcb) 826} 827 828func (bc *bitmapContainer) andNotArray(value2 *arrayContainer) container { 829 answer := bc.clone().(*bitmapContainer) 830 c := value2.getCardinality() 831 for k := 0; k < c; k++ { 832 vc := value2.content[k] 833 i := uint(vc) >> 6 834 oldv := answer.bitmap[i] 835 newv := oldv &^ (uint64(1) << (vc % 64)) 836 answer.bitmap[i] = newv 837 answer.cardinality -= int((oldv ^ newv) >> (vc % 64)) 838 } 839 if answer.cardinality <= arrayDefaultMaxSize { 840 return answer.toArrayContainer() 841 } 842 return answer 843} 844 845func (bc *bitmapContainer) andNotBitmap(value2 *bitmapContainer) container { 846 newCardinality := int(popcntMaskSlice(bc.bitmap, value2.bitmap)) 847 if newCardinality > arrayDefaultMaxSize { 848 answer := newBitmapContainer() 849 for k := 0; k < len(answer.bitmap); k++ { 850 answer.bitmap[k] = bc.bitmap[k] &^ value2.bitmap[k] 851 } 852 answer.cardinality = newCardinality 853 return answer 854 } 855 ac := newArrayContainerSize(newCardinality) 856 fillArrayANDNOT(ac.content, bc.bitmap, value2.bitmap) 857 return ac 858} 859 860func (bc *bitmapContainer) iandNotBitmapSurely(value2 *bitmapContainer) container { 861 newCardinality := int(popcntMaskSlice(bc.bitmap, value2.bitmap)) 862 for k := 0; k < len(bc.bitmap); k++ { 863 bc.bitmap[k] = bc.bitmap[k] &^ value2.bitmap[k] 864 } 865 bc.cardinality = newCardinality 866 if bc.getCardinality() <= arrayDefaultMaxSize { 867 return bc.toArrayContainer() 868 } 869 return bc 870} 871 872func (bc *bitmapContainer) contains(i uint16) bool { //testbit 873 x := uint(i) 874 w := bc.bitmap[x>>6] 875 mask := uint64(1) << (x & 63) 876 return (w & mask) != 0 877} 878 879func (bc *bitmapContainer) bitValue(i uint16) uint64 { 880 x := uint(i) 881 w := bc.bitmap[x>>6] 882 return (w >> (x & 63)) & 1 883} 884 885func (bc *bitmapContainer) loadData(arrayContainer *arrayContainer) { 886 bc.cardinality = arrayContainer.getCardinality() 887 c := arrayContainer.getCardinality() 888 for k := 0; k < c; k++ { 889 x := arrayContainer.content[k] 890 i := int(x) / 64 891 bc.bitmap[i] |= (uint64(1) << uint(x%64)) 892 } 893} 894 895func (bc *bitmapContainer) toArrayContainer() *arrayContainer { 896 ac := &arrayContainer{} 897 ac.loadData(bc) 898 return ac 899} 900 901func (bc *bitmapContainer) fillArray(container []uint16) { 902 //TODO: rewrite in assembly 903 pos := 0 904 base := 0 905 for k := 0; k < len(bc.bitmap); k++ { 906 bitset := bc.bitmap[k] 907 for bitset != 0 { 908 t := bitset & -bitset 909 container[pos] = uint16((base + int(popcount(t-1)))) 910 pos = pos + 1 911 bitset ^= t 912 } 913 base += 64 914 } 915} 916 917func (bc *bitmapContainer) NextSetBit(i int) int { 918 x := i / 64 919 if x >= len(bc.bitmap) { 920 return -1 921 } 922 w := bc.bitmap[x] 923 w = w >> uint(i%64) 924 if w != 0 { 925 return i + countTrailingZeros(w) 926 } 927 x++ 928 for ; x < len(bc.bitmap); x++ { 929 if bc.bitmap[x] != 0 { 930 return (x * 64) + countTrailingZeros(bc.bitmap[x]) 931 } 932 } 933 return -1 934} 935 936func (bc *bitmapContainer) PrevSetBit(i int) int { 937 if i < 0 { 938 return -1 939 } 940 x := i / 64 941 if x >= len(bc.bitmap) { 942 return -1 943 } 944 945 w := bc.bitmap[x] 946 947 b := i % 64 948 949 w = w << uint(63-b) 950 if w != 0 { 951 return b - countLeadingZeros(w) 952 } 953 x-- 954 for ; x >= 0; x-- { 955 if bc.bitmap[x] != 0 { 956 return (x * 64) + 63 - countLeadingZeros(bc.bitmap[x]) 957 } 958 } 959 return -1 960} 961 962// reference the java implementation 963// https://github.com/RoaringBitmap/RoaringBitmap/blob/master/src/main/java/org/roaringbitmap/BitmapContainer.java#L875-L892 964// 965func (bc *bitmapContainer) numberOfRuns() int { 966 if bc.cardinality == 0 { 967 return 0 968 } 969 970 var numRuns uint64 971 nextWord := bc.bitmap[0] 972 973 for i := 0; i < len(bc.bitmap)-1; i++ { 974 word := nextWord 975 nextWord = bc.bitmap[i+1] 976 numRuns += popcount((^word)&(word<<1)) + ((word >> 63) &^ nextWord) 977 } 978 979 word := nextWord 980 numRuns += popcount((^word) & (word << 1)) 981 if (word & 0x8000000000000000) != 0 { 982 numRuns++ 983 } 984 985 return int(numRuns) 986} 987 988// convert to run or array *if needed* 989func (bc *bitmapContainer) toEfficientContainer() container { 990 991 numRuns := bc.numberOfRuns() 992 993 sizeAsRunContainer := runContainer16SerializedSizeInBytes(numRuns) 994 sizeAsBitmapContainer := bitmapContainerSizeInBytes() 995 card := bc.getCardinality() 996 sizeAsArrayContainer := arrayContainerSizeInBytes(card) 997 998 if sizeAsRunContainer <= minOfInt(sizeAsBitmapContainer, sizeAsArrayContainer) { 999 return newRunContainer16FromBitmapContainer(bc) 1000 } 1001 if card <= arrayDefaultMaxSize { 1002 return bc.toArrayContainer() 1003 } 1004 return bc 1005} 1006 1007func newBitmapContainerFromRun(rc *runContainer16) *bitmapContainer { 1008 1009 if len(rc.iv) == 1 { 1010 return newBitmapContainerwithRange(int(rc.iv[0].start), int(rc.iv[0].last())) 1011 } 1012 1013 bc := newBitmapContainer() 1014 for i := range rc.iv { 1015 setBitmapRange(bc.bitmap, int(rc.iv[i].start), int(rc.iv[i].last())+1) 1016 bc.cardinality += int(rc.iv[i].last()) + 1 - int(rc.iv[i].start) 1017 } 1018 //bc.computeCardinality() 1019 return bc 1020} 1021 1022func (bc *bitmapContainer) containerType() contype { 1023 return bitmapContype 1024} 1025 1026func (bc *bitmapContainer) addOffset(x uint16) []container { 1027 low := newBitmapContainer() 1028 high := newBitmapContainer() 1029 b := uint32(x) >> 6 1030 i := uint32(x) % 64 1031 end := uint32(1024) - b 1032 if i == 0 { 1033 copy(low.bitmap[b:], bc.bitmap[:end]) 1034 copy(high.bitmap[:b], bc.bitmap[end:]) 1035 } else { 1036 low.bitmap[b] = bc.bitmap[0] << i 1037 for k := uint32(1); k < end; k++ { 1038 newval := bc.bitmap[k] << i 1039 if newval == 0 { 1040 newval = bc.bitmap[k-1] >> (64 - i) 1041 } 1042 low.bitmap[b+k] = newval 1043 } 1044 for k := end; k < 1024; k++ { 1045 newval := bc.bitmap[k] << i 1046 if newval == 0 { 1047 newval = bc.bitmap[k-1] >> (64 - i) 1048 } 1049 high.bitmap[k-end] = newval 1050 } 1051 high.bitmap[b] = bc.bitmap[1023] >> (64 - i) 1052 } 1053 low.computeCardinality() 1054 high.computeCardinality() 1055 return []container{low, high} 1056} 1057