goque: github.com/beeker1121/goque Index | Examples | Files

package goque

import "github.com/beeker1121/goque"

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.

ExampleObject demonstrates enqueuing a struct object.

Code:

// 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
}

// Enqueue an object.
item, err := q.EnqueueObject(object{X: 1, Y: 2})
if err != nil {
    fmt.Println(err)
    return
}

fmt.Println(item.ID)  // 1
fmt.Println(item.Key) // [0 0 0 0 0 0 0 1]

// Dequeue an item.
deqItem, err := q.Dequeue()
if err != nil {
    fmt.Println(err)
    return
}

// Create variable to hold our object in.
var obj object

// Decode 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}

// Delete the queue and its database.
q.Drop()

ExamplePrefixQueue demonstrates the implementation of a Goque queue.

Code:

// Open/create a prefix queue.
pq, err := goque.OpenPrefixQueue("data_dir")
if err != nil {
    fmt.Println(err)
    return
}
defer pq.Close()

// Enqueue an item.
item, err := pq.Enqueue([]byte("prefix"), []byte("item value"))
if err != nil {
    fmt.Println(err)
    return
}

fmt.Println(item.ID)         // 1
fmt.Println(item.Key)        // [112 114 101 102 105 120 0 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.
item, err = pq.Update([]byte("prefix"), item.ID, []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([]byte("prefix"))
if err != nil {
    fmt.Println(err)
    return
}

fmt.Println(deqItem.ToString()) // new item value

// Delete the queue and its database.
pq.Drop()

ExamplePriorityQueue demonstrates the implementation of a Goque queue.

Code:

// Open/create a priority queue.
pq, err := goque.OpenPriorityQueue("data_dir", goque.ASC)
if err != nil {
    fmt.Println(err)
    return
}
defer pq.Close()

// Enqueue the item.
item, err := pq.Enqueue(0, []byte("item value"))
if err != nil {
    fmt.Println(err)
    return
}

fmt.Println(item.ID)         // 1
fmt.Println(item.Priority)   // 0
fmt.Println(item.Key)        // [0 58 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.
item, err = pq.Update(item.Priority, item.ID, []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

// Delete the queue and its database.
pq.Drop()

ExampleQueue demonstrates the implementation of a Goque queue.

Code:

// Open/create a queue.
q, err := goque.OpenQueue("data_dir")
if err != nil {
    fmt.Println(err)
    return
}
defer q.Close()

// Enqueue an item.
item, err := q.Enqueue([]byte("item value"))
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.
item, err = q.Update(item.ID, []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

// Delete the queue and its database.
q.Drop()

ExampleStack demonstrates the implementation of a Goque stack.

Code:

// Open/create a stack.
s, err := goque.OpenStack("data_dir")
if err != nil {
    fmt.Println(err)
    return
}
defer s.Close()

// Push an item onto the stack.
item, err := s.Push([]byte("item value"))
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.
item, err = s.Update(item.ID, []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

// Delete the stack and its database.
s.Drop()

Index

Examples

Package Files

doc.go errors.go file.go item.go prefix_queue.go priority_queue.go queue.go stack.go

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")
)

type Item Uses

type Item struct {
    ID    uint64
    Key   []byte
    Value []byte
}

Item represents an entry in either a stack or queue.

func (*Item) ToObject Uses

func (i *Item) 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 (*Item) ToString Uses

func (i *Item) ToString() string

ToString returns the item value as a string.

type PrefixQueue Uses

type PrefixQueue struct {
    sync.RWMutex
    DataDir string
    // contains filtered or unexported fields
}

PrefixQueue is a standard FIFO (first in, first out) queue that separates each given prefix into its own queue.

func OpenPrefixQueue Uses

func OpenPrefixQueue(dataDir string) (*PrefixQueue, error)

OpenPrefixQueue opens a prefix queue if one exists at the given directory. If one does not already exist, a new prefix queue is created.

func (*PrefixQueue) Close Uses

func (pq *PrefixQueue) Close() error

Close closes the LevelDB database of the prefix queue.

func (*PrefixQueue) Dequeue Uses

func (pq *PrefixQueue) Dequeue(prefix []byte) (*Item, error)

Dequeue removes the next item in the prefix queue and returns it.

func (*PrefixQueue) DequeueString Uses

func (pq *PrefixQueue) DequeueString(prefix string) (*Item, error)

DequeueString is a helper function for Dequeue that accepts the prefix as a string rather than a byte slice.

func (*PrefixQueue) Drop Uses

func (pq *PrefixQueue) Drop() error

Drop closes and deletes the LevelDB database of the prefix queue.

func (*PrefixQueue) Enqueue Uses

func (pq *PrefixQueue) Enqueue(prefix, value []byte) (*Item, error)

Enqueue adds an item to the queue.

func (*PrefixQueue) EnqueueObject Uses

func (pq *PrefixQueue) EnqueueObject(prefix []byte, value interface{}) (*Item, error)

EnqueueObject is a helper function for Enqueue that accepts any value type, which is then encoded into a byte slice using encoding/gob.

func (*PrefixQueue) EnqueueString Uses

func (pq *PrefixQueue) EnqueueString(prefix, value string) (*Item, error)

EnqueueString is a helper function for Enqueue that accepts the prefix and value as a string rather than a byte slice.

func (*PrefixQueue) Length Uses

func (pq *PrefixQueue) Length() uint64

Length returns the total number of items in the prefix queue.

func (*PrefixQueue) Peek Uses

func (pq *PrefixQueue) Peek(prefix []byte) (*Item, error)

Peek returns the next item in the given queue without removing it.

func (*PrefixQueue) PeekByID Uses

func (pq *PrefixQueue) PeekByID(prefix []byte, id uint64) (*Item, error)

PeekByID returns the item with the given ID without removing it.

func (*PrefixQueue) PeekByIDString Uses

func (pq *PrefixQueue) PeekByIDString(prefix string, id uint64) (*Item, error)

PeekByIDString is a helper function for Peek that accepts the prefix as a string rather than a byte slice.

func (*PrefixQueue) PeekString Uses

func (pq *PrefixQueue) PeekString(prefix string) (*Item, error)

PeekString is a helper function for Peek that accepts the prefix as a string rather than a byte slice.

func (*PrefixQueue) Update Uses

func (pq *PrefixQueue) Update(prefix []byte, id uint64, newValue []byte) (*Item, error)

Update updates an item in the given queue without changing its position.

func (*PrefixQueue) UpdateObject Uses

func (pq *PrefixQueue) UpdateObject(prefix []byte, id uint64, newValue interface{}) (*Item, 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 (*PrefixQueue) UpdateString Uses

func (pq *PrefixQueue) UpdateString(prefix string, id uint64, value string) (*Item, error)

UpdateString is a helper function for Update that accepts the prefix and value as a string rather than a byte slice.

type PriorityItem Uses

type PriorityItem struct {
    ID       uint64
    Priority uint8
    Key      []byte
    Value    []byte
}

PriorityItem represents an entry in a priority queue.

func (*PriorityItem) ToObject Uses

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 Uses

func (pi *PriorityItem) ToString() string

ToString returns the priority item value as a string.

type PriorityQueue Uses

type PriorityQueue struct {
    sync.RWMutex
    DataDir string
    // contains filtered or unexported fields
}

PriorityQueue is a standard FIFO (first in, first out) queue with priority levels.

func OpenPriorityQueue Uses

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 Uses

func (pq *PriorityQueue) Close() error

Close closes the LevelDB database of the priority queue.

func (*PriorityQueue) Dequeue Uses

func (pq *PriorityQueue) Dequeue() (*PriorityItem, error)

Dequeue removes the next item in the priority queue and returns it.

func (*PriorityQueue) DequeueByPriority Uses

func (pq *PriorityQueue) DequeueByPriority(priority uint8) (*PriorityItem, error)

DequeueByPriority removes the next item in the given priority level and returns it.

func (*PriorityQueue) Drop Uses

func (pq *PriorityQueue) Drop() error

Drop closes and deletes the LevelDB database of the priority queue.

func (*PriorityQueue) Enqueue Uses

func (pq *PriorityQueue) Enqueue(priority uint8, value []byte) (*PriorityItem, error)

Enqueue adds an item to the priority queue.

func (*PriorityQueue) EnqueueObject Uses

func (pq *PriorityQueue) EnqueueObject(priority uint8, value interface{}) (*PriorityItem, error)

EnqueueObject is a helper function for Enqueue that accepts any value type, which is then encoded into a byte slice using encoding/gob.

func (*PriorityQueue) EnqueueString Uses

func (pq *PriorityQueue) EnqueueString(priority uint8, value string) (*PriorityItem, error)

EnqueueString is a helper function for Enqueue that accepts a value as a string rather than a byte slice.

func (*PriorityQueue) Length Uses

func (pq *PriorityQueue) Length() uint64

Length returns the total number of items in the priority queue.

func (*PriorityQueue) Peek Uses

func (pq *PriorityQueue) Peek() (*PriorityItem, error)

Peek returns the next item in the priority queue without removing it.

func (*PriorityQueue) PeekByOffset Uses

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 Uses

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 Uses

func (pq *PriorityQueue) Update(priority uint8, id uint64, newValue []byte) (*PriorityItem, error)

Update updates an item in the priority queue without changing its position.

func (*PriorityQueue) UpdateObject Uses

func (pq *PriorityQueue) UpdateObject(priority uint8, id uint64, newValue interface{}) (*PriorityItem, 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 Uses

func (pq *PriorityQueue) UpdateString(priority uint8, id uint64, newValue string) (*PriorityItem, error)

UpdateString is a helper function for Update that accepts a value as a string rather than a byte slice.

type Queue Uses

type Queue struct {
    sync.RWMutex
    DataDir string
    // contains filtered or unexported fields
}

Queue is a standard FIFO (first in, first out) queue.

func OpenQueue Uses

func OpenQueue(dataDir string) (*Queue, error)

OpenQueue opens a queue if one exists at the given directory. If one does not already exist, a new queue is created.

func (*Queue) Close Uses

func (q *Queue) Close() error

Close closes the LevelDB database of the queue.

func (*Queue) Dequeue Uses

func (q *Queue) Dequeue() (*Item, error)

Dequeue removes the next item in the queue and returns it.

func (*Queue) Drop Uses

func (q *Queue) Drop() error

Drop closes and deletes the LevelDB database of the queue.

func (*Queue) Enqueue Uses

func (q *Queue) Enqueue(value []byte) (*Item, error)

Enqueue adds an item to the queue.

func (*Queue) EnqueueObject Uses

func (q *Queue) EnqueueObject(value interface{}) (*Item, error)

EnqueueObject is a helper function for Enqueue that accepts any value type, which is then encoded into a byte slice using encoding/gob.

func (*Queue) EnqueueString Uses

func (q *Queue) EnqueueString(value string) (*Item, error)

EnqueueString is a helper function for Enqueue that accepts a value as a string rather than a byte slice.

func (*Queue) Length Uses

func (q *Queue) Length() uint64

Length returns the total number of items in the queue.

func (*Queue) Peek Uses

func (q *Queue) Peek() (*Item, error)

Peek returns the next item in the queue without removing it.

func (*Queue) PeekByID Uses

func (q *Queue) PeekByID(id uint64) (*Item, error)

PeekByID returns the item with the given ID without removing it.

func (*Queue) PeekByOffset Uses

func (q *Queue) PeekByOffset(offset uint64) (*Item, error)

PeekByOffset returns the item located at the given offset, starting from the head of the queue, without removing it.

func (*Queue) Update Uses

func (q *Queue) Update(id uint64, newValue []byte) (*Item, error)

Update updates an item in the queue without changing its position.

func (*Queue) UpdateObject Uses

func (q *Queue) UpdateObject(id uint64, newValue interface{}) (*Item, 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 (*Queue) UpdateString Uses

func (q *Queue) UpdateString(id uint64, newValue string) (*Item, error)

UpdateString is a helper function for Update that accepts a value as a string rather than a byte slice.

type Stack Uses

type Stack struct {
    sync.RWMutex
    DataDir string
    // contains filtered or unexported fields
}

Stack is a standard LIFO (last in, first out) stack.

func OpenStack Uses

func OpenStack(dataDir string) (*Stack, error)

OpenStack opens a stack if one exists at the given directory. If one does not already exist, a new stack is created.

func (*Stack) Close Uses

func (s *Stack) Close() error

Close closes the LevelDB database of the stack.

func (*Stack) Drop Uses

func (s *Stack) Drop() error

Drop closes and deletes the LevelDB database of the stack.

func (*Stack) Length Uses

func (s *Stack) Length() uint64

Length returns the total number of items in the stack.

func (*Stack) Peek Uses

func (s *Stack) Peek() (*Item, error)

Peek returns the next item in the stack without removing it.

func (*Stack) PeekByID Uses

func (s *Stack) PeekByID(id uint64) (*Item, error)

PeekByID returns the item with the given ID without removing it.

func (*Stack) PeekByOffset Uses

func (s *Stack) PeekByOffset(offset uint64) (*Item, error)

PeekByOffset returns the item located at the given offset, starting from the head of the stack, without removing it.

func (*Stack) Pop Uses

func (s *Stack) Pop() (*Item, error)

Pop removes the next item in the stack and returns it.

func (*Stack) Push Uses

func (s *Stack) Push(value []byte) (*Item, error)

Push adds an item to the stack.

func (*Stack) PushObject Uses

func (s *Stack) PushObject(value interface{}) (*Item, error)

PushObject is a helper function for Push that accepts any value type, which is then encoded into a byte slice using encoding/gob.

func (*Stack) PushString Uses

func (s *Stack) PushString(value string) (*Item, error)

PushString is a helper function for Push that accepts a value as a string rather than a byte slice.

func (*Stack) Update Uses

func (s *Stack) Update(id uint64, newValue []byte) (*Item, error)

Update updates an item in the stack without changing its position.

func (*Stack) UpdateObject Uses

func (s *Stack) UpdateObject(id uint64, newValue interface{}) (*Item, 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 (*Stack) UpdateString Uses

func (s *Stack) UpdateString(id uint64, newValue string) (*Item, error)

UpdateString is a helper function for Update that accepts a value as a string rather than a byte slice.

Package goque imports 10 packages (graph) and is imported by 13 packages. Updated 2017-06-15. Refresh now. Tools for package owners.