COMP281 (Principles of C & Memory Management)

C Memory Management

So far we have seen:

• Static-duration Variables (Allocated in Main Memory)
• Automatic-duration Variables (Allocated on the Stack)

There are two issues with these types of variables:

• The size of the allocation must be compile-time constant.
• Their persistence cannot be manually controlled.

Dynamic Memory Allocation

Dynamic memory is allocated into the heap which grows in the opposite direction to the stack.

malloc

void *malloc(size_t size);

• It takes the size of the memory to be allocated,
• and returns the pointer to the memory that has been allocated.

We can type cast this pointer into the type that we want to put in that memory.

We can use malloc like so:

int *arr;
arr = (int *)malloc(10 * sizeof(int));

We can then use this as an array of integers as this is a pointer to 10 ints worth of space.

calloc

void *calloc(size_t nmemb, size_t size);

• nmemb - The number of things to store.
• size - The size of the thing to store.

This function also initialises the memory that is allocated.

• It also returns a pointer to the memory requested.

We can use it like so:

int *arr;
arr = (int *)calloc(10, sizeof(int));

realloc

Increases or decreases the size of the specified block of memory, reallocates it if needed:

void *realloc(pointer, int new_size);

Not Enough Memory

If there isn’t enough memory available then malloc and calloc will return NULL.

We can handle this like so:

int *arr = (int *)malloc(10 * sizeof(int));
if (arr == NULL) {
	fprintf(stderr, "out of memory!\n");
	exit(1);
}
/* code that uses arr… */

free

We can call free on the pointer to memory to return the memory back to the operating system.

It may be useful to set the pointer to NULL after the memory has been freed as a reminder.

We can use it like so:

int *j;
j = (int *)malloc(2 * sizeof(int));
free (j);

Memory Leaks

Failure to deallocate memory using free elads to a build-up of non-reusable memory.

This wastes memory resources and can lead to allocation failures.

We can use tools such as valgrind to debug memory leaks.

The Stack

Local variables, function arguments and return values are all stored on the stack.

• Each function call generates a new stack frame.
• After a function returns, the stack frame disappears, along with ll local variable and function arguments for that invocation.

Each time we call a recursive function, it’s variables and space for it’s return value is stored on the stack. This will grow until the function unwinds.

struct

struct is a user-defined datatype. It is used to construct complex datatypes from existing ones.

struct Syntax

struct [struct_tag] {
	/* member variable 1 */
	/* member variable 2 */
	/* member variable 3 */
}[struct_variables];	// <-- remember the semicolon

• struct_tag - The name for the structure (optional).

You can then define a struct like so:

struct Employee {
	char name[50];
	int age;
	char gender;
	float salary;
} employee1, employee2;

Accessing struct Members

To assign a value to a struct member, the member name must be liked with the struct variable using a dot . operator:

#include <stdio.h>
#include <string.h>

struct Lecturer {
	char name[50];
	char *room[20];
	int age;
};

int main() {
	struct Lecturer lec;
	strcpy(lec.name, "Phil Jimmieson");
	*lec.room = "Ashton 1.20";
	printf("Name: %s\n", lec.name);
	printf("Room: %s\n", *lec.room);
	return 0;
}

Be aware that you cannot assign structure arrays in the normal way. Either use strcpy or use pointers.

You can also initialise the struct like so:

struct Lecturer lec = {"Phil Jimmieson", "Ashton 1.20", 69};

This way you don’t have to mess with array types.

Array of struct

You can initialise arrays of structs in the normal way:

struct Lecturer lec[4];
lec[0] = {"Phil Jimmieson", "Ashton 1.20", 69};

Nested struct

struct Student {
	char[30] anme;
	int age;
	struct Address {
		char[50] locality;
		char[50] city;
		int pincode;
	} addr;
};

Pointers to struct

#include <stdio.h>

struct point {
	int x;
	int y;
	double dist;
};

void init_point(struct point *p) {
	/* Normal Way */
	(*p).x = (*p).y = 0;
	(*p).dist = 0.0;
	
	/* Syntactic Sugar */
	p->x = p->y = 0;
	p->dist = 0.0;
}

int main() {
	struct point p;	// allocate structure
	struct point *pt = &p;	// allocate pointer to struc
	init_point(pt);
	printf("x=%d\n", pt->x);
	return 0;
}

typedef

typedef allows us to assign alternative names to existing datatypes.

Defining a typedef

The syntax takes the following form:

typedef <existing_name> <alias_name>

For example, we can use this to shorten double-barrelled types:

typedef unsigned long ulong;

We can also use this in conjunction with struct to define new types:

typedef struct { // no name is used
	int x;
	int y;
	double dist;
} Point, *pointPtr;

From this we now have:

• A new datatype called Point.
• A new type of pointer to the custom type called pointPtr.

We can also use it to give an alias for pointers to a type:

typedef int* IntPtr;
IntPtr x, y, z;

union

union is a special datatype allowing us to store different datatypes in the same physical memory location. A union can have many members by only one member can contain a value at any given time.

union Syntax

The syntax of union is very similar to struct:

union Example {
	int i;
	float f;
	char str[20];
} e;

The difference is that the memory allocated for union is based on the largest type that it can store, instead of the sum of the type sizes.

Accessing union Members

This is very similar to assessing struct members:

#include <stdio.h>
#include <string.h>

union Data {
	int i;
	float f;
	char str[20];
};

int main() {
	union Data data;
	data.i = 66;
	data.f = 99.9;
	strcpy(data.str, "comp281");
	
	/* only data.str will print correctly */
	printf("data.i:\t%d\n", data.i);
	printf("data.f:\t%d\n", data.f);
	printf("data.str:\t%d\n", data.str);
	return 0;

The difference is that writing to additional members will overwrite previous ones.

Strings

There is no specific datatype for strings, they are just arrays of char terminated by \0 (NUL).

You should be aware of the extra NUL character when calculating the length of strings.

String Functions

strcat()

For concatenating two strings:

char *strcat(char *s1, const char *s2);

Parameters:

• s1 - A pointer to a string that will be modified.
• s2 - A pointer to a string that will be appended to the end of s1.

Returns:

• A pointer to s1 (where the resulting string resides).

strcpy()

For copying one string into another:

char *strcpy(char *dest, const char *src);

Parameters:

• dest - The pointer to the destination char array where the content is to be copied.
• src - The string to be copied.

Returns:

• A pointer to the destination string.

strlen()

Returns the length of a string:

size_t strlen(const char *s);

Parameters:

• s - The string whose length is to be found.

Returns:

• The length of the string pointed to by s.

  This does not include the NUL character in the length calculation.

strcmp()

For comparing two strings:

int strcmp(const char *str1, const char *str2);

Parameters:

• str1 - The first string to be compared.
• str2 - The second string to be compared.

Returns:

• $0$ - If s1 and s2 are the same.
• $<0$ - If s1 < s2.
• $>0$ - If s1 > s2.

strchr()

For searching for the first occurrence of a character:

char *strchr(const char *str, int c);

Parameters:

• str - The string to be searched in.
• c - The character to be searched for.

Returns:

• A pointer to the first occurrence of the character c in the string str.
• NULL if the character is not found.

Storage Classes

Each variable has a storage class which decides the scope, default initial value and lifetime. The following storage classes are mostly used:

Automatic Variables

• Scope - Local to the function block when they are defined.
• Default Initial Value - Garbage.
• Lifetime - Till the end of the function where they are defined.

They can be used in the following two ways:

int detail;
auto int details; 

If you have no specific need, use this type of variable.

External (Global) Variables

• Scope - Not bound by any function; available everywhere.
• Default Initial Value - 0 (Zero)
• Lifetime - Until the program finishes executing.

Global values can be changed by any function in the program and are declared outside of the scope of any functions:

#include <stdio.h>

int meaningOfLife = 42;

int main() {
	printf("The meaning of life, the universe and everything is: %d.\n", meaningOfLife);
}

extern

If we want to include global variables from included files then we need to use the extern keyword:

#include <stdio.h>
#include "file.c"

int main() {
	extern int a;
	printf("%d", a);
	return 0;
}

Static Variables

This tells the compiler to persist the variable until the end of the program:

• Scope - Local to the block in which the variable is defined.
• Default Initial Value - 0 (Zero)
• Lifetime - Until the program finished executing.

Instead of creating and destroying a variable every time is goes in and out of scope, a static variable is initialised only once.

This is not the same as a constant.

The following program:

#include <stdio.h>

void test();

int main() {
	test();
	test();
	test();
	return 0;
}

void test() {
	static int a = 0;
	a++;
	printf("%d\t", a);
}

will product the following output:

1	2	3

Register Variables

Tells the compiler to store the variable in a CPU register:

• Scope - Local to the function in which it is declared.
• Default Initial Value - Garbage
• Lifetime - Until the end of the function in which the variable is defined.

We can use them like so:

register int number

We cannot get the address of register variables.

Arrays & Pointers

Arrays are a sugar for pointer arithmetic. We can emulate this behaviour like so:

#include <stdio.h>
int main()j {
	int i;
	int arr[5] = {1, 2, 3, 4, 5};
	int *p = arr;
	for (i = 0; i < 5; i++) {
		printf("%d\n", *p);
		p++;
	}
}

This prints out the first 4 elements of the array.

Pointer Arithmetic

When adding or subtracting to a pointer like so:

int *p = arr;
p++;

the value added is multiplied by the size of the type.

Hence 4 would be added to the pointer here to account for the size of int.

Size of Pointer

A pointer to a type always has a size of 8 bytes on a 64 bit machine:

sizeof(int) is 4
sizeof(char) is 1
sizeof(float) is 4
sizeof(double) is 8
==========
sizeof(int*) is 8
sizeof(char*) is 8
sizeof(float*) is 8
sizeof(double*) is 8

Pointers with Functions

Pointers as Function Arguments

• A pointer as a function parameter is used to hold the addresses of arguments passes during a function call (call by reference).
• When a function parameter is called by reference any change made to the reference variable will affect the original variable.

Functions Returning Pointer Variables

A function can return a pointer to the calling function.

• Local variables of a function don’t live outside of the function.

Pointers to Functions

A pointer to a function can be used as an argument in another function.

To declare a pointer to a function:

type (*pointer-name)(parameter);

We can use this like so:

int (*s)(); // s is a pointer to a function with no parameters
	// it returns an int

We can then assign this to another function:

s = sum; // assign s to sum function

Passing the Pointer to Another Function

We can then use this, to use a function in another function:

#include <stdio.h>
int sum(int x, int y) {
	return x + y;
}
// This function takes a function that returns an int:
int sum6_9(int (*fp2)(int,int)){
	return (*fp2)(6, 9);
}
int main() {
	int (*fp)(int, int)
	fp = sum;
	printf("Sum is %d.\n", sum6_9(fp));
	return 0;
}

Using Function Pointers in Return Values

We can also have a function that houses many functions:

#include <stdio.h>
int sum(int x, int y) {
	return x + y;
}
int (*functionFactory(int z))(int, int) {
	printf("Got parameter %d.\n", z);
	int (*fp)(int,int) = sum;
	return fp;
}
int main() {
printf("Sum is %d.\n", functionFactory(3)(6,9));
return 0;
}

Pointers are a variable holding the address of another variable of the same data type.

You can use them to create:

• Shared variables between different functions without copying.
• Linked data structures such as linked lists.

Addresses vs Pointers

• You can get the address of a variable using &.
• You can store that address in a pointer using *.

int x = 9;
int *y = &x;

Pointers have their own addresses as they are a variable that holds an address.

The * Operator

The star operator has several functions:

• Multiplication:

    a = b * c;
  

• Declaring a pointer variable:

    int *a;
  

• Dereferencing a pointer:

    printf("%d", *a);
  

Dereferencing

This operation follows the pointer’s reference to get the value of its pointee.

printf("%d", *a);

If we didn’t dereference we will just get the value of the pointee’s address.

If you are pointing to a pointer that points to the value (and so on), you need to dereference an appropriate amount of times to get the value you want:

int x = 9;
int *y = &x;
int **z = &y;
printf("%d", **z);

Initialisation

If you are not sure about which variable’s address to assign to a pointer, use:

int *ptr = NULL;

This ensures that the pointer is not pointing to some random place in memory.

Call by Reference

To use a reference to a variable in a function, instead of calling by value, you can use the following:

void incr(int *z) {
	(*z)++;
}

int main(void) {
	int x = 10;
	incr(&x);
	printf("&d", &x);
	return 0;
}

The brackets need to be used around z: (*z)++ to avoid incrementing the pointer instead of the value.

Arrays

An array consists of contiguous memory locations:

• The highest address corresponds to the last element.
• The lowest address corresponds to the first element.

Declaring Arrays

Arrays can be declared like so:

float income[3];

This will create an array called income of type float that can hold three elements.

Initialising Array

Arrays can be assigned in the following ways:

income[0] = 198.76;
income[1]= 236.89;
income[2] = 218.54;

float income[3] = {198.76, 236.89, 218.54};

This syntax is only available when declaring new arrays.

Arrays can be partially initialised:

float income[3] = {198.76, 236.89};

The rest of the values are zero.

float income[];

The array contains garbage.

Multi-dimensional Arrays

We can declare and assign multi-dimensional arrays like so:

int arr[2][3]; /* not arr[2, 3] */
int i, j;
int sum = 0;
arr[0][0] = 12;
arr[0][1] = 23;
arr[0][2] = 34;
arr[1][0] = 45;
arr[1][1] = 56;
arr[1][2] = 67;
for ( i=0; i<2; i++ ) {
	for ( j=0; j<3; j++ ) {
		sum += arr[i][j];
	}
}
printf("sum = %d\n", sum);

This structure is laid out in memory with the all elements of arr[0] first, then arr[1] and so on.

When assigning implicitly, all but the leftmost dimension must be specified:

int my_array[][3] = {{12, 23, 34}, {45, 56, 67}};

Passing Arrays to Functions

As arrays are a pointer to their first element we can pass them to functions without passing a pointer:

void foo(int arr[]) {
	arr[0] = 12;
}

int arr[] = {1, 2, 3}
foo(arr);

If we did this with a single value then the change wouldn’t be reflected outside the scope of the function.

Debugging

Both lldb and gdb are nice tools for debugging C but I will be using `gdb.

Before running code in a debugger it is nice to rememeber to include debugging symbols with -g:

gcc -Wall -g test.c -o test

Open the file with the debugger with:

gdb test

Breakpoints

By setting a breakpoint we are able to step through the code:

b main

We can also use linenumbers for this.

TUI Layouts

To see our code we can run:

layout src

If we have already set a layout before we can run tui enable to get to our last layout.

Stepping Through Code

We can step through our code with the following commands:

Variables

We can use the following commands to inspect variables:

We can also modify variables:

set var i = 2

Frames

If you have several nested functions then you can use the following commands to navigate up and down the calling stack to view what is running at each level:

A fragment of code that accepts zero of more argument values, produces a result value and has zero or more side effects.

Arguments

By default arguments are passed by value:

int main (void) {
	putInFridge(eggs)
	return 0;
}

This means that if the variable changes in the function, the change is not made outide the function.

Library Functions

math.h

• sin(x) - (Radians)
• cos(x) - (Radians)
• tan(x) - (Radians)
• atan(x)
• atan2(y,x)
• exp(x) - ($e^x$)
• log(x) - ($\log_e x$)
• log10(x) - ($log_{10} x$)
• sqrt(x) - ($x \geq 0$)
• pow(x, y) ($x^y$)

string.h

• strcpy()
• strcat()
• strcmp()
• strlen()

stdio.h

• printf()
• fprintf()
• scanf()
• sscanf()

Function Definition Syntax

returnType functionName(type1 parameter1, ...) {
	// function body
}

while

This checks the statement before running the statements:

while (<expression>) {
	<statements>
}

Be aware of the limits of the data-types you are using if you are including counters in your while loops. limits.h has information regarding maximum values.

do while

This checks the statement after running the statements:

do {
	<statements>
} while (<expression>)

for

The action is performed after every iteration:

for (<initialisation>; <continuation>; <action>) {
	<statements>
}

You can remove values, such as pre-initialised variables, like so:

int num = 10;
for (; num < 20;) {
	<statements>
	num++;
}

You can also create multiple counters like so:

for (int i, int j; i < 10 || j < 20; i++, j++) {
	<statements>
}

Other Flow Control Commands

continue

The continue statement jumps to the next iteration of a loop when encountered.

break

This statement “breaks” out of a loop.

This is often used in switch case constructs.

goto

This jumps directly to a label in the code:

goto label;
label:
<statement>

This is rarely used as is makes the code hard to read.

Basic I/O

printf()

This function is used for output like so:

printf("I have %d modules this term\n", sum);

This string is then sent to the standard output (stdout).

Format Specifiers

Format specifiers start with a % and define the type and format of a value to substituted. Above we saw %d for an integer but they follow the following form:

%[flags][minimum-field-width][.precision]Type

The following types are supported:

The following flags are supported:

You can use the minimum-field-width like so:

printf("|%5s|","ABC");

/* Outputs: */
// |··ABC|

printf("|%-5s|","ABC");

/* Outputs: */
// |ABC··|

you can also use it with a runtime variable:

printf("|%-*s|",5,"ABC");

/* Outputs: */
// |ABC··|

Precision works differently for different types:

Escape Sequences

The following escape sequences are available:

scanf()

This function is used to read in data from the standard input (stdin). We can use it like so:

scanf("<format string>, &variable);

The variable must have an ampersand & before it so that the address is passed to scanf().

Operators

The following types of operators were covered in the lectures:

• Arithmetic
• Relational
• Logical
  • Short circuit evaluation is used so the whole expression may not be evaluated depending on the result of the first expression.
• Bit-wise Operators
• Assignment Operators

You can see examples of them starting at slide 25 of the slides.

There are also the following miscellaneous operators:

Comments

You can write comments like so:

/* This is a comment */

/*
 * This is also
 * a comment.
 */

Comments like these may not be recognised:

// I am generally a comment.

Comment are recommended when using values instead of constants, so that we know what the value means.

Decision Making

if & else

You can write an if else condition like so:

#include <stdio.h>
int main(void)
{
	int var;
	printf("Enter a Number: ");
	scanf("%d", &var);
	if( var % 2 == 0 )
	{
		printf("You entered an Even Number.\n");
	}
	else
	{
		printf("You entered an Odd Number\n");
	}
	return 0;
}

Nested ifs are also possible.

Conditional Operator

You can use this structure to write an if statement and assignment in one line:

var = (<conditional_statement>) ? <true_block/expression> : <false_block/expression>

This code finds the max of three numbers using this technique:

#include <stdio.h>
int main(void)
{
	int a, b, c, max;
	printf("Enter three numbers: ");
	scanf("%d%d%d", &a, &b, &c);
	max = ( a > b ) ? a : b;
	max = ( max > c ) ? max : c;
	printf("Maximum value = %d\n", max);
	return 0;
}

switch Statement

You can use this structure when checking for many conditions. It takes an integer expression like so:

#include <stdio.h>
int main(void)
{
	int score1, score2;
	printf("Enter scores for two tests: ");
	scanf("%d%d", &score1, &score2);
	switch( (score1 + score2) / 2 / 10 )
	{
		case 10:
		case 9:
		case 8:
			printf("Distinction.\n");
		break;
		case 7:
		case 6:
			printf("First Division.\n");
			break;
		case 5:
			printf("Second Division.\n");
			break;
		case 4:
			printf("Pass.\n");
			break;
		default:
			printf("Fail.\n");
	}
	return 0;
}

break finishes the block and stops you falling through to the next case.

Prefix & Postfix Operators

• Prefix Operators - Evaluate to the current value and then complete the operation.
• Postfix Operators - Complete the operation and then evaluate to the result.

Compiling and running a program takes the program through the following steps:

1. Editor - You edit the source code on disk .c
2. Preprocessor - This program processes the code.
3. Compiler - This creates object code and stores it on disk.
4. Linker - This links object code with libraries and creates .out.
5. Loader - This puts the program in memory.
6. Execution - Each instruction in memory is executed in the flow of the program.

There are four kinds of files that we work with:

1. Source Code Files *.c
   • Contain function definitions.
2. Header Files *.h
   • Contains various preprocessor statements.
   • Allow source code files to access externally-defined functions.
3. Object Files *.o or *.obj.
   • Contain function definitions in binary form.
4. Binary Executable
   • They are the output of the linker.
   • Made from a few object files.

Preprocessor

Preprocessor commands start with # and look like so:

#include <stdio.h>

#include

This allows us to access function definitions defined outside of the source file.

#include <stdio.h>

The preprocessor pastes the contents of <stdio.h> into the source code at the location of the #include statement.

Functions must be declared in the code before they are called.

#define

This is used to include header files which are used to define constants.

For example, if we define the following:

#define MAXNUM 999

then the preprocessor will turn the following:

int i = MAXNUM

into this:

int i = 999

Using #define makes your code more legible as the values are labelled in the code.

Other Preprocessor Commands

• #define
• #include
• #undef
• #ifdef
• #ifundef
• #error
• #if
• #else
• #elif
• #endif
• #pragma

The Compiler

After the program has been preprocessed it is compiled by the compiler. It turns source code into object code.

Object code is a non-executable binary version of the source code.

The compiler can be invoked as:

$ gcc foo.c

if we just want to make object files then we can run it like so:

$ gcc -c foo.c

• -c - Just compile the source files to object files.

Generating object files can be useful in large projects where you don’t want to compile everything, or for proprietary code.

You can use the following to name the output of the compiler:

$ gcc foo.x -o foo

• -o - Name the output executable.

The Linker

This links together object files into a binary executable. It is a separate program called ld.

The normal way to link together several files is like so:

$ gcc foo.o bar.o baz.o -o myprogram

C Language Basics

This simple example has the following components:

#include <stdio.h>
int main(void) {
	printf("Hello, World!\n");
	return 0;
}

• The main() function:
  • main is a C keyword that is reserved.
  • The function is called automatically for us. Ideally we should not call it ourselves in the code.
• Statements:
  • Each statement in C needs to be terminated with a semicolon ;.
  • Functions should return a result, hence we return 0;.
• Identifiers
  • These are words used to represent certain program entities such as variables and functions.
  • They have the following rules:

  Rule	Example
  Can contain a mix of characters and numbers	W3c
  Cannot start with a number	2assignments
  Must start with a letter or underscore	Number1 _area
  Can be of mixed cases	whoAmI
  Cannot contain any arithmetic operators	Sm*il
  Cannot be any other punctuation marks (separators)	!@#$%^&*(){}
  Cannot be a C keyword/reserved word	main printf
  Cannot contain a space	Oh yay
  Identifiers are case sensitive	Happy ≠ happy

The following keywords are reserved:

Basic Data Variables and Types

All data in C has to have a specified type. There are the following types:

• Integers:
  • char
    • This is ASCII text only.
    • They are only quoted in single quotes '.
  • int
  • short
  • long
  • long long
• Unsigned Integers:
  • unsigned char
  • unsigned int
  • unsigned short
  • unsigned long
  • unsigned long long
• Floating Point Numbers
  • float
  • double

Constants

These are entities that appear in the program code as fixed values. There are four types on constant:

• Integer:

    const int FOO = 999;
  

• Floating Point:

    const double FOO = 1.23e4;
  

• Character:

    const char FOO = 'l';
  

• Enumeration:

    enum City {Manchester, Liverpool, Leeds};
  

Attempts to modify a constant will result in an error.

Hello, world!

A “Hello, world!” program would look something like so:

#include <stdio.h>
int main(void) {
	printf("Hello, World!\n");
	return 0;
}

You can then compile and run with the following commands:

$ gcc hello.c
$ ./a.out
Hello, world!

Properties of C

Advantages

• C is almost a portable assembly language. It is as close to the machine as possible while it is almost universally available for existing processor architectures.
• Arbitrary memory address access and pointer arithmetic.
• Deterministic usage of resources that fit for resource-limited systems.
• C has a very small runtime. The memory footprint for its code is smaller than for most other languages.
• Many implementations of new algorithms in books are first (or only) made available in C by their authors.
• C is an old and widespread language – it’s easy to find all kinds of algorithms written in C.

Disadvantages

• No concept of Object Oriented Programming (OOP).
• No concept of namespace.
• No constructor or destructor.
• Difficult to debug.
• Compilers cannot handle exceptions (run-time errors).
• No strict data type checking:
  • An integer value can be passed for floating datatype.