# The Heap and Structs CSE 333 Spring 2018

L04: The Heap, Structs The Heap and Structs CSE 333 Spring 2018 Instructor: Justin Hsia Teaching Assistants: Danny Allen Dennis Shao Eddie Huang Kevin Bi Jack Xu Matthew Neldam Michael Poulain Renshu Gu Robby Marver Waylon Huang Wei Lin CSE333, Spring 2018 L04: The Heap, Structs CSE333, Spring 2018 Administrivia Piazza has a search bar use it before you post! And make sure you name your posts descriptively so others can find them! Exercise 3 out today and due Wednesday morning We highly recommend doing the extra exercises that are at the end of each lecture

Also, Google for C pointer exercises and do as many as you can get your hands on 2 L04: The Heap, Structs CSE333, Spring 2018 Administrivia hw0 due tonight before 11:59 pm (and 0 seconds) If your clock says 11:59, then its late! You really, really dont want to use late day tokens for hw0 Git: add/commit/push, then tag with hw0-final, then push tag Then clone repo somewhere totally different and do git checkout hw0-final and verify that all is well hw1 due Thu, 4/12 You may not modify interfaces (.h files) You might get a merge conflict when pushing hw0 Do a pull, accept the merge (ok to use default 3 L04: The Heap, Structs CSE333, Spring 2018

Lecture Outline Heap-allocated Memory malloc() and free() Memory leaks structs and typedef 4 L04: The Heap, Structs CSE333, Spring 2018 Memory Allocation So Far So far, we have seen two kinds of memory allocation: int foo(int a) { int counter = 0; // global var int x = a + 1; return x; // local var } int main(int argc, char** argv) { counter++; printf("count = %d\n",counter); return 0; }

int main(int argc, char** argv) { int y = foo(10); // local var printf("y = %d\n",y); return 0; } counter is statically- a, x, y are automatically- allocated Allocated when program is loaded Deallocated when program exits allocated Allocated when function is called Deallocated when function returns 5 L04: The Heap, Structs CSE333, Spring 2018 Dynamic Allocation Situations where static and automatic allocation arent sufficient: We need memory that persists across multiple

function calls but not the whole lifetime of the program We need more memory than can fit on the Stack We need memory whose size is not known in advance theiscaller // to this pseudo-C code char* ReadFile(char* filename) { int size = GetFileSize(filename); char* buffer = AllocateMem(size); ReadFileIntoBuffer(filename, buffer); return buffer; } 6 L04: The Heap, Structs CSE333, Spring 2018 Dynamic Allocation What we want is dynamically-allocated memory Your program explicitly requests a new block of memory The language allocates it at runtime, perhaps with help from OS Dynamically-allocated memory persists until either: Your code explicitly deallocated it (manual memory management)

A garbage collector collects it (automatic memory management) C requires you to manually manage memory 7 L04: The Heap, Structs CSE333, Spring 2018 Aside: NULL NULL is a memory location that is guaranteed to be invalid In C on Linux, NULL is 0x0 and an attempt to dereference NULL causes a segmentation fault Useful as an indicator of an uninitialized (or currently unused) pointer or allocation error Its better to cause a segfault than to allow the corruption of memory! segfault. c int main(int argc, char** argv) { int* p = NULL; *p = 1; // causes a segmentation fault return 0; } 8 L04: The Heap, Structs CSE333, Spring 2018 malloc()

var = (type*) malloc(size in General usage: bytes) malloc allocates a block of memory of the requested size Returns a pointer to the first byte of that memory And returns NULL if the memory allocation failed! You should assume that the memory initially contains garbage Youll typically use sizeof // allocate a 10-float array to calculate the size you float* arr = (float*) malloc(10*sizeof(float)); need if (arr == NULL) { return errcode; } ... // do stuff with arr 9 L04: The Heap, Structs CSE333, Spring 2018 calloc() General usage:

Like malloc, but also zeros out the block of memory var = (type*) calloc(num, bytes per element) Helpful for shaking out bugs Slightly slower; preferred for non-performance-critical code malloc // allocate a 10-double and calloc arearray found in stdlib.h double* arr = (double*) calloc(10, sizeof(double)); if (arr == NULL) { return errcode; } ... // do stuff with arr 10 L04: The Heap, Structs CSE333, Spring 2018 free() Usage: free(pointer); free(pointer); Deallocates the memory pointed-to by the pointer

Pointer must point to the first byte of heap-allocated memory (i.e. something previously returned by malloc or calloc) Freed memory becomes eligible for future allocation Pointer is unaffected by call to free float* arr = (float*) malloc(10*sizeof(float)); (arr == NULL) if Defensive programming: can set return errcode; freeing it ... // do stuff with arr free(arr); arr = NULL; // OPTIONAL pointer to NULL after 11 L04: The Heap, Structs CSE333, Spring 2018 The Heap The Heap is a large pool of unused memory that is used for dynamicallyallocated data 0xFF FF Shared Libraries malloc allocates chunks of

data in the Heap; free deallocates those chunks malloc maintains bookkeeping data in the Heap to track allocated blocks OS kernel [protected] Stack Heap (malloc/free) Read/Write Segment .data, .bss Read-Only Segment .text, .rodata Lab 5 from 351! 0x00 00 12 L04: The Heap, Structs CSE333, Spring 2018 Heap and Stack Example arraycopy.c Note: Arrow points to next instruction. OS kernel [protected] #include

Stack int* copy(int a[], int size) { int i, *a2; a2 = malloc(size*sizeof(int)); if (a2 == NULL) return NULL; main nums ncopy for (i = 0; i < size; i++) a2[i] = a[i]; return a2; } int main(int argc, char** int nums[4] = {1, 2, 3, int* ncopy = copy(nums, // .. do stuff with the free(ncopy); return 0; } argv) { 4}; 4); array .. Heap (malloc/free) Read/Write Segment Read-Only Segment (main, copy) 13 L04: The Heap, Structs CSE333, Spring 2018 Heap and Stack Example

arraycopy.c OS kernel [protected] #include Stack int* copy(int a[], int size) { int i, *a2; a2 = malloc(size*sizeof(int)); if (a2 == NULL) return NULL; main nums 1 2 3 4 ncopy for (i = 0; i < size; i++) a2[i] = a[i]; return a2; } int main(int argc, char** int nums[4] = {1, 2, 3, int* ncopy = copy(nums, // .. do stuff with the free(ncopy); return 0; } argv) { 4}; 4);

array .. Heap (malloc/free) Read/Write Segment Read-Only Segment (main, copy) 14 L04: The Heap, Structs CSE333, Spring 2018 Heap and Stack Example arraycopy.c OS kernel [protected] #include Stack int* copy(int a[], int size) { int i, *a2; a2 = malloc(size*sizeof(int)); if (a2 == NULL) return NULL; main copy nums 1 2 3 4 ncopy a

size 4 i a2 for (i = 0; i < size; i++) a2[i] = a[i]; return a2; } int main(int argc, char** int nums[4] = {1, 2, 3, int* ncopy = copy(nums, // .. do stuff with the free(ncopy); return 0; } argv) { 4}; 4); array .. Heap (malloc/free) Read/Write Segment Read-Only Segment (main, copy) 15 L04: The Heap, Structs CSE333, Spring 2018 Heap and Stack Example arraycopy.c OS kernel [protected] #include Stack

int* copy(int a[], int size) { int i, *a2; a2 = malloc(size*sizeof(int)); if (a2 == NULL) return NULL; for (i = 0; i < size; i++) a2[i] = a[i]; main nums 1 2 3 4 ncopy copy a size 4 i a2 malloc return a2; } int main(int argc, char** int nums[4] = {1, 2, 3, int* ncopy = copy(nums, // .. do stuff with the free(ncopy); return 0;

} argv) { 4}; 4); array .. Heap (malloc/free) Read/Write Segment Read-Only Segment (main, copy) 16 L04: The Heap, Structs CSE333, Spring 2018 Heap and Stack Example arraycopy.c OS kernel [protected] #include Stack int* copy(int a[], int size) { int i, *a2; a2 = malloc(size*sizeof(int)); if (a2 == NULL) return NULL; main copy nums 1 2 3

4 ncopy a size 4 i a2 for (i = 0; i < size; i++) a2[i] = a[i]; return a2; } int main(int argc, char** int nums[4] = {1, 2, 3, int* ncopy = copy(nums, // .. do stuff with the free(ncopy); return 0; } argv) { 4}; 4); array .. Heap (malloc/free) Read/Write Segment Read-Only Segment (main, copy) 17 L04: The Heap, Structs CSE333, Spring 2018 Heap and Stack Example arraycopy.c

OS kernel [protected] #include Stack int* copy(int a[], int size) { int i, *a2; a2 = malloc(size*sizeof(int)); if (a2 == NULL) return NULL; main copy nums 1 2 3 4 ncopy a i size 4 0 a2 for (i = 0; i < size; i++) a2[i] = a[i]; return a2; } int main(int argc, char** int nums[4] = {1, 2, 3, int* ncopy = copy(nums, // .. do stuff with the free(ncopy);

return 0; } argv) { 4}; 4); array .. Heap (malloc/free) Read/Write Segment Read-Only Segment (main, copy) 18 L04: The Heap, Structs CSE333, Spring 2018 Heap and Stack Example arraycopy.c OS kernel [protected] #include Stack int* copy(int a[], int size) { int i, *a2; a2 = malloc(size*sizeof(int)); if (a2 == NULL) return NULL; main copy nums 1 2 3

4 ncopy a size 4 i 4 1 2 a2 for (i = 0; i < size; i++) a2[i] = a[i]; return a2; } int main(int argc, char** int nums[4] = {1, 2, 3, int* ncopy = copy(nums, // .. do stuff with the free(ncopy); return 0; } argv) { 4}; 4); array .. 3 4 Heap (malloc/free) Read/Write Segment

Read-Only Segment (main, copy) 19 L04: The Heap, Structs CSE333, Spring 2018 Heap and Stack Example arraycopy.c OS kernel [protected] #include Stack int* copy(int a[], int size) { int i, *a2; a2 = malloc(size*sizeof(int)); if (a2 == NULL) return NULL; main nums 1 2 3 4 ncopy for (i = 0; i < size; i++) a2[i] = a[i]; return a2; } int main(int argc, char** int nums[4] = {1, 2, 3,

int* ncopy = copy(nums, // .. do stuff with the free(ncopy); return 0; } argv) { 4}; 4); array .. 1 2 3 4 Heap (malloc/free) Read/Write Segment Read-Only Segment (main, copy) 20 L04: The Heap, Structs CSE333, Spring 2018 Heap and Stack Example arraycopy.c OS kernel [protected] #include Stack int* copy(int a[], int size) { int i, *a2; a2 = malloc(size*sizeof(int));

if (a2 == NULL) return NULL; main nums 1 2 3 4 ncopy for (i = 0; i < size; i++) a2[i] = a[i]; return a2; } int main(int argc, char** int nums[4] = {1, 2, 3, int* ncopy = copy(nums, // .. do stuff with the free(ncopy); return 0; } argv) { 4}; 4); array .. 1 2 3 4 Heap (malloc/free)

Read/Write Segment Read-Only Segment (main, copy) 21 L04: The Heap, Structs CSE333, Spring 2018 Heap and Stack Example arraycopy.c OS kernel [protected] #include Stack int* copy(int a[], int size) { int i, *a2; a2 = malloc(size*sizeof(int)); if (a2 == NULL) return NULL; main nums 1 2 3 4 ncopy free for (i = 0; i < size; i++) a2[i] = a[i]; return a2;

} int main(int argc, char** int nums[4] = {1, 2, 3, int* ncopy = copy(nums, // .. do stuff with the free(ncopy); return 0; } argv) { 4}; 4); array .. Heap (malloc/free) Read/Write Segment Read-Only Segment (main, copy) 22 L04: The Heap, Structs CSE333, Spring 2018 Heap and Stack Example arraycopy.c OS kernel [protected] #include Stack int* copy(int a[], int size) { int i, *a2; a2 = malloc(size*sizeof(int)); if (a2 == NULL) return NULL; main

nums 1 2 3 4 ncopy for (i = 0; i < size; i++) a2[i] = a[i]; return a2; } int main(int argc, char** int nums[4] = {1, 2, 3, int* ncopy = copy(nums, // .. do stuff with the free(ncopy); return 0; } argv) { 4}; 4); array .. Heap (malloc/free) Read/Write Segment Read-Only Segment (main, copy) 23 L04: The Heap, Structs CSE333, Spring 2018 Peer Instruction Question Which line below is first guaranteed to cause

an error? Vote at http://PollEv.com/justinh #include #include A. Line 1 B. Line 4 C. Line 6 D. Line 7 E. Were lost int main(int argc, char** argv) { int a[2]; int* b = malloc(2*sizeof(int)); int* c; a[2] = 5; b[0] += 2; c = b+3; free(&(a[0])); free(b); free(b); b[0] = 5; 1 2 3 4 5 6 7 return 0; } 24 L04: The Heap, Structs CSE333, Spring 2018 Memory Corruption

There are all sorts of ways to corrupt memory in C #include #include int main(int argc, char** argv) { int a[2]; int* b = malloc(2*sizeof(int)); int* c; a[2] = 5; // b[0] += 2; // c = b+3; // free(&(a[0])); free(b); free(b); // b[0] = 5; // assign past the end of an array assume malloc zeros out memory mess up your pointer arithmetic // free something not malloc'ed double-free the same block use a freed pointer // any many more! return 0; memcorrup } 25 L04: The Heap, Structs CSE333, Spring 2018

Memory Leak A memory leak occurs when code fails to deallocate dynamically-allocated memory that is no longer used e.g. forget to free malloc-ed block, lose/change pointer to malloc-ed block Implication: programs VM footprint will keep growing This might be OK for short-lived program, since memory deallocated when program ends Usually has bad repercussions for long-lived programs Might slow down over time (e.g. lead to VM thrashing) 26 L04: The Heap, Structs CSE333, Spring 2018 Lecture Outline Heap-allocated Memory malloc() and free() Memory leaks structs and typedef 27 L04: The Heap, Structs

CSE333, Spring 2018 Structured Data A struct is a C datatype that contains a set of fields Similar to a Java class, but with no methods or constructors Useful for defining new structured types of data Act similarly to primitive variables struct tagname { type1declaration: name1; Generic ... typeN nameN; }; // the following defines a new // structured datatype called // a "struct Point" struct Point { float x, y; }; // declare and initialize a // struct Point variable struct Point origin = {0.0,0.0}; 28 L04: The Heap, Structs CSE333, Spring 2018 Using structs

Use . to refer to a field in a struct Use -> to refer to a field from a struct pointer Dereferences pointer first, then accesses field struct Point { float x, y; }; int main(int argc, char** argv) { struct Point p1 = {0.0, 0.0}; // p1 is stack allocated struct Point* p1_ptr = &p1; p1.x = 1.0; p1_ptr->y = 2.0; return 0; // equivalent to (*p1_ptr).y = 2.0; } simplestruct.c 29 L04: The Heap, Structs CSE333, Spring 2018 Copy by Assignment You can assign the value of a struct from a struct of the same type this copies the entire contents! #include struct Point { float x, y; }; int main(int argc, char** argv) { struct Point p1 = {0.0, 2.0}; struct Point p2 = {4.0, 6.0};

printf("p1: {%f,%f} p2 = p1; printf("p1: {%f,%f} return 0; p2: {%f,%f}\n", p1.x, p1.y, p2.x, p2.y); p2: {%f,%f}\n", p1.x, p1.y, p2.x, p2.y); } structassign.c 30 L04: The Heap, Structs CSE333, Spring 2018 typedef type name; Generic format:typedef typedef type name; Allows you to define new data type names/synonyms Both type and name are usable and refer to the same type // make "superlong" a synonym for "unsigned long long" typedef unsigned long superlong; Be careful withlong pointers * before name is part

of type! // make "str" a synonym for "char*" typedef char *str; // make "Point" a synonym for "struct point_st { ... } // make "PointPtr" a synonym for "struct point_st*" typedef struct point_st { superlong x; superlong y; } Point, *PointPtr; // similar syntax to "int n, *p;" Point origin = {0, 0}; 31 L04: The Heap, Structs CSE333, Spring 2018 Dynamically-allocated Structs You can malloc and free structs, just like other data type sizeof is particularly helpful here // a complex number is a + bi typedef struct complex_st { double real; // real component double imag; // imaginary component } Complex, *ComplexPtr; // note that ComplexPtr is equivalent to Complex* ComplexPtr AllocComplex(double real, double imag) { Complex* retval = (Complex*) malloc(sizeof(Complex)); if (retval != NULL) { retval->real = real; retval->imag = imag; } return retval;

} complexstruct.c 32 L04: The Heap, Structs CSE333, Spring 2018 Structs as Arguments Structs are passed by value, like everything else in C Entire struct is copied where? To manipulate a struct argument, pass a pointer typedef struct point_st { instead int x, y; } Point, *PointPtr; void DoubleXBroken(Point p) { p.x *= 2; } void DoubleXWorks(PointPtr p) { p->x *= 2; } int main(int argc, char** argv) { Point a = {1,1}; DoubleXBroken(a); printf("(%d,%d)\n", a.x, a.y); DoubleXWorks(&a); printf("(%d,%d)\n", a.x, a.y); return 0; } // prints: ( ,

) // prints: ( , ) 33 L04: The Heap, Structs CSE333, Spring 2018 Returning Structs Exact method of return depends on calling conventions Often in %rax and %rdx for small structs Often returned in memory for larger structs // a complex number is a + bi typedef struct complex_st { double real; // real component double imag; // imaginary component } Complex, *ComplexPtr; Complex MultiplyComplex(Complex x, Complex y) { Complex retval; retval.real = (x.real * y.real) - (x.imag * y.imag); retval.imag = (x.imag * y.real) - (x.real * y.imag); return retval; // returns a copy of retval } complexstruct.c 34 L04: The Heap, Structs CSE333, Spring 2018

Pass Copy of Struct or Pointer? Value passed: passing a pointer is cheaper and takes less space unless struct is small Field access: indirect accesses through pointers are a bit more expensive and can be harder for compiler to optimize For small stucts (like struct complex_st), passing a copy of the struct can be faster and often preferred; for large structs use pointers 35 L04: The Heap, Structs CSE333, Spring 2018 Extra Exercise #1 Write a program that defines: A new structured type Point Represent it with floats for the x and y coordinates A new structured type Rectangle Assume its sides are parallel to the x-axis and y-axis Represent it with the bottom-left and top-right Points A function that computes and returns the area of a

Rectangle A function that tests whether a Point is inside of a Rectangle 36 L04: The Heap, Structs CSE333, Spring 2018 Extra Exercise #2 Implement AllocSet() and FreeSet() AllocSet() needs to use malloc twice: once to allocate a new ComplexSet and once to allocate the points field inside it FreeSet() needs to use free twice typedef struct complex_st { double real; // real component double imag; // imaginary component } Complex; typedef struct complex_set_st { double num_points_in_set; Complex* points; // an array of Complex } ComplexSet; ComplexSet* AllocSet(Complex c_arr[], int size); void FreeSet(ComplexSet* set); 37

## Recently Viewed Presentations

• Charles Bourque is a Professor in the Department of Neurology-Neurosurgery at McGill University. He holds a Distinguished James McGill Chair and his laboratory is part of the Centre for Research in Neuroscience at the Montreal General Hospital. Bourque and his...
• The second part is much like our usual statistical assumption about independence of observations. That is, the treatment or outcome of one subject is not affected by the treatment or outcome of any other subjects. Violations of these assumptions would...
• CºC triple bond. Formula for one triple bond = CnH2n-2. Subtract four Hs from alkane for each triple bond. Linear shape. More reactive than alkenes. * * n-1-Alkynes * Alkynes Ethyne = acetylene Propyne * Physical Properties of Alkynes *...
• If we execute one test per millisecond, it would take 3,170 years to test this program!! 14 * Selective Testing loop < 20 X Selected path * Software Testing Methods Strategies white-box methods black-box methods * White-Box Testing ... our...
• Iowa Caucuses. An Imperfect Political Weather Vane. ON TUESDAY, perhaps 100,000 to 150,000 Iowans will gather in buildings ranging from high school gymnasiums to small airports. They will munch leftover Christmas treats and cast ballots in a straw poll, which...
• Alternative debt assumptions. Sculpting. Re-financing. Tail by the end of re-financing. Key is the interest rate relative to inflation. With re-financing, the amount of debt and the credit spread really matter and not the tenor of the debt. Case 6:...
• Going to highlight everything you can use to talk about the theme of a poem. By the end of the class, you shall be able to discuss the theme of any poem in great detail. Today. Unseen Poetry 3. ......
• The Trinity: Unpacking the Nicene Creed. I believe in one God, the Father almighty, maker of heaven and earth, of all things visible and invisible. I believe in one Lord Jesus Christ, the Only Begotten Son of God, born of...