MYF

[RA] Ch12 Dynamic Allocation

Posted on | In | | Visitors

Reading Assignment: All of Programming Chapter 12 Dynamic Allocation

If you initialize the array with the size from function parameter, it won’t work. This is because the array is created on the stack. Variables on the stack exist only until the function ends, at which point, the stack frame essentially disappears.

You might want to write a function to read the information, allocating memory to hold the results in some combination of arrays and structs, and return the result to the caller. There is a way: dynamic memory allocation.

Dynamic memory allocation request a specific amount memory to be allocated on the heap. The programmer must explicitly free the memory when he is done using it.

Unlike the code and static data segment, the heap changes sizes as the program runs-thus the term “dynamic memory allocation”.

malloc

Calling this function is how you allocate memory dynamically. The malloc function teaks one argument telling it how much memory is needed and it returns a pointer to that allocated memory in the form of a void *.

How Many Bytes?

Writing a specific number of bytes is never correct for two reasons:

  • Portability. The ability to compile your code on a different system and still have it work correctly. Although an int takes up 4 bytes, but it may take 8 on a different computer.
  • Maintainability. You may have to go find and changes ever place in the code where you assume the size is 100 bytes.

You should use sizeof operator to calculate the space for entire array.

The very best way to call malloc would be:

1
int *myArray = malloc(6 * sizeof(*myArray));

This way, if someone decides later that the array should actually be of type char or double, the call to malloc would continue to be correct with no additional changes.

Video Example

1
2
int *p;
p = malloc(6 * sizeof(*p));

Failure

If heap do not have enough memory to fulfill the current request. In such cases, malloc will return NULL instead of a valid pointer to a location on the head.

Fixing initArray

1
2
3
4
5
6
7
8
9
int *initArray(int howLarge) {
    int *array = malloc(howLarge * sizeof(*array));
    if (array != NULL) {
        for(int i = 0; i < howLarge; i++){
            array[i] = i;
        }   
    }
    return array;
}

Whenever you write a function where you would not honw how the error should be handled, making the caller handle the error is a good stratege.

Mallocing More Complexes Structures

1
polygon_t *answer = malloc(sizeof(*answer));

Shallow vs Deep Copying

If we make it p2 = p1, it only make p2 point at p1. It is shallow copying.

If we were to use malloc, we could create a copy, and we also need to copy the filed inside of it. Deep copy means having distinct objects, we do not just copy pointers, but allocate new memory for and make deep copies of whatever the pointers point to.

Free

Unlike memory allocated on the stack, memory on the heap must be explicitly freed by the programmer. If the code says free(p), you should follow the arrow for p, and then erase that entire block of memory. If p is NULL, nothing happens. If p points at something other than the start of a block in the heap, it is an error and bad things will happen.

Memory Leaks

When you lose all references to a block of memory, and the memory is still allocated, you have leaked memory. In real programs, memory leaks present significant performance issues. When you write program, you should run it in valgrind, and be sure you get the following message at the end.

All heap blocks were freed – no leaks are possibile

A Dynamic Memory Allocation Analogy

lockers on bus.

Common Problems with Free

Trying to “free” the same lockers twice is a problem. In the case of memory allocation, trying to free the same block of memory more than one time is called double freeing. It will lead to crash or stranger symptoms, like there may be problems when you call malloc next time.

malloc actually allocates more memory than you ask for, and keeps a bit for itself, right before the start of what it gives you. If you asking for 16 bytes, malloc may give you 32, the first 16 contain its information about the block, and the next 16 it gives you to use. Therefore, you can not give free a mid value in the range, and ask the system to free it.

A third common mistake is that memory to be freed is not on the heap.

Realloc

realloc effectively resizes a malloced region of memory. The argument to realloc are the pointer to the region in memory that you wish to resize and new size you wish the region in memory to have. If no area in the heap of the requested size is available, realloc returns NULL.

If realloc fails, it returns NULL, but does not free the memory that was passed in to it.

Beyond malloc, free, realloc, there are a few more standard functions available for memory allocation, such as calloc.

Getline

getline is a C function available in the stdio.h. It reads a single line from the file specified in its third argument, stream. It does this by reading characters from the file repeatedly until it sees the character \n. After reading the newline character, it places \0. The difference to fgets is that getline allocates space for the string as needed.

getline is different from gets, which arises inthe fact that getline use malloc and realloc to allocate/enlarge the buffer. The linep parameter points at a pointer. If *linep is NULL, getline mallocs a new buffer. If *linep is not NULL, getline uses that buffer to start with. If the initial buffer is no long enough, getline reallocates the buffer as needed. Whenever getline mallocs or reallocs the buffer, it updates *n to reflect the number of bytes allocated. It also updates *linep to point at the new buffer. When the getline function returns, *linep is a pointer to the string read from the file. It returns the number of bytes read if success, and -1 if error.

1
2
3
4
5
6
7
8
9
10
11
int main(void) {
    size_t sz = 0;
    ssize_t len = 0;
    char * line = NULL;
    FILE *f = fopen("name.txt", "r");
    while((len = getline(&line, &sz, f)) >= 0) {
        printf("%s", line);
    }
    free(line);
    return EXIT_SUCCESS;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int main(void){
    char **lines = NULL;
    char *curr = NULL;
    size_t sz;
    size_t i = 0;
    while(getline(&curr, &sz, &stdin) >= 0) {
        lines = realloc(lines, (i+1)*sizeof(*lines));
        lines[i] = curr;
        curr = NULL;
        i++;
    }
    free(curr);
    sort(lines, i);
    for(size_t j = 0; j < i; j++){
        printf("%s", line[j]);
        free(lines[j]);
    }
    free(lines);
    return EXIT_SUCCESS;
}