I've learned a lot thanks to people on this board. Below is an implementation of an array stack that I wrote and rewrote as I learned new or better concepts. I hope people will take a moment to review it and give me any and all criticisms. I'm doing this to try to learn so the more criticism the better.
stack.h
Code:
#ifndef _STACK_H_
#define _STACK_H_
#include <stddef.h> /* size_t */
typedef
struct stack
stack_t;
struct stack {
void **stack;
size_t top;
size_t capacity;
unsigned int err;
};
enum {
STACK_ERR_OK,
STACK_ERR_MEMORY
};
stack_t * stack_create(void);
void stack_destroy(stack_t *stack);
void stack_push(stack_t *stack, void *item);
void * stack_pop(stack_t *stack);
void * stack_peek(stack_t *stack);
int stack_isempty(stack_t *stack);
/*******************************************************************************
*
* stack_create
* Dynamically allocates and initializes a new stack. Returns a valid pointer
* if successful, NULL otherwise.
*
* stack_destroy
* Frees all memory dynamically allocated by the associated stack functions.
* It will *not* free items that have been pushed on the stack. If you
* dynamically allocated these items yourself then you must free them
* yourself.
*
* stack_push
* Pushes the given item onto the stack. The stack will increase in size if
* necessary. If memory could not be allocated to accomodate the stack's new
* size, the stack will retain its state prior to the function call and the
* member 'err' is set to STACK_ERR_MEMORY. The member 'err' is otherwise
* guarenteed to hold the value STACK_ERR_OK.
*
* stack_pop
* Removes and returns the last item pushed onto the stack. If the stack is
* empty the behavior is undefined.
*
* stack_peek
* Returns the last item pushed onto the stack. If the stack is empty the
* behavior is undefined.
*
* stack_isempty
* Returns a value that evaluates to true if the stack is empty, false
* otherwise.
*
******************************************************************************/
#endif
stack.c
Code:
#ifndef _STACK_C_
#define _STACK_C_
#include <stddef.h> /* NULL size_t */
#include <stdlib.h> /* malloc realloc free */
#include "stack.h"
#define STACK_INITIAL_CAPACITY (8 * sizeof(int))
#define STACK_CAPACITY_INCREMENT (8 * sizeof(int))
stack_t *
stack_create(void)
{
stack_t *stack;
stack = malloc(sizeof(stack_t));
if (stack == NULL)
return NULL;
stack->stack = malloc(STACK_INITIAL_CAPACITY * sizeof(void *));
if (stack->stack == NULL) {
free(stack);
return NULL;
}
stack->top = (size_t)-1;
stack->capacity = STACK_INITIAL_CAPACITY;
stack->err = STACK_ERR_OK;
return stack;
}
void
stack_destroy(stack_t *stack)
{
free(stack->stack);
free(stack);
}
void
stack_push(stack_t *stack, void *item)
{
stack->err = STACK_ERR_OK;
stack->top++;
if (stack->top == stack->capacity)
{
void *bigger_stack;
stack->capacity += STACK_CAPACITY_INCREMENT;
bigger_stack = realloc(stack->stack, stack->capacity * sizeof(void *));
if (bigger_stack == NULL) {
stack->err = STACK_ERR_MEMORY;
stack->top--;
stack->capacity -= STACK_CAPACITY_INCREMENT;
return;
}
stack->stack = bigger_stack;
}
stack->stack[stack->top] = item;
}
void *
stack_pop(stack_t *stack)
{
stack->top--;
if (stack->capacity - stack->top - 1 >= 1.5 * STACK_CAPACITY_INCREMENT)
{
void *smaller_stack;
stack->capacity -= STACK_CAPACITY_INCREMENT;
smaller_stack = realloc(stack->stack, stack->capacity * sizeof(void *));
if (smaller_stack == NULL)
stack->capacity += STACK_CAPACITY_INCREMENT;
else
stack->stack = smaller_stack;
}
return stack->stack[1 + stack->top];
}
void *
stack_peek(stack_t *stack)
{
return stack->stack[stack->top];
}
int
stack_isempty(stack_t *stack)
{
return stack->top == (size_t)-1;
}
#endif