Help us shape the future of Go! Take the 2026 Go Developer Survey

skewBinomialQ

package module
v0.1.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Feb 13, 2018 License: MIT Imports: 8 Imported by: 2

README

Thread-Safe Lock Free Priority Queue

The BootstrappedSkewBinomialQueue provides the fundamental data structure specific to this repository. It is based on Dr. Chris Okasaki's paper, Optimal Purely Functional Priority Queues. You can also read my own blog for background, motivation, and analysis of the repository.

The supported operations and their associated run time complexities are as follows:

Enqueue: O(1)
Peek: O(1)
Dequeue: O(log N)
Length: O(1)
Meld: O(1)

The fundamental advantage of a comparable priority queue datastructure is the ability to meld queues in constant time.

Usage:

type ArbitraryDataType struct {
    ArbitraryData string
    Score         int
}

func (a ArbitraryDataType) LessThan(otherPriority skewBinomialQ.QueuePriority) bool {
	casted, ok := otherPriority.(ArbitraryDataType)
	if ok {
		return a.Score < casted.Score
	}
	return false
}

arbitraryScore := 100
q1 := skewBinomialQ.NewEmptyBootstrappedSkewBinomialQueue()

/**********  ENQUEUE  **********/
q1 = q.Enqueue(
    ArbitraryDataType{
        "some_data",
        arbitraryScore,
    }
)


/**********  PEEK  **********/
highestPriorityData := q1.Peek()


/**********  DEQUEUE  **********/
highestPriorityData, ok = q1.Dequeue()
casted, ok := highestPriorityData.(ArbitraryDataType)


/**********  MELD  **********/
anotherQ := NewEmptyBootstrappedSkewBinomialQueue()
melded := q1.Meld(anotherQ)

The library was also an experiment with lock-free datastructures. You can also initialize a LazyMergeSkewBinomialQueue in place of the synchronous BootstrappedSkewBinomialQueue. This datastructure will allow for thread-safe operations, but it will NOT guarantee that the highest priority element is popped in the case that the queue is saturated with dequeues from multiple threads.

As the code currently stands, there are some less than optimal uses of goroutines that need to be cleaned up, so it is unlikely that the concurrent implementation offers significant benefit to any consumers.

Documentation

Index

Constants

View Source 
const MELD_PERIOD = 2

Variables

View Source 
var FAIL_ADDRESS unsafe.Pointer = unsafe.Pointer(new(int8))
View Source 
var NULL_OBJECT = NullObject{}

Functions

func MaxParallelism 

func MaxParallelism() int

Types

type BootstrappedSkewBinomialQueue 

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

func NewEmptyBootstrappedSkewBinomialQueue 

func NewEmptyBootstrappedSkewBinomialQueue() BootstrappedSkewBinomialQueue

func (BootstrappedSkewBinomialQueue) Dequeue 

func (b BootstrappedSkewBinomialQueue) Dequeue() (QueuePriority, BootstrappedSkewBinomialQueue)

func (BootstrappedSkewBinomialQueue) DequeueWithMergeCallback 

func (b BootstrappedSkewBinomialQueue) DequeueWithMergeCallback(mergeCallback func([]Node, ...*SkewBinomialQueue) SkewBinomialQueue) (QueuePriority, BootstrappedSkewBinomialQueue)

func (BootstrappedSkewBinomialQueue) Enqueue 

func (b BootstrappedSkewBinomialQueue) Enqueue(priority QueuePriority) BootstrappedSkewBinomialQueue

func (BootstrappedSkewBinomialQueue) IsEmpty 

func (b BootstrappedSkewBinomialQueue) IsEmpty() bool

func (BootstrappedSkewBinomialQueue) Length 

func (b BootstrappedSkewBinomialQueue) Length() int

func (BootstrappedSkewBinomialQueue) LessThan 

func (b BootstrappedSkewBinomialQueue) LessThan(otherPriority QueuePriority) bool

func (BootstrappedSkewBinomialQueue) Meld 

func (b BootstrappedSkewBinomialQueue) Meld(otherQ BootstrappedSkewBinomialQueue) BootstrappedSkewBinomialQueue

func (BootstrappedSkewBinomialQueue) Peek 

func (b BootstrappedSkewBinomialQueue) Peek() QueuePriority

func (BootstrappedSkewBinomialQueue) String 

func (b BootstrappedSkewBinomialQueue) String() string

type LazyMergeSkewBinomialQueue 

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

func (LazyMergeSkewBinomialQueue) BlockUntilNoPending 

func (q LazyMergeSkewBinomialQueue) BlockUntilNoPending()

func (LazyMergeSkewBinomialQueue) Dequeue 

func (q LazyMergeSkewBinomialQueue) Dequeue() (QueuePriority, PriorityQueue)

func (LazyMergeSkewBinomialQueue) Enqueue 

func (q LazyMergeSkewBinomialQueue) Enqueue(priority QueuePriority) PriorityQueue

func (LazyMergeSkewBinomialQueue) IsEmpty 

func (q LazyMergeSkewBinomialQueue) IsEmpty() bool

func (LazyMergeSkewBinomialQueue) Length 

func (q LazyMergeSkewBinomialQueue) Length() int

func (LazyMergeSkewBinomialQueue) Meld 

func (q LazyMergeSkewBinomialQueue) Meld(otherQ PriorityQueue) PriorityQueue

func (LazyMergeSkewBinomialQueue) Peek 

func (q LazyMergeSkewBinomialQueue) Peek() QueuePriority

type Node 

type Node interface {
	Rank() int
	Length() int
	Children() []Node
	Peek() QueuePriority
	Link(heaps ...Node) Node
	IsEmpty() bool
}

func NewSkewBinomialHeap 

func NewSkewBinomialHeap(priority QueuePriority) Node

type NullObject 

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

func (NullObject) Children 

func (n NullObject) Children() []Node

func (NullObject) IsEmpty 

func (n NullObject) IsEmpty() bool

func (NullObject) Length 

func (n NullObject) Length() int
func (n NullObject) Link(heaps ...Node) Node

func (NullObject) Peek 

func (n NullObject) Peek() QueuePriority

func (NullObject) Rank 

func (n NullObject) Rank() int

type PriorityQueue 

type PriorityQueue interface {
	Enqueue(priority QueuePriority) PriorityQueue
	Peek() QueuePriority
	Meld(otherQ PriorityQueue) PriorityQueue
	Dequeue() (QueuePriority, PriorityQueue)
	Length() int
	IsEmpty() bool
}

func NewEmptyLazyMergeSkewBinomialQueue 

func NewEmptyLazyMergeSkewBinomialQueue() PriorityQueue

type QueuePriority 

type QueuePriority interface {
	LessThan(otherPriority QueuePriority) bool
}

type RootedSkewBinomialQueue 

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

func NewEmptyRootedSkewBinomialQueue 

func NewEmptyRootedSkewBinomialQueue() RootedSkewBinomialQueue

func (RootedSkewBinomialQueue) Dequeue 

func (r RootedSkewBinomialQueue) Dequeue() (QueuePriority, RootedSkewBinomialQueue)

func (RootedSkewBinomialQueue) Enqueue 

func (r RootedSkewBinomialQueue) Enqueue(priority QueuePriority) RootedSkewBinomialQueue

func (RootedSkewBinomialQueue) IsEmpty 

func (r RootedSkewBinomialQueue) IsEmpty() bool

func (RootedSkewBinomialQueue) Length 

func (r RootedSkewBinomialQueue) Length() int

func (RootedSkewBinomialQueue) Meld 

func (r RootedSkewBinomialQueue) Meld(otherQ RootedSkewBinomialQueue) RootedSkewBinomialQueue

func (RootedSkewBinomialQueue) Peek 

func (r RootedSkewBinomialQueue) Peek() QueuePriority

type SkewBinomialHeap 

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

func (SkewBinomialHeap) Children 

func (s SkewBinomialHeap) Children() []Node

func (SkewBinomialHeap) IsEmpty 

func (s SkewBinomialHeap) IsEmpty() bool

func (SkewBinomialHeap) Length 

func (s SkewBinomialHeap) Length() int
func (s SkewBinomialHeap) Link(heaps ...Node) Node

func (SkewBinomialHeap) Peek 

func (s SkewBinomialHeap) Peek() QueuePriority

func (SkewBinomialHeap) Rank 

func (s SkewBinomialHeap) Rank() int

type SkewBinomialQueue 

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

func NewEmptySkewBinomialQueue 

func NewEmptySkewBinomialQueue() SkewBinomialQueue

func (SkewBinomialQueue) Dequeue 

func (q SkewBinomialQueue) Dequeue() (QueuePriority, PriorityQueue)

func (SkewBinomialQueue) DequeueWithMergeCallback 

func (q SkewBinomialQueue) DequeueWithMergeCallback(callback func([]Node, ...*SkewBinomialQueue) SkewBinomialQueue) (QueuePriority, PriorityQueue)

func (SkewBinomialQueue) Enqueue 

func (q SkewBinomialQueue) Enqueue(priority QueuePriority) PriorityQueue

func (SkewBinomialQueue) IsEmpty 

func (q SkewBinomialQueue) IsEmpty() bool

func (SkewBinomialQueue) Length 

func (q SkewBinomialQueue) Length() int

func (SkewBinomialQueue) Meld 

func (q SkewBinomialQueue) Meld(otherQ PriorityQueue) PriorityQueue

func (SkewBinomialQueue) Peek 

func (q SkewBinomialQueue) Peek() QueuePriority

func (SkewBinomialQueue) String 

func (q SkewBinomialQueue) String() string

type ThreadSafeList 

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

func NewThreadSafeList 

func NewThreadSafeList() ThreadSafeList

func (ThreadSafeList) Count 

func (t ThreadSafeList) Count() int

func (*ThreadSafeList) DeleteObject 

func (t *ThreadSafeList) DeleteObject(object unsafe.Pointer) (success bool)

func (*ThreadSafeList) InsertObject 

func (t *ThreadSafeList) InsertObject(object unsafe.Pointer, lessThanFn func(unsafe.Pointer, unsafe.Pointer) bool)

func (ThreadSafeList) Iter 

func (t ThreadSafeList) Iter() <-chan unsafe.Pointer

func (ThreadSafeList) LengthGreaterThan 

func (t ThreadSafeList) LengthGreaterThan(n int) bool

func (ThreadSafeList) Peek 

func (t ThreadSafeList) Peek() unsafe.Pointer

func (*ThreadSafeList) PopFirst 

func (t *ThreadSafeList) PopFirst(failAddress unsafe.Pointer) unsafe.Pointer

func (*ThreadSafeList) PopHead 

func (t *ThreadSafeList) PopHead() unsafe.Pointer

func (ThreadSafeList) PopNth 

func (t ThreadSafeList) PopNth(n int, failAddress unsafe.Pointer) unsafe.Pointer

type TrySplitParameter 

type TrySplitParameter struct {
	N int
	// contains filtered or unexported fields
}

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.