mirror of
https://github.com/golang/go
synced 2025-04-12 00:29:42 +00:00
.github
api
doc
lib
misc
src
test
abi
alias3.dir
asmhdr.dir
bench
chan
doubleselect.go
fifo.go
goroutines.go
nonblock.go
perm.go
powser1.go
powser2.go
select.go
select2.go
select3.go
select4.go
select5.go
select6.go
select7.go
select8.go
sendstmt.go
sieve1.go
sieve2.go
zerosize.go
closure3.dir
closure5.dir
codegen
ddd2.dir
dwarf
fixedbugs
import2.dir
import4.dir
interface
intrinsic.dir
ken
linkname.dir
method4.dir
retjmp.dir
runtime
stress
syntax
typeparam
uintptrescapes.dir
235.go
64bit.go
README.md
alg.go
alias.go
alias1.go
alias2.go
alias3.go
align.go
append.go
append1.go
args.go
armimm.go
asmhdr.go
assign.go
assign1.go
atomicload.go
bigalg.go
bigmap.go
blank.go
blank1.go
bom.go
bombad.go
bounds.go
cannotassign.go
chancap.go
chanlinear.go
char_lit.go
char_lit1.go
checkbce.go
clearfat.go
closedchan.go
closure.go
closure1.go
closure2.go
closure3.go
closure4.go
closure5.go
closure6.go
closure7.go
cmp.go
cmp6.go
cmplx.go
cmplxdivide.c
cmplxdivide.go
cmplxdivide1.go
complit.go
complit1.go
compos.go
const.go
const1.go
const2.go
const3.go
const4.go
const5.go
const6.go
const7.go
const8.go
convT2X.go
convert.go
convert1.go
convert2.go
convert3.go
convert4.go
convinline.go
convlit.go
convlit1.go
copy.go
copy1.go
crlf.go
ddd.go
ddd1.go
ddd2.go
decl.go
declbad.go
defer.go
defererrcheck.go
deferfin.go
defernil.go
deferprint.go
deferprint.out
devirt.go
directive.go
directive2.go
divide.go
divmod.go
embedfunc.go
embedvers.go
empty.go
env.go
eof.go
eof1.go
escape.go
escape2.go
escape2n.go
escape3.go
escape4.go
escape5.go
escape_array.go
escape_calls.go
escape_closure.go
escape_field.go
escape_goto.go
escape_hash_maphash.go
escape_iface.go
escape_iface_nounified.go
escape_iface_unified.go
escape_indir.go
escape_level.go
escape_map.go
escape_param.go
escape_runtime_atomic.go
escape_selfassign.go
escape_slice.go
escape_struct_param1.go
escape_struct_param2.go
escape_struct_return.go
escape_sync_atomic.go
escape_unsafe.go
fibo.go
finprofiled.go
float_lit.go
float_lit2.go
float_lit3.go
floatcmp.go
for.go
func.go
func1.go
func2.go
func3.go
func4.go
func5.go
func6.go
func7.go
func8.go
funcdup.go
funcdup2.go
fuse.go
gc.go
gc1.go
gc2.go
gcgort.go
gcstring.go
goprint.go
goprint.out
goto.go
heapsampling.go
helloworld.go
helloworld.out
if.go
import.go
import1.go
import2.go
import4.go
import5.go
import6.go
index.go
index0.go
index1.go
index2.go
indirect.go
indirect1.go
init.go
init1.go
initcomma.go
initexp.go
initialize.go
initializerr.go
initloop.go
inline.go
inline_big.go
inline_caller.go
inline_callers.go
inline_endian.go
inline_literal.go
inline_math_bits_rotate.go
inline_nounified.go
inline_sync.go
inline_unified.go
inline_variadic.go
int_lit.go
intcvt.go
intrinsic.go
intrinsic_atomic.go
iota.go
label.go
label1.go
linkmain.go
linkmain_run.go
linkname.go
linkname3.go
linkobj.go
linkx.go
linkx_run.go
literal.go
literal2.go
live.go
live1.go
live2.go
live_regabi.go
live_uintptrkeepalive.go
loopbce.go
mainsig.go
makechan.go
makemap.go
makenew.go
makeslice.go
mallocfin.go
map.go
map1.go
mapclear.go
maplinear.go
maymorestack.go
mergemul.go
method.go
method1.go
method2.go
method3.go
method4.go
method5.go
method6.go
method7.go
named.go
named1.go
nil.go
nilcheck.go
nilptr.go
nilptr2.go
nilptr3.go
nilptr4.go
nilptr5.go
nilptr5_aix.go
nilptr5_wasm.go
nilptr_aix.go
noinit.go
nosplit.go
nowritebarrier.go
nul1.go
opt_branchlikely.go
parentype.go
peano.go
phiopt.go
print.go
print.out
printbig.go
printbig.out
prove.go
prove_constant_folding.go
range.go
recover.go
recover1.go
recover2.go
recover3.go
recover4.go
recover5.go
reflectmethod1.go
reflectmethod2.go
reflectmethod3.go
reflectmethod4.go
reflectmethod5.go
reflectmethod6.go
reflectmethod7.go
reflectmethod8.go
rename.go
rename1.go
reorder.go
reorder2.go
retjmp.go
return.go
rotate.go
rotate0.go
rotate1.go
rotate2.go
rotate3.go
run.go
rune.go
runtime.go
shift1.go
shift2.go
shift3.go
sieve.go
sigchld.go
sigchld.out
simassign.go
sizeof.go
slice3.go
slice3err.go
slicecap.go
sliceopt.go
solitaire.go
stack.go
stackobj.go
stackobj2.go
stackobj3.go
strcopy.go
strength.go
string_lit.go
stringrange.go
struct0.go
switch.go
switch2.go
switch3.go
switch4.go
switch5.go
switch6.go
switch7.go
tinyfin.go
torture.go
turing.go
typecheck.go
typecheckloop.go
typeswitch.go
typeswitch1.go
typeswitch2.go
typeswitch2b.go
typeswitch3.go
uintptrescapes.go
uintptrescapes2.go
uintptrescapes3.go
uintptrkeepalive.go
undef.go
unsafe_slice_data.go
unsafe_string.go
unsafe_string_data.go
unsafebuiltins.go
used.go
utf.go
varerr.go
varinit.go
winbatch.go
writebarrier.go
zerodivide.go
.gitattributes
.gitignore
CONTRIBUTING.md
LICENSE
PATENTS
README.md
SECURITY.md
VERSION
codereview.cfg
189 lines
3.9 KiB
Go
189 lines
3.9 KiB
Go
// 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 <http://blog.onideas.ws/eratosthenes.go>.
|
|
|
|
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")
|
|
}
|
|
}
|
|
}
|