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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [gcc/] [testsuite/] [go.test/] [test/] [chan/] [sieve2.go] - Blame information for rev 700

Details | Compare with Previous | View Log


// $G $D/$F.go && $L $F.$A && ./$A.out
 
// 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.
 
// Generate primes up to 100 using channels, checking the results.
// This sieve is Eratosthenesque and only considers odd candidates.
// See discussion at .
 
package main
 
import (
        "container/heap"
        "container/ring"
)
 
// Return a chan of odd numbers, starting from 5.
func odds() chan int {
        out := make(chan int, 50)
        go func() {
                n := 5
                for {
                        out <- n
                        n += 2
                }
        }()
        return out
}
 
// Return a chan of odd multiples of the prime number p, starting from p*p.
func multiples(p int) chan int {
        out := make(chan int, 10)
        go func() {
                n := p * p
                for {
                        out <- n
                        n += 2 * p
                }
        }()
        return out
}
 
type PeekCh struct {
        head int
        ch   chan int
}
 
// Heap of PeekCh, sorting by head values, satisfies Heap interface.
type PeekChHeap []*PeekCh
 
func (h *PeekChHeap) Less(i, j int) bool {
        return (*h)[i].head < (*h)[j].head
}
 
func (h *PeekChHeap) Swap(i, j int) {
        (*h)[i], (*h)[j] = (*h)[j], (*h)[i]
}
 
func (h *PeekChHeap) Len() int {
        return len(*h)
}
 
func (h *PeekChHeap) Pop() (v interface{}) {
        *h, v = (*h)[:h.Len()-1], (*h)[h.Len()-1]
        return
}
 
func (h *PeekChHeap) Push(v interface{}) {
        *h = append(*h, v.(*PeekCh))
}
 
// Return a channel to serve as a sending proxy to 'out'.
// Use a goroutine to receive values from 'out' and store them
// in an expanding buffer, so that sending to 'out' never blocks.
func sendproxy(out chan<- int) chan<- int {
        proxy := make(chan int, 10)
        go func() {
                n := 16 // the allocated size of the circular queue
                first := ring.New(n)
                last := first
                var c chan<- int
                var e int
                for {
                        c = out
                        if first == last {
                                // buffer empty: disable output
                                c = nil
                        } else {
                                e = first.Value.(int)
                        }
                        select {
                        case e = <-proxy:
                                last.Value = e
                                if last.Next() == first {
                                        // buffer full: expand it
                                        last.Link(ring.New(n))
                                        n *= 2
                                }
                                last = last.Next()
                        case c <- e:
                                first = first.Next()
                        }
                }
        }()
        return proxy
}
 
// Return a chan int of primes.
func Sieve() chan int {
        // The output values.
        out := make(chan int, 10)
        out <- 2
        out <- 3
 
        // The channel of all composites to be eliminated in increasing order.
        composites := make(chan int, 50)
 
        // The feedback loop.
        primes := make(chan int, 10)
        primes <- 3
 
        // Merge channels of multiples of 'primes' into 'composites'.
        go func() {
                var h PeekChHeap
                min := 15
                for {
                        m := multiples(<-primes)
                        head := <-m
                        for min < head {
                                composites <- min
                                minchan := heap.Pop(&h).(*PeekCh)
                                min = minchan.head
                                minchan.head = <-minchan.ch
                                heap.Push(&h, minchan)
                        }
                        for min == head {
                                minchan := heap.Pop(&h).(*PeekCh)
                                min = minchan.head
                                minchan.head = <-minchan.ch
                                heap.Push(&h, minchan)
                        }
                        composites <- head
                        heap.Push(&h, &PeekCh{<-m, m})
                }
        }()
 
        // Sieve out 'composites' from 'candidates'.
        go func() {
                // In order to generate the nth prime we only need multiples of
                // primes ≤ sqrt(nth prime).  Thus, the merging goroutine will
                // receive from 'primes' much slower than this goroutine
                // will send to it, making the buffer accumulate and block this
                // goroutine from sending, causing a deadlock.  The solution is to
                // use a proxy goroutine to do automatic buffering.
                primes := sendproxy(primes)
 
                candidates := odds()
                p := <-candidates
 
                for {
                        c := <-composites
                        for p < c {
                                primes <- p
                                out <- p
                                p = <-candidates
                        }
                        if p == c {
                                p = <-candidates
                        }
                }
        }()
 
        return out
}
 
func main() {
        primes := Sieve()
        a := []int{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}
        for i := 0; i < len(a); i++ {
                if x := <-primes; x != a[i] {
                        println(x, " != ", a[i])
                        panic("fail")
                }
        }
}

Line No.	Rev	Author	Line
1	700	jeremybenn	`// $G $D/$F.go && $L $F.$A && ./$A.out`
2
3			`// Copyright 2009 The Go Authors. All rights reserved.`
4			`// Use of this source code is governed by a BSD-style`
5			`// license that can be found in the LICENSE file.`
6
7			`// Generate primes up to 100 using channels, checking the results.`
8			`// This sieve is Eratosthenesque and only considers odd candidates.`
9			`// See discussion at .`
10
11			`package main`
12
13			`import (`
14			`"container/heap"`
15			`"container/ring"`
16			`)`
17
18			`// Return a chan of odd numbers, starting from 5.`
19			`func odds() chan int {`
20			`out := make(chan int, 50)`
21			`go func() {`
22			`n := 5`
23			`for {`
24			`out <- n`
25			`n += 2`
26			`}`
27			`}()`
28			`return out`
29			`}`
30
31			`// Return a chan of odd multiples of the prime number p, starting from p*p.`
32			`func multiples(p int) chan int {`
33			`out := make(chan int, 10)`
34			`go func() {`
35			`n := p * p`
36			`for {`
37			`out <- n`
38			`n += 2 * p`
39			`}`
40			`}()`
41			`return out`
42			`}`
43
44			`type PeekCh struct {`
45			`head int`
46			`ch chan int`
47			`}`
48
49			`// Heap of PeekCh, sorting by head values, satisfies Heap interface.`
50			`type PeekChHeap []*PeekCh`
51
52			`func (h *PeekChHeap) Less(i, j int) bool {`
53			`return (h)[i].head < (h)[j].head`
54			`}`
55
56			`func (h *PeekChHeap) Swap(i, j int) {`
57			`(h)[i], (h)[j] = (h)[j], (h)[i]`
58			`}`
59
60			`func (h *PeekChHeap) Len() int {`
61			`return len(*h)`
62			`}`
63
64			`func (h *PeekChHeap) Pop() (v interface{}) {`
65			`h, v = (h)[:h.Len()-1], (*h)[h.Len()-1]`
66			`return`
67			`}`
68
69			`func (h *PeekChHeap) Push(v interface{}) {`
70			`h = append(h, v.(*PeekCh))`
71			`}`
72
73			`// Return a channel to serve as a sending proxy to 'out'.`
74			`// Use a goroutine to receive values from 'out' and store them`
75			`// in an expanding buffer, so that sending to 'out' never blocks.`
76			`func sendproxy(out chan<- int) chan<- int {`
77			`proxy := make(chan int, 10)`
78			`go func() {`
79			`n := 16 // the allocated size of the circular queue`
80			`first := ring.New(n)`
81			`last := first`
82			`var c chan<- int`
83			`var e int`
84			`for {`
85			`c = out`
86			`if first == last {`
87			`// buffer empty: disable output`
88			`c = nil`
89			`} else {`
90			`e = first.Value.(int)`
91			`}`
92			`select {`
93			`case e = <-proxy:`
94			`last.Value = e`
95			`if last.Next() == first {`
96			`// buffer full: expand it`
97			`last.Link(ring.New(n))`
98			`n *= 2`
99			`}`
100			`last = last.Next()`
101			`case c <- e:`
102			`first = first.Next()`
103			`}`
104			`}`
105			`}()`
106			`return proxy`
107			`}`
108
109			`// Return a chan int of primes.`
110			`func Sieve() chan int {`
111			`// The output values.`
112			`out := make(chan int, 10)`
113			`out <- 2`
114			`out <- 3`
115
116			`// The channel of all composites to be eliminated in increasing order.`
117			`composites := make(chan int, 50)`
118
119			`// The feedback loop.`
120			`primes := make(chan int, 10)`
121			`primes <- 3`
122
123			`// Merge channels of multiples of 'primes' into 'composites'.`
124			`go func() {`
125			`var h PeekChHeap`
126			`min := 15`
127			`for {`
128			`m := multiples(<-primes)`
129			`head := <-m`
130			`for min < head {`
131			`composites <- min`
132			`minchan := heap.Pop(&h).(*PeekCh)`
133			`min = minchan.head`
134			`minchan.head = <-minchan.ch`
135			`heap.Push(&h, minchan)`
136			`}`
137			`for min == head {`
138			`minchan := heap.Pop(&h).(*PeekCh)`
139			`min = minchan.head`
140			`minchan.head = <-minchan.ch`
141			`heap.Push(&h, minchan)`
142			`}`
143			`composites <- head`
144			`heap.Push(&h, &PeekCh{<-m, m})`
145			`}`
146			`}()`
147
148			`// Sieve out 'composites' from 'candidates'.`
149			`go func() {`
150			`// In order to generate the nth prime we only need multiples of`
151			`// primes ≤ sqrt(nth prime). Thus, the merging goroutine will`
152			`// receive from 'primes' much slower than this goroutine`
153			`// will send to it, making the buffer accumulate and block this`
154			`// goroutine from sending, causing a deadlock. The solution is to`
155			`// use a proxy goroutine to do automatic buffering.`
156			`primes := sendproxy(primes)`
157
158			`candidates := odds()`
159			`p := <-candidates`
160
161			`for {`
162			`c := <-composites`
163			`for p < c {`
164			`primes <- p`
165			`out <- p`
166			`p = <-candidates`
167			`}`
168			`if p == c {`
169			`p = <-candidates`
170			`}`
171			`}`
172			`}()`
173
174			`return out`
175			`}`
176
177			`func main() {`
178			`primes := Sieve()`
179			`a := []int{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}`
180			`for i := 0; i < len(a); i++ {`
181			`if x := <-primes; x != a[i] {`
182			`println(x, " != ", a[i])`
183			`panic("fail")`
184			`}`
185			`}`
186			`}`

Browse

Tools

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [gcc/] [testsuite/] [go.test/] [test/] [chan/] [sieve2.go] - Blame information for rev 700