[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.
