11.1.1 Why Do We Need Pointers?

As the C language has a von Neumann model of computations, the program execution is essentially a sequence of data manipulation commands. The data resides in addressable memory, and the addressability of data is the propriety that allows for a more refined and effective data manipulation. Many higher-level languages lack this property because direct address manipulations are forbidden.

However, that advantage comes at a price: it becomes easier to produce subtle and usually irrecoverable errors in the code.

The necessity of storing and manipulating addresses is why we need pointers. Performing a typical case study for Listing 11-1, we observe, that in terms of the abstract C machine:

• a - is the name of data cells of abstract machine, containing the number 4 of type int.

• p_a - is the name of data cells of abstract machine, which contain the address of a variable of type int.

• p_a stores the address of a.

• *p_a is the same as a;

• &a equals p_a, but these two entities are not the same. While p_a is the name for some consecutive data cells, &a is the contents of p_a, a bit string representing an address.

Listing 11-1. pointers_ex.c

int a = 4;
int* p_a = &a;
*p_a = 10; /* a = 10*/

11.1.2 Pointer Arithmetic

Following are the only actions you can perform on pointers:

• Add or subtract integers (also negatives);

  So, we have pointers, and they contain addresses. For a computer, there is no difference between an address of an integer and an address of a string. In assembly language, as we have seen, all addresses are of the same type. Why do we need to keep the type information about what the pointer points to? What is the difference between int* and char*?

  The size of the element we are pointing at matters. By adding or subtracting an integer value X from the pointer of type T *, we, in fact, change it by X * sizeof( T ). Let’s see an example shown in Listing 11-2.

  Listing 11-2. ptr_change_ex.c

  int a = 42;             /* Assume this integer's address is 1000 */
  int* p_a = &a;
  p_a += 42;              /* 1000 + 42 * sizeof( int ) */
  p_a = p_a + 1;          /* 1168 + 1 * sizeof( int ) */
  p_a --;                 /* 1172 - 1 * sizeof( int ) */

• Take its own address. If the pointer is a variable, it is located somewhere in memory too. So, it has an address on its own! Use the & operator to take it.

• Dereference, which is a basic operation that we have also seen. We are taking a data entry from memory starting at the address, stored in the given pointer. The * operator does it. Listing 11-3 shows an example.

  Listing 11-3. deref_ex.c

  int catsAreCool = 0;
  int* ptr = &catsAreCool;
  *ptr = 1; /* catsAreCool = 1 */

• Compare (with <, >, == and alike).

  We can compare two pointers. The result is only defined if they both point to the same memory block (e.g., at different elements of the same array). Otherwise the result is random, undefined by the language standard.

• Subtract another pointer.

  If and only if we have two pointers, which are certainly pointing at the contiguous memory block, then by subtracting a smaller valued one from a greater valued one we get the amount of elements between them. For pointers x and y, we are talking about a range of elements from *x inclusive to *y exclusive (so x − x = 0).

  Starting from C99, the type of the expression ptr2 - ptr1 is a special type ptrdiff_t. It is a signed type of the same size as size_t.

  Note, that the result is different from the amount of bytes between *x and *y! The naively calculated difference would be the amount of bytes, while the result of subtraction is the amount of bytes divided by an element size. Listing 11-4 shows an example.

  Listing 11-4. ptr_diff_calc.c

  int arr[128];
  int* ptr1 = &arr[50]; /* `array` address + 50 int sizes */
  int* ptr2 = &arr[90]; /* `array` address + 90 int sizes */
  ptrdiff_t d = ptr2 - ptr1; /* exactly 40 */

In all other cases (subtracting greater pointer from lesser one, subtracting pointers pointing into different areas, etc.) the result can be absolutely random.

Addition, multiplication, and division of two pointers are syntactically incorrect; thus, they trigger an immediate compilation error.

11.1.3 The void* Type

Apart from regular pointer types, a type void* exists, which is kind of special. It forgets all information about the entity it points to, apart from its address. The pointer arithmetic is forbidden for void* pointers, because the size of the entity we are pointing at is unknown and thus cannot be added or subtracted.

Before you can work with such a pointer, you should cast it to another type explicitly. Alternatively, C allows you to assign this pointer to any other pointer (and assign to void* a pointer of any type) without any warnings. In other words, while assigning short* to long is a clear error, assignments treats void* as equal to any pointer type.

Listing 11-5 shows an example.

Listing 11-5. void_ptr_ex.c

void* a = (void*)4;
short* b = (short*) a;
b ++; /* correct, b = 6 */
b = a; /* correct */
a = b; /* correct */

11.1.4 NULL

C defines a special preprocessor constant NULL equal to 0. It means a pointer “pointing to nowhere,” an invalid pointer. By writing this value to a pointer, we can be sure that it is not yet initialized to a valid address. Otherwise, we would not be able to distinguish initialized pointers.

In most architectures people reserve a special value for invalid pointers, assuming no program will actually hold a useful value by this address.

As we already know, 0 in pointer context does not always mean a binary number with all bits cleared. Pointer-0 can be equal to 0, but this is not enforced by standard. The history knows architectures where the null-pointer was chosen in a rather exotic way . For example, some Prime 50 series computers used segment 07777, offset 0 for the null pointer; some Honeywell-Bull mainframes use the bit pattern 06000 for a kind of null pointers.

Listing 11-6 shows the correct ways to check whether the pointer is NULL or not.

Listing 11-6. null_check.c

if( x ) { ... }
if( NULL  != x ) { ... }
if( 0 != x ) { ... }

if( x != NULL  ) { ... }
if( x != 0 ) { ... }

11.1.5 A Word on ptrdiff_t

Take a look at the example shown in Listing 11-7. Can you spot a bug?

Listing 11-7. ptrdiff_bug.c

int* max;
int* cur;

int f( unsigned int e )
{
    if ( max - cur > e )
        return 1;
    else
        return 0;
}

What happens if cur > max ? It implies, that the difference between cur and max is negative. Its type is ptrdiff_t. Comparing it with a value of type unsigned int is an interesting case to study.

ptrdiff_t has as many bits as the address on the target architecture. Let’s study two cases:

• 32-bit system, where sizeof( unsigned int ) ==  4 and sizeof( ptrdiff_t ) ==  4. In this case, the types in our comparison will pass through these conversions.

  int < unsigned int
  (unsigned  int)int <  unsigned  int

  The compiler will issue a warning, because the cast from int to unsigned int is not always preserving values. You cannot freely map values in range −2³¹ . . . 2³¹ − 1 to the range 0 . . . 2³² − 1.

  For example, in case the left-hand side was equal to -1, after the conversion to unsigned int type it will become the maximal value representable in unsigned int type (2³² − 1). Apparently, the result of this comparison will be almost always equal to 0, which is wrong, because -1 is smaller than any unsigned integer.

• 64-bit system , where sizeof( unsigned int ) ==  4 and sizeof( ptrdiff_t ) ==  8. In this situation, ptrdiff_t will be probably aliased to the signed long.

  signed long < unsigned int
  long < (signed long)unsigned int

  Here the right-hand side is going to be cast. This cast preserves information, so the compiler will issue no warning.

As you see, the behavior of this code depends on target architecture, which is a big no. To avoid it, ptrdiff_t should always go in par with size_t, because only then their sizes are guaranteed to be the same.

11.1.6 Function Pointers

The von Neumann model of computations implies that the code and data reside in the same addressable memory. So, functions have addresses on their own. We can take the starting addresses of functions, pass them to other functions, call functions by pointers, store them in variables or arrays, etc. Why, however, would we do all that? It allows us for better abstractions. We can write a function that launches another function and measures its working time, or transforms an array by applying the function to all its elements. This technique allows the code to be reused on a whole new level.

The function pointer stores information about the function type just as the data pointers do. The function type includes the argument types and the return value type. A syntax that mimics the function declaration is used to declare a function pointer:

<return_value_type> (*name) (arg1, arg2, ...);

Listing 11-8 shows an example.

Listing 11-8. fun_ptr_example.c

double doubler (int a) { return a * 2.5; }
...
double (*fptr)( int );
double a;
fptr = &doubler;
a = fptr(10); /* a = 25.0 */

We have described the pointer fptr of type “a pointer to a function, that accepts int and returns double.” Then we assigned the doubler function address to it and performed a call by this pointer with an argument 10, storing the returned value in the variable a.

typedef works, and is sometimes a great help. The previous example can be rewritten as shown in Listing 11-9.

Listing 11-9. fun_ptr_example_typedef.c

double doubler (int a) { return a * 2.5; }
typedef double (megapointer_type)( int );

...
double a;
megapointer_type*  variable  =  &doubler;
a  =  variable(10);  /*  a  =  25.0  */

Now by means of typedef we have created a function type that cannot be instantiated directly. However, we can create variables of the said pointer type. We cannot create variables of the function types directly, so we add an asterisk.

First-class objects in programming languages are the entities that can be passed as a parameter, returned from functions, or assigned to a variable.

As we see, functions are not first-class objects in C. Sometimes they are called “second-class objects” because the pointers to them are first-class objects.

11.2.1 Memory Allocation

Before you can use memory cells , you have to allocate memory. There are three types of memory allocation in C.

• Automatic memory allocation occurs when we are entering a routine. When we enter the function, a part of the stack is dedicated to its local variables. When we leave the function, all information about these variables is lost. The lifetime of this data is limited by the lifetime of a function instance. Once the function terminates, the memory becomes unavailable.

  In assembly level, we have already done it in the very first assignment. The functions that performed integer printing allocated a buffer on the stack to store the resulting string. It was achieved by simply decreasing rsp by the buffer size.

  Note Never return pointers to local variables from functions! They point to the data that no longer exists.

• Static memory allocation happens during compilation in the data or constant data region. These variables exist until the program terminates. By default, the variables are initialized with zeros, and thus end up in .bss section. The constant data is allocated in .rodata ; the mutable data is allocated in .data .

• Dynamic memory allocation is needed when we do not know the size of the memory we need to allocate until some external events happen. This type of allocation relies on an implementation in the standard C library. It means that when the C standard library is not available (e.g., bare metal programming), this type of memory allocation is also unavailable.

  This type of memory allocation uses the heap.

  A part of the standard library keeps track of the reserved and available memory addresses. This part’s interface consists of the following functions, whose prototypes are located in malloc.h header file.

  • void* malloc(size_t size) allocates size bytes in heap and returns an address of the first one. Returns NULL if it fails.

    This memory is not initialized and thus holds random values.

  • void* calloc(size_t size, size_t count) allocates size * count bytes in heap and initializes them to zero. Returns the address of the first one or NULL if it fails.

  • void free(void* p) frees memory, allocated in heap.

  • void* realloc(void* ptr, size_t newsize) changes the size of a memory block starting at ptr to newsize bytes. The added memory will not be initialized. The contents are copied into the new block, and the old block is freed. Returns a pointer to the new memory block or NULL on failure.

When we no longer need a memory block we have to free it, otherwise it will stay in a “reserved” state forever, never to be reused. This situation is called memory leak. When you are using a heavy piece of software, which contains bugs related to memory management, its memory footprint can grow significantly over time without the program actually needing that much memory.

Usually, the operating system provides the program with a number of pages in advance. These pages are used until the program needs more dynamic memory to allocate. When it happens, the malloc call can internally trigger a system call (such as mmap) to request more pages.

As the void* pointer type can be assigned to any pointer type, the following code will issue no warning (see Listing 11-10) when compiling it as a C code.

Listing 11-10. malloc_no_cast.c

#include <malloc.h>

...
int* a =  malloc(200);
a[4]  =  2;

However, in C++, a popular language that was originally derived from C (and which tries to maintain backward compatibility), the void* pointer should be explicitly cast to the type of the pointer you are assigning it to. Listing 11-11 shows the difference.

Listing 11-11. malloc_cast_explicit.c

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

int* x = malloc( 40 );

int* x  =  (int*)malloc( 40  );

11.3.1 Syntax Details

C allows us to define several variables in a row.

int a,b = 4, c;

To declare several pointers, however, you have to add an asterisk before every pointer.

Listing 11-14 shows an example: a and b are pointers, but the type of c is int.

Listing 11-14. ptr_mult_decl.c

int* a, *b, c;

This rule can be worked around by creating a type alias for int* using typedef, hiding an asterisk.

Defining multiple variables in a row is a generally discouraged practice as in most cases it makes the code harder to read.

It is possible to create rather complex type definitions by mixing function pointers , arrays, pointers, etc. You can use the following algorithm to decipher them:

1. Find an identifier, and start from it.

2. Go to the right until the first closing parenthesis. Find its pair on the left. Interpret an expression between these parentheses.

3. Go “up” one level, relative to the expression we have parsed during the previous step. Find outer parentheses and repeat step 2.

We will illustrate this algorithm in an example shown in Listing 11-15. Table 11-1 describes the parsing process.

Listing 11-15. complex_decl_1.c

int* (* (*fp) (int) ) [10];

As you see, the process of deciphering complex declarations is not a breeze. It can be made simpler by using typedefs for parts of the declarations.

11.4.1 String Interning

“String interning ” is a term more accustomed to Java or C# programmers. However, in reality, a similar thing is happening in C (but only in compile time). The compiler tries to avoid duplicating strings in the read-only data region. It means that usually the equal addresses will be assigned to all three variables in the code shown in Listing 11-22.

Listing 11-22. str_intern.c

char* best_guitar_solo  = "Firth of fifth";
char* good_genesis_song = "Firth of fifth";
char* best_1973_live = "Firth of fifth";

String interning would be impossible if string literals were not protected from rewriting. Otherwise, by changing such strings in one place of a program we are introducing an unpredictable change in data used in another place, as both share the same copy of string.

11.7.1 Common Higher-Order Functions

In this assignment, we are going to implement several higher-order functions on linked lists, which should be familiar to those used to functional programming paradigm.

These functions are known under the names foreach, map, map_mut, and foldl.

• foreach accepts a pointer to the list start and a function (which returns void and accepts an int). It launches the function on each element of the list.

• map accepts a function f and a list. It returns a new list containing the results of the f applied to all elements of the source list. The source list is not affected.

For example, f (x) = x + 1 will map the list (1, 2, 3) into (2, 3, 4).

• map_mut does the same but changes the source list.

• foldl is a bit more complicated. It accepts:

  • The accumulator starting value.

  • A function f (x, a).

  • A list of elements.

It returns a value of the same type as the accumulator, computed in the following way:

1. We launch f on accumulator and the first element of the list. The result is the new accumulator value a′.

2. We launch f on a′ and the second element in list. The result is again the new accumulator value a′′.

3. We repeat the process until the list is consumed. In the end the final accumulator value is the final result.

For example, let’s take f (x, a) = x * a. By launching foldl with the accumulator value 1 and this function we will compute the product of all elements in the list.

• iterate accepts the initial value s, list length n, and function f. It then generates a list of length n as follows:
  

The functions described above are called higher-order functions, because they do accept other functions as arguments. Another example of such a function is the array sorting function qsort.

void qsort( void *base,
            size_t nmemb,
            size_t size,
            int (*compar)(const void *, const void *));

It accepts the array starting address base, elements count nmemb, size of individual elements size, and the comparator function compar. This function is the decision maker which tells which one of the given elements should be closer to the beginning of the array.

11.7.2 Assignment

The input contains an arbitrary number of integers.

1. Save these integers in a linked list.

2. Transfer all functions written in previous assignment into separate .h and c files. Do not forget to put an include guard!

3. Implement foreach; using it, output the initial list to stdout twice: the first time, separate elements with spaces, the second time output each element on the new line.

4. Implement map; using it, output the squares and the cubes of the numbers from list.

5. Implement foldl; using it, output the sum and the minimal and maximal element in the list.

6. Implement map_mut; using it, output the modules of the input numbers.

7. Implement iterate; using it, create and output the list of the powers of two (first 10 values: 1, 2, 4, 8, …).

8. Implement a function bool save(struct list* lst, const char* filename);, which will write all elements of the list into a text file filename. It should return true in case the write is successful, false otherwise.

9. Implement a function bool load(struct list** lst, const char* filename);, which will read all integers from a text file filename and write the saved list into *lst. It should return true in case the write is successful, false otherwise.

10. Save the list into a text file and load it back using the two functions above. Verify that the save and load are correct.

11. Implement a function bool serialize(struct list* lst, const char* filename);, which will write all elements of the list into a binary file filename. It should return true in case the write is successful, false otherwise.

12. Implement a function bool deserialize(struct list** lst, const char* filename);, which will read all integers from a binary file filename and write the saved list into *lst. It should return true in case the write is successful, false otherwise.

13. Serialize the list into a binary file and load it back using two functions above. Verify that the serialization and deserialization are correct.

14. Free all allocated memory.

You will have to learn to use

• Function pointers.

• limits.h and constants from it. For example, in order to find the minimal element in an array, you have to use foldl with the maximal possible int value as an accumulator and a function that returns a minimum of two elements.

• The static keyword for functions that you only want to use in one module.

You are guaranteed, that

• Input stream contains only integer numbers separated by whitespace characters.

• All numbers from input can be contained as int.

It is probably wise to write a separate function to read a list from FILE.

The solution takes about 150 lines of code, not counting the functions, defined in the previous assignment.

var count = 0;                    
mylist.Foreach(  x  =>  count  +=  1  );                    

void no_name( int x ) { count += 1; }