.gitignore | 1 + client.go | 2 +- file.go | 2 +- file_test.go | 2 +- go.mod | 3 ++- go.sum | 6 ++++-- internal/request-strategy/peer.go | 2 ++ misc.go | 2 +- ordered-bitmap.go | 4 ++++ peer-impl.go | 2 +- peer.go | 2 +- peerconn.go | 2 +- piece.go | 3 +-- requesting.go | 2 +- roaring.go | 9 +++------ torrent-piece-request-order.go | 2 +- torrent.go | 2 +- typed-roaring/bitmap.go | 8 ++++++-- typed-roaring/iterator.go | 2 +- webseed-peer.go | 6 +++--- webseed/client.go | 2 +- diff --git a/.gitignore b/.gitignore index aaa3ebc23096440095c7740a83e053231ecb4ebc..296db6a902cde700cba1d87bc0d63a7b7b0acfb8 100644 --- a/.gitignore +++ b/.gitignore @@ -2,3 +2,4 @@ .idea *-run.gob .envrc* .DS_Store +/vendor \ No newline at end of file diff --git a/client.go b/client.go index c35df32fb125bb55de3955756149f228f6d1a1aa..fbc8c8264458504f389649e72298caaa36360c07 100644 --- a/client.go +++ b/client.go @@ -21,7 +21,7 @@ "slices" "strconv" "time" - "github.com/RoaringBitmap/roaring" + "github.com/RoaringBitmap/roaring/v2" "github.com/anacrolix/chansync" "github.com/anacrolix/chansync/events" "github.com/anacrolix/dht/v2" diff --git a/file.go b/file.go index be2c64ac83c9b5a985678e213b2afc598a6ecd20..abf4070441023a046d1523037636f700e623ec02 100644 --- a/file.go +++ b/file.go @@ -3,7 +3,7 @@ import ( "iter" - "github.com/RoaringBitmap/roaring" + "github.com/RoaringBitmap/roaring/v2" g "github.com/anacrolix/generics" "github.com/anacrolix/missinggo/v2/bitmap" diff --git a/file_test.go b/file_test.go index 2f57bcf46ae3d747f499598eeb1116dcb2015df7..0d594ec073f598e2802be749159810aecdda878b 100644 --- a/file_test.go +++ b/file_test.go @@ -3,7 +3,7 @@ import ( "testing" - "github.com/RoaringBitmap/roaring" + "github.com/RoaringBitmap/roaring/v2" "github.com/stretchr/testify/assert" ) diff --git a/go.mod b/go.mod index 2e23caf6398d0343d163b086ad2a023770b5aa77..3d087e2fef441d15c0a71155750e91b295f18f57 100644 --- a/go.mod +++ b/go.mod @@ -4,6 +4,7 @@ go 1.24.0 require ( github.com/RoaringBitmap/roaring v1.2.3 + github.com/RoaringBitmap/roaring/v2 v2.15.0 github.com/alexflint/go-arg v1.4.3 github.com/anacrolix/bargle v1.0.0 github.com/anacrolix/bargle/v2 v2.0.0 @@ -68,7 +69,7 @@ github.com/anacrolix/mmsg v1.0.1 // indirect github.com/anacrolix/stm v0.5.0 // indirect github.com/benbjohnson/immutable v0.4.1-0.20221220213129-8932b999621d // indirect github.com/beorn7/perks v1.0.1 // indirect - github.com/bits-and-blooms/bitset v1.2.2 // indirect + github.com/bits-and-blooms/bitset v1.24.2 // indirect github.com/cenkalti/backoff/v5 v5.0.3 // indirect github.com/cespare/xxhash/v2 v2.3.0 // indirect github.com/ebitengine/purego v0.9.1 // indirect diff --git a/go.sum b/go.sum index 26244c13ea0a410b6627b282ef77e41bb704c0f8..5ea651437b9feb9040c5e43894a5d100b3b8d59e 100644 --- a/go.sum +++ b/go.sum @@ -44,6 +44,8 @@ github.com/RoaringBitmap/roaring v0.4.17/go.mod h1:D3qVegWTmfCaX4Bl5CrBE9hfrSrrXIr8KVNvRsDi1NI= github.com/RoaringBitmap/roaring v0.4.23/go.mod h1:D0gp8kJQgE1A4LQ5wFLggQEyvDi06Mq5mKs52e1TwOo= github.com/RoaringBitmap/roaring v1.2.3 h1:yqreLINqIrX22ErkKI0vY47/ivtJr6n+kMhVOVmhWBY= github.com/RoaringBitmap/roaring v1.2.3/go.mod h1:plvDsJQpxOC5bw8LRteu/MLWHsHez/3y6cubLI4/1yE= +github.com/RoaringBitmap/roaring/v2 v2.15.0 h1:gCbixa3UiG7g6WUZNVOfEEg2HTc1vR4OVdMkX8t1ZFc= +github.com/RoaringBitmap/roaring/v2 v2.15.0/go.mod h1:eq4wdNXxtJIS/oikeCzdX1rBzek7ANzbth041hrU8Q4= github.com/Shopify/sarama v1.19.0/go.mod h1:FVkBWblsNy7DGZRfXLU0O9RCGt5g3g3yEuWXgklEdEo= github.com/Shopify/toxiproxy v2.1.4+incompatible/go.mod h1:OXgGpZ6Cli1/URJOF1DMxUHB2q5Ap20/P/eIdh4G0pI= github.com/ajwerner/btree v0.0.0-20211221152037-f427b3e689c0 h1:byYvvbfSo3+9efR4IeReh77gVs4PnNDR3AMOE9NJ7a0= @@ -143,8 +145,8 @@ github.com/beorn7/perks v1.0.0/go.mod h1:KWe93zE9D1o94FZ5RNwFwVgaQK1VOXiVxmqh+CedLV8= github.com/beorn7/perks v1.0.1 h1:VlbKKnNfV8bJzeqoa4cOKqO6bYr3WgKZxO8Z16+hsOM= github.com/beorn7/perks v1.0.1/go.mod h1:G2ZrVWU2WbWT9wwq4/hrbKbnv/1ERSJQ0ibhJ6rlkpw= 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/bits-and-blooms/bitset v1.24.2 h1:M7/NzVbsytmtfHbumG+K2bremQPMJuqv1JD3vOaFxp0= +github.com/bits-and-blooms/bitset v1.24.2/go.mod h1:7hO7Gc7Pp1vODcmWvKMRA9BNmbv6a/7QIWpPxHddWR8= github.com/bradfitz/iter v0.0.0-20140124041915-454541ec3da2/go.mod h1:PyRFw1Lt2wKX4ZVSQ2mk+PeDa1rxyObEDlApuIsUKuo= github.com/bradfitz/iter v0.0.0-20190303215204-33e6a9893b0c/go.mod h1:PyRFw1Lt2wKX4ZVSQ2mk+PeDa1rxyObEDlApuIsUKuo= github.com/bradfitz/iter v0.0.0-20191230175014-e8f45d346db8 h1:GKTyiRCL6zVf5wWaqKnf+7Qs6GbEPfd4iMOitWzXJx8= diff --git a/internal/request-strategy/peer.go b/internal/request-strategy/peer.go index 1eea0329ebf6148916da7e41c169112f409c59f5..72b0972465dadfc4435cbbd6be32e1cf9e741e80 100644 --- a/internal/request-strategy/peer.go +++ b/internal/request-strategy/peer.go @@ -33,4 +33,6 @@ // See roaring.Bitmap.CheckedRemove. CheckedRemove(RequestIndex) bool // Iterate a snapshot of the values. It is safe to mutate the underlying data structure. IterateSnapshot(func(RequestIndex) bool) + + RangeCardinality(start, end RequestIndex) uint64 } diff --git a/misc.go b/misc.go index 511d6d3e6dd223526db62a0e64954a4f8b684f7f..94b3187bb2d8cf95ef3cf9e895905798bf1424e5 100644 --- a/misc.go +++ b/misc.go @@ -4,7 +4,7 @@ import ( "errors" "net" - "github.com/RoaringBitmap/roaring" + "github.com/RoaringBitmap/roaring/v2" "github.com/anacrolix/missinggo/v2" "github.com/anacrolix/missinggo/v2/panicif" "golang.org/x/time/rate" diff --git a/ordered-bitmap.go b/ordered-bitmap.go index 849a1380b2f6e59e36f096b33c83224ddadbfe0a..f304f97c716f71f6f74a9c92d4b7502f30904ff8 100644 --- a/ordered-bitmap.go +++ b/ordered-bitmap.go @@ -72,3 +72,7 @@ o.order.Remove(o.elements[index]) delete(o.elements, index) return true } + +func (o *orderedBitmap[T]) RangeCardinality(start, end T) uint64 { + return o.bitmap.RangeCardinality(start, end) +} \ No newline at end of file diff --git a/peer-impl.go b/peer-impl.go index 25fe5a72b9591e5ca09938146ef01c9b352ac277..cb31a817f067e3945a4a28880df985a50d1d5549 100644 --- a/peer-impl.go +++ b/peer-impl.go @@ -3,7 +3,7 @@ import ( "io" - "github.com/RoaringBitmap/roaring" + "github.com/RoaringBitmap/roaring/v2" "github.com/anacrolix/torrent/metainfo" pp "github.com/anacrolix/torrent/peer_protocol" diff --git a/peer.go b/peer.go index 0902938f95118c7360b402209d6bca527866708b..9a5ae4fd3bd11030e644a586daf49107aa6bc2ab 100644 --- a/peer.go +++ b/peer.go @@ -11,7 +11,7 @@ "strings" "sync" "time" - "github.com/RoaringBitmap/roaring" + "github.com/RoaringBitmap/roaring/v2" "github.com/anacrolix/chansync" g "github.com/anacrolix/generics" "github.com/anacrolix/log" diff --git a/peerconn.go b/peerconn.go index 9444428ecab9cebf5c7262f6127b4af64fb42f3f..d7418edbdf152981b550f6d6625c0336dcb0abd6 100644 --- a/peerconn.go +++ b/peerconn.go @@ -16,7 +16,7 @@ "sync/atomic" "time" "weak" - "github.com/RoaringBitmap/roaring" + "github.com/RoaringBitmap/roaring/v2" "github.com/anacrolix/chansync" g "github.com/anacrolix/generics" "github.com/anacrolix/log" diff --git a/piece.go b/piece.go index bab0dd7b70778b240994f214da18c34bc8ba9594..1252e205ecf3ba6b92a6f32c34f482362af1cc2a 100644 --- a/piece.go +++ b/piece.go @@ -7,7 +7,7 @@ "fmt" "iter" "sync" - "github.com/RoaringBitmap/roaring" + "github.com/RoaringBitmap/roaring/v2" "github.com/anacrolix/chansync" g "github.com/anacrolix/generics" "github.com/anacrolix/missinggo/v2/bitmap" @@ -462,4 +462,3 @@ cur, }) } } - diff --git a/requesting.go b/requesting.go index 155f597ba983e9392278ea19878612c295750743..b903739dbead5d8296945a8e01dad57f8f036b1b 100644 --- a/requesting.go +++ b/requesting.go @@ -10,7 +10,7 @@ "runtime/pprof" "time" "unsafe" - "github.com/RoaringBitmap/roaring" + "github.com/RoaringBitmap/roaring/v2" g "github.com/anacrolix/generics" "github.com/anacrolix/generics/heap" "github.com/anacrolix/multiless" diff --git a/roaring.go b/roaring.go index f8e622b1163072364650d041598aa2eb39a1348a..e75ba99560787cf4c6e637132142104a9e7f3211 100644 --- a/roaring.go +++ b/roaring.go @@ -5,10 +5,7 @@ // Return the number of bits set in the range. To do this we need the rank of the item before the // first, and the rank of the last item. An off-by-one minefield. Hopefully I haven't missed // something in roaring's API that provides this. -func roaringBitmapRangeCardinality[T typedRoaring.BitConstraint](bm interface{ Rank(T) uint64 }, start, end T) (card uint64) { - card = bm.Rank(end - 1) - if start != 0 { - card -= bm.Rank(start - 1) - } +func roaringBitmapRangeCardinality[T typedRoaring.BitConstraint](bm interface{ RangeCardinality(T, T) uint64 }, start, end T) (card uint64) { + card = bm.RangeCardinality(start, end) return -} +} diff --git a/torrent-piece-request-order.go b/torrent-piece-request-order.go index cedc919d4f6933d6d4dc7bf28e401b64b9043b91..f3b8da98fe59ce9cae669aba9676927f2f755de3 100644 --- a/torrent-piece-request-order.go +++ b/torrent-piece-request-order.go @@ -3,7 +3,7 @@ import ( "fmt" - "github.com/RoaringBitmap/roaring" + "github.com/RoaringBitmap/roaring/v2" g "github.com/anacrolix/generics" "github.com/anacrolix/torrent/internal/amortize" requestStrategy "github.com/anacrolix/torrent/internal/request-strategy" diff --git a/torrent.go b/torrent.go index 76b164e0cad137945dae461e09b455dc783f9368..73ef35eafbf1f426b22add23e847260c19e26d21 100644 --- a/torrent.go +++ b/torrent.go @@ -25,7 +25,7 @@ "unique" "unsafe" "weak" - "github.com/RoaringBitmap/roaring" + "github.com/RoaringBitmap/roaring/v2" "github.com/anacrolix/chansync" "github.com/anacrolix/chansync/events" "github.com/anacrolix/dht/v2" diff --git a/typed-roaring/bitmap.go b/typed-roaring/bitmap.go index d61ffe4864b4af24d5a5d016d2a7fc9461262fe8..2ce01f9e5288a5a0b6d865fa53e3c40972cce1b3 100644 --- a/typed-roaring/bitmap.go +++ b/typed-roaring/bitmap.go @@ -1,12 +1,12 @@ package typedRoaring import ( - "github.com/RoaringBitmap/roaring" + roaringv2 "github.com/RoaringBitmap/roaring/v2" ) // TODO: Update to roaring v2 or higher type Bitmap[T BitConstraint] struct { - roaring.Bitmap + roaringv2.Bitmap } func (me *Bitmap[T]) Contains(x T) bool { @@ -46,6 +46,10 @@ // Returns an uninitialized iterator for the type of the receiver. func (Bitmap[T]) IteratorType() Iterator[T] { return Iterator[T]{} +} + +func (me Bitmap[T]) RangeCardinality(start, end T) uint64 { + return me.Bitmap.CardinalityInRange(uint64(start), uint64(end)) } // TODO: Override Bitmap.Iterator. diff --git a/typed-roaring/iterator.go b/typed-roaring/iterator.go index 8766db1750d6aa8d8fb86b67a3d4e96d206c6f90..ab55c4eed34b7aab19b0e5f5c6465441d7e32df1 100644 --- a/typed-roaring/iterator.go +++ b/typed-roaring/iterator.go @@ -1,7 +1,7 @@ package typedRoaring import ( - "github.com/RoaringBitmap/roaring" + "github.com/RoaringBitmap/roaring/v2" ) type Iterator[T BitConstraint] struct { diff --git a/webseed-peer.go b/webseed-peer.go index 0acd585f98d09a699155812423a3bfc10a4524b7..222679fde18ccf71ce01859d40fe38637b91829f 100644 --- a/webseed-peer.go +++ b/webseed-peer.go @@ -14,7 +14,7 @@ "sync" "syscall" "time" - "github.com/RoaringBitmap/roaring" + "github.com/RoaringBitmap/roaring/v2" g "github.com/anacrolix/generics" "github.com/anacrolix/missinggo/v2/panicif" "golang.org/x/net/http2" @@ -26,8 +26,8 @@ ) type webseedPeer struct { // First field for stats alignment. - peer Peer - client webseed.Client + peer Peer + client webseed.Client activeRequests map[*webseedRequest]struct{} locker sync.Locker hostKey webseedHostKeyHandle diff --git a/webseed/client.go b/webseed/client.go index accfb273b4b11ee0280109b978d2874ff7240866..4f7c32206775fa78ae08cbf62d7f13827915f2c3 100644 --- a/webseed/client.go +++ b/webseed/client.go @@ -12,7 +12,7 @@ "runtime/pprof" "strings" "sync" - "github.com/RoaringBitmap/roaring" + "github.com/RoaringBitmap/roaring/v2" g "github.com/anacrolix/generics" "github.com/anacrolix/missinggo/v2/panicif" "github.com/dustin/go-humanize"