3101-1-lec5

CS3101-1 Programming Languages – C Lecture 5 Matthew P. Johnson Columbia University Fall 2003 10/17/08

CS3101-1, Lecture 5

1

Important Reminder Do not let me fail to repeat Qs Remind me if I forget  Win valuable prizes

10/17/08

CS3101-1, Lecture 5

2

Agenda Hw3 due last night Hw4 assigned tonight Last time: arrays & ptrs This time: More on ptrs Structures

• • – – – –

• • • • • 10/17/08

Not objects! Struct ptrs, struct params Self-ref structs More mallac, casting

Typedef Unions & Bitfields More I/O Var-length args Final exam CS3101-1, Lecture 5

3

Multi-D arrays as ftn args Any dims after the first (0th) must be specified: – int ftn(int days[2][12]) { … }  – int ftn(int days[][12]) { … }  – int ftn(int (*days)[12]) { … }

Remember: pass int days[2][12]  receive int(*days)[12] Q: Why do others need to be specified? Q: Why needn’t the first? A: 2 in days[2] ignored, so days[] is equiv to *days – passing array same as passing ptr

So: passing a ptr—to what? – Passing a ptr to int[12]’s

Remember: referent type tells ptr the number of bytes that compose its referent 10/17/08

CS3101-1, Lecture 5

4

Array-of-ptrs v. 2-dim arrays Almost the same but not quite int a[10][20];

– 10x20 2-dim array  10*20 == 200 ints – each row same length – a[1][6]  (a[1])[6]  *(a[1]+6)  *(*(a+1) + 6)  *(*a + 1*20 +6)  *(*a + 26) – In each addition, offset has implicit coeff of sizeof(type) • sizeof(int) == 4, sizeof(int[20]) == 4*20

– why we need the length of the rows! – See twodim.c

int *b[10];

– No ints created, but 10 int *s created – Each can be set to point to an int[20] (~ a row) – Or could be set to diff length arrays

10/17/08

CS3101-1, Lecture 5

5

Array-of-ptrs v. 2-dim arrays Also, we wrote: – int (*days)[12] as the same as int days[2][12] • A ptr to length-12 int arrays

– int *b[10]; the ptr analog of int a[10][20] • 10 int ptrs

Q: Why not *b[20]? A: These look analogous, but are not int (*days)[12] is one ptr, a ptr that points to a length-12 int array int *b[10] is 10 ptrs, each of which points to int(s) – Interped as a table, this gives a 10x? table

we had a 10x20 table ~ 10 rows  10 ptrs to ints 10/17/08

CS3101-1, Lecture 5

6

Array-of-ptrs v. 2-dim arrays Diff between int (*d)[10] and int *d[10]? [] have higher precedence than * In second, [10] attaches to d, then * to result  array of int-ptrs In first, * attaches to d, then [10] to result  ptr to int-array(s) Just remember: [], () bind tighter than * 10/17/08

CS3101-1, Lecture 5

7

* v. () You should know diff bet int *f() and int (*pf)() (without helpful names) Be careful with *’s and []’s/()’s Q: What does the following mean? – char (*(*x())[])()

A: left as an exercise for the listener

10/17/08

CS3101-1, Lecture 5

8

Array-of-strs v. 2-D char arrs char *names[] = {“Abc”, “d”, “efgh”}; – names array of char*, each pts to just-largeenough string ({‘A’,’b’,’c’,’\0’})

char names[][5] = {“Abc”, “d”, “efgh”}; – len-15 array, with empty space between entries: – Abc\0 d\0 efgh\0 10/17/08

CS3101-1, Lecture 5

9

Command-line args  main ftn params Canonical main ftn: – int main(int argc, char *argv[]) { … }

Looks like Java’s main method – OO – public static void main(String[] args) {…}

argv: array of strings argv[0] = … exec name! Other elms: cmd-line args, in order type Args sep-ed by spaces To include space in string, surround by quotes

10/17/08

CS3101-1, Lecture 5

10

Command-line args Q: What is **++argv? A:  **(++argv)  **(argv+1)  *argv[1]  argv[1][0]  char 0 of arg 1 Q: What is *++argv[0]? A:  something of arg 0  something of char 1 of arg 0  val of char 1 of arg 0 Q: What is (*++argv)[0]? A:  0th of *(argv+1)  0th of arg 1  char 0 of arg 1  **++argv 10/17/08

CS3101-1, Lecture 5

11

Ftn pointers Ftns aren’t values; vars can’t be set to them But: ptrs can point to them!  Can pass one ftn to another, so second can call first! Ftn name simpliciter (no parens) evals to ptr to the ftn To call, dereference ftn, in parens, followed by args: – res = (*cmp)(pa, pb);

Dereferencing ftn ptr is actually not required, but reminds us that cmp is a ptr

10/17/08

CS3101-1, Lecture 5

12

Ftn pointers Example: qsort – Sorts according to some ordering of items – Ordering specified by implementation of cmp ftn – How does qsort find out which cmp to call?

Cmp (or a ptr to it) is passed to qsort as a param NB: type depends on param-list types and return type Show ftnptrs.c

10/17/08

CS3101-1, Lecture 5

13

Proper main ftns int main(int argc, char argv[][]) { … return 0; } NB: Ftn signature is similar to Java equiv, minus OO: public static void main(String[] args) {…} Since arrays don’t “know” their length, this info is sent separately: – argc ~ argument count – argv ~ argument vector

Also, argv[0] is always the exec name (e.g., “a.out”) 10/17/08

CS3101-1, Lecture 5

14

Meta-pointers Given any type, exists ptr to type: int  int* char  char* int*  int** “ptr to a ptr to an int” Ever used? Yes! -qsort 10/17/08

CS3101-1, Lecture 5

15

Pointer op review Q: suppose say: int x = 10; int *ip = &x; int **ipp = &ip;  **ipp = ? A: 10 Q: suppose say: int *ip; int **ipp = &ip; /* ! */ int x = 10; ip = &x; Any problem, since ip is not initiated? A: No, ip not set, but it has mem reserved for it - picture

10/17/08

CS3101-1, Lecture 5

16

Pointer op review Q: suppose say: int *ip; *ip = 10; Any problem? A: Yes! ip not set  *ip == who knows? Q: suppose say: int *ftn() { int x = 10; return &x; } Any problem? A: Yes! X is popped off stack on return – “dangling pointer”

10/17/08

CS3101-1, Lecture 5

17

Structures Primary sort of user-defined complex data type type: inst composed of arb set of other vars – Perhaps contains other structs (usually w/ptrs) – No order – Multiple data types

Intuitions: – struct = a record containing fields/DB row – struct = Java object - methods

10/17/08

CS3101-1, Lecture 5

18

struct example: Point Declare a struct to represent a point in the plane: struct Point { int x; int y; } Now can create Point vars: struct Point pt; NB: type of pt is struct Point, not simply Point – As with enum types – Point is called the struct tag

10/17/08

CS3101-1, Lecture 5

19

struct example: Point Can access struct members with dot op: struct-name.mem pt.x = 10; Can also do static init: struct Point pt = {10, 10};

10/17/08

CS3101-1, Lecture 5

20

structs Notice: no pointers here (yet)  declaration of struct obtains mem for all elms – Like def/declar of prims, arrays

10/17/08

CS3101-1, Lecture 5

21

Nested structs Structs can be nested (structs within structs): struct Rect { struct Point lowerleft; struct Point upperright; } struct Rect screen; screen.lowerleft.x = 5; … picture 10/17/08

CS3101-1, Lecture 5

22

Struct ops Field access: . Address-of: & Assignment: = – Values of all struct members (recursively) constitute val of struct – s1 = s2;  all fields of s1 set to vals in s2 – Unlike arrays! – Of course, can only assign between same struct types 10/17/08

CS3101-1, Lecture 5

23

struct = op struct Point pt1 = {5,10}, p2 = {30,40}; pt2 = pt1; pt2.x = 13;  pt1.x == ?  == 5 We have 4 distinct ints in mem Changing one does not affect the other 10/17/08

CS3101-1, Lecture 5

24

C structs v. Java objs In Java, all objs are implicitly pass-by-ref – Not the case for C structs!

Also, no concept of public/private struct mems – Everything is public-access – Concept of inside not even applicable • No methods in structs, just data

NB: passing structures would be much more work (=slower) w/o pointers 10/17/08

CS3101-1, Lecture 5

25

structs as params, return vals Suppose want to add two points – Intuition: add x’s, add y’s

Would be nice to say: – pt3 = pt1 + pt2 – Programmatic op overloading – Can’t in C– see 3101-2

Next best: use a function – Take two pt params – Return a pt 10/17/08

CS3101-1, Lecture 5

26

Add pts struct Point addpt(struct Point p1, struct Point p2) {

stuct Point sum; sum.x = p1.x + p2.x; sum.y = p1.y + p2.y; return sum; } Can we do better? 10/17/08

CS3101-1, Lecture 5

27

Add pts’ Yes: struct params are passed-by-val  we can modify them struct Point addpt(struct Point p1, struct Point p2) { p1.x += p2.x; p1.y += p2.y; return p1; } No extra var

10/17/08

CS3101-1, Lecture 5

28

Struct ptrs Ptrs can point to any var type Declare struct ptrs thus: struct Point *pp; *pp is a struct Point can apply dot op Dot op has (naturally) high prec.: – – – –

10/17/08

pt.x + 5  (pt.x) + 5 But not quite high enough: *pp.x  *(pp.x)   Dot higher than *  need parens

CS3101-1, Lecture 5

29

Shortcut op  *pp.x  *(pp.x)  (*pp).x  ppx  works , dot have same precedence Assocs L-to-R: r.lowerleft.x  (r.lowerleft).x rplowerleft.x  (rplowerleft).x Q: ++ppx  what? A:  has highest prec  ++(ppx) (), [], .,  have highest precedence – See table on page 52 10/17/08

CS3101-1, Lecture 5

30

Static inits Can combine array static inits and struct static inits: struct Point pts[] = { {10, 20}, {30, 40} };

Shorter: struct Point pts[] = {10, 20, 30, 40}; – Braces around rows optional 10/17/08

CS3101-1, Lecture 5

31

sizeof structs sizeof applies to arrays: For any locally defined array, sizeof(ar) == sizeof(ar[0])*len == sizeof(elm type)*len  len == sizeof(ar) / sizeof(ar[0]) For pointers or array params (same thing), length is unkown

10/17/08

CS3101-1, Lecture 5

32

sizeof structs sizeof applies to structs: sizeof pt sizeof (struct Point) Gives actual #bytes needed to store the struct – May be more than just sum of field sizes – Implementation reasons

10/17/08

CS3101-1, Lecture 5

33

sizeof structs Consider: struct S { int i; char c; } May turn out: sizeof (struct S) == 8 == 4+4  sizeof sAr == 8*len 10/17/08

CS3101-1, Lecture 5

34

Self-ref structs Claimed: when struct var defined, all mems defined What about self-referential data structures: linked lists, trees, etc. struct Listnode { int val; struct Listnode next; } Define var: struct Listnode first; In mem, we autoly create 1) an int and 2) a Listnode  1) an int and 2) a) an int and b) a Listnode  off to the races Any instance, fully expanded, is infinite 10/17/08

CS3101-1, Lecture 5

35

Self-ref structs Soln: next is not a struct, but a ptr: struct Listnode { int val; struct Listnode *next; } Now define var: struct Listnode head; In mem, we autoly create 1) an int and 2) a ptr – That’s all! 10/17/08

CS3101-1, Lecture 5

36

Self-ref structs To expand: – Create another node with malloc – Set prev node’s next value to address of new – Always set new next value to null

Traversal is straight-forward: struct Listnode *curr; for (curr = head; curr != NULL; curr = currnext) { … } 10/17/08

CS3101-1, Lecture 5

37

Self-ref structs struct Listnode* addnewnode(struct Listnode* curr, int i) { struct Listnode *node = (struct Listnode*) malloc(sizeof(struct Listnode)); nodei = i; currnext = node; return node; }

10/17/08

CS3101-1, Lecture 5

38

Casting ptrs NB: we cast result from malloc – Its type is void*, the generic ptr

What happens when we cast a ptr? Is its referent affected? No Remember: int* is a var that is a ptr (to an int); void* is a var that is a ptr (to something) So: casting a ptr changes how much mem is interped as its referent – But not the referent itself 10/17/08

CS3101-1, Lecture 5

39

Casting ptr example int x = 1025; int *ip = &x; int *cp = (char*)ip; Q: What do we get if we read four bytes as four chars? A: 0, 0, 4, 1 == 2563 + 2562 + 4*2561 + 1*2560 ~ “byte-string” representation 10/17/08

CS3101-1, Lecture 5

40

malloc example Goal: duplicate string char *strdup(char *s) { char *p = (char*)malloc(strlen(s)+1);

if (p != NULL) strcpy(p,s); return p; } 10/17/08

CS3101-1, Lecture 5

41

malloc example NB: strlen doesn’t include ‘\0’ –

Add 1 to get in-mem size

Used strcpy –

One of ftns in string.h

Others: 1. strncpy(s,t,n) • •

At most n chars Assumes s ref has enough room

2. strcmp(s,t) • • • 10/17/08

-1 ~ s < t 0 ~ s == t +1 ~ s > t CS3101-1, Lecture 5

42

string.h ftns – 3. strcat(s,t) • Concantation to to end of s

– 4. strncat(s,t,n) • <=n chars of t

– 5. strchr(s,c) • Ptr to first appearance of c in s

– 6. strrchr(s,c) • Ptr to last appearance of c in s

10/17/08

CS3101-1, Lecture 5

43

Dynamic memory malloc allocates memory dynamically – As opposed to regular var definition – Local vars are “automatic” • pushed, popped to stack

malloc-ed mem stays on heap until freed – Some langs have “garbage collection” – not C

Main dynamic memory ftns (stdlib.h): – void *malloc(int size) • If none available returns NULL • Memory is not initilialized!

– void free (void *p) 10/17/08

CS3101-1, Lecture 5

44

Dynamic memory example Suppose want 53 Ball objects Can do: – Ball[53] theballs;

Suppose want n Ball objects, with n user-specified Q: Will this work: – Ball[n] theballs;

A: No! array-size must be constant/Known at compile time Soln: obtain memory dynamically – Ball* theballs = (Ball*)malloc(n*sizeof(Ball)); – if (theballs != NULL) … – free(theballs); 10/17/08

CS3101-1, Lecture 5

45

Dynamic memory dangers •

•

“dangling pointers” – free(p); … *p = 10; – Mem at address p may be reclaimed – Don’t try to read/write there – Soln: – free(p); p = NULL;

Memory leaks – – – – –

10/17/08

p = NULL; We’re done with the mem at address p But we forgot where it is! – that much less mem now Soln: free(p); p = NULL; CS3101-1, Lecture 5

46

Dynamic memory dangers Generalization: When finished with dynamic mem, always 1. Free it 2. Reset ptr to null

Q: Why doesn’t free automatically reset p to null? A: p is passed by value! Q: Any other possible soln? A: Yes, pass meta-pointer (but C doesn’t do this) 10/17/08

CS3101-1, Lecture 5

47

Dynamic memory Freeing is done in “reverse” order: Suppose have two listnodes: – node1next == node2

To free both: – free(node1next); – free(node1);

Q: What if freed node1 first? A: Not allowed to access node1next afterward – Of course, can still free node2 if we have a separate ptr

10/17/08

CS3101-1, Lecture 5

48

typedef Used to “define” new types “Really”, merely creates synonym for existing type Examples: 1. typedef int Length;  can declare ints with “Length”: Length x = 10; 2. typedef char * String; String s = “hi”; 10/17/08

CS3101-1, Lecture 5

49

typedef examples 3. typedef struct Listnode Node; struct Listnode n  Node n;

4. typedef double (*DDFtn) (double); DDFtn ftn = sin;

10/17/08

CS3101-1, Lecture 5

50

typedef benefits Replace long type constructions with simple names Part of C, not CPP – (simple) typedefs could be done with CPP

Give semantic meaning to types – Suppose want all Length vars to change from short to long – But other shorts should stay shorts  just change def of Length! 10/17/08

CS3101-1, Lecture 5

51

Unions Fairly rarely used; should be aware of Idea: declare var can take on one val of mult types – Switch between

Syntax similar to that of structs: union utag { int i; double d; char *s; } un; un.i = 3; un.f = 3.5; Retains only most recently set val 10/17/08

CS3101-1, Lecture 5

52

Accessing unions How does it remember which “field” you most recently set? It doesn’t – access the right one: – un.i, un.f, upi

Size of union is size of largest elm Other construals: – un = struct that has only 1 elm at a time – un = struct s.t. all mems have offset 0 10/17/08

CS3101-1, Lecture 5

53

Bitfields Also infrequently used – Here we use unsigneds

struct { unsigned int a : 1; unsigned int b : 2; unsigned int c : 1; } bits; Bitfields get machine-dependent and messy Usually bit masks are better choice if (att & (HIDDEN | SYSTEM)) … 10/17/08

CS3101-1, Lecture 5

54

I/O We’ve used I/O streams – stdin ~ from keyboard – stdout ~ to screen – stderr ~ to screen, for errors

Can redirect to, from: $ a.out < in.txt > out.txt Can also pipe from one exec to another: $ progA | progB – A’s output sent to B as input

Done this before? Yes! $ ls | more 10/17/08

CS3101-1, Lecture 5

55

I/O ftns Simplest I/O ftns: – getchar() – putchar(c)

More sophisticated: – scanf – printf

Saw most important conv wildcards Others: – printf(“%.*s”, max, s); ~ at most max chars of s – scanf(“1s”, &s); ~ gives ptr to first nonwhitepace char 10/17/08

CS3101-1, Lecture 5

56

File access Know how to access files by redirection: <, > Can also do so programmatically FILE *fopen(char *name, char *mode); – Nodes: “r”, “w”, “a” – Returns file ptr or NULL if failed

int fclose(fp); 10/17/08

CS3101-1, Lecture 5

57

File access Most I/O routines have file-spec analogs: int getc(fp); int putc(c, fp); – NB: diff names because no function overloading

int fputs(s, fp); char *fgets(s, fp); int fscanf(fp, format, …); int fprintf(fp, format, …); Passing stdin/stdout reduces to calling the regular routines 10/17/08

CS3101-1, Lecture 5

58

Low-level I/O All I/O routines discussed so far are high-level (!) Rely on lower-level routines On Unix, these are system calls like: – read(fd, buf, n); – write(fd, buf, n);

n chosen from: – 0 ~ stdin – 1 ~ stdout – 2 ~ stderr

How to open file? – Fd = creat(name, parms); /* no ‘e’ in creat */ – Unlink(name); – Lseek(fd, offset, origin) …

See course in OS’s 10/17/08

CS3101-1, Lecture 5

59

Error-handling Built-in error stream: strerr

– Also goes to screen – Redirected indly – machine/shell-dependent?

Should return success val from main – 0 ~ success – !0 ~ error

Can also exit with success val from elsewhere: – exit(0);

Can also assert what should be true: – assert(a > 0); – If expr is false, we quit – Feature recently added to Java

10/17/08

CS3101-1, Lecture 5

60

Var-length param lists Seen var-length param lists to scanf, printf – Claimed: no ftn over-loading in C – Very strange! How does this work?

Declarations: – int scanf(char *format, …); – int printf(char *format, …);

As one says in original, “ellipses in original.” … is part of C

10/17/08

CS3101-1, Lecture 5

61

Var-length param lists varargs.h , included by stdargs.h, contains macros: va_list – type used for var that pts to arg in list

va_start(ap, fmt) – Sets ap to first arg

va_arg(ap, type-name)

– Returns current arg interped as type-name

va_end(ap) – Cleans up

Q: How do we know when to quit? A: Pass in info Q: But we didn’t pass it to printf/scanf A: Yes we did – in the form of appearances of wildcards in the pattern string

Content of macros left as an exercise sum.c 10/17/08

CS3101-1, Lecture 5

62

Grading Final will be hard/challenging – Ave score probably near 70% – Final grades are curved

Rule of thumb: mean ~ stdev – Mean ~ B/B– +-stdev ~ one letter grade – See mean/stdevs on web to estimate your grade

10/17/08

CS3101-1, Lecture 5

63

Next time: final exam Closed books/notes/everything 2 hours/class time Questions: – “Vocab”: extern, static, etc. – Find errors/read code/predict output – Write code

See web for a semi-definitive list of topics Jake will be proctoring the exam But we’ll both have OH this week(end) – Come in if you have questions! 10/17/08

CS3101-1, Lecture 5

64

The future Q: What happens when OO is added to C? A: See CS3101-2: C++, beginning the week after the final – Same time, same channel

hw4 TBA Please fill out mid-term course evals! – Link will be on classpage tonight – Available until day of final

Sign in and good luck! 10/17/08

CS3101-1, Lecture 5

65