渠道僵局

Question

I'm building an asynchronous Btree in Go with channels, but I'm getting the error fatal error: all goroutines are asleep - deadlock! I don't know why 'cause I'm getting the values from the channel in a for loop with a buffered channel.

type Obj interface {
    Compare(node Obj) int
}

type Tree struct {
    Item        Obj
    Rigth, Left *Tree
    height      int16
}

func NewTree() *Tree {
    return &Tree{Item: nil, Rigth: nil, Left: nil, height: 0}
}

func InOrder(t *Tree, chTree chan Obj) {
    if t != nil {
        InOrder(t.Left, chTree)
        chTree <- t.Item
        InOrder(t.Rigth, chTree)
    }
}

// == testing ==

func TestInOrder(t *testing.T) {
    tree := NewTree()
    nums := []int{9, 7, 2, 4, 6, 10, 1, 5, 8, 3}
    for i := 0; i < len(nums); i++ {
        tree.Insert(ObjInt{nums[i]})
    }
    result := make(chan Obj, 10)
    go InOrder(tree, result)
    var previous Obj
    for obj := range result {
        fmt.Println(obj)
        if previous == nil {
            previous = obj
            continue
        }
        assertTrue(previous.Compare(obj) == -1, t,
            "Previous obj should be smaller than current object")
        previous = obj
    }
}

Output:

1
2
3
4
5
6
7
8
9
10

fatal error: all goroutines are asleep - deadlock!

Answer 1

You're not closing the channel. You'll notice that it's actually printing correctly, then freaking out.

In a range over a channel, like this:

for obj := range result {
     //...
}

The loop will only exit if you call close(result). In this case it's a bit tricky because of the recursive nature. Ultimately I'd recommend wrapping the call to InOrder like so:

func InOrder(t *Tree, chTree chan obj) {
    inOrder(t, chTree)
    close(chTree)
}

func inOrder(t *Tree, chTree chan Obj) {
    if t != nil {
        inOrder(t.Left, chTree)
        chTree <- t.Item
        inOrder(t.Rigth, chTree)
    }
}