20-queue-and-stack/stack.c

/*----------------------------------------------------------
 *				HTBLA-Leonding / Class: 2IHIF
 * ---------------------------------------------------------
 * Exercise Number: S03
 * Title:			Stack implementation
 * Author:			Marc Tismonar
 * ----------------------------------------------------------
 * Description:
 * Implementation of a stack based on an advanced singly linked list.
 * ----------------------------------------------------------
 */

/*
  Implementation notes:

  1) The 'StackData' struct SHALL encapsulate the underlying list
     to decouple stack and stack interfaces. No further members are required.

  2) Stack allocation: 
     Use functions `mem_alloc(…)` and `mem_free(…)`
     declared in `allocator.h`. DO NOT use `malloc(…)` and `free(…)` directly
     as unit tests will fail.

  3) Avoid code duplication wherever (reasonably) possible.
     The implemenation of each function mostly delegates 
     to the corresponding stack function (one-liners).

     Implement the combined functionality of 'pop' and 'peek' 
     as a single private function which is used by 'pop' and 'peek'.

*/

/* includes */
#include <stdbool.h>
#include "stack.h"
#include "advanced_singly_linked_list.h"
#include "allocator.h"

/** The implementation of stack data */
struct IntStackData {
   IntList list;
};

/* ===================================================================== */
/* private stack functions */


/* ===================================================================== */
/**
 * Obtains ('creates') and provides a 'new' stack instance.
 * Any stack obtained via this function MUST be released using
 * function `release_stack()`.
 * 
 * Note: This function does not make any assumptions 
 * about how stack components, esp. nodes, are allocated.
 * 
 * @return IntStack The stack instance or 0, if no stack could by instantiated.
 */
IntStack stack_obtain() {
   IntStack stack = (IntStack)alloc_mem(sizeof(struct IntStackData));
   if (stack != 0) {
      stack->list = list_obtain();
   }

   return stack;
}

/**
 * Releases a stack that was obtained earlier via function `obtain_stack`.
 * Released stacks MUST NOT be used anymore.
 * 
 * Note: The implementation of this function does not make any assumptions
 * about the allocation method of stack elements, but MUST match the implementation
 * of function `obtain_stack` as its inverse function.
 * 
 * @param p_stack The pointer to the stack to release. The value of the pointer
 * is set to 0, if the stack was successfully released, otherwise it is left untouched.
 */
IntStack stack_release(IntStack* p_stack) {
   if (p_stack == 0 || *p_stack == 0) {
      return 0;
   }

   IntStack stack = *p_stack;
   list_release(&stack->list);
   free_mem(stack);
   *p_stack = 0;

   return stack;
}

/**
 * Determines whether or not the given stack is valid.
 * 
 * @param stack The stack to evaluate.
 * @return `True` if the stack is valid, false otherwise.
 */
bool stack_is_valid(IntStack stack) {
   return stack != 0 && stack->list != 0;
}

/**
 * Determines whether or not the stack contains at least one item.
 * 
 * @param stack The stack to evaluate.
 * @return `False` if the stack contains one or more items, `true` otherwise.
 */
bool stack_is_empty(IntStack stack) {
   return !stack_is_valid(stack) || list_is_empty(stack->list);
}

/**
 * Provides the number of values stored in the stack.
 * 
 * @param stack The stack to evaluate.
 * @return The number of values the stack contains.
 */
int stack_get_size(IntStack stack) {
   if (!stack_is_valid(stack)) {
      return 0;
   }

   return list_get_size(stack->list);
}

/**
 * Clears the given stack by removing all values from the stack.
 * 
 * @param stack The stack to clear.
 */
void stack_clear(IntStack stack) {
   if (!stack_is_valid(stack)) {
      return;
   }

   list_clear(stack->list);
}

/**
 * Inserts the given value to the stack.
 * 
 * @param stack The stack to which the value shall be appended.
 * @param value The value to append to the stack.
 */
void stack_push(IntStack stack, int value) {
   if (!stack_is_valid(stack)) {
      return;
   }

   list_insert(stack->list, value);
}

/**
 * Provides the value that 'pop' would provided but WITHOUT removing 
 * this value from the stack.
 * 
 * @param stack The stack from which the value shall be peeked.
 * @return The next value or 0, if the stack is empty.
 */
int stack_peek(IntStack stack) {
   if (!stack_is_valid(stack)) {
      return 0;
   }

   return list_get_at(stack->list, stack_get_size(stack) - 1);
}

/**
 * Provides AND removes the top-most value from the stack.
 * 
 * @param stack The stack from which the value be removed shall be returned.
 * @return The value or 0, if the stack is empty.
 */
int stack_pop(IntStack stack) {
   if (!stack_is_valid(stack)) {
      return 0;
   }

   return list_remove_at(stack->list, stack_get_size(stack) - 1);
}