Intermediate to Advanced C Programming Notes

1. Stack and Heap
   1. Stack
   2. Heap
   3. Pros and Cons of Stack and Heap
      1. Stack
         1. Example Stack Program
      2. Heap
         1. Example Heap Program
   4. Further Reading
2. Detecting leaks easily
3. Sparse Matrix / Sparse Array in C
   1. Example: A Sparse array in action

Stack and Heap

Remember the difference between Stack and Heap by remembering “The heap is a heap of a pain.”

Stack

Region of computer’s memory that stores temporary variables.

Memory is managed for you automatically.

Is a “LIFO” (Last in first out) data strucutre and is managed by the CPU.

Whenever a function declares a variable, it is pushed to the stack. Whenever the function exits, the variables are freed.

Heap

The heap is the region of memory that is not managed automatically.

You are responsible for freeing memory by using the free() function.

Pros and Cons of Stack and Heap

If you are dealing with relatively small variables that only need to exist as long as the function is running, then the stack is a good choice.

You should use the heap when you have to allocate a large block of memory that needs to be around for a long time.

Also if you want to use variables such as arrays and structs and would like to dynamically change their size, the heap is the way to go.

Stack

Pros:

• Don’t have to worry about freeing memory you allocate. It is done for you.

Cons:

• Variables can only be accessed locally
• Variables cannot be resized

Example Stack Program

#include <stdio.h>

int main() {
	int age = 30;

	printf("you are %i years old.", *age);
}

Heap

Pros:

• Variables can be accessed globally
• No limit on memory size
• Variables can be resized using realloc()

Cons:

• (relatively) slower access
• no guaranteed efficient use of space, memory may become fragmented over time as blocks of memory are allocated, then freed
• you must manage memory (you’re in charge of allocating and freeing variables)

Example Heap Program

#include <stdio.h>
#include <stdlib.h>

int main() {
	int *age = malloc(sizeof(int));
	*age = 30;

	printf("you are %i years old.", *age);
	free(age); // Very important that you free variables on the heap!
}

Further Reading

Stack vs. Heap - GribbleLab.org

Detecting leaks easily

To detect leaks, you can use the program, Valgrind.

Usage: valgrind --leak-check=full ./app

Sparse Matrix / Sparse Array in C

Sparse arrays are a cool way to hold data efficiently if you have a lot of zero values.

As an example, say you were creating a spreadsheet application. When the user opens the program, they might be presented with a 1000x1000 grid of cells for them to work with.

They are probably not going to use all of those cells. They might only use 100 cells in total for whatever they are doing.

So, you have two options:

• Create a multi-dimensional array to hold values for all of these cells. (char cells[1000][1000])
• Use a sparse array and only keep track of the cells your user is utilizing.

The second option is clearly the best. a 1000x1000 array is very large for a lot of zero values.

Example: A Sparse array in action

Before using this example, you may want to watch this video to better understand the method we are using.

/* Sparse Matrix Example
 * Goal: Instead of storing every variable from a 2d grid into an array,
 *       you can use less memory (assuming you have more zero-values
 *       than non-zero) and faster scanning time by using a Sparse
 *       Matrix.
 *
 * The Example Matrix Grid:
 * Note: '_' represents blank spaces.
 * ------------------------
 *    [0] [1] [2]
 * [0] a   _   b
 * [1] c   d   e
 * [2] _   _   f
 *
 */

#include <stdio.h>

int main() {
	 // A list (in order from right to left) of non-zero values
	 char non_zeros[6]    = {'a', 'b', 'c', 'd', 'e', 'f'};
	 int  colmap[6]       = { 0,   2,   0,   1,   2,   2 };
	 int  row_starters[3] = { 0,        2,             5 };

	 int  current_row = 0; // Current row we are processing
	 //loop through non-zero values
	 for (int i = 0; i < 6; i++) {
		int is_row_starter = 0; // boolean of whether value is first value in a row
		// Loop through the list of row starting values
		for (int j = 0; j < 3; j++) {
			/*
			 * If i is a row-starting value, print out where it is
			 * located. Also, set is_row_start to true and current_row to
			 * the new row we are working on.s
			 */
			if (i == row_starters[j]) {
				printf("%c is located at [%i][%i]\n", non_zeros[i], colmap[i], j);
				is_row_starter = 1;
				current_row = j;
			}
		}
		// If the value is not a row-starting value.
		if(!is_row_starter) {
			printf("%c is located at [%i][%i]\n", non_zeros[i], colmap[i], current_row);
		}
	 }

	return 0;
}