teaching machines

CS 330 Lecture 16 – Polymorphism in C

February 28, 2014 by . Filed under cs330, lectures, spring 2014.

Agenda

Think About This

Pair up with a neighbor. One of you is pro, the other con. Your topic: static types—are the benefits worth the costs? Spend 90 seconds forming your argument.

Then persuade your neighbor to your side.

Code

stack1.c

#include "ezmalloc.h"

#include "stack1.h"

staq_t *stack_new() {
  staq_t *stack = EZMALLOC(staq_t, 1);  
  stack->head = NULL;
  return stack;
}

void stack_push(staq_t *stack, const void *new_item) {
  node_t *new_node = EZMALLOC(node_t, 1);  
  new_node->item = new_item;
  new_node->next = stack->head;
  stack->head = new_node;
}

void stack_free(staq_t *stack) {
  while (!stack_is_empty(stack)) {
    stack_pop(stack);
  }
  free(stack);
}

const void *stack_pop(staq_t *stack) {
  const void *popped_item = stack->head->item;
  node_t *node_to_axe = stack->head;
  stack->head = stack->head->next;
  free(node_to_axe);
  return popped_item;
}

int stack_is_empty(staq_t *stack) {
  return stack->head == NULL;
}

const void *stack_peek(staq_t *stack) {
  return stack->head->item;
}

stack1.h

#ifndef STACK1_H
#define STACK1_H

typedef struct node_t {
  const void *item;
  struct node_t *next;
} node_t;

typedef struct {
  node_t *head;
} staq_t;

staq_t *stack_new(); // row # % 6 == 0
void stack_push(staq_t *stack, const void *new_item); // row # % 6 == 1
int stack_is_empty(staq_t *stack); // row # % 6 == 2
const void *stack_pop(staq_t *stack); // row # % 6 == 3
const void *stack_peek(staq_t *stack); // row # % 6 == 4
void stack_free(staq_t *stack); // row # % 6 == 5

#endif

postfix.c

#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "ezmalloc.h"
#include "stack1.h"

int main(int argc, char **argv) {
  staq_t *operands = stack_new();

  // Visit each token in postfix expression.
  for (int i = 0; i < argc; ++i) {

    // Check if token is an operand. Either -\d* or \d+.
    if (strlen(argv[i]) > 1 || isdigit(argv[i][0])) {
      double *new_operand = EZMALLOC(double, 1);
      *new_operand = atof(argv[i]);
      stack_push(operands, new_operand);
      /* stack_push(operands, (void *) atof(argv[i])); */
      /* stack_push(operands, &atof(argv[i])); */
    }

    else {
      double *bp = (double *) stack_pop(operands);
      double *ap = (double *) stack_pop(operands);
      double b = *bp;
      double a = *ap;
      free(bp);
      free(ap);
      double *answer = EZMALLOC(double, 1);

      if (strcmp(argv[i], "+") == 0) {
        *answer = a + b;
      } else if (strcmp(argv[i], "-") == 0) {
        *answer = a - b;
      } else if (strcmp(argv[i], "*") == 0) {
        *answer = a * b;
      } else if (strcmp(argv[i], "/") == 0) {
        *answer = a / b;
      }

      stack_push(operands, answer);
    }
  }

  /* double *answer = stack_pop(operands); */
  printf("%lf\n", *((double *) stack_peek(operands)));
  stack_free(operands);  
  return 0;
}

stack3.c

#include "PREFIX_stack.h"
#include "ezmalloc.h"

PREFIX_staq_t *PREFIX_stack_new() {
  PREFIX_staq_t *stack = EZMALLOC(PREFIX_staq_t, 1);
  stack->head = NULL;
  return stack;
}

void PREFIX_stack_push(PREFIX_staq_t *stack, ITEMTYPE new_item) {
  PREFIX_node_t *node = EZMALLOC(PREFIX_node_t, 1);
  node->item = new_item;
  node->next = stack->head;
  stack->head = node;
}

int PREFIX_stack_is_empty(PREFIX_staq_t *stack) {
  return stack->head == NULL;
}

ITEMTYPE PREFIX_stack_pop(PREFIX_staq_t *stack) {
  PREFIX_node_t *PREFIX_node_to_axe = stack->head;
  ITEMTYPE item = PREFIX_node_to_axe->item;
  stack->head = PREFIX_node_to_axe->next;
  free(PREFIX_node_to_axe);
  return item;
}

ITEMTYPE PREFIX_stack_peek(PREFIX_staq_t *stack) {
  return stack->head->item;
}

void PREFIX_stack_free(PREFIX_staq_t *stack) {
  while (!PREFIX_stack_is_empty(stack)) {
    PREFIX_stack_pop(stack);
  }
}

stack3.h

#ifndef PREFIX_STACK3_H
#define PREFIX_STACK3_H

typedef struct PREFIX_node_t {
  ITEMTYPE item;
  struct PREFIX_node_t *next;
} PREFIX_node_t;

typedef struct {
  PREFIX_node_t *head;
} PREFIX_staq_t;

PREFIX_staq_t *PREFIX_stack_new();
void PREFIX_stack_push(PREFIX_staq_t *stack, ITEMTYPE new_item);
int PREFIX_stack_is_empty(PREFIX_staq_t *stack);
ITEMTYPE PREFIX_stack_pop(PREFIX_staq_t *stack);
ITEMTYPE PREFIX_stack_peek(PREFIX_staq_t *stack);
void PREFIX_stack_free(PREFIX_staq_t *stack);

#endif

makefile

Note to copy and pasters: makefile rules need to be indented with real tabs, not spaces.


int_stack.h: stack3.h
  sed -e 's/ITEMTYPE/int/g' -e 's/PREFIX/int/g' stack3.h > int_stack.h

int_stack.c: stack3.c
  sed -e 's/ITEMTYPE/int/g' -e 's/PREFIX/int/g' stack3.c > int_stack.c

double_stack.h: stack3.h
  sed -e 's/ITEMTYPE/double/g' -e 's/PREFIX/double/g' stack3.h > double_stack.h

double_stack.c: stack3.c
  sed -e 's/ITEMTYPE/double/g' -e 's/PREFIX/double/g' stack3.c > double_stack.c

foo: foo.c int_stack.h int_stack.c
  gcc -o foo $^

Haiku

Their stuff is too good
I feel like I can’t compete
They left me nothing