← Back to branch summary

~john-koepi/ubuntu/trusty/golang/default

« back to all changes in this revision

Viewing changes to src/pkg/container/ring/ring_test.go

  • Committer: Bazaar Package Importer
  • Author(s): Ondřej Surý
  • Date: 2011-04-20 17:36:48 UTC
  • Revision ID: james.westby@ubuntu.com-20110420173648-ifergoxyrm832trd
Tags: upstream-2011.03.07.1
Import upstream version 2011.03.07.1

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/pkg/container/ring/ring_test.go
 
1
// Copyright 2009 The Go Authors. All rights reserved.
 
2
// Use of this source code is governed by a BSD-style
 
3
// license that can be found in the LICENSE file.
 
4
 
 
5
package ring
 
6
 
 
7
import (
 
8
        "fmt"
 
9
        "testing"
 
10
)
 
11
 
 
12
 
 
13
// For debugging - keep around.
 
14
func dump(r *Ring) {
 
15
        if r == nil {
 
16
                fmt.Println("empty")
 
17
                return
 
18
        }
 
19
        i, n := 0, r.Len()
 
20
        for p := r; i < n; p = p.next {
 
21
                fmt.Printf("%4d: %p = {<- %p | %p ->}\n", i, p, p.prev, p.next)
 
22
                i++
 
23
        }
 
24
        fmt.Println()
 
25
}
 
26
 
 
27
 
 
28
func verify(t *testing.T, r *Ring, N int, sum int) {
 
29
        // Len
 
30
        n := r.Len()
 
31
        if n != N {
 
32
                t.Errorf("r.Len() == %d; expected %d", n, N)
 
33
        }
 
34
 
 
35
        // iteration
 
36
        n = 0
 
37
        s := 0
 
38
        r.Do(func(p interface{}) {
 
39
                n++
 
40
                if p != nil {
 
41
                        s += p.(int)
 
42
                }
 
43
        })
 
44
        if n != N {
 
45
                t.Errorf("number of forward iterations == %d; expected %d", n, N)
 
46
        }
 
47
        if sum >= 0 && s != sum {
 
48
                t.Errorf("forward ring sum = %d; expected %d", s, sum)
 
49
        }
 
50
 
 
51
        if r == nil {
 
52
                return
 
53
        }
 
54
 
 
55
        // connections
 
56
        if r.next != nil {
 
57
                var p *Ring // previous element
 
58
                for q := r; p == nil || q != r; q = q.next {
 
59
                        if p != nil && p != q.prev {
 
60
                                t.Errorf("prev = %p, expected q.prev = %p\n", p, q.prev)
 
61
                        }
 
62
                        p = q
 
63
                }
 
64
                if p != r.prev {
 
65
                        t.Errorf("prev = %p, expected r.prev = %p\n", p, r.prev)
 
66
                }
 
67
        }
 
68
 
 
69
        // Next, Prev
 
70
        if r.Next() != r.next {
 
71
                t.Errorf("r.Next() != r.next")
 
72
        }
 
73
        if r.Prev() != r.prev {
 
74
                t.Errorf("r.Prev() != r.prev")
 
75
        }
 
76
 
 
77
        // Move
 
78
        if r.Move(0) != r {
 
79
                t.Errorf("r.Move(0) != r")
 
80
        }
 
81
        if r.Move(N) != r {
 
82
                t.Errorf("r.Move(%d) != r", N)
 
83
        }
 
84
        if r.Move(-N) != r {
 
85
                t.Errorf("r.Move(%d) != r", -N)
 
86
        }
 
87
        for i := 0; i < 10; i++ {
 
88
                ni := N + i
 
89
                mi := ni % N
 
90
                if r.Move(ni) != r.Move(mi) {
 
91
                        t.Errorf("r.Move(%d) != r.Move(%d)", ni, mi)
 
92
                }
 
93
                if r.Move(-ni) != r.Move(-mi) {
 
94
                        t.Errorf("r.Move(%d) != r.Move(%d)", -ni, -mi)
 
95
                }
 
96
        }
 
97
}
 
98
 
 
99
 
 
100
func TestCornerCases(t *testing.T) {
 
101
        var (
 
102
                r0 *Ring
 
103
                r1 Ring
 
104
        )
 
105
        // Basics
 
106
        verify(t, r0, 0, 0)
 
107
        verify(t, &r1, 1, 0)
 
108
        // Insert
 
109
        r1.Link(r0)
 
110
        verify(t, r0, 0, 0)
 
111
        verify(t, &r1, 1, 0)
 
112
        // Insert
 
113
        r1.Link(r0)
 
114
        verify(t, r0, 0, 0)
 
115
        verify(t, &r1, 1, 0)
 
116
        // Unlink
 
117
        r1.Unlink(0)
 
118
        verify(t, &r1, 1, 0)
 
119
}
 
120
 
 
121
 
 
122
func makeN(n int) *Ring {
 
123
        r := New(n)
 
124
        for i := 1; i <= n; i++ {
 
125
                r.Value = i
 
126
                r = r.Next()
 
127
        }
 
128
        return r
 
129
}
 
130
 
 
131
func sumN(n int) int { return (n*n + n) / 2 }
 
132
 
 
133
 
 
134
func TestNew(t *testing.T) {
 
135
        for i := 0; i < 10; i++ {
 
136
                r := New(i)
 
137
                verify(t, r, i, -1)
 
138
        }
 
139
        for i := 0; i < 10; i++ {
 
140
                r := makeN(i)
 
141
                verify(t, r, i, sumN(i))
 
142
        }
 
143
}
 
144
 
 
145
 
 
146
func TestLink1(t *testing.T) {
 
147
        r1a := makeN(1)
 
148
        var r1b Ring
 
149
        r2a := r1a.Link(&r1b)
 
150
        verify(t, r2a, 2, 1)
 
151
        if r2a != r1a {
 
152
                t.Errorf("a) 2-element link failed")
 
153
        }
 
154
 
 
155
        r2b := r2a.Link(r2a.Next())
 
156
        verify(t, r2b, 2, 1)
 
157
        if r2b != r2a.Next() {
 
158
                t.Errorf("b) 2-element link failed")
 
159
        }
 
160
 
 
161
        r1c := r2b.Link(r2b)
 
162
        verify(t, r1c, 1, 1)
 
163
        verify(t, r2b, 1, 0)
 
164
}
 
165
 
 
166
 
 
167
func TestLink2(t *testing.T) {
 
168
        var r0 *Ring
 
169
        r1a := &Ring{Value: 42}
 
170
        r1b := &Ring{Value: 77}
 
171
        r10 := makeN(10)
 
172
 
 
173
        r1a.Link(r0)
 
174
        verify(t, r1a, 1, 42)
 
175
 
 
176
        r1a.Link(r1b)
 
177
        verify(t, r1a, 2, 42+77)
 
178
 
 
179
        r10.Link(r0)
 
180
        verify(t, r10, 10, sumN(10))
 
181
 
 
182
        r10.Link(r1a)
 
183
        verify(t, r10, 12, sumN(10)+42+77)
 
184
}
 
185
 
 
186
 
 
187
func TestLink3(t *testing.T) {
 
188
        var r Ring
 
189
        n := 1
 
190
        for i := 1; i < 100; i++ {
 
191
                n += i
 
192
                verify(t, r.Link(New(i)), n, -1)
 
193
        }
 
194
}
 
195
 
 
196
 
 
197
func TestUnlink(t *testing.T) {
 
198
        r10 := makeN(10)
 
199
        s10 := r10.Move(6)
 
200
 
 
201
        sum10 := sumN(10)
 
202
 
 
203
        verify(t, r10, 10, sum10)
 
204
        verify(t, s10, 10, sum10)
 
205
 
 
206
        r0 := r10.Unlink(0)
 
207
        verify(t, r0, 0, 0)
 
208
 
 
209
        r1 := r10.Unlink(1)
 
210
        verify(t, r1, 1, 2)
 
211
        verify(t, r10, 9, sum10-2)
 
212
 
 
213
        r9 := r10.Unlink(9)
 
214
        verify(t, r9, 9, sum10-2)
 
215
        verify(t, r10, 9, sum10-2)
 
216
}
 
217
 
 
218
 
 
219
func TestLinkUnlink(t *testing.T) {
 
220
        for i := 1; i < 4; i++ {
 
221
                ri := New(i)
 
222
                for j := 0; j < i; j++ {
 
223
                        rj := ri.Unlink(j)
 
224
                        verify(t, rj, j, -1)
 
225
                        verify(t, ri, i-j, -1)
 
226
                        ri.Link(rj)
 
227
                        verify(t, ri, i, -1)
 
228
                }
 
229
        }
 
230
}