blocking_dequeue

README

Blocking Dequeue

This package (repo) provides an implementation of a thread-safe, blocking, generic dequeue that can be used as FIFO or LIFO or a hybrid between the 2.

Installation

To install this package, you will need to setup your go workspace first. Also this package requires go v1.18 or later.

1. To install the package run the following command:

   go get github.com/AmrSaber/go-blocking-dequeue
   

2. To import the package:

   import "github.com/AmrSaber/go-blocking-dequeue"
   

3. Use the package in code using blocking_dequeue module (see usage below).

Usage

Initialization

To create a new dequeue use blocking_dequeue.NewBlockingDequeue function as follows:

// Integers dequeue
buffer := make([]int, 10)
integersDequeue := blocking_dequeue.NewBlockingDequeue(buffer)
integersDequeue.PushBack(10)

// Strings dequeue
buffer := make([]string, 10)
stringsDequeue := blocking_dequeue.NewBlockingDequeue(buffer)
stringsDequeue.PushBack("hello")

type User struct {
  Username string
  Age      int
}

// Dequeue of custom type
buffer := make([]User, 10)
usersDequeue := blocking_dequeue.NewBlockingDequeue(buffer)
usersDequeue.PushBack(User{ "Amr", 25 })

// Pointer dequeue
buffer := make([]*User, 10)
usersPtrDequeue := blocking_dequeue.NewBlockingDequeue(buffer)
usersPtrDequeue.PushBack(&User{ "Amr", 25 })

The dequeue is implemented using generics, so it can hold any datatype, just create a buffer with the desired datatype and pass it to the creation function.

Capacity

The capacity of the dequeue is the length of the provided buffer.

Usage as Queue

buffer := make([]int, 10)
dq := blocking_dequeue.NewBlockingDequeue(buffer)

dq.PushBack(1) // Pushed to the end of the dequeue
dq.PushBack(2) // Pushed to the end of the dequeue
dq.PushBack(3) // Pushed to the end of the dequeue

dq.PopFront() // Pops from the top, returns 1
dq.PopFront() // Pops from the top, returns 2
dq.PopFront() // Pops from the top, returns 3

Usage as Stack

buffer := make([]int, 10)
dq := blocking_dequeue.NewBlockingDequeue(buffer)

dq.PushFront(1) // Pushed to the start of the dequeue
dq.PushFront(2) // Pushed to the start of the dequeue
dq.PushFront(3) // Pushed to the start of the dequeue

dq.PopFront() // Pops from the top, returns 3
dq.PopFront() // Pops from the top, returns 2
dq.PopFront() // Pops from the top, returns 1

API Documentation

The package itself exposes 1 function NewBlockingQueue that is used to create a new dequeue and return a pointer to it.

The dequeue itself exposes the following methods:

• PushFront, PushBack
• PopFront, PopBack
• PeekFront, PeekBack
• Size, IsEmpty, IsFull

The detailed documentation can be found at the related go packages page.

Limitations and Drawbacks

This dequeue is implemented using ring (or circular) buffer so all of the operations are done in O(1) time complexity.

However, due to the thread-safe nature, and all the lock/unlock/wait/signal logic, it's expected to be a bit slower than plain ring buffer. If you intend to use this dequeue in a single threaded context (where only a single goroutine will have access to it) it's advised to use plain circular buffer or the built-in container/list instead.

If you intend to use it as a limited capacity queue to communicate between goroutines, it would be better to use built-in channels with buffer, so instead of

buffer := make([]int, 10)
dq := blocking_dequeue.NewBlockingDequeue(buffer)

// Push to queue
dq.PushBack(1)

// Pop from queue
dq.PopFront()

You better use

ch := make(chan int, 10)

// Push to queue
ch <- 1

// Pop from queue
<- ch

That is unless you need access the other provided methods, such as Peek variations, Size, IsFull, and so on...

Benchmarking

No benchmarking against plain ring buffer or the built-in container/list nor channels yet. But it's in the plan.

Contribution

If you find a bug, you are welcome to create a ticket on github or create a PR with the fix directly mentioning in the description of the PR what is the problem and how your PR fixes it.

If you want to suggest a feature (even if you have no idea how it will be implemented) feel free to open a ticket with it.

Documentation

Index

• type BlockingDequeue
  • func NewBlockingDequeue[T any](buffer []T) *BlockingDequeue[T]
  • func (d *BlockingDequeue[T]) IsEmpty() bool
  • func (d *BlockingDequeue[T]) IsFull() bool
  • func (d *BlockingDequeue[T]) PeekBack() T
  • func (d *BlockingDequeue[T]) PeekFront() T
  • func (d *BlockingDequeue[T]) PopBack() T
  • func (d *BlockingDequeue[T]) PopFront() T
  • func (d *BlockingDequeue[T]) PushBack(item T)
  • func (d *BlockingDequeue[T]) PushFront(item T)
  • func (d *BlockingDequeue[T]) Size() int

Types

type BlockingDequeue

type BlockingDequeue[T any] struct {
	// contains filtered or unexported fields
}

Blocking dequeue, implemented with a circular buffer. The dequeue is thread safe. And must not be copied.

func NewBlockingDequeue

func NewBlockingDequeue[T any](buffer []T) *BlockingDequeue[T]

Creates a new blocking dequeue with the provided buffer. The dequeue MUST only be created using this method.

func (*BlockingDequeue[T]) IsEmpty

func (d *BlockingDequeue[T]) IsEmpty() bool

Return true if the dequeue is empty.

func (*BlockingDequeue[T]) IsFull

func (d *BlockingDequeue[T]) IsFull() bool

Return true if the dequeue is full.

func (*BlockingDequeue[T]) PeekBack

func (d *BlockingDequeue[T]) PeekBack() T

Read the last item of the dequeue without removing it. Blocks if the dequeue is empty.

func (*BlockingDequeue[T]) PeekFront

func (d *BlockingDequeue[T]) PeekFront() T

Read the first item of the dequeue without removing it. Blocks if the dequeue is empty.

func (*BlockingDequeue[T]) PopBack

func (d *BlockingDequeue[T]) PopBack() T

Read the last item (at the end/back) of the dequeue and remove it. Blocks if the dequeue is empty.

func (*BlockingDequeue[T]) PopFront

func (d *BlockingDequeue[T]) PopFront() T

Read the first item (on the top/front) of the dequeue and remove it. Blocks if the dequeue is empty.

func (*BlockingDequeue[T]) PushBack

func (d *BlockingDequeue[T]) PushBack(item T)

Add an item to the back (bottom) of the dequeue. Blocks if dequeue is full.

func (*BlockingDequeue[T]) PushFront

func (d *BlockingDequeue[T]) PushFront(item T)

Add an item into the front (top) of the dequeue. Blocks if dequeue is full.

func (*BlockingDequeue[T]) Size

func (d *BlockingDequeue[T]) Size() int

Return the number of elements in the dequeue.