sequence window without advance...

2 files changed, 91 insertions, 18 deletions

diff --git a/satp/sequence-window.go b/satp/sequence-window.go
index c527f4e..f529231 100644
--- a/satp/sequence-window.go
+++ b/satp/sequence-window.go
@@ -49,10 +49,12 @@ func seqDistance(top, seq uint32) (less bool, distance uint32) {
 // aka: top >= seq && (top-seq) <= window_size
 //        (with both conditions compensated for value wrap around)
 func bitSliceIndex(top, seq uint32) int {
-	if top > seq {
-		return int(top/32) - int(seq/32)
+	idxTop := int(top / 32)
+	idxSeq := int(seq / 32)
+	if idxTop >= idxSeq {
+		return idxTop - idxSeq
 	}
-	return int(top/32) + int(1<<(32-5)) - int(seq/32)
+	return idxTop + int(1<<(32-5)) - idxSeq
 }
 
 type SequenceWindow struct {
@@ -107,6 +109,39 @@ func (w *SequenceWindow) bitSlice(idx int) uint32 {
 	return w.body[idx-1]
 }
 
+func (w *SequenceWindow) check(sequenceNumber uint32) bool {
+	idx := bitSliceIndex(w.top(), sequenceNumber)
+	bit := int(sequenceNumber % 32)
+	return ((w.bitSlice(idx) >> uint(bit)) & 1) == 0
+}
+
+func (w *SequenceWindow) checkAndSet(sequenceNumber uint32) bool {
+	idx := bitSliceIndex(w.top(), sequenceNumber)
+	bit := int(sequenceNumber % 32)
+
+	// TODO: use atomic.CompareAndSwap and loop
+
+	oldSlice := w.bitSlice(idx)
+	newSlice := oldSlice | 1<<uint(bit)
+	if oldSlice == newSlice {
+		return false
+	}
+	if idx <= 0 {
+		newTop := w.top()
+		if sequenceNumber >= newTop {
+			newTop = sequenceNumber + 1
+		}
+		w.head = uint64(newTop)<<32 | uint64(newSlice)
+	} else {
+		w.body[idx-1] = newSlice
+	}
+	return true
+}
+
+func (w *SequenceWindow) advanceTop(newTop uint32) {
+	// TODO: implement this
+}
+
 func (w *SequenceWindow) top() uint32 {
 	// return uint32(atomic.LoadUint64(&w.head) >> 32)
 	return uint32(w.head >> 32)
@@ -125,30 +160,36 @@ func (w *SequenceWindow) Check(sequenceNumber uint32) bool {
 	w.mtx.RLock()
 	defer w.mtx.RUnlock()
 
-	top := w.top()
-	lt, d := seqDistance(top, sequenceNumber)
+	lt, d := seqDistance(w.top(), sequenceNumber)
 	if lt {
 		if d > uint32(w.size) {
 			return false
 		}
-		bits := w.bitSlice(bitSliceIndex(top, sequenceNumber))
-		return ((bits >> (sequenceNumber % 32)) & 1) != 1
+		return w.check(sequenceNumber)
 	}
 	return true
 }
 
-// func (w *SequenceWindow) advanceTop(sequenceNumber uint32) {
-// }
+func (w *SequenceWindow) CheckAndSet(sequenceNumber uint32) bool {
+	if w.size <= 0 {
+		return true
+	}
+	w.mtx.Lock()
+	defer w.mtx.Unlock()
+
+	top := w.top()
+	lt, d := seqDistance(top, sequenceNumber)
+	if lt && d > uint32(w.size) {
+		return false
+	}
+	if lt || top/32 == sequenceNumber/32 {
+		return w.checkAndSet(sequenceNumber)
+	}
 
-// func (w *SequenceWindow) CheckAndSet(sequenceNumber uint32) bool {
-// 	if w.size <= 0 {
-// 		return true
-// 	}
-// 	w.mtx.Lock()
-// 	defer w.mtx.Unlock()
-// 	// TODO: implement this
-// 	return false
-// }
+	// TODO: only now we would need the writers lock
+	w.advanceTop(sequenceNumber + 1)
+	return w.checkAndSet(sequenceNumber)
+}
 
 func NewSequenceWindow(size int, top uint32) (w *SequenceWindow, err error) {
 	if size < 0 || size > int(^uint32(0)/4) {
diff --git a/satp/sequence-window_test.go b/satp/sequence-window_test.go
index 097cacd..91211cd 100644
--- a/satp/sequence-window_test.go
+++ b/satp/sequence-window_test.go
@@ -186,3 +186,35 @@ func TestSequenceWindowCheck(t *testing.T) {
 		}
 	}
 }
+
+func TestSequenceWindowCheckAndSet(t *testing.T) {
+	testvectors := []struct {
+		size   int
+		top    uint32
+		seqs   []uint32
+		result bool
+	}{
+		{0, 0, []uint32{0, 1, 2, 3, 4}, true},
+		{0, 0, []uint32{^uint32(0)}, true},
+		{10, 0, []uint32{^uint32(0)}, false},
+		{10, 20, []uint32{^uint32(0), 5, 9, 10}, false},
+		{32, 0, []uint32{0, 1, 2, 3, 4}, true},
+		{32, 10, []uint32{0, 1, 2, 3, 4}, false},
+		{32, 10, []uint32{10, 11, 12, 13, 14}, true},
+		{32, 0, []uint32{10, 17, 23, 0, 1, 18, 9, 8, 31}, true},
+	}
+
+	for _, vector := range testvectors {
+		w, err := NewSequenceWindow(vector.size, vector.top)
+		if err != nil {
+			t.Fatal("unexpected error:", err)
+		}
+		for _, seq := range vector.seqs {
+			result := w.CheckAndSet(seq)
+			if result != vector.result {
+				t.Fatalf("check-and-set %d on %s returned %v but should be %v", seq, w, result, vector.result)
+			}
+			t.Log(w)
+		}
+	}
+}