Pointers
COP-3223H
Table of Contents
What are pointers
A pointer is a variable that stores a memory address
Desktop calculator model
- Memory address are numbers
Remember how goto works.
Recall how memory is contiguous. Instructions are stored in memorylocations that are numbered sequentially. This is true for data as well.
Diagram
- Variables are named memory locations
- Memory locations always store numbers
- Data types define how the number is used
Diagram
- Two variables
- Numbered memory, address
- Contents, numbers
- One number is the address of the other variable
Data types
Recall: data types are defined by how they are used
Integers and characters are both numbers.
- Integers are used with integer operations.
- Characters are used with printing
Pointer data type
Asterisk (*) after the data type means pointer
int *x; // x holds an address int y;
The int means that the data at the address is integer data (not the pointer's data type itself, which is always just an address number).
Pointer operators: how they are used
Three basic operations
x = &yReference a variable's addressz = *xDereference a pointer*x = 1Assign to a dereference pointer
Reference means the address of a variable, another term for pointer
Dereference means follow the pointer
Get a variable's address
x = &y;
x now holds the address that y names
Diagram
Dereference a pointer
z = *x;
*x get the value at the address stored in x, not the value of x itself, which is a memory address.
Assign to a dereference pointer
*x = 1;
v#+begin_notes
*x here assigns to the address that x points to. It doesn't assign to x's address itself.
#+end_notes
x has its own address too
What's confusing about pointers is that if x is a pointer, x holds the address of a memory location, but x itself also names a memory address.
Diagram
int *x; int y; x = &y;
xandyname two different memory locations (which are numbered in the machine)&ygets the address thatynamesx = &yassigns that address tox
Full example
int *x;
int y;
int z;
y = 9;
x = &y;
y = 10;
z = *x;
printf("z is %d\n", z);
y = 8;
x = &y;
*x = 10;
printf("y is %d\n", y);
Passing pointers to functions
Passing values
- Recall that functions have their own variables
int g(int x) {
x = x + 1;
return x;
}
int main(int argc, char **argv) {
int x = 1;
g(x);
printf("%d\n", x);
}
The program prints 1, because the addition to x only happens to the x allocated for g.
Passing pointer values instead
// now g takes a pointer instead
int g(int *x_ptr) {
// increment the integer value that x_ptr points to
*x_ptr = *x_ptr + 1;
return x;
}
int main(int argc, char **argv) {
int x = 1;
int *x_ptr = &x; // get x's address
g(x_ptr); // pass x's address
printf("%d\n", x);
}
Diagram.
Passing pointer values instead
x_ptr itself is different variable in each function
int g(int *x_ptr) {
*x_ptr = *x_ptr + 1;
int y;
x_ptr = &y;
printf("%p\n", x_ptr);
return x;
}
int main(int argc, char **argv) {
int x = 1;
int *x_ptr = &x;
g(x_ptr);
printf("%p\n", x_ptr);
printf("%d\n", x);
}
Reassigning x_ptr's value in g does not affect x_ptr in main.
Diagram.
This is what the use of scanf does. scanf takes a pointer and we pass that via &x.
Automatically passing the pointer
// use the ampersand to make it pass by reference
int g(int &x) {
}
Arrays variables are pointers
#include <stdio.h>
void g(int a[3]) {
a[0] = 1;
a[1] = 2;
}
int main(int argc, char **argv) {
char arr[3];
for (int i = 0; i < 3; i++) {
arr[i] = 3;
}
for (int i = 0; i < 3; i++) {
printf("%d\n", arr[i]);
}
}
Diagram
Array indices are pointer derefences:
- a[0] = *(a + 0)
- a[1] = *(a + 1)
- a[2] = *(a + 2)
C handles size of data types for you
Dynamic memory allocation
"Dynamic" - while the program is running
Default function behavior: automatic memory allocation
x's memory is automatically allocated and deallocated on each function call.
int g() {
int x;
}
Recall that this is why recursion works: each call to the function gets its own memory allocation.
There's a bit more to memory management not described here. The program requests memory from the operating system (sbrk), and the programming language system tracks which parts of this memory are being used (malloc for the heap and auto for the stack).
Allocating memory manually
| Function | Description |
|---|---|
malloc |
Requests a chunk of memory |
free |
Returns a chunk of memory |
Memory is finite. malloc keeps track of what memory has been requested by the program. free returns this memory for later use by the program.
Technically malloc can fail if the program is out of memory, e.g., exceeding the limit for a program. We can check this by seeing whether the output is 0 (NULL).
Using malloc
malloc takes as input the number of memory slots requested
Diagram.
- Different numbers request different sequences of memory.
- Memory is always contiguous
- Does this look familiar? Like arrays
Example call
#include <stdio.h>
#include <malloc.h>
int g() {
int *x_ptr;
// request 10 bytes
x_ptr = malloc(10);
}
int main(int argc, char **argv) {
g();
}
What happens when the function ends?
Memory leak. If we have a loop, memory keeps getting requested indefinitely. We eventually run out of memory.
Using free
#include <stdio.h>
#include <stdint.h>
#include <malloc.h>
int g() {
int *x_ptr;
// request 10 bytes
x_ptr = malloc(0xFFFFFFFF);
if (0 == x_ptr) {
printf("malloc failed\n");
} else {
printf("malloc succeeded\n");
}
free(x_ptr);
}
int main(int argc, char **argv) {
while (1) {
g();
}
}
Using malloc and free
sizeof: getting the size of a datatype
sizeof(int)
Storing the pointer
int ptr = malloc(sizeof(int));
Using the pointer
Same as pointer operations we've seen
*ptr = 10;
printf("%d\n", *ptr);
Freeing the pointer
free(ptr);
Full example
#include <stdio.h>
#include <malloc.h>
int main(int argc, char **argv) {
int *ptr = malloc(sizeof(int));
printf("ptr = %p\n", ptr);
*ptr = 10;
printf("*ptr = %d\n", *ptr);
int *xyz;
xyz = ptr;
printf("*xyz = %d\n", *xyz);
*xyz = 11;
printf("*ptr = %d\n", *ptr);
printf("*xyz = %d\n", *xyz);
}
Diagram memory
sizeof works for structs
struct player {
int x;
int y;
};
int main() {
struct player *ptr = sizeof(struct player);
}
Accessing struct fields via a pointer
There are two equivalent ways to access the struct field via a pointer
struct player {
int x;
int y;
};
int main() {
struct player *ptr = sizeof(struct player);
(*ptr).x; // dereference first, then access the field
ptr->x; // -> is syntactic sugar for dereference then access the field
}
Linked lists
struct list {
int data;
struct list *next;
};
Diagram
We can "link" the list structures in memory.
Each struct points to another list struct
What is the end of the list?
NULL or 0 means "empty" pointer
Tony Hoare's billion-dollar mistake
I call it my billion-dollar mistake. It was the invention of the null reference in 1965. At that time, I was designing the first comprehensive type system for references in an object oriented language (ALGOL W). My goal was to ensure that all use of references should be absolutely safe, with checking performed automatically by the compiler. But I couldn't resist the temptation to put in a null reference, simply because it was so easy to implement. This has led to innumerable errors, vulnerabilities, and system crashes, which have probably caused a billion dollars of pain and damage in the last forty years. In recent years, a number of program analysers like PREfix and PREfast in Microsoft have been used to check references, and give warnings if there is a risk they may be non-null. More recent programming languages like Spec# have introduced declarations for non-null references. This is the solution, which I rejected in 1965.
Creating one link
struct list *newlink; newlink = malloc(sizeof(struct list));
Initializing it
newlink->data = 1; newlink->next = NULL; // points to nothing
Connecting the links
struct list *newlink; newlink = malloc(sizeof(struct list)); newlink->data = 1; newlink->next = NULL; // points to nothing struct list *another; another = malloc(sizeof(struct list)); another->data = 2; another->next = newlink; // points to new link
Diagram
What does memory look like?
Which link is "first"?