Dynamic Memory Allocation

## Learning Objectives - Understand stack vs heap - Master malloc, calloc, realloc, free - Learn common memory mistakes - Work with dynamic arrays ## Memory Layout ```text +------------------+ High Address | Stack | Local variables, function calls | | | | v | | | | ^ | | | | | Heap | Dynamic allocation (malloc) | | +------------------+ Low Address | Uninitialized | | Initialized | | Code Segment | +------------------+ ``` ## Stack vs Heap ### Stack (Automatic) ```c void function(void) { int arr[1000]; // Allocated on stack // Freed automatically when function returns } ``` ### Heap (Dynamic) ```c void function(void) { int *arr = malloc(1000 * sizeof(int)); // Allocated on heap // Must free manually! free(arr); } ``` ## malloc ### Basic Usage ```c #include int *ptr = (int*)malloc(sizeof(int)); if (ptr == NULL) { // Handle allocation failure return 1; } *ptr = 42; printf("%d\n", *ptr); free(ptr); ptr = NULL; ``` ### Allocate Array ```c int *arr = (int*)malloc(5 * sizeof(int)); if (arr == NULL) { return 1; } for (int i = 0; i < 5; i++) { arr[i] = i * 10; } free(arr); ``` ### malloc Does Not Initialize ```c int *arr = (int*)malloc(5 * sizeof(int)); // Values are UNINITIALIZED (garbage) int *arr2 = (int*)calloc(5, sizeof(int)); // Zero-initialized ``` ## calloc ### calloc Syntax ```c int *arr = (int*)calloc(5, sizeof(int)); // All 5 elements are 0 for (int i = 0; i < 5; i++) { printf("%d ", arr[i]); // 0 0 0 0 0 } free(arr); ``` ### Syntax ```c void *calloc(size_t num, size_t size); // num: number of elements // size: size of each element ``` ## realloc ### Resize Memory ```c int *arr = (int*)malloc(5 * sizeof(int)); // Fill array for (int i = 0; i < 5; i++) { arr[i] = i; } // Resize to 10 elements int *newArr = (int*)realloc(arr, 10 * sizeof(int)); if (newArr == NULL) { free(arr); // Original still valid return 1; } arr = newArr; // Update pointer // New elements are uninitialized for (int i = 5; i < 10; i++) { arr[i] = i * 10; } free(arr); ``` ### Shrink Memory ```c int *arr = (int*)malloc(10 * sizeof(int)); // ... use first 5 elements ... int *newArr = (int*)realloc(arr, 5 * sizeof(int)); // Can safely shrink even if newArr == arr ``` ### Common Pattern: Grow Array ```c int *arr = NULL; int size = 0; int capacity = 0; int value; while (scanf("%d", &value) == 1) { if (size >= capacity) { capacity = capacity == 0 ? 1 : capacity * 2; int *newArr = (int*)realloc(arr, capacity * sizeof(int)); if (newArr == NULL) { free(arr); return 1; } arr = newArr; } arr[size++] = value; } ``` ## free ### free Basic Usage ```c int *ptr = (int*)malloc(sizeof(int)); *ptr = 42; free(ptr); ptr = NULL; // Always set to NULL after free ``` ### free(NULL) is Safe ```c int *ptr = NULL; free(ptr); // No-op, perfectly safe ``` ## Common Mistakes ### Memory Leak ```c void leak(void) { int *ptr = malloc(sizeof(int)); *ptr = 42; // Missing free(ptr)! } ``` **Detected with valgrind:** ```bash valgrind --leak-check=full ./program ``` ### Double Free ```c int *ptr = malloc(sizeof(int)); free(ptr); free(ptr); // Undefined behavior! ``` ### Use After Free (Dangling Pointer) ```c int *ptr = malloc(sizeof(int)); *ptr = 42; free(ptr); printf("%d\n", *ptr); // Undefined behavior! ``` ### Not Checking NULL ```c int *ptr = (int*)malloc(sizeof(int)); *ptr = 42; // Crash if malloc returns NULL! ``` ### Partial Free ```c int **grid = (int**)malloc(10 * sizeof(int*)); for (int i = 0; i < 10; i++) { grid[i] = (int*)malloc(10 * sizeof(int)); } // Wrong: only frees outer array free(grid); // Correct: free inner arrays first for (int i = 0; i < 10; i++) { free(grid[i]); } free(grid); ``` ## Dynamic 2D Arrays ### Array of Pointers ```c int **createMatrix(int rows, int cols) { int **matrix = (int**)malloc(rows * sizeof(int*)); if (matrix == NULL) return NULL; for (int i = 0; i < rows; i++) { matrix[i] = (int*)malloc(cols * sizeof(int)); if (matrix[i] == NULL) { // Cleanup on failure for (int j = 0; j < i; j++) { free(matrix[j]); } free(matrix); return NULL; } } return matrix; } void freeMatrix(int **matrix, int rows) { for (int i = 0; i < rows; i++) { free(matrix[i]); } free(matrix); } ``` ### Contiguous 2D Array (Better) ```c int **createMatrix(int rows, int cols) { int **matrix = (int**)malloc(rows * sizeof(int*)); int *data = (int*)malloc(rows * cols * sizeof(int)); if (matrix == NULL || data == NULL) { free(matrix); free(data); return NULL; } for (int i = 0; i < rows; i++) { matrix[i] = data + i * cols; } return matrix; } ``` ## Allocating Strings ```c char *strdup(const char *s) { size_t len = strlen(s) + 1; char *copy = (char*)malloc(len); if (copy) { memcpy(copy, s, len); } return copy; } // Usage char *name = strdup("Hello"); free(name); ``` ## Flexible Array Members ```c struct Person { size_t nameLength; char name[]; // Flexible array member }; struct Person *p = malloc(sizeof(struct Person) + 21); p->nameLength = 20; strcpy(p->name, "Alice"); free(p); ``` ## Memory Management Best Practices ### Always Initialize ```c int *ptr = (int*)calloc(n, sizeof(int)); // Zero-initialized ``` ### Always Check ```c int *ptr = (int*)malloc(sizeof(int)); if (ptr == NULL) { // Handle error return; } ``` ### Always Free ```c free(ptr); ptr = NULL; ``` ### Tool: valgrind ```bash valgrind --leak-check=full --show-leak-kinds=all ./program ``` ## Summary - Stack: automatic, fast, limited size - Heap: manual, flexible, larger - `malloc(size)`: allocates raw memory - `calloc(n, size)`: allocates zero-initialized memory - `realloc(ptr, newSize)`: resizes memory - `free(ptr)`: releases memory - Always check for NULL - Always set pointer to NULL after free - Use valgrind to detect leaks