From efe2f9881e50811bddd3054c6768a2e213c16d7c Mon Sep 17 00:00:00 2001 From: "dependabot[bot]" <49699333+dependabot[bot]@users.noreply.github.com> Date: Mon, 21 Mar 2022 02:15:59 +0000 Subject: [PATCH] build(deps): bump github.com/bits-and-blooms/bitset from 1.2.0 to 1.2.2 Bumps [github.com/bits-and-blooms/bitset](https://github.com/bits-and-blooms/bitset) from 1.2.0 to 1.2.2. - [Release notes](https://github.com/bits-and-blooms/bitset/releases) - [Commits](https://github.com/bits-and-blooms/bitset/compare/v1.2.0...v1.2.2) --- updated-dependencies: - dependency-name: github.com/bits-and-blooms/bitset dependency-type: direct:production update-type: version-update:semver-patch ... Signed-off-by: dependabot[bot] --- go.mod | 2 +- go.sum | 3 +- .../bits-and-blooms/bitset/bitset.go | 82 ++++++++++++++----- vendor/modules.txt | 2 +- 4 files changed, 67 insertions(+), 22 deletions(-) diff --git a/go.mod b/go.mod index a45e2da843c..b879909578d 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.2.2 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..ec3227b03c0 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.2.2 h1:J5gbX05GpMdBjCvQ9MteIg2KKDExr7DrgK+Yc15FvIk= +github.com/bits-and-blooms/bitset v1.2.2/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..be2f5fb5c51 100644 --- a/vendor/github.com/bits-and-blooms/bitset/bitset.go +++ b/vendor/github.com/bits-and-blooms/bitset/bitset.go @@ -89,7 +89,12 @@ func (b *BitSet) safeSet() []uint64 { // 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 @@ -226,7 +231,9 @@ func (b *BitSet) FlipRange(start, end uint) *BitSet { 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) >> (-end & (wordSize - 1)) + } return b } @@ -254,7 +261,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) - uint64(length&(wordSize-1)))) + } return b } @@ -522,9 +531,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 +549,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 { @@ -866,7 +897,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 } @@ -886,9 +928,18 @@ func (b *BitSet) ReadFrom(stream io.Reader) (int64, error) { } // Read remaining bytes as set - err = binary.Read(stream, binaryOrder, newset.set) - if err != nil { - return 0, err + // current implementation bufio.Reader is more memory efficient than + // binary.Read for large set + reader := bufio.NewReader(stream) + var item = make([]byte, binary.Size(uint64(0))) // one uint64 + for i := uint64(0); i < length; i++ { + if _, err := reader.Read(item); err != nil { + if err == io.EOF { + break // done + } + return 0, err + } + newset.set[i] = binaryOrder.Uint64(item) } *b = *newset @@ -898,25 +949,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..91dfc9c6598 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.2.2 ## explicit github.com/bits-and-blooms/bitset # github.com/checkpoint-restore/go-criu/v5 v5.0.0