Lesson 308: `malloc(...)` and `free(...)`

Up to now, we have seen that in C++, dynamic memory allocation may be performed using new and delete. In addition to allocating memory, new and delete call the appropriate constructor and destructor, respectively, but also if there is an array, it will call the appropriate constructor on each entry of the array.

The original C programming language was not so helpful:

The void *malloc( size_t n ) function made a request to the operating system for $n$ bytes. You had to specify how many bytes you required. The function returned to a block of $n$ bytes, none of which are initialized.
The void free( void *p_memory ) function took an address and indicated to the operating system that the memory allocated at that address was no longer necessary and coould be freed.

Both malloc(...) and free(...) are declared in the standard library stdlib.h.

Allocating memory

The void *malloc( size_t n ) makes a request for $n$ bytes to the operating system:

If the operating system can find $n$ contiguous bytes of memory, it will designate that block of memory as belonging to your program, and malloc(...) returns the address of the first byte of that block of memory.
If the operating system cannot allocate sufficient memory, it will return the null pointer.

The defined type size_t is defined in the standard definitions libary header file stddef.h, although it is defined in other header files, as well. The size of this type depends on the system: on a 64-bit system, it will be 8 bytes, on a 32-bit system it will be 4 bytes, and in general, it is guaranteed to be large enough to store an index in a byte array.

If you are allocating dynamic memory for an instance of a type or structure, you simply need to use the sizeof operator, which examines the type and returns the number of bytes occupied in memory by one instance of that type. The return value is void *, or a generic address, so you should always cast the output to the appropriate type:

	int *p_datum = (int *)malloc( sizeof( int ) );

	if ( p_dataum == NULL ) {
		// A problem occurred...
		return -1;
	}

	*p_datum = 42;

Warning:
Because it is not necessary to cast a void pointer in C (it is in C++), there is significant discussion on this topic. One of the most lame arguments is that it may "hide the fact you forgot #include <stdlib.h>." From a software engineering persepective, allowing the reader to see exactly what you mean when you assign a void pointer to another pointer type is beneficial both for the author (a second check) and for another reader of the code.

If you wanted to allocate an array of capacity $n$ of a type, you simply multiply the size by $n$:

	unsigned int N = 20;
	int *p_data = (int *)malloc( N*sizeof( int ) );

	if ( p_dataum == NULL ) {
		// A problem occurred...
		return -1;
	}

	int i;

	// Assign the array the entries
	//   0,   1,   3,   6,  10,  15,  21,  28,  36,  45,
	//  55,  66,  78,  91, 105, 120, 136, 153, 171, 190
	p_data[0] = 0;

	for ( i = 1; i < N; ++i ) {
		p_data[i] = p_data[i - 1] + i;
	}

If you allocate memory for an instance of a structure or an array of a structure, no initializer is called: this must be done explicitly by the programmer:

	// Allocate memory for the vector
	int *p_point = (vector_2d_t *)malloc( sizeof( vector_2d_t ) );

	if ( p_point == NULL ) {
		// A problem occurred...
		return -1;
	}

	// Intialize the vector
	vector_2d_init( p_datum, 0.0, 0.0 );

If you have an array, each must be individually initalized by you, the programmer:

	unsigned int N = 20;
	int *p_points = (vector_2d_t *)malloc( N*sizeof( vector_2d_t ) );

	if ( p_points == NULL ) {
		// A problem occurred...
		return -1;
	}

	int const TWO_PI = 2.0*acos( -1.0 );

	// Initialize all vectors to twenty equally spaced vectors
	// with a 2-distance of 1 from the zero vector
	for ( i = 0; i < N; ++i ) {
		double angle = (TWO_PI*i)/N;
		vector_2d_init( &(p_data[i]), cos( angle ), sin( angle ) );
	}

If you try to access a memory location that has not been initialized, that pointer storing the address of that uninitialized memory location is described to be a wild pointer. As C++ automatically calls the constructor, it is seldom that a wild pointer rears its ugly head in C++, but it is more common in C.

Deallocating memory

As with new, the memory allocated by malloc remains allocated to the task until one of two events occurs:

you explicitly deallocate the memory with free(...), or
your program terminates.

To deallocate the memory, it is simply necessary to call free, although as with C++, it is generally a good idea to assign that pointer NULL as soon as you have called free(...):

	free( p_datum );
	p_datum = NULL;

	free( p_data );
	p_data = NULL;

	free( p_point );
	p_point = NULL;

	free( p_points );
	p_points = NULL;

Note that there is no special convention for calling free on an array, so if you needed to explicitly call a destructor on each entry of the array, it is up to you to do this work first.

Critical warning:

In C++, do not mix new and free(...) or malloc with delete. This may work with simple types, but it is likely to cause issues with arrays. In general, you should have no reason for calling malloc(...) or free(...) in C++.

Example: linked list

The following is a linked list implementation using structures in C where memory allocation and deallocation is highlighted in red. You can view the linked list in the source code directory.

`single_list.h`

#ifndef CA_UWATERLOO_DWHARDER_C_LINKED_LIST_T
#define CA_UWATERLOO_DWHARDER_C_LINKED_LIST_T

#include <stdbool.h>    // Needed for type 'bool'
#include <stddef.h>     // Needed for type 'size_t'

// Declare data structures
struct node;
struct linked_list;

// Type definitions
typedef struct node node_t;
typedef struct linked_list linked_list_t;

// Define data structures
struct node {
	int     value;
	node_t *p_next;
};

struct linked_list {
	node_t *p_head;
	node_t *p_tail;
	size_t  size;
};

// Declare functions
void init( linked_list_t *p_list );

int front( linked_list_t *p_list, bool *p_valid );
int  back( linked_list_t *p_list, bool *p_valid );

void push_front( linked_list_t *p_list, int new_value );
void  push_back( linked_list_t *p_list, int new_value );
void  pop_front( linked_list_t *p_list );

node_t *find( linked_list_t *p_list, int sought_value );

#endif

`single_list.c`

#include "linked_list.h"
#include <stddef.h>     // Needed for 'NULL'
#include <stdlib.h>     // Needed for 'malloc(...)' and 'free(...)'

void init( linked_list_t *p_list ) {
	p_list->p_head = NULL;
	p_list->p_tail = NULL;
	p_list->size = 0;
}

int front( linked_list_t *p_list, bool *p_valid ) {
	int front_value = 0;

	if ( p_list->size == 0 ) {
		*p_valid = false;
	} else {
		*p_valid = true;
		front_value = p_list->p_head->value;
	}

	return front_value;
}

int back( linked_list_t *p_list, bool *p_valid ) {
	int back_value = 0;

	if ( p_list->size == 0 ) {
		*p_valid = false;
	} else {
		*p_valid = true;
		back_value = p_list->p_tail->value;
	}

	return back_value;
}

void push_front( linked_list_t *p_list, int new_value ) {
	if ( p_list->size == 0 ) {
		// Allocate memory for a new node while updating the linked list
		p_list->p_head = (node_t *)malloc( sizeof( node_t ) );
		p_list->size = 1;

		// Initialize the new node
		p_list->p_head->value = new_value;
		p_list->p_tail = p_list->p_head;
	} else {
		// Allocate memory for a new node
		node_t *p_new_node = (node_t *)malloc( sizeof( node_t ) );

		// Initialize the new node
		p_new_node->value = new_value;
		p_new_node->p_next = p_list->p_head;

		// Update the linked list
		p_list->p_head = p_new_node;
		++( p_list->size );
	}
}

void push_back( linked_list_t *p_list, int new_value ) {
	if ( p_list->size == 0 ) {
		// Let's not repeat ourselves...
		push_front( p_list, new_value );
	} else {
		// Allocate memory for a new node
		p_list->p_tail->p_next = (node_t *)malloc( sizeof( node_t ) );

		// Update the linked list
		p_list->p_tail = p_list->p_tail->p_next;
		++( p_list->size );

		// Initialize the new node
		p_list->p_tail->value = new_value;
		p_list->p_tail->p_next = NULL;
	}
}

void pop_front( linked_list_t *p_list ) {
	if ( p_list->size == 1 ) {
		// Deallocate memory for the one node
		free( p_list->p_head );

		// Reset the linked list
		p_list->p_head = NULL;
		p_list->p_tail = NULL;
		p_list->size = 0;
	} else if ( p_list->size > 1 ) {
		// Store a pointer to the first node
		node_t *p_to_delete = p_list->p_head;

		// Update the linked list
		p_list->p_head = p_list->p_head->p_next;
		--( p_list->size );

		// Deallocate memory for the previous first node
		free( p_to_delete );
	}

	// Do nothing if the linked list is empty
}

node_t *find( linked_list_t *p_list, int sought_value ) {
	node_t *p_found_node = NULL;

	node_t *p_node;

	for ( p_node = p_list->p_head; p_node != NULL; p_node = p_node->p_next ) {
		if ( p_node->value == sought_value ) {
			p_found_node = p_node;
			break;
		}
	}

	return p_found_node;
}

Previous lesson Next lesson

ECE 050 Programming: Early Functions

Lesson 308: malloc(...) and free(...)