skiplist.go

package skiplist

import (
	"math/rand"
	"sync"
)

const (
	// ListMaxLevel is the Skiplist can have
	ListMaxLevel = 32
	// ListP is the P value for the SkipList
	ListP = 0.5
)

// SkipList interface defining the methods
// needed for a skip list
type SkipList interface {
	Search(key int) *Node
	Delete(key int) bool
	Insert(key int, val interface{}) *Node
	Iterator() Iterator
}

// List is a basic skip list implementation
// with search, delete, and insert functionality
// and uses a mutex to allow for multi-threaded interaction
type List struct {
	sync.RWMutex
	MaxLevel int
	level    int
	length   int
	header   *Node
	footer   *Node
}

var _ SkipList = (*List)(nil)

// Returns a random level used during inserting nodes
func randomLevel(maxLevel int) int {
	newLevel := 1
	for rand.Float64() >= ListP && newLevel < maxLevel && newLevel < ListMaxLevel-1 {
		newLevel++
	}
	return newLevel
}

// NewList initializes a new skiplist with
// max level of 32 or 2^32 elements
func NewList() *List {
	return NewListWithLevel(ListMaxLevel)
}

// NewListWithLevel initializes a new skiplist with a custom
// max level. Level is defaulted to 32 to allow
// for 2^32 max elements
func NewListWithLevel(level int) *List {
	return &List{
		MaxLevel: level,
		header:   &Node{forward: make([]*Node, level)},
		level:    0,
	}
}

// Iterator returns an iterable from the current
// head of the skiplist.
func (l *List) Iterator() Iterator {
	return &iterable{curr: l.header}
}

// Size returns the length of the list
func (l *List) Size() int {
	return l.length
}

// Search for a node in the skip list by the key
// will return a Node if found or nil if not found
func (l *List) Search(key int) *Node {
	l.RLock()
	defer l.RUnlock()
	x := l.header
	for i := l.level; i >= 0; i-- {
		for x.forward[i] != nil && x.forward[i].key < key {
			x = x.forward[i]
		}
	}
	x = x.forward[0]
	if x != nil && x.key == key {
		return x
	}
	return nil
}

// Insert a new node into the skip list providing a
// integer key and a byte array value. Will return
// the inserted Node
func (l *List) Insert(key int, val interface{}) *Node {
	update := make([]*Node, l.MaxLevel)
	x := l.header
	var alreadyChecked *Node
	l.Lock()
	defer l.Unlock()

	for i := l.level; i >= 0; i-- {
		for x.forward[i] != nil &&
			alreadyChecked != x.forward[i] &&
			x.forward[i].key < key {
			x = x.forward[i]
		}
		alreadyChecked = x.forward[i]
		update[i] = x
	}
	x = x.forward[0]
	if x != nil && x.key == key {
		x.val = val
		return x
	}
	newLevel := randomLevel(l.MaxLevel)
	if newLevel > l.level {
		for i := l.level + 1; i < newLevel; i++ {
			update[i] = l.header
		}
		l.level = newLevel
	}
	x = NewNode(newLevel, key, val)
	for i := 0; i < newLevel; i++ {
		x.forward[i] = update[i].forward[i]
		update[i].forward[i] = x
	}
	x.backward = nil
	if update[0] != l.header {
		x.backward = update[0]
	}
	if x.forward[0] != nil {
		x.forward[0].backward = x
	}
	if l.footer == nil || l.footer.key < key {
		l.footer = x
	}
	l.length++
	return x
}

// Delete will delete a node for the provided key
// will return a true/false if Node was deleted or not
func (l *List) Delete(key int) bool {
	update := make([]*Node, l.MaxLevel)
	x := l.header
	var alreadyChecked *Node
	l.Lock()
	defer l.Unlock()

	for i := l.level; i >= 0; i-- {
		for x.forward[i] != nil &&
			alreadyChecked != x.forward[i] &&
			x.forward[i].key < key {
			x = x.forward[i]
		}
		alreadyChecked = x.forward[i]
		update[i] = x
	}
	x = x.forward[0]
	if x != nil && x.key == key {
		for i := 0; i < l.level; i++ {
			if update[i].forward[i] != x {
				break
			}
			update[i].forward[i] = x.forward[i]
		}
		for l.level > 1 && len(l.header.forward) > l.level && l.header.forward[l.level-1] == nil {
			l.level--
		}
		l.length--
		return true
	}
	return false
}