CS 61C L05 C Structs (1) Wawrzynek Spring 2006 © UCB1/27/2006John Wawrzynek(www.cs.berkeley.edu/~johnw)www-inst.eecs.berkeley.edu/~cs61c/CS61C – Machine StructuresLecture 5 – C Structs & Memory MangementCS 61C L05 C Structs (2) Wawrzynek Spring 2006 © UCBC String Standard Functionsint strlen(char *string);• compute the length of stringint strcmp(char *str1, char *str2);• return 0 if str1 and str2 are identical (how isthis different from str1 == str2?)char *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 L05 C Structs (3) Wawrzynek Spring 2006 © UCBPointers (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 L05 C Structs (4) Wawrzynek Spring 2006 © UCBPointers (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 L05 C Structs (5) Wawrzynek Spring 2006 © UCBPointers (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 L05 C Structs (6) Wawrzynek Spring 2006 © UCBPointers (4/4)°Solution! Pass a pointer to a pointer,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 L05 C Structs (7) Wawrzynek Spring 2006 © UCBDynamic Memory Allocation (1/4)° C has operator sizeof() which gives size inbytes (of type or variable)° Assume size of objects can be misleadingand is bad style, so use sizeof(type)(Many years ago an int was 16 bits, and programswere written with this assumption. What is thesize of integers now?)° “sizeof” is not a real function - it does itswork at compile time. So:char foo[3*sizeof(int)] is valid,• But neither of these is valid in C:char foo[3*myfunction(int)]char foo[3*myfunction(7)]CS 61C L05 C Structs (8) Wawrzynek Spring 2006 © UCBDynamic Memory Allocation (2/4)°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 L05 C Structs (9) Wawrzynek Spring 2006 © UCBDynamic Memory Allocation (3/4)°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 L05 C Structs (10) Wawrzynek Spring 2006 © UCBDynamic Memory Allocation (4/4)° The following two things will cause yourprogram to crash or behave strangely lateron, and cause VERY VERY hard to figureout bugs:free()ing the same piece of memory twicecalling free() on something you didn't getback from malloc()• The runtime does *not* check for thesemistakes (memory allocation is soperformance-critical that there just isn't time todo this), and the usual result is that you corruptthe memory allocator's internal structures -- butyou won't find out until much later on, in sometotally unrelated part of your code.CS 61C L05 C Structs (11) Wawrzynek Spring 2006 © UCBC structures : Overview°A struct is a data structurecomposed from simpler data types.• Like a class in Java/C++ but withoutmethods or inheritance.struct point { /* type definition */ int x; int y;};void PrintPoint(struct point p){ printf(“(%d,%d)”, p.x, p.y);}struct point p1 = {0,10}; PrintPoint(p1);As always in C, the argument is passed by “value” - a copy is made.CS 61C L05 C Structs (12) Wawrzynek Spring 2006 © UCBC structures: Pointers to them°Usually, more efficient to pass apointer to the struct.°The C arrow operator (->)dereferences and extracts a structurefield with a single operator.°The following are equivalent:struct point *p; code to assign to pointerprintf(“x is %d\n”, (*p).x);printf(“x is %d\n”, p->x);CS 61C L05 C Structs (13) Wawrzynek Spring 2006 © 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 L05 C Structs (14) Wawrzynek Spring 2006 © UCBLinked List Example°Let’s look at an example of usingstructures, pointers, malloc(), andfree() to implement a linked list ofstrings./* node structure for linked list */struct Node { char *value; struct Node *next; };CS 61C L05 C Structs (15) Wawrzynek Spring 2006 © UCBLinked List Example/* add a string to an existing list */Node * list_add(Node *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;}{ char *s1 = “abc”, *s2 = “cde”; Node *theList = NULL; theList = list_add(theList, s1); theList = list_add(theList, s2);CS 61C L05 C Structs (16) Wawrzynek Spring 2006 © UCBLinked List Example/* add a string to an existing list, 2nd call */Node * list_add(Node *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:“cde”… …NULL?CS 61C L05 C Structs (17) Wawrzynek Spring 2006 © UCBLinked List Example/* add a string to an existing list */Node * list_add(Node *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:“cde”… …NULL??CS 61C L05 C Structs (18) Wawrzynek Spring 2006 © UCBLinked List Example/* add a string to an existing list */Node * list_add(Node *list, char *string){ struct Node *node = (struct Node *)
View Full Document
Unlocking...