teaching machines

CS 330 Lecture 16 – Polymorphism in C, Higher-order Functions

February 27, 2013 by Chris Johnson. Filed under cs330, lectures, spring 2013.

Agenda

• what ?s
• answer this!
• polymorphism in C through unions
• higher-order functions in C

TODO

• Rest.

Answer This!

1. A board was sawed into two pieces. One piece was two-thirds as long as the whole board—and was exceeded in length by the second piece by four feet. How long was the board before it was cut?
2. What’s the capital of West Virginia?

Code

makefile

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

CFLAGS = -std=c99 -g

all: 

stack.o: stack.c stack.h
  gcc $(CFLAGS) -c stack.c

names: stack.o names.c
  gcc $(CFLAGS) -o names names.c stack.o

sorters: sorters.c
  gcc $(CFLAGS) -o sorters sorters.c

clean:
  rm -f *.o ./a.out names

stack.h

#ifndef STACK_H
#define STACK_H

union item_t {
  int i;
  char c;
  char *s;
  float f;
  void *p;
};

typedef union item_t item_t;

struct stack_t {
  int size;
  int capacity;
  item_t *items;
};

typedef struct stack_t stack_t;

stack_t *make_stack(int capacity);
void stack_push(stack_t *stack, item_t item);
item_t stack_pop(stack_t *stack);
void stack_free(stack_t *stack);

#endif

stack.c

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

#include "stack.h"

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

stack_t *make_stack(int capacity) {
  stack_t *stack = EZMALLOC(stack_t, 1);  
  stack->size = 0;
  stack->capacity = capacity;
  stack->items = EZMALLOC(item_t, stack->capacity);
}

void stack_push(stack_t *stack, item_t item) {
  if (stack->size >= stack->capacity) {
    fprintf(stderr, "Stack full, you foo bag.\n");
    exit(1);
  }

  stack->items[stack->size] = item;
  ++stack->size;
}

item_t stack_pop(stack_t *stack) {
  if (stack->size == 0) {
    fprintf(stderr, "Stack empty, you foo bag.\n");
    exit(1);
  }

  item_t item = stack->items[stack->size - 1];
  --stack->size;
  return item;
}

void stack_free(stack_t *stack) {
  free(stack->items);
  free(stack);
}

names.c

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#include "stack.h"

int main(int argc, char **argv) {
  int n = 5;
  srand(time(NULL));

  stack_t *stack = make_stack(30); 

  item_t entry;

  /* entry.i = 67; */
  /* stack_push(stack, entry); */

  entry.s = "Matthew";
  stack_push(stack, entry);

  entry.s = "Thomas";
  stack_push(stack, entry);

  entry.s = "Jake";
  stack_push(stack, entry);

  entry.s = "Christian";
  stack_push(stack, entry);

  entry.s = "Taylor";
  stack_push(stack, entry);

  for (int i = 0; i < n; ++i) {
    item_t item = stack_pop(stack);
    if (rand() % 4 == 0) {
      printf("item: %s\n", item.s);
    }
  }

  stack_free(stack);

  return 0;
}

sorters.c

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

int smallest_from(void *list,
                  int nitems,
                  int nbytes_per_element,
                  int starting_index,
                  int (*compare)(const void *a, const void *b)) {
  // Let's guess the first element to be the smallest.
  int smallest_so_far = starting_index;

  // Now let's try to oust it.
  for (int i = smallest_so_far + 1; i < nitems; ++i) {

    // We can't index away from a void *. We've got to pointer
    // arithmetic, manually offsetting by some number of bytes.
    void *candidate = list + smallest_so_far * nbytes_per_element;
    void *ouster = list + i * nbytes_per_element;

    // If candidate is bigger, pick ouster as the minimum.
    if (compare(candidate, ouster) > 0) {
      smallest_so_far = i;
    }
  }

  return smallest_so_far;
}

/*
 Exchange the nbytes pointed to by a with the nbytes pointed to by b, using the
 memory pointed to by tmp as intermediate storage.
 */
void swap(void *a,
          void *b,
          void *tmp,
          int nbytes) {
  memcpy(tmp, a, nbytes);
  memcpy(a, b, nbytes);
  memcpy(b, tmp, nbytes);
}

void sort(void *list,
          int nitems,
          int nbytes_per_element,
          int (*compare)(const void *a, const void *b)) {
  // Make some temporary storage so that we can swap elements.
  char *tmp = (char *) malloc(sizeof(char) * nbytes_per_element);

  // Go through each cell in the array and find the element that belongs there.
  for (int i = 0; i < nitems; ++i) {
    int i_smallest = smallest_from(list, nitems, nbytes_per_element, i, compare);
    swap(list + i * nbytes_per_element, list + i_smallest * nbytes_per_element, tmp, nbytes_per_element);
  }

  free(tmp);
}

int int_compare(const void *a,
                const void *b) {
  int value_a = *((int *) a); 
  int value_b = *((int *) b); 

  return value_a - value_b;
}

int main(int argc, char **argv) {

  int n = 7;
  int nums[] = {
    5, -37, 8, 4, 10, 1001, 42
  }; 

  for (int i = 0; i < n; ++i) {
    printf("smallest_from(list, %d, sizeof(int), %d, int_compare): %d\n", n, i, smallest_from(nums, n, sizeof(int), i, int_compare));
  }

  sort(nums, n, sizeof(int), int_compare);

  for (int i = 0; i < n; ++i) {
    printf("nums[%d]; %d\n", i, nums[i]);
  }

  return 0;
}

Haiku