From 5e20f2ecc145837ae0282a9a7e0c123f6c0c5c27 Mon Sep 17 00:00:00 2001 From: "dependabot[bot]" <49699333+dependabot[bot]@users.noreply.github.com> Date: Thu, 15 Sep 2022 02:17:07 +0000 Subject: [PATCH] build(deps): bump github.com/bits-and-blooms/bitset from 1.2.0 to 1.3.3 Bumps [github.com/bits-and-blooms/bitset](https://github.com/bits-and-blooms/bitset) from 1.2.0 to 1.3.3. - [Release notes](https://github.com/bits-and-blooms/bitset/releases) - [Commits](https://github.com/bits-and-blooms/bitset/compare/v1.2.0...v1.3.3) --- updated-dependencies: - dependency-name: github.com/bits-and-blooms/bitset dependency-type: direct:production update-type: version-update:semver-minor ... Signed-off-by: dependabot[bot] --- go.mod | 2 +- go.sum | 3 +- .../bits-and-blooms/bitset/bitset.go | 208 +++++++++++------- vendor/modules.txt | 2 +- 4 files changed, 136 insertions(+), 79 deletions(-) diff --git a/go.mod b/go.mod index a45e2da843c..111e72f1028 100644 --- a/go.mod +++ b/go.mod @@ -3,7 +3,7 @@ module github.com/opencontainers/runc go 1.15 require ( - github.com/bits-and-blooms/bitset v1.2.0 + github.com/bits-and-blooms/bitset v1.3.3 github.com/checkpoint-restore/go-criu/v5 v5.0.0 github.com/cilium/ebpf v0.6.2 github.com/containerd/console v1.0.3 diff --git a/go.sum b/go.sum index 7937c033bdb..e07cdba7900 100644 --- a/go.sum +++ b/go.sum @@ -1,6 +1,7 @@ github.com/BurntSushi/toml v0.3.1/go.mod h1:xHWCNGjB5oqiDr8zfno3MHue2Ht5sIBksp03qcyfWMU= -github.com/bits-and-blooms/bitset v1.2.0 h1:Kn4yilvwNtMACtf1eYDlG8H77R07mZSPbMjLyS07ChA= github.com/bits-and-blooms/bitset v1.2.0/go.mod h1:gIdJ4wp64HaoK2YrL1Q5/N7Y16edYb8uY+O0FJTyyDA= +github.com/bits-and-blooms/bitset v1.3.3 h1:R1XWiopGiXf66xygsiLpzLo67xEYvMkHw3w+rCOSAwg= +github.com/bits-and-blooms/bitset v1.3.3/go.mod h1:gIdJ4wp64HaoK2YrL1Q5/N7Y16edYb8uY+O0FJTyyDA= github.com/checkpoint-restore/go-criu/v5 v5.0.0 h1:TW8f/UvntYoVDMN1K2HlT82qH1rb0sOjpGw3m6Ym+i4= github.com/checkpoint-restore/go-criu/v5 v5.0.0/go.mod h1:cfwC0EG7HMUenopBsUf9d89JlCLQIfgVcNsNN0t6T2M= github.com/cilium/ebpf v0.6.2 h1:iHsfF/t4aW4heW2YKfeHrVPGdtYTL4C4KocpM8KTSnI= diff --git a/vendor/github.com/bits-and-blooms/bitset/bitset.go b/vendor/github.com/bits-and-blooms/bitset/bitset.go index d688806a54b..32d7cfb1245 100644 --- a/vendor/github.com/bits-and-blooms/bitset/bitset.go +++ b/vendor/github.com/bits-and-blooms/bitset/bitset.go @@ -33,7 +33,6 @@ Example use: As an alternative to BitSets, one should check out the 'big' package, which provides a (less set-theoretical) view of bitsets. - */ package bitset @@ -87,9 +86,20 @@ func (b *BitSet) safeSet() []uint64 { return b.set } +// SetBitsetFrom fills the bitset with an array of integers without creating a new BitSet instance +func (b *BitSet) SetBitsetFrom(buf []uint64) { + b.length = uint(len(buf)) * 64 + b.set = buf +} + // 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} + return FromWithLength(uint(len(buf))*64, buf) +} + +// FromWithLength constructs from an array of integers and length. +func FromWithLength(len uint, set []uint64) *BitSet { + return &BitSet{len, set} } // Bytes returns the bitset as array of integers @@ -105,6 +115,11 @@ func wordsNeeded(i uint) int { return int((i + (wordSize - 1)) >> log2WordSize) } +// wordsIndex calculates the index of words in a `uint64` +func wordsIndex(i uint) uint { + return i & (wordSize - 1) +} + // New creates a new BitSet with a hint that length bits will be required func New(length uint) (bset *BitSet) { defer func() { @@ -135,24 +150,22 @@ func (b *BitSet) Len() uint { return b.length } -// extendSetMaybe adds additional words to incorporate new bits if needed -func (b *BitSet) extendSetMaybe(i uint) { - if i >= b.length { // if we need more bits, make 'em - if i >= Cap() { - panic("You are exceeding the capacity") - } - nsize := wordsNeeded(i + 1) - if b.set == nil { - b.set = make([]uint64, nsize) - } else if cap(b.set) >= nsize { - b.set = b.set[:nsize] // fast resize - } else if len(b.set) < nsize { - newset := make([]uint64, nsize, 2*nsize) // increase capacity 2x - copy(newset, b.set) - b.set = newset - } - b.length = i + 1 +// extendSet adds additional words to incorporate new bits if needed +func (b *BitSet) extendSet(i uint) { + if i >= Cap() { + panic("You are exceeding the capacity") + } + nsize := wordsNeeded(i + 1) + if b.set == nil { + b.set = make([]uint64, nsize) + } else if cap(b.set) >= nsize { + b.set = b.set[:nsize] // fast resize + } else if len(b.set) < nsize { + newset := make([]uint64, nsize, 2*nsize) // increase capacity 2x + copy(newset, b.set) + b.set = newset } + b.length = i + 1 } // Test whether bit i is set. @@ -160,7 +173,7 @@ func (b *BitSet) Test(i uint) bool { if i >= b.length { return false } - return b.set[i>>log2WordSize]&(1<<(i&(wordSize-1))) != 0 + return b.set[i>>log2WordSize]&(1<>log2WordSize] |= 1 << (i & (wordSize - 1)) + if i >= b.length { // if we need more bits, make 'em + b.extendSet(i) + } + b.set[i>>log2WordSize] |= 1 << wordsIndex(i) return b } @@ -180,7 +195,7 @@ func (b *BitSet) Clear(i uint) *BitSet { if i >= b.length { return b } - b.set[i>>log2WordSize] &^= 1 << (i & (wordSize - 1)) + b.set[i>>log2WordSize] &^= 1 << wordsIndex(i) return b } @@ -205,7 +220,7 @@ func (b *BitSet) Flip(i uint) *BitSet { if i >= b.length { return b.Set(i) } - b.set[i>>log2WordSize] ^= 1 << (i & (wordSize - 1)) + b.set[i>>log2WordSize] ^= 1 << wordsIndex(i) return b } @@ -218,15 +233,18 @@ func (b *BitSet) FlipRange(start, end uint) *BitSet { if start >= end { return b } - - b.extendSetMaybe(end - 1) + if end-1 >= b.length { // if we need more bits, make 'em + b.extendSet(end - 1) + } var startWord uint = start >> log2WordSize var endWord uint = end >> log2WordSize - b.set[startWord] ^= ^(^uint64(0) << (start & (wordSize - 1))) + b.set[startWord] ^= ^(^uint64(0) << wordsIndex(start)) for i := startWord; i < endWord; i++ { b.set[i] = ^b.set[i] } - b.set[endWord] ^= ^uint64(0) >> (-end & (wordSize - 1)) + if end&(wordSize-1) != 0 { + b.set[endWord] ^= ^uint64(0) >> wordsIndex(-end) + } return b } @@ -254,7 +272,9 @@ func (b *BitSet) Shrink(lastbitindex uint) *BitSet { copy(shrunk, b.set[:idx]) b.set = shrunk b.length = length - b.set[idx-1] &= (allBits >> (uint64(64) - uint64(length&(wordSize-1)))) + if length < 64 { + b.set[idx-1] &= allBits >> uint64(64-wordsIndex(length)) + } return b } @@ -283,7 +303,7 @@ func (b *BitSet) Compact() *BitSet { // 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) + insertAtElement := idx >> log2WordSize // if length of set is a multiple of wordSize we need to allocate more space first if b.isLenExactMultiple() { @@ -302,13 +322,13 @@ func (b *BitSet) InsertAt(idx uint) *BitSet { // generate a mask to extract the data that we need to shift left // within the element where we insert a bit - dataMask := ^(uint64(1)<> (i & (wordSize - 1)) + w = w >> wordsIndex(i) if w != 0 { return i + trailingZeroes64(w), true } @@ -413,21 +433,20 @@ func (b *BitSet) NextSet(i uint) (uint, bool) { // 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 -// } -// +// 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) +// 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. @@ -438,7 +457,7 @@ func (b *BitSet) NextSetMany(i uint, buffer []uint) (uint, []uint) { if x >= len(b.set) || capacity == 0 { return 0, myanswer[:0] } - skip := i & (wordSize - 1) + skip := wordsIndex(i) word := b.set[x] >> skip myanswer = myanswer[:capacity] size := int(0) @@ -481,8 +500,8 @@ func (b *BitSet) NextClear(i uint) (uint, bool) { return 0, false } w := b.set[x] - w = w >> (i & (wordSize - 1)) - wA := allBits >> (i & (wordSize - 1)) + w = w >> wordsIndex(i) + wA := allBits >> wordsIndex(i) index := i + trailingZeroes64(^w) if w != wA && index < b.length { return index, true @@ -522,9 +541,10 @@ func (b *BitSet) Clone() *BitSet { return c } -// Copy into a destination BitSet -// Returning the size of the destination BitSet -// like array copy +// Copy into a destination BitSet using the Go array copy semantics: +// the number of bits copied is the minimum of the number of bits in the current +// BitSet (Len()) and the destination Bitset. +// We return the number of bits copied in the destination BitSet. func (b *BitSet) Copy(c *BitSet) (count uint) { if c == nil { return @@ -539,6 +559,27 @@ func (b *BitSet) Copy(c *BitSet) (count uint) { return } +// CopyFull copies into a destination BitSet such that the destination is +// identical to the source after the operation, allocating memory if necessary. +func (b *BitSet) CopyFull(c *BitSet) { + if c == nil { + return + } + c.length = b.length + if len(b.set) == 0 { + if c.set != nil { + c.set = c.set[:0] + } + } else { + if cap(c.set) < len(b.set) { + c.set = make([]uint64, len(b.set)) + } else { + c.set = c.set[:len(b.set)] + } + copy(c.set, b.set) + } +} + // Count (number of set bits). // Also known as "popcount" or "population count". func (b *BitSet) Count() uint { @@ -671,7 +712,9 @@ func (b *BitSet) InPlaceIntersection(compare *BitSet) { b.set[i] = 0 } if compare.length > 0 { - b.extendSetMaybe(compare.length - 1) + if compare.length-1 >= b.length { + b.extendSet(compare.length - 1) + } } } @@ -710,8 +753,8 @@ func (b *BitSet) InPlaceUnion(compare *BitSet) { if l > int(b.wordCount()) { l = int(b.wordCount()) } - if compare.length > 0 { - b.extendSetMaybe(compare.length - 1) + if compare.length > 0 && compare.length-1 >= b.length { + b.extendSet(compare.length - 1) } for i := 0; i < l; i++ { b.set[i] |= compare.set[i] @@ -758,8 +801,8 @@ func (b *BitSet) InPlaceSymmetricDifference(compare *BitSet) { if l > int(b.wordCount()) { l = int(b.wordCount()) } - if compare.length > 0 { - b.extendSetMaybe(compare.length - 1) + if compare.length > 0 && compare.length-1 >= b.length { + b.extendSet(compare.length - 1) } for i := 0; i < l; i++ { b.set[i] ^= compare.set[i] @@ -773,17 +816,17 @@ func (b *BitSet) InPlaceSymmetricDifference(compare *BitSet) { // Is the length an exact multiple of word sizes? func (b *BitSet) isLenExactMultiple() bool { - return b.length%wordSize == 0 + return wordsIndex(b.length) == 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) + b.set[len(b.set)-1] &= allBits >> (wordSize - wordsIndex(b.length)) } } -// Complement computes the (local) complement of a biset (up to length bits) +// Complement computes the (local) complement of a bitset (up to length bits) func (b *BitSet) Complement() (result *BitSet) { panicIfNull(b) result = New(b.length) @@ -811,7 +854,6 @@ func (b *BitSet) None() bool { return false } } - return true } return true } @@ -866,7 +908,18 @@ func (b *BitSet) WriteTo(stream io.Writer) (int64, error) { } // Write set - err = binary.Write(stream, binaryOrder, b.set) + // current implementation of bufio.Writer is more memory efficient than + // binary.Write for large set + writer := bufio.NewWriter(stream) + var item = make([]byte, binary.Size(uint64(0))) // for serializing one uint64 + for i := range b.set { + binaryOrder.PutUint64(item, b.set[i]) + if nn, err := writer.Write(item); err != nil { + return int64(i*binary.Size(uint64(0)) + nn), err + } + } + + err = writer.Flush() return int64(b.BinaryStorageSize()), err } @@ -877,6 +930,9 @@ func (b *BitSet) ReadFrom(stream io.Reader) (int64, error) { // Read length first err := binary.Read(stream, binaryOrder, &length) if err != nil { + if err == io.EOF { + err = io.ErrUnexpectedEOF + } return 0, err } newset := New(uint(length)) @@ -885,10 +941,17 @@ func (b *BitSet) ReadFrom(stream io.Reader) (int64, error) { 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 + var item [8]byte + nWords := wordsNeeded(uint(length)) + reader := bufio.NewReader(io.LimitReader(stream, 8*int64(nWords))) + for i := 0; i < nWords; i++ { + if _, err := io.ReadFull(reader, item[:]); err != nil { + if err == io.EOF { + err = io.ErrUnexpectedEOF + } + return 0, err + } + newset.set[i] = binaryOrder.Uint64(item[:]) } *b = *newset @@ -898,25 +961,18 @@ func (b *BitSet) ReadFrom(stream io.Reader) (int64, error) { // 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) + _, err := b.WriteTo(&buf) 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) - + _, err := b.ReadFrom(buf) return err } diff --git a/vendor/modules.txt b/vendor/modules.txt index 24b3c52f52e..350d7b5ead9 100644 --- a/vendor/modules.txt +++ b/vendor/modules.txt @@ -1,4 +1,4 @@ -# github.com/bits-and-blooms/bitset v1.2.0 +# github.com/bits-and-blooms/bitset v1.3.3 ## explicit github.com/bits-and-blooms/bitset # github.com/checkpoint-restore/go-criu/v5 v5.0.0