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 ¶
Constants ¶
This section is empty.
Variables ¶
var NotComparable error = errors.New("Not Comparable")
Functions ¶
This section is empty.
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 (*Goroutree) Contains ¶
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 ¶
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.
Source Files