Code:
#ifndef __STACK_H__
#define __STACK_H__
/**
* stack.h: Definitions for a general stack type.
*
* Clients need to define the Stack_Elt data type
* specifying the fields comprising a stack element
* before including this header:
* ...
* typedef struct Stack_Elt {
* ...fields...
* } Stack_Elt, *Stack_Elt_POINTER;
* ...
* #include <stack.h>
*/
#define N_STACK_ELEMENTS(S) (S->size)
#define STACK_MAX_ELEMENTS(S) (N_STACK_ELEMENTS(S) - 1)
#define STACK_CURRENT_SIZE(S) (N_STACK_ELEMENTS(S) * sizeof(Stack_Elt *))
#define STACK_EXPAND_SIZED(S, N) \
(STACK_CURRENT_SIZE(S) + (N * sizeof(Stack_Elt *)))
/**
* How many elements occupy the stack.
*/
#define STACK_N_ELEMENTS(S) \
((N_STACK_ELEMENTS(S) - (N_STACK_ELEMENTS(S) - (S->top + 1))))
#define STACK_IS_EMPTY(S) ((S->top == -1))
#define STACK_EMPTY_CLEAR(S) (stack_wipe(S))
typedef struct Stack_Elt Stack_Elt;
typedef struct Stack {
int top; /* top of stack */
int size; /* number of possible elements */
int expand; /* size to grow by */
void (*elt_free)(void *); /* function to free stack elements */
struct Stack_Elt **data; /* stack elements */
} Stack, *Stack_POINTER;
int stack_empty(Stack *);
void stack_wipe(Stack *);
Stack *stack_new(int, int, void (*elt_free)(void *));
Stack *stack_expand(Stack *, int);
Stack_Elt *stack_pop(Stack *);
Stack_Elt *stack_peek(Stack *);
Stack_Elt *stack_push(Stack *, Stack_Elt *);
#endif /* __STACK_H__ */
stack.c:
Code:
/**
* stack.c: Implementation of a general stack.
*/
#include <stdlib.h>
#include <string.h>
#include "stack.h"
enum { FALSE, TRUE };
struct Stack_Elt { /* opaque */ };
/**
* stack_new: Create a new stack.
*/
Stack *stack_new(int size, int expand, void (*elt_free)(void *)) {
int i = 0;
Stack *stack = malloc(sizeof(Stack));
stack->top = -1;
stack->size = size;
stack->expand = (expand > 0 ? expand : FALSE);
stack->elt_free = (elt_free == NULL ? free : elt_free);
stack->data = calloc(size, sizeof(Stack_Elt *));
for (i = 0; i < stack->size; i++)
stack->data[i] = malloc(sizeof(Stack_Elt));
return stack;
}
/**
* stack_empty: Check whether stack is empty.
*/
int stack_empty(Stack *stack) { return stack->top == -1; }
/**
* stack_pop: Remove top item from stack and return it.
*/
Stack_Elt *stack_pop(Stack *stack) {
return (STACK_IS_EMPTY(stack)) ? NULL : stack->data[stack->top--];
}
/**
* stack_peek: Preview item at the top of the stack.
*/
Stack_Elt *stack_peek(Stack *stack) {
Stack_Elt *elt = malloc(sizeof(Stack_Elt));
return (STACK_IS_EMPTY(stack)) ?
NULL : memcpy(elt, stack->data[stack->top], sizeof(Stack_Elt));
}
/**
* stack_push: Push a stack element onto the stack.
*/
Stack_Elt *stack_push(Stack *stack, Stack_Elt *elt) {
/**
* Stack push is invalid if stack is full.
*/
if (stack->top == STACK_MAX_ELEMENTS(stack))
if (stack->expand)
stack = stack_expand(stack, stack->expand);
else
return NULL;
/**
* Insert element into next available slot.
* Free memory occupied by a prior element, if necessary.
*/
stack->top++;
if (stack->data[stack->top] != NULL)
stack->elt_free(stack->data[stack->top]);
stack->data[stack->top] = elt;
return elt;
}
/**
* stack_expand: Expand the size of the stack.
*/
Stack *stack_expand(Stack *stack, int n_elements) {
stack->data = realloc(stack->data, STACK_EXPAND_SIZED(stack, n_elements));
stack->size = N_STACK_ELEMENTS(stack) + n_elements;
return stack;
}
/**
* stack_wipe: Remove all stack elements and free their memory.
*/
void stack_wipe(Stack *stack) {
/**
* Number of elements is S->top + 1
*/
int n_elements = STACK_N_ELEMENTS(stack);
while (!stack_empty(stack))
stack->elt_free(stack_pop(stack));
/**
* Clean the slate.
*/
memset(stack->data, 0, n_elements);
}
To use the stack, define your stack items with:
