#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

#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

#ifndef _STACK_H_
#define _STACK_H_

#ifndef FOO_H_
#define FOO_H_

#endif