skiplist

README

fast-skiplist

Original repo -> github.com/sean-public/fast-skiplist

Purpose

Changes have been made to this fork to support storing a range of sequences and a timestamp as the key. This is very specific to Sync Gateway's use case and probably won't be generally fit to use for other use cases.

Sync Gateway needs to cache documents over the DCP feed in sequence order, so Sync Gateway needs a way to store sequences that don't arrive in the order expected until they eventually arrive over the feed. A skip-list with support for storing sequence ranges is a good data structure to do so.

Documentation

Index

• Constants
• type Element
  • func (element *Element) IsWithinRange(elem SkippedSequenceEntry) bool
  • func (e *Element) Key() SkippedSequenceEntry
  • func (element *Element) Next() *Element
• type SkipList
  • func New() *SkipList
  • func NewWithMaxLevel(maxLevel int) *SkipList
  • func (list *SkipList) CompactList(timeNow, maxWait int64) ([]SkippedSequenceEntry, int64, int64)
  • func (list *SkipList) Front() *Element
  • func (list *SkipList) Get(key SkippedSequenceEntry) *Element
  • func (list *SkipList) GetLastElement() *Element
  • func (list *SkipList) GetLength() int
  • func (list *SkipList) GetNumSequencesInList() int64
  • func (list *SkipList) Remove(key SkippedSequenceEntry) (*Element, int64, error)
  • func (list *SkipList) Set(key SkippedSequenceEntry) (*Element, error)
  • func (list *SkipList) SetProbability(newProbability float64)
• type SkippedSequenceEntry
  • func (s *SkippedSequenceEntry) GetNumSequencesInEntry() int64
  • func (s *SkippedSequenceEntry) String() string

Constants

const (
	// Suitable for math.Floor(math.Pow(math.E, 18)) == 65659969 elements in list
	DefaultMaxLevel    int     = 18
	DefaultProbability float64 = 1 / math.E
)

Types

type Element

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

func (*Element) IsWithinRange

func (element *Element) IsWithinRange(elem SkippedSequenceEntry) bool

IsWithinRange checks if the SkippedSequenceEntry is within the range of the Element's key.

func (*Element) Key

func (e *Element) Key() SkippedSequenceEntry

Key allows retrieval of the key for a given Element

func (*Element) Next

func (element *Element) Next() *Element

Next returns the following Element or nil if we're at the end of the list. Only operates on the bottom level of the skip list (a fully linked list).

type SkipList

type SkipList struct {
	NumSequencesInList int64

	Length int
	// contains filtered or unexported fields
}

func New

func New() *SkipList

New creates a new skip list with default parameters. Returns a pointer to the new list.

func NewWithMaxLevel

func NewWithMaxLevel(maxLevel int) *SkipList

NewWithMaxLevel creates a new skip list with MaxLevel set to the provided number. maxLevel has to be int(math.Ceil(math.Log(N))) for DefaultProbability (where N is an upper bound on the number of elements in a skip list). See http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.17.524 Returns a pointer to the new list.

func (*SkipList) CompactList

func (list *SkipList) CompactList(timeNow, maxWait int64) ([]SkippedSequenceEntry, int64, int64)

CompactList compacts the skiplist by removing elements that are older than maxWait. Returns number of sequences compacted and number of sequences left in list

func (*SkipList) Front

func (list *SkipList) Front() *Element

Front returns the head node of the list.

func (*SkipList) Get

func (list *SkipList) Get(key SkippedSequenceEntry) *Element

Get finds an element by key. It returns element pointer if found, nil if not found.

func (*SkipList) GetLastElement

func (list *SkipList) GetLastElement() *Element

GetLastElement will return the last element in the skiplist

func (*SkipList) GetLength

func (list *SkipList) GetLength() int

GetLength will return the number of elements in the skiplist

func (*SkipList) GetNumSequencesInList

func (list *SkipList) GetNumSequencesInList() int64

GetNumSequencesInList will return the total number of sequences in the skiplist

func (*SkipList) Remove

func (list *SkipList) Remove(key SkippedSequenceEntry) (*Element, int64, error)

Remove deletes an element from the list. Returns removed element pointer if found, nil if not found. Also returns the number of sequences left in list and an error if the element was not found.

func (*SkipList) Set

func (list *SkipList) Set(key SkippedSequenceEntry) (*Element, error)

Set inserts a value in the list with the specified key, ordered by the key. If the key exists, we will error, this is unexpected behaviour Returns a pointer to the new element nd error type.

func (*SkipList) SetProbability

func (list *SkipList) SetProbability(newProbability float64)

SetProbability changes the current P value of the list. It doesn't alter any existing data, only changes how future insert heights are calculated.

type SkippedSequenceEntry

type SkippedSequenceEntry struct {
	Start     uint64
	End       uint64
	Timestamp int64
}

func (*SkippedSequenceEntry) GetNumSequencesInEntry

func (s *SkippedSequenceEntry) GetNumSequencesInEntry() int64

GetNumSequencesInEntry return the number of sequences in the SkippedSequenceEntry sequence range.

func (*SkippedSequenceEntry) String

func (s *SkippedSequenceEntry) String() string

String will return a string representation of the SkippedSequenceEntry Formats: Singular: "#<seq>" or ranges: "#<start>-#<end>"