Last time, we learned how to dynamically allocate memory when we needed it and we used a very simple example where we allocated the memory and ran our entire program and then freed that memory, and that was fine to learn how dynamic memory allocation works. But we're regularly going to run our program and discover that we need more memory as our program runs. Learning how to get that additional memory is what this lecture is about. The process that we follow with the code in this lecture will probably remind you some of dynamic arrays because there are lots of parallels between the approach that we're using here, and the approach we used for dynamic arrays. We're going to have a grow amount, a factor of two. So each time that we need to get more memory we will double the memory we have. As we discussed in dynamic arrays, people have empirically determined that data least reasonable because growing memory costs and we don't want to do it too often. But, we want to do it often enough, it's hard to optimize that particular thing but this is a reasonable approach to use. Just as we needed in dynamic arrays, we need to keep track of how many valid values we have stored and we need to keep track of how many values we can store. Here's where I'm allocating a pointer, but I should tell you what we're actually doing. We're going to let the user enter numbers until they enter a negative one and we're going to store those numbers in memory just in case after they're done entering those numbers, we want to go process them in some way or something like that. So that's the big idea. I could have led with that but I didn't. So here, we're going to allocate a pointer to integers using malloc and it's capacity times the size of an int. We know we're storing int and we know we have capacity here. So at this point on this computer with this compiler, I am allocating eight bytes of memory. As we always should, we'll check for allocation failure and quit if we have allocation failure. We initialize n equal to zero and is the variable that we're going to use to store the user's input at least temporarily, and we're going to use it to push us into the while loop the first time. So while n is not equal to negative one, remember the user enters negative one to exit this loop, that's sometimes called a sentinel value because it watches to see when the user has decided to quit. So we need to make sure we explicitly set n to something that's not negative one to make sure we get into the while loop the first time. This should look really familiar to you based on the work we've done so far in the course, and now we're going to check to see if n is not equal to negative one here inside the while loop because we're about to add the number to the set of numbers we're storing in memory, but the user doesn't want negative one to be stored, that's just the indicator that they want to quit. Now, the user has just said they want to enter another number and that number right now is held in n. What if, count the number of numbers we're already storing is equal to capacity? That means we don't have any room for the number that is currently held in n, so now is the time for us to grow the memory that we have allocated for these numbers. The first thing I do is multiply by grow amount. So because grow amount is two, I'm doubling every time. The first time this happens, capacity changes from two to four because two times two is four. This is the new stuff or one of the new pieces for this lecture. We're now going to go get that bigger chunk of memory. This is realloc , it is not malloc, it's not memory allocation, it's reallocation. So it's called realloc, and we pass in two arguments. We pass in the pointer we currently have pointing at our current block of memory, and we pass in the size of the new block of memory we need. The reason we need to pass in p numbers is because we have some values that are already pointed to by p numbers, and we need to make sure those are included at the beginning of the new block of memory we get. Now if we're super lucky, there's memory that's available right after our existing block of memory and there's enough of it. So we don't actually have to do any copying. But, sometimes we're going to end up with a memory block that's twice our current size but it's somewhere else in memory. So, we need to know where p numbers is right now so we can get those valid values copied over into the new block of memory. Because realloc is allocating memory, we want to check for an allocation failure there. For demonstration purposes, I'm printing out when we allocate new memory, you typically wouldn't include that in your program, right? The user doesn't care that you've just allocated more memory, but for us to observe what's happening in the code, I'm printing it out as we run. Then, once we have made sure that p numbers points to a block of memory that's big enough, we do this. We take p numbers plus count, and remember even if count is one it's really going to be four when we're talking about ints. Here's the address of the next open space in the memory block that we're filling with numbers. We need to de-reference that address and set it to n. So the contents of the address p numbers plus count is set to n, and we increment count. Even though we're using pointers here, this is the same exact idea we used in dynamic arrays when we were adding an additional item to a dynamic array, whether or not we grew it. We're adding the new value here whether or not we grew the block of memory that p numbers point to. Let's go ahead and run it. I'll enter one into two and remember our capacity is two. We don't have to grow the block of memory yet because I could enter negative one right here, and if that's the case, then I'm good. I allocated eight bytes and eight bytes was exactly what I need. But if I say I want to add another number, remember our block of memory isn't big enough here. So we've reallocated, I have a new capacity that I can hold four things, and right now our p numbers points to the values one, two and three. I'll say I want to add four and I'm still okay. If I enter negative one I'm done but if I say I want to add five, I'm going to have to grow again, up to eight. As you can see, this will keep happening as I grow larger and larger doubling each time until the user finally says they want to quit. As always, when we're done with memory that we have explicitly allocated, we want to free that memory and null out the pointer to that block of memory. To recap, in this lecture we learned how to get more memory if we discover we need it as our program is running.
