Stack Implementation with data hiding
This code snippet implements a basic stack in C. The interesting part is that the implementation uses data hiding to shroud the internal details of the stack. There are two separate stack implementations: a stack growing up and a stack growing down. This is to demonstrate that the specific implementation of an object can't be relied on - only the public API.
This snippet is technically three separate files - a header and two separate implementations. Preprocessor defines can control which implementation is used. This file could be compiled with Cygwin GCC 4.5.3.
Update: Several people correctly pointed out I never checked for NULL pointers in considering the validity of the stack. Good catch. Fixed.
/**@file stack.h
@brief This header file contains the public types, variables and methods associated with the stack implementation in stack.c. None of the internal implementation details are exposed. This allows the implementation to vary while the public interface remains the same.
@author Stephen Friederichs
@date 4/28/13
@note This compiles in Cygwin using GCC 4.5.3
*/
#ifndef __STACK_H__
#define __STACK_H__
/**@include stdint.h
@brief Include for standard integer definitions (ie, uint8_t, int32_t, etc)
*/
#include <stdint.h>
/**@include stdlib.h
@brief Include stdlib for malloc and free definition
*/
#include <stdlib.h>
/**@include stddef.h
@brief Include stddef.h for definition of size_t
*/
#include <stddef.h>
/**@typedef stack
@brief Define the type for a stack handle
There are two fundamental aspects of data hiding in C used here.
The first is that you can define a type as a pointer to a struct WITHOUT
having defined the struct. The struct is defined in the source file alone
and no implementation details are exposed in the header file.
The second aspect of this typedef is that stack_t is defined as a
pointer to a const st_stack struct. Const correctness is tricky in C but
for this usage the stack_t type points to a constant struct - changes to the
struct are NOT ALLOWED when the stack_t type is used.
Is this tough security? No. This only ensures the compiler complains if
someone tries to dereference a stack_t type and mess with the data inside
(of course, they don't know what any of the data inside the struct IS due
to the fact it's hidden in the source file). An unscrupulous person could
cast to a void pointer and do whatever they want with it. Or edit the
header file to remove the const. And of course, if they have the source they
know exactly what's inside the struct and can do whatever they want.
Definitely read the Wikipedia article on const correctness to get this all
straight in your head: http://en.wikipedia.org/wiki/Const-correctness
*/
typedef const struct st_stack * stack_t;
/**@typedef stack_element_t
@brief Define the type of the stack elements - bytes in this case
*/
typedef uint8_t stack_element_t;
/**@fn stack_init
@brief Initializes the stack and returns a pointer to the stack struct
@param[in] size The number of elements that can be stored on the stack
@return A pointer to the stack or NULL if the initialization failed.
*/
stack_t stack_init(size_t size);
/**@fn stack_push
@brief Push an element on to the stack
@param[in] stack A pointer to the stack to which we are pushing data
@param[in] element The data to push to the stack
@return Status of the call
@retval -1 The supplied pointer doesn't point to a stack
@retval -2 The stack is full
@retval 0 The call succeeded
*/
int stack_push(stack_t stack, stack_element_t element);
/**@fn stack_pop
@brief Remove an element from the stack
@param[in] element Pointer to an element variable to hold the received data
@note The element argument is a const pointer to an element. This means that the function will not change the address of the pointer, but the value of the element can change (this is the entire point of the function call).
@return Status of the call
@retval -1 Call failed - not a valid stack
@retval -2 Call failed - stack empty
@retval 0 Call succeeded
*/
int stack_pop(stack_element_t const * element);
/**@fn stack_destroy
@brief This stack no longer pleases me and I wish it gone. Or the program is exiting. Either way, free the memory associated with the stack.
@param[in] stack The stack which should no longer exist.
@return Status of the call
@retval -1 Call failed - not a valid stack
@retval 0 Call succeeded
*/
int stack_destroy(stack_t stack);
#endif
/*---------------------------------------------------------------------------*/
#ifdef STACK_IMPLEMENTATION_1
/**@file stack.c
@brief This file implements a basic stack in C but uses C's scope system and typing to hide the internal implementation of the stack and only allow to publicly-advertised functions and variables. This stack implementation uses an array to hold the data and grows up.
@note Implementation 1
@author Stephen Friederichs
@date 4/20/13
*/
/**@include stack.h
@brief stack.h contains all of the types and includeds that allow this stack implementation uses.
*/
/* This file doesn't actually exist - it's all of the above definitions
To avoid errors, comment it out
*/
//#include <stack.h>
/**@def STACK_CANARY_VALUE
@brief Value that the canary in the stack struct must be set to for the stack to be considered a value stack object
*/
#define STACK_CANARY_VALUE 0x31
/**@struct st_stack
@brief Struct containing the internal variables for the stack implementation
*/
struct st_stack
{
uint8_t canary; /**< A value that will be initialized to a specific value to show signify that the pointer points to a stack and that the stack is a valid stack object. This can't protect against any malicious intent but should at least serve as an indication that someone might have tried to modify the internals of the stack object itself*/
stack_element_t * array;/**< Pointer to the array where the stack data is stored*/
size_t head; /**< Index of the most recently added element in the stack*/
size_t size; /**< The maximum size of the stack*/
};
/**@fn _stack_valid
@brief Returns 1 if the stack object is valid
@param[in] stack Pointer to the stack
@return Validity of the object
@retval 1 Valid object
@retval 0 Invalid object
@note This function can only be called from within this file.
*/
static int _stack_valid( stack_t stack)
{
return (STACK_CANARY_VALUE == stack->canary)?1:0;
}
/**@fn stack_init
See above
*/
stack_t stack_init(size_t size)
{
struct st_stack * new_stack = malloc(sizeof(st_stack));
if(NULL == new_stack)
{
return NULL;
}
new_stack->array = malloc(sizeof(st_element)*size));
if(NULL == new_stack->array)
{
/* Allocation of the array failed, so free the memory associated with the stack
object before returning
*/
free(new_stack);
return NULL;
}
new_stack->head = 0; /* This stack grows up so it starts at element 0*/
new_stack->size = size
new_stack->canary = STACK_CANARY_VALUE; /* Initialize the stack's canary
to the appropriate value*/
/* Return a pointer to the new stack object - appropriately cast
to the const type to avoid warnings
*/
return (stack_t)new_stack;
}
/**@fn stack_push
See above
*/
int stack_push(stack_t stack, stack_element_t element)
{
/* The passed pointer is a pointer to a const stack,
so generate a non-const pointer
*/
st_stack * stack_pointer = (st_stack *)stack;
if(!_stack_valid(stack))
{
return -1; /* Object is not a stack*/
}
if(stack->head == (stack->size-1))
{
return -2; /* Stack is full*/
}
/* All checks passed, add element*/
stack_pointer->array[++head] = element;
return 0;
}
/**@fn stack_pop
See above
*/
int stack_pop(stack_t stack, stack_element const * element)
{
stack_element popped_element;
/* The passed pointer is a pointer to a const stack,
so generate a non-const pointer
*/
st_stack * stack_pointer = (st_stack*)stack;
if(!_stack_valid(stack))
{
return -1; /* Pointer doesn't point to a stack*/
}
/* Check to see if the stack is empty*/
if(0 == stack->head)
{
return -2; /* Stack is empty, cannot pop*/
}
*popped_element = stack->array[stack_pointer->head--];
return 0;
}
/**@fn stack_destroy
See above
*/
int stack_destroy(stack_t stack)
{
/* The passed pointer is a pointer to a const stack,
so generate a non-const pointer
*/
st_stack stack_pointer = (st_stack*)stack;
if(!_stack_valid(stack))
{
return -1; /* Signal failure - not a stack object*/
}
/* Clear the canary - if the pointer to this struct is reused after the
stack is destroyed, the canary will be invalid and the call wil fail
*/
stack_pointer->canary = 0x00;
free(stack->array);
free(stack);
return 0;
}
/* Don't allow the use of the STACK_CANARY_VALUE outside of this vile*/
#undef STACK_CANARY_VALUE
#else //STACK_IMPLEMENTATION_2
/**@file stack.c
@brief This file implements a basic stack in C but uses C's scope system and typing to hide the internal implementation of the stack and only allow to publicly-advertised functions and variables. This stack implementation uses an array to hold the data and grows down.
@note Implementation 2
@author Stephen Friederichs
@date 4/20/13
*/
/**@include stack.h
@brief stack.h contains all of the types and includes that allow this stack implementation uses.
*/
/* This file doesn't actually exist - it would if this weren't one huge file
So comment this out to ensure no compilation errors
*/
//#include <stack.h>
/**@def STACK_CANARY_VALUE
@brief Value that the canary in the stack struct must be set to for the stack to be considered a value stack object
*/
#define STACK_CANARY_VALUE 0x32
/**@struct st_stack
@brief Struct containing the internal variables for the stack implementation
*/
struct st_stack
{
uint8_t canary; /**< A value that will be initialized to a specific value to show signify that the pointer points to a stack and that the stack is a valid stack object. This won't protect against any truly malicious intent but might indicate that someone tried to modify the internals of the object themselves.*/
stack_element_t * array; /**< Pointer to the array where the stack data is stored*/
size_t head; /**< Index of the most recently added element in the stack*/
size_t size; /**< The maximum size of the stack*/
};
/**@fn _stack_valid
@brief Returns 1 if the stack object is valid
@param[in] stack Pointer to the stack
@return Validity of the object
@retval 1 Valid object
@retval 0 Invalid object
@note This function can only be called from within this file.
*/
static int _stack_valid( stack_t stack)
{
/* Ensure we don't try to dereference a NULL pointer
Obviously if the pointer is NULL it's not a valid stack
*/
if(NULL == stack)
{
return 0;
}
return (STACK_CANARY_VALUE == stack->canary)?1:0;
}
/**@fn stack_init
See above
*/
stack_t stack_init(size_t size)
{
struct st_stack * new_stack = malloc(sizeof(st_stack));
if(NULL == new_stack)
{
return NULL;
}
new_stack->array = malloc(sizeof(st_element)*size));
if(NULL == new_stack->array)
{
/* Allocation failed, so free the memory associated with the stack
object before returning
*/
free(new_stack);
return NULL;
}
new_stack->head = size; /* This stack grows down so it starts at the
highest element*/
new_stack->size = size
new_stack->canary = STACK_CANARY_VALUE;
return (stack_t)new_stack;
}
/**@fn stack_push
See above
*/
int stack_push(stack_t stack, stack_element_t element)
{
/* The passed pointer is a pointer to a const stack,
so generate a non-const pointer
*/
st_stack * stack_pointer = (st_stack *)stack;
if(!_stack_valid(stack))
{
return -1; /* Object is not a stack*/
}
if(0 == stack->head)
{
return -2; /* Stack is full*/
}
/* All checks passed, add element*/
stack_pointer->array[--head] = element;
/* Return success*/
return 0;
}
/**@fn stack_pop
See above
*/
int stack_pop(stack_t stack, stack_element const * element)
{
stack_element popped_element;
/* The passed pointer is a pointer to a const stack,
so generate a non-const pointer so we can modify
the head variable.
*/
st_stack * stack_pointer = (st_stack *)stack;
if(!_stack_valid(stack))
{
return -1; /* Pointer doesn't point to a stack*/
}
/* Check to see if the stack is empty*/
if(stack->size == stack->head)
{
return -2; /* Stack is empty, cannot pop*/
}
*popped_element = stack->array[stack_pointer->head--];
/* Signal success*/
return 0;
}
/**@fn stack_destroy
See above
*/
int stack_destroy(stack_t stack)
{
/* The passed pointer is a pointer to a const stack,
so generate a non-const pointer so the canary can
be cleared later
*/
st_stack * stack_pointer = (st_stack *)stack;
if(!_stack_valid(stack))
{
return -1; /* Signal failure - not a stack object*/
}
/* Clear the canary - if the pointer to this struct is reused after the
stack is destroyed, the canary will be invalid and the call wil fail
*/
stack_pointer->canary = 0x00;
free(stack->array);
free(stack);
/* Return success*/
return 0;
}
/* Don't allow the use of the STACK_CANARY_VALUE outside of this vile*/
#undef STACK_CANARY_VALUE
#endif
