tickettreap

README

tickettreap

[] (https://travis-ci.org/decred/dcrd) ![ISC License] (http://img.shields.io/badge/license-ISC-blue.svg) [] (http://godoc.org/github.com/decred/dcrd/blockchain/stake/internal/tickettreap)

Package tickettreap implements a treap data structure that is used to hold live tickets ordered by their key along with some associated data using a combination of binary search tree and heap semantics. It is a self-organizing and randomized data structure that doesn't require complex operations to maintain balance. Search, insert, and delete operations are all O(log n). Both mutable and immutable variants are provided.

The mutable variant is typically faster since it is able to simply update the treap when modifications are made. However, a mutable treap is not safe for concurrent access without careful use of locking by the caller and care must be taken when iterating since it can change out from under the iterator.

The immutable variant works by creating a new version of the treap for all mutations by replacing modified nodes with new nodes that have updated values while sharing all unmodified nodes with the previous version. This is extremely useful in concurrent applications since the caller only has to atomically replace the treap pointer with the newly returned version after performing any mutations. All readers can simply use their existing pointer as a snapshot since the treap it points to is immutable. This effectively provides O(1) snapshot capability with efficient memory usage characteristics since the old nodes only remain allocated until there are no longer any references to them.

Usage

This package is only used internally in the stake code and as such is not available for use outside of it.

License

Package tickettreap is licensed under the copyfree ISC License.

Documentation

Overview

Package tickettreap implements a treap data structure that is used to hold live tickets ordered by their key along with some associated data using a combination of binary search tree and heap semantics. It is a self-organizing and randomized data structure that doesn't require complex operations to maintain balance. Search, insert, and delete operations are all O(log n). Both mutable and immutable variants are provided.

The mutable variant is typically faster since it is able to simply update the treap when modifications are made. However, a mutable treap is not safe for concurrent access without careful use of locking by the caller and care must be taken when iterating since it can change out from under the iterator.

The immutable variant works by creating a new version of the treap for all mutations by replacing modified nodes with new nodes that have updated values while sharing all unmodified nodes with the previous version. This is extremely useful in concurrent applications since the caller only has to atomically replace the treap pointer with the newly returned version after performing any mutations. All readers can simply use their existing pointer as a snapshot since the treap it points to is immutable. This effectively provides O(1) snapshot capability with efficient memory usage characteristics since the old nodes only remain allocated until there are no longer any references to them.

Index

• type Immutable
  • func NewImmutable() *Immutable
  • func (t *Immutable) Delete(key Key) *Immutable
  • func (t *Immutable) FetchWinnersAndExpired(idxs []int, height uint32) ([]*Key, []*Key)
  • func (t *Immutable) ForEach(fn func(k Key, v *Value) bool)
  • func (t *Immutable) ForEachByHeight(heightLessThan uint32, fn func(k Key, v *Value) bool)
  • func (t *Immutable) Get(key Key) *Value
  • func (t *Immutable) GetByIndex(idx int) (Key, *Value)
  • func (t *Immutable) Has(key Key) bool
  • func (t *Immutable) Len() int
  • func (t *Immutable) Put(key Key, value *Value) *Immutable
  • func (t *Immutable) Size() uint64
• type Key
• type Value

Types

type Immutable

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

Immutable represents a treap data structure which is used to hold ordered key/value pairs using a combination of binary search tree and heap semantics.

In other parts of the code base, we see a traditional implementation of the treap with a randomised priority.

Note that this treap has been modified from the original in that the priority, rather than being a random value, is deterministically assigned the monotonically increasing block height.

However what is interesting is that we see similar behaviour to the treap structure, because the keys themselves are totally randomised, degenerate cases of trees with a bias for leftness or rightness cannot occur.

Do make note however, if the keys were not to be randomised, this would not be a structure which can be relied upon to self-balance as treaps do.

What motivated this alteration of the treap priority was that it can be used as a priority queue to discover the elements at the smallest height, which substantially improves application performance in one critical spot, via use of ForEachByHeight.

All operations which result in modifying the treap return a new version of the treap with only the modified nodes updated. All unmodified nodes are shared with the previous version. This is extremely useful in concurrent applications since the caller only has to atomically replace the treap pointer with the newly returned version after performing any mutations. All readers can simply use their existing pointer as a snapshot since the treap it points to is immutable. This effectively provides O(1) snapshot capability with efficient memory usage characteristics since the old nodes only remain allocated until there are no longer any references to them.

func NewImmutable

func NewImmutable() *Immutable

NewImmutable returns a new empty immutable treap ready for use. See the documentation for the Immutable structure for more details.

func (*Immutable) Delete

func (t *Immutable) Delete(key Key) *Immutable

Delete removes the passed key from the treap and returns the resulting treap if it exists. The original immutable treap is returned if the key does not exist.

func (*Immutable) FetchWinnersAndExpired

func (t *Immutable) FetchWinnersAndExpired(idxs []int, height uint32) ([]*Key, []*Key)

FetchWinnersAndExpired is a ticket database specific function which iterates over the entire treap and finds winners at selected indexes and all tickets whose height is less than or equal to the passed height. These are returned as slices of pointers to keys, which can be recast as []*chainhash.Hash. This is only used for benchmarking and is not consensus compatible.

func (*Immutable) ForEach

func (t *Immutable) ForEach(fn func(k Key, v *Value) bool)

ForEach invokes the passed function with every key/value pair in the treap in ascending order.

func (*Immutable) ForEachByHeight

func (t *Immutable) ForEachByHeight(heightLessThan uint32, fn func(k Key, v *Value) bool)

ForEachByHeight iterates all elements in the tree less than a given height in the blockchain.

func (*Immutable) Get

func (t *Immutable) Get(key Key) *Value

Get returns the value for the passed key. The function will return nil when the key does not exist.

func (*Immutable) GetByIndex

func (t *Immutable) GetByIndex(idx int) (Key, *Value)

GetByIndex returns the (Key, *Value) at the given position and panics if idx is out of bounds.

func (*Immutable) Has

func (t *Immutable) Has(key Key) bool

Has returns whether or not the passed key exists.

func (*Immutable) Len

func (t *Immutable) Len() int

Len returns the number of items stored in the treap.

func (*Immutable) Put

func (t *Immutable) Put(key Key, value *Value) *Immutable

Put inserts the passed key/value pair. Passing a nil value will result in a NOOP.

func (*Immutable) Size

func (t *Immutable) Size() uint64

Size returns a best estimate of the total number of bytes the treap is consuming including all of the fields used to represent the nodes as well as the size of the keys and values. Shared values are not detected, so the returned size assumes each value is pointing to different memory.

type Key

type Key chainhash.Hash

Key defines the key used to add an associated value to the treap.

type Value

type Value struct {
	// Height is the block height of the associated ticket.
	Height uint32

	// Flags defining the ticket state.
	Missed  bool
	Revoked bool
	Spent   bool
	Expired bool
}

Value defines the information stored for a given key in the treap.