summaryrefslogtreecommitdiff
path: root/vendor/github.com/willf/bitset
diff options
context:
space:
mode:
Diffstat (limited to 'vendor/github.com/willf/bitset')
-rw-r--r--vendor/github.com/willf/bitset/.gitignore26
-rw-r--r--vendor/github.com/willf/bitset/.travis.yml37
-rw-r--r--vendor/github.com/willf/bitset/LICENSE27
-rw-r--r--vendor/github.com/willf/bitset/Makefile191
-rw-r--r--vendor/github.com/willf/bitset/README.md96
-rw-r--r--vendor/github.com/willf/bitset/azure-pipelines.yml39
-rw-r--r--vendor/github.com/willf/bitset/bitset.go879
-rw-r--r--vendor/github.com/willf/bitset/popcnt.go53
-rw-r--r--vendor/github.com/willf/bitset/popcnt_19.go45
-rw-r--r--vendor/github.com/willf/bitset/popcnt_amd64.go68
-rw-r--r--vendor/github.com/willf/bitset/popcnt_amd64.s104
-rw-r--r--vendor/github.com/willf/bitset/popcnt_generic.go24
-rw-r--r--vendor/github.com/willf/bitset/trailing_zeros_18.go14
-rw-r--r--vendor/github.com/willf/bitset/trailing_zeros_19.go9
14 files changed, 1612 insertions, 0 deletions
diff --git a/vendor/github.com/willf/bitset/.gitignore b/vendor/github.com/willf/bitset/.gitignore
new file mode 100644
index 000000000..5c204d28b
--- /dev/null
+++ b/vendor/github.com/willf/bitset/.gitignore
@@ -0,0 +1,26 @@
+# 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/willf/bitset/.travis.yml b/vendor/github.com/willf/bitset/.travis.yml
new file mode 100644
index 000000000..094aa5ce0
--- /dev/null
+++ b/vendor/github.com/willf/bitset/.travis.yml
@@ -0,0 +1,37 @@
+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/willf/bitset/LICENSE b/vendor/github.com/willf/bitset/LICENSE
new file mode 100644
index 000000000..59cab8a93
--- /dev/null
+++ b/vendor/github.com/willf/bitset/LICENSE
@@ -0,0 +1,27 @@
+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/willf/bitset/Makefile b/vendor/github.com/willf/bitset/Makefile
new file mode 100644
index 000000000..db8377106
--- /dev/null
+++ b/vendor/github.com/willf/bitset/Makefile
@@ -0,0 +1,191 @@
+# MAKEFILE
+#
+# @author Nicola Asuni <info@tecnick.com>
+# @link https://github.com/willf/bitset
+# ------------------------------------------------------------------------------
+
+# List special make targets that are not associated with files
+.PHONY: help all test format fmtcheck vet lint coverage cyclo ineffassign misspell structcheck varcheck errcheck gosimple astscan qa deps clean nuke
+
+# Use bash as shell (Note: Ubuntu now uses dash which doesn't support PIPESTATUS).
+SHELL=/bin/bash
+
+# CVS path (path to the parent dir containing the project)
+CVSPATH=github.com/willf
+
+# Project owner
+OWNER=willf
+
+# Project vendor
+VENDOR=willf
+
+# Project name
+PROJECT=bitset
+
+# Project version
+VERSION=$(shell cat VERSION)
+
+# Name of RPM or DEB package
+PKGNAME=${VENDOR}-${PROJECT}
+
+# Current directory
+CURRENTDIR=$(shell pwd)
+
+# GO lang path
+ifneq ($(GOPATH),)
+ ifeq ($(findstring $(GOPATH),$(CURRENTDIR)),)
+ # the defined GOPATH is not valid
+ GOPATH=
+ endif
+endif
+ifeq ($(GOPATH),)
+ # extract the GOPATH
+ GOPATH=$(firstword $(subst /src/, ,$(CURRENTDIR)))
+endif
+
+# --- MAKE TARGETS ---
+
+# Display general help about this command
+help:
+ @echo ""
+ @echo "$(PROJECT) Makefile."
+ @echo "GOPATH=$(GOPATH)"
+ @echo "The following commands are available:"
+ @echo ""
+ @echo " make qa : Run all the tests"
+ @echo " make test : Run the unit tests"
+ @echo ""
+ @echo " make format : Format the source code"
+ @echo " make fmtcheck : Check if the source code has been formatted"
+ @echo " make vet : Check for suspicious constructs"
+ @echo " make lint : Check for style errors"
+ @echo " make coverage : Generate the coverage report"
+ @echo " make cyclo : Generate the cyclomatic complexity report"
+ @echo " make ineffassign : Detect ineffectual assignments"
+ @echo " make misspell : Detect commonly misspelled words in source files"
+ @echo " make structcheck : Find unused struct fields"
+ @echo " make varcheck : Find unused global variables and constants"
+ @echo " make errcheck : Check that error return values are used"
+ @echo " make gosimple : Suggest code simplifications"
+ @echo " make astscan : GO AST scanner"
+ @echo ""
+ @echo " make docs : Generate source code documentation"
+ @echo ""
+ @echo " make deps : Get the dependencies"
+ @echo " make clean : Remove any build artifact"
+ @echo " make nuke : Deletes any intermediate file"
+ @echo ""
+
+# Alias for help target
+all: help
+
+# Run the unit tests
+test:
+ @mkdir -p target/test
+ @mkdir -p target/report
+ GOPATH=$(GOPATH) \
+ go test \
+ -covermode=atomic \
+ -bench=. \
+ -race \
+ -cpuprofile=target/report/cpu.out \
+ -memprofile=target/report/mem.out \
+ -mutexprofile=target/report/mutex.out \
+ -coverprofile=target/report/coverage.out \
+ -v ./... | \
+ tee >(PATH=$(GOPATH)/bin:$(PATH) go-junit-report > target/test/report.xml); \
+ test $${PIPESTATUS[0]} -eq 0
+
+# Format the source code
+format:
+ @find . -type f -name "*.go" -exec gofmt -s -w {} \;
+
+# Check if the source code has been formatted
+fmtcheck:
+ @mkdir -p target
+ @find . -type f -name "*.go" -exec gofmt -s -d {} \; | tee target/format.diff
+ @test ! -s target/format.diff || { echo "ERROR: the source code has not been formatted - please use 'make format' or 'gofmt'"; exit 1; }
+
+# Check for syntax errors
+vet:
+ GOPATH=$(GOPATH) go vet .
+
+# Check for style errors
+lint:
+ GOPATH=$(GOPATH) PATH=$(GOPATH)/bin:$(PATH) golint .
+
+# Generate the coverage report
+coverage:
+ @mkdir -p target/report
+ GOPATH=$(GOPATH) \
+ go tool cover -html=target/report/coverage.out -o target/report/coverage.html
+
+# Report cyclomatic complexity
+cyclo:
+ @mkdir -p target/report
+ GOPATH=$(GOPATH) gocyclo -avg ./ | tee target/report/cyclo.txt ; test $${PIPESTATUS[0]} -eq 0
+
+# Detect ineffectual assignments
+ineffassign:
+ @mkdir -p target/report
+ GOPATH=$(GOPATH) ineffassign ./ | tee target/report/ineffassign.txt ; test $${PIPESTATUS[0]} -eq 0
+
+# Detect commonly misspelled words in source files
+misspell:
+ @mkdir -p target/report
+ GOPATH=$(GOPATH) misspell -error ./ | tee target/report/misspell.txt ; test $${PIPESTATUS[0]} -eq 0
+
+# Find unused struct fields
+structcheck:
+ @mkdir -p target/report
+ GOPATH=$(GOPATH) structcheck -a ./ | tee target/report/structcheck.txt
+
+# Find unused global variables and constants
+varcheck:
+ @mkdir -p target/report
+ GOPATH=$(GOPATH) varcheck -e ./ | tee target/report/varcheck.txt
+
+# Check that error return values are used
+errcheck:
+ @mkdir -p target/report
+ GOPATH=$(GOPATH) errcheck ./ | tee target/report/errcheck.txt
+
+# AST scanner
+astscan:
+ @mkdir -p target/report
+ GOPATH=$(GOPATH) gosec . | tee target/report/astscan.txt ; test $${PIPESTATUS[0]} -eq 0 || true
+
+# Generate source docs
+docs:
+ @mkdir -p target/docs
+ nohup sh -c 'GOPATH=$(GOPATH) godoc -http=127.0.0.1:6060' > target/godoc_server.log 2>&1 &
+ wget --directory-prefix=target/docs/ --execute robots=off --retry-connrefused --recursive --no-parent --adjust-extension --page-requisites --convert-links http://127.0.0.1:6060/pkg/github.com/${VENDOR}/${PROJECT}/ ; kill -9 `lsof -ti :6060`
+ @echo '<html><head><meta http-equiv="refresh" content="0;./127.0.0.1:6060/pkg/'${CVSPATH}'/'${PROJECT}'/index.html"/></head><a href="./127.0.0.1:6060/pkg/'${CVSPATH}'/'${PROJECT}'/index.html">'${PKGNAME}' Documentation ...</a></html>' > target/docs/index.html
+
+# Alias to run all quality-assurance checks
+qa: fmtcheck test vet lint coverage cyclo ineffassign misspell structcheck varcheck errcheck gosimple astscan
+
+# --- INSTALL ---
+
+# Get the dependencies
+deps:
+ GOPATH=$(GOPATH) go get ./...
+ GOPATH=$(GOPATH) go get golang.org/x/lint/golint
+ GOPATH=$(GOPATH) go get github.com/jstemmer/go-junit-report
+ GOPATH=$(GOPATH) go get github.com/axw/gocov/gocov
+ GOPATH=$(GOPATH) go get github.com/fzipp/gocyclo
+ GOPATH=$(GOPATH) go get github.com/gordonklaus/ineffassign
+ GOPATH=$(GOPATH) go get github.com/client9/misspell/cmd/misspell
+ GOPATH=$(GOPATH) go get github.com/opennota/check/cmd/structcheck
+ GOPATH=$(GOPATH) go get github.com/opennota/check/cmd/varcheck
+ GOPATH=$(GOPATH) go get github.com/kisielk/errcheck
+ GOPATH=$(GOPATH) go get github.com/securego/gosec/cmd/gosec/...
+
+# Remove any build artifact
+clean:
+ GOPATH=$(GOPATH) go clean ./...
+
+# Deletes any intermediate file
+nuke:
+ rm -rf ./target
+ GOPATH=$(GOPATH) go clean -i ./...
diff --git a/vendor/github.com/willf/bitset/README.md b/vendor/github.com/willf/bitset/README.md
new file mode 100644
index 000000000..6c62b20c6
--- /dev/null
+++ b/vendor/github.com/willf/bitset/README.md
@@ -0,0 +1,96 @@
+# bitset
+
+*Go language library to map between non-negative integers and boolean values*
+
+[![Master Build Status](https://secure.travis-ci.org/willf/bitset.png?branch=master)](https://travis-ci.org/willf/bitset?branch=master)
+[![Master Coverage Status](https://coveralls.io/repos/willf/bitset/badge.svg?branch=master&service=github)](https://coveralls.io/github/willf/bitset?branch=master)
+[![Go Report Card](https://goreportcard.com/badge/github.com/willf/bitset)](https://goreportcard.com/report/github.com/willf/bitset)
+[![GoDoc](https://godoc.org/github.com/willf/bitset?status.svg)](http://godoc.org/github.com/willf/bitset)
+
+
+## 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/willf/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.
+
+Godoc documentation is at: https://godoc.org/github.com/willf/bitset
+
+
+## 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/willf/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/)")
+
+This project include a Makefile that allows you to test and build the project with simple commands.
+To see all available options:
+```bash
+make help
+```
+
+## Running all tests
+
+Before committing the code, please check if it passes all tests using (note: this will install some dependencies):
+```bash
+make qa
+```
diff --git a/vendor/github.com/willf/bitset/azure-pipelines.yml b/vendor/github.com/willf/bitset/azure-pipelines.yml
new file mode 100644
index 000000000..f9b295918
--- /dev/null
+++ b/vendor/github.com/willf/bitset/azure-pipelines.yml
@@ -0,0 +1,39 @@
+# 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/willf/bitset/bitset.go b/vendor/github.com/willf/bitset/bitset.go
new file mode 100644
index 000000000..22e5d42e5
--- /dev/null
+++ b/vendor/github.com/willf/bitset/bitset.go
@@ -0,0 +1,879 @@
+/*
+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
+ 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
+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
+func (b *BitSet) SetTo(i uint, value bool) *BitSet {
+ if value {
+ return b.Set(i)
+ }
+ return b.Clear(i)
+}
+
+// Flip bit at i
+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
+}
+
+// Shrink shrinks BitSet to desired length in bits. It clears all bits > length
+// and reduces the size and length of the set.
+//
+// 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(length uint) *BitSet {
+ idx := wordsNeeded(length + 1)
+ if idx > len(b.set) {
+ return b
+ }
+ shrunk := make([]uint64, idx)
+ copy(shrunk, b.set[:idx])
+ b.set = shrunk
+ b.length = length + 1
+ b.set[idx-1] &= (allBits >> (uint64(64) - uint64(length&(wordSize-1)) - 1))
+ return b
+}
+
+// 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) {...}
+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
+// }
+//
+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 "popularity 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/willf/bitset/popcnt.go b/vendor/github.com/willf/bitset/popcnt.go
new file mode 100644
index 000000000..76577a838
--- /dev/null
+++ b/vendor/github.com/willf/bitset/popcnt.go
@@ -0,0 +1,53 @@
+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/willf/bitset/popcnt_19.go b/vendor/github.com/willf/bitset/popcnt_19.go
new file mode 100644
index 000000000..fc8ff4f36
--- /dev/null
+++ b/vendor/github.com/willf/bitset/popcnt_19.go
@@ -0,0 +1,45 @@
+// +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/willf/bitset/popcnt_amd64.go b/vendor/github.com/willf/bitset/popcnt_amd64.go
new file mode 100644
index 000000000..4cf64f24a
--- /dev/null
+++ b/vendor/github.com/willf/bitset/popcnt_amd64.go
@@ -0,0 +1,68 @@
+// +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/willf/bitset/popcnt_amd64.s b/vendor/github.com/willf/bitset/popcnt_amd64.s
new file mode 100644
index 000000000..666c0dcc1
--- /dev/null
+++ b/vendor/github.com/willf/bitset/popcnt_amd64.s
@@ -0,0 +1,104 @@
+// +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/willf/bitset/popcnt_generic.go b/vendor/github.com/willf/bitset/popcnt_generic.go
new file mode 100644
index 000000000..21e0ff7b4
--- /dev/null
+++ b/vendor/github.com/willf/bitset/popcnt_generic.go
@@ -0,0 +1,24 @@
+// +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/willf/bitset/trailing_zeros_18.go b/vendor/github.com/willf/bitset/trailing_zeros_18.go
new file mode 100644
index 000000000..c52b61be9
--- /dev/null
+++ b/vendor/github.com/willf/bitset/trailing_zeros_18.go
@@ -0,0 +1,14 @@
+// +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/willf/bitset/trailing_zeros_19.go b/vendor/github.com/willf/bitset/trailing_zeros_19.go
new file mode 100644
index 000000000..36a988e71
--- /dev/null
+++ b/vendor/github.com/willf/bitset/trailing_zeros_19.go
@@ -0,0 +1,9 @@
+// +build go1.9
+
+package bitset
+
+import "math/bits"
+
+func trailingZeroes64(v uint64) uint {
+ return uint(bits.TrailingZeros64(v))
+}