Class ScyllaDeque<T>

High-performance double-ended queue (deque) backed by a circular buffer. Supports O(1) amortized push and pop at both the front and the back, with O(1) peek at either end.

Inheritance
object
ScyllaDeque<T>
Implements
Inherited Members
Namespace: Scylla.Core.Structures
Assembly: ScyllaCore.dll
Syntax
public sealed class ScyllaDeque<T> : IScyllaCollection<T>, IScyllaCollection
Type Parameters
Name Description
T

The type of elements stored in the deque. May be a value type or a reference type. For reference types, popped slots are cleared to null to release references and allow garbage collection.
Remarks

Circular buffer layout: internally the deque maintains a flat array together with a _head index (pointing to the front element) and a _tail index (pointing to the first free slot past the back element). Both indices wrap around modulo the buffer length. The buffer is considered full when _count == _buffer.Length, and empty when _count == 0.

Growth policy: when IsFixedCapacity is false (the default), the buffer doubles in size whenever it is full and a push is attempted. The doubled buffer is allocated fresh and all existing elements are copied into it in front-to-back order so that _head == 0 after growth. When IsFixedCapacity is true, push operations simply return false instead of growing.

IScyllaCollection convention: TryAdd(T) delegates to TryPushBack(T) and TryRemove(out T) delegates to TryPopFront(out T), so a deque used through the abstract interface behaves as a FIFO queue. Use the explicit TryPush* / TryPop* API for stack or double-ended access patterns.

Thread safety: this class is unsynchronized by default. Call AsSynchronized(object) to obtain a ScyllaDeque<T>.SynchronizedScyllaDeque wrapper that protects every operation with a lock.

Enumeration: use foreach on the concrete type to iterate front-to-back without heap allocation. The value-type ScyllaDeque<T>.Enumerator snapshots the element count at construction time and does not detect concurrent modifications. 

// Direct construction
var deque = new ScyllaDeque<int>(capacity: 64, fixedCapacity: true);
// Using fluent builder for complex configuration
var deque = ScyllaDeque<string>.CreateBuilder()
    .WithCapacity(128)
    .FixedCapacity()
    .Synchronized()
    .Build();

Constructors

ScyllaDeque(int, bool)

Initializes a new ScyllaDeque<T> with the specified initial capacity and growth policy.

Declaration
public ScyllaDeque(int capacity = 4, bool fixedCapacity = false)
Parameters
Type Name Description
int capacity

The initial capacity of the backing circular buffer. Values less than 1 are silently clamped to 1. The deque does not allocate more than this until the first push that would exceed it (assuming fixedCapacity is false).
bool fixedCapacity

When true, the backing buffer never grows beyond capacity; push operations return false when the deque is full. When false (the default), the buffer doubles in size automatically when a push would exceed the current capacity.

Properties

Capabilities

Gets the capability flags advertised by this deque instance.

Declaration
public ScyllaCollectionCapabilities Capabilities { get; }
Property Value
Type Description
ScyllaCollectionCapabilities

A combination of HasCapacity, SupportsPeek, SupportsCopyTo, and SupportsContains.

Capacity

Gets the current capacity of the backing circular buffer - the maximum number of elements that can be stored without a reallocation.

Declaration
public int Capacity { get; }
Property Value
Type Description
int

The length of the internal array. For a fixed-capacity deque this value is constant after construction; for an auto-growing deque it increases when Grow(int) is invoked.

Count

Gets the number of elements currently stored in the deque.

Declaration
public int Count { get; }
Property Value
Type Description
int

A non-negative integer in the range [0, Capacity].

IsEmpty

Gets a value indicating whether the deque contains no elements.

Declaration
public bool IsEmpty { get; }
Property Value
Type Description
bool

true when Count is 0; otherwise false.

IsFixedCapacity

Gets a value indicating whether this deque was created with a fixed capacity that prevents automatic buffer growth.

Declaration
public bool IsFixedCapacity { get; }
Property Value
Type Description
bool

true if push operations return false when the buffer is full rather than reallocating; false if the buffer grows automatically.

IsFull

Gets a value indicating whether the deque is currently at full capacity.

Declaration
public bool IsFull { get; }
Property Value
Type Description
bool

true when Count equals Capacity. For fixed-capacity deques this means the next push will fail. For auto-growing deques this means the next push will trigger a buffer reallocation.

SyncRoot

Gets the synchronization root for this deque. Always null for unsynchronized instances; use AsSynchronized(object) to obtain a wrapper that exposes a non-null SyncRoot.

Declaration
public object SyncRoot { get; }
Property Value
Type Description
object

null

ThreadSafety

Gets the thread-safety level of this deque, which is always Unsynchronized. Use AsSynchronized(object) to obtain a thread-safe wrapper.

Declaration
public ScyllaCollectionThreadSafety ThreadSafety { get; }
Property Value
Type Description
ScyllaCollectionThreadSafety

Unsynchronized

Methods

AsSynchronized(object)

Creates and returns a ScyllaDeque<T>.SynchronizedScyllaDeque wrapper that protects all operations on this deque with a lock, making each individual operation thread-safe.

Declaration
public ScyllaDeque<T>.SynchronizedScyllaDeque AsSynchronized(object syncRoot = null)
Parameters
Type Name Description
object syncRoot

An optional external lock object. If null, the wrapper allocates and owns a new private object as its lock. Pass a shared object to coordinate locking across multiple synchronized collections that must be accessed atomically together.
Returns
Type Description
ScyllaDeque<T>.SynchronizedScyllaDeque

A new ScyllaDeque<T>.SynchronizedScyllaDeque that wraps this deque instance.
Remarks

After calling this method the caller should access the deque exclusively through the returned wrapper. Continued direct access to the original unsynchronized deque from multiple threads will result in undefined behavior.

Clear()

Removes all elements from the deque and resets it to an empty state. For reference-type elements, the backing array slots that held live references are cleared to null so the GC can reclaim the referenced objects.

Declaration
public void Clear()
Remarks

Value-type elements do not require reference clearing, so the slots are left with their stale values (which will be overwritten by subsequent pushes). After this call Count is 0, IsEmpty is true, and _head / _tail are both reset to 0. The backing buffer is not reallocated; Capacity is unchanged.

Contains(T, IEqualityComparer<T>)

Determines whether the deque contains the specified item using a forward linear scan (O(n)).

Declaration
public bool Contains(T item, IEqualityComparer<T> comparer = null)
Parameters
Type Name Description
T item

The item to locate in the deque.
IEqualityComparer<T> comparer

Optional equality comparer used to test element equality. If null, Default is used, which selects the most appropriate comparer for T (e.g. IEquatable<T> when available).
Returns
Type Description
bool

true if an element equal to item exists in the deque; otherwise false. Always returns false immediately when the deque is empty.
Remarks

The scan traverses elements from front to back in circular-buffer order, incrementing the internal index modulo the buffer length at each step. Avoid calling this method in tight loops on large collections; consider a set-based structure for O(1) membership tests.

CopyTo(Span<T>)

Copies elements from the deque into the provided Span<T> in front-to-back order. At most min(Count, destination.Length) elements are written.

Declaration
public int CopyTo(Span<T> destination)
Parameters
Type Name Description
Span<T> destination

A caller-owned span that receives the copied elements. Writing stops when either the deque is exhausted or the span is full, whichever comes first.
Returns
Type Description
int

The number of elements actually copied. Returns 0 if the deque is empty or destination.Length is 0.
Remarks

The copy handles the circular-buffer wrap transparently: if the live region spans the end of the backing array, two separate span copies are performed - the right segment (from _head to the end of the buffer) followed by the left segment (from index 0 up to the number of remaining elements needed).

CopyTo(T[], int)

Copies elements from the deque into the provided array starting at the given index, in front-to-back order. At most min(Count, destination.Length - destinationIndex) elements are written.

Declaration
public int CopyTo(T[] destination, int destinationIndex)
Parameters
Type Name Description
T[] destination

The target array. Must not be null. Writing starts at destinationIndex and proceeds toward higher indices.
int destinationIndex

The zero-based index in destination at which copying begins. Must be in the range [0, destination.Length]. An index equal to destination.Length results in zero elements being copied.
Returns
Type Description
int

The number of elements actually copied. Returns 0 if the deque is empty or there is no available space in destination.
Remarks

Like the CopyTo(Span<T>) overload, this method handles the circular-buffer wrap using two sequential Copy(Array, Array, int) calls when the live region spans the end of the backing array.

Exceptions
Type Condition
ArgumentNullException

Thrown when destination is null.
ArgumentOutOfRangeException

Thrown when destinationIndex is negative or greater than destination.Length.

CreateBuilder()

Creates and returns a new fluent ScyllaDeque<T>.Builder for configuring and constructing a ScyllaDeque<T> instance.

Declaration
public static ScyllaDeque<T>.Builder CreateBuilder()
Returns
Type Description
ScyllaDeque<T>.Builder

A fresh ScyllaDeque<T>.Builder instance with default settings: initial capacity Scylla.Core.Structures.ScyllaDeque<T>.DEFAULT_CAPACITY, auto-growing, and not synchronized.
Remarks

The builder provides a named-parameter-style API that is easier to read than positional constructor arguments when multiple options need to be configured together.

var deque = ScyllaDeque<int>.CreateBuilder()
    .WithCapacity(64)
    .FixedCapacity()
    .Build();

EnsureCapacity(int)

Ensures the backing buffer has capacity for at least minCapacity elements, triggering a reallocation if the current capacity is smaller.

Declaration
public void EnsureCapacity(int minCapacity)
Parameters
Type Name Description
int minCapacity

The minimum number of elements the deque must be able to hold. If the current Capacity is already at least this large, no action is taken.
Remarks

Proactively calling this method before a batch of pushes avoids multiple incremental reallocations and can improve throughput in write-heavy scenarios.

Exceptions
Type Condition
InvalidOperationException

Thrown when called on a fixed-capacity deque (IsFixedCapacity is true), because a fixed-capacity deque is not permitted to grow.

GetEnumerator()

Returns a value-type ScyllaDeque<T>.Enumerator that iterates through the deque in front-to-back order without allocating on the heap.

Declaration
public ScyllaDeque<T>.Enumerator GetEnumerator()
Returns
Type Description
ScyllaDeque<T>.Enumerator

A new ScyllaDeque<T>.Enumerator positioned before the first element. Use in a foreach statement on the concrete ScyllaDeque<T> type to benefit from the allocation-free duck-typed enumerator pattern.
Remarks

Because ScyllaDeque<T>.Enumerator is a struct the C# compiler resolves foreach on the concrete type directly to this method, bypassing the interface and avoiding a heap allocation. Do not modify the deque while enumerating; the enumerator snapshots Count at construction and will silently yield stale or incorrect elements if the deque changes.

TryAdd(T)

Attempts to add an item to the deque using the FIFO (queue) convention by delegating to TryPushBack(T). Implements TryAdd(T) for polymorphic usage through the abstract interface.

Declaration
public bool TryAdd(T item)
Parameters
Type Name Description
T item

The item to push onto the back of the deque.
Returns
Type Description
bool

true if the item was added; false if the deque is fixed-capacity and full.

TryPeek(out T)

Attempts to inspect the front element without removing it by delegating to TryPeekFront(out T). Implements TryPeek(out T) for polymorphic usage through the abstract interface.

Declaration
public bool TryPeek(out T item)
Parameters
Type Name Description
T item

When this method returns true, contains the current front element; otherwise default.
Returns
Type Description
bool

true if an element was available; false if the deque is empty.

TryPeekBack(out T)

Attempts to inspect the back element without removing it, in O(1) time.

Declaration
public bool TryPeekBack(out T item)
Parameters
Type Name Description
T item

When this method returns true, contains the back element. When this method returns false, contains default(T).
Returns
Type Description
bool

true if an element was available; false if the deque is empty.
Remarks

Because _tail points one slot past the back element, the back element is read from (_tail - 1) modulo the buffer length.

TryPeekFront(out T)

Attempts to inspect the front element without removing it, in O(1) time.

Declaration
public bool TryPeekFront(out T item)
Parameters
Type Name Description
T item

When this method returns true, contains the front element. When this method returns false, contains default(T).
Returns
Type Description
bool

true if an element was available; false if the deque is empty.

TryPopBack(out T)

Attempts to remove and return the back element of the deque in O(1) time.

Declaration
public bool TryPopBack(out T item)
Parameters
Type Name Description
T item

When this method returns true, contains the removed back element. When this method returns false, contains default(T).
Returns
Type Description
bool

true if an element was removed; false if the deque is empty.
Remarks

For reference types the vacated buffer slot is cleared to null immediately after removal. Before removal, _tail is decremented modulo the buffer length so that it points to the back element itself (recall that _tail normally points one slot past the back element).

TryPopFront(out T)

Attempts to remove and return the front element of the deque in O(1) time.

Declaration
public bool TryPopFront(out T item)
Parameters
Type Name Description
T item

When this method returns true, contains the removed front element. When this method returns false, contains default(T).
Returns
Type Description
bool

true if an element was removed; false if the deque is empty.
Remarks

For reference types the vacated buffer slot is cleared to null immediately after removal so the GC can collect the referenced object if no other live references remain. After removal, _head is incremented modulo the buffer length.

TryPushBack(T)

Attempts to append an item at the back of the deque in O(1) amortized time.

Declaration
public bool TryPushBack(T item)
Parameters
Type Name Description
T item

The item to place at the back of the deque.
Returns
Type Description
bool

true if the item was added successfully. false if IsFixedCapacity is true and the deque is already full. For auto-growing deques this method always returns true unless an out-of-memory exception is thrown during buffer growth.
Remarks

Internally, the item is written to the slot at _tail, then _tail is incremented modulo the buffer length to point to the next free slot.

TryPushFront(T)

Attempts to insert an item at the front of the deque in O(1) amortized time.

Declaration
public bool TryPushFront(T item)
Parameters
Type Name Description
T item

The item to place at the front of the deque.
Returns
Type Description
bool

true if the item was added successfully. false if IsFixedCapacity is true and the deque is already full. For auto-growing deques this method always returns true unless an out-of-memory exception is thrown during buffer growth.
Remarks

Internally, _head is decremented modulo the buffer length before writing the item, so the item occupies the slot immediately before the previous front element.

TryRemove(out T)

Attempts to remove and return the front element of the deque using the FIFO (queue) convention by delegating to TryPopFront(out T). Implements TryRemove(out T) for polymorphic usage through the abstract interface.

Declaration
public bool TryRemove(out T item)
Parameters
Type Name Description
T item

When this method returns true, contains the removed front element; otherwise default.
Returns
Type Description
bool

true if an element was removed; false if the deque is empty.

Implements

Extension Methods

See Also