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:

Cons:

Example Stack Program
#include <stdio.h>

int main() {
	int age = 30;

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

Heap

Pros:

Cons:

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:

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;
}

Leave a comment