inst eecs berkeley edu cs61c CS61C Machine Structures Lecture 4 C Memory Management 2007 06 28 Scott Beamer Instructor iPhone Comes out Tomorrow Review C99 is the update to the ANSI standard Pointers and arrays are virtually same C knows how to increment pointers C is an efficient language w little protection Array bounds not checked Variables not automatically initialized Beware The cost of efficiency is more overhead for the programmer C gives you a lot of extra rope but be careful not to hang yourself with it Use handles to change pointers P 53 is a precedence table useful for e g x p p p 1 x p www apple com iphone CS61C L4 C M emory Management 1 Beamer Summer 2007 UCB Binky Pointer Video thanks to NP SU CS61C L4 C M emory Management 2 Beamer Summer 2007 UCB C structures Overview A struct is a data structure composed for simpler data types Like a class in Java C but without methods or inheritance struct point int x int y void PrintPoint struct point p printf d d p x p y CS61C L4 C M emory Management 3 Beamer Summer 2007 UCB CS61C L4 C M emory Management 4 Beamer Summer 2007 UCB C structures Pointers to them How big are structs The C arrow operator dereferences and extracts a structure field with a single operator Recall C operator sizeof which gives size in bytes of type or variable The following are equivalent struct point p printf x is d n p x printf x is d n p x CS61C L4 C M emory Management 5 Beamer Summer 2007 UCB How big is sizeof p struct p char x int y 5 bytes 8 bytes Compiler may word align integer y CS61C L4 C M emory Management 6 Beamer Summer 2007 UCB Linked List Example Linked List Example Let s look at an example of using structures pointers malloc and free to implement a linked list of strings struct Node char value struct Node next typedef struct Node List Create a new empty list List ListNew void return NULL CS61C L4 C M emory Management 7 Beamer Summer 2007 UCB Linked List Example add a string to an existing list List list add List list char string struct Node node struct Node malloc sizeof struct Node node value char malloc strlen string 1 strcpy node value string node next list return node list node NULL string abc CS61C L4 C M emory Management 8 Beamer Summer 2007 UCB Linked List Example add a string to an existing list List list add List list char string struct Node node struct Node malloc sizeof struct Node node value char malloc strlen string 1 strcpy node value string node next list return node list node NULL string abc add a string to an existing list List list add List list char string struct Node node struct Node malloc sizeof struct Node node value char malloc strlen string 1 strcpy node value string node next list return node list node CS61C L4 C M emory Management 9 CS61C L4 C M emory Management 10 Beamer Summer 2007 UCB Linked List Example abc CS61C L4 C M emory Management 11 NULL string abc Beamer Summer 2007 UCB Linked List Example add a string to an existing list List list add List list char string struct Node node struct Node malloc sizeof struct Node node value char malloc strlen string 1 strcpy node value string node next list return node list node add a string to an existing list List list add List list char string struct Node node struct Node malloc sizeof struct Node node value char malloc strlen string 1 strcpy node value string node next list return node list node NULL string abc abc Beamer Summer 2007 UCB NULL string CS61C L4 C M emory Management 12 abc Beamer Summer 2007 UCB Linked List Example And in Semi Conclusion add a string to an existing list List list add List list char string struct Node node struct Node malloc sizeof struct Node node value char malloc strlen string 1 strcpy node value string node next list return node node Use handles to change pointers Create abstractions with structures Dynamically allocated heap memory must be manually deallocated in C Use malloc and free to allocate and deallocate memory from heap NULL abc CS61C L4 C M emory Management 13 Beamer Summer 2007 UCB Peer Instruction CS61C L4 C M emory Management 14 Peer Instruction int main void int A 5 10 int p A 5 10 A 0 A 1 I main int a ptr a ptr 5 printf d a ptr II main int p a 5 p a code a p NEVER on LHS of printf d a 1 2 3 4 5 6 7 8 I II III YES YES YES YES YES YES YES YES YES YES YES YES CS61C L4 C M emory Management 15 Beamer Summer 2007 UCB If the first printf outputs 100 5 5 10 what will the other two printf output 1 2 3 4 5 6 101 10 5 10 then 104 10 5 10 then 101 other 5 10 then 104 other 5 10 then One of the two printfs I surrender 101 11 5 11 104 11 5 11 101 3 others 104 3 others causes an ERROR CS61C L4 C M emory Management 16 Administrivia Where is data allocated Assignments Structure declaration does not allocate memory HW1 due 7 1 11 59pm Beamer Summer 2007 UCB Variable declaration does allocate memory HW2 due 7 4 11 59pm No class on 7 4 Another section is in the works It won t be official until the last minute Keep checking the course website Once known I will email people on waitlist CS61C L4 C M emory Management 17 p printf u d d d n p p A 0 A 1 p p 1 printf u d d d n p p A 0 A 1 p p 1 printf u d d d n p p A 0 A 1 Which are guaranteed to print out 5 III main int ptr ptr int malloc sizeof int ptr 5 printf d ptr Beamer Summer 2007 UCB Beamer Summer 2007 UCB If declare outside a procedure allocated in static storage If declare inside procedure allocated on the stack and freed when int myGlobal procedure returns main NB main is a int myTemp procedure CS61C L4 C M emory Management 18 Beamer Summer 2007 UCB The Stack Stack Stack frame includes Last In First Out LIFO memory usage Return address Parameters Space for other local variables SP Stack frames contiguous blocks of memory stack pointer tells where top stack frame is When procedure ends stack frame is tossed off the stack frees memory for future stack frames CS61C L4 C M emory Management 19 stack frame frame frame frame Beamer Summer 2007 UCB Who cares about stack management Pointers in C allow access to deallocated memory leading to hard to find bugs int ptr main main main int y SP y 3 ptr printf return y y 3 …
View Full Document
Unlocking...