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.

Expand ▾ Collapse ▴

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.