A collection of useful, performant, and threadsafe Go datastructures.

Overview

go-datastructures

Go-datastructures is a collection of useful, performant, and threadsafe Go datastructures.

NOTE: only tested with Go 1.3+.

Augmented Tree

Interval tree for collision in n-dimensional ranges. Implemented via a red-black 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.

Fibonacci Heap

A standard Fibonacci heap providing the usual operations. Can be useful in executing Dijkstra or Prim's algorithms in the theoretically minimal time. Also useful as a general-purpose priority queue. The special thing about Fibonacci heaps versus other heap variants is the cheap decrease-key operation. This heap has a constant complexity for find minimum, insert and merge of two heaps, an amortized constant complexity for decrease key and O(log(n)) complexity for a deletion or dequeue minimum. In practice the constant factors are large, so Fibonacci heaps could be slower than Pairing heaps, depending on usage. Benchmarks - in the project subfolder. The heap has not been designed for thread-safety.

Range Tree

Useful to determine if n-dimensional points fall within an n-dimensional range. Not a typical range tree however, as we are actually using an n-dimensional 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.

X-Fast 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.

Y-Fast Trie

An extension of the X-Fast trie in which an X-Fast 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 B-tree). In the future, this will be implemented with a B-tree 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 B-tree 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 B-tree 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, lock-free hash array mapped trie with efficient non-blocking 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 lock-free, linearizable, constant-time 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, cons-style of list manipulation. Insert, get, remove, and size operations are O(n) as you would expect.

Simple Graph

A mutable, non-persistent undirected graph where parallel edges and self-loops are not permitted. Operations to add an edge as well as retrieve the total number of vertices/edges are O(1) while the operation to retrieve the vertices adjacent to a target is O(n). For more details see wikipedia

Installation

  1. Install Go 1.3 or higher.
  2. Run go get github.com/Workiva/go-datastructures/...

Updating

When new code is merged to master, you can use

go get -u github.com/Workiva/go-datastructures/...

To retrieve the latest version of go-datastructures.

Testing

To run all the unit tests use these commands:

cd $GOPATH/src/github.com/Workiva/go-datastructures
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:

Maintainers

Comments
  • ctrie: iterator performance

    ctrie: iterator performance

    I've been comparing an implementation of a database cache using ctrie & the immutable avl tree. The ctrie is more efficient except when iterating. I think the ctrie iteration scheme of using a goroutine and channel gives pretty bad performance compared to the straight traversal of the avl tree nodes, plus the channel is prone to leakage (as noted in the code).

    opened by newhook 13
  • Make rangetree ranges inclusive.

    Make rangetree ranges inclusive.

    Makes rangetree ranges inclusive. Easier to reason about I think and matches what we are trying to do elsewhere. This will probably break the older repos, but should be an easy change for @alexandercampbell-wf I think.

    @alexandercampbell-wf @rosshendrickson-wf @ericolson-wf @seanstrickland-wf @matthinrichsen-wf @wesleybalvanz-wf @blakewilson-wf

    opened by dustinhiatt-wf 13
  • Avoid deadlock between Put and Get

    Avoid deadlock between Put and Get

    There is a problem where the batch channel fills up and Puts hold the lock preventing Gets from catching up.

    @dustinhiatt-wf @brianshannan-wf @tylertreat @alexandercampbell-wf

    opened by stevenosborne-wf 11
  • Implement heap-based priority queue

    Implement heap-based priority queue

    This change provides O(log n) performance for inserts and removals. The exported interfaces remain intact, only internal implementation has been modified.

    Changes:

    • Maintain heap property on item update/retrieval
    • Avoid duplicates with a map[Item]bool variable
    • Use push() and pop() naming for internal operations
    opened by ichinaski 11
  • Future

    Future

    I think it is better to make future to look like

    type Future struct {
        m sync.Mutex
        val interface{}
        err error
        wait chan struct{}
        filled bool
        timeout *time.Timer
    }
    
    func NewFuture(d time.Duration) (f *Future) {
        ch := make(chan struct{})
        f = &Future { wait: ch }
        if d > 0 {
            f.timeout = time.AfterFunc(d, f.timedout)
        }
        return
    }
    
    func (f *Future) timedout() {
        f.m.Lock()
        if !f.filled {
            f.err = errors.New("timeout")
            close(f.wait)
            f.filled = true
            f.timeout = nil
        }
        f.m.Unlock()
    }
    
    func (f *Future) Fill(val interface{}) (err error) {
        f.m.Lock()
        if !f.filled {
            f.val = val
            if f.timeout != nil {
                f.timeout.Stop()
                f.timeout = nil
            }
            close(f.wait)
            f.filled = true
        } else if (f.err != nil) {
            err = f.err
        } else {
            err = errors.New("already filled")
        }
        f.m.Unlock()
        return
    }
    
    func (f *Future) Wait() <-chan struct{} {
        return f.wait
    }
    
    func (f *Future) Value() (interface{}, error) {
        /* normally one will call f.Value() only after f.Wait() already closed,
           but lets check it once again */
        <- f.wait
        return f.val, f.err
    }
    

    Not tested.

    opened by funny-falcon 10
  • ctrie data race

    ctrie data race

    I just got a report of data race in the ctrie impl on committed.

    func (c *Ctrie) rdcssRoot(old *iNode, expected *mainNode, nv *iNode) bool {
        desc := &iNode{
            rdcss: &rdcssDescriptor{
                old:      old,
                expected: expected,
                nv:       nv,
            },
        }
        if c.casRoot(old, desc) {
            c.rdcssComplete(false)
            return desc.rdcss.committed
        }
        return false
    }
    
    func (c *Ctrie) rdcssComplete(abort bool) *iNode {
    ...
                if oldeMain == exp {
                // Commit the RDCSS.
                if c.casRoot(r, nv) {
                    desc.committed = true
                    return nv
    
    Read by goroutine 9:
      customerio/chgbuf/ctrie.(*Ctrie).rdcssRoot()
          /Users/matthew/src/services/src/customerio/chgbuf/ctrie/ctrie.go:881 +0x1e7
      customerio/chgbuf/ctrie.(*Ctrie).Snapshot()
          /Users/matthew/src/services/src/customerio/chgbuf/ctrie/ctrie.go:318 +0xb7
    ...
    Previous write by goroutine 6:
      customerio/chgbuf/ctrie.(*Ctrie).rdcssComplete()
          /Users/matthew/src/services/src/customerio/chgbuf/ctrie/ctrie.go:912 +0x1a1
      customerio/chgbuf/ctrie.(*Ctrie).rdcssReadRoot()
          /Users/matthew/src/services/src/customerio/chgbuf/ctrie/ctrie.go:863 +0x78
      customerio/chgbuf/ctrie.(*Ctrie).readRoot()
          /Users/matthew/src/services/src/customerio/chgbuf/ctrie/ctrie.go:855 +0x33
      customerio/chgbuf/ctrie.(*Ctrie).ReadOnlySnapshot()
    ...
    
    opened by newhook 9
  • Bitmap

    Bitmap

    I figured that the bitmapping used in the Dtrie could also be useful to other data structures. I will change the Dtrie implementation to use this package but I was not sure if you would want that done in a separate PR.

    Benchmarks for PopCount: BenchmarkPopCount32-4 1000000000 2.09 ns/op BenchmarkPopCount64-4 1000000000 2.59 ns/op

    opened by Theodus 8
  • Ctrie

    Ctrie

    This includes an implementation of a Ctrie, which is a concurrent, lock-free hash trie. This supports insert, remove, and lookup. Snapshot isn't supported yet, but I plan to add it later.

    Benchmarks if you're curious: BenchmarkInsert-8 3000000 449 ns/op BenchmarkLookup-8 10000000 224 ns/op BenchmarkRemove-8 10000000 192 ns/op

    This also includes an implementation of a persistent, immutable linked list (which the Ctrie uses).

    @dustinhiatt-wf @alexandercampbell-wf @beaulyddon-wf @tannermiller-wf @rosshendrickson-wf @stevenosborne-wf

    opened by tylertreat-wf 8
  • Tiny Set optimizations

    Tiny Set optimizations

    1. bool is replaced with struct{} to save some memory in large sets
    2. Use direct call of (R)Unlock in really plain simple methods like Exists, Len, Clear to speedup Set

    with defer()

    BenchmarkLen    50000000            52.8 ns/op
    BenchmarkExists 20000000            93.4 ns/op
    BenchmarkClear  10000000           215 ns/op
    

    without defer()

    BenchmarkLen    100000000           21.9 ns/op
    BenchmarkExists 50000000            51.5 ns/op
    BenchmarkClear  10000000           167 ns/op
    
    opened by noxiouz 8
  • RM-30330 Workiva-Build: Update Dockerfile to mirror smithy.yaml

    RM-30330 Workiva-Build: Update Dockerfile to mirror smithy.yaml

    Overview

    In order to improve build isolation, reduce costs, reduce support burden, remove black magic, and improve local consistency, we are migrating away from smithy.yaml and existing Smithy infrastructure to Dockerfile builds supported by off the shelf AWS resources.

    Reviewing and merging this PR is the first step in that process; this PR simply copies the contents of your smithy.yaml into a more explicit Dockerfile. In order to begin running Dockerfile builds you will need to enable Dockerfile builds from your repo configuration page in Smithy. Once you have enabled Dockerfile builds for your repo, rebuilding the PR build in smithy will trigger the newly enabled Dockefile build.

    Expectations

    With only a couple of exceptions the behavior of this new Dockerfile should match the existing behavior in your smithy.yaml Therefore, our expectations are for you to merge this PR as soon as possible. If for any reason you discover a problem post merge, you can disable the new builds and re-enable smithy.yaml builds in your repo configuration page in Smithy

    Support/Questions

    The migration to Dockerfile builds is our top priority, so please reach out to us if you have any questions, comments, or concerns during this process. Non-urgent questions should go into Confluence Questions and urgent support can be requested in the Support: Build Tools Hipchat Room

    More Info

    Information about the migration to dockerfile can be found here A user guide for Dockerfile builds can be found here

    @brianshannan-wf

    opened by ci-push-wf 7
  • Dtrie

    Dtrie

    This is an implementation of a persistent hash array mapped trie that expands or shrinks to provide efficient memory allocation. Details on the papers that this project is based on can be found at github.com/theodus/dtrie.

    Benchmarks: BenchmarkInsert-4 5000000 547 ns/op 164 B/op 2 allocs/op BenchmarkGet-4 10000000 250 ns/op 8 B/op 1 allocs/op BenchmarkRemove-4 10000000 253 ns/op 8 B/op 1 allocs/op BenchmarkUpdate-4 5000000 383 ns/op 55 B/op 3 allocs/op

    opened by Theodus 7
  • RingBuffer with a size of 1 should not be allowed due to an insert bug, so increment a size of one, by one.

    RingBuffer with a size of 1 should not be allowed due to an insert bug, so increment a size of one, by one.

    RingBuffer with a size of 1 will have a mask of 0 which uncovers a bug in the algorithm since the mask value must only contain ones (left padded with zeros) if it's represented in its binary format (e.g. '0111', '0011 1111', etc.). So we should not allow having RingBuffer queues with a size of 1. We can simply fix this by incrementing the size inside the RingBuffer's init method.

    With a full RingBuffer of size 1, insert operations replace the existing item in the queue and then puts the RingBuffer into an invalid state.

    opened by hedisam 2
  • Change traverse implemention to in-order traverse

    Change traverse implemention to in-order traverse

    the current traverse implemention has several weakness:

    1. unable to stop traverse, thus unable to reduce traverse time complexity around O(logN)
    2. out-of-order, ordinary traverse method should be pre-order, in-order, post-order, but the current implemention belongs none of them
    3. memory cost, since traversing in flat levels, maximum memory usage will reach to nearly half tree width
    opened by qiuchengxuan 1
  • State of rtree different after insert/delete (0,0,0,0) and insert/delete (0,0,10,10)

    State of rtree different after insert/delete (0,0,0,0) and insert/delete (0,0,10,10)

    The state of rtree is different after insert/delete (0,0,0,0) and insert/delete (0,0,10,10).

    The difference is that maxHilbert changed from 0 to 34 in the (0,0,10,10) case. Is this intentional or a bug? I expect that the rtree behaves the same, independently of what kind of rectangles I have.

    Maybe it's not relevant but I have one case, where an other rTree gives a correct search result whereas this one here is wrong. I search for P1 = (1,1,1,1) and P2 = (1001,1,1001,1) The sequence is:

    Node-1: (0,0, 2000, 1000) Node-12: (0,0,2000,1000)

    P1 and P2 are correctly found.

    Adding Node-13 and changing Node-12 by remove and insert:

    Node-1: (0,0, 2000, 1000) Node-12: (0,0,1000,1000) Node-13: (1000,0,2000,1000)

    P1 correctly found, P2 reports Node-1 and Node-12 as result, which is wrong.

    opened by Robert-M-Muench 3
  • Will rtree recognize coordinate/dimension changes of inserted rects?

    Will rtree recognize coordinate/dimension changes of inserted rects?

    If I have a rtree where I insert 50 rectangles and change the coordinates/dimensions of some rectangles afterwards, will rtree recognize this and adapt the internal data structure to work correctly? Or do I have to somehow let the tree know, that some rectangles changed?

    opened by Robert-M-Muench 1
  • RingBuffer's Offer returns false (queue full) even when there is space in queue

    RingBuffer's Offer returns false (queue full) even when there is space in queue

    As per documentation, rb.Offer should return false only when the queue is full:

    // Offer adds the provided item to the queue if there is space.  If the queue
    // is full, this call will return false.  An error will be returned if the
    // queue is disposed.
    func (rb *RingBuffer) Offer(item interface{}) (bool, error) {
    	return rb.put(item, true)
    }
    

    But, when adding elements to queue by concurrently calling rb.Offer, It returns false even when there is enough space. The following test file can reproduce the issue.

    package test
    
    import (
    	"sync"
    	"testing"
    
    	"github.com/Workiva/go-datastructures/queue"
    )
    
    func TestRingQueueOffer_parallel(t *testing.T) {
    	size := 256
    	parallelGoroutines := 8
    
    	rb := queue.NewRingBuffer(uint64(size * parallelGoroutines))
    
    	wg := new(sync.WaitGroup)
    	wg.Add(parallelGoroutines)
    
    	for i := 0; i < parallelGoroutines; i++ {
    		go func(id int) {
    			defer wg.Done()
    
    			for el := 1; el <= size; el++ {
    				ok, err := rb.Offer(el)
    				if err != nil {
    					t.Errorf("error in goroutine-%d: %v", id, err)
    					return
    				}
    
    				if !ok {
    					t.Errorf("queue full before expected on adding %d element, len: %d, cap: %d ", el, rb.Len(), rb.Cap())
    				}
    			}
    		}(i)
    	}
    
    	wg.Wait()
    }
    

    On running the above test file, I got:

    --- FAIL: TestRingQueueOffer_parallel (0.00s)
        ring_buffer_test.go:31: queue full before expected on adding 1 element, len: 49, cap: 2048 
        ring_buffer_test.go:31: queue full before expected on adding 256 element, len: 1391, cap: 2048 
        ring_buffer_test.go:31: queue full before expected on adding 1 element, len: 1730, cap: 2048 
    FAIL
    FAIL	command-line-arguments	0.028s
    FAIL
    
    opened by SharanSharathi 0
  • rtree / hilbert / func New(bufferSize, ary uint64) => what is parameter ary?

    rtree / hilbert / func New(bufferSize, ary uint64) => what is parameter ary?

    I tried New(100,2) for a tree managing 2D rectangles. But that failed... I used New(100,3) which works but I don't know why.

    So, what does this parameter specify?

    And if I want to manage, let's say 5D "rectangles" I just extend my rectangle definition to 5 dimensions?

    opened by Robert-M-Muench 0
Releases(v1.0.53)
  • v1.0.53(Mar 29, 2021)

    Info

    Build: https://ci.webfilings.com/build/2762799 Skynet Results: https://wf-skynet-hrd.appspot.com/apps/test/smithy/2762799/latest Pipeline: No Pipeline This patch release includes the following changes:

    Miscellaneous

    • [x] #217 Migrate to Go Modules + Off of Smithy-runner

    Notes created on Monday, March 29 03:14 PM UTC

    Source code(tar.gz)
    Source code(zip)
  • v1.0.52(Mar 9, 2020)

    Info

    Build: https://ci.webfilings.com/build/2150392 Skynet Results: https://wf-skynet-hrd.appspot.com/apps/test/smithy/2150392/latest Pipeline: No Pipeline This patch release includes the following changes:

    Miscellaneous

    • [x] #207 Add nil check to Dtrie.Get()

    Notes created on Monday, March 09 02:29 PM UTC

    Source code(tar.gz)
    Source code(zip)
  • v1.0.51(Mar 2, 2020)

    Info

    Build: https://ci.webfilings.com/build/2139022 Skynet Results: https://wf-skynet-hrd.appspot.com/apps/test/smithy/2139022/latest Pipeline: No Pipeline This patch release includes the following changes:

    Miscellaneous

    • [x] #205 Reduce RingBuffer heap allocation

    Notes created on Monday, March 02 07:31 PM UTC

    Source code(tar.gz)
    Source code(zip)
  • v1.0.50(Aug 29, 2018)

    Info

    This patch release includes the following changes:

    Miscellaneous

    • [x] #198 RM-30900 Ctrie hash collisions
      • RM-30900 RELEASE go-datastructures v1.0.49

    Notes created on Wednesday, August 29 08:59 PM UTC

    Source code(tar.gz)
    Source code(zip)
  • v1.0.49(Aug 29, 2018)

    Info

    This patch release includes the following changes:

    Miscellaneous

    • [x] #199 RM-30900 Drop zero-block values in sparse vs dense AND
      • RM-30900 RELEASE go-datastructures v1.0.49

    Notes created on Wednesday, August 29 08:16 PM UTC

    Source code(tar.gz)
    Source code(zip)
  • v1.0.48(Jun 12, 2018)

    Info

    This patch release includes the following changes:

    Miscellaneous

    • [x] #196 RM-30330 Workiva-Build: Update Dockerfile to mirror smithy.yaml
      • RM-30330 RELEASE go-datastructures v1.0.48

    Notes created on Tuesday, June 12 03:50 PM UTC

    Source code(tar.gz)
    Source code(zip)
  • v1.0.47(May 25, 2018)

    Info

    This patch release includes the following changes:

    Miscellaneous

    • [x] #192 btree: remove dependency on github.com/satori/go.uuid

    Notes created on Friday, May 25 01:32 PM UTC

    Source code(tar.gz)
    Source code(zip)
  • v1.0.46(Apr 12, 2018)

    Info

    This patch release includes the following changes:

    Miscellaneous

    • [x] #178 RM-23161 Add Simple Graph Implementation/tests
      • RM-23161 RELEASE go-datastructures v1.0.41

    Notes created on Thursday, April 12 01:39 PM UTC

    Source code(tar.gz)
    Source code(zip)
  • v1.0.45(Apr 12, 2018)

    Info

    This patch release includes the following changes:

    Miscellaneous

    • [x] #186 RM-25125 Fix #183
      • RM-25125 RELEASE go-datastructures v1.0.44

    Notes created on Thursday, April 12 01:26 PM UTC

    Source code(tar.gz)
    Source code(zip)
  • v1.0.44(Feb 13, 2018)

    Info

    Shipyard Build: (waiting for build to complete) Skynet Results: (waiting for Skynet results) This patch release includes the following changes:

    Miscellaneous

    • [x] #185 RM-25125 Fix non aligned read
      • RM-25125 RELEASE go-datastructures v1.0.44

    Notes created on Tuesday, February 13 06:36 PM UTC

    Source code(tar.gz)
    Source code(zip)
  • v1.0.43(Dec 1, 2017)

    This patch release includes the following changes:

    Miscellaneous

    • [x] #179 RM-24272 travis: update go versions
      • RM-24272 RELEASE go-datastructures v1.0.42

    Notes created on Friday, December 01 07:11 PM UTC

    Source code(tar.gz)
    Source code(zip)
  • v1.0.42(Nov 7, 2017)

    This patch release includes the following changes:

    Miscellaneous

    • [x] #182 RM-24272 Fix that read-only snapshots shared state with original.
      • RM-24272 RELEASE go-datastructures v1.0.42

    Notes created on Tuesday, November 07 03:14 PM UTC

    Source code(tar.gz)
    Source code(zip)
  • v1.0.41(Oct 26, 2017)

    This patch release includes the following changes:

    Miscellaneous

    • [x] #155 [RED-659] Add Aviary.yaml
      • RED-659 Migrate raven configuration files to repo specific aviary.yaml files (P1 OKR)

    Notes created on Thursday, October 26 02:05 PM UTC

    Source code(tar.gz)
    Source code(zip)
  • v1.0.40(Sep 8, 2017)

    This patch release includes the following changes:

    Miscellaneous

    • [x] #175 RM-22582 Dependency tracking
      • RM-22582 RELEASE go-datastructures v1.0.40

    Notes created on Friday, September 08 02:47 PM UTC

    Source code(tar.gz)
    Source code(zip)
  • v1.0.39(Aug 10, 2017)

    This patch release includes the following changes:

    Miscellaneous

    • [x] #172 RM-19979 Fix that Ctrie iterator did not return entries from tNodes.
      • RM-19979 RELEASE go-datastructures v1.0.37

    Notes created on Thursday, August 10 08:46 PM UTC

    Source code(tar.gz)
    Source code(zip)
  • v1.0.38(Jul 19, 2017)

    This patch release includes the following changes:

    Miscellaneous

    • [x] #174 RM-21797 Remove Gosched call limiting
      • RM-21797 RELEASE go-datastructures v1.0.38

    Notes created on Wednesday, July 19 02:56 PM UTC

    Source code(tar.gz)
    Source code(zip)
  • v1.0.37(Jul 10, 2017)

    This patch release includes the following changes:

    Miscellaneous

    • [x] #173 RM-19979 Add Poll method to RingBuffer
      • RM-19979 RELEASE go-datastructures v1.0.37

    Notes created on Monday, July 10 09:12 PM UTC

    Source code(tar.gz)
    Source code(zip)
  • v1.0.36(May 3, 2017)

    This patch release includes the following changes:

    Miscellaneous

    • [x] #169 Set: Add unit test for New with entries

    Notes created on Wednesday, May 03 03:55 PM UTC

    Source code(tar.gz)
    Source code(zip)
  • v1.0.35(May 3, 2017)

    This patch release includes the following changes:

    Miscellaneous

    • [x] #168 Set: Remove obsolete whitespace from documentation

    Notes created on Wednesday, May 03 03:55 PM UTC

    Source code(tar.gz)
    Source code(zip)
  • v1.0.34(Mar 31, 2017)

  • v1.0.33(Mar 2, 2017)

    This patch release includes the following changes:

    Miscellaneous

    • [x] #161 Implement Fibonacci heap

    Notes created on Thursday, March 02 08:14 PM UTC

    Source code(tar.gz)
    Source code(zip)
  • v1.0.32(Jan 19, 2017)

    This patch release includes the following changes:

    Miscellaneous

    • [x] #159 Patch Panic on Augmented Interval Tree Traverse

    Notes created on Thursday, January 19 07:47 PM UTC

    Source code(tar.gz)
    Source code(zip)
  • v1.0.31(Dec 6, 2016)

    This patch release includes the following changes:

    Miscellaneous

    • [x] #158 Add Cache Implementation

    Notes created on Tuesday, December 06 03:12 PM UTC

    Source code(tar.gz)
    Source code(zip)
  • v1.0.30(Oct 27, 2016)

    This patch release includes the following changes:

    Miscellaneous

    • [x] #157 Add HasResult to Future

    Notes created on Thursday, October 27 07:53 PM UTC

    Source code(tar.gz)
    Source code(zip)
  • v1.0.29(Oct 27, 2016)

    This patch release includes the following changes:

    Miscellaneous

    • [x] #156 future/selectable: lazy allocate wait chan

    Notes created on Thursday, October 27 04:11 PM UTC

    Source code(tar.gz)
    Source code(zip)
  • v1.0.28(Aug 25, 2016)

    This patch release includes the following changes:

    Miscellaneous

    • [x] #153 Add an explicit timer and stop it

    Notes created on Thursday, August 25 08:40 PM UTC

    Source code(tar.gz)
    Source code(zip)
  • v1.0.27(Aug 18, 2016)

    This patch release includes the following changes:

    Miscellaneous

    • [x] #151 augmentedtree: add traverse func

    Notes created on Thursday, August 18 04:20 PM UTC

    Source code(tar.gz)
    Source code(zip)
  • v1.0.26(Aug 2, 2016)

    This patch release includes the following changes:

    Miscellaneous

    • [x] #149 Fix the bug where the capacity is incorrectly calculated.

    Notes created on Tuesday, August 02 03:45 PM UTC

    Source code(tar.gz)
    Source code(zip)
  • v1.0.25(Jul 6, 2016)

    This patch release includes the following changes:

    Miscellaneous

    • [x] #148 Sort keys before deleting.

    Notes created on Wednesday, July 06 02:34 PM UTC

    Source code(tar.gz)
    Source code(zip)
  • v1.0.24(Jun 27, 2016)

    This patch release includes the following changes:

    Miscellaneous

    • [x] #146 slice/skip: atomize SkipList.num operations
    • [x] #147 fix queue.Poll() memory leak

    Notes created on Monday, June 27 01:31 PM UTC

    Source code(tar.gz)
    Source code(zip)
Owner
Workiva
Workiva
Go datastructures for a generic world

Generic data structures for Go With the upcoming release of 1.18, it's now possible to build a library of generic data structures in Go. The purpose o

Camden Cheek 0 Nov 9, 2021
A threadsafe single-value cache for Go with a simple but flexible API

SVCache SVCache is a threadsafe, single-value cache with a simple but flexible API. When there is no fresh value in the cache, an attempt to retrieve

softwaretechnik.berlin 1 Jan 23, 2022
A fast, threadsafe skip list in Go

fast-skiplist Purpose As the basic building block of an in-memory data structure store, I needed an implementation of skip lists in Go. It needed to b

sean 240 Dec 2, 2022
Set is a useful collection but there is no built-in implementation in Go lang.

goset Set is a useful collection but there is no built-in implementation in Go lang. Why? The only one pkg which provides set operations now is golang

zoumo 50 Sep 26, 2022
AVL tree with some useful extensions written in Go

gocover An AVL tree (Adel'son-Vel'skii & Landis) is a binary search tree in which the heights of the left and right subtrees of the root differ by at

Michael Lore 28 Mar 23, 2022
fim is a collection of some popular frequent itemset mining algorithms implemented in Go.

fim fim is a collection of some popular frequent itemset mining algorithms implemented in Go. fim contains the implementations of the following algori

Paul Fedorow 7 Jul 14, 2022
Collection library using generics in Go

Collection Collection library using generics in Go Overview This is a library to provide useful collection data structures and methods for Gophers. Th

Hidetatz Yaginuma 11 Sep 4, 2022
Leetcode-in-go - A collection of solutions of leetcode problems solved in go!

Leetcode in Go A collection of solutions of leetcode problems solved in go! The problems are categorized based on their difficulty level. Easy Problem

null 0 Jan 8, 2022
estruct traverses javascript projects and maps all the dependencies and relationships to a JSON. the output can be used to build network visualizations of the project and document the architecture.

EStruct traverses javascript projects and maps all the dependencies and relationships to a JSON. The output can be used to build network visualizations of the project and document the architecture.

Ray Luxembourg 11 Jan 27, 2022
Golang string comparison and edit distance algorithms library, featuring : Levenshtein, LCS, Hamming, Damerau levenshtein (OSA and Adjacent transpositions algorithms), Jaro-Winkler, Cosine, etc...

Go-edlib : Edit distance and string comparison library Golang string comparison and edit distance algorithms library featuring : Levenshtein, LCS, Ham

Hugo Bollon 369 Nov 28, 2022
Go package for mapping values to and from space-filling curves, such as Hilbert and Peano curves.

Hilbert Go package for mapping values to and from space-filling curves, such as Hilbert and Peano curves. Documentation available here This is not an

Google 255 Sep 26, 2022
Levenshtein distance and similarity metrics with customizable edit costs and Winkler-like bonus for common prefix.

A Go package for calculating the Levenshtein distance between two strings This package implements distance and similarity metrics for strings, based o

AGExt 73 Nov 23, 2022
Decode / encode XML to/from map[string]interface{} (or JSON); extract values with dot-notation paths and wildcards. Replaces x2j and j2x packages.

mxj - to/from maps, XML and JSON Decode/encode XML to/from map[string]interface{} (or JSON) values, and extract/modify values from maps by key or key-

Charles Banning 534 Nov 30, 2022
Dasel - Select, put and delete data from JSON, TOML, YAML, XML and CSV files with a single tool.

Select, put and delete data from JSON, TOML, YAML, XML and CSV files with a single tool. Supports conversion between formats and can be used as a Go package.

Tom Wright 3.9k Nov 29, 2022
💯 Go Struct and Field validation, including Cross Field, Cross Struct, Map, Slice and Array diving

Package validator implements value validations for structs and individual fields based on tags.

Flamego 10 Nov 9, 2022
Go translations of the algorithms and clients in the textbook Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

Overview Go translations of the Java source code for the algorithms and clients in the textbook Algorithms, 4th Edition by Robert Sedgewick and Kevin

youngzy 172 Nov 24, 2022
Package iter provides generic, lazy iterators, functions for producing them from primitive types, as well as functions and methods for transforming and consuming them.

iter Package iter provides generic, lazy iterators, functions for producing them from primitive types, as well as functions and methods for transformi

Matthew Toohey 26 Sep 29, 2022
Snackbox - Snackbox can make it easier for customers to order snacks and rice boxes and do tracking

Catering Ecommerce Platform API Docs · Wireflow · Use Case Diagram · Entity Rela

Muhammad Arif Furqon 1 Oct 18, 2022
An app with Trie tree and Breve search Implementation CLI and HTTP both 🥳

Introduction LifeLongLearner project consists of two different parts. My English Vocabulary My Technical Book Notes All of them provided by me within

A.Samet İleri 15 Jul 1, 2022