Double-ended queue

Typedefs
typedef struct deque_t	deque_t
	Opaque type for a double-ended queue. More...

Functions
deque_t *	dequeCreate (int sizeHint)
	Create a new deque with space reserved for at least sizeHint elements. More...
void	dequeDestroy (deque_t *d)
	Destroy a deque created with dequeCreate(). More...
int	dequePushBack (deque_t *d, void *p)
	Add an element to the "back" of a deque. More...
int	dequePopBack (deque_t *d)
	Remove the last element of a queue. More...
int	dequePushFront (deque_t *d, void *p)
	Add an element on the "back" of a deque. More...
int	dequePopFront (deque_t *d)
	Remove the last element of a queue. More...
int	dequeLength (const deque_t *d)
	Return the number of elements inside a deque. More...
void *	dequeGet (const deque_t *d, int i)
	Return the i'th element on a queue. More...
void *	dequeGetFront (const deque_t *d)
	Return the first element on a deque. More...
void *	dequeGetBack (const deque_t *d)
	Return the last element on a deque. More...
void *	dequeSet (deque_t *d, int i, void *p)
	Change the value of the i'th element on a deque. More...
int	dequeInsert (deque_t *d, int i, void *p)
	Insert an element at any position inside the deque. More...
int	dequeRemove (deque_t *d, int i)
	Remove an element at any position inside the deque. More...

Detailed Description

Introduction

This module implements a double-ended queue (deque) of opaque elements that provides amortized O(1) push and pop operations on both ends (but not in the middle) and random item access (get and set operations).

Note that the implementation treats elements as opaque pointers, their memory is not automatically released when removed from the queue, the user must do that.

Typedef Documentation

typedef struct deque_t deque_t

Opaque type for a double-ended queue.

All operations on deques receive a parameter of this type.

Function Documentation

deque_t* dequeCreate

(

int

sizeHint

)

Create a new deque with space reserved for at least sizeHint elements.

Creating a deque with sizeHint close to the maximum number of elements that will ever be inserted gives the best performance characteristics, since no re-allocation will ever be necessary.

Parameters

sizeHint

A hint on the maximum size of elements that will ever be inserted on the deque. The implementation may use a value larger than this on practice.

Returns

A new deque_t instance, or NULL on error.

void dequeDestroy

(

deque_t *

d

)

Destroy a deque created with dequeCreate().

Parameters

d	deque to be destroyed. NULL is accepted, and ignored.

void* dequeGet	(	const deque_t *	d,
		int	i
	)

Return the i'th element on a queue.

Note

An implementation may check boundaries and cause an assertion error on out of bounds access in debug builds. This check may be omitted in non-debug builds. In this case accessing an element out of bounds is undefined behavior.

Calling with an invalid d parameter may cause an assertion error on debug builds or undefined behavior on non-debug builds.

Precondition

(d != NULL) && (0 <= i < dequeLength(d))

Parameters

d	A valid deque_t instance.
i	Index of the element to be returned.

Returns

The element at the i'th position on the deque d.

void* dequeGetBack

(

const deque_t *

d

)

Return the last element on a deque.

This call is equivalent to dequeGet(d, dequeLength(d) - 1). The same bound checking notes that apply to dequeGet() are valid here.

Note

Calling with an invalid d parameter may cause an assertion error on debug builds or undefined behavior on non-debug builds.

Parameters

d	A valid deque_t instance.

Returns

The element at the last position on the deque d.

void* dequeGetFront

(

const deque_t *

d

)

Return the first element on a deque.

This call is equivalent to dequeGet(d, 0). The same bound checking notes that apply to dequeGet() are valid here.

Note

Calling with an invalid d parameter may cause an assertion error on debug builds or undefined behavior on non-debug builds.

Parameters

d	A valid deque_t instance.

Returns

The element at the first position on the deque d.

int dequeInsert	(	deque_t *	d,
		int	i,
		void *	p
	)

Insert an element at any position inside the deque.

Even without any reallocation this is a O(n) operation, as other elements may need to be moved. Operations on either ends of the deque will behave as if dequePushFront() and dequePushBack() were called.

Note

If there is not enough space on the deque_t for a new element it will be resized, which is also an O(n) operation.

Parameters

d	A valid deque_t instance.
i	Index where to insert element. If this operation succeeds, dequeGet(d, i) == p. i == dequeLength(d) is a valid index.
p	Element to be added.

Returns

BASE_ERR_OK if the element was inserted.

BASE_ERR_INVALID_HANDLE if d is an invalid queue_t.

BASE_ERR_RESOURCE_PB if could not expand deque to hold the new element.

BASE_ERR_DATA_NOT_FOUND if the index is out of range.

int dequeLength

(

const deque_t *

d

)

Return the number of elements inside a deque.

Note that this value is not related to the actual memory occupation of a deque. For example, a large sizeHint parameter to dequeCreate() will reserve much memory to the deque, but dequeLength() will return zero.

Parameters

d	A valid deque_t instance.

Returns

The number of elements inside the deque >= 0 .

BASE_ERR_INVALID_HANDLE if d is an invalid queue_t.

int dequePopBack

(

deque_t *

d

)

Remove the last element of a queue.

Parameters

d	A valid deque_t instance.

Returns

BASE_ERR_OK if the element was removed.

BASE_ERR_INVALID_HANDLE if d is an invalid queue_t.

BASE_ERR_DATA_NOT_FOUND if the deque is empty.

int dequePopFront

(

deque_t *

d

)

Remove the last element of a queue.

Parameters

d	A valid deque_t instance.

Returns

BASE_ERR_OK if the element was removed.

BASE_ERR_INVALID_HANDLE if d is an invalid queue_t.

BASE_ERR_DATA_NOT_FOUND if the deque is empty.

int dequePushBack	(	deque_t *	d,
		void *	p
	)

Add an element to the "back" of a deque.

This is equivalent as inserting an element at position dequeLength(d).

Note

If there is not enough space on the deque_t for a new element it will be resized, which is an O(n) operation. Otherwise, this is an O(1) operation.

Parameters

d	A valid deque_t instance.
p	Element to be added.

Returns

BASE_ERR_OK if the element was inserted.

BASE_ERR_INVALID_HANDLE if d is an invalid queue_t.

BASE_ERR_RESOURCE_PB if could not expand deque to hold the new element.

int dequePushFront	(	deque_t *	d,
		void *	p
	)

Add an element on the "back" of a deque.

This is equivalent as inserting an element at position 0.

Note

If there is not enough space on the deque_t for a new element it will be resized, which is an O(n) operation. Otherwise, this is an O(1) operation.

Parameters

d	A valid deque_t instance.
p	Element to be added.

Returns

BASE_ERR_OK if the element was inserted.

BASE_ERR_INVALID_HANDLE if d is an invalid queue_t.

BASE_ERR_RESOURCE_PB if could not expand deque to hold the new element.

int dequeRemove	(	deque_t *	d,
		int	i
	)

Remove an element at any position inside the deque.

Note

A check is made if the element is the first or last on the deque, and dequePopFront() or dequePopBack() are called on those cases, operations on any other index are O(n).

Parameters

d	A valid deque_t instance.
i	Index of element to be removed.

Returns

BASE_ERR_OK if the element was removed.

BASE_ERR_INVALID_HANDLE if d is an invalid queue_t.

BASE_ERR_DATA_NOT_FOUND if the index is out of range.

void* dequeSet	(	deque_t *	d,
		int	i,
		void *	p
	)

Change the value of the i'th element on a deque.

Note

An implementation may check boundaries and cause an assertion error on access out of bounds in debug builds. This check may be omitted in non-debug builds. In this case accessing an element out of bounds is undefined behavior.

Calling with an invalid d parameter may cause an assertion error on debug builds or undefined behavior on non-debug builds.

Parameters

d	A valid deque_t instance.
i	Index of element to set.
p	Value to be written.

Returns

The value of the parameter p.