vl_deque.h File Reference

#include "vl_linear_pool.h"

Include dependency graph for vl_deque.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	vl_deque
	Double-ended queue. More...

Functions
void	vlDequeInit (vl_deque *deq, vl_memsize_t elementSize)
	Initializes the specified instance of vl_deque.
void	vlDequeFree (vl_deque *deq)
	Frees the specified instance of vl_deque.
vl_deque *	vlDequeNew (vl_memsize_t elementSize)
	Allocates, initializes, and returns an instance of vl_deque.
void	vlDequeDelete (vl_deque *deq)
	De-initializes and deletes the specified instance of vl_deque.
void	vlDequeClear (vl_deque *deq)
	Clears the specified deque.
void	vlDequeReserve (vl_deque *deque, vl_memsize_t n)
	Reserves space for n-many elements in the underlying buffer of the specified deque.
vl_deque *	vlDequeClone (const vl_deque *src, vl_deque *dest)
	Clones the specified deque to another.
vl_memsize_t	vlDequeSize (vl_deque *deq)
	Returns the total number of elements.
void	vlDequePushFront (vl_deque *deq, const void *val)
	Adds and copies an element to the front of the deque.
int	vlDequePopFront (vl_deque *deq, void *val)
	Copies and removes an element from the front of the deque.
void	vlDequePushBack (vl_deque *deq, const void *val)
	Adds and copies an en element to the end of the deque.
int	vlDequePopBack (vl_deque *deq, void *val)
	Copies and removes an element from the end of the deque.

---

Data Structure Documentation

vl_deque

struct vl_deque

Double-ended queue.

The Deque data structure is a doubly-linked list. It is implemented on top of a pool allocator, and thus requires all elements in the queue to be the same size.

Items may be added or removed from either end, but iteration is inherently disallowed. Just like the vl_queue data structure, direct sampling is also disallowed. Thus, all IO requires a copy. If you're using "weighty" (or, large in byte size) elements and are worried about the efficiency of copying, storing pointers, iterators, or offsets in the queue is a perfectly valid approach.

See also

vl_queue

Collaboration diagram for vl_deque:

Data Fields
vl_memsize_t	elementSize
vl_linearpool_idx	head
vl_linearpool	nodes
vl_linearpool_idx	tail

Function Documentation

vlDequeClear()

void vlDequeClear

(

vl_deque *

deq

)

Clears the specified deque.

This does not actually touch any underlying element data, but does reset some bookkeeping values.

Parameters

deq

pointer

Complexity O(1) constant.

Here is the call graph for this function:

vlDequeClone()

vl_deque * vlDequeClone	(	const vl_deque *	src,
		vl_deque *	dest )

Clones the specified deque to another.

Clones the entirety of the src deque to the dest deque.

The 'src' deque pointer must be non-null and initialized. The 'dest' deque pointer may be null, but if it is not null it must be initialized.

If the 'dest' deque pointer is null, a new list is created via vlListNew. Otherwise, its element size is set to the source's and all of its existing data is replaced.

Parameters

src	pointer
dest	pointer

Returns

pointer to deque that was copied to or created.

Here is the call graph for this function:

vlDequeDelete()

void vlDequeDelete

(

vl_deque *

deq

)

De-initializes and deletes the specified instance of vl_deque.

The deque should have been initialized via vlDequeNew.

See also

vlDequeNew

Parameters

deq

pointer

Complexity O(1) constant.

Here is the call graph for this function:

vlDequeFree()

void vlDequeFree

(

vl_deque *

deq

)

Frees the specified instance of vl_deque.

The deque should have been initialized via vlDequeInit.

See also

vlDequeInit

Parameters

deq

pointer

Here is the call graph for this function:

Here is the caller graph for this function:

vlDequeInit()

void vlDequeInit	(	vl_deque *	deq,
		vl_memsize_t	elementSize )

Initializes the specified instance of vl_deque.

The deque should later be freed via vlDequeFree.

See also

vlDequeFree

Parameters

deq	pointer
elementSize	size of each element, in bytes.

Complexity O(1) constant.

Here is the call graph for this function:

Here is the caller graph for this function:

vlDequeNew()

vl_deque * vlDequeNew

(

vl_memsize_t

elementSize

)

Allocates, initializes, and returns an instance of vl_deque.

The deque should later be freed via vlDequeFree.

See also

vlDequeFree

Parameters

deq	pointer
elementSize	size of each element, in bytes.

Complexity O(1) constant.

Returns

deque pointer

Here is the call graph for this function:

Here is the caller graph for this function:

vlDequePopBack()

int vlDequePopBack	(	vl_deque *	deq,
		void *	val )

Copies and removes an element from the end of the deque.

If specified pointer val is NULL, the element is not copied, but the element is still removed.

Parameters

deq	pointer
val	pointer where the element will be copied to.

Returns

1 if success, 0 if failed.

Here is the call graph for this function:

vlDequePopFront()

int vlDequePopFront	(	vl_deque *	deq,
		void *	val )

Copies and removes an element from the front of the deque.

If specified pointer val is NULL, the element is not copied, but the element is still removed.

Parameters

deq	pointer
val	pointer where the element will be copied to.

Complexity O(1) constant.

Returns

1 if success, 0 if failed

Here is the call graph for this function:

vlDequePushBack()

void vlDequePushBack	(	vl_deque *	deq,
		const void *	val )

Adds and copies an en element to the end of the deque.

Parameters

deq	pointer
val	element data pointer

Complexity O(1) constant.

Here is the call graph for this function:

vlDequePushFront()

void vlDequePushFront	(	vl_deque *	deq,
		const void *	val )

Adds and copies an element to the front of the deque.

Parameters

deq	pointer
val	element data pointer

Complexity O(1) constant.

Here is the call graph for this function:

vlDequeReserve()

void vlDequeReserve	(	vl_deque *	deque,
		vl_memsize_t	n )

Reserves space for n-many elements in the underlying buffer of the specified deque.

This is done by doubling the size until the requested growth is met or exceeded. This function will always result in the reallocation of the underlying memory.

Parameters

deque	pointer
n	total number of elements to reserve space for.

Here is the call graph for this function:

vlDequeSize()

vl_memsize_t vlDequeSize

(

vl_deque *

deq

)

Returns the total number of elements.

Parameters

deq

pointer

Complexity O(1) constant.

Returns

total number of elements in the deque.