sorted

README

sorted

SortedSet and SortedMap with skip list for Go. It also supports sorting by score.

Rationale

It's designed to be used in Olric. I need a GC friendly SortedSet/SortedMap implementation which implements Load/Dump functions and my keys and values are byte slices.

Features

• Implemented with Skip list,
• Uses only one byte slice. It's GC friendly,
• Supports compaction: Frees claimed memory when it's needed,
• Supports sorting keys by score,
• Implements Load/Dump methods to store whole data set or transfer over network.

Limitations

• Keys and values are byte slices due to its design.

Usage

Contributions

Please don't hesitate to fork the project and send a pull request or just e-mail me to ask questions and share ideas.:w

Documentation

Overview

Package sorted provides SortedMap and SortedSet implementations and supports sorting by score.

Index

• Constants
• Variables
• type Hasher
• type SortedMap
  • func NewSortedMap(maxGarbageRatio float64) *SortedMap
  • func (m *SortedMap) Check(key []byte) bool
  • func (m *SortedMap) Close()
  • func (m *SortedMap) Delete(key []byte) error
  • func (m *SortedMap) Get(key []byte) ([]byte, error)
  • func (m *SortedMap) HeadMap(toKey []byte, f func(key, value []byte) bool) error
  • func (m *SortedMap) Len() int
  • func (m *SortedMap) Range(f func(key, value []byte) bool)
  • func (m *SortedMap) Set(key, value []byte) error
  • func (m *SortedMap) SubMap(fromKey, toKey []byte, f func(key, value []byte) bool) error
  • func (m *SortedMap) TailMap(fromKey []byte, f func(key, value []byte) bool) error
• type SortedMapWithScore
  • func NewSortedMapWithScore(maxGarbageRatio float64, hasher Hasher) *SortedMapWithScore
  • func (m *SortedMapWithScore) Check(key []byte) bool
  • func (m *SortedMapWithScore) Close()
  • func (m *SortedMapWithScore) Delete(key []byte) error
  • func (m *SortedMapWithScore) Get(key []byte) ([]byte, error)
  • func (m *SortedMapWithScore) GetScore(key []byte) (uint64, error)
  • func (m *SortedMapWithScore) HeadMap(toScore uint64, f func(key, value []byte) bool) error
  • func (m *SortedMapWithScore) Len() int
  • func (m *SortedMapWithScore) Range(f func(key, value []byte) bool)
  • func (m *SortedMapWithScore) Set(key, value []byte, score uint64) error
  • func (m *SortedMapWithScore) SubMap(fromScore, toScore uint64, f func(key, value []byte) bool) error
  • func (m *SortedMapWithScore) TailMap(fromScore uint64, f func(key, value []byte) bool) error
• type SortedSet
  • func NewSortedSet(maxGarbageRatio float64) *SortedSet
  • func (ss *SortedSet) Check(key []byte) bool
  • func (ss *SortedSet) Close()
  • func (ss *SortedSet) Delete(key []byte) error
  • func (ss *SortedSet) Len() int
  • func (ss *SortedSet) Range(f func(key []byte) bool)
  • func (ss *SortedSet) Set(key []byte) error
• type SortedSetWithScore
  • func NewSortedSetWithScore(maxGarbageRatio float64) *SortedSetWithScore
  • func (s *SortedSetWithScore) Check(key []byte) bool
  • func (s *SortedSetWithScore) Close()
  • func (s *SortedSetWithScore) Delete(key []byte) error
  • func (s *SortedSetWithScore) Len() int
  • func (s *SortedSetWithScore) Range(f func(key []byte) bool)
  • func (s *SortedSetWithScore) Set(key []byte, score uint64) error

Constants

const DefaultMaxGarbageRatio = 0.40

Variables

var (
	// ErrKeyNotFound means that given key could not be found in the data structure.
	ErrKeyNotFound = errors.New("key not found")

	// ErrInvalidRange means that given range is invalid to iterate: if fromKey is greater than toKey.
	ErrInvalidRange = errors.New("given range is invalid")
)

Types

type Hasher

type Hasher interface {
	Sum64([]byte) uint64
}

Hasher is responsible for generating unsigned, 64 bit hash of provided byte slice.

type SortedMap

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

SortedMap is a map that provides a total ordering of its elements (elements can be traversed in sorted order of keys).

func NewSortedMap

func NewSortedMap(maxGarbageRatio float64) *SortedMap

NewSortedMap creates and returns a new SortedMap with given parameters.

func (*SortedMap) Check

func (m *SortedMap) Check(key []byte) bool

Check checks the given key in SortedMap without reading its value.

func (*SortedMap) Close

func (m *SortedMap) Close()

Close stops background tasks and quits.

func (*SortedMap) Delete

func (m *SortedMap) Delete(key []byte) error

Delete deletes key/value pair from map. It returns nil if the key doesn't exist.

func (*SortedMap) Get

func (m *SortedMap) Get(key []byte) ([]byte, error)

Get returns the value for given key, if any.

func (*SortedMap) HeadMap

func (m *SortedMap) HeadMap(toKey []byte, f func(key, value []byte) bool) error

HeadMap returns a view of the portion of this map whose keys are strictly less than toKey.

func (*SortedMap) Len

func (m *SortedMap) Len() int

Len returns the key count in this map.

func (*SortedMap) Range

func (m *SortedMap) Range(f func(key, value []byte) bool)

Range calls f sequentially for each key and value present in the map. If f returns false, range stops the iteration.

func (*SortedMap) Set

func (m *SortedMap) Set(key, value []byte) error

Set sets a new key/value pair to the map.

func (*SortedMap) SubMap

func (m *SortedMap) SubMap(fromKey, toKey []byte, f func(key, value []byte) bool) error

SubMap returns a view of the portion of this map whose keys range from fromKey, inclusive, to toKey, exclusive.

func (*SortedMap) TailMap

func (m *SortedMap) TailMap(fromKey []byte, f func(key, value []byte) bool) error

TailMap returns a view of the portion of this map whose keys are greater than or equal to fromKey.

type SortedMapWithScore

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

SortedMapWithScore is just a SortedMap which supports sort by score instead of keys. Just a wrapper around SortedMap implementation.

func NewSortedMapWithScore

func NewSortedMapWithScore(maxGarbageRatio float64, hasher Hasher) *SortedMapWithScore

NewSortedMapWithScore creates and returns a new SortedMapWithScore

func (*SortedMapWithScore) Check

func (m *SortedMapWithScore) Check(key []byte) bool

Check checks the key without reading its value and returns true, if any.

func (*SortedMapWithScore) Close

func (m *SortedMapWithScore) Close()

Close stops background tasks, if any and waits for them until quit.

func (*SortedMapWithScore) Delete

func (m *SortedMapWithScore) Delete(key []byte) error

Delete deletes the key/value pair for given key. It may trigger compaction to reclaim memory.

func (*SortedMapWithScore) Get

func (m *SortedMapWithScore) Get(key []byte) ([]byte, error)

Get returns the value for given key, if any. Otherwise it returns ErrKeyNotFound. The returned value is its own copy.

func (*SortedMapWithScore) GetScore

func (m *SortedMapWithScore) GetScore(key []byte) (uint64, error)

GetScore returns the score for given key, if any. Otherwise it returns ErrKeyNotFound.

func (*SortedMapWithScore) HeadMap

func (m *SortedMapWithScore) HeadMap(toScore uint64, f func(key, value []byte) bool) error

HeadMap returns a view of the portion of this map whose keys are strictly less than toKey.

func (*SortedMapWithScore) Len

func (m *SortedMapWithScore) Len() int

Len returns the length of SortedMap.

func (*SortedMapWithScore) Range

func (m *SortedMapWithScore) Range(f func(key, value []byte) bool)

Range calls f sequentially for each key and value present in the SortedMap. If f returns false, range stops the iteration.

func (*SortedMapWithScore) Set

func (m *SortedMapWithScore) Set(key, value []byte, score uint64) error

Set sets a new key/value pair to the map.

func (*SortedMapWithScore) SubMap

func (m *SortedMapWithScore) SubMap(fromScore, toScore uint64, f func(key, value []byte) bool) error

SubMap returns a view of the portion of this map whose keys range from fromKey, inclusive, to toKey, exclusive.

func (*SortedMapWithScore) TailMap

func (m *SortedMapWithScore) TailMap(fromScore uint64, f func(key, value []byte) bool) error

TailMap returns a view of the portion of this map whose keys are greater than or equal to fromKey.

type SortedSet

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

func NewSortedSet

func NewSortedSet(maxGarbageRatio float64) *SortedSet

func (*SortedSet) Check

func (ss *SortedSet) Check(key []byte) bool

func (*SortedSet) Close

func (ss *SortedSet) Close()

func (*SortedSet) Delete

func (ss *SortedSet) Delete(key []byte) error

func (*SortedSet) Len

func (ss *SortedSet) Len() int

func (*SortedSet) Range

func (ss *SortedSet) Range(f func(key []byte) bool)

func (*SortedSet) Set

func (ss *SortedSet) Set(key []byte) error

type SortedSetWithScore

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

func NewSortedSetWithScore

func NewSortedSetWithScore(maxGarbageRatio float64) *SortedSetWithScore

func (*SortedSetWithScore) Check

func (s *SortedSetWithScore) Check(key []byte) bool

func (*SortedSetWithScore) Close

func (s *SortedSetWithScore) Close()

func (*SortedSetWithScore) Delete

func (s *SortedSetWithScore) Delete(key []byte) error

func (*SortedSetWithScore) Len

func (s *SortedSetWithScore) Len() int

func (*SortedSetWithScore) Range

func (s *SortedSetWithScore) Range(f func(key []byte) bool)

func (*SortedSetWithScore) Set

func (s *SortedSetWithScore) Set(key []byte, score uint64) error