treap

package
v1.0.0 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Sep 9, 2023 License: ISC Imports: 3 Imported by: 0

README

treap

Build Status ISC License GoDoc

Package treap implements a treap data structure that 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). 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.

Package treap is licensed under the copyfree ISC license.

Usage

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

License

Package treap is licensed under the copyfree ISC License.

Documentation

Overview

Package treap implements a treap data structure that 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 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

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

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 []byte) *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) ForEach

func (t *Immutable) ForEach(fn func(k, v []byte) 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 []byte) []byte

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 []byte) bool

Has returns whether or not the passed key exists.

func (*Immutable) Iterator

func (t *Immutable) Iterator(startKey, limitKey []byte) *Iterator

Iterator returns a new iterator for the immutable treap. The newly returned iterator is not pointing to a valid item until a call to one of the methods to position it is made.

The start key and limit key parameters cause the iterator to be limited to a range of keys. The start key is inclusive and the limit key is exclusive. Either or both can be nil if the functionality is not desired.

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, value []byte) *Immutable

Put inserts the passed key/value pair.

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 Iterator

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

Iterator represents an iterator for forwards and backwards iteration over the contents of a treap (mutable or immutable).

func (*Iterator) First

func (iter *Iterator) First() bool

First moves the iterator to the first key/value pair. When there is only a single key/value pair both First and Last will point to the same pair. Returns false if there are no key/value pairs.

func (*Iterator) ForceReseek

func (iter *Iterator) ForceReseek()

ForceReseek notifies the iterator that the underlying mutable treap has been updated, so the next call to Prev or Next needs to reseek in order to allow the iterator to continue working properly.

NOTE: Calling this function when the iterator is associated with an immutable treap has no effect as you would expect.

func (*Iterator) Key

func (iter *Iterator) Key() []byte

Key returns the key of the current key/value pair or nil when the iterator is exhausted. The caller should not modify the contents of the returned slice.

func (*Iterator) Last

func (iter *Iterator) Last() bool

Last moves the iterator to the last key/value pair. When there is only a single key/value pair both First and Last will point to the same pair. Returns false if there are no key/value pairs.

func (*Iterator) Next

func (iter *Iterator) Next() bool

Next moves the iterator to the next key/value pair and returns false when the iterator is exhausted. When invoked on a newly created iterator it will position the iterator at the first item.

func (*Iterator) Prev

func (iter *Iterator) Prev() bool

Prev moves the iterator to the previous key/value pair and returns false when the iterator is exhausted. When invoked on a newly created iterator it will position the iterator at the last item.

func (*Iterator) Seek

func (iter *Iterator) Seek(key []byte) bool

Seek moves the iterator to the first key/value pair with a key that is greater than or equal to the given key and returns true if successful.

func (*Iterator) Valid

func (iter *Iterator) Valid() bool

Valid indicates whether the iterator is positioned at a valid key/value pair. It will be considered invalid when the iterator is newly created or exhausted.

func (*Iterator) Value

func (iter *Iterator) Value() []byte

Value returns the value of the current key/value pair or nil when the iterator is exhausted. The caller should not modify the contents of the returned slice.

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 []byte)

Delete removes the passed key if it exists.

func (*Mutable) ForEach

func (t *Mutable) ForEach(fn func(k, v []byte) 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 []byte) []byte

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 []byte) bool

Has returns whether or not the passed key exists.

func (*Mutable) Iterator

func (t *Mutable) Iterator(startKey, limitKey []byte) *Iterator

Iterator returns a new iterator for the mutable treap. The newly returned iterator is not pointing to a valid item until a call to one of the methods to position it is made.

The start key and limit key parameters cause the iterator to be limited to a range of keys. The start key is inclusive and the limit key is exclusive. Either or both can be nil if the functionality is not desired.

WARNING: The ForceSeek method must be called on the returned iterator if the treap is mutated. Failure to do so will cause the iterator to return unexpected keys and/or values.

For example:

iter := t.Iterator(nil, nil)
for iter.Next() {
	if someCondition {
		t.Delete(iter.Key())
		iter.ForceReseek()
	}
}

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, value []byte)

Put inserts the passed key/value pair.

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.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL