src/stack.c

   1 /*******************************************************************************
   2  * Reverse Polish Notation calculator.                                         *
   3  * Copyright (c) 2007-2008, Samuel Fredrickson <kinghajj@gmail.com>            *
   4  * All rights reserved.                                                        *
   5  *                                                                             *
   6  * Redistribution and use in source and binary forms, with or without          *
   7  * modification, are permitted provided that the following conditions are met: *
   8  *     * Redistributions of source code must retain the above copyright        *
   9  *       notice, this list of conditions and the following disclaimer.         *
  10  *     * Redistributions in binary form must reproduce the above copyright     *
  11  *       notice, this list of conditions and the following disclaimer in the   *
  12  *       documentation and/or other materials provided with the distribution.  *
  13  *                                                                             *
  14  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER ``AS IS'' AND ANY EXPRESS *
  15  * OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED           *
  16  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE      *
  17  * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE FOR ANY        *
  18  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES  *
  19  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR          *
  20  * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER  *
  21  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT          *
  22  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY   *
  23  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH *
  24  * DAMAGE.                                                                     *
  25  ******************************************************************************/
  26
  27 /*******************************************************************************
  28  * stack.c - implements the value stack.                                       *
  29  ******************************************************************************/
  30
  31 #include "rpn.h"
  32 #include <stdio.h>
  33 #include <stdlib.h>
  34
  35 /**
  36  * Creates a new, empty stack.
  37  *
  38  * @return The new, empty stack.
  39  */
  40 RPNStack *RPN_newStack(RPNStack *next)
  41 {
  42         RPNStack *stack = new(RPNStack);
  43         if(!stack)
  44                 RPN_error("could not allocate memory for the stack.");
  45         stack->first = NULL;
  46         stack->next  = next;
  47         stack->len   = 0;
  48         RPN_dprintf("allocated stack %p", stack);
  49         return stack;
  50 }
  51
  52 /**
  53  * Creates a new node.
  54  * @param value The value of the node.
  55  *
  56  * @param next The next node in the stack.
  57  * @return The new node.
  58  */
  59 RPNNode *RPN_newNode(RPNValue value, RPNNode *next)
  60 {
  61         RPNNode *node = new(RPNNode);
  62         if(!node)
  63                 RPN_error("could not allocate memory for a stack node.");
  64         node->value = value;
  65         node->next  = next;
  66         RPN_dprintf("allocated node at %p to %p", node, next);
  67         return node;
  68 }
  69
  70 /**
  71  * Creates a deep copy of a node.
  72  *
  73  * @param node The node to copy.
  74  * @return A new node and its subnodes with the same values of the input node.
  75  */
  76 RPNNode *RPN_copyNode(RPNNode *node)
  77 {
  78         RPNNode *new_node = NULL;
  79
  80         if(node)
  81                 new_node = RPN_newNode(node->value, RPN_copyNode(node->next));
  82
  83         return new_node;
  84 }
  85
  86 /**
  87  * Creates a deep copy of the stack.
  88  *
  89  * @param stack The stack to copy.
  90  * @return A new stack with new nodes with the same values of the input stack.
  91  */
  92 RPNStack *RPN_copyStack(RPNStack *stack)
  93 {
  94         RPNStack *new_stack = NULL;
  95
  96         if(stack) {
  97                 new_stack = RPN_newStack(stack);
  98                 new_stack->first = RPN_copyNode(stack->first);
  99                 new_stack->len = stack->len;
 100         }
 101
 102         return new_stack;
 103 }
 104
 105 /**
 106  * Pushes a value to a stack.
 107  *
 108  * @param stack The stack.
 109  * @param value The value to push.
 110  * @return true if succeeds.
 111  */
 112 bool RPN_push(RPNStack *stack, RPNValue value)
 113 {
 114         RPNNode *node;
 115
 116         if(!stack)
 117                 RPN_error("tried to push to a NULL stack.");
 118         node = RPN_newNode(value, stack->first);
 119         stack->first = node;
 120         stack->len++;
 121         RPN_dprintf("pushed " RPN_VALUE_SHORT_FORMAT  " to stack", value);
 122         return true;
 123 }
 124
 125 /**
 126  * Pops a value from a stack.
 127  *
 128  * @param stack The stack to pop.
 129  * @return The popped value.
 130  */
 131 RPNValue RPN_pop(RPNStack *stack)
 132 {
 133         RPNNode *popped;
 134         RPNValue value = 0;
 135
 136         if(!stack)
 137                 RPN_error("tried to pop from a NULL stack.");
 138         if(RPN_canOperate(stack, 1))
 139         {
 140                 // get node to pop
 141                 popped = stack->first;
 142                 value = popped->value;
 143                 // re-wire stack
 144                 stack->first = popped->next;
 145                 // free node
 146                 RPN_free(popped);
 147                 stack->len--;
 148                 RPN_dprintf("poped %x from stack", popped);
 149         }
 150
 151         return value;
 152 }
 153
 154 /**
 155  * Returns the topmost item of a stack.
 156  *
 157  * @param stack The stack.
 158  * @return The topmost item of the stack.
 159  */
 160 RPNValue RPN_peek(RPNStack *stack)
 161 {
 162         RPNValue value = 0;
 163
 164         if(!stack)
 165                 RPN_error("attempted to peek a NULL stack.");
 166
 167         if(RPN_canOperate(stack, 1))
 168                 value = stack->first->value;
 169
 170         return value;
 171 }
 172
 173 /**
 174  * Swaps the top two items of a stack.
 175  *
 176  * @param stack The stack.
 177  */
 178 void RPN_swap(RPNStack *stack)
 179 {
 180         RPNValue first, second;
 181
 182         if(RPN_canOperate(stack, 2))
 183         {
 184                 first  = RPN_pop(stack);
 185                 second = RPN_pop(stack);
 186                 RPN_push(stack, first);
 187                 RPN_push(stack, second);
 188         }
 189 }
 190
 191 /**
 192  * Frees a stack and all of its nodes.
 193  *
 194  * @param stack The stack to free.
 195  */
 196 void RPN_freeStack(RPNStack *stack)
 197 {
 198         RPNNode *node, *next;
 199
 200         if(stack) {
 201                 // free all nodes
 202                 for(node = stack->first; node; node = next)
 203                 {
 204                         next = node->next;
 205                         RPN_free(node);
 206                         RPN_dprintf("freed node %p", node);
 207                 }
 208
 209                 // free the stack
 210                 RPN_free(stack);
 211                 RPN_dprintf("freed stack %p", stack);
 212         }
 213 }
 214
 215 /**
 216  * Tests if the stack has at least a certain number of items.
 217  *
 218  * @param stack The stack to test.
 219  * @param nargs The number of required items.
 220  * @return true or false.
 221  */
 222 bool RPN_canOperate(RPNStack *stack, unsigned int nargs)
 223 {
 224         if(!stack)
 225                 RPN_error("tried to probe a NULL stack.");
 226
 227         RPN_dprintf("probing %p\n", stack);
 228
 229         // can only operate if there are enough items in the stack
 230         return stack->len >= nargs ? true : false;
 231 }
 232
 233 /**
 234  * Prints a stack.
 235  *
 236  * @param stack The stack.
 237  */
 238 void RPN_printStack(RPNStack *stack)
 239 {
 240         RPNNode *node;
 241
 242         RPN_printf("[ ");
 243         for(node = stack->first; node; node = node->next)
 244                 RPN_printf(RPN_VALUE_SHORT_FORMAT ", ", node->value);
 245         RPN_printf("]");
 246 }
 247
 248 /**
 249  * Prints a stack in more detail.
 250  *
 251  * @param stack The stack.
 252  */
 253 void RPN_printStackDetailed(RPNStack *stack)
 254 {
 255         RPNNode *node;
 256
 257         RPN_printf("[ ");
 258         for(node = stack->first; node; node = node->next)
 259                 RPN_printf(RPN_VALUE_LONG_FORMAT ", ", node->value);
 260         RPN_printf("]");
 261 }