README
¶
Skiplist
Skiplist implementation in Go. Read more on Skip Lists
Skiplist with various additions and potential variations on the standard list.
Install
go get -u github.com/mtchavez/skiplist
Usage
Initialize a skiplist
package main
func main() {
list := skiplist.NewList()
}
Insert Nodes
package main
func main() {
list := skiplist.NewList()
list.Insert(1, []byte("Node 1"))
list.Insert(2, []byte("Node 2"))
}
Iterate through nodes
package main
import (
"fmt"
)
func main() {
list := skiplist.NewList()
list.Insert(1, []byte("Node 1"))
list.Insert(2, []byte("Node 2"))
list.Insert(3, []byte("Node 3"))
for i := list.Iterator(); i.Next(); {
// Print Key
fmt.Println(i.Key())
// Print Value
fmt.Println(i.Val())
}
}
Documentation
Docs are on GoDoc
Tests
Run tests with coverage
go test --cover
TODO
- Update to use
interface{}for key/value- With a compare interface
- Concurrent skiplist implementation
Documentation
¶
Index ¶
Examples ¶
Constants ¶
const ( // ListMaxLevel is the Skiplist can have ListMaxLevel = 32 // ListP is the P value for the SkipList ListP = 0.25 )
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type CList ¶
CList is a skip list built for high concurrency
func NewCList ¶
func NewCList() *CList
NewDupeList initializes a new skiplist with max level of 32 or 2^32 elements that allows duplicates
func NewCListWithLevel ¶
NewDupeListWithLevel initializes a new skiplist with a custom max level. Level is defaulted to 32 to allow for 2^32 max elements
type DupeList ¶
DupeList implements the SkipList interface but allows for duplicate keys to be inserted
func NewDupeList ¶
func NewDupeList() *DupeList
NewDupeList initializes a new skiplist with max level of 32 or 2^32 elements that allows duplicates
func NewDupeListWithLevel ¶
NewDupeListWithLevel initializes a new skiplist with a custom max level. Level is defaulted to 32 to allow for 2^32 max elements
type Iterator ¶
Iterator interface Implements an iterator to be used to navigate through the skiplist
type List ¶
List is a basic skip list implementation with search, delete, and insert functionality and uses a mutex to allow for multi-threaded interaction
func NewList ¶
func NewList() *List
NewList initializes a new skiplist with max level of 32 or 2^32 elements
Example ¶
l := NewList()
fmt.Println("Max level:", l.MaxLevel)
Output: Max level: 32
func NewListWithLevel ¶
NewListWithLevel initializes a new skiplist with a custom max level. Level is defaulted to 32 to allow for 2^32 max elements
Example ¶
l := NewListWithLevel(200)
fmt.Println("Max level:", l.MaxLevel)
Output: Max level: 200
func (*List) Delete ¶
Delete will delete a node for the provided key will return a true/false if Node was deleted or not
Example ¶
l := NewList()
l.Insert(1, []byte("example 1"))
l.Insert(2, []byte("example 2"))
l.Insert(3, []byte("example 3"))
l.Insert(4, []byte("example 4"))
found := l.Search(4)
fmt.Printf("Searched for 4 and got '%+v'\n", string(found.Value()))
// Delete node
fmt.Printf("Deleted key 4? %+v\n", l.Delete(4))
notFound := l.Search(4)
fmt.Printf("Searched for deleted key of 4 and got %+v\n", notFound)
Output: Searched for 4 and got 'example 4' Deleted key 4? true Searched for deleted key of 4 and got <nil>
func (*List) Insert ¶
Insert a new node into the skip list providing a integer key and a byte array value. Will return the inserted Node
Example ¶
l := NewList()
l.Insert(1, []byte("example 1"))
l.Insert(2, []byte("example 2"))
l.Insert(3, []byte("example 3"))
l.Insert(4, []byte("example 4"))
fmt.Println("Size:", l.Size())
Output: Size: 4
func (*List) Search ¶
Search for a node in the skip list by the key will return a Node if found or nil if not found
Example ¶
l := NewList()
l.Insert(1, []byte("example 1"))
l.Insert(2, []byte("example 2"))
l.Insert(3, []byte("example 3"))
l.Insert(4, []byte("example 4"))
// Not Found
notFound := l.Search(45)
found := l.Search(4)
fmt.Printf("Searched for 45 and got %+v\n", notFound)
fmt.Printf("Searched for 4 and got '%+v'\n", string(found.Value()))
Output: Searched for 45 and got <nil> Searched for 4 and got 'example 4'
type Node ¶
type Node struct {
// contains filtered or unexported fields
}
Node for a skiplist which is a linked list node containing a slice of forward referencing nodes, the previous node and the key and value of the node
Source Files