Reference type confusing in Go language

Question

I tried to make Trie data structures by Go Language, but somehow it stuck with References problem, Here it is. http://play.golang.org/p/ASSGF5Oe9R

// Package main provides ...
package main

import "fmt"

type RootTrie []Trie

type Trie struct {
    subtrie []Trie
    index   byte
}

func (trie *Trie) Insert(data string) *Trie {
    if data != "" {
        if trie.index == 0 {
            trie.index = data[0]
        }
        if next := trie.containsIndex(data[1:]); next != nil {
            //Problem Point
            fmt.Println(string(data[1]), "found follwing", string(data[0]))
            next.Insert(data[1:])
        } else {
            nt := &Trie{}
            trie.subtrie = append(trie.subtrie, *nt.Insert(data[1:]))
        }
    }

    return trie
}
func (trie *Trie) containsIndex(next string) *Trie {
    if next != "" {
        for _, st := range trie.subtrie {
            if st.index == next[0] {
                return &st
            }
        }
    }
    return nil
}

func main() {
    t := &Trie{}
    t = t.Insert("hanyang")
    fmt.Println("result:", t)
    t = t.Insert("hanyKk")
    fmt.Println("result:", t)
    t.Insert("hanyK")
}

The following problems happen in second "Insert", the where I put, //Problem Point

I made containsIndex method for searching next linked trie, and it searched well actually. But when I updated next property which containsIndex given, its not affected its mother struct trie though.

What I don't understand is I gave it reference type when returning containsIndex, but its still act liked 'value copied', Why does it not affected its mother structure(trie)?

Thanks!

I don't get the -1--there're language nits, but it explains the nature of the problem and there's code you can mess around with. — twotwotwo, Dec 30 '14 at 17:43

score 3 · Accepted Answer · answered Dec 30 '14 at 08:33

3

The problem is in method containsIndex. Golang range by default creates copy each element in slice and assigns copy of this value to st (in your example). Usually to preserve reference to element in slice you should use original slice and its index. In you case method containsIndex should look something like this:

func (trie *Trie) containsIndex(next string) *Trie {
    if next != "" {
        for i, st := range trie.subtrie {
            if st.index == next[0] {
                return &trie.subtrie[i]
            }
        }
    }
    return nil
}

answered Dec 30 '14 at 08:33

wonsky

503
2
7

Does this also imply a performance difference when using just indices, instead of values as well? – Etienne Bruines Dec 30 '14 at 10:34
@EtienneBruines -- Maybe. It might be it's negligible, or there might be no difference if the compiler recognizes it can optimize the copy away sometimes. If you run into this choice in a performance-critical inner loop, you can always test. – twotwotwo Dec 30 '14 at 17:36
@twotwotwo Thank you for your response. I've ran some benchmarks: in non-complicated cases, there is no performance difference at all. https://github.com/EtienneBruines/go-range-performance-analysis – Etienne Bruines Dec 31 '14 at 00:24
1

Thanks, @wonsky. and I found some interesting answers there I examine about address differences [link](http://stackoverflow.com/a/15952415/369929) – tomahawk28 Dec 31 '14 at 04:04

Reference type confusing in Go language

1 Answers1