General Stack Implementation
Hey all,
I’ve implemented a general stack data type and am posting the source code here in the hope that others may find it useful.
The stack:
1. Can hold objects of any type.
2. Can grow dynamically
3. Will free memory occupied by stack elements, provided a client-defined free function exists.
stack.h:
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:
Code:
struct Stack_Elt {
...fields…
};
This structure must be defined comprising the fields of your stack items. Now include the stack.h header.
To create a new stack:
Code:
Stack *stack_new(int, int, void (*elt_free)(void *));
The first parameter is the size of the stack. The second parameter is the number of items to expand the stack by when it reaches the top of the stack (pass 0 to indicate a non-growing stack). And the third parameter is the user-defined function to free a complex stack item structure, if necessary. By default stack items will be freed with free().
