Pointers
•
A pointer in C holds the memory address of a value
the value of a pointer is an address
the value of the memory location pointed at can be obtained by “dereferencing the pointer” (retrieving the contents of that address)
p pointer
memory location
address
10000 10001 10002 10003 10004 10005 10006
129
77
31542
108
97
542
100652
10004
dereferencing:
*
1
C pointers vs. Java references
C pointers
• a pointer is the address of a memory location
– you have access to that representation (a number)
– the compiler helps you keep track of what it points to
• arithmetic on pointers is allowed, e.g.:
*(p+27)
Java references
•
a reference is an alias for an object
– references have associated type information
arithmetic on references not allowed
•
2
Declaring pointer variables
• Declarations:
a pointer x to something of type T is declared as T *x
Example: int *p; // p: pointer to an int
char **w; // w: pointer to a pointer to a char
3
Using pointer-related operators
• Two new operators (unary, prefix): & : “address of”
* : “dereference”
• If x is a variable, &x is the address of x
• If p is a pointer, *p is the value of whatever points to
• *(&p) ≡ p always
4
Arrays
• An array in C is just a contiguous sequence of memory locations
– size of each element depends on type
– the length of the array is not part of the array type
– the language does not require that array accesses be checked to be within the array bounds
• out-of-bound accesses result in bugs, security flaws (“buffer overflow vulnerabilities”)
5
More arrays
• Consider an array declared as: int A[20];
– the value of A[i] is the contents of the memory location occupied by element i of A;
– the value of A is the address of the array A, i.e., &(A[0]); • this does not have size information associated with it.
6
More arrays
• To pass an array as an argument to a function, you pass the array name
what is actually passed is a pointer to the first element of the array
• This does not have associated size information
the called function does not know how big the array is
you need to provide a mechanism for the called function to determine it:
• either pass the size of the array separately; or • terminate the array with a known value (e.g., 0)
7
Review of pointers introduced for scanf()
• Recall that to read input using scanf(), we provide:
a format string with conversion specifications (%d, %s, etc.)
that says what kind of value is being read in; and
a pointer to (i.e., the address of) a memory area where the value is to be placed
• Reading in an integer: int x;
scanf(“%d”, &x);
• Reading in a string: char str[…];
scanf(“%s”, str);
// &x ≡ address of x
// str ≡ address of the array str
8
Pointer arithmetic (appetizer)
• Suppose p points to an item in an array
• Then p+1 points to the next element
• Also, p++ increments the pointer so when you use it in a subsequent statement it will be pointing to the next one; similarly p– decrements.
9
When 1 is 4 is 8
lec-kob ( ~/teaching/cs352/17/examples ) cat ptr_arithmetic.c #include
int main(void)
{
char cvar;
int ivar;
long lvar;
long val1, val2;
val1 = (long) cptr; val2 = (long) (cptr+1); printf(“char ptr diff is: %ld\n”, val2 – val1);
val1 = (long) iptr; val2 = (long) (iptr+1); printf(“int ptr diff is: %ld\n”, val2 – val1);
val1 = (long) lptr; val2 = (long) (lptr+1); printf(“long ptr diff is: %ld\n”, val2 – val1);
return 0; }
pointers of different types
pointer arithmetic: add 1 to pointers of different types
char* cptr = &cvar;
int* iptr = &ivar;
long* lptr = &lvar;
10
When 1 is 4 is 8 (continued)
%
%
% gcc -Wall ptr_arithmetic.c -o ptr_arithmetic %
% ./ptr_arithmetic
char ptr diff is: 1 int ptr diff is: 4 long ptr diff is: 8
but each pointer was incremented by 1!!!
11
What’s going on
• Pointer arithmetic is performed relative to the size of the pointee type
– for char* pointers, “+= 1” increments by 1
– for int* pointers, “+= 1” increments by 4 (if size of int is 4)
in general, “+= 1” will increment a pointer by the size (in bytes) of the type being pointed at
• analogouslyforotherarithmetic • Reason:portability:
• want code to be able to step through an array of values without worrying about architecture-dependent issues of their size
12
Figuring out sizes: sizeof()
Currently, on lectura, you will get the same answer with just “long,” i.e., we no longer need “long long”
sizeof() invoked with a type name
sizeof() invoked with a variable name
sizeof() invoked with a pointer dereference
13
Figuring out sizes: sizeof()
Currently, on lectura, you will get the same answer with just “long,” i.e., we no longer need “long long”
14
More sizeof()
• sizeof() applied to an array returns the total size of that array
– but be careful about implicit array/pointer conversions
what is passed to f() is a pointer, not the whole array
15
Dereferencing and updating pointers
A common C idiom is to use an expression that
• gives the value of what a pointer is pointing at; and • updates the pointer to point to the next element:
*p++
The inner box evaluates to the value of p which is some address a (side effect: p incremented by ‘++’ afterwards)
parsed as:
* ( p++ )
• similarly: *p–
The entire box evaluates to the contents of location a = *p (side effect: p incremented by ‘++’)
16
*p++ versus *++p
• *p++ and *++p are NOT the same
• *p++ evaluates to where p points to BEFORE it is incremented.
(Dereference first, then increment).
• *++p increments p first, and evaluates to what it points AFTER it is incremented. (Increment, then dereference).
• The above two constructs are also different from additional constructs (*p)++ and ++(*p).
• You should have familiarity with the four syntactic possibilities (eight with “- -”), but you do NOT need to USE all of them. *p++ is very useful, *p– a bit less so, and the others are relatively rare (perhaps sometimes useful?).
19
Walking Ptrs Down Arrays
• Instead of using array indexes we can use pointers to access elements of an array.
• For example, the following statements to the same thing:
a[5] = ‘c’;
*(a + 5) = ‘c’;
• Likewise, these statements to the same thing: x = a[i];
x = *(a + i);
20
Indexs and Pointers
• Recall the program to capitalize the letters in a string we saw in the last slide deck. (It will be on the next slide.)
• We can rewrite that program doing the same thing without using any indexes at all.
21
Program to Change to Upper Case
22
Program to Change to Upper Case (ptrs)
23
Walking a pointer down an array
dereference the pointer to access memory, then increment the pointer
24
Two common pointer problems
• Uninitializedpointers
– the pointer has not been initialized to point to a valid
location
• Danglingpointers
– the pointer points at a memory location that has become obsolete (deallocated)
25
Uninitialized pointers: Example
fix: initialize str
str was never initialized to point to anything
26
Two common pointer problems
• Uninitializedpointers
– the pointer has not been initialized to point to a valid location
• Danglingpointers
– the pointer points at a memory location that has become
obsolete (deallocated)
– two most common cases (on the “stack” or in the “heap”)
27
Background: Runtime Memory Organization
Layout of an executing process’s virtual memory:
0xffffffff
high addresses
operating system
stack (grows downwards)
memory mapped files
heap (grows upwards)
global data
code
0x00000000
low addresses
28
Background: Runtime Memory Organization
Code:
p(…) { …
q(…);
s(…); }
q(…) {
Runtime stack:
p’s caller’s stack frame
stack growth
……
r(…); }
r(…) {
… }
}
s(…) {
top of stack
p’s stack frame
29
Background: Runtime Memory Organization
Code:
p(…) { …
q(…);
s(…); }
q(…) {
Runtime stack:
p’s caller’s stack frame
……
r(…); }
r(…) {
… }
}
p’s stack frame
stack growth
s(…) {
top of stack
30
Background: Runtime Memory Organization
Code:
p(…) { …
q(…);
s(…); }
q(…) { …
r(…);
r(…) {
… }
Runtime stack:
p’s caller’s stack frame
p’s stack frame
q’s stack frame
stack growth
s(…) { …
}
}
top of stack
31
Background: Runtime Memory Organization
Code:
p(…) { …
q(…);
s(…); }
q(…) { …
r(…); }
r(…) {
… }
Runtime stack:
p’s caller’s stack frame
p’s stack frame
q’s stack frame
r’s stack frame
stack growth
s(…) { …
}
top of stack
32
Background: Runtime Memory Organization
Code:
p(…) { …
q(…);
s(…); }
q(…) { …
r(…);
r(…) {
… }
Runtime stack:
p’s caller’s stack frame
p’s stack frame
q’s stack frame
r’s stack frame (deallocated)
s(…) { …
}
stack growth
}
top of stack
33
Background: Runtime Memory Organization
Code:
p(…) { …
q(…);
s(…); }
q(…) {
Runtime stack:
p’s caller’s stack frame
p’s stack frame
q’s stack frame
r’s stack frame
……
r(…); }
r(…) {
… }
}
stack growth
s(…) {
top of stack
34
Background: Runtime Memory Organization
Code:
p(…) { …
q(…);
s(…); }
q(…) { …
r(…); }
r(…) {
… }
Runtime stack:
p’s caller’s stack frame
p’s stack frame
q’s stack frame
s’s stack frame
r’s stack frame
stack growth
s(…) { …
}
top of stack
35
Dangling pointers
What’s wrong with this code?
36
Dangling pointers
What’s wrong with this code?
37
Dangling pointers
What’s wrong with this code?
38
Dangling pointers
What’s wrong with this code?
39
Dangling pointers
What’s wrong with this code?
runtime stack
string
buf
str
main
my_read
read_string
40
Dangling pointers
What’s wrong with this code?
runtime stack
string
main
my_read
read_string
a
buf
c
b
a
str
41
Dangling pointers
What’s wrong with this code?
runtime stack
string
main
my_read
read_string
a
buf
str
c
b
a
42
Dangling pointers
What’s wrong with this code?
runtime stack
string
main
my_read
read_string
a
c
buf
str
b
a
dangling pointer!
43
Avoiding this error
• Never return a pointer to a local variable (e.g., buff in the example).
• You will get a warning for many innocent attempts at doing so.
– Unfortunately, it is possible to make it so that the compiler cannot spot it.
• Notice the example disguised this with an intermediate function so that it is not obvious that this is what is happening from syntax alone.
44
Dynamic memory allocation
• We can’t always anticipate how much memory to allocate
– too little ⇒program doesn’t work – toomuch⇒wastesspace
• Solution: allocate memory at runtime as necessary
– malloc(), calloc()
• allocates memory in the heap area
– free()
• deallocates previously allocated heap memory block
program memory layout
low addr
reserved
code
global variables, strings
heap
stack
reserved
high addr
(Upside down from previous layout figure).
45
Dynamic memory allocation: usage
void * : “generic pointer”
Usage:
int *iptr = malloc(sizeof(int)) char *str = malloc(64)
int *iarr = calloc(40, sizeof(int))
// one int
// an array of 64 chars
// ( sizeof(char) = 1 by definition )
// a 0-initialized array of 40 ints
46
Dynamic memory allocation: example 1
47
Dynamic memory allocation: example 1
ALWAYS check the return value of any system call that may fail
48
Dynamic memory allocation: example 2
49
Dynamic memory allocation: example 2
50
Dynamic memory allocation: example 2
figure out the total size of the concatenated strings
allocate space
concatenate the strings into buf
51
Dynamic memory allocation: example 2
52
Reading a line at a time
• scanf is nice. It parses the input and converts it to integers, floating points, etc.
• Sometimes we want to read a line at a time from the input. scanf is not so great for that.
• Fortunately there are functions that do read in a line at a time from the input. Two of them are:
– getline() – fgets()
53
getline
54
getline
55
getline (code example)
#include
int main(void) {
int block = 1; char* line = NULL; size_t len = 0;
while (getline(&line, &len, stdin) != EOF) {
/* Because we read as many characters as needed (subject to available
* memory), we will generally have a return in line, and so we do not
* want one in the printf().
*/
printf(“Line %03d: %s”, block, line); block++;
}
/*
* When we are done with it, we free line. This will become much more clear * in a few weeks.
*/
free(line);
return 0; }
56
getline
• The nice thing about getline is that it allocates the memory you need for you. You don’t have to worry about the input being to big to fit in the memory you’ve allocated.
• The bad thing about getline is that it is a gnu extension and is not available for all systems. (It is available on most systems including lectura though)
57
fgets
58
fgets
59
fgets (coding example)
#include
int main(void)
{
int block = 1; char buff[ 10 ];
/*
* Unfortunately, fgets() returns NULL both on EOF and on error. We could
* use ferror() and feof() to distinguish these, but for the example we will
* assume that error on read is rare enough for demos.
*/
while (fgets(buff, sizeof(buff), stdin) != NULL) {
/* When we get to ends of lines, we will output an extra return * because fgets() puts the end of line into the buffer.
*/
printf(“Block %03d: %s\n”, block, buff); block++;
}
return 0; }
60
fgets
• The nice thing about fgets() is that it’s a standard c function and should be available on all systems.
• The bad thing is that you have to provide the memory for the function to store the input lines into.
• Notice that one of the parameters to fgets is the maximum number of characters to be read in. (See how this is slightly different than scanf?)
• There is a fprintf() and printf() if I want to just print
to stdout. Likewise there is a fscanf() to read from
any stream and scanf() to just read from stdin. fgets()
lets me read from any stream, can I use gets() when I
just want to read from stdin?
61
gets
62
Don’t use gets()! Even the manual page says not to.
So why is it in the library?
63
Don’t use gets()! Even the manual page says not to.
• The reason for this confusion is that gets() is not simply fgets() with the stream argument set to stdin (the buffer size argument gets dropped).
• This is different from printf/fprintf and scanf/fscanf
• Presumably the lack of consistency reflects historical order of
development.
• Flaws like this are hard to repair because significant code basis might break if you fixed them.
64
Structs
• Astructis
– an aggregate data structure, i.e., a collection of other data;
– can contain components (“fields”) of different types • by contrast, arrays contain components of the same type
– fields are accessed by name
• by contrast, array elements are accessed by position
• Unlike Java classes, a struct can only contain data, not code.
65
Declaring structs
• A node for a linked list of integers:
struct node {
int val;
struct node *next;
}
struct node
val
next
“structure tag” – used to refer to the structure
66
Accessing structure fields
• Given
– a struct s containing a
field f
to access f, we write
s.f Example:
struct foo {
int count, bar[10]; } x, y;
x.count = y.bar[3];
• Given
– a pointer p to a struct s
containing a field f to access f we write
p->f // eqvt. to: (*p).f Example:
struct foo {
int count, bar[10];
} *p, *q;
p->count = q->bar[3];
declares x, y to be variables of type “struct foo”
67
Example: sorting a linked list of strings
declares list_hd as “pointer to something of type struct s”
struct s
points to a string
str
next
points to another list node
68
Example: sorting a linked list of strings
BAD! Should be “%63s”
allocate memory for a list node
amount allocated = size of the struct
(not the pointer to the struct)
69
Example: sorting a linked list of strings
• fill in the fields of the newly allocated struct • add it to the head of the linked list
tmpnode, buf will get deallocated does this cause any problems?
70
Example: sorting a linked list of strings
traverse the list
compare strings by lexicographic ordering
idiomatic C:
“iterate as long as ptr NULL
71
Example: sorting a linked list of strings
input strings sorted output
72
typedefs
• Allow us to define aliases for types
• Syntax:
typedef old_type_name new_type_name;
• new_type_name becomes an alias for old_type_name
• Example:
– typedef int BasePay; – typedef struct node {
int value;
struct node *next; } node;
73
Example
defines “wcnode” as an alias for “struct wc”
we can use “wcnode” in place of“struct wc”
but not here, since “wcnode” has not yet been defined
74
Operator Precedence and Associativity
• Operatorprecedenceandassociativitydefinehowan expression is parsed and evaluated
– The text (King, C Programming: A Modern Approach), Appendix A has a full list of all C operator precedences
• Some highlights: in decreasing order of precedence: – postfix expressions ( [ ] ( ) -> . ++postfix –postfix )
– unary expressions ( ++prefix –prefix & * + – ~ ! sizeof ) – type cast
– arithmetic: multiplicative additive bit-shift
– relational (not all of the same precedence)
– bitwise operators (not all of the same precedence)
75
•
Decreasing order of precedence:
– postfix expressions [ ] ( ) -> . ++post –post
– unary expressions
++pre –pre & *deref + – ~ ! sizeof
– type cast – arithmetic –…
How are these parsed? • *p++
• *p->q
• *A[10]
• *p->q++
Operator Precedence Examples
++ binds tighter than *: *(p++) not: (*p)++
-> binds tighter than *: *(p->q) not: (*p)->q
[ ] binds tighter than *: *(A[10]) not: (*A)[10]
-> and ++ left-associative: *( (p->q) ++ )
76
Operator Precedence — last words
• If you are relatively comfortable with C and still need to consult a manual to make sense of your expression, perhaps you are being too fancy.
• If in doubt, add parentheses.
• If it is hard to read, perhaps break the expression
into pieces.
• Clarity, above all else!
77