teaching machines

CS 330 Lecture 15 – Polymorphism in C

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

Agenda

TODO

EZMALLOC

What do these malloc calls look like?

Postfix

for each token
  if token is an operand
    push onto operand stack
  else token is an operator
    pop two operands off stack
    if addition
      push sum
    else if substraction
      push difference
    else if multiply
      push product
    else if divide
      push quotient

pop final answer

Program This

Implement one of the following stack functions—for a linked stack data structure that holds pointers to anything ( void *s).

#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

Code

ezmalloc.h

#ifndef EZMALLOC_H
#define EZMALLOC_H

#include <stdlib.h>

#define EZMALLOC(type, n) (type *) malloc(sizeof(type) * n)

#endif

ezmalloc_test.c

/* #include <stdio.h> */
/* #include <stdlib.h> */

#include "ezmalloc.h"

struct foo_t {
  int a;
};

int main(int argc, char **argv) {
  int *ia = EZMALLOC(int, 100);  
  char **sa = EZMALLOC(char *, 10);  
  struct foo_t *f = EZMALLOC(struct foo_t, 1);  
  return 0;
}

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

stack1.c

#include "ezmalloc.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;
  stack->head = stack->head->next;
  // we've lost the head node
  return popped_item;
}

Haiku

We must be two things
Similar and different
Super and downcast