URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [libgo/] [go/] [container/] [ring/] [ring_test.go] - Blame information for rev 801

Go to most recent revision | Details | Compare with Previous | View Log


// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
 
package ring
 
import (
        "fmt"
        "testing"
)
 
// For debugging - keep around.
func dump(r *Ring) {
        if r == nil {
                fmt.Println("empty")
                return
        }
        i, n := 0, r.Len()
        for p := r; i < n; p = p.next {
                fmt.Printf("%4d: %p = {<- %p | %p ->}\n", i, p, p.prev, p.next)
                i++
        }
        fmt.Println()
}
 
func verify(t *testing.T, r *Ring, N int, sum int) {
        // Len
        n := r.Len()
        if n != N {
                t.Errorf("r.Len() == %d; expected %d", n, N)
        }
 
        // iteration
        n = 0
        s := 0
        r.Do(func(p interface{}) {
                n++
                if p != nil {
                        s += p.(int)
                }
        })
        if n != N {
                t.Errorf("number of forward iterations == %d; expected %d", n, N)
        }
        if sum >= 0 && s != sum {
                t.Errorf("forward ring sum = %d; expected %d", s, sum)
        }
 
        if r == nil {
                return
        }
 
        // connections
        if r.next != nil {
                var p *Ring // previous element
                for q := r; p == nil || q != r; q = q.next {
                        if p != nil && p != q.prev {
                                t.Errorf("prev = %p, expected q.prev = %p\n", p, q.prev)
                        }
                        p = q
                }
                if p != r.prev {
                        t.Errorf("prev = %p, expected r.prev = %p\n", p, r.prev)
                }
        }
 
        // Next, Prev
        if r.Next() != r.next {
                t.Errorf("r.Next() != r.next")
        }
        if r.Prev() != r.prev {
                t.Errorf("r.Prev() != r.prev")
        }
 
        // Move
        if r.Move(0) != r {
                t.Errorf("r.Move(0) != r")
        }
        if r.Move(N) != r {
                t.Errorf("r.Move(%d) != r", N)
        }
        if r.Move(-N) != r {
                t.Errorf("r.Move(%d) != r", -N)
        }
        for i := 0; i < 10; i++ {
                ni := N + i
                mi := ni % N
                if r.Move(ni) != r.Move(mi) {
                        t.Errorf("r.Move(%d) != r.Move(%d)", ni, mi)
                }
                if r.Move(-ni) != r.Move(-mi) {
                        t.Errorf("r.Move(%d) != r.Move(%d)", -ni, -mi)
                }
        }
}
 
func TestCornerCases(t *testing.T) {
        var (
                r0 *Ring
                r1 Ring
        )
        // Basics
        verify(t, r0, 0, 0)
        verify(t, &r1, 1, 0)
        // Insert
        r1.Link(r0)
        verify(t, r0, 0, 0)
        verify(t, &r1, 1, 0)
        // Insert
        r1.Link(r0)
        verify(t, r0, 0, 0)
        verify(t, &r1, 1, 0)
        // Unlink
        r1.Unlink(0)
        verify(t, &r1, 1, 0)
}
 
func makeN(n int) *Ring {
        r := New(n)
        for i := 1; i <= n; i++ {
                r.Value = i
                r = r.Next()
        }
        return r
}
 
func sumN(n int) int { return (n*n + n) / 2 }
 
func TestNew(t *testing.T) {
        for i := 0; i < 10; i++ {
                r := New(i)
                verify(t, r, i, -1)
        }
        for i := 0; i < 10; i++ {
                r := makeN(i)
                verify(t, r, i, sumN(i))
        }
}
 
func TestLink1(t *testing.T) {
        r1a := makeN(1)
        var r1b Ring
        r2a := r1a.Link(&r1b)
        verify(t, r2a, 2, 1)
        if r2a != r1a {
                t.Errorf("a) 2-element link failed")
        }
 
        r2b := r2a.Link(r2a.Next())
        verify(t, r2b, 2, 1)
        if r2b != r2a.Next() {
                t.Errorf("b) 2-element link failed")
        }
 
        r1c := r2b.Link(r2b)
        verify(t, r1c, 1, 1)
        verify(t, r2b, 1, 0)
}
 
func TestLink2(t *testing.T) {
        var r0 *Ring
        r1a := &Ring{Value: 42}
        r1b := &Ring{Value: 77}
        r10 := makeN(10)
 
        r1a.Link(r0)
        verify(t, r1a, 1, 42)
 
        r1a.Link(r1b)
        verify(t, r1a, 2, 42+77)
 
        r10.Link(r0)
        verify(t, r10, 10, sumN(10))
 
        r10.Link(r1a)
        verify(t, r10, 12, sumN(10)+42+77)
}
 
func TestLink3(t *testing.T) {
        var r Ring
        n := 1
        for i := 1; i < 100; i++ {
                n += i
                verify(t, r.Link(New(i)), n, -1)
        }
}
 
func TestUnlink(t *testing.T) {
        r10 := makeN(10)
        s10 := r10.Move(6)
 
        sum10 := sumN(10)
 
        verify(t, r10, 10, sum10)
        verify(t, s10, 10, sum10)
 
        r0 := r10.Unlink(0)
        verify(t, r0, 0, 0)
 
        r1 := r10.Unlink(1)
        verify(t, r1, 1, 2)
        verify(t, r10, 9, sum10-2)
 
        r9 := r10.Unlink(9)
        verify(t, r9, 9, sum10-2)
        verify(t, r10, 9, sum10-2)
}
 
func TestLinkUnlink(t *testing.T) {
        for i := 1; i < 4; i++ {
                ri := New(i)
                for j := 0; j < i; j++ {
                        rj := ri.Unlink(j)
                        verify(t, rj, j, -1)
                        verify(t, ri, i-j, -1)
                        ri.Link(rj)
                        verify(t, ri, i, -1)
                }
        }
}

Browse

Tools

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [libgo/] [go/] [container/] [ring/] [ring_test.go] - Blame information for rev 801

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