deque.h File Reference

Double ended queue generators specialized to any given type. More...

#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

Go to the source code of this file.

Classes
struct	Example
	A data structure generated by IMPLEMENT_DEQUE_STRUCT() to store the state of a deque. More...

Macros
#define	IMPLEMENT_DEQUE_STRUCT(struct_name, type)
	Generates a structure for use with Double Ended Queues. More...
#define	PROTOTYPE_DEQUE(struct_name, type)
	Generates prototypes for functions that manipulate Double Ended Queue structures. More...
#define	IMPLEMENT_DEQUE(struct_name, type)
	Generates a malloc based set of functions for use with a structure generated by IMPLEMENT_DEQUE_STRUCT() More...

Typedefs
typedef char	Type
	An example type used for example purposes only.
typedef struct Example	Example
	This way you do not have to type "struct Example" each time you wish to refer to an Example structure.

Functions
Example	new_Example (size_t)
	Create a new, fully initialized deque structure. More...
Example	new_destructable_Example (size_t, void(*)(Type))
	Create a new, fully initialized deque structure with a destructor that is applied to every element when the destroy_Example() function is called. More...
void	destroy_Example (Example *)
	Destroy the deque structure freeing memory if necessary. More...
void	empty_Example (Example *)
	Quickly empties the deque structure calling a destructor on each element in the deque if a destructor was specified. More...
bool	is_empty_Example (Example *)
	Checks if the deque is empty. More...
size_t	length_Example (Example *)
	Query the number of elements in the deque. More...
Type *	as_array_Example (Example *, size_t *)
	Extract an array based off the deque. More...
void	apply_Example (Example *, void(*)(Type))
	Calls the function func on every element in the deque. More...
void	push_front_Example (Example *, Type)
	Insert an element to the front of the deque. More...
void	push_back_Example (Example *, Type)
	Insert an element to the back of the deque. More...
Type	pop_front_Example (Example *)
	Remove an element from the front of the deque. More...
Type	pop_back_Example (Example *)
	Remove an element from the back of the deque. More...
Type	peek_front_Example (Example *)
	Get a copy of the element at the front of the deque. More...
Type	peek_back_Example (Example *)
	Remove an element from the back of the deque. More...
void	update_front_Example (Example *, Type)
	Change the element at the front of the deque to be a copy of element If a destructor is presesnt, then call the destructor on the value of the element that is being replaced. More...
void	update_back_Example (Example *, Type)
	Change the element at the back of the deque to be a copy of element. If a destructor is presesnt, then call the destructor on the value of the element that is being replaced. More...
void	update_and_destroy_front_Example (Example *, Type)
	Change the element at the front of the deque to be a copy of element. If a destructor is presesnt, then call the destructor on the element that is being replaced. More...
void	update_and_destroy_back_Example (Example *, Type)
	Change the element at the back of the deque to be a copy of element. If a destructor is presesnt, then call the destructor on the element that is being replaced. More...

Detailed Description

Double ended queue generators specialized to any given type.

Macro Definition Documentation

#define IMPLEMENT_DEQUE	(		struct_name,
			type
	)

Generates a malloc based set of functions for use with a structure generated by IMPLEMENT_DEQUE_STRUCT()

Parameters

struct_name	The name of the structure
type	The name of the type of elements stored in the struct_name structure

See also

IMPLEMENT_DEQUE_STRUCT(), PROTOTYPE_DEQUE()

#define IMPLEMENT_DEQUE_STRUCT	(		struct_name,
			type
	)

Value:

typedef struct struct_name {                                          \
    type* data;                                                         \
    size_t cap;                                                         \
    size_t front;                                                       \
    size_t back;                                                        \
                                                                        \
    void (*destructor)(type);                                           \
  } struct_name;

Generates a structure for use with Double Ended Queues.

Follow this call with either PROTOTYPE_DEQUE() (if in a header file) or IMPLEMENT_DEQUE() to generate the functions that correspond to this structure. The structure fields should not be manually changed at any time. Instead use one of the generated functions from the aforementioned macros.

Parameters

struct_name	The name of the structure
type	The name of the type of elements stored in the struct_name structure

See also

PROTOTYPE_DEQUE, IMPLEMENT_DEQUE

#define PROTOTYPE_DEQUE	(		struct_name,
			type
	)

Value:

struct_name new_##struct_name(size_t);                                \
  struct_name new_destructable_##struct_name(size_t, void (*)(type));   \
  void destroy_##struct_name(struct_name*);                             \
  void empty_##struct_name(struct_name*);                               \
  bool is_empty_##struct_name(struct_name*);                            \
  size_t length_##struct_name(struct_name*);                            \
  type* as_array_##struct_name(struct_name*, size_t*);                  \
  void apply_##struct_name(struct_name*, void (*)(type));               \
  void push_front_##struct_name(struct_name*, type);                    \
  void push_back_##struct_name(struct_name*, type);                     \
  type pop_front_##struct_name(struct_name*);                           \
  type pop_back_##struct_name(struct_name*);                            \
  type peek_front_##struct_name(struct_name*);                          \
  type peek_back_##struct_name(struct_name*);                           \
  void update_front_##struct_name(struct_name*, type);                  \
  void update_back_##struct_name(struct_name*, type);                   \
  void update_and_destroy_front_##struct_name(struct_name*, type);      \
  void update_and_destroy_back_##struct_name(struct_name*, type);

Generates prototypes for functions that manipulate Double Ended Queue structures.

This is intended for use in a header file or anywhere you need a forward declaration of these functions. This does not actually implement these functions.

Parameters

struct_name	The name of the structure
type	The name of the type of elements stored in the struct_name structure

See also

IMPLEMENT_DEQUE_STRUCT(), IMPLEMENT_DEQUE()

Function Documentation

void apply_Example	(	Example *	deq,
		void(*)(Type)	func
	)

Calls the function func on every element in the deque.

Note

We will have a lab over function pointers later in the semester. If this doesn't make sense now then skip it or come to your TA for assistance if you really want to use it.

Parameters

deq	A pointer to the deque to apply the function func to
func	A pointer to a function that takes an element of type

See also

Example, Type

Type * as_array_Example	(	Example *	deq,
		size_t *	len
	)

Extract an array based off the deque.

Note

Calling this function on a deque will invalidate the deque. This means no further deque functions can be called on the deq until it is reinitialized with new_Example(). If this function was created with the IMPLEMENT_DEQUE() macro, then the destructor is never called and you will be responsible for freeing the memory of the array.

Parameters

	deq	in A pointer to the deque to extract an array from
[out]	len	A pointer to an size_t value. This value will be set to the current length of the deque returned from the length_Example() function. If knowing the length of the array is unnecessary then NULL may be passed as this parameter.

Returns

An array containing the data from the deque

See also

Example, Type

void destroy_Example

(

Example *

deq

)

Destroy the deque structure freeing memory if necessary.

Parameters

deq	A pointer to the deque to destory

See also

Example

void empty_Example

(

Example *

deq

)

Quickly empties the deque structure calling a destructor on each element in the deque if a destructor was specified.

Parameters

deq	A pointer to the deque to empty

See also

Example

bool is_empty_Example

(

Example *

deq

)

Checks if the deque is empty.

Parameters

deq	A pointer to the deque to check if empty

Returns

Returns true if empty and false if not empty

See also

Example

size_t length_Example

(

Example *

deq

)

Query the number of elements in the deque.

Parameters

deq	A pointer to the deque to calculate the length of

Returns

The number of elements in the deque

See also

Example

Example new_destructable_Example	(	size_t	init_cap,
		void(*)(Type)	destructor
	)

Create a new, fully initialized deque structure with a destructor that is applied to every element when the destroy_Example() function is called.

Specifying the destructor is useful to not have to manually iterate over the deque destroying any malloc'd memory in each element.

Parameters

init_cap	Initial capacity of the deque
destructor	A function that is run on each element in the deque when destroy_Example() is called

Returns

A copy of the fully initialized struct

See also

Example

Example new_Example

(

size_t

init_cap

)

Create a new, fully initialized deque structure.

Parameters

init_cap

Initial capacity of the deque

Returns

A copy of the fully initialized struct

See also

Example

Type peek_back_Example

(

Example *

deq

)

Remove an element from the back of the deque.

Parameters

deq	A pointer to the deque to view the last element from

Returns

A copy of the element removed from the back of the queue

See also

Example, Type

Type peek_front_Example

(

Example *

deq

)

Get a copy of the element at the front of the deque.

Parameters

deq	A pointer to the deque to view the first element from

Returns

A copy of the element at the front of the deque

See also

Example, Type

Type pop_back_Example

(

Example *

deq

)

Remove an element from the back of the deque.

Parameters

deq	A pointer to the deque to remove an element from

Returns

A copy of the element removed from the back of the deque

See also

Example, Type

Type pop_front_Example

(

Example *

deq

)

Remove an element from the front of the deque.

Parameters

deq	A pointer to the deque to remove an element from

Returns

A copy of the element removed from the front of the deque

See also

Example, Type

void push_back_Example	(	Example *	deq,
		Type	element
	)

Insert an element to the back of the deque.

Parameters

deq	A pointer to the deque to insert the element
element	The element to copy into the deque

See also

Example, Type

void push_front_Example	(	Example *	deq,
		Type	element
	)

Insert an element to the front of the deque.

Parameters

deq	A pointer to the deque to insert the element
element	The element to copy into the deque

See also

Example, Type

void update_and_destroy_back_Example	(	Example *	deq,
		Type	element
	)

Change the element at the back of the deque to be a copy of element. If a destructor is presesnt, then call the destructor on the element that is being replaced.

Parameters

deq	A pointer to the deque to update
element	The element to copy into the current last element in the deque

See also

Example, Type

void update_and_destroy_front_Example	(	Example *	deq,
		Type	element
	)

Change the element at the front of the deque to be a copy of element. If a destructor is presesnt, then call the destructor on the element that is being replaced.

Parameters

deq	A pointer to the deque to update
element	The element to update the first element to

See also

Example, Type

void update_back_Example	(	Example *	deq,
		Type	element
	)

Change the element at the back of the deque to be a copy of element. If a destructor is presesnt, then call the destructor on the value of the element that is being replaced.

Change the element at the back of the deque to be a copy of element. This will NOT call the destructor on the old element. This is useful for simply replacing a few fields.

Parameters

deq	A pointer to the deque to update
element	The element to copy into the current last element in the deque

See also

Example, Type

void update_front_Example	(	Example *	deq,
		Type	element
	)

Change the element at the front of the deque to be a copy of element If a destructor is presesnt, then call the destructor on the value of the element that is being replaced.

Change the element at the front of the deque to be a copy of element. This will NOT call the destructor on the old element. This is useful for simply replacing a few fields.

Parameters

deq	A pointer to the deque to update
element	The element to update the first element to

See also

Example, Type