'&$%CSE 303:Concepts and Tools for Software DevelopmentHal PerkinsSpring 2008Lecture 9— C: structs, the heap and manual memory managementCSE303 Spring 2008, Lecture 9 1'&$%Where are we• structs (records with fields) and more on pointers• heap-allocated objects; space leaks and more dangling pointers• Next week: our first “societal implications” class (suggestions fortopics?)CSE303 Spring 2008, Lecture 9 2'&$%StructsA struct is a record.A pointer to a struct is like a Java object with no methods.x.f is for fie ld acce ss. (if x not a pointer — something new!)(*x).f in C is like x.f in Java. (if x is a pointer)x->f is an abbreviation for (*x).f.There is a huge difference between passing a struct and passing apointer to a struct.Again, left-expressions evaluate to locations (which can be wholestruct locations or just a field’s location).Again, right-expressions evaluate to values (which can be whole structsor just a field’s contents ).CSE303 Spring 2008, Lecture 9 3'&$%Pointer syntaxDeclare a variable to have a pointer type:t * x; or t* x; or t *x; or t*x;(where t is a type and x is a variable)An expression to derefere nce a pointer:*x (or m ore generally *e)where e is an expression.C’s designers used the same character on purpose, but declarations(create space) and expres sions (c ompute a value) are totally differentthings.(And there’s multiplication too.)CSE303 Spring 2008, Lecture 9 4'&$%Heap-AllocationSo far, all of our ints, pointers, arrays, and structs have beenstack-allocated, which in C has two huge limitations:• The space is reclaimed when the allocating function returns• The space required must be a constant (only an issue for arrays)Heap-allocation has neither limitation.Comparison: new C(...) in Java:• Allocate space for a C (exception if out-of-memory)• Initialize the fields to null or 0• Call the user-written constructor function• Return a reference (hey, a pointer!) to the new object.In C, these steps are almost all separated.CSE303 Spring 2008, Lecture 9 5'&$%Malloc, part 1malloc is “just” a library function: it takes a number, heap-allocatesthat many bytes and returns a pointer to the newly-allocated memory.• Returns NULL on failure.• Does not initialize the memory.• You must cast the result to the pointer type you want.• You do not know how much space different values need!Do not do things like (struct Foo*)(malloc(8))!CSE303 Spring 2008, Lecture 9 6'&$%Malloc, part 2malloc is “always” used in a specific way:(t*)malloc(e * sizeof(t))Returns a pointer to memory large enough to hold an array of length ewith elements of type t.It is still not initialized (use a loop)!Underused friend: calloc (takes e and sizeof(t) as separatearguments, initializes everything to 0).Note: x[i] and *(x+i) actually get you the sizeof(x) bytes ataddress “x plus (i times sizeof(x))” – do not do *(x+i*sizeof(x))(that’s too big an index).CSE303 Spring 2008, Lecture 9 7'&$%Half the BattleWe c an now alloc ate me mory of any size and have it “live” forever.For example, we can allocate an array and return it.Unfortunately, computers do not have infinite memory so “livingforever” could be a problem.Java solution: Conceptually objects live forever, but the syste m has agarbage collector that finds unreachable objects and reclaims theirspace.C solution: You e xplicitly free an object’s space by passing a pointerto it to the library function free.Freeing heap me mory correctly is very hard in complex software and isthe disadvantage of C-style heap-allocation.• Later we will le arn idioms that help. For now just learn the rulesof the game.CSE303 Spring 2008, Lecture 9 8'&$%Everybody wants to be free(d once)int * p = (int*)malloc(sizeof(int));p = NULL; /* LEAK! */int * q = (int*)malloc(sizeof(int));free(q);free(q); /* HYCSBWK */int * r = (int*)malloc(sizeof(int));free(r);int * s = (int*)malloc(sizeof(int));*s = 19;*r = 17; /* HYCSBWK, but maybe *s==17 ?! */Problems much worse with functions:f returns a pointer; (w hen) should f’s caller free the pointed-to object?g takes two pointers and frees one pointed-to object. Can the otherpointer be dereferenced?CSE303 Spring 2008, Lecture 9 9'&$%The rules of malloc/freeFor every run-time call to malloc there should be one run-time call tofree.If you “lose all pointers” to an object, you c an’t ever c all free (a leak)!If you “use an object after it’s freed” (or free it twice), you used adangling pointer!Note: It’s possible but rare to use up too much memory withoutcreating “leaks via no more pointers to an object”.Interesting side-note: The standard-library must “remember” how bigthe object is (but it won’t tell you).CSE303 Spring 2008, Lecture 9
View Full Document
Unlocking...