[MUSIC PLAYING] DOUG LLOYD: OK so a suggestion before starting here. If you haven't watched the video on pointers you might want to do so first. Because this video is another way of working with pointers. 

So it's going to talk about some concepts that we cover in the pointers video, and we're going to gloss over them now, assuming that they're already sort of understood. So that's just your fair warning that if you're seeing this video and you haven't seen the pointers video, it might sort of fly over your head a little bit. And so it might be better to watch it in that order. 

So we have already seen one way to work with pointers, which is we declare a variable, and then we declare another variable, a pointer variable, that points to it. So we've created a variable with a name, we've created a second variable with a name, and we point that second variable at that first. This sort of has a problem though, because it requires us to know exactly how much memory we're going to need the moment our program is compiled. 

Why is that? Because we need to be able to name or identify all of the possible variables we might encounter. We might have an array that might be able to hold a lot of information, but it's still not exactly precise enough. What if we don't know, what if we have no idea how much we'll need at compile time? Or what if our program will run for a really long time, accepting various user data, and we can't really estimate whether we're going to need 1,000 units? 

It's not like we can say at the command line enter how many items you think you'll need. Well what if that guess is wrong? Dynamic memory allocation sort of allows us the way to get around this particular problem. And the way it does it is by using pointers. 

We can use pointers to get access to dynamically allocated memory, memory that is allocated as your program is running. It's not allocated at compile time. When you dynamically allocate memory it comes from a pool of memory known as the heap. Previously all the memory we've been working with in the course has been coming from a pool of memory known as the stack. A good way to generally keep in mind-- and this rule doesn't always hold true, but pretty much almost always holds true-- is that any time you give a variable name it probably lives on the stack. And any time you don't give a variable a name, which you can do with dynamic memory allocation, it lives on the heap. 

Now I'm kind of presenting this as if there's these two pools of memory. But you may have seen this diagram, which is generally a representation of what memory looks like, and we're not going to care about all the stuff at the top and the bottom. What we care about is this part in the middle here, heap and stack. As you can see by looking at this diagram, these actually aren't two separate pools of memory. It's one shared pool of memory where you start, in this visual you start at the bottom and start filling up from the bottom with the stack, and you start at the top and start filling up from the top down with the heap. But it really is the same pool, it's just different spots, different locations in memory that are being allocated. And you can run out of memory by either having the heap go all the way to the bottom, or have the stack go all the way to the top, or having the heap and the stack meet up against each other. All of those can be conditions that cause your program to run out of memory. So keep that in mind. When we talk about the heap and the stack we are really talking about the same general chunk of memory, just different portions of that memory. 

So how do we get dynamically allocated memory in the first place? How does our program get memory as it's running? Well C provides a function called malloc, memory allocator, which you make a call to, and you pass in how many bytes of memory that you want. So if your program is running and you want an integer runtime, you might mallock four bytes of memory, malloc parentheses four. 

mallock will go through looking through the heap, because we're dynamically allocating memory, and it will return to you a pointer to that memory. It doesn't give you that memory-- it doesn't give it a name, it gives you a pointer to it. And so that's why again I said that it's important to maybe have watched the pointers video before we get too far into this. So malloc's going to give you back a pointer. 

If mallock can't give you any memory because you've run out, it'll give you back a null pointer. Do you remember what happens if we try and dereference a null pointer? We suffer a seg fault, right? That's probably not good. 

So every time you make a call to malloc you always, always need to check whether or not the pointer it gave you back is null. If it is, you need to end your program because if you try and dereference the null pointer you're going to suffer a segmentation fault and your program is going to crash anyway. So how do we statically obtain an integer? 

int x. We've probably done that a bunch of times, right? This creates a variable called x that lives on the stack. How do we dynamically obtain an integer? Int star px equals malloc 4. 

Or more appropriately we'd say int star px equals malloc size of int, just to throw some fewer magic numbers around our program. This is going to obtain for us four bytes of memory from the heap, and the pointer we get back to it is called px. And then just as we've done previously we can dereference px to access that memory. How do we get an integer from the user? We can say int x equals get int. That's pretty straightforward. What if we want to create an array of x floats that live on the stack? float stack_array-- that's the name of our array-- square brackets x. That will create for us an array of x floats that live on the stack. We can create an array of floats that lives on the heap, too. The syntax might look a little more cumbersome, but we can say float star heap_array equals malloc x times the size of the float. I need enough room to hold x floating point values. So say I need 100 floats, or 1,000 floats. So in that case it would be 400 bytes for 100 floats, or 4,000 bytes for 1,000 floats, because each float takes up four bytes of space. 

After doing this I can use the square bracket syntax on heap_array. Just as I would on stack_array, I can access its elements individually using heap_array zero, heap_array one. But recall the reason we can do that is because the name of an array in C is really a pointer to that array's first element. So the fact that we're declaring an array of floats on the stack here is actually a bit misleading. We really are in the second line of code there also creating a pointer to a chunk of memory that we then do some work with. 

Here's the big problem with dynamically allocated memory though, and this is why it's really important to develop some good habits when you're working with it. Unlike statically declared memory, your memory is not automatically returned to the system when your function is done. So if we have main, and main calls a function f, when f finishes whatever it's doing and returns control of the program back to main, all of the memory that f used is given back. It can be used again by some other program, or some other function that gets called later on in main. It can use that same memory over again. 

If you dynamically allocate memory though you have to explicitly tell the system that you're done with it. It'll hold onto it for you, which could lead to a problem of you running out of memory. And in fact we sometimes refer to this as a memory leak. And sometimes these memory leaks can actually be really devastating for system performance. 

If you are a frequent internet user you might use certain web browsers, and I won't name names here, but there are some web browsers out there that are notorious for actually having memory leaks that don't get fixed. And if you leave your browser open for a very long period of time, days and days, or weeks, you sometimes might notice that your system is running really, really slowly. And the reason for that is that the browser has allocated memory, but then not told the system that it's done with it. And so that leaves less memory available for all of your other programs to have to share, because you're leaking-- that web browser program is leaking memory. How do we give memory back when we're done with it? Well fortunately it's a very easy way to do it. We just free it. There's a function called free, it accepts a pointer to memory, and we're good to go. 

So let's say we're in the middle of our program, we want to malloc 50 characters. We want to malloc an array that can capable of holding 50 characters. And when we get a pointer back to that, that pointer's name is word. We do whatever we're going to do with word, and then when we're done we just free it. And now we have returned those 50 bytes of memory back to the system. Some other function can use them. We don't have to worry about suffering a memory leak because we have freed word. We've given the memory back, so we're done working with it. So there are three golden rules that should be kept in mind whenever you're dynamically allocating memory with malloc. Every block of memory that you malloc must be freed before your program finishes running. Now again, in the appliance or in the IDE this sort of happens for you anyway when you-- this will happen anyway when your program is terminated, all the memory will be released. But it's generally good coding practice to always, when you're done, free what you have mallocd. 

That said, only things that you've mallocd should be freed. If you statically declare an integer, int x semi-colon, that lives on the stack, you don't then want to free x. So only things that you've mallocd should be freed. 

And lastly, don't free something twice. That can lead to another weird situation. So everything that you've mallocd has to be freed. Only things that you've malloc should be freed. And don't free something twice. 

So let's go through an example here of what some dynamically allocated memory might look like mixed in with some static memory. What might happen here? See if you can follow along and guess what's going to happen as we go through all these lines of code. 

So we say int m. What happens here? Well this is pretty straightforward. I create an integer variable called m. I color it green, because that's the color that I use when I'm talking about integer variables. It's a box. It's called m, and you can store integers inside of it. 

What if I then say int star a? Well that's pretty similar. I'm creating a box called a. It's capable of holding int stars, pointers to integers. So I'm coloring it green-ish as well. 

I know it has something to do with an integer, but it's not itself an integer. But it's pretty much the same idea. I've created a box. Both of these right now live on the stack. I've given them both names. 

int star b equals malloc size of int. This one might be a little tricky. Take a second and think about what you would expect to happen on this diagram. int star b equals malloc size of int. 

Well this doesn't just create one box. This actually creates two boxes. And it ties, it also establishes a point in a relationship. We've allocated one block of memory on the heap. Notice that the top right box there does not have a name. 

We mallocd it. It exists on the heap. But b has a name. It's a pointer variable called b. That lives on the stack. 

So it's a piece of memory that points to another one. b contains the address of that block of memory. It doesn't have a name otherwise. But it points to it. So when we say int star b equals malloc size of int, that right there, that arrow that popped up on the right side there, that whole thing, I'll have it appear again, is what happens. All of that happens in that single line of code. Now we'll get little more straightforward again. a equals ampersand m. Do you recall what a equals ampersand m is? Well that's a gets m's address. Or put more diagrammatically, a points to m. 

a equals b. OK so here's another one. A equals b. What's going to happen to the diagram this time? 

Well recall that the assignment operator works by assigning the value on the right to the value on the left. So instead of a pointing to m, a now points to the same place that b points. a doesn't point to b, a points where b points. 

If a pointed to b that would have been a equals ampersand b. But instead a equals b just means that and b are now pointing to the same address, because inside of b is just an address. And now inside of a is the same address. m equals 10, probably the most straightforward thing we've done in a little bit. Put the 10 in the box. Star b equals m plus 2, recall from our pointers video what star b means. We're going to dereference b and put some value in that memory location. In this case 12. 

So when we dereference a point of recall we just travel down the arrow. Or put another way, we go to that memory address and we manipulate it in some way. We put some value in there. In this case star b equals m plus 2 is just go to the variable pointed to by b, go to the memory pointed to by b, and put m plus 2 in there, 12. 

Now I free b. What happens when I free b? Remember what I said free means. What am I saying when I free b? 

I'm done working with it, right? I essentially give up the memory. I give it back to the system. I don't need this anymore is what I'm telling them, OK? 

Now if I say star a equals 11 you can probably already tell that something bad is going to happen here, right? And indeed if I tried that I probably would suffer a segmentation fault. Because now, although previously that chunk of memory was something that I had access to, at this point now I'm accessing memory that is not legal for me to access. 

And as we will probably recall, when we access memory that we're not supposed to touch, that's the most common cause of a segmentation fault. And so my program would crash if I tried to do this. So again it's a good idea to get good practice and good habits ingrained when working with malloc and free, so that you don't suffer segmentation faults, and that you use your dynamically allocated memory responsibly. 

I'm Doug Lloyd this is CS50.