Introduction
Go has a number of great features that make programming fun again. The inclusion of channels as first class values is among my particular favorites. This combined with go also having support for first class functions really provides a great foundation for being able to do some really neat things very easily.
Building a “thread safe” stack.
I’m sure we all remember from a ‘classic data structures’ class how to build a stack. Since the stack arguably the most basic of the data structures, I will show a basic example how how to implement a stack using first class functions and channels that is safe for concurrent use in Go. I’m in the process of building a more robust library of thread-safe data structures which can be found here.
The SafeStack Data Structures
The complete code listing for this is located here.
The primary structure for the SafeStack is simply a publically available Structure that has a private channel that accepts any function that takes a stack pointer.
//SafeStack is the structure that contains the channel used to
//communicate with the stack.
type SafeStack struct {
op chan (func(*stack))
}
Next, we must define a container structure for the stack:
//stack is the basic container for the stack
type stack struct {
top *elem
size int64
}
And, finally, the elements. We will use the empty interface as the datatype for the stack element’s value.
//elem is the element structure
type elem struct {
value interface{}
next *elem
}
The private method loop()
This is a special method which requires a little explanation. First the code listing:
//loop creates the guarded data structure and listens for
//methods on the op channel. The loop method terminates when the op
//channel is closed.
func (s *SafeStack) loop() {
st := &stack{}
for op := range s.op {
op(st)
}
}
There is not a lot here, but the order and manner in which this is implemented is important. First, we create the actual stack data structure here, local to the loop method. This is an easy way to guard the data from the outside, requiring Public Methods to access the stack. Then, we use Go’s range loop control to iterate over the channel and process any requests sequentially without having to use locks or mutex’s.
The New function
In order to initialize a new stack, we need to create the channel and start the go routine:
//New creates a new Safe Stack, this also starts the go-routine
//so once this is called, you need to clean up after yourself
//by using the Destroy method.
func New() (s *SafeStack) {
s = &SafeStack{make(chan func(*stack))}
go s.loop()
return
}
In the next part we will cover creating the Public methods for accessing and managing the elements in the stack.
The Public Safe Stack Methods
There are 4 Public methods that we need to implement for this stack.. They are:
- Len
- Push
- Pop
- Destroy
The public methods all use the same general format, sending a function on the ops channel that accepts an argument of a stack pointer. It is this argument that allows you to perform operations on the stack. We’ll start with the Len method because it is simple, all we want to do is return the current length of the stack
The Len method
Code first:
//Len will get return the number of items in the stack.
func (s *SafeStack) Len() (i int64) {
lChan := make(chan int64)
s.op <- func(curr *stack) {
lChan <- curr.size
}
return <-lChan
}
You will see this pattern repeat throughout the stack, what we are doing as Dave Cheney so eloquently put it “Passing behavior instead of data”. I’d strongly urge you to watch his fantastic presentation here, it illustrates how to minimize select blocks for channels and make much more readable and maintainable code.
What we’re doing is passing a function on a channel which will operate on the protected stack which we created in the loop method. There is one caveat though, since we’re passing the method in the channel using a closure, we need to use a channel to pass any data back that we want returned. That is the purpose of the local channel lChan. By structuring the code this way, we are eliminating a select block which makes the code more readable and easier to maintain.
The Push method
//Push will push the value v onto the stack.
func (s *SafeStack) Push(v interface{}) {
s.op <- func(curr *stack) {
curr.top = &elem{v, curr.top}
curr.size++
}
}
The Push method is quite simple, as we are simply creating a new element with it’s next value as the current top, setting it to the current top and incrementing the size. Note that when operating on the stack inside the stack inside the closure, the parameter of the function is the stack structure you created inside the loop() method earlier.
The Pop method
//Pop will perform a pop on the stack, removing the first item
//and returning it's value.
func (s *SafeStack) Pop() (v interface{}) {
vChan := make(chan interface{})
s.op <- func(curr *stack) {
if curr.size == 0 {
vChan <- nil
return
}
val := curr.top.value
curr.top = curr.top.next
curr.size--
vChan <- val
return
}
return <-vChan
}
The Pop method is the most complicated of the bunch and it’s not really that complex. Here, like in Len() we use a channel to return the data but this time it’s a type of empty interface instead of int64. As long as the channel type you create matches the return value, you’ll be fine.
The Destroy method
//Destroy closes the primary channel thus stopping
//the running go-routine.
func (s *SafeStack) Destroy() {
close(s.op)
}
Because we’re running the go-routine in a loop, we need a way to stop it. you should never start a go routine without knowing how it will terminate. Since we decided to iterate over the channel, we can just close it and the go routine will terminate.
Conclusion
In the github repository, there is a runnable example in the example directory, I’d encourage you to run it using the go race detector to show there are no race conditions. Also, as an additional excercise, you can try to make a Peek() method that returns the top of the stack but doesn’t remove it. Please check out the complete source code here and if you have comments or questions, please contact me via twitter.