README ¶
godatastructures
Godatastructures is a collection of useful, performant, and threadsafe Go datastructures.
NOTE: only tested with Go 1.3+.
Augmented Tree
Interval tree for collision in ndimensional ranges. Implemented via a redblack augmented tree. Extra dimensions are handled in simultaneous inserts/queries to save space although this may result in suboptimal time complexity. Intersection determined using bit arrays. In a single dimension, inserts, deletes, and queries should be in O(log n) time.
Bitarray
Bitarray used to detect existence without having to resort to hashing with hashmaps. Requires entities have a uint64 unique identifier. Two implementations exist, regular and sparse. Sparse saves a great deal of space but insertions are O(log n). There are some useful functions on the BitArray interface to detect intersection between two bitarrays. This package also includes bitmaps of length 32 and 64 that provide increased speed and O(1) for all operations by storing the bitmaps in unsigned integers rather than arrays.
Futures
A helpful tool to send a "broadcast" message to listeners. Channels have the issue that once one listener takes a message from a channel the other listeners aren't notified. There were many cases when I wanted to notify many listeners of a single event and this package helps.
Queue
Package contains both a normal and priority queue. Both implementations never block on send and grow as much as necessary. Both also only return errors if you attempt to push to a disposed queue and will not panic like sending a message on a closed channel. The priority queue also allows you to place items in priority order inside the queue. If you give a useful hint to the regular queue, it is actually faster than a channel. The priority queue is somewhat slow currently and targeted for an update to a Fibonacci heap.
Also included in the queue package is a MPMC threadsafe ring buffer. This is a block full/empty queue, but will return a blocked thread if the queue is disposed while a thread is blocked. This can be used to synchronize goroutines and ensure goroutines quit so objects can be GC'd. Threadsafety is achieved using only CAS operations making this queue quite fast. Benchmarks can be found in that package.
Range Tree
Useful to determine if ndimensional points fall within an ndimensional range. Not a typical range tree however, as we are actually using an ndimensional sorted list of points as this proved to be simpler and faster than attempting a traditional range tree while saving space on any dimension greater than one. Inserts are typical BBST times at O(log n^d) where d is the number of dimensions.
Set
Our Set implementation is very simple, accepts items of type interface{}
and
includes only a few methods. If your application requires a richer Set
implementation over lists of type sort.Interface
, see
xtgo/set and
goware/set.
Threadsafe
A package that is meant to contain some commonly used items but in a threadsafe way. Example: there's a threadsafe error in there as I commonly found myself wanting to set an error in many threads at the same time (yes, I know, but channels are slow).
AVL Tree
This is an example of a branch copy immutable AVL BBST. Any operation on a node makes a copy of that node's branch. Because of this, this tree is inherently threadsafe although the writes will likely still need to be serialized. This structure is good if your use case is a large number of reads and infrequent writes as reads will be highly available but writes somewhat slow due to the copying. This structure serves as a basis for a large number of functional data structures.
XFast Trie
An interesting design that treats integers as words and uses a trie structure to reduce time complexities by matching prefixes. This structure is really fast for finding values or making predecessor/successor types of queries, but also results in greater than linear space consumption. The exact time complexities can be found in that package.
YFast Trie
An extension of the XFast trie in which an XFast trie is combined with some other ordered data structure to reduce space consumption and improve CRUD types of operations. These secondary structures are often BSTs, but our implementation uses a simple ordered list as I believe this improves cache locality. We also use fixed size buckets to aid in parallelization of operations. Exact time complexities are in that package.
Fast integer hashmap
A datastructure used for checking existence but without knowing the bounds of your data. If you have a limited small bounds, the bitarray package might be a better choice. This implementation uses a fairly simple hashing algorithm combined with linear probing and a flat datastructure to provide optimal performance up to a few million integers (faster than the native Golang implementation). Beyond that, the native implementation is faster (I believe they are using a large ary Btree). In the future, this will be implemented with a Btree for scale.
Skiplist
An ordered structure that provides amortized logarithmic operations but without the complication of rotations that are required by BSTs. In testing, however, the performance of the skip list is often far worse than the guaranteed log n time of a BBST. Tall nodes tend to "cast shadows", especially when large bitsizes are required as the optimum maximum height for a node is often based on this. More detailed performance characteristics are provided in that package.
Sort
The sort package implements a multithreaded bucket sort that can be up to 3x faster than the native Golang sort package. These buckets are then merged using a symmetrical merge, similar to the stable sort in the Golang package. However, our algorithm is modified so that two sorted lists can be merged by using symmetrical decomposition.
Numerics
Early work on some nonlinear optimization problems. The initial implementation allows a simple use case with either linear or nonlinear constraints. You can find min/max or target an optimal value. The package currently employs a probabilistic global restart system in an attempt to avoid local critical points. More details can be found in that package.
B+ Tree
Initial implementation of a B+ tree. Delete method still needs added as well as some performance optimization. Specific performance characteristics can be found in that package. Despite the theoretical superiority of BSTs, the Btree often has better all around performance due to cache locality. The current implementation is mutable, but the immutable AVL tree can be used to build an immutable version. Unfortunately, to make the Btree generic we require an interface and the most expensive operation in CPU profiling is the interface method which in turn calls into runtime.assertI2T. We need generics.
Immutable B Tree
A btree based on two principals, immutablability and concurrency.
Somewhat slow for single value lookups and puts, it is very fast for bulk operations.
A persister can be injected to make this index persistent.
Ctrie
A concurrent, lockfree hash array mapped trie with efficient nonblocking snapshots. For lookups, Ctries have comparable performance to concurrent skip lists and concurrent hashmaps. One key advantage of Ctries is they are dynamically allocated. Memory consumption is always proportional to the number of keys in the Ctrie, while hashmaps typically have to grow and shrink. Lookups, inserts, and removes are O(logn).
One interesting advantage Ctries have over traditional concurrent data structures is support for lockfree, linearizable, constanttime snapshots. Most concurrent data structures do not support snapshots, instead opting for locks or requiring a quiescent state. This allows Ctries to have O(1) iterator creation and clear operations and O(logn) size retrieval.
Dtrie
A persistent hash trie that dynamically expands or shrinks to provide efficient memory allocation. Being persistent, the Dtrie is immutable and any modification yields a new version of the Dtrie rather than changing the original. Bitmapped nodes allow for O(log32(n)) get, remove, and update operations. Insertions are O(n) and iteration is O(1).
Persistent List
A persistent, immutable linked list. All write operations yield a new, updated structure which preserve and reuse previous versions. This uses a very functional, consstyle of list manipulation. Insert, get, remove, and size operations are O(n) as you would expect.
Installation
 Install Go 1.3 or higher.
 Run
go get github.com/Workiva/godatastructures/...
Updating
When new code is merged to master, you can use
go get u github.com/Workiva/godatastructures/...
To retrieve the latest version of godatastructures.
Testing
To run all the unit tests use these commands:
cd $GOPATH/src/github.com/Workiva/godatastructures
go get t u ./...
go test ./...
Once you've done this once, you can simply use this command to run all unit tests:
go test ./...
Contributing
Requirements to commit here:
 Branch off master, PR back to master.
gofmt
'd code. Compliance with these guidelines
 Unit test coverage
 Good commit messages
Maintainers
 Dustin Hiatt <dustin.hiatt@workiva.com>
 Alexander Campbell <alexander.campbell@workiva.com>
Documentation ¶
Overview ¶
Package datastructures exists solely to aid consumers of the godatastructures library when using dependency managers. Depman, for instance, will work correctly with any datastructure by simply importing this package instead of each subpackage individually.
For more information about the datastructures package, see the README at
http://github.com/Workiva/godatastructures
Directories ¶
Path  Synopsis 

Package augmentedtree is designed to be useful when checking for intersection of ranges in ndimensions.

Package augmentedtree is designed to be useful when checking for intersection of ranges in ndimensions. 
Package bitarray implements a bit array.

Package bitarray implements a bit array. 
btree


immutable
Package btree provides a very specific set implementation for k/v lookup.

Package btree provides a very specific set implementation for k/v lookup. 
palm
Package palm implements parallel architecturefriendly latchfree modifications (PALM).

Package palm implements parallel architecturefriendly latchfree modifications (PALM). 
plus
Package btree/plus implements the ubiquitous B+ tree.

Package btree/plus implements the ubiquitous B+ tree. 
Package futures is useful for broadcasting an identical message to a multitude of listeners as opposed to channels which will choose a listener at random if multiple listeners are listening to the same channel.

Package futures is useful for broadcasting an identical message to a multitude of listeners as opposed to channels which will choose a listener at random if multiple listeners are listening to the same channel. 
hashmap


fastinteger
Package fastinteger is designed to provide a very primitive implementation of a hash map for unsigned integer keys and values.

Package fastinteger is designed to provide a very primitive implementation of a hash map for unsigned integer keys and values. 
Package list provides list implementations.

Package list provides list implementations. 
numerics


hilbert
Package Hilbert is designed to allow consumers to find the Hilbert distance on the Hilbert curve if given a 2 dimensional coordinate.

Package Hilbert is designed to allow consumers to find the Hilbert distance on the Hilbert curve if given a 2 dimensional coordinate. 
Package queue includes a regular queue and a priority queue.

Package queue includes a regular queue and a priority queue. 
Package rangetree is designed to store ndimensional data in an easytoquery way.

Package rangetree is designed to store ndimensional data in an easytoquery way. 
skiplist
Package skiplist implements an ndimensional rangetree based on a skip list.

Package skiplist implements an ndimensional rangetree based on a skip list. 
hilbert
Package hilbert implements a Hilbert Rtree based on PALM principles to improve multithreaded performance.

Package hilbert implements a Hilbert Rtree based on PALM principles to improve multithreaded performance. 
Package Int64 simply adds an Int64typed version of the standard library's sort/IntSlice implementation.

Package Int64 simply adds an Int64typed version of the standard library's sort/IntSlice implementation. 
skip
Package skip defines a skiplist datastructure.

Package skip defines a skiplist datastructure. 
threadsafe


err
Package err implements a threadsafe error interface.

Package err implements a threadsafe error interface. 
tree


avl
Package avl includes an immutable AVL tree.

Package avl includes an immutable AVL tree. 
trie


ctrie
Package ctrie provides an implementation of the Ctrie data structure, which is a concurrent, lockfree hash trie.

Package ctrie provides an implementation of the Ctrie data structure, which is a concurrent, lockfree hash trie. 
dtrie
Package dtrie provides an implementation of the dtrie data structure, which is a persistent hash trie that dynamically expands or shrinks to provide efficient memory allocation.

Package dtrie provides an implementation of the dtrie data structure, which is a persistent hash trie that dynamically expands or shrinks to provide efficient memory allocation. 
xfast
Package xfast provides access to a sorted tree that treats integers as if they were words of m bits, where m can be 8, 16, 32, or 64.

Package xfast provides access to a sorted tree that treats integers as if they were words of m bits, where m can be 8, 16, 32, or 64. 
yfast
Package yfast implements a yfast trie.

Package yfast implements a yfast trie. 