Double Ended Queue

Implementation if a double ended queue datastructure for generic pointers. More...

Defines
#define	new_waitq()   new_pdeq()
	Creates a new pointer wait queue (fifo).
#define	del_waitq(wq)   del_pdeq(wq)
	Delete a wait queue (fifo)
#define	waitq_get(wq)   pdeq_getl(wq)
	Retrieve a pointer from the wait queue (fifo).
#define	waitq_put(wq, x)   pdeq_putr((wq), (x))
	Add a pointer to the wait queue (fifo).
#define	waitq_empty(wq)   pdeq_empty(wq)
	Checks if a wait queue is empty.
#define	new_stack()   new_pdeq()
	Creates a new pointer stack (lifo).
#define	stack_pop(st)   pdeq_getr(st)
	Pop a pointer from the stack (lifo).
#define	stack_push(st, x)   pdeq_putr((st), (x))
	Push a pointer to the stack (lifo).
#define	stack_empty(st)   pdeq_empty(wq)
	Checks if a stack is empty.
Typedefs
typedef int(*	cmp_fun )(const void *elem, const void *key)
	The type of the pointer compare function.
typedef struct pdeq	pdeq
	The pointer double ended queue (list).
typedef pdeq	waitq
	The pdeq is often used as a wait queue.
typedef pdeq	stack
	The pdeq can be used as a stack.
Functions
pdeq *	new_pdeq (void)
	Creates a new double ended pointer list.
pdeq *	new_pdeq1 (const void *x)
	Creates a new double ended pointer list and puts an initial pointer element in.
void	del_pdeq (pdeq *dq)
	Delete a double ended pointer list.
size_t	pdeq_len (pdeq *dq)
	Returns the length of a double ended pointer list.
int	pdeq_empty (pdeq *dq)
	Checks if a list is empty.
int	pdeq_contains (pdeq *dq, const void *x)
	Returns non-zero if a double ended pointer list contains a pointer x.
void *	pdeq_search (pdeq *qp, cmp_fun cmp, const void *key)
	Search a key in a double ended pointer list, the search is controlled by a compare function.
void **	pdeq_copyl (pdeq *qp, const void **dst)
	Convert the double ended pointer list into a linear array beginning from left, the first element in the linear array will be the left one.
void **	pdeq_copyr (pdeq *qp, const void **dst)
	Convert the double ended pointer list into a linear array beginning from right, the first element in the linear array will be the right one.
pdeq *	pdeq_putl (pdeq *dq, const void *x)
	Add a pointer to the left side of a double ended pointer list.
pdeq *	pdeq_putr (pdeq *dq, const void *x)
	Add a pointer to the right side of a double ended pointer list.
void *	pdeq_getl (pdeq *dq)
	Retrieve (and remove) a pointer from the left site of a double ended pointer list.
void *	pdeq_getr (pdeq *dq)
	Retrieve (and remove) a pointer from the right site of a double ended pointer list.

---

Detailed Description

Implementation if a double ended queue datastructure for generic pointers.

---

Define Documentation

#define del_waitq

(

wq

)

del_pdeq(wq)

Delete a wait queue (fifo)

Parameters:

wq	The wait queue.

Definition at line 199 of file pdeq.h.

#define new_stack

(

)

new_pdeq()

Creates a new pointer stack (lifo).

Returns:

A new stack.

Definition at line 242 of file pdeq.h.

#define new_waitq

(

)

new_pdeq()

Creates a new pointer wait queue (fifo).

Returns:

A new queue.

Definition at line 192 of file pdeq.h.

#define stack_empty

(

st

)

pdeq_empty(wq)

Checks if a stack is empty.

Parameters:

st	The stack.

Returns:

non-zero if the stack is empty.

Definition at line 272 of file pdeq.h.

#define stack_pop

(

st

)

pdeq_getr(st)

Pop a pointer from the stack (lifo).

Parameters:

st	The stack.

Returns:

The pointer element.

Remarks:

This function will fail if the stack is empty.

Definition at line 253 of file pdeq.h.

#define stack_push	(		st,
			x
	)		pdeq_putr((st), (x))

Push a pointer to the stack (lifo).

Parameters:

st	The stack.
x	The pointer element to be added

Returns:

The stack.

Definition at line 263 of file pdeq.h.

#define waitq_empty

(

wq

)

pdeq_empty(wq)

Checks if a wait queue is empty.

Parameters:

wq	The wait queue.

Returns:

non-zero if the queue is empty.

Definition at line 229 of file pdeq.h.

#define waitq_get

(

wq

)

pdeq_getl(wq)

Retrieve a pointer from the wait queue (fifo).

Parameters:

wq	The wait queue.

Returns:

The pointer element.

Remarks:

This function will fail if the queue is empty.

Definition at line 210 of file pdeq.h.

#define waitq_put	(		wq,
			x
	)		pdeq_putr((wq), (x))

Add a pointer to the wait queue (fifo).

Parameters:

wq	The wait queue
x	The pointer element to be added

Returns:

The wait queue.

Definition at line 220 of file pdeq.h.

---

Typedef Documentation

typedef int(* cmp_fun)(const void *elem, const void *key)

The type of the pointer compare function.

Parameters:

elem	The list element.
key	The user supplied key.

Returns:

0 if the element matches the key, non-zero else.

Definition at line 47 of file pdeq.h.

typedef struct pdeq pdeq

The pointer double ended queue (list).

Definition at line 52 of file pdeq.h.

typedef pdeq stack

The pdeq can be used as a stack.

A helper type to support this.

Definition at line 235 of file pdeq.h.

typedef pdeq waitq

The pdeq is often used as a wait queue.

A helper type to support this.

Definition at line 185 of file pdeq.h.

---

Function Documentation

void del_pdeq

(

pdeq *

dq

)

Delete a double ended pointer list.

Parameters:

dq	The list to be deleted.

pdeq* new_pdeq

(

void

)

Creates a new double ended pointer list.

Returns:

A new list.

pdeq* new_pdeq1

(

const void *

x

)

Creates a new double ended pointer list and puts an initial pointer element in.

Parameters:

x	The pointer element to put in.

Returns:

The new list.

int pdeq_contains	(	pdeq *	dq,
		const void *	x
	)

Returns non-zero if a double ended pointer list contains a pointer x.

Parameters:

dq	The list.
x	The pointer to be searched for.

void** pdeq_copyl	(	pdeq *	qp,
		const void **	dst
	)

Convert the double ended pointer list into a linear array beginning from left, the first element in the linear array will be the left one.

Parameters:

qp	The list.
dst	A pointer to a pointer array with must be at least pdeq_len(dq) * sizeof(void *)

Returns:

dst

void** pdeq_copyr	(	pdeq *	qp,
		const void **	dst
	)

Convert the double ended pointer list into a linear array beginning from right, the first element in the linear array will be the right one.

Parameters:

qp	The list.
dst	A pointer to a pointer array with must be at least pdeq_len(dq) * sizeof(void *)

Returns:

dst

int pdeq_empty

(

pdeq *

dq

)

Checks if a list is empty.

Parameters:

dq

The list.

Returns:

non-zero if the list is empty.

void* pdeq_getl

(

pdeq *

dq

)

Retrieve (and remove) a pointer from the left site of a double ended pointer list.

Parameters:

dq

The list

Returns:

The pointer element.

Remarks:

This function will fail if the list is empty.

void* pdeq_getr

(

pdeq *

dq

)

Retrieve (and remove) a pointer from the right site of a double ended pointer list.

Parameters:

dq

The list

Returns:

The pointer element.

Remarks:

This function will fail if the list is empty.

size_t pdeq_len

(

pdeq *

dq

)

Returns the length of a double ended pointer list.

Parameters:

dq

The list.

pdeq* pdeq_putl	(	pdeq *	dq,
		const void *	x
	)

Add a pointer to the left side of a double ended pointer list.

Parameters:

dq	The list to add a pointer to.
x	The pointer element to be added

Returns:

The list.

pdeq* pdeq_putr	(	pdeq *	dq,
		const void *	x
	)

Add a pointer to the right side of a double ended pointer list.

Parameters:

dq	The list to add a pointer to.
x	The pointer element to be added

Returns:

The list.

void* pdeq_search	(	pdeq *	qp,
		cmp_fun	cmp,
		const void *	key
	)

Search a key in a double ended pointer list, the search is controlled by a compare function.

An element is found, if the compare function returns 0. The search is started from the left site of the list.

Parameters:

qp	The list.
cmp	The compare function.
key	The search key.

Returns:

The address of the element entry if the key was found, NULL else.