CS 61C L04 C Structures, Memory Management (1)Garcia, Fall 2004 © UCBLecturer PSOE Dan Garciawww.cs.berkeley.edu/~ddgarciainst.eecs.berkeley.edu/~cs61cCS61C : Machine Structures Lecture 5 – C Memory Management 2004-09-10Barry Bonds nears 700! ⇒ We are witness to perhapsthe greatest baseball player of all time,and he plays weekly 10 miles fromhere! Years from now you’ll knowwhere you were when he passed 755.CS 61C L04 C Structures, Memory Management (2)Garcia, Fall 2004 © UCBMore from Wednesday’s lecture1. #define macros may go anywhere.Thereafter the name is replaced with thereplacement text. It is usually good style toput all #defines at the top so thatreordering code doesn’t cause bugs.2. void * pointers used to be char *pointers (before ANSI C). Therefore, partiallyto maintain compatibility, ++ incrementing avoid * pointer via increments it by 1 byte.3. const type qualifier announces objects arenot to be changed. Implementation-dependent storage and violation penalty.CS 61C L04 C Structures, Memory Management (3)Garcia, Fall 2004 © UCBC String Standard Functions• int strlen(char *string);• compute the length of string• int strcmp(char *str1, char *str2);• return 0 if str1 and str2 are identical (how isthis different from str1 == str2?)• int strcpy(char *dst, char *src);• copy the contents of string src to the memoryat dst. The caller must ensure that dst hasenough memory to hold the data to be copied.CS 61C L04 C Structures, Memory Management (4)Garcia, Fall 2004 © UCBPointers to pointers (1/4)• Sometimes you want to have aprocedure increment a variable?• What gets printed?void AddOne(int x){ x = x + 1; }int y = 5;AddOne( y);printf(“y = %d\n”, y);y = 5…review…CS 61C L04 C Structures, Memory Management (5)Garcia, Fall 2004 © UCBPointers to pointers (2/4)• Solved by passing in a pointer to oursubroutine.• Now what gets printed?void AddOne(int *p){ *p = *p + 1; }int y = 5;AddOne(&y);printf(“y = %d\n”, y);y = 6…review…CS 61C L04 C Structures, Memory Management (6)Garcia, Fall 2004 © UCBPointers to pointers (3/4)• But what if what you want changed isa pointer?• What gets printed?void IncrementPtr(int *p){ p = p + 1; }int A[3] = {50, 60, 70};int *q = A;IncrementPtr( q);printf(“*q = %d\n”, *q);*q = 5050 60 70AqCS 61C L04 C Structures, Memory Management (7)Garcia, Fall 2004 © UCBPointers to pointers (4/4)• Solution! Pass a pointer to a pointer,called a handle, declared as **h• Now what gets printed?void IncrementPtr(int **h){ *h = *h + 1; }int A[3] = {50, 60, 70};int *q = A;IncrementPtr(&q);printf(“*q = %d\n”, *q);*q = 6050 60 70AqqCS 61C L04 C Structures, Memory Management (8)Garcia, Fall 2004 © UCBAdministrivia• One extra credit lab checkoff pt!• Sign up to get your lab checked off bythe first hour and you will get 1 bonuscheckoff point to count toward finalgrade. (Not 1/300, +1 out of 4 for that lab)CS 61C L04 C Structures, Memory Management (9)Garcia, Fall 2004 © UCBDynamic Memory Allocation (1/3)• C has operator sizeof() which givessize in bytes (of type or variable)• Assume size of objects can bemisleading & is bad style, so usesizeof(type)• Many years ago an int was 16 bits, andprograms assumed it was 2 bytesCS 61C L04 C Structures, Memory Management (10)Garcia, Fall 2004 © UCBDynamic Memory Allocation (2/3)• To allocate room for something new topoint to, use malloc() (with the help of atypecast and sizeof):ptr = (int *) malloc (sizeof(int));• Now, ptr points to a space somewhere inmemory of size (sizeof(int)) in bytes.•(int *) simply tells the compiler what willgo into that space (called a typecast).• malloc is almost never used for 1 varptr = (int *) malloc (n*sizeof(int));• This allocates an array of n integers.CS 61C L04 C Structures, Memory Management (11)Garcia, Fall 2004 © UCBDynamic Memory Allocation (3/3)• Once malloc() is called, the memorylocation contains garbage, so don’tuse it until you’ve set its value.• After dynamically allocating space, wemust dynamically free it:free(ptr);• Use this command to clean up.CS 61C L04 C Structures, Memory Management (12)Garcia, Fall 2004 © UCBBinky Pointer Video (thanks to NP @ SU)CS 61C L04 C Structures, Memory Management (13)Garcia, Fall 2004 © UCBC structures : Overview• A struct is a data structurecomposed for simpler data types.• Like a class in Java/C++ but withoutmethods or inheritance.struct point { int x; int y;}void PrintPoint(point p){ printf(“(%d,%d)”, p.x, p.y);}CS 61C L04 C Structures, Memory Management (14)Garcia, Fall 2004 © UCBC structures: Pointers to them• The C arrow operator (->)dereferences and extracts a structurefield with a single operator.• The following are equivalent:struct point *p;printf(“x is %d\n”, (*p).x);printf(“x is %d\n”, p->x);CS 61C L04 C Structures, Memory Management (15)Garcia, Fall 2004 © UCBHow big are structs?• Recall C operator sizeof() whichgives size in bytes (of type or variable)• How big is sizeof(p)? struct p {char x;int y;};• 5 bytes? 8 bytes?• Compiler may word align integer yCS 61C L04 C Structures, Memory Management (16)Garcia, Fall 2004 © UCBWhich are guaranteed to print out 5?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); }III: main() { int *ptr; ptr = (int *) malloc (sizeof(int)); *ptr = 5; printf(“%d”, *ptr); }Peer Instruction I II III1: - - -2: - - YES3: - YES -4: - YES YES5: YES - -6: YES - YES7: YES YES -8: YES YES YESCS 61C L04 C Structures, Memory Management (17)Garcia, Fall 2004 © UCBLinked List Example• Let’s look at an example of usingstructures, pointers, malloc(), andfree() to implement a linked list ofstrings.struct Node { char *value; struct Node *next; };typedef Node *List;/* Create a new (empty) list */List ListNew(void){ return NULL; }CS 61C L04 C Structures, Memory Management (18)Garcia, Fall 2004 © UCBLinked 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;}node:list:string:“abc”… …NULL?CS 61C L04 C Structures, Memory Management (19)Garcia, Fall 2004 © UCBLinked List Example/* add a string to an existing list
View Full Document