README
¶
gozset
An efficient redis-like zset golang implementation
Usage
// Create a ZSet with a less function and the rankNum of 50
var rankNum = 50
zs := NewZSetInt(func(l, r int32) bool {
return l < r
}, rankNum)
// Add 10 key-value(i,10*i) pairs to the ZSet
for i := 0; i < 10; i++ {
zs.Add(int64(i), int32(i)*10)
}
// Check the size of the ZSet
if zs.Card() != 10 {
log.Printf("The length of the ZSet should be 10")
}
// Check the Rank call
for i := 0; i < 10; i++ {
if zs.Rank(int64(i)) != uint32(i+1) {
log.Printf("Rank error")
}
}
// Check the RangeByRank call
for i, ks := range zs.RangeByRank(1, 10000) {
if ks[1] != int64(i*10) || ks[0] != int64(i) {
log.Printf("RangeByRank error")
}
}
// Check the RangeByScore call
for i, k := range zs.RangeByScore(0, 1000) {
if k != int64(i) {
log.Printf("RangByScore error")
}
}
// Remove some keys
zs.Remove(5)
zs.Remove(6)
more examples in zset_int_test.go
##Benchmark
BenchmarkZSetAdd-4 1278654 862 ns/op 377 B/op 1 allocs/op
BenchmarkZSetAddNoHeapMap-4 926547 4383 ns/op 1207 B/op 4 allocs/op
BenchmarkZSetRemove-4 1229588 936 ns/op 43 B/op 1 allocs/op
BenchmarkZSetRemoveNoHeapMap-4 1000000 3270 ns/op 256 B/op 1 allocs/op
BenchmarkZSetRank-4 3538854 298 ns/op 0 B/op 0 allocs/op
BenchmarkZSetRankNoHeampMap-4 1405663 974 ns/op 0 B/op 0 allocs/op
BenchmarkZSetTopN-4 132181 8300 ns/op 4912 B/op 2 allocs/op
BenchmarkZSetTopNNoHeapMap-4 133660 9044 ns/op 4912 B/op 2 allocs/op
BenchmarkZSetMarshal-4 10000 220510 ns/op 229425 B/op 3 allocs/op
BenchmarkZSetMarshalNoHeapMap-4 10000 663226 ns/op 163888 B/op 2 allocs/op
Documentation
¶
Overview ¶
Package skiplist implements skip list based maps and sets.
Skip lists are a data structure that can be used in place of balanced trees. Skip lists use probabilistic balancing rather than strictly enforced balancing and as a result the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees.
Skip lists were first described in Pugh, William (June 1990). "Skip lists: a probabilistic alternative to balanced trees". Communications of the ACM 33 (6): 668–676
redis like sorted set
Index ¶
- Constants
- type IntOrderedKey
- type Iterator
- type SkipListInt
- func (s *SkipListInt) Clear()
- func (s *SkipListInt) Delete(key IntOrderedKey) (value int64, ok bool)
- func (s *SkipListInt) FillBySortedSlice(keys []IntOrderedKey, values []int64) bool
- func (s *SkipListInt) Get(key IntOrderedKey) (value int64, ok bool)
- func (s *SkipListInt) GetElemByRank(rank uint32) Iterator
- func (s *SkipListInt) GetGreaterOrEqual(min IntOrderedKey) (actualKey IntOrderedKey, value int64, ok bool)
- func (s *SkipListInt) Iterator() Iterator
- func (s *SkipListInt) Len() int
- func (s *SkipListInt) Range(from, to IntOrderedKey) Iterator
- func (s *SkipListInt) Rank(key IntOrderedKey) uint32
- func (s *SkipListInt) Seek(key IntOrderedKey) Iterator
- func (s *SkipListInt) SeekToFirst() Iterator
- func (s *SkipListInt) SeekToLast() Iterator
- func (s *SkipListInt) Set(key IntOrderedKey, value int64)
- type ZSetInt
- func (z *ZSetInt) Add(key int64, score int32) bool
- func (z *ZSetInt) Card() int
- func (z *ZSetInt) Clear()
- func (z *ZSetInt) Exist(key int64) bool
- func (z *ZSetInt) ForeachInOrder(fn func(key int64, score int32) bool)
- func (z *ZSetInt) Marshal() (sortedSlice [][2]int64, heapSlice [][3]int64)
- func (z *ZSetInt) RangeByRank(rankFrom uint32, rankTo uint32) [][2]int64
- func (z *ZSetInt) RangeByScore(scoreFrom int32, scoreTo int32) []int64
- func (z *ZSetInt) Rank(key int64) uint32
- func (z *ZSetInt) Remove(key int64) bool
- func (z *ZSetInt) Score(key int64) (int32, bool)
- func (z *ZSetInt) Unmarshal(sortedSlice [][2]int64, heapSlice [][3]int64) bool
- func (z *ZSetInt) UnmarshalMerge(sortedSlice1 [][2]int64, heapSlice1 [][3]int64, sortedSlice2 [][2]int64, ...) error
- func (z *ZSetInt) Update(key int64, score int32) bool
Constants ¶
const DefaultMaxLevel = 32
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type IntOrderedKey ¶
type IntOrderedKey [2]int64 // 0:score 1:timeCounter
func (IntOrderedKey) IsZero ¶
func (k IntOrderedKey) IsZero() bool
func (IntOrderedKey) Score ¶
func (k IntOrderedKey) Score() int32
func (IntOrderedKey) TimeCounter ¶
func (k IntOrderedKey) TimeCounter() int64
type Iterator ¶
type Iterator interface {
// Next returns true if the iterator contains subsequent elements
// and advances its state to the next element if that is possible.
Next() (ok bool)
// Previous returns true if the iterator contains previous elements
// and rewinds its state to the previous element if that is possible.
Previous() (ok bool)
// Key returns the current key.
Key() IntOrderedKey
// Value returns the current value.
Value() int64
// Seek reduces iterative seek costs for searching forward into the Skip List
// by remarking the range of keys over which it has scanned before. If the
// requested key occurs prior to the point, the Skip List will start searching
// as a safeguard. It returns true if the key is within the known range of
// the list.
Seek(key IntOrderedKey) (ok bool)
// Close this iterator to reap resources associated with it. While not
// strictly required, it will provide extra hints for the garbage collector.
Close()
}
Iterator is an interface that you can use to iterate through the skip list (in its entirety or fragments). For an use example, see the documentation of SkipListInt.
Key and Value return the key and the value of the current node.
type SkipListInt ¶
type SkipListInt struct {
// MaxLevel determines how many items the SkipList can store
// efficiently (2^MaxLevel).
//
// It is safe to increase MaxLevel to accomodate more
// elements. If you decrease MaxLevel and the skip list
// already contains nodes on higer levels, the effective
// MaxLevel will be the greater of the new MaxLevel and the
// level of the highest node.
//
// A SkipListInt with MaxLevel equal to 0 is equivalent to a
// standard linked list and will not have any of the nice
// properties of skip lists (probably not what you want).
MaxLevel int
// contains filtered or unexported fields
}
A SkipListInt is a map-like data structure that maintains an ordered collection of key-value pairs. Insertion, lookup, and deletion are all O(log n) operations. A SkipListInt can efficiently store up to 2^MaxLevel items.
To iterate over a skip list (where s is a *SkipListInt):
for i := s.Iterator(); i.Next(); {
// do something with i.Key() and i.Value()
}
func NewSkipListInt ¶
func NewSkipListInt(lessThan func(l, r IntOrderedKey) bool) *SkipListInt
NewCustomMap returns a new SkipListInt that will use lessThan as the comparison function. lessThan should define a linear order on keys you intend to use with the SkipListInt.
func (*SkipListInt) Clear ¶
func (s *SkipListInt) Clear()
func (*SkipListInt) Delete ¶
func (s *SkipListInt) Delete(key IntOrderedKey) (value int64, ok bool)
Delete removes the node with the given key.
It returns the old value and whether the node was present.
func (*SkipListInt) FillBySortedSlice ¶
func (s *SkipListInt) FillBySortedSlice(keys []IntOrderedKey, values []int64) bool
func (*SkipListInt) Get ¶
func (s *SkipListInt) Get(key IntOrderedKey) (value int64, ok bool)
Get returns the value associated with key from s (nil if the key is not present in s). The second return value is true when the key is present.
func (*SkipListInt) GetElemByRank ¶
func (s *SkipListInt) GetElemByRank(rank uint32) Iterator
func (*SkipListInt) GetGreaterOrEqual ¶
func (s *SkipListInt) GetGreaterOrEqual(min IntOrderedKey) (actualKey IntOrderedKey, value int64, ok bool)
GetGreaterOrEqual finds the node whose key is greater than or equal to min. It returns its value, its actual key, and whether such a node is present in the skip list.
func (*SkipListInt) Iterator ¶
func (s *SkipListInt) Iterator() Iterator
Iterator returns an Iterator that will go through all elements s.
func (*SkipListInt) Range ¶
func (s *SkipListInt) Range(from, to IntOrderedKey) Iterator
Range returns an iterator that will go through all the elements of the skip list that are greater or equal than from, but less than to.
func (*SkipListInt) Rank ¶
func (s *SkipListInt) Rank(key IntOrderedKey) uint32
func (*SkipListInt) Seek ¶
func (s *SkipListInt) Seek(key IntOrderedKey) Iterator
Seek returns a bidirectional iterator starting with the first element whose key is greater or equal to key; otherwise, a nil iterator is returned.
func (*SkipListInt) SeekToFirst ¶
func (s *SkipListInt) SeekToFirst() Iterator
SeekToFirst returns a bidirectional iterator starting from the first element in the list if the list is populated; otherwise, a nil iterator is returned.
func (*SkipListInt) SeekToLast ¶
func (s *SkipListInt) SeekToLast() Iterator
SeekToLast returns a bidirectional iterator starting from the last element in the list if the list is populated; otherwise, a nil iterator is returned.
func (*SkipListInt) Set ¶
func (s *SkipListInt) Set(key IntOrderedKey, value int64)
Sets set the value associated with key in s.
type ZSetInt ¶
type ZSetInt struct {
// contains filtered or unexported fields
}
Source Files