Cheat Sheet

Off By One Rules

Off by one bugs are annoying.

I try to stick to these rules for consistency.

Half Open Ranges

The start index is included and the end index is NOT included
The example below, an array has a length of 5 items.
Iterating starting at the 0 index, the loop MUST terminate at n-1, otherwise there will be an out of bounds error.

int arr[] = {10, 20, 30, 40, 50};
int n = sizeof(arr) / sizeof(arr[0]); // n = 5

for (int i = 0; i < n; i++) {
    printf("%x/n", arr[i])
}

Rules

array sizes MUST be the length of the array (not the 0th indexed length)

int n = sizeof(arr) / sizeof(arr[0]); // n = 5

loops must always be i < n NOT i <= n since this is EXCLUSIVE of the end

for (int i = 0; i < n; i++) {
    printf("%x/n", arr[i])
}

Array slices should be half-open [start, end), end is not included. It’s everything UP TO END BUT NOT INCLUDING.
Computing the length given start and end is always:

// Given indexes
int len = end - start;

or

int len = sizeof(arr) / sizeof(arr[0]);

Empty ranges are expressed as: [start, start)
A single element range is: [index, index + 1), because its not inclusive.
Function parameters should also be Half Open in range: void printRange(int arr[], int start, int end)
Splitting sub-arrays, now can just use the Half open range without +1/-1 to avoid overlap.

[start, mid)
[mid, end)

Recursive base cases with indexes, this is because recursive functions usually bottom out when there is only 1 or 0 items left

if (end - start <= 1) return;

Iterating and comparing items in an array

I think this is safer because, using arr[i + 1] would end in it out bounds.

Starting at 1 allows the comparison with -1 and will terminate using the half open rule.

Drawback - arr_size must be at least 1 , if its 0 then there would be undefined behaviour.

  for (int i = 1; i < arr_size; i++) {
    if (arr[i] < arr[i - 1]) {
    ...
  ...

Finding the mid point given indexes into an array:

It allows computing the mid using a non-zero start

int mid = start + (end - start) / 2

Pointers

const variable

Variable cannot be mutated but the pointer can be mutated

const int *arr = {1, 2, 3, 4};

arr[0] = 5; // ERROR

arr = NULL; // OK

const pointer

Pointer cannot be mutated but the variable can be mutated

int *const arr = {1, 2, 3, 4};

arr = NULL; // ERROR

arr[0] = 5; // OK

const variable const pointer

Pointer cannot be mutated and the variable cannot be mutated

const int *const arr = {1, 2, 3, 4};

arr[0] = 5; // ERROR

arr = NULL; // ERROR

Macros

Macros don’t specify a return type in their definition, since they are preproccessed and expanded using the operands type

#pragma once

#define ARR_SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
#define ARR_SIZE_PTR(ptr, size) (size / sizeof((ptr)[0]))

Makefiles and Compilation

Creating Static Libraries

A static library is reusable code that can be imported and linked at compile time.

CC = gcc
CFLAGS = -Wall -std=c99 -g -O2

# Targets
SRC = $(wildcard src/*.c)
TEST_SRC = $(wildcard tests/*.c)
OBJS = $(SRC:.c=.o)
LIB = libcommon.a

all: $(LIB)

$(LIB): $(OBJS)
	ar rcs $(LIB) $(OBJS)

%.o: %.c
	$(CC) $(CFLAGS) -c $< -o $@

test: $(SRC)
	$(CC) $(CFLAGS) $(TEST_SRC) $(SRC) -o test_runner

run_test: test
	./test_runner

clean:
	rm -f $(OBJS) $(LIB) test_runner

CFLAGS:
- -Wall: enables warnings on compilation
- -std=c99: compiled with c99 standard
- -g: enables debug information for tools like gdb
- O2: enables optimization
SRC: using a wildcard, gets all c files in src
TEST_SRC: using a wildcard, gets all c files in tests
OBJS: used to convert all c files in src to object files
LIB: the name of the static library
all: $(LIB): the default command for the makefile, it will build the static library
$(LIB): $(OBJS): declares that the library depends on the object files in src
- ar: the archive command for creating static libraries in Unix
- rcs:
  - r: adds the object files into the library archive
  - c: creates the archive if it doesn’t exist
  - s: adds an index to the archive to speed up linking
- $(LIB) $(OBJ): the target and inputs for archiving
%.o: %.c: wildcare for any object file depends on c files
- $(CC) $(CFLAGS) -c $< -o $@:
  - $<: declares a prerequisite that the c files must be compiled
  - -o $@: the target output rule
test: $(SRC): compiles the test and relies on the src
run_test: test: run the test binary but relies and runs test before
clean: remove all generated artifacts

GDB

A useful debugger for C.

If you are debugging a test binary and you would like to set breakpoints in the testing code:

set environment CK_FORK=no

Starting the debugger in a terminal user interface

gdb -tui ./binary

Commands

start - starts the debugger to enable move line by line
step - moves to the next command
step <N> - steo through the program over the next N commands
print <variable> - prints the value of a variable in the program

Memory Alignment

Placing variables of the same type together in a struct, ideally from largest to lowest will minimize the padding required.

This will help optimize memory usage:

Reduce amount of memory required
Faster Access
Helps Cache Efficie

Not an optimized struct:

typedef struct {
    char a; // 1 byte
    int b;  // 4 bytes
    char c; // 1 byte
} NotOptimized

Memory Layout of the above:

Byte | 0 |  1  |  2  |  3  | 4 | 5 | 6 | 7 | 8 |  9  |  10 | 11  | Total Size
Data | a | Pad | Pad | Pad | b | b | b | b | c | Pad | Pad | Pad | 12 bytes

Optimized:

typedef struct {
    int b;  // 4 bytes
    char a; // 1 byte
    char c; // 1 byte
} Optimized

Byte | 0 | 1 | 2 | 3 | 4 | 5 |  6  |  7  | Total Size
Data | b | b | b | b | a | c | Pad | Pad | 8 bytes

The int (4 bytes) must start at an address divisble by 4 so that the CPU can fetch it in one operation. If not, the CPU may need to read multiple memory chunks in multiple operations to retrieve unaligned data.

C Cheat Sheet