src/stack.h File Reference

An array-backed last-in first-out queue (aka pushdown stack). More...

#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <assert.h>
#include "cdsa_types.h"

Include dependency graph for stack.h:

Go to the source code of this file.

Defines

#define DEFAULT_STACK_CAPACITY

The default stack capacity that is used if 0 is specified as the capacity value to stack_new.

Typedefs

typedef struct Stack Stack

A LIFO queue.

Functions

cdsa_status_t stack_new (Stack **new_stack, size_t elem_size, size_t capacity, cdsa_destroy_func1_t destroy)

Create a new stack, setting *new_stack to the new stack on success, with elem_size determining whether to store pointers or copies in the stack.

cdsa_status_t stack_destroy (Stack **stack)

Destroy *stack that was created using stack_new and set the pointer to NULL.

cdsa_status_t stack_push (Stack *const stack, void *const data)

Push an item onto the stack.

cdsa_status_t stack_pop (Stack *const stack, void *ptr)

Answer the last pushed item from the stack, if any, recording result in *ptr.

cdsa_status_t stack_peek (Stack *const stack, void *ptr)

Peek at the last pushed item without removing it, setting ptr to the value if the stack is not empty.

cdsa_status_t stack_is_empty (const Stack *const stack, bool *is_empty)

Answer whether the stack is empty, recording result in *is_empty.

cdsa_status_t stack_size (const Stack *const stack, size_t *size)

Answer the size of the stack, recording result in *size.

cdsa_status_t stack_capacity (const Stack *const stack, size_t *capacity)

Answer the current capacity of the stack, recording result in *capacity.

Detailed Description

An array-backed last-in first-out queue (aka pushdown stack).

This stack implementation may be used in either of two modes: (1) as a structure that stores only pointers to the client's data, or (2) as a structure that actually stores a copy of the client's data. In the first case, the client is responsible for memory management of data, which must persist as long as the stack is to be used. In the second case, the stack itself allocates the memory for the data copies, and the stack takes care of freeing the memory when the stack is destroy.

When the stack is used in copy mode, the pointers that are returned are valid only until the stack is destroyed or new values are pushed onto the stack in place of the old values.

When a stack is created, the initial capacity of the backing array may be specified, or a default may be used by specifying a capacity of 0. In both cases, the stack will automatically resize the backing array whenever space is needed to push an element.

The client may optionally supply a destroy function that is applied to each data element when the stack is destroyed.

Definition in file stack.h.

Typedef Documentation

Stack

A LIFO queue.

Functions are declared below for creating, destroying and manipulating a stack.

Definition at line 51 of file stack.h.

Function Documentation

cdsa_status_t stack_new	(	Stack **	new_stack,
		size_t	elem_size,
		size_t	capacity,
		cdsa_destroy_func1_t	destroy
	)

Create a new stack, setting *new_stack to the new stack on success, with elem_size determining whether to store pointers or copies in the stack.

If elem_size 0 or less, the stack stores only pointers to the data, and the client must ensure that the data elements are heap allocated if the stack itself is persistent. If greater than 0, elem_size gives the size of each element, and each element will be copied into the stack rather than stored as a pointer.

Regardless of whether the stack stores data or only pointers to data, the client must use the stack_destroy method to destroy the stack and free its associated memory.

If using the stack in copy mode, make sure your destroy function does not call free on the elements itself. It is okay to call it on pointers inside the element (since they refer to the original memory you allocated), but the element itself is a byte-for-byte copy that you didn't allocate.

Parameters:

	new_stack	A non-NULL pointer to a Stack pointer, which will be set to the new stack on success.
	elem_size	The size of each element (to store copies), or 0 (to store pointers).
	capacity	The initial capacity for the stack, or 0 for the default.
	destroy	A pointer to a function (or NULL) to be applied to every element in the stack when stack_destroy is called.

cdsa_status_t stack_destroy ( Stack ** stack )

Destroy *stack that was created using stack_new and set the pointer to NULL.

Calling this function frees memory associated with the stack itself, and if a non-NULL destroy function was used to create the stack, it will be applied to each remaining element in the stack. Any data that has already been popped in pointer mode must be managed by the client, and any pointers that have been popped in copy mode will no longer be valid after this function returns.

After this function returns, the stack will no longer be usable.

Parameters:

stack

A non-NULL pointer to stack pointer, which will be set to NULL on success.

cdsa_status_t stack_push	(	Stack *const	stack,
		void *const	data
	)

Push an item onto the stack.

Whether this results in the pointer being stored in the stack or a copy being made of what the pointer refers to is determined by how the stack was created via stack_new.

Parameters:

	stack	A non-NULL stack.
	data	A non-NULL pointer to the data to be copied into the stack, if in copy mode, or a possibly NULL pointer to be stored in the stack if in pointer mode.

cdsa_status_t stack_pop	(	Stack *const	stack,
		void *	ptr
	)

Answer the last pushed item from the stack, if any, recording result in *ptr.

If the stack was created with elem_size > 0, then the pointer returned is a pointer to a copy of the data of the original element. It will be overwritten when another element is pushed onto the stack, so the client should copy the data if it is needed for longer. The pointer will of course no longer be valid after the stack is destroyed.

Parameters:

	stack	A non-NULL stack.
	ptr	A pointer to a client pointer to store the popped element (a pointer to the copy in the stack in copy mode or the original pointer supplied by client if in pointer mode).

Returns:: If stack is empty, returns CDSA_EMPTY_ERR; if non-empty and successful, returns CDSA_SUCCESS; other codes indicate other errors.

cdsa_status_t stack_peek	(	Stack *const	stack,
		void *	ptr
	)

Peek at the last pushed item without removing it, setting ptr to the value if the stack is not empty.

Parameters:

	stack	A non-NULL stack.
	ptr	A pointer to a client pointer to store the element (a pointer to the copy in the stack in copy mode or the original pointer supplied by client if in pointer mode).

Returns:: If stack is empty, returns CDSA_EMPTY_ERR; if non-empty and successful, returns CDSA_SUCCESS; other codes indicate other errors.

cdsa_status_t stack_is_empty	(	const Stack *const	stack,
		bool *	is_empty
	)

Answer whether the stack is empty, recording result in *is_empty.

A stack is empty if it contains no elements. If stack is NULL, is_empty will not be set

Parameters:

	stack	A non-NULL stack.
	is_empty	A pointer to a boolean, which will be set to true iff stack is non-NULL and contains no elements or to false if stack is non-NULL and contains at least one element.

cdsa_status_t stack_size	(	const Stack *const	stack,
		size_t *	size
	)

Answer the size of the stack, recording result in *size.

The size of the stack is the total number of pushes that have occurred on the stack minus the total number of pops that have occurred.

Parameters:

	stack	A non-NULL stack.
	size	A non-NULL pointer to a size_t variable, to record the size on success.

cdsa_status_t stack_capacity	(	const Stack *const	stack,
		size_t *	capacity
	)

Answer the current capacity of the stack, recording result in *capacity.

The capacity is the total number of elements that may be stored in the stack without the underlying array being resized. The number of items that may be pushed without resizing is (stack->capacity - stack->size).

Parameters:

	stack	A non-NULL stack.
	capacity	A non-NULL pointer to a size_t variable, to record the capacity on success.


Defines
#define	DEFAULT_STACK_CAPACITY
	The default stack capacity that is used if 0 is specified as the capacity value to stack_new.
Typedefs
typedef struct Stack	Stack
	A LIFO queue.
Functions
cdsa_status_t	stack_new (Stack **new_stack, size_t elem_size, size_t capacity, cdsa_destroy_func1_t destroy)
	Create a new stack, setting *new_stack to the new stack on success, with elem_size determining whether to store pointers or copies in the stack.
cdsa_status_t	stack_destroy (Stack **stack)
	Destroy *stack that was created using stack_new and set the pointer to NULL.
cdsa_status_t	stack_push (Stack const stack, void const data)
	Push an item onto the stack.
cdsa_status_t	stack_pop (Stack const stack, void ptr)
	Answer the last pushed item from the stack, if any, recording result in *ptr.
cdsa_status_t	stack_peek (Stack const stack, void ptr)
	Peek at the last pushed item without removing it, setting ptr to the value if the stack is not empty.
cdsa_status_t	stack_is_empty (const Stack const stack, bool is_empty)
	Answer whether the stack is empty, recording result in *is_empty.
cdsa_status_t	stack_size (const Stack const stack, size_t size)
	Answer the size of the stack, recording result in *size.
cdsa_status_t	stack_capacity (const Stack const stack, size_t capacity)
	Answer the current capacity of the stack, recording result in *capacity.