diff options
author | gluk256 <gluk256@users.noreply.github.com> | 2019-01-12 03:42:33 +0800 |
---|---|---|
committer | Viktor TrĂ³n <viktor.tron@gmail.com> | 2019-01-12 03:42:33 +0800 |
commit | 1636d9574be4e3df318f16bd1bf2741cf79b76a1 (patch) | |
tree | f3fb5986f98a1a149a65da93c9f9ddfff001f5fa | |
parent | 88168ff5c57b1a9c944d02e93e6e49368ccc968f (diff) | |
download | dexon-1636d9574be4e3df318f16bd1bf2741cf79b76a1.tar dexon-1636d9574be4e3df318f16bd1bf2741cf79b76a1.tar.gz dexon-1636d9574be4e3df318f16bd1bf2741cf79b76a1.tar.bz2 dexon-1636d9574be4e3df318f16bd1bf2741cf79b76a1.tar.lz dexon-1636d9574be4e3df318f16bd1bf2741cf79b76a1.tar.xz dexon-1636d9574be4e3df318f16bd1bf2741cf79b76a1.tar.zst dexon-1636d9574be4e3df318f16bd1bf2741cf79b76a1.zip |
swarm/pot: pot.remove fixed (#18431)
* swarm/pot: refactored pot.remove(), updated comments
* swarm/pot: comments updated
-rw-r--r-- | swarm/pot/address.go | 4 | ||||
-rw-r--r-- | swarm/pot/pot.go | 18 | ||||
-rw-r--r-- | swarm/pot/pot_test.go | 84 |
3 files changed, 86 insertions, 20 deletions
diff --git a/swarm/pot/address.go b/swarm/pot/address.go index 5af3381a7..91cada2e8 100644 --- a/swarm/pot/address.go +++ b/swarm/pot/address.go @@ -162,7 +162,6 @@ func ToBytes(v Val) []byte { } // DefaultPof returns a proximity order comparison operator function -// where all func DefaultPof(max int) func(one, other Val, pos int) (int, bool) { return func(one, other Val, pos int) (int, bool) { po, eq := proximityOrder(ToBytes(one), ToBytes(other), pos) @@ -174,6 +173,9 @@ func DefaultPof(max int) func(one, other Val, pos int) (int, bool) { } } +// proximityOrder returns two parameters: +// 1. relative proximity order of the arguments one & other; +// 2. boolean indicating whether the full match occurred (one == other). func proximityOrder(one, other []byte, pos int) (int, bool) { for i := pos / 8; i < len(one); i++ { if one[i] == other[i] { diff --git a/swarm/pot/pot.go b/swarm/pot/pot.go index a71219779..0797b286c 100644 --- a/swarm/pot/pot.go +++ b/swarm/pot/pot.go @@ -144,13 +144,10 @@ func add(t *Pot, val Val, pof Pof) (*Pot, int, bool) { return r, po, found } -// Remove called on (v) deletes v from the Pot and returns -// the proximity order of v and a boolean value indicating -// if the value was found -// Remove called on (t, v) returns a new Pot that contains all the elements of t -// minus the value v, using the applicative remove -// the second return value is the proximity order of the inserted element -// the third is boolean indicating if the item was found +// Remove deletes element v from the Pot t and returns three parameters: +// 1. new Pot that contains all the elements of t minus the element v; +// 2. proximity order of the removed element v; +// 3. boolean indicating whether the item was found. func Remove(t *Pot, v Val, pof Pof) (*Pot, int, bool) { return remove(t, v, pof) } @@ -161,10 +158,7 @@ func remove(t *Pot, val Val, pof Pof) (r *Pot, po int, found bool) { if found { size-- if size == 0 { - r = &Pot{ - po: t.po, - } - return r, po, true + return &Pot{}, po, true } i := len(t.bins) - 1 last := t.bins[i] @@ -201,7 +195,7 @@ func remove(t *Pot, val Val, pof Pof) (r *Pot, po int, found bool) { } bins = append(bins, t.bins[j:]...) r = &Pot{ - pin: val, + pin: t.pin, size: size, po: t.po, bins: bins, diff --git a/swarm/pot/pot_test.go b/swarm/pot/pot_test.go index aeb23dfc6..8c7daebe0 100644 --- a/swarm/pot/pot_test.go +++ b/swarm/pot/pot_test.go @@ -82,6 +82,72 @@ func testAdd(t *Pot, pof Pof, j int, values ...string) (_ *Pot, n int, f bool) { return t, n, f } +// removing non-existing element from pot +func TestPotRemoveNonExisting(t *testing.T) { + pof := DefaultPof(8) + n := NewPot(newTestAddr("00111100", 0), 0) + n, _, _ = Remove(n, newTestAddr("00000101", 0), pof) + exp := "00111100" + got := Label(n.Pin()) + if got[:8] != exp { + t.Fatalf("incorrect pinned value. Expected %v, got %v", exp, got[:8]) + } +} + +// this test creates hierarchical pot tree, and therefore any child node will have +// child_po = parent_po + 1. +// then removes a node from the middle of the tree. +func TestPotRemoveSameBin(t *testing.T) { + pof := DefaultPof(8) + n := NewPot(newTestAddr("11111111", 0), 0) + n, _, _ = testAdd(n, pof, 1, "00000000", "01000000", "01100000", "01110000", "01111000") + n, _, _ = Remove(n, newTestAddr("01110000", 0), pof) + inds, po := indexes(n) + goti := n.Size() + expi := 5 + if goti != expi { + t.Fatalf("incorrect number of elements in Pot. Expected %v, got %v", expi, goti) + } + inds, po = indexes(n) + got := fmt.Sprintf("%v", inds) + exp := "[5 3 2 1 0]" + if got != exp { + t.Fatalf("incorrect indexes in iteration over Pot. Expected %v, got %v", exp, got) + } + got = fmt.Sprintf("%v", po) + exp = "[3 2 1 0 0]" + if got != exp { + t.Fatalf("incorrect po-s in iteration over Pot. Expected %v, got %v", exp, got) + } +} + +// this test creates a flat pot tree (all the elements are leafs of one root), +// and therefore they all have the same po. +// then removes an arbitrary element from the pot. +func TestPotRemoveDifferentBins(t *testing.T) { + pof := DefaultPof(8) + n := NewPot(newTestAddr("11111111", 0), 0) + n, _, _ = testAdd(n, pof, 1, "00000000", "10000000", "11000000", "11100000", "11110000") + n, _, _ = Remove(n, newTestAddr("11100000", 0), pof) + inds, po := indexes(n) + goti := n.Size() + expi := 5 + if goti != expi { + t.Fatalf("incorrect number of elements in Pot. Expected %v, got %v", expi, goti) + } + inds, po = indexes(n) + got := fmt.Sprintf("%v", inds) + exp := "[1 2 3 5 0]" + if got != exp { + t.Fatalf("incorrect indexes in iteration over Pot. Expected %v, got %v", exp, got) + } + got = fmt.Sprintf("%v", po) + exp = "[0 1 2 4 0]" + if got != exp { + t.Fatalf("incorrect po-s in iteration over Pot. Expected %v, got %v", exp, got) + } +} + func TestPotAdd(t *testing.T) { pof := DefaultPof(8) n := NewPot(newTestAddr("00111100", 0), 0) @@ -135,25 +201,29 @@ func TestPotRemove(t *testing.T) { t.Fatalf("incorrect number of elements in Pot. Expected %v, got %v", expi, goti) } inds, po := indexes(n) + got = fmt.Sprintf("%v", po) + exp = "[1 3 0]" + if got != exp { + t.Fatalf("incorrect po-s in iteration over Pot. Expected %v, got %v", exp, got) + } got = fmt.Sprintf("%v", inds) - exp = "[2 4 0]" + exp = "[2 4 1]" if got != exp { t.Fatalf("incorrect indexes in iteration over Pot. Expected %v, got %v", exp, got) } - got = fmt.Sprintf("%v", po) - exp = "[1 3 0]" + n, _, _ = Remove(n, newTestAddr("00111100", 0), pof) // remove again same element + inds, _ = indexes(n) + got = fmt.Sprintf("%v", inds) if got != exp { - t.Fatalf("incorrect po-s in iteration over Pot. Expected %v, got %v", exp, got) + t.Fatalf("incorrect indexes in iteration over Pot. Expected %v, got %v", exp, got) } - // remove again - n, _, _ = Remove(n, newTestAddr("00111100", 0), pof) + n, _, _ = Remove(n, newTestAddr("00000000", 0), pof) // remove the first element inds, _ = indexes(n) got = fmt.Sprintf("%v", inds) exp = "[2 4]" if got != exp { t.Fatalf("incorrect indexes in iteration over Pot. Expected %v, got %v", exp, got) } - } func TestPotSwap(t *testing.T) { |