"testing"
"time"
- "github.com/stretchr/testify/assert"
-
- "github.com/anacrolix/torrent/internal/pieceordering"
"github.com/anacrolix/torrent/peer_protocol"
)
}
}
}
-
-func pieceOrderingAsSlice(po *pieceordering.Instance) (ret []int) {
- for e := po.First(); e != nil; e = e.Next() {
- ret = append(ret, e.Piece())
- }
- return
-}
-
-func testRequestOrder(expected []int, ro *pieceordering.Instance, t *testing.T) {
- assert.EqualValues(t, pieceOrderingAsSlice(ro), expected)
-}
+++ /dev/null
-// Implements ordering of torrent piece indices for such purposes as download
-// prioritization.
-package pieceordering
-
-import (
- "math/rand"
-
- "github.com/ryszard/goskiplist/skiplist"
-)
-
-// Maintains piece integers by their ascending assigned keys.
-type Instance struct {
- // Contains the ascending priority keys. The keys contain a slice of piece
- // indices.
- sl *skiplist.SkipList
- // Maps from piece index back to its key, so that it can be remove
- // efficiently from the skip list.
- pieceKeys map[int]int
-}
-
-func New() *Instance {
- return &Instance{
- sl: skiplist.NewIntMap(),
- }
-}
-
-// Add the piece with the given key. If the piece is already present, change
-// its key.
-func (me *Instance) SetPiece(piece, key int) {
- if existingKey, ok := me.pieceKeys[piece]; ok {
- if existingKey == key {
- return
- }
- me.removeKeyPiece(existingKey, piece)
- }
- var itemSl []int
- if exItem, ok := me.sl.Get(key); ok {
- itemSl = exItem.([]int)
- }
- me.sl.Set(key, append(itemSl, piece))
- if me.pieceKeys == nil {
- me.pieceKeys = make(map[int]int)
- }
- me.pieceKeys[piece] = key
- me.shuffleItem(key)
-}
-
-// Shuffle the piece indices that share a given key.
-func (me *Instance) shuffleItem(key int) {
- _item, ok := me.sl.Get(key)
- if !ok {
- return
- }
- item := _item.([]int)
- for i := range item {
- j := i + rand.Intn(len(item)-i)
- item[i], item[j] = item[j], item[i]
- }
- me.sl.Set(key, item)
-}
-
-func (me *Instance) removeKeyPiece(key, piece int) {
- item, ok := me.sl.Get(key)
- if !ok {
- panic("no item for key")
- }
- itemSl := item.([]int)
- for i, piece1 := range itemSl {
- if piece1 == piece {
- itemSl[i] = itemSl[len(itemSl)-1]
- itemSl = itemSl[:len(itemSl)-1]
- break
- }
- }
- if len(itemSl) == 0 {
- me.sl.Delete(key)
- } else {
- me.sl.Set(key, itemSl)
- }
-}
-
-func (me *Instance) DeletePiece(piece int) {
- key, ok := me.pieceKeys[piece]
- if !ok {
- return
- }
- me.removeKeyPiece(key, piece)
- delete(me.pieceKeys, piece)
-}
-
-// Returns the piece with the lowest key.
-func (me *Instance) First() Element {
- i := me.sl.SeekToFirst()
- if i == nil {
- return nil
- }
- return &element{i, i.Value().([]int)}
-}
-
-func (me *Instance) Empty() bool {
- return me.sl.Len() == 0
-}
-
-type Element interface {
- Piece() int
- Next() Element
-}
-
-type element struct {
- i skiplist.Iterator
- sl []int
-}
-
-func (e *element) Next() Element {
- e.sl = e.sl[1:]
- if len(e.sl) > 0 {
- return e
- }
- ok := e.i.Next()
- if !ok {
- return nil
- }
- e.sl = e.i.Value().([]int)
- return e
-}
-
-func (e *element) Piece() int {
- return e.sl[0]
-}
+++ /dev/null
-package pieceordering
-
-import (
- "sort"
- "testing"
-
- "github.com/bradfitz/iter"
- "github.com/stretchr/testify/assert"
-)
-
-func instanceSlice(i *Instance) (sl []int) {
- for e := i.First(); e != nil; e = e.Next() {
- sl = append(sl, e.Piece())
- }
- return
-}
-
-func sameContents(a, b []int) bool {
- if len(a) != len(b) {
- panic("y u pass different length slices")
- }
- sort.IntSlice(a).Sort()
- sort.IntSlice(b).Sort()
- for i := range a {
- if a[i] != b[i] {
- return false
- }
- }
- return true
-}
-
-func checkOrder(t testing.TB, i *Instance, ppp ...[]int) {
- fatal := func() {
- t.Fatalf("have %v, expected %v", instanceSlice(i), ppp)
- }
- e := i.First()
- for _, pp := range ppp {
- var pp_ []int
- for len(pp_) != len(pp) {
- pp_ = append(pp_, e.Piece())
- e = e.Next()
- }
- if !sameContents(pp, pp_) {
- fatal()
- }
- }
- if e != nil {
- fatal()
- }
-}
-
-func testPieceOrdering(t testing.TB) {
- i := New()
- assert.True(t, i.Empty())
- i.SetPiece(0, 1)
- assert.False(t, i.Empty())
- i.SetPiece(1, 0)
- checkOrder(t, i, []int{1, 0})
- i.SetPiece(1, 2)
- checkOrder(t, i, []int{0, 1})
- i.DeletePiece(1)
- checkOrder(t, i, []int{0})
- i.DeletePiece(2)
- i.DeletePiece(1)
- checkOrder(t, i, []int{0})
- i.DeletePiece(0)
- assert.True(t, i.Empty())
- checkOrder(t, i, nil)
- i.SetPiece(2, 1)
- assert.False(t, i.Empty())
- i.SetPiece(1, 1)
- i.SetPiece(3, 1)
- checkOrder(t, i, []int{3, 1, 2})
- // Move a piece that isn't the youngest in a key.
- i.SetPiece(1, -1)
- checkOrder(t, i, []int{1}, []int{3, 2})
- i.DeletePiece(2)
- i.DeletePiece(3)
- i.DeletePiece(1)
- assert.True(t, i.Empty())
- checkOrder(t, i, nil)
- // Deleting pieces that aren't present.
- i.DeletePiece(2)
- i.DeletePiece(3)
- i.DeletePiece(1)
- assert.True(t, i.Empty())
- checkOrder(t, i, nil)
-}
-
-func TestPieceOrdering(t *testing.T) {
- testPieceOrdering(t)
-}
-
-func BenchmarkPieceOrdering(b *testing.B) {
- for range iter.N(b.N) {
- testPieceOrdering(b)
- }
-}
-
-func BenchmarkIteration(b *testing.B) {
- for range iter.N(b.N) {
- i := New()
- for p := range iter.N(500) {
- i.SetPiece(p, p)
- }
- for e := i.First(); e != nil; e = e.Next() {
- }
- }
-}