CS 330 Lecture 16 – Polymorphism in C, Higher-order Functions
Agenda
- what ?s
- answer this!
- polymorphism in C through unions
- higher-order functions in C
TODO
- Rest.
Answer This!
- 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?
- 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
Void stars are black holes
First they swallow up your types
Your brain is dessert
First they swallow up your types
Your brain is dessert