README
¶
Queues Library
This library provides a rich set of data structures for queuing in Go. It includes implementations for both a FIFO ( First-In-First-Out) queue and a priority queue.
Features
- Generic Implementation: Both the FIFO and priority queues are implemented using Go's new generics feature, allowing you to queue items of any type.
- Thread-Safety: Built with concurrency in mind, you can safely use the queues across multiple goroutines.
- Timeouts for Polling: The
Pollfunction allows consumers to wait for items with a timeout.
Structures
FIFOQueueImpl
A standard FIFO (First-In-First-Out) queue implementation.
Methods
NewFIFOQueue: Initializes a new FIFO queue with optional initial elements.Queue: Enqueues an item to the back of the queue.Fetch: Dequeues an item from the front of the queue without waiting.Poll: Dequeues an item from the front of the queue or waits for a specified timeout.
PriorityQueueImpl
A priority queue where items can be enqueued with a priority level, and dequeuing will retrieve the highest priority item.
Methods
NewPrioritizedPriorityQueue: Initializes a new empty priority queue.Queue: Enqueues an item with a specified priority.Fetch: Dequeues the highest-priority item from the queue without waiting.Poll: Dequeues the highest-priority item from the queue or waits for a specified timeout.
Dependencies
The library uses the container/heap package for the priority queue implementation and an opt package for optional
value handling.
Usage
First, import the queue package in your Go code:
package myprogram
import "github.com/kordax/basic-utils/queue"
// To use the FIFO queue:
q := queue.NewFIFOQueue[int](1, 2, 3)
q.Queue(4)
item := q.Poll(5 * time.Second)
For the priority queue:
pq := queue.NewPrioritizedPriorityQueueint
pq.Queue(1, 3) // The number 3 here is the priority
pq.Queue(2, 1)
item := pq.Poll(5 * time.Second)
Author
Developed by @kordax (Dmitry Morozov)
Documentation
¶
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type ConcurrentFIFOQueueImpl ¶
type ConcurrentFIFOQueueImpl[T any] struct { // contains filtered or unexported fields }
ConcurrentFIFOQueueImpl implementation that queues/dequeues items according to https://www.cs.rochester.edu/~scott/papers/1996_PODC_queues.pdf
func NewConcurrentFIFOQueueImpl ¶
func NewConcurrentFIFOQueueImpl[T any]() *ConcurrentFIFOQueueImpl[T]
func (*ConcurrentFIFOQueueImpl[T]) Fetch ¶
func (q *ConcurrentFIFOQueueImpl[T]) Fetch() opt.Opt[T]
Fetch fetches item in the finite time.
func (*ConcurrentFIFOQueueImpl[T]) Len ¶
func (q *ConcurrentFIFOQueueImpl[T]) Len() uint64
func (*ConcurrentFIFOQueueImpl[T]) Poll ¶
func (q *ConcurrentFIFOQueueImpl[T]) Poll(timeout time.Duration) opt.Opt[T]
Poll items fetches item in the finite time.
func (*ConcurrentFIFOQueueImpl[T]) Queue ¶
func (q *ConcurrentFIFOQueueImpl[T]) Queue(t T)
Queue queues an item in the finite time. This operation is thread-safe yet is not "synchronized" by its nature. Implementation uses Michael-Scott CAS implementation.
type FIFOQueueImpl ¶
type FIFOQueueImpl[T any] struct { // contains filtered or unexported fields }
FIFOQueueImpl represents a generic implementation of a First-In-First-Out (FIFO) data structure. This struct uses a slice to maintain elements in the order they are added, ensuring that the oldest item (the first one added) is the first to be fetched.
Fields: - queue: Slice holding the actual elements. It grows dynamically as new elements are added.
- ch: A communication channel utilized in the Poll() method. The channel is used to help in fetching elements with a specified timeout. When a new item is queued and the channel is not full, the new item's pointer is sent into the channel.
Note: This implementation isn't thread-safe. If concurrent access is required please use ConcurrentFIFOQueueImpl.
func NewFIFOQueue ¶
func NewFIFOQueue[T any](elements ...T) *FIFOQueueImpl[T]
func (*FIFOQueueImpl[T]) Fetch ¶
func (q *FIFOQueueImpl[T]) Fetch() opt.Opt[T]
func (*FIFOQueueImpl[T]) Len ¶
func (q *FIFOQueueImpl[T]) Len() uint64
func (*FIFOQueueImpl[T]) Queue ¶
func (q *FIFOQueueImpl[T]) Queue(t T)
Queue queues an item. This operation is not thread-safe, and a synchronization wrapper should be provided in case consistent results are required in an async environment.
type PriorityQueue ¶
type PriorityQueueImpl ¶
type PriorityQueueImpl[T any] struct { // contains filtered or unexported fields }
PriorityQueueImpl represents a generic implementation of a priority queue data structure. Items are organized based on their priorities, with higher-priority items being fetched before lower-priority ones. This struct uses a heap data structure (as implemented in the "container/heap" package) to efficiently manage the priorities and retrieval of items.
Fields: - queue: The underlying heap structure (prioritizedQueue) that manages the prioritized items.
- ch: A communication channel utilized in the Poll() method. The channel is used to assist in fetching elements with a specified timeout. When a new item is queued and the channel is not full, the new item's pointer is sent into the channel.
Note: This implementation isn't inherently thread-safe. If concurrent access is anticipated,
external synchronization mechanisms should be used, or you can use ConcurrentFIFOQueueImpl.
func NewPriorityQueue ¶
func NewPriorityQueue[T any]() *PriorityQueueImpl[T]
func (*PriorityQueueImpl[T]) Fetch ¶
func (q *PriorityQueueImpl[T]) Fetch() opt.Opt[T]
func (*PriorityQueueImpl[T]) Len ¶
func (q *PriorityQueueImpl[T]) Len() uint64
func (*PriorityQueueImpl[T]) Poll ¶
func (q *PriorityQueueImpl[T]) Poll(timeout time.Duration) opt.Opt[T]
func (*PriorityQueueImpl[T]) Queue ¶
func (q *PriorityQueueImpl[T]) Queue(t T, priority int)
Source Files