Awesome Open Source
Awesome Open Source

Treap

Tread-safe, persistent treaps in pure Go.

tests Godoc Reference Go Report Card

Installation

go get github.com/lthibault/treap

Treap is tested using go 1.14 and later, but is likely to work with earlier versions.

Why Treaps?

Most developers are familiar with maps and heaps.

  • Maps provide keyed lookups. Some even sort entries by key.
  • Heaps provide priority-ordering, with fast inserts and pops.

But what if you need both? And what if it needs to be both thread-safe, and non-blocking?

Enter the Immutable Treap.

Immutable treaps are persistent datastructures that provide:

  • Keyed lookups (like maps)
  • Priority ordering, pops and weighted inserts (like heaps)
  • Wait-free concurrency through immutability
  • Memory-efficiency through structural sharing
  • O(log n) time complexity for all operations

When used in conjunction with atomic.CompareAndSwapPointer, it is possible to read from a treap without ever blocking -- even in the presence of concurrent writers! Your typical CAS-loop will look like this:

type Foo struct {
    ptr unsafe.Pointer  // a *treap.Node
}

func (f *Foo) AddItem(key string, value, weight int) {
    for {
        old := (*treap.Node)(atomic.LoadPointer(&f.ptr))
        new, _ := handle.Upsert(old, key, value, weight)

        // attempt CAS
        if atomic.CompareAndSwapPointer(&f.ptr,
            unsafe.Pointer(old),
            unsafe.Pointer(new),
        ) {
            break  // value successfully set; we're done
        }
    }
}

In addition, this package features zero external dependencies and extensive test coverage.

Usage

The treap data-structure is purely functional and immutable. Methods like Insert and Delete return a new treap containing the desired modifications.

A fully-runnable version of the following example can be found in example_test.go.

package main

import (
    "fmt"

    "github.com/lthibault/treap"
)

// Treap operations are performed by a lightweight handle.  Usually, you'll create a
// single global handle and share it between goroutines.  Handle's methods are thread-
// safe.
//
// A handle is defined by it's comparison functions (type `treap.Comparator`).
var handle = treap.Handle{
    // CompareKeys is used to store and receive mapped entries.  The comparator must be
    // compatible with the Go type used for keys.  In this example, we'll use strings as
    // keys.
    CompareKeys: treap.StringComparator,

    // CompareWeights is used to maintain priority-ordering of mapped entries, providing
    // us with fast `Pop`, `Insert` and `SetWeight` operations.  You'll usually want
    // to use a `treap.IntComparator` for weights, but you can use any comparison
    // function you require.  Try it with `treap.TimeComparator`!
    //
    // Note that treaps are min-heaps by default, so `Pop` will always return the item
    // with the _smallest_ weight.  You can easily switch to a max-heap by using
    // `treap.MaxTreap`, if required.
    CompareWeights: treap.IntComparator,
}

func main() {
    // We define an empty root node.  Don't worry -- there's no initialization required!
    var root *treap.Node

    // We're going to insert each of these boxers into the treap, and observe how the
    // treap treap provides us with a combination of map and heap semantics.
    for _, boxer := range []struct{
        FirstName, LastName string
        Weight int
    }{{
        FirstName: "Cassius",
        LastName: "Clay",
        Weight: 210,
    }, {
        FirstName: "Joe",
        LastName: "Frazier",
        Weight: 215,
    }, {
        FirstName: "Marcel",
        LastName: "Cerdan",
        Weight: 154,
    }, {
        FirstName: "Jake",
        LastName: "LaMotta",
        Weight: 160,
    }}{
        // Again, the treap is a purely-functional, persistent data structure.  `Insert`
        // returns a _new_ heap, which replaces `root` on each iteration.
        //
        // When used in conjunction with `atomic.CompareAndSwapPointer`, it is possible
        // to read from a treap without ever blocking -- even in the presence of
        // concurrent writers!
        root, _ = handle.Insert(root, boxer.FirstName, boxer.LastName, boxer.Weight)
    }

    // Now that we've populated the treap, we can query it like an ordinary map.
    lastn, _ := handle.Get(root, "Cassius")
    fmt.Printf("Cassius %s\n", lastn)  // prints:  "Cassius Clay"

    // Treaps also behave like binary heaps.  Let's start by peeking at the first value
    // in the resulting priority queue.  Remember:  this is a min-heap by default.
    fmt.Printf("%s %s, %d lbs\n", root.Key, root.Value, root.Weight)

    // Woah, that was easy!  Now let's Pop that first value off of the heap.
    // Remember:  this is an immutable data-structure, so `Pop` doesn't actually mutate
    // any state!
    lastn, _ = handle.Pop(root)
    fmt.Printf("Marcel %s\n", lastn)  // prints:  "Marcel Cerdan"

    // Jake LaMotta moved up to the heavyweight class late in his career.  Let's made an
    // adjustment to his weight.
    root, _ = handle.SetWeight(root, "Jake", 205)

    // Let's list our boxers in ascending order of weight.  You may have noticed
    // there's no `PopNode` method on `treap.Handler`.  This is not a mistake!  A `Pop`
    // is just a merge on the root node's subtrees.  Check it out:
    for n := root; n != nil; {
        fmt.Printf("%s %s: %d\n", n.Key, n.Value, n.Weight)
        n = handle.Merge(n.Left, n.Right)
    }

    // Lastly, we can iterate through the treap in key-order (smallest to largest).
    // To do this, we use an iterator.  Contrary to treaps, iterators are stateful and
    // mutable!  As such, they are NOT thread-safe.  However, multiple concurrent
    // iterators can traverse the same treap safely.
    for iterator := handle.Iter(root); iterator.Node != nil; iterator.Next(); {
        fmt.Printf("%s %s: %d\n", iterator.Key, iterator.Value, iterator.Weight)
    }
}


Alternative Project Comparisons
Related Awesome Lists
Top Programming Languages
Top Projects

Get A Weekly Email With Trending Projects For These Topics
No Spam. Unsubscribe easily at any time.
Golang (158,041
Map (32,543
Tree (20,459
Thread (12,451
Data Structure (9,583
Priority (3,539
Concurrency (3,272
Heap (3,060
Immutable (2,812
Concurrent (2,715
Threadsafe (416
Persistent Data Structure (53
Treap (14