summaryrefslogtreecommitdiff
path: root/vendor/github.com/bits-and-blooms
diff options
context:
space:
mode:
Diffstat (limited to 'vendor/github.com/bits-and-blooms')
-rw-r--r--vendor/github.com/bits-and-blooms/bitset/.gitignore26
-rw-r--r--vendor/github.com/bits-and-blooms/bitset/.travis.yml37
-rw-r--r--vendor/github.com/bits-and-blooms/bitset/LICENSE27
-rw-r--r--vendor/github.com/bits-and-blooms/bitset/README.md93
-rw-r--r--vendor/github.com/bits-and-blooms/bitset/azure-pipelines.yml39
-rw-r--r--vendor/github.com/bits-and-blooms/bitset/bitset.go952
-rw-r--r--vendor/github.com/bits-and-blooms/bitset/go.mod3
-rw-r--r--vendor/github.com/bits-and-blooms/bitset/go.sum0
-rw-r--r--vendor/github.com/bits-and-blooms/bitset/popcnt.go53
-rw-r--r--vendor/github.com/bits-and-blooms/bitset/popcnt_19.go45
-rw-r--r--vendor/github.com/bits-and-blooms/bitset/popcnt_amd64.go68
-rw-r--r--vendor/github.com/bits-and-blooms/bitset/popcnt_amd64.s104
-rw-r--r--vendor/github.com/bits-and-blooms/bitset/popcnt_generic.go24
-rw-r--r--vendor/github.com/bits-and-blooms/bitset/trailing_zeros_18.go14
-rw-r--r--vendor/github.com/bits-and-blooms/bitset/trailing_zeros_19.go9
15 files changed, 0 insertions, 1494 deletions
diff --git a/vendor/github.com/bits-and-blooms/bitset/.gitignore b/vendor/github.com/bits-and-blooms/bitset/.gitignore
deleted file mode 100644
index 5c204d28b..000000000
--- a/vendor/github.com/bits-and-blooms/bitset/.gitignore
+++ /dev/null
@@ -1,26 +0,0 @@
-# Compiled Object files, Static and Dynamic libs (Shared Objects)
-*.o
-*.a
-*.so
-
-# Folders
-_obj
-_test
-
-# Architecture specific extensions/prefixes
-*.[568vq]
-[568vq].out
-
-*.cgo1.go
-*.cgo2.c
-_cgo_defun.c
-_cgo_gotypes.go
-_cgo_export.*
-
-_testmain.go
-
-*.exe
-*.test
-*.prof
-
-target
diff --git a/vendor/github.com/bits-and-blooms/bitset/.travis.yml b/vendor/github.com/bits-and-blooms/bitset/.travis.yml
deleted file mode 100644
index 094aa5ce0..000000000
--- a/vendor/github.com/bits-and-blooms/bitset/.travis.yml
+++ /dev/null
@@ -1,37 +0,0 @@
-language: go
-
-sudo: false
-
-branches:
- except:
- - release
-
-branches:
- only:
- - master
- - travis
-
-go:
- - "1.11.x"
- - tip
-
-matrix:
- allow_failures:
- - go: tip
-
-before_install:
- - if [ -n "$GH_USER" ]; then git config --global github.user ${GH_USER}; fi;
- - if [ -n "$GH_TOKEN" ]; then git config --global github.token ${GH_TOKEN}; fi;
- - go get github.com/mattn/goveralls
-
-before_script:
- - make deps
-
-script:
- - make qa
-
-after_failure:
- - cat ./target/test/report.xml
-
-after_success:
- - if [ "$TRAVIS_GO_VERSION" = "1.11.1" ]; then $HOME/gopath/bin/goveralls -covermode=count -coverprofile=target/report/coverage.out -service=travis-ci; fi;
diff --git a/vendor/github.com/bits-and-blooms/bitset/LICENSE b/vendor/github.com/bits-and-blooms/bitset/LICENSE
deleted file mode 100644
index 59cab8a93..000000000
--- a/vendor/github.com/bits-and-blooms/bitset/LICENSE
+++ /dev/null
@@ -1,27 +0,0 @@
-Copyright (c) 2014 Will Fitzgerald. All rights reserved.
-
-Redistribution and use in source and binary forms, with or without
-modification, are permitted provided that the following conditions are
-met:
-
- * Redistributions of source code must retain the above copyright
-notice, this list of conditions and the following disclaimer.
- * Redistributions in binary form must reproduce the above
-copyright notice, this list of conditions and the following disclaimer
-in the documentation and/or other materials provided with the
-distribution.
- * Neither the name of Google Inc. nor the names of its
-contributors may be used to endorse or promote products derived from
-this software without specific prior written permission.
-
-THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
-"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
-LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
-A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
-OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
-SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
-LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
-DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
-THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
-(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
diff --git a/vendor/github.com/bits-and-blooms/bitset/README.md b/vendor/github.com/bits-and-blooms/bitset/README.md
deleted file mode 100644
index 97e83071e..000000000
--- a/vendor/github.com/bits-and-blooms/bitset/README.md
+++ /dev/null
@@ -1,93 +0,0 @@
-# bitset
-
-*Go language library to map between non-negative integers and boolean values*
-
-[![Test](https://github.com/bits-and-blooms/bitset/workflows/Test/badge.svg)](https://github.com/willf/bitset/actions?query=workflow%3ATest)
-[![Go Report Card](https://goreportcard.com/badge/github.com/willf/bitset)](https://goreportcard.com/report/github.com/willf/bitset)
-[![PkgGoDev](https://pkg.go.dev/badge/github.com/bits-and-blooms/bitset?tab=doc)](https://pkg.go.dev/github.com/bits-and-blooms/bitset?tab=doc)
-
-
-## Description
-
-Package bitset implements bitsets, a mapping between non-negative integers and boolean values.
-It should be more efficient than map[uint] bool.
-
-It provides methods for setting, clearing, flipping, and testing individual integers.
-
-But it also provides set intersection, union, difference, complement, and symmetric operations, as well as tests to check whether any, all, or no bits are set, and querying a bitset's current length and number of positive bits.
-
-BitSets are expanded to the size of the largest set bit; the memory allocation is approximately Max bits, where Max is the largest set bit. BitSets are never shrunk. On creation, a hint can be given for the number of bits that will be used.
-
-Many of the methods, including Set, Clear, and Flip, return a BitSet pointer, which allows for chaining.
-
-### Example use:
-
-```go
-package main
-
-import (
- "fmt"
- "math/rand"
-
- "github.com/bits-and-blooms/bitset"
-)
-
-func main() {
- fmt.Printf("Hello from BitSet!\n")
- var b bitset.BitSet
- // play some Go Fish
- for i := 0; i < 100; i++ {
- card1 := uint(rand.Intn(52))
- card2 := uint(rand.Intn(52))
- b.Set(card1)
- if b.Test(card2) {
- fmt.Println("Go Fish!")
- }
- b.Clear(card1)
- }
-
- // Chaining
- b.Set(10).Set(11)
-
- for i, e := b.NextSet(0); e; i, e = b.NextSet(i + 1) {
- fmt.Println("The following bit is set:", i)
- }
- if b.Intersection(bitset.New(100).Set(10)).Count() == 1 {
- fmt.Println("Intersection works.")
- } else {
- fmt.Println("Intersection doesn't work???")
- }
-}
-```
-
-As an alternative to BitSets, one should check out the 'big' package, which provides a (less set-theoretical) view of bitsets.
-
-Package documentation is at: https://pkg.go.dev/github.com/bits-and-blooms/bitset?tab=doc
-
-## Memory Usage
-
-The memory usage of a bitset using N bits is at least N/8 bytes. The number of bits in a bitset is at least as large as one plus the greatest bit index you have accessed. Thus it is possible to run out of memory while using a bitset. If you have lots of bits, you might prefer compressed bitsets, like the [Roaring bitmaps](http://roaringbitmap.org) and its [Go implementation](https://github.com/RoaringBitmap/roaring).
-
-## Implementation Note
-
-Go 1.9 introduced a native `math/bits` library. We provide backward compatibility to Go 1.7, which might be removed.
-
-It is possible that a later version will match the `math/bits` return signature for counts (which is `int`, rather than our library's `unit64`). If so, the version will be bumped.
-
-## Installation
-
-```bash
-go get github.com/bits-and-blooms/bitset
-```
-
-## Contributing
-
-If you wish to contribute to this project, please branch and issue a pull request against master ("[GitHub Flow](https://guides.github.com/introduction/flow/)")
-
-## Running all tests
-
-Before committing the code, please check if it passes tests, has adequate coverage, etc.
-```bash
-go test
-go test -cover
-```
diff --git a/vendor/github.com/bits-and-blooms/bitset/azure-pipelines.yml b/vendor/github.com/bits-and-blooms/bitset/azure-pipelines.yml
deleted file mode 100644
index f9b295918..000000000
--- a/vendor/github.com/bits-and-blooms/bitset/azure-pipelines.yml
+++ /dev/null
@@ -1,39 +0,0 @@
-# Go
-# Build your Go project.
-# Add steps that test, save build artifacts, deploy, and more:
-# https://docs.microsoft.com/azure/devops/pipelines/languages/go
-
-trigger:
-- master
-
-pool:
- vmImage: 'Ubuntu-16.04'
-
-variables:
- GOBIN: '$(GOPATH)/bin' # Go binaries path
- GOROOT: '/usr/local/go1.11' # Go installation path
- GOPATH: '$(system.defaultWorkingDirectory)/gopath' # Go workspace path
- modulePath: '$(GOPATH)/src/github.com/$(build.repository.name)' # Path to the module's code
-
-steps:
-- script: |
- mkdir -p '$(GOBIN)'
- mkdir -p '$(GOPATH)/pkg'
- mkdir -p '$(modulePath)'
- shopt -s extglob
- shopt -s dotglob
- mv !(gopath) '$(modulePath)'
- echo '##vso[task.prependpath]$(GOBIN)'
- echo '##vso[task.prependpath]$(GOROOT)/bin'
- displayName: 'Set up the Go workspace'
-
-- script: |
- go version
- go get -v -t -d ./...
- if [ -f Gopkg.toml ]; then
- curl https://raw.githubusercontent.com/golang/dep/master/install.sh | sh
- dep ensure
- fi
- go build -v .
- workingDirectory: '$(modulePath)'
- displayName: 'Get dependencies, then build'
diff --git a/vendor/github.com/bits-and-blooms/bitset/bitset.go b/vendor/github.com/bits-and-blooms/bitset/bitset.go
deleted file mode 100644
index d688806a5..000000000
--- a/vendor/github.com/bits-and-blooms/bitset/bitset.go
+++ /dev/null
@@ -1,952 +0,0 @@
-/*
-Package bitset implements bitsets, a mapping
-between non-negative integers and boolean values. It should be more
-efficient than map[uint] bool.
-
-It provides methods for setting, clearing, flipping, and testing
-individual integers.
-
-But it also provides set intersection, union, difference,
-complement, and symmetric operations, as well as tests to
-check whether any, all, or no bits are set, and querying a
-bitset's current length and number of positive bits.
-
-BitSets are expanded to the size of the largest set bit; the
-memory allocation is approximately Max bits, where Max is
-the largest set bit. BitSets are never shrunk. On creation,
-a hint can be given for the number of bits that will be used.
-
-Many of the methods, including Set,Clear, and Flip, return
-a BitSet pointer, which allows for chaining.
-
-Example use:
-
- import "bitset"
- var b BitSet
- b.Set(10).Set(11)
- if b.Test(1000) {
- b.Clear(1000)
- }
- if B.Intersection(bitset.New(100).Set(10)).Count() > 1 {
- fmt.Println("Intersection works.")
- }
-
-As an alternative to BitSets, one should check out the 'big' package,
-which provides a (less set-theoretical) view of bitsets.
-
-*/
-package bitset
-
-import (
- "bufio"
- "bytes"
- "encoding/base64"
- "encoding/binary"
- "encoding/json"
- "errors"
- "fmt"
- "io"
- "strconv"
-)
-
-// the wordSize of a bit set
-const wordSize = uint(64)
-
-// log2WordSize is lg(wordSize)
-const log2WordSize = uint(6)
-
-// allBits has every bit set
-const allBits uint64 = 0xffffffffffffffff
-
-// default binary BigEndian
-var binaryOrder binary.ByteOrder = binary.BigEndian
-
-// default json encoding base64.URLEncoding
-var base64Encoding = base64.URLEncoding
-
-// Base64StdEncoding Marshal/Unmarshal BitSet with base64.StdEncoding(Default: base64.URLEncoding)
-func Base64StdEncoding() { base64Encoding = base64.StdEncoding }
-
-// LittleEndian Marshal/Unmarshal Binary as Little Endian(Default: binary.BigEndian)
-func LittleEndian() { binaryOrder = binary.LittleEndian }
-
-// A BitSet is a set of bits. The zero value of a BitSet is an empty set of length 0.
-type BitSet struct {
- length uint
- set []uint64
-}
-
-// Error is used to distinguish errors (panics) generated in this package.
-type Error string
-
-// safeSet will fixup b.set to be non-nil and return the field value
-func (b *BitSet) safeSet() []uint64 {
- if b.set == nil {
- b.set = make([]uint64, wordsNeeded(0))
- }
- return b.set
-}
-
-// From is a constructor used to create a BitSet from an array of integers
-func From(buf []uint64) *BitSet {
- return &BitSet{uint(len(buf)) * 64, buf}
-}
-
-// Bytes returns the bitset as array of integers
-func (b *BitSet) Bytes() []uint64 {
- return b.set
-}
-
-// wordsNeeded calculates the number of words needed for i bits
-func wordsNeeded(i uint) int {
- if i > (Cap() - wordSize + 1) {
- return int(Cap() >> log2WordSize)
- }
- return int((i + (wordSize - 1)) >> log2WordSize)
-}
-
-// New creates a new BitSet with a hint that length bits will be required
-func New(length uint) (bset *BitSet) {
- defer func() {
- if r := recover(); r != nil {
- bset = &BitSet{
- 0,
- make([]uint64, 0),
- }
- }
- }()
-
- bset = &BitSet{
- length,
- make([]uint64, wordsNeeded(length)),
- }
-
- return bset
-}
-
-// Cap returns the total possible capacity, or number of bits
-func Cap() uint {
- return ^uint(0)
-}
-
-// Len returns the number of bits in the BitSet.
-// Note the difference to method Count, see example.
-func (b *BitSet) Len() uint {
- return b.length
-}
-
-// extendSetMaybe adds additional words to incorporate new bits if needed
-func (b *BitSet) extendSetMaybe(i uint) {
- if i >= b.length { // if we need more bits, make 'em
- if i >= Cap() {
- panic("You are exceeding the capacity")
- }
- nsize := wordsNeeded(i + 1)
- if b.set == nil {
- b.set = make([]uint64, nsize)
- } else if cap(b.set) >= nsize {
- b.set = b.set[:nsize] // fast resize
- } else if len(b.set) < nsize {
- newset := make([]uint64, nsize, 2*nsize) // increase capacity 2x
- copy(newset, b.set)
- b.set = newset
- }
- b.length = i + 1
- }
-}
-
-// Test whether bit i is set.
-func (b *BitSet) Test(i uint) bool {
- if i >= b.length {
- return false
- }
- return b.set[i>>log2WordSize]&(1<<(i&(wordSize-1))) != 0
-}
-
-// Set bit i to 1, the capacity of the bitset is automatically
-// increased accordingly.
-// If i>= Cap(), this function will panic.
-// Warning: using a very large value for 'i'
-// may lead to a memory shortage and a panic: the caller is responsible
-// for providing sensible parameters in line with their memory capacity.
-func (b *BitSet) Set(i uint) *BitSet {
- b.extendSetMaybe(i)
- b.set[i>>log2WordSize] |= 1 << (i & (wordSize - 1))
- return b
-}
-
-// Clear bit i to 0
-func (b *BitSet) Clear(i uint) *BitSet {
- if i >= b.length {
- return b
- }
- b.set[i>>log2WordSize] &^= 1 << (i & (wordSize - 1))
- return b
-}
-
-// SetTo sets bit i to value.
-// If i>= Cap(), this function will panic.
-// Warning: using a very large value for 'i'
-// may lead to a memory shortage and a panic: the caller is responsible
-// for providing sensible parameters in line with their memory capacity.
-func (b *BitSet) SetTo(i uint, value bool) *BitSet {
- if value {
- return b.Set(i)
- }
- return b.Clear(i)
-}
-
-// Flip bit at i.
-// If i>= Cap(), this function will panic.
-// Warning: using a very large value for 'i'
-// may lead to a memory shortage and a panic: the caller is responsible
-// for providing sensible parameters in line with their memory capacity.
-func (b *BitSet) Flip(i uint) *BitSet {
- if i >= b.length {
- return b.Set(i)
- }
- b.set[i>>log2WordSize] ^= 1 << (i & (wordSize - 1))
- return b
-}
-
-// FlipRange bit in [start, end).
-// If end>= Cap(), this function will panic.
-// Warning: using a very large value for 'end'
-// may lead to a memory shortage and a panic: the caller is responsible
-// for providing sensible parameters in line with their memory capacity.
-func (b *BitSet) FlipRange(start, end uint) *BitSet {
- if start >= end {
- return b
- }
-
- b.extendSetMaybe(end - 1)
- var startWord uint = start >> log2WordSize
- var endWord uint = end >> log2WordSize
- b.set[startWord] ^= ^(^uint64(0) << (start & (wordSize - 1)))
- for i := startWord; i < endWord; i++ {
- b.set[i] = ^b.set[i]
- }
- b.set[endWord] ^= ^uint64(0) >> (-end & (wordSize - 1))
- return b
-}
-
-// Shrink shrinks BitSet so that the provided value is the last possible
-// set value. It clears all bits > the provided index and reduces the size
-// and length of the set.
-//
-// Note that the parameter value is not the new length in bits: it is the
-// maximal value that can be stored in the bitset after the function call.
-// The new length in bits is the parameter value + 1. Thus it is not possible
-// to use this function to set the length to 0, the minimal value of the length
-// after this function call is 1.
-//
-// A new slice is allocated to store the new bits, so you may see an increase in
-// memory usage until the GC runs. Normally this should not be a problem, but if you
-// have an extremely large BitSet its important to understand that the old BitSet will
-// remain in memory until the GC frees it.
-func (b *BitSet) Shrink(lastbitindex uint) *BitSet {
- length := lastbitindex + 1
- idx := wordsNeeded(length)
- if idx > len(b.set) {
- return b
- }
- shrunk := make([]uint64, idx)
- copy(shrunk, b.set[:idx])
- b.set = shrunk
- b.length = length
- b.set[idx-1] &= (allBits >> (uint64(64) - uint64(length&(wordSize-1))))
- return b
-}
-
-// Compact shrinks BitSet to so that we preserve all set bits, while minimizing
-// memory usage. Compact calls Shrink.
-func (b *BitSet) Compact() *BitSet {
- idx := len(b.set) - 1
- for ; idx >= 0 && b.set[idx] == 0; idx-- {
- }
- newlength := uint((idx + 1) << log2WordSize)
- if newlength >= b.length {
- return b // nothing to do
- }
- if newlength > 0 {
- return b.Shrink(newlength - 1)
- }
- // We preserve one word
- return b.Shrink(63)
-}
-
-// InsertAt takes an index which indicates where a bit should be
-// inserted. Then it shifts all the bits in the set to the left by 1, starting
-// from the given index position, and sets the index position to 0.
-//
-// Depending on the size of your BitSet, and where you are inserting the new entry,
-// this method could be extremely slow and in some cases might cause the entire BitSet
-// to be recopied.
-func (b *BitSet) InsertAt(idx uint) *BitSet {
- insertAtElement := (idx >> log2WordSize)
-
- // if length of set is a multiple of wordSize we need to allocate more space first
- if b.isLenExactMultiple() {
- b.set = append(b.set, uint64(0))
- }
-
- var i uint
- for i = uint(len(b.set) - 1); i > insertAtElement; i-- {
- // all elements above the position where we want to insert can simply by shifted
- b.set[i] <<= 1
-
- // we take the most significant bit of the previous element and set it as
- // the least significant bit of the current element
- b.set[i] |= (b.set[i-1] & 0x8000000000000000) >> 63
- }
-
- // generate a mask to extract the data that we need to shift left
- // within the element where we insert a bit
- dataMask := ^(uint64(1)<<uint64(idx&(wordSize-1)) - 1)
-
- // extract that data that we'll shift
- data := b.set[i] & dataMask
-
- // set the positions of the data mask to 0 in the element where we insert
- b.set[i] &= ^dataMask
-
- // shift data mask to the left and insert its data to the slice element
- b.set[i] |= data << 1
-
- // add 1 to length of BitSet
- b.length++
-
- return b
-}
-
-// String creates a string representation of the Bitmap
-func (b *BitSet) String() string {
- // follows code from https://github.com/RoaringBitmap/roaring
- var buffer bytes.Buffer
- start := []byte("{")
- buffer.Write(start)
- counter := 0
- i, e := b.NextSet(0)
- for e {
- counter = counter + 1
- // to avoid exhausting the memory
- if counter > 0x40000 {
- buffer.WriteString("...")
- break
- }
- buffer.WriteString(strconv.FormatInt(int64(i), 10))
- i, e = b.NextSet(i + 1)
- if e {
- buffer.WriteString(",")
- }
- }
- buffer.WriteString("}")
- return buffer.String()
-}
-
-// DeleteAt deletes the bit at the given index position from
-// within the bitset
-// All the bits residing on the left of the deleted bit get
-// shifted right by 1
-// The running time of this operation may potentially be
-// relatively slow, O(length)
-func (b *BitSet) DeleteAt(i uint) *BitSet {
- // the index of the slice element where we'll delete a bit
- deleteAtElement := i >> log2WordSize
-
- // generate a mask for the data that needs to be shifted right
- // within that slice element that gets modified
- dataMask := ^((uint64(1) << (i & (wordSize - 1))) - 1)
-
- // extract the data that we'll shift right from the slice element
- data := b.set[deleteAtElement] & dataMask
-
- // set the masked area to 0 while leaving the rest as it is
- b.set[deleteAtElement] &= ^dataMask
-
- // shift the previously extracted data to the right and then
- // set it in the previously masked area
- b.set[deleteAtElement] |= (data >> 1) & dataMask
-
- // loop over all the consecutive slice elements to copy each
- // lowest bit into the highest position of the previous element,
- // then shift the entire content to the right by 1
- for i := int(deleteAtElement) + 1; i < len(b.set); i++ {
- b.set[i-1] |= (b.set[i] & 1) << 63
- b.set[i] >>= 1
- }
-
- b.length = b.length - 1
-
- return b
-}
-
-// NextSet returns the next bit set from the specified index,
-// including possibly the current index
-// along with an error code (true = valid, false = no set bit found)
-// for i,e := v.NextSet(0); e; i,e = v.NextSet(i + 1) {...}
-//
-// Users concerned with performance may want to use NextSetMany to
-// retrieve several values at once.
-func (b *BitSet) NextSet(i uint) (uint, bool) {
- x := int(i >> log2WordSize)
- if x >= len(b.set) {
- return 0, false
- }
- w := b.set[x]
- w = w >> (i & (wordSize - 1))
- if w != 0 {
- return i + trailingZeroes64(w), true
- }
- x = x + 1
- for x < len(b.set) {
- if b.set[x] != 0 {
- return uint(x)*wordSize + trailingZeroes64(b.set[x]), true
- }
- x = x + 1
-
- }
- return 0, false
-}
-
-// NextSetMany returns many next bit sets from the specified index,
-// including possibly the current index and up to cap(buffer).
-// If the returned slice has len zero, then no more set bits were found
-//
-// buffer := make([]uint, 256) // this should be reused
-// j := uint(0)
-// j, buffer = bitmap.NextSetMany(j, buffer)
-// for ; len(buffer) > 0; j, buffer = bitmap.NextSetMany(j,buffer) {
-// for k := range buffer {
-// do something with buffer[k]
-// }
-// j += 1
-// }
-//
-//
-// It is possible to retrieve all set bits as follow:
-//
-// indices := make([]uint, bitmap.Count())
-// bitmap.NextSetMany(0, indices)
-//
-// However if bitmap.Count() is large, it might be preferable to
-// use several calls to NextSetMany, for performance reasons.
-func (b *BitSet) NextSetMany(i uint, buffer []uint) (uint, []uint) {
- myanswer := buffer
- capacity := cap(buffer)
- x := int(i >> log2WordSize)
- if x >= len(b.set) || capacity == 0 {
- return 0, myanswer[:0]
- }
- skip := i & (wordSize - 1)
- word := b.set[x] >> skip
- myanswer = myanswer[:capacity]
- size := int(0)
- for word != 0 {
- r := trailingZeroes64(word)
- t := word & ((^word) + 1)
- myanswer[size] = r + i
- size++
- if size == capacity {
- goto End
- }
- word = word ^ t
- }
- x++
- for idx, word := range b.set[x:] {
- for word != 0 {
- r := trailingZeroes64(word)
- t := word & ((^word) + 1)
- myanswer[size] = r + (uint(x+idx) << 6)
- size++
- if size == capacity {
- goto End
- }
- word = word ^ t
- }
- }
-End:
- if size > 0 {
- return myanswer[size-1], myanswer[:size]
- }
- return 0, myanswer[:0]
-}
-
-// NextClear returns the next clear bit from the specified index,
-// including possibly the current index
-// along with an error code (true = valid, false = no bit found i.e. all bits are set)
-func (b *BitSet) NextClear(i uint) (uint, bool) {
- x := int(i >> log2WordSize)
- if x >= len(b.set) {
- return 0, false
- }
- w := b.set[x]
- w = w >> (i & (wordSize - 1))
- wA := allBits >> (i & (wordSize - 1))
- index := i + trailingZeroes64(^w)
- if w != wA && index < b.length {
- return index, true
- }
- x++
- for x < len(b.set) {
- index = uint(x)*wordSize + trailingZeroes64(^b.set[x])
- if b.set[x] != allBits && index < b.length {
- return index, true
- }
- x++
- }
- return 0, false
-}
-
-// ClearAll clears the entire BitSet
-func (b *BitSet) ClearAll() *BitSet {
- if b != nil && b.set != nil {
- for i := range b.set {
- b.set[i] = 0
- }
- }
- return b
-}
-
-// wordCount returns the number of words used in a bit set
-func (b *BitSet) wordCount() int {
- return len(b.set)
-}
-
-// Clone this BitSet
-func (b *BitSet) Clone() *BitSet {
- c := New(b.length)
- if b.set != nil { // Clone should not modify current object
- copy(c.set, b.set)
- }
- return c
-}
-
-// Copy into a destination BitSet
-// Returning the size of the destination BitSet
-// like array copy
-func (b *BitSet) Copy(c *BitSet) (count uint) {
- if c == nil {
- return
- }
- if b.set != nil { // Copy should not modify current object
- copy(c.set, b.set)
- }
- count = c.length
- if b.length < c.length {
- count = b.length
- }
- return
-}
-
-// Count (number of set bits).
-// Also known as "popcount" or "population count".
-func (b *BitSet) Count() uint {
- if b != nil && b.set != nil {
- return uint(popcntSlice(b.set))
- }
- return 0
-}
-
-// Equal tests the equivalence of two BitSets.
-// False if they are of different sizes, otherwise true
-// only if all the same bits are set
-func (b *BitSet) Equal(c *BitSet) bool {
- if c == nil || b == nil {
- return c == b
- }
- if b.length != c.length {
- return false
- }
- if b.length == 0 { // if they have both length == 0, then could have nil set
- return true
- }
- // testing for equality shoud not transform the bitset (no call to safeSet)
-
- for p, v := range b.set {
- if c.set[p] != v {
- return false
- }
- }
- return true
-}
-
-func panicIfNull(b *BitSet) {
- if b == nil {
- panic(Error("BitSet must not be null"))
- }
-}
-
-// Difference of base set and other set
-// This is the BitSet equivalent of &^ (and not)
-func (b *BitSet) Difference(compare *BitSet) (result *BitSet) {
- panicIfNull(b)
- panicIfNull(compare)
- result = b.Clone() // clone b (in case b is bigger than compare)
- l := int(compare.wordCount())
- if l > int(b.wordCount()) {
- l = int(b.wordCount())
- }
- for i := 0; i < l; i++ {
- result.set[i] = b.set[i] &^ compare.set[i]
- }
- return
-}
-
-// DifferenceCardinality computes the cardinality of the differnce
-func (b *BitSet) DifferenceCardinality(compare *BitSet) uint {
- panicIfNull(b)
- panicIfNull(compare)
- l := int(compare.wordCount())
- if l > int(b.wordCount()) {
- l = int(b.wordCount())
- }
- cnt := uint64(0)
- cnt += popcntMaskSlice(b.set[:l], compare.set[:l])
- cnt += popcntSlice(b.set[l:])
- return uint(cnt)
-}
-
-// InPlaceDifference computes the difference of base set and other set
-// This is the BitSet equivalent of &^ (and not)
-func (b *BitSet) InPlaceDifference(compare *BitSet) {
- panicIfNull(b)
- panicIfNull(compare)
- l := int(compare.wordCount())
- if l > int(b.wordCount()) {
- l = int(b.wordCount())
- }
- for i := 0; i < l; i++ {
- b.set[i] &^= compare.set[i]
- }
-}
-
-// Convenience function: return two bitsets ordered by
-// increasing length. Note: neither can be nil
-func sortByLength(a *BitSet, b *BitSet) (ap *BitSet, bp *BitSet) {
- if a.length <= b.length {
- ap, bp = a, b
- } else {
- ap, bp = b, a
- }
- return
-}
-
-// Intersection of base set and other set
-// This is the BitSet equivalent of & (and)
-func (b *BitSet) Intersection(compare *BitSet) (result *BitSet) {
- panicIfNull(b)
- panicIfNull(compare)
- b, compare = sortByLength(b, compare)
- result = New(b.length)
- for i, word := range b.set {
- result.set[i] = word & compare.set[i]
- }
- return
-}
-
-// IntersectionCardinality computes the cardinality of the union
-func (b *BitSet) IntersectionCardinality(compare *BitSet) uint {
- panicIfNull(b)
- panicIfNull(compare)
- b, compare = sortByLength(b, compare)
- cnt := popcntAndSlice(b.set, compare.set)
- return uint(cnt)
-}
-
-// InPlaceIntersection destructively computes the intersection of
-// base set and the compare set.
-// This is the BitSet equivalent of & (and)
-func (b *BitSet) InPlaceIntersection(compare *BitSet) {
- panicIfNull(b)
- panicIfNull(compare)
- l := int(compare.wordCount())
- if l > int(b.wordCount()) {
- l = int(b.wordCount())
- }
- for i := 0; i < l; i++ {
- b.set[i] &= compare.set[i]
- }
- for i := l; i < len(b.set); i++ {
- b.set[i] = 0
- }
- if compare.length > 0 {
- b.extendSetMaybe(compare.length - 1)
- }
-}
-
-// Union of base set and other set
-// This is the BitSet equivalent of | (or)
-func (b *BitSet) Union(compare *BitSet) (result *BitSet) {
- panicIfNull(b)
- panicIfNull(compare)
- b, compare = sortByLength(b, compare)
- result = compare.Clone()
- for i, word := range b.set {
- result.set[i] = word | compare.set[i]
- }
- return
-}
-
-// UnionCardinality computes the cardinality of the uniton of the base set
-// and the compare set.
-func (b *BitSet) UnionCardinality(compare *BitSet) uint {
- panicIfNull(b)
- panicIfNull(compare)
- b, compare = sortByLength(b, compare)
- cnt := popcntOrSlice(b.set, compare.set)
- if len(compare.set) > len(b.set) {
- cnt += popcntSlice(compare.set[len(b.set):])
- }
- return uint(cnt)
-}
-
-// InPlaceUnion creates the destructive union of base set and compare set.
-// This is the BitSet equivalent of | (or).
-func (b *BitSet) InPlaceUnion(compare *BitSet) {
- panicIfNull(b)
- panicIfNull(compare)
- l := int(compare.wordCount())
- if l > int(b.wordCount()) {
- l = int(b.wordCount())
- }
- if compare.length > 0 {
- b.extendSetMaybe(compare.length - 1)
- }
- for i := 0; i < l; i++ {
- b.set[i] |= compare.set[i]
- }
- if len(compare.set) > l {
- for i := l; i < len(compare.set); i++ {
- b.set[i] = compare.set[i]
- }
- }
-}
-
-// SymmetricDifference of base set and other set
-// This is the BitSet equivalent of ^ (xor)
-func (b *BitSet) SymmetricDifference(compare *BitSet) (result *BitSet) {
- panicIfNull(b)
- panicIfNull(compare)
- b, compare = sortByLength(b, compare)
- // compare is bigger, so clone it
- result = compare.Clone()
- for i, word := range b.set {
- result.set[i] = word ^ compare.set[i]
- }
- return
-}
-
-// SymmetricDifferenceCardinality computes the cardinality of the symmetric difference
-func (b *BitSet) SymmetricDifferenceCardinality(compare *BitSet) uint {
- panicIfNull(b)
- panicIfNull(compare)
- b, compare = sortByLength(b, compare)
- cnt := popcntXorSlice(b.set, compare.set)
- if len(compare.set) > len(b.set) {
- cnt += popcntSlice(compare.set[len(b.set):])
- }
- return uint(cnt)
-}
-
-// InPlaceSymmetricDifference creates the destructive SymmetricDifference of base set and other set
-// This is the BitSet equivalent of ^ (xor)
-func (b *BitSet) InPlaceSymmetricDifference(compare *BitSet) {
- panicIfNull(b)
- panicIfNull(compare)
- l := int(compare.wordCount())
- if l > int(b.wordCount()) {
- l = int(b.wordCount())
- }
- if compare.length > 0 {
- b.extendSetMaybe(compare.length - 1)
- }
- for i := 0; i < l; i++ {
- b.set[i] ^= compare.set[i]
- }
- if len(compare.set) > l {
- for i := l; i < len(compare.set); i++ {
- b.set[i] = compare.set[i]
- }
- }
-}
-
-// Is the length an exact multiple of word sizes?
-func (b *BitSet) isLenExactMultiple() bool {
- return b.length%wordSize == 0
-}
-
-// Clean last word by setting unused bits to 0
-func (b *BitSet) cleanLastWord() {
- if !b.isLenExactMultiple() {
- b.set[len(b.set)-1] &= allBits >> (wordSize - b.length%wordSize)
- }
-}
-
-// Complement computes the (local) complement of a biset (up to length bits)
-func (b *BitSet) Complement() (result *BitSet) {
- panicIfNull(b)
- result = New(b.length)
- for i, word := range b.set {
- result.set[i] = ^word
- }
- result.cleanLastWord()
- return
-}
-
-// All returns true if all bits are set, false otherwise. Returns true for
-// empty sets.
-func (b *BitSet) All() bool {
- panicIfNull(b)
- return b.Count() == b.length
-}
-
-// None returns true if no bit is set, false otherwise. Returns true for
-// empty sets.
-func (b *BitSet) None() bool {
- panicIfNull(b)
- if b != nil && b.set != nil {
- for _, word := range b.set {
- if word > 0 {
- return false
- }
- }
- return true
- }
- return true
-}
-
-// Any returns true if any bit is set, false otherwise
-func (b *BitSet) Any() bool {
- panicIfNull(b)
- return !b.None()
-}
-
-// IsSuperSet returns true if this is a superset of the other set
-func (b *BitSet) IsSuperSet(other *BitSet) bool {
- for i, e := other.NextSet(0); e; i, e = other.NextSet(i + 1) {
- if !b.Test(i) {
- return false
- }
- }
- return true
-}
-
-// IsStrictSuperSet returns true if this is a strict superset of the other set
-func (b *BitSet) IsStrictSuperSet(other *BitSet) bool {
- return b.Count() > other.Count() && b.IsSuperSet(other)
-}
-
-// DumpAsBits dumps a bit set as a string of bits
-func (b *BitSet) DumpAsBits() string {
- if b.set == nil {
- return "."
- }
- buffer := bytes.NewBufferString("")
- i := len(b.set) - 1
- for ; i >= 0; i-- {
- fmt.Fprintf(buffer, "%064b.", b.set[i])
- }
- return buffer.String()
-}
-
-// BinaryStorageSize returns the binary storage requirements
-func (b *BitSet) BinaryStorageSize() int {
- return binary.Size(uint64(0)) + binary.Size(b.set)
-}
-
-// WriteTo writes a BitSet to a stream
-func (b *BitSet) WriteTo(stream io.Writer) (int64, error) {
- length := uint64(b.length)
-
- // Write length
- err := binary.Write(stream, binaryOrder, length)
- if err != nil {
- return 0, err
- }
-
- // Write set
- err = binary.Write(stream, binaryOrder, b.set)
- return int64(b.BinaryStorageSize()), err
-}
-
-// ReadFrom reads a BitSet from a stream written using WriteTo
-func (b *BitSet) ReadFrom(stream io.Reader) (int64, error) {
- var length uint64
-
- // Read length first
- err := binary.Read(stream, binaryOrder, &length)
- if err != nil {
- return 0, err
- }
- newset := New(uint(length))
-
- if uint64(newset.length) != length {
- return 0, errors.New("unmarshalling error: type mismatch")
- }
-
- // Read remaining bytes as set
- err = binary.Read(stream, binaryOrder, newset.set)
- if err != nil {
- return 0, err
- }
-
- *b = *newset
- return int64(b.BinaryStorageSize()), nil
-}
-
-// MarshalBinary encodes a BitSet into a binary form and returns the result.
-func (b *BitSet) MarshalBinary() ([]byte, error) {
- var buf bytes.Buffer
- writer := bufio.NewWriter(&buf)
-
- _, err := b.WriteTo(writer)
- if err != nil {
- return []byte{}, err
- }
-
- err = writer.Flush()
-
- return buf.Bytes(), err
-}
-
-// UnmarshalBinary decodes the binary form generated by MarshalBinary.
-func (b *BitSet) UnmarshalBinary(data []byte) error {
- buf := bytes.NewReader(data)
- reader := bufio.NewReader(buf)
-
- _, err := b.ReadFrom(reader)
-
- return err
-}
-
-// MarshalJSON marshals a BitSet as a JSON structure
-func (b *BitSet) MarshalJSON() ([]byte, error) {
- buffer := bytes.NewBuffer(make([]byte, 0, b.BinaryStorageSize()))
- _, err := b.WriteTo(buffer)
- if err != nil {
- return nil, err
- }
-
- // URLEncode all bytes
- return json.Marshal(base64Encoding.EncodeToString(buffer.Bytes()))
-}
-
-// UnmarshalJSON unmarshals a BitSet from JSON created using MarshalJSON
-func (b *BitSet) UnmarshalJSON(data []byte) error {
- // Unmarshal as string
- var s string
- err := json.Unmarshal(data, &s)
- if err != nil {
- return err
- }
-
- // URLDecode string
- buf, err := base64Encoding.DecodeString(s)
- if err != nil {
- return err
- }
-
- _, err = b.ReadFrom(bytes.NewReader(buf))
- return err
-}
diff --git a/vendor/github.com/bits-and-blooms/bitset/go.mod b/vendor/github.com/bits-and-blooms/bitset/go.mod
deleted file mode 100644
index c43e4522b..000000000
--- a/vendor/github.com/bits-and-blooms/bitset/go.mod
+++ /dev/null
@@ -1,3 +0,0 @@
-module github.com/bits-and-blooms/bitset
-
-go 1.14
diff --git a/vendor/github.com/bits-and-blooms/bitset/go.sum b/vendor/github.com/bits-and-blooms/bitset/go.sum
deleted file mode 100644
index e69de29bb..000000000
--- a/vendor/github.com/bits-and-blooms/bitset/go.sum
+++ /dev/null
diff --git a/vendor/github.com/bits-and-blooms/bitset/popcnt.go b/vendor/github.com/bits-and-blooms/bitset/popcnt.go
deleted file mode 100644
index 76577a838..000000000
--- a/vendor/github.com/bits-and-blooms/bitset/popcnt.go
+++ /dev/null
@@ -1,53 +0,0 @@
-package bitset
-
-// bit population count, take from
-// https://code.google.com/p/go/issues/detail?id=4988#c11
-// credit: https://code.google.com/u/arnehormann/
-func popcount(x uint64) (n uint64) {
- x -= (x >> 1) & 0x5555555555555555
- x = (x>>2)&0x3333333333333333 + x&0x3333333333333333
- x += x >> 4
- x &= 0x0f0f0f0f0f0f0f0f
- x *= 0x0101010101010101
- return x >> 56
-}
-
-func popcntSliceGo(s []uint64) uint64 {
- cnt := uint64(0)
- for _, x := range s {
- cnt += popcount(x)
- }
- return cnt
-}
-
-func popcntMaskSliceGo(s, m []uint64) uint64 {
- cnt := uint64(0)
- for i := range s {
- cnt += popcount(s[i] &^ m[i])
- }
- return cnt
-}
-
-func popcntAndSliceGo(s, m []uint64) uint64 {
- cnt := uint64(0)
- for i := range s {
- cnt += popcount(s[i] & m[i])
- }
- return cnt
-}
-
-func popcntOrSliceGo(s, m []uint64) uint64 {
- cnt := uint64(0)
- for i := range s {
- cnt += popcount(s[i] | m[i])
- }
- return cnt
-}
-
-func popcntXorSliceGo(s, m []uint64) uint64 {
- cnt := uint64(0)
- for i := range s {
- cnt += popcount(s[i] ^ m[i])
- }
- return cnt
-}
diff --git a/vendor/github.com/bits-and-blooms/bitset/popcnt_19.go b/vendor/github.com/bits-and-blooms/bitset/popcnt_19.go
deleted file mode 100644
index fc8ff4f36..000000000
--- a/vendor/github.com/bits-and-blooms/bitset/popcnt_19.go
+++ /dev/null
@@ -1,45 +0,0 @@
-// +build go1.9
-
-package bitset
-
-import "math/bits"
-
-func popcntSlice(s []uint64) uint64 {
- var cnt int
- for _, x := range s {
- cnt += bits.OnesCount64(x)
- }
- return uint64(cnt)
-}
-
-func popcntMaskSlice(s, m []uint64) uint64 {
- var cnt int
- for i := range s {
- cnt += bits.OnesCount64(s[i] &^ m[i])
- }
- return uint64(cnt)
-}
-
-func popcntAndSlice(s, m []uint64) uint64 {
- var cnt int
- for i := range s {
- cnt += bits.OnesCount64(s[i] & m[i])
- }
- return uint64(cnt)
-}
-
-func popcntOrSlice(s, m []uint64) uint64 {
- var cnt int
- for i := range s {
- cnt += bits.OnesCount64(s[i] | m[i])
- }
- return uint64(cnt)
-}
-
-func popcntXorSlice(s, m []uint64) uint64 {
- var cnt int
- for i := range s {
- cnt += bits.OnesCount64(s[i] ^ m[i])
- }
- return uint64(cnt)
-}
diff --git a/vendor/github.com/bits-and-blooms/bitset/popcnt_amd64.go b/vendor/github.com/bits-and-blooms/bitset/popcnt_amd64.go
deleted file mode 100644
index 4cf64f24a..000000000
--- a/vendor/github.com/bits-and-blooms/bitset/popcnt_amd64.go
+++ /dev/null
@@ -1,68 +0,0 @@
-// +build !go1.9
-// +build amd64,!appengine
-
-package bitset
-
-// *** the following functions are defined in popcnt_amd64.s
-
-//go:noescape
-
-func hasAsm() bool
-
-// useAsm is a flag used to select the GO or ASM implementation of the popcnt function
-var useAsm = hasAsm()
-
-//go:noescape
-
-func popcntSliceAsm(s []uint64) uint64
-
-//go:noescape
-
-func popcntMaskSliceAsm(s, m []uint64) uint64
-
-//go:noescape
-
-func popcntAndSliceAsm(s, m []uint64) uint64
-
-//go:noescape
-
-func popcntOrSliceAsm(s, m []uint64) uint64
-
-//go:noescape
-
-func popcntXorSliceAsm(s, m []uint64) uint64
-
-func popcntSlice(s []uint64) uint64 {
- if useAsm {
- return popcntSliceAsm(s)
- }
- return popcntSliceGo(s)
-}
-
-func popcntMaskSlice(s, m []uint64) uint64 {
- if useAsm {
- return popcntMaskSliceAsm(s, m)
- }
- return popcntMaskSliceGo(s, m)
-}
-
-func popcntAndSlice(s, m []uint64) uint64 {
- if useAsm {
- return popcntAndSliceAsm(s, m)
- }
- return popcntAndSliceGo(s, m)
-}
-
-func popcntOrSlice(s, m []uint64) uint64 {
- if useAsm {
- return popcntOrSliceAsm(s, m)
- }
- return popcntOrSliceGo(s, m)
-}
-
-func popcntXorSlice(s, m []uint64) uint64 {
- if useAsm {
- return popcntXorSliceAsm(s, m)
- }
- return popcntXorSliceGo(s, m)
-}
diff --git a/vendor/github.com/bits-and-blooms/bitset/popcnt_amd64.s b/vendor/github.com/bits-and-blooms/bitset/popcnt_amd64.s
deleted file mode 100644
index 666c0dcc1..000000000
--- a/vendor/github.com/bits-and-blooms/bitset/popcnt_amd64.s
+++ /dev/null
@@ -1,104 +0,0 @@
-// +build !go1.9
-// +build amd64,!appengine
-
-TEXT ·hasAsm(SB),4,$0-1
-MOVQ $1, AX
-CPUID
-SHRQ $23, CX
-ANDQ $1, CX
-MOVB CX, ret+0(FP)
-RET
-
-#define POPCNTQ_DX_DX BYTE $0xf3; BYTE $0x48; BYTE $0x0f; BYTE $0xb8; BYTE $0xd2
-
-TEXT ·popcntSliceAsm(SB),4,$0-32
-XORQ AX, AX
-MOVQ s+0(FP), SI
-MOVQ s_len+8(FP), CX
-TESTQ CX, CX
-JZ popcntSliceEnd
-popcntSliceLoop:
-BYTE $0xf3; BYTE $0x48; BYTE $0x0f; BYTE $0xb8; BYTE $0x16 // POPCNTQ (SI), DX
-ADDQ DX, AX
-ADDQ $8, SI
-LOOP popcntSliceLoop
-popcntSliceEnd:
-MOVQ AX, ret+24(FP)
-RET
-
-TEXT ·popcntMaskSliceAsm(SB),4,$0-56
-XORQ AX, AX
-MOVQ s+0(FP), SI
-MOVQ s_len+8(FP), CX
-TESTQ CX, CX
-JZ popcntMaskSliceEnd
-MOVQ m+24(FP), DI
-popcntMaskSliceLoop:
-MOVQ (DI), DX
-NOTQ DX
-ANDQ (SI), DX
-POPCNTQ_DX_DX
-ADDQ DX, AX
-ADDQ $8, SI
-ADDQ $8, DI
-LOOP popcntMaskSliceLoop
-popcntMaskSliceEnd:
-MOVQ AX, ret+48(FP)
-RET
-
-TEXT ·popcntAndSliceAsm(SB),4,$0-56
-XORQ AX, AX
-MOVQ s+0(FP), SI
-MOVQ s_len+8(FP), CX
-TESTQ CX, CX
-JZ popcntAndSliceEnd
-MOVQ m+24(FP), DI
-popcntAndSliceLoop:
-MOVQ (DI), DX
-ANDQ (SI), DX
-POPCNTQ_DX_DX
-ADDQ DX, AX
-ADDQ $8, SI
-ADDQ $8, DI
-LOOP popcntAndSliceLoop
-popcntAndSliceEnd:
-MOVQ AX, ret+48(FP)
-RET
-
-TEXT ·popcntOrSliceAsm(SB),4,$0-56
-XORQ AX, AX
-MOVQ s+0(FP), SI
-MOVQ s_len+8(FP), CX
-TESTQ CX, CX
-JZ popcntOrSliceEnd
-MOVQ m+24(FP), DI
-popcntOrSliceLoop:
-MOVQ (DI), DX
-ORQ (SI), DX
-POPCNTQ_DX_DX
-ADDQ DX, AX
-ADDQ $8, SI
-ADDQ $8, DI
-LOOP popcntOrSliceLoop
-popcntOrSliceEnd:
-MOVQ AX, ret+48(FP)
-RET
-
-TEXT ·popcntXorSliceAsm(SB),4,$0-56
-XORQ AX, AX
-MOVQ s+0(FP), SI
-MOVQ s_len+8(FP), CX
-TESTQ CX, CX
-JZ popcntXorSliceEnd
-MOVQ m+24(FP), DI
-popcntXorSliceLoop:
-MOVQ (DI), DX
-XORQ (SI), DX
-POPCNTQ_DX_DX
-ADDQ DX, AX
-ADDQ $8, SI
-ADDQ $8, DI
-LOOP popcntXorSliceLoop
-popcntXorSliceEnd:
-MOVQ AX, ret+48(FP)
-RET
diff --git a/vendor/github.com/bits-and-blooms/bitset/popcnt_generic.go b/vendor/github.com/bits-and-blooms/bitset/popcnt_generic.go
deleted file mode 100644
index 21e0ff7b4..000000000
--- a/vendor/github.com/bits-and-blooms/bitset/popcnt_generic.go
+++ /dev/null
@@ -1,24 +0,0 @@
-// +build !go1.9
-// +build !amd64 appengine
-
-package bitset
-
-func popcntSlice(s []uint64) uint64 {
- return popcntSliceGo(s)
-}
-
-func popcntMaskSlice(s, m []uint64) uint64 {
- return popcntMaskSliceGo(s, m)
-}
-
-func popcntAndSlice(s, m []uint64) uint64 {
- return popcntAndSliceGo(s, m)
-}
-
-func popcntOrSlice(s, m []uint64) uint64 {
- return popcntOrSliceGo(s, m)
-}
-
-func popcntXorSlice(s, m []uint64) uint64 {
- return popcntXorSliceGo(s, m)
-}
diff --git a/vendor/github.com/bits-and-blooms/bitset/trailing_zeros_18.go b/vendor/github.com/bits-and-blooms/bitset/trailing_zeros_18.go
deleted file mode 100644
index c52b61be9..000000000
--- a/vendor/github.com/bits-and-blooms/bitset/trailing_zeros_18.go
+++ /dev/null
@@ -1,14 +0,0 @@
-// +build !go1.9
-
-package bitset
-
-var deBruijn = [...]byte{
- 0, 1, 56, 2, 57, 49, 28, 3, 61, 58, 42, 50, 38, 29, 17, 4,
- 62, 47, 59, 36, 45, 43, 51, 22, 53, 39, 33, 30, 24, 18, 12, 5,
- 63, 55, 48, 27, 60, 41, 37, 16, 46, 35, 44, 21, 52, 32, 23, 11,
- 54, 26, 40, 15, 34, 20, 31, 10, 25, 14, 19, 9, 13, 8, 7, 6,
-}
-
-func trailingZeroes64(v uint64) uint {
- return uint(deBruijn[((v&-v)*0x03f79d71b4ca8b09)>>58])
-}
diff --git a/vendor/github.com/bits-and-blooms/bitset/trailing_zeros_19.go b/vendor/github.com/bits-and-blooms/bitset/trailing_zeros_19.go
deleted file mode 100644
index 36a988e71..000000000
--- a/vendor/github.com/bits-and-blooms/bitset/trailing_zeros_19.go
+++ /dev/null
@@ -1,9 +0,0 @@
-// +build go1.9
-
-package bitset
-
-import "math/bits"
-
-func trailingZeroes64(v uint64) uint {
- return uint(bits.TrailingZeros64(v))
-}