Algorithms in a Nutshell

Manual Memory Allocation

Most modern programming languages allow the programmer to allocate dynamic memory from the Heap (as opposed to the Stack) during the execution of a program. Consider the C program in Example 3-1.

Example 3-1. Sample program that allocates memory

#include <stdlib.h>
#include <string.h>
void f(char *inner) {
  char temp[11];
  strcpy (temp, "algorithms");
  int i;
  for (i=0; i<11; i++) {
    inner[i] = temp[i];
  }
}
int main (int argc, char **argv) {
  char *ar1  = malloc(132);
  char *ar2  = malloc(132);
  int i = 17, j;
  f (ar2);
  return 0;
}

When the program executes, variables that are local to a function (such as argc, and argv for main) are assigned to locations on the Execution Stack, which stores the progress of the program execution. Dynamically allocated memory (such as ar1 in main) is instead stored on the Heap, a separate region of memory available for allocation. The address of the variable determines where the memory can be found. In the example, one possible assignment of variables (on a Linux i686) is shown in Table 3-5.

Table 3-5. Addresses for symbols and variables

f variables	Addresses	main variables	Addresses	Global symbols	Addresses
f.inner	3221222728	main.argc	3221222796	&f	4195576
f.temp	3221222704	main.argv	3221222784	&main	4195648
f.i	3221222700	main.ar1	3221222776
		main.ar2	3221222768
		main.i	3221222764
		main.j	3221222760
		*main.ar1	5246992
		*main.ar2	5247136

Note how the address values are all near one another, ...