Pointers and Memory Management

The memory

The memory is a large array of bytes, numbered 0,1,2,... up to some large number. Each byte holds a number from -128 to 127. Byte number 1 has address 1, byte number 2 has address 2, etc. Each thing that you store in the memory occupies some number of bytes. An ASCII character occupies one byte. An integer typically occupies four bytes. An array might occupy 1000 bytes. You refer to a collection of bytes by the address of the first byte in the collection. A program breaks its memory into a few areas, including the following. The static area The static part of memory holds your program, some constants that your program contains, and global variables. The program itself (a sequence of machine-language instructions) normally does not change during its execution. Constants are also unchanged. Global variables can be changed, but they are static in the sense that they do not move while the program runs; they stay in the same place in memory. The static portion of memory is called static because it is allocated once, when the program starts, and remains of the same size while the program runs. The static area is usually divided into two main parts. The first part, containing your program and constants such as string constants, is read-only, and your program is not allowed to change it. The second part, holding global variables, is allowed to be changed by your program. The run-time stack The run-time stack (often called simply the stack) holds information necessary to manage function calls. The local variables of functions are stored in the stack, along with extra information to allow a function to know, for example, where it should return control when it is done. When a function is called, it is automatically allocated as much memory as it needs in the stack. When the function returns, all of its memory in the stack is automatically deallocated, to be reused later for another function. This is important to remember. When a function returns, all of its local variables are taken away, and your program cannot continue to use them in any way. The heap The heap is an area of memory where a program can allocate and deallocate memory. The key difference between the stack and the heap is that memory is not deallocated from the heap until the program explicitly deallocates it. The heap is used to get memory that a program can continue to use even after the function that allocated the memory has returned.

Pointers

A pointer is a memory address. So, in a sense, a pointer is an integer. On a 32 bit machine, a pointer occupies four bytes. Pointers are not treated quite like integers in C/C++. Instead, a specialized set of operations is provided for them. What you can do with a pointer is look at or modify the memory at the address given by the pointer; compute pointers to memory cells around a given pointer; compare pointers to one another. Each pointer has a type. If T is a type, the type T* is the type of a pointer that points to something of type T. For example, type int* is the type of a pointer to an int. Operations on pointers Operation Meaning *p *p is the content of the memory at address p. The number of bytes that you fetch from the memory depends on the type of p. For example, if p has type char*, then *p is a one-byte quantity. If p has type long*, then *p is a four-byte quantity. Note that, if p has type T*, then *p always has type T, for any T. p+k Suppose that p is a pointer pointing to a type that occupies b bytes, and suppose that k is an integer. Then p+k is memory address p + b*k. For example, suppose that p is a pointer with memory address 100. If p has type char*, then p+2 is a pointer, also of type char*, with memory address 102. But if p has type long*, then p+2 is a pointer, also of type long*, with memory address 108. Notice that, if p has type long*, then p+1 points to the next long int in memory, just after the one pointed to by p, without overlap. p-k You can subtract an integer from a pointer. The result is similar to addition. For example, if p has type int* then p-1 points to the int that occurs just prior the int pointed to by p in memory, without overlap. p[k] p[k] abbreviates *(p+k). So p[0] is the same as *p. p[1] is the same as *(p+1); it is the thing in memory just after the thing pointed to by p. Note: Memory address 0 is not available to application programs. It is used as a special pointer value, called the null pointer. Normally, NULL is another name for 0. You use it when you want the null pointer. Only use NULL as a null pointer, not as a general replacement for the number 0.

Pointer variables and constants

Declaring pointer variables You must be careful when declaring pointer variables. Each variable is said to be a pointer or not to be a pointer independently of the others. If you write int *x, *y; then you declare x and y each to be pointers to integers. If you write int *x, y; then you declare x to have type int*, but y to have type int. There is no * on y, so y is not a pointer. Spacing in your program does not affect this. So if you write int* x, y; it might look like x and y are each pointers, but in fact only x is a pointer; y is an int. To avoid this problem, you might want to declare only one pointer variable per line. Alternatively, use a typedef, discussed later. Assignment using pointers When you assign a value to a pointer variable, you change the pointer variable itself. If you what to modify the memory pointed to by p, assign to *p. For example, *p = 20; goes to the memory whose address is in variable p and puts 20 there. If p holds address 5000, the this stores 20 at address 5000 in memory. Suppose that you have declared p as follows. int *p; and suppose that you have put memory address 3000 into p. If you perform assignment p[1] = 72; what happens to the memory? Suppose that an int occupies four bytes. Expression p[1] abbreviates *(p+1). Since p holds address 3000, address p+1 is really 3004. So 72 is stored in the four bytes starting at address 3004. Constant pointers You can declare pointer variables to be constant, but the const modifier means something different for a pointer from what it means for a nonpointer. If you declare const char* p; then you are allowed to change p, but you are not allowed to use p to change the memory that p points to. So you can fetch p[1], but you cannot set p[1] = a. Any time you have a pointer variable, you really have two memory locations: the memory address that the variable refers to (stored in the variable) and the memory address of the pointer variable itself. You might want to indicate that either or both of those memory slots should not be changed. You can do that by putting the const modifier after the type that it modifies. Here are some declarations of variable p that illustrate. Declaration Meaning int const * p; The const modifier applies to the type int that p points to. You are not allowed to assign a new value to *p. int * const p = ...; The const modifier applies to type int*. You are not allowed to change the address that is in variable p, but you can store something into *p. (The initialization of p is required here, but is not shown in detail.) int const * const p =...; You cannot modify p or *p. For your convenience, you can move the const modifier before the beginning of the type. The compiler moves it after the first part of the type. So const int* is the same as int const *. Getting the address of a variable If x is a variable, then &x is the address of x (a pointer). If x has type int, for example, then &x has type int*. You can use this to initialize a pointer. For example, int x; int* p = &x; makes pointer variable p hold the address of x. You must be very cautious using the & operator. There are important int* f() { int x; return &x; } As soon as the function returns, variable x is lost. But the address of x is being returned to another function that is still alive. The address &x that is returned will live longer than the variable x to which it points. What is returned is called a dangling pointer: a pointer to memory that is no longer owned by your program, or that has been taken away from you. Using dangling pointers can yield very strange behavior. What if you have a pointer variable p, and you get its address? If p has type int*, then &p has type int**. That is, it is a pointer to a pointer. &p is the address of a variable that contains a pointer value.

Allocating memory in the heap

The usual way to get a pointer is not to get the address of a variable that is in the run-time stack, but instead to get the address of some memory in the heap. To get memory from the heap, you can use either C or C++ style. C++ style is the most pleasant by far. Memory allocation in C++ Suppose that T is a type. Expression new T performs the following steps. It finds a chunk of memory in the heap that is large enough to hold a variable of type T. It indicates that this memory is now in use (by your program). It produces, as the value of the expression, the memory address of the first byte in the chunk. For example, to get a pointer to an int, you might write int* q = new int; As you can see, q is a variable of type int*. That is, it is a pointer to an int. It is initialized to point to newly allocated memory in the heap. Keep in mind that expression new int allocates the memory that variable q is made to point to. It does not allocate variable q itself. You are not required to use new every time you create a pointer variable. For example, int* q = new int; int* r = q; creates two pointer variable, q and r, and makes them hold the same memory address (the address of some newly allocated memory in the heap). Memory allocation in C C has a different way of allocating memory. It is recommended that you use the C++ style. However, you are likely to see the C style used occasionally. In C, memory is allocated by calling a system function called malloc. malloc(n) returns n bytes in the heap and returns a pointer to the first of those bytes. To allocate an integer, you could write int* p = (int*)malloc(4); The malloc function returns a pointer of the special type void*, indicating a pointer to an unknown type of thing. You must cast the pointer to the appropriate type for your use. Here, the result is cast to type int* by placing (int*) in front of it. When using malloc, you should not guess at how many bytes something requires. You can use the built-in operator sizeof to compute the number of bytes needed by a particular type. So a more reasonable way to allocate an integer is int* p = (int*)malloc(sizeof(int)); What if I run out of memory? If you try to allocate memory in the heap (either via new or malloc) and there is no more memory available, you will get a null pointer as the result. It is a good idea to check that your pointer is not null after doing an allocation. In practical terms, however, if you run out of memory there is little that you can do to recover. Anything that you try to do will probably need some memory, and none is available.

Pointer diagrams

To use pointers, you will need to do careful hand simulations. You usually draw a pointer variable as a box that contains one end of an arrow. The arrow points to another box, representing the memory whose address is in the pointer variable. For example, after performing int* q = new int; int* r = q; *q = 50; you will have the following diagram. -- ---- q| -|------->| 50 | -- ---- ^ -- | r| -|---------- -- Always draw careful pointer diagrams when using pointers! Sloppiness, or failure to draw diagrams at all, will result in programs that do not work.

Freeing memory

The malloc function and new operator make use of memory managers that keep track of available memory. They might use the same memory manager, but might use different ones. When you are done with memory that you allocated in the heap using new or malloc, you can return it to the memory manager so that it can be used again later. Returning memory is called freeing the memory or deallocating it. Suppose that pointer p points to memory that you have allocated. If you allocated that memory using new, you write delete p; to return that memory to the system. If you allocate that memory using malloc, use free(p); It is important only to return something to the memory manager that was allocated by that memory manager. The rule is If you say delete p, make sure that p is a memory address that was given to you by an expression of the form new T for some type T. If you say free(p), make sure that p is a memory address that was given to you by malloc. Never use delete or free on a memory address that is in the run-time stack or static area of memory. Be very careful about deallocating memory. Keep in mind that you can have more than one variable that holds a pointer to a given piece of memory. If you deallocate the memory, all of those pointers become stale. They continue to hold memory addresses, but the memory to which they refer does not belong to you any more. You have no idea what that memory will be used for after it has been deallocated. A pointer that points to deallocated memory is called a dangling pointer. Problems that occur from the use of dangling pointers are among the most devastating, and most difficult to eliminate, of all the problems that you can have. By avoiding them with care, you will not be subjected to the pain of finding them by laborious debugging. If you fail to deallocate memory that you have allocated, and you let that memory become inaccessible to you, the system will not take that memory back automatically. The system will presume that your program still needs the memory. The result is a memory leak. Memory leaks are quite benign for programs that do not use much memory, but can be deadly in long runs, when your program will run out of memory.