Addressable or not addressable, that is the question

programming

ACME Corporation has commissioned Wile E. to build an Address Book component for their new flagship product.

Wile: "Ok, I will create 2 structs: Contact and AddressBook and they will be like this:"

  • Contact will be a struct containing the name, surname and phone properties
  • AddressBook will be a struct containing a slice of Contacts and 2 methods to retrieve (Get(surname string)) and add (Add(surname, name, phone string)) a contact.

When Wile finally finishes writing the code, the implementation looks like this:

package main

import "fmt"

/** Contact type **/
type Contact struct {
    name    string
    surname string
    phone   string
}

func (c *Contact) Name() string { return c.name }

func (c *Contact) Surname() string { return c.surname }

func (c *Contact) Phone() string { return c.phone }

func (c *Contact) SetName(name string) { c.name = name }

func (c *Contact) SetSurname(surname string) { c.surname = surname }

func (c *Contact) SetPhone(phone string) { c.phone = phone }

/** Address Book Type **/
type AddressBook struct {
    contacts []Contact
}

func (a *AddressBook) Add(surname, name, phone string) {
    a.contacts = append(a.contacts, Contact{surname: surname, name: name, phone: phone})
}

func (a *AddressBook) Get(surname string) *Contact {
    for _, c := range a.contacts {
        if c.Surname() == surname {
            return &c
        }
    }
    return nil
}

func NewAddressBook() AddressBook {
    return AddressBook{}
}

To be sure, Wile writes some simple code to ensure it works as expected:

func main() {
    addressBook := NewAddressBook()
    addressBook.Add("Ethelbert", "Wile", "(01)-12345678")
    addressBook.Add("Beep", "Beep", "(01)-87654321")

    fmt.Println("Wile: ", addressBook.Get("Ethelbert"))
    fmt.Println("Beep: ", addressBook.Get("Beep"))
    fmt.Println("Rabbit: ", addressBook.Get("Rabbit"))
}

=== OUTPUT ===
Wile:  &{Wile Ethelbert (01)-12345678}
Beep:  &{Beep Beep (01)-87654321}
Rabbit:  <nil>

Wile: "Great, works as expected! However, I already know what Beep Beep would say if he would read that code: - Hey Wile! What will happen when you have thousands of entries?"

To avoid having the code become slower and slower with the growth of the number of entries, Wile decides to change the []Contact with a map[string]Contact using the surname as key:

/** Address Book Type **/
type AddressBook struct {
    contacts map[string]Contact
}

func (a *AddressBook) Add(surname, name, phone string) {
    a.contacts[surname] = Contact{surname: surname, name: name, phone: phone}
}

func (a *AddressBook) Get(surname string) *Contact {
    return &a.contacts[surname]
}

func NewAddressBook() AddressBook {
    return AddressBook{
        contacts: map[string]Contact{},
    }
}

Something unexpected happens, the code doesn't build:

./prog.go:34:10: invalid operation: cannot take address of a.contacts[surname] (map index expression of type Contact)

What is happening?

Golang map internals

To understand why Wile got the cannot take address error, Wile started reading a lot of documentation and discovered that the reason is due to some internal details of the golang map.

When Golang designers had to implement the map object, they faced the same issue Wile faced implementing the AddressBook: they had to find a way to give a constant time lookup, regardless of the size of the map. To achieve such a goal, they decided to implement map this way:

  1. Implement the map as an array of Buckets. Each bucket will contain up to 8 entries and an overflow pointer pointing to an overflow bucket to be used in the unlikely case that more than 8 map entries will need the same bucket.
  2. Implement a hash function to be used to compute which bucket is associated with the given key
  3. If the average usage of the buckets is 6.5 or more, double the size of the buckets array into a new array and move all the entries to the new array (1)

The last point is the key to understanding the cannot take address error: map in golang is a self-organising structure. Objects in the map can be moved when the map is resized making any external pointer to map entries invalid. For that reason, map entries are not addressable.

Be aware that this has another consequence: you won't be able to call any method defined with a pointer receiver on the map entry.

This code, for example, would fail: a.contacts[surname].Name()

(1) Copy doesn't happen immediately. If a resize happens, every time an object is inserted or deleted from the map, a bunch of objects is copied from the old array to the new one, up until all of them are moved and the old array can be discarded.

Solution to the Wile E. problem

First solution: return the address of a copy of the map entry

If we create a copy and return the address of the copy, the code will work again:

func (a *AddressBook) Get(surname string) *Contact {
    if c, ok := a.contacts[surname]; ok {
        return &c
    }
    return nil
}

By returning the address of a copy, any change to the returned object will be performed to the copy. The object inside the map will be unchanged.

Try for example the following code:

package main

import "fmt"

/** Contact type **/
type Contact struct {
    name    string
    surname string
    phone   string
}

func (c *Contact) Name() string { return c.name }

func (c *Contact) Surname() string { return c.surname }

func (c *Contact) Phone() string { return c.phone }

func (c *Contact) SetName(name string) { c.name = name }

func (c *Contact) SetSurname(surname string) { c.surname = surname }

func (c *Contact) SetPhone(phone string) { c.phone = phone }

/** Address Book Type **/
type AddressBook struct {
    contacts map[string]Contact
}

func (a *AddressBook) Add(surname, name, phone string) {
    a.contacts[surname] = Contact{surname: surname, name: name, phone: phone}
}

func (a *AddressBook) Get(surname string) *Contact {
    if c, ok := a.contacts[surname]; ok {
        return &c
    }
    return nil
}

func NewAddressBook() AddressBook {
    return AddressBook{
        contacts: map[string]Contact{},
    }
}

func main() {
    addressBook := NewAddressBook()
    addressBook.Add("Ethelbert", "Wile", "(01)-12345678")
    addressBook.Add("Beep", "Beep", "(01)-87654321")

    c := addressBook.Get("Beep")
    c.SetName("Road")
    c.SetSurname("Runner")
    fmt.Println("c: ", c)
    fmt.Println("addressBook.Get: ", addressBook.Get("Beep"))
}

=== OUTPUT ===
c:  &{Road Runner (01)-87654321}
addressBook.Get:  &{Beep Beep (01)-87654321}

Be careful about what you return! If you look carefully at the code, in the Get method I changed the code from return a.contacts[surname] to 

if c, ok := a.contacts[surname]; ok {
  return &c
}
return nil

Why? Because when the passed in key is not found, the map object returns the zero value for the value object, in our case Contact{}

Second solution: change the map from map[string]Contact to map[string]*Contact

If we need to be able to make changes to the object inside the map, we can store a pointer to our struct:

package main

import "fmt"

/** Contact type **/
type Contact struct {
    name    string
    surname string
    phone   string
}

func (c *Contact) Name() string { return c.name }

func (c *Contact) Surname() string { return c.surname }

func (c *Contact) Phone() string { return c.phone }

func (c *Contact) SetName(name string) { c.name = name }

func (c *Contact) SetSurname(surname string) { c.surname = surname }

func (c *Contact) SetPhone(phone string) { c.phone = phone }

/** Address Book Type **/
type AddressBook struct {
    contacts map[string]*Contact
}

func (a *AddressBook) Add(surname, name, phone string) {
    a.contacts[surname] = &Contact{surname: surname, name: name, phone: phone}
}

func (a *AddressBook) Get(surname string) *Contact {
    if c, ok := a.contacts[surname]; ok {
        return c
    }
    return nil
}

func NewAddressBook() AddressBook {
    return AddressBook{
        contacts: map[string]*Contact{},
    }
}

func main() {
    addressBook := NewAddressBook()
    addressBook.Add("Ethelbert", "Wile", "(01)-12345678")
    addressBook.Add("Beep", "Beep", "(01)-87654321")

    c := addressBook.Get("Beep")
    c.SetName("Road")
    c.SetSurname("Runner")
    fmt.Println("c: ", c)
    fmt.Println("addressBook.Get: ", addressBook.Get("Beep"))
}

=== OUTPUT ===
c:  &{Road Runner (01)-87654321}
addressBook.Get:  &{Road Runner (01)-87654321}

That's all folks!

Previous Next