blob: 09e5c527b6cca9c3c59f05676c1732d3fb5a0132 [file] [log] [blame]
 // run // 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. // Test concurrency primitives: prime sieve of Eratosthenes. // 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") } } }