diff -Nru golang-github-willf-bitset-1.1.3/azure-pipelines.yml golang-github-willf-bitset-1.1.11/azure-pipelines.yml --- golang-github-willf-bitset-1.1.3/azure-pipelines.yml 1970-01-01 00:00:00.000000000 +0000 +++ golang-github-willf-bitset-1.1.11/azure-pipelines.yml 2020-07-30 13:51:44.000000000 +0000 @@ -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 -Nru golang-github-willf-bitset-1.1.3/bitset_benchmark_test.go golang-github-willf-bitset-1.1.11/bitset_benchmark_test.go --- golang-github-willf-bitset-1.1.3/bitset_benchmark_test.go 2017-08-29 22:58:51.000000000 +0000 +++ golang-github-willf-bitset-1.1.11/bitset_benchmark_test.go 2020-07-30 13:51:44.000000000 +0000 @@ -102,10 +102,11 @@ // go test -bench=LemireCount // see http://lemire.me/blog/2016/09/22/swift-versus-java-the-bitset-performance-test/ func BenchmarkLemireCount(b *testing.B) { - bitmap := New(100000000) // we force dynamic memory allocation + bitmap := New(100000000) for v := uint(0); v <= 100000000; v += 100 { bitmap.Set(v) } + b.ResetTimer() sum := uint(0) for i := 0; i < b.N; i++ { sum += bitmap.Count() @@ -118,13 +119,14 @@ // go test -bench=LemireIterate // see http://lemire.me/blog/2016/09/22/swift-versus-java-the-bitset-performance-test/ func BenchmarkLemireIterate(b *testing.B) { - bitmap := New(100000000) // we force dynamic memory allocation + bitmap := New(100000000) for v := uint(0); v <= 100000000; v += 100 { bitmap.Set(v) } + b.ResetTimer() sum := uint(0) for i := 0; i < b.N; i++ { - for i, e := bitmap.NextSet(0); e; i, e = bitmap.NextSet(i + 1) { + for j, e := bitmap.NextSet(0); e; j, e = bitmap.NextSet(j + 1) { sum++ } } @@ -132,3 +134,314 @@ return } } + +// go test -bench=LemireIterateb +// see http://lemire.me/blog/2016/09/22/swift-versus-java-the-bitset-performance-test/ +func BenchmarkLemireIterateb(b *testing.B) { + bitmap := New(100000000) + for v := uint(0); v <= 100000000; v += 100 { + bitmap.Set(v) + } + b.ResetTimer() + sum := uint(0) + for i := 0; i < b.N; i++ { + for j, e := bitmap.NextSet(0); e; j, e = bitmap.NextSet(j + 1) { + sum += j + } + } + + if sum == 0 { // added just to fool ineffassign + return + } +} + +// go test -bench=BenchmarkLemireIterateManyb +// see http://lemire.me/blog/2016/09/22/swift-versus-java-the-bitset-performance-test/ +func BenchmarkLemireIterateManyb(b *testing.B) { + bitmap := New(100000000) + for v := uint(0); v <= 100000000; v += 100 { + bitmap.Set(v) + } + buffer := make([]uint, 256) + b.ResetTimer() + sum := uint(0) + for i := 0; i < b.N; i++ { + j := uint(0) + j, buffer = bitmap.NextSetMany(j, buffer) + for ; len(buffer) > 0; j, buffer = bitmap.NextSetMany(j, buffer) { + for k := range buffer { + sum += buffer[k] + } + j++ + } + } + + if sum == 0 { // added just to fool ineffassign + return + } +} + +func setRnd(bits []uint64, halfings int) { + var rnd = rand.NewSource(0).(rand.Source64) + for i := range bits { + bits[i] = 0xFFFFFFFFFFFFFFFF + for j := 0; j < halfings; j++ { + bits[i] &= rnd.Uint64() + } + } +} + +// go test -bench=BenchmarkFlorianUekermannIterateMany +func BenchmarkFlorianUekermannIterateMany(b *testing.B) { + var input = make([]uint64, 68) + setRnd(input, 4) + var bitmap = From(input) + buffer := make([]uint, 256) + b.ResetTimer() + var checksum = uint(0) + for i := 0; i < b.N; i++ { + var last, batch = bitmap.NextSetMany(0, buffer) + for len(batch) > 0 { + for _, idx := range batch { + checksum += idx + } + last, batch = bitmap.NextSetMany(last+1, batch) + } + } + if checksum == 0 { // added just to fool ineffassign + return + } +} + +func BenchmarkFlorianUekermannIterateManyReg(b *testing.B) { + var input = make([]uint64, 68) + setRnd(input, 4) + var bitmap = From(input) + b.ResetTimer() + var checksum = uint(0) + for i := 0; i < b.N; i++ { + for j, e := bitmap.NextSet(0); e; j, e = bitmap.NextSet(j + 1) { + checksum += j + } + } + if checksum == 0 { // added just to fool ineffassign + return + } +} + +// function provided by FlorianUekermann +func good(set []uint64) (checksum uint) { + for wordIdx, word := range set { + var wordIdx = uint(wordIdx * 64) + for word != 0 { + var bitIdx = uint(trailingZeroes64(word)) + word ^= 1 << bitIdx + var index = wordIdx + bitIdx + checksum += index + } + } + return checksum +} + +func BenchmarkFlorianUekermannIterateManyComp(b *testing.B) { + var input = make([]uint64, 68) + setRnd(input, 4) + b.ResetTimer() + var checksum = uint(0) + for i := 0; i < b.N; i++ { + checksum += good(input) + } + if checksum == 0 { // added just to fool ineffassign + return + } +} + +/////// Mid density + +// go test -bench=BenchmarkFlorianUekermannLowDensityIterateMany +func BenchmarkFlorianUekermannLowDensityIterateMany(b *testing.B) { + var input = make([]uint64, 1000000) + var rnd = rand.NewSource(0).(rand.Source64) + for i := 0; i < 50000; i++ { + input[rnd.Uint64()%1000000] = 1 + } + var bitmap = From(input) + buffer := make([]uint, 256) + b.ResetTimer() + var sum = uint(0) + for i := 0; i < b.N; i++ { + j := uint(0) + j, buffer = bitmap.NextSetMany(j, buffer) + for ; len(buffer) > 0; j, buffer = bitmap.NextSetMany(j, buffer) { + for k := range buffer { + sum += buffer[k] + } + j++ + } + } + if sum == 0 { // added just to fool ineffassign + return + } +} + +func BenchmarkFlorianUekermannLowDensityIterateManyReg(b *testing.B) { + var input = make([]uint64, 1000000) + var rnd = rand.NewSource(0).(rand.Source64) + for i := 0; i < 50000; i++ { + input[rnd.Uint64()%1000000] = 1 + } + var bitmap = From(input) + b.ResetTimer() + var checksum = uint(0) + for i := 0; i < b.N; i++ { + for j, e := bitmap.NextSet(0); e; j, e = bitmap.NextSet(j + 1) { + checksum += j + } + } + if checksum == 0 { // added just to fool ineffassign + return + } +} + +func BenchmarkFlorianUekermannLowDensityIterateManyComp(b *testing.B) { + var input = make([]uint64, 1000000) + var rnd = rand.NewSource(0).(rand.Source64) + for i := 0; i < 50000; i++ { + input[rnd.Uint64()%1000000] = 1 + } + b.ResetTimer() + var checksum = uint(0) + for i := 0; i < b.N; i++ { + checksum += good(input) + } + if checksum == 0 { // added just to fool ineffassign + return + } +} + +/////// Mid density + +// go test -bench=BenchmarkFlorianUekermannMidDensityIterateMany +func BenchmarkFlorianUekermannMidDensityIterateMany(b *testing.B) { + var input = make([]uint64, 1000000) + var rnd = rand.NewSource(0).(rand.Source64) + for i := 0; i < 3000000; i++ { + input[rnd.Uint64()%1000000] |= uint64(1) << (rnd.Uint64() % 64) + } + var bitmap = From(input) + buffer := make([]uint, 256) + b.ResetTimer() + sum := uint(0) + for i := 0; i < b.N; i++ { + j := uint(0) + j, buffer = bitmap.NextSetMany(j, buffer) + for ; len(buffer) > 0; j, buffer = bitmap.NextSetMany(j, buffer) { + for k := range buffer { + sum += buffer[k] + } + j++ + } + } + + if sum == 0 { // added just to fool ineffassign + return + } +} + +func BenchmarkFlorianUekermannMidDensityIterateManyReg(b *testing.B) { + var input = make([]uint64, 1000000) + var rnd = rand.NewSource(0).(rand.Source64) + for i := 0; i < 3000000; i++ { + input[rnd.Uint64()%1000000] |= uint64(1) << (rnd.Uint64() % 64) + } + var bitmap = From(input) + b.ResetTimer() + var checksum = uint(0) + for i := 0; i < b.N; i++ { + for j, e := bitmap.NextSet(0); e; j, e = bitmap.NextSet(j + 1) { + checksum += j + } + } + if checksum == 0 { // added just to fool ineffassign + return + } +} + +func BenchmarkFlorianUekermannMidDensityIterateManyComp(b *testing.B) { + var input = make([]uint64, 1000000) + var rnd = rand.NewSource(0).(rand.Source64) + for i := 0; i < 3000000; i++ { + input[rnd.Uint64()%1000000] |= uint64(1) << (rnd.Uint64() % 64) + } + b.ResetTimer() + var checksum = uint(0) + for i := 0; i < b.N; i++ { + checksum += good(input) + } + if checksum == 0 { // added just to fool ineffassign + return + } +} + +////////// High density + +func BenchmarkFlorianUekermannMidStrongDensityIterateMany(b *testing.B) { + var input = make([]uint64, 1000000) + var rnd = rand.NewSource(0).(rand.Source64) + for i := 0; i < 20000000; i++ { + input[rnd.Uint64()%1000000] |= uint64(1) << (rnd.Uint64() % 64) + } + var bitmap = From(input) + buffer := make([]uint, 256) + b.ResetTimer() + sum := uint(0) + for i := 0; i < b.N; i++ { + j := uint(0) + j, buffer = bitmap.NextSetMany(j, buffer) + for ; len(buffer) > 0; j, buffer = bitmap.NextSetMany(j, buffer) { + for k := range buffer { + sum += buffer[k] + } + j++ + } + } + + if sum == 0 { // added just to fool ineffassign + return + } +} + +func BenchmarkFlorianUekermannMidStrongDensityIterateManyReg(b *testing.B) { + var input = make([]uint64, 1000000) + var rnd = rand.NewSource(0).(rand.Source64) + for i := 0; i < 20000000; i++ { + input[rnd.Uint64()%1000000] |= uint64(1) << (rnd.Uint64() % 64) + } + var bitmap = From(input) + b.ResetTimer() + var checksum = uint(0) + for i := 0; i < b.N; i++ { + for j, e := bitmap.NextSet(0); e; j, e = bitmap.NextSet(j + 1) { + checksum += j + } + } + if checksum == 0 { // added just to fool ineffassign + return + } +} + +func BenchmarkFlorianUekermannMidStrongDensityIterateManyComp(b *testing.B) { + var input = make([]uint64, 1000000) + var rnd = rand.NewSource(0).(rand.Source64) + for i := 0; i < 20000000; i++ { + input[rnd.Uint64()%1000000] |= uint64(1) << (rnd.Uint64() % 64) + } + b.ResetTimer() + var checksum = uint(0) + for i := 0; i < b.N; i++ { + checksum += good(input) + } + if checksum == 0 { // added just to fool ineffassign + return + } +} diff -Nru golang-github-willf-bitset-1.1.3/bitset.go golang-github-willf-bitset-1.1.11/bitset.go --- golang-github-willf-bitset-1.1.3/bitset.go 2017-08-29 22:58:51.000000000 +0000 +++ golang-github-willf-bitset-1.1.11/bitset.go 2020-07-30 13:51:44.000000000 +0000 @@ -58,6 +58,18 @@ // 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 @@ -117,7 +129,8 @@ return ^uint(0) } -// Len returns the length of the BitSet in words +// 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 } @@ -125,6 +138,9 @@ // 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) @@ -147,7 +163,12 @@ return b.set[i>>log2WordSize]&(1<<(i&(wordSize-1))) != 0 } -// Set bit i to 1 +// 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)) @@ -163,7 +184,11 @@ return b } -// SetTo sets bit i to value +// 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) @@ -171,7 +196,11 @@ return b.Clear(i) } -// Flip bit at 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) @@ -180,6 +209,95 @@ 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)<> 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) { @@ -230,6 +388,69 @@ 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) @@ -297,7 +518,8 @@ return } -// Count (number of set bits) +// 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)) @@ -305,12 +527,12 @@ return 0 } -// Equal tests the equvalence of two BitSets. +// 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 { - return false + if c == nil || b == nil { + return c == b } if b.length != c.length { return false @@ -558,7 +780,7 @@ return b.Count() == b.length } -// None returns true if no bit is set, false otherwise. Retursn true for +// None returns true if no bit is set, false otherwise. Returns true for // empty sets. func (b *BitSet) None() bool { panicIfNull(b) @@ -604,7 +826,7 @@ for ; i >= 0; i-- { fmt.Fprintf(buffer, "%064b.", b.set[i]) } - return string(buffer.Bytes()) + return buffer.String() } // BinaryStorageSize returns the binary storage requirements @@ -617,13 +839,13 @@ length := uint64(b.length) // Write length - err := binary.Write(stream, binary.BigEndian, length) + err := binary.Write(stream, binaryOrder, length) if err != nil { return 0, err } // Write set - err = binary.Write(stream, binary.BigEndian, b.set) + err = binary.Write(stream, binaryOrder, b.set) return int64(b.BinaryStorageSize()), err } @@ -632,18 +854,18 @@ var length uint64 // Read length first - err := binary.Read(stream, binary.BigEndian, &length) + 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") + return 0, errors.New("unmarshalling error: type mismatch") } // Read remaining bytes as set - err = binary.Read(stream, binary.BigEndian, newset.set) + err = binary.Read(stream, binaryOrder, newset.set) if err != nil { return 0, err } @@ -686,7 +908,7 @@ } // URLEncode all bytes - return json.Marshal(base64.URLEncoding.EncodeToString(buffer.Bytes())) + return json.Marshal(base64Encoding.EncodeToString(buffer.Bytes())) } // UnmarshalJSON unmarshals a BitSet from JSON created using MarshalJSON @@ -699,7 +921,7 @@ } // URLDecode string - buf, err := base64.URLEncoding.DecodeString(s) + buf, err := base64Encoding.DecodeString(s) if err != nil { return err } diff -Nru golang-github-willf-bitset-1.1.3/bitset_test.go golang-github-willf-bitset-1.1.11/bitset_test.go --- golang-github-willf-bitset-1.1.3/bitset_test.go 2017-08-29 22:58:51.000000000 +0000 +++ golang-github-willf-bitset-1.1.11/bitset_test.go 2020-07-30 13:51:44.000000000 +0000 @@ -11,6 +11,7 @@ "encoding/json" "fmt" "math" + "strconv" "testing" ) @@ -22,7 +23,6 @@ if v.String() != "{0,1,2,3,4,5,6,7,8,9}" { t.Error("bad string output") } - fmt.Println(v) } func TestStringLong(t *testing.T) { @@ -81,6 +81,38 @@ } } +func TestLenIsNumberOfBitsNotBytes(t *testing.T) { + var b BitSet + if b.Len() != 0 { + t.Errorf("empty bitset should have Len 0, got %v", b.Len()) + } + + b.Set(0) + if b.Len() != 1 { + t.Errorf("bitset with first bit set should have Len 1, got %v", b.Len()) + } + + b.Set(8) + if b.Len() != 9 { + t.Errorf("bitset with 0th and 8th bit set should have Len 9, got %v", b.Len()) + } + + b.Set(1) + if b.Len() != 9 { + t.Errorf("bitset with 0th, 1st and 8th bit set should have Len 9, got %v", b.Len()) + } +} + +func ExampleBitSet_Len() { + var b BitSet + b.Set(8) + fmt.Println("len", b.Len()) + fmt.Println("count", b.Count()) + // Output: + // len 9 + // count 1 +} + func TestBitSetIsClear(t *testing.T) { v := New(1000) for i := uint(0); i < 1000; i++ { @@ -100,6 +132,20 @@ v.Set(32) } +func TestExceedCap(t *testing.T) { + defer func() { + if r := recover(); r == nil { + t.Error("Set to capacity should have caused a panic") + } + }() + NumHosts := uint(32768) + bmp := New(NumHosts) + bmp.ClearAll() + d := Cap() + bmp.Set(d) + +} + func TestExpand(t *testing.T) { v := New(0) defer func() { @@ -517,6 +563,281 @@ } } +func TestShrink(t *testing.T) { + b := New(0) + + b.Set(0) + b.Set(1) + b.Set(2) + b.Set(3) + b.Set(64) + b.Compact() + if !b.Test(0) { + t.Error("0 should be set") + return + } + if !b.Test(1) { + t.Error("1 should be set") + return + } + if !b.Test(2) { + t.Error("2 should be set") + return + } + if !b.Test(3) { + t.Error("3 should be set") + return + } + if !b.Test(64) { + t.Error("64 should be set") + return + } + + b.Shrink(2) + if !b.Test(0) { + t.Error("0 should be set") + return + } + if !b.Test(1) { + t.Error("1 should be set") + return + } + if !b.Test(2) { + t.Error("2 should be set") + return + } + if b.Test(3) { + t.Error("3 should not be set") + return + } + if b.Test(64) { + t.Error("64 should not be set") + return + } + + b.Set(24) + b.Shrink(100) + if !b.Test(24) { + t.Error("24 should be set") + return + } + + b.Set(127) + b.Set(128) + b.Set(129) + b.Compact() + if !b.Test(127) { + t.Error("127 should be set") + return + } + if !b.Test(128) { + t.Error("128 should be set") + return + } + if !b.Test(129) { + t.Error("129 be set") + return + } + + b.Shrink(128) + if !b.Test(127) { + t.Error("127 should be set") + return + } + if !b.Test(128) { + t.Error("128 should be set") + return + } + if b.Test(129) { + t.Error("129 should not be set") + return + } + + b.Set(129) + b.Shrink(129) + if !b.Test(129) { + t.Error("129 should be set") + return + } + + b.Set(1000) + b.Set(2000) + b.Set(3000) + b.Shrink(3000) + if len(b.set) != 3000/64+1 { + t.Error("Wrong length of BitSet.set") + return + } + if !b.Test(3000) { + t.Error("3000 should be set") + return + } + + b.Shrink(2000) + if len(b.set) != 2000/64+1 { + t.Error("Wrong length of BitSet.set") + return + } + if b.Test(3000) { + t.Error("3000 should not be set") + return + } + if !b.Test(2000) { + t.Error("2000 should be set") + return + } + if !b.Test(1000) { + t.Error("1000 should be set") + return + } + if !b.Test(24) { + t.Error("24 should be set") + return + } +} + +func TestInsertAtWithSet(t *testing.T) { + b := New(0) + b.Set(0) + b.Set(1) + b.Set(63) + b.Set(64) + b.Set(65) + + b.InsertAt(3) + if !b.Test(0) { + t.Error("0 should be set") + return + } + if !b.Test(1) { + t.Error("1 should be set") + return + } + if b.Test(3) { + t.Error("3 should not be set") + return + } + if !b.Test(64) { + t.Error("64 should be set") + return + } + if !b.Test(65) { + t.Error("65 should be set") + return + } + if !b.Test(66) { + t.Error("66 should be set") + return + } + +} + +func TestInsertAt(t *testing.T) { + type testCase struct { + input []string + insertIdx uint + expected []string + } + + testCases := []testCase{ + { + input: []string{ + "1111111111111111111111111111111111111111111111111111111111111111", + }, + insertIdx: uint(62), + expected: []string{ + "1011111111111111111111111111111111111111111111111111111111111111", + "0000000000000000000000000000000000000000000000000000000000000001", + }, + }, + { + input: []string{ + "1111111111111111111111111111111111111111111111111111111111111111", + }, + insertIdx: uint(63), + expected: []string{ + "0111111111111111111111111111111111111111111111111111111111111111", + "0000000000000000000000000000000000000000000000000000000000000001", + }, + }, + { + input: []string{ + "1111111111111111111111111111111111111111111111111111111111111111", + }, + insertIdx: uint(0), + expected: []string{ + "1111111111111111111111111111111111111111111111111111111111111110", + "0000000000000000000000000000000000000000000000000000000000000001", + }, + }, + { + input: []string{ + "1111111111111111111111111111111111111111111111111111111111111111", + "1111111111111111111111111111111111111111111111111111111111111111", + "1111111111111111111111111111111111111111111111111111111111111111", + }, + insertIdx: uint(70), + expected: []string{ + "1111111111111111111111111111111111111111111111111111111111111111", + "1111111111111111111111111111111111111111111111111111111110111111", + "1111111111111111111111111111111111111111111111111111111111111111", + "0000000000000000000000000000000000000000000000000000000000000001", + }, + }, + { + input: []string{ + "1111111111111111111111111111111111111111111111111111111111111111", + "1111111111111111111111111111111111111111111111111111111111111111", + "1111111111111111111111111111111111111111111111111111111111110000", + }, + insertIdx: uint(70), + expected: []string{ + "1111111111111111111111111111111111111111111111111111111111111111", + "1111111111111111111111111111111111111111111111111111111110111111", + "1111111111111111111111111111111111111111111111111111111111100001", + "0000000000000000000000000000000000000000000000000000000000000001", + }, + }, + { + input: []string{ + "1111111111111111111111111111111111111111111111111111111111110000", + }, + insertIdx: uint(10), + expected: []string{ + "1111111111111111111111111111111111111111111111111111101111110000", + "0000000000000000000000000000000000000000000000000000000000000001", + }, + }, + } + + for _, tc := range testCases { + var input []uint64 + for _, inputElement := range tc.input { + parsed, _ := strconv.ParseUint(inputElement, 2, 64) + input = append(input, parsed) + } + + var expected []uint64 + for _, expectedElement := range tc.expected { + parsed, _ := strconv.ParseUint(expectedElement, 2, 64) + expected = append(expected, parsed) + } + + b := From(input) + b.InsertAt(tc.insertIdx) + if len(b.set) != len(expected) { + t.Error("Length of sets should be equal") + return + } + for i := range b.set { + if b.set[i] != expected[i] { + t.Error("Unexpected results found in set") + return + } + } + } +} + func TestNone(t *testing.T) { v := New(0) if !v.None() { @@ -571,6 +892,15 @@ if !a.Equal(b) { t.Error("Two empty set should be equal") } + var x *BitSet + var y *BitSet + z := New(0) + if !x.Equal(y) { + t.Error("Two nil bitsets should be equal") + } + if x.Equal(z) { + t.Error("Nil receiver bitset should not be equal to non-nil bitset") + } } func TestUnion(t *testing.T) { @@ -883,6 +1213,20 @@ } } +func TestMarshalUnmarshalBinaryByLittleEndian(t *testing.T) { + LittleEndian() + a := New(1010).Set(10).Set(1001) + b := new(BitSet) + + copyBinary(t, a, b) + + // BitSets must be equal after marshalling and unmarshalling + if !a.Equal(b) { + t.Error("Bitsets are not equal:\n\t", a.DumpAsBits(), "\n\t", b.DumpAsBits()) + return + } +} + func copyBinary(t *testing.T, from encoding.BinaryMarshaler, to encoding.BinaryUnmarshaler) { data, err := from.MarshalBinary() if err != nil { @@ -919,6 +1263,29 @@ } } +func TestMarshalUnmarshalJSONByStdEncoding(t *testing.T) { + Base64StdEncoding() + a := New(1010).Set(10).Set(1001) + data, err := json.Marshal(a) + if err != nil { + t.Errorf(err.Error()) + return + } + + b := new(BitSet) + err = json.Unmarshal(data, b) + if err != nil { + t.Errorf(err.Error()) + return + } + + // Bitsets must be equal after marshalling and unmarshalling + if !a.Equal(b) { + t.Error("Bitsets are not equal:\n\t", a.DumpAsBits(), "\n\t", b.DumpAsBits()) + return + } +} + func TestSafeSet(t *testing.T) { b := new(BitSet) c := b.safeSet() @@ -977,14 +1344,6 @@ } } -func TestNewPanic(t *testing.T) { - n := New(Cap()) - if n.length != 0 { - t.Error("Unexpected value: ", n.length) - return - } -} - func TestTestTooLong(t *testing.T) { b := new(BitSet) if b.Test(1) { @@ -1052,3 +1411,147 @@ return } } + +func TestDeleteWithBitStrings(t *testing.T) { + type testCase struct { + input []string + deleteIdx uint + expected []string + } + + testCases := []testCase{ + { + input: []string{ + "1110000000000000000000000000000000000000000000000000000000000001", + }, + deleteIdx: uint(63), + expected: []string{ + "0110000000000000000000000000000000000000000000000000000000000001", + }, + }, + { + input: []string{ + "1000000000000000000000000000000000000000000000000000000000010101", + }, + deleteIdx: uint(0), + expected: []string{ + "0100000000000000000000000000000000000000000000000000000000001010", + }, + }, + { + input: []string{ + "0000000000000000000000000000000000000000000000000000000000111000", + }, + deleteIdx: uint(4), + expected: []string{ + "0000000000000000000000000000000000000000000000000000000000011000", + }, + }, + { + input: []string{ + "1000000000000000000000000000000000000000000000000000000000000001", + "1010000000000000000000000000000000000000000000000000000000000001", + }, + deleteIdx: uint(63), + expected: []string{ + "1000000000000000000000000000000000000000000000000000000000000001", + "0101000000000000000000000000000000000000000000000000000000000000", + }, + }, + { + input: []string{ + "1000000000000000000000000000000000000000000000000000000000000000", + "1000000000000000000000000000000000000000000000000000000000000001", + "1000000000000000000000000000000000000000000000000000000000000001", + }, + deleteIdx: uint(64), + expected: []string{ + "1000000000000000000000000000000000000000000000000000000000000000", + "1100000000000000000000000000000000000000000000000000000000000000", + "0100000000000000000000000000000000000000000000000000000000000000", + }, + }, + { + input: []string{ + "0000000000000000000000000000000000000000000000000000000000000001", + "0000000000000000000000000000000000000000000000000000000000000001", + "0000000000000000000000000000000000000000000000000000000000000001", + "0000000000000000000000000000000000000000000000000000000000000001", + "0000000000000000000000000000000000000000000000000000000000000001", + }, + deleteIdx: uint(256), + expected: []string{ + "0000000000000000000000000000000000000000000000000000000000000001", + "0000000000000000000000000000000000000000000000000000000000000001", + "0000000000000000000000000000000000000000000000000000000000000001", + "0000000000000000000000000000000000000000000000000000000000000001", + "0000000000000000000000000000000000000000000000000000000000000000", + }, + }, + } + + for _, tc := range testCases { + var input []uint64 + for _, inputElement := range tc.input { + parsed, _ := strconv.ParseUint(inputElement, 2, 64) + input = append(input, parsed) + } + + var expected []uint64 + for _, expectedElement := range tc.expected { + parsed, _ := strconv.ParseUint(expectedElement, 2, 64) + expected = append(expected, parsed) + } + + b := From(input) + b.DeleteAt(tc.deleteIdx) + if len(b.set) != len(expected) { + t.Errorf("Length of sets expected to be %d, but was %d", len(expected), len(b.set)) + return + } + for i := range b.set { + if b.set[i] != expected[i] { + t.Errorf("Unexpected output\nExpected: %b\nGot: %b", expected[i], b.set[i]) + return + } + } + } +} + +func TestDeleteWithBitSetInstance(t *testing.T) { + length := uint(256) + bitSet := New(length) + + // the indexes that get set in the bit set + indexesToSet := []uint{0, 1, 126, 127, 128, 129, 170, 171, 200, 201, 202, 203, 255} + + // the position we delete from the bitset + deleteAt := uint(127) + + // the indexes that we expect to be set after the delete + expectedToBeSet := []uint{0, 1, 126, 127, 128, 169, 170, 199, 200, 201, 202, 254} + + expected := make(map[uint]struct{}) + for _, index := range expectedToBeSet { + expected[index] = struct{}{} + } + + for _, index := range indexesToSet { + bitSet.Set(index) + } + + bitSet.DeleteAt(deleteAt) + + for i := uint(0); i < length; i++ { + if _, ok := expected[i]; ok { + if !bitSet.Test(i) { + t.Errorf("Expected index %d to be set, but wasn't", i) + } + } else { + if bitSet.Test(i) { + t.Errorf("Expected index %d to not be set, but was", i) + } + } + + } +} diff -Nru golang-github-willf-bitset-1.1.3/debian/changelog golang-github-willf-bitset-1.1.11/debian/changelog --- golang-github-willf-bitset-1.1.3/debian/changelog 2018-02-03 18:13:34.000000000 +0000 +++ golang-github-willf-bitset-1.1.11/debian/changelog 2020-08-23 16:09:17.000000000 +0000 @@ -1,3 +1,30 @@ +golang-github-willf-bitset (1.1.11-1) unstable; urgency=medium + + [ Alexandre Viau ] + * Point Vcs-* urls to salsa.debian.org. + + [ Jelmer Vernooij ] + * Use secure copyright file specification URI. + * Fix Debian QA group name. + + [ Debian Janitor ] + * Update standards version to 4.1.1, no changes needed. + * Bump debhelper from old 10 to 12. + * Change priority extra to priority optional. + * Update renamed lintian tag names in lintian overrides. + * Set upstream metadata fields: Repository. + + [ Shengjing Zhu ] + * New upstream version 1.1.11 + * New maintainer (Closes: #889198) + * Update debhelper compat to 13 + * Update Standards-Version to 4.5.0 (no changes) + * Add Rules-Requires-Root + * Enable tests + * Update d/copyright + + -- Shengjing Zhu Mon, 24 Aug 2020 00:09:17 +0800 + golang-github-willf-bitset (1.1.3-3) unstable; urgency=medium * Remove Michael Lustfield from Uploaders list. diff -Nru golang-github-willf-bitset-1.1.3/debian/compat golang-github-willf-bitset-1.1.11/debian/compat --- golang-github-willf-bitset-1.1.3/debian/compat 2018-02-03 17:53:04.000000000 +0000 +++ golang-github-willf-bitset-1.1.11/debian/compat 1970-01-01 00:00:00.000000000 +0000 @@ -1 +0,0 @@ -10 diff -Nru golang-github-willf-bitset-1.1.3/debian/control golang-github-willf-bitset-1.1.11/debian/control --- golang-github-willf-bitset-1.1.3/debian/control 2018-02-03 18:13:34.000000000 +0000 +++ golang-github-willf-bitset-1.1.11/debian/control 2020-08-23 16:09:17.000000000 +0000 @@ -1,21 +1,23 @@ Source: golang-github-willf-bitset Section: devel -Priority: extra -Maintainer: QA Group -Build-Depends: debhelper (>= 10), +Priority: optional +Maintainer: Debian Go Packaging Team +Uploaders: Shengjing Zhu , +Build-Depends: debhelper-compat (= 13), dh-golang, - golang-any -Standards-Version: 4.1.0 + golang-any, +Standards-Version: 4.5.0 Homepage: https://github.com/willf/bitset -Vcs-Browser: https://anonscm.debian.org/cgit/pkg-go/packages/golang-github-willf-bitset.git -Vcs-Git: https://anonscm.debian.org/git/pkg-go/packages/golang-github-willf-bitset.git +Vcs-Browser: https://salsa.debian.org/go-team/packages/golang-github-willf-bitset +Vcs-Git: https://salsa.debian.org/go-team/packages/golang-github-willf-bitset.git +Rules-Requires-Root: no Testsuite: autopkgtest-pkg-go XS-Go-Import-Path: github.com/willf/bitset Package: golang-github-willf-bitset-dev Architecture: all -Depends: ${shlibs:Depends}, - ${misc:Depends} +Depends: ${misc:Depends}, + ${shlibs:Depends}, Description: Implements bitsets, a mapping between non-negative integers and boolean values This package provides a Go library with methods for setting, clearing, flipping, and testing individual integers. diff -Nru golang-github-willf-bitset-1.1.3/debian/copyright golang-github-willf-bitset-1.1.11/debian/copyright --- golang-github-willf-bitset-1.1.3/debian/copyright 2018-02-03 17:53:04.000000000 +0000 +++ golang-github-willf-bitset-1.1.11/debian/copyright 2020-08-23 16:09:17.000000000 +0000 @@ -1,4 +1,4 @@ -Format: http://www.debian.org/doc/packaging-manuals/copyright-format/1.0/ +Format: https://www.debian.org/doc/packaging-manuals/copyright-format/1.0/ Upstream-Name: bitset Source: https://github.com/willf/bitset @@ -6,11 +6,6 @@ Copyright: 2014 Will Fitzgerald License: BSD-3-clause -Files: Makefile -Copyright: 2014 Will Fitzgerald -License: BSD-3-clause -Comment: Author listed as Nicola Asuni - Files: debian/* Copyright: 2017 Michael Lustfield License: BSD-3-clause diff -Nru golang-github-willf-bitset-1.1.3/debian/gitlab-ci.yml golang-github-willf-bitset-1.1.11/debian/gitlab-ci.yml --- golang-github-willf-bitset-1.1.3/debian/gitlab-ci.yml 1970-01-01 00:00:00.000000000 +0000 +++ golang-github-willf-bitset-1.1.11/debian/gitlab-ci.yml 2020-08-23 16:09:17.000000000 +0000 @@ -0,0 +1,28 @@ + +# auto-generated, DO NOT MODIFY. +# The authoritative copy of this file lives at: +# https://salsa.debian.org/go-team/ci/blob/master/cmd/ci/gitlabciyml.go + +# TODO: publish under debian-go-team/ci +image: stapelberg/ci2 + +test_the_archive: + artifacts: + paths: + - before-applying-commit.json + - after-applying-commit.json + script: + # Create an overlay to discard writes to /srv/gopath/src after the build: + - "rm -rf /cache/overlay/{upper,work}" + - "mkdir -p /cache/overlay/{upper,work}" + - "mount -t overlay overlay -o lowerdir=/srv/gopath/src,upperdir=/cache/overlay/upper,workdir=/cache/overlay/work /srv/gopath/src" + - "export GOPATH=/srv/gopath" + - "export GOCACHE=/cache/go" + # Build the world as-is: + - "ci-build -exemptions=/var/lib/ci-build/exemptions.json > before-applying-commit.json" + # Copy this package into the overlay: + - "GBP_CONF_FILES=:debian/gbp.conf gbp buildpackage --git-no-pristine-tar --git-ignore-branch --git-ignore-new --git-export-dir=/tmp/export --git-no-overlay --git-tarball-dir=/nonexistant --git-cleaner=/bin/true --git-builder='dpkg-buildpackage -S -d --no-sign'" + - "pgt-gopath -dsc /tmp/export/*.dsc" + # Rebuild the world: + - "ci-build -exemptions=/var/lib/ci-build/exemptions.json > after-applying-commit.json" + - "ci-diff before-applying-commit.json after-applying-commit.json" diff -Nru golang-github-willf-bitset-1.1.3/debian/rules golang-github-willf-bitset-1.1.11/debian/rules --- golang-github-willf-bitset-1.1.3/debian/rules 2018-02-03 17:53:04.000000000 +0000 +++ golang-github-willf-bitset-1.1.11/debian/rules 2020-08-23 16:09:17.000000000 +0000 @@ -2,6 +2,3 @@ %: dh $@ --buildsystem=golang --with=golang - -# Tests fail on 32-bit architectures. -override_dh_auto_test: diff -Nru golang-github-willf-bitset-1.1.3/debian/source/lintian-overrides golang-github-willf-bitset-1.1.11/debian/source/lintian-overrides --- golang-github-willf-bitset-1.1.3/debian/source/lintian-overrides 2018-02-03 17:53:04.000000000 +0000 +++ golang-github-willf-bitset-1.1.11/debian/source/lintian-overrides 2020-08-23 16:09:17.000000000 +0000 @@ -1,2 +1,2 @@ # upstream does not sign releases -source: debian-watch-may-check-gpg-signature +source: debian-watch-does-not-check-gpg-signature diff -Nru golang-github-willf-bitset-1.1.3/debian/upstream/metadata golang-github-willf-bitset-1.1.11/debian/upstream/metadata --- golang-github-willf-bitset-1.1.3/debian/upstream/metadata 1970-01-01 00:00:00.000000000 +0000 +++ golang-github-willf-bitset-1.1.11/debian/upstream/metadata 2020-08-23 16:09:17.000000000 +0000 @@ -0,0 +1 @@ +Repository: https://github.com/willf/bitset diff -Nru golang-github-willf-bitset-1.1.3/.github/FUNDING.yml golang-github-willf-bitset-1.1.11/.github/FUNDING.yml --- golang-github-willf-bitset-1.1.3/.github/FUNDING.yml 1970-01-01 00:00:00.000000000 +0000 +++ golang-github-willf-bitset-1.1.11/.github/FUNDING.yml 2020-07-30 13:51:44.000000000 +0000 @@ -0,0 +1,5 @@ +# You can add one username per supported platform and one custom link +patreon: # Replace with your Patreon username +open_collective: # Replace with your Open Collective username +ko_fi: # Replace with your Ko-fi username +custom: https://donate.mcc.org/ # Replace with your custom donation URL diff -Nru golang-github-willf-bitset-1.1.3/.github/workflows/test.yml golang-github-willf-bitset-1.1.11/.github/workflows/test.yml --- golang-github-willf-bitset-1.1.3/.github/workflows/test.yml 1970-01-01 00:00:00.000000000 +0000 +++ golang-github-willf-bitset-1.1.11/.github/workflows/test.yml 2020-07-30 13:51:44.000000000 +0000 @@ -0,0 +1,18 @@ +on: pull_request +name: Test +jobs: + test: + strategy: + matrix: + go-version: ['1.13', '1.14'] + os: [ubuntu-latest, macos-latest, windows-latest] + runs-on: ${{ matrix.os }} + steps: + - name: Install Go + uses: actions/setup-go@v2 + with: + go-version: ${{ matrix.go-version }} + - name: Checkout code + uses: actions/checkout@master + - name: Test + run: go test ./... diff -Nru golang-github-willf-bitset-1.1.3/go.mod golang-github-willf-bitset-1.1.11/go.mod --- golang-github-willf-bitset-1.1.3/go.mod 1970-01-01 00:00:00.000000000 +0000 +++ golang-github-willf-bitset-1.1.11/go.mod 2020-07-30 13:51:44.000000000 +0000 @@ -0,0 +1,3 @@ +module github.com/willf/bitset + +go 1.14 diff -Nru golang-github-willf-bitset-1.1.3/Makefile golang-github-willf-bitset-1.1.11/Makefile --- golang-github-willf-bitset-1.1.3/Makefile 2017-08-29 22:58:51.000000000 +0000 +++ golang-github-willf-bitset-1.1.11/Makefile 1970-01-01 00:00:00.000000000 +0000 @@ -1,197 +0,0 @@ -# MAKEFILE -# -# @author Nicola Asuni -# @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 - -# Suggest code simplifications -gosimple: - @mkdir -p target/report - GOPATH=$(GOPATH) gosimple ./ | tee target/report/gosimple.txt - -# AST scanner -astscan: - @mkdir -p target/report - GOPATH=$(GOPATH) gas .//*.go | tee target/report/astscan.txt ; test $${PIPESTATUS[0]} -eq 0 - -# 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 ''${PKGNAME}' Documentation ...' > 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 github.com/golang/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 honnef.co/go/tools/cmd/gosimple - GOPATH=$(GOPATH) go get github.com/GoASTScanner/gas - -# Remove any build artifact -clean: - GOPATH=$(GOPATH) go clean ./... - -# Deletes any intermediate file -nuke: - rm -rf ./target - GOPATH=$(GOPATH) go clean -i ./... diff -Nru golang-github-willf-bitset-1.1.3/README.md golang-github-willf-bitset-1.1.11/README.md --- golang-github-willf-bitset-1.1.3/README.md 2017-08-29 22:58:51.000000000 +0000 +++ golang-github-willf-bitset-1.1.11/README.md 2020-07-30 13:51:44.000000000 +0000 @@ -2,10 +2,10 @@ *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) +[![Test](https://github.com/willf/bitset/workflows/Test/badge.svg)](https://github.com/willf/bitset/actions?query=workflow%3ATest) [![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) +[![PkgGoDev](https://pkg.go.dev/badge/github.com/willf/bitset?tab=doc)](https://pkg.go.dev/github.com/willf/bitset?tab=doc) ## Description @@ -63,8 +63,11 @@ 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 +Package documentation is at: https://pkg.go.dev/github.com/willf/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 @@ -82,15 +85,10 @@ 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): +Before committing the code, please check if it passes tests, has adequate coverage, etc. ```bash -make qa +go test +go test -cover ``` diff -Nru golang-github-willf-bitset-1.1.3/.travis.yml golang-github-willf-bitset-1.1.11/.travis.yml --- golang-github-willf-bitset-1.1.3/.travis.yml 2017-08-29 22:58:51.000000000 +0000 +++ golang-github-willf-bitset-1.1.11/.travis.yml 2020-07-30 13:51:44.000000000 +0000 @@ -12,8 +12,7 @@ - travis go: - - 1.8 - - 1.9 + - "1.11.x" - tip matrix: @@ -35,4 +34,4 @@ - cat ./target/test/report.xml after_success: - - if [ "$TRAVIS_GO_VERSION" = "1.8" ]; then $HOME/gopath/bin/goveralls -covermode=count -coverprofile=target/report/coverage.out -service=travis-ci; fi; + - if [ "$TRAVIS_GO_VERSION" = "1.11.1" ]; then $HOME/gopath/bin/goveralls -covermode=count -coverprofile=target/report/coverage.out -service=travis-ci; fi; diff -Nru golang-github-willf-bitset-1.1.3/VERSION golang-github-willf-bitset-1.1.11/VERSION --- golang-github-willf-bitset-1.1.3/VERSION 2017-08-29 22:58:51.000000000 +0000 +++ golang-github-willf-bitset-1.1.11/VERSION 1970-01-01 00:00:00.000000000 +0000 @@ -1 +0,0 @@ -1.1.3