Documentation
¶
Overview ¶
Package goque provides embedded, disk-based implementations of stack, queue, and priority queue data structures.
Motivation for creating this project was the need for a persistent priority queue that remained performant while growing well beyond the available memory of a given machine. While there are many packages for Go offering queues, they all seem to be memory based and/or standalone solutions that are not embeddable within an application.
Instead of using an in-memory heap structure to store data, everything is stored using the Go port of LevelDB (https://github.com/syndtr/goleveldb). This results in very little memory being used no matter the size of the database, while read and write performance remains near constant.
See README.md or visit https://github.com/beeker1121/goque for more info.
Example (Object) ¶
ExampleObject demonstrates enqueuing a struct object.
package main
import (
"fmt"
"github.com/beeker1121/goque"
)
func main() {
// Open/create a queue.
q, err := goque.OpenQueue("data_dir")
if err != nil {
fmt.Println(err)
return
}
defer q.Close()
// Define our struct.
type object struct {
X int
Y int
}
// Create a new item with our struct.
item, err := goque.NewItemObject(object{X: 1, Y: 2})
if err != nil {
fmt.Println(err)
return
}
// Enqueue the item.
err = q.Enqueue(item)
if err != nil {
fmt.Println(err)
return
}
fmt.Println(item.ID) // 1
fmt.Println(item.Key) // [0 0 0 0 0 0 0 1]
fmt.Println(item.Value) // [105 116 101 109 32 118 97 108 117 101]
// Dequeue the item.
deqItem, err := q.Dequeue()
if err != nil {
fmt.Println(err)
return
}
// Create a variable to hold our decoded struct in.
var obj object
// Decode the item into our struct type.
if err := deqItem.ToObject(&obj); err != nil {
fmt.Println(err)
return
}
fmt.Printf("%+v\n", obj) // {X:1 Y:2}
}
Output:
Example (PriorityQueue) ¶
ExampleQueue demonstrates the implementation of a Goque queue.
package main
import (
"fmt"
"github.com/beeker1121/goque"
)
func main() {
// Open/create a priority queue.
pq, err := goque.OpenPriorityQueue("data_dir", goque.ASC)
if err != nil {
fmt.Println(err)
return
}
defer pq.Close()
// Create a new item.
item := goque.NewPriorityItem([]byte("item value"), 0)
// Enqueue the item.
err = pq.Enqueue(item)
if err != nil {
fmt.Println(err)
return
}
fmt.Println(item.ID) // 1
fmt.Println(item.Priority) // 0
fmt.Println(item.Key) // [0 0 0 0 0 0 0 1]
fmt.Println(item.Value) // [105 116 101 109 32 118 97 108 117 101]
fmt.Println(item.ToString()) // item value
// Change the item value in the queue.
err = pq.Update(item, []byte("new item value"))
if err != nil {
fmt.Println(err)
return
}
fmt.Println(item.ToString()) // new item value
// Dequeue the next item.
deqItem, err := pq.Dequeue()
if err != nil {
fmt.Println(err)
return
}
fmt.Println(deqItem.ToString()) // new item value
}
Output:
Example (Queue) ¶
ExampleQueue demonstrates the implementation of a Goque queue.
package main
import (
"fmt"
"github.com/beeker1121/goque"
)
func main() {
// Open/create a queue.
q, err := goque.OpenQueue("data_dir")
if err != nil {
fmt.Println(err)
return
}
defer q.Close()
// Create a new item.
item := goque.NewItem([]byte("item value"))
// Enqueue the item.
err = q.Enqueue(item)
if err != nil {
fmt.Println(err)
return
}
fmt.Println(item.ID) // 1
fmt.Println(item.Key) // [0 0 0 0 0 0 0 1]
fmt.Println(item.Value) // [105 116 101 109 32 118 97 108 117 101]
fmt.Println(item.ToString()) // item value
// Change the item value in the queue.
err = q.Update(item, []byte("new item value"))
if err != nil {
fmt.Println(err)
return
}
fmt.Println(item.ToString()) // new item value
// Dequeue the next item.
deqItem, err := q.Dequeue()
if err != nil {
fmt.Println(err)
return
}
fmt.Println(deqItem.ToString()) // new item value
}
Output:
Example (Stack) ¶
ExampleStack demonstrates the implementation of a Goque stack.
package main
import (
"fmt"
"github.com/beeker1121/goque"
)
func main() {
// Open/create a stack.
s, err := goque.OpenStack("data_dir")
if err != nil {
fmt.Println(err)
return
}
defer s.Close()
// Create a new item.
item := goque.NewItem([]byte("item value"))
// Push it onto the stack.
err = s.Push(item)
if err != nil {
fmt.Println(err)
return
}
fmt.Println(item.ID) // 1
fmt.Println(item.Key) // [0 0 0 0 0 0 0 1]
fmt.Println(item.Value) // [105 116 101 109 32 118 97 108 117 101]
fmt.Println(item.ToString()) // item value
// Change the item value in the stack.
err = s.Update(item, []byte("new item value"))
if err != nil {
fmt.Println(err)
return
}
fmt.Println(item.ToString()) // new item value
// Pop an item off the stack.
popItem, err := s.Pop()
if err != nil {
fmt.Println(err)
return
}
fmt.Println(popItem.ToString()) // new item value
}
Output:
Index ¶
- Constants
- Variables
- type Item
- type PriorityItem
- type PriorityQueue
- func (pq *PriorityQueue) Close()
- func (pq *PriorityQueue) Dequeue() (*PriorityItem, error)
- func (pq *PriorityQueue) DequeueByPriority(priority uint8) (*PriorityItem, error)
- func (pq *PriorityQueue) Drop()
- func (pq *PriorityQueue) Enqueue(item *PriorityItem) error
- func (pq *PriorityQueue) Length() uint64
- func (pq *PriorityQueue) Peek() (*PriorityItem, error)
- func (pq *PriorityQueue) PeekByOffset(offset uint64) (*PriorityItem, error)
- func (pq *PriorityQueue) PeekByPriorityID(priority uint8, id uint64) (*PriorityItem, error)
- func (pq *PriorityQueue) Update(item *PriorityItem, newValue []byte) error
- func (pq *PriorityQueue) UpdateObject(item *PriorityItem, newValue interface{}) error
- func (pq *PriorityQueue) UpdateString(item *PriorityItem, newValue string) error
- type Queue
- func (q *Queue) Close()
- func (q *Queue) Dequeue() (*Item, error)
- func (q *Queue) Drop()
- func (q *Queue) Enqueue(item *Item) error
- func (q *Queue) Length() uint64
- func (q *Queue) Peek() (*Item, error)
- func (q *Queue) PeekByID(id uint64) (*Item, error)
- func (q *Queue) PeekByOffset(offset uint64) (*Item, error)
- func (q *Queue) Update(item *Item, newValue []byte) error
- func (q *Queue) UpdateObject(item *Item, newValue interface{}) error
- func (q *Queue) UpdateString(item *Item, newValue string) error
- type Stack
- func (s *Stack) Close()
- func (s *Stack) Drop()
- func (s *Stack) Length() uint64
- func (s *Stack) Peek() (*Item, error)
- func (s *Stack) PeekByID(id uint64) (*Item, error)
- func (s *Stack) PeekByOffset(offset uint64) (*Item, error)
- func (s *Stack) Pop() (*Item, error)
- func (s *Stack) Push(item *Item) error
- func (s *Stack) Update(item *Item, newValue []byte) error
- func (s *Stack) UpdateObject(item *Item, newValue interface{}) error
- func (s *Stack) UpdateString(item *Item, newValue string) error
Examples ¶
Constants ¶
const ( ASC order = iota // Set priority level 0 as most important. DESC // Set priority level 255 as most important. )
Defines which priority order to dequeue in.
Variables ¶
var ( // ErrIncompatibleType is returned when the opener type is // incompatible with the stored Goque type. ErrIncompatibleType = errors.New("goque: Opener type is incompatible with stored Goque type") // ErrEmpty is returned when the stack or queue is empty. ErrEmpty = errors.New("goque: Stack or queue is empty") // ErrOutOfBounds is returned when the ID used to lookup an item // is outside of the range of the stack or queue. ErrOutOfBounds = errors.New("goque: ID used is outside range of stack or queue") // ErrDBClosed is returned when the Close function has already // been called, causing the stack or queue to close, as well as // its underlying database. ErrDBClosed = errors.New("goque: Database is closed") )
Functions ¶
This section is empty.
Types ¶
type Item ¶
Item represents an entry in either a stack or queue.
func NewItemObject ¶
NewItemObject is a helper function for NewItem that accepts any value type, which is then encoded into a byte slice using encoding/gob.
func NewItemString ¶
NewItemString is a helper function for NewItem that accepts a value as a string rather than a byte slice.
type PriorityItem ¶
PriorityItem represents an entry in a priority queue.
func NewPriorityItem ¶
func NewPriorityItem(value []byte, priority uint8) *PriorityItem
NewPriorityItem creates a new item for use with a priority queue.
func NewPriorityItemObject ¶
func NewPriorityItemObject(value interface{}, priority uint8) (*PriorityItem, error)
NewPriorityItemObject is a helper function for NewPriorityItem that accepts any value type, which is then encoded into a byte slice using encoding/gob.
func NewPriorityItemString ¶
func NewPriorityItemString(value string, priority uint8) *PriorityItem
NewPriorityItemString is a helper function for NewPriorityItem that accepts a value as a string rather than a byte slice.
func (*PriorityItem) ToObject ¶
func (pi *PriorityItem) ToObject(value interface{}) error
ToObject decodes the item value into the given value type using encoding/gob.
The value passed to this method should be a pointer to a variable of the type you wish to decode into. The variable pointed to will hold the decoded object.
func (*PriorityItem) ToString ¶
func (pi *PriorityItem) ToString() string
ToString returns the priority item value as a string.
type PriorityQueue ¶
PriorityQueue is a standard FIFO (first in, first out) queue with priority levels.
func OpenPriorityQueue ¶
func OpenPriorityQueue(dataDir string, order order) (*PriorityQueue, error)
OpenPriorityQueue opens a priority queue if one exists at the given directory. If one does not already exist, a new priority queue is created.
func (*PriorityQueue) Close ¶
func (pq *PriorityQueue) Close()
Close closes the LevelDB database of the priority queue.
func (*PriorityQueue) Dequeue ¶
func (pq *PriorityQueue) Dequeue() (*PriorityItem, error)
Dequeue removes the next item in the priority queue and returns it.
func (*PriorityQueue) DequeueByPriority ¶
func (pq *PriorityQueue) DequeueByPriority(priority uint8) (*PriorityItem, error)
DequeueByPriority removes the next item in the given priority level and returns it.
func (*PriorityQueue) Drop ¶
func (pq *PriorityQueue) Drop()
Drop closes and deletes the LevelDB database of the priority queue.
func (*PriorityQueue) Enqueue ¶
func (pq *PriorityQueue) Enqueue(item *PriorityItem) error
Enqueue adds an item to the priority queue.
func (*PriorityQueue) Length ¶
func (pq *PriorityQueue) Length() uint64
Length returns the total number of items in the priority queue.
func (*PriorityQueue) Peek ¶
func (pq *PriorityQueue) Peek() (*PriorityItem, error)
Peek returns the next item in the priority queue without removing it.
func (*PriorityQueue) PeekByOffset ¶
func (pq *PriorityQueue) PeekByOffset(offset uint64) (*PriorityItem, error)
PeekByOffset returns the item located at the given offset, starting from the head of the queue, without removing it.
func (*PriorityQueue) PeekByPriorityID ¶
func (pq *PriorityQueue) PeekByPriorityID(priority uint8, id uint64) (*PriorityItem, error)
PeekByPriorityID returns the item with the given ID and priority without removing it.
func (*PriorityQueue) Update ¶
func (pq *PriorityQueue) Update(item *PriorityItem, newValue []byte) error
Update updates an item in the priority queue without changing its position.
func (*PriorityQueue) UpdateObject ¶
func (pq *PriorityQueue) UpdateObject(item *PriorityItem, newValue interface{}) error
UpdateObject is a helper function for Update that accepts any value type, which is then encoded into a byte slice using encoding/gob.
func (*PriorityQueue) UpdateString ¶
func (pq *PriorityQueue) UpdateString(item *PriorityItem, newValue string) error
UpdateString is a helper function for Update that accepts a value as a string rather than a byte slice.
type Queue ¶
Queue is a standard FIFO (first in, first out) queue.
func OpenQueue ¶
OpenQueue opens a queue if one exists at the given directory. If one does not already exist, a new queue is created.
func (*Queue) Drop ¶
func (q *Queue) Drop()
Drop closes and deletes the LevelDB database of the queue.
func (*Queue) PeekByOffset ¶
PeekByOffset returns the item located at the given offset, starting from the head of the queue, without removing it.
func (*Queue) UpdateObject ¶
UpdateObject is a helper function for Update that accepts any value type, which is then encoded into a byte slice using encoding/gob.
type Stack ¶
Stack is a standard LIFO (last in, first out) stack.
func OpenStack ¶
OpenStack opens a stack if one exists at the given directory. If one does not already exist, a new stack is created.
func (*Stack) Drop ¶
func (s *Stack) Drop()
Drop closes and deletes the LevelDB database of the stack.
func (*Stack) PeekByOffset ¶
PeekByOffset returns the item located at the given offset, starting from the head of the stack, without removing it.
func (*Stack) UpdateObject ¶
UpdateObject is a helper function for Update that accepts any value type, which is then encoded into a byte slice using encoding/gob.