Chapter 18: Using Dynamic Memory Allocation

Not all data can be allocated statically or automatically. Sometimes, the number of items to be manipulated is not known beforehand; that number can only be known at runtime and may vary from run to run, depending on external inputs (such as user input and files). In the preceding chapter, we examined automatic and static memory allocation. We now stand on the threshold of an incredibly powerful feature of C – dynamic memory allocation and manipulation. Once we pass this threshold, many flexible dynamic data manipulations will be available to us. We will briefly introduce many of these data structures and their uses in this chapter.

As mentioned in the preceding chapter, dynamic memory is unnamed, so it can only be manipulated via pointers. Furthermore, dynamic memory has a different lifetime than either automatic or static memory.

The following topics will be covered in this chapter:

• Acquiring an introductory...

Technical requirements

As detailed in the Technical requirements section of Chapter 1, Running Hello World!, continue to use the tools you have chosen.

The source code for this chapter can be found at https://github.com/PacktPublishing/Learn-C-Programming-Second-Edition/tree/main/Chapter18.

Introducing dynamic memory

Do we always know exactly how many objects we will need to manipulate and allocate memory for in a program? The answer is a resounding no!

Not every situation or program can be efficiently addressed using just automatic or static memory. The number of objects may vary widely over the runtime of the program and from one run to another of the same program. The number of objects may depend on inputs from the user (covered in Chapter 20, Getting Input from the Command Line, and Chapter 21, Exploring Formatted Input), from one or more existing files (covered in Chapter 22 Working with Files, and Chapter 23, Using File Input and File Output), another device, or even from a network connection to a remote server.

Furthermore, some problems cannot be easily solved with simple automatic or static memory. These types of problems include sorting algorithms, efficient searching and lookup of large amounts of...

Allocating and releasing dynamic memory

Dynamic memory is allocated and released (deallocated) only at very explicit points by a program. It doesn't happen automatically; it doesn't happen by accident or by chance. You make this happen when you call specific C Standard Library calls to allocate and release dynamic memory.

Allocating dynamic memory

Memory allocation routines are declared in stdlib.h and are a part of the C runtime library. There are two very similar allocation routines, malloc() and calloc(), which are used to allocate a new block of memory from the heap. The main difference between malloc() and calloc() is that calloc() clears the memory block it allocates, whereas malloc() only does allocation. There is a third routine, realloc(), which is used to resize an existing block of heap memory. These functions have the following prototypes: 

void* malloc( size_t size );

void* calloc( size_t...

Special considerations for dynamic allocation

Dynamic memory allocation does not come without a cost. In this case, the cost is typically conceptual complexity. This cost also takes the form of added management of heap memory and awareness of the pitfalls of potential memory leaks.

To be honest, I should add that it may take some time to get your head around some of these concepts. For me, some of them took me quite a while to grasp. The best way, I've found, is to take a working program and alter it, see how it behaves, and then understand why it did what it did. Assume nothing. Or, start with a minimal working program that uses the mind-bending feature and then build upon it. Interact with your code; play with it. No matter how you do it, you can't just think about it. You have to twist, poke, prod, and cajole your code until you understand what it is doing. Otherwise, it is just guesswork.

Heap memory management

The amount or degree...

The linked list dynamic data structure

The most basic dynamic data structure is the linked list. A linked list is the basis for other dynamic structures, such as stacks, queues, and deques. A stack conforms to the rules that each new element must be added to the front of the list, and that each element can only be removed from the front of the list. A queue conforms to the rules that each new element must be added to the back of the list, and that each element can only be removed from the front of the list. A deque is a generalized form of both a stack and queue and has the operations of both of them.

We will implement a simple linked list and then test it from within the main() function. Later, we will employ this list structure and its routines when we return to our carddeck.c program in Chapter 24, Working with Multi-File Programs.

Create a file called linklisttester.c. It is in this single file that we will create our linked list structure, operations...

Pointers to functions

When we declare a pointer to a function, we need more than just the pointer value – we need to specify both the return type of the function and the parameter list of the function being pointed to.

Let's break this apparent syntactical gobbledygook down into understandable parts. It consists of three parts:

• The return type of the function; in this case, void.
• The name of the pointer to the function; in this case, (*printData). This indicates that printData is the name pointer to a function; the function itself may have a completely different name. Given the first item, we know that the function returns void.
• The function we'll implement via this pointer to it has a parameter list, in this case, (ListData* pData).

Given these three parts, compare the function pointer declaration to the function's prototype, in this case, PrintInt():

void (*printData)(ListData* pData)...

Other dynamic data structures

In this chapter, we have created a program that implements a singly-linked list where we can add and remove list elements, or list nodes, from the front or back of the list. This is a fairly general, minimal list implementation that leaves out a few other possibly useful operations, such as listConcatenate() to join two lists, listSplit() to break a list into two given criteria, listSort() to order the elements of the list in various ways, and listReverse() to reverse the elements of a list. We may also want to enhance our insert and remove operations so that we can add and remove nodes from anywhere in the list. Because of space limitations, we will not do so here.

The following is a brief, annotated list of other useful, possibly mind-bending, data structures:

• Doubly-linked list: A linked list that contains not only a single pointer to the next list node, but also another pointer...

Summary

In this chapter, we learned how to allocate, release, and manipulate dynamic memory. We learned about some special considerations to take into account when employing dynamic memory, such as memory management and avoidance of memory leaks. To put our knowledge into practice, we implemented a singly-linked list, which can add and remove list nodes to either the front or back of the list. We learned from this that data structures, as well as performing operations on those data structures, can allow us to create very powerful tools. Consequently, our implementation can be reused for any kind of data wherever needed. In doing so, we have gotten an introduction to the power and flexibility of dynamic data structures.

We also employed another flexible mechanism pointer to functions and saw how to pass that pointer to another function, as well as call a function using that pointer. Lastly, we got a brief overview of other important dynamic data structures, such as deques, maps,...

Questions

1. What is the difference between malloc() and calloc()?
2. What is the lifetime of memory allocated on the heap?
3. What is a memory leak?
4. Describe several reasons to create test code that verifies the code you create.