**Lab 15: Dynamic Allocation and Valgrind** | COMP1633 @ MRU

Note: This lab is due on Tuesday, March 19th at 11:59pm. Due to the increased difficulty of this lab, the recent midterm, and the overall chaos at this time in the semester, two lab sessions were provided to work on this lab and it is due a week after the second session.

Setup

There’s a new git issue that’s popping up - we’re running in to file limit quota issues! Before starting this lab, do the following:

cd into your labs repo
Run the following command:
```
$ git gc
```
gc stands for garbage collection - this will tell git to consolidate a bunch of small files into a larger object
Fetch your new changes as usual with git pull or git pull --no-rebase, depending on whatever elves are in your particular instance.

Finally, cd into the dynamic folder to begin.

Dynamic Allocation

In the previous lab , you wrote a function called sort_3 to take pointers to three Complex objects and sort them by swapping pointers. You called your function with pointers to Complex objects on the stack. A solution to this function is provided. Now, modify your main code as follows:
1. Remove the declarations for c1, c2, and c3
2. Use the new keyword to dynamically allocate Complex objects for each of the three pointers (p1, p2, and p3)
3. Assign values to the real and imag fields of each of the three objects (remembering the -> operator)
4. Call sort_3 as before
5. Print the results as before
6. Free all the memory allocated with new using delete

Double check using valgrind. Run your code with the following command:

valgrind ./main

If all goes well you should see something like:

HEAP SUMMARY:
==954584==     in use at exit: 0 bytes in 0 blocks
==954584==   total heap usage: 5 allocs, 5 frees, 73,776 bytes allocated
==954584==
==954584== All heap blocks were freed -- no leaks are possible
==954584==
==954584== For lists of detected and suppressed errors, rerun with: -s
==954584== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

where the exact numbers will differ depending on your program.

If instead you see something like:

==954599== HEAP SUMMARY:
==954599==     in use at exit: 16 bytes in 1 blocks
==954599==   total heap usage: 5 allocs, 4 frees, 73,776 bytes allocated
==954599==
==954599== LEAK SUMMARY:
==954599==    definitely lost: 16 bytes in 1 blocks
==954599==    indirectly lost: 0 bytes in 0 blocks
==954599==      possibly lost: 0 bytes in 0 blocks
==954599==    still reachable: 0 bytes in 0 blocks
==954599==         suppressed: 0 bytes in 0 blocks
==954599== Rerun with --leak-check=full to see details of leaked memory

then this means you forgot a delete somewhere.

Open up dynamic.h and dynamic.cpp for this part (totally separate from the Complex stuff, so it logically should go in a new module).
Python’s range function is pretty handy for generating a list of integers, but C++ doesn’t have an equivalent. Let’s write one! The table below shows example function calls. Note that if the array would be empty, a NULL pointer should be returned.
Function Call Resulting Array
range(0, 3, 1, size) [0, 1, 2]
range(0, 3, 2, size) [0, 2]
range(-2, 2, 1, size) [-2, -1, 0, 1]
range(3, 0, 1, size) NULL
range(3, 0, -1, size) [3, 2, 1]
range(0, 0, 0, size) NULL
where the size in the function call is a reference to an integer that should be updated with the size of the array.
Implement the function range to do the following:
1. Calculate the size of the array that will be needed to hold all the numbers from start to end counting by step. Do not include the end value. Store this size in the size parameter.
2. Allocate the array on the heap using new.
3. Fill the array with the appropriate values.
4. Return the pointer to the array.
Call your function from main with a set of test values. You may want to also write a helper function to print out the array in a loop, as simply couting an array will just show you the memory location.
Finally, don’t forget to free the memory using the array syntax:
```
int size;
int *arr = range(0, 3, 1, size);
// do stuff with arr
delete [] arr;
```
When you are satisfied with your own testing, try running the test code by building it in the top-level labs directory:
```
$ make lab=dynamic
```
Tips: This is not as trivial as it seems! Pay attention to:
- Calculating the size of the array, especially when step is not an even divisor of end - start. The ceil function from the cmath library may be useful.
- step of 0
- start and end being the same value
- Your loop condition when filling the array, especially when step is negative
One thing that can be helpful in tracking down errors is running the test program in gdb and setting a breakpoint at the range function, e.g. (from your top-level labs directory):
```
$ gdb ./test
(gdb) break range
(gdb) run
```
You can then repeatedly hit c to call the function until the test fails.

Function Call	Resulting Array
`range(0, 3, 1, size)`	`[0, 1, 2]`
`range(0, 3, 2, size)`	`[0, 2]`
`range(-2, 2, 1, size)`	`[-2, -1, 0, 1]`
`range(3, 0, 1, size)`	`NULL`
`range(3, 0, -1, size)`	`[3, 2, 1]`
`range(0, 0, 0, size)`	`NULL`

Extra: stack overflow

It’s not just a website! Try the following to see what happens:

Declare an array of 10e6 integers on the stack, then cout the address of the first element
Compile and run your code. What warnings or errors occur?
Now change the initialization to allocate memory on the heap instead, then cout the address of the first element. Why is it different?
Don’t forget to delete your array when you’re done!
Remember, to free the memory for a dynamically allocated array you need to use delete [] instead of just delete

More extras: Tracing memory errors

Each program segment below contains at least one error which may cause the program to crash or behave unexpectedly. Try to trace the code and predict where the problem is manually before running it. You can test your prediction by visualizing each code segment in Python Tutor

double *pd1;
double *pd2;

pd1 = new double;
pd2 = new double;

*pd1 = 100.0;
pd2 = pd1;

delete pd1;
delete pd2;

int *ptr1;
int *ptr2;

ptr1 = ptr2;
ptr2 = new int;

cin >> *ptr2;
cout << *ptr1;

delete ptr2;

int *ptr1;
int *ptr2;

ptr1 = new int;
ptr2 = ptr1;
cin >> *ptr1;
delete ptr2;

cout << *ptr1;

bool gimme_gimme();

int main() {
    bool done = false;

    while (!done)
        done = gimme_gimme();

    return 0;
}

bool gimme_gimme() {
    bool done;
    double *dyn = new double;

    cout << "Gimme: ";
    cin >> *dyn;
    cout << "You gamee " << *dyn;

    done = *dyn < 0.0;
    return done;
}

int x;
int *p;

cout << "Enter a number: ";
cin >> x;

if (x % 2 == 0)
    p = &x;
else {
    p = new int;
    *p = x + 1;
}

cout << "The smallest even >= " << x << " is " << *p << endl;
delete p;