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) Get(key 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 Mutable
  • func NewMutable() *Mutable
  • func (t *Mutable) Delete(key Key)
  • func (t *Mutable) ForEach(fn func(k Key, v *Value) bool)
  • func (t *Mutable) Get(key Key) *Value
  • func (t *Mutable) Has(key Key) bool
  • func (t *Mutable) Len() int
  • func (t *Mutable) Put(key Key, value *Value)
  • func (t *Mutable) Reset()
  • func (t *Mutable) Size() uint64
• 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. 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). In addition, it provides O(1) snapshots for multi-version concurrency control (MVCC).

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) 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) 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 Mutable

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

Mutable represents a treap data structure which is used to hold ordered key/value pairs 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).

func NewMutable

func NewMutable() *Mutable

NewMutable returns a new empty mutable treap ready for use. See the documentation for the Mutable structure for more details.

func (*Mutable) Delete

func (t *Mutable) Delete(key Key)

Delete removes the passed key if it exists.

func (*Mutable) ForEach

func (t *Mutable) 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 (*Mutable) Get

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

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

func (*Mutable) Has

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

Has returns whether or not the passed key exists.

func (*Mutable) Len

func (t *Mutable) Len() int

Len returns the number of items stored in the treap.

func (*Mutable) Put

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

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

func (*Mutable) Reset

func (t *Mutable) Reset()

Reset efficiently removes all items in the treap.

func (*Mutable) Size

func (t *Mutable) 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 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.