Page 1

Monday, January 31, 2022
Computer Systems
Winter 2022
Stanford University
Computer Science Department
Reading: Reader: Ch 8,
Pointers, Generic functions
with void *, and Pointers to Functions,
K&R Ch 1.6,
5.6
-
5.9
Lecturer: Chris Gregg
CS 107
Lecture 8: More
Void *: Generic stack
void swap_generic(void *arr, int index_x,
int index_y, int width)
{
char tmp[width];
void *x_loc = (char *)arr + index_x * width;
void *y_loc = (char *)arr + index_y * width;
memmove(tmp, x_loc, width);
memmove(x_loc, y_loc, width);
memmove(y_loc, tmp, width);
}

Page 2

Today's Topics
•

Logistics
•

Midterm next Tuesday. If you have OAE accommodations and haven't yet emailed
them to me (
cgregg@stanford.edu
), please do so ASAP.
•

Go to next week's lab! The material will be on the midterm exam, and you will get
good practice! Thursday labs: if you want to do the lab at a different time, that is
fine (or on your own).
•

Reading: Reader: Ch 8, Pointers, Generic functions with void *, and Pointers to
Functions
•

Lab: winky, change_char, and change_ptr
•

More on Generic pointers, void *
•

The standard library's qsort
•

A generic stack

Page 3

gdb step, next, finish
I've seen a few students who have been frustrated with stepping through functions in gdb.
Sometimes, they will accidentally step into a function like
strlen
or printf
and get stuck.
There are three important gdb commands about stepping through a program:
step
(abbreviation: s) : executes the next line and goes into function calls.
next
(abbreviation: n) : executes the next line, and does not go into function calls. I.e., if you
want to run a line with
strlen
or printf
but don't want to attempt to go into that function,
use
next
.
display
(abbreviation: disp) : displays a variable (or other item) after each step.
finish
(abbreviation: fin) : completes a function and returns to the calling function. This is the
command you want if you accidentally go into a function like
strlen
or printf
! This
continues the program until the end of the function, putting you back into the calling function.

Page 4

gdb step, next, finish : example
$
gdb print_arr
The target architecture is assumed to be i386:x86
-
64
Reading symbols from print_arr...done.
(gdb)
b 35
Breakpoint 1 at 0x400700: file print_arr.c, line 35.
(gdb)
run
Starting program:
/afs/ir/class/cs107/samples/lect8/print_arr
Breakpoint 1, main (argc=1, argv=0x7fffffffea38) at
print_arr.c:35
35
print_array(i_array,i_nelems,sizeof(i_array[0]),print
_int);
(gdb)
n
0, 1, 2, 3, 4, 5
36
print_array(l_array,l_nelems,sizeof(l_array[0]),print
_long);
(gdb)
s
print_array (arr=0x7fffffffe910, nelems=6, width=8,
pr_func=0x400648 <print_long>) at print_arr.c:8
8

for (int i=0; i < nelems; i++) {
(gdb)
s
9

void *element = (char *)arr + i * width;
(gdb)
s
10

pr_func(element);
(gdb)
s
print_long (arr=0x7fffffffe910) at print_arr.c:23
23

long l = *(long *)arr;
(gdb)
s
24

printf("%ld",l);
(gdb)
s
__printf (format=0x4007dc "%ld") at printf.c:28
28

printf.c: No such file or directory.
(gdb)
s
32

in printf.c
(gdb)
n
33

in printf.c
(gdb)
n
32

in printf.c
(gdb)
finish
Run till exit from #0 __printf (format=0x4007dc
"%ld") at printf.c:32
print_long (arr=0x7fffffffe910) at print_arr.c:25
25

}
Value returned is $1 = 1
(gdb)
where
#0 print_long (arr=0x7fffffffe910) at print_arr.c:25
#1 0x00000000004005d8 in print_array
(arr=0x7fffffffe910, nelems=6, width=8,
pr_func=0x400648 <print_long>)
at print_arr.c:10
#2 0x0000000000400734 in main (argc=1,
argv=0x7fffffffea38) at print_arr.c:36

Page 5

Example: qsort with an array of structs
Last time, we saw that we can use qsort to sort any generic array we want, as long
as:
1.

We have an array of some type
2.

We have a function that can compare two elements of that type when passed
two pointers to two of the elements in the array
So, let's try to do this with an array of structs. Let's sort a list of rectangles by their
area, given that each rectangle is defined by its width and height. E.g.,:
typedef struct rect {
int width;
int height;
} rect;

Page 6

Example: qsort with an array of structs
First, let's write a function that can compare two pointers to rect structs:
typedef struct rect {
int width;
int height;
} rect;
int rect_comp_area(const void *r1, const void *r2) {
const rect *r1ptr = r1; // no cast necessary
const rect *r2ptr = r2;
int area1 = r1ptr->width * r1ptr->height;
int area2 = r2ptr->width * r2ptr->height;
return area1 - area2;
}

Page 7

Example: qsort with an array of structs
Next, let's create a bunch of random rectangles in an array:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define NUM_RECTS 100
#define MAX_WIDTH 100
#define MAX_HEIGHT 100
int main(int argc, char **argv)
{
time_t t;
srand((unsigned) time(&t)); // this "seeds" the pseudorandom number generator
// create a rect array
rect rect_arr[NUM_RECTS];
// populate with random rectangles
for (int i = 0; i < NUM_RECTS; i++) {
rect r;
r.width = rand() % MAX_WIDTH; // rand() is a number between 0 and RAND_MAX
r.height = rand() % MAX_HEIGHT;
rect_arr[i] = r; // can copy a struct, all fields copied by value
}

Page 8

Example: qsort with an array of structs
Next, we run qsort, then print the results:
qsort(rect_arr, NUM_RECTS, sizeof(rect), rect_comp_area);
for (int i = 0; i < NUM_RECTS; i++) {
int w = rect_arr[i].width;
int h = rect_arr[i].height;
printf("w: %d, h: %d, area: %d
\
n", w, h, w * h);
}
Output example:
$ ./qsort
-
ex
w: 21, h: 1, area: 21
w: 15, h: 3, area: 45
w: 1, h: 64, area: 64
…
w: 95, h: 80, area: 7600
w: 81, h: 97, area: 7857
w: 99, h: 87, area: 8613

Page 9

Example: qsort with an array of structs
Full code:
// file: qsort
-
ex.c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef struct rect {
int width;
int height;
} rect;
#define NUM_RECTS 100
#define MAX_WIDTH 100
#define MAX_HEIGHT 100
int rect_comp_area(const void *r1, const void *r2) {
const rect *r1ptr = r1;
const rect *r2ptr = r2;
int area1 = r1ptr
-
>width * r1ptr
-
>height;
int area2 = r2ptr
-
>width * r2ptr
-
>height;
return area1
-
area2;
}
int main(int argc, char **argv)
{
time_t t;
srand((unsigned) time(&t));
// create a rect array
rect rect_arr[NUM_RECTS];
// populate with random rectangles
for (int i = 0; i < NUM_RECTS; i++) {
rect r;
r.width = rand() % MAX_WIDTH;
r.height = rand() % MAX_HEIGHT;
rect_arr[i] = r;
}
qsort(rect_arr, NUM_RECTS, sizeof(rect), rect_comp_area);
for (int i = 0; i < NUM_RECTS; i++) {
int w = rect_arr[i].width;
int h = rect_arr[i].height;
printf("w: %d, h: %d, area: %d\n", w, h, w * h);
}
return 0;
}

Page 10

Example: Building a generic stack
Let's build a generic stack. We are going to be using
struct
s extensively for this
example, and they are fair game for the midterm exam. So, make sure you
understand this example!
First, let's remind ourselves what the stack data structure does (back to CS 106B!):
1.

A stack is a last-in-first-out data structure that can store elements. The first
element in the stack is the last element out of the stack.
2.

The
push
operation adds an element onto the stack
3.

The
pop
operation removes an element from the stack.
Note, we are not talking about the program stack, but a generic version of the
stack abstract data type!
Code at: /afs/ir/class/cs107/lecture
-
code/lect8

Page 11

Example: Building a generic stack
Let's build a generic stack. We are going to be using
struct
s extensively for this
example, and they are fair game for the midterm exam. So, make sure you
understand this example!
We'll start by defining a node that will hold a pointer to a "next" node, and some
data:
typedef struct node {
struct node *next;
void *data;
} node;
A note on syntax: We are defining a type
here (thus,
typedef
), and we are defining
a node to be a "
struct node". This is
different from C++, where we can just
define a struct and use its name. In C,
without the typedef, we would constantly
have to be referring to "
struct node
"
every time we wanted to use it. Not fun!

Page 12

Example: Building a generic stack
Let's build a generic stack. We are going to be using
struct
s extensively for this
example, and they are fair game for the midterm exam. So, make sure you
understand this example!
We'll start by defining a node that will hold a pointer to a "next" node, and some
data:
typedef struct node {
struct node *next;
void *data;
} node;
We don't know anything about the type of
thing that
data
will point to, although the
stack itself will know its width.

Page 13

Example: Building a generic stack
Next, let's build the
stack
type. It will have a defined width for each node, and it
will also keep track of how many elements it holds. It will also keep track of the top
of the stack. Again, we want to typedef it so we don't have to continually say
"
struct stack
" when we want to use it.
typedef struct stack {
int width;
int nelems;
node *top;
} stack;
Remember, a node is generic, so this
stack can hold any time, although once it
has a width defined, all elements you push
must have that width.

Page 14

Example: Building a generic stack
How do we create a default stack? We could do it manually:
stack *s = stack_create(...);
But let's create a function for it, in which case we should use a pointer:
stack s1;
s1.width = sizeof(int); // store ints
s1.nelems = 0;
s1.top = NULL;

Page 15

Example: Building a generic stack
Our stack creation function:
Let's investigate...
stack *stack_create(int width)
{
stack *s = malloc(sizeof(stack));
s->width = width;
s->nelems = 0;
s->top = NULL;
return s;
}

Page 16

Example: Building a generic stack
Our stack creation function:
A particular stack
must have a set width
(otherwise, we would
have to pass in the
width each time, and
this doesn't make
sense for
pop
--
we
wouldn't know what
type we were popping
off!)
stack *stack_create(int width)
{
stack *s = malloc(sizeof(stack));
s->width = width;
s->nelems = 0;
s->top = NULL;
return s;
}

Page 17

Example: Building a generic stack
Our stack creation function:
Get enough memory
from the heap to
create the stack.
stack *stack_create(int width)
{
stack *s = malloc(sizeof(stack));
s->width = width;
s->nelems = 0;
s->top = NULL;
return s;
}

Page 18

Example: Building a generic stack
Our stack creation function:
Set the initial
conditions.
stack *stack_create(int width)
{
stack *s = malloc(sizeof(stack));
s->width = width;
s->nelems = 0;
s->top = NULL;
return s;
}

Page 19

Example: Building a generic stack
Our stack creation function:
Return the pointer to
the memory we just
requested and
initialized.
stack *stack_create(int width)
{
stack *s = malloc(sizeof(stack));
s->width = width;
s->nelems = 0;
s->top = NULL;
return s;
}

Page 20

Example: Building a generic stack
Let's look at our
push
function:
void stack_push(stack *s, const void *data)
{
node *new_node = malloc(sizeof(node));
new_node->data = malloc(s->width);
memcpy(new_node->data, data, s->width);
new_node->next = s->top;
s->top = new_node;
s->nelems++;
}

Page 21

Example: Building a generic stack
Let's look at our
push
function:
The stack function takes a stack as a parameter! The stack isn't an object, and it
doesn't have functions built in. If we really wanted to, we could create a stack struct that
has function pointers, but that is more advanced. A pointer to the data is also required.
void stack_push(stack *s, const void *data)
{
node *new_node = malloc(sizeof(node));
new_node->data = malloc(s->width);
memcpy(new_node->data,data,s->width);
new_node->next = s->top;
s->top = new_node;
s->nelems++;
}

Page 22

Example: Building a generic stack
Let's look at our
push
function:
Each time we add an element to the stack, we need to create a
node
, and we get that
off the heap, too.
void stack_push(stack *s, const void *data)
{
node *new_node = malloc(sizeof(node));
new_node->data = malloc(s->width);
memcpy(new_node->data,data,s->width);
new_node->next = s->top;
s->top = new_node;
s->nelems++;
}

Page 23

Example: Building a generic stack
Let's look at our
push
function:
Guess what? We also have to use heap memory to store the data! We are making a
copy of the data, not just pointing to it!
void stack_push(stack *s, const void *data)
{
node *new_node = malloc(sizeof(node));
new_node->data = malloc(s->width);
memcpy(new_node->data,data,s->width);
new_node->next = s->top;
s->top = new_node;
s->nelems++;
}

Page 24

Example: Building a generic stack
Let's look at our
push
function:
We copy the data pointed to into our node. This could be anything, but we know the
width. If it is a pointer, we'll copy the pointer, but it could be integer data, or any other
kind of data.
void stack_push(stack *s, const void *data)
{
node *new_node = malloc(sizeof(node));
new_node->data = malloc(s->width);
memcpy(new_node->data, data, s->width);
new_node->next = s->top;
s->top = new_node;
s->nelems++;
}

Page 25

Example: Building a generic stack
Let's look at our
push
function:
We have to do some wiring here (kind of like linked lists). We are inserting this node
before the top of the stack.
void stack_push(stack *s, const void *data)
{
node *new_node = malloc(sizeof(node));
new_node->data = malloc(s->width);
memcpy(new_node->data, data, s->width);
new_node->next = s->top;
s->top = new_node;
s->nelems++;
}

Page 26

Example: Building a generic stack
Let's look at our
push
function:
Don't forget to update the number of elements.
void stack_push(stack *s, const void *data)
{
node *new_node = malloc(sizeof(node));
new_node->data = malloc(s->width);
memcpy(new_node->data, data, s->width);
new_node->next = s->top;
s->top = new_node;
s->nelems++;
}

Page 27

Example: Building a generic stack
Let's look at our
pop
function. Pop will copy data back into a memory location we
give it, instead of returning a pointer -- this preserves the encapsulation of our data.
bool stack_pop(stack *s, void *addr)
{
if (s
-
>nelems == 0) {
return false;
}
node *n = s
-
>top;
memcpy(addr, n
-
>data, s
-
>width);
// rewire
s-
>top = n
-
>next;
free(n
-
>data);
free(n);
s-
>nelems--
;
return true;
}

Page 28

Example: Building a generic stack
Let's look at our
pop
function. Pop will copy data back into a memory location we
give it, instead of retiring a pointer -- this preserves the encapsulation of our data.
Let's return a boolean value to say
whether or not we had an element to
return. In other words, if the stack is
empty, return
false
; otherwise, return
true
.
bool stack_pop(stack *s, void *addr)
{
if (s
-
>nelems == 0) {
return false;
}
node *n = s
-
>top;
memcpy(addr, n
-
>data, s
-
>width);
// rewire
s-
>top = n
-
>next;
free(n
-
>data);
free(n);
s-
>nelems--
;
return true;
}

Page 29

Example: Building a generic stack
Let's look at our
pop
function. Pop will copy data back into a memory location we
give it, instead of retiring a pointer -- this preserves the encapsulation of our data.
Again,
pop has a stack argument, and a
pointer to a memory location to hold the
data we are going to copy.
bool stack_pop(stack *s, void *addr)
{
if (s
-
>nelems == 0) {
return false;
}
node *n = s
-
>top;
memcpy(addr, n
-
>data, s
-
>width);
// rewire
s-
>top = n
-
>next;
free(n
-
>data);
free(n);
s-
>nelems--
;
return true;
}

Page 30

Example: Building a generic stack
Let's look at our
pop
function. Pop will copy data back into a memory location we
give it, instead of retiring a pointer -- this preserves the encapsulation of our data.
Check to see if the stack is empty.
bool stack_pop(stack *s, void *addr)
{
if (s
-
>nelems == 0) {
return false;
}
node *n = s
-
>top;
memcpy(addr, n
-
>data, s
-
>width);
// rewire
s-
>top = n
-
>next;
free(n
-
>data);
free(n);
s-
>nelems--
;
return true;
}

Page 31

Example: Building a generic stack
Let's look at our
pop
function. Pop will copy data back into a memory location we
give it, instead of retiring a pointer -- this preserves the encapsulation of our data.
Might as well create a temporary pointer
so we don't have to do a bunch of
double "
->
" references.
bool stack_pop(stack *s, void *addr)
{
if (s
-
>nelems == 0) {
return false;
}
node *n = s
-
>top;
memcpy(addr, n
-
>data, s
-
>width);
// rewire
s-
>top = n
-
>next;
free(n
-
>data);
free(n);
s-
>nelems--
;
return true;
}

Page 32

Example: Building a generic stack
Let's look at our
pop
function. Pop will copy data back into a memory location we
give it, instead of retiring a pointer -- this preserves the encapsulation of our data.
We'll copy the data back to the memory
location we were provided.
bool stack_pop(stack *s, void *addr)
{
if (s
-
>nelems == 0) {
return false;
}
node *n = s
-
>top;
memcpy(addr, n
-
>data, s
-
>width);
// rewire
s-
>top = n
-
>next;
free(n
-
>data);
free(n);
s-
>nelems--
;
return true;
}

Page 33

Example: Building a generic stack
Let's look at our
pop
function. Pop will copy data back into a memory location we
give it, instead of retiring a pointer -- this preserves the encapsulation of our data.
Re
-wiring is pretty easy -- the top is now
just the next element in the stack.
bool stack_pop(stack *s, void *addr)
{
if (s
-
>nelems == 0) {
return false;
}
node *n = s
-
>top;
memcpy(addr, n
-
>data, s
-
>width);
// rewire
s-
>top = n
-
>next;
free(n
-
>data);
free(n);
s-
>nelems--
;
return true;
}

Page 34

Example: Building a generic stack
Let's look at our
pop
function. Pop will copy data back into a memory location we
give it, instead of retiring a pointer -- this preserves the encapsulation of our data.
We have to clean up. First, we free the
data (remember, we malloc'd it
originally!)
bool stack_pop(stack *s, void *addr)
{
if (s
-
>nelems == 0) {
return false;
}
node *n = s
-
>top;
memcpy(addr, n
-
>data, s
-
>width);
// rewire
s-
>top = n
-
>next;
free(n
-
>data);
free(n);
s-
>nelems--
;
return true;
}

Page 35

Example: Building a generic stack
Let's look at our
pop
function. Pop will copy data back into a memory location we
give it, instead of retiring a pointer -- this preserves the encapsulation of our data.
Then, we free the node itself (because
we malloc'd it!)
bool stack_pop(stack *s, void *addr)
{
if (s
-
>nelems == 0) {
return false;
}
node *n = s
-
>top;
memcpy(addr, n
-
>data, s
-
>width);
// rewire
s-
>top = n
-
>next;
free(n
-
>data);
free(n);
s-
>nelems--
;
return true;
}

Page 36

Example: Building a generic stack
Let's look at our
pop
function. Pop will copy data back into a memory location we
give it, instead of retiring a pointer -- this preserves the encapsulation of our data.
Don't forget to decrement the number of
elements!
bool stack_pop(stack *s, void *addr)
{
if (s
-
>nelems == 0) {
return false;
}
node *n = s
-
>top;
memcpy(addr, n
-
>data, s
-
>width);
// rewire
s-
>top = n
-
>next;
free(n
-
>data);
free(n);
s-
>nelems--
;
return true;
}

Page 37

Example: Building a generic stack
Let's look at our
pop
function. Pop will copy data back into a memory location we
give it, instead of retiring a pointer -- this preserves the encapsulation of our data.
We did have an element to return, so we
return
true.
bool stack_pop(stack *s, void *addr)
{
if (s
-
>nelems == 0) {
return false;
}
node *n = s
-
>top;
memcpy(addr, n
-
>data, s
-
>width);
// rewire
s-
>top = n
-
>next;
free(n
-
>data);
free(n);
s-
>nelems--
;
return true;
}

Page 38

Example: Building a generic stack
Now we can try it. Let's push on an array of
int
s, and then pop them all off:
int main(int argc, char **argv)
{
// start with an int array
int iarr[] = {0,2,4,6,8,12345678,24680};
int nelems = sizeof(iarr) / sizeof(iarr[0]);
stack *intstack = stack_create(sizeof(iarr[0]));
for (int i=0; i < nelems; i++) {
stack_push(intstack, iarr + i);
}
int popped_int;
while (stack_pop(intstack,&popped_int)) {
printf("%d
\
n",popped_int);
}
free(s); // clean up!
return 0;
}
What is the size of each
element?

Page 39

Page 40

Example: Building a generic stack
Now we can try it. Let's push on an array of
int
s, and then pop them all off:
int main(int argc, char **argv)
{
// start with an int array
int iarr[] = {0,2,4,6,8,12345678,24680};
int nelems = sizeof(iarr) / sizeof(iarr[0]);
stack *intstack = stack_create(sizeof(iarr[0]));
for (int i=0; i < nelems; i++) {
stack_push(intstack, iarr + i);
}
int popped_int;
while (stack_pop(intstack,&popped_int)) {
printf("%d
\
n",popped_int);
}
free(intstack); // clean up!
return 0;
}
$ ./stack
24680
12345678
8
6
4
2
0
7

Page 41

Example: Building a generic stack
Let's try and push one more int onto the stack (assume we do this before the call to
free:
int main(int argc, char **argv)
{
...
int x = 42;
stack_push(intstack, x);
Does this work? Recall:
void stack_push(stack *s, const void *data)

Page 42

Example: Building a generic stack
Does this work? Recall:
void stack_push(stack *s, const void *data)
This does
not
work -- we need a pointer to x. So, we should do:
stack_push(intstack, &x);
Let's try and push one more int onto the stack (assume we do this before the call to
free:
int main(int argc, char **argv)
{
...
int x = 42;
stack_push(intstack, x);

Page 43

Example: Building a generic stack
Let's go ahead and use an array of
char *
pointers -- remember, our stack is generic,
and will work for any pointer! Let's push all the command line args onto the stack:
stack *s = stack_create(sizeof(argv[0]));
for (int i=1; i < argc; i++) {
stack_push(s,argv+i);
}
char *next_arg;
while (stack_pop(s,&next_arg)) {
printf("%s
\
n",next_arg);
}
We're pushing on all but the program name.
What is the size of each
element?

Page 44

Page 45

Page 46

Page 47

Example: Building a generic stack
Can we push on one more string?
...
string *h = "hello";
stack_push(s,h);
This should work, right?
h
is a pointer! Recall:
void stack_push(stack *s, const void *data)
This doesn't work!
We need a pointer to the memory we are pushing onto the
stack. We aren't pushing string characters, we are pushing a string pointer!
So,
we need:
stack_push(s,&h); // &h is a char **

Page 48

References and Advanced Reading
•
References:
•
K&R C Programming (from our course)
•
Course Reader, C Primer
•Awesome C book:
http://books.goalkicker.com/CBook
•
Function Pointer tutorial: https://www.cprogramming.com/tutorial/function-
pointers.html
•
Advanced Reading:
•
virtual memory:
https://en.wikipedia.org/wiki/Virtual_memory

Page 49

Extra Slides