# Intro to Dynamic Allocation

1. Static allocation:

Static allocation is when the amount of space for an array or some other construct is determined at compile-time. The disadvantage of this is that we don't always know how big an array we need until the program is run.

With static allocation, if we wanted a char array `label` to be able to hold various strings, then we would have to determine the length of all of the strings that would be held in `label` and then make that array large enough to accommodate the largest string.

For example, if we need to store labels like: `"Single"`, `"Married (J)"`, `"Married (S)"`, and `"Head of Household"`... What would the size of the array needed to hold these things be?

```char label[??];
```

In some cases, we can't determine the maximum size at compile-time. For example, suppose labels are entered by user when the program is run. There is no size that we can choose for the array while ensuring that the user doesn't type in something longer.

2. Array local variables must be of a static size:

Sometimes, we need to create a string whose size we won't know until the program runs (i.e., until run-time).

Suppose we want to make a copy of a string that was passed to a function. The following is illegal.

```void foo(char text[])
{
char copy[strlen(text) + 1];  /* WRONG--Not valid! */

/* copy 'text' into 'copy' */

copy[0] = 'A';

...
}
```

because the length of the string, i.e., `strlen(text)`, cannot be determined at compile-time.

3. Library routines for dynamic allocation:

C provide a set of routines for allocating space for any type of object at run-time. Generally, we use use a pair of functions (prototyped in `stdlib.h`) named `malloc()` and `free()`.

These functions work as follows:

• `ptr = malloc(bytes)`

You tell `malloc()` how many bytes of memory to allocate and it returns a pointer to the beginning of a contiguous chunk of memory.

When `malloc()` cannot find enough memory, it returns the `NULL` pointer.

• `free(ptr)`

When you are done with that memory you need to free it so that the space can be given out by future calls to `malloc()`.

For example, we want to dynamically allocate an array of integers. Suppose, the variable n holds the number of integers we need. Remember, we could not do something like:

```int grades[n];  /* WRONG!! n is a variable. */
...
...
```

because n is a variable, and thus, its value is not known until the program runs.

Instead, we'd use `malloc()`, as in:

```int *grades;
...
grades = (int *)malloc(sizeof(int) * n);
...
exit(1);  /* End program, returning error status. */
}
...
...
free(grades);  /* Deallocate the space since */
/* we're done with it.        */
...
/* has been freed!!!          */
```

Remember, `malloc()` always takes the number of bytes needed. So, we need n `int`'s, where the number of bytes used by an `int` is given by `sizeof(int)`. Thus, we need `sizeof(int) * n` bytes in total.

The pointer returned from `malloc()` is a generic pointer, so we cast it to the right type (here, ```int *```), although strictly this is not necessary in C.

When we are done with the dynamic array, we `free()` it. We should not use that space afterwards.

4. Making a copy of a string:

Now, suppose we wanted to make a copy of a string passed to a function, here's how we could use dynamic allocation to do so:

```#include <stdlib.h>

void foo(char text[])
{
int num_chars;
char *copy;

num_chars = strlen(text) + 1;

/* Allocate room for the string. */
copy = (char *)malloc(sizeof(char) * num_chars);

/* Copy the contents of the string. */
strcpy(copy, text);

...

/* Use the copy. */

copy[0] = 'A';

...

/*
* Don't waste memory.  We are done with the
* dynamically-allocated string, so free it.
*/
free(copy);
}
```

Writing code like this every time we need a dynamically-allocated string is a hassle. Let's think about writing a library with functions that handle this task for us.

5. Our string library:

Let's write a string library for this task. We call the string library mystrlib. This means we should have two source code files named what?

The string library will consist of 3 functions: NewStr, ConcatStr and FreeStr. Here is how the library functions should work:

• `NewStr`

This function allocates enough space for the string passed to it, copies the text of the string passed to it, and returns a pointer to that dynamically-allocated string.

• `ConcatStr`

This function allocates enough space for the concatenation of the two strings passed to it, copies the text of the both strings into that new space, and returns a pointer to that dynamically-allocated string.

• `FreeStr`

Deallocates the space for the string when we are done with it.

We've provided a header file and file for the function definitions for you. There is also a test program that you may use to test the library. Finally, there is a Makefile that generates the executable strtest.

Note that we include the system header file `stdlib.h` where we need `malloc()` and `free()` (it also provides the `NULL` pointer).
```str1 is: This is the value