goroutree

README

Goroutree: A tree-based set made of coordinating goroutines

This project is an idea I had for a long time, but didn't have a reason to actually implement. It was implemented for a blog post in the Gopher Academy Advent Series 2016.

(link to blog post to be added when it goes live)

It's a set that's made of a tree of coordinating goroutines. All communication is async with responses returning via a channel supplied by the caller.

There's only three real operations: Insert, Contains, and Delete.

• Insert will add an item if it does not already exist (and will tel you if it was successful).
• Contains will tell you whether the value is already in the tree.
• Delete will remove an item if it exists (and will tell you if it did).

There's a fourth, print, that is used to dump the state of the tree for verification and testing.

In general, each node in the tree is a separate goroutine that has a stream of messages coming in. The node will respond to each message as it receives it and will forward to children as appropriate. In order to start things out (and to deal with things like an empty set) there is a manager that runs as a "super root" node and receives the messages first and forwards as necessary to the main root node.

The code is fairly straightforward in terms of organization, just a single implementation file and a single test file.

A note of caution: This is not production level code. It was written for a blog post as a toy and to prove out the concept. I don't recommend running it in a production system without a lot more testing in concurrent situations.

Documentation

Index

• Variables
• type Comparer
• type Goroutree
  • func New() *Goroutree
  • func (g *Goroutree) Contains(reschan chan bool, val Comparer)
  • func (g *Goroutree) Delete(reschan chan bool, val Comparer)
  • func (g *Goroutree) Insert(reschan chan bool, val Comparer)
  • func (g *Goroutree) Print(reschan chan struct{}, w io.Writer)
• type Int
  • func (i Int) Compare(value interface{}) (int, error)

Variables

var NotComparable error = errors.New("Not Comparable")

Types

type Comparer

type Comparer interface {
	// Compare yourself to something.  If the values are not comparable,
	// returns negative if the first argument is “less” than the second, zero
	// if they are “equal”, and positive if the first argument is “greater”
	// returns 0, and an error of "Not Comparable" if not comparable
	Compare(interface{}) (int, error)
}

type Goroutree

type Goroutree struct {
	// contains filtered or unexported fields
}

Goroutree is a tree set represented by a set of running goroutines, one per node in the tree. It is essentially an actor-based tree that holds machine-sized integers. The tree is unbalanced and does no rotations, so a series of inserts and deletes can make it very unbalanced. The tree is not going to be bombproof (because this is for a blog post) and probably has some obvious races.

func New

func New() *Goroutree

New creates a new empty Goroutree

func (*Goroutree) Contains

func (g *Goroutree) Contains(reschan chan bool, val Comparer)

Contains will tell if the set contains the given value. The channel passed will receive a true if the value does exist in the set and a false if not.

func (*Goroutree) Delete

func (g *Goroutree) Delete(reschan chan bool, val Comparer)

Delete removes a value from the tree set if it exists. The channel passed will receive a true if the value did exist in the set and a false if not.

func (*Goroutree) Insert

func (g *Goroutree) Insert(reschan chan bool, val Comparer)

Insert adds a new value into the set if it does not already exist. The channel passed will receive a true if the value was successfully inserted and a false if the value already existed.

func (*Goroutree) Print

func (g *Goroutree) Print(reschan chan struct{}, w io.Writer)

Print will print out the tree. This is a blocking operation, so no other messages can be processed while printing. This is for debugging purposes only.

type Int

type Int int

func (Int) Compare

func (i Int) Compare(value interface{}) (int, error)