New Upstream Release - golang-github-greatroar-blobloom
Ready changes
Summary
Merged new upstream version: 0.7.2 (was: 0.7.1).
Resulting package
Built on 2022-12-14T17:17 (took 4m47s)
The resulting binary packages can be installed (if you have the apt repository enabled) by running one of:
apt install -t fresh-releases golang-github-greatroar-blobloom-dev
Lintian Result
Diff
diff --git a/README.md b/README.md
index ce2e480..a390d62 100644
--- a/README.md
+++ b/README.md
@@ -34,7 +34,7 @@ To test for the presence of a key in the filter:
if f.Has(xxhash.Sum64(key)) {
// Key is probably in f.
} else {
- // Key is certainly in f.
+ // Key is certainly not in f.
}
The false positive rate is defined as usual:
@@ -71,7 +71,7 @@ So does passing integer keys in without running them through a mixing function.
License
-------
-Copyright © 2020-2021 the Blobloom authors
+Copyright © 2020-2022 the Blobloom authors
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
diff --git a/benchmarks/go.sum b/benchmarks/go.sum
index 2a9458a..dbe507d 100644
--- a/benchmarks/go.sum
+++ b/benchmarks/go.sum
@@ -360,8 +360,9 @@ gopkg.in/yaml.v2 v2.2.1/go.mod h1:hI93XBmqTisBFMUTm0b8Fm+jr3Dg1NNxqwp+5A1VGuI=
gopkg.in/yaml.v2 v2.2.2/go.mod h1:hI93XBmqTisBFMUTm0b8Fm+jr3Dg1NNxqwp+5A1VGuI=
gopkg.in/yaml.v2 v2.2.4/go.mod h1:hI93XBmqTisBFMUTm0b8Fm+jr3Dg1NNxqwp+5A1VGuI=
gopkg.in/yaml.v2 v2.2.5/go.mod h1:hI93XBmqTisBFMUTm0b8Fm+jr3Dg1NNxqwp+5A1VGuI=
-gopkg.in/yaml.v3 v3.0.0-20200313102051-9f266ea9e77c h1:dUUwHk2QECo/6vqA44rthZ8ie2QXMNeKRTHCNY2nXvo=
gopkg.in/yaml.v3 v3.0.0-20200313102051-9f266ea9e77c/go.mod h1:K4uyk7z7BCEPqu6E+C64Yfv1cQ7kz7rIZviUmN+EgEM=
+gopkg.in/yaml.v3 v3.0.1 h1:fxVm/GzAzEWqLHuvctI91KS9hhNmmWOoWu0XTYJS7CA=
+gopkg.in/yaml.v3 v3.0.1/go.mod h1:K4uyk7z7BCEPqu6E+C64Yfv1cQ7kz7rIZviUmN+EgEM=
honnef.co/go/tools v0.0.0-20190102054323-c2f93a96b099/go.mod h1:rf3lG4BRIbNafJWhAfAdb/ePZxsR/4RtNHQocxwk9r4=
honnef.co/go/tools v0.0.0-20190523083050-ea95bdfd59fc/go.mod h1:rf3lG4BRIbNafJWhAfAdb/ePZxsR/4RtNHQocxwk9r4=
istio.io/gogo-genproto v0.0.0-20190124151557-6d926a6e6feb/go.mod h1:eIDJ6jNk/IeJz6ODSksHl5Aiczy5JUq6vFhJWI5OtiI=
diff --git a/bloomfilter.go b/bloomfilter.go
index eda9215..d1930e1 100644
--- a/bloomfilter.go
+++ b/bloomfilter.go
@@ -1,4 +1,4 @@
-// Copyright 2020-2021 the Blobloom authors
+// Copyright 2020-2022 the Blobloom authors
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
@@ -64,6 +64,15 @@ type Filter struct {
// single hash passed in by the client. It is silently increased to two if
// a lower value is given.
func New(nbits uint64, nhashes int) *Filter {
+ nbits, nhashes = fixBitsAndHashes(nbits, nhashes)
+
+ return &Filter{
+ b: make([]block, nbits/BlockBits),
+ k: nhashes,
+ }
+}
+
+func fixBitsAndHashes(nbits uint64, nhashes int) (uint64, int) {
if nbits < 1 {
nbits = BlockBits
}
@@ -79,16 +88,13 @@ func New(nbits uint64, nhashes int) *Filter {
nbits += BlockBits - nbits%BlockBits
}
- return &Filter{
- b: make([]block, nbits/BlockBits),
- k: nhashes,
- }
+ return nbits, nhashes
}
// Add insert a key with hash value h into f.
func (f *Filter) Add(h uint64) {
h1, h2 := uint32(h>>32), uint32(h)
- b := f.getblock(h2)
+ b := getblock(f.b, h2)
for i := 1; i < f.k; i++ {
h1, h2 = doublehash(h1, h2, i)
@@ -112,11 +118,11 @@ const log1minus1divBlockbits = -0.0019550348358033505576274922418668121377
// and Nejdl, summed over the blocks
// (https://www.win.tue.nl/~opapapetrou/papers/Bloomfilters-DAPD.pdf).
func (f *Filter) Cardinality() float64 {
- return f.cardinality(onescount)
+ return cardinality(f.k, f.b, onescount)
}
-func (f *Filter) cardinality(onescount func(*block) int) float64 {
- k := float64(f.k) - 1
+func cardinality(nhashes int, b []block, onescount func(*block) int) float64 {
+ k := float64(nhashes - 1)
// The probability of some bit not being set in a single insertion is
// p0 = (1-1/BlockBits)^k.
@@ -125,8 +131,8 @@ func (f *Filter) cardinality(onescount func(*block) int) float64 {
logProb0Inv := 1 / (k * log1minus1divBlockbits)
var n float64
- for i := range f.b {
- ones := onescount(&f.b[i])
+ for i := range b {
+ ones := onescount(&b[i])
if ones == 0 {
continue
}
@@ -166,7 +172,7 @@ func (f *Filter) Fill() {
// It may return a false positive.
func (f *Filter) Has(h uint64) bool {
h1, h2 := uint32(h>>32), uint32(h)
- b := f.getblock(h2)
+ b := getblock(f.b, h2)
for i := 1; i < f.k; i++ {
h1, h2 = doublehash(h1, h2, i)
@@ -234,9 +240,9 @@ const (
// A block is a fixed-size Bloom filter, used as a shard of a Filter.
type block [blockWords]uint32
-func (f *Filter) getblock(h2 uint32) *block {
- i := reducerange(h2, uint32(len(f.b)))
- return &f.b[i]
+func getblock(b []block, h2 uint32) *block {
+ i := reducerange(h2, uint32(len(b)))
+ return &b[i]
}
// reducerange maps i to an integer in the range [0,n).
diff --git a/debian/changelog b/debian/changelog
index ce04d0c..6dfd4e5 100644
--- a/debian/changelog
+++ b/debian/changelog
@@ -1,3 +1,9 @@
+golang-github-greatroar-blobloom (0.7.2-1) UNRELEASED; urgency=low
+
+ * New upstream release.
+
+ -- Debian Janitor <janitor@jelmer.uk> Wed, 14 Dec 2022 17:12:46 -0000
+
golang-github-greatroar-blobloom (0.7.1-1) unstable; urgency=medium
* New upstream release.
diff --git a/go.mod b/go.mod
index 4a0a9e1..1f614aa 100644
--- a/go.mod
+++ b/go.mod
@@ -2,4 +2,4 @@ module github.com/greatroar/blobloom
go 1.14
-require github.com/stretchr/testify v1.6.1
+require github.com/stretchr/testify v1.8.0
diff --git a/go.sum b/go.sum
index afe7890..5164829 100644
--- a/go.sum
+++ b/go.sum
@@ -1,11 +1,15 @@
-github.com/davecgh/go-spew v1.1.0 h1:ZDRjVQ15GmhC3fiQ8ni8+OwkZQO4DARzQgrnXU1Liz8=
github.com/davecgh/go-spew v1.1.0/go.mod h1:J7Y8YcW2NihsgmVo/mv3lAwl/skON4iLHjSsI+c5H38=
+github.com/davecgh/go-spew v1.1.1 h1:vj9j/u1bqnvCEfJOwUhtlOARqs3+rkHYY13jYWTU97c=
+github.com/davecgh/go-spew v1.1.1/go.mod h1:J7Y8YcW2NihsgmVo/mv3lAwl/skON4iLHjSsI+c5H38=
github.com/pmezard/go-difflib v1.0.0 h1:4DBwDE0NGyQoBHbLQYPwSUPoCMWR5BEzIk/f1lZbAQM=
github.com/pmezard/go-difflib v1.0.0/go.mod h1:iKH77koFhYxTK1pcRnkKkqfTogsbg7gZNVY4sRDYZ/4=
github.com/stretchr/objx v0.1.0/go.mod h1:HFkY916IF+rwdDfMAkV7OtwuqBVzrE8GR6GFx+wExME=
-github.com/stretchr/testify v1.6.1 h1:hDPOHmpOpP40lSULcqw7IrRb/u7w6RpDC9399XyoNd0=
-github.com/stretchr/testify v1.6.1/go.mod h1:6Fq8oRcR53rry900zMqJjRRixrwX3KX962/h/Wwjteg=
+github.com/stretchr/objx v0.4.0/go.mod h1:YvHI0jy2hoMjB+UWwv71VJQ9isScKT/TqJzVSSt89Yw=
+github.com/stretchr/testify v1.7.1/go.mod h1:6Fq8oRcR53rry900zMqJjRRixrwX3KX962/h/Wwjteg=
+github.com/stretchr/testify v1.8.0 h1:pSgiaMZlXftHpm5L7V1+rVB+AZJydKsMxsQBIJw4PKk=
+github.com/stretchr/testify v1.8.0/go.mod h1:yNjHg4UonilssWZ8iaSj1OCr/vHnekPRkoO+kdMU+MU=
gopkg.in/check.v1 v0.0.0-20161208181325-20d25e280405 h1:yhCVgyC4o1eVCa2tZl7eS0r+SDo693bJlVdllGtEeKM=
gopkg.in/check.v1 v0.0.0-20161208181325-20d25e280405/go.mod h1:Co6ibVJAznAaIkqp8huTwlJQCZ016jof/cbN4VW5Yz0=
-gopkg.in/yaml.v3 v3.0.0-20200313102051-9f266ea9e77c h1:dUUwHk2QECo/6vqA44rthZ8ie2QXMNeKRTHCNY2nXvo=
gopkg.in/yaml.v3 v3.0.0-20200313102051-9f266ea9e77c/go.mod h1:K4uyk7z7BCEPqu6E+C64Yfv1cQ7kz7rIZviUmN+EgEM=
+gopkg.in/yaml.v3 v3.0.1 h1:fxVm/GzAzEWqLHuvctI91KS9hhNmmWOoWu0XTYJS7CA=
+gopkg.in/yaml.v3 v3.0.1/go.mod h1:K4uyk7z7BCEPqu6E+C64Yfv1cQ7kz7rIZviUmN+EgEM=
diff --git a/setop_64bit.go b/setop_64bit.go
index 6d6a67e..b588038 100644
--- a/setop_64bit.go
+++ b/setop_64bit.go
@@ -1,4 +1,4 @@
-// Copyright 2020 the Blobloom authors
+// Copyright 2020-2022 the Blobloom authors
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
@@ -29,7 +29,7 @@ type block64 [BlockBits / 64]uint64
func (f *Filter) intersect(g *Filter) {
a, b := f.b, g.b
- for len(a) >= 2 {
+ for len(a) >= 2 && len(b) >= 2 {
p := (*block64)(unsafe.Pointer(&a[0]))
q := (*block64)(unsafe.Pointer(&b[0]))
@@ -57,7 +57,7 @@ func (f *Filter) intersect(g *Filter) {
a, b = a[2:], b[2:]
}
- if len(a) > 0 {
+ if len(a) > 0 && len(b) > 0 {
p := (*block64)(unsafe.Pointer(&a[0]))
q := (*block64)(unsafe.Pointer(&b[0]))
@@ -74,7 +74,7 @@ func (f *Filter) intersect(g *Filter) {
func (f *Filter) union(g *Filter) {
a, b := f.b, g.b
- for len(a) >= 2 {
+ for len(a) >= 2 && len(b) >= 2 {
p := (*block64)(unsafe.Pointer(&a[0]))
q := (*block64)(unsafe.Pointer(&b[0]))
@@ -102,7 +102,7 @@ func (f *Filter) union(g *Filter) {
a, b = a[2:], b[2:]
}
- if len(a) > 0 {
+ if len(a) > 0 && len(b) > 0 {
p := (*block64)(unsafe.Pointer(&a[0]))
q := (*block64)(unsafe.Pointer(&b[0]))
diff --git a/setop_other.go b/setop_other.go
index f5216f2..53749a2 100644
--- a/setop_other.go
+++ b/setop_other.go
@@ -1,4 +1,4 @@
-// Copyright 2020 the Blobloom authors
+// Copyright 2020-2022 the Blobloom authors
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
diff --git a/sync.go b/sync.go
index 501c807..22503ba 100644
--- a/sync.go
+++ b/sync.go
@@ -1,4 +1,4 @@
-// Copyright 2021 the Blobloom authors
+// Copyright 2021-2022 the Blobloom authors
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
@@ -43,17 +43,23 @@ type SyncFilter struct {
// single hash passed in by the client. It is silently increased to two if
// a lower value is given.
func NewSync(nbits uint64, nhashes int) *SyncFilter {
- return (*SyncFilter)(New(nbits, nhashes))
+ nbits, nhashes = fixBitsAndHashes(nbits, nhashes)
+
+ return &SyncFilter{
+ b: make([]block, nbits/BlockBits),
+ k: nhashes,
+ }
+
}
// Add insert a key with hash value h into f.
func (f *SyncFilter) Add(h uint64) {
h1, h2 := uint32(h>>32), uint32(h)
- b := (*Filter)(f).getblock(h2)
+ b := getblock(f.b, h2)
for i := 1; i < f.k; i++ {
h1, h2 = doublehash(h1, h2, i)
- b.setbitAtomic(h1)
+ setbitAtomic(b, h1)
}
}
@@ -72,7 +78,7 @@ func (f *SyncFilter) Add(h uint64) {
// before the concurrent updates started and what is returned
// after the updates complete.
func (f *SyncFilter) Cardinality() float64 {
- return (*Filter)(f).cardinality(onescountAtomic)
+ return cardinality(f.k, f.b, onescountAtomic)
}
// Empty reports whether f contains no keys.
@@ -104,11 +110,11 @@ func (f *SyncFilter) Fill() {
// It may return a false positive.
func (f *SyncFilter) Has(h uint64) bool {
h1, h2 := uint32(h>>32), uint32(h)
- b := (*Filter)(f).getblock(h2)
+ b := getblock(f.b, h2)
for i := 1; i < f.k; i++ {
h1, h2 = doublehash(h1, h2, i)
- if !b.getbitAtomic(h1) {
+ if !getbitAtomic(b, h1) {
return false
}
}
@@ -116,14 +122,14 @@ func (f *SyncFilter) Has(h uint64) bool {
}
// getbitAtomic reports whether bit (i modulo BlockBits) is set.
-func (b *block) getbitAtomic(i uint32) bool {
+func getbitAtomic(b *block, i uint32) bool {
bit := uint32(1) << (i % wordSize)
x := atomic.LoadUint32(&(*b)[(i/wordSize)%blockWords])
return x&bit != 0
}
// setbit sets bit (i modulo BlockBits) of b, atomically.
-func (b *block) setbitAtomic(i uint32) {
+func setbitAtomic(b *block, i uint32) {
bit := uint32(1) << (i % wordSize)
p := &(*b)[(i/wordSize)%blockWords]
Debdiff
File lists identical (after any substitutions)
No differences were encountered in the control files